2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 * This module provides a traits class for describing properties about mutex
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.
28 #include <type_traits>
30 #include <folly/functional/Invoke.h>
32 // Android, OSX, and Cygwin don't have timed mutexes
33 #if defined(ANDROID) || defined(__ANDROID__) || defined(__APPLE__) || \
35 #define FOLLY_LOCK_TRAITS_HAVE_TIMED_MUTEXES 0
37 #define FOLLY_LOCK_TRAITS_HAVE_TIMED_MUTEXES 1
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);
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
57 enum class MutexLevel { UNIQUE, SHARED, UPGRADE };
60 * A template dispatch mechanism that is used to determine the level of the
61 * mutex based on its interface. As decided by LockInterfaceDispatcher.
63 template <bool is_unique, bool is_shared, bool is_upgrade>
64 struct MutexLevelValueImpl;
66 struct MutexLevelValueImpl<true, false, false> {
67 static constexpr MutexLevel value = MutexLevel::UNIQUE;
70 struct MutexLevelValueImpl<true, true, false> {
71 static constexpr MutexLevel value = MutexLevel::SHARED;
74 struct MutexLevelValueImpl<true, true, true> {
75 static constexpr MutexLevel value = MutexLevel::UPGRADE;
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
84 template <class Mutex>
85 class LockInterfaceDispatcher {
87 // assert that the mutex type has basic lock and unlock functions
89 member::lock::is_invocable<Mutex>::value,
90 "The mutex type must support lock and unlock functions");
92 using duration = std::chrono::milliseconds;
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;
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
111 template <class Mutex, MutexLevel level, bool is_timed>
112 struct LockTraitsImpl;
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};
121 * Acquire the lock exclusively.
123 static void lock(Mutex& mutex) {
128 * Release an exclusively-held lock.
130 static void unlock(Mutex& mutex) {
136 * Higher level mutexes have all the capabilities of the lower levels so
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};
147 * Acquire the lock in shared (read) mode.
149 static void lock_shared(Mutex& mutex) {
154 * Release a lock held in shared mode.
156 static void unlock_shared(Mutex& mutex) {
157 mutex.unlock_shared();
162 * The following methods are supported. There are a few methods
167 * m.unlock_upgrade_and_lock()
169 * m.unlock_and_lock_upgrade()
170 * m.unlock_and_lock_shared()
171 * m.unlock_upgrade_and_lock_shared()
173 * m.try_lock_upgrade_for(rel_time)
174 * m.try_unlock_upgrade_and_lock_for(rel_time)
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.
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
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};
196 * Acquire the lock in upgradable mode.
198 static void lock_upgrade(Mutex& mutex) {
199 mutex.lock_upgrade();
203 * Release the lock in upgrade mode
205 static void unlock_upgrade(Mutex& mutex) {
206 mutex.unlock_upgrade();
210 * Upgrade from an upgradable state to an exclusive state
212 static void unlock_upgrade_and_lock(Mutex& mutex) {
213 mutex.unlock_upgrade_and_lock();
217 * Downgrade from an exclusive state to an upgrade state
219 static void unlock_and_lock_upgrade(Mutex& mutex) {
220 mutex.unlock_and_lock_upgrade();
224 * Downgrade from an exclusive state to a shared state
226 static void unlock_and_lock_shared(Mutex& mutex) {
227 mutex.unlock_and_lock_shared();
231 * Downgrade from an upgrade state to a shared state
233 static void unlock_upgrade_and_lock_shared(Mutex& mutex) {
234 mutex.unlock_upgrade_and_lock_shared();
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};
246 * Acquire the lock exclusively, with a timeout.
248 * Returns true or false indicating if the lock was acquired or not.
250 template <class Rep, class Period>
251 static bool try_lock_for(
253 const std::chrono::duration<Rep, Period>& timeout) {
254 return mutex.try_lock_for(timeout);
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
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};
272 * Acquire the lock exclusively, with a timeout.
274 * Returns true or false indicating if the lock was acquired or not.
276 template <class Rep, class Period>
277 static bool try_lock_for(
279 const std::chrono::duration<Rep, Period>& timeout) {
280 return mutex.try_lock_for(timeout);
284 * Acquire the lock in shared (read) mode, with a timeout.
286 * Returns true or false indicating if the lock was acquired or not.
288 template <class Rep, class Period>
289 static bool try_lock_shared_for(
291 const std::chrono::duration<Rep, Period>& timeout) {
292 return mutex.try_lock_shared_for(timeout);
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};
305 * Acquire the lock in upgrade mode with a timeout
307 * Returns true or false indicating whether the lock was acquired or not
309 template <class Rep, class Period>
310 static bool try_lock_upgrade_for(
312 const std::chrono::duration<Rep, Period>& timeout) {
313 return mutex.try_lock_upgrade_for(timeout);
317 * Try to upgrade from an upgradable state to an exclusive state.
319 * Returns true or false indicating whether the lock was acquired or not
321 template <class Rep, class Period>
322 static bool try_unlock_upgrade_and_lock_for(
324 const std::chrono::duration<Rep, Period>& timeout) {
325 return mutex.try_unlock_upgrade_and_lock_for(timeout);
329 } // namespace detail
332 * LockTraits describes details about a particular mutex type.
334 * The default implementation automatically attempts to detect traits
335 * based on the presence of various member functions.
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())
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
350 * The following static methods always exist:
351 * - lock(Mutex& mutex)
352 * - unlock(Mutex& mutex)
354 * The following static methods may exist, depending on is_shared, is_timed
359 * - try_lock_shared_for()
362 * - unlock_upgrade_and_lock()
363 * - unlock_and_lock_upgrade()
364 * - unlock_and_lock_shared()
365 * - unlock_upgrade_and_lock_shared()
367 * - try_lock_upgrade_for()
368 * - try_unlock_upgrade_and_lock_for()
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 :)
379 template <class Mutex>
380 struct LockTraitsBase
381 : public detail::LockTraitsImpl<
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> {};
389 template <class Mutex>
390 struct LockTraits : public LockTraitsBase<Mutex> {};
393 * If the lock is a shared lock, acquire it in shared mode.
394 * Otherwise, for plain (exclusive-only) locks, perform a normal acquire.
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);
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);
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.
412 * Returns true if the lock was acquired, or false on time out.
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(
418 const std::chrono::duration<Rep, Period>& timeout) {
419 return LockTraits<Mutex>::try_lock_shared_for(mutex, timeout);
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(
425 const std::chrono::duration<Rep, Period>& timeout) {
426 return LockTraits<Mutex>::try_lock_for(mutex, timeout);
430 * Release a lock acquired with lock_shared_or_unique()
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);
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);
444 * Lock policy classes.
446 * These can be used as template parameters to provide compile-time
447 * selection over the type of lock operation to perform.
451 * A lock policy that performs exclusive lock operations.
453 struct LockPolicyExclusive {
454 template <class Mutex>
455 static void lock(Mutex& mutex) {
456 LockTraits<Mutex>::lock(mutex);
458 template <class Mutex, class Rep, class Period>
459 static bool try_lock_for(
461 const std::chrono::duration<Rep, Period>& timeout) {
462 return LockTraits<Mutex>::try_lock_for(mutex, timeout);
464 template <class Mutex>
465 static void unlock(Mutex& mutex) {
466 LockTraits<Mutex>::unlock(mutex);
471 * A lock policy that performs shared lock operations.
472 * This policy only works with shared mutex types.
474 struct LockPolicyShared {
475 template <class Mutex>
476 static void lock(Mutex& mutex) {
477 LockTraits<Mutex>::lock_shared(mutex);
479 template <class Mutex, class Rep, class Period>
480 static bool try_lock_for(
482 const std::chrono::duration<Rep, Period>& timeout) {
483 return LockTraits<Mutex>::try_lock_shared_for(mutex, timeout);
485 template <class Mutex>
486 static void unlock(Mutex& mutex) {
487 LockTraits<Mutex>::unlock_shared(mutex);
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.
495 struct LockPolicyShareable {
496 template <class Mutex>
497 static void lock(Mutex& mutex) {
498 lock_shared_or_unique(mutex);
500 template <class Mutex, class Rep, class Period>
501 static bool try_lock_for(
503 const std::chrono::duration<Rep, Period>& timeout) {
504 return try_lock_shared_or_unique_for(mutex, timeout);
506 template <class Mutex>
507 static void unlock(Mutex& mutex) {
508 unlock_shared_or_unique(mutex);
513 * A lock policy with the following mapping
515 * lock() -> lock_upgrade()
516 * unlock() -> unlock_upgrade()
517 * try_lock_for -> try_lock_upgrade_for()
519 struct LockPolicyUpgrade {
520 template <class Mutex>
521 static void lock(Mutex& mutex) {
522 LockTraits<Mutex>::lock_upgrade(mutex);
524 template <class Mutex, class Rep, class Period>
525 static bool try_lock_for(
527 const std::chrono::duration<Rep, Period>& timeout) {
528 return LockTraits<Mutex>::try_lock_upgrade_for(mutex, timeout);
530 template <class Mutex>
531 static void unlock(Mutex& mutex) {
532 LockTraits<Mutex>::unlock_upgrade(mutex);
536 /*****************************************************************************
537 * Policies for all the transitions from possible mutex levels
538 ****************************************************************************/
540 * A lock policy with the following mapping
542 * lock() -> unlock_upgrade_and_lock()
543 * unlock() -> unlock()
544 * try_lock_for -> try_unlock_upgrade_and_lock_for()
546 struct LockPolicyFromUpgradeToExclusive : public LockPolicyExclusive {
547 template <class Mutex>
548 static void lock(Mutex& mutex) {
549 LockTraits<Mutex>::unlock_upgrade_and_lock(mutex);
551 template <class Mutex, class Rep, class Period>
552 static bool try_lock_for(
554 const std::chrono::duration<Rep, Period>& timeout) {
555 return LockTraits<Mutex>::try_unlock_upgrade_and_lock_for(mutex, timeout);
560 * A lock policy with the following mapping
562 * lock() -> unlock_and_lock_upgrade()
563 * unlock() -> unlock_upgrade()
564 * try_lock_for -> unlock_and_lock_upgrade()
566 struct LockPolicyFromExclusiveToUpgrade : public LockPolicyUpgrade {
567 template <class Mutex>
568 static void lock(Mutex& mutex) {
569 LockTraits<Mutex>::unlock_and_lock_upgrade(mutex);
571 template <class Mutex, class Rep, class Period>
572 static bool try_lock_for(
574 const std::chrono::duration<Rep, Period>&) {
575 LockTraits<Mutex>::unlock_and_lock_upgrade(mutex);
577 // downgrade should be non blocking and should succeed
583 * A lock policy with the following mapping
585 * lock() -> unlock_upgrade_and_lock_shared()
586 * unlock() -> unlock_shared()
587 * try_lock_for -> unlock_upgrade_and_lock_shared()
589 struct LockPolicyFromUpgradeToShared : public LockPolicyShared {
590 template <class Mutex>
591 static void lock(Mutex& mutex) {
592 LockTraits<Mutex>::unlock_upgrade_and_lock_shared(mutex);
594 template <class Mutex, class Rep, class Period>
595 static bool try_lock_for(
597 const std::chrono::duration<Rep, Period>&) {
598 LockTraits<Mutex>::unlock_upgrade_and_lock_shared(mutex);
600 // downgrade should be non blocking and should succeed
606 * A lock policy with the following mapping
608 * lock() -> unlock_and_lock_shared()
609 * unlock() -> unlock_shared()
610 * try_lock_for() -> unlock_and_lock_shared()
612 struct LockPolicyFromExclusiveToShared : public LockPolicyShared {
613 template <class Mutex>
614 static void lock(Mutex& mutex) {
615 LockTraits<Mutex>::unlock_and_lock_shared(mutex);
617 template <class Mutex, class Rep, class Period>
618 static bool try_lock_for(
620 const std::chrono::duration<Rep, Period>&) {
621 LockTraits<Mutex>::unlock_and_lock_shared(mutex);
623 // downgrade should be non blocking and should succeed