Commit | Line | Data |
---|---|---|
fbb9ce95 IM |
1 | /* |
2 | * kernel/lockdep_internals.h | |
3 | * | |
4 | * Runtime locking correctness validator | |
5 | * | |
6 | * lockdep subsystem internal functions and variables. | |
7 | */ | |
8 | ||
9851673b PZ |
9 | /* |
10 | * Lock-class usage-state bits: | |
11 | */ | |
12 | enum lock_usage_bit { | |
d7b1b021 PZ |
13 | #define LOCKDEP_STATE(__STATE) \ |
14 | LOCK_USED_IN_##__STATE, \ | |
15 | LOCK_USED_IN_##__STATE##_READ, \ | |
16 | LOCK_ENABLED_##__STATE, \ | |
17 | LOCK_ENABLED_##__STATE##_READ, | |
18 | #include "lockdep_states.h" | |
19 | #undef LOCKDEP_STATE | |
20 | LOCK_USED, | |
9851673b PZ |
21 | LOCK_USAGE_STATES |
22 | }; | |
23 | ||
24 | /* | |
25 | * Usage-state bitmasks: | |
26 | */ | |
d7b1b021 PZ |
27 | #define __LOCKF(__STATE) LOCKF_##__STATE = (1 << LOCK_##__STATE), |
28 | ||
29 | enum { | |
30 | #define LOCKDEP_STATE(__STATE) \ | |
31 | __LOCKF(USED_IN_##__STATE) \ | |
32 | __LOCKF(USED_IN_##__STATE##_READ) \ | |
33 | __LOCKF(ENABLED_##__STATE) \ | |
34 | __LOCKF(ENABLED_##__STATE##_READ) | |
35 | #include "lockdep_states.h" | |
36 | #undef LOCKDEP_STATE | |
37 | __LOCKF(USED) | |
38 | }; | |
9851673b PZ |
39 | |
40 | #define LOCKF_ENABLED_IRQ (LOCKF_ENABLED_HARDIRQ | LOCKF_ENABLED_SOFTIRQ) | |
41 | #define LOCKF_USED_IN_IRQ (LOCKF_USED_IN_HARDIRQ | LOCKF_USED_IN_SOFTIRQ) | |
42 | ||
9851673b PZ |
43 | #define LOCKF_ENABLED_IRQ_READ \ |
44 | (LOCKF_ENABLED_HARDIRQ_READ | LOCKF_ENABLED_SOFTIRQ_READ) | |
45 | #define LOCKF_USED_IN_IRQ_READ \ | |
46 | (LOCKF_USED_IN_HARDIRQ_READ | LOCKF_USED_IN_SOFTIRQ_READ) | |
47 | ||
fbb9ce95 IM |
48 | /* |
49 | * MAX_LOCKDEP_ENTRIES is the maximum number of lock dependencies | |
50 | * we track. | |
51 | * | |
52 | * We use the per-lock dependency maps in two ways: we grow it by adding | |
53 | * every to-be-taken lock to all currently held lock's own dependency | |
54 | * table (if it's not there yet), and we check it for lock order | |
55 | * conflicts and deadlocks. | |
56 | */ | |
d80c19df | 57 | #define MAX_LOCKDEP_ENTRIES 16384UL |
fbb9ce95 | 58 | |
d80c19df | 59 | #define MAX_LOCKDEP_CHAINS_BITS 15 |
fbb9ce95 IM |
60 | #define MAX_LOCKDEP_CHAINS (1UL << MAX_LOCKDEP_CHAINS_BITS) |
61 | ||
443cd507 HY |
62 | #define MAX_LOCKDEP_CHAIN_HLOCKS (MAX_LOCKDEP_CHAINS*5) |
63 | ||
fbb9ce95 IM |
64 | /* |
65 | * Stack-trace: tightly packed array of stack backtrace | |
66 | * addresses. Protected by the hash_lock. | |
67 | */ | |
9bb25bf3 | 68 | #define MAX_STACK_TRACE_ENTRIES 262144UL |
fbb9ce95 IM |
69 | |
70 | extern struct list_head all_lock_classes; | |
443cd507 | 71 | extern struct lock_chain lock_chains[]; |
fbb9ce95 | 72 | |
f510b233 PZ |
73 | #define LOCK_USAGE_CHARS (1+LOCK_USAGE_STATES/2) |
74 | ||
75 | extern void get_usage_chars(struct lock_class *class, | |
76 | char usage[LOCK_USAGE_CHARS]); | |
fbb9ce95 IM |
77 | |
78 | extern const char * __get_key_name(struct lockdep_subclass_key *key, char *str); | |
79 | ||
443cd507 HY |
80 | struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i); |
81 | ||
fbb9ce95 IM |
82 | extern unsigned long nr_lock_classes; |
83 | extern unsigned long nr_list_entries; | |
84 | extern unsigned long nr_lock_chains; | |
cd1a28e8 | 85 | extern int nr_chain_hlocks; |
fbb9ce95 IM |
86 | extern unsigned long nr_stack_trace_entries; |
87 | ||
88 | extern unsigned int nr_hardirq_chains; | |
89 | extern unsigned int nr_softirq_chains; | |
90 | extern unsigned int nr_process_chains; | |
91 | extern unsigned int max_lockdep_depth; | |
92 | extern unsigned int max_recursion_depth; | |
93 | ||
d6672c50 | 94 | #ifdef CONFIG_PROVE_LOCKING |
419ca3f1 DM |
95 | extern unsigned long lockdep_count_forward_deps(struct lock_class *); |
96 | extern unsigned long lockdep_count_backward_deps(struct lock_class *); | |
d6672c50 IM |
97 | #else |
98 | static inline unsigned long | |
99 | lockdep_count_forward_deps(struct lock_class *class) | |
100 | { | |
101 | return 0; | |
102 | } | |
103 | static inline unsigned long | |
104 | lockdep_count_backward_deps(struct lock_class *class) | |
105 | { | |
106 | return 0; | |
107 | } | |
108 | #endif | |
419ca3f1 | 109 | |
fbb9ce95 IM |
110 | #ifdef CONFIG_DEBUG_LOCKDEP |
111 | /* | |
112 | * Various lockdep statistics: | |
113 | */ | |
114 | extern atomic_t chain_lookup_hits; | |
115 | extern atomic_t chain_lookup_misses; | |
116 | extern atomic_t hardirqs_on_events; | |
117 | extern atomic_t hardirqs_off_events; | |
118 | extern atomic_t redundant_hardirqs_on; | |
119 | extern atomic_t redundant_hardirqs_off; | |
120 | extern atomic_t softirqs_on_events; | |
121 | extern atomic_t softirqs_off_events; | |
122 | extern atomic_t redundant_softirqs_on; | |
123 | extern atomic_t redundant_softirqs_off; | |
124 | extern atomic_t nr_unused_locks; | |
125 | extern atomic_t nr_cyclic_checks; | |
126 | extern atomic_t nr_cyclic_check_recursions; | |
127 | extern atomic_t nr_find_usage_forwards_checks; | |
128 | extern atomic_t nr_find_usage_forwards_recursions; | |
129 | extern atomic_t nr_find_usage_backwards_checks; | |
130 | extern atomic_t nr_find_usage_backwards_recursions; | |
131 | # define debug_atomic_inc(ptr) atomic_inc(ptr) | |
132 | # define debug_atomic_dec(ptr) atomic_dec(ptr) | |
133 | # define debug_atomic_read(ptr) atomic_read(ptr) | |
134 | #else | |
135 | # define debug_atomic_inc(ptr) do { } while (0) | |
136 | # define debug_atomic_dec(ptr) do { } while (0) | |
137 | # define debug_atomic_read(ptr) 0 | |
138 | #endif | |
c94aa5ca | 139 | |
d588e461 | 140 | |
12f3dfd0 | 141 | extern unsigned int max_bfs_queue_depth; |
d588e461 ML |
142 | extern unsigned long nr_list_entries; |
143 | extern struct lock_list list_entries[MAX_LOCKDEP_ENTRIES]; | |
144 | extern unsigned long bfs_accessed[]; | |
145 | ||
146 | /*For good efficiency of modular, we use power of 2*/ | |
147 | #define MAX_CIRCULAR_QUE_SIZE 4096UL | |
148 | ||
c94aa5ca ML |
149 | /* The circular_queue and helpers is used to implement the |
150 | * breadth-first search(BFS)algorithem, by which we can build | |
151 | * the shortest path from the next lock to be acquired to the | |
152 | * previous held lock if there is a circular between them. | |
153 | * */ | |
c94aa5ca ML |
154 | struct circular_queue{ |
155 | unsigned long element[MAX_CIRCULAR_QUE_SIZE]; | |
156 | unsigned int front, rear; | |
157 | }; | |
158 | ||
c94aa5ca ML |
159 | static inline void __cq_init(struct circular_queue *cq) |
160 | { | |
161 | cq->front = cq->rear = 0; | |
d588e461 | 162 | bitmap_zero(bfs_accessed, MAX_LOCKDEP_ENTRIES); |
c94aa5ca ML |
163 | } |
164 | ||
165 | static inline int __cq_empty(struct circular_queue *cq) | |
166 | { | |
167 | return (cq->front == cq->rear); | |
168 | } | |
169 | ||
170 | static inline int __cq_full(struct circular_queue *cq) | |
171 | { | |
d588e461 | 172 | return ((cq->rear + 1)&(MAX_CIRCULAR_QUE_SIZE-1)) == cq->front; |
c94aa5ca ML |
173 | } |
174 | ||
175 | static inline int __cq_enqueue(struct circular_queue *cq, unsigned long elem) | |
176 | { | |
177 | if (__cq_full(cq)) | |
178 | return -1; | |
179 | ||
180 | cq->element[cq->rear] = elem; | |
d588e461 | 181 | cq->rear = (cq->rear + 1)&(MAX_CIRCULAR_QUE_SIZE-1); |
c94aa5ca ML |
182 | return 0; |
183 | } | |
184 | ||
185 | static inline int __cq_dequeue(struct circular_queue *cq, unsigned long *elem) | |
186 | { | |
187 | if (__cq_empty(cq)) | |
188 | return -1; | |
189 | ||
190 | *elem = cq->element[cq->front]; | |
d588e461 | 191 | cq->front = (cq->front + 1)&(MAX_CIRCULAR_QUE_SIZE-1); |
c94aa5ca ML |
192 | return 0; |
193 | } | |
194 | ||
12f3dfd0 | 195 | static inline unsigned int __cq_get_elem_count(struct circular_queue *cq) |
c94aa5ca | 196 | { |
d588e461 | 197 | return (cq->rear - cq->front)&(MAX_CIRCULAR_QUE_SIZE-1); |
c94aa5ca ML |
198 | } |
199 | ||
200 | static inline void mark_lock_accessed(struct lock_list *lock, | |
201 | struct lock_list *parent) | |
202 | { | |
d588e461 ML |
203 | unsigned long nr; |
204 | nr = lock - list_entries; | |
205 | WARN_ON(nr >= nr_list_entries); | |
206 | lock->parent = parent; | |
207 | set_bit(nr, bfs_accessed); | |
c94aa5ca ML |
208 | } |
209 | ||
210 | static inline unsigned long lock_accessed(struct lock_list *lock) | |
211 | { | |
d588e461 ML |
212 | unsigned long nr; |
213 | nr = lock - list_entries; | |
214 | WARN_ON(nr >= nr_list_entries); | |
215 | return test_bit(nr, bfs_accessed); | |
c94aa5ca ML |
216 | } |
217 | ||
218 | static inline struct lock_list *get_lock_parent(struct lock_list *child) | |
219 | { | |
d588e461 | 220 | return child->parent; |
c94aa5ca ML |
221 | } |
222 | ||
24208ca7 | 223 | static inline int get_lock_depth(struct lock_list *child) |
c94aa5ca | 224 | { |
24208ca7 | 225 | int depth = 0; |
c94aa5ca ML |
226 | struct lock_list *parent; |
227 | ||
228 | while ((parent = get_lock_parent(child))) { | |
229 | child = parent; | |
230 | depth++; | |
231 | } | |
232 | return depth; | |
233 | } |