There is a very simple pattern of memory allocation using arenas that makes memory management in C safe, easy, and efficient. I've been using this pattern for a little while now, and it has dramatically simplified working with memory in C for me.
Any language that has manual memory management has a number of problems that must be solved including:
If you already are familiar with arenas, you can skip this section. Otherwise, I'll give you a brief introduction to what arenas are. First, I should make the caveat that people have different names for what I'm calling an "arena". Some people call it a "bump allocator", some call it a "region allocator". There are probably other names. I'm just going to use the term "arena".
An arena allocator is a pool of memory that acts similar to a stack. Allocating memory involves returning a pointer to a location in the pool and bumping that pointer by the number of bytes allocated. Typically, arenas cannot free individual allocations. Instead, an arena is "reset" by just returning the memory pointer back to its original position. This "frees" all allocations that were made to that allocator all at once.
Recently, I've been using a strategy for memory allocation that I'm calling Structured Allocation. I like to think of it as an analogy to "structured programming". Structured programming introduced the concept of breaking code into managemable blocks that are delineated by control flow such as loops, if-then-else statements, switch statements, etc. By introducing restrictions to how people wrote code, it became more readable, modular, modifiable, debuggable, etc. The concepts behind structured programming were so successful that every major programming language has included them since the 1960s.
Structured allocation is similar. The idea is that instead of using malloc and free anywhere in our program, we actually restrict our allocations to grouped lifetimes collected into arenas. Typically, the lifetime of these arenas is the lifetime of a function call. There are only 3 simple rules to structured allocation:
The following is a very simplified and contrived example, but should be enought to illustrate the point.
#include "clib.h"
typedef struct Person {
char *name;
int favorite_int;
} Person;
Person get_person(Arena *a);
int main(void) {
// This is our top-level arena for allocations that will last the lifetime of
// the program
Arena arena = arena_make();
// We pass arena into get person so it can allocate and give that memory
// back to us
Person p = get_person(&arena);
printf("name:%s, favorite int:%d\n", p.name, p.favorite_int);
// We destroy the arena when we are done
arena_destroy(&arena);
return 0;
}
Person get_person(Arena *a) {
// create a local "scratchpad" arena
Arena local = arena_make();
char *name = arena_allocate(1024, &local);
char *favint = arena_allocate(64, &local);
// get input from user
printf("Enter your first name:");
fgets(name, 1024, stdin);
printf("Enter your favorite 32 bit integer:");
fgets(favint, 64, stdin);
// allocate only necessary memory for the user's name using the provided arena
Person p = {0};
p.name = arena_allocate(strlen(name), a); // <- allocation owned by main (yay!)
strncpy(p.name, name, strlen(name)-1); // cut off the newline
// convert the string to an integer
p.favorite_int = atoi(favint);
// get rid of our "scratchpad" allocations
arena_destroy(&local);
// return our Person with allocations that are owned by "main", the caller
return p;
}
Notice how in get_person We create a "scratchpad" arena for allocations that will be temporary.
Typically you only need one local arena for a function, but you could use more if you want fine-grained control.
Also notice how we use the a arena passed to get_person in order to allocate memory that will outlast the get_person function call.
Just by following this simple pattern we solve all of our problems.
It's now very simple to write c libraries and share them with people. It is also much simpler to write c programs without having to constantly worry about mis-matched lifetimes. There are some things I haven't addressed here, such as how to deal with memory shared between threads, but I just wanted to cover the idea of using "local" and "external" arenas to simplify memory management in C.
If you want to play around with this arena allocator, I've pushed it to a gitlab repo here. There are some interesting properties of my Arena implementation itself, but that is beyond the scope of this blog entry.