Sort memslots then search the slot with binary search to speed up the slot searching
Signed-off-by: Xiao Guangrong <[email protected]> --- 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 -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
