Anonymous | Login | 2024-12-12 13:48 UTC |
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 | |||||||
|
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 |