From 43b04a1bfaecfabe8b3460575db7be5d592f896b Mon Sep 17 00:00:00 2001
From: Thomas Voss <mail@thomasvoss.com>
Date: Tue, 16 Apr 2024 02:03:12 +0200
Subject: implement arena allocators

---
 lib/alloc/arena_alloc.c     | 77 +++++++++++++++++++++++++++++++++++++++++++++
 lib/alloc/arena_free.c      | 20 ++++++++++++
 lib/alloc/arena_zero.c      | 14 +++++++++
 lib/alloc/bufalloc_noterm.c | 14 +--------
 4 files changed, 112 insertions(+), 13 deletions(-)
 create mode 100644 lib/alloc/arena_alloc.c
 create mode 100644 lib/alloc/arena_free.c
 create mode 100644 lib/alloc/arena_zero.c

(limited to 'lib/alloc')

diff --git a/lib/alloc/arena_alloc.c b/lib/alloc/arena_alloc.c
new file mode 100644
index 0000000..e5b99b7
--- /dev/null
+++ b/lib/alloc/arena_alloc.c
@@ -0,0 +1,77 @@
+#include <sys/mman.h>
+
+#include <errno.h>
+#include <stdckdint.h>
+#include <stdlib.h>
+
+#include "_attrs.h"
+#include "alloc.h"
+#include "macros.h"
+
+#define IS_POW_2(n) ((n) != 0 && ((n) & ((n) - 1)) == 0)
+
+[[_mlib_pure, _mlib_inline]] static size_t pad(size_t, size_t);
+static struct _region *mkregion(size_t);
+
+size_t
+pad(size_t len, size_t align)
+{
+	return (len + align - 1) & ~(align - 1);
+}
+
+struct _region *
+mkregion(size_t cap)
+{
+	struct _region *r = malloc(sizeof(struct _region));
+	if (r == nullptr)
+		return nullptr;
+	*r = (struct _region){
+		.cap = cap,
+		.data = mmap(nullptr, cap, PROT_READ | PROT_WRITE,
+	                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0),
+	};
+	if (r->data == MAP_FAILED) {
+		free(r);
+		return nullptr;
+	}
+	return r;
+}
+
+void *
+arena_alloc(arena *a, size_t sz, size_t n, size_t align)
+{
+	ASSUME(a != nullptr);
+	ASSUME(IS_POW_2(align));
+
+	if (ckd_mul(&sz, sz, n)) {
+		errno = EOVERFLOW;
+		return nullptr;
+	}
+
+	for (struct _region *r = a->_head; r != nullptr; r = r->next) {
+		size_t off = pad(r->len, align);
+
+		/* Technically there are other ways to solve this… but at this point you
+		   might as well just fail */
+		size_t padded_sz;
+		if (ckd_add(&padded_sz, off, sz)) {
+			errno = EOVERFLOW;
+			return nullptr;
+		}
+
+		if (padded_sz <= r->cap) {
+			void *ret = (char *)r->data + off;
+			r->len = off + sz;
+			return ret;
+		}
+	}
+
+	/* No page exists with enough space */
+	struct _region *r = mkregion(MAX(sz, a->_init));
+	if (r == nullptr)
+		return nullptr;
+	r->next = a->_head;
+	r->len = sz;
+	a->_head = r;
+	return r->data;
+}
diff --git a/lib/alloc/arena_free.c b/lib/alloc/arena_free.c
new file mode 100644
index 0000000..dc2b45e
--- /dev/null
+++ b/lib/alloc/arena_free.c
@@ -0,0 +1,20 @@
+#include <sys/mman.h>
+
+#include <stdlib.h>
+
+#include "alloc.h"
+#include "macros.h"
+
+void
+arena_free(arena *a)
+{
+	ASSUME(a != nullptr);
+
+	struct _region *cur, *next;
+	for (cur = a->_head; cur != nullptr; cur = next) {
+		next = cur->next;
+		munmap(cur->data, cur->cap);
+		free(cur);
+	}
+	a->_head = nullptr;
+}
diff --git a/lib/alloc/arena_zero.c b/lib/alloc/arena_zero.c
new file mode 100644
index 0000000..b0e3fbe
--- /dev/null
+++ b/lib/alloc/arena_zero.c
@@ -0,0 +1,14 @@
+#include "alloc.h"
+#include "macros.h"
+
+void
+arena_zero(arena *a)
+{
+	ASSUME(a != nullptr);
+
+	struct _region *cur = a->_head;
+	while (cur != nullptr) {
+		cur->len = 0;
+		cur = cur->next;
+	}
+}
diff --git a/lib/alloc/bufalloc_noterm.c b/lib/alloc/bufalloc_noterm.c
index 8258521..e46d2a1 100644
--- a/lib/alloc/bufalloc_noterm.c
+++ b/lib/alloc/bufalloc_noterm.c
@@ -1,17 +1,5 @@
 #include <errno.h>
-#if __has_include(<stdckdint.h>)
-#	include <stdckdint.h>
-#	ifdef __APPLE__
-#		warning "stdckdint.h now available on Mac; remove manual ckd_*() code"
-#	endif
-#elifdef __GNUC__
-#	define ckd_add(r, a, b) ((bool)__builtin_add_overflow(a, b, r))
-#	define ckd_mul(r, a, b) ((bool)__builtin_mul_overflow(a, b, r))
-#else
-#	define ckd_add(r, a, b) (*(r) = (a) + (b))
-#	define ckd_mul(r, a, b) (*(r) = (a) * (b))
-#	warning "ckd_*() not supported on the current platform"
-#endif
+#include <stdckdint.h>
 #include <stdlib.h>
 
 #include "alloc.h"
-- 
cgit v1.2.3