[patch] Fix shared_timed_mutex::try_lock_until() et al

[Jonathan Wakely <jwakely at redhat dot com>]

When I implemented the C++14 type std::shared_timed_mutex (or
std::shared_mutex as it was originally called) I must have been half
asleep, because I completely messed up the timed locking functions,
try_lock_for, try_lock_until, try_shared_lock_for and
try_shared_lock_until. I wrote them to only use the timeout when
trying to lock the internal mutex object, but that is not the actual
lock, it just protects access to shared_timed_mutex::_M_state, so it
is only held for very short periods and is usually not heavily
contended. That means the internal lock gets taken immediately, but
then if the actual reader or writer lock can't be taken the functions
return immediately, instead of retrying for the specified time.

This fixes those functions to block on the condition variables until
the specified time, and adds a test to confirm that the timed
functions keep trying instead of returning immediately.

I've also cleaned the code up considerably, documenting the algorithm,
replacing explicit loops around condition variable waits with the form
of waiting that takes a predicate, and replacing lots of fiddly bit
twiddling with much simpler operations.

Tested x86_64-linux, powerpc64le-linux and x86_64-dragonfly3.6 with
hacked config to test the code changed in this patch as well as the
default pthread_rwlock_t implementation.

This only affects C++14, so I'd like to commit it to trunk and the 4.9
branch.

commit 9622a4b4672ba14cefec2ffae5cf0a2c91f5f5ae
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Apr 2 19:50:50 2015 +0100

    	* include/std/shared_mutex (shared_timed_mutex): Add comments to
    	explain the logic.
    	(_M_n_readers): Rename to _S_n_readers.
    	(_M_write_entered, _M_readers): New convenience functions.
    	(lock, lock_shared, try_lock_shared, unlock_shared): Use convenience
    	functions. Use predicates with condition variables. Simplify bitwise
    	operations.
    	(try_lock_for, try_shared_lock_for): Convert duration to time_point
    	and call try_lock_until or try_shared_lock_until respectively.
    	(try_lock_until, try_shared_lock_until): Wait on the condition
    	variables until the specified time passes.
    	* testsuite/30_threads/shared_timed_mutex/try_lock/3.cc: New.

diff --git a/libstdc++-v3/include/std/shared_mutex b/libstdc++-v3/include/std/shared_mutex
index ab1b45b..7391f11 100644
--- a/libstdc++-v3/include/std/shared_mutex
+++ b/libstdc++-v3/include/std/shared_mutex
@@ -268,7 +268,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 #else // ! _GLIBCXX_USE_PTHREAD_RWLOCK_T
 
+    // Must use the same clock as condition_variable
+    typedef chrono::system_clock	__clock_t;
+
 #if _GTHREAD_USE_MUTEX_TIMEDLOCK
