qsort_r or qsort_s in musl

qsort_r or qsort_s in musl

[Balazs Kezes]

Hi!

I can find a lot of discussions on the web around qsort_r and the pain that musl
lacks it but I can't find any official word on this from musl devs. If there is
one, could src/stdlib/qsort.c contain a pointer to it?

Are there any plans having one of them in musl? I'd prefer qsort_r since that
would provide greater compatibility with glibc. I even found patches for it:
https://gist.github.com/izabera/e68927258ad2d29a1586bad276fabcab
https://github.com/esmil/musl/commit/194f9cf93da8ae62491b7386edf481ea8565ae4e

qsort_r differs between bsd/osx and glibc though:
https://sourceware.org/ml/libc-alpha/2008-12/msg00003.html

The argument for qsort_s is that it is in the C11 standard as an optional
feature and has similar interface as glibc's qsort_r.

To avoid choosing sides it could be even qsort_musl for all I care. I could then
use preprocessor to choose the right version. I know there are many workarounds:
global variables, thread local variables, copy pasting and changing qsort from
musl in my own source tree, using glibc. None of them feel right.

Any thoughts?

Please CC me on the replies.

Thank you,
Balazs

Re: qsort_r or qsort_s in musl

[Rich Felker]

On Mon, Sep 03, 2018 at 09:57:05PM +0100, Balazs Kezes wrote:
> Hi!
> 
> I can find a lot of discussions on the web around qsort_r and the pain that musl
> lacks it but I can't find any official word on this from musl devs. If there is
> one, could src/stdlib/qsort.c contain a pointer to it?
> 
> Are there any plans having one of them in musl? I'd prefer qsort_r since that
> would provide greater compatibility with glibc. I even found patches for it:
> https://gist.github.com/izabera/e68927258ad2d29a1586bad276fabcab
> https://github.com/esmil/musl/commit/194f9cf93da8ae62491b7386edf481ea8565ae4e
> 
> qsort_r differs between bsd/osx and glibc though:
> https://sourceware.org/ml/libc-alpha/2008-12/msg00003.html
> 
> The argument for qsort_s is that it is in the C11 standard as an optional
> feature and has similar interface as glibc's qsort_r.
> 
> To avoid choosing sides it could be even qsort_musl for all I care. I could then
> use preprocessor to choose the right version. I know there are many workarounds:
> global variables, thread local variables, copy pasting and changing qsort from
> musl in my own source tree, using glibc. None of them feel right.
> 
> Any thoughts?

I think it's been discussed several times before, probably on the
list, but I can summarize the state of the topic as far as I'm aware:

qsort_s, as part of Annex K, is pretty much rejected as long as it's
neither a mandatory part of C, nor widely used by applications. If we
were to implement it, it should conform to the standard function by
that name, which would entail doing lots of wrong things like
introducing "runtime constraint handler" as global state. It's ironic
that the function whose purported purpose is being thread-safe with
regard to context ends up introducing mechanisms that make it
fundamentally thread-unsafe.

qsort_r was at first rejected because of the conflicting definitions
-- existence of same-named interfaces with different semantics or
signatures is one of the big criteria for exclusion of nonstandard
extensions in musl. However, from the FreeBSD side at least there
seems to be interest in dropping their version and agreeing upon a
standard aligned with glibc's version, for the sake of POSIX:

http://austingroupbugs.net/view.php?id=900

I'm not aware of any further progress on the issue, but if it becomes
clear that POSIX is either going to standardize a version that agree
with the GNU definition, or commit to not standardizing any that
conflict, I think the level of consensus we have so far is sufficient
to consider doing it.

In the mean time, you can always implement a thin wrapper defining
qsort_r in terms of qsort, using thread-local storage for the context
argument.

Rich

Re: qsort_r or qsort_s in musl

[Balazs Kezes]

On 2018-09-03 18:53 -0400, Rich Felker wrote:
> http://austingroupbugs.net/view.php?id=900
>
> I'm not aware of any further progress on the issue, but if it becomes
> clear that POSIX is either going to standardize a version that agree
> with the GNU definition, or commit to not standardizing any that
> conflict, I think the level of consensus we have so far is sufficient
> to consider doing it.

Ah, so to get this into musl, POSIX needs to get this first. Is there a way to
ping that issue tracker to resolve the issue? Doesn't look like random schmucks
like myself can ping it. I think I found eblake's email, let me CC him.

Eric: Would it be possible to resolve the above POSIX feature request one way or
another so that C code can start using it more portably? I would be happy with
qsortr too, it's nice and short. (This thread's archive is at the
http://www.openwall.com/lists/musl/2018/09/03/2 url.)

Thanks all!

Balazs

Re: qsort_r or qsort_s in musl

[Eric Blake]

On 09/04/2018 02:41 AM, Balazs Kezes wrote:
> On 2018-09-03 18:53 -0400, Rich Felker wrote:
>> http://austingroupbugs.net/view.php?id=900
>>
>> I'm not aware of any further progress on the issue, but if it becomes
>> clear that POSIX is either going to standardize a version that agree
>> with the GNU definition, or commit to not standardizing any that
>> conflict, I think the level of consensus we have so far is sufficient
>> to consider doing it.
> 
> Ah, so to get this into musl, POSIX needs to get this first. Is there a way to
> ping that issue tracker to resolve the issue? Doesn't look like random schmucks
> like myself can ping it. I think I found eblake's email, let me CC him.
> 
> Eric: Would it be possible to resolve the above POSIX feature request one way or
> another so that C code can start using it more portably? I would be happy with
> qsortr too, it's nice and short. (This thread's archive is at the
> http://www.openwall.com/lists/musl/2018/09/03/2 url.)

I will attempt to raise the priority of bug 900 in order to get it onto 
the agenda of an upcoming Austing Group call (unfortunately, the Austin 
Group meeting once per week tends to get through fewer bugs on average 
than the rate at which bugs are being filed, so there have been rather 
long lags at resolving any particular bug).

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org

Re: Re: qsort_r or qsort_s in musl

[Rich Felker]

On Tue, Sep 04, 2018 at 09:48:02AM -0500, Eric Blake wrote:
> On 09/04/2018 02:41 AM, Balazs Kezes wrote:
> >On 2018-09-03 18:53 -0400, Rich Felker wrote:
> >>http://austingroupbugs.net/view.php?id=900
> >>
> >>I'm not aware of any further progress on the issue, but if it becomes
> >>clear that POSIX is either going to standardize a version that agree
> >>with the GNU definition, or commit to not standardizing any that
> >>conflict, I think the level of consensus we have so far is sufficient
> >>to consider doing it.
> >
> >Ah, so to get this into musl, POSIX needs to get this first. Is there a way to
> >ping that issue tracker to resolve the issue? Doesn't look like random schmucks
> >like myself can ping it. I think I found eblake's email, let me CC him.
> >
> >Eric: Would it be possible to resolve the above POSIX feature request one way or
> >another so that C code can start using it more portably? I would be happy with
> >qsortr too, it's nice and short. (This thread's archive is at the
> >http://www.openwall.com/lists/musl/2018/09/03/2 url.)
> 
> I will attempt to raise the priority of bug 900 in order to get it
> onto the agenda of an upcoming Austing Group call (unfortunately,
> the Austin Group meeting once per week tends to get through fewer
> bugs on average than the rate at which bugs are being filed, so
> there have been rather long lags at resolving any particular bug).

Thanks. Final acceptance into POSIX isn't completely mandatory for us
to adopt it, but I'd at least want to see that FreeBSD (others would
be great too) is moving forward with converting over to the
glibc/proposed-POSIX signature so the risk of this devolving into a
deadlock is in the past.

Rich

Re: qsort_r or qsort_s in musl

[Balazs Kezes]

Awesome, thank you all!

Balazs

Re: Re: qsort_r or qsort_s in musl

[Leah Neukirchen]

Rich Felker <dalias@libc.org> writes:

> Thanks. Final acceptance into POSIX isn't completely mandatory for us
> to adopt it, but I'd at least want to see that FreeBSD (others would
> be great too) is moving forward with converting over to the
> glibc/proposed-POSIX signature so the risk of this devolving into a
> deadlock is in the past.

AFAICS, macOS and DragonFlyBSD also use the FreeBSD signature.
OpenBSD never implemented qsort_r; NetBSD proposed to implemement the
glibc signature in 2013, but this didn't seem to be merged.

-- 
Leah Neukirchen  <leah@vuxu.org>  http://leah.zone

Re: Re: qsort_r or qsort_s in musl

[Rich Felker]

On Tue, Sep 04, 2018 at 05:45:50PM +0200, Leah Neukirchen wrote:
> Rich Felker <dalias@libc.org> writes:
> 
> > Thanks. Final acceptance into POSIX isn't completely mandatory for us
> > to adopt it, but I'd at least want to see that FreeBSD (others would
> > be great too) is moving forward with converting over to the
> > glibc/proposed-POSIX signature so the risk of this devolving into a
> > deadlock is in the past.
> 
> AFAICS, macOS and DragonFlyBSD also use the FreeBSD signature.
> OpenBSD never implemented qsort_r; NetBSD proposed to implemement the
> glibc signature in 2013, but this didn't seem to be merged.

Yes, I'm aware there are a couple others and at least one (OSX) is
probably going to be hard to get to change. I'm pretty okay with that
as long as there is good consensus among the implementations that
actually care about portability and consensus. OSX has so many serious
conformance bugs, and is stuck so far in the past (17 years -- POSIX
2001, with problems even conforming to that), that it's like MSVCRT;
they really don't have standing to push their way on this.

Rich

Re: qsort_r or qsort_s in musl

[Ed Maste]

> qsort_r was at first rejected because of the conflicting definitions
> -- existence of same-named interfaces with different semantics or
> signatures is one of the big criteria for exclusion of nonstandard
> extensions in musl. However, from the FreeBSD side at least there
> seems to be interest in dropping their version and agreeing upon a
> standard aligned with glibc's version, for the sake of POSIX:

If you want to see the current state of this in FreeBSD, we have a
code review in progress in Phabricator at
https://reviews.freebsd.org/D17083. If POSIX standardizes on the glibc
version I'm sure we'll follow.

Re: qsort_r or qsort_s in musl

[Rich Felker]

On Mon, Sep 10, 2018 at 01:27:00PM -0400, Ed Maste wrote:
> > qsort_r was at first rejected because of the conflicting definitions
> > -- existence of same-named interfaces with different semantics or
> > signatures is one of the big criteria for exclusion of nonstandard
> > extensions in musl. However, from the FreeBSD side at least there
> > seems to be interest in dropping their version and agreeing upon a
> > standard aligned with glibc's version, for the sake of POSIX:
> 
> If you want to see the current state of this in FreeBSD, we have a
> code review in progress in Phabricator at
> https://reviews.freebsd.org/D17083. If POSIX standardizes on the glibc
> version I'm sure we'll follow.

Thanks for the update. It looks like we have a sort of 3- (N-?) way
deadlock:

A: POSIX adopts qsort_r with glibc signature
B: FreeBSD switches qsort_r to glibc signature
C: musl adds qsort_r with glibc signature

A seems kinda stalled and dependent on B and possibly others.
B seems dependent on A.
C seems dependent on A || B || some approximation of A. ;-)

Fortunately it looks like we're all on the same page about where it
should end up and all sides still want it to happen.

Rich