1 files changed, 121 insertions, 112 deletions

diff --git a/erts/emulator/sys/common/erl_mmap.c b/erts/emulator/sys/common/erl_mmap.c
index 58795bd3a6..723efa772f 100644
--- a/erts/emulator/sys/common/erl_mmap.c
+++ b/erts/emulator/sys/common/erl_mmap.c
@@ -126,15 +126,15 @@ static RBTNode* check_tree(RBTree* tree, Uint);
 
 
 typedef struct {
-    RBTNode snode;
-    RBTNode anode;
+    RBTNode snode;      /* node in 'stree' */
+    RBTNode anode;      /* node in 'atree' */
     char* start;
     char* end;
 }ErtsFreeSegDesc;
 
 typedef struct {
-    RBTree stree;
-    RBTree atree;
+    RBTree stree;       /* size ordered tree */
+    RBTree atree;       /* address ordered tree */
     Uint nseg;
 }ErtsFreeSegMap;
 
@@ -277,8 +277,8 @@ static ERTS_INLINE ErtsFreeSegDesc* node_to_desc(enum SortOrder order, RBTNode*
 }
 
 #ifdef HARD_DEBUG
-static ERTS_INLINE SWord cmp_blocks(enum SortOrder order,
-                                     RBTNode* lhs, RBTNode* rhs)
+static ERTS_INLINE SWord cmp_nodes(enum SortOrder order,
+                                   RBTNode* lhs, RBTNode* rhs)
 {
     ErtsFreeSegDesc* ldesc = node_to_desc(order, lhs);
     ErtsFreeSegDesc* rdesc = node_to_desc(order, rhs);
@@ -296,10 +296,10 @@ static ERTS_INLINE SWord cmp_blocks(enum SortOrder order,
         return (char*)rdesc->start - (char*)ldesc->start;
     }
 }
-#endif
+#endif  /* HARD_DEBUG */
 
-static ERTS_INLINE SWord cmp_with_block(enum SortOrder order,
-                                        SWord sz, char* addr, RBTNode* rhs)
+static ERTS_INLINE SWord cmp_with_node(enum SortOrder order,
+                                       SWord sz, char* addr, RBTNode* rhs)
 {
     ErtsFreeSegDesc* rdesc;
     if (order != ADDR_ORDER) {
@@ -340,10 +340,6 @@ left_rotate(RBTNode **root, RBTNode *x)
     }
     y->left = x;
     set_parent(x, y);
-
-    /*SVERK y->max_sz = x->max_sz;
-    x->max_sz = node_max_size(x);
-    ASSERT(y->max_sz >= x->max_sz);*/
 }
 
 static ERTS_INLINE void
@@ -366,14 +362,11 @@ right_rotate(RBTNode **root, RBTNode *x)
     }
     y->right = x;
     set_parent(x, y);
-    /*SVERK y->max_sz = x->max_sz;
-    x->max_sz = node_max_size(x);
-    ASSERT(y->max_sz >= x->max_sz);*/
 }
 
 /*
  * Replace node x with node y
- * NOTE: block header of y is not changed
+ * NOTE: segment descriptor of y is not changed
  */
 static ERTS_INLINE void
 replace(RBTNode **root, RBTNode *x, RBTNode *y)
@@ -398,17 +391,15 @@ replace(RBTNode **root, RBTNode *x, RBTNode *y)
 	set_parent(x->right, y);
     }
 
-    /*y->flags	= x->flags;*/
     y->parent_and_color	= x->parent_and_color;
     y->right	= x->right;
     y->left	= x->left;
-    /*SVERK y->max_sz   = x->max_sz;*/
 }
 
 static void
-tree_insert_fixup(RBTNode** root, RBTNode *blk)
+tree_insert_fixup(RBTNode** root, RBTNode *node)
 {
-    RBTNode *x = blk, *y, *papa_x, *granpa_x;
+    RBTNode *x = node, *y, *papa_x, *granpa_x;
 
     /*
      * Rearrange the tree so that it satisfies the Red-Black Tree properties
@@ -501,14 +492,15 @@ tree_insert_fixup(RBTNode** root, RBTNode *blk)
 }
 
 static void
-rbt_delete(RBTNode** root, RBTNode* del)
+rbt_delete(RBTree* tree, RBTNode* del)
 {
     Uint spliced_is_black;
     RBTNode *x, *y, *z = del, *papa_y;
     RBTNode null_x; /* null_x is used to get the fixup started when we
 			splice out a node without children. */
 
-    HARD_CHECK_IS_MEMBER(*root, del);
+    HARD_CHECK_IS_MEMBER(tree->root, del);
+    HARD_CHECK_TREE(tree, 0);
 
     null_x.parent_and_color = parent_and_color(NULL, !RED_FLG);
 
@@ -529,17 +521,14 @@ rbt_delete(RBTNode** root, RBTNode* del)
     }
     else if (spliced_is_black) {
 	x = &null_x;
-        /*x->flags = 0;
-	SET_BLACK(x);*/
 	x->right = x->left = NULL;
-        /*SVERK x->max_sz = 0;*/
 	x->parent_and_color = parent_and_color(papa_y, !RED_FLG);
 	y->left = x;
     }
 
     if (!papa_y) {
-	RBT_ASSERT(*root == y);
-	*root = x;
+	RBT_ASSERT(tree->root == y);
+	tree->root = x;
     }
     else {
 	if (y == papa_y->left) {
@@ -549,15 +538,11 @@ rbt_delete(RBTNode** root, RBTNode* del)
 	    RBT_ASSERT(y == papa_y->right);
 	    papa_y->right = x;
 	}
-	/*SVERK if (y->parent != z) {
-	    lower_max_size(y->parent, (y==z ? NULL : z));
-	}*/
     }
     if (y != z) {
 	/* We spliced out the successor of z; replace z by the successor */
 	RBT_ASSERT(z != &null_x);
-	replace(root, z, y);
-	/*SVERK lower_max_size(y, NULL);*/
+	replace(&tree->root, z, y);
     }
 
     if (spliced_is_black) {
@@ -584,7 +569,7 @@ rbt_delete(RBTNode** root, RBTNode* del)
 		    SET_BLACK(y);
 		    RBT_ASSERT(IS_BLACK(papa_x));
 		    SET_RED(papa_x);
-		    left_rotate(root, papa_x);
+		    left_rotate(&tree->root, papa_x);
                     RBT_ASSERT(papa_x == parent(x));
 		    y = papa_x->right;
 		}
@@ -597,7 +582,7 @@ rbt_delete(RBTNode** root, RBTNode* del)
 		    if (IS_BLACK(y->right)) {
 			SET_BLACK(y->left);
 			SET_RED(y);
-			right_rotate(root, y);
+			right_rotate(&tree->root, y);
                         RBT_ASSERT(papa_x == parent(x));
 			y = papa_x->right;
 		    }
@@ -609,8 +594,8 @@ rbt_delete(RBTNode** root, RBTNode* del)
 		    }
 		    RBT_ASSERT(y->right);
 		    SET_BLACK(y->right);
-		    left_rotate(root, papa_x);
-		    x = *root;
+		    left_rotate(&tree->root, papa_x);
+		    x = tree->root;
 		    break;
 		}
 	    }
@@ -624,7 +609,7 @@ rbt_delete(RBTNode** root, RBTNode* del)
 		    SET_BLACK(y);
 		    RBT_ASSERT(IS_BLACK(papa_x));
 		    SET_RED(papa_x);
-		    right_rotate(root, papa_x);
+		    right_rotate(&tree->root, papa_x);
                     RBT_ASSERT(papa_x == parent(x));
 		    y = papa_x->left;
 		}
@@ -637,7 +622,7 @@ rbt_delete(RBTNode** root, RBTNode* del)
 		    if (IS_BLACK(y->left)) {
 			SET_BLACK(y->right);
 			SET_RED(y);
-			left_rotate(root, y);
+			left_rotate(&tree->root, y);
                         RBT_ASSERT(papa_x == parent(x));
 			y = papa_x->left;
 		    }
@@ -648,8 +633,8 @@ rbt_delete(RBTNode** root, RBTNode* del)
 		    }
 		    RBT_ASSERT(y->left);
 		    SET_BLACK(y->left);
-		    right_rotate(root, papa_x);
-		    x = *root;
+		    right_rotate(&tree->root, papa_x);
+		    x = tree->root;
 		    break;
 		}
 	    }
@@ -669,49 +654,44 @@ rbt_delete(RBTNode** root, RBTNode* del)
 	    RBT_ASSERT(!null_x.left);
 	    RBT_ASSERT(!null_x.right);
 	}
-	else if (*root == &null_x) {
-	    *root = NULL;
+	else if (tree->root == &null_x) {
+	    tree->root = NULL;
 	    RBT_ASSERT(!null_x.left);
 	    RBT_ASSERT(!null_x.right);
 	}
     }
+    HARD_CHECK_TREE(tree, 0);
 }
 
 
 static void
-rbt_insert(enum SortOrder order, RBTNode** root, RBTNode* blk)
+rbt_insert(enum SortOrder order, RBTree* tree, RBTNode* node)
 {
 #ifdef RBT_DEBUG
     ErtsFreeSegDesc *dbg_under=NULL, *dbg_over=NULL;
 #endif
-    ErtsFreeSegDesc* desc = node_to_desc(order, blk);
-    char* blk_addr = desc->start;
-    SWord blk_sz = desc->end - desc->start;
-    /*SVERK Uint blk_sz = AOFF_BLK_SZ(blk);*/
-
-    /*blk->flags  = 0;*/
-    blk->left	= NULL;
-    blk->right	= NULL;
-    /*SVERK blk->max_sz = blk_sz;*/
-
-    if (!*root) {
-	blk->parent_and_color = parent_and_color(NULL, !RED_FLG);
-        /*SET_BLACK(blk);*/
-	*root = blk;
+    ErtsFreeSegDesc* desc = node_to_desc(order, node);
+    char* seg_addr = desc->start;
+    SWord seg_sz = desc->end - desc->start;
+
+    HARD_CHECK_TREE(tree, 0);
+
+    node->left	= NULL;
+    node->right	= NULL;
+
+    if (!tree->root) {
+	node->parent_and_color = parent_and_color(NULL, !RED_FLG);
+	tree->root = node;
     }
     else {
-	RBTNode *x = *root;
+	RBTNode *x = tree->root;
 	while (1) {
-	    SWord diff;
-	    /*SVERK if (x->max_sz < blk_sz) {
-		x->max_sz = blk_sz;
-	    }*/
-	    diff = cmp_with_block(order, blk_sz, blk_addr, x);
+	    SWord diff = cmp_with_node(order, seg_sz, seg_addr, x);
 	    if (diff < 0) {
                 IF_RBT_DEBUG(dbg_over = node_to_desc(order, x));
 		if (!x->left) {
-		    blk->parent_and_color = parent_and_color(x, RED_FLG);
-		    x->left = blk;
+		    node->parent_and_color = parent_and_color(x, RED_FLG);
+		    x->left = node;
 		    break;
 		}
 		x = x->left;
@@ -720,43 +700,26 @@ rbt_insert(enum SortOrder order, RBTNode** root, RBTNode* blk)
                 RBT_ASSERT(diff > 0);
                 IF_RBT_DEBUG(dbg_under = node_to_desc(order, x));
                 if (!x->right) {
-                    blk->parent_and_color = parent_and_color(x, RED_FLG);
-                    x->right = blk;
+                    node->parent_and_color = parent_and_color(x, RED_FLG);
+                    x->right = node;
                     break;
                 }
                 x = x->right;
             }
-	    /*SVERK else {
-		ASSERT(flavor == AOFF_BF);
-		ASSERT(blk->flags & IS_BF_FLG);
-		ASSERT(x->flags & IS_BF_FLG);
-		SET_LIST_ELEM(blk);
-		LIST_NEXT(blk) = LIST_NEXT(x);
-		LIST_PREV(blk) = x;
-		if (LIST_NEXT(x))
-		    LIST_PREV(LIST_NEXT(x)) = blk;
-		LIST_NEXT(x) = blk;
-		return;
-	    }*/
 	}
 
-	/* Insert block into size tree */
-	RBT_ASSERT(parent(blk));
+	RBT_ASSERT(parent(node));
 #ifdef RBT_DEBUG
-        if (!order) {
+        if (order == ADDR_ORDER) {
             RBT_ASSERT(!dbg_under || dbg_under->end < desc->start);
             RBT_ASSERT(!dbg_over || dbg_over->start > desc->end);
         }
 #endif
-	/*SET_RED(blk);*/
-        RBT_ASSERT(IS_RED(blk));
-	if (IS_RED(parent(blk)))
-	    tree_insert_fixup(root, blk);
+        RBT_ASSERT(IS_RED(node));
+	if (IS_RED(parent(node)))
+	    tree_insert_fixup(&tree->root, node);
     }
-    /*SVERK if (flavor == AOFF_BF) {
-	SET_TREE_NODE(blk);
-	LIST_NEXT(blk) = NULL;
-    }*/
+    HARD_CHECK_TREE(tree, 0);
 }
 
 /*
@@ -860,9 +823,39 @@ rbt_foreach_node(RBTree* tree,
 #endif
 }
 
+#ifdef RBT_DEBUG
+static RBTNode* rbt_prev_node(RBTNode* node)
+{
+    RBTNode* x;
+    if (node->left) {
+        for (x=node->left; x->right; x=x->right)
+            ;
+        return x;
+    }
+    for (x=node; parent(x); x=parent(x)) {
+        if (parent(x)->right == x)
+            return parent(x);
+    }
+    return NULL;
+}
+static RBTNode* rbt_next_node(RBTNode* node)
+{
+    RBTNode* x;
+    if (node->right) {
+        for (x=node->right; x->left; x=x->left)
+            ;
+        return x;
+    }
+    for (x=node; parent(x); x=parent(x)) {
+        if (parent(x)->left == x)
+            return parent(x);
+    }
+    return NULL;
+}
+#endif /* RBT_DEBUG */
 
 
-/* The API to keep track of a bunch of separated free segments
+/* The API to keep track of a bunch of separated (free) segments
    (non-overlapping and non-adjacent).
  */
 static void init_free_seg_map(ErtsFreeSegMap*, int reverse_ao);
@@ -883,6 +876,9 @@ static void init_free_seg_map(ErtsFreeSegMap* map, int reverse_ao)
     map->nseg = 0;
 }
 
+/* Lookup directly adjacent free segments to the given area [start->end].
+ * The given area must not contain any free segments.
+ */
 static void adjacent_free_seg(ErtsFreeSegMap* map, char* start, char* end,
                               ErtsFreeSegDesc** under, ErtsFreeSegDesc** over)
 {
@@ -910,39 +906,49 @@ static void adjacent_free_seg(ErtsFreeSegMap* map, char* start, char* end,
     }
 }
 
+/* Initialize 'desc' and insert as new free segment [start->end].
+ * The new segment must not contain or be adjacent to any free segment in 'map'.
+ */
 static void insert_free_seg(ErtsFreeSegMap* map, ErtsFreeSegDesc* desc,
                             char* start, char* end)
 {
     desc->start = start;
     desc->end = end;
-    rbt_insert(map->atree.order, &map->atree.root, &desc->anode);
-    rbt_insert(map->stree.order, &map->stree.root, &desc->snode);
+    rbt_insert(map->atree.order, &map->atree, &desc->anode);
+    rbt_insert(map->stree.order, &map->stree, &desc->snode);
     map->nseg++;
 }
 
+/* Resize existing free segment 'desc' to [start->end].
+ * The new segment location must overlap the old location and
+ * it must not contain or be adjacent to any other free segment in 'map'.
+ */
 static void resize_free_seg(ErtsFreeSegMap* map, ErtsFreeSegDesc* desc,
                             char* start, char* end)
 {
-#ifdef DEBUG
-    ErtsFreeSegDesc *dbg_under, *dbg_over;
-    rbt_delete(&map->atree.root, &desc->anode);
-    adjacent_free_seg(map, start, end, &dbg_under, &dbg_over);
-    RBT_ASSERT(dbg_under == NULL && dbg_over == NULL);
-    rbt_insert(map->atree.order, &map->atree.root, &desc->anode);
+#ifdef RBT_DEBUG
+    RBTNode* prev = rbt_prev_node(&desc->anode);
+    RBTNode* next = rbt_next_node(&desc->anode);
+    RBT_ASSERT(!prev || anode_to_desc(prev)->end < start);
+    RBT_ASSERT(!next || anode_to_desc(next)->start > end);
 #endif
-    rbt_delete(&map->stree.root, &desc->snode);
+    rbt_delete(&map->stree, &desc->snode);
     desc->start = start;
     desc->end = end;
-    rbt_insert(map->stree.order, &map->stree.root, &desc->snode);
+    rbt_insert(map->stree.order, &map->stree, &desc->snode);
 }
 
+/* Delete existing free segment 'desc' from 'map'.
+ */
 static void delete_free_seg(ErtsFreeSegMap* map, ErtsFreeSegDesc* desc)
 {
-    rbt_delete(&map->atree.root, &desc->anode);
-    rbt_delete(&map->stree.root, &desc->snode);
+    rbt_delete(&map->atree, &desc->anode);
+    rbt_delete(&map->stree, &desc->snode);
     map->nseg--;
 }
 
+/* Lookup a free segment in 'map' with a size of at least 'need_sz' bytes.
+ */
 static ErtsFreeSegDesc* lookup_free_seg(ErtsFreeSegMap* map, SWord need_sz)
 {
     RBTNode* x = map->stree.root;
@@ -1934,7 +1940,7 @@ static int rbt_assert_is_member(RBTNode* root, RBTNode* node)
 }
 
 
-#if 1 /*SVERK*/
+#if 0
 #  define PRINT_TREE
 #else
 #  undef PRINT_TREE
@@ -1964,7 +1970,7 @@ struct check_arg_t {
     Uint size;
     RBTNode *res;
 };
-static void check_node(RBTNode* x, void* arg);
+static void check_node_callback(RBTNode* x, void* arg);
 
 
 static RBTNode *
@@ -1986,13 +1992,12 @@ check_tree(RBTree* tree, Uint size)
     RBT_ASSERT(IS_BLACK(tree->root));
     RBT_ASSERT(!parent(tree->root));
 
-    rbt_foreach_node(tree, check_node, &carg, 0);
+    rbt_foreach_node(tree, check_node_callback, &carg, 0);
 
     return carg.res;
 }
 
