Second-Level Address Translation: Composing Two Page Walks in Hardware

Shadow paging made the guest’s page tables into data that the hypervisor watched. The hardware walked one set of tables, the hypervisor’s, and every guest write to its own tables trapped so the hypervisor could keep the two in sync. The design worked, and it charged the guest a trap for each page-table entry it wrote, which for a process that maps and unmaps memory constantly is the dominant cost.

Second-level address translation moves the composition into the page walker. The guest’s tables stay in guest memory and the hardware walks them. The addresses those tables produce are guest-physical, and before the processor fetches from such an address it walks a second set of tables, owned by the hypervisor, that map guest-physical frames to machine frames. One guest page-table write now costs nothing extra; the guest’s tables are authoritative and nothing shadows them.

Two dimensions of translation

The guest’s translation is the familiar one: a virtual address is split into indices, the root is named by the guest’s control register, and each level’s entry points to the next. In the hardware-assisted model the guest’s control register holds a guest-physical address, not a machine address, so the processor must translate the table address before it can read the table. That translation is the second level, and it applies recursively: every table read in the guest’s walk is itself an address that must be translated through the second-level tables.

The consequence is a walk whose length is the product of the two levels. On a 64-bit x86 processor the guest’s walk is four levels. The second-level structure is also four levels. A full translation with no cached intermediates therefore requires up to twenty memory references instead of four. Hardware page-walk caches absorb most of that, which is why the scheme is viable at all, but the uncached path is genuinely long, and it shows up as the latency of a TLB miss on a guest that has just changed address spaces.

The number of levels in each dimension is a design parameter, not a constant. Processors offer second-level structures with fewer levels for smaller guests, and the choice trades addressable memory against walk depth. A two-level second-level structure covers less guest-physical space but halves the references for each guest table read.

/* Walk a guest address the way the hardware does, one dimension at a time. */
static int translate_gva(struct vcpu *v, uint64_t gva, uint64_t *machine)
{
    uint64_t gpa = gva;
    int level;

    /* First dimension: the guest's own tables, addressed by guest-physical frames. */
    for (level = 4; level >= 1; level--) {
        uint64_t entry_gpa = guest_table_base(v, gva, level);
        uint64_t entry;

        /* Each table read is itself a guest-physical address. */
        if (translate_gpa(v, entry_gpa, &entry) != 0)
            return -1;
        entry = read_machine_qword(entry);

        if (!(entry & PTE_PRESENT))
            return -1;
        gpa = (entry & PTE_FRAME_MASK) | (gva & offset_mask(level));
    }

    /* Second dimension: guest-physical frame to machine frame. */
    return translate_gpa(v, gpa, machine);
}

Permission composition, now in two places

The guest’s entry carries a user/supervisor bit and a writable bit. The second-level entry carries its own writable bit, and it is enforced after the guest’s check. An access succeeds only if both levels permit it, so the effective permission is the intersection, exactly as with shadow tables, but the intersection is computed by hardware rather than by the hypervisor.

The asymmetry that causes trouble is that the second level has no user/supervisor distinction. It has read, write, and execute permissions, and nothing that says “this frame is only for the guest’s kernel”. A guest kernel at ring 0 and a guest user process at ring 3 both reach the same second-level entry, and the distinction between them is enforced entirely by the guest’s own tables. That is correct for an unmodified guest, because the guest kernel is the authority on its own address space. It becomes a problem for a hypervisor that wants to enforce something the guest does not agree with, such as marking a page execute-only or revoking a mapping the guest believes it has.

The write permission is the one hypervisors use most. Marking a second-level entry read-only is how a hypervisor implements copy-on-write across guests, tracks dirty pages for migration, and enforces a read-only shared image. The guest’s own entry stays writable, so the guest’s page-table walk succeeds and the second-level check fails, producing an exit that the hypervisor handles by performing the copy or recording the dirty bit and then upgrading the entry. The mechanism is the same as shadow paging’s write-protection, but the trap happens at the level of the data access rather than the page-table write, which is a much lower rate.

Accessed and dirty bits as a virtualization problem

