Austin Group Defect Tracker

Aardvark Mark III


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 2018-09-08 22:23
Reporter eblake View Status public  
Assigned To
Priority normal Resolution Open  
Status New  
Name Eric Blake
Organization Red Hat
User Reference ebb.qsort_r
Section qsort
Page Number 1744
Line Number 56084
Interp Status ---
Final Accepted Text
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 No tags attached.
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).

- 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


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