8 files changed, 437 insertions, 0 deletions
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 <assert.h>
+#include <stdint.h>
+#include <string.h>
+#include <stddef.h>
+
+#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 <stddef.h>
+#include <stdbool.h>
+
+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 <assert.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+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 <assert.h>
+#include <stdint.h>
+#include <unistd.h>
+#include <sys/mman.h>
+
+#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 <stdlib.h>
+
+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