osdev-paging

name	osdev-paging
description	Virtual memory and paging for x86, x86-64, ARM, RISC-V. Page tables, PTE flags, TLB, identity mapping, higher-half kernel. Use when implementing paging, virtual memory, page tables, or address space management.
origin	MCC

Virtual Memory and Paging

Complete reference for implementing paging across architectures: page table structures, entry formats, TLB management, identity mapping, and higher-half kernel setup.

When to Use

• Setting up paging for the first time in a new kernel
• Implementing virtual address spaces for user processes
• Mapping kernel to the higher half of the address space
• Debugging page faults and TLB-related issues
• Porting paging code between x86, x86-64, ARM, or RISC-V
• Implementing demand paging, copy-on-write, or memory-mapped I/O

Why Paging Matters

Without paging, every process shares the same flat physical address space. A bug in one program can overwrite another program's memory or corrupt the kernel. Paging solves this by giving each process its own virtual address space that the MMU translates to physical addresses transparently.

What paging enables:

Capability	Why It Matters
Process isolation	Each process gets its own address space; a wild pointer in process A cannot touch process B
Kernel protection	Kernel pages marked supervisor-only; user code page-faults instead of corrupting the kernel
Demand paging	Pages loaded from disk on first access; processes can have larger virtual memory than physical RAM
Memory-mapped I/O	Hardware registers mapped into virtual address space for clean driver interfaces
Copy-on-write	Fork shares pages read-only; copy only on write, making fork nearly free
ASLR	Randomized virtual addresses make exploits harder

x86 32-bit Paging (2-Level)

Two-level translation: CR3 points to a Page Directory, each PD entry points to a Page Table, each PT entry points to a 4KB physical page frame.

Virtual Address (32 bits):
[31:22] PD index (10 bits = 1024 entries)
[21:12] PT index (10 bits = 1024 entries)
[11:0]  Page offset (12 bits = 4KB)

CR3 --> Page Directory (1024 x 4-byte entries)
            |
            v
        Page Table (1024 x 4-byte entries)
            |
            v
        4KB Physical Page Frame + offset

Each level has 1024 entries because 10 bits index into 4-byte entries in a 4KB-aligned table. The full directory + tables can map the entire 4GB 32-bit address space, but you only need to populate entries for address ranges you actually use -- unpopulated entries are marked not-present.

PSE (Page Size Extension): Setting the PS bit in a Page Directory Entry maps a 4MB page directly, skipping the Page Table level. Enable via CR4.PSE. Useful for identity-mapping large regions during boot.

See references/x86-paging.md for entry formats, C code, and identity mapping examples.

x86-64 Paging (4-Level)

Long mode extends paging to four levels with 512 entries per table (9 bits each, 8-byte entries). Only 48 bits of virtual address are used in standard 4-level paging.

Virtual Address (48 bits used, canonical form):
[47:39] PML4 index  (9 bits = 512 entries)
[38:30] PDPT index  (9 bits = 512 entries)
[29:21] PD index    (9 bits = 512 entries)
[20:12] PT index    (9 bits = 512 entries)
[11:0]  Page offset (12 bits = 4KB)

CR3 --> PML4 (512 x 8-byte entries)
           |
           v
        PDPT (512 x 8-byte entries)
           |
           v
        PD (512 x 8-byte entries)
           |
           v
        PT (512 x 8-byte entries)
           |
           v
        4KB Physical Page Frame + offset

Canonical addresses: Bits 48-63 must be copies of bit 47. This creates a "hole" in the middle of the address space: valid ranges are 0x0000000000000000--0x00007FFFFFFFFFFF (user) and 0xFFFF800000000000--0xFFFFFFFFFFFFFFFF (kernel). Non-canonical addresses cause a General Protection Fault.

Huge pages: Setting the PS bit in a PD entry creates a 2MB page (skips PT). Setting PS in a PDPT entry creates a 1GB page (skips PD and PT). Huge pages reduce TLB pressure for large contiguous mappings.

5-level paging (PML5): Adds a fifth level for 57-bit virtual addresses. Enable via CR4.LA57 before entering long mode. Detected via CPUID leaf 7, ECX bit 16.

See references/x86_64-paging.md for entry formats, NX bit, C code, and higher-half examples.

PTE Flags

Page table entries use the low 12 bits (and bit 63 on x86-64) for control flags. The physical address occupies the remaining bits (aligned to 4KB, so bits [11:0] are always zero in the address portion).

x86/x86-64 PTE Bit Layout

