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
40namespace folly {
41namespace detail {
42
43namespace member {
44FOLLY_CREATE_MEMBER_INVOKE_TRAITS(lock, lock);
45FOLLY_CREATE_MEMBER_INVOKE_TRAITS(try_lock_for, try_lock_for);
46FOLLY_CREATE_MEMBER_INVOKE_TRAITS(lock_shared, lock_shared);
47FOLLY_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 */
57enum 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 */
63template <bool is_unique, bool is_shared, bool is_upgrade>
64struct MutexLevelValueImpl;
65template <>
66struct MutexLevelValueImpl<true, false, false> {
67 static constexpr MutexLevel value = MutexLevel::UNIQUE;
68};
69template <>
70struct MutexLevelValueImpl<true, true, false> {
71 static constexpr MutexLevel value = MutexLevel::SHARED;
72};
73template <>
74struct 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 */
84template <class Mutex>
85class 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 */
111template <class Mutex, MutexLevel level, bool is_timed>
112struct LockTraitsImpl;
113
114template <class Mutex>
115struct 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 * Try to acquire the mutex
136 */
137 static bool try_lock(Mutex& mutex) {
138 return mutex.try_lock();
139 }
140};
141
142/**
143 * Higher level mutexes have all the capabilities of the lower levels so
144 * inherit
145 */
146template <class Mutex>
147struct LockTraitsImpl<Mutex, MutexLevel::SHARED, false>
148 : public LockTraitsImpl<Mutex, MutexLevel::UNIQUE, false> {
149 static constexpr bool is_timed{false};
150 static constexpr bool is_shared{true};
151 static constexpr bool is_upgrade{false};
152
153 /**
154 * Acquire the lock in shared (read) mode.
155 */
156 static void lock_shared(Mutex& mutex) {
157 mutex.lock_shared();
158 }
159
160 /**
161 * Release a lock held in shared mode.
162 */
163 static void unlock_shared(Mutex& mutex) {
164 mutex.unlock_shared();
165 }
166
167 /**
168 * Try to acquire the mutex in shared mode
169 */
170 static bool try_lock_shared(Mutex& mutex) {
171 return mutex.try_lock_shared();
172 }
173};
174
175/**
176 * The following methods are supported. There are a few methods
177 *
178 * m.lock_upgrade()
179 * m.unlock_upgrade()
180 * m.try_lock_upgrade()
181 *
182 * m.unlock_upgrade_and_lock()
183 *
184 * m.unlock_and_lock_upgrade()
185 * m.unlock_and_lock_shared()
186 * m.unlock_upgrade_and_lock_shared()
187 *
188 * m.try_lock_upgrade_for(rel_time)
189 * m.try_unlock_upgrade_and_lock_for(rel_time)
190 *
191 * Upgrading a shared lock is likely to deadlock when there is more than one
192 * thread performing an upgrade. This applies both to upgrading a shared lock
193 * to an upgrade lock and to upgrading a shared lock to a unique lock.
194 *
195 * Therefore, none of the following methods is supported:
196 * unlock_shared_and_lock_upgrade
197 * unlock_shared_and_lock
198 * try_unlock_shared_and_lock_upgrade
199 * try_unlock_shared_and_lock
200 * try_unlock_shared_and_lock_upgrade_for
201 * try_unlock_shared_and_lock_for
202 */
203template <class Mutex>
204struct LockTraitsImpl<Mutex, MutexLevel::UPGRADE, false>
205 : public LockTraitsImpl<Mutex, MutexLevel::SHARED, false> {
206 static constexpr bool is_timed{false};
207 static constexpr bool is_shared{true};
208 static constexpr bool is_upgrade{true};
209
210 /**
211 * Acquire the lock in upgradable mode.
212 */
213 static void lock_upgrade(Mutex& mutex) {
214 mutex.lock_upgrade();
215 }
216
217 /**
218 * Release the lock in upgrade mode
219 */
220 static void unlock_upgrade(Mutex& mutex) {
221 mutex.unlock_upgrade();
222 }
223
224 /**
225 * Try and acquire the lock in upgrade mode
226 */
227 static bool try_lock_upgrade(Mutex& mutex) {
228 return mutex.try_lock_upgrade();
229 }
230
231 /**
232 * Upgrade from an upgradable state to an exclusive state
233 */
234 static void unlock_upgrade_and_lock(Mutex& mutex) {
235 mutex.unlock_upgrade_and_lock();
236 }
237
238 /**
239 * Downgrade from an exclusive state to an upgrade state
240 */
241 static void unlock_and_lock_upgrade(Mutex& mutex) {
242 mutex.unlock_and_lock_upgrade();
243 }
244
245 /**
246 * Downgrade from an exclusive state to a shared state
247 */
248 static void unlock_and_lock_shared(Mutex& mutex) {
249 mutex.unlock_and_lock_shared();
250 }
251
252 /**
253 * Downgrade from an upgrade state to a shared state
254 */
255 static void unlock_upgrade_and_lock_shared(Mutex& mutex) {
256 mutex.unlock_upgrade_and_lock_shared();
257 }
258};
259
260template <class Mutex>
261struct LockTraitsImpl<Mutex, MutexLevel::UNIQUE, true>
262 : public LockTraitsImpl<Mutex, MutexLevel::UNIQUE, false> {
263 static constexpr bool is_timed{true};
264 static constexpr bool is_shared{false};
265 static constexpr bool is_upgrade{false};
266
267 /**
268 * Acquire the lock exclusively, with a timeout.
269 *
270 * Returns true or false indicating if the lock was acquired or not.
271 */
272 template <class Rep, class Period>
273 static bool try_lock_for(
274 Mutex& mutex,
275 const std::chrono::duration<Rep, Period>& timeout) {
276 return mutex.try_lock_for(timeout);
277 }
278};
279
280/**
281 * Note that there is no deadly diamond here because all the structs only have
282 * static functions and static bools which are going to be overridden by the
283 * lowest level implementation
284 */
285template <class Mutex>
286struct LockTraitsImpl<Mutex, MutexLevel::SHARED, true>
287 : public LockTraitsImpl<Mutex, MutexLevel::SHARED, false>,
288 public LockTraitsImpl<Mutex, MutexLevel::UNIQUE, true> {
289 static constexpr bool is_timed{true};
290 static constexpr bool is_shared{true};
291 static constexpr bool is_upgrade{false};
292
293 /**
294 * Acquire the lock exclusively, with a timeout.
295 *
296 * Returns true or false indicating if the lock was acquired or not.
297 */
298 template <class Rep, class Period>
299 static bool try_lock_for(
300 Mutex& mutex,
301 const std::chrono::duration<Rep, Period>& timeout) {
302 return mutex.try_lock_for(timeout);
303 }
304
305 /**
306 * Acquire the lock in shared (read) mode, with a timeout.
307 *
308 * Returns true or false indicating if the lock was acquired or not.
309 */
310 template <class Rep, class Period>
311 static bool try_lock_shared_for(
312 Mutex& mutex,
313 const std::chrono::duration<Rep, Period>& timeout) {
314 return mutex.try_lock_shared_for(timeout);
315 }
316};
317
318template <class Mutex>
319struct LockTraitsImpl<Mutex, MutexLevel::UPGRADE, true>
320 : public LockTraitsImpl<Mutex, MutexLevel::UPGRADE, false>,
321 public LockTraitsImpl<Mutex, MutexLevel::SHARED, true> {
322 static constexpr bool is_timed{true};
323 static constexpr bool is_shared{true};
324 static constexpr bool is_upgrade{true};
325
326 /**
327 * Acquire the lock in upgrade mode with a timeout
328 *
329 * Returns true or false indicating whether the lock was acquired or not
330 */
331 template <class Rep, class Period>
332 static bool try_lock_upgrade_for(
333 Mutex& mutex,
334 const std::chrono::duration<Rep, Period>& timeout) {
335 return mutex.try_lock_upgrade_for(timeout);
336 }
337
338 /**
339 * Try to upgrade from an upgradable state to an exclusive state.
340 *
341 * Returns true or false indicating whether the lock was acquired or not
342 */
343 template <class Rep, class Period>
344 static bool try_unlock_upgrade_and_lock_for(
345 Mutex& mutex,
346 const std::chrono::duration<Rep, Period>& timeout) {
347 return mutex.try_unlock_upgrade_and_lock_for(timeout);
348 }
349};
350
351/**
352 * Unlock helpers
353 *
354 * These help in determining whether it is safe for Synchronized::LockedPtr
355 * instances to be move assigned from one another. It is safe if they both
356 * have the same unlock policy, and it is not if they don't have the same
357 * unlock policy. For example
358 *
359 * auto wlock = synchronized.wlock();
360 * wlock.unlock();
361 *
362 * wlock = synchronized.rlock();
363 *
364 * This code would try to release the shared lock with a call to unlock(),
365 * resulting in possibly undefined behavior. By allowing the LockPolicy
366 * classes (defined below) to know what their unlocking behavior is, we can
367 * prevent against this by disabling unsafe conversions to and from
368 * incompatible LockedPtr types (they are incompatible if the underlying
369 * LockPolicy has different unlock policies.
370 */
371template <template <typename...> class LockTraits>
372struct UnlockPolicyExclusive {
373 template <typename Mutex>
374 static void unlock(Mutex& mutex) {
375 LockTraits<Mutex>::unlock(mutex);
376 }
377};
378template <template <typename...> class LockTraits>
379struct UnlockPolicyShared {
380 template <typename Mutex>
381 static void unlock(Mutex& mutex) {
382 LockTraits<Mutex>::unlock_shared(mutex);
383 }
384};
385template <template <typename...> class LockTraits>
386struct UnlockPolicyUpgrade {
387 template <typename Mutex>
388 static void unlock(Mutex& mutex) {
389 LockTraits<Mutex>::unlock_upgrade(mutex);
390 }
391};
392
393} // namespace detail
394
395/**
396 * LockTraits describes details about a particular mutex type.
397 *
398 * The default implementation automatically attempts to detect traits
399 * based on the presence of various member functions.
400 *
401 * You can specialize LockTraits to provide custom behavior for lock
402 * classes that do not use the standard method names
403 * (lock()/unlock()/lock_shared()/unlock_shared()/try_lock_for())
404 *
405 *
406 * LockTraits contains the following members variables:
407 * - static constexpr bool is_shared
408 * True if the lock supports separate shared vs exclusive locking states.
409 * - static constexpr bool is_timed
410 * True if the lock supports acquiring the lock with a timeout.
411 * - static constexpr bool is_upgrade
412 * True if the lock supports an upgradable state
413 *
414 * The following static methods always exist:
415 * - lock(Mutex& mutex)
416 * - unlock(Mutex& mutex)
417 * - try_lock(Mutex& mutex)
418 *
419 * The following static methods may exist, depending on is_shared, is_timed
420 * and is_upgrade:
421 * - lock_shared()
422 * - try_lock_shared()
423 *
424 * - try_lock_for()
425 * - try_lock_shared_for()
426 *
427 * - lock_upgrade()
428 * - try_lock_upgrade()
429 * - unlock_upgrade_and_lock()
430 * - unlock_and_lock_upgrade()
431 * - unlock_and_lock_shared()
432 * - unlock_upgrade_and_lock_shared()
433 *
434 * - try_lock_upgrade_for()
435 * - try_unlock_upgrade_and_lock_for()
436 *
437 * - unlock_shared()
438 * - unlock_upgrade()
439 */
440
441/**
442 * Decoupling LockTraits and LockTraitsBase so that if people want to fully
443 * specialize LockTraits then they can inherit from LockTraitsBase instead
444 * of LockTraits with all the same goodies :)
445 */
446template <class Mutex>
447struct LockTraitsBase
448 : public detail::LockTraitsImpl<
449 Mutex,
450 detail::MutexLevelValueImpl<
451 detail::LockInterfaceDispatcher<Mutex>::has_lock_unique,
452 detail::LockInterfaceDispatcher<Mutex>::has_lock_shared,
453 detail::LockInterfaceDispatcher<Mutex>::has_lock_upgrade>::value,
454 detail::LockInterfaceDispatcher<Mutex>::has_lock_timed> {};
455
456template <class Mutex>
457struct LockTraits : public LockTraitsBase<Mutex> {};
458
459/*
460 * Lock policy classes.
461 *
462 * These can be used as template parameters to provide compile-time
463 * selection over the type of lock operation to perform.
464 */
465/**
466 * A lock policy that performs exclusive lock operations.
467 */
468struct LockPolicyExclusive : detail::UnlockPolicyExclusive<LockTraits> {
469 using UnlockPolicy = detail::UnlockPolicyExclusive<LockTraits>;
470
471 template <class Mutex>
472 static std::true_type lock(Mutex& mutex) {
473 LockTraits<Mutex>::lock(mutex);
474 return std::true_type{};
475 }
476 template <class Mutex, class Rep, class Period>
477 static bool try_lock_for(
478 Mutex& mutex,
479 const std::chrono::duration<Rep, Period>& timeout) {
480 return LockTraits<Mutex>::try_lock_for(mutex, timeout);
481 }
482};
483
484/**
485 * A lock policy that performs shared lock operations.
486 * This policy only works with shared mutex types.
487 */
488struct LockPolicyShared : detail::UnlockPolicyShared<LockTraits> {
489 using UnlockPolicy = detail::UnlockPolicyShared<LockTraits>;
490
491 template <class Mutex>
492 static std::true_type lock(Mutex& mutex) {
493 LockTraits<Mutex>::lock_shared(mutex);
494 return std::true_type{};
495 }
496 template <class Mutex, class Rep, class Period>
497 static bool try_lock_for(
498 Mutex& mutex,
499 const std::chrono::duration<Rep, Period>& timeout) {
500 return LockTraits<Mutex>::try_lock_shared_for(mutex, timeout);
501 }
502};
503
504/**
505 * A lock policy with the following mapping
506 *
507 * lock() -> lock_upgrade()
508 * unlock() -> unlock_upgrade()
509 * try_lock_for -> try_lock_upgrade_for()
510 */
511struct LockPolicyUpgrade : detail::UnlockPolicyUpgrade<LockTraits> {
512 using UnlockPolicy = detail::UnlockPolicyUpgrade<LockTraits>;
513
514 template <class Mutex>
515 static std::true_type lock(Mutex& mutex) {
516 LockTraits<Mutex>::lock_upgrade(mutex);
517 return std::true_type{};
518 }
519 template <class Mutex, class Rep, class Period>
520 static bool try_lock_for(
521 Mutex& mutex,
522 const std::chrono::duration<Rep, Period>& timeout) {
523 return LockTraits<Mutex>::try_lock_upgrade_for(mutex, timeout);
524 }
525};
526
527/*****************************************************************************
528 * Policies for optional mutex locking
529 ****************************************************************************/
530/**
531 * A lock policy that tries to acquire write locks and returns true or false
532 * based on whether the lock operation succeeds
533 */
534struct LockPolicyTryExclusive : detail::UnlockPolicyExclusive<LockTraits> {
535 using UnlockPolicy = detail::UnlockPolicyExclusive<LockTraits>;
536
537 template <class Mutex>
538 static bool lock(Mutex& mutex) {
539 return LockTraits<Mutex>::try_lock(mutex);
540 }
541};
542
543/**
544 * A lock policy that tries to acquire a read lock and returns true or false
545 * based on whether the lock operation succeeds
546 */
547struct LockPolicyTryShared : detail::UnlockPolicyShared<LockTraits> {
548 using UnlockPolicy = detail::UnlockPolicyShared<LockTraits>;
549
550 template <class Mutex>
551 static bool lock(Mutex& mutex) {
552 return LockTraits<Mutex>::try_lock_shared(mutex);
553 }
554};
555
556/**
557 * A lock policy that tries to acquire an upgrade lock and returns true or
558 * false based on whether the lock operation succeeds
559 */
560struct LockPolicyTryUpgrade : detail::UnlockPolicyUpgrade<LockTraits> {
561 using UnlockPolicy = detail::UnlockPolicyUpgrade<LockTraits>;
562
563 template <class Mutex>
564 static bool lock(Mutex& mutex) {
565 return LockTraits<Mutex>::try_lock_upgrade(mutex);
566 }
567};
568
569/*****************************************************************************
570 * Policies for all the transitions from possible mutex levels
571 ****************************************************************************/
572/**
573 * A lock policy with the following mapping
574 *
575 * lock() -> unlock_upgrade_and_lock()
576 * unlock() -> unlock()
577 * try_lock_for -> try_unlock_upgrade_and_lock_for()
578 */
579struct LockPolicyFromUpgradeToExclusive : LockPolicyExclusive {
580 template <class Mutex>
581 static std::true_type lock(Mutex& mutex) {
582 LockTraits<Mutex>::unlock_upgrade_and_lock(mutex);
583 return std::true_type{};
584 }
585 template <class Mutex, class Rep, class Period>
586 static bool try_lock_for(
587 Mutex& mutex,
588 const std::chrono::duration<Rep, Period>& timeout) {
589 return LockTraits<Mutex>::try_unlock_upgrade_and_lock_for(mutex, timeout);
590 }
591};
592
593/**
594 * A lock policy with the following mapping
595 *
596 * lock() -> unlock_and_lock_upgrade()
597 * unlock() -> unlock_upgrade()
598 * try_lock_for -> unlock_and_lock_upgrade()
599 */
600struct LockPolicyFromExclusiveToUpgrade : LockPolicyUpgrade {
601 template <class Mutex>
602 static std::true_type lock(Mutex& mutex) {
603 LockTraits<Mutex>::unlock_and_lock_upgrade(mutex);
604 return std::true_type{};
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_and_lock_upgrade(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_upgrade_and_lock_shared()
621 * unlock() -> unlock_shared()
622 * try_lock_for -> unlock_upgrade_and_lock_shared()
623 */
624struct LockPolicyFromUpgradeToShared : LockPolicyShared {
625 template <class Mutex>
626 static std::true_type lock(Mutex& mutex) {
627 LockTraits<Mutex>::unlock_upgrade_and_lock_shared(mutex);
628 return std::true_type{};
629 }
630 template <class Mutex, class Rep, class Period>
631 static bool try_lock_for(
632 Mutex& mutex,
633 const std::chrono::duration<Rep, Period>&) {
634 LockTraits<Mutex>::unlock_upgrade_and_lock_shared(mutex);
635
636 // downgrade should be non blocking and should succeed
637 return true;
638 }
639};
640
641/**
642 * A lock policy with the following mapping
643 *
644 * lock() -> unlock_and_lock_shared()
645 * unlock() -> unlock_shared()
646 * try_lock_for() -> unlock_and_lock_shared()
647 */
648struct LockPolicyFromExclusiveToShared : LockPolicyShared {
649 template <class Mutex>
650 static std::true_type lock(Mutex& mutex) {
651 LockTraits<Mutex>::unlock_and_lock_shared(mutex);
652 return std::true_type{};
653 }
654 template <class Mutex, class Rep, class Period>
655 static bool try_lock_for(
656 Mutex& mutex,
657 const std::chrono::duration<Rep, Period>&) {
658 LockTraits<Mutex>::unlock_and_lock_shared(mutex);
659
660 // downgrade should be non blocking and should succeed
661 return true;
662 }
663};
664
665} // namespace folly
666