diff options
Diffstat (limited to 'erts/emulator/beam/erl_ao_firstfit_alloc.c')
-rw-r--r-- | erts/emulator/beam/erl_ao_firstfit_alloc.c | 129 |
1 files changed, 58 insertions, 71 deletions
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c index 73576c0189..917cb1cf10 100644 --- a/erts/emulator/beam/erl_ao_firstfit_alloc.c +++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c @@ -1,7 +1,7 @@ /* * %CopyrightBegin% * - * Copyright Ericsson AB 2003-2016. All Rights Reserved. + * Copyright Ericsson AB 2003-2018. All Rights Reserved. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -100,22 +100,14 @@ #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) +#define AOFF_LIST_NEXT(N) (((AOFF_RBTree_t*)(N))->u.next) +#define AOFF_LIST_PREV(N) (((AOFF_RBTree_t*)(N))->parent) 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 */ - Sint64 birth_time; AOFF_RBTree_t* root; /* Root of my block tree */ }; #define RBT_NODE_TO_MBC(PTR) ErtsContainerStruct((PTR), AOFF_Carrier_t, rbt_node) @@ -160,13 +152,13 @@ static ERTS_INLINE Uint node_max_size(AOFF_RBTree_t *x) static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node, AOFF_RBTree_t* stop_at) { - AOFF_RBTree_t* x = node; + AOFF_RBTree_t* x = node; Uint old_max = x->max_sz; Uint new_max = node_max_size(x); if (new_max < old_max) { x->max_sz = new_max; - while ((x=x->parent) != stop_at && x->max_sz == old_max) { + while ((x=x->parent) != stop_at && x->max_sz == old_max) { x->max_sz = node_max_size(x); } ASSERT(x == stop_at || x->max_sz > old_max); @@ -174,7 +166,6 @@ 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 */ @@ -193,7 +184,6 @@ void erts_aoff_larger_max_size(AOFF_RBTree_t *node) break; } } -#endif /* Compare nodes for both carrier and block trees */ static ERTS_INLINE SWord cmp_blocks(enum AOFFSortOrder order, @@ -201,9 +191,7 @@ static ERTS_INLINE SWord cmp_blocks(enum AOFFSortOrder order, { ASSERT(lhs != rhs); if (order == FF_AGEFF) { - AOFF_Carrier_t* lc = RBT_NODE_TO_MBC(lhs); - AOFF_Carrier_t* rc = RBT_NODE_TO_MBC(rhs); - Sint64 diff = lc->birth_time - rc->birth_time; + Sint64 diff = lhs->u.birth_time - rhs->u.birth_time; #ifdef ARCH_64 if (diff) return diff; @@ -298,8 +286,10 @@ erts_aoffalc_start(AOFFAllctr_t *alc, 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 = (aoffinit->blk_order == FF_BF ? - sizeof(AOFF_RBTreeList_t):sizeof(AOFF_RBTree_t)); + allctr->min_block_size = (aoffinit->blk_order == FF_BF + ? (offsetof(AOFF_RBTree_t, u.next) + + ErtsSizeofMember(AOFF_RBTree_t, u.next)) + : offsetof(AOFF_RBTree_t, u)); allctr->vsn_str = ERTS_ALC_AOFF_ALLOC_VSN_STR; @@ -362,7 +352,7 @@ left_rotate(AOFF_RBTree_t **root, AOFF_RBTree_t *x) x->parent = y; y->max_sz = x->max_sz; - x->max_sz = node_max_size(x); + x->max_sz = node_max_size(x); ASSERT(y->max_sz >= x->max_sz); } @@ -387,7 +377,7 @@ right_rotate(AOFF_RBTree_t **root, AOFF_RBTree_t *x) y->right = x; x->parent = y; y->max_sz = x->max_sz; - x->max_sz = node_max_size(x); + x->max_sz = node_max_size(x); ASSERT(y->max_sz >= x->max_sz); } @@ -533,23 +523,23 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *blk) 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); + ASSERT(AOFF_LIST_PREV(del)); + ASSERT(AOFF_LIST_PREV(del)->flags & IS_BF_FLG); + AOFF_LIST_NEXT(AOFF_LIST_PREV(del)) = AOFF_LIST_NEXT(del); + if (AOFF_LIST_NEXT(del)) { + ASSERT(AOFF_LIST_NEXT(del)->flags & IS_BF_FLG); + AOFF_LIST_PREV(AOFF_LIST_NEXT(del)) = AOFF_LIST_PREV(del); } return; } - else if (LIST_NEXT(del)) { + else if (AOFF_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)); - + + ASSERT(AOFF_BLK_SZ(AOFF_LIST_NEXT(del)) == AOFF_BLK_SZ(del)); + ASSERT(IS_LIST_ELEM(AOFF_LIST_NEXT(del))); + + replace(&crr->root, (AOFF_RBTree_t*)del, AOFF_LIST_NEXT(del)); + HARD_CHECK_TREE(&crr->crr, alc->blk_order, crr->root, 0); return; } @@ -560,13 +550,13 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *blk) HARD_CHECK_TREE(&crr->crr, alc->blk_order, 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; + crr->rbt_node.hdr.bhdr = crr->root->max_sz; } else { crr->rbt_node.hdr.bhdr = 0; @@ -783,7 +773,7 @@ rbt_insert(enum AOFFSortOrder order, AOFF_RBTree_t** root, AOFF_RBTree_t* blk) #ifdef DEBUG blk->flags = (order == FF_BF) ? IS_BF_FLG : 0; #else - blk->flags = 0; + blk->flags = 0; #endif blk->left = NULL; blk->right = NULL; @@ -797,7 +787,7 @@ rbt_insert(enum AOFFSortOrder order, AOFF_RBTree_t** root, AOFF_RBTree_t* blk) else { AOFF_RBTree_t *x = *root; while (1) { - SWord diff; + SWord diff; if (x->max_sz < blk_sz) { x->max_sz = blk_sz; } @@ -820,14 +810,14 @@ rbt_insert(enum AOFFSortOrder order, AOFF_RBTree_t** root, AOFF_RBTree_t* blk) } else { ASSERT(order == FF_BF); - ASSERT(blk->flags & IS_BF_FLG); - ASSERT(x->flags & IS_BF_FLG); + 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; + AOFF_LIST_NEXT(blk) = AOFF_LIST_NEXT(x); + AOFF_LIST_PREV(blk) = x; + if (AOFF_LIST_NEXT(x)) + AOFF_LIST_PREV(AOFF_LIST_NEXT(x)) = blk; + AOFF_LIST_NEXT(x) = blk; return; } } @@ -841,7 +831,7 @@ rbt_insert(enum AOFFSortOrder order, AOFF_RBTree_t** root, AOFF_RBTree_t* blk) } if (order == FF_BF) { SET_TREE_NODE(blk); - LIST_NEXT(blk) = NULL; + AOFF_LIST_NEXT(blk) = NULL; } } @@ -867,7 +857,6 @@ 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; @@ -877,7 +866,6 @@ Carrier_t* aoff_lookup_pooled_mbc(Allctr_t* allctr, Uint size) 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, @@ -890,7 +878,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size, #ifdef HARD_DEBUG AOFF_RBTree_t* dbg_blk; #endif - + ASSERT(!cand_blk || cand_size >= size); /* Get first-fit carrier @@ -943,8 +931,11 @@ static void aoff_creating_mbc(Allctr_t *allctr, Carrier_t *carrier) HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0); crr->rbt_node.hdr.bhdr = 0; - if (alc->crr_order == FF_AGEFF || IS_DEBUG) - crr->birth_time = get_birth_time(); + if (alc->crr_order == FF_AGEFF || IS_DEBUG) { + Sint64 bt = get_birth_time(); + crr->rbt_node.u.birth_time = bt; + crr->crr.cpool.pooled.u.birth_time = bt; + } rbt_insert(alc->crr_order, root, &crr->rbt_node); /* aoff_link_free_block will add free block later */ @@ -973,16 +964,16 @@ static void aoff_add_mbc(Allctr_t *allctr, Carrier_t *carrier) AOFF_RBTree_t **root = &alc->mbc_root; ASSERT(!IS_CRR_IN_TREE(crr, *root)); - HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0); + HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0); rbt_insert(alc->crr_order, root, &crr->rbt_node); HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0); } -#ifdef ERTS_SMP void aoff_add_pooled_mbc(Allctr_t *allctr, Carrier_t *crr) { + AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr; AOFF_RBTree_t **root = &allctr->cpool.pooled_tree; ASSERT(allctr == crr->cpool.orig_allctr); @@ -990,11 +981,10 @@ void aoff_add_pooled_mbc(Allctr_t *allctr, Carrier_t *crr) /* Link carrier in address order tree */ - rbt_insert(FF_AOFF, root, &crr->cpool.pooled); + rbt_insert(alc->crr_order, root, &crr->cpool.pooled); HARD_CHECK_TREE(NULL, 0, *root, 0); } -#endif static void aoff_remove_mbc(Allctr_t *allctr, Carrier_t *carrier) { @@ -1017,7 +1007,6 @@ static void aoff_remove_mbc(Allctr_t *allctr, Carrier_t *carrier) HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0); } -#ifdef ERTS_SMP void aoff_remove_pooled_mbc(Allctr_t *allctr, Carrier_t *crr) { ASSERT(allctr == crr->cpool.orig_allctr); @@ -1034,7 +1023,6 @@ void aoff_remove_pooled_mbc(Allctr_t *allctr, Carrier_t *crr) HARD_CHECK_TREE(NULL, 0, allctr->cpool.pooled_tree, 0); } -#endif static UWord aoff_largest_fblk_in_mbc(Allctr_t* allctr, Carrier_t* carrier) @@ -1062,7 +1050,7 @@ static struct { static void ERTS_INLINE atom_init(Eterm *atom, const char *name) { - *atom = am_atom_put(name, strlen(name)); + *atom = am_atom_put(name, sys_strlen(name)); } #define AM_INIT(AM) atom_init(&am.AM, #AM) @@ -1117,7 +1105,7 @@ info_options(Allctr_t *allctr, } if (hpp || szp) { - + if (!atoms_initialized) erts_exit(ERTS_ERROR_EXIT, "%s:%d: Internal error: Atoms not initialized", __FILE__, __LINE__);; @@ -1144,7 +1132,7 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2) switch (op) { case 0x500: return (UWord) ((AOFFAllctr_t *) a1)->blk_order == FF_AOBF; case 0x501: { - AOFF_RBTree_t *node = ((AOFFAllctr_t *) a1)->mbc_root; + AOFF_RBTree_t *node = ((AOFFAllctr_t *) a1)->mbc_root; Uint size = (Uint) a2; node = node ? rbt_search(node, size) : NULL; return (UWord) (node ? RBT_NODE_TO_MBC(node)->root : NULL); @@ -1152,13 +1140,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 0x505: return (UWord) AOFF_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)->blk_order == FF_BF; - case 0x50b: return (UWord) LIST_PREV(a1); + case 0x50b: return (UWord) AOFF_LIST_PREV(a1); default: ASSERT(0); return ~((UWord) 0); } } @@ -1178,7 +1166,7 @@ static int rbt_is_member(AOFF_RBTree_t* root, AOFF_RBTree_t* node) return 0; } node = node->parent; - } + } return 1; } @@ -1291,15 +1279,15 @@ check_tree(Carrier_t* within_crr, enum AOFFSortOrder order, AOFF_RBTree_t* root, } if (order == FF_BF) { AOFF_RBTree_t* y = x; - AOFF_RBTree_t* nxt = LIST_NEXT(y); + AOFF_RBTree_t* nxt = AOFF_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); + ASSERT(AOFF_LIST_PREV(nxt) == y); y = nxt; - nxt = LIST_NEXT(nxt); + nxt = AOFF_LIST_NEXT(nxt); } } @@ -1313,13 +1301,13 @@ check_tree(Carrier_t* within_crr, enum AOFFSortOrder order, AOFF_RBTree_t* root, if (x->left) { ASSERT(x->left->parent == x); ASSERT(cmp_blocks(order, x->left, x) < 0); - ASSERT(x->left->max_sz <= x->max_sz); + ASSERT(x->left->max_sz <= x->max_sz); } if (x->right) { ASSERT(x->right->parent == x); ASSERT(cmp_blocks(order, x->right, x) > 0); - ASSERT(x->right->max_sz <= x->max_sz); + ASSERT(x->right->max_sz <= x->max_sz); } ASSERT(x->max_sz >= AOFF_BLK_SZ(x)); ASSERT(x->max_sz == AOFF_BLK_SZ(x) @@ -1339,7 +1327,7 @@ check_tree(Carrier_t* within_crr, enum AOFFSortOrder order, AOFF_RBTree_t* root, x = x->parent; --depth; } - ASSERT(depth == 0 || (!root && depth==1)); + ASSERT(depth == 0 || (!root && depth==1)); ASSERT(curr_blacks == 0); ASSERT((1 << (max_depth/2)) <= node_cnt); @@ -1385,4 +1373,3 @@ print_tree(AOFF_RBTree_t* root) #endif /* PRINT_TREE */ #endif /* HARD_DEBUG */ - |