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) | |
25985edc | 26 | - reliability: avoid multipage or GFP_ATOMIC allocations |
03909187 AK |
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 | |
21bbe18b | 80 | addresses (gpa->hva); note that two gpas may alias to the same hva, but not |
03909187 AK |
81 | vice versa. |
82 | ||
21bbe18b | 83 | These hvas may be backed using any method available to the host: anonymous |
03909187 AK |
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. | |
411c588d AK |
168 | role.smep_andnot_wp: |
169 | Contains the value of cr4.smep && !cr0.wp for which the page is valid | |
170 | (pages for which this is true are different from other pages; see the | |
171 | treatment of cr0.wp=0 below). | |
03909187 AK |
172 | gfn: |
173 | Either the guest page table containing the translations shadowed by this | |
174 | page, or the base page frame for linear translations. See role.direct. | |
175 | spt: | |
c4bd09b2 | 176 | A pageful of 64-bit sptes containing the translations for this page. |
03909187 AK |
177 | Accessed by both kvm and hardware. |
178 | The page pointed to by spt will have its page->private pointing back | |
179 | at the shadow page structure. | |
180 | sptes in spt point either at guest pages, or at lower-level shadow pages. | |
181 | Specifically, if sp1 and sp2 are shadow pages, then sp1->spt[n] may point | |
182 | at __pa(sp2->spt). sp2 will point back at sp1 through parent_pte. | |
183 | The spt array forms a DAG structure with the shadow page as a node, and | |
184 | guest pages as leaves. | |
185 | gfns: | |
186 | An array of 512 guest frame numbers, one for each present pte. Used to | |
2032a93d LJ |
187 | perform a reverse map from a pte to a gfn. When role.direct is set, any |
188 | element of this array can be calculated from the gfn field when used, in | |
189 | this case, the array of gfns is not allocated. See role.direct and gfn. | |
03909187 AK |
190 | slot_bitmap: |
191 | A bitmap containing one bit per memory slot. If the page contains a pte | |
192 | mapping a page from memory slot n, then bit n of slot_bitmap will be set | |
193 | (if a page is aliased among several slots, then it is not guaranteed that | |
194 | all slots will be marked). | |
195 | Used during dirty logging to avoid scanning a shadow page if none if its | |
196 | pages need tracking. | |
197 | root_count: | |
198 | A counter keeping track of how many hardware registers (guest cr3 or | |
199 | pdptrs) are now pointing at the page. While this counter is nonzero, the | |
200 | page cannot be destroyed. See role.invalid. | |
201 | multimapped: | |
202 | Whether there exist multiple sptes pointing at this page. | |
203 | parent_pte/parent_ptes: | |
204 | If multimapped is zero, parent_pte points at the single spte that points at | |
205 | this page's spt. Otherwise, parent_ptes points at a data structure | |
206 | with a list of parent_ptes. | |
207 | unsync: | |
208 | If true, then the translations in this page may not match the guest's | |
209 | translation. This is equivalent to the state of the tlb when a pte is | |
210 | changed but before the tlb entry is flushed. Accordingly, unsync ptes | |
211 | are synchronized when the guest executes invlpg or flushes its tlb by | |
212 | other means. Valid for leaf pages. | |
213 | unsync_children: | |
214 | How many sptes in the page point at pages that are unsync (or have | |
215 | unsynchronized children). | |
216 | unsync_child_bitmap: | |
217 | A bitmap indicating which sptes in spt point (directly or indirectly) at | |
218 | pages that may be unsynchronized. Used to quickly locate all unsychronized | |
219 | pages reachable from a given page. | |
220 | ||
221 | Reverse map | |
222 | =========== | |
223 | ||
224 | The mmu maintains a reverse mapping whereby all ptes mapping a page can be | |
225 | reached given its gfn. This is used, for example, when swapping out a page. | |
226 | ||
227 | Synchronized and unsynchronized pages | |
228 | ===================================== | |
229 | ||
230 | The guest uses two events to synchronize its tlb and page tables: tlb flushes | |
231 | and page invalidations (invlpg). | |
232 | ||
233 | A tlb flush means that we need to synchronize all sptes reachable from the | |
234 | guest's cr3. This is expensive, so we keep all guest page tables write | |
235 | protected, and synchronize sptes to gptes when a gpte is written. | |
236 | ||
237 | A special case is when a guest page table is reachable from the current | |
238 | guest cr3. In this case, the guest is obliged to issue an invlpg instruction | |
239 | before using the translation. We take advantage of that by removing write | |
240 | protection from the guest page, and allowing the guest to modify it freely. | |
241 | We synchronize modified gptes when the guest invokes invlpg. This reduces | |
242 | the amount of emulation we have to do when the guest modifies multiple gptes, | |
243 | or when the a guest page is no longer used as a page table and is used for | |
244 | random guest data. | |
245 | ||
c4bd09b2 | 246 | As a side effect we have to resynchronize all reachable unsynchronized shadow |
03909187 AK |
247 | pages on a tlb flush. |
248 | ||
249 | ||
250 | Reaction to events | |
251 | ================== | |
252 | ||
253 | - guest page fault (or npt page fault, or ept violation) | |
254 | ||
255 | This is the most complicated event. The cause of a page fault can be: | |
256 | ||
257 | - a true guest fault (the guest translation won't allow the access) (*) | |
258 | - access to a missing translation | |
259 | - access to a protected translation | |
260 | - when logging dirty pages, memory is write protected | |
261 | - synchronized shadow pages are write protected (*) | |
262 | - access to untranslatable memory (mmio) | |
263 | ||
264 | (*) not applicable in direct mode | |
265 | ||
266 | Handling a page fault is performed as follows: | |
267 | ||
268 | - if needed, walk the guest page tables to determine the guest translation | |
269 | (gva->gpa or ngpa->gpa) | |
270 | - if permissions are insufficient, reflect the fault back to the guest | |
271 | - determine the host page | |
272 | - if this is an mmio request, there is no host page; call the emulator | |
273 | to emulate the instruction instead | |
274 | - walk the shadow page table to find the spte for the translation, | |
275 | instantiating missing intermediate page tables as necessary | |
276 | - try to unsynchronize the page | |
277 | - if successful, we can let the guest continue and modify the gpte | |
278 | - emulate the instruction | |
279 | - if failed, unshadow the page and let the guest continue | |
280 | - update any translations that were modified by the instruction | |
281 | ||
282 | invlpg handling: | |
283 | ||
284 | - walk the shadow page hierarchy and drop affected translations | |
285 | - try to reinstantiate the indicated translation in the hope that the | |
286 | guest will use it in the near future | |
287 | ||
288 | Guest control register updates: | |
289 | ||
290 | - mov to cr3 | |
291 | - look up new shadow roots | |
292 | - synchronize newly reachable shadow pages | |
293 | ||
294 | - mov to cr0/cr4/efer | |
295 | - set up mmu context for new paging mode | |
296 | - look up new shadow roots | |
297 | - synchronize newly reachable shadow pages | |
298 | ||
299 | Host translation updates: | |
300 | ||
301 | - mmu notifier called with updated hva | |
302 | - look up affected sptes through reverse map | |
303 | - drop (or update) translations | |
304 | ||
ec87fe2a AK |
305 | Emulating cr0.wp |
306 | ================ | |
307 | ||
308 | If tdp is not enabled, the host must keep cr0.wp=1 so page write protection | |
309 | works for the guest kernel, not guest guest userspace. When the guest | |
310 | cr0.wp=1, this does not present a problem. However when the guest cr0.wp=0, | |
311 | we cannot map the permissions for gpte.u=1, gpte.w=0 to any spte (the | |
312 | semantics require allowing any guest kernel access plus user read access). | |
313 | ||
314 | We handle this by mapping the permissions to two possible sptes, depending | |
315 | on fault type: | |
316 | ||
317 | - kernel write fault: spte.u=0, spte.w=1 (allows full kernel access, | |
318 | disallows user access) | |
319 | - read fault: spte.u=1, spte.w=0 (allows full read access, disallows kernel | |
320 | write access) | |
321 | ||
322 | (user write faults generate a #PF) | |
323 | ||
411c588d AK |
324 | In the first case there is an additional complication if CR4.SMEP is |
325 | enabled: since we've turned the page into a kernel page, the kernel may now | |
326 | execute it. We handle this by also setting spte.nx. If we get a user | |
327 | fetch or read fault, we'll change spte.u=1 and spte.nx=gpte.nx back. | |
328 | ||
329 | To prevent an spte that was converted into a kernel page with cr0.wp=0 | |
330 | from being written by the kernel after cr0.wp has changed to 1, we make | |
331 | the value of cr0.wp part of the page role. This means that an spte created | |
332 | with one value of cr0.wp cannot be used when cr0.wp has a different value - | |
333 | it will simply be missed by the shadow page lookup code. A similar issue | |
334 | exists when an spte created with cr0.wp=0 and cr4.smep=0 is used after | |
335 | changing cr4.smep to 1. To avoid this, the value of !cr0.wp && cr4.smep | |
336 | is also made a part of the page role. | |
337 | ||
316b9521 AK |
338 | Large pages |
339 | =========== | |
340 | ||
341 | The mmu supports all combinations of large and small guest and host pages. | |
342 | Supported page sizes include 4k, 2M, 4M, and 1G. 4M pages are treated as | |
343 | two separate 2M pages, on both guest and host, since the mmu always uses PAE | |
344 | paging. | |
345 | ||
346 | To instantiate a large spte, four constraints must be satisfied: | |
347 | ||
348 | - the spte must point to a large host page | |
349 | - the guest pte must be a large pte of at least equivalent size (if tdp is | |
350 | enabled, there is no guest pte and this condition is satisified) | |
351 | - if the spte will be writeable, the large page frame may not overlap any | |
352 | write-protected pages | |
353 | - the guest page must be wholly contained by a single memory slot | |
354 | ||
355 | To check the last two conditions, the mmu maintains a ->write_count set of | |
356 | arrays for each memory slot and large page size. Every write protected page | |
357 | causes its write_count to be incremented, thus preventing instantiation of | |
358 | a large spte. The frames at the end of an unaligned memory slot have | |
359 | artificically inflated ->write_counts so they can never be instantiated. | |
360 | ||
03909187 AK |
361 | Further reading |
362 | =============== | |
363 | ||
364 | - NPT presentation from KVM Forum 2008 | |
365 | http://www.linux-kvm.org/wiki/images/c/c8/KvmForum2008%24kdf2008_21.pdf | |
366 |