[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 9 Jan 2016 10:07:19 +0100
From: Felix Janda <felix.janda@...teo.de>
To: musl@...ts.openwall.com
Subject: Re: Possible infinite loop in qsort()
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.
Felix
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
