add membarrier syscall wrapper, refactor dynamic tls install to use it

the motivation for this change is twofold. first, it gets the fallback
logic out of the dynamic linker, improving code readability and
organization. second, it provides application code that wants to use
the membarrier syscall, which depends on preregistration of intent
before the process becomes multithreaded unless unbounded latency is
acceptable, with a symbol that, when linked, ensures that this
registration happens.

make thread list lock a recursive lock

this is a prerequisite for factoring the membarrier fallback code into
a function that can be called from a context with the thread list
already locked or independently.

fix loop logic cruft in dynamic tls installation

commit 9d44b6460ab603487dab4d916342d9ba4467e6b9 inadvertently
contained leftover logic from a previous approach to the fallback
signaling loop. it had no adverse effect, since j was always nonzero
if the loop body was reachable, but it makes no sense to be there with
the current approach to avoid signaling self.

fix spurious undefined behavior in getaddrinfo

addressing &out[k].sa was arguably undefined, despite &out[k] being
defined the slot one past the end of an array, since the member access
.sa is intervening between the [] operator and the & operator.

fix invalid free of partial addrinfo list with multiple services

the backindex stored by getaddrinfo to allow freeaddrinfo to perform
partial-free wrongly used the address result index, rather than the
output slot index, and thus was only valid when they were equal
(nservs==1).

patch based on report with proposed fix by Markus Wichmann.

install dynamic tls synchronously at dlopen, streamline access

previously, dynamic loading of new libraries with thread-local storage
allocated the storage needed for all existing threads at load-time,
precluding late failure that can't be handled, but left installation
in existing threads to take place lazily on first access. this imposed
an additional memory access and branch on every dynamic tls access,
and imposed a requirement, which was not actually met, that the
dynamic tlsdesc asm functions preserve all call-clobbered registers
before calling C code to to install new dynamic tls on first access.
the x86[_64] versions of this code wrongly omitted saving and
restoring of fpu/vector registers, assuming the compiler would not
generate anything using them in the called C code. the arm and aarch64
versions saved known existing registers, but failed to be future-proof
against expansion of the register file.

now that we track live threads in a list, it's possible to install the
new dynamic tls for each thread at dlopen time. for the most part,
synchronization is not needed, because if a thread has not
synchronized with completion of the dlopen, there is no way it can
meaningfully request access to a slot past the end of the old dtv,
which remains valid for accessing slots which already existed.
however, it is necessary to ensure that, if a thread sees its new dtv
pointer, it sees correct pointers in each of the slots that existed
prior to the dlopen. my understanding is that, on most real-world
coherency architectures including all the ones we presently support, a
built-in consume order guarantees this; however, don't rely on that.
instead, the SYS_membarrier syscall is used to ensure that all threads
see the stores to the slots of their new dtv prior to the installation
of the new dtv. if it is not supported, the same is implemented in
userspace via signals, using the same mechanism as __synccall.

the __tls_get_addr function, variants, and dynamic tlsdesc asm
functions are all updated to remove the fallback paths for claiming
new dynamic tls, and are now all branch-free.

fix data race between new pthread_key_delete and dtor execution

access to clear the entry in each thread's tsd array for the key being
deleted was not synchronized with __pthread_tsd_run_dtors. I probably
made this mistake from a mistaken belief that the thread list lock was
held during the latter, which of course is not possible since it
executes application code in a still-live-thread context.

while we're at it, expand the interval during which signals are
blocked to cover taking the write lock on key_lock, so that a signal
at an inopportune time doesn't block forward progress of readers.

introduce namespace-safe rwlock aliases; use in pthread_key_create

commit 84d061d5a31c9c773e29e1e2b1ffe8cb9557bc58 inadvertently
introduced namespace violations by using the pthread-namespace rwlock
functions in pthread_key_create, which is in turn used for C11 tss.
fix that and possible future uses of rwlocks elsewhere.

rewrite pthread_key_delete to use global thread list

with the availability of the thread list, there is no need to mark tsd
key slots dirty and clean them up only when a free slot can't be
found. instead, directly iterate threads and clear any value
associated with the key being deleted.

no synchronization is necessary for the clearing, since there is no
way the slot can be accessed without having synchronized with the
creation of a new key occupying the same slot, which is already
sequenced after and synchronized with the deletion of the old key.

rewrite __synccall in terms of global thread list

the __synccall mechanism provides stop-the-world synchronous execution
of a callback in all threads of the process. it is used to implement
multi-threaded setuid/setgid operations, since Linux lacks them at the
kernel level, and for some other less-critical purposes.

this change eliminates dependency on /proc/self/task to determine the
set of live threads, which in addition to being an unwanted dependency
and a potential point of resource-exhaustion failure, turned out to be
inaccurate. test cases provided by Alexey Izbyshev showed that it
could fail to reflect newly created threads. due to how the
presignaling phase worked, this usually yielded a deadlock if hit, but
in the worst case it could also result in threads being silently
missed (allowed to continue running without executing the callback).

track all live threads in an AS-safe, fully-consistent linked list

the hard problem here is unlinking threads from a list when they exit
without creating a window of inconsistency where the kernel task for a
thread still exists and is still executing instructions in userspace,
but is not reflected in the list. the magic solution here is getting
rid of per-thread exit futex addresses (set_tid_address), and instead
using the exit futex to unlock the global thread list.

since pthread_join can no longer see the thread enter a detach_state
of EXITED (which depended on the exit futex address pointing to the
detach_state), it must now observe the unlocking of the thread list
lock before it can unmap the joined thread and return. it doesn't
actually have to take the lock. for this, a __tl_sync primitive is
offered, with a signature that will allow it to be enhanced for quick
return even under contention on the lock, if needed. for now, the
exiting thread always performs a futex wake on its detach_state. a
future change could optimize this out except when there is already a
joiner waiting.

