Photo by Umberto on Unsplash

Memory Allocator Free Lists: Block Reuse Without Search


Every memory allocator faces the same fundamental problem: when a program frees memory, how do you track that space so the next allocation can reuse it? Scanning the entire heap to find free blocks would be prohibitively expensive. Free lists solve this by turning freed memory into its own index.

The Core Mechanism

A free list is an intrusive linked list where each freed memory block stores a pointer to the next free block. When you call free(), the allocator writes a pointer into the first few bytes of the block being freed, linking it into a chain. When you call malloc() for a matching size, the allocator pops the head of that list in O(1) time.

This approach is “intrusive” because the list metadata lives inside the freed blocks themselves, not in a separate data structure. A 64-byte freed block doesn’t need external bookkeeping—it uses its own 8 bytes to store the next pointer. The rest of the block sits idle until reallocation.

The beauty is that freed memory costs nothing to track. You’re not maintaining a parallel index or scanning a bitmap. The blocks form their own registry simply by existing.

Size Class Segregation

Modern allocators maintain multiple free lists, one per size class. Small allocations (say, 16, 32, 64, 128 bytes) each get their own list. When you free a 32-byte block, it goes onto the 32-byte free list. When you request 32 bytes, the allocator checks that specific list first.

This segregation prevents fragmentation and eliminates the need to search for a “best fit.” You’re not walking a list of mixed-size blocks trying to find one large enough. Each size class is homogeneous, so any block on the list works.

For sizes larger than a threshold (often 1-2 KB), allocators typically switch strategies—using tree-based structures or returning blocks directly to the operating system—but free lists dominate the small-object fast path where allocation frequency is highest.

Splitting and Coalescing

What happens when you request 32 bytes but the 32-byte free list is empty? The allocator can split a larger block. It takes a 64-byte block from that list, carves off 32 bytes to satisfy the request, and puts the remaining 32 bytes onto the 32-byte free list.

Coalescing is the reverse: when you free a block adjacent to another free block, the allocator merges them into a single larger block. This requires boundary tags or other metadata to detect adjacency, which is why many high-performance allocators skip coalescing for small sizes. The bookkeeping overhead outweighs the benefit, especially when size-class segregation already limits fragmentation.

Per-Thread Free Lists

Shared free lists create contention. If every thread in a multi-threaded program is allocating and freeing from the same list, you need locks or atomic operations on every malloc() and free(). The solution is per-thread caches.

Allocators like tcmalloc and jemalloc give each thread its own set of free lists. Allocations hit thread-local lists with no synchronization. When a thread’s list runs dry, it grabs a batch of blocks from a central depot. When a thread frees memory it didn’t allocate, the block might go into a different thread’s cache or back to the central pool, depending on the policy.

This design trades some memory overhead (multiple caches holding partially-used blocks) for dramatic reductions in lock contention.

Why Not Just Use a Heap?

You might wonder why allocators don’t use a min-heap or tree to track free blocks by size, enabling efficient best-fit searches. The answer is allocation patterns. Most programs allocate and free objects of the same few sizes repeatedly—JSON objects, AST nodes, network buffers. Free lists with size-class segregation align perfectly with this behavior.

A search structure optimizes for variety. Free lists optimize for repetition. For the workloads that matter—tight loops allocating small, uniform objects—free lists are unbeatable. They turn deallocation into a pointer write and allocation into a pointer read. No traversal, no comparison, no rebalancing.

Real-World Variants

Production allocators layer additional optimizations on top of free lists. Some use magazines (small LIFO stacks of recently freed blocks) to improve cache locality. Others employ deferred coalescing, batching merge operations to amortize the cost. SLUB (the Linux kernel’s allocator) uses per-CPU free lists with lockless fast paths.

The fundamental idea remains: let freed memory index itself. Free lists transform the problem of tracking available space into a problem of maintaining linked lists, and linked lists are among the simplest, fastest data structures we have.