Nested Paging: The Two-Dimensional Walk and the Cost of a Single Guest Access

A guest kernel maintains page tables that map guest-virtual addresses to what it believes are physical addresses. Those addresses are not physical. The host must translate them again, from guest-physical to host-physical, before the memory controller sees them. Nested paging makes the processor perform both translations in hardware on every access. It replaces the older technique of shadow page tables, in which the hypervisor maintained a merged table so the guest’s writes had to be trapped and propagated. The trade is stark: nested paging removes a trap per guest page-table update and adds a second level of translation to every single memory reference.

Two hierarchies, one walk

The guest’s tables are ordinary x86-64 tables with a four-level structure: PML4, PDPT, PD, and PT, each level consuming nine bits of the virtual address and each entry pointing to the next table. The host maintains a parallel structure, the extended page table on Intel or the nested page table on AMD, whose entries map guest-physical page numbers to host-physical page numbers. The EPT itself is also four levels, indexed by the guest-physical address in the same nine-bit chunks, and its entries carry permission bits and a accessed/dirty pair.

The consequence is that resolving one guest load can require walking up to twenty memory reads. Four reads traverse the guest tables to find the guest-physical address of the target page. Then, because each of those four reads is itself a memory access to a guest-physical address, each must be translated through the EPT, which is another four reads. Twenty reads, each of which may miss in the data cache, and the final one is the access the guest actually wanted. Real implementations are far more efficient because they cache intermediate translations, but the worst case is the worst case, and it sets the design constraints.

On AMD the structure is slightly different: the nested page table has the same four-level shape, and the guest page table walk is performed with the same hardware walker. The performance characteristics are close enough that the analysis carries over.

/* Worst-case memory reads for one cold guest access. Each read of a guest
   page-table entry targets a guest-physical address, so the second level
   must translate it too. The final data access needs a translation as well. */
static int cold_nested_reads(int guest_levels, int host_levels)
{
    return guest_levels * host_levels + host_levels;
}

/* 4-level guest tables behind a 4-level EPT cost 4 * 4 + 4 = 20 reads.
   A 2 MiB guest page removes one guest level and a 2 MiB EPT mapping
   removes one host level: 3 * 3 + 3 = 12. */

What the hardware caches and why it matters

A TLB entry produced by a nested walk caches the composite translation, guest-virtual to host-physical, tagged with the address-space identifier of the guest’s table and the identifier of the EPT. A second-level cache holds translations of guest-physical to host-physical, so that a new guest page-table entry pointing to an already-mapped guest-physical page does not require a fresh EPT walk.

The practical effect is that a guest with a large working set and frequent address-space switches pays for nested walks repeatedly, while a guest running one process with a stable mapping pays almost nothing after warm-up. This is the single largest source of variance between workloads on identical hardware, and it explains why benchmarks of nested paging disagree so widely.

There is a second, subtler cache effect. The hardware walker must consult the guest’s page-table entries in memory. Those entries live in pages that the host has backed, and reading them costs cache lines. A guest whose page tables are large and cold causes the walker to pull in four cache lines per level, and the walk’s latency becomes memory latency multiplied by depth rather than a cache hit. A 64-byte cache line holds eight 8-byte entries, so a table with entries spread across many pages has poor locality even though each individual entry is small.

Permission composition and the EPT violation

An access succeeds only if both levels grant it. The guest’s page-table entry must permit the access, and the EPT entry must permit it as well. Write permission is not inherited: an EPT entry that is read-only makes the page read-only regardless of what the guest’s own tables say, which is how the hypervisor implements copy-on-write and dirty tracking without modifying guest tables.

When the check fails, the processor exits with an EPT violation, and the exit qualification reports four independent facts. It says whether the access was a read, a write, or an instruction fetch, with the three bits potentially combined for a read-modify-write instruction. It says whether the faulting address was translated through the guest’s tables at all, distinguishing a failure in the guest-virtual walk from a failure in the second-level walk. It says whether the access was to a guest-linear address or directly to a guest-physical address, which matters for instructions that bypass paging. And it reports whether the violation occurred while the processor was translating a guest page-table entry for another access, which tells the handler that the fault is in a table page rather than a data page.

That last bit is not a curiosity. If the hypervisor has not yet backed the page containing a guest page-table entry, the walk itself faults, and the handler must populate that page before the original access can be retried. Handlers that only consider the guest’s data pages will loop.

The qualification also carries the guest-linear address and the guest-physical address when they are available, which lets the handler avoid re-walking the tables itself. On hardware where a guest-physical address is not supplied for a particular violation class, the handler has to walk the guest tables in software to discover which page to map, and that walk is several dependent memory reads.

Populating on demand without thrashing

The standard use of EPT violations is lazy backing. The hypervisor maps a guest-physical page the first time the guest touches it, so that a virtual machine’s memory footprint tracks what it actually uses rather than what it was assigned. This is the mechanism that makes memory overcommit possible, and it produces a predictable pattern: a burst of violations as the guest touches new pages, then silence.

The pattern degrades badly when the hypervisor reclaims pages it previously mapped. Each reclaim converts a future access into another violation, and the guest’s own page cache makes this worse: a guest that believes a page is resident will touch it again, generating a violation, a host-side fault, a possible I/O read, and a mapping. The guest has no way to know its page was taken away, because the EPT entry is invisible to it. This is why the balloon driver exists: it gives the guest a way to participate in the decision rather than discovering it through repeated faults.

Another failure mode is the page-table walk fault. A guest that allocates a new page table touches a page that itself needs mapping. The handler must be reentrant with respect to its own page-table accesses, because servicing the fault requires the hypervisor to read guest memory, which can fault again. Implementations handle this by pre-mapping the structures the handler needs or by using a separate address space for host access to guest memory, but the general problem of a fault handler that faults is a real source of complexity.

Large pages and the walk that disappears

Both levels support large pages: a 2 MiB page at the second level of the guest hierarchy and at the corresponding level of the EPT, and a 1 GiB page one level up. A 2 MiB EPT entry collapses one level of the second walk, and a guest using 2 MiB pages collapses one level of the first. Combined, a 2 MiB guest page backed by a 2 MiB EPT entry reduces the twenty-read worst case to roughly twelve, and the TLB entry covers 2 MiB of address space instead of 4 KiB.

The catch is that large pages require contiguity at both levels and are therefore hard to obtain after a system has fragmented. A hypervisor that backs guest memory with 4 KiB host pages cannot offer a 2 MiB EPT mapping even if the guest uses huge pages, because the underlying host frames are scattered. This is why backing guest memory with huge pages at allocation time, rather than on demand, changes nested paging performance more than any handler optimization.

The reverse also holds. A guest that uses 4 KiB pages throughout forces a four-level walk at both levels no matter how the host is configured. The guest’s choice of page size and the host’s choice of backing granularity are independent decisions that multiply, and either one alone limits the benefit.

When shadow paging wins

Shadow paging, the predecessor, keeps a single merged table that the hardware walks once. Access is therefore as cheap as bare metal. The cost moves to maintenance: every guest write to a page-table page must be trapped, the shadow must be updated, and the TLB entries derived from the old shadow must be invalidated. A guest that maps and unmaps memory frequently, such as one running a workload with many short-lived processes, generates a write trap per page-table update.

The trade is between a per-access cost and a per-update cost. Workloads with high update rates and low access rates, such as a guest that forks repeatedly but touches little memory, can favor shadow paging. Workloads that read far more than they remap favor nested paging. Modern hardware makes the first case rare enough that nested paging is the default, but the analysis is the reason hypervisors retained a shadow mode for a long time, and the reason a guest’s page-table behavior is a first-order performance property rather than an implementation detail.

Both schemes interact with the TLB in ways that invalidation and address-space tagging determine, since the cost of a stale translation is paid either at the walk or at the flush.