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

[Torvald Riegel <triegel@redhat.com>]

There is an correctness issue related to mutex destruction.  The added
documentation is a good start, but I'd still add some more for the
complicated pieces of reasoning.  Details inline below.

On Tue, 2015-04-07 at 15:28 +0100, Jonathan Wakely wrote:
> 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

I think this is easier to parse if you add a comma: "To take a reader
lock, block ...".  Same for other sentences below.

> +    // 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.

Perhaps it would also be useful to have a sentence on how writers and
readers are prioritized (e.g., writers preferred if readers already hold
the lock, all are equal when writer unlocks, ...).

> +
> +    // 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;

Rename this to _S_max_readers or such?

> +
> +    // 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);

Add something like this:?

// We first wait until we acquire the writer-part of the lock, and
// then wait until no readers hold the lock anymore.

> +      _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;

I think a non-timed acquisition for the internal lock should be fine.
The internal lock is supposed to protect critical sections of finite
(and short) length, and the condvars also don't do acquisition with time
outs.

> +       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; }))
> +         {

I'd add a comment saying that you have to mimic a full write unlock, so
that's why those steps are necessary.

> +           _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();

The notification must be *inside* of the critical section.  Otherwise,
you're violating the mutex destruction requirements (see 30.4.1.3.1p3):
After you set _M_state to 0 and release _M_mut, another thread can go
it, acquire, assume it's the last one to own the mutex if that's what
the program ensures, and destroy; then, destruction would be concurrent
with the call to notify_all.  (Perhaps check other wake-ups / unlocks as
well.)

> @@ -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;

See above.

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

I think this needs documentation why we can't miss a wake-up in case
_M_write_entered is true and we have a reader overflow.  I think it's
not quite obvious why this works.
If there is a writer we don't notify gate1 in unlock_shared(), so there
is potential to "loose" that information in interleavings with a writer.
If the writer acquires the lock eventually, things will work because
then, the writer will do the gate1 notification in its unlock path.  If
the writer times out, it still does the gate1 notification regardless of
the the number of readers registered (because if there is no reader, it
will never time out but simply acquire the lock).  Thus, when there is a
writer, the writer becomes responsible for gate1 notification, and
things work.