kvm: fix to update memslots properly

This suggests another fix. We can change the insertion to use a ">=" comparison, as in your first patch. Alone it is not correct, but we only need to take some care and avoid breaking the case of deleting a memslot.

It's enough to wrap the second loop (that you patched) with "if (new->npages)". In the new->npages == 0 case the first loop has already set i to the right value, and moving i back would be wrong:

virt/kvm/kvm_main.c +10 -5

index f5283438ee05..050974c051b5 100644
@@ -687,11 +687,23 @@ static void update_memslots(struct kvm_memslots *slots,
 		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--;
+
+	/*
+	 * The ">=" is needed when creating a slot with base_gfn == 0,
+	 * so that it moves before all those with base_gfn == npages == 0.
+	 *
+	 * On the other hand, if new->npages is zero, the above loop has
+	 * already left i pointing to the beginning of the empty part of
+	 * mslots, and the ">=" would move the hole backwards in this
+	 * case---which is wrong.  So skip the loop when deleting a slot.
+	 */

virt/kvm/kvm_main.c static void update_memslots(struct kvm_memslots *slots, · line 678

Quoted 12 lines

virt/kvm/kvm_main.c +1 -0

index f528343..6e52f3f 100644
@@ -672,6 +672,7 @@ static void update_memslots(struct kvm_memslots *slots,
  	WARN_ON(mslots[i].id != id);
  	if (!new->npages) {
  		new->base_gfn = 0;
+		new->flags = 0;
  		if (mslots[i].npages)
  			slots->used_slots--;
  	} else {

This should not be necessary. The part of the mslots array that has base_gfn == npages == 0 is entirely unused, and such a slot can never be returned by search_memslots because this:

if (gfn >= memslots[slot].base_gfn &&
gfn < memslots[slot].base_gfn + memslots[slot].npages)

can never be true.

virt/kvm/kvm_main.c static void update_memslots(struct kvm_memslots *slots, · line 697

Quoted 13 lines

virt/kvm/kvm_main.c +3 -1

@@ -688,7 +689,9 @@ static void update_memslots(struct kvm_memslots *slots,
  		i++;
  	}
  	while (i > 0 &&
-	       new->base_gfn > mslots[i - 1].base_gfn) {
+	       ((new->base_gfn > mslots[i - 1].base_gfn) ||
+	        (!new->base_gfn &&
+	         !mslots[i - 1].base_gfn && !mslots[i - 1].npages))) {
  		mslots[i] = mslots[i - 1];
  		slots->id_to_index[mslots[i].id] = i;
  		i--;

You should have explained _why_ this fixes the bug, and what invariant

is not being respected, something like this:

kvm: fix sorting of memslots with base_gfn == 0

Before commit 0e60b0799fed (kvm: change memslot sorting rule from size to GFN, 2014-12-01), the memslots' sorting key was npages, meaning that a valid memslot couldn't have its sorting key equal to zero. On the other hand, a valid memslot can have base_gfn == 0, and invalid memslots are identified by base_gfn == npages == 0.

Because of this, commit 0e60b0799fed broke the invariant that invalid memslots are at the end of the mslots array. When a memslot with base_gfn == 0 was created, any invalid memslot before it were left in place.

This suggests another fix. We can change the insertion to use a ">=" comparison, as in your first patch. Alone it is not correct, but we only need to take some care and avoid breaking the case of deleting a memslot.

It's enough to wrap the second loop (that you patched) with "if (new->npages)". In the new->npages == 0 case the first loop has already set i to the right value, and moving i back would be wrong:

virt/kvm/kvm_main.c +10 -5

index f5283438ee05..050974c051b5 100644
@@ -687,11 +687,23 @@ static void update_memslots(struct kvm_memslots *slots,
  		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--;
+
+	/*
+	 * The ">=" is needed when creating a slot with base_gfn == 0,
+	 * so that it moves before all those with base_gfn == npages == 0.
+	 *
+	 * On the other hand, if new->npages is zero, the above loop has
+	 * already left i pointing to the beginning of the empty part of
+	 * mslots, and the ">=" would move the hole backwards in this
+	 * case---which is wrong.  So skip the loop when deleting a slot.
+	 */

virt/kvm/kvm_main.c static void update_memslots(struct kvm_memslots *slots, · line 678

Quoted 12 lines

virt/kvm/kvm_main.c +1 -0

index f528343..6e52f3f 100644
@@ -672,6 +672,7 @@ static void update_memslots(struct kvm_memslots *slots,
 	WARN_ON(mslots[i].id != id);
 	if (!new->npages) {
 		new->base_gfn = 0;
+		new->flags = 0;
 		if (mslots[i].npages)
 			slots->used_slots--;
 	} else {

This should not be necessary. The part of the mslots array that has base_gfn == npages == 0 is entirely unused, and such a slot can never be returned by search_memslots because this:

if (gfn >= memslots[slot].base_gfn &&
gfn < memslots[slot].base_gfn + memslots[slot].npages)

can never be true.

virt/kvm/kvm_main.c static void update_memslots(struct kvm_memslots *slots, · line 697

Quoted 12 lines

virt/kvm/kvm_main.c +3 -1

@@ -688,7 +689,9 @@ static void update_memslots(struct kvm_memslots *slots,
 		i++;
 	}
 	while (i > 0 &&
-	       new->base_gfn > mslots[i - 1].base_gfn) {
+	       ((new->base_gfn > mslots[i - 1].base_gfn) ||
+	        (!new->base_gfn &&
+	         !mslots[i - 1].base_gfn && !mslots[i - 1].npages))) {
 		mslots[i] = mslots[i - 1];
 		slots->id_to_index[mslots[i].id] = i;
 		i--;

You should have explained _why_ this fixes the bug, and what invariant is not being respected, something like this:

kvm: fix sorting of memslots with base_gfn == 0

Before commit 0e60b0799fed (kvm: change memslot sorting rule from size to GFN, 2014-12-01), the memslots' sorting key was npages, meaning that a valid memslot couldn't have its sorting key equal to zero. On the other hand, a valid memslot can have base_gfn == 0, and invalid memslots are identified by base_gfn == npages == 0.

Because of this, commit 0e60b0799fed broke the invariant that invalid memslots are at the end of the mslots array. When a memslot with base_gfn == 0 was created, any invalid memslot before it were left in place.

This suggests another fix. We can change the insertion to use a ">=" comparison, as in your first patch. Alone it is not correct, but we only need to take some care and avoid breaking the case of deleting a memslot.

It's enough to wrap the second loop (that you patched) with "if (new->npages)". In the new->npages == 0 case the first loop has already set i to the right value, and moving i back would be wrong:

virt/kvm/kvm_main.c +17 -5

index f5283438ee05..050974c051b5 100644
@@ -687,11 +687,23 @@ static void update_memslots(struct kvm_memslots *slots,
 		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--;
+
+	/*
+	 * The ">=" is needed when creating a slot with base_gfn == 0,
+	 * so that it moves before all those with base_gfn == npages == 0.
+	 *
+	 * On the other hand, if new->npages is zero, the above loop has
+	 * already left i pointing to the beginning of the empty part of
+	 * mslots, and the ">=" would move the hole backwards in this
+	 * case---which is wrong.  So skip the loop when deleting a slot.
+	 */
+	if (new->npages) {
+		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;

Paolo

Quoted 92 lines · Paolo Bonzini

virt/kvm/kvm_main.c static void update_memslots(struct kvm_memslots *slots, · line 678

Quoted 12 lines

virt/kvm/kvm_main.c +1 -0

index f528343..6e52f3f 100644
@@ -672,6 +672,7 @@ static void update_memslots(struct kvm_memslots *slots,
  	WARN_ON(mslots[i].id != id);
  	if (!new->npages) {
  		new->base_gfn = 0;
+		new->flags = 0;
  		if (mslots[i].npages)
  			slots->used_slots--;
  	} else {

This should not be necessary. The part of the mslots array that has base_gfn == npages == 0 is entirely unused, and such a slot can never be returned by search_memslots because this:

if (gfn >= memslots[slot].base_gfn &&
gfn < memslots[slot].base_gfn + memslots[slot].npages)

can never be true.

virt/kvm/kvm_main.c static void update_memslots(struct kvm_memslots *slots, · line 697

Quoted 12 lines

virt/kvm/kvm_main.c +3 -1

@@ -688,7 +689,9 @@ static void update_memslots(struct kvm_memslots *slots,
  		i++;
  	}
  	while (i > 0 &&
-	       new->base_gfn > mslots[i - 1].base_gfn) {
+	       ((new->base_gfn > mslots[i - 1].base_gfn) ||
+	        (!new->base_gfn &&
+	         !mslots[i - 1].base_gfn && !mslots[i - 1].npages))) {
  		mslots[i] = mslots[i - 1];
  		slots->id_to_index[mslots[i].id] = i;
  		i--;

You should have explained _why_ this fixes the bug, and what invariant is not being respected, something like this:

kvm: fix sorting of memslots with base_gfn == 0

Before commit 0e60b0799fed (kvm: change memslot sorting rule from size to GFN, 2014-12-01), the memslots' sorting key was npages, meaning that a valid memslot couldn't have its sorting key equal to zero. On the other hand, a valid memslot can have base_gfn == 0, and invalid memslots are identified by base_gfn == npages == 0.

Because of this, commit 0e60b0799fed broke the invariant that invalid memslots are at the end of the mslots array. When a memslot with base_gfn == 0 was created, any invalid memslot before it were left in place.

This suggests another fix. We can change the insertion to use a ">=" comparison, as in your first patch. Alone it is not correct, but we only need to take some care and avoid breaking the case of deleting a memslot.

It's enough to wrap the second loop (that you patched) with "if (new->npages)". In the new->npages == 0 case the first loop has already set i to the right value, and moving i back would be wrong:

virt/kvm/kvm_main.c +17 -5

index f5283438ee05..050974c051b5 100644
@@ -687,11 +687,23 @@ static void update_memslots(struct kvm_memslots *slots,
  		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--;
+
+	/*
+	 * The ">=" is needed when creating a slot with base_gfn == 0,
+	 * so that it moves before all those with base_gfn == npages == 0.
+	 *
+	 * On the other hand, if new->npages is zero, the above loop has
+	 * already left i pointing to the beginning of the empty part of
+	 * mslots, and the ">=" would move the hole backwards in this
+	 * case---which is wrong.  So skip the loop when deleting a slot.
+	 */
+	if (new->npages) {
+		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--;
+		}
  	}
 

Quoted 3 lines

virt/kvm/kvm_main.c +0 -0

  	mslots[i] = *new;

Paolo

Paolo,

Can you include a proper changelog for this patch?

Quoted 45 lines

Quoted 45 lines

This suggests another fix. We can change the insertion to use a ">=" comparison, as in your first patch. Alone it is not correct, but we only need to take some care and avoid breaking the case of deleting a memslot.

It's enough to wrap the second loop (that you patched) with "if (new->npages)". In the new->npages == 0 case the first loop has already set i to the right value, and moving i back would be wrong:

virt/kvm/kvm_main.c +17 -5

index f5283438ee05..050974c051b5 100644
@@ -687,11 +687,23 @@ static void update_memslots(struct kvm_memslots
 *slots,
          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--;
+
+    /*
+     * The ">=" is needed when creating a slot with base_gfn == 0,
+     * so that it moves before all those with base_gfn == npages == 0.
+     *
+     * On the other hand, if new->npages is zero, the above loop has
+     * already left i pointing to the beginning of the empty part of
+     * mslots, and the ">=" would move the hole backwards in this
+     * case---which is wrong.  So skip the loop when deleting a slot.
+     */
+    if (new->npages) {
+        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;

Quoted 6 lines

Quoted 1 line

Paolo

Paolo,

Can you include a proper changelog for this patch?

But this is already applied long time ago...