10 files changed, 226 insertions, 225 deletions

diff --git a/lib/alloc/alloc_arena.c b/lib/alloc/alloc_arena.c
deleted file mode 100644
index 8d2aa11..0000000
--- a/lib/alloc/alloc_arena.c
+++ /dev/null
@@ -1,22 +0,0 @@
-#include <stdlib.h>
-
-#include "alloc.h"
-#include "errors.h"
-#include "macros.h"
-
-void *
-alloc_arena(void *raw_ctx, void *ptr, size_t old, size_t new, size_t elemsz,
-            size_t align)
-{
-	struct arena_ctx *ctx = raw_ctx;
-	ASSUME(ctx != nullptr);
-	ASSUME(ctx->a != nullptr);
-
-	void *p = arena_realloc(ctx->a, ptr, old, new, elemsz, align);
-	if (new == 0 || p != nullptr)
-		return p;
-
-	if (ctx->jmp != nullptr)
-		longjmp(*ctx->jmp, 1);
-	err("arena_realloc:");
-}
diff --git a/lib/alloc/alloc_heap.c b/lib/alloc/alloc_heap.c
deleted file mode 100644
index fccfcfc..0000000
--- a/lib/alloc/alloc_heap.c
+++ /dev/null
@@ -1,31 +0,0 @@
-#include <errno.h>
-#include <setjmp.h>
-#include <stdckdint.h>
-#include <stddef.h>
-#include <stdlib.h>
-
-#include "alloc.h"
-#include "errors.h"
-
-void *
-alloc_heap(void *raw_ctx, void *ptr, size_t, size_t new, size_t elemsz, size_t)
-{
-	if (new == 0) {
-		free(ptr);
-		return nullptr;
-	}
-
-	if (!ckd_mul(&new, new, elemsz)) {
-		void *p = realloc(ptr, new);
-		if (p != nullptr)
-			return p;
-	} else
-		errno = EOVERFLOW;
-
-	struct heap_ctx *ctx = raw_ctx;
-	if (ctx == nullptr || ctx->jmp == nullptr)
-		err("realloc:");
-
-	longjmp(*ctx->jmp, 1);
-	unreachable();
-}
diff --git a/lib/alloc/arena_alloc.c b/lib/alloc/arena_alloc.c
index 65123d4..d953423 100644
--- a/lib/alloc/arena_alloc.c
+++ b/lib/alloc/arena_alloc.c
@@ -1,80 +1,137 @@
+/* TODO: Support malloc() backend for systems without MAP_ANONYMOUS */
+
 #include <sys/mman.h>
 
 #include <errno.h>
+#include <setjmp.h>
 #include <stdckdint.h>
-#include <stdlib.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+#include <unistd.h>
 
 #include "_attrs.h"
+#include "_charN_t.h"
 #include "alloc.h"
+#include "error.h"
 #include "macros.h"
 
-#define IS_POW_2(n) ((n) != 0 && ((n) & ((n) - 1)) == 0)
+#define PAD(len, align) (((len) + (align) - 1) & ~((align) - 1))
 
-[[_mlib_pure, _mlib_inline]] static size_t pad(size_t, size_t);
-static struct _region *mkregion(size_t);
+struct arena_blk {
+	char8_t *head, *tail, *fngr;
+	struct arena_blk *next;
+};
 
-size_t
-pad(size_t len, size_t align)
-{
-	return (len + align - 1) & ~(align - 1);
-}
+static void *alloc(allocator_t mem, ptrdiff_t nmemb, ptrdiff_t elemsz,
+				   ptrdiff_t align);
+static void freeall(allocator_t mem);
+static arena_blk_t *mkblk(ptrdiff_t blksz);
+[[noreturn]] static void errjmp(jmp_buf *env);
 
