How Paging Works

The Two-Level Page Table

Translating a virtual address to a physical address involves two lookups:

32-bit Virtual Address
┌──────────┬──────────┬────────────────┐
│ Dir (10) │ Tab (10) │  Offset (12)   │
└──────────┴──────────┴────────────────┘
 Bits 31-22  Bits 21-12  Bits 11-0

1. The CPU reads CR3 to get the physical address of the Page Directory
2. Bits 31-22 index into the Page Directory (0-1023) → gives address of a Page Table
3. Bits 21-12 index into that Page Table (0-1023) → gives physical address of a 4KB page
4. Bits 11-0 are the offset within that 4KB page (0-4095)

CR3 → Page Directory
          │
          │ [bits 31-22]
          ▼
      PD Entry → Page Table
                     │
                     │ [bits 21-12]
                     ▼
                 PT Entry → Physical Page
                                 │
                                 │ + [bits 11-0]
                                 ▼
                           Physical Address

Worked Example

Virtual address: 0x00120ABC

0x00120ABC = 0000 0000 00 | 01 0010 0000 | 1010 1011 1100
              ───────────   ────────────   ────────────
               PD index:0   PT index:288   Offset:0xABC

1. Read PD[0] → Physical address of page table 0
2. Read PT[288] → Physical address of some 4KB page
3. Physical address = page_base + 0xABC

Capacity

• One page table covers: 1024 × 4KB = 4MB
• One page directory covers: 1024 × 4MB = 4GB
• Each structure (directory or table) is: 1024 × 4 bytes = 4KB (one page!)

Enabling Paging

Two control registers:

CR3 — Holds the physical address of the Page Directory. The CPU reads this to start every address translation.

CR0 — Bit 31 (the PG bit) enables paging:

#![allow(unused)]
fn main() {
unsafe fn enable_paging(page_dir_phys: u32) {
    // Tell CPU where the page directory is
    core::arch::asm!("mov cr3, {}", in(reg) page_dir_phys);

    // Enable paging by setting the PG bit in CR0
    core::arch::asm!(
        "mov eax, cr0",
        "or eax, 0x80000000",  // Set bit 31
        "mov cr0, eax",
        out("eax") _,
    );
}
}

Why OR instead of MOV?

CR0 has other important bits (Protected Mode enable, Write Protect, etc.). MOV would overwrite them. OR only sets the PG bit and leaves everything else intact.

After the mov cr0, eax instruction, the CPU immediately starts translating all virtual addresses. If the page tables aren’t set up correctly at that exact moment, the next instruction causes a page fault and the system crashes.

The Translation Lookaside Buffer (TLB)

Walking two levels of page tables for every memory access would be slow. The CPU caches recent translations in the TLB (Translation Lookaside Buffer).

When we modify a page table entry, we must invalidate the corresponding TLB entry:

#![allow(unused)]
fn main() {
unsafe fn flush_tlb(vaddr: u32) {
    core::arch::asm!(
        "invlpg [{0:e}]",
        in(reg) vaddr,
        options(nostack, preserves_flags)
    );
}
}

invlpg — Invalidate a single TLB entry for the given virtual address. After this, the next access to that address will do a fresh page table walk.

Loading a new value into CR3 flushes the entire TLB (all entries).