kvm: optimize GFN to memslot lookup with large slots amount

[deliverable/linux.git] / include / linux / kvm_host.h

diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index 231dd9472226639569f9f9cb7aefc26279bfbb01..193bca68372d3a73f08dd39288fa84a5a95df1b3 100644 (file)
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -353,6 +353,8 @@ struct kvm_memslots {
        struct kvm_memory_slot memslots[KVM_MEM_SLOTS_NUM];
        /* The mapping table from slot id to the index in memslots[]. */
        short id_to_index[KVM_MEM_SLOTS_NUM];
+       atomic_t lru_slot;
+       int used_slots;
 };
 
 struct kvm {
@@ -790,12 +792,28 @@ static inline void kvm_guest_exit(void)
 static inline struct kvm_memory_slot *
 search_memslots(struct kvm_memslots *slots, gfn_t gfn)
 {
-       struct kvm_memory_slot *memslot;
+       int start = 0, end = slots->used_slots;
+       int slot = atomic_read(&slots->lru_slot);
+       struct kvm_memory_slot *memslots = slots->memslots;
 
-       kvm_for_each_memslot(memslot, slots)
-               if (gfn >= memslot->base_gfn &&
-                     gfn < memslot->base_gfn + memslot->npages)
-                       return memslot;
+       if (gfn >= memslots[slot].base_gfn &&
+           gfn < memslots[slot].base_gfn + memslots[slot].npages)
+               return &memslots[slot];
+
+       while (start < end) {
+               slot = start + (end - start) / 2;
+
+               if (gfn >= memslots[slot].base_gfn)
+                       end = slot;
+               else
+                       start = slot + 1;
+       }
+
+       if (gfn >= memslots[start].base_gfn &&
+           gfn < memslots[start].base_gfn + memslots[start].npages) {
+               atomic_set(&slots->lru_slot, start);
+               return &memslots[start];
+       }
 
        return NULL;
 }