x86 Address Translation, Paging & TLBs

Paging is the hardware contract between an address used by an instruction and the physical location eventually accessed. On Intel 64, the common path is logical address → linear address → page-table walk → physical address. The same walk also decides whether the access is legal and which memory type applies; it is therefore simultaneously an address-translation mechanism, a protection mechanism, and part of cache control.

The address pipeline #

An x86 memory operand is not simply a physical address:

1. The instruction computes an effective offset from registers, displacement, scale, and index.
2. Segmentation combines that offset with the selected segment. In 64-bit mode, normal code and data segments are effectively flat; FS.base and GS.base remain useful exceptions. This produces a linear address.
3. Paging translates the linear address to a physical address and checks permissions.
4. MTRRs plus page attributes select the effective memory type used for the physical access.
5. The memory hierarchy satisfies the access from a cache or ultimately from the memory or I/O agent.

This vocabulary matters. CR2 receives the faulting linear address after a page fault, while a PTE contains a page-frame physical address. A user-space pointer is normally a linear address, not a physical one.

In 64-bit mode, a linear address must also be canonical. With ordinary four-level paging, bits 63:48 must repeat bit 47; with five-level paging, bits 63:57 repeat bit 56. A non-canonical address faults before an ordinary page-table translation can complete.

Paging modes and page sizes #

Intel 64 currently specifies four paging modes. The mode is selected by CR0.PG, CR4.PAE, IA32_EFER.LME, and, for five-level paging, CR4.LA57.

Physical-address width is not synonymous with linear-address width. Software obtains the implemented physical width and linear width from CPUID.80000008H; paging entries reserve physical-address bits above the implemented limit. Intel currently defines paging entries with room for physical addresses up to 52 bits, but a particular processor may implement fewer.

A four-level page-table walk #

For a 4 KiB mapping, the processor uses the address fields as follows:

Each table is naturally aligned and 4 KiB long. Each entry is 8 bytes, so a table holds exactly $4096 / 8 = 512 = 2^9$ entries. That is why every level consumes nine address bits.

The address of an entry at a level is:

$$\text{entry\_address} = \text{table\_base} + 8 \times \text{index}$$

If the entry points to another table, its physical-address field becomes the next table_base. If it maps a page, the frame address from the entry is combined with the remaining low address bits.

For the canonical address 0x00007f12_3456_789a, the four indices are 254, 72, 418, and 359; the byte offset is 0x89a. This NASM fragment performs the same bit slicing for the PML4 index:

; RDI = canonical linear address
mov rax, rdi
shr rax, 39
and eax, 0x1ff            ; RAX = PML4 index, 0..511

The code computes an index only. It does not make page-table memory directly accessible: the tables are addressed physically by the page walker, while kernel software normally reaches them through a deliberate virtual mapping.

Large pages terminate the walk early #

The PS bit changes whether an intermediate entry points downward or maps a page:

• a PDPTE with PS=1 maps a 1 GiB page when the processor supports it;
• a PDE with PS=1 maps a 2 MiB page;
• a PTE always maps a 4 KiB page.

The unused low physical-address bits become the larger page offset: 30 bits for 1 GiB and 21 bits for 2 MiB. Consequently, the physical frame must be aligned to the page size.

Large pages reduce walk depth and increase TLB reach, but they also increase internal fragmentation, make fine-grained protection harder, and amplify the cost of copying or reclaiming a mapping. See Huge Pages & TLB Pressure for the operating-system trade-off.

What a paging entry means #

The leaf and non-leaf entries share several important flags. For an access to succeed, relevant restrictions accumulate across every entry used by the walk; a permissive leaf cannot override a restrictive ancestor.

CR4.SMEP prevents supervisor instruction fetches from user pages. CR4.SMAP normally prevents explicit supervisor data accesses to user pages unless the kernel deliberately opens the access window through EFLAGS.AC. These checks complement U/S; they do not replace it.

Page faults are a structured diagnostic #

