toys

toys.git
git clone git://git.lenczewski.org/toys.git
Log | Files | Refs | README | LICENSE
commit 056ff846e2933ffea4378fad0e81796008af37ba
parent a5594b59cb12558282cba3beb74eba97fe168969
Author: MikoĊ‚aj Lenczewski <mblenczewski@gmail.com>
Date:   Sat,  4 Oct 2025 23:14:17 +0100

Added initial allocator implementations

Diffstat:

Aallocators.c | 176+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


Aallocators.h | 247+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


Darena.c | 88-------------------------------------------------------------------------------


Darena.h | 68--------------------------------------------------------------------


4 files changed, 423 insertions(+), 156 deletions(-)

diff --git a/allocators.c b/allocators.c
@@ -0,0 +1,176 @@
+#define HEADER_IMPL
+#include "allocators.h"
+
+#include <assert.h>
+#include <stdio.h>
+
+struct mystruct {
+	int a, b, c;
+};
+
+struct alignas(64) mystruct2 {
+	char buf[17];
+};
+
+static void
+test_arena(struct arena_allocator *allocator);
+
+static void
+test_stack(struct stack_allocator *allocator);
+
+static void
+test_pool(struct pool_allocator *allocator);
+
+static void
+test_heap(struct heap_allocator *allocator);
+
+static void
+test_buddy(struct buddy_allocator *allocator);
+
+int
+main(void)
+{
+	printf("IS_POW2(1): %d, IS_POW2(2): %d, IS_POW2(3): %d\n",
+			IS_POW2(1), IS_POW2(2), IS_POW2(3));
+
+	printf("IS_ALIGNED(2, 2): %d, IS_ALIGNED(1, 2): %d\n",
+			IS_ALIGNED(2, 2), IS_ALIGNED(1, 2));
+
+	printf("ALIGN_PREV(2, 2): %d, ALIGN_PREV(1, 2): %d\n",
+			ALIGN_PREV(2, 2), ALIGN_PREV(1, 2));
+
+	printf("ALIGN_NEXT(2, 2): %d, ALIGN_NEXT(1, 2): %d\n",
+			ALIGN_NEXT(2, 2), ALIGN_NEXT(1, 2));
+
+	char buf[1024];
+
+	struct arena_allocator arena = { .ptr = buf, .cap = sizeof buf, .len = 0, };
+	test_arena(&arena);
+
+	struct stack_allocator stack = { .ptr = buf, .cap = sizeof buf, .len = 0, };
+	test_stack(&stack);
+
+	struct pool_allocator pool = { .ptr = buf, .cap = sizeof buf, };
+	pool_init(&pool, pool.cap / 16);
+	test_pool(&pool);
+
+	struct heap_allocator heap = { .ptr = buf, .cap = sizeof buf, };
+	test_heap(&heap);
+
+	struct buddy_allocator buddy = { .ptr = buf, .cap = sizeof buf, };
+	test_buddy(&buddy);
+
+	return 0;
+}
+
+static void
+test_arena(struct arena_allocator *allocator)
+{
+	printf("arena: buf: %p, cap: %zu, len: %zu\n",
+			allocator->ptr, allocator->cap, allocator->len);
+
+	struct mystruct *foo = arena_alloc(allocator, sizeof *foo, alignof(struct mystruct));
+	assert(foo);
+
+	printf("foo: %p, sizeof foo: %zu, alignof foo: %zu\n",
+			foo, sizeof *foo, alignof(struct mystruct));
+
+	foo->a = foo->b = foo->c = 42;
+
+	struct mystruct *bar = ARENA_ALLOC_SIZED(allocator, struct mystruct);
+	assert(bar);
+
+	printf("bar: %p, sizeof bar: %zu, alignof bar: %zu\n",
+			bar, sizeof *bar, alignof(struct mystruct));
+
+	bar->a = bar->b = bar->c = 69;
+
+	assert(foo != bar);
+
+	printf("arena_reset() ...\n");
+
+	printf("\tbefore reset: foo->a = %d\n", foo->a);
+	arena_reset(allocator);
+	printf("\tafter reset: foo->a = %d\n", foo->a);
+
+	struct mystruct *baz = ARENA_ALLOC_SIZED(allocator, struct mystruct);
+	assert(baz);
+	assert(foo == baz);
+
+	printf("\tafter reset: baz: %p, baz->a = %d, baz == foo: %d\n",
+			baz, baz->a, baz == foo);
+
+	// struct mystruct2 *fee = ARENA_ALLOC_ARRAY(allocator, struct mystruct2, 2);
+	struct mystruct2 *fee = arena_alloc(allocator, sizeof *fee * 2, alignof(struct mystruct2));
+	assert(fee);
+
+	printf("fee: %p, sizeof fee: %zu, alignof fee: %zu\n",
+			fee, sizeof *fee, alignof(struct mystruct2));
+
+	printf("fee[0]: %p, fee[0] is aligned: %d, fee[1]: %p, fee[1] is aligned: %d\n",
+			&fee[0], IS_ALIGNED((uintptr_t) &fee[0], alignof(struct mystruct2)),
+			&fee[1], IS_ALIGNED((uintptr_t) &fee[1], alignof(struct mystruct2)));
+
+	assert(IS_ALIGNED((uintptr_t) &fee[0], 64));
+	assert(IS_ALIGNED((uintptr_t) &fee[1], 64));
+
+	char *mybuf = arena_alloc(allocator, 128, 256);
+	assert(mybuf);
+
+	printf("mybuf: %p, sizeof mybuf: 128, alignof mybuf: 256\n", mybuf);
+
+	assert(IS_ALIGNED((uintptr_t) mybuf, 256));
+}
+
+static void
+test_stack(struct stack_allocator *allocator)
+{
+	printf("stack: buf: %p, cap: %zu, len: %zu\n",
+			allocator->ptr, allocator->cap, allocator->len);
+
+	struct mystruct *foo = stack_alloc(allocator, sizeof *foo, alignof(struct mystruct));
+	assert(foo);
+
+	printf("foo: %p, sizeof foo: %zu, alignof foo: %zu\n",
+			foo, sizeof *foo, alignof(struct mystruct));
+	printf("foo padding: %zu\n", stack_alloc_padding(foo));
+
+	stack_free(allocator, foo);
+
+	void *bar = stack_alloc(allocator, 64, 8);
+	printf("bar: %p, sizeof bar: %d, alignof bar: %d\n",
+			bar, 64, 8);
+	printf("bar padding: %zu\n", stack_alloc_padding(bar));
+
+	void *baz = stack_alloc(allocator, 8, 8);
+	printf("baz: %p, sizeof baz: %d, alignof baz: %d\n",
+			baz, 8, 8);
+	printf("baz padding: %zu\n", stack_alloc_padding(baz));
+
+	stack_free(allocator, bar);
+	assert(allocator->len == 0);
+
+	// WARN: freeing baz here is unsupported, and WILL cause memory leakage
+	// stack_free(allocator, baz);
+}
+
+static void
+test_pool(struct pool_allocator *allocator)
+{
+	printf("pool: buf: %p, cap: %zu, block_size: %zu\n",
+			allocator->ptr, allocator->cap, allocator->block_size);
+}
+
+static void
+test_heap(struct heap_allocator *allocator)
+{
+	printf("heap: buf: %p, cap: %zu\n",
+			allocator->ptr, allocator->cap);
+}
+
+static void
+test_buddy(struct buddy_allocator *allocator)
+{
+	printf("buddy: buf: %p, cap: %zu\n",
+			allocator->ptr, allocator->cap);
+}
diff --git a/allocators.h b/allocators.h
@@ -0,0 +1,247 @@
+#ifndef ALLOCATORS_H
+#define ALLOCATORS_H
+
+#include <stdalign.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include "assert.h"
+
+/* helper macros to allow us to use bitwise tricks to quickly and efficiently
+ * calculate aligned addresses and sizes.
+ */
+#define IS_POW2(v) (((v) & ((v) - 1)) == 0)
+#define IS_ALIGNED(v, align) (((v) & ((align) - 1)) == 0)
+#define ALIGN_PREV(v, align) ((v) & ~((align) - 1))
+#define ALIGN_NEXT(v, align) ALIGN_PREV(((v) + ((align) - 1)), (align))
+
+/* arena allocator
+ * ---------------------------------------------------------------------------
+ *  Linear/bump allocator. Supports allocations of arbitray size and with
+ *  power-of-two alignments. Does not support freeing individual allocations.
+ */
+struct arena_allocator {
+	void *ptr;
+	size_t cap, len;
+};
+
+inline void
+arena_reset(struct arena_allocator *allocator)
+{
+	allocator->len = 0;
+}
+
+inline void *
+arena_alloc(struct arena_allocator *allocator, size_t size, size_t align)
+{
+	ASSERT(size);
+	ASSERT(IS_POW2(align));
+
+	uintptr_t base = (uintptr_t) allocator->ptr;
+	uintptr_t end = base + allocator->cap;
+
+	uintptr_t aligned_ptr = ALIGN_NEXT(base + allocator->len, align);
+	if (end < aligned_ptr + size)
+		return NULL;
+
+	allocator->len = (aligned_ptr + size) - base;
+
+	return (void *) aligned_ptr;
+}
+
+#define ARENA_ALLOC_ARRAY(arena, T, n) \
+	((T *) arena_alloc((arena), sizeof(T) * (n), alignof(T)))
+
+#define ARENA_ALLOC_SIZED(arena, T) \
+	ARENA_ALLOC_ARRAY((arena), T, 1)
+
+/* stack allocator
+ * ---------------------------------------------------------------------------
+ *  A LIFO allocator. Supports allocations of arbitrary size but with limited
+ *  power-of-two alignments. Supports freeing individual allocations, with
+ *  frees of older allocations freeing more recent allocations. Frees of newer
+ *  allocations are assumed never to happen after frees of the then-older
+ *  allocations (i.e. no alloc1-alloc2-free1-alloc3-free2-...).
+ */
+
+struct stack_allocator_frameinfo {
+	uint8_t padding;
+};
+
+#define STACK_ALLOCATOR_MAX_ALIGNMENT \
+	(2 << ((8 * sizeof(struct stack_allocator_frameinfo)) - 1))
+
+struct stack_allocator {
+	void *ptr;
+	size_t cap, len;
+};
+
+inline void
+stack_reset(struct stack_allocator *allocator)
+{
+	allocator->len = 0;
+}
+
+inline void *
+stack_alloc(struct stack_allocator *allocator, size_t size, size_t align)
+{
+	ASSERT(size);
+	ASSERT(IS_POW2(align));
+	ASSERT(align < STACK_ALLOCATOR_MAX_ALIGNMENT);
+
+	uintptr_t base = (uintptr_t) allocator->ptr;
+	uintptr_t end = base + allocator->cap;
+
+	struct stack_allocator_frameinfo *info;
+	uintptr_t unaligned_ptr = base + allocator->len;
+	uintptr_t aligned_ptr = ALIGN_NEXT(unaligned_ptr + sizeof *info, align);
+	if (end < aligned_ptr + size)
+		return NULL;
+
+	info = (void *) (aligned_ptr - sizeof *info);
+	info->padding = aligned_ptr - unaligned_ptr;
+
+	allocator->len = (aligned_ptr + size) - base;
+
+	return (void *) aligned_ptr;
+}
+
+inline size_t
+stack_alloc_padding(void *ptr)
+{
+	struct stack_allocator_frameinfo *info = (void *) (((uintptr_t) ptr) - sizeof *info);
+	return info->padding;
+}
+
+inline void
+stack_free(struct stack_allocator *allocator, void *res)
+{
+	uintptr_t base = (uintptr_t) allocator->ptr, ptr = (uintptr_t) res;
+	allocator->len = (ptr - stack_alloc_padding(res)) - base;
+}
+
+/* pool allocator
+ * ---------------------------------------------------------------------------
+ *  A block-based allocator. Supports allocating out of a pool of memory blocks,
+ *  all of a fixed power-of-two size and with an alignment dependent on the
+ *  alignment of the main memory buffer, and the size of each block. Supports
+ *  freeing individual allocations (i.e. returning blocks to the pool).
+ */
+
+struct pool_allocator_block {
+	struct pool_allocator_block *next;
+};
+
+struct pool_allocator {
+	void *ptr;
+	size_t cap;
+
+	size_t block_size;
+	struct pool_allocator_block freelist;
+};
+
+inline void
+pool_init(struct pool_allocator *allocator, size_t block_size)
+{
+	ASSERT(IS_POW2(block_size));
+	ASSERT(sizeof(struct pool_allocator_block) <= block_size);
+
+	allocator->block_size = block_size;
+
+	uintptr_t base = (uintptr_t) allocator->ptr;
+	struct pool_allocator_block **tail = &allocator->freelist.next;
+	for (size_t off = 0; off < allocator->cap; off += block_size) {
+		struct pool_allocator_block *block = (void *) (base + off);
+
+		*tail = block;
+		tail = &block->next;
+	}
+	*tail = NULL;
+}
+
+inline void *
+pool_alloc(struct pool_allocator *allocator, size_t size, size_t align)
+{
+	ASSERT(size);
+	ASSERT(IS_POW2(align));
+
+	if (allocator->block_size < size)
+		return NULL;
+
+	struct pool_allocator_block *block = allocator->freelist.next;
+	if (!block)
+		return NULL;
+
+	if (!IS_ALIGNED((uintptr_t) block, align))
+		return NULL;
+
+	allocator->freelist.next = block->next;
+
+	return block;
+}
+
+inline void
+pool_free(struct pool_allocator *allocator, void *res)
+{
+	struct pool_allocator_block *block = res;
+
+	block->next = allocator->freelist.next;
+	allocator->freelist.next = block;
+}
+
+/* heap allocator
+ * ---------------------------------------------------------------------------
+ *  A general-purpose allocator. Supports allocations of arbitrary size, and
+ *  with power-of-two alignments. Supports unordered frees. Uses a red-black
+ *  tree to get best-fit. Suffers from internal fragmentation.
+ */
+
+struct heap_allocator {
+	void *ptr;
+	size_t cap;
+};
+
+/* buddy allocator
+ * ---------------------------------------------------------------------------
+ *  A block-based allocator. Supports allocating out of a tree of memory blocks,
+ *  each being sized as an order of two multiple of a base block size. Supports
+ *  coalescing of blocks on free to minimise internal fragmentation.
+ */
+
+struct buddy_allocator {
+	void *ptr;
+	size_t cap;
+};
+
+#endif /* ALLOCATORS_H */
+
+#ifdef HEADER_IMPL
+
+extern inline void
+arena_reset(struct arena_allocator *allocator);
+
+extern inline void *
+arena_alloc(struct arena_allocator *allocator, size_t size, size_t align);
+
+extern inline void
+stack_reset(struct stack_allocator *allocator);
+
+extern inline void *
+stack_alloc(struct stack_allocator *allocator, size_t size, size_t align);
+
+extern inline size_t
+stack_alloc_padding(void *res);
+
+extern inline void
+stack_free(struct stack_allocator *allocator, void *res);
+
+extern inline void
+pool_init(struct pool_allocator *allocator, size_t block_size);
+
+extern inline void *
+pool_alloc(struct pool_allocator *allocator, size_t size, size_t align);
+
+extern inline void
+pool_free(struct pool_allocator *allocator, void *res);
+
+#endif /* HEADER_IMPL */
diff --git a/arena.c b/arena.c
@@ -1,88 +0,0 @@
-#define HEADER_IMPL
-#include "arena.h"
-
-#include <stdio.h>
-
-struct mystruct {
-	int a, b, c;
-};
-
-struct alignas(64) mystruct2 {
-	char buf[17];
-};
-
-int
-main(void)
-{
-	printf("IS_POW2(1): %d, IS_POW2(2): %d, IS_POW2(3): %d\n",
-			IS_POW2(1), IS_POW2(2), IS_POW2(3));
-
-	printf("IS_ALIGNED(2, 2): %d, IS_ALIGNED(1, 2): %d\n",
-			IS_ALIGNED(2, 2), IS_ALIGNED(1, 2));
-
-	printf("ALIGN_PREV(2, 2): %d, ALIGN_PREV(1, 2): %d\n",
-			ALIGN_PREV(2, 2), ALIGN_PREV(1, 2));
-
-	printf("ALIGN_NEXT(2, 2): %d, ALIGN_NEXT(1, 2): %d\n",
-			ALIGN_NEXT(2, 2), ALIGN_NEXT(1, 2));
-
-	char buf[1024];
-	struct arena arena = { .ptr = buf, .cap = sizeof buf, .len = 0, };
-
-	printf("arena: buf: %p, cap: %zu, len: %zu\n",
-			arena.ptr, arena.cap, arena.len);
-
-	struct mystruct *foo = arena_alloc(&arena, sizeof *foo, alignof(struct mystruct));
-	assert(foo);
-
-	printf("foo: %p, sizeof foo: %zu, alignof foo: %zu\n",
-			foo, sizeof *foo, alignof(struct mystruct));
-
-	foo->a = foo->b = foo->c = 42;
-
-	struct mystruct *bar = ARENA_ALLOC_SIZED(&arena, struct mystruct);
-	assert(bar);
-
-	printf("bar: %p, sizeof bar: %zu, alignof bar: %zu\n",
-			bar, sizeof *bar, alignof(struct mystruct));
-
-	bar->a = bar->b = bar->c = 69;
-
-	assert(foo != bar);
-
-	printf("arena_reset() ...\n");
-
-	printf("\tbefore reset: foo->a = %d\n", foo->a);
-	arena_reset(&arena);
-	printf("\tafter reset: foo->a = %d\n", foo->a);
-
-	struct mystruct *baz = ARENA_ALLOC_SIZED(&arena, struct mystruct);
-	assert(baz);
-	assert(foo == baz);
-
-	printf("\tafter reset: baz: %p, baz->a = %d, baz == foo: %d\n",
-			baz, baz->a, baz == foo);
-
-	// struct mystruct2 *fee = ARENA_ALLOC_ARRAY(&arena, struct mystruct2, 2);
-	struct mystruct2 *fee = arena_alloc(&arena, sizeof *fee * 2, alignof(struct mystruct2));
-	assert(fee);
-
-	printf("fee: %p, sizeof fee: %zu, alignof fee: %zu\n",
-			fee, sizeof *fee, alignof(struct mystruct2));
-
-	printf("fee[0]: %p, fee[0] is aligned: %d, fee[1]: %p, fee[1] is aligned: %d\n",
-			&fee[0], IS_ALIGNED((uintptr_t) &fee[0], alignof(struct mystruct2)),
-			&fee[1], IS_ALIGNED((uintptr_t) &fee[1], alignof(struct mystruct2)));
-
-	assert(IS_ALIGNED((uintptr_t) &fee[0], 64));
-	assert(IS_ALIGNED((uintptr_t) &fee[1], 64));
-
-	char *mybuf = arena_alloc(&arena, 128, 256);
-	assert(mybuf);
-
-	printf("mybuf: %p, sizeof mybuf: 128, alignof mybuf: 256\n", mybuf);
-
-	assert(IS_ALIGNED((uintptr_t) mybuf, 256));
-
-	return 0;
-}
diff --git a/arena.h b/arena.h
@@ -1,68 +0,0 @@
-#ifndef ARENA_H
-#define ARENA_H
-
-#include <assert.h>
-#include <stdalign.h>
-#include <stddef.h>
-#include <stdint.h>
-
-/* helper macros to allow us to use bitwise tricks to quickly and efficiently
- * calculate aligned addresses and sizes.
- */
-#define IS_POW2(v) (((v) & ((v) - 1)) == 0)
-#define IS_ALIGNED(v, align) (((v) & ((align) - 1)) == 0)
-#define ALIGN_PREV(v, align) ((v) & ~((align) - 1))
-#define ALIGN_NEXT(v, align) ALIGN_PREV(((v) + ((align) - 1)), (align))
-
-struct arena {
-	void *ptr;
-	uint64_t cap, len;
-};
-
-/* arenas dont support freeing individual elements, instead allowing only to
- * free all elements at once.
- */
-inline void
-arena_reset(struct arena *arena)
-{
-	arena->len = 0;
-}
-
-/* we might want to allocate arbitrary buffers out of an arena, with any given
- * alignment (as long as it is a power of two).
- */
-inline void *
-arena_alloc(struct arena *arena, size_t size, size_t align)
-{
-	assert(size);
-	assert(align);
-	assert(IS_POW2(align));
-
-	uintptr_t aligned_ptr = ALIGN_NEXT((uintptr_t) arena->ptr + arena->len, align);
-	if (aligned_ptr + size > (uintptr_t) arena->ptr + arena->cap)
-		return NULL;
-
-	arena->len = (aligned_ptr - (uintptr_t) arena->ptr) + size;
-
-	return (void *) aligned_ptr;
-}
-
-/* helper macros to make allocation more concise.
- */
-#define ARENA_ALLOC_ARRAY(arena, T, n) \
-	((T *) arena_alloc((arena), sizeof(T) * (n), alignof(T)))
-
-#define ARENA_ALLOC_SIZED(arena, T) \
-	ARENA_ALLOC_ARRAY((arena), T, 1)
-
-#endif /* ARENA_H */
-
-#ifdef HEADER_IMPL
-
-extern inline void
-arena_reset(struct arena *arena);
-
-extern inline void *
-arena_alloc(struct arena *arena, size_t size, size_t align);
-
-#endif /* HEADER_IMPL */