1 files changed, 324 insertions, 97 deletions

diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index 6ce209085c..f73ac2eb6e 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -28,11 +28,16 @@
  *
  *              This module is a callback-module for erl_alloc_util.c
  *
- * Algorithm:   The tree nodes are free-blocks ordered in address order.
+ * AOFF Algorithm:
+ *              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 within the same carrier are sorted
+ *              wrt size instead of address. 
  *
  * Authors: 	Rickard Green/Sverker Eriksson
  */
@@ -85,21 +90,45 @@ 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)
 
+typedef struct AOFF_Carrier_t_ AOFF_Carrier_t;
+
+struct AOFF_Carrier_t_ {
+    Carrier_t crr;
+    AOFF_RBTree_t rbt_node;     /* My node in the carrier tree */
+    AOFF_RBTree_t* root;        /* Root of my 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 AOFF_RBTree_t * check_tree(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)
 {
@@ -113,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)
@@ -132,32 +161,53 @@ static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
     else ASSERT(new_max == old_max);
 }
 
+static ERTS_INLINE SWord cmp_blocks(int bestfit,
+				    AOFF_RBTree_t* lhs, AOFF_RBTree_t* rhs)
+{
+    ASSERT(lhs != rhs);
+    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(int bestfit,
+				      Block_t* cand_blk, AOFF_RBTree_t* rhs)
+{
+    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;
+	}
+    }
+    return (char*)cand_blk - (char*)rhs;
+}
+
 
 /* Prototypes of callback functions */
-static Block_t*	aoff_get_free_block(Allctr_t *, Uint, Block_t *, Uint, Uint32 flags);
-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 Block_t*	aoff_get_free_block(Allctr_t *, Uint, Block_t *, Uint);
+static void aoff_link_free_block(Allctr_t *, Block_t*);
+static void aoff_unlink_free_block(Allctr_t *allctr, Block_t *del);
+static void aoff_creating_mbc(Allctr_t*, Carrier_t*);
+static void aoff_destroying_mbc(Allctr_t*, Carrier_t*);
+static void aoff_add_mbc(Allctr_t*, Carrier_t*);
+static void aoff_remove_mbc(Allctr_t*, Carrier_t*);
+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);
 
 
-
-#ifdef DEBUG
-
-/* Destroy all tree fields */
-#define DESTROY_TREE_NODE(N)						\
-  sys_memset((void *) (((Block_t *) (N)) + 1),				\
-	     0xff,							\
-	     (sizeof(AOFF_RBTree_t) - sizeof(Block_t)))
-
-#else
-
-#define DESTROY_TREE_NODE(N)
-
-#endif
-
-
 static int atoms_initialized = 0;
 
 void
@@ -184,11 +234,14 @@ erts_aoffalc_start(AOFFAllctr_t *alc,
 
     sys_memcpy((void *) alc, (void *) &zero.allctr, sizeof(AOFFAllctr_t));
 
+    alc->bf_within_carrier              = aoffinit->bf_within_carrier;
+    allctr->mbc_header_size		= sizeof(AOFF_Carrier_t);
     allctr->min_mbc_size		= MIN_MBC_SZ;
     allctr->min_mbc_first_free_size	= MIN_MBC_FIRST_FREE_SZ;
     allctr->min_block_size		= sizeof(AOFF_RBTree_t);
 
-    allctr->vsn_str			= ERTS_ALC_AOFF_ALLOC_VSN_STR;
+    allctr->vsn_str			= aoffinit->bf_within_carrier ?
+	ERTS_ALC_AOFF_CBF_ALLOC_VSN_STR : ERTS_ALC_AOFF_ALLOC_VSN_STR;
 
 
     /* Callback functions */
@@ -199,8 +252,11 @@ erts_aoffalc_start(AOFFAllctr_t *alc,
     allctr->info_options		= info_options;
 
     allctr->get_next_mbc_size		= NULL;
-    allctr->creating_mbc		= NULL;
-    allctr->destroying_mbc		= NULL;
+    allctr->creating_mbc		= aoff_creating_mbc;
+    allctr->destroying_mbc		= aoff_destroying_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
@@ -306,7 +362,6 @@ replace(AOFF_RBTree_t **root, AOFF_RBTree_t *x, AOFF_RBTree_t *y)
 
     y->max_sz = x->max_sz;
     lower_max_size(y, NULL);
-    DESTROY_TREE_NODE(x);
 }
 
 static void
@@ -403,21 +458,47 @@ tree_insert_fixup(AOFF_RBTree_t** root, AOFF_RBTree_t *blk)
 }
 
 static void
-aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
+aoff_unlink_free_block(Allctr_t *allctr, Block_t *del)
+{
+#ifdef HARD_DEBUG
+    AOFFAllctr_t* alc = (AOFFAllctr_t*)allctr;
+#endif
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(del);
+
+    ASSERT(crr->rbt_node.hdr.bhdr == crr->root->max_sz);
+    HARD_CHECK_IS_MEMBER(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)
 {
-    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
-    AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC)
-			    ? &alc->sbmbc_root : &alc->mbc_root);
     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_tree(*root, 0);
-#endif
+    null_x.parent = NULL;
 
     /* Remove node from tree... */
 
@@ -572,26 +653,43 @@ 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(*root, 0);
-#endif
 }
 
 static void
-aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
+aoff_link_free_block(Allctr_t *allctr, Block_t *block)
 {
-    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+    AOFFAllctr_t* alc = (AOFFAllctr_t*) allctr;
     AOFF_RBTree_t *blk = (AOFF_RBTree_t *) block;
-    AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC)
-			    ? &alc->sbmbc_root : &alc->mbc_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_tree(*root, 0);
-#endif
+    ASSERT(allctr == ERTS_ALC_CARRIER_TO_ALLCTR(&blk_crr->crr));
+    ASSERT(blk_crr->rbt_node.hdr.bhdr == (blk_crr->root ? blk_crr->root->max_sz : 0));
+    HARD_CHECK_IS_MEMBER(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);
 
     blk->flags	= 0;
     blk->left	= NULL;
@@ -609,7 +707,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 (blk < x) {
+	    if (cmp_blocks(bestfit, blk, x) < 0) {
 		if (!x->left) {
 		    blk->parent = x;
 		    x->left = blk;
@@ -625,7 +723,6 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
 		}
 		x = x->right;
 	    }
-
 	}
 
 	/* Insert block into size tree */
@@ -635,38 +732,59 @@ 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(*root, 0);
-#endif
 }
 
