erts: Add new allocator strategy aoffcbf

with better performance than aoffcaobf as we don't have to rearrange
the search tree when there are blocks of equal size.

8 files changed, 220 insertions, 110 deletions

diff --git a/erts/doc/src/erts_alloc.xml b/erts/doc/src/erts_alloc.xml
index 2ffb55c6ab..5e008493b9 100644
--- a/erts/doc/src/erts_alloc.xml
+++ b/erts/doc/src/erts_alloc.xml
@@ -170,6 +170,15 @@
           used. The time complexity is proportional to log N, where
           N is the number of free blocks.</p>
       </item>
+      <tag>Address order first fit carrier best fit</tag>
+      <item>
+        <p>Strategy: Find the <em>carrier</em> with the lowest address that
+	can satisfy the requested block size, then find a block within
+	that carrier using the "best fit" strategy.</p>
+        <p>Implementation: Balanced binary search trees are
+          used. The time complexity is proportional to log N, where
+          N is the number of free blocks.</p>
+      </item>
       <tag>Address order first fit carrier address order best fit</tag>
       <item>
         <p>Strategy: Find the <em>carrier</em> with the lowest address that
@@ -330,7 +339,7 @@
 	fetched it will function as an ordinary carrier. This feature has
 	special requirements on the
 	<seealso marker="#M_as">allocation strategy</seealso> used. Currently
-	only the <c>aoff</c> and the <c>aoffcaobf</c> strategies support
+	only the strategies <c>aoff</c>, <c>aoffcbf</c> and <c>aoffcaobf</c> support
 	abandoned carriers. This feature also requires
 	<seealso marker="#M_t">multiple thread specific instances</seealso>
 	to be enabled. When enabling this feature, multiple thread specific
@@ -340,10 +349,11 @@
 	allocators based on the <c>alloc_util</c> framework with the
 	exception of <c>temp_alloc</c> (which would be pointless).
       </item>
-      <tag><marker id="M_as"><c><![CDATA[+M<S>as bf|aobf|aoff|aoffcaobf|gf|af]]></c></marker></tag>
+      <tag><marker id="M_as"><c><![CDATA[+M<S>as bf|aobf|aoff|aoffcbf|aoffcaobf|gf|af]]></c></marker></tag>
       <item>
        Allocation strategy. Valid strategies are <c>bf</c> (best fit),
       <c>aobf</c> (address order best fit), <c>aoff</c> (address order first fit),
+      <c>aoffcbf</c> (address order first fit carrier best fit),
       <c>aoffcaobf</c> (address order first fit carrier address order best fit),
       <c>gf</c> (good fit), and <c>af</c> (a fit). See 
       <seealso marker="#strategy">the description of allocation strategies</seealso> in "the <c>alloc_util</c> framework" section.</item>
diff --git a/erts/emulator/beam/erl_alloc.c b/erts/emulator/beam/erl_alloc.c
index a547191d6d..7b77bcca58 100644
--- a/erts/emulator/beam/erl_alloc.c
+++ b/erts/emulator/beam/erl_alloc.c
@@ -245,7 +245,7 @@ set_default_acul(struct au_init *ip, int acul)
 {
     ip->thr_spec = 1;
     ip->atype = AOFIRSTFIT;
-    ip->init.aoff.bf_within_carrier = 1;
+    ip->init.aoff.flavor = AOFF_AOBF;
     ip->init.util.acul = acul;
 }
 
@@ -558,7 +558,7 @@ static ERTS_INLINE int
 strategy_support_carrier_migration(struct au_init *auip)
 {
     /*
-     * Currently only aoff and aoffcaobf support carrier
+     * Currently only aoff, aoffcbf and aoffcaobf support carrier
      * migration, i.e, type AOFIRSTFIT.
      */
     return auip->atype == AOFIRSTFIT;
@@ -583,7 +583,7 @@ ensure_carrier_migration_support(struct au_init *auip)
     if (!strategy_support_carrier_migration(auip)) {
 	/* Default to aoffcaobf */
 	auip->atype = AOFIRSTFIT;
-	auip->init.aoff.bf_within_carrier = 1;
+	auip->init.aoff.flavor = AOFF_AOBF;
     }
 }
 
