The hotel of addresses

The last chapter ended with an experiment that is hard to wrap your head around. A C program splits in two with a call to fork, the child changes a variable, and both processes print its address. The address is the same and the values differ: 99 in the child, 10 in the parent. If an address is the number of a memory cell, as we have assumed since Chapter 14, one cell can’t hold two numbers at once. So the address a program sees is not the number of a cell. Every program believes that all of memory belongs to it alone. To understand how this illusion holds up, what it costs and where it breaks, you will have to work the front desk.

The number on the key and the number of the room

Imagine a hotel with odd rules. Every guest gets keys numbered from one to a million, as if the whole hotel were theirs. The building has only a few hundred rooms, and the number on a key doesn’t match the number of a room. When a guest heads for “their” room 4012, the desk clerk opens that guest’s book, finds the line “4012” and takes the guest to room 37. The guest next door also has a key 4012, but in that guest’s book the line says room 108. The guests never meet and can’t meet: nobody will take them to someone else’s room.

That is how the memory of every modern computer works. The numbers a program uses to name memory cells are virtual addresses, the numbers on the keys. The numbers of the cells in the chips themselves are physical addresses, the rooms. The set of all virtual addresses a process may use is its address space: every process has its own, which is why the same number in two processes leads to different cells. The whole system of translation is called virtual memory. The desk clerk is a unit inside the processor, the MMU (memory management unit), and it translates every address on every memory access, billions of times a second.

You can see your own address space. The Linux kernel keeps its map in the file /proc/self/maps, one line per region: where it begins and ends, what may be done with it and where it came from. The cell below looks up on the map where a list, a big buffer, Python’s own machine code and the stack live.

The ctypes microscope from Chapter 14 found three addresses: the list itself, the buffer’s data and one function inside the interpreter, written in C. The list lives in a big nameless region where Python lays out its small objects. The ten megabytes of the buffer got a region of their own, sized to fit. The machine code sits in a region mapped from the library file libpython. The second column holds the permissions: r is read, w is write, x is execute as instructions, and p means the region is private, the process’s own. Data regions have rw-p, code has r-xp: code can be executed but not rewritten. There are about a hundred regions, and between them lie huge stretches of emptiness, addresses that nobody ever gave the process. And the variable x from the last chapter was given to both processes, but in the two books the same number points to different rooms.

Manchester, 1962. A one-level store

In the 1960s virtual memory appeared in machines from Burroughs and IBM, in the 1970s it became the norm on big computers, and it came to personal computers with Intel processors: in segments with the 80286 (1982), and in pages, the scheme described here, with the 80386 (1985). Today not a single phone works without it. How does the desk clerk manage the book when there are millions of rooms and hundreds of guests?

Pages and rooms

The first difficulty is plain to see: a book with a line for every address would be bigger than the memory itself. As on Atlas, translation is therefore done in chunks. The address space is cut into pages, usually of 4096 bytes, and physical memory into frames of the same size. A page, like a guest, can live in any frame, and nothing is rearranged inside a page: byte number 100 of the page ends up as byte number 100 of the frame. So an address splits into two parts. $4096 = 2^{12}$, so the low 12 bits are the offset within the page, and everything above them is the page number. This is the shift and the mask from Chapter 28: the page number is address >> 12, the offset is address & 0xFFF.

The clerk’s book is the page table. For every page of the process it records the frame the page is in, plus a few flags: whether the page is in memory at all, whether it may be written, whether it may be executed as code, whether an ordinary program may use it or only the kernel. Two more flags are set by the processor itself: “the page has been accessed” and “the page has been written to.” Translating an address is a one-liner: find the page’s frame in the table and attach the same offset to it. Take your place behind the front desk.

The same digit on a key takes guests A and B to different rooms. That settles the mystery of the two processes: the address of the variable x is the same, but the parent and the child have different page tables, and after the write that address leads to different frames in them. Why the address matched at all, and what the write has to do with it, will become clear in the section on copying.

A book in four volumes

