erts: Change naive list to rb-tree of carriers in AOFF allocator

and add new callbacks add_mbc(), remove_mbc() and largest_fblk_in_mbc()
for carrier migration.

6 files changed, 224 insertions, 135 deletions

diff --git a/erts/emulator/beam/erl_afit_alloc.c b/erts/emulator/beam/erl_afit_alloc.c
index d03d6a591c..608a4dd26d 100644
--- a/erts/emulator/beam/erl_afit_alloc.c
+++ b/erts/emulator/beam/erl_afit_alloc.c
@@ -101,6 +101,9 @@ erts_afalc_start(AFAllctr_t *afallctr,
     allctr->get_next_mbc_size		= NULL;
     allctr->creating_mbc		= NULL;
     allctr->destroying_mbc		= NULL;
+    allctr->add_mbc                     = NULL;
+    allctr->remove_mbc                  = NULL;
+    allctr->largest_fblk_in_mbc         = NULL;
     allctr->init_atoms			= init_atoms;
 
 #ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
diff --git a/erts/emulator/beam/erl_alloc_util.h b/erts/emulator/beam/erl_alloc_util.h
index 1183bf901d..739871957c 100644
--- a/erts/emulator/beam/erl_alloc_util.h
+++ b/erts/emulator/beam/erl_alloc_util.h
@@ -475,6 +475,12 @@ struct Allctr_t_ {
     Uint		(*get_next_mbc_size)	(Allctr_t *);
     void		(*creating_mbc)		(Allctr_t *, Carrier_t *, Uint32);
     void		(*destroying_mbc)	(Allctr_t *, Carrier_t *, Uint32);
+
+    /* The three callbacks below are needed to support carrier migration */
+    void		(*add_mbc)		(Allctr_t *, Carrier_t *, Uint32);
+    void		(*remove_mbc)	        (Allctr_t *, Carrier_t *, Uint32);
+    UWord		(*largest_fblk_in_mbc)  (Allctr_t *, Carrier_t *);
+
     void		(*init_atoms)		(void);
 
 #ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index 50cbfc5033..dbf930509f 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -29,15 +29,15 @@
  *              This module is a callback-module for erl_alloc_util.c
  *
  * AOFF Algorithm:
- *              The tree nodes are free-blocks ordered in address order.
+ *              The tree nodes are ordered in address order.
  *              Every node also keeps the size of the largest block in its
- *              sub-tree ('max_size'). By that we can start from root and keep
+ *              sub-tree ('max_sz'). By that we can start from root and keep
  *              left (for low addresses) while dismissing entire sub-trees with
  *              too small blocks.
  * AOFFCBF:
  *              The only difference for "bestfit within carrier" is the tree
- *              sorting order. Blocks are first sorted wrt carrier address
- *              and then wrt size if they belong to the same carrier. 
+ *              sorting order. Blocks within the same carrier are sorted
+ *              wrt size instead of address. 
  *
  * Authors: 	Rickard Green/Sverker Eriksson
  */
@@ -90,11 +90,11 @@ typedef struct AOFF_RBTree_t_ AOFF_RBTree_t;
 
 struct AOFF_RBTree_t_ {
     Block_t hdr;
-    Uint flags;
     AOFF_RBTree_t *parent;
     AOFF_RBTree_t *left;
     AOFF_RBTree_t *right;
-    Uint max_sz;  /* of all blocks in this sub-tree */
+    Uint32 flags;
+    Uint32 max_sz;  /* of all blocks in this sub-tree */
 };
 #define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
 
@@ -102,19 +102,33 @@ typedef struct AOFF_Carrier_t_ AOFF_Carrier_t;
 
 struct AOFF_Carrier_t_ {
     Carrier_t crr;
-    AOFF_Carrier_t* next;
-    AOFF_Carrier_t** prevp;
-    AOFF_RBTree_t* root;
+    AOFF_RBTree_t rbt_node;     /* My node in the carrier tree */
+    AOFF_RBTree_t* root;        /* Root of the block tree */
 };
+#define RBT_NODE_TO_MBC(PTR) ((AOFF_Carrier_t*)((char*)(PTR) - offsetof(AOFF_Carrier_t, rbt_node)))
+
+/* 
+   To support carrier migration we keep two kinds of rb-trees:
+   1. One tree of carriers for each allocator instance.
+   2. One tree of free blocks for each carrier. 
+   Both trees use the same node structure AOFF_RBTree_t and implementation.
+   Carrier nodes thus contain a phony Block_t header 'rbt_node.hdr'.
+   The size value of such a phony block is the size of the largest free block in
+   that carrier, i.e same as 'max_sz' of the root node of its block tree.  
+*/
 
 #ifdef HARD_DEBUG
-static void check_carriers(AOFFAllctr_t* alc, AOFF_Carrier_t *crr, Uint32 flags);
-static AOFF_RBTree_t * check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint);
+#  define HARD_CHECK_IS_MEMBER(ROOT,NODE) rbt_assert_is_member(ROOT,NODE)
+#  define HARD_CHECK_TREE(CRR,BF,ROOT,SZ) check_tree(CRR, BF, ROOT, SZ)
+static AOFF_RBTree_t * check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint);
+#else
+#  define HARD_CHECK_IS_MEMBER(ROOT,NODE)
+#  define HARD_CHECK_TREE(CRR,BF,ROOT,SZ)
 #endif
 
 
-/* Calculate 'max_size' of tree node x by only looking at the direct children
- * of x and x itself.
+/* Calculate 'max_sz' of tree node x by only looking at 'max_sz' of the
+ * direct children of x and the size x itself.
  */
 static ERTS_INLINE Uint node_max_size(AOFF_RBTree_t *x)
 {
@@ -128,7 +142,7 @@ static ERTS_INLINE Uint node_max_size(AOFF_RBTree_t *x)
     return sz;
 }
 
-/* Set new possibly lower 'max_size' of node and propagate change toward root
+/* Set new possibly lower 'max_sz' of node and propagate change toward root
 */
 static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
 				       AOFF_RBTree_t* stop_at)
@@ -147,21 +161,21 @@ static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
     else ASSERT(new_max == old_max);
 }
 
-static ERTS_INLINE SWord cmp_blocks(AOFFAllctr_t* alc,
+static ERTS_INLINE SWord cmp_blocks(int bestfit,
 				    AOFF_RBTree_t* lhs, AOFF_RBTree_t* rhs)
 {
-    ASSERT(FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr));
-    if (alc->bf_within_carrier) {
+    ASSERT(!bestfit || FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr));
+    if (bestfit) {
 	SWord diff = (SWord)AOFF_BLK_SZ(lhs) - (SWord)AOFF_BLK_SZ(rhs);
 	if (diff) return diff;
     }
     return (char*)lhs - (char*)rhs;
 }
 
-static ERTS_INLINE SWord cmp_cand_blk(AOFFAllctr_t* alc,
+static ERTS_INLINE SWord cmp_cand_blk(int bestfit,
 				      Block_t* cand_blk, AOFF_RBTree_t* rhs)
 {
-    if (alc->bf_within_carrier) {
+    if (bestfit) {
 	if (BLK_TO_MBC(cand_blk) == FBLK_TO_MBC(&rhs->hdr)) {
 	    SWord diff = (SWord)MBC_BLK_SZ(cand_blk) - (SWord)MBC_FBLK_SZ(&rhs->hdr);
 	    if (diff) return diff;
@@ -176,7 +190,17 @@ static Block_t*	aoff_get_free_block(Allctr_t *, Uint, Block_t *, Uint, Uint32 fl
 static void aoff_link_free_block(Allctr_t *, Block_t*, Uint32 flags);
 static void aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags);
 static void aoff_creating_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
-static void aoff_destroying_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
+static void aoff_add_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
+static void aoff_remove_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
+static UWord aoff_largest_fblk_in_mbc(Allctr_t*, Carrier_t*);
+
+/* Generic tree functions used by both carrier and block trees. */
+static void rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del);
+static void rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk);
+static AOFF_RBTree_t* rbt_search(AOFF_RBTree_t* root, Uint size);
+#ifdef HARD_DEBUG
+static int rbt_assert_is_member(AOFF_RBTree_t* root, AOFF_RBTree_t* node);
+#endif
 
 static Eterm info_options(Allctr_t *, char *, int *, void *, Uint **, Uint *);
 static void init_atoms(void);
@@ -243,7 +267,10 @@ erts_aoffalc_start(AOFFAllctr_t *alc,
 
     allctr->get_next_mbc_size		= NULL;
     allctr->creating_mbc		= aoff_creating_mbc;
-    allctr->destroying_mbc		= aoff_destroying_mbc;
+    allctr->destroying_mbc		= aoff_remove_mbc;
+    allctr->add_mbc                     = aoff_add_mbc;
+    allctr->remove_mbc                  = aoff_remove_mbc;
+    allctr->largest_fblk_in_mbc         = aoff_largest_fblk_in_mbc;
     allctr->init_atoms			= init_atoms;
 
 #ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
@@ -449,21 +476,45 @@ static void
 aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
 {
 #ifdef HARD_DEBUG
-    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+    AOFFAllctr_t* alc = (AOFFAllctr_t*)allctr;
 #endif
     AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(del);
-    AOFF_RBTree_t **root = &crr->root;
+
+    ASSERT(crr->rbt_node.hdr.bhdr == crr->root->max_sz);
+    HARD_CHECK_IS_MEMBER(((flags & ERTS_ALCU_FLG_SBMBC) ? alc->sbmbc_root : alc->mbc_root),
+			 &crr->rbt_node);
+    HARD_CHECK_TREE(&crr->crr, alc->bf_within_carrier, crr->root, 0);
+
+    rbt_delete(&crr->root, (AOFF_RBTree_t*)del);
+
+    HARD_CHECK_TREE(&crr->crr, alc->bf_within_carrier, crr->root, 0);
+
+   /* Update the carrier tree with a potentially new (lower) max_sz
+    */    
+    if (crr->root) {
+	if (crr->rbt_node.hdr.bhdr == crr->root->max_sz) {
+	    return;
+	}
+	ASSERT(crr->rbt_node.hdr.bhdr > crr->root->max_sz);
+	crr->rbt_node.hdr.bhdr = crr->root->max_sz; 
+    }
+    else {
+	crr->rbt_node.hdr.bhdr = 0;
+    }
+    lower_max_size(&crr->rbt_node, NULL);
+}
+
+static void
+rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del)
+{
     Uint spliced_is_black;
-    AOFF_RBTree_t *x, *y, *z = (AOFF_RBTree_t *) del;
+    AOFF_RBTree_t *x, *y, *z = del;
     AOFF_RBTree_t null_x; /* null_x is used to get the fixup started when we
 			splice out a node without children. */
 
-    null_x.parent = NULL;
+    HARD_CHECK_IS_MEMBER(*root, del);
 
-#ifdef HARD_DEBUG
-    check_carriers(alc, crr, flags);
-    check_tree(alc, *root, 0);
-#endif
+    null_x.parent = NULL;
 
     /* Remove node from tree... */
 
@@ -618,29 +669,47 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
 	    RBT_ASSERT(!null_x.right);
 	}
     }
-
     DESTROY_TREE_NODE(del);
-
-#ifdef HARD_DEBUG
-    check_tree(alc, *root, 0);
-#endif
 }
 
 static void
 aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
 {
-    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+    AOFFAllctr_t* alc = (AOFFAllctr_t*) allctr;
     AOFF_RBTree_t *blk = (AOFF_RBTree_t *) block;
-    AOFF_RBTree_t **root;
+    AOFF_RBTree_t *crr_node;
     AOFF_Carrier_t *blk_crr = (AOFF_Carrier_t*) FBLK_TO_MBC(block);
     Uint blk_sz = AOFF_BLK_SZ(blk);
 
-#ifdef HARD_DEBUG
-    check_carriers(alc, blk_crr, flags);
-    check_tree(alc, blk_crr->root, 0);
-#endif
+    ASSERT(allctr == blk_crr->crr.allctr);
+    ASSERT(blk_crr->rbt_node.hdr.bhdr == (blk_crr->root ? blk_crr->root->max_sz : 0));
+
+    HARD_CHECK_IS_MEMBER(((flags & ERTS_ALCU_FLG_SBMBC) ? alc->sbmbc_root : alc->mbc_root),
+			 &blk_crr->rbt_node);
+    HARD_CHECK_TREE(&blk_crr->crr, alc->bf_within_carrier, blk_crr->root, 0);
+
+    rbt_insert(alc->bf_within_carrier, &blk_crr->root, blk);
+
+    /* Update the carrier tree with a potential new (larger) max_sz
+    */
+    crr_node = &blk_crr->rbt_node;
+    if (blk_sz > crr_node->hdr.bhdr) {
+	ASSERT(blk_sz == blk_crr->root->max_sz);
+	crr_node->hdr.bhdr = blk_sz;
+	while (blk_sz > crr_node->max_sz) {
+	    crr_node->max_sz = blk_sz;
+	    crr_node = crr_node->parent;
+	    if (!crr_node) break;
+	}
+    }
+    HARD_CHECK_TREE(&blk_crr->crr, alc->bf_within_carrier, blk_crr->root, 0);
+}
+
+static void
+rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
+{
+    Uint blk_sz = AOFF_BLK_SZ(blk);
 
-    root = &blk_crr->root;
     blk->flags	= 0;
     blk->left	= NULL;
     blk->right	= NULL;
@@ -657,7 +726,7 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
 	    if (x->max_sz < blk_sz) {
 		x->max_sz = blk_sz;
 	    }
-	    if (cmp_blocks(alc, blk, x) < 0) {
+	    if (cmp_blocks(bestfit, blk, x) < 0) {
 		if (!x->left) {
 		    blk->parent = x;
 		    x->left = blk;
@@ -682,10 +751,28 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
 	if (IS_RED(blk->parent))
 	    tree_insert_fixup(root, blk);
     }
+}
 
-#ifdef HARD_DEBUG
-    check_tree(alc, *root, 0);
-#endif
+static AOFF_RBTree_t*
+rbt_search(AOFF_RBTree_t* root, Uint size)
+{
+    AOFF_RBTree_t* x = root;
+
+    ASSERT(x);
+    for (;;) {
+	if (x->left && x->left->max_sz >= size) {
+	    x = x->left;
+	}
+	else if (AOFF_BLK_SZ(x) >= size) {
+	    return x;
+	}
+	else {
+	    x = x->right;
+	    if (!x) {
+		return NULL;
+	    }
+	}
+    }
 }
 
 static Block_t *
@@ -693,44 +780,31 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
 		    Block_t *cand_blk, Uint cand_size, Uint32 flags)
 {
     AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
-    AOFF_Carrier_t *crr = ((flags & ERTS_ALCU_FLG_SBMBC)
-			   ? alc->sbmbc_first : alc->mbc_first);
-    AOFF_RBTree_t *x, *blk = NULL;
+    AOFF_RBTree_t *crr_node = ((flags & ERTS_ALCU_FLG_SBMBC)
+			       ? alc->sbmbc_root : alc->mbc_root);
+    AOFF_Carrier_t* crr;
+    AOFF_RBTree_t *blk = NULL;
 #ifdef HARD_DEBUG
     AOFF_RBTree_t* dbg_blk;
 #endif
-
+    
     ASSERT(!cand_blk || cand_size >= size);
 
     /* Get first-fit carrier
      */
-    for (;;) {
-	if (!crr)
-	    return NULL;
-	if (crr->root && crr->root->max_sz >= size)
-	    break;
-	crr = crr->next;
+    if (!crr_node || !(blk=rbt_search(crr_node, size))) {
+	return NULL;
     }
+    crr = RBT_NODE_TO_MBC(blk);
 
     /* Get block within carrier tree
      */
-    x = crr->root;
 #ifdef HARD_DEBUG
-    dbg_blk = check_tree(alc, x, size);
+    dbg_blk = HARD_CHECK_TREE(&crr->crr, alc->bf_within_carrier, crr->root, size);
 #endif
 
-    while (x) {
-	if (x->left && x->left->max_sz >= size) {
-	    x = x->left;
-	}
-	else if (AOFF_BLK_SZ(x) >= size) {
-	    blk = x;
-	    break;
-	}
-	else {
-	    x = x->right;
-	}
-    }
+    blk = rbt_search(crr->root, size);
+    ASSERT(blk);
 
 #ifdef HARD_DEBUG
     ASSERT(blk == dbg_blk);
@@ -739,7 +813,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
     if (!blk)
 	return NULL;
 
-    if (cand_blk && cmp_cand_blk(alc, cand_blk, blk) < 0) {
+    if (cand_blk && cmp_cand_blk(alc->bf_within_carrier, cand_blk, blk) < 0) {
 	return NULL; /* cand_blk was better */
     }
 
@@ -752,50 +826,61 @@ static void aoff_creating_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags
 {
     AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
     AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
-    AOFF_Carrier_t **prevp = ((flags & ERTS_ALCU_FLG_SBMBC)
-			      ? &alc->sbmbc_first : &alc->mbc_first);
-    AOFF_Carrier_t *p;
+    AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC)
+			    ? &alc->sbmbc_root : &alc->mbc_root);
 
+    HARD_CHECK_TREE(NULL, 0, *root, 0);
 
-    /* Link carrier in address order
+    /* Link carrier in address order tree
      */
-    for (p = *prevp; p && crr > p; p = p->next) {
-	prevp = &p->next;
-    }
-    ASSERT(crr != p);
-
-    crr->next = p;
-    crr->prevp = prevp;
-    *prevp = crr;
-    if (p) {
-	ASSERT(prevp == p->prevp);
-	p->prevp = &crr->next;
-    }
+    crr->rbt_node.hdr.bhdr = 0;
+    rbt_insert(0, root, &crr->rbt_node);
 
     /* aoff_link_free_block will add free block later */
     crr->root = NULL;
+
+    HARD_CHECK_TREE(NULL, 0, *root, 0);
 }
 
-static void aoff_destroying_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags)
+static void aoff_add_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags)
 {
     AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
     AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
-    AOFF_Carrier_t **pp = ((flags & ERTS_ALCU_FLG_SBMBC)
-			   ? &alc->sbmbc_first : &alc->mbc_first);
+    AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC)
+			    ? &alc->sbmbc_root : &alc->mbc_root);
+
+    HARD_CHECK_TREE(NULL, 0, *root, 0);
 
