erts: Improve carrier pool search

* Give back carrier to owner when put in pool with use of dd-queue.
* Replace pooled_list with pooled_tree for more efficient search
  of all owned pooled carriers.
* Remove traitor_list as it does not serve much purpose anymore.
* Add HOMECOMING bit flag in crr->allctr atomic to
  (1) avoid double enqueue into dd-enqueue.
  (2) trigger read barrier in get_used_allctr for newly received carriers.

4 files changed, 464 insertions, 361 deletions

diff --git a/erts/emulator/beam/erl_alloc_util.c b/erts/emulator/beam/erl_alloc_util.c
index f0597e778a..dbf27f1d2f 100644
--- a/erts/emulator/beam/erl_alloc_util.c
+++ b/erts/emulator/beam/erl_alloc_util.c
@@ -375,8 +375,10 @@ do {										\
 
 #define ERTS_CRR_ALCTR_FLG_IN_POOL	(((erts_aint_t) 1) << 0)
 #define ERTS_CRR_ALCTR_FLG_BUSY		(((erts_aint_t) 1) << 1)
+#define ERTS_CRR_ALCTR_FLG_HOMECOMING	(((erts_aint_t) 1) << 2)
 #define ERTS_CRR_ALCTR_FLG_MASK (ERTS_CRR_ALCTR_FLG_IN_POOL | \
-                                 ERTS_CRR_ALCTR_FLG_BUSY)
+                                 ERTS_CRR_ALCTR_FLG_BUSY |    \
+                                 ERTS_CRR_ALCTR_FLG_HOMECOMING)
 
 #ifdef ERTS_SMP
 #define SBC_HEADER_SIZE	   						\
@@ -583,7 +585,7 @@ do {									\
     DEBUG_CHECK_CARRIER_NO_SZ((AP));					\
 } while (0)
 
-#define STAT_MBC_CPOOL_INSERT(AP, CRR)					\
+#define STAT_MBC_ABANDON(AP, CRR)					\
 do {									\
     UWord csz__ = CARRIER_SZ((CRR));					\
     if (IS_MSEG_CARRIER((CRR)))						\
@@ -1143,90 +1145,25 @@ unlink_carrier(CarrierList_t *cl, Carrier_t *crr)
 	ASSERT(crr->next);
 	crr->next->prev = crr->prev;
     }
-}
-
-#ifdef ERTS_SMP
-
 #ifdef DEBUG
-static int is_in_list(ErtsDoubleLink_t* sentinel, ErtsDoubleLink_t* node)
-{
-    ErtsDoubleLink_t* p;
-
-    ASSERT(node != sentinel);
-    for (p = sentinel->next; p != sentinel; p = p->next) {
-	if (p == node)
-	    return 1;
-    }
-    return 0;
-}
-#endif /* DEBUG */
-
-static ERTS_INLINE void
-link_edl_after(ErtsDoubleLink_t* after_me, ErtsDoubleLink_t* node)
-{
-    ErtsDoubleLink_t* before_me = after_me->next;
-    ASSERT(node != after_me && node != before_me);
-    node->next = before_me;
-    node->prev = after_me;
-    before_me->prev = node;
-    after_me->next = node;
-}
-
-static ERTS_INLINE void
-link_edl_before(ErtsDoubleLink_t* before_me, ErtsDoubleLink_t* node)
-{
-    ErtsDoubleLink_t* after_me = before_me->prev;
-    ASSERT(node != before_me && node != after_me);
-    node->next = before_me;
-    node->prev = after_me;
-    before_me->prev = node;
-    after_me->next = node;
-}
-
-static ERTS_INLINE void
-unlink_edl(ErtsDoubleLink_t* node)
-{
-    node->next->prev = node->prev;
-    node->prev->next = node->next;
+    crr->next = crr;
+    crr->prev = crr;
+#endif
 }
 
-static ERTS_INLINE void
-relink_edl_before(ErtsDoubleLink_t* before_me, ErtsDoubleLink_t* node)
-{
-    if (node != before_me && node != before_me->prev) {
-	unlink_edl(node);
-	link_edl_before(before_me, node);
-    }
-}
+#ifdef ERTS_SMP
 
 static ERTS_INLINE int is_abandoned(Carrier_t *crr)
 {
-    return crr->cpool.abandoned.next != NULL;
-}
-
-static ERTS_INLINE void
-link_abandoned_carrier(ErtsDoubleLink_t* list, Carrier_t *crr)
-{
-    ASSERT(!is_abandoned(crr));
-
-    link_edl_after(list, &crr->cpool.abandoned);
-
-    ASSERT(crr->cpool.abandoned.next != &crr->cpool.abandoned);
-    ASSERT(crr->cpool.abandoned.prev != &crr->cpool.abandoned);
+    return crr->cpool.state != ERTS_MBC_IS_HOME;
 }
 
 static ERTS_INLINE void
 unlink_abandoned_carrier(Carrier_t *crr)
 {
-    ASSERT(is_in_list(&crr->cpool.orig_allctr->cpool.pooled_list,
-		      &crr->cpool.abandoned) ||
-	   is_in_list(&crr->cpool.orig_allctr->cpool.traitor_list,
-		      &crr->cpool.abandoned));
-
-    unlink_edl(&crr->cpool.abandoned);
-
-    crr->cpool.abandoned.next = NULL;
-    crr->cpool.abandoned.prev = NULL;
+    if (crr->cpool.state == ERTS_MBC_WAS_POOLED) {
+        aoff_remove_pooled_mbc(crr->cpool.orig_allctr, crr);
+    }
 }
 
 static ERTS_INLINE void
@@ -1234,24 +1171,19 @@ clear_busy_pool_carrier(Allctr_t *allctr, Carrier_t *crr)
 {
     if (crr) {
 	erts_aint_t max_size;
-	erts_aint_t new_val;
+	erts_aint_t iallctr;
 
 	max_size = (erts_aint_t) allctr->largest_fblk_in_mbc(allctr, crr);
 	erts_atomic_set_nob(&crr->cpool.max_size, max_size);
 
-	new_val = (((erts_aint_t) allctr)|ERTS_CRR_ALCTR_FLG_IN_POOL);
-
-#ifdef ERTS_ALC_CPOOL_DEBUG
-	{
-	    erts_aint_t old_val = new_val|ERTS_CRR_ALCTR_FLG_BUSY;
+        iallctr = erts_smp_atomic_read_nob(&crr->allctr);
+        ERTS_ALC_CPOOL_ASSERT((iallctr & ~ERTS_CRR_ALCTR_FLG_HOMECOMING)
+                              == ((erts_aint_t)allctr |
+                                  ERTS_CRR_ALCTR_FLG_IN_POOL |
+                                  ERTS_CRR_ALCTR_FLG_BUSY));
 
-	    ERTS_ALC_CPOOL_ASSERT(old_val
-				  == erts_smp_atomic_xchg_relb(&crr->allctr,
-							       new_val));
-	}
-#else
-	erts_smp_atomic_set_relb(&crr->allctr, new_val);
-#endif
+	iallctr &= ~ERTS_CRR_ALCTR_FLG_BUSY;
+	erts_smp_atomic_set_relb(&crr->allctr, iallctr);
     }
 }
 
@@ -1667,6 +1599,11 @@ dealloc_mbc(Allctr_t *allctr, Carrier_t *crr)
 
 #ifdef ERTS_SMP
 
