[patch 10/10] KVM: MMU: speed up mmu_unsync_walk

Marcelo Tosatti
2008-09-18T21:49:59Z

[-- Attachment #1: kvm-oos-speed-walk --]
[-- Type: text/plain, Size: 4602 bytes --]

Cache the unsynced children information in a per-page bitmap.

Index: kvm/arch/x86/kvm/mmu.c
===================================================================
--- kvm.orig/arch/x86/kvm/mmu.c
+++ kvm/arch/x86/kvm/mmu.c
@@ -924,6 +924,38 @@ static void mmu_parent_walk(struct kvm_v
} while (level > start_level-1);
}

+static void kvm_mmu_update_unsync_bitmap(u64 *spte)
+{
+ unsigned int index;
+ struct kvm_mmu_page *sp = page_header(__pa(spte));
+
+ index = spte - sp->spt;
+ __set_bit(index, sp->unsync_child_bitmap);
+ sp->unsync_children = 1;
+}
+
+static void kvm_mmu_update_parents_unsync(struct kvm_mmu_page *sp)
+{
+ struct kvm_pte_chain *pte_chain;
+ struct hlist_node *node;
+ int i;
+
+ if (!sp->parent_pte)
+ return;
+
+ if (!sp->multimapped) {
+ kvm_mmu_update_unsync_bitmap(sp->parent_pte);
+ return;
+ }
+
+ hlist_for_each_entry(pte_chain, node, &sp->parent_ptes, link)
+ for (i = 0; i < NR_PTE_CHAIN_ENTRIES; ++i) {
+ if (!pte_chain->parent_ptes[i])
+ break;
+ kvm_mmu_update_unsync_bitmap(pte_chain->parent_ptes[i]);
+ }
+}
+
static void nonpaging_prefetch_page(struct kvm_vcpu *vcpu,
struct kvm_mmu_page *sp)
{
@@ -946,33 +978,57 @@ static void nonpaging_invlpg(struct kvm_
static int mmu_unsync_walk(struct kvm_mmu_page *parent, mmu_unsync_fn fn,
void *priv)
{
- int i, ret;
- struct kvm_mmu_page *sp = parent;
+ int ret, level, i;
+ u64 ent;
+ struct kvm_mmu_page *sp, *child;
+ struct walk {
+ struct kvm_mmu_page *sp;
+ int pos;
+ } walk[PT64_ROOT_LEVEL];

- while (parent->unsync_children) {
- for (i = 0; i < PT64_ENT_PER_PAGE; ++i) {
- u64 ent = sp->spt[i];
+ WARN_ON(parent->role.level == PT_PAGE_TABLE_LEVEL);
+
+ if (!parent->unsync_children)
+ return 0;
+
+ memset(&walk, 0, sizeof(walk));
+ level = parent->role.level;
+ walk[level-1].sp = parent;
+
+ do {
+ sp = walk[level-1].sp;
+ i = find_next_bit(sp->unsync_child_bitmap, 512, walk[level-1].pos);
+ if (i < 512) {
+ walk[level-1].pos = i+1;
+ ent = sp->spt[i];

if (is_shadow_present_pte(ent)) {
- struct kvm_mmu_page *child;
child = page_header(ent & PT64_BASE_ADDR_MASK);

if (child->unsync_children) {
- sp = child;
- break;
+ --level;
+ walk[level-1].sp = child;
+ walk[level-1].pos = 0;
+ continue;
}
if (child->unsync) {
ret = fn(child, priv);
+ __clear_bit(i, sp->unsync_child_bitmap);
if (ret)
return ret;
}
}
+ __clear_bit(i, sp->unsync_child_bitmap);
+ } else {
+ ++level;
+ if (find_first_bit(sp->unsync_child_bitmap, 512) == 512) {
+ sp->unsync_children = 0;
+ if (level-1 < PT64_ROOT_LEVEL)
+ walk[level-1].pos = 0;
+ }
}
- if (i == PT64_ENT_PER_PAGE) {
- sp->unsync_children = 0;
- sp = parent;
- }
- }
+ } while (level <= parent->role.level);
+
return 0;
}

@@ -1037,6 +1093,13 @@ static void mmu_sync_children(struct kvm
cond_resched_lock(&vcpu->kvm->mmu_lock);
}

+static int unsync_walk_fn(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp)
+{
+ sp->unsync_children = 1;
+ kvm_mmu_update_parents_unsync(sp);
+ return 1;
+}
+
static struct kvm_mmu_page *kvm_mmu_get_page(struct kvm_vcpu *vcpu,
gfn_t gfn,
gva_t gaddr,
@@ -1075,10 +1138,11 @@ static struct kvm_mmu_page *kvm_mmu_get_
if (sp->role.word != role.word)
continue;

- if (sp->unsync_children)
- vcpu->arch.mmu.need_root_sync = 1;
-
mmu_page_add_parent_pte(vcpu, sp, parent_pte);
+ if (sp->unsync_children) {
+ vcpu->arch.mmu.need_root_sync = 1;
+ mmu_parent_walk(vcpu, sp, unsync_walk_fn);
+ }
pgprintk("%s: found\n", __func__);
return sp;
}
@@ -1337,12 +1401,6 @@ struct page *gva_to_page(struct kvm_vcpu
return page;
}

-static int unsync_walk_fn(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp)
-{
- sp->unsync_children = 1;
- return 1;
-}
-
static int kvm_unsync_page(struct kvm_vcpu *vcpu, struct kvm_mmu_page *sp)
{
unsigned index;
@@ -1360,6 +1418,7 @@ static int kvm_unsync_page(struct kvm_vc
return 1;
}
mmu_parent_walk(vcpu, sp, unsync_walk_fn);
+ kvm_mmu_update_parents_unsync(sp);
++vcpu->kvm->stat.mmu_unsync;
sp->unsync = 1;
return 0;
Index: kvm/include/asm-x86/kvm_host.h
===================================================================
--- kvm.orig/include/asm-x86/kvm_host.h
+++ kvm/include/asm-x86/kvm_host.h
@@ -201,6 +201,7 @@ struct kvm_mmu_page {
u64 *parent_pte; /* !multimapped */
struct hlist_head parent_ptes; /* multimapped, kvm_pte_chain */
};
+ DECLARE_BITMAP(unsync_child_bitmap, 512);
};

struct kvm_pv_mmu_op_buffer {

--