Question

To support multiple virtual machines, two levels of memory virtualization are needed. Each virtual machine still controls the mapping of virtual address (VA) to physical address (PA), while the hypervisor maps the physical address (PA) of each virtual machine to the actual machine address (MA). To accelerate such mappings, a software approach called “shadow paging” duplicates each virtual machine’s page tables in the hypervisor, and intercepts VA to PA mapping changes to keep both copies consistent. To remove the complexity of shadow page tables, a hardware approach called nested page table (NPT) explicitly supports two classes of page tables (VAPA and PAMA) and can walk such tables purely in hardware.

Consider the following sequence of operations: (1) Create process; (2) TLB miss; (3) page fault; (4) context switch;

(5.14.1) What would happen for the given operation sequence for shadow page table and nested page table, respectively?

(5.14.2) Assuming an x86-based 4-level page table in both guest and nested page table, how many memory references are needed to service a TLB miss for native vs. nested page table?

(5.14.3) Among TLB miss rate, TLB miss latency, page fault rate, and page fault latency, which metrics are more important for shadow page table? Which are important for nested page table?

Assume the following parameters for a shadow paging system

TLB Misses per 1000 instructions	NPT TLB Miss Latency	Page Faults per 1000 instructions	Shadowing Page Fault Overhead
0.2	200 cycles	0.001	30,000 cycles

(5.14.4) For a benchmark with native execution CPI of 1, what are the CPI numbers if using shadow page tables vs. NPT (assuming only page table virtualization overhead)?

(5.14.5) What techniques can be used to reduce page table shadowing induced overhead?

(5.14.6) What techniques can be used to reduce NPT induced overhead?

Short answer

(5.14.1)

In shadow paging, on the creation of a new process, the hypervisor updates the shadow paging table. On TLB miss, there is no change in a page table. On page fault, mapping is updated. And on context switch, mapping is invalidated.

In a nested page table, creating a new process creates two tables for the translation of addresses. On TLB miss, both tables need to be accessed. On page fault, both tables are updated and on context switch, the page tables are invalidated.

(5.14.2)

Four memory references are needed for the native page table and 24 are needed for the nested page table.

(5.14.3)

Page fault rate is an important metric for shadow paging and TLB miss rate is an important metric for the nested page table.

(5.14.4)

CPI number for shadow paging is 1.03 and for nested page table is 1.04.

(5.14.5)

Page table shadowing induced overhead is reduced by combining the updates of multiple page tables.

(5.14.6)

NPT induced overhead can be reduced by using agile paging.

Step-by-step solution

Effect of creating process, TLB miss, page fault, and context switch on Shadow paging

(5.14.1)

The process running on a virtual machine has a guest virtual address space, guest physical address space, and host physical address space. So, every guest virtual address is first translated to a guest physical address. The guest physical address is converted to the host physical address. In shadow paging, the table contains the mapping from the guest virtual address to the host physical address.

When a new process is created, the Virtual machine creates a page table, and the hypervisor updates the table to shadow paging. The TLB does not affect the shadow paging. On page fault, the new mapping is introduced in shadow paging and the old mapping is invalidated. On a context switch, the virtual machine notifies the hypervisor to invalidate the mapping of the process.

Effect of creating process, TLB miss, page fault, and context switch on Nested Page table (NPT)

In the Nested page table, two tables are used. On to convert virtual address to physical address and converting physical address to machine address. When a new process is created, the virtual machine creates a page table and the hypervisor adds new mapping to convert the physical address to the machine address. On TLB miss, both page tables are accessed. One to convert virtual address to physical address and the other to convert physical address to machine address. On page fault, both the virtual machine and hypervisor have to update the page table. On a context switch, the virtual machine notifies the hypervisor to invalidate the mapping of the process.

Formula to calculate memory references on TLB miss for native and nested page table

(5.14.2)

For a guest page table, a 4-level page table requires a memory reference equal to the number of levels. But for the nested page table, a 4-level page table requires the following number of memory references:

Where L is a number of levels.

Calculate the number of memory references on TLB miss

The number of memory references on TLB miss for the guest page table is 4.

The number of memory references on TLB miss for nested page table is:

Metrics for shadow page table and nested page table

(5.14.3)

In shadow paging, on the occurrence of a page fault, new mapping has to be introduced between virtual and physical addresses. So, for shadow paging, the page fault rate is an important metric. In the nested page table, on TLB miss, two tables are accessed. One to convert virtual address to physical address and the other to convert physical address to machine address. So, the TLB miss rate is an important metric for the nested page table.

Formula to calculate CPI numbers

(5.14.4)

The CPI numbers are calculated using the following formula:

Calculation of CPI numbers for shadow paging and Nested Page Table

The CPI number for shadow paging is calculated below:

CPI number for Nested Page Table is calculated below:

Technique to reduce the shadowing page table overhead

(5.14.5)

The overhead of shadow paging is reduced using the nested page table. It reduces the complexity of shadow paging. The nested page table technique is better than shadow paging. This overhead can also be reduced by combining the updates of multiple page tables.

Technique to reduce the Nested Page table induced overhead

(5.14.6)

One way to reduce the overhead in the Nested page table is to use caching. Similar to TLB caching, caching is done for nested page tables and overhead can be reduced.

Another way is to use agile paging. It comprises the benefits of both shadow paging and nested page table. It enables handling of the TLB misses as fast as native and changes in the page table are done without much intervention from the virtual machine.