-static Block_t *
-aoff_get_free_block(Allctr_t *allctr, Uint size,
-		    Block_t *cand_blk, Uint cand_size, Uint32 flags)
+static AOFF_RBTree_t*
+rbt_search(AOFF_RBTree_t* root, Uint size)
 {
-    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
-    AOFF_RBTree_t *x = ((flags & ERTS_ALCU_FLG_SBMBC)
-		       ? alc->sbmbc_root : alc->mbc_root);
-    AOFF_RBTree_t *blk = NULL;
-#ifdef HARD_DEBUG
-    AOFF_RBTree_t* dbg_blk = check_tree(x, size);
-#endif
+    AOFF_RBTree_t* x = root;
 
-    ASSERT(!cand_blk || cand_size >= size);
-
-    while (x) {
+    ASSERT(x);
+    for (;;) {
 	if (x->left && x->left->max_sz >= size) {
 	    x = x->left;
 	}
 	else if (AOFF_BLK_SZ(x) >= size) {
-	    blk = x;
-	    break;
+	    return x;
 	}
 	else {
 	    x = x->right;
+	    if (!x) {
+		return NULL;
+	    }
 	}
     }
+}
+
+static Block_t *
+aoff_get_free_block(Allctr_t *allctr, Uint size,
+		    Block_t *cand_blk, Uint cand_size)
+{
+    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+    AOFF_RBTree_t *crr_node = 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
+     */
+    if (!crr_node || !(blk=rbt_search(crr_node, size))) {
+	return NULL;
+    }
+    crr = RBT_NODE_TO_MBC(blk);
+
+    /* Get block within carrier tree
+     */
+#ifdef HARD_DEBUG
+    dbg_blk = HARD_CHECK_TREE(&crr->crr, alc->bf_within_carrier, crr->root, size);
+#endif
+
+    blk = rbt_search(crr->root, size);
+    ASSERT(blk);
 
 #ifdef HARD_DEBUG
     ASSERT(blk == dbg_blk);
@@ -675,15 +793,87 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
     if (!blk)
 	return NULL;
 
-    if (cand_blk && cand_blk < &blk->hdr) {
+    if (cand_blk && cmp_cand_blk(alc->bf_within_carrier, cand_blk, blk) < 0) {
 	return NULL; /* cand_blk was better */
     }
 
-    aoff_unlink_free_block(allctr, (Block_t *) blk, flags);
+    aoff_unlink_free_block(allctr, (Block_t *) blk);
 
     return (Block_t *) blk;
 }
 
+static void aoff_creating_mbc(Allctr_t *allctr, Carrier_t *carrier)
+{
+    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+    AOFF_RBTree_t **root = &alc->mbc_root;
+
+    HARD_CHECK_TREE(NULL, 0, *root, 0);
+
+    /* Link carrier in address order tree
+     */
+    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)
+{
+    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+    AOFF_RBTree_t *root = alc->mbc_root;
+
+    if (crr->rbt_node.parent || &crr->rbt_node == root) {
+	aoff_remove_mbc(allctr, carrier);
+    }
+    /*else already removed */
+}
+
+static void aoff_add_mbc(Allctr_t *allctr, Carrier_t *carrier)
+{
+    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+    AOFF_RBTree_t **root = &alc->mbc_root;
+
+    HARD_CHECK_TREE(NULL, 0, *root, 0);   
+
+    /* Link carrier in address order tree
+     */
+    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)
+{
+    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+    AOFF_RBTree_t **root = &alc->mbc_root;
+
+    ASSERT(allctr == ERTS_ALC_CARRIER_TO_ALLCTR(carrier));
+    HARD_CHECK_TREE(NULL, 0, *root, 0);
+
+    rbt_delete(root, &crr->rbt_node);
+    crr->rbt_node.parent = NULL;
+    crr->rbt_node.left = NULL;
+    crr->rbt_node.right = NULL;
+    crr->rbt_node.max_sz = crr->rbt_node.hdr.bhdr;
+
+    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 == ERTS_ALC_CARRIER_TO_ALLCTR(carrier));
+    ASSERT(crr->rbt_node.hdr.bhdr == (crr->root ? crr->root->max_sz : 0));
+    return crr->rbt_node.hdr.bhdr;
+}
 
 /*
  * info_options()
@@ -692,6 +882,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
 static struct {
     Eterm as;
     Eterm aoff;
+    Eterm aoffcaobf;
 #ifdef DEBUG
     Eterm end_of_atoms;
 #endif
@@ -720,6 +911,7 @@ init_atoms(void)
 #endif
     AM_INIT(as);
     AM_INIT(aoff);
+    AM_INIT(aoffcaobf);
 
 #ifdef DEBUG
     for (atom = (Eterm *) &am; atom < &am.end_of_atoms; atom++) {
@@ -749,6 +941,7 @@ info_options(Allctr_t *allctr,
 	     Uint **hpp,
 	     Uint *szp)
 {
+    AOFFAllctr_t* alc = (AOFFAllctr_t*) allctr;
     Eterm res = THE_NON_VALUE;
 
     if (print_to_p) {
@@ -756,7 +949,7 @@ info_options(Allctr_t *allctr,
 		   print_to_arg,
 		   "%sas: %s\n",
 		   prefix,
-		   "aoff");
+		   alc->bf_within_carrier ? "aoffcaobf" : "aoff");
     }
 
     if (hpp || szp) {
@@ -766,7 +959,8 @@ info_options(Allctr_t *allctr,
 		     __FILE__, __LINE__);;
 
 	res = NIL;
-	add_2tup(hpp, szp, &res, am.as, am.aoff);
+	add_2tup(hpp, szp, &res, am.as,
+		 alc->bf_within_carrier ? am.aoffcaobf : am.aoff);
     }
 
     return res;
@@ -780,19 +974,24 @@ info_options(Allctr_t *allctr,
  * to erts_aoffalc_test()                                                    *
 \*                                                                           */
 
-unsigned long
-erts_aoffalc_test(unsigned long op, unsigned long a1, unsigned long a2)
+UWord
+erts_aoffalc_test(UWord op, UWord a1, UWord a2)
 {
     switch (op) {
-    case 0x500:	return (unsigned long) 0; /* IS_AOBF */
-    case 0x501:	return (unsigned long) ((AOFFAllctr_t *) a1)->mbc_root;
-    case 0x502:	return (unsigned long) ((AOFF_RBTree_t *) a1)->parent;
-    case 0x503:	return (unsigned long) ((AOFF_RBTree_t *) a1)->left;
-    case 0x504:	return (unsigned long) ((AOFF_RBTree_t *) a1)->right;
-    case 0x506:	return (unsigned long) IS_BLACK((AOFF_RBTree_t *) a1);
-    case 0x508: return (unsigned long) 1; /* IS_AOFF */
-    case 0x509: return (unsigned long) ((AOFF_RBTree_t *) a1)->max_sz;
-    default:	ASSERT(0); return ~((unsigned long) 0);
+    case 0x501: {
+	AOFF_RBTree_t *node = ((AOFFAllctr_t *) a1)->mbc_root; 
+	Uint size = (Uint) a2;
+	node = node ? rbt_search(node, size) : NULL;
+	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;
+    case 0x504:	return (UWord) ((AOFF_RBTree_t *) a1)->right;
+    case 0x506:	return (UWord) IS_BLACK((AOFF_RBTree_t *) a1);
+    case 0x508: return (UWord) 0; /* IS_BF_ALGO */
+    case 0x509: return (UWord) ((AOFF_RBTree_t *) a1)->max_sz;
+    case 0x50a: return (UWord) ((AOFFAllctr_t *) a1)->bf_within_carrier;
+    default:	ASSERT(0); return ~((UWord) 0);
     }
 }
 
@@ -804,6 +1003,16 @@ erts_aoffalc_test(unsigned long op, unsigned long a1, unsigned long a2)
 
 #ifdef HARD_DEBUG
 
+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)
 
@@ -840,12 +1049,14 @@ static void print_tree(AOFF_RBTree_t*);
  */
 
 static AOFF_RBTree_t *
-check_tree(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;
     Sint curr_blacks;
     AOFF_RBTree_t *x;
+    Carrier_t* crr;
+    Uint depth, max_depth, node_cnt;
 
 #ifdef PRINT_TREE
     print_tree(root);
@@ -859,12 +1070,16 @@ check_tree(AOFF_RBTree_t* root, Uint size)
     ASSERT(!x->parent);
     curr_blacks = 1;
     blacks = -1;
+    depth = 1;
+    max_depth = 0;
+    node_cnt = 0;
 
     while (x) {
 	if (!IS_LEFT_VISITED(x)) {
 	    SET_LEFT_VISITED(x);
 	    if (x->left) {
 		x = x->left;
+		++depth;
 		if (IS_BLACK(x))
 		    curr_blacks++;
 		continue;
@@ -880,6 +1095,7 @@ check_tree(AOFF_RBTree_t* root, Uint size)
 	    SET_RIGHT_VISITED(x);
 	    if (x->right) {
 		x = x->right;
+		++depth;
 		if (IS_BLACK(x))
 		    curr_blacks++;
 		continue;
@@ -891,6 +1107,16 @@ check_tree(AOFF_RBTree_t* root, Uint size)
 	    }
 	}
 
+	++node_cnt;
+	if (depth > max_depth)
+	    max_depth = depth;
+
+	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));
@@ -901,13 +1127,13 @@ check_tree(AOFF_RBTree_t* root, Uint size)
 
 	if (x->left) {
 	    ASSERT(x->left->parent == x);
-	    ASSERT(x->left < x);
+	    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(x->right > x);
+	    ASSERT(cmp_blocks(bestfit, x->right, x) > 0);
 	    ASSERT(x->right->max_sz <= x->max_sz);	    
 	}
 	ASSERT(x->max_sz >= AOFF_BLK_SZ(x));
@@ -916,7 +1142,7 @@ check_tree(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 || x < res) {
+	    if (!res || cmp_blocks(bestfit, x, res) < 0) {
 		res = x;
 	    }
 	}
@@ -926,10 +1152,11 @@ check_tree(AOFF_RBTree_t* root, Uint size)
 	if (IS_BLACK(x))
 	    curr_blacks--;
 	x = x->parent;
-
+	--depth;
     }
-
+    ASSERT(depth == 0 || (!root && depth==1)); 
     ASSERT(curr_blacks == 0);
+    ASSERT((1 << (max_depth/2)) <= node_cnt);
 
     UNSET_LEFT_VISITED(root);
     UNSET_RIGHT_VISITED(root);
@@ -954,9 +1181,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);
     }
 }