Putting It All Together

Every technique in a production allocator is now something you have implemented by hand. This last lesson combines the ones that fit together into the front end of a real allocator, a miniature of tcmalloc's fast path: segregated free lists over a bump tail, with realloc on top.

The capstone design

• HEAP = 32768 bytes. Classes are 16, 32, 64, 128, 256, 512, 1024, 2048.
• ALLOC n rounds n up to a class (a request of 0 gets 16; over 2048 there is no class: OOM). If that class's free list holds a block, pop the MOST RECENTLY freed one and return its address. Otherwise carve fresh: the address is the current bump pointer, which then advances by the class size; if the tail cannot hold the whole class, OOM.
• FREE addr pushes the block onto the free list of the class it was ALLOCATED as, which the allocator recorded when it handed the block out. Anything that is not a live allocation prints BAD: an address never returned, a block already freed, an address inside a block.
• REALLOC addr n resizes a live block. The block's class is looked up; if n rounds to the SAME class the address is returned unchanged, because the block is already big enough (the cheap case that real realloc hits constantly). Otherwise a block of the new class is obtained exactly as ALLOC would, the old block is freed, and the new address is printed. If the new block cannot be obtained, print OOM and leave the old block untouched and live. A dead or unknown addr prints BAD.
• STATS prints the eight classes as class=<c> alloc=<a> free=<f> (alloc counts LIVE blocks, free blocks on the list), then bump=<b>/32768.

A trace of the opening, so you can see addresses follow CLASS sizes, not request sizes:

ALLOC 5     -> 0     class 16,  bump 0 -> 16
ALLOC 70    -> 16    class 128, bump 16 -> 144
ALLOC 3     -> 144   class 16,  bump 144 -> 160
FREE 0      -> OK    class 16 free list: [0]
ALLOC 9     -> 0     the freed block, not a new one
STATS       ...  class=16 alloc=2 free=0 ...  bump=160/32768

What this design trades away

A freed block serves ONLY its own class, forever. There is no splitting a freed 128 into two 64s and no coalescing two 64s into a 128. That rigidity is what buys O(1) on every path, and it is how production fast paths behave. The difference is that real allocators bolt an escape hatch onto the back end: coalescing at the page or span level (jemalloc runs, tcmalloc spans) so memory trapped in one class is eventually reshaped. Ours never is. A heap full of freed 2048-byte blocks cannot serve a single 16-byte request once the tail is spent, which makes realloc to a smaller class able to FAIL here. You now know how to remove that limitation.

What we deliberately skipped

• mmap for big allocations: glibc sends anything over M_MMAP_THRESHOLD (128 KB by default) straight to mmap, and freeing it munmaps it back to the OS instead of fragmenting the heap.
• Hardware memory tagging (ARM MTE): tags on pointers and memory make use-after-free trap in production at near-zero cost.
• Hardened allocators (GrapheneOS hardened_malloc, Apple's secure modes): canaries, randomised placement, zero-on-free; speed traded for exploit resistance.
• GC heaps: allocator and collector co-designed, which is what makes compaction possible.

To go further read Doug Lea's "A Memory Allocator" essay, Bonwick's slab paper, jemalloc's design notes and CS:APP chapter 9.

Common mistakes

• Handing a freed block of one class to a request of another. The freed 128 must not serve a 64-byte request.
• Popping the OLDEST freed block instead of the newest.
• Freeing the old block of a REALLOC before checking that the new one can be had, which loses the data on failure.
• Advancing the bump pointer on a failed allocation.

Your exercise

The starter holds the tables, the class lookup and STATS; you write ALLOC, FREE and REALLOC. The tests fill the heap completely, then check that freed blocks of the wrong class do not help, that LIFO order holds, and that a failed REALLOC leaves the original block alive.