-struct _region *
-mkregion(size_t cap)
+void *
+arena_alloc(allocator_t mem, alloc_mode_t mode, void *ptr, ptrdiff_t oldnmemb,
+			ptrdiff_t newnmemb, ptrdiff_t elemsz, ptrdiff_t align)
 {
-	struct _region *r = malloc(sizeof(struct _region));
-	if (r == nullptr)
+	(void)ptr;
+	(void)oldnmemb;
+	switch (mode) {
+	case ALLOC_NEW:
+		return alloc(mem, newnmemb, elemsz, align);
+	case ALLOC_RESIZE:
+		/* TODO: Make this more efficient */
+		void *p = alloc(mem, newnmemb, elemsz, align);
+		memcpy(p, ptr, MIN(oldnmemb, newnmemb) * elemsz);
+		return p;
+	case ALLOC_FREE:
+		/* TODO: Allow freeing the very last allocation */
 		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) {
-		int save = errno;
-		free(r);
-		errno = save;
+	case ALLOC_FREEALL:
+		freeall(mem);
 		return nullptr;
+	default:
+		unreachable();
 	}
-	r->last = r->data;
-	return r;
 }
 
 void *
-arena_alloc(arena *a, size_t sz, size_t n, size_t align)
+alloc(allocator_t mem, ptrdiff_t nmemb, ptrdiff_t elemsz, ptrdiff_t align)
 {
-	ASSUME(a != nullptr);
-	ASSUME(IS_POW_2(align));
+	arena_ctx_t *ctx = mem.ctx;
+	if (ctx->blksz == 0) {
+		long blksz = sysconf(_SC_PAGESIZE);
+		if (blksz == -1)
+			errjmp(mem.err);
+		ctx->blksz = blksz;
+	}
 
-	if (ckd_mul(&sz, sz, n)) {
+	ptrdiff_t bufsz;
+	if (ckd_mul(&bufsz, nmemb, elemsz)) {
 		errno = EOVERFLOW;
-		return nullptr;
+		errjmp(mem.err);
 	}
 
-	for (struct _region *r = a->_head; r != nullptr; r = r->next) {
-		size_t nlen, off = pad(r->len, align);
+	for (arena_blk_t *blk = ctx->_head; blk != nullptr; blk = blk->next) {
+		ptrdiff_t nbufsz, off = PAD((uintptr_t)blk->fngr, align);
+		if (ckd_add(&nbufsz, bufsz, off))
+			continue;
 
-		/* Technically there are other ways to solve this… but at this point you
-		   might as well just fail */
-		if (ckd_add(&nlen, off, sz)) {
-			errno = EOVERFLOW;
-			return nullptr;
+		if (blk->tail - blk->fngr >= nbufsz) {
+			void *p = blk->fngr + off;
+			blk->fngr += nbufsz;
+			return p;
 		}
+	}
 
-		if (nlen <= r->cap) {
-			void *ret = (char *)r->data + off;
-			r->len = nlen;
-			r->last = ret;
-			return ret;
-		}
+	/* No page exists that is large enough for our allocation */
+	ptrdiff_t padding = PAD(sizeof(arena_blk_t), align);
+
+	if (ckd_add(&bufsz, bufsz, sizeof(arena_blk_t))
+	 || ckd_add(&bufsz, bufsz, padding))
+	{
+		errno = EOVERFLOW;
+		errjmp(mem.err);
 	}
+	
+	arena_blk_t *blk = mkblk(MAX(bufsz, ctx->blksz));
+	if (blk == nullptr)
+		errjmp(mem.err);
+	blk->next = ctx->_head;
+	blk->fngr = blk->head + bufsz;
+	ctx->_head = blk;
+	return blk->head + sizeof(arena_blk_t) + padding;
+}
 
-	/* No page exists with enough space */
-	struct _region *r = mkregion(MAX(sz, a->_init));
-	if (r == nullptr)
+void
+freeall(allocator_t mem)
+{
+	arena_ctx_t *ctx = mem.ctx;
+	arena_blk_t *blk = ctx->_head;
+	while (blk != nullptr) {
+		arena_blk_t *next = blk->next;
+		(void)munmap(blk, blk->tail - blk->head);
+		blk = next;
+	}
+	ctx->_head = nullptr;
+}
+
+static arena_blk_t *
+mkblk(ptrdiff_t blksz)
+{
+	arena_blk_t blk;
+	/* blk.next and blk.fngr get set by the caller */
+	blk.head = mmap(nullptr, blksz, PROT_READ | PROT_WRITE,
+					MAP_PRIVATE | MAP_ANON, -1, 0);
+	if (blk.head == MAP_FAILED)
 		return nullptr;
-	r->next = a->_head;
-	r->len = sz;
-	a->_head = r;
-	return r->data;
+	blk.tail = blk.head + blksz;
+	return memcpy(blk.head, &blk, sizeof blk);
+}	
+
+void
+errjmp(jmp_buf *env)
+{
+	if (env != nullptr)
+		longjmp(*env, 1);
+	err("arena_alloc:");
 }
diff --git a/lib/alloc/arena_free.c b/lib/alloc/arena_free.c
deleted file mode 100644
index dc2b45e..0000000
--- a/lib/alloc/arena_free.c
+++ /dev/null
@@ -1,20 +0,0 @@
-#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_realloc.c b/lib/alloc/arena_realloc.c
deleted file mode 100644
index 6877ae1..0000000
--- a/lib/alloc/arena_realloc.c
+++ /dev/null
@@ -1,62 +0,0 @@
-#include <errno.h>
-#include <stdckdint.h>
-#include <string.h>
-
-#include "alloc.h"
-#include "macros.h"
-
-void *
-arena_realloc(arena *a, void *ptr, size_t old, size_t new, size_t elemsz,
-              size_t align)
-{
-	ASSUME(a != nullptr);
-
-	if (ptr == nullptr)
-		return arena_alloc(a, new, elemsz, align);
-
-	if (old == new)
-		return ptr;
-
-	struct _region *cur = a->_head;
-	while (cur != nullptr) {
-		if (ptr >= cur->data && (char *)ptr < (char *)cur->data + cur->cap)
-			break;
-		cur = cur->next;
-	}
-	if (cur == nullptr)
-		cur = a->_head;
-
-	/* cur now points to the region containing ‘ptr’ */
-
-	/* If we are shrinking the buffer, then we don’t need to move our allocation
-	   and can just return it directly.  As a minor optimization if the
-	   allocation we are shrinking is the last allocation in the current region,
-	   we can decrease the region length to make space for more future
-	   allocations. */
-	if (old > new) {
-		if (ptr == cur->last)
-			cur->len -= (old - new) * elemsz;
-		return ptr;
-	}
-
-	ASSUME(old < new);
-
-	/* If we need to grow the given allocation, but it was the last allocation
-	   made in a region, then we first see if we can just eat more trailing free
-	   space in the region to avoid a memcpy(). */
-	if (ptr == cur->last) {
-		size_t need, free = cur->cap - cur->len;
-		if (ckd_mul(&need, new - old, elemsz)) {
-			errno = EOVERFLOW;
-			return nullptr;
-		}
-		if (need <= free) {
-			cur->len += need;
-			return ptr;
-		}
-	}
-
-	/* At this point we just make a new allocation and copy the data over */
-	void *dst = arena_alloc(a, new, elemsz, align);
-	return dst == nullptr ? nullptr : memcpy(dst, ptr, old * elemsz);
-}
diff --git a/lib/alloc/arena_zero.c b/lib/alloc/arena_zero.c
deleted file mode 100644
index 296007e..0000000
--- a/lib/alloc/arena_zero.c
+++ /dev/null
@@ -1,15 +0,0 @@
-#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->last = cur->data;
-		cur = cur->next;
-	}
-}
diff --git a/lib/alloc/bufalloc.c b/lib/alloc/bufalloc.c
deleted file mode 100644
index 264f242..0000000
--- a/lib/alloc/bufalloc.c
+++ /dev/null
@@ -1,10 +0,0 @@
-#include "alloc.h"
-#include "errors.h"
-
-void *
-bufalloc(void *p, size_t n, size_t m)
-{
-	if ((p = bufalloc_noterm(p, n, m)) == nullptr)
-		err("%s:", __func__);
-	return p;
-}
diff --git a/lib/alloc/bufalloc_noterm.c b/lib/alloc/bufalloc_noterm.c
deleted file mode 100644
index e46d2a1..0000000
--- a/lib/alloc/bufalloc_noterm.c
+++ /dev/null
@@ -1,16 +0,0 @@
-#include <errno.h>
-#include <stdckdint.h>
-#include <stdlib.h>
-
-#include "alloc.h"
-
-void *
-bufalloc_noterm(void *p, size_t n, size_t m)
-{
-	if (ckd_mul(&n, n, m)) {
-		errno = EOVERFLOW;
-		return nullptr;
-	}
-
-	return realloc(p, n);
-}
diff --git a/lib/alloc/heap_alloc.c b/lib/alloc/heap_alloc.c
new file mode 100644
index 0000000..4779ff6
--- /dev/null
+++ b/lib/alloc/heap_alloc.c
@@ -0,0 +1,76 @@
+#include <assert.h>
+#include <stdckdint.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "alloc.h"
+#include "errors.h"
+
+[[noreturn]] static void oom(jmp_buf *env);
+
+void *
+heap_alloc(allocator_t mem, alloc_mode_t mode, void *ptr, ptrdiff_t oldnmemb,
+		   ptrdiff_t newnmemb, ptrdiff_t elemsz, ptrdiff_t align) 
+{
+	void *p;
+	ptrdiff_t oldsz, newsz;
+	
+	switch (mode) {
+	case ALLOC_NEW:
+		if (ckd_mul(&newsz, newnmemb, elemsz))
+			oom(mem.err);
+		/* Malloc is guaranteed to return a pointer aligned to an
+		   alignment that is suitable for all fundamental types.  For
+		   larger alignments we need to use specialized functionality. */
+		if ((size_t)align <= alignof(max_align_t)) {
+			if ((p = malloc(newsz)) == nullptr)
+				oom(mem.err);
+		} else {
+			if ((p = aligned_alloc(align, newsz)) == nullptr)
+				oom(mem.err);
+		}
+		return p;
+	case ALLOC_RESIZE:
+		if (ckd_mul(&newsz, newnmemb, elemsz))
+			oom(mem.err);
+		if (ckd_mul(&oldsz, oldnmemb, elemsz))
+			oom(mem.err);
+		if ((size_t)align <= alignof(max_align_t)) {
+			if ((p = realloc(ptr, newsz)) == nullptr)
+				oom(mem.err);
+		} else {
+			/* We were allocated using aligned_alloc().  Unfortunately
+		       there is no way to reallocate a buffer aligned via
+		       aligned_alloc() so we need to allocate a new buffer and do
+		       a manual copy… */
+			if ((p = aligned_alloc(align, newsz)) == nullptr)
+				oom(mem.err);
+			memcpy(p, ptr, oldsz);
+#if 0
+			/* We would rather use free_aligned_size(), but it isn’t
+			   available yet on most systems. */
+			free_aligned_sized(ptr, align, oldsz);
+#else
+			free(ptr);
+#endif
+		}
+		return p;
+	case ALLOC_FREE:
+		free(ptr);
+		return nullptr;
+	case ALLOC_FREEALL:
+		assert(!"Not implemented");
+		return nullptr;
+	default:
+		unreachable();
+	}
+}
+
+void
+oom(jmp_buf *env)
+{
+	if (env != nullptr)
+		longjmp(*env, 1);
+	err("heap_alloc:");
+}
diff --git a/lib/alloc/static_scratch_alloc.c b/lib/alloc/static_scratch_alloc.c
new file mode 100644
index 0000000..2489b98
--- /dev/null
+++ b/lib/alloc/static_scratch_alloc.c
@@ -0,0 +1,44 @@
+#include <errno.h>
+#include <setjmp.h>
+#include <stdckdint.h>
+#include <stdint.h>
+
+#include "alloc.h"
+#include "errors.h"
+
+[[noreturn]] static void oom(jmp_buf *env);
+
+void *
+static_scratch_alloc(allocator_t mem, alloc_mode_t mode, void *,
+					 ptrdiff_t, ptrdiff_t newnmemb, ptrdiff_t elemsz,
+					 ptrdiff_t align) 
+{
+	st_buf_t *ctx = mem.ctx;
+	
+	switch (mode) {
+	case ALLOC_NEW:
+	case ALLOC_RESIZE:
+		ptrdiff_t pad, avail, total;
+		if (ckd_mul(&total, newnmemb, elemsz))
+			oom(mem.err);
+		pad = -(uintptr_t)ctx->buf & (align - 1);
+		avail = ctx->len - pad;
+		if (avail < 0 || total > avail)
+			oom(mem.err);
+		return (char *)ctx->buf + pad;
+	case ALLOC_FREE:
+	case ALLOC_FREEALL:
+		return nullptr;
+	default:
+		unreachable();
+	}
+}
+
+void
+oom(jmp_buf *env)
+{
+	errno = ENOMEM;
+	if (env != nullptr)
+		longjmp(*env, 1);
+	err("static_scratch_alloc:");
+}