initial/dynamic variants of detached state no longer need to be
tracked separately, since the futex address is always set to the
global list lock, not a thread-local address that could become invalid
on detached thread exit. all detached threads, however, must perform a
second sigprocmask syscall to block implementation-internal signals,
since locking the thread list with them already blocked is not
permissible.

the arch-independent C version of __unmapself no longer needs to take
a lock or setup its own futex address to release the lock, since it
must necessarily be called with the thread list lock already held,
guaranteeing exclusive access to the temporary stack.

changes to libc.threads_minus_1 no longer need to be atomic, since
they are guarded by the thread list lock. it is largely vestigial at
this point, and can be replaced with a cheaper boolean indicating
whether the process is multithreaded at some point in the future.

always block signals for starting new threads, refactor start args

whether signals need to be blocked at thread start, and whether
unblocking is necessary in the entry point function, has historically
depended on intricacies of the cancellation design and on whether
there are scheduling operations to perform on the new thread before
its successful creation can be committed. future changes to track an
AS-safe list of live threads will require signals to be blocked
whenever changes are made to the list, so ...

prior to commits b8742f32602add243ee2ce74d804015463726899 and
40bae2d32fd6f3ffea437fa745ad38a1fe77b27e, a signal mask for the entry
function to restore was part of the pthread structure. it was removed
to trim down the size of the structure, which both saved a small
amount of stack space and improved code generation on archs where
small immediate displacements are less costly than arbitrary ones, by
limiting the range of offsets between the base of the thread
structure, its members, and the thread pointer. these commits moved
the saved mask to a special structure used only when special
scheduling was needed, in which case the pthread_create caller and new
thread had to synchronize with each other and could use this memory to
pass a mask.

this commit partially reverts the above two commits, but instead of
putting the mask back in the pthread structure, it moves all "start
argument" members out of the pthread structure, trimming it down
further, and puts them in a separate structure passed on the new
thread's stack. the code path for explicit scheduling of the new
thread is also changed to synchronize with the calling thread in such
a way to avoid spurious futex wakes.

for SIGEV_THREAD timer threads, replace signal handler with sigwaitinfo

this eliminates some ugly hacks that were repurposing the start
function and start argument fields in the pthread structure for timer
use, and the need to longjmp out of a signal handler.

defer free of thread-local dlerror buffers from inconsistent context

__dl_thread_cleanup is called from the context of an exiting thread
that is not in a consistent state valid for calling application code.
since commit c9f415d7ea2dace5bf77f6518b6afc36bb7a5732, it's possible
(and supported usage) for the allocator to have been replaced by the
application, so __dl_thread_cleanup can no longer call free. instead,
reuse the message buffer as a linked-list pointer, and queue it to be
freed the next time any dynamic linker error message is generated.

fix behavior of gets when input line contains a null byte

the way gets was implemented in terms of fgets, it used the location
of the null termination to determine where to find and remove the
newline, if any. an embedded null byte prevented this from working.

this also fixes a one-byte buffer overflow, whereby when gets read an
N-byte line (not counting newline), it would store two null
terminators for a total of N+2 bytes. it's unlikely that anyone would
care that a function whose use is pretty much inherently a buffer
overflow writes too much, but it could break the only possible correct
uses of this function, in conjunction with input of known format from
a trusted/same-privilege-domain source, where the buffer length may
have been selected to exactly match a line length contract.

there seems to be no correct way to implement gets in terms of a
single call to fgets or scanf, and using multiple calls would require
explicit locking, so we might as well just write the logic out
explicitly character-at-a-time. this isn't fast, but nobody cares if a
catastrophically unsafe function that's so bad it was removed from the
C language is fast.

redesign robust mutex states to eliminate data races on type field

in order to implement ENOTRECOVERABLE, the implementation has
traditionally used a bit of the mutex type field to indicate that it's
recovered after EOWNERDEAD and will go into ENOTRECOVERABLE state if
pthread_mutex_consistent is not called before unlocking. while it's
only the thread that holds the lock that needs access to this
information (except possibly for the sake of pthread_mutex_consistent
choosing between EINVAL and EPERM for erroneous calls), the change to
the type field is formally a data race with all other threads that
perform any operation on the mutex. no individual bits race, and no
write races are possible, so things are "okay" in some sense, but it's
still not good.

this patch moves the recovery/consistency state to the mutex
owner/lock field which is rightfully mutable. bit 30, the same bit the
kernel uses with a zero owner to indicate that the previous owner died
holding the lock, is now used with a nonzero owner to indicate that
the mutex is held but has not yet been marked consistent. note that
the kernel ABI also reserves bit 29 not to appear in any tid, so the
sentinel value we use for ENOTRECOVERABLE, 0x7fffffff, does not clash
with any tid plus bit 30.

fail fdopendir for O_PATH file descriptors

fdopendir is specified to fail with EBADF if the file descriptor
passed is not open for reading. while O_PATH is an extension and
arguably exempt from this requirement, it's used, albeit incompletely,
to implement O_SEARCH, and fdopendir should fail when passed an
O_SEARCH file descriptor.

the new check is performed after fstat so that we don't have to
consider the possibility that the fd is invalid.

an alternate solution would be attempting to pre-fill the buffer using
getdents, which would fail with EBADF for us, but that seems more
complex and error-prone and involves either code duplication or
refactoring, so the simple fix with an additional inexpensive syscall
is what I've made for now.

update line discipline constants

move arch-invariant definitions out of bits/ioctl.h

locale: ensure dcngettext() preserves errno

Some packages call gettext to format a message to be sent to perror.
If the currently set user locale points to a non-existent .mo file,
open via __map_file in dcngettext will set errno to ENOENT.

