Austin Group Defect Tracker

Aardvark Mark IV

Main | My View | View Issues | Change Log | Docs
  

Viewing Issue Simple Details [ Jump to Notes ] [ Issue History ] [ Print ]
ID Category Severity Type Date Submitted Last Update
0000900 [1003.1(2013)/Issue7+TC1] System Interfaces Comment Enhancement Request 2014-12-04 16:37 2024-06-11 09:02
Reporter eblake View Status public  
Assigned To
Priority normal Resolution Accepted As Marked  
Status Closed  
Name Eric Blake
Organization Red Hat
User Reference ebb.qsort_r
Section qsort
Page Number 1744
Line Number 56084
Interp Status ---
Final Accepted Text Note: 0005333
Summary 0000900: add qsort_r
Description qsort requires the use of global variables for passing any state to the comparator. As a result, several implementations (at least glibc and BSD) have added a re-entrant variant qsort_r that takes an opaque pointer allowing for thread-safe reuse of a common stateful comparator function across two parallel sorts.

Unfortunately, the glibc folks picked a different signature (opaque argument last in comparator, after compar argument of qsort_r) than the BSD folks (opaque argument first in comparator, before compar argument of qsort_r). If we standardize the name qsort_r, at least one platform will have existing code break. This proposal goes with the glibc signature (on the grounds that pthread_create establishes precedent of opaque argument last), but the committee may wish to go with an alternate name such as 'qsortr' or 'posix_qsort_r' to avoid breaking existing use with the opposite parameter ordering. Such changes to the proposed desired action will probably also warrant an addition to RATIONALE why we used a name not already in existing practice.

We may want to consider re-entrant variants of other functions that might benefit from stateful callbacks, such as scandir or bsearch, although I did not tackle that here (in part because those do not have existing practice to copy from at the moment).
Desired Action After page 359 line 12104 (XBD <stdlib.h>), add a line with CX shading:
void qsort_r(void *, size_t, size_t, int (*)(const void *, const void *, void *), void *);


At page 1744 line 56084 (XSH qsort NAME), change "qsort" to "qsort, qsort_r"

After page 1744 line 56088 (SYNOPSIS), add a line with CX shading:
void qsort_r(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *, void *), void *arg);


After page 1744 line 56108 (DESCRIPTION), add a paragraph with CX shading:
The qsort_r() function is identical to qsort() except that the comparison function compar takes a third argument. The arg opaque pointer passed to qsort_r( ) is in turn passed as the third argument to the comparison function.


At page 1744 line 56110 (RETURN VALUE), change "qsort( ) function" to "qsort( ) and qsort_r( ) functions"

At page 1744 line 56117 (APPLICATION USAGE), add a paragraph:
If the compar callback requires any additional state outside of the items being sorted, it can only access this state through global variables, making it potentially unsafe to use qsort with the same compar function from separate threads at the same time. The qsort_r( ) function was added with the ability to pass through arbitrary arguments to the comparator, which avoids the need to access global variables and thus making it possible to safely share a stateful comparator across threads.
Tags issue8
Attached Files

- Relationships

-  Notes
(0002476)
eblake (manager)
2014-12-04 18:45

 In addition to the precedence of pthread_create and pthread_cleanup_push as my rational for preferring the glibc signature as the version we should standardize (even if we choose a different function name), I add an additional argument based on implementation:

