Commit | Line | Data |
---|---|---|
03909187 AK |
1 | The x86 kvm shadow mmu |
2 | ====================== | |
3 | ||
4 | The mmu (in arch/x86/kvm, files mmu.[ch] and paging_tmpl.h) is responsible | |
5 | for presenting a standard x86 mmu to the guest, while translating guest | |
6 | physical addresses to host physical addresses. | |
7 | ||
8 | The mmu code attempts to satisfy the following requirements: | |
9 | ||
10 | - correctness: the guest should not be able to determine that it is running | |
11 | on an emulated mmu except for timing (we attempt to comply | |
12 | with the specification, not emulate the characteristics of | |
13 | a particular implementation such as tlb size) | |
14 | - security: the guest must not be able to touch host memory not assigned | |
15 | to it | |
16 | - performance: minimize the performance penalty imposed by the mmu | |
17 | - scaling: need to scale to large memory and large vcpu guests | |
18 | - hardware: support the full range of x86 virtualization hardware | |
19 | - integration: Linux memory management code must be in control of guest memory | |
20 | so that swapping, page migration, page merging, transparent | |
21 | hugepages, and similar features work without change | |
22 | - dirty tracking: report writes to guest memory to enable live migration | |
23 | and framebuffer-based displays | |
24 | - footprint: keep the amount of pinned kernel memory low (most memory | |
25 | should be shrinkable) | |
26 | - reliablity: avoid multipage or GFP_ATOMIC allocations | |
27 | ||
28 | Acronyms | |
29 | ======== | |
30 | ||
31 | pfn host page frame number | |
32 | hpa host physical address | |
33 | hva host virtual address | |
34 | gfn guest frame number | |
35 | gpa guest physical address | |
36 | gva guest virtual address | |
37 | ngpa nested guest physical address | |
38 | ngva nested guest virtual address | |
39 | pte page table entry (used also to refer generically to paging structure | |
40 | entries) | |
41 | gpte guest pte (referring to gfns) | |
42 | spte shadow pte (referring to pfns) | |
43 | tdp two dimensional paging (vendor neutral term for NPT and EPT) | |
44 | ||
45 | Virtual and real hardware supported | |
46 | =================================== | |
47 | ||
48 | The mmu supports first-generation mmu hardware, which allows an atomic switch | |
49 | of the current paging mode and cr3 during guest entry, as well as | |
50 | two-dimensional paging (AMD's NPT and Intel's EPT). The emulated hardware | |
51 | it exposes is the traditional 2/3/4 level x86 mmu, with support for global | |
52 | pages, pae, pse, pse36, cr0.wp, and 1GB pages. Work is in progress to support | |
53 | exposing NPT capable hardware on NPT capable hosts. | |
54 | ||
55 | Translation | |
56 | =========== | |
57 | ||
58 | The primary job of the mmu is to program the processor's mmu to translate | |
59 | addresses for the guest. Different translations are required at different | |
60 | times: | |
61 | ||
62 | - when guest paging is disabled, we translate guest physical addresses to | |
63 | host physical addresses (gpa->hpa) | |
64 | - when guest paging is enabled, we translate guest virtual addresses, to | |
65 | guest physical addresses, to host physical addresses (gva->gpa->hpa) | |
66 | - when the guest launches a guest of its own, we translate nested guest | |
67 | virtual addresses, to nested guest physical addresses, to guest physical | |
68 | addresses, to host physical addresses (ngva->ngpa->gpa->hpa) | |
69 | ||
70 | The primary challenge is to encode between 1 and 3 translations into hardware | |
71 | that support only 1 (traditional) and 2 (tdp) translations. When the | |
72 | number of required translations matches the hardware, the mmu operates in | |
73 | direct mode; otherwise it operates in shadow mode (see below). | |
74 | ||
75 | Memory | |
76 | ====== | |
77 | ||
c4bd09b2 AK |
78 | Guest memory (gpa) is part of the user address space of the process that is |
79 | using kvm. Userspace defines the translation between guest addresses and user | |
03909187 AK |
80 | addresses (gpa->hva); note that two gpas may alias to the same gva, but not |
81 | vice versa. | |
82 | ||
83 | These gvas may be backed using any method available to the host: anonymous | |
84 | memory, file backed memory, and device memory. Memory might be paged by the | |
85 | host at any time. | |
86 | ||
87 | Events | |
88 | ====== | |
89 | ||
90 | The mmu is driven by events, some from the guest, some from the host. | |
91 | ||
92 | Guest generated events: | |
93 | - writes to control registers (especially cr3) | |
94 | - invlpg/invlpga instruction execution | |
95 | - access to missing or protected translations | |
96 | ||
97 | Host generated events: | |
98 | - changes in the gpa->hpa translation (either through gpa->hva changes or | |
99 | through hva->hpa changes) | |
100 | - memory pressure (the shrinker) | |
101 | ||
102 | Shadow pages | |
103 | ============ | |
104 | ||
105 | The principal data structure is the shadow page, 'struct kvm_mmu_page'. A | |
106 | shadow page contains 512 sptes, which can be either leaf or nonleaf sptes. A | |
107 | shadow page may contain a mix of leaf and nonleaf sptes. | |
108 | ||
109 | A nonleaf spte allows the hardware mmu to reach the leaf pages and | |
110 | is not related to a translation directly. It points to other shadow pages. | |
111 | ||
112 | A leaf spte corresponds to either one or two translations encoded into | |
113 | one paging structure entry. These are always the lowest level of the | |
c4bd09b2 | 114 | translation stack, with optional higher level translations left to NPT/EPT. |
03909187 AK |
115 | Leaf ptes point at guest pages. |
116 | ||
117 | The following table shows translations encoded by leaf ptes, with higher-level | |
118 | translations in parentheses: | |
119 | ||
120 | Non-nested guests: | |
121 | nonpaging: gpa->hpa | |
122 | paging: gva->gpa->hpa | |
123 | paging, tdp: (gva->)gpa->hpa | |
124 | Nested guests: | |
125 | non-tdp: ngva->gpa->hpa (*) | |
126 | tdp: (ngva->)ngpa->gpa->hpa | |
127 | ||
128 | (*) the guest hypervisor will encode the ngva->gpa translation into its page | |
129 | tables if npt is not present | |
130 | ||
131 | Shadow pages contain the following information: | |
132 | role.level: | |
133 | The level in the shadow paging hierarchy that this shadow page belongs to. | |
134 | 1=4k sptes, 2=2M sptes, 3=1G sptes, etc. | |
135 | role.direct: | |
136 | If set, leaf sptes reachable from this page are for a linear range. | |
137 | Examples include real mode translation, large guest pages backed by small | |
138 | host pages, and gpa->hpa translations when NPT or EPT is active. | |
139 | The linear range starts at (gfn << PAGE_SHIFT) and its size is determined | |
140 | by role.level (2MB for first level, 1GB for second level, 0.5TB for third | |
141 | level, 256TB for fourth level) | |
142 | If clear, this page corresponds to a guest page table denoted by the gfn | |
143 | field. | |
144 | role.quadrant: | |
145 | When role.cr4_pae=0, the guest uses 32-bit gptes while the host uses 64-bit | |
146 | sptes. That means a guest page table contains more ptes than the host, | |
147 | so multiple shadow pages are needed to shadow one guest page. | |
148 | For first-level shadow pages, role.quadrant can be 0 or 1 and denotes the | |
149 | first or second 512-gpte block in the guest page table. For second-level | |
150 | page tables, each 32-bit gpte is converted to two 64-bit sptes | |
151 | (since each first-level guest page is shadowed by two first-level | |
152 | shadow pages) so role.quadrant takes values in the range 0..3. Each | |
153 | quadrant maps 1GB virtual address space. | |
154 | role.access: | |
155 | Inherited guest access permissions in the form uwx. Note execute | |
156 | permission is positive, not negative. | |
157 | role.invalid: | |
158 | The page is invalid and should not be used. It is a root page that is | |
159 | currently pinned (by a cpu hardware register pointing to it); once it is | |
160 | unpinned it will be destroyed. | |
161 | role.cr4_pae: | |
162 | Contains the value of cr4.pae for which the page is valid (e.g. whether | |
163 | 32-bit or 64-bit gptes are in use). | |
6859762e | 164 | role.nxe: |
03909187 | 165 | Contains the value of efer.nxe for which the page is valid. |
3dbe1415 AK |
166 | role.cr0_wp: |
167 | Contains the value of cr0.wp for which the page is valid. | |
03909187 AK |
168 | gfn: |
169 | Either the guest page table containing the translations shadowed by this | |
170 | page, or the base page frame for linear translations. See role.direct. | |
171 | spt: | |
c4bd09b2 | 172 | A pageful of 64-bit sptes containing the translations for this page. |
03909187 AK |
173 | Accessed by both kvm and hardware. |
174 | The page pointed to by spt will have its page->private pointing back | |
175 | at the shadow page structure. | |
176 | sptes in spt point either at guest pages, or at lower-level shadow pages. | |
177 | Specifically, if sp1 and sp2 are shadow pages, then sp1->spt[n] may point | |
178 | at __pa(sp2->spt). sp2 will point back at sp1 through parent_pte. | |
179 | The spt array forms a DAG structure with the shadow page as a node, and | |
180 | guest pages as leaves. | |
181 | gfns: | |
182 | An array of 512 guest frame numbers, one for each present pte. Used to | |
2032a93d LJ |
183 | perform a reverse map from a pte to a gfn. When role.direct is set, any |
184 | element of this array can be calculated from the gfn field when used, in | |
185 | this case, the array of gfns is not allocated. See role.direct and gfn. | |
03909187 AK |
186 | slot_bitmap: |
187 | A bitmap containing one bit per memory slot. If the page contains a pte | |
188 | mapping a page from memory slot n, then bit n of slot_bitmap will be set | |
189 | (if a page is aliased among several slots, then it is not guaranteed that | |
190 | all slots will be marked). | |
191 | Used during dirty logging to avoid scanning a shadow page if none if its | |
192 | pages need tracking. | |
193 | root_count: | |
194 | A counter keeping track of how many hardware registers (guest cr3 or | |
195 | pdptrs) are now pointing at the page. While this counter is nonzero, the | |
196 | page cannot be destroyed. See role.invalid. | |
197 | multimapped: | |
198 | Whether there exist multiple sptes pointing at this page. | |
199 | parent_pte/parent_ptes: | |
200 | If multimapped is zero, parent_pte points at the single spte that points at | |
201 | this page's spt. Otherwise, parent_ptes points at a data structure | |
202 | with a list of parent_ptes. | |
203 | unsync: | |
204 | If true, then the translations in this page may not match the guest's | |
205 | translation. This is equivalent to the state of the tlb when a pte is | |
206 | changed but before the tlb entry is flushed. Accordingly, unsync ptes | |
207 | are synchronized when the guest executes invlpg or flushes its tlb by | |
208 | other means. Valid for leaf pages. | |
209 | unsync_children: | |
210 | How many sptes in the page point at pages that are unsync (or have | |
211 | unsynchronized children). | |
212 | unsync_child_bitmap: | |
213 | A bitmap indicating which sptes in spt point (directly or indirectly) at | |
214 | pages that may be unsynchronized. Used to quickly locate all unsychronized | |
215 | pages reachable from a given page. | |
216 | ||
217 | Reverse map | |
218 | =========== | |
219 | ||
220 | The mmu maintains a reverse mapping whereby all ptes mapping a page can be | |
221 | reached given its gfn. This is used, for example, when swapping out a page. | |
222 | ||
223 | Synchronized and unsynchronized pages | |
224 | ===================================== | |
225 | ||
226 | The guest uses two events to synchronize its tlb and page tables: tlb flushes | |
227 | and page invalidations (invlpg). | |
228 | ||
229 | A tlb flush means that we need to synchronize all sptes reachable from the | |
230 | guest's cr3. This is expensive, so we keep all guest page tables write | |
231 | protected, and synchronize sptes to gptes when a gpte is written. | |
232 | ||
233 | A special case is when a guest page table is reachable from the current | |
234 | guest cr3. In this case, the guest is obliged to issue an invlpg instruction | |
235 | before using the translation. We take advantage of that by removing write | |
236 | protection from the guest page, and allowing the guest to modify it freely. | |
237 | We synchronize modified gptes when the guest invokes invlpg. This reduces | |
238 | the amount of emulation we have to do when the guest modifies multiple gptes, | |
239 | or when the a guest page is no longer used as a page table and is used for | |
240 | random guest data. | |
241 | ||
c4bd09b2 | 242 | As a side effect we have to resynchronize all reachable unsynchronized shadow |
03909187 AK |
243 | pages on a tlb flush. |
244 | ||
245 | ||
246 | Reaction to events | |
247 | ================== | |
248 | ||
249 | - guest page fault (or npt page fault, or ept violation) | |
250 | ||
251 | This is the most complicated event. The cause of a page fault can be: | |
252 | ||
253 | - a true guest fault (the guest translation won't allow the access) (*) | |
254 | - access to a missing translation | |
255 | - access to a protected translation | |
256 | - when logging dirty pages, memory is write protected | |
257 | - synchronized shadow pages are write protected (*) | |
258 | - access to untranslatable memory (mmio) | |
259 | ||
260 | (*) not applicable in direct mode | |
261 | ||
262 | Handling a page fault is performed as follows: | |
263 | ||
264 | - if needed, walk the guest page tables to determine the guest translation | |
265 | (gva->gpa or ngpa->gpa) | |
266 | - if permissions are insufficient, reflect the fault back to the guest | |
267 | - determine the host page | |
268 | - if this is an mmio request, there is no host page; call the emulator | |
269 | to emulate the instruction instead | |
270 | - walk the shadow page table to find the spte for the translation, | |
271 | instantiating missing intermediate page tables as necessary | |
272 | - try to unsynchronize the page | |
273 | - if successful, we can let the guest continue and modify the gpte | |
274 | - emulate the instruction | |
275 | - if failed, unshadow the page and let the guest continue | |
276 | - update any translations that were modified by the instruction | |
277 | ||
278 | invlpg handling: | |
279 | ||
280 | - walk the shadow page hierarchy and drop affected translations | |
281 | - try to reinstantiate the indicated translation in the hope that the | |
282 | guest will use it in the near future | |
283 | ||
284 | Guest control register updates: | |
285 | ||
286 | - mov to cr3 | |
287 | - look up new shadow roots | |
288 | - synchronize newly reachable shadow pages | |
289 | ||
290 | - mov to cr0/cr4/efer | |
291 | - set up mmu context for new paging mode | |
292 | - look up new shadow roots | |
293 | - synchronize newly reachable shadow pages | |
294 | ||
295 | Host translation updates: | |
296 | ||
297 | - mmu notifier called with updated hva | |
298 | - look up affected sptes through reverse map | |
299 | - drop (or update) translations | |
300 | ||
ec87fe2a AK |
301 | Emulating cr0.wp |
302 | ================ | |
303 | ||
304 | If tdp is not enabled, the host must keep cr0.wp=1 so page write protection | |
305 | works for the guest kernel, not guest guest userspace. When the guest | |
306 | cr0.wp=1, this does not present a problem. However when the guest cr0.wp=0, | |
307 | we cannot map the permissions for gpte.u=1, gpte.w=0 to any spte (the | |
308 | semantics require allowing any guest kernel access plus user read access). | |
309 | ||
310 | We handle this by mapping the permissions to two possible sptes, depending | |
311 | on fault type: | |
312 | ||
313 | - kernel write fault: spte.u=0, spte.w=1 (allows full kernel access, | |
314 | disallows user access) | |
315 | - read fault: spte.u=1, spte.w=0 (allows full read access, disallows kernel | |
316 | write access) | |
317 | ||
318 | (user write faults generate a #PF) | |
319 | ||
03909187 AK |
320 | Further reading |
321 | =============== | |
322 | ||
323 | - NPT presentation from KVM Forum 2008 | |
324 | http://www.linux-kvm.org/wiki/images/c/c8/KvmForum2008%24kdf2008_21.pdf | |
325 |