Logo ROOT   6.14/05
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 
17 This class provides an implementation of a reentrant read-write lock
18 that uses an internal lock and a condition variable to synchronize
19 readers and writers when necessary.
20 
21 The implementation allows a single reader to take the write lock without
22 releasing the reader lock. It also allows the writer to take a read lock.
23 In other word, the lock is re-entrant for both reading and writing.
24 
25 The implementation tries to make faster the scenario when readers come
26 and go but there is no writer. In that case, readers will not pay the
27 price of taking the internal spin lock.
28 
29 Moreover, this RW lock tries to be fair with writers, giving them the
30 possibility to claim the lock and wait for only the remaining readers,
31 thus preventing starvation.
32 */
33 
35 #include "ROOT/TSpinMutex.hxx"
36 #include "TMutex.h"
37 #include "TError.h"
38 #include <assert.h>
39 
40 using 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 
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.
61 template <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.
128 template <typename MutexT, typename RecurseCountsT>
129 void TReentrantRWLock<MutexT, RecurseCountsT>::ReadUnLock(TVirtualRWMutex::Hint_t *hint)
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.
160 template <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();
181  }
182  fCond.wait(lock, [this] { return !fWriter; });
183  }
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.
208 template <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 }
231 namespace {
232 template <typename MutexT, typename RecurseCountsT>
233 struct TReentrantRWLockState: public TVirtualRWMutex::State {
234  size_t *fReadersCountLoc = nullptr;
235  int fReadersCount = 0;
236  size_t fWriteRecurse = 0;
237 };
238 
239 template <typename MutexT, typename RecurseCountsT>
240 struct 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 
250 template <typename MutexT, typename RecurseCountsT>
251 std::unique_ptr<TVirtualRWMutex::State>
253 {
254  using State_t = TReentrantRWLockState<MutexT, RecurseCountsT>;
255  if (!fWriter) {
256  Error("TReentrantRWLock::GetStateBefore()", "Must be write locked!");
257  return nullptr;
258  }
259 
260  auto local = fRecurseCounts.GetLocal();
261  if (fRecurseCounts.IsNotCurrentWriter(local)) {
262  Error("TReentrantRWLock::GetStateBefore()", "Not holding the write lock!");
263  return nullptr;
264  }
265 
266  std::unique_ptr<State_t> pState(new State_t);
267  {
268  std::lock_guard<MutexT> lock(fMutex);
269  pState->fReadersCountLoc = &(fRecurseCounts.GetLocalReadersCount(local));
270  }
271  pState->fReadersCount = *(pState->fReadersCountLoc);
272  // *Before* the most recent write lock (that is required by GetStateBefore())
273  // was taken, the write recursion level was `fWriteRecurse - 1`
274  pState->fWriteRecurse = fRecurseCounts.fWriteRecurse - 1;
275 
276  return std::move(pState);
277 }
278 
279 //////////////////////////////////////////////////////////////////////////
280 /// Rewind to an earlier mutex state, returning the delta.
281 
282 template <typename MutexT, typename RecurseCountsT>
283 std::unique_ptr<TVirtualRWMutex::StateDelta>
285  using State_t = TReentrantRWLockState<MutexT, RecurseCountsT>;
286  using StateDelta_t = TReentrantRWLockStateDelta<MutexT, RecurseCountsT>;
287  auto& typedState = static_cast<const State_t&>(earlierState);
288 
289  R__MAYBE_AssertReadCountLocIsFromCurrentThread(typedState.fReadersCountLoc);
290 
291  std::unique_ptr<StateDelta_t> pStateDelta(new StateDelta_t);
292  pStateDelta->fReadersCountLoc = typedState.fReadersCountLoc;
293  pStateDelta->fDeltaReadersCount = *typedState.fReadersCountLoc - typedState.fReadersCount;
294  pStateDelta->fDeltaWriteRecurse = fRecurseCounts.fWriteRecurse - typedState.fWriteRecurse;
295 
296  if (pStateDelta->fDeltaReadersCount < 0) {
297  Error("TReentrantRWLock::Rewind", "Inconsistent read lock count!");
298  return nullptr;
299  }
300 
301  if (pStateDelta->fDeltaWriteRecurse < 0) {
302  Error("TReentrantRWLock::Rewind", "Inconsistent write lock count!");
303  return nullptr;
304  }
305 
306  auto hint = reinterpret_cast<TVirtualRWMutex::Hint_t *>(typedState.fReadersCountLoc);
307  if (pStateDelta->fDeltaWriteRecurse != 0) {
308  // Claim a recurse-state +1 to be able to call Unlock() below.
309  fRecurseCounts.fWriteRecurse = typedState.fWriteRecurse + 1;
310  // Release this thread's write lock
311  WriteUnLock(hint);
312  }
313 
314  if (pStateDelta->fDeltaReadersCount != 0) {
315  // Claim a recurse-state +1 to be able to call Unlock() below.
316  *typedState.fReadersCountLoc = typedState.fReadersCount + 1;
317  fReaders = typedState.fReadersCount + 1;
318  // Release this thread's reader lock(s)
319  ReadUnLock(hint);
320  }
321  // else earlierState and *this are identical!
322 
323  return std::unique_ptr<TVirtualRWMutex::StateDelta>(std::move(pStateDelta));
324 }
325 
326 //////////////////////////////////////////////////////////////////////////
327 /// Re-apply a delta.
328 
329 template <typename MutexT, typename RecurseCountsT>
330 void TReentrantRWLock<MutexT, RecurseCountsT>::Apply(std::unique_ptr<StateDelta> &&state) {
331  if (!state) {
332  Error("TReentrantRWLock::Apply", "Cannot apply empty delta!");
333  return;
334  }
335 
336  using StateDelta_t = TReentrantRWLockStateDelta<MutexT, RecurseCountsT>;
337  const StateDelta_t* typedDelta = static_cast<const StateDelta_t*>(state.get());
338 
339  if (typedDelta->fDeltaWriteRecurse < 0) {
340  Error("TReentrantRWLock::Apply", "Negative write recurse count delta!");
341  return;
342  }
343  if (typedDelta->fDeltaReadersCount < 0) {
344  Error("TReentrantRWLock::Apply", "Negative read count delta!");
345  return;
346  }
347  R__MAYBE_AssertReadCountLocIsFromCurrentThread(typedDelta->fReadersCountLoc);
348 
349  if (typedDelta->fDeltaWriteRecurse != 0) {
350  WriteLock();
351  fRecurseCounts.fWriteRecurse += typedDelta->fDeltaWriteRecurse - 1;
352  }
353  if (typedDelta->fDeltaReadersCount != 0) {
354  ReadLock();
355  // "- 1" due to ReadLock() above.
356  fReaders += typedDelta->fDeltaReadersCount - 1;
357  *typedDelta->fReadersCountLoc += typedDelta->fDeltaReadersCount - 1;
358  }
359 }
360 
361 //////////////////////////////////////////////////////////////////////////
362 /// Assert that presumedLocalReadersCount really matches the local read count.
363 /// Print an error message if not.
364 
365 template <typename MutexT, typename RecurseCountsT>
367 {
368  auto local = fRecurseCounts.GetLocal();
369  size_t* localReadersCount;
370  {
371  std::lock_guard<MutexT> lock(fMutex);
372  localReadersCount = &(fRecurseCounts.GetLocalReadersCount(local));
373  }
374  if (localReadersCount != presumedLocalReadersCount) {
375  Error("TReentrantRWLock::AssertReadCountLocIsFromCurrentThread", "ReadersCount is from different thread!");
376  }
377 }
378 
379 
380 namespace ROOT {
384 
387 }
void ReadUnLock(TVirtualRWMutex::Hint_t *)
Release the lock in read mode.
Namespace for new ROOT classes and functions.
Definition: StringConv.hxx:21
void Fatal(const char *location, const char *msgfmt,...)
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 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.
size_t fWriteRecurse
! Number of re-entry in the lock by the same thread.
void Apply(std::unique_ptr< StateDelta > &&delta)
Re-apply a delta.
#define R__MAYBE_AssertReadCountLocIsFromCurrentThread(READERSCOUNTLOC)
State as returned by GetStateDelta() that can be passed to Restore()
TVirtualRWMutex::Hint_t * ReadLock()
Acquire the lock in read mode.
TVirtualRWMutex::Hint_t * WriteLock()
Acquire the lock in write mode.
Earlier lock state as returned by GetState() that can be passed to Restore()
void Error(ErrorHandler_t func, int code, const char *va_(fmt),...)
Write error message and call a handler, if required.