Quelle  mmu.c   Sprache: C

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Kernel-based Virtual Machine driver for Linux
 *
 * This module enables machines with Intel VT-x extensions to run virtual
 * machines without emulation or binary translation.
 *
 * MMU support
 *
 * Copyright (C) 2006 Qumranet, Inc.
 * Copyright 2010 Red Hat, Inc. and/or its affiliates.
 *
 * Authors:
 *   Yaniv Kamay  <yaniv@qumranet.com>
 *   Avi Kivity   <avi@qumranet.com>
 */
#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

#include "irq.h"
#include "ioapic.h"
#include "mmu.h"
#include "mmu_internal.h"
#include "tdp_mmu.h"
#include "x86.h"
#include "kvm_cache_regs.h"
#include "smm.h"
#include "kvm_emulate.h"
#include "page_track.h"
#include "cpuid.h"
#include "spte.h"

#include <linux/kvm_host.h>
#include <linux/types.h>
#include <linux/string.h>
#include <linux/mm.h>
#include <linux/highmem.h>
#include <linux/moduleparam.h>
#include <linux/export.h>
#include <linux/swap.h>
#include <linux/hugetlb.h>
#include <linux/compiler.h>
#include <linux/srcu.h>
#include <linux/slab.h>
#include <linux/sched/signal.h>
#include <linux/uaccess.h>
#include <linux/hash.h>
#include <linux/kern_levels.h>
#include <linux/kstrtox.h>
#include <linux/kthread.h>
#include <linux/wordpart.h>

#include <asm/page.h>
#include <asm/memtype.h>
#include <asm/cmpxchg.h>
#include <asm/io.h>
#include <asm/set_memory.h>
#include <asm/spec-ctrl.h>
#include <asm/vmx.h>

#include "trace.h"

static bool nx_hugepage_mitigation_hard_disabled;

int __read_mostly nx_huge_pages = -1;
static uint __read_mostly nx_huge_pages_recovery_period_ms;
#ifdef CONFIG_PREEMPT_RT
/* Recovery can cause latency spikes, disable it for PREEMPT_RT.  */
static uint __read_mostly nx_huge_pages_recovery_ratio = 0;
#else
static uint __read_mostly nx_huge_pages_recovery_ratio = 60;
#endif

static int get_nx_huge_pages(char *buffer, const struct kernel_param *kp);
static int set_nx_huge_pages(const char *val, const struct kernel_param *kp);
static int set_nx_huge_pages_recovery_param(const char *val, const struct kernel_param *kp);

static const struct kernel_param_ops nx_huge_pages_ops = {
 .set = set_nx_huge_pages,
 .get = get_nx_huge_pages,
};

static const struct kernel_param_ops nx_huge_pages_recovery_param_ops = {
 .set = set_nx_huge_pages_recovery_param,
 .get = param_get_uint,
};

module_param_cb(nx_huge_pages, &nx_huge_pages_ops, &nx_huge_pages, 0644);
__MODULE_PARM_TYPE(nx_huge_pages, "bool");
module_param_cb(nx_huge_pages_recovery_ratio, &nx_huge_pages_recovery_param_ops,
  &nx_huge_pages_recovery_ratio, 0644);
__MODULE_PARM_TYPE(nx_huge_pages_recovery_ratio, "uint");
module_param_cb(nx_huge_pages_recovery_period_ms, &nx_huge_pages_recovery_param_ops,
  &nx_huge_pages_recovery_period_ms, 0644);
__MODULE_PARM_TYPE(nx_huge_pages_recovery_period_ms, "uint");

static bool __read_mostly force_flush_and_sync_on_reuse;
module_param_named(flush_on_reuse, force_flush_and_sync_on_reuse, bool, 0644);

/*
 * When setting this variable to true it enables Two-Dimensional-Paging
 * where the hardware walks 2 page tables:
 * 1. the guest-virtual to guest-physical
 * 2. while doing 1. it walks guest-physical to host-physical
 * If the hardware supports that we don't need to do shadow paging.
 */
bool tdp_enabled = false;

static bool __ro_after_init tdp_mmu_allowed;

#ifdef CONFIG_X86_64
bool __read_mostly tdp_mmu_enabled = true;
module_param_named(tdp_mmu, tdp_mmu_enabled, bool, 0444);
EXPORT_SYMBOL_GPL(tdp_mmu_enabled);
#endif

static int max_huge_page_level __read_mostly;
static int tdp_root_level __read_mostly;
static int max_tdp_level __read_mostly;

#define PTE_PREFETCH_NUM  8

#include <trace/events/kvm.h>

/* make pte_list_desc fit well in cache lines */
#define PTE_LIST_EXT 14

/*
 * struct pte_list_desc is the core data structure used to implement a custom
 * list for tracking a set of related SPTEs, e.g. all the SPTEs that map a
 * given GFN when used in the context of rmaps.  Using a custom list allows KVM
 * to optimize for the common case where many GFNs will have at most a handful
 * of SPTEs pointing at them, i.e. allows packing multiple SPTEs into a small
 * memory footprint, which in turn improves runtime performance by exploiting
 * cache locality.
 *
 * A list is comprised of one or more pte_list_desc objects (descriptors).
 * Each individual descriptor stores up to PTE_LIST_EXT SPTEs.  If a descriptor
 * is full and a new SPTEs needs to be added, a new descriptor is allocated and
 * becomes the head of the list.  This means that by definitions, all tail
 * descriptors are full.
 *
 * Note, the meta data fields are deliberately placed at the start of the
 * structure to optimize the cacheline layout; accessing the descriptor will
 * touch only a single cacheline so long as @spte_count<=6 (or if only the
 * descriptors metadata is accessed).
 */
struct pte_list_desc {
 struct pte_list_desc *more;
 /* The number of PTEs stored in _this_ descriptor. */
 u32 spte_count;
 /* The number of PTEs stored in all tails of this descriptor. */
 u32 tail_count;
 u64 *sptes[PTE_LIST_EXT];
};

struct kvm_shadow_walk_iterator {
 u64 addr;
 hpa_t shadow_addr;
 u64 *sptep;
 int level;
 unsigned index;
};

#define for_each_shadow_entry_using_root(_vcpu, _root, _addr, _walker)     \
 for (shadow_walk_init_using_root(&(_walker), (_vcpu),              \
      (_root), (_addr));                \
      shadow_walk_okay(&(_walker));              \
      shadow_walk_next(&(_walker)))

#define for_each_shadow_entry(_vcpu, _addr, _walker)            \
 for (shadow_walk_init(&(_walker), _vcpu, _addr); \
      shadow_walk_okay(&(_walker));   \
      shadow_walk_next(&(_walker)))

#define for_each_shadow_entry_lockless(_vcpu, _addr, _walker, spte) \
 for (shadow_walk_init(&(_walker), _vcpu, _addr);  \
      shadow_walk_okay(&(_walker)) &&    \
  ({ spte = mmu_spte_get_lockless(_walker.sptep); 1; }); \
      __shadow_walk_next(&(_walker), spte))

static struct kmem_cache *pte_list_desc_cache;
struct kmem_cache *mmu_page_header_cache;

static void mmu_spte_set(u64 *sptep, u64 spte);

struct kvm_mmu_role_regs {
 const unsigned long cr0;
 const unsigned long cr4;
 const u64 efer;
};

#define CREATE_TRACE_POINTS
#include "mmutrace.h"

/*
 * Yes, lot's of underscores.  They're a hint that you probably shouldn't be
 * reading from the role_regs.  Once the root_role is constructed, it becomes
 * the single source of truth for the MMU's state.
 */
#define BUILD_MMU_ROLE_REGS_ACCESSOR(reg, name, flag)   \
static inline bool __maybe_unused     \
____is_##reg##_##name(const struct kvm_mmu_role_regs *regs)  \
{         \
 return !!(regs->reg & flag);     \
}
BUILD_MMU_ROLE_REGS_ACCESSOR(cr0, pg, X86_CR0_PG);
BUILD_MMU_ROLE_REGS_ACCESSOR(cr0, wp, X86_CR0_WP);
BUILD_MMU_ROLE_REGS_ACCESSOR(cr4, pse, X86_CR4_PSE);
BUILD_MMU_ROLE_REGS_ACCESSOR(cr4, pae, X86_CR4_PAE);
BUILD_MMU_ROLE_REGS_ACCESSOR(cr4, smep, X86_CR4_SMEP);
BUILD_MMU_ROLE_REGS_ACCESSOR(cr4, smap, X86_CR4_SMAP);
BUILD_MMU_ROLE_REGS_ACCESSOR(cr4, pke, X86_CR4_PKE);
BUILD_MMU_ROLE_REGS_ACCESSOR(cr4, la57, X86_CR4_LA57);
BUILD_MMU_ROLE_REGS_ACCESSOR(efer, nx, EFER_NX);
BUILD_MMU_ROLE_REGS_ACCESSOR(efer, lma, EFER_LMA);

/*
 * The MMU itself (with a valid role) is the single source of truth for the
 * MMU.  Do not use the regs used to build the MMU/role, nor the vCPU.  The
 * regs don't account for dependencies, e.g. clearing CR4 bits if CR0.PG=1,
 * and the vCPU may be incorrect/irrelevant.
 */
