Page Tables and Faults

Three concepts in the six-part treatment: the page table walk, the fault handler, and reverse mapping and TLBs — the two things that make the whole arrangement maintainable rather than merely correct.

Concept 1: The Page Table Walk

1. What problem it solves

Every process needs its own view of memory, larger than physical RAM, protected from every other process, with parts shared and parts private. Doing that with a flat table would need one entry per page of a 256 TB address space — hundreds of gigabytes of table for a process using a megabyte.

The answer is a sparse radix tree in hardware: a multi-level table where an entire subtree can be absent, costing nothing. The MMU walks it on every memory access, and the kernel's job is to build and maintain it.

2. Where it exists in the kernel

Generic page-table code in mm/, with the actual entry formats per architecture.

rg -n "p4d_offset|pud_offset|pmd_offset|pte_offset_map" mm/memory.c | head
ls arch/x86/include/asm/pgtable*.h arch/arm64/include/asm/pgtable*.h
rg -n "define PAGE_SHIFT|define PTRS_PER_PTE" arch/x86/include/asm/ arch/arm64/include/asm/ | head
find Documentation -path '*x86*' -name 'mm.rst'      # the x86-64 address-space map

3. Who owns or interacts with it

4. The levels

   virtual address (x86-64, 4-level, 4 KB pages)
   ┌─────────┬─────────┬─────────┬─────────┬──────────────┐
   │  PGD    │  PUD    │  PMD    │  PTE    │  offset      │
   │  9 bits │  9 bits │  9 bits │  9 bits │  12 bits     │
   └────┬────┴────┬────┴────┬────┴────┬────┴──────────────┘
        │         │         │         │
    mm->pgd ──▶ pud ──▶   pmd ──▶   pte ──▶ physical frame + flags

   Five levels (p4d inserted) on machines with 5-level paging.
   Each table is one page: 512 8-byte entries.

   A level can TERMINATE EARLY: a PMD entry with the "huge" bit set maps a
   2 MB page directly, with no PTE level. That is what a transparent huge
   page IS -- one fewer level, one TLB entry instead of 512.

The kernel's accessor names mirror the levels exactly, and reading handle_mm_fault means reading this sequence:

pgd = pgd_offset(mm, address);
p4d = p4d_offset(pgd, address);
pud = pud_offset(p4d, address);
pmd = pmd_offset(pud, address);
pte = pte_offset_map(pmd, address);     /* may be NULL: nothing mapped here */

Each entry carries flags as well as an address: present, writable, user-accessible, accessed, dirty, no-execute, and per-architecture extras. Those bits are how protection, copy-on-write, and the accessed/dirty tracking that reclaim depends on are all implemented.

rg -n "define _PAGE_PRESENT|_PAGE_RW|_PAGE_USER|_PAGE_ACCESSED|_PAGE_DIRTY|_PAGE_NX" \
   arch/x86/include/asm/pgtable_types.h | head

5. Experiment

CLAIM. Page tables are real, walkable, and sparse — and you can read the physical mapping of your own process.

METHOD. /proc/PID/pagemap exposes the PTE for each virtual page.

cat > /tmp/pm.c <<'EOF'
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdint.h>
int main(void) {
    size_t sz = 16 * 4096;
    char *p = aligned_alloc(4096, sz);
    printf("virt = %p  pid = %d\n", (void *)p, getpid());
    printf("BEFORE touching:\n"); fflush(stdout);
    getchar();                          /* inspect pagemap now */
    memset(p, 1, sz);                   /* now fault them all in */
    printf("AFTER touching:\n"); fflush(stdout);
    getchar();
    return 0;
}
EOF
gcc -o /tmp/pm /tmp/pm.c && /tmp/pm

In another terminal, decode pagemap for that range (bit 63 = present, bits 0–54 = PFN):

sudo python3 - <<'EOF'
import struct, sys
pid, virt, n = int(input("pid: ")), int(input("virt (hex): "), 16), 16
with open(f"/proc/{pid}/pagemap", "rb") as f:
    for i in range(n):
        f.seek(((virt >> 12) + i) * 8)
        e, = struct.unpack("<Q", f.read(8))
        print(f"page {i:2d}: present={bool(e >> 63)} swapped={bool((e>>62)&1)} pfn={e & ((1<<55)-1):#x}")
EOF

PREDICT FIRST: before memset, how many of the 16 pages are present? After? And does the PFN of page 0 stay the same across the two inspections?

Then look at the whole address space's structure:

cat /proc/self/maps | head -20
grep -E 'AnonHugePages|Hugepagesize' /proc/meminfo
cat /sys/kernel/mm/transparent_hugepage/enabled

6. Failure mode

Concept 2: The Fault Handler

1. What problem it solves

If the kernel had to populate every page table entry up front, fork() would copy gigabytes, mmap() of a large file would read it all, and a program that touches one page of a 1 GB allocation would pay for 1 GB.

