Re: [Qemu-devel] [PATCH v2 3/3] qapi: Fix memleak in string visitors on int lists

[Markus Armbruster <armbru@redhat.com>]

Eric Blake <eblake@redhat.com> writes:

> On 06/01/2016 01:47 AM, Markus Armbruster wrote:
>> Eric Blake <eblake@redhat.com> writes:
>> 
>>> Commit 7f8f9ef1 introduced the ability to store a list of
>>> integers as a sorted list of ranges, but when merging ranges,
>>> it leaks one or more ranges.  It was also using range_get_last()
>>> incorrectly within range_compare() (a range is a start/end pair,
>>> but range_get_last() is for start/len pairs), and will also
>>> mishandle a range ending in UINT64_MAX (remember, we document
>>> that no range covers 2**64 bytes, but that ranges that end on
>>> UINT64_MAX have end < begin).
>>>
>
>>>
>>> -    if (!list) {
>>> -        list = g_list_insert_sorted(list, data, range_compare);
>>> -        return list;
>>> +    /* Range lists require no empty ranges */
>>> +    assert(data->begin < data->end || (data->begin && !data->end));
>> 
>> Consider { begin = 0, end = 0 }.
>> 
>> Since zero @end means 2^64, this encodes the (non-empty) range
>> 0..2^64-1.
>
> Or else it means an uninitialized range.  My argument is that no range
> can contain 2^64 bytes, and therefore the only possible range that would
> be that large (0..2^64-1) is unrepresentable, therefore, if end == 0,
> begin must be non-zero for the range to be valid as an initialized range.

I'm not sure what you mean by "uninitialized range".  Maybe "invalid
range"?

>> range.h's comment
>> 
>>  * Notes:
>>  *   - ranges must not wrap around 0, but can include the last byte ~0x0LL.
>>  *   - this can not represent a full 0 to ~0x0LL range.
>> 
>> appears to be wrong.  The actual limitation is "can't represent ranges
>> wrapping around zero, and can't represent the empty range starting at
>> zero."  Would you like to correct it?
>
> I'm not sure what corrections it needs, though.
>
>> I'm afraid range.h is too clever by half.
>
> Unfortunately true.
>
>> 
>>> +
>>> +    for (l = list; l && range_compare(l->data, data) < 0; l = l->next) {
>>> +        /* Skip all list elements strictly less than data */
>>>      }
>> 
>> Let's put the comment before the loop.  It describes the whole loop.
>> Also makes the emptiness of the body more obvious.
>
> Sure.
>
>> 
>> I think I could fix up things on commit (assuming we agree on what needs
>> fixing).
>> 
>
> Adding other authors of range.h for their opinions...

No reply.

I find the comments in range.h terminally confusing.

The clear parts:

* we want to have inclusive lower bound <= inclusive upper bound (no
  wrap around), and

* we want to encode the bounds using @start as inclusive lower bound,
  and @end as exclusive upper bound.

This begs the question how end == 0 is to be interpreted.  Options:

(1) It's literally the exclusive upper bound.  An interval with a
non-negative inclusive lower bound and a zero exclusive upper bound is
empty.  There is no way to represent the inclusive upper bound 2^63-1.
This contradicts the comment's claim that you can.

(2) It's 2^64.  Now you cannot represent the inclusive upper bound -1.
You cannot represent the empty interval [0,-1], although you can
represent other empty intervals [b,b-1], b>0.  { start = 0, end = 0 }
encodes the interval [0,2^64-1].  Contradicts the comment's claim that
you can't, unless...

(2') end=0 is special-cased to mean something else when start=0!  Namely
0 instead of 2^64, so that { start=0, end=0 } becomes the empty interval
[0,-1].

The tradeoff between (2) and (2') is between two anomalies: "can't do
[0,-1]", and "can't do [0..2^64-1]".

I prefer (2), because I find the former anomaly less bad, and feel
special-casing @end is bound to lead to bugs.

Whatever option we choose, we should fix the comment to explain it
clearly.