@@ -1284,11 +1284,15 @@ handle_au_arg(struct au_init *auip,
 	    }
 	    else if (strcmp("aoff", alg) == 0) {
 		auip->atype = AOFIRSTFIT;
-		auip->init.aoff.bf_within_carrier = 0;
+		auip->init.aoff.flavor = AOFF_AOFF;
+	    }
+	    else if (strcmp("aoffcbf", alg) == 0) {
+		auip->atype = AOFIRSTFIT;
+		auip->init.aoff.flavor = AOFF_BF;
 	    }
 	    else if (strcmp("aoffcaobf", alg) == 0) {
 		auip->atype = AOFIRSTFIT;
-		auip->init.aoff.bf_within_carrier = 1;
+		auip->init.aoff.flavor = AOFF_AOBF;
 	    }
 	    else {
 		bad_value(param, sub_param + 1, alg);
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index f73ac2eb6e..4e6c8b317e 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -34,10 +34,11 @@
  *              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:
+ * Bestfit within carrier:
  *              The only difference for "bestfit within carrier" is the tree
  *              sorting order. Blocks within the same carrier are sorted
- *              wrt size instead of address. 
+ *              wrt size instead of address. The 'max_sz' field is maintained
+ *              in order to dismiss entire carriers with too small blocks. 
  *
  * Authors: 	Rickard Green/Sverker Eriksson
  */
@@ -67,6 +68,15 @@
 #  define LEFT_VISITED_FLG	(((Uint) 1) << 2)
 #  define RIGHT_VISITED_FLG	(((Uint) 1) << 3)
 #endif
+#ifdef DEBUG
+#  define IS_BF_FLG	        (((Uint) 1) << 4)
+#endif
+
+#define IS_TREE_NODE(N)		(((AOFF_RBTree_t *) (N))->flags & TREE_NODE_FLG)
+#define IS_LIST_ELEM(N)		(!IS_TREE_NODE(((AOFF_RBTree_t *) (N))))
+
+#define SET_TREE_NODE(N)	(((AOFF_RBTree_t *) (N))->flags |= TREE_NODE_FLG)
+#define SET_LIST_ELEM(N)	(((AOFF_RBTree_t *) (N))->flags &= ~TREE_NODE_FLG)
 
 #define IS_RED(N)		(((AOFF_RBTree_t *) (N)) \
 				 && ((AOFF_RBTree_t *) (N))->flags & RED_FLG)
@@ -98,6 +108,16 @@ struct AOFF_RBTree_t_ {
 };
 #define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
 
+/* BF block nodes keeps list of all with equal size
+ */
+typedef struct {
+    AOFF_RBTree_t t;
+    AOFF_RBTree_t *next;
+}AOFF_RBTreeList_t;
+
+#define LIST_NEXT(N) (((AOFF_RBTreeList_t*) (N))->next)
+#define LIST_PREV(N) (((AOFF_RBTreeList_t*) (N))->t.parent)
+
 typedef struct AOFF_Carrier_t_ AOFF_Carrier_t;
 
 struct AOFF_Carrier_t_ {
@@ -119,11 +139,11 @@ 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,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);
+#  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);
 #else
 #  define HARD_CHECK_IS_MEMBER(ROOT,NODE)
-#  define HARD_CHECK_TREE(CRR,BF,ROOT,SZ)
+#  define HARD_CHECK_TREE(CRR,FLV,ROOT,SZ)
 #endif
 
 
@@ -161,25 +181,25 @@ 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,
+static ERTS_INLINE SWord cmp_blocks(enum AOFF_Flavor flavor,
 				    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) {
+    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) return diff;
+	if (diff || flavor == AOFF_BF) return diff;
     }
     return (char*)lhs - (char*)rhs;
 }
 
