folly/folly/Synchronized.h

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * 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
 *
 *     http://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.
 */

//
// Docs: https://fburl.com/fbcref_synchronized
//

/**
 * This module implements a Synchronized abstraction useful in
 * mutex-based concurrency.
 *
 * The Synchronized<T, Mutex> class is the primary public API exposed by this
 * module.  See folly/docs/Synchronized.md for a more complete explanation of
 * this class and its benefits.
 */

#pragma once

#include <folly/Function.h>
#include <folly/Likely.h>
#include <folly/Preprocessor.h>
#include <folly/SharedMutex.h>
#include <folly/Traits.h>
#include <folly/Utility.h>
#include <folly/container/Foreach.h>
#include <folly/functional/ApplyTuple.h>
#include <folly/synchronization/Lock.h>

#include <glog/logging.h>

#include <array>
#include <mutex>
#include <tuple>
#include <type_traits>
#include <utility>

namespace folly {

namespace detail {

kSynchronizedMutexIsUnique;
kSynchronizedMutexIsUnique;

kSynchronizedMutexIsShared;
kSynchronizedMutexIsShared;

kSynchronizedMutexIsUpgrade;
kSynchronizedMutexIsUpgrade;

/**
 * An enum to describe the "level" of a mutex.  The supported levels are
 *  Unique - a normal mutex that supports only exclusive locking
 *  Shared - a shared mutex which has shared locking and unlocking functions;
 *  Upgrade - a mutex that has all the methods of the two above along with
 *            support for upgradable locking
 */
enum class SynchronizedMutexLevel { … };

kSynchronizedMutexLevel;

enum class SynchronizedMutexMethod { … };

template <SynchronizedMutexLevel Level, SynchronizedMutexMethod Method>
struct SynchronizedLockPolicy { … };
SynchronizedLockPolicyExclusive;
SynchronizedLockPolicyTryExclusive;
SynchronizedLockPolicyShared;
SynchronizedLockPolicyTryShared;
SynchronizedLockPolicyUpgrade;
SynchronizedLockPolicyTryUpgrade;

template <SynchronizedMutexLevel>
struct SynchronizedLockType_ { … };
template <>
struct SynchronizedLockType_<SynchronizedMutexLevel::Unique> { … };
template <>
struct SynchronizedLockType_<SynchronizedMutexLevel::Shared> { … };
template <>
struct SynchronizedLockType_<SynchronizedMutexLevel::Upgrade> { … };
SynchronizedLockType;

} // namespace detail

/**
 * SynchronizedBase is a helper parent class for Synchronized<T>.
 *
 * It provides wlock() and rlock() methods for shared mutex types,
 * or lock() methods for purely exclusive mutex types.
 */
template <class Subclass, detail::SynchronizedMutexLevel level>
class SynchronizedBase;

template <class LockedType, class Mutex, class LockPolicy>
class LockedPtrBase;
template <class LockedType, class LockPolicy>
class LockedPtr;

/**
 * SynchronizedBase specialization for shared mutex types.
 *
 * This class provides wlock() and rlock() methods for acquiring the lock and
 * accessing the data.
 */
SynchronizedBase<Subclass, detail::SynchronizedMutexLevel::Shared>;

/**
 * SynchronizedBase specialization for upgrade mutex types.
 *
 * This class provides all the functionality provided by the SynchronizedBase
 * specialization for shared mutexes and a ulock() method that returns an
 * upgrade lock RAII proxy
 */
SynchronizedBase<Subclass, detail::SynchronizedMutexLevel::Upgrade>;

/**
 * SynchronizedBase specialization for non-shared mutex types.
 *
 * This class provides lock() methods for acquiring the lock and accessing the
 * data.
 */
SynchronizedBase<Subclass, detail::SynchronizedMutexLevel::Unique>;

/**
 * `folly::Synchronized` pairs a datum with a mutex. The datum can only be
 * reached through a `LockedPtr`, typically acquired via `.rlock()` or
 * `.wlock()`; the mutex is held for the lifetime of the `LockedPtr`.
 *
 * It is recommended to explicitly open a new nested scope when aquiring
 * a `LockedPtr` object, to help visibly delineate the critical section and to
 * ensure that the `LockedPtr` is destroyed as soon as it is no longer needed.
 *
 * @tparam T  The type of datum to be stored.
 * @tparam Mutex  The mutex type that guards the datum. Must be Lockable.
 *
 * @refcode folly/docs/examples/folly/Synchronized.cpp
 */
template <class T, class Mutex = SharedMutex>
struct Synchronized : public SynchronizedBase<
                          Synchronized<T, Mutex>,
                          detail::kSynchronizedMutexLevel<Mutex>> { … };

/**
 * Deprecated subclass of Synchronized that provides implicit locking
 * via operator->. This is intended to ease migration while preventing
 * accidental use of operator-> in new code.
 */
template <class T, class Mutex = SharedMutex>
struct [[deprecated(
    "use Synchronized and explicit lock(), wlock(), or rlock() instead")]] ImplicitSynchronized
    : Synchronized<T, Mutex> { … };

template <class SynchronizedType, class LockPolicy>
class ScopedUnlocker;

namespace detail {
/*
 * A helper alias that resolves to "const T" if the template parameter
 * is a const Synchronized<T>, or "T" if the parameter is not const.
 */
SynchronizedDataType;
/*
 * A helper alias that resolves to a ConstLockedPtr if the template parameter
 * is a const Synchronized<T>, or a LockedPtr if the parameter is not const.
 */
LockedPtrType;

template <
    typename Synchronized,
    typename LockFunc,
    typename TryLockFunc,
    typename... Args>
class SynchronizedLocker { … };

template <
    typename Synchronized,
    typename LockFunc,
    typename TryLockFunc,
    typename... Args>
auto makeSynchronizedLocker(
    Synchronized& synchronized,
    LockFunc&& lockFunc,
    TryLockFunc&& tryLockFunc,
    Args&&... args) { … }

/**
 * Acquire locks for multiple Synchronized<T> objects, in a deadlock-safe
 * manner.
 *
 * The function uses the "smart and polite" algorithm from this link
 * http://howardhinnant.github.io/dining_philosophers.html#Polite
 *
 * The gist of the algorithm is that it locks a mutex, then tries to lock the
 * other mutexes in a non-blocking manner.  If all the locks succeed, we are
 * done, if not, we release the locks we have held, yield to allow other
 * threads to continue and then block on the mutex that we failed to acquire.
 *
 * This allows dynamically yielding ownership of all the mutexes but one, so
 * that other threads can continue doing work and locking the other mutexes.
 * See the benchmarks in folly/test/SynchronizedBenchmark.cpp for more.
 */
template <typename... SynchronizedLocker>
auto lock(SynchronizedLocker... lockersIn)
    -> std::tuple<typename SynchronizedLocker::LockedPtr...> { … }

template <typename Synchronized, typename... Args>
auto wlock(Synchronized& synchronized, Args&&... args) { … }
template <typename Synchronized, typename... Args>
auto rlock(Synchronized& synchronized, Args&&... args) { … }
template <typename Synchronized, typename... Args>
auto ulock(Synchronized& synchronized, Args&&... args) { … }
template <typename Synchronized, typename... Args>
auto lock(Synchronized& synchronized, Args&&... args) { … }

} // namespace detail

/**
 * This class temporarily unlocks a LockedPtr in a scoped manner.
 */
template <class SynchronizedType, class LockPolicy>
class ScopedUnlocker { … };

/**
 * A LockedPtr keeps a Synchronized<T> object locked for the duration of
 * LockedPtr's existence.
 *
 * It provides access the datum's members directly by using operator->() and
 * operator*().
 *
 * The LockPolicy parameter controls whether or not the lock is acquired in
 * exclusive or shared mode.
 */
template <class SynchronizedType, class LockPolicy>
class LockedPtr { … };

/**
 * Helper functions that should be passed to either a lock() or synchronized()
 * invocation, these return implementation defined structs that will be used
 * to lock the synchronized instance appropriately.
 *
 *    lock(wlock(one), rlock(two), wlock(three));
 *    synchronized([](auto one, two) { ... }, wlock(one), rlock(two));
 *
 * For example in the above rlock() produces an implementation defined read
 * locking helper instance and wlock() a write locking helper
 *
 * Subsequent arguments passed to these locking helpers, after the first, will
 * be passed by const-ref to the corresponding function on the synchronized
 * instance.  This means that if the function accepts these parameters by
 * value, they will be copied.  Note that it is not necessary that the primary
 * locking function will be invoked at all (for eg.  the implementation might
 * just invoke the try*Lock() method)
 *
 *    // Try to acquire the lock for one second
 *    synchronized([](auto) { ... }, wlock(one, 1s));
 *
 *    // The timed lock acquire might never actually be called, if it is not
 *    // needed by the underlying deadlock avoiding algorithm
 *    synchronized([](auto, auto) { ... }, rlock(one), wlock(two, 1s));
 *
 * Note that the arguments passed to to *lock() calls will be passed by
 * const-ref to the function invocation, as the implementation might use them
 * many times
 */
template <typename D, typename M, typename... Args>
auto wlock(Synchronized<D, M>& synchronized, Args&&... args) { … }
template <typename D, typename M, typename... Args>
auto wlock(const Synchronized<D, M>& synchronized, Args&&... args) { … }
template <typename Data, typename Mutex, typename... Args>
auto rlock(const Synchronized<Data, Mutex>& synchronized, Args&&... args) { … }
template <typename D, typename M, typename... Args>
auto ulock(Synchronized<D, M>& synchronized, Args&&... args) { … }
template <typename D, typename M, typename... Args>
auto lock(Synchronized<D, M>& synchronized, Args&&... args) { … }
template <typename D, typename M, typename... Args>
auto lock(const Synchronized<D, M>& synchronized, Args&&... args) { … }

/**
 * Acquire locks for multiple Synchronized<> objects, in a deadlock-safe
 * manner.
 *
 * Wrap the synchronized instances with the appropriate locking strategy by
 * using one of the four strategies - folly::lock (exclusive acquire for
 * exclusive only mutexes), folly::rlock (shared acquire for shareable
 * mutexes), folly::wlock (exclusive acquire for shareable mutexes) or
 * folly::ulock (upgrade acquire for upgrade mutexes) (see above)
 *
 * The locks will be acquired and the passed callable will be invoked with the
 * LockedPtr instances in the order that they were passed to the function
 */
template <typename Func, typename... SynchronizedLockers>
decltype(auto) synchronized(Func&& func, SynchronizedLockers&&... lockers) { … }

/**
 * Acquire locks on many lockables or synchronized instances in such a way
 * that the sequence of calls within the function does not cause deadlocks.
 *
 * This can often result in a performance boost as compared to simply
 * acquiring your locks in an ordered manner.  Even for very simple cases.
 * The algorithm tried to adjust to contention by blocking on the mutex it
 * thinks is the best fit, leaving all other mutexes open to be locked by
 * other threads.  See the benchmarks in folly/test/SynchronizedBenchmark.cpp
 * for more
 *
 * This works differently as compared to the locking algorithm in libstdc++
 * and is the recommended way to acquire mutexes in a generic order safe
 * manner.  Performance benchmarks show that this does better than the one in
 * libstdc++ even for the simple cases
 *
 * Usage is the same as std::lock() for arbitrary lockables
 *
 *    folly::lock(one, two, three);
 *
 * To make it work with folly::Synchronized you have to specify how you want
 * the locks to be acquired, use the folly::wlock(), folly::rlock(),
 * folly::ulock() and folly::lock() helpers defined below
 *
 *    auto [one, two] = lock(folly::wlock(a), folly::rlock(b));
 *
 * Note that you can/must avoid the folly:: namespace prefix on the lock()
 * function if you use the helpers, ADL lookup is done to find the lock function
 *
 * This will execute the deadlock avoidance algorithm and acquire a write lock
 * for a and a read lock for b
 */
template <typename LockableOne, typename LockableTwo, typename... Lockables>
void lock(LockableOne& one, LockableTwo& two, Lockables&... lockables) { … }

/**
 * Acquire locks for multiple Synchronized<T> objects, in a deadlock-safe
 * manner.
 *
 * The locks are acquired in order from lowest address to highest address.
 * (Note that this is not necessarily the same algorithm used by std::lock().)
 * For parameters that are const and support shared locks, a read lock is
 * acquired.  Otherwise an exclusive lock is acquired.
 *
 * use lock() with folly::wlock(), folly::rlock() and folly::ulock() for
 * arbitrary locking without causing a deadlock (as much as possible), with the
 * same effects as std::lock()
 */
template <class Sync1, class Sync2>
std::tuple<detail::LockedPtrType<Sync1>, detail::LockedPtrType<Sync2>>
acquireLocked(Sync1& l1, Sync2& l2) { … }

/**
 * A version of acquireLocked() that returns a std::pair rather than a
 * std::tuple, which is easier to use in many places.
 */
template <class Sync1, class Sync2>
std::pair<detail::LockedPtrType<Sync1>, detail::LockedPtrType<Sync2>>
acquireLockedPair(Sync1& l1, Sync2& l2) { … }

/************************************************************************
 * NOTE: All APIs below this line will be deprecated in upcoming diffs.
 ************************************************************************/

// Non-member swap primitive
template <class T, class M>
void swap(Synchronized<T, M>& lhs, Synchronized<T, M>& rhs) { … }

/**
 * Disambiguate the name var by concatenating the line number of the original
 * point of expansion. This avoids shadowing warnings for nested
 * SYNCHRONIZEDs. The name is consistent if used multiple times within
 * another macro.
 * Only for internal use.
 */
#define SYNCHRONIZED_VAR(var) …

namespace detail {
struct [[deprecated(
    "use explicit lock(), wlock(), or rlock() instead")]] SYNCHRONIZED_macro_is_deprecated { … };
} // namespace detail

/**
 * NOTE: This API is deprecated.  Use lock(), wlock(), rlock() or the withLock
 * functions instead.  In the future it will be marked with a deprecation
 * attribute to emit build-time warnings, and then it will be removed entirely.
 *
 * SYNCHRONIZED is the main facility that makes Synchronized<T>
 * helpful. It is a pseudo-statement that introduces a scope where the
 * object is locked. Inside that scope you get to access the unadorned
 * datum.
 *
 * Example:
 *
 * Synchronized<vector<int>> svector;
 * ...
 * SYNCHRONIZED (svector) { ... use svector as a vector<int> ... }
 * or
 * SYNCHRONIZED (v, svector) { ... use v as a vector<int> ... }
 *
 * Refer to folly/docs/Synchronized.md for a detailed explanation and more
 * examples.
 */
#define SYNCHRONIZED(...) …

/**
 * NOTE: This API is deprecated.  Use lock(), wlock(), rlock() or the withLock
 * functions instead.  In the future it will be marked with a deprecation
 * attribute to emit build-time warnings, and then it will be removed entirely.
 *
 * Similar to SYNCHRONIZED, but only uses a read lock.
 */
#define SYNCHRONIZED_CONST(...) …

/**
 * NOTE: This API is deprecated.  Use lock(), wlock(), rlock() or the withLock
 * functions instead.  In the future it will be marked with a deprecation
 * attribute to emit build-time warnings, and then it will be removed entirely.
 *
 * Synchronizes two Synchronized objects (they may encapsulate
 * different data). Synchronization is done in increasing address of
 * object order, so there is no deadlock risk.
 */
#define SYNCHRONIZED_DUAL(n1, e1, n2, e2) …

} /* namespace folly */