The processor sets the accessed bit when it reads an entry and the dirty bit when a write succeeds. On bare metal the operating system uses those bits to approximate a reference pattern: whether a page has been touched since the last scan, whether it needs writeback. In a virtual machine the bits that matter are the guest’s, but the bits the hardware sets are in the second-level structure, which the guest cannot see.

A guest that reads its own entry and finds the accessed bit clear will conclude the page is unreferenced and reclaim it. If the hardware has been setting only the second-level bit, the guest’s conclusion is wrong, and reclaiming the page corrupts a working set. Hypervisors therefore have two options. One is to leave the second-level accessed bit clear so that the first access exits, and reflect the bit into the guest’s entry at that point, at the cost of one exit per page per scan epoch. The other is to have the guest read the bit through a paravirtualized interface, which is cheaper but requires a modified guest.

The dirty bit has the same shape and a sharper failure. A guest filesystem that flushes a page believes the page is clean afterwards. If the hypervisor’s second-level dirty bit is set and the guest’s is not, the guest may skip a writeback that the hypervisor needs for a checkpoint or a migration. Hypervisors that track dirty memory in order to copy a running machine’s memory elsewhere therefore maintain their own dirty bitmap from second-level bits and never rely on the guest’s.

Some implementations write-protect a page after the first write so that every write exits and the hypervisor can build an exact dirty log. Others clear the second-level dirty bit periodically and treat any subsequent set as evidence of a write since the last clear, which trades precision for exit count. The trade is real: an exact log costs an exit per written page per epoch, a coarse log costs an extra round of copying during migration for pages written more than once.

Large pages and the cost of splitting

Both dimensions support large pages. A guest mapping that covers two megabytes or one gigabyte collapses several levels of the guest walk into one, and a second-level entry that covers the same range collapses levels in the other dimension. A translation served by large pages at both levels can complete in a handful of references instead of twenty.

The conflict is that the hypervisor often needs finer granularity than the guest chose. Deduplicating a page, write-protecting part of a shared image, or tracking dirty pages at four-kilobyte granularity requires the second-level entry to be split from a large page into small ones. Splitting is not free: it requires allocating a new table, filling it with entries that reproduce the large mapping, and invalidating any cached translations that used the large entry. A hypervisor that splits aggressively ends up with second-level tables as large as the guest’s own, and a hypervisor that never splits cannot implement sharing at fine granularity.

The practical rule is to split lazily, when a feature needs it, and to coalesce back when the feature stops needing it. Coalescing is harder than splitting because it requires proving that every small entry in the range is identical and that nothing holds a reference to the small table. Implementations that skip coalescing accumulate fragmented tables over the life of a virtual machine.

Where the TLB fits

Every translation result is cached in the TLB, tagged so that entries from different address spaces do not collide. With second-level translation, an entry must be invalidated when either dimension changes. The guest changing its own tables is handled by the guest’s own invalidation instructions, which the hypervisor intercepts and reflects, because a guest INVLPG must invalidate the composed translation and the guest’s instruction names only a virtual address. The hypervisor changing a second-level entry must invalidate the corresponding translations itself, and the invalidation must cover every virtual address that maps through the changed guest-physical frame, which is why the reverse map from shadow paging survives even when the shadow tables do not.

Address-space identifiers reduce the flush cost and introduce their own hazard. If the hypervisor assigns identifiers to guest address spaces, it must ensure that a guest’s reuse of a virtual address under a new identifier does not leave a stale entry reachable. Some processors tag second-level translations with an identifier derived from the second-level root, which means a change of root invalidates everything without an explicit flush, at the cost of losing TLB reuse across root changes.

What the scheme does not remove

Second-level translation removes the trap per guest page-table write, which was the dominant term in shadow paging’s cost. It does not remove the need to know which guest mappings reference a frame, because invalidation, dirty tracking, and page sharing all need that relation. It does not remove the need to intercept the guest’s own invalidation instructions, because the composed translation is not the guest’s to invalidate alone. And it does not remove the exit for a page-table write that changes a mapping the hypervisor has pinned, because the second-level entry must be updated to match.

What it does remove is the composition itself, and with it the largest source of complexity in a software-virtualizing hypervisor. The remaining work is bookkeeping about frames, which is smaller and easier to reason about than a second copy of every page table in the system.