/*
- * Copyright 2016 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
namespace detail {
/**
- * An internal helper class for identifying if a lock type supports
- * lock_shared() and try_lock_for() methods.
+ * 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 MutexLevel { UNIQUE, SHARED, UPGRADE };
+
+/**
+ * A template dispatch mechanism that is used to determine the level of the
+ * mutex based on its interface. As decided by LockInterfaceDispatcher.
+ */
+template <bool is_unique, bool is_shared, bool is_upgrade>
+struct MutexLevelValueImpl;
+template <>
+struct MutexLevelValueImpl<true, false, false> {
+ static constexpr MutexLevel value = MutexLevel::UNIQUE;
+};
+template <>
+struct MutexLevelValueImpl<true, true, false> {
+ static constexpr MutexLevel value = MutexLevel::SHARED;
+};
+template <>
+struct MutexLevelValueImpl<true, true, true> {
+ static constexpr MutexLevel value = MutexLevel::UPGRADE;
+};
+
+/**
+ * An internal helper class to help identify the interface supported by the
+ * mutex. This is used in conjunction with the above MutexLevel
+ * specializations and the LockTraitsImpl to determine what functions are
+ * supported by objects of type Mutex
+ *
+ * The implementation uses SINAE in the return value with trailing return
+ * types to figure out what level a mutex is
*/
template <class Mutex>
-class LockTraitsImpl {
+class LockInterfaceDispatcher {
private:
+ // assert that the mutex type has basic lock and unlock functions
+ static_assert(
+ std::is_same<decltype(std::declval<Mutex>().lock()), void>::value,
+ "The mutex type must support lock and unlock functions");
+
// Helper functions for implementing the traits using SFINAE
template <class T>
static auto timed_lock_test(T*) -> typename std::is_same<
template <class T>
static std::false_type lock_shared_test(...);
+ template <class T>
+ static auto lock_upgrade_test(T*) -> typename std::
+ is_same<decltype(std::declval<T>().lock_upgrade()), void>::type;
+ template <class T>
+ static std::false_type lock_upgrade_test(...);
+
public:
- static constexpr bool has_timed_lock =
+ static constexpr bool has_lock_unique = true;
+ static constexpr bool has_lock_timed =
decltype(timed_lock_test<Mutex>(0))::value;
static constexpr bool has_lock_shared =
decltype(lock_shared_test<Mutex>(0))::value;
+ static constexpr bool has_lock_upgrade =
+ decltype(lock_upgrade_test<Mutex>(0))::value;
};
+/**
+ * LockTraitsImpl is the base that is used to desribe the interface used by
+ * different mutex types. It accepts a MutexLevel argument and a boolean to
+ * show whether the mutex is a timed mutex or not. The implementations are
+ * partially specialized and inherit from the other implementations to get
+ * similar functionality
+ */
+template <class Mutex, MutexLevel level, bool is_timed>
+struct LockTraitsImpl;
+
template <class Mutex>
-struct LockTraitsUniqueBase {
+struct LockTraitsImpl<Mutex, MutexLevel::UNIQUE, false> {
+ static constexpr bool is_timed{false};
+ static constexpr bool is_shared{false};
+ static constexpr bool is_upgrade{false};
+
/**
* Acquire the lock exclusively.
*/
}
};
+/**
+ * Higher level mutexes have all the capabilities of the lower levels so
+ * inherit
+ */
template <class Mutex>
-struct LockTraitsSharedBase : public LockTraitsUniqueBase<Mutex> {
+struct LockTraitsImpl<Mutex, MutexLevel::SHARED, false>
+ : public LockTraitsImpl<Mutex, MutexLevel::UNIQUE, false> {
+ static constexpr bool is_timed{false};
+ static constexpr bool is_shared{true};
+ static constexpr bool is_upgrade{false};
+
/**
* Acquire the lock in shared (read) mode.
*/
}
};
-template <class Mutex, bool is_shared, bool is_timed>
-struct LockTraitsBase {};
-
+/**
+ * The following methods are supported. There are a few methods
+ *
+ * m.lock_upgrade()
+ * m.unlock_upgrade()
+ *
+ * m.unlock_upgrade_and_lock()
+ *
+ * m.unlock_and_lock_upgrade()
+ * m.unlock_and_lock_shared()
+ * m.unlock_upgrade_and_lock_shared()
+ *
+ * m.try_lock_upgrade_for(rel_time)
+ * m.try_unlock_upgrade_and_lock_for(rel_time)
+ *
+ * Upgrading a shared lock is likely to deadlock when there is more than one
+ * thread performing an upgrade. This applies both to upgrading a shared lock
+ * to an upgrade lock and to upgrading a shared lock to a unique lock.
+ *
+ * Therefore, none of the following methods is supported:
+ * unlock_shared_and_lock_upgrade
+ * unlock_shared_and_lock
+ * try_unlock_shared_and_lock_upgrade
+ * try_unlock_shared_and_lock
+ * try_unlock_shared_and_lock_upgrade_for
+ * try_unlock_shared_and_lock_for
+ */
template <class Mutex>
-struct LockTraitsBase<Mutex, false, false>
- : public LockTraitsUniqueBase<Mutex> {
- static constexpr bool is_shared = false;
- static constexpr bool is_timed = false;
-};
+struct LockTraitsImpl<Mutex, MutexLevel::UPGRADE, false>
+ : public LockTraitsImpl<Mutex, MutexLevel::SHARED, false> {
+ static constexpr bool is_timed{false};
+ static constexpr bool is_shared{true};
+ static constexpr bool is_upgrade{true};
-template <class Mutex>
-struct LockTraitsBase<Mutex, true, false> : public LockTraitsSharedBase<Mutex> {
- static constexpr bool is_shared = true;
- static constexpr bool is_timed = false;
+ /**
+ * Acquire the lock in upgradable mode.
+ */
+ static void lock_upgrade(Mutex& mutex) {
+ mutex.lock_upgrade();
+ }
+
+ /**
+ * Release the lock in upgrade mode
+ */
+ static void unlock_upgrade(Mutex& mutex) {
+ mutex.unlock_upgrade();
+ }
+
+ /**
+ * Upgrade from an upgradable state to an exclusive state
+ */
+ static void unlock_upgrade_and_lock(Mutex& mutex) {
+ mutex.unlock_upgrade_and_lock();
+ }
+
+ /**
+ * Downgrade from an exclusive state to an upgrade state
+ */
+ static void unlock_and_lock_upgrade(Mutex& mutex) {
+ mutex.unlock_and_lock_upgrade();
+ }
+
+ /**
+ * Downgrade from an exclusive state to a shared state
+ */
+ static void unlock_and_lock_shared(Mutex& mutex) {
+ mutex.unlock_and_lock_shared();
+ }
+
+ /**
+ * Downgrade from an upgrade state to a shared state
+ */
+ static void unlock_upgrade_and_lock_shared(Mutex& mutex) {
+ mutex.unlock_upgrade_and_lock_shared();
+ }
};
template <class Mutex>
-struct LockTraitsBase<Mutex, false, true> : public LockTraitsUniqueBase<Mutex> {
- static constexpr bool is_shared = false;
- static constexpr bool is_timed = true;
+struct LockTraitsImpl<Mutex, MutexLevel::UNIQUE, true>
+ : public LockTraitsImpl<Mutex, MutexLevel::UNIQUE, false> {
+ static constexpr bool is_timed{true};
+ static constexpr bool is_shared{false};
+ static constexpr bool is_upgrade{false};
/**
* Acquire the lock exclusively, with a timeout.
}
};
+/**
+ * Note that there is no deadly diamond here because all the structs only have
+ * static functions and static bools which are going to be overridden by the
+ * lowest level implementation
+ */
template <class Mutex>
-struct LockTraitsBase<Mutex, true, true> : public LockTraitsSharedBase<Mutex> {
- static constexpr bool is_shared = true;
- static constexpr bool is_timed = true;
+struct LockTraitsImpl<Mutex, MutexLevel::SHARED, true>
+ : public LockTraitsImpl<Mutex, MutexLevel::SHARED, false>,
+ public LockTraitsImpl<Mutex, MutexLevel::UNIQUE, true> {
+ static constexpr bool is_timed{true};
+ static constexpr bool is_shared{true};
+ static constexpr bool is_upgrade{false};
/**
* Acquire the lock exclusively, with a timeout.
return mutex.try_lock_shared_for(timeout);
}
};
+
+template <class Mutex>
+struct LockTraitsImpl<Mutex, MutexLevel::UPGRADE, true>
+ : public LockTraitsImpl<Mutex, MutexLevel::UPGRADE, false>,
+ public LockTraitsImpl<Mutex, MutexLevel::SHARED, true> {
+ static constexpr bool is_timed{true};
+ static constexpr bool is_shared{true};
+ static constexpr bool is_upgrade{true};
+
+ /**
+ * Acquire the lock in upgrade mode with a timeout
+ *
+ * Returns true or false indicating whether the lock was acquired or not
+ */
+ template <class Rep, class Period>
+ static bool try_lock_upgrade_for(
+ Mutex& mutex,
+ const std::chrono::duration<Rep, Period>& timeout) {
+ return mutex.try_lock_upgrade_for(timeout);
+ }
+
+ /**
+ * Try to upgrade from an upgradable state to an exclusive state.
+ *
+ * Returns true or false indicating whether the lock was acquired or not
+ */
+ template <class Rep, class Period>
+ static bool try_unlock_upgrade_and_lock_for(
+ Mutex& mutex,
+ const std::chrono::duration<Rep, Period>& timeout) {
+ return mutex.try_unlock_upgrade_and_lock_for(timeout);
+ }
+};
+
} // detail
/**
* True if the lock supports separate shared vs exclusive locking states.
* - static constexpr bool is_timed
* True if the lock supports acquiring the lock with a timeout.
+ * - static constexpr bool is_upgrade
+ * True if the lock supports an upgradable state
*
* The following static methods always exist:
* - lock(Mutex& mutex)
* - unlock(Mutex& mutex)
*
- * The following static methods may exist, depending on is_shared and
- * is_timed:
- * - try_lock_for(Mutex& mutex, <std_chrono_duration> timeout)
- * - lock_shared(Mutex& mutex)
- * - unlock_shared(Mutex& mutex)
- * - try_lock_shared_for(Mutex& mutex, <std_chrono_duration> timeout)
+ * The following static methods may exist, depending on is_shared, is_timed
+ * and is_upgrade:
+ * - lock_shared()
+ *
+ * - try_lock_for()
+ * - try_lock_shared_for()
+ *
+ * - lock_upgrade()
+ * - unlock_upgrade_and_lock()
+ * - unlock_and_lock_upgrade()
+ * - unlock_and_lock_shared()
+ * - unlock_upgrade_and_lock_shared()
+ *
+ * - try_lock_upgrade_for()
+ * - try_unlock_upgrade_and_lock_for()
+ *
+ * - unlock_shared()
+ * - unlock_upgrade()
+ */
+
+/**
+ * Decoupling LockTraits and LockTraitsBase so that if people want to fully
+ * specialize LockTraits then they can inherit from LockTraitsBase instead
+ * of LockTraits with all the same goodies :)
*/
template <class Mutex>
-struct LockTraits : public detail::LockTraitsBase<
- Mutex,
- detail::LockTraitsImpl<Mutex>::has_lock_shared,
- detail::LockTraitsImpl<Mutex>::has_timed_lock> {};
+struct LockTraitsBase
+ : public detail::LockTraitsImpl<
+ Mutex,
+ detail::MutexLevelValueImpl<
+ detail::LockInterfaceDispatcher<Mutex>::has_lock_unique,
+ detail::LockInterfaceDispatcher<Mutex>::has_lock_shared,
+ detail::LockInterfaceDispatcher<Mutex>::has_lock_upgrade>::value,
+ detail::LockInterfaceDispatcher<Mutex>::has_lock_timed> {};
+
+template <class Mutex>
+struct LockTraits : public LockTraitsBase<Mutex> {};
/**
* If the lock is a shared lock, acquire it in shared mode.
/**
* A lock policy that performs exclusive lock operations.
*/
-class LockPolicyExclusive {
- public:
+struct LockPolicyExclusive {
template <class Mutex>
static void lock(Mutex& mutex) {
LockTraits<Mutex>::lock(mutex);
* A lock policy that performs shared lock operations.
* This policy only works with shared mutex types.
*/
-class LockPolicyShared {
- public:
+struct LockPolicyShared {
template <class Mutex>
static void lock(Mutex& mutex) {
LockTraits<Mutex>::lock_shared(mutex);
* A lock policy that performs a shared lock operation if a shared mutex type
* is given, or a normal exclusive lock operation on non-shared mutex types.
*/
-class LockPolicyShareable {
- public:
+struct LockPolicyShareable {
template <class Mutex>
static void lock(Mutex& mutex) {
lock_shared_or_unique(mutex);
}
};
+/**
+ * A lock policy with the following mapping
+ *
+ * lock() -> lock_upgrade()
+ * unlock() -> unlock_upgrade()
+ * try_lock_for -> try_lock_upgrade_for()
+ */
+struct LockPolicyUpgrade {
+ template <class Mutex>
+ static void lock(Mutex& mutex) {
+ LockTraits<Mutex>::lock_upgrade(mutex);
+ }
+ template <class Mutex, class Rep, class Period>
+ static bool try_lock_for(
+ Mutex& mutex,
+ const std::chrono::duration<Rep, Period>& timeout) {
+ return LockTraits<Mutex>::try_lock_upgrade_for(mutex, timeout);
+ }
+ template <class Mutex>
+ static void unlock(Mutex& mutex) {
+ LockTraits<Mutex>::unlock_upgrade(mutex);
+ }
+};
+
+/*****************************************************************************
+ * Policies for all the transitions from possible mutex levels
+ ****************************************************************************/
+/**
+ * A lock policy with the following mapping
+ *
+ * lock() -> unlock_upgrade_and_lock()
+ * unlock() -> unlock()
+ * try_lock_for -> try_unlock_upgrade_and_lock_for()
+ */
+struct LockPolicyFromUpgradeToExclusive : public LockPolicyExclusive {
+ template <class Mutex>
+ static void lock(Mutex& mutex) {
+ LockTraits<Mutex>::unlock_upgrade_and_lock(mutex);
+ }
+ template <class Mutex, class Rep, class Period>
+ static bool try_lock_for(
+ Mutex& mutex,
+ const std::chrono::duration<Rep, Period>& timeout) {
+ return LockTraits<Mutex>::try_unlock_upgrade_and_lock_for(mutex, timeout);
+ }
+};
+
+/**
+ * A lock policy with the following mapping
+ *
+ * lock() -> unlock_and_lock_upgrade()
+ * unlock() -> unlock_upgrade()
+ * try_lock_for -> unlock_and_lock_upgrade()
+ */
+struct LockPolicyFromExclusiveToUpgrade : public LockPolicyUpgrade {
+ template <class Mutex>
+ static void lock(Mutex& mutex) {
+ LockTraits<Mutex>::unlock_and_lock_upgrade(mutex);
+ }
+ template <class Mutex, class Rep, class Period>
+ static bool try_lock_for(
+ Mutex& mutex,
+ const std::chrono::duration<Rep, Period>&) {
+ LockTraits<Mutex>::unlock_and_lock_upgrade(mutex);
+
+ // downgrade should be non blocking and should succeed
+ return true;
+ }
+};
+
+/**
+ * A lock policy with the following mapping
+ *
+ * lock() -> unlock_upgrade_and_lock_shared()
+ * unlock() -> unlock_shared()
+ * try_lock_for -> unlock_upgrade_and_lock_shared()
+ */
+struct LockPolicyFromUpgradeToShared : public LockPolicyShared {
+ template <class Mutex>
+ static void lock(Mutex& mutex) {
+ LockTraits<Mutex>::unlock_upgrade_and_lock_shared(mutex);
+ }
+ template <class Mutex, class Rep, class Period>
+ static bool try_lock_for(
+ Mutex& mutex,
+ const std::chrono::duration<Rep, Period>&) {
+ LockTraits<Mutex>::unlock_upgrade_and_lock_shared(mutex);
+
+ // downgrade should be non blocking and should succeed
+ return true;
+ }
+};
+
+/**
+ * A lock policy with the following mapping
+ *
+ * lock() -> unlock_and_lock_shared()
+ * unlock() -> unlock_shared()
+ * try_lock_for() -> unlock_and_lock_shared()
+ */
+struct LockPolicyFromExclusiveToShared : public LockPolicyShared {
+ template <class Mutex>
+ static void lock(Mutex& mutex) {
+ LockTraits<Mutex>::unlock_and_lock_shared(mutex);
+ }
+ template <class Mutex, class Rep, class Period>
+ static bool try_lock_for(
+ Mutex& mutex,
+ const std::chrono::duration<Rep, Period>&) {
+ LockTraits<Mutex>::unlock_and_lock_shared(mutex);
+
+ // downgrade should be non blocking and should succeed
+ return true;
+ }
+};
+
} // folly