Maintainer's notes: Non-modification of errno is a documented part of
the interface contract for the GNU version of this function and likely
other versions. The issue being fixed here seems to be a regression
from commit 1b52863e244ecee5b5935b6d36bb9e6efe84c035, which enabled
setting of errno from __map_file.

release 1.1.21

fix call to __pthread_tsd_run_dtors with too many arguments

commit a6054e3c94aa0491d7366e4b05ae0d73f661bfe2 removed the argument,
making it a constraint violation to pass one. caught by cparser/firm;
other compilers seem to ignore it.

configure: accept ppc[64] as alias for powerpc[64] in gcc tuples

apparently some distros use this form, and it seems to be supported in
the gcc build system.

fix unintended linking dependency of pthread_key_create on __synccall

commit 84d061d5a31c9c773e29e1e2b1ffe8cb9557bc58 attempted to do this
already, but omitted from pthread_key_create.c the weak definition of
__pthread_key_delete_synccall, so that the definition provided by
pthread_key_delete.c was always pulled in.

based on patch by Markus Wichmann, but with a weak alias rather than
weak reference for consistency/policy about dependence on tooling
features.

halt getspnam[_r] search on error accessing TCB shadow

fallback to /etc/shadow should happen only when the entry is not found
in the TCB shadow. otherwise transient errors or permission errors can
cause inconsistent results.

don't set errno or return an error when getspnam[_r] finds no entry

this case is specified as success with a null result, rather than an
error, and errno is not to be set on success.

make sem_wait and sem_timedwait interruptible by signals

this reverts commit c0ed5a201b2bdb6d1896064bec0020c9973db0a1, which
was based on a mistaken reading of POSIX due to inconsistency between
the description (which requires return upon interruption by a signal)
and the errors list (which wrongly lists EINTR as "may fail").

since the previously-introduced behavior was a workaround for an old
kernel bug to ensure safety of correct programs that were not hardened
against the bug, an effort has been made to preserve it for programs
which do not use interrupting signal handlers. the stage for this was
set in commit a63c0104e496f7ba78b64be3cd299b41e8cd427f, which makes
the futex __timedwait backend suppress EINTR if it's seen when no
interrupting signal handlers have been installed.

based loosely on a patch submitted by Orivej Desh, but with
unnecessary additional changes removed.

don't fail pthread_sigmask/sigprocmask on invalid how when set is null

the resolution of Austin Group issue #1132 changes the requirement to
fail so that it only applies when the set argument (new mask) is
non-null. this change was made for consistency with the description,
which specified "if set is a null pointer, the value of the argument
how is not significant".

add __timedwait backend workaround for old kernels where futex EINTRs

prior to linux 2.6.22, futex wait could fail with EINTR even for
non-interrupting (SA_RESTART) signals. this was no problem provided
the caller simply restarted the wait, but sem_[timed]wait is required
by POSIX to return when interrupted by a signal. commit
a113434cd68ce30642c4995b1caadcd084be6f09 introduced this behavior, and
commit c0ed5a201b2bdb6d1896064bec0020c9973db0a1 reverted it based on a
mistaken belief that it was not required. this belief stems from a bug
in the specification: the description requires the function to return
when interrupted, but the errors section marks EINTR as a "may fail"
condition rather than a "shall fail" one.

since there does seem to be significant value in the change made in
commit c0ed5a201b2bdb6d1896064bec0020c9973db0a1, making it so that
programs that call sem_wait without checking for EINTR don't silently
make forward progress without obtaining the semaphore or treat it as a
fatal error and abort, add a behind-the-scenes mechanism in the
__timedwait backend to suppress EINTR in programs that have never
installed interrupting signal handlers, and have sigaction track and
report this state. this way the semaphore code is not cluttered by
workarounds and can be updated (to be done in next commit) to reflect
the high-level logic for conforming behavior.

these changes are based loosely on a patch by Markus Wichmann, with
the main changes being atomic update to flag object and moving the
workaround from sem_timedwait to the __timedwait futex backend.

on failed aio submission, set aiocb error and return value

it's not clear whether this is required, but it seems arguable that it
should happen. for example aio_suspend is supposed to return
immediately if any of the operations has "completed", which includes
ending with an error status asynchonously and might also be
interpreted to include doing so synchronously.

don't create aio queue/map structures for invalid file descriptors

the map structures in particular are permanent once created, and thus
a large number of aio function calls with invalid file descriptors
could exhaust memory, whereas, assuming normal resource limits, only a
very small number of entries ever need to be allocated. check validity
of the fd before allocating anything new, so that allocation of large
amounts of memory is only possible when resource limits have been
increased and a large number of files are actually open.

this change also improves error reporting for bad file descriptors to
happen at the time the aio submission call is made, as opposed to
asynchronously.

move aio queue allocation from io thread to submitting thread

since commit c9f415d7ea2dace5bf77f6518b6afc36bb7a5732, it has been
possible that the allocator is application-provided code, which cannot
necessarily run safely on io thread stacks, and which should not be
able to see the existence of io threads, since they are an
implementation detail.

instead of having the io thread request and possibly allocate its
queue (and the map structures leading to it), make the submitting
thread responsible for this, and pass the queue pointer into the io
thread via its args structure. this eliminates the only early error
case in io threads, making it no longer necessary to pass an error
status back to the submitting thread via the args structure.

fix and future-proof against stack overflow in aio io threads

aio threads not using SIGEV_THREAD notification are created with small
stacks and no guard page, which is possible since they only run the
code for the requested io operation, not any application code. the
motivation is not creating a lot of VMAs. however, the io thread needs
to be able to receive a cancellation signal in case aio_cancel
(implemented via pthread_cancel) is called. this requires sufficient
stack space for a signal frame, which PTHREAD_STACK_MIN does not
necessarily include.

