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=lp=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
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.