How a program gets memory and gives it back.

Memory allocation is how programs request and release memory at runtime. The stack grows and shrinks with function calls (LIFO, fast); the heap handles dynamic allocations through malloc/free or a garbage collector. Production allocators — jemalloc, tcmalloc, mimalloc — manage size classes, free lists, and per-thread arenas to avoid fragmentation and contention.

When the OS launches a program, it hands it a virtual address space — typically 256 TB on 64-bit Linux. That space is partitioned: text (the executable code), data (initialized globals), bss (uninitialized globals), heap (dynamic, grows up), thread stacks (one per thread, grow down), shared libraries, and at the top, the kernel reserves space for itself.

None of these regions are physically contiguous. The page table maps virtual to physical pages on demand — see how virtual memory and the TLB work for the four-level walk every load actually performs. Reading /proc/self/maps shows the layout: every distinct entry is one VMA (virtual memory area), tracked by the kernel.

The stack is a LIFO region tied to a thread. Each call frame is pushed on entry and popped on return — bumping a register. Allocation is one instruction; deallocation is automatic. The trade is shape: stack memory is sized at compile time, and the lifetime is exactly the call. Recursion or huge locals will blow the stack.

The heap is a free pool with arbitrary lifetimes. You ask for memory, you get a pointer, you free it whenever. Allocation is bookkeeping — find a chunk that fits, split, return. Deallocation is more bookkeeping — coalesce neighbors. Threads contend on the same heap, so allocators add per-thread caches to dodge locks — the same idea behind a thread pool's per-worker queues.

Below: a 24-slot heap. Each row of "Alloc" finds a free run of contiguous slots and claims it. Free a block in the middle and now you have a hole — small allocations may use it, but a big request may have to skip it. That mismatch is fragmentation.

Modern allocators (glibc's ptmalloc, jemalloc, tcmalloc, mimalloc) all do roughly the same thing differently. They keep separate free lists for different size classes — small (under ~16 KB), medium, and large. Small allocations come from per-thread arenas (no lock needed). Medium come from per-process pools with size-class buckets. Large go straight to mmap and bypass the heap entirely.

On free, the allocator tries to coalesce — if the neighbor is also free, merge them. This fights fragmentation but costs CPU. tcmalloc and jemalloc lean on size classes to skip coalescing in the hot path; they accept some internal fragmentation in exchange for speed.

External fragmentation is what the simulator above shows: enough total free memory exists, but no single contiguous run is large enough. Mitigations: power-of-two size classes, bump allocators, occasional compaction (in GC'd languages), or just plain mmap'ing a fresh region.

Internal fragmentation is rounding waste — you ask for 17 bytes, you get a 32-byte slot, and 15 bytes are unused. Smaller size classes reduce it but increase metadata cost. Most allocators target ~10% waste in steady state.

If you allocate millions of one fixed size — kernel objects, network buffers, pooled structs — a general-purpose allocator wastes both space and time. The slab allocator (Bonwick, 1994; in Linux as the SLAB/SLUB subsystem) keeps caches of pre-initialized fixed-size objects per size class. Allocation: pop from a freelist. Free: push back. Constant time, no metadata, no fragmentation within the slab — close kin to a ring buffer for fixed-shape records.

Userspace equivalent: object pools. Game engines, network servers, and JIT compilers maintain pools of "things I will need many of" — connections (pooled the same way a Redis client multiplexes them), render commands, AST nodes. The cost saved is not just the allocator call but cache warmth and metadata.

An mmap(64 GB) succeeds on a 4 GB machine. It just reserves virtual addresses; no physical pages are bound. The first time you write to a page, the CPU traps, the OS allocates a 4 KB physical page, updates the page table, and resumes you. This is a minor page fault — typically a few microseconds.

Major page faults are different: the OS has to read from disk (anonymous swap, or a backing file). They are 10,000× slower. RSS (resident set size) shows physical pages currently bound; VSZ shows virtual reservation. They differ by orders of magnitude in normal programs. On multi-socket machines, where physical pages get allocated also matters — see NUMA and memory bandwidth for why first-touch placement is one of the most common production-perf bugs.

Use-after-free: free() returns memory to the allocator. If you keep the pointer and read it, you read whoever got the slot next. The allocator may even rewrite the bytes immediately (debug builds explicitly do — 0xdeadbeef, 0xfeedface).

Double free: passing the same pointer twice corrupts the free list. Modern allocators detect this with magic numbers and abort; older ones just silently mis-track.

Leak: alloc without matching free. Not always fatal — short-running programs can leak forever — but in long-running services, RSS climbs until OOM. AddressSanitizer (ASan) and Valgrind catch all three at the cost of 2–5× runtime.

ptmalloc / glibc malloc

The default on Linux. Has per-thread arenas, bins by size class, fastbins for small allocs. Decent baseline; loses to specialised allocators on multi-threaded workloads.

jemalloc · 2005, FreeBSD/Facebook

Per-thread caches with arena assignment. Battle-tested at Meta scale; default in Rust until 2018. ~10-30% faster than glibc on multi-threaded server workloads, lower fragmentation.

tcmalloc · Google

Thread-Caching malloc. Per-thread free lists with size classes; central heap when caches drain. The allocator behind every Google service. Open-sourced separately as part of Abseil.

mimalloc · Microsoft 2019

The latest allocator from Microsoft Research; benchmarks show ~10% faster than jemalloc/tcmalloc on common workloads with simpler internals (~3,500 LOC). Used in Azure components.

scudo · LLVM

Hardened allocator with built-in mitigations against use-after-free and buffer overflows. Default on recent Android. Trade ~10-15% performance for memory-safety bug detection.

Switching is easy. Most Linux apps can switch allocator just by linking libjemalloc.so via LD_PRELOAD. Many production teams do this for free 10-20% throughput gains on memory-heavy services. Redis, MariaDB, ClickHouse, and Cassandra all ship with jemalloc by default.

Memory leaks. The classic: allocate, forget to free. Symptoms: process RSS grows monotonically until OOM kill. Diagnosis: heaptrack (Linux) tracks every allocation and shows what's still alive. Valgrind massif for offline analysis. jemalloc's built-in profiler with the MALLOC_CONF=prof:true env var.

Fragmentation. RSS doesn't shrink even though heap usage is low — the allocator can't return free memory to the OS because of holes. More common in long-running services. Diagnosis: jemalloc-stats shows active vs resident; a large gap signals fragmentation. Fix: switch to a compacting allocator (mimalloc), or accept periodic restarts.

Use-after-free, double-free, buffer overflow. The dangerous trio in C/C++. Modern compilers detect many at runtime via AddressSanitizer (ASan) — link with -fsanitize=address and the runtime catches each invalid access. ASan adds ~2× CPU overhead; useful in CI and staging, not production. Hardware MTE (Memory Tagging Extension, ARMv8.5+) does the same in production with ~5-10% overhead.

The Rust answer. Rust's ownership system catches all three at compile time. The cost is the borrow-checker learning curve; the win is C/C++-class performance with memory-safety guarantees. Why the kernel, browsers, and security-critical systems are slowly migrating.