* [Tarantool-patches] [PATCH] memtx: change small allocator behavior
2020-12-23 13:14 [Tarantool-patches] [PATCH v2 0/3] change small allocator behavior mechanik20051988
@ 2020-12-23 13:14 ` mechanik20051988
2020-12-24 15:13 ` Vladislav Shpilevoy
2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation mechanik20051988
` (2 subsequent siblings)
3 siblings, 1 reply; 14+ messages in thread
From: mechanik20051988 @ 2020-12-23 13:14 UTC (permalink / raw)
To: v.shpilevoy; +Cc: mechanik20051988, tarantool-patches
From: mechanik20051988 <mechanik20.05.1988@gmail.com>
Branch: https://github.com/tarantool/tarantool/tree/mechanik20051988/gh-5216-fix-strange-allocator-behavior
Pull request: https://github.com/tarantool/tarantool/pull/5503
Thank you for the previous review. Here some answers on you questions.
1. I add subsystem name prefix for the commit title
2. As you can see at this moment, small_alloc_create already
has restrictions on alloc_factor (see small.c in master branch)
They change it silently.
if (alloc_factor > 2.0)
alloc_factor = 2.0;
/*
* Correct the user-supplied alloc_factor to ensure that
* it actually produces growing object sizes.
*/
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;
}
I only moved them in memtx_engine.c with an explicit message.
3. Fix whitespaces
4. I took an example from issue to show that everything works now.
5. Fixed.
Previously, in small allocator, memory pools
were allocated at the request, which in the case
of a small slab_alloc_factor led to use
pools with incorrect sizes. This patch changed
small allocator behavior, now we allocate pools
on the stage of allocator creation. Also we use
special function to find appropriate pool, which
is faster, then previous version with rbtree.
This change fixes #5216.
Also moved a check, that the slab_alloc_factor is in
the range (1.0, 2.0] from small allocator to memtx_engine.
If factor is not in range change it to 1.0001 or 2.0 respectively
Closes #5216
---
src/box/memtx_engine.c | 8 +++
src/lib/small | 2 +-
test/engine/engine.cfg | 3 ++
test/engine/small_alloc_factor.lua | 11 ++++
test/engine/small_alloc_factor.result | 70 +++++++++++++++++++++++++
test/engine/small_alloc_factor.test.lua | 20 +++++++
6 files changed, 113 insertions(+), 1 deletion(-)
create mode 100644 test/engine/small_alloc_factor.lua
create mode 100644 test/engine/small_alloc_factor.result
create mode 100644 test/engine/small_alloc_factor.test.lua
diff --git a/src/box/memtx_engine.c b/src/box/memtx_engine.c
index 4f1fe3a3f..3ab292f2e 100644
--- a/src/box/memtx_engine.c
+++ b/src/box/memtx_engine.c
@@ -1116,6 +1116,14 @@ memtx_engine_new(const char *snap_dirname, bool force_recovery,
if (objsize_min < OBJSIZE_MIN)
objsize_min = OBJSIZE_MIN;
+ if (alloc_factor > 2) {
+ say_error("Alloc factor must be less than or equal to 2.0. It will be reduced to 2.0");
+ alloc_factor = 2.0;
+ } else if (alloc_factor <= 1.0) {
+ say_error("Alloc factor must be greater than then 1.0. It will be increased to 1.001");
+ alloc_factor = 1.001;
+ }
+
/* Initialize tuple allocator. */
quota_init(&memtx->quota, tuple_arena_max_size);
tuple_arena_create(&memtx->arena, &memtx->quota, tuple_arena_max_size,
diff --git a/src/lib/small b/src/lib/small
index fcac155db..2053b49df 160000
--- a/src/lib/small
+++ b/src/lib/small
@@ -1 +1 @@
-Subproject commit fcac155dba18e97b10bc668d1a2fae01184adc13
+Subproject commit 2053b49dff3cb419245d243e96dbe981625be6d2
diff --git a/test/engine/engine.cfg b/test/engine/engine.cfg
index f017a03ec..4a6a8bbbf 100644
--- a/test/engine/engine.cfg
+++ b/test/engine/engine.cfg
@@ -8,6 +8,9 @@
},
"gh-4973-concurrent-alter-fails.test.lua": {
"memtx": {"engine": "memtx"}
+ },
+ "small_alloc_factor.test.lua" : {
+ "memtx": {"engine": "memtx"}
}
}
diff --git a/test/engine/small_alloc_factor.lua b/test/engine/small_alloc_factor.lua
new file mode 100644
index 000000000..a303a95d4
--- /dev/null
+++ b/test/engine/small_alloc_factor.lua
@@ -0,0 +1,11 @@
+#!/usr/bin/env tarantool
+
+require('console').listen(os.getenv('ADMIN'))
+
+box.cfg({
+ wal_mode = 'none',
+ memtx_memory = 2*1024*1024*1024,
+ listen = os.getenv("LISTEN"),
+ memtx_min_tuple_size=32,
+ slab_alloc_factor=1.03
+})
diff --git a/test/engine/small_alloc_factor.result b/test/engine/small_alloc_factor.result
new file mode 100644
index 000000000..31d0f8ffd
--- /dev/null
+++ b/test/engine/small_alloc_factor.result
@@ -0,0 +1,70 @@
+env = require('test_run')
+---
+...
+test_run = env.new()
+---
+...
+test_run:cmd('create server test with script="engine/small_alloc_factor.lua"')
+---
+- true
+...
+test_run:cmd('start server test with args="none"')
+---
+- true
+...
+test_run:cmd('switch test')
+---
+- true
+...
+s = box.schema.space.create('test')
+---
+...
+_ = s:create_index('test')
+---
+...
+function str(i) return string.rep('a', math.floor(256 * math.pow(1.03, i))) end
+---
+...
+for i=1,276 do _ = s:replace{i+200, str(i)} end
+---
+...
+for i=1,274 do _ = s:delete{i+200} end
+---
+...
+collectgarbage('collect')
+---
+- 0
+...
+_ = s:replace{200+277, str(275)}
+---
+...
+_ = s:delete{200+275}
+---
+...
+collectgarbage('collect')
+---
+- 0
+...
+_ = s:delete{200+276}
+---
+...
+collectgarbage('collect')
+---
+- 0
+...
+test_run:cmd('switch default')
+---
+- true
+...
+test_run:cmd('stop server test')
+---
+- true
+...
+test_run:cmd('cleanup server test')
+---
+- true
+...
+test_run:cmd('delete server test')
+---
+- true
+...
diff --git a/test/engine/small_alloc_factor.test.lua b/test/engine/small_alloc_factor.test.lua
new file mode 100644
index 000000000..4edc4e5c2
--- /dev/null
+++ b/test/engine/small_alloc_factor.test.lua
@@ -0,0 +1,20 @@
+env = require('test_run')
+test_run = env.new()
+test_run:cmd('create server test with script="engine/small_alloc_factor.lua"')
+test_run:cmd('start server test with args="none"')
+test_run:cmd('switch test')
+s = box.schema.space.create('test')
+_ = s:create_index('test')
+function str(i) return string.rep('a', math.floor(256 * math.pow(1.03, i))) end
+for i=1,276 do _ = s:replace{i+200, str(i)} end
+for i=1,274 do _ = s:delete{i+200} end
+collectgarbage('collect')
+_ = s:replace{200+277, str(275)}
+_ = s:delete{200+275}
+collectgarbage('collect')
+_ = s:delete{200+276}
+collectgarbage('collect')
+test_run:cmd('switch default')
+test_run:cmd('stop server test')
+test_run:cmd('cleanup server test')
+test_run:cmd('delete server test')
--
2.20.1
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: [Tarantool-patches] [PATCH] memtx: change small allocator behavior
2020-12-23 13:14 ` [Tarantool-patches] [PATCH] memtx: " mechanik20051988
@ 2020-12-24 15:13 ` Vladislav Shpilevoy
[not found] ` <0076A088-8CBC-4238-9EEB-0C73EC516098@hxcore.ol>
0 siblings, 1 reply; 14+ messages in thread
From: Vladislav Shpilevoy @ 2020-12-24 15:13 UTC (permalink / raw)
To: mechanik20051988; +Cc: tarantool-patches
Hi! Thanks for the fixes!
On 23.12.2020 14:14, mechanik20051988 via Tarantool-patches wrote:
> From: mechanik20051988 <mechanik20.05.1988@gmail.com>
>
> Branch: https://github.com/tarantool/tarantool/tree/mechanik20051988/gh-5216-fix-strange-allocator-behavior
> Pull request: https://github.com/tarantool/tarantool/pull/5503
>
> Thank you for the previous review. Here some answers on you questions.
I don't remember the questions by their numbers. I enumerate them so as
people wouldn't miss any of the comments. For example, when I say 'see 10
comments below', it is supposed to be easier to check if you didn't miss,
say, comment 5, between comments 4 and 6.
Try to follow this guide:
https://github.com/tarantool/tarantool/wiki/Code-review-procedure#during-the-review
Responses better be right under the questions, in response to the original
email in the old thread, with diff under each comment.
> 2. As you can see at this moment, small_alloc_create already
> has restrictions on alloc_factor (see small.c in master branch)
> They change it silently.
> if (alloc_factor > 2.0)
> alloc_factor = 2.0;
> /*
> * Correct the user-supplied alloc_factor to ensure that
> * it actually produces growing object sizes.
> */
> 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;
> }
> I only moved them in memtx_engine.c with an explicit message.
Ok, I see now.
See 3 comments below.
> src/box/memtx_engine.c | 8 +++
> src/lib/small | 2 +-
> test/engine/engine.cfg | 3 ++
> test/engine/small_alloc_factor.lua | 11 ++++
> test/engine/small_alloc_factor.result | 70 +++++++++++++++++++++++++
> test/engine/small_alloc_factor.test.lua | 20 +++++++
> 6 files changed, 113 insertions(+), 1 deletion(-)
> create mode 100644 test/engine/small_alloc_factor.lua
> create mode 100644 test/engine/small_alloc_factor.result
> create mode 100644 test/engine/small_alloc_factor.test.lua
>
> diff --git a/src/box/memtx_engine.c b/src/box/memtx_engine.c
> index 4f1fe3a3f..3ab292f2e 100644
> --- a/src/box/memtx_engine.c
> +++ b/src/box/memtx_engine.c
> @@ -1116,6 +1116,14 @@ memtx_engine_new(const char *snap_dirname, bool force_recovery,
> if (objsize_min < OBJSIZE_MIN)
> objsize_min = OBJSIZE_MIN;
>
> + if (alloc_factor > 2) {
> + say_error("Alloc factor must be less than or equal to 2.0. It will be reduced to 2.0");
> + alloc_factor = 2.0;
> + } else if (alloc_factor <= 1.0) {
> + say_error("Alloc factor must be greater than then 1.0. It will be increased to 1.001");
1. Can't parse 'than then' - please, rephrase. I assume 'then' is
not needed.
> + alloc_factor = 1.001;
2. I don't see the factor being rounded up in the original code.
Why did you add it? And why 1.0 is bad?
> + }
> diff --git a/test/engine/small_alloc_factor.result b/test/engine/small_alloc_factor.result
> new file mode 100644
> index 000000000..31d0f8ffd
> --- /dev/null
> +++ b/test/engine/small_alloc_factor.result
3. Please, read this document, and especially the specified
section: https://github.com/tarantool/tarantool/wiki/Code-review-procedure#testing.
The test file names should have a special pattern. Please, follow it.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation
2020-12-23 13:14 [Tarantool-patches] [PATCH v2 0/3] change small allocator behavior mechanik20051988
2020-12-23 13:14 ` [Tarantool-patches] [PATCH] memtx: " mechanik20051988
@ 2020-12-23 13:14 ` mechanik20051988
2020-12-24 15:13 ` Vladislav Shpilevoy
2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 2/3] test: add small allocator performance test mechanik20051988
2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 3/3] small: changed small allocator pool management mechanik20051988
3 siblings, 1 reply; 14+ messages in thread
From: mechanik20051988 @ 2020-12-23 13:14 UTC (permalink / raw)
To: v.shpilevoy; +Cc: tarantool-patches
From: Aleksandr Lyapunov <alyapunov@tarantool.org>
1. Fixed
2. Fixed
3. Fixed
4. Yes count of incremental size == (1 << effective_bits), for example:
granularity = 8,
alloc_factor = 1.05,
min_alloc = 24
so we have:
ignore_bits_count = 3,
effective_bits = 4,
effective_size = 16,
effective_mask = 15,
size_shift = 16
and we can calculate first incremental pool sizes:
24, 32, 40, 48, ... and so on 16 times
5. Change rnd to ignore bits count
6. eff means effective, change to effective
7. For faster calculation, so as not to calculate in the process
of calculating the offset of the pool from the beginning of the array
8. Yes, drop it
9. The user configures the allocation factor, the actual factor may differ,
but it depends directly on the parameter set by the user.
User can choose the parameter so that it suits the real allocation factor.
10. Fixed
11. Fls - find last significant bit see for example
https://elixir.bootlin.com/linux/latest/source/arch/x86/include/asm/bitops.h#L324
12. Yes you right, it's offset in the array of pools. Rename this functions
small_class_calc_offset_by_size and small_class_calc_size_by_offset
13. Fixed
14. You can calculate it manually using
float log2 = logf(2);
sc->effective_bits = (unsigned)(logf(log2 / logf(desired_factor)) / log2 + .5);
15. Fixed
16. These are numbers from my head, i change test to make it more clear
small_alloc uses a collection of mempools of different sizes.
If small_alloc stores all mempools in an array then it have to determine
an offset in that array where the most suitable mempool is.
Let's name the offset as 'size class' and the size that the corresponding
mempool allocates as 'class size'.
Historically the class sizes grow incrementally up to some point and then
(at some size class) grow exponentially with user-provided factor.
Apart from incremental part the exponential part is not very obvious.
Binary search and floating-point logarithm could be used for size class
determination but both approaches seem to be too slow.
This patch implements faster size class evaluation based on integral
operations.
Part of #5216
---
CMakeLists.txt | 4 +
LICENSE | 2 +-
small/small_class.c | 56 ++++++++
small/small_class.h | 218 +++++++++++++++++++++++++++++
test/CMakeLists.txt | 9 ++
test/small_class.c | 176 +++++++++++++++++++++++
test/small_class.result | 15 ++
test/small_class_branchless.result | 15 ++
8 files changed, 494 insertions(+), 1 deletion(-)
create mode 100644 small/small_class.c
create mode 100644 small/small_class.h
create mode 100644 test/small_class.c
create mode 100644 test/small_class.result
create mode 100644 test/small_class_branchless.result
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 4c575eb..d797128 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -53,6 +53,7 @@ set(lib_headers
small/rlist.h
small/slab_arena.h
small/slab_cache.h
+ small/small_class.h
small/small.h
small/lsregion.h
small/static.h)
@@ -63,6 +64,7 @@ set(lib_sources
small/region.c
small/mempool.c
small/slab_arena.c
+ small/small_class.c
small/small.c
small/matras.c
small/ibuf.c
@@ -71,6 +73,7 @@ set(lib_sources
small/static.c)
add_library(${PROJECT_NAME} STATIC ${lib_sources})
+target_link_libraries(${PROJECT_NAME} m)
enable_testing()
add_subdirectory(test)
@@ -87,6 +90,7 @@ if (NOT ENABLE_VALGRIND)
endif()
add_library(${PROJECT_NAME}_shared SHARED ${lib_sources})
+target_link_libraries(${PROJECT_NAME}_shared m)
set_target_properties(${PROJECT_NAME}_shared PROPERTIES VERSION 1.0 SOVERSION 1)
set_target_properties(${PROJECT_NAME}_shared PROPERTIES OUTPUT_NAME ${PROJECT_NAME})
Redistribution and use in source and binary forms, with or
without modification, are permitted provided that the following
diff --git a/small/small_class.c b/small/small_class.c
new file mode 100644
index 0000000..99915a8
--- /dev/null
+++ b/small/small_class.c
@@ -0,0 +1,56 @@
+/*
+ * Copyright 2010-2020, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "small_class.h"
+#include <assert.h>
+#include <math.h>
+
+void
+small_class_create(struct small_class *sc, unsigned granularity,
+ float desired_factor, unsigned min_alloc)
+{
+ 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. */
+
+ sc->granularity = granularity;
+ sc->ignore_bits_count = __builtin_ctz(granularity);
+ float log2 = logf(2);
+ sc->effective_bits = (unsigned)(logf(log2 / logf(desired_factor)) / log2 + .5);
+ sc->effective_size = 1u << sc->effective_bits;
+ sc->effective_mask = sc->effective_size - 1u;
+ sc->size_shift = min_alloc - granularity;
+ sc->size_shift_plus_1 = sc->size_shift + 1;
+
+ sc->actual_factor = powf(2, 1.f / powf(2, sc->effective_bits));
+}
diff --git a/small/small_class.h b/small/small_class.h
new file mode 100644
index 0000000..0677557
--- /dev/null
+++ b/small/small_class.h
@@ -0,0 +1,218 @@
+#pragma once
+/*
+ * Copyright 2010-2020, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/**
+ * CHAR_BIT
+ */
+#include <limits.h>
+
+/**
+ *
+ * small_alloc uses a collection of mempools of different sizes.
+ * If small_alloc stores all mempools in an array then it have to determine
+ * an offset in that array where the most suitable mempool is.
+ * Let's name the offset as 'size class' and the size that the corresponding
+ * mempool allocates as 'class size'.
+ * Historically the class sizes grow incrementally up to some point and then
+ * (at some size class) grow exponentially with user-provided factor.
+ * Apart from incremental part the exponential part is not very obvious.
+ * Binary search and floating-point logarithm could be used for size class
+ * determination but both approaches seem to be too slow.
+ *
+ * This module is designed for faster size class determination.
+ * The idea is to use integral binary logarithm (bit search) and improve it
+ * in some way in order to increase precision - allow other logarithm bases
+ * along with 2.
+ * Binary integral logarithm is just a position of the most significant bit of
+ * a value. Let's look closer to binary representation of an allocation size
+ * and size class that is calculated as binary logarithm:
+ * size | size class
+ * 00001????.. | x
+ * 0001?????.. | x + 1
+ * 001??????.. | x + 2
+ * Let's take into account n lower bits just after the most significant
+ * in the value and divide size class into 2^n subclasses. For example if n = 2:
+ * size | size class
+ * 0000100??.. | x
+ * 0000101??.. | x + 1
+ * 0000110??.. | x + 2
+ * 0000111??.. | x + 3
+ * 000100???.. | x + 4 <- here the size doubles, in 4 = 2^n steps.
+ * 000101???.. | x + 5
+ * That gives us some kind of approximation of a logarithm with a base equal
+ * to pow(2, 1 / pow(2, n)). That means that for given factor 'f' of exponent
+ * we can choose such a number of bits 'n' that gives us an approximation of
+ * an exponent that is close to 'f'.
+ *
+ * Of course if the most significant bit of a value is less than 'n' we can't
+ * use the formula above. But it's not a problem since we can (and even would
+ * like to!) use an incremental size class evaluation of those sizes.
+ * size | size class
+ * 0000001 | 1 <- incremental growth.
+ * 0000010 | 2
+ * 0000011 | 3
+ * 0000100 | 4 <- here the exponential approximation starts.
+ * 0000101 | 5
+ * 0000110 | 6
+ * 0000111 | 7
+ * 000100? | 8
+ * 000101? | 9
+ *
+ * There's some implementation details. Size class is zero based, and the size
+ * must be rounded up to the closest class size. Even more, we want to round
+ * up size to some granularity, we doesn't want to have incremental pools of
+ * sizes 1, 2, 3.., we want them to be 8, 16, 24.... All that is achieved by
+ * subtracting size by one and omitting several lower bits of the size.
+ */
+
+#if defined(__cplusplus)
+extern "C" {
+#endif /* defined(__cplusplus) */
+
+struct small_class {
+ /** Every class size must be a multiple of this. */
+ unsigned granularity;
+ /** log2(granularity), ignore those number of the lowest bit of size. */
+ unsigned ignore_bits_count;
+ /**
+ * A number of bits (after the most significant bit) that are used in
+ * size class evaluation ('n' in the Explanation above).
+ */
+ unsigned effective_bits;
+ /** 1u << effective_bits. */
+ unsigned effective_size;
+ /** effective_size - 1u. */
+ unsigned effective_mask;
+ /**
+ * By default the lowest possible allocation size (aka class size of
+ * class 0) is granularity. If a user wants different min_alloc, we
+ * simply shift sizes; min_alloc = granularity + size_shift.
+ */
+ unsigned size_shift;
+ /** Actually we need 'size_shift + 1', so store it. */
+ unsigned size_shift_plus_1;
+ /**
+ * Exponential factor, approximation of which we managed to provide.
+ * It is calculated from requested_factor, it's guaranteed that
+ * it must be in range [requested_factor/k, requested_factor*k],
+ * where k = pow(requested_factor, 0.5).
+ */
+ float actual_factor;
+};
+
+/**
+ * Create an instance of small_class evaluator. All args must meet the
+ * requirements, undefined behaviour otherwise (at least assert).
+ * @param sc - instance to create.
+ * @param granularity - any class size will be a multiple of this value.
+ * Must be a power of 2 (and thus greater than zero).
+ * @param desired_factor - desired factor of growth of class size.
+ * 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.
+ */
+void
+small_class_create(struct small_class *sc, unsigned granularity,
+ float desired_factor, unsigned min_alloc);
+
+/**
+ * Find position of the most significant bit in a value.
+ * If the value is zero the behaviour is undefined.
+ */
+static inline unsigned
+small_class_fls(unsigned value)
+{
+ /*
+ * Usually clz is implemented as bsr XOR 0x1f.
+ * If we add another XOR the compiler will squash 'em and leave just bsr.
+ */
+ unsigned clz = __builtin_clz(value);
+ return (sizeof(value) * CHAR_BIT - 1) ^ clz;
+}
+
+static inline unsigned
+small_class_calc_offset_by_size(struct small_class *sc, unsigned size)
+{
+ /*
+ * Usually we have to decrement size in order to:
+ * 1)make zero base class.
+ * 2)round up to class size.
+ * Also here is a good place to shift size if a user wants the lowest
+ * class size to be different from granularity.
+ */
+ unsigned checked_size = size - sc->size_shift_plus_1;
+ /* Check overflow. */
+ size = checked_size > size ? 0 : checked_size;
+ /* Omit never significant bits. */
+ size >>= sc->ignore_bits_count;
+#ifndef SMALL_CLASS_BRANCHLESS
+ if (size < sc->effective_size)
+ return size; /* Linear approximation, faster part. */
+ /* Get log2 base part of result. Effective bits are omitted. */
+ unsigned log2 = small_class_fls(size >> sc->effective_bits);
+#else
+ /* Evaluation without branching */
+ /*
+ * Get log2 base part of result. Effective bits are omitted.
+ * Also note that 1u is ORed to make log2 == 0 for smaller sizes.
+ */
+ unsigned log2 = small_class_fls((size >> sc->effective_bits) | 1u);
+#endif
+ /* Effective bits (and leading 1?) in size, represent small steps. */
+ unsigned linear_part = size >> log2;
+ /* Log2 part, multiplied correspondingly, represent big steps. */
+ unsigned log2_part = log2 << sc->effective_bits;
+ /* Combine the result. */
+ return linear_part + log2_part;
+}
+
+static inline unsigned
+small_class_calc_size_by_offset(struct small_class *sc, unsigned cls)
+{
+ ++cls;
+ /* Effective bits (without leading 1) in size */
+ unsigned linear_part = cls & sc->effective_mask;
+ /* Log2 base part of the size, maybe with leading 1 of the size. */
+ unsigned log2 = cls >> sc->effective_bits;
+ if (log2 != 0) {
+ /* Remove leading 1 from log2 part and add to linear part. */
+ log2--;
+ linear_part |= sc->effective_size;
+ }
+ /* Reassemble size and add never significant bits. */
+ return sc->size_shift + (linear_part << log2 << sc->ignore_bits_count);
+}
+
+#if defined(__cplusplus)
+} /* extern "C" { */
+#endif /* defined(__cplusplus) */
+
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 8317c65..5ee0821 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -31,6 +31,13 @@ set_source_files_properties(rb_rand.cc PROPERTIES
add_executable(mempool.test mempool.c)
target_link_libraries(mempool.test small)
+add_executable(small_class.test small_class.c unit.c)
+target_link_libraries(small_class.test small)
+
+add_executable(small_class_branchless.test small_class.c unit.c)
+target_link_libraries(small_class_branchless.test small)
+target_compile_definitions(small_class_branchless.test PUBLIC SMALL_CLASS_BRANCHLESS)
+
add_executable(small_alloc.test small_alloc.c)
target_link_libraries(small_alloc.test small)
@@ -64,6 +71,8 @@ add_test(region ${CMAKE_CURRENT_BUILD_DIR}/region.test)
add_test(ibuf ${CMAKE_CURRENT_BUILD_DIR}/ibuf.test)
add_test(obuf ${CMAKE_CURRENT_BUILD_DIR}/obuf.test)
add_test(mempool ${CMAKE_CURRENT_BUILD_DIR}/mempool.test)
+add_test(small_class ${CMAKE_CURRENT_BUILD_DIR}/small_class.test)
+add_test(small_class_branchless ${CMAKE_CURRENT_BUILD_DIR}/small_class_branchless.test)
add_test(small_alloc ${CMAKE_CURRENT_BUILD_DIR}/small_alloc.test)
add_test(lf_lifo ${CMAKE_CURRENT_BUILD_DIR}/lf_lifo.test)
add_test(slab_cache ${CMAKE_CURRENT_BUILD_DIR}/slab_cache.test)
diff --git a/test/small_class.c b/test/small_class.c
new file mode 100644
index 0000000..b56cfeb
--- /dev/null
+++ b/test/small_class.c
@@ -0,0 +1,176 @@
+/*
+ * Copyright 2010-2020, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include "small/small_class.h"
+#include "unit.h"
+#include <math.h>
+
+#define SZR(arr) sizeof(arr) / sizeof(arr[0])
+
+static void
+test_class(void)
+{
+ header();
+ plan(0);
+
+ struct small_class sc;
+ small_class_create(&sc, 2, 1.2, 12);
+ unsigned class = small_class_calc_offset_by_size(&sc, 0);
+ unsigned class_size = small_class_calc_size_by_offset(&sc, class);
+
+ for (unsigned size = 1; size <= 100; size++) {
+ unsigned cls = small_class_calc_offset_by_size(&sc, size);
+ if (size <= class_size)
+ fail_unless(cls == class);
+ if (size == class_size + 1) {
+ fail_unless(cls == class + 1);
+ class = cls;
+ class_size = small_class_calc_size_by_offset(&sc, class);
+ }
+ }
+
+ check_plan();
+ footer();
+}
+
+static void
+check_expectation()
+{
+ header();
+
+ const unsigned granularity_arr[] = {1, 2, 4, 8};
+ const unsigned test_sizes = 1024;
+ const unsigned test_classes = 1024;
+ /*
+ * We expect 4 effective bits with factor = 1.05,
+ * see small_class_create
+ */
+ float factor = 1.05;
+ /*
+ * 1 << 4 (effective bits mentioned above)
+ */
+ const unsigned eff_size = 16;
+ unsigned test_class_size[test_classes + eff_size];
+
+ plan(0);
+
+ for (unsigned variant = 0; variant < SZR(granularity_arr); variant++) {
+ unsigned granularity = granularity_arr[variant];
+ unsigned min_alloc = granularity + (rand () % 16);
+
+ {
+ unsigned class_size = min_alloc - granularity;
+ /* incremental growth */
+ for (unsigned i = 0; i < eff_size; i++) {
+ class_size += granularity;
+ test_class_size[i] = class_size;
+ }
+ /* exponential growth */
+ unsigned growth = granularity;
+ for (unsigned i = eff_size; i < test_classes; i += eff_size) {
+ for (unsigned j = 0; j < eff_size; j++) {
+ class_size += growth;
+ test_class_size[i + j] = class_size;
+ }
+ growth *= 2;
+ }
+ }
+
+ struct small_class sc;
+ small_class_create(&sc, granularity, factor, min_alloc);
+ fail_unless(sc.effective_size == eff_size);
+
+ for (unsigned s = 0; s <= test_sizes; s++) {
+ unsigned expect_class = 0;
+ while (expect_class < test_classes && s > test_class_size[expect_class])
+ expect_class++;
+ unsigned expect_class_size = test_class_size[expect_class];
+ unsigned got_class = small_class_calc_offset_by_size(&sc, s);
+ unsigned got_class_size = small_class_calc_size_by_offset(&sc, got_class);
+ fail_unless(got_class == expect_class);
+ fail_unless(got_class_size == expect_class_size);
+ }
+ }
+
+ check_plan();
+ footer();
+}
+
+static void
+check_factor()
+{
+ header();
+
+ plan(0);
+
+ 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 k = powf(factor, 0.5f);
+ fail_unless(sc.actual_factor >= factor / k && sc.actual_factor <= factor * k);
+
+ float min_deviation = 1.f;
+ float max_deviation = 1.f;
+ /* Skip incremental growth. */
+ for (unsigned i = sc.effective_size; i < sc.effective_size * 3; i++) {
+ unsigned cl_sz1 = small_class_calc_size_by_offset(&sc, i);
+ unsigned cl_sz2 = small_class_calc_size_by_offset(&sc, i + 1);
+ float real_growth = 1.f * cl_sz2 / cl_sz1;
+ float deviation = sc.actual_factor / real_growth;
+ if (deviation < min_deviation)
+ min_deviation = deviation;
+ if (deviation > max_deviation)
+ max_deviation = deviation;
+ }
+ float ln2 = logf(2);
+ fail_unless(min_deviation > ln2 && max_deviation < 2 * ln2);
+ }
+ }
+
+ check_plan();
+ footer();
+}
+
+
+int
+main(void)
+{
+ header();
+ plan(3);
+
+ test_class();
+ check_expectation();
+ check_factor();
+
+ int rc = check_plan();
+ footer();
+ return rc;
+}
diff --git a/test/small_class.result b/test/small_class.result
new file mode 100644
index 0000000..de74f00
--- /dev/null
+++ b/test/small_class.result
@@ -0,0 +1,15 @@
+ *** main ***
+1..3
+ *** test_class ***
+ 1..0
+ok 1 - subtests
+ *** test_class: done ***
+ *** check_expectation ***
+ 1..0
+ok 2 - subtests
+ *** check_expectation: done ***
+ *** check_factor ***
+ 1..0
+ok 3 - subtests
+ *** check_factor: done ***
+ *** main: done ***
diff --git a/test/small_class_branchless.result b/test/small_class_branchless.result
new file mode 100644
index 0000000..de74f00
--- /dev/null
+++ b/test/small_class_branchless.result
@@ -0,0 +1,15 @@
+ *** main ***
+1..3
+ *** test_class ***
+ 1..0
+ok 1 - subtests
+ *** test_class: done ***
+ *** check_expectation ***
+ 1..0
+ok 2 - subtests
+ *** check_expectation: done ***
+ *** check_factor ***
+ 1..0
+ok 3 - subtests
+ *** check_factor: done ***
+ *** main: done ***
--
2.20.1
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation
2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation mechanik20051988
@ 2020-12-24 15:13 ` Vladislav Shpilevoy
[not found] ` <A90D94B7-298A-4D1B-8134-6EE2ED45D615@hxcore.ol>
2020-12-28 12:10 ` [Tarantool-patches] " Vladislav Shpilevoy
0 siblings, 2 replies; 14+ messages in thread
From: Vladislav Shpilevoy @ 2020-12-24 15:13 UTC (permalink / raw)
To: mechanik20051988; +Cc: tarantool-patches
Thanks for the fixes!
>> Lets omit unnecessary changes. This clearly has nothing to do with
>> the functional part of the patch.
> 1. Fixed
Nope, it is not. The diff hunk is still here.
>> I don't understand. So you can make the factor smaller than it was
>> requested? What is the point in configuring the factor then?
> 9. The user configures the allocation factor, the actual factor may differ,
> but it depends directly on the parameter set by the user.
> User can choose the parameter so that it suits the real allocation factor.
But this is not the answer on the question, is it? What is the point is
making it bigger if it can get smaller in the result? And the user can't
even understand how to select the factor he actually needs. For instance,
he sets 1.5, but he has no idea what will be the final value. How can one
tune it then? How to choose the value?
> diff --git a/small/small_class.h b/small/small_class.h
> new file mode 100644
> index 0000000..0677557
> --- /dev/null
> +++ b/small/small_class.h
> @@ -0,0 +1,218 @@
> +
> +/**
> + * CHAR_BIT
> + */
> +#include <limits.h>
> +
> +/**
> + *
Unnecessary empty line.
> + * small_alloc uses a collection of mempools of different sizes.
> + * If small_alloc stores all mempools in an array then it have to determine
> + * an offset in that array where the most suitable mempool is.
> + * Let's name the offset as 'size class' and the size that the corresponding
> + * mempool allocates as 'class size'.> diff --git a/test/small_class.c b/test/small_class.c
> new file mode 100644
> index 0000000..b56cfeb
> --- /dev/null
> +++ b/test/small_class.c
> @@ -0,0 +1,176 @@
> +#include "small/small_class.h"
> +#include "unit.h"
> +#include <math.h>
> +
> +#define SZR(arr) sizeof(arr) / sizeof(arr[0])
We have lengthof() in trivia/util.h.
The test below I still don't understand in a single bit :D
But I give up, and hope Alexander L. validated all the calculations
and ensured they don't make things slower.
^ permalink raw reply [flat|nested] 14+ messages in thread[parent not found: <A90D94B7-298A-4D1B-8134-6EE2ED45D615@hxcore.ol>]
* Re: [Tarantool-patches] FW: [PATCH v2 1/3] small: implement new size class evaluation
[not found] ` <A90D94B7-298A-4D1B-8134-6EE2ED45D615@hxcore.ol>
@ 2020-12-25 7:48 ` Evgeny Mekhanik
0 siblings, 0 replies; 14+ messages in thread
From: Evgeny Mekhanik @ 2020-12-25 7:48 UTC (permalink / raw)
To: Vladislav Shpilevoy; +Cc: tarantool-patches
[-- Attachment #1: Type: text/plain, Size: 2458 bytes --]
>> I don't understand. So you can make the factor smaller than it was
>> requested? What is the point in configuring the factor then?
> 9. The user configures the allocation factor, the actual factor may differ,
> but it depends directly on the parameter set by the user.
> User can choose the parameter so that it suits the real allocation factor.
But this is not the answer on the question, is it? What is the point is
making it bigger if it can get smaller in the result? And the user can't
even understand how to select the factor he actually needs. For instance,
he sets 1.5, but he has no idea what will be the final value. How can one
tune it then? How to choose the value?
Answer:
This is an approximating function, so it really changes the allocation factor.
We can pass the real factor up and print it so that the user understands the real value
> diff --git a/small/small_class.h b/small/small_class.h
> new file mode 100644
> index 0000000..0677557
> --- /dev/null
> +++ b/small/small_class.h
> @@ -0,0 +1,218 @@
> +
> +/**
> + * CHAR_BIT
> + */
> +#include <limits.h>
> +
> +/**
> + *
Unnecessary empty line.
Fixed: Delete unnecessary empty line.
+/**
+ * CHAR_BIT
+ */
+#include <limits.h>
+
+/**
+ * small_alloc uses a collection of mempools of different sizes.
> + * small_alloc uses a collection of mempools of different sizes.
> + * If small_alloc stores all mempools in an array then it have to determine
> + * an offset in that array where the most suitable mempool is.
> + * Let's name the offset as 'size class' and the size that the corresponding
> + * mempool allocates as 'class size'.> diff --git a/test/small_class.c b/test/small_class.c
> new file mode 100644
> index 0000000..b56cfeb
> --- /dev/null
> +++ b/test/small_class.c
> @@ -0,0 +1,176 @@
> +#include "small/small_class.h"
> +#include "unit.h"
> +#include <math.h>
> +
> +#define SZR(arr) sizeof(arr) / sizeof(arr[0])
We have lengthof() in trivia/util.h.
Answer:
We can't use lengthof() from trivia/util.h, because this file is not a part of small project.
Small should be built by itself without dependencies from third-party components, but
i change my macro SZR to lengthof as you can see in patch below:
+#include "small/small_class.h"
+#include "unit.h"
+#include <math.h>
+
+#ifndef lengthof
+#define lengthof(array) (sizeof (array) / sizeof ((array)[0]))
+#endif
+
+static void
+test_class(void)
[-- Attachment #2: Type: text/html, Size: 5255 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation
2020-12-24 15:13 ` Vladislav Shpilevoy
[not found] ` <A90D94B7-298A-4D1B-8134-6EE2ED45D615@hxcore.ol>
@ 2020-12-28 12:10 ` Vladislav Shpilevoy
1 sibling, 0 replies; 14+ messages in thread
From: Vladislav Shpilevoy @ 2020-12-28 12:10 UTC (permalink / raw)
To: mechanik20051988; +Cc: tarantool-patches
On 24.12.2020 18:13, Vladislav Shpilevoy via Tarantool-patches wrote:
> Thanks for the fixes!
>
>>> Lets omit unnecessary changes. This clearly has nothing to do with
>>> the functional part of the patch.
>> 1. Fixed
>
> Nope, it is not. The diff hunk is still here.
It is still here. Don't ignore, please.
I took the latest version of your branch, called `git submodule update`,
went to src/lib/small, and the change is here in the first commit.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Tarantool-patches] [PATCH v2 2/3] test: add small allocator performance test
2020-12-23 13:14 [Tarantool-patches] [PATCH v2 0/3] change small allocator behavior mechanik20051988
2020-12-23 13:14 ` [Tarantool-patches] [PATCH] memtx: " mechanik20051988
2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation mechanik20051988
@ 2020-12-23 13:14 ` mechanik20051988
2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 3/3] small: changed small allocator pool management mechanik20051988
3 siblings, 0 replies; 14+ messages in thread
From: mechanik20051988 @ 2020-12-23 13:14 UTC (permalink / raw)
To: v.shpilevoy; +Cc: mechanik20051988, tarantool-patches
From: mechanik20051988 <mechanik20.05.1988@gmail.com>
---
CMakeLists.txt | 1 +
perf/.gitignore | 1 +
perf/CMakeLists.txt | 7 +
perf/small_alloc_perf.c | 375 ++++++++++++++++++++++++++++++++++++++++
4 files changed, 384 insertions(+)
create mode 100644 perf/.gitignore
create mode 100644 perf/CMakeLists.txt
create mode 100644 perf/small_alloc_perf.c
diff --git a/CMakeLists.txt b/CMakeLists.txt
index d797128..b0dec0e 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -77,6 +77,7 @@ target_link_libraries(${PROJECT_NAME} m)
enable_testing()
add_subdirectory(test)
+add_subdirectory(perf)
if(DEFINED SMALL_EMBEDDED)
# Don't build shared library and skip INSTALL() targets if this
diff --git a/perf/.gitignore b/perf/.gitignore
new file mode 100644
index 0000000..9ed3b07
--- /dev/null
+++ b/perf/.gitignore
@@ -0,0 +1 @@
+*.test
diff --git a/perf/CMakeLists.txt b/perf/CMakeLists.txt
new file mode 100644
index 0000000..1a9d933
--- /dev/null
+++ b/perf/CMakeLists.txt
@@ -0,0 +1,7 @@
+add_executable(small_alloc_perf.test small_alloc_perf.c)
+if (NOT ${CMAKE_SYSTEM_NAME} MATCHES "Darwin")
+ set(LIBRT "rt")
+endif ()
+
+target_link_libraries(small_alloc_perf.test small ${LIBRT})
+include_directories("${PROJECT_SOURCE_DIR}")
diff --git a/perf/small_alloc_perf.c b/perf/small_alloc_perf.c
new file mode 100644
index 0000000..3b9b443
--- /dev/null
+++ b/perf/small_alloc_perf.c
@@ -0,0 +1,375 @@
+#include <small/small.h>
+#include <small/quota.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include <math.h>
+#include "../test/unit.h"
+
+enum {
+ OBJSIZE_MIN = 3 * sizeof(int),
+ OBJECTS_MAX = 1000
+};
+
+const size_t SLAB_SIZE_MIN = 4 * 1024 * 1024;
+const size_t SLAB_SIZE_MAX = 16 * 1024 * 1024;
+static const unsigned long long NANOSEC_PER_SEC = 1000000000;
+static const unsigned long long NANOSEC_PER_MSEC = 1000000;
+#define SZR(arr) sizeof(arr) / sizeof(arr[0])
+
+float slab_alloc_factor[] = {1.01, 1.03, 1.05, 1.1, 1.3, 1.5};
+
+struct slab_arena arena;
+struct slab_cache cache;
+struct small_alloc alloc;
+struct quota quota;
+/** Streak type - allocating or freeing */
+bool allocating = true;
+/** Enable human output */
+bool human = false;
+/** Keep global to easily inspect the core. */
+long seed;
+char json_output[100000];
+size_t length = sizeof(json_output);
+size_t pos = 0;
+
+static int *ptrs[OBJECTS_MAX];
+
+static inline
+long long int timediff(struct timespec *tm1, struct timespec *tm2)
+{
+ return NANOSEC_PER_SEC * (tm2->tv_sec - tm1->tv_sec) +
+ (tm2->tv_nsec - tm1->tv_nsec);
+}
+
+static inline void
+free_checked(int *ptr)
+{
+ int pos = ptr[0];
+ smfree_delayed(&alloc, ptrs[pos], ptrs[pos][1]);
+ ptrs[pos] = NULL;
+}
+
+static float
+calculate_pow_factor(int size_max, int pow_max, int start)
+{
+ return exp(log((double)size_max / start) / pow_max);
+}
+
+static inline void *
+alloc_checked(int pos, int size_min, int size_max, int rnd, double pow_factor)
+{
+ int size;
+ if (ptrs[pos])
+ free_checked(ptrs[pos]);
+
+ if (!allocating)
+ return NULL;
+
+ if (rnd) {
+ size = size_min + (rand() % (size_max - size_min));
+ } else {
+ size = floor(256 * pow(pow_factor, pos));
+ }
+ ptrs[pos] = smalloc(&alloc, size);
+ if (ptrs[pos] == NULL)
+ return NULL;
+ ptrs[pos][0] = pos;
+ ptrs[pos][1] = size;
+ return ptrs[pos];
+}
+
+static int
+small_is_unused_cb(const struct mempool_stats *stats, void *arg)
+{
+ unsigned long *slab_total = arg;
+ *slab_total += stats->slabsize * stats->slabcount;
+ return 0;
+}
+
+static bool
+small_is_unused(void)
+{
+ struct small_stats totals;
+ unsigned long slab_total = 0;
+ small_stats(&alloc, &totals, small_is_unused_cb, &slab_total);
+ if (totals.used > 0)
+ return false;
+ if (slab_cache_used(&cache) > slab_total)
+ return false;
+ return true;
+}
+
+static void
+small_alloc_test(int size_min, int size_max, int iterations_max,
+ int rnd, int cnt)
+{
+ double pow_factor = calculate_pow_factor(size_max, cnt, 256);
+ for (int i = 0; i <= iterations_max; i++) {
+ int mode = i % 3;
+ switch (mode) {
+ case 1:
+ small_alloc_setopt(&alloc,
+ SMALL_DELAYED_FREE_MODE, false);
+ break;
+ case 2:
+ small_alloc_setopt(&alloc,
+ SMALL_DELAYED_FREE_MODE, true);
+ break;
+ default:
+ break;
+ }
+ for (int j = 0; j < cnt; ++j)
+ alloc_checked(j, size_min, size_max, rnd, pow_factor);
+ allocating = !allocating;
+ }
+
+ small_alloc_setopt(&alloc, SMALL_DELAYED_FREE_MODE, false);
+
+ for (int pos = 0; pos < cnt; pos++) {
+ if (ptrs[pos] != NULL)
+ free_checked(ptrs[pos]);
+ }
+
+ /* Trigger garbage collection. */
+ allocating = true;
+ for (int i = 0; i < iterations_max; i++) {
+ if (small_is_unused())
+ break;
+ void *p = alloc_checked(0, size_min, size_max, rnd, pow_factor);
+ if (p != NULL)
+ free_checked(p);
+ }
+}
+
+static void
+print_json_test_header(const char *type)
+{
+ size_t x = snprintf (json_output + pos, length,
+ " \"%s\": {\n", type);
+ length -=x;
+ pos +=x;
+ x = snprintf (json_output + pos, length,
+ " \"alloc factor\": {\n");
+ length -=x;
+ pos +=x;
+ for (unsigned int i = 0; i < SZR(slab_alloc_factor); i++) {
+ size_t x = snprintf (json_output + pos, length,
+ " \"%.4f\"\n", slab_alloc_factor[i]);
+ length -=x;
+ pos +=x;
+ }
+ x = snprintf (json_output + pos, length, " },\n");
+ length -=x;
+ pos +=x;
+ x = snprintf (json_output + pos, length,
+ " \"time, s\": {\n");
+ length -=x;
+ pos +=x;
+}
+
+static void
+print_json_test_finish(const char * finish)
+{
+ size_t x = snprintf (json_output + pos, length, " }\n");
+ length -=x;
+ pos +=x;
+ x = snprintf (json_output + pos, length, " }%s\n", finish);
+ length -=x;
+ pos +=x;
+}
+
+static void
+print_json_test_result(double time)
+{
+ size_t x = snprintf (json_output + pos, length,
+ " \"%.3f\"\n", time);
+ length -=x;
+ pos +=x;
+}
+
+static void
+small_alloc_basic(unsigned int slab_size)
+{
+ struct timespec tm1, tm2;
+ if(human) {
+ fprintf(stderr, "| SMALL RANDOM "
+ "ALLOCATION RESULT TABLE |\n");
+ fprintf(stderr, "|___________________________________"
+ "_________________________________|\n");
+ fprintf(stderr, "| alloc_factor "
+ " | time, ms |\n");
+ fprintf(stderr, "|__________________________________|"
+ "_________________________________|\n");
+ } else {
+ print_json_test_header("random");
+ }
+ quota_init("a, UINT_MAX);
+ 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++) {
+ small_alloc_create(&alloc, &cache,
+ OBJSIZE_MIN, slab_alloc_factor[i]);
+ int size_min = OBJSIZE_MIN;
+ int size_max = (int)alloc.objsize_max - 1;
+ fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm1) == 0);
+ small_alloc_test(size_min, size_max, 300, 1, OBJECTS_MAX);
+ fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm2) == 0);
+ if (human) {
+ fprintf(stderr, "| %.4f |"
+ " %6llu |\n",
+ slab_alloc_factor[i],
+ timediff(&tm1, &tm2) / NANOSEC_PER_MSEC);
+ } else {
+ print_json_test_result(timediff(&tm1, &tm2) /
+ NANOSEC_PER_MSEC);
+ }
+ small_alloc_destroy(&alloc);
+ }
+ slab_cache_destroy(&cache);
+ slab_arena_destroy(&arena);
+ quota_init("a, UINT_MAX);
+ slab_arena_create(&arena, "a, 0, slab_size, MAP_PRIVATE);
+ slab_cache_create(&cache, &arena);
+ if (human) {
+ fprintf(stderr, "|__________________________________|"
+ "_________________________________|\n");
+ fprintf(stderr, "| SMALL EXP GROW "
+ "ALLOCATION RESULT TABLE |\n");
+ fprintf(stderr, "|___________________________________"
+ "_________________________________|\n");
+ fprintf(stderr, "| alloc_factor "
+ " | time, ms |\n");
+ fprintf(stderr, "|__________________________________|"
+ "_________________________________|\n");
+ } else {
+ print_json_test_finish(",");
+ print_json_test_header("exponent");
+ }
+ for (unsigned int i = 0; i < SZR(slab_alloc_factor); i++) {
+ small_alloc_create(&alloc, &cache,
+ OBJSIZE_MIN, slab_alloc_factor[i]);
+ int size_min = OBJSIZE_MIN;
+ int size_max = (int)alloc.objsize_max - 1;
+ fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm1) == 0);
+ small_alloc_test(size_min, size_max, 1000, 0, OBJECTS_MAX);
+ fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm2) == 0);
+ if (human) {
+ fprintf(stderr, "| %.4f |"
+ " %6llu |\n",
+ slab_alloc_factor[i],
+ timediff(&tm1, &tm2) / NANOSEC_PER_MSEC);
+ } else {
+ print_json_test_result(timediff(&tm1, &tm2) /
+ NANOSEC_PER_MSEC);
+ }
+ small_alloc_destroy(&alloc);
+ }
+ if (human) {
+ fprintf(stderr, "|___________________________________"
+ "_________________________________|\n");
+ } else {
+ print_json_test_finish(",");
+ }
+ slab_cache_destroy(&cache);
+ slab_arena_destroy(&arena);
+}
+
+static void
+small_alloc_large()
+{
+ struct timespec tm1, tm2;
+ size_t large_size_min = mempool_objsize_max(cache.arena->slab_size);
+ size_t large_size_max = 2 * cache.arena->slab_size;
+ if (human) {
+ fprintf(stderr, "| LARGE RANDOM "
+ "ALLOCATION RESULT TABLE |\n");
+ fprintf(stderr, "|___________________________________"
+ "_________________________________|\n");
+ fprintf(stderr, "| alloc_factor "
+ " | time, ms |\n");
+ fprintf(stderr, "|__________________________________|"
+ "_________________________________|\n");
+ } else {
+ print_json_test_header("large");
+ }
+ for (unsigned int i = 0; i < SZR(slab_alloc_factor); i++) {
+ small_alloc_create(&alloc, &cache, OBJSIZE_MIN,
+ slab_alloc_factor[i]);
+ 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);
+ if (human) {
+ fprintf(stderr, "| %.4f |"
+ " %6llu |\n",
+ slab_alloc_factor[i],
+ timediff(&tm1, &tm2) / NANOSEC_PER_MSEC);
+ } else {
+ print_json_test_result(timediff(&tm1, &tm2) /
+ NANOSEC_PER_MSEC);
+ }
+ small_alloc_destroy(&alloc);
+ }
+ if (human) {
+ fprintf(stderr, "|___________________________________"
+ "_________________________________|\n");
+ } else {
+ print_json_test_finish("");
+ }
+}
+
+int main(int argc, char* argv[])
+{
+ size_t x;
+ seed = time(0);
+ srand(seed);
+
+ if (argc == 2 && !strcmp(argv[1], "-h")) //human clear output
+ human = true;
+
+ if (!human) {
+ x = snprintf (json_output + pos, length, "{\n");
+ length -=x;
+ pos +=x;
+ }
+ for (unsigned int slab_size = SLAB_SIZE_MIN; slab_size <= SLAB_SIZE_MAX;
+ slab_size *= 2) {
+ if(human) {
+ fprintf(stderr, "_____________________________________"
+ "_________________________________\n");
+ fprintf(stderr, "| PERFORMANCE TEST WITH SLABSIZE "
+ "%8u BYTES |\n", slab_size);
+ fprintf(stderr, "|___________________________________"
+ "_________________________________|\n");
+ } else {
+ size_t x = snprintf (json_output + pos, length,
+ " \"test\": {\n");
+ length -=x;
+ pos +=x;
+ x = snprintf (json_output + pos, length,
+ " \"slab size, bytes\": \"%u\",\n",
+ slab_size);
+ length -=x;
+ pos +=x;
+ }
+ small_alloc_basic(slab_size);
+ quota_init("a, UINT_MAX);
+ slab_arena_create(&arena, "a, 0, slab_size, MAP_PRIVATE);
+ slab_cache_create(&cache, &arena);
+ small_alloc_large();
+ slab_cache_destroy(&cache);
+ slab_arena_destroy(&arena);
+ if (!human) {
+ x = snprintf (json_output + pos, length,
+ " }%s\n",
+ (slab_size == SLAB_SIZE_MAX ? "" : ","));
+ length -=x;
+ pos +=x;
+ }
+ }
+ if (!human) {
+ x = snprintf (json_output + pos, length, "}\n");
+ fprintf(stderr, "%s\n", json_output);
+ }
+ return EXIT_SUCCESS;
+}
--
2.20.1
^ permalink raw reply [flat|nested] 14+ messages in thread* [Tarantool-patches] [PATCH v2 3/3] small: changed small allocator pool management
2020-12-23 13:14 [Tarantool-patches] [PATCH v2 0/3] change small allocator behavior mechanik20051988
` (2 preceding siblings ...)
2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 2/3] test: add small allocator performance test mechanik20051988
@ 2020-12-23 13:14 ` mechanik20051988
2020-12-24 15:13 ` Vladislav Shpilevoy
3 siblings, 1 reply; 14+ messages in thread
From: mechanik20051988 @ 2020-12-23 13:14 UTC (permalink / raw)
To: v.shpilevoy; +Cc: tarantool-patches
1. Fxed
2. As i understand you comment, you wrote that pools
should be aligned on the 8-byte boundary.
This is guaranteed by the granularity parameter in small_class if min_alloc
have 8-byte boundary alignment. We calculate
min_alloc = objsize_min = small_align(objsize_min, sizeof(intptr_t));
and pass granularity sizeof(uintptr_t).
3. Fixed
4. Fixed
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
---
small/small.c | 216 ++++++++++++--------------------------------------
small/small.h | 47 ++++-------
2 files changed, 66 insertions(+), 197 deletions(-)
diff --git a/small/small.c b/small/small.c
index 48085fb..d3c51b8 100644
--- a/small/small.c
+++ b/small/small.c
@@ -33,66 +33,34 @@
#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. */
@@ -102,53 +70,21 @@ small_alloc_create(struct small_alloc *alloc, struct slab_cache *cache,
{
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);
+ factor_pool_create(alloc);
lifo_init(&alloc->delayed);
lifo_init(&alloc->delayed_large);
@@ -225,72 +161,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 +210,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 +240,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 +248,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..02d42d3 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,19 +148,23 @@ 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.
+ */
void
small_alloc_create(struct small_alloc *alloc, struct slab_cache *cache,
uint32_t objsize_min, float alloc_factor);
--
2.20.1
^ permalink raw reply [flat|nested] 14+ messages in thread