From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 45192 invoked by alias); 8 Apr 2015 16:59:41 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 45166 invoked by uid 89); 8 Apr 2015 16:59:40 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.5 required=5.0 tests=AWL,BAYES_50,SPF_HELO_PASS,SPF_PASS,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Wed, 08 Apr 2015 16:59:39 +0000 Received: from int-mx14.intmail.prod.int.phx2.redhat.com (int-mx14.intmail.prod.int.phx2.redhat.com [10.5.11.27]) by mx1.redhat.com (Postfix) with ESMTPS id DFB8A8E3F0; Wed, 8 Apr 2015 16:59:37 +0000 (UTC) Received: from [10.36.5.197] (vpn1-5-197.ams2.redhat.com [10.36.5.197]) by int-mx14.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id t38GxYsg010057; Wed, 8 Apr 2015 12:59:35 -0400 Subject: Re: [patch] Fix shared_timed_mutex::try_lock_until() et al From: Torvald Riegel To: Jonathan Wakely Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org In-Reply-To: <20150407142830.GG9755@redhat.com> References: <20150407142830.GG9755@redhat.com> Content-Type: text/plain; charset="UTF-8" Date: Wed, 08 Apr 2015 16:59:00 -0000 Message-ID: <1428512373.924.26.camel@triegel.csb> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2015-04/txt/msg00331.txt.bz2 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 > @@ -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 __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 > 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 __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 __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 __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 __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 > @@ -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 __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 __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.