erts: Refactor erl_ao_firstfit_alloc

In preparation for carrier age order.

Change 'flavor' to 'blk_order' and 'crr_order'.

3 files changed, 77 insertions, 66 deletions

diff --git a/erts/emulator/beam/erl_alloc.c b/erts/emulator/beam/erl_alloc.c
index b51cf5bdfc..4c9fb466eb 100644
--- a/erts/emulator/beam/erl_alloc.c
+++ b/erts/emulator/beam/erl_alloc.c
@@ -167,7 +167,7 @@ enum allctr_type {
     GOODFIT,
     BESTFIT,
     AFIT,
-    AOFIRSTFIT
+    FIRSTFIT
 };
 
 struct au_init {
@@ -500,8 +500,9 @@ set_default_test_alloc_opts(struct au_init *ip)
     SET_DEFAULT_ALLOC_OPTS(ip);
     ip->enable			= 0; /* Disabled by default */
     ip->thr_spec		= -1 * erts_no_schedulers;
-    ip->atype			= AOFIRSTFIT;
-    ip->init.aoff.flavor        = AOFF_BF;
+    ip->atype			= FIRSTFIT;
+    ip->init.aoff.crr_order     = FF_AOFF;
+    ip->init.aoff.blk_order     = FF_BF;
     ip->init.util.name_prefix	= "test_";
     ip->init.util.alloc_no	= ERTS_ALC_A_TEST;
     ip->init.util.mmbcs 	= 0; /* Main carrier size */
@@ -606,7 +607,7 @@ strategy_support_carrier_migration(struct au_init *auip)
      * Currently only aoff, aoffcbf and aoffcaobf support carrier
      * migration, i.e, type AOFIRSTFIT.
      */
-    return auip->atype == AOFIRSTFIT;
+    return auip->atype == FIRSTFIT;
 }
 
 static ERTS_INLINE void
@@ -622,8 +623,9 @@ adjust_carrier_migration_support(struct au_init *auip)
 	 */
 	if (!strategy_support_carrier_migration(auip)) {
 	    /* Default to aoffcbf */
-	    auip->atype = AOFIRSTFIT;
-	    auip->init.aoff.flavor = AOFF_BF;
+	    auip->atype = FIRSTFIT;
+	    auip->init.aoff.crr_order = FF_AOFF;
+	    auip->init.aoff.blk_order = FF_BF;
 	}
     }
 #else
@@ -1176,7 +1178,7 @@ start_au_allocator(ErtsAlcType_t alctr_n,
 					   &init->init.af,
 					   &init->init.util);
 	    break;
-    	case AOFIRSTFIT:
+	case FIRSTFIT:
 	    as = erts_aoffalc_start((AOFFAllctr_t *) as0,
 					     &init->init.aoff,
 					     &init->init.util);
@@ -1416,16 +1418,19 @@ handle_au_arg(struct au_init *auip,
 		auip->atype = AFIT;
 	    }
 	    else if (strcmp("aoff", alg) == 0) {
-		auip->atype = AOFIRSTFIT;
-		auip->init.aoff.flavor = AOFF_AOFF;
+		auip->atype = FIRSTFIT;
+		auip->init.aoff.crr_order = FF_AOFF;
+		auip->init.aoff.blk_order = FF_AOFF;
 	    }
 	    else if (strcmp("aoffcbf", alg) == 0) {
-		auip->atype = AOFIRSTFIT;
-		auip->init.aoff.flavor = AOFF_BF;
+		auip->atype = FIRSTFIT;
+		auip->init.aoff.crr_order = FF_AOFF;
+		auip->init.aoff.blk_order = FF_BF;
 	    }
 	    else if (strcmp("aoffcaobf", alg) == 0) {
-		auip->atype = AOFIRSTFIT;
-		auip->init.aoff.flavor = AOFF_AOBF;
+		auip->atype = FIRSTFIT;
+		auip->init.aoff.crr_order = FF_AOFF;
+		auip->init.aoff.blk_order = FF_AOBF;
 	    }
 	    else {
 		bad_value(param, sub_param + 1, alg);
@@ -3634,7 +3639,7 @@ UWord erts_alc_test(UWord op, UWord a1, UWord a2, UWord a3)
 					  &init.init.af,
 					  &init.init.util);
 		break;
