Memory Allocation Primer

Every new in C++, every malloc in C, everyBox::new in Rust eventually asks the OS for memory and then carves it up. Five sections build the picture: stack vs heap and how brk / mmap actually grow the heap; malloc & free internals with an interactive heap layout; modern jemalloc / tcmalloc / mimalloc and why they exist; fragmentation — internal, external, leaks; and a quick reference.

Stack vs heap — and how the heap actually grows

Every process has both. The stack is cheap, automatic, and bounded; the heap is flexible, manual, and where every allocator lives. The kernel grows the heap on request through two surprisingly different syscalls.

The stack is a fixed region (default 8 MB on Linux) that grows downward as functions are called and shrinks upward as they return. Allocation is essentially free — just decrement rsp. Deallocation is also free — incrementing rsp on return discards everything. The catch is that every byte on the stack is gone the instant the function returns; you can't share stack data across function calls without copying. And the size cap is rigid: overflow it and you get a SIGSEGV (sometimes via a kernel guard page).

The heap is everything else. Anything that needs to outlive a function call, anything whose size isn't known at compile time, anything that grows or shrinks at runtime — lives on the heap. C's malloc, C++'s new, Java's and JS's object allocations, Rust's Box, Go's escaped values — all heap.

How the kernel gives the heap memory

Two syscalls grow a process's heap:

brk (and sbrk): classic Unix. Sets the data-segment boundary to a new high-water mark, and all addresses between the old and new mark become valid. Used by allocators for small allocations because growing/shrinking by a few KB at a time is cheap.
mmap with MAP_ANONYMOUS: create a fresh, file-less VMA somewhere in the address space. Allocators use this for large allocations (default threshold in glibc: 128 KB) because they can be returned to the kernel independently when freed.

The difference matters operationally. brk can only release memory from the top of the heap — if you have a small allocation at the top-of-heap watermark, the entire heap below it stays mapped even after everything below is freed. mmap-allocated regions can be munmap'd in any order. This is why long-running processes that allocate lots of small objects often appear to leak memory to ps even when the working set isn't growing: the glibc allocator can't return the brk-allocated heap to the OS.

RSS vs VSZ

VSZ is virtual size — the total mapped address space. RSS (resident set size) is the actual physical pages in RAM right now. A process with 2 GB VSZ and 100 MB RSS has allocated 2 GB of virtual memory but only touched 100 MB worth of pages. RSS is what costs you physical RAM; VSZ matters only when it exceeds what page tables can cheaply describe (~256 GB on 4 KB pages before becoming a real concern).

The compiler also helps