-    /* Unlink carrier
+    /* Link carrier in address order tree
      */
-    while (*pp != crr) {
-	ASSERT(*pp && (*pp)->prevp == pp);
-	pp = &(*pp)->next;
-    }
-    *pp = crr->next;
-    if (crr->next) {
-	ASSERT(crr->next->prevp == &crr->next);
-	crr->next->prevp = crr->prevp;
-    }
+    rbt_insert(0, root, &crr->rbt_node);
+
+    HARD_CHECK_TREE(NULL, 0, *root, 0);
+}
+
+static void aoff_remove_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags)
+{
+    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+    AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC)
+			    ? &alc->sbmbc_root : &alc->mbc_root);
+
+    ASSERT(allctr == carrier->allctr);
+    HARD_CHECK_TREE(NULL, 0, *root, 0);
+
+    rbt_delete(root, &crr->rbt_node);
+
+    HARD_CHECK_TREE(NULL, 0, *root, 0);
 }
 
+static UWord aoff_largest_fblk_in_mbc(Allctr_t* allctr, Carrier_t* carrier)
+{
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+
+    ASSERT(allctr == carrier->allctr);
+    ASSERT(crr->rbt_node.hdr.bhdr == (crr->root ? crr->root->max_sz : 0));
+    return crr->rbt_node.hdr.bhdr;
+}
 
 /*
  * info_options()
@@ -901,16 +986,10 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2)
 {
     switch (op) {
     case 0x501: {
-	AOFF_Carrier_t* crr = ((AOFFAllctr_t *) a1)->mbc_first;
+	AOFF_RBTree_t *node = ((AOFFAllctr_t *) a1)->mbc_root; 
 	Uint size = (Uint) a2;
-	for (;;) {
-	    if (!crr)
-		return (UWord)NULL;
-	    if (crr->root && crr->root->max_sz >= size)
-		break;
-	    crr = crr->next;
-	}	
-	return (UWord) crr->root;
+	node = rbt_search(node, size);
+	return (UWord) (node ? RBT_NODE_TO_MBC(node)->root : NULL);
     }
     case 0x502:	return (UWord) ((AOFF_RBTree_t *) a1)->parent;
     case 0x503:	return (UWord) ((AOFF_RBTree_t *) a1)->left;
@@ -931,23 +1010,16 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2)
 
 #ifdef HARD_DEBUG
 
-static void check_carriers(AOFFAllctr_t* alc, AOFF_Carrier_t *crr, Uint32 flags)
-{ 
-    AOFF_Carrier_t *p = ((flags & ERTS_ALCU_FLG_SBMBC)
-			 ? alc->sbmbc_first : alc->mbc_first);
-    int found_it = 0;
-
-    for ( ; p; p = p->next) {
-	if (p == crr) {
-	    ASSERT(!found_it);
-	    found_it = 1;
-	}
-	ASSERT(!p->next || p->next > p);
-    }
-    ASSERT(found_it);
+static int rbt_assert_is_member(AOFF_RBTree_t* root, AOFF_RBTree_t* node)
+{
+    while (node != root) {
+	ASSERT(node->parent);
+	ASSERT(node->parent->left == node || node->parent->right == node);
+	node = node->parent;
+    }    
+    return 1;
 }
 
-
 #define IS_LEFT_VISITED(FB)	((FB)->flags & LEFT_VISITED_FLG)
 #define IS_RIGHT_VISITED(FB)	((FB)->flags & RIGHT_VISITED_FLG)
 
@@ -984,7 +1056,7 @@ static void print_tree(AOFF_RBTree_t*);
  */
 
 static AOFF_RBTree_t *
-check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint size)
+check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint size)
 {
     AOFF_RBTree_t *res = NULL;
     Sint blacks;
@@ -1046,9 +1118,12 @@ check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint size)
 	if (depth > max_depth)
 	    max_depth = depth;
 
-	crr = FBLK_TO_MBC(&x->hdr);
-	ASSERT((char*)x > (char*)crr);
-	ASSERT(((char*)x + AOFF_BLK_SZ(x)) <= ((char*)crr + CARRIER_SZ(crr)));
+	if (within_crr) {
+	    crr = FBLK_TO_MBC(&x->hdr);
+	    ASSERT(crr == within_crr);
+	    ASSERT((char*)x > (char*)crr);
+	    ASSERT(((char*)x + AOFF_BLK_SZ(x)) <= ((char*)crr + CARRIER_SZ(crr)));
+	}
 
 	if (IS_RED(x)) {
 	    ASSERT(IS_BLACK(x->right));
@@ -1059,13 +1134,13 @@ check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint size)
 
 	if (x->left) {
 	    ASSERT(x->left->parent == x);
-	    ASSERT(cmp_blocks(alc, x->left, x) < 0);
+	    ASSERT(cmp_blocks(bestfit, x->left, x) < 0);
 	    ASSERT(x->left->max_sz <= x->max_sz);	    
 	}
 
 	if (x->right) {
 	    ASSERT(x->right->parent == x);
-	    ASSERT(cmp_blocks(alc, x->right, x) > 0);
+	    ASSERT(cmp_blocks(bestfit, x->right, x) > 0);
 	    ASSERT(x->right->max_sz <= x->max_sz);	    
 	}
 	ASSERT(x->max_sz >= AOFF_BLK_SZ(x));
@@ -1074,7 +1149,7 @@ check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint size)
 	       || x->max_sz == (x->right ? x->right->max_sz : 0));
 
 	if (size && AOFF_BLK_SZ(x) >= size) {
-	    if (!res || cmp_blocks(alc, x, res) < 0) {
+	    if (!res || cmp_blocks(bestfit, x, res) < 0) {
 		res = x;
 	    }
 	}
@@ -1113,9 +1188,9 @@ print_tree_aux(AOFF_RBTree_t *x, int indent)
 	for (i = 0; i < indent; i++) {
 	    putc(' ', stderr);
 	}
-	fprintf(stderr, "%s: sz=%lu addr=0x%lx max_size=%lu\r\n",
+	fprintf(stderr, "%s: sz=%lu addr=0x%lx max_size=%u\r\n",
 		IS_BLACK(x) ? "BLACK" : "RED",
-		AOFF_BLK_SZ(x), (Uint)x, x->max_sz);
+		AOFF_BLK_SZ(x), (Uint)x, (unsigned)x->max_sz);
 	print_tree_aux(x->left,  indent + INDENT_STEP);
     }
 }
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.h b/erts/emulator/beam/erl_ao_firstfit_alloc.h
index a8fa69ab79..36995a20f0 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.h
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.h
@@ -51,8 +51,8 @@ Allctr_t *erts_aoffalc_start(AOFFAllctr_t *, AOFFAllctrInit_t*, AllctrInit_t *);
 struct AOFFAllctr_t_ {
     Allctr_t		allctr; /* Has to be first! */
 
-    struct AOFF_Carrier_t_* mbc_first;
-    struct AOFF_Carrier_t_* sbmbc_first;
+    struct AOFF_RBTree_t_* mbc_root;
+    struct AOFF_RBTree_t_* sbmbc_root;
     int bf_within_carrier;
 };
 