+static void set_new_allctr_abandon_limit(Allctr_t*);
+static void abandon_carrier(Allctr_t*, Carrier_t*);
+static void poolify_my_carrier(Allctr_t*, Carrier_t*);
+static void enqueue_homecoming(Allctr_t*, Carrier_t*);
+
 static ERTS_INLINE Allctr_t*
 get_pref_allctr(void *extra)
 {
@@ -1733,9 +1670,23 @@ get_used_allctr(Allctr_t *pref_allctr, int pref_lock, void *p, UWord *sizep,
 		erts_aint_t act;
 
 		ERTS_ALC_CPOOL_ASSERT(!(iallctr & ERTS_CRR_ALCTR_FLG_BUSY));
-		act = erts_smp_atomic_cmpxchg_ddrb(&crr->allctr,
-						   iallctr|ERTS_CRR_ALCTR_FLG_BUSY,
-						   iallctr);
+                if (iallctr & ERTS_CRR_ALCTR_FLG_HOMECOMING) {
+                    /*
+                     * This carrier has just been given back to us by writing
+                     * to crr->allctr with a write barrier (see abandon_carrier).
+                     *
+                     * We need a mathing read barrier to guarantee a correct view
+                     * of the carrier for deallocation work.
+                     */
+                    act = erts_smp_atomic_cmpxchg_rb(&crr->allctr,
+                                                     iallctr|ERTS_CRR_ALCTR_FLG_BUSY,
+                                                     iallctr);
+                }
+                else {
+                    act = erts_smp_atomic_cmpxchg_ddrb(&crr->allctr,
+                                                       iallctr|ERTS_CRR_ALCTR_FLG_BUSY,
+                                                       iallctr);
+                }
 		if (act == iallctr) {
 		    *busy_pcrr_pp = crr;
 		    break;
@@ -1751,13 +1702,6 @@ get_used_allctr(Allctr_t *pref_allctr, int pref_lock, void *p, UWord *sizep,
 		    erts_mtx_unlock(&pref_allctr->mutex);
 		}
 	    }
-
-	    ERTS_ALC_CPOOL_ASSERT(
-		(((iallctr & ~ERTS_CRR_ALCTR_FLG_MASK) == (erts_aint_t) pref_allctr)
-		 ? (((iallctr & ERTS_CRR_ALCTR_FLG_MASK) == ERTS_CRR_ALCTR_FLG_IN_POOL)
-		    || ((iallctr & ERTS_CRR_ALCTR_FLG_MASK) == 0))
-		 : 1));
-
 	    return used_allctr;
 	}
     }
@@ -2009,9 +1953,9 @@ handle_delayed_fix_dealloc(Allctr_t *allctr, void *ptr)
 	    /* Carrier migrated; need to redirect block to new owner... */
 	    int cinit = used_allctr->dd.ix - allctr->dd.ix;
 
-	    ERTS_ALC_CPOOL_ASSERT(!busy_pcrr_p);
+            ERTS_ALC_CPOOL_ASSERT(!busy_pcrr_p);
 
-	    DEC_CC(allctr->calls.this_free);
+            DEC_CC(allctr->calls.this_free);
 
 	    ((ErtsAllctrFixDDBlock_t *) ptr)->fix_type = type;
 	    if (ddq_enqueue(&used_allctr->dd.q, ptr, cinit))
@@ -2020,8 +1964,9 @@ handle_delayed_fix_dealloc(Allctr_t *allctr, void *ptr)
     }
 }
 
