The x86 kvm shadow mmu
  ======================
  
  The mmu (in arch/x86/kvm, files mmu.[ch] and paging_tmpl.h) is responsible
  for presenting a standard x86 mmu to the guest, while translating guest
  physical addresses to host physical addresses.
  
  The mmu code attempts to satisfy the following requirements:
  
  - correctness: the guest should not be able to determine that it is running
                 on an emulated mmu except for timing (we attempt to comply
                 with the specification, not emulate the characteristics of
                 a particular implementation such as tlb size)
  - security:    the guest must not be able to touch host memory not assigned
                 to it
  - performance: minimize the performance penalty imposed by the mmu
  - scaling:     need to scale to large memory and large vcpu guests
  - hardware:    support the full range of x86 virtualization hardware
  - integration: Linux memory management code must be in control of guest memory
                 so that swapping, page migration, page merging, transparent
                 hugepages, and similar features work without change
  - dirty tracking: report writes to guest memory to enable live migration
                 and framebuffer-based displays
  - footprint:   keep the amount of pinned kernel memory low (most memory
                 should be shrinkable)
  - reliability:  avoid multipage or GFP_ATOMIC allocations
  
  Acronyms
  ========
  
  pfn   host page frame number
  hpa   host physical address
  hva   host virtual address
  gfn   guest frame number
  gpa   guest physical address
  gva   guest virtual address
  ngpa  nested guest physical address
  ngva  nested guest virtual address
  pte   page table entry (used also to refer generically to paging structure
        entries)
  gpte  guest pte (referring to gfns)
  spte  shadow pte (referring to pfns)
  tdp   two dimensional paging (vendor neutral term for NPT and EPT)
  
  Virtual and real hardware supported
  ===================================
  
  The mmu supports first-generation mmu hardware, which allows an atomic switch
  of the current paging mode and cr3 during guest entry, as well as
  two-dimensional paging (AMD's NPT and Intel's EPT).  The emulated hardware
  it exposes is the traditional 2/3/4 level x86 mmu, with support for global
  pages, pae, pse, pse36, cr0.wp, and 1GB pages.  Work is in progress to support
  exposing NPT capable hardware on NPT capable hosts.
  
  Translation
  ===========
  
  The primary job of the mmu is to program the processor's mmu to translate
  addresses for the guest.  Different translations are required at different
  times:
  
  - when guest paging is disabled, we translate guest physical addresses to
    host physical addresses (gpa->hpa)
  - when guest paging is enabled, we translate guest virtual addresses, to
    guest physical addresses, to host physical addresses (gva->gpa->hpa)
  - when the guest launches a guest of its own, we translate nested guest
    virtual addresses, to nested guest physical addresses, to guest physical
    addresses, to host physical addresses (ngva->ngpa->gpa->hpa)
  
  The primary challenge is to encode between 1 and 3 translations into hardware
  that support only 1 (traditional) and 2 (tdp) translations.  When the
  number of required translations matches the hardware, the mmu operates in
  direct mode; otherwise it operates in shadow mode (see below).
  
  Memory
  ======
  
  Guest memory (gpa) is part of the user address space of the process that is
  using kvm.  Userspace defines the translation between guest addresses and user
  addresses (gpa->hva); note that two gpas may alias to the same hva, but not
  vice versa.
  
  These hvas may be backed using any method available to the host: anonymous
  memory, file backed memory, and device memory.  Memory might be paged by the
  host at any time.
  
  Events
  ======
  
  The mmu is driven by events, some from the guest, some from the host.
  
  Guest generated events:
  - writes to control registers (especially cr3)
  - invlpg/invlpga instruction execution
  - access to missing or protected translations
  
  Host generated events:
  - changes in the gpa->hpa translation (either through gpa->hva changes or
    through hva->hpa changes)
  - memory pressure (the shrinker)
  
  Shadow pages
  ============
  
  The principal data structure is the shadow page, 'struct kvm_mmu_page'.  A
  shadow page contains 512 sptes, which can be either leaf or nonleaf sptes.  A
  shadow page may contain a mix of leaf and nonleaf sptes.
  
  A nonleaf spte allows the hardware mmu to reach the leaf pages and
  is not related to a translation directly.  It points to other shadow pages.
  
  A leaf spte corresponds to either one or two translations encoded into
  one paging structure entry.  These are always the lowest level of the
  translation stack, with optional higher level translations left to NPT/EPT.
  Leaf ptes point at guest pages.
  
  The following table shows translations encoded by leaf ptes, with higher-level
  translations in parentheses:
  
   Non-nested guests:
    nonpaging:     gpa->hpa
    paging:        gva->gpa->hpa
    paging, tdp:   (gva->)gpa->hpa
   Nested guests:
    non-tdp:       ngva->gpa->hpa  (*)
    tdp:           (ngva->)ngpa->gpa->hpa
  
  (*) the guest hypervisor will encode the ngva->gpa translation into its page
      tables if npt is not present
  
  Shadow pages contain the following information:
    role.level:
      The level in the shadow paging hierarchy that this shadow page belongs to.
      1=4k sptes, 2=2M sptes, 3=1G sptes, etc.
    role.direct:
      If set, leaf sptes reachable from this page are for a linear range.
      Examples include real mode translation, large guest pages backed by small
      host pages, and gpa->hpa translations when NPT or EPT is active.
      The linear range starts at (gfn << PAGE_SHIFT) and its size is determined
      by role.level (2MB for first level, 1GB for second level, 0.5TB for third
      level, 256TB for fourth level)
      If clear, this page corresponds to a guest page table denoted by the gfn
      field.
    role.quadrant:
      When role.cr4_pae=0, the guest uses 32-bit gptes while the host uses 64-bit
      sptes.  That means a guest page table contains more ptes than the host,
      so multiple shadow pages are needed to shadow one guest page.
      For first-level shadow pages, role.quadrant can be 0 or 1 and denotes the
      first or second 512-gpte block in the guest page table.  For second-level
      page tables, each 32-bit gpte is converted to two 64-bit sptes
      (since each first-level guest page is shadowed by two first-level
      shadow pages) so role.quadrant takes values in the range 0..3.  Each
      quadrant maps 1GB virtual address space.
    role.access:
      Inherited guest access permissions in the form uwx.  Note execute
      permission is positive, not negative.
    role.invalid:
      The page is invalid and should not be used.  It is a root page that is
      currently pinned (by a cpu hardware register pointing to it); once it is
      unpinned it will be destroyed.
    role.cr4_pae:
      Contains the value of cr4.pae for which the page is valid (e.g. whether
      32-bit or 64-bit gptes are in use).
    role.nxe:
      Contains the value of efer.nxe for which the page is valid.
    role.cr0_wp:
      Contains the value of cr0.wp for which the page is valid.
    role.smep_andnot_wp:
      Contains the value of cr4.smep && !cr0.wp for which the page is valid
      (pages for which this is true are different from other pages; see the
      treatment of cr0.wp=0 below).
    gfn:
      Either the guest page table containing the translations shadowed by this
      page, or the base page frame for linear translations.  See role.direct.
    spt:
      A pageful of 64-bit sptes containing the translations for this page.
      Accessed by both kvm and hardware.
      The page pointed to by spt will have its page->private pointing back
      at the shadow page structure.
      sptes in spt point either at guest pages, or at lower-level shadow pages.
      Specifically, if sp1 and sp2 are shadow pages, then sp1->spt[n] may point
      at __pa(sp2->spt).  sp2 will point back at sp1 through parent_pte.
      The spt array forms a DAG structure with the shadow page as a node, and
      guest pages as leaves.
    gfns:
      An array of 512 guest frame numbers, one for each present pte.  Used to
      perform a reverse map from a pte to a gfn. When role.direct is set, any
      element of this array can be calculated from the gfn field when used, in
      this case, the array of gfns is not allocated. See role.direct and gfn.
    root_count:
      A counter keeping track of how many hardware registers (guest cr3 or
      pdptrs) are now pointing at the page.  While this counter is nonzero, the
      page cannot be destroyed.  See role.invalid.
    parent_ptes:
      The reverse mapping for the pte/ptes pointing at this page's spt. If
      parent_ptes bit 0 is zero, only one spte points at this pages and
      parent_ptes points at this single spte, otherwise, there exists multiple
      sptes pointing at this page and (parent_ptes & ~0x1) points at a data
      structure with a list of parent_ptes.
    unsync:
      If true, then the translations in this page may not match the guest's
      translation.  This is equivalent to the state of the tlb when a pte is
      changed but before the tlb entry is flushed.  Accordingly, unsync ptes
      are synchronized when the guest executes invlpg or flushes its tlb by
      other means.  Valid for leaf pages.
    unsync_children:
      How many sptes in the page point at pages that are unsync (or have
      unsynchronized children).
    unsync_child_bitmap:
      A bitmap indicating which sptes in spt point (directly or indirectly) at
      pages that may be unsynchronized.  Used to quickly locate all unsychronized
      pages reachable from a given page.
    mmu_valid_gen:
      Generation number of the page.  It is compared with kvm->arch.mmu_valid_gen
      during hash table lookup, and used to skip invalidated shadow pages (see
      "Zapping all pages" below.)
    clear_spte_count:
      Only present on 32-bit hosts, where a 64-bit spte cannot be written
      atomically.  The reader uses this while running out of the MMU lock
      to detect in-progress updates and retry them until the writer has
      finished the write.
    write_flooding_count:
      A guest may write to a page table many times, causing a lot of
      emulations if the page needs to be write-protected (see "Synchronized
      and unsynchronized pages" below).  Leaf pages can be unsynchronized
      so that they do not trigger frequent emulation, but this is not
      possible for non-leafs.  This field counts the number of emulations
      since the last time the page table was actually used; if emulation
      is triggered too frequently on this page, KVM will unmap the page
      to avoid emulation in the future.
  
  Reverse map
  ===========
  
  The mmu maintains a reverse mapping whereby all ptes mapping a page can be
  reached given its gfn.  This is used, for example, when swapping out a page.
  
  Synchronized and unsynchronized pages
  =====================================
  
  The guest uses two events to synchronize its tlb and page tables: tlb flushes
  and page invalidations (invlpg).
  
  A tlb flush means that we need to synchronize all sptes reachable from the
  guest's cr3.  This is expensive, so we keep all guest page tables write
  protected, and synchronize sptes to gptes when a gpte is written.
  
  A special case is when a guest page table is reachable from the current
  guest cr3.  In this case, the guest is obliged to issue an invlpg instruction
  before using the translation.  We take advantage of that by removing write
  protection from the guest page, and allowing the guest to modify it freely.
  We synchronize modified gptes when the guest invokes invlpg.  This reduces
  the amount of emulation we have to do when the guest modifies multiple gptes,
  or when the a guest page is no longer used as a page table and is used for
  random guest data.
  
  As a side effect we have to resynchronize all reachable unsynchronized shadow
  pages on a tlb flush.
  
  
  Reaction to events
  ==================
  
  - guest page fault (or npt page fault, or ept violation)
  
  This is the most complicated event.  The cause of a page fault can be:
  
    - a true guest fault (the guest translation won't allow the access) (*)
    - access to a missing translation
    - access to a protected translation
      - when logging dirty pages, memory is write protected
      - synchronized shadow pages are write protected (*)
    - access to untranslatable memory (mmio)
  
    (*) not applicable in direct mode
  
  Handling a page fault is performed as follows:
  
   - if the RSV bit of the error code is set, the page fault is caused by guest
     accessing MMIO and cached MMIO information is available.
     - walk shadow page table
     - check for valid generation number in the spte (see "Fast invalidation of
       MMIO sptes" below)
     - cache the information to vcpu->arch.mmio_gva, vcpu->arch.access and
       vcpu->arch.mmio_gfn, and call the emulator
   - If both P bit and R/W bit of error code are set, this could possibly
     be handled as a "fast page fault" (fixed without taking the MMU lock).  See
     the description in Documentation/virtual/kvm/locking.txt.
   - if needed, walk the guest page tables to determine the guest translation
     (gva->gpa or ngpa->gpa)
     - if permissions are insufficient, reflect the fault back to the guest
   - determine the host page
     - if this is an mmio request, there is no host page; cache the info to
       vcpu->arch.mmio_gva, vcpu->arch.access and vcpu->arch.mmio_gfn
   - walk the shadow page table to find the spte for the translation,
     instantiating missing intermediate page tables as necessary
     - If this is an mmio request, cache the mmio info to the spte and set some
       reserved bit on the spte (see callers of kvm_mmu_set_mmio_spte_mask)
   - try to unsynchronize the page
     - if successful, we can let the guest continue and modify the gpte
   - emulate the instruction
     - if failed, unshadow the page and let the guest continue
   - update any translations that were modified by the instruction
  
  invlpg handling:
  
    - walk the shadow page hierarchy and drop affected translations
    - try to reinstantiate the indicated translation in the hope that the
      guest will use it in the near future
  
  Guest control register updates:
  
  - mov to cr3
    - look up new shadow roots
    - synchronize newly reachable shadow pages
  
  - mov to cr0/cr4/efer
    - set up mmu context for new paging mode
    - look up new shadow roots
    - synchronize newly reachable shadow pages
  
  Host translation updates:
  
    - mmu notifier called with updated hva
    - look up affected sptes through reverse map
    - drop (or update) translations
  
  Emulating cr0.wp
  ================
  
  If tdp is not enabled, the host must keep cr0.wp=1 so page write protection
  works for the guest kernel, not guest guest userspace.  When the guest
  cr0.wp=1, this does not present a problem.  However when the guest cr0.wp=0,
  we cannot map the permissions for gpte.u=1, gpte.w=0 to any spte (the
  semantics require allowing any guest kernel access plus user read access).
  
  We handle this by mapping the permissions to two possible sptes, depending
  on fault type:
  
  - kernel write fault: spte.u=0, spte.w=1 (allows full kernel access,
    disallows user access)
  - read fault: spte.u=1, spte.w=0 (allows full read access, disallows kernel
    write access)
  
  (user write faults generate a #PF)
  
  In the first case there is an additional complication if CR4.SMEP is
  enabled: since we've turned the page into a kernel page, the kernel may now
  execute it.  We handle this by also setting spte.nx.  If we get a user
  fetch or read fault, we'll change spte.u=1 and spte.nx=gpte.nx back.
  
  To prevent an spte that was converted into a kernel page with cr0.wp=0
  from being written by the kernel after cr0.wp has changed to 1, we make
  the value of cr0.wp part of the page role.  This means that an spte created
  with one value of cr0.wp cannot be used when cr0.wp has a different value -
  it will simply be missed by the shadow page lookup code.  A similar issue
  exists when an spte created with cr0.wp=0 and cr4.smep=0 is used after
  changing cr4.smep to 1.  To avoid this, the value of !cr0.wp && cr4.smep
  is also made a part of the page role.
  
  Large pages
  ===========
  
  The mmu supports all combinations of large and small guest and host pages.
  Supported page sizes include 4k, 2M, 4M, and 1G.  4M pages are treated as
  two separate 2M pages, on both guest and host, since the mmu always uses PAE
  paging.
  
  To instantiate a large spte, four constraints must be satisfied:
  
  - the spte must point to a large host page
  - the guest pte must be a large pte of at least equivalent size (if tdp is
    enabled, there is no guest pte and this condition is satisfied)
  - if the spte will be writeable, the large page frame may not overlap any
    write-protected pages
  - the guest page must be wholly contained by a single memory slot
  
  To check the last two conditions, the mmu maintains a ->write_count set of
  arrays for each memory slot and large page size.  Every write protected page
  causes its write_count to be incremented, thus preventing instantiation of
  a large spte.  The frames at the end of an unaligned memory slot have
  artificially inflated ->write_counts so they can never be instantiated.
  
  Zapping all pages (page generation count)
  =========================================
  
  For the large memory guests, walking and zapping all pages is really slow
  (because there are a lot of pages), and also blocks memory accesses of
  all VCPUs because it needs to hold the MMU lock.
  
  To make it be more scalable, kvm maintains a global generation number
  which is stored in kvm->arch.mmu_valid_gen.  Every shadow page stores
  the current global generation-number into sp->mmu_valid_gen when it
  is created.  Pages with a mismatching generation number are "obsolete".
  
  When KVM need zap all shadow pages sptes, it just simply increases the global
  generation-number then reload root shadow pages on all vcpus.  As the VCPUs
  create new shadow page tables, the old pages are not used because of the
  mismatching generation number.
  
  KVM then walks through all pages and zaps obsolete pages.  While the zap
  operation needs to take the MMU lock, the lock can be released periodically
  so that the VCPUs can make progress.
  
  Fast invalidation of MMIO sptes
  ===============================
  
  As mentioned in "Reaction to events" above, kvm will cache MMIO
  information in leaf sptes.  When a new memslot is added or an existing
  memslot is changed, this information may become stale and needs to be
  invalidated.  This also needs to hold the MMU lock while walking all
  shadow pages, and is made more scalable with a similar technique.
  
  MMIO sptes have a few spare bits, which are used to store a
  generation number.  The global generation number is stored in
  kvm_memslots(kvm)->generation, and increased whenever guest memory info
  changes.  This generation number is distinct from the one described in
  the previous section.
  
  When KVM finds an MMIO spte, it checks the generation number of the spte.
  If the generation number of the spte does not equal the global generation
  number, it will ignore the cached MMIO information and handle the page
  fault through the slow path.
  
  Since only 19 bits are used to store generation-number on mmio spte, all
  pages are zapped when there is an overflow.
  
  Unfortunately, a single memory access might access kvm_memslots(kvm) multiple
  times, the last one happening when the generation number is retrieved and
  stored into the MMIO spte.  Thus, the MMIO spte might be created based on
  out-of-date information, but with an up-to-date generation number.
  
  To avoid this, the generation number is incremented again after synchronize_srcu
  returns; thus, the low bit of kvm_memslots(kvm)->generation is only 1 during a
  memslot update, while some SRCU readers might be using the old copy.  We do not
  want to use an MMIO sptes created with an odd generation number, and we can do
  this without losing a bit in the MMIO spte.  The low bit of the generation
  is not stored in MMIO spte, and presumed zero when it is extracted out of the
  spte.  If KVM is unlucky and creates an MMIO spte while the low bit is 1,
  the next access to the spte will always be a cache miss.
  
  
  Further reading
  ===============
  
  - NPT presentation from KVM Forum 2008
    http://www.linux-kvm.org/wiki/images/c/c8/KvmForum2008%24kdf2008_21.pdf