kvm: x86 mmu: avoid mmu_page_hash lookup for direct_map-only VM
PATCH 1/1 kvm: x86 mmu: avoid mmu_page_hash lookup for direct_map-only VM
From: Peter Feiner <[email protected]>
Optimization for avoiding lookups in mmu_page_hash. When there's a single direct root, a shadow page has at most one parent SPTE (non-root SPs have exactly one; the root has none). Thus, if an SPTE is non-present, it can be linked to a newly allocated SP without first checking if the SP already exists.
This optimization has proven significant in batch large SP shattering where the hash lookup accounted for 95% of the overhead.
--- arch/x86/include/asm/kvm_host.h | 13 ++++++++ arch/x86/kvm/mmu/mmu.c | 55 +++++++++++++++++++-------------- 2 files changed, 45 insertions(+), 23 deletions(-)
arch/x86/include/asm/kvm_host.h +13 -0
@@ -913,6 +913,19 @@ struct kvm_arch {struct kvm_page_track_notifier_node mmu_sp_tracker;struct kvm_page_track_notifier_head track_notifier_head; +/* +* Optimization for avoiding lookups in mmu_page_hash. When there's a +* single direct root, a shadow page has at most one parent SPTE +* (non-root SPs have exactly one; the root has none). Thus, if an SPTE +* is non-present, it can be linked to a newly allocated SP without +* first checking if the SP already exists. +* +* False initially because there are no indirect roots. +* +* Guarded by mmu_lock. +*/ +bool shadow_page_may_have_multiple_parents; +struct list_head assigned_dev_head;struct iommu_domain *iommu_domain;bool iommu_noncoherent;
arch/x86/kvm/mmu/mmu.c +32 -23
73 lines not on this page · raw message
Signature · 1 line
2.26.2.303.gf8c07b1a785-goog
Quoted 7 lines · Jon Cargille
From: Peter Feiner <[email protected]>
Optimization for avoiding lookups in
mmu_page_hash. When there's a single direct root, a shadow page has at most one parent SPTE (non-root SPs have exactly one; the root has none). Thus, if an SPTE is non-present, it can be linked to a newly allocated SP without first checking if the SP already exists.
Some mechanical comments below. I'll think through the actual logic next week, my brain needs to be primed anytime the MMU is involved :-)
Quoted 22 lines
This optimization has proven significant in batch large SP shattering where the hash lookup accounted for 95% of the overhead.
Signed-off-by Peter Feiner <[email protected]>Signed-off-by Jon Cargille <[email protected]>Reviewed-by Jim Mattson <[email protected]>--- arch/x86/include/asm/kvm_host.h | 13 ++++++++ arch/x86/kvm/mmu/mmu.c | 55 +++++++++++++++++++-------------- 2 files changed, 45 insertions(+), 23 deletions(-)arch/x86/include/asm/kvm_host.h +2
-0@@ -913,6 +913,19 @@ struct kvm_arch {struct kvm_page_track_notifier_node mmu_sp_tracker;struct kvm_page_track_notifier_head track_notifier_head; +/* +* Optimization for avoiding lookups in mmu_page_hash. When there's a
arch/x86/include/asm/kvm_host.h struct kvm_arch { · line 927
Quoted 10 lines
arch/x86/include/asm/kvm_host.h +10
-0+* single direct root, a shadow page has at most one parent SPTE +* (non-root SPs have exactly one; the root has none). Thus, if an SPTE +* is non-present, it can be linked to a newly allocated SP without +* first checking if the SP already exists. +* +* False initially because there are no indirect roots. +* +* Guarded by mmu_lock. +*/ +bool shadow_page_may_have_multiple_parents;
Why make this a one-way bool? Wouldn't it be better to let this transition back to '0' once all nested guests go away?
And maybe a shorter name that reflects what it tracks instead of how its used, e.g. has_indirect_mmu or indirect_mmu_count.
Quoted 12 lines
arch/x86/include/asm/kvm_host.h +1
-0+struct list_head assigned_dev_head;struct iommu_domain *iommu_domain;bool iommu_noncoherent;arch/x86/kvm/mmu/mmu.c +0
-0@@ -2499,35 +2499,40 @@ static struct kvm_mmu_page *kvm_mmu_get_page(struct kvm_vcpu *vcpu, quadrant &= (1 << ((PT32_PT_BITS -PT64_PT_BITS ) * level)) -1 ; role.quadrant = quadrant; }
arch/x86/kvm/mmu/mmu.c static struct kvm_mmu_page *kvm_mmu_get_page(struct kvm_vcpu *vcpu, · line 2504
Quoted 10 lines
arch/x86/kvm/mmu/mmu.c +2
-7-for_each_valid_sp (vcpu->kvm, sp, gfn) { -if (sp->gfn != gfn) { - collisions++; -continue ; - } -if (!need_sync && sp->unsync) - need_sync = true; +if (vcpu->kvm->arch.shadow_page_may_have_multiple_parents || + level == vcpu->arch.mmu->root_level) {
Might be worth a goto to preserve the for-loop.
Quoted 51 lines
arch/x86/kvm/mmu/mmu.c +26
-16+for_each_valid_sp (vcpu->kvm, sp, gfn) { +if (sp->gfn != gfn) { + collisions++; +continue ; + } -if (sp->role.word != role.word) -continue ; +if (!need_sync && sp->unsync) + need_sync = true; -if (sp->unsync) { -/* The page is good, but __kvm_sync_page might still end -* up zapping it. If so, break in order to rebuild it. -*/ -if (!__kvm_sync_page (vcpu, sp, &invalid_list)) -break ; +if (sp->role.word != role.word) +continue ; -WARN_ON (!list_empty (&invalid_list)); -kvm_make_request (KVM_REQ_TLB_FLUSH_CURRENT , vcpu); - } +if (sp->unsync) { +/* The page is good, but __kvm_sync_page might +* still end up zapping it. If so, break in +* order to rebuild it. +*/ +if (!__kvm_sync_page (vcpu, sp, &invalid_list)) +break ; -if (sp->unsync_children) -kvm_make_request (KVM_REQ_TLB_FLUSH_CURRENT , vcpu); +WARN_ON (!list_empty (&invalid_list)); +kvm_make_request (KVM_REQ_TLB_FLUSH_CURRENT , vcpu); + } -__clear_sp_write_flooding_count (sp); -trace_kvm_mmu_get_page (sp, false); - goto out; +if (sp->unsync_children) +kvm_make_request (KVM_REQ_TLB_FLUSH_CURRENT , vcpu); + +__clear_sp_write_flooding_count (sp); +trace_kvm_mmu_get_page (sp, false); + goto out; + } } ++vcpu->kvm->stat.mmu_cache_miss;
arch/x86/kvm/mmu/mmu.c static int mmu_alloc_shadow_roots(struct kvm_vcpu *vcpu) · line 3745
Quoted 6 lines
arch/x86/kvm/mmu/mmu.c +3
-0@@ -3735,6 +3740,10 @@ static int mmu_alloc_shadow_roots(struct kvm_vcpu *vcpu)gfn_t root_gfn, root_pgd;int i; +spin_lock (&vcpu->kvm->mmu_lock); + vcpu->kvm->arch.shadow_page_may_have_multiple_parents = true; +spin_unlock (&vcpu->kvm->mmu_lock);
Taking the lock every time is unnecessary, even if this is changed to a refcount type variable, e.g.
if (!has_indirect_mmu) {
lock_and_set
}or
if (atomic_inc_return(&indirect_mmu_count) == 1) lock_and_unlock;
Quoted 7 lines
arch/x86/kvm/mmu/mmu.c +1
-0+ root_pgd = vcpu->arch.mmu->get_guest_pgd (vcpu); root_gfn = root_pgd >>PAGE_SHIFT ;Signature · 1 line
2.26.2.303.gf8c07b1a785-goog
Quoted 33 lines · Sean Christopherson
Quoted 7 lines · Jon Cargille
From: Peter Feiner <[email protected]>
Optimization for avoiding lookups in
mmu_page_hash. When there's a single direct root, a shadow page has at most one parent SPTE (non-root SPs have exactly one; the root has none). Thus, if an SPTE is non-present, it can be linked to a newly allocated SP without first checking if the SP already exists.Some mechanical comments below. I'll think through the actual logic next week, my brain needs to be primed anytime the MMU is involved :-)
Quoted 20 lines
This optimization has proven significant in batch large SP shattering where the hash lookup accounted for 95% of the overhead.
Signed-off-by Peter Feiner <[email protected]>Signed-off-by Jon Cargille <[email protected]>Reviewed-by Jim Mattson <[email protected]>--- arch/x86/include/asm/kvm_host.h | 13 ++++++++ arch/x86/kvm/mmu/mmu.c | 55 +++++++++++++++++++-------------- 2 files changed, 45 insertions(+), 23 deletions(-)arch/x86/include/asm/kvm_host.h +0
-0@@ -913,6 +913,19 @@ struct kvm_arch {struct kvm_page_track_notifier_node mmu_sp_tracker;struct kvm_page_track_notifier_head track_notifier_head;
Quoted 15 lines
arch/x86/include/asm/kvm_host.h struct kvm_arch { · line 927
Quoted 12 lines
arch/x86/include/asm/kvm_host.h +12
-0+/* +* Optimization for avoiding lookups in mmu_page_hash. When there's a +* single direct root, a shadow page has at most one parent SPTE +* (non-root SPs have exactly one; the root has none). Thus, if an SPTE +* is non-present, it can be linked to a newly allocated SP without +* first checking if the SP already exists. +* +* False initially because there are no indirect roots. +* +* Guarded by mmu_lock. +*/ +bool shadow_page_may_have_multiple_parents;Why make this a one-way bool? Wouldn't it be better to let this transition back to '0' once all nested guests go away?
I made it one way because I didn't know how the shadow MMU worked in 2015 :-) I was concerned about not quite getting the transition back to '0' at the right point. I.e., what's the necessary set of conditions where we never have to look for a parent SP? Is it just when there are no indirect roots? Or could we be building some internal part of the tree despite there not being roots? TBH, now that it's been 12 months since I last thought _hard_ about the KVM MMU, it'd take some time for me to review these questions.
Quoted 3 lines
And maybe a shorter name that reflects what it tracks instead of how its used, e.g.
has_indirect_mmuorindirect_mmu_count.
Good idea.
Quoted 19 lines
Quoted 19 lines
arch/x86/include/asm/kvm_host.h +1
-0+struct list_head assigned_dev_head;struct iommu_domain *iommu_domain;bool iommu_noncoherent;arch/x86/kvm/mmu/mmu.c +0
-5@@ -2499,35 +2499,40 @@ static struct kvm_mmu_page *kvm_mmu_get_page(struct kvm_vcpu *vcpu, quadrant &= (1 << ((PT32_PT_BITS -PT64_PT_BITS ) * level)) -1 ; role.quadrant = quadrant; } -for_each_valid_sp (vcpu->kvm, sp, gfn) { -if (sp->gfn != gfn) { - collisions++; -continue ; - }
Quoted 6 lines
arch/x86/kvm/mmu/mmu.c static struct kvm_mmu_page *kvm_mmu_get_page(struct kvm_vcpu *vcpu, · line 2504
Quoted 4 lines
arch/x86/kvm/mmu/mmu.c +2
-2-if (!need_sync && sp->unsync) - need_sync = true; +if (vcpu->kvm->arch.shadow_page_may_have_multiple_parents || + level == vcpu->arch.mmu->root_level) {Might be worth a goto to preserve the for-loop.
Or factor out the guts of the loop into a function.
Quoted 62 lines
Quoted 52 lines
arch/x86/kvm/mmu/mmu.c +26
-16+for_each_valid_sp (vcpu->kvm, sp, gfn) { +if (sp->gfn != gfn) { + collisions++; +continue ; + } -if (sp->role.word != role.word) -continue ; +if (!need_sync && sp->unsync) + need_sync = true; -if (sp->unsync) { -/* The page is good, but __kvm_sync_page might still end -* up zapping it. If so, break in order to rebuild it. -*/ -if (!__kvm_sync_page (vcpu, sp, &invalid_list)) -break ; +if (sp->role.word != role.word) +continue ; -WARN_ON (!list_empty (&invalid_list)); -kvm_make_request (KVM_REQ_TLB_FLUSH_CURRENT , vcpu); - } +if (sp->unsync) { +/* The page is good, but __kvm_sync_page might +* still end up zapping it. If so, break in +* order to rebuild it. +*/ +if (!__kvm_sync_page (vcpu, sp, &invalid_list)) +break ; -if (sp->unsync_children) -kvm_make_request (KVM_REQ_TLB_FLUSH_CURRENT , vcpu); +WARN_ON (!list_empty (&invalid_list)); +kvm_make_request (KVM_REQ_TLB_FLUSH_CURRENT , vcpu); + } -__clear_sp_write_flooding_count (sp); -trace_kvm_mmu_get_page (sp, false); - goto out; +if (sp->unsync_children) +kvm_make_request (KVM_REQ_TLB_FLUSH_CURRENT , vcpu); + +__clear_sp_write_flooding_count (sp); +trace_kvm_mmu_get_page (sp, false); + goto out; + } } ++vcpu->kvm->stat.mmu_cache_miss;arch/x86/kvm/mmu/mmu.c static int mmu_alloc_shadow_roots(struct kvm_vcpu *vcpu) · line 3745
Quoted 6 lines
arch/x86/kvm/mmu/mmu.c +3
-0@@ -3735,6 +3740,10 @@ static int mmu_alloc_shadow_roots(struct kvm_vcpu *vcpu)gfn_t root_gfn, root_pgd;int i; +spin_lock (&vcpu->kvm->mmu_lock); + vcpu->kvm->arch.shadow_page_may_have_multiple_parents = true; +spin_unlock (&vcpu->kvm->mmu_lock);Taking the lock every time is unnecessary, even if this is changed to a refcount type variable, e.g.
Quoted 10 lines
if (!has_indirect_mmu) { lock_and_set }or
if (atomic_inc_return(&indirect_mmu_count) == 1) lock_and_unlock;
Indeed. Good suggestion.
Quoted 7 lines
Quoted 7 lines
arch/x86/kvm/mmu/mmu.c +1
-1+ root_pgd = vcpu->arch.mmu->get_guest_pgd (vcpu); root_gfn = root_pgd >>PAGE_SHIFT ; --2.26.2.303.gf8c07b1a785-goog
Quoted 12 lines · Peter Feiner
Quoted 10 lines · Sean Christopherson
Quoted 7 lines · Jon Cargille
From: Peter Feiner <[email protected]>
Optimization for avoiding lookups in
mmu_page_hash. When there's a single direct root, a shadow page has at most one parent SPTE (non-root SPs have exactly one; the root has none). Thus, if an SPTE is non-present, it can be linked to a newly allocated SP without first checking if the SP already exists.
Quoted 5 lines
Quoted 5 lines
Some mechanical comments below. I'll think through the actual logic next week, my brain needs to be primed anytime the MMU is involved :-)
Quoted 2 lines
This optimization has proven significant in batch large SP shattering where the hash lookup accounted for 95% of the overhead.
Is it the hash lookup or the hlist walk that is expensive? If it's the hash lookup, then a safer fix would be to do the hash lookup once in kvm_mmu_get_page() instead of doing it for both the walk and the insertion. Assuming, that's the case, I'll send a patch. Actually, I'll probably send a patch no matter what, I've been looking for an excuse to get rid of that obnoxiously long hash lookup line. :-)
Quoted 17 lines
Quoted 17 lines
Quoted 17 lines
Signed-off-by Peter Feiner <[email protected]>Signed-off-by Jon Cargille <[email protected]>Reviewed-by Jim Mattson <[email protected]>--- arch/x86/include/asm/kvm_host.h | 13 ++++++++ arch/x86/kvm/mmu/mmu.c | 55 +++++++++++++++++++-------------- 2 files changed, 45 insertions(+), 23 deletions(-)arch/x86/include/asm/kvm_host.h +0
-0@@ -913,6 +913,19 @@ struct kvm_arch {struct kvm_page_track_notifier_node mmu_sp_tracker;struct kvm_page_track_notifier_head track_notifier_head;
Quoted 6 lines
Quoted 6 lines
arch/x86/include/asm/kvm_host.h struct kvm_arch { · line 921
Quoted 6 lines
arch/x86/include/asm/kvm_host.h +6
-0+/* +* Optimization for avoiding lookups in mmu_page_hash. When there's a +* single direct root, a shadow page has at most one parent SPTE +* (non-root SPs have exactly one; the root has none). Thus, if an SPTE +* is non-present, it can be linked to a newly allocated SP without +* first checking if the SP already exists.
I'm pretty sure this will break due to the "zap oldest shadow page" behavior of make_mmu_pages_available() and mmu_shrink_scan(). In that case, KVM can zap a parent SP and leave a dangling child. If/when the zapped parent SP is rebuilt, it should find and relink the temporarily orphaned child. I believe the error will not actively manifest since the new, duplicate SP will be added to the front of the hlist, i.e. the newest entry will always be observed first. But, it will "leak" the child and all its children, at least until they get zapped in turn.
Hitting the above is probably extremely rare in the current code base. Presumably the make_mmu_pages_available() path is rarely hit, and the mmu_shrink_scan() path is basically broken (it zaps at most a single page after reporting to the scanner that it can potentially free thousands of pages; I'm working on a series).
One thought would be to zap the entire family tree when zapping a shadow page for a direct MMU. Then the above assumption would hold. I think that would be ok/safe-ish? It definitely would have "interesting" side effects.
Actually, there's another case that would break, though it's contrived and silly. If a VM is configured to have vCPUs with different physical address widths (yay KVM) and caused KVM to use both 4-level and 5-level EPT, then the "single direct root" rule above would be violated.
If we do get agressive and zap all children (or if my analysis is wrong), and prevent the mixed level insansity, then a simpler approach would be to skip the lookup if the MMU is direct. I.e. no need for the per-VM toggle. Direct vs. indirect MMUs are guaranteed to have different roles and so the direct MMU's pages can't be reused/shared.
Quoted 5 lines · Sean Christopherson
If we do get agressive and zap all children (or if my analysis is wrong), and prevent the mixed level insansity, then a simpler approach would be to skip the lookup if the MMU is direct. I.e. no need for the per-VM toggle. Direct vs. indirect MMUs are guaranteed to have different roles and so the direct MMU's pages can't be reused/shared.
Clarification on the above. Direct and not-guaranteed-to-be-direct MMUs for a given VM are guaranteed to have different roles, even for nested NPT vs. NPT, as nested MMUs will have role.guest_mode=1.