Possible infinite loop in qsort()

Possible infinite loop in qsort()

[Markus Wichmann]

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

Re: Possible infinite loop in qsort()

[Felix Janda]

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

Re: Possible infinite loop in qsort()

[Rich Felker]

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[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

Re: Possible infinite loop in qsort()

[Szabolcs Nagy]

* Rich Felker <dalias@libc.org> [2016-01-09 23:05:16 -0500]:
> On Sat, Jan 09, 2016 at 10:07:19AM +0100, Felix Janda wrote:
> > Markus Wichmann wrote:
> > > 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++);
> > > 
...
> > 
> > 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.

one element array would have to be special cased too:

qsort(p, 1, SIZE_MAX, cmp)

would oob access lp

in musl

qsort(p, 1, SIZE_MAX/2, cmp)

would loop for more than necessary before lp[i] reaches >=size
but it's harmless because lp is large enough.

Re: Possible infinite loop in qsort()

[Alexander Monakov]

On Sat, 9 Jan 2016, Rich Felker wrote:
> 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.

I don't think so: the problematic loop in musl computes Leonardo numbers
premultiplied by member size, to be used as byte offsets in the array to be
sorted.  So individual member size doesn't matter, only the overall array
size.

Alexander

Re: Possible infinite loop in qsort()

[Markus Wichmann]

On Sat, Jan 09, 2016 at 11:05:16PM -0500, Rich Felker wrote:
> On Sat, Jan 09, 2016 at 10:07:19AM +0100, Felix Janda wrote:
> > 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.
> 

OK. Might want to make that assumption a bit more prominent, because
this is the first time I've ever heard about it, but OK, no objects >2GB
on 32-bit archs.

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

Maybe, but the point was that you can overflow the Leonardo number
calculation for any given width. Re-read the example I gave: It was less
than 900,000,000 ints you needed to overflow the calculation.

What I did was make sure that nel * width is greater than the greatest
Leonardo number * width that's representable in the architecture's
size_t. That is possible for every given width. The inequation I just
gave boils down to nel > max{l | l is Leonardo number, l * width < 2^32}

But since there are (plenty of) Leonardo numbers between 2^31 and 2^32,
and object size (nel * width) is limited to <2^31, with a valid object
the calculation can't overflow. And with an invalid object, I don't know
if the code as given would even work, as pointer differences wouldn't
work. Haven't tested that one, either.

Ciao,
Markus

Re: Possible infinite loop in qsort()

[Szabolcs Nagy]

* Markus Wichmann <nullplan@gmx.net> [2016-01-10 12:38:53 +0100]:
> What I did was make sure that nel * width is greater than the greatest
> Leonardo number * width that's representable in the architecture's
> size_t. That is possible for every given width. The inequation I just

size_t overflow is not a problem

unsigned overflow is well defined and the loop is guaranteed
to finish, the only question if it finishes before lp array
is filled, and the answer is yes if object size is restricted
to <= SIZE_MAX/2

> gave boils down to nel > max{l | l is Leonardo number, l * width < 2^32}
> 
> But since there are (plenty of) Leonardo numbers between 2^31 and 2^32,
> and object size (nel * width) is limited to <2^31, with a valid object
> the calculation can't overflow. And with an invalid object, I don't know
> if the code as given would even work, as pointer differences wouldn't
> work. Haven't tested that one, either.

invalid input is ub and qsort does not try catch such ub

Re: Possible infinite loop in qsort()

[Alexander Cherepanov]

On 2016-01-10 14:38, Markus Wichmann wrote:
> On Sat, Jan 09, 2016 at 11:05:16PM -0500, Rich Felker wrote:
>> On Sat, Jan 09, 2016 at 10:07:19AM +0100, Felix Janda wrote:
>>> 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.
>>
>
> OK. Might want to make that assumption a bit more prominent, because
> this is the first time I've ever heard about it, but OK, no objects >2GB
> on 32-bit archs.

Yeah, I don't see it in the doc. Did I miss it?

If it neither works nor documented as a limit I'd call it a bug.

BTW the support in compilers for working with objects larger than half 
the address space is buggy -- see 
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67999 . The same situation 
-- it neither works nor documented. Somewhat puzzling...

-- 
Alexander Cherepanov

Re: Possible infinite loop in qsort()

[Szabolcs Nagy]

* Alexander Cherepanov <ch3root@openwall.com> [2016-01-12 15:25:57 +0300]:

> On 2016-01-10 14:38, Markus Wichmann wrote:
> >On Sat, Jan 09, 2016 at 11:05:16PM -0500, Rich Felker wrote:
> >>On Sat, Jan 09, 2016 at 10:07:19AM +0100, Felix Janda wrote:
> >>>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.
> >>
> >
> >OK. Might want to make that assumption a bit more prominent, because
> >this is the first time I've ever heard about it, but OK, no objects >2GB
> >on 32-bit archs.
> 
> Yeah, I don't see it in the doc. Did I miss it?
> 
> If it neither works nor documented as a limit I'd call it a bug.

