1 | // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors |
2 | // Licensed under the MIT License: |
3 | // |
4 | // Permission is hereby granted, free of charge, to any person obtaining a copy |
5 | // of this software and associated documentation files (the "Software"), to deal |
6 | // in the Software without restriction, including without limitation the rights |
7 | // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
8 | // copies of the Software, and to permit persons to whom the Software is |
9 | // furnished to do so, subject to the following conditions: |
10 | // |
11 | // The above copyright notice and this permission notice shall be included in |
12 | // all copies or substantial portions of the Software. |
13 | // |
14 | // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
15 | // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
16 | // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
17 | // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
18 | // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
19 | // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
20 | // THE SOFTWARE. |
21 | |
22 | #pragma once |
23 | |
24 | #if defined(__GNUC__) && !KJ_HEADER_WARNINGS |
25 | #pragma GCC system_header |
26 | #endif |
27 | |
28 | #include "memory.h" |
29 | #include <inttypes.h> |
30 | |
31 | #if __linux__ && !defined(KJ_USE_FUTEX) |
32 | #define KJ_USE_FUTEX 1 |
33 | #endif |
34 | |
35 | #if !KJ_USE_FUTEX && !_WIN32 |
36 | // On Linux we use futex. On other platforms we wrap pthreads. |
37 | // TODO(someday): Write efficient low-level locking primitives for other platforms. |
38 | #include <pthread.h> |
39 | #endif |
40 | |
41 | namespace kj { |
42 | |
43 | // ======================================================================================= |
44 | // Private details -- public interfaces follow below. |
45 | |
46 | namespace _ { // private |
47 | |
48 | class Mutex { |
49 | // Internal implementation details. See `MutexGuarded<T>`. |
50 | |
51 | public: |
52 | Mutex(); |
53 | ~Mutex(); |
54 | KJ_DISALLOW_COPY(Mutex); |
55 | |
56 | enum Exclusivity { |
57 | EXCLUSIVE, |
58 | SHARED |
59 | }; |
60 | |
61 | void lock(Exclusivity exclusivity); |
62 | void unlock(Exclusivity exclusivity); |
63 | |
64 | void assertLockedByCaller(Exclusivity exclusivity); |
65 | // In debug mode, assert that the mutex is locked by the calling thread, or if that is |
66 | // non-trivial, assert that the mutex is locked (which should be good enough to catch problems |
67 | // in unit tests). In non-debug builds, do nothing. |
68 | |
69 | #if KJ_USE_FUTEX // TODO(someday): Implement on pthread & win32 |
70 | class Predicate { |
71 | public: |
72 | virtual bool check() = 0; |
73 | }; |
74 | |
75 | void lockWhen(Predicate& predicate); |
76 | // Lock (exclusively) when predicate.check() returns true. |
77 | #endif |
78 | |
79 | private: |
80 | #if KJ_USE_FUTEX |
81 | uint futex; |
82 | // bit 31 (msb) = set if exclusive lock held |
83 | // bit 30 (msb) = set if threads are waiting for exclusive lock |
84 | // bits 0-29 = count of readers; If an exclusive lock is held, this is the count of threads |
85 | // waiting for a read lock, otherwise it is the count of threads that currently hold a read |
86 | // lock. |
87 | |
88 | static constexpr uint EXCLUSIVE_HELD = 1u << 31; |
89 | static constexpr uint EXCLUSIVE_REQUESTED = 1u << 30; |
90 | static constexpr uint SHARED_COUNT_MASK = EXCLUSIVE_REQUESTED - 1; |
91 | |
92 | struct Waiter; |
93 | kj::Maybe<Waiter&> waitersHead = nullptr; |
94 | kj::Maybe<Waiter&>* waitersTail = &waitersHead; |
95 | // linked list of waitUntil()s; can only modify under lock |
96 | |
97 | #elif _WIN32 |
98 | uintptr_t srwLock; // Actually an SRWLOCK, but don't want to #include <windows.h> in header. |
99 | |
100 | #else |
101 | mutable pthread_rwlock_t mutex; |
102 | #endif |
103 | }; |
104 | |
105 | class Once { |
106 | // Internal implementation details. See `Lazy<T>`. |
107 | |
108 | public: |
109 | #if KJ_USE_FUTEX |
110 | inline Once(bool startInitialized = false) |
111 | : futex(startInitialized ? INITIALIZED : UNINITIALIZED) {} |
112 | #else |
113 | Once(bool startInitialized = false); |
114 | ~Once(); |
115 | #endif |
116 | KJ_DISALLOW_COPY(Once); |
117 | |
118 | class Initializer { |
119 | public: |
120 | virtual void run() = 0; |
121 | }; |
122 | |
123 | void runOnce(Initializer& init); |
124 | |
125 | #if _WIN32 // TODO(perf): Can we make this inline on win32 somehow? |
126 | bool isInitialized() noexcept; |
127 | |
128 | #else |
129 | inline bool isInitialized() noexcept { |
130 | // Fast path check to see if runOnce() would simply return immediately. |
131 | #if KJ_USE_FUTEX |
132 | return __atomic_load_n(&futex, __ATOMIC_ACQUIRE) == INITIALIZED; |
133 | #else |
134 | return __atomic_load_n(&state, __ATOMIC_ACQUIRE) == INITIALIZED; |
135 | #endif |
136 | } |
137 | #endif |
138 | |
139 | void reset(); |
140 | // Returns the state from initialized to uninitialized. It is an error to call this when |
141 | // not already initialized, or when runOnce() or isInitialized() might be called concurrently in |
142 | // another thread. |
143 | |
144 | private: |
145 | #if KJ_USE_FUTEX |
146 | uint futex; |
147 | |
148 | enum State { |
149 | UNINITIALIZED, |
150 | INITIALIZING, |
151 | INITIALIZING_WITH_WAITERS, |
152 | INITIALIZED |
153 | }; |
154 | |
155 | #elif _WIN32 |
156 | uintptr_t initOnce; // Actually an INIT_ONCE, but don't want to #include <windows.h> in header. |
157 | |
158 | #else |
159 | enum State { |
160 | UNINITIALIZED, |
161 | INITIALIZED |
162 | }; |
163 | State state; |
164 | pthread_mutex_t mutex; |
165 | #endif |
166 | }; |
167 | |
168 | } // namespace _ (private) |
169 | |
170 | // ======================================================================================= |
171 | // Public interface |
172 | |
173 | template <typename T> |
174 | class Locked { |
175 | // Return type for `MutexGuarded<T>::lock()`. `Locked<T>` provides access to the bounded object |
176 | // and unlocks the mutex when it goes out of scope. |
177 | |
178 | public: |
179 | KJ_DISALLOW_COPY(Locked); |
180 | inline Locked(): mutex(nullptr), ptr(nullptr) {} |
181 | inline Locked(Locked&& other): mutex(other.mutex), ptr(other.ptr) { |
182 | other.mutex = nullptr; |
183 | other.ptr = nullptr; |
184 | } |
185 | inline ~Locked() { |
186 | if (mutex != nullptr) mutex->unlock(isConst<T>() ? _::Mutex::SHARED : _::Mutex::EXCLUSIVE); |
187 | } |
188 | |
189 | inline Locked& operator=(Locked&& other) { |
190 | if (mutex != nullptr) mutex->unlock(isConst<T>() ? _::Mutex::SHARED : _::Mutex::EXCLUSIVE); |
191 | mutex = other.mutex; |
192 | ptr = other.ptr; |
193 | other.mutex = nullptr; |
194 | other.ptr = nullptr; |
195 | return *this; |
196 | } |
197 | |
198 | inline void release() { |
199 | if (mutex != nullptr) mutex->unlock(isConst<T>() ? _::Mutex::SHARED : _::Mutex::EXCLUSIVE); |
200 | mutex = nullptr; |
201 | ptr = nullptr; |
202 | } |
203 | |
204 | inline T* operator->() { return ptr; } |
205 | inline const T* operator->() const { return ptr; } |
206 | inline T& operator*() { return *ptr; } |
207 | inline const T& operator*() const { return *ptr; } |
208 | inline T* get() { return ptr; } |
209 | inline const T* get() const { return ptr; } |
210 | inline operator T*() { return ptr; } |
211 | inline operator const T*() const { return ptr; } |
212 | |
213 | private: |
214 | _::Mutex* mutex; |
215 | T* ptr; |
216 | |
217 | inline Locked(_::Mutex& mutex, T& value): mutex(&mutex), ptr(&value) {} |
218 | |
219 | template <typename U> |
220 | friend class MutexGuarded; |
221 | }; |
222 | |
223 | template <typename T> |
224 | class MutexGuarded { |
225 | // An object of type T, bounded by a mutex. In order to access the object, you must lock it. |
226 | // |
227 | // Write locks are not "recursive" -- trying to lock again in a thread that already holds a lock |
228 | // will deadlock. Recursive write locks are usually a sign of bad design. |
229 | // |
230 | // Unfortunately, **READ LOCKS ARE NOT RECURSIVE** either. Common sense says they should be. |
231 | // But on many operating systems (BSD, OSX), recursively read-locking a pthread_rwlock is |
232 | // actually unsafe. The problem is that writers are "prioritized" over readers, so a read lock |
233 | // request will block if any write lock requests are outstanding. So, if thread A takes a read |
234 | // lock, thread B requests a write lock (and starts waiting), and then thread A tries to take |
235 | // another read lock recursively, the result is deadlock. |
236 | |
237 | public: |
238 | template <typename... Params> |
239 | explicit MutexGuarded(Params&&... params); |
240 | // Initialize the mutex-bounded object by passing the given parameters to its constructor. |
241 | |
242 | Locked<T> lockExclusive() const; |
243 | // Exclusively locks the object and returns it. The returned `Locked<T>` can be passed by |
244 | // move, similar to `Own<T>`. |
245 | // |
246 | // This method is declared `const` in accordance with KJ style rules which say that constness |
247 | // should be used to indicate thread-safety. It is safe to share a const pointer between threads, |
248 | // but it is not safe to share a mutable pointer. Since the whole point of MutexGuarded is to |
249 | // be shared between threads, its methods should be const, even though locking it produces a |
250 | // non-const pointer to the contained object. |
251 | |
252 | Locked<const T> lockShared() const; |
253 | // Lock the value for shared access. Multiple shared locks can be taken concurrently, but cannot |
254 | // be held at the same time as a non-shared lock. |
255 | |
256 | inline const T& getWithoutLock() const { return value; } |
257 | inline T& getWithoutLock() { return value; } |
258 | // Escape hatch for cases where some external factor guarantees that it's safe to get the |
259 | // value. You should treat these like const_cast -- be highly suspicious of any use. |
260 | |
261 | inline const T& getAlreadyLockedShared() const; |
262 | inline T& getAlreadyLockedShared(); |
263 | inline T& getAlreadyLockedExclusive() const; |
264 | // Like `getWithoutLock()`, but asserts that the lock is already held by the calling thread. |
265 | |
266 | #if KJ_USE_FUTEX // TODO(someday): Implement on pthread & win32 |
267 | template <typename Cond, typename Func> |
268 | auto when(Cond&& condition, Func&& callback) const -> decltype(callback(instance<T&>())) { |
269 | // Waits until condition(state) returns true, then calls callback(state) under lock. |
270 | // |
271 | // `condition`, when called, receives as its parameter a const reference to the state, which is |
272 | // locked (either shared or exclusive). `callback` returns a mutable reference, which is |
273 | // exclusively locked. |
274 | // |
275 | // `condition()` may be called multiple times, from multiple threads, while waiting for the |
276 | // condition to become true. It may even return true once, but then be called more times. |
277 | // It is guaranteed, though, that at the time `callback()` is finally called, `condition()` |
278 | // would currently return true (assuming it is a pure function of the guarded data). |
279 | |
280 | struct PredicateImpl final: public _::Mutex::Predicate { |
281 | bool check() override { |
282 | return condition(value); |
283 | } |
284 | |
285 | Cond&& condition; |
286 | const T& value; |
287 | |
288 | PredicateImpl(Cond&& condition, const T& value) |
289 | : condition(kj::fwd<Cond>(condition)), value(value) {} |
290 | }; |
291 | |
292 | PredicateImpl impl(kj::fwd<Cond>(condition), value); |
293 | mutex.lockWhen(impl); |
294 | KJ_DEFER(mutex.unlock(_::Mutex::EXCLUSIVE)); |
295 | return callback(value); |
296 | } |
297 | #endif |
298 | |
299 | private: |
300 | mutable _::Mutex mutex; |
301 | mutable T value; |
302 | }; |
303 | |
304 | template <typename T> |
305 | class MutexGuarded<const T> { |
306 | // MutexGuarded cannot guard a const type. This would be pointless anyway, and would complicate |
307 | // the implementation of Locked<T>, which uses constness to decide what kind of lock it holds. |
308 | static_assert(sizeof(T) < 0, "MutexGuarded's type cannot be const." ); |
309 | }; |
310 | |
311 | template <typename T> |
312 | class Lazy { |
313 | // A lazily-initialized value. |
314 | |
315 | public: |
316 | template <typename Func> |
317 | T& get(Func&& init); |
318 | template <typename Func> |
319 | const T& get(Func&& init) const; |
320 | // The first thread to call get() will invoke the given init function to construct the value. |
321 | // Other threads will block until construction completes, then return the same value. |
322 | // |
323 | // `init` is a functor(typically a lambda) which takes `SpaceFor<T>&` as its parameter and returns |
324 | // `Own<T>`. If `init` throws an exception, the exception is propagated out of that thread's |
325 | // call to `get()`, and subsequent calls behave as if `get()` hadn't been called at all yet -- |
326 | // in other words, subsequent calls retry initialization until it succeeds. |
327 | |
328 | private: |
329 | mutable _::Once once; |
330 | mutable SpaceFor<T> space; |
331 | mutable Own<T> value; |
332 | |
333 | template <typename Func> |
334 | class InitImpl; |
335 | }; |
336 | |
337 | // ======================================================================================= |
338 | // Inline implementation details |
339 | |
340 | template <typename T> |
341 | template <typename... Params> |
342 | inline MutexGuarded<T>::MutexGuarded(Params&&... params) |
343 | : value(kj::fwd<Params>(params)...) {} |
344 | |
345 | template <typename T> |
346 | inline Locked<T> MutexGuarded<T>::lockExclusive() const { |
347 | mutex.lock(_::Mutex::EXCLUSIVE); |
348 | return Locked<T>(mutex, value); |
349 | } |
350 | |
351 | template <typename T> |
352 | inline Locked<const T> MutexGuarded<T>::lockShared() const { |
353 | mutex.lock(_::Mutex::SHARED); |
354 | return Locked<const T>(mutex, value); |
355 | } |
356 | |
357 | template <typename T> |
358 | inline const T& MutexGuarded<T>::getAlreadyLockedShared() const { |
359 | #ifdef KJ_DEBUG |
360 | mutex.assertLockedByCaller(_::Mutex::SHARED); |
361 | #endif |
362 | return value; |
363 | } |
364 | template <typename T> |
365 | inline T& MutexGuarded<T>::getAlreadyLockedShared() { |
366 | #ifdef KJ_DEBUG |
367 | mutex.assertLockedByCaller(_::Mutex::SHARED); |
368 | #endif |
369 | return value; |
370 | } |
371 | template <typename T> |
372 | inline T& MutexGuarded<T>::getAlreadyLockedExclusive() const { |
373 | #ifdef KJ_DEBUG |
374 | mutex.assertLockedByCaller(_::Mutex::EXCLUSIVE); |
375 | #endif |
376 | return const_cast<T&>(value); |
377 | } |
378 | |
379 | template <typename T> |
380 | template <typename Func> |
381 | class Lazy<T>::InitImpl: public _::Once::Initializer { |
382 | public: |
383 | inline InitImpl(const Lazy<T>& lazy, Func&& func): lazy(lazy), func(kj::fwd<Func>(func)) {} |
384 | |
385 | void run() override { |
386 | lazy.value = func(lazy.space); |
387 | } |
388 | |
389 | private: |
390 | const Lazy<T>& lazy; |
391 | Func func; |
392 | }; |
393 | |
394 | template <typename T> |
395 | template <typename Func> |
396 | inline T& Lazy<T>::get(Func&& init) { |
397 | if (!once.isInitialized()) { |
398 | InitImpl<Func> initImpl(*this, kj::fwd<Func>(init)); |
399 | once.runOnce(initImpl); |
400 | } |
401 | return *value; |
402 | } |
403 | |
404 | template <typename T> |
405 | template <typename Func> |
406 | inline const T& Lazy<T>::get(Func&& init) const { |
407 | if (!once.isInitialized()) { |
408 | InitImpl<Func> initImpl(*this, kj::fwd<Func>(init)); |
409 | once.runOnce(initImpl); |
410 | } |
411 | return *value; |
412 | } |
413 | |
414 | } // namespace kj |
415 | |