summaryrefslogtreecommitdiff
path: root/src
AgeCommit message (Collapse)AuthorLines
2011-04-27replace heap sort with smoothsort implementation by Valentin OchsRich Felker-32/+193
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.
2011-04-26function signature fix: add const qualifier to mempcpy src argRich Felker-1/+1
2011-04-25fix bug in ipv6 parsing that prevented parsing a lone "::"Rich Felker-4/+1
2011-04-25ipv6 parsing code (formerly dummied-out)Rich Felker-8/+62
2011-04-25fix 2 eof-related bugs in scanfRich Felker-3/+4
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.
2011-04-22fix initial stack alignment in new threads on x86_64Rich Felker-1/+1
2011-04-21omit errno update path for syscalls that cannot failRich Felker-7/+7
2011-04-21fix bogus return values for inet_ptonRich Felker-2/+2
2011-04-20fix minor bugs due to incorrect threaded-predicate semanticsRich Felker-6/+6
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.
2011-04-20workaround bug in linux dup2Rich Felker-1/+4
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
2011-04-20properly create new session/controlling terminal in forkptyRich Felker-1/+4
2011-04-20implement (nonstandard) forkptyRich Felker-0/+22
2011-04-20disallow blank strings as service or host nameRich Felker-0/+3
2011-04-20fix bugs in ipv4 parsingRich Felker-1/+2
2011-04-20fix initgroups (uninitialized count passed to getgrouplist)Rich Felker-1/+1
2011-04-20shadow password fixes: empty fields should read as -1 not 0Rich Felker-7/+13
2011-04-20namespace fixes for sys/mman.hRich Felker-0/+1
2011-04-20fix missing include in posix_madvise.c (compile error)Rich Felker-0/+1
2011-04-20support posix_madvise (previous a stub)Rich Felker-1/+3
the check against MADV_DONTNEED to because linux MADV_DONTNEED semantics conflict dangerously with the POSIX semantics
2011-04-20add syscall wrappers for posix_fadvise, posix_fallocateRich Felker-0/+16
2011-04-19block cancellation in wordexp, handle more errorsRich Felker-2/+17
2011-04-19avoid malloc of potentially-large string in wordexpRich Felker-10/+28
2011-04-19move some more code out of pthread_create.cRich Felker-7/+4
this also de-uglifies the dummy function aliasing a bit.
2011-04-19fix uninitialized waiters field in semaphoresRich Felker-0/+1
2011-04-18dns lookups: protect against cancellation and fix incorrect error codesRich Felker-4/+10
2011-04-18avoid fd leak if opendir is cancelled when calloc has failedRich Felker-1/+2
2011-04-18protect ftw and nftw against cancellationRich Felker-1/+6
2011-04-18protect syslog against cancellationRich Felker-5/+19
these functions are allowed to be cancellation points, but then we would have to install cleanup handlers to avoid termination with locks held.
2011-04-18recheck cancellation disabled flag after syscall returns EINTRRich Felker-1/+1
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.
2011-04-18remove bogus extra logic for close cancellabilityRich Felker-3/+1
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.
2011-04-17fix typo in x86_64 cancellable syscall asmRich Felker-1/+1
2011-04-17minimal realpath implementation using /procRich Felker-0/+43
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.
2011-04-17pthread_exit is not supposed to affect cancellabilityRich Felker-2/+0
if the exit was caused by cancellation, __cancel has already set these flags anyway.
2011-04-17fix pthread_exit from cancellation handlerRich Felker-5/+5
cancellation frames were not correctly popped, so this usage would not only loop, but also reuse discarded and invalid parts of the stack.
2011-04-17clean up handling of thread/nothread mode, lockingRich Felker-27/+16
2011-04-17debloat: use __syscall instead of syscall where possibleRich Felker-8/+8
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.
2011-04-17fix bugs in cancellable syscall asmRich Felker-11/+12
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.
2011-04-17optimize cancellation enable/disable codeRich Felker-4/+11
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.
2011-04-17don't use pthread_once when there is no danger in raceRich Felker-2/+5
2011-04-17fix some minor issues in cancellation handling patchRich Felker-11/+19
signals were wrongly left masked, and cancellability state was not switched to disabled, during the execution of cleanup handlers.
2011-04-17overhaul pthread cancellationRich Felker-218/+235
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.
2011-04-15remove stupid debug code in wordexpRich Felker-1/+0
2011-04-15implement wordexp. first try, may be buggy. intended to be safe.Rich Felker-0/+128
2011-04-15avoid setting errno when checking for ttyRich Felker-2/+2
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.
2011-04-14make tmpfile slightly more efficient (use unlink syscall instead of remove)Rich Felker-1/+1
2011-04-14change sem_trywait algorithm so it never has to call __wakeRich Felker-3/+2
2011-04-14cheap trick to further optimize locking normal mutexesRich Felker-2/+2
2011-04-14use a separate signal from SIGCANCEL for SIGEV_THREAD timersRich Felker-11/+29
otherwise we cannot support an application's desire to use asynchronous cancellation within the callback function. this change also slightly debloats pthread_create.c.
2011-04-13simplify cancellation point handlingRich Felker-16/+5
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.
2011-04-13simplify syslog, add vsyslog interface (nonstandard)Rich Felker-31/+36
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...