in musl things are documented in the git log for now, e.g.:
http://git.musl-libc.org/cgit/musl/commit/?id=3cd6f5229f079f892411e82fce3fe15c78eef4d8

i think if an implementation does not give this guarantee
that should be considered a bug.

(glibc does not guarantee this and indeed it is full of invalid
pointer arithmetics, but more importantly a huge number of
existing libraries depend on this)

> BTW the support in compilers for working with objects larger than half the
> address space is buggy -- see
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67999 . The same situation --
> it neither works nor documented. Somewhat puzzling...

yes, but it's not possible to support reasonably

Re: Possible infinite loop in qsort()

[Alexander Cherepanov]

On 2016-01-12 15:48, Szabolcs Nagy wrote:
> * Alexander Cherepanov <ch3root@openwall.com> [2016-01-12 15:25:57 +0300]:
>
>> On 2016-01-10 14:38, Markus Wichmann wrote:
>>> On Sat, Jan 09, 2016 at 11:05:16PM -0500, Rich Felker wrote:
>>>> On Sat, Jan 09, 2016 at 10:07:19AM +0100, Felix Janda wrote:
>>>>> 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.
>>>>
>>>
>>> OK. Might want to make that assumption a bit more prominent, because
>>> this is the first time I've ever heard about it, but OK, no objects >2GB
>>> on 32-bit archs.
>>
>> Yeah, I don't see it in the doc. Did I miss it?
>>
>> If it neither works nor documented as a limit I'd call it a bug.
>
> in musl things are documented in the git log for now, e.g.:
> http://git.musl-libc.org/cgit/musl/commit/?id=3cd6f5229f079f892411e82fce3fe15c78eef4d8

IMHO such things should be documented in user-facing documentation, not 
in source code comments, git log or email posts.

> i think if an implementation does not give this guarantee
> that should be considered a bug.

Some consider it a bug, others -- a feature.

But if you want to provide this guarantee it's not that easy. Compilers 
are not under your control. Even with gcc (which tries to provide this 
guarantee) you can create VLA 2.5GB in size and run it with `ulimit -s 
unlimited` (at least as a 32-bit binary on a 64-bit host).

Then, a user can create an object of any size via mmap with MAP_FIXED 
flag, right?

> (glibc does not guarantee this and indeed it is full of invalid
> pointer arithmetics,

Care to provide examples?

> but more importantly a huge number of
> existing libraries depend on this)
>
>> BTW the support in compilers for working with objects larger than half the
>> address space is buggy -- see
>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67999 . The same situation --
>> it neither works nor documented. Somewhat puzzling...
>
> yes, but it's not possible to support reasonably

Why is that?

-- 
Alexander Cherepanov

Re: Possible infinite loop in qsort()

[Szabolcs Nagy]

* Alexander Cherepanov <ch3root@openwall.com> [2016-01-12 17:31:31 +0300]:
> On 2016-01-12 15:48, Szabolcs Nagy wrote:
> >in musl things are documented in the git log for now, e.g.:
> >http://git.musl-libc.org/cgit/musl/commit/?id=3cd6f5229f079f892411e82fce3fe15c78eef4d8
> 
> IMHO such things should be documented in user-facing documentation, not in
> source code comments, git log or email posts.
> 

yes, that would be a useful project

> >i think if an implementation does not give this guarantee
> >that should be considered a bug.
> 
> Some consider it a bug, others -- a feature.
> 
> But if you want to provide this guarantee it's not that easy. Compilers are
> not under your control. Even with gcc (which tries to provide this
> guarantee) you can create VLA 2.5GB in size and run it with `ulimit -s
> unlimited` (at least as a 32-bit binary on a 64-bit host).
> 

large vla sounds like a problem, the libc can guard against that
by placing a guard page in the way on the main thread.

but stack allocations are kind of outside the c language:
stack limits are not admitted in the standard causing technical
issues around correctness proofs.

> Then, a user can create an object of any size via mmap with MAP_FIXED flag,
> right?

creating a single object by two mmaps that happen to be
adjacent sounds like a grey area (not sure if that's strictly
conforming in posix/c).

the user can get a large object behind the libc (e.g. by using
raw syscalls) but the portable ways are controlled by the libc.

