1 files changed, 193 insertions, 106 deletions

diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index 05ba1f9891..73576c0189 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -20,7 +20,7 @@
 
 
 /*
- * Description:	An "address order first fit" allocator
+ * Description:	A family of "first fit" allocator strategies
  *              based on a Red-Black (binary search) Tree. The search,
  *              insert, and delete operations are all O(log n) operations
  *              on a Red-Black Tree.
@@ -40,6 +40,10 @@
  *              sorting order. Blocks within the same carrier are sorted
  *              wrt size instead of address. The 'max_sz' field is maintained
  *              in order to dismiss entire carriers with too small blocks. 
+ * Age Order:
+ *      	Carriers are ordered by creation time instead of address.
+ *      	Oldest carrier with a large enough free block is chosen.
+ *      	No age order supported for blocks.
  *
  * Authors: 	Rickard Green/Sverker Eriksson
  */
@@ -53,10 +57,12 @@
 #include "erl_ao_firstfit_alloc.h"
 
 #ifdef DEBUG
+# define IS_DEBUG 1
 #if 0
 #define HARD_DEBUG
 #endif
 #else
+# define IS_DEBUG 0
 #undef HARD_DEBUG
 #endif
 
@@ -92,18 +98,6 @@
 #define RBT_ASSERT(x)
 #endif
 
-
-/* Types... */
-typedef struct AOFF_RBTree_t_ AOFF_RBTree_t;
-
-struct AOFF_RBTree_t_ {
-    Block_t hdr;
-    AOFF_RBTree_t *parent;
-    AOFF_RBTree_t *left;
-    AOFF_RBTree_t *right;
-    Uint32 flags;
-    Uint32 max_sz;  /* of all blocks in this sub-tree */
-};
 #define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
 
 /* BF block nodes keeps list of all with equal size
@@ -121,6 +115,7 @@ 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 */
+    Sint64 birth_time;
     AOFF_RBTree_t* root;        /* Root of my block tree */
 };
 #define RBT_NODE_TO_MBC(PTR) ErtsContainerStruct((PTR), AOFF_Carrier_t, rbt_node)
@@ -136,12 +131,12 @@ struct AOFF_Carrier_t_ {
 */
 
 #ifdef HARD_DEBUG
-#  define HARD_CHECK_IS_MEMBER(ROOT,NODE) rbt_assert_is_member(ROOT,NODE)
-#  define HARD_CHECK_TREE(CRR,FLV,ROOT,SZ) check_tree(CRR, FLV, ROOT, SZ)
-static AOFF_RBTree_t * check_tree(Carrier_t* within_crr, enum AOFF_Flavor flavor, AOFF_RBTree_t* root, Uint);
+#  define HARD_CHECK_IS_MEMBER(ROOT,NODE) ASSERT(rbt_is_member(ROOT,NODE))
+#  define HARD_CHECK_TREE(CRR,ORDER,ROOT,SZ) check_tree(CRR, ORDER, ROOT, SZ)
+static AOFF_RBTree_t * check_tree(Carrier_t*, enum AOFFSortOrder, AOFF_RBTree_t*, Uint);
 #else
 #  define HARD_CHECK_IS_MEMBER(ROOT,NODE)
-#  define HARD_CHECK_TREE(CRR,FLV,ROOT,SZ)
+#  define HARD_CHECK_TREE(CRR,ORDER,ROOT,SZ)
 #endif
 
 
@@ -179,25 +174,65 @@ static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
     else ASSERT(new_max == old_max);
 }
 
-static ERTS_INLINE SWord cmp_blocks(enum AOFF_Flavor flavor,
+#ifdef ERTS_SMP
+/*
+ * Set possibly new larger 'max_sz' of node and propagate change toward root
+ */
+void erts_aoff_larger_max_size(AOFF_RBTree_t *node)
+{
+    AOFF_RBTree_t* x = node;
+    const Uint new_sz = node->hdr.bhdr;
+
+    ASSERT(!x->left  || x->left->max_sz  <= x->max_sz);
+    ASSERT(!x->right || x->right->max_sz <= x->max_sz);
+
+    while (new_sz > x->max_sz) {
+        x->max_sz = new_sz;
+        x = x->parent;
+        if (!x)
+            break;
+    }
+}
+#endif
+
+/* Compare nodes for both carrier and block trees */
+static ERTS_INLINE SWord cmp_blocks(enum AOFFSortOrder order,
 				    AOFF_RBTree_t* lhs, AOFF_RBTree_t* rhs)
 {
     ASSERT(lhs != rhs);
-    ASSERT(flavor == AOFF_AOFF || FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr));
-    if (flavor != AOFF_AOFF) {
-	SWord diff = (SWord)AOFF_BLK_SZ(lhs) - (SWord)AOFF_BLK_SZ(rhs);
-	if (diff || flavor == AOFF_BF) return diff;
+    if (order == FF_AGEFF) {
+	AOFF_Carrier_t* lc = RBT_NODE_TO_MBC(lhs);
+	AOFF_Carrier_t* rc = RBT_NODE_TO_MBC(rhs);
+	Sint64 diff = lc->birth_time - rc->birth_time;
+ #ifdef ARCH_64
+        if (diff)
+            return diff;
+ #else
+        if (diff < 0)
+            return -1;
+        else if (diff > 0)
+            return 1;
+ #endif
+    }
+    else {
+	ASSERT(order == FF_AOFF || FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr));
+	if (order != FF_AOFF) {
+	    SWord diff = (SWord)AOFF_BLK_SZ(lhs) - (SWord)AOFF_BLK_SZ(rhs);
+	    if (diff || order == FF_BF) return diff;
+	}
     }
     return (char*)lhs - (char*)rhs;
 }
 
-static ERTS_INLINE SWord cmp_cand_blk(enum AOFF_Flavor flavor,
+/* Compare candidate block. Only for block tree */
+static ERTS_INLINE SWord cmp_cand_blk(enum AOFFSortOrder order,
 				      Block_t* cand_blk, AOFF_RBTree_t* rhs)
 {
-    if (flavor != AOFF_AOFF) {
+    ASSERT(order != FF_AGEFF);
+    if (order != FF_AOFF) {
 	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 || flavor == AOFF_BF) return diff;
+	    if (diff || order == FF_BF) return diff;
 	}
     }
     return (char*)cand_blk - (char*)rhs;
@@ -218,11 +253,8 @@ 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(enum AOFF_Flavor flavor, AOFF_RBTree_t** root, AOFF_RBTree_t* blk);
+static void rbt_insert(enum AOFFSortOrder, 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 *, fmtfn_t *, void *, Uint **, Uint *);
 static void init_atoms(void);
@@ -230,10 +262,17 @@ static void init_atoms(void);
 
 static int atoms_initialized = 0;
 
+#ifndef ERTS_HAVE_OS_MONOTONIC_TIME_SUPPORT
+static erts_atomic64_t birth_time_counter;
+#endif
+
 void
 erts_aoffalc_init(void)
 {
     atoms_initialized = 0;
+#ifndef ERTS_HAVE_OS_MONOTONIC_TIME_SUPPORT
+    erts_atomic64_init_nob(&birth_time_counter, 0);
+#endif
 }
 
 Allctr_t *
@@ -254,11 +293,12 @@ erts_aoffalc_start(AOFFAllctr_t *alc,
 
     sys_memcpy((void *) alc, (void *) &zero.allctr, sizeof(AOFFAllctr_t));
 
-    alc->flavor                         = aoffinit->flavor;
+    alc->blk_order                      = aoffinit->blk_order;
+    alc->crr_order                      = aoffinit->crr_order;
     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 = (aoffinit->flavor == AOFF_BF ?
+    allctr->min_block_size = (aoffinit->blk_order == FF_BF ?
 			      sizeof(AOFF_RBTreeList_t):sizeof(AOFF_RBTree_t));
 
     allctr->vsn_str			= ERTS_ALC_AOFF_ALLOC_VSN_STR;
@@ -487,9 +527,9 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *blk)
     AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(&del->hdr);
 
     ASSERT(crr->rbt_node.hdr.bhdr == crr->root->max_sz);
-    HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, 0);
+    HARD_CHECK_TREE(&crr->crr, alc->blk_order, crr->root, 0);
 
-    if (alc->flavor == AOFF_BF) {
+    if (alc->blk_order == FF_BF) {
 	ASSERT(del->flags & IS_BF_FLG);
 	if (IS_LIST_ELEM(del)) {
 	    /* Remove from list */
@@ -510,14 +550,14 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *blk)
 	    
 	    replace(&crr->root, (AOFF_RBTree_t*)del, LIST_NEXT(del));
 	    
-	    HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, 0);
+	    HARD_CHECK_TREE(&crr->crr, alc->blk_order, crr->root, 0);
 	    return;
 	}
     }
 
     rbt_delete(&crr->root, (AOFF_RBTree_t*)del);
 
