Project

General

Profile

Bug #3763

Implement qsort_r(3C)

Added by Chris Nehren over 7 years ago. Updated about 1 month ago.

Status:
Closed
Priority:
Normal
Category:
lib - userland libraries
Start date:
Due date:
% Done:

100%

Estimated time:
Difficulty:
Medium
Tags:
needs-triage
Gerrit CR:

Description

This reentrant variant of qsort(3C) is used in modern software such as libgit2. Both BSD and GNU have implementations.

#1

Updated by Chris Nehren over 7 years ago

s/recursive/reentrant/ of course. I blame Monday morning.

#2

Updated by Prasad Joshi about 7 years ago

  • Assignee set to Prasad Joshi
#3

Updated by Robert Mustacchi about 2 months ago

  • Assignee changed from Prasad Joshi to Robert Mustacchi
  • Start date deleted (2013-05-06)
#4

Updated by Robert Mustacchi about 2 months 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
#5

Updated by Electric Monk about 2 months ago

  • Gerrit CR set to 920
#6

Updated by Robert Mustacchi about 1 month 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.

#7

Updated by Electric Monk about 1 month 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>

Also available in: Atom PDF