#define BUILD_MMU_ROLE_ACCESSOR(base_or_ext, reg, name)  \
static inline bool __maybe_unused is_##reg##_##name(struct kvm_mmu *mmu) \
{        \
 return !!(mmu->cpu_role. base_or_ext . reg##_##name); \
}
BUILD_MMU_ROLE_ACCESSOR(base, cr0, wp);
BUILD_MMU_ROLE_ACCESSOR(ext,  cr4, pse);
BUILD_MMU_ROLE_ACCESSOR(ext,  cr4, smep);
BUILD_MMU_ROLE_ACCESSOR(ext,  cr4, smap);
BUILD_MMU_ROLE_ACCESSOR(ext,  cr4, pke);
BUILD_MMU_ROLE_ACCESSOR(ext,  cr4, la57);
BUILD_MMU_ROLE_ACCESSOR(base, efer, nx);
BUILD_MMU_ROLE_ACCESSOR(ext,  efer, lma);

static inline bool is_cr0_pg(struct kvm_mmu *mmu)
{
        return mmu->cpu_role.base.level > 0;
}

static inline bool is_cr4_pae(struct kvm_mmu *mmu)
{
        return !mmu->cpu_role.base.has_4_byte_gpte;
}

static struct kvm_mmu_role_regs vcpu_to_role_regs(struct kvm_vcpu *vcpu)
{
 struct kvm_mmu_role_regs regs = {
  .cr0 = kvm_read_cr0_bits(vcpu, KVM_MMU_CR0_ROLE_BITS),
  .cr4 = kvm_read_cr4_bits(vcpu, KVM_MMU_CR4_ROLE_BITS),
  .efer = vcpu->arch.efer,
 };

 return regs;
}

static unsigned long get_guest_cr3(struct kvm_vcpu *vcpu)
{
 return kvm_read_cr3(vcpu);
}

static inline unsigned long kvm_mmu_get_guest_pgd(struct kvm_vcpu *vcpu,
        struct kvm_mmu *mmu)
{
 if (IS_ENABLED(CONFIG_MITIGATION_RETPOLINE) && mmu->get_guest_pgd == get_guest_cr3)
  return kvm_read_cr3(vcpu);

 return mmu->get_guest_pgd(vcpu);
}

static inline bool kvm_available_flush_remote_tlbs_range(void)
{
#if IS_ENABLED(CONFIG_HYPERV)
 return kvm_x86_ops.flush_remote_tlbs_range;
#else
 return false;
#endif
}

static gfn_t kvm_mmu_page_get_gfn(struct kvm_mmu_page *sp, int index);

/* Flush the range of guest memory mapped by the given SPTE. */
static void kvm_flush_remote_tlbs_sptep(struct kvm *kvm, u64 *sptep)
{
 struct kvm_mmu_page *sp = sptep_to_sp(sptep);
 gfn_t gfn = kvm_mmu_page_get_gfn(sp, spte_index(sptep));

 kvm_flush_remote_tlbs_gfn(kvm, gfn, sp->role.level);
}

static void mark_mmio_spte(struct kvm_vcpu *vcpu, u64 *sptep, u64 gfn,
      unsigned int access)
{
 u64 spte = make_mmio_spte(vcpu, gfn, access);

 trace_mark_mmio_spte(sptep, gfn, spte);
 mmu_spte_set(sptep, spte);
}

static gfn_t get_mmio_spte_gfn(u64 spte)
{
 u64 gpa = spte & shadow_nonpresent_or_rsvd_lower_gfn_mask;

 gpa |= (spte >> SHADOW_NONPRESENT_OR_RSVD_MASK_LEN)
        & shadow_nonpresent_or_rsvd_mask;

 return gpa >> PAGE_SHIFT;
}

static unsigned get_mmio_spte_access(u64 spte)
{
 return spte & shadow_mmio_access_mask;
}

static bool check_mmio_spte(struct kvm_vcpu *vcpu, u64 spte)
{
 u64 kvm_gen, spte_gen, gen;

 gen = kvm_vcpu_memslots(vcpu)->generation;
 if (unlikely(gen & KVM_MEMSLOT_GEN_UPDATE_IN_PROGRESS))
  return false;

 kvm_gen = gen & MMIO_SPTE_GEN_MASK;
 spte_gen = get_mmio_spte_generation(spte);

 trace_check_mmio_spte(spte, kvm_gen, spte_gen);
 return likely(kvm_gen == spte_gen);
}

static int is_cpuid_PSE36(void)
{
 return 1;
}

#ifdef CONFIG_X86_64
static void __set_spte(u64 *sptep, u64 spte)
{
 KVM_MMU_WARN_ON(is_ept_ve_possible(spte));
 WRITE_ONCE(*sptep, spte);
}

static void __update_clear_spte_fast(u64 *sptep, u64 spte)
{
 KVM_MMU_WARN_ON(is_ept_ve_possible(spte));
 WRITE_ONCE(*sptep, spte);
}

static u64 __update_clear_spte_slow(u64 *sptep, u64 spte)
{
 KVM_MMU_WARN_ON(is_ept_ve_possible(spte));
 return xchg(sptep, spte);
}

static u64 __get_spte_lockless(u64 *sptep)
{
 return READ_ONCE(*sptep);
}
#else
union split_spte {
 struct {
  u32 spte_low;
  u32 spte_high;
 };
 u64 spte;
};

static void count_spte_clear(u64 *sptep, u64 spte)
{
 struct kvm_mmu_page *sp =  sptep_to_sp(sptep);

 if (is_shadow_present_pte(spte))
  return;

 /* Ensure the spte is completely set before we increase the count */
 smp_wmb();
 sp->clear_spte_count++;
}

static void __set_spte(u64 *sptep, u64 spte)
{
 union split_spte *ssptep, sspte;

 ssptep = (union split_spte *)sptep;
 sspte = (union split_spte)spte;

 ssptep->spte_high = sspte.spte_high;

 /*
 * If we map the spte from nonpresent to present, We should store
 * the high bits firstly, then set present bit, so cpu can not
 * fetch this spte while we are setting the spte.
 */
 smp_wmb();

 WRITE_ONCE(ssptep->spte_low, sspte.spte_low);
}

static void __update_clear_spte_fast(u64 *sptep, u64 spte)
{
 union split_spte *ssptep, sspte;

 ssptep = (union split_spte *)sptep;
 sspte = (union split_spte)spte;

 WRITE_ONCE(ssptep->spte_low, sspte.spte_low);

 /*
 * If we map the spte from present to nonpresent, we should clear
 * present bit firstly to avoid vcpu fetch the old high bits.
 */
 smp_wmb();

 ssptep->spte_high = sspte.spte_high;
 count_spte_clear(sptep, spte);
}

static u64 __update_clear_spte_slow(u64 *sptep, u64 spte)
{
 union split_spte *ssptep, sspte, orig;

 ssptep = (union split_spte *)sptep;
 sspte = (union split_spte)spte;

 /* xchg acts as a barrier before the setting of the high bits */
 orig.spte_low = xchg(&ssptep->spte_low, sspte.spte_low);
 orig.spte_high = ssptep->spte_high;
 ssptep->spte_high = sspte.spte_high;
 count_spte_clear(sptep, spte);

 return orig.spte;
}

/*
 * The idea using the light way get the spte on x86_32 guest is from
 * gup_get_pte (mm/gup.c).
 *
 * An spte tlb flush may be pending, because they are coalesced and
 * we are running out of the MMU lock.  Therefore
 * we need to protect against in-progress updates of the spte.
 *
 * Reading the spte while an update is in progress may get the old value
 * for the high part of the spte.  The race is fine for a present->non-present
 * change (because the high part of the spte is ignored for non-present spte),
 * but for a present->present change we must reread the spte.
 *
 * All such changes are done in two steps (present->non-present and
 * non-present->present), hence it is enough to count the number of
 * present->non-present updates: if it changed while reading the spte,
 * we might have hit the race.  This is done using clear_spte_count.
 */
static u64 __get_spte_lockless(u64 *sptep)
{
 struct kvm_mmu_page *sp =  sptep_to_sp(sptep);
 union split_spte spte, *orig = (union split_spte *)sptep;
 int count;

retry:
 count = sp->clear_spte_count;
 smp_rmb();

 spte.spte_low = orig->spte_low;
 smp_rmb();

 spte.spte_high = orig->spte_high;
 smp_rmb();

 if (unlikely(spte.spte_low != orig->spte_low ||
       count != sp->clear_spte_count))
  goto retry;

 return spte.spte;
}
#endif

/* Rules for using mmu_spte_set:
 * Set the sptep from nonpresent to present.
 * Note: the sptep being assigned *must* be either not present
 * or in a state where the hardware will not attempt to update
 * the spte.
 */
static void mmu_spte_set(u64 *sptep, u64 new_spte)
{
 WARN_ON_ONCE(is_shadow_present_pte(*sptep));
 __set_spte(sptep, new_spte);
}

/* Rules for using mmu_spte_update:
 * Update the state bits, it means the mapped pfn is not changed.
 *
 * Returns true if the TLB needs to be flushed
 */
static bool mmu_spte_update(u64 *sptep, u64 new_spte)
{
 u64 old_spte = *sptep;

 WARN_ON_ONCE(!is_shadow_present_pte(new_spte));
 check_spte_writable_invariants(new_spte);

 if (!is_shadow_present_pte(old_spte)) {
  mmu_spte_set(sptep, new_spte);
  return false;
 }

 if (!spte_needs_atomic_update(old_spte))
  __update_clear_spte_fast(sptep, new_spte);
 else
  old_spte = __update_clear_spte_slow(sptep, new_spte);

 WARN_ON_ONCE(!is_shadow_present_pte(old_spte) ||
       spte_to_pfn(old_spte) != spte_to_pfn(new_spte));

 return leaf_spte_change_needs_tlb_flush(old_spte, new_spte);
}

/*
 * Rules for using mmu_spte_clear_track_bits:
 * It sets the sptep from present to nonpresent, and track the
 * state bits, it is used to clear the last level sptep.
 * Returns the old PTE.
 */
static u64 mmu_spte_clear_track_bits(struct kvm *kvm, u64 *sptep)
{
 u64 old_spte = *sptep;
 int level = sptep_to_sp(sptep)->role.level;

 if (!is_shadow_present_pte(old_spte) ||
     !spte_needs_atomic_update(old_spte))
  __update_clear_spte_fast(sptep, SHADOW_NONPRESENT_VALUE);
 else
  old_spte = __update_clear_spte_slow(sptep, SHADOW_NONPRESENT_VALUE);

 if (!is_shadow_present_pte(old_spte))
  return old_spte;

 kvm_update_page_stats(kvm, level, -1);
 return old_spte;
}

/*
 * Rules for using mmu_spte_clear_no_track:
 * Directly clear spte without caring the state bits of sptep,
 * it is used to set the upper level spte.
 */
static void mmu_spte_clear_no_track(u64 *sptep)
{
 __update_clear_spte_fast(sptep, SHADOW_NONPRESENT_VALUE);
}

static u64 mmu_spte_get_lockless(u64 *sptep)
{
 return __get_spte_lockless(sptep);
}

static inline bool is_tdp_mmu_active(struct kvm_vcpu *vcpu)
{
 return tdp_mmu_enabled && vcpu->arch.mmu->root_role.direct;
}

static void walk_shadow_page_lockless_begin(struct kvm_vcpu *vcpu)
{
 if (is_tdp_mmu_active(vcpu)) {
  kvm_tdp_mmu_walk_lockless_begin();
 } else {
  /*
 * Prevent page table teardown by making any free-er wait during
 * kvm_flush_remote_tlbs() IPI to all active vcpus.
 */
  local_irq_disable();

  /*
 * Make sure a following spte read is not reordered ahead of the write
 * to vcpu->mode.
 */
  smp_store_mb(vcpu->mode, READING_SHADOW_PAGE_TABLES);
 }
}

static void walk_shadow_page_lockless_end(struct kvm_vcpu *vcpu)
{
 if (is_tdp_mmu_active(vcpu)) {
  kvm_tdp_mmu_walk_lockless_end();
 } else {
  /*
 * Make sure the write to vcpu->mode is not reordered in front of
 * reads to sptes.  If it does, kvm_mmu_commit_zap_page() can see us
 * OUTSIDE_GUEST_MODE and proceed to free the shadow page table.
 */
  smp_store_release(&vcpu->mode, OUTSIDE_GUEST_MODE);
  local_irq_enable();
 }
}

static int mmu_topup_memory_caches(struct kvm_vcpu *vcpu, bool maybe_indirect)
{
 int r;

 /* 1 rmap, 1 parent PTE per level, and the prefetched rmaps. */
 r = kvm_mmu_topup_memory_cache(&vcpu->arch.mmu_pte_list_desc_cache,
           1 + PT64_ROOT_MAX_LEVEL + PTE_PREFETCH_NUM);
 if (r)
  return r;
 if (kvm_has_mirrored_tdp(vcpu->kvm)) {
  r = kvm_mmu_topup_memory_cache(&vcpu->arch.mmu_external_spt_cache,
            PT64_ROOT_MAX_LEVEL);
  if (r)
   return r;
 }
 r = kvm_mmu_topup_memory_cache(&vcpu->arch.mmu_shadow_page_cache,
           PT64_ROOT_MAX_LEVEL);
 if (r)
  return r;
 if (maybe_indirect) {
  r = kvm_mmu_topup_memory_cache(&vcpu->arch.mmu_shadowed_info_cache,
            PT64_ROOT_MAX_LEVEL);
  if (r)
   return r;
 }
 return kvm_mmu_topup_memory_cache(&vcpu->arch.mmu_page_header_cache,
       PT64_ROOT_MAX_LEVEL);
}

static void mmu_free_memory_caches(struct kvm_vcpu *vcpu)
{
 kvm_mmu_free_memory_cache(&vcpu->arch.mmu_pte_list_desc_cache);
 kvm_mmu_free_memory_cache(&vcpu->arch.mmu_shadow_page_cache);
 kvm_mmu_free_memory_cache(&vcpu->arch.mmu_shadowed_info_cache);
 kvm_mmu_free_memory_cache(&vcpu->arch.mmu_external_spt_cache);
 kvm_mmu_free_memory_cache(&vcpu->arch.mmu_page_header_cache);
}

static void mmu_free_pte_list_desc(struct pte_list_desc *pte_list_desc)
{
 kmem_cache_free(pte_list_desc_cache, pte_list_desc);
}

static bool sp_has_gptes(struct kvm_mmu_page *sp);

static gfn_t kvm_mmu_page_get_gfn(struct kvm_mmu_page *sp, int index)
{
 if (sp->role.passthrough)
  return sp->gfn;

 if (sp->shadowed_translation)
  return sp->shadowed_translation[index] >> PAGE_SHIFT;

 return sp->gfn + (index << ((sp->role.level - 1) * SPTE_LEVEL_BITS));
}

/*
 * For leaf SPTEs, fetch the *guest* access permissions being shadowed. Note
 * that the SPTE itself may have a more constrained access permissions that
 * what the guest enforces. For example, a guest may create an executable
 * huge PTE but KVM may disallow execution to mitigate iTLB multihit.
 */
static u32 kvm_mmu_page_get_access(struct kvm_mmu_page *sp, int index)
{
 if (sp->shadowed_translation)
  return sp->shadowed_translation[index] & ACC_ALL;

 /*
 * For direct MMUs (e.g. TDP or non-paging guests) or passthrough SPs,
 * KVM is not shadowing any guest page tables, so the "guest access
 * permissions" are just ACC_ALL.
 *
 * For direct SPs in indirect MMUs (shadow paging), i.e. when KVM
 * is shadowing a guest huge page with small pages, the guest access
 * permissions being shadowed are the access permissions of the huge
 * page.
 *
 * In both cases, sp->role.access contains the correct access bits.
 */
 return sp->role.access;
}

static void kvm_mmu_page_set_translation(struct kvm_mmu_page *sp, int index,
      gfn_t gfn, unsigned int access)
{
 if (sp->shadowed_translation) {
  sp->shadowed_translation[index] = (gfn << PAGE_SHIFT) | access;
  return;
 }

 WARN_ONCE(access != kvm_mmu_page_get_access(sp, index),
           "access mismatch under %s page %llx (expected %u, got %u)\n",
           sp->role.passthrough ? "passthrough" : "direct",
           sp->gfn, kvm_mmu_page_get_access(sp, index), access);

 WARN_ONCE(gfn != kvm_mmu_page_get_gfn(sp, index),
           "gfn mismatch under %s page %llx (expected %llx, got %llx)\n",
           sp->role.passthrough ? "passthrough" : "direct",
           sp->gfn, kvm_mmu_page_get_gfn(sp, index), gfn);
}

static void kvm_mmu_page_set_access(struct kvm_mmu_page *sp, int index,
        unsigned int access)
{
 gfn_t gfn = kvm_mmu_page_get_gfn(sp, index);

 kvm_mmu_page_set_translation(sp, index, gfn, access);
}

/*
 * Return the pointer to the large page information for a given gfn,
 * handling slots that are not large page aligned.
 */
static struct kvm_lpage_info *lpage_info_slot(gfn_t gfn,
  const struct kvm_memory_slot *slot, int level)
{
 unsigned long idx;

 idx = gfn_to_index(gfn, slot->base_gfn, level);
 return &slot->arch.lpage_info[level - 2][idx];
}

/*
 * The most significant bit in disallow_lpage tracks whether or not memory
 * attributes are mixed, i.e. not identical for all gfns at the current level.
 * The lower order bits are used to refcount other cases where a hugepage is
 * disallowed, e.g. if KVM has shadow a page table at the gfn.
 */
#define KVM_LPAGE_MIXED_FLAG BIT(31)

static void update_gfn_disallow_lpage_count(const struct kvm_memory_slot *slot,
         gfn_t gfn, int count)
{
 struct kvm_lpage_info *linfo;
 int old, i;

 for (i = PG_LEVEL_2M; i <= KVM_MAX_HUGEPAGE_LEVEL; ++i) {
  linfo = lpage_info_slot(gfn, slot, i);

  old = linfo->disallow_lpage;
  linfo->disallow_lpage += count;
  WARN_ON_ONCE((old ^ linfo->disallow_lpage) & KVM_LPAGE_MIXED_FLAG);
 }
}

void kvm_mmu_gfn_disallow_lpage(const struct kvm_memory_slot *slot, gfn_t gfn)
{
 update_gfn_disallow_lpage_count(slot, gfn, 1);
}

void kvm_mmu_gfn_allow_lpage(const struct kvm_memory_slot *slot, gfn_t gfn)
{
 update_gfn_disallow_lpage_count(slot, gfn, -1);
}

static void account_shadowed(struct kvm *kvm, struct kvm_mmu_page *sp)
{
 struct kvm_memslots *slots;
 struct kvm_memory_slot *slot;
 gfn_t gfn;

 kvm->arch.indirect_shadow_pages++;
 /*
 * Ensure indirect_shadow_pages is elevated prior to re-reading guest
 * child PTEs in FNAME(gpte_changed), i.e. guarantee either in-flight
 * emulated writes are visible before re-reading guest PTEs, or that
 * an emulated write will see the elevated count and acquire mmu_lock
 * to update SPTEs.  Pairs with the smp_mb() in kvm_mmu_track_write().
 */
 smp_mb();

 gfn = sp->gfn;
 slots = kvm_memslots_for_spte_role(kvm, sp->role);
 slot = __gfn_to_memslot(slots, gfn);

 /* the non-leaf shadow pages are keeping readonly. */
 if (sp->role.level > PG_LEVEL_4K)
  return __kvm_write_track_add_gfn(kvm, slot, gfn);

 kvm_mmu_gfn_disallow_lpage(slot, gfn);

 if (kvm_mmu_slot_gfn_write_protect(kvm, slot, gfn, PG_LEVEL_4K))
  kvm_flush_remote_tlbs_gfn(kvm, gfn, PG_LEVEL_4K);
}

void track_possible_nx_huge_page(struct kvm *kvm, struct kvm_mmu_page *sp)
{
 /*
 * If it's possible to replace the shadow page with an NX huge page,
 * i.e. if the shadow page is the only thing currently preventing KVM
 * from using a huge page, add the shadow page to the list of "to be
 * zapped for NX recovery" pages.  Note, the shadow page can already be
 * on the list if KVM is reusing an existing shadow page, i.e. if KVM
 * links a shadow page at multiple points.
 */
 if (!list_empty(&sp->possible_nx_huge_page_link))
  return;

 ++kvm->stat.nx_lpage_splits;
 list_add_tail(&sp->possible_nx_huge_page_link,
        &kvm->arch.possible_nx_huge_pages);
}

static void account_nx_huge_page(struct kvm *kvm, struct kvm_mmu_page *sp,
     bool nx_huge_page_possible)
{
 sp->nx_huge_page_disallowed = true;

 if (nx_huge_page_possible)
  track_possible_nx_huge_page(kvm, sp);
}

static void unaccount_shadowed(struct kvm *kvm, struct kvm_mmu_page *sp)
{
 struct kvm_memslots *slots;
 struct kvm_memory_slot *slot;
 gfn_t gfn;

 kvm->arch.indirect_shadow_pages--;
 gfn = sp->gfn;
 slots = kvm_memslots_for_spte_role(kvm, sp->role);
 slot = __gfn_to_memslot(slots, gfn);
 if (sp->role.level > PG_LEVEL_4K)
  return __kvm_write_track_remove_gfn(kvm, slot, gfn);

 kvm_mmu_gfn_allow_lpage(slot, gfn);
}

void untrack_possible_nx_huge_page(struct kvm *kvm, struct kvm_mmu_page *sp)
{
 if (list_empty(&sp->possible_nx_huge_page_link))
  return;

 --kvm->stat.nx_lpage_splits;
 list_del_init(&sp->possible_nx_huge_page_link);
}

static void unaccount_nx_huge_page(struct kvm *kvm, struct kvm_mmu_page *sp)
{
 sp->nx_huge_page_disallowed = false;

 untrack_possible_nx_huge_page(kvm, sp);
}

static struct kvm_memory_slot *gfn_to_memslot_dirty_bitmap(struct kvm_vcpu *vcpu,
          gfn_t gfn,
          bool no_dirty_log)
{
 struct kvm_memory_slot *slot;

 slot = kvm_vcpu_gfn_to_memslot(vcpu, gfn);
 if (!slot || slot->flags & KVM_MEMSLOT_INVALID)
  return NULL;
 if (no_dirty_log && kvm_slot_dirty_track_enabled(slot))
  return NULL;

 return slot;
}

/*
 * About rmap_head encoding:
 *
 * If the bit zero of rmap_head->val is clear, then it points to the only spte
 * in this rmap chain. Otherwise, (rmap_head->val & ~3) points to a struct
 * pte_list_desc containing more mappings.
 */
#define KVM_RMAP_MANY BIT(0)

/*
 * rmaps and PTE lists are mostly protected by mmu_lock (the shadow MMU always
 * operates with mmu_lock held for write), but rmaps can be walked without
 * holding mmu_lock so long as the caller can tolerate SPTEs in the rmap chain
 * being zapped/dropped _while the rmap is locked_.
 *
 * Other than the KVM_RMAP_LOCKED flag, modifications to rmap entries must be
 * done while holding mmu_lock for write.  This allows a task walking rmaps
 * without holding mmu_lock to concurrently walk the same entries as a task
 * that is holding mmu_lock but _not_ the rmap lock.  Neither task will modify
 * the rmaps, thus the walks are stable.
 *
 * As alluded to above, SPTEs in rmaps are _not_ protected by KVM_RMAP_LOCKED,
 * only the rmap chains themselves are protected.  E.g. holding an rmap's lock
 * ensures all "struct pte_list_desc" fields are stable.
 */
#define KVM_RMAP_LOCKED BIT(1)

static unsigned long __kvm_rmap_lock(struct kvm_rmap_head *rmap_head)
{
 unsigned long old_val, new_val;

 lockdep_assert_preemption_disabled();

 /*
 * Elide the lock if the rmap is empty, as lockless walkers (read-only
 * mode) don't need to (and can't) walk an empty rmap, nor can they add
 * entries to the rmap.  I.e. the only paths that process empty rmaps
 * do so while holding mmu_lock for write, and are mutually exclusive.
 */
 old_val = atomic_long_read(&rmap_head->val);
 if (!old_val)
  return 0;

 do {
  /*
 * If the rmap is locked, wait for it to be unlocked before
 * trying acquire the lock, e.g. to avoid bouncing the cache
 * line.
 */
  while (old_val & KVM_RMAP_LOCKED) {
   cpu_relax();
   old_val = atomic_long_read(&rmap_head->val);
  }

  /*
 * Recheck for an empty rmap, it may have been purged by the
 * task that held the lock.
 */
  if (!old_val)
   return 0;

  new_val = old_val | KVM_RMAP_LOCKED;
 /*
 * Use try_cmpxchg_acquire() to prevent reads and writes to the rmap
 * from being reordered outside of the critical section created by
 * __kvm_rmap_lock().
 *
 * Pairs with the atomic_long_set_release() in kvm_rmap_unlock().
 *
 * For the !old_val case, no ordering is needed, as there is no rmap
 * to walk.
 */
 } while (!atomic_long_try_cmpxchg_acquire(&rmap_head->val, &old_val, new_val));

 /*
 * Return the old value, i.e. _without_ the LOCKED bit set.  It's
 * impossible for the return value to be 0 (see above), i.e. the read-
 * only unlock flow can't get a false positive and fail to unlock.
 */
 return old_val;
}

static unsigned long kvm_rmap_lock(struct kvm *kvm,
       struct kvm_rmap_head *rmap_head)
{
 lockdep_assert_held_write(&kvm->mmu_lock);

 return __kvm_rmap_lock(rmap_head);
}

static void __kvm_rmap_unlock(struct kvm_rmap_head *rmap_head,
         unsigned long val)
{
 KVM_MMU_WARN_ON(val & KVM_RMAP_LOCKED);
 /*
 * Ensure that all accesses to the rmap have completed before unlocking
 * the rmap.
 *
 * Pairs with the atomic_long_try_cmpxchg_acquire() in __kvm_rmap_lock().
 */
 atomic_long_set_release(&rmap_head->val, val);
}

static void kvm_rmap_unlock(struct kvm *kvm,
       struct kvm_rmap_head *rmap_head,
       unsigned long new_val)
{
 lockdep_assert_held_write(&kvm->mmu_lock);

 __kvm_rmap_unlock(rmap_head, new_val);
}

static unsigned long kvm_rmap_get(struct kvm_rmap_head *rmap_head)
{
 return atomic_long_read(&rmap_head->val) & ~KVM_RMAP_LOCKED;
}

/*
 * If mmu_lock isn't held, rmaps can only be locked in read-only mode.  The
 * actual locking is the same, but the caller is disallowed from modifying the
 * rmap, and so the unlock flow is a nop if the rmap is/was empty.
 */
static unsigned long kvm_rmap_lock_readonly(struct kvm_rmap_head *rmap_head)
{
 unsigned long rmap_val;

 preempt_disable();
 rmap_val = __kvm_rmap_lock(rmap_head);

 if (!rmap_val)
  preempt_enable();

 return rmap_val;
}

static void kvm_rmap_unlock_readonly(struct kvm_rmap_head *rmap_head,
         unsigned long old_val)
{
 if (!old_val)
  return;

 KVM_MMU_WARN_ON(old_val != kvm_rmap_get(rmap_head));

 __kvm_rmap_unlock(rmap_head, old_val);
 preempt_enable();
}

/*
 * Returns the number of pointers in the rmap chain, not counting the new one.
 */
static int pte_list_add(struct kvm *kvm, struct kvm_mmu_memory_cache *cache,
   u64 *spte, struct kvm_rmap_head *rmap_head)
{
 unsigned long old_val, new_val;
 struct pte_list_desc *desc;
 int count = 0;

 old_val = kvm_rmap_lock(kvm, rmap_head);

 if (!old_val) {
  new_val = (unsigned long)spte;
 } else if (!(old_val & KVM_RMAP_MANY)) {
  desc = kvm_mmu_memory_cache_alloc(cache);
  desc->sptes[0] = (u64 *)old_val;
  desc->sptes[1] = spte;
  desc->spte_count = 2;
  desc->tail_count = 0;
  new_val = (unsigned long)desc | KVM_RMAP_MANY;
  ++count;
 } else {
  desc = (struct pte_list_desc *)(old_val & ~KVM_RMAP_MANY);
  count = desc->tail_count + desc->spte_count;

  /*
 * If the previous head is full, allocate a new head descriptor
 * as tail descriptors are always kept full.
 */
  if (desc->spte_count == PTE_LIST_EXT) {
   desc = kvm_mmu_memory_cache_alloc(cache);
   desc->more = (struct pte_list_desc *)(old_val & ~KVM_RMAP_MANY);
   desc->spte_count = 0;
   desc->tail_count = count;
   new_val = (unsigned long)desc | KVM_RMAP_MANY;
  } else {
   new_val = old_val;
  }
  desc->sptes[desc->spte_count++] = spte;
 }

 kvm_rmap_unlock(kvm, rmap_head, new_val);

 return count;
}

static void pte_list_desc_remove_entry(struct kvm *kvm, unsigned long *rmap_val,
           struct pte_list_desc *desc, int i)
{
 struct pte_list_desc *head_desc = (struct pte_list_desc *)(*rmap_val & ~KVM_RMAP_MANY);
 int j = head_desc->spte_count - 1;

 /*
 * The head descriptor should never be empty.  A new head is added only
 * when adding an entry and the previous head is full, and heads are
 * removed (this flow) when they become empty.
 */
 KVM_BUG_ON_DATA_CORRUPTION(j < 0, kvm);

 /*
 * Replace the to-be-freed SPTE with the last valid entry from the head
 * descriptor to ensure that tail descriptors are full at all times.
 * Note, this also means that tail_count is stable for each descriptor.
 */
 desc->sptes[i] = head_desc->sptes[j];
 head_desc->sptes[j] = NULL;
 head_desc->spte_count--;
 if (head_desc->spte_count)
  return;

 /*
 * The head descriptor is empty.  If there are no tail descriptors,
 * nullify the rmap head to mark the list as empty, else point the rmap
 * head at the next descriptor, i.e. the new head.
 */
 if (!head_desc->more)
  *rmap_val = 0;
 else
  *rmap_val = (unsigned long)head_desc->more | KVM_RMAP_MANY;
 mmu_free_pte_list_desc(head_desc);
}

static void pte_list_remove(struct kvm *kvm, u64 *spte,
       struct kvm_rmap_head *rmap_head)
{
 struct pte_list_desc *desc;
 unsigned long rmap_val;
 int i;

 rmap_val = kvm_rmap_lock(kvm, rmap_head);
 if (KVM_BUG_ON_DATA_CORRUPTION(!rmap_val, kvm))
  goto out;

 if (!(rmap_val & KVM_RMAP_MANY)) {
  if (KVM_BUG_ON_DATA_CORRUPTION((u64 *)rmap_val != spte, kvm))
   goto out;

  rmap_val = 0;
 } else {
  desc = (struct pte_list_desc *)(rmap_val & ~KVM_RMAP_MANY);
  while (desc) {
   for (i = 0; i < desc->spte_count; ++i) {
    if (desc->sptes[i] == spte) {
     pte_list_desc_remove_entry(kvm, &rmap_val,
           desc, i);
     goto out;
    }
   }
   desc = desc->more;
  }

  KVM_BUG_ON_DATA_CORRUPTION(true, kvm);
 }

out:
 kvm_rmap_unlock(kvm, rmap_head, rmap_val);
}

static void kvm_zap_one_rmap_spte(struct kvm *kvm,
      struct kvm_rmap_head *rmap_head, u64 *sptep)
{
 mmu_spte_clear_track_bits(kvm, sptep);
 pte_list_remove(kvm, sptep, rmap_head);
}

/* Return true if at least one SPTE was zapped, false otherwise */
static bool kvm_zap_all_rmap_sptes(struct kvm *kvm,
       struct kvm_rmap_head *rmap_head)
{
 struct pte_list_desc *desc, *next;
 unsigned long rmap_val;
 int i;

 rmap_val = kvm_rmap_lock(kvm, rmap_head);
 if (!rmap_val)
  return false;

 if (!(rmap_val & KVM_RMAP_MANY)) {
  mmu_spte_clear_track_bits(kvm, (u64 *)rmap_val);
  goto out;
 }

 desc = (struct pte_list_desc *)(rmap_val & ~KVM_RMAP_MANY);

 for (; desc; desc = next) {
  for (i = 0; i < desc->spte_count; i++)
   mmu_spte_clear_track_bits(kvm, desc->sptes[i]);
  next = desc->more;
  mmu_free_pte_list_desc(desc);
 }
out:
 /* rmap_head is meaningless now, remember to reset it */
 kvm_rmap_unlock(kvm, rmap_head, 0);
 return true;
}

unsigned int pte_list_count(struct kvm_rmap_head *rmap_head)
{
 unsigned long rmap_val = kvm_rmap_get(rmap_head);
 struct pte_list_desc *desc;

 if (!rmap_val)
  return 0;
 else if (!(rmap_val & KVM_RMAP_MANY))
  return 1;

 desc = (struct pte_list_desc *)(rmap_val & ~KVM_RMAP_MANY);
 return desc->tail_count + desc->spte_count;
}

static struct kvm_rmap_head *gfn_to_rmap(gfn_t gfn, int level,
      const struct kvm_memory_slot *slot)
{
 unsigned long idx;

 idx = gfn_to_index(gfn, slot->base_gfn, level);
 return &slot->arch.rmap[level - PG_LEVEL_4K][idx];
}

static void rmap_remove(struct kvm *kvm, u64 *spte)
{
 struct kvm_memslots *slots;
 struct kvm_memory_slot *slot;
 struct kvm_mmu_page *sp;
 gfn_t gfn;
 struct kvm_rmap_head *rmap_head;

 sp = sptep_to_sp(spte);
 gfn = kvm_mmu_page_get_gfn(sp, spte_index(spte));

 /*
 * Unlike rmap_add, rmap_remove does not run in the context of a vCPU
 * so we have to determine which memslots to use based on context
 * information in sp->role.
 */
 slots = kvm_memslots_for_spte_role(kvm, sp->role);

 slot = __gfn_to_memslot(slots, gfn);
 rmap_head = gfn_to_rmap(gfn, sp->role.level, slot);

 pte_list_remove(kvm, spte, rmap_head);
}

/*
 * Used by the following functions to iterate through the sptes linked by a
 * rmap.  All fields are private and not assumed to be used outside.
 */
struct rmap_iterator {
 /* private fields */
 struct rmap_head *head;
 struct pte_list_desc *desc; /* holds the sptep if not NULL */
 int pos;   /* index of the sptep */
};

/*
 * Iteration must be started by this function.  This should also be used after
 * removing/dropping sptes from the rmap link because in such cases the
 * information in the iterator may not be valid.
 *
 * Returns sptep if found, NULL otherwise.
 */
static u64 *rmap_get_first(struct kvm_rmap_head *rmap_head,
      struct rmap_iterator *iter)
{
 unsigned long rmap_val = kvm_rmap_get(rmap_head);

 if (!rmap_val)
  return NULL;

 if (!(rmap_val & KVM_RMAP_MANY)) {
  iter->desc = NULL;
  return (u64 *)rmap_val;
 }

 iter->desc = (struct pte_list_desc *)(rmap_val & ~KVM_RMAP_MANY);
 iter->pos = 0;
 return iter->desc->sptes[iter->pos];
}

/*
 * Must be used with a valid iterator: e.g. after rmap_get_first().
 *
 * Returns sptep if found, NULL otherwise.
 */
static u64 *rmap_get_next(struct rmap_iterator *iter)
{
 if (iter->desc) {
  if (iter->pos < PTE_LIST_EXT - 1) {
   ++iter->pos;
   if (iter->desc->sptes[iter->pos])
    return iter->desc->sptes[iter->pos];
  }

  iter->desc = iter->desc->more;

  if (iter->desc) {
   iter->pos = 0;
   /* desc->sptes[0] cannot be NULL */
   return iter->desc->sptes[iter->pos];
  }
 }

 return NULL;
}

#define __for_each_rmap_spte(_rmap_head_, _iter_, _sptep_) \
 for (_sptep_ = rmap_get_first(_rmap_head_, _iter_); \
      _sptep_; _sptep_ = rmap_get_next(_iter_))

#define for_each_rmap_spte(_rmap_head_, _iter_, _sptep_)   \
 __for_each_rmap_spte(_rmap_head_, _iter_, _sptep_)   \
  if (!WARN_ON_ONCE(!is_shadow_present_pte(*(_sptep_)))) \

#define for_each_rmap_spte_lockless(_rmap_head_, _iter_, _sptep_, _spte_) \
 __for_each_rmap_spte(_rmap_head_, _iter_, _sptep_)   \
  if (is_shadow_present_pte(_spte_ = mmu_spte_get_lockless(sptep)))

static void drop_spte(struct kvm *kvm, u64 *sptep)
{
 u64 old_spte = mmu_spte_clear_track_bits(kvm, sptep);

 if (is_shadow_present_pte(old_spte))
  rmap_remove(kvm, sptep);
}

static void drop_large_spte(struct kvm *kvm, u64 *sptep, bool flush)
{
 struct kvm_mmu_page *sp;

 sp = sptep_to_sp(sptep);
 WARN_ON_ONCE(sp->role.level == PG_LEVEL_4K);

 drop_spte(kvm, sptep);

 if (flush)
  kvm_flush_remote_tlbs_sptep(kvm, sptep);
}

/*
 * Write-protect on the specified @sptep, @pt_protect indicates whether
 * spte write-protection is caused by protecting shadow page table.
 *
 * Note: write protection is difference between dirty logging and spte
 * protection:
 * - for dirty logging, the spte can be set to writable at anytime if
 *   its dirty bitmap is properly set.
 * - for spte protection, the spte can be writable only after unsync-ing
 *   shadow page.
 *
 * Return true if tlb need be flushed.
 */
static bool spte_write_protect(u64 *sptep, bool pt_protect)
{
 u64 spte = *sptep;

 if (!is_writable_pte(spte) &&
     !(pt_protect && is_mmu_writable_spte(spte)))
  return false;

 if (pt_protect)
  spte &= ~shadow_mmu_writable_mask;
 spte = spte & ~PT_WRITABLE_MASK;

 return mmu_spte_update(sptep, spte);
}

static bool rmap_write_protect(struct kvm_rmap_head *rmap_head,
          bool pt_protect)
{
 u64 *sptep;
 struct rmap_iterator iter;
 bool flush = false;

 for_each_rmap_spte(rmap_head, &iter, sptep)
  flush |= spte_write_protect(sptep, pt_protect);

 return flush;
}

static bool spte_clear_dirty(u64 *sptep)
{
 u64 spte = *sptep;

 KVM_MMU_WARN_ON(!spte_ad_enabled(spte));
 spte &= ~shadow_dirty_mask;
 return mmu_spte_update(sptep, spte);
}

/*
 * Gets the GFN ready for another round of dirty logging by clearing the
 * - D bit on ad-enabled SPTEs, and
 * - W bit on ad-disabled SPTEs.
 * Returns true iff any D or W bits were cleared.
 */
static bool __rmap_clear_dirty(struct kvm *kvm, struct kvm_rmap_head *rmap_head,
          const struct kvm_memory_slot *slot)
{
 u64 *sptep;
 struct rmap_iterator iter;
 bool flush = false;

 for_each_rmap_spte(rmap_head, &iter, sptep) {
  if (spte_ad_need_write_protect(*sptep))
   flush |= test_and_clear_bit(PT_WRITABLE_SHIFT,
          (unsigned long *)sptep);
  else
   flush |= spte_clear_dirty(sptep);
 }

 return flush;
}

static void kvm_mmu_write_protect_pt_masked(struct kvm *kvm,
         struct kvm_memory_slot *slot,
         gfn_t gfn_offset, unsigned long mask)
{
 struct kvm_rmap_head *rmap_head;

 if (tdp_mmu_enabled)
  kvm_tdp_mmu_clear_dirty_pt_masked(kvm, slot,
    slot->base_gfn + gfn_offset, mask, true);

 if (!kvm_memslots_have_rmaps(kvm))
  return;

 while (mask) {
  rmap_head = gfn_to_rmap(slot->base_gfn + gfn_offset + __ffs(mask),
     PG_LEVEL_4K, slot);
  rmap_write_protect(rmap_head, false);

  /* clear the first set bit */
  mask &= mask - 1;
 }
}

static void kvm_mmu_clear_dirty_pt_masked(struct kvm *kvm,
      struct kvm_memory_slot *slot,
      gfn_t gfn_offset, unsigned long mask)
{
 struct kvm_rmap_head *rmap_head;

 if (tdp_mmu_enabled)
  kvm_tdp_mmu_clear_dirty_pt_masked(kvm, slot,
    slot->base_gfn + gfn_offset, mask, false);

 if (!kvm_memslots_have_rmaps(kvm))
  return;

 while (mask) {
  rmap_head = gfn_to_rmap(slot->base_gfn + gfn_offset + __ffs(mask),
     PG_LEVEL_4K, slot);
  __rmap_clear_dirty(kvm, rmap_head, slot);

  /* clear the first set bit */
  mask &= mask - 1;
 }
}

void kvm_arch_mmu_enable_log_dirty_pt_masked(struct kvm *kvm,
    struct kvm_memory_slot *slot,
    gfn_t gfn_offset, unsigned long mask)
{
 /*
 * If the slot was assumed to be "initially all dirty", write-protect
 * huge pages to ensure they are split to 4KiB on the first write (KVM
 * dirty logs at 4KiB granularity). If eager page splitting is enabled,
 * immediately try to split huge pages, e.g. so that vCPUs don't get
 * saddled with the cost of splitting.
 *
 * The gfn_offset is guaranteed to be aligned to 64, but the base_gfn
 * of memslot has no such restriction, so the range can cross two large
 * pages.
 */
 if (kvm_dirty_log_manual_protect_and_init_set(kvm)) {
  gfn_t start = slot->base_gfn + gfn_offset + __ffs(mask);
  gfn_t end = slot->base_gfn + gfn_offset + __fls(mask);

  if (READ_ONCE(eager_page_split))
   kvm_mmu_try_split_huge_pages(kvm, slot, start, end + 1, PG_LEVEL_4K);

  kvm_mmu_slot_gfn_write_protect(kvm, slot, start, PG_LEVEL_2M);

  /* Cross two large pages? */
  if (ALIGN(start << PAGE_SHIFT, PMD_SIZE) !=
      ALIGN(end << PAGE_SHIFT, PMD_SIZE))
   kvm_mmu_slot_gfn_write_protect(kvm, slot, end,
             PG_LEVEL_2M);
 }

 /*
 * (Re)Enable dirty logging for all 4KiB SPTEs that map the GFNs in
 * mask.  If PML is enabled and the GFN doesn't need to be write-
 * protected for other reasons, e.g. shadow paging, clear the Dirty bit.
 * Otherwise clear the Writable bit.
 *
 * Note that kvm_mmu_clear_dirty_pt_masked() is called whenever PML is
 * enabled but it chooses between clearing the Dirty bit and Writeable
 * bit based on the context.
 */
 if (kvm->arch.cpu_dirty_log_size)
  kvm_mmu_clear_dirty_pt_masked(kvm, slot, gfn_offset, mask);
 else
  kvm_mmu_write_protect_pt_masked(kvm, slot, gfn_offset, mask);
}

int kvm_cpu_dirty_log_size(struct kvm *kvm)
{
 return kvm->arch.cpu_dirty_log_size;
}

bool kvm_mmu_slot_gfn_write_protect(struct kvm *kvm,
        struct kvm_memory_slot *slot, u64 gfn,
        int min_level)
{
 struct kvm_rmap_head *rmap_head;
 int i;
 bool write_protected = false;

 if (kvm_memslots_have_rmaps(kvm)) {
  for (i = min_level; i <= KVM_MAX_HUGEPAGE_LEVEL; ++i) {
   rmap_head = gfn_to_rmap(gfn, i, slot);
   write_protected |= rmap_write_protect(rmap_head, true);
  }
 }

 if (tdp_mmu_enabled)
  write_protected |=
   kvm_tdp_mmu_write_protect_gfn(kvm, slot, gfn, min_level);

 return write_protected;
}

static bool kvm_vcpu_write_protect_gfn(struct kvm_vcpu *vcpu, u64 gfn)
{
 struct kvm_memory_slot *slot;

 slot = kvm_vcpu_gfn_to_memslot(vcpu, gfn);
 return kvm_mmu_slot_gfn_write_protect(vcpu->kvm, slot, gfn, PG_LEVEL_4K);
}

static bool kvm_zap_rmap(struct kvm *kvm, struct kvm_rmap_head *rmap_head,
    const struct kvm_memory_slot *slot)
{
 return kvm_zap_all_rmap_sptes(kvm, rmap_head);
}

struct slot_rmap_walk_iterator {
 /* input fields. */
 const struct kvm_memory_slot *slot;
 gfn_t start_gfn;
 gfn_t end_gfn;
 int start_level;
 int end_level;

 /* output fields. */
 gfn_t gfn;
 struct kvm_rmap_head *rmap;
 int level;

 /* private field. */
 struct kvm_rmap_head *end_rmap;
};

static void rmap_walk_init_level(struct slot_rmap_walk_iterator *iterator,
     int level)
{
 iterator->level = level;
 iterator->gfn = iterator->start_gfn;
 iterator->rmap = gfn_to_rmap(iterator->gfn, level, iterator->slot);
 iterator->end_rmap = gfn_to_rmap(iterator->end_gfn, level, iterator->slot);
}

static void slot_rmap_walk_init(struct slot_rmap_walk_iterator *iterator,
    const struct kvm_memory_slot *slot,
    int start_level, int end_level,
    gfn_t start_gfn, gfn_t end_gfn)
{
 iterator->slot = slot;
 iterator->start_level = start_level;
 iterator->end_level = end_level;
 iterator->start_gfn = start_gfn;
 iterator->end_gfn = end_gfn;

 rmap_walk_init_level(iterator, iterator->start_level);
}

static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator)
{
 return !!iterator->rmap;
}

