Memory Allocation and the Allocator: What malloc Actually Does

Hook #

When you called malloc(64) in the C course — or every time Ruby created an object, or Python grew a list — something had to find 64 free bytes in the heap, mark them used, and hand back a pointer. When you free them, something has to reclaim that space and, ideally, stitch it back together with neighboring free space so a later large request can succeed. That something is the memory allocator, and it's one of the most quietly important pieces of software on your machine — it runs on nearly every object creation, and its design decides whether your program's memory stays tight or bloats and fragments over time. The virtual-memory course showed you how the OS hands pages to a process. This lesson is the layer above: how a process carves those coarse pages into the fine-grained allocations your program actually asks for, and why doing that well is harder than it looks.

What you'll be able to do by the end of this lesson #

• Distinguish the two layers: the OS gives a process large chunks of address space (via the page mechanism from last course); the allocator sub-divides those into the small blocks your code requests.
• Explain internal vs. external fragmentation and why external fragmentation is the allocator's central enemy.
• Describe how a free-list allocator works: tracking free blocks, splitting on allocation, coalescing on free.
• Explain the classic placement policies (first-fit, best-fit, worst-fit) and the trade-off each makes between speed and fragmentation.

A quick try before we start #

Imagine a heap with 100 bytes free, but split into two 50-byte gaps with a used block between them. A request for 60 bytes arrives. Before reading: can it be satisfied? (No — there's 100 bytes free total, but no contiguous 60.) That gap between "enough total free space" and "no single chunk big enough" is external fragmentation, the problem that shapes every allocator design in this lesson. Feeling why it's a hard problem is the whole setup.

Why this matters here #

Allocators are invisible until they hurt, and then they hurt in ways that are baffling without this lesson. Memory fragmentation is a real production problem — a long-running Ruby or Java process whose memory usage creeps upward not because of a leak but because the allocator can't coalesce freed space back into usable chunks. The reason Ruby applications sometimes benefit from jemalloc over the system malloc is entirely this lesson: jemalloc's different fragmentation behavior can meaningfully lower a Rails app's memory footprint, and knowing why lets you make that call deliberately instead of cargo-culting a config flag. When you reason about memory bloat, choose an allocator, or size a heap, you're working at the layer this lesson explains.

Within the course, this lesson establishes memory management from the program's side, complementing the OS's side from last quarter. Last course, virtual memory was about the OS mapping virtual pages to physical frames. This course is about what happens within a process's allocated memory — how the heap is managed, how it grows (via the sbrk/mmap syscalls that ask the OS for more pages), and how allocation and freeing are implemented. The Memory Allocator project makes this concrete: you'll build a real malloc/free with a free list, and every design decision in that project is a topic from this lesson.

The engineer's lens #

The idea worth carrying is that an allocator is a resource manager solving the exact bin-packing problem you meet at every scale — and its core moves (split, coalesce, pick a placement policy) recur wherever you manage a pool of a divisible resource. A free list is a data structure tracking available chunks; allocation splits a chunk to fit; freeing coalesces adjacent free chunks so future large requests can be served. This is precisely the shape of a connection pool, a thread pool, a slab of pre-allocated buffers, a disk's free-block manager (which you'll meet later this course), even how a cloud scheduler packs containers onto machines. The placement-policy trade-off is the transferable insight: first-fit is fast but leaves small unusable gaps near the start; best-fit minimizes wasted space per allocation but is slower to search and paradoxically can create many tiny unusable fragments; worst-fit tries to keep large blocks available. There is no universally best policy — it depends on your allocation pattern — which is the same "no free lunch" you saw in cache replacement and CPU scheduling. Once you see allocation as bin-packing-under-uncertainty, every pool you ever manage inherits this lesson's vocabulary.

The second lens is the two-layer structure, which is a general systems pattern: coarse-grained wholesale from the layer below, fine-grained retail to the layer above. The OS deals in pages (4KB chunks) because managing memory byte-by-byte at the OS level would be absurdly expensive. But your program wants a 24-byte struct, not a 4KB page. So the allocator sits in between, buying pages wholesale from the OS (rarely, in bulk) and retailing small blocks to your code (constantly, cheaply), amortizing the expensive syscall across thousands of fast in-process allocations. This "batch expensive wholesale operations, serve cheap retail from a local pool" pattern is everywhere — it's connection pooling (expensive TCP handshake amortized across many queries), it's buffering (one big write instead of many small ones), it's how a CDN caches. The allocator is the archetype of amortizing an expensive boundary crossing, and recognizing the pattern helps you design any two-tier resource system.

What to focus on in OSTEP (Free-Space Management) and CS:APP §9.9 #

• The free-list mechanics: splitting and coalescing. These are the two operations that make dynamic allocation work. Coalescing (merging adjacent free blocks on free) is the anti-fragmentation move; understand why an allocator that splits but never coalesces slowly dies.
• Fragmentation, internal vs. external. Internal = wasted space inside an allocated block (you asked for 24, got a 32-byte block). External = free space that's too scattered to use. Know which policies fight which.
• Placement policies as a trade-off, not a ranking. First-fit, best-fit, worst-fit each win under different allocation patterns. CS:APP's treatment makes the speed-vs-fragmentation tension concrete.
• Skip on first pass: the deep internals of production allocators (jemalloc/tcmalloc arenas, size classes, thread caches) and buddy-system math. Know they exist as sophisticated answers to fragmentation and multithreaded contention; the free-list foundation is what the project needs.

Explain it back #

Explain to a colleague why a long-running process's memory can keep growing even without a memory leak. A strong answer names external fragmentation: as blocks of varying sizes are allocated and freed, the heap develops scattered gaps that can't be coalesced into large-enough contiguous regions, so the allocator asks the OS for more pages rather than reusing the fragmented space. Bonus: explain why switching to a different allocator (e.g. jemalloc) can help — different fragmentation and arena strategies.

Where this connects #

Backward: Last course's virtual memory (the allocator gets its raw material — pages — from the OS via the page mechanism you learned; malloc growing the heap is sbrk/mmap asking for more virtual pages). Fragmentation echoes the contiguity concerns from arrays (Course 2.1) and the free-block problem foreshadows this course's file systems.

Forward: Lesson 2 covers what the OS does with those pages under memory pressure — swapping, copy-on-write, memory-mapped files. Lesson 5's Ruby GC lens is the automatic-allocation counterpart: a garbage collector is an allocator that also decides when to free, and it fights the same fragmentation battles. The free-block management in lesson 3's file systems is this same problem on disk.