11. Storage Allocation

What this lecture covers

This lecture explains how memory allocators actually work underneath malloc and free, and how garbage collectors work underneath languages that manage memory automatically. It starts from the simplest possible allocator, the stack, then builds up to fixed-size and variable-size heap allocation, and finishes with three garbage collection strategies: reference counting, mark-and-sweep, and stop-and-copy.

The lecture sits after the multithreading and measurement lectures and before a lecture on parallel storage allocation, and it feeds directly into project 3 and homework 6, where students implement their own allocators. After watching, you should be able to explain why a stack allocator is fast but limited, trace through how a free-list or bin-free-list allocator services a request, and describe how each garbage collection scheme identifies and reclaims unreachable memory, including their respective weaknesses around cycles and fragmentation.

Key ideas

• Stack allocation: allocating and freeing are just incrementing or decrementing a single pointer, making it constant time and inlinable, but you can only free the most recently allocated block, which is why the C call stack uses this discipline.
• Free list: unused fixed-size blocks are linked together using their own storage as pointers; allocation and freeing are constant time, with good temporal locality but poor spatial locality (external fragmentation).
• External vs. internal fragmentation: external fragmentation means used blocks are scattered across virtual memory, hurting the page table and TLB; internal fragmentation means wasted space inside an allocated block, as happens when the bin free list rounds a request up to the next power of two.
• Bin free list: bins hold blocks whose sizes are powers of two; a request is rounded up to the nearest bin, and if that bin is empty a larger block is split down. This scheme uses at most M log M virtual memory for a program with peak heap usage M, and is a constant factor (six) worse than an optimal allocator.
• Storage layout: a process's virtual address space places the stack at the top growing down, the heap below it growing up, and the BSS, data and text segments below that; because addresses are 64-bit, the stack and heap effectively never collide.
• Reference counting: each object tracks how many pointers reference it and is freed when that count hits zero; simple and efficient, but it can never collect a cycle of objects that reference each other.
• Mark-and-sweep: a breadth-first search from the program's roots marks every reachable (live) object, then a sweep pass frees everything unmarked; it handles cycles correctly but does nothing about fragmentation.
• Stop-and-copy: live objects are copied into a second memory space during the same breadth-first traversal, so unreachable objects are implicitly left behind and live objects end up contiguous, fixing fragmentation at the cost of copying overhead and using twice the space.

Walkthrough

The stack as the simplest allocator (1:05)

Allocation and deallocation on a stack are shown as pure stack-pointer arithmetic, with overflow and underflow checks typically skipped for speed since a violation is a program bug that will segfault. The C call stack itself works this way, and alloca lets a program allocate on the call stack directly, though it is deprecated in favor of heap pointers.

Why the heap is needed, and its hazards (5:08)

Because a stack can only free its most recent allocation, general-purpose programs need the heap. C and C++ give the programmer manual control via malloc/free or new/delete, which is fast but exposes the programmer to memory leaks, dangling pointers and double frees; tools like AddressSanitizer and Valgrind help catch these bugs.

Fixed-size allocation with a free list (11:09)

Unused same-size blocks are linked into a free list using their own bytes to store a next pointer. Allocation pops the head of the list; freeing pushes a block back onto the head, giving stack-like temporal locality without the stack's last-in restriction, but at the cost of external fragmentation, which is shown to hurt page-table size and TLB hit rate. Grouping blocks by page, and preferentially allocating from the fullest page, is presented as a mitigation, backed by a probability calculation showing skewed allocation increases the chance repeated accesses land on the same page.

Variable-size allocation with a bin free list (19:16)

Bins are indexed by power-of-two block size; a request is rounded up to ceil(log2(X)), and if that bin is empty, a larger block is recursively split into two smaller ones until the right size is produced. The lecture proves the scheme uses at most M log M virtual memory for peak usage M, and cites a result that it is a constant factor of six worse than an optimal allocator that knows the future, a bound shown to be tight. Coalescing adjacent free blocks (such as the buddy system) can reduce fragmentation further, though with overhead that sometimes outweighs its benefit.

Process memory layout (26:20)

The virtual address space is laid out with the stack at the high end growing down, the heap growing up toward it, and the BSS, data and text segments below. Because 64-bit address spaces are effectively unbounded, the stack and heap never actually collide, but never freeing memory is still bad because of fragmentation, page-table blowup, disk thrashing and eventually exhausting physical memory.

Garbage collection basics and reference counting (35:26)

Garbage collection frees the programmer from manually calling free, at the cost of requiring strong typing (to distinguish pointers from integers) and disallowing pointer arithmetic, which is why general-purpose garbage collection isn't practical in plain C. Reference counting tracks incoming pointers per object and frees any object whose count reaches zero, cascading to its children, but it can never reclaim a cycle of mutually referencing objects, since their counts never drop to zero.

Mark-and-sweep (43:42)

Treating objects and pointers as a graph, a breadth-first search from the roots marks every reachable object; a sweep then frees everything unmarked. This correctly handles cycles, unlike reference counting, but requires scanning all of memory and does nothing to compact the surviving live objects, so fragmentation remains.

Stop-and-copy (50:46)

Using two memory spaces (from-space and to-space), the same breadth-first search copies each live object directly into the to-space as it's discovered, using forwarding pointers left in the from-space to fix up references once an object's new address is known. Unreachable objects are implicitly discarded since they're never copied, and live objects end up contiguous, eliminating external fragmentation. The lecture works through the time cost (linear in objects, pointers and bytes copied) and the amortized-constant cost of doubling space when a from-space fills up.

Before you watch

• Review the earlier lecture on virtual memory, the page table and the TLB, since the fragmentation discussion depends on them.
• Basic graph traversal (breadth-first search) is used directly to describe both mark-and-sweep and stop-and-copy.
• Familiarity with malloc/free and common C memory bugs (leaks, dangling pointers, double frees) is assumed from the start.

Check your understanding

1. Why can a stack allocator only free the most recently allocated block, and why does that make it unsuitable as a general-purpose allocator?
2. Explain why the bin free list scheme uses at most M log M virtual memory when the peak heap usage is M.
3. Why does skewing allocations onto as few pages as possible reduce the impact of external fragmentation?
4. Why can reference counting never garbage-collect a cycle of objects, and how does mark-and-sweep avoid this problem?
5. How does the stop-and-copy algorithm both identify garbage and eliminate fragmentation in a single pass?