static void slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
{
 while (++iterator->rmap <= iterator->end_rmap) {
  iterator->gfn += KVM_PAGES_PER_HPAGE(iterator->level);

  if (atomic_long_read(&iterator->rmap->val))
   return;
 }

 if (++iterator->level > iterator->end_level) {
  iterator->rmap = NULL;
  return;
 }

 rmap_walk_init_level(iterator, iterator->level);
}

#define for_each_slot_rmap_range(_slot_, _start_level_, _end_level_, \
    _start_gfn, _end_gfn, _iter_)    \
 for (slot_rmap_walk_init(_iter_, _slot_, _start_level_,  \
     _end_level_, _start_gfn, _end_gfn); \
      slot_rmap_walk_okay(_iter_);    \
      slot_rmap_walk_next(_iter_))

/* The return value indicates if tlb flush on all vcpus is needed. */
typedef bool (*slot_rmaps_handler) (struct kvm *kvm,
        struct kvm_rmap_head *rmap_head,
        const struct kvm_memory_slot *slot);

static __always_inline bool __walk_slot_rmaps(struct kvm *kvm,
           const struct kvm_memory_slot *slot,
           slot_rmaps_handler fn,
           int start_level, int end_level,
           gfn_t start_gfn, gfn_t end_gfn,
           bool can_yield, bool flush_on_yield,
           bool flush)
{
 struct slot_rmap_walk_iterator iterator;

 lockdep_assert_held_write(&kvm->mmu_lock);

 for_each_slot_rmap_range(slot, start_level, end_level, start_gfn,
   end_gfn, &iterator) {
  if (iterator.rmap)
   flush |= fn(kvm, iterator.rmap, slot);

  if (!can_yield)
   continue;

  if (need_resched() || rwlock_needbreak(&kvm->mmu_lock)) {
   if (flush && flush_on_yield) {
    kvm_flush_remote_tlbs_range(kvm, start_gfn,
           iterator.gfn - start_gfn + 1);
    flush = false;
   }
   cond_resched_rwlock_write(&kvm->mmu_lock);
  }
 }

 return flush;
}

