What an Allocator Does Under the Hood

Where the bytes actually come from

Here is a question the earlier guides quietly dodged: when you call malloc(), who actually has the memory? The kernel owns all of physical memory, and ordinary code cannot just take some — a heap region is real address space that must be granted by the operating system. But the kernel hands out memory only in whole pages (typically 4 KiB) and only through a system call, which is far too coarse and far too slow to do for every little `malloc(16)`. So malloc() is not a system call. It is a plain library function living inside libc, and the heap it manages is a slab of address space it obtained from the kernel once, up front, to parcel out itself.

How does it get that slab? Historically the classic move is to grow the program break — the top edge of the heap region — with the sbrk() system call. Calling `sbrk(amount)` pushes the break up by `amount` bytes, and that newly exposed address space becomes the allocator's to sub-divide. Modern allocators more often grab big chunks with mmap() instead, but the idea is identical: take a large region from the kernel rarely, then satisfy thousands of `malloc()` calls out of it without bothering the kernel again. The win is enormous — a system call costs hundreds of cycles for the trap into the kernel, while carving a byte range out of a region you already hold is a handful of ordinary instructions.

Hidden bookkeeping: the secret bytes before your pointer

Now the question that has been hiding in plain sight since guide 1: how can `free(p)` possibly work? You hand it a single pointer and no size, yet it returns exactly the right number of bytes. The trick is that the allocator never gives you a bare block. When you ask for `n` usable bytes, it actually carves out a slightly larger chunk, writes a small header of metadata at the front of it — typically the chunk's size and a flag or two — and then returns a pointer to the byte just after that header. The address you receive is the start of your data; the bookkeeping sits invisibly a few bytes in front of it.

  malloc(24) returns p ----+
                           v
  +-----------+------------------------------+
  |  header   |   24 usable bytes for you    |
  | size=24.. |   (this is what p points at) |
  +-----------+------------------------------+
  ^
  +-- a few hidden bytes the allocator keeps

  free(p) reads the header at p - (header size)
          to learn the chunk is 24 bytes, then
          marks it free.  No size argument needed.

So `free(p)` does something quietly clever: it computes `p` minus the header size, reads the size field sitting there, and now knows the whole chunk to reclaim. This single fact explains a cluster of rules you have been told to obey. You must pass free() the exact pointer malloc() returned — pass `p + 1` and the allocator reads garbage where it expects a header, with undefined results. A double-free is dangerous because the second free() reads a header the allocator has already meddled with. And a buffer overflow that writes one byte past your block is so vicious precisely because the very next bytes are often the next chunk's header — corrupt it, and the allocator's own data structures break, sometimes long after the bad write.

The free list: a ledger of what's available

Inside its slab the allocator needs to track which chunks are in use and which are free, and it does this with a free list — a linked list threaded through the free chunks themselves. Here is the elegant part: a free chunk is, by definition, memory nobody is using, so the allocator stores its next-pointer inside the free chunk's own body. The free list costs almost no extra memory because it lives in the holes. To satisfy a `malloc()`, the allocator walks this list looking for a chunk big enough; to handle a `free()`, it flips the chunk's in-use flag and links it back onto the list.

Which free chunk should a request take when several fit? This is a genuine policy choice with real trade-offs, not a settled fact. First-fit grabs the first chunk on the list that is large enough — fast, but tends to chew up the front of the list. Best-fit scans for the chunk closest in size to the request, wasting the least leftover but searching more and leaving a litter of tiny unusable slivers. Real allocators are far more sophisticated than a single list: they keep many lists binned by size class so a request jumps near-instantly to chunks of about the right size, dodging the linear scan entirely. But every one of these is still, at heart, a free list with a search policy.

Splitting, coalescing, and the cost called fragmentation

Two operations keep the free list healthy as a program churns. When a request needs 24 bytes but the best free chunk is 200, the allocator performs block splitting: it carves off the 24 you asked for and returns the remaining 176 as a fresh smaller free chunk, so the surplus is not wasted. The reverse happens at free time. When you release a chunk, the allocator checks whether the chunks immediately before and after it are also free, and if so it coalesces them — merging adjacent free chunks back into one larger chunk. Together, splitting and coalescing are how the heap breathes: it subdivides on demand and reassembles on release, fighting to keep large contiguous holes available.

Even so, the heap loses the war sometimes, and the result is fragmentation. Picture allocating ten 1 KiB blocks side by side, then freeing every other one. You now hold 5 KiB of free space — but it is five separate 1 KiB holes with live blocks wedged between them, so a single request for 2 KiB fails, even though plenty of total memory is free. That is external fragmentation: free memory exists but is scattered into pieces too small to be useful. Coalescing cannot help here because no two free holes are adjacent. This is the honest, hard truth of manual allocation — fragmentation is an inherent cost of the model, not a bug you can simply code away.

There is a second flavour worth naming. Internal fragmentation is space wasted inside a chunk you do hold — because the allocator rounds your request up. Ask for 17 bytes and you will very likely be handed a 24- or 32-byte chunk, since allocators round up for alignment and to fit their size bins. Those extra bytes are charged to you but unusable. Neither kind of fragmentation is a sign you did something wrong; both are the standing tax for the heap's flexibility. A managed pool that lets you ask for memory by the byte, at any moment, for any lifetime, simply cannot also promise zero waste.

Putting the whole picture together

Let us trace a single `int *p = malloc(24)` through the machine, now that every part has a name. The allocator searches its free list (really its size-binned lists) for a chunk of at least 24 bytes plus header room. If the chunk it finds is much larger, it splits off the surplus. It writes the size and an in-use flag into the chunk's header, then returns the address of the byte just past that header — that is your `p`. Later, `free(p)` steps back to read the header, marks the chunk free, links it onto the list, and coalesces with any free neighbours. No kernel call happens in the common case; it is all bookkeeping inside the slab libc obtained long ago.

1. Obtain a slab: once, up front, the allocator grows the heap with sbrk() or mmap() so it has raw address space to manage.
2. Serve malloc(): walk the free list for a big-enough chunk, split off the surplus, write the size into a hidden header, and return the byte just after it.
3. Serve free(p): read the header at p minus the header size, mark the chunk free, link it back, and coalesce with adjacent free chunks.
4. Pay the standing tax: rounding up requests (internal) and scattered live blocks (external) leave fragmentation that no amount of careful coding fully removes.

Step back and see what this rung gave you. The contracts you learned in the earlier guides were never arbitrary rituals: you free the exact malloc() pointer because free() reads a header at a fixed offset before it; you never write past your block because the next chunk's header lives right there; you free once because the second free() corrupts a list it has already touched; and you cannot leak with impunity in a long-running program because the heap can only grow. The allocator is not magic — it is a small, knowable machine of slabs, headers, and lists. And if hand-managing all of this sounds exhausting, that honest fatigue is exactly the motivation for what comes later: a garbage collector reclaims memory for you at a runtime cost, while Rust's ownership system enforces these very rules at compile time, no collector needed — different points on the same hard trade-off you now understand from the inside.