[PATCH] msort: Get rid of alloca.

[Joe Simmons-Talbott]

On Thu, Jul 06, 2023 at 10:43:42AM -0300, Adhemerval Zanella Netto wrote:
> 
> 
> 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.
> 

>From my understanding there are three cases in __qsort_r; small where we
use alloca, medium where we use malloc, and large where we use
_quicksort.  This would lead to always using _quicksort, if I understand
correctly.  _quicksort reduces the probability of the worst case by
choosing the median as the pivot.  Am I missing something?

Thanks,
Joe