Logo ROOT  
Reference Guide
TReentrantRWLock.cxx
Go to the documentation of this file.
1// @(#)root/thread:$Id$
2// Authors: Enric Tejedor CERN 12/09/2016
3// Philippe Canal FNAL 12/09/2016
4
5/*************************************************************************
6 * Copyright (C) 1995-2016, Rene Brun and Fons Rademakers. *
7 * All rights reserved. *
8 * *
9 * For the licensing terms see $ROOTSYS/LICENSE. *
10 * For the list of contributors see $ROOTSYS/README/CREDITS. *
11 *************************************************************************/
12
13/** \class TReentrantRWLock
14 \brief An implementation of a reentrant read-write lock with a
15 configurable internal mutex/lock (default Spin Lock).
16
17This class provides an implementation of a reentrant read-write lock
18that uses an internal lock and a condition variable to synchronize
19readers and writers when necessary.
20
21The implementation allows a single reader to take the write lock without
22releasing the reader lock. It also allows the writer to take a read lock.
23In other word, the lock is re-entrant for both reading and writing.
24
25The implementation tries to make faster the scenario when readers come
26and go but there is no writer. In that case, readers will not pay the
27price of taking the internal spin lock.
28
29Moreover, this RW lock tries to be fair with writers, giving them the
30possibility to claim the lock and wait for only the remaining readers,
31thus preventing starvation.
32*/
33
35#include "ROOT/TSpinMutex.hxx"
36#include "TMutex.h"
37#include "TError.h"
38#include <assert.h>
39
40using namespace ROOT;
41
42#ifdef NDEBUG
43# define R__MAYBE_AssertReadCountLocIsFromCurrentThread(READERSCOUNTLOC)
44#else
45# define R__MAYBE_AssertReadCountLocIsFromCurrentThread(READERSCOUNTLOC) \
46 AssertReadCountLocIsFromCurrentThread(READERSCOUNTLOC)
47#endif
48
49Internal::UniqueLockRecurseCount::UniqueLockRecurseCount()
50{
51 static bool singleton = false;
52 if (singleton) {
53 ::Fatal("UniqueLockRecurseCount Ctor", "Only one TReentrantRWLock using a UniqueLockRecurseCount is allowed.");
54 }
55 singleton = true;
56}
57
58
59////////////////////////////////////////////////////////////////////////////
60/// Acquire the lock in read mode.
61template <typename MutexT, typename RecurseCountsT>
63{
64 ++fReaderReservation;
65
66 // if (fReaders == std::numeric_limits<decltype(fReaders)>::max()) {
67 // ::Fatal("TRWSpinLock::WriteLock", "Too many recursions in TRWSpinLock!");
68 // }
69
70 auto local = fRecurseCounts.GetLocal();
71
72 TVirtualRWMutex::Hint_t *hint = nullptr;
73
74 if (!fWriter) {
75 // There is no writer, go freely to the critical section
76 ++fReaders;
77 --fReaderReservation;
78
79 hint = fRecurseCounts.IncrementReadCount(local, fMutex);
80
81 } else if (fRecurseCounts.IsCurrentWriter(local)) {
82
83 --fReaderReservation;
84 // This can run concurrently with another thread trying to get
85 // the read lock and ending up in the next section ("Wait for writers, if any")
86 // which need to also get the local readers count and thus can
87 // modify the map.
88 hint = fRecurseCounts.IncrementReadCount(local, fMutex);
89 ++fReaders;
90
91 } else {
92 // A writer claimed the RW lock, we will need to wait on the
93 // internal lock
94 --fReaderReservation;
95
96 std::unique_lock<MutexT> lock(fMutex);
97
98 // Wait for writers, if any
99 if (fWriter && fRecurseCounts.IsNotCurrentWriter(local)) {
100 auto readerCount = fRecurseCounts.GetLocalReadersCount(local);
101 if (readerCount == 0)
102 fCond.wait(lock, [this] { return !fWriter; });
103 // else
104 // There is a writer **but** we have outstanding readers
105 // locks, this must mean that the writer is actually
106 // waiting on this thread to release its read locks.
107 // This can be done in only two ways:
108 // * request the writer lock
109 // * release the reader lock
110 // Either way, this thread needs to proceed to
111 // be able to reach a point whether it does one
112 // of the two.
113 }
114
115 hint = fRecurseCounts.IncrementReadCount(local);
116
117 // This RW lock now belongs to the readers
118 ++fReaders;
119
120 lock.unlock();
121 }
122
123 return hint;
124}
125
126//////////////////////////////////////////////////////////////////////////
127/// Release the lock in read mode.
128template <typename MutexT, typename RecurseCountsT>
130{
131 size_t *localReaderCount;
132 if (!hint) {
133 // This should be very rare.
134 auto local = fRecurseCounts.GetLocal();
135 std::lock_guard<MutexT> lock(fMutex);
136 localReaderCount = &(fRecurseCounts.GetLocalReadersCount(local));
137 } else {
138 localReaderCount = reinterpret_cast<size_t*>(hint);
139 }
140
141 --fReaders;
142 if (fWriterReservation && fReaders == 0) {
143 // We still need to lock here to prevent interleaving with a writer
144 std::lock_guard<MutexT> lock(fMutex);
145
146 --(*localReaderCount);
147
148 // Make sure you wake up a writer, if any
149 // Note: spurrious wakeups are okay, fReaders
150 // will be checked again in WriteLock
151 fCond.notify_all();
152 } else {
153
154 --(*localReaderCount);
155 }
156}
157
158//////////////////////////////////////////////////////////////////////////
159/// Acquire the lock in write mode.
160template <typename MutexT, typename RecurseCountsT>
162{
163 ++fWriterReservation;
164
165 std::unique_lock<MutexT> lock(fMutex);
166
167 auto local = fRecurseCounts.GetLocal();
168
169 // Release this thread's reader lock(s)
170 auto &readerCount = fRecurseCounts.GetLocalReadersCount(local);
171 TVirtualRWMutex::Hint_t *hint = reinterpret_cast<TVirtualRWMutex::Hint_t *>(&readerCount);
172
173 fReaders -= readerCount;
174
175 // Wait for other writers, if any
176 if (fWriter && fRecurseCounts.IsNotCurrentWriter(local)) {
177 if (readerCount && fReaders == 0) {
178 // we decrease fReaders to zero, let's wake up the
179 // other writer.
180 fCond.notify_all();
182 fCond.wait(lock, [this] { return !fWriter; });
184
185 // Claim the lock for this writer
186 fWriter = true;
187 fRecurseCounts.SetIsWriter(local);
188
189 // Wait until all reader reservations finish
190 while (fReaderReservation) {
191 };
192
193 // Wait for remaining readers
194 fCond.wait(lock, [this] { return fReaders == 0; });
195
196 // Restore this thread's reader lock(s)
197 fReaders += readerCount;
198
199 --fWriterReservation;
200
201 lock.unlock();
202
203 return hint;
204}
205
206//////////////////////////////////////////////////////////////////////////
207/// Release the lock in write mode.
208template <typename MutexT, typename RecurseCountsT>
210{
211 // We need to lock here to prevent interleaving with a reader
212 std::lock_guard<MutexT> lock(fMutex);
213
214 if (!fWriter || fRecurseCounts.fWriteRecurse == 0) {
215 Error("TReentrantRWLock::WriteUnLock", "Write lock already released for %p", this);
216 return;
217 }
218
219 fRecurseCounts.DecrementWriteCount();
220
221 if (!fRecurseCounts.fWriteRecurse) {
222 fWriter = false;
223
224 auto local = fRecurseCounts.GetLocal();
225 fRecurseCounts.ResetIsWriter(local);
226
227 // Notify all potential readers/writers that are waiting
228 fCond.notify_all();
229 }
230}
231namespace {
232template <typename MutexT, typename RecurseCountsT>
233struct TReentrantRWLockState: public TVirtualRWMutex::State {
234 size_t *fReadersCountLoc = nullptr;
235 int fReadersCount = 0;
236 size_t fWriteRecurse = 0;
237};
238
239template <typename MutexT, typename RecurseCountsT>
240struct TReentrantRWLockStateDelta: public TVirtualRWMutex::StateDelta {
241 size_t *fReadersCountLoc = nullptr;
242 int fDeltaReadersCount = 0;
243 int fDeltaWriteRecurse = 0;
244};
245}
246
247//////////////////////////////////////////////////////////////////////////
248/// Get the lock state before the most recent write lock was taken.
249
250template <typename MutexT, typename RecurseCountsT>
251std::unique_ptr<TVirtualRWMutex::State>
253{
254 using State_t = TReentrantRWLockState<MutexT, RecurseCountsT>;
255
256 if (!fWriter) {
257 Error("TReentrantRWLock::GetStateBefore()", "Must be write locked!");
258 return nullptr;
259 }
260
261 auto local = fRecurseCounts.GetLocal();
262 if (fRecurseCounts.IsNotCurrentWriter(local)) {
263 Error("TReentrantRWLock::GetStateBefore()", "Not holding the write lock!");
264 return nullptr;
265 }
266
267 std::unique_ptr<State_t> pState(new State_t);
268 {
269 std::lock_guard<MutexT> lock(fMutex);
270 pState->fReadersCountLoc = &(fRecurseCounts.GetLocalReadersCount(local));
271 }
272 pState->fReadersCount = *(pState->fReadersCountLoc);
273 // *Before* the most recent write lock (that is required by GetStateBefore())
274 // was taken, the write recursion level was `fWriteRecurse - 1`
275 pState->fWriteRecurse = fRecurseCounts.fWriteRecurse - 1;
276
277#if __GNUC__ < 7
278 // older version of gcc can not convert implicitly from
279 // unique_ptr of derived to unique_ptr of base
280 using BaseState_t = TVirtualRWMutex::State;
281 return std::unique_ptr<BaseState_t>(pState.release());
282#else
283 return pState;
284#endif
285}
286
287//////////////////////////////////////////////////////////////////////////
288/// Rewind to an earlier mutex state, returning the delta.
289
290template <typename MutexT, typename RecurseCountsT>
291std::unique_ptr<TVirtualRWMutex::StateDelta>
293 using State_t = TReentrantRWLockState<MutexT, RecurseCountsT>;
294 using StateDelta_t = TReentrantRWLockStateDelta<MutexT, RecurseCountsT>;
295 auto& typedState = static_cast<const State_t&>(earlierState);
296
297 R__MAYBE_AssertReadCountLocIsFromCurrentThread(typedState.fReadersCountLoc);
298
299 std::unique_ptr<StateDelta_t> pStateDelta(new StateDelta_t);
300 pStateDelta->fReadersCountLoc = typedState.fReadersCountLoc;
301 pStateDelta->fDeltaReadersCount = *typedState.fReadersCountLoc - typedState.fReadersCount;
302 pStateDelta->fDeltaWriteRecurse = fRecurseCounts.fWriteRecurse - typedState.fWriteRecurse;
303
304 if (pStateDelta->fDeltaReadersCount < 0) {
305 Error("TReentrantRWLock::Rewind", "Inconsistent read lock count!");
306 return nullptr;
307 }
308
309 if (pStateDelta->fDeltaWriteRecurse < 0) {
310 Error("TReentrantRWLock::Rewind", "Inconsistent write lock count!");
311 return nullptr;
312 }
313
314 auto hint = reinterpret_cast<TVirtualRWMutex::Hint_t *>(typedState.fReadersCountLoc);
315 if (pStateDelta->fDeltaWriteRecurse != 0) {
316 // Claim a recurse-state +1 to be able to call Unlock() below.
317 fRecurseCounts.fWriteRecurse = typedState.fWriteRecurse + 1;
318 // Release this thread's write lock
319 WriteUnLock(hint);
320 }
321
322 if (pStateDelta->fDeltaReadersCount != 0) {
323 // Claim a recurse-state +1 to be able to call Unlock() below.
324 *typedState.fReadersCountLoc = typedState.fReadersCount + 1;
325 fReaders = typedState.fReadersCount + 1;
326 // Release this thread's reader lock(s)
327 ReadUnLock(hint);
328 }
329 // else earlierState and *this are identical!
330
331 return std::unique_ptr<TVirtualRWMutex::StateDelta>(std::move(pStateDelta));
332}
333
334//////////////////////////////////////////////////////////////////////////
335/// Re-apply a delta.
336
337template <typename MutexT, typename RecurseCountsT>
338void TReentrantRWLock<MutexT, RecurseCountsT>::Apply(std::unique_ptr<StateDelta> &&state) {
339 if (!state) {
340 Error("TReentrantRWLock::Apply", "Cannot apply empty delta!");
341 return;
342 }
343
344 using StateDelta_t = TReentrantRWLockStateDelta<MutexT, RecurseCountsT>;
345 const StateDelta_t* typedDelta = static_cast<const StateDelta_t*>(state.get());
346
347 if (typedDelta->fDeltaWriteRecurse < 0) {
348 Error("TReentrantRWLock::Apply", "Negative write recurse count delta!");
349 return;
350 }
351 if (typedDelta->fDeltaReadersCount < 0) {
352 Error("TReentrantRWLock::Apply", "Negative read count delta!");
353 return;
354 }
355 R__MAYBE_AssertReadCountLocIsFromCurrentThread(typedDelta->fReadersCountLoc);
356
357 if (typedDelta->fDeltaWriteRecurse != 0) {
358 WriteLock();
359 fRecurseCounts.fWriteRecurse += typedDelta->fDeltaWriteRecurse - 1;
360 }
361 if (typedDelta->fDeltaReadersCount != 0) {
362 ReadLock();
363 // "- 1" due to ReadLock() above.
364 fReaders += typedDelta->fDeltaReadersCount - 1;
365 *typedDelta->fReadersCountLoc += typedDelta->fDeltaReadersCount - 1;
366 }
367}
368
369//////////////////////////////////////////////////////////////////////////
370/// Assert that presumedLocalReadersCount really matches the local read count.
371/// Print an error message if not.
372
373template <typename MutexT, typename RecurseCountsT>
375{
376 auto local = fRecurseCounts.GetLocal();
377 size_t* localReadersCount;
378 {
379 std::lock_guard<MutexT> lock(fMutex);
380 localReadersCount = &(fRecurseCounts.GetLocalReadersCount(local));
381 }
382 if (localReadersCount != presumedLocalReadersCount) {
383 Error("TReentrantRWLock::AssertReadCountLocIsFromCurrentThread", "ReadersCount is from different thread!");
384 }
385}
386
387
388namespace ROOT {
392
396}
void Error(const char *location, const char *msgfmt,...)
void Fatal(const char *location, const char *msgfmt,...)
#define R__MAYBE_AssertReadCountLocIsFromCurrentThread(READERSCOUNTLOC)
void WriteUnLock(TVirtualRWMutex::Hint_t *)
Release the lock in write mode.
std::unique_ptr< StateDelta > Rewind(const State &earlierState)
Rewind to an earlier mutex state, returning the delta.
TVirtualRWMutex::Hint_t * ReadLock()
Acquire the lock in read mode.
TVirtualRWMutex::Hint_t * WriteLock()
Acquire the lock in write mode.
void ReadUnLock(TVirtualRWMutex::Hint_t *)
Release the lock in read mode.
void AssertReadCountLocIsFromCurrentThread(const size_t *presumedLocalReadersCount)
Assert that presumedLocalReadersCount really matches the local read count.
std::unique_ptr< State > GetStateBefore()
Get the lock state before the most recent write lock was taken.
void Apply(std::unique_ptr< StateDelta > &&delta)
Re-apply a delta.
VSD Structures.
Definition: StringConv.hxx:21
State as returned by GetStateDelta() that can be passed to Restore()
Earlier lock state as returned by GetState() that can be passed to Restore()