[patch 09/13] KVM: MMU: out of sync shadow core

Marcelo Tosatti
2008-09-06T19:27:37Z

[-- Attachment #1: kvm-oos-core --]
[-- Type: text/plain, Size: 15796 bytes --]

Allow global and single-root, single-role-per-gfn leaf shadowed
pagetables to be unsynced.

Global unsync pages are saved into a per-vm array, synced on cr4/cr0 writes.

Non-global unsync pages are linked off their root shadow page, synced
on cr3/cr4/cr0 writes.

Some of this logic is simplistic and could be smarter (page_multimapped and
the full root sync on higher level pagetable sharing).

Also unsyncing of non-leaf nodes might be interesting (but more complicated).

Index: kvm/arch/x86/kvm/mmu.c
===================================================================
--- kvm.orig/arch/x86/kvm/mmu.c
+++ kvm/arch/x86/kvm/mmu.c
@@ -64,6 +64,17 @@ static void kvm_mmu_audit(struct kvm_vcp
#define rmap_printk(x...) do { } while (0)

#endif
+#define OOS_DEBUG
+#if defined (OOS_DEBUG)
+#define OOS_ASSERT(x) \
+ if (!(x)) { \
+ printk(KERN_WARNING "assertion failed %s:%d: %s\n", \
+ __FILE__, __LINE__, #x); \
+ dump_stack(); \
+ }
+#else
+#define OOS_ASSERT(x) do { } while (0)
+#endif

#if defined(MMU_DEBUG) || defined(AUDIT)
static int dbg = 0;
@@ -773,6 +784,8 @@ static struct kvm_mmu_page *kvm_mmu_allo
sp = mmu_memory_cache_alloc(&vcpu->arch.mmu_page_header_cache, sizeof *sp);
sp->spt = mmu_memory_cache_alloc(&vcpu->arch.mmu_page_cache, PAGE_SIZE);
sp->gfns = mmu_memory_cache_alloc(&vcpu->arch.mmu_page_cache, PAGE_SIZE);
+ INIT_LIST_HEAD(&sp->oos_link);
+ INIT_LIST_HEAD(&sp->unsync_pages);
set_page_private(virt_to_page(sp->spt), (unsigned long)sp);
list_add(&sp->link, &vcpu->kvm->arch.active_mmu_pages);
ASSERT(is_empty_shadow_page(sp->spt));
@@ -896,6 +909,31 @@ static struct kvm_mmu_page *kvm_mmu_look
return NULL;
}

+static struct kvm_mmu_page *kvm_mmu_lookup_page_root(struct kvm_vcpu *vcpu,
+ gfn_t gfn)
+{
+ unsigned index;
+ struct hlist_head *bucket;
+ struct kvm_mmu_page *sp;
+ struct hlist_node *node;
+ struct kvm *kvm = vcpu->kvm;
+ int level = vcpu->arch.mmu.root_level;
+ if (!is_long_mode(vcpu) && is_pae(vcpu))
+ level--;
+
+ pgprintk("%s: looking for gfn %lx\n", __func__, gfn);
+ index = kvm_page_table_hashfn(gfn);
+ bucket = &kvm->arch.mmu_page_hash[index];
+ hlist_for_each_entry(sp, node, bucket, hash_link)
+ if (sp->gfn == gfn && !sp->role.metaphysical
+ && !sp->role.invalid && sp->role.level == level) {
+ pgprintk("%s: found role %x\n",
+ __func__, sp->role.word);
+ return sp;
+ }
+ return NULL;
+}
+
static void kvm_sync_writeble(struct kvm_vcpu *vcpu, u64 *spte, int gpte_rw,
gfn_t gfn)
{
@@ -913,12 +951,48 @@ static void kvm_sync_writeble(struct kvm
return;
}

-static void kvm_mmu_zap_page(struct kvm *kvm, struct kvm_mmu_page *sp);
+static void kvm_unlink_unsync_page(struct kvm *kvm, struct kvm_mmu_page *sp)
+{
+ if (kvm_page_global(sp)) {
+ int i;
+ /* FIXME: save index into sp->flags */
+ for (i = 0; i < ARRAY_SIZE(kvm->arch.oos_global_pages); i++)
+ if (kvm->arch.oos_global_pages[i] == sp) {
+ kvm->arch.oos_global_pages[i] = NULL;
+ break;
+ }
+ OOS_ASSERT(i < ARRAY_SIZE(kvm->arch.oos_global_pages));
+ --kvm->stat.mmu_unsync_global;
+ } else {
+ list_del(&sp->oos_link);
+ --kvm->stat.mmu_unsync;
+ }
+}
+
+static void kvm_mmu_page_unlink_children(struct kvm *kvm,
+ struct kvm_mmu_page *sp);
+static int kvm_mmu_zap_page(struct kvm *kvm, struct kvm_mmu_page *sp);
+
+static void kvm_mmu_zap_unsync_page(struct kvm *kvm, struct kvm_mmu_page *sp)
+{
+ if (unlikely(kvm_page_inuse(sp))) {
+ kvm_mmu_page_unlink_children(kvm, sp);
+ kvm_flush_remote_tlbs(kvm);
+ kvm_unlink_unsync_page(kvm, sp);
+ kvm_clear_pg_unsync(sp);
+ } else
+ kvm_mmu_zap_page(kvm, sp);
+}

static int kvm_sync_page(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp)
{
int ret;

+ if (sp->role.glevels != vcpu->arch.mmu.root_level) {
+ kvm_mmu_zap_unsync_page(vcpu->kvm, sp);
+ return -EINVAL;
+ }
+
rmap_write_protect(vcpu->kvm, sp->gfn);
ret = vcpu->arch.mmu.sync_page(vcpu, sp);
if (ret <= 0)
@@ -926,13 +1000,87 @@ static int kvm_sync_page(struct kvm_vcpu
* mappings (only originally writeble ones
* of course).
*/
- kvm_mmu_zap_page(vcpu->kvm, sp);
- else
+ kvm_mmu_zap_unsync_page(vcpu->kvm, sp);
+ else {
+ kvm_unlink_unsync_page(vcpu->kvm, sp);
kvm_clear_pg_unsync(sp);
+ }

return ret;
}

+static int mmu_unsync_global_page(struct kvm_vcpu *vcpu,
+ struct kvm_mmu_page *sp)
+
+{
+ struct kvm *kvm = vcpu->kvm;
+ unsigned idx = kvm->arch.oos_global_idx;
+
+ if (kvm->arch.oos_global_pages[idx])
+ kvm_sync_page(vcpu, kvm->arch.oos_global_pages[idx]);
+
+ kvm_set_pg_unsync(sp);
+ kvm->arch.oos_global_pages[idx] = sp;
+
+ kvm->arch.oos_global_idx++;
+ if (kvm->arch.oos_global_idx >= ARRAY_SIZE(kvm->arch.oos_global_pages))
+ kvm->arch.oos_global_idx = 0;
+
+ ++kvm->stat.mmu_unsync_global;
+ return 0;
+}
+
+static int page_multimapped(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp)
+{
+ while (!sp->multimapped) {
+ if (!sp->parent_pte)
+ return 0;
+ sp = page_header(__pa(sp->parent_pte));
+ }
+ return 1;
+}
+
+static int mmu_unsync_page(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp)
+{
+ struct kvm_mmu_page *root_sp;
+
+ if (page_multimapped(vcpu, sp))
+ return 1;
+
+ root_sp = kvm_mmu_lookup_page_root(vcpu, sp->root_gfn);
+ if (!root_sp)
+ return 1;
+
+ kvm_set_pg_unsync(sp);
+ list_add(&sp->oos_link, &root_sp->unsync_pages);
+ ++vcpu->kvm->stat.mmu_unsync;
+ return 0;
+}
+
+static int kvm_unsync_page(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp)
+{
+ if (kvm_page_global(sp))
+ return mmu_unsync_global_page(vcpu, sp);
+ else
+ return mmu_unsync_page(vcpu, sp);
+}
+
+static int set_shared_mmu_page(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp)
+{
+ struct kvm_mmu_page *root_sp;
+ int ret = 0;
+
+ if (sp->role.level == PT_PAGE_TABLE_LEVEL) {
+ if (kvm_page_unsync(sp))
+ kvm_sync_page(vcpu, sp);
+ } else if (sp->root_gfn != -1) {
+ root_sp = kvm_mmu_lookup_page_root(vcpu, sp->root_gfn);
+ }
+
+ sp->root_gfn = -1;
+ return ret;
+}
+
static struct kvm_mmu_page *kvm_mmu_get_page(struct kvm_vcpu *vcpu,
gfn_t root_gfn,
gfn_t gfn,
@@ -947,7 +1095,8 @@ static struct kvm_mmu_page *kvm_mmu_get_
unsigned quadrant;
struct hlist_head *bucket;
struct kvm_mmu_page *sp;
- struct hlist_node *node;
+ struct hlist_node *node, *tmp;
+ int unsyncable = 1;

role.word = 0;
role.glevels = vcpu->arch.mmu.root_level;
@@ -963,8 +1112,24 @@ static struct kvm_mmu_page *kvm_mmu_get_
gfn, role.word);
index = kvm_page_table_hashfn(gfn);
bucket = &vcpu->kvm->arch.mmu_page_hash[index];
- hlist_for_each_entry(sp, node, bucket, hash_link)
- if (sp->gfn == gfn && sp->role.word == role.word) {
+ hlist_for_each_entry_safe(sp, node, tmp, bucket, hash_link)
+ if (sp->gfn == gfn) {
+ /*
+ * If a pagetable becomes referenced by more than one
+ * root, or has multiple roles, unsync it and disable
+ * oos. For higher level pgtables the entire tree
+ * has to be synced.
+ */
+ if (sp->root_gfn != root_gfn) {
+ kvm_set_pg_inuse(sp);
+ if (set_shared_mmu_page(vcpu, sp))
+ tmp = bucket->first;
+ kvm_clear_pg_inuse(sp);
+ unsyncable = 0;
+ }
+ if (sp->role.word != role.word)
+ continue;
+
mmu_page_add_parent_pte(vcpu, sp, parent_pte);
pgprintk("%s: found\n", __func__);
return sp;
@@ -975,6 +1140,9 @@ static struct kvm_mmu_page *kvm_mmu_get_
return sp;
pgprintk("%s: adding gfn %lx role %x\n", __func__, gfn, role.word);
sp->gfn = gfn;
+ if (!unsyncable)
+ root_gfn = -1;
+ sp->root_gfn = root_gfn;
sp->role = role;
hlist_add_head(&sp->hash_link, bucket);
if (!metaphysical)
@@ -1084,14 +1252,35 @@ static void kvm_mmu_unlink_parents(struc
}
}

-static void kvm_mmu_zap_page(struct kvm *kvm, struct kvm_mmu_page *sp)
+static void kvm_drop_unsync_children(struct kvm *kvm,
+ struct kvm_mmu_page *root_sp)
+{
+ struct kvm_mmu_page *sp, *n;
+
+ list_for_each_entry_safe(sp, n, &root_sp->unsync_pages, oos_link) {
+ OOS_ASSERT(kvm_page_unsync(sp));
+ OOS_ASSERT(!kvm_page_global(sp));
+ OOS_ASSERT(sp->role.level == PT_PAGE_TABLE_LEVEL);
+ OOS_ASSERT(list_empty(&sp->unsync_pages));
+ kvm_mmu_zap_page(kvm, sp);
+ }
+}
+
+static int kvm_mmu_zap_page(struct kvm *kvm, struct kvm_mmu_page *sp)
{
+ int ret = 0;
++kvm->stat.mmu_shadow_zapped;
kvm_mmu_page_unlink_children(kvm, sp);
kvm_mmu_unlink_parents(kvm, sp);
kvm_flush_remote_tlbs(kvm);
if (!sp->role.invalid && !sp->role.metaphysical)
unaccount_shadowed(kvm, sp->gfn);
+ if (kvm_test_clear_pg_unsync(sp))
+ kvm_unlink_unsync_page(kvm, sp);
+ if (!list_empty(&sp->unsync_pages)) {
+ kvm_drop_unsync_children(kvm, sp);
+ ret = 1;
+ }
if (!sp->root_count) {
hlist_del(&sp->hash_link);
kvm_mmu_free_page(kvm, sp);
@@ -1101,6 +1290,7 @@ static void kvm_mmu_zap_page(struct kvm
kvm_reload_remote_mmus(kvm);
}
kvm_mmu_reset_last_pte_updated(kvm);
+ return ret;
}

/*
@@ -1153,8 +1343,9 @@ static int kvm_mmu_unprotect_page(struct
if (sp->gfn == gfn && !sp->role.metaphysical) {
pgprintk("%s: gfn %lx role %x\n", __func__, gfn,
sp->role.word);
- kvm_mmu_zap_page(kvm, sp);
r = 1;
+ if (kvm_mmu_zap_page(kvm, sp))
+ n = bucket->first;
}
return r;
}
@@ -1191,6 +1382,25 @@ struct page *gva_to_page(struct kvm_vcpu
return page;
}

+static int mmu_need_write_protect(struct kvm_vcpu *vcpu, gfn_t gfn,
+ int write_fault)
+{
+ struct kvm_mmu_page *shadow;
+
+ shadow = kvm_mmu_lookup_page(vcpu->kvm, gfn);
+ if (shadow) {
+ if (!write_fault)
+ return 1;
+ if (shadow->role.level != PT_PAGE_TABLE_LEVEL)
+ return 1;
+ if (shadow->root_gfn == -1)
+ return 1;
+ if (!kvm_page_unsync(shadow))
+ return kvm_unsync_page(vcpu, shadow);
+ }
+ return 0;
+}
+
static void mmu_set_spte(struct kvm_vcpu *vcpu, u64 *shadow_pte,
unsigned pt_access, unsigned pte_access,
int user_fault, int write_fault, int dirty,
@@ -1207,8 +1417,13 @@ static void mmu_set_spte(struct kvm_vcpu
__func__, *shadow_pte, pt_access,
write_fault, user_fault, gfn);

- if (!global)
+ kvm_set_pg_inuse(sp);
+
+ if (!global && kvm_page_global(sp)) {
+ if (kvm_page_unsync(sp))
+ kvm_sync_page(vcpu, sp);
kvm_clear_pg_global(sp);
+ }

if (is_rmap_pte(*shadow_pte)) {
/*
@@ -1256,12 +1471,19 @@ static void mmu_set_spte(struct kvm_vcpu

if ((pte_access & ACC_WRITE_MASK)
|| (write_fault && !is_write_protection(vcpu) && !user_fault)) {
- struct kvm_mmu_page *shadow;
+ /*
+ * Do not create write protected large translations.
+ */
+ if (largepage && has_wrprotected_page(vcpu->kvm, gfn)) {
+ spte = shadow_trap_nonpresent_pte;
+ was_writeble = 0;
+ *ptwrite = 0;
+ goto set_shadow;
+ }

spte |= PT_WRITABLE_MASK;

- shadow = kvm_mmu_lookup_page(vcpu->kvm, gfn);
- if (shadow) {
+ if (mmu_need_write_protect(vcpu, gfn, write_fault)) {
pgprintk("%s: found shadow page for %lx, marking ro\n",
__func__, gfn);
pte_access &= ~ACC_WRITE_MASK;
@@ -1272,16 +1494,9 @@ static void mmu_set_spte(struct kvm_vcpu
if (write_fault)
*ptwrite = 1;
}
- /*
- * Do not create write protected large translations.
- */
- if (largepage && has_wrprotected_page(vcpu->kvm, gfn)) {
- spte = shadow_trap_nonpresent_pte;
- was_writeble = 0;
- *ptwrite = 0;
- }
}

+set_shadow:
if (pte_access & ACC_WRITE_MASK)
mark_page_dirty(vcpu->kvm, gfn);

@@ -1309,6 +1524,7 @@ static void mmu_set_spte(struct kvm_vcpu
vcpu->arch.last_pte_updated = shadow_pte;
vcpu->arch.last_pte_gfn = gfn;
}
+ kvm_clear_pg_inuse(sp);
}

static void nonpaging_new_cr3(struct kvm_vcpu *vcpu)
@@ -1950,7 +2166,8 @@ void kvm_mmu_pte_write(struct kvm_vcpu *
*/
pgprintk("misaligned: gpa %llx bytes %d role %x\n",
gpa, bytes, sp->role.word);
- kvm_mmu_zap_page(vcpu->kvm, sp);
+ if (kvm_mmu_zap_page(vcpu->kvm, sp))
+ n = bucket->first;
++vcpu->kvm->stat.mmu_flooded;
continue;
}
@@ -2174,7 +2391,9 @@ void kvm_mmu_zap_all(struct kvm *kvm)

spin_lock(&kvm->mmu_lock);
list_for_each_entry_safe(sp, node, &kvm->arch.active_mmu_pages, link)
- kvm_mmu_zap_page(kvm, sp);
+ if (kvm_mmu_zap_page(kvm, sp))
+ node = container_of(kvm->arch.active_mmu_pages.next,
+ struct kvm_mmu_page, link);
spin_unlock(&kvm->mmu_lock);

kvm_flush_remote_tlbs(kvm);
Index: kvm/include/asm-x86/kvm_host.h
===================================================================
--- kvm.orig/include/asm-x86/kvm_host.h
+++ kvm/include/asm-x86/kvm_host.h
@@ -179,6 +179,10 @@ union kvm_mmu_page_role {
struct kvm_mmu_page {
struct list_head link;
struct hlist_node hash_link;
+ /* FIXME: one list_head is enough */
+ struct list_head unsync_pages;
+ struct list_head oos_link;
+ gfn_t root_gfn; /* root this pagetable belongs to, -1 if multimapped */

/*
* The following two entries are used to key the shadow page in the
@@ -362,6 +366,8 @@ struct kvm_arch{
unsigned int n_requested_mmu_pages;
unsigned int n_alloc_mmu_pages;
struct hlist_head mmu_page_hash[KVM_NUM_MMU_PAGES];
+ struct kvm_mmu_page *oos_global_pages[7];
+ unsigned oos_global_idx;
/*
* Hash table of struct kvm_mmu_page.
*/
@@ -390,6 +396,8 @@ struct kvm_vm_stat {
u32 mmu_flooded;
u32 mmu_recycled;
u32 mmu_cache_miss;
+ u32 mmu_unsync;
+ u32 mmu_unsync_global;
u32 remote_tlb_flush;
u32 lpages;
};
@@ -763,6 +771,7 @@ int kvm_age_hva(struct kvm *kvm, unsigne
enum kvm_page_flags {
KVM_PG_global,
KVM_PG_unsync,
+ KVM_PG_inuse,
};

#define KVMPGFLAG(name) \
@@ -777,5 +786,6 @@ static inline int kvm_test_clear_pg_##na

KVMPGFLAG(global);
KVMPGFLAG(unsync);
+KVMPGFLAG(inuse);

#endif
Index: kvm/arch/x86/kvm/x86.c
===================================================================
--- kvm.orig/arch/x86/kvm/x86.c
+++ kvm/arch/x86/kvm/x86.c
@@ -100,6 +100,8 @@ struct kvm_stats_debugfs_item debugfs_en
{ "mmu_flooded", VM_STAT(mmu_flooded) },
{ "mmu_recycled", VM_STAT(mmu_recycled) },
{ "mmu_cache_miss", VM_STAT(mmu_cache_miss) },
+ { "mmu_unsync", VM_STAT(mmu_unsync) },
+ { "mmu_unsync_global", VM_STAT(mmu_unsync_global) },
{ "remote_tlb_flush", VM_STAT(remote_tlb_flush) },
{ "largepages", VM_STAT(lpages) },
{ NULL }
Index: kvm/arch/x86/kvm/paging_tmpl.h
===================================================================
--- kvm.orig/arch/x86/kvm/paging_tmpl.h
+++ kvm/arch/x86/kvm/paging_tmpl.h
@@ -81,6 +81,7 @@ struct shadow_walker {
int write_fault;
int largepage;
int *ptwrite;
+ int multiroot;
pfn_t pfn;
u64 *sptep;
};
@@ -294,7 +295,7 @@ static int FNAME(shadow_walk_entry)(stru
struct kvm_mmu_page *shadow_page;
u64 spte;
int metaphysical;
- gfn_t table_gfn;
+ gfn_t table_gfn, root_gfn;
int r;
pt_element_t curr_pte;

@@ -324,9 +325,11 @@ static int FNAME(shadow_walk_entry)(stru
metaphysical = 0;
table_gfn = gw->table_gfn[level - 2];
}
- shadow_page = kvm_mmu_get_page(vcpu, gw->table_gfn[gw->root_level - 1],
- table_gfn, (gva_t)addr, level-1,
- metaphysical, access, sptep);
+ root_gfn = gw->table_gfn[gw->root_level - 1];
+ if (sw->multiroot)
+ root_gfn = -1;
+ shadow_page = kvm_mmu_get_page(vcpu, root_gfn, table_gfn, (gva_t)addr,
+ level-1, metaphysical, access, sptep);
if (!metaphysical) {
r = kvm_read_guest_atomic(vcpu->kvm, gw->pte_gpa[level - 2],
&curr_pte, sizeof(curr_pte));
@@ -336,6 +339,8 @@ static int FNAME(shadow_walk_entry)(stru
return 1;
}
}
+ if (shadow_page->root_gfn == -1)
+ sw->multiroot = 1;

spte = __pa(shadow_page->spt) | PT_PRESENT_MASK | PT_ACCESSED_MASK
| PT_WRITABLE_MASK | PT_USER_MASK;
@@ -355,6 +360,7 @@ static u64 *FNAME(fetch)(struct kvm_vcpu
.write_fault = write_fault,
.largepage = largepage,
.ptwrite = ptwrite,
+ .multiroot = 0,
.pfn = pfn,
};

--