* Re: [PATCH] kvm: fix to update memslots properly
2014-12-27 20:41 ` Paolo Bonzini
@ 2014-12-27 22:52 ` Jamie Heilman
2014-12-29 1:06 ` Chen, Tiejun
2015-03-09 20:54 ` Marcelo Tosatti
2 siblings, 0 replies; 7+ messages in thread
From: Jamie Heilman @ 2014-12-27 22:52 UTC (permalink / raw)
To: Paolo Bonzini; +Cc: Tiejun Chen, KVM list, Andy Lutomirski, Igor Mammedov
Paolo Bonzini wrote:
> 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;
I gave this a try, and it works just fine for me too.
--
Jamie Heilman http://audible.transient.net/~jamie/
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH] kvm: fix to update memslots properly
2014-12-27 20:41 ` Paolo Bonzini
2014-12-27 22:52 ` Jamie Heilman
@ 2014-12-29 1:06 ` Chen, Tiejun
2015-03-09 20:54 ` Marcelo Tosatti
2 siblings, 0 replies; 7+ messages in thread
From: Chen, Tiejun @ 2014-12-29 1:06 UTC (permalink / raw)
To: Paolo Bonzini, KVM list, Andy Lutomirski, jamie, Igor Mammedov
On 2014/12/28 4:41, Paolo Bonzini wrote:
>> 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.
Yeah, but its really a little ugly to see some slots,
base_gfn:npages:falgs = 0:0:(!0), to resort again when debug something
inside of update_memslots().
>
>> @@ -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
Yeah.
> 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;
>
This looks better.
Tiejun
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH] kvm: fix to update memslots properly
2014-12-27 20:41 ` Paolo Bonzini
2014-12-27 22:52 ` Jamie Heilman
2014-12-29 1:06 ` Chen, Tiejun
@ 2015-03-09 20:54 ` Marcelo Tosatti
2015-03-10 6:17 ` Chen, Tiejun
2 siblings, 1 reply; 7+ messages in thread
From: Marcelo Tosatti @ 2015-03-09 20:54 UTC (permalink / raw)
To: Paolo Bonzini
Cc: Tiejun Chen, KVM list, Andy Lutomirski, jamie, Igor Mammedov
On Sat, Dec 27, 2014 at 09:41:45PM +0100, Paolo Bonzini wrote:
> > 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
Paolo,
Can you include a proper changelog for this patch?
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH] kvm: fix to update memslots properly
2015-03-09 20:54 ` Marcelo Tosatti
@ 2015-03-10 6:17 ` Chen, Tiejun
2015-03-10 11:59 ` Paolo Bonzini
0 siblings, 1 reply; 7+ messages in thread
From: Chen, Tiejun @ 2015-03-10 6:17 UTC (permalink / raw)
To: Marcelo Tosatti, Paolo Bonzini
Cc: KVM list, Andy Lutomirski, jamie, Igor Mammedov
On 2015/3/10 4:54, Marcelo Tosatti wrote:
> On Sat, Dec 27, 2014 at 09:41:45PM +0100, Paolo Bonzini wrote:
>>> 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
>
> Paolo,
>
> Can you include a proper changelog for this patch?
>
But this is already applied long time ago...
Tiejun
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH] kvm: fix to update memslots properly
2015-03-10 6:17 ` Chen, Tiejun
@ 2015-03-10 11:59 ` Paolo Bonzini
0 siblings, 0 replies; 7+ messages in thread
From: Paolo Bonzini @ 2015-03-10 11:59 UTC (permalink / raw)
To: Chen, Tiejun, Marcelo Tosatti
Cc: KVM list, Andy Lutomirski, jamie, Igor Mammedov
>>> 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
>>
>> Paolo,
>>
>> Can you include a proper changelog for this patch?
>>
>
> But this is already applied long time ago...
Yes, this is commit efbeec7098eee2b3d2359d0cc24bbba0436e7f21.
Paolo
^ permalink raw reply [flat|nested] 7+ messages in thread