folly/LockTraits.h

   1 /*
   2  * Copyright 2016-present Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /**
  18  * This module provides a traits class for describing properties about mutex
  19  * classes.
  20  *
  21  * This is a primitive for building higher-level abstractions that can work
  22  * with a variety of mutex classes.  For instance, this allows
  23  * folly::Synchronized to support a number of different mutex types.
  24  */
  25 #pragma once
  26
  27 #include <chrono>
  28 #include <type_traits>
  29
  30 #include <folly/functional/Invoke.h>
  31
  32 // Android, OSX, and Cygwin don't have timed mutexes
  33 #if defined(ANDROID) || defined(__ANDROID__) || defined(__APPLE__) || \
  34     defined(__CYGWIN__)
  35 #define FOLLY_LOCK_TRAITS_HAVE_TIMED_MUTEXES 0
  36 #else
  37 #define FOLLY_LOCK_TRAITS_HAVE_TIMED_MUTEXES 1
  38 #endif
  39
  40 namespace folly {
  41 namespace detail {
  42
  43 namespace member {
  44 FOLLY_CREATE_MEMBER_INVOKE_TRAITS(lock, lock);
  45 FOLLY_CREATE_MEMBER_INVOKE_TRAITS(try_lock_for, try_lock_for);
  46 FOLLY_CREATE_MEMBER_INVOKE_TRAITS(lock_shared, lock_shared);
  47 FOLLY_CREATE_MEMBER_INVOKE_TRAITS(lock_upgrade, lock_upgrade);
  48 } // namespace member
  49
  50 /**
  51  * An enum to describe the "level" of a mutex.  The supported levels are
  52  *  Unique - a normal mutex that supports only exclusive locking
  53  *  Shared - a shared mutex which has shared locking and unlocking functions;
  54  *  Upgrade - a mutex that has all the methods of the two above along with
  55  *            support for upgradable locking
  56  */
  57 enum class MutexLevel { UNIQUE, SHARED, UPGRADE };
  58
  59 /**
  60  * A template dispatch mechanism that is used to determine the level of the
  61  * mutex based on its interface.  As decided by LockInterfaceDispatcher.
  62  */
  63 template <bool is_unique, bool is_shared, bool is_upgrade>
  64 struct MutexLevelValueImpl;
  65 template <>
  66 struct MutexLevelValueImpl<true, false, false> {
  67   static constexpr MutexLevel value = MutexLevel::UNIQUE;
  68 };
  69 template <>
  70 struct MutexLevelValueImpl<true, true, false> {
  71   static constexpr MutexLevel value = MutexLevel::SHARED;
  72 };
  73 template <>
  74 struct MutexLevelValueImpl<true, true, true> {
  75   static constexpr MutexLevel value = MutexLevel::UPGRADE;
  76 };
  77
  78 /**
  79  * An internal helper class to help identify the interface supported by the
  80  * mutex.  This is used in conjunction with the above MutexLevel
  81  * specializations and the LockTraitsImpl to determine what functions are
  82  * supported by objects of type Mutex
  83  */
  84 template <class Mutex>
  85 class LockInterfaceDispatcher {
  86  private:
  87   // assert that the mutex type has basic lock and unlock functions
  88   static_assert(
  89       member::lock::is_invocable<Mutex>::value,
  90       "The mutex type must support lock and unlock functions");
  91
  92   using duration = std::chrono::milliseconds;
  93
  94  public:
  95   static constexpr bool has_lock_unique = true;
  96   static constexpr bool has_lock_timed =
  97       member::try_lock_for::is_invocable<Mutex, duration>::value;
  98   static constexpr bool has_lock_shared =
  99       member::lock_shared::is_invocable<Mutex>::value;
 100   static constexpr bool has_lock_upgrade =
 101       member::lock_upgrade::is_invocable<Mutex>::value;
 102 };
 103
 104 /**
 105  * LockTraitsImpl is the base that is used to desribe the interface used by
 106  * different mutex types.  It accepts a MutexLevel argument and a boolean to
 107  * show whether the mutex is a timed mutex or not.  The implementations are
 108  * partially specialized and inherit from the other implementations to get
 109  * similar functionality
 110  */
 111 template <class Mutex, MutexLevel level, bool is_timed>
 112 struct LockTraitsImpl;
 113
 114 template <class Mutex>
 115 struct LockTraitsImpl<Mutex, MutexLevel::UNIQUE, false> {
 116   static constexpr bool is_timed{false};
 117   static constexpr bool is_shared{false};
 118   static constexpr bool is_upgrade{false};
 119
 120   /**
 121    * Acquire the lock exclusively.
 122    */
 123   static void lock(Mutex& mutex) {
 124     mutex.lock();
 125   }
 126
 127   /**
 128    * Release an exclusively-held lock.
 129    */
 130   static void unlock(Mutex& mutex) {
 131     mutex.unlock();
 132   }
 133 };
 134
 135 /**
 136  * Higher level mutexes have all the capabilities of the lower levels so
 137  * inherit
 138  */
 139 template <class Mutex>
 140 struct LockTraitsImpl<Mutex, MutexLevel::SHARED, false>
 141     : public LockTraitsImpl<Mutex, MutexLevel::UNIQUE, false> {
 142   static constexpr bool is_timed{false};
 143   static constexpr bool is_shared{true};
 144   static constexpr bool is_upgrade{false};
 145
 146   /**
 147    * Acquire the lock in shared (read) mode.
 148    */
 149   static void lock_shared(Mutex& mutex) {
 150     mutex.lock_shared();
 151   }
 152
 153   /**
 154    * Release a lock held in shared mode.
 155    */
 156   static void unlock_shared(Mutex& mutex) {
 157     mutex.unlock_shared();
 158   }
 159 };
 160
 161 /**
 162  * The following methods are supported.  There are a few methods
 163  *
 164  *  m.lock_upgrade()
 165  *  m.unlock_upgrade()
 166  *
 167  *  m.unlock_upgrade_and_lock()
 168  *
 169  *  m.unlock_and_lock_upgrade()
 170  *  m.unlock_and_lock_shared()
 171  *  m.unlock_upgrade_and_lock_shared()
 172  *
 173  *  m.try_lock_upgrade_for(rel_time)
 174  *  m.try_unlock_upgrade_and_lock_for(rel_time)
 175  *
 176  * Upgrading a shared lock is likely to deadlock when there is more than one
 177  * thread performing an upgrade.  This applies both to upgrading a shared lock
 178  * to an upgrade lock and to upgrading a shared lock to a unique lock.
 179  *
 180  * Therefore, none of the following methods is supported:
 181  *  unlock_shared_and_lock_upgrade
 182  *  unlock_shared_and_lock
 183  *  try_unlock_shared_and_lock_upgrade
 184  *  try_unlock_shared_and_lock
 185  *  try_unlock_shared_and_lock_upgrade_for
 186  *  try_unlock_shared_and_lock_for
 187  */
 188 template <class Mutex>
 189 struct LockTraitsImpl<Mutex, MutexLevel::UPGRADE, false>
 190     : public LockTraitsImpl<Mutex, MutexLevel::SHARED, false> {
 191   static constexpr bool is_timed{false};
 192   static constexpr bool is_shared{true};
 193   static constexpr bool is_upgrade{true};
 194
 195   /**
 196    * Acquire the lock in upgradable mode.
 197    */
 198   static void lock_upgrade(Mutex& mutex) {
 199     mutex.lock_upgrade();
 200   }
 201
 202   /**
 203    * Release the lock in upgrade mode
 204    */
 205   static void unlock_upgrade(Mutex& mutex) {
 206     mutex.unlock_upgrade();
 207   }
 208
 209   /**
 210    * Upgrade from an upgradable state to an exclusive state
 211    */
 212   static void unlock_upgrade_and_lock(Mutex& mutex) {
 213     mutex.unlock_upgrade_and_lock();
 214   }
 215
 216   /**
 217    * Downgrade from an exclusive state to an upgrade state
 218    */
 219   static void unlock_and_lock_upgrade(Mutex& mutex) {
 220     mutex.unlock_and_lock_upgrade();
 221   }
 222
 223   /**
 224    * Downgrade from an exclusive state to a shared state
 225    */
 226   static void unlock_and_lock_shared(Mutex& mutex) {
 227     mutex.unlock_and_lock_shared();
 228   }
 229
 230   /**
 231    * Downgrade from an upgrade state to a shared state
 232    */
 233   static void unlock_upgrade_and_lock_shared(Mutex& mutex) {
 234     mutex.unlock_upgrade_and_lock_shared();
 235   }
 236 };
 237
 238 template <class Mutex>
 239 struct LockTraitsImpl<Mutex, MutexLevel::UNIQUE, true>
 240     : public LockTraitsImpl<Mutex, MutexLevel::UNIQUE, false> {
 241   static constexpr bool is_timed{true};
 242   static constexpr bool is_shared{false};
 243   static constexpr bool is_upgrade{false};
 244
 245   /**
 246    * Acquire the lock exclusively, with a timeout.
 247    *
 248    * Returns true or false indicating if the lock was acquired or not.
 249    */
 250   template <class Rep, class Period>
 251   static bool try_lock_for(
 252       Mutex& mutex,
 253       const std::chrono::duration<Rep, Period>& timeout) {
 254     return mutex.try_lock_for(timeout);
 255   }
 256 };
 257
 258 /**
 259  * Note that there is no deadly diamond here because all the structs only have
 260  * static functions and static bools which are going to be overridden by the
 261  * lowest level implementation
 262  */
 263 template <class Mutex>
 264 struct LockTraitsImpl<Mutex, MutexLevel::SHARED, true>
 265     : public LockTraitsImpl<Mutex, MutexLevel::SHARED, false>,
 266       public LockTraitsImpl<Mutex, MutexLevel::UNIQUE, true> {
 267   static constexpr bool is_timed{true};
 268   static constexpr bool is_shared{true};
 269   static constexpr bool is_upgrade{false};
 270
 271   /**
 272    * Acquire the lock exclusively, with a timeout.
 273    *
 274    * Returns true or false indicating if the lock was acquired or not.
 275    */
 276   template <class Rep, class Period>
 277   static bool try_lock_for(
 278       Mutex& mutex,
 279       const std::chrono::duration<Rep, Period>& timeout) {
 280     return mutex.try_lock_for(timeout);
 281   }
 282
 283   /**
 284    * Acquire the lock in shared (read) mode, with a timeout.
 285    *
 286    * Returns true or false indicating if the lock was acquired or not.
 287    */
 288   template <class Rep, class Period>
 289   static bool try_lock_shared_for(
 290       Mutex& mutex,
 291       const std::chrono::duration<Rep, Period>& timeout) {
 292     return mutex.try_lock_shared_for(timeout);
 293   }
 294 };
 295
 296 template <class Mutex>
 297 struct LockTraitsImpl<Mutex, MutexLevel::UPGRADE, true>
 298     : public LockTraitsImpl<Mutex, MutexLevel::UPGRADE, false>,
 299       public LockTraitsImpl<Mutex, MutexLevel::SHARED, true> {
 300   static constexpr bool is_timed{true};
 301   static constexpr bool is_shared{true};
 302   static constexpr bool is_upgrade{true};
 303
 304   /**
 305    * Acquire the lock in upgrade mode with a timeout
 306    *
 307    * Returns true or false indicating whether the lock was acquired or not
 308    */
 309   template <class Rep, class Period>
 310   static bool try_lock_upgrade_for(
 311       Mutex& mutex,
 312       const std::chrono::duration<Rep, Period>& timeout) {
 313     return mutex.try_lock_upgrade_for(timeout);
 314   }
 315
 316   /**
 317    * Try to upgrade from an upgradable state to an exclusive state.
 318    *
 319    * Returns true or false indicating whether the lock was acquired or not
 320    */
 321   template <class Rep, class Period>
 322   static bool try_unlock_upgrade_and_lock_for(
 323       Mutex& mutex,
 324       const std::chrono::duration<Rep, Period>& timeout) {
 325     return mutex.try_unlock_upgrade_and_lock_for(timeout);
 326   }
 327 };
 328
 329 } // namespace detail
 330
 331 /**
 332  * LockTraits describes details about a particular mutex type.
 333  *
 334  * The default implementation automatically attempts to detect traits
 335  * based on the presence of various member functions.
 336  *
 337  * You can specialize LockTraits to provide custom behavior for lock
 338  * classes that do not use the standard method names
 339  * (lock()/unlock()/lock_shared()/unlock_shared()/try_lock_for())
 340  *
 341  *
 342  * LockTraits contains the following members variables:
 343  * - static constexpr bool is_shared
 344  *   True if the lock supports separate shared vs exclusive locking states.
 345  * - static constexpr bool is_timed
 346  *   True if the lock supports acquiring the lock with a timeout.
 347  * - static constexpr bool is_upgrade
 348  *   True if the lock supports an upgradable state
 349  *
 350  * The following static methods always exist:
 351  * - lock(Mutex& mutex)
 352  * - unlock(Mutex& mutex)
 353  *
 354  * The following static methods may exist, depending on is_shared, is_timed
 355  * and is_upgrade:
 356  * - lock_shared()
 357  *
 358  * - try_lock_for()
 359  * - try_lock_shared_for()
 360  *
 361  * - lock_upgrade()
 362  * - unlock_upgrade_and_lock()
 363  * - unlock_and_lock_upgrade()
 364  * - unlock_and_lock_shared()
 365  * - unlock_upgrade_and_lock_shared()
 366  *
 367  * - try_lock_upgrade_for()
 368  * - try_unlock_upgrade_and_lock_for()
 369  *
 370  * - unlock_shared()
 371  * - unlock_upgrade()
 372  */
 373
 374 /**
 375  * Decoupling LockTraits and LockTraitsBase so that if people want to fully
 376  * specialize LockTraits then they can inherit from LockTraitsBase instead
 377  * of LockTraits with all the same goodies :)
 378  */
 379 template <class Mutex>
 380 struct LockTraitsBase
 381     : public detail::LockTraitsImpl<
 382           Mutex,
 383           detail::MutexLevelValueImpl<
 384               detail::LockInterfaceDispatcher<Mutex>::has_lock_unique,
 385               detail::LockInterfaceDispatcher<Mutex>::has_lock_shared,
 386               detail::LockInterfaceDispatcher<Mutex>::has_lock_upgrade>::value,
 387           detail::LockInterfaceDispatcher<Mutex>::has_lock_timed> {};
 388
 389 template <class Mutex>
 390 struct LockTraits : public LockTraitsBase<Mutex> {};
 391
 392 /**
 393  * If the lock is a shared lock, acquire it in shared mode.
 394  * Otherwise, for plain (exclusive-only) locks, perform a normal acquire.
 395  */
 396 template <class Mutex>
 397 typename std::enable_if<LockTraits<Mutex>::is_shared>::type
 398 lock_shared_or_unique(Mutex& mutex) {
 399   LockTraits<Mutex>::lock_shared(mutex);
 400 }
 401 template <class Mutex>
 402 typename std::enable_if<!LockTraits<Mutex>::is_shared>::type
 403 lock_shared_or_unique(Mutex& mutex) {
 404   LockTraits<Mutex>::lock(mutex);
 405 }
 406
 407 /**
 408  * If the lock is a shared lock, try to acquire it in shared mode, for up to
 409  * the given timeout.  Otherwise, for plain (exclusive-only) locks, try to
 410  * perform a normal acquire.
 411  *
 412  * Returns true if the lock was acquired, or false on time out.
 413  */
 414 template <class Mutex, class Rep, class Period>
 415 typename std::enable_if<LockTraits<Mutex>::is_shared, bool>::type
 416 try_lock_shared_or_unique_for(
 417     Mutex& mutex,
 418     const std::chrono::duration<Rep, Period>& timeout) {
 419   return LockTraits<Mutex>::try_lock_shared_for(mutex, timeout);
 420 }
 421 template <class Mutex, class Rep, class Period>
 422 typename std::enable_if<!LockTraits<Mutex>::is_shared, bool>::type
 423 try_lock_shared_or_unique_for(
 424     Mutex& mutex,
 425     const std::chrono::duration<Rep, Period>& timeout) {
 426   return LockTraits<Mutex>::try_lock_for(mutex, timeout);
 427 }
 428
 429 /**
 430  * Release a lock acquired with lock_shared_or_unique()
 431  */
 432 template <class Mutex>
 433 typename std::enable_if<LockTraits<Mutex>::is_shared>::type
 434 unlock_shared_or_unique(Mutex& mutex) {
 435   LockTraits<Mutex>::unlock_shared(mutex);
 436 }
 437 template <class Mutex>
 438 typename std::enable_if<!LockTraits<Mutex>::is_shared>::type
 439 unlock_shared_or_unique(Mutex& mutex) {
 440   LockTraits<Mutex>::unlock(mutex);
 441 }
 442
 443 /*
 444  * Lock policy classes.
 445  *
 446  * These can be used as template parameters to provide compile-time
 447  * selection over the type of lock operation to perform.
 448  */
 449
 450 /**
 451  * A lock policy that performs exclusive lock operations.
 452  */
 453 struct LockPolicyExclusive {
 454   template <class Mutex>
 455   static void lock(Mutex& mutex) {
 456     LockTraits<Mutex>::lock(mutex);
 457   }
 458   template <class Mutex, class Rep, class Period>
 459   static bool try_lock_for(
 460       Mutex& mutex,
 461       const std::chrono::duration<Rep, Period>& timeout) {
 462     return LockTraits<Mutex>::try_lock_for(mutex, timeout);
 463   }
 464   template <class Mutex>
 465   static void unlock(Mutex& mutex) {
 466     LockTraits<Mutex>::unlock(mutex);
 467   }
 468 };
 469
 470 /**
 471  * A lock policy that performs shared lock operations.
 472  * This policy only works with shared mutex types.
 473  */
 474 struct LockPolicyShared {
 475   template <class Mutex>
 476   static void lock(Mutex& mutex) {
 477     LockTraits<Mutex>::lock_shared(mutex);
 478   }
 479   template <class Mutex, class Rep, class Period>
 480   static bool try_lock_for(
 481       Mutex& mutex,
 482       const std::chrono::duration<Rep, Period>& timeout) {
 483     return LockTraits<Mutex>::try_lock_shared_for(mutex, timeout);
 484   }
 485   template <class Mutex>
 486   static void unlock(Mutex& mutex) {
 487     LockTraits<Mutex>::unlock_shared(mutex);
 488   }
 489 };
 490
 491 /**
 492  * A lock policy that performs a shared lock operation if a shared mutex type
 493  * is given, or a normal exclusive lock operation on non-shared mutex types.
 494  */
 495 struct LockPolicyShareable {
 496   template <class Mutex>
 497   static void lock(Mutex& mutex) {
 498     lock_shared_or_unique(mutex);
 499   }
 500   template <class Mutex, class Rep, class Period>
 501   static bool try_lock_for(
 502       Mutex& mutex,
 503       const std::chrono::duration<Rep, Period>& timeout) {
 504     return try_lock_shared_or_unique_for(mutex, timeout);
 505   }
 506   template <class Mutex>
 507   static void unlock(Mutex& mutex) {
 508     unlock_shared_or_unique(mutex);
 509   }
 510 };
 511
 512 /**
 513  * A lock policy with the following mapping
 514  *
 515  *  lock() -> lock_upgrade()
 516  *  unlock() -> unlock_upgrade()
 517  *  try_lock_for -> try_lock_upgrade_for()
 518  */
 519 struct LockPolicyUpgrade {
 520   template <class Mutex>
 521   static void lock(Mutex& mutex) {
 522     LockTraits<Mutex>::lock_upgrade(mutex);
 523   }
 524   template <class Mutex, class Rep, class Period>
 525   static bool try_lock_for(
 526       Mutex& mutex,
 527       const std::chrono::duration<Rep, Period>& timeout) {
 528     return LockTraits<Mutex>::try_lock_upgrade_for(mutex, timeout);
 529   }
 530   template <class Mutex>
 531   static void unlock(Mutex& mutex) {
 532     LockTraits<Mutex>::unlock_upgrade(mutex);
 533   }
 534 };
 535
 536 /*****************************************************************************
 537  * Policies for all the transitions from possible mutex levels
 538  ****************************************************************************/
 539 /**
 540  * A lock policy with the following mapping
 541  *
 542  *  lock() -> unlock_upgrade_and_lock()
 543  *  unlock() -> unlock()
 544  *  try_lock_for -> try_unlock_upgrade_and_lock_for()
 545  */
 546 struct LockPolicyFromUpgradeToExclusive : public LockPolicyExclusive {
 547   template <class Mutex>
 548   static void lock(Mutex& mutex) {
 549     LockTraits<Mutex>::unlock_upgrade_and_lock(mutex);
 550   }
 551   template <class Mutex, class Rep, class Period>
 552   static bool try_lock_for(
 553       Mutex& mutex,
 554       const std::chrono::duration<Rep, Period>& timeout) {
 555     return LockTraits<Mutex>::try_unlock_upgrade_and_lock_for(mutex, timeout);
 556   }
 557 };
 558
 559 /**
 560  * A lock policy with the following mapping
 561  *
 562  *  lock() -> unlock_and_lock_upgrade()
 563  *  unlock() -> unlock_upgrade()
 564  *  try_lock_for -> unlock_and_lock_upgrade()
 565  */
 566 struct LockPolicyFromExclusiveToUpgrade : public LockPolicyUpgrade {
 567   template <class Mutex>
 568   static void lock(Mutex& mutex) {
 569     LockTraits<Mutex>::unlock_and_lock_upgrade(mutex);
 570   }
 571   template <class Mutex, class Rep, class Period>
 572   static bool try_lock_for(
 573       Mutex& mutex,
 574       const std::chrono::duration<Rep, Period>&) {
 575     LockTraits<Mutex>::unlock_and_lock_upgrade(mutex);
 576
 577     // downgrade should be non blocking and should succeed
 578     return true;
 579   }
 580 };
 581
 582 /**
 583  * A lock policy with the following mapping
 584  *
 585  *  lock() -> unlock_upgrade_and_lock_shared()
 586  *  unlock() -> unlock_shared()
 587  *  try_lock_for -> unlock_upgrade_and_lock_shared()
 588  */
 589 struct LockPolicyFromUpgradeToShared : public LockPolicyShared {
 590   template <class Mutex>
 591   static void lock(Mutex& mutex) {
 592     LockTraits<Mutex>::unlock_upgrade_and_lock_shared(mutex);
 593   }
 594   template <class Mutex, class Rep, class Period>
 595   static bool try_lock_for(
 596       Mutex& mutex,
 597       const std::chrono::duration<Rep, Period>&) {
 598     LockTraits<Mutex>::unlock_upgrade_and_lock_shared(mutex);
 599
 600     // downgrade should be non blocking and should succeed
 601     return true;
 602   }
 603 };
 604
 605 /**
 606  * A lock policy with the following mapping
 607  *
 608  *  lock() -> unlock_and_lock_shared()
 609  *  unlock() -> unlock_shared()
 610  *  try_lock_for() -> unlock_and_lock_shared()
 611  */
 612 struct LockPolicyFromExclusiveToShared : public LockPolicyShared {
 613   template <class Mutex>
 614   static void lock(Mutex& mutex) {
 615     LockTraits<Mutex>::unlock_and_lock_shared(mutex);
 616   }
 617   template <class Mutex, class Rep, class Period>
 618   static bool try_lock_for(
 619       Mutex& mutex,
 620       const std::chrono::duration<Rep, Period>&) {
 621     LockTraits<Mutex>::unlock_and_lock_shared(mutex);
 622
 623     // downgrade should be non blocking and should succeed
 624     return true;
 625   }
 626 };
 627
 628 } // namespace folly