aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2013-06-19 18:34:56 +0200
committerSverker Eriksson <[email protected]>2013-06-19 18:51:06 +0200
commit5d67cc7f4c176ea6ab4d2538443d5fe264152861 (patch)
tree02629c584461df3b6f80d09a1de6298af4c3440c
parentf91c381afa2ebed6e37b49b4cc3f81bb9ca9e3eb (diff)
downloadotp-5d67cc7f4c176ea6ab4d2538443d5fe264152861.tar.gz
otp-5d67cc7f4c176ea6ab4d2538443d5fe264152861.tar.bz2
otp-5d67cc7f4c176ea6ab4d2538443d5fe264152861.zip
erts: Add new allocator strategy aoffcbf
with better performance than aoffcaobf as we don't have to rearrange the search tree when there are blocks of equal size.
-rw-r--r--erts/doc/src/erts_alloc.xml14
-rw-r--r--erts/emulator/beam/erl_alloc.c14
-rw-r--r--erts/emulator/beam/erl_ao_firstfit_alloc.c190
-rw-r--r--erts/emulator/beam/erl_ao_firstfit_alloc.h11
-rw-r--r--erts/emulator/beam/erl_bestfit_alloc.c6
-rw-r--r--erts/emulator/test/alloc_SUITE_data/allocator_test.h3
-rw-r--r--erts/emulator/test/alloc_SUITE_data/coalesce.c2
-rw-r--r--erts/emulator/test/alloc_SUITE_data/rbtree.c90
8 files changed, 220 insertions, 110 deletions
diff --git a/erts/doc/src/erts_alloc.xml b/erts/doc/src/erts_alloc.xml
index 2ffb55c6ab..5e008493b9 100644
--- a/erts/doc/src/erts_alloc.xml
+++ b/erts/doc/src/erts_alloc.xml
@@ -170,6 +170,15 @@
used. The time complexity is proportional to log N, where
N is the number of free blocks.</p>
</item>
+ <tag>Address order first fit carrier best fit</tag>
+ <item>
+ <p>Strategy: Find the <em>carrier</em> with the lowest address that
+ can satisfy the requested block size, then find a block within
+ that carrier using the "best fit" strategy.</p>
+ <p>Implementation: Balanced binary search trees are
+ used. The time complexity is proportional to log N, where
+ N is the number of free blocks.</p>
+ </item>
<tag>Address order first fit carrier address order best fit</tag>
<item>
<p>Strategy: Find the <em>carrier</em> with the lowest address that
@@ -330,7 +339,7 @@
fetched it will function as an ordinary carrier. This feature has
special requirements on the
<seealso marker="#M_as">allocation strategy</seealso> used. Currently
- only the <c>aoff</c> and the <c>aoffcaobf</c> strategies support
+ only the strategies <c>aoff</c>, <c>aoffcbf</c> and <c>aoffcaobf</c> support
abandoned carriers. This feature also requires
<seealso marker="#M_t">multiple thread specific instances</seealso>
to be enabled. When enabling this feature, multiple thread specific
@@ -340,10 +349,11 @@
allocators based on the <c>alloc_util</c> framework with the
exception of <c>temp_alloc</c> (which would be pointless).
</item>
- <tag><marker id="M_as"><c><![CDATA[+M<S>as bf|aobf|aoff|aoffcaobf|gf|af]]></c></marker></tag>
+ <tag><marker id="M_as"><c><![CDATA[+M<S>as bf|aobf|aoff|aoffcbf|aoffcaobf|gf|af]]></c></marker></tag>
<item>
Allocation strategy. Valid strategies are <c>bf</c> (best fit),
<c>aobf</c> (address order best fit), <c>aoff</c> (address order first fit),
+ <c>aoffcbf</c> (address order first fit carrier best fit),
<c>aoffcaobf</c> (address order first fit carrier address order best fit),
<c>gf</c> (good fit), and <c>af</c> (a fit). See
<seealso marker="#strategy">the description of allocation strategies</seealso> in "the <c>alloc_util</c> framework" section.</item>
diff --git a/erts/emulator/beam/erl_alloc.c b/erts/emulator/beam/erl_alloc.c
index a547191d6d..7b77bcca58 100644
--- a/erts/emulator/beam/erl_alloc.c
+++ b/erts/emulator/beam/erl_alloc.c
@@ -245,7 +245,7 @@ set_default_acul(struct au_init *ip, int acul)
{
ip->thr_spec = 1;
ip->atype = AOFIRSTFIT;
- ip->init.aoff.bf_within_carrier = 1;
+ ip->init.aoff.flavor = AOFF_AOBF;
ip->init.util.acul = acul;
}
@@ -558,7 +558,7 @@ static ERTS_INLINE int
strategy_support_carrier_migration(struct au_init *auip)
{
/*
- * Currently only aoff and aoffcaobf support carrier
+ * Currently only aoff, aoffcbf and aoffcaobf support carrier
* migration, i.e, type AOFIRSTFIT.
*/
return auip->atype == AOFIRSTFIT;
@@ -583,7 +583,7 @@ ensure_carrier_migration_support(struct au_init *auip)
if (!strategy_support_carrier_migration(auip)) {
/* Default to aoffcaobf */
auip->atype = AOFIRSTFIT;
- auip->init.aoff.bf_within_carrier = 1;
+ auip->init.aoff.flavor = AOFF_AOBF;
}
}
@@ -1284,11 +1284,15 @@ handle_au_arg(struct au_init *auip,
}
else if (strcmp("aoff", alg) == 0) {
auip->atype = AOFIRSTFIT;
- auip->init.aoff.bf_within_carrier = 0;
+ auip->init.aoff.flavor = AOFF_AOFF;
+ }
+ else if (strcmp("aoffcbf", alg) == 0) {
+ auip->atype = AOFIRSTFIT;
+ auip->init.aoff.flavor = AOFF_BF;
}
else if (strcmp("aoffcaobf", alg) == 0) {
auip->atype = AOFIRSTFIT;
- auip->init.aoff.bf_within_carrier = 1;
+ auip->init.aoff.flavor = AOFF_AOBF;
}
else {
bad_value(param, sub_param + 1, alg);
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index f73ac2eb6e..4e6c8b317e 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -34,10 +34,11 @@
* sub-tree ('max_sz'). By that we can start from root and keep
* left (for low addresses) while dismissing entire sub-trees with
* too small blocks.
- * AOFFCBF:
+ * Bestfit within carrier:
* The only difference for "bestfit within carrier" is the tree
* sorting order. Blocks within the same carrier are sorted
- * wrt size instead of address.
+ * wrt size instead of address. The 'max_sz' field is maintained
+ * in order to dismiss entire carriers with too small blocks.
*
* Authors: Rickard Green/Sverker Eriksson
*/
@@ -67,6 +68,15 @@
# define LEFT_VISITED_FLG (((Uint) 1) << 2)
# define RIGHT_VISITED_FLG (((Uint) 1) << 3)
#endif
+#ifdef DEBUG
+# define IS_BF_FLG (((Uint) 1) << 4)
+#endif
+
+#define IS_TREE_NODE(N) (((AOFF_RBTree_t *) (N))->flags & TREE_NODE_FLG)
+#define IS_LIST_ELEM(N) (!IS_TREE_NODE(((AOFF_RBTree_t *) (N))))
+
+#define SET_TREE_NODE(N) (((AOFF_RBTree_t *) (N))->flags |= TREE_NODE_FLG)
+#define SET_LIST_ELEM(N) (((AOFF_RBTree_t *) (N))->flags &= ~TREE_NODE_FLG)
#define IS_RED(N) (((AOFF_RBTree_t *) (N)) \
&& ((AOFF_RBTree_t *) (N))->flags & RED_FLG)
@@ -98,6 +108,16 @@ struct AOFF_RBTree_t_ {
};
#define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
+/* BF block nodes keeps list of all with equal size
+ */
+typedef struct {
+ AOFF_RBTree_t t;
+ AOFF_RBTree_t *next;
+}AOFF_RBTreeList_t;
+
+#define LIST_NEXT(N) (((AOFF_RBTreeList_t*) (N))->next)
+#define LIST_PREV(N) (((AOFF_RBTreeList_t*) (N))->t.parent)
+
typedef struct AOFF_Carrier_t_ AOFF_Carrier_t;
struct AOFF_Carrier_t_ {
@@ -119,11 +139,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,BF,ROOT,SZ) check_tree(CRR, BF, ROOT, SZ)
-static AOFF_RBTree_t * check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint);
+# 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);
#else
# define HARD_CHECK_IS_MEMBER(ROOT,NODE)
-# define HARD_CHECK_TREE(CRR,BF,ROOT,SZ)
+# define HARD_CHECK_TREE(CRR,FLV,ROOT,SZ)
#endif
@@ -161,25 +181,25 @@ static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
else ASSERT(new_max == old_max);
}
-static ERTS_INLINE SWord cmp_blocks(int bestfit,
+static ERTS_INLINE SWord cmp_blocks(enum AOFF_Flavor flavor,
AOFF_RBTree_t* lhs, AOFF_RBTree_t* rhs)
{
ASSERT(lhs != rhs);
- ASSERT(!bestfit || FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr));
- if (bestfit) {
+ 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) return diff;
+ if (diff || flavor == AOFF_BF) return diff;
}
return (char*)lhs - (char*)rhs;
}
-static ERTS_INLINE SWord cmp_cand_blk(int bestfit,
+static ERTS_INLINE SWord cmp_cand_blk(enum AOFF_Flavor flavor,
Block_t* cand_blk, AOFF_RBTree_t* rhs)
{
- if (bestfit) {
+ if (flavor != AOFF_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) return diff;
+ if (diff || flavor == AOFF_BF) return diff;
}
}
return (char*)cand_blk - (char*)rhs;
@@ -198,7 +218,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(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk);
+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);
@@ -234,21 +254,21 @@ erts_aoffalc_start(AOFFAllctr_t *alc,
sys_memcpy((void *) alc, (void *) &zero.allctr, sizeof(AOFFAllctr_t));
- alc->bf_within_carrier = aoffinit->bf_within_carrier;
+ alc->flavor = aoffinit->flavor;
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);
+ allctr->min_block_size = (aoffinit->flavor == AOFF_BF ?
+ sizeof(AOFF_RBTreeList_t):sizeof(AOFF_RBTree_t));
- allctr->vsn_str = aoffinit->bf_within_carrier ?
- ERTS_ALC_AOFF_CBF_ALLOC_VSN_STR : ERTS_ALC_AOFF_ALLOC_VSN_STR;
+ allctr->vsn_str = ERTS_ALC_AOFF_ALLOC_VSN_STR;
/* Callback functions */
allctr->get_free_block = aoff_get_free_block;
allctr->link_free_block = aoff_link_free_block;
- allctr->unlink_free_block = aoff_unlink_free_block;
+ allctr->unlink_free_block = aoff_unlink_free_block;
allctr->info_options = info_options;
allctr->get_next_mbc_size = NULL;
@@ -359,9 +379,7 @@ replace(AOFF_RBTree_t **root, AOFF_RBTree_t *x, AOFF_RBTree_t *y)
y->parent = x->parent;
y->right = x->right;
y->left = x->left;
-
- y->max_sz = x->max_sz;
- lower_max_size(y, NULL);
+ y->max_sz = x->max_sz;
}
static void
@@ -458,23 +476,47 @@ tree_insert_fixup(AOFF_RBTree_t** root, AOFF_RBTree_t *blk)
}
static void
-aoff_unlink_free_block(Allctr_t *allctr, Block_t *del)
+aoff_unlink_free_block(Allctr_t *allctr, Block_t *blk)
{
-#ifdef HARD_DEBUG
AOFFAllctr_t* alc = (AOFFAllctr_t*)allctr;
-#endif
- AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(del);
+ AOFF_RBTree_t* del = (AOFF_RBTree_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_IS_MEMBER(alc->mbc_root, &crr->rbt_node);
- HARD_CHECK_TREE(&crr->crr, alc->bf_within_carrier, crr->root, 0);
+ HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, 0);
+
+ if (alc->flavor == AOFF_BF) {
+ ASSERT(del->flags & IS_BF_FLG);
+ if (IS_LIST_ELEM(del)) {
+ /* Remove from list */
+ ASSERT(LIST_PREV(del));
+ ASSERT(LIST_PREV(del)->flags & IS_BF_FLG);
+ LIST_NEXT(LIST_PREV(del)) = LIST_NEXT(del);
+ if (LIST_NEXT(del)) {
+ ASSERT(LIST_NEXT(del)->flags & IS_BF_FLG);
+ LIST_PREV(LIST_NEXT(del)) = LIST_PREV(del);
+ }
+ return;
+ }
+ else if (LIST_NEXT(del)) {
+ /* Replace tree node by next element in list... */
+
+ ASSERT(AOFF_BLK_SZ(LIST_NEXT(del)) == AOFF_BLK_SZ(del));
+ ASSERT(IS_LIST_ELEM(LIST_NEXT(del)));
+
+ replace(&crr->root, (AOFF_RBTree_t*)del, LIST_NEXT(del));
+
+ HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, 0);
+ return;
+ }
+ }
rbt_delete(&crr->root, (AOFF_RBTree_t*)del);
- HARD_CHECK_TREE(&crr->crr, alc->bf_within_carrier, crr->root, 0);
+ HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, 0);
- /* Update the carrier tree with a potentially new (lower) max_sz
- */
+ /* Update the carrier tree with a potentially new (lower) max_sz
+ */
if (crr->root) {
if (crr->rbt_node.hdr.bhdr == crr->root->max_sz) {
return;
@@ -488,6 +530,7 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *del)
lower_max_size(&crr->rbt_node, NULL);
}
+
static void
rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del)
{
@@ -542,7 +585,9 @@ rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del)
}
if (y != z) {
/* We spliced out the successor of z; replace z by the successor */
+ ASSERT(z != &null_x);
replace(root, z, y);
+ lower_max_size(y, NULL);
}
if (spliced_is_black) {
@@ -666,12 +711,11 @@ 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_IS_MEMBER(alc->mbc_root, &blk_crr->rbt_node);
- HARD_CHECK_TREE(&blk_crr->crr, alc->bf_within_carrier, blk_crr->root, 0);
+ HARD_CHECK_TREE(&blk_crr->crr, alc->flavor, blk_crr->root, 0);
- rbt_insert(alc->bf_within_carrier, &blk_crr->root, blk);
+ rbt_insert(alc->flavor, &blk_crr->root, blk);
- /* Update the carrier tree with a potential new (larger) max_sz
+ /* Update the carrier tree with a potentially new (larger) max_sz
*/
crr_node = &blk_crr->rbt_node;
if (blk_sz > crr_node->hdr.bhdr) {
@@ -683,15 +727,19 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block)
if (!crr_node) break;
}
}
- HARD_CHECK_TREE(&blk_crr->crr, alc->bf_within_carrier, blk_crr->root, 0);
+ HARD_CHECK_TREE(&blk_crr->crr, alc->flavor, blk_crr->root, 0);
}
static void
-rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
+rbt_insert(enum AOFF_Flavor flavor, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
{
Uint blk_sz = AOFF_BLK_SZ(blk);
- blk->flags = 0;
+#ifdef DEBUG
+ blk->flags = (flavor == AOFF_BF) ? IS_BF_FLG : 0;
+#else
+ blk->flags = 0;
+#endif
blk->left = NULL;
blk->right = NULL;
blk->max_sz = blk_sz;
@@ -704,10 +752,12 @@ rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
else {
AOFF_RBTree_t *x = *root;
while (1) {
+ SWord diff;
if (x->max_sz < blk_sz) {
x->max_sz = blk_sz;
}
- if (cmp_blocks(bestfit, blk, x) < 0) {
+ diff = cmp_blocks(flavor, blk, x);
+ if (diff < 0) {
if (!x->left) {
blk->parent = x;
x->left = blk;
@@ -715,7 +765,7 @@ rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
}
x = x->left;
}
- else {
+ else if (diff > 0) {
if (!x->right) {
blk->parent = x;
x->right = blk;
@@ -723,6 +773,18 @@ rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
}
x = x->right;
}
+ else {
+ ASSERT(flavor == AOFF_BF);
+ ASSERT(blk->flags & IS_BF_FLG);
+ ASSERT(x->flags & IS_BF_FLG);
+ SET_LIST_ELEM(blk);
+ LIST_NEXT(blk) = LIST_NEXT(x);
+ LIST_PREV(blk) = x;
+ if (LIST_NEXT(x))
+ LIST_PREV(LIST_NEXT(x)) = blk;
+ LIST_NEXT(x) = blk;
+ return;
+ }
}
/* Insert block into size tree */
@@ -732,6 +794,10 @@ rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
if (IS_RED(blk->parent))
tree_insert_fixup(root, blk);
}
+ if (flavor == AOFF_BF) {
+ SET_TREE_NODE(blk);
+ LIST_NEXT(blk) = NULL;
+ }
}
static AOFF_RBTree_t*
@@ -780,7 +846,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->bf_within_carrier, crr->root, size);
+ dbg_blk = HARD_CHECK_TREE(&crr->crr, alc->flavor, crr->root, size);
#endif
blk = rbt_search(crr->root, size);
@@ -793,7 +859,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
if (!blk)
return NULL;
- if (cand_blk && cmp_cand_blk(alc->bf_within_carrier, cand_blk, blk) < 0) {
+ if (cand_blk && cmp_cand_blk(alc->flavor, cand_blk, blk) < 0) {
return NULL; /* cand_blk was better */
}
@@ -813,7 +879,7 @@ static void aoff_creating_mbc(Allctr_t *allctr, Carrier_t *carrier)
/* Link carrier in address order tree
*/
crr->rbt_node.hdr.bhdr = 0;
- rbt_insert(0, root, &crr->rbt_node);
+ rbt_insert(AOFF_AOFF, root, &crr->rbt_node);
/* aoff_link_free_block will add free block later */
crr->root = NULL;
@@ -843,7 +909,7 @@ static void aoff_add_mbc(Allctr_t *allctr, Carrier_t *carrier)
/* Link carrier in address order tree
*/
- rbt_insert(0, root, &crr->rbt_node);
+ rbt_insert(AOFF_AOFF, root, &crr->rbt_node);
HARD_CHECK_TREE(NULL, 0, *root, 0);
}
@@ -883,6 +949,7 @@ static struct {
Eterm as;
Eterm aoff;
Eterm aoffcaobf;
+ Eterm aoffcbf;
#ifdef DEBUG
Eterm end_of_atoms;
#endif
@@ -912,6 +979,7 @@ init_atoms(void)
AM_INIT(as);
AM_INIT(aoff);
AM_INIT(aoffcaobf);
+ AM_INIT(aoffcbf);
#ifdef DEBUG
for (atom = (Eterm *) &am; atom < &am.end_of_atoms; atom++) {
@@ -943,13 +1011,15 @@ info_options(Allctr_t *allctr,
{
AOFFAllctr_t* alc = (AOFFAllctr_t*) allctr;
Eterm res = THE_NON_VALUE;
+ const char* flavor_str[3] = {"aoff", "aoffcaobf", "aoffcbf"};
+ Eterm flavor_atom[3] = {am.aoff, am.aoffcaobf, am.aoffcbf};
if (print_to_p) {
erts_print(*print_to_p,
print_to_arg,
"%sas: %s\n",
prefix,
- alc->bf_within_carrier ? "aoffcaobf" : "aoff");
+ flavor_str[alc->flavor]);
}
if (hpp || szp) {
@@ -959,8 +1029,7 @@ info_options(Allctr_t *allctr,
__FILE__, __LINE__);;
res = NIL;
- add_2tup(hpp, szp, &res, am.as,
- alc->bf_within_carrier ? am.aoffcaobf : am.aoff);
+ add_2tup(hpp, szp, &res, am.as, flavor_atom[alc->flavor]);
}
return res;
@@ -978,6 +1047,7 @@ UWord
erts_aoffalc_test(UWord op, UWord a1, UWord a2)
{
switch (op) {
+ case 0x500: return (UWord) ((AOFFAllctr_t *) a1)->flavor == AOFF_AOBF;
case 0x501: {
AOFF_RBTree_t *node = ((AOFFAllctr_t *) a1)->mbc_root;
Uint size = (Uint) a2;
@@ -987,10 +1057,13 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2)
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 0x505: return (UWord) LIST_NEXT(a1);
case 0x506: return (UWord) IS_BLACK((AOFF_RBTree_t *) a1);
+ 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)->bf_within_carrier;
+ case 0x50a: return (UWord) ((AOFFAllctr_t *) a1)->flavor == AOFF_BF;
+ case 0x50b: return (UWord) LIST_PREV(a1);
default: ASSERT(0); return ~((UWord) 0);
}
}
@@ -1049,7 +1122,7 @@ static void print_tree(AOFF_RBTree_t*);
*/
static AOFF_RBTree_t *
-check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint size)
+check_tree(Carrier_t* within_crr, enum AOFF_Flavor flavor, AOFF_RBTree_t* root, Uint size)
{
AOFF_RBTree_t *res = NULL;
Sint blacks;
@@ -1061,6 +1134,7 @@ check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint size)
#ifdef PRINT_TREE
print_tree(root);
#endif
+ ASSERT(within_crr || flavor == AOFF_AOFF);
if (!root)
return res;
@@ -1116,6 +1190,20 @@ check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint size)
ASSERT(crr == within_crr);
ASSERT((char*)x > (char*)crr);
ASSERT(((char*)x + AOFF_BLK_SZ(x)) <= ((char*)crr + CARRIER_SZ(crr)));
+
+ }
+ if (flavor == AOFF_BF) {
+ AOFF_RBTree_t* y = x;
+ AOFF_RBTree_t* nxt = LIST_NEXT(y);
+ ASSERT(IS_TREE_NODE(x));
+ while (nxt) {
+ ASSERT(IS_LIST_ELEM(nxt));
+ ASSERT(AOFF_BLK_SZ(nxt) == AOFF_BLK_SZ(x));
+ ASSERT(FBLK_TO_MBC(&nxt->hdr) == within_crr);
+ ASSERT(LIST_PREV(nxt) == y);
+ y = nxt;
+ nxt = LIST_NEXT(nxt);
+ }
}
if (IS_RED(x)) {
@@ -1127,13 +1215,13 @@ check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint size)
if (x->left) {
ASSERT(x->left->parent == x);
- ASSERT(cmp_blocks(bestfit, x->left, x) < 0);
+ ASSERT(cmp_blocks(flavor, x->left, x) < 0);
ASSERT(x->left->max_sz <= x->max_sz);
}
if (x->right) {
ASSERT(x->right->parent == x);
- ASSERT(cmp_blocks(bestfit, x->right, x) > 0);
+ ASSERT(cmp_blocks(flavor, x->right, x) > 0);
ASSERT(x->right->max_sz <= x->max_sz);
}
ASSERT(x->max_sz >= AOFF_BLK_SZ(x));
@@ -1142,7 +1230,7 @@ check_tree(Carrier_t* within_crr, int bestfit, 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 || cmp_blocks(bestfit, x, res) < 0) {
+ if (!res || cmp_blocks(flavor, 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 87427e8e62..6fa2c0e5bf 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.h
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.h
@@ -24,12 +24,17 @@
#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;
+enum AOFF_Flavor {
+ AOFF_AOFF = 0,
+ AOFF_AOBF = 1,
+ AOFF_BF = 2
+};
+
typedef struct {
- int bf_within_carrier;
+ enum AOFF_Flavor flavor;
} AOFFAllctrInit_t;
#define ERTS_DEFAULT_AOFF_ALLCTR_INIT {0/*dummy*/}
@@ -52,7 +57,7 @@ struct AOFFAllctr_t_ {
Allctr_t allctr; /* Has to be first! */
struct AOFF_RBTree_t_* mbc_root;
- int bf_within_carrier;
+ enum AOFF_Flavor flavor;
};
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 58e53c3d00..41f449bb28 100644
--- a/erts/emulator/beam/erl_bestfit_alloc.c
+++ b/erts/emulator/beam/erl_bestfit_alloc.c
@@ -966,15 +966,17 @@ UWord
erts_bfalc_test(UWord op, UWord a1, UWord a2)
{
switch (op) {
- case 0x200: return (UWord) ((BFAllctr_t *) a1)->address_order;
+ case 0x200: return (UWord) ((BFAllctr_t *) a1)->address_order; /* IS_AOBF */
case 0x201: return (UWord) ((BFAllctr_t *) a1)->mbc_root;
case 0x202: return (UWord) ((RBTree_t *) a1)->parent;
case 0x203: return (UWord) ((RBTree_t *) a1)->left;
case 0x204: return (UWord) ((RBTree_t *) a1)->right;
- case 0x205: return (UWord) ((RBTreeList_t *) a1)->next;
+ case 0x205: return (UWord) LIST_NEXT(a1);
case 0x206: return (UWord) IS_BLACK((RBTree_t *) a1);
case 0x207: return (UWord) IS_TREE_NODE((RBTree_t *) a1);
case 0x208: return (UWord) 1; /* IS_BF_ALGO */
+ case 0x20a: return (UWord) !((BFAllctr_t *) a1)->address_order; /* IS_BF */
+ case 0x20b: return (UWord) LIST_PREV(a1);
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 c37b074f93..2d6c5f9dc7 100644
--- a/erts/emulator/test/alloc_SUITE_data/allocator_test.h
+++ b/erts/emulator/test/alloc_SUITE_data/allocator_test.h
@@ -102,7 +102,8 @@ typedef void* erts_cond;
#define RBT_IS_TREE(T) ((Ulong) ALC_TEST1(RBT_OP(7), (T)))
#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)))
+#define IS_BF(A) ((Ulong) ALC_TEST1(RBT_OP(0xa), (A)))
+#define RBT_PREV(T) ((RBTL_t *) ALC_TEST1(RBT_OP(0xb), (T)))
/* 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 36710bf7b5..9da49a0d14 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", "aoffcaobf", NULL};
+ char *alg[] = {"af", "gf", "bf", "aobf", "aoff", "aoffcbf", "aoffcaobf", 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 702f075304..49df2f0245 100644
--- a/erts/emulator/test/alloc_SUITE_data/rbtree.c
+++ b/erts/emulator/test/alloc_SUITE_data/rbtree.c
@@ -85,23 +85,21 @@ 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, AOFFCAOBF }type;
+ enum { BF, AOBF, AOFF } type;
int i, max_i;
char stk[128];
RBT_t *root, *x, *y, *res;
Ulong x_sz, y_sz, is_x_black;
long blacks, curr_blacks;
+ int have_max_sz;
res = NULL;
- if (IS_BF_ALGO(alc)) {
- if (IS_AOBF(alc)) type = AOBF;
- else type = BF;
- }
- else { /* AOFF_ALGO */
- if (IS_CBF(alc)) type = AOFFCAOBF;
- else type = AOFF;
- }
+ if (IS_AOBF(alc)) type = AOBF;
+ else if (IS_BF(alc)) type = BF;
+ else type = AOFF;
+
+ have_max_sz = !IS_BF_ALGO(alc);
root = RBT_ROOT(alc, size);
@@ -191,17 +189,10 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
break;
case AOFF:
ASSERT(tcs, y < x);
- ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
break;
- case AOFFCAOBF:
- {
- 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;
- }
+ }
+ if (have_max_sz) {
+ ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
}
}
@@ -219,27 +210,22 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
break;
case AOFF:
ASSERT(tcs, y > x);
- ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
break;
- case AOFFCAOBF:
- {
- 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;
- }
+ }
+ if (have_max_sz) {
+ ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
}
}
if (type == BF) {
Ulong l_sz;
- RBTL_t *l = RBT_NEXT(x);
+ RBTL_t *l, *prev=x;
for (l = RBT_NEXT(x); l; l = RBT_NEXT(l)) {
l_sz = BLK_SZ(l);
ASSERT(tcs, l_sz == x_sz);
ASSERT(tcs, !RBT_IS_TREE(l));
+ ASSERT(tcs, RBT_PREV(l) == prev);
+ prev = l;
}
}
@@ -262,18 +248,7 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
res = x;
}
break;
- case AOFFCAOBF:
- 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;
}
-
}
}
@@ -310,7 +285,7 @@ do_check(TestCaseState_t *tcs, Allctr_t *a, Ulong size, int ignore_null)
tmp = ALLOC(a, sz - ABLK_HDR_SZ);
ASSERT(tcs, tmp);
y = UMEM2BLK(tmp);
- if (!(IS_BF_ALGO(a) && !IS_AOBF(a))) {
+ if (!IS_BF(a)) {
ASSERT(tcs, x == y);
}
else {
@@ -488,6 +463,7 @@ testcase_run(TestCaseState_t *tcs)
char *argv2[] = {"-tasaobf", NULL};
char *argv3[] = {"-tasaoff", NULL};
char *argv4[] = {"-tasaoffcaobf", NULL};
+ char *argv5[] = {"-tasaoffcbf", NULL};
Allctr_t *a;
rbtree_test_data *td;
@@ -511,6 +487,7 @@ testcase_run(TestCaseState_t *tcs)
ASSERT(tcs, a);
ASSERT(tcs, IS_BF_ALGO(a));
ASSERT(tcs, !IS_AOBF(a));
+ ASSERT(tcs, IS_BF(a));
test_it(tcs);
@@ -529,6 +506,7 @@ testcase_run(TestCaseState_t *tcs)
ASSERT(tcs, a);
ASSERT(tcs, IS_BF_ALGO(a));
ASSERT(tcs, IS_AOBF(a));
+ ASSERT(tcs, !IS_BF(a));
test_it(tcs);
@@ -546,7 +524,8 @@ testcase_run(TestCaseState_t *tcs)
ASSERT(tcs, a);
ASSERT(tcs, !IS_BF_ALGO(a));
- ASSERT(tcs, !IS_CBF(a));
+ ASSERT(tcs, !IS_AOBF(a));
+ ASSERT(tcs, !IS_BF(a));
test_it(tcs);
test_carrier_migration(tcs);
@@ -556,7 +535,7 @@ testcase_run(TestCaseState_t *tcs)
testcase_printf(tcs, "Address order first fit test succeeded!\n");
- /* Address order first fit, best fit within carrier */
+ /* Address order first fit, aobf within carrier */
testcase_printf(tcs, "Starting test of aoffcaobf...\n");
@@ -565,7 +544,28 @@ testcase_run(TestCaseState_t *tcs)
ASSERT(tcs, a);
ASSERT(tcs, !IS_BF_ALGO(a));
- ASSERT(tcs, IS_CBF(a));
+ ASSERT(tcs, IS_AOBF(a));
+ ASSERT(tcs, !IS_BF(a));
+
+ test_it(tcs);
+ test_carrier_migration(tcs);
+
+ STOP_ALC(a);
+ td->allocator = NULL;
+
+ testcase_printf(tcs, "aoffcaobf test succeeded!\n");
+
+ /* Address order first fit, bf 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, argv5);
+
+ ASSERT(tcs, a);
+ ASSERT(tcs, !IS_BF_ALGO(a));
+ ASSERT(tcs, !IS_AOBF(a));
+ ASSERT(tcs, IS_BF(a));
test_it(tcs);
test_carrier_migration(tcs);