HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
spinRWMutex.h
Go to the documentation of this file.
1 //
2 // Copyright 2022 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 #ifndef PXR_BASE_TF_SPIN_RW_MUTEX_H
25 #define PXR_BASE_TF_SPIN_RW_MUTEX_H
26 
27 #include "pxr/pxr.h"
28 #include "pxr/base/tf/api.h"
29 
30 #include "pxr/base/arch/hints.h"
32 
33 #include <atomic>
34 
36 
37 /// \class TfSpinRWMutex
38 ///
39 /// This class implements a readers-writer spin lock that emphasizes throughput
40 /// when there is light contention or moderate contention dominated by readers.
41 /// Like all spin locks, significant contention performs poorly; consider a
42 /// different algorithm design or synchronization strategy in that case.
43 ///
44 /// In the best case, acquiring a read lock is an atomic add followed by a
45 /// conditional branch, and acquiring a write lock is an atomic bitwise-or
46 /// followed by a conditional branch.
47 ///
48 /// When contended by only readers, acquiring a read lock is the same: an atomic
49 /// add followed by a conditional branch. Of course the shared cache line being
50 /// concurrently read and modified will affect performance.
51 ///
52 /// In the worst case, acquiring a read lock does the atomic add and conditional
53 /// branch, but the condition shows writer activity, so the add must be undone
54 /// by a subtraction, and then the thread must wait to see no writer activity
55 /// before trying again.
56 ///
57 /// Similarly in the worst case for acquiring a write lock, the thread does the
58 /// atomic bitwise-or, but sees another active writer, and then must wait to see
59 /// no writer activity before trying again. Once the exclusive-or is done
60 /// successfully, then the writer must wait for any pending readers to clear out
61 /// before it can proceed.
62 ///
63 /// This class provides a nested TfSpinRWMutex::ScopedLock that makes it easy to
64 /// acquire locks, upgrade reader to writer, downgrade writer to reader, and
65 /// have those locks automatically release when the ScopedLock is destroyed.
66 ///
68 {
69  static constexpr int OneReader = 2;
70  static constexpr int WriterFlag = 1;
71 
72 public:
73 
74  /// Construct a mutex, initially unlocked.
75  TfSpinRWMutex() : _lockState(0) {}
76 
77  /// Scoped lock utility class. API modeled roughly after
78  /// tbb::spin_rw_mutex::scoped_lock.
79  struct ScopedLock {
80 
81  // Acquisition states.
82  static constexpr int NotAcquired = 0;
83  static constexpr int ReadAcquired = 1;
84  static constexpr int WriteAcquired = 2;
85 
86  /// Construct a scoped lock for mutex \p m and acquire either a read or
87  /// a write lock depending on \p write.
88  explicit ScopedLock(TfSpinRWMutex &m, bool write=true)
89  : _mutex(&m)
90  , _acqState(NotAcquired) {
91  Acquire(write);
92  }
93 
94  /// Construct a scoped lock not associated with a \p mutex.
95  ScopedLock() : _mutex(nullptr), _acqState(NotAcquired) {}
96 
97  /// If this scoped lock is acquired for either read or write, Release()
98  /// it.
100  Release();
101  }
102 
103  /// If the current scoped lock is acquired, Release() it, then associate
104  /// this lock with \p m and acquire either a read or a write lock,
105  /// depending on \p write.
106  void Acquire(TfSpinRWMutex &m, bool write=true) {
107  Release();
108  _mutex = &m;
109  Acquire(write);
110  }
111 
112  /// Acquire either a read or write lock on this lock's associated mutex
113  /// depending on \p write. This lock must be associated with a mutex
114  /// (typically by construction or by a call to Acquire() that takes a
115  /// mutex). This lock must not already be acquired when calling
116  /// Acquire().
117  void Acquire(bool write=true) {
118  if (write) {
119  AcquireWrite();
120  }
121  else {
122  AcquireRead();
123  }
124  }
125 
126  /// Release the currently required lock on the associated mutex. If
127  /// this lock is not currently acquired, silently do nothing.
128  void Release() {
129  switch (_acqState) {
130  default:
131  case NotAcquired:
132  break;
133  case ReadAcquired:
134  _ReleaseRead();
135  break;
136  case WriteAcquired:
137  _ReleaseWrite();
138  break;
139  };
140  }
141 
142  /// Acquire a read lock on this lock's associated mutex. This lock must
143  /// not already be acquired when calling \p AcquireRead().
144  void AcquireRead() {
145  TF_DEV_AXIOM(_acqState == NotAcquired);
146  _mutex->AcquireRead();
147  _acqState = ReadAcquired;
148  }
149 
150  /// Acquire a write lock on this lock's associated mutex. This lock
151  /// must not already be acquired when calling \p AcquireWrite().
152  void AcquireWrite() {
153  TF_DEV_AXIOM(_acqState == NotAcquired);
154  _mutex->AcquireWrite();
155  _acqState = WriteAcquired;
156  }
157 
158  /// Change this lock's acquisition state from a read lock to a write
159  /// lock. This lock must already be acquired for reading. Return true
160  /// if the upgrade occurred without releasing the read lock, false if it
161  /// was released.
163  TF_DEV_AXIOM(_acqState == ReadAcquired);
164  _acqState = WriteAcquired;
165  return _mutex->UpgradeToWriter();
166  }
167 
168  /// Change this lock's acquisition state from a write lock to a read
169  /// lock. This lock must already be acquired for writing. Return true
170  /// if the downgrade occurred without releasing the write in the
171  /// interim, false if it was released and other writers may have
172  /// intervened.
174  TF_DEV_AXIOM(_acqState == WriteAcquired);
175  _acqState = ReadAcquired;
176  return _mutex->DowngradeToReader();
177  }
178 
179  private:
180 
181  void _ReleaseRead() {
182  TF_DEV_AXIOM(_acqState == ReadAcquired);
183  _mutex->ReleaseRead();
184  _acqState = NotAcquired;
185  }
186 
187  void _ReleaseWrite() {
188  TF_DEV_AXIOM(_acqState == WriteAcquired);
189  _mutex->ReleaseWrite();
190  _acqState = NotAcquired;
191  }
192 
193  TfSpinRWMutex *_mutex;
194  int _acqState; // NotAcquired (0), ReadAcquired (1), WriteAcquired (2)
195  };
196 
197  /// Attempt to acquire a read lock on this mutex without waiting for
198  /// writers. This thread must not already hold a lock on this mutex (either
199  /// read or write). Return true if the lock is acquired, false otherwise.
200  inline bool TryAcquireRead() {
201  // Optimistically increment the reader count.
202  if (ARCH_LIKELY(!(_lockState.fetch_add(OneReader) & WriterFlag))) {
203  // We incremented the reader count and observed no writer activity,
204  // we have a read lock.
205  return true;
206  }
207 
208  // Otherwise there's writer activity. Undo the increment and return
209  // false.
210  _lockState -= OneReader;
211  return false;
212  }
213 
214  /// Acquire a read lock on this mutex. This thread must not already hold a
215  /// lock on this mutex (either read or write). Consider calling
216  /// DowngradeToReader() if this thread holds a write lock.
217  inline void AcquireRead() {
218  while (true) {
219  if (TryAcquireRead()) {
220  return;
221  }
222  // There's writer activity. Wait to see no writer activity and
223  // retry.
224  _WaitForWriter();
225  }
226  }
227 
228  /// Release this thread's read lock on this mutex.
229  inline void ReleaseRead() {
230  // Just decrement the count.
231  _lockState -= OneReader;
232  }
233 
234  /// Attempt to acquire a write lock on this mutex without waiting for other
235  /// writers. This thread must not already hold a lock on this mutex (either
236  /// read or write). Return true if the lock is acquired, false otherwise.
237  inline bool TryAcquireWrite() {
238  int state = _lockState.fetch_or(WriterFlag);
239  if (!(state & WriterFlag)) {
240  // We set the flag, wait for readers.
241  if (state != 0) {
242  // Wait for pending readers.
243  _WaitForReaders();
244  }
245  return true;
246  }
247  return false;
248  }
249 
250  /// Acquire a write lock on this mutex. This thread must not already hold a
251  /// lock on this mutex (either read or write). Consider calling
252  /// UpgradeToWriter() if this thread holds a read lock.
253  void AcquireWrite() {
254  // Attempt to acquire -- if we fail then wait to see no other writer and
255  // retry.
256  while (true) {
257  if (TryAcquireWrite()) {
258  return;
259  }
260  _WaitForWriter();
261  }
262  }
263 
264  /// Release this thread's write lock on this mutex.
265  inline void ReleaseWrite() {
266  _lockState &= ~WriterFlag;
267  }
268 
269  /// Upgrade this thread's lock on this mutex (which must be a read lock) to
270  /// a write lock. Return true if the upgrade is done "atomically" meaning
271  /// that the read lock was not released (and thus no other writer could have
272  /// acquired the lock in the interim). Return false if this lock was
273  /// released and thus another writer could have taken the lock in the
274  /// interim.
276  // This thread owns a read lock, attempt to upgrade to write lock. If
277  // we do so without an intervening writer, return true, otherwise return
278  // false.
279  bool atomic = true;
280  while (true) {
281  int state = _lockState.fetch_or(WriterFlag);
282  if (!(state & WriterFlag)) {
283  // We set the flag, release our reader count and wait for any
284  // other pending readers.
285  if (_lockState.fetch_sub(
286  OneReader) != (OneReader | WriterFlag)) {
287  _WaitForReaders();
288  }
289  return atomic;
290  }
291  // There was other writer activity -- wait for it to clear, then
292  // retry.
293  atomic = false;
294  _WaitForWriter();
295  }
296  }
297 
298  /// Downgrade this mutex, which must be locked for write by this thread, to
299  /// being locked for read by this thread. Return true if the downgrade
300  /// happened "atomically", meaning that the write lock was not released (and
301  /// thus possibly acquired by another thread). This implementation
302  /// currently always returns true.
304  // Simultaneously add a reader count and clear the writer bit by adding
305  // (OneReader-1).
306  _lockState += (OneReader-1);
307  return true;
308  }
309 
310 private:
311  friend class TfBigRWMutex;
312 
313  // Helpers for staged-acquire-write that BigRWMutex uses.
314  enum _StagedAcquireWriteState {
315  _StageNotAcquired,
316  _StageAcquiring,
317  _StageAcquired
318  };
319 
320  // This API lets TfBigRWMutex acquire a write lock step-by-step so that it
321  // can begin acquiring write locks on several mutexes without waiting
322  // serially for pending readers to complete. Call _StagedAcquireWriteStep
323  // with _StageNotAcquired initially, and save the returned value. Continue
324  // repeatedly calling _StagedAcquireWriteStep, passing the previously
325  // returned value until this function returns _StageAcquired. At this
326  // point the write lock is acquired.
327  _StagedAcquireWriteState
328  _StagedAcquireWriteStep(_StagedAcquireWriteState curState) {
329  int state;
330  switch (curState) {
331  case _StageNotAcquired:
332  state = _lockState.fetch_or(WriterFlag);
333  if (!(state & WriterFlag)) {
334  // We set the flag. If there were no readers we're done,
335  // otherwise we'll have to wait for them, next step.
336  return state == 0 ? _StageAcquired : _StageAcquiring;
337  }
338  // Other writer activity, must retry next step.
339  return _StageNotAcquired;
340  case _StageAcquiring:
341  // We have set the writer flag but must wait to see no readers.
342  _WaitForReaders();
343  return _StageAcquired;
344  case _StageAcquired:
345  default:
346  return _StageAcquired;
347  };
348  }
349 
350  TF_API void _WaitForReaders() const;
351  TF_API void _WaitForWriter() const;
352 
353  std::atomic<int> _lockState;
354 };
355 
357 
358 #endif // PXR_BASE_TF_SPIN_RW_MUTEX_H
#define ARCH_LIKELY(x)
Definition: hints.h:46
ScopedLock()
Construct a scoped lock not associated with a mutex.
Definition: spinRWMutex.h:95
bool TryAcquireWrite()
Definition: spinRWMutex.h:237
#define TF_API
Definition: api.h:40
static constexpr int ReadAcquired
Definition: spinRWMutex.h:83
bool DowngradeToReader()
Definition: spinRWMutex.h:303
void Acquire(bool write=true)
Definition: spinRWMutex.h:117
#define TF_DEV_AXIOM(cond)
void AcquireWrite()
Definition: spinRWMutex.h:253
bool UpgradeToWriter()
Definition: spinRWMutex.h:275
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1432
void AcquireRead()
Definition: spinRWMutex.h:217
bool TryAcquireRead()
Definition: spinRWMutex.h:200
TfSpinRWMutex()
Construct a mutex, initially unlocked.
Definition: spinRWMutex.h:75
static constexpr int NotAcquired
Definition: spinRWMutex.h:82
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:91
static constexpr int WriteAcquired
Definition: spinRWMutex.h:84
void ReleaseWrite()
Release this thread's write lock on this mutex.
Definition: spinRWMutex.h:265
void ReleaseRead()
Release this thread's read lock on this mutex.
Definition: spinRWMutex.h:229
ScopedLock(TfSpinRWMutex &m, bool write=true)
Definition: spinRWMutex.h:88
void Acquire(TfSpinRWMutex &m, bool write=true)
Definition: spinRWMutex.h:106