-static ERTS_INLINE SWord cmp_cand_blk(int bestfit,
+static ERTS_INLINE SWord cmp_cand_blk(enum AOFF_Flavor flavor,
 				      Block_t* cand_blk, AOFF_RBTree_t* rhs)
 {
-    if (bestfit) {
+    if (flavor != AOFF_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) return diff;
+	    if (diff || flavor == AOFF_BF) return diff;
 	}
     }
     return (char*)cand_blk - (char*)rhs;
@@ -198,7 +218,7 @@ 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 void rbt_insert(enum AOFF_Flavor flavor, 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);
@@ -234,21 +254,21 @@ erts_aoffalc_start(AOFFAllctr_t *alc,
 
     sys_memcpy((void *) alc, (void *) &zero.allctr, sizeof(AOFFAllctr_t));
 
-    alc->bf_within_carrier              = aoffinit->bf_within_carrier;
+    alc->flavor                         = aoffinit->flavor;
     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->min_block_size = (aoffinit->flavor == AOFF_BF ?
+			      sizeof(AOFF_RBTreeList_t):sizeof(AOFF_RBTree_t));
 
-    allctr->vsn_str			= aoffinit->bf_within_carrier ?
-	ERTS_ALC_AOFF_CBF_ALLOC_VSN_STR : ERTS_ALC_AOFF_ALLOC_VSN_STR;
+    allctr->vsn_str			= ERTS_ALC_AOFF_ALLOC_VSN_STR;
 
 
     /* Callback functions */
 
     allctr->get_free_block		= aoff_get_free_block;
     allctr->link_free_block		= aoff_link_free_block;
-    allctr->unlink_free_block	        = aoff_unlink_free_block;
+    allctr->unlink_free_block           = aoff_unlink_free_block;
     allctr->info_options		= info_options;
 
     allctr->get_next_mbc_size		= NULL;
@@ -359,9 +379,7 @@ replace(AOFF_RBTree_t **root, AOFF_RBTree_t *x, AOFF_RBTree_t *y)
     y->parent	= x->parent;
     y->right	= x->right;
     y->left	= x->left;
-
-    y->max_sz = x->max_sz;
-    lower_max_size(y, NULL);
+    y->max_sz   = x->max_sz;
 }
 
 static void
@@ -458,23 +476,47 @@ tree_insert_fixup(AOFF_RBTree_t** root, AOFF_RBTree_t *blk)
 }
 
 static void
-aoff_unlink_free_block(Allctr_t *allctr, Block_t *del)
+aoff_unlink_free_block(Allctr_t *allctr, Block_t *blk)
 {
-#ifdef HARD_DEBUG
     AOFFAllctr_t* alc = (AOFFAllctr_t*)allctr;
-#endif
-    AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(del);
+    AOFF_RBTree_t* del = (AOFF_RBTree_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_IS_MEMBER(alc->mbc_root, &crr->rbt_node);
-    HARD_CHECK_TREE(&crr->crr, alc->bf_within_carrier, crr->root, 0);
+    HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, 0);
+
+    if (alc->flavor == AOFF_BF) {
+	ASSERT(del->flags & IS_BF_FLG);
+	if (IS_LIST_ELEM(del)) {
+	    /* Remove from list */
+	    ASSERT(LIST_PREV(del));
+	    ASSERT(LIST_PREV(del)->flags & IS_BF_FLG);
+	    LIST_NEXT(LIST_PREV(del)) = LIST_NEXT(del);
+	    if (LIST_NEXT(del)) {
+		ASSERT(LIST_NEXT(del)->flags & IS_BF_FLG);
+		LIST_PREV(LIST_NEXT(del)) = LIST_PREV(del);
+	    }
+	    return;
+	}
+	else if (LIST_NEXT(del)) {
+	    /* Replace tree node by next element in list... */
+	    
+	    ASSERT(AOFF_BLK_SZ(LIST_NEXT(del)) == AOFF_BLK_SZ(del));
+	    ASSERT(IS_LIST_ELEM(LIST_NEXT(del)));
+	    
+	    replace(&crr->root, (AOFF_RBTree_t*)del, LIST_NEXT(del));
+	    
+	    HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, 0);
+	    return;
+	}
+    }
 
     rbt_delete(&crr->root, (AOFF_RBTree_t*)del);
 
-    HARD_CHECK_TREE(&crr->crr, alc->bf_within_carrier, crr->root, 0);
+    HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, 0);
 
-   /* Update the carrier tree with a potentially new (lower) max_sz
-    */    
+    /* 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;
@@ -488,6 +530,7 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *del)
     lower_max_size(&crr->rbt_node, NULL);
 }
 
+
 static void
 rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del)
 {
@@ -542,7 +585,9 @@ rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del)
     }
     if (y != z) {
 	/* We spliced out the successor of z; replace z by the successor */
+	ASSERT(z != &null_x);
 	replace(root, z, y);
+	lower_max_size(y, NULL);
     }
 
     if (spliced_is_black) {
@@ -666,12 +711,11 @@ 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_IS_MEMBER(alc->mbc_root, &blk_crr->rbt_node);
-    HARD_CHECK_TREE(&blk_crr->crr, alc->bf_within_carrier, blk_crr->root, 0);
+    HARD_CHECK_TREE(&blk_crr->crr, alc->flavor, blk_crr->root, 0);
 
-    rbt_insert(alc->bf_within_carrier, &blk_crr->root, blk);
+    rbt_insert(alc->flavor, &blk_crr->root, blk);
 
-    /* Update the carrier tree with a potential new (larger) max_sz
+    /* Update the carrier tree with a potentially new (larger) max_sz
     */
     crr_node = &blk_crr->rbt_node;
     if (blk_sz > crr_node->hdr.bhdr) {
@@ -683,15 +727,19 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block)
 	    if (!crr_node) break;
 	}
     }
-    HARD_CHECK_TREE(&blk_crr->crr, alc->bf_within_carrier, blk_crr->root, 0);
+    HARD_CHECK_TREE(&blk_crr->crr, alc->flavor, blk_crr->root, 0);
 }
 
 static void
-rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
+rbt_insert(enum AOFF_Flavor flavor, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
 {
     Uint blk_sz = AOFF_BLK_SZ(blk);
 
-    blk->flags	= 0;
+#ifdef DEBUG
+    blk->flags  = (flavor == AOFF_BF) ? IS_BF_FLG : 0; 
+#else
+    blk->flags  = 0; 
+#endif
     blk->left	= NULL;
     blk->right	= NULL;
     blk->max_sz = blk_sz;
@@ -704,10 +752,12 @@ rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
     else {
 	AOFF_RBTree_t *x = *root;
 	while (1) {
+	    SWord diff; 
 	    if (x->max_sz < blk_sz) {
 		x->max_sz = blk_sz;
 	    }
-	    if (cmp_blocks(bestfit, blk, x) < 0) {
+	    diff = cmp_blocks(flavor, blk, x);
+	    if (diff < 0) {
 		if (!x->left) {
 		    blk->parent = x;
 		    x->left = blk;
@@ -715,7 +765,7 @@ rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
 		}
 		x = x->left;
 	    }
-	    else {
+	    else if (diff > 0) {
 		if (!x->right) {
 		    blk->parent = x;
 		    x->right = blk;
@@ -723,6 +773,18 @@ rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
 		}
 		x = x->right;
 	    }
+	    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 */
@@ -732,6 +794,10 @@ rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
 	if (IS_RED(blk->parent))
 	    tree_insert_fixup(root, blk);
     }
+    if (flavor == AOFF_BF) {
+	SET_TREE_NODE(blk);
+	LIST_NEXT(blk) = NULL;
+    }
 }
 
 static AOFF_RBTree_t*
@@ -780,7 +846,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->bf_within_carrier, crr->root, size);
+    dbg_blk = HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, size);
 #endif
 
     blk = rbt_search(crr->root, size);
@@ -793,7 +859,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
     if (!blk)
 	return NULL;
 
-    if (cand_blk && cmp_cand_blk(alc->bf_within_carrier, cand_blk, blk) < 0) {
+    if (cand_blk && cmp_cand_blk(alc->flavor, cand_blk, blk) < 0) {
 	return NULL; /* cand_blk was better */
     }
 
@@ -813,7 +879,7 @@ static void aoff_creating_mbc(Allctr_t *allctr, Carrier_t *carrier)
     /* Link carrier in address order tree
      */
     crr->rbt_node.hdr.bhdr = 0;
-    rbt_insert(0, root, &crr->rbt_node);
+    rbt_insert(AOFF_AOFF, root, &crr->rbt_node);
 
     /* aoff_link_free_block will add free block later */
     crr->root = NULL;
@@ -843,7 +909,7 @@ static void aoff_add_mbc(Allctr_t *allctr, Carrier_t *carrier)
 
     /* Link carrier in address order tree
      */
-    rbt_insert(0, root, &crr->rbt_node);
+    rbt_insert(AOFF_AOFF, root, &crr->rbt_node);
 
     HARD_CHECK_TREE(NULL, 0, *root, 0);
 }
@@ -883,6 +949,7 @@ static struct {
     Eterm as;
     Eterm aoff;
     Eterm aoffcaobf;
+    Eterm aoffcbf;
 #ifdef DEBUG
     Eterm end_of_atoms;
 #endif
@@ -912,6 +979,7 @@ init_atoms(void)
     AM_INIT(as);
     AM_INIT(aoff);
     AM_INIT(aoffcaobf);
+    AM_INIT(aoffcbf);
 
 #ifdef DEBUG
     for (atom = (Eterm *) &am; atom < &am.end_of_atoms; atom++) {
@@ -943,13 +1011,15 @@ 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};
 
     if (print_to_p) {
 	erts_print(*print_to_p,
 		   print_to_arg,
 		   "%sas: %s\n",
 		   prefix,
-		   alc->bf_within_carrier ? "aoffcaobf" : "aoff");
+		   flavor_str[alc->flavor]);
     }
 
     if (hpp || szp) {
@@ -959,8 +1029,7 @@ info_options(Allctr_t *allctr,
 		     __FILE__, __LINE__);;
 
 	res = NIL;
-	add_2tup(hpp, szp, &res, am.as,
-		 alc->bf_within_carrier ? am.aoffcaobf : am.aoff);
+	add_2tup(hpp, szp, &res, am.as, flavor_atom[alc->flavor]);
     }
 
     return res;
@@ -978,6 +1047,7 @@ UWord
 erts_aoffalc_test(UWord op, UWord a1, UWord a2)
 {
     switch (op) {
+    case 0x500: return (UWord) ((AOFFAllctr_t *) a1)->flavor == AOFF_AOBF;
     case 0x501: {
 	AOFF_RBTree_t *node = ((AOFFAllctr_t *) a1)->mbc_root; 
 	Uint size = (Uint) a2;
@@ -987,10 +1057,13 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2)
     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 0x505:	return (UWord) LIST_NEXT(a1);
     case 0x506:	return (UWord) IS_BLACK((AOFF_RBTree_t *) a1);
+    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)->bf_within_carrier;
+    case 0x50a: return (UWord) ((AOFFAllctr_t *) a1)->flavor == AOFF_BF;
+    case 0x50b:	return (UWord) LIST_PREV(a1);
     default:	ASSERT(0); return ~((UWord) 0);
     }
 }
@@ -1049,7 +1122,7 @@ static void print_tree(AOFF_RBTree_t*);
  */
 
 static AOFF_RBTree_t *
-check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint size)
+check_tree(Carrier_t* within_crr, enum AOFF_Flavor flavor, AOFF_RBTree_t* root, Uint size)
 {
     AOFF_RBTree_t *res = NULL;
     Sint blacks;
@@ -1061,6 +1134,7 @@ check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint size)
 #ifdef PRINT_TREE
     print_tree(root);
 #endif