static __always_inline bool walk_slot_rmaps(struct kvm *kvm,
         const struct kvm_memory_slot *slot,
         slot_rmaps_handler fn,
         int start_level, int end_level,
         bool flush_on_yield)
{
 return __walk_slot_rmaps(kvm, slot, fn, start_level, end_level,
     slot->base_gfn, slot->base_gfn + slot->npages - 1,
     true, flush_on_yield, false);
}

static __always_inline bool walk_slot_rmaps_4k(struct kvm *kvm,
            const struct kvm_memory_slot *slot,
            slot_rmaps_handler fn,
            bool flush_on_yield)
{
 return walk_slot_rmaps(kvm, slot, fn, PG_LEVEL_4K, PG_LEVEL_4K, flush_on_yield);
}

static bool __kvm_rmap_zap_gfn_range(struct kvm *kvm,
         const struct kvm_memory_slot *slot,
         gfn_t start, gfn_t end, bool can_yield,
         bool flush)
{
 return __walk_slot_rmaps(kvm, slot, kvm_zap_rmap,
     PG_LEVEL_4K, KVM_MAX_HUGEPAGE_LEVEL,
     start, end - 1, can_yield, true, flush);
}

bool kvm_unmap_gfn_range(struct kvm *kvm, struct kvm_gfn_range *range)
{
 bool flush = false;

 /*
 * To prevent races with vCPUs faulting in a gfn using stale data,
 * zapping a gfn range must be protected by mmu_invalidate_in_progress
 * (and mmu_invalidate_seq).  The only exception is memslot deletion;
 * in that case, SRCU synchronization ensures that SPTEs are zapped
 * after all vCPUs have unlocked SRCU, guaranteeing that vCPUs see the
 * invalid slot.
 */
 lockdep_assert_once(kvm->mmu_invalidate_in_progress ||
       lockdep_is_held(&kvm->slots_lock));

 if (kvm_memslots_have_rmaps(kvm))
  flush = __kvm_rmap_zap_gfn_range(kvm, range->slot,
       range->start, range->end,
       range->may_block, flush);

 if (tdp_mmu_enabled)
  flush = kvm_tdp_mmu_unmap_gfn_range(kvm, range, flush);

 if (kvm_x86_ops.set_apic_access_page_addr &&
     range->slot->id == APIC_ACCESS_PAGE_PRIVATE_MEMSLOT)
  kvm_make_all_cpus_request(kvm, KVM_REQ_APIC_PAGE_RELOAD);

 return flush;
}

