From 84f24236e480f1ab287f07c8d862df8928b45115 Mon Sep 17 00:00:00 2001 From: Aaryaman Sagar Date: Thu, 4 Aug 2016 17:14:45 -0700 Subject: [PATCH] Adding support for upgradable mutexes to LockTraits Summary: This diff adds support for upgradable mutexes to the LockTraits abstraction used by folly::Synchronized Reviewed By: yfeldblum Differential Revision: D3645453 fbshipit-source-id: 30f16eb3fbebc687a4136256f1103962c0e4c465 --- folly/LockTraits.h | 270 ++++++++++++++++++++++++++++---- folly/LockTraitsBoost.h | 6 +- folly/test/LockTraitsTest.cpp | 69 +++++++- folly/test/SynchronizedTest.cpp | 6 +- 4 files changed, 308 insertions(+), 43 deletions(-) diff --git a/folly/LockTraits.h b/folly/LockTraits.h index 3b84f503..1879e3bc 100644 --- a/folly/LockTraits.h +++ b/folly/LockTraits.h @@ -39,12 +39,50 @@ namespace folly { 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 +struct MutexLevelValueImpl; +template <> +struct MutexLevelValueImpl { + static constexpr MutexLevel value = MutexLevel::UNIQUE; +}; +template <> +struct MutexLevelValueImpl { + static constexpr MutexLevel value = MutexLevel::SHARED; +}; +template <> +struct MutexLevelValueImpl { + 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 LockTraitsImpl { +class LockInterfaceDispatcher { private: + // assert that the mutex type has basic lock and unlock functions + static_assert( + std::is_same().lock()), void>::value, + "The mutex type must support lock and unlock functions"); + // Helper functions for implementing the traits using SFINAE template static auto timed_lock_test(T*) -> typename std::is_same< @@ -59,15 +97,38 @@ class LockTraitsImpl { template static std::false_type lock_shared_test(...); + template + static auto lock_upgrade_test(T*) -> typename std:: + is_same().lock_upgrade()), void>::type; + template + 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(0))::value; static constexpr bool has_lock_shared = decltype(lock_shared_test(0))::value; + static constexpr bool has_lock_upgrade = + decltype(lock_upgrade_test(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 +struct LockTraitsImpl; + template -struct LockTraitsUniqueBase { +struct LockTraitsImpl { + static constexpr bool is_timed{false}; + static constexpr bool is_shared{false}; + static constexpr bool is_upgrade{false}; + /** * Acquire the lock exclusively. */ @@ -83,8 +144,17 @@ struct LockTraitsUniqueBase { } }; +/** + * Higher level mutexes have all the capabilities of the lower levels so + * inherit + */ template -struct LockTraitsSharedBase : public LockTraitsUniqueBase { +struct LockTraitsImpl + : public LockTraitsImpl { + 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. */ @@ -100,26 +170,89 @@ struct LockTraitsSharedBase : public LockTraitsUniqueBase { } }; -template -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 -struct LockTraitsBase - : public LockTraitsUniqueBase { - static constexpr bool is_shared = false; - static constexpr bool is_timed = false; -}; +struct LockTraitsImpl + : public LockTraitsImpl { + static constexpr bool is_timed{false}; + static constexpr bool is_shared{true}; + static constexpr bool is_upgrade{true}; -template -struct LockTraitsBase : public LockTraitsSharedBase { - 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 -struct LockTraitsBase : public LockTraitsUniqueBase { - static constexpr bool is_shared = false; - static constexpr bool is_timed = true; +struct LockTraitsImpl + : public LockTraitsImpl { + 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. @@ -134,10 +267,18 @@ struct LockTraitsBase : public LockTraitsUniqueBase { } }; +/** + * 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 -struct LockTraitsBase : public LockTraitsSharedBase { - static constexpr bool is_shared = true; - static constexpr bool is_timed = true; +struct LockTraitsImpl + : public LockTraitsImpl, + public LockTraitsImpl { + 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. @@ -163,6 +304,40 @@ struct LockTraitsBase : public LockTraitsSharedBase { return mutex.try_lock_shared_for(timeout); } }; + +template +struct LockTraitsImpl + : public LockTraitsImpl, + public LockTraitsImpl { + 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 + static bool try_lock_upgrade_for( + Mutex& mutex, + const std::chrono::duration& 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 + static bool try_unlock_upgrade_and_lock_for( + Mutex& mutex, + const std::chrono::duration& timeout) { + return mutex.try_unlock_upgrade_and_lock_for(timeout); + } +}; + } // detail /** @@ -181,23 +356,50 @@ struct LockTraitsBase : public LockTraitsSharedBase { * 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, timeout) - * - lock_shared(Mutex& mutex) - * - unlock_shared(Mutex& mutex) - * - try_lock_shared_for(Mutex& mutex, 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 +struct LockTraitsBase + : public detail::LockTraitsImpl< + Mutex, + detail::MutexLevelValueImpl< + detail::LockInterfaceDispatcher::has_lock_unique, + detail::LockInterfaceDispatcher::has_lock_shared, + detail::LockInterfaceDispatcher::has_lock_upgrade>::value, + detail::LockInterfaceDispatcher::has_lock_timed> {}; + template -struct LockTraits : public detail::LockTraitsBase< - Mutex, - detail::LockTraitsImpl::has_lock_shared, - detail::LockTraitsImpl::has_timed_lock> {}; +struct LockTraits : public LockTraitsBase {}; /** * If the lock is a shared lock, acquire it in shared mode. diff --git a/folly/LockTraitsBoost.h b/folly/LockTraitsBoost.h index 459a5fe8..0d86d235 100644 --- a/folly/LockTraitsBoost.h +++ b/folly/LockTraitsBoost.h @@ -44,7 +44,7 @@ boost::chrono::duration> toBoostDuration( */ template <> struct LockTraits - : public folly::detail::LockTraitsSharedBase { + : public LockTraitsBase { static constexpr bool is_shared = true; static constexpr bool is_timed = true; @@ -68,7 +68,7 @@ struct LockTraits */ template <> struct LockTraits - : public folly::detail::LockTraitsUniqueBase { + : public LockTraitsBase { static constexpr bool is_shared = false; static constexpr bool is_timed = true; @@ -85,7 +85,7 @@ struct LockTraits */ template <> struct LockTraits - : public folly::detail::LockTraitsUniqueBase { + : public LockTraitsBase { static constexpr bool is_shared = false; static constexpr bool is_timed = true; diff --git a/folly/test/LockTraitsTest.cpp b/folly/test/LockTraitsTest.cpp index df43a8a0..be9f0ec9 100644 --- a/folly/test/LockTraitsTest.cpp +++ b/folly/test/LockTraitsTest.cpp @@ -25,10 +25,13 @@ using namespace folly; +static constexpr auto one_ms = std::chrono::milliseconds(1); + TEST(LockTraits, std_mutex) { using traits = LockTraits; static_assert(!traits::is_timed, "std:mutex is not a timed lock"); static_assert(!traits::is_shared, "std:mutex is not a shared lock"); + static_assert(!traits::is_upgrade, "std::mutex is not an upgradable lock"); std::mutex mutex; traits::lock(mutex); @@ -40,8 +43,9 @@ TEST(LockTraits, std_mutex) { TEST(LockTraits, SharedMutex) { using traits = LockTraits; - static_assert(traits::is_timed, "SharedMutex is a timed lock"); - static_assert(traits::is_shared, "SharedMutex is a shared lock"); + static_assert(traits::is_timed, "folly::SharedMutex is a timed lock"); + static_assert(traits::is_shared, "folly::SharedMutex is a shared lock"); + static_assert(traits::is_upgrade, "folly::SharedMutex is an upgradable lock"); SharedMutex mutex; traits::lock(mutex); @@ -56,12 +60,62 @@ TEST(LockTraits, SharedMutex) { lock_shared_or_unique(mutex); unlock_shared_or_unique(mutex); unlock_shared_or_unique(mutex); + + traits::lock_upgrade(mutex); + traits::unlock_upgrade(mutex); + + // test upgrade and downgrades + traits::lock_upgrade(mutex); + traits::unlock_upgrade_and_lock(mutex); + bool gotLock = traits::try_lock_for(mutex, one_ms); + EXPECT_FALSE(gotLock) << "Should not have been able to acquire an exclusive " + "lock after upgrading to an exclusive lock"; + gotLock = traits::try_lock_upgrade_for(mutex, one_ms); + EXPECT_FALSE(gotLock) << "Should not have been able to acquire an upgrade " + "lock after upgrading to an exclusive lock"; + gotLock = traits::try_lock_shared_for(mutex, one_ms); + EXPECT_FALSE(gotLock) << "Should not have been able to acquire a shared " + "lock after upgrading to an exclusive lock"; + traits::unlock(mutex); + + traits::lock_upgrade(mutex); + traits::unlock_upgrade_and_lock_shared(mutex); + gotLock = traits::try_lock_for(mutex, one_ms); + EXPECT_FALSE(gotLock) << "Should not have been able to acquire an exclusive " + "mutex after downgrading from an upgrade to a " + "shared lock"; + traits::unlock_shared(mutex); + + traits::lock(mutex); + gotLock = traits::try_lock_for(mutex, one_ms); + EXPECT_FALSE(gotLock) << "Should not have been able to acquire an exclusive " + "lock after acquiring an exclusive lock"; + gotLock = traits::try_lock_upgrade_for(mutex, one_ms); + EXPECT_FALSE(gotLock) << "Should not have been able to acquire an upgrade " + "lock after acquiring an exclusive lock"; + gotLock = traits::try_lock_shared_for(mutex, one_ms); + EXPECT_FALSE(gotLock) << "Should not have been able to acquire a shared " + "lock after acquiring an exclusive lock"; + traits::unlock_and_lock_upgrade(mutex); + gotLock = traits::try_lock_for(mutex, one_ms); + EXPECT_FALSE(gotLock) << "Should not have been able to acquire an exclusive " + "lock after downgrading to an upgrade lock"; + traits::unlock_upgrade(mutex); + + traits::lock(mutex); + traits::unlock_and_lock_shared(mutex); + gotLock = traits::try_lock_for(mutex, one_ms); + EXPECT_FALSE(gotLock) << "Should not have been able to acquire an exclusive " + "lock after downgrading to a shared lock"; + traits::unlock_shared(mutex); } TEST(LockTraits, SpinLock) { using traits = LockTraits; static_assert(!traits::is_timed, "folly::SpinLock is not a timed lock"); static_assert(!traits::is_shared, "folly::SpinLock is not a shared lock"); + static_assert( + !traits::is_upgrade, "folly::SpinLock is not an upgradable lock"); SpinLock mutex; traits::lock(mutex); @@ -75,6 +129,7 @@ TEST(LockTraits, RWSpinLock) { using traits = LockTraits; static_assert(!traits::is_timed, "folly::RWSpinLock is not a timed lock"); static_assert(traits::is_shared, "folly::RWSpinLock is a shared lock"); + static_assert(traits::is_upgrade, "folly::RWSpinLock is an upgradable lock"); RWSpinLock mutex; traits::lock(mutex); @@ -95,6 +150,7 @@ TEST(LockTraits, boost_mutex) { using traits = LockTraits; static_assert(!traits::is_timed, "boost::mutex is not a timed lock"); static_assert(!traits::is_shared, "boost::mutex is not a shared lock"); + static_assert(!traits::is_upgrade, "boost::mutex is not an upgradable lock"); boost::mutex mutex; traits::lock(mutex); @@ -110,6 +166,8 @@ TEST(LockTraits, boost_recursive_mutex) { !traits::is_timed, "boost::recursive_mutex is not a timed lock"); static_assert( !traits::is_shared, "boost::recursive_mutex is not a shared lock"); + static_assert( + !traits::is_upgrade, "boost::recursive_mutex is not an upgradable lock"); boost::recursive_mutex mutex; traits::lock(mutex); @@ -128,6 +186,8 @@ TEST(LockTraits, timed_mutex) { using traits = LockTraits; static_assert(traits::is_timed, "std::timed_mutex is a timed lock"); static_assert(!traits::is_shared, "std::timed_mutex is not a shared lock"); + static_assert( + !traits::is_upgrade, "std::timed_mutex is not an upgradable lock"); std::timed_mutex mutex; traits::lock(mutex); @@ -148,6 +208,9 @@ TEST(LockTraits, recursive_timed_mutex) { static_assert(traits::is_timed, "std::recursive_timed_mutex is a timed lock"); static_assert( !traits::is_shared, "std::recursive_timed_mutex is not a shared lock"); + static_assert( + !traits::is_upgrade, + "std::recursive_timed_mutex is not an upgradable lock"); std::recursive_timed_mutex mutex; traits::lock(mutex); @@ -169,6 +232,8 @@ TEST(LockTraits, boost_shared_mutex) { using traits = LockTraits; static_assert(traits::is_timed, "boost::shared_mutex is a timed lock"); static_assert(traits::is_shared, "boost::shared_mutex is a shared lock"); + static_assert( + traits::is_upgrade, "boost::shared_mutex is an upgradable lock"); boost::shared_mutex mutex; traits::lock(mutex); diff --git a/folly/test/SynchronizedTest.cpp b/folly/test/SynchronizedTest.cpp index fb77721e..5826ef28 100644 --- a/folly/test/SynchronizedTest.cpp +++ b/folly/test/SynchronizedTest.cpp @@ -154,14 +154,12 @@ using CountPair = std::pair; // This class is specialized only to be uesed in SynchronizedLockTest class FakeMutex { public: - bool lock() { + void lock() { ++lockCount_; - return true; } - bool unlock() { + void unlock() { ++unlockCount_; - return true; } static CountPair getLockUnlockCount() { -- 2.34.1