Arena (/Bump/Linear) allocator

Implementation Details

• Standard: ISO C11 (requires <stdalign.h> support).
• Structure: Single-Header Library (STB-style).
• Compatibility: POSIX / Windows / Embedded (no OS-specific syscalls, just standard memory manipulation).
• Dependencies: None (Standard C Library only).

Whether you're new to arena allocators or not, this file will help you understand the lib AND learn an innovative and important concept!

1. Memory management

Malloc and free:

A "general purpose" allocator, it's functional with small and big allocations and is used the most of the time. Due to its "flexibility", it may have some downsides: fragmentation (allocating and freeing memory can create "holes"), and slowness (every call has to search for a sufficiently large block).

Linear allocator (Arena)

Instead of looking for a free block for every allocation, an arena allocator already has a large space of contiguous addresses to allocate data! We allocate a large quantity of memory, and the next allocations are made by moving a pointer forward (-> extremely fast, just pointer arithmetic).

NOTE: an arena brings performance, but comes with rules too.

---

2. Memory Alignment

Modern CPUs read data by "words" of 4 or 8 bytes (depends on the system). If we stored a value without proper alignment it could be split across multiple words -> reading those data can lead to crashes or worsen performances.

Examples:

• A char is 1 byte, so it doesnt require a specific alignment; it can start at any address.
• An int is (usually) 4 bytes, so it needs to be stored starting on an address multiple of 4 (or 8 on 64-bit systems) -> This ensures efficient and safe access.

Padding

To achieve the correct alignment we use the padding: depending on the type (and its size) for which we want to allocate space, the allocator has to calculate the next address that is multiple of the requested alignment (some bytes could be remain unused but that's acceptable).

Implementation is simply made by some bitwise operations:

uintptr_t current_ptr = (uintptr_t)buffer + used;
uintptr_t aligned_ptr = (current_ptr + align - 1) & ~(align - 1);
size_t padding = aligned_ptr - current_ptr;

The formula for the alignment (implemented in align_forward) just rounds up the address to the nearest multiple of the requested alignment.

If you dont know uintptr_t type, you could find usefull this file.

---

3. How the arena works?

An arena has 3 attributes:

// base arena struct
typedef struct {
  unsigned char* buffer; // pointer to the buffer start
  size_t size; // buffer size
  size_t used; // used bytes of the buffer
} Arena;

• buffer is the pre-allocated memory block.
• used is the "bump pointer", a shifting pointer for the allocation.

-> arena_init(&arena, backing_buffer, size) initialize an existing Arena object.

Why unsigned char* (instead of void*)?

In C, pointer arithmetic depends on the type size:

• If you have int *p (where int is 4 bytes), p + 1 advances the address by 4 bytes.
• If you have void *p, doing arithmetic (p + 1) is technically illegal in standard C (though GCC allows it as an extension, treating it as 1 byte).

By using unsigned char* (which is guaranteed to be 1 byte), we ensure that buffer + used advances exactly by used bytes, not multiples of something else.

---

4. Usage

The user stores data on the arena by arena_alloc_align(&arena, size, align, is_zero):

1. Calculate the index to store data: aligned_ptr = align_forward(arena->buffer + arena->used, align)
2. Verify if size bytes can be stored: padding + size <= arena->size
3. Update used: used += size
4. Return aligned_ptr

The library also contains some macros to facilitate alloc-operations (arena_push, arena_push_array). The alloc function can clean the memory (by memset(ptr, 0, size)).

Free the memory:

(for dynamically allocated backing stores) A single free (arena->buffer) deallocates everything! To "clear" the arena, there are arena_pop, and arena_reset which change arena->used and allows to reuse those addresses.

---

5. "Ownership"

The arena only manages the allocated memory; it does NOT own it! Therefore, the user is responsible for freeing the backing buffer, not the "entire" arena.

• (case 1) The Arena call free when it has to be destroyed. PROBLEM: we can not use the Arena for the static memory (a free will crash the program).
• (case 2) The user decide how deallocate the memory, call the free if it is needed or not (more flexible).

---

6. Temporary Arena (scoped allocation)

The library offers some functions to manage temporary scopes, similarly to the stack of functions but for dynamic data.

(hypothetically) A function that needs to allocate space can temporarily store data on the arena, and at the end restore the previous state.

Begin/End pattern

The user saves the original state (the current state) of the arena before storing data on it.

typedef struct {
  Arena* arena;
  size_t old_used;
} TempArena;

Usage

1. Begin: call arena_temp_begin(&arena), which saves arena->used and stores it in a returned TempArena.
2. Work: allocate data on the arena (arena_push, arena_push_array,...), and used increments.
3. End: call arena_temp_end(temparena), which restore the previous arena's state with temparena.old_used

It appears that middle allocations (Work) never occurred.

---

7. Split allocations (safe pattern)

Sometimes the user does not know how many bytes he need to allocate (e.g. reading a file, formatting strings, receiving network packets). Instead of allocating temporary buffers, the library allows the user to write directly into the arena.

Usage

1. Begin write: call arena_write_begin(&arena, align, &max_len), which returns a pointer to the free space without modifing arena->used; it also stores in max_len the maximum size the user can write (arena_available).
2. Work: user can store data (e.g. by read, fgets, snprintf, ...) in the arena, keeping track of how many bytes are written. NOTE: Do NOT perform other allocations on the arena during this step!
3. End write: calling arena_write_end(&arena, start_ptr, write_size) finally advances arena->used, committing the allocation!

Good workflow:

size_t max;
char *ptr = arena_write_begin(&arena, 1, &max);
// ...
arena_write_end(&arena, bytes_written);

Bad worflow:

char *ptr = arena_write_begin(&arena, 1, &max);
ptr[0] = 'A';
// ERROR! this push overwrites everything after the write_begin
int *x = arena_push(&arena, int); 
ptr[1] = 'B'; // ptr[1] write on 'x'
arena_write_end(&arena, 2);