From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp54.i.mail.ru (smtp54.i.mail.ru [217.69.128.34]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id C59EF4765E3 for ; Fri, 25 Dec 2020 14:45:26 +0300 (MSK) From: mechanik20051988 Date: Fri, 25 Dec 2020 14:45:20 +0300 Message-Id: <20201225114520.18796-2-mechanik20051988@tarantool.org> In-Reply-To: <20201225114520.18796-1-mechanik20051988@tarantool.org> References: <20201225114520.18796-1-mechanik20051988@tarantool.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH v4] small: changed small allocator pool management List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: v.shpilevoy@tarantool.org Cc: tarantool-patches@dev.tarantool.org Branch: https://github.com/tarantool/small/tree/mechanik20051988/gh-5216-fix-strange-allocator-behavior Cnanges in v4: Add actual_alloc_factor parameter to small_class_create In previous version allocator created new pool if necessary and inserted it in the pools tree. Now we allocate pools on the stage of allocator creation according alloc_factor. We use small_alloc class for this purpose also we use it to find necessary pool when we alloc memory. This is faster then previous allocator behavior and also fixes #5216. Closes #5216 --- perf/small_alloc_perf.c | 11 +- small/small.c | 219 ++++++++++------------------------------ small/small.h | 56 ++++------ small/small_class.c | 5 +- small/small_class.h | 3 +- test/small_alloc.c | 3 +- test/small_class.c | 9 +- 7 files changed, 94 insertions(+), 212 deletions(-) diff --git a/perf/small_alloc_perf.c b/perf/small_alloc_perf.c index b980e38..210bcc9 100644 --- a/perf/small_alloc_perf.c +++ b/perf/small_alloc_perf.c @@ -209,8 +209,10 @@ small_alloc_basic(unsigned int slab_size) slab_arena_create(&arena, "a, 0, slab_size, MAP_PRIVATE); slab_cache_create(&cache, &arena); for (unsigned int i = 0; i < SZR(slab_alloc_factor); i++) { + float actual_alloc_factor; small_alloc_create(&alloc, &cache, - OBJSIZE_MIN, slab_alloc_factor[i]); + OBJSIZE_MIN, slab_alloc_factor[i], + &actual_alloc_factor); int size_min = OBJSIZE_MIN; int size_max = (int)alloc.objsize_max - 1; fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm1) == 0); @@ -248,8 +250,10 @@ small_alloc_basic(unsigned int slab_size) print_json_test_header("exponent"); } for (unsigned int i = 0; i < SZR(slab_alloc_factor); i++) { + float actual_alloc_factor; small_alloc_create(&alloc, &cache, - OBJSIZE_MIN, slab_alloc_factor[i]); + OBJSIZE_MIN, slab_alloc_factor[i], + &actual_alloc_factor); int size_min = OBJSIZE_MIN; int size_max = (int)alloc.objsize_max - 1; fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm1) == 0); @@ -295,8 +299,9 @@ small_alloc_large() print_json_test_header("large"); } for (unsigned int i = 0; i < SZR(slab_alloc_factor); i++) { + float actual_alloc_factor; small_alloc_create(&alloc, &cache, OBJSIZE_MIN, - slab_alloc_factor[i]); + slab_alloc_factor[i], &actual_alloc_factor); fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm1) == 0); small_alloc_test(large_size_min, large_size_max, 200, 1, 25); fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm2) == 0); diff --git a/small/small.c b/small/small.c index 48085fb..e2798fb 100644 --- a/small/small.c +++ b/small/small.c @@ -33,122 +33,59 @@ #include #include -enum { - /** Step size for stepped pools, in bytes */ - STEP_SIZE = 8, - /** - * LB stands for logarithm with binary base, this constant - * is used for bit shifts, when we need to divide by - * STEP_SIZE. - */ - STEP_SIZE_LB = 3, -}; - -rb_proto(, factor_tree_, factor_tree_t, struct factor_pool) - -/** Used for search in the tree. */ -static inline int -factor_pool_cmp(const struct factor_pool *a, const struct factor_pool *b) +static inline struct factor_pool * +factor_pool_search(struct small_alloc *alloc, size_t size) { - return a->pool.objsize > b->pool.objsize ? 1 : - a->pool.objsize < b->pool.objsize ? -1 : 0; + if (size > alloc->objsize_max) + return NULL; + unsigned cls = small_class_calc_offset_by_size(&alloc->small_class, size); + struct factor_pool *pool = &alloc->factor_pool_cache[cls]; + return pool; } -rb_gen(, factor_tree_, factor_tree_t, struct factor_pool, node, - factor_pool_cmp) - -static inline struct factor_pool * -factor_pool_create(struct small_alloc *alloc, - struct factor_pool *upper_bound, - size_t size) +static inline void +factor_pool_create(struct small_alloc *alloc) { - assert(size > alloc->step_pool_objsize_max); - assert(size <= alloc->objsize_max); - - if (alloc->factor_pool_next == NULL) { - /** - * Too many factored pools already, fall back - * to an imperfect one. - */ - return upper_bound; + size_t objsize = 0; + for (alloc->factor_pool_cache_size = 0; + objsize < alloc->objsize_max && alloc->factor_pool_cache_size < FACTOR_POOL_MAX; + alloc->factor_pool_cache_size++) { + size_t prevsize = objsize; + objsize = small_class_calc_size_by_offset(&alloc->small_class, + alloc->factor_pool_cache_size); + if (objsize > alloc->objsize_max) + objsize = alloc->objsize_max; + struct factor_pool *pool = + &alloc->factor_pool_cache[alloc->factor_pool_cache_size]; + mempool_create(&pool->pool, alloc->cache, objsize); + pool->objsize_min = prevsize + 1; } - size_t objsize = alloc->step_pool_objsize_max; - size_t prevsize; - do { - prevsize = objsize; - /* - * Align objsize after each multiplication to - * ensure that the distance between objsizes of - * factored pools is a multiple of STEP_SIZE. - */ - objsize = small_align(objsize * alloc->factor, - sizeof(intptr_t)); - assert(objsize > alloc->step_pool_objsize_max); - } while (objsize < size); - if (objsize > alloc->objsize_max) - objsize = alloc->objsize_max; - struct factor_pool *pool = alloc->factor_pool_next; - alloc->factor_pool_next = pool->next; - mempool_create(&pool->pool, alloc->cache, objsize); - pool->objsize_min = prevsize + 1; - factor_tree_insert(&alloc->factor_pools, pool); - return pool; + alloc->objsize_max = objsize; } /** Initialize the small allocator. */ void small_alloc_create(struct small_alloc *alloc, struct slab_cache *cache, - uint32_t objsize_min, float alloc_factor) + uint32_t objsize_min, float alloc_factor, + float *actual_alloc_factor) { alloc->cache = cache; /* Align sizes. */ - objsize_min = small_align(objsize_min, STEP_SIZE); - alloc->step_pool0_step_count = (objsize_min - 1) >> STEP_SIZE_LB; + objsize_min = small_align(objsize_min, sizeof(intptr_t)); /* Make sure at least 4 largest objects can fit in a slab. */ alloc->objsize_max = mempool_objsize_max(slab_order_size(cache, cache->order_max)); - if (!(alloc->objsize_max > objsize_min + STEP_POOL_MAX * STEP_SIZE)) { - fprintf(stderr, "Can't create small alloc, small " - "object min size should not be greather than %u\n", - alloc->objsize_max - (STEP_POOL_MAX + 1) * STEP_SIZE); - abort(); - } + assert(alloc_factor > 1. && alloc_factor <= 2.); - struct mempool *step_pool; - for (step_pool = alloc->step_pools; - step_pool < alloc->step_pools + STEP_POOL_MAX; - step_pool++) { - mempool_create(step_pool, alloc->cache, objsize_min); - objsize_min += STEP_SIZE; - } - alloc->step_pool_objsize_max = (step_pool - 1)->objsize; - if (alloc_factor > 2.0) - alloc_factor = 2.0; + alloc->factor = alloc_factor; /* - * Correct the user-supplied alloc_factor to ensure that - * it actually produces growing object sizes. + * Second parameter (uintptr_t) - granularity, + * determines alignment. */ - if (alloc->step_pool_objsize_max * alloc_factor < - alloc->step_pool_objsize_max + STEP_SIZE) { - - alloc_factor = - (alloc->step_pool_objsize_max + STEP_SIZE + 0.5)/ - alloc->step_pool_objsize_max; - } - alloc->factor = alloc_factor; - - /* Initialize the factored pool cache. */ - struct factor_pool *factor_pool = alloc->factor_pool_cache; - do { - factor_pool->next = factor_pool + 1; - factor_pool++; - } while (factor_pool != - alloc->factor_pool_cache + FACTOR_POOL_MAX - 1); - factor_pool->next = NULL; - alloc->factor_pool_next = alloc->factor_pool_cache; - factor_tree_new(&alloc->factor_pools); - (void) factor_pool_create(alloc, NULL, alloc->objsize_max); + small_class_create(&alloc->small_class, sizeof(intptr_t), + alloc->factor, objsize_min, actual_alloc_factor); + factor_pool_create(alloc); lifo_init(&alloc->delayed); lifo_init(&alloc->delayed_large); @@ -225,72 +162,27 @@ smalloc(struct small_alloc *alloc, size_t size) { small_collect_garbage(alloc); - struct mempool *pool; - int idx = (size - 1) >> STEP_SIZE_LB; - idx = (idx > (int) alloc->step_pool0_step_count) ? idx - alloc->step_pool0_step_count : 0; - if (idx < STEP_POOL_MAX) { - /* Allocate in a stepped pool. */ - pool = &alloc->step_pools[idx]; - assert(size <= pool->objsize && - (size + STEP_SIZE > pool->objsize || idx == 0)); - } else { - struct factor_pool pattern; - pattern.pool.objsize = size; - struct factor_pool *upper_bound = - factor_tree_nsearch(&alloc->factor_pools, &pattern); - if (upper_bound == NULL) { - /* Object is too large, fallback to slab_cache */ - struct slab *slab = slab_get_large(alloc->cache, size); - if (slab == NULL) - return NULL; - return slab_data(slab); - } - - if (size < upper_bound->objsize_min) - upper_bound = factor_pool_create(alloc, upper_bound, - size); - pool = &upper_bound->pool; + struct factor_pool *upper_bound = factor_pool_search(alloc, size); + if (upper_bound == NULL) { + /* Object is too large, fallback to slab_cache */ + struct slab *slab = slab_get_large(alloc->cache, size); + if (slab == NULL) + return NULL; + return slab_data(slab); } + struct mempool *pool = &upper_bound->pool; assert(size <= pool->objsize); return mempool_alloc(pool); } -static void -small_recycle_pool(struct small_alloc *alloc, struct mempool *pool) -{ - if (mempool_used(pool) == 0 && - pool->objsize > alloc->step_pool_objsize_max && - alloc->factor_pool_next == NULL) { - struct factor_pool *factor_pool = (struct factor_pool *) - ((char *) pool - (intptr_t) - &((struct factor_pool *) NULL)->pool); - factor_tree_remove(&alloc->factor_pools, factor_pool); - mempool_destroy(pool); - alloc->factor_pool_next = factor_pool; - } -} - static inline struct mempool * mempool_find(struct small_alloc *alloc, size_t size) { - struct mempool *pool; - int idx = (size - 1) >> STEP_SIZE_LB; - idx = (idx > (int) alloc->step_pool0_step_count) ? idx - alloc->step_pool0_step_count : 0; - if (idx < STEP_POOL_MAX) { - /* Allocated in a stepped pool. */ - pool = &alloc->step_pools[idx]; - assert((size + STEP_SIZE > pool->objsize) || (idx == 0)); - } else { - /* Allocated in a factor pool. */ - struct factor_pool pattern; - pattern.pool.objsize = size; - struct factor_pool *upper_bound = - factor_tree_nsearch(&alloc->factor_pools, &pattern); - if (upper_bound == NULL) - return NULL; /* Allocated by slab_cache. */ - assert(size >= upper_bound->objsize_min); - pool = &upper_bound->pool; - } + struct factor_pool *upper_bound = factor_pool_search(alloc, size); + if (upper_bound == NULL) + return NULL; /* Allocated by slab_cache. */ + assert(size >= upper_bound->objsize_min); + struct mempool *pool = &upper_bound->pool; assert(size <= pool->objsize); return pool; } @@ -319,8 +211,6 @@ smfree(struct small_alloc *alloc, void *ptr, size_t size) /* Regular allocation in mempools */ mempool_free(pool, ptr); - if (mempool_used(pool) == 0) - small_recycle_pool(alloc, pool); } /** @@ -351,8 +241,7 @@ smfree_delayed(struct small_alloc *alloc, void *ptr, size_t size) struct mempool_iterator { struct small_alloc *alloc; - struct mempool *step_pool; - struct factor_tree_iterator factor_iterator; + uint32_t factor_iterator; }; void @@ -360,19 +249,19 @@ mempool_iterator_create(struct mempool_iterator *it, struct small_alloc *alloc) { it->alloc = alloc; - it->step_pool = alloc->step_pools; - factor_tree_ifirst(&alloc->factor_pools, &it->factor_iterator); + it->factor_iterator = 0; } struct mempool * mempool_iterator_next(struct mempool_iterator *it) { - if (it->step_pool < it->alloc->step_pools + STEP_POOL_MAX) - return it->step_pool++; - struct factor_pool *factor_pool = factor_tree_inext(&it->factor_iterator); - if (factor_pool) { + struct factor_pool *factor_pool = NULL; + if (it->factor_iterator < it->alloc->factor_pool_cache_size) + factor_pool = + &it->alloc->factor_pool_cache[(it->factor_iterator)++]; + if (factor_pool) return &(factor_pool->pool); - } + return NULL; } diff --git a/small/small.h b/small/small.h index 376c600..3a44b6c 100644 --- a/small/small.h +++ b/small/small.h @@ -34,6 +34,7 @@ #include "mempool.h" #include "slab_arena.h" #include "lifo.h" +#include "small_class.h" #if defined(__cplusplus) extern "C" { @@ -86,10 +87,8 @@ extern "C" { /** Basic constants of small object allocator. */ enum { - /** How many stepped pools there is. */ - STEP_POOL_MAX = 32, /** How many factored pools there can be. */ - FACTOR_POOL_MAX = 256, + FACTOR_POOL_MAX = 1024, }; enum small_opt { @@ -107,8 +106,6 @@ enum small_opt { */ struct factor_pool { - /** rb_tree entry */ - rb_node(struct factor_pool) node; /** the pool itself. */ struct mempool pool; /** @@ -117,12 +114,8 @@ struct factor_pool * pool. */ size_t objsize_min; - /** next free factor pool in the cache. */ - struct factor_pool *next; }; -typedef rb_tree(struct factor_pool) factor_tree_t; - /** * Free mode */ @@ -138,26 +131,10 @@ enum small_free_mode { /** A slab allocator for a wide range of object sizes. */ struct small_alloc { struct slab_cache *cache; - uint32_t step_pool_objsize_max; - /** - * All slabs in all pools must be of the same order, - * otherwise small_free() has no way to derive from - * pointer its slab and then the pool. - */ - /** - * An array of "stepped" pools, pool->objsize of adjacent - * pools differ by a fixed size (step). - */ - struct mempool step_pools[STEP_POOL_MAX]; /** A cache for nodes in the factor_pools tree. */ struct factor_pool factor_pool_cache[FACTOR_POOL_MAX]; - /** First free element in factor_pool_cache. */ - struct factor_pool *factor_pool_next; - /** - * A red-black tree with "factored" pools, i.e. - * each pool differs from its neighbor by a factor. - */ - factor_tree_t factor_pools; + /* factor_pool_cache array real size */ + uint32_t factor_pool_cache_size; /** * List of mempool which objects to be freed if delayed free mode. */ @@ -171,22 +148,29 @@ struct small_alloc { * Is provided during initialization. */ float factor; + /** Small class for this allocator */ + struct small_class small_class; uint32_t objsize_max; /** * Free mode. */ enum small_free_mode free_mode; - /** - * Object size of step pool 0 divided by STEP_SIZE, to - * quickly find the right stepped pool given object size. - */ - uint32_t step_pool0_step_count; }; -/** Initialize a small memory allocator. */ +/** + * Initialize a small memory allocator. + * @param alloc - instance to create. + * @param cache - pointer to used slab cache. + * @param objsize_min - minimal object size. + * @param alloc_factor - desired factor of growth object size. + * Must be in (1, 2] range. + * @param actual_alloc_factor real allocation factor calculated the basis of + * desired alloc_factor + */ void small_alloc_create(struct small_alloc *alloc, struct slab_cache *cache, - uint32_t objsize_min, float alloc_factor); + uint32_t objsize_min, float alloc_factor, + float *actual_alloc_factor); /** * Enter or leave delayed mode - in delayed mode smfree_delayed() @@ -213,10 +197,6 @@ smalloc(struct small_alloc *alloc, size_t size); * * This boils down to finding the object's mempool and delegating * to mempool_free(). - * - * If the pool becomes completely empty, and it's a factored pool, - * and the factored pool's cache is empty, put back the empty - * factored pool into the factored pool cache. */ void smfree(struct small_alloc *alloc, void *ptr, size_t size); diff --git a/small/small_class.c b/small/small_class.c index 99915a8..07df5d2 100644 --- a/small/small_class.c +++ b/small/small_class.c @@ -32,16 +32,18 @@ #include "small_class.h" #include #include +#include void small_class_create(struct small_class *sc, unsigned granularity, - float desired_factor, unsigned min_alloc) + float desired_factor, unsigned min_alloc, float *actual_factor) { assert(granularity > 0); /* size cannot be multiple of zero. */ assert((granularity & (granularity - 1)) == 0); /* must power of 2. */ assert(desired_factor > 1.f); assert(desired_factor <= 2.f); assert(min_alloc > 0); /* Cannot allocate zero. */ + assert(actual_factor != NULL); sc->granularity = granularity; sc->ignore_bits_count = __builtin_ctz(granularity); @@ -53,4 +55,5 @@ small_class_create(struct small_class *sc, unsigned granularity, sc->size_shift_plus_1 = sc->size_shift + 1; sc->actual_factor = powf(2, 1.f / powf(2, sc->effective_bits)); + *actual_factor = sc->actual_factor; } diff --git a/small/small_class.h b/small/small_class.h index e6b0a7c..b787aa6 100644 --- a/small/small_class.h +++ b/small/small_class.h @@ -138,10 +138,11 @@ struct small_class { * Must be in (1, 2] range. Actual factor can be different. * @param min_alloc - the lowest class size, must be greater than zero. * The good choice is the same value as granularity. + * @param actual_factor calculated on the basis of desired factor */ void small_class_create(struct small_class *sc, unsigned granularity, - float desired_factor, unsigned min_alloc); + float desired_factor, unsigned min_alloc, float *actual_factor); /** * Find position of the most significant bit in a value. diff --git a/test/small_alloc.c b/test/small_alloc.c index 421442a..65f081b 100644 --- a/test/small_alloc.c +++ b/test/small_alloc.c @@ -78,7 +78,8 @@ static void small_alloc_test(int size_min, int size_max, int objects_max, int oscillation_max, int iterations_max) { - small_alloc_create(&alloc, &cache, OBJSIZE_MIN, 1.3); + float actual_alloc_factor; + small_alloc_create(&alloc, &cache, OBJSIZE_MIN, 1.3, &actual_alloc_factor); for (int i = 0; i < iterations_max; i++) { small_alloc_setopt(&alloc, SMALL_DELAYED_FREE_MODE, i % 5 == 0); diff --git a/test/small_class.c b/test/small_class.c index 48cdac9..cfb9b47 100644 --- a/test/small_class.c +++ b/test/small_class.c @@ -43,7 +43,8 @@ test_class(void) plan(0); struct small_class sc; - small_class_create(&sc, 2, 1.2, 12); + float actual_factor; + small_class_create(&sc, 2, 1.2, 12, &actual_factor); unsigned class = small_class_calc_offset_by_size(&sc, 0); unsigned class_size = small_class_calc_size_by_offset(&sc, class); @@ -106,7 +107,8 @@ check_expectation() } struct small_class sc; - small_class_create(&sc, granularity, factor, min_alloc); + float actual_factor; + small_class_create(&sc, granularity, factor, min_alloc, &actual_factor); fail_unless(sc.effective_size == eff_size); for (unsigned s = 0; s <= test_sizes; s++) { @@ -135,7 +137,8 @@ check_factor() for (unsigned granularity = 1; granularity <= 4; granularity *= 4) { for(float factor = 1.01; factor < 1.995; factor += 0.01) { struct small_class sc; - small_class_create(&sc, granularity, factor, granularity); + float actual_factor; + small_class_create(&sc, granularity, factor, granularity, &actual_factor); float k = powf(factor, 0.5f); fail_unless(sc.actual_factor >= factor / k && sc.actual_factor <= factor * k); -- 2.20.1