[Tarantool-patches] [PATCH v4] small: changed small allocator pool management

[mechanik20051988 <mechanik20051988@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, &quota, 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