chromium/third_party/abseil-cpp/absl/synchronization/mutex.h

// Copyright 2017 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// -----------------------------------------------------------------------------
// mutex.h
// -----------------------------------------------------------------------------
//
// This header file defines a `Mutex` -- a mutually exclusive lock -- and the
// most common type of synchronization primitive for facilitating locks on
// shared resources. A mutex is used to prevent multiple threads from accessing
// and/or writing to a shared resource concurrently.
//
// Unlike a `std::mutex`, the Abseil `Mutex` provides the following additional
// features:
//   * Conditional predicates intrinsic to the `Mutex` object
//   * Shared/reader locks, in addition to standard exclusive/writer locks
//   * Deadlock detection and debug support.
//
// The following helper classes are also defined within this file:
//
//  MutexLock - An RAII wrapper to acquire and release a `Mutex` for exclusive/
//              write access within the current scope.
//
//  ReaderMutexLock
//            - An RAII wrapper to acquire and release a `Mutex` for shared/read
//              access within the current scope.
//
//  WriterMutexLock
//            - Effectively an alias for `MutexLock` above, designed for use in
//              distinguishing reader and writer locks within code.
//
// In addition to simple mutex locks, this file also defines ways to perform
// locking under certain conditions.
//
//  Condition - (Preferred) Used to wait for a particular predicate that
//              depends on state protected by the `Mutex` to become true.
//  CondVar   - A lower-level variant of `Condition` that relies on
//              application code to explicitly signal the `CondVar` when
//              a condition has been met.
//
// See below for more information on using `Condition` or `CondVar`.
//
// Mutexes and mutex behavior can be quite complicated. The information within
// this header file is limited, as a result. Please consult the Mutex guide for
// more complete information and examples.

#ifndef ABSL_SYNCHRONIZATION_MUTEX_H_
#define ABSL_SYNCHRONIZATION_MUTEX_H_

#include <atomic>
#include <cstdint>
#include <cstring>
#include <iterator>
#include <string>

#include "absl/base/attributes.h"
#include "absl/base/const_init.h"
#include "absl/base/internal/identity.h"
#include "absl/base/internal/low_level_alloc.h"
#include "absl/base/internal/thread_identity.h"
#include "absl/base/internal/tsan_mutex_interface.h"
#include "absl/base/port.h"
#include "absl/base/thread_annotations.h"
#include "absl/synchronization/internal/kernel_timeout.h"
#include "absl/synchronization/internal/per_thread_sem.h"
#include "absl/time/time.h"

namespace absl {
ABSL_NAMESPACE_BEGIN

class Condition;
struct SynchWaitParams;

// -----------------------------------------------------------------------------
// Mutex
// -----------------------------------------------------------------------------
//
// A `Mutex` is a non-reentrant (aka non-recursive) Mutually Exclusive lock
// on some resource, typically a variable or data structure with associated
// invariants. Proper usage of mutexes prevents concurrent access by different
// threads to the same resource.
//
// A `Mutex` has two basic operations: `Mutex::Lock()` and `Mutex::Unlock()`.
// The `Lock()` operation *acquires* a `Mutex` (in a state known as an
// *exclusive* -- or *write* -- lock), and the `Unlock()` operation *releases* a
// Mutex. During the span of time between the Lock() and Unlock() operations,
// a mutex is said to be *held*. By design, all mutexes support exclusive/write
// locks, as this is the most common way to use a mutex.
//
// Mutex operations are only allowed under certain conditions; otherwise an
// operation is "invalid", and disallowed by the API. The conditions concern
// both the current state of the mutex and the identity of the threads that
// are performing the operations.
//
// The `Mutex` state machine for basic lock/unlock operations is quite simple:
//
// |                | Lock()                 | Unlock() |
// |----------------+------------------------+----------|
// | Free           | Exclusive              | invalid  |
// | Exclusive      | blocks, then exclusive | Free     |
//
// The full conditions are as follows.
//
// * Calls to `Unlock()` require that the mutex be held, and must be made in the
//   same thread that performed the corresponding `Lock()` operation which
//   acquired the mutex; otherwise the call is invalid.
//
// * The mutex being non-reentrant (or non-recursive) means that a call to
//   `Lock()` or `TryLock()` must not be made in a thread that already holds the
//   mutex; such a call is invalid.
//
// * In other words, the state of being "held" has both a temporal component
//   (from `Lock()` until `Unlock()`) as well as a thread identity component:
//   the mutex is held *by a particular thread*.
//
// An "invalid" operation has undefined behavior. The `Mutex` implementation
// is allowed to do anything on an invalid call, including, but not limited to,
// crashing with a useful error message, silently succeeding, or corrupting
// data structures. In debug mode, the implementation may crash with a useful
// error message.
//
// `Mutex` is not guaranteed to be "fair" in prioritizing waiting threads; it
// is, however, approximately fair over long periods, and starvation-free for
// threads at the same priority.
//
// The lock/unlock primitives are now annotated with lock annotations
// defined in (base/thread_annotations.h). When writing multi-threaded code,
// you should use lock annotations whenever possible to document your lock
// synchronization policy. Besides acting as documentation, these annotations
// also help compilers or static analysis tools to identify and warn about
// issues that could potentially result in race conditions and deadlocks.
//
// For more information about the lock annotations, please see
// [Thread Safety
// Analysis](http://clang.llvm.org/docs/ThreadSafetyAnalysis.html) in the Clang
// documentation.
//
// See also `MutexLock`, below, for scoped `Mutex` acquisition.

class ABSL_LOCKABLE ABSL_ATTRIBUTE_WARN_UNUSED Mutex { … };

// -----------------------------------------------------------------------------
// Mutex RAII Wrappers
// -----------------------------------------------------------------------------

// MutexLock
//
// `MutexLock` is a helper class, which acquires and releases a `Mutex` via
// RAII.
//
// Example:
//
// Class Foo {
//  public:
//   Foo::Bar* Baz() {
//     MutexLock lock(&mu_);
//     ...
//     return bar;
//   }
//
// private:
//   Mutex mu_;
// };
class ABSL_SCOPED_LOCKABLE MutexLock { … };

// ReaderMutexLock
//
// The `ReaderMutexLock` is a helper class, like `MutexLock`, which acquires and
// releases a shared lock on a `Mutex` via RAII.
class ABSL_SCOPED_LOCKABLE ReaderMutexLock { … };

// WriterMutexLock
//
// The `WriterMutexLock` is a helper class, like `MutexLock`, which acquires and
// releases a write (exclusive) lock on a `Mutex` via RAII.
class ABSL_SCOPED_LOCKABLE WriterMutexLock { … };

// -----------------------------------------------------------------------------
// Condition
// -----------------------------------------------------------------------------
//
// `Mutex` contains a number of member functions which take a `Condition` as an
// argument; clients can wait for conditions to become `true` before attempting
// to acquire the mutex. These sections are known as "condition critical"
// sections. To use a `Condition`, you simply need to construct it, and use
// within an appropriate `Mutex` member function; everything else in the
// `Condition` class is an implementation detail.
//
// A `Condition` is specified as a function pointer which returns a boolean.
// `Condition` functions should be pure functions -- their results should depend
// only on passed arguments, should not consult any external state (such as
// clocks), and should have no side-effects, aside from debug logging. Any
// objects that the function may access should be limited to those which are
// constant while the mutex is blocked on the condition (e.g. a stack variable),
// or objects of state protected explicitly by the mutex.
//
// No matter which construction is used for `Condition`, the underlying
// function pointer / functor / callable must not throw any
// exceptions. Correctness of `Mutex` / `Condition` is not guaranteed in
// the face of a throwing `Condition`. (When Abseil is allowed to depend
// on C++17, these function pointers will be explicitly marked
// `noexcept`; until then this requirement cannot be enforced in the
// type system.)
//
// Note: to use a `Condition`, you need only construct it and pass it to a
// suitable `Mutex' member function, such as `Mutex::Await()`, or to the
// constructor of one of the scope guard classes.
//
// Example using LockWhen/Unlock:
//
//   // assume count_ is not internal reference count
//   int count_ ABSL_GUARDED_BY(mu_);
//   Condition count_is_zero(+[](int *count) { return *count == 0; }, &count_);
//
//   mu_.LockWhen(count_is_zero);
//   // ...
//   mu_.Unlock();
//
// Example using a scope guard:
//
//   {
//     MutexLock lock(&mu_, count_is_zero);
//     // ...
//   }
//
// When multiple threads are waiting on exactly the same condition, make sure
// that they are constructed with the same parameters (same pointer to function
// + arg, or same pointer to object + method), so that the mutex implementation
// can avoid redundantly evaluating the same condition for each thread.
class Condition { … };

// -----------------------------------------------------------------------------
// CondVar
// -----------------------------------------------------------------------------
//
// A condition variable, reflecting state evaluated separately outside of the
// `Mutex` object, which can be signaled to wake callers.
// This class is not normally needed; use `Mutex` member functions such as
// `Mutex::Await()` and intrinsic `Condition` abstractions. In rare cases
// with many threads and many conditions, `CondVar` may be faster.
//
// The implementation may deliver signals to any condition variable at
// any time, even when no call to `Signal()` or `SignalAll()` is made; as a
// result, upon being awoken, you must check the logical condition you have
// been waiting upon.
//
// Examples:
//
// Usage for a thread waiting for some condition C protected by mutex mu:
//       mu.Lock();
//       while (!C) { cv->Wait(&mu); }        // releases and reacquires mu
//       //  C holds; process data
//       mu.Unlock();
//
// Usage to wake T is:
//       mu.Lock();
//       // process data, possibly establishing C
//       if (C) { cv->Signal(); }
//       mu.Unlock();
//
// If C may be useful to more than one waiter, use `SignalAll()` instead of
// `Signal()`.
//
// With this implementation it is efficient to use `Signal()/SignalAll()` inside
// the locked region; this usage can make reasoning about your program easier.
//
class CondVar { … };

// Variants of MutexLock.
//
// If you find yourself using one of these, consider instead using
// Mutex::Unlock() and/or if-statements for clarity.

// MutexLockMaybe
//
// MutexLockMaybe is like MutexLock, but is a no-op when mu is null.
class ABSL_SCOPED_LOCKABLE MutexLockMaybe { … };

// ReleasableMutexLock
//
// ReleasableMutexLock is like MutexLock, but permits `Release()` of its
// mutex before destruction. `Release()` may be called at most once.
class ABSL_SCOPED_LOCKABLE ReleasableMutexLock { … };

inline Mutex::Mutex() : … { … }

inline constexpr Mutex::Mutex(absl::ConstInitType) : … { … }

#if !defined(__APPLE__) && !defined(ABSL_BUILD_DLL)
ABSL_ATTRIBUTE_ALWAYS_INLINE
inline Mutex::~Mutex() { … }
#endif

#if defined(NDEBUG) && !defined(ABSL_HAVE_THREAD_SANITIZER)
// Use default (empty) destructor in release build for performance reasons.
// We need to mark both Dtor and ~Mutex as always inline for inconsistent
// builds that use both NDEBUG and !NDEBUG with dynamic libraries. In these
// cases we want the empty functions to dissolve entirely rather than being
// exported from dynamic libraries and potentially override the non-empty ones.
ABSL_ATTRIBUTE_ALWAYS_INLINE
inline void Mutex::Dtor() {}
#endif

inline CondVar::CondVar() : … { … }

// static
template <typename T, typename ConditionMethodPtr>
bool Condition::CastAndCallMethod(const Condition* c) { … }

// static
template <typename T>
bool Condition::CastAndCallFunction(const Condition* c) { … }

template <typename T>
inline Condition::Condition(bool (*func)(T*), T* arg)
    : eval_(&CastAndCallFunction<T>),
      arg_(const_cast<void*>(static_cast<const void*>(arg))) { … }

template <typename T, typename>
inline Condition::Condition(
    bool (*func)(T*), typename absl::internal::type_identity<T>::type* arg)
    // Just delegate to the overload above.
    : Condition(func, arg) { … }

template <typename T>
inline Condition::Condition(
    T* object, bool (absl::internal::type_identity<T>::type::*method)())
    : eval_(&CastAndCallMethod<T, decltype(method)>), arg_(object) { … }

template <typename T>
inline Condition::Condition(
    const T* object,
    bool (absl::internal::type_identity<T>::type::*method)() const)
    : eval_(&CastAndCallMethod<const T, decltype(method)>),
      arg_(reinterpret_cast<void*>(const_cast<T*>(object))) { … }

// Register hooks for profiling support.
//
// The function pointer registered here will be called whenever a mutex is
// contended.  The callback is given the cycles for which waiting happened (as
// measured by //absl/base/internal/cycleclock.h, and which may not
// be real "cycle" counts.)
//
// There is no ordering guarantee between when the hook is registered and when
// callbacks will begin.  Only a single profiler can be installed in a running
// binary; if this function is called a second time with a different function
// pointer, the value is ignored (and will cause an assertion failure in debug
// mode.)
void RegisterMutexProfiler(void (*fn)(int64_t wait_cycles));

// Register a hook for Mutex tracing.
//
// The function pointer registered here will be called whenever a mutex is
// contended.  The callback is given an opaque handle to the contended mutex,
// an event name, and the number of wait cycles (as measured by
// //absl/base/internal/cycleclock.h, and which may not be real
// "cycle" counts.)
//
// The only event name currently sent is "slow release".
//
// This has the same ordering and single-use limitations as
// RegisterMutexProfiler() above.
void RegisterMutexTracer(void (*fn)(const char* msg, const void* obj,
                                    int64_t wait_cycles));

// Register a hook for CondVar tracing.
//
// The function pointer registered here will be called here on various CondVar
// events.  The callback is given an opaque handle to the CondVar object and
// a string identifying the event.  This is thread-safe, but only a single
// tracer can be registered.
//
// Events that can be sent are "Wait", "Unwait", "Signal wakeup", and
// "SignalAll wakeup".
//
// This has the same ordering and single-use limitations as
// RegisterMutexProfiler() above.
void RegisterCondVarTracer(void (*fn)(const char* msg, const void* cv));

// EnableMutexInvariantDebugging()
//
// Enable or disable global support for Mutex invariant debugging.  If enabled,
// then invariant predicates can be registered per-Mutex for debug checking.
// See Mutex::EnableInvariantDebugging().
void EnableMutexInvariantDebugging(bool enabled);

// When in debug mode, and when the feature has been enabled globally, the
// implementation will keep track of lock ordering and complain (or optionally
// crash) if a cycle is detected in the acquired-before graph.

// Possible modes of operation for the deadlock detector in debug mode.
enum class OnDeadlockCycle { … };

// SetMutexDeadlockDetectionMode()
//
// Enable or disable global support for detection of potential deadlocks
// due to Mutex lock ordering inversions.  When set to 'kIgnore', tracking of
// lock ordering is disabled.  Otherwise, in debug builds, a lock ordering graph
// will be maintained internally, and detected cycles will be reported in
// the manner chosen here.
void SetMutexDeadlockDetectionMode(OnDeadlockCycle mode);

ABSL_NAMESPACE_END
}  // namespace absl

// In some build configurations we pass --detect-odr-violations to the
// gold linker.  This causes it to flag weak symbol overrides as ODR
// violations.  Because ODR only applies to C++ and not C,
// --detect-odr-violations ignores symbols not mangled with C++ names.
// By changing our extension points to be extern "C", we dodge this
// check.
extern "C" {
void ABSL_INTERNAL_C_SYMBOL(AbslInternalMutexYield)();
}  // extern "C"

#endif  // ABSL_SYNCHRONIZATION_MUTEX_H_