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    [W:0.026 / U:26.048 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site