[PATCH v3] libstdc++: Improve std::lock algorithm

[Jonathan Wakely <jwakely@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 3789 bytes --]

On Tue, 22 Jun 2021 at 20:51, Jonathan Wakely wrote:
>
> On Tue, 22 Jun 2021 at 17:03, Matthias Kretz <m.kretz@gsi.de> wrote:
> >
> > On Dienstag, 22. Juni 2021 17:20:41 CEST Jonathan Wakely wrote:
> > > On Tue, 22 Jun 2021 at 14:21, Matthias Kretz wrote:
> > > > This does a try_lock on all lockabes even if any of them fails. I think
> > > > that's
> > > > not only more expensive but also non-conforming. I think you need to defer
> > > > locking and then loop from beginning to end to break the loop on the first
> > > > unsuccessful try_lock.
> > >
> > > Oops, good point. I'll add a test for that too. Here's the fixed code:
> > >
> > >     template<typename _L0, typename... _Lockables>
> > >       inline int
> > >       __try_lock_impl(_L0& __l0, _Lockables&... __lockables)
> > >       {
> > > #if __cplusplus >= 201703L
> > >         if constexpr ((is_same_v<_L0, _Lockables> && ...))
> > >           {
> > >             constexpr int _Np = 1 + sizeof...(_Lockables);
> > >             unique_lock<_L0> __locks[_Np] = {
> > >                 {__l0, defer_lock}, {__lockables, defer_lock}...
> > >             };
> > >             for (int __i = 0; __i < _Np; ++__i)
> >
> > I thought coding style requires a { here?
>
> Maybe for the compiler, but I don't think libstdc++ has such a rule. I
> can add the braces though, it's probably better.
>
> >
> > >               if (!__locks[__i].try_lock())
> > >                 {
> > >                   const int __failed = __i;
> > >                   while (__i--)
> > >                     __locks[__i].unlock();
> > >                   return __i;
> >
> > You meant `return __failed`?
>
> Yep, copy&paste error while trying to avoid the TABs in the real code
> screwing up the gmail formatting :-(
>
>
> > >                 }
> > >             for (auto& __l : __locks)
> > >               __l.release();
> > >             return -1;
> > >           }
> > >         else
> > > #endif
> > >
> > > > [...]
> > > > Yes, if only we had a wrapping integer type that wraps at an arbitrary N.
> > > > Like
> > > >
> > > > unsigned int but with parameter, like:
> > > >   for (__wrapping_uint<_Np> __k = __idx; __k != __first; --__k)
> > > >
> > > >     __locks[__k - 1].unlock();
> > > >
> > > > This is the loop I wanted to write, except --__k is simpler to write and
> > > > __k -
> > > > 1 would also wrap around to _Np - 1 for __k == 0. But if this is the only
> > > > place it's not important enough to abstract.
> > >
> > > We might be able to use __wrapping_uint in std::seed_seq::generate too, and
> > > maybe some other places in <random>. But we can add that later if we decide
> > > it's worth it.
> >
> > OK.
> >
> > > > I also considered moving it down here. Makes sense unless you want to call
> > > > __detail::__lock_impl from other functions. And if we want to make it work
> > > > for
> > > > pre-C++11 we could do
> > > >
> > > >   using __homogeneous
> > > >
> > > >     = __and_<is_same<_L1, _L2>, is_same<_L1, _L3>...>;
> > > >
> > > >   int __i = 0;
> > > >   __detail::__lock_impl(__homogeneous(), __i, 0, __l1, __l2, __l3...);
> > >
> > > We don't need tag dispatching, we could just do:
> > >
> > > if _GLIBCXX17_CONSTEXPR (homogeneous::value)
> > >  ...
> > > else
> > >  ...
> > >
> > > because both branches are valid for the homogeneous case, i.e. we aren't
> > > using if-constexpr to avoid invalid instantiations.
> >
> > But for the inhomogeneous case the homogeneous code is invalid (initialization
> > of C-array of unique_lock<_L1>).
>
> Oops, yeah of course.
>
> >
> > > But given that the default -std option is gnu++17 now, I'm OK with the
> > > iterative version only being used for C++17.
> >
> > Fair enough.

Here's what I've tested and pushed to trunk. Thanks for the
improvement and comments.

[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 12128 bytes --]

commit c556596119307f9ef1c9079ef2bd3a035dea355d
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Jun 22 13:35:19 2021

    libstdc++: Simplify std::try_lock and std::lock further
    
    The std::try_lock and std::lock algorithms can use iteration instead of
    recursion when all lockables have the same type and can be held by an
    array of unique_lock<L> objects.
    
    By making this change to __detail::__try_lock_impl it also benefits
    __detail::__lock_impl, which uses it. For std::lock we can just put the
    iterative version directly in std::lock, to avoid making any call to
    __detail::__lock_impl.
    
    Signed-off-by: Matthias Kretz <m.kretz@gsi.de>
    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>
    
    Co-authored-by: Matthias Kretz <m.kretz@gsi.de>
    
    libstdc++-v3/ChangeLog:
    
            * include/std/mutex (lock): Replace recursion with iteration
            when lockables all have the same type.
            (__detail::__try_lock_impl): Likewise. Pass lockables as
            parameters, instead of a tuple. Always lock the first one, and
            recurse for the rest.
            (__detail::__lock_impl): Adjust call to __try_lock_impl.
            (__detail::__try_to_lock): Remove.
            * testsuite/30_threads/lock/3.cc: Check that mutexes are locked.
            * testsuite/30_threads/lock/4.cc: Also test non-heterogeneous
            arguments.
            * testsuite/30_threads/unique_lock/cons/60497.cc: Also check
            std::try_lock.
            * testsuite/30_threads/try_lock/5.cc: New test.

diff --git a/libstdc++-v3/include/std/mutex b/libstdc++-v3/include/std/mutex
index 5f2d8f9ee7b..c18ca1a1955 100644
--- a/libstdc++-v3/include/std/mutex
+++ b/libstdc++-v3/include/std/mutex
@@ -514,39 +514,61 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   /// @cond undocumented
   namespace __detail
   {
+    // Lock the last lockable, after all previous ones are locked.
     template<typename _Lockable>
-      inline unique_lock<_Lockable>
-      __try_to_lock(_Lockable& __l)
-      { return unique_lock<_Lockable>{__l, try_to_lock}; }
-
-    // Lock the last element of the tuple, after all previous ones are locked.
-    template<int _Idx, typename... _Lockables>
-      inline __enable_if_t<_Idx + 1 == sizeof...(_Lockables), int>
-      __try_lock_impl(tuple<_Lockables&...>& __lockables)
+      inline int
+      __try_lock_impl(_Lockable& __lockable)
       {
-	if (auto __lock = __detail::__try_to_lock(std::get<_Idx>(__lockables)))
+	if (unique_lock<_Lockable> __lock{__lockable, try_to_lock})
 	  {
 	    __lock.release();
 	    return -1;
 	  }
 	else
-	  return _Idx;
+	  return 0;
       }
 
-    // Lock tuple elements starting from _Idx.
-    template<int _Idx, typename... _Lockables>
-      inline __enable_if_t<_Idx + 1 != sizeof...(_Lockables), int>
-      __try_lock_impl(tuple<_Lockables&...>& __lockables)
+    // Lock each lockable in turn.
+    // Use iteration if all lockables are the same type, recursion otherwise.
+    template<typename _L0, typename... _Lockables>
+      inline int
+      __try_lock_impl(_L0& __l0, _Lockables&... __lockables)
       {
-	if (auto __lock = __detail::__try_to_lock(std::get<_Idx>(__lockables)))
+#if __cplusplus >= 201703L
+	if constexpr ((is_same_v<_L0, _Lockables> && ...))
 	  {
-	    int __idx = __detail::__try_lock_impl<_Idx + 1>(__lockables);
-	    if (__idx == -1)
-	      __lock.release();
-	    return __idx;
+	    constexpr int _Np = 1 + sizeof...(_Lockables);
+	    unique_lock<_L0> __locks[_Np] = {
+		{__l0, defer_lock}, {__lockables, defer_lock}...
+	    };
+	    for (int __i = 0; __i < _Np; ++__i)
+	      {
+		if (!__locks[__i].try_lock())
+		  {
+		    const int __failed = __i;
+		    while (__i--)
+		      __locks[__i].unlock();
+		    return __failed;
+		  }
+	      }
+	    for (auto& __l : __locks)
+	      __l.release();
+	    return -1;
 	  }
 	else
-	  return _Idx;
+#endif
+	if (unique_lock<_L0> __lock{__l0, try_to_lock})
+	  {
+	    int __idx = __detail::__try_lock_impl(__lockables...);
+	    if (__idx == -1)
+	      {
+		__lock.release();
+		return -1;
+	      }
+	    return __idx + 1;
+	  }
+	else
+	  return 0;
       }
 
   } // namespace __detail
@@ -562,12 +584,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *
    *  Sequentially calls try_lock() on each argument.
    */
-  template<typename _Lock1, typename _Lock2, typename... _Lock3>
+  template<typename _L1, typename _L2, typename... _L3>
     int
-    try_lock(_Lock1& __l1, _Lock2& __l2, _Lock3&... __l3)
+    try_lock(_L1& __l1, _L2& __l2, _L3&... __l3)
     {
-      auto __lockables = std::tie(__l1, __l2, __l3...);
-      return __detail::__try_lock_impl<0>(__lockables);
+      return __detail::__try_lock_impl(__l1, __l2, __l3...);
     }
 
   /// @cond undocumented
@@ -589,8 +610,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		int __failed = 1; // index that couldn't be locked
 		{
 		  unique_lock<_L0> __first(__l0);
-		  auto __rest = std::tie(__l1...);
-		  __failed += __detail::__try_lock_impl<0>(__rest);
+		  __failed += __detail::__try_lock_impl(__l1...);
 		  if (!__failed)
 		    {
 		      __i = -1; // finished
@@ -620,15 +640,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  @post All arguments are locked.
    *
    *  All arguments are locked via a sequence of calls to lock(), try_lock()
-   *  and unlock().  If the call exits via an exception any locks that were
-   *  obtained will be released.
+   *  and unlock().  If this function exits via an exception any locks that
+   *  were obtained will be released.
    */
   template<typename _L1, typename _L2, typename... _L3>
     void
     lock(_L1& __l1, _L2& __l2, _L3&... __l3)
     {
-      int __i = 0;
-      __detail::__lock_impl(__i, 0, __l1, __l2, __l3...);
+#if __cplusplus >= 201703L
+      if constexpr (is_same_v<_L1, _L2> && (is_same_v<_L1, _L3> && ...))
+	{
+	  constexpr int _Np = 2 + sizeof...(_L3);
+	  unique_lock<_L1> __locks[] = {
+	      {__l1, defer_lock}, {__l2, defer_lock}, {__l3, defer_lock}...
+	  };
+	  int __first = 0;
+	  do {
+	    __locks[__first].lock();
+	    for (int __j = 1; __j < _Np; ++__j)
+	      {
+		const int __idx = (__first + __j) % _Np;
+		if (!__locks[__idx].try_lock())
+		  {
+		    for (int __k = __j; __k != 0; --__k)
+		      __locks[(__first + __k - 1) % _Np].unlock();
+		    __first = __idx;
+		    break;
+		  }
+	      }
+	  } while (!__locks[__first].owns_lock());
+
+	  for (auto& __l : __locks)
+	    __l.release();
+	}
+      else
+#endif
+	{
+	  int __i = 0;
+	  __detail::__lock_impl(__i, 0, __l1, __l2, __l3...);
+	}
     }
 
 #if __cplusplus >= 201703L
diff --git a/libstdc++-v3/testsuite/30_threads/lock/3.cc b/libstdc++-v3/testsuite/30_threads/lock/3.cc
index 52136077be8..5fa118768bd 100644
--- a/libstdc++-v3/testsuite/30_threads/lock/3.cc
+++ b/libstdc++-v3/testsuite/30_threads/lock/3.cc
@@ -37,7 +37,7 @@ struct user_lock
     is_locked = true;
   }
 
-  bool try_lock() 
+  bool try_lock()
   { return is_locked ? false : (is_locked = true); }
 
   void unlock()
@@ -62,6 +62,8 @@ int main()
 	{
 	  //heterogeneous types
 	  std::lock(m1, m2, m3);
+	  VERIFY( !m1.try_lock() );
+	  VERIFY( !m3.try_lock() );
 	  m1.unlock();
 	  m2.unlock();
 	  m3.unlock();
diff --git a/libstdc++-v3/testsuite/30_threads/lock/4.cc b/libstdc++-v3/testsuite/30_threads/lock/4.cc
index 7ba15cba84b..130c1f62d73 100644
--- a/libstdc++-v3/testsuite/30_threads/lock/4.cc
+++ b/libstdc++-v3/testsuite/30_threads/lock/4.cc
@@ -73,6 +73,7 @@ int unreliable_lock::lock_on = -1;
 void test01()
 {
   unreliable_lock l1, l2, l3;
+  std::mutex m1, m2, m3;
 
   try
     {
@@ -87,6 +88,60 @@ void test01()
     {
       VERIFY( false );
     }
+
+  // Repeat with non-heterogeneous arguments
+
+  try
+    {
+      unreliable_lock::count = 0;
+      std::lock(l1, l2, l3, m1);
+      VERIFY( unreliable_lock::count == 3 );
+      l1.unlock();
+      l2.unlock();
+      l3.unlock();
+      VERIFY( !m1.try_lock() ); // already locked
+      m1.unlock();
+    }
+  catch (...)
+    {
+      VERIFY( false );
+    }
+
+  try
+    {
+      unreliable_lock::count = 0;
+      std::lock(m1, l1, l2, l3);
+      VERIFY( unreliable_lock::count == 3 );
+      VERIFY( !m1.try_lock() ); // already locked
+      m1.unlock();
+      l1.unlock();
+      l2.unlock();
+      l3.unlock();
+    }
+  catch (...)
+    {
+      VERIFY( false );
+    }
+
+  try
+    {
+      unreliable_lock::count = 0;
+      std::lock(l1, m1, l2, m2, l3, m3);
+      VERIFY( unreliable_lock::count == 3 );
+      l1.unlock();
+      l2.unlock();
+      l3.unlock();
+      VERIFY( !m1.try_lock() ); // already locked
+      VERIFY( !m2.try_lock() ); // already locked
+      VERIFY( !m3.try_lock() ); // already locked
+      m1.unlock();
+      m2.unlock();
+      m3.unlock();
+    }
+  catch (...)
+    {
+      VERIFY( false );
+    }
 }
 
 void test02()
@@ -111,6 +166,31 @@ void test02()
     {
       VERIFY( false );
     }
+
+  // Repeat with non-heterogeneous arguments
+
+  try
+    {
+      unreliable_lock::lock_on = 1;
+      while (unreliable_lock::lock_on < 3)
+      {
+        unreliable_lock::count = 0;
+        unreliable_lock l1, l2, l3;
+	std::mutex m1;
+        std::lock(l1, l2, l3, m1);
+        VERIFY( unreliable_lock::count > 3 );
+        l1.unlock();
+        l2.unlock();
+        l3.unlock();
+	VERIFY( !m1.try_lock() ); // already locked
+        m1.unlock();
+        ++unreliable_lock::lock_on;
+      }
+    }
+  catch (...)
+    {
+      VERIFY( false );
+    }
 }
 
 void test03()
@@ -133,6 +213,50 @@ void test03()
     VERIFY( test );
     ++unreliable_lock::throw_on;
   }
+
+  // Repeat with non-heterogeneous arguments
+
+  unreliable_lock::throw_on = 0;
+  while (unreliable_lock::throw_on < 3)
+  {
+    unreliable_lock::count = 0;
+    unreliable_lock l1, l2, l3;
+    std::mutex m1;
+    bool test = false;
+    try
+      {
+        std::lock(l1, l2, l3, m1);
+      }
+    catch (...)
+      {
+        test = true;
+      }
+    VERIFY( test );
+    VERIFY( m1.try_lock() ); // m1 was not left locked by failed std::lock
+    m1.unlock();
+    ++unreliable_lock::throw_on;
+  }
+
+  unreliable_lock::throw_on = 0;
+  while (unreliable_lock::throw_on < 3)
+  {
+    unreliable_lock::count = 0;
+    unreliable_lock l1, l2, l3;
+    std::mutex m1;
+    bool test = false;
+    try
+      {
+        std::lock(m1, l1, l2, l3);
+      }
+    catch (...)
+      {
+        test = true;
+      }
+    VERIFY( test );
+    VERIFY( m1.try_lock() ); // m1 was not left locked by failed std::lock
+    m1.unlock();
+    ++unreliable_lock::throw_on;
+  }
 }
 
 int main()
diff --git a/libstdc++-v3/testsuite/30_threads/try_lock/5.cc b/libstdc++-v3/testsuite/30_threads/try_lock/5.cc
new file mode 100644
index 00000000000..a5574ff01fb
--- /dev/null
+++ b/libstdc++-v3/testsuite/30_threads/try_lock/5.cc
@@ -0,0 +1,41 @@
+// { dg-do run { target c++11 } }
+
+#include <mutex>
+#include <testsuite_hooks.h>
+
+struct Lockable
+{
+  static int tries;
+
+  void lock() { }
+  void unlock() { }
+  bool try_lock() { return ++tries != 2; }
+};
+
+int Lockable::tries = 0;
+
+void test01()
+{
+  Lockable l1, l2, l3;
+  std::mutex m1, m2;
+
+  VERIFY( std::try_lock(l1, l2, l3) == 1 );
+  VERIFY( Lockable::tries == 2 );
+
+  Lockable::tries = 0;
+  VERIFY( std::try_lock(m1, l1, l2, l3) == 2 );
+  VERIFY( Lockable::tries == 2 );
+
+  Lockable::tries = 0;
+  VERIFY( std::try_lock(l1, l2, l3, m1) == 1 );
+  VERIFY( Lockable::tries == 2 );
+
+  Lockable::tries = 0;
+  VERIFY( std::try_lock(m1, l1, l2, l3, m2) == 2 );
+  VERIFY( Lockable::tries == 2 );
+}
+
+int main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/30_threads/unique_lock/cons/60497.cc b/libstdc++-v3/testsuite/30_threads/unique_lock/cons/60497.cc
index 8603e56790e..08698cea783 100644
--- a/libstdc++-v3/testsuite/30_threads/unique_lock/cons/60497.cc
+++ b/libstdc++-v3/testsuite/30_threads/unique_lock/cons/60497.cc
@@ -46,3 +46,9 @@ void test02()
   test_type l1, l2, l3;
   std::lock(l1, l2, l3);
 }
+
+void test03()
+{
+  test_type l1, l2, l3;
+  std::try_lock(l1, l2, l3);
+}