From 8dd0c4f27aae02dd60f029db4cf03f9902cba26f Mon Sep 17 00:00:00 2001 From: Linnnus Date: Tue, 8 Apr 2025 01:07:22 +0000 Subject: feat: Initial commit At this point we have some allocation routines but no work on the actual language has been done. --- src/core/allocator.c | 87 ++++++++++++++++++++++++++++++++++++++++ src/core/allocator.h | 69 ++++++++++++++++++++++++++++++++ src/core/arena_allocator.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++ src/core/arena_allocator.h | 33 ++++++++++++++++ src/core/page_allocator.c | 91 ++++++++++++++++++++++++++++++++++++++++++ src/core/page_allocator.h | 11 ++++++ src/core/std_allocator.c | 37 +++++++++++++++++ src/core/std_allocator.h | 11 ++++++ 8 files changed, 437 insertions(+) create mode 100644 src/core/allocator.c create mode 100644 src/core/allocator.h create mode 100644 src/core/arena_allocator.c create mode 100644 src/core/arena_allocator.h create mode 100644 src/core/page_allocator.c create mode 100644 src/core/page_allocator.h create mode 100644 src/core/std_allocator.c create mode 100644 src/core/std_allocator.h (limited to 'src/core') diff --git a/src/core/allocator.c b/src/core/allocator.c new file mode 100644 index 0000000..5444b39 --- /dev/null +++ b/src/core/allocator.c @@ -0,0 +1,87 @@ +#include "allocator.h" + +#include +#include +#include +#include + +#define DEFAULT_ALIGNMENT ((size_t)_Alignof(max_align_t)) + +void *sand_allocate_aligned(SandAllocator *a, size_t size, size_t alignment) { + assert(a != NULL); + assert(size > 0); + assert(alignment > 0); + void *ptr = a->allocate(size, alignment, a->user_data); + assert(ptr == NULL || sand_pointer_is_aligned(ptr, alignment)); + return ptr; +} + +void *sand_allocate(SandAllocator *a, size_t size) { + return sand_allocate_aligned(a, size, DEFAULT_ALIGNMENT); +} + +void *sand_reallocate_aligned(SandAllocator *a, void *old_ptr, size_t old_size, size_t new_size, size_t alignment) { + assert(a != NULL); + assert(old_ptr != NULL); + assert(old_size > 0); + assert(new_size > 0); + assert(alignment > 0); + + if (a->reallocate != NULL) { + void *new_ptr = a->reallocate(old_ptr, old_size, new_size, alignment, a->user_data); + assert(sand_pointer_is_aligned(new_ptr, alignment)); + return new_ptr; + } else { + void *new_ptr = a->allocate(new_size, alignment, a->user_data); + if (new_ptr == NULL) { + return NULL; // Note that we HAVEN'T freed `old_ptr`! + } + assert(sand_pointer_is_aligned(new_ptr, alignment)); + memmove(new_ptr, old_ptr, old_size); // Can't know if they overlap. + a->deallocate(old_ptr, old_size, a->user_data); + return new_ptr; + } +} + +void *sand_reallocate(SandAllocator *a, void *old_ptr, size_t old_size, size_t new_size) { + return sand_reallocate_aligned(a, old_ptr, old_size, new_size, DEFAULT_ALIGNMENT); +} + +void sand_deallocate(SandAllocator *a, void *old_ptr, size_t old_size) { + assert(a != NULL); + assert(old_ptr != NULL); + assert(old_size > 0); + + if (old_ptr == NULL) { + return; + } + a->deallocate(old_ptr, old_size, a->user_data); +} + +bool sand_is_valid_alignment(size_t alignment) { + // Only powers of two are allowed as alignments for simplicity. + return alignment % 2 == 0; +} + +void *sand_align_pointer_forward(void *ptr, size_t alignment) { + intptr_t p = (intptr_t)ptr; + intptr_t a = alignment; + intptr_t ap = ((p + a - 1) & ~(a - 1)); + void *result = (void *)ap; + assert(sand_pointer_is_aligned(result, alignment)); + return result; +} + +size_t sand_align_size_forward(size_t n, size_t alignment) { + size_t result = ((n + alignment - 1) & ~(alignment - 1)); + assert(sand_size_is_aligned(result, alignment)); + return result; +} + +bool sand_pointer_is_aligned(void *pointer, size_t alignment) { + return ((uintptr_t)pointer & (alignment - 1)) == 0; +} + +bool sand_size_is_aligned(size_t n, size_t alignment) { + return (n & (alignment - 1)) == 0; +} diff --git a/src/core/allocator.h b/src/core/allocator.h new file mode 100644 index 0000000..e67a08b --- /dev/null +++ b/src/core/allocator.h @@ -0,0 +1,69 @@ +#ifndef SAND_ALLOCATOR_H +#define SAND_ALLOCATOR_H + +// This module defines a generic allocator interface. All allocations in this +// family of programs happen through this allocation interface. +// +// As references to `SandAllocator`s are passed all around the program, the +// convention adopted here is to allow single-variable (mainly `a`) names for +// these. + +#include +#include + +typedef struct { + // Shall return a new piece of writable and readable memory of size `size` and with alignment `alignment`. + // This function may return `NULL` to indicate out-of-memory. + // Caller promises to call `deallocate` or `reallocate` on the returned pointer. + void *(* allocate)(size_t size, size_t alignment, void *user_data); + + // Shall the allocation made at `old_ptr`. + // Unlike with `realloc(3)`, `old_ptr` is not nullable. + // This operation is assumed to be infallible, as there is no reasonable way to recover. + // FIXME: This should take alignment as well. + void (* deallocate)(void *old_ptr, size_t old_size, void *user_data); + + // Resize the allocation at `old_ptr` from `old_size` to `new_size`. + // `alignment` is guaranteed to be the same as passed to the original call to `allocate`. + // `old_ptr` and `old_size` are guaranteed to be from the last successful invocation of `allocate` or `reallocate`. + // This function may return `NULL` to indicate out-of-memory, however `old_ptr` should still remain valid in that case. + // The struct member itself may be `NULL`, in which case a default implementation is used. + void *(* reallocate)(void *old_ptr, size_t old_size, size_t new_size, size_t alignment, void *user_data); + + // Custom data which is passed to every function in the interface. The + // allocator can use this for extra metadata it needs to keep. + void *user_data; +} SandAllocator; + + +// Allocates a chunk of memory with the given size and alignment. +// Returns `NULL` on failure. +// Caller assumes ownership of returned pointer, must free with `sand_deallocate`. +void *sand_allocate_aligned(SandAllocator *, size_t size, size_t alignment); + +// Same as `sand_allocate_aligned` but with default alignment. +void *sand_allocate(SandAllocator *, size_t size); + +// Resize the allocation at `old_ptr` from `old_size` to `new_size`. +// `alignment` is guaranteed to be the same as passed to the original call to `allocate`. +// Returns a new pointer or `NULL` if reallocation fails. +// If `NULL` is returned, `old_ptr` remains valid. +// Caller assumes ownership of returned pointer (or retains ownership of old pointer). +void *sand_reallocate_aligned(SandAllocator *, void *old_ptr, size_t old_size, size_t new_size, size_t alignment); + +// Same as `sand_reallocate_aligned` but with default alignment. +void *sand_reallocate(SandAllocator *, void *old_ptr, size_t old_size, size_t new_size); + +// Frees `old_ptr`. +// `old_ptr` is nullable, in which case `old_size` is ignored. +// `old_size` must match the size passed to last call to `sand_allocate` or `sand_reallocate`. +void sand_deallocate(SandAllocator *, void *old_ptr, size_t old_size); + +// The following are only intended to be used by allocator implementations. +bool sand_is_valid_alignment(size_t alignment); +bool sand_pointer_is_aligned(void *pointer, size_t alignment); +void *sand_align_pointer_forward(void *ptr, size_t alignment); +bool sand_size_is_aligned(size_t n, size_t alignment); +size_t sand_align_size_forward(size_t n, size_t alignment); + +#endif diff --git a/src/core/arena_allocator.c b/src/core/arena_allocator.c new file mode 100644 index 0000000..cbde038 --- /dev/null +++ b/src/core/arena_allocator.c @@ -0,0 +1,98 @@ +#include "arena_allocator.h" + +#include +#include +#include + +SandArena sand_create_arena(SandAllocator *a) { + return (SandArena) { + .parent = a, + .current_region = NULL, + }; +} + +#define MAX(a, b) ({ \ + __auto_type _a = (a);\ + __auto_type _b = (b);\ + _a > _b ? _a : _b;\ + }) + +#define REGION_DEFUALT_SIZE ((size_t)2048) + +static SandRegion *allocate_new_region(SandAllocator *a, size_t size, size_t alignment) { + size_t padded_size = size + (alignment - 1); + size_t capacity = MAX(padded_size, REGION_DEFUALT_SIZE) ; + size_t region_size = offsetof(SandRegion, data) + capacity; + SandRegion *result = sand_allocate_aligned(a, region_size, _Alignof(SandRegion)); + if (result == NULL) { + return NULL; + } + result->capacity = capacity; + result->used = 0; + return result; +} + +static void *allocate(size_t size, size_t alignment, void *user_data) { + SandArena *arena = user_data; + + // This is the first allocation made within the arena. Let's allocate the initial region. + if (arena->current_region == NULL) { + SandRegion *first_region = allocate_new_region(arena->parent, size, alignment); + if (first_region == NULL) { + return NULL; + } + first_region->prev = NULL; + arena->current_region = first_region; + } + + SandRegion *iter = arena->current_region; + while (true) { // Loop looking for a region. + void *aligned_ptr = sand_align_pointer_forward(iter->data + iter->used, alignment); + void *end_ptr = iter->data + iter->capacity; + if (aligned_ptr + size > end_ptr) { // This pointer region doesn't have room; allocate a new one and try again. + SandRegion *new_region = allocate_new_region(arena->parent, size, alignment); + if (new_region == NULL) { + return NULL; + } + + new_region->prev = arena->current_region; + arena->current_region = iter; + + iter = new_region; // Next time is guaranteed to succeed. + continue; + } else { // Yay, we found a spot! + iter->used += aligned_ptr - (void *)iter->data; + return aligned_ptr; + } + } + + assert(false); // unreachable +} + +static void deallocate(void *old_ptr, size_t old_size, void *user_data) { + (void)old_ptr; + (void)old_size; + (void)user_data; + return; // No-op, as all allocations are freed when the arena is freed. +} + +// Returns a `SandAllocator` which is valid as long as the arena is. +// The arena must not be moved afterwards, as the allocator retains a pointer to the arena. +SandAllocator sand_get_allocator_for_arena(SandArena *arena) { + return (SandAllocator) { + .allocate = allocate, + .reallocate = NULL, // TODO: Special case for if it is the last allocation of the current region. + .deallocate = deallocate, + .user_data = arena, + }; +} + +void sand_destroy_arena(SandArena *arena) { + SandRegion *iter = arena->current_region; + while (iter != NULL) { + SandRegion *next = iter->prev; + size_t region_size = offsetof(SandRegion, data) + iter->capacity; + sand_deallocate(arena->parent, iter, region_size); + iter = next; + } +} diff --git a/src/core/arena_allocator.h b/src/core/arena_allocator.h new file mode 100644 index 0000000..5fba78a --- /dev/null +++ b/src/core/arena_allocator.h @@ -0,0 +1,33 @@ +#ifndef SAND_ARENA_ALLOCATOR_H +#define SAND_ARENA_ALLOCATOR_H + +// This module defines an arena allocator which implements `SandAllocator`. It +// is useful if one needs to allocate a lot of objects with the same lifetime +// very quickly. When the arena is destroyed, all objects allocated within are +// freed. + +#include "allocator.h" + +// This should only be used internally by an arena allocator. +// It is only public because of C's stone-age """modules""". +typedef struct _SandRegion { + struct _SandRegion *prev; + size_t capacity; + size_t used; + unsigned char data[]; +} SandRegion; + +typedef struct { + SandAllocator *parent; + SandRegion *current_region; +} SandArena; + +SandArena sand_create_arena(SandAllocator *parent); + +// Returns a `SandAllocator` which is valid as long as the arena is. +// The arena must not be moved afterwards, as the allocator retains a pointer to the arena. +SandAllocator sand_get_allocator_for_arena(SandArena *); + +void sand_destroy_arena(SandArena *); + +#endif diff --git a/src/core/page_allocator.c b/src/core/page_allocator.c new file mode 100644 index 0000000..a20aa76 --- /dev/null +++ b/src/core/page_allocator.c @@ -0,0 +1,91 @@ +#include "page_allocator.h" + +#include +#include +#include +#include + +#define MIN(a, b) \ + ({ \ + __auto_type _a = (a); \ + __auto_type _b = (b); \ + _a > _b ? _a : _b; \ + }) + +static void *allocate(size_t size, size_t alignment, void *user_data) { + (void)user_data; + + long _page_size = sysconf(_SC_PAGESIZE); + if (_page_size < 0) { + return NULL; + } + assert(_page_size > 512); // Sanity check + size_t page_size = _page_size; + + // First of all, the actual allocation size needs to be a multiple of the page size. + if (size >= SIZE_MAX - page_size) { + return NULL; // Nice overflow, idiot. + } + size_t aligned_size = sand_align_size_forward(size, page_size); + + // Furthermore, page alignment may not be enough, i.e. the required + // alignment is larger than the page size. So we compute how much extra + // memory (overallocation) is required. That gives us the size of the final allocation. + size_t max_drop_size = alignment - MIN(alignment, page_size); + size_t raw_size = (max_drop_size <= aligned_size - page_size) + ? aligned_size + : sand_align_size_forward(aligned_size + max_drop_size, page_size); + + void *raw_ptr = mmap(/* hint = */ NULL, + /* length = */ raw_size, + /* protection = */ PROT_READ | PROT_WRITE, + /* flags = */ MAP_PRIVATE | MAP_ANONYMOUS, + /* fd = */ -1, + /* offset = */ 0); + if (raw_ptr == MAP_FAILED) { + return NULL; + } + + // At this point we have our properly aligned pointer, which is + // guaranteed to point to a region of at least `size`. Now we just have + // to clean up after ourselves... The superflous bytes could be at the + // beginning or the end or both. + void *aligned_ptr = sand_align_pointer_forward(raw_ptr, alignment); + + assert(aligned_ptr >= raw_ptr); + size_t drop_size = aligned_ptr - raw_ptr; + if (drop_size > 0) { + munmap(raw_ptr, drop_size); + } + + size_t remaining_size = raw_size - drop_size; + if (remaining_size > aligned_size) { + munmap(aligned_ptr + aligned_size, remaining_size - aligned_size); + } + + return aligned_ptr; +} + +static void deallocate(void *old_ptr, size_t old_size, void *user_data) { + (void)user_data; + + // The actual allocation will be roughly a multiple of the page size + // (disregarding the cleanup at the end of `allocate`). This calculation + // matches that of the start of `allocate`. + long page_size = sysconf(_SC_PAGESIZE); + assert(old_size < SIZE_MAX - page_size); + size_t aligned_size = sand_align_size_forward(old_size, page_size); + + // This _should_ unmap the correct pages. + munmap(old_ptr, aligned_size); +} +static SandAllocator vtable = { + .allocate = allocate, + .deallocate = deallocate, + .reallocate = NULL, // TODO + .user_data = NULL, +}; + +SandAllocator *sand_get_page_allocator() { + return &vtable; +} diff --git a/src/core/page_allocator.h b/src/core/page_allocator.h new file mode 100644 index 0000000..506cd8f --- /dev/null +++ b/src/core/page_allocator.h @@ -0,0 +1,11 @@ +#ifndef SAND_PAGE_ALLOCATOR_H +#define SAND_PAGE_ALLOCATOR_H + +// This module defines an allocator (i.e. an implementation of `SandAllocator`) +// which allocates virtual memory pages. + +#include "allocator.h" + +SandAllocator *sand_get_page_allocator(); + +#endif diff --git a/src/core/std_allocator.c b/src/core/std_allocator.c new file mode 100644 index 0000000..ecfa806 --- /dev/null +++ b/src/core/std_allocator.c @@ -0,0 +1,37 @@ +#include "std_allocator.h" + +#include + +static void *allocate(size_t size, size_t alignment, void *user_data) { + (void)user_data; + + // `aligned_alloc(3)` requires that the requested size be a multiple of the requested alignment. + // this is safe to do, because we ignore `old_size` everywhere else. + size_t actual_size = (size + alignment - 1) & ~(alignment - 1); + + return aligned_alloc(alignment, actual_size); +} + +static void deallocate(void *old_ptr, size_t old_size, void *user_data) { + (void)old_size; + (void)user_data; + free(old_ptr); +} + +static void *reallocate(void *old_ptr, size_t old_size, size_t new_size, size_t alignment, void *user_data) { + (void)old_size; + (void)alignment; + (void)user_data; + + // fixme: does `realloc(3)` preserve alignment? + return realloc(old_ptr, new_size); +} + +SandAllocator sand_new_std_allocator() { + return (SandAllocator) { + .allocate = allocate, + .deallocate = deallocate, + .reallocate = reallocate, + .user_data = NULL, + }; +} diff --git a/src/core/std_allocator.h b/src/core/std_allocator.h new file mode 100644 index 0000000..6170272 --- /dev/null +++ b/src/core/std_allocator.h @@ -0,0 +1,11 @@ +#ifndef SAND_STD_ALLOCATOR_H +#define SAND_STD_ALLOCATOR_H + +// This module defines an allocator (i.e. an implementation of `SandAllocator`) +// which simply passes allocations to libc's sallocator. + +#include "allocator.h" + +SandAllocator sand_new_std_allocator(); + +#endif -- cgit v1.2.3