https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127757
Bug ID: 127757
Summary: [16/17 Regression] atomic<T>::notify_all() can miss a
futex waiter: waiter-count check is not ordered after
the caller's store
Product: gcc
Version: 16.1.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: daniel.grunwald at gmail dot com
Target Milestone: ---
Created attachment 65775
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65775&action=edit
Reproducer demonstrating lost wake ups
For types that wait directly on a futex (4-byte scalars on Linux),
`__notify_impl` in
src/c++20/atomic.cc skips the FUTEX_WAKE if the per-bucket waiter count is
zero:
if (!proxy_wait)
{
if (__track_contention)
if (!__waitable_state::_S_state_for(__addr)._M_waiting())
return;
__platform_notify(__wait_addr, __all, __args._M_obj_size);
return;
}
The two threads then do:
notifier waiter
x.store(new, release) _M_waiters fetch_add (seq_cst)
_M_waiters load (seq_cst) futex(FUTEX_WAIT, &x, old)
This is the store-buffering pattern. Nothing orders the caller's store before
the load of
`_M_waiters`: a seq_cst load does not order against a preceding non-seq_cst
store to a
different object. So the notifier can read `_M_waiters == 0` and return, while
the waiter
increments `_M_waiters`, still reads `old` from `x` in the kernel, and sleeps.
On x86-64
the store is a plain `mov` and the `_M_waiting()` load is a plain `mov` with no
fence in
between (checked in the disassembly of `__notify_impl` in libstdc++.so.6 from
16.1.0), so
the reordering happens on real hardware: the load can complete while the store
to `x` is
still in the store buffer.
[atomics.wait] makes the waiter eligible to be unblocked: it blocked after
observing
`old`, the store of `new` follows that in the modification order of `x`, and
the store
happens before the notify. The waiter stays blocked until something else wakes
it.
We hit this as a nondeterministic hang in a multithreaded program, with every
thread
idle except one blocked in `std::atomic<enum>::wait` on a value that had
already
changed. Attaching gdb made the futex syscall return, the wait loop re-read the
value and the program completed.
Reproducer (attached below). The notifier makes cache-missing stores before the
store to
`x` to keep that store in the store buffer longer; this only widens the window.
A
watchdog thread detects a waiter that is still blocked although `x` already has
the new
value, and recovers with an extra notify_all():
$ g++ -std=c++20 -O2 -pthread repro.cpp -o repro && ./repro 300000 32
...
300000 iterations, 124 lost wakeups
$ g++ -std=c++20 -O2 -pthread -DFENCE repro.cpp -o repro && ./repro 300000
32
300000 iterations, 0 lost wakeups
Results for 300000 iterations with 32 cold stores, each binary run against the
libstdc++.so.6 of the compiler that built it:
GCC lost wakeups lost wakeups with -DFENCE
11.5.0 0 0
12.5.0 0 0
13.4.0 0 0
14.3.0 0 0
15.2.0 0 0
16.1.0 124 0
With 16.1.0, 8 cold stores still give 12 lost wakeups
in 100000 iterations, and 0 cold stores give none. With 15.2.0, up to 400 cold
stores
give none in 100000 iterations.
Tested on an AMD EPYC 9355 (Zen 5, 32 cores), Linux 6.12.
Intel i9-13900T (32 cores), Linux 7.1.10: 9 lost wakeups with gcc 16.2.0.
The -DFENCE variant adds `std::atomic_thread_fence(std::memory_order_seq_cst)`
between the
store and `notify_all()`. Users can apply that as a workaround, but the
standard does not
require it. A fix in the library would be a seq_cst fence before the
`_M_waiting()` check
in `__notify_impl`; on x86-64 that costs an `mfence`, still much cheaper than
the syscall
it lets the check avoid.
GCC 11-15 have the same unordered check in `__waiter_pool_base::_M_notify`
(`if (__bare || _M_waiting()) __platform_notify(...)`), but there `__waiter`
increments
`_M_wait` in its constructor, before the spin loop (12 pause, 4 sched_yield).
The store
to `x` must then stay invisible for the whole spin loop for the wakeup to be
lost, which
I could not reproduce. In 16.1.0, `__wait_impl` spins first and increments
`_M_waiters`
only directly before FUTEX_WAIT, so the store only has to stay invisible for
the time
between that increment and the kernel's read of `x`.
Related: PR 106772 (discusses the waiter-count check), PR 106183 (lost wakeup
on
non-futex targets), llvm-project issue #109290.
Disclaimer: this bug was investigated and written up by Claude Opus 5.5.
