kvm: x86: increase user memory slots to 509

With the 3 private slots, this gives us 512 slots total. Motivation for this is in addition to assigned devices support more memory hotplug slots, where 1 slot is used by a hotplugged memory stick.
It will allow to support upto 256 hotplug memory slots and leave 253 slots for assigned devices and other devices that use them.

Signed-off-by Igor Mammedov <[email protected]>

memslots is a sorted array, when slot changes in it with current heapsort it would take O(n log n) time to update array, while using insertion sort like algorithm on array with 1 item out of order will take only O(n) time.

Replace current heapsort with custom sort that takes advantage of memslots usage pattern and known position of changed slot.

performance change of 128 memslots insersions with gradually increasing size (the worst case):

      heap sort   custom sort
max:  249747      15654 cycles
min:  52536       5562 cycles

with custom sort alg taking 90% less then original update time.

Signed-off-by Igor Mammedov <[email protected]>

---
 virt/kvm/kvm_main.c | 54 +++++++++++++++++++++++++++++------------------------
 1 file changed, 30 insertions(+), 24 deletions(-)

memslots is a sorted array, when slot changes in it with current heapsort it would take O(n log n) time to update array, while using insertion sort like algorithm on array with 1 item out of order will take only O(n) time.

Replace current heapsort with custom sort that takes advantage of memslots usage pattern and known position of changed slot.

performance change of 128 memslots insersions with gradually increasing size (the worst case):
heap sort custom sort
max: 249747 2500 cycles
with custom sort alg taking ~98% less then original update time.

Signed-off-by Igor Mammedov <[email protected]>

---
v2:
- replace swap with slot shift, improves result 2x
- reprofile original/swap based and swapless 15 times discarding spikes swap based takes ~5900 cycles max and swapless ~2500 cycles.

---
 virt/kvm/kvm_main.c | 54 ++++++++++++++++++++++++++---------------------------
 1 file changed, 26 insertions(+), 28 deletions(-)

virt/kvm/kvm_main.c +4 -17

index 25ffac9..49f896a 100644
@@ -668,31 +668,35 @@ static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot)
 	return 0;
 }
 
-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->npages < s2->npages)
-		return 1;
-	if (s1->npages > s2->npages)
-		return -1;
-
-	return 0;
-}
-
 /*
- * Sort the memslots base on its size, so the larger slots
- * will get better fit.
+ * 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.

virt/kvm/kvm_main.c +14 -9

-	sort(slots->memslots, KVM_MEM_SLOTS_NUM,
-	      sizeof(struct kvm_memory_slot), cmp_memslot, NULL);
+	while (1) {
+		if (i < (KVM_MEM_SLOTS_NUM - 1) &&
+			new->npages < mslots[i + 1].npages) {
+			mslots[i] = mslots[i + 1];
+			i++;
+		} else if (i > 0 && new->npages > mslots[i - 1].npages) {
+			mslots[i] = mslots[i - 1];
+			i--;
+		} else {
+			mslots[i] = *new;
+			break;
+		}
+	}
 
 	for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
 		slots->id_to_index[slots->memslots[i].id] = i;

@@ -702,13 +706,7 @@ static void update_memslots(struct kvm_memslots *slots,
 			    struct kvm_memory_slot *new)
 {
 	if (new) {
-		int id = new->id;
-		struct kvm_memory_slot *old = id_to_memslot(slots, id);
-		unsigned long npages = old->npages;
-
-		*old = *new;
-		if (new->npages != npages)
-			sort_memslots(slots);
+		insert_memslot(slots, new);
 	}
 }
 

Quoted 60 lines · Igor Mammedov

memslots is a sorted array, when slot changes in it with current heapsort it would take O(n log n) time to update array, while using insertion sort like algorithm on array with 1 item out of order will take only O(n) time.

Replace current heapsort with custom sort that takes advantage of memslots usage pattern and known position of changed slot.

performance change of 128 memslots insersions with gradually increasing size (the worst case):
heap sort custom sort
max: 249747 2500 cycles
with custom sort alg taking ~98% less then original update time.

Signed-off-by Igor Mammedov <[email protected]>

---
v2:
- replace swap with slot shift, improves result 2x
- reprofile original/swap based and swapless 15 times discarding spikes swap based takes ~5900 cycles max and swapless ~2500 cycles.

---
 virt/kvm/kvm_main.c | 54

++++++++++++++++++++++++++--------------------------- 1 file changed, 26 insertions(+), 28 deletions(-)

virt/kvm/kvm_main.c +4 -17

index 25ffac9..49f896a 100644
@@ -668,31 +668,35 @@ static int kvm_create_dirty_bitmap(struct
 kvm_memory_slot *memslot) return 0;
 }
 
-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->npages < s2->npages)
-		return 1;
-	if (s1->npages > s2->npages)
-		return -1;
-
-	return 0;
-}
-
 /*
- * Sort the memslots base on its size, so the larger slots
- * will get better fit.
+ * 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.
  */

virt/kvm/kvm_main.c static int kvm_create_dirty_bitmap(struct · line 684

Quoted 10 lines

virt/kvm/kvm_main.c +6 -2

-static void sort_memslots(struct kvm_memslots *slots)
+static void insert_memslot(struct kvm_memslots *slots,
+			   struct kvm_memory_slot *new)
 {
-	int i;
+	int i = slots->id_to_index[new->id];
+	struct kvm_memory_slot *old = id_to_memslot(slots,
 new->id);
+	struct kvm_memory_slot *mslots = slots->memslots;
+

It is important to leave the "*old = *new" assignment here, see the comment in __kvm_set_memory_region:

/*
* 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. */

This small problem was already present in v1, but I didn't notice it yesterday. With the new code, we can add it inside this if:

virt/kvm/kvm_main.c static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot) · line 685

Quoted 2 lines

virt/kvm/kvm_main.c +2 -0

+	if (new->npages == old->npages)
+		return;

Do you agree? (No need to send v3).

Paolo

Quoted 36 lines

virt/kvm/kvm_main.c +13 -2

-	sort(slots->memslots, KVM_MEM_SLOTS_NUM,
-	      sizeof(struct kvm_memory_slot), cmp_memslot, NULL);
+	while (1) {
+		if (i < (KVM_MEM_SLOTS_NUM - 1) &&
+			new->npages < mslots[i + 1].npages) {
+			mslots[i] = mslots[i + 1];
+			i++;
+		} else if (i > 0 && new->npages > mslots[i -
 1].npages) {
+			mslots[i] = mslots[i - 1];
+			i--;
+		} else {
+			mslots[i] = *new;
+			break;
+		}
+	}
 
 	for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)

virt/kvm/kvm_main.c +1 -7

 		slots->id_to_index[slots->memslots[i].id] = i;

@@ -702,13 +706,7 @@ static void update_memslots(struct
 kvm_memslots *slots, struct kvm_memory_slot *new)
 {
 	if (new) {
-		int id = new->id;
-		struct kvm_memory_slot *old = id_to_memslot(slots,
 id);
-		unsigned long npages = old->npages;
-
-		*old = *new;
-		if (new->npages != npages)
-			sort_memslots(slots);
+		insert_memslot(slots, new);
 	}
 }

Quoted 8 lines · Igor Mammedov

With the 3 private slots, this gives us 512 slots total. Motivation for this is in addition to assigned devices support more memory hotplug slots, where 1 slot is used by a hotplugged memory stick.
It will allow to support upto 256 hotplug memory slots and leave 253 slots for assigned devices and other devices that use them.

Quoted 1 line

Signed-off-by Igor Mammedov <[email protected]>

It would use more memory, and some loops are now becoming more expensive. In general adding a memory slot to a VM is not cheap, and I question the wisdom of having 256 hotplug memory slots. But the slowdown mostly would only happen if you actually _use_ those memory slots, so it is not a blocker for this patch.

Paolo

Quoted 5 lines · On Thu, 06 Nov 2014 17:23:58 +0100 Paolo Bonzini <[email protected]> wrote:

It would use more memory, and some loops are now becoming more expensive. In general adding a memory slot to a VM is not cheap, and I question the wisdom of having 256 hotplug memory slots. But the slowdown mostly would only happen if you actually _use_ those memory slots, so it is not a blocker for this patch.

It might be useful to have a big amount of slots for big guests and although linux works with minimum section 128Mb but Windows memory hotplug works just fine even with page-sized slots so when unplug in QEMU is implemented it would be possible to drop balooning driver at least there.

And providing that memslots could be allocated during runtime when guest programs devices or maps roms (i.e. no fail path), I don't see a way to fix it in QEMU (i.e. avoid abort when limit is reached). Hence an attempt to bump memslots limit to 512, where current 125 are reserved for initial memory mappings and passthrough devices 256 goes to hotplug memory slots and leaves us 128 free slots for future expansion.

To see what would be affected by large amount of slots I played with perf a bit and the biggest hotspot offender with large amount of memslots was:

gfn_to_memslot() -> ... -> search_memslots()

I'll try to make it faster for this case so 512 memslots wouldn't affect guest performance.

So please consider applying this patch.