From 43b04a1bfaecfabe8b3460575db7be5d592f896b Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Tue, 16 Apr 2024 02:03:12 +0200 Subject: implement arena allocators --- README | 3 +- include/_attrs.h | 7 +++++ include/alloc.h | 31 ++++++++++++++++++ lib/alloc/arena_alloc.c | 77 +++++++++++++++++++++++++++++++++++++++++++++ lib/alloc/arena_free.c | 20 ++++++++++++ lib/alloc/arena_zero.c | 14 +++++++++ lib/alloc/bufalloc_noterm.c | 14 +-------- 7 files changed, 151 insertions(+), 15 deletions(-) create mode 100644 include/_attrs.h create mode 100644 lib/alloc/arena_alloc.c create mode 100644 lib/alloc/arena_free.c create mode 100644 lib/alloc/arena_zero.c 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 +#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 + +#include +#include +#include + +#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 + +#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_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 -#if __has_include() -# include -# 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 #include #include "alloc.h" -- cgit v1.2.3