-    HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, 0);
+    HARD_CHECK_TREE(&crr->crr, alc->blk_order, crr->root, 0);
 
     /* Update the carrier tree with a potentially new (lower) max_sz
      */    
@@ -715,32 +755,33 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block)
 
     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_TREE(&blk_crr->crr, alc->flavor, blk_crr->root, 0);
+    HARD_CHECK_TREE(&blk_crr->crr, alc->blk_order, blk_crr->root, 0);
 
-    rbt_insert(alc->flavor, &blk_crr->root, blk);
+    rbt_insert(alc->blk_order, &blk_crr->root, blk);
 
-    /* Update the carrier tree with a potentially new (larger) max_sz
-    */
+    /*
+     * Update carrier tree with a potentially 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;
-	}
+        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->flavor, blk_crr->root, 0);
+    HARD_CHECK_TREE(NULL, alc->crr_order, alc->mbc_root, 0);
 }
 
 static void
-rbt_insert(enum AOFF_Flavor flavor, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
+rbt_insert(enum AOFFSortOrder order, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
 {
     Uint blk_sz = AOFF_BLK_SZ(blk);
 
 #ifdef DEBUG
-    blk->flags  = (flavor == AOFF_BF) ? IS_BF_FLG : 0; 
+    blk->flags  = (order == FF_BF) ? IS_BF_FLG : 0;
 #else
     blk->flags  = 0; 
 #endif
@@ -760,7 +801,7 @@ rbt_insert(enum AOFF_Flavor flavor, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
 	    if (x->max_sz < blk_sz) {
 		x->max_sz = blk_sz;
 	    }
-	    diff = cmp_blocks(flavor, blk, x);
+	    diff = cmp_blocks(order, blk, x);
 	    if (diff < 0) {
 		if (!x->left) {
 		    blk->parent = x;
@@ -778,7 +819,7 @@ rbt_insert(enum AOFF_Flavor flavor, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
 		x = x->right;
 	    }
 	    else {
-		ASSERT(flavor == AOFF_BF);
+		ASSERT(order == FF_BF);
 		ASSERT(blk->flags & IS_BF_FLG);			    
 		ASSERT(x->flags & IS_BF_FLG);			    
 		SET_LIST_ELEM(blk);
@@ -798,7 +839,7 @@ rbt_insert(enum AOFF_Flavor flavor, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
 	if (IS_RED(blk->parent))
 	    tree_insert_fixup(root, blk);
     }
-    if (flavor == AOFF_BF) {
+    if (order == FF_BF) {
 	SET_TREE_NODE(blk);
 	LIST_NEXT(blk) = NULL;
     }
@@ -826,6 +867,18 @@ rbt_search(AOFF_RBTree_t* root, Uint size)
     }
 }
 
+#ifdef ERTS_SMP
+Carrier_t* aoff_lookup_pooled_mbc(Allctr_t* allctr, Uint size)
+{
+    AOFF_RBTree_t* node;
+
+    if (!allctr->cpool.pooled_tree)
+	return NULL;
+    node = rbt_search(allctr->cpool.pooled_tree, size);
+    return node ? ErtsContainerStruct(node, Carrier_t, cpool.pooled) : NULL;
+}
+#endif
+
 static Block_t *
 aoff_get_free_block(Allctr_t *allctr, Uint size,
 		    Block_t *cand_blk, Uint cand_size)
@@ -850,7 +903,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
     /* Get block within carrier tree
      */
 #ifdef HARD_DEBUG
