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: |
e3e7439d | 45 | |
f510b233 | 46 | - 'ever held in STATE context' |
0e692a94 LZ |
47 | - 'ever held as readlock in STATE context' |
48 | - 'ever held with STATE enabled' | |
49 | - 'ever held as readlock with STATE enabled' | |
f510b233 | 50 | |
c01fbbc8 YD |
51 | where the n STATEs are coded in kernel/locking/lockdep_states.h and as of |
52 | now they include: | |
e3e7439d | 53 | |
c01fbbc8 YD |
54 | - hardirq |
55 | - softirq | |
f3e97da3 | 56 | |
c01fbbc8 | 57 | where the last 1 category is: |
e3e7439d | 58 | |
f3e97da3 IM |
59 | - 'ever used' [ == !unused ] |
60 | ||
c01fbbc8 YD |
61 | When locking rules are violated, these usage bits are presented in the |
62 | locking error messages, inside curlies, with a total of 2 * n STATEs bits. | |
387b1468 | 63 | A contrived example:: |
fd7bcea3 JC |
64 | |
65 | modprobe/2287 is trying to acquire lock: | |
866d65b9 | 66 | (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24 |
fd7bcea3 JC |
67 | |
68 | but task is already holding lock: | |
866d65b9 | 69 | (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24 |
fd7bcea3 JC |
70 | |
71 | ||
c01fbbc8 YD |
72 | For a given lock, the bit positions from left to right indicate the usage |
73 | of the lock and readlock (if exists), for each of the n STATEs listed | |
74 | above respectively, and the character displayed at each bit position | |
75 | indicates: | |
fd7bcea3 | 76 | |
387b1468 | 77 | === =================================================== |
992d7ced ML |
78 | '.' acquired while irqs disabled and not in irq context |
79 | '-' acquired in irq context | |
80 | '+' acquired with irqs enabled | |
f510b233 | 81 | '?' acquired in irq context with irqs enabled. |
387b1468 | 82 | === =================================================== |
fd7bcea3 | 83 | |
387b1468 | 84 | The bits are illustrated with an example:: |
c01fbbc8 YD |
85 | |
86 | (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24 | |
87 | |||| | |
88 | ||| \-> softirq disabled and not in softirq context | |
89 | || \--> acquired in softirq context | |
90 | | \---> hardirq disabled and not in hardirq context | |
91 | \----> acquired in hardirq context | |
92 | ||
93 | ||
94 | For a given STATE, whether the lock is ever acquired in that STATE | |
95 | context and whether that STATE is enabled yields four possible cases as | |
96 | shown in the table below. The bit character is able to indicate which | |
97 | exact case is for the lock as of the reporting time. | |
98 | ||
387b1468 | 99 | +--------------+-------------+--------------+ |
c01fbbc8 | 100 | | | irq enabled | irq disabled | |
387b1468 | 101 | +--------------+-------------+--------------+ |
e3e7439d | 102 | | ever in irq | '?' | '-' | |
387b1468 | 103 | +--------------+-------------+--------------+ |
e3e7439d | 104 | | never in irq | '+' | '.' | |
387b1468 | 105 | +--------------+-------------+--------------+ |
c01fbbc8 YD |
106 | |
107 | The character '-' suggests irq is disabled because if otherwise the | |
108 | charactor '?' would have been shown instead. Similar deduction can be | |
109 | applied for '+' too. | |
110 | ||
111 | Unused locks (e.g., mutexes) cannot be part of the cause of an error. | |
fd7bcea3 JC |
112 | |
113 | ||
f3e97da3 IM |
114 | Single-lock state rules: |
115 | ------------------------ | |
116 | ||
1ac4ba5e YD |
117 | A lock is irq-safe means it was ever used in an irq context, while a lock |
118 | is irq-unsafe means it was ever acquired with irq enabled. | |
119 | ||
f3e97da3 | 120 | A softirq-unsafe lock-class is automatically hardirq-unsafe as well. The |
1ac4ba5e | 121 | following states must be exclusive: only one of them is allowed to be set |
387b1468 | 122 | for any lock-class based on its usage:: |
1ac4ba5e YD |
123 | |
124 | <hardirq-safe> or <hardirq-unsafe> | |
125 | <softirq-safe> or <softirq-unsafe> | |
f3e97da3 | 126 | |
1ac4ba5e YD |
127 | This is because if a lock can be used in irq context (irq-safe) then it |
128 | cannot be ever acquired with irq enabled (irq-unsafe). Otherwise, a | |
129 | deadlock may happen. For example, in the scenario that after this lock | |
130 | was acquired but before released, if the context is interrupted this | |
131 | lock will be attempted to acquire twice, which creates a deadlock, | |
132 | referred to as lock recursion deadlock. | |
f3e97da3 | 133 | |
1ac4ba5e | 134 | The validator detects and reports lock usage that violates these |
f3e97da3 IM |
135 | single-lock state rules. |
136 | ||
137 | Multi-lock dependency rules: | |
138 | ---------------------------- | |
139 | ||
140 | The same lock-class must not be acquired twice, because this could lead | |
141 | to lock recursion deadlocks. | |
142 | ||
387b1468 | 143 | Furthermore, two locks can not be taken in inverse order:: |
f3e97da3 IM |
144 | |
145 | <L1> -> <L2> | |
146 | <L2> -> <L1> | |
147 | ||
1ac4ba5e YD |
148 | because this could lead to a deadlock - referred to as lock inversion |
149 | deadlock - as attempts to acquire the two locks form a circle which | |
150 | could lead to the two contexts waiting for each other permanently. The | |
151 | validator will find such dependency circle in arbitrary complexity, | |
152 | i.e., there can be any other locking sequence between the acquire-lock | |
153 | operations; the validator will still find whether these locks can be | |
154 | acquired in a circular fashion. | |
f3e97da3 IM |
155 | |
156 | Furthermore, the following usage based lock dependencies are not allowed | |
387b1468 | 157 | between any two lock-classes:: |
f3e97da3 IM |
158 | |
159 | <hardirq-safe> -> <hardirq-unsafe> | |
160 | <softirq-safe> -> <softirq-unsafe> | |
161 | ||
1d4093d3 | 162 | The first rule comes from the fact that a hardirq-safe lock could be |
f3e97da3 IM |
163 | taken by a hardirq context, interrupting a hardirq-unsafe lock - and |
164 | thus could result in a lock inversion deadlock. Likewise, a softirq-safe | |
165 | lock could be taken by an softirq context, interrupting a softirq-unsafe | |
166 | lock. | |
167 | ||
168 | The above rules are enforced for any locking sequence that occurs in the | |
169 | kernel: when acquiring a new lock, the validator checks whether there is | |
170 | any rule violation between the new lock and any of the held locks. | |
171 | ||
172 | When a lock-class changes its state, the following aspects of the above | |
173 | dependency rules are enforced: | |
174 | ||
175 | - if a new hardirq-safe lock is discovered, we check whether it | |
176 | took any hardirq-unsafe lock in the past. | |
177 | ||
178 | - if a new softirq-safe lock is discovered, we check whether it took | |
179 | any softirq-unsafe lock in the past. | |
180 | ||
181 | - if a new hardirq-unsafe lock is discovered, we check whether any | |
182 | hardirq-safe lock took it in the past. | |
183 | ||
184 | - if a new softirq-unsafe lock is discovered, we check whether any | |
185 | softirq-safe lock took it in the past. | |
186 | ||
187 | (Again, we do these checks too on the basis that an interrupt context | |
188 | could interrupt _any_ of the irq-unsafe or hardirq-unsafe locks, which | |
189 | could lead to a lock inversion deadlock - even if that lock scenario did | |
190 | not trigger in practice yet.) | |
191 | ||
192 | Exception: Nested data dependencies leading to nested locking | |
193 | ------------------------------------------------------------- | |
194 | ||
195 | There are a few cases where the Linux kernel acquires more than one | |
196 | instance of the same lock-class. Such cases typically happen when there | |
197 | is some sort of hierarchy within objects of the same type. In these | |
198 | cases there is an inherent "natural" ordering between the two objects | |
199 | (defined by the properties of the hierarchy), and the kernel grabs the | |
200 | locks in this fixed order on each of the objects. | |
201 | ||
2fe0ae78 | 202 | An example of such an object hierarchy that results in "nested locking" |
f3e97da3 IM |
203 | is that of a "whole disk" block-dev object and a "partition" block-dev |
204 | object; the partition is "part of" the whole device and as long as one | |
205 | always takes the whole disk lock as a higher lock than the partition | |
206 | lock, the lock ordering is fully correct. The validator does not | |
207 | automatically detect this natural ordering, as the locking rule behind | |
208 | the ordering is not static. | |
209 | ||
210 | In order to teach the validator about this correct usage model, new | |
211 | versions of the various locking primitives were added that allow you to | |
212 | specify a "nesting level". An example call, for the block device mutex, | |
387b1468 | 213 | looks like this:: |
f3e97da3 | 214 | |
387b1468 MCC |
215 | enum bdev_bd_mutex_lock_class |
216 | { | |
f3e97da3 IM |
217 | BD_MUTEX_NORMAL, |
218 | BD_MUTEX_WHOLE, | |
219 | BD_MUTEX_PARTITION | |
387b1468 | 220 | }; |
f3e97da3 | 221 | |
e3e7439d | 222 | mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION); |
f3e97da3 IM |
223 | |
224 | In this case the locking is done on a bdev object that is known to be a | |
225 | partition. | |
226 | ||
a2ffd275 | 227 | The validator treats a lock that is taken in such a nested fashion as a |
f3e97da3 IM |
228 | separate (sub)class for the purposes of validation. |
229 | ||
230 | Note: When changing code to use the _nested() primitives, be careful and | |
2fe0ae78 | 231 | check really thoroughly that the hierarchy is correctly mapped; otherwise |
f3e97da3 IM |
232 | you can get false positives or false negatives. |
233 | ||
a1ea544f JL |
234 | Annotations |
235 | ----------- | |
236 | ||
237 | Two constructs can be used to annotate and check where and if certain locks | |
238 | must be held: lockdep_assert_held*(&lock) and lockdep_*pin_lock(&lock). | |
239 | ||
240 | As the name suggests, lockdep_assert_held* family of macros assert that a | |
241 | particular lock is held at a certain time (and generate a WARN() otherwise). | |
242 | This annotation is largely used all over the kernel, e.g. kernel/sched/ | |
387b1468 | 243 | core.c:: |
a1ea544f JL |
244 | |
245 | void update_rq_clock(struct rq *rq) | |
246 | { | |
247 | s64 delta; | |
248 | ||
249 | lockdep_assert_held(&rq->lock); | |
250 | [...] | |
251 | } | |
252 | ||
253 | where holding rq->lock is required to safely update a rq's clock. | |
254 | ||
255 | The other family of macros is lockdep_*pin_lock(), which is admittedly only | |
256 | used for rq->lock ATM. Despite their limited adoption these annotations | |
257 | generate a WARN() if the lock of interest is "accidentally" unlocked. This turns | |
258 | out to be especially helpful to debug code with callbacks, where an upper | |
259 | layer assumes a lock remains taken, but a lower layer thinks it can maybe drop | |
260 | and reacquire the lock ("unwittingly" introducing races). lockdep_pin_lock() | |
261 | returns a 'struct pin_cookie' that is then used by lockdep_unpin_lock() to check | |
387b1468 | 262 | that nobody tampered with the lock, e.g. kernel/sched/sched.h:: |
a1ea544f JL |
263 | |
264 | static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf) | |
265 | { | |
266 | rf->cookie = lockdep_pin_lock(&rq->lock); | |
267 | [...] | |
268 | } | |
269 | ||
270 | static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf) | |
271 | { | |
272 | [...] | |
273 | lockdep_unpin_lock(&rq->lock, rf->cookie); | |
274 | } | |
275 | ||
276 | While comments about locking requirements might provide useful information, | |
277 | the runtime checks performed by annotations are invaluable when debugging | |
278 | locking problems and they carry the same level of details when inspecting | |
279 | code. Always prefer annotations when in doubt! | |
280 | ||
f3e97da3 IM |
281 | Proof of 100% correctness: |
282 | -------------------------- | |
283 | ||
284 | The validator achieves perfect, mathematical 'closure' (proof of locking | |
285 | correctness) in the sense that for every simple, standalone single-task | |
992caacf | 286 | locking sequence that occurred at least once during the lifetime of the |
f3e97da3 IM |
287 | kernel, the validator proves it with a 100% certainty that no |
288 | combination and timing of these locking sequences can cause any class of | |
387b1468 | 289 | lock related deadlock. [1]_ |
f3e97da3 IM |
290 | |
291 | I.e. complex multi-CPU and multi-task locking scenarios do not have to | |
292 | occur in practice to prove a deadlock: only the simple 'component' | |
293 | locking chains have to occur at least once (anytime, in any | |
294 | task/context) for the validator to be able to prove correctness. (For | |
295 | example, complex deadlocks that would normally need more than 3 CPUs and | |
296 | a very unlikely constellation of tasks, irq-contexts and timings to | |
297 | occur, can be detected on a plain, lightly loaded single-CPU system as | |
298 | well!) | |
299 | ||
300 | This radically decreases the complexity of locking related QA of the | |
301 | kernel: what has to be done during QA is to trigger as many "simple" | |
302 | single-task locking dependencies in the kernel as possible, at least | |
303 | once, to prove locking correctness - instead of having to trigger every | |
304 | possible combination of locking interaction between CPUs, combined with | |
305 | every possible hardirq and softirq nesting scenario (which is impossible | |
306 | to do in practice). | |
307 | ||
387b1468 MCC |
308 | .. [1] |
309 | ||
310 | assuming that the validator itself is 100% correct, and no other | |
f3e97da3 IM |
311 | part of the system corrupts the state of the validator in any way. |
312 | We also assume that all NMI/SMM paths [which could interrupt | |
313 | even hardirq-disabled codepaths] are correct and do not interfere | |
314 | with the validator. We also assume that the 64-bit 'chain hash' | |
315 | value is unique for every lock-chain in the system. Also, lock | |
316 | recursion must not be higher than 20. | |
317 | ||
318 | Performance: | |
319 | ------------ | |
320 | ||
387b1468 | 321 | The above rules require **massive** amounts of runtime checking. If we did |
f3e97da3 IM |
322 | that for every lock taken and for every irqs-enable event, it would |
323 | render the system practically unusably slow. The complexity of checking | |
324 | is O(N^2), so even with just a few hundred lock-classes we'd have to do | |
325 | tens of thousands of checks for every event. | |
326 | ||
327 | This problem is solved by checking any given 'locking scenario' (unique | |
328 | sequence of locks taken after each other) only once. A simple stack of | |
329 | held locks is maintained, and a lightweight 64-bit hash value is | |
330 | calculated, which hash is unique for every lock chain. The hash value, | |
331 | when the chain is validated for the first time, is then put into a hash | |
332 | table, which hash-table can be checked in a lockfree manner. If the | |
333 | locking chain occurs again later on, the hash table tells us that we | |
1d4093d3 | 334 | don't have to validate the chain again. |
b804cb9e PM |
335 | |
336 | Troubleshooting: | |
337 | ---------------- | |
338 | ||
339 | The validator tracks a maximum of MAX_LOCKDEP_KEYS number of lock classes. | |
e3e7439d | 340 | Exceeding this number will trigger the following lockdep warning:: |
b804cb9e PM |
341 | |
342 | (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS)) | |
343 | ||
344 | By default, MAX_LOCKDEP_KEYS is currently set to 8191, and typical | |
345 | desktop systems have less than 1,000 lock classes, so this warning | |
346 | normally results from lock-class leakage or failure to properly | |
347 | initialize locks. These two problems are illustrated below: | |
348 | ||
349 | 1. Repeated module loading and unloading while running the validator | |
350 | will result in lock-class leakage. The issue here is that each | |
351 | load of the module will create a new set of lock classes for | |
352 | that module's locks, but module unloading does not remove old | |
353 | classes (see below discussion of reuse of lock classes for why). | |
354 | Therefore, if that module is loaded and unloaded repeatedly, | |
355 | the number of lock classes will eventually reach the maximum. | |
356 | ||
357 | 2. Using structures such as arrays that have large numbers of | |
358 | locks that are not explicitly initialized. For example, | |
359 | a hash table with 8192 buckets where each bucket has its own | |
360 | spinlock_t will consume 8192 lock classes -unless- each spinlock | |
361 | is explicitly initialized at runtime, for example, using the | |
362 | run-time spin_lock_init() as opposed to compile-time initializers | |
363 | such as __SPIN_LOCK_UNLOCKED(). Failure to properly initialize | |
364 | the per-bucket spinlocks would guarantee lock-class overflow. | |
365 | In contrast, a loop that called spin_lock_init() on each lock | |
366 | would place all 8192 locks into a single lock class. | |
367 | ||
368 | The moral of this story is that you should always explicitly | |
369 | initialize your locks. | |
370 | ||
371 | One might argue that the validator should be modified to allow | |
372 | lock classes to be reused. However, if you are tempted to make this | |
373 | argument, first review the code and think through the changes that would | |
374 | be required, keeping in mind that the lock classes to be removed are | |
375 | likely to be linked into the lock-dependency graph. This turns out to | |
376 | be harder to do than to say. | |
377 | ||
378 | Of course, if you do run out of lock classes, the next thing to do is | |
379 | to find the offending lock classes. First, the following command gives | |
387b1468 | 380 | you the number of lock classes currently in use along with the maximum:: |
b804cb9e PM |
381 | |
382 | grep "lock-classes" /proc/lockdep_stats | |
383 | ||
387b1468 | 384 | This command produces the following output on a modest system:: |
b804cb9e | 385 | |
387b1468 | 386 | lock-classes: 748 [max: 8191] |
b804cb9e PM |
387 | |
388 | If the number allocated (748 above) increases continually over time, | |
389 | then there is likely a leak. The following command can be used to | |
387b1468 | 390 | identify the leaking lock classes:: |
b804cb9e PM |
391 | |
392 | grep "BD" /proc/lockdep | |
393 | ||
394 | Run the command and save the output, then compare against the output from | |
395 | a later run of this command to identify the leakers. This same output | |
396 | can also help you find situations where runtime lock initialization has | |
397 | been omitted. | |
224ec489 BF |
398 | |
399 | Recursive read locks: | |
400 | --------------------- | |
401 | The whole of the rest document tries to prove a certain type of cycle is equivalent | |
402 | to deadlock possibility. | |
403 | ||
404 | There are three types of lockers: writers (i.e. exclusive lockers, like | |
405 | spin_lock() or write_lock()), non-recursive readers (i.e. shared lockers, like | |
406 | down_read()) and recursive readers (recursive shared lockers, like rcu_read_lock()). | |
407 | And we use the following notations of those lockers in the rest of the document: | |
408 | ||
409 | W or E: stands for writers (exclusive lockers). | |
410 | r: stands for non-recursive readers. | |
411 | R: stands for recursive readers. | |
412 | S: stands for all readers (non-recursive + recursive), as both are shared lockers. | |
413 | N: stands for writers and non-recursive readers, as both are not recursive. | |
414 | ||
415 | Obviously, N is "r or W" and S is "r or R". | |
416 | ||
417 | Recursive readers, as their name indicates, are the lockers allowed to acquire | |
418 | even inside the critical section of another reader of the same lock instance, | |
419 | in other words, allowing nested read-side critical sections of one lock instance. | |
420 | ||
421 | While non-recursive readers will cause a self deadlock if trying to acquire inside | |
422 | the critical section of another reader of the same lock instance. | |
423 | ||
424 | The difference between recursive readers and non-recursive readers is because: | |
425 | recursive readers get blocked only by a write lock *holder*, while non-recursive | |
e3e7439d MCC |
426 | readers could get blocked by a write lock *waiter*. Considering the follow |
427 | example:: | |
224ec489 BF |
428 | |
429 | TASK A: TASK B: | |
430 | ||
431 | read_lock(X); | |
432 | write_lock(X); | |
433 | read_lock_2(X); | |
434 | ||
435 | Task A gets the reader (no matter whether recursive or non-recursive) on X via | |
436 | read_lock() first. And when task B tries to acquire writer on X, it will block | |
437 | and become a waiter for writer on X. Now if read_lock_2() is recursive readers, | |
438 | task A will make progress, because writer waiters don't block recursive readers, | |
439 | and there is no deadlock. However, if read_lock_2() is non-recursive readers, | |
440 | it will get blocked by writer waiter B, and cause a self deadlock. | |
441 | ||
442 | Block conditions on readers/writers of the same lock instance: | |
443 | -------------------------------------------------------------- | |
444 | There are simply four block conditions: | |
445 | ||
446 | 1. Writers block other writers. | |
447 | 2. Readers block writers. | |
448 | 3. Writers block both recursive readers and non-recursive readers. | |
449 | 4. And readers (recursive or not) don't block other recursive readers but | |
450 | may block non-recursive readers (because of the potential co-existing | |
451 | writer waiters) | |
452 | ||
453 | Block condition matrix, Y means the row blocks the column, and N means otherwise. | |
454 | ||
224ec489 | 455 | +---+---+---+---+ |
fab6216f | 456 | | | W | r | R | |
e3e7439d | 457 | +---+---+---+---+ |
fab6216f | 458 | | W | Y | Y | Y | |
e3e7439d MCC |
459 | +---+---+---+---+ |
460 | | r | Y | Y | N | | |
224ec489 | 461 | +---+---+---+---+ |
e3e7439d | 462 | | R | Y | Y | N | |
224ec489 | 463 | +---+---+---+---+ |
224ec489 BF |
464 | |
465 | (W: writers, r: non-recursive readers, R: recursive readers) | |
466 | ||
467 | ||
468 | acquired recursively. Unlike non-recursive read locks, recursive read locks | |
469 | only get blocked by current write lock *holders* other than write lock | |
e3e7439d | 470 | *waiters*, for example:: |
224ec489 BF |
471 | |
472 | TASK A: TASK B: | |
473 | ||
474 | read_lock(X); | |
475 | ||
476 | write_lock(X); | |
477 | ||
478 | read_lock(X); | |
479 | ||
480 | is not a deadlock for recursive read locks, as while the task B is waiting for | |
481 | the lock X, the second read_lock() doesn't need to wait because it's a recursive | |
482 | read lock. However if the read_lock() is non-recursive read lock, then the above | |
483 | case is a deadlock, because even if the write_lock() in TASK B cannot get the | |
484 | lock, but it can block the second read_lock() in TASK A. | |
485 | ||
486 | Note that a lock can be a write lock (exclusive lock), a non-recursive read | |
487 | lock (non-recursive shared lock) or a recursive read lock (recursive shared | |
488 | lock), depending on the lock operations used to acquire it (more specifically, | |
489 | the value of the 'read' parameter for lock_acquire()). In other words, a single | |
490 | lock instance has three types of acquisition depending on the acquisition | |
491 | functions: exclusive, non-recursive read, and recursive read. | |
492 | ||
493 | To be concise, we call that write locks and non-recursive read locks as | |
494 | "non-recursive" locks and recursive read locks as "recursive" locks. | |
495 | ||
496 | Recursive locks don't block each other, while non-recursive locks do (this is | |
497 | even true for two non-recursive read locks). A non-recursive lock can block the | |
498 | corresponding recursive lock, and vice versa. | |
499 | ||
e3e7439d | 500 | A deadlock case with recursive locks involved is as follow:: |
224ec489 BF |
501 | |
502 | TASK A: TASK B: | |
503 | ||
504 | read_lock(X); | |
505 | read_lock(Y); | |
506 | write_lock(Y); | |
507 | write_lock(X); | |
508 | ||
509 | Task A is waiting for task B to read_unlock() Y and task B is waiting for task | |
510 | A to read_unlock() X. | |
511 | ||
512 | Dependency types and strong dependency paths: | |
513 | --------------------------------------------- | |
514 | Lock dependencies record the orders of the acquisitions of a pair of locks, and | |
515 | because there are 3 types for lockers, there are, in theory, 9 types of lock | |
516 | dependencies, but we can show that 4 types of lock dependencies are enough for | |
517 | deadlock detection. | |
518 | ||
e3e7439d | 519 | For each lock dependency:: |
224ec489 BF |
520 | |
521 | L1 -> L2 | |
522 | ||
523 | , which means lockdep has seen L1 held before L2 held in the same context at runtime. | |
524 | And in deadlock detection, we care whether we could get blocked on L2 with L1 held, | |
525 | IOW, whether there is a locker L3 that L1 blocks L3 and L2 gets blocked by L3. So | |
526 | we only care about 1) what L1 blocks and 2) what blocks L2. As a result, we can combine | |
527 | recursive readers and non-recursive readers for L1 (as they block the same types) and | |
528 | we can combine writers and non-recursive readers for L2 (as they get blocked by the | |
529 | same types). | |
530 | ||
531 | With the above combination for simplification, there are 4 types of dependency edges | |
532 | in the lockdep graph: | |
533 | ||
e3e7439d MCC |
534 | 1) -(ER)->: |
535 | exclusive writer to recursive reader dependency, "X -(ER)-> Y" means | |
224ec489 BF |
536 | X -> Y and X is a writer and Y is a recursive reader. |
537 | ||
e3e7439d MCC |
538 | 2) -(EN)->: |
539 | exclusive writer to non-recursive locker dependency, "X -(EN)-> Y" means | |
224ec489 BF |
540 | X -> Y and X is a writer and Y is either a writer or non-recursive reader. |
541 | ||
e3e7439d MCC |
542 | 3) -(SR)->: |
543 | shared reader to recursive reader dependency, "X -(SR)-> Y" means | |
224ec489 BF |
544 | X -> Y and X is a reader (recursive or not) and Y is a recursive reader. |
545 | ||
e3e7439d MCC |
546 | 4) -(SN)->: |
547 | shared reader to non-recursive locker dependency, "X -(SN)-> Y" means | |
224ec489 BF |
548 | X -> Y and X is a reader (recursive or not) and Y is either a writer or |
549 | non-recursive reader. | |
550 | ||
e3e7439d MCC |
551 | Note that given two locks, they may have multiple dependencies between them, |
552 | for example:: | |
224ec489 BF |
553 | |
554 | TASK A: | |
555 | ||
556 | read_lock(X); | |
557 | write_lock(Y); | |
558 | ... | |
559 | ||
560 | TASK B: | |
561 | ||
562 | write_lock(X); | |
563 | write_lock(Y); | |
564 | ||
565 | , we have both X -(SN)-> Y and X -(EN)-> Y in the dependency graph. | |
566 | ||
567 | We use -(xN)-> to represent edges that are either -(EN)-> or -(SN)->, the | |
568 | similar for -(Ex)->, -(xR)-> and -(Sx)-> | |
569 | ||
570 | A "path" is a series of conjunct dependency edges in the graph. And we define a | |
571 | "strong" path, which indicates the strong dependency throughout each dependency | |
572 | in the path, as the path that doesn't have two conjunct edges (dependencies) as | |
573 | -(xR)-> and -(Sx)->. In other words, a "strong" path is a path from a lock | |
574 | walking to another through the lock dependencies, and if X -> Y -> Z is in the | |
575 | path (where X, Y, Z are locks), and the walk from X to Y is through a -(SR)-> or | |
576 | -(ER)-> dependency, the walk from Y to Z must not be through a -(SN)-> or | |
577 | -(SR)-> dependency. | |
578 | ||
579 | We will see why the path is called "strong" in next section. | |
580 | ||
581 | Recursive Read Deadlock Detection: | |
582 | ---------------------------------- | |
583 | ||
584 | We now prove two things: | |
585 | ||
586 | Lemma 1: | |
587 | ||
588 | If there is a closed strong path (i.e. a strong circle), then there is a | |
589 | combination of locking sequences that causes deadlock. I.e. a strong circle is | |
590 | sufficient for deadlock detection. | |
591 | ||
592 | Lemma 2: | |
593 | ||
594 | If there is no closed strong path (i.e. strong circle), then there is no | |
595 | combination of locking sequences that could cause deadlock. I.e. strong | |
596 | circles are necessary for deadlock detection. | |
597 | ||
598 | With these two Lemmas, we can easily say a closed strong path is both sufficient | |
599 | and necessary for deadlocks, therefore a closed strong path is equivalent to | |
600 | deadlock possibility. As a closed strong path stands for a dependency chain that | |
601 | could cause deadlocks, so we call it "strong", considering there are dependency | |
602 | circles that won't cause deadlocks. | |
603 | ||
604 | Proof for sufficiency (Lemma 1): | |
605 | ||
e3e7439d | 606 | Let's say we have a strong circle:: |
224ec489 BF |
607 | |
608 | L1 -> L2 ... -> Ln -> L1 | |
609 | ||
e3e7439d | 610 | , which means we have dependencies:: |
224ec489 BF |
611 | |
612 | L1 -> L2 | |
613 | L2 -> L3 | |
614 | ... | |
615 | Ln-1 -> Ln | |
616 | Ln -> L1 | |
617 | ||
618 | We now can construct a combination of locking sequences that cause deadlock: | |
619 | ||
620 | Firstly let's make one CPU/task get the L1 in L1 -> L2, and then another get | |
621 | the L2 in L2 -> L3, and so on. After this, all of the Lx in Lx -> Lx+1 are | |
622 | held by different CPU/tasks. | |
623 | ||
624 | And then because we have L1 -> L2, so the holder of L1 is going to acquire L2 | |
625 | in L1 -> L2, however since L2 is already held by another CPU/task, plus L1 -> | |
626 | L2 and L2 -> L3 are not -(xR)-> and -(Sx)-> (the definition of strong), which | |
627 | means either L2 in L1 -> L2 is a non-recursive locker (blocked by anyone) or | |
628 | the L2 in L2 -> L3, is writer (blocking anyone), therefore the holder of L1 | |
629 | cannot get L2, it has to wait L2's holder to release. | |
630 | ||
631 | Moreover, we can have a similar conclusion for L2's holder: it has to wait L3's | |
632 | holder to release, and so on. We now can prove that Lx's holder has to wait for | |
633 | Lx+1's holder to release, and note that Ln+1 is L1, so we have a circular | |
634 | waiting scenario and nobody can get progress, therefore a deadlock. | |
635 | ||
636 | Proof for necessary (Lemma 2): | |
637 | ||
638 | Lemma 2 is equivalent to: If there is a deadlock scenario, then there must be a | |
639 | strong circle in the dependency graph. | |
640 | ||
641 | According to Wikipedia[1], if there is a deadlock, then there must be a circular | |
642 | waiting scenario, means there are N CPU/tasks, where CPU/task P1 is waiting for | |
643 | a lock held by P2, and P2 is waiting for a lock held by P3, ... and Pn is waiting | |
644 | for a lock held by P1. Let's name the lock Px is waiting as Lx, so since P1 is waiting | |
645 | for L1 and holding Ln, so we will have Ln -> L1 in the dependency graph. Similarly, | |
646 | we have L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln in the dependency graph, which means we | |
e3e7439d | 647 | have a circle:: |
224ec489 BF |
648 | |
649 | Ln -> L1 -> L2 -> ... -> Ln | |
650 | ||
651 | , and now let's prove the circle is strong: | |
652 | ||
653 | For a lock Lx, Px contributes the dependency Lx-1 -> Lx and Px+1 contributes | |
654 | the dependency Lx -> Lx+1, and since Px is waiting for Px+1 to release Lx, | |
655 | so it's impossible that Lx on Px+1 is a reader and Lx on Px is a recursive | |
656 | reader, because readers (no matter recursive or not) don't block recursive | |
657 | readers, therefore Lx-1 -> Lx and Lx -> Lx+1 cannot be a -(xR)-> -(Sx)-> pair, | |
658 | and this is true for any lock in the circle, therefore, the circle is strong. | |
659 | ||
660 | References: | |
661 | ----------- | |
662 | [1]: https://en.wikipedia.org/wiki/Deadlock | |
663 | [2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill |