diff options
| -rw-r--r-- | erts/emulator/beam/erl_alloc_util.c | 6 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_alloc_util.h | 3 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_ao_firstfit_alloc.c | 148 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_ao_firstfit_alloc.h | 4 | ||||
| -rw-r--r-- | erts/emulator/test/alloc_SUITE_data/allocator_test.h | 2 | ||||
| -rw-r--r-- | erts/emulator/test/alloc_SUITE_data/rbtree.c | 8 |
6 files changed, 137 insertions, 34 deletions
diff --git a/erts/emulator/beam/erl_alloc_util.c b/erts/emulator/beam/erl_alloc_util.c index bf7d561b00..ce66727fae 100644 --- a/erts/emulator/beam/erl_alloc_util.c +++ b/erts/emulator/beam/erl_alloc_util.c @@ -205,8 +205,6 @@ MBC after deallocating first block: (B)->bhdr = ((Sz) | (F)), \ (B)->u.carrier = (C)) -# define BLK_TO_MBC(B) (IS_FREE_BLK(B) ? FBLK_TO_MBC(B) : ABLK_TO_MBC(B)) - # define IS_MBC_FIRST_ABLK(AP,B) \ ((((UWord)(B) & ~MSEG_UNIT_MASK) == MBC_HEADER_SIZE(AP)) \ && ((B)->bhdr & MBC_ABLK_OFFSET_MASK) == 0) @@ -245,8 +243,6 @@ MBC after deallocating first block: (B)->bhdr = ((Sz) | (F)), \ (B)->carrier = (C)) -# define BLK_TO_MBC(B) ((B)->carrier) - # define IS_MBC_FIRST_BLK(AP,B) \ ((char*)(B) == (char*)((B)->carrier) + MBC_HEADER_SIZE(AP)) # define IS_MBC_FIRST_ABLK(AP,B) IS_MBC_FIRST_BLK(AP,B) @@ -287,8 +283,6 @@ MBC after deallocating first block: #define GET_BLK_HDR_FLGS(B) \ ((B)->bhdr & FLG_MASK) -#define MBC_BLK_SZ(B) (IS_FREE_BLK(B) ? MBC_FBLK_SZ(B) : MBC_ABLK_SZ(B)) - #define NXT_BLK(B) \ (ASSERT(IS_MBC_BLK(B)), \ (Block_t *) (((char *) (B)) + MBC_BLK_SZ((B)))) diff --git a/erts/emulator/beam/erl_alloc_util.h b/erts/emulator/beam/erl_alloc_util.h index af8f72ed7d..1183bf901d 100644 --- a/erts/emulator/beam/erl_alloc_util.h +++ b/erts/emulator/beam/erl_alloc_util.h @@ -306,10 +306,13 @@ typedef struct { (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)))) +# define BLK_TO_MBC(B) (IS_FREE_BLK(B) ? FBLK_TO_MBC(B) : ABLK_TO_MBC(B)) #else # define FBLK_TO_MBC(B) ((B)->carrier) # define ABLK_TO_MBC(B) ((B)->carrier) +# define BLK_TO_MBC(B) ((B)->carrier) #endif +#define MBC_BLK_SZ(B) (IS_FREE_BLK(B) ? MBC_FBLK_SZ(B) : MBC_ABLK_SZ(B)) typedef UWord FreeBlkFtr_t; /* Footer of a free block */ diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c index 1570daf90e..50cbfc5033 100644 --- a/erts/emulator/beam/erl_ao_firstfit_alloc.c +++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c @@ -98,7 +98,17 @@ struct AOFF_RBTree_t_ { }; #define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr) +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; +}; + #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); #endif @@ -140,8 +150,8 @@ static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node, 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)) { + ASSERT(FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr)); + if (alc->bf_within_carrier) { SWord diff = (SWord)AOFF_BLK_SZ(lhs) - (SWord)AOFF_BLK_SZ(rhs); if (diff) return diff; } @@ -152,11 +162,8 @@ 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 (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; } } @@ -168,6 +175,8 @@ static ERTS_INLINE SWord cmp_cand_blk(AOFFAllctr_t* alc, static Block_t* aoff_get_free_block(Allctr_t *, Uint, Block_t *, Uint, Uint32 flags); 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 Eterm info_options(Allctr_t *, char *, int *, void *, Uint **, Uint *); static void init_atoms(void); @@ -216,7 +225,7 @@ 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->mbc_header_size = sizeof(Carrier_t); + 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); @@ -233,8 +242,8 @@ erts_aoffalc_start(AOFFAllctr_t *alc, allctr->info_options = info_options; allctr->get_next_mbc_size = NULL; - allctr->creating_mbc = NULL; - allctr->destroying_mbc = NULL; + allctr->creating_mbc = aoff_creating_mbc; + allctr->destroying_mbc = aoff_destroying_mbc; allctr->init_atoms = init_atoms; #ifdef ERTS_ALLOC_UTIL_HARD_DEBUG @@ -439,9 +448,11 @@ tree_insert_fixup(AOFF_RBTree_t** root, AOFF_RBTree_t *blk) static void aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags) { +#ifdef HARD_DEBUG AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr; - AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC) - ? &alc->sbmbc_root : &alc->mbc_root); +#endif + AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(del); + AOFF_RBTree_t **root = &crr->root; Uint spliced_is_black; AOFF_RBTree_t *x, *y, *z = (AOFF_RBTree_t *) del; AOFF_RBTree_t null_x; /* null_x is used to get the fixup started when we @@ -450,6 +461,7 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags) null_x.parent = NULL; #ifdef HARD_DEBUG + check_carriers(alc, crr, flags); check_tree(alc, *root, 0); #endif @@ -619,14 +631,16 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags) { AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr; AOFF_RBTree_t *blk = (AOFF_RBTree_t *) block; - AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC) - ? &alc->sbmbc_root : &alc->mbc_root); + AOFF_RBTree_t **root; + AOFF_Carrier_t *blk_crr = (AOFF_Carrier_t*) FBLK_TO_MBC(block); Uint blk_sz = AOFF_BLK_SZ(blk); #ifdef HARD_DEBUG - check_tree(alc, *root, 0); + check_carriers(alc, blk_crr, flags); + check_tree(alc, blk_crr->root, 0); #endif + root = &blk_crr->root; blk->flags = 0; blk->left = NULL; blk->right = NULL; @@ -659,7 +673,6 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags) } x = x->right; } - } /* Insert block into size tree */ @@ -680,15 +693,32 @@ 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_RBTree_t *x = ((flags & ERTS_ALCU_FLG_SBMBC) - ? alc->sbmbc_root : alc->mbc_root); - AOFF_RBTree_t *blk = NULL; + AOFF_Carrier_t *crr = ((flags & ERTS_ALCU_FLG_SBMBC) + ? alc->sbmbc_first : alc->mbc_first); + AOFF_RBTree_t *x, *blk = NULL; #ifdef HARD_DEBUG - AOFF_RBTree_t* dbg_blk = check_tree(alc, x, size); + 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; + } + + /* Get block within carrier tree + */ + x = crr->root; +#ifdef HARD_DEBUG + dbg_blk = check_tree(alc, x, size); +#endif + while (x) { if (x->left && x->left->max_sz >= size) { x = x->left; @@ -718,6 +748,54 @@ aoff_get_free_block(Allctr_t *allctr, Uint size, return (Block_t *) blk; } +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; + + + /* Link carrier in address order + */ + 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; + } + + /* aoff_link_free_block will add free block later */ + crr->root = NULL; +} + +static void aoff_destroying_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); + + /* Unlink carrier + */ + 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; + } +} + /* * info_options() @@ -822,7 +900,18 @@ UWord erts_aoffalc_test(UWord op, UWord a1, UWord a2) { switch (op) { - case 0x501: return (UWord) ((AOFFAllctr_t *) a1)->mbc_root; + case 0x501: { + AOFF_Carrier_t* crr = ((AOFFAllctr_t *) a1)->mbc_first; + 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; + } 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; @@ -842,6 +931,23 @@ 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); +} + + #define IS_LEFT_VISITED(FB) ((FB)->flags & LEFT_VISITED_FLG) #define IS_RIGHT_VISITED(FB) ((FB)->flags & RIGHT_VISITED_FLG) diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.h b/erts/emulator/beam/erl_ao_firstfit_alloc.h index 36995a20f0..a8fa69ab79 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_RBTree_t_* mbc_root; - struct AOFF_RBTree_t_* sbmbc_root; + struct AOFF_Carrier_t_* mbc_first; + struct AOFF_Carrier_t_* sbmbc_first; int bf_within_carrier; }; diff --git a/erts/emulator/test/alloc_SUITE_data/allocator_test.h b/erts/emulator/test/alloc_SUITE_data/allocator_test.h index ec5bb9dcd6..c08398d40f 100644 --- a/erts/emulator/test/alloc_SUITE_data/allocator_test.h +++ b/erts/emulator/test/alloc_SUITE_data/allocator_test.h @@ -85,7 +85,7 @@ typedef void* erts_cond; /* From erl_bestfit_alloc.c and erl_ao_firstfit_alloc.c */ #define IS_AOBF(A) ((Ulong) ALC_TEST1(RBT_OP(0), (A))) -#define RBT_ROOT(A) ((RBT_t *) ALC_TEST1(RBT_OP(1), (A))) +#define RBT_ROOT(A,SZ) ((RBT_t *) ALC_TEST2(RBT_OP(1), (A), (SZ))) #define RBT_PARENT(T) ((RBT_t *) ALC_TEST1(RBT_OP(2), (T))) #define RBT_LEFT(T) ((RBT_t *) ALC_TEST1(RBT_OP(3), (T))) #define RBT_RIGHT(T) ((RBT_t *) ALC_TEST1(RBT_OP(4), (T))) diff --git a/erts/emulator/test/alloc_SUITE_data/rbtree.c b/erts/emulator/test/alloc_SUITE_data/rbtree.c index 105c9c0eb4..bdada7ca33 100644 --- a/erts/emulator/test/alloc_SUITE_data/rbtree.c +++ b/erts/emulator/test/alloc_SUITE_data/rbtree.c @@ -103,7 +103,7 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) else type = AOFF; } - root = RBT_ROOT(alc); + root = RBT_ROOT(alc, size); #ifdef PRINT_TREE print_tree(tcs, root); @@ -369,9 +369,9 @@ test_it(TestCaseState_t *tcs) do_check(tcs, a, 300); } - ASSERT(tcs, RBT_ROOT(a)); - ASSERT(tcs, !RBT_LEFT(RBT_ROOT(a))); - ASSERT(tcs, !RBT_RIGHT(RBT_ROOT(a))); + ASSERT(tcs, RBT_ROOT(a,0)); + ASSERT(tcs, !RBT_LEFT(RBT_ROOT(a,0))); + ASSERT(tcs, !RBT_RIGHT(RBT_ROOT(a,0))); } |