implement arena allocators

7 files changed, 151 insertions, 15 deletions

diff --git a/README b/README
index a5a0832..303eea4 100644
--- a/README
+++ b/README
@@ -9,7 +9,7 @@ This does not aim to be a LibC replacement, but rather a supplimentary
 library.  It is a C23 library with no plans to support older standards.
 
 The headers as of now are:
- • alloc.h — memory allocation functions
+ • alloc.h — allocators and memory allocation functions
  • bitset.h — bitset implementation
  • dynarr.h — dynamic array implementation
  • errors.h — err.h-inspired diagnostics functions
@@ -44,7 +44,6 @@ DISCLAIMER:
     you not?
 
 Planned Features:
- • Arena Allocators            (alloc.h)
  • Missing Unicode Properties  (unicode/prop.h)
  • String Case Conversions     (unicode/string.h)
  • Unicode Normalization       (unicode/string.h)
diff --git a/include/_attrs.h b/include/_attrs.h
new file mode 100644
index 0000000..513a5c7
--- /dev/null
+++ b/include/_attrs.h
@@ -0,0 +1,7 @@
+#ifndef MLIB__ATTRS_H
+#define MLIB__ATTRS_H
+
+#define _mlib_pure __nodiscard__, __unsequenced__
+#define _mlib_inline gnu::__always_inline__, clang::__always_inline__
+
+#endif /* !MLIB__ATTRS_H */
diff --git a/include/alloc.h b/include/alloc.h
index 6eb2a30..0855e01 100644
--- a/include/alloc.h
+++ b/include/alloc.h
@@ -3,7 +3,38 @@
 
 #include <stddef.h>
 
+#include "_attrs.h"
+
+#ifndef MLIB_ARENA_BLKSIZE
+#	define MLIB_ARENA_BLKSIZE (8 * 1024)
+#endif
+
+struct _region {
+	size_t len, cap;
+	void *data;
+	struct _region *next;
+};
+
+typedef struct {
+	struct _region *_head;
+	size_t _init;
+} arena;
+
 [[gnu::__returns_nonnull__]] void *bufalloc(void *, size_t, size_t);
 void *bufalloc_noterm(void *, size_t, size_t);
 
+[[_mlib_pure, _mlib_inline]]
+static inline arena
+mkarena(size_t n)
+{
+	return (arena){._init = n ? n : MLIB_ARENA_BLKSIZE};
+}
+
+[[gnu::__malloc__, gnu::__alloc_size__(2, 3), gnu::__alloc_align__(4)]]
+void *arena_alloc(arena *, size_t, size_t, size_t);
+void arena_zero(arena *);
+void arena_free(arena *);
+
+#define arena_new(a, T, n) ((T *)arena_alloc((a), sizeof(T), (n), alignof(T)))
+
 #endif /* !MLIB_ALLOC_H */
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"