kvm: optimize GFN to memslot lookup with large slots amount

[deliverable/linux.git] / virt / kvm / kvm_main.c

diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index eae07f97ecf70dd6b0d6621dd1d89a3935b3ccc8..759af6596a07ec10fd3e54f5c49e8b195a195df0 100644 (file)
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -468,9 +468,6 @@ static struct kvm *kvm_create_vm(unsigned long type)
        if (r)
                goto out_err_no_disable;
 
-#ifdef CONFIG_HAVE_KVM_IRQCHIP
-       INIT_HLIST_HEAD(&kvm->mask_notifier_list);
-#endif
 #ifdef CONFIG_HAVE_KVM_IRQFD
        INIT_HLIST_HEAD(&kvm->irq_ack_notifier_list);
 #endif
@@ -669,49 +666,47 @@ 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 insert_memslot(struct kvm_memslots *slots,
-                          struct kvm_memory_slot *new)
+static void update_memslots(struct kvm_memslots *slots,
+                           struct kvm_memory_slot *new)
 {
        int id = new->id;
        int i = slots->id_to_index[id];
        struct kvm_memory_slot *mslots = slots->memslots;
 
        WARN_ON(mslots[i].id != id);
-       if (new->npages != mslots[i].npages) {
-               if (new->npages < mslots[i].npages) {
-                       while (i < KVM_MEM_SLOTS_NUM - 1 &&
-                              new->npages < mslots[i + 1].npages) {
-                               mslots[i] = mslots[i + 1];
-                               slots->id_to_index[mslots[i].id] = i;
-                               i++;
-                       }
-               } else {
-                       while (i > 0 &&
-                              new->npages > mslots[i - 1].npages) {
-                               mslots[i] = mslots[i - 1];
-                               slots->id_to_index[mslots[i].id] = i;
-                               i--;
-                       }
-               }
+       if (!new->npages) {
+               new->base_gfn = 0;
+               if (mslots[i].npages)
+                       slots->used_slots--;
+       } else {
+               if (!mslots[i].npages)
+                       slots->used_slots++;
+       }
+
+       while (i < KVM_MEM_SLOTS_NUM - 1 &&
+              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->base_gfn > mslots[i - 1].base_gfn) {
+               mslots[i] = mslots[i - 1];
+               slots->id_to_index[mslots[i].id] = i;
+               i--;
        }
 
        mslots[i] = *new;
        slots->id_to_index[mslots[i].id] = i;
 }
 
-static void update_memslots(struct kvm_memslots *slots,
-                           struct kvm_memory_slot *new)
-{
-       if (new) {
-               insert_memslot(slots, new);
-       }
-}
-
 static int check_memory_region_flags(struct kvm_userspace_memory_region *mem)
 {
        u32 valid_flags = KVM_MEM_LOG_DIRTY_PAGES;
@@ -727,7 +722,7 @@ static int check_memory_region_flags(struct kvm_userspace_memory_region *mem)
 }
 
 static struct kvm_memslots *install_new_memslots(struct kvm *kvm,
-               struct kvm_memslots *slots, struct kvm_memory_slot *new)
+               struct kvm_memslots *slots)
 {
        struct kvm_memslots *old_memslots = kvm->memslots;
 
@@ -738,7 +733,6 @@ static struct kvm_memslots *install_new_memslots(struct kvm *kvm,
        WARN_ON(old_memslots->generation & 1);
        slots->generation = old_memslots->generation + 1;
 
-       update_memslots(slots, new);
        rcu_assign_pointer(kvm->memslots, slots);
        synchronize_srcu_expedited(&kvm->srcu);
 
@@ -866,15 +860,16 @@ int __kvm_set_memory_region(struct kvm *kvm,
                        goto out_free;
        }
 
+       slots = kmemdup(kvm->memslots, sizeof(struct kvm_memslots),
+                       GFP_KERNEL);
+       if (!slots)
+               goto out_free;
+
        if ((change == KVM_MR_DELETE) || (change == KVM_MR_MOVE)) {
-               slots = kmemdup(kvm->memslots, sizeof(struct kvm_memslots),
-                               GFP_KERNEL);
-               if (!slots)
-                       goto out_free;
                slot = id_to_memslot(slots, mem->slot);
                slot->flags |= KVM_MEMSLOT_INVALID;
 
-               old_memslots = install_new_memslots(kvm, slots, NULL);
+               old_memslots = install_new_memslots(kvm, slots);
 
                /* slot was deleted or moved, clear iommu mapping */
                kvm_iommu_unmap_pages(kvm, &old);
@@ -886,6 +881,12 @@ int __kvm_set_memory_region(struct kvm *kvm,
                 *      - kvm_is_visible_gfn (mmu_check_roots)
                 */
                kvm_arch_flush_shadow_memslot(kvm, slot);
+
+               /*
+                * We can re-use the old_memslots from above, the only difference
+                * from the currently installed memslots is the invalid flag.  This
+                * will get overwritten by update_memslots anyway.
+                */
                slots = old_memslots;
        }
 
@@ -893,26 +894,14 @@ int __kvm_set_memory_region(struct kvm *kvm,
        if (r)
                goto out_slots;
 
-       r = -ENOMEM;
-       /*
-        * We can re-use the old_memslots from above, the only difference
-        * from the currently installed memslots is the invalid flag.  This
-        * will get overwritten by update_memslots anyway.
-        */
-       if (!slots) {
-               slots = kmemdup(kvm->memslots, sizeof(struct kvm_memslots),
-                               GFP_KERNEL);
-               if (!slots)
-                       goto out_free;
-       }
-
        /* actual memory is freed via old in kvm_free_physmem_slot below */
        if (change == KVM_MR_DELETE) {
                new.dirty_bitmap = NULL;
                memset(&new.arch, 0, sizeof(new.arch));
        }
 
-       old_memslots = install_new_memslots(kvm, slots, &new);
+       update_memslots(slots, &new);
+       old_memslots = install_new_memslots(kvm, slots);
 
        kvm_arch_commit_memory_region(kvm, mem, &old, change);
 
@@ -2599,8 +2588,6 @@ static long kvm_vm_ioctl(struct file *filp,
                break;
        default:
                r = kvm_arch_vm_ioctl(filp, ioctl, arg);
-               if (r == -ENOTTY)
-                       r = kvm_vm_ioctl_assigned_device(kvm, ioctl, arg);
        }
 out:
        return r;