Understanding Memory Paging and Page Table Structures in x86-64

Memory paging is a computer memory‑management technique widely used in modern operating systems and x86‑64 processors. It splits physical memory into fixed‑size blocks (usually 4 KB) called pages, allowing each process to have an independent, contiguous virtual address space.

When a program accesses a virtual address, the CPU translates it to a physical address using a page table, a data structure that records the mapping between virtual and physical pages. Hardware support such as the TLB accelerates this translation, and pages are loaded on demand.

Paging provides several advantages:

Virtualization: each process gets its own address space, improving security and isolation.

Memory sharing: multiple processes can share the same physical page, saving memory.

Lazy loading: pages are loaded only when accessed, reducing initialization time and memory usage.

Memory protection: pages can be marked read‑only or non‑executable to protect code and data.

1. Functions of Memory Paging

Paging works together with the operating system and hardware to map virtual memory to physical pages. Its main functions include virtual memory management, memory protection, memory sharing, flexible memory allocation and reclamation, page replacement, and reduction of external fragmentation.

1.1 First‑Level Page Table

Before paging, linear addresses equal physical addresses. After enabling paging, the linear address becomes virtual and must be translated via the page table.

1.2 Second‑Level Page Table

Using a second‑level page table avoids the memory overhead of a full first‑level table. Only needed entries are created dynamically.

1.3 Page‑Table Entry Flags

P (Present): page is in physical memory.

RW (Read/Write): writable if set.

US (User/Supervisor): accessible from user mode if set.

PWT (Page‑Level Write‑Through): cache write‑through.

PCD (Page‑Level Cache Disable): disables caching.

A (Accessed): set when the page is accessed.

D (Dirty): set on write.

PAT (Page Attribute Table): reserved.

G (Global): prevents TLB eviction.

AV L (Available): reserved for OS.

The page‑table base address is stored in control register CR3 (Page Directory Base Register).

2. Enabling and Disabling Paging

To enable paging:

Prepare page directory and page tables.

Load the physical address of the page directory into CR3 (high 20 bits of the address).

Set the PG bit (bit 31) in CR0.

Paging works only in protected mode (CR0.PE = 1). The PG bit in CR0 determines whether paging is active.

Assembly Example (loader.s)

; os/src/boot/loader.s
[bits 32]
p_mode_start:
    mov ax, SELECTOR_DATA
    mov ds, ax
    mov es, ax
    mov ss, ax
    mov esp, LOADER_STACK_TOP
    mov ax, SELECTOR_VIDEO
    mov gs, ax

    mov byte [gs:320], 'M'
    mov byte [gs:322], 'A'
    mov byte [gs:324], 'I'
    mov byte [gs:326], 'N'

    call setup_page ; create page directory and tables

    sgdt [gdt_ptr]
    mov ebx, [gdt_ptr + 2]
    or dword [ebx + 0x18 + 4], 0xc0000000
    add dword [gdt_ptr + 2], 0xc0000000
    add esp, 0xc0000000
    mov eax, PAGE_DIR_TABLE_POS
    mov cr3, eax
    mov eax, cr0
    or eax, 0x80000000
    mov cr0, eax
    lgdt [gdt_ptr]
    ; ... (write "Virtual" characters) ...
    jmp $

setup_page:
    ; create page directory and first page table
    mov ecx, 4096
    mov esi, 0
.clear_page_dir:
    mov byte [PAGE_DIR_TABLE_POS + esi], 0
    inc esi
    loop .clear_page_dir

    ; create first PDE and map first 1 MB
    mov eax, PAGE_DIR_TABLE_POS
    add eax, 0x1000
    or eax, PG_US_U | PG_RW_W | PG_P
    mov [PAGE_DIR_TABLE_POS + 0x0], eax
    mov [PAGE_DIR_TABLE_POS + 0xc00], eax
    sub eax, 0x1000
    mov [PAGE_DIR_TABLE_POS + 4092], eax

    ; create first PTEs (256 entries for 1 MB)
    mov ecx, 256
    mov esi, 0
    mov edx, PG_US_U | PG_RW_W | PG_P
.create_pte:
    mov [ebx+esi*4], edx
    add edx, 4096
    inc esi
    loop .create_pte
    ; ... create kernel page tables ...
    ret

Macro definitions (boot.inc):

PAGE_DIR_TABLE_POS equ 0x100000
PG_P  equ   1b
PG_RW_R  equ  00b 
PG_RW_W  equ  10b 
PG_US_S  equ  000b 
PG_US_U  equ  100b

3. Paging Modes

Intel‑64 processors support four paging modes:

32‑bit paging (CR4.PAE = 0)

PAE paging (CR4.PAE = 1, IA32_EFER.LME = 0)

4‑level paging (CR4.PAE = 1, IA32_EFER.LME = 1, CR4.LA57 = 0)

5‑level paging (CR4.PAE = 1, IA32_EFER.LME = 1, CR4.LA57 = 1)

The active mode is determined by the combination of CR4.PAE, CR4.LA57, and IA32_EFER.LME.

3.1 32‑bit Mode

Uses a three‑level hierarchy (CR3 → PDE → PTE → page). Linear addresses are 32 bits, physical addresses are 32 bits, and each page table entry is 4 bytes.

3.2 PAE Mode

Extends physical addresses to up to 52 bits. Page‑table entries become 8 bytes, and an additional level (PDPTE) is introduced. CR3 now points to a Page‑Directory‑Pointer Table (PDPT).

3.3 4‑level Mode

Introduces a fourth level (PML4). Linear addresses are up to 48 bits, physical addresses up to 52 bits, and each entry is 8 bytes. CR3 holds the physical address of the PML4 table.

3.4 5‑level Mode

Extends linear addresses to 57 bits, adding a fifth level (PML5). The hierarchy is CR3 → PML5 → PML4 → PDPTE → PDE → PTE.

All modes share the same page‑size options (4 KB, 2 MB, 1 GB) and use the same flag bits (Present, RW, US, etc.).

4. Hierarchical Paging Structure

Each level contains a fixed number of entries (1024 for 32‑bit, 512 for 64‑bit modes). The low 12 bits of a linear address are the page offset; the remaining bits are split among the indices for each level.

4.1 Translation Process

Starting from the address stored in CR3, the CPU indexes the appropriate entry at each level using the corresponding bits of the linear address, until a page‑frame address is found. If a “Present” bit is clear or a reserved bit is set, a page‑fault exception is raised.

4.2 Exception‑Handling Flags

Reserved bits include MAXPHYADDR, PS bits in higher‑level entries, and the NX (No‑Execute) bit when IA32_EFER.NXE = 0.

Overall, the article provides a comprehensive overview of memory paging, page‑table structures, paging modes, and practical assembly code for enabling and inspecting paging on x86‑64 systems.