Bump Allocation and the Cost of Arena Reset

A general-purpose malloc has to answer an impossible question: given an arbitrary pointer returned long ago, recover its extent and make the hole reusable, in any order, from any thread, without knowing anything about the program’s structure. Every byte of metadata in a real heap exists to service that question. An arena declines to answer it. If every object in a region dies at the same moment, then the allocator never needs to know where an individual object ended; it needs to know only where the region began.

That single observation removes almost all of the work. An arena allocator, sometimes called a region or bump-pointer allocator, has the cheapest allocation path available to compiled code: on the common architectures an allocation is a load, an add, a mask, and a store, with no search, no lock, and no per-object header.

One pointer, one subtraction

The state of an arena is a base address, a current offset, and a capacity. Allocation returns the base plus the offset and advances the offset by the requested size. That is the entire mechanism.

typedef struct {
    unsigned char *base;
    size_t         used;
    size_t         cap;
} arena_t;

void *arena_alloc(arena_t *a, size_t n, size_t align)
{
    /* Round the current offset up to the requested alignment. */
    size_t start = (a->used + (align - 1)) & ~(align - 1);
    if (start > a->cap || n > a->cap - start)
        return NULL;                 /* reject before any subtraction */
    a->used = start + n;
    return a->base + start;
}

The overflow check deserves attention. a->used + (align - 1) can wrap if used is close to SIZE_MAX, and a->cap - start underflows if start exceeded the capacity. The version above rejects a rounded start beyond the capacity before subtracting, so the subtraction cannot underflow, and the second test then compares the size against what actually remains. The invariant it preserves is that used stays at or below cap: after a successful call, used equals start + n and start + n <= cap. An implementation that computes used + n > cap directly is vulnerable to the wrap.

Note what is absent. There is no header, so the returned pointer is the object. There is no free list, so there is no search. There is no lock, because an arena is normally owned by one thread or one task at a time; sharing one across threads requires external synchronisation and gives up the main advantage.

Alignment is the only bookkeeping

Hardware and language rules force the mask step. malloc must return memory suitably aligned for any fundamental type, which means the strictest alignment among them: 16 bytes on x86-64 and on AArch64 with the standard C ABI, because long double and max_align_t require it. Objects of size 1 must still start on a 16-byte boundary if the caller might later treat them as anything else. The padding produced by rounding is the arena’s only waste, and it is bounded: at most align - 1 bytes per allocation.

Padding is invisible and therefore easy to misjudge. A loop that allocates a million 24-byte nodes from a 16-byte-aligned arena consumes 32 bytes each, not 24, a third more memory than the struct size suggests. Sizing a request to a multiple of the alignment removes the gap, which is why arena-backed node pools usually pad their element type to a power of two.

For larger alignment, such as a cache line at 64 bytes, a page at 4096, or a vector type with a 32- or 64-byte ABI alignment, the same mask works, provided the base itself is aligned. A base obtained from malloc is only guaranteed 16-byte alignment, so an arena that must serve 4096-byte requests has to obtain its backing memory from a page-aligned source, or over-allocate and round the base up while remembering the original pointer for release.

Reset is a single assignment

Deallocation from an arena is not per object. It is a->used = 0, or a return to a previously recorded offset. The idiom is a checkpoint: save used, allocate freely, then restore it.

size_t mark = a->used;
/* any allocation through a between these two lines dies together */
a->used = mark;

Restoring an earlier offset reclaims every allocation made after it, in one store. Because the arena is a stack of offsets rather than a stack of objects, checkpoints must nest properly. A later restore invalidates any checkpoint taken after it. Enforcing that discipline is the caller’s job; the allocator cannot detect a stale mark, and reusing one silently hands out memory that is still live elsewhere.

Nested arenas make the discipline easier to keep. A parent arena hands out large chunks; a child takes its backing store from the parent and can be discarded as a unit. This is how per-request scopes are usually built in servers and compilers: one arena per parse, per query, or per frame, destroyed when the unit of work ends. Destruction is a loop over chunk headers plus a release of each chunk, and the cost is proportional to the number of chunks, one per few kilobytes, rather than to the number of objects.

The absence of per-object free also means the arena never fragments in the classic sense. Space is consumed strictly in address order, so the live set is always a prefix of the region. There is no hole to fit a later request into, which is why first-fit and best-fit policies, and the boundary tags that support them, have no counterpart here.

Where arenas stop being cheap

The first limitation follows directly from the reset model: an arena cannot reclaim one object while keeping its neighbours. A long-lived object allocated early pins its bytes until the whole region is released. A workload with one persistent structure and a high churn of short-lived ones in the same arena will grow without bound, because the churn accumulates behind the survivor.

The second is growth. When the current chunk fills, the arena must acquire another. Chunks are usually linked, each carrying a pointer to the previous one, so the arena needs a chunk header of one or two words; obtaining the chunk itself normally means a page-granular request to the operating system or a large malloc. Growth by doubling keeps the number of chunks logarithmic in the total bytes allocated, at the cost of up to a 2× overshoot in reserved address space at the moment of the last doubling. For a 4 KiB page granularity, a chunk sequence of 4 KiB, 8 KiB, 16 KiB and so on reaches 1 MiB in nine steps.

The third is that peak usage equals the sum of all live objects plus padding plus slack in the partially used chunk. Because nothing is recycled within a chunk, the arena’s high-water mark is the maximum over the whole scope, not the maximum concurrent live set. The distinction matters when one phase of a computation allocates far more than the rest and the arena outlives it.

Reallocation is the awkward case. Growing an object in place is possible only if it is the most recent allocation, which the allocator can check by comparing the pointer against base + used minus the object’s size. Otherwise the object must be copied to fresh space, and the old bytes leak until reset. Some arena interfaces therefore offer a grow-in-place path that the caller uses only when it knows the object is the newest; without that knowledge, copying is the only correct option.

Ownership rules that keep reset sound

The mechanism is trivial; the failure mode is not. An arena reset is safe only if no pointer into the region survives it. That is an ownership statement, and it is the part that costs design effort:

• Every object allocated from the arena must be reachable only from other objects in the same arena, or from stack state that dies before the reset.
• No object may be published to a longer-lived structure, such as a cache, a global registry, or a queue drained by another thread, unless ownership is transferred and the receiving side copies.
• Destructors must run before the reset if the objects own external resources. The arena frees bytes, not file descriptors, and skipping the destructor loop turns a memory optimisation into a resource leak.

These rules are checkable by review and by type discipline, but not by the allocator. A dangling arena pointer dereferences like any other use-after-free, and because the region is still mapped it will often read plausible stale data instead of faulting, which is the worst kind of bug to diagnose. Systems that rely on arenas for large fractions of their allocation therefore tend to pair them with a debug mode that unmaps or poisons the region on reset.

Arenas also interact with the rest of the heap. Their chunks come from the same page pool that the general allocator uses, so a process that holds many small arenas has a footprint set by chunk size rather than by live data; the slab and object-cache design solves the analogous problem for fixed-size objects by sharing one cache among many consumers. And because arenas never return individual bytes, the question of when memory goes back to the kernel is deferred entirely to chunk release, which the kernel interface controls.

The trade is stark and worth stating plainly: an arena buys a handful of cycles per allocation and a single store per reset, and it pays with the inability to free an object early, with peak footprint set by scope rather than by liveness, and with an ownership obligation that the type system does not enforce. For phases of work with a common lifetime, such as request handling, compilation passes, serialisation buffers or per-frame scratch, that is usually the right trade. For a long-lived heterogeneous heap it is not, and the free-list structures that handle arbitrary order come next.