folly/LockTraits.h

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