Memory Virtualization

You know how an OS gives each process a private virtual address space: the page tables map virtual pages to physical frames, and the TLB caches the hot translations so the MMU rarely has to walk the tables. Now put a hypervisor underneath. The guest OS also runs its own page tables, mapping guest-virtual to what it believes is physical memory — but "guest physical" is itself a fiction the VMM invented. There are now two levels of translation stacked on top of each other, and reconciling them cheaply is one of the hardest problems in virtualization. This lesson is how VMMs solve it — first in software (shadow page tables), then in hardware (nested paging).

The two-level translation problem

Follow a single guest memory access. The guest application touches a guest-virtual address (GVA). Two translations must happen before the CPU can reach real DRAM:

\text{GVA} \;\xrightarrow{\text{guest page tables}}\; \text{GPA} \;\xrightarrow{\text{VMM mapping}}\; \text{HPA}

GVA → GPA: the guest's own page tables map guest-virtual to guest-physical — the address space the guest thinks is real RAM.
GPA → HPA: but guest-physical is virtual too! The VMM has scattered the guest's "physical" memory across real host-physical frames (and may have paged some out, or shared some). So a second map, owned by the VMM, turns GPA into the true HPA.

The hardware TLB, though, only understands one mapping: virtual → host-physical. The whole problem is: how do we collapse two logical translations into what the MMU and TLB can actually cache? Two answers, a decade apart.

Answer 1 — shadow page tables (software)

The pre-hardware trick: the VMM maintains a hidden set of shadow page tables that map guest-virtual directly to host-physical (GVA → HPA), composing the two levels in advance. These shadows — not the guest's own tables — are what the VMM loads into the real \texttt{cr3}, so the hardware TLB caches GVA → HPA and memory access at steady state is native speed. Lovely — until the guest edits its page tables.

The guest thinks it owns its page tables, so when it writes a PTE the VMM must notice and update the shadow to match. The VMM write-protects the guest's page-table pages; each guest PTE write faults into the VMM, which patches the shadow and resumes. This is the dreaded page-table-update trap storm.
Every guest process needs its own shadow (a different GVA→HPA map), so the VMM keeps a pool of shadows and rebuilds/switches them on guest context switch — heavy memory and CPU overhead.

Shadow paging makes reads fast but page-table writes and context switches painfully expensive — a workload that forks and maps a lot (a build server, say) can spend a huge fraction of its time in the VMM keeping shadows in sync.

Answer 2 — nested / extended page tables (hardware)

Intel's EPT (Extended Page Tables) and AMD's NPT (Nested Page Tables) put the second map in silicon. The guest keeps and freely edits its own GVA→GPA page tables (no write-protection, no traps on PTE writes!). The VMM installs a second hardware table, the EPT/NPT, mapping GPA→HPA. On a TLB miss the MMU now performs a two-dimensional page walk, consulting both tables, entirely in hardware — no VM-exit.

The cost is that the walk is much longer. On x86-64 the guest page table has 4 levels. But every guest-physical pointer the walker touches — including the pointers inside each guest page-table level — is itself a GPA that must be translated by a full 4-level EPT walk. Lay the guest walk along one axis and the EPT walk along the other and you get a grid:

For 4-level tables this is up to (4+1)\times(4+1) - 1 = 24 memory accesses for a single TLB miss, versus 4 on bare metal. This is why the TLB (and large pages, and the page-walk caches) matter enormously under virtualization: a TLB hit costs the same virtualized or not, so the whole game is keeping the hit rate high so those 24-access walks stay rare. Nested paging trades a slow miss for eliminating the shadow-paging trap storm — and for almost all workloads that is a decisive win.

Shadow vs nested, at a glance

	Shadow page tables	Nested paging (EPT / NPT)
Who composes GVA→HPA	the VMM, in software	the hardware MMU, on each walk
TLB miss cost	4 accesses (native-length walk)	up to 24 accesses (2-D walk)
Guest PTE write	traps into the VMM (write-protected)	free — no trap
Guest context switch	expensive — switch/rebuild shadows	cheap — hardware handles it
Memory overhead	a shadow per guest process	one EPT per VM
Verdict	fast reads, costly updates	slower miss, but no trap storm — wins in practice

Reclaiming memory: overcommit, ballooning, and page sharing

The GPA→HPA indirection buys the VMM a superpower the guest can't see: it can hand out more guest-physical memory than the host truly has — memory overcommit — betting that not every guest uses its full allotment at once (just as an airline overbooks seats). But when the bet goes bad and host RAM runs low, who gives memory back? Three classic mechanisms:

Ballooning. A tiny balloon driver installed inside the guest is told by the VMM to "inflate" — it allocates guest pages and pins them. The guest's own memory manager, feeling the pressure, pages out its least-useful data to free those pages, which the VMM then reclaims as host frames. The genius is that the guest chooses what to evict (it knows best), without the VMM having to guess. Deflate the balloon to give memory back.
Transparent page sharing (content-based dedup). Many VMs run the same OS and libraries, so identical pages abound. The VMM hashes guest pages, finds duplicates, and maps them all copy-on-write to a single host frame — reclaiming the rest. VMware's ESX pioneered this; a rack of near-identical Linux VMs can share a large fraction of memory.
Hypervisor swapping. The blunt fallback: the VMM pages guest memory to its own swap file. It works but is slow and uninformed — the VMM might evict a page the guest is about to use (double paging), which is exactly why ballooning (guest-informed) is preferred.

Compute the walk cost

The simulation makes the 2-D walk concrete: it computes memory accesses per TLB miss for shadow vs nested paging at a given page-table depth, then folds in a TLB hit rate to get the effective average cost per memory reference. Watch how a high hit rate hides even a 24-access nested miss.

// Effective memory-access cost under virtualization: shadow vs nested paging. const levels = 4; // x86-64 has 4 page-table levels const tlbHitRate = 0.99; // 99% of references hit the TLB (cost ~1) const ACCESS = 100; // cycles for one DRAM access on a walk step const HIT = 1; // a TLB hit is ~free // Accesses per TLB MISS: const shadowMiss = levels; // native-length walk (VMM pre-composed) const nestedMiss = (levels + 1) * (levels + 1) - 1; // 2-D walk function effective(missAccesses: number): number { const missCost = missAccesses * ACCESS; return tlbHitRate * HIT + (1 - tlbHitRate) * missCost; } console.log(`page-table levels : ${levels}`); console.log(`shadow miss walk : ${shadowMiss} accesses`); console.log(`nested miss walk : ${nestedMiss} accesses (the '2-D walk')`); console.log(`TLB hit rate : ${(tlbHitRate * 100).toFixed(0)}%`); console.log(`\neffective cost/ref (shadow): ${effective(shadowMiss).toFixed(2)} cycles`); console.log(`effective cost/ref (nested): ${effective(nestedMiss).toFixed(2)} cycles`); console.log("\nBUT shadow paging TRAPS on every guest PTE write; nested paging does not."); console.log("=> nested trades a rare, longer miss for eliminating the page-table trap storm — usually a win.");

The design law

Under a hypervisor there are two translations: GVA→GPA (guest page tables) and GPA→HPA (VMM map). The hardware TLB caches only the composed GVA→HPA.
Shadow page tables pre-compose GVA→HPA in software: native-speed reads, but every guest page-table write traps and every guest context switch is costly.
Nested paging (EPT/NPT) lets hardware walk both tables — a 2-D page walk of up to (L+1)^2-1 accesses per TLB miss (24 for L=4) — but with no PTE-write traps; it wins on most workloads.
The GPA→HPA indirection enables overcommit, reclaimed via ballooning (guest-informed eviction), transparent page sharing (copy-on-write dedup), and hypervisor swapping (last resort).

Because the VMM is blind to guest importance. From outside, every guest page looks the same — the VMM cannot tell the guest's hot database buffer from a stale cached file. If it swaps out the wrong page, the guest immediately faults it back in, and you get double paging: the page is on the VMM's swap disk and the guest tries to page it to its own swap — two disk trips for one eviction, catastrophic. Ballooning cleverly sidesteps this by pushing the decision into the guest: the balloon driver allocates pages, so the guest's own, fully-informed memory manager decides what to evict using all its knowledge (LRU, dirty bits, working sets). The VMM gets memory back without ever guessing. It's a beautiful example of putting the policy where the information is.

The word "physical" in guest-physical address fools many students. Inside the VM, the guest OS genuinely believes GPA 0 is the first byte of real DRAM and manages "its RAM" accordingly — but GPA is just another virtual space the VMM invented. GPA 0 might live at host-physical frame 9 million, might be shared copy-on-write with three other VMs, or might currently be swapped out to the VMM's disk and not resident at all. Only the host-physical address is real silicon. Keeping the three spaces straight — GVA (guest-virtual), GPA (guest-physical/really-virtual), HPA (host-physical/real) — is the single most important discipline for reasoning about memory virtualization.

Where next

We have virtualized the CPU and memory. The last hardware resource is I/O devices — disks and network cards — where the choices between full emulation, paravirtual drivers (virtio), and direct hardware passthrough echo everything you've seen here.