-static void
-schedule_dealloc_carrier(Allctr_t *allctr, Carrier_t *crr);
+static void schedule_dealloc_carrier(Allctr_t*, Carrier_t*);
+static void dealloc_my_carrier(Allctr_t*, Carrier_t*);
+
 
 static ERTS_INLINE int
 handle_delayed_dealloc(Allctr_t *allctr,
@@ -2086,24 +2031,58 @@ handle_delayed_dealloc(Allctr_t *allctr,
 	if (blk->bhdr == HOMECOMING_MBC_BLK_HDR) {
 	    /*
 	     * A multiblock carrier that previously has been migrated away
-	     * from us and now is back to be deallocated. For more info
-	     * see schedule_dealloc_carrier().
+             * from us, was sent back to us either because
+             * - it became empty and we need to deallocated it, or
+             * - it was inserted into the pool and we need to update our pooled_tree
 	     */
 	    Carrier_t *crr = ErtsContainerStruct(blk, Carrier_t,
                                                  cpool.homecoming_dd.blk);
+            Block_t* first_blk = MBC_TO_FIRST_BLK(allctr, crr);
+            erts_aint_t iallctr;
 
 	    ERTS_ALC_CPOOL_ASSERT(ERTS_ALC_IS_CPOOL_ENABLED(allctr));
 	    ERTS_ALC_CPOOL_ASSERT(allctr == crr->cpool.orig_allctr);
-	    ERTS_ALC_CPOOL_ASSERT(((erts_aint_t) allctr)
-				  != (erts_smp_atomic_read_nob(&crr->allctr)
-				      & ~ERTS_CRR_ALCTR_FLG_MASK));
 
-	    erts_smp_atomic_set_nob(&crr->allctr, ((erts_aint_t) allctr));
-
-	    schedule_dealloc_carrier(allctr, crr);
+            iallctr = erts_smp_atomic_read_nob(&crr->allctr);
+            ASSERT(iallctr & ERTS_CRR_ALCTR_FLG_HOMECOMING);
+            while (1) {
+                if ((iallctr & (~ERTS_CRR_ALCTR_FLG_MASK |
+                                ERTS_CRR_ALCTR_FLG_IN_POOL))
+                    == (erts_aint_t)allctr) {
+                    /*
+                     * Carrier is home (mine and not in pool)
+                     */
+                    ASSERT(!(iallctr & ERTS_CRR_ALCTR_FLG_BUSY));
+                    erts_smp_atomic_set_nob(&crr->allctr, (erts_aint_t)allctr);
+                    if (IS_FREE_LAST_MBC_BLK(first_blk))
+                        dealloc_my_carrier(allctr, crr);
+                    else
+                        ASSERT(crr->cpool.state == ERTS_MBC_IS_HOME);
+                }
+                else {
+                    erts_aint_t exp = iallctr;
+                    erts_aint_t want = iallctr & ~ERTS_CRR_ALCTR_FLG_HOMECOMING;
+
+                    iallctr = erts_smp_atomic_cmpxchg_nob(&crr->allctr,
+                                                          want,
+                                                          exp);
+                    if (iallctr != exp)
+                        continue; /* retry */
+
+                    ASSERT(crr->cpool.state != ERTS_MBC_IS_HOME);
+                    unlink_abandoned_carrier(crr);
+                    if (iallctr & ERTS_CRR_ALCTR_FLG_IN_POOL)
+                        poolify_my_carrier(allctr, crr);
+                    else
+                        crr->cpool.state = ERTS_MBC_WAS_TRAITOR;
+                }
+                break;
+            }
 	}
 	else {
-            ASSERT(IS_SBC_BLK(blk) || !IS_FREE_BLK(blk));
+            ASSERT(IS_SBC_BLK(blk) || (ABLK_TO_MBC(blk) !=
+                                       ErtsContainerStruct(blk, Carrier_t,
+                                                           cpool.homecoming_dd.blk)));
 
 	    INC_CC(allctr->calls.this_free);
 
@@ -2145,23 +2124,26 @@ enqueue_dealloc_other_instance(ErtsAlcType_t type,
 	erts_alloc_notify_delayed_dealloc(allctr->ix);
 }
 
-#endif
-
-#ifdef ERTS_SMP
-static void
-set_new_allctr_abandon_limit(Allctr_t *allctr);
-static void
-abandon_carrier(Allctr_t *allctr, Carrier_t *crr);
-
+static ERTS_INLINE void
+update_pooled_tree(Allctr_t *allctr, Carrier_t *crr, Uint blk_sz)
+{
+    if (allctr == crr->cpool.orig_allctr && crr->cpool.state == ERTS_MBC_WAS_POOLED) {
+	/*
+	 * Update pooled_tree with a potentially new (larger) max_sz
+         */
+        AOFF_RBTree_t* crr_node = &crr->cpool.pooled;
+        if (blk_sz > crr_node->hdr.bhdr) {
+            crr_node->hdr.bhdr = blk_sz;
+            erts_aoff_larger_max_size(crr_node);
+        }
+    }
+}
 
 static ERTS_INLINE void
 check_abandon_carrier(Allctr_t *allctr, Block_t *fblk, Carrier_t **busy_pcrr_pp)
 {
     Carrier_t *crr;
 
-    if (busy_pcrr_pp && *busy_pcrr_pp)
-	return;
-
     if (!ERTS_ALC_IS_CPOOL_ENABLED(allctr))
 	return;
 
@@ -2243,6 +2225,7 @@ dealloc_block(Allctr_t *allctr, void *ptr, ErtsAlcFixList_t *fix, int dec_cc_on_
     else {
 	Carrier_t *busy_pcrr_p;
 	Allctr_t *used_allctr;
+
 	used_allctr = get_used_allctr(allctr, ERTS_ALC_TS_PREF_LOCK_NO, ptr,
 				      NULL, &busy_pcrr_p);
 	if (used_allctr == allctr) {
@@ -2259,10 +2242,10 @@ dealloc_block(Allctr_t *allctr, void *ptr, ErtsAlcFixList_t *fix, int dec_cc_on_
 	    /* Carrier migrated; need to redirect block to new owner... */
 	    int cinit = used_allctr->dd.ix - allctr->dd.ix;
 
-	    ERTS_ALC_CPOOL_ASSERT(!busy_pcrr_p);
+            ERTS_ALC_CPOOL_ASSERT(!busy_pcrr_p);
 
-	    if (dec_cc_on_redirect)
-		DEC_CC(allctr->calls.this_free);
+            if (dec_cc_on_redirect)
+                DEC_CC(allctr->calls.this_free);
 	    if (ddq_enqueue(&used_allctr->dd.q, ptr, cinit))
 		erts_alloc_notify_delayed_dealloc(used_allctr->ix);
 	}
@@ -2507,16 +2490,17 @@ mbc_free(Allctr_t *allctr, void *p, Carrier_t **busy_pcrr_pp)
     ASSERT(blk_sz % sizeof(Unit_t) == 0);
     ASSERT(IS_MBC_BLK(blk));
 
-    if (is_first_blk
-	&& is_last_blk
-	&& allctr->main_carrier != FIRST_BLK_TO_MBC(allctr, blk)) {
-	destroy_carrier(allctr, blk, busy_pcrr_pp);
+    if (is_first_blk && is_last_blk && crr != allctr->main_carrier) {
+        destroy_carrier(allctr, blk, busy_pcrr_pp);
     }
     else {
 	(*allctr->link_free_block)(allctr, blk);
 	HARD_CHECK_BLK_CARRIER(allctr, blk);
 #ifdef ERTS_SMP
-	check_abandon_carrier(allctr, blk, busy_pcrr_pp);
+        if (busy_pcrr_pp && *busy_pcrr_pp)
+            update_pooled_tree(allctr, crr, blk_sz);
+        else
+            check_abandon_carrier(allctr, blk, busy_pcrr_pp);
 #endif
     }
 }
@@ -2552,8 +2536,19 @@ mbc_realloc(Allctr_t *allctr, void *p, Uint size, Uint32 alcu_flgs,
 #else /* !MBC_REALLOC_ALWAYS_MOVES */
 
 #ifdef ERTS_SMP
-    if (busy_pcrr_pp && *busy_pcrr_pp)
-	goto realloc_move; /* Don't want to use carrier in pool */
+    if (busy_pcrr_pp && *busy_pcrr_pp) {
+        /*
+         * Don't want to use carrier in pool
+         */
+        new_p = mbc_alloc(allctr, size);
+        if (!new_p)
+            return NULL;
+        new_blk = UMEM2BLK(new_p);
+        ASSERT(!(IS_MBC_BLK(new_blk) && ABLK_TO_MBC(new_blk) == *busy_pcrr_pp));
+        sys_memcpy(new_p, p, MIN(size, old_blk_sz - ABLK_HDR_SZ));
+        mbc_free(allctr, p, busy_pcrr_pp);
+        return new_p;
+    }
 #endif
 
     get_blk_sz = blk_sz = UMEMSZ2BLKSZ(allctr, size);
@@ -2789,9 +2784,7 @@ mbc_realloc(Allctr_t *allctr, void *p, Uint size, Uint32 alcu_flgs,
 
     if (cand_blk_sz < get_blk_sz) {
 	/* We wont fit in cand_blk get a new one */
-#ifdef ERTS_SMP
-    realloc_move:
-#endif
+
 #endif /* !MBC_REALLOC_ALWAYS_MOVES */
 
 	new_p = mbc_alloc(allctr, size);
@@ -2896,8 +2889,7 @@ mbc_realloc(Allctr_t *allctr, void *p, Uint size, Uint32 alcu_flgs,
 #ifdef ERTS_SMP
 
 #define ERTS_ALC_MAX_DEALLOC_CARRIER		10
-#define ERTS_ALC_CPOOL_MAX_FETCH_INSPECT	20
-#define ERTS_ALC_CPOOL_MAX_TRAITOR_INSPECT	10
+#define ERTS_ALC_CPOOL_MAX_FETCH_INSPECT	100
 #define ERTS_ALC_CPOOL_CHECK_LIMIT_COUNT	100
 #define ERTS_ALC_CPOOL_MAX_FAILED_STAT_READS	3
 
@@ -3061,19 +3053,18 @@ cpool_insert(Allctr_t *allctr, Carrier_t *crr)
     ErtsAlcCPoolData_t *cpd1p, *cpd2p;
     erts_aint_t val;
     ErtsAlcCPoolData_t *sentinel = &carrier_pool[allctr->alloc_no].sentinel;
+    Allctr_t *orig_allctr = crr->cpool.orig_allctr;
 
     ERTS_ALC_CPOOL_ASSERT(allctr->alloc_no == ERTS_ALC_A_INVALID /* testcase */
 			  || erts_thr_progress_is_managed_thread());
-    ERTS_ALC_CPOOL_ASSERT(erts_smp_atomic_read_nob(&crr->allctr)
-			  == (erts_aint_t) allctr);
 
-    erts_atomic_add_nob(&allctr->cpool.stat.blocks_size,
+    erts_atomic_add_nob(&orig_allctr->cpool.stat.blocks_size,
 			(erts_aint_t) crr->cpool.blocks_size);
-    erts_atomic_add_nob(&allctr->cpool.stat.no_blocks,
+    erts_atomic_add_nob(&orig_allctr->cpool.stat.no_blocks,
 			(erts_aint_t) crr->cpool.blocks);
-    erts_atomic_add_nob(&allctr->cpool.stat.carriers_size,
+    erts_atomic_add_nob(&orig_allctr->cpool.stat.carriers_size,
 			(erts_aint_t) CARRIER_SZ(crr));
-    erts_atomic_inc_nob(&allctr->cpool.stat.no_carriers);
+    erts_atomic_inc_nob(&orig_allctr->cpool.stat.no_carriers);
 
     /*
      * We search in 'next' direction and begin by passing
@@ -3134,8 +3125,6 @@ cpool_insert(Allctr_t *allctr, Carrier_t *crr)
 			 (erts_aint_t) &crr->cpool,
 			 (erts_aint_t) cpd1p);
 
-    erts_smp_atomic_set_wb(&crr->allctr,
-			   ((erts_aint_t) allctr)|ERTS_CRR_ALCTR_FLG_IN_POOL);
     LTTNG3(carrier_pool_put, ERTS_ALC_A2AD(allctr->alloc_no), allctr->ix, CARRIER_SZ(crr));
 }
 
@@ -3237,130 +3226,119 @@ cpool_delete(Allctr_t *allctr, Allctr_t *prev_allctr, Carrier_t *crr)
 static Carrier_t *
 cpool_fetch(Allctr_t *allctr, UWord size)
 {
-    int i, i_stop, has_passed_sentinel;
+    enum { IGNORANT, HAS_SEEN_SENTINEL, THE_LAST_ONE } loop_state;
+    int i;
     Carrier_t *crr;
+    Carrier_t *reinsert_crr = NULL;
     ErtsAlcCPoolData_t *cpdp;
-    ErtsAlcCPoolData_t *cpool_entrance;
+    ErtsAlcCPoolData_t *cpool_entrance = NULL;
     ErtsAlcCPoolData_t *sentinel;
-    ErtsDoubleLink_t* dl;
-    ErtsDoubleLink_t* first_old_traitor;
 
     ERTS_ALC_CPOOL_ASSERT(allctr->alloc_no == ERTS_ALC_A_INVALID /* testcase */
 			  || erts_thr_progress_is_managed_thread());
 
     i = ERTS_ALC_CPOOL_MAX_FETCH_INSPECT;
-    first_old_traitor = allctr->cpool.traitor_list.next;
-    cpool_entrance = NULL;
 
     LTTNG3(carrier_pool_get, ERTS_ALC_A2AD(allctr->alloc_no), allctr->ix, (unsigned long)size);
     /*
-     * Search my own pooled_list,
+     * Search my own pooled_tree,
      * i.e my abandoned carriers that were in the pool last time I checked.
      */
+    do {
+        erts_aint_t exp, act;
+
+        crr = aoff_lookup_pooled_mbc(allctr, size);
+        if (!crr)
+            break;
+
+        ASSERT(crr->cpool.state == ERTS_MBC_WAS_POOLED);
+        ASSERT(crr->cpool.orig_allctr == allctr);
+
+        aoff_remove_pooled_mbc(allctr, crr);
+
+        exp = erts_smp_atomic_read_nob(&crr->allctr);
+        if (exp & ERTS_CRR_ALCTR_FLG_IN_POOL) {
+            ASSERT((exp & ~ERTS_CRR_ALCTR_FLG_MASK) == (erts_aint_t)allctr);
+            if (erts_atomic_read_nob(&crr->cpool.max_size) < size) {
+                /*
+                 * This carrier has been fetched and inserted back again
+                 * by a foreign allocator. That's why it has a stale search size.
+                 */
+                ASSERT(exp & ERTS_CRR_ALCTR_FLG_HOMECOMING);
+                crr->cpool.pooled.hdr.bhdr = erts_atomic_read_nob(&crr->cpool.max_size);
+                aoff_add_pooled_mbc(allctr, crr);
+                continue;
+            }
+            else if (exp & ERTS_CRR_ALCTR_FLG_BUSY) {
+                /*
+                 * This must be our own carrier as part of a realloc call.
+                 * Skip it to make things simpler.
+                 * Must wait to re-insert to not be found again by lookup.
+                 */
+                ASSERT(!reinsert_crr);
+                reinsert_crr = crr;
+                continue;
+            }
+
+            /* Try to fetch it... */
+            act = erts_smp_atomic_cmpxchg_mb(&crr->allctr,
+                                             exp & ~ERTS_CRR_ALCTR_FLG_IN_POOL,
+                                             exp);
+            if (act == exp) {
+                cpool_delete(allctr, allctr, crr);
+                crr->cpool.state = ERTS_MBC_IS_HOME;
+
+                if (reinsert_crr)
+                    aoff_add_pooled_mbc(allctr, reinsert_crr);
+                return crr;
+            }
+            exp = act;
+        }
 
-    dl = allctr->cpool.pooled_list.next;
-    while(dl != &allctr->cpool.pooled_list) {
-	erts_aint_t exp, act;
-	crr = (Carrier_t *) (((char *) dl) - offsetof(Carrier_t, cpool.abandoned));
+        /* Not in pool anymore */
+        ASSERT(!(exp & ERTS_CRR_ALCTR_FLG_BUSY));
+        crr->cpool.state = ERTS_MBC_WAS_TRAITOR;
 
-	ASSERT(!is_in_list(&allctr->cpool.traitor_list, dl));
-	ASSERT(crr->cpool.orig_allctr == allctr);
-	dl = dl->next;
-	exp = erts_smp_atomic_read_rb(&crr->allctr);
-	if ((exp & ERTS_CRR_ALCTR_FLG_MASK) == ERTS_CRR_ALCTR_FLG_IN_POOL
-	    && erts_atomic_read_nob(&crr->cpool.max_size) >= size) {
-	    /* Try to fetch it... */
-	    act = erts_smp_atomic_cmpxchg_mb(&crr->allctr,
-					     (erts_aint_t) allctr,
-					     exp);
-	    if (act == exp) {
-		cpool_delete(allctr, ((Allctr_t *) (act & ~ERTS_CRR_ALCTR_FLG_MASK)), crr);
-		unlink_abandoned_carrier(crr);
+    }while (--i > 0);
 
-		/* Move sentinel to continue next search from here */
-		relink_edl_before(dl, &allctr->cpool.pooled_list);
-		return crr;
-	    }
-	    exp = act;
-	}
-	if (exp & ERTS_CRR_ALCTR_FLG_IN_POOL) {
-	    if (!cpool_entrance)
-		cpool_entrance = &crr->cpool;
-	}
-	else { /* Not in pool, move to traitor_list */
-	    unlink_abandoned_carrier(crr);
-	    link_abandoned_carrier(&allctr->cpool.traitor_list, crr);
-	}
-	if (--i <= 0) {
-	    /* Move sentinel to continue next search from here */
-	    relink_edl_before(dl, &allctr->cpool.pooled_list);
-	    return NULL;
-	}
-    }
+    if (reinsert_crr)
+        aoff_add_pooled_mbc(allctr, reinsert_crr);
 
-    /* Now search traitor_list.
-     * i.e carriers employed by other allocators last time I checked.
-     * They might have been abandoned since then.
+    /*
+     * Try find a nice cpool_entrance
      */
+    while (allctr->cpool.pooled_tree) {
+        erts_aint_t iallctr;
+
+        crr = ErtsContainerStruct(allctr->cpool.pooled_tree, Carrier_t, cpool.pooled);
+        iallctr = erts_smp_atomic_read_nob(&crr->allctr);
+        if (iallctr & ERTS_CRR_ALCTR_FLG_IN_POOL) {
+            cpool_entrance = &crr->cpool;
+            break;
+        }
+        /* Not in pool anymore */
+        ASSERT(!(iallctr & ERTS_CRR_ALCTR_FLG_BUSY));
+        aoff_remove_pooled_mbc(allctr, crr);
+        crr->cpool.state = ERTS_MBC_WAS_TRAITOR;
 
-    i_stop = (i < ERTS_ALC_CPOOL_MAX_TRAITOR_INSPECT ?
-	      0 : i - ERTS_ALC_CPOOL_MAX_TRAITOR_INSPECT);
-    dl = first_old_traitor;
-    while(dl != &allctr->cpool.traitor_list) {
-	erts_aint_t exp, act;
-	crr = (Carrier_t *) (((char *) dl) - offsetof(Carrier_t, cpool.abandoned));
-	ASSERT(dl != &allctr->cpool.pooled_list);
-	ASSERT(crr->cpool.orig_allctr == allctr);
-	dl = dl->next;
-	exp = erts_smp_atomic_read_rb(&crr->allctr);
-	if (exp & ERTS_CRR_ALCTR_FLG_IN_POOL) {
-	    if (!(exp & ERTS_CRR_ALCTR_FLG_BUSY)
-		&& erts_atomic_read_nob(&crr->cpool.max_size) >= size) {
-		/* Try to fetch it... */
-		act = erts_smp_atomic_cmpxchg_mb(&crr->allctr,
-						 (erts_aint_t) allctr,
-						 exp);
-		if (act == exp) {
-		    cpool_delete(allctr, ((Allctr_t *) (act & ~ERTS_CRR_ALCTR_FLG_MASK)), crr);
-		    unlink_abandoned_carrier(crr);
-
-		    /* Move sentinel to continue next search from here */
-		    relink_edl_before(dl, &allctr->cpool.traitor_list);
-		    return crr;
-		}
-		exp = act;
-	    }
-	    if (exp & ERTS_CRR_ALCTR_FLG_IN_POOL) {
-		if (!cpool_entrance)
-		    cpool_entrance = &crr->cpool;
-
-		/* Move to pooled_list */
-		unlink_abandoned_carrier(crr);
-		link_abandoned_carrier(&allctr->cpool.pooled_list, crr);
-	    }
-	}
-	if (--i <= i_stop) {
-	    /* Move sentinel to continue next search from here */
-	    relink_edl_before(dl, &allctr->cpool.traitor_list);
-	    if (i > 0)
-		break;
-	    else
-		return NULL;
-	}
+        if (--i <= 0)
+            return NULL;
     }
 
+
     /*
      * Finally search the shared pool and try employ foreign carriers
      */
-
     sentinel = &carrier_pool[allctr->alloc_no].sentinel;
     if (cpool_entrance) {
-	/* We saw a pooled carried above, use it as entrance into the pool
+        /*
+         * We saw a pooled carried above, use it as entrance into the pool
 	 */
 	cpdp = cpool_entrance;
     }
     else {
-	/* No pooled carried seen above. Start search at cpool sentinel,
+        /*
+         * No pooled carried seen above. Start search at cpool sentinel,
 	 * but begin by passing one element before trying to fetch.
 	 * This in order to avoid contention with threads inserting elements.
 	 */
@@ -3370,8 +3348,8 @@ cpool_fetch(Allctr_t *allctr, UWord size)
 	    goto check_dc_list;
     }
 
-    has_passed_sentinel = 0;
-    while (1) {
+    loop_state = IGNORANT;
+    do {
 	erts_aint_t exp;
 	cpdp = cpool_aint2cpd(cpool_read(&cpdp->prev));
 	if (cpdp == cpool_entrance) {
@@ -3380,38 +3358,41 @@ cpool_fetch(Allctr_t *allctr, UWord size)
 		if (cpdp == sentinel)
 		    break;
 	    }
-	    i = 0; /* Last one to inspect */
+            loop_state = THE_LAST_ONE;
 	}
 	else if (cpdp == sentinel) {
-	    if (has_passed_sentinel) {
+	    if (loop_state == HAS_SEEN_SENTINEL) {
 		/* We been here before. cpool_entrance must have been removed */
 		break;
 	    }
 	    cpdp = cpool_aint2cpd(cpool_read(&cpdp->prev));
 	    if (cpdp == sentinel)
                 break;
-	    has_passed_sentinel = 1;
+            loop_state = HAS_SEEN_SENTINEL;
 	}
-	crr = (Carrier_t *)(((char *)cpdp) - offsetof(Carrier_t, cpool));
+	crr = ErtsContainerStruct(cpdp, Carrier_t, cpool);
 	exp = erts_smp_atomic_read_rb(&crr->allctr);
-	if (((exp & (ERTS_CRR_ALCTR_FLG_MASK)) == ERTS_CRR_ALCTR_FLG_IN_POOL)
-	    && (erts_atomic_read_nob(&cpdp->max_size) >= size)) {
+	if (((exp & (ERTS_CRR_ALCTR_FLG_IN_POOL |
+                     ERTS_CRR_ALCTR_FLG_BUSY)) == ERTS_CRR_ALCTR_FLG_IN_POOL)
+            && (erts_atomic_read_nob(&cpdp->max_size) >= size)) {
 	    erts_aint_t act;
-	    /* Try to fetch it... */
-	    act = erts_smp_atomic_cmpxchg_mb(&crr->allctr,
-					     (erts_aint_t) allctr,
-					     exp);
+            erts_aint_t want = (((erts_aint_t) allctr)
+                                | (exp & ERTS_CRR_ALCTR_FLG_HOMECOMING));
+            /* Try to fetch it... */
+	    act = erts_smp_atomic_cmpxchg_mb(&crr->allctr, want, exp);
 	    if (act == exp) {
 		cpool_delete(allctr, ((Allctr_t *) (act & ~ERTS_CRR_ALCTR_FLG_MASK)), crr);
 		if (crr->cpool.orig_allctr == allctr) {
 		    unlink_abandoned_carrier(crr);
-		}
+                    crr->cpool.state = ERTS_MBC_IS_HOME;
+                }
 		return crr;
 	    }
 	}
+
 	if (--i <= 0)
 	    return NULL;
-    }
+    }while (loop_state != THE_LAST_ONE);
 
 check_dc_list:
     /* Last; check our own pending dealloc carrier list... */
@@ -3420,13 +3401,8 @@ check_dc_list:
 	if (erts_atomic_read_nob(&crr->cpool.max_size) >= size) {
 	    Block_t* blk;
 	    unlink_carrier(&allctr->cpool.dc_list, crr);
-#ifdef ERTS_ALC_CPOOL_DEBUG
-	    ERTS_ALC_CPOOL_ASSERT(erts_smp_atomic_xchg_nob(&crr->allctr,
-							   ((erts_aint_t) allctr))
-				  == (((erts_aint_t) allctr) & ~ERTS_CRR_ALCTR_FLG_MASK));
-#else
-	    erts_smp_atomic_set_nob(&crr->allctr, ((erts_aint_t) allctr));
-#endif
+	    ERTS_ALC_CPOOL_ASSERT(erts_smp_atomic_read_nob(&crr->allctr)
+                                  == ((erts_aint_t) allctr));
 	    blk = MBC_TO_FIRST_BLK(allctr, crr);
 	    ASSERT(FBLK_TO_MBC(blk) == crr);
 	    allctr->link_free_block(allctr, blk);
@@ -3491,9 +3467,6 @@ static void
 schedule_dealloc_carrier(Allctr_t *allctr, Carrier_t *crr)
 {
     Allctr_t *orig_allctr;
-    Block_t *blk;
-    int check_pending_dealloc;
-    erts_aint_t max_size;
 
     ASSERT(IS_MB_CARRIER(crr));
 
@@ -3504,9 +3477,17 @@ schedule_dealloc_carrier(Allctr_t *allctr, Carrier_t *crr)
 
     orig_allctr = crr->cpool.orig_allctr;
 
-    if (allctr != orig_allctr) {
-	int cinit = orig_allctr->dd.ix - allctr->dd.ix;
-
+    if (allctr == orig_allctr) {
+        if (!(erts_smp_atomic_read_nob(&crr->allctr) & ERTS_CRR_ALCTR_FLG_HOMECOMING)) {
+            dealloc_my_carrier(allctr, crr);
+        }
+        /*else
+         * Carrier was abandoned earlier by other thread and
+         * is still waiting for us in dd-queue.
+         * handle_delayed_dealloc() will handle it when crr is dequeued.
+         */
+    }
+    else {
 	/*
 	 * We send the carrier to its origin for deallocation.
 	 * This in order:
@@ -3515,31 +3496,39 @@ schedule_dealloc_carrier(Allctr_t *allctr, Carrier_t *crr)
 	 * - to ensure that we always only reuse empty carriers
 	 *   originating from our own thread specific mseg_alloc
 	 *   instance which is beneficial on NUMA systems.
-	 *
-	 * The receiver will recognize that this is a carrier to
-	 * deallocate (and not a block which is the common case)
-	 * since the block is an mbc block that is free and last
-	 * in the carrier.
 	 */
-	blk = MBC_TO_FIRST_BLK(allctr, crr);
-	ERTS_ALC_CPOOL_ASSERT(IS_FREE_LAST_MBC_BLK(blk));
-
-	ERTS_ALC_CPOOL_ASSERT(IS_MBC_FIRST_ABLK(allctr, blk));
-	ERTS_ALC_CPOOL_ASSERT(crr == FBLK_TO_MBC(blk));
-	ERTS_ALC_CPOOL_ASSERT(crr == FIRST_BLK_TO_MBC(allctr, blk));
-	ERTS_ALC_CPOOL_ASSERT(((erts_aint_t) allctr)
-			      == (erts_smp_atomic_read_nob(&crr->allctr)
-				  & ~ERTS_CRR_ALCTR_FLG_MASK));
-
-        blk = &crr->cpool.homecoming_dd.blk;
-        ERTS_ALC_CPOOL_ASSERT(blk->bhdr == HOMECOMING_MBC_BLK_HDR);
-	if (ddq_enqueue(&orig_allctr->dd.q, BLK2UMEM(blk), cinit))
-	    erts_alloc_notify_delayed_dealloc(orig_allctr->ix);
-	return;
+        erts_aint_t iallctr;
+#ifdef ERTS_ALC_CPOOL_DEBUG
+	Block_t* first_blk = MBC_TO_FIRST_BLK(allctr, crr);
+	ERTS_ALC_CPOOL_ASSERT(IS_FREE_LAST_MBC_BLK(first_blk));
+
+	ERTS_ALC_CPOOL_ASSERT(IS_MBC_FIRST_ABLK(allctr, first_blk));
+	ERTS_ALC_CPOOL_ASSERT(crr == FBLK_TO_MBC(first_blk));
+	ERTS_ALC_CPOOL_ASSERT(crr == FIRST_BLK_TO_MBC(allctr, first_blk));
+	ERTS_ALC_CPOOL_ASSERT((erts_smp_atomic_read_nob(&crr->allctr)
+                               & ~ERTS_CRR_ALCTR_FLG_HOMECOMING)
+                              == (erts_aint_t) allctr);
+#endif
+
+        iallctr = (erts_aint_t)orig_allctr | ERTS_CRR_ALCTR_FLG_HOMECOMING;
+        if (!(erts_smp_atomic_xchg_nob(&crr->allctr, iallctr)
+              & ERTS_CRR_ALCTR_FLG_HOMECOMING)) {
+            enqueue_homecoming(allctr, crr);
+        }
     }
+}
 
-    if (is_abandoned(crr))
-	unlink_abandoned_carrier(crr);
+static void dealloc_my_carrier(Allctr_t *allctr, Carrier_t *crr)
+{
+    Block_t *blk;
+    int check_pending_dealloc;
+    erts_aint_t max_size;
+
+    ERTS_ALC_CPOOL_ASSERT(allctr == crr->cpool.orig_allctr);
+    if (is_abandoned(crr)) {
+        unlink_abandoned_carrier(crr);
+        crr->cpool.state = ERTS_MBC_IS_HOME;
+    }
 
     if (crr->cpool.thr_prgr == ERTS_THR_PRGR_INVALID
 	|| erts_thr_progress_has_reached(crr->cpool.thr_prgr)) {
@@ -3590,8 +3579,7 @@ cpool_init_carrier_data(Allctr_t *allctr, Carrier_t *crr)
 	    limit = (csz/100)*allctr->cpool.util_limit;
 	crr->cpool.abandon_limit = limit;
     }
-    crr->cpool.abandoned.next = NULL;
-    crr->cpool.abandoned.prev = NULL;
+    crr->cpool.state = ERTS_MBC_IS_HOME;
 }
 
 static void
@@ -3618,22 +3606,64 @@ static void
 abandon_carrier(Allctr_t *allctr, Carrier_t *crr)
 {
     erts_aint_t max_size;
+    erts_aint_t iallctr;
 
-    STAT_MBC_CPOOL_INSERT(allctr, crr);
+    STAT_MBC_ABANDON(allctr, crr);
 
     unlink_carrier(&allctr->mbc_list, crr);
-    if (crr->cpool.orig_allctr == allctr) {
-	link_abandoned_carrier(&allctr->cpool.pooled_list, crr);
-    }
-
     allctr->remove_mbc(allctr, crr);
+    set_new_allctr_abandon_limit(allctr);
 
     max_size = (erts_aint_t) allctr->largest_fblk_in_mbc(allctr, crr);
     erts_atomic_set_nob(&crr->cpool.max_size, max_size);
-
     cpool_insert(allctr, crr);
 
-    set_new_allctr_abandon_limit(allctr);
+
+    iallctr = erts_smp_atomic_read_nob(&crr->allctr);
+    if (allctr == crr->cpool.orig_allctr) {
+        /* preserve HOMECOMING flag */
+        ASSERT((iallctr & ~ERTS_CRR_ALCTR_FLG_HOMECOMING) == (erts_aint_t)allctr);
+        erts_smp_atomic_set_wb(&crr->allctr, iallctr | ERTS_CRR_ALCTR_FLG_IN_POOL);
+        poolify_my_carrier(allctr, crr);
+    }
+    else {
+        ASSERT((iallctr & ~ERTS_CRR_ALCTR_FLG_HOMECOMING) == (erts_aint_t)allctr);
+        iallctr = ((erts_aint_t)crr->cpool.orig_allctr |
+                   ERTS_CRR_ALCTR_FLG_HOMECOMING |
+                   ERTS_CRR_ALCTR_FLG_IN_POOL);
+        if (!(erts_smp_atomic_xchg_wb(&crr->allctr, iallctr)
+              & ERTS_CRR_ALCTR_FLG_HOMECOMING)) {
+
+            enqueue_homecoming(allctr, crr);
+        }
+    }
+}
+
+static void
+enqueue_homecoming(Allctr_t* allctr, Carrier_t* crr)
+{
+    Allctr_t* orig_allctr = crr->cpool.orig_allctr;
+    const int cinit = orig_allctr->dd.ix - allctr->dd.ix;
+    Block_t* dd_blk = &crr->cpool.homecoming_dd.blk;
+
+    /*
+     * The receiver will recognize this as a carrier
+     * (and not a block which is the common case)
+     * since the block header is HOMECOMING_MBC_BLK_HDR.
+     */
+    ASSERT(dd_blk->bhdr == HOMECOMING_MBC_BLK_HDR);
+    if (ddq_enqueue(&orig_allctr->dd.q, BLK2UMEM(dd_blk), cinit))
+        erts_alloc_notify_delayed_dealloc(orig_allctr->ix);
+}
+
+static void
+poolify_my_carrier(Allctr_t *allctr, Carrier_t *crr)
+{
+    ERTS_ALC_CPOOL_ASSERT(allctr == crr->cpool.orig_allctr);
+
+    crr->cpool.pooled.hdr.bhdr = erts_atomic_read_nob(&crr->cpool.max_size);
+    aoff_add_pooled_mbc(allctr, crr);
+    crr->cpool.state = ERTS_MBC_WAS_POOLED;
 }
 
 static void
@@ -4153,16 +4183,21 @@ destroy_carrier(Allctr_t *allctr, Block_t *blk, Carrier_t **busy_pcrr_pp)
 
 #ifdef ERTS_SMP
 	if (busy_pcrr_pp && *busy_pcrr_pp) {
+            erts_aint_t iallctr = erts_smp_atomic_read_nob(&crr->allctr);
 	    ERTS_ALC_CPOOL_ASSERT(*busy_pcrr_pp == crr);
-	    *busy_pcrr_pp = NULL;
-	    ERTS_ALC_CPOOL_ASSERT(erts_smp_atomic_read_nob(&crr->allctr)
-				  == (((erts_aint_t) allctr)
-				      | ERTS_CRR_ALCTR_FLG_IN_POOL
-				      | ERTS_CRR_ALCTR_FLG_BUSY));
-	    erts_smp_atomic_set_nob(&crr->allctr, ((erts_aint_t) allctr));
+            ERTS_ALC_CPOOL_ASSERT((iallctr & ~ERTS_CRR_ALCTR_FLG_HOMECOMING)
+                                  == (((erts_aint_t) allctr)
+                                      | ERTS_CRR_ALCTR_FLG_IN_POOL
+                                      | ERTS_CRR_ALCTR_FLG_BUSY));
+            ERTS_ALC_CPOOL_ASSERT(allctr == crr->cpool.orig_allctr);
+
+            *busy_pcrr_pp = NULL;
+	    erts_smp_atomic_set_nob(&crr->allctr,
+                                    (iallctr & ~(ERTS_CRR_ALCTR_FLG_IN_POOL |
+                                                 ERTS_CRR_ALCTR_FLG_BUSY)));
 	    cpool_delete(allctr, allctr, crr);
 	}
-	else
+        else
 #endif
 	{
 	    unlink_carrier(&allctr->mbc_list, crr);
@@ -5565,12 +5600,13 @@ erts_alcu_free_thr_pref(ErtsAlcType_t type, void *extra, void *p)
 	pref_allctr = get_pref_allctr(extra);
 	used_allctr = get_used_allctr(pref_allctr, ERTS_ALC_TS_PREF_LOCK_IF_USED,
 				      p, NULL, &busy_pcrr_p);
-	if (pref_allctr != used_allctr)
+	if (pref_allctr != used_allctr) {
 	    enqueue_dealloc_other_instance(type,
-					   used_allctr,
-					   p,
-					   (used_allctr->dd.ix
-					    - pref_allctr->dd.ix));
+                                           used_allctr,
+                                           p,
+                                           (used_allctr->dd.ix
+                                            - pref_allctr->dd.ix));
+        }
 	else {
 	    ERTS_ALCU_DBG_CHK_THR_ACCESS(used_allctr);
 	    do_erts_alcu_free(type, used_allctr, p, &busy_pcrr_p);
@@ -6040,10 +6076,7 @@ erts_alcu_start(Allctr_t *allctr, AllctrInit_t *init)
 	    allctr->min_block_size = sz;
     }
 
-    allctr->cpool.pooled_list.next  = &allctr->cpool.pooled_list;
-    allctr->cpool.pooled_list.prev  = &allctr->cpool.pooled_list;
-    allctr->cpool.traitor_list.next = &allctr->cpool.traitor_list;
-    allctr->cpool.traitor_list.prev = &allctr->cpool.traitor_list;
+    allctr->cpool.pooled_tree = NULL;
     allctr->cpool.dc_list.first = NULL;
     allctr->cpool.dc_list.last = NULL;
     allctr->cpool.abandon_limit = 0;
diff --git a/erts/emulator/beam/erl_alloc_util.h b/erts/emulator/beam/erl_alloc_util.h
index 1291a6c10e..e5bf494e97 100644
--- a/erts/emulator/beam/erl_alloc_util.h
+++ b/erts/emulator/beam/erl_alloc_util.h
@@ -307,6 +307,7 @@ typedef union {char c[ERTS_ALLOC_ALIGN_BYTES]; long l; double d;} Unit_t;
 
 typedef struct Carrier_t_ Carrier_t;
 
+
 typedef struct {
     UWord bhdr;
 #if !MBC_ABLK_OFFSET_BITS
@@ -373,13 +374,24 @@ typedef struct {
 
 typedef UWord FreeBlkFtr_t; /* Footer of a free block */
 
-
+/* This AOFF stuff really belong in erl_ao_firstfit_alloc.h */
+typedef struct AOFF_RBTree_t_ AOFF_RBTree_t;
+struct AOFF_RBTree_t_ {
+    Block_t hdr;
+    AOFF_RBTree_t *parent;
+    AOFF_RBTree_t *left;
+    AOFF_RBTree_t *right;
+    Uint32 flags;
+    Uint32 max_sz;  /* of all blocks in this sub-tree */
+};
 #ifdef ERTS_SMP
+void aoff_add_pooled_mbc(Allctr_t*, Carrier_t*);
+void aoff_remove_pooled_mbc(Allctr_t*, Carrier_t*);
+Carrier_t* aoff_lookup_pooled_mbc(Allctr_t*, Uint size);
+void erts_aoff_larger_max_size(AOFF_RBTree_t *node);
+#endif
 
-typedef struct ErtsDoubleLink_t_ {
-    struct ErtsDoubleLink_t_ *next;
-    struct ErtsDoubleLink_t_ *prev;
-}ErtsDoubleLink_t;
+#ifdef ERTS_SMP
 
 typedef struct {
     ErtsFakeDDBlock_t homecoming_dd;
@@ -391,7 +403,12 @@ typedef struct {
     UWord abandon_limit;
     UWord blocks;
     UWord blocks_size;
-    ErtsDoubleLink_t abandoned; /* node in pooled_list or traitor_list */
+    enum {
+        ERTS_MBC_IS_HOME,
+        ERTS_MBC_WAS_POOLED,
+        ERTS_MBC_WAS_TRAITOR
+    } state;
+    AOFF_RBTree_t pooled;  /* node in pooled_tree */
 } ErtsAlcCPoolData_t;
 
 #endif
@@ -566,15 +583,14 @@ struct Allctr_t_ {
     UWord               crr_set_flgs;
     UWord               crr_clr_flgs;
 
-    /* Carriers */
+    /* Carriers *employed* by this allocator */
     CarrierList_t	mbc_list;
     CarrierList_t	sbc_list;
 #ifdef ERTS_SMP
     struct {
-	/* pooled_list, traitor list and dc_list contain only
-           carriers _created_ by this allocator */
-	ErtsDoubleLink_t pooled_list;
-	ErtsDoubleLink_t traitor_list;
+	/* pooled_tree and dc_list contain only
+           carriers *created* by this allocator */
+	AOFF_RBTree_t*   pooled_tree;
 	CarrierList_t	 dc_list;
 
 	UWord		abandon_limit;
@@ -686,7 +702,6 @@ void erts_alcu_assert_failed(char* expr, char* file, int line, char *func);
 int is_sbc_blk(Block_t*);
 #endif
 
-
 #endif /* #if defined(GET_ERL_ALLOC_UTIL_IMPL)
 	      && !defined(ERL_ALLOC_UTIL_IMPL__) */
 
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index 05ba1f9891..b781db152f 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -92,18 +92,6 @@
 #define RBT_ASSERT(x)
 #endif
 
-
-/* Types... */
-typedef struct AOFF_RBTree_t_ AOFF_RBTree_t;
-
-struct AOFF_RBTree_t_ {
-    Block_t hdr;
-    AOFF_RBTree_t *parent;
-    AOFF_RBTree_t *left;
-    AOFF_RBTree_t *right;
-    Uint32 flags;
-    Uint32 max_sz;  /* of all blocks in this sub-tree */
-};
 #define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
 
 /* BF block nodes keeps list of all with equal size
@@ -120,7 +108,7 @@ 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 rbt_node;   /* My node in the carrier tree */
     AOFF_RBTree_t* root;        /* Root of my block tree */
 };
 #define RBT_NODE_TO_MBC(PTR) ErtsContainerStruct((PTR), AOFF_Carrier_t, rbt_node)
@@ -136,8 +124,9 @@ struct AOFF_Carrier_t_ {
 */
 
 #ifdef HARD_DEBUG
-#  define HARD_CHECK_IS_MEMBER(ROOT,NODE) rbt_assert_is_member(ROOT,NODE)
+#  define HARD_CHECK_IS_MEMBER(ROOT,NODE) ASSERT(rbt_is_member(ROOT,NODE))
 #  define HARD_CHECK_TREE(CRR,FLV,ROOT,SZ) check_tree(CRR, FLV, ROOT, SZ)
+static int rbt_is_member(AOFF_RBTree_t* root, AOFF_RBTree_t* node);
 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)
@@ -179,6 +168,27 @@ static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
     else ASSERT(new_max == old_max);
 }
 
+#ifdef ERTS_SMP
+/*
+ * Set possibly new larger 'max_sz' of node and propagate change toward root
+ */
+void erts_aoff_larger_max_size(AOFF_RBTree_t *node)
+{
+    AOFF_RBTree_t* x = node;
+    const Uint new_sz = node->hdr.bhdr;
+
+    ASSERT(!x->left  || x->left->max_sz  <= x->max_sz);
+    ASSERT(!x->right || x->right->max_sz <= x->max_sz);
+
+    while (new_sz > x->max_sz) {
+        x->max_sz = new_sz;
+        x = x->parent;
+        if (!x)
+            break;
+    }
+}
+#endif
+
 static ERTS_INLINE SWord cmp_blocks(enum AOFF_Flavor flavor,
 				    AOFF_RBTree_t* lhs, AOFF_RBTree_t* rhs)
 {
@@ -220,9 +230,6 @@ static UWord aoff_largest_fblk_in_mbc(Allctr_t*, Carrier_t*);
 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 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);
-#endif
 
 static Eterm info_options(Allctr_t *, char *, fmtfn_t *, void *, Uint **, Uint *);
 static void init_atoms(void);
@@ -719,19 +726,20 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block)
 
     rbt_insert(alc->flavor, &blk_crr->root, blk);
 
-    /* Update the carrier tree with a potentially new (larger) max_sz
-    */
+    /*
+     * Update carrier tree with a potentially new (larger) max_sz
+     */
     crr_node = &blk_crr->rbt_node;
     if (blk_sz > crr_node->hdr.bhdr) {
-	ASSERT(blk_sz == blk_crr->root->max_sz);
-	crr_node->hdr.bhdr = blk_sz;
-	while (blk_sz > crr_node->max_sz) {
-	    crr_node->max_sz = blk_sz;
-	    crr_node = crr_node->parent;
-	    if (!crr_node) break;
-	}
+        ASSERT(blk_sz == blk_crr->root->max_sz);
+        crr_node->hdr.bhdr = blk_sz;
+        while (blk_sz > crr_node->max_sz) {
+            crr_node->max_sz = blk_sz;
+            crr_node = crr_node->parent;
+            if (!crr_node) break;
+        }
     }
-    HARD_CHECK_TREE(&blk_crr->crr, alc->flavor, blk_crr->root, 0);
+    HARD_CHECK_TREE(NULL, AOFF_AOFF, alc->mbc_root, 0);
 }
 
 static void
@@ -826,6 +834,18 @@ rbt_search(AOFF_RBTree_t* root, Uint size)
     }
 }
 
+#ifdef ERTS_SMP
+Carrier_t* aoff_lookup_pooled_mbc(Allctr_t* allctr, Uint size)
+{
+    AOFF_RBTree_t* node;
+
+    if (!allctr->cpool.pooled_tree)
+	return NULL;
+    node = rbt_search(allctr->cpool.pooled_tree, size);
+    return node ? ErtsContainerStruct(node, Carrier_t, cpool.pooled) : NULL;
+}
+#endif
+
 static Block_t *
 aoff_get_free_block(Allctr_t *allctr, Uint size,
 		    Block_t *cand_blk, Uint cand_size)
@@ -920,16 +940,31 @@ static void aoff_add_mbc(Allctr_t *allctr, Carrier_t *carrier)
     HARD_CHECK_TREE(NULL, 0, *root, 0);
 }
 
+#ifdef ERTS_SMP
+void aoff_add_pooled_mbc(Allctr_t *allctr, Carrier_t *crr)
+{
+    AOFF_RBTree_t **root = &allctr->cpool.pooled_tree;
+
+    ASSERT(allctr == crr->cpool.orig_allctr);
+    HARD_CHECK_TREE(NULL, 0, *root, 0);
+
+    /* Link carrier in address order tree
+     */
+    rbt_insert(AOFF_AOFF, root, &crr->cpool.pooled);
+
+    HARD_CHECK_TREE(NULL, 0, *root, 0);
+}
+#endif
+
 static void aoff_remove_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;
+    AOFF_RBTree_t **root = &((AOFFAllctr_t*)allctr)->mbc_root;
+    AOFF_Carrier_t *crr = (AOFF_Carrier_t*)carrier;
 
     ASSERT(allctr == ERTS_ALC_CARRIER_TO_ALLCTR(carrier));
 
     if (!IS_CRR_IN_TREE(crr,*root))
-        return;
+	return;
 
     HARD_CHECK_TREE(NULL, 0, *root, 0);
 
@@ -942,6 +977,26 @@ static void aoff_remove_mbc(Allctr_t *allctr, Carrier_t *carrier)
     HARD_CHECK_TREE(NULL, 0, *root, 0);
 }
 
+#ifdef ERTS_SMP
+void aoff_remove_pooled_mbc(Allctr_t *allctr, Carrier_t *crr)
+{
+    ASSERT(allctr == crr->cpool.orig_allctr);
+
+    HARD_CHECK_TREE(NULL, 0, allctr->cpool.pooled_tree, 0);
+
+    rbt_delete(&allctr->cpool.pooled_tree, &crr->cpool.pooled);
+#ifdef DEBUG
+    crr->cpool.pooled.parent = NULL;
+    crr->cpool.pooled.left = NULL;
+    crr->cpool.pooled.right = NULL;
+    crr->cpool.pooled.max_sz = 0;
+#endif
+    HARD_CHECK_TREE(NULL, 0, allctr->cpool.pooled_tree, 0);
+
+}
+#endif
+
+
 static UWord aoff_largest_fblk_in_mbc(Allctr_t* allctr, Carrier_t* carrier)
 {
     AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
@@ -1085,12 +1140,13 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2)
 
 
 #ifdef HARD_DEBUG
-
-static int rbt_assert_is_member(AOFF_RBTree_t* root, AOFF_RBTree_t* node)
+static int rbt_is_member(AOFF_RBTree_t* root, AOFF_RBTree_t* node)
 {
     while (node != root) {
-	ASSERT(node->parent);
-	ASSERT(node->parent->left == node || node->parent->right == node);
+        if (!node->parent || (node->parent->left != node &&
+                              node->parent->right != node)) {
+            return 0;
+        }
 	node = node->parent;
     }    
     return 1;
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.h b/erts/emulator/beam/erl_ao_firstfit_alloc.h
index 7349c6ab19..a3fca7d3e3 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.h
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.h
@@ -53,7 +53,6 @@ Allctr_t *erts_aoffalc_start(AOFFAllctr_t *, AOFFAllctrInit_t*, AllctrInit_t *);
 #define GET_ERL_ALLOC_UTIL_IMPL
 #include "erl_alloc_util.h"
 
-
 struct AOFFAllctr_t_ {
     Allctr_t		allctr; /* Has to be first! */