erts: Add "bestfit within carrier" for aoff allocator (aoffcbf)

9 files changed, 181 insertions, 66 deletions

diff --git a/erts/emulator/beam/erl_alloc.c b/erts/emulator/beam/erl_alloc.c
index 403776aade..cb69be33ad 100644
--- a/erts/emulator/beam/erl_alloc.c
+++ b/erts/emulator/beam/erl_alloc.c
@@ -1197,6 +1197,11 @@ handle_au_arg(struct au_init *auip,
 	    }
 	    else if (strcmp("aoff", alg) == 0) {
 		auip->atype = AOFIRSTFIT;
+		auip->init.aoff.bf_within_carrier = 0;
+	    }
+	    else if (strcmp("aoffcbf", alg) == 0) {
+		auip->atype = AOFIRSTFIT;
+		auip->init.aoff.bf_within_carrier = 1;
 	    }
 	    else {
 		bad_value(param, sub_param + 1, alg);
diff --git a/erts/emulator/beam/erl_alloc_util.c b/erts/emulator/beam/erl_alloc_util.c
index 53062979a6..c57ddc424e 100644
--- a/erts/emulator/beam/erl_alloc_util.c
+++ b/erts/emulator/beam/erl_alloc_util.c
@@ -76,16 +76,6 @@ static int initialized = 0;
 
 int erts_have_sbmbc_alloc;
 
-#if HAVE_ERTS_MSEG
-
-#define MSEG_UNIT_SHIFT         MSEG_ALIGN_BITS
-#define MSEG_UNIT_SZ            (1 << MSEG_UNIT_SHIFT)
-#define MSEG_UNIT_MASK		((~(UWord)0) << MSEG_UNIT_SHIFT)
-
-#define MSEG_UNIT_FLOOR(X)	((X) & MSEG_UNIT_MASK)
-#define MSEG_UNIT_CEILING(X)	MSEG_UNIT_FLOOR((X) + ~MSEG_UNIT_MASK)
-
-#endif
 
 #define INV_SYS_ALLOC_CARRIER_MASK	((UWord) (sys_alloc_carrier_size - 1))
 #define SYS_ALLOC_CARRIER_MASK		(~INV_SYS_ALLOC_CARRIER_MASK)
@@ -173,14 +163,6 @@ MBC after deallocating first block:
 #define SET_BLK_SZ_FTR(B, SZ) \
   (((FreeBlkFtr_t *) (((char *) (B)) + (SZ)))[-1] = (SZ))
 
-#define THIS_FREE_BLK_HDR_FLG 	(((UWord) 1) << 0)
-#define PREV_FREE_BLK_HDR_FLG 	(((UWord) 1) << 1)
-#define LAST_BLK_HDR_FLG 	(((UWord) 1) << 2)
-
-/* Special flag combo for (allocated) SBC blocks 
-*/
-#define SBC_BLK_HDR_FLG (THIS_FREE_BLK_HDR_FLG | PREV_FREE_BLK_HDR_FLG | LAST_BLK_HDR_FLG)
-
 #define SET_MBC_ABLK_SZ(B, SZ) \
   (ASSERT(((SZ) & FLG_MASK) == 0), \
    (B)->bhdr = (((B)->bhdr) & ~MBC_ABLK_SZ_MASK) | (SZ))
@@ -222,15 +204,6 @@ MBC after deallocating first block:
      ASSERT(((UWord)(F) & (~FLG_MASK|THIS_FREE_BLK_HDR_FLG|PREV_FREE_BLK_HDR_FLG)) == THIS_FREE_BLK_HDR_FLG), \
      (B)->bhdr = ((Sz) | (F)), \
      (B)->u.carrier = (C))
-
-#  define ABLK_TO_MBC(B) \
-    (ASSERT(IS_MBC_BLK(B) && IS_ALLOCED_BLK(B)), \
-     (Carrier_t*)((MSEG_UNIT_FLOOR((UWord)(B)) - \
-		  (((B)->bhdr >> MBC_ABLK_OFFSET_SHIFT) << MSEG_UNIT_SHIFT))))
-
-#  define FBLK_TO_MBC(B) \
-    (ASSERT(IS_MBC_BLK(B) && IS_FREE_BLK(B)), \
-     (B)->u.carrier)
       
 #  define BLK_TO_MBC(B) (IS_FREE_BLK(B) ? FBLK_TO_MBC(B) : ABLK_TO_MBC(B))
 
@@ -273,8 +246,6 @@ MBC after deallocating first block:
      (B)->carrier = (C))
 
 #  define BLK_TO_MBC(B) ((B)->carrier)
-#  define ABLK_TO_MBC(B) BLK_TO_MBC(B)
-#  define FBLK_TO_MBC(B) BLK_TO_MBC(B)
 
 #  define IS_MBC_FIRST_BLK(AP,B) \
   ((char*)(B) == (char*)((B)->carrier) + MBC_HEADER_SIZE(AP))
@@ -300,8 +271,6 @@ MBC after deallocating first block:
   ((B)->bhdr & PREV_FREE_BLK_HDR_FLG)
 #define IS_PREV_BLK_ALLOCED(B) \
   (!IS_PREV_BLK_FREE((B)))
-#define IS_FREE_BLK(B) \
-  (ASSERT(!IS_SBC_BLK(B)), (B)->bhdr & THIS_FREE_BLK_HDR_FLG)
 #define IS_ALLOCED_BLK(B) \
   (!IS_FREE_BLK((B)))  
 #define IS_LAST_BLK(B) \
@@ -318,11 +287,6 @@ MBC after deallocating first block:
 #define GET_BLK_HDR_FLGS(B) \
   ((B)->bhdr & FLG_MASK)
 
-#define IS_SBC_BLK(B) \
-    (((B)->bhdr & FLG_MASK) == SBC_BLK_HDR_FLG)
-#define IS_MBC_BLK(B) \
-  (!IS_SBC_BLK((B)))
-
 #define MBC_BLK_SZ(B) (IS_FREE_BLK(B) ? MBC_FBLK_SZ(B) : MBC_ABLK_SZ(B))
 
 #define NXT_BLK(B) \
@@ -4440,6 +4404,7 @@ erts_alcu_test(UWord op, UWord a1, UWord a2)
     case 0x019:	return (UWord) PREV_BLK((Block_t *) a1);
     case 0x01a: return (UWord) IS_MBC_FIRST_BLK((Allctr_t*)a1, (Block_t *) a2);
     case 0x01b: return (UWord) sizeof(Unit_t);
+    case 0x01c: return (unsigned long) BLK_TO_MBC((Block_t*) a1);
     default:	ASSERT(0); return ~((UWord) 0);
     }
 }
diff --git a/erts/emulator/beam/erl_alloc_util.h b/erts/emulator/beam/erl_alloc_util.h
index 4773598561..404ba66971 100644
--- a/erts/emulator/beam/erl_alloc_util.h
+++ b/erts/emulator/beam/erl_alloc_util.h
@@ -221,8 +221,15 @@ erts_aint32_t erts_alcu_fix_alloc_shrink(Allctr_t *, erts_aint32_t);
 #define MBC_FBLK_SZ_MASK        UNIT_MASK
 #define CARRIER_SZ_MASK         UNIT_MASK
 
-
 #if HAVE_ERTS_MSEG
+
+#  define MSEG_UNIT_SHIFT         MSEG_ALIGN_BITS
+#  define MSEG_UNIT_SZ            (1 << MSEG_UNIT_SHIFT)
+#  define MSEG_UNIT_MASK		((~(UWord)0) << MSEG_UNIT_SHIFT)
+
+#  define MSEG_UNIT_FLOOR(X)	((X) & MSEG_UNIT_MASK)
+#  define MSEG_UNIT_CEILING(X)	MSEG_UNIT_FLOOR((X) + ~MSEG_UNIT_MASK)
+
 #  ifdef ARCH_64 
 #    define MBC_ABLK_OFFSET_BITS   24
 #  elif HAVE_SUPER_ALIGNED_MB_CARRIERS
@@ -280,6 +287,30 @@ typedef struct {
 #endif
 } Block_t;
 
+#define THIS_FREE_BLK_HDR_FLG 	(((UWord) 1) << 0)
+#define PREV_FREE_BLK_HDR_FLG 	(((UWord) 1) << 1)
+#define LAST_BLK_HDR_FLG 	(((UWord) 1) << 2)
+
+#define SBC_BLK_HDR_FLG /* Special flag combo for (allocated) SBC blocks */\
+    (THIS_FREE_BLK_HDR_FLG | PREV_FREE_BLK_HDR_FLG | LAST_BLK_HDR_FLG)
+
+#define IS_SBC_BLK(B) (((B)->bhdr & FLG_MASK) == SBC_BLK_HDR_FLG)
+#define IS_MBC_BLK(B) (!IS_SBC_BLK((B)))
+#define IS_FREE_BLK(B) (ASSERT(IS_MBC_BLK(B)), \
+			(B)->bhdr & THIS_FREE_BLK_HDR_FLG)
+
+#if MBC_ABLK_OFFSET_BITS
+#  define FBLK_TO_MBC(B) (ASSERT(IS_MBC_BLK(B) && IS_FREE_BLK(B)), \
+			  (B)->u.carrier)
+#  define ABLK_TO_MBC(B) \
+    (ASSERT(IS_MBC_BLK(B) && !IS_FREE_BLK(B)), \
+     (Carrier_t*)((MSEG_UNIT_FLOOR((UWord)(B)) - \
+		  (((B)->bhdr >> MBC_ABLK_OFFSET_SHIFT) << MSEG_UNIT_SHIFT))))
+#else
+#  define FBLK_TO_MBC(B) ((B)->carrier)
+#  define ABLK_TO_MBC(B) ((B)->carrier)
+#endif
+
 typedef UWord FreeBlkFtr_t; /* Footer of a free block */
 
 typedef struct {
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index b916cb6198..e277006e58 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 free-blocks 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
  *              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. 
  *
  * Authors: 	Rickard Green/Sverker Eriksson
  */
@@ -94,7 +99,7 @@ struct AOFF_RBTree_t_ {
 #define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
 
 #ifdef HARD_DEBUG
-static AOFF_RBTree_t * check_tree(AOFF_RBTree_t* root, Uint);
+static AOFF_RBTree_t * check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint);
 #endif
 
 
@@ -132,6 +137,32 @@ 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,
+				    AOFF_RBTree_t* lhs, AOFF_RBTree_t* rhs)
+{
+    if (alc->bf_within_carrier
+	&& FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr)) {
+	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,
+				      Block_t* cand_blk, AOFF_RBTree_t* rhs)
+{
+    if (alc->bf_within_carrier) {
+	if (IS_FREE_BLK(cand_blk))
+	    return cmp_blocks(alc, (AOFF_RBTree_t*)cand_blk, rhs);
+
+	if (ABLK_TO_MBC(cand_blk) == FBLK_TO_MBC(&rhs->hdr)) {
+	    SWord diff = (SWord)MBC_ABLK_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);
@@ -184,11 +215,13 @@ 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->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 */
@@ -416,7 +449,7 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
     null_x.parent = NULL;
 
 #ifdef HARD_DEBUG
-    check_tree(*root, 0);
+    check_tree(alc, *root, 0);
 #endif
 
     /* Remove node from tree... */
@@ -576,7 +609,7 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
     DESTROY_TREE_NODE(del);
 
 #ifdef HARD_DEBUG
-    check_tree(*root, 0);
+    check_tree(alc, *root, 0);
 #endif
 }
 
@@ -590,7 +623,7 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
     Uint blk_sz = AOFF_BLK_SZ(blk);
 
 #ifdef HARD_DEBUG
-    check_tree(*root, 0);
+    check_tree(alc, *root, 0);
 #endif
 
     blk->flags	= 0;
@@ -609,7 +642,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(alc, blk, x) < 0) {
 		if (!x->left) {
 		    blk->parent = x;
 		    x->left = blk;
@@ -637,7 +670,7 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
     }
 
 #ifdef HARD_DEBUG
-    check_tree(*root, 0);
+    check_tree(alc, *root, 0);
 #endif
 }
 
@@ -650,7 +683,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
 		       ? alc->sbmbc_root : alc->mbc_root);
     AOFF_RBTree_t *blk = NULL;
 #ifdef HARD_DEBUG
-    AOFF_RBTree_t* dbg_blk = check_tree(x, size);
+    AOFF_RBTree_t* dbg_blk = check_tree(alc, x, size);
 #endif
 
     ASSERT(!cand_blk || cand_size >= size);
@@ -675,7 +708,7 @@ 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, cand_blk, blk) < 0) {
 	return NULL; /* cand_blk was better */
     }
 
@@ -692,6 +725,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
 static struct {
     Eterm as;
     Eterm aoff;
+    Eterm aoffcbf;
 #ifdef DEBUG
     Eterm end_of_atoms;
 #endif
@@ -720,6 +754,7 @@ init_atoms(void)
 #endif
     AM_INIT(as);
     AM_INIT(aoff);
+    AM_INIT(aoffcbf);
 
 #ifdef DEBUG
     for (atom = (Eterm *) &am; atom < &am.end_of_atoms; atom++) {
@@ -749,6 +784,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 +792,7 @@ info_options(Allctr_t *allctr,
 		   print_to_arg,
 		   "%sas: %s\n",
 		   prefix,
-		   "aoff");
+		   alc->bf_within_carrier ? "aoffcbf" : "aoff");
     }
 
     if (hpp || szp) {
@@ -766,7 +802,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.aoffcbf : am.aoff);
     }
 
     return res;
