Arena Allocation and Ownership by Convention

Every object-level scheme in this cluster pays for its generality at the point of allocation: a header, a free list, a count, or a mark bit, plus a decision about which object to free. Region allocation removes the decision. Objects are placed into a region, and the region is released as a whole, so no individual object is ever freed and no per-object metadata exists. The result is the fastest allocation primitive in ordinary use, together with a set of restrictions that reshape how the program must be written.

One pointer and one comparison

A bump allocator holds three values: a base address, a current offset, and a limit. Allocation rounds the requested size to the platform’s alignment, checks that offset plus size does not exceed the limit, and returns base + offset, advancing the offset.

#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

struct arena {
    unsigned char *base;
    size_t offset;
    size_t limit;
};

void *arena_alloc(struct arena *a, size_t n) {
    const size_t align = 16;
    n = (n + align - 1) & ~(align - 1);      /* round up to 16 bytes */
    if (a->offset + n > a->limit) return NULL;
    void *p = a->base + a->offset;
    a->offset += n;
    return p;
}

void arena_reset(struct arena *a) { a->offset = 0; }  /* the entire free operation */

The fast path is an add, a compare, and a store, with no branches beyond the bounds test. A comparison against malloc is not close: the allocator must find a free block of the right size class, write a header, and possibly split a larger chunk, with a fast path in the tens of cycles at best. The arena’s fast path is a handful of cycles, and its free path is a single assignment.

Deallocation is the interesting part. arena_reset returns everything at once, and individual objects cannot be returned. That is not a missing feature; it is the source of the speed. Without the ability to free individual objects there is no need for headers, no need for coalescing adjacent free blocks, and no reusable free space inside the region at all: every byte stays allocated until the reset.

The region’s memory typically comes from one large malloc or a direct mmap. Because the region is contiguous, objects allocated from it in sequence land in sequence, so iterating a linked list of arena-allocated nodes touches a contiguous span rather than a scattered set of blocks. The locality benefit is often larger than the allocation-time benefit.

The lifetime rule the region imposes

The constraint is simple and unforgiving: nothing allocated from a region may outlive the region. Any pointer into the region becomes dangling the moment the region is reset or destroyed, and the compiler cannot tell which pointers those are.

That is why region-based systems are usually paired with a static discipline. Tofte and Talpin’s region inference infers, rather than requires the programmer to write, a region for every allocation and checks that a value is never stored into a region that is freed earlier than the region its contents live in. Their calculus makes the stack of regions follow the call stack, so a callee can allocate in its own region and the region is deallocated on return, which recovers the stack discipline for heap data. The cost is that the inferred regions become part of every function’s type, which is what makes them checkable and also what makes interfaces between separately compiled modules hard to keep stable.

Real implementations take a lighter route. The Apache Portable Runtime pools are the clearest example in C: an apr_pool_t is created, passed to every function that needs memory, and destroyed at the end of a request. Every allocation takes the pool as its first argument, so the ownership is visible in every signature. The pool tracks its allocations in a linked list so that any cleanup handlers registered against it run before the memory is released, which reintroduces per-allocation bookkeeping but only for allocations that need cleanup.

The same shape appears in compilers. A parser typically allocates AST nodes from a per-compilation arena and never frees them individually, because the whole arena is released when compilation finishes. LLVM’s BumpPtrAllocator works this way, and its SpecificBumpPtrAllocator adds typed destruction at the end of the arena’s life rather than per object.

Destructors do not run

A region release is a pointer reset. It does not walk the objects and call destructors, because it does not know what types they are. Anything with an external resource must therefore be released explicitly before the region dies.

That inverts the RAII relationship described in destructors and unwinding. With destructors, forgetting the explicit release is safe and forgetting the destructor is impossible. With arenas, the memory is always reclaimed and the resource is not. A file handle stored in an arena-allocated struct will leak its descriptor when the arena dies unless a cleanup handler is registered.

The pool pattern solves this with a cleanup registry: apr_pool_cleanup_register attaches a function and an argument to the pool, and the pool runs those functions before releasing memory. That registry is per-cleanup rather than per-object, so it costs a node in a list only for objects that need it. C++ achieves the same by giving the arena’s owner a destructor that destroys the objects it placed, which requires the arena to be typed and to know the element types.

Where the pattern shows up

The most consequential use is in request handling. A server that processes a request can allocate everything the request touches (parsed headers, decoded body, response buffer) from one region and reset it when the response is sent. That converts an arbitrary number of allocations and frees into a single reset, and it makes leak-freedom a property of the region rather than of every code path. The constraint is that nothing retained across requests may point into the request region, which pushes persistent state into a separate long-lived region.

Compilers use the same decomposition: a per-function region for the intermediate representation of one function, a per-module region for symbol tables, and a global region for the whole compilation. The regions are nested, and a nested region must not store pointers into a parent that may be freed first. That is the inverse of the usual rule, and it is the reason the region hierarchy has to match the data’s actual lifetime structure.

Serialization and parsing libraries use regions to avoid the “who owns the decoded tree” question entirely: the tree is owned by the parse context, and the context is dropped as a unit. This is the design of several binary-format parsers, where the decoded structure is only valid while the input buffer is alive and the arena holding the decoded nodes is alive.

The costs that remain

Fragmentation within a region is real, though it takes a different form. Because objects are never freed individually, an object allocated early and used briefly still occupies its bytes until the region dies. A long-lived region that allocates short-lived objects will grow without bound, which is the arena’s version of a leak. The remedy is a second region with a shorter life, and choosing the right boundaries is the design work.

Memory is also held longer than strictly necessary. A per-request region that lives until the response is written holds the request’s buffers for the whole processing time. For a large body, that is a real cost in resident set, and the alternative is streaming with a bounded buffer rather than a region per request.

Alignment padding accumulates. With a fixed 16-byte alignment, an object whose size is not a multiple of 16 occupies the next multiple up, so a node of 40 bytes occupies 48 and the waste is a fifth of the region. Parsers that allocate millions of small nodes therefore store them in a single array with an index instead of a pointer, so that the padding is paid once per array rather than once per node. Object pools with fixed-size slots are the specialized form: one arena per element size, so padding is paid once per size class rather than per allocation.

The pattern is not a general replacement for malloc. It is a bet that most allocations in a phase share a death time, and the bet is usually right in compilers, servers, and batch processors, and usually wrong in long-running interactive programs where objects have genuinely independent lifetimes. When the bet fails, the result is unbounded growth, which is harder to diagnose than an ordinary leak because no allocation is individually lost. The borrow checker makes the corresponding static rule checkable for region-annotated languages, and malloc and manual ownership covers the per-object alternative that arenas are measured against.