diff --git a/erts/emulator/beam/erl_bestfit_alloc.c b/erts/emulator/beam/erl_bestfit_alloc.c
index 42c7c9bbe2..dff69faa4e 100644
--- a/erts/emulator/beam/erl_bestfit_alloc.c
+++ b/erts/emulator/beam/erl_bestfit_alloc.c
@@ -208,6 +208,9 @@ erts_bfalc_start(BFAllctr_t *bfallctr,
     allctr->get_next_mbc_size		= NULL;
     allctr->creating_mbc		= NULL;
     allctr->destroying_mbc		= NULL;
+    allctr->add_mbc                     = NULL;
+    allctr->remove_mbc		        = NULL;
+    allctr->largest_fblk_in_mbc         = NULL;
     allctr->init_atoms			= init_atoms;
 
 #ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
diff --git a/erts/emulator/beam/erl_goodfit_alloc.c b/erts/emulator/beam/erl_goodfit_alloc.c
index fce443c101..72620a362b 100644
--- a/erts/emulator/beam/erl_goodfit_alloc.c
+++ b/erts/emulator/beam/erl_goodfit_alloc.c
@@ -223,7 +223,9 @@ erts_gfalc_start(GFAllctr_t *gfallctr,
     allctr->get_next_mbc_size		= NULL;
     allctr->creating_mbc		= update_last_aux_mbc;
     allctr->destroying_mbc		= update_last_aux_mbc;
-
+    allctr->add_mbc		        = NULL;
+    allctr->remove_mbc		        = NULL;
+    allctr->largest_fblk_in_mbc         = NULL;
     allctr->init_atoms			= init_atoms;
 
 #ifdef ERTS_ALLOC_UTIL_HARD_DEBUG