Why this matters: systems interviewers check your code against your invariants the way machine-coding interviewers check code against seams. The arena's fast path is four lines, which means every line carries weight — and the alignment arithmetic in the middle of it is where hand-waving goes to die. Walk it with real numbers and it can't hand-wave.
The structures
typedef struct Block {
char* base; // start of slab
char* cursor; // next free byte
char* end; // one past last byte
struct Block* next;
} Block;
typedef struct Arena {
Block* head; // chain of all blocks (for reset/destroy)
Block* current; // block being bumped
size_t block_size; // 64 KiB standard slab
} Arena;No other state exists. Narrate that: everything the arena knows is where each slab starts, where its next free byte is, and where it stops.
The fast path: aligned bump
void* arena_alloc(Arena* a, size_t size, size_t align) {
// align is a power of two, >= 8
uintptr_t p = (uintptr_t) a->current->cursor;
uintptr_t aligned = (p + align - 1) & ~(uintptr_t)(align - 1);
if (aligned + size > (uintptr_t) a->current->end)
return arena_alloc_slow(a, size, align); // grow, then retry
a->current->cursor = (char*)(aligned + size);
return (void*) aligned;
}Walk the arithmetic on real numbers, out loud. Say the cursor sits at 0x5008 and the caller wants 40 bytes aligned to 16:
p = 0x5008 align-1 = 0xF p + 15 = 0x5017 & ~0xF = 0x5010 <- rounded UP to the next 16-boundary cursor = 0x5010 + 40 = 0x5038
Eight bytes (0x5008 to 0x5010) were skipped to honor alignment — the arena's only waste on this path, and it required no record-keeping at all. Also worth saying: when the cursor is already aligned, (p + align - 1) & ~(align - 1) leaves it unchanged — the formula rounds up only when needed, which is why it's the standard idiom.
The slow path: chain a block
void* arena_alloc_slow(Arena* a, size_t size, size_t align) {
// Worst case: alignment padding can cost up to align-1 bytes.
size_t need = size + align - 1;
if (need <= a->block_size) {
Block* b = block_new(a->block_size); // fresh standard slab
b->next = a->head;
a->head = b;
a->current = b; // future bumps land here
return arena_alloc(a, size, align); // retry: guaranteed to fit
}
// Oversized: dedicated block, spliced BEHIND current.
Block* big = block_new(need);
big->next = a->head;
a->head = big;
uintptr_t aligned = ((uintptr_t)big->base + align - 1) & ~(uintptr_t)(align - 1);
big->cursor = big->end; // fully consumed; never bumped again
return (void*) aligned;
}Two decisions to narrate. The need computation is the honest worst case — a fresh block's base might land maximally misaligned for the caller's request, so reserve padding room up front. And the oversized block joins the chain but never becomes current: the standard path keeps bumping a normal slab, while the outlier lives in its own link and dies with everything else. That's the splice from lesson 02, made literal.
reset() and destroy()
void arena_reset(Arena* a) {
for (Block* b = a->head; b != NULL; b = b->next)
b->cursor = b->base; // rewind; release nothing
a->current = a->head;
}
void arena_destroy(Arena* a) {
Block* b = a->head;
while (b != NULL) {
Block* next = b->next;
block_free(b); // slab released exactly once
b = next;
}
a->head = a->current = NULL;
}reset is the phase boundary: cursors rewind, warm memory stays, and the invariant base <= cursor <= end holds trivially at cursor == base. destroy is the only place slabs are released, satisfying "exactly once" by construction of the single walk.
What you'd say about complexity
Allocation: O(1) — arithmetic plus one comparison; the slow path amortizes to O(1) because each chained block serves many allocations (and the oversized path is one system allocation for one request). reset: O(blocks), typically a handful. destroy: O(blocks). Space overhead: alignment padding per allocation (bounded by align − 1), plus unused slack at the tail of each non-current block — and be honest that slack is the price of chaining rather than resizing.
Key takeaway
The whole arena is arithmetic on three pointers: round the cursor up with the power-of-two mask, fit-check against end, advance, return — walked on real addresses so nothing hides. Growth chains standard slabs, oversized requests get a dedicated spliced block that never becomes current, reset rewinds cursors without releasing, and destroy is the single walk that frees each slab exactly once.