[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <1417454967-4465-5-git-send-email-imammedo@redhat.com>
Date: Mon, 1 Dec 2014 17:29:26 +0000
From: Igor Mammedov <imammedo@...hat.com>
To: linux-kernel@...r.kernel.org
Cc: pbonzini@...hat.com, kvm@...r.kernel.org
Subject: [PATCH 4/5] 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@...hat.com>
---
virt/kvm/kvm_main.c | 17 +++++++++++------
1 file changed, 11 insertions(+), 6 deletions(-)
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 278ed65..162817f 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--;
--
1.8.3.1
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists