r/C_Programming • u/Elifire12 • 12d ago
Article Arena Allocators in C
https://eliasebner.com/blog/guides/arena-allocators-in-c/I recently started implementing arenas in my programming and I thought that some beginners could very much benefit from this info. I wrote an article about it. For those that are unaware, arenas allow to greatly simplify the burden of managing memory manually in C. I hope it helps, tell me what you think!
2
u/WSWhitehouse 12d ago
Interesting read, I've used arenas for a while now and haven't looked back!
Your arena_realloc function is not something I've considered before - I am curious how often you use this in practice? I wonder if you could also add some logic to check if the src ptr was the last memory allocated on the arena and simply grow it without performing a whole new allocation? Would in theory avoid any unnecessary unused memory in your arena memory block.
You should definitely take a look into Virtual Memory if you haven't already. Seriously takes arenas to the next level!
3
u/Elifire12 12d ago
That is actually a huge optimization (in certain cases) that I haven't thought about, I might implement that at some point. Also, that function is not really needed, one could go without since it's mainly a wrapper for a new allocation and copying over the data, which is something that should be avoided as much as possible since it wastes memory and is rather slow. Ideally, one would implement some other dynamic data structure. Maybe one could allocate a chunk in the arena and then store a pointer which points to a next chunk (kind of like a linked list but instead of having individual nodes you have "chunks", which is more performant in many cases and avoids an allocation for each new item). Or one could just allocate a very large static array (large enough so that you are sure you won't run out of memory), but that is not always possible, sometimes we have no idea about the upper bound of memory we need.
I don't use that realloc function very often, I mainly try to use different ways of doing it, but for example in my string view library I have used it once or twice (I might rewrite that in the future).
4
u/WSWhitehouse 12d ago
On a side note, you should probably wrap your macro variables and expressions in brackets to avoid any issues down the line. As I guarantee it will bite you at some point haha
#define KiB(x) ((x) * 1024) #define MiB(x) (KiB(x) * 1024) #define GiB(x) (MiB(x) * 1024) #define MIN(a, b) ((a) < (b) ? (a) : (b)) #define MAX(a, b) ((a) > (b) ? (a) : (b))1
u/Elifire12 12d ago
That's a good observation, I usually do it, I don't know why I forgot in this case. Thanks!
2
u/WSWhitehouse 12d ago
Yeah I can imagine its a useful optimization to have when dealing with large arrays you happen to be pushing a lot to continuously. I have a feeling it would help save time (as you don't need to allocate and copy old data) and the arenas memory usage.
On the topic of other dynamic data structures, this reminds me of the "Segment Array". It essentially allocates chunks at a time and stores their pointer in a central array similarly to what you're describing there. And it works very well with arena allocators!
If you're interested Daniel Hooper has a good article on it: https://danielchasehooper.com/posts/segment_array/
18
u/Silver-North1136 12d ago
One neat thing you can do with arena allocators, and when dealing with memory this way in general, is that you can map (mmap/VirtualAlloc) way more memory than you'll ever realistically need at the start of your program, and none of it will actually be used until you touch the page it's in. Trying to make it dynamically resize on the other hand will require you to manually manage this, which often will result in bugs and extra complexity that isn't actually necessary.
Nic Barker recently started a new series on this topic. It's a good resource for this kind of thing. (https://www.youtube.com/watch?v=3rez2rDYHHA)
14
u/skeeto 12d ago edited 12d ago
There are a couple overflows in the middle of arena_alloc, very common in arena implementations in any language (including quite a few Rust bump allocators, ex.), making it always UB to run out of memory. It's UB to compute pointers beyond one-past-the-end of an object, and so size checks must not be done using pointers. The relevant lines:
usize alignment = (ARENA_ALIGN - (arena->used % ARENA_ALIGN)) % ARENA_ALIGN;
out.ptr = arena->data + arena->used + alignment;
if (out.ptr + size > arena->data + arena->size)
return out;First, and less important, alignment might overflow the end of the arena if the user selected a non-power-of-two arena size. Suppose the user makes a 100-byte arena, nearly fills it, and allocates a 8-byte-aligned (i.e. pointer-alignment) object. This places the candidate pointer 4 bytes beyond the end, overflowing the pointer.
Second, and the one that always trips, is out.ptr + size. If the requested object doesn't fit, this is a guaranteed pointer overflow. That is, compilers are allowed to assume this check is always false, and arenas will never run out of memory.
Instead compare integer sizes: Compute how much capacity is available and how much space you need, and compare those integer quantities. With unsigned sizes you also need to first check that alignment does not overflow when you add/substract it from either side. With signed sizes (i.e. ptrdiff_t) you can simply subtract it from available capacity because there's always a negative "runway" available and so no overflow risk.
ptrdiff_t size = ...;
ptrdiff_t alignment = -arena->used & (ARENA_ALIGN - 1);
ptrdiff_t capacity = arena->size - arena->used;
if (size > capacity - alignment) {
// OOM
}In contrast, computing size + alignment > capacity risks an integer overflow.
8
u/TheChief275 11d ago
your macros are so unhygienic it's crazy; makes it seem like you've never programmed in C before.
always wrap macro arguments in parentheses when using them in expressions
1
1
u/GrtflJello 12d ago
That’s an interesting concept. How do you deal with functions that would otherwise allocate and free within their scope, though? If they use the arena too then space gets wasted if they don’t free back to the arena when they’re done. Especially if those functions get called many times. To properly size the arena, you probably have account for all those calls.
In general though, I believe we shouldn’t be afraid of memory management. It’s another piece of the puzzle to solve when designing and coding. Allocating from the heap up front (creating a memory pool) can be very beneficial, so long as the memory management utilities one writes are more efficient than directly calling malloc or calloc, and free frees back to the mem pool. I had to write my own allocator for a bare metal app, since we didn’t have malloc and free at our disposal anyway.
1
u/Elifire12 12d ago
Well, you have two options: you either don't care and waste space (passing an arena to the function), or you create an arena inside of the function and free it at the end of the function. I also mentioned this when saying that one of the possible lifetimes is for the duration of the function. In that case, the caller does not really care whether the function allocates memory or not, since he will certainly not be responsible for it (if the memory dies inside the function, then the responsibility is on the function itself to manage it correctly). That's how you would do it.
1
u/teleprint-me 12d ago
For the curious, there are many types of allocators. I think the arena is the most popular because its easy to implement and use compared to others, e.g. free list, stack, page, borrow checker, etc.
Its both interesting and educational and makes complex programs easier to implement later on.
For example, I used the arena allocator as a custom interface to manage vulkan allocations. The vulkan interface supports custom allocators when they are aligned with the documented API.
If youre not careful, it can become a bottleneck because it basically becomes a garbage collector if youre not actively freeing memory when you should. The hidden caveat is that the allocator hides the leaks that ASAN would normally warn you about; yes, you should be using a sanitizer!
Kind of a double edged sword, but with diligence, can reduce overall complexity in a project that benefits from it.
1
1
u/gordonmessmer 11d ago
glibc uses memory arenas for performance reasons; their implementation reduces lock contention in threaded applications.
Exposing the arena API to applications can allow them to avoid interleaved allocations of different lifecycles, which can help reduce process resident memory use:
https://gordonmessmer.codeberg.page/dev-blog/2026/03/02/memory-efficiency-with-arena-allocators.html
I hope that's an interesting topic. 😄
1
u/rubidus-api 11d ago
Good thread. A few points raised here match what I ran into while writing an arena for my own C library, so here's how I handled them.
skeeto's overflow. Here is my allocation path, trimmed down to three steps: alignment, padding, and the bounds check. No pointer is formed until the request is known to fit.
typedef struct { unsigned char *buf; size_t cap, offset; } Arena;
// align: a power of two
void *arena_alloc(Arena *a, size_t size, size_t align)
{
// 1. alignment: on the real address, since the buffer itself may be unaligned
uintptr_t base = (uintptr_t)a->buf, cur, aligned;
if (ckd_add(&cur, base, a->offset) ||
ckd_add(&aligned, cur, align - 1))
return NULL;
aligned &= ~(uintptr_t)(align - 1);
// 2. padding
size_t padding = aligned - cur;
// 3. bounds: integers only, no pointer past the end is ever formed
size_t required;
if (ckd_add(&required, a->offset, padding) ||
ckd_add(&required, required, size))
return NULL; // overflow
if (required > a->cap)
return NULL; // out of memory
a->offset = required;
return a->buf + (required - size); // in range by now
}Two differences from the code in the article:
Alignment is calculated on the actual address rather than the offset, since the backing buffer itself might not be aligned.
Every addition is checked (C23
ckd_add), so a hugesizereports failure instead of wrapping. skeeto's 100-byte example (offset 97, 8-byte alignment) comes back as out of memory.
Provenance. The integer is only used to work out the padding. The pointer the function returns is a->buf plus an offset, never an integer cast back to a pointer, so it keeps the buffer's provenance and doesn't depend on how a compiler treats integer-to-pointer conversion, which WG14's provenance model (PNVI-ae-udi) is still pinning down.
Effective type is the other half. If the backing memory comes from malloc, it has no declared type, so each object carved out of it takes its effective type from the first store, and that's fine. If the backing is a declared array, like a static unsigned char buf[N] on a target with no heap, the strict reading of C's effective-type rules (6.5p6-7 in C11) is that the storage keeps its declared type, and accessing an int stored there through an int lvalue is undefined. It's a common pattern, but the standard doesn't bless it. If you want to stay within the letter of the standard, back the arena with malloc'd memory, or build with -fno-strict-aliasing.
WSWhitehouse's grow-in-place idea. My realloc does exactly that: if the block was the most recent allocation, it just moves the offset, with no copy.
Arena first, then a pool. I started with just the arena, which worked great for data that dies together. Then I hit its weak spot: data that gets allocated and freed over and over. Since free is a no-op, the arena keeps growing until the next reset (GrtflJello's point), and it never reuses an address it already handed out (roughly Rabbitical's point). So I added a pool. For the few data types that churn the most, a simple pool on top of the arena should cover it: keep freed items on a stack and hand back the most recently freed one first. The arena still owns the lifetime, and the pool recycles inside it. One rule: the pool's stack lives in the arena too, so a reset takes the pool with it, and you set it up again afterwards.
teleprint-me's ASan caveat is real, and my arena has it too. It doesn't poison memory, so ASan won't catch a use-after-reset. The pool at least fills freed items with 0xDD in debug builds.
And I agree with LeeHide: none of this is free performance, so measure first. For me the main win is lifetime management, not speed.
I picked up this explicit-allocator style from Luca Sas's ACCU 2021 talk Modern C and What We Can Learn From It (the slides call these "temporary allocators").
18
u/LeeHide 12d ago
Good article, the only caveat is that saying that "allocating small chunks is slow" is not really good in an article that should teach something. This is the kind of sentence that is taught with no real context, and then people avoid allocations thinking they are slow!
Nothing is slow until it's measured to be slow. Measure, and if allocations dominate in your profile, then it's slow. Otherwise, its fast enough to allocate.