From d874d01e8e9a30f0073a6e559cbae07244dec7bf Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Thu, 3 Oct 2024 00:36:26 +0200 Subject: Huge library overhaul --- lib/alloc/alloc_arena.c | 22 ------ lib/alloc/alloc_heap.c | 31 -------- lib/alloc/arena_alloc.c | 155 ++++++++++++++++++++++++++------------- lib/alloc/arena_free.c | 20 ----- lib/alloc/arena_realloc.c | 62 ---------------- lib/alloc/arena_zero.c | 15 ---- lib/alloc/bufalloc.c | 10 --- lib/alloc/bufalloc_noterm.c | 16 ---- lib/alloc/heap_alloc.c | 76 +++++++++++++++++++ lib/alloc/static_scratch_alloc.c | 44 +++++++++++ 10 files changed, 226 insertions(+), 225 deletions(-) delete mode 100644 lib/alloc/alloc_arena.c delete mode 100644 lib/alloc/alloc_heap.c delete mode 100644 lib/alloc/arena_free.c delete mode 100644 lib/alloc/arena_realloc.c delete mode 100644 lib/alloc/arena_zero.c delete mode 100644 lib/alloc/bufalloc.c delete mode 100644 lib/alloc/bufalloc_noterm.c create mode 100644 lib/alloc/heap_alloc.c create mode 100644 lib/alloc/static_scratch_alloc.c (limited to 'lib/alloc') 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 - -#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 -#include -#include -#include -#include - -#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 #include +#include #include -#include +#include +#include +#include +#include #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 - -#include - -#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 -#include -#include - -#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 -#include -#include - -#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 +#include +#include +#include +#include + +#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 +#include +#include +#include + +#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:"); +} -- cgit v1.2.3