about summary refs log tree commit diff
path: root/manual/locale.texi
diff options
context:
space:
mode:
authorAdhemerval Zanella <adhemerval.zanella@linaro.org>2024-01-15 11:07:21 -0300
committerAdhemerval Zanella <adhemerval.zanella@linaro.org>2024-01-15 15:58:35 -0300
commit709fbd3ec3595f2d1076b4fec09a739327459288 (patch)
tree7d0b3f146b1d659a5f620bd74557e2869f77ea79 /manual/locale.texi
parent457bd9cf2e27550dd66b2d8f3c5a8dbd0dfb398f (diff)
downloadglibc-709fbd3ec3595f2d1076b4fec09a739327459288.tar.gz
glibc-709fbd3ec3595f2d1076b4fec09a739327459288.tar.xz
glibc-709fbd3ec3595f2d1076b4fec09a739327459288.zip
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 <fweimer@redhat.com>
Diffstat (limited to 'manual/locale.texi')
-rw-r--r--manual/locale.texi2
1 files changed, 1 insertions, 1 deletions
diff --git a/manual/locale.texi b/manual/locale.texi
index f6afa5dc44..1b3f97839b 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