1 files changed, 107 insertions, 22 deletions

diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index 917cb1cf10..c19d6d1b1e 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -107,9 +107,11 @@ 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 */
-    AOFF_RBTree_t* root;        /* Root of my block tree */
+    AOFF_RBTree_t rbt_node;        /* My node in the carrier tree */
+    AOFF_RBTree_t* root;           /* Root of my block tree */
+    enum AOFFSortOrder blk_order;
 };
+
 #define RBT_NODE_TO_MBC(PTR) ErtsContainerStruct((PTR), AOFF_Carrier_t, rbt_node)
 
 /* 
@@ -239,6 +241,9 @@ static void aoff_add_mbc(Allctr_t*, Carrier_t*);
 static void aoff_remove_mbc(Allctr_t*, Carrier_t*);
 static UWord aoff_largest_fblk_in_mbc(Allctr_t*, Carrier_t*);
 
+static Block_t *aoff_first_fblk_in_mbc(Allctr_t *, Carrier_t *);
+static Block_t *aoff_next_fblk_in_mbc(Allctr_t *, Carrier_t *, Block_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 AOFFSortOrder, AOFF_RBTree_t** root, AOFF_RBTree_t* blk);
@@ -281,15 +286,28 @@ erts_aoffalc_start(AOFFAllctr_t *alc,
 
     sys_memcpy((void *) alc, (void *) &zero.allctr, sizeof(AOFFAllctr_t));
 
+    if (aoffinit->blk_order == FF_CHAOS) {
+        const enum AOFFSortOrder orders[3] = {FF_AOFF, FF_AOBF, FF_BF};
+        int index = init->ix % (sizeof(orders) / sizeof(orders[0]));
+
+        ASSERT(init->alloc_no == ERTS_ALC_A_TEST);
+        aoffinit->blk_order = orders[index];
+    }
+
+    if (aoffinit->crr_order == FF_CHAOS) {
+        const enum AOFFSortOrder orders[2] = {FF_AGEFF, FF_AOFF};
+        int index = init->ix % (sizeof(orders) / sizeof(orders[0]));
+
+        ASSERT(init->alloc_no == ERTS_ALC_A_TEST);
+        aoffinit->crr_order = orders[index];
+    }
+
     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->blk_order == FF_BF
-                              ? (offsetof(AOFF_RBTree_t, u.next)
-                                 + ErtsSizeofMember(AOFF_RBTree_t, u.next))
-                              : offsetof(AOFF_RBTree_t, u));
+    allctr->min_block_size              = sizeof(AOFF_RBTree_t);
 
     allctr->vsn_str			= ERTS_ALC_AOFF_ALLOC_VSN_STR;
 
@@ -311,6 +329,8 @@ erts_aoffalc_start(AOFFAllctr_t *alc,
     allctr->add_mbc                     = aoff_add_mbc;
     allctr->remove_mbc                  = aoff_remove_mbc;
     allctr->largest_fblk_in_mbc         = aoff_largest_fblk_in_mbc;
+    allctr->first_fblk_in_mbc           = aoff_first_fblk_in_mbc;
+    allctr->next_fblk_in_mbc            = aoff_next_fblk_in_mbc;
     allctr->init_atoms			= init_atoms;
 
 #ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
@@ -512,14 +532,15 @@ tree_insert_fixup(AOFF_RBTree_t** root, AOFF_RBTree_t *blk)
 static void
 aoff_unlink_free_block(Allctr_t *allctr, Block_t *blk)
 {
-    AOFFAllctr_t* alc = (AOFFAllctr_t*)allctr;
     AOFF_RBTree_t* del = (AOFF_RBTree_t*)blk;
     AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(&del->hdr);
 
+    (void)allctr;
+
     ASSERT(crr->rbt_node.hdr.bhdr == crr->root->max_sz);
-    HARD_CHECK_TREE(&crr->crr, alc->blk_order, crr->root, 0);
+    HARD_CHECK_TREE(&crr->crr, crr->blk_order, crr->root, 0);
 
-    if (alc->blk_order == FF_BF) {
+    if (crr->blk_order == FF_BF) {
 	ASSERT(del->flags & IS_BF_FLG);
 	if (IS_LIST_ELEM(del)) {
 	    /* Remove from list */
@@ -534,20 +555,20 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *blk)
 	}
 	else if (AOFF_LIST_NEXT(del)) {
 	    /* Replace tree node by next element in list... */
-
+	    
 	    ASSERT(AOFF_BLK_SZ(AOFF_LIST_NEXT(del)) == AOFF_BLK_SZ(del));
 	    ASSERT(IS_LIST_ELEM(AOFF_LIST_NEXT(del)));
 
 	    replace(&crr->root, (AOFF_RBTree_t*)del, AOFF_LIST_NEXT(del));
 
-	    HARD_CHECK_TREE(&crr->crr, alc->blk_order, crr->root, 0);
+	    HARD_CHECK_TREE(&crr->crr, crr->blk_order, crr->root, 0);
 	    return;
 	}
     }
 
     rbt_delete(&crr->root, (AOFF_RBTree_t*)del);
 
