Heap Allocators

A heap allocator manages variable-size, arbitrarily-timed memory requests within a region of address space already backed by real memory, exposing an interface such as malloc and free. It sits above physical memory management and paging rather than replacing either: a page allocator hands out memory in fixed, page-sized units, which is far coarser than most allocations a kernel or program actually needs, and a heap allocator exists specifically to subdivide that coarse-grained memory into the small, differently-sized pieces real code asks for.

Purpose and scope

A page allocator alone is insufficient for general-purpose use because most allocations are far smaller than a page and arrive in unpredictable sizes and order. A kernel data structure might need 64 bytes; a userspace program might request a string of arbitrary length. Rounding every such request up to a full page would waste enormous amounts of memory and would not, on its own, provide any mechanism for reusing space once an allocation is freed. A heap allocator addresses this by requesting memory from the page allocator in large chunks and then managing the internal layout of those chunks itself, tracking which portions are in use and which are free, and satisfying future requests from the free portions before asking the page allocator for more.

A kernel’s own internal allocator operates under constraints a userspace allocator does not. Code running with interrupts disabled, or inside an interrupt handler itself, generally cannot block waiting for memory to become available, which rules out any allocation path that might need to wait on a lock held by code that has itself been interrupted, or that might trigger a page-reclaim operation expected to take an unbounded amount of time. Production kernels commonly express this distinction through flags passed to every internal allocation call, indicating, for instance, whether the caller is in a context that permits sleeping if memory must first be freed elsewhere, or whether it requires an immediate answer regardless of whether that answer is a successful allocation or outright failure. A heap allocator intended only for straightforward, single-context kernel use can generally ignore this distinction, but it becomes unavoidable once interrupt handlers and preemptible kernel code share the same allocator.

This division of responsibility is not unique to a kernel: userspace malloc implementations solve the identical problem, requesting memory from the kernel via a system call (historically brk/sbrk, more commonly mmap on modern systems) and then managing that memory themselves rather than making a system call for every allocation. A kernel’s internal heap allocator, used for its own data structures, and the allocator backing a userspace program’s malloc are conceptually the same kind of software solving the same problem, differing mainly in what they ask the level below them for.

The free list model

The most common allocator design maintains a linked list of free blocks. Each block, whether free or in use, is preceded by a small header recording at minimum its size, which allows free to determine how much memory to reclaim given only the pointer originally returned by malloc: the header sits just before that pointer, at a fixed negative offset, and is never exposed to the caller.

struct block_header {
    size_t size;       // size of the usable region, not including this header
    int    free;
    struct block_header *next; // next block in the free list
};

const BlockHeader = struct {
    size: usize,          // size of the usable region, not including this header
    free: bool,
    next: ?*BlockHeader,  // next block in the free list
};

#[repr(C)]
struct BlockHeader {
    size: usize,             // size of the usable region, not including this header
    free: bool,
    next: *mut BlockHeader,  // next block in the free list
}

Allocation walks the free list looking for a block large enough to satisfy the request. Several search strategies trade off allocation speed against how well they preserve large contiguous free regions: first-fit returns the first block found that is large enough, which is fast but tends to leave many small unusable fragments near the start of the list over time; best-fit scans the entire list and returns the smallest block that still satisfies the request, minimizing wasted space per allocation at the cost of a full scan; next-fit behaves like first-fit but resumes searching from wherever the previous search left off rather than restarting from the beginning, spreading allocations more evenly across the heap.

The list described above is an explicit free list: pointers linking one free block to the next are stored inside the blocks themselves, but only inside free ones, since an allocated block has no need to appear on the list at all and its payload belongs entirely to the caller. An alternative, simpler design uses an implicit free list, where every block, free or allocated, is linked in address order regardless of status, and a search walks past allocated blocks by reading their size field and skipping ahead rather than following an explicit next pointer. An implicit list requires less per-block bookkeeping in the free case but must inspect every block, allocated or not, during a search, whereas an explicit list can skip allocated blocks entirely since they were never linked into it in the first place, a tradeoff between simplicity and search efficiency that mirrors the choice between an array and a linked list in other contexts.

Splitting and coalescing

A free block larger than the requested size is not necessarily used in its entirety: allocators typically split it, carving off only the amount needed and leaving the remainder as a smaller free block back on the list, provided the remainder is large enough to hold a header and be useful on its own. Splitting indefinitely would eventually produce blocks too small to be worth tracking separately, so implementations generally define a minimum block size below which a remainder is left oversized instead of split.

The reverse operation, coalescing, merges a freed block with any physically adjacent free blocks back into one larger block, which is what prevents the heap from fragmenting into an ever-growing number of small, individually-useless free regions over the lifetime of a long-running program. Coalescing with the following block is straightforward if free blocks are linked in address order: the header of the block being freed can inspect its immediate neighbor directly. Coalescing with the preceding block requires knowing that block’s size without walking the entire list from the start, which is what a boundary tag (also called a footer) provides: a copy of the size field duplicated at the end of every block, whether free or allocated, letting code immediately behind a given block work backward to find that block’s header directly, in constant time, regardless of list length.

A single free list searched linearly does not scale well once the heap holds many blocks of widely varying size, since satisfying a small request may require walking past a large number of unrelated free blocks before finding a suitable one. Segregated free lists address this by maintaining several free lists rather than one, each dedicated to a range of block sizes (one list for blocks under 32 bytes, another for 32 to 64 bytes, and so on) so that a search only ever examines blocks already known to be roughly the right size. Coalescing under this scheme additionally requires moving a newly-merged block from its old size class’s list to whichever list matches its new, larger size, but the reduction in per-allocation search time is substantial enough that most general-purpose allocators used in production, rather than a single flat free list, adopt some form of size-class segregation.

Growing the heap

When no free block is large enough to satisfy a request, the allocator extends the region it manages by requesting additional memory from whatever sits below it: the physical page allocator and paging code, inside a kernel, or a system call such as brk or mmap in userspace. The newly obtained memory is formatted as one large free block, coalesced with any existing free block that happened to sit at the end of the previous region, and the allocation then proceeds as it would against any other sufficiently large free block. Because requesting more memory from the layer below is typically far more expensive than satisfying an allocation from an existing free block, allocators generally request more memory than the immediate allocation strictly requires, anticipating future requests and amortizing the cost of the underlying request across many subsequent allocations.

Shrinking the heap back down is considerably rarer in practice than growing it, and many allocators never attempt it at all, retaining every byte ever requested from the layer below for the remaining lifetime of the process or kernel. Where it is attempted, it is only straightforward when a large free region sits at the very end of the managed area: memory can then be released with brk (moving the break address backward) or munmap, exactly mirroring how it was obtained, because a free region anywhere else in the middle of the heap cannot be released independently without either relocating still-live allocations around it or leaving a hole the underlying layer has no way to reclaim.

Fragmentation

Internal fragmentation is memory wasted inside an allocated block that is larger than what was actually requested, the result of alignment requirements, minimum block sizes, or an allocator’s decision not to split a block whose remainder would be too small to be useful. External fragmentation is memory wasted between allocations: enough total free memory may exist to satisfy a request, but no single free block is large enough because the free memory is scattered in pieces too small individually, even after coalescing has merged whatever adjacent free regions it could. External fragmentation is the harder problem in practice, since it depends on the entire history of allocation and deallocation order rather than on any single allocation in isolation, and different allocator designs make different tradeoffs to control it: smaller allocation classes, more aggressive coalescing, and address-ordered free lists all reduce it at some cost in either speed or code complexity.

Fragmentation is commonly quantified as a utilization ratio: the peak amount of memory actually requested by live allocations at any point, divided by the total amount of memory the allocator has requested from the layer below it to satisfy those requests. A ratio close to one indicates an allocator wasting little space to overhead or unusable gaps; allocator research and benchmarking historically compares implementations against synthetic and real-world allocation traces specifically to measure this ratio under realistic, rather than adversarial or best-case, usage patterns, since an allocator’s fragmentation behavior depends heavily on the particular mix and order of sizes a given workload requests.

Alternative allocator designs

The free-list model is general-purpose but not the only approach, and kernels frequently use more than one allocator internally for different purposes.

A buddy allocator manages memory in power-of-two-sized blocks. A request is rounded up to the nearest power of two, and a block of that size is obtained by recursively splitting a larger free block in half, into two “buddies”, until a block of the required size results. Freeing a block checks whether its buddy (found via a simple address XOR with the block’s size) is also free, and if so merges the two into the next larger power-of-two block, repeating the check at each larger size. This makes coalescing extremely fast and the bookkeeping simple, at the cost of potentially significant internal fragmentation, since a 65 KB request rounds up to 128 KB. Buddy allocators are common as the allocator managing physical page frames themselves, one level below the heap allocator described in the rest of this article.

A slab allocator takes a different approach suited to a pattern common inside kernels: repeatedly allocating and freeing many objects of the exact same fixed size and type: process control blocks, filesystem inodes, network packet buffers. Rather than a general free list, a slab allocator maintains separate pools (“caches”), each pre-formatted to hold objects of one specific size, with free objects in a cache tracked by a simple embedded free list requiring no separate header at all. This avoids both the search overhead of a general-purpose allocator and its internal fragmentation entirely, since every object in a given cache is exactly the size it needs to be, and is why production kernels typically layer a slab allocator on top of their page allocator for their own fixed-size internal structures, reserving a general-purpose heap allocator for variable-size or userspace-facing allocations.

Production general-purpose allocators intended for large multithreaded userspace programs frequently combine several of the ideas above into a single design rather than choosing one exclusively. Size classes narrow enough to bound internal fragmentation tightly, per-thread caches to avoid contention, and page-granularity backing structures shared across size classes are common structural elements across independently-developed allocators used in widely deployed software, arrived at separately by different implementations converging on broadly similar solutions to the same underlying constraints rather than by any one design being copied between them.

Concurrency

An allocator shared across multiple CPUs must protect its free list, or lists, against concurrent modification, and a single global lock around every allocation becomes a significant bottleneck as CPU count grows, since every core contends for the same lock on every malloc and free call. Allocators intended for multiprocessor use commonly give each CPU (or each thread) its own small local cache of free blocks, satisfying most allocations without taking any shared lock at all, and falling back to a shared, locked structure only when a local cache is empty or needs to return excess memory. This pattern shows up in both kernel-internal slab allocators and in userspace allocators designed for multithreaded programs, for the same underlying reason: contention on a single shared data structure scales poorly, while per-CPU state that is only occasionally reconciled with a shared pool scales far better.

A subtler concurrency hazard specific to memory reuse is false sharing: even without any lock contention, if two unrelated allocations made by different threads happen to land on the same CPU cache line, because an allocator packed them tightly together with no regard for which thread requested which, writes by one thread to its own, logically independent data will still force the cache line out of the other thread’s cache, degrading performance in a way that has nothing to do with any actual data dependency between the two threads. Allocators aware of this sometimes pad or align per-thread allocations to cache-line boundaries specifically to prevent it, trading a small amount of additional internal fragmentation for the elimination of an otherwise difficult-to-diagnose performance problem.

A minimal implementation

A first-fit allocator over a single fixed-size arena can be implemented compactly. The header defined earlier is placed immediately before every block, and the free list is singly linked:

static struct block_header *free_list = NULL;

void heap_init(void *start, size_t size) {
    free_list = start;
    free_list->size = size - sizeof(struct block_header);
    free_list->free = 1;
    free_list->next = NULL;
}

void *heap_alloc(size_t size) {
    struct block_header *curr = free_list;
    while (curr) {
        if (curr->free && curr->size >= size) {
            if (curr->size >= size + sizeof(struct block_header) + MIN_BLOCK_SIZE) {
                struct block_header *remainder =
                    (void *)((char *)curr + sizeof(struct block_header) + size);
                remainder->size = curr->size - size - sizeof(struct block_header);
                remainder->free = 1;
                remainder->next = curr->next;
                curr->size = size;
                curr->next = remainder;
            }
            curr->free = 0;
            return (char *)curr + sizeof(struct block_header);
        }
        curr = curr->next;
    }
    return NULL; // out of memory; a real implementation would grow the heap here
}

void heap_free(void *ptr) {
    struct block_header *block =
        (struct block_header *)((char *)ptr - sizeof(struct block_header));
    block->free = 1;
    // a real implementation coalesces with adjacent free blocks here
}

A production allocator adds coalescing, heap growth, and typically alignment padding so every returned pointer satisfies the platform’s worst-case alignment requirement (commonly 16 bytes on x86-64), none of which changes the fundamental free-list-and-header structure shown above.

The same logic, expressed in Zig, looks structurally identical (a tagged header, a singly linked free list, and the same split-on-allocate behavior), differing mainly in how the language expresses pointer arithmetic and optional values explicitly:

const BlockHeader = struct {
    size: usize,
    free: bool,
    next: ?*BlockHeader,
};

const min_block_size: usize = 16;
var free_list: ?*BlockHeader = null;

fn heapInit(start: [*]u8, size: usize) void {
    const block: *BlockHeader = @ptrCast(@alignCast(start));
    block.size = size - @sizeOf(BlockHeader);
    block.free = true;
    block.next = null;
    free_list = block;
}

fn heapAlloc(size: usize) ?[*]u8 {
    var curr = free_list;
    while (curr) |block| {
        if (block.free and block.size >= size) {
            if (block.size >= size + @sizeOf(BlockHeader) + min_block_size) {
                const remainder_addr = @intFromPtr(block) + @sizeOf(BlockHeader) + size;
                const remainder: *BlockHeader = @ptrFromInt(remainder_addr);
                remainder.size = block.size - size - @sizeOf(BlockHeader);
                remainder.free = true;
                remainder.next = block.next;
                block.size = size;
                block.next = remainder;
            }
            block.free = false;
            const data_addr = @intFromPtr(block) + @sizeOf(BlockHeader);
            return @ptrFromInt(data_addr);
        }
        curr = block.next;
    }
    return null;
}

fn heapFree(ptr: [*]u8) void {
    const block_addr = @intFromPtr(ptr) - @sizeOf(BlockHeader);
    const block: *BlockHeader = @ptrFromInt(block_addr);
    block.free = true;
}

Zig’s optional pointer type (?*BlockHeader) makes the “end of list” case (Zig’s equivalent of a null next pointer) checked by the compiler at every point the value is used, rather than relying on a programmer to remember to test for it, though the underlying algorithm and memory layout are unchanged from the C version.

A kernel written in Rust generally implements the same structure behind the GlobalAlloc trait, still relying on raw pointers and unsafe blocks internally, since manipulating a free list fundamentally requires the kind of unchecked pointer arithmetic Rust’s ownership model does not otherwise permit:

#[repr(C)]
struct BlockHeader {
    size: usize,
    free: bool,
    next: *mut BlockHeader,
}

const MIN_BLOCK_SIZE: usize = 16;
static mut FREE_LIST: *mut BlockHeader = core::ptr::null_mut();

unsafe fn heap_init(start: *mut u8, size: usize) {
    let block = start as *mut BlockHeader;
    (*block).size = size - core::mem::size_of::<BlockHeader>();
    (*block).free = true;
    (*block).next = core::ptr::null_mut();
    FREE_LIST = block;
}

unsafe fn heap_alloc(size: usize) -> *mut u8 {
    let header_size = core::mem::size_of::<BlockHeader>();
    let mut curr = FREE_LIST;
    while !curr.is_null() {
        if (*curr).free && (*curr).size >= size {
            if (*curr).size >= size + header_size + MIN_BLOCK_SIZE {
                let remainder = (curr as *mut u8).add(header_size + size) as *mut BlockHeader;
                (*remainder).size = (*curr).size - size - header_size;
                (*remainder).free = true;
                (*remainder).next = (*curr).next;
                (*curr).size = size;
                (*curr).next = remainder;
            }
            (*curr).free = false;
            return (curr as *mut u8).add(header_size);
        }
        curr = (*curr).next;
    }
    core::ptr::null_mut()
}

unsafe fn heap_free(ptr: *mut u8) {
    let header_size = core::mem::size_of::<BlockHeader>();
    let block = ptr.sub(header_size) as *mut BlockHeader;
    (*block).free = true;
}

The #[repr(C)] attribute on the header struct is required here for the same reason a kernel written in Rust generally needs it on any structure whose memory layout must be predictable: Rust’s default struct layout is deliberately unspecified and may reorder fields for optimization, whereas size, free, and next must occupy the exact offsets this code’s pointer arithmetic assumes.

Implementation notes

Writing past the end of an allocation corrupts whatever follows it in memory, commonly the header of the next block, since blocks are typically packed contiguously, which can cause an unrelated, later allocation or free to fail in a way that appears entirely disconnected from the actual bug. Freeing the same pointer twice corrupts the free list by linking a block into it more than once, so that a subsequent allocation can return the same memory to two different callers simultaneously. Both classes of bug are considerably harder to diagnose in a heap allocator than in most other code, precisely because their symptoms surface far from their cause; debugging builds of an allocator commonly add guard values around each block and check them on every operation specifically to catch this class of corruption closer to where it actually occurs.

Alignment deserves separate attention from sizing: most architectures require certain data types to begin at addresses that are multiples of their size, and an allocator that does not guarantee a minimum alignment for every returned pointer will eventually hand out memory that causes a misaligned access fault, or silent performance degradation on architectures that tolerate misalignment but penalize it.

Guard values placed immediately before and after the usable region of a block, commonly called redzones, extend this defense specifically against writes that overrun an allocation’s boundary rather than corrupt it internally: a fixed, recognizable byte pattern is written into the redzone bytes when a block is allocated, and checked again when it is freed, so that a write extending even slightly past the end of the caller’s requested size is caught at the point the block is freed rather than surfacing much later as unrelated, unexplained corruption somewhere else in the heap. Tools built around this technique, most notably AddressSanitizer, extend the same idea further by additionally poisoning the redzone in a way that a hardware or software check can detect immediately at the moment of an out-of-bounds access, rather than only retroactively when the block is eventually freed.

References

^ D. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms: describes the boundary-tag technique and classical free-list allocation strategies.
^ J. L. Peterson and T. A. Norman, “Buddy Systems,” Communications of the ACM, 1977: the original description of buddy-system memory allocation.
^ J. Bonwick, “The Slab Allocator: An Object-Caching Kernel Memory Allocator,” USENIX Summer 1994: introduces the slab allocation model used by most production kernels.

Heap Allocators

Purpose and scope

The free list model

Splitting and coalescing

Growing the heap

Fragmentation

Alternative allocator designs

Concurrency

A minimal implementation

Implementation notes

References

See also