1The x86 kvm shadow mmu
   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.
   8The mmu code attempts to satisfy the following requirements:
  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
  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)
  45Virtual and real hardware supported
  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.  Work is in progress to support
  53exposing NPT capable hardware on NPT capable hosts.
  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
  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)
  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).
  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.
  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.
  90The mmu is driven by events, some from the guest, some from the host.
  92Guest generated events:
  93- writes to control registers (especially cr3)
  94- invlpg/invlpga instruction execution
  95- access to missing or protected translations
  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)
 102Shadow pages
 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.
 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.
 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.
 117The following table shows translations encoded by leaf ptes, with higher-level
 118translations in parentheses:
 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
 128(*) the guest hypervisor will encode the ngva->gpa translation into its page
 129    tables if npt is not present
 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.
 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  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  gfn:
 173    Either the guest page table containing the translations shadowed by this
 174    page, or the base page frame for linear translations.  See
 175  spt:
 176    A pageful of 64-bit sptes containing the translations for this page.
 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
 187    perform a reverse map from a pte to a gfn. When 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 and gfn.
 190  root_count:
 191    A counter keeping track of how many hardware registers (guest cr3 or
 192    pdptrs) are now pointing at the page.  While this counter is nonzero, the
 193    page cannot be destroyed.  See role.invalid.
 194  parent_ptes:
 195    The reverse mapping for the pte/ptes pointing at this page's spt. If
 196    parent_ptes bit 0 is zero, only one spte points at this pages and
 197    parent_ptes points at this single spte, otherwise, there exists multiple
 198    sptes pointing at this page and (parent_ptes & ~0x1) points at a data
 199    structure with a list of parent_ptes.
 200  unsync:
 201    If true, then the translations in this page may not match the guest's
 202    translation.  This is equivalent to the state of the tlb when a pte is
 203    changed but before the tlb entry is flushed.  Accordingly, unsync ptes
 204    are synchronized when the guest executes invlpg or flushes its tlb by
 205    other means.  Valid for leaf pages.
 206  unsync_children:
 207    How many sptes in the page point at pages that are unsync (or have
 208    unsynchronized children).
 209  unsync_child_bitmap:
 210    A bitmap indicating which sptes in spt point (directly or indirectly) at
 211    pages that may be unsynchronized.  Used to quickly locate all unsychronized
 212    pages reachable from a given page.
 213  mmu_valid_gen:
 214    Generation number of the page.  It is compared with kvm->arch.mmu_valid_gen
 215    during hash table lookup, and used to skip invalidated shadow pages (see
 216    "Zapping all pages" below.)
 217  clear_spte_count:
 218    Only present on 32-bit hosts, where a 64-bit spte cannot be written
 219    atomically.  The reader uses this while running out of the MMU lock
 220    to detect in-progress updates and retry them until the writer has
 221    finished the write.
 222  write_flooding_count:
 223    A guest may write to a page table many times, causing a lot of
 224    emulations if the page needs to be write-protected (see "Synchronized
 225    and unsynchronized pages" below).  Leaf pages can be unsynchronized
 226    so that they do not trigger frequent emulation, but this is not
 227    possible for non-leafs.  This field counts the number of emulations
 228    since the last time the page table was actually used; if emulation
 229    is triggered too frequently on this page, KVM will unmap the page
 230    to avoid emulation in the future.
 232Reverse map
 235The mmu maintains a reverse mapping whereby all ptes mapping a page can be
 236reached given its gfn.  This is used, for example, when swapping out a page.
 238Synchronized and unsynchronized pages
 241The guest uses two events to synchronize its tlb and page tables: tlb flushes
 242and page invalidations (invlpg).
 244A tlb flush means that we need to synchronize all sptes reachable from the
 245guest's cr3.  This is expensive, so we keep all guest page tables write
 246protected, and synchronize sptes to gptes when a gpte is written.
 248A special case is when a guest page table is reachable from the current
 249guest cr3.  In this case, the guest is obliged to issue an invlpg instruction
 250before using the translation.  We take advantage of that by removing write
 251protection from the guest page, and allowing the guest to modify it freely.
 252We synchronize modified gptes when the guest invokes invlpg.  This reduces
 253the amount of emulation we have to do when the guest modifies multiple gptes,
 254or when the a guest page is no longer used as a page table and is used for
 255random guest data.
 257As a side effect we have to resynchronize all reachable unsynchronized shadow
 258pages on a tlb flush.
 261Reaction to events
 264- guest page fault (or npt page fault, or ept violation)
 266This is the most complicated event.  The cause of a page fault can be:
 268  - a true guest fault (the guest translation won't allow the access) (*)
 269  - access to a missing translation
 270  - access to a protected translation
 271    - when logging dirty pages, memory is write protected
 272    - synchronized shadow pages are write protected (*)
 273  - access to untranslatable memory (mmio)
 275  (*) not applicable in direct mode
 277Handling a page fault is performed as follows:
 279 - if the RSV bit of the error code is set, the page fault is caused by guest
 280   accessing MMIO and cached MMIO information is available.
 281   - walk shadow page table
 282   - check for valid generation number in the spte (see "Fast invalidation of
 283     MMIO sptes" below)
 284   - cache the information to vcpu->arch.mmio_gva, vcpu->arch.access and
 285     vcpu->arch.mmio_gfn, and call the emulator
 286 - If both P bit and R/W bit of error code are set, this could possibly
 287   be handled as a "fast page fault" (fixed without taking the MMU lock).  See
 288   the description in Documentation/virtual/kvm/locking.txt.
 289 - if needed, walk the guest page tables to determine the guest translation
 290   (gva->gpa or ngpa->gpa)
 291   - if permissions are insufficient, reflect the fault back to the guest
 292 - determine the host page
 293   - if this is an mmio request, there is no host page; cache the info to
 294     vcpu->arch.mmio_gva, vcpu->arch.access and vcpu->arch.mmio_gfn
 295 - walk the shadow page table to find the spte for the translation,
 296   instantiating missing intermediate page tables as necessary
 297   - If this is an mmio request, cache the mmio info to the spte and set some
 298     reserved bit on the spte (see callers of kvm_mmu_set_mmio_spte_mask)
 299 - try to unsynchronize the page
 300   - if successful, we can let the guest continue and modify the gpte
 301 - emulate the instruction
 302   - if failed, unshadow the page and let the guest continue
 303 - update any translations that were modified by the instruction
 305invlpg handling:
 307  - walk the shadow page hierarchy and drop affected translations
 308  - try to reinstantiate the indicated translation in the hope that the
 309    guest will use it in the near future
 311Guest control register updates:
 313- mov to cr3
 314  - look up new shadow roots
 315  - synchronize newly reachable shadow pages
 317- mov to cr0/cr4/efer
 318  - set up mmu context for new paging mode
 319  - look up new shadow roots
 320  - synchronize newly reachable shadow pages
 322Host translation updates:
 324  - mmu notifier called with updated hva
 325  - look up affected sptes through reverse map
 326  - drop (or update) translations
 328Emulating cr0.wp
 331If tdp is not enabled, the host must keep cr0.wp=1 so page write protection
 332works for the guest kernel, not guest guest userspace.  When the guest
 333cr0.wp=1, this does not present a problem.  However when the guest cr0.wp=0,
 334we cannot map the permissions for gpte.u=1, gpte.w=0 to any spte (the
 335semantics require allowing any guest kernel access plus user read access).
 337We handle this by mapping the permissions to two possible sptes, depending
 338on fault type:
 340- kernel write fault: spte.u=0, spte.w=1 (allows full kernel access,
 341  disallows user access)
 342- read fault: spte.u=1, spte.w=0 (allows full read access, disallows kernel
 343  write access)
 345(user write faults generate a #PF)
 347In the first case there is an additional complication if CR4.SMEP is
 348enabled: since we've turned the page into a kernel page, the kernel may now
 349execute it.  We handle this by also setting spte.nx.  If we get a user
 350fetch or read fault, we'll change spte.u=1 and spte.nx=gpte.nx back.
 352To prevent an spte that was converted into a kernel page with cr0.wp=0
 353from being written by the kernel after cr0.wp has changed to 1, we make
 354the value of cr0.wp part of the page role.  This means that an spte created
 355with one value of cr0.wp cannot be used when cr0.wp has a different value -
 356it will simply be missed by the shadow page lookup code.  A similar issue
 357exists when an spte created with cr0.wp=0 and cr4.smep=0 is used after
 358changing cr4.smep to 1.  To avoid this, the value of !cr0.wp && cr4.smep
 359is also made a part of the page role.
 361Large pages
 364The mmu supports all combinations of large and small guest and host pages.
 365Supported page sizes include 4k, 2M, 4M, and 1G.  4M pages are treated as
 366two separate 2M pages, on both guest and host, since the mmu always uses PAE
 369To instantiate a large spte, four constraints must be satisfied:
 371- the spte must point to a large host page
 372- the guest pte must be a large pte of at least equivalent size (if tdp is
 373  enabled, there is no guest pte and this condition is satisfied)
 374- if the spte will be writeable, the large page frame may not overlap any
 375  write-protected pages
 376- the guest page must be wholly contained by a single memory slot
 378To check the last two conditions, the mmu maintains a ->write_count set of
 379arrays for each memory slot and large page size.  Every write protected page
 380causes its write_count to be incremented, thus preventing instantiation of
 381a large spte.  The frames at the end of an unaligned memory slot have
 382artificially inflated ->write_counts so they can never be instantiated.
 384Zapping all pages (page generation count)
 387For the large memory guests, walking and zapping all pages is really slow
 388(because there are a lot of pages), and also blocks memory accesses of
 389all VCPUs because it needs to hold the MMU lock.
 391To make it be more scalable, kvm maintains a global generation number
 392which is stored in kvm->arch.mmu_valid_gen.  Every shadow page stores
 393the current global generation-number into sp->mmu_valid_gen when it
 394is created.  Pages with a mismatching generation number are "obsolete".
 396When KVM need zap all shadow pages sptes, it just simply increases the global
 397generation-number then reload root shadow pages on all vcpus.  As the VCPUs
 398create new shadow page tables, the old pages are not used because of the
 399mismatching generation number.
 401KVM then walks through all pages and zaps obsolete pages.  While the zap
 402operation needs to take the MMU lock, the lock can be released periodically
 403so that the VCPUs can make progress.
 405Fast invalidation of MMIO sptes
 408As mentioned in "Reaction to events" above, kvm will cache MMIO
 409information in leaf sptes.  When a new memslot is added or an existing
 410memslot is changed, this information may become stale and needs to be
 411invalidated.  This also needs to hold the MMU lock while walking all
 412shadow pages, and is made more scalable with a similar technique.
 414MMIO sptes have a few spare bits, which are used to store a
 415generation number.  The global generation number is stored in
 416kvm_memslots(kvm)->generation, and increased whenever guest memory info
 417changes.  This generation number is distinct from the one described in
 418the previous section.
 420When KVM finds an MMIO spte, it checks the generation number of the spte.
 421If the generation number of the spte does not equal the global generation
 422number, it will ignore the cached MMIO information and handle the page
 423fault through the slow path.
 425Since only 19 bits are used to store generation-number on mmio spte, all
 426pages are zapped when there is an overflow.
 429Further reading
 432- NPT presentation from KVM Forum 2008