1 // Copyright 2018 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 //
6 // Common definitions for the lockdep library.
7 //
8
9 #pragma once
10
11 #include <stddef.h>
12 #include <stdint.h>
13 #include <type_traits>
14
15 #include <lockdep/runtime_api.h>
16
17 namespace lockdep {
18
19 // Configures the maximum number of dependencies each lock class may have. A
20 // system may override the default by globally defining this name to the desired
21 // value. This value is automatically converted to the next suitable prime.
22 #ifndef LOCK_DEP_MAX_DEPENDENCIES
23 #define LOCK_DEP_MAX_DEPENDENCIES 31
24 #endif
25
26 // Configures whether lock validation is enabled or not. Defaults to disabled.
27 // When disabled the locking utilities simply lock the underlying lock types,
28 // without performing any validation operations.
29 #ifndef LOCK_DEP_ENABLE_VALIDATION
30 #define LOCK_DEP_ENABLE_VALIDATION 0
31 #endif
32
33 // Id type used to identify each lock class.
34 using LockClassId = uintptr_t;
35
36 // A sentinel value indicating an empty slot in lock tracking data structures.
37 constexpr LockClassId kInvalidLockClassId = 0;
38
39 namespace internal {
40
41 // Returns a prime number that reasonably accommodates a hash table of the given
42 // number of entries. Each number is selected to be slightly less than twice the
43 // previous and as far as possible from the nearest two powers of two.
NextPrime(size_t n)44 constexpr size_t NextPrime(size_t n) {
45 if (n < (1 << 4))
46 return 23;
47 else if (n < (1 << 5))
48 return 53;
49 else if (n < (1 << 6))
50 return 97;
51 else if (n < (1 << 7))
52 return 193;
53 else if (n < (1 << 8))
54 return 389;
55 else if (n < (1 << 9))
56 return 769;
57 else if (n < (1 << 10))
58 return 1543;
59 else
60 return 0; // The input exceeds the size of this prime table.
61 }
62
63 } // namespace internal
64
65 // The maximum number of dependencies each lock class may have. This is the
66 // maximum branching factor of the directed graph of locks managed by this
67 // lock dependency algorithm. The value is a prime number selected to optimize
68 // the hash map in LockDependencySet.
69 constexpr size_t kMaxLockDependencies = internal::NextPrime(LOCK_DEP_MAX_DEPENDENCIES);
70
71 // Check to make sure that the requested max does not exceed the prime table.
72 static_assert(kMaxLockDependencies != 0, "LOCK_DEP_MAX_DEPENDENCIES too large!");
73
74 // Whether or not lock validation is globally enabled.
75 constexpr bool kLockValidationEnabled = static_cast<bool>(LOCK_DEP_ENABLE_VALIDATION);
76
77 // Utility template alias to simplify selecting different types based whether
78 // lock validation is enabled or disabled.
79 template <typename EnabledType, typename DisabledType>
80 using IfLockValidationEnabled = typename std::conditional<kLockValidationEnabled,
81 EnabledType,
82 DisabledType>::type;
83
84 // Result type that represents whether a lock attempt was successful, or if not
85 // which check failed.
86 enum class LockResult : uint8_t {
87 Success,
88 AlreadyAcquired,
89 OutOfOrder,
90 InvalidNesting,
91 InvalidIrqSafety,
92
93 // Non-fatal error that indicates the dependency hash set for a particular
94 // lock class is full. Consider increasing the size of the lock dependency
95 // sets if this error is reported.
96 MaxLockDependencies,
97
98 // Internal error value used to differentiate between dependency set updates
99 // that add a new edge and those that do not. Only new edges trigger loop
100 // detection.
101 DependencyExists,
102 };
103
104 // Returns a string representation of the given LockResult.
ToString(LockResult result)105 static inline const char* ToString(LockResult result) {
106 switch (result) {
107 case LockResult::Success:
108 return "Success";
109 case LockResult::AlreadyAcquired:
110 return "Already Acquired";
111 case LockResult::OutOfOrder:
112 return "Out Of Order";
113 case LockResult::InvalidNesting:
114 return "Invalid Nesting";
115 case LockResult::InvalidIrqSafety:
116 return "Invalid Irq Safety";
117 case LockResult::MaxLockDependencies:
118 return "Max Lock Dependencies";
119 case LockResult::DependencyExists:
120 return "Dependency Exists";
121 default:
122 return "Unknown";
123 }
124 }
125
126 } // namespace lockdep
127