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

["lewissbaker.opensource at gmail dot com" <gcc-bugzilla@gcc.gnu.org>]

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();
    }
}
-------------