Avi Kivity | 0390918 | 2010-04-21 16:08:20 +0300 | [diff] [blame] | 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) |
Lucas De Marchi | 25985ed | 2011-03-30 22:57:33 -0300 | [diff] [blame] | 26 | - reliability: avoid multipage or GFP_ATOMIC allocations |
Avi Kivity | 0390918 | 2010-04-21 16:08:20 +0300 | [diff] [blame] | 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 | |
Avi Kivity | c4bd09b | 2010-04-26 11:59:21 +0300 | [diff] [blame] | 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 |
Jason Wang | 21bbe18 | 2010-06-17 16:49:22 +0800 | [diff] [blame] | 80 | addresses (gpa->hva); note that two gpas may alias to the same hva, but not |
Avi Kivity | 0390918 | 2010-04-21 16:08:20 +0300 | [diff] [blame] | 81 | vice versa. |
| 82 | |
Jason Wang | 21bbe18 | 2010-06-17 16:49:22 +0800 | [diff] [blame] | 83 | These hvas may be backed using any method available to the host: anonymous |
Avi Kivity | 0390918 | 2010-04-21 16:08:20 +0300 | [diff] [blame] | 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 |
Avi Kivity | c4bd09b | 2010-04-26 11:59:21 +0300 | [diff] [blame] | 114 | translation stack, with optional higher level translations left to NPT/EPT. |
Avi Kivity | 0390918 | 2010-04-21 16:08:20 +0300 | [diff] [blame] | 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). |
Gui Jianfeng | 6859762 | 2010-05-11 14:36:58 +0800 | [diff] [blame] | 164 | role.nxe: |
Avi Kivity | 0390918 | 2010-04-21 16:08:20 +0300 | [diff] [blame] | 165 | Contains the value of efer.nxe for which the page is valid. |
Avi Kivity | 3dbe141 | 2010-05-12 11:48:18 +0300 | [diff] [blame] | 166 | role.cr0_wp: |
| 167 | Contains the value of cr0.wp for which the page is valid. |
Avi Kivity | 411c588 | 2011-06-06 16:11:54 +0300 | [diff] [blame] | 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). |
Avi Kivity | 0390918 | 2010-04-21 16:08:20 +0300 | [diff] [blame] | 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: |
Avi Kivity | c4bd09b | 2010-04-26 11:59:21 +0300 | [diff] [blame] | 176 | A pageful of 64-bit sptes containing the translations for this page. |
Avi Kivity | 0390918 | 2010-04-21 16:08:20 +0300 | [diff] [blame] | 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 |
Lai Jiangshan | 2032a93 | 2010-05-26 16:49:59 +0800 | [diff] [blame] | 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. |
Avi Kivity | 0390918 | 2010-04-21 16:08:20 +0300 | [diff] [blame] | 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 | |
Avi Kivity | c4bd09b | 2010-04-26 11:59:21 +0300 | [diff] [blame] | 246 | As a side effect we have to resynchronize all reachable unsynchronized shadow |
Avi Kivity | 0390918 | 2010-04-21 16:08:20 +0300 | [diff] [blame] | 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 | |
Avi Kivity | ec87fe2 | 2010-05-27 14:46:04 +0300 | [diff] [blame] | 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 | |
Avi Kivity | 411c588 | 2011-06-06 16:11:54 +0300 | [diff] [blame] | 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 | |
Avi Kivity | 316b952 | 2010-05-27 16:44:12 +0300 | [diff] [blame] | 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 | |
Avi Kivity | 0390918 | 2010-04-21 16:08:20 +0300 | [diff] [blame] | 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 | |