kvm: change memslot sorting rule from size to GFN

it will allow to use binary search for GFN -> memslot
lookups, reducing lookup cost with large slots amount.

Signed-off-by: Igor Mammedov <imammedo@redhat.com>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>

1 files changed, 11 insertions, 6 deletions

diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 278ed65cc9c5..162817f853ec 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -666,10 +666,10 @@ static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot)
 }
 
 /*
- * Insert memslot and re-sort memslots based on their size,
- * so the larger slots will get better fit. Sorting algorithm
- * takes advantage of having initially sorted array and
- * known changed memslot position.
+ * Insert memslot and re-sort memslots based on their GFN,
+ * so binary search could be used to lookup GFN.
+ * Sorting algorithm takes advantage of having initially
+ * sorted array and known changed memslot position.
  */
 static void update_memslots(struct kvm_memslots *slots,
 			    struct kvm_memory_slot *new)
@@ -679,14 +679,19 @@ static void update_memslots(struct kvm_memslots *slots,
 	struct kvm_memory_slot *mslots = slots->memslots;
 
 	WARN_ON(mslots[i].id != id);
+	if (!new->npages)
+		new->base_gfn = 0;
+
 	while (i < KVM_MEM_SLOTS_NUM - 1 &&
-	       new->npages < mslots[i + 1].npages) {
+	       new->base_gfn <= mslots[i + 1].base_gfn) {
+		if (!mslots[i + 1].npages)
+			break;
 		mslots[i] = mslots[i + 1];
 		slots->id_to_index[mslots[i].id] = i;
 		i++;
 	}
 	while (i > 0 &&
-	       new->npages > mslots[i - 1].npages) {
+	       new->base_gfn > mslots[i - 1].base_gfn) {
 		mslots[i] = mslots[i - 1];
 		slots->id_to_index[mslots[i].id] = i;
 		i--;