§23.2–23.3The Linux Virtual Memory System … Summary

Second case study: the system on your phone, your laptop, and the datacenter — whose VM has been driven forward by real engineers solving real production problems.

23.2 The Linux Virtual Memory System

The Linux Address Space

Familiar bones: user portion below, kernel above, kernel identical in every process (and untouchable from user mode). In classic 32-bit Linux the split sits at 0xC0000000:

The interesting wrinkle is the kernel’s two address types. Kernel logical addresses kernel logical address Linux's kmalloc territory: direct-mapped to the start of physical memory (0xC0000000 → PA 0), never swapped, and contiguity carries over to physical — which is what DMA transfers require. defined in ch. 23 — open in glossary (get them with kmalloc) are direct-mapped onto the start of physical memory — trivially translatable, never swapped, and physically contiguous, which is exactly what device DMA transfers demand. Kernel virtual addresses kernel virtual address Linux's vmalloc territory: virtually contiguous, physically scattered (so no DMA) — easier to allocate for large buffers, and on 32-bit systems the kernel's route past its ~1GB direct-map limit. defined in ch. 23 — open in glossary (vmalloc) promise only virtual contiguity — easier to allocate for large buffers, useless for DMA, and historically the 32-bit kernel’s escape hatch beyond its ~1GB direct map.

Page Table Structure

x86 dictates terms: hardware-managed, multi-level, one table per process — the OS writes mappings, points CR3, and gets out of the way. The 64-bit era brought a four-level walk over the bottom 48 bits:

Nine bits per level because 512 eight-byte PTEs fill one 4KB page — chapter 20’s fit-in-a-page rule, stacked four high. As memories grow, five- and six-level trees are coming: imagine six translations to find one byte.

Large Page Support

x86 also offers 2MB and 1GB pages, which Linux exposes as huge pages huge pages Linux's 2MB/1GB pages. The prize is TLB coverage (big-memory apps burn ~10% of cycles on TLB misses with 4KB pages), plus shorter miss walks; adopted incrementally — explicit mmap/shmget first, then transparent huge pages. Costs: internal fragmentation, swap amplification. defined in ch. 23 — open in glossary . The driving force is TLB behavior, not table size: big-memory workloads can burn ~10% of their cycles on TLB misses with 4KB pages, and one huge-page entry covers five hundred 4KB entries’ worth of memory (with a shorter miss walk as a bonus). The rollout was deliberately slow: first explicit requests only (mmap/shmget flags, for databases that cared), then — once the upsides were proven broadly — transparent huge pages, applied automatically. The tax: internal fragmentation, and ugly interactions with swapping.

The Page Cache

Linux caches aggressively and uniformly: the page cache page cache Linux's unified in-memory cache of memory-mapped files, file data/metadata, and anonymous (heap/stack) memory, kept in a hash table with clean/dirty tracking; pdflush threads write dirty pages back in the background. defined in ch. 23 — open in glossary holds memory-mapped files, file data and metadata, and the anonymous memory (heap, stack) backed by swap — all in one hash table, clean/dirty tracked, with pdflush background threads writing dirty pages to their backing store on a timer or a dirty-count threshold. When memory runs low, Linux evicts using a modified 2Q 2q replacement Linux's answer to LRU's scan problem: first touch puts a page on the INACTIVE list; a re-reference promotes it to the ACTIVE list (kept ~2/3 of the cache); evict from inactive. A huge cyclic file parades through inactive without flushing the hot working set. defined in ch. 23 — open in glossary scheme:

0000000000400000    372K r-x— tcsh
00000000019d5000   1780K rw---   [ anon ]
00007f4e7cf06000   1792K r-x— libc-2.23.so
00007f4e7d508000    148K r-x— libtinfo.so.5.9
00007f4e7d731000    152K r-x— ld-2.23.so
00007f4e7d932000     16K rw---   [ stack ]

Security And Buffer Overflows

The sharpest difference between modern VM systems and their ancestors is the security arms race — and it opens with the buffer overflow buffer overflow Writing past an allocation's end (e.g., forgetting strlen+1); sometimes silently "works," sometimes crashes, often a security hole. defined in ch. 14 — open in glossary attack, which starts with one line of trusting code:

int some_function(char *input) {
  char dest_buffer[100];
  strcpy(dest_buffer, input); // oops, unbounded copy!
}

Overflow the buffer with crafted input and you may redirect execution itself. The escalation, round by round:

You can watch ASLR aslr Address space layout randomization: place code, stack, and heap at randomized virtual addresses so ROP chains can't be pre-computed (print &stack twice — different every run). KASLR extends the trick to the kernel. defined in ch. 23 — open in glossary work from your own shell — print a stack address twice:

int main(int argc, char *argv[]) {
    int stack = 0;
    printf("%p\n", &stack);
    return 0;
}

prompt> ./random
0x7ffd3e55d2b4
prompt> ./random
0x7ffe1033b8f4

The NX bit nx bit No-eXecute: a PTE bit (AMD's NX, Intel's XD) that forbids executing from a page — stacks stop being launchpads for injected code. The first rung on the defense ladder. defined in ch. 23 — open in glossary , ROP return-oriented programming ROP: with injection blocked, attackers chain 'gadgets' — instruction fragments already present in the program and libc — by overwriting the stack with a sequence of return addresses. Arbitrary computation from borrowed code. defined in ch. 23 — open in glossary , ASLR/KASLR, Meltdown & Spectre meltdown and spectre The 2018 attacks showing that SPECULATIVE EXECUTION — the CPU running guessed-at instructions early — leaves traces in caches and predictors that leak memory the MMU supposedly protects. Mitigations (like KPTI) help; the fundamental tension remains. defined in ch. 23 — open in glossary , and KPTI kpti Kernel page-table isolation: post-Meltdown, unmap (almost all of) the kernel from user page tables and switch tables on every kernel entry — better isolation, real performance cost. Security's price: convenience and performance. defined in ch. 23 — open in glossary form a ladder with no visible top: turning speculation off entirely would run thousands of times slower, so the tension is permanent. An interesting time to be alive, if systems security is your thing.

23.3 Summary

Two complete systems, top to bottom. VMS taught the canon — hybrid paging/segmentation, kernel-in-every-space, segmented FIFO, demand zeroing, COW — and Linux runs on it still: lazy COW fork(), demand zeroing via /dev/zero mappings, a background swap daemon (swapd), plus its own inventions (2Q, transparent huge pages, the unified page cache) and its own scars (KPTI). Read Levy and Lipman’s short, excellent VAX/VMS paper to see the source material behind these chapters. And with that, memory virtualization is complete — “what is any ocean, but a multitude of drops?”