Shadow Page Tables: Keeping Two Guest Mappings Consistent With One Hardware Walk

A guest kernel builds page tables that map guest virtual addresses to what it believes are physical addresses. The processor walks those tables using a control register the hypervisor controls, and the physical addresses it produces must be real ones. The hypervisor therefore cannot let the guest’s tables be used directly, because the guest’s “physical” addresses are not the machine’s. Something has to translate the guest’s translation, and before hardware offered a second walk, the hypervisor did it by hand.

Shadow paging is the name for that hand translation. The hypervisor keeps a second set of page tables, in the format the hardware walks, whose entries map guest virtual addresses directly to machine frames. The guest’s own tables are never loaded into the page-table base register. They exist as data, and the hypervisor treats writes to them as events.

The translation that must happen twice

Take a guest that maps virtual address 0x400000 to guest-physical 0x1a000, and a hypervisor that has placed the guest’s frame 0x1a000 at machine frame 0x9f3000. The guest’s page-table entry holds 0x1a000 with a present bit. The hardware, if handed that entry, would fetch from machine address 0x1a000, which belongs to some other guest or to the hypervisor itself.

The shadow entry must instead hold 0x9f3000 with the same permission bits. Composing the two translations is straightforward for a single level: walk the guest’s tables to find the guest-physical frame, then consult the hypervisor’s frame map to find the machine frame, then write a shadow entry that skips the middle step entirely. The shadow table is thus a flattened composition of two mappings, and it is flattened because the hardware knows only how to do one.

The difficulty is not the composition. It is that the guest can change its tables at any time, and the shadow must follow. A guest kernel writing a page-table entry is performing an ordinary memory write to a page it owns. Nothing about that write faults by default, so without intervention the shadow table silently diverges from the guest’s intent: the guest believes it unmapped a page, the hardware still has a valid shadow entry, and the guest’s user process can keep reading memory the guest kernel thought it had revoked.

Write-protecting the tables, not the data

The fix is to make page-table writes visible. The hypervisor marks every guest page that contains page-table entries as read-only in the shadow tables. A guest write to such a page then causes a protection fault, which the hypervisor intercepts, decodes, and reflects into the shadow. This is the mirror image of ordinary shadowing: the shadow tables describe guest memory, and the guest’s page-table pages are shadowed with a permission the guest did not ask for.

Marking them read-only requires knowing which guest pages they are. The guest tells the hypervisor where its top-level table is by loading the page-table base register, which faults and is emulated. From that root the hypervisor can walk the guest’s tables and discover the lower levels, marking each one read-only as it goes. Every level that the walk touches becomes a trapped page, and the set grows as the guest maps more of its address space.

The bookkeeping needed for the reverse direction is larger. When a guest write changes an entry, the hypervisor must find every shadow entry that depended on it. A single guest page-table page can be referenced by many shadow tables if the guest shares page tables between address spaces, and a single guest-physical page can appear in many guest mappings. The structure that answers “which shadow entries derive from this guest entry” is a reverse map: a table keyed by guest-physical frame listing the shadow entries that reference it.

/* On a write-protection fault from the guest at gpa, inside a page-table page. */
static void shadow_write_fault(struct vcpu *v, uint64_t gpa, uint64_t value)
{
    struct shadow_pte *spte;

    /* The guest's write already happened in its own memory; read it back. */
    write_guest_phys(v, gpa, value);

    list_for_each(spte, rmap_lookup(v->shadow, gpa)) {
        if (guest_entry_now_invalid(v, spte->gpte_addr)) {
            shadow_pte_clear(spte);        /* unmap in the shadow tables */
            invlpg_for(spte);              /* and drop the stale TLB entry */
        } else {
            spte->frame = machine_frame_of(v, guest_frame_of(v, spte->gpte_addr));
            spte->flags = permission_bits_of(v, spte->gpte_addr);
            invlpg_for(spte);
        }
    }
}

Two costs hide in that snippet. The reverse map must be maintained on every shadow entry creation and destroyed on every teardown, which means the hypervisor touches memory proportional to the number of mappings the guest has, not to the number it is changing. And every invalidation must be paired with a TLB flush for the affected address, because the processor caches translations and a stale entry survives the shadow table update.

Permission composition and the access-bit problem

Permissions in a shadow entry are not simply copied from the guest entry. The shadow entry must express the intersection of what the guest permits and what the hypervisor permits. If the guest marks a page writable but the hypervisor has decided that page is shared and must be tracked for copy-on-write, the shadow entry is read-only and the guest’s write traps to the hypervisor, which performs the copy and then upgrades the shadow entry. That mechanism is the basis of memory sharing and deduplication, and it lives entirely in the shadow layer.

The intersection has an asymmetry that causes real bugs. The hardware sets the accessed and dirty bits in the entry it walks, which is the shadow entry. The guest expects those bits to appear in its own entries, because guest software reads them to decide whether a page has been referenced or modified. A hypervisor that only propagates permissions in one direction loses that information. The usual remedy is to have the shadow entry start with accessed and dirty clear, so the first access faults, and to reflect the hardware-set bits back into the guest entry during the fault. The cost is one extra fault per page per epoch, which is why shadow paging implementations batch the reflection.

The user/supervisor bit interacts with the privilege arrangement described in ring compression. A guest kernel at ring 1 and its user processes at ring 3 differ in privilege, so the bit means what the guest thinks it means. A compressed guest at ring 3 has no such distinction, and the shadow layer must then enforce the guest’s intended privilege in software rather than in the entry.

Global pages, PCIDs, and flushes that are too wide

A guest kernel typically maps its own code and data into every address space and marks those entries global, so a context switch does not flush them. The shadow equivalent is harder: the shadow tables for two guest address spaces are distinct, so a global guest mapping appears in both, and a change to it must invalidate both. Global entries are therefore a special case in the reverse map, and an implementation that ignores them produces a guest that sees stale code after modifying a shared library page.

Address-space identifiers make the same problem cheaper and more dangerous. The processor can tag TLB entries with an identifier so that switching address spaces does not require a flush. The hypervisor controls the identifier field, so it can assign identifiers to guest address spaces and avoid most flushes. The danger is that the guest also has its own notion of address-space identifiers, and the two numbering schemes must not collide. Hypervisors that pass the guest’s identifiers through directly inherit a correctness bug when the guest reuses an identifier for a different address space, because the TLB entry from the old space survives.

The cheapest correct policy is to flush on every shadow table update and accept the cost, which is what early implementations did and why their page-fault-heavy workloads suffered. The better policy is to flush narrowly, by virtual address, and to keep a generation counter per shadow table so that stale entries are distinguishable without a global flush.

Where the model stops paying

Shadow paging has one property no hardware scheme reproduces: the shadow tables are ordinary memory owned by the hypervisor, so the hypervisor can put any permission in them, for any reason, at any granularity. Copy-on-write, page sharing, dirty tracking for migration, and execute-only enforcement all compose into the same structure.

The cost is that every guest page-table write becomes a trap, every trap becomes a reverse-map walk, and every walk becomes a TLB invalidation. A guest that creates and destroys address spaces quickly, which is what a fork-heavy workload does, generates a trap storm. Adams and Agesen measured the effect on x86 and found shadow paging losing badly on workloads that touch page tables frequently, while remaining competitive where the guest’s mappings are stable.

That measurement is the argument for second-level address translation, which removes the composition from software and gives it to the page-table walker. It does not remove the need for the reverse map, because dirty tracking and page sharing still require knowing which guest mappings reference a frame. It removes the trap per page-table write, which was the dominant term. The shadow layer survives in reduced form: not as a translator, but as a recorder of what the hardware walk did.