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

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

[Thomas Rodgers]

From: Thomas Rodgers <rodgert@twrodgers.com>

This should also be backported to gcc-11

libstdc++/ChangeLog:
	* include/bits/atomic_wait.h (__waiter::_M_do_wait_v): loop
	until observe value change.
	(__waiter_base::_M_laundered): New member.
	(__watier_base::_M_notify): Check _M_laundered to determine
	whether to wake one or all.
	(__detail::__atomic_compare): Do not implicitly convert
	result of __buildtin_memcpmp to bool,
	(__waiter_base::_S_do_spin_v): Adjust predicate.
	* testsuite/29_atomics/atomic/wait_notify/100334.cc: New
	test.
---
 libstdc++-v3/include/bits/atomic_wait.h       | 20 +++-
 .../29_atomics/atomic/wait_notify/100334.cc   | 94 +++++++++++++++++++
 2 files changed, 109 insertions(+), 5 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc

diff --git a/libstdc++-v3/include/bits/atomic_wait.h b/libstdc++-v3/include/bits/atomic_wait.h
index 984ed70f16c..528e4868410 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
@@ -277,6 +278,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	__waiter_type& _M_w;
 	__platform_wait_t* _M_addr;
+	bool _M_laundered;
 
 	template<typename _Up>
 	  static __platform_wait_t*
@@ -300,6 +302,7 @@ _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))
+	    , _M_laundered(!__platform_wait_uses_type<_Up>)
 	  {
 	  }
 
@@ -308,7 +311,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	{
 	  if (_M_addr == &_M_w._M_ver)
 	    __atomic_fetch_add(_M_addr, 1, __ATOMIC_ACQ_REL);
-	  _M_w._M_notify(_M_addr, __all, __bare);
+	  _M_w._M_notify(_M_addr,
+			 (_M_laundered ? true : __all),
+			 __bare);
 	}
 
 	template<typename _Up, typename _ValFn,
@@ -320,7 +325,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 +392,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 +462,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 00000000000..3e63eca42fa
--- /dev/null
+++ b/libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc
@@ -0,0 +1,94 @@
+// { 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;
+}
+
-- 
2.30.2

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

[Jonathan Wakely]

On 03/05/21 09:43 -0700, Thomas Rodgers wrote:
>From: Thomas Rodgers <rodgert@twrodgers.com>
>
>This should also be backported to gcc-11

The additional _M_laundered data member changes the object layout.
That isn't safe for the branch. Would it be possible to smuggle that
flag in the least significant bit of the _M_addr member, which is
always aligned to more than one byte? Just on the gcc-11 branch, not
for trunk.


>libstdc++/ChangeLog:
>	* include/bits/atomic_wait.h (__waiter::_M_do_wait_v): loop
>	until observe value change.
>	(__waiter_base::_M_laundered): New member.
>	(__watier_base::_M_notify): Check _M_laundered to determine
>	whether to wake one or all.
>	(__detail::__atomic_compare): Do not implicitly convert
>	result of __buildtin_memcpmp to bool,

Typos, and the description doesn't seem accurate (it wasn't implicitly
converting it to bool, there was always an explicit comparison, but
now it's == rather than !=).

>	(__waiter_base::_S_do_spin_v): Adjust predicate.
>	* testsuite/29_atomics/atomic/wait_notify/100334.cc: New
>	test.


OK for trunk with a fixed changelog, but we need a different patch for
the branch.

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

[Thomas Rodgers]

From: Thomas Rodgers <rodgert@twrodgers.com>

libstdc++/ChangeLog:
	* include/bits/atomic_wait.h (__waiter::_M_do_wait_v): loop
	until value change observed.
	(__waiter_base::_M_a): Renamed member from _M_addr, changed
	type to uintptr_t.
	(__waiter_base::_S_wait_addr): Change return type to uinptr_t,
	sets LSB if 'laundering' the wait address 
	(__waiter_base::_M_addr): New member, returns wait address,
	masking off LSB of _M_a.
	(__waiter_base::_M_laundered): New member, returns true if
	LSB of _M_a is set.
	(__waiter_base::_M_notify): Call _M_addr(), check _M_laundered()
	to determine whether to wake one or all.
	(__waiter_base::_M_do_spin_v): Call _M_addr().
	(__waiter_base::_M_do_spin): Likewise.
	(__waiter::_M_do_wait_v): Likewise.
	(__waiter::_M_do_wait): Likewise.
	(__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.
	* include/bits/atomic_timed_wait.h
	(__timed_waiter::_M_do_wait_until_v): Call _M_addr().
	(__timed_waiter::_M_do_wait_until): Likewise.
---
 libstdc++-v3/include/bits/atomic_timed_wait.h |  6 +-
 libstdc++-v3/include/bits/atomic_wait.h       | 49 ++++++----
 .../29_atomics/atomic/wait_notify/100334.cc   | 94 +++++++++++++++++++
 3 files changed, 129 insertions(+), 20 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc

diff --git a/libstdc++-v3/include/bits/atomic_timed_wait.h b/libstdc++-v3/include/bits/atomic_timed_wait.h
index ec7ff51cdbc..5fe64fa2219 100644
--- a/libstdc++-v3/include/bits/atomic_timed_wait.h
+++ b/libstdc++-v3/include/bits/atomic_timed_wait.h
@@ -289,7 +289,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    if (_M_do_spin(__old, std::move(__vfn), __val,
 			   __timed_backoff_spin_policy(__atime)))
 	      return true;
-	    return __base_type::_M_w._M_do_wait_until(__base_type::_M_addr, __val, __atime);
+	    return __base_type::_M_w._M_do_wait_until(__base_type::_M_addr(), __val, __atime);
 	  }
 
 	// returns true if wait ended before timeout