-    dbg_blk = HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, size);
+    dbg_blk = HARD_CHECK_TREE(&crr->crr, alc->blk_order, crr->root, size);
 #endif
 
     blk = rbt_search(crr->root, size);
@@ -863,7 +916,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
     if (!blk)
 	return NULL;
 
-    if (cand_blk && cmp_cand_blk(alc->flavor, cand_blk, blk) < 0) {
+    if (cand_blk && cmp_cand_blk(alc->blk_order, cand_blk, blk) < 0) {
 	return NULL; /* cand_blk was better */
     }
 
@@ -872,23 +925,32 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
     return (Block_t *) blk;
 }
 
+static ERTS_INLINE Sint64 get_birth_time(void)
+{
+#ifdef ERTS_HAVE_OS_MONOTONIC_TIME_SUPPORT
+    return (Sint64) erts_os_monotonic_time();
+#else
+    return (Sint64) erts_atomic64_inc_read_nob(&birth_time_counter);
+#endif
+}
+
 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);
+    HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
 
-    /* Link carrier in address order tree
-     */
     crr->rbt_node.hdr.bhdr = 0;
-    rbt_insert(AOFF_AOFF, root, &crr->rbt_node);
+    if (alc->crr_order == FF_AGEFF || IS_DEBUG)
+	crr->birth_time = get_birth_time();
+    rbt_insert(alc->crr_order, root, &crr->rbt_node);
 
     /* aoff_link_free_block will add free block later */
     crr->root = NULL;
 
-    HARD_CHECK_TREE(NULL, 0, *root, 0);
+    HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
 }
 
 #define IS_CRR_IN_TREE(CRR,ROOT) \
@@ -911,27 +973,40 @@ static void aoff_add_mbc(Allctr_t *allctr, Carrier_t *carrier)
     AOFF_RBTree_t **root = &alc->mbc_root;
 
     ASSERT(!IS_CRR_IN_TREE(crr, *root));
-    HARD_CHECK_TREE(NULL, 0, *root, 0);   
+    HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);   
+
+    rbt_insert(alc->crr_order, root, &crr->rbt_node);
+
+    HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
+}
+
+#ifdef ERTS_SMP
+void aoff_add_pooled_mbc(Allctr_t *allctr, Carrier_t *crr)
+{
+    AOFF_RBTree_t **root = &allctr->cpool.pooled_tree;
+
+    ASSERT(allctr == crr->cpool.orig_allctr);
+    HARD_CHECK_TREE(NULL, 0, *root, 0);
 
     /* Link carrier in address order tree
      */
-    rbt_insert(AOFF_AOFF, root, &crr->rbt_node);
+    rbt_insert(FF_AOFF, root, &crr->cpool.pooled);
 
     HARD_CHECK_TREE(NULL, 0, *root, 0);
 }
+#endif
 
 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;
+    AOFF_RBTree_t **root = &((AOFFAllctr_t*)allctr)->mbc_root;
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*)carrier;
 
     ASSERT(allctr == ERTS_ALC_CARRIER_TO_ALLCTR(carrier));
 
     if (!IS_CRR_IN_TREE(crr,*root))
-        return;
+	return;
 
-    HARD_CHECK_TREE(NULL, 0, *root, 0);
+    HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
 
     rbt_delete(root, &crr->rbt_node);
     crr->rbt_node.parent = NULL;
@@ -939,8 +1014,28 @@ static void aoff_remove_mbc(Allctr_t *allctr, Carrier_t *carrier)
     crr->rbt_node.right = NULL;
     crr->rbt_node.max_sz = crr->rbt_node.hdr.bhdr;
 
