Part 4 of 6 · 3 min read
Shadow tables and nested paging
Think of a translator who must turn English into Spanish and then Spanish into Hindi for each sentence. A faster way is to prepare a direct English to Hindi book, but it must be rewritten whenever either dictionary changes. The analogy stops in one place: a dictionary is read by a person, while the hardware reads tables in memory and caches the results in the TLB.
In plain words: Two designs exist. With shadow page tables, the hypervisor builds one combined table GVA to HPA for each guest process and gives it to the hardware. Every time the guest changes its own table, the write traps, and the hypervisor updates the shadow. Walks are as short as native ones, and page-table changes are slow. With nested paging (Intel EPT, AMD NPT), the hardware knows both tables and walks them itself. The guest changes its table freely without trapping. A TLB miss costs more, because each of the guest's table pointers is itself a guest physical address that must be translated by the second table. Nearly all current systems use nested paging, and the TLB (Level 6) hides most of the extra cost.
A worked example. The count of memory references for one TLB miss with g guest levels and h host levels is (g + 1) x (h + 1) - 1. This program prints it.
#include <stdio.h>
/* memory references for one TLB miss: guest levels g, host (nested) levels h */
static int refs_native(int g) { return g; }
static int refs_nested(int g, int h) { return (g + 1) * (h + 1) - 1; }
int main(void) {
int g[] = {4, 4, 5, 5}, h[] = {4, 5, 4, 5};
printf("native 4 levels: %d references\n", refs_native(4));
for (int i = 0; i < 4; i++)
printf("nested guest %d x host %d levels: %d references\n",
g[i], h[i], refs_nested(g[i], h[i]));
return 0;
}
native 4 levels: 4 references
nested guest 4 x host 4 levels: 24 references
nested guest 4 x host 5 levels: 29 references
nested guest 5 x host 4 levels: 29 references
nested guest 5 x host 5 levels: 35 references
A native four-level walk reads 4 table entries, and a nested one reads 24: six times more. Take a made-up workload where 99 of 100 accesses hit the TLB (1 memory reference for the data) and 1 misses. Native: 0.99 x 1 + 0.01 x (4 + 1) = 1.04 references per access. Nested: 0.99 x 1 + 0.01 x (24 + 1) = 1.24. The VM does 1.24 / 1.04 = 1.19 times as many memory references, 19 per cent more, and the share grows when the miss rate is higher. This is why huge pages (Level 7) matter even more in VMs: a huge page makes a walk shorter and a TLB entry cover more.
The key lines. Shadow tables make a walk cheap and a table update expensive. Nested paging does the reverse. The choice follows the workload, and the hardware made nested paging the default.
Nested paging
Nested paging (Intel EPT, AMD NPT) is hardware support in which the processor translates a guest virtual address through the guest's page table and then every guest physical address through a second table owned by the hypervisor, so that the guest can change its own table without trapping.
Example: a TLB miss in a 4-level guest on a 4-level host reads (4 + 1) x (4 + 1) - 1 = 24 entries.
Check yourself: 1. What must happen under shadow tables when the guest changes its page table? 2. How many references does a 4 by 4 nested walk need? 3. Why do huge pages help a VM even more than a native system?