Memory allocators, visually

The first time I ran out of memory I was about fourteen, and it was in Turbo C on a DOS machine with 640K, and malloc returned NULL on what I was sure was a tiny request. I’d been allocating and freeing strings in a loop all afternoon, and the total I had allocated at the time was nowhere near the limit. I didn’t have the word for what had happened then. It was fragmentation, and thirty years later I still see it in production, most recently in a service of ours that was “leaking” memory that it had in fact freed.

Sam Rose’s Memory Allocation went up last week, an interactive essay where you can watch an allocator hand out and take back blocks from a little strip of memory, and it’s the best explanation of the basics I’ve seen. Go and play with it. This post is the version I’d have written with diagrams instead of animations, plus the parts I care about from having to debug this stuff: why heaps fragment, and what the allocators everyone uses do about it.

The job

An allocator manages a big region of memory, the heap, that it gets from the operating system in large chunks (brk and mmap on Linux, VirtualAlloc on Windows). Your program asks for n bytes and gets back a pointer to at least n usable bytes. Later it hands that pointer back with free, and doesn’t say how big the block was. That one detail drives a lot of the design. Since free only gets a pointer, the allocator has to be able to find the size from the pointer, and the usual way is to put a small header just before the block it returns, with the size in it.

The simplest allocator that works is a bump allocator. Keep a pointer to the start of the free space, and on each request return the pointer and move it forward by n plus the header. It’s incredibly fast, two or three instructions, and it can’t free anything individually. You throw the whole region away at once. That’s not a toy, by the way. It’s how a lot of compilers and game engines handle memory for one frame or one request, under names like arenas or regions, and it’s essentially how .NET and Java allocate new objects, which is part of why allocation in a garbage-collected runtime is cheaper than people expect. The collector takes care of the freeing part.

If you want to free blocks one at a time and reuse the space, you need to keep track of the holes.

Free lists

The classic answer is a free list: a linked list of the free blocks, threaded through the free blocks themselves (a free block isn’t holding anything, so it might as well hold the next pointer). To allocate, walk the list and find a block that’s big enough. If it’s bigger than you need, split it, hand out the front and leave the rest on the list. To free, put the block back on the list.

There are a few ways to pick the block. First fit takes the first one that’s big enough. Best fit searches for the smallest one that’s big enough, which sounds smarter and leaves behind lots of tiny useless slivers. Next fit is first fit, but starting where the last search stopped. The research, most famously a big survey of allocators from the mid-1990s, mostly says that first fit and best fit both do well on real programs, and that the choice matters less than what you do on free.

What you do on free is coalesce. If the block you’re freeing is right next to another free block, merge them into one bigger block, otherwise the heap turns into a list of small adjacent holes that could have been one big one. To do that quickly, you need to be able to find your neighbors. The block after you is easy, since your header gives your size. The block before you is harder, and the standard trick, which Knuth describes in the first volume of The Art of Computer Programming, is the boundary tag: put a copy of the size in a footer at the end of each free block too, so the next block can look just before its own header and find where its neighbor starts.

Fragmentation

Even with coalescing, a heap fragments. This is the whole problem in one picture:

That’s external fragmentation: free memory that exists but is in pieces too small to use. A C allocator can’t fix it by moving C, because the program holds a raw pointer to C and the allocator has no idea where that pointer is stored. A compacting garbage collector can, because it knows where every reference is. That’s the trade at the bottom of the whole managed-versus-native argument, and it’s why my Turbo C program died and a C# program doing the same thing wouldn’t have.

The other kind is internal fragmentation: memory inside a block you handed out that the program didn’t ask for. If you always round sizes up, to a multiple of 16 bytes for alignment for instance, the rounding is waste. So is the header. On 64-bit Linux, glibc’s malloc(1) gives you a 32-byte chunk with 24 usable bytes, and a program that allocates millions of tiny objects can easily spend more memory on overhead than on data.

Size classes

Modern allocators mostly stop treating every size as different. They pick a fixed set of size classes and round every request up to one. Then each class gets its own free list, and allocation is just “pop the head of the list for this class”, with no searching at all.

