Boundary Tags and Coalescing in a Free-List Heap

A free list solves the easy half of dynamic allocation: remembering which extents are available. The hard half is that adjacent free extents must be merged, or the heap degrades into a field of small holes separated by live objects, each hole too small for the requests that arrive next. The classic solution, boundary tags, is a small piece of metadata duplicated at both ends of every block, and it is one of the oldest structural ideas in heap design.

Why a size alone is not enough

Suppose each block carries a header with its size. Freeing a block is then a matter of pushing it onto a list. But consider two adjacent free blocks, of 48 and 40 bytes, and a later request for 72 bytes, which needs 88 bytes once the header is counted. Neither block can serve it; together they can. To discover that, the allocator must be able to find the block that starts where another block ends.

Walking forward is easy: the next header sits at block + size. Walking backward is not, because block sizes vary and nothing in the current header says how far back the previous block began. Appending a footer that repeats the size solves it. The footer of the preceding block is the word immediately before the current header, so the allocator reads it, subtracts, and lands on the previous header.

typedef struct block {
    size_t size;   /* extent in bytes, header and footer included;
                      bit 0 set means the physically previous block is free */
    /* payload ... */
    /* size_t footer;  at (char *)block + (size & ~1) - sizeof(size_t) */
} block_t;

The lowest bit of size is normally borrowed as a flag, because sizes are multiples of the alignment, 8 or 16 bytes, so the low bits are free. That trick packs two facts into a field that is already being read, at the cost of masking before every arithmetic use. The previous-free bit is what makes backward coalescing constant time in the common case: if the previous block is not free, there is no point reading its footer at all.

The cost is concrete: two words per block instead of one. On a 64-bit system, a minimal block is therefore 16 bytes of metadata, and with a 16-byte alignment rule a 16-byte payload needs a 32-byte block. Overheads of 50% at that size are the reason real allocators set a minimum block size, often 32 bytes, and refuse to split below it. Every allocation of a size class below the minimum is rounded up, which is where the familiar gap between “bytes requested” and “bytes consumed” begins.

Splitting, merging, and the four neighbour cases

Allocation from a free block is a split: if the block is larger than needed by at least the minimum block size, the tail becomes a new free block with its own header and footer, and the head is returned. Splitting is what keeps the heap responsive to mixed sizes, and the minimum-block rule is what stops it from producing slivers that no future request can use.

Freeing examines two neighbours, which gives four cases:

• Neither neighbour free: the block becomes free on its own and joins a free list.
• Next block free: absorb it, extending the size by the neighbour’s size and rewriting the footer that now terminates the merged block.
• Previous block free: absorb it in the other direction, which requires reading the previous block’s size from the footer, then moving the block’s start pointer back.
• Both free: remove the next block from its free list, absorb both, and write one footer.

Each absorption requires removing the absorbed block from whatever free list holds it. If the lists are doubly linked with pointers stored inside the free payload, removal is O(1). That is why free blocks must be at least large enough to hold two pointers plus the header and footer, and the same minimum-size rule serves both purposes.

The merge is not merely an optimisation. Without it, a program that allocates and frees a mixture of sizes leaves a heap of unusable gaps, and total free bytes can be large while no single request can be satisfied. Coalescing converts that condition into large extents that satisfy big requests, at the cost of work on the free path.

Immediate versus deferred coalescing

Merging eagerly on every free keeps the heap maximally consolidated but charges the cost to the caller doing the free. An alternative is deferred coalescing: free blocks are not merged when freed; the allocator merges only when a request cannot otherwise be satisfied, or when it walks a list and notices adjacent free blocks. Deferral shifts work from the common case to the rare one, which is usually the right direction, since most frees are followed by allocations of similar size that the freshly freed block serves directly.

The price of deferral is that the free lists may contain adjacent blocks, so a scan for a sufficiently large block has to look at more entries before concluding that no fit exists. Deferral also makes accounting harder: the sum of free-list sizes overstates what any single request can obtain until the merge pass runs. Some allocators defer only backward coalescing, or merge only within a bounded window, trading some consolidation for a bounded worst case.

A related variant is the segregated free list, in which blocks are bucketed by size and each bucket holds blocks in a known size range. Coalescing then has to find which bucket the neighbour belongs to, which is derivable from the neighbour’s size, so removal stays O(1). Bucketing changes the search from “walk one list” to “pick the right list, then walk a short one”. That idea is developed in size-class design.

Where the scheme breaks

Boundary tags assume that the allocator owns a contiguous region and that every block’s extent is recoverable from its header. Both assumptions fail in ordinary systems.

Once the heap is a set of non-contiguous chunks obtained from the kernel, the block at the start of a chunk has no valid predecessor, so the allocator needs a sentinel: a zero-size or always-allocated header at each chunk boundary. Without it, reading the word before the first block reads unrelated memory and the merge corrupts the heap. Sentinel handling is a recurring source of bugs in allocators that grew from a single contiguous region into chunked allocation.

Metadata corruption is the other exposure. Because coalescing writes to the header and footer of neighbours, a single overwritten size field propagates: the allocator computes a wrong neighbour address, merges across live data, and the next allocation returns a pointer into a live object. The damage appears far from the original overflow. This is exactly the failure that hardening measures target, and it is why some designs keep metadata out of band, in a separate table indexed by chunk and offset, so a heap overflow cannot rewrite it.

Placement policy interacts with all of this. First-fit scans from the head of a list and leaves fragments near the front; best-fit scans further and leaves smaller remainders; next-fit resumes from the last successful position. Measurements in the allocation literature consistently show that address-ordered first-fit and best-fit behave better than their naive counterparts on real traces, because they tend to preserve large extents, a consequence of keeping the free list sorted by address, which also makes coalescing trivial since neighbours are adjacent in the list. The cost of maintaining that order is an O(n) insertion in the simple case, or a tree index in a serious implementation.

There is also a boundary condition on the arithmetic itself. Sizes are computed by adding a header and rounding up to alignment; for a request near SIZE_MAX that addition wraps, producing a tiny block that “fits” and hands back a pointer to a buffer far smaller than requested. Every careful allocator rejects requests above a maximum, commonly on the order of PTRDIFF_MAX, before doing any arithmetic.

The design constraint behind boundary tags is thus not space efficiency but the ability to answer “who is adjacent to me” in constant time with data that lives next to the object. That is cheap when the heap is one array of bytes and expensive when it is not, which is why segmented and page-based designs replace footer arithmetic with address-to-chunk mapping, and why the arena model in bump allocation can drop the footer entirely: with allocations strictly ordered and no per-object free, adjacency is trivial and no merge is ever needed.