[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <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[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?
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.
