Re: [Qemu-devel] [PATCH] virtio: fix vring->inuse recalc after migr

[Stefan Hajnoczi]

On Fri, Dec 16, 2016 at 05:43:29PM +0100, Halil Pasic wrote:
> 
> 
> On 12/16/2016 05:12 PM, Stefan Hajnoczi wrote:
> >> You are not the first one complaining, so the sentence is definitively
> >> bad. What disturbs me regarding your formulation is that we do not use
> >> uint16_t to represent neither the ring size nor inuse.
> >>
> >> How about "Since max ring size < UINT16_MAX it's safe to use modulo
> >> UINT16_MAX + 1 subtraction."?
> > That doesn't mention "representing the size of the ring" so it's
> > unclear what "safe" means.
> > 
> > Stefan
> > 
> 
> IMHO it is not about representation but about correct arithmetic.
> We introduce the cast, not because representing the ring size as
> int is necessarily an issue, but because we ended up with a wrong
> result. In my opinion how can 'inuse' be represented correctly and
> efficiently concerns the member of struct VirtQueue.

Fair enough, the type of VirtQueue.inuse doesn't need to be justified at
this point in the code.

> Here the important point is how conversions between signed unsigned
> integer types work in C.
> 
> """
> 6.3.1.3 Signed and unsigned integers
> 1 When a value with integer type is converted to another integer
> type other than _Bool, if  the value can be represented by the new
> type, it is unchanged.
> 2 Otherwise, if the new type is unsigned, the value is converted by
> repeatedly adding or  subtracting one more than the maximum value that
> can be represented in the new type until the value is in the range
> of the new type.
> """
> 
> That is we get mod UINT16_MAX + 1  subtraction which is what we
> need if we want to calculate the difference between the two counters
> under the assumption that the actual conceptual difference (that
> is if the counters where of type arbitrary natural) is less or equal that
> queue size which is less than UINT16_MAX.

-vdev->vq[i].inuse = vdev->vq[i].last_avail_idx -
-vdev->vq[i].used_idx;
+vdev->vq[i].inuse = (uint16_t)(vdev->vq[i].last_avail_idx -
+vdev->vq[i].used_idx);

Looking at C99 I learnt the cause of the bug is the integer promotion
performed on the uint16_t subtraction operands.  Previously I was only
aware of integer promotion on varargs and function arguments where no
prototype is declared.

So the original statement behaves like:

vdev->vq[i].inuse = (int)vdev->vq[i].last_avail_idx -
(int)vdev->vq[i].used_idx;

This is the real gotcha for me.

If you feel it helps to explain the signed -> unsigned cast behavior,
feel free.  I don't think it's necessary.

Stefan


signature.asc
Description: PGP signature

Re: [Qemu-devel] [PATCH] virtio: fix vring->inuse recalc after migr

[Michael S. Tsirkin]

On Fri, Dec 16, 2016 at 04:12:24PM +, Stefan Hajnoczi wrote:
> On Fri, Dec 16, 2016 at 3:41 PM, Halil Pasic  wrote:
> > On 12/16/2016 11:25 AM, Stefan Hajnoczi wrote:
> >> On Thu, Dec 15, 2016 at 04:43:30PM +0100, Halil Pasic wrote:
> >>> Correct recalculation of vring->inuse after migration for
> >>> the corner case where the avail_idx has already wrapped
> >>> but used_idx not yet.
> >>>
> >>> Signed-off-by: Halil Pasic 
> >>> Fixes: bccdef6b ("virtio: recalculate vq->inuse after migration")
> >>> CC: qemu-sta...@nongnu.org
> >>> ---
> >>>
> >>> I think we could also change the type of inuse to uint16_t.
> >>> Would this be considered a good idea?
> >>
> >> VRing.num is unsigned int.  I would use the same type as num since this
> >> is a size, not an index.
> >>
> >
> > Thanks. I asked myself the question why are VRing.num and inuse (at
> > least theoretically arch depended width but at least 16 bit) int while
> > the indexes of the available and used rings uint16_t. Only thing I can
> > think of is some sort of optimization, because the only difference I can
> > see is that the VRing.num is communicated via the transport while the
> > indexes are a part (and/or corresponding to) of the ring layout (that is
> > the shared memory virtio structures and have a fixed width).
> >
> > Now I'm kind of in doubt: I think having a signed has the benefit of a
> > negative value being more obviously wrong size (for a human looking at
> > it) that a to large positive, but purely theoretically the maximum value
> > of inuse is not guaranteed to fit int (as in C99 MIN_INT is 2^15 - 1).
> >
> > What is your opinion? Should we keep 'inuse' as is, or should I change
> > it to unsigned with v2 (or prepare a separate patch)?
> 
> I'm happy with unsigned.  I've CCed Michael Tsirkin in case he has a 
> preference.

I don't mind.

> >>> ---
> >>>  hw/virtio/virtio.c | 7 +--
> >>>  1 file changed, 5 insertions(+), 2 deletions(-)
> >>>
> >>> diff --git a/hw/virtio/virtio.c b/hw/virtio/virtio.c
> >>> index 1af2de2..089c6f6 100644
> >>> --- a/hw/virtio/virtio.c
> >>> +++ b/hw/virtio/virtio.c
> >>> @@ -1855,9 +1855,12 @@ int virtio_load(VirtIODevice *vdev, QEMUFile *f, 
> >>> int version_id)
> >>>  /*
> >>>   * Some devices migrate VirtQueueElements that have been 
> >>> popped
> >>>   * from the avail ring but not yet returned to the used ring.
> >>> + * Cast to uint16_t is OK because max ring size is 0x8000. 
> >>> Thus
> >>> + * no the size of largest array indexable by an integral type
> >>> + * can not be represented by the same type problem.
> >>
> >> I think it would be safe up to max ring size UINT16_MAX - 1 (we need
> >> that extra value to distinguish between empty and full avail rings)?
> >>
> >
> > Yeah.
> >
> >> The last sentence is hard to understand due to the double negative.  I
> >> think you are saying "Since max ring size < UINT16_MAX it's safe to use
> >> uint16_t to represent the size of the ring".
> >>
> >
> > You are not the first one complaining, so the sentence is definitively
> > bad. What disturbs me regarding your formulation is that we do not use
> > uint16_t to represent neither the ring size nor inuse.
> >
> > How about "Since max ring size < UINT16_MAX it's safe to use modulo
> > UINT16_MAX + 1 subtraction."?
> 
> That doesn't mention "representing the size of the ring" so it's
> unclear what "safe" means.
> 
> Stefan

Re: [Qemu-devel] [PATCH] virtio: fix vring->inuse recalc after migr

[Halil Pasic]

On 12/16/2016 05:12 PM, Stefan Hajnoczi wrote:
>> You are not the first one complaining, so the sentence is definitively
>> bad. What disturbs me regarding your formulation is that we do not use
>> uint16_t to represent neither the ring size nor inuse.
>>
>> How about "Since max ring size < UINT16_MAX it's safe to use modulo
>> UINT16_MAX + 1 subtraction."?
> That doesn't mention "representing the size of the ring" so it's
> unclear what "safe" means.
> 
> Stefan
> 

IMHO it is not about representation but about correct arithmetic.
We introduce the cast, not because representing the ring size as
int is necessarily an issue, but because we ended up with a wrong
result. In my opinion how can 'inuse' be represented correctly and
efficiently concerns the member of struct VirtQueue.

Here the important point is how conversions between signed unsigned
integer types work in C.

"""
6.3.1.3 Signed and unsigned integers
1 When a value with integer type is converted to another integer
type other than _Bool, if  the value can be represented by the new
type, it is unchanged.
2 Otherwise, if the new type is unsigned, the value is converted by
repeatedly adding or  subtracting one more than the maximum value that
can be represented in the new type until the value is in the range
of the new type.
"""

That is we get mod UINT16_MAX + 1  subtraction which is what we
need if we want to calculate the difference between the two counters
under the assumption that the actual conceptual difference (that
is if the counters where of type arbitrary natural) is less or equal that
queue size which is less than UINT16_MAX.

But no strong opinion here. If I did not manage to convince you
now, just tell, and I will be happy to just go with your formulation.

Thanks,

Halil

Re: [Qemu-devel] [PATCH] virtio: fix vring->inuse recalc after migr

[Stefan Hajnoczi]

On Fri, Dec 16, 2016 at 3:41 PM, Halil Pasic  wrote:
> On 12/16/2016 11:25 AM, Stefan Hajnoczi wrote:
>> On Thu, Dec 15, 2016 at 04:43:30PM +0100, Halil Pasic wrote:
>>> Correct recalculation of vring->inuse after migration for
>>> the corner case where the avail_idx has already wrapped
>>> but used_idx not yet.
>>>
>>> Signed-off-by: Halil Pasic 
>>> Fixes: bccdef6b ("virtio: recalculate vq->inuse after migration")
>>> CC: qemu-sta...@nongnu.org
>>> ---
>>>
>>> I think we could also change the type of inuse to uint16_t.
>>> Would this be considered a good idea?
>>
>> VRing.num is unsigned int.  I would use the same type as num since this
>> is a size, not an index.
>>
>
> Thanks. I asked myself the question why are VRing.num and inuse (at
> least theoretically arch depended width but at least 16 bit) int while
> the indexes of the available and used rings uint16_t. Only thing I can
> think of is some sort of optimization, because the only difference I can
> see is that the VRing.num is communicated via the transport while the
> indexes are a part (and/or corresponding to) of the ring layout (that is
> the shared memory virtio structures and have a fixed width).
>
> Now I'm kind of in doubt: I think having a signed has the benefit of a
> negative value being more obviously wrong size (for a human looking at
> it) that a to large positive, but purely theoretically the maximum value
> of inuse is not guaranteed to fit int (as in C99 MIN_INT is 2^15 - 1).
>
> What is your opinion? Should we keep 'inuse' as is, or should I change
> it to unsigned with v2 (or prepare a separate patch)?

I'm happy with unsigned.  I've CCed Michael Tsirkin in case he has a preference.

>>> ---
>>>  hw/virtio/virtio.c | 7 +--
>>>  1 file changed, 5 insertions(+), 2 deletions(-)
>>>
>>> diff --git a/hw/virtio/virtio.c b/hw/virtio/virtio.c
>>> index 1af2de2..089c6f6 100644
>>> --- a/hw/virtio/virtio.c
>>> +++ b/hw/virtio/virtio.c
>>> @@ -1855,9 +1855,12 @@ int virtio_load(VirtIODevice *vdev, QEMUFile *f, int 
>>> version_id)
>>>  /*
>>>   * Some devices migrate VirtQueueElements that have been popped
>>>   * from the avail ring but not yet returned to the used ring.
>>> + * Cast to uint16_t is OK because max ring size is 0x8000. Thus
>>> + * no the size of largest array indexable by an integral type
>>> + * can not be represented by the same type problem.
>>
>> I think it would be safe up to max ring size UINT16_MAX - 1 (we need
>> that extra value to distinguish between empty and full avail rings)?
>>
>
> Yeah.
>
>> The last sentence is hard to understand due to the double negative.  I
>> think you are saying "Since max ring size < UINT16_MAX it's safe to use
>> uint16_t to represent the size of the ring".
>>
>
> You are not the first one complaining, so the sentence is definitively
> bad. What disturbs me regarding your formulation is that we do not use
> uint16_t to represent neither the ring size nor inuse.
>
> How about "Since max ring size < UINT16_MAX it's safe to use modulo
> UINT16_MAX + 1 subtraction."?

That doesn't mention "representing the size of the ring" so it's
unclear what "safe" means.

Stefan

Re: [Qemu-devel] [PATCH] virtio: fix vring->inuse recalc after migr

[Halil Pasic]

On 12/16/2016 11:25 AM, Stefan Hajnoczi wrote:
> On Thu, Dec 15, 2016 at 04:43:30PM +0100, Halil Pasic wrote:
>> Correct recalculation of vring->inuse after migration for
>> the corner case where the avail_idx has already wrapped
>> but used_idx not yet.
>>
>> Signed-off-by: Halil Pasic 
>> Fixes: bccdef6b ("virtio: recalculate vq->inuse after migration")
>> CC: qemu-sta...@nongnu.org
>> ---
>>
>> I think we could also change the type of inuse to uint16_t.
>> Would this be considered a good idea?
> 
> VRing.num is unsigned int.  I would use the same type as num since this
> is a size, not an index.
> 

Thanks. I asked myself the question why are VRing.num and inuse (at
least theoretically arch depended width but at least 16 bit) int while
the indexes of the available and used rings uint16_t. Only thing I can
think of is some sort of optimization, because the only difference I can
see is that the VRing.num is communicated via the transport while the
indexes are a part (and/or corresponding to) of the ring layout (that is
the shared memory virtio structures and have a fixed width).

Now I'm kind of in doubt: I think having a signed has the benefit of a
negative value being more obviously wrong size (for a human looking at
it) that a to large positive, but purely theoretically the maximum value
of inuse is not guaranteed to fit int (as in C99 MIN_INT is 2^15 - 1).

What is your opinion? Should we keep 'inuse' as is, or should I change
it to unsigned with v2 (or prepare a separate patch)?


>> ---
>>  hw/virtio/virtio.c | 7 +--
>>  1 file changed, 5 insertions(+), 2 deletions(-)
>>
>> diff --git a/hw/virtio/virtio.c b/hw/virtio/virtio.c
>> index 1af2de2..089c6f6 100644
>> --- a/hw/virtio/virtio.c
>> +++ b/hw/virtio/virtio.c
>> @@ -1855,9 +1855,12 @@ int virtio_load(VirtIODevice *vdev, QEMUFile *f, int 
>> version_id)
>>  /*
>>   * Some devices migrate VirtQueueElements that have been popped
>>   * from the avail ring but not yet returned to the used ring.
>> + * Cast to uint16_t is OK because max ring size is 0x8000. Thus
>> + * no the size of largest array indexable by an integral type
>> + * can not be represented by the same type problem.
> 
> I think it would be safe up to max ring size UINT16_MAX - 1 (we need
> that extra value to distinguish between empty and full avail rings)?
>

Yeah.
 
> The last sentence is hard to understand due to the double negative.  I
> think you are saying "Since max ring size < UINT16_MAX it's safe to use
> uint16_t to represent the size of the ring".
> 

You are not the first one complaining, so the sentence is definitively
bad. What disturbs me regarding your formulation is that we do not use
uint16_t to represent neither the ring size nor inuse.

How about "Since max ring size < UINT16_MAX it's safe to use modulo
UINT16_MAX + 1 subtraction."?

Cheers,
Halil

>>   */
>> -vdev->vq[i].inuse = vdev->vq[i].last_avail_idx -
>> -vdev->vq[i].used_idx;
>> +vdev->vq[i].inuse = (uint16_t)(vdev->vq[i].last_avail_idx -
>> +vdev->vq[i].used_idx);
>>  if (vdev->vq[i].inuse > vdev->vq[i].vring.num) {
>>  error_report("VQ %d size 0x%x < last_avail_idx 0x%x - "
>>   "used_idx 0x%x",
>> -- 
>> 2.8.4
>>
>>



signature.asc
Description: OpenPGP digital signature

Re: [Qemu-devel] [PATCH] virtio: fix vring->inuse recalc after migr

[Stefan Hajnoczi]

On Thu, Dec 15, 2016 at 04:43:30PM +0100, Halil Pasic wrote:
> Correct recalculation of vring->inuse after migration for
> the corner case where the avail_idx has already wrapped
> but used_idx not yet.
> 
> Signed-off-by: Halil Pasic 
> Fixes: bccdef6b ("virtio: recalculate vq->inuse after migration")
> CC: qemu-sta...@nongnu.org
> ---
> 
> I think we could also change the type of inuse to uint16_t.
> Would this be considered a good idea?

VRing.num is unsigned int.  I would use the same type as num since this
is a size, not an index.

> ---
>  hw/virtio/virtio.c | 7 +--
>  1 file changed, 5 insertions(+), 2 deletions(-)
> 
> diff --git a/hw/virtio/virtio.c b/hw/virtio/virtio.c
> index 1af2de2..089c6f6 100644
> --- a/hw/virtio/virtio.c
> +++ b/hw/virtio/virtio.c
> @@ -1855,9 +1855,12 @@ int virtio_load(VirtIODevice *vdev, QEMUFile *f, int 
> version_id)
>  /*
>   * Some devices migrate VirtQueueElements that have been popped
>   * from the avail ring but not yet returned to the used ring.
> + * Cast to uint16_t is OK because max ring size is 0x8000. Thus
> + * no the size of largest array indexable by an integral type
> + * can not be represented by the same type problem.

I think it would be safe up to max ring size UINT16_MAX - 1 (we need
that extra value to distinguish between empty and full avail rings)?

The last sentence is hard to understand due to the double negative.  I
think you are saying "Since max ring size < UINT16_MAX it's safe to use
uint16_t to represent the size of the ring".

>   */
> -vdev->vq[i].inuse = vdev->vq[i].last_avail_idx -
> -vdev->vq[i].used_idx;
> +vdev->vq[i].inuse = (uint16_t)(vdev->vq[i].last_avail_idx -
> +vdev->vq[i].used_idx);
>  if (vdev->vq[i].inuse > vdev->vq[i].vring.num) {
>  error_report("VQ %d size 0x%x < last_avail_idx 0x%x - "
>   "used_idx 0x%x",
> -- 
> 2.8.4
> 
> 


signature.asc
Description: PGP signature

[Qemu-devel] [PATCH] virtio: fix vring->inuse recalc after migr

[Halil Pasic]

Correct recalculation of vring->inuse after migration for
the corner case where the avail_idx has already wrapped
but used_idx not yet.

Signed-off-by: Halil Pasic 
Fixes: bccdef6b ("virtio: recalculate vq->inuse after migration")
CC: qemu-sta...@nongnu.org
---

I think we could also change the type of inuse to uint16_t.
Would this be considered a good idea?
---
 hw/virtio/virtio.c | 7 +--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/hw/virtio/virtio.c b/hw/virtio/virtio.c
index 1af2de2..089c6f6 100644
--- a/hw/virtio/virtio.c
+++ b/hw/virtio/virtio.c
@@ -1855,9 +1855,12 @@ int virtio_load(VirtIODevice *vdev, QEMUFile *f, int 
version_id)
 /*
  * Some devices migrate VirtQueueElements that have been popped
  * from the avail ring but not yet returned to the used ring.
+ * Cast to uint16_t is OK because max ring size is 0x8000. Thus
+ * no the size of largest array indexable by an integral type
+ * can not be represented by the same type problem.
  */
-vdev->vq[i].inuse = vdev->vq[i].last_avail_idx -
-vdev->vq[i].used_idx;
+vdev->vq[i].inuse = (uint16_t)(vdev->vq[i].last_avail_idx -
+vdev->vq[i].used_idx);
 if (vdev->vq[i].inuse > vdev->vq[i].vring.num) {
 error_report("VQ %d size 0x%x < last_avail_idx 0x%x - "
  "used_idx 0x%x",
-- 
2.8.4