aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator
diff options
context:
space:
mode:
authorSverker Eriksson <sverker@erlang.org>2013-04-22 14:43:27 +0200
committerSverker Eriksson <sverker@erlang.org>2013-06-03 14:24:23 +0200
commit2fab1055580b4c5c00ef23db59b40a1b0b5a9acc (patch)
treece42fd1dc36eceee55e8a836a35542b1cd7b3f43 /erts/emulator
parent7a1cf0d233d8e3981f1e4a822aa1837591697c3a (diff)
downloadotp-2fab1055580b4c5c00ef23db59b40a1b0b5a9acc.tar.gz
otp-2fab1055580b4c5c00ef23db59b40a1b0b5a9acc.tar.bz2
otp-2fab1055580b4c5c00ef23db59b40a1b0b5a9acc.zip
erts: Add "bestfit within carrier" for aoff allocator (aoffcbf)
Diffstat (limited to 'erts/emulator')
-rw-r--r--erts/emulator/beam/erl_alloc.c5
-rw-r--r--erts/emulator/beam/erl_alloc_util.c37
-rw-r--r--erts/emulator/beam/erl_alloc_util.h33
-rw-r--r--erts/emulator/beam/erl_ao_firstfit_alloc.c92
-rw-r--r--erts/emulator/beam/erl_ao_firstfit_alloc.h4
-rw-r--r--erts/emulator/beam/erl_bestfit_alloc.c2
-rw-r--r--erts/emulator/test/alloc_SUITE_data/allocator_test.h4
-rw-r--r--erts/emulator/test/alloc_SUITE_data/coalesce.c2
-rw-r--r--erts/emulator/test/alloc_SUITE_data/rbtree.c68
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");
+
}