1 Runtime locking correctness validator
2 =====================================
3
4 started by Ingo Molnar <mingo@redhat.com>
5
6 additions by Arjan van de Ven <arjan@linux.inte
7
8 Lock-class
9 ----------
10
11 The basic object the validator operates upon i
12
13 A class of locks is a group of locks that are
14 respect to locking rules, even if the locks ma
15 tens of thousands of) instantiations. For exam
16 struct is one class, while each inode has its
17 lock class.
18
19 The validator tracks the 'usage state' of lock
20 the dependencies between different lock-classe
21 how a lock is used with regard to its IRQ cont
22 dependency can be understood as lock order, wh
23 a task is attempting to acquire L2 while holdi
24 perspective, the two locks (L1 and L2) are not
25 dependency just means the order ever happened.
26 continuing effort to prove lock usages and dep
27 the validator will shoot a splat if incorrect.
28
29 A lock-class's behavior is constructed by its
30 when the first instance of a lock-class is use
31 gets registered, then all (subsequent) instanc
32 class and hence their usages and dependencies
33 the class. A lock-class does not go away when
34 it can be removed if the memory space of the l
35 dynamic) is reclaimed, this happens for exampl
36 unloaded or a workqueue is destroyed.
37
38 State
39 -----
40
41 The validator tracks lock-class usage history
42 (4 usages * n STATEs + 1) categories:
43
44 where the 4 usages can be:
45
46 - 'ever held in STATE context'
47 - 'ever held as readlock in STATE context'
48 - 'ever held with STATE enabled'
49 - 'ever held as readlock with STATE enabled'
50
51 where the n STATEs are coded in kernel/locking
52 now they include:
53
54 - hardirq
55 - softirq
56
57 where the last 1 category is:
58
59 - 'ever used'
60
61 When locking rules are violated, these usage b
62 locking error messages, inside curlies, with a
63 A contrived example::
64
65 modprobe/2287 is trying to acquire lock:
66 (&sio_locks[i].lock){-.-.}, at: [<c02867fd
67
68 but task is already holding lock:
69 (&sio_locks[i].lock){-.-.}, at: [<c02867fd
70
71
72 For a given lock, the bit positions from left
73 of the lock and readlock (if exists), for each
74 above respectively, and the character displaye
75 indicates:
76
77 === ======================================
78 '.' acquired while irqs disabled and not i
79 '-' acquired in irq context
80 '+' acquired with irqs enabled
81 '?' acquired in irq context with irqs enab
82 === ======================================
83
84 The bits are illustrated with an example::
85
86 (&sio_locks[i].lock){-.-.}, at: [<c02867fd
87 ||||
88 ||| \-> softirq disab
89 || \--> acquired in s
90 | \---> hardirq disab
91 \----> acquired in h
92
93
94 For a given STATE, whether the lock is ever ac
95 context and whether that STATE is enabled yiel
96 shown in the table below. The bit character is
97 exact case is for the lock as of the reporting
98
99 +--------------+-------------+--------------
100 | | irq enabled | irq disabled
101 +--------------+-------------+--------------
102 | ever in irq | '?' | '-'
103 +--------------+-------------+--------------
104 | never in irq | '+' | '.'
105 +--------------+-------------+--------------
106
107 The character '-' suggests irq is disabled bec
108 character '?' would have been shown instead. S
109 applied for '+' too.
110
111 Unused locks (e.g., mutexes) cannot be part of
112
113
114 Single-lock state rules:
115 ------------------------
116
117 A lock is irq-safe means it was ever used in a
118 is irq-unsafe means it was ever acquired with
119
120 A softirq-unsafe lock-class is automatically h
121 following states must be exclusive: only one o
122 for any lock-class based on its usage::
123
124 <hardirq-safe> or <hardirq-unsafe>
125 <softirq-safe> or <softirq-unsafe>
126
127 This is because if a lock can be used in irq c
128 cannot be ever acquired with irq enabled (irq-
129 deadlock may happen. For example, in the scena
130 was acquired but before released, if the conte
131 lock will be attempted to acquire twice, which
132 referred to as lock recursion deadlock.
133
134 The validator detects and reports lock usage t
135 single-lock state rules.
136
137 Multi-lock dependency rules:
138 ----------------------------
139
140 The same lock-class must not be acquired twice
141 to lock recursion deadlocks.
142
143 Furthermore, two locks can not be taken in inv
144
145 <L1> -> <L2>
146 <L2> -> <L1>
147
148 because this could lead to a deadlock - referr
149 deadlock - as attempts to acquire the two lock
150 could lead to the two contexts waiting for eac
151 validator will find such dependency circle in
152 i.e., there can be any other locking sequence
153 operations; the validator will still find whet
154 acquired in a circular fashion.
155
156 Furthermore, the following usage based lock de
157 between any two lock-classes::
158
159 <hardirq-safe> -> <hardirq-unsafe>
160 <softirq-safe> -> <softirq-unsafe>
161
162 The first rule comes from the fact that a hard
163 taken by a hardirq context, interrupting a har
164 thus could result in a lock inversion deadlock
165 lock could be taken by an softirq context, int
166 lock.
167
168 The above rules are enforced for any locking s
169 kernel: when acquiring a new lock, the validat
170 any rule violation between the new lock and an
171
172 When a lock-class changes its state, the follo
173 dependency rules are enforced:
174
175 - if a new hardirq-safe lock is discovered, we
176 took any hardirq-unsafe lock in the past.
177
178 - if a new softirq-safe lock is discovered, we
179 any softirq-unsafe lock in the past.
180
181 - if a new hardirq-unsafe lock is discovered,
182 hardirq-safe lock took it in the past.
183
184 - if a new softirq-unsafe lock is discovered,
185 softirq-safe lock took it in the past.
186
187 (Again, we do these checks too on the basis th
188 could interrupt _any_ of the irq-unsafe or har
189 could lead to a lock inversion deadlock - even
190 not trigger in practice yet.)
191
192 Exception: Nested data dependencies leading to
193 ----------------------------------------------
194
195 There are a few cases where the Linux kernel a
196 instance of the same lock-class. Such cases ty
197 is some sort of hierarchy within objects of th
198 cases there is an inherent "natural" ordering
199 (defined by the properties of the hierarchy),
200 locks in this fixed order on each of the objec
201
202 An example of such an object hierarchy that re
203 is that of a "whole disk" block-dev object and
204 object; the partition is "part of" the whole d
205 always takes the whole disk lock as a higher l
206 lock, the lock ordering is fully correct. The
207 automatically detect this natural ordering, as
208 the ordering is not static.
209
210 In order to teach the validator about this cor
211 versions of the various locking primitives wer
212 specify a "nesting level". An example call, fo
213 looks like this::
214
215 enum bdev_bd_mutex_lock_class
216 {
217 BD_MUTEX_NORMAL,
218 BD_MUTEX_WHOLE,
219 BD_MUTEX_PARTITION
220 };
221
222 mutex_lock_nested(&bdev->bd_contains->bd_mut
223
224 In this case the locking is done on a bdev obj
225 partition.
226
227 The validator treats a lock that is taken in s
228 separate (sub)class for the purposes of valida
229
230 Note: When changing code to use the _nested()
231 check really thoroughly that the hierarchy is
232 you can get false positives or false negatives
233
234 Annotations
235 -----------
236
237 Two constructs can be used to annotate and che
238 must be held: lockdep_assert_held*(&lock) and
239
240 As the name suggests, lockdep_assert_held* fam
241 particular lock is held at a certain time (and
242 This annotation is largely used all over the k
243 core.c::
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 u
254
255 The other family of macros is lockdep_*pin_loc
256 used for rq->lock ATM. Despite their limited a
257 generate a WARN() if the lock of interest is "
258 out to be especially helpful to debug code wit
259 layer assumes a lock remains taken, but a lowe
260 and reacquire the lock ("unwittingly" introduc
261 returns a 'struct pin_cookie' that is then use
262 that nobody tampered with the lock, e.g. kerne
263
264 static inline void rq_pin_lock(struct rq *rq
265 {
266 rf->cookie = lockdep_pin_lock(&rq->loc
267 [...]
268 }
269
270 static inline void rq_unpin_lock(struct rq *
271 {
272 [...]
273 lockdep_unpin_lock(&rq->lock, rf->cook
274 }
275
276 While comments about locking requirements migh
277 the runtime checks performed by annotations ar
278 locking problems and they carry the same level
279 code. Always prefer annotations when in doubt
280
281 Proof of 100% correctness:
282 --------------------------
283
284 The validator achieves perfect, mathematical '
285 correctness) in the sense that for every simpl
286 locking sequence that occurred at least once d
287 kernel, the validator proves it with a 100% ce
288 combination and timing of these locking sequen
289 lock related deadlock. [1]_
290
291 I.e. complex multi-CPU and multi-task locking
292 occur in practice to prove a deadlock: only th
293 locking chains have to occur at least once (an
294 task/context) for the validator to be able to
295 example, complex deadlocks that would normally
296 a very unlikely constellation of tasks, irq-co
297 occur, can be detected on a plain, lightly loa
298 well!)
299
300 This radically decreases the complexity of loc
301 kernel: what has to be done during QA is to tr
302 single-task locking dependencies in the kernel
303 once, to prove locking correctness - instead o
304 possible combination of locking interaction be
305 every possible hardirq and softirq nesting sce
306 to do in practice).
307
308 .. [1]
309
310 assuming that the validator itself is 100%
311 part of the system corrupts the state of t
312 We also assume that all NMI/SMM paths [whi
313 even hardirq-disabled codepaths] are corre
314 with the validator. We also assume that th
315 value is unique for every lock-chain in th
316 recursion must not be higher than 20.
317
318 Performance:
319 ------------
320
321 The above rules require **massive** amounts of
322 that for every lock taken and for every irqs-e
323 render the system practically unusably slow. T
324 is O(N^2), so even with just a few hundred loc
325 tens of thousands of checks for every event.
326
327 This problem is solved by checking any given '
328 sequence of locks taken after each other) only
329 held locks is maintained, and a lightweight 64
330 calculated, which hash is unique for every loc
331 when the chain is validated for the first time
332 table, which hash-table can be checked in a lo
333 locking chain occurs again later on, the hash
334 don't have to validate the chain again.
335
336 Troubleshooting:
337 ----------------
338
339 The validator tracks a maximum of MAX_LOCKDEP_
340 Exceeding this number will trigger the followi
341
342 (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP
343
344 By default, MAX_LOCKDEP_KEYS is currently set
345 desktop systems have less than 1,000 lock clas
346 normally results from lock-class leakage or fa
347 initialize locks. These two problems are illu
348
349 1. Repeated module loading and unloading
350 will result in lock-class leakage. Th
351 load of the module will create a new s
352 that module's locks, but module unload
353 classes (see below discussion of reuse
354 Therefore, if that module is loaded an
355 the number of lock classes will eventu
356
357 2. Using structures such as arrays that h
358 locks that are not explicitly initiali
359 a hash table with 8192 buckets where e
360 spinlock_t will consume 8192 lock clas
361 is explicitly initialized at runtime,
362 run-time spin_lock_init() as opposed t
363 such as __SPIN_LOCK_UNLOCKED(). Failu
364 the per-bucket spinlocks would guarant
365 In contrast, a loop that called spin_l
366 would place all 8192 locks into a sing
367
368 The moral of this story is that you sh
369 initialize your locks.
370
371 One might argue that the validator should be m
372 lock classes to be reused. However, if you ar
373 argument, first review the code and think thro
374 be required, keeping in mind that the lock cla
375 likely to be linked into the lock-dependency g
376 be harder to do than to say.
377
378 Of course, if you do run out of lock classes,
379 to find the offending lock classes. First, th
380 you the number of lock classes currently in us
381
382 grep "lock-classes" /proc/lockdep_stat
383
384 This command produces the following output on
385
386 lock-classes:
387
388 If the number allocated (748 above) increases
389 then there is likely a leak. The following co
390 identify the leaking lock classes::
391
392 grep "BD" /proc/lockdep
393
394 Run the command and save the output, then comp
395 a later run of this command to identify the le
396 can also help you find situations where runtim
397 been omitted.
398
399 Recursive read locks:
400 ---------------------
401 The whole of the rest document tries to prove
402 to deadlock possibility.
403
404 There are three types of lockers: writers (i.e
405 spin_lock() or write_lock()), non-recursive re
406 down_read()) and recursive readers (recursive
407 And we use the following notations of those lo
408
409 W or E: stands for writers (exclusive
410 r: stands for non-recursive reade
411 R: stands for recursive readers.
412 S: stands for all readers (non-re
413 N: stands for writers and non-rec
414
415 Obviously, N is "r or W" and S is "r or R".
416
417 Recursive readers, as their name indicates, ar
418 even inside the critical section of another re
419 in other words, allowing nested read-side crit
420
421 While non-recursive readers will cause a self
422 the critical section of another reader of the
423
424 The difference between recursive readers and n
425 recursive readers get blocked only by a write
426 readers could get blocked by a write lock *wai
427 example::
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 recu
436 read_lock() first. And when task B tries to ac
437 and become a waiter for writer on X. Now if re
438 task A will make progress, because writer wait
439 and there is no deadlock. However, if read_loc
440 it will get blocked by writer waiter B, and ca
441
442 Block conditions on readers/writers of the sam
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 a
449 4. And readers (recursive or not) don't b
450 may block non-recursive readers (becau
451 writer waiters)
452
453 Block condition matrix, Y means the row blocks
454
455 +---+---+---+---+
456 | | W | r | R |
457 +---+---+---+---+
458 | W | Y | Y | Y |
459 +---+---+---+---+
460 | r | Y | Y | N |
461 +---+---+---+---+
462 | R | Y | Y | N |
463 +---+---+---+---+
464
465 (W: writers, r: non-recursive readers,
466
467
468 acquired recursively. Unlike non-recursive rea
469 only get blocked by current write lock *holder
470 *waiters*, for example::
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
481 the lock X, the second read_lock() doesn't nee
482 read lock. However if the read_lock() is non-r
483 case is a deadlock, because even if the write_
484 lock, but it can block the second read_lock()
485
486 Note that a lock can be a write lock (exclusiv
487 lock (non-recursive shared lock) or a recursiv
488 lock), depending on the lock operations used t
489 the value of the 'read' parameter for lock_acq
490 lock instance has three types of acquisition d
491 functions: exclusive, non-recursive read, and
492
493 To be concise, we call that write locks and no
494 "non-recursive" locks and recursive read locks
495
496 Recursive locks don't block each other, while
497 even true for two non-recursive read locks). A
498 corresponding recursive lock, and vice versa.
499
500 A deadlock case with recursive locks involved
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()
510 A to read_unlock() X.
511
512 Dependency types and strong dependency paths:
513 ---------------------------------------------
514 Lock dependencies record the orders of the acq
515 because there are 3 types for lockers, there a
516 dependencies, but we can show that 4 types of
517 deadlock detection.
518
519 For each lock dependency::
520
521 L1 -> L2
522
523 , which means lockdep has seen L1 held before
524 And in deadlock detection, we care whether we
525 IOW, whether there is a locker L3 that L1 bloc
526 we only care about 1) what L1 blocks and 2) wh
527 recursive readers and non-recursive readers fo
528 we can combine writers and non-recursive reade
529 same types).
530
531 With the above combination for simplification,
532 in the lockdep graph:
533
534 1) -(ER)->:
535 exclusive writer to recursive read
536 X -> Y and X is a writer and Y is
537
538 2) -(EN)->:
539 exclusive writer to non-recursive
540 X -> Y and X is a writer and Y is
541
542 3) -(SR)->:
543 shared reader to recursive reader
544 X -> Y and X is a reader (recursiv
545
546 4) -(SN)->:
547 shared reader to non-recursive loc
548 X -> Y and X is a reader (recursiv
549 non-recursive reader.
550
551 Note that given two locks, they may have multi
552 for example::
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
566
567 We use -(xN)-> to represent edges that are eit
568 similar for -(Ex)->, -(xR)-> and -(Sx)->
569
570 A "path" is a series of conjunct dependency ed
571 "strong" path, which indicates the strong depe
572 in the path, as the path that doesn't have two
573 -(xR)-> and -(Sx)->. In other words, a "strong
574 walking to another through the lock dependenci
575 path (where X, Y, Z are locks), and the walk f
576 -(ER)-> dependency, the walk from Y to Z must
577 -(SR)-> dependency.
578
579 We will see why the path is called "strong" in
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 stron
589 combination of locking sequences that causes d
590 sufficient for deadlock detection.
591
592 Lemma 2:
593
594 If there is no closed strong path (i.e. strong
595 combination of locking sequences that could ca
596 circles are necessary for deadlock detection.
597
598 With these two Lemmas, we can easily say a clo
599 and necessary for deadlocks, therefore a close
600 deadlock possibility. As a closed strong path
601 could cause deadlocks, so we call it "strong",
602 circles that won't cause deadlocks.
603
604 Proof for sufficiency (Lemma 1):
605
606 Let's say we have a strong circle::
607
608 L1 -> L2 ... -> Ln -> L1
609
610 , which means we have dependencies::
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
619
620 Firstly let's make one CPU/task get the L1 in
621 the L2 in L2 -> L3, and so on. After this, all
622 held by different CPU/tasks.
623
624 And then because we have L1 -> L2, so the hold
625 in L1 -> L2, however since L2 is already held
626 L2 and L2 -> L3 are not -(xR)-> and -(Sx)-> (t
627 means either L2 in L1 -> L2 is a non-recursive
628 the L2 in L2 -> L3, is writer (blocking anyone
629 cannot get L2, it has to wait L2's holder to r
630
631 Moreover, we can have a similar conclusion for
632 holder to release, and so on. We now can prove
633 Lx+1's holder to release, and note that Ln+1 i
634 waiting scenario and nobody can get progress,
635
636 Proof for necessary (Lemma 2):
637
638 Lemma 2 is equivalent to: If there is a deadlo
639 strong circle in the dependency graph.
640
641 According to Wikipedia[1], if there is a deadl
642 waiting scenario, means there are N CPU/tasks,
643 a lock held by P2, and P2 is waiting for a loc
644 for a lock held by P1. Let's name the lock Px
645 for L1 and holding Ln, so we will have Ln -> L
646 we have L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln in
647 have a circle::
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 L
654 the dependency Lx -> Lx+1, and since Px is wai
655 so it's impossible that Lx on Px+1 is a reader
656 reader, because readers (no matter recursive o
657 readers, therefore Lx-1 -> Lx and Lx -> Lx+1 c
658 and this is true for any lock in the circle, t
659
660 References:
661 -----------
662 [1]: https://en.wikipedia.org/wiki/Deadlock
663 [2]: Shibu, K. (2009). Intro To Embedded Syste
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.