The LSB of g_signals was unused. The LSB of g1_start was used to indicate
which group is G2. This was used to always go to sleep in pthread_cond_wait
if a waiter is in G2. A comment earlier in the file says that this is not
correct to do:
"Waiters cannot determine whether they are currently in G2 or G1 -- but they
do not have to because all they are interested in is whether there are
available signals"
I either would have had to update the comment, or get rid of the check. I
chose to get rid of the check. In fact I don't quite know why it was there.
There will never be available signals for group G2, so we didn't need the
special case. Even if there were, this would just be a spurious wake. This
might have caught some cases where the count has wrapped around, but it
wouldn't reliably do that, (and even if it did, why would you want to force a
sleep in that case?) and we don't support that many concurrent waiters
anyway. Getting rid of it allows us to use one more bit, making us more
robust to wraparound.
Signed-off-by: Malte Skarupke <malteskarupke@fastmail.fm>
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
This function no longer waits for threads to leave g1, so rename it to
__condvar_switch_g1
Signed-off-by: Malte Skarupke <malteskarupke@fastmail.fm>
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
In my previous change I turned a nested loop into a simple loop. I'm doing
the resulting indentation changes in a separate commit to make the diff on
the previous commit easier to review.
Signed-off-by: Malte Skarupke <malteskarupke@fastmail.fm>
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
The loop was a little more complicated than necessary. There was only one
break statement out of the inner loop, and the outer loop was nearly empty.
So just remove the outer loop, moving its code to the one break statement in
the inner loop. This allows us to replace all gotos with break statements.
Signed-off-by: Malte Skarupke <malteskarupke@fastmail.fm>
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
This variable used to be needed to wait in group switching until all sleepers
have confirmed that they have woken. This is no longer needed. Nothing waits
on this variable so there is no need to track how many threads are currently
asleep in each group.
Signed-off-by: Malte Skarupke <malteskarupke@fastmail.fm>
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
pthread_cond_wait was checking whether it was in a closed group no less than
four times. Checking once is enough. Here are the four checks:
1. While spin-waiting. This was dead code: maxspin is set to 0 and has been
for years.
2. Before deciding to go to sleep, and before incrementing grefs: I kept this
3. After incrementing grefs. There is no reason to think that the group would
close while we do an atomic increment. Obviously it could close at any
point, but that doesn't mean we have to recheck after every step. This
check was equally good as check 2, except it has to do more work.
4. When we find ourselves in a group that has a signal. We only get here after
we check that we're not in a closed group. There is no need to check again.
The check would only have helped in cases where the compare_exchange in the
next line would also have failed. Relying on the compare_exchange is fine.
Removing the duplicate checks clarifies the code.
Signed-off-by: Malte Skarupke <malteskarupke@fastmail.fm>
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
Some comments were wrong after the most recent commit. This fixes that.
Also fixing indentation where it was using spaces instead of tabs.
Signed-off-by: Malte Skarupke <malteskarupke@fastmail.fm>
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
This fixes the lost wakeup (from a bug in signal stealing) with a change
in the usage of g_signals[] in the condition variable internal state.
It also completely eliminates the concept and handling of signal stealing,
as well as the need for signalers to block to wait for waiters to wake
up every time there is a G1/G2 switch. This greatly reduces the average
and maximum latency for pthread_cond_signal.
The g_signals[] field now contains a signal count that is relative to
the current g1_start value. Since it is a 32-bit field, and the LSB is
still reserved (though not currently used anymore), it has a 31-bit value
that corresponds to the low 31 bits of the sequence number in g1_start.
(since g1_start also has an LSB flag, this means bits 31:1 in g_signals
correspond to bits 31:1 in g1_start, plus the current signal count)
By making the signal count relative to g1_start, there is no longer
any ambiguity or A/B/A issue, and thus any checks before blocking,
including the futex call itself, are guaranteed not to block if the G1/G2
switch occurs, even if the signal count remains the same. This allows
initially safely blocking in G2 until the switch to G1 occurs, and
then transitioning from G1 to a new G1 or G2, and always being able to
distinguish the state change. This removes the race condition and A/B/A
problems that otherwise ocurred if a late (pre-empted) waiter were to
resume just as the futex call attempted to block on g_signal since
otherwise there was no last opportunity to re-check things like whether
the current G1 group was already closed.
By fixing these issues, the signal stealing code can be eliminated,
since there is no concept of signal stealing anymore. The code to block
for all waiters to exit g_refs can also be removed, since any waiters
that are still in the g_refs region can be guaranteed to safely wake
up and exit. If there are still any left at this time, they are all
sent one final futex wakeup to ensure that they are not blocked any
longer, but there is no need for the signaller to block and wait for
them to wake up and exit the g_refs region.
The signal count is then effectively "zeroed" but since it is now
relative to g1_start, this is done by advancing it to a new value that
can be observed by any pending blocking waiters. Any late waiters can
always tell the difference, and can thus just cleanly exit if they are
in a stale G1 or G2. They can never steal a signal from the current
G1 if they are not in the current G1, since the signal value that has
to match in the cmpxchg has the low 31 bits of the g1_start value
contained in it, and that's first checked, and then it won't match if
there's a G1/G2 change.
Note: the 31-bit sequence number used in g_signals is designed to
handle wrap-around when checking the signal count, but if the entire
31-bit wraparound (2 billion signals) occurs while there is still a
late waiter that has not yet resumed, and it happens to then match
the current g1_start low bits, and the pre-emption occurs after the
normal "closed group" checks (which are 64-bit) but then hits the
futex syscall and signal consuming code, then an A/B/A issue could
still result and cause an incorrect assumption about whether it
should block. This particular scenario seems unlikely in practice.
Note that once awake from the futex, the waiter would notice the
closed group before consuming the signal (since that's still a 64-bit
check that would not be aliased in the wrap-around in g_signals),
so the biggest impact would be blocking on the futex until the next
full wakeup from a G1/G2 switch.
Signed-off-by: Frank Barrus <frankbarrus_sw@shaggy.cc>
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
I used these shell commands:
../glibc/scripts/update-copyrights $PWD/../gnulib/build-aux/update-copyright
(cd ../glibc && git commit -am"[this commit message]")
and then ignored the output, which consisted lines saying "FOO: warning:
copyright statement not found" for each of 7061 files FOO.
I then removed trailing white space from math/tgmath.h,
support/tst-support-open-dev-null-range.c, and
sysdeps/x86_64/multiarch/strlen-vec.S, to work around the following
obscure pre-commit check failure diagnostics from Savannah. I don't
know why I run into these diagnostics whereas others evidently do not.
remote: *** 912-#endif
remote: *** 913:
remote: *** 914-
remote: *** error: lines with trailing whitespace found
...
remote: *** error: sysdeps/unix/sysv/linux/statx_cp.c: trailing lines
We stopped adding "Contributed by" or similar lines in sources in 2012
in favour of git logs and keeping the Contributors section of the
glibc manual up to date. Removing these lines makes the license
header a bit more consistent across files and also removes the
possibility of error in attribution when license blocks or files are
copied across since the contributed-by lines don't actually reflect
reality in those cases.
Move all "Contributed by" and similar lines (Written by, Test by,
etc.) into a new file CONTRIBUTED-BY to retain record of these
contributions. These contributors are also mentioned in
manual/contrib.texi, so we just maintain this additional record as a
courtesy to the earlier developers.
The following scripts were used to filter a list of files to edit in
place and to clean up the CONTRIBUTED-BY file respectively. These
were not added to the glibc sources because they're not expected to be
of any use in future given that this is a one time task:
https://gist.github.com/siddhesh/b5ecac94eabfd72ed2916d6d8157e7dchttps://gist.github.com/siddhesh/15ea1f5e435ace9774f485030695ee02
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
The remaining symbols are mostly used by libthread_db.
__pthread_get_minstack has to remain exported even though unused.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
A new build flag, _TIME_BITS, enables the usage of the newer 64-bit
time symbols for legacy ABI (where 32-bit time_t is default). The 64
bit time support is only enabled if LFS (_FILE_OFFSET_BITS=64) is
also used.
Different than LFS support, the y2038 symbols are added only for the
required ABIs (armhf, csky, hppa, i386, m68k, microblaze, mips32,
mips64-n32, nios2, powerpc32, sparc32, s390-32, and sh). The ABIs with
64-bit time support are unchanged, both for symbol and types
redirection.
On Linux the full 64-bit time support requires a minimum of kernel
version v5.1. Otherwise, the 32-bit fallbacks are used and might
results in error with overflow return code (EOVERFLOW).
The i686-gnu does not yet support 64-bit time.
This patch exports following rediretions to support 64-bit time:
* libc:
adjtime
adjtimex
clock_adjtime
clock_getres
clock_gettime
clock_nanosleep
clock_settime
cnd_timedwait
ctime
ctime_r
difftime
fstat
fstatat
futimens
futimes
futimesat
getitimer
getrusage
gettimeofday
gmtime
gmtime_r
localtime
localtime_r
lstat_time
lutimes
mktime
msgctl
mtx_timedlock
nanosleep
nanosleep
ntp_gettime
ntp_gettimex
ppoll
pselec
pselect
pthread_clockjoin_np
pthread_cond_clockwait
pthread_cond_timedwait
pthread_mutex_clocklock
pthread_mutex_timedlock
pthread_rwlock_clockrdlock
pthread_rwlock_clockwrlock
pthread_rwlock_timedrdlock
pthread_rwlock_timedwrlock
pthread_timedjoin_np
recvmmsg
sched_rr_get_interval
select
sem_clockwait
semctl
semtimedop
sem_timedwait
setitimer
settimeofday
shmctl
sigtimedwait
stat
thrd_sleep
time
timegm
timerfd_gettime
timerfd_settime
timespec_get
utime
utimensat
utimes
utimes
wait3
wait4
* librt:
aio_suspend
mq_timedreceive
mq_timedsend
timer_gettime
timer_settime
* libanl:
gai_suspend
Reviewed-by: Lukasz Majewski <lukma@denx.de>
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
Tested-by: Carlos O'Donell <carlos@redhat.com>
The symbol was moved using scripts/move-symbol-to-libc.py.
The __pthread_cond_wait@@GLIBC_PRIVATE symbol is no longer
neded, so remove that as well.
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
Tested-by: Carlos O'Donell <carlos@redhat.com>
The symbol was moved using scripts/move-symbol-to-libc.py.
The __pthread_cond_timedwait@@GLIBC_PRIVATE symbol is no longer
neded, so remove that as well.
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
Tested-by: Carlos O'Donell <carlos@redhat.com>
Onl pthread_cond_clockwait did not have a forwarder, so it needs
a new symbol version.
Some complications arise due to the need to supply hidden aliases,
GLIBC_PRIVATE exports (for the C11 condition variable implementation
that still remains in libpthread) and 64-bit time_t stubs.
pthread_cond_broadcast, pthread_cond_signal, pthread_cond_timedwait,
pthread_cond_wait, pthread_cond_clockwait have been moved using
scripts/move-symbol-to-libc.py.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
I used these shell commands:
../glibc/scripts/update-copyrights $PWD/../gnulib/build-aux/update-copyright
(cd ../glibc && git commit -am"[this commit message]")
and then ignored the output, which consisted lines saying "FOO: warning:
copyright statement not found" for each of 6694 files FOO.
I then removed trailing white space from benchtests/bench-pthread-locks.c
and iconvdata/tst-iconv-big5-hkscs-to-2ucs4.c, to work around this
diagnostic from Savannah:
remote: *** pre-commit check failed ...
remote: *** error: lines with trailing whitespace found
remote: error: hook declined to update refs/heads/master
Some futex-internal calls require additional check for EOVERFLOW (as
indicated by [1] [2] [3]). For both mutex and rwlock code, EOVERFLOW is
handle as ETIMEDOUT; since it indicate to the caller that the blocking
operation could not be issued.
For mutex it avoids a possible issue where PTHREAD_MUTEX_ROBUST_* might
assume EOVERFLOW indicate futex has succeed, and for PTHREAD_MUTEX_PP_*
it avoid a potential busy infinite loop. For rwlock and semaphores, it
also avoids potential busy infinite loops.
Checked on x86_64-linux-gnu and i686-linux-gnu, although EOVERFLOW
won't be possible with current usage (since all timeouts on 32-bit
architectures with 32-bit time_t support will be in the range of
32-bit time_t).
[1] https://sourceware.org/pipermail/libc-alpha/2020-November/120079.html
[2] https://sourceware.org/pipermail/libc-alpha/2020-November/120080.html
[3] https://sourceware.org/pipermail/libc-alpha/2020-November/120127.html
It is used solely on __pthread_cond_wait_common and the call can be
replaced by a __futex_abstimed_wait_cancelable64 one.
Checked on x86_64-linux-gnu and i686-linux-gnu.
Reviewed-by: Lukasz Majewski <lukma@denx.de>
The pthread_cond_clockwait and pthread_cond_timedwait have been converted
to support 64 bit time.
This change introduces new futex_abstimed_wait_cancelable64 function in
./sysdeps/nptl/futex-helpers.c, which uses futex_time64 where possible
and tries to replace low-level preprocessor macros from
lowlevellock-futex.h
The pthread_cond_{clock|timed}wait only accepts absolute time. Moreover,
there is no need to check for NULL passed as *abstime pointer as
__pthread_cond_wait_common() always passes non-NULL struct __timespec64
pointer to futex_abstimed_wait_cancellable64().
For systems with __TIMESIZE != 64 && __WORDSIZE == 32:
- Conversions between 64 bit time to 32 bit are necessary
- Redirection to __pthread_cond_{clock|timed}wait64 will provide support
for 64 bit time
The futex_abstimed_wait_cancelable64 function has been put into a separate
file on the purpose - to avoid issues apparent on the m68k architecture
related to small number of available registers (there is not enough
registers to put all necessary arguments in them if the above function
would be added to futex-internal.h with __always_inline attribute).
In fact - new function - namely __futex_abstimed_wait_cancellable32 is
used to reduce number of needed registers (as some in-register values are
stored on the stack when function call is made).
Build tests:
./src/scripts/build-many-glibcs.py glibcs
Run-time tests:
- Run specific tests on ARM/x86 32bit systems (qemu):
https://github.com/lmajewski/meta-y2038 and run tests:
https://github.com/lmajewski/y2038-tests/commits/master
Above tests were performed with Y2038 redirection applied as well as without
to test the proper usage of both __pthread_cond_{clock|timed}wait64 and
__pthread_cond_{clock|timed}wait.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
The valid_nanoseconds () static inline function has been introduced to
check if nanoseconds value is in the correct range - greater or equal to
zero and less than 1000000000.
The explicit #include <time.h> has been added to files where it was
missing.
The __syscall_slong_t type for ns has been used to avoid issues on x32.
Tested with:
- scripts/build-many-glibcs.py
- make PARALLELMFLAGS="-j12" && make PARALLELMFLAGS="-j12" xcheck on x86_64
The only implementation of futex_supports_exact_relative_timeouts always
returns true. Let's remove it and all its callers.
* nptl/pthread_cond_wait.c: (__pthread_cond_clockwait): Remove code
that is only useful if futex_supports_exact_relative_timeouts ()
returns false.
* nptl/pthread_condattr_setclock.c: (pthread_condattr_setclock):
Likewise.
* sysdeps/nptl/futex-internal.h: Remove comment about relative
timeouts potentially being imprecise since it's no longer true.
Remove declaration of futex_supports_exact_relative_timeouts.
* sysdeps/unix/sysv/linux/futex-internal.h: Remove implementation
of futex_supports_exact_relative_timeouts.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Add:
int pthread_cond_clockwait (pthread_cond_t *cond,
pthread_mutex_t *mutex,
clockid_t clockid,
const struct timespec *abstime)
which behaves just like pthread_cond_timedwait except it always measures
abstime against the supplied clockid. Currently supports CLOCK_REALTIME
and
CLOCK_MONOTONIC and returns EINVAL if any other clock is specified.
Includes feedback from many others. This function was originally
proposed[1] as pthread_cond_timedwaitonclock_np, but The Austin Group
preferred the new name.
* nptl/Makefile: Add tst-cond26 and tst-cond27
* nptl/Versions (GLIBC_2.30): Add pthread_cond_clockwait
* sysdeps/nptl/pthread.h: Likewise
* nptl/forward.c: Add __pthread_cond_clockwait
* nptl/forward.c: Likewise
* nptl/pthreadP.h: Likewise
* sysdeps/nptl/pthread-functions.h: Likewise
* nptl/pthread_cond_wait.c (__pthread_cond_wait_common): Add
clockid parameter and comment describing why we don't need to
check
its value. Use that value when calling
futex_abstimed_wait_cancelable rather than reading the clock
from
the flags. (__pthread_cond_wait): Pass unused clockid parameter.
(__pthread_cond_timedwait): Read clock from flags and pass it to
__pthread_cond_wait_common. (__pthread_cond_clockwait): Add new
function with weak alias from pthread_cond_clockwait.
* sysdeps/mach/hurd/i386/libpthread.abilist (GLIBC_2.30):
* Likewise.
* sysdeps/unix/sysv/linux/aarch64/libpthread.abilist
* (GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/alpha/libpthread.abilist (GLIBC_2.30):
* Likewise.
* sysdeps/unix/sysv/linux/arm/libpthread.abilist (GLIBC_2.30):
* Likewise.
* sysdeps/unix/sysv/linux/csky/libpthread.abilist (GLIBC_2.30):
* Likewise.
* sysdeps/unix/sysv/linux/hppa/libpthread.abilist (GLIBC_2.30):
* Likewise.
* sysdeps/unix/sysv/linux/i386/libpthread.abilist (GLIBC_2.30):
* Likewise.
* sysdeps/unix/sysv/linux/ia64/libpthread.abilist (GLIBC_2.30):
* Likewise.
* sysdeps/unix/sysv/linux/m68k/coldfire/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/m68k/m680x0/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/microblaze/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/mips/mips32/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/mips/mips64/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/nios2/libpthread.abilist (GLIBC_2.30):
* Likewise.
* sysdeps/unix/sysv/linux/powerpc/powerpc32/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/powerpc/powerpc64/be/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/powerpc/powerpc64/le/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/riscv/rv64/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/s390/s390-32/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/s390/s390-64/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/sh/libpthread.abilist (GLIBC_2.30):
* Likewise.
* sysdeps/unix/sysv/linux/sparc/sparc32/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/sparc/sparc64/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/x86_64/64/libpthread.abilist
(GLIBC_2.30): Likewise.
* sysdeps/unix/sysv/linux/x86_64/x32/libpthread.abilist
(GLIBC_2.30): Likewise.
* nptl/tst-cond11.c (run_test): Support testing
pthread_cond_clockwait too by using a special magic
CLOCK_USE_ATTR_CLOCK value to determine whether to call
pthread_cond_timedwait or pthread_cond_clockwait. (do_test):
Pass
CLOCK_USE_ATTR_CLOCK for existing tests, and add new tests using
all combinations of CLOCK_MONOTONIC and CLOCK_REALTIME.
* ntpl/tst-cond26.c: New test for passing unsupported and
* invalid
clocks to pthread_cond_clockwait.
* nptl/tst-cond27.c: Add test similar to tst-cond5.c, but using
struct timespec and pthread_cond_clockwait.
* manual/threads.texi: Document pthread_cond_clockwait. The
* comment
was provided by Carlos O'Donell.
[1] https://sourceware.org/ml/libc-alpha/2015-07/msg00193.html
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
In preparation for adding POSIX clockwait variants of timedwait functions,
add a clockid_t parameter to futex_abstimed_wait functions and pass
CLOCK_REALTIME from all callers for the time being.
Replace lll_futex_timed_wait_bitset with lll_futex_clock_wait_bitset
which takes a clockid_t parameter rather than the magic clockbit.
* sysdeps/nptl/lowlevellock-futex.h,
sysdeps/unix/sysv/linux/lowlevellock-futex.h: Replace
lll_futex_timed_wait_bitset with lll_futex_clock_wait_bitset that
takes a clockid rather than a special clockbit.
* sysdeps/nptl/lowlevellock-futex.h: Add
lll_futex_supported_clockid so that client functions can check
whether their clockid parameter is valid even if they don't
ultimately end up calling lll_futex_clock_wait_bitset.
* sysdeps/nptl/futex-internal.h,
sysdeps/unix/sysv/linux/futex-internal.h
(futex_abstimed_wait, futex_abstimed_wait_cancelable): Add
clockid_t parameter to indicate which clock the absolute time
passed should be measured against. Pass that clockid onto
lll_futex_clock_wait_bitset. Add invalid clock as reason for
returning -EINVAL.
* sysdeps/nptl/futex-internal.h,
sysdeps/unix/sysv/linux/futex-internal.h: Introduce
futex_abstimed_supported_clockid so that client functions can check
whether their clockid parameter is valid even if they don't
ultimately end up calling futex_abstimed_wait.
* nptl/pthread_cond_wait.c (__pthread_cond_wait_common): Remove
code to calculate relative timeout for
__PTHREAD_COND_CLOCK_MONOTONIC_MASK and just pass CLOCK_MONOTONIC
or CLOCK_REALTIME as required to futex_abstimed_wait_cancelable.
* nptl/pthread_rwlock_common (__pthread_rwlock_rdlock_full)
(__pthread_wrlock_full), nptl/sem_waitcommon (do_futex_wait): Pass
additional CLOCK_REALTIME to futex_abstimed_wait_cancelable.
* nptl/pthread_mutex_timedlock.c (__pthread_mutex_timedlock):
Switch to lll_futex_clock_wait_bitset and pass CLOCK_REALTIME
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
This is a new implementation for condition variables, required
after http://austingroupbugs.net/view.php?id=609 to fix bug 13165. In
essence, we need to be stricter in which waiters a signal or broadcast
is required to wake up; this couldn't be solved using the old algorithm.
ISO C++ made a similar clarification, so this also fixes a bug in
current libstdc++, for example.
We can't use the old algorithm anymore because futexes do not guarantee
to wake in FIFO order. Thus, when we wake, we can't simply let any
waiter grab a signal, but we need to ensure that one of the waiters
happening before the signal is woken up. This is something the previous
algorithm violated (see bug 13165).
There's another issue specific to condvars: ABA issues on the underlying
futexes. Unlike mutexes that have just three states, or semaphores that
have no tokens or a limited number of them, the state of a condvar is
the *order* of the waiters. A waiter on a semaphore can grab a token
whenever one is available; a condvar waiter must only consume a signal
if it is eligible to do so as determined by the relative order of the
waiter and the signal.
Therefore, this new algorithm maintains two groups of waiters: Those
eligible to consume signals (G1), and those that have to wait until
previous waiters have consumed signals (G2). Once G1 is empty, G2
becomes the new G1. 64b counters are used to avoid ABA issues.
This condvar doesn't yet use a requeue optimization (ie, on a broadcast,
waking just one thread and requeueing all others on the futex of the
mutex supplied by the program). I don't think doing the requeue is
necessarily the right approach (but I haven't done real measurements
yet):
* If a program expects to wake many threads at the same time and make
that scalable, a condvar isn't great anyway because of how it requires
waiters to operate mutually exclusive (due to the mutex usage). Thus, a
thundering herd problem is a scalability problem with or without the
optimization. Using something like a semaphore might be more
appropriate in such a case.
* The scalability problem is actually at the mutex side; the condvar
could help (and it tries to with the requeue optimization), but it
should be the mutex who decides how that is done, and whether it is done
at all.
* Forcing all but one waiter into the kernel-side wait queue of the
mutex prevents/avoids the use of lock elision on the mutex. Thus, it
prevents the only cure against the underlying scalability problem
inherent to condvars.
* If condvars use short critical sections (ie, hold the mutex just to
check a binary flag or such), which they should do ideally, then forcing
all those waiter to proceed serially with kernel-based hand-off (ie,
futex ops in the mutex' contended state, via the futex wait queues) will
be less efficient than just letting a scalable mutex implementation take
care of it. Our current mutex impl doesn't employ spinning at all, but
if critical sections are short, spinning can be much better.
* Doing the requeue stuff requires all waiters to always drive the mutex
into the contended state. This leads to each waiter having to call
futex_wake after lock release, even if this wouldn't be necessary.
[BZ #13165]
* nptl/pthread_cond_broadcast.c (__pthread_cond_broadcast): Rewrite to
use new algorithm.
* nptl/pthread_cond_destroy.c (__pthread_cond_destroy): Likewise.
* nptl/pthread_cond_init.c (__pthread_cond_init): Likewise.
* nptl/pthread_cond_signal.c (__pthread_cond_signal): Likewise.
* nptl/pthread_cond_wait.c (__pthread_cond_wait): Likewise.
(__pthread_cond_timedwait): Move here from pthread_cond_timedwait.c.
(__condvar_confirm_wakeup, __condvar_cancel_waiting,
__condvar_cleanup_waiting, __condvar_dec_grefs,
__pthread_cond_wait_common): New.
(__condvar_cleanup): Remove.
* npt/pthread_condattr_getclock.c (pthread_condattr_getclock): Adapt.
* npt/pthread_condattr_setclock.c (pthread_condattr_setclock):
Likewise.
* npt/pthread_condattr_getpshared.c (pthread_condattr_getpshared):
Likewise.
* npt/pthread_condattr_init.c (pthread_condattr_init): Likewise.
* nptl/tst-cond1.c: Add comment.
* nptl/tst-cond20.c (do_test): Adapt.
* nptl/tst-cond22.c (do_test): Likewise.
* sysdeps/aarch64/nptl/bits/pthreadtypes.h (pthread_cond_t): Adapt
structure.
* sysdeps/arm/nptl/bits/pthreadtypes.h (pthread_cond_t): Likewise.
* sysdeps/ia64/nptl/bits/pthreadtypes.h (pthread_cond_t): Likewise.
* sysdeps/m68k/nptl/bits/pthreadtypes.h (pthread_cond_t): Likewise.
* sysdeps/microblaze/nptl/bits/pthreadtypes.h (pthread_cond_t):
Likewise.
* sysdeps/mips/nptl/bits/pthreadtypes.h (pthread_cond_t): Likewise.
* sysdeps/nios2/nptl/bits/pthreadtypes.h (pthread_cond_t): Likewise.
* sysdeps/s390/nptl/bits/pthreadtypes.h (pthread_cond_t): Likewise.
* sysdeps/sh/nptl/bits/pthreadtypes.h (pthread_cond_t): Likewise.
* sysdeps/tile/nptl/bits/pthreadtypes.h (pthread_cond_t): Likewise.
* sysdeps/unix/sysv/linux/alpha/bits/pthreadtypes.h (pthread_cond_t):
Likewise.
* sysdeps/unix/sysv/linux/powerpc/bits/pthreadtypes.h (pthread_cond_t):
Likewise.
* sysdeps/x86/bits/pthreadtypes.h (pthread_cond_t): Likewise.
* sysdeps/nptl/internaltypes.h (COND_NWAITERS_SHIFT): Remove.
(COND_CLOCK_BITS): Adapt.
* sysdeps/nptl/pthread.h (PTHREAD_COND_INITIALIZER): Adapt.
* nptl/pthreadP.h (__PTHREAD_COND_CLOCK_MONOTONIC_MASK,
__PTHREAD_COND_SHARED_MASK): New.
* nptl/nptl-printers.py (CLOCK_IDS): Remove.
(ConditionVariablePrinter, ConditionVariableAttributesPrinter): Adapt.
* nptl/nptl_lock_constants.pysym: Adapt.
* nptl/test-cond-printers.py: Adapt.
* sysdeps/unix/sysv/linux/hppa/internaltypes.h (cond_compat_clear,
cond_compat_check_and_clear): Adapt.
* sysdeps/unix/sysv/linux/hppa/pthread_cond_timedwait.c: Remove file ...
* sysdeps/unix/sysv/linux/hppa/pthread_cond_wait.c
(__pthread_cond_timedwait): ... and move here.
* nptl/DESIGN-condvar.txt: Remove file.
* nptl/lowlevelcond.sym: Likewise.
* nptl/pthread_cond_timedwait.c: Likewise.
* sysdeps/unix/sysv/linux/i386/i486/pthread_cond_broadcast.S: Likewise.
* sysdeps/unix/sysv/linux/i386/i486/pthread_cond_signal.S: Likewise.
* sysdeps/unix/sysv/linux/i386/i486/pthread_cond_timedwait.S: Likewise.
* sysdeps/unix/sysv/linux/i386/i486/pthread_cond_wait.S: Likewise.
* sysdeps/unix/sysv/linux/i386/i586/pthread_cond_broadcast.S: Likewise.
* sysdeps/unix/sysv/linux/i386/i586/pthread_cond_signal.S: Likewise.
* sysdeps/unix/sysv/linux/i386/i586/pthread_cond_timedwait.S: Likewise.
* sysdeps/unix/sysv/linux/i386/i586/pthread_cond_wait.S: Likewise.
* sysdeps/unix/sysv/linux/i386/i686/pthread_cond_broadcast.S: Likewise.
* sysdeps/unix/sysv/linux/i386/i686/pthread_cond_signal.S: Likewise.
* sysdeps/unix/sysv/linux/i386/i686/pthread_cond_timedwait.S: Likewise.
* sysdeps/unix/sysv/linux/i386/i686/pthread_cond_wait.S: Likewise.
* sysdeps/unix/sysv/linux/x86_64/pthread_cond_broadcast.S: Likewise.
* sysdeps/unix/sysv/linux/x86_64/pthread_cond_signal.S: Likewise.
* sysdeps/unix/sysv/linux/x86_64/pthread_cond_timedwait.S: Likewise.
* sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S: Likewise.
This patch makes files using __ASSUME_* macros include
<kernel-features.h> explicitly, rather than relying on some other
header (such as tls.h, lowlevellock.h or pthreadP.h) to include it
implicitly. (I omitted cases where I've already posted or am testing
the patch that stops the file from needing __ASSUME_* at all.) This
accords with the general principle of making source files include the
headers for anything they use, and also helps make it safe to remove
<kernel-features.h> includes from any file that doesn't use
__ASSUME_* (some of those may be stray includes left behind after
increasing the minimum kernel version, others may never have been
needed or may have become obsolete after some other change).
Tested x86_64 that the disassembly of installed shared libraries is
unchanged by this patch.
* nptl/pthread_cond_wait.c: Include <kernel-features.h>.
* nptl/pthread_rwlock_timedrdlock.c: Likewise.
* nptl/pthread_rwlock_timedwrlock.c: Likewise.
* nptl/sysdeps/unix/sysv/linux/lowlevelrobustlock.c: Likewise.
* nscd/nscd.c: Likewise.
* sysdeps/i386/nptl/tcb-offsets.sym: Likewise.
* sysdeps/powerpc/nptl/tcb-offsets.sym: Likewise.
* sysdeps/sh/nptl/tcb-offsets.sym: Likewise.
* sysdeps/x86_64/nptl/tcb-offsets.sym: Likewise.
* pthread_mutex_lock.c: Use it instead of PTHREAD_MUTEX_PSHARED when
dealing with robust mutexes.
* pthread_mutex_timedlock.c: Likewise.
* pthread_mutex_trylock.c: Likewise.
* pthread_mutex_unlock.c: Likewise.
* sysdeps/unix/sysv/linux/pthread_mutex_cond_lock.c: Likewise.
2007-08-06 Jakub Jelinek <jakub@redhat.com>
* pthreadP.h (PTHREAD_MUTEX_PSHARED_BIT): Define.
(PTHREAD_MUTEX_TYPE): Mask __kind with 127.
(PTHREAD_MUTEX_PSHARED): Define.
* pthread_mutex_init.c (__pthread_mutex_init): Set
PTHREAD_MUTEX_PSHARED_BIT for pshared or robust
mutexes.
* pthread_mutex_lock.c (LLL_MUTEX_LOCK): Take mutex as argument
instead of its __data.__lock field, pass PTHREAD_MUTEX_PSHARED
as second argument to lll_lock.
(LLL_MUTEX_TRYLOCK): Take mutex as argument
instead of its __data.__lock field.
(LLL_ROBUST_MUTEX_LOCK): Take mutex as argument instead of its
__data.__lock field, pass PTHREAD_MUTEX_PSHARED as second argument
to lll_robust_lock.
(__pthread_mutex_lock): Update LLL_MUTEX_LOCK, LLL_MUTEX_TRYLOCK,
LLL_ROBUST_MUTEX_LOCK users, use PTHREAD_MUTEX_TYPE (mutex)
instead of mutex->__data.__kind directly, pass
PTHREAD_MUTEX_PSHARED (mutex) to lll_unlock and lll_futex_wait.
* pthread_mutex_trylock.c (__pthread_mutex_trylock): Use
PTHREAD_MUTEX_TYPE (mutex) instead of mutex->__data.__kind
directly, pass PTHREAD_MUTEX_PSHARED (mutex) to lll_unlock.
(pthread_mutex_timedlock): Pass PTHREAD_MUTEX_PSHARED (mutex)
to lll_timedlock, lll_robust_timedlock, lll_unlock and
lll_futex_timed_wait. Use PTHREAD_MUTEX_TYPE (mutex) instead
of mutex->__data.__kind directly.
* pthread_mutex_timedlock.c (pthread_mutex_timedlock): Pass
PTHREAD_MUTEX_PSHARED (mutex) to lll_timedlock,
lll_robust_timedlock, lll_unlock and lll_futex_timed_wait. Use
PTHREAD_MUTEX_TYPE (mutex) instead of mutex->__data.__kind directly.
* pthread_mutex_unlock.c (__pthread_mutex_unlock_usercnt): Pass
PTHREAD_MUTEX_PSHARED (mutex) to lll_unlock, lll_robust_unlock
and lll_futex_wake.
* pthread_mutex_setprioceiling.c (pthread_mutex_setprioceiling): Pass
PTHREAD_MUTEX_PSHARED (mutex) to lll_futex_wait and lll_futex_wake.
Use PTHREAD_MUTEX_TYPE (mutex) instead of mutex->__data.__kind
directly.
* sysdeps/unix/sysv/linux/pthread_mutex_cond_lock.c (LLL_MUTEX_LOCK):
Take mutex as argument instead of its __data.__lock field, pass
PTHREAD_MUTEX_PSHARED as second argument to lll_cond_lock.
(LLL_MUTEX_TRYLOCK): Take mutex as argument instead of its
__data.__lock field.
(LLL_ROBUST_MUTEX_LOCK): Take mutex as argument instead of its
__data.__lock field, pass PTHREAD_MUTEX_PSHARED as second argument
to lll_robust_cond_lock.
* pthread_cond_broadcast.c (__pthread_cond_broadcast): Add pshared
variable, pass it to lll_lock, lll_unlock, lll_futex_requeue and
lll_futex_wake. Don't use lll_futex_requeue if dependent mutex
has PTHREAD_MUTEX_PSHARED_BIT bit set in its __data.__kind.
* pthread_cond_destroy.c (__pthread_cond_destroy): Add pshared
variable, pass it to lll_lock, lll_unlock, lll_futex_wake and
lll_futex_wait.
* pthread_cond_signal.c (__pthread_cond_signal): Add pshared
variable, pass it to lll_lock, lll_unlock, lll_futex_wake_unlock and
lll_futex_wake.
* pthread_cond_timedwait.c (__pthread_cond_wait): Add
pshared variable, pass it to lll_lock, lll_unlock,
lll_futex_timedwait and lll_futex_wake.
* pthread_cond_wait.c (__condvar_cleanup, __pthread_cond_wait): Add
pshared variable, pass it to lll_lock, lll_unlock, lll_futex_wait
and lll_futex_wake.
* sysdeps/unix/sysv/linux/alpha/lowlevellock.h (lll_futex_requeue,
lll_futex_wake_unlock): Add private argument, use __lll_private_flag
macro.
* sysdeps/unix/sysv/linux/ia64/lowlevellock.h (lll_futex_requeue,
lll_futex_wake_unlock): Likewise.
* sysdeps/unix/sysv/linux/powerpc/lowlevellock.h (lll_futex_requeue):
Likewise.
* sysdeps/unix/sysv/linux/sparc/lowlevellock.h (lll_futex_requeue,
lll_futex_wake_unlock): Likewise.
* sysdeps/unix/sysv/linux/x86_64/lowlevellock.h (lll_futex_requeue):
Likewise.
* sysdeps/unix/sysv/linux/s390/lowlevellock.h (lll_futex_requeue,
lll_futex_wake_unlock): Likewise.
(lll_futex_wake): Fix a typo.
* sysdeps/unix/sysv/linux/pthread-pi-defines.sym (PS_BIT): Add.
* sysdeps/unix/sysv/linux/x86_64/pthread_cond_broadcast.S
(__pthread_cond_broadcast): Pass LLL_PRIVATE to lll_* and or
FUTEX_PRIVATE_FLAG into SYS_futex op if cv is process private.
Don't use FUTEX_CMP_REQUEUE if dep_mutex is not process private.
* sysdeps/unix/sysv/linux/x86_64/pthread_cond_signal.S
(__pthread_cond_signal): Pass LLL_PRIVATE to lll_* and or
FUTEX_PRIVATE_FLAG into SYS_futex op if cv is process private.
* sysdeps/unix/sysv/linux/x86_64/pthread_cond_timedwait.S
(__pthread_cond_timedwait): Likewise.
* sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:
(__condvar_cleanup, __pthread_cond_wait): Likewise.
