aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2013-05-17 14:47:08 +0200
committerSverker Eriksson <[email protected]>2013-06-03 14:24:24 +0200
commite5bbae8ae46bb11ab1c4f1a5e4e671d7a888ad84 (patch)
tree51a57d316842a93edaad9c4c01790857c7ca8828
parentc6a4999a5e6692f35cf384b854595db6302039b9 (diff)
downloadotp-e5bbae8ae46bb11ab1c4f1a5e4e671d7a888ad84.tar.gz
otp-e5bbae8ae46bb11ab1c4f1a5e4e671d7a888ad84.tar.bz2
otp-e5bbae8ae46bb11ab1c4f1a5e4e671d7a888ad84.zip
erts: Change naive list to rb-tree of carriers in AOFF allocator
and add new callbacks add_mbc(), remove_mbc() and largest_fblk_in_mbc() for carrier migration.
-rw-r--r--erts/emulator/beam/erl_afit_alloc.c3
-rw-r--r--erts/emulator/beam/erl_alloc_util.h6
-rw-r--r--erts/emulator/beam/erl_ao_firstfit_alloc.c339
-rw-r--r--erts/emulator/beam/erl_ao_firstfit_alloc.h4
-rw-r--r--erts/emulator/beam/erl_bestfit_alloc.c3
-rw-r--r--erts/emulator/beam/erl_goodfit_alloc.c4
6 files changed, 224 insertions, 135 deletions
diff --git a/erts/emulator/beam/erl_afit_alloc.c b/erts/emulator/beam/erl_afit_alloc.c
index d03d6a591c..608a4dd26d 100644
--- a/erts/emulator/beam/erl_afit_alloc.c
+++ b/erts/emulator/beam/erl_afit_alloc.c
@@ -101,6 +101,9 @@ erts_afalc_start(AFAllctr_t *afallctr,
allctr->get_next_mbc_size = NULL;
allctr->creating_mbc = NULL;
allctr->destroying_mbc = NULL;
+ allctr->add_mbc = NULL;
+ allctr->remove_mbc = NULL;
+ allctr->largest_fblk_in_mbc = NULL;
allctr->init_atoms = init_atoms;
#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
diff --git a/erts/emulator/beam/erl_alloc_util.h b/erts/emulator/beam/erl_alloc_util.h
index 1183bf901d..739871957c 100644
--- a/erts/emulator/beam/erl_alloc_util.h
+++ b/erts/emulator/beam/erl_alloc_util.h
@@ -475,6 +475,12 @@ struct Allctr_t_ {
Uint (*get_next_mbc_size) (Allctr_t *);
void (*creating_mbc) (Allctr_t *, Carrier_t *, Uint32);
void (*destroying_mbc) (Allctr_t *, Carrier_t *, Uint32);
+
+ /* The three callbacks below are needed to support carrier migration */
+ void (*add_mbc) (Allctr_t *, Carrier_t *, Uint32);
+ void (*remove_mbc) (Allctr_t *, Carrier_t *, Uint32);
+ UWord (*largest_fblk_in_mbc) (Allctr_t *, Carrier_t *);
+
void (*init_atoms) (void);
#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index 50cbfc5033..dbf930509f 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -29,15 +29,15 @@
* This module is a callback-module for erl_alloc_util.c
*
* AOFF Algorithm:
- * The tree nodes are free-blocks ordered in address order.
+ * The tree nodes are 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
+ * 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:
* 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.
+ * sorting order. Blocks within the same carrier are sorted
+ * wrt size instead of address.
*
* Authors: Rickard Green/Sverker Eriksson
*/
@@ -90,11 +90,11 @@ typedef struct AOFF_RBTree_t_ AOFF_RBTree_t;
struct AOFF_RBTree_t_ {
Block_t hdr;
- Uint flags;
AOFF_RBTree_t *parent;
AOFF_RBTree_t *left;
AOFF_RBTree_t *right;
- Uint max_sz; /* of all blocks in this sub-tree */
+ Uint32 flags;
+ Uint32 max_sz; /* of all blocks in this sub-tree */
};
#define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
@@ -102,19 +102,33 @@ typedef struct AOFF_Carrier_t_ AOFF_Carrier_t;
struct AOFF_Carrier_t_ {
Carrier_t crr;
- AOFF_Carrier_t* next;
- AOFF_Carrier_t** prevp;
- AOFF_RBTree_t* root;
+ AOFF_RBTree_t rbt_node; /* My node in the carrier tree */
+ AOFF_RBTree_t* root; /* Root of the block tree */
};
+#define RBT_NODE_TO_MBC(PTR) ((AOFF_Carrier_t*)((char*)(PTR) - offsetof(AOFF_Carrier_t, rbt_node)))
+
+/*
+ To support carrier migration we keep two kinds of rb-trees:
+ 1. One tree of carriers for each allocator instance.
+ 2. One tree of free blocks for each carrier.
+ Both trees use the same node structure AOFF_RBTree_t and implementation.
+ Carrier nodes thus contain a phony Block_t header 'rbt_node.hdr'.
+ The size value of such a phony block is the size of the largest free block in
+ that carrier, i.e same as 'max_sz' of the root node of its block tree.
+*/
#ifdef HARD_DEBUG
-static void check_carriers(AOFFAllctr_t* alc, AOFF_Carrier_t *crr, Uint32 flags);
-static AOFF_RBTree_t * check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint);
+# 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);
+#else
+# define HARD_CHECK_IS_MEMBER(ROOT,NODE)
+# define HARD_CHECK_TREE(CRR,BF,ROOT,SZ)
#endif
-/* Calculate 'max_size' of tree node x by only looking at the direct children
- * of x and x itself.
+/* Calculate 'max_sz' of tree node x by only looking at 'max_sz' of the
+ * direct children of x and the size x itself.
*/
static ERTS_INLINE Uint node_max_size(AOFF_RBTree_t *x)
{
@@ -128,7 +142,7 @@ static ERTS_INLINE Uint node_max_size(AOFF_RBTree_t *x)
return sz;
}
-/* Set new possibly lower 'max_size' of node and propagate change toward root
+/* Set new possibly lower 'max_sz' of node and propagate change toward root
*/
static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
AOFF_RBTree_t* stop_at)
@@ -147,21 +161,21 @@ 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,
+static ERTS_INLINE SWord cmp_blocks(int bestfit,
AOFF_RBTree_t* lhs, AOFF_RBTree_t* rhs)
{
- ASSERT(FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr));
- if (alc->bf_within_carrier) {
+ ASSERT(!bestfit || FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr));
+ if (bestfit) {
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,
+static ERTS_INLINE SWord cmp_cand_blk(int bestfit,
Block_t* cand_blk, AOFF_RBTree_t* rhs)
{
- if (alc->bf_within_carrier) {
+ if (bestfit) {
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;
@@ -176,7 +190,17 @@ static Block_t* aoff_get_free_block(Allctr_t *, Uint, Block_t *, Uint, Uint32 fl
static void aoff_link_free_block(Allctr_t *, Block_t*, Uint32 flags);
static void aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags);
static void aoff_creating_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
-static void aoff_destroying_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
+static void aoff_add_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
+static void aoff_remove_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
+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 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 *, int *, void *, Uint **, Uint *);
static void init_atoms(void);
@@ -243,7 +267,10 @@ erts_aoffalc_start(AOFFAllctr_t *alc,
allctr->get_next_mbc_size = NULL;
allctr->creating_mbc = aoff_creating_mbc;
- allctr->destroying_mbc = aoff_destroying_mbc;
+ allctr->destroying_mbc = aoff_remove_mbc;
+ allctr->add_mbc = aoff_add_mbc;
+ allctr->remove_mbc = aoff_remove_mbc;
+ allctr->largest_fblk_in_mbc = aoff_largest_fblk_in_mbc;
allctr->init_atoms = init_atoms;
#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
@@ -449,21 +476,45 @@ static void
aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
{
#ifdef HARD_DEBUG
- AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+ AOFFAllctr_t* alc = (AOFFAllctr_t*)allctr;
#endif
AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(del);
- AOFF_RBTree_t **root = &crr->root;
+
+ ASSERT(crr->rbt_node.hdr.bhdr == crr->root->max_sz);
+ HARD_CHECK_IS_MEMBER(((flags & ERTS_ALCU_FLG_SBMBC) ? alc->sbmbc_root : alc->mbc_root),
+ &crr->rbt_node);
+ HARD_CHECK_TREE(&crr->crr, alc->bf_within_carrier, crr->root, 0);
+
+ rbt_delete(&crr->root, (AOFF_RBTree_t*)del);
+
+ HARD_CHECK_TREE(&crr->crr, alc->bf_within_carrier, crr->root, 0);
+
+ /* 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;
+ }
+ ASSERT(crr->rbt_node.hdr.bhdr > crr->root->max_sz);
+ crr->rbt_node.hdr.bhdr = crr->root->max_sz;
+ }
+ else {
+ crr->rbt_node.hdr.bhdr = 0;
+ }
+ lower_max_size(&crr->rbt_node, NULL);
+}
+
+static void
+rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del)
+{
Uint spliced_is_black;
- AOFF_RBTree_t *x, *y, *z = (AOFF_RBTree_t *) del;
+ AOFF_RBTree_t *x, *y, *z = del;
AOFF_RBTree_t null_x; /* null_x is used to get the fixup started when we
splice out a node without children. */
- null_x.parent = NULL;
+ HARD_CHECK_IS_MEMBER(*root, del);
-#ifdef HARD_DEBUG
- check_carriers(alc, crr, flags);
- check_tree(alc, *root, 0);
-#endif
+ null_x.parent = NULL;
/* Remove node from tree... */
@@ -618,29 +669,47 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
RBT_ASSERT(!null_x.right);
}
}
-
DESTROY_TREE_NODE(del);
-
-#ifdef HARD_DEBUG
- check_tree(alc, *root, 0);
-#endif
}
static void
aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
{
- AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+ AOFFAllctr_t* alc = (AOFFAllctr_t*) allctr;
AOFF_RBTree_t *blk = (AOFF_RBTree_t *) block;
- AOFF_RBTree_t **root;
+ AOFF_RBTree_t *crr_node;
AOFF_Carrier_t *blk_crr = (AOFF_Carrier_t*) FBLK_TO_MBC(block);
Uint blk_sz = AOFF_BLK_SZ(blk);
-#ifdef HARD_DEBUG
- check_carriers(alc, blk_crr, flags);
- check_tree(alc, blk_crr->root, 0);
-#endif
+ ASSERT(allctr == blk_crr->crr.allctr);
+ ASSERT(blk_crr->rbt_node.hdr.bhdr == (blk_crr->root ? blk_crr->root->max_sz : 0));
+
+ HARD_CHECK_IS_MEMBER(((flags & ERTS_ALCU_FLG_SBMBC) ? alc->sbmbc_root : alc->mbc_root),
+ &blk_crr->rbt_node);
+ HARD_CHECK_TREE(&blk_crr->crr, alc->bf_within_carrier, blk_crr->root, 0);
+
+ rbt_insert(alc->bf_within_carrier, &blk_crr->root, blk);
+
+ /* Update the carrier tree with a potential 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;
+ }
+ }
+ HARD_CHECK_TREE(&blk_crr->crr, alc->bf_within_carrier, blk_crr->root, 0);
+}
+
+static void
+rbt_insert(int bestfit, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
+{
+ Uint blk_sz = AOFF_BLK_SZ(blk);
- root = &blk_crr->root;
blk->flags = 0;
blk->left = NULL;
blk->right = NULL;
@@ -657,7 +726,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 (cmp_blocks(alc, blk, x) < 0) {
+ if (cmp_blocks(bestfit, blk, x) < 0) {
if (!x->left) {
blk->parent = x;
x->left = blk;
@@ -682,10 +751,28 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
if (IS_RED(blk->parent))
tree_insert_fixup(root, blk);
}
+}
-#ifdef HARD_DEBUG
- check_tree(alc, *root, 0);
-#endif
+static AOFF_RBTree_t*
+rbt_search(AOFF_RBTree_t* root, Uint size)
+{
+ AOFF_RBTree_t* x = root;
+
+ ASSERT(x);
+ for (;;) {
+ if (x->left && x->left->max_sz >= size) {
+ x = x->left;
+ }
+ else if (AOFF_BLK_SZ(x) >= size) {
+ return x;
+ }
+ else {
+ x = x->right;
+ if (!x) {
+ return NULL;
+ }
+ }
+ }
}
static Block_t *
@@ -693,44 +780,31 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
Block_t *cand_blk, Uint cand_size, Uint32 flags)
{
AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
- AOFF_Carrier_t *crr = ((flags & ERTS_ALCU_FLG_SBMBC)
- ? alc->sbmbc_first : alc->mbc_first);
- AOFF_RBTree_t *x, *blk = NULL;
+ AOFF_RBTree_t *crr_node = ((flags & ERTS_ALCU_FLG_SBMBC)
+ ? alc->sbmbc_root : alc->mbc_root);
+ AOFF_Carrier_t* crr;
+ AOFF_RBTree_t *blk = NULL;
#ifdef HARD_DEBUG
AOFF_RBTree_t* dbg_blk;
#endif
-
+
ASSERT(!cand_blk || cand_size >= size);
/* Get first-fit carrier
*/
- for (;;) {
- if (!crr)
- return NULL;
- if (crr->root && crr->root->max_sz >= size)
- break;
- crr = crr->next;
+ if (!crr_node || !(blk=rbt_search(crr_node, size))) {
+ return NULL;
}
+ crr = RBT_NODE_TO_MBC(blk);
/* Get block within carrier tree
*/
- x = crr->root;
#ifdef HARD_DEBUG
- dbg_blk = check_tree(alc, x, size);
+ dbg_blk = HARD_CHECK_TREE(&crr->crr, alc->bf_within_carrier, crr->root, size);
#endif
- while (x) {
- if (x->left && x->left->max_sz >= size) {
- x = x->left;
- }
- else if (AOFF_BLK_SZ(x) >= size) {
- blk = x;
- break;
- }
- else {
- x = x->right;
- }
- }
+ blk = rbt_search(crr->root, size);
+ ASSERT(blk);
#ifdef HARD_DEBUG
ASSERT(blk == dbg_blk);
@@ -739,7 +813,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
if (!blk)
return NULL;
- if (cand_blk && cmp_cand_blk(alc, cand_blk, blk) < 0) {
+ if (cand_blk && cmp_cand_blk(alc->bf_within_carrier, cand_blk, blk) < 0) {
return NULL; /* cand_blk was better */
}
@@ -752,50 +826,61 @@ static void aoff_creating_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags
{
AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
- AOFF_Carrier_t **prevp = ((flags & ERTS_ALCU_FLG_SBMBC)
- ? &alc->sbmbc_first : &alc->mbc_first);
- AOFF_Carrier_t *p;
+ AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC)
+ ? &alc->sbmbc_root : &alc->mbc_root);
+ HARD_CHECK_TREE(NULL, 0, *root, 0);
- /* Link carrier in address order
+ /* Link carrier in address order tree
*/
- for (p = *prevp; p && crr > p; p = p->next) {
- prevp = &p->next;
- }
- ASSERT(crr != p);
-
- crr->next = p;
- crr->prevp = prevp;
- *prevp = crr;
- if (p) {
- ASSERT(prevp == p->prevp);
- p->prevp = &crr->next;
- }
+ crr->rbt_node.hdr.bhdr = 0;
+ rbt_insert(0, root, &crr->rbt_node);
/* aoff_link_free_block will add free block later */
crr->root = NULL;
+
+ HARD_CHECK_TREE(NULL, 0, *root, 0);
}
-static void aoff_destroying_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags)
+static void aoff_add_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags)
{
AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
- AOFF_Carrier_t **pp = ((flags & ERTS_ALCU_FLG_SBMBC)
- ? &alc->sbmbc_first : &alc->mbc_first);
+ AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC)
+ ? &alc->sbmbc_root : &alc->mbc_root);
+
+ HARD_CHECK_TREE(NULL, 0, *root, 0);
- /* Unlink carrier
+ /* Link carrier in address order tree
*/
- while (*pp != crr) {
- ASSERT(*pp && (*pp)->prevp == pp);
- pp = &(*pp)->next;
- }
- *pp = crr->next;
- if (crr->next) {
- ASSERT(crr->next->prevp == &crr->next);
- crr->next->prevp = crr->prevp;
- }
+ rbt_insert(0, root, &crr->rbt_node);
+
+ HARD_CHECK_TREE(NULL, 0, *root, 0);
+}
+
+static void aoff_remove_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags)
+{
+ AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+ AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+ AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC)
+ ? &alc->sbmbc_root : &alc->mbc_root);
+
+ ASSERT(allctr == carrier->allctr);
+ HARD_CHECK_TREE(NULL, 0, *root, 0);
+
+ rbt_delete(root, &crr->rbt_node);
+
+ HARD_CHECK_TREE(NULL, 0, *root, 0);
}
+static UWord aoff_largest_fblk_in_mbc(Allctr_t* allctr, Carrier_t* carrier)
+{
+ AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+
+ ASSERT(allctr == carrier->allctr);
+ ASSERT(crr->rbt_node.hdr.bhdr == (crr->root ? crr->root->max_sz : 0));
+ return crr->rbt_node.hdr.bhdr;
+}
/*
* info_options()
@@ -901,16 +986,10 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2)
{
switch (op) {
case 0x501: {
- AOFF_Carrier_t* crr = ((AOFFAllctr_t *) a1)->mbc_first;
+ AOFF_RBTree_t *node = ((AOFFAllctr_t *) a1)->mbc_root;
Uint size = (Uint) a2;
- for (;;) {
- if (!crr)
- return (UWord)NULL;
- if (crr->root && crr->root->max_sz >= size)
- break;
- crr = crr->next;
- }
- return (UWord) crr->root;
+ node = rbt_search(node, size);
+ return (UWord) (node ? RBT_NODE_TO_MBC(node)->root : NULL);
}
case 0x502: return (UWord) ((AOFF_RBTree_t *) a1)->parent;
case 0x503: return (UWord) ((AOFF_RBTree_t *) a1)->left;
@@ -931,23 +1010,16 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2)
#ifdef HARD_DEBUG
-static void check_carriers(AOFFAllctr_t* alc, AOFF_Carrier_t *crr, Uint32 flags)
-{
- AOFF_Carrier_t *p = ((flags & ERTS_ALCU_FLG_SBMBC)
- ? alc->sbmbc_first : alc->mbc_first);
- int found_it = 0;
-
- for ( ; p; p = p->next) {
- if (p == crr) {
- ASSERT(!found_it);
- found_it = 1;
- }
- ASSERT(!p->next || p->next > p);
- }
- ASSERT(found_it);
+static int rbt_assert_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);
+ node = node->parent;
+ }
+ return 1;
}
-
#define IS_LEFT_VISITED(FB) ((FB)->flags & LEFT_VISITED_FLG)
#define IS_RIGHT_VISITED(FB) ((FB)->flags & RIGHT_VISITED_FLG)
@@ -984,7 +1056,7 @@ static void print_tree(AOFF_RBTree_t*);
*/
static AOFF_RBTree_t *
-check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint size)
+check_tree(Carrier_t* within_crr, int bestfit, AOFF_RBTree_t* root, Uint size)
{
AOFF_RBTree_t *res = NULL;
Sint blacks;
@@ -1046,9 +1118,12 @@ check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint size)
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 (within_crr) {
+ crr = FBLK_TO_MBC(&x->hdr);
+ ASSERT(crr == within_crr);
+ 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));
@@ -1059,13 +1134,13 @@ check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint size)
if (x->left) {
ASSERT(x->left->parent == x);
- ASSERT(cmp_blocks(alc, x->left, x) < 0);
+ ASSERT(cmp_blocks(bestfit, x->left, x) < 0);
ASSERT(x->left->max_sz <= x->max_sz);
}
if (x->right) {
ASSERT(x->right->parent == x);
- ASSERT(cmp_blocks(alc, x->right, x) > 0);
+ ASSERT(cmp_blocks(bestfit, x->right, x) > 0);
ASSERT(x->right->max_sz <= x->max_sz);
}
ASSERT(x->max_sz >= AOFF_BLK_SZ(x));
@@ -1074,7 +1149,7 @@ check_tree(AOFFAllctr_t* alc, 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(alc, x, res) < 0) {
+ if (!res || cmp_blocks(bestfit, x, res) < 0) {
res = x;
}
}
@@ -1113,9 +1188,9 @@ print_tree_aux(AOFF_RBTree_t *x, int indent)
for (i = 0; i < indent; i++) {
putc(' ', stderr);
}
- fprintf(stderr, "%s: sz=%lu addr=0x%lx max_size=%lu\r\n",
+ fprintf(stderr, "%s: sz=%lu addr=0x%lx max_size=%u\r\n",
IS_BLACK(x) ? "BLACK" : "RED",
- AOFF_BLK_SZ(x), (Uint)x, x->max_sz);
+ AOFF_BLK_SZ(x), (Uint)x, (unsigned)x->max_sz);
print_tree_aux(x->left, indent + INDENT_STEP);
}
}
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.h b/erts/emulator/beam/erl_ao_firstfit_alloc.h
index a8fa69ab79..36995a20f0 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.h
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.h
@@ -51,8 +51,8 @@ Allctr_t *erts_aoffalc_start(AOFFAllctr_t *, AOFFAllctrInit_t*, AllctrInit_t *);
struct AOFFAllctr_t_ {
Allctr_t allctr; /* Has to be first! */
- struct AOFF_Carrier_t_* mbc_first;
- struct AOFF_Carrier_t_* sbmbc_first;
+ struct AOFF_RBTree_t_* mbc_root;
+ struct AOFF_RBTree_t_* sbmbc_root;
int bf_within_carrier;
};
diff --git a/erts/emulator/beam/erl_bestfit_alloc.c b/erts/emulator/beam/erl_bestfit_alloc.c
index 42c7c9bbe2..dff69faa4e 100644
--- a/erts/emulator/beam/erl_bestfit_alloc.c
+++ b/erts/emulator/beam/erl_bestfit_alloc.c
@@ -208,6 +208,9 @@ erts_bfalc_start(BFAllctr_t *bfallctr,
allctr->get_next_mbc_size = NULL;
allctr->creating_mbc = NULL;
allctr->destroying_mbc = NULL;
+ allctr->add_mbc = NULL;
+ allctr->remove_mbc = NULL;
+ allctr->largest_fblk_in_mbc = NULL;
allctr->init_atoms = init_atoms;
#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
diff --git a/erts/emulator/beam/erl_goodfit_alloc.c b/erts/emulator/beam/erl_goodfit_alloc.c
index fce443c101..72620a362b 100644
--- a/erts/emulator/beam/erl_goodfit_alloc.c
+++ b/erts/emulator/beam/erl_goodfit_alloc.c
@@ -223,7 +223,9 @@ erts_gfalc_start(GFAllctr_t *gfallctr,
allctr->get_next_mbc_size = NULL;
allctr->creating_mbc = update_last_aux_mbc;
allctr->destroying_mbc = update_last_aux_mbc;
-
+ allctr->add_mbc = NULL;
+ allctr->remove_mbc = NULL;
+ allctr->largest_fblk_in_mbc = NULL;
allctr->init_atoms = init_atoms;
#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG