Commit Graph

1104 Commits

Author SHA1 Message Date
Adhemerval Zanella
461cab1de7 linux: Add support for getrandom vDSO
Linux 6.11 has getrandom() in vDSO. It operates on a thread-local opaque
state allocated with mmap using flags specified by the vDSO.

Multiple states are allocated at once, as many as fit into a page, and
these are held in an array of available states to be doled out to each
thread upon first use, and recycled when a thread terminates. As these
states run low, more are allocated.

To make this procedure async-signal-safe, a simple guard is used in the
LSB of the opaque state address, falling back to the syscall if there's
reentrancy contention.

Also, _Fork() is handled by blocking signals on opaque state allocation
(so _Fork() always sees a consistent state even if it interrupts a
getrandom() call) and by iterating over the thread stack cache on
reclaim_stack. Each opaque state will be in the free states list
(grnd_alloc.states) or allocated to a running thread.

The cancellation is handled by always using GRND_NONBLOCK flags while
calling the vDSO, and falling back to the cancellable syscall if the
kernel returns EAGAIN (would block). Since getrandom is not defined by
POSIX and cancellation is supported as an extension, the cancellation is
handled as 'may occur' instead of 'shall occur' [1], meaning that if
vDSO does not block (the expected behavior) getrandom will not act as a
cancellation entrypoint. It avoids a pthread_testcancel call on the fast
path (different than 'shall occur' functions, like sem_wait()).

It is currently enabled for x86_64, which is available in Linux 6.11,
and aarch64, powerpc32, powerpc64, loongarch64, and s390x, which are
available in Linux 6.12.

Link: https://pubs.opengroup.org/onlinepubs/9799919799/nframe.html [1]
Co-developed-by: Jason A. Donenfeld <Jason@zx2c4.com>
Tested-by: Jason A. Donenfeld <Jason@zx2c4.com> # x86_64
Tested-by: Adhemerval Zanella <adhemerval.zanella@linaro.org> # x86_64, aarch64
Tested-by: Xi Ruoyao <xry111@xry111.site> # x86_64, aarch64, loongarch64
Tested-by: Stefan Liebler <stli@linux.ibm.com> # s390x
2024-11-12 14:42:12 -03:00
Adhemerval Zanella
d40ac01cbb stdlib: Make abort/_Exit AS-safe (BZ 26275)
The recursive lock used on abort does not synchronize with a new process
creation (either by fork-like interfaces or posix_spawn ones), nor it
is reinitialized after fork().

Also, the SIGABRT unblock before raise() shows another race condition,
where a fork or posix_spawn() call by another thread, just after the
recursive lock release and before the SIGABRT signal, might create
programs with a non-expected signal mask.  With the default option
(without POSIX_SPAWN_SETSIGDEF), the process can see SIG_DFL for
SIGABRT, where it should be SIG_IGN.

To fix the AS-safe, raise() does not change the process signal mask,
and an AS-safe lock is used if a SIGABRT is installed or the process
is blocked or ignored.  With the signal mask change removal,
there is no need to use a recursive loc.  The lock is also taken on
both _Fork() and posix_spawn(), to avoid the spawn process to see the
abort handler as SIG_DFL.

A read-write lock is used to avoid serialize _Fork and posix_spawn
execution.  Both sigaction (SIGABRT) and abort() requires to lock
as writer (since both change the disposition).

The fallback is also simplified: there is no need to use a loop of
ABORT_INSTRUCTION after _exit() (if the syscall does not terminate the
process, the system is broken).

The proposed fix changes how setjmp works on a SIGABRT handler, where
glibc does not save the signal mask.  So usage like the below will now
always abort.

  static volatile int chk_fail_ok;
  static jmp_buf chk_fail_buf;

  static void
  handler (int sig)
  {
    if (chk_fail_ok)
      {
        chk_fail_ok = 0;
        longjmp (chk_fail_buf, 1);
      }
    else
      _exit (127);
  }
  [...]
  signal (SIGABRT, handler);
  [....]
  chk_fail_ok = 1;
  if (! setjmp (chk_fail_buf))
    {
      // Something that can calls abort, like a failed fortify function.
      chk_fail_ok = 0;
      printf ("FAIL\n");
    }

