Paging & Virtual Memory

Paging is the mechanism by which a CPU translates virtual addresses (the addresses code actually uses) into physical addresses, the real locations in RAM those addresses correspond to. Every address a running program touches, from instruction fetches to data reads, passes through this translation, performed by dedicated hardware (the memory management unit) consulting a set of in-memory tables the operating system builds and maintains.

Why virtual memory

Without translation, every program would need to know the exact physical addresses of the memory it uses, and any two programs running at once would need disjoint physical memory carved out for them by convention rather than enforcement: one program’s bug could silently corrupt another’s memory, or the kernel’s own. Paging solves both problems by giving each process its own independent mapping from a private virtual address space to physical memory: two processes can use the identical virtual address for entirely different data, since the hardware translates each through a different set of tables, and a process has no way to construct a virtual address that resolves to physical memory outside its own mappings, because the mapping itself is what would have to permit it.

Paging also enables capabilities with no equivalent in a system that addresses physical memory directly. A process’s virtual address space can appear contiguous even when the physical memory backing it is scattered across RAM in unrelated locations, since only the mapping needs to be contiguous, not the underlying frames. Memory can be mapped lazily, with a page only becoming physically backed the first time it is actually touched. And more virtual memory can be promised to a process than physical memory actually exists to back, with the difference made up by moving rarely-used pages out to disk, if the operating system implements swapping.

The translation hierarchy

Rather than one flat table mapping every possible virtual address (which would be impractically large), x86-64 paging uses a multi-level tree of tables, each level narrowing down part of the address until the final physical frame is identified. In the most common configuration, a 64-bit virtual address is split into six parts: 16 bits that must currently be a sign-extension of bit 47 (limiting the actually usable range to 48 bits), four 9-bit indices selecting an entry at each of four table levels, and a 12-bit offset within the final 4 KB page.

Level	Table	Indexes	Entries
4	PML4 (Page Map Level 4)	bits 47:39	512
3	PDPT (Page Directory Pointer Table)	bits 38:30	512
2	PD (Page Directory)	bits 29:21	512
1	PT (Page Table)	bits 20:12	512

Each table holds 512 eight-byte entries, and each entry either points to the next table down or, at the final level, to a physical page frame. CR3 holds the physical address of the top-level PML4 table for whatever address space is currently active; switching CR3, as happens on every context switch between processes, switches the entire mapping the CPU uses, without needing to update the mappings themselves.

A page table entry packs a physical address alongside several control bits in its remaining space:

Bit	Meaning
0	Present: must be set or every other bit is ignored and any access faults
1	Writable
2	User-accessible: clear restricts the page to ring 0 only
3	Write-through caching
4	Cache-disabled: set for an MMIO mapping so the CPU never serves a stale cached read
5	Accessed: set by the CPU, never cleared by hardware
6	Dirty (page table entries only): set by the CPU on a write
7	Page size (huge page) at PD/PDPT level, or PAT at the final level
63	No-execute: requires the NX feature enabled via an MSR, one of the security mitigations covered separately

Walking the tables

On every memory access, the CPU takes the virtual address, splits it into the indices above, and walks from CR3 down through each table level, using each index to select the next entry, until it reaches a present entry at the final level pointing at a physical frame; at that point the 12-bit page offset is added directly, since offsets within a page require no translation. If any table walked along the way has its present bit clear, or the access violates the permissions encoded in an entry (writing to a read-only page, or executing a no-execute page), the CPU raises a page fault instead of completing the access.

Performing this four-level walk on every single memory access would be far too slow, so the CPU caches recent translations in a translation lookaside buffer (TLB) and only performs the full walk on a TLB miss. This cache is what makes changing a mapping more involved than simply rewriting the corresponding page table entry: a stale TLB entry for that virtual address may still exist and will continue to be used until explicitly invalidated, either for a single page with the invlpg instruction or, less selectively, by reloading CR3 entirely, which flushes every non-global TLB entry associated with the previous address space at once.

