Re: Possible infinite loop in qsort()

[Alexander Cherepanov <ch3root@openwall.com>]

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