-    HARD_CHECK_TREE(NULL, 0, *root, 0);
+    HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
+}
+
+#ifdef ERTS_SMP
+void aoff_remove_pooled_mbc(Allctr_t *allctr, Carrier_t *crr)
+{
+    ASSERT(allctr == crr->cpool.orig_allctr);
+
+    HARD_CHECK_TREE(NULL, 0, allctr->cpool.pooled_tree, 0);
+
+    rbt_delete(&allctr->cpool.pooled_tree, &crr->cpool.pooled);
+#ifdef DEBUG
+    crr->cpool.pooled.parent = NULL;
+    crr->cpool.pooled.left = NULL;
+    crr->cpool.pooled.right = NULL;
+    crr->cpool.pooled.max_sz = 0;
+#endif
+    HARD_CHECK_TREE(NULL, 0, allctr->cpool.pooled_tree, 0);
+
 }
+#endif
+
 
 static UWord aoff_largest_fblk_in_mbc(Allctr_t* allctr, Carrier_t* carrier)
 {
@@ -955,17 +1050,17 @@ static UWord aoff_largest_fblk_in_mbc(Allctr_t* allctr, Carrier_t* carrier)
  * info_options()
  */
 
+static const char* flavor_str[2][3] = {
+    {"ageffcaoff", "ageffcaobf", "ageffcbf"},
+    {      "aoff",  "aoffcaobf",  "aoffcbf"}
+};
+static Eterm flavor_atoms[2][3];
+
 static struct {
     Eterm as;
-    Eterm aoff;
-    Eterm aoffcaobf;
-    Eterm aoffcbf;
-#ifdef DEBUG
-    Eterm end_of_atoms;
-#endif
 } am;
 
-static void ERTS_INLINE atom_init(Eterm *atom, char *name)
+static void ERTS_INLINE atom_init(Eterm *atom, const char *name)
 {
     *atom = am_atom_put(name, strlen(name));
 }
@@ -974,28 +1069,16 @@ static void ERTS_INLINE atom_init(Eterm *atom, char *name)
 static void
 init_atoms(void)
 {
-#ifdef DEBUG
-    Eterm *atom;
-#endif
+    int i, j;
 
     if (atoms_initialized)
 	return;
 
-#ifdef DEBUG
-    for (atom = (Eterm *) &am; atom <= &am.end_of_atoms; atom++) {
-	*atom = THE_NON_VALUE;
-    }
-#endif
     AM_INIT(as);
-    AM_INIT(aoff);
-    AM_INIT(aoffcaobf);
-    AM_INIT(aoffcbf);
 
-#ifdef DEBUG
-    for (atom = (Eterm *) &am; atom < &am.end_of_atoms; atom++) {
-	ASSERT(*atom != THE_NON_VALUE);
-    }
-#endif
+    for (i = 0; i < 2; i++)
+        for (j = 0; j < 3; j++)
+            atom_init(&flavor_atoms[i][j], flavor_str[i][j]);
 
     atoms_initialized = 1;
 }
@@ -1021,15 +1104,16 @@ info_options(Allctr_t *allctr,
 {
     AOFFAllctr_t* alc = (AOFFAllctr_t*) allctr;
     Eterm res = THE_NON_VALUE;
-    const char* flavor_str[3] = {"aoff", "aoffcaobf", "aoffcbf"};
-    Eterm flavor_atom[3] = {am.aoff, am.aoffcaobf, am.aoffcbf};
+
+    ASSERT(alc->crr_order >= 0 && alc->crr_order <= 1);
+    ASSERT(alc->blk_order >= 1 && alc->blk_order <= 3);
 
     if (print_to_p) {
 	erts_print(*print_to_p,
 		   print_to_arg,
 		   "%sas: %s\n",
 		   prefix,
-		   flavor_str[alc->flavor]);
+		   flavor_str[alc->crr_order][alc->blk_order-1]);
     }
 
     if (hpp || szp) {
@@ -1039,7 +1123,8 @@ info_options(Allctr_t *allctr,
 		     __FILE__, __LINE__);;
 
 	res = NIL;
-	add_2tup(hpp, szp, &res, am.as, flavor_atom[alc->flavor]);
+	add_2tup(hpp, szp, &res, am.as,
+                 flavor_atoms[alc->crr_order][alc->blk_order-1]);
     }
 
     return res;
@@ -1057,7 +1142,7 @@ UWord
 erts_aoffalc_test(UWord op, UWord a1, UWord a2)
 {
     switch (op) {
-    case 0x500: return (UWord) ((AOFFAllctr_t *) a1)->flavor == AOFF_AOBF;
+    case 0x500: return (UWord) ((AOFFAllctr_t *) a1)->blk_order == FF_AOBF;
     case 0x501: {
 	AOFF_RBTree_t *node = ((AOFFAllctr_t *) a1)->mbc_root; 
 	Uint size = (Uint) a2;
@@ -1072,7 +1157,7 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2)
     case 0x507:	return (UWord) IS_TREE_NODE((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)->flavor == AOFF_BF;
+    case 0x50a: return (UWord) ((AOFFAllctr_t *) a1)->blk_order == FF_BF;
     case 0x50b:	return (UWord) LIST_PREV(a1);
     default:	ASSERT(0); return ~((UWord) 0);
     }
@@ -1085,12 +1170,13 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2)
 
 
 #ifdef HARD_DEBUG
-
-static int rbt_assert_is_member(AOFF_RBTree_t* root, AOFF_RBTree_t* node)
+static int rbt_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);
+        if (!node->parent || (node->parent->left != node &&
+                              node->parent->right != node)) {
+            return 0;
+        }
 	node = node->parent;
     }    
     return 1;
@@ -1132,7 +1218,7 @@ static void print_tree(AOFF_RBTree_t*);
  */
 
 static AOFF_RBTree_t *
-check_tree(Carrier_t* within_crr, enum AOFF_Flavor flavor, AOFF_RBTree_t* root, Uint size)
+check_tree(Carrier_t* within_crr, enum AOFFSortOrder order, AOFF_RBTree_t* root, Uint size)
 {
     AOFF_RBTree_t *res = NULL;
     Sint blacks;
@@ -1144,7 +1230,8 @@ check_tree(Carrier_t* within_crr, enum AOFF_Flavor flavor, AOFF_RBTree_t* root,
 #ifdef PRINT_TREE
     print_tree(root);
 #endif
-    ASSERT(within_crr || flavor == AOFF_AOFF);
+    ASSERT((within_crr && order >= FF_AOFF) ||
+           (!within_crr && order <= FF_AOFF));
 
     if (!root)
 	return res;
@@ -1202,7 +1289,7 @@ check_tree(Carrier_t* within_crr, enum AOFF_Flavor flavor, AOFF_RBTree_t* root,
 	    ASSERT(((char*)x + AOFF_BLK_SZ(x)) <= ((char*)crr + CARRIER_SZ(crr)));
 
 	}
-	if (flavor == AOFF_BF) {
+	if (order == FF_BF) {
 	    AOFF_RBTree_t* y = x;
 	    AOFF_RBTree_t* nxt = LIST_NEXT(y);
 	    ASSERT(IS_TREE_NODE(x));
@@ -1225,13 +1312,13 @@ check_tree(Carrier_t* within_crr, enum AOFF_Flavor flavor, AOFF_RBTree_t* root,
 
 	if (x->left) {
 	    ASSERT(x->left->parent == x);
-	    ASSERT(cmp_blocks(flavor, x->left, x) < 0);
+	    ASSERT(cmp_blocks(order, x->left, x) < 0);
 	    ASSERT(x->left->max_sz <= x->max_sz);	    
 	}
 
 	if (x->right) {
 	    ASSERT(x->right->parent == x);
-	    ASSERT(cmp_blocks(flavor, x->right, x) > 0);
+	    ASSERT(cmp_blocks(order, x->right, x) > 0);
 	    ASSERT(x->right->max_sz <= x->max_sz);	    
 	}
 	ASSERT(x->max_sz >= AOFF_BLK_SZ(x));
@@ -1240,7 +1327,7 @@ check_tree(Carrier_t* within_crr, enum AOFF_Flavor flavor, AOFF_RBTree_t* root,
 	       || x->max_sz == (x->right ? x->right->max_sz : 0));
 
 	if (size && AOFF_BLK_SZ(x) >= size) {
-	    if (!res || cmp_blocks(flavor, x, res) < 0) {
+	    if (!res || cmp_blocks(order, x, res) < 0) {
 		res = x;
 	    }
 	}