The second difficulty is the size of the book itself. On an x86-64 processor a virtual address takes 48 bits. Such a space holds $2^{48} / 2^{12} = 2^{36}$ pages, about 69 billion, and if each got an 8-byte line, the table of a single process would take 512 GiB. But a process uses a tiny fraction of its space: on the map we saw about a hundred regions amid emptiness. So the book is built as a tree. The page number is cut into four more pieces of 9 bits each. The first piece picks a line in the table of contents, the table of contents points to a volume, the second piece picks a line in that volume, and so on four times, until the last line names a frame. Every table has $2^9 = 512$ lines of 8 bytes: one page. And volumes without a single page given out are never created at all. This is the trie from Chapter 27, except that its letters are 9-bit pieces of an address.

Four numbers from 0 to 511 are the clerk’s path through the four volumes to the frame that holds the list. Your numbers will be different: the system places regions in the address space at random, to make it harder for an attacker to guess what lies where. For the newest processors even 48 bits are too few, and they have a fifth volume: 57-bit addresses.

The clerk’s notebook

Four volumes mean four extra memory reads for every access the program makes, and there are billions of accesses. If the MMU leafed through the book every time, memory would become five times slower. What saves the day is the same thing that saved it in Chapter 34: locality. A program goes to the same pages again and again: along an array, into the same function, to the top of the stack. So the clerk keeps a notebook with the last few translations, the TLB (translation lookaside buffer), a cache of translations inside the processor. It holds from a few dozen to a couple of thousand “page → frame” lines, and usually more than 99% of accesses find their translation there without opening the book.

The notebook has one drawback, and we have met it before. A translation depends on the process: page 0x1 of guest A and page 0x1 of guest B are different rooms. So on a context switch, which we met in the last chapter, the old process’s entries in the TLB become useless: either the notebook is wiped and the new process starts with misses, or every entry is tagged with a process number. This is one more hidden cost of a switch. Programs that need gigabytes, such as databases or neural network training, ask the system for huge pages of 2 MiB or even 1 GiB: one line of the notebook then covers 512 or 262,144 times more memory.

A call in the night: the page fault

Sometimes the line in the book says “no room.” Then the clerk wakes up the owner of the hotel. The processor, failing to find the page in memory, raises a page fault. It is an interrupt like the ones in the last chapter, only it is raised by an instruction of the program itself rather than by the timer. The operating system kernel looks at which page this is. If it was never given out, that is a bug in the program, which we come to below. If it was, the kernel finds a free frame, puts the right contents in it, writes the frame into the table and runs the instruction again. The program notices nothing except a delay.

Page faults are what makes virtual memory lazy. When a program asks for memory, the system puts nothing into frames: it only notes in the book that these numbers have been given out. A frame appears on the first write. The course sandbox gets 256 MB of physical memory. We ask for 600.

The mmap module asks the kernel for a piece of address space directly, which is also how Python itself takes memory for big objects. The kernel agreed to give out 600 MB of addresses, more than the sandbox has, and not a single kilobyte more was taken in the chips. We touched 100 MB, and exactly 100 MB more became occupied. The first write to each page costs noticeably more than the second: its price includes the page fault, the trip into the kernel, and finding and zeroing a free frame. The second write is only a write. On the course server the difference is even larger: there an extra protective layer handles the fault. Ask for 1200 MB instead of 600 and mmap refuses: the sandbox has a separate limit of a gigabyte on addresses.

That is why any task manager shows two memory figures for a program. One is how many addresses it has taken, the other how many frames it occupies; in Linux they are called VSZ and RSS. The first can be huge and means almost nothing. If a program “weighs” ten gigabytes of virtual memory and two hundred megabytes of resident memory, those two hundred are all it has taken from its neighbors.

The annex: swapping

Because addresses are lazy, more can be handed out than there is memory. But the guests may well all move in at once. Then the owner of the hotel moves someone out to the annex. The kernel picks a frame, writes its contents to disk, to a special file or partition, the swap space, marks the former tenant as “in the annex” in its page table and gives the freed frame to the newcomer. When the evicted page is needed, a page fault happens, and the kernel brings the page back from disk, moving someone else out. If the page hasn’t changed since it moved in (program code, for example), it needn’t be written to disk: a copy is already in the program’s file. That is what the processor’s “written to” flag in the table is for.

