1/*
2 * Copyright (c) Facebook, Inc. and its affiliates.
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_INVOKER(lock_invoker, lock);
45FOLLY_CREATE_MEMBER_INVOKER(try_lock_for_invoker, try_lock_for);
46FOLLY_CREATE_MEMBER_INVOKER(lock_shared_invoker, lock_shared);
47FOLLY_CREATE_MEMBER_INVOKER(lock_upgrade_invoker, 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 folly::is_invocable<member::lock_invoker, 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 folly::is_invocable<member::try_lock_for_invoker, Mutex, duration>::value;
98 static constexpr bool has_lock_shared =
99 folly::is_invocable<member::lock_shared_invoker, Mutex>::value;
100 static constexpr bool has_lock_upgrade =
101 folly::is_invocable<member::lock_upgrade_invoker, 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 constexpr static bool allows_concurrent_access = false;
374
375 template <typename Mutex>
376 static void unlock(Mutex& mutex) {
377 LockTraits<Mutex>::unlock(mutex);
378 }
379};
380template <template <typename...> class LockTraits>
381struct UnlockPolicyShared {
382 constexpr static bool allows_concurrent_access = true;
383
384 template <typename Mutex>
385 static void unlock(Mutex& mutex) {
386 LockTraits<Mutex>::unlock_shared(mutex);
387 }
388};
389template <template <typename...> class LockTraits>
390struct UnlockPolicyUpgrade {
391 constexpr static bool allows_concurrent_access = true;
392
393 template <typename Mutex>
394 static void unlock(Mutex& mutex) {
395 LockTraits<Mutex>::unlock_upgrade(mutex);
396 }
397};
398
399} // namespace detail
400
401/**
402 * LockTraits describes details about a particular mutex type.
403 *
404 * The default implementation automatically attempts to detect traits
405 * based on the presence of various member functions.
406 *
407 * You can specialize LockTraits to provide custom behavior for lock
408 * classes that do not use the standard method names
409 * (lock()/unlock()/lock_shared()/unlock_shared()/try_lock_for())
410 *
411 *
412 * LockTraits contains the following members variables:
413 * - static constexpr bool is_shared
414 * True if the lock supports separate shared vs exclusive locking states.
415 * - static constexpr bool is_timed
416 * True if the lock supports acquiring the lock with a timeout.
417 * - static constexpr bool is_upgrade
418 * True if the lock supports an upgradable state
419 *
420 * The following static methods always exist:
421 * - lock(Mutex& mutex)
422 * - unlock(Mutex& mutex)
423 * - try_lock(Mutex& mutex)
424 *
425 * The following static methods may exist, depending on is_shared, is_timed
426 * and is_upgrade:
427 * - lock_shared()
428 * - try_lock_shared()
429 *
430 * - try_lock_for()
431 * - try_lock_shared_for()
432 *
433 * - lock_upgrade()
434 * - try_lock_upgrade()
435 * - unlock_upgrade_and_lock()
436 * - unlock_and_lock_upgrade()
437 * - unlock_and_lock_shared()
438 * - unlock_upgrade_and_lock_shared()
439 *
440 * - try_lock_upgrade_for()
441 * - try_unlock_upgrade_and_lock_for()
442 *
443 * - unlock_shared()
444 * - unlock_upgrade()
445 */
446
447/**
448 * Decoupling LockTraits and LockTraitsBase so that if people want to fully
449 * specialize LockTraits then they can inherit from LockTraitsBase instead
450 * of LockTraits with all the same goodies :)
451 */
452template <class Mutex>
453struct LockTraitsBase
454 : public detail::LockTraitsImpl<
455 Mutex,
456 detail::MutexLevelValueImpl<
457 detail::LockInterfaceDispatcher<Mutex>::has_lock_unique,
458 detail::LockInterfaceDispatcher<Mutex>::has_lock_shared,
459 detail::LockInterfaceDispatcher<Mutex>::has_lock_upgrade>::value,
460 detail::LockInterfaceDispatcher<Mutex>::has_lock_timed> {};
461
462template <class Mutex>
463struct LockTraits : public LockTraitsBase<Mutex> {};
464
465/*
466 * Lock policy classes.
467 *
468 * These can be used as template parameters to provide compile-time
469 * selection over the type of lock operation to perform.
470 */
471/**
472 * A lock policy that performs exclusive lock operations.
473 */
474struct LockPolicyExclusive : detail::UnlockPolicyExclusive<LockTraits> {
475 using UnlockPolicy = detail::UnlockPolicyExclusive<LockTraits>;
476
477 template <class Mutex>
478 static std::true_type lock(Mutex& mutex) {
479 LockTraits<Mutex>::lock(mutex);
480 return std::true_type{};
481 }
482 template <class Mutex, class Rep, class Period>
483 static bool try_lock_for(
484 Mutex& mutex,
485 const std::chrono::duration<Rep, Period>& timeout) {
486 return LockTraits<Mutex>::try_lock_for(mutex, timeout);
487 }
488};
489
490/**
491 * A lock policy that performs shared lock operations.
492 * This policy only works with shared mutex types.
493 */
494struct LockPolicyShared : detail::UnlockPolicyShared<LockTraits> {
495 using UnlockPolicy = detail::UnlockPolicyShared<LockTraits>;
496
497 template <class Mutex>
498 static std::true_type lock(Mutex& mutex) {
499 LockTraits<Mutex>::lock_shared(mutex);
500 return std::true_type{};
501 }
502 template <class Mutex, class Rep, class Period>
503 static bool try_lock_for(
504 Mutex& mutex,
505 const std::chrono::duration<Rep, Period>& timeout) {
506 return LockTraits<Mutex>::try_lock_shared_for(mutex, timeout);
507 }
508};
509
510/**
511 * A lock policy with the following mapping
512 *
513 * lock() -> lock_upgrade()
514 * unlock() -> unlock_upgrade()
515 * try_lock_for -> try_lock_upgrade_for()
516 */
517struct LockPolicyUpgrade : detail::UnlockPolicyUpgrade<LockTraits> {
518 using UnlockPolicy = detail::UnlockPolicyUpgrade<LockTraits>;
519
520 template <class Mutex>
521 static std::true_type lock(Mutex& mutex) {
522 LockTraits<Mutex>::lock_upgrade(mutex);
523 return std::true_type{};
524 }
525 template <class Mutex, class Rep, class Period>
526 static bool try_lock_for(
527 Mutex& mutex,
528 const std::chrono::duration<Rep, Period>& timeout) {
529 return LockTraits<Mutex>::try_lock_upgrade_for(mutex, timeout);
530 }
531};
532
533/*****************************************************************************
534 * Policies for optional mutex locking
535 ****************************************************************************/
536/**
537 * A lock policy that tries to acquire write locks and returns true or false
538 * based on whether the lock operation succeeds
539 */
540struct LockPolicyTryExclusive : detail::UnlockPolicyExclusive<LockTraits> {
541 using UnlockPolicy = detail::UnlockPolicyExclusive<LockTraits>;
542
543 template <class Mutex>
544 static bool lock(Mutex& mutex) {
545 return LockTraits<Mutex>::try_lock(mutex);
546 }
547};
548
549/**
550 * A lock policy that tries to acquire a read lock and returns true or false
551 * based on whether the lock operation succeeds
552 */
553struct LockPolicyTryShared : detail::UnlockPolicyShared<LockTraits> {
554 using UnlockPolicy = detail::UnlockPolicyShared<LockTraits>;
555
556 template <class Mutex>
557 static bool lock(Mutex& mutex) {
558 return LockTraits<Mutex>::try_lock_shared(mutex);
559 }
560};
561
562/**
563 * A lock policy that tries to acquire an upgrade lock and returns true or
564 * false based on whether the lock operation succeeds
565 */
566struct LockPolicyTryUpgrade : detail::UnlockPolicyUpgrade<LockTraits> {
567 using UnlockPolicy = detail::UnlockPolicyUpgrade<LockTraits>;
568
569 template <class Mutex>
570 static bool lock(Mutex& mutex) {
571 return LockTraits<Mutex>::try_lock_upgrade(mutex);
572 }
573};
574
575/*****************************************************************************
576 * Policies for all the transitions from possible mutex levels
577 ****************************************************************************/
578/**
579 * A lock policy with the following mapping
580 *
581 * lock() -> unlock_upgrade_and_lock()
582 * unlock() -> unlock()
583 * try_lock_for -> try_unlock_upgrade_and_lock_for()
584 */
585struct LockPolicyFromUpgradeToExclusive : LockPolicyExclusive {
586 template <class Mutex>
587 static std::true_type lock(Mutex& mutex) {
588 LockTraits<Mutex>::unlock_upgrade_and_lock(mutex);
589 return std::true_type{};
590 }
591 template <class Mutex, class Rep, class Period>
592 static bool try_lock_for(
593 Mutex& mutex,
594 const std::chrono::duration<Rep, Period>& timeout) {
595 return LockTraits<Mutex>::try_unlock_upgrade_and_lock_for(mutex, timeout);
596 }
597};
598
599/**
600 * A lock policy with the following mapping
601 *
602 * lock() -> unlock_and_lock_upgrade()
603 * unlock() -> unlock_upgrade()
604 * try_lock_for -> unlock_and_lock_upgrade()
605 */
606struct LockPolicyFromExclusiveToUpgrade : LockPolicyUpgrade {
607 template <class Mutex>
608 static std::true_type lock(Mutex& mutex) {
609 LockTraits<Mutex>::unlock_and_lock_upgrade(mutex);
610 return std::true_type{};
611 }
612 template <class Mutex, class Rep, class Period>
613 static bool try_lock_for(
614 Mutex& mutex,
615 const std::chrono::duration<Rep, Period>&) {
616 LockTraits<Mutex>::unlock_and_lock_upgrade(mutex);
617
618 // downgrade should be non blocking and should succeed
619 return true;
620 }
621};
622
623/**
624 * A lock policy with the following mapping
625 *
626 * lock() -> unlock_upgrade_and_lock_shared()
627 * unlock() -> unlock_shared()
628 * try_lock_for -> unlock_upgrade_and_lock_shared()
629 */
630struct LockPolicyFromUpgradeToShared : LockPolicyShared {
631 template <class Mutex>
632 static std::true_type lock(Mutex& mutex) {
633 LockTraits<Mutex>::unlock_upgrade_and_lock_shared(mutex);
634 return std::true_type{};
635 }
636 template <class Mutex, class Rep, class Period>
637 static bool try_lock_for(
638 Mutex& mutex,
639 const std::chrono::duration<Rep, Period>&) {
640 LockTraits<Mutex>::unlock_upgrade_and_lock_shared(mutex);
641
642 // downgrade should be non blocking and should succeed
643 return true;
644 }
645};
646
647/**
648 * A lock policy with the following mapping
649 *
650 * lock() -> unlock_and_lock_shared()
651 * unlock() -> unlock_shared()
652 * try_lock_for() -> unlock_and_lock_shared()
653 */
654struct LockPolicyFromExclusiveToShared : LockPolicyShared {
655 template <class Mutex>
656 static std::true_type lock(Mutex& mutex) {
657 LockTraits<Mutex>::unlock_and_lock_shared(mutex);
658 return std::true_type{};
659 }
660 template <class Mutex, class Rep, class Period>
661 static bool try_lock_for(
662 Mutex& mutex,
663 const std::chrono::duration<Rep, Period>&) {
664 LockTraits<Mutex>::unlock_and_lock_shared(mutex);
665
666 // downgrade should be non blocking and should succeed
667 return true;
668 }
669};
670
671} // namespace folly
672