From dcd887eb8326ec195149c7fd6711ddb715c4ad1f Mon Sep 17 00:00:00 2001 From: David Robillard Date: Wed, 15 Sep 2021 23:07:06 -0400 Subject: Add a simple bump pointer allocator --- include/zix/bump_allocator.h | 52 ++++++++++++++ meson.build | 5 +- src/bump_allocator.c | 161 +++++++++++++++++++++++++++++++++++++++++++ test/allocator_test.c | 60 ++++++++++++++++ test/ring_test.c | 1 - 5 files changed, 276 insertions(+), 3 deletions(-) create mode 100644 include/zix/bump_allocator.h create mode 100644 src/bump_allocator.c diff --git a/include/zix/bump_allocator.h b/include/zix/bump_allocator.h new file mode 100644 index 0000000..712ea46 --- /dev/null +++ b/include/zix/bump_allocator.h @@ -0,0 +1,52 @@ +// Copyright 2021 David Robillard +// SPDX-License-Identifier: ISC + +#ifndef ZIX_BUMP_ALLOCATOR_H +#define ZIX_BUMP_ALLOCATOR_H + +#include "zix/allocator.h" +#include "zix/attributes.h" + +#include + +/** + A simple bump-pointer allocator that never frees. + + This is about the simplest possible allocator that is useful in practice. + It uses a user-provided memory buffer with a fixed size, and allocates by + simply "bumping" the top offset like a stack. This approach is simple, + extremely fast, and hard real-time safe, but at the cost of being limited to + narrow use cases since there is (almost) no support for deallocation. + + Using this allocator requires knowing up-front the total amount of memory + that will be allocated (without reuse). Typically this makes sense in short + scopes like a function call. + + This allocator adheres to standard C semantics as much as possible, but is + much more restrictive. Specifically: + + - All allocations are aligned to sizeof(uintmax_t). + + - Both free() and realloc() only work on the most recently allocated + pointer, essentially serving as a cheap pop and pop-push, respectively. + + - Calling free() means that realloc() will fail and free() will do nothing + until the next allocation. In other words, free() can not be used twice + in a row. + + - There is no relocation: realloc() always returns either the input pointer, + or null. +*/ +typedef struct { + ZixAllocator base; ///< Base allocator instance + void* ZIX_NONNULL buffer; ///< User-owned memory buffer + size_t last; ///< Last allocation offset in bytes + size_t top; ///< Stack top/end offset in bytes + size_t capacity; ///< Size of buffer in bytes (the maximum top) +} ZixBumpAllocator; + +ZIX_API +ZixBumpAllocator +zix_bump_allocator(size_t capacity, void* ZIX_NONNULL buffer); + +#endif // ZIX_BUMP_ALLOCATOR_H diff --git a/meson.build b/meson.build index d7ba9d0..45009c4 100644 --- a/meson.build +++ b/meson.build @@ -66,7 +66,7 @@ if get_option('strict') '-Wformat-signedness', '-Wformat-truncation=2', '-Wformat=2', - '-Wframe-larger-than=1024', + '-Wframe-larger-than=2048', '-Wimplicit-fallthrough=2', '-Winit-self', # '-Winline', @@ -86,7 +86,7 @@ if get_option('strict') '-Wshift-overflow=2', '-Wsizeof-array-argument', '-Wstack-protector', - '-Wstack-usage=1024', + '-Wstack-usage=2048', '-Wstrict-aliasing=3', # '-Wstrict-overflow=5', '-Wstringop-overflow=3', @@ -184,6 +184,7 @@ sources = [ 'src/allocator.c', 'src/bitset.c', 'src/btree.c', + 'src/bump_allocator.c', 'src/digest.c', 'src/hash.c', 'src/ring.c', diff --git a/src/bump_allocator.c b/src/bump_allocator.c new file mode 100644 index 0000000..d6d1c41 --- /dev/null +++ b/src/bump_allocator.c @@ -0,0 +1,161 @@ +// Copyright 2021 David Robillard +// SPDX-License-Identifier: ISC + +#include "zix/bump_allocator.h" +#include "zix/allocator.h" +#include "zix/attributes.h" + +#include +#include +#include +#include + +static const size_t min_alignment = sizeof(uintmax_t); + +static size_t +round_up_multiple(const size_t number, const size_t factor) +{ + assert(factor); // Factor must be non-zero + assert((factor & (factor - 1)) == 0u); // Factor must be a power of two + + return (number + factor - 1u) & ~(factor - 1u); +} + +ZIX_MALLOC_FUNC +static void* +zix_bump_malloc(ZixAllocator* const allocator, const size_t size) +{ + ZixBumpAllocator* const state = (ZixBumpAllocator*)allocator; + + assert((uintptr_t)((char*)state->buffer + state->top) % min_alignment == 0); + + /* For C malloc(), the result is guaranteed to be aligned for any variable. + What that means is deliberately vague to accommodate diverse platforms, + but sizeof(uintmax_t) is more than enough on all the common ones. */ + + const size_t real_size = round_up_multiple(size, min_alignment); + if (state->top + real_size > state->capacity) { + return NULL; + } + + state->last = state->top; + state->top += real_size; + + return (void*)((char*)state->buffer + state->last); +} + +ZIX_MALLOC_FUNC +static void* +zix_bump_calloc(ZixAllocator* const allocator, + const size_t nmemb, + const size_t size) +{ + const size_t total_size = nmemb * size; + void* const ptr = zix_bump_malloc(allocator, total_size); + if (ptr) { + memset(ptr, 0, total_size); + } + + return ptr; +} + +static void* +zix_bump_realloc(ZixAllocator* const allocator, + void* const ptr, + const size_t size) +{ + ZixBumpAllocator* const state = (ZixBumpAllocator*)allocator; + + if ((char*)ptr != (char*)state->buffer + state->last) { + return NULL; + } + + const size_t new_top = state->last + size; + if (new_top > state->capacity) { + return NULL; + } + + state->top = new_top; + return ptr; +} + +static void +zix_bump_free(ZixAllocator* const allocator, void* const ptr) +{ + ZixBumpAllocator* const state = (ZixBumpAllocator*)allocator; + + if (ptr == (char*)state->buffer + state->last) { + state->top = state->last; // Reclaim the space of the last allocation + } +} + +ZIX_MALLOC_FUNC +static void* +zix_bump_aligned_alloc(ZixAllocator* const allocator, + const size_t alignment, + const size_t size) +{ + ZixBumpAllocator* const state = (ZixBumpAllocator*)allocator; + const size_t old_last = state->last; + const size_t old_top = state->top; + + assert(alignment >= min_alignment); + assert(size % alignment == 0u); + + /* First, calculate how much we need to offset the top to achieve this + alignment. Note that it's not the offset that needs to be aligned (since + the buffer may not be), but the final address, so we do the calculation + with "global" addresses and calculate the offset from that. */ + + const char* top_ptr = (char*)state->buffer + state->top; + const uintptr_t top_addr = (uintptr_t)top_ptr; + const uintptr_t aligned_top_addr = round_up_multiple(top_addr, alignment); + const uintptr_t offset = aligned_top_addr - top_addr; + if (state->top + offset > state->capacity) { + return NULL; + } + + /* Then, adjust the top to be aligned and try to allocate. If that fails, + reset everything to how it was before this call. */ + + state->top += offset; + + void* const ptr = zix_bump_malloc(allocator, size); + if (!ptr) { + state->last = old_last; + state->top = old_top; + return NULL; + } + + return ptr; +} + +static void +zix_bump_aligned_free(ZixAllocator* const allocator, void* const ptr) +{ + zix_bump_free(allocator, ptr); +} + +ZIX_CONST_FUNC +ZixBumpAllocator +zix_bump_allocator(const size_t capacity, void* buffer) +{ + const size_t aligned_top = (uintptr_t)buffer % min_alignment; + + ZixBumpAllocator bump_allocator = { + { + zix_bump_malloc, + zix_bump_calloc, + zix_bump_realloc, + zix_bump_free, + zix_bump_aligned_alloc, + zix_bump_aligned_free, + }, + buffer, + aligned_top, + aligned_top, + capacity, + }; + + return bump_allocator; +} diff --git a/test/allocator_test.c b/test/allocator_test.c index 5275ce8..b4aec16 100644 --- a/test/allocator_test.c +++ b/test/allocator_test.c @@ -4,6 +4,7 @@ #undef NDEBUG #include "zix/allocator.h" +#include "zix/bump_allocator.h" #include #include @@ -53,9 +54,68 @@ test_allocator(void) zix_free(allocator, malloced); } +static void +test_bump_allocator(void) +{ + char buffer[1024] = {0}; + ZixBumpAllocator allocator = zix_bump_allocator(sizeof(buffer), buffer); + + assert(!zix_malloc(&allocator.base, 1025)); + + char* const malloced = (char*)zix_malloc(&allocator.base, 3); + assert(malloced >= buffer); + assert(malloced <= buffer + sizeof(buffer)); + assert((uintptr_t)malloced % sizeof(uintmax_t) == 0u); + + assert(!zix_calloc(&allocator.base, 1017, 1)); + + char* const calloced = (char*)zix_calloc(&allocator.base, 4, 1); + assert(calloced > malloced); + assert(calloced <= buffer + sizeof(buffer)); + assert((uintptr_t)calloced % sizeof(uintmax_t) == 0u); + assert(!calloced[0]); + assert(!calloced[1]); + assert(!calloced[2]); + assert(!calloced[3]); + + char* const realloced = (char*)zix_realloc(&allocator.base, calloced, 8); + assert(realloced == calloced); + + assert(!zix_realloc(&allocator.base, malloced, 8)); // Not the top + assert(!zix_realloc(&allocator.base, realloced, 4089)); // No space + + zix_free(&allocator.base, realloced); + + char* const reclaimed = (char*)zix_malloc(&allocator.base, 512); + assert(reclaimed); + assert(reclaimed == realloced); + + assert(!zix_aligned_alloc(&allocator.base, sizeof(uintmax_t), 1024)); + assert(!zix_aligned_alloc(&allocator.base, 1024, 1024)); + assert(!zix_aligned_alloc(&allocator.base, 2048, 2048)); + assert(!zix_aligned_alloc(&allocator.base, 4096, 4096)); + assert(!zix_aligned_alloc(&allocator.base, 8192, 8192)); + assert(!zix_aligned_alloc(&allocator.base, 4096, 4096)); + assert(!zix_aligned_alloc(&allocator.base, 2048, 2048)); + assert(!zix_aligned_alloc(&allocator.base, 1024, 1024)); + assert(!zix_aligned_alloc(&allocator.base, 512, 512)); + + char* const aligned = (char*)zix_aligned_alloc(&allocator.base, 128, 128); + assert(aligned); + assert(aligned >= reclaimed); + assert(aligned <= buffer + sizeof(buffer)); + assert((uintptr_t)aligned % 128 == 0u); + + zix_aligned_free(&allocator.base, aligned); + zix_free(&allocator.base, reclaimed); // Correct, but a noop + zix_free(&allocator.base, malloced); // Correct, but a noop +} + int main(void) { test_allocator(); + test_bump_allocator(); + return 0; } diff --git a/test/ring_test.c b/test/ring_test.c index ba2a4d1..2b87efa 100644 --- a/test/ring_test.c +++ b/test/ring_test.c @@ -5,7 +5,6 @@ #include "failing_allocator.h" -#include "zix/allocator.h" #include "zix/attributes.h" #include "zix/ring.h" #include "zix/thread.h" -- cgit v1.2.1