Modern compilers do escape analysis: if a heap allocation never "escapes" the current function (it's not stored in any field, returned, or passed to anything that might retain it), the compiler can hoist it onto the stack. Go does this aggressively; C++ and Rust do it via inlining + dead-code elimination on small types; Java's JIT does it as "scalar replacement." The result is that idiomatic code in these languages often runs without heap touches in hot loops despite what the source looks like.

The takeaway. "Stack: cheap, bounded, function-local. Heap: flexible, manual, the allocator's domain. The kernel grows the heap via brk (small / fast / can't easily release back) or mmap with MAP_ANONYMOUS (large / can be munmap'd). RSS is physical memory consumed; VSZ is virtual space mapped — the former is what costs RAM."

What `malloc` and `free` actually do

The allocator's job is to carve a contiguous slab of OS-given memory into request-sized pieces, track which pieces are live, recycle freed ones, and grow the slab when it runs out. Most of the complexity is in fighting fragmentation.

malloc(n) returns a pointer to n bytes of uninitialised memory. free(p) tells the allocator that pointer is no longer in use. Between these two calls, the allocator is responsible for: (1) finding a free chunk of the right size, (2) recording bookkeeping so it knows the chunk's size on free, (3) handing back aligned memory (typically 16-byte aligned for SSE compatibility).

Free lists and size classes

The simplest allocator keeps a single linked list of free chunks and walks it to find one big enough (first-fit) or smallest that fits (best-fit). Both are O(n) per allocation, terrible at scale. Real allocators use size classes: bucket allocations by size (typically powers of 2 or some other geometric series like 16, 24, 32, 48, 64, ...) and maintain a separate free list per bucket. Allocation becomes O(1): round up the request to the nearest size class, pop the head of that bucket's free list.

The cost: internal fragmentation. A 17-byte allocation rounded to 24 wastes 7 bytes per allocation. With millions of allocations, this adds up. Modern allocators use finer-grained size classes (jemalloc has ~40 buckets up to a few KB) to keep internal waste below 10%.

1 / 8

Real allocators are more sophisticated than this simple bump-and-merge — they maintain free lists organized by size class, coalesce adjacent free blocks, and reuse holes when they can. But the fundamental problem stays the same: even with all free memory totalling enough, the largest contiguous run may not be large enough for the request. That's external fragmentation, and it's what jemalloc / tcmalloc / mimalloc spend most of their effort fighting.

Coalescing

When a chunk is freed, the allocator checks whether its neighbours are also free; if so, it merges them into a single larger free chunk. This coalescing is what prevents external fragmentation from compounding indefinitely. The standard implementation puts a small footer at the end of each chunk so coalescing can find the previous chunk's header in O(1) by walking backwards.

Where the per-allocation header lives

Just before the pointer you got from malloc, the allocator stashes a few bytes of metadata (typically 8–16 bytes) recording the chunk size and a flag or two. This means: (1) every allocation has at least that much overhead — small allocations are ratio wasteful; (2) writing past the end of an allocation corrupts thenext chunk's header, which is detected only on the next allocation/free, far from the bug; (3) free(p)knows the size by looking at the bytes just before p.

Why C's built-in `malloc` is rarely the best choice

glibc's malloc (ptmalloc) is fine for many workloads but loses to specialised allocators on three axes: multi-threaded scaling (per-thread arenas, next section), memory return to OS (it's sticky), and tail-latency under contention (locking inside the allocator). Production code at scale almost always overrides it with jemalloc, tcmalloc, or mimalloc viaLD_PRELOAD — typically a 10–30% throughput win and often dramatic improvements in 99th-percentile latency.

The takeaway. "malloc finds a free chunk, stamps a header on it, returns it. freeputs it back on the free list and tries to coalesce with neighbours. Real allocators bucket by size class for O(1) and maintain per-bucket free lists. The hardest problem is external fragmentation — total free isn't the same as largest contiguous free, and small holes accumulate over time."

jemalloc, tcmalloc, mimalloc — why modern allocators exist

Single-threaded malloc is essentially a solved problem. Multi-threaded malloc on 32+ cores is not — and three landmark allocators have each carved out a different design point in the trade-off space.

The thread-contention problem

A naive allocator wraps its data structures in a lock. With one thread that's fine; with 32 threads all calling malloc in a tight loop, the lock becomes the bottleneck and the allocator scales no better than a single thread. Pre-2008 glibc malloc had exactly this problem.

The fix everyone settled on: per-thread caches (or arenas). Each thread keeps a small local pool of free chunks it can serve allocations from with no lock at all. When the local pool runs dry or overflows, the thread synchronises with the global pool — but that's rare. The bookkeeping is more complex (per-thread state, periodic balancing, locks at the global tier), but the common-case allocation is lock-free.

jemalloc

Originally from FreeBSD (2005), adopted by Facebook (now Meta) for their backend ~2009. Per-thread caches (tcache) backed by a small number of global arenas (typically 4× the number of CPUs). Allocations are size-classed into ~40 buckets up to ~14 KB; anything larger goes through a separate slab system. Strong on fragmentation control (sophisticated coalescing) and on returning memory to the OS (active purging). Industry default for high-allocation-rate server workloads; Rust's default until recently, Redis's default in many builds.

tcmalloc

Google's contribution (~2006, rewritten as "tcmalloc next generation" in 2019). The original variant uses per-thread caches with a global pageheap and a CentralFreeList per size class. Optimised for short-lived small allocations (the workload Google traces dominated by hash-table churn and protobuf objects). Has a sampling-based profiler that gives you pprof-compatible heap profiles for free.

