Memory fragmentation

Why can a long-running program fail to allocate memory when far more than it asked for is free?

A service has been up three weeks. It asks for eight kilobytes and is refused, while the accounting says thirty megabytes are free. Nothing leaked — the live set has been flat for days.

So the refusal cannot be about quantity. Something is being demanded that thirty megabytes of free memory does not necessarily supply. What?

Contiguity. An allocation returns a single address, and the caller treats the bytes from there onward as one block. So the allocator cannot hand back a hundred scattered fragments summing to eight kilobytes; it must find one hole at least eight kilobytes long. Free memory is not a quantity in a pool, it is a set of holes, and the only number that matters for a given request is the size of the largest one.

Now ask how the holes got their shape. Allocate a hundred blocks into an empty heap and there are no holes — a solid run. Free every other one and the heap is a comb: half free, no hole larger than a single block. Nothing about how much is free changed; only the order of operations did. The hole structure is a function of the entire history of allocations and frees, not of current occupancy. Fragmentation is path-dependent, and history is not something an allocator can undo.

What makes the history sticky is lifetime mixing. Free a short-lived sixty-four-byte object sitting between two long-lived megabyte buffers, and the hole it leaves can serve nothing bigger and cannot merge with anything until both neighbours die — which may be never. Long-lived objects act as pins, so every short-lived death leaves a hole they hold open indefinitely.

The natural next thought is that a cleverer placement policy avoids this. Best-fit, first-fit, buddy allocation — surely one wins? There is a result here I recall rather than derive, from Robson: for any online allocator, worst-case memory use grows roughly like the live requirement times the logarithm of the ratio between largest and smallest request size. The constants matter less than the shape of the claim — there is a lower bound, and it is not zero. The reason is plain once stated: an allocator must place a block now without knowing what will be requested later. Fragmentation is the price of deciding under ignorance, not a defect anyone will engineer away.

So why not slide everything down and close the gaps? Because a pointer is an address. Moving a block invalidates every pointer naming it, and where addresses are ordinary observable values — stored in structs, cast to integers, handed to a driver — the allocator cannot find them all. Compaction is possible only for a runtime that knows where every reference lives, exactly what a tracing garbage collector maintains. That is the real division of the bill: a manual allocator pays in fragmentation because it cannot move things, a moving collector pays in pause time and write barriers because it can. Neither escapes the underlying problem, that a block once placed is expensive to unplace.

The practical answer in production allocators is segregation by size class: serve every request from a pool dedicated to a rounded-up size, so blocks within a class are interchangeable. This genuinely helps — but note what it moved rather than removed. A class holding many free slots cannot lend them to another class, and every allocation wastes the gap between its true size and its class size. External fragmentation, "no hole is big enough", has become internal fragmentation, "the space inside the blocks is not all used", plus whole pages stranded in idle classes.

A falsification test, since fragmentation is easy to say and easy to misdiagnose. The account predicts a signature: bytes actually live stay flat while bytes mapped from the operating system rise and then plateau, and restarting restores the original footprint with no code change. A leak looks different — the live set itself grows without bound, unaffected by whether allocation sizes are mixed.

And the refuting observation? If contiguity is really the constraint, enlarging the heap while leaving the allocation pattern identical should postpone the failure but not prevent it — the comb re-forms at the new scale. If a one-off increase permanently fixed it, the program was simply undersized and contiguity was never binding.

Two clarifications connect the steps. First, fragmentation is not memory nobody is using; it is memory that is free but unreachable by this request. The same thirty megabytes that cannot serve one eight-kilobyte block may serve four hundred sixty-four-byte blocks perfectly well — which is why a fragmented program limps rather than dying outright, and why the failure looks random.

Second, the honest scope. For sixty-four-bit user-space programs, virtual memory has largely defused the classic version: the address space is vast enough that holes are cheap to leave alone. The constraint still bites where the arena is genuinely bounded — fixed-size embedded and kernel pools, thirty-two-bit processes, and above all physical page allocation, where a driver or a huge-page request needs contiguous frames and no virtual indirection helps. That form will not be designed away, because it follows from blocks needing to be in one piece.

This sits alongside memory thrashing, a shortfall of capacity and a collapse of locality, and next to garbage collection pauses, the cost of the machinery that makes moving objects possible at all. Fragmentation is the failure that happens when capacity is ample and only the geometry is wrong.

• How size-class and slab allocators decide class boundaries, and what the rounding waste comes to in practice.
• Why physical-page fragmentation still causes huge-page allocation failures on machines with plenty of free RAM.

Every term the collection defines is gathered in the glossary.