replace heap sort with smoothsort implementation by Valentin Ochs

Smoothsort is an adaptive variant of heapsort. This version was
written by Valentin Ochs (apo) specifically for inclusion in musl. I
worked with him to get it working in O(1) memory usage even with giant
array element widths, and to optimize it heavily for size and speed.
It's still roughly 4 times as large as the old heap sort
implementation, but roughly 20 times faster given an almost-sorted
array of 1M elements (20 being the base-2 log of 1M), i.e. it really
does reduce O(n log n) to O(n) in the mostly-sorted case. It's still
somewhat slower than glibc's Introsort for random input, but now
considerably faster than glibc when the input is already sorted, or
mostly sorted.

add word-sized ctz function to atomic.h

strictly speaking this and a few other ops should be factored into
asm.h or the file should just be renamed to asm.h, but whatever. clean
it up someday.

function signature fix: add const qualifier to mempcpy src arg

typo in prototype for mempcpy

prototype for mempcpy

fix bug in ipv6 parsing that prevented parsing a lone "::"

ipv6 parsing code (formerly dummied-out)

fix 2 eof-related bugs in scanf

1. failed match of literal chars from the format string would always
return matching failure rather than input failure at eof, leading to
infinite loops in some programs.

2. unread of eof would wrongly adjust the character counts reported by
%n, yielding an off-by-one error.

update release notes to new format, add more

fix initial stack alignment in new threads on x86_64

update release notes in prep for 0.7.9 release

omit errno update path for syscalls that cannot fail

fix bogus return values for inet_pton

move wait.h macros out of bits. they do not vary.

include signal.h to avoid thorny __sigcontext/sigcontext issues

this is explicitly allowed by POSIX

fix minor bugs due to incorrect threaded-predicate semantics

some functions that should have been testing whether pthread_self()
had been called and initialized the thread pointer were instead
testing whether pthread_create() had been called and actually made the
program "threaded". while it's unlikely any mismatch would occur in
real-world problems, this could have introduced subtle bugs. now, we
store the address of the main thread's thread descriptor in the libc
structure and use its presence as a flag that the thread register is
initialized. note that after fork, the calling thread (not necessarily
the original main thread) is the new main thread.

workaround bug in linux dup2

the linux documentation for dup2 says it can fail with EBUSY due to a
race condition with open and dup in the kernel. shield applications
(and the rest of libc) from this nonsense by looping until it succeeds

properly create new session/controlling terminal in forkpty

implement (nonstandard) forkpty

disallow blank strings as service or host name

fix bugs in ipv4 parsing

fix initgroups (uninitialized count passed to getgrouplist)

shadow password fixes: empty fields should read as -1 not 0

namespace fixes for sys/mman.h

fix missing include in posix_madvise.c (compile error)

support posix_madvise (previous a stub)

the check against MADV_DONTNEED to because linux MADV_DONTNEED
semantics conflict dangerously with the POSIX semantics

add syscall wrappers for posix_fadvise, posix_fallocate

block cancellation in wordexp, handle more errors

avoid malloc of potentially-large string in wordexp

move some more code out of pthread_create.c

this also de-uglifies the dummy function aliasing a bit.

fix uninitialized waiters field in semaphores

dns lookups: protect against cancellation and fix incorrect error codes

avoid fd leak if opendir is cancelled when calloc has failed

protect ftw and nftw against cancellation

protect syslog against cancellation

these functions are allowed to be cancellation points, but then we
would have to install cleanup handlers to avoid termination with locks
held.

recheck cancellation disabled flag after syscall returns EINTR

we already checked before making the syscall, but it's possible that a
signal handler interrupted the blocking syscall and disabled
cancellation, and that this is the cause of EINTR. in this case, the
old behavior was testably wrong.

remove bogus extra logic for close cancellability

like all other syscalls, close should return to the caller if and only
if it successfully performed its action. it is necessary that the
application be able to determine whether the close succeeded.

fix typo in x86_64 cancellable syscall asm

minimal realpath implementation using /proc

clean and simple, but fails when the caller does not have permissions
to open the file for reading or when /proc is not available. i may
replace this with a full implementation later, possibly leaving this
version as an optimization to use when it works.

pthread_exit is not supposed to affect cancellability

if the exit was caused by cancellation, __cancel has already set these
flags anyway.

fix pthread_exit from cancellation handler

cancellation frames were not correctly popped, so this usage would not
only loop, but also reuse discarded and invalid parts of the stack.

clean up handling of thread/nothread mode, locking

debloat: use __syscall instead of syscall where possible

don't waste time (and significant code size due to function call
overhead!) setting errno when the result of a syscall does not matter
or when it can't fail.

fix bugs in cancellable syscall asm

x86_64 was just plain wrong in the cancel-flag-already-set path, and
crashing.

the more subtle error was not clearing the saved stack pointer before
returning to c code. this could result in the signal handler
misidentifying c code as the pre-syscall part of the asm, and acting
on cancellation at the wrong time, and thus resource leak race
conditions.

also, now __cancel (in the c code) is responsible for clearing the
saved sp in the already-cancelled branch. this means we have to use
call rather than jmp to ensure the stack pointer in the c will never
match what the asm saved.

optimize cancellation enable/disable code

the goal is to be able to use pthread_setcancelstate internally in
the implementation, whenever a function might want to use functions
which are cancellation points but avoid becoming a cancellation point
itself. i could have just used a separate internal function for
temporarily inhibiting cancellation, but the solution in this commit
is better because (1) it's one less implementation-specific detail in
functions that need to use it, and (2) application code can also get
the same benefit.

previously, pthread_setcancelstate dependend on pthread_self, which
would pull in unwanted thread setup overhead for non-threaded
programs. now, it temporarily stores the state in the global libc
struct if threads have not been initialized, and later moves it if
needed. this way we can instead use __pthread_self, which has no
dependencies and assumes that the thread register is already valid.

don't use pthread_once when there is no danger in race

fix some minor issues in cancellation handling patch

signals were wrongly left masked, and cancellability state was not
switched to disabled, during the execution of cleanup handlers.

overhaul pthread cancellation

this patch improves the correctness, simplicity, and size of
cancellation-related code. modulo any small errors, it should now be
completely conformant, safe, and resource-leak free.

the notion of entering and exiting cancellation-point context has been
completely eliminated and replaced with alternative syscall assembly
code for cancellable syscalls. the assembly is responsible for setting
up execution context information (stack pointer and address of the
syscall instruction) which the cancellation signal handler can use to
determine whether the interrupted code was in a cancellable state.

these changes eliminate race conditions in the previous generation of
cancellation handling code (whereby a cancellation request received
just prior to the syscall would not be processed, leaving the syscall
to block, potentially indefinitely), and remedy an issue where
non-cancellable syscalls made from signal handlers became cancellable
if the signal handler interrupted a cancellation point.

x86_64 asm is untested and may need a second try to get it right.

remove stupid debug code in wordexp

implement wordexp. first try, may be buggy. intended to be safe.

avoid setting errno when checking for tty

setting errno here is completely valid, but some programs, notably
busybox printf, assume that errno will not be set during output and
treat this as an error condition. in any case, skipping it slightly
reduces code size and saves time.

document some changes in the upcoming release

fix O_SYNC definition, cleanup fcntl.h

fix FAPPEND typo on x86_64 (previously only fixed on i386)

fcntl.h: move macros that do not vary between archs out of bits

fix broken fcntl locks on x86_64

make tmpfile slightly more efficient (use unlink syscall instead of remove)

fix typo in legacy FAPPEND definition

add useless type fd_mask. it's in the reserved namespace.

change sem_trywait algorithm so it never has to call __wake

cheap trick to further optimize locking normal mutexes

use a separate signal from SIGCANCEL for SIGEV_THREAD timers

otherwise we cannot support an application's desire to use
asynchronous cancellation within the callback function. this change
also slightly debloats pthread_create.c.

simplify cancellation point handling

