Commit | Line | Data |
---|---|---|
f3e97da3 IM |
1 | Runtime locking correctness validator |
2 | ===================================== | |
3 | ||
4 | started by Ingo Molnar <mingo@redhat.com> | |
387b1468 | 5 | |
f3e97da3 IM |
6 | additions by Arjan van de Ven <arjan@linux.intel.com> |
7 | ||
8 | Lock-class | |
9 | ---------- | |
10 | ||
11 | The basic object the validator operates upon is a 'class' of locks. | |
12 | ||
13 | A class of locks is a group of locks that are logically the same with | |
14 | respect to locking rules, even if the locks may have multiple (possibly | |
15 | tens of thousands of) instantiations. For example a lock in the inode | |
16 | struct is one class, while each inode has its own instantiation of that | |
17 | lock class. | |
18 | ||
c01fbbc8 YD |
19 | The validator tracks the 'usage state' of lock-classes, and it tracks |
20 | the dependencies between different lock-classes. Lock usage indicates | |
21 | how a lock is used with regard to its IRQ contexts, while lock | |
22 | dependency can be understood as lock order, where L1 -> L2 suggests that | |
23 | a task is attempting to acquire L2 while holding L1. From lockdep's | |
24 | perspective, the two locks (L1 and L2) are not necessarily related; that | |
25 | dependency just means the order ever happened. The validator maintains a | |
26 | continuing effort to prove lock usages and dependencies are correct or | |
27 | the validator will shoot a splat if incorrect. | |
28 | ||
29 | A lock-class's behavior is constructed by its instances collectively: | |
30 | when the first instance of a lock-class is used after bootup the class | |
31 | gets registered, then all (subsequent) instances will be mapped to the | |
32 | class and hence their usages and dependecies will contribute to those of | |
33 | the class. A lock-class does not go away when a lock instance does, but | |
34 | it can be removed if the memory space of the lock class (static or | |
35 | dynamic) is reclaimed, this happens for example when a module is | |
36 | unloaded or a workqueue is destroyed. | |
f3e97da3 IM |
37 | |
38 | State | |
39 | ----- | |
40 | ||
c01fbbc8 YD |
41 | The validator tracks lock-class usage history and divides the usage into |
42 | (4 usages * n STATEs + 1) categories: | |
f3e97da3 | 43 | |
c01fbbc8 | 44 | where the 4 usages can be: |
f510b233 | 45 | - 'ever held in STATE context' |
0e692a94 LZ |
46 | - 'ever held as readlock in STATE context' |
47 | - 'ever held with STATE enabled' | |
48 | - 'ever held as readlock with STATE enabled' | |
f510b233 | 49 | |
c01fbbc8 YD |
50 | where the n STATEs are coded in kernel/locking/lockdep_states.h and as of |
51 | now they include: | |
52 | - hardirq | |
53 | - softirq | |
f3e97da3 | 54 | |
c01fbbc8 | 55 | where the last 1 category is: |
f3e97da3 IM |
56 | - 'ever used' [ == !unused ] |
57 | ||
c01fbbc8 YD |
58 | When locking rules are violated, these usage bits are presented in the |
59 | locking error messages, inside curlies, with a total of 2 * n STATEs bits. | |
387b1468 | 60 | A contrived example:: |
fd7bcea3 JC |
61 | |
62 | modprobe/2287 is trying to acquire lock: | |
866d65b9 | 63 | (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24 |
fd7bcea3 JC |
64 | |
65 | but task is already holding lock: | |
866d65b9 | 66 | (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24 |
fd7bcea3 JC |
67 | |
68 | ||
c01fbbc8 YD |
69 | For a given lock, the bit positions from left to right indicate the usage |
70 | of the lock and readlock (if exists), for each of the n STATEs listed | |
71 | above respectively, and the character displayed at each bit position | |
72 | indicates: | |
fd7bcea3 | 73 | |
387b1468 | 74 | === =================================================== |
992d7ced ML |
75 | '.' acquired while irqs disabled and not in irq context |
76 | '-' acquired in irq context | |
77 | '+' acquired with irqs enabled | |
f510b233 | 78 | '?' acquired in irq context with irqs enabled. |
387b1468 | 79 | === =================================================== |
fd7bcea3 | 80 | |
387b1468 | 81 | The bits are illustrated with an example:: |
c01fbbc8 YD |
82 | |
83 | (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24 | |
84 | |||| | |
85 | ||| \-> softirq disabled and not in softirq context | |
86 | || \--> acquired in softirq context | |
87 | | \---> hardirq disabled and not in hardirq context | |
88 | \----> acquired in hardirq context | |
89 | ||
90 | ||
91 | For a given STATE, whether the lock is ever acquired in that STATE | |
92 | context and whether that STATE is enabled yields four possible cases as | |
93 | shown in the table below. The bit character is able to indicate which | |
94 | exact case is for the lock as of the reporting time. | |
95 | ||
387b1468 | 96 | +--------------+-------------+--------------+ |
c01fbbc8 | 97 | | | irq enabled | irq disabled | |
387b1468 | 98 | +--------------+-------------+--------------+ |
c01fbbc8 | 99 | | ever in irq | ? | - | |
387b1468 | 100 | +--------------+-------------+--------------+ |
c01fbbc8 | 101 | | never in irq | + | . | |
387b1468 | 102 | +--------------+-------------+--------------+ |
c01fbbc8 YD |
103 | |
104 | The character '-' suggests irq is disabled because if otherwise the | |
105 | charactor '?' would have been shown instead. Similar deduction can be | |
106 | applied for '+' too. | |
107 | ||
108 | Unused locks (e.g., mutexes) cannot be part of the cause of an error. | |
fd7bcea3 JC |
109 | |
110 | ||
f3e97da3 IM |
111 | Single-lock state rules: |
112 | ------------------------ | |
113 | ||
1ac4ba5e YD |
114 | A lock is irq-safe means it was ever used in an irq context, while a lock |
115 | is irq-unsafe means it was ever acquired with irq enabled. | |
116 | ||
f3e97da3 | 117 | A softirq-unsafe lock-class is automatically hardirq-unsafe as well. The |
1ac4ba5e | 118 | following states must be exclusive: only one of them is allowed to be set |
387b1468 | 119 | for any lock-class based on its usage:: |
1ac4ba5e YD |
120 | |
121 | <hardirq-safe> or <hardirq-unsafe> | |
122 | <softirq-safe> or <softirq-unsafe> | |
f3e97da3 | 123 | |
1ac4ba5e YD |
124 | This is because if a lock can be used in irq context (irq-safe) then it |
125 | cannot be ever acquired with irq enabled (irq-unsafe). Otherwise, a | |
126 | deadlock may happen. For example, in the scenario that after this lock | |
127 | was acquired but before released, if the context is interrupted this | |
128 | lock will be attempted to acquire twice, which creates a deadlock, | |
129 | referred to as lock recursion deadlock. | |
f3e97da3 | 130 | |
1ac4ba5e | 131 | The validator detects and reports lock usage that violates these |
f3e97da3 IM |
132 | single-lock state rules. |
133 | ||
134 | Multi-lock dependency rules: | |
135 | ---------------------------- | |
136 | ||
137 | The same lock-class must not be acquired twice, because this could lead | |
138 | to lock recursion deadlocks. | |
139 | ||
387b1468 | 140 | Furthermore, two locks can not be taken in inverse order:: |
f3e97da3 IM |
141 | |
142 | <L1> -> <L2> | |
143 | <L2> -> <L1> | |
144 | ||
1ac4ba5e YD |
145 | because this could lead to a deadlock - referred to as lock inversion |
146 | deadlock - as attempts to acquire the two locks form a circle which | |
147 | could lead to the two contexts waiting for each other permanently. The | |
148 | validator will find such dependency circle in arbitrary complexity, | |
149 | i.e., there can be any other locking sequence between the acquire-lock | |
150 | operations; the validator will still find whether these locks can be | |
151 | acquired in a circular fashion. | |
f3e97da3 IM |
152 | |
153 | Furthermore, the following usage based lock dependencies are not allowed | |
387b1468 | 154 | between any two lock-classes:: |
f3e97da3 IM |
155 | |
156 | <hardirq-safe> -> <hardirq-unsafe> | |
157 | <softirq-safe> -> <softirq-unsafe> | |
158 | ||
1d4093d3 | 159 | The first rule comes from the fact that a hardirq-safe lock could be |
f3e97da3 IM |
160 | taken by a hardirq context, interrupting a hardirq-unsafe lock - and |
161 | thus could result in a lock inversion deadlock. Likewise, a softirq-safe | |
162 | lock could be taken by an softirq context, interrupting a softirq-unsafe | |
163 | lock. | |
164 | ||
165 | The above rules are enforced for any locking sequence that occurs in the | |
166 | kernel: when acquiring a new lock, the validator checks whether there is | |
167 | any rule violation between the new lock and any of the held locks. | |
168 | ||
169 | When a lock-class changes its state, the following aspects of the above | |
170 | dependency rules are enforced: | |
171 | ||
172 | - if a new hardirq-safe lock is discovered, we check whether it | |
173 | took any hardirq-unsafe lock in the past. | |
174 | ||
175 | - if a new softirq-safe lock is discovered, we check whether it took | |
176 | any softirq-unsafe lock in the past. | |
177 | ||
178 | - if a new hardirq-unsafe lock is discovered, we check whether any | |
179 | hardirq-safe lock took it in the past. | |
180 | ||
181 | - if a new softirq-unsafe lock is discovered, we check whether any | |
182 | softirq-safe lock took it in the past. | |
183 | ||
184 | (Again, we do these checks too on the basis that an interrupt context | |
185 | could interrupt _any_ of the irq-unsafe or hardirq-unsafe locks, which | |
186 | could lead to a lock inversion deadlock - even if that lock scenario did | |
187 | not trigger in practice yet.) | |
188 | ||
189 | Exception: Nested data dependencies leading to nested locking | |
190 | ------------------------------------------------------------- | |
191 | ||
192 | There are a few cases where the Linux kernel acquires more than one | |
193 | instance of the same lock-class. Such cases typically happen when there | |
194 | is some sort of hierarchy within objects of the same type. In these | |
195 | cases there is an inherent "natural" ordering between the two objects | |
196 | (defined by the properties of the hierarchy), and the kernel grabs the | |
197 | locks in this fixed order on each of the objects. | |
198 | ||
2fe0ae78 | 199 | An example of such an object hierarchy that results in "nested locking" |
f3e97da3 IM |
200 | is that of a "whole disk" block-dev object and a "partition" block-dev |
201 | object; the partition is "part of" the whole device and as long as one | |
202 | always takes the whole disk lock as a higher lock than the partition | |
203 | lock, the lock ordering is fully correct. The validator does not | |
204 | automatically detect this natural ordering, as the locking rule behind | |
205 | the ordering is not static. | |
206 | ||
207 | In order to teach the validator about this correct usage model, new | |
208 | versions of the various locking primitives were added that allow you to | |
209 | specify a "nesting level". An example call, for the block device mutex, | |
387b1468 | 210 | looks like this:: |
f3e97da3 | 211 | |
387b1468 MCC |
212 | enum bdev_bd_mutex_lock_class |
213 | { | |
f3e97da3 IM |
214 | BD_MUTEX_NORMAL, |
215 | BD_MUTEX_WHOLE, | |
216 | BD_MUTEX_PARTITION | |
387b1468 | 217 | }; |
f3e97da3 | 218 | |
387b1468 | 219 | mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION); |
f3e97da3 IM |
220 | |
221 | In this case the locking is done on a bdev object that is known to be a | |
222 | partition. | |
223 | ||
a2ffd275 | 224 | The validator treats a lock that is taken in such a nested fashion as a |
f3e97da3 IM |
225 | separate (sub)class for the purposes of validation. |
226 | ||
227 | Note: When changing code to use the _nested() primitives, be careful and | |
2fe0ae78 | 228 | check really thoroughly that the hierarchy is correctly mapped; otherwise |
f3e97da3 IM |
229 | you can get false positives or false negatives. |
230 | ||
a1ea544f JL |
231 | Annotations |
232 | ----------- | |
233 | ||
234 | Two constructs can be used to annotate and check where and if certain locks | |
235 | must be held: lockdep_assert_held*(&lock) and lockdep_*pin_lock(&lock). | |
236 | ||
237 | As the name suggests, lockdep_assert_held* family of macros assert that a | |
238 | particular lock is held at a certain time (and generate a WARN() otherwise). | |
239 | This annotation is largely used all over the kernel, e.g. kernel/sched/ | |
387b1468 | 240 | core.c:: |
a1ea544f JL |
241 | |
242 | void update_rq_clock(struct rq *rq) | |
243 | { | |
244 | s64 delta; | |
245 | ||
246 | lockdep_assert_held(&rq->lock); | |
247 | [...] | |
248 | } | |
249 | ||
250 | where holding rq->lock is required to safely update a rq's clock. | |
251 | ||
252 | The other family of macros is lockdep_*pin_lock(), which is admittedly only | |
253 | used for rq->lock ATM. Despite their limited adoption these annotations | |
254 | generate a WARN() if the lock of interest is "accidentally" unlocked. This turns | |
255 | out to be especially helpful to debug code with callbacks, where an upper | |
256 | layer assumes a lock remains taken, but a lower layer thinks it can maybe drop | |
257 | and reacquire the lock ("unwittingly" introducing races). lockdep_pin_lock() | |
258 | returns a 'struct pin_cookie' that is then used by lockdep_unpin_lock() to check | |
387b1468 | 259 | that nobody tampered with the lock, e.g. kernel/sched/sched.h:: |
a1ea544f JL |
260 | |
261 | static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf) | |
262 | { | |
263 | rf->cookie = lockdep_pin_lock(&rq->lock); | |
264 | [...] | |
265 | } | |
266 | ||
267 | static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf) | |
268 | { | |
269 | [...] | |
270 | lockdep_unpin_lock(&rq->lock, rf->cookie); | |
271 | } | |
272 | ||
273 | While comments about locking requirements might provide useful information, | |
274 | the runtime checks performed by annotations are invaluable when debugging | |
275 | locking problems and they carry the same level of details when inspecting | |
276 | code. Always prefer annotations when in doubt! | |
277 | ||
f3e97da3 IM |
278 | Proof of 100% correctness: |
279 | -------------------------- | |
280 | ||
281 | The validator achieves perfect, mathematical 'closure' (proof of locking | |
282 | correctness) in the sense that for every simple, standalone single-task | |
992caacf | 283 | locking sequence that occurred at least once during the lifetime of the |
f3e97da3 IM |
284 | kernel, the validator proves it with a 100% certainty that no |
285 | combination and timing of these locking sequences can cause any class of | |
387b1468 | 286 | lock related deadlock. [1]_ |
f3e97da3 IM |
287 | |
288 | I.e. complex multi-CPU and multi-task locking scenarios do not have to | |
289 | occur in practice to prove a deadlock: only the simple 'component' | |
290 | locking chains have to occur at least once (anytime, in any | |
291 | task/context) for the validator to be able to prove correctness. (For | |
292 | example, complex deadlocks that would normally need more than 3 CPUs and | |
293 | a very unlikely constellation of tasks, irq-contexts and timings to | |
294 | occur, can be detected on a plain, lightly loaded single-CPU system as | |
295 | well!) | |
296 | ||
297 | This radically decreases the complexity of locking related QA of the | |
298 | kernel: what has to be done during QA is to trigger as many "simple" | |
299 | single-task locking dependencies in the kernel as possible, at least | |
300 | once, to prove locking correctness - instead of having to trigger every | |
301 | possible combination of locking interaction between CPUs, combined with | |
302 | every possible hardirq and softirq nesting scenario (which is impossible | |
303 | to do in practice). | |
304 | ||
387b1468 MCC |
305 | .. [1] |
306 | ||
307 | assuming that the validator itself is 100% correct, and no other | |
f3e97da3 IM |
308 | part of the system corrupts the state of the validator in any way. |
309 | We also assume that all NMI/SMM paths [which could interrupt | |
310 | even hardirq-disabled codepaths] are correct and do not interfere | |
311 | with the validator. We also assume that the 64-bit 'chain hash' | |
312 | value is unique for every lock-chain in the system. Also, lock | |
313 | recursion must not be higher than 20. | |
314 | ||
315 | Performance: | |
316 | ------------ | |
317 | ||
387b1468 | 318 | The above rules require **massive** amounts of runtime checking. If we did |
f3e97da3 IM |
319 | that for every lock taken and for every irqs-enable event, it would |
320 | render the system practically unusably slow. The complexity of checking | |
321 | is O(N^2), so even with just a few hundred lock-classes we'd have to do | |
322 | tens of thousands of checks for every event. | |
323 | ||
324 | This problem is solved by checking any given 'locking scenario' (unique | |
325 | sequence of locks taken after each other) only once. A simple stack of | |
326 | held locks is maintained, and a lightweight 64-bit hash value is | |
327 | calculated, which hash is unique for every lock chain. The hash value, | |
328 | when the chain is validated for the first time, is then put into a hash | |
329 | table, which hash-table can be checked in a lockfree manner. If the | |
330 | locking chain occurs again later on, the hash table tells us that we | |
1d4093d3 | 331 | don't have to validate the chain again. |
b804cb9e PM |
332 | |
333 | Troubleshooting: | |
334 | ---------------- | |
335 | ||
336 | The validator tracks a maximum of MAX_LOCKDEP_KEYS number of lock classes. | |
337 | Exceeding this number will trigger the following lockdep warning: | |
338 | ||
339 | (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS)) | |
340 | ||
341 | By default, MAX_LOCKDEP_KEYS is currently set to 8191, and typical | |
342 | desktop systems have less than 1,000 lock classes, so this warning | |
343 | normally results from lock-class leakage or failure to properly | |
344 | initialize locks. These two problems are illustrated below: | |
345 | ||
346 | 1. Repeated module loading and unloading while running the validator | |
347 | will result in lock-class leakage. The issue here is that each | |
348 | load of the module will create a new set of lock classes for | |
349 | that module's locks, but module unloading does not remove old | |
350 | classes (see below discussion of reuse of lock classes for why). | |
351 | Therefore, if that module is loaded and unloaded repeatedly, | |
352 | the number of lock classes will eventually reach the maximum. | |
353 | ||
354 | 2. Using structures such as arrays that have large numbers of | |
355 | locks that are not explicitly initialized. For example, | |
356 | a hash table with 8192 buckets where each bucket has its own | |
357 | spinlock_t will consume 8192 lock classes -unless- each spinlock | |
358 | is explicitly initialized at runtime, for example, using the | |
359 | run-time spin_lock_init() as opposed to compile-time initializers | |
360 | such as __SPIN_LOCK_UNLOCKED(). Failure to properly initialize | |
361 | the per-bucket spinlocks would guarantee lock-class overflow. | |
362 | In contrast, a loop that called spin_lock_init() on each lock | |
363 | would place all 8192 locks into a single lock class. | |
364 | ||
365 | The moral of this story is that you should always explicitly | |
366 | initialize your locks. | |
367 | ||
368 | One might argue that the validator should be modified to allow | |
369 | lock classes to be reused. However, if you are tempted to make this | |
370 | argument, first review the code and think through the changes that would | |
371 | be required, keeping in mind that the lock classes to be removed are | |
372 | likely to be linked into the lock-dependency graph. This turns out to | |
373 | be harder to do than to say. | |
374 | ||
375 | Of course, if you do run out of lock classes, the next thing to do is | |
376 | to find the offending lock classes. First, the following command gives | |
387b1468 | 377 | you the number of lock classes currently in use along with the maximum:: |
b804cb9e PM |
378 | |
379 | grep "lock-classes" /proc/lockdep_stats | |
380 | ||
387b1468 | 381 | This command produces the following output on a modest system:: |
b804cb9e | 382 | |
387b1468 | 383 | lock-classes: 748 [max: 8191] |
b804cb9e PM |
384 | |
385 | If the number allocated (748 above) increases continually over time, | |
386 | then there is likely a leak. The following command can be used to | |
387b1468 | 387 | identify the leaking lock classes:: |
b804cb9e PM |
388 | |
389 | grep "BD" /proc/lockdep | |
390 | ||
391 | Run the command and save the output, then compare against the output from | |
392 | a later run of this command to identify the leakers. This same output | |
393 | can also help you find situations where runtime lock initialization has | |
394 | been omitted. |