-    HARD_CHECK_TREE(&crr->crr, alc->blk_order, crr->root, 0);
+    HARD_CHECK_TREE(&crr->crr, crr->blk_order, crr->root, 0);
 
     /* Update the carrier tree with a potentially new (lower) max_sz
      */
@@ -737,17 +758,18 @@ rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del)
 static void
 aoff_link_free_block(Allctr_t *allctr, Block_t *block)
 {
-    AOFFAllctr_t* alc = (AOFFAllctr_t*) allctr;
     AOFF_RBTree_t *blk = (AOFF_RBTree_t *) block;
     AOFF_RBTree_t *crr_node;
     AOFF_Carrier_t *blk_crr = (AOFF_Carrier_t*) FBLK_TO_MBC(block);
     Uint blk_sz = AOFF_BLK_SZ(blk);
 
+    (void)allctr;
+
     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->blk_order, blk_crr->root, 0);
+    HARD_CHECK_TREE(&blk_crr->crr, blk_crr->blk_order, blk_crr->root, 0);
 
-    rbt_insert(alc->blk_order, &blk_crr->root, blk);
+    rbt_insert(blk_crr->blk_order, &blk_crr->root, blk);
 
     /*
      * Update carrier tree with a potentially new (larger) max_sz
@@ -891,7 +913,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->blk_order, crr->root, size);
+    dbg_blk = HARD_CHECK_TREE(&crr->crr, crr->blk_order, crr->root, size);
 #endif
 
     blk = rbt_search(crr->root, size);
@@ -904,7 +926,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
     if (!blk)
 	return NULL;
 
-    if (cand_blk && cmp_cand_blk(alc->blk_order, cand_blk, blk) < 0) {
+    if (cand_blk && cmp_cand_blk(crr->blk_order, cand_blk, blk) < 0) {
 	return NULL; /* cand_blk was better */
     }
 
@@ -927,21 +949,28 @@ 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;
+    Sint64 bt = get_birth_time();
 
     HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
 
     crr->rbt_node.hdr.bhdr = 0;
-    if (alc->crr_order == FF_AGEFF || IS_DEBUG) {
-        Sint64 bt = get_birth_time();
-        crr->rbt_node.u.birth_time = bt;
-        crr->crr.cpool.pooled.u.birth_time = bt;
-    }
+
+    /* While birth time is only used for FF_AGEFF, we have to set it for all
+     * types as we can be migrated to an instance that uses it and we don't
+     * want to mess its order up. */
+    crr->rbt_node.u.birth_time = bt;
+    crr->crr.cpool.pooled.u.birth_time = bt;
+
     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, alc->crr_order, *root, 0);
+
+    /* When a carrier has been migrated, its block order may differ from that
+     * of the allocator it's been migrated to. */
+    crr->blk_order = alc->blk_order;
 }
 
 #define IS_CRR_IN_TREE(CRR,ROOT) \
@@ -1034,6 +1063,62 @@ static UWord aoff_largest_fblk_in_mbc(Allctr_t* allctr, Carrier_t* carrier)
     return crr->rbt_node.hdr.bhdr;
 }
 
+static Block_t *aoff_first_fblk_in_mbc(Allctr_t *allctr, Carrier_t *carrier)
+{
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*)carrier;
+
+    (void)allctr;
+
+    if (crr->root) {
+        AOFF_RBTree_t *blk;
+
+        /* Descend to the rightmost block of the tree. */
+        for (blk = crr->root; blk->right; blk = blk->right);
+
+        return (Block_t*)blk;
+    }
+
+    return NULL;
+}
+
+static Block_t *aoff_next_fblk_in_mbc(Allctr_t *allctr, Carrier_t *carrier,
+                                      Block_t *block)
+{
+    AOFF_RBTree_t *parent, *blk;
+
+    (void)allctr;
+    (void)carrier;
+
+    blk = (AOFF_RBTree_t*)block;
+
+    if (blk->left) {
+        /* Descend to the rightmost block of the left subtree. */
+        for (blk = blk->left; blk->right; blk = blk->right);
+
+        return (Block_t*)blk;
+    }
+
+    while (blk->parent) {
+        parent = blk->parent;
+
+        /* If we ascend from the right we know we haven't visited our parent
+         * yet, because we always descend as far as we can to the right when
+         * entering a subtree. */
+        if (parent->right == blk) {
+            ASSERT(parent->left != blk);
+            return (Block_t*)parent;
+        }
+
+        /* If we ascend from the left we know we've already visited our
+         * parent, and will need to keep ascending until we do so from the
+         * right or reach the end of the tree. */
+        ASSERT(parent->left == blk);
+        blk = parent;
+    }
+
+    return NULL;
+}
+
 /*
  * info_options()
  */