Free Lists: Threading Reuse Through the Blocks an Allocator Has Released

Every allocator has a free list. The interesting design question is where it lives. A separate table of free blocks costs memory proportional to the number of blocks and a second structure to maintain; a list threaded through the free blocks themselves costs nothing beyond the fields the block already has, because a freed block’s payload is, by definition, unused.

That single decision, storing the link inside the free memory, produces a family of designs whose differences are all about how the link interacts with the surrounding blocks. Coalescing needs to find neighbours, which needs boundary information. Size-class segregation needs several lists. Concurrency needs per-thread lists or lock-free ones. The linked structure is the common substrate, and the variations are the subject.

The implicit list

The simplest possible allocator carves a heap region into a chain of blocks, each with a header holding its size and a flag, and keeps a free list whose nodes are the blocks themselves.

struct block {
    size_t size;             /* payload bytes, header excluded */
    struct block *next;      /* free-list link, valid only when free */
    int free;                /* 1 = on the free list */
};

Allocating pops a block from the head of the list, marks it used, and returns the address immediately after the header, which is where the payload begins. Freeing pushes it back. Both are O(1) and neither touches more than the header and the list head.

A first-fit policy over a single unsorted list has a well-known weakness: it tends to fragment the heap into many small blocks near the head, because allocation always consumes the first block large enough. A long-running program that allocates and frees mixed sizes ends up with a list of blocks too small for any request, and the allocator must extend the heap even though total free bytes are ample.

Coalescing adjacent free blocks at free time is the remedy, and the direction that is cheap depends on the list’s order. If the list is unsorted, the block immediately after the freed one can be examined with one pointer addition, because blocks are contiguous and every block carries its size in its header, but the block immediately before it cannot be found without a backward walk. The allocator presented in The C Programming Language resolves this by keeping the free list sorted by address: free scans the list for the insertion point, which costs O(n), and once there it can test both physical neighbours for adjacency and merge them. The scan is linear, but the number of free blocks is usually far smaller than the number of live allocations, and the merge keeps that number from growing.

A second approach avoids the scan. Each block stores its size both at its start and at its end, so the header of the physically preceding block can be found by reading the word immediately before the current block’s header.

+----------------+---------------------+----------------+
| size | flags   | payload ...         | size | flags   |
+----------------+---------------------+----------------+
 ^ header                                ^ footer

With a footer, coalescing in both directions is O(1) from an unsorted list, and the free list can stay LIFO for locality. The cost is one extra word per block, which for small blocks is a significant fraction: a 16-byte payload with an 8-byte header and an 8-byte footer occupies 32 bytes of heap, so half the block is metadata.

Segregated free lists

The alternative to one list is many. A segregated-fit allocator keeps an array of free lists indexed by size class, where class i holds blocks of a narrow size range, often a power-of-two band or a fixed-size bin.

#define NBINS 32
struct bin { struct block *head; };
struct heap { struct bin bins[NBINS]; };

Allocation rounds the request up to a class, pops from that class’s list, and splits the block if it is larger than needed. Freeing determines the block’s class from its size and pushes it onto the corresponding list. No search is required at all, which makes both operations O(1) in the class count.

Segregation buys speed and costs space. With power-of-two classes, a 17-byte request lands in the 32-byte class and wastes nearly half the block; a 33-byte request lands in the 64-byte class and wastes almost as much. Internal fragmentation is bounded by the ratio between adjacent class sizes, so power-of-two classes waste up to 50 percent per allocation and finer geometric classes waste proportionally less. The usual compromise is a geometric progression with a ratio around 1.25 above a small threshold, giving at most about 20 percent internal waste, or exact classes for small sizes where the waste matters most.

Segregation also affects coalescing. Blocks of different classes cannot be merged into a block that belongs to a class, because the merged size may fall between classes. Allocators that segregate therefore either accept external fragmentation between classes or maintain a separate mechanism for large blocks, which are the ones where coalescing matters. The common architecture is segregated bins for small allocations and a boundary-tagged, coalescing free list for large ones.

The list that is a tree

Free blocks in a size-ordered allocator are often kept in a balanced tree rather than a list, so that a best-fit search is O(log n) instead of O(n). The nodes of that tree are the free blocks themselves, which means a free block must carry the tree’s own fields: two child pointers and a parent or colour bit, stored in the block’s payload while the block is free.

