Memory Allocation Primer

Nothing manages the stack. A call reserves its locals by subtracting from rsp, the return adds the same number back, and there is no free list, no search and no metadata anywhere in that. Below, the frames already on the stack sit above the one the current call just pushed. Walk the slider through the call depth:

Notice that nothing is searched. The pointer moves by the frame's own size and the allocation is finished; the deallocation is the same instruction with the sign flipped. It is also why a pointer into a frame that has returned is worse than stale — the bytes are still there, and the next call overwrites them.

The price is that the region is fixed. Linux gives 8 MiB by default, and a 1 MiB guard gap below it that nothing may map. Pick a frame size and push the recursion past the limit:

Where it dies depends entirely on the frame. With 64-byte frames the stack takes 131,072 calls; at 8 KiB of locals it takes 1,024, so the same recursion is safe in one function and fatal in another. Push it past the limit and the failure is at least loud: the guard gap has no mapping, so the first touch is SIGSEGV at the instruction that made it.

Anything that has to outlive its call goes on the heap instead, and the heap is just a region the kernel will extend on request. Drag the break and watch what one brk buys:

Five calls buy the whole thing. glibc asks for 128 KiB more than it needs on every growth — M_TOP_PAD — so a program that allocates 640 KiB in small pieces makes five brk calls, not five thousand. The syscall amortises away; what is left is the bookkeeping inside the region, and that is the allocator.

The break is one number, though, so it can only give back what lies above the highest live allocation. Move the allocation that is still in use and watch the rest stop being returnable:

Because the break is a watermark, a single 48 KiB allocation at the top pins 592 KiB beneath it — free as far as the allocator is concerned, resident as far as the kernel is concerned. This is the commonest reason a healthy process looks like it is leaking, and no amount of free fixes it, because free was never the thing that returns pages.

glibc writes one 8-byte word immediately before the pointer it hands you: the chunk's own size, which is how free(p) knows how big p was without being told. Everything past your request is alignment. Drag the request and watch what the rounding adds:

The arithmetic is exact — (n + 8 + 15) & ~15, floored at 32. malloc(24) costs 32 bytes and malloc(25) costs 48, so one byte of request buys sixteen bytes of chunk. And malloc_usable_size reports 24 for a 17-byte request, because the next chunk's size word is only in use while this chunk is free.

A fixed word plus a 16-byte grid is a proportional tax on small objects and a rounding error on large ones. Walk the request across four decades and watch the overhead collapse:

Watch the left end. malloc(1) takes 32 bytes for one — 3,100% — and a linked list of 24-byte nodes lives in 32-byte chunks, so a quarter of the list is size fields nobody reads. That is the real argument for pools and arenas: not that malloc is slow, but that per-object bookkeeping never amortises when the object is small.

Past a threshold the arena stops being the right answer and glibc goes straight to the kernel instead. Slide the request through 128 KiB and watch the path change:

At the boundary the path changes, not the size. The chunk becomes a mapping of its own, rounded up to whole pages, and every allocate-and-free pair costs two syscalls where it cost none. Freeing one raises the threshold to that size — up to 32 MiB — so a program recycling 1 MiB buffers pays the syscalls once and then stops.

The gap between what you asked for and what you got is also where the quietest heap bug lives. Drag the write past the end of a 17-byte allocation and watch what it reaches:

That allocation really owns 24 usable bytes, so the first seven bytes past the end land in padding nobody reads and change nothing: the test passes, the review passes, the bug ships. Byte eight overwrites the next chunk's size field, and the crash arrives at an unrelated free much later. Loud failures are the lucky ones.

The list is in free order, not size order, so the first chunk big enough and the smallest chunk big enough are usually not the same chunk. Set a request, switch the rule, and watch how much of the list gets read:

Notice the trade at malloc(104). First fit reads two chunks and shreds a 512-byte one to serve 112; best fit reads all eight and leaves 64 behind. Neither is free — first fit is cheap and destroys large chunks, best fit preserves them and is O(n). Size classes buy both by indexing the list instead of walking it.

Putting a chunk back is the other half, and it is the half that stops the list growing without bound. Choose an order and step through the frees:

The number to read is the largest run, not the total. Every free checks its two neighbours and merges at most twice, whatever it merges into, so a sequence of frees that collapses the whole heap into one chunk still costs constant time each. Keep one chunk in the middle alive and 304 free bytes never become a run larger than 224.

Which list a chunk goes back to is decided by its size alone, and glibc has four answers to that. Walk a chunk size across them:

Because the first three are indexed, a free and the malloc that reuses it are both a pointer write and a pop. Only largebins are searched, and in size order — which is why the allocator's worst case lives above a kilobyte and its common case has none. The tcache is the newest of the four and the reason glibc caught up: added in 2.26, seven chunks per bin, no lock at all.

glibc's classes are the 16-byte grid from the last section, with the size word in front of every object. jemalloc's are four per doubling — 8, 16, 32, 48, 64, 80, 96, 112, 128, 160 — with no per-object header at all, because the metadata lives in the slab. Switch the table and move the request:

The two tables lose in opposite places. At 16 bytes glibc takes 32 and jemalloc takes 16, because a fixed word doubles a tiny object. At 513 bytes glibc takes 528 and jemalloc takes 640, because four classes per doubling puts the next class a quarter above the last.

Plotted across the whole small range, the two tables have exactly one crossing. Walk the request through it and read both wastes at once:

They cross at 129 bytes. Below it glibc's grid is finer and the header is the whole cost; above it jemalloc's class spacing dominates and peaks at exactly 25%, one byte past a boundary — at 8,277 bytes jemalloc pays 23.7% where glibc pays 0.1%. A 65-byte struct costs 80; packing it to 64 gives a fifth of it back.

The class is half the design. The other half is the slab it is cut from, and a slab is whole pages, so the page count is chosen to make the tail small. Pick a class and watch the slab follow it:

An awkward class takes more than one page, because the slab is sized to minimise the tail: 112-byte regions strand 64 bytes in a single page and 16 across two. The shape of the answer is what matters — one bitmap per slab instead of one header per object, which is how a 16-byte allocation gets to cost sixteen bytes. Neither table is wrong; they are priced for different distributions, and if your hot allocation is a 9 KiB buffer, size it to a class rather than argue with the allocator.

One arena, one mutex, and every malloc on every thread queues for it. In the model below the critical section is 8 ns — index a bin, unlink a chunk, write two pointers — against 40 ns of work outside it. Add threads and watch the curve leave the straight line:

Notice where it stops. The lock serves one allocation every 8 ns however many threads want one, so throughput saturates at six threads and the next twenty-six buy nothing at all. The constants are modelling choices; the shape is not. Any fixed critical section gives a flat line, and the only real fix is to stop taking the lock.

Which is what a per-thread cache is for. glibc's tcache holds seven chunks per size class and asks nobody's permission. Free chunks without allocating any back:

Watch the eighth. Up to seven, a free is a push onto a thread-local singly linked list — no atomic, no lock, a dozen instructions — and the matching malloc is the pop. The eighth spills into the arena and pays for the lock. Sixty-four bins cover every request up to 1,032 usable bytes, which is most of them.

The other half of glibc's answer is simply to have more locks: a thread that finds the main arena busy is given an arena of its own, up to eight per core. Raise the thread count and watch what gets reserved:

Each of those arenas is its own 64 MiB mapping, so sixty-five threads on a sixteen-core box reserve 4 GiB of address space before allocating anything. It is virtual, not resident, so it costs nothing until touched — and it is also the number a container limit reports as a leak. MALLOC_ARENA_MAX=2 is the one-line fix, and it buys the contention back.

One pattern defeats all of it: a chunk allocated on one thread and freed on another. Raise the remote share and compare the two ways of handling it:

Because a chunk belongs to the arena it came from, glibc has to take that arena's lock to give it back, so the freeing thread serialises against the owner. At half remote the model's sixteen threads fall from 1,081 to 234 million allocations a second. mimalloc pushes the chunk onto the owning page's atomic free list instead — one compare-and-swap, with nothing to queue behind.

So a heap can grow while the program's demand does not. Below, every cycle frees a scattered third of the live allocations and immediately allocates the same number of bytes back, so the live total is constant to the byte. Run the cycles, then ask the heap for something:

Notice which number answers a request. After thirty cycles there are 768 free bytes and the largest single run is 352, so a 512-byte request fits nowhere and the heap has to grow — with the live set still the 3,360 bytes it started at. Total free is a statistic; the holes are what you actually have.

That growth is permanent in the only sense an operator cares about. Drag along two minutes of a bursty workload and compare resident with live:

Watch the two curves separate at the first burst and never meet again. The peak becomes the floor for resident: free returned those bytes to a bin, the pages stayed mapped and stayed dirty, and two minutes later the kernel is still charging for 440 MiB while the program uses 180. RSS is a running maximum unless something hands pages back on purpose.

Something can. jemalloc runs a decay purger that madvises pages the program has not touched for a while. Set the window and watch the ceiling come down:

The window has to be shorter than the gap between bursts. At ten seconds resident follows live all the way down; at thirty it never purges at all, because a page is dirty again before its window closes. And purging is not free — re-faulting 260 MiB costs about 67 ms of minor faults, paid by whoever touches those pages next.

Three different mechanisms draw the same graph if you only read the last point. Pick one and walk the trace:

Two of them land within 5 MiB of each other at two minutes and they are not the same bug. Fragmentation reaches 410 MiB by climbing and decelerating, because holes do get reused eventually; a leak reaches 415 on a straight line with no plateau, and it is the only one whose fix is in your code. Rounding gives itself away by flattening at 229. The shape over an hour is the diagnosis; the number at the end is not.

If nothing in a region is ever freed on its own, allocation stops needing a data structure at all — a pointer that only goes one way, a compare against the limit, a branch. Fill the nursery and put the two costs side by side:

The ratio is the whole story. Filling all 8 MiB with 48-byte objects is 174,762 allocations: 0.35 ms of bump pointer against 2.1 ms of tcache hits — and the tcache hit was already the fast path. There is no free list and no size class. The runtime still writes an object header, but it writes it for the type system, not for the allocator.

The bill arrives at collection time, and the shape of the bill is the whole point. Set how much survives and watch what gets touched:

Watch what is not touched. A copying collector walks the survivors, moves them out, and reclaims everything else by setting the pointer back to the start — so the garbage costs nothing and the cost is linear in what lives. At 10% survival that is 0.10 ms of copying on top of 0.35 ms of allocating, still 4.6× cheaper than malloc and free for the same objects.

Moving is the part malloc cannot copy, and it is not a matter of effort. Drag the chunk sideways and look at what the program is still holding:

Because a C pointer is the address, moving the chunk leaves the pointer naming whatever now lives at the old address. A collector may move because it knows every root and every reference and can rewrite them; malloc was never told where its pointers went. That is why a C heap can only be defragmented by restarting the process.

So the collector escapes fragmentation altogether — and charges for the room it needs to do it. Set the heap as a multiple of the live set:

Hertz and Berger measured the three points this curve interpolates: at five times the live set a generational collector matches explicit malloc and free; at three times it runs 17% slower; at twice, 70% slower. That is the trade in one number. The choice is not fast against slow — it is whether to spend memory or spend your own attention on lifetimes.

They only diverge on two of the four. For a single-threaded tool all three tie, and glibc wins by already being linked. On a pipeline at sixteen threads — allocate on the producer, free on the consumer — glibc runs at a fifth of mimalloc. On a bursty service the throughput ties and the resident set does not: 432 MiB against 191.

Three things worth flagging in review, all of them consequences above:

• malloc in a hot loop over objects under 64 bytes. The header is a quarter of the object. Hoist it, or use an arena.
• A struct sized just past a class boundary. 65 bytes costs 80 — sizeof it and pack it to 64.
• Alerting on VSZ. It counts arenas nobody has touched. Alert on RSS, and on its slope.

The rung that matters is the last one. A fresh 1 MiB mapping costs 256 µs before the program has read a byte of it — 128,000 times a bump allocation — and none of it shows up in a throughput benchmark, because the second iteration amortises it away. It is exactly what a p99 graph is made of.

/* the chunk one malloc(n) really takes */
size_t c = (n + 8 + 15) & ~(size_t)15;
if (c < 32) c = 32;      /* MINSIZE   */
/* usable = c - 8                     */
/* own mmap when c >= 128 * 1024      */