in principle MINSIGSTKSZ from signal.h should give us sufficient space
for a signal frame, but the value is incorrect on some existing archs
due to kernel addition of new vector register support without
consideration for impact on ABI. some powerpc models exceed
MINSIGSTKSZ by about 0.5k, and x86[_64] with AVX-512 can exceed it by
up to about 1.5k. so use MINSIGSTKSZ+2048 to allow for the discrepancy
plus some working space.

unfortunately, it's possible that signal frame sizes could continue to
grow, and some archs (aarch64) explicitly specify that they may.
passing of a runtime value for MINSIGSTKSZ via AT_MINSIGSTKSZ in the
aux vector was added to aarch64 linux, and presumably other archs will
use this mechanism to report if they further increase the signal frame
size. when AT_MINSIGSTKSZ is present, assume it's correct, so that we
only need a small amount of working space in addition to it; in this
case just add 512.

add namespace-safe version of getauxval for internal use

add NT_VMCOREDD to elf.h from linux v4.18

used for device driver dump in /proc/vmcore
new in linux commit 2724273e8fd00b512596a77ee063f49b25f36507

add AT_MINSIGSTKSZ to elf.h from linux v4.18

new in linux commit 94b07c1f8c39c6d839df35fa28ffd1785d385897

currently only supported on aarch64

add io_pgetevents and rseq syscall numbers from linux v4.18

io_pgetevents is new in linux commit
7a074e96dee62586c935c80cecd931431bfdd0be

rseq is new in linux commit
d7822b1e24f2df5df98c76f0e94a5416349ff759

add TRAP_UNK si_code to signal.h from linux v4.18

used for undiagnosed trap exceptions where linux previously set si_code
to 0. new in linux commit db78e6a0a6f9f7d7277965600eeb1a5b3a6f55a8

add SIGSYS support to sys/signalfd.h from linux v4.18

new in linux commit 76b7f670730e87974f71df9f6129811e2769666e

in struct signalfd_siginfo the pad member is changed to __pad to keep
the namespace clean, it's not part of the public api.

add AF_XDP to sys/socket.h from linux v4.18

new address family and related macros were added in linux commit
68e8b849b221b37a78a110a0307717d45e3593a0

update netinet/udp.h for linux v4.18

add UDP_NO_CHECK6_* to restrict zero UDP6 checksums, new in linux commit
1c19448c9ba6545b80ded18488a64a7f3d8e6998 (pre-v4.18 change, was missed)
add UDP_SEGMENT to support generic segmentation offload for udp datagrams,
bec1f6f697362c5bc635dacd7ac8499d0a10a4e7 (new in v4.18)

update netinet/tcp.h for linux v4.18

add packet delivery info to tcp_info,
new in linux commit feb5f2ec646483fb66f9ad7218b1aad2a93a2a5c
add TCP_ZEROCOPY_RECEIVE socket option for zerocopy receive,
new in linux commit 05255b823a6173525587f29c4e8f1ca33fd7677d
add TCP_INQ socket option and TCP_CM_INQ cmsg to get in-queue bytes in cmsg
upon read, new in linux commit b75eba76d3d72e2374fac999926dafef2997edd2
add TCP_REPAIR_* to fix repair socket window probe patch,
new in linux commit 31048d7aedf31bf0f69c54a662944632f29d82f2

fix wordexp not to read past end of string ending with lone backslash

fix memccpy to not access buffer past given size

memccpy would return a pointer over the given size when c is not
found in the source buffer and n reaches 0.

fix regression in access to optopt object

commit b9410061e2ad6fe91bb3910c3adc7d4a315b7ce9 inadvertently omitted
optopt from the "dynamic list", causing it to be split into separate
objects that don't share their value if the main program contains a
copy relocation for it (for non-PIE executables that access it, and
some PIE ones, depending on arch and toolchain versions/options).

optimize two-way strstr and memmem bad character shift

first, the condition (mem && k < p) is redundant, because mem being
nonzero implies the needle is periodic with period exactly p, in which
case any byte that appears in the needle must appear in the last p
bytes of the needle, bounding the shift (k) by p.

second, the whole point of replacing the shift k by mem (=l-p) is to
prevent shifting by less than mem when discarding the memory on shift,
in which case linear time could not be guaranteed. but as written, the
check also replaced shifts greater than mem by mem, reducing the
benefit of the shift. there is no possible benefit to this reduction of
the shift; since mem is being cleared, the full shift is valid and
more optimal. so only replace the shift by mem when it would be less
than mem.

fix regression in setlocale for LC_ALL with per-category setting

commit d88e5dfa8b989dafff4b748bfb3cba3512c8482e inadvertently changed
the argument pased to __get_locale from part (the current ;-delimited
component) to name (the full string).

fix failure to flush stderr when fflush(0) is called

commit ddc947eda311331959c73dbc4491afcfe2326346 fixed the
corresponding bug for exit which was introduced when commit
0b80a7b0404b6e49b0b724e3e3fe0ed5af3b08ef added support for
caller-provided buffers, making it possible for stderr to be a
buffered stream.

fix deadlock and buffered data loss race in fclose

fflush(NULL) and __stdio_exit lock individual FILEs while holding the
open file list lock to walk the list. since fclose first locked the
FILE to be closed, then the ofl lock, it could deadlock with these
functions.

also, because fclose removed the FILE to be closed from the open file
list before flushing and closing it, a concurrent fclose or exit could
complete successfully before fclose flushed the FILE it was closing,
resulting in data loss.

reorder the body of fclose to first flush and close the file, then
remove it from the open file list only after unlocking it. this
creates a window where consumers of the open file list can see dead
FILE objects, but in the absence of undefined behavior on the part of
the application, such objects will be in an inactive-buffer state and
processing them will have no side effects.