+    ASSERT(within_crr || flavor == AOFF_AOFF);
 
     if (!root)
 	return res;
@@ -1116,6 +1190,20 @@ check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint size)
 	    ASSERT(crr == within_crr);
 	    ASSERT((char*)x > (char*)crr);
 	    ASSERT(((char*)x + AOFF_BLK_SZ(x)) <= ((char*)crr + CARRIER_SZ(crr)));
+
+	}
+	if (flavor == AOFF_BF) {
+	    AOFF_RBTree_t* y = x;
+	    AOFF_RBTree_t* nxt = LIST_NEXT(y);
+	    ASSERT(IS_TREE_NODE(x));
+	    while (nxt) {
+		ASSERT(IS_LIST_ELEM(nxt));
+		ASSERT(AOFF_BLK_SZ(nxt) == AOFF_BLK_SZ(x));
+		ASSERT(FBLK_TO_MBC(&nxt->hdr) == within_crr);
+		ASSERT(LIST_PREV(nxt) == y);
+		y = nxt;
+		nxt = LIST_NEXT(nxt);
+	    }
 	}
 
 	if (IS_RED(x)) {
@@ -1127,13 +1215,13 @@ check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint size)
 
 	if (x->left) {
 	    ASSERT(x->left->parent == x);
-	    ASSERT(cmp_blocks(bestfit, x->left, x) < 0);
+	    ASSERT(cmp_blocks(flavor, x->left, x) < 0);
 	    ASSERT(x->left->max_sz <= x->max_sz);	    
 	}
 
 	if (x->right) {
 	    ASSERT(x->right->parent == x);
-	    ASSERT(cmp_blocks(bestfit, x->right, x) > 0);
+	    ASSERT(cmp_blocks(flavor, x->right, x) > 0);
 	    ASSERT(x->right->max_sz <= x->max_sz);	    
 	}
 	ASSERT(x->max_sz >= AOFF_BLK_SZ(x));
