Tribute to hackers | Review of the exploration of memory virtualization

[[415610]]

Cloud and virtualization

Cloud computing is a computing model that provides dynamic and scalable resources through Internet services. After years of development, it has become an important support for enterprise IT technology. Virtualization is one of the core technologies of cloud computing. It abstracts a computer into multiple logical computers, namely virtual machines. Each virtual machine is a separate and secure environment that can run different operating systems without affecting each other.

Virtualization technology has greatly facilitated resource usage and scheduling. Cloud computing systems can schedule resources in a timely manner according to load conditions, improving resource utilization while ensuring that applications and services will not be affected by insufficient resources. However, virtualization also has a price. The abstraction of resources has brought performance losses, which is also a problem that virtualization has been committed to solving.

Virtualized resource abstraction can be simply divided into three parts: CPU virtualization, memory virtualization, and device virtualization . Device virtualization can already realize direct access to virtual machines for network, storage and other devices without performance loss; CPU virtualization, with the support of hardware features, has the same performance as bare metal in executing common instructions; while memory virtualization is still significantly different from bare metal, which is an issue worthy of attention at present.

Memory Virtualization

Virtual memory : When it comes to memory virtualization, we have to mention the concept of virtual memory. Early operating systems only had physical addresses and limited space, so processes had to be careful when using memory to avoid overwriting the memory of other processes. To avoid this problem, the concept of virtual memory was abstracted to ensure that each process has a continuous, independent virtual memory space. The process uses memory directly through VA (Virtual Address). The VA issued by the CPU when accessing memory is intercepted by the hardware MMU (Memory Management Unit) and converted to PA (Physical Address). The mapping from VA to PA is managed using a page table, and the MMU automatically queries the page table during the conversion.

Memory virtualization : Similar to the concept of virtual memory, each virtual machine on a host believes that it has exclusive use of the entire physical address space, so it is necessary to abstract the memory again, that is, memory virtualization, to ensure that each virtual machine has an independent address space. In this way, there are concepts of VA and PA in both virtual machines and physical machines, namely GVA (Guest Virtual Address) and GPA (Guest Physical Address), as well as HVA (Host Virtual Address) and HPA (Host Physical Address). The program in the virtual machine uses GVA, which eventually needs to be converted into HPA. The mapping of the two VAs to PAs (GVA to GPA and HVA to HPA) is also managed using page tables. GPA to HVA is generally a continuous linear mapping of several segments, which is managed by the virtual machine's hypervisor VMM (Virtual Machine Monitor).

Process memory access needs to be converted from VA to PA. After the introduction of memory virtualization, the conversion path has changed greatly. Originally, it was only necessary to convert VA to PA. After virtualization, the conversion process becomes GVA -> GPA -> HVA -> HPA . As the path becomes longer and more complex, it brings challenges to the security and performance of memory access. These two points are also the goals that memory virtualization needs to achieve: 1) Security, that is, the legality of address conversion, the virtual machine cannot access memory that does not belong to it; 2) Performance, that is, the efficiency of address conversion, including low overhead in establishing the conversion relationship and low overhead in the conversion process itself.

Classic Solution

To achieve the goal of memory virtualization, many virtualization solutions have been proposed. SPT (Shadow Page Table) and EPT (Extended Page Table) are two typical solutions, and they are also the most familiar solutions. Let's take these as a starting point to see how they work, and then discuss other virtualization solutions.

SPT : Since the original hardware only supports one layer of page table translation, directly converting VA to PA on a virtual machine or physical machine cannot complete the conversion of GVA to HPA. Therefore, SPT established a shortcut, namely the shadow page table, to directly manage the mapping of GVA to HPA, as shown in the following figure. Each shadow page table instance corresponds to a process in the virtual machine, and the establishment of the shadow page table requires the VMM to query the page table of the process in the virtual machine.

Since the shadow page table manages the direct mapping from GVA to HPA, the SPT address translation path is equivalent to the physical machine path, and the address translation can be completed by directly querying one level of page table. When using a 4-level page table, the translation process is shown in the figure below.

Advantages: The SPT address translation process has low overhead, comparable to that of a physical machine.

Disadvantages:

1) The establishment of address translation relationships is very expensive. To ensure the legitimacy of address translation, all the establishment of translation relationships, that is, the modification of the page table of the virtual machine process, will be intercepted and then trapped into the privileged VMM for execution;

2) The shadow page table itself requires memory, and one shadow page table only corresponds to one process in the virtual machine, so it will occupy more memory resources as a whole.

EPT: Later hardware added support for nested page tables for virtualization, allowing the hardware to automatically complete the two-layer page table conversion. EPT is a solution based on hardware support. On the basis of managing the virtual machine page table from GVA to GPA, an extended page table is added to manage the mapping from GPA to HPA, as shown in the following figure. The two layers of page tables are independent of each other, and the conversion of the two layers of mapping relationships is automatically completed by the hardware.

Since the contents of each level of page table (gL4, gL3, gL2, gL1) in the virtual machine are only GPA, when querying the next level, it must first be converted to HPA through the extended page table (nL4, nL3, nL2, nL1), making the entire conversion path very long. When both levels of page tables are 4, the conversion process is shown in the following figure.

Advantages: The overhead of establishing the address translation relationship is low. The existence of an independent EPT page table ensures the legitimacy of the address translation. Therefore, the page table of the virtual machine can be modified by itself without the intervention of the VMM.

Disadvantages: The conversion process is very expensive, requiring 24 (4 + 4 + 4 * 4) hardware table lookup conversions in the worst case.

Both classic solutions have solid security guarantees, but each has its own performance flaws. SPT pays a high price when establishing the conversion relationship to ensure the legitimacy of address conversion, while EPT eliminates the overhead of establishing the conversion relationship but the conversion path is longer.