Huge pages

Setting the page size bit (bit 7) at the PD or PDPT level, rather than descending to a full page table, produces a 2 MB page (at the PD level) or a 1 GB page (at the PDPT level) instead of the usual 4 KB page, mapped directly by that single entry. Because a TLB has a fixed number of entries regardless of how much memory each one covers, mapping a large region with huge pages lets far more of it stay resident in the TLB at once: a workload touching gigabytes of memory can exhaust a 4 KB-page TLB’s coverage quickly, while the same memory mapped with 2 MB pages needs a thousand times fewer entries to cover the same range. The tradeoff is coarser-grained protection and allocation: an entire 2 MB or 1 GB region shares one set of permission bits and is backed as a single unit, which wastes memory if only a small part of it is actually used.

Page faults

A page fault (#PF, vector 14) is not necessarily an error condition: it is the mechanism paging uses to notify software that an access could not be completed by hardware alone, and a page fault handler is expected to distinguish several genuinely different situations using the error code pushed onto the stack alongside the fault. Bit 0 of the error code says whether the fault was caused by a page that was not present at all, versus one that was present but violated a permission check; bit 1 says whether the offending access was a write; bit 2 says whether it originated from user mode.

Two common, deliberate uses of this mechanism are demand paging and copy-on-write. Demand paging maps a page as not-present initially and only allocates and fills a real physical frame the first time a fault occurs on it, deferring the cost of backing memory until it is actually used: the basis of loading an executable’s code without reading the entire file into memory up front. Copy-on-write maps a page read-only in two or more address spaces that logically each believe they have their own private, writable copy; the first write from either side faults, and the handler at that point allocates a real private copy and updates that one address space’s mapping, leaving the other side’s mapping, and the original physical frame, untouched. This is what makes fork inexpensive despite appearing to duplicate an entire address space: no physical memory is actually copied unless and until one side writes to it.

Enabling paging

Paging is controlled by bit 31 of CR0 (PG). Setting it requires CR3 already pointing at a valid top-level table, since the very next instruction fetch after PG is set will itself be translated through the tables just installed: a kernel enabling paging must have already identity-mapped, or otherwise correctly mapped, the code currently executing, or the machine faults immediately on an instruction fetch it cannot resolve. Long mode compounds this: transitioning into 64-bit long mode requires paging already enabled with PAE (Physical Address Extension, CR4 bit 5) active, since long mode’s page table format is the PAE format extended with an additional table level, and the CPU will refuse the transition to long mode with PAE off.

Implementation notes

On a multiprocessor system, changing a mapping that another CPU may have cached in its own TLB requires more than updating the table and flushing the local TLB: a TLB shootdown is needed, typically implemented by sending an inter-processor interrupt to every other CPU that might hold the stale entry, each of which then executes its own local invlpg or CR3 reload in response before the operation is considered complete. Skipping this on SMP produces a rare, hard-to-reproduce class of bug where one CPU updates a mapping while another continues silently using the old, now-incorrect translation.

A common implementation technique for accessing page tables from within the kernel itself is recursive mapping: one entry of the top-level PML4 is made to point back at the PML4 table itself, rather than at a PDPT. Because the CPU’s page-walk logic doesn’t distinguish this case from any other, this trick makes every page table at every level addressable through a predictable, fixed range of virtual addresses, without the kernel needing to separately track or physically map each table’s location; walking through the recursive entry the right number of times lands on any table the kernel needs to inspect or modify.

References

^ Intel, Intel 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A, Chapter 4: defines the page table entry format and translation process referenced throughout this article.
^ AMD, AMD64 Architecture Programmer’s Manual, Volume 2, Chapter 5: the corresponding long-mode paging reference.

Paging & Virtual Memory

Why virtual memory

The translation hierarchy

Walking the tables

Huge pages

Page faults

Enabling paging

Implementation notes

References

See also