X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FLockTraits.h;h=2f051f5cbfd9bfdd17eb1d2f4a2981036fc46562;hb=3d9eb7ffc32c2f5f878bb4aee61d30cb8c62a146;hp=3b0d21a25d61e0867171ad9f07e7c764c9981a77;hpb=9276f2a5646a94eda765c92b171b98c499313213;p=folly.git

diff --git a/folly/LockTraits.h b/folly/LockTraits.h
index 3b0d21a2..2f051f5c 100644
--- a/folly/LockTraits.h
+++ b/folly/LockTraits.h
@@ -1,5 +1,5 @@
 /*
- * 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.
@@ -27,6 +27,8 @@
 #include <chrono>
 #include <type_traits>
 
+#include <folly/functional/Invoke.h>
+
 // Android, OSX, and Cygwin don't have timed mutexes
 #if defined(ANDROID) || defined(__ANDROID__) || defined(__APPLE__) || \
     defined(__CYGWIN__)
@@ -38,36 +40,83 @@
 namespace folly {
 namespace detail {
 
+namespace member {
+FOLLY_CREATE_MEMBER_INVOKE_TRAITS(lock, lock);
+FOLLY_CREATE_MEMBER_INVOKE_TRAITS(try_lock_for, try_lock_for);
+FOLLY_CREATE_MEMBER_INVOKE_TRAITS(lock_shared, lock_shared);
+FOLLY_CREATE_MEMBER_INVOKE_TRAITS(lock_upgrade, lock_upgrade);
+} // namespace member
+
+/**
+ * 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 for identifying if a lock type supports
- * lock_shared() and try_lock_for() methods.
+ * 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
  */
 template <class Mutex>
-class LockTraitsImpl {
+class LockInterfaceDispatcher {
  private:
-  // Helper functions for implementing the traits using SFINAE
-  template <class T>
-  static auto timed_lock_test(T*) -> typename std::is_same<
-      decltype(std::declval<T>().try_lock_for(std::chrono::milliseconds(0))),
-      bool>::type;
-  template <class T>
-  static std::false_type timed_lock_test(...);
-
-  template <class T>
-  static auto lock_shared_test(T*) -> typename std::
-      is_same<decltype(std::declval<T>().lock_shared()), void>::type;
-  template <class T>
-  static std::false_type lock_shared_test(...);
+  // assert that the mutex type has basic lock and unlock functions
+  static_assert(
+      member::lock::is_invocable<Mutex>::value,
+      "The mutex type must support lock and unlock functions");
+
+  using duration = std::chrono::milliseconds;
 
  public:
-  static constexpr bool has_timed_lock =
-      decltype(timed_lock_test<Mutex>(0))::value;
+  static constexpr bool has_lock_unique = true;
+  static constexpr bool has_lock_timed =
+      member::try_lock_for::is_invocable<Mutex, duration>::value;
   static constexpr bool has_lock_shared =
-      decltype(lock_shared_test<Mutex>(0))::value;
+      member::lock_shared::is_invocable<Mutex>::value;
+  static constexpr bool has_lock_upgrade =
+      member::lock_upgrade::is_invocable<Mutex>::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.
    */
@@ -83,8 +132,17 @@ struct LockTraitsUniqueBase {
   }
 };
 
+/**
+ * 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.
    */
@@ -100,26 +158,89 @@ struct LockTraitsSharedBase : public LockTraitsUniqueBase<Mutex> {
   }
 };
 
-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.
@@ -134,10 +255,18 @@ struct LockTraitsBase<Mutex, false, true> : public LockTraitsUniqueBase<Mutex> {
   }
 };
 
+/**
+ * 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.
@@ -163,7 +292,41 @@ struct LockTraitsBase<Mutex, true, true> : public LockTraitsSharedBase<Mutex> {
     return mutex.try_lock_shared_for(timeout);
   }
 };
-} // detail
+
+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);
+  }
+};
+
+} // namespace detail
 
 /**
  * LockTraits describes details about a particular mutex type.
@@ -181,23 +344,50 @@ struct LockTraitsBase<Mutex, true, true> : public LockTraitsSharedBase<Mutex> {
  *   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.
@@ -249,4 +439,190 @@ typename std::enable_if<!LockTraits<Mutex>::is_shared>::type
 unlock_shared_or_unique(Mutex& mutex) {
   LockTraits<Mutex>::unlock(mutex);
 }
-} // folly
+
+/*
+ * Lock policy classes.
+ *
+ * These can be used as template parameters to provide compile-time
+ * selection over the type of lock operation to perform.
+ */
+
+/**
+ * A lock policy that performs exclusive lock operations.
+ */
+struct LockPolicyExclusive {
+  template <class Mutex>
+  static void lock(Mutex& mutex) {
+    LockTraits<Mutex>::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_lock_for(mutex, timeout);
+  }
+  template <class Mutex>
+  static void unlock(Mutex& mutex) {
+    LockTraits<Mutex>::unlock(mutex);
+  }
+};
+
+/**
+ * A lock policy that performs shared lock operations.
+ * This policy only works with shared mutex types.
+ */
+struct LockPolicyShared {
+  template <class Mutex>
+  static void lock(Mutex& mutex) {
+    LockTraits<Mutex>::lock_shared(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_shared_for(mutex, timeout);
+  }
+  template <class Mutex>
+  static void unlock(Mutex& mutex) {
+    LockTraits<Mutex>::unlock_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.
+ */
+struct LockPolicyShareable {
+  template <class Mutex>
+  static void lock(Mutex& mutex) {
+    lock_shared_or_unique(mutex);
+  }
+  template <class Mutex, class Rep, class Period>
+  static bool try_lock_for(
+      Mutex& mutex,
+      const std::chrono::duration<Rep, Period>& timeout) {
+    return try_lock_shared_or_unique_for(mutex, timeout);
+  }
+  template <class Mutex>
+  static void unlock(Mutex& mutex) {
+    unlock_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;
+  }
+};
+
+} // namespace folly