Other Explorations

There is still a lot of exploration in the industry and academia about memory virtualization. The basic idea is similar to SPT or EPT, which can be divided into three categories:

1) One-layer page table scheme. Similar to SPT, one-layer page table is used to directly manage the mapping from GVA to HPA;

2) Two-layer page table scheme. Similar to EPT, two layers of independent page tables are used to manage the mapping from GVA to GPA and from GPA to HPA respectively;

3) Hybrid solution: Combine the first two solutions and make dynamic selections.

Direct Paging: A one-layer page table solution, which is a paravirtualization solution of Xen when the early hardware only supports one layer of page table. Compared with SPT, the biggest difference is that there is no separate maintenance of the virtual machine page table from GVA to GPA. The virtual machine knows that it is in a virtualized environment, that is, it knows that the content of its page table is HPA. The virtual machine also needs to trap out when modifying the page table, but it uses an active trapping method, which can be batched, while SPT is a passive interception trap; when reading the page table, only HPA can be obtained, and an M2P (Machine to Physical) table needs to be checked to get GPA.

Direct Paging also uses a layer of page table to manage the GVA to HPA mapping, and the address translation path is the same as SPT. When using a 4-level page table, only 4 table lookups are required at worst.

Advantages: The address translation process has low overhead, comparable to that of a physical machine.

Disadvantages:

1) The establishment of address translation relationships is very expensive, and all page table modifications require active trapping;

2) The virtual machine needs to be adapted for paravirtualization. The virtual machine needs to be aware that its page table manages the mapping from GVA to HPA.

Direct Segment: A two-layer page table solution, which is a solution proposed by the academic community based on new hardware. The mapping management from GVA to GPA is the same as that of EPT, and also uses a multi-level page table. However, the mapping from GPA to HPA uses a segmentation mechanism, and when converting GPA to HPA, only an offset needs to be added through hardware.

Although GPA is not equal to HPA, the mapping relationship between the two is very simple. Only an offset is required for the Direct Segment hardware. The entire conversion path is very different from the path of the physical machine, with only a few more hardware offsets. When the virtual machine uses a 4-level page table, the conversion path is shown in the following figure, where DS indicates hardware support for GPA to HPA conversion.

Advantages: The overhead of establishing the address translation relationship is low, and the overhead of the translation process is also low.

Disadvantages:

1) Hardware support for GPA to HPA segment mapping is required, and existing hardware does not have such a function;

2) Large continuous memory segments need to be allocated, that is, the host cannot have too much memory fragmentation.

Flat EPT: A two-layer page table solution, which is also a solution proposed by the academic community based on new hardware. It is very similar to EPT in general, with the only difference being that EPT uses a multi-level page table to manage GPA to HPA, usually 4 levels with 512 entries per level, while Flat EPT uses a flat page table with only one level, with far more than 512 entries.

Similar to EPT, the contents of each level of page table in the virtual machine are also GPA. When querying the next level, it needs to be converted to HPA through the flat extended page table (nL4). Since the flat extended page table has only one level, the conversion path is much shorter than that of EPT. When using a 4-level page table in the virtual machine, the conversion path is shown in the figure below. The worst case requires only 9 (4 + 1 + 4 * 1) table lookups.

Advantages: The overhead of establishing the address translation relationship is low, and the overhead of the translation process is also low. Compared with Direct Segment, it has very low requirements for memory allocation, and only a small amount of continuous memory is needed for the flat extended page table (an 8G virtual machine only needs 16M).

Disadvantages: Hardware support for flat extended page tables is required. Current hardware only supports multi-level extended page tables with 512 entries.

Mix SPT and EPT: This is a mixed solution proposed earlier by the academic community. In simple terms, it is a dynamic time-sharing switch between SPT and EPT. When the virtual machine is running, it monitors and collects TLB miss and Page Fault data, and switches between SPT and EPT when the two reach the set threshold, as shown in the following figure:

When the TLB miss rate is higher than threshold T1 and the Page Fault frequency is lower than threshold T2, switch from EPT to SPT
When the TLB miss rate is lower than threshold T1 and the Page Fault frequency is higher than threshold T2, switch from SPT to EPT

Advantages: There is an opportunity to take full advantage of the advantages of SPT and EPT to achieve better performance.

Disadvantages:

1) It is difficult to set the page table switching threshold, and the hardware configuration may affect the threshold;

2) The switch between SPT and EPT also has a cost, mainly the destruction and reconstruction of SPT.

Summarize

The significant advantage of a one-layer page table is that the address translation process has low overhead, which is the same as that of a physical machine. The problem that needs to be solved is to reduce the overhead of establishing address translation. One possible direction is to give up some security and make page table modifications lighter; another more practical direction is to use it in appropriate scenarios, that is, for loads that do not modify page tables frequently.

The advantage of two-layer page tables is that the overhead of address translation is small, and the virtual machine can modify the page table independently. The problem that needs to be considered is to shorten the translation path. This direction is actually very feasible, but it depends on the support of new hardware, and it is unlikely that new hardware that meets the requirements will appear in the short term.

The original intention of designing hybrid page tables is to make full use of the advantages of the two types of page tables, but it is very difficult to do a good job of dynamic mode switching. Differences in load and even hardware may affect the effect of switching. Perhaps targeted tuning for known loads is a feasible direction.

In the long run, if there is new hardware support, two-layer page tables (especially Flat EPT) is a more complete solution. Address translation can be very efficient and there is no need to sacrifice security and versatility. However, in the short term, it is too early for new hardware. Further exploration and optimization on the one-layer page table solution is more practical. We will continue to explore more possibilities in the path of memory virtualization. Welcome to join the OpenAnolis community for discussion and exchange.