Such cases will need to use sigsetjmp instead.

The _dl_start_profile calls sigaction through _profil, and to avoid
pulling abort() on loader the call is replaced with __libc_sigaction.

Checked on x86_64-linux-gnu and aarch64-linux-gnu.

Reviewed-by: DJ Delorie <dj@redhat.com>
2024-10-08 14:40:12 -03:00
Joseph Myers
94ca2c0894 Make tst-strtod-underflow type-generic
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.
2024-09-20 23:25:32 +00:00
Joseph Myers
378039ca57 Add tests of more strtod special cases
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.
2024-09-20 23:24:45 +00:00
Joseph Myers
b5d3737b30 Add more tests of strtod end pointer
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.
2024-09-20 23:24:02 +00:00
Joseph Myers
8de031bcb9 Make tst-strtod2 and tst-strtod5 type-generic
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.
2024-09-20 23:23:13 +00:00
Joseph Myers
64f62c47e9 Do not set errno for overflowing NaN payload in strtod/nan (bug 32045)
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.
2024-09-04 13:21:23 +00:00
Joseph Myers
3fc063dee0 Make __strtod_internal tests type-generic
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.
2024-08-27 20:41:54 +00:00
Joseph Myers
457622c2fa Fix strtod subnormal rounding (bug 30220)
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.
2024-08-27 12:41:02 +00:00
Joseph Myers
d73ed2601b More thoroughly test underflow / errno in tst-strtod-round
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.
2024-08-27 12:38:01 +00:00
Florian Weimer
e7c14e542d support: Use macros for *stat wrappers
Macros will automatically use the correct types, without
having to fiddle with internal glibc macros.  It's also
impossible to get the types wrong due to aliasing because
support_check_stat_fd and support_check_stat_path do not
depend on the struct stat* types.

The changes reveal some inconsistencies in tests.

Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
2024-08-16 16:05:20 +02:00
Joseph Myers
207d64feb2 Test errno setting on strtod overflow in tst-strtod-round
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.
2024-08-14 17:15:46 +00:00
Adhemerval Zanella
c2a05c99e3 stdlib: Link tst-concurrent-quick_exit with $(shared-thread-library)
This avoids a Hurd build failure.  Fixes commit c6af8a9a3c
("stdlib: Allow concurrent quick_exit (BZ 31997)").
2024-08-06 14:01:27 -03:00
Adhemerval Zanella
c6af8a9a3c stdlib: Allow concurrent quick_exit (BZ 31997)
As for exit, also allows concurrent quick_exit to avoid race
conditions when it is called concurrently.  Since it uses the same
internal function as exit, the __exit_lock lock is moved to
__run_exit_handlers.  It also solved a potential concurrent when
calling exit and quick_exit concurrently.

The test case 'expected' is expanded to a value larger than the
minimum required by C/POSIX (32 entries) so at_quick_exit() will
require libc to allocate a new block.  This makes the test mre likely to
trigger concurrent issues (through free() at __run_exit_handlers)
if quick_exit() interacts with the at_quick_exit list concurrently.

This is also the latest interpretation of the Austin Ticket [1].

Checked on x86_64-linux-gnu.

[1] https://austingroupbugs.net/view.php?id=1845
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
2024-08-05 17:07:57 -03:00
Andreas Schwab
39ca997ab3 Fix name space violation in fortify wrappers (bug 32052)
Rename the identifier sz to __sz everywhere.

Fixes: a643f60c53 ("Make sure that the fortified function conditionals are constant")
2024-08-05 16:49:58 +02:00
Florian Weimer
fb507de8fc stdlib: Link tst-concurrent-exit with $(shared-thread-library)
This avoids a Hurd build failure.  Fixes commit f6ba993e0c
("stdlib: Allow concurrent exit (BZ 31997)").
2024-08-02 14:45:10 +02:00
Noah Goldstein
e3b0b3484c stdlib: Mark abort as cold
This helps HotColdSplitting in GCC/LLVM.

Thought about doing `exit` as well since its only called once per
process, but since its easy to imagine a hot path leading into
`exit(0)`, its less clear if its profitable.