@@ -1142,7 +1230,7 @@ check_tree(Carrier_t* within_crr, int bestfit, 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(bestfit, x, res) < 0) {
+	    if (!res || cmp_blocks(flavor, x, res) < 0) {
 		res = x;
 	    }
 	}
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.h b/erts/emulator/beam/erl_ao_firstfit_alloc.h
index 87427e8e62..6fa2c0e5bf 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.h
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.h
@@ -24,12 +24,17 @@
 #include "erl_alloc_util.h"
 
 #define ERTS_ALC_AOFF_ALLOC_VSN_STR "0.9"
-#define ERTS_ALC_AOFF_CBF_ALLOC_VSN_STR "0.9"
 
 typedef struct AOFFAllctr_t_ AOFFAllctr_t;
 
+enum AOFF_Flavor {
+    AOFF_AOFF = 0,
+    AOFF_AOBF = 1,
+    AOFF_BF   = 2
+};
+
 typedef struct {
-    int bf_within_carrier;
+    enum AOFF_Flavor flavor;
 } AOFFAllctrInit_t;
 
 #define ERTS_DEFAULT_AOFF_ALLCTR_INIT {0/*dummy*/}
@@ -52,7 +57,7 @@ struct AOFFAllctr_t_ {
     Allctr_t		allctr; /* Has to be first! */
 
     struct AOFF_RBTree_t_* mbc_root;
-    int bf_within_carrier;
+    enum AOFF_Flavor flavor;
 };
 
 UWord erts_aoffalc_test(UWord, UWord, UWord);
diff --git a/erts/emulator/beam/erl_bestfit_alloc.c b/erts/emulator/beam/erl_bestfit_alloc.c
index 58e53c3d00..41f449bb28 100644
--- a/erts/emulator/beam/erl_bestfit_alloc.c
+++ b/erts/emulator/beam/erl_bestfit_alloc.c
@@ -966,15 +966,17 @@ UWord
 erts_bfalc_test(UWord op, UWord a1, UWord a2)
 {
     switch (op) {
-    case 0x200:	return (UWord) ((BFAllctr_t *) a1)->address_order;
+    case 0x200:	return (UWord) ((BFAllctr_t *) a1)->address_order; /* IS_AOBF */
     case 0x201:	return (UWord) ((BFAllctr_t *) a1)->mbc_root;
     case 0x202:	return (UWord) ((RBTree_t *) a1)->parent;
     case 0x203:	return (UWord) ((RBTree_t *) a1)->left;
     case 0x204:	return (UWord) ((RBTree_t *) a1)->right;
-    case 0x205:	return (UWord) ((RBTreeList_t *) a1)->next;
+    case 0x205:	return (UWord) LIST_NEXT(a1);
     case 0x206:	return (UWord) IS_BLACK((RBTree_t *) a1);
     case 0x207:	return (UWord) IS_TREE_NODE((RBTree_t *) a1);
     case 0x208:	return (UWord) 1; /* IS_BF_ALGO */
+    case 0x20a: return (UWord) !((BFAllctr_t *) a1)->address_order; /* IS_BF */
+    case 0x20b:	return (UWord) LIST_PREV(a1);
     default:	ASSERT(0); return ~((UWord) 0);
     }
 }
diff --git a/erts/emulator/test/alloc_SUITE_data/allocator_test.h b/erts/emulator/test/alloc_SUITE_data/allocator_test.h
index c37b074f93..2d6c5f9dc7 100644
--- a/erts/emulator/test/alloc_SUITE_data/allocator_test.h
+++ b/erts/emulator/test/alloc_SUITE_data/allocator_test.h
@@ -102,7 +102,8 @@ typedef void* erts_cond;
 #define RBT_IS_TREE(T)		((Ulong)	ALC_TEST1(RBT_OP(7), (T)))
 #define IS_BF_ALGO(A)		((Ulong)	ALC_TEST1(RBT_OP(8), (A)))
 #define RBT_MAX_SZ(T)		((Ulong)	ALC_TEST1(RBT_OP(9), (T)))
-#define IS_CBF(A)		((Ulong)	ALC_TEST1(RBT_OP(0xa), (A)))
+#define IS_BF(A)		((Ulong)	ALC_TEST1(RBT_OP(0xa), (A)))
+#define RBT_PREV(T)		((RBTL_t *)	ALC_TEST1(RBT_OP(0xb), (T)))
 
 /* From erl_mseg.c */
 #define HAVE_MSEG()		((int)		ALC_TEST0(0x400))
diff --git a/erts/emulator/test/alloc_SUITE_data/coalesce.c b/erts/emulator/test/alloc_SUITE_data/coalesce.c
index 36710bf7b5..9da49a0d14 100644
--- a/erts/emulator/test/alloc_SUITE_data/coalesce.c
+++ b/erts/emulator/test/alloc_SUITE_data/coalesce.c
@@ -267,7 +267,7 @@ void
 testcase_run(TestCaseState_t *tcs)
 {
     char *argv_org[] = {"-tsmbcs511","-tmmbcs511", "-tsbct512", "-trmbcmt100", "-tas", NULL, NULL};
-    char *alg[] = {"af", "gf", "bf", "aobf", "aoff", "aoffcaobf", NULL};
+    char *alg[] = {"af", "gf", "bf", "aobf", "aoff", "aoffcbf", "aoffcaobf", NULL};
     int i;
 
     for (i = 0; alg[i]; i++) {
diff --git a/erts/emulator/test/alloc_SUITE_data/rbtree.c b/erts/emulator/test/alloc_SUITE_data/rbtree.c
index 702f075304..49df2f0245 100644
--- a/erts/emulator/test/alloc_SUITE_data/rbtree.c
+++ b/erts/emulator/test/alloc_SUITE_data/rbtree.c
@@ -85,23 +85,21 @@ print_tree(TestCaseState_t *tcs, RBT_t *root)
 static RBT_t *
 check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 {
-    enum { BF, AOBF, AOFF, AOFFCAOBF }type;
+    enum { BF, AOBF, AOFF } type;
     int i, max_i;
     char stk[128];
     RBT_t *root, *x, *y, *res;
     Ulong x_sz, y_sz, is_x_black;
     long blacks, curr_blacks;
+    int have_max_sz;
 
     res = NULL;
 
-    if (IS_BF_ALGO(alc)) {
-	if (IS_AOBF(alc)) type = AOBF;
-	else type = BF;
-    }
-    else { /* AOFF_ALGO */
-	if (IS_CBF(alc)) type = AOFFCAOBF;
-	else type = AOFF;
-    }
+    if (IS_AOBF(alc)) type = AOBF;
+    else if (IS_BF(alc)) type = BF;
+    else type = AOFF;
+
+    have_max_sz = !IS_BF_ALGO(alc);
 
     root = RBT_ROOT(alc, size);
 
@@ -191,17 +189,10 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 		break;
 	    case AOFF:
 		ASSERT(tcs, y < x);
-		ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
 		break;
-	    case AOFFCAOBF:
-		{
-		    void* x_crr = BLK_TO_MBC(x);
-		    void* y_crr = BLK_TO_MBC(y);
-		    ASSERT(tcs, (y < x && (x_crr != y_crr || x_sz == y_sz))
-			   || (y_sz < x_sz && x_crr == y_crr));
-		    ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
-		    break;
-		}
+	    }
+	    if (have_max_sz) {
+		ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
 	    }
 	}
 
@@ -219,27 +210,22 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 		break;
 	    case AOFF:
 		ASSERT(tcs, y > x);
-		ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
 		break;
-	    case AOFFCAOBF:
-		{
-		    void* x_crr = BLK_TO_MBC(x);
-		    void* y_crr = BLK_TO_MBC(y);
-		    ASSERT(tcs, (y > x && (x_crr != y_crr || x_sz == y_sz))
-			   || (y_sz > x_sz && x_crr == y_crr));
-		    ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
-		    break;
-		}
+	    }
+	    if (have_max_sz) {
+		ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
 	    }
 	}
 
 	if (type == BF) {
 	    Ulong l_sz;
-	    RBTL_t *l = RBT_NEXT(x);
+	    RBTL_t *l, *prev=x;
 	    for (l = RBT_NEXT(x); l; l = RBT_NEXT(l)) {
 		l_sz = BLK_SZ(l);
 		ASSERT(tcs, l_sz == x_sz);
 		ASSERT(tcs, !RBT_IS_TREE(l));
+		ASSERT(tcs, RBT_PREV(l) == prev);
+		prev = l;
 	    }
 	}
 
