This is a follow-up to: An Arena/Bump Allocator in C.
LOC: 234. (Not including the sample tests, still quite small and manageable.)
The allocator uses C99, but sample tests use C11's alignof and alignas.
What has changed:
The internal memory pool no longer needs to be allocated on the heap by the allocator. It can be one of the following:
- A statically-allocated pool specified by the client.
- A dynamically-allocated pool specified by the client.
- An automatically-allocated pool specified by the client.
A null pointer is also entertained, in which case a memory pool of size
DEFAULT_BUF_CAPKiB is allocated dynamically by the allocator.arena_new()now also takes an initial size.Pointers returned by the allocator are now stable. The allocator starts with a single memory pool, and adds more when needed. I have opted for an array of pointers instead of a linked list for this.
The allocator now returns aligned memory. The alignment is passed as an argument to the allocation functions.
Documentation and missing overflow checks have been added.
If compiled with
-DDEBUG, the padding for alignment (if any) and the subsequent bytes after a user block are set to0xA5. (The value was taken from Wikipedia, which stated that FreeBSD's PHK malloc uses it for debugging purposes.)
API Additions:
arena_realloc()- Extends the last allocation made in place. Can be used to shrink, grow, or delete the last allocation.arena_reset()- Simply sets the count member of all the memory pools to 0.arena_resize()- Adds a new memory pool to the exisiting arena passed in as an argument.arena_allocarray()- Equivalent to the call:arena_alloc(arena, alignment, nmemb * size);But unlike
arena_alloc(), fails safely where the multiplication overflows.
Code:
arena.h:
#ifndef ARENA_H
#define ARENA_H 1
/* *INDENT-OFF* */
#if defined(__GNUC__) || defined(__clang__) || defined(__INTEL_LLVM_COMPILER)
#define ATTRIB_CONST __attribute__((const))
#define ATTRIB_MALLOC __attribute__((malloc))
#define ATTRIB_NONNULL __attribute__((nonnull))
#define ATTRIB_NONNULLEX(...) __attribute__((nonnull(__VA_ARGS__)))
#define ATTRIB_INLINE __attribute__((always_inline))
#else
#define ATTRIB_CONST /**/
#define ATTRIB_MALLOC /**/
#define ATTRIB_NONNULL /**/
#define ATTRIB_NONNULLEX(...) /**/
#define ATTRIB_INLINE /**/
#endif
/* *INDENT-ON* */
#define DEFAULT_BUF_CAP 256 * (size_t)1024
#include <stddef.h>
/* Bump allocator arena. */
typedef struct arena Arena;
/* Returns a new arena with the specified `capacity`.
* If `capacity` is 0, a default size of `DEFAULT_BUF_CAP` is used.
*
* On allocation failure, or if `buf` is a non-null pointer and `capacity` is 0,
* returns `nullptr`.
*
* Passing a `buf` that is smaller than the specified `capacity` would invoke
* undefined behavior. */
Arena *arena_new(void *buf, size_t capacity);
/* Destroys `arena`, freeing all the memory associated with it.
*
* Any pointer allocated by this arena is invalidated after this call. */
void arena_destroy(Arena *arena) ATTRIB_NONNULL;
/* Resets `arena`, invalidating all existing allocations.
*
* Whilst existing pointers allocated by this arena are valid after this call
* as far as the language is concerned, they should be considered invalid as
* using them * would invoke Undefined Behavior. */
void arena_reset(Arena *arena) ATTRIB_NONNULL;
/* Allocates a pointer from `arena`.
*
* The allocated pointer is at least aligned to `alignment`.
*
* `alignment` must be a power of 2.
*
* `size` must be a multiple of `alignment`.
*
* If a request can not be entertained, i.e. would overflow, or `arena` is full,
* the function returns `nullptr`. The function also returns a `nullptr` if the
* requested `size` is 0 or if `alignment` is not a power of 2, or if `size` is
* not a multiple of `alignment`.
*
* Any allocations made prior to this call are not freed on failure, and remain
* valid until the arena is either reset or destroyed.
*/
void *arena_alloc(Arena *arena, size_t alignment, size_t size)
ATTRIB_MALLOC ATTRIB_NONNULL;
/* Adds a new memory pool to the existing arena `arena`.
* If `capacity` is 0, a default size of `DEFAULT_BUF_CAP` is used.
*
* On allocation failure, or if `buf` is a non-null pointer and `capacity` is 0,
* returns `nullptr`.
*
* Any allocations made prior to this call are not freed on failure, and remain
* valid until the arena is either reset or destroyed.
* Passing a `buf` that is smaller than the specified `capacity`, or passing an
* `arena` that was not returned by `arena_new()` would invoke Undefined Behavior. */
Arena *arena_resize(Arena *restrict arena, void *restrict buf, size_t capacity)
ATTRIB_NONNULLEX(1);
/* Allocates a pointer from `arena` large enough for an array of `nmemb`
* elements, each of which is `size` bytes. It is equivalent to the call:
*
* arena_alloc(arena, alignment, nmemb * size);
*
* However, unlike that `arena_alloc()` call, `arena_allocarray()` fails safely
* in the case where the multiplication would overflow. If such an overflow
* occurs, `arena_allocarray()` returns `nullptr`.
*
* Has the same requirements for `size` and `alignment` as `arena_alloc()`, and
* returns `nullptr` for all the cases `arena_alloc()` does.
*
* Any allocations made prior to this call are not freed on failure, and remain
* valid until the arena is either reset or destroyed.
*/
void *arena_allocarray(Arena *arena,
size_t alignment,
size_t nmemb,
size_t size) ATTRIB_MALLOC ATTRIB_NONNULL;
/* Extends the last allocation in place.
*
* If `size` is 0, the last allocation is deleted. Else if it is less than the
* last allocated size, it is shrinked to `size`. Else, it is expanded to `size`
* bytes.
*
* Returns `false` if the request can not be entertained, i.e out of memory.
* Else it returns `true`.
*/
bool arena_realloc(Arena *arena, size_t size) ATTRIB_NONNULL;
#endif /* ARENA_H */
arena.c:
#include "arena.h"
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
/* *INDENT-OFF* */
/* In C2X/C23 or later, nullptr is a keyword. */
/* Patch up C18 (__STDC_VERSION__ == 201710L) and earlier versions. */
#if !defined(__STDC_VERSION__) || __STDC_VERSION__ <= 201710L
#define nullptr ((void *)0)
#endif
#define INITIAL_MPOOL_COUNT 2
#ifdef DEBUG
#include <string.h>
#define D(x) x
#else
#define D(x) (void) 0
#endif
/* *INDENT-ON* */
typedef struct pool {
size_t count;
size_t capacity;
bool is_heap_alloc;
uint8_t *buf;
} M_Pool;
typedef struct arena {
size_t count;
size_t capacity;
size_t current;
size_t last_alloc_size;
M_Pool *pools[];
} Arena;
ATTRIB_INLINE ATTRIB_CONST static inline bool is_power_of_two(uintptr_t x)
{
return (x & (x - 1)) == 0;
}
ATTRIB_INLINE ATTRIB_CONST static inline bool is_multiple_of(size_t a, size_t b)
{
return a / b * b == a;
}
static M_Pool *pool_new(void *buf, size_t capacity)
{
if (capacity == 0) {
if (buf != nullptr) {
return nullptr;
}
capacity = DEFAULT_BUF_CAP;
}
M_Pool *const pool = calloc(1, sizeof *pool);
/* *INDENT-OFF* */
if (pool != nullptr) {
*pool = (M_Pool) {
.capacity = capacity,
.is_heap_alloc = buf == nullptr,
.buf = buf ? buf : calloc(1, capacity),
};
}
/* *INDENT-ON* */
return pool;
}
Arena *arena_new(void *buf, size_t capacity)
{
Arena *const arena = calloc(1,
sizeof *arena + (INITIAL_MPOOL_COUNT * sizeof arena->pools[0]));
if (arena == nullptr) {
return nullptr;
}
arena->capacity = INITIAL_MPOOL_COUNT;
arena->count = 1;
arena->current = 1;
arena->pools[0] = pool_new(buf, capacity);
if (arena->pools[0] == nullptr) {
free(arena);
return nullptr;
}
return arena;
}
void *arena_alloc(Arena *arena, size_t alignment, size_t size)
{
if (size == 0
|| (alignment != 1 && !is_power_of_two(alignment))
|| !is_multiple_of(size, alignment)) {
return nullptr;
}
M_Pool *curr_pool = arena->pools[arena->current - 1];
uint8_t *const p = curr_pool->buf + curr_pool->count;
const uintptr_t original = ((uintptr_t) p);
if (original > UINTPTR_MAX - alignment) {
return nullptr;
}
const uintptr_t remain = original & (alignment - 1);
const uintptr_t aligned =
remain != 0 ? original + (alignment - remain) : original;
const size_t offset = aligned - original;
if (size > SIZE_MAX - offset) {
return nullptr;
}
size += offset;
if (size > curr_pool->capacity - curr_pool->count) {
return nullptr;
}
/* Set the optional padding for alignment immediately before a user block,
* and the bytes immediately following such a block to non-zero.
* The intent is to trigger OBOB failures to inappropiate app use of
* strlen()/strnlen(), which keep forging ahead till encountering ascii NUL. */
D(
/* 0xA5 is used in FreeBSD's PHK malloc for debugging purposes. */
if (remain) {
memset(p + (alignment - remain), 0xA5, alignment - remain);}
);
curr_pool->count += size;
D(memset(curr_pool->buf + curr_pool->count, 0xA5,
curr_pool->capacity - curr_pool->count));
arena->last_alloc_size = size;
/* Equal to "aligned", but preserves provenance. */
return p + offset;
}
void *arena_allocarray(Arena *arena,
size_t alignment,
size_t nmemb,
size_t size)
{
if (nmemb != 0 && size > SIZE_MAX / nmemb) {
return nullptr;
}
return arena_alloc(arena, alignment, nmemb * size);
}
bool arena_realloc(Arena *arena, size_t size)
{
if (size == arena->last_alloc_size) {
return true;
}
M_Pool *const curr_pool = arena->pools[arena->current - 1];
if (size == 0) {
/* Delete allocation. */
curr_pool->count -= arena->last_alloc_size;
arena->last_alloc_size = size;
return true;
}
if (size < arena->last_alloc_size) {
/* Shrink allocation. */
curr_pool->count -= arena->last_alloc_size - size;
arena->last_alloc_size = size;
return true;
}
if (size > (curr_pool->capacity - curr_pool->count)) {
return false;
}
/* Expand allocation. */
curr_pool->count += size - arena->last_alloc_size;
arena->last_alloc_size = size;
return true;
}
Arena *arena_resize(Arena *restrict arena, void *restrict buf, size_t capacity)
{
if (arena->count >= arena->capacity) {
arena->capacity *= 2;
Arena *tmp = realloc(arena,
sizeof *tmp + (arena->capacity * sizeof arena->pools[0]));
if (tmp == nullptr) {
return nullptr;
}
arena = tmp;
}
M_Pool *const new_pool = pool_new(buf, capacity);
if (new_pool == nullptr) {
return nullptr;
}
arena->pools[arena->count++] = new_pool;
++arena->current;
return arena;
}
void arena_destroy(Arena *arena)
{
for (size_t i = 0; i < arena->count; ++i) {
if (arena->pools[i]->is_heap_alloc) {
free(arena->pools[i]->buf);
}
free(arena->pools[i]);
}
free(arena);
}
void arena_reset(Arena *arena)
{
for (size_t i = 0; i < arena->count; ++i) {
arena->pools[i]->count = 0;
}
arena->current = 1;
}
#ifdef TEST_MAIN
#include <assert.h>
#include <stdalign.h>
#include <stdio.h>
static void test_arena_allocarray(void)
{
Arena *const arena = arena_new(nullptr, 100);
assert(arena && "error: arena_new(): failed to allocate memory.\n");
const int *const nums = arena_allocarray(arena, alignof (int), 10, sizeof *nums);
assert(nums && "error: arena_allocarray(): failed to allocate memory.\n");
arena_destroy(arena);
}
static void test_arena_realloc(void)
{
Arena *const arena = arena_new(nullptr, 100);
assert(arena && "error: arena_new(): failed to allocate memory.\n");
assert(arena_alloc(arena, 1, 10));
assert(arena->pools[0]->count == 10 && arena->last_alloc_size == 10);
/* Test expansion. */
assert(arena_realloc(arena, 20));
assert(arena->pools[0]->count == 20 && arena->last_alloc_size == 20);
/* Test shrinking. */
assert(arena_realloc(arena, 15));
assert(arena->pools[0]->count == 15 && arena->last_alloc_size == 15);
/* Test deletion. */
assert(arena_realloc(arena, 0));
assert(arena->pools[0]->count == 0 && arena->last_alloc_size == 0);
arena_destroy(arena);
}
ATTRIB_INLINE ATTRIB_CONST static inline bool is_aligned(const void *ptr,
size_t byte_count)
{
return (uintptr_t) ptr % (byte_count) == 0;
}
static void test_debug_magic_bytes(void)
{
Arena *const arena = arena_new(nullptr, 100);
assert(arena && "error: arena_new(): failed to allocate memory.\n");
assert(arena_alloc(arena, 1, 95));
uint8_t *const curr_pool = arena->pools[0]->buf;
assert(curr_pool[96] == 0xA5 && curr_pool[97] == 0xA5
&& curr_pool[98] == 0xA5 && curr_pool[99] == 0xA5);
arena_destroy(arena);
}
static void test_alignment(void)
{
Arena *const arena = arena_new(nullptr, 1000);
assert(arena && "error: arena_new(): failed to allocate memory.\n");
const int *const a = arena_alloc(arena, alignof (int), 5 * sizeof *a);
const double *const b = arena_alloc(arena, alignof (double), 2 * sizeof *b);
const char *const c = arena_alloc(arena, 1, 10);
const short *const d = arena_alloc(arena, alignof (short), 5 * sizeof *d);
assert(a && is_aligned(a, alignof (int)));
assert(b && is_aligned(b, alignof (double)));
assert(c && is_aligned(c, 1));
assert(d && is_aligned(d, alignof (short)));
arena_destroy(arena);
}
static void test_growth(void)
{
Arena *arena = arena_new(nullptr, 1000);
assert(arena && "error: arena_new(): failed to allocate memory.\n");
const char *c = arena_alloc(arena, 1, 10000);
assert(!c);
arena = arena_resize(arena, nullptr, 10000);
assert(arena->current == 2 && arena->count == 2);
assert(arena && "error: arena_new(): failed to allocate memory.\n");
c = arena_alloc(arena, 1, 10000);
assert(c);
arena_reset(arena);
assert(arena->current == 1 && arena->count == 2);
arena_destroy(arena);
}
static void test_failure(void)
{
assert(arena_new(stderr, 0) == nullptr);
Arena *const arena = arena_new(nullptr, 100);
assert(arena && "error: arena_new(): failed to allocate memory.\n");
assert(arena_alloc(arena, 1, 112) == nullptr);
arena_reset(arena);
assert(arena_alloc(arena, 16, 80));
arena_destroy(arena);
}
static void test_allocation(Arena * arena)
{
assert(arena && "error: arena_new(): failed to allocate memory.\n");
char *const c = arena_alloc(arena, 1, 5);
int *const i = arena_alloc(arena, alignof (int), sizeof *i);
double *const d = arena_alloc(arena, alignof (double), sizeof *d);
assert(c && i && d && "error: arena_alloc(): failed to allocate memory.\n");
*c = 'A';
*i = 1;
*d = 20103.212;
printf("&c (char *): %p, c: %c\n"
"&i (int *): %p, i: %d\n"
"&d (double *): %p, d: %lf\n",
(void *) c, *c, (void *) i, *i, (void *) d, *d);
arena_destroy(arena);
}
static void test_client_static_arena(void)
{
static uint8_t alignas (max_align_t) static_pool[BUFSIZ];
Arena *const static_arena = arena_new(static_pool, sizeof static_pool);
puts("---- Using a statically-allocated arena ----");
test_allocation(static_arena);
}
static void test_client_automatic_arena(void)
{
uint8_t alignas (max_align_t) thread_local_pool[BUFSIZ];
Arena *const thread_local_arena =
arena_new(thread_local_pool, sizeof thread_local_pool);
puts("---- Using an automatically-allocated arena ----");
test_allocation(thread_local_arena);
}
static void test_client_dynamic_arena(void)
{
uint8_t *const client_heap_pool = malloc(100 * (size_t) 1024);
assert(client_heap_pool && "error: failed to allocate client_heap_pool.\n");
Arena *const client_heap_arena =
arena_new(client_heap_pool, 100 * (size_t) 1024);
puts("---- Using a dynamically-allocated arena ----");
test_allocation(client_heap_arena);
free(client_heap_pool);
}
static void test_lib_dynamic_arena(void)
{
Arena *const lib_arena = arena_new(nullptr, 100);
puts("---- Using the library's internal arena ----");
test_allocation(lib_arena);
}
int main(void)
{
test_lib_dynamic_arena();
test_client_dynamic_arena();
test_client_automatic_arena();
test_client_static_arena();
test_arena_allocarray();
test_arena_realloc();
test_failure();
test_alignment();
test_growth();
D(test_debug_magic_bytes());
return EXIT_SUCCESS;
}
#undef ATTRIB_CONST
#undef ATTRIB_MALLOC
#undef ATTRIB_NONNULL
#undef ATTRIB_NONNULLEX
#undef ATTRIB_INLINE
#undef nullptr
#undef DEFAULT_BUF_CAP
#undef INITIAL_MPOOL_COUNT
#undef DEBUG
#undef D
#endif /* TEST_MAIN */
Makefile:
CC := gcc-13
CFLAGS += -std=c2x
CFLAGS += -fPIC
CFLAGS += -Wall
CFLAGS += -Wextra
CFLAGS += -Werror
CFLAGS += -Wwrite-strings
CFLAGS += -Wno-unused-variable
CFLAGS += -Wno-parentheses
CFLAGS += -Wpedantic
CFLAGS += -Warray-bounds
CFLAGS += -Wno-unused-function
CFLAGS += -Wstrict-prototypes
CFLAGS += -Wconversion
CFLAGS += -Wdeprecated
CFLAGS += -DTEST_MAIN
TARGET := arena
release: CFLAGS += -O2 -s
release: $(TARGET)
# To run under valgrind, remove the sanitizer.
debug: CFLAGS += -DDEBUG -g3 -ggdb -fanalyzer -fsanitize=address,leak,undefined
debug: $(TARGET)
clean:
$(RM) $(TARGET)
.PHONY: release debug clean
.DELETE_ON_ERROR:
Or clone this repository: An Arena Allocator in C.
Review Request:
Have I introduced any new bugs (memory leaks, undefined/implementation-defined) behavior in the code?
Is the documentation lacking at any place?
Are my overflow checks correct?
Naming.
Anything, everything.
Valgrind's output:
==9152== Memcheck, a memory error detector
==9152== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==9152== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==9152== Command: ./arena
==9152==
---- Using the library's internal arena ----
&c (char *): 0x4a9b110, c: A
&i (int *): 0x4a9b118, i: 1
&d (double *): 0x4a9b120, d: 20103.212000
---- Using a dynamically-allocated arena ----
&c (char *): 0x4a9c200, c: A
&i (int *): 0x4a9c208, i: 1
&d (double *): 0x4a9c210, d: 20103.212000
---- Using an automatically-allocated arena ----
&c (char *): 0x1ffeffdde0, c: A
&i (int *): 0x1ffeffdde8, i: 1
&d (double *): 0x1ffeffddf0, d: 20103.212000
---- Using a statically-allocated arena ----
&c (char *): 0x10c020, c: A
&i (int *): 0x10c028, i: 1
&d (double *): 0x10c030, d: 20103.212000
==9152==
==9152== HEAP SUMMARY:
==9152== in use at exit: 0 bytes in 0 blocks
==9152== total heap usage: 29 allocs, 29 frees, 119,696 bytes allocated
==9152==
==9152== All heap blocks were freed -- no leaks are possible
==9152==
==9152== For lists of detected and suppressed errors, rerun with: -s
==9152== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