The illusion of endless memory holds as long as the annex gets the guests who won’t be needed for a long time. But a disk is vastly slower than memory: a memory access takes about a tenth of a microsecond, a fast SSD about a hundred microseconds, an old hard disk milliseconds. Every miss costs as much as a thousand memory accesses, or even a hundred thousand. Suppose a program goes round and round fifty pages and gets sometimes more rooms, sometimes fewer. As in Chapter 34, we evict the one that has gone longest without being needed (LRU).

As long as there are at least fifty rooms, misses happen only on the first round, when the pages move in for the first time. Take away a single room, and every access becomes a miss, and the average cost jumps almost fortyfold, all at once, with no gradual slowdown. LRU on a loop slightly bigger than memory always guesses wrong (we saw that in Chapter 34), but other policies won’t help much here either: there are more pages needed right now than there are rooms. The set of pages a program uses in the near term was named the working set by Peter Denning in 1968. If the working sets of all processes don’t fit in memory, the system spends almost all its time hauling pages back and forth, and useful work stands still. This is thrashing. Everyone knows the symptoms: the computer stops responding, the disk runs nonstop, and the processor is nearly idle, because everyone is waiting for the disk. There is only one cure: close some programs, so that the working sets of the rest fit.

Whom to move out

You know the policies from Chapter 34: by arrival (FIFO), the one unused for longest (LRU), a random one, and Bélády’s unreachable ideal: evict the one that will be needed latest of all. Pages have a difficulty of their own. A processor cache tracks every access by itself, in hardware. But the kernel can’t keep an exact LRU for pages: it would have to move a page in a list on every memory access, billions of times a second. What the kernel does have is the “accessed” flag, which the processor sets by itself.

That flag is what the clock policy, or “second chance,” is built on. The frames stand in a circle, like the numbers on a dial, and a hand goes round them. When a frame has to be freed, the hand looks at the flag of the next one. If the flag is up, the page has been used recently: the hand lowers the flag, leaves the page and moves on. If the flag is down, nobody has used the page since the hand last came round, and that page is moved out. One bit per page instead of a list, and a choice almost as sensible as LRU’s. Modern systems run more elaborate descendants of this clock.

More rooms, more moves

The example from that paper fits in twelve accesses. Guests knock on pages 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. We play them through with three rooms and with four, evicting whoever moved in first.

With three rooms there are nine misses, with four there are ten. Where it all goes wrong shows in the seventh line, when the 5 arrives. In three rooms the tenants at that point are 4, 1, 2: the 1 and the 2 moved back in moments ago, they are young, and the 4 is evicted. In four rooms the 1 and the 2 were hits, so the 1 has lived there from the start: it is the oldest, and it is the one evicted. And the next two guests are the 1 and the 2. A first-come policy looks at when a page moved in, not at when it is needed, and the extra room changes the order of moving in so that the wrong page gets evicted.

Hunt the anomaly yourself. A red ring on the chart appears where an extra room gave more misses. At the bottom, two runs stand side by side, with the chosen number of rooms and with one more: they show at which guest the two parted ways.

The LRU and OPT curves never go up, however long you search, and this can be proved.

Policies with this property, where the contents of the smaller memory are always contained in the contents of the larger, were later called stack algorithms; LRU and OPT are among them. FIFO breaks the property, and the seventh line of the cell shows how: three rooms hold 1, 2, 5, four rooms hold 2, 3, 4, 5, and the 1 isn’t there. The clock isn’t a stack algorithm either, and it can be anomalous too. How rare is the anomaly? We check on twenty thousand random sequences.