__unlist_locked_file is also moved so that it's performed only for
non-permanent files. this change is not necessary, but preserves
consistency (and thereby provides safety/hardening) in the case where
an application uses one of the standard streams after closing it while
holding an explicit lock on it. such usage is of course undefined
behavior.

__libc_start_main: slightly simplify stage2 pointer setup

Use "+r" in the asm instead of implementing a non-transparent copy by
applying "0" constraint to the source value. Introduce a typedef for
the function type to avoid spelling it out twice.

remove commented-out debug printf from strstr

this was leftover from before the initial commit.

fix spuriously slow check in twoway strstr/memmem cores

mem0 && mem && ... is redundant since mem can only be nonzero when
mem0 is nonzero.

don't omit setting errno in internal __map_file function

a caller needs the reason for open (or fstat, albeit unlikely) failure
if it's going to make decisions about continuing a path search or
similar.

make the default locale (& a variant) failure-free cases for newlocale

commit aeeac9ca5490d7d90fe061ab72da446c01ddf746 introduced fail-safe
invariants that creating a locale_t object for the C locale or C.UTF-8
locale will always succeed. extend the guarantee to also cover the
following:

- newlocale(LC_ALL_MASK, "", 0)
- newlocale(LC_ALL_MASK-LC_CTYPE_MASK, "C", 0)

provided that the LANG/LC_* environment variables have not been
changed by the program. these usages are idiomatic for getting the
default locale, and for getting a locale that behaves as the C locale
except for honoring the default locale's character encoding.

simplify newlocale and allow failure for explicit locale names

unify the code paths for allocated and non-allocated locale objects,
always using a tmp object. this is necessary to avoid clobbering the
base locale object too soon if we allow for the possibility that
looking up an explicitly requested locale name may fail, and makes the
code simpler and cleaner anyway.

eliminate the complex and fragile logic for checking whether one of
the non-allocated locale objects can be used for the result, and
instead just memcmp against each of them.

remove volatile qualification from category pointers in __locale_struct

commit 63c188ec42e76ff768e81f6b65b11c68fc43351e missed making this
change when switching from atomics to locking for modification of the
global locale, leaving access to locale structures unnecessarily
burdened with the restrictions of volatile.

the volatile qualification was originally added in commit
56fbaa3bbe73f12af2bfbbcf2adb196e6f9fe264.

adapt setlocale to support possibility of failure

introduce a new LOC_MAP_FAILED sentinel for errors, since null
pointers for a category's locale map indicate the C locale. at this
time, __get_locale does not fail, so there should be no functional
change by this commit.

adjust types in FILE struct to make line buffering check less expensive

the choice of signed char for lbf was a theoretically space-saving
hack that was not helping, and was unwantedly expensive. while
comparing bytes against a byte-sized member sounds easy, the trick
here was that the byte to be compared was unsigned while the lbf
member was signed, making it possible to set lbf negative to disable
line buffering. however, this imposed a requirement to promote both
operands, zero-extending one and sign-extending the other, in order to
compare them.

to fix this, repurpose the waiters count slot (unused since commit
c21f750727515602a9e84f2a190ee8a0a2aeb2a1). while we're at it, switch
mode (orientation) from signed char to int as well. this makes no
semantic difference (its only possible values are -1, 0, and 1) but it
might help on archs where byte access is awkward.

optimize internal putc_unlocked macro used in putc

to check whether flush due to line buffering is needed, the int-type
character argument must be truncated to unsigned char for comparison.
if the original value is subsequently passed to __overflow, it must be
preserved, adding to register pressure. since it doesn't matter,
truncate all uses so the original value is no longer live.

fix wrong result for putc variants due to operator precedence

the internal putc_unlocked macro was wrongly returning a meaningless
boolean result rather than the written character or EOF.

bug was found by reading (very surprising) asm.

further optimize getc/putc when locking is needed

