commit 457012a136f9a1c00d34fa74cf0ecfa6cf5d8e22
parent 0783fbf889025baa4c38a739cf889ec78fa49fbd
Author: MikoĊaj Lenczewski <mblenczewski@gmail.com>
Date: Sun, 12 Oct 2025 21:27:49 +0100
Added freelist allocator
Diffstat:
| M | allocators.c | | | 56 | ++++++++++++++++++++++++++++++++++++++++++++++++++------ |
| M | allocators.h | | | 198 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------- |
2 files changed, 226 insertions(+), 28 deletions(-)
diff --git a/allocators.c b/allocators.c
@@ -22,7 +22,7 @@ static void
test_pool(struct pool_allocator *allocator);
static void
-test_heap(struct heap_allocator *allocator);
+test_freelist(struct freelist_allocator *allocator);
static void
test_buddy(struct buddy_allocator *allocator);
@@ -51,11 +51,12 @@ main(void)
test_stack(&stack);
struct pool_allocator pool = { .ptr = buf, .cap = sizeof buf, };
- pool_init(&pool, pool.cap / 16);
+ pool_allocator_init(&pool, pool.cap / 16);
test_pool(&pool);
- struct heap_allocator heap = { .ptr = buf, .cap = sizeof buf, };
- test_heap(&heap);
+ struct freelist_allocator heap_freelist = { .ptr = buf, .cap = sizeof buf, };
+ freelist_allocator_init(&heap_freelist);
+ test_freelist(&heap_freelist);
struct buddy_allocator buddy = { .ptr = buf, .cap = sizeof buf, };
test_buddy(&buddy);
@@ -161,11 +162,54 @@ test_pool(struct pool_allocator *allocator)
allocator->ptr, allocator->cap, allocator->block_size);
}
+static inline void
+freelist_print(struct freelist_allocator *allocator)
+{
+ printf("freelist_allocator.freelist:\n");
+
+ struct freelist_allocator_block *freelist = &allocator->freelist, *block;
+ for (block = freelist->next; block != freelist; block = block->next) {
+ printf("\t{ %p, prev: %p, next: %p, size: %zu }\n",
+ block, block->prev, block->next, block->size);
+ }
+}
+
static void
-test_heap(struct heap_allocator *allocator)
+test_freelist(struct freelist_allocator *allocator)
{
- printf("heap: buf: %p, cap: %zu\n",
+ printf("heap freelist: buf: %p, cap: %zu\n",
allocator->ptr, allocator->cap);
+
+ struct mystruct *foo = freelist_alloc(allocator, sizeof *foo, alignof(struct mystruct));
+ assert(foo);
+
+ freelist_print(allocator);
+
+ freelist_free(allocator, foo);
+ assert(allocator->freelist.next->size == allocator->cap);
+
+ freelist_print(allocator);
+
+ struct mystruct *bar = freelist_alloc(allocator, sizeof *bar, alignof(struct mystruct));
+ freelist_print(allocator);
+ struct mystruct *baz = freelist_alloc(allocator, sizeof *baz, alignof(struct mystruct));
+ freelist_print(allocator);
+ struct mystruct *qux = freelist_alloc(allocator, sizeof *qux, alignof(struct mystruct));
+ freelist_print(allocator);
+
+ freelist_free(allocator, baz);
+ freelist_print(allocator);
+ freelist_free(allocator, qux);
+ freelist_print(allocator);
+
+ struct mystruct *fee = freelist_alloc(allocator, sizeof *fee, alignof(struct mystruct));
+ assert(fee == baz);
+
+ freelist_free(allocator, bar);
+ freelist_free(allocator, fee);
+
+ assert(allocator->freelist.next->size == allocator->cap);
+ freelist_print(allocator);
}
static void
diff --git a/allocators.h b/allocators.h
@@ -64,12 +64,12 @@ arena_alloc(struct arena_allocator *allocator, size_t size, size_t align)
* allocations (i.e. no alloc1-alloc2-free1-alloc3-free2-...).
*/
-struct stack_allocator_frameinfo {
+struct stack_allocator_header {
uint8_t padding;
};
#define STACK_ALLOCATOR_MAX_ALIGNMENT \
- (2 << ((8 * sizeof(struct stack_allocator_frameinfo)) - 1))
+ (2 << ((8 * sizeof(struct stack_allocator_header)) - 1))
struct stack_allocator {
void *ptr;
@@ -92,14 +92,14 @@ stack_alloc(struct stack_allocator *allocator, size_t size, size_t align)
uintptr_t base = (uintptr_t) allocator->ptr;
uintptr_t end = base + allocator->cap;
- struct stack_allocator_frameinfo *info;
+ struct stack_allocator_header *hdr;
uintptr_t unaligned_ptr = base + allocator->len;
- uintptr_t aligned_ptr = ALIGN_NEXT(unaligned_ptr + sizeof *info, align);
+ uintptr_t aligned_ptr = ALIGN_NEXT(unaligned_ptr + sizeof *hdr, align);
if (end < aligned_ptr + size)
return NULL;
- info = (void *) (aligned_ptr - sizeof *info);
- info->padding = aligned_ptr - unaligned_ptr;
+ hdr = (void *) (aligned_ptr - sizeof *hdr);
+ hdr->padding = aligned_ptr - unaligned_ptr;
allocator->len = (aligned_ptr + size) - base;
@@ -109,8 +109,8 @@ stack_alloc(struct stack_allocator *allocator, size_t size, size_t align)
inline size_t
stack_alloc_padding(void *ptr)
{
- struct stack_allocator_frameinfo *info = (void *) (((uintptr_t) ptr) - sizeof *info);
- return info->padding;
+ struct stack_allocator_header *hdr = (void *) (((uintptr_t) ptr) - sizeof *hdr);
+ return hdr->padding;
}
inline void
@@ -128,8 +128,8 @@ stack_free(struct stack_allocator *allocator, void *res)
* freeing individual allocations (i.e. returning blocks to the pool).
*/
-struct pool_allocator_block {
- struct pool_allocator_block *next;
+struct pool_allocator_freeblock {
+ struct pool_allocator_freeblock *next;
};
struct pool_allocator {
@@ -137,21 +137,21 @@ struct pool_allocator {
size_t cap;
size_t block_size;
- struct pool_allocator_block freelist;
+ struct pool_allocator_freeblock freelist;
};
inline void
-pool_init(struct pool_allocator *allocator, size_t block_size)
+pool_allocator_init(struct pool_allocator *allocator, size_t block_size)
{
ASSERT(IS_POW2(block_size));
- ASSERT(sizeof(struct pool_allocator_block) <= block_size);
+ ASSERT(sizeof(struct pool_allocator_freeblock) <= block_size);
allocator->block_size = block_size;
uintptr_t base = (uintptr_t) allocator->ptr;
- struct pool_allocator_block **tail = &allocator->freelist.next;
+ struct pool_allocator_freeblock **tail = &allocator->freelist.next;
for (size_t off = 0; off < allocator->cap; off += block_size) {
- struct pool_allocator_block *block = (void *) (base + off);
+ struct pool_allocator_freeblock *block = (void *) (base + off);
*tail = block;
tail = &block->next;
@@ -168,7 +168,7 @@ pool_alloc(struct pool_allocator *allocator, size_t size, size_t align)
if (allocator->block_size < size)
return NULL;
- struct pool_allocator_block *block = allocator->freelist.next;
+ struct pool_allocator_freeblock *block = allocator->freelist.next;
if (!block)
return NULL;
@@ -183,24 +183,161 @@ pool_alloc(struct pool_allocator *allocator, size_t size, size_t align)
inline void
pool_free(struct pool_allocator *allocator, void *res)
{
- struct pool_allocator_block *block = res;
-
+ struct pool_allocator_freeblock *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.
+ * with power-of-two alignments. Supports unordered frees. Suffers from
+ * internal fragmentation. Supports both a freelist implementation, and a
+ * red-black tree implementation.
*/
-struct heap_allocator {
+struct freelist_allocator_header {
+ size_t padding;
+ size_t size;
+};
+
+struct freelist_allocator_block {
+ struct freelist_allocator_block *prev, *next;
+ size_t size;
+};
+
+inline void
+freelist_allocator_freelist_insert(struct freelist_allocator_block *block,
+ struct freelist_allocator_block *prev,
+ struct freelist_allocator_block *next)
+{
+ prev->next = block;
+ block->prev = prev;
+ next->prev = block;
+ block->next = next;
+}
+
+inline void
+freelist_allocator_freelist_remove(struct freelist_allocator_block *block)
+{
+ block->prev->next = block->next;
+ block->next->prev = block->prev;
+}
+
+struct freelist_allocator {
void *ptr;
size_t cap;
+
+ struct freelist_allocator_block freelist;
};
+inline void
+freelist_allocator_init(struct freelist_allocator *allocator)
+{
+ ASSERT(IS_ALIGNED((uintptr_t) allocator->ptr,
+ alignof(struct freelist_allocator_block)));
+
+ allocator->freelist.prev = allocator->freelist.next = &allocator->freelist;
+
+ struct freelist_allocator_block *root = allocator->ptr;
+ root->size = allocator->cap;
+
+ freelist_allocator_freelist_insert(root,
+ allocator->freelist.prev,
+ allocator->freelist.next);
+}
+
+inline void *
+freelist_alloc(struct freelist_allocator *allocator, size_t size, size_t align)
+{
+ ASSERT(size);
+ ASSERT(IS_POW2(align));
+
+ /* ensure that the allocation header can be placed immediately in
+ * front of the main allocation
+ */
+ if (align < alignof(struct freelist_allocator_header))
+ align = alignof(struct freelist_allocator_header);
+
+ struct freelist_allocator_header *hdr;
+
+ struct freelist_allocator_block *freelist = &allocator->freelist, *block;
+ for (block = freelist->next; block != freelist; block = block->next) {
+ uintptr_t block_ptr = (uintptr_t) block;
+ uintptr_t block_end = block_ptr + block->size;
+
+ uintptr_t aligned_ptr = ALIGN_NEXT(block_ptr + sizeof *hdr, align);
+ if (block_end < aligned_ptr + size)
+ continue;
+
+ /* allocate new freeblock if there remaining space */
+ uintptr_t new_block_ptr = ALIGN_NEXT(aligned_ptr + size,
+ alignof(struct freelist_allocator_block));
+ if (new_block_ptr + sizeof *block < block_end) {
+ struct freelist_allocator_block *new_block = (void *) new_block_ptr;
+ new_block->size = block_end - new_block_ptr;
+
+ /* replace old block with new block in freelist */
+ freelist_allocator_freelist_insert(new_block,
+ block->prev,
+ block->next);
+
+ block_end = new_block_ptr;
+ } else {
+ /* cannot fit new block, snip old block from freelist */
+ freelist_allocator_freelist_remove(block);
+ }
+
+ /* write out header and return aligned allocation */
+ uintptr_t header_ptr = aligned_ptr - sizeof *hdr;
+ ASSERT(IS_ALIGNED(header_ptr, alignof(struct freelist_allocator_header)));
+
+ hdr = (void *) header_ptr;
+ hdr->padding = aligned_ptr - block_ptr;
+ hdr->size = block_end - aligned_ptr;
+
+ return (void *) aligned_ptr;
+ }
+
+ return NULL;
+}
+
+inline void
+freelist_free(struct freelist_allocator *allocator, void *res)
+{
+ uintptr_t ptr = (uintptr_t) res;
+
+ struct freelist_allocator_header *hdr = (void *) (ptr - sizeof *hdr);
+ uintptr_t block_ptr = ptr - hdr->padding;
+ uintptr_t block_end = ptr + hdr->size;
+
+ struct freelist_allocator_block *block = (void *) block_ptr;
+ block->size = block_end - block_ptr;
+
+ /* find blocks in freelist list immediately before and after new block */
+ struct freelist_allocator_block *freelist = &allocator->freelist, *next, *prev;
+ for (next = freelist->next; next != freelist; next = next->next) {
+ if (block < next)
+ break;
+ }
+
+ prev = next->prev;
+
+ freelist_allocator_freelist_insert(block, prev, next);
+
+ /* coalesce blocks if possible */
+ if (next != freelist && (uintptr_t) next == block_end) {
+ block->size += next->size;
+ freelist_allocator_freelist_remove(next);
+ }
+
+ if (prev != freelist && (uintptr_t) prev + prev->size == block_ptr) {
+ prev->size += block->size;
+ freelist_allocator_freelist_remove(block);
+ }
+}
+
/* buddy allocator
* ---------------------------------------------------------------------------
* A block-based allocator. Supports allocating out of a tree of memory blocks,
@@ -236,7 +373,7 @@ extern inline void
stack_free(struct stack_allocator *allocator, void *res);
extern inline void
-pool_init(struct pool_allocator *allocator, size_t block_size);
+pool_allocator_init(struct pool_allocator *allocator, size_t block_size);
extern inline void *
pool_alloc(struct pool_allocator *allocator, size_t size, size_t align);
@@ -244,4 +381,21 @@ pool_alloc(struct pool_allocator *allocator, size_t size, size_t align);
extern inline void
pool_free(struct pool_allocator *allocator, void *res);
+extern inline void
+freelist_allocator_freelist_insert(struct freelist_allocator_block *block,
+ struct freelist_allocator_block *prev,
+ struct freelist_allocator_block *next);
+
+extern inline void
+freelist_allocator_freelist_remove(struct freelist_allocator_block *block);
+
+extern inline void
+freelist_allocator_init(struct freelist_allocator *allocator);
+
+extern inline void *
+freelist_alloc(struct freelist_allocator *allocator, size_t size, size_t align);
+
+extern inline void
+freelist_free(struct freelist_allocator *allocator, void *res);
+
#endif /* HEADER_IMPL */
