
MessageID: <20160109082139.GD2016@debian> Date: Sat, 9 Jan 2016 09:21:39 +0100 From: Markus Wichmann <nullplan@....net> To: musl@...ts.openwall.com Subject: Possible infinite loop in qsort() 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? Ciao, Markus
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.