-/* callback */
-static void check_node(RBTNode* x, void* arg)
+static void check_node_callback(RBTNode* x, void* arg)
 {
     struct check_arg_t* a = (struct check_arg_t*) arg;
     ErtsFreeSegDesc* seg;
@@ -2005,16 +2010,16 @@ static void check_node(RBTNode* x, void* arg)
     RBT_ASSERT(parent(x) || x == a->tree->root);
 
     if (x->left) {
-        RBT_ASSERT(cmp_blocks(a->tree->order, x->left, x) < 0);
+        RBT_ASSERT(cmp_nodes(a->tree->order, x->left, x) < 0);
     }
     if (x->right) {
-        RBT_ASSERT(cmp_blocks(a->tree->order, x->right, x) > 0);
+        RBT_ASSERT(cmp_nodes(a->tree->order, x->right, x) > 0);
     }
 
     seg = node_to_desc(a->tree->order, x);
     RBT_ASSERT(seg->start < seg->end);
     if (a->size && (seg->end - seg->start) >= a->size) {
-        if (!a->res || cmp_blocks(a->tree->order, x, a->res) < 0) {
+        if (!a->res || cmp_nodes(a->tree->order, x, a->res) < 0) {
             a->res = x;
         }
     }
@@ -2063,6 +2068,8 @@ print_tree(enum SortOrder order, RBTNode* root)
 #endif /* PRINT_TREE */
 
 
+#ifdef FREE_SEG_API_SMOKE_TEST
+
 void test_it(void)
 {
     ErtsFreeSegMap map;
@@ -2128,3 +2135,5 @@ void test_it(void)
         ERTS_ASSERT(d1->start == (char*)0x15000);
     }
 }
+
+#endif /* FREE_SEG_API_SMOKE_TEST */