cannam@49: // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
cannam@49: // Licensed under the MIT License:
cannam@49: //
cannam@49: // Permission is hereby granted, free of charge, to any person obtaining a copy
cannam@49: // of this software and associated documentation files (the "Software"), to deal
cannam@49: // in the Software without restriction, including without limitation the rights
cannam@49: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
cannam@49: // copies of the Software, and to permit persons to whom the Software is
cannam@49: // furnished to do so, subject to the following conditions:
cannam@49: //
cannam@49: // The above copyright notice and this permission notice shall be included in
cannam@49: // all copies or substantial portions of the Software.
cannam@49: //
cannam@49: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
cannam@49: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
cannam@49: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
cannam@49: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
cannam@49: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
cannam@49: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
cannam@49: // THE SOFTWARE.
cannam@49: 
cannam@49: #ifndef KJ_MUTEX_H_
cannam@49: #define KJ_MUTEX_H_
cannam@49: 
cannam@49: #if defined(__GNUC__) && !KJ_HEADER_WARNINGS
cannam@49: #pragma GCC system_header
cannam@49: #endif
cannam@49: 
cannam@49: #include "memory.h"
cannam@49: #include <inttypes.h>
cannam@49: 
cannam@49: #if __linux__ && !defined(KJ_USE_FUTEX)
cannam@49: #define KJ_USE_FUTEX 1
cannam@49: #endif
cannam@49: 
cannam@49: #if !KJ_USE_FUTEX && !_WIN32
cannam@49: // On Linux we use futex.  On other platforms we wrap pthreads.
cannam@49: // TODO(someday):  Write efficient low-level locking primitives for other platforms.
cannam@49: #include <pthread.h>
cannam@49: #endif
cannam@49: 
cannam@49: namespace kj {
cannam@49: 
cannam@49: // =======================================================================================
cannam@49: // Private details -- public interfaces follow below.
cannam@49: 
cannam@49: namespace _ {  // private
cannam@49: 
cannam@49: class Mutex {
cannam@49:   // Internal implementation details.  See `MutexGuarded<T>`.
cannam@49: 
cannam@49: public:
cannam@49:   Mutex();
cannam@49:   ~Mutex();
cannam@49:   KJ_DISALLOW_COPY(Mutex);
cannam@49: 
cannam@49:   enum Exclusivity {
cannam@49:     EXCLUSIVE,
cannam@49:     SHARED
cannam@49:   };
cannam@49: 
cannam@49:   void lock(Exclusivity exclusivity);
cannam@49:   void unlock(Exclusivity exclusivity);
cannam@49: 
cannam@49:   void assertLockedByCaller(Exclusivity exclusivity);
cannam@49:   // In debug mode, assert that the mutex is locked by the calling thread, or if that is
cannam@49:   // non-trivial, assert that the mutex is locked (which should be good enough to catch problems
cannam@49:   // in unit tests).  In non-debug builds, do nothing.
cannam@49: 
cannam@49: private:
cannam@49: #if KJ_USE_FUTEX
cannam@49:   uint futex;
cannam@49:   // bit 31 (msb) = set if exclusive lock held
cannam@49:   // bit 30 (msb) = set if threads are waiting for exclusive lock
cannam@49:   // bits 0-29 = count of readers; If an exclusive lock is held, this is the count of threads
cannam@49:   //   waiting for a read lock, otherwise it is the count of threads that currently hold a read
cannam@49:   //   lock.
cannam@49: 
cannam@49:   static constexpr uint EXCLUSIVE_HELD = 1u << 31;
cannam@49:   static constexpr uint EXCLUSIVE_REQUESTED = 1u << 30;
cannam@49:   static constexpr uint SHARED_COUNT_MASK = EXCLUSIVE_REQUESTED - 1;
cannam@49: 
cannam@49: #elif _WIN32
cannam@49:   uintptr_t srwLock;  // Actually an SRWLOCK, but don't want to #include <windows.h> in header.
cannam@49: 
cannam@49: #else
cannam@49:   mutable pthread_rwlock_t mutex;
cannam@49: #endif
cannam@49: };
cannam@49: 
cannam@49: class Once {
cannam@49:   // Internal implementation details.  See `Lazy<T>`.
cannam@49: 
cannam@49: public:
cannam@49: #if KJ_USE_FUTEX
cannam@49:   inline Once(bool startInitialized = false)
cannam@49:       : futex(startInitialized ? INITIALIZED : UNINITIALIZED) {}
cannam@49: #else
cannam@49:   Once(bool startInitialized = false);
cannam@49:   ~Once();
cannam@49: #endif
cannam@49:   KJ_DISALLOW_COPY(Once);
cannam@49: 
cannam@49:   class Initializer {
cannam@49:   public:
cannam@49:     virtual void run() = 0;
cannam@49:   };
cannam@49: 
cannam@49:   void runOnce(Initializer& init);
cannam@49: 
cannam@49: #if _WIN32  // TODO(perf): Can we make this inline on win32 somehow?
cannam@49:   bool isInitialized() noexcept;
cannam@49: 
cannam@49: #else
cannam@49:   inline bool isInitialized() noexcept {
cannam@49:     // Fast path check to see if runOnce() would simply return immediately.
cannam@49: #if KJ_USE_FUTEX
cannam@49:     return __atomic_load_n(&futex, __ATOMIC_ACQUIRE) == INITIALIZED;
cannam@49: #else
cannam@49:     return __atomic_load_n(&state, __ATOMIC_ACQUIRE) == INITIALIZED;
cannam@49: #endif
cannam@49:   }
cannam@49: #endif
cannam@49: 
cannam@49:   void reset();
cannam@49:   // Returns the state from initialized to uninitialized.  It is an error to call this when
cannam@49:   // not already initialized, or when runOnce() or isInitialized() might be called concurrently in
cannam@49:   // another thread.
cannam@49: 
cannam@49: private:
cannam@49: #if KJ_USE_FUTEX
cannam@49:   uint futex;
cannam@49: 
cannam@49:   enum State {
cannam@49:     UNINITIALIZED,
cannam@49:     INITIALIZING,
cannam@49:     INITIALIZING_WITH_WAITERS,
cannam@49:     INITIALIZED
cannam@49:   };
cannam@49: 
cannam@49: #elif _WIN32
cannam@49:   uintptr_t initOnce;  // Actually an INIT_ONCE, but don't want to #include <windows.h> in header.
cannam@49: 
cannam@49: #else
cannam@49:   enum State {
cannam@49:     UNINITIALIZED,
cannam@49:     INITIALIZED
cannam@49:   };
cannam@49:   State state;
cannam@49:   pthread_mutex_t mutex;
cannam@49: #endif
cannam@49: };
cannam@49: 
cannam@49: }  // namespace _ (private)
cannam@49: 
cannam@49: // =======================================================================================
cannam@49: // Public interface
cannam@49: 
cannam@49: template <typename T>
cannam@49: class Locked {
cannam@49:   // Return type for `MutexGuarded<T>::lock()`.  `Locked<T>` provides access to the guarded object
cannam@49:   // and unlocks the mutex when it goes out of scope.
cannam@49: 
cannam@49: public:
cannam@49:   KJ_DISALLOW_COPY(Locked);
cannam@49:   inline Locked(): mutex(nullptr), ptr(nullptr) {}
cannam@49:   inline Locked(Locked&& other): mutex(other.mutex), ptr(other.ptr) {
cannam@49:     other.mutex = nullptr;
cannam@49:     other.ptr = nullptr;
cannam@49:   }
cannam@49:   inline ~Locked() {
cannam@49:     if (mutex != nullptr) mutex->unlock(isConst<T>() ? _::Mutex::SHARED : _::Mutex::EXCLUSIVE);
cannam@49:   }
cannam@49: 
cannam@49:   inline Locked& operator=(Locked&& other) {
cannam@49:     if (mutex != nullptr) mutex->unlock(isConst<T>() ? _::Mutex::SHARED : _::Mutex::EXCLUSIVE);
cannam@49:     mutex = other.mutex;
cannam@49:     ptr = other.ptr;
cannam@49:     other.mutex = nullptr;
cannam@49:     other.ptr = nullptr;
cannam@49:     return *this;
cannam@49:   }
cannam@49: 
cannam@49:   inline void release() {
cannam@49:     if (mutex != nullptr) mutex->unlock(isConst<T>() ? _::Mutex::SHARED : _::Mutex::EXCLUSIVE);
cannam@49:     mutex = nullptr;
cannam@49:     ptr = nullptr;
cannam@49:   }
cannam@49: 
cannam@49:   inline T* operator->() { return ptr; }
cannam@49:   inline const T* operator->() const { return ptr; }
cannam@49:   inline T& operator*() { return *ptr; }
cannam@49:   inline const T& operator*() const { return *ptr; }
cannam@49:   inline T* get() { return ptr; }
cannam@49:   inline const T* get() const { return ptr; }
cannam@49:   inline operator T*() { return ptr; }
cannam@49:   inline operator const T*() const { return ptr; }
cannam@49: 
cannam@49: private:
cannam@49:   _::Mutex* mutex;
cannam@49:   T* ptr;
cannam@49: 
cannam@49:   inline Locked(_::Mutex& mutex, T& value): mutex(&mutex), ptr(&value) {}
cannam@49: 
cannam@49:   template <typename U>
cannam@49:   friend class MutexGuarded;
cannam@49: };
cannam@49: 
cannam@49: template <typename T>
cannam@49: class MutexGuarded {
cannam@49:   // An object of type T, guarded by a mutex.  In order to access the object, you must lock it.
cannam@49:   //
cannam@49:   // Write locks are not "recursive" -- trying to lock again in a thread that already holds a lock
cannam@49:   // will deadlock.  Recursive write locks are usually a sign of bad design.
cannam@49:   //
cannam@49:   // Unfortunately, **READ LOCKS ARE NOT RECURSIVE** either.  Common sense says they should be.
cannam@49:   // But on many operating systems (BSD, OSX), recursively read-locking a pthread_rwlock is
cannam@49:   // actually unsafe.  The problem is that writers are "prioritized" over readers, so a read lock
cannam@49:   // request will block if any write lock requests are outstanding.  So, if thread A takes a read
cannam@49:   // lock, thread B requests a write lock (and starts waiting), and then thread A tries to take
cannam@49:   // another read lock recursively, the result is deadlock.
cannam@49: 
cannam@49: public:
cannam@49:   template <typename... Params>
cannam@49:   explicit MutexGuarded(Params&&... params);
cannam@49:   // Initialize the mutex-guarded object by passing the given parameters to its constructor.
cannam@49: 
cannam@49:   Locked<T> lockExclusive() const;
cannam@49:   // Exclusively locks the object and returns it.  The returned `Locked<T>` can be passed by
cannam@49:   // move, similar to `Own<T>`.
cannam@49:   //
cannam@49:   // This method is declared `const` in accordance with KJ style rules which say that constness
cannam@49:   // should be used to indicate thread-safety.  It is safe to share a const pointer between threads,
cannam@49:   // but it is not safe to share a mutable pointer.  Since the whole point of MutexGuarded is to
cannam@49:   // be shared between threads, its methods should be const, even though locking it produces a
cannam@49:   // non-const pointer to the contained object.
cannam@49: 
cannam@49:   Locked<const T> lockShared() const;
cannam@49:   // Lock the value for shared access.  Multiple shared locks can be taken concurrently, but cannot
cannam@49:   // be held at the same time as a non-shared lock.
cannam@49: 
cannam@49:   inline const T& getWithoutLock() const { return value; }
cannam@49:   inline T& getWithoutLock() { return value; }
cannam@49:   // Escape hatch for cases where some external factor guarantees that it's safe to get the
cannam@49:   // value.  You should treat these like const_cast -- be highly suspicious of any use.
cannam@49: 
cannam@49:   inline const T& getAlreadyLockedShared() const;
cannam@49:   inline T& getAlreadyLockedShared();
cannam@49:   inline T& getAlreadyLockedExclusive() const;
cannam@49:   // Like `getWithoutLock()`, but asserts that the lock is already held by the calling thread.
cannam@49: 
cannam@49: private:
cannam@49:   mutable _::Mutex mutex;
cannam@49:   mutable T value;
cannam@49: };
cannam@49: 
cannam@49: template <typename T>
cannam@49: class MutexGuarded<const T> {
cannam@49:   // MutexGuarded cannot guard a const type.  This would be pointless anyway, and would complicate
cannam@49:   // the implementation of Locked<T>, which uses constness to decide what kind of lock it holds.
cannam@49:   static_assert(sizeof(T) < 0, "MutexGuarded's type cannot be const.");
cannam@49: };
cannam@49: 
cannam@49: template <typename T>
cannam@49: class Lazy {
cannam@49:   // A lazily-initialized value.
cannam@49: 
cannam@49: public:
cannam@49:   template <typename Func>
cannam@49:   T& get(Func&& init);
cannam@49:   template <typename Func>
cannam@49:   const T& get(Func&& init) const;
cannam@49:   // The first thread to call get() will invoke the given init function to construct the value.
cannam@49:   // Other threads will block until construction completes, then return the same value.
cannam@49:   //
cannam@49:   // `init` is a functor(typically a lambda) which takes `SpaceFor<T>&` as its parameter and returns
cannam@49:   // `Own<T>`.  If `init` throws an exception, the exception is propagated out of that thread's
cannam@49:   // call to `get()`, and subsequent calls behave as if `get()` hadn't been called at all yet --
cannam@49:   // in other words, subsequent calls retry initialization until it succeeds.
cannam@49: 
cannam@49: private:
cannam@49:   mutable _::Once once;
cannam@49:   mutable SpaceFor<T> space;
cannam@49:   mutable Own<T> value;
cannam@49: 
cannam@49:   template <typename Func>
cannam@49:   class InitImpl;
cannam@49: };
cannam@49: 
cannam@49: // =======================================================================================
cannam@49: // Inline implementation details
cannam@49: 
cannam@49: template <typename T>
cannam@49: template <typename... Params>
cannam@49: inline MutexGuarded<T>::MutexGuarded(Params&&... params)
cannam@49:     : value(kj::fwd<Params>(params)...) {}
cannam@49: 
cannam@49: template <typename T>
cannam@49: inline Locked<T> MutexGuarded<T>::lockExclusive() const {
cannam@49:   mutex.lock(_::Mutex::EXCLUSIVE);
cannam@49:   return Locked<T>(mutex, value);
cannam@49: }
cannam@49: 
cannam@49: template <typename T>
cannam@49: inline Locked<const T> MutexGuarded<T>::lockShared() const {
cannam@49:   mutex.lock(_::Mutex::SHARED);
cannam@49:   return Locked<const T>(mutex, value);
cannam@49: }
cannam@49: 
cannam@49: template <typename T>
cannam@49: inline const T& MutexGuarded<T>::getAlreadyLockedShared() const {
cannam@49: #ifdef KJ_DEBUG
cannam@49:   mutex.assertLockedByCaller(_::Mutex::SHARED);
cannam@49: #endif
cannam@49:   return value;
cannam@49: }
cannam@49: template <typename T>
cannam@49: inline T& MutexGuarded<T>::getAlreadyLockedShared() {
cannam@49: #ifdef KJ_DEBUG
cannam@49:   mutex.assertLockedByCaller(_::Mutex::SHARED);
cannam@49: #endif
cannam@49:   return value;
cannam@49: }
cannam@49: template <typename T>
cannam@49: inline T& MutexGuarded<T>::getAlreadyLockedExclusive() const {
cannam@49: #ifdef KJ_DEBUG
cannam@49:   mutex.assertLockedByCaller(_::Mutex::EXCLUSIVE);
cannam@49: #endif
cannam@49:   return const_cast<T&>(value);
cannam@49: }
cannam@49: 
cannam@49: template <typename T>
cannam@49: template <typename Func>
cannam@49: class Lazy<T>::InitImpl: public _::Once::Initializer {
cannam@49: public:
cannam@49:   inline InitImpl(const Lazy<T>& lazy, Func&& func): lazy(lazy), func(kj::fwd<Func>(func)) {}
cannam@49: 
cannam@49:   void run() override {
cannam@49:     lazy.value = func(lazy.space);
cannam@49:   }
cannam@49: 
cannam@49: private:
cannam@49:   const Lazy<T>& lazy;
cannam@49:   Func func;
cannam@49: };
cannam@49: 
cannam@49: template <typename T>
cannam@49: template <typename Func>
cannam@49: inline T& Lazy<T>::get(Func&& init) {
cannam@49:   if (!once.isInitialized()) {
cannam@49:     InitImpl<Func> initImpl(*this, kj::fwd<Func>(init));
cannam@49:     once.runOnce(initImpl);
cannam@49:   }
cannam@49:   return *value;
cannam@49: }
cannam@49: 
cannam@49: template <typename T>
cannam@49: template <typename Func>
cannam@49: inline const T& Lazy<T>::get(Func&& init) const {
cannam@49:   if (!once.isInitialized()) {
cannam@49:     InitImpl<Func> initImpl(*this, kj::fwd<Func>(init));
cannam@49:     once.runOnce(initImpl);
cannam@49:   }
cannam@49:   return *value;
cannam@49: }
cannam@49: 
cannam@49: }  // namespace kj
cannam@49: 
cannam@49: #endif  // KJ_MUTEX_H_