erts: Prepare aoff allocator for carrier migration

by putting blocks from different carrier into separate search trees.

Carriers are currently organized in a naive linked list by address order.

6 files changed, 137 insertions, 34 deletions

diff --git a/erts/emulator/beam/erl_alloc_util.c b/erts/emulator/beam/erl_alloc_util.c
index bf7d561b00..ce66727fae 100644
--- a/erts/emulator/beam/erl_alloc_util.c
+++ b/erts/emulator/beam/erl_alloc_util.c
@@ -205,8 +205,6 @@ MBC after deallocating first block:
      (B)->bhdr = ((Sz) | (F)), \
      (B)->u.carrier = (C))
       
-#  define BLK_TO_MBC(B) (IS_FREE_BLK(B) ? FBLK_TO_MBC(B) : ABLK_TO_MBC(B))
-
 #  define IS_MBC_FIRST_ABLK(AP,B) \
   ((((UWord)(B) & ~MSEG_UNIT_MASK) == MBC_HEADER_SIZE(AP)) \
    && ((B)->bhdr & MBC_ABLK_OFFSET_MASK) == 0)
@@ -245,8 +243,6 @@ MBC after deallocating first block:
      (B)->bhdr = ((Sz) | (F)), \
      (B)->carrier = (C))
 
-#  define BLK_TO_MBC(B) ((B)->carrier)
-
 #  define IS_MBC_FIRST_BLK(AP,B) \
   ((char*)(B) == (char*)((B)->carrier) + MBC_HEADER_SIZE(AP))
 #  define IS_MBC_FIRST_ABLK(AP,B) IS_MBC_FIRST_BLK(AP,B)
@@ -287,8 +283,6 @@ MBC after deallocating first block:
 #define GET_BLK_HDR_FLGS(B) \
   ((B)->bhdr & FLG_MASK)
 
-#define MBC_BLK_SZ(B) (IS_FREE_BLK(B) ? MBC_FBLK_SZ(B) : MBC_ABLK_SZ(B))
-
 #define NXT_BLK(B) \
   (ASSERT(IS_MBC_BLK(B)), \
    (Block_t *) (((char *) (B)) + MBC_BLK_SZ((B))))
diff --git a/erts/emulator/beam/erl_alloc_util.h b/erts/emulator/beam/erl_alloc_util.h
index af8f72ed7d..1183bf901d 100644
--- a/erts/emulator/beam/erl_alloc_util.h
+++ b/erts/emulator/beam/erl_alloc_util.h
@@ -306,10 +306,13 @@ typedef struct {
     (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))))
+#  define BLK_TO_MBC(B) (IS_FREE_BLK(B) ? FBLK_TO_MBC(B) : ABLK_TO_MBC(B))
 #else
 #  define FBLK_TO_MBC(B) ((B)->carrier)
 #  define ABLK_TO_MBC(B) ((B)->carrier)
+#  define BLK_TO_MBC(B)  ((B)->carrier)
 #endif
+#define MBC_BLK_SZ(B) (IS_FREE_BLK(B) ? MBC_FBLK_SZ(B) : MBC_ABLK_SZ(B))
 
 typedef UWord FreeBlkFtr_t; /* Footer of a free block */
 
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index 1570daf90e..50cbfc5033 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -98,7 +98,17 @@ struct AOFF_RBTree_t_ {
 };
 #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_Carrier_t* next;
+    AOFF_Carrier_t** prevp;
+    AOFF_RBTree_t* root;
+};
+
 #ifdef HARD_DEBUG
+static void check_carriers(AOFFAllctr_t* alc, AOFF_Carrier_t *crr, Uint32 flags);
 static AOFF_RBTree_t * check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint);
 #endif
 
@@ -140,8 +150,8 @@ static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
 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)) {
+    ASSERT(FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr));
+    if (alc->bf_within_carrier) {
 	SWord diff = (SWord)AOFF_BLK_SZ(lhs) - (SWord)AOFF_BLK_SZ(rhs);
 	if (diff) return diff;
     }
@@ -152,11 +162,8 @@ 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 (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;
 	}
     }
@@ -168,6 +175,8 @@ static ERTS_INLINE SWord cmp_cand_blk(AOFFAllctr_t* alc,
 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 void aoff_creating_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
+static void aoff_destroying_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
 
 static Eterm info_options(Allctr_t *, char *, int *, void *, Uint **, Uint *);
 static void init_atoms(void);
@@ -216,7 +225,7 @@ 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(Carrier_t);
+    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);
@@ -233,8 +242,8 @@ 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->init_atoms			= init_atoms;
 
 #ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
