From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTP id 701AE2B99F for ; Mon, 13 May 2019 17:50:08 -0400 (EDT) Received: from turing.freelists.org ([127.0.0.1]) by localhost (turing.freelists.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id scUR1Yy3ZT54 for ; Mon, 13 May 2019 17:50:08 -0400 (EDT) Received: from smtp48.i.mail.ru (smtp48.i.mail.ru [94.100.177.108]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTPS id 962732B99D for ; Mon, 13 May 2019 17:50:07 -0400 (EDT) From: Vladislav Shpilevoy Subject: [tarantool-patches] [PATCH v2 small 1/1] small: introduce static allocator Date: Tue, 14 May 2019 00:49:59 +0300 Message-Id: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: tarantool-patches-bounce@freelists.org Errors-to: tarantool-patches-bounce@freelists.org Reply-To: tarantool-patches@freelists.org List-Help: List-Unsubscribe: List-software: Ecartis version 1.0.0 List-Id: tarantool-patches List-Subscribe: List-Owner: List-post: List-Archive: To: tarantool-patches@freelists.org Cc: kostja@tarantool.org 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 ``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 + * 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 ``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 + * 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 +#include +#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 ``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 + * 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)