lkml.org 
[lkml]   [2011]   [Feb]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[PATCH 4/7] KVM: sort memslots and use binary search to search the right slot
Sort memslots then search the slot with binary search to speed up the
slot searching

Signed-off-by: Xiao Guangrong <xiaoguangrong@cn.fujitsu.com>
---
include/linux/kvm_host.h | 2 +
virt/kvm/kvm_main.c | 85 ++++++++++++++++++++++++++++++++++------------
2 files changed, 65 insertions(+), 22 deletions(-)
diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index 15ff818..f1963a4 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -223,8 +223,10 @@ struct kvm_irq_routing_table {};

struct kvm_memslots {
int nmemslots;
+ int used_slots;
u64 generation;
struct kvm_memory_slot memslots[KVM_MEM_SLOTS_NUM];
+ struct kvm_memory_slot *slots_sort[KVM_MEM_SLOTS_NUM];
};

struct kvm {
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index e1c6e24..0795426 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -47,6 +47,7 @@
#include <linux/srcu.h>
#include <linux/hugetlb.h>
#include <linux/slab.h>
+#include <linux/sort.h>

#include <asm/processor.h>
#include <asm/io.h>
@@ -623,11 +624,67 @@ static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot)
}
#endif /* !CONFIG_S390 */

+static int cmp_memslot(const void *slot1, const void *slot2)
+{
+ struct kvm_memory_slot *s1, *s2;
+
+ s1 = *(struct kvm_memory_slot **)slot1;
+ s2 = *(struct kvm_memory_slot **)slot2;
+
+ if (s1->base_gfn > s2->base_gfn)
+ return 1;
+ if (s1->base_gfn < s2->base_gfn)
+ return -1;
+
+ return 0;
+}
+
+static struct kvm_memory_slot *search_memslots(struct kvm_memslots *slots,
+ gfn_t gfn)
+{
+ int start = 0, end = slots->used_slots, idx;
+ struct kvm_memory_slot *memslot;
+
+ while (start < end) {
+ idx = (start + end) / 2;
+ memslot = slots->slots_sort[idx];
+
+ if (gfn >= memslot->base_gfn &&
+ gfn < memslot->base_gfn + memslot->npages)
+ return memslot;
+
+ if (memslot->base_gfn < gfn)
+ start = idx + 1;
+ else
+ end = idx;
+ }
+
+ return NULL;
+}
+
+static void sort_memslots(struct kvm_memslots *slots)
+{
+ int i, num = 0;
+ struct kvm_memory_slot *memslot;
+
+ for (i = 0; i < slots->nmemslots; i++) {
+ memslot = &slots->memslots[i];
+ if (!memslot->npages)
+ continue;
+
+ slots->slots_sort[num++] = memslot;
+ }
+
+ slots->used_slots = num;
+ sort(slots->slots_sort, num, sizeof(memslot), cmp_memslot, NULL);
+}
+
void memslots_updated(struct kvm_memslots *slots, int slot_id)
{
if (slot_id >= slots->nmemslots)
slots->nmemslots = slot_id + 1;
slots->generation++;
+ sort_memslots(slots);
}

/*
@@ -939,16 +996,7 @@ EXPORT_SYMBOL_GPL(kvm_is_error_hva);
static struct kvm_memory_slot *__gfn_to_memslot(struct kvm_memslots *slots,
gfn_t gfn)
{
- int i;
-
- for (i = 0; i < slots->nmemslots; ++i) {
- struct kvm_memory_slot *memslot = &slots->memslots[i];
-
- if (gfn >= memslot->base_gfn
- && gfn < memslot->base_gfn + memslot->npages)
- return memslot;
- }
- return NULL;
+ return search_memslots(slots, gfn);
}

struct kvm_memory_slot *gfn_to_memslot(struct kvm *kvm, gfn_t gfn)
@@ -959,20 +1007,13 @@ EXPORT_SYMBOL_GPL(gfn_to_memslot);

int kvm_is_visible_gfn(struct kvm *kvm, gfn_t gfn)
{
- int i;
- struct kvm_memslots *slots = kvm_memslots(kvm);
+ struct kvm_memory_slot *memslot = gfn_to_memslot(kvm, gfn);

- for (i = 0; i < KVM_MEMORY_SLOTS; ++i) {
- struct kvm_memory_slot *memslot = &slots->memslots[i];
-
- if (memslot->flags & KVM_MEMSLOT_INVALID)
- continue;
+ if (!memslot || memslot->id > KVM_MEMORY_SLOTS ||
+ memslot->flags & KVM_MEMSLOT_INVALID)
+ return 0;

- if (gfn >= memslot->base_gfn
- && gfn < memslot->base_gfn + memslot->npages)
- return 1;
- }
- return 0;
+ return 1;
}
EXPORT_SYMBOL_GPL(kvm_is_visible_gfn);

--
1.7.4


\
 
 \ /
  Last update: 2011-02-22 09:13    [from the cache]
©2003-2011 Jasper Spaans