@@ -784,14 +821,14 @@ UWord
 erts_aoffalc_test(UWord op, UWord a1, UWord a2)
 {
     switch (op) {
-    case 0x500:	return (UWord) 0; /* IS_AOBF */
     case 0x501:	return (UWord) ((AOFFAllctr_t *) a1)->mbc_root;
     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) 1; /* IS_AOFF */
+    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);
     }
 }
@@ -840,12 +877,14 @@ static void print_tree(AOFF_RBTree_t*);
  */
 
 static AOFF_RBTree_t *
-check_tree(AOFF_RBTree_t* root, Uint size)
+check_tree(AOFFAllctr_t* alc, 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 +898,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 +923,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 +935,13 @@ check_tree(AOFF_RBTree_t* root, Uint size)
 	    }
 	}
 
+	++node_cnt;
+	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 (IS_RED(x)) {
 	    ASSERT(IS_BLACK(x->right));
@@ -901,13 +952,13 @@ check_tree(AOFF_RBTree_t* root, Uint size)
 
 	if (x->left) {
 	    ASSERT(x->left->parent == x);
-	    ASSERT(x->left < x);
+	    ASSERT(cmp_blocks(alc, 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(alc, x->right, x) > 0);
 	    ASSERT(x->right->max_sz <= x->max_sz);	    
 	}
 	ASSERT(x->max_sz >= AOFF_BLK_SZ(x));
@@ -916,7 +967,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(alc, x, res) < 0) {
 		res = x;
 	    }
 	}
@@ -926,10 +977,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);
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.h b/erts/emulator/beam/erl_ao_firstfit_alloc.h
index 21c36c6654..36995a20f0 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.h
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.h
@@ -24,11 +24,12 @@
 #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;
 
 typedef struct {
-    int dummy;
+    int bf_within_carrier;
 } AOFFAllctrInit_t;
 
 #define ERTS_DEFAULT_AOFF_ALLCTR_INIT {0/*dummy*/}
@@ -52,6 +53,7 @@ struct AOFFAllctr_t_ {
 
     struct AOFF_RBTree_t_* mbc_root;
     struct AOFF_RBTree_t_* sbmbc_root;
+    int bf_within_carrier;
 };
 
 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 ed843a51fb..e3fc8f4cb1 100644
--- a/erts/emulator/beam/erl_bestfit_alloc.c
+++ b/erts/emulator/beam/erl_bestfit_alloc.c
@@ -984,7 +984,7 @@ erts_bfalc_test(UWord op, UWord a1, UWord a2)
     case 0x205:	return (UWord) ((RBTreeList_t *) a1)->next;
     case 0x206:	return (UWord) IS_BLACK((RBTree_t *) a1);
     case 0x207:	return (UWord) IS_TREE_NODE((RBTree_t *) a1);
-    case 0x208:	return (UWord) 0; /* IS_AOFF */
+    case 0x208:	return (UWord) 1; /* IS_BF_ALGO */
     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 c0396ddb61..ec5bb9dcd6 100644
--- a/erts/emulator/test/alloc_SUITE_data/allocator_test.h
+++ b/erts/emulator/test/alloc_SUITE_data/allocator_test.h
@@ -75,6 +75,7 @@ typedef void* erts_cond;
 #define PREV_BLK(B)		((Block_t *)	ALC_TEST1(0x019, (B)))
 #define IS_MBC_FIRST_BLK(A,B)	((Ulong)	ALC_TEST2(0x01a, (A), (B)))
 #define UNIT_SZ			((Ulong)	ALC_TEST0(0x01b))
+#define BLK_TO_MBC(B)		((Carrier_t *)	ALC_TEST1(0x01c, (B)))
 
 /* From erl_goodfit_alloc.c */
 #define BKT_IX(A, S)		((Ulong)	ALC_TEST2(0x100, (A), (S)))
@@ -91,8 +92,9 @@ typedef void* erts_cond;
 #define RBT_NEXT(T)		((RBTL_t *)	ALC_TEST1(RBT_OP(5), (T)))
 #define RBT_IS_BLACK(T)		((Ulong)	ALC_TEST1(RBT_OP(6), (T)))
 #define RBT_IS_TREE(T)		((Ulong)	ALC_TEST1(RBT_OP(7), (T)))
