HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
bigRWMutex.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_BIG_RW_MUTEX_H
25 #define PXR_BASE_TF_BIG_RW_MUTEX_H
26 
27 #include "pxr/pxr.h"
28 #include "pxr/base/tf/api.h"
29 
30 #include "pxr/base/arch/align.h"
31 #include "pxr/base/arch/hints.h"
33 #include "pxr/base/tf/hash.h"
35 
36 #include <atomic>
37 #include <memory>
38 #include <thread>
39 
41 
42 /// \class TfBigRWMutex
43 ///
44 /// This class implements a readers-writer mutex and provides a scoped lock
45 /// utility. Multiple clients may acquire a read lock simultaneously, but only
46 /// one client may hold a write lock, exclusive to all other locks.
47 ///
48 /// This class emphasizes throughput for (and is thus best used in) the case
49 /// where there are many simultaneous reader clients all concurrently taking
50 /// read locks, with clients almost never taking write locks. As such, taking a
51 /// read lock is a lightweight operation that usually does not imply much
52 /// hardware-level concurrency penalty (i.e. writes to shared cache lines).
53 /// This is done by allocating several cache-line-sized chunks of memory to
54 /// represent lock state, and readers typically only deal with a single lock
55 /// state (and therefore a single cache line). On the other hand, taking a
56 /// write lock is very expensive from a hardware concurrency point of view; it
57 /// requires atomic memory operations on every cache-line.
58 ///
59 /// To achieve good throughput under highly read-contended workloads, this class
60 /// allocates 10s of cachelines worth of state (~1 KB) to help minimize
61 /// hardware-level contention. So it is probably not appropriate to use as
62 /// (e.g.) a member variable in an object that there are likely to be many of.
63 ///
64 /// This class has been measured to show >10x throughput compared to
65 /// tbb::spin_rw_mutex, and >100x better throughput compared to
66 /// tbb::queuing_rw_mutex on reader-contention-heavy loads. The tradeoff being
67 /// the relatively large size required compared to these other classes.
68 ///
70 {
71 public:
72  // Number of different cache-line-sized lock states.
73  static constexpr unsigned NumStates = 16;
74 
75  // Lock states -- 0 means not locked, -1 means locked for write, other
76  // positive values count the number of readers locking this particular lock
77  // state object.
78  static constexpr int NotLocked = 0;
79  static constexpr int WriteLocked = -1;
80 
81  /// Construct a mutex, initially unlocked.
83 
84  /// Scoped lock utility class. API modeled after
85  /// tbb::spin_rw_mutex::scoped_lock.
86  struct ScopedLock {
87 
88  // Acquisition states: -1 means not acquired, -2 means acquired for
89  // write (exclusive lock), >= 0 indicates locked for read, and the value
90  // indicates which lock state index the reader has incremented.
91  static constexpr int NotAcquired = -1;
92  static constexpr int WriteAcquired = -2;
93 
94  /// Construct a scoped lock for mutex \p m and acquire either a read or
95  /// a write lock depending on \p write.
96  explicit ScopedLock(TfBigRWMutex &m, bool write=true)
97  : _mutex(&m)
98  , _acqState(NotAcquired) {
99  Acquire(write);
100  }
101 
102  /// Construct a scoped lock not associated with a \p mutex.
103  ScopedLock() : _mutex(nullptr), _acqState(NotAcquired) {}
104 
105  /// If this scoped lock is acquired for either read or write, Release()
106  /// it.
108  Release();
109  }
110 
111  /// If the current scoped lock is acquired, Release() it, then associate
112  /// this lock with \p m and acquire either a read or a write lock,
113  /// depending on \p write.
114  void Acquire(TfBigRWMutex &m, bool write=true) {
115  Release();
116  _mutex = &m;
117  Acquire(write);
118  }
119 
120  /// Acquire either a read or write lock on this lock's associated mutex
121  /// depending on \p write. This lock must be associated with a mutex
122  /// (typically by construction or by a call to Acquire() that takes a
123  /// mutex). This lock must not already be acquired when calling
124  /// Acquire().
125  void Acquire(bool write=true) {
126  if (write) {
127  AcquireWrite();
128  }
129  else {
130  AcquireRead();
131  }
132  }
133 
134  /// Release the currently required lock on the associated mutex. If
135  /// this lock is not currently acquired, silently do nothing.
136  void Release() {
137  switch (_acqState) {
138  case NotAcquired:
139  break;
140  case WriteAcquired:
141  _ReleaseWrite();
142  break;
143  default:
144  _ReleaseRead();
145  break;
146  };
147  }
148 
149  /// Acquire a read lock on this lock's associated mutex. This lock must
150  /// not already be acquired when calling \p AcquireRead().
151  void AcquireRead() {
152  TF_AXIOM(_acqState == NotAcquired);
153  _acqState = _mutex->_AcquireRead(_GetSeed());
154  }
155 
156  /// Acquire a write lock on this lock's associated mutex. This lock
157  /// must not already be acquired when calling \p AcquireWrite().
158  void AcquireWrite() {
159  TF_AXIOM(_acqState == NotAcquired);
160  _mutex->_AcquireWrite();
161  _acqState = WriteAcquired;
162  }
163 
164  /// Change this lock's acquisition state from a read lock to a write
165  /// lock. This lock must already be acquired for reading. For
166  /// consistency with tbb, this function returns a bool indicating
167  /// whether the upgrade was done atomically, without releasing the
168  /// read-lock. However the current implementation always releases the
169  /// read lock so this function always returns false.
171  TF_AXIOM(_acqState >= 0);
172  Release();
173  AcquireWrite();
174  return false;
175  }
176 
177  private:
178 
179  void _ReleaseRead() {
180  TF_AXIOM(_acqState >= 0);
181  _mutex->_ReleaseRead(_acqState);
182  _acqState = NotAcquired;
183  }
184 
185  void _ReleaseWrite() {
186  TF_AXIOM(_acqState == WriteAcquired);
187  _mutex->_ReleaseWrite();
188  _acqState = NotAcquired;
189  }
190 
191  // Helper for returning a seed value associated with this lock object.
192  // This helps determine which lock state a read-lock should use.
193  inline int _GetSeed() const {
194  return static_cast<int>(
195  static_cast<unsigned>(TfHash()(this)) >> 8);
196  }
197 
198  TfBigRWMutex *_mutex;
199  int _acqState; // NotAcquired (-1), WriteAcquired (-2), otherwise
200  // acquired for read, and index indicates which lock
201  // state we are associated with.
202  };
203 
204 private:
205 
206  // Optimistic read-lock case inlined.
207  inline int _AcquireRead(int seed) {
208  // Determine a lock state index to use.
209  int stateIndex = seed % NumStates;
210  if (ARCH_UNLIKELY(_writerActive) ||
211  !_states[stateIndex].mutex.TryAcquireRead()) {
212  _AcquireReadContended(stateIndex);
213  }
214  return stateIndex;
215  }
216 
217  // Contended read-lock helper.
218  TF_API void _AcquireReadContended(int stateIndex);
219 
220  void _ReleaseRead(int stateIndex) {
221  _states[stateIndex].mutex.ReleaseRead();
222  }
223 
224  TF_API void _AcquireWrite();
225  TF_API void _ReleaseWrite();
226 
227  struct _LockState {
228  TfSpinRWMutex mutex;
229  // This padding ensures that \p state instances sit on different cache
230  // lines.
231  char _unused_padding[
232  ARCH_CACHE_LINE_SIZE-(sizeof(mutex) % ARCH_CACHE_LINE_SIZE)];
233  };
234 
235  std::unique_ptr<_LockState []> _states;
236  std::atomic<bool> _writerActive;
237 
238 };
239 
241 
242 #endif // PXR_BASE_TF_BIG_RW_MUTEX_H
static constexpr unsigned NumStates
Definition: bigRWMutex.h:73
#define TF_API
Definition: api.h:40
TF_API TfBigRWMutex()
Construct a mutex, initially unlocked.
void Acquire(TfBigRWMutex &m, bool write=true)
Definition: bigRWMutex.h:114
Definition: hash.h:477
#define ARCH_UNLIKELY(x)
Definition: hints.h:47
static constexpr int NotAcquired
Definition: bigRWMutex.h:91
static constexpr int NotLocked
Definition: bigRWMutex.h:78
ScopedLock(TfBigRWMutex &m, bool write=true)
Definition: bigRWMutex.h:96
static constexpr int WriteLocked
Definition: bigRWMutex.h:79
#define ARCH_CACHE_LINE_SIZE
Definition: align.h:84
#define TF_AXIOM(cond)
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1432
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:91
void Acquire(bool write=true)
Definition: bigRWMutex.h:125
ScopedLock()
Construct a scoped lock not associated with a mutex.
Definition: bigRWMutex.h:103
static constexpr int WriteAcquired
Definition: bigRWMutex.h:92