@@ -439,9 +448,11 @@ 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)
 {
+#ifdef HARD_DEBUG
     AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
-    AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC)
-			    ? &alc->sbmbc_root : &alc->mbc_root);
+#endif
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(del);
+    AOFF_RBTree_t **root = &crr->root;
     Uint spliced_is_black;
     AOFF_RBTree_t *x, *y, *z = (AOFF_RBTree_t *) del;
     AOFF_RBTree_t null_x; /* null_x is used to get the fixup started when we
@@ -450,6 +461,7 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
     null_x.parent = NULL;
 
 #ifdef HARD_DEBUG
+    check_carriers(alc, crr, flags);
     check_tree(alc, *root, 0);
 #endif
 
@@ -619,14 +631,16 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
 {
     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 **root;
+    AOFF_Carrier_t *blk_crr = (AOFF_Carrier_t*) FBLK_TO_MBC(block);
     Uint blk_sz = AOFF_BLK_SZ(blk);
 
 #ifdef HARD_DEBUG
-    check_tree(alc, *root, 0);
+    check_carriers(alc, blk_crr, flags);
+    check_tree(alc, blk_crr->root, 0);
 #endif
 
+    root = &blk_crr->root;
     blk->flags	= 0;
     blk->left	= NULL;
     blk->right	= NULL;
@@ -659,7 +673,6 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
 		}
 		x = x->right;
 	    }
-
 	}
 
 	/* Insert block into size tree */
@@ -680,15 +693,32 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
 		    Block_t *cand_blk, Uint cand_size, Uint32 flags)
 {
     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;
+    AOFF_Carrier_t *crr = ((flags & ERTS_ALCU_FLG_SBMBC)
+			   ? alc->sbmbc_first : alc->mbc_first);
+    AOFF_RBTree_t *x, *blk = NULL;
 #ifdef HARD_DEBUG
-    AOFF_RBTree_t* dbg_blk = check_tree(alc, x, size);
+    AOFF_RBTree_t* dbg_blk;
 #endif
 
     ASSERT(!cand_blk || cand_size >= size);
 
+    /* Get first-fit carrier
+     */
+    for (;;) {
+	if (!crr)
+	    return NULL;
+	if (crr->root && crr->root->max_sz >= size)
+	    break;
+	crr = crr->next;
+    }
+
+    /* Get block within carrier tree
+     */
+    x = crr->root;
+#ifdef HARD_DEBUG
+    dbg_blk = check_tree(alc, x, size);
+#endif
+
     while (x) {
 	if (x->left && x->left->max_sz >= size) {
 	    x = x->left;
@@ -718,6 +748,54 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
     return (Block_t *) blk;
 }
 
+static void aoff_creating_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags)
+{
+    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+    AOFF_Carrier_t **prevp = ((flags & ERTS_ALCU_FLG_SBMBC)
+			      ? &alc->sbmbc_first : &alc->mbc_first);
+    AOFF_Carrier_t *p;
+
+
+    /* Link carrier in address order
+     */
+    for (p = *prevp; p && crr > p; p = p->next) {
+	prevp = &p->next;
+    }
+    ASSERT(crr != p);
+
+    crr->next = p;
+    crr->prevp = prevp;
+    *prevp = crr;
+    if (p) {
+	ASSERT(prevp == p->prevp);
+	p->prevp = &crr->next;
+    }
+
+    /* aoff_link_free_block will add free block later */
+    crr->root = NULL;
+}
+
+static void aoff_destroying_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags)
+{
+    AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+    AOFF_Carrier_t **pp = ((flags & ERTS_ALCU_FLG_SBMBC)
+			   ? &alc->sbmbc_first : &alc->mbc_first);
+
+    /* Unlink carrier
+     */
+    while (*pp != crr) {
+	ASSERT(*pp && (*pp)->prevp == pp);
+	pp = &(*pp)->next;
+    }
+    *pp = crr->next;
+    if (crr->next) {
+	ASSERT(crr->next->prevp == &crr->next);
+	crr->next->prevp = crr->prevp;
+    }
+}
+
 
 /*
  * info_options()
@@ -822,7 +900,18 @@ UWord
 erts_aoffalc_test(UWord op, UWord a1, UWord a2)
 {
     switch (op) {
-    case 0x501:	return (UWord) ((AOFFAllctr_t *) a1)->mbc_root;
+    case 0x501: {
+	AOFF_Carrier_t* crr = ((AOFFAllctr_t *) a1)->mbc_first;
+	Uint size = (Uint) a2;
+	for (;;) {
+	    if (!crr)
+		return (UWord)NULL;
+	    if (crr->root && crr->root->max_sz >= size)
+		break;
+	    crr = crr->next;
+	}	
+	return (UWord) crr->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;
@@ -842,6 +931,23 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2)
 
 #ifdef HARD_DEBUG
 
+static void check_carriers(AOFFAllctr_t* alc, AOFF_Carrier_t *crr, Uint32 flags)
+{ 
+    AOFF_Carrier_t *p = ((flags & ERTS_ALCU_FLG_SBMBC)
+			 ? alc->sbmbc_first : alc->mbc_first);
+    int found_it = 0;
+
+    for ( ; p; p = p->next) {
+	if (p == crr) {
+	    ASSERT(!found_it);
+	    found_it = 1;
+	}
+	ASSERT(!p->next || p->next > p);
+    }
+    ASSERT(found_it);
+}
+
+
 #define IS_LEFT_VISITED(FB)	((FB)->flags & LEFT_VISITED_FLG)
 #define IS_RIGHT_VISITED(FB)	((FB)->flags & RIGHT_VISITED_FLG)
 
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.h b/erts/emulator/beam/erl_ao_firstfit_alloc.h
index 36995a20f0..a8fa69ab79 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.h
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.h
@@ -51,8 +51,8 @@ Allctr_t *erts_aoffalc_start(AOFFAllctr_t *, AOFFAllctrInit_t*, AllctrInit_t *);
 struct AOFFAllctr_t_ {
     Allctr_t		allctr; /* Has to be first! */
 
-    struct AOFF_RBTree_t_* mbc_root;
-    struct AOFF_RBTree_t_* sbmbc_root;
+    struct AOFF_Carrier_t_* mbc_first;
+    struct AOFF_Carrier_t_* sbmbc_first;
     int bf_within_carrier;
 };
 
diff --git a/erts/emulator/test/alloc_SUITE_data/allocator_test.h b/erts/emulator/test/alloc_SUITE_data/allocator_test.h
index ec5bb9dcd6..c08398d40f 100644
--- a/erts/emulator/test/alloc_SUITE_data/allocator_test.h
+++ b/erts/emulator/test/alloc_SUITE_data/allocator_test.h
@@ -85,7 +85,7 @@ typedef void* erts_cond;
 
 /* From erl_bestfit_alloc.c and erl_ao_firstfit_alloc.c */
 #define IS_AOBF(A)		((Ulong)	ALC_TEST1(RBT_OP(0), (A)))
-#define RBT_ROOT(A)		((RBT_t *)	ALC_TEST1(RBT_OP(1), (A)))
+#define RBT_ROOT(A,SZ)		((RBT_t *)	ALC_TEST2(RBT_OP(1), (A), (SZ)))
 #define RBT_PARENT(T)		((RBT_t *)	ALC_TEST1(RBT_OP(2), (T)))
 #define RBT_LEFT(T)		((RBT_t *)	ALC_TEST1(RBT_OP(3), (T)))
 #define RBT_RIGHT(T)		((RBT_t *)	ALC_TEST1(RBT_OP(4), (T)))
diff --git a/erts/emulator/test/alloc_SUITE_data/rbtree.c b/erts/emulator/test/alloc_SUITE_data/rbtree.c
index 105c9c0eb4..bdada7ca33 100644
--- a/erts/emulator/test/alloc_SUITE_data/rbtree.c
+++ b/erts/emulator/test/alloc_SUITE_data/rbtree.c
@@ -103,7 +103,7 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 	else type = AOFF;
     }
 
-    root = RBT_ROOT(alc);
+    root = RBT_ROOT(alc, size);
 
 #ifdef PRINT_TREE
     print_tree(tcs, root);
@@ -369,9 +369,9 @@ test_it(TestCaseState_t *tcs)
 	    do_check(tcs, a, 300);
     }
 
-    ASSERT(tcs, RBT_ROOT(a));
-    ASSERT(tcs, !RBT_LEFT(RBT_ROOT(a)));
-    ASSERT(tcs, !RBT_RIGHT(RBT_ROOT(a)));
+    ASSERT(tcs, RBT_ROOT(a,0));
+    ASSERT(tcs, !RBT_LEFT(RBT_ROOT(a,0)));
+    ASSERT(tcs, !RBT_RIGHT(RBT_ROOT(a,0)));
 }