Arena Allocator
Logic
Only requires an offset or pointer to state the end of the last allocation. To allocate some memory from the arena it is as simple as moving the offset (or pointer) forward. The allocation has the complexity of O(1).
Due to being teh simplest allocator possible, the arena allocator does nto allow the user to free certain blocks of memory. The memory is usually freed all at once.
Basic interface
An arena is like a stack with extensions, e.g. it can be named.
Arena *arena_alloc(void);
void arena_release(Arena *arena);
void arena_set_auto_align(Arena *arena, u64 align);
u64 arena_pos(Arena *arena);
void *arena_push_no_zero(Arena *arena, u64 size);
void *arena_push_aligner(Arena *arena, u64 alignment);
void *arena_push(Arena *arena, u64 size);
void arena_pop_to(Arena *arena, u64 pos);
void arena_pop(Arena *arena, u64 size);
void arena_clear(Arena *arena);
#define PushArrayNoZero(arena, type, count) (type *)arena_push_no_zero((arena), sizeof(type) * (count))
#define PushArray(arena, type, count) (type *)arena_push((arena), sizeof(type) * (count))
Basic implementation
the simplest arena allocator will look something like
static unsigned char *arena_buffer;
static size_t arena_buffer_length;
static size_t arena_offset;
void *arena_alloc(size_t size) {
// Check to see if the backing memory has space left
if (arena_offset+size <= arena_buffer_length) {
void *ptr = &arena_buffer[arena_offset];
arena_offset += size;
// Zero memory
memset(ptr, 0, size);
return ptr;
}
return NULL;
}
While this is as simple as it gets, there are two issues with the basic approach
- You cannot reuse this procedure for different arenas.
- The pointer returned may not be aligned correctly for the data you need.
The first issue can be solved by coupling the data into a structure and passing that to the procedure arena_alloc.
Memory alignment
Modern computer architectures will always read memory as its ‘word size’. On a 32 bit machine this will be 4 bytes, and 8 bytes for 64 bit machines. If you have an unaligned memory access the processor will have to read read multiple words. This means that an unaligned memory access may be much slower than aligned memory access.
On most architectures the amount of bytes that something must be aligned by must be a power of two. So we need a procedure to assert that the alignment is a power of two
bool is_power_of_two(uintptr_t x) {
return (x & (x-1)) == 0;
}
To align a memory address to the specified alignment is simple modulo arithmetic. You are looking to find how many bytes forward you need to go in order for the memory address is a multiple of the specified alignment.
uintptr_t align_forward(unintptr_t ptr, size_t align) {
uintptr_t p, a, modulo;
assert(is_power_of_two(align));
p = ptr;
a = (uintptr_t)align;
// same as (p % a) but faster as 'a' is a power of two
modulo = p & (a-1);
// if 'p' address is not aligned push the address to the next value which
// is aligned.
if (modulo != 0) p += a - modulo;
return p;
}