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