Virtual memory

A puzzle to start

Every program running on your computer thinks its memory starts near address 0 and runs up to enormous addresses. Your browser, your editor and your terminal can each use the very same address, say 0x400000, at the same moment, and each finds its own different data there. How can one address hold several different things? The answer is that the addresses your program uses aren’t real RAM locations. They’re virtual addresses, and every running program (every process) gets its own private set.

Virtual addresses and translation

Each process gets its own address space: the illusion of having the whole range of addresses to itself. Behind the scenes, the hardware translates every virtual address into a physical address (a real location in RAM), on every single memory access. The part of the CPU that does this is the MMU (memory management unit), and it follows translation tables called page tables, which the operating system kernel sets up for each process. This buys three big things:

Isolation: a process can only reach memory its page tables map. A bug in one program can’t scribble over another program or over the kernel.
Simplicity: every program can be laid out the same way, as if it owned the machine, no matter what else is running.
Flexibility: the OS can put a process’s memory anywhere in RAM, move it, share it between processes, or park it on disk for a while.

Pages: translation in chunks

Translating every byte individually would need gigantic tables. Instead, memory is divided into fixed-size pages, usually 4 KiB. A virtual address is split into two parts: the page number and the offset inside the page. Only the page number is translated; the offset stays the same.

virtual address   0x7f3a12345678
                  page number = 0x7f3a12345    offset = 0x678 (low 12 bits)

page table says:  virtual page 0x7f3a12345  ->  physical page 0x1a2b3
physical address  = 0x1a2b3 * 4096 + 0x678  = 0x1a2b3678

4 KiB is 2¹² bytes, so the low 12 bits (the last three hex digits) are the offset, and the rest is the page number. Each page table entry also stores permissions: can this page be read? written? run as code? used by normal programs, or only by the kernel? Your program’s machine code is mapped read and execute but not write; your data is read and write but not execute. That blocks a whole family of attacks where someone tries to sneak in code as data. Real page tables have several levels (four on most x86-64 systems), so a full translation takes several memory reads. To avoid paying that on every access, the CPU keeps a small cache of recent translations called the TLB (translation lookaside buffer). Most accesses hit the TLB, and translation costs nothing.

Page faults: when translation fails

Sometimes the MMU looks up a virtual page and finds no valid translation, or the access breaks the page’s permissions (writing to a read-only page, say). The CPU then pauses your program and hands control to the kernel. This is a page fault, and it isn’t necessarily an error. The kernel looks at what happened and decides:

The page should be there, it just isn’t yet. The kernel finds a free physical page, fills it in (with zeros, data from a file, or data from swap), updates the page table and resumes your program as if nothing happened. You never notice, apart from a tiny delay.
The address is invalid or the access isn’t allowed. The kernel sends your process the signal SIGSEGV, and it crashes with the famous “segmentation fault”. The first case enables demand paging: memory isn’t really handed out until it’s used. Ask the OS for 1 GiB with mmap and the call returns instantly, because the kernel only noted “these addresses are now valid”. Physical pages are assigned one at a time as you first touch each one. The kernel also deliberately leaves the page at address 0 unmapped. So dereferencing a null pointer always hits the second case and crashes immediately and clearly, instead of quietly reading whatever happened to be at address 0.

What a process looks like inside

Every process’s address space is organised into regions, roughly like this:

high  +-----------------------+
      |  stack   (grows down) |
      |          ...          |
      |  mmap region          |  shared libraries, big allocations
      |          ...          |
      |  heap    (grows up)   |
      |  .bss                 |  globals that start as zero
      |  .data                |  globals with an initial value
      |  .text                |  machine code (read + execute)
low   +-----------------------+  (page 0 is never mapped)

.text holds your compiled machine code.
.data holds global variables that start with a value, such as var counter: u32 = 5; at the top level of a file.
.bss holds globals that start as zero. They take no space in the executable file; the OS just maps zero-filled pages.
The heap grows upward as the allocator asks for more memory.
The mmap region holds shared libraries and large allocations.
The stack sits near the top and grows downward. Pointers are 64 bits wide, but most x86-64 CPUs only use 48 bits of virtual address (256 TiB), and the kernel takes the top half. That’s why the stack addresses you print usually look like 0x7ff…, while code and globals sit at much lower numbers.

Recap

Programs use virtual addresses. The MMU translates them to physical RAM using per-process page tables.
That gives isolation: processes can’t touch each other’s memory.
Translation works in 4 KiB pages, each with read/write/execute permissions, and the TLB caches translations.
A page fault is either fixed silently (demand paging) or becomes SIGSEGV.
Null dereferences crash reliably because page 0 is never mapped.