mimalloc

Microsoft Research, 2019. The newest of the three, designed for a clean implementation (~6000 LOC for the whole allocator) and first-class support for embedding in language runtimes. Per-thread heaps with per-page free lists, distinguished by being explicitly designed for the "free in a different thread than you allocated in" case (common in async runtimes and message-passing systems). The data-locality story is unusually good — sibling allocations stay near each other in the address space, which helps cache behaviour. Roughly competitive with jemalloc/tcmalloc on macro-benchmarks; better on some, worse on others.

When to switch

The default glibc malloc is fine for many CLI tools and single-threaded workloads. Switch to one of the above when:

Multi-threaded server with high allocation rate.Per-thread caches give 2–5× throughput improvement at 16+ threads.
RSS grows over time despite stable working set. Glibc struggles to return memory; jemalloc actively purges viamadvise(MADV_DONTNEED).
Tail latency matters. Allocator lock contention shows up as p99 spikes that don't correlate with anything else.
You need heap profiling. tcmalloc's pprof integration is the easiest way to find where allocations happen without recompiling.

Switching usually means LD_PRELOAD=/path/to/libjemalloc.soon the command line, or linking it as a dependency. No code changes needed.

The takeaway. "Single-threaded malloc is solved. Multi-threaded scaling requires per-thread caches: jemalloc (the FB default, best fragmentation), tcmalloc (Google's, best profiling), mimalloc (Microsoft's, best for cross-thread frees and embedding). Switching via LD_PRELOAD is often 10–30% throughput + lower p99 latency for free."

Fragmentation, leaks, and the difference

Three distinct ways a process's memory grows without bound, each with different mechanism and different fix. Mixing them up is the single most common source of memory-debugging confusion.

Internal fragmentation

The allocator gives you 24 bytes when you asked for 17. The 7 wasted bytes are internal fragmentation: they belong to your allocation but you can't use them. Caused by size-class rounding (every modern allocator) and alignment requirements (malloc'd memory is typically 16-byte aligned). Typical waste: 5–15% of total allocated memory for general-purpose workloads. Cheap allocators with coarse size classes waste more; fine-grained ones less.

Fix: choose size-class-aware allocators (jemalloc, mimalloc); avoid many distinct "just under a class boundary" allocations (a 65-byte struct gets rounded to 80 in jemalloc — pack it down to 64 if you can).

External fragmentation

The heap has plenty of free bytes in total, but no single contiguous chunk large enough for a new request. The HeapAllocator demo in §2 shows the basic case. The allocator must either fail the request (rare) or extend the heap by asking the kernel for more memory (common — and that memory grows RSS even though the existing fragments could have absorbed many small requests).

Fix: coalescing helps (every real allocator does it). Per-size-class free lists prevent it within a class but allow it across classes. Long-running processes with mixed allocation sizes inevitably accumulate some — the question is the rate. Restarting the process is the brute-force fix and is widely used (rolling restarts in production).

Memory leaks

The application allocates memory, loses all references to it, but never calls free. Classic causes: forgetting to free in C/C++; cycles in reference-counted data (Rust's Rc / Python's reference counting); growing caches without eviction; unbounded queues. Net effect: RSS grows monotonically with workload, not with concurrent load.

Garbage-collected languages don't have classical leaks but do have retention bugs: a global cache, an event listener that captures a closure over a large object, a static map that grows without bound. Same operational symptom as a C leak. Heap dumps (jmap, V8's heap snapshot) identify the retention root.

How to tell them apart

RSS climbs with throughput but plateaus. Likely internal fragmentation — total allocations grew because workload grew, but every chunk-class is well-utilised. Switching allocator may help; otherwise just budget for it.
RSS climbs slowly over hours/days even at steady throughput. External fragmentation. The allocator can't recompact the heap, so brk-allocated pages stay mapped even when mostly unused. Switch to an allocator that purges back to the OS (jemalloc with default settings).
RSS climbs linearly with cumulative requests served, never plateaus. Leak. Some allocation per request is never freed. Tools: valgrind --leak-check=full for C/C++; ASan (-fsanitize=address) for compiled languages; heap profilers (jemalloc's, tcmalloc's, V8's) sample allocation sites.

The RSS = max() problem

RSS only ever grows (or stays the same) — it almost never shrinks. Once the allocator has touched a page it's in RSS, and pages get returned to the kernel only on explicit madvise ormunmap. So even a brief spike in working set can leave the process's long-term RSS elevated. Modern allocators run background purging threads to mitigate this; older ones don't.

The takeaway. "Internal fragmentation: requested fewer bytes than the size-class bucket holds, the rest is wasted but consistent (5–15% typical). External fragmentation: total free is fine but no contiguous chunk fits — grows over time, mitigated by coalescing and active purging. Leaks: never call free, monotonically grow with cumulative work. The shape of the RSS-over-time graph is the diagnostic."

Quick reference

Six questions worth being able to reason about cold, and five red flags to spot in a code review.

What's the difference between stack and heap allocation?

Stack: allocation is decrementing rsp (zero cost); memory lives only until the function returns; bounded size (~8 MB on Linux). Heap: allocator finds a free chunk, stamps a header, returns it; memory persists until free; bounded only by virtual address space. Anything outliving a function call goes on the heap.

What two syscalls grow a process's heap?

brk (and sbrk) moves the data-segment boundary, growing the heap contiguously. Cheap, but memory can only be returned to the OS from the top — a small allocation at the top keeps the entire heap below mapped. mmap MAP_ANONYMOUS creates an independent VMA; can be munmap'd in any order. glibc uses brk for small allocations and mmap for >128 KB by default.

Why are jemalloc / tcmalloc / mimalloc faster than glibc malloc?

Per-thread caches. glibc's default (ptmalloc) uses arenas locked by a mutex; under contention from many threads the lock becomes the bottleneck. jemalloc, tcmalloc, and mimalloc each give every thread a private cache of free chunks it can serve from lock-free. Allocation becomes O(1) and contention-free in the common case. The throughput win is 2–5× at 16+ threads.

What's the difference between RSS and VSZ?

RSS (resident set size) is physical memory currently allocated to the process. VSZ (virtual size) is the total virtual address space mapped — including parts not yet touched (still zero in page tables) and parts swapped to disk. RSS is what costs you RAM; VSZ matters only when it's huge enough to bloat the page tables themselves. A process with 1 TB VSZ and 200 MB RSS is fine.

Distinguish internal fragmentation, external fragmentation, and a memory leak.

Internal: you asked for 17 bytes, the allocator gave you 24; the extra 7 are wasted but counted as "in use." Stable overhead (5–15% typical). External: plenty of free bytes total, but no single contiguous run is large enough; the heap grows over time. Leak: allocation is never freed; RSS grows monotonically with cumulative work. Different shapes on an RSS-over-time graph; different fixes.

When would you choose mmap directly over malloc?

Three cases: (1) very large allocations (multi-MB) where you want easy return to the OS — direct mmap is cleaner than relying on the allocator's decisions; (2) shared memory between processes — mmap with MAP_SHARED on a file or shm region; (3) memory-mapped files where you want OS demand-paging instead ofread/write overhead. For everything else, let the allocator handle it.

Red flags in code review

malloc/free in a hot inner loop. Each call is ~50 ns plus potential lock contention. Hoist allocations out, use a pool, or stack-allocate via alloca/VLAs where bounded.
Many tiny allocations of similar size. Even with per-thread caches, the per-chunk overhead dominates. Use an arena allocator or a slab.
Long-lived caches without an eviction policy. Especially in garbage-collected languages, an unboundedHashMap/dict/Map appears as a memory leak even though it's "reachable." Use an LRU or bound the size.
Mixing many distinct fixed-size allocators in the same process. Each one has its own bookkeeping overhead. Consolidate.
Calling free from a different thread than allocated, with default glibc malloc. ptmalloc's arenas degrade badly under this pattern; switch to mimalloc or jemalloc, which are designed for it.