Model the heap as one byte buffer so malloc, free, and realloc return exact offsets you can assert against - no real pointers, no OS calls. Every lesson is one concrete spec with exact block layouts and free-list states: alignment rounding, splitting a free block, coalescing with the neighbor before, after, and both, first-fit versus best-fit picking different blocks, growing a realloc in place versus relocating it, and detecting a double free.
Over 32 lessons you build a working memory allocator from scratch, modelled as a simulated arena: one fixed backing byte buffer where every allocation returns a deterministic offset into it. That design keeps the whole thing exactly testable - real block layouts, real free-list states, real addresses - with no true pointers and no operating-system calls, so the allocator you write is the same in any language.
You start with a bump allocator that advances a cursor to get something usable immediately, then build the real thing: blocks carrying a header and a matching footer (boundary tags), an explicit free list, first-fit search, splitting a large free block, and coalescing a freed block with the free neighbour before it, after it, and on both sides. On top of that core you add first-fit versus best-fit fit policies, realloc that shrinks in place, grows in place by absorbing a following free block, or relocates and copies, calloc that zeroes, segregated size-class bins for faster allocation, and a heap-integrity checker. The capstone runs a scripted allocate, free, and realloc workload and asserts the exact final heap layout.
This is a teaching-grade allocator built around the classic boundary-tag design from CS:APP and Knuth: it manages one fixed arena, is single-threaded, and returns offsets rather than mapping real memory. It is honest about what it stops short of - it never calls the operating system to grow the heap (no sbrk or mmap), has no thread safety, and uses a simplified set of size classes - which is exactly the honest core that production allocators like dlmalloc, jemalloc, and tcmalloc extend with arenas, per-thread caches, and OS integration.
Every allocator needs memory to hand out. Ours is a simulated one - a single fixed byte buffer we call the arena - so that every allocation is just an offset into it, fully deterministic and testable. Today you build that buffer and report its size.
Create an arena of a fixed number of bytes and report how many bytes it holds.
A real allocator asks the operating system for memory and hands back pointers. That is impossible to test with exact values and different in every language, so we do the honest teaching version instead: a simulated arena. The arena is one fixed slab of bytes, and every allocation is an offset into it - a plain integer saying “your memory starts here.” No real pointers, no system calls, and every result is a number you can assert.
Today is deliberately tiny: a buffer of a chosen size that can report how big it is. That size is the total memory our allocator will ever have to work with - it never grows - so knowing it precisely is where everything starts. Every later lesson carves this same buffer into blocks.
// the whole allocator will manage space inside this one buffertype Arena struct {buf []byte // the simulated memory; offsets index into it}func NewArena(size int) *Arena { return &Arena{buf: make([]byte, size)} }func (a *Arena) Size() int { return len(a.buf) }
A genuinely working allocator over a single fixed simulated arena - boundary-tagged blocks, segregated size-class bins, splitting and both-sided coalescing, first-fit and best-fit, realloc and calloc, a heap-integrity checker, and graceful rejection of double frees and bad offsets - but it manages one fixed arena that never grows (no OS sbrk or mmap), is single-threaded with no locking, returns integer offsets rather than real pointers, and uses five fixed size-class bins.
Section 9.9 (Dynamic Memory Allocation) and the famous malloc lab are the backbone of this project - implicit and explicit free lists, boundary tags, splitting, coalescing, and fit policies, all laid out step by step.
The design writeup for dlmalloc, the allocator most system mallocs descend from. Read it for boundary tags, binning by size class, and the real-world tradeoffs a teaching allocator simplifies.
Section 8.7 builds a storage allocator in a few pages - a free list of blocks threaded through the arena, coalescing on free, and a circular first-fit search. The smallest complete allocator worth reading.
A from-scratch walkthrough of writing malloc, free, and realloc with block metadata and coalescing - the practical companion to the CS:APP chapter.
A modern, well-illustrated treatment of headers, alignment, free-list search, splitting, coalescing, and segregated lists - closely parallel to the arc built here.
Section 2.5 (Dynamic Storage Allocation) is the original rigorous treatment of boundary tags, first-fit versus best-fit, and the fragmentation tradeoffs every allocator negotiates.