1The x86 kvm shadow mmu 2====================== 3 4The mmu (in arch/x86/kvm, files mmu.[ch] and paging_tmpl.h) is responsible 5for presenting a standard x86 mmu to the guest, while translating guest 6physical addresses to host physical addresses. 7 8The 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- reliability: avoid multipage or GFP_ATOMIC allocations 27 28Acronyms 29======== 30 31pfn host page frame number 32hpa host physical address 33hva host virtual address 34gfn guest frame number 35gpa guest physical address 36gva guest virtual address 37ngpa nested guest physical address 38ngva nested guest virtual address 39pte page table entry (used also to refer generically to paging structure 40 entries) 41gpte guest pte (referring to gfns) 42spte shadow pte (referring to pfns) 43tdp two dimensional paging (vendor neutral term for NPT and EPT) 44 45Virtual and real hardware supported 46=================================== 47 48The mmu supports first-generation mmu hardware, which allows an atomic switch 49of the current paging mode and cr3 during guest entry, as well as 50two-dimensional paging (AMD's NPT and Intel's EPT). The emulated hardware 51it exposes is the traditional 2/3/4 level x86 mmu, with support for global 52pages, pae, pse, pse36, cr0.wp, and 1GB pages. Emulated hardware also 53able to expose NPT capable hardware on NPT capable hosts. 54 55Translation 56=========== 57 58The primary job of the mmu is to program the processor's mmu to translate 59addresses for the guest. Different translations are required at different 60times: 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 70The primary challenge is to encode between 1 and 3 translations into hardware 71that support only 1 (traditional) and 2 (tdp) translations. When the 72number of required translations matches the hardware, the mmu operates in 73direct mode; otherwise it operates in shadow mode (see below). 74 75Memory 76====== 77 78Guest memory (gpa) is part of the user address space of the process that is 79using kvm. Userspace defines the translation between guest addresses and user 80addresses (gpa->hva); note that two gpas may alias to the same hva, but not 81vice versa. 82 83These hvas may be backed using any method available to the host: anonymous 84memory, file backed memory, and device memory. Memory might be paged by the 85host at any time. 86 87Events 88====== 89 90The mmu is driven by events, some from the guest, some from the host. 91 92Guest generated events: 93- writes to control registers (especially cr3) 94- invlpg/invlpga instruction execution 95- access to missing or protected translations 96 97Host 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 102Shadow pages 103============ 104 105The principal data structure is the shadow page, 'struct kvm_mmu_page'. A 106shadow page contains 512 sptes, which can be either leaf or nonleaf sptes. A 107shadow page may contain a mix of leaf and nonleaf sptes. 108 109A nonleaf spte allows the hardware mmu to reach the leaf pages and 110is not related to a translation directly. It points to other shadow pages. 111 112A leaf spte corresponds to either one or two translations encoded into 113one paging structure entry. These are always the lowest level of the 114translation stack, with optional higher level translations left to NPT/EPT. 115Leaf ptes point at guest pages. 116 117The following table shows translations encoded by leaf ptes, with higher-level 118translations 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 131Shadow 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.gpte_is_8_bytes=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 from the parent ptes in the form uwx. 156 Note execute 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.gpte_is_8_bytes: 162 Reflects the size of the guest PTE for which the page is valid, i.e. '1' 163 if 64-bit gptes are in use, '0' if 32-bit gptes are in use. 164 role.nxe: 165 Contains the value of efer.nxe for which the page is valid. 166 role.cr0_wp: 167 Contains the value of cr0.wp for which the page is valid. 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). 172 role.smap_andnot_wp: 173 Contains the value of cr4.smap && !cr0.wp for which the page is valid 174 (pages for which this is true are different from other pages; see the 175 treatment of cr0.wp=0 below). 176 role.ept_sp: 177 This is a virtual flag to denote a shadowed nested EPT page. ept_sp 178 is true if "cr0_wp && smap_andnot_wp", an otherwise invalid combination. 179 role.smm: 180 Is 1 if the page is valid in system management mode. This field 181 determines which of the kvm_memslots array was used to build this 182 shadow page; it is also used to go back from a struct kvm_mmu_page 183 to a memslot, through the kvm_memslots_for_spte_role macro and 184 __gfn_to_memslot. 185 role.ad_disabled: 186 Is 1 if the MMU instance cannot use A/D bits. EPT did not have A/D 187 bits before Haswell; shadow EPT page tables also cannot use A/D bits 188 if the L1 hypervisor does not enable them. 189 gfn: 190 Either the guest page table containing the translations shadowed by this 191 page, or the base page frame for linear translations. See role.direct. 192 spt: 193 A pageful of 64-bit sptes containing the translations for this page. 194 Accessed by both kvm and hardware. 195 The page pointed to by spt will have its page->private pointing back 196 at the shadow page structure. 197 sptes in spt point either at guest pages, or at lower-level shadow pages. 198 Specifically, if sp1 and sp2 are shadow pages, then sp1->spt[n] may point 199 at __pa(sp2->spt). sp2 will point back at sp1 through parent_pte. 200 The spt array forms a DAG structure with the shadow page as a node, and 201 guest pages as leaves. 202 gfns: 203 An array of 512 guest frame numbers, one for each present pte. Used to 204 perform a reverse map from a pte to a gfn. When role.direct is set, any 205 element of this array can be calculated from the gfn field when used, in 206 this case, the array of gfns is not allocated. See role.direct and gfn. 207 root_count: 208 A counter keeping track of how many hardware registers (guest cr3 or 209 pdptrs) are now pointing at the page. While this counter is nonzero, the 210 page cannot be destroyed. See role.invalid. 211 parent_ptes: 212 The reverse mapping for the pte/ptes pointing at this page's spt. If 213 parent_ptes bit 0 is zero, only one spte points at this page and 214 parent_ptes points at this single spte, otherwise, there exists multiple 215 sptes pointing at this page and (parent_ptes & ~0x1) points at a data 216 structure with a list of parent sptes. 217 unsync: 218 If true, then the translations in this page may not match the guest's 219 translation. This is equivalent to the state of the tlb when a pte is 220 changed but before the tlb entry is flushed. Accordingly, unsync ptes 221 are synchronized when the guest executes invlpg or flushes its tlb by 222 other means. Valid for leaf pages. 223 unsync_children: 224 How many sptes in the page point at pages that are unsync (or have 225 unsynchronized children). 226 unsync_child_bitmap: 227 A bitmap indicating which sptes in spt point (directly or indirectly) at 228 pages that may be unsynchronized. Used to quickly locate all unsychronized 229 pages reachable from a given page. 230 clear_spte_count: 231 Only present on 32-bit hosts, where a 64-bit spte cannot be written 232 atomically. The reader uses this while running out of the MMU lock 233 to detect in-progress updates and retry them until the writer has 234 finished the write. 235 write_flooding_count: 236 A guest may write to a page table many times, causing a lot of 237 emulations if the page needs to be write-protected (see "Synchronized 238 and unsynchronized pages" below). Leaf pages can be unsynchronized 239 so that they do not trigger frequent emulation, but this is not 240 possible for non-leafs. This field counts the number of emulations 241 since the last time the page table was actually used; if emulation 242 is triggered too frequently on this page, KVM will unmap the page 243 to avoid emulation in the future. 244 245Reverse map 246=========== 247 248The mmu maintains a reverse mapping whereby all ptes mapping a page can be 249reached given its gfn. This is used, for example, when swapping out a page. 250 251Synchronized and unsynchronized pages 252===================================== 253 254The guest uses two events to synchronize its tlb and page tables: tlb flushes 255and page invalidations (invlpg). 256 257A tlb flush means that we need to synchronize all sptes reachable from the 258guest's cr3. This is expensive, so we keep all guest page tables write 259protected, and synchronize sptes to gptes when a gpte is written. 260 261A special case is when a guest page table is reachable from the current 262guest cr3. In this case, the guest is obliged to issue an invlpg instruction 263before using the translation. We take advantage of that by removing write 264protection from the guest page, and allowing the guest to modify it freely. 265We synchronize modified gptes when the guest invokes invlpg. This reduces 266the amount of emulation we have to do when the guest modifies multiple gptes, 267or when the a guest page is no longer used as a page table and is used for 268random guest data. 269 270As a side effect we have to resynchronize all reachable unsynchronized shadow 271pages on a tlb flush. 272 273 274Reaction to events 275================== 276 277- guest page fault (or npt page fault, or ept violation) 278 279This is the most complicated event. The cause of a page fault can be: 280 281 - a true guest fault (the guest translation won't allow the access) (*) 282 - access to a missing translation 283 - access to a protected translation 284 - when logging dirty pages, memory is write protected 285 - synchronized shadow pages are write protected (*) 286 - access to untranslatable memory (mmio) 287 288 (*) not applicable in direct mode 289 290Handling a page fault is performed as follows: 291 292 - if the RSV bit of the error code is set, the page fault is caused by guest 293 accessing MMIO and cached MMIO information is available. 294 - walk shadow page table 295 - check for valid generation number in the spte (see "Fast invalidation of 296 MMIO sptes" below) 297 - cache the information to vcpu->arch.mmio_gva, vcpu->arch.mmio_access and 298 vcpu->arch.mmio_gfn, and call the emulator 299 - If both P bit and R/W bit of error code are set, this could possibly 300 be handled as a "fast page fault" (fixed without taking the MMU lock). See 301 the description in Documentation/virt/kvm/locking.txt. 302 - if needed, walk the guest page tables to determine the guest translation 303 (gva->gpa or ngpa->gpa) 304 - if permissions are insufficient, reflect the fault back to the guest 305 - determine the host page 306 - if this is an mmio request, there is no host page; cache the info to 307 vcpu->arch.mmio_gva, vcpu->arch.mmio_access and vcpu->arch.mmio_gfn 308 - walk the shadow page table to find the spte for the translation, 309 instantiating missing intermediate page tables as necessary 310 - If this is an mmio request, cache the mmio info to the spte and set some 311 reserved bit on the spte (see callers of kvm_mmu_set_mmio_spte_mask) 312 - try to unsynchronize the page 313 - if successful, we can let the guest continue and modify the gpte 314 - emulate the instruction 315 - if failed, unshadow the page and let the guest continue 316 - update any translations that were modified by the instruction 317 318invlpg handling: 319 320 - walk the shadow page hierarchy and drop affected translations 321 - try to reinstantiate the indicated translation in the hope that the 322 guest will use it in the near future 323 324Guest control register updates: 325 326- mov to cr3 327 - look up new shadow roots 328 - synchronize newly reachable shadow pages 329 330- mov to cr0/cr4/efer 331 - set up mmu context for new paging mode 332 - look up new shadow roots 333 - synchronize newly reachable shadow pages 334 335Host translation updates: 336 337 - mmu notifier called with updated hva 338 - look up affected sptes through reverse map 339 - drop (or update) translations 340 341Emulating cr0.wp 342================ 343 344If tdp is not enabled, the host must keep cr0.wp=1 so page write protection 345works for the guest kernel, not guest guest userspace. When the guest 346cr0.wp=1, this does not present a problem. However when the guest cr0.wp=0, 347we cannot map the permissions for gpte.u=1, gpte.w=0 to any spte (the 348semantics require allowing any guest kernel access plus user read access). 349 350We handle this by mapping the permissions to two possible sptes, depending 351on fault type: 352 353- kernel write fault: spte.u=0, spte.w=1 (allows full kernel access, 354 disallows user access) 355- read fault: spte.u=1, spte.w=0 (allows full read access, disallows kernel 356 write access) 357 358(user write faults generate a #PF) 359 360In the first case there are two additional complications: 361- if CR4.SMEP is enabled: since we've turned the page into a kernel page, 362 the kernel may now execute it. We handle this by also setting spte.nx. 363 If we get a user fetch or read fault, we'll change spte.u=1 and 364 spte.nx=gpte.nx back. For this to work, KVM forces EFER.NX to 1 when 365 shadow paging is in use. 366- if CR4.SMAP is disabled: since the page has been changed to a kernel 367 page, it can not be reused when CR4.SMAP is enabled. We set 368 CR4.SMAP && !CR0.WP into shadow page's role to avoid this case. Note, 369 here we do not care the case that CR4.SMAP is enabled since KVM will 370 directly inject #PF to guest due to failed permission check. 371 372To prevent an spte that was converted into a kernel page with cr0.wp=0 373from being written by the kernel after cr0.wp has changed to 1, we make 374the value of cr0.wp part of the page role. This means that an spte created 375with one value of cr0.wp cannot be used when cr0.wp has a different value - 376it will simply be missed by the shadow page lookup code. A similar issue 377exists when an spte created with cr0.wp=0 and cr4.smep=0 is used after 378changing cr4.smep to 1. To avoid this, the value of !cr0.wp && cr4.smep 379is also made a part of the page role. 380 381Large pages 382=========== 383 384The mmu supports all combinations of large and small guest and host pages. 385Supported page sizes include 4k, 2M, 4M, and 1G. 4M pages are treated as 386two separate 2M pages, on both guest and host, since the mmu always uses PAE 387paging. 388 389To instantiate a large spte, four constraints must be satisfied: 390 391- the spte must point to a large host page 392- the guest pte must be a large pte of at least equivalent size (if tdp is 393 enabled, there is no guest pte and this condition is satisfied) 394- if the spte will be writeable, the large page frame may not overlap any 395 write-protected pages 396- the guest page must be wholly contained by a single memory slot 397 398To check the last two conditions, the mmu maintains a ->disallow_lpage set of 399arrays for each memory slot and large page size. Every write protected page 400causes its disallow_lpage to be incremented, thus preventing instantiation of 401a large spte. The frames at the end of an unaligned memory slot have 402artificially inflated ->disallow_lpages so they can never be instantiated. 403 404Fast invalidation of MMIO sptes 405=============================== 406 407As mentioned in "Reaction to events" above, kvm will cache MMIO 408information in leaf sptes. When a new memslot is added or an existing 409memslot is changed, this information may become stale and needs to be 410invalidated. This also needs to hold the MMU lock while walking all 411shadow pages, and is made more scalable with a similar technique. 412 413MMIO sptes have a few spare bits, which are used to store a 414generation number. The global generation number is stored in 415kvm_memslots(kvm)->generation, and increased whenever guest memory info 416changes. 417 418When KVM finds an MMIO spte, it checks the generation number of the spte. 419If the generation number of the spte does not equal the global generation 420number, it will ignore the cached MMIO information and handle the page 421fault through the slow path. 422 423Since only 18 bits are used to store generation-number on mmio spte, all 424pages are zapped when there is an overflow. 425 426Unfortunately, a single memory access might access kvm_memslots(kvm) multiple 427times, the last one happening when the generation number is retrieved and 428stored into the MMIO spte. Thus, the MMIO spte might be created based on 429out-of-date information, but with an up-to-date generation number. 430 431To avoid this, the generation number is incremented again after synchronize_srcu 432returns; thus, bit 63 of kvm_memslots(kvm)->generation set to 1 only during a 433memslot update, while some SRCU readers might be using the old copy. We do not 434want to use an MMIO sptes created with an odd generation number, and we can do 435this without losing a bit in the MMIO spte. The "update in-progress" bit of the 436generation is not stored in MMIO spte, and is so is implicitly zero when the 437generation is extracted out of the spte. If KVM is unlucky and creates an MMIO 438spte while an update is in-progress, the next access to the spte will always be 439a cache miss. For example, a subsequent access during the update window will 440miss due to the in-progress flag diverging, while an access after the update 441window closes will have a higher generation number (as compared to the spte). 442 443 444Further reading 445=============== 446 447- NPT presentation from KVM Forum 2008 448 http://www.linux-kvm.org/images/c/c8/KvmForum2008%24kdf2008_21.pdf 449 450