#define RMAP_RECYCLE_THRESHOLD 1000

static void __rmap_add(struct kvm *kvm,
         struct kvm_mmu_memory_cache *cache,
         const struct kvm_memory_slot *slot,
         u64 *spte, gfn_t gfn, unsigned int access)
{
 struct kvm_mmu_page *sp;
 struct kvm_rmap_head *rmap_head;
 int rmap_count;

 sp = sptep_to_sp(spte);
 kvm_mmu_page_set_translation(sp, spte_index(spte), gfn, access);
 kvm_update_page_stats(kvm, sp->role.level, 1);

 rmap_head = gfn_to_rmap(gfn, sp->role.level, slot);
 rmap_count = pte_list_add(kvm, cache, spte, rmap_head);

 if (rmap_count > kvm->stat.max_mmu_rmap_size)
  kvm->stat.max_mmu_rmap_size = rmap_count;
 if (rmap_count > RMAP_RECYCLE_THRESHOLD) {
  kvm_zap_all_rmap_sptes(kvm, rmap_head);
  kvm_flush_remote_tlbs_gfn(kvm, gfn, sp->role.level);
 }
}

static void rmap_add(struct kvm_vcpu *vcpu, const struct kvm_memory_slot *slot,
       u64 *spte, gfn_t gfn, unsigned int access)
{
 struct kvm_mmu_memory_cache *cache = &vcpu->arch.mmu_pte_list_desc_cache;

 __rmap_add(vcpu->kvm, cache, slot, spte, gfn, access);
}