That requirement is why allocator block headers are larger than the payload needs. A free block must carry enough metadata to participate in the index structure, and a used block does not, so the header is sized for the free case. dlmalloc’s design, documented in its source and widely copied, keeps free chunks in doubly linked bins, one per size class, together with a tree index over the larger bins; each chunk header carries the size and flags in one word, and the word before it holds the size of the preceding chunk, which lets a freed chunk find its lower neighbour without a footer of its own.

The lesson generalises: in an allocator, the metadata a free block needs while it sits in a tree or a bin has to be stored somewhere, and the block is the only place it exists. The cost is paid by every allocation, used or not. This is the same trade described in Intrusive Linked Lists, where the link field exists in every element whether or not it is linked.

Per-thread lists and the remote free path

A single free list shared by all threads needs a lock on every allocation and every free, which is expensive for an operation that occurs millions of times per second. The standard mitigation is a per-thread cache: each thread owns a small free list of recently freed blocks, and only falls back to the shared structure when its list is empty or too full.

struct tcache {
    struct block *head;
    size_t count;
    size_t limit;    /* e.g. 64 blocks */
};

Allocation pops from the thread’s list, free pushes to it, and both are lock-free with respect to other threads. When the list exceeds its limit, a batch of blocks is flushed to the shared structure; when it is empty, a batch is refilled. The batching amortises the shared-structure cost across many operations, and the limit bounds the memory a thread can hoard.

The correctness hazard is that ownership must move completely at each transfer. Once a block has been flushed to the shared structure, the flushing thread’s cache must no longer hold it; a cache that keeps a pointer to a block it has flushed, or that reads a block’s link field after the block has been reallocated to another thread, corrupts whichever list now owns the block. The rule is that exactly one owner exists at a time, and the handover happens before the block can be reused elsewhere.

A second hazard is false sharing. Two threads’ caches in the same cache line cause the line to bounce between cores on every push and pop, even though the threads never touch the same block. Padding each thread’s cache to a cache line removes the interference at the cost of 64 bytes per thread, which is why allocator thread caches are usually aligned and padded.

What the free list cannot fix

The linked structure is not the source of fragmentation, and no free-list discipline eliminates it. Three failure patterns recur regardless of the list design.

Size-class mismatch. A workload that alternates between allocating a large block and a small one leaves holes that fit neither. Segregated bins cannot merge across classes, so the holes persist.

Long-lived small allocations among short-lived large ones. A single small allocation that survives forever pins the block it sits in, preventing the surrounding region from coalescing. This is why allocators distinguish small objects into arenas and why a long-lived allocation in a short-lived arena is the classic leak-shaped fragmentation.

Unbounded caching. A per-thread cache with no limit retains memory proportional to the peak allocation rate of each thread, which can be far above the steady-state requirement. Limits and periodic trimming bound it, at the cost of returning memory to the shared structure more often.

The measurement that matters is not free bytes but the largest allocation the heap can still satisfy, because that is what determines whether the next request succeeds. A heap with 40 percent free bytes scattered in unusable holes is effectively full for a request larger than the largest hole.

Relation to the rest of the cluster

A free list is an intrusive list whose elements are blocks rather than objects, and the pattern’s properties carry over directly. Insertion and removal are pointer writes with no allocation. The list cannot free its elements, because the elements are the memory the allocator manages. The link field is present in every block, used or free, and its size is set by the worst case rather than the common one.

The differences are equally instructive. Free-list order is usually LIFO for cache locality, since the most recently freed block is the most likely to still be in cache. Free-list membership is transient in a way that a queue’s is not, so the link field is overwritten on every reuse and any stale reference to a block’s link is immediately wrong. And the structure is modified concurrently by design in a multi-threaded allocator, which is why the concurrency techniques in Lock-Free Linked Lists apply directly to allocator free lists, including the ABA problem that a pop-then-push of the same block creates.

A free list is the cheapest possible dynamic structure, and it is also the one with the least forgiveness for a stale pointer. The block’s payload is not just freed, it is overwritten by the link, so a use-after-free read returns a pointer value rather than the stale data, and the error propagates into the structure rather than staying local.