TLB Tagging and Nested Invalidation: Keeping Translations Alive Across a VM Boundary

A translation lookaside buffer is a cache of address translations, and caches are invalidated by context changes. On a bare machine, switching processes by writing CR3 invalidates entries tagged with the outgoing address space, which is why processors grew the cruder approach first and the finer one later. A virtual machine adds a second context change, the transition between host and guest, and without care that transition would invalidate everything the guest had cached.

The design question is what a TLB entry should be tagged with, and how many orthogonal identifiers a processor can maintain before the tag comparison becomes the expensive part of a lookup.

The two identifiers a guest needs

Without hardware assistance, a hypervisor has no way for the processor to distinguish the guest’s translations from its own, so the safe choice is to flush on every transition. That makes an exit cost more than the state save: it costs the entire address-translation working set, and the guest must re-walk its tables after every entry. For a guest that exits frequently, the TLB refill dominates.

Virtual processor identifiers remove that flush. On Intel VT-x the identifier is a 16-bit field stored in the control structure, and entries generated while the guest runs are tagged with it. Entries generated in host context carry a different tag, or no tag that the guest’s can match. An exit does not invalidate guest entries; the entry back into the guest rediscovers them. AMD’s equivalent is the address-space identifier, and the concept is common enough that hypervisors abstract it.

Within the guest, the same problem appears at the process level. A guest kernel switching processes writes CR3, and each write would invalidate the guest’s translations if the processor treated each CR3 value as a distinct space by default. Process-context identifiers let the guest assign a short tag to each address space so that switching between two of them leaves both sets of entries intact. A guest that never uses them pays a full refill on every context switch, which is the largest single source of avoidable TLB misses in a virtual machine that is otherwise well configured.

The two identifiers compose. A translation cached while the guest ran process A in a particular virtual machine is valid only while the guest is still running process A and still in that virtual machine. The processor matches both tags, plus the identity of the second-level translation structure, before accepting the entry.

What the second level adds

With nested paging, a TLB entry represents a composition: a guest-virtual page to host-physical page mapping, derived from the guest’s table entry and the extended page table entry that resolved the guest-physical address. The composition means the entry depends on more state, and invalidation must consider changes at either level.

The processor provides separate invalidation instructions for the second level, and their granularity choice is the interesting part. One form invalidates all entries derived from a given second-level structure, which is the right response when a hypervisor changes an EPT entry and needs every cached translation derived from that EPT to disappear. Another invalidates entries from every such structure, which is the nuclear option: it discards translations belonging to other guests running on the same physical processor. The third form considers only entries that might be affected by a specific guest-physical address.

The cost ordering follows the granularity. Invalidating one address is cheap but requires the hypervisor to have precise knowledge of what changed. Invalidating all entries derived from one EPT is moderate and is the common case, because a hypervisor that changes a memory mapping knows which guest it belongs to. Invalidating everything is the fallback for cases where the hypervisor cannot prove that a narrower invalidation is sufficient, such as when it removes a memory slot that many address ranges could reference.

The address form is the finest the second level offers, and it is coarser than its name suggests. It is defined to invalidate every cached translation that might be affected by a change to the given guest-physical address, which permits an implementation to discard more than the one page: entries for the same second-level structure that the processor cannot prove are unrelated may go as well. A hypervisor that unmaps four kilobytes therefore cannot assume that only four kilobytes of cached translation disappeared, and a hypervisor that relies on that assumption will be correct on one microarchitecture and wrong on the next.

Page-walk caches and the entries that are not in the TLB

The TLB is not the only structure holding translations. Processors keep caches of intermediate page-table entries, and they may cache the final translation without caching the path that produced it. When the hypervisor or guest changes a table entry, these caches must be invalidated too, and the invalidation instructions are defined to cover them.

This matters because a page walk that hits an intermediate cache is much faster than one that does not, and it explains a behaviour that surprises people who reason only about TLB capacity: a system can have a high TLB hit rate and still see walk cost, because misses that are followed by cached intermediate entries are cheap while misses that are not are not. It also explains why the invalidation granularity is defined in terms of what is architecturally visible rather than in terms of what the caches actually hold. Implementations are free to keep more state than the architecture describes, and they are responsible for invalidating it correctly; the software contract is only that after the invalidation instruction, no stale translation is observable.

A hypervisor that modifies second-level entries without requesting invalidation is therefore not merely slower, it is incorrect, and the failure is silent: the guest reaches a page it should not reach, or fails to reach one it should.

Shootdowns in the guest and their amplification

A guest with multiple processors must invalidate translations on all of them after changing a shared mapping. The guest sends an inter-processor interrupt and each target invalidates locally. The cost has three parts: delivering the interrupt, performing the invalidation, and waiting for acknowledgement.

Under virtualization, the first part becomes a virtualization cost. An IPI written to the interrupt command register may be an emulated access, and its delivery to another vCPU may take the interrupt injection path rather than a hardware shortcut. The second part is where the guest’s choice of granularity matters, and the third part is where CPU overcommit shows up: a target vCPU that is not currently running cannot invalidate anything, and the sender must wait until the host schedules it. Under heavy vCPU oversubscription, a shootdown that costs a few microseconds on bare metal can cost milliseconds, and the guest’s kernel sees this as lock-held time in the page-table locks.

/* Batched invalidation: per-page instructions are cheap only for short ranges. */
void flush_range(unsigned long start, unsigned long end)
{
    unsigned long pages = (end - start) >> 12;

    /* A full reload discards unrelated mappings; only do it when the range
       is large enough that the per-page cost would exceed the refill cost. */
    if (pages > 64) {
        unsigned long cr3;
        __asm__ __volatile__("mov %%cr3, %0" : "=r"(cr3));
        __asm__ __volatile__("mov %0, %%cr3" : : "r"(cr3) : "memory");
        return;
    }
    for (; start < end; start += 4096)
        __asm__ __volatile__("invlpg (%0)" : : "r"(start) : "memory");
}

The threshold in a function like this is a microarchitectural parameter, not a constant: the cost of one page invalidation and the cost of refilling the entries a full flush discards both vary by processor, and the refill cost depends on how much of the working set the process is actually using.

Huge pages change the shape of both problems

A 2 MiB translation covers the address range of 512 base pages with a single entry, and a 1 GiB translation covers 512 of those. The TLB is entry-limited rather than byte-limited, so the reachable footprint for a given number of TLB entries grows by three orders of magnitude between base pages and gigabyte pages. This is the main reason large pages are worth pursuing inside a guest, and it is also the reason a guest using large pages has far fewer invalidation events to issue.

The cost is granularity in the other direction. Invalidating a range that partially overlaps a large page cannot preserve the rest of the page’s translation, because the translation is a single entry. Changing the protection of one base page inside a 2 MiB region can force the entire region to be split, which means allocating a new table level, updating the parent entry, and invalidating the entry that is being replaced. A guest that mprotects small regions of large-page-backed memory one at a time will spend its time splitting pages, which is why the kernel tends to avoid faults on large pages for small writes and why transparent huge pages are used with care for workloads with fine-grained protection changes.

For the hypervisor, the same logic applies to the second level. Backing a guest with 2 MiB host mappings reduces walk depth and entry pressure, but a change to any page within that region requires either invalidating the whole 2 MiB entry or splitting the mapping. A hypervisor performing device assignment or memory hot removal at base-page granularity will fragment its second-level tables, and the fragmentation persists until the guest’s memory is defragmented, which under on-demand backing may never happen.

Knowing whether invalidation is the problem

Two counters distinguish an invalidation problem from a capacity problem. The first is the number of invalidation instructions issued per unit of work, which is visible from the hypervisor’s side for second-level invalidations and from the guest’s side for first-level ones. The second is the walk cost, approximated by the number of cycles spent on misses, which on hardware with performance monitoring is available as a counter.

A system with many invalidations and few walks is spending its budget on overhead that better batching or better tagging removes. A system with few invalidations and many walks needs larger pages or a working set that fits. The two diagnoses suggest opposite remedies, and the underlying events are close enough in an unqualified profile that they are routinely confused.