Bug #3763
closedImplement qsort_r(3C)
100%
Description
This reentrant variant of qsort(3C) is used in modern software such as libgit2. Both BSD and GNU have implementations.
Updated by Chris Nehren almost 10 years ago
s/recursive/reentrant/ of course. I blame Monday morning.
Updated by Robert Mustacchi over 2 years ago
- Assignee changed from Prasad Joshi to Robert Mustacchi
- Start date deleted (
2013-05-06)
Updated by Robert Mustacchi over 2 years ago
To test this I did a few things:
- I imported the OpenBDS quicksort tests and ran the libc test suite, run below.
- I generated a file with 1 million random integers. I then sorted it with the old libc and a new libc and compared the results and run times. The run times were approximately the same (within noise) and the results were identical.
- I disassembled the libc's and verified that we found the med3 calls were still all inlined.
Test: /opt/libc-tests/tests/aligned_alloc.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/aligned_alloc.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/c11_threads.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/c11_threads.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/c11_tss.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/c11_tss.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/call_once.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/call_once.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/catopen (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/endian.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/endian.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/env-7076.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/env-7076.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/fnmatch.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/fnmatch.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/fpround_test (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/i18n/bindtextdomain_test (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/memset_s.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/memset_s.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/newlocale_test (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/nl_langinfo_test (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/posix_memalign.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/posix_memalign.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/printf-6961.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/printf-9511.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/printf-9511.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/priv_gettext (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/psignal (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/pthread_attr_get_np (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/qsort/qsort_test (run as root) [00:02] [PASS] Test: /opt/libc-tests/tests/quick_exit (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/arc4key.ksh (run as root) [00:01] [PASS] Test: /opt/libc-tests/tests/random/arc4random (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/arc4random_fork (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/arc4random_forkall (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/arc4random_forksig (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/arc4random_prefork (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/arc4random_preforkall (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/arc4random_preforksig (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/chacha (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/getentropy (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/getrandom (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/inz_child (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/inz_inval (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/inz_mlock (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/inz_region (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/inz_split (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/inz_split_vpp (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/random/inz_vpp (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/regex/regex_test (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/select/select.sh (run as root) [00:08] [PASS] Test: /opt/libc-tests/tests/set_constraint_handler_s.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/set_constraint_handler_s.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/fileno.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/fileno.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/fmemopentest.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/fmemopentest.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/ftell_ungetc.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/ftell_ungetc.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/ftello_12768.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/ftello_12768.lfs (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/memstream.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/memstream.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/memstream_reopen.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/memstream_reopen.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/open_memstreamtest.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/open_memstreamtest.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/orientation_test.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/orientation_test.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/test_mbrtowc.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/stdio/test_mbrtowc.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/strcoll-strxfrm-6907.32 (run as root) [00:01] [PASS] Test: /opt/libc-tests/tests/strcoll-strxfrm-6907.64 (run as root) [00:01] [PASS] Test: /opt/libc-tests/tests/strerror (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/thread_name (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/timespec_get.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/timespec_get.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/uchar.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/uchar.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/wcsncasecmp-7344.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/wcsncasecmp-7344.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/wcsncasecmp-7350.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/wcsncasecmp-7350.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/wcsncasecmp.32 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/wcsncasecmp.64 (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/wcsrtombs_test (run as root) [00:01] [PASS] Test: /opt/libc-tests/tests/wctype_test (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/symbols/setup (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/symbols/assert_h (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/symbols/ctype_h (run as root) [00:23] [PASS] Test: /opt/libc-tests/tests/symbols/dirent_h (run as root) [00:05] [PASS] Test: /opt/libc-tests/tests/symbols/fcntl_h (run as root) [00:14] [PASS] Test: /opt/libc-tests/tests/symbols/locale_h (run as root) [00:10] [PASS] Test: /opt/libc-tests/tests/symbols/math_h (run as root) [00:04] [PASS] Test: /opt/libc-tests/tests/symbols/netdb_h (run as root) [00:01] [PASS] Test: /opt/libc-tests/tests/symbols/pthread_h (run as root) [00:03] [PASS] Test: /opt/libc-tests/tests/symbols/signal_h (run as root) [00:01] [PASS] Test: /opt/libc-tests/tests/symbols/stdalign_h (run as root) [00:01] [PASS] Test: /opt/libc-tests/tests/symbols/stddef_h (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/symbols/stdio_h (run as root) [00:13] [PASS] Test: /opt/libc-tests/tests/symbols/stdlib_h (run as root) [00:12] [PASS] Test: /opt/libc-tests/tests/symbols/stdnoreturn_h (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/symbols/string_h (run as root) [00:01] [PASS] Test: /opt/libc-tests/tests/symbols/strings_h (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/symbols/sys_stat_h (run as root) [00:07] [PASS] Test: /opt/libc-tests/tests/symbols/sys_time_h (run as root) [00:01] [PASS] Test: /opt/libc-tests/tests/symbols/sys_timeb_h (run as root) [00:00] [PASS] Test: /opt/libc-tests/tests/symbols/time_h (run as root) [00:01] [PASS] Test: /opt/libc-tests/tests/symbols/threads_h (run as root) [00:23] [PASS] Test: /opt/libc-tests/tests/symbols/ucontext_h (run as root) [00:02] [PASS] Test: /opt/libc-tests/tests/symbols/unistd_h (run as root) [00:19] [PASS] Test: /opt/libc-tests/tests/symbols/wchar_h (run as root) [00:09] [PASS] Test: /opt/libc-tests/tests/symbols/wctype_h (run as root) [00:24] [PASS] Results Summary PASS 113 Running Time: 00:03:26 Percent passed: 100.0% Log directory: /var/tmp/test_results/20200912T095313
Updated by Robert Mustacchi over 2 years ago
I also tested this by running the util-tests as an extra sanity test and did a wsdiff between the workspce with this and doing an ONU onto those built bits, but then rebuliding the same workspace. In addition to the normal DOF false positives and existing acpi issues, I did find a couple more changes. In investigating them they were all changes to the read only data section and seemed to be the strings for the symbol table. The reason this changed is that gcc decided to change the number used to uniquely identify some local symbols.
Updated by Electric Monk over 2 years ago
- Status changed from New to Closed
- % Done changed from 0 to 100
git commit 44431c82ebd7ee1d7c240683235e728d70d96cf2
commit 44431c82ebd7ee1d7c240683235e728d70d96cf2 Author: Robert Mustacchi <rm@fingolfin.org> Date: 2020-09-23T15:49:23.000Z 3763 Implement qsort_r(3C) Reviewed by: Toomas Soome <tsoome@me.com> Reviewed by: Andy Fiddaman <andy@omniosce.org> Approved by: Dan McDonald <danmcd@joyent.com>