we take advantage of the fact that unless self->cancelpt is 1,
cancellation cannot happen. so just increment it by 2 to temporarily
block cancellation. this drops pthread_create.o well under 1k.

simplify syslog, add vsyslog interface (nonstandard)

with datagram sockets, depending on fprintf not to flush the output
early was very fragile; the new version simply uses a small fixed-size
buffer. it could be updated to dynamic-allocate large buffers if
needed, but i can't envision any admin being happy about finding
64kb-long lines in their syslog...

remove useless SIGPIPE protection from syslog

per the standard, SIGPIPE is not generated for SOCK_DGRAM.

fix syslog (corrected SIGPIPE blocking, and using dgram instead of stream)

it actually appears the hacks to block SIGPIPE are probably not
necessary, and potentially harmful. if i can confirm this, i'll remove
them.

numerous fixes to sysv ipc

some of these definitions were just plain wrong, others based on
outdated ancient "non-64" versions of the kernel interface.

as much as possible has now been moved out of bits/*

these changes break abi (the old abi for these functions was wrong),
but since they were not working anyway it can hardly matter.

add syslog.h cruft for syslogd to use...

add profile for getmntent_r

add syscall wrapper for flock

it should be noted that flock does not mix well with standard fcntl
locking, but nonetheless some applications will attempt to use flock
instead of fcntl if both exist. options to configure or small patches
may be needed. debian maintainers have plenty of experience with this
unfortunate situation...

fix bug whereby getopt_long allowed mismatch in last char of option name

fix typos on RLIM_NLIMITS, remove _GNU_SOURCE test for it

RLIM_* is in the reserved namespace for this header

fix and cleanup suseconds_t/timeval stuff (broken on 64-bit)

trash in the upper 32 bits was making the kernel sleep forever in
select on 64-bit systems.

implement getgrouplist (for initgroups), formerly dummied-out

fix prototypes/signature for setgroups, etc.

fix incorrect GNU sighandler_t typedef

implement memrchr (nonstandard) and optimize strrchr in terms of it

add ptsname_r (nonstandard) and split ptsname (standard) to separate file

this eliminates the ugly static buffer in programs that use ptsname_r.

speed up threaded fork

after fork, we have a new process and the pid is equal to the tid of
the new main thread. there is no need to make two separate syscalls to
obtain the same number.

more changes for upcoming 0.7.8

optimize ntohl etc. in terms of bswap functions

we can do this without violating the namespace now that they are
macros/inline functions rather than extern functions. the motivation
is that gcc was generating giant, slow, horrible code for the old
functions, and now generates a single byte-swapping instruction.

move bswap functions to static inline in byteswap.h

fix broken bswap_32

utmpx.h is no longer under standards, so expose ut_exit structure

add some traditional aliases to stat.h

fix printf("%.9g", 1.1) and similar not dropping trailing zeros

add missing rlimit macros

more types cleanup

the basic idea is that the only things in alltypes.h should be types
that either vary from system to system (in practice, not just in
theoretical la-la land - this is the implementation so we choose what
constraints we want to impose on ports) or which are needed by
multiple system headers.

cleanup types stuff in headers, fix missing u_int*_t in sys/types.h

fix errno handling in scandir:

1. saved errno was not being restored, illegally clearing errno to 0.
2. no need to backup and save errno around free; it will not touch
except perhaps when the program has already invoked UB...

fix fputwc return value

remove ugly warning-suppression hack from crypt - this invokes UB!

update README since we now DO have a mailing list

add some ugly legacy type names in sys/types.h (u_char etc.)

add legacy BSD-style timer*() macros in sys/time.h

add missing UTIME_* macros in sys/stat.h

add missing float.h macros

actually FLT_ROUNDS needs to expand to a static inline function that
obtains the current rounding mode and returns it, but that will be
added later with fenv.h stuff.

run pthread tsd destructors when a timer thread pretends to exit

greatly improve SIGEV_THREAD timers

calling pthread_exit from, or pthread_cancel on, the timer callback
thread will no longer destroy the timer.

prepare notes for 0.7.8 release