Instead the kernel leaves entries deliberately absent or deliberately read-only, and lets the hardware trap when the program touches them. The fault handler is not an error path; it is the mechanism.

2. Where it exists in the kernel

rg -n "handle_mm_fault" -A 40 mm/memory.c | head -50
rg -n "do_user_addr_fault|do_page_fault" arch/x86/mm/fault.c arch/arm64/mm/fault.c | head
rg -n "do_anonymous_page|do_fault\b|do_swap_page|do_wp_page" mm/memory.c | head

3. Who owns or interacts with it

4. The four cases

   CPU traps: address + error code (read/write, user/kernel, present/absent)
     │
   arch: do_user_addr_fault()
     │  - is it a kernel address? -> a KERNEL BUG (oops), no VMA involved
     │  - is it in the guard region below the stack? -> expand the stack
     │
   handle_mm_fault(vma, address, flags)
     │
     ├── NO VMA COVERS IT ────────────────▶ SIGSEGV
     │
     ├── VMA exists, permission denied ───▶ SIGSEGV
     │      (writing to a read-only VMA)
     │
     ├── VMA exists, entry absent:
     │     ├── ANONYMOUS, first touch     do_anonymous_page()
     │     │     - a write?  allocate a zeroed page
     │     │     - a read?   map the shared zero page (no allocation at all)
     │     │     MINOR fault, microseconds
     │     │
     │     ├── FILE-BACKED                do_fault() -> vma->vm_ops->fault()
     │     │     - in the page cache?     MINOR: just install the PTE
     │     │     - not cached?            MAJOR: submit I/O and SLEEP
     │     │
     │     └── SWAPPED OUT                do_swap_page()
     │           MAJOR: read from swap, and SLEEP
     │
     └── VMA exists, entry present but READ-ONLY, and it was a write:
           └── COPY ON WRITE              do_wp_page()
                 - is this the only reference?  just make it writable
                 - shared (post-fork)?          copy it, map the copy

Three consequences worth stating explicitly:

A read of untouched anonymous memory allocates nothing. It maps a single shared zero page, read-only, for every such address in the system. Only a write allocates. This is why calloc(1, 1<<30) is instant and costs no memory until you write.

fork() copies page tables, not pages. Everything is marked read-only in both processes, and the first write to any page triggers do_wp_page() to copy just that one. That is the entire reason fork() is affordable.

A major fault sleeps. Which puts every fault-handling path under all of context and atomicity, and is why copy_to_user() can sleep.

5. Experiment

CLAIM. The four cases are distinguishable from user space, and each has a different cost.

METHOD.