Reviewed-by: Carlos O'Donell <carlos@redhat.com>
2024-07-31 14:26:00 +08:00
Adhemerval Zanella
f6ba993e0c stdlib: Allow concurrent exit (BZ 31997)
Even if C/POSIX standard states that exit is not formally thread-unsafe,
calling it more than once is UB.  The glibc already supports
it for the single-thread, and both elf/nodelete2.c and tst-rseq-disable.c
call exit from a DSO destructor (which is called by _dl_fini, registered
at program startup with __cxa_atexit).

However, there are still race issues when it is called more than once
concurrently by multiple threads.  A recent Rust PR triggered this
issue [1], which resulted in an Austin Group ask for clarification [2].
Besides it, there is a discussion to make concurrent calling not UB [3],
wtih a defined semantic where any remaining callers block until the first
call to exit has finished (reentrant calls, leaving through longjmp, and
exceptions are still undefined).

For glibc, at least reentrant calls are required to be supported to avoid
changing the current behaviour.  This requires locking using a recursive
lock, where any exit called by atexit() handlers resumes at the point of
the current handler (thus avoiding calling the current handle multiple
times).

Checked on x86_64-linux-gnu and aarch64-linux-gnu.

[1] https://github.com/rust-lang/rust/issues/126600
[2] https://austingroupbugs.net/view.php?id=1845
[3] https://www.openwall.com/lists/libc-coord/2024/07/24/4
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
2024-07-30 08:54:23 -03:00
John David Anglin
8cfa4ecff2 Fix usage of _STACK_GROWS_DOWN and _STACK_GROWS_UP defines [BZ 31989]
Signed-off-by: John David Anglin <dave.anglin@bell.net>
Reviewed-By: Andreas K. Hüttel <dilfridge@gentoo.org>
2024-07-19 10:10:17 -04:00
Adhemerval Zanella
184b9e530e stdlib: fix arc4random fallback to /dev/urandom (BZ 31612)
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>
2024-07-08 10:05:10 -03:00
Florian Weimer
992daa0b4b stdlib: Describe __cxa_finalize usage in function comment
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
2024-06-03 19:04:58 +02:00
Stafford Horne
4a13b3ef46 stdlib: Fix tst-makecontext2 log when swapcontext fails
The log incorrectly prints, setcontext failed.  Update this to indicate
that actually swapcontext failed.

Signed-off-by: Stafford Horne <shorne@gmail.com>
Reviewed-by: H.J. Lu <hjl.tools@gmail.com>
2024-03-23 08:36:28 +00:00
Adhemerval Zanella
d39a893ed6 stdlib: Improve fortify with clang
It improve fortify checks for realpath, ptsname_r, wctomb, mbstowcs,
and wcstombs.  The runtime and compile checks have similar coverage as
with GCC.

Checked on aarch64, armhf, x86_64, and i686.
Tested-by: Carlos O'Donell <carlos@redhat.com>
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
2024-02-27 10:52:58 -03:00
Dragan Stanojević (Nevidljivi)
559010e471 localedata: hr_HR: change currency to EUR/€
Resolves: BZ # 29845
2024-02-08 08:13:37 +01:00
Joseph Myers
83d8d289b2 Rename c2x / gnu2x tests to c23 / gnu23
Complete the internal renaming from "C2X" and related names in GCC by
renaming *-c2x and *-gnu2x tests to *-c23 and *-gnu23.

Tested for x86_64, and with build-many-glibcs.py for powerpc64le.
2024-02-01 17:55:57 +00:00
Joseph Myers
42cc619dfb Refer to C23 in place of C2X in glibc
WG14 decided to use the name C23 as the informal name of the next
revision of the C standard (notwithstanding the publication date in
2024).  Update references to C2X in glibc to use the C23 name.

This is intended to update everything *except* where it involves
renaming files (the changes involving renaming tests are intended to
be done separately).  In the case of the _ISOC2X_SOURCE feature test
macro - the only user-visible interface involved - support for that
macro is kept for backwards compatibility, while adding
_ISOC23_SOURCE.