Bit	Name	Purpose	Why It Matters
0	P (Present)	Entry is valid and mapped	Not-present triggers page fault; used for demand paging and swap
1	R/W (Read/Write)	1=read/write, 0=read-only	Enforce write protection; essential for copy-on-write
2	U/S (User/Supervisor)	1=user accessible, 0=kernel only	Prevents user code from accessing kernel memory
3	PWT (Write-Through)	1=write-through caching	Controls cache behavior for MMIO regions
4	PCD (Cache Disable)	1=caching disabled	Required for memory-mapped device registers
5	A (Accessed)	Set by CPU on read or write	OS uses for page replacement algorithms (LRU approximation)
6	D (Dirty)	Set by CPU on write	OS uses to know which pages need writing back to disk on eviction
7	PS/PAT	PS=Page Size (in PDE/PDPTE), PAT (in PTE)	PS enables huge pages; PAT selects memory type
8	G (Global)	Page not flushed on CR3 reload	Kernel pages should be global to avoid unnecessary TLB misses on context switch
63	NX (No Execute)	1=execution disabled (x86-64 only)	Prevents code execution from data pages; requires IA32_EFER.NXE=1

Critical rules:

• P must be set for the CPU to use any other bits. When P=0, the CPU ignores all other bits (OS can use them for bookkeeping, e.g., swap location).
• U/S must be set at every level of the hierarchy. If any level is supervisor-only, the final page is supervisor-only.
• R/W is checked at every level. If any level is read-only, the final page is read-only (unless CR0.WP=0, which gives the kernel write access regardless).
• The CPU sets A and D bits automatically but never clears them. The OS must clear them periodically for page replacement to work.

TLB Management

The TLB (Translation Lookaside Buffer) caches virtual-to-physical translations. Without it, every memory access would require walking 2-4 levels of page tables (2-4 extra memory reads). The TLB makes paging nearly free for cached translations.

The problem: After modifying page table entries, the TLB may still hold the old translation. The CPU does not snoop page table changes. You MUST manually invalidate stale entries.

Invalidation Methods

Method	Instruction	Scope	When to Use
Single page	invlpg [addr]	One virtual address	After modifying a single PTE (most common case)
Full flush	Reload CR3 (mov cr3, reg)	All non-global entries	After bulk page table changes or address space switch
Global flush	Toggle CR4.PGE off then on	All entries including global	Rare; needed when modifying kernel mappings marked global
INVPCID	invpcid type, desc	Per-PCID or all	When using Process Context IDs for selective flushing

When you MUST flush:

• After changing any PTE that maps a currently-accessible virtual address
• After changing Present from 1 to 0 (unmapping)
• After changing R/W, U/S, or NX bits
• After clearing Accessed or Dirty bits (otherwise CPU may not re-set them)

When you can skip flushing:

• After changing a PTE from not-present to present (the TLB cannot have cached a not-present entry)
• After modifying entries in a page table that is not currently loaded in CR3

Identity Mapping and Higher-Half Kernel

Identity Mapping

Identity mapping means virtual address == physical address. During boot, before paging is enabled, code executes at physical addresses. The instant you set CR0.PG, the CPU starts translating the very next instruction through page tables. If the code you are currently executing is not mapped, you get an immediate page fault.

Rule: Before enabling paging, you MUST identity-map at minimum the memory region containing the code that enables paging and the instructions immediately following.

Higher-Half Kernel

Most serious kernels map themselves to the upper portion of the virtual address space:

• 32-bit: Kernel at 0xC0000000 (3GB), user space gets 0x00000000--0xBFFFFFFF
• 64-bit: Kernel at 0xFFFF800000000000 or 0xFFFFFFFF80000000, user space gets the lower canonical half

Why higher-half: Each process can have the full lower address space for its own code and data, while the kernel is always mapped at the same virtual address in every process's page tables. Context switching only needs to swap the user-space mappings.

Boot Sequence for Higher-Half

1. Bootloader loads kernel at physical address (e.g., 0x100000)
2. Boot code creates page tables that map the kernel at both:
   • Identity: physical addr 0x100000 -> virtual 0x100000 (temporary)
   • Higher-half: physical addr 0x100000 -> virtual 0xC0100000 (permanent)
3. Load CR3 with page directory physical address
4. Enable paging (set CR0.PG)
5. Jump to a higher-half virtual address (absolute jump, not relative)
6. Remove the identity mapping (set PDE entry 0 to not-present)
7. Flush TLB (reload CR3)

The identity mapping in step 2 is required because the mov cr0 instruction and the next few instructions still execute at physical addresses. After the absolute jump to the higher-half address in step 5, the identity mapping is no longer needed.

See references/x86-paging.md for 32-bit higher-half example and references/x86_64-paging.md for 64-bit.

Enabling Paging

x86 32-bit

; 1. Load CR3 with page directory physical address
mov eax, page_directory
mov cr3, eax

; 2. Enable paging (PG) and protection (PE) in CR0
mov eax, cr0
or  eax, 0x80000001    ; bit 31 = PG, bit 0 = PE
mov cr0, eax
; Paging is now active. Next instruction is fetched through page tables.

; Optional: also set WP bit (0x80010001) to enforce read-only pages for kernel too

x86-64 (entering long mode)

; 1. Disable 32-bit paging if active
mov eax, cr0
and eax, ~(1 << 31)
mov cr0, eax

; 2. Set up 4-level page tables, load CR3
mov eax, pml4_table
mov cr3, eax

; 3. Enable PAE (required for long mode)
mov eax, cr4
or  eax, (1 << 5)      ; CR4.PAE
mov cr4, eax

; 4. Enable long mode in EFER MSR
mov ecx, 0xC0000080     ; IA32_EFER
rdmsr
or  eax, (1 << 8)       ; EFER.LME
wrmsr

; 5. Enable paging to activate long mode
mov eax, cr0
or  eax, (1 << 31) | (1 << 0)  ; PG + PE
mov cr0, eax
; CPU is now in compatibility mode (32-bit long mode)

; 6. Load 64-bit GDT and far jump to 64-bit code segment
lgdt [gdt64_pointer]
jmp  gdt64_code_seg:long_mode_entry

Critical ordering: PAE must be enabled before setting EFER.LME. EFER.LME must be set before enabling paging. Violating this order causes a General Protection Fault.

ARM and RISC-V Paging

ARM and RISC-V take different approaches but share the same core concept: multi-level page table walks controlled by a base register.

See references/arm-paging.md for ARMv7, ARMv8/AArch64, and RISC-V details.

Key Differences from x86

Feature	x86/x86-64	ARMv7	ARMv8 (AArch64)	RISC-V
Base register	CR3	TTBR0/TTBR1	TTBR0_EL1/TTBR1_EL1	SATP
User/kernel split	Same CR3, U/S bit per page	Separate TTBR0 (user) and TTBR1 (kernel)	Separate TTBR0 (user) and TTBR1 (kernel)	Same SATP, U bit per page
Page sizes	4KB, 2MB, 1GB	4KB, 64KB, 1MB (section)	4KB, 16KB, 64KB, 2MB, 1GB	4KB, 2MB, 1GB
Levels (4KB pages)	2 (32-bit), 4 (64-bit)	2 (short), 3 (long)	4	3 (Sv39), 4 (Sv48), 5 (Sv57)
NX/XN	NX bit 63 (x86-64 only)	XN bit in PTE	XN/UXN/PXN bits	X bit per page

ARM advantage: The TTBR0/TTBR1 split means user and kernel page tables are physically separate. On context switch, only TTBR0 needs to change -- the kernel mapping in TTBR1 stays untouched. x86 achieves similar effect with global pages (G bit) but still uses a single CR3.

Common Pitfalls

1. Forgetting to identity-map before enabling paging. The instruction after mov cr0, eax is fetched through page tables. If it is not mapped, you triple-fault.

2. Not page-aligning page tables. Page directories and tables MUST be aligned to 4KB. Using malloc or an unaligned BSS buffer silently corrupts entries because the low 12 bits are used for flags.

3. Modifying page tables without flushing TLB. The CPU will continue using the stale cached translation. Use invlpg after single-PTE changes, or reload CR3 after bulk changes.

4. Forgetting U/S at every level. Setting U/S=1 only in the PTE but leaving the PDE as supervisor-only still blocks user access. Permissions are checked at every level of the hierarchy.

5. Enabling paging without PE (Protected Mode). Setting CR0.PG without CR0.PE causes a General Protection Fault. Protected mode must be active first.

6. Writing to read-only pages from kernel. With CR0.WP=1 (recommended), even ring 0 code page-faults on write to read-only pages. This is intentional -- it enables copy-on-write. Set CR0.WP=1 early.

7. Assuming contiguous physical memory. Virtual pages can map to any physical frames in any order. Your page frame allocator returns scattered frames -- that is normal and expected.

8. NX bit without enabling EFER.NXE. On x86-64, bit 63 is reserved unless IA32_EFER.NXE is set. Using it without NXE causes page faults with reserved-bit error code.

9. Not handling canonical address holes. On x86-64, addresses between 0x00007FFFFFFFFFFF and 0xFFFF800000000000 are non-canonical. Dereferencing them causes #GP, not #PF.

10. Recursive mapping confusion. Mapping a PD entry to point back to the PD itself is a useful trick for accessing page tables without knowing their physical addresses, but getting the math wrong leads to subtle corruption.

Related Skills

• osdev-toolchain -- cross-compiler setup, linker scripts, QEMU debugging
• osdev-interrupts -- page fault handler setup (IDT entry 14)
• osdev-memory -- physical memory allocator (page frame allocator)
• osdev-process -- process address spaces and context switching