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
41namespace kj {
42
43// =======================================================================================
44// Private details -- public interfaces follow below.
45
46namespace _ { // private
47
48class Mutex {
49 // Internal implementation details. See `MutexGuarded<T>`.
50
51public:
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
79private:
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
105class Once {
106 // Internal implementation details. See `Lazy<T>`.
107
108public:
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
144private:
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
173template <typename T>
174class 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
178public:
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
213private:
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
223template <typename T>
224class 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
237public:
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
299private:
300 mutable _::Mutex mutex;
301 mutable T value;
302};
303
304template <typename T>
305class 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
311template <typename T>
312class Lazy {
313 // A lazily-initialized value.
314
315public:
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
328private:
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
340template <typename T>
341template <typename... Params>
342inline MutexGuarded<T>::MutexGuarded(Params&&... params)
343 : value(kj::fwd<Params>(params)...) {}
344
345template <typename T>
346inline Locked<T> MutexGuarded<T>::lockExclusive() const {
347 mutex.lock(_::Mutex::EXCLUSIVE);
348 return Locked<T>(mutex, value);
349}
350
351template <typename T>
352inline Locked<const T> MutexGuarded<T>::lockShared() const {
353 mutex.lock(_::Mutex::SHARED);
354 return Locked<const T>(mutex, value);
355}
356
357template <typename T>
358inline const T& MutexGuarded<T>::getAlreadyLockedShared() const {
359#ifdef KJ_DEBUG
360 mutex.assertLockedByCaller(_::Mutex::SHARED);
361#endif
362 return value;
363}
364template <typename T>
365inline T& MutexGuarded<T>::getAlreadyLockedShared() {
366#ifdef KJ_DEBUG
367 mutex.assertLockedByCaller(_::Mutex::SHARED);
368#endif
369 return value;
370}
371template <typename T>
372inline T& MutexGuarded<T>::getAlreadyLockedExclusive() const {
373#ifdef KJ_DEBUG
374 mutex.assertLockedByCaller(_::Mutex::EXCLUSIVE);
375#endif
376 return const_cast<T&>(value);
377}
378
379template <typename T>
380template <typename Func>
381class Lazy<T>::InitImpl: public _::Once::Initializer {
382public:
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
389private:
390 const Lazy<T>& lazy;
391 Func func;
392};
393
394template <typename T>
395template <typename Func>
396inline 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
404template <typename T>
405template <typename Func>
406inline 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