Re: Possible infinite loop in qsort()

[Morten Welinder <mwelinder@gmail.com>]

> Note also that if you do want to use this code on an
> implementation without such a guarantee, only the case where
> the member size is 1 can possibly have >SIZE_MAX/2
> members.

That's correct.

> In that case, you can massively optimize out the whole sort
> by just counting the number of times each byte appears [...]

That isn't.  sizeof(char) is guaranteed to be 1.  Is it not, however,
required to represent bytes.  You could have sizeof(pointer) be
1 also and if you so, you really cannot do sorting by counting.

M.



On Sat, Jan 9, 2016 at 11:05 PM, Rich Felker <dalias@libc.org> wrote:
> On Sat, Jan 09, 2016 at 10:07:19AM +0100, Felix Janda wrote:
>> Markus Wichmann wrote:
>> > Hi all,
>> >
>> > This is the Leonardo number precompute loop in qsort():
>> >
>> >    for(lp[0]=lp[1]=width, i=2; (lp[i]=lp[i-2]+lp[i-1]+width) < size; i++);
>> >
>> > I haven't actually tested this, but is it possible that this can become
>> > infinite on x32? My reasoning is this:
>> >
>> > This loop calculates all Leonardo numbers (scaled by width) until one
>> > comes along that is greater than the array length. However, that number
>> > is never actually needed, we only need to calculate all Leonardo numbers
>> > smaller than array size. And there is another problem: What if that
>> > smallest Leonardo number greater than array size isn't representable in
>> > size_t? In that case, the final addition step will overflow and the
>> > inequation will never become false. So if an array is entered that has
>> > more elements than the largest representable Leonardo number scaled by
>> > width (for instance, an array with more than 866,988,873 ints (size 4)),
>> > the above loop becomes infinite: The next Leonardo number is
>> > 1,402,817,465, multiplied by 4 that is larger than 2^32, so on a 32-bit
>> > architecture, this will overflow.
>> >
>> > Then I thought more about this: Such an array would be just over 3GB
>> > long. You don't have that much address space available on most 32-bit
>> > archs because Linux selfishly hogs a whole GB of address space for the
>> > kernel. On 64-bit archs, Linux hogs half the address space, so no
>> > userspace array can be larger than the largest Leonardo number
>> > representable in 64 bits, so it looks like we're safe, right?
>> >
>> > Except there's x32: 4GB of address space and no kernel infringes on it
>> > (x32 is basically x86_64, but we keep the userspace pointers down to 32
>> > bits, so the kernel is way beyond what we're looking at).
>> >
>> > But as I said, we don't actually need the smallest Leonardo number
>> > greater than size, we only need the largest Leonardo numer smaller than
>> > size. So this problem could be solved by either of:
>> >
>> > 1. Checking for overflow.
>> > 2. Putting an absolute limit on i.
>> >
>> > Did I miss anything?
>>
>> musl enforces that object sizes should not be greater than PTRDIFF_MAX.
>> See for example the discussion at
>>
>> http://www.openwall.com/lists/musl/2013/06/27/7
>>
>> So there will not be objects of size 3GB with musl on x32. Since the
>> Leonardo numbers grow slower than 2^n in general no overflow should
>> happen if "size" is valid. Otherwise, UB was invoked.
>
> Note also that if you do want to use this code on an implementation
> without such a guarantee, only the case where the member size is 1 can
> possibly have >SIZE_MAX/2 members. In that case, you can massively
> optimize out the whole sort by just counting the number of times each
> byte appears (in size_t[UCHAR_MAX+1] space which is tiny), sorting the
> pairs (value,count) using the comparison function, then writing out
> each value the appropriate number of times.
>
> Rich