diff options
Diffstat (limited to 'erts/emulator/beam/erl_goodfit_alloc.c')
| -rw-r--r-- | erts/emulator/beam/erl_goodfit_alloc.c | 662 |
1 files changed, 662 insertions, 0 deletions
diff --git a/erts/emulator/beam/erl_goodfit_alloc.c b/erts/emulator/beam/erl_goodfit_alloc.c new file mode 100644 index 0000000000..ea2ba4d55c --- /dev/null +++ b/erts/emulator/beam/erl_goodfit_alloc.c @@ -0,0 +1,662 @@ +/* + * %CopyrightBegin% + * + * Copyright Ericsson AB 2003-2009. All Rights Reserved. + * + * The contents of this file are subject to the Erlang Public License, + * Version 1.1, (the "License"); you may not use this file except in + * compliance with the License. You should have received a copy of the + * Erlang Public License along with this software. If not, it can be + * retrieved online at http://www.erlang.org/. + * + * Software distributed under the License is distributed on an "AS IS" + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See + * the License for the specific language governing rights and limitations + * under the License. + * + * %CopyrightEnd% + */ + + +/* + * Description: A "good fit" allocator. Segregated free-lists with a + * maximum search depth are used in order to find a good + * fit fast. Each free-list contains blocks of sizes in a + * specific range. First the free-list + * covering the desired size is searched if it is not empty. + * This search is stopped when the maximum search depth has + * been reached. If no free block was found in the free-list + * covering the desired size, the next non-empty free-list + * covering larger sizes is searched. The maximum search + * depth is by default 3. The insert and delete operations + * are O(1) and the search operation is O(n) where n is the + * maximum search depth, i.e. by default the all operations + * are O(1). + * + * This module is a callback-module for erl_alloc_util.c + * + * Author: Rickard Green + */ + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif +#include "global.h" +#define GET_ERL_GF_ALLOC_IMPL +#include "erl_goodfit_alloc.h" + +#define MIN_MBC_SZ (16*1024) +#define MIN_MBC_FIRST_FREE_SZ (4*1024) + +#define MAX_SUB_MASK_IX \ + ((((Uint)1) << (NO_OF_BKT_IX_BITS - SUB_MASK_IX_SHIFT)) - 1) +#define MAX_SUB_BKT_IX ((((Uint)1) << SUB_MASK_IX_SHIFT) - 1) +#define MAX_BKT_IX (NO_OF_BKTS - 1) + +#define MIN_BLK_SZ UNIT_CEILING(sizeof(GFFreeBlock_t) + sizeof(Uint)) + +#define IX2SBIX(IX) ((IX) & (~(~((Uint)0) << SUB_MASK_IX_SHIFT))) +#define IX2SMIX(IX) ((IX) >> SUB_MASK_IX_SHIFT) +#define MAKE_BKT_IX(SMIX, SBIX) \ + ((((Uint)(SMIX)) << SUB_MASK_IX_SHIFT) | ((Uint)(SBIX))) + +#define SET_BKT_MASK_IX(BM, IX) \ +do { \ + int sub_mask_ix__ = IX2SMIX((IX)); \ + (BM).main |= (((Uint) 1) << sub_mask_ix__); \ + (BM).sub[sub_mask_ix__] |= (((Uint)1) << IX2SBIX((IX))); \ +} while (0) + +#define UNSET_BKT_MASK_IX(BM, IX) \ +do { \ + int sub_mask_ix__ = IX2SMIX((IX)); \ + (BM).sub[sub_mask_ix__] &= ~(((Uint)1) << IX2SBIX((IX))); \ + if (!(BM).sub[sub_mask_ix__]) \ + (BM).main &= ~(((Uint)1) << sub_mask_ix__); \ +} while (0) + +/* Buckets ... */ + +#define BKT_INTRVL_A (1*sizeof(Unit_t)) +#define BKT_INTRVL_B (16*sizeof(Unit_t)) +#define BKT_INTRVL_C (96*sizeof(Unit_t)) + +#define BKT_MIN_SIZE_A MIN_BLK_SZ +#define BKT_MIN_SIZE_B (BKT_MAX_SIZE_A + 1) +#define BKT_MIN_SIZE_C (BKT_MAX_SIZE_B + 1) +#define BKT_MIN_SIZE_D (BKT_MAX_SIZE_C + 1) + +#define BKT_MAX_SIZE_A ((NO_OF_BKTS/4)*BKT_INTRVL_A+BKT_MIN_SIZE_A-1) +#define BKT_MAX_SIZE_B ((NO_OF_BKTS/4)*BKT_INTRVL_B+BKT_MIN_SIZE_B-1) +#define BKT_MAX_SIZE_C ((NO_OF_BKTS/4)*BKT_INTRVL_C+BKT_MIN_SIZE_C-1) + + +#define BKT_MAX_IX_A ((NO_OF_BKTS*1)/4 - 1) +#define BKT_MAX_IX_B ((NO_OF_BKTS*2)/4 - 1) +#define BKT_MAX_IX_C ((NO_OF_BKTS*3)/4 - 1) +#define BKT_MAX_IX_D ((NO_OF_BKTS*4)/4 - 1) + +#define BKT_MIN_IX_A (0) +#define BKT_MIN_IX_B (BKT_MAX_IX_A + 1) +#define BKT_MIN_IX_C (BKT_MAX_IX_B + 1) +#define BKT_MIN_IX_D (BKT_MAX_IX_C + 1) + + +#define BKT_IX_(BAP, SZ) \ + ((SZ) <= BKT_MAX_SIZE_A \ + ? (((SZ) - BKT_MIN_SIZE_A)/BKT_INTRVL_A + BKT_MIN_IX_A) \ + : ((SZ) <= BKT_MAX_SIZE_B \ + ? (((SZ) - BKT_MIN_SIZE_B)/BKT_INTRVL_B + BKT_MIN_IX_B) \ + : ((SZ) <= BKT_MAX_SIZE_C \ + ? (((SZ) - BKT_MIN_SIZE_C)/BKT_INTRVL_C + BKT_MIN_IX_C) \ + : ((SZ) <= (BAP)->bkt_max_size_d \ + ? (((SZ) - BKT_MIN_SIZE_D)/(BAP)->bkt_intrvl_d + BKT_MIN_IX_D)\ + : (NO_OF_BKTS - 1))))) + +#define BKT_MIN_SZ_(BAP, IX) \ + ((IX) <= BKT_MAX_IX_A \ + ? (((IX) - BKT_MIN_IX_A)*BKT_INTRVL_A + BKT_MIN_SIZE_A) \ + : ((IX) <= BKT_MAX_IX_B \ + ? (((IX) - BKT_MIN_IX_B)*BKT_INTRVL_B + BKT_MIN_SIZE_B) \ + : ((IX) <= BKT_MAX_IX_C \ + ? (((IX) - BKT_MIN_IX_C)*BKT_INTRVL_C + BKT_MIN_SIZE_C) \ + : (((IX) - BKT_MIN_IX_D)*(BAP)->bkt_intrvl_d + BKT_MIN_SIZE_D)))) + +#ifdef DEBUG + +static int +BKT_IX(GFAllctr_t *gfallctr, Uint size) +{ + int ix; + ASSERT(size >= MIN_BLK_SZ); + + ix = BKT_IX_(gfallctr, size); + + ASSERT(0 <= ix && ix <= BKT_MAX_IX_D); + + return ix; +} + +static Uint +BKT_MIN_SZ(GFAllctr_t *gfallctr, int ix) +{ + Uint size; + ASSERT(0 <= ix && ix <= BKT_MAX_IX_D); + + size = BKT_MIN_SZ_(gfallctr, ix); + +#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG + ASSERT(ix == BKT_IX(gfallctr, size)); + ASSERT(size == MIN_BLK_SZ || ix - 1 == BKT_IX(gfallctr, size - 1)); +#endif + + return size; +} + +#else + +#define BKT_IX BKT_IX_ +#define BKT_MIN_SZ BKT_MIN_SZ_ + +#endif + + +/* Prototypes of callback functions */ +static Block_t * get_free_block (Allctr_t *, Uint, + Block_t *, Uint); +static void link_free_block (Allctr_t *, Block_t *); +static void unlink_free_block (Allctr_t *, Block_t *); +static void update_last_aux_mbc (Allctr_t *, Carrier_t *); +static Eterm info_options (Allctr_t *, char *, int *, + void *, Uint **, Uint *); +static void init_atoms (void); + +#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG +static void check_block (Allctr_t *, Block_t *, int); +static void check_mbc (Allctr_t *, Carrier_t *); +#endif + +static int atoms_initialized = 0; + +void +erts_gfalc_init(void) +{ + atoms_initialized = 0; +} + + +Allctr_t * +erts_gfalc_start(GFAllctr_t *gfallctr, + GFAllctrInit_t *gfinit, + AllctrInit_t *init) +{ + GFAllctr_t nulled_state = {{0}}; + /* {{0}} is used instead of {0}, in order to avoid (an incorrect) gcc + warning. gcc warns if {0} is used as initializer of a struct when + the first member is a struct (not if, for example, the third member + is a struct). */ + Allctr_t *allctr = (Allctr_t *) gfallctr; + + sys_memcpy((void *) gfallctr, (void *) &nulled_state, sizeof(GFAllctr_t)); + + allctr->mbc_header_size = sizeof(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(GFFreeBlock_t); + + + allctr->vsn_str = ERTS_ALC_GF_ALLOC_VSN_STR; + + /* Callback functions */ + + allctr->get_free_block = get_free_block; + allctr->link_free_block = link_free_block; + allctr->unlink_free_block = unlink_free_block; + allctr->info_options = info_options; + + allctr->get_next_mbc_size = NULL; + allctr->creating_mbc = update_last_aux_mbc; + allctr->destroying_mbc = update_last_aux_mbc; + + allctr->init_atoms = init_atoms; + +#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG + allctr->check_block = check_block; + allctr->check_mbc = check_mbc; +#endif + + allctr->atoms_initialized = 0; + + if (init->sbct > BKT_MIN_SIZE_D-1) + gfallctr->bkt_intrvl_d = + UNIT_CEILING(((3*(init->sbct - BKT_MIN_SIZE_D - 1) + /(NO_OF_BKTS/4 - 1)) + 1) + / 2); + if (gfallctr->bkt_intrvl_d < BKT_INTRVL_C) + gfallctr->bkt_intrvl_d = BKT_INTRVL_C; + gfallctr->bkt_max_size_d = ((NO_OF_BKTS/4)*gfallctr->bkt_intrvl_d + + BKT_MIN_SIZE_D + - 1); + + gfallctr->max_blk_search = (Uint) MAX(1, gfinit->mbsd); + + if (!erts_alcu_start(allctr, init)) + return NULL; + + if (allctr->min_block_size != MIN_BLK_SZ) + return NULL; + + return allctr; +} + +static int +find_bucket(BucketMask_t *bmask, int min_index) +{ + int min, mid, max; + int sub_mask_ix, sub_bkt_ix; + int ix = -1; + +#undef GET_MIN_BIT +#define GET_MIN_BIT(MinBit, BitMask, Min, Max) \ + min = (Min); \ + max = (Max); \ + while(max != min) { \ + mid = ((max - min) >> 1) + min; \ + if((BitMask) \ + & (~(~((Uint) 0) << (mid + 1))) \ + & (~((Uint) 0) << min)) \ + max = mid; \ + else \ + min = mid + 1; \ + } \ + (MinBit) = min + + + ASSERT(bmask->main < (((Uint) 1) << (MAX_SUB_MASK_IX+1))); + + sub_mask_ix = IX2SMIX(min_index); + + if ((bmask->main & (~((Uint) 0) << sub_mask_ix)) == 0) + return -1; + + /* There exists a non empty bucket; find it... */ + + if (bmask->main & (((Uint) 1) << sub_mask_ix)) { + sub_bkt_ix = IX2SBIX(min_index); + if ((bmask->sub[sub_mask_ix] & (~((Uint) 0) << sub_bkt_ix)) == 0) { + sub_mask_ix++; + sub_bkt_ix = 0; + if ((bmask->main & (~((Uint) 0)<< sub_mask_ix)) == 0) + return -1; + } + else + goto find_sub_bkt_ix; + } + else { + sub_mask_ix++; + sub_bkt_ix = 0; + } + + ASSERT(sub_mask_ix <= MAX_SUB_MASK_IX); + /* Has to be a bit > sub_mask_ix */ + ASSERT(bmask->main & (~((Uint) 0) << (sub_mask_ix))); + GET_MIN_BIT(sub_mask_ix, bmask->main, sub_mask_ix, MAX_SUB_MASK_IX); + + find_sub_bkt_ix: + ASSERT(sub_mask_ix <= MAX_SUB_MASK_IX); + ASSERT(sub_bkt_ix <= MAX_SUB_BKT_IX); + + if ((bmask->sub[sub_mask_ix] & (((Uint) 1) << sub_bkt_ix)) == 0) { + ASSERT(sub_mask_ix + 1 <= MAX_SUB_BKT_IX); + /* Has to be a bit > sub_bkt_ix */ + ASSERT(bmask->sub[sub_mask_ix] & (~((Uint) 0) << sub_bkt_ix)); + + GET_MIN_BIT(sub_bkt_ix, + bmask->sub[sub_mask_ix], + sub_bkt_ix+1, + MAX_SUB_BKT_IX); + + ASSERT(sub_bkt_ix <= MAX_SUB_BKT_IX); + } + + ix = MAKE_BKT_IX(sub_mask_ix, sub_bkt_ix); + + ASSERT(0 <= ix && ix < NO_OF_BKTS); + + return ix; + +#undef GET_MIN_BIT + +} + +static Block_t * +search_bucket(Allctr_t *allctr, int ix, Uint size) +{ + int i; + Uint min_sz; + Uint blk_sz; + Uint cand_sz = 0; + Uint max_blk_search; + GFFreeBlock_t *blk; + GFFreeBlock_t *cand = NULL; + int blk_on_lambc; + int cand_on_lambc = 0; + GFAllctr_t *gfallctr = (GFAllctr_t *) allctr; + + ASSERT(0 <= ix && ix <= NO_OF_BKTS - 1); + + if (!gfallctr->buckets[ix]) + return NULL; + + min_sz = BKT_MIN_SZ(gfallctr, ix); + if (min_sz < size) + min_sz = size; + + max_blk_search = gfallctr->max_blk_search; + for (blk = gfallctr->buckets[ix], i = 0; + blk && i < max_blk_search; + blk = blk->next, i++) { + + blk_sz = BLK_SZ(blk); + blk_on_lambc = (((char *) blk) < gfallctr->last_aux_mbc_end + && gfallctr->last_aux_mbc_start <= ((char *) blk)); + + if (blk_sz == min_sz && !blk_on_lambc) + return (Block_t *) blk; + + if (blk_sz >= min_sz + && (!cand + || (!blk_on_lambc && (cand_on_lambc || blk_sz < cand_sz)) + || (blk_on_lambc && cand_on_lambc && blk_sz < cand_sz))) { + cand_sz = blk_sz; + cand = blk; + cand_on_lambc = blk_on_lambc; + } + + } + return (Block_t *) cand; +} + +static Block_t * +get_free_block(Allctr_t *allctr, Uint size, + Block_t *cand_blk, Uint cand_size) +{ + GFAllctr_t *gfallctr = (GFAllctr_t *) allctr; + int unsafe_bi, min_bi; + Block_t *blk; + + ASSERT(!cand_blk || cand_size >= size); + + unsafe_bi = BKT_IX(gfallctr, size); + + min_bi = find_bucket(&gfallctr->bucket_mask, unsafe_bi); + if (min_bi < 0) + return NULL; + + if (min_bi == unsafe_bi) { + blk = search_bucket(allctr, min_bi, size); + if (blk) { + if (cand_blk && cand_size <= BLK_SZ(blk)) + return NULL; /* cand_blk was better */ + unlink_free_block(allctr, blk); + return blk; + } + if (min_bi < NO_OF_BKTS - 1) { + min_bi = find_bucket(&gfallctr->bucket_mask, min_bi + 1); + if (min_bi < 0) + return NULL; + } + else + return NULL; + } + else { + ASSERT(min_bi > unsafe_bi); + } + + /* We are guaranteed to find a block that fits in this bucket */ + blk = search_bucket(allctr, min_bi, size); + ASSERT(blk); + if (cand_blk && cand_size <= BLK_SZ(blk)) + return NULL; /* cand_blk was better */ + unlink_free_block(allctr, blk); + return blk; +} + + + +static void +link_free_block(Allctr_t *allctr, Block_t *block) +{ + GFAllctr_t *gfallctr = (GFAllctr_t *) allctr; + GFFreeBlock_t *blk = (GFFreeBlock_t *) block; + Uint sz = BLK_SZ(blk); + int i = BKT_IX(gfallctr, sz); + + ASSERT(sz >= MIN_BLK_SZ); + + SET_BKT_MASK_IX(gfallctr->bucket_mask, i); + + blk->prev = NULL; + blk->next = gfallctr->buckets[i]; + if (blk->next) { + ASSERT(!blk->next->prev); + blk->next->prev = blk; + } + gfallctr->buckets[i] = blk; +} + +static void +unlink_free_block(Allctr_t *allctr, Block_t *block) +{ + GFAllctr_t *gfallctr = (GFAllctr_t *) allctr; + GFFreeBlock_t *blk = (GFFreeBlock_t *) block; + Uint sz = BLK_SZ(blk); + int i = BKT_IX(gfallctr, sz); + + if (!blk->prev) { + ASSERT(gfallctr->buckets[i] == blk); + gfallctr->buckets[i] = blk->next; + } + else + blk->prev->next = blk->next; + if (blk->next) + blk->next->prev = blk->prev; + + if (!gfallctr->buckets[i]) + UNSET_BKT_MASK_IX(gfallctr->bucket_mask, i); +} + +static void +update_last_aux_mbc(Allctr_t *allctr, Carrier_t *mbc) +{ + GFAllctr_t *gfallctr = (GFAllctr_t *) allctr; + + if (gfallctr->last_aux_mbc_start != (char *) allctr->mbc_list.last) { + + if (allctr->mbc_list.last + && allctr->main_carrier != allctr->mbc_list.last) { + gfallctr->last_aux_mbc_start = (char *) allctr->mbc_list.last; + gfallctr->last_aux_mbc_end = (((char *) allctr->mbc_list.last) + + CARRIER_SZ(allctr->mbc_list.last)); + } + else { + gfallctr->last_aux_mbc_start = NULL; + gfallctr->last_aux_mbc_end = NULL; + } + + } +} + +static struct { + Eterm mbsd; + Eterm as; + Eterm gf; +#ifdef DEBUG + Eterm end_of_atoms; +#endif +} am; + +static void ERTS_INLINE atom_init(Eterm *atom, char *name) +{ + *atom = am_atom_put(name, strlen(name)); +} +#define AM_INIT(AM) atom_init(&am.AM, #AM) + +static void +init_atoms(void) +{ +#ifdef DEBUG + Eterm *atom; +#endif + + if (atoms_initialized) + return; + +#ifdef DEBUG + for (atom = (Eterm *) &am; atom <= &am.end_of_atoms; atom++) { + *atom = THE_NON_VALUE; + } +#endif + + AM_INIT(mbsd); + AM_INIT(as); + AM_INIT(gf); + +#ifdef DEBUG + for (atom = (Eterm *) &am; atom < &am.end_of_atoms; atom++) { + ASSERT(*atom != THE_NON_VALUE); + } +#endif + + atoms_initialized = 1; +} + +#define bld_uint erts_bld_uint +#define bld_cons erts_bld_cons +#define bld_tuple erts_bld_tuple + +static ERTS_INLINE void +add_2tup(Uint **hpp, Uint *szp, Eterm *lp, Eterm el1, Eterm el2) +{ + *lp = bld_cons(hpp, szp, bld_tuple(hpp, szp, 2, el1, el2), *lp); +} + +static Eterm +info_options(Allctr_t *allctr, + char *prefix, + int *print_to_p, + void *print_to_arg, + Uint **hpp, + Uint *szp) +{ + GFAllctr_t *gfallctr = (GFAllctr_t *) allctr; + Eterm res = THE_NON_VALUE; + + if (print_to_p) { + erts_print(*print_to_p, + print_to_arg, + "%smbsd: %lu\n" + "%sas: gf\n", + prefix, gfallctr->max_blk_search, + prefix); + } + + if (hpp || szp) { + + if (!atoms_initialized) + erl_exit(1, "%s:%d: Internal error: Atoms not initialized", + __FILE__, __LINE__);; + + res = NIL; + add_2tup(hpp, szp, &res, am.as, am.gf); + add_2tup(hpp, szp, &res, + am.mbsd, + bld_uint(hpp, szp, gfallctr->max_blk_search)); + } + + return res; +} + +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ + * NOTE: erts_gfalc_test() is only supposed to be used for testing. * + * * + * Keep alloc_SUITE_data/allocator_test.h updated if changes are made * + * to erts_gfalc_test() * +\* */ + +unsigned long +erts_gfalc_test(unsigned long op, unsigned long a1, unsigned long a2) +{ + switch (op) { + case 0x100: return (unsigned long) BKT_IX((GFAllctr_t *) a1, (Uint) a2); + case 0x101: return (unsigned long) BKT_MIN_SZ((GFAllctr_t *) a1, (int) a2); + case 0x102: return (unsigned long) NO_OF_BKTS; + case 0x103: return (unsigned long) + find_bucket(&((GFAllctr_t *) a1)->bucket_mask, (int) a2); + default: ASSERT(0); return ~((unsigned long) 0); + } +} + +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ + * Debug functions * +\* */ + +#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG +void +check_block(Allctr_t *allctr, Block_t * blk, int free_block) +{ + GFAllctr_t *gfallctr = (GFAllctr_t *) allctr; + int i; + int bi; + int found; + GFFreeBlock_t *fblk; + + if(free_block) { + Uint blk_sz = BLK_SZ(blk); + bi = BKT_IX(gfallctr, blk_sz); + + ASSERT(gfallctr->bucket_mask.main & (((Uint) 1) << IX2SMIX(bi))); + ASSERT(gfallctr->bucket_mask.sub[IX2SMIX(bi)] + & (((Uint) 1) << IX2SBIX(bi))); + + found = 0; + for (fblk = gfallctr->buckets[bi]; fblk; fblk = fblk->next) + if (blk == (Block_t *) fblk) + found++; + ASSERT(found == 1); + } + else + bi = -1; + + found = 0; + for (i = 0; i < NO_OF_BKTS; i++) { + if (i == bi) + continue; /* Already checked */ + for (fblk = gfallctr->buckets[i]; fblk; fblk = fblk->next) + if (blk == (Block_t *) fblk) + found++; + } + + ASSERT(found == 0); + +} + +void +check_mbc(Allctr_t *allctr, Carrier_t *mbc) +{ + GFAllctr_t *gfallctr = (GFAllctr_t *) allctr; + int bi; + + for(bi = 0; bi < NO_OF_BKTS; bi++) { + if ((gfallctr->bucket_mask.main & (((Uint) 1) << IX2SMIX(bi))) + && (gfallctr->bucket_mask.sub[IX2SMIX(bi)] + & (((Uint) 1) << IX2SBIX(bi)))) { + ASSERT(gfallctr->buckets[bi] != NULL); + } + else { + ASSERT(gfallctr->buckets[bi] == NULL); + } + } +} + +#endif |