A Picture Is Worth 1024³ WORDs
Sigma loaded new Haskell code while it was running. After a while it couldn’t load any more. The memory wasn’t full. It was fragmented.
Code that has to live below 2 GB
This is the system from That One Time It Was Glibc, a couple of years earlier. Jon Coens described it in 2017: the frequently changing code is built as an object file, loaded into the running server, and the old one is dropped once nothing refers to it. The object files were loaded by GHC’s own linker, and that came with a limit:
Files like these can only be loaded into the lower 2GB of memory (x86_64 small memory model uses 32 bit relative jumps), which can become restrictive when your object file gets large. Since the update mechanism relies on having multiple objects in memory at the same time, fragmentation of the mappable address space can become a problem.
On Linux it can be tighter still.
By default GHC’s linker asks the kernel for such memory with MAP_32BIT, and the kernel hands those mappings out of the upper half only, from 1 GB to 2 GB.
The comment in the kernel source says “Give it 1GB of playground for now.”
The linker can be told where to start instead, with +RTS -xm, and then the space below 1 GB is usable too.
Simon Marlow, who wrote most of GHC’s runtime, was on our team, so I’m sure we used the best flags and took all we could get.
The pictures below use 2000 MB.
A new object before the old one goes
New code was loaded about every ten minutes. The server keeps serving requests with the old code until the new code is loaded. So for a moment both are in memory, and then the old one goes. In a code review from 2016 I put it this way: “We load and unload in a FIFO manner”.
One file, several pieces
At first the linker put a whole object file below 2 GB, as one block. In 2015 Simon changed that, and his commit says why:
Previously we would map the entire object file using MAP_32BIT, but the object file can consist of 75% or more symbols, which only need to be present during linking, so this is wasteful. In our particular application, we’re already running out of space here.
The application was Sigma. Since that change the linker maps the file above 2 GB to read it, and puts below 2 GB only what has to be there:
Each big section becomes a mapping of its own. The small sections are copied into 4 KB pages that a small allocator inside the linker hands out. The linker also adds a table with 16 bytes for every symbol in the file, which it uses to reach things that are more than 2 GB away from the code. For a big object that table is megabytes, so it gets a mapping of its own too.
Each of those mappings goes to the lowest address where it fits, which is how the kernel searches for mappings like these. So one object is several pieces, and they don’t have to end up next to each other.
Looking at the address space
After a while we were unable to load new objects. I built a visualizer for the process’s memory mappings to see why. It drew one row of the pictures below: the address space at one moment.
I don’t have it any more, so I had a clanker draw time-lapses from a model. The model has 2000 MB of address space and a load every ten minutes. Its small allocator is copied from GHC’s source. How big the pieces are is my guess. When I say an object is 600 MB, I mean what it puts below 2 GB, and its code is the biggest piece, 56% of that.
Pages in the way
The small allocator fills up to 32 pages at a time, and when none of them has room it maps one more page, wherever the kernel puts it.
It never reused a page. When an object was unloaded and its small sections were freed, their page still counted as full, and it stayed mapped for as long as the allocator kept it on its list. So new objects kept needing fresh pages, and each fresh page landed at the lowest free address there was at that moment, somewhere among the pieces of the objects.
Each row is one load, and it shows where the pieces of the new object went. The objects are about 600 MB, give or take 20, and they don’t grow.
In the upper half the black lines are pages. Each one starts when the allocator needs a fresh page and then runs down the picture, because the page stays. A piece of an object can’t lie across a page, so the address space on the left is cut into narrower and narrower columns. After three hours a 617 MB object arrives. Its code is 346 MB and has to go in one piece, and the biggest hole is 330 MB, with 1384 MB free.
In March 2016 I landed a fix for that in GHC. The allocator now reuses a page once nobody else is using it, and it gets its 32 pages as one block up front:
m32_allocator will preallocate the “filling” area, so that the pages it allocates end up as a big chunk instead of being allocated on demand in random places, fragmenting the precious lower 2G address space.
My first version asked the kernel for those 32 pages one at a time, and when I tested it they came back next to each other. Simon pointed out in the review that nothing guarantees that, so the final version asks for one block.
In the same review I wrote what we had been seeing:
The live memory should easily fit into 2 pages, but without reuse we ended up allocating up to
M32_MAX_PAGESpages, before any of them would stop being “filling” pages and end up beingmunmaped.
The lower half of the picture is the same objects with the fix. The block is the single line at the left edge, and the pieces go wherever there is room.
In twelve runs of the model without the fix, a load failed in nine, after 3 to 18 hours. With the fix, none of the twelve had a failed load in 400 loads, which is almost three days.
Even then
The size of the object file fluctuated organically as the code was developed, and the trend was general growth. With that, things still break, in a way that is hard to guess.
Here the allocator is the fixed one. The objects are a little bigger, about 680 MB. They still vary by up to 20 MB, and now they also grow by half a megabyte per load:
For twelve hours every load succeeds. Then a 734 MB object arrives. Its code is 411 MB and has to go in one piece, and the biggest hole is 406 MB, with 1238 MB of the 2000 free.
A swap needs room for the new object while the old one is still there, and the pieces of the old one sit wherever the swaps before it left room. Nothing is leaking, and nothing is in the way any more. There is simply no hole big enough, long before the address space is full.
In twelve runs like this one the first failure came after 12 hours to 2 days, with objects between 734 and 837 MB.
The price
The price was stale code or service unavailability.
Restarting a server that has reached that state gets it out of it. But how do you avoid a restart storm? The obvious next fix would be rolling restarts.
It was more complex than that, and more complex than these pictures. Depending on how requests were routed, some servers sometimes kept three objects at once. In the model, with objects of about 600 MB that grow the same way, a server that holds on to a third object for one load in ten has its first failed load within a day, where the others last a day and a half to three.
The way out
By 2017 the write-up said “we’re running out of options”, and named the way out: true shared objects, which can be loaded anywhere. That is the change from That One Time It Was Glibc.
Worth writing
A counter can tell you how much of the address space is free. It takes a picture to show why that doesn’t help. The visualizer drew one row of these pictures, a 1024³ WORDs.