Tested for x86_64.
2024-02-01 11:02:01 +00:00
Jakub Jelinek
da89496337 Use gcc __builtin_stdc_* builtins in stdbit.h if possible
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>
2024-01-31 19:17:27 +01:00
Xi Ruoyao
dfa3394a60 qsort: Fix a typo causing unnecessary malloc/free (BZ 31276)
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>
2024-01-23 05:17:31 -08:00
Adhemerval Zanella
31bd548650 stdlib: Remove unused is_aligned function from qsort.c
Checked on x86_64-linux-gnu.
2024-01-17 08:08:56 -03:00
Kuan-Wei Chiu
1bb28b7b4f stdlib: Verify heapsort for two-element cases
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>
2024-01-16 11:00:51 -03:00
Kuan-Wei Chiu
74d2731a5f stdlib: Fix heapsort for cases with exactly two elements
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>
2024-01-16 11:00:51 -03:00
Adhemerval Zanella
709fbd3ec3 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>
2024-01-15 15:58:35 -03:00
Adhemerval Zanella
48ef5aeb1b stdlib: Fix stdbit.h with -Wconversion for clang
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.
2024-01-05 14:52:29 -03:00
Adhemerval Zanella
c8e31fbf04 stdlib: Fix stdbit.h with -Wconversion for older gcc
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.
2024-01-05 14:52:29 -03:00
Joseph Myers
b34b46b880 Implement C23 <stdbit.h>
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.
2024-01-03 12:07:14 +00:00
H.J. Lu
8d8ae5eebd Add a setjmp/longjmp test between user contexts
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>
2024-01-01 15:55:38 -08:00
Paul Eggert
dff8da6b3e Update copyright dates with scripts/update-copyrights 2024-01-01 10:53:40 -08:00
H.J. Lu
46432be2f1 tst-setcontext10.c: Undef _FORTIFY_SOURCE
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.
2023-12-19 13:39:34 -08:00
H.J. Lu
49b4de21dc Add a test for setjmp/longjmp within user context
Verify that setjmp/longjmp works correctly within a user context.
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
2023-12-16 08:39:08 -08:00
H.J. Lu
08bc191fd1 Add a test for longjmp from user context
Verify that longjmp works correctly after setcontext is called to switch
to a user context.
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
2023-12-16 08:38:48 -08:00
Florian Weimer
b9390ba936 stdlib: Fix array bounds protection in insertion sort phase of qsort
The previous check did not do anything because tmp_ptr already
points before run_ptr due to the way it is initialized.

Fixes commit e4d8117b82
("stdlib: Avoid another self-comparison in qsort").

Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
2023-12-04 06:35:56 +01:00
Florian Weimer
64e4acf24d stdlib: The qsort implementation needs to use heapsort in more cases
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>
2023-11-21 16:46:18 +01:00
Florian Weimer
55364e1f7d stdlib: Handle various corner cases in the fallback heapsort for qsort
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>
2023-11-21 16:46:02 +01:00
Florian Weimer
e4d8117b82 stdlib: Avoid another self-comparison in qsort
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>
2023-11-21 16:45:47 +01:00
Florian Weimer
f8cfb6836e stdlib: Avoid element self-comparisons in qsort
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>
2023-11-08 15:18:02 +01:00
Adhemerval Zanella
bc888a3976 stdlib: Add more qsort{_r} coverage
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>
2023-10-31 14:18:07 -03:00
Adhemerval Zanella
03bf8357e8 stdlib: Remove use of mergesort on qsort (BZ 21719)
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>
2023-10-31 14:18:05 -03:00
Adhemerval Zanella
274a46c9b2 stdlib: Implement introsort for qsort (BZ 19305)
This patch makes the quicksort implementation to acts as introsort, to
avoid worse-case performance (and thus making it O(nlog n)).  It switch
to heapsort when the depth level reaches 2*log2(total elements).  The
heapsort is a textbook implementation.

Checked on x86_64-linux-gnu and aarch64-linux-gnu.
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
2023-10-31 14:18:03 -03:00
Adhemerval Zanella
d097f3c79b stdlib: qsort: Move some macros to inline function
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
2023-10-31 14:17:53 -03:00
Adhemerval Zanella
a035a9857e stdlib: Move insertion sort out qsort
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
2023-10-31 14:17:45 -03:00