libstdc++: Fix wrong thread waking on notify [PR100334]

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

libstdc++-v3/ChangeLog:
	* include/bits/atomic_wait.h (__waiter::_M_do_wait_v): loop
	until value change observed.
	(__waiter_base::_M_laundered): New member.
	(__waiter_base::_M_notify): Check _M_laundered to determine
	whether to wake one or all.
	(__detail::__atomic_compare): Return true if call to
	__builtin_memcmp() == 0.
	(__waiter_base::_S_do_spin_v): Adjust predicate.
	* testsuite/29_atomics/atomic/wait_notify/100334.cc: New
	test.

2 files changed, 113 insertions, 8 deletions

diff --git a/libstdc++-v3/include/bits/atomic_wait.h b/libstdc++-v3/include/bits/atomic_wait.h
index 984ed70..07bb744 100644
--- a/libstdc++-v3/include/bits/atomic_wait.h
+++ b/libstdc++-v3/include/bits/atomic_wait.h
@@ -181,11 +181,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return false;
       }
 
+    // return true if equal
     template<typename _Tp>
       bool __atomic_compare(const _Tp& __a, const _Tp& __b)
       {
 	// TODO make this do the correct padding bit ignoring comparison
-	return __builtin_memcmp(&__a, &__b, sizeof(_Tp)) != 0;
+	return __builtin_memcmp(&__a, &__b, sizeof(_Tp)) == 0;
       }
 
     struct __waiter_pool_base
@@ -300,14 +301,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  explicit __waiter_base(const _Up* __addr) noexcept
 	    : _M_w(_S_for(__addr))
 	    , _M_addr(_S_wait_addr(__addr, &_M_w._M_ver))
-	  {
-	  }
+	  { }
+
+	bool
+	_M_laundered() const
+	{ return _M_addr == &_M_w._M_ver; }
 
 	void
 	_M_notify(bool __all, bool __bare = false)
 	{
-	  if (_M_addr == &_M_w._M_ver)
-	    __atomic_fetch_add(_M_addr, 1, __ATOMIC_ACQ_REL);
+	  if (_M_laundered())
+	    {
+	      __atomic_fetch_add(_M_addr, 1, __ATOMIC_ACQ_REL);
+	      __all = true;
+	    }
 	  _M_w._M_notify(_M_addr, __all, __bare);
 	}
 
@@ -320,7 +327,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		       _Spin __spin = _Spin{ })
 	  {
 	    auto const __pred = [=]
-	      { return __detail::__atomic_compare(__old, __vfn()); };
+	      { return !__detail::__atomic_compare(__old, __vfn()); };
 
 	    if constexpr (__platform_wait_uses_type<_Up>)
 	      {
@@ -387,7 +394,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    __platform_wait_t __val;
 	    if (__base_type::_M_do_spin_v(__old, __vfn, __val))
 	      return;
-	    __base_type::_M_w._M_do_wait(__base_type::_M_addr, __val);
+
+	    do
+	      {
+		__base_type::_M_w._M_do_wait(__base_type::_M_addr, __val);
+	      }
+	    while (__detail::__atomic_compare(__old, __vfn()));
 	  }
 
 	template<typename _Pred>
@@ -452,7 +464,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __atomic_notify_address(const _Tp* __addr, bool __all) noexcept
     {
       __detail::__bare_wait __w(__addr);
-      __w._M_notify(__all, true);
+      __w._M_notify(__all);
     }
 
   // This call is to be used by atomic types which track contention externally
diff --git a/libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc b/libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc
new file mode 100644
index 0000000..fceb709
--- /dev/null
+++ b/libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc
@@ -0,0 +1,93 @@
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+// { dg-require-gthreads "" }
+// { dg-additional-options "-pthread" { target pthread } }
+// { dg-add-options libatomic }
+
+// Copyright (C) 2021 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <atomic>
+#include <future>
+
+#include <testsuite_hooks.h>
+
+template <typename T>
+struct atomics_sharing_same_waiter
+{
+   std::atomic<T> tmp[49 * 4] = {};
+   std::atomic<T>* a[4] = {
+      { &tmp[0] },
+      { &tmp[16 * 4] },
+      { &tmp[32 * 4] },
+      { &tmp[48 * 4] }
+   };
+};
+
+constexpr unsigned key(void * a)
+{
+  constexpr uintptr_t ct = 16;
+  return (uintptr_t(a) >> 2) % ct;
+}
+
+int
+main()
+{
+  // all atomic share the same waiter
+//  atomics_sharing_same_waiter<char> atomics;
+  atomics_sharing_same_waiter<char> atomics;
+  for (auto& atom : atomics.a)
+  {
+    atom->store(0);
+  }
+
+  auto a = &std::__detail::__waiter_pool_base::_S_for(reinterpret_cast<char *>(atomics.a[0]));
+  auto b = &std::__detail::__waiter_pool_base::_S_for(reinterpret_cast<char *>(atomics.a[1]));
+  VERIFY( a == b );
+
+  auto fut0 = std::async(std::launch::async, [&] { atomics.a[0]->wait(0); });
+  auto fut1 = std::async(std::launch::async, [&] { atomics.a[1]->wait(0); });
+  auto fut2 = std::async(std::launch::async, [&] { atomics.a[2]->wait(0); });
+  auto fut3 = std::async(std::launch::async, [&] { atomics.a[3]->wait(0); });
+
+  // make sure the all threads already await
+  std::this_thread::sleep_for(std::chrono::milliseconds{100});
+
+  atomics.a[2]->store(1);
+  atomics.a[2]->notify_one();
+
+  VERIFY(std::future_status::timeout == fut0.wait_for(std::chrono::milliseconds{100}));
+  VERIFY(atomics.a[0]->load() == 0);
+
+  VERIFY(std::future_status::timeout == fut1.wait_for(std::chrono::milliseconds{100}));
+  VERIFY(atomics.a[1]->load() == 0);
+
+  VERIFY(std::future_status::ready == fut2.wait_for(std::chrono::milliseconds{100}));
+  VERIFY(atomics.a[2]->load() == 1);
+
+  VERIFY(std::future_status::timeout == fut3.wait_for(std::chrono::milliseconds{100}));
+  VERIFY(atomics.a[3]->load() == 0);
+
+  atomics.a[0]->store(1);
+  atomics.a[0]->notify_one();
+  atomics.a[1]->store(1);
+  atomics.a[1]->notify_one();
+  atomics.a[3]->store(1);
+  atomics.a[3]->notify_one();
+
+  return 0;
+}