A few dozen sequences out of twenty thousand for FIFO, none for LRU, as the theorem promises. Rare, but not unheard of. Bélády and his coauthors built sequences on which FIFO with extra memory missed almost twice as often, and conjectured that it never gets worse than twice. Then in 2010 Fornai and Iványi showed that for FIFO the ratio of misses with more memory to misses with less can be as large as you like.

Locks on the doors

The clerk’s book also guards the guests. Every page in the table has permissions: whether it may be read, written, executed as code, whether an ordinary program may go there or only the kernel. The MMU checks them on every access, along with the translation and at no extra cost. A violation also causes a page fault, only this time the kernel sees that the page is in place but forbidden, or that the process was never given such an address at all. There is nothing to fix here, and the kernel sends the program the signal SIGSEGV, number 11. If the program doesn’t catch it, it dies with a message known to everyone who has written C: segmentation fault. The word “segment” is left over from an older protection scheme, in which memory was divided into segments.

The most common case is a null pointer. The page with address 0 is deliberately given to nobody, so an access through NULL is always caught and never quietly spoils someone else’s data. The second case is writing where you mustn’t. The mprotect call changes a page’s permissions on the fly: we hang a “read only” lock on a room and try to write to it.

Both programs are killed by signal 11, but at different moments. The first got nothing done; the second wrote, read and died on the first write after the lock. Both print to stderr for a reason: ordinary output collects in a buffer and is lost with the process in a crash, while stderr goes out at once. Put your debugging output before a suspicious spot there too.

The death of a recursion without a base case from Chapter 33 now makes sense too: below the stack the system leaves pages that are never given out, and when the frames grow into them, the MMU raises the alarm. Python doesn’t let things get that far: it checks the recursion depth and the bounds of lists itself and raises an exception with a traceback. But Python can segfault too, in C extensions or through ctypes. Then the process dies silently. The faulthandler module helps: when a crash happens, it manages to print the Python line where it happened.

Exit code −11 means “killed by signal 11.” Without faulthandler, not a word; with it, the line where it all happened. Remember the switch -X faulthandler (or the environment variable PYTHONFAULTHANDLER=1): if a Python program with C libraries sometimes vanishes without a traceback, this is the first step.

The same locks guard the kernel. The kernel’s memory is mapped into the address space of every process, but its pages are marked “kernel only,” and an ordinary program gets SIGSEGV the moment it tries to peek in. This is the wall that the Meltdown attack from Chapter 35 broke through: the processor checked the permissions too late and managed to read the forbidden data speculatively. The 2018 patch took the kernel out of ordinary processes’ page tables almost completely (only a tiny piece remained, the one used to enter and leave the kernel), and every system call became a little more expensive: entering and leaving the kernel now swaps the clerk’s book itself.

One room for two

Back to the mystery of the last chapter. fork makes a copy of a process with all its memory. If the process takes a gigabyte, copying a gigabyte on every such call would be ruinous, all the more so because the shell starts every command with fork followed at once by exec, and throws the copy away immediately. So the kernel copies only the book. Both books point to the same rooms, and every page that may be written is marked “read only” in both books. As long as the parent and the child only read, they live in the same frames. The first write is a protection violation and a page fault. The kernel sees that the page is shared and that the lock on it is temporary, copies the page into a new frame for the writer and removes the lock. This is copy-on-write. The child from the last chapter wrote 99 into its x, and at that moment got a page of its own with the same number on the key.

We test it at the sandbox’s limit. A program takes 150 MB and gives birth to three children. If fork copied memory, 600 MB would be needed, while the sandbox has only 256, and the program would be killed.

Three copies of a 150 MB process appeared within a millisecond or two, and all of them lived to the end: each child read all 38,400 pages, and only the ten it wrote to were copied. You can see the same thing in the desk clerk widget: press fork and write something to the stack on behalf of C. Copy-on-write lives outside fork as well. Snapshots in file systems and in some databases are built on it: a snapshot copies nothing until the data start to change.

In Python this technique has an enemy: the reference count, the subject of the next section. Even reading an object changes its count, which means writing to the page where the object lies. So the children of a Python server process created with fork gradually copy almost all the shared memory for themselves. For such servers Python 3.7 added the function gc.freeze(): it is called before fork so that at least the garbage collector itself leaves the old objects alone.

Housekeeping: Python’s memory

The kernel gives a process pages, and inside them Python lays out its objects itself, and decides itself when an object’s stay is over. You know the picture from Chapter 2: a name is a label on a string, tied to an object; an object can have many labels; an object with none left is unreachable, and Python frees its memory. And in Chapter 14 the microscope found the number of labels itself in the object’s header. That is the reference count. Every new reference (a name, a list element, an attribute of another object) adds one to it, every reference that disappears subtracts one, and an object whose count reaches zero is freed at once, with no delay. You can peek at the count with the function sys.getrefcount.

A two instead of the expected one is no mistake: while getrefcount runs, its own argument also refers to the list. The second name added one, and del took it away: it removes a label, it doesn’t destroy the object. And None and the number 7 have a count of 4,294,967,295 (that is in the sandbox’s Python 3.13; in other versions the number may differ, but it is just as huge), and it doesn’t change. Since Python 3.12 such ubiquitous objects are immortal: their count is deliberately left alone, so that thousands of references to None don’t keep writing to its page. Remember copy-on-write.

Reference counts have one blind spot: cycles. If objects refer to each other, their counts won’t drop to zero even when no name can reach them any longer. Step through it in the widget.

For cycles, CPython has a second mechanism, the garbage collector, the gc module; it appeared in Python 2.0, in 2000. The collector looks only at containers (lists, dictionaries, instances of classes), since only objects that refer to something can form a cycle. For each one it subtracts from the count the references coming from other containers. Whatever is left with a positive number is held by something outside: a name, the stack, a module. From those objects the collector follows the references and marks everything it reaches as alive. The rest is garbage. We check it in a cell, switching automatic collection off for a while.

Room A, with no cycle, checked out the moment its name disappeared. Rooms X and Y outlived their names and waited until gc.collect() found them. Usually nobody runs a collection by hand: Python starts one by itself when the number of containers created and still alive has grown by 2000 since the last collection; that is the first of the thresholds. Objects are also divided into generations: young ones are checked often, those that have survived several collections less often, because most objects die young, and old-timers will probably live on.

Leaks

Python cleans up after a program by itself, and memory still leaks in it, only usually not the way it does in C. In C a leak is a forgotten call to free. In a language with garbage collection a memory leak is a forgotten reference: an object is no longer needed, but it can still be reached, and the collector has every right to consider it alive. A list where every request is stored “just in case”; a cache without a limit, such as @cache from Chapter 34 on a long-running server; an event handler that was subscribed and never unsubscribed. The tracemalloc module helps find such a reference: it records which line of the program allocated how much memory, and it can compare two snapshots.

Comparing the snapshots points straight at the culprit: line 7, twenty thousand objects, nearly thirteen mebibytes. On a server you do the same: a snapshot now, a snapshot an hour later, and the difference is a list of suspect lines. If memory grows and tracemalloc stays silent, the leak is most likely not in Python but in a C library, and then you watch the process’s RSS from the section on laziness.

Tasks

Three tasks behind the front desk: count the moves, build Bélády’s anomaly for any number of rooms, and translate an address by a book in two volumes, as the Intel 80386 processor did.

What next

The hotel is running: every guest has a book of their own, the locks keep people out of other guests’ rooms, and after a fork a shared room is split only when something in it changes. Processes are isolated from each other almost completely.

But sometimes isolation gets in the way. A browser wants four cores to decode a page’s images at once, and a server wants a hundred handlers to see one and the same table of users. For that, several threads are started inside one process: they share one book, the same rooms, and each of them can write anywhere. The scheduler from the last chapter hands them cores as if they were separate programs. Here are two threads, each adding one to a shared counter a million times.

It should be two million. Run it a few times: almost certainly you’ll get less, and different each time. Increments get lost, although nobody erased anything and not a single instruction went wrong. Where they vanish, and how to keep them from vanishing, is the subject of the next chapter.