Putting It All Together

Every technique in a production allocator is now something you have implemented by hand:

The capstone design

Your final allocator is the front end of a real one — a recognizable miniature of tcmalloc's fast path: segregated free lists over a bump tail.

• HEAP = 32768 bytes; classes 16, 32, 64, 128, 256, 512, 1024, 2048.
• ALLOC <size>: round up to a class (OOM if even 2048 is too small). If that class's free list holds a block, pop it and print its address. Otherwise carve fresh: address = current bump, then bump += class size; OOM if the tail cannot fit the whole class.
• FREE <addr>: the block goes onto the free list of the class it was ALLOCATED as — record the class at allocation time. Anything that is not a live allocation prints BAD.
• STATS: all eight classes as class=<c> alloc=<a> free=<f> (alloc counts LIVE blocks), then bump=<b>/32768.

Trace the opening of test 0:

ALLOC 10  -> 0     class 16,   bump  0 -> 16
ALLOC 20  -> 16    class 32,   bump 16 -> 48
ALLOC 100 -> 48    class 128,  bump 48 -> 176

Addresses are spaced by CLASS sizes, not request sizes — the third allocation lands at 48 because 16 + 32 came before it, and STATS then reports bump=176/32768.

What this design trades away

A freed block here serves ONLY its own class, forever. No splitting a freed 128 into two 64s; no coalescing two 64s into a 128. That rigidity is what buys O(1) on every path — and it is how production fast paths genuinely behave. The difference: real allocators bolt an escape hatch onto the back end, coalescing at the page/span level (jemalloc runs, tcmalloc spans) so class-trapped memory eventually gets reshaped. Ours never is — a deliberate simplification you now know how to remove.

What we deliberately skipped

• mmap for big allocations: glibc sends anything over M_MMAP_THRESHOLD (128 KB by default) straight to mmap; freeing 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, randomized placement, zero-on-free — some speed traded for exploit resistance.
• GC heaps: allocator and collector co-designed, which is what makes compaction possible.

Reading that pays off: Doug Lea's "A Memory Allocator" essay, Bonwick's slab paper, jemalloc's design notes, CS:APP chapter 9. You now know what every malloc, new, and object allocation actually does.

Your exercise

Hidden test 5 checks class rigidity head-on: ALLOC 50 (class 64, address 0), ALLOC 100 (class 128, address 64), ALLOC 200 (class 256, address 192), FREE 64, then ALLOC 60. The new 64-class request must NOT touch the freed 128-class block: the grader expects address 448 — a fresh carve off the bump tail — with STATS showing class=128 alloc=0 free=1 and bump=512/32768. Printing 64 means you handed a 128-class block to a 64-class request: sharing across classes is the feature this design explicitly gives up. And ALLOC 5000 must print OOM — no class holds it.