[Tarantool-patches] [PATCH v4] small: changed small allocator pool management
mechanik20051988
mechanik20051988 at tarantool.org
Fri Dec 25 14:45:20 MSK 2020
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 <string.h>
#include <stdio.h>
-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 <assert.h>
#include <math.h>
+#include <stddef.h>
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
More information about the Tarantool-patches
mailing list