+    // Can't use std::timed_mutex with std::condition_variable, so define
+    // a new timed mutex type that derives from std::mutex.
     struct _Mutex : mutex, __timed_mutex_impl<_Mutex>
     {
       template<typename _Rep, typename _Period>
@@ -285,16 +290,44 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     typedef mutex _Mutex;
 #endif
 
-    // Based on Howard Hinnant's reference implementation from N2406
-
+    // Based on Howard Hinnant's reference implementation from N2406.
+
+    // The high bit of _M_state is the write-entered flag which is set to
+    // indicate a writer has taken the lock or is queuing to take the lock.
+    // The remaining bits are the count of reader locks.
+    //
+    // To take a reader lock block on gate1 while the write-entered flag is
+    // set or the maximum number of reader locks is held, then increment the
+    // reader lock count.
+    // To release decrement the count, then if the write-entered flag is set
+    // and the count is zero then signal gate2 to wake a queued writer,
+    // otherwise if the maximum number of reader locks was held signal gate1
+    // to wake a reader.
+    //
+    // To take a writer lock block on gate1 while the write-entered flag is
+    // set, then set the write-entered flag to start queueing, then block on
+    // gate2 while the number of reader locks is non-zero.
+    // To release unset the write-entered flag and signal gate1 to wake all
+    // blocked readers and writers.
+
+    // Only locked when accessing _M_state or waiting on condition variables.
     _Mutex		_M_mut;
+    // Used to block while write-entered is set or reader count at maximum.
     condition_variable	_M_gate1;
+    // Used to block queued writers while reader count is non-zero.
     condition_variable	_M_gate2;
+    // The write-entered flag and reader count.
     unsigned		_M_state;
 
     static constexpr unsigned _S_write_entered
       = 1U << (sizeof(unsigned)*__CHAR_BIT__ - 1);
-    static constexpr unsigned _M_n_readers = ~_S_write_entered;
+    static constexpr unsigned _S_n_readers = ~_S_write_entered;
+
+    // Test whether the write-entered flag is set. _M_mut must be locked.
+    bool _M_write_entered() const { return _M_state & _S_write_entered; }
+
+    // The number of reader locks currently held. _M_mut must be locked.
+    unsigned _M_readers() const { return _M_state & _S_n_readers; }
 
   public:
     shared_timed_mutex() : _M_state(0) {}
@@ -313,11 +346,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     lock()
     {
       unique_lock<mutex> __lk(_M_mut);
-      while (_M_state & _S_write_entered)
-	_M_gate1.wait(__lk);
+      _M_gate1.wait(__lk, [=]{ return !_M_write_entered(); });
       _M_state |= _S_write_entered;
-      while (_M_state & _M_n_readers)
-	_M_gate2.wait(__lk);
+      _M_gate2.wait(__lk, [=]{ return _M_readers() == 0; });
     }
 
     bool
@@ -337,26 +368,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       bool
       try_lock_for(const chrono::duration<_Rep, _Period>& __rel_time)
       {
-	unique_lock<_Mutex> __lk(_M_mut, __rel_time);
-	if (__lk.owns_lock() && _M_state == 0)
-	  {
-	    _M_state = _S_write_entered;
-	    return true;
-	  }
-	return false;
+	return try_lock_until(__clock_t::now() + __rel_time);
       }
 
     template<typename _Clock, typename _Duration>
       bool
       try_lock_until(const chrono::time_point<_Clock, _Duration>& __abs_time)
       {
-	unique_lock<_Mutex> __lk(_M_mut, __abs_time);
-	if (__lk.owns_lock() && _M_state == 0)
+	if (!_M_mut.try_lock_until(__abs_time))
+	  return false;
+	unique_lock<mutex> __lk(_M_mut, adopt_lock);
+	if (!_M_gate1.wait_until(__lk, __abs_time,
+				 [=]{ return !_M_write_entered(); }))
 	  {
-	    _M_state = _S_write_entered;
-	    return true;
+	    return false;
 	  }
-	return false;
+	_M_state |= _S_write_entered;
+	if (!_M_gate2.wait_until(__lk, __abs_time,
+				 [=]{ return _M_readers() == 0; }))
+	  {
+	    _M_state ^= _S_write_entered;
+	    _M_gate1.notify_all();
+	    return false;
+	  }
+	return true;
       }
 #endif
 
@@ -364,7 +399,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     unlock()
     {
       {
-	lock_guard<_Mutex> __lk(_M_mut);
+	lock_guard<mutex> __lk(_M_mut);
 	_M_state = 0;
       }
       _M_gate1.notify_all();
@@ -376,27 +411,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     lock_shared()
     {
       unique_lock<mutex> __lk(_M_mut);
-      while ((_M_state & _S_write_entered)
-	  || (_M_state & _M_n_readers) == _M_n_readers)
-	{
-	  _M_gate1.wait(__lk);
-	}
-      unsigned __num_readers = (_M_state & _M_n_readers) + 1;
-      _M_state &= ~_M_n_readers;
-      _M_state |= __num_readers;
+      _M_gate1.wait(__lk, [=]{ return _M_state < _S_n_readers; });
+      ++_M_state;
     }
 
     bool
     try_lock_shared()
     {
-      unique_lock<_Mutex> __lk(_M_mut, try_to_lock);
-      unsigned __num_readers = _M_state & _M_n_readers;
-      if (__lk.owns_lock() && !(_M_state & _S_write_entered)
-	  && __num_readers != _M_n_readers)
+      unique_lock<mutex> __lk(_M_mut, try_to_lock);
+      if (!__lk.owns_lock())
+	return false;
+      if (_M_state < _S_n_readers)
 	{
-	  ++__num_readers;
-	  _M_state &= ~_M_n_readers;
-	  _M_state |= __num_readers;
+	  ++_M_state;
 	  return true;
 	}
       return false;
@@ -407,20 +434,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       bool
       try_lock_shared_for(const chrono::duration<_Rep, _Period>& __rel_time)
       {
-	unique_lock<_Mutex> __lk(_M_mut, __rel_time);
-	if (__lk.owns_lock())
-	  {
-	    unsigned __num_readers = _M_state & _M_n_readers;
-	    if (!(_M_state & _S_write_entered)
-		&& __num_readers != _M_n_readers)
-	      {
-		++__num_readers;
-		_M_state &= ~_M_n_readers;
-		_M_state |= __num_readers;
-		return true;
-	      }
-	  }
-	return false;
+	return try_lock_shared_until(__clock_t::now() + __rel_time);
       }
 
     template <typename _Clock, typename _Duration>
@@ -428,38 +442,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       try_lock_shared_until(const chrono::time_point<_Clock,
 						     _Duration>& __abs_time)
       {
-	unique_lock<_Mutex> __lk(_M_mut, __abs_time);
-	if (__lk.owns_lock())
+	if (!_M_mut.try_lock_until(__abs_time))
+	  return false;
+	unique_lock<mutex> __lk(_M_mut, adopt_lock);
+	if (!_M_gate1.wait_until(__lk, __abs_time,
+				 [=]{ return _M_state < _S_n_readers; }))
 	  {
-	    unsigned __num_readers = _M_state & _M_n_readers;
-	    if (!(_M_state & _S_write_entered)
-		&& __num_readers != _M_n_readers)
-	      {
-		++__num_readers;
-		_M_state &= ~_M_n_readers;
-		_M_state |= __num_readers;
-		return true;
-	      }
+	    return false;
 	  }
-	return false;
+	++_M_state;
+	return true;
       }
 #endif
 
     void
     unlock_shared()
     {
-      lock_guard<_Mutex> __lk(_M_mut);
-      unsigned __num_readers = (_M_state & _M_n_readers) - 1;
-      _M_state &= ~_M_n_readers;
-      _M_state |= __num_readers;
-      if (_M_state & _S_write_entered)
+      lock_guard<mutex> __lk(_M_mut);
+      auto __prev = _M_state--;
+      if (_M_write_entered())
 	{
-	  if (__num_readers == 0)
+	  if (_M_readers() == 0)
 	    _M_gate2.notify_one();
 	}
       else
 	{
-	  if (__num_readers == _M_n_readers - 1)
+	  if (__prev == _S_n_readers)
 	    _M_gate1.notify_one();
 	}
     }
diff --git a/libstdc++-v3/testsuite/30_threads/shared_timed_mutex/try_lock/3.cc b/libstdc++-v3/testsuite/30_threads/shared_timed_mutex/try_lock/3.cc
new file mode 100644
index 0000000..e9f728e
--- /dev/null
+++ b/libstdc++-v3/testsuite/30_threads/shared_timed_mutex/try_lock/3.cc
@@ -0,0 +1,75 @@
+// { dg-do run { target *-*-freebsd* *-*-dragonfly* *-*-netbsd* *-*-linux* *-*-solaris* *-*-cygwin *-*-darwin* powerpc-ibm-aix* } }
+// { dg-options " -std=gnu++14 -pthread" { target *-*-freebsd* *-*-dragonfly* *-*-netbsd* *-*-linux* powerpc-ibm-aix* } }
+// { dg-options " -std=gnu++14 -pthreads" { target *-*-solaris* } }
+// { dg-options " -std=gnu++14 " { target *-*-cygwin *-*-darwin* } }
+// { dg-require-cstdint "" }
+// { dg-require-gthreads "" }
+
+// Copyright (C) 2013-2015 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 <shared_mutex>
+#include <thread>
+#include <system_error>
+#include <testsuite_hooks.h>
+
+int main()
+{
+  bool test __attribute__((unused)) = true;
+  typedef std::shared_timed_mutex mutex_type;
+
+  try
+    {
+      mutex_type m;
+      m.lock();
+      bool b;
+
+      std::thread t([&] {
+        try
+          {
+            using namespace std::chrono;
+            auto timeout = 100ms;
+            auto start = system_clock::now();
+            b = m.try_lock_for(timeout);
+            auto t = system_clock::now() - start;
+            VERIFY( !b );
+            VERIFY( t >= timeout );
+
+            start = system_clock::now();
+            b = m.try_lock_until(start + timeout);
+            t = system_clock::now() - start;
+            VERIFY( !b );
+            VERIFY( t >= timeout );
+          }
+        catch (const std::system_error& e)
+          {
+            VERIFY( false );
+          }
+      });
+      t.join();
+      m.unlock();
+    }
+  catch (const std::system_error& e)
+    {
+      VERIFY( false );
+    }
+  catch (...)
+    {
+      VERIFY( false );
+    }
+}