[tarantool-patches] [PATCH v2 small 1/1] small: introduce static allocator

[tarantool-patches] [PATCH v2 small 1/1] small: introduce static allocator

[Vladislav Shpilevoy]

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  |  43 +++++++++++++
 6 files changed, 364 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..e7d4843
--- /dev/null
+++ b/test/static.result
@@ -0,0 +1,43 @@
+	*** main ***
+1..2
+	*** test_unaligned ***
+    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
+ok 1 - subtests
+	*** test_unaligned: done ***
+	*** test_aligned ***
+    1..17
+    ok 1 - aligned reserve 0
+    ok 2 - position is not changed
+    ok 3 - alloc 1
+    ok 4 - position is 1
+    ok 5 - aligned alloc 3
+    ok 6 - position is changed to aligned pos + size
+    ok 7 - alloc 2
+    ok 8 - position is changed to + size, no alignment
+    ok 9 - aligned reserve 53
+    ok 10 - position is not changed
+    ok 11 - aligned alloc 53
+    ok 12 - position is changed to aligned pos + size
+    ok 13 - aligned alloc 100
+    ok 14 - position is changed to aligned pos + size
+    ok 15 - aligned alloc 10, when 13 is available, alignment wrapped the buffer
+    ok 16 - position is changed to aligned pos + size
+    ok 17 - the same reserve returns the same address
+ok 2 - subtests
+	*** test_aligned: done ***
+	*** main: done ***
-- 
2.20.1 (Apple Git-117)

[tarantool-patches] Re: [PATCH v2 small 1/1] small: introduce static allocator

[Konstantin Osipov]

* Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [19/05/14 00:58]:

OK to push.

> 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

-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32

[tarantool-patches] Re: [PATCH v2 small 1/1] small: introduce static allocator

[Vladislav Shpilevoy]

Pushed into the master.

On 14/05/2019 01:11, Konstantin Osipov wrote:
> * Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [19/05/14 00:58]:
> 
> OK to push.
> 
>> 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
>