jpayne@69: // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
jpayne@69: // Licensed under the MIT License:
jpayne@69: //
jpayne@69: // Permission is hereby granted, free of charge, to any person obtaining a copy
jpayne@69: // of this software and associated documentation files (the "Software"), to deal
jpayne@69: // in the Software without restriction, including without limitation the rights
jpayne@69: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
jpayne@69: // copies of the Software, and to permit persons to whom the Software is
jpayne@69: // furnished to do so, subject to the following conditions:
jpayne@69: //
jpayne@69: // The above copyright notice and this permission notice shall be included in
jpayne@69: // all copies or substantial portions of the Software.
jpayne@69: //
jpayne@69: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
jpayne@69: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
jpayne@69: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
jpayne@69: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
jpayne@69: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
jpayne@69: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
jpayne@69: // THE SOFTWARE.
jpayne@69: 
jpayne@69: #pragma once
jpayne@69: 
jpayne@69: #include "debug.h"
jpayne@69: #include "memory.h"
jpayne@69: #include <inttypes.h>
jpayne@69: #include "time.h"
jpayne@69: #include "source-location.h"
jpayne@69: #include "one-of.h"
jpayne@69: 
jpayne@69: KJ_BEGIN_HEADER
jpayne@69: 
jpayne@69: #if __linux__ && !defined(KJ_USE_FUTEX)
jpayne@69: #define KJ_USE_FUTEX 1
jpayne@69: #endif
jpayne@69: 
jpayne@69: #if !KJ_USE_FUTEX && !_WIN32 && !__CYGWIN__
jpayne@69: // We fall back to pthreads when we don't have a better platform-specific primitive. pthreads
jpayne@69: // mutexes are bloated, though, so we like to avoid them. Hence on Linux we use futex(), and on
jpayne@69: // Windows we use SRW locks and friends. On Cygwin we prefer the Win32 primitives both because they
jpayne@69: // are more efficient and because I ran into problems with Cygwin's implementation of RW locks
jpayne@69: // seeming to allow multiple threads to lock the same mutex (but I didn't investigate very
jpayne@69: // closely).
jpayne@69: //
jpayne@69: // TODO(someday):  Write efficient low-level locking primitives for other platforms.
jpayne@69: #include <pthread.h>
jpayne@69: #endif
jpayne@69: 
jpayne@69: // There are 3 macros controlling lock tracking:
jpayne@69: // KJ_TRACK_LOCK_BLOCKING will set up async signal safe TLS variables that can be used to identify
jpayne@69: // the KJ primitive blocking the current thread.
jpayne@69: // KJ_SAVE_ACQUIRED_LOCK_INFO will allow introspection of a Mutex to get information about what is
jpayne@69: // currently holding the lock.
jpayne@69: // KJ_TRACK_LOCK_ACQUISITION is automatically enabled by either one of them.
jpayne@69: 
jpayne@69: #if KJ_TRACK_LOCK_BLOCKING
jpayne@69: // Lock tracking is required to keep track of what blocked.
jpayne@69: #define KJ_TRACK_LOCK_ACQUISITION 1
jpayne@69: #endif
jpayne@69: 
jpayne@69: #if KJ_SAVE_ACQUIRED_LOCK_INFO
jpayne@69: #define KJ_TRACK_LOCK_ACQUISITION 1
jpayne@69: #include <unistd.h>
jpayne@69: #endif
jpayne@69: 
jpayne@69: namespace kj {
jpayne@69: #if KJ_TRACK_LOCK_ACQUISITION
jpayne@69: #if !KJ_USE_FUTEX
jpayne@69: #error Lock tracking is only currently supported for futex-based mutexes.
jpayne@69: #endif
jpayne@69: 
jpayne@69: #if !KJ_COMPILER_SUPPORTS_SOURCE_LOCATION
jpayne@69: #error C++20 or newer is required (or the use of clang/gcc).
jpayne@69: #endif
jpayne@69: 
jpayne@69: using LockSourceLocation = SourceLocation;
jpayne@69: using LockSourceLocationArg = const SourceLocation&;
jpayne@69: // On x86-64 the codegen is optimal if the argument has type const& for the location. However,
jpayne@69: // since this conflicts with the optimal call signature for NoopSourceLocation,
jpayne@69: // LockSourceLocationArg is used to conditionally select the right type without polluting the usage
jpayne@69: // themselves. Interestingly this makes no difference on ARM.
jpayne@69: // https://godbolt.org/z/q6G8ee5a3
jpayne@69: #else
jpayne@69: using LockSourceLocation = NoopSourceLocation;
jpayne@69: using LockSourceLocationArg = NoopSourceLocation;
jpayne@69: #endif
jpayne@69: 
jpayne@69: 
jpayne@69: class Exception;
jpayne@69: 
jpayne@69: // =======================================================================================
jpayne@69: // Private details -- public interfaces follow below.
jpayne@69: 
jpayne@69: namespace _ {  // private
jpayne@69: 
jpayne@69: #if KJ_SAVE_ACQUIRED_LOCK_INFO
jpayne@69: class HoldingExclusively {
jpayne@69:   // The lock is being held in exclusive mode.
jpayne@69: public:
jpayne@69:   constexpr HoldingExclusively(pid_t tid, const SourceLocation& location)
jpayne@69:       : heldBy(tid), acquiredAt(location) {}
jpayne@69: 
jpayne@69:   pid_t threadHoldingLock() const { return heldBy; }
jpayne@69:   const SourceLocation& lockAcquiredAt() const { return acquiredAt; }
jpayne@69: 
jpayne@69: private:
jpayne@69:   pid_t heldBy;
jpayne@69:   SourceLocation acquiredAt;
jpayne@69: };
jpayne@69: 
jpayne@69: class HoldingShared {
jpayne@69:   // The lock is being held in shared mode currently. Which threads are holding this lock open
jpayne@69:   // is unknown.
jpayne@69: public:
jpayne@69:   constexpr HoldingShared(const SourceLocation& location) : acquiredAt(location) {}
jpayne@69: 
jpayne@69:   const SourceLocation& lockAcquiredAt() const { return acquiredAt; }
jpayne@69: 
jpayne@69: private:
jpayne@69:   SourceLocation acquiredAt;
jpayne@69: };
jpayne@69: #endif
jpayne@69: 
jpayne@69: class Mutex {
jpayne@69:   // Internal implementation details.  See `MutexGuarded<T>`.
jpayne@69: 
jpayne@69:   struct Waiter;
jpayne@69: 
jpayne@69: public:
jpayne@69:   Mutex();
jpayne@69:   ~Mutex();
jpayne@69:   KJ_DISALLOW_COPY_AND_MOVE(Mutex);
jpayne@69: 
jpayne@69:   enum Exclusivity {
jpayne@69:     EXCLUSIVE,
jpayne@69:     SHARED
jpayne@69:   };
jpayne@69: 
jpayne@69:   bool lock(Exclusivity exclusivity, Maybe<Duration> timeout, LockSourceLocationArg location);
jpayne@69:   void unlock(Exclusivity exclusivity, Waiter* waiterToSkip = nullptr);
jpayne@69: 
jpayne@69:   void assertLockedByCaller(Exclusivity exclusivity) const;
jpayne@69:   // In debug mode, assert that the mutex is locked by the calling thread, or if that is
jpayne@69:   // non-trivial, assert that the mutex is locked (which should be good enough to catch problems
jpayne@69:   // in unit tests).  In non-debug builds, do nothing.
jpayne@69: 
jpayne@69:   class Predicate {
jpayne@69:   public:
jpayne@69:     virtual bool check() = 0;
jpayne@69:   };
jpayne@69: 
jpayne@69:   void wait(Predicate& predicate, Maybe<Duration> timeout, LockSourceLocationArg location);
jpayne@69:   // If predicate.check() returns false, unlock the mutex until predicate.check() returns true, or
jpayne@69:   // when the timeout (if any) expires. The mutex is always re-locked when this returns regardless
jpayne@69:   // of whether the timeout expired, and including if it throws.
jpayne@69:   //
jpayne@69:   // Requires that the mutex is already exclusively locked before calling.
jpayne@69: 
jpayne@69:   void induceSpuriousWakeupForTest();
jpayne@69:   // Utility method for mutex-test.c++ which causes a spurious thread wakeup on all threads that
jpayne@69:   // are waiting for a wait() condition. Assuming correct implementation, all those threads
jpayne@69:   // should immediately go back to sleep.
jpayne@69: 
jpayne@69: #if KJ_USE_FUTEX
jpayne@69:   uint numReadersWaitingForTest() const;
jpayne@69:   // The number of reader locks that are currently blocked on this lock (must be called while
jpayne@69:   // holding the writer lock). This is really only a utility method for mutex-test.c++ so it can
jpayne@69:   // validate certain invariants.
jpayne@69: #endif
jpayne@69: 
jpayne@69: #if KJ_SAVE_ACQUIRED_LOCK_INFO
jpayne@69:   using AcquiredMetadata = kj::OneOf<HoldingExclusively, HoldingShared>;
jpayne@69:   KJ_DISABLE_TSAN AcquiredMetadata lockedInfo() const;
jpayne@69:   // Returns metadata about this lock when its held. This method is async signal safe. It must also
jpayne@69:   // be called in a state where it's guaranteed that the lock state won't be released by another
jpayne@69:   // thread. In other words this has to be called from the signal handler within the thread that's
jpayne@69:   // holding the lock.
jpayne@69: #endif
jpayne@69: 
jpayne@69: private:
jpayne@69: #if KJ_USE_FUTEX
jpayne@69:   uint futex;
jpayne@69:   // bit 31 (msb) = set if exclusive lock held
jpayne@69:   // bit 30 (msb) = set if threads are waiting for exclusive lock
jpayne@69:   // bits 0-29 = count of readers; If an exclusive lock is held, this is the count of threads
jpayne@69:   //   waiting for a read lock, otherwise it is the count of threads that currently hold a read
jpayne@69:   //   lock.
jpayne@69: 
jpayne@69: #ifdef KJ_CONTENTION_WARNING_THRESHOLD
jpayne@69:   bool printContendedReader = false;
jpayne@69: #endif
jpayne@69: 
jpayne@69:   static constexpr uint EXCLUSIVE_HELD = 1u << 31;
jpayne@69:   static constexpr uint EXCLUSIVE_REQUESTED = 1u << 30;
jpayne@69:   static constexpr uint SHARED_COUNT_MASK = EXCLUSIVE_REQUESTED - 1;
jpayne@69: 
jpayne@69: #elif _WIN32 || __CYGWIN__
jpayne@69:   uintptr_t srwLock;  // Actually an SRWLOCK, but don't want to #include <windows.h> in header.
jpayne@69: 
jpayne@69: #else
jpayne@69:   mutable pthread_rwlock_t mutex;
jpayne@69: #endif
jpayne@69: 
jpayne@69: #if KJ_SAVE_ACQUIRED_LOCK_INFO
jpayne@69:   pid_t lockedExclusivelyByThread = 0;
jpayne@69:   SourceLocation lockAcquiredLocation;
jpayne@69: 
jpayne@69:   KJ_DISABLE_TSAN void acquiredExclusive(pid_t tid, const SourceLocation& location) noexcept {
jpayne@69:     lockAcquiredLocation = location;
jpayne@69:     __atomic_store_n(&lockedExclusivelyByThread, tid, __ATOMIC_RELAXED);
jpayne@69:   }
jpayne@69: 
jpayne@69:   KJ_DISABLE_TSAN void acquiredShared(const SourceLocation& location) noexcept {
jpayne@69:     lockAcquiredLocation = location;
jpayne@69:   }
jpayne@69: 
jpayne@69:   KJ_DISABLE_TSAN SourceLocation releasingExclusive() noexcept {
jpayne@69:     auto tmp = lockAcquiredLocation;
jpayne@69:     lockAcquiredLocation = SourceLocation{};
jpayne@69:     lockedExclusivelyByThread = 0;
jpayne@69:     return tmp;
jpayne@69:   }
jpayne@69: #else
jpayne@69:   static constexpr void acquiredExclusive(uint, LockSourceLocationArg) {}
jpayne@69:   static constexpr void acquiredShared(LockSourceLocationArg) {}
jpayne@69:   static constexpr NoopSourceLocation releasingExclusive() { return NoopSourceLocation{}; }
jpayne@69: #endif
jpayne@69:   struct Waiter {
jpayne@69:     kj::Maybe<Waiter&> next;
jpayne@69:     kj::Maybe<Waiter&>* prev;
jpayne@69:     Predicate& predicate;
jpayne@69:     Maybe<Own<Exception>> exception;
jpayne@69: #if KJ_USE_FUTEX
jpayne@69:     uint futex;
jpayne@69:     bool hasTimeout;
jpayne@69: #elif _WIN32 || __CYGWIN__
jpayne@69:     uintptr_t condvar;
jpayne@69:     // Actually CONDITION_VARIABLE, but don't want to #include <windows.h> in header.
jpayne@69: #else
jpayne@69:     pthread_cond_t condvar;
jpayne@69: 
jpayne@69:     pthread_mutex_t stupidMutex;
jpayne@69:     // pthread condvars are only compatible with basic pthread mutexes, not rwlocks, for no
jpayne@69:     // particularly good reason. To work around this, we need an extra mutex per condvar.
jpayne@69: #endif
jpayne@69:   };
jpayne@69: 
jpayne@69:   kj::Maybe<Waiter&> waitersHead = nullptr;
jpayne@69:   kj::Maybe<Waiter&>* waitersTail = &waitersHead;
jpayne@69:   // linked list of waiters; can only modify under lock
jpayne@69: 
jpayne@69:   inline void addWaiter(Waiter& waiter);
jpayne@69:   inline void removeWaiter(Waiter& waiter);
jpayne@69:   bool checkPredicate(Waiter& waiter);
jpayne@69: #if _WIN32 || __CYGWIN__
jpayne@69:   void wakeReadyWaiter(Waiter* waiterToSkip);
jpayne@69: #endif
jpayne@69: };
jpayne@69: 
jpayne@69: class Once {
jpayne@69:   // Internal implementation details.  See `Lazy<T>`.
jpayne@69: 
jpayne@69: public:
jpayne@69: #if KJ_USE_FUTEX
jpayne@69:   inline Once(bool startInitialized = false)
jpayne@69:       : futex(startInitialized ? INITIALIZED : UNINITIALIZED) {}
jpayne@69: #else
jpayne@69:   Once(bool startInitialized = false);
jpayne@69:   ~Once();
jpayne@69: #endif
jpayne@69:   KJ_DISALLOW_COPY_AND_MOVE(Once);
jpayne@69: 
jpayne@69:   class Initializer {
jpayne@69:   public:
jpayne@69:     virtual void run() = 0;
jpayne@69:   };
jpayne@69: 
jpayne@69:   void runOnce(Initializer& init, LockSourceLocationArg location);
jpayne@69: 
jpayne@69: #if _WIN32 || __CYGWIN__  // TODO(perf): Can we make this inline on win32 somehow?
jpayne@69:   bool isInitialized() noexcept;
jpayne@69: 
jpayne@69: #else
jpayne@69:   inline bool isInitialized() noexcept {
jpayne@69:     // Fast path check to see if runOnce() would simply return immediately.
jpayne@69: #if KJ_USE_FUTEX
jpayne@69:     return __atomic_load_n(&futex, __ATOMIC_ACQUIRE) == INITIALIZED;
jpayne@69: #else
jpayne@69:     return __atomic_load_n(&state, __ATOMIC_ACQUIRE) == INITIALIZED;
jpayne@69: #endif
jpayne@69:   }
jpayne@69: #endif
jpayne@69: 
jpayne@69:   void reset();
jpayne@69:   // Returns the state from initialized to uninitialized.  It is an error to call this when
jpayne@69:   // not already initialized, or when runOnce() or isInitialized() might be called concurrently in
jpayne@69:   // another thread.
jpayne@69: 
jpayne@69: private:
jpayne@69: #if KJ_USE_FUTEX
jpayne@69:   uint futex;
jpayne@69: 
jpayne@69:   enum State {
jpayne@69:     UNINITIALIZED,
jpayne@69:     INITIALIZING,
jpayne@69:     INITIALIZING_WITH_WAITERS,
jpayne@69:     INITIALIZED
jpayne@69:   };
jpayne@69: 
jpayne@69: #elif _WIN32 || __CYGWIN__
jpayne@69:   uintptr_t initOnce;  // Actually an INIT_ONCE, but don't want to #include <windows.h> in header.
jpayne@69: 
jpayne@69: #else
jpayne@69:   enum State {
jpayne@69:     UNINITIALIZED,
jpayne@69:     INITIALIZED
jpayne@69:   };
jpayne@69:   State state;
jpayne@69:   pthread_mutex_t mutex;
jpayne@69: #endif
jpayne@69: };
jpayne@69: 
jpayne@69: }  // namespace _ (private)
jpayne@69: 
jpayne@69: // =======================================================================================
jpayne@69: // Public interface
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: class Locked {
jpayne@69:   // Return type for `MutexGuarded<T>::lock()`.  `Locked<T>` provides access to the bounded object
jpayne@69:   // and unlocks the mutex when it goes out of scope.
jpayne@69: 
jpayne@69: public:
jpayne@69:   KJ_DISALLOW_COPY(Locked);
jpayne@69:   inline Locked(): mutex(nullptr), ptr(nullptr) {}
jpayne@69:   inline Locked(Locked&& other): mutex(other.mutex), ptr(other.ptr) {
jpayne@69:     other.mutex = nullptr;
jpayne@69:     other.ptr = nullptr;
jpayne@69:   }
jpayne@69:   inline ~Locked() {
jpayne@69:     if (mutex != nullptr) mutex->unlock(isConst<T>() ? _::Mutex::SHARED : _::Mutex::EXCLUSIVE);
jpayne@69:   }
jpayne@69: 
jpayne@69:   inline Locked& operator=(Locked&& other) {
jpayne@69:     if (mutex != nullptr) mutex->unlock(isConst<T>() ? _::Mutex::SHARED : _::Mutex::EXCLUSIVE);
jpayne@69:     mutex = other.mutex;
jpayne@69:     ptr = other.ptr;
jpayne@69:     other.mutex = nullptr;
jpayne@69:     other.ptr = nullptr;
jpayne@69:     return *this;
jpayne@69:   }
jpayne@69: 
jpayne@69:   inline void release() {
jpayne@69:     if (mutex != nullptr) mutex->unlock(isConst<T>() ? _::Mutex::SHARED : _::Mutex::EXCLUSIVE);
jpayne@69:     mutex = nullptr;
jpayne@69:     ptr = nullptr;
jpayne@69:   }
jpayne@69: 
jpayne@69:   inline T* operator->() { return ptr; }
jpayne@69:   inline const T* operator->() const { return ptr; }
jpayne@69:   inline T& operator*() { return *ptr; }
jpayne@69:   inline const T& operator*() const { return *ptr; }
jpayne@69:   inline T* get() { return ptr; }
jpayne@69:   inline const T* get() const { return ptr; }
jpayne@69:   inline operator T*() { return ptr; }
jpayne@69:   inline operator const T*() const { return ptr; }
jpayne@69: 
jpayne@69:   template <typename Cond>
jpayne@69:   void wait(Cond&& condition, Maybe<Duration> timeout = nullptr,
jpayne@69:       LockSourceLocationArg location = {}) {
jpayne@69:     // Unlocks the lock until `condition(state)` evaluates true (where `state` is type `const T&`
jpayne@69:     // referencing the object protected by the lock).
jpayne@69: 
jpayne@69:     // We can't wait on a shared lock because the internal bookkeeping needed for a wait requires
jpayne@69:     // the protection of an exclusive lock.
jpayne@69:     static_assert(!isConst<T>(), "cannot wait() on shared lock");
jpayne@69: 
jpayne@69:     struct PredicateImpl final: public _::Mutex::Predicate {
jpayne@69:       bool check() override {
jpayne@69:         return condition(value);
jpayne@69:       }
jpayne@69: 
jpayne@69:       Cond&& condition;
jpayne@69:       const T& value;
jpayne@69: 
jpayne@69:       PredicateImpl(Cond&& condition, const T& value)
jpayne@69:           : condition(kj::fwd<Cond>(condition)), value(value) {}
jpayne@69:     };
jpayne@69: 
jpayne@69:     PredicateImpl impl(kj::fwd<Cond>(condition), *ptr);
jpayne@69:     mutex->wait(impl, timeout, location);
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   _::Mutex* mutex;
jpayne@69:   T* ptr;
jpayne@69: 
jpayne@69:   inline Locked(_::Mutex& mutex, T& value): mutex(&mutex), ptr(&value) {}
jpayne@69: 
jpayne@69:   template <typename U>
jpayne@69:   friend class MutexGuarded;
jpayne@69:   template <typename U>
jpayne@69:   friend class ExternalMutexGuarded;
jpayne@69: 
jpayne@69: #if KJ_MUTEX_TEST
jpayne@69: public:
jpayne@69: #endif
jpayne@69:   void induceSpuriousWakeupForTest() { mutex->induceSpuriousWakeupForTest(); }
jpayne@69:   // Utility method for mutex-test.c++ which causes a spurious thread wakeup on all threads that
jpayne@69:   // are waiting for a when() condition. Assuming correct implementation, all those threads should
jpayne@69:   // immediately go back to sleep.
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: class MutexGuarded {
jpayne@69:   // An object of type T, bounded by a mutex.  In order to access the object, you must lock it.
jpayne@69:   //
jpayne@69:   // Write locks are not "recursive" -- trying to lock again in a thread that already holds a lock
jpayne@69:   // will deadlock.  Recursive write locks are usually a sign of bad design.
jpayne@69:   //
jpayne@69:   // Unfortunately, **READ LOCKS ARE NOT RECURSIVE** either.  Common sense says they should be.
jpayne@69:   // But on many operating systems (BSD, OSX), recursively read-locking a pthread_rwlock is
jpayne@69:   // actually unsafe.  The problem is that writers are "prioritized" over readers, so a read lock
jpayne@69:   // request will block if any write lock requests are outstanding.  So, if thread A takes a read
jpayne@69:   // lock, thread B requests a write lock (and starts waiting), and then thread A tries to take
jpayne@69:   // another read lock recursively, the result is deadlock.
jpayne@69: 
jpayne@69: public:
jpayne@69:   template <typename... Params>
jpayne@69:   explicit MutexGuarded(Params&&... params);
jpayne@69:   // Initialize the mutex-bounded object by passing the given parameters to its constructor.
jpayne@69: 
jpayne@69:   Locked<T> lockExclusive(LockSourceLocationArg location = {}) const;
jpayne@69:   // Exclusively locks the object and returns it.  The returned `Locked<T>` can be passed by
jpayne@69:   // move, similar to `Own<T>`.
jpayne@69:   //
jpayne@69:   // This method is declared `const` in accordance with KJ style rules which say that constness
jpayne@69:   // should be used to indicate thread-safety.  It is safe to share a const pointer between threads,
jpayne@69:   // but it is not safe to share a mutable pointer.  Since the whole point of MutexGuarded is to
jpayne@69:   // be shared between threads, its methods should be const, even though locking it produces a
jpayne@69:   // non-const pointer to the contained object.
jpayne@69: 
jpayne@69:   Locked<const T> lockShared(LockSourceLocationArg location = {}) const;
jpayne@69:   // Lock the value for shared access.  Multiple shared locks can be taken concurrently, but cannot
jpayne@69:   // be held at the same time as a non-shared lock.
jpayne@69: 
jpayne@69:   Maybe<Locked<T>> lockExclusiveWithTimeout(Duration timeout,
jpayne@69:       LockSourceLocationArg location = {}) const;
jpayne@69:   // Attempts to exclusively lock the object. If the timeout elapses before the lock is acquired,
jpayne@69:   // this returns null.
jpayne@69: 
jpayne@69:   Maybe<Locked<const T>> lockSharedWithTimeout(Duration timeout,
jpayne@69:       LockSourceLocationArg location = {}) const;
jpayne@69:   // Attempts to lock the value for shared access. If the timeout elapses before the lock is acquired,
jpayne@69:   // this returns null.
jpayne@69: 
jpayne@69:   inline const T& getWithoutLock() const { return value; }
jpayne@69:   inline T& getWithoutLock() { return value; }
jpayne@69:   // Escape hatch for cases where some external factor guarantees that it's safe to get the
jpayne@69:   // value.  You should treat these like const_cast -- be highly suspicious of any use.
jpayne@69: 
jpayne@69:   inline const T& getAlreadyLockedShared() const;
jpayne@69:   inline T& getAlreadyLockedShared();
jpayne@69:   inline T& getAlreadyLockedExclusive() const;
jpayne@69:   // Like `getWithoutLock()`, but asserts that the lock is already held by the calling thread.
jpayne@69: 
jpayne@69:   template <typename Cond, typename Func>
jpayne@69:   auto when(Cond&& condition, Func&& callback, Maybe<Duration> timeout = nullptr,
jpayne@69:       LockSourceLocationArg location = {}) const
jpayne@69:       -> decltype(callback(instance<T&>())) {
jpayne@69:     // Waits until condition(state) returns true, then calls callback(state) under lock.
jpayne@69:     //
jpayne@69:     // `condition`, when called, receives as its parameter a const reference to the state, which is
jpayne@69:     // locked (either shared or exclusive). `callback` receives a mutable reference, which is
jpayne@69:     // exclusively locked.
jpayne@69:     //
jpayne@69:     // `condition()` may be called multiple times, from multiple threads, while waiting for the
jpayne@69:     // condition to become true. It may even return true once, but then be called more times.
jpayne@69:     // It is guaranteed, though, that at the time `callback()` is finally called, `condition()`
jpayne@69:     // would currently return true (assuming it is a pure function of the guarded data).
jpayne@69:     //
jpayne@69:     // If `timeout` is specified, then after the given amount of time, the callback will be called
jpayne@69:     // regardless of whether the condition is true. In this case, when `callback()` is called,
jpayne@69:     // `condition()` may in fact evaluate false, but *only* if the timeout was reached.
jpayne@69:     //
jpayne@69:     // TODO(cleanup): lock->wait() is a better interface. Can we deprecate this one?
jpayne@69: 
jpayne@69:     auto lock = lockExclusive();
jpayne@69:     lock.wait(kj::fwd<Cond>(condition), timeout, location);
jpayne@69:     return callback(value);
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   mutable _::Mutex mutex;
jpayne@69:   mutable T value;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: class MutexGuarded<const T> {
jpayne@69:   // MutexGuarded cannot guard a const type.  This would be pointless anyway, and would complicate
jpayne@69:   // the implementation of Locked<T>, which uses constness to decide what kind of lock it holds.
jpayne@69:   static_assert(sizeof(T) < 0, "MutexGuarded's type cannot be const.");
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: class ExternalMutexGuarded {
jpayne@69:   // Holds a value that can only be manipulated while some other mutex is locked.
jpayne@69:   //
jpayne@69:   // The ExternalMutexGuarded<T> lives *outside* the scope of any lock on the mutex, but ensures
jpayne@69:   // that the value it holds can only be accessed under lock by forcing the caller to present a
jpayne@69:   // lock before accessing the value.
jpayne@69:   //
jpayne@69:   // Additionally, ExternalMutexGuarded<T>'s destructor will take an exclusive lock on the mutex
jpayne@69:   // while destroying the held value, unless the value has been release()ed before hand.
jpayne@69:   //
jpayne@69:   // The type T must have the following properties (which probably all movable types satisfy):
jpayne@69:   // - T is movable.
jpayne@69:   // - Immediately after any of the following has happened, T's destructor is effectively a no-op
jpayne@69:   //   (hence certainly not requiring locks):
jpayne@69:   //   - The value has been default-constructed.
jpayne@69:   //   - The value has been initialized by-move from a default-constructed T.
jpayne@69:   //   - The value has been moved away.
jpayne@69:   // - If ExternalMutexGuarded<T> is ever moved, then T must have a move constructor and move
jpayne@69:   //   assignment operator that do not follow any pointers, therefore do not need to take a lock.
jpayne@69:   //
jpayne@69:   // Inherits from LockSourceLocation to perform an empty base class optimization when lock tracking
jpayne@69:   // is compiled out. Once the minimum C++ standard for the KJ library is C++20, this optimization
jpayne@69:   // could be replaced by a member variable with a [[no_unique_address]] annotation.
jpayne@69: public:
jpayne@69:   ExternalMutexGuarded(LockSourceLocationArg location = {})
jpayne@69:       : location(location) {}
jpayne@69: 
jpayne@69:   template <typename U, typename... Params>
jpayne@69:   ExternalMutexGuarded(Locked<U> lock, Params&&... params, LockSourceLocationArg location = {})
jpayne@69:       : mutex(lock.mutex),
jpayne@69:         value(kj::fwd<Params>(params)...),
jpayne@69:         location(location) {}
jpayne@69:   // Construct the value in-place. This constructor requires passing ownership of the lock into
jpayne@69:   // the constructor. Normally this should be a lock that you take on the line calling the
jpayne@69:   // constructor, like:
jpayne@69:   //
jpayne@69:   //     ExternalMutexGuarded<T> foo(someMutexGuarded.lockExclusive());
jpayne@69:   //
jpayne@69:   // The reason this constructor does not accept an lvalue reference to an existing lock is because
jpayne@69:   // this would be deadlock-prone: If an exception were thrown immediately after the constructor
jpayne@69:   // completed, then the destructor would deadlock, because the lock would still be held. An
jpayne@69:   // ExternalMutexGuarded must live outside the scope of any locks to avoid such a deadlock.
jpayne@69: 
jpayne@69:   ~ExternalMutexGuarded() noexcept(false) {
jpayne@69:     if (mutex != nullptr) {
jpayne@69:       mutex->lock(_::Mutex::EXCLUSIVE, nullptr, location);
jpayne@69:       KJ_DEFER(mutex->unlock(_::Mutex::EXCLUSIVE));
jpayne@69:       value = T();
jpayne@69:     }
jpayne@69:   }
jpayne@69: 
jpayne@69:   ExternalMutexGuarded(ExternalMutexGuarded&& other)
jpayne@69:       : mutex(other.mutex), value(kj::mv(other.value)), location(other.location) {
jpayne@69:     other.mutex = nullptr;
jpayne@69:   }
jpayne@69:   ExternalMutexGuarded& operator=(ExternalMutexGuarded&& other) {
jpayne@69:     mutex = other.mutex;
jpayne@69:     value = kj::mv(other.value);
jpayne@69:     location = other.location;
jpayne@69:     other.mutex = nullptr;
jpayne@69:     return *this;
jpayne@69:   }
jpayne@69: 
jpayne@69:   template <typename U>
jpayne@69:   void set(Locked<U>& lock, T&& newValue) {
jpayne@69:     KJ_IREQUIRE(mutex == nullptr);
jpayne@69:     mutex = lock.mutex;
jpayne@69:     value = kj::mv(newValue);
jpayne@69:   }
jpayne@69: 
jpayne@69:   template <typename U>
jpayne@69:   T& get(Locked<U>& lock) {
jpayne@69:     KJ_IREQUIRE(lock.mutex == mutex);
jpayne@69:     return value;
jpayne@69:   }
jpayne@69: 
jpayne@69:   template <typename U>
jpayne@69:   const T& get(Locked<const U>& lock) const {
jpayne@69:     KJ_IREQUIRE(lock.mutex == mutex);
jpayne@69:     return value;
jpayne@69:   }
jpayne@69: 
jpayne@69:   template <typename U>
jpayne@69:   T release(Locked<U>& lock) {
jpayne@69:     // Release (move away) the value. This allows the destructor to skip locking the mutex.
jpayne@69:     KJ_IREQUIRE(lock.mutex == mutex);
jpayne@69:     T result = kj::mv(value);
jpayne@69:     mutex = nullptr;
jpayne@69:     return result;
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   _::Mutex* mutex = nullptr;
jpayne@69:   T value;
jpayne@69:   KJ_NO_UNIQUE_ADDRESS LockSourceLocation location;
jpayne@69:   // When built against C++20 (or clang >= 9.0), the overhead of this is elided. Otherwise this
jpayne@69:   // struct will be 1 byte larger than it would otherwise be.
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: class Lazy {
jpayne@69:   // A lazily-initialized value.
jpayne@69: 
jpayne@69: public:
jpayne@69:   template <typename Func>
jpayne@69:   T& get(Func&& init, LockSourceLocationArg location = {});
jpayne@69:   template <typename Func>
jpayne@69:   const T& get(Func&& init, LockSourceLocationArg location = {}) const;
jpayne@69:   // The first thread to call get() will invoke the given init function to construct the value.
jpayne@69:   // Other threads will block until construction completes, then return the same value.
jpayne@69:   //
jpayne@69:   // `init` is a functor(typically a lambda) which takes `SpaceFor<T>&` as its parameter and returns
jpayne@69:   // `Own<T>`.  If `init` throws an exception, the exception is propagated out of that thread's
jpayne@69:   // call to `get()`, and subsequent calls behave as if `get()` hadn't been called at all yet --
jpayne@69:   // in other words, subsequent calls retry initialization until it succeeds.
jpayne@69: 
jpayne@69: private:
jpayne@69:   mutable _::Once once;
jpayne@69:   mutable SpaceFor<T> space;
jpayne@69:   mutable Own<T> value;
jpayne@69: 
jpayne@69:   template <typename Func>
jpayne@69:   class InitImpl;
jpayne@69: };
jpayne@69: 
jpayne@69: // =======================================================================================
jpayne@69: // Inline implementation details
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: template <typename... Params>
jpayne@69: inline MutexGuarded<T>::MutexGuarded(Params&&... params)
jpayne@69:     : value(kj::fwd<Params>(params)...) {}
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: inline Locked<T> MutexGuarded<T>::lockExclusive(LockSourceLocationArg location)
jpayne@69:     const {
jpayne@69:   mutex.lock(_::Mutex::EXCLUSIVE, nullptr, location);
jpayne@69:   return Locked<T>(mutex, value);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: inline Locked<const T> MutexGuarded<T>::lockShared(LockSourceLocationArg location) const {
jpayne@69:   mutex.lock(_::Mutex::SHARED, nullptr, location);
jpayne@69:   return Locked<const T>(mutex, value);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: inline Maybe<Locked<T>> MutexGuarded<T>::lockExclusiveWithTimeout(Duration timeout,
jpayne@69:     LockSourceLocationArg location) const {
jpayne@69:   if (mutex.lock(_::Mutex::EXCLUSIVE, timeout, location)) {
jpayne@69:     return Locked<T>(mutex, value);
jpayne@69:   } else {
jpayne@69:     return nullptr;
jpayne@69:   }
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: inline Maybe<Locked<const T>> MutexGuarded<T>::lockSharedWithTimeout(Duration timeout,
jpayne@69:     LockSourceLocationArg location) const {
jpayne@69:   if (mutex.lock(_::Mutex::SHARED, timeout, location)) {
jpayne@69:     return Locked<const T>(mutex, value);
jpayne@69:   } else {
jpayne@69:     return nullptr;
jpayne@69:   }
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: inline const T& MutexGuarded<T>::getAlreadyLockedShared() const {
jpayne@69: #ifdef KJ_DEBUG
jpayne@69:   mutex.assertLockedByCaller(_::Mutex::SHARED);
jpayne@69: #endif
jpayne@69:   return value;
jpayne@69: }
jpayne@69: template <typename T>
jpayne@69: inline T& MutexGuarded<T>::getAlreadyLockedShared() {
jpayne@69: #ifdef KJ_DEBUG
jpayne@69:   mutex.assertLockedByCaller(_::Mutex::SHARED);
jpayne@69: #endif
jpayne@69:   return value;
jpayne@69: }
jpayne@69: template <typename T>
jpayne@69: inline T& MutexGuarded<T>::getAlreadyLockedExclusive() const {
jpayne@69: #ifdef KJ_DEBUG
jpayne@69:   mutex.assertLockedByCaller(_::Mutex::EXCLUSIVE);
jpayne@69: #endif
jpayne@69:   return const_cast<T&>(value);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: template <typename Func>
jpayne@69: class Lazy<T>::InitImpl: public _::Once::Initializer {
jpayne@69: public:
jpayne@69:   inline InitImpl(const Lazy<T>& lazy, Func&& func): lazy(lazy), func(kj::fwd<Func>(func)) {}
jpayne@69: 
jpayne@69:   void run() override {
jpayne@69:     lazy.value = func(lazy.space);
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   const Lazy<T>& lazy;
jpayne@69:   Func func;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: template <typename Func>
jpayne@69: inline T& Lazy<T>::get(Func&& init, LockSourceLocationArg location) {
jpayne@69:   if (!once.isInitialized()) {
jpayne@69:     InitImpl<Func> initImpl(*this, kj::fwd<Func>(init));
jpayne@69:     once.runOnce(initImpl, location);
jpayne@69:   }
jpayne@69:   return *value;
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: template <typename Func>
jpayne@69: inline const T& Lazy<T>::get(Func&& init, LockSourceLocationArg location) const {
jpayne@69:   if (!once.isInitialized()) {
jpayne@69:     InitImpl<Func> initImpl(*this, kj::fwd<Func>(init));
jpayne@69:     once.runOnce(initImpl, location);
jpayne@69:   }
jpayne@69:   return *value;
jpayne@69: }
jpayne@69: 
jpayne@69: #if KJ_TRACK_LOCK_BLOCKING
jpayne@69: struct BlockedOnMutexAcquisition {
jpayne@69:   const _::Mutex& mutex;
jpayne@69:   // The mutex we are blocked on.
jpayne@69: 
jpayne@69:   const SourceLocation& origin;
jpayne@69:   // Where did the blocking operation originate from.
jpayne@69: };
jpayne@69: 
jpayne@69: struct BlockedOnCondVarWait {
jpayne@69:   const _::Mutex& mutex;
jpayne@69:   // The mutex the condition variable is using (may or may not be locked).
jpayne@69: 
jpayne@69:   const void* waiter;
jpayne@69:   // Pointer to the waiter that's being waited on.
jpayne@69: 
jpayne@69:   const SourceLocation& origin;
jpayne@69:   // Where did the blocking operation originate from.
jpayne@69: };
jpayne@69: 
jpayne@69: struct BlockedOnOnceInit {
jpayne@69:   const _::Once& once;
jpayne@69: 
jpayne@69:   const SourceLocation& origin;
jpayne@69:   // Where did the blocking operation originate from.
jpayne@69: };
jpayne@69: 
jpayne@69: using BlockedOnReason = OneOf<BlockedOnMutexAcquisition, BlockedOnCondVarWait, BlockedOnOnceInit>;
jpayne@69: 
jpayne@69: Maybe<const BlockedOnReason&> blockedReason() noexcept;
jpayne@69: // Returns the information about the reason the current thread is blocked synchronously on KJ
jpayne@69: // lock primitives. Returns nullptr if the current thread is not currently blocked on such
jpayne@69: // primitives. This is intended to be called from a signal handler to check whether the current
jpayne@69: // thread is blocked. Outside of a signal handler there is little value to this function. In those
jpayne@69: // cases by definition the thread is not blocked. This includes the callable used as part of a
jpayne@69: // condition variable since that happens after the lock is acquired & the current thread is no
jpayne@69: // longer blocked). The utility could be made useful for non-signal handler use-cases by being able
jpayne@69: // to fetch the pointer to the TLS variable directly (i.e. const BlockedOnReason&*). However, there
jpayne@69: // would have to be additional changes/complexity to try make that work since you'd need
jpayne@69: // synchronization to ensure that the memory you'd try to reference is still valid. The likely
jpayne@69: // solution would be to make these mutually exclusive options where you can use either the fast
jpayne@69: // async-safe option, or a mutex-guarded TLS variable you can get a reference to that isn't
jpayne@69: // async-safe. That being said, maybe someone can come up with a way to make something that works
jpayne@69: // in both use-cases which would of course be more preferable.
jpayne@69: #endif
jpayne@69: 
jpayne@69: 
jpayne@69: }  // namespace kj
jpayne@69: 
jpayne@69: KJ_END_HEADER