@@ -262,18 +248,7 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 			res = x;
 		    }
 		    break;
-		case AOFFCAOBF:
-		    if (BLK_TO_MBC(x) != BLK_TO_MBC(res) || x_sz == y_sz) {
-			if (x < res) {
-			    res = x;
-			}
-		    }
-		    else if (x_sz < y_sz) {
-			res = x;
-		    }
-		    break;
 		}
-
 	    }
 	}
 
@@ -310,7 +285,7 @@ do_check(TestCaseState_t *tcs, Allctr_t *a, Ulong size, int ignore_null)
     tmp = ALLOC(a, sz - ABLK_HDR_SZ);
     ASSERT(tcs, tmp);
     y = UMEM2BLK(tmp);
-    if (!(IS_BF_ALGO(a) && !IS_AOBF(a))) {
+    if (!IS_BF(a)) {
 	ASSERT(tcs, x == y);
     }
     else {
@@ -488,6 +463,7 @@ testcase_run(TestCaseState_t *tcs)
     char *argv2[] = {"-tasaobf", NULL};
     char *argv3[] = {"-tasaoff", NULL};
     char *argv4[] = {"-tasaoffcaobf", NULL};
+    char *argv5[] = {"-tasaoffcbf", NULL};
     Allctr_t *a;
     rbtree_test_data *td;
 
@@ -511,6 +487,7 @@ testcase_run(TestCaseState_t *tcs)
     ASSERT(tcs, a);
     ASSERT(tcs, IS_BF_ALGO(a));
     ASSERT(tcs, !IS_AOBF(a));
+    ASSERT(tcs, IS_BF(a));
 
     test_it(tcs);
 
@@ -529,6 +506,7 @@ testcase_run(TestCaseState_t *tcs)
     ASSERT(tcs, a);
     ASSERT(tcs, IS_BF_ALGO(a));
     ASSERT(tcs, IS_AOBF(a));
+    ASSERT(tcs, !IS_BF(a));
 
     test_it(tcs);
 
@@ -546,7 +524,8 @@ testcase_run(TestCaseState_t *tcs)
 
     ASSERT(tcs, a);
     ASSERT(tcs, !IS_BF_ALGO(a));
-    ASSERT(tcs, !IS_CBF(a));
+    ASSERT(tcs, !IS_AOBF(a));
+    ASSERT(tcs, !IS_BF(a));
 
     test_it(tcs);
     test_carrier_migration(tcs);
@@ -556,7 +535,7 @@ testcase_run(TestCaseState_t *tcs)
 
     testcase_printf(tcs, "Address order first fit test succeeded!\n");
 
-    /* Address order first fit, best fit within carrier */
+    /* Address order first fit, aobf within carrier */
 
     testcase_printf(tcs, "Starting test of aoffcaobf...\n");
 
@@ -565,7 +544,28 @@ testcase_run(TestCaseState_t *tcs)
 
     ASSERT(tcs, a);
     ASSERT(tcs, !IS_BF_ALGO(a));
-    ASSERT(tcs, IS_CBF(a));
+    ASSERT(tcs, IS_AOBF(a));
+    ASSERT(tcs, !IS_BF(a));
+
+    test_it(tcs);
+    test_carrier_migration(tcs);
+
+    STOP_ALC(a);
+    td->allocator = NULL;
+
+    testcase_printf(tcs, "aoffcaobf test succeeded!\n");
+
+    /* Address order first fit, bf within carrier */
+
+    testcase_printf(tcs, "Starting test of aoffcbf...\n");
+
+    current_rbt_type_op_base = AO_FIRSTFIT_OP_BASE;
+    td->allocator = a = START_ALC("rbtree_aoffcbf_", 0, argv5);
+
+    ASSERT(tcs, a);
+    ASSERT(tcs, !IS_BF_ALGO(a));
+    ASSERT(tcs, !IS_AOBF(a));
+    ASSERT(tcs, IS_BF(a));
 
     test_it(tcs);
     test_carrier_migration(tcs);