Add a simple bump pointer allocator

5 files changed, 276 insertions, 3 deletions

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 <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#ifndef ZIX_BUMP_ALLOCATOR_H
+#define ZIX_BUMP_ALLOCATOR_H
+
+#include "zix/allocator.h"
+#include "zix/attributes.h"
+
+#include <stddef.h>
+
+/**
+   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 <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#include "zix/bump_allocator.h"
+#include "zix/allocator.h"
+#include "zix/attributes.h"
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+
+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 <assert.h>
 #include <stdint.h>
@@ -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"