Arena allocators
Tales of memory management in C
Programming in low level languages such as C, requires for the programmer to manage it's memory, preferably without causing memory leaks and definitely without use-after-free. This is easier said than done, since it is very easy to forget to some free after doing a malloc. This is further aggravated when allocating and de-allocating large and complex data structures. The traditional way of doing it is to do everything manually, pay close attention, and have a free for each allocation. This approach quickly leads to errors, use-after-free and madness. However, there is an alternative approach that works for most cases and simplifies memory management a whole lot. This new approach uses Arenas.
Arenas save the day
When programming, you may have observed that there are for the most part two forms of memory allocation on display in every program:
-
Transient memory allocations
-
Persistent memory allocations
Transient memory allocations are those that last very little, as when making a temporary string or resource that will be freed shortly (e.g building a formatted string to pass to another function). Persistent memory allocations are those which last very long, and usually exhibit locality in allocation and de-allocation (that is, they are malloc'ed and free'd in the same place). We shall see how arenas exploit the locality of the latter. Here is an example interface of an arena allocator:
typedef struct Arena { ... } Arena;
void arena_init(Arena *); // init arena
void *arena_alloc(Arena *arena, size_t sz); // allocate memory
void arena_free(Arena *arena); // free all allocated memory
The interface is actually very simple and straightforward to implement. The `Arena` structure keeps a record of all the allocations and allows for freeing everything at the end. This approach also has other benefits. Since we don't need to free memory inidividually, there is no complex system to keep track of free'd chunks, and we can instead allocate large chunks of memory and serve it on demand with very little overhead. Using arenas is also very ergonomic, specially when constructing large data structures that will be freed all at once. One can initialize the arena, get memory on demand via `arena_alloc` and then, when we are done, use one `arena_free` call to free everything in one go.
My implementation of an Arena allocator
Here is my implementation for an Arena allocator that I use in some of my projects. It uses a linked list of `ArenaRegion` that contain every allocated region and can be then free by a simple forward run over the list. For initialization, one can use the idiom `Arena arena = {0}`, which rocks ;). I recommend that you implement your own and tune the interface to your liking.
One bad thing about arenas with this kind of implementation, is that since memory is given out contiguously and in a very predictable manner, it increases the risk of exploitability in the event of an over/under flow as a result of programmer error. This could be mitigated by using the standard memory allocation schema combined with tracking of allocated memory, wich would fix this problem but increase overhead. As always, it is a matter of trade-offs.
/*
* OPTIONS
* static implementation - arena_static
*
* INIT : clear the Arena to 0
* DROP : you can discard the arena when it is empty
*
* FUNCTIONS
* b32x arena_empty(Arena *);
* check if arena is empty
*
* void *arena_alloc(Arena *, u32x);
* allocate chunk of memory
*
* void *arena_zalloc(Arena *, u32x)
* allocate chunk of zero'ed memory
*
* void arena_freeall(Arena *);
* free all memory (the arena will be empty)
*
* void *arena_dup(Arena *, const void *, u32x)
* duplicate memory region
*
* CONSTRAINTS
* all arena_xxx functions for a `arena` must be used by a single thread
*
* REFERENCES
* tsoding - arena data structures
* Adam H Smith - for inspiration to adopt arenas
*/
#ifndef qanta_arena_h
#define qanta_arena_h
#include "types.h"
struct ArenaRegion;
typedef struct {
struct ArenaRegion *first, *last;
} Arena;
# ifdef arena_static
# define arena_decl local_unused
# else
# define arena_decl
# endif
#define arena_empty(_a) ((b32x)!(_a)->first)
arena_decl void *arena_alloc(Arena *, u32x);
arena_decl void *arena_zalloc(Arena *, u32x);
arena_decl void arena_freeall(Arena *);
arena_decl void *arena_dup(Arena *, const void *, u32x);
arena_decl u32x arena_st_alloc(void);
arena_decl u32x arena_st_nalive(void);
#endif /* qanta_arena_h */
# if defined(arena_impl)
#include "util.h"
#include <pthread.h>
#include <sys/mman.h>
#include <errno.h>
#include <memory.h>
local struct {
pthread_mutex_t mt;
volatile u32x nalive, alloc;
} qanta_ar_stats_ = {
.mt = PTHREAD_MUTEX_INITIALIZER,
.nalive = 0,
.alloc = 0,
};
struct ArenaRegion {
struct ArenaRegion *next; // this pointer guarantess good alignment
u32 off; // offset of next free byte
u32 sz; // size in bytes of allocation
};
local struct ArenaRegion *
arena_new_region_(void *prev, u32x sz)
{
struct ArenaRegion *region;
pthread_mutex_lock(&qanta_ar_stats_.mt);
++qanta_ar_stats_.nalive;
qanta_ar_stats_.alloc += sz;
pthread_mutex_unlock(&qanta_ar_stats_.mt);
sz = 4096 > sz + sizeof(struct ArenaRegion)
? 4096
: (sz + sizeof(struct ArenaRegion) + sizeof(void *) - 1) /
sizeof(void *) * sizeof(void *);
region = mmap(prev, sz, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANON, -1, 0);
if (region == MAP_FAILED)
panic("mmap %u: %s", sz, strerror(errno));
region->next = NULL;
// NOTE: sizeof Region is properly aligned
region->off = sizeof(struct ArenaRegion);
region->sz = sz;
return region;
}
local void
arena_free_region_(struct ArenaRegion *region)
{
pthread_mutex_lock(&qanta_ar_stats_.mt);
--qanta_ar_stats_.nalive;
qanta_ar_stats_.alloc -= region->sz;
pthread_mutex_unlock(&qanta_ar_stats_.mt);
if (munmap(region, region->sz) == -1)
panic("munmap %u: %s", region->sz, strerror(errno));
}
arena_decl void *
arena_alloc(Arena *arena, u32x sz)
/* allocate memory
* arena target arena
* sz memory size
* returns the requested pointer
*
* memory will be aligned properly for any data-type
*
* XXX this function ALWAYS succeeds, else the program crashes, if necessary,
* a new interface should be added in the future
*/
{
void *ret;
if (sz <= 0)
return NULL;
/* align `sz`, hence keeping `off` aligned too */
if (sz % sizeof(void *))
sz += sizeof(void *) - sz % sizeof(void *);
if (!arena->first) {
arena->first = arena->last = arena_new_region_(0, sz);
} else {
/* if this arena is not sufficient, create new one with size at
* least sz, to guarantee it will have space for sz.
* XXX we should keep the arena with the most space at last,
* instead of the new one.
*/
if (arena->last->sz - arena->last->off < sz) {
arena->last->next = arena_new_region_((void *) arena->last, sz);
arena->last = arena->last->next;
}
}
ret = (u8*) arena->last + arena->last->off;
arena->last->off += sz;
return ret;
}
arena_decl void *
arena_zalloc(Arena *arena, u32x sz)
/* allocate zero'ed memory
* arena target arena
* sz memory size
* returns the requested pointer
*
* memory will be aligned properly for any data-type
*
* XXX this function ALWAYS succeeds, else the program crashes, if necessary,
* a new interface should be added in the future
*/
{
void *ret = arena_alloc(arena, sz);
memset(ret, 0, sz);
return ret;
}
arena_decl void
arena_freeall(Arena *arena)
/* free all memory
* arena target arena
*/
{
struct ArenaRegion *region, *next;
region = arena->first;
arena->first = arena->last = NULL;
while (region) {
next = region->next;
arena_free_region_(region);
region = next;
}
}
arena_decl void *
arena_dup(Arena *arena, const void *mem, u32x sz)
/* duplicate memory
* arena target arena
* mem memory region
* sz size of memory
*/
{
/* [ never found this return useful until now XD ] */
return memcpy(arena_alloc(arena, sz), mem, sz);
}
arena_decl u32x
arena_st_nalive(void)
{
u32x n;
pthread_mutex_lock(&qanta_ar_stats_.mt);
n = qanta_ar_stats_.nalive;
pthread_mutex_unlock(&qanta_ar_stats_.mt);
return n;
}
arena_decl u32x
arena_st_alloc(void)
{
u32x n;
pthread_mutex_lock(&qanta_ar_stats_.mt);
n = qanta_ar_stats_.alloc;
pthread_mutex_unlock(&qanta_ar_stats_.mt);
return n;
}
# undef arena_impl
#endif /* arena_impl */
Izan, 01 Jan 2025, LLU blog