Building a Free-List Allocator on Top of an Arena

Normal Arena is fairly simple concept, big pre-allocation, then small further allocations and single release after work is done. If workload however requires more flexible object lifetimes some allocation may perish while other linger. This turn normal arena into more complex general-purpose memory allocator, but still backed by one mmap region.

Changes

The bump allocator only needed three pointers (start, cursor, end). Individual free needs a way to walk the region block by block, so every allocation now gets a Header in front of it:

typedef struct {
  size_t size;
  int is_free;
} Header;

size lets the allocator skip to the next block without knowing anything else about the data in between. is_free marks whether that block can be reused.

Code example

Memory layout

Tracing main - arena_alloc(512) (a), arena_alloc(512) (b), then arena_alloc(1024) (c) - then arena_free(a) followed by arena_free(b), then arena_alloc(900) followed by arena_alloc(64):

Freeing a just flips its flag - it's the first block and b after it is still used, so nothing merges. Freeing b is where backward coalescing earns its keep: c ahead is still used, but find_previous_header walks from start, finds a free, and folds the two into one 1040-byte block. Forward-only merging could only reach this by freeing b before a; now order doesn't matter.

arena_alloc(900) reuses that block. The leftover is 1040 - 900 - 16 (the header) = 124 bytes, under the 128-byte MIN_SPLIT_SIZE, so process_header hands back the whole block instead of splitting off a fragment too small to track.

arena_alloc(64) finds nothing free - a, b, d are all USED and c never was - so arena_alloc falls through to the arena's bump path: e lands right after c, out of untouched, and cursor moves for the first time since the initial three allocations. Reuse and bump are the same call, not two allocators.

Allocating

arena_alloc first calls find_free_block, which walks headers from start to cursor looking for a free block big enough to fit size. If one exists, process_header splits it: the requested size becomes its own block, and the leftover space becomes a new free block right after it - but only if that leftover is at least MIN_SPLIT_SIZE to not leave small pieces unused. Only when no free block fits does the allocator fall back to bumping cursor, exactly like the plain arena.

Freeing and coalescing

arena_free flips is_free on the freed block's header (it gets the user pointer and steps back sizeof(Header) to find it), then merges with free neighbors on both sides - and keeps going as long as there are free blocks to absorb, not just the one immediately adjacent.

Merging forward does arena_coalescing - from a header it looks at the block right after it, and if it's free, devours it. Then loops further until it hits a used block or the cursor.

Merging backward is trickier, because a header only knows how to skip forward - there is no pointer back to the previous block. find_previous_header walks from start, remembering the last header seen, until it reaches the one being freed. If that predecessor is free, arena_free folds the current block into it, then repeats from the merged block, collapsing a run of free predecessors rather than only the one directly behind.

In practice neither loop iterates more than once: coalescing is eager, so a run of adjacent free blocks never gets a chance to build up. The loops exist so a single missed merge somewhere can't quietly compound into a chain of unmerged free blocks.

The tradeoff

This is still backed by one mmap region and still can't return memory to the OS until the whole thing is torn down - that part of the arena model survives. What's gone is the O(1) free and the zero-metadata layout: every allocation now carries a header, and both arena_alloc and arena_free can trigger a linear scan over previous blocks. MIN_SPLIT_SIZE trades a small amount of guaranteed internal fragmentation (up to 127 bytes kept attached to an allocation) for avoiding free blocks so small they can never be reused - a fixed threshold, not something the allocator adapts based on actual usage patterns.

More scenarios to consider

• worst-case fragmentation across many alloc/free cycles - a free block that's too small for anything and has no free neighbor to merge with, sitting dead between two used blocks indefinitely.
• alignment - arena_alloc returns whatever offset the cursor or a reused block happens to land on; nothing rounds it up. After a 900-byte allocation the next header and its payload sit on an odd address, and a type the ABI wants 8- or 16-byte aligned (double, SIMD) then faults or runs slow. A real allocator rounds every request up to a max-align multiple so every returned pointer is aligned.
• double-free / invalid-pointer detection - arena_free trusts the pointer blindly: it steps back sizeof(Header) and flips is_free with no check that the block came from this arena or wasn't already free. Freeing twice runs coalescing twice and can swallow a block that's since been handed out again; a pointer into the middle of a block reads garbage as a header. A magic field in the header, plus checking the address is in [start, cursor) and is_free was really 0, catches the common mistakes.
• where this stops being worth it vs just calling malloc/free per-object.