diff options
| author | Maciej S. Szmigiero <maciej.szmigiero@oracle.com> | 2021-12-06 20:54:28 +0100 |
|---|---|---|
| committer | Paolo Bonzini <pbonzini@redhat.com> | 2021-12-08 04:24:32 -0500 |
| commit | ed922739c9199bf515a3e7fec3e319ce1edeef2a (patch) | |
| tree | 287fba29b9f4f72147c4db889723274e3e7269f1 /include | |
| parent | 26b8345abc75a7404716864710930407b7d873f9 (diff) | |
| download | linux-ed922739c9199bf515a3e7fec3e319ce1edeef2a.tar.bz2 | |
KVM: Use interval tree to do fast hva lookup in memslots
The current memslots implementation only allows quick binary search by gfn,
quick lookup by hva is not possible - the implementation has to do a linear
scan of the whole memslots array, even though the operation being performed
might apply just to a single memslot.
This significantly hurts performance of per-hva operations with higher
memslot counts.
Since hva ranges can overlap between memslots an interval tree is needed
for tracking them.
[sean: handle interval tree updates in kvm_replace_memslot()]
Signed-off-by: Maciej S. Szmigiero <maciej.szmigiero@oracle.com>
Message-Id: <d66b9974becaa9839be9c4e1a5de97b177b4ac20.1638817640.git.maciej.szmigiero@oracle.com>
Diffstat (limited to 'include')
| -rw-r--r-- | include/linux/kvm_host.h | 3 |
1 files changed, 3 insertions, 0 deletions
diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h index 79db70a8323e..9552ad6d6652 100644 --- a/include/linux/kvm_host.h +++ b/include/linux/kvm_host.h @@ -30,6 +30,7 @@ #include <linux/nospec.h> #include <linux/notifier.h> #include <linux/hashtable.h> +#include <linux/interval_tree.h> #include <linux/xarray.h> #include <asm/signal.h> @@ -428,6 +429,7 @@ static inline int kvm_vcpu_exiting_guest_mode(struct kvm_vcpu *vcpu) struct kvm_memory_slot { struct hlist_node id_node; + struct interval_tree_node hva_node; gfn_t base_gfn; unsigned long npages; unsigned long *dirty_bitmap; @@ -529,6 +531,7 @@ static inline int kvm_arch_vcpu_memslots_id(struct kvm_vcpu *vcpu) */ struct kvm_memslots { u64 generation; + struct rb_root_cached hva_tree; /* * The mapping table from slot id to the index in memslots[]. * |