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