cat > /tmp/faults.c <<'EOF'
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/resource.h>
#include <unistd.h>
static void report(const char *tag) {
    struct rusage r; getrusage(RUSAGE_SELF, &r);
    printf("%-28s minor=%-9ld major=%ld\n", tag, r.ru_minflt, r.ru_majflt);
}
int main(void) {
    size_t sz = 64UL << 20;
    report("start");
    char *p = mmap(NULL, sz, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
    report("after mmap (untouched)");
    volatile long sum = 0;
    for (size_t i = 0; i < sz; i += 4096) sum += p[i];      /* READ  */
    report("after reading every page");
    for (size_t i = 0; i < sz; i += 4096) p[i] = 1;         /* WRITE */
    report("after writing every page");
    if (fork() == 0) {
        report("child, after fork");
        for (size_t i = 0; i < sz; i += 4096) p[i] = 2;     /* CoW   */
        report("child, after writing (CoW)");
        _exit(0);
    }
    sleep(1);
    return 0;
}
EOF
gcc -O0 -o /tmp/faults /tmp/faults.c && /tmp/faults

PREDICT FIRST, filling this in before running (64 MB = 16384 pages):

The row people get wrong is "after reading": most predict 16384, and the answer depends on the zero page. Then check RSS at each stage to see whether memory was actually consumed.

Now major faults:

dd if=/dev/urandom of=/tmp/big bs=1M count=256 status=none
sync; sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
/usr/bin/time -v sh -c 'cat /tmp/big > /dev/null' 2>&1 | grep -E 'Major|Minor'
/usr/bin/time -v sh -c 'cat /tmp/big > /dev/null' 2>&1 | grep -E 'Major|Minor'

6. Failure mode

Concept 3: Reverse Mapping and the TLB

1. What problem it solves

The page tables answer "given a virtual address, which physical page?" Reclaim needs the opposite: "given this physical page I want to evict, who is mapping it, so I can unmap them all first?"

And once you unmap something, every CPU that cached the translation must be told — because a stale TLB entry means a CPU keeps writing to a page you just handed to someone else.

2. Where it exists in the kernel

rg -n "try_to_unmap\b|rmap_walk" -A 20 mm/rmap.c | head -40
rg -n "struct anon_vma \{" -A 20 include/linux/rmap.h
rg -n "flush_tlb_range|flush_tlb_mm|tlb_gather_mmu" mm/ arch/x86/mm/tlb.c | head
$EDITOR Documentation/mm/process_addrs.rst 2>/dev/null || ls Documentation/mm/

3. Reverse mapping

   FILE-BACKED pages:  easy.
     folio->mapping ──▶ address_space ──▶ i_mmap interval tree
     "every VMA mapping this file, and at which offset"

   ANONYMOUS pages:    harder. There is no file.
     folio ──▶ anon_vma ──▶ a chain of VMAs that could map this page
     After fork(), parent and child share anon_vmas, so the structure is a
     tree that records the fork relationship.

   try_to_unmap(folio):
     walk every mapping, clear each PTE, flush the TLB, and only then is
     the page free to reuse.

This is why reclaim is expensive: evicting one page can mean walking many page tables and issuing cross-CPU TLB invalidations. And it is why a page mapped by many processes is harder to evict, not easier.

4. TLB invalidation

The TLB caches translations, per CPU. When the kernel changes a PTE, every CPU that might have cached it must be told — a TLB shootdown, implemented as an inter-processor interrupt.

   CPU 0: unmaps a page
     └── flush_tlb_range()
           ├── flush this CPU's TLB
           └── IPI every other CPU in mm_cpumask ──▶ they flush too,
                                                     and CPU 0 WAITS.

   That wait is why munmap() of a large region on a 96-CPU machine is not
   free, and why the kernel batches invalidations (mmu_gather) rather than
   doing one per PTE.

grep -E 'TLB|CAL' /proc/interrupts | head        # shootdowns, per CPU
sudo perf stat -e dTLB-load-misses,iTLB-load-misses -- <workload>

Warning: Getting TLB invalidation wrong produces the worst class of bug in the kernel: a CPU continues to read and write a physical page after it has been freed and reallocated to something else. There is no crash at the point of the mistake, the corruption appears somewhere unrelated, and it depends on timing and CPU count. This is why mmu_gather exists as a structured API rather than leaving people to call flushes by hand.

5. Experiment

CLAIM. TLB shootdowns are real, measurable, and scale with CPU count.

METHOD.

cat > /tmp/tlb.c <<'EOF'
#define _GNU_SOURCE
#include <pthread.h>
#include <stdio.h>
#include <sys/mman.h>
#include <unistd.h>
static volatile int stop;
static void *spin(void *a){ (void)a; while(!stop); return 0; }
int main(void) {
    int n = sysconf(_SC_NPROCESSORS_ONLN);
    pthread_t t[64];
    /* Threads share the mm, so they are all in mm_cpumask. */
    for (int i = 0; i < n && i < 64; i++) pthread_create(&t[i], 0, spin, 0);
    for (int i = 0; i < 20000; i++) {
        void *p = mmap(NULL, 4096, PROT_READ|PROT_WRITE,
                       MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
        *(char *)p = 1;            /* fault it in, so there IS a translation */
        munmap(p, 4096);           /* -> shootdown to every CPU in mm_cpumask */
    }
    stop = 1;
    for (int i = 0; i < n && i < 64; i++) pthread_join(t[i], 0);
    return 0;
}
EOF
gcc -O2 -pthread -o /tmp/tlb /tmp/tlb.c

before=$(grep -E '^TLB' /proc/interrupts | awk '{s=0; for(i=2;i<=NF-2;i++) s+=$i; print s}')
time /tmp/tlb
after=$(grep -E '^TLB' /proc/interrupts | awk '{s=0; for(i=2;i<=NF-2;i++) s+=$i; print s}')
echo "TLB shootdown IPIs: $((after - before))"

PREDICT FIRST: 20,000 munmap calls with nproc spinning threads sharing the address space. How many shootdown IPIs? And how does the wall-clock time compare with running the same loop single-threaded?

6. Failure mode

Validation / Self-check

1. Why a multi-level page table rather than a flat one? What does "sparse" buy?
2. Name the levels for x86-64 and give the kernel accessor for each.
3. What does it mean for a PMD entry to "terminate early", and what feature is that?
4. Give the four cases of handle_mm_fault and say which of them sleep.
5. Reading 64 MB of untouched anonymous memory: how many pages are allocated? Why?
6. Why is fork() affordable? What exactly does it copy?
7. What is a minor fault versus a major fault, and how do you count each from user space?
8. Why does reverse mapping exist? Why is it harder for anonymous pages than file-backed ones?
9. Why is a page mapped by many processes harder to reclaim?
10. What is a TLB shootdown, what triggers one, and why does the initiating CPU wait?
11. Describe the failure mode of a missed TLB flush, and say why it is the worst class of kernel bug.
12. Why does mmu_gather exist rather than a flush call per PTE?

Next: Allocators and Folios — where memory comes from, and what the page cache actually is.