Documentation/kvm/mmu.txt

   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
  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
  80 addresses (gpa->hva); note that two gpas may alias to the same hva, but not
  81 vice versa.
  82
  83 These hvas 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
 114 translation stack, with optional higher level translations left to NPT/EPT.
 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).
 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   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:
 172     A pageful of 64-bit sptes containing the translations for this page.
 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
 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.
 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
 242 As a side effect we have to resynchronize all reachable unsynchronized shadow
 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
 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
 320 Large pages
 321 ===========
 322
 323 The mmu supports all combinations of large and small guest and host pages.
 324 Supported page sizes include 4k, 2M, 4M, and 1G.  4M pages are treated as
 325 two separate 2M pages, on both guest and host, since the mmu always uses PAE
 326 paging.
 327
 328 To instantiate a large spte, four constraints must be satisfied:
 329
 330 - the spte must point to a large host page
 331 - the guest pte must be a large pte of at least equivalent size (if tdp is
 332   enabled, there is no guest pte and this condition is satisified)
 333 - if the spte will be writeable, the large page frame may not overlap any
 334   write-protected pages
 335 - the guest page must be wholly contained by a single memory slot
 336
 337 To check the last two conditions, the mmu maintains a ->write_count set of
 338 arrays for each memory slot and large page size.  Every write protected page
 339 causes its write_count to be incremented, thus preventing instantiation of
 340 a large spte.  The frames at the end of an unaligned memory slot have
 341 artificically inflated ->write_counts so they can never be instantiated.
 342
 343 Further reading
 344 ===============
 345
 346 - NPT presentation from KVM Forum 2008
 347   http://www.linux-kvm.org/wiki/images/c/c8/KvmForum2008%24kdf2008_21.pdf
 348