
Date: Sun, 10 Jan 2016 11:35:04 0500 From: Morten Welinder <mwelinder@...il.com> To: musl@...ts.openwall.com Subject: Re: Possible infinite loop in qsort() > 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@...c.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[i2]+lp[i1]+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 32bit >> > 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 32bit >> > archs because Linux selfishly hogs a whole GB of address space for the >> > kernel. On 64bit 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
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.