Lines Matching +full:lock +full:- +full:- +full:- +full:-
8 Lock-class
9 ----------
15 tens of thousands of) instantiations. For example a lock in the inode
17 lock class.
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
26 continuing effort to prove lock usages and dependencies are correct or
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
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
39 -----
41 The validator tracks lock-class usage history and divides the usage into
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'
54 - hardirq
55 - softirq
59 - 'ever used' [ == !unused ]
65 modprobe/2287 is trying to acquire lock:
66 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
68 but task is already holding lock:
69 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
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
79 '-' acquired in irq context
86 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
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
94 For a given STATE, whether the lock is ever acquired in that STATE
97 exact case is for the lock as of the reporting time.
99 +--------------+-------------+--------------+
101 +--------------+-------------+--------------+
102 | ever in irq | '?' | '-' |
103 +--------------+-------------+--------------+
105 +--------------+-------------+--------------+
107 The character '-' suggests irq is disabled because if otherwise the
114 Single-lock state rules:
115 ------------------------
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.
120 A softirq-unsafe lock-class is automatically hardirq-unsafe as well. The
122 for any lock-class based on its usage::
124 <hardirq-safe> or <hardirq-unsafe>
125 <softirq-safe> or <softirq-unsafe>
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
131 lock will be attempted to acquire twice, which creates a deadlock,
132 referred to as lock recursion deadlock.
134 The validator detects and reports lock usage that violates these
135 single-lock state rules.
137 Multi-lock dependency rules:
138 ----------------------------
140 The same lock-class must not be acquired twice, because this could lead
141 to lock recursion deadlocks.
145 <L1> -> <L2>
146 <L2> -> <L1>
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
152 i.e., there can be any other locking sequence between the acquire-lock
156 Furthermore, the following usage based lock dependencies are not allowed
157 between any two lock-classes::
159 <hardirq-safe> -> <hardirq-unsafe>
160 <softirq-safe> -> <softirq-unsafe>
162 The first rule comes from the fact that a hardirq-safe lock could be
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.
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.
172 When a lock-class changes its state, the following aspects of the above
175 - if a new hardirq-safe lock is discovered, we check whether it
176 took any hardirq-unsafe lock in the past.
178 - if a new softirq-safe lock is discovered, we check whether it took
179 any softirq-unsafe lock in the past.
181 - if a new hardirq-unsafe lock is discovered, we check whether any
182 hardirq-safe lock took it in the past.
184 - if a new softirq-unsafe lock is discovered, we check whether any
185 softirq-safe lock took it in the past.
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
193 -------------------------------------------------------------
196 instance of the same lock-class. Such cases typically happen when there
203 is that of a "whole disk" block-dev object and a "partition" block-dev
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
222 mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);
227 The validator treats a lock that is taken in such a nested fashion as a
235 -----------
238 must be held: lockdep_assert_held*(&lock) and lockdep_*pin_lock(&lock).
241 particular lock is held at a certain time (and generate a WARN() otherwise).
249 lockdep_assert_held(&rq->lock);
253 where holding rq->lock is required to safely update a rq's clock.
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
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()
262 that nobody tampered with the lock, e.g. kernel/sched/sched.h::
266 rf->cookie = lockdep_pin_lock(&rq->lock);
273 lockdep_unpin_lock(&rq->lock, rf->cookie);
282 --------------------------
285 correctness) in the sense that for every simple, standalone single-task
289 lock related deadlock. [1]_
291 I.e. complex multi-CPU and multi-task locking scenarios do not have to
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
302 single-task locking dependencies in the kernel as possible, at least
303 once, to prove locking correctness - instead of having to trigger every
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
319 ------------
322 that for every lock taken and for every irqs-enable event, it would
324 is O(N^2), so even with just a few hundred lock-classes we'd have to do
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,
332 table, which hash-table can be checked in a lockfree manner. If the
337 ----------------
339 The validator tracks a maximum of MAX_LOCKDEP_KEYS number of lock classes.
345 desktop systems have less than 1,000 lock classes, so this warning
346 normally results from lock-class leakage or failure to properly
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
353 classes (see below discussion of reuse of lock classes for why).
355 the number of lock classes will eventually reach the maximum.
360 spinlock_t will consume 8192 lock classes -unless- each spinlock
362 run-time spin_lock_init() as opposed to compile-time initializers
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.
372 lock classes to be reused. However, if you are tempted to make this
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
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
380 you the number of lock classes currently in use along with the maximum::
382 grep "lock-classes" /proc/lockdep_stats
386 lock-classes: 748 [max: 8191]
390 identify the leaking lock classes::
396 can also help you find situations where runtime lock initialization has
400 ---------------------
405 spin_lock() or write_lock()), non-recursive readers (i.e. shared lockers, like
410 r: stands for non-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.
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.
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.
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
426 readers could get blocked by a write lock *waiter*. Considering the follow
435 Task A gets the reader (no matter whether recursive or non-recursive) on X via
439 and there is no deadlock. However, if read_lock_2() is non-recursive readers,
442 Block conditions on readers/writers of the same lock instance:
443 --------------------------------------------------------------
448 3. Writers block both recursive readers and non-recursive readers.
450 may block non-recursive readers (because of the potential co-existing
455 +---+---+---+---+
457 +---+---+---+---+
459 +---+---+---+---+
461 +---+---+---+---+
463 +---+---+---+---+
465 (W: writers, r: non-recursive readers, R: recursive readers)
468 acquired recursively. Unlike non-recursive read locks, recursive read locks
469 only get blocked by current write lock *holders* other than write lock
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
484 lock, but it can block the second read_lock() in TASK A.
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,
490 lock instance has three types of acquisition depending on the acquisition
491 functions: exclusive, non-recursive read, and recursive read.
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.
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.
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
519 For each lock dependency::
521 L1 -> L2
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
534 1) -(ER)->:
535 exclusive writer to recursive reader dependency, "X -(ER)-> Y" means
536 X -> Y and X is a writer and Y is a recursive reader.
538 2) -(EN)->:
539 exclusive writer to non-recursive locker dependency, "X -(EN)-> Y" means
540 X -> Y and X is a writer and Y is either a writer or non-recursive reader.
542 3) -(SR)->:
543 shared reader to recursive reader dependency, "X -(SR)-> Y" means
544 X -> Y and X is a reader (recursive or not) and Y is a recursive reader.
546 4) -(SN)->:
547 shared reader to non-recursive locker dependency, "X -(SN)-> Y" means
548 X -> Y and X is a reader (recursive or not) and Y is either a writer or
549 non-recursive reader.
565 , we have both X -(SN)-> Y and X -(EN)-> Y in the dependency graph.
567 We use -(xN)-> to represent edges that are either -(EN)-> or -(SN)->, the
568 similar for -(Ex)->, -(xR)-> and -(Sx)->
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.
582 ----------------------------------
608 L1 -> L2 ... -> Ln -> L1
612 L1 -> L2
613 L2 -> L3
615 Ln-1 -> Ln
616 Ln -> L1
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
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
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
649 Ln -> L1 -> L2 -> ... -> Ln
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,
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.
661 -----------
663 [2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill