Nested Paging: Two-Dimensional Translation for Virtual Machines

A virtual machine monitor has to translate twice. The guest believes it is programming page tables that map its virtual addresses to physical addresses, and it is, but the addresses its tables contain are not physical from the host’s point of view. They are guest physical addresses, and the host has its own mapping from guest physical to host physical. A guest’s load therefore requires resolving a virtual address through the guest’s tables into a guest physical address, then resolving that address through the host’s tables into a host physical address.

The straightforward implementation is shadow paging: the monitor intercepts every guest modification of its page tables, computes the composition of the two mappings itself, and installs a single set of tables that the hardware walks directly. Guest writes to its tables trap, the monitor updates the shadow, and the guest runs with ordinary one-dimensional translation. It works, and it costs a trap per page-table update plus a great deal of bookkeeping.

Nested paging, called EPT on Intel, NPT on AMD, and stage-2 translation on ARMv8, removes the software from the path. The hardware holds a pointer to the guest’s tables and a pointer to the host’s tables, and it performs both walks itself. The guest updates its own tables freely, with no traps, and the hardware composes the translation on demand.

The Walk Multiplies

Consider a four-level guest and a four-level host, both with 4 KiB leaves. Resolving one guest virtual address requires walking the guest’s tables. Each entry in those tables contains a guest physical address, and the hardware must translate that address through the host’s tables before it can read the entry. So each of the four guest-table reads becomes a host-table walk of up to four levels.

In the worst case that is four levels of guest walk, each requiring four levels of host walk to fetch the entry, plus a final host walk of the guest’s leaf frame: twenty memory accesses instead of four. The total is not four times four in practice, because the upper levels of the host tables are shared and their translations stay cached, but the dependency chain is the same shape: a walk that misses in the translation cache can cost five times what an unnested walk costs.

This is why a nested miss is qualitatively different from an ordinary miss. The cost of the nested walk is not a constant multiple of the single-level walk that the guest’s own operating system has already been tuned for; it is a new regime in which the translation cache’s reach is effectively divided by the number of host pages needed to hold the guest’s tables.

The tables themselves also cost memory twice. The guest’s tables are data from the host’s perspective: they occupy guest physical pages, which occupy host physical frames. A guest with a large address space allocates tables that the host must map, and those host mappings are themselves entries in the host tables. The host’s page-table footprint grows with the guest’s, and a host running many guests with large footprints can spend a noticeable fraction of memory on tables that describe other tables.

Why the Translation Cache Still Works

The saving grace is that the composed translation is cached. The hardware stores, for a guest virtual page, the final host physical frame, tagged with an address-space identifier for the virtual machine. A hit requires no walk at all, of either level. The guest’s translation cache behaviour is therefore normal as long as its working set fits, and the penalty appears only on misses.

That reframes the design problem. Nested paging is expensive per miss and cheap per hit, so everything that increases the hit rate becomes more valuable than it is without nesting. Large pages are the primary tool: a 2 MiB guest page composed with a 2 MiB host page collapses three levels of the guest walk and three of the host walk into one entry, and the resulting translation covers the same 2 MiB in both dimensions. The combination is worth far more than either alone, which is why hypervisors encourage guests to use large pages and why host memory is reserved and compacted to make the corresponding host large pages available. The mechanics on the host side are those described in large pages and translation reach.

The other tool is to keep the guest’s table pages resident in the host. A guest table page that the host has swapped out turns a nested walk into a nested fault, which requires the host to fault in the table before it can complete the translation of the address that needed the table. Kernels that manage memory for virtual machines therefore pin or preferentially retain the pages that hold guest page tables, and the accounting for that is one of the places where a general-purpose memory manager needs guest-specific knowledge.

Faults Inside the Walk

The two levels can fault independently, and the combination produces cases that do not exist in a single-level system.

A guest page may be present in the guest’s tables while the corresponding guest physical page is not present in the host’s. The hardware walk reaches the guest leaf, obtains a guest physical frame, attempts to translate it through the host tables, and finds the host entry not present. The fault is reported to the host, which must decide whether to populate the host mapping, and it cannot simply populate it if the guest physical page has never been backed. This is the mechanism by which a host can overcommit guest memory: the guest’s tables describe a large address space, the host backs only the pages the guest has touched, and the rest fault on first access.

A guest page may be absent in the guest’s tables. Then the walk fails at the guest level, and the fault must be delivered to the guest rather than handled by the host. Distinguishing the two cases requires examining which level failed, which the hardware reports, and the handling is entirely different: the host either backs a page or injects a fault into the guest so that the guest’s own fault handler runs. A hypervisor that conflates the two produces a guest that either sees spurious faults or silently loses memory.

A permission mismatch is a third case. The guest may mark a page writable while the host has mapped it read-only for its own reasons, such as tracking dirty pages for live migration. The effective permission is the intersection of the two, so a write that the guest permits faults at the host level, and the host uses that fault to record the page as dirty before granting write access. This is the standard write-protection technique for migration, and it works only because the hardware applies both sets of permissions.

Memory Overhead and the Accounting Problem

The host’s tables describe the guest’s tables, and the guest’s tables describe the guest’s memory. Neither side knows the other’s costs, and both account memory in their own terms. A guest that reports its memory usage is reporting guest physical usage, which may bear little relation to the host frames actually consumed, since the host may have deduplicated identical pages, may have swapped some out, or may hold them in a compressed cache.

The host’s accounting must therefore be independent, and it must include the second-level tables, which are invisible to the guest. For a guest with a large, sparsely populated address space, the second-level tables can be a significant fraction of the host memory the guest consumes, and a host that budgets only for the guest’s declared memory will overcommit itself. The usual remedy is to charge the tables to the guest’s memory cgroup and to let the guest see the charge through ballooning, which is a mechanism that lets the host reclaim guest memory by asking the guest to release pages.

The table overhead is also sensitive to the guest’s page size choices. A guest using 4 KiB pages has many more table pages than one using 2 MiB pages, and every one of those table pages is a host frame that must be mapped. This is a case where the guest’s internal policy decision has a cost outside its own accounting, and it is one of the reasons hypervisors expose large-page support to guests even when the guest would otherwise have no use for it.

When Shadow Paging Was Better

Nested paging is not uniformly superior. Shadow paging produces a single-level walk, so its translation-cache behaviour is exactly that of a native system, and its miss cost is the ordinary one. For a workload with a large, stable working set and few page-table updates, shadow paging can therefore have a lower steady-state translation cost than nested paging.

The reason nested paging won is the update path. Shadow paging requires trapping every guest write to a page table, and a guest that creates and destroys mappings frequently, such as one running a workload with heavy mmap traffic, generates a trap storm. The monitor must also keep the shadow consistent with the guest’s tables under concurrency, which is a substantial correctness burden. Nested paging moves all of that into hardware and pays with a more expensive miss, and the trade is favourable for the general case because most workloads touch their page tables rarely relative to the number of memory accesses.

The remaining software cost is in the fault path, where the hypervisor must still interpret the hardware’s report, distinguish guest faults from host faults, and decide whether to back a page, inject a fault, or migrate the guest physical page. That path is where the complexity lives now, and it is where the interaction with the host’s own reclaim and migration machinery, described in reverse mapping and page migration, becomes visible: moving a host frame that backs a guest page requires updating the host’s tables and invalidating a translation that the guest believes is its own.