Re: [PATCH v5.5 24/30] KVM: Use interval tree to do fast hva lookup in memslots

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On 04.11.2021 01:25, Sean Christopherson wrote:
From: Maciej S. Szmigiero <maciej.szmigiero@xxxxxxxxxx>

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 <maciej.szmigiero@xxxxxxxxxx>
[sean: handle interval tree updates in kvm_replace_memslot()]
Signed-off-by: Sean Christopherson <seanjc@xxxxxxxxxx>
---
  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(-)

(..)
@@ -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



[Index of Archives]     [KVM ARM]     [KVM ia64]     [KVM ppc]     [Virtualization Tools]     [Spice Development]     [Libvirt]     [Libvirt Users]     [Linux USB Devel]     [Linux Audio Users]     [Yosemite Questions]     [Linux Kernel]     [Linux SCSI]     [XFree86]

  Powered by Linux