From cbe2c473c9aee71f5f770dc7f41973d2ef4c273c Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Mon, 19 Jun 2023 16:58:24 -0400 Subject: alloc: Implement an arena for flexible structs --- src/alloc.c | 118 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/alloc.h | 92 +++++++++++++++++++++++++++++++++++++++++++++ tests/alloc.c | 14 ++++++- 3 files changed, 223 insertions(+), 1 deletion(-) diff --git a/src/alloc.c b/src/alloc.c index b437975..a6910ce 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -157,5 +157,123 @@ void arena_destroy(struct arena *arena) { for (size_t i = 0; i < arena->nslabs; ++i) { free(arena->slabs[i]); } + free(arena->slabs); sanitize_uninit(arena); } + +void varena_init(struct varena *varena, size_t align, size_t min, size_t offset, size_t size) { + varena->align = align; + varena->offset = offset; + varena->size = size; + varena->narenas = 0; + varena->arenas = NULL; + + // The smallest size class is at least as many as fit in the smallest + // aligned allocation size + size_t min_count = (flex_size(align, min, offset, size, 1) - offset + size - 1) / size; + varena->shift = bit_width(min_count - 1); +} + +/** Get the size class for the given array length. */ +static size_t varena_size_class(struct varena *varena, size_t count) { + // Since powers of two are common array lengths, make them the + // (inclusive) upper bound for each size class + return bit_width((count - !!count) >> varena->shift); +} + +/** Get the exact size of a flexible struct. */ +static size_t varena_exact_size(const struct varena *varena, size_t count) { + return flex_size(varena->align, 0, varena->offset, varena->size, count); +} + +/** Get the arena for the given array length. */ +static struct arena *varena_get(struct varena *varena, size_t count) { + size_t i = varena_size_class(varena, count); + + if (i >= varena->narenas) { + size_t narenas = i + 1; + struct arena *arenas = realloc(varena->arenas, sizeof_array(struct arena, narenas)); + if (!arenas) { + return NULL; + } + + for (size_t j = varena->narenas; j < narenas; ++j) { + size_t shift = j + varena->shift; + size_t size = varena_exact_size(varena, (size_t)1 << shift); + arena_init(&arenas[j], varena->align, size); + } + + varena->narenas = narenas; + varena->arenas = arenas; + } + + return &varena->arenas[i]; +} + +void *varena_alloc(struct varena *varena, size_t count) { + struct arena *arena = varena_get(varena, count); + if (!arena) { + return NULL; + } + + void *ret = arena_alloc(arena); + if (!ret) { + return NULL; + } + + // Tell the sanitizers the exact size of the allocated struct + sanitize_free(ret, arena->size); + sanitize_alloc(ret, varena_exact_size(varena, count)); + + return ret; +} + +void *varena_realloc(struct varena *varena, void *ptr, size_t old_count, size_t new_count) { + struct arena *new_arena = varena_get(varena, new_count); + struct arena *old_arena = varena_get(varena, old_count); + if (!new_arena) { + return NULL; + } + + size_t new_exact_size = varena_exact_size(varena, new_count); + size_t old_exact_size = varena_exact_size(varena, old_count); + + if (new_arena == old_arena) { + if (new_count < old_count) { + sanitize_free((char *)ptr + new_exact_size, old_exact_size - new_exact_size); + } else if (new_count > old_count) { + sanitize_alloc((char *)ptr + old_exact_size, new_exact_size - old_exact_size); + } + return ptr; + } + + void *ret = arena_alloc(new_arena); + if (!ret) { + return NULL; + } + + size_t old_size = old_arena->size; + sanitize_alloc((char *)ptr + old_exact_size, old_size - old_exact_size); + + size_t new_size = new_arena->size; + size_t min_size = new_size < old_size ? new_size : old_size; + memcpy(ret, ptr, min_size); + + arena_free(old_arena, ptr); + sanitize_free((char *)ret + new_exact_size, new_size - new_exact_size); + + return ret; +} + +void varena_free(struct varena *varena, void *ptr, size_t count) { + struct arena *arena = varena_get(varena, count); + arena_free(arena, ptr); +} + +void varena_destroy(struct varena *varena) { + for (size_t i = 0; i < varena->narenas; ++i) { + arena_destroy(&varena->arenas[i]); + } + free(varena->arenas); + sanitize_uninit(varena); +} diff --git a/src/alloc.h b/src/alloc.h index 65edb92..c2ea09b 100644 --- a/src/alloc.h +++ b/src/alloc.h @@ -190,4 +190,96 @@ void arena_free(struct arena *arena, void *ptr); */ void arena_destroy(struct arena *arena); +/** + * An arena allocator for flexibly-sized types. + */ +struct varena { + /** The alignment of the struct. */ + size_t align; + /** The offset of the flexible array. */ + size_t offset; + /** The size of the flexible array elements. */ + size_t size; + /** Shift amount for the smallest size class. */ + size_t shift; + /** The number of arenas of different sizes. */ + size_t narenas; + /** The array of differently-sized arenas. */ + struct arena *arenas; +}; + +/** + * Initialize a varena for a struct with the given layout. + * + * @param varena + * The varena to initialize. + * @param align + * alignof(type) + * @param min + * sizeof(type) + * @param offset + * offsetof(type, flexible_array) + * @param size + * sizeof(flexible_array[i]) + */ +void varena_init(struct varena *varena, size_t align, size_t min, size_t offset, size_t size); + +/** + * Initialize a varena for the given type and flexible array. + * + * @param varena + * The varena to initialize. + * @param type + * A struct type containing a flexible array. + * @param member + * The name of the flexible array member. + */ +#define VARENA_INIT(varena, type, member) \ + varena_init(varena, alignof(type), sizeof(type), offsetof(type, member), sizeof_member(type, member[0])) + +/** + * Arena-allocate a flexible struct. + * + * @param varena + * The varena to allocate from. + * @param count + * The length of the flexible array. + * @return + * The allocated struct, or NULL on failure. + */ +void *varena_alloc(struct varena *varena, size_t count); + +/** + * Resize a flexible struct. + * + * @param varena + * The varena to allocate from. + * @param ptr + * The object to resize. + * @param old_count + * The old array lenth. + * @param new_count + * The new array length. + * @return + * The resized struct, or NULL on failure. + */ +void *varena_realloc(struct varena *varena, void *ptr, size_t old_count, size_t new_count); + +/** + * Free an arena-allocated flexible struct. + * + * @param varena + * The that allocated the object. + * @param ptr + * The object to free. + * @param count + * The length of the flexible array. + */ +void varena_free(struct varena *varena, void *ptr, size_t count); + +/** + * Destroy a varena, freeing all allocations. + */ +void varena_destroy(struct varena *varena); + #endif // BFS_ALLOC_H diff --git a/tests/alloc.c b/tests/alloc.c index 91b1b43..9e6e892 100644 --- a/tests/alloc.c +++ b/tests/alloc.c @@ -8,7 +8,7 @@ int main(void) { // Check sizeof_flex() struct flexible { - alignas(64) int foo; + alignas(64) int foo[8]; int bar[]; }; bfs_verify(sizeof_flex(struct flexible, bar, 0) >= sizeof(struct flexible)); @@ -20,5 +20,17 @@ int main(void) { // Doesn't happen in typical ABIs bfs_verify(flex_size(8, 16, 4, 4, 1) == 16); + // varena tests + struct varena varena; + VARENA_INIT(&varena, struct flexible, bar); + + for (size_t i = 0; i < 256; ++i) { + bfs_verify(varena_alloc(&varena, i)); + struct arena *arena = &varena.arenas[varena.narenas - 1]; + bfs_verify(arena->size >= sizeof_flex(struct flexible, bar, i)); + } + + varena_destroy(&varena); + return EXIT_SUCCESS; } -- cgit v1.2.3