Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Thu, 23 Sep 2021 20:18:19 -0400
From: Rich Felker <dalias@...c.org>
To: √Črico Nogueira <ericonr@...root.org>
Cc: musl@...ts.openwall.com
Subject: Re: [PATCH v3] add qsort_r and make qsort a wrapper around it

On Tue, Mar 09, 2021 at 06:02:13PM -0300, √Črico Nogueira wrote:
> we make qsort a wrapper by providing a wrapper_cmp function that uses
> the extra argument as a function pointer. should be optimized to a tail
> call on most architectures, as long as it's built with
> -fomit-frame-pointer, so the performance impact should be minimal.
> 
> to keep the git history clean, for now qsort_r is implemented in qsort.c
> and qsort is implemented in qsort_nr.c.  qsort.c also received a few
> trivial cleanups, including replacing (*cmp)() calls with cmp().
> qsort_nr.c contains only wrapper_cmp and qsort as a qsort_r wrapper
> itself.
> ---
> 
> Following suggestions from IRC, as few changes as possible to the files,
> a final clean up commit after this one would involve some git mv's (I
> won't make a patch for it). Added weak_alias to force qsort to use
> libc's qsort_r.
> 
> If this can't be accepted due to the overhead on some archs (ppc, mips,
> arm in some situations?), maybe we could revisit v2 of the patch?
> 
>  include/stdlib.h      |  1 +
>  src/include/stdlib.h  |  1 +
>  src/stdlib/qsort.c    | 37 ++++++++++++++++++++-----------------
>  src/stdlib/qsort_nr.c | 14 ++++++++++++++
>  4 files changed, 36 insertions(+), 17 deletions(-)
>  create mode 100644 src/stdlib/qsort_nr.c
> 
> diff --git a/include/stdlib.h b/include/stdlib.h
> index b54a051f..0c0ced5f 100644
> --- a/include/stdlib.h
> +++ b/include/stdlib.h
> @@ -158,6 +158,7 @@ struct __locale_struct;
>  float strtof_l(const char *__restrict, char **__restrict, struct __locale_struct *);
>  double strtod_l(const char *__restrict, char **__restrict, struct __locale_struct *);
>  long double strtold_l(const char *__restrict, char **__restrict, struct __locale_struct *);
> +void qsort_r (void *, size_t, size_t, int (*)(const void *, const void *, void *), void *);
>  #endif
> [...]

I'm merging this now with the change from only exposing it under
_GNU_SOURCE to _BSD_SOURCE (default). As it's been accepted for POSIX
future, I'd like to make it visible under baseline POSIX profile too,
but I think that's a potentially riskier change that we can do later.

As noted many times, the issue of GCC refusing to tail call on some
archs is unfortunate, but we should get this fixed on the GCC side
rather than doing ugly things trying to work around it.

Rich

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.