[tarantool-patches] [PATCH v2 small 1/1] small: introduce static allocator
Vladislav Shpilevoy
v.shpilevoy at tarantool.org
Sat May 4 21:09:38 MSK 2019
Currently Tarantool has a global thread local array of 4 static
buffers, each 1028 bytes. It provides an API tt_static_buf()
allowing to return them one by one in a cycle. But sometimes it
is needed to obtain a bit bigger buffer, or on the contrary -
many smaller buffers. For example, to store a UDP packet -
~1.5Kb, or a small array of integers, probably not fitting into
1028 bytes.
This patch introduces a cyclic allocator having static thread
local buffer with fixed size 4096 * 3 bytes, and provides an API
to slice it by any smaller sizes. When the buffer is done, it is
recycled.
This allocator will allow to drop tt_static buffers and lots of
other static thread local buffers scattered over Tarantool source
code.
---
Branch: https://github.com/tarantool/small/tree/gerold103/static-allocator
CMakeLists.txt | 6 +-
small/static.c | 34 ++++++++++
small/static.h | 129 +++++++++++++++++++++++++++++++++++++
test/CMakeLists.txt | 4 ++
test/static.c | 150 ++++++++++++++++++++++++++++++++++++++++++++
test/static.result | 18 ++++++
6 files changed, 339 insertions(+), 2 deletions(-)
create mode 100644 small/static.c
create mode 100644 small/static.h
create mode 100644 test/static.c
create mode 100644 test/static.result
diff --git a/CMakeLists.txt b/CMakeLists.txt
index ad27423..2b7d0dc 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -32,7 +32,8 @@ set(lib_headers
small/slab_arena.h
small/slab_cache.h
small/small.h
- small/lsregion.h)
+ small/lsregion.h
+ small/static.h)
set(lib_sources
small/slab_cache.c
@@ -43,7 +44,8 @@ set(lib_sources
small/matras.c
small/ibuf.c
small/obuf.c
- small/lsregion.c)
+ small/lsregion.c
+ small/static.c)
add_library(${PROJECT_NAME} STATIC ${lib_sources})
diff --git a/small/static.c b/small/static.c
new file mode 100644
index 0000000..b8283a7
--- /dev/null
+++ b/small/static.c
@@ -0,0 +1,34 @@
+/*
+ * Copyright 2010-2019, 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 "static.h"
+
+__thread char static_storage_buffer[SMALL_STATIC_SIZE];
+__thread size_t static_storage_pos = 0;
diff --git a/small/static.h b/small/static.h
new file mode 100644
index 0000000..e0db777
--- /dev/null
+++ b/small/static.h
@@ -0,0 +1,129 @@
+#ifndef TARANTOOL_SMALL_STATIC_H_INCLUDED
+#define TARANTOOL_SMALL_STATIC_H_INCLUDED
+/*
+ * Copyright 2010-2019, 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 <stddef.h>
+#include <string.h>
+#include "slab_arena.h"
+
+enum {
+ /**
+ * Two pages (8192) would be too small for arbitrary
+ * cases, but plus even 1 byte would occupy the whole new
+ * page anyway, so here it is 3 pages.
+ */
+ SMALL_STATIC_SIZE = 4096 * 3,
+};
+
+/**
+ * Thread-local statically allocated temporary BSS resident
+ * cyclic buffer.
+ */
+extern __thread char static_storage_buffer[SMALL_STATIC_SIZE];
+/** Next free position in the buffer. */
+extern __thread size_t static_storage_pos;
+
+/**
+ * Reset the static buffer to its initial state. Can be used, for
+ * example, if there are many reserve + alloc calls, and a caller
+ * needs them contiguous. Reset can prevent buffer position wrap.
+ */
+static inline void
+statis_reset(void)
+{
+ static_storage_pos = 0;
+}
+
+/**
+ * Return a pointer onto the static buffer with at least @a size
+ * continuous bytes. When @a size is bigger than the static buffer
+ * size, then NULL is returned always. This is due to the fact the
+ * buffer is stored in BSS section - it is not dynamic and can't
+ * be extended. If there is not enough space till the end of the
+ * buffer, then it is recycled.
+ */
+static inline void *
+static_reserve(size_t size)
+{
+ if (static_storage_pos + size > SMALL_STATIC_SIZE) {
+ if (size > SMALL_STATIC_SIZE)
+ return NULL;
+ static_storage_pos = 0;
+ }
+ return &static_storage_buffer[static_storage_pos];
+}
+
+/**
+ * Reserve and propagate buffer position so as next allocations
+ * would not get the same pointer until the buffer is recycled.
+ */
+static inline void *
+static_alloc(size_t size)
+{
+ void *res = static_reserve(size);
+ if (res != NULL)
+ static_storage_pos += size;
+ return res;
+}
+
+/**
+ * The same as reserve, but a result address is aligned by @a
+ * alignment.
+ */
+static inline void *
+static_aligned_reserve(size_t size, size_t alignment)
+{
+ void *unaligned = static_reserve(size + alignment - 1);
+ if (unaligned == NULL)
+ return NULL;
+ return (void *) small_align((size_t) unaligned, alignment);
+}
+
+/**
+ * The same as alloc, but a result address is aligned by @a
+ * alignment.
+ */
+static inline void *
+static_aligned_alloc(size_t size, size_t alignment)
+{
+ void *res = static_aligned_reserve(size, alignment);
+ if (res != NULL) {
+ /*
+ * Aligned reserve could add a padding. Restore
+ * the position.
+ */
+ static_storage_pos = (char *) res - &static_storage_buffer[0];
+ static_storage_pos += size;
+ }
+ return res;
+}
+
+#endif /* TARANTOOL_SMALL_STATIC_H_INCLUDED */
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 9520446..84d59dc 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -51,6 +51,9 @@ target_link_libraries(quota.test pthread)
add_executable(quota_lessor.test quota_lessor.c unit.c)
target_link_libraries(quota_lessor.test pthread)
+add_executable(static.test static.c unit.c)
+target_link_libraries(static.test pthread small)
+
include_directories("${PROJECT_SOURCE_DIR}")
add_test(slab_cache ${CMAKE_CURRENT_BUILD_DIR}/slab_cache.test)
@@ -69,6 +72,7 @@ add_test(quota_lessor ${CMAKE_CURRENT_BUILD_DIR}/quota_lessor.test)
add_test(rb ${CMAKE_CURRENT_BUILD_DIR}/rb.test)
add_test(rb_aug ${CMAKE_CURRENT_BUILD_DIR}/rb_aug.test)
add_test(rb_rand ${CMAKE_CURRENT_BUILD_DIR}/rb_rand.test)
+add_test(static ${CMAKE_CURRENT_BUILD_DIR}/static.test)
if(DEFINED SMALL_EMBEDDED)
return()
diff --git a/test/static.c b/test/static.c
new file mode 100644
index 0000000..9e06691
--- /dev/null
+++ b/test/static.c
@@ -0,0 +1,150 @@
+/*
+ * Copyright 2010-2019, 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/static.h"
+#include "unit.h"
+
+static inline void
+check_static_alloc(size_t size, size_t first_pos, size_t end_pos)
+{
+ char *b = static_alloc(size);
+ is(b, &static_storage_buffer[first_pos], "allocated %d from %d",
+ (int) size, (int) first_pos);
+ is(static_storage_pos, end_pos, "to %d", (int) end_pos);
+}
+
+static void
+test_unaligned(void)
+{
+ header();
+ plan(15);
+ statis_reset();
+
+ check_static_alloc(10, 0, 10);
+ int offset = 10;
+ int size = SMALL_STATIC_SIZE / 2;
+ check_static_alloc(size, offset, offset + size);
+ offset += size;
+
+ size = SMALL_STATIC_SIZE / 3;
+ check_static_alloc(size, offset, offset + size);
+ offset += size;
+
+ size = SMALL_STATIC_SIZE - offset;
+ check_static_alloc(size, offset, offset + size);
+
+ size = 1;
+ offset = 0;
+ check_static_alloc(size, offset, offset + size);
+
+ char *a = static_reserve(300);
+ char *b = static_alloc(100);
+ char *c = static_alloc(153);
+ char *d = static_alloc(47);
+ ok(a == b && c == b + 100 && d == c + 153,
+ "big reserve can be consumed in multiple allocs");
+
+ is(static_alloc(SMALL_STATIC_SIZE), static_storage_buffer,
+ "can allocate the entire buffer");
+ is(static_storage_pos, SMALL_STATIC_SIZE, "position is updated");
+
+ is(static_alloc(SMALL_STATIC_SIZE + 1), NULL,
+ "can't allocate more - the memory is static and can't be extended");
+ is(static_storage_pos, SMALL_STATIC_SIZE, "position is not changed");
+
+ check_plan();
+ footer();
+}
+
+static void
+test_aligned(void)
+{
+ header();
+ plan(17);
+ statis_reset();
+ size_t alignment = 8;
+
+ char *p = static_aligned_reserve(0, alignment);
+ is(p, &static_storage_buffer[0], "aligned reserve 0");
+ is(static_storage_pos, 0, "position is not changed");
+
+ p = static_alloc(1);
+ is(p, &static_storage_buffer[0], "alloc 1");
+ is(static_storage_pos, 1, "position is 1");
+
+ p = static_aligned_alloc(3, alignment);
+ is(p, &static_storage_buffer[8], "aligned alloc 3");
+ is(static_storage_pos, 11, "position is changed to aligned pos + size");
+
+ p = static_alloc(2);
+ is(p, &static_storage_buffer[11], "alloc 2");
+ is(static_storage_pos, 13, "position is changed to + size, "\
+ "no alignment");
+
+ p = static_aligned_reserve(53, alignment);
+ is(p, &static_storage_buffer[16], "aligned reserve 53");
+ is(static_storage_pos, 13, "position is not changed");
+
+ p = static_aligned_alloc(53, alignment);
+ is(p, &static_storage_buffer[16], "aligned alloc 53");
+ is(static_storage_pos, 69, "position is changed to aligned pos + size");
+
+ p = static_aligned_alloc(100, alignment);
+ is(p, &static_storage_buffer[72], "aligned alloc 100");
+ is(static_storage_pos, 172, "position is changed to aligned pos + size")
+
+ static_alloc(SMALL_STATIC_SIZE - static_storage_pos - 13);
+ p = static_aligned_alloc(10, alignment);
+ is(p, &static_storage_buffer[0], "aligned alloc 10, when 13 is "\
+ "available, alignment wrapped the buffer");
+ is(static_storage_pos, 10, "position is changed to aligned pos + size");
+
+ static_alloc(SMALL_STATIC_SIZE - static_storage_pos - 13);
+ p = static_aligned_reserve(6, alignment);
+ is(p, static_aligned_reserve(6, alignment),
+ "the same reserve returns the same address");
+
+ check_plan();
+ footer();
+}
+
+int
+main(void)
+{
+ header();
+ plan(2);
+
+ test_unaligned();
+ test_aligned();
+
+ int rc = check_plan();
+ footer();
+ return rc;
+}
diff --git a/test/static.result b/test/static.result
new file mode 100644
index 0000000..604f61c
--- /dev/null
+++ b/test/static.result
@@ -0,0 +1,18 @@
+ *** main ***
+1..15
+ok 1 - allocated 10 from 0
+ok 2 - to 10
+ok 3 - allocated 6144 from 10
+ok 4 - to 6154
+ok 5 - allocated 4096 from 6154
+ok 6 - to 10250
+ok 7 - allocated 2038 from 10250
+ok 8 - to 12288
+ok 9 - allocated 1 from 0
+ok 10 - to 1
+ok 11 - big reserve can be consumed in multiple allocs
+ok 12 - can allocate the entire buffer
+ok 13 - position is updated
+ok 14 - can't allocate more - the memory is static and can't be extended
+ok 15 - position is not changed
+ *** main: done ***
--
2.20.1 (Apple Git-117)
More information about the Tarantool-patches
mailing list