-	    case AOFIRSTFIT:
+	    case FIRSTFIT:
 		allctr = erts_aoffalc_start((AOFFAllctr_t *)
 					  erts_alloc(ERTS_ALC_T_UNDEF,
 						     sizeof(AOFFAllctr_t)),
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index 05ba1f9891..8808a4f0a4 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -137,11 +137,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,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_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 +179,27 @@ 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,
+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;
+    {
+	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,
+static ERTS_INLINE SWord cmp_cand_blk(enum AOFFSortOrder order,
 				      Block_t* cand_blk, AOFF_RBTree_t* rhs)
 {
-    if (flavor != AOFF_AOFF) {
+    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,7 +220,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(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);
@@ -254,11 +256,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 +490,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 +513,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,9 +718,9 @@ 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
     */
@@ -731,16 +734,16 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block)
 	    if (!crr_node) break;
 	}
     }
-    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);
 }
 
 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 +763,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 +781,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 +801,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;
     }
@@ -850,7 +853,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 +866,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 */
     }
 
@@ -878,17 +881,17 @@ static void aoff_creating_mbc(Allctr_t *allctr, Carrier_t *carrier)
     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);
+    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,13 +914,13 @@ 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);   
 
     /* Link carrier in address order tree
      */
-    rbt_insert(AOFF_AOFF, root, &crr->rbt_node);
+    rbt_insert(alc->crr_order, root, &crr->rbt_node);
 
-    HARD_CHECK_TREE(NULL, 0, *root, 0);
+    HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
 }
 
 static void aoff_remove_mbc(Allctr_t *allctr, Carrier_t *carrier)
@@ -931,7 +934,7 @@ static void aoff_remove_mbc(Allctr_t *allctr, Carrier_t *carrier)
     if (!IS_CRR_IN_TREE(crr,*root))
         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,7 +942,7 @@ 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);
 }
 
 static UWord aoff_largest_fblk_in_mbc(Allctr_t* allctr, Carrier_t* carrier)
@@ -1029,7 +1032,7 @@ info_options(Allctr_t *allctr,
 		   print_to_arg,
 		   "%sas: %s\n",
 		   prefix,
-		   flavor_str[alc->flavor]);
+		   flavor_str[alc->blk_order-1]);
     }
 
     if (hpp || szp) {
@@ -1039,7 +1042,7 @@ 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_atom[alc->blk_order-1]);
     }
 
     return res;
@@ -1057,7 +1060,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 +1075,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);
     }
@@ -1132,7 +1135,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 +1147,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 +1206,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 +1229,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 +1244,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;
 	    }
 	}
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.h b/erts/emulator/beam/erl_ao_firstfit_alloc.h
index 7349c6ab19..7864f6c914 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.h
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.h
@@ -28,14 +28,15 @@
 
 typedef struct AOFFAllctr_t_ AOFFAllctr_t;
 
-enum AOFF_Flavor {
-    AOFF_AOFF = 0,
-    AOFF_AOBF = 1,
-    AOFF_BF   = 2
+enum AOFFSortOrder {
+    FF_AOFF  = 1,
+    FF_AOBF  = 2,
+    FF_BF    = 3
 };
 
 typedef struct {
-    enum AOFF_Flavor flavor;
+    enum AOFFSortOrder blk_order;
+    enum AOFFSortOrder crr_order;
 } AOFFAllctrInit_t;
 
 #define ERTS_DEFAULT_AOFF_ALLCTR_INIT {0/*dummy*/}
@@ -58,7 +59,8 @@ struct AOFFAllctr_t_ {
     Allctr_t		allctr; /* Has to be first! */
 
     struct AOFF_RBTree_t_* mbc_root;
-    enum AOFF_Flavor flavor;
+    enum AOFFSortOrder blk_order;
+    enum AOFFSortOrder crr_order;
 };
 
 UWord erts_aoffalc_test(UWord, UWord, UWord);