Lines Matching +full:non +full:- +full:exclusive
8 Lock-class
9 ----------
19 The validator tracks the 'usage state' of lock-classes, and it tracks
20 the dependencies between different lock-classes. Lock usage indicates
22 dependency can be understood as lock order, where L1 -> L2 suggests that
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
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 ]
66 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
69 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
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
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
121 following states must be exclusive: only one of them is allowed to be set
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
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
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
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
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
222 mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);
235 -----------
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
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
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
332 table, which hash-table can be checked in a lockfree manner. If the
337 ----------------
346 normally results from lock-class leakage or failure to properly
350 will result in lock-class leakage. The issue here is that each
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.
375 likely to be linked into the lock-dependency graph. This turns out to
382 grep "lock-classes" /proc/lockdep_stats
386 lock-classes: 748 [max: 8191]
400 ---------------------
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
409 W or E: stands for writers (exclusive lockers).
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.
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
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
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,
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
482 read lock. However if the read_lock() is non-recursive read lock, then the above
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
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
513 ---------------------------------------------
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
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,
661 -----------
663 [2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill