The Second Half of Memory Management

The Memory Management topic covered virtual memory: how the OS gives every process an address space and maps pages. This topic is about what happens inside that address space — the heap, the region where programs allocate and free variable-sized objects. Every malloc, new, make, or String::new is handled by an allocator, and how it works decides throughput, memory overhead, fragmentation, and even security.

The practical punchline: allocation is not free, is not O(1), and its cost model is why every serious runtime (Go, Rust, Java, Node) ships its own tuned allocator rather than relying on the system’s.

From brk and mmap to a Heap

A process’s heap starts small. On Unix, the C library grows it with brk/sbrk (extend the data segment) for small allocations, and mmap for large ones (a fresh, separate mapping). On Windows, HeapCreate/VirtualAlloc play the same roles. But calling the OS for every allocation is far too slow — the kernel round-trip and page-table work dwarf the allocation itself. So the runtime creates a user-space heap: a large chunk of virtual memory it manages itself, calling the OS only occasionally to grow it.

That distinction is the key mental model: the allocator manages memory in user space; the OS only supplies and reclaims pages.

Free Lists and Fitting Strategies

The heap is a set of blocks: some live (in use by the program) and some free (available for reuse). The allocator tracks free blocks in a free list. When the program asks for N bytes, the allocator must pick a free block — a fit — of at least N:

• First fit — walk the list, take the first block big enough. Fast, tends to fragment the front of the heap.
• Best fit — walk the whole list, take the smallest block big enough. Minimizes waste per allocation but costs a full scan and leaves tiny unusable fragments.
• Next fit — like first fit but resume the scan where the last allocation stopped. Spreads the load, avoids the “front-loaded” pattern of first fit.

When a block is returned (free), the allocator coalesces adjacent free blocks back into one — otherwise fragmentation grows monotonically. Coalescing is why freeing memory “looks” trivial in languages with manual allocation but is actually a list surgery.

Segregated Lists

A general free list has to search and coalesce, which costs. Real allocators cheat with size classes: they keep a separate list per common size (16 B, 32 B, 64 B, 128 B, …). A request for, say, 50 bytes goes to the 64-byte list — a lookup, not a search. This is the segregated free list design behind glibc’s fastbins, jemalloc, and Windows heaps. The trade-off is internal fragmentation: a 50-byte request wastes 14 bytes inside its 64-byte slot, and tiny “leaks” of rounding add up.

Thread Caches and Arenas

Contention is the second cost: a heap guarded by one lock becomes a serialization point under many threads. Two standard fixes:

• Thread caches — each thread owns a private cache of free blocks (per-thread bins); most alloc/free operations touch only the thread’s cache and never the shared lock. When the cache overfills, blocks trickle back to the shared heap.
• Arenas — instead of one global heap, the allocator maintains several independent heaps (arenas); threads are assigned to arenas, reducing cross-thread contention. glibc malloc uses arenas (default: up to 8× the core count) plus per-thread tcache; jemalloc (used by FreeBSD, Rust) and Go’s runtime push the same idea further.

The design goal is the same as every concurrency fix: make the common case lock-free and per-thread.

Kernel Slab Allocators

The kernel itself allocates small, fixed-size objects constantly — inodes, file descriptors, PCB entries, socket buffers. A general-purpose malloc would fragment and waste. Instead, the kernel uses slab allocators (slab, slob, slub on Linux): a cache per object type, pre-filled with a batch of same-size objects; allocating an inode is “pop from the cache,” freeing is “push back.” This is the kernel analog of a segregated list, specialized by type rather than just size — and it’s why cat /proc/slabinfo shows named caches like inode_cache.

External vs Internal Fragmentation

Two fragmentation costs to keep distinct:

• External fragmentation — free space is split into blocks too small to satisfy a request, even though total free memory is ample. The classic disease of variable-size allocation; coalescing and segregated lists fight it.
• Internal fragmentation — a block is larger than requested (size-class rounding, page rounding at the OS level). The waste lives inside allocated blocks and is invisible to a free-list scan.

Paging (from Memory Management) already eliminated external fragmentation at the page level; allocators reintroduce both kinds within a page-sized region. This is why a “10 MB heap” can’t actually satisfy ten 1 MB allocations when fragmentation has left nothing contiguous.

Overcommit and the OOM Killer

Most operating systems practice overcommit: they let programs allocate virtual memory far beyond physical RAM, betting that not all of it will be touched. This is why malloc can return a valid pointer for a gigabyte on a machine with 512 MB — the pages are only committed when written. The bet fails when everything is touched: then the kernel must free memory urgently.

• On Linux, the OOM killer picks a process to kill (scored by a heuristic — memory use, root status, lifetime) and signals it.
• On Windows, commit limits are enforced more strictly at allocation time.

The engineering consequences: reserve large buffers carefully, treat allocation failure as a real state, and understand that a process killed by the OOM killer often was not “running out of memory” so much as losing the race for resident pages.

Heap Safety and Exploitation

The heap is a favorite attacker target, and its design shapes the attack surface:

• Heap overflow — writing past an allocated block corrupts the metadata of the next block; with careful layout, an attacker redirects the free list. glibc’s old unlink bug was the canonical example.
• Use-after-free / double free — freeing a block twice corrupts the free list into a write primitive; tcache poisoning exploits the per-thread cache the same way.
• Defenses — heap metadata hardening (checksums, list integrity cookies), safe-linking, guard/shield allocators, ASLR for heap base, and compiler sanitizers (-fsanitize=address) that detect the bugs during development.

This is the bridge from allocator design to the OS Security topic: every performance optimization in the allocator (fast free lists, thread caches) is also a potential corruption primitive if the metadata isn’t defended.

Worked Example: Why a Thread-Cached Allocator Wins

A server allocates and frees a 100-byte request object per incoming request, on 16 threads:

1. With one global heap: every malloc/free takes the global lock; under 16 threads the lock serializes allocation, and top shows the threads spinning.
2. With per-thread tcache: each thread pops/pushes from its private cache — lock-free in the common case. Only cache refills drain the shared heap.
3. With arenas: threads spread across independent heaps, further cutting contention.

The same server sees allocation time drop from a contended mutex to a few pointer operations — which is exactly why high-concurrency runtimes bundle their own allocator.

Practice Trajectory

1. On Linux, run a malloc-heavy program under ltrace/strace and count how often brk/mmap are actually called vs how many mallocs happened — observe the amortization.
2. Use malloc_info (glibc) or a heap profiler (heaptrack, valgrind massif) to view arenas, fastbins, and size-class usage in a real program.
3. Write a program that allocates and frees blocks in an adversarial order and measure the virtual vs resident memory (/proc/<pid>/smaps, or Task Manager commit) — watch overcommit in action.
4. Trigger the OOM killer deliberately in a container with a hard memory cgroup limit; read dmesg for the kill decision.
5. Compile a small use-after-free with -fsanitize=address and watch it catch exactly the heap state the safe-linking defenses are meant to frustrate.

When It’s the Right Tool