static bool kvm_rmap_age_gfn_range(struct kvm *kvm,
       struct kvm_gfn_range *range,
       bool test_only)
{
 struct kvm_rmap_head *rmap_head;
 struct rmap_iterator iter;
 unsigned long rmap_val;
 bool young = false;
 u64 *sptep;
 gfn_t gfn;
 int level;
 u64 spte;

 for (level = PG_LEVEL_4K; level <= KVM_MAX_HUGEPAGE_LEVEL; level++) {
  for (gfn = range->start; gfn < range->end;
       gfn += KVM_PAGES_PER_HPAGE(level)) {
   rmap_head = gfn_to_rmap(gfn, level, range->slot);
   rmap_val = kvm_rmap_lock_readonly(rmap_head);

   for_each_rmap_spte_lockless(rmap_head, &iter, sptep, spte) {
    if (!is_accessed_spte(spte))
     continue;

    if (test_only) {
     kvm_rmap_unlock_readonly(rmap_head, rmap_val);
     return true;
    }

    if (spte_ad_enabled(spte))
     clear_bit((ffs(shadow_accessed_mask) - 1),
        (unsigned long *)sptep);
    else
     /*
 * If the following cmpxchg fails, the
 * spte is being concurrently modified
 * and should most likely stay young.
 */
     cmpxchg64(sptep, spte,
           mark_spte_for_access_track(spte));
    young = true;
   }

   kvm_rmap_unlock_readonly(rmap_head, rmap_val);
  }
 }
 return young;
}

