text: /******************************************************************************
   * arch/x86/mm/shadow/private.h
   *
   * Shadow code that is private, and does not need to be multiply compiled.
   * Parts of this code are Copyright (c) 2006 by XenSource Inc.
   * Parts of this code are Copyright (c) 2006 by Michael A Fetterman
   * Parts based on earlier work by Michael A Fetterman, Ian Pratt et al.
   *
   * This program is free software; you can redistribute it and/or modify
   * it under the terms of the GNU General Public License as published by
   * the Free Software Foundation; either version 2 of the License, or
   * (at your option) any later version.
   *
   * This program is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU General Public License for more details.
   *
   * You should have received a copy of the GNU General Public License
   * along with this program; if not, write to the Free Software
   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   */
  
  #ifndef _XEN_SHADOW_PRIVATE_H
  #define _XEN_SHADOW_PRIVATE_H
  
  // In order to override the definition of mfn_to_page, we make sure page.h has
  // been included...
  #include <asm/page.h>
  #include <xen/domain_page.h>
  #include <asm/x86_emulate.h>
  #include <asm/hvm/support.h>
  #include <asm/atomic.h>
  
  #include "../mm-locks.h"
  
  /******************************************************************************
   * Levels of self-test and paranoia
   */
  
  #define SHADOW_AUDIT_HASH           0x01  /* Check current hash bucket */
  #define SHADOW_AUDIT_HASH_FULL      0x02  /* Check every hash bucket */
  #define SHADOW_AUDIT_ENTRIES        0x04  /* Check this walk's shadows */
  #define SHADOW_AUDIT_ENTRIES_FULL   0x08  /* Check every shadow */
  #define SHADOW_AUDIT_ENTRIES_MFNS   0x10  /* Check gfn-mfn map in shadows */
  
  #ifdef NDEBUG
  #define SHADOW_AUDIT                   0
  #define SHADOW_AUDIT_ENABLE            0
  #else
  #define SHADOW_AUDIT                0x15  /* Basic audit of all */
  #define SHADOW_AUDIT_ENABLE         shadow_audit_enable
  extern int shadow_audit_enable;
  #endif
  
  /******************************************************************************
   * Levels of optimization
   */
  
  #define SHOPT_WRITABLE_HEURISTIC  0x01  /* Guess at RW PTEs via linear maps */
  #define SHOPT_EARLY_UNSHADOW      0x02  /* Unshadow l1s on fork or exit */
  #define SHOPT_FAST_FAULT_PATH     0x04  /* Fast-path MMIO and not-present */
  #define SHOPT_PREFETCH            0x08  /* Shadow multiple entries per fault */
  #define SHOPT_LINUX_L3_TOPLEVEL   0x10  /* Pin l3es on early 64bit linux */
  #define SHOPT_SKIP_VERIFY         0x20  /* Skip PTE v'fy when safe to do so */
  #define SHOPT_VIRTUAL_TLB         0x40  /* Cache guest v->p translations */
  #define SHOPT_FAST_EMULATION      0x80  /* Fast write emulation */
  #define SHOPT_OUT_OF_SYNC        0x100  /* Allow guest writes to L1 PTs */
  
  #define SHADOW_OPTIMIZATIONS     0x1ff
  
  
  /******************************************************************************
   * Debug and error-message output
   */
  
  #define SHADOW_PRINTK(_f, _a...)                                     \
      debugtrace_printk("sh: %s(): " _f, __func__, ##_a)
  #define SHADOW_ERROR(_f, _a...)                                      \
      printk("sh error: %s(): " _f, __func__, ##_a)
  #define SHADOW_DEBUG(flag, _f, _a...)                                \
      do {                                                              \
          if (SHADOW_DEBUG_ ## flag)                                   \
              debugtrace_printk("shdebug: %s(): " _f, __func__, ##_a); \
      } while (0)
  
  // The flags for use with SHADOW_DEBUG:
  #define SHADOW_DEBUG_PROPAGATE         1
  #define SHADOW_DEBUG_MAKE_SHADOW       1
  #define SHADOW_DEBUG_DESTROY_SHADOW    1
  #define SHADOW_DEBUG_A_AND_D           1
  #define SHADOW_DEBUG_EMULATE           1
  #define SHADOW_DEBUG_P2M               1
  #define SHADOW_DEBUG_LOGDIRTY          0
  
  /******************************************************************************
   * Tracing
   */
  DECLARE_PER_CPU(uint32_t,trace_shadow_path_flags);
  
  #define TRACE_SHADOW_PATH_FLAG(_x)                      \
      do {                                                \
          this_cpu(trace_shadow_path_flags) |= (1<<(_x));      \
      } while(0)
  
  #define TRACE_CLEAR_PATH_FLAGS                  \
      this_cpu(trace_shadow_path_flags) = 0
  
  enum {
      TRCE_SFLAG_SET_AD,
      TRCE_SFLAG_SET_A,
      TRCE_SFLAG_SHADOW_L1_GET_REF,
      TRCE_SFLAG_SHADOW_L1_PUT_REF,
      TRCE_SFLAG_L2_PROPAGATE,
      TRCE_SFLAG_SET_CHANGED,
      TRCE_SFLAG_SET_FLUSH,
      TRCE_SFLAG_SET_ERROR,
      TRCE_SFLAG_DEMOTE,
      TRCE_SFLAG_PROMOTE,
      TRCE_SFLAG_WRMAP,
      TRCE_SFLAG_WRMAP_GUESS_FOUND,
      TRCE_SFLAG_WRMAP_BRUTE_FORCE,
      TRCE_SFLAG_EARLY_UNSHADOW,
      TRCE_SFLAG_EMULATION_2ND_PT_WRITTEN,
      TRCE_SFLAG_EMULATION_LAST_FAILED,
      TRCE_SFLAG_EMULATE_FULL_PT,
      TRCE_SFLAG_PREALLOC_UNHOOK,
      TRCE_SFLAG_UNSYNC,
      TRCE_SFLAG_OOS_FIXUP_ADD,
      TRCE_SFLAG_OOS_FIXUP_EVICT,
  };
  
  
  /* Size (in bytes) of a guest PTE */
  #if GUEST_PAGING_LEVELS >= 3
  # define GUEST_PTE_SIZE 8
  #else
  # define GUEST_PTE_SIZE 4
  #endif
  
  /******************************************************************************
   * Auditing routines 
   */
  
  #if SHADOW_AUDIT & SHADOW_AUDIT_ENTRIES_FULL
  extern void shadow_audit_tables(struct vcpu *v);
  #else
  #define shadow_audit_tables(_v) do {} while(0)
  #endif
  
  /******************************************************************************
   * Macro for dealing with the naming of the internal names of the
   * shadow code's external entry points.
   */
  #define SHADOW_INTERNAL_NAME_HIDDEN(name, guest_levels) \
      name ## __guest_ ## guest_levels
  #define SHADOW_INTERNAL_NAME(name, guest_levels)        \
      SHADOW_INTERNAL_NAME_HIDDEN(name, guest_levels)
  
  #define GUEST_LEVELS  2
  #include "multi.h"
  #undef GUEST_LEVELS
  
  #define GUEST_LEVELS  3
  #include "multi.h"
  #undef GUEST_LEVELS
  
  #if CONFIG_PAGING_LEVELS == 4
  #define GUEST_LEVELS  4
  #include "multi.h"
  #undef GUEST_LEVELS
  #endif /* CONFIG_PAGING_LEVELS == 4 */
  
  /* Shadow type codes */
  #define SH_type_none           (0U) /* on the shadow free list */
  #define SH_type_min_shadow     (1U)
  #define SH_type_l1_32_shadow   (1U) /* shadowing a 32-bit L1 guest page */
  #define SH_type_fl1_32_shadow  (2U) /* L1 shadow for a 32b 4M superpage */
  #define SH_type_l2_32_shadow   (3U) /* shadowing a 32-bit L2 guest page */
  #define SH_type_l1_pae_shadow  (4U) /* shadowing a pae L1 page */
  #define SH_type_fl1_pae_shadow (5U) /* L1 shadow for pae 2M superpg */
  #define SH_type_l2_pae_shadow  (6U) /* shadowing a pae L2-low page */
  #define SH_type_l2h_pae_shadow (7U) /* shadowing a pae L2-high page */
  #define SH_type_l1_64_shadow   (8U) /* shadowing a 64-bit L1 page */
  #define SH_type_fl1_64_shadow  (9U) /* L1 shadow for 64-bit 2M superpg */
  #define SH_type_l2_64_shadow  (10U) /* shadowing a 64-bit L2 page */
  #define SH_type_l2h_64_shadow (11U) /* shadowing a compat PAE L2 high page */
  #define SH_type_l3_64_shadow  (12U) /* shadowing a 64-bit L3 page */
  #define SH_type_l4_64_shadow  (13U) /* shadowing a 64-bit L4 page */
  #define SH_type_max_shadow    (13U)
  #define SH_type_p2m_table     (14U) /* in use as the p2m table */
  #define SH_type_monitor_table (15U) /* in use as a monitor table */
  #define SH_type_oos_snapshot  (16U) /* in use as OOS snapshot */
  #define SH_type_unused        (17U)
  
  /* 
   * What counts as a pinnable shadow?
   */
  
  static inline int sh_type_is_pinnable(struct vcpu *v, unsigned int t) 
  {
      /* Top-level shadow types in each mode can be pinned, so that they 
       * persist even when not currently in use in a guest CR3 */
      if ( t == SH_type_l2_32_shadow
           || t == SH_type_l2_pae_shadow
           || t == SH_type_l2h_pae_shadow 
           || t == SH_type_l4_64_shadow )
          return 1;
  
  #if (SHADOW_OPTIMIZATIONS & SHOPT_LINUX_L3_TOPLEVEL) 
      /* Early 64-bit linux used three levels of pagetables for the guest
       * and context switched by changing one l4 entry in a per-cpu l4
       * page.  When we're shadowing those kernels, we have to pin l3
       * shadows so they don't just evaporate on every context switch.
       * For all other guests, we'd rather use the up-pointer field in l3s. */ 
      if ( unlikely((v->domain->arch.paging.shadow.opt_flags & SHOPT_LINUX_L3_TOPLEVEL) 
                    && CONFIG_PAGING_LEVELS >= 4
                    && t == SH_type_l3_64_shadow) )
          return 1;
  #endif
  
      /* Everything else is not pinnable, and can use the "up" pointer */
      return 0;
  }
  
  static inline int sh_type_has_up_pointer(struct vcpu *v, unsigned int t) 
  {
      /* Multi-page shadows don't have up-pointers */
      if ( t == SH_type_l1_32_shadow
           || t == SH_type_fl1_32_shadow
           || t == SH_type_l2_32_shadow )
          return 0;
      /* Pinnable shadows don't have up-pointers either */
      return !sh_type_is_pinnable(v, t);
  }
  
  /*
   * Definitions for the shadow_flags field in page_info.
   * These flags are stored on *guest* pages...
   * Bits 1-13 are encodings for the shadow types.
   */
  #define SHF_page_type_mask \
      (((1u << (SH_type_max_shadow + 1u)) - 1u) - \
       ((1u << SH_type_min_shadow) - 1u))
  
  #define SHF_L1_32   (1u << SH_type_l1_32_shadow)
  #define SHF_FL1_32  (1u << SH_type_fl1_32_shadow)
  #define SHF_L2_32   (1u << SH_type_l2_32_shadow)
  #define SHF_L1_PAE  (1u << SH_type_l1_pae_shadow)
  #define SHF_FL1_PAE (1u << SH_type_fl1_pae_shadow)
  #define SHF_L2_PAE  (1u << SH_type_l2_pae_shadow)
  #define SHF_L2H_PAE (1u << SH_type_l2h_pae_shadow)
  #define SHF_L1_64   (1u << SH_type_l1_64_shadow)
  #define SHF_FL1_64  (1u << SH_type_fl1_64_shadow)
  #define SHF_L2_64   (1u << SH_type_l2_64_shadow)
  #define SHF_L2H_64  (1u << SH_type_l2h_64_shadow)
  #define SHF_L3_64   (1u << SH_type_l3_64_shadow)
  #define SHF_L4_64   (1u << SH_type_l4_64_shadow)
  
  #define SHF_32  (SHF_L1_32|SHF_FL1_32|SHF_L2_32)
  #define SHF_PAE (SHF_L1_PAE|SHF_FL1_PAE|SHF_L2_PAE|SHF_L2H_PAE)
  #define SHF_64  (SHF_L1_64|SHF_FL1_64|SHF_L2_64|SHF_L2H_64|SHF_L3_64|SHF_L4_64)
  
  #define SHF_L1_ANY  (SHF_L1_32|SHF_L1_PAE|SHF_L1_64)
  
  #if (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC) 
  /* Marks a guest L1 page table which is shadowed but not write-protected.
   * If set, then *only* L1 shadows (SHF_L1_*) are allowed. 
   *
   * out_of_sync indicates that the shadow tables may not reflect the
   * guest tables.  If it is clear, then the shadow tables *must* reflect
   * the guest tables.
   *
   * oos_may_write indicates that a page may have writable mappings.
   *
   * Most of the time the flags are synonymous.  There is a short period of time 
   * during resync that oos_may_write is clear but out_of_sync is not.  If a 
   * codepath is called during that time and is sensitive to oos issues, it may 
   * need to use the second flag.
   */
  #define SHF_out_of_sync (1u<<30)
  #define SHF_oos_may_write (1u<<29)
  
  #endif /* (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC) */
  
  #define SHF_pagetable_dying (1u<<31)
  
  static inline int sh_page_has_multiple_shadows(struct page_info *pg)
  {
      u32 shadows;
      if ( !(pg->count_info & PGC_page_table) )
          return 0;
      shadows = pg->shadow_flags & SHF_page_type_mask;
      /* More than one type bit set in shadow-flags? */
      return ( (shadows & ~(1UL << find_first_set_bit(shadows))) != 0 );
  }
  
  #if (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC) 
  /* The caller must verify this is reasonable to call; i.e., valid mfn,
   * domain is translated, &c */
  static inline int page_is_out_of_sync(struct page_info *p) 
  {
      return (p->count_info & PGC_page_table)
          && (p->shadow_flags & SHF_out_of_sync);
  }
  
  static inline int mfn_is_out_of_sync(mfn_t gmfn) 
  {
      return page_is_out_of_sync(mfn_to_page(mfn_x(gmfn)));
  }
  
  static inline int page_oos_may_write(struct page_info *p) 
  {
      return (p->count_info & PGC_page_table)
          && (p->shadow_flags & SHF_oos_may_write);
  }
  
  static inline int mfn_oos_may_write(mfn_t gmfn) 
  {
      return page_oos_may_write(mfn_to_page(mfn_x(gmfn)));
  }
  #endif /* (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC) */
  
  /******************************************************************************
   * Various function declarations 
   */
  
  /* Hash table functions */
  mfn_t shadow_hash_lookup(struct vcpu *v, unsigned long n, unsigned int t);
  void  shadow_hash_insert(struct vcpu *v, 
                           unsigned long n, unsigned int t, mfn_t smfn);
  void  shadow_hash_delete(struct vcpu *v, 
                           unsigned long n, unsigned int t, mfn_t smfn);
  
  /* shadow promotion */
  void shadow_promote(struct vcpu *v, mfn_t gmfn, u32 type);
  void shadow_demote(struct vcpu *v, mfn_t gmfn, u32 type);
  
  /* Shadow page allocation functions */
  void  shadow_prealloc(struct domain *d, u32 shadow_type, unsigned int count);
  mfn_t shadow_alloc(struct domain *d, 
                      u32 shadow_type,
                      unsigned long backpointer);
  void  shadow_free(struct domain *d, mfn_t smfn);
  
  /* Install the xen mappings in various flavours of shadow */
  void sh_install_xen_entries_in_l4(struct vcpu *v, mfn_t gl4mfn, mfn_t sl4mfn);
  
  /* Update the shadows in response to a pagetable write from Xen */
  int sh_validate_guest_entry(struct vcpu *v, mfn_t gmfn, void *entry, u32 size);
  
  /* Update the shadows in response to a pagetable write from a HVM guest */
  void sh_validate_guest_pt_write(struct vcpu *v, mfn_t gmfn, 
                                  void *entry, u32 size);
  
  /* Remove all writeable mappings of a guest frame from the shadows.
   * Returns non-zero if we need to flush TLBs. 
   * level and fault_addr desribe how we found this to be a pagetable;
   * level==0 means we have some other reason for revoking write access. */
  extern int sh_remove_write_access(struct vcpu *v, mfn_t readonly_mfn,
                                    unsigned int level,
                                    unsigned long fault_addr);
  
  /* Functions that atomically write PT/P2M entries and update state */
  void shadow_write_p2m_entry(struct vcpu *v, unsigned long gfn, 
                              l1_pgentry_t *p, mfn_t table_mfn,
                              l1_pgentry_t new, unsigned int level);
  int shadow_write_guest_entry(struct vcpu *v, intpte_t *p,
                               intpte_t new, mfn_t gmfn);
  int shadow_cmpxchg_guest_entry(struct vcpu *v, intpte_t *p,
                                 intpte_t *old, intpte_t new, mfn_t gmfn);
  
  /* Unhook the non-Xen mappings in this top-level shadow mfn.
   * With user_only == 1, unhooks only the user-mode mappings. */
  void shadow_unhook_mappings(struct vcpu *v, mfn_t smfn, int user_only);
  
  #if (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC)
  /* Allow a shadowed page to go out of sync */
  int sh_unsync(struct vcpu *v, mfn_t gmfn);
  
  /* Pull an out-of-sync page back into sync. */
  void sh_resync(struct vcpu *v, mfn_t gmfn);
  
  void oos_fixup_add(struct vcpu *v, mfn_t gmfn, mfn_t smfn, unsigned long off);
  
  int sh_remove_write_access_from_sl1p(struct vcpu *v, mfn_t gmfn,
                                       mfn_t smfn, unsigned long offset);
  
  /* Pull all out-of-sync shadows back into sync.  If skip != 0, we try
   * to avoid resyncing where we think we can get away with it. */
  
  void sh_resync_all(struct vcpu *v, int skip, int this, int others);
  
  static inline void
  shadow_resync_all(struct vcpu *v)
  {
      sh_resync_all(v, 0 /* skip */, 1 /* this */, 1 /* others */);
  }
  
  static inline void
  shadow_resync_current_vcpu(struct vcpu *v)
  {
      sh_resync_all(v, 0 /* skip */, 1 /* this */, 0 /* others */);
  }
  
  static inline void
  shadow_sync_other_vcpus(struct vcpu *v)
  {
      sh_resync_all(v, 1 /* skip */, 0 /* this */, 1 /* others */);
  }
  
  void oos_audit_hash_is_present(struct domain *d, mfn_t gmfn);
  mfn_t oos_snapshot_lookup(struct vcpu *v, mfn_t gmfn);
  
  #endif /* (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC) */
  
  
  /* Reset the up-pointers of every L3 shadow to 0. 
   * This is called when l3 shadows stop being pinnable, to clear out all
   * the list-head bits so the up-pointer field is properly inititalised. */
  void sh_reset_l3_up_pointers(struct vcpu *v);
  
  /******************************************************************************
   * Flags used in the return value of the shadow_set_lXe() functions...
   */
  
  /* We actually wrote something new to the shadow */
  #define SHADOW_SET_CHANGED            0x1
  /* Caller should flush TLBs to clear the old entry */
  #define SHADOW_SET_FLUSH              0x2
  /* Something went wrong: the shadow entry was invalid or refcount failed */
  #define SHADOW_SET_ERROR              0x4
  
  
  /******************************************************************************
   * MFN/page-info handling 
   */
  
  /* Override macros from asm/page.h to make them work with mfn_t */
  #undef mfn_to_page
  #define mfn_to_page(_m) __mfn_to_page(mfn_x(_m))
  #undef mfn_valid
  #define mfn_valid(_mfn) __mfn_valid(mfn_x(_mfn))
  #undef page_to_mfn
  #define page_to_mfn(_pg) _mfn(__page_to_mfn(_pg))
  
  /* Override pagetable_t <-> struct page_info conversions to work with mfn_t */
  #undef pagetable_get_page
  #define pagetable_get_page(x)   mfn_to_page(pagetable_get_mfn(x))
  #undef pagetable_from_page
  #define pagetable_from_page(pg) pagetable_from_mfn(page_to_mfn(pg))
  
  #define backpointer(sp) _mfn(pdx_to_pfn((unsigned long)(sp)->v.sh.back))
  static inline unsigned long __backpointer(const struct page_info *sp)
  {
      switch (sp->u.sh.type)
      {
      case SH_type_fl1_32_shadow:
      case SH_type_fl1_pae_shadow:
      case SH_type_fl1_64_shadow:
          return sp->v.sh.back;
      }
      return pdx_to_pfn(sp->v.sh.back);
  }
  
  static inline int
  sh_mfn_is_a_page_table(mfn_t gmfn)
  {
      struct page_info *page = mfn_to_page(gmfn);
      struct domain *owner;
      unsigned long type_info;
  
      if ( !mfn_valid(gmfn) )
          return 0;
  
      owner = page_get_owner(page);
      if ( owner && shadow_mode_refcounts(owner) 
           && (page->count_info & PGC_page_table) )
          return 1; 
  
      type_info = page->u.inuse.type_info & PGT_type_mask;
      return type_info && (type_info <= PGT_l4_page_table);
  }
  
  // Provide mfn_t-aware versions of common xen functions
  static inline void *
  sh_map_domain_page(mfn_t mfn)
  {
      return map_domain_page(mfn_x(mfn));
  }
  
  static inline void 
  sh_unmap_domain_page(void *p) 
  {
      unmap_domain_page(p);
  }
  
  static inline void *
  sh_map_domain_page_global(mfn_t mfn)
  {
      return map_domain_page_global(mfn_x(mfn));
  }
  
  static inline void 
  sh_unmap_domain_page_global(void *p) 
  {
      unmap_domain_page_global(p);
  }
  
  /**************************************************************************/
  /* Shadow-page refcounting. */
  
  void sh_destroy_shadow(struct vcpu *v, mfn_t smfn);
  
  /* Increase the refcount of a shadow page.  Arguments are the mfn to refcount, 
   * and the physical address of the shadow entry that holds the ref (or zero
   * if the ref is held by something else).  
   * Returns 0 for failure, 1 for success. */
  static inline int sh_get_ref(struct vcpu *v, mfn_t smfn, paddr_t entry_pa)
  {
      u32 x, nx;
      struct page_info *sp = mfn_to_page(smfn);
  
      ASSERT(mfn_valid(smfn));
      ASSERT(sp->u.sh.head);
  
      x = sp->u.sh.count;
      nx = x + 1;
  
      if ( unlikely(nx >= 1U<<26) )
      {
          SHADOW_PRINTK("shadow ref overflow, gmfn=%lx smfn=%lx\n",
                         __backpointer(sp), mfn_x(smfn));
          return 0;
      }
      
      /* Guarded by the paging lock, so no need for atomic update */
      sp->u.sh.count = nx;
  
      /* We remember the first shadow entry that points to each shadow. */
      if ( entry_pa != 0 
           && sh_type_has_up_pointer(v, sp->u.sh.type)
           && sp->up == 0 ) 
          sp->up = entry_pa;
      
      return 1;
  }
  
  
  /* Decrease the refcount of a shadow page.  As for get_ref, takes the
   * physical address of the shadow entry that held this reference. */
  static inline void sh_put_ref(struct vcpu *v, mfn_t smfn, paddr_t entry_pa)
  {
      u32 x, nx;
      struct page_info *sp = mfn_to_page(smfn);
  
      ASSERT(mfn_valid(smfn));
      ASSERT(sp->u.sh.head);
      ASSERT(!(sp->count_info & PGC_count_mask));
  
      /* If this is the entry in the up-pointer, remove it */
      if ( entry_pa != 0 
           && sh_type_has_up_pointer(v, sp->u.sh.type)
           && sp->up == entry_pa ) 
          sp->up = 0;
  
      x = sp->u.sh.count;
      nx = x - 1;
  
      if ( unlikely(x == 0) ) 
      {
          SHADOW_ERROR("shadow ref underflow, smfn=%lx oc=%08x t=%#x\n",
                       mfn_x(smfn), sp->u.sh.count, sp->u.sh.type);
          BUG();
      }
  
      /* Guarded by the paging lock, so no need for atomic update */
      sp->u.sh.count = nx;
  
      if ( unlikely(nx == 0) ) 
          sh_destroy_shadow(v, smfn);
  }
  
  
  /* Walk the list of pinned shadows, from the tail forwards, 
   * skipping the non-head-page entries */
  static inline struct page_info *
  prev_pinned_shadow(const struct page_info *page,
                     const struct domain *d)
  {
      struct page_info *p;
  
      if ( page == d->arch.paging.shadow.pinned_shadows.next ) 
          return NULL;
      
      if ( page == NULL ) /* If no current place, start at the tail */
          p = d->arch.paging.shadow.pinned_shadows.tail;
      else
          p = pdx_to_page(page->list.prev);
      /* Skip over the non-tail parts of multi-page shadows */
      if ( p && p->u.sh.type == SH_type_l2_32_shadow )
      {
          p = pdx_to_page(p->list.prev);
          ASSERT(p && p->u.sh.type == SH_type_l2_32_shadow);
          p = pdx_to_page(p->list.prev);
          ASSERT(p && p->u.sh.type == SH_type_l2_32_shadow);
          p = pdx_to_page(p->list.prev);
          ASSERT(p && p->u.sh.type == SH_type_l2_32_shadow);
      }
      ASSERT(!p || p->u.sh.head);
      return p;
  }
  
  #define foreach_pinned_shadow(dom, pos, tmp)                    \
      for ( pos = prev_pinned_shadow(NULL, (dom));                \
            pos ? (tmp = prev_pinned_shadow(pos, (dom)), 1) : 0;  \
            pos = tmp )
  
  /* Pin a shadow page: take an extra refcount, set the pin bit,
   * and put the shadow at the head of the list of pinned shadows.
   * Returns 0 for failure, 1 for success. */
  static inline int sh_pin(struct vcpu *v, mfn_t smfn)
  {
      struct page_info *sp;
      struct page_list_head h, *pin_list;
      
      ASSERT(mfn_valid(smfn));
      sp = mfn_to_page(smfn);
      ASSERT(sh_type_is_pinnable(v, sp->u.sh.type));
      ASSERT(sp->u.sh.head);
  
      /* Treat the up-to-four pages of the shadow as a unit in the list ops */
      h.next = h.tail = sp; 
      if ( sp->u.sh.type == SH_type_l2_32_shadow ) 
      {
          h.tail = pdx_to_page(h.tail->list.next);
          h.tail = pdx_to_page(h.tail->list.next);
          h.tail = pdx_to_page(h.tail->list.next);
          ASSERT(h.tail->u.sh.type == SH_type_l2_32_shadow); 
      }
      pin_list = &v->domain->arch.paging.shadow.pinned_shadows;
  
      if ( sp->u.sh.pinned )
      {
          /* Already pinned: take it out of the pinned-list so it can go 
           * at the front */
          if ( pin_list->next == h.next )
              return 1;
          page_list_prev(h.next, pin_list)->list.next = h.tail->list.next;
          if ( pin_list->tail == h.tail )
              pin_list->tail = page_list_prev(h.next, pin_list);
          else
              page_list_next(h.tail, pin_list)->list.prev = h.next->list.prev;
          h.tail->list.next = h.next->list.prev = PAGE_LIST_NULL;
      }
      else
      {
          /* Not pinned: pin it! */
          if ( !sh_get_ref(v, smfn, 0) )
              return 0;
          sp->u.sh.pinned = 1;
          ASSERT(h.next->list.prev == PAGE_LIST_NULL);
          ASSERT(h.tail->list.next == PAGE_LIST_NULL);
      }
      /* Put it at the head of the list of pinned shadows */
      page_list_splice(&h, pin_list);
      return 1;
  }
  
  /* Unpin a shadow page: unset the pin bit, take the shadow off the list
   * of pinned shadows, and release the extra ref. */
  static inline void sh_unpin(struct vcpu *v, mfn_t smfn)
  {
      struct page_list_head h, *pin_list;
      struct page_info *sp;
      
      ASSERT(mfn_valid(smfn));
      sp = mfn_to_page(smfn);
      ASSERT(sh_type_is_pinnable(v, sp->u.sh.type));
      ASSERT(sp->u.sh.head);
  
      /* Treat the up-to-four pages of the shadow as a unit in the list ops */
      h.next = h.tail = sp; 
      if ( sp->u.sh.type == SH_type_l2_32_shadow ) 
      {
          h.tail = pdx_to_page(h.tail->list.next);
          h.tail = pdx_to_page(h.tail->list.next);
          h.tail = pdx_to_page(h.tail->list.next);
          ASSERT(h.tail->u.sh.type == SH_type_l2_32_shadow); 
      }
      pin_list = &v->domain->arch.paging.shadow.pinned_shadows;
  
      if ( !sp->u.sh.pinned )
          return;
  
      sp->u.sh.pinned = 0;
  
      /* Cut the sub-list out of the list of pinned shadows */
      if ( pin_list->next == h.next && pin_list->tail == h.tail )
          pin_list->next = pin_list->tail = NULL;
      else 
      {
          if ( pin_list->next == h.next )
              pin_list->next = page_list_next(h.tail, pin_list);
          else
              page_list_prev(h.next, pin_list)->list.next = h.tail->list.next;
          if ( pin_list->tail == h.tail )
              pin_list->tail = page_list_prev(h.next, pin_list);
          else
              page_list_next(h.tail, pin_list)->list.prev = h.next->list.prev;
      }
      h.tail->list.next = h.next->list.prev = PAGE_LIST_NULL;
      
      sh_put_ref(v, smfn, 0);
  }
  
  
  /**************************************************************************/
  /* PTE-write emulation. */
  
  struct sh_emulate_ctxt {
      struct x86_emulate_ctxt ctxt;
  
      /* Cache of up to 31 bytes of instruction. */
      uint8_t insn_buf[31];
      uint8_t insn_buf_bytes;
      unsigned long insn_buf_eip;
  
      /* Cache of segment registers already gathered for this emulation. */
      unsigned int valid_seg_regs;
      struct segment_register seg_reg[6];
  
      /* MFNs being written to in write/cmpxchg callbacks */
      mfn_t mfn1, mfn2;
  
  #if (SHADOW_OPTIMIZATIONS & SHOPT_SKIP_VERIFY)
      /* Special case for avoiding having to verify writes: remember 
       * whether the old value had its low bit (_PAGE_PRESENT) clear. */
      int low_bit_was_clear:1;
  #endif
  };
  
  const struct x86_emulate_ops *shadow_init_emulation(
      struct sh_emulate_ctxt *sh_ctxt, struct cpu_user_regs *regs);
  void shadow_continue_emulation(
      struct sh_emulate_ctxt *sh_ctxt, struct cpu_user_regs *regs);
  struct segment_register *hvm_get_seg_reg(
      enum x86_segment seg, struct sh_emulate_ctxt *sh_ctxt);
  
  #if (SHADOW_OPTIMIZATIONS & SHOPT_VIRTUAL_TLB)
  /**************************************************************************/
  /* Virtual TLB entries 
   *
   * We keep a cache of virtual-to-physical translations that we have seen 
   * since the last TLB flush.  This is safe to use for frame translations, 
   * but callers need to re-check the actual guest tables if the lookup fails.
   * 
   * Lookups and updates are protected by a per-vTLB (and hence per-vcpu)
   * lock.  This lock is held *only* while reading or writing the table,
   * so it is safe to take in any non-interrupt context.  Most lookups
   * happen with v==current, so we expect contention to be low.
   */
  
  #define VTLB_ENTRIES 13
  
  struct shadow_vtlb {
      unsigned long page_number;      /* Guest virtual address >> PAGE_SHIFT  */
      unsigned long frame_number;     /* Guest physical address >> PAGE_SHIFT */
      uint32_t pfec;     /* PF error code of the lookup that filled this
                          * entry.  A pfec of zero means the slot is empty
                          * (since that would require us to re-try anyway) */
  };
  
  /* Call whenever the guest flushes hit actual TLB */
  static inline void vtlb_flush(struct vcpu *v) 
  {
      spin_lock(&v->arch.paging.vtlb_lock);
      memset(v->arch.paging.vtlb, 0, VTLB_ENTRIES * sizeof (struct shadow_vtlb));
      spin_unlock(&v->arch.paging.vtlb_lock);
  }
  
  static inline int vtlb_hash(unsigned long page_number)
  {
      return page_number % VTLB_ENTRIES;
  }
  
  /* Put a translation into the vTLB, potentially clobbering an old one */
  static inline void vtlb_insert(struct vcpu *v, unsigned long page,
                                 unsigned long frame, uint32_t pfec)
  {
      struct shadow_vtlb entry = 
          { .page_number = page, .frame_number = frame, .pfec = pfec };
      spin_lock(&v->arch.paging.vtlb_lock);
      v->arch.paging.vtlb[vtlb_hash(page)] = entry;
      spin_unlock(&v->arch.paging.vtlb_lock);
  }
  
  /* Look a translation up in the vTLB.  Returns INVALID_GFN if not found. */
  static inline unsigned long vtlb_lookup(struct vcpu *v,
                                          unsigned long va, uint32_t pfec)
  {
      unsigned long page_number = va >> PAGE_SHIFT;
      unsigned long frame_number = INVALID_GFN;
      int i = vtlb_hash(page_number);
  
      spin_lock(&v->arch.paging.vtlb_lock);
      if ( v->arch.paging.vtlb[i].pfec != 0
           && v->arch.paging.vtlb[i].page_number == page_number 
           /* Any successful walk that had at least these pfec bits is OK */
           && (v->arch.paging.vtlb[i].pfec & pfec) == pfec )
      {
          frame_number = v->arch.paging.vtlb[i].frame_number;
      }
      spin_unlock(&v->arch.paging.vtlb_lock);
      return frame_number;
  }
  #endif /* (SHADOW_OPTIMIZATIONS & SHOPT_VIRTUAL_TLB) */
  
  static inline int sh_check_page_has_no_refs(struct page_info *page)
  {
      unsigned long count = read_atomic(&page->count_info);
      return ( (count & PGC_count_mask) ==
               ((count & PGC_allocated) ? 1 : 0) ); 
  }
  
  #endif /* _XEN_SHADOW_PRIVATE_H */
  
  /*
   * Local variables:
   * mode: C
   * c-set-style: "BSD"
   * c-basic-offset: 4
   * indent-tabs-mode: nil
   * End:
   */
  