From 709fbd3ec3595f2d1076b4fec09a739327459288 Mon Sep 17 00:00:00 2001 From: Adhemerval Zanella Date: Mon, 15 Jan 2024 11:07:21 -0300 Subject: stdlib: Reinstate stable mergesort implementation on qsort The mergesort removal from qsort implementation (commit 03bf8357e8) had the side-effect of making sorting nonstable. Although neither POSIX nor C standard specify that qsort should be stable, it seems that it has become an instance of Hyrum's law where multiple programs expect it. Also, the resulting introsort implementation is not faster than the previous mergesort (which makes the change even less appealing). This patch restores the previous mergesort implementation, with the exception of machinery that checks the resulting allocation against the _SC_PHYS_PAGES (it only adds complexity and the heuristic not always make sense depending on the system configuration and load). The alloca usage was replaced with a fixed-size buffer. For the fallback mechanism, the implementation uses heapsort. It is simpler than quicksort, and it does not suffer from adversarial inputs. With memory overcommit, it should be rarely triggered. The drawback is mergesort requires O(n) extra space, and since it is allocated with malloc the function is AS-signal-unsafe. It should be feasible to change it to use mmap, although I am not sure how urgent it is. The heapsort is also nonstable, so programs that require a stable sort would still be subject to this latent issue. The tst-qsort5 is removed since it will not create quicksort adversarial inputs with the current qsort_r implementation. Checked on x86_64-linux-gnu and aarch64-linux-gnu. Reviewed-by: Florian Weimer --- manual/argp.texi | 2 +- manual/locale.texi | 2 +- manual/search.texi | 7 ++++--- 3 files changed, 6 insertions(+), 5 deletions(-) (limited to 'manual') diff --git a/manual/argp.texi b/manual/argp.texi index b77ad68..0023441 100644 --- a/manual/argp.texi +++ b/manual/argp.texi @@ -735,7 +735,7 @@ for options, bad phase of the moon, etc. @c hol_set_group ok @c hol_find_entry ok @c hol_sort @mtslocale @acucorrupt -@c qsort dup +@c qsort dup @acucorrupt @c hol_entry_qcmp @mtslocale @c hol_entry_cmp @mtslocale @c group_cmp ok diff --git a/manual/locale.texi b/manual/locale.texi index f6afa5d..1b3f978 100644 --- a/manual/locale.texi +++ b/manual/locale.texi @@ -253,7 +253,7 @@ The symbols in this section are defined in the header file @file{locale.h}. @c calculate_head_size ok @c __munmap ok @c compute_hashval ok -@c qsort dup +@c qsort dup @acucorrupt @c rangecmp ok @c malloc @ascuheap @acsmem @c strdup @ascuheap @acsmem diff --git a/manual/search.texi b/manual/search.texi index a550858..ffaadc4 100644 --- a/manual/search.texi +++ b/manual/search.texi @@ -159,7 +159,7 @@ To sort an array using an arbitrary comparison function, use the @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare}) @standards{ISO, stdlib.h} -@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} +@safety{@prelim{}@mtsafe{}@assafe{}@acunsafe{@acucorrupt{}}} The @code{qsort} function sorts the array @var{array}. The array contains @var{count} elements, each of which is of size @var{size}. @@ -199,8 +199,9 @@ Functions}): The @code{qsort} function derives its name from the fact that it was originally implemented using the ``quick sort'' algorithm. -The implementation of @code{qsort} in this library is an in-place sort -and uses a constant extra space (allocated on the stack). +The implementation of @code{qsort} attempts to allocate auxiliary storage +and use the merge sort algorithm, without violating C standard requirement +that arguments passed to the comparison function point within the array. @end deftypefun @node Search/Sort Example -- cgit v1.1