Arena Allocators in C

# Arena Allocators in C Source: [https://eliasebner.com/blog/guides/arena-allocators-in-c/](https://eliasebner.com/blog/guides/arena-allocators-in-c/) --- As we all know, C is a very low level language\. It allows you \(and kind of forces you\) to manage the memory you use by yourself\. This is one of the \(probably many\) reasons that people are turn to other languages when it comes to their daily programming\. In this article, I will show you a paradigm for managing memory which is not only very performant, but it’s also extremely versatile\. It makes the task significantly easier and decrease the chance of memory leaks by a large margin\. Maybe you already know about them, maybe not, in any case: I’m talking about arena allocators\. I will get to the implementation, but before I do that, here is a brief introduction to the concept of an arena allocator\. ## What Are Arena Allocators? The way people usually go about managing memory is that they allocate a small amount of memory every time they need it from the heap with`malloc`\- just what they need\. If they find out later that they need more than what was originally planned, they use`realloc`to increase the size of their memory allocation\. Once they are done with using that memory, they call`free`to tell the operating system that this memory is no longer needed and it can be employed for other tasks\. This is great, but it has a few issues: **1\.** The programmer must remember to free the memory once he is done using it\. This is especially dangerous if the allocation happens in a loop \- like in games, for example \- since in that case the operating system keeps allocating more and more memory, but that memory is never freed\. Memory, as a resource, is not infinite\. At some point, your computer will run out, and your program will be terminated by the operating system \(i\.e\. it will crash\)\. **2\.** Allocating and freeing many small chunks of memory is*slow*\. **3\.** If you have a function like: ``` i32 *create_array(usize len) { i32 *elements = (i32 *)malloc(sizeof(int)); return elements; } ``` Now, tell me: how does the programmer calling the function know that this function performs a memory allocation? In this case, one could figure it out by looking at the name of the function and thinking about what the function could possibly be doing, but it’s not always so trivial\. Remember, this is important, since the programmer needs to know when to free the memory\. The programmer needs to be made aware of the fact that it is his responsibility to free the memory\. There are probably more issues that I have not thought about, but these are some of the main ones I could think about on the spot\. **The Solution\.** Enter*the arena allocator*\. Most lifetimes \(i\.e\. how long a certain region of memory is used before it is freed\) can be grouped into one of a handful of categories: 1. The memory lives for the duration of the entire program 2. The memory lives until the completion of some tasks \(i\.e\. a frame in a game or the handling of an HTTP request\) 3. The memory lives for the scope of a function This is usually enough grouping, but depending on what you consider a group, there may be more\. In any case, we can just allocate a large chunk that we will use to work with things that have a similar lifetime \(i\.e\. things that can be freed together\)\. We then have a large amount of memory that can be used\. Whenever we use some of that memory to do something, we advance a pointer to remember up to which point the memory has been used and where the free memory begins\. This will become clearer once you see the implementation\. When we don’t need any of the data that lives inside that large chunk of memory anymore, we can simply free it all at once \(or \- if we want to reuse that same memory \- reinitialize the memory arena to its initial state and begin allocating from the start again\)\. This saves individial memory allocations \(which remember, are slow\), and makes us have to worry less about managing memory since we only have to worry about a couple of different “chunks” of memory instead of small pieces used for individual arrays\. ## The Implementation ### Clarification Before we start, I almost always include this file at the top of my code when I use C\. It simply`typedef`s some built\-in types and has some useful, commonly used utilities\. I include`\.c`files directly, since I use unity builds for faster compilation\. You can easily write the header files for this if you prefer that\. ``` // types.c #ifndef TYPES_C #define TYPES_C #include <stddef.h> #include <stdint.h> typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef float f32; typedef double f64; typedef size_t usize; #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 #endif // TYPES_C ``` ### `arena\.c` Here is the actual arena implementation\. We start with the include guard \(again, because of the unity build\), and include some`libc`headers we will use: ``` #ifndef ARENA_C #define ARENA_C #include "types.c" #include <stdbool.h> #include <stdlib.h> #include <string.h> // code goes here #endif // ARENA_C ``` Here is the arena struct definition: ``` struct arena { void *data; usize size; usize used; }; ``` It keeps track of how much memory was used\. This could also be achieved by using a pointer that points to the start of the region in memory that is still unused\. The`size`field is needed to understand if we are overflowing the arena when allocating \(that could very well happen if you are using too much memory\)\. And`data`simply points to the start of the arena\. So far so good, but now we need a way to create a new arena\. Here it is: ``` struct arena_create_out { struct arena arena; bool success; }; [[nodiscard]] struct arena_create_out arena_create(usize size) { struct arena_create_out out = {0}; out.arena.data = malloc(size); if (out.arena.data == NULL) return out; out.arena.size = size; out.arena.used = 0; out.success = true; return out; } ``` When returning multiple values, instead of using output parameters, which I find confusing and it makes the API unintuitive in my opinion, I much prefer to return structs\. We then need a way to allocate some memory in this arena\. Before this, define this macro \(I have it at the top of the file, but I am introducing it now since this is when it becomes relevant\): ``` #define ARENA_ALIGN 8 ``` This will be used to align the data\. For some reason, our computers are much better at dealing with data that is aligned at 8 bytes\. This means that the start of each new allocation has to be at a multiple of 8 bytes\. `malloc`handles this for us, but since we are not allocating with`malloc`now, but simply reserving some space in an already allocated chunk of memory, we have to align the data ourselves to make for faster accessing\. Here is the allocation function: ``` struct arena_alloc_out { void *ptr; bool success; }; [[nodiscard]] struct arena_alloc_out arena_alloc(struct arena *arena, usize size) { struct arena_alloc_out out = {0}; 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; arena->used += size + alignment; out.success = true; return out; } ``` Here, we understand how much “padding” we need to add \(the`alignment`variable\) at the end of our allocation such that the next one will be aligned to 8 bytes\. I use the pattern of having a`success`field in the return type of the function, and on error I simply return early \(since it is initialized as all\-zeroes with`= \{0\}`,`success`will be`false`\)\. If you don’t like this approach, it should be fairly trivial to migrate the API to a different convention\. Most of the work is done, I created a simple wrapper to change the size of an allocation\. It simply allocates at the end of the arena with the new size and copies the data over\. The old data is left untouched as it will be freed once the arena is freed \(remember, we cannot free individual allocations, it’s either the whole arena or nothing\)\. You don’t*really*need it, but I found that it made my code cleaner, so here it is: ``` struct arena_realloc_out { void *ptr; bool success; }; [[nodiscard]] struct arena_realloc_out arena_realloc(struct arena *arena, usize new_size, void *src, usize old_size) { struct arena_realloc_out out = {0}; struct arena_alloc_out alloc_out = arena_alloc(arena, new_size); if (!alloc_out.success) return out; out.ptr = memcpy(alloc_out.ptr, src, MIN(old_size, new_size)); out.success = true; return out; } ``` If the new size is smaller than the new size, then a part of the data is cut off at the end\. Also, internally`realloc`knows the size of each allocation associated with each pointer, so you do not need to pass the old size, only the new size\. Since our arena implementation does not keep track of the size of allocations in any way, we will have to pass the old size to the function separately\. The user of the arena is expected to know the size of each allocation\. This could also be implemented, but I would like to keep it simple\. The next two functions are small wrappers, they’re only there for convenience but are not essential: ``` void arena_clear(struct arena *arena) { arena->used = 0; } void arena_free(struct arena *arena) { free(arena->data); } ``` This is it for my implementation\. ## Example Usage I have a simple string library that I have implemented for my own use cases\. It has two concepts: a string view and an owned string\. An owned string is NUL\-terminated and`owns`its data \(i\.e\. it has to be allocated and freed\)\. That also means that one can modify an owned string directly\. A string view only*views*the data, so you cannot modify it directly, since there may exist multiple string views viewing the same data and modifying it would lead to unexpected changes to the other strings\. On the other hand, only one owned string shall exists for any given region of data\. What is important is that I need a way of converting string views to owned strings\. To do this, we have to create a new owned string \(which means allocating the memory for it\), and copy the data over\. Again, this is to make sure that changes to this owned string do not interfere with other potential string views viewing it\. We also add a NUL\-terminator at the end of the owned string \(to make it compatible with other legacy C APIs\)\. To do this, we pass an arena allocator to the function and allocate to that arena: ``` struct str_view { const u8 *data; usize len; }; struct str_owned { u8 *data; usize len; }; struct str_view_to_str_owned_out { struct str_owned str; bool success; }; [[nodiscard]] struct str_view_to_str_owned_out str_view_to_str_owned( struct arena *arena, struct str_view s ) { struct str_view_to_str_owned_out out = {0}; struct arena_alloc_out alloc_out = arena_alloc(arena, s.len + 1); if (!alloc_out.success) return out; out.str.data = alloc_out.ptr; memcpy(out.str.data, s.data, s.len); out.str.len = s.len; out.str.data[out.str.len] = 0; out.success = true; return out; } ``` This does two things: 1. The caller immediately knows that this function allocates memory \(since its first argument is an arena pointer\) 2. The caller can decide where \(i\.e\. with which lifetime\) to allocate the memory\. Regarding point no\. 2, since the caller decides the lifetime by passing the relevant arena, they do not have to worry about freeing the memory directly, the memory is simply freed once the lifetime is over and the arena is discarded \(or cleared\)\. This could be at the end of the program \(in which case freeing the memory would be unnecessary, since the operating system handles it for us\), or at the end of the function, or whenever they are sure that the memory is not needed anymore\. ## Conclusion I recently started including arenas in my programming habits and I must say that I have been really satisfied\. I have migrated my string library to use arenas and I think you could benefit a lot from using arenas as well\. Sometimes the gains in developer experience are larger than in other cases, but I would say that having this tool under your belt as a programmer is definitely a net benefit\. I don’t claim to be an expert and this implementation is just something that I have built myself for personal use\. It may not be perfect, but it should serve as a nice introduction to get you started\. Thanks for reading and I hope you found this useful\! As always, for any questions, feedback, or insights, you can reach me at my email: [info@eliasebner\.com](mailto:[email protected])