The glibc implementation is an easy shim on most modern architectures: passing a third parameter in a register to a function prototyped to only take two parameters just works (with the help of a cast to silence the compiler's notion of type-safety, but where the cast does not require any change to the emitted assembly code), and the cost of populating a third register is minimal, so users would not notice if qsort was implemented in terms of qsort_r. But the BSD implementation requires application writers to rewrite their comparator if they convert their code from qsort to qsort_r, and if the qsort implementation itself is done via such a rewrite, it makes qsort noticeably slower.

That is, the glibc implementation can be as simple as:
void qsort(void *base, size_t nel, size_t width,
           int (*compar)(const void *, const void *))
{
  qsort_r(base, nel, width,
          (int (*)(const void*, const void*, void*))compar, NULL);
}

followed by a 2-line rewrite of the existing qsort into the new qsort_r by modifying two lines: the signature, and the call to compar. Existing callers of qsort will continue to work, with minimal execution overhead (populating an ignored third register for each call to compar(a, b) is in the noise).

On the other hand, it is tougher for the BSD implementation to share qsort and qsort_r code. The comparators differ on whether the first argument is an array element to be compared or the opaque pointer. If BSD implements qsort_r by the comparable 2-line rewrite of the existing qsort (change the signature and the call to compar, but with different positions of the opaque pointer), then the conversion would also require a shim something like:

static int compar_shim(void *func, const void *a, const void *b)
{
  int (*compar)(const void *, const void *) = func;
  return compar(a, b);
}
void qsort(void *base, size_t nel, size_t width,
           int (*compar)(const void *, const void *))
{
  qsort_r(base, nel, width, compar, compar_shim);
}

and where the execution overhead of qsort would include another indirect function call per comparison made (each comparison goes through compar_shim(compar, a, b) in addition to compar(a, b), for twice as many function calls for a shared qsort/qsort_r as compared to the original qsort implementation). Thus, in the BSD case, it would be argued that duplicating qsort and qsort_r code would be wiser for speed, at the penalty of size due to not sharing the code.
(0002779)
EdSchouten (updater)
2015-08-01 21:38

 There is no need for a bsearch_r(). The standard already requires that the key and the list objects are passed in in a certain order.

I just did a grep through the FreeBSD source tree and it seems like qsort_r() is only hardly used. i think it wouldn't be a bad idea to just standardize the glibc version and use symbol versioning on FreeBSD to deal with compatibility.
(0004108)
Don Cragun (manager)
2018-09-06 16:52
edited on: 2018-09-06 16:53

 Do we have any indication of what the developers at FreeBSD think about changing the function prototype for qsort_r() in their implementation to match the GNU function prototype?

If they agree with the description in this bug report and the notes in Note: 0002476, it seems to me that we should standardize this function using the name qsort_r() with the GNU function prototype; otherwise, we should probably use the name posix_qsort_r().
(0004112)
EdSchouten (updater)
2018-09-08 22:23

 I wrote a patch for FreeBSD to switch over to the same prototype as glibc and sent it out for review:

https://reviews.freebsd.org/D17083 [^]

If I'm able to get the necessary approvals, my plan is to commit it by the end of this month, which is right after FreeBSD 12 branches. In other words, it would only become part of FreeBSD 13 (very far in the future).
(0005049)
geoffclare (manager)
2020-10-16 09:15
edited on: 2020-10-16 09:17

 The qsort_r() additions have been made in the Issue8NewAPIs branch in gitlab, based on the desired action.

It was also added to the POSIX_C_LANG_SUPPORT_R subprofile group in XRAT E.1.
(0005333)
geoffclare (manager)
2021-04-29 15:14

 Make the changes from "Additional APIs for Issue 8, Part 1" (Austin/1110).
(0005344)
enh (reporter)
2021-04-29 16:23

 do we know if iOS/macOS will take the FreeBSD change? otherwise it seems like we should go with posix_qsort_r() instead to avoid source compatibility issues? it seems unlikely that Apple would be able to make a breaking change like this?

(as the Android libc maintainer there's more value to my users if i follow the iOS/macOS prototype than the glibc one, which is one reason why Android has offered neither up to now, and why i still probably wouldn't go with the glibc prototype. going with posix_qsort_r() would be the best of both worlds because it seems like the only way for us to get the three major libcs all in sync.)
(0005349)
geoffclare (manager)
2021-04-30 08:55

 > it seems unlikely that Apple would be able to make a breaking change like this?

Similar changes have been made by implementations in the past. They can be done with little or no application breakage if the compiler supports a way to rename external symbol references. For example, Solaris has this in <unistd.h> (with some details omitted):
#if     (_POSIX_C_SOURCE - 0 >= 199506L) || ...
#ifdef __PRAGMA_REDEFINE_EXTNAME
#pragma redefine_extname getlogin_r __posix_getlogin_r
#pragma redefine_extname ttyname_r __posix_ttyname_r
extern int getlogin_r(char *, size_t);
extern int ttyname_r(int, char *, size_t);
#else  /* __PRAGMA_REDEFINE_EXTNAME */
extern int __posix_getlogin_r(char *, size_t);
extern int __posix_ttyname_r(int, char *, size_t);
static int
getlogin_r(char *__name, size_t __len)
{
        return (__posix_getlogin_r(__name, __len));
}
static int
ttyname_r(int __fildes, char *__buf, size_t __size)
{
        return (__posix_ttyname_r(__fildes, __buf, __size));
}
#endif /* __PRAGMA_REDEFINE_EXTNAME */
#else  /* (_POSIX_C_SOURCE - 0 >= 199506L) || ... */
extern char *getlogin_r(char *, int);
extern char *ttyname_r(int, char *, int);
#endif /* (_POSIX_C_SOURCE - 0 >= 199506L) || ... */

(The static definitions are a fallback for compilers that don't support the #pragma, but of course they don't conform to the standard.)

I said "little or no" breakage, but actually the only type of breakage I can think of (when the #pragma is used) perhaps doesn't count as breakage anyway. It would happen if an application that defines _POSIX_C_SOURCE=1 and uses the "old" getlogin_r() or ttyname_r() as an extension is updated to define _POSIX_C_SOURCE=199506L. However, by defining that FTM the application is signalling to the implementation that it conforms to POSIX.1-1996 and so should be expected to need updating to use the new prototypes.

It occurs to me that with symbol versioning, it may be better for the old function to be the one whose name is changed. For example:
#if _XOPEN_SOURCE - 0 >= 800 || ...
extern void qsort_r(void *, size_t, size_t, int (*)(const void *, const void *, void *), void *);
#else /* _XOPEN_SOURCE - 0 >= 800 || ... */
#ifdef __PRAGMA_REDEFINE_EXTNAME
#pragma redefine_extname qsort_r __old_qsort_r
extern void qsort_r(void *, size_t, size_t, void *, int (*)(void *,const void *, const void *));
#else  /* __PRAGMA_REDEFINE_EXTNAME */
extern void __old_qsort_r(void *, size_t, size_t, void *, int (*)(void *,const void *, const void *)
);
... static defs ... (or even just #define qsort_r __old_qsort_r)
#endif /* __PRAGMA_REDEFINE_EXTNAME */
#endif /* _XOPEN_SOURCE - 0 >= 800 || ... */

This way, any problems arising with use of compilers that don't support the #pragma would occur for old applications and wouldn't affect standards conformance. (Old binaries would still work courtesy of symbol versioning.)

- Issue History
Date Modified Username Field Change
2014-12-04 16:37 eblake New Issue
2014-12-04 16:37 eblake Name => Eric Blake
2014-12-04 16:37 eblake Organization => Red Hat
2014-12-04 16:37 eblake User Reference => ebb.qsort_r
2014-12-04 16:37 eblake Section => qsort
2014-12-04 16:37 eblake Page Number => 1744
2014-12-04 16:37 eblake Line Number => 56084
2014-12-04 16:37 eblake Interp Status => ---
2014-12-04 18:45 eblake Note Added: 0002476
2015-08-01 21:38 EdSchouten Note Added: 0002779
2018-09-06 16:52 Don Cragun Note Added: 0004108
2018-09-06 16:53 Don Cragun Note Edited: 0004108
2018-09-08 22:23 EdSchouten Note Added: 0004112
2020-10-16 09:15 geoffclare Note Added: 0005049
2020-10-16 09:17 geoffclare Note Edited: 0005049
2021-04-29 15:14 geoffclare Note Added: 0005333
2021-04-29 15:15 geoffclare Final Accepted Text => Note: 0005333
2021-04-29 15:15 geoffclare Status New => Resolved
2021-04-29 15:15 geoffclare Resolution Open => Accepted As Marked
2021-04-29 15:15 geoffclare Tag Attached: issue8
2021-04-29 16:23 enh Note Added: 0005344
2021-04-30 08:55 geoffclare Note Added: 0005349
2021-05-07 15:10 geoffclare Status Resolved => Applied
2024-06-11 09:02 agadmin Status Applied => Closed

Mantis 1.1.6[^]
Copyright © 2000 - 2008 Mantis Group
Powered by Mantis Bugtracker