| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
Add a test for setenv with updated environ. Verify that BZ #32588 is
fixed.
Signed-off-by: H.J. Lu <hjl.tools@gmail.com>
Reviewed-by: Florian Weimer <fweimer@redhat.com>
(cherry picked from commit 8ab34497de14e35aff09b607222fe1309ef156da)
|
|
Since internal tests don't have access to internal symbols in libm,
exclude them for internal tests. Also make tst-strtod5 and tst-strtod5i
depend on $(libm) to support older versions of GCC which can't inline
copysign family functions. This fixes BZ #32414.
Signed-off-by: H.J. Lu <hjl.tools@gmail.com>
Reviewed-by: Sunil K Pandey <skpgkp2@gmail.com>
(cherry picked from commit 5df09b444835fca6e64b3d4b4a5beb19b3b2ba21)
|
|
The test tst-strtod-underflow covers various edge cases close to the
underflow threshold for strtod (especially cases where underflow on
architectures with after-rounding tininess detection depends on the
rounding mode). Make it use the type-generic machinery, with
corresponding test inputs for each supported floating-point format, so
that other functions in the strtod family are tested for underflow
edge cases as well.
Tested for x86_64.
(cherry picked from commit 94ca2c0894f0e1b62625c369cc598a2b9236622c)
|
|
There is very little test coverage of inputs to strtod-family
functions that don't contain anything that can be parsed as a number
(one test of ".y" in tst-strtod2), and none that I can see of skipping
initial whitespace. Add some tests of these things to tst-strtod2.
Tested for x86_64.
(cherry picked from commit 378039ca578c2ea93095a1e710d96f58c68a3997)
|
|
Although there are some tests in tst-strtod2 and tst-strtod3 for the
end pointer provided by strtod when it doesn't parse the whole string,
they aren't very thorough. Add tests of more such cases to
tst-strtod2.
Tested for x86_64.
(cherry picked from commit b5d3737b305525315e0c7c93ca49eadc868eabd5)
|
|
Some of the strtod tests use type-generic machinery in tst-strtod.h to
test the strto* functions for all floating types, while others only
test double even when the tests are in fact meaningful for all
floating types.
Convert tst-strtod2 and tst-strtod5 to use the type-generic machinery
so they test all floating types. I haven't tried to convert them to
use newer test interfaces in other ways, just made the changes
necessary to use the type-generic machinery.
Tested for x86_64.
(cherry picked from commit 8de031bcb9adfa736c0caed2c79d10947b8d8f48)
|
|
As reported in bug 32045, it's incorrect for strtod/nan functions to
set errno based on overflowing payload (strtod should only set errno
for overflow / underflow of its actual result, and potentially if
nothing in the string can be parsed as a number at all; nan should be
a pure function that never sets it). Save and restore errno around
the internal strtoull call and add associated test coverage.
Tested for x86_64.
(cherry picked from commit 64f62c47e9c350f353336f2df6714e1d48ec50d8)
|
|
Some of the strtod tests use type-generic machinery in tst-strtod.h to
test the strto* functions for all floating types, while others only
test double even when the tests are in fact meaningful for all
floating types.
Convert the tests of the internal __strtod_internal interface to cover
all floating types. I haven't tried to convert them to use newer test
interfaces in other ways, just made the changes necessary to use the
type-generic machinery. As an internal interface, there are no
aliases for different types with the same ABI (however,
__strtold_internal is defined even if long double has the same ABI as
double), so macros used by the type-generic testing code are redefined
as needed to avoid expecting such aliases to be present.
Tested for x86_64.
(cherry picked from commit 3fc063dee01da4f80920a14b7db637c8501d6fd4)
|
|
As reported in bug 30220, the implementation of strtod-family
functions has a bug in the following case: the input string would,
with infinite exponent range, take one more bit to represent than is
available in the normal precision of the return type; the value
represented is in the subnormal range; and there are no nonzero bits
in the value, below those that can be represented in subnormal
precision, other than the least significant bit and possibly the
0.5ulp bit. In this case, round_and_return ends up discarding the
least significant bit.
Fix by saving that bit to merge into more_bits (it can't be merged in
at the time it's computed, because more_bits mustn't include this bit
in the case of after-rounding tininess detection checking if the
result is still subnormal when rounded to normal precision, so merging
this bit into more_bits needs to take place after that check).
Tested for x86_64.
(cherry picked from commit 457622c2fa8f9f7435822d5287a437bc8be8090d)
|
|
Add tests of underflow in tst-strtod-round, and thus also test for
errno being unchanged when there is neither overflow nor underflow.
The errno setting before the function call to test for being unchanged
is adjusted to set errno to 12345 instead of 0, so that any bugs where
strtod sets errno to 0 would be detected.
This doesn't add any new test inputs for tst-strtod-round, and in
particular doesn't cover the edge cases of underflow the way
tst-strtod-underflow does (none of the existing test inputs for
tst-strtod-round actually exercise cases that have underflow with
before-rounding tininess detection but not with after-rounding
tininess detection), but at least it provides some coverage (as per
the recent discussions) that ordinary non-overflowing non-underflowing
inputs to these functions do not set errno.
Tested for x86_64.
(cherry picked from commit d73ed2601b7c3c93c3529149a3d7f7b6177900a8)
|
|
We have no tests that errno is set to ERANGE on overflow of
strtod-family functions (we do have some tests for underflow, in
tst-strtod-underflow). Add such tests to tst-strtod-round.
Tested for x86_64.
(cherry picked from commit 207d64feb26279e152c50744e3c37e68491aca99)
|
|
Rename the identifier sz to __sz everywhere.
Fixes: a643f60c53 ("Make sure that the fortified function conditionals are constant")
(cherry picked from commit 39ca997ab378990d5ac1aadbaa52aaf1db6d526f)
(redone from scratch because of many conflicts)
|
|
Signed-off-by: John David Anglin <dave.anglin@bell.net>
Reviewed-By: Andreas K. Hüttel <dilfridge@gentoo.org>
(cherry picked from commit 8cfa4ecff21adf226984f135aa576dd8063bbba3)
|
|
The __getrandom_nocancel used by __arc4random_buf uses
INLINE_SYSCALL_CALL (which returns -1/errno) and the loop checks for
the return value instead of errno to fallback to /dev/urandom.
The malloc code now uses __getrandom_nocancel_nostatus, which uses
INTERNAL_SYSCALL_CALL, so there is no need to use the variant that does
not set errno (BZ#29624).
Checked on x86_64-linux-gnu.
Reviewed-by: Xi Ruoyao <xry111@xry111.site>
(cherry picked from commit 184b9e530e6326e668709826903b6d30dc6cac3f)
|
|
The following patch uses the GCC 14 __builtin_stdc_* builtins in stdbit.h
for the type-generic macros, so that when compiled with GCC 14 or later,
it supports not just 8/16/32/64-bit unsigned integers, but also 128-bit
(if target supports them) and unsigned _BitInt (any supported precision).
And so that the macros don't expand arguments multiple times and can be
evaluated in constant expressions.
The new testcase is gcc's gcc/testsuite/gcc.dg/builtin-stdc-bit-1.c
adjusted to test stdbit.h and the type-generic macros in there instead
of the builtins and adjusted to use glibc test framework rather than
gcc style tests with __builtin_abort ().
Signed-off-by: Jakub Jelinek <jakub@redhat.com>
Reviewed-by: Joseph Myers <josmyers@redhat.com>
(cherry picked from commit da89496337b97e6a2aaf1e81d55cf998f6db1070)
|
|
In qsort_r we allocate a buffer sized QSORT_STACK_SIZE (1024) on stack
and we intend to use it if all elements can fit into it. But there is a
typo:
if (total_size < sizeof buf)
buf = tmp;
else
/* allocate a buffer on heap and use it ... */
Here "buf" is a pointer, thus sizeof buf is just 4 or 8, instead of
1024. There is also a minor issue that we should use "<=" instead of
"<".
This bug is detected debugging some strange heap corruption running the
Ruby-3.3.0 test suite (on an experimental Linux From Scratch build using
Binutils-2.41.90 and Glibc trunk, and also Fedora Rawhide [1]). It
seems Ruby is doing some wild "optimization" by jumping into somewhere
in qsort_r instead of calling it normally, resulting in a double free of
buf if we allocate it on heap. The issue can be reproduced
deterministically with:
LD_PRELOAD=/usr/lib/libc_malloc_debug.so MALLOC_CHECK_=3 \
LD_LIBRARY_PATH=. ./ruby test/runner.rb test/ruby/test_enum.rb
in Ruby-3.3.0 tree after building it. This change would hide the issue
for Ruby, but Ruby is likely still buggy (if using this "optimization"
sorting larger arrays).
[1]:https://kojipkgs.fedoraproject.org/work/tasks/9729/111889729/build.log
Signed-off-by: Xi Ruoyao <xry111@xry111.site>
|
|
Checked on x86_64-linux-gnu.
|
|
Adjust the testing approach to start from scenarios with only 2
elements, as insertion sort no longer handles such cases.
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
|
|
When malloc fails to allocate a buffer and falls back to heapsort, the
current heapsort implementation does not perform sorting when there are
exactly two elements. Heapsort is now skipped only when there is
exactly one element.
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
|
|
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>
|
|
With clang 14 and also with main the tst-stdbit-Wconversion
issues the warnings:
../stdlib/stdbit.h:701:40: error: implicit conversion loses integer
precision: 'int' to 'uint16_t' (aka 'unsigned short')
[-Werror,-Wimplicit-int-conversion]
return __x == 0 ? 0 : ((uint16_t) 1) << (__bw16_inline (__x) - 1);
~~~~~~ ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
../stdlib/stdbit.h:707:39: error: implicit conversion loses integer
precision: 'int' to 'uint8_t' (aka 'unsigned char')
[-Werror,-Wimplicit-int-conversion]
return __x == 0 ? 0 : ((uint8_t) 1) << (__bw8_inline (__x) - 1);
~~~~~~ ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
../stdlib/stdbit.h:751:40: error: implicit conversion loses integer
precision: 'int' to 'uint16_t' (aka 'unsigned short')
[-Werror,-Wimplicit-int-conversion]
return __x <= 1 ? 1 : ((uint16_t) 2) << (__bw16_inline (__x - 1) - 1);
~~~~~~ ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../stdlib/stdbit.h:757:39: error: implicit conversion loses integer
precision: 'int' to 'uint8_t' (aka 'unsigned char')
[-Werror,-Wimplicit-int-conversion]
return __x <= 1 ? 1 : ((uint8_t) 2) << (__bw8_inline (__x - 1) - 1);
~~~~~~ ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tst-stdbit-Wconversion.c:45:31: error: implicit conversion loses integer
precision: 'unsigned short' to 'uint8_t' (aka 'unsigned char')
[-Werror,-Wimplicit-int-conversion]
(void) stdc_trailing_zeros (us);
~~~~~~~~~~~~~~~~~~~~~^~~
../stdlib/stdbit.h:164:30: note: expanded from macro
'stdc_trailing_zeros'
: stdc_trailing_zeros_uc (x))
~~~~~~~~~~~~~~~~~~~~~~~~^~
../stdlib/stdbit.h:191:52: note: expanded from macro
'stdc_trailing_zeros_uc'
# define stdc_trailing_zeros_uc(x) (__ctz8_inline (x))
~~~~~~~~~~~~~ ^
tst-stdbit-Wconversion.c:46:31: error: implicit conversion loses integer
precision: 'unsigned int' to 'uint16_t' (aka 'unsigned short')
[-Werror,-Wimplicit-int-conversion]
(void) stdc_trailing_zeros (ui);
~~~~~~~~~~~~~~~~~~~~~^~~
../stdlib/stdbit.h:163:48: note: expanded from macro
'stdc_trailing_zeros'
: sizeof (x) == 2 ? stdc_trailing_zeros_us (x) \
~~~~~~~~~~~~~~~~~~~~~~~~^~
../stdlib/stdbit.h:192:53: note: expanded from macro
'stdc_trailing_zeros_us'
# define stdc_trailing_zeros_us(x) (__ctz16_inline (x))
~~~~~~~~~~~~~~ ^
tst-stdbit-Wconversion.c:46:31: error: implicit conversion loses integer
precision: 'unsigned int' to 'uint8_t' (aka 'unsigned char')
[-Werror,-Wimplicit-int-conversion]
(void) stdc_trailing_zeros (ui);
~~~~~~~~~~~~~~~~~~~~~^~~
../stdlib/stdbit.h:164:30: note: expanded from macro
'stdc_trailing_zeros'
: stdc_trailing_zeros_uc (x))
~~~~~~~~~~~~~~~~~~~~~~~~^~
../stdlib/stdbit.h:191:52: note: expanded from macro
'stdc_trailing_zeros_uc'
# define stdc_trailing_zeros_uc(x) (__ctz8_inline (x))
~~~~~~~~~~~~~ ^
tst-stdbit-Wconversion.c:47:31: error: implicit conversion loses integer
precision: 'unsigned long' to 'uint16_t' (aka 'unsigned short')
[-Werror,-Wimplicit-int-conversion]
(void) stdc_trailing_zeros (ul);
~~~~~~~~~~~~~~~~~~~~~^~~
../stdlib/stdbit.h:163:48: note: expanded from macro
'stdc_trailing_zeros'
: sizeof (x) == 2 ? stdc_trailing_zeros_us (x) \
~~~~~~~~~~~~~~~~~~~~~~~~^~
../stdlib/stdbit.h:192:53: note: expanded from macro
'stdc_trailing_zeros_us'
# define stdc_trailing_zeros_us(x) (__ctz16_inline (x))
~~~~~~~~~~~~~~ ^
[...]
It seems to boiler down to __builtin_clz not having a variant for 8 or
16 bits. Fix it by explicit casting to the expected types. Although
not strickly required for older gcc, using the same __pacify macro
simpify the required code.
Checked on x86_64-linux-gnu and i686-linux-gnu.
|
|
With gcc 6.5.0, 7.5.0, 8.5.0, and 9.5.0 the tst-stdbit-Wconversion
issues the warnings:
../stdlib/stdbit.h: In function ‘__clo16_inline’:
../stdlib/stdbit.h:128:26: error: conversion to ‘uint16_t {aka short
unsigned int}’ from ‘int’ may alter its value [-Werror=conversion]
return __clz16_inline (~__x);
^
../stdlib/stdbit.h: In function ‘__clo8_inline’:
../stdlib/stdbit.h:134:25: error: conversion to ‘uint8_t {aka unsigned
char}’ from ‘int’ may alter its value [-Werror=conversion]
return __clz8_inline (~__x);
^
../stdlib/stdbit.h: In function ‘__cto16_inline’:
../stdlib/stdbit.h:232:26: error: conversion to ‘uint16_t {aka short
unsigned int}’ from ‘int’ may alter its value [-Werror=conversion]
return __ctz16_inline (~__x);
^
../stdlib/stdbit.h: In function ‘__cto8_inline’:
../stdlib/stdbit.h:238:25: error: conversion to ‘uint8_t {aka unsigned
char}’ from ‘int’ may alter its value [-Werror=conversion]
return __ctz8_inline (~__x);
^
../stdlib/stdbit.h: In function ‘__bf16_inline’:
../stdlib/stdbit.h:701:23: error: conversion to ‘uint16_t {aka short
unsigned int}’ from ‘int’ may alter its value [-Werror=conversion]
return __x == 0 ? 0 : ((uint16_t) 1) << (__bw16_inline (__x) - 1);
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../stdlib/stdbit.h: In function ‘__bf8_inline’:
../stdlib/stdbit.h:707:23: error: conversion to ‘uint8_t {aka unsigned
char}’ from ‘int’ may alter its value [-Werror=conversion]
return __x == 0 ? 0 : ((uint8_t) 1) << (__bw8_inline (__x) - 1);
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../stdlib/stdbit.h: In function ‘__bc16_inline’:
../stdlib/stdbit.h:751:59: error: conversion to ‘uint16_t {aka short
unsigned int}’ from ‘int’ may alter its value [-Werror=conversion]
return __x <= 1 ? 1 : ((uint16_t) 2) << (__bw16_inline (__x - 1) -
1);
^~~
../stdlib/stdbit.h:751:23: error: conversion to ‘uint16_t {aka short
unsigned int}’ from ‘int’ may alter its value [-Werror=conversion]
return __x <= 1 ? 1 : ((uint16_t) 2) << (__bw16_inline (__x - 1) -
1);
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../stdlib/stdbit.h: In function ‘__bc8_inline’:
../stdlib/stdbit.h:757:57: error: conversion to ‘uint8_t {aka unsigned
char}’ from ‘int’ may alter its value [-Werror=conversion]
return __x <= 1 ? 1 : ((uint8_t) 2) << (__bw8_inline (__x - 1) - 1);
^~~
../stdlib/stdbit.h:757:23: error: conversion to ‘uint8_t {aka unsigned
char}’ from ‘int’ may alter its value [-Werror=conversion]
return __x <= 1 ? 1 : ((uint8_t) 2) << (__bw8_inline (__x - 1) - 1);
It seems to boiler down to __builtin_clz not having a variant for 8 or
16 bits. Fix it by explicit casting to the expected types.
Checked on x86_64-linux-gnu and i686-linux-gnu with gcc 9.5.0.
|
|
C23 adds a header <stdbit.h> with various functions and type-generic
macros for bit-manipulation of unsigned integers (plus macro defines
related to endianness). Implement this header for glibc.
The functions have both inline definitions in the header (referenced
by macros defined in the header) and copies with external linkage in
the library (which are implemented in terms of those macros to avoid
duplication). They are documented in the glibc manual. Tests, as
well as verifying results for various inputs (of both the macros and
the out-of-line functions), verify the types of those results (which
showed up a bug in an earlier version with the type-generic macro
stdc_has_single_bit wrongly returning a promoted type), that the
macros can be used at top level in a source file (so don't use ({})),
that they evaluate their arguments exactly once, and that the macros
for the type-specific functions have the expected implicit conversions
to the relevant argument type.
Jakub previously referred to -Wconversion warnings in type-generic
macros, so I've included a test with -Wconversion (but the only
warnings I saw and fixed from that test were actually in inline
functions in the <stdbit.h> header - not anything coming from use of
the type-generic macros themselves).
This implementation of the type-generic macros does not handle
unsigned __int128, or unsigned _BitInt types with a width other than
that of a standard integer type (and C23 doesn't require the header to
handle such types either). Support for those types, using the new
type-generic built-in functions Jakub's added for GCC 14, can
reasonably be added in a followup (along of course with associated
tests).
This implementation doesn't do anything special to handle C++, or have
any tests of functionality in C++ beyond the existing tests that all
headers can be compiled in C++ code; it's not clear exactly what form
this header should take in C++, but probably not one using macros.
DIS ballot comment AT-107 asks for the word "count" to be added to the
names of the stdc_leading_zeros, stdc_leading_ones,
stdc_trailing_zeros and stdc_trailing_ones functions and macros. I
don't think it's likely to be accepted (accepting any technical
comments would mean having an FDIS ballot), but if it is accepted at
the WG14 meeting (22-26 January in Strasbourg, starting with DIS
ballot comment handling) then there would still be time to update
glibc for the renaming before the 2.39 release.
The new functions and header are placed in the stdlib/ directory in
glibc, rather than creating a new toplevel stdbit/ or putting them in
string/ alongside ffs.
Tested for x86_64 and x86.
|
|
Verify that setjmp and longjmp work correctly between user contexts.
Arrange stacks for uctx_func1 and uctx_func2 so that ____longjmp_chk
works when setjmp and longjmp are called from different user contexts.
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
|
|
|
|
When _FORTIFY_SOURCE is defined to 2, ____longjmp_chk is called,
instead of longjmp. ____longjmp_chk compares the relative stack
values to decide if it is called from a stack frame which called
setjmp. If not, ____longjmp_chk assumes that an alternate signal
stack is used. Since comparing the relative stack values isn't
reliable with user context, when there is no signal, ____longjmp_chk
will fail. Undefine _FORTIFY_SOURCE to avoid ____longjmp_chk in
user context test.
|
|
Verify that setjmp/longjmp works correctly within a user context.
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
|
|
Verify that longjmp works correctly after setcontext is called to switch
to a user context.
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
|
|
The previous check did not do anything because tmp_ptr already
points before run_ptr due to the way it is initialized.
Fixes commit e4d8117b82065dc72e8df80097360e7c05a349b9
("stdlib: Avoid another self-comparison in qsort").
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
|
|
The existing logic avoided internal stack overflow. To avoid
a denial-of-service condition with adversarial input, it is necessary
to fall over to heapsort if tail-recursing deeply, too, which does
not result in a deep stack of pending partitions.
The new test stdlib/tst-qsort5 is based on Douglas McIlroy's paper
on this subject.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
|
|
The previous implementation did not consistently apply the rule that
the child nodes of node K are at 2 * K + 1 and 2 * K + 2, or
that the parent node is at (K - 1) / 2.
Add an internal test that targets the heapsort implementation
directly.
Reported-by: Stepan Golosunov <stepan@golosunov.pp.ru>
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
|
|
In the insertion phase, we could run off the start of the array if the
comparison function never runs zero. In that case, it never finds the
initial element that terminates the iteration.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
|
|
This improves compatibility with applications which assume that qsort
does not invoke the comparison function with equal pointer arguments.
The newly introduced branches should be predictable, as leading to a
call to the comparison function. If the prediction fails, we avoid
calling the function.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
|
|
This patch adds a qsort and qsort_r to trigger the worst case
scenario for the quicksort (which glibc current lacks coverage).
The test is done with random input, dfferent internal types (uint8_t,
uint16_t, uint32_t, uint64_t, large size), and with
different set of element numbers.
Checked on x86_64-linux-gnu and i686-linux-gnu.
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
|
|
This patch removes the mergesort optimization on qsort implementation
and uses the introsort instead. The mergesort implementation has some
issues:
- It is as-safe only for certain types sizes (if total size is less
than 1 KB with large element sizes also forcing memory allocation)
which contradicts the function documentation. Although not required
by the C standard, it is preferable and doable to have an O(1) space
implementation.
- The malloc for certain element size and element number adds
arbitrary latency (might even be worse if malloc is interposed).
- To avoid trigger swap from memory allocation the implementation
relies on system information that might be virtualized (for instance
VMs with overcommit memory) which might lead to potentially use of
swap even if system advertise more memory than actually has. The
check also have the downside of issuing syscalls where none is
expected (although only once per execution).
- The mergesort is suboptimal on an already sorted array (BZ#21719).
The introsort implementation is already optimized to use constant extra
space (due to the limit of total number of elements from maximum VM
size) and thus can be used to avoid the malloc usage issues.
Resulting performance is slower due the usage of qsort, specially in the
worst-case scenario (partialy or sorted arrays) and due the fact
mergesort uses a slight improved swap operations.
This change also renders the BZ#21719 fix unrequired (since it is meant
to fix the sorted input performance degradation for mergesort). The
manual is also updated to indicate the function is now async-cancel
safe.
Checked on x86_64-linux-gnu.
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
|