static bool kvm_may_have_shadow_mmu_sptes(struct kvm *kvm)
{
 return !tdp_mmu_enabled || READ_ONCE(kvm->arch.indirect_shadow_pages);
}

bool kvm_age_gfn(struct kvm *kvm, struct kvm_gfn_range *range)
{
 bool young = false;

 if (tdp_mmu_enabled)
  young = kvm_tdp_mmu_age_gfn_range(kvm, range);

 if (kvm_may_have_shadow_mmu_sptes(kvm))
  young |= kvm_rmap_age_gfn_range(kvm, range, false);

 return young;
}

bool kvm_test_age_gfn(struct kvm *kvm, struct kvm_gfn_range *range)
{
 bool young = false;

 if (tdp_mmu_enabled)
  young = kvm_tdp_mmu_test_age_gfn(kvm, range);

 if (young)
  return young;

 if (kvm_may_have_shadow_mmu_sptes(kvm))
  young |= kvm_rmap_age_gfn_range(kvm, range, true);

 return young;
}

static void kvm_mmu_check_sptes_at_free(struct kvm_mmu_page *sp)
{
#ifdef CONFIG_KVM_PROVE_MMU
 int i;

 for (i = 0; i < SPTE_ENT_PER_PAGE; i++) {
  if (KVM_MMU_WARN_ON(is_shadow_present_pte(sp->spt[i])))
   pr_err_ratelimited("SPTE %llx (@ %p) for gfn %llx shadow-present at free",
        sp->spt[i], &sp->spt[i],
        kvm_mmu_page_get_gfn(sp, i));
 }
#endif
}

static void kvm_account_mmu_page(struct kvm *kvm, struct kvm_mmu_page *sp)
{
 kvm->arch.n_used_mmu_pages++;
 kvm_account_pgtable_pages((void *)sp->spt, +1);
}

static void kvm_unaccount_mmu_page(struct kvm *kvm, struct kvm_mmu_page *sp)
{
 kvm->arch.n_used_mmu_pages--;
 kvm_account_pgtable_pages((void *)sp->spt, -1);
}

static void kvm_mmu_free_shadow_page(struct kvm_mmu_page *sp)
{
 kvm_mmu_check_sptes_at_free(sp);

 hlist_del(&sp->hash_link);
 list_del(&sp->link);
 free_page((unsigned long)sp->spt);
 free_page((unsigned long)sp->shadowed_translation);
 kmem_cache_free(mmu_page_header_cache, sp);
}

static unsigned kvm_page_table_hashfn(gfn_t gfn)
{
 return hash_64(gfn, KVM_MMU_HASH_SHIFT);
}

static void mmu_page_add_parent_pte(struct kvm *kvm,
        struct kvm_mmu_memory_cache *cache,
        struct kvm_mmu_page *sp, u64 *parent_pte)
{
 if (!parent_pte)
  return;

 pte_list_add(kvm, cache, parent_pte, &sp->parent_ptes);
}

static void mmu_page_remove_parent_pte(struct kvm *kvm, struct kvm_mmu_page *sp,
           u64 *parent_pte)
{
 pte_list_remove(kvm, parent_pte, &sp->parent_ptes);
}

static void drop_parent_pte(struct kvm *kvm, struct kvm_mmu_page *sp,
       u64 *parent_pte)
{
 mmu_page_remove_parent_pte(kvm, sp, parent_pte);
 mmu_spte_clear_no_track(parent_pte);
}

static void mark_unsync(u64 *spte);
static void kvm_mmu_mark_parents_unsync(struct kvm_mmu_page *sp)
{
 u64 *sptep;
 struct rmap_iterator iter;

 for_each_rmap_spte(&sp->parent_ptes, &iter, sptep) {
  mark_unsync(sptep);
 }
}

static void mark_unsync(u64 *spte)
{
 struct kvm_mmu_page *sp;

 sp = sptep_to_sp(spte);
 if (__test_and_set_bit(spte_index(spte), sp->unsync_child_bitmap))
  return;
 if (sp->unsync_children++)
  return;
 kvm_mmu_mark_parents_unsync(sp);
}

#define KVM_PAGE_ARRAY_NR 16

struct kvm_mmu_pages {
 struct mmu_page_and_offset {
  struct kvm_mmu_page *sp;
  unsigned int idx;
 } page[KVM_PAGE_ARRAY_NR];
 unsigned int nr;
};

static int mmu_pages_add(struct kvm_mmu_pages *pvec, struct kvm_mmu_page *sp,
    int idx)
{
 int i;

 if (sp->unsync)
  for (i=0; i < pvec->nr; i++)
   if (pvec->page[i].sp == sp)
    return 0;

 pvec->page[pvec->nr].sp = sp;
 pvec->page[pvec->nr].idx = idx;
 pvec->nr++;
 return (pvec->nr == KVM_PAGE_ARRAY_NR);
}

static inline void clear_unsync_child_bit(struct kvm_mmu_page *sp, int idx)
{
 --sp->unsync_children;
 WARN_ON_ONCE((int)sp->unsync_children < 0);
 __clear_bit(idx, sp->unsync_child_bitmap);
}

static int __mmu_unsync_walk(struct kvm_mmu_page *sp,
      struct kvm_mmu_pages *pvec)
{
 int i, ret, nr_unsync_leaf = 0;

 for_each_set_bit(i, sp->unsync_child_bitmap, 512) {
  struct kvm_mmu_page *child;
  u64 ent = sp->spt[i];

  if (!is_shadow_present_pte(ent) || is_large_pte(ent)) {
   clear_unsync_child_bit(sp, i);
   continue;
  }

  child = spte_to_child_sp(ent);

  if (child->unsync_children) {
   if (mmu_pages_add(pvec, child, i))
    return -ENOSPC;

   ret = __mmu_unsync_walk(child, pvec);
   if (!ret) {
    clear_unsync_child_bit(sp, i);
    continue;
   } else if (ret > 0) {
    nr_unsync_leaf += ret;
   } else
    return ret;
  } else if (child->unsync) {
   nr_unsync_leaf++;
   if (mmu_pages_add(pvec, child, i))
    return -ENOSPC;
  } else
   clear_unsync_child_bit(sp, i);
 }

 return nr_unsync_leaf;
}

#define INVALID_INDEX (-1)

static int mmu_unsync_walk(struct kvm_mmu_page *sp,
      struct kvm_mmu_pages *pvec)
{
 pvec->nr = 0;
 if (!sp->unsync_children)
  return 0;

 mmu_pages_add(pvec, sp, INVALID_INDEX);
 return __mmu_unsync_walk(sp, pvec);
}

static void kvm_unlink_unsync_page(struct kvm *kvm, struct kvm_mmu_page *sp)
{
 WARN_ON_ONCE(!sp->unsync);
 trace_kvm_mmu_sync_page(sp);
 sp->unsync = 0;
 --kvm->stat.mmu_unsync;
}

static bool kvm_mmu_prepare_zap_page(struct kvm *kvm, struct kvm_mmu_page *sp,
         struct list_head *invalid_list);
static void kvm_mmu_commit_zap_page(struct kvm *kvm,
        struct list_head *invalid_list);

static bool sp_has_gptes(struct kvm_mmu_page *sp)
{
 if (sp->role.direct)
  return false;

 if (sp->role.passthrough)
  return false;

 return true;
}

static __ro_after_init HLIST_HEAD(empty_page_hash);

static struct hlist_head *kvm_get_mmu_page_hash(struct kvm *kvm, gfn_t gfn)
{
 /*
 * Ensure the load of the hash table pointer itself is ordered before
 * loads to walk the table.  The pointer is set at runtime outside of
 * mmu_lock when the TDP MMU is enabled, i.e. when the hash table of
 * shadow pages becomes necessary only when KVM needs to shadow L1's
 * TDP for an L2 guest.  Pairs with the smp_store_release() in
 * kvm_mmu_alloc_page_hash().
 */
 struct hlist_head *page_hash = smp_load_acquire(&kvm->arch.mmu_page_hash);

 lockdep_assert_held(&kvm->mmu_lock);

 if (!page_hash)
  return &empty_page_hash;

 return &page_hash[kvm_page_table_hashfn(gfn)];
}

#define for_each_valid_sp(_kvm, _sp, _list)    \
 hlist_for_each_entry(_sp, _list, hash_link)   \
  if (is_obsolete_sp((_kvm), (_sp))) {   \
  } else

#define for_each_gfn_valid_sp_with_gptes(_kvm, _sp, _gfn)  \
 for_each_valid_sp(_kvm, _sp, kvm_get_mmu_page_hash(_kvm, _gfn)) \
  if ((_sp)->gfn != (_gfn) || !sp_has_gptes(_sp)) {} else

static bool kvm_sync_page_check(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp)
{
 union kvm_mmu_page_role root_role = vcpu->arch.mmu->root_role;

 /*
 * Ignore various flags when verifying that it's safe to sync a shadow
 * page using the current MMU context.
 *
 *  - level: not part of the overall MMU role and will never match as the MMU's
 *           level tracks the root level
 *  - access: updated based on the new guest PTE
 *  - quadrant: not part of the overall MMU role (similar to level)
 */
 const union kvm_mmu_page_role sync_role_ign = {
  .level = 0xf,
  .access = 0x7,
  .quadrant = 0x3,
  .passthrough = 0x1,
 };

 /*
 * Direct pages can never be unsync, and KVM should never attempt to
 * sync a shadow page for a different MMU context, e.g. if the role
 * differs then the memslot lookup (SMM vs. non-SMM) will be bogus, the
 * reserved bits checks will be wrong, etc...
 */
 if (WARN_ON_ONCE(sp->role.direct || !vcpu->arch.mmu->sync_spte ||
    (sp->role.word ^ root_role.word) & ~sync_role_ign.word))
  return false;

 return true;
}