-#define IS_AOFF(A)		((Ulong)	ALC_TEST1(RBT_OP(8), (A)))
+#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)))
 
 /* 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 981fa6d43e..1fb4d7791d 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", NULL};
+    char *alg[] = {"af", "gf", "bf", "aobf", "aoff", "aoffcbf", 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 4e7f821baf..105c9c0eb4 100644
--- a/erts/emulator/test/alloc_SUITE_data/rbtree.c
+++ b/erts/emulator/test/alloc_SUITE_data/rbtree.c
@@ -85,7 +85,7 @@ 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 }type;
+    enum { BF, AOBF, AOFF, AOFFCBF }type;
     int i, max_i;
     char stk[128];
     RBT_t *root, *x, *y, *res;
@@ -94,9 +94,14 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 
     res = NULL;
 
-    if      (IS_AOBF(alc)) type = AOBF;
-    else if (IS_AOFF(alc)) type = AOFF;
-    else type = BF;
+    if (IS_BF_ALGO(alc)) {
+	if (IS_AOBF(alc)) type = AOBF;
+	else type = BF;
+    }
+    else { /* AOFF_ALGO */
+	if (IS_CBF(alc)) type = AOFFCBF;
+	else type = AOFF;
+    }
 
     root = RBT_ROOT(alc);
 
@@ -188,6 +193,15 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 		ASSERT(tcs, y < x);
 		ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
 		break;
+	    case AOFFCBF:
+		{
+		    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;
+		}
 	    }
 	}
 
@@ -207,6 +221,15 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 		ASSERT(tcs, y > x);
 		ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
 		break;
+	    case AOFFCBF:
+		{
+		    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;
+		}
 	    }
 	}
 
@@ -239,7 +262,18 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 			res = x;
 		    }
 		    break;
+		case AOFFCBF:
+		    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;
 		}
+
 	    }
 	}
 
@@ -273,7 +307,7 @@ do_check(TestCaseState_t *tcs, Allctr_t *a, Ulong size)
     tmp = ALLOC(a, sz - ABLK_HDR_SZ);
     ASSERT(tcs, tmp);
     y = UMEM2BLK(tmp);
-    if (IS_AOBF(a)) {
+    if (!(IS_BF_ALGO(a) && !IS_AOBF(a))) {
 	ASSERT(tcs, x == y);
     }
     else {
@@ -369,6 +403,7 @@ testcase_run(TestCaseState_t *tcs)
     char *argv1[] = {"-tasbf", NULL};
     char *argv2[] = {"-tasaobf", NULL};
     char *argv3[] = {"-tasaoff", NULL};
+    char *argv4[] = {"-tasaoffcbf", NULL};
     Allctr_t *a;
     rbtree_test_data *td;
 
@@ -390,6 +425,7 @@ testcase_run(TestCaseState_t *tcs)
     td->allocator = a = START_ALC("rbtree_bf_", 0, argv1);
 
     ASSERT(tcs, a);
+    ASSERT(tcs, IS_BF_ALGO(a));
     ASSERT(tcs, !IS_AOBF(a));
 
     test_it(tcs);
@@ -407,6 +443,7 @@ testcase_run(TestCaseState_t *tcs)
     td->allocator = a = START_ALC("rbtree_aobf_", 0, argv2);
 
     ASSERT(tcs, a);
+    ASSERT(tcs, IS_BF_ALGO(a));
     ASSERT(tcs, IS_AOBF(a));
 
     test_it(tcs);
@@ -424,6 +461,8 @@ testcase_run(TestCaseState_t *tcs)
     td->allocator = a = START_ALC("rbtree_aoff_", 0, argv3);
 
     ASSERT(tcs, a);
+    ASSERT(tcs, !IS_BF_ALGO(a));
+    ASSERT(tcs, !IS_CBF(a));
 
     test_it(tcs);
 
@@ -431,4 +470,23 @@ testcase_run(TestCaseState_t *tcs)
     td->allocator = NULL;
 
     testcase_printf(tcs, "Address order first fit test succeeded!\n");
+
+    /* Address order first fit, best fit 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, argv4);
+
+    ASSERT(tcs, a);
+    ASSERT(tcs, !IS_BF_ALGO(a));
+    ASSERT(tcs, IS_CBF(a));
+
+    test_it(tcs);
+
+    STOP_ALC(a);
+    td->allocator = NULL;
+
+    testcase_printf(tcs, "aoffcbf test succeeded!\n");
+
 }