Re: Possible infinite loop in qsort()

[Rich Felker <dalias@libc.org>]

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