static int kvm_sync_spte(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp, int i)
{
 /* sp->spt[i] has initial value of shadow page table allocation */
 if (sp->spt[i] == SHADOW_NONPRESENT_VALUE)
  return 0;

 return vcpu->arch.mmu->sync_spte(vcpu, sp, i);
}

static int __kvm_sync_page(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp)
{
 int flush = 0;
 int i;

 if (!kvm_sync_page_check(vcpu, sp))
  return -1;

 for (i = 0; i < SPTE_ENT_PER_PAGE; i++) {
  int ret = kvm_sync_spte(vcpu, sp, i);

  if (ret < -1)
   return -1;
  flush |= ret;
 }

 /*
 * Note, any flush is purely for KVM's correctness, e.g. when dropping
 * an existing SPTE or clearing W/A/D bits to ensure an mmu_notifier
 * unmap or dirty logging event doesn't fail to flush.  The guest is
 * responsible for flushing the TLB to ensure any changes in protection
 * bits are recognized, i.e. until the guest flushes or page faults on
 * a relevant address, KVM is architecturally allowed to let vCPUs use
 * cached translations with the old protection bits.
 */
 return flush;
}

static int kvm_sync_page(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp,
    struct list_head *invalid_list)
{
 int ret = __kvm_sync_page(vcpu, sp);

 if (ret < 0)
  kvm_mmu_prepare_zap_page(vcpu->kvm, sp, invalid_list);
 return ret;
}

static bool kvm_mmu_remote_flush_or_zap(struct kvm *kvm,
     struct list_head *invalid_list,
     bool remote_flush)
{
 if (!remote_flush && list_empty(invalid_list))
  return false;

 if (!list_empty(invalid_list))
  kvm_mmu_commit_zap_page(kvm, invalid_list);
 else
  kvm_flush_remote_tlbs(kvm);
 return true;
}

static bool is_obsolete_sp(struct kvm *kvm, struct kvm_mmu_page *sp)
{
 if (sp->role.invalid)
  return true;

 /* TDP MMU pages do not use the MMU generation. */
 return !is_tdp_mmu_page(sp) &&
        unlikely(sp->mmu_valid_gen != kvm->arch.mmu_valid_gen);
}

struct mmu_page_path {
 struct kvm_mmu_page *parent[PT64_ROOT_MAX_LEVEL];
 unsigned int idx[PT64_ROOT_MAX_LEVEL];
};

#define for_each_sp(pvec, sp, parents, i)   \
  for (i = mmu_pages_first(&pvec, &parents); \
   i < pvec.nr && ({ sp = pvec.page[i].sp; 1;}); \
   i = mmu_pages_next(&pvec, &parents, i))

static int mmu_pages_next(struct kvm_mmu_pages *pvec,
     struct mmu_page_path *parents,
     int i)
{
 int n;

 for (n = i+1; n < pvec->nr; n++) {
  struct kvm_mmu_page *sp = pvec->page[n].sp;
  unsigned idx = pvec->page[n].idx;
  int level = sp->role.level;

  parents->idx[level-1] = idx;
  if (level == PG_LEVEL_4K)
   break;

  parents->parent[level-2] = sp;
 }

 return n;
}

static int mmu_pages_first(struct kvm_mmu_pages *pvec,
      struct mmu_page_path *parents)
{
 struct kvm_mmu_page *sp;
 int level;

 if (pvec->nr == 0)
  return 0;

 WARN_ON_ONCE(pvec->page[0].idx != INVALID_INDEX);

 sp = pvec->page[0].sp;
 level = sp->role.level;
 WARN_ON_ONCE(level == PG_LEVEL_4K);

 parents->parent[level-2] = sp;

 /* Also set up a sentinel.  Further entries in pvec are all
 * children of sp, so this element is never overwritten.
 */
 parents->parent[level-1] = NULL;
 return mmu_pages_next(pvec, parents, 0);
}

static void mmu_pages_clear_parents(struct mmu_page_path *parents)
{
 struct kvm_mmu_page *sp;
 unsigned int level = 0;

 do {
  unsigned int idx = parents->idx[level];
  sp = parents->parent[level];
  if (!sp)
   return;

  WARN_ON_ONCE(idx == INVALID_INDEX);
  clear_unsync_child_bit(sp, idx);
  level++;
 } while (!sp->unsync_children);
}

static int mmu_sync_children(struct kvm_vcpu *vcpu,
        struct kvm_mmu_page *parent, bool can_yield)
{
 int i;
 struct kvm_mmu_page *sp;
 struct mmu_page_path parents;
 struct kvm_mmu_pages pages;
 LIST_HEAD(invalid_list);
 bool flush = false;

 while (mmu_unsync_walk(parent, &pages)) {
  bool protected = false;

  for_each_sp(pages, sp, parents, i)
   protected |= kvm_vcpu_write_protect_gfn(vcpu, sp->gfn);

  if (protected) {
   kvm_mmu_remote_flush_or_zap(vcpu->kvm, &invalid_list, true);
   flush = false;
  }

  for_each_sp(pages, sp, parents, i) {
   kvm_unlink_unsync_page(vcpu->kvm, sp);
   flush |= kvm_sync_page(vcpu, sp, &invalid_list) > 0;
   mmu_pages_clear_parents(&parents);
  }
  if (need_resched() || rwlock_needbreak(&vcpu->kvm->mmu_lock)) {
   kvm_mmu_remote_flush_or_zap(vcpu->kvm, &invalid_list, flush);
   if (!can_yield) {
    kvm_make_request(KVM_REQ_MMU_SYNC, vcpu);
    return -EINTR;
   }

   cond_resched_rwlock_write(&vcpu->kvm->mmu_lock);
   flush = false;
  }
 }

 kvm_mmu_remote_flush_or_zap(vcpu->kvm, &invalid_list, flush);
 return 0;
}

static void __clear_sp_write_flooding_count(struct kvm_mmu_page *sp)
{
 atomic_set(&sp->write_flooding_count,  0);
}

static void clear_sp_write_flooding_count(u64 *spte)
{
 __clear_sp_write_flooding_count(sptep_to_sp(spte));
}

/*
 * The vCPU is required when finding indirect shadow pages; the shadow
 * page may already exist and syncing it needs the vCPU pointer in
 * order to read guest page tables.  Direct shadow pages are never
 * unsync, thus @vcpu can be NULL if @role.direct is true.
 */
static struct kvm_mmu_page *kvm_mmu_find_shadow_page(struct kvm *kvm,
           struct kvm_vcpu *vcpu,
           gfn_t gfn,
           struct hlist_head *sp_list,
           union kvm_mmu_page_role role)
{
 struct kvm_mmu_page *sp;
 int ret;
 int collisions = 0;
 LIST_HEAD(invalid_list);

 for_each_valid_sp(kvm, sp, sp_list) {
  if (sp->gfn != gfn) {
   collisions++;
   continue;
  }

  if (sp->role.word != role.word) {
   /*
 * If the guest is creating an upper-level page, zap
 * unsync pages for the same gfn.  While it's possible
 * the guest is using recursive page tables, in all
 * likelihood the guest has stopped using the unsync
 * page and is installing a completely unrelated page.
 * Unsync pages must not be left as is, because the new
 * upper-level page will be write-protected.
 */
   if (role.level > PG_LEVEL_4K && sp->unsync)
    kvm_mmu_prepare_zap_page(kvm, sp,
        &invalid_list);
   continue;
  }

  /* unsync and write-flooding only apply to indirect SPs. */
  if (sp->role.direct)
   goto out;

  if (sp->unsync) {
   if (KVM_BUG_ON(!vcpu, kvm))
    break;

   /*
 * The page is good, but is stale.  kvm_sync_page does
 * get the latest guest state, but (unlike mmu_unsync_children)
 * it doesn't write-protect the page or mark it synchronized!
 * This way the validity of the mapping is ensured, but the
 * overhead of write protection is not incurred until the
 * guest invalidates the TLB mapping.  This allows multiple
 * SPs for a single gfn to be unsync.
 *
 * If the sync fails, the page is zapped.  If so, break
 * in order to rebuild it.
 */
   ret = kvm_sync_page(vcpu, sp, &invalid_list);
   if (ret < 0)
    break;

   WARN_ON_ONCE(!list_empty(&invalid_list));
   if (ret > 0)
    kvm_flush_remote_tlbs(kvm);
  }

  __clear_sp_write_flooding_count(sp);

  goto out;
 }

 sp = NULL;
 ++kvm->stat.mmu_cache_miss;

out:
 kvm_mmu_commit_zap_page(kvm, &invalid_list);

 if (collisions > kvm->stat.max_mmu_page_hash_collisions)
  kvm->stat.max_mmu_page_hash_collisions = collisions;
 return sp;
}

/* Caches used when allocating a new shadow page. */
struct shadow_page_caches {
 struct kvm_mmu_memory_cache *page_header_cache;
 struct kvm_mmu_memory_cache *shadow_page_cache;
 struct kvm_mmu_memory_cache *shadowed_info_cache;
};

static struct kvm_mmu_page *kvm_mmu_alloc_shadow_page(struct kvm *kvm,
            struct shadow_page_caches *caches,
            gfn_t gfn,
            struct hlist_head *sp_list,
            union kvm_mmu_page_role role)
{
 struct kvm_mmu_page *sp;

 sp = kvm_mmu_memory_cache_alloc(caches->page_header_cache);
 sp->spt = kvm_mmu_memory_cache_alloc(caches->shadow_page_cache);
 if (!role.direct && role.level <= KVM_MAX_HUGEPAGE_LEVEL)
  sp->shadowed_translation = kvm_mmu_memory_cache_alloc(caches->shadowed_info_cache);

 set_page_private(virt_to_page(sp->spt), (unsigned long)sp);

 INIT_LIST_HEAD(&sp->possible_nx_huge_page_link);

 /*
 * active_mmu_pages must be a FIFO list, as kvm_zap_obsolete_pages()
 * depends on valid pages being added to the head of the list.  See
 * comments in kvm_zap_obsolete_pages().
 */
 sp->mmu_valid_gen = kvm->arch.mmu_valid_gen;
 list_add(&sp->link, &kvm->arch.active_mmu_pages);
--> --------------------

--> maximum size reached

--> --------------------