Re: [PATCH] kvm: fix to update memslots properly

[Paolo Bonzini <pbonzini@redhat.com>]

> diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
> index f528343..6e52f3f 100644
> --- a/virt/kvm/kvm_main.c
> +++ b/virt/kvm/kvm_main.c
> @@ -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.

> @@ -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:

diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index f5283438ee05..050974c051b5 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -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