Where you put the classes is a real design decision, and it’s mostly a question about internal fragmentation. With power-of-two classes (16, 32, 64, 128…), a request for one byte more than a class rounds up to the next one, so asking for 65 bytes gets you 128 and wastes nearly half. jemalloc, the allocator FreeBSD and Facebook use, spaces its classes four to a doubling instead, so between 64 and 128 there are 80, 96, 112 and 128. Now the worst case is a request just past a boundary, 129 bytes rounding up to 160, which wastes 31 of 160 bytes, about 19%. As the sizes grow, that worst case creeps towards 20% and never reaches it, which is a nice bit of arithmetic: the gap between classes is a quarter of the power of two below, and the class is one and a quarter times that power, so the waste is at most a quarter divided by one and a quarter.

Size classes also help with external fragmentation, in a quieter way. If all the 64-byte blocks come from the same pages, and the 4 KB blocks come from other pages, then small, short-lived objects stop scattering holes between large, long-lived ones. A page full of identical slots either has room for another one or it doesn’t, and when all of its slots are free the whole page can go back to the OS. This is the slab idea, which Jeff Bonwick described for the SunOS kernel in 1994, and almost every serious allocator since has some version of it.

Threads

Everything so far assumes one thread. With many threads, one heap with one lock becomes the bottleneck, and every allocator worth using deals with that somehow. glibc’s malloc (ptmalloc) creates multiple arenas, separate heaps that threads get spread across, so they don’t all fight over one lock. Google’s tcmalloc, which stands for thread-caching malloc, gives each thread a small cache of free blocks per size class, so most allocations don’t take a lock at all, and only go to the shared heap to refill or drain the cache. jemalloc does both, and Microsoft Research’s mimalloc, from a few years ago, goes further and keeps many small free lists per page instead of one big one per size class, so that frees and allocations on the same page stay close together in memory.

On Windows, which is where I spent most of my career, HeapAlloc has its own version of all this. The Low Fragmentation Heap, which is essentially size-class buckets on top of the regular heap, was something you had to opt into on XP and became the default in Vista, and I remember a lot of server code getting quietly faster around then without anyone touching it. Windows 10 added a newer segment heap, used for some system processes and apps, that I haven’t had any reason to look at closely.

There’s also a security angle, which I’ll keep at the conceptual level. Because classic allocators keep their bookkeeping, the headers and free-list pointers, right next to the data the program is writing, a bug that writes past the end of a buffer doesn’t only corrupt the neighboring data, it corrupts the allocator’s own records. A big part of the hardening in modern allocators is about making that bookkeeping harder to corrupt or easier to check, and it’s the reason heap bugs show up in CTFs at all. I’ve done badly at enough heap challenges to have a healthy respect for the people who do well at them.

Our “leak”

Which brings me back to production. Last year we had a Ruby job-processing service whose memory grew steadily over a day or two, from about 600 MB per process at start to well over 2 GB, until the container got killed and restarted. It looked exactly like a leak. We spent most of a week on heap dumps from inside Ruby, and the number of live Ruby objects was flat the whole time. The garbage collector was doing its job. Ruby wasn’t holding the memory. Underneath Ruby, glibc was.

What we had was the multi-arena behavior from the section above, fragmenting badly. The service ran a couple of dozen worker threads, glibc had created an arena for many of them, and each arena had ended up holding on to a scatter of partly used pages that it couldn’t give back to the OS, because a few long-lived objects were pinned in each. Lots of free memory, all in the wrong places, and nothing could move the objects in the way. The diagram above, at a much larger scale.

The fix that’s been going around the Ruby community for years is setting the environment variable MALLOC_ARENA_MAX=2, which caps the number of arenas, and the other well-known fix is to load jemalloc instead of glibc’s allocator. We tried both. Capping arenas brought the steady state down to around 900 MB, with a small slowdown we couldn’t reliably measure. jemalloc brought it to about 750 MB and was a little faster, and that’s what we run now. Nobody wrote any Ruby.

This is a different animal from a real leak, like the .NET statics and event handlers I wrote about in 2007, where the program really is holding references it should have dropped and the fix is in the code. The tools for finding a real leak, heap dumps and object counts, tell you nothing about fragmentation, and that’s what cost us the week. If the object counts are flat and the process keeps growing, look underneath the runtime, which we eventually did, on day four.