> >(glibc does not guarantee this and indeed it is full of invalid
> >pointer arithmetics,
> 
> Care to provide examples?
> 

this is what i did: went to the glibc string directory
looked for pointer - operations, there are already several
in various argz_* functions so i didnt have to go further
than the letter 'a' to find

char *match = strstr (arg, str);
...
size_t to_len = match - arg;

in argz_replace, if arg is a large object and str only
matches near the end, then match - arg is ub.

i think the argz buffer is internally allocated by
the libc so it could protect against large objects but
i don't see such protection.

the first obvious example i see is in memccpy

void *p = memchr (src, c, n);
...
return __mempcpy (dest, src, p - src + 1);

again p - src can be ub.

> >but more importantly a huge number of
> >existing libraries depend on this)
> >
> >>BTW the support in compilers for working with objects larger than half the
> >>address space is buggy -- see
> >>https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67999 . The same situation --
> >>it neither works nor documented. Somewhat puzzling...
> >
> >yes, but it's not possible to support reasonably
> 
> Why is that?

i guess it can be supported but you lose some useful
transformations

e.g. p < q can be transformed to p-q < 0
in the compiler if the diff cannot overflow

i don't know how much this matters for optimization
and how much harder it is to implement, but i do
think there are easy mistakes to be made if p-q can
overflow.

Re: Possible infinite loop in qsort()

[Rich Felker]

On Tue, Jan 12, 2016 at 05:22:44PM +0100, Szabolcs Nagy wrote:
> > >i think if an implementation does not give this guarantee
> > >that should be considered a bug.
> > 
> > Some consider it a bug, others -- a feature.
> > 
> > But if you want to provide this guarantee it's not that easy. Compilers are
> > not under your control. Even with gcc (which tries to provide this
> > guarantee) you can create VLA 2.5GB in size and run it with `ulimit -s
> > unlimited` (at least as a 32-bit binary on a 64-bit host).
> > 
> 
> large vla sounds like a problem, the libc can guard against that
> by placing a guard page in the way on the main thread.
> 
> but stack allocations are kind of outside the c language:
> stack limits are not admitted in the standard causing technical
> issues around correctness proofs.

While the C standard fails to specify it as such, overflowing the
stack has to be treated as undefined behavior. One such case of
overflow is an object >SIZE_MAX/2 bytes.

> > Then, a user can create an object of any size via mmap with MAP_FIXED flag,
> > right?
> 
> creating a single object by two mmaps that happen to be
> adjacent sounds like a grey area (not sure if that's strictly
> conforming in posix/c).

POSIX is not clear on how the memory obtained by mmap becomes C
"objects", but it's not important anyway. You cannot use MAP_FIXED to
create such objects because passing an address to mmap/MAP_FIXED that
you don't already own/control produces UB. You could use opportunistic
address requests to attempt to produce such a large contiguous region,
but you still would not be justified in interpreting them as a single
large object.

> the user can get a large object behind the libc (e.g. by using
> raw syscalls) but the portable ways are controlled by the libc.

These are not formal objects; if you do stupid stuff by calling
syscalls directly, you get what you deserve.

Rich

Re: Possible infinite loop in qsort()

[Rich Felker]

On Tue, Jan 12, 2016 at 03:25:57PM +0300, Alexander Cherepanov wrote:
> On 2016-01-10 14:38, Markus Wichmann wrote:
> >On Sat, Jan 09, 2016 at 11:05:16PM -0500, Rich Felker wrote:
> >>On Sat, Jan 09, 2016 at 10:07:19AM +0100, Felix Janda wrote:
> >>>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.
> >>
> >
> >OK. Might want to make that assumption a bit more prominent, because
> >this is the first time I've ever heard about it, but OK, no objects >2GB
> >on 32-bit archs.
> 
> Yeah, I don't see it in the doc. Did I miss it?

The documentation is incomplete; in particular, the part that would
cover things like this has not been written at all and exists just in
my head (and to a lesser extent as implied from commit messages and
mailing list threads). :-)

> If it neither works nor documented as a limit I'd call it a bug.

An implementation is under no obligation to document the conditions
under which it's "out of memory" (ENOMEM). These are usually complex
and highly implementation specific.

> BTW the support in compilers for working with objects larger than
> half the address space is buggy -- see
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67999 . The same
> situation -- it neither works nor documented. Somewhat puzzling...

The only bug here is that it's not documented. "Supporting" such
objects without making ptrdiff_t a 64-bit type is an intolerably bad
QoI issue.

Rich

Re: Possible infinite loop in qsort()

[Morten Welinder]

> 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@libc.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[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

Re: Possible infinite loop in qsort()

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 951 bytes --]

Am Sonntag, den 10.01.2016, 11:35 -0500 schrieb Morten Welinder:
> > 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.

Generally for C it isn't, but for POSIX it is. char there always have
8 bit. So if we are also supposing that pointers have more than 8 bit :)
we never have sizeof(pointer) to be 1. So in that sense we are safe for
musl.

Jens

-- 
:: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::




[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: Possible infinite loop in qsort()

[Alexander Cherepanov]

On 2016-01-09 11:21, Markus Wichmann wrote:
> 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).

Another case: 32-bit binary on 64-bit OS. Compile with `gcc -m32` and 
easily malloc more that 3GB. With glibc, that is.

-- 
Alexander Cherepanov