Re: [PATCH] msort: Get rid of alloca.

[Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>]

On 03/07/23 13:08, Joe Simmons-Talbott via Libc-alpha wrote:
> On Fri, Jun 30, 2023 at 01:12:28PM -0700, Paul Eggert wrote:
>> On 2023-06-30 10:26, Joe Simmons-Talbott via Libc-alpha wrote:
>>
>>> +  /* If the memory requirements are too high don't allocate memory.  */
>>> +  if (size / pagesize > (size_t) phys_pages)
>>> +    {
>>> +      _quicksort (b, n, s, cmp, arg);
>>> +      return;
>>> +    }
>>> ...
>>> +  if (!scratch_buffer_set_array_size (&buf, 1, size))
>>> +    {
>>> +      /* Couldn't get space, so use the slower algorithm
>>> +         that doesn't need a temporary array.  */
>>> +      _quicksort (b, n, s, cmp, arg);
>>> +      return;
>>>       }
>>
>> Please combine the two ifs into one, since their then-parts are the same and
>> that will make the code easier to follow.
> 
> I'll do this in v2.  Thanks for the suggestion and the review.
> 
>>
>>
>>> +  scratch_buffer_free (&buf);
>>
>> Dumb question: can we arrange for scratch_buffer_free to be called even if
>> qsort's comparison function longjmps out of qsort? I realize the old code
>> leaked in that case, but it'd be nice if the new code didn't leak too. This
>> sort of longjmp sometimes happens in real code, e.g., in GNU 'ls'.
>>
> 
> I'll have to defer to someone more knowledgable than me on this one.  My
> understanding is that longjmp resets the stack pointer and doesn't call
> any GCC cleanup handlers thus ruling out the one option I was able to
> think of.  Does anyone else have thoughts on this?

Another option would to just remove malloc from qsort usage, by using the
quicksort implementation instead.  To avoid the worse case we fallback to
a simple heapsort, as some of C++ implementation does.  This has the advantage
of fixing the possible longjmp issue and making the qsort full async-safe.