Re: [PATCH v5.5 24/30] KVM: Use interval tree to do fast hva lookup in memslots
From: Maciej S. Szmigiero <hidden>
Date: 2021-11-11 23:53:13
Also in:
kvm, kvm-riscv, kvmarm, linux-mips, linux-riscv, lkml
On 04.11.2021 01:25, Sean Christopherson wrote:
From: Maciej S. Szmigiero <redacted> 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. Signed-off-by: Maciej S. Szmigiero <redacted> [sean: handle interval tree updates in kvm_replace_memslot()] Signed-off-by: Sean Christopherson <seanjc@google.com> --- arch/arm64/kvm/Kconfig | 1 + arch/mips/kvm/Kconfig | 1 + arch/powerpc/kvm/Kconfig | 1 + arch/s390/kvm/Kconfig | 1 + arch/x86/kvm/Kconfig | 1 + include/linux/kvm_host.h | 3 ++ virt/kvm/kvm_main.c | 60 +++++++++++++++++++++++++++++----------- 7 files changed, 52 insertions(+), 16 deletions(-)
(..)
quoted hunk ↗ jump to hunk
@@ -1262,22 +1274,32 @@ static void kvm_replace_memslot(struct kvm_memslots *slots, struct kvm_memory_slot *new) { /* - * Remove the old memslot from the hash list, copying the node data - * would corrupt the list. + * Remove the old memslot from the hash list and interval tree, copying + * the node data would corrupt the structures. */ if (old) { hash_del(&old->id_node); + interval_tree_remove(&old->hva_node, &slots->hva_tree); if (!new) return; } - /* Copy the source *data*, not the pointer, to the destination. */ - if (old) + /* + * Copy the source *data*, not the pointer, to the destination. If + * @old is NULL, initialize @new's hva range. + */ + if (old) { *new = *old; + } else if (new) {
Unnecessary check - if "new" is NULL then the code will crash anyway accessing this pointer unconditionally...
+ new->hva_node.start = new->userspace_addr; + new->hva_node.last = new->userspace_addr + + (new->npages << PAGE_SHIFT) - 1; + } /* (Re)Add the new memslot. */ hash_add(slots->id_hash, &new->id_node, new->id); + interval_tree_insert(&new->hva_node, &slots->hva_tree);
...in these two lines above. Thanks, Maciej _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel