The Allocator's Job and the Free List

What you are really asking malloc to do

On the earlier rungs you learned that the heap is the region of memory you grow yourself, and that malloc() and free() are how you carve pieces out of it and give them back. That was the user's view. Now you sit on the other side of the call. The allocator's whole job is this: a program will ask, in any order it likes, for blocks of any size — 8 bytes here, 4000 bytes there, 24 bytes, 1 MiB — and will later hand each one back, also in any order. The allocator owns one big slab of address space from the kernel and must satisfy every request out of it, deciding for each malloc() exactly which bytes to return.

Stated that baldly it sounds easy, but four demands pull against each other, and the art of allocator design is balancing them. It must be fast: malloc() and free() sit on the hot path of nearly every program, so an answer that takes a microsecond to compute is already a disaster. It must be space-efficient: if it wastes half the bytes it hands out, your program needs twice the RAM. It must avoid fragmentation: even with plenty of free bytes in total, it can fail to find enough contiguous bytes for one request. And it must be correct under concurrency, because real programs allocate from many threads at once. Every technique in this rung is a move in that four-way tug-of-war.

Bookkeeping: the header on every block

Here is the first puzzle. When you call free(p), you hand back only a pointer — you do not say how big the block was. Yet the allocator must know its size to reuse it. So the size has to be written down somewhere it can find from p alone. The classic trick is allocation metadata: just before the bytes it returns to you, the allocator keeps a small hidden header. If a block of 32 usable bytes lives at address p, the header sits a few bytes earlier, at p minus the header size, and records the block's total length and whether it is free or in use.

This is why malloc(32) often consumes noticeably more than 32 bytes of heap: you pay for the payload plus the header plus rounding up for alignment. It is also why the cardinal sin of heap programming — writing one byte past the end of your block — is so dangerous: the byte just past your payload is very often the next block's header, and corrupting a size field turns the allocator's own data structures into garbage. The crash, if you are lucky enough to get one, usually surfaces in a later, innocent free() far from the real bug.

  ... | header | payload (returned to you) | header | payload | ...
           ^         ^
        p - 8        p   <- malloc() returns p; free(p) reads p-8

  header (one common layout):
    size of this block, in bytes   (low bits unused -> reused as flags)
    in-use / free bit
    [optional] link to next free block

Each block carries a hidden header just before the pointer you receive. free(p) steps back from p to read the size and flags.

The free list: a chain through the holes

Now the central idea of this whole rung. When you free() a block, the allocator does not return its bytes to the kernel — that would be slow, and you will probably ask for a block that size again soon. Instead it marks the block free and threads it onto a free list: a linked list of every chunk currently available for reuse. The clever part is that a free block's payload is, by definition, not being used by your program, so the allocator stores the list's next-pointer inside the free block itself. The free list costs no extra memory; it lives in the holes.

With that list in hand, malloc(n) becomes a search: walk the free list looking for a block big enough to hold n bytes. Which one you pick is the placement policy, and the two classic choices teach the whole tension. First fit takes the first block large enough — fast, because you stop early, but it tends to chew up the big blocks near the front of the list. Best fit scans the whole list for the block whose size is closest to n — it wastes the fewest leftover bytes per allocation, but it is slower, and counter-intuitively it can litter the heap with tiny unusable slivers. There is no universally best policy; each trades search time against wasted space, which is the four-way tug-of-war showing up in miniature.

Splitting and coalescing: fighting fragmentation

Suppose malloc(16) finds a free block of 64 bytes. Handing over the whole 64 to satisfy a 16-byte request wastes 48 bytes — that waste-inside-a-block is internal fragmentation. The fix is splitting: carve the 64-byte block into a 16-byte piece you return and a 48-byte remainder that goes back on the free list as a smaller free block. Now you serve the request tightly and keep the leftover available. Splitting is half of how an allocator keeps memory dense; you will see it again in splitting and coalescing throughout this rung.

The opposite danger appears over time. Free a block here, free a block there, and the heap fills with small free blocks scattered between live ones — lots of free bytes in total, but no single hole big enough for a large request. That is external fragmentation, and it is the subtler, nastier failure: malloc() can return NULL while megabytes sit free, simply because they are not contiguous. The cure is coalescing: when you free a block, check whether the block physically adjacent to it is also free, and if so, merge the two free blocks into one larger free block. Do this on every free() and small holes keep healing back into big ones.

Coalescing hides a real puzzle, though. From a pointer to a block you can find the next block easily — its address is your address plus your size. But how do you find the previous block to check if it is free? You only have a pointer into the middle of the heap; there is no back-link. The classic answer is the boundary tag (Knuth's trick): write the block's size not only in its header but also in a footer at its very end. Then the previous block's footer sits in the bytes immediately before your header, so reading the word just before your header tells you the previous block's size and free bit — and you can step back to it. With a header and a footer, merging adjacent free blocks becomes a constant-time check on both sides.

Walking one allocation all the way through

Let us make all of it concrete by tracing a single malloc(24) with a first-fit free list and boundary tags. Watch how header reading, list search, splitting, and alignment all show up in one ordinary call — this is the loop the next four guides keep refining.

Round the request up. 24 bytes plus header/footer overhead, rounded up to the alignment (say 16), becomes a real block size — so you never serve a misaligned or too-small block.
Walk the free list from the head, reading each block's header size, and stop at the first free block large enough to hold that rounded size.
Decide whether to split. If the found block is much bigger than needed, carve off the remainder as a new free block, write its header and footer, and link it back onto the free list.
Mark the chosen block in-use by setting its in-use bit (size | 0x1) in both header and footer, and unlink it from the free list.
Return the pointer just past the header. The program writes its 24 bytes; later, free(p) reads p minus the header size to recover everything and begins coalescing.

Every later idea in this rung is an answer to a weakness you can already feel in that loop. The list walk in step 2 is O(n) — so guide 4 introduces size classes and segregated lists to skip straight to a list of right-sized blocks. The split/coalesce churn fights fragmentation — so guide 3 brings the buddy system, which makes splitting and merging trivially cheap by restricting sizes to powers of two. The single shared list is a contention point under threads — so guide 5 shows how jemalloc, tcmalloc, and mimalloc give each thread its own cache. You now hold the skeleton; the rest of the rung is muscle.