check whether the lock is free before loading the calling thread's
tid. if so, just use a dummy tid value that cannot compare equal to
any actual thread id (because it's one bit wider). this also avoids
the need to save the tid and pass it to locking_getc or locking_putc,
reducing register pressure.

this change might slightly hurt the case where the caller already
holds the lock, but it does not affect the single-threaded case, and
may significantly improve the multi-threaded case, especially on archs
where loading the thread pointer is disproportionately expensive like
early mips and arm ISA levels. but even on i386 it helps, at least on
some machines; I measured roughly a 10-15% improvement.

use prototype for function pointer in static link libc init barrier

this is not needed for correctness, but doesn't hurt, and in some
cases the compiler may pessimize the call assuming the callee might be
variadic when it lacks a prototype.

fix error in constraints for static link libc init barrier

commit 4390383b32250a941ec616e8bff6f568a801b1c0 inadvertently used "r"
instead of "0" for the input constraint, which only happened to work
for the configuration I tested it on because it usually makes sense
for the compiler to choose the same input and output register.

fix build regression due to missing file for putc changes

commit d664061adb4d7f6647ab2059bc351daa394bf5da inadvertently omitted
the new file putc.h.

bypass indirection through pointer objects to access stdin/out/err

by ABI, the public stdin/out/err macros use extern pointer objects,
and this is necessary to avoid copy relocations that would be
expensive and make the size of the FILE structure part of the ABI.
however, internally it makes sense to access the underlying FILE
objects directly. this avoids both an indirection through the GOT to
find the address of the stdin/out/err pointer objects (which can't be
computed PC-relative because they may have been moved to the main
program by copy relocations) and an indirection through the resulting
pointer object.

in most places this is just a minor optimization, but in the case of
getchar and putchar (and the unlocked versions thereof), ipa constant
propagation makes all accesses to members of stdin/out PC-relative or
GOT-relative, possibly reducing register pressure as well.

optimize hot paths of putc with manual shrink-wrapping

this is the analog of commit dd8f02b7dce53d6b1c4282439f1636a2d63bee01,
but for putc.

optimize hot paths of getc with manual shrink-wrapping

with these changes, in a program that has not created any threads
besides the main thread and that has not called f[try]lockfile, getc
performs indistinguishably from getc_unlocked. this was measured on
several i386 and x86_64 models, and should hold on other archs too
simply by the properties of the code generation.

the case where the caller already holds the lock (via flockfile) is
improved significantly as well (40-60% reduction in time on machines
tested) and the case where locking is needed is improved somewhat
(roughly 10%).

the key technique used here is forcing the non-hot path out-of-line
and enabling it to be a tail call. a static noinline function
(conditional on __GNUC__) is used rather than the extern hiddens used
elsewhere for this purpose, so that the compiler can choose
non-default calling conventions, making it possible to tail-call to a
callee that takes more arguments than the caller on archs where
arguments are passed on the stack or must have space reserved on the
stack for spilling the. the tid could just be reloaded via the thread
pointer in locking_getc, but that would be ridiculously expensive on
some archs where thread pointer load requires a trap or syscall.

document and make explicit desired noinline property for __init_libc

on multiple occasions I've started to flatten/inline the code in
__init_libc, only to rediscover the reason it was not inlined: GCC
fails to deallocate its stack (and now, with the changes in commit
4390383b32250a941ec616e8bff6f568a801b1c0, fails to produce a tail call
to the stage 2 function; see PR #87639) before calling main if it was
inlined.

document this with a comment and use an explicit noinline attribute if
__GNUC__ is defined so that even with CFLAGS that heavily favor
inlining it won't get inlined.

impose barrier between thread pointer setup and use for static linking

this is the analog of commit 1c84c99913bf1cd47b866ed31e665848a0da84a2
for static linking. unlike with dynamic linking, we don't have
symbolic lookup to use as a barrier. use a dummy (target-agnostic)
degenerate inline asm fragment instead. this technique has precedent
in commit 05ac345f895098657cf44d419b5d572161ebaf43 where it's used for
explicit_bzero. if it proves problematic in any way, loading the
address of the stage 2 function from a pointer object whose address
leaks to kernelspace during thread pointer init could be used as an
even stronger barrier.

make thread-pointer-loading asm non-volatile

this will allow the compiler to cache and reuse the result, meaning we
no longer have to take care not to load it more than once for the sake
of archs where the load may be expensive.

depends on commit 1c84c99913bf1cd47b866ed31e665848a0da84a2 for
correctness, since otherwise the compiler could hoist loads during
stage 3 of dynamic linking before the initial thread-pointer setup.

remove ancient clang workaround from powerpc pthread_arch.h asm

versions of clang all the way back to 3.1 lack the bug this was
purportedly working around.

restore attribute((const)) to pthread_self and errno location decls

revert commit a603a75a72bb469c6be4963ed1b55fabe675fe15.

as a result of commit 1c84c99913bf1cd47b866ed31e665848a0da84a2 this is
now safe, assuming an interpretation of the somewhat-underspecified
attribute((const)) consistent with real-world usage.

add new stage 2b to dynamic linker bootstrap for thread pointer

commit a603a75a72bb469c6be4963ed1b55fabe675fe15 removed attribute
const from __errno_location and pthread_self, and the same reasoning
forced arch definitions of __pthread_self to use volatile asm,
significantly impacting code generation and imposing manual caching of
pointers where the impact might be noticable.

reorder the thread pointer setup and place it across a strong barrier
(symbolic function lookup) so that there is no assumed ordering
between the initialization and the accesses to the thread pointer in
stage 3.

move stdio locking MAYBE_WAITERS definition to stdio_impl.h

don't repeat definition in two places.

fix misleading placement of statement on same line as for loop in ldso

the placement triggered -Wmisleading-indentation warnings if enabled,
and was gratuitously confusing to anyone reading the code.

x86_64: add single instruction fma

fma is only available on recent x86_64 cpus and it is much faster than
a software fma, so this should be done with a runtime check, however
that requires more changes, this patch just adds the code so it can be
tested when musl is compiled with -mfma or -mfma4.

arm: add single instruction fma

vfma is available in the vfpv4 fpu and above, the ACLE standard feature
test for double precision hardware fma support is
  __ARM_FEATURE_FMA && __ARM_FP&8
we need further checks to work around clang bugs (fixed in clang >=7.0)
  && !__SOFTFP__
because __ARM_FP is defined even with -mfloat-abi=soft
  && !BROKEN_VFP_ASM
to disable the single precision code when inline asm handling is broken.

For runtime selection the HWCAP_ARM_VFPv4 hwcap flag can be used, but
that requires further work.

powerpc: add single instruction fabs, fabsf, fma, fmaf, sqrt, sqrtf

These are only available on hard float target and sqrt is not available
in the base ISA, so further check is used.

s390x: add single instruction fma and fmaf

These are available in the s390x baseline isa -march=z900.

allow escaped path-separator slashes in glob

previously (before and after rewrite), spurious escaping of path
separators as \/ was not treated the same as /, but rather got split
as an unpaired \ at the end of the fnmatch pattern and an unescaped /,
resulting in a mismatch/error.

for the case of \/ as part of the maximal literal prefix, remove the
explicit rejection of it and move the handling of / below escape
processing.

for the case of \/ after a proper glob pattern, it's hard to parse the
pattern, so don't. instead cheat and count repetitions of \ prior to
the already-found / character. if there are an odd number, the last is
escaping the /, so back up the split position by one. now the
char clobbered by null termination is variable, so save it and restore
as needed.

rewrite core of the glob implementation for correctness & optimization

this code has been long overdue for a rewrite, but the immediate cause
that necessitated it was total failure to see past unreadable path
components. for example, A/B/* would fail to match anything, even
though it should succeed, when both A and A/B are searchable but only
A/B is readable. this problem both was caught in conformance testing,
and impacted users.

the old glob implementation insisted on searching the listing of each
path component for a match, even if the next component was a literal.
it also used considerable stack space, up to length of the pattern,
per recursion level, and relied on an artificial bound of the pattern
length by PATH_MAX, which was incorrect because a pattern can be much
longer than PATH_MAX while having matches shorter (for example, with
necessarily long bracket expressions, or with redundancy).

in the new implementation, each level of recursion starts by consuming
the maximal literal (possibly escaped-literal) path prefix remaining
in the pattern, and only opening a directory to read when there is a
proper glob pattern in the next path component. it then recurses into
each matching entry. the top-level glob function provided automatic
storage (up to PATH_MAX) for construction of candidate/result strings,
and allocates a duplicate of the pattern that can be modified in-place
with temporary null-termination to pass to fnmatch. this allocation is
not a big deal since glob already has to perform allocation, and has
to link free to clean up if it experiences an allocation failure or
other error after some results have already been allocated.

care is taken to use the d_type field from iterated dirents when
possible; stat is called only when there are literal path components
past the last proper-glob component, or when needed to disambiguate
symlinks for the purpose of GLOB_MARK.

one peculiarity with the new implementation is the manner in which the
error handling callback will be called. if attempting to match */B/C/D
where a directory A exists that is inaccessible, the error reported
will be a stat error for A/B/C/D rather than (previous and wrong
implementation) an opendir error for A, or (likely on other
implementations) a stat error for A/B. such behavior does not seem to
be non-conforming, but if it turns out to be undesirable for any
reason, backtracking could be done on error to report the first
component producing it.

also, redundant slashes are no longer normalized, but preserved as
they appear in the pattern; this is probably more correct, and falls
out naturally from the algorithm used. since trailing slashes (which
force all matches to be directories) are preserved as well, the
behavior of GLOB_MARK has been adjusted not to append an additional
slash to results that already end in slash.

fix dlsym of thread-local symbols on archs with DTP_OFFSET!=0

commit 6ba5517a460c6c438f64d69464fdfc3269a4c91a modified
__tls_get_addr to offset the address by +DTP_OFFSET (0x8000 on
powerpc, mips, etc.) and adjusted the result of DTPREL relocations by
-DTP_OFFSET to compensate, but missed changing the argument setup for
calls to __tls_get_addr from dlsym.

combine arch ABI's DTP_OFFSET into DTV pointers

as explained in commit 6ba5517a460c6c438f64d69464fdfc3269a4c91a, some
archs use an offset (typicaly -0x8000) with their DTPOFF relocations,
which __tls_get_addr needs to invert. on affected archs, which lack
direct support for large immediates, this can cost multiple extra
instructions in the hot path. instead, incorporate the DTP_OFFSET into
the DTV entries. this means they are no longer valid pointers, so
store them as an array of uintptr_t rather than void *; this also
makes it easier to access slot 0 as a valid slot count.

commit e75b16cf93ebbc1ce758d3ea6b2923e8b2457c68 left behind cruft in
two places, __reset_tls and __tls_get_new, from back when it was
possible to have uninitialized gap slots indicated by a null pointer
in the DTV. since the concept of null pointer is no longer meaningful
with an offset applied, remove this cruft.

presently there are no archs with both TLSDESC and nonzero DTP_OFFSET,
but the dynamic TLSDESC relocation code is also updated to apply an
inverted offset to its offset field, so that the offset DTV would not
impose a runtime cost in TLSDESC resolver functions.

fix redundant computations of strlen in glob append function

len was already passed as an argument, so don't use strcat, and use
memcpy instead of strcpy.

fix invalid substitute of [1] for flexible array member in glob

fix fesetround error checking

Rounding modes are not bit flags, but arbitrary non-negative integers.

fix build regression on armhf in tlsdesc asm

when invoking the assembler, arm gcc does not always pass the right
flags to enable use of vfp instruction mnemonics. for C code it
produces, it emits the .fpu directive, but this does not help when
building asm source files, which tlsdesc needs to be. to fix, use an
explicit directive here.

commit 0beb9dfbecad38af9759b1e83eeb007e28b70abb introduced this
regression. it has not appeared in any release.

allow freeaddrinfo of arbitrary sublists of addrinfo list

the specification for freeaddrinfo allows it to be used to free
"arbitrary sublists" of the list returned by getaddrinfo. it's not
clearly stated how such sublists come into existence, but the
interpretation seems to be that the application can edit the ai_next
pointers to cut off a portion of the list and then free it.

actual freeing of individual list slots is contrary to the design of
our getaddrinfo implementation, which has no failure paths after
making a single allocation, so that light callers can avoid linking
realloc/free. freeing individual slots is also incompatible with
sharing the string for ai_canonname, which the current implementation
does despite no requirement that it be present except on the first
result. so, rather than actually freeing individual slots, provide a
way to find the start of the allocated array, and reference-count it,
freeing the memory all at once after the last slot has been freed.

since the language in the spec is "arbitrary sublists", no provision
for handling other constructs like multiple lists glued together,
circular links, etc. is made. presumably passing such a construct to
freeaddrinfo produces undefined behavior.

inline cp15 thread pointer load in arm dynamic TLSDESC asm when possible

the indirect function call is a significant portion of the code path
for the dynamic case, and most users are probably building for ISA
levels where it can be omitted.

we could drop at least one register save/restore (lr) with this
change, and possibly another (ip) with some clever shuffling, but it's
not clear whether there's a way to do it that's not more expensive, or
whether avoiding the save/restore would have any practical effect, so
in the interest of avoiding complexity it's omitted for now.

add TLSDESC support for 32-bit arm

unlike other asm where the baseline ISA is used, these functions are
hot paths and use ISA-level specializations.

call-clobbered vfp registers are saved before calling __tls_get_new,
since there is no guarantee it won't use them. while setjmp/longjmp
have to use hwcap to decide whether to the fpu is in use, since
application code could be using vfp registers even if libc was
compiled as pure softfloat, __tls_get_new is part of libc and can be
assumed not to have access to vfp registers if tlsdesc.S does not.
thus it suffices just to check the predefined preprocessor macros. the
check for __ARM_PCS_VFP is redundant; !__SOFTFP__ must always be true
if the target ISA level includes fpu instructions/registers.

fix aliasing-based undefined behavior in string functions

use the GNU C may_alias attribute if available, and fallback to naive
byte-by-byte loops if __GNUC__ is not defined.

this patch has been written to minimize changes so that history
remains reviewable; it does not attempt to bring the affected code
into a more consistent or elegant form.

optimize nop case of wmemmove

fix undefined pointer comparison in wmemmove

fix undefined pointer comparison in memmove

the comparison must take place in the address space model as an
integer type, since comparing pointers that are not pointing into the
same array is undefined.

the subsequent d<s comparison however is valid, because it's only
reached in the case where the source and dest overlap, in which case
they are necessarily pointing to parts of the same array.

to make the comparison, use an unsigned range check for dist(s,d)>=n,
algebraically !(-n<s-d<n). subtracting n yields !(-2*n<s-d-n<0), which
mapped into unsigned modular arithmetic is !(-2*n<s-d-n) or rather
-2*n>=s-d-n.

new tsearch implementation

Rewrote the AVL tree implementation:

- It is now non-recursive with fixed stack usage (large enough for
worst case tree height). twalk and tdestroy are still recursive as
that's smaller/simpler.

- Moved unrelated interfaces into separate translation units.

- The node structure is changed to use indexed children instead of
left/right pointers, this simplifies the balancing logic.

- Using void * pointers instead of struct node * in various places,
because this better fits the api (node address is passed in a void**
argument, so it is tempting to incorrectly cast it to struct node **).

- As a further performance improvement the rebalancing now stops
when it is not needed (subtree height is unchanged). Otherwise
the behaviour should be the same as before (checked over generated
random inputs that the resulting tree shape is equivalent).

- Removed the old copyright notice (including prng related one: it
should be licensed under the same terms as the rest of the project).

.text size of pic tsearch + tfind + tdelete + twalk:

   x86_64 i386 aarch64  arm mips powerpc ppc64le  sh4 m68k s390x
old   941  899    1220 1068 1852    1400    1600 1008 1008  1488
new   857  881    1040  976 1564    1192    1360  736  820  1408

add arm and sh bits/ptrace.h

These should have been added in commit
df6d9450ea19fd71e52cf5cdb4c85beb73066394
that added target specific PTRACE_ macros, but somehow got missed.

fix getaddrinfo regression with AI_ADDRCONFIG on some configurations

despite not being documented to do so in the standard or Linux
documentation, attempts to udp connect to 127.0.0.1 or ::1 generate
EADDRNOTAVAIL when the loopback device is not configured and there is
no default route for IPv6. this caused getaddrinfo with AI_ADDRCONFIG
to fail with EAI_SYSTEM and EADDRNOTAVAIL on some no-IPv6
configurations, rather than the intended behavior of detecting IPv6 as
unsuppported and producing IPv4-only results.

previously, only EAFNOSUPPORT was treated as unavailability of the
address family being probed. instead, treat all errors related to
inability to get an address or route as conclusive that the family
being probed is unsupported, and only fail with EAI_SYSTEM on other
errors.

further improvements may be desirable, such as reporting EAI_AGAIN
instead of EAI_SYSTEM for errors which are expected to be transient,
but this patch should suffice to fix the serious regression.

support clang internal assembler when building for arm as thumb2 code

the clang internal assembler does not accept assembler options passed
via the usual -Wa mechanism, but it does accept -mimplicit-it directly
as an option to the compiler driver.

support setting of default thread stack size via PT_GNU_STACK header

this facilitates building software that assumes a large default stack
size without any patching to call pthread_setattr_default_np or
pthread_attr_setstacksize at each thread creation site, using just
LDFLAGS.

normally the PT_GNU_STACK header is used only to reflect whether
executable stack is desired, but with GNU ld at least, passing
-Wl,-z,stack-size=N will set a size on the program header. with this
patch, that size will be incorporated into the default stack size
(subject to increase-only rule and DEFAULT_STACK_MAX limit).

both static and dynamic linking honor the program header. for dynamic
linking, all libraries loaded at program start, including preloaded
ones, are considered. dlopened libraries are not considered, for
several reasons. extra logic would be needed to defer processing until
the load of the new library is commited, synchronization woud be
needed since other threads may be running concurrently, and the
effectiveness woud be limited since the larger size would not apply to
threads that already existed at the time of dlopen. programs that will
dlopen code expecting a large stack need to declare the requirement
themselves, or pthread_setattr_default_np can be used.

increase default thread stack/guard size

stack size default is increased from 80k to 128k. this coincides with
Linux's hard-coded default stack for the main thread (128k is
initially committed; growth beyond that up to ulimit is contingent on
additional allocation succeeding) and GNU ld's default PT_GNU_STACK
size for FDPIC, at least on sh.

guard size default is increased from 4k to 8k to reduce the risk of
guard page jumping on overflow, since use of just over 4k of stack is
common (PATH_MAX buffers, etc.).