How Do Memory Allocators Manage Free Lists and Fragmentation?

Dynamic memory allocators manage heap memory by tracking unallocated blocks using data structures known as free lists and applying placement, splitting, and coalescing strategies to minimize external fragmentation. External fragmentation occurs when free memory is broken into many small, non-contiguous blocks, preventing a large allocation request from succeeding even when the total free memory is sufficient. Classical allocators balance allocation speed, metadata overhead, and memory utilization through specialized free list organizations and block-merging techniques.

Free List Architectures

A free list is a data structure that records the location and size of every unallocated block on the heap. Allocators typically embed this metadata directly within the free blocks themselves, avoiding the need for separate auxiliary memory.

Implicit Free Lists

In an implicit free list, the allocator stores a header—and often a footer—in every block, whether allocated or free. The header contains the block's total size and an allocation bit indicating whether the block is in use. Because there are no explicit pointers connecting free blocks, the allocator must traverse the entire heap sequentially from the beginning to find a suitable free block. While simple and space-efficient for small heaps, implicit lists have a linear search time of \(O(N)\), where \(N\) is the total number of blocks on the heap.

Explicit Free Lists

An explicit free list improves lookup performance by storing next and prev pointers inside the payload area of each free block, forming a doubly linked list of only the unallocated blocks. This reduces search time to \(O(F)\), where \(F\) is the number of free blocks. When a block is freed, it can be inserted into the list using either a Last-In, First-Out (LIFO) policy—inserting at the head in \(O(1)\) time—or an address-ordered policy, which keeps the list sorted by memory address to simplify coalescing.

Segregated Free Lists

Segregated free lists partition free blocks into multiple lists based on size classes, such as powers of two (\(2^k\)). An array of list heads points to each size class. When a request of size \(s\) arrives, the allocator computes the appropriate size class index and searches only that list (or the next larger non-empty list). This approach approximates best-fit placement in near-constant time, \(O(1)\), and is widely used in production allocators like jemalloc and ptmalloc.

Placement Policies

When searching a free list for a block of size \(s\), the allocator uses a placement policy to choose among available candidates:

• First Fit: Scans the list from the beginning and selects the first free block that is large enough. It is fast but can leave small, unusable splinters near the front of the list.
• Next Fit: Resumes scanning from the point where the previous search ended. This avoids clustering splinters at the start of the heap, though it can slightly increase fragmentation compared to first fit.
• Best Fit: Searches the entire list (or size class) to find the smallest free block that satisfies the request. This minimizes wasted space per allocation but can be slower and may produce tiny leftover fragments.

Combating External Fragmentation

Even with optimal placement, repeated allocations and deallocations inevitably divide the heap into small, scattered chunks. Allocators use several mechanisms to restore contiguous free space.

Block Splitting

When an allocator selects a free block of size \(B\) to satisfy a request of size \(s\), and \(B - s\) is large enough to hold a valid block (including its header, footer, and minimum payload), the allocator splits the block into two. The first part of size \(s\) is marked allocated, and the remainder of size \(B - s\) is returned to the free list. Without splitting, internal fragmentation would waste the unused portion of the block.

Coalescing with Boundary Tags

Coalescing is the process of merging adjacent free blocks into a single larger block. To perform coalescing in \(O(1)\) time without traversing the entire heap, allocators use boundary tags. Each block includes both a header at the start and a footer (a copy of the header) at the end. When a block is freed, the allocator checks the allocation bit of the immediately preceding block (via its footer) and the immediately following block (via its header). If either neighbor is free, their sizes are combined into one contiguous free block.

Deferred Coalescing and Compaction

Immediate coalescing merges blocks on every free() call, which can cause thrashing if a program repeatedly allocates and frees blocks of the same size. Some allocators use deferred coalescing, waiting until an allocation request fails or a threshold is reached before scanning and merging adjacent free blocks. In environments with managed runtimes or garbage collection, allocators may also perform heap compaction—relocating live objects to one end of the heap to eliminate external fragmentation entirely—though this is generally not possible in unmanaged languages like C and C++ where raw pointers cannot be safely updated.