[Bug libstdc++/106183] New: std::atomic::wait might deadlock on platforms without platform_wait()

[Bug libstdc++/106183] New: std::atomic::wait might deadlock on platforms without platform_wait()

[lewissbaker.opensource at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

            Bug ID: 106183
           Summary: std::atomic::wait might deadlock on platforms without
                    platform_wait()
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: lewissbaker.opensource at gmail dot com
  Target Milestone: ---

I have been doing some research on implementations of std::atomic::notify_all()
and std::atomic::wait() as part of a C++ paper I've been working on.

I've recently been studying the libc++ implementation and I think I have
discovered a potential bug in the implementation for platforms that do not have
__GLIBCXX_HAVE_PLATFORM_WAIT defined (i.e. that don't have futex syscall or
similar) and for std::atomic<T> types where T is different from
__platform_wait_t.

I believe there is potential for a thread calling x.wait(old) to fail to be
unblocked by a call by another thread to x.notify_all() after modifying the
value to something other than 'old'.

I have reduced the current implementation of the std::atomic<T>::wait() and
std::atomic<T>::notify_all() functions and I believe the code currently in
trunk to be effectively equivalent to the following code-snippet:

------
using __platform_wait_t = std::uint64_t;

struct __waiter_pool {
  std::atomic<__platform_wait_t> _M_wait{0};
  std::mutex _M_mut;
  std::atomic<__platform_wait_t> _M_ver{0};
  std::condition_variable _M_cv;

  static __waiter_pool& _S_for(void* __addr) noexcept {
    constexpr uintptr_t __count = 16;
    static __waiter_pool __x[__count];
    uintptr_t __key = (((uintptr_t)__addr) >> 2) % __count;
    return __x[__key];
  }
};

template<typename _Tp>
bool __atomic_compare(const _Tp& __a, const _Tp& __b) noexcept {
  return std::memcmp(std::addressof(__a), std::addressof(__b), sizeof(_Tp)) ==
0;
}

template<typename T>
void atomic<T>::wait(T __old, memory_order __mo = memory_order_seq_cst)
noexcept {
  __waiter_pool& __w = __waiter_pool::_S_for(this);
  __w._M_wait.fetch_add(1, std::memory_order_seq_cst);
  do {
    __platform_wait_t __val1 = __w._M_ver.load(std::memory_order_acquire);
    if (!__atomic_compare(__old, this->load(__mo))) {
        return;
    }

    __platform__wait_t __val2 = __w._M_ver.load(std::memory_order_seq_cst);
    // <---- BUG: problem if notify_all() is executed at this point
    if (__val2 == __val1) {
        lock_guard<mutex> __lk(__w._M_mtx);
        __w._M_cv.wait(__lk);
    }

  } while (__atomic_compare(__old, this->load(__mo)));

  __w._M_wait.fetch_sub(1, std::memory_order_release);    
}

void atomic<T>::notify_all() noexcept {
    __waiter_pool& __w = __waiter_pool::_S_for(this);
    __w._M_ver.fetch_add(1, memory_order_seq_cst);
    if (__w._M_wait.load(memory_order_seq_cst) != 0) {
        __w._M_cv.notify_all();
    }
}
-------

The wait() method reads the _M_ver value then checks whether the value being
waited on has changed
and then if it has not, then reads the _M_ver value again. If the two values
read from _M_ver are
the same then we can infer that there has not been an intervening call to
notify_all().

However, after checking that _M_ver has not changed, it then (and only then)
proceeds to acquire
the lock on the _M_mut mutex and then waits on the _M_cv condition variable.

The problem occurs if the waiting thread happens to be delayed between reading
_M_ver for the second
time and blocking inside the call to  _M_cv.wait() (indicated with a comment).
If this happens, it may be possible then for another thread that was supposed
to unblock this thread
to then modify the atomic value, call notify_all() which increments _M_ver and
calls _M_cv.notify_all(),
all before the waiting thread acquires the mutex and blocks on the
condition-variable.

If this happens and no other thread is subsequently going to call notify_all()
on the atomic variable
then it's possible the call to wait() will block forever as it missed its
wake-up call.

The solution here is to do more work while holding the mutex.

I haven't fully verified the correctness of the following code, but I think it
should help to
avoid the missed wake-ups situations that are possible in the current
implementation. It does
come at a higher synchronisation cost, however, as notifying threads also need
to acquire the
mutex.

-------------

template<typename T>
void atomic<T>::wait(T __old, memory_order __mo = memory_order_seq_cst)
noexcept {
  __waiter_pool& __w = __waiter_pool::_S_for(this);
  __w._M_wait.fetch_add(1, std::memory_order_seq_cst);
  do {
    __platform_wait_t __val1 = __w._M_ver.load(std::memory_order_acquire);
    if (!__atomic_compare(__old, this->load(__mo))) {
        return;
    }

    __platform__wait_t __val2 = __w._M_ver.load(std::memory_order_seq_cst);
    if (__val2 == __val1) {
        lock_guard<mutex> __lk(__w._M_mtx);
        // read again under protection of the lock
        __val2 = __w._M_ver.load(std::memory_order_seq_cst);
        if (__val2 == __val1) {
          __w._M_cv.wait(__lk);
        }
    }
  } while (__atomic_compare(__old, this->load(__mo)));

  __w._M_wait.fetch_sub(1, std::memory_order_release);    
}

void atomic<T>::notify_all() noexcept {
    __waiter_pool& __w = __waiter_pool::_S_for(this);
    if (__w._M_wait.load(memory_order_seq_cst) != 0) {
      // need to increment _M_ver while holding the lock
      {
        lock_guard<mutex> __lk{__w._M_mtx};
        __w._M_ver.fetch_add(1, memory_order_seq_cst);
      }
      __w._M_cv.notify_all();
    }
}
-------------

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[rodgertq at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

Thomas Rodgers <rodgertq at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2022-07-06
             Status|UNCONFIRMED                 |ASSIGNED

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[tedlion_tang at foxmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

Ted_lion <tedlion_tang at foxmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |tedlion_tang at foxmail dot com

--- Comment #1 from Ted_lion <tedlion_tang at foxmail dot com> ---
I found my program blocked and it turned out to be the same problem of
atomic::wait. According to the C++20 Standard, the function atomic::wait should
perform an atomic waiting operations. The subprocedure of comparison with old
value and waiting for the notification should not be interrupted by an
operation on same atomic object.

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Ted_lion from comment #1)
> The subprocedure of comparison
> with old value and waiting for the notification should not be interrupted by
> an operation on same atomic object.

I'm not sure what you mean here, could you clarify please?

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[anthony.ajw at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

Anthony Williams <anthony.ajw at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |anthony.ajw at gmail dot com

--- Comment #3 from Anthony Williams <anthony.ajw at gmail dot com> ---
This is one of the common mistakes I mention when teaching people about
condition variables. Just because the data being waited for is atomic, doesn't
guarantee that the condition variable state is updated: you need the mutex to
synchronize that.

In current libstdc++ trunk libstdc++-v3/include/bits/atomic_wait.h insert a
line in _M_notify at line 235:

https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/atomic_wait.h;h=125b1cad88682384737c048ac236af9c4deab957;hb=refs/heads/trunk

      void
      _M_notify(const __platform_wait_t* __addr, bool __all, bool __bare)
noexcept
      {
        if (!(__bare || _M_waiting()))
          return;

#ifdef _GLIBCXX_HAVE_PLATFORM_WAIT
        __platform_notify(__addr, __all);
#else
/// INSERT HERE
        { std::lock_guard<mutex> __lock(_M_mtx); }
/// END INSERT
        if (__all)
          _M_cv.notify_all();
        else
          _M_cv.notify_one();
#endif
      }

The lock/unlock here ensures that the notify is correctly synchronized with the
wait.

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Created attachment 53394
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53394&action=edit
Proposed patch: Unblock atomic wait on non-futex platforms

    When using a mutex and condition variable, the notifying thread needs to
    increment _M_ver while holding the mutex lock, and the waiting thread
    needs to re-check after locking the mutex. This avoids a missed
    notification as described in the PR.

    By moving the increment of _M_ver to the base _M_notify we can make the
    use of the mutex local to the use of the condition variable, and
    simplify the code a little. We can use a relaxed store because the mutex
    already provides sequential consistency. Also we don't need to check
    whether __addr == &_M_ver because we know that's always true for
    platforms that use a condition variable, and so we also know that we
    always need to use notify_all() not notify_one().

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:af98cb88eb4be6a1668ddf966e975149bf8610b1

commit r13-1957-gaf98cb88eb4be6a1668ddf966e975149bf8610b1
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Jul 28 16:15:58 2022 +0100

    libstdc++: Unblock atomic wait on non-futex platforms [PR106183]

    When using a mutex and condition variable, the notifying thread needs to
    increment _M_ver while holding the mutex lock, and the waiting thread
    needs to re-check after locking the mutex. This avoids a missed
    notification as described in the PR.

    By moving the increment of _M_ver to the base _M_notify we can make the
    use of the mutex local to the use of the condition variable, and
    simplify the code a little. We can use a relaxed store because the mutex
    already provides sequential consistency. Also we don't need to check
    whether __addr == &_M_ver because we know that's always true for
    platforms that use a condition variable, and so we also know that we
    always need to use notify_all() not notify_one().

    Reviewed-by: Thomas Rodgers <trodgers@redhat.com>

    libstdc++-v3/ChangeLog:

            PR libstdc++/106183
            * include/bits/atomic_wait.h (__waiter_pool_base::_M_notify):
            Move increment of _M_ver here.
            [!_GLIBCXX_HAVE_PLATFORM_WAIT]: Lock mutex around increment.
            Use relaxed memory order and always notify all waiters.
            (__waiter_base::_M_do_wait) [!_GLIBCXX_HAVE_PLATFORM_WAIT]:
            Check value again after locking mutex.
            (__waiter_base::_M_notify): Remove increment of _M_ver.

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|rodgertq at gcc dot gnu.org        |redi at gcc dot gnu.org

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Should be fixed on trunk now.

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bjornsundin02 at gmail dot com

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
*** Bug 101037 has been marked as a duplicate of this bug. ***

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:1dfe15e534adba21e680b8128f0631e8054a5e42

commit r12-9047-g1dfe15e534adba21e680b8128f0631e8054a5e42
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Jul 28 16:15:58 2022 +0100

    libstdc++: Unblock atomic wait on non-futex platforms [PR106183]

    When using a mutex and condition variable, the notifying thread needs to
    increment _M_ver while holding the mutex lock, and the waiting thread
    needs to re-check after locking the mutex. This avoids a missed
    notification as described in the PR.

    By moving the increment of _M_ver to the base _M_notify we can make the
    use of the mutex local to the use of the condition variable, and
    simplify the code a little. We can use a relaxed store because the mutex
    already provides sequential consistency. Also we don't need to check
    whether __addr == &_M_ver because we know that's always true for
    platforms that use a condition variable, and so we also know that we
    always need to use notify_all() not notify_one().

    Reviewed-by: Thomas Rodgers <trodgers@redhat.com>

    libstdc++-v3/ChangeLog:

            PR libstdc++/106183
            * include/bits/atomic_wait.h (__waiter_pool_base::_M_notify):
            Move increment of _M_ver here.
            [!_GLIBCXX_HAVE_PLATFORM_WAIT]: Lock mutex around increment.
            Use relaxed memory order and always notify all waiters.
            (__waiter_base::_M_do_wait) [!_GLIBCXX_HAVE_PLATFORM_WAIT]:
            Check value again after locking mutex.
            (__waiter_base::_M_notify): Remove increment of _M_ver.

    (cherry picked from commit af98cb88eb4be6a1668ddf966e975149bf8610b1)

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[i.nixman at autistici dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

--- Comment #9 from niXman <i.nixman at autistici dot org> ---
looks like it's fixed for x86_64-w64-mingw32.

I used the test from the: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101037

I run it on bash loop for the night and it successfully executed for ~179k
times.

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:ed58809ea1a8ccc1829d830799d34aa51e51d39e

commit r11-10472-ged58809ea1a8ccc1829d830799d34aa51e51d39e
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Jul 28 16:15:58 2022 +0100

    libstdc++: Unblock atomic wait on non-futex platforms [PR106183]

    When using a mutex and condition variable, the notifying thread needs to
    increment _M_ver while holding the mutex lock, and the waiting thread
    needs to re-check after locking the mutex. This avoids a missed
    notification as described in the PR.

    By moving the increment of _M_ver to the base _M_notify we can make the
    use of the mutex local to the use of the condition variable, and
    simplify the code a little. We can use a relaxed store because the mutex
    already provides sequential consistency. Also we don't need to check
    whether __addr == &_M_ver because we know that's always true for
    platforms that use a condition variable, and so we also know that we
    always need to use notify_all() not notify_one().

    Reviewed-by: Thomas Rodgers <trodgers@redhat.com>

    libstdc++-v3/ChangeLog:

            PR libstdc++/106183
            * include/bits/atomic_wait.h (__waiter_pool_base::_M_notify):
            Move increment of _M_ver here.
            [!_GLIBCXX_HAVE_PLATFORM_WAIT]: Lock mutex around increment.
            Use relaxed memory order and always notify all waiters.
            (__waiter_base::_M_do_wait) [!_GLIBCXX_HAVE_PLATFORM_WAIT]:
            Check value again after locking mutex.
            (__waiter_base::_M_notify): Remove increment of _M_ver.

    (cherry picked from commit af98cb88eb4be6a1668ddf966e975149bf8610b1)

[Bug libstdc++/106183] std::atomic::wait might fail to be unblocked by notify_one/all on platforms without platform_wait()

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106183

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED
   Target Milestone|---                         |11.4

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 11.4 and 12.3