@@ -304,7 +304,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  __now = _Clock::now())
 	      {
 		if (__base_type::_M_w._M_do_wait_until(
-		      __base_type::_M_addr, __val, __atime)
+		      __base_type::_M_addr(), __val, __atime)
 		    && __pred())
 		  return true;
 
@@ -347,7 +347,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    auto __reltime = chrono::ceil<__wait_clock_t::duration>(__rtime);
 
 	    return __base_type::_M_w._M_do_wait_until(
-					  __base_type::_M_addr,
+					  __base_type::_M_addr(),
 					  __val,
 					  chrono::steady_clock::now() + __reltime);
 	  }
diff --git a/libstdc++-v3/include/bits/atomic_wait.h b/libstdc++-v3/include/bits/atomic_wait.h
index 984ed70f16c..06ebcc7bce3 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
@@ -276,16 +277,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	using __waiter_type = _Tp;
 
 	__waiter_type& _M_w;
-	__platform_wait_t* _M_addr;
+	uintptr_t  _M_a;
 
 	template<typename _Up>
-	  static __platform_wait_t*
+	  static uintptr_t
 	  _S_wait_addr(const _Up* __a, __platform_wait_t* __b)
 	  {
 	    if constexpr (__platform_wait_uses_type<_Up>)
-	      return reinterpret_cast<__platform_wait_t*>(const_cast<_Up*>(__a));
+	      return reinterpret_cast<uintptr_t>(const_cast<_Up*>(__a));
 	    else
-	      return __b;
+	      return reinterpret_cast<uintptr_t>(__b) | 0x1;
 	  }
 
 	static __waiter_type&
@@ -299,16 +300,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	template<typename _Up>
 	  explicit __waiter_base(const _Up* __addr) noexcept
 	    : _M_w(_S_for(__addr))
-	    , _M_addr(_S_wait_addr(__addr, &_M_w._M_ver))
-	  {
-	  }
+	    , _M_a(_S_wait_addr(__addr, &_M_w._M_ver))
+	  { }
+
+	__platform_wait_t*
+	_M_addr() const noexcept
+	{ return reinterpret_cast<__platform_wait_t*>(_M_a & (-1 << 1)); }
+
+	bool
+	_M_laundered() const
+	{ return _M_a & 0x1; }
 
 	void
 	_M_notify(bool __all, bool __bare = false)
 	{
-	  if (_M_addr == &_M_w._M_ver)
-	    __atomic_fetch_add(_M_addr, 1, __ATOMIC_ACQ_REL);
-	  _M_w._M_notify(_M_addr, __all, __bare);
+	  const auto __addr = _M_addr();
+	  const auto __laundered = _M_laundered();
+	  if (__laundered)
+	    __atomic_fetch_add(__addr, 1, __ATOMIC_ACQ_REL);
+	  _M_w._M_notify(__addr, (__laundered ? true : __all), __bare);
 	}
 
 	template<typename _Up, typename _ValFn,
@@ -320,7 +330,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>)
 	      {
@@ -339,7 +349,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  _M_do_spin_v(const _Up& __old, _ValFn __vfn,
 		       __platform_wait_t& __val,
 		       _Spin __spin = _Spin{ })
-	  { return _S_do_spin_v(_M_addr, __old, __vfn, __val, __spin); }
+	  { return _S_do_spin_v(_M_addr(), __old, __vfn, __val, __spin); }
 
 	template<typename _Pred,
 		 typename _Spin = __default_spin_policy>
@@ -358,7 +368,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  bool
 	  _M_do_spin(_Pred __pred, __platform_wait_t& __val,
 		     _Spin __spin = _Spin{ })
-	  { return _S_do_spin(_M_addr, __pred, __val, __spin); }
+	  { return _S_do_spin(_M_addr(), __pred, __val, __spin); }
       };
 
     template<typename _EntersWait>
@@ -387,7 +397,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>
@@ -399,7 +414,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		__platform_wait_t __val;
 		if (__base_type::_M_do_spin(__pred, __val))
 		  return;
-		__base_type::_M_w._M_do_wait(__base_type::_M_addr, __val);
+		__base_type::_M_w._M_do_wait(__base_type::_M_addr(), __val);
 	      }
 	    while (!__pred());
 	  }
@@ -452,7 +467,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 00000000000..3e63eca42fa
--- /dev/null
+++ b/libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc
@@ -0,0 +1,94 @@
+// { 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;
+}
+
-- 
2.30.2

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

[Thomas Rodgers]

From: Thomas Rodgers <rodgert@twrodgers.com>

Please ignore the previous patch. This one removes the need to carry any
extra state in the case of a 'laundered' atomic wait.

libstdc++/ChangeLog:
	* include/bits/atomic_wait.h (__waiter::_M_do_wait_v): loop
	until value change observed.
	(__waiter_base::_M_laundered): New member function.
	(__watier_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.
---
 libstdc++-v3/include/bits/atomic_wait.h       | 28 ++++--
 .../29_atomics/atomic/wait_notify/100334.cc   | 94 +++++++++++++++++++
 2 files changed, 114 insertions(+), 8 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc

diff --git a/libstdc++-v3/include/bits/atomic_wait.h b/libstdc++-v3/include/bits/atomic_wait.h
index 984ed70f16c..07bb744d822 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 00000000000..3e63eca42fa
--- /dev/null
+++ b/libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc
@@ -0,0 +1,94 @@
+// { 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;
+}
+
-- 
2.30.2

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

[Jonathan Wakely]

On 13/05/21 18:54 -0700, Thomas Rodgers wrote:
>From: Thomas Rodgers <rodgert@twrodgers.com>
>
>Please ignore the previous patch. This one removes the need to carry any
>extra state in the case of a 'laundered' atomic wait.
>
>libstdc++/ChangeLog:
>	* include/bits/atomic_wait.h (__waiter::_M_do_wait_v): loop
>	until value change observed.
>	(__waiter_base::_M_laundered): New member function.
>	(__watier_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.
>---
> libstdc++-v3/include/bits/atomic_wait.h       | 28 ++++--
> .../29_atomics/atomic/wait_notify/100334.cc   | 94 +++++++++++++++++++
> 2 files changed, 114 insertions(+), 8 deletions(-)
> create mode 100644 libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc
>
>diff --git a/libstdc++-v3/include/bits/atomic_wait.h b/libstdc++-v3/include/bits/atomic_wait.h
>index 984ed70f16c..07bb744d822 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);

Please mention this increment in the changelog.

OK for trunk and gcc-11 with that change, thanks.

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

[Jonathan Wakely]

On 14/05/21 18:09 +0100, Jonathan Wakely wrote:
>On 13/05/21 18:54 -0700, Thomas Rodgers wrote:
>>From: Thomas Rodgers <rodgert@twrodgers.com>
>>
>>Please ignore the previous patch. This one removes the need to carry any
>>extra state in the case of a 'laundered' atomic wait.
>>
>>libstdc++/ChangeLog:
>>	* include/bits/atomic_wait.h (__waiter::_M_do_wait_v): loop
>>	until value change observed.
>>	(__waiter_base::_M_laundered): New member function.
>>	(__watier_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.
>>---
>>libstdc++-v3/include/bits/atomic_wait.h       | 28 ++++--
>>.../29_atomics/atomic/wait_notify/100334.cc   | 94 +++++++++++++++++++
>>2 files changed, 114 insertions(+), 8 deletions(-)
>>create mode 100644 libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc
>>
>>diff --git a/libstdc++-v3/include/bits/atomic_wait.h b/libstdc++-v3/include/bits/atomic_wait.h
>>index 984ed70f16c..07bb744d822 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);
>
>Please mention this increment in the changelog.

Ugh, sorry, I seem to have forgotten how to read a diff.

>OK for trunk and gcc-11 with that change, thanks.

OK to push, no changes needed.

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

[Thomas Rodgers]

On 2021-05-17 09:43, Jonathan Wakely wrote:

> On 14/05/21 18:09 +0100, Jonathan Wakely wrote: On 13/05/21 18:54 
> -0700, Thomas Rodgers wrote: From: Thomas Rodgers 
> <rodgert@twrodgers.com>
> 
> Please ignore the previous patch. This one removes the need to carry 
> any
> extra state in the case of a 'laundered' atomic wait.
> 
> libstdc++/ChangeLog:
> * include/bits/atomic_wait.h (__waiter::_M_do_wait_v): loop
> until value change observed.
> (__waiter_base::_M_laundered): New member function.
> (__watier_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.
> ---
> libstdc++-v3/include/bits/atomic_wait.h       | 28 ++++--
> .../29_atomics/atomic/wait_notify/100334.cc   | 94 +++++++++++++++++++
> 2 files changed, 114 insertions(+), 8 deletions(-)
> create mode 100644 
> libstdc++-v3/testsuite/29_atomics/atomic/wait_notify/100334.cc
> 
> diff --git a/libstdc++-v3/include/bits/atomic_wait.h 
> b/libstdc++-v3/include/bits/atomic_wait.h
> index 984ed70f16c..07bb744d822 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);
> Please mention this increment in the changelog.

Ugh, sorry, I seem to have forgotten how to read a diff.

> OK for trunk and gcc-11 with that change, thanks.

OK to push, no changes needed.

Tested x86_64-pc-linux-gnu, committed to master and cherry-picked to 
releases/gcc-11.