A page fault (#PF, vector 14) means either that translation failed or that the completed translation denied the attempted access. Hardware records the faulting linear address in CR2 and pushes an error code describing the access.

Demand paging deliberately uses the not-present case. The kernel locates or creates a physical frame, updates the paging structures, performs any required invalidation, and returns from the exception. The faulting instruction is then restarted. The hardware supplies the mechanism; eviction policy, copy-on-write, swap, and file-backed mappings belong to Virtual Memory & Paging.

TLBs and page-walk caches #

Walking four memory-resident tables for every load would be prohibitively expensive. Processors therefore cache translation information in two conceptually distinct places:

• TLBs cache completed page-number → page-frame translations together with access rights and memory type;
• paging-structure caches cache information from non-leaf entries so a later walk can begin below the root.

These are not data caches. A data-cache hit answers “where are the bytes for this physical cache line?” A TLB hit answers “which physical page and permissions correspond to this linear page?” One memory access can hit one cache and miss the other.

CR4.PCIDE enables process-context identifiers. With PCID enabled, the low 12 bits of CR3 tag an address space, allowing non-global translations for several address spaces to coexist. Global translations, enabled through CR4.PGE and the entry's G bit, are intended for mappings shared across address spaces, such as kernel mappings. PCID and global pages reduce flushes; they do not make stale translations self-invalidating.

Changing a PTE is a publication protocol #

Page tables live in coherent memory, but the translation caches are architecturally allowed to retain information derived from the old entry. Updating an entry and invalidating its cached consequences are separate operations.

A safe unmap-and-reuse sequence has this shape:

1. Serialize page-table writers with the kernel's page-table lock or equivalent protocol.
2. Clear P or install the intended replacement entry with an aligned, atomic update appropriate to the table format.
3. Invalidate the affected translation on every logical processor that may use that address space.
4. Wait until those processors have acknowledged the invalidation.
5. Only then reuse the old physical frame or the linear range for an incompatible purpose.

On the current logical processor, INVLPG invalidates the translation for one page containing the supplied linear address and also invalidates paging-structure-cache entries associated with the current PCID as specified by the architecture:

; Ring 0. RDI is any linear address inside the changed mapping.
; The page-table update must already be visible under the OS protocol.
invlpg [rdi]

MOV to CR3, toggling CR4.PGE/CR4.PCIDE under their architectural rules, and INVPCID provide broader or PCID-aware invalidation choices. Their exact coverage differs, especially for global entries; choose the operation from the required invalidation set rather than from folklore.

; Broad current-context refresh when PCID/global semantics permit it.
mov rax, cr3
mov cr3, rax

Both fragments use privileged instructions and belong in kernel or bare-metal code. They assemble as ordinary NASM syntax but fault if executed without the required privilege.

On a multiprocessor system, local INVLPG is insufficient when another logical processor may have cached the translation. The operating system sends interprocessor interrupts or uses an equivalent rendezvous so every affected processor invalidates and acknowledges: this is a TLB shootdown.

Two subtleties explain many low-level bugs:

• Changing P from 0 to 1 needs no invalidation only if no stale translation from an earlier present lifetime remains. If an earlier 1 → 0 transition was not invalidated, that assumption is false.
• Clearing A or D without invalidation can leave hardware using a cached translation and therefore fail to set the cleared memory bit on a later access. A clear bit is then not trustworthy evidence that the page was untouched.

Worked update scenarios #

The architecture permits delayed invalidation only when software can tolerate accesses using either the old or new translation during the delay. That is a narrow concurrency proof, not a general optimization.

Diagnostic checklist #

When a mapping behaves impossibly, inspect the layers in order:

1. Is the input address canonical, and is it the expected linear address after segmentation?
2. Which paging mode is active? Read CR0, CR4, IA32_EFER, and the implemented address widths.
3. Does CR3 identify the expected root and PCID?
4. At each level, are P, reserved bits, frame alignment, and the next-level physical address valid?
5. Which ancestor first restricts R/W, U/S, or XD?
6. Do SMEP, SMAP, PKU/PKS, CET, or CR0.WP change the result?
7. Decode CR2 and the complete #PF error code rather than logging only “page fault.”
8. If memory disagrees with observed behavior, was the required local invalidation and remote TLB shootdown completed?
9. If the problem is cacheability rather than translation, inspect PAT/MTRR state separately; INVLPG and CLFLUSH solve different stale-state problems.

The decisive mental model is that a page-table edit changes memory, while an invalidation changes what the translation machinery is allowed to remember. Correct system software must publish both halves of that state transition.