Virtual Memory

Two Python processes on the same machine can each hold an object at the same address and hold completely different data there. Every address a program uses is a fiction. On every memory access, the hardware translates it through a table that the kernel keeps for that one process, and only the translated address reaches RAM.

That translation is what makes processes private, lets them share libraries, makes fork cheap and makes allocation lazy. It also has a price, and you pay it on every random access into a large data structure. This topic follows one address through the translation and puts a number on the price.

Addresses Are Names, Not Places

A virtual address is looked up, never used directly. The unit of translation is the page, usually 4 KiB. Each page of a process's address space maps to one physical frame of RAM of the same size, or to nothing yet. The low bits of an address, the position inside the page, pass through untouched; only the page number is translated.

So memory that is contiguous to the program may be scattered all over RAM. A 1 MiB array is 256 consecutive pages to the program and 256 frames wherever the kernel found them. Two processes can map the same frame, which is how they share a library, and a page can be mapped to no frame at all until someone touches it.

The Page Table

A flat array would be enormous, so the table that holds the mapping is a tree, of the kind Chapter 6 introduces, indexed by slices of the virtual address. On x86-64, the processor family in most servers, the tree has four levels of 512 entries each. The top 36 bits of a 48-bit address are cut into four 9-bit indexes, one per level, and the last 12 bits are the offset inside a 4 KiB page. Four levels of 512 cover 256 TiB of address space per process. Newer processors add a fifth level for 57-bit addresses.

Every entry carries permission bits as well as a frame number: present, writable, executable, accessible from user mode. The processor checks them on every access. A missing entry is not an error yet. It is a page fault, a trap into the kernel, which decides what the access should mean; the next topic follows that decision.

The TLB

Walking four levels of table on every access would add up to four memory reads to every load and store. So the processor caches recent translations in the translation lookaside buffer, the TLB. It holds a few thousand entries at most, so with 4 KiB pages it covers only a few megabytes, 8 MiB for a 2,048-entry buffer.

A TLB hit costs nothing extra. A miss costs a page walk: tens of nanoseconds when the table entries are themselves in the processor's cache, and up to four trips to RAM, about a hundred nanoseconds each on the latency ladder in Chapter 4, when they are not. Huge pages change the arithmetic. On x86-64 a page can also be 2 MiB or 1 GiB, and one TLB entry for a 2 MiB page covers 512 times as much memory, so the same few thousand entries cover gigabytes. Databases and large runtimes ask for them to get that reach.

What the Indirection Buys

Isolation comes first: a process cannot even name another process's memory, because every address it can form goes through its own table. Protection comes from the permission bits: code pages are read-only and the stack is not executable, so a write into code or a jump into data faults instead of running. Sharing is a matter of two tables pointing at one frame, which is how one copy of a common library serves every process on the machine.

Copy-on-write, from the previous topic but one, is two tables pointing at one frame with the writable bit cleared. And laziness falls out for free: an allocation only reserves a range of addresses, and a frame is found for each page only when that page is first touched. A program that allocates a gigabyte and touches ten megabytes uses about ten megabytes.

Why Every Process Thinks It Owns All of Memory

Address space is enormous and nearly free, so processes reserve far more than they use. Thread stacks, memory-mapped files and the arenas of language runtimes all reserve large ranges up front. Add up the reservations on one machine and they can be many times its RAM.

The kernel is betting that not everything reserved will be touched at once. Most of the time the bet wins. When it loses, the kernel pushes rarely used pages out to disk, the swapping of the next topic, or it picks a process and kills it to free memory. So running out of memory usually strikes at some ordinary write far away from any allocation: the write is when the page is actually needed.

Huge Pages and Memory Limits

Random lookups into a 10 GB in-memory hash table, the structure of Chapter 5, miss the TLB almost every time, because a few megabytes of translations cannot cover 10 GB of randomly chosen pages. Each lookup then pays a page walk on top of its cache miss. The same table backed by 2 MiB huge pages runs measurably faster with no change to the code. It needs about five thousand translations instead of about two and a half million, so a large share of them fit in the TLB, and a miss walks one level fewer through a table small enough to stay in the processor's cache.

A container's memory limit counts pages actually held in RAM, not reserved addresses. A service showing 20 GB of virtual size may be using 300 MB, and the process that gets killed is the one whose touched pages grew, not the one with the biggest reservation. Watching a process's resident and virtual memory on a real machine is covered in Linux Deep Dive, chapter Performance and Troubleshooting.