]>
Commit | Line | Data |
---|---|---|
ef0758dd BP |
1 | Crossrelease |
2 | ============ | |
3 | ||
4 | Started by Byungchul Park <byungchul.park@lge.com> | |
5 | ||
6 | Contents: | |
7 | ||
8 | (*) Background | |
9 | ||
10 | - What causes deadlock | |
11 | - How lockdep works | |
12 | ||
13 | (*) Limitation | |
14 | ||
15 | - Limit lockdep | |
16 | - Pros from the limitation | |
17 | - Cons from the limitation | |
18 | - Relax the limitation | |
19 | ||
20 | (*) Crossrelease | |
21 | ||
22 | - Introduce crossrelease | |
23 | - Introduce commit | |
24 | ||
25 | (*) Implementation | |
26 | ||
27 | - Data structures | |
28 | - How crossrelease works | |
29 | ||
30 | (*) Optimizations | |
31 | ||
32 | - Avoid duplication | |
33 | - Lockless for hot paths | |
34 | ||
35 | (*) APPENDIX A: What lockdep does to work aggresively | |
36 | ||
37 | (*) APPENDIX B: How to avoid adding false dependencies | |
38 | ||
39 | ||
40 | ========== | |
41 | Background | |
42 | ========== | |
43 | ||
44 | What causes deadlock | |
45 | -------------------- | |
46 | ||
47 | A deadlock occurs when a context is waiting for an event to happen, | |
48 | which is impossible because another (or the) context who can trigger the | |
49 | event is also waiting for another (or the) event to happen, which is | |
50 | also impossible due to the same reason. | |
51 | ||
52 | For example: | |
53 | ||
54 | A context going to trigger event C is waiting for event A to happen. | |
55 | A context going to trigger event A is waiting for event B to happen. | |
56 | A context going to trigger event B is waiting for event C to happen. | |
57 | ||
58 | A deadlock occurs when these three wait operations run at the same time, | |
59 | because event C cannot be triggered if event A does not happen, which in | |
60 | turn cannot be triggered if event B does not happen, which in turn | |
61 | cannot be triggered if event C does not happen. After all, no event can | |
62 | be triggered since any of them never meets its condition to wake up. | |
63 | ||
64 | A dependency might exist between two waiters and a deadlock might happen | |
65 | due to an incorrect releationship between dependencies. Thus, we must | |
66 | define what a dependency is first. A dependency exists between them if: | |
67 | ||
68 | 1. There are two waiters waiting for each event at a given time. | |
69 | 2. The only way to wake up each waiter is to trigger its event. | |
70 | 3. Whether one can be woken up depends on whether the other can. | |
71 | ||
72 | Each wait in the example creates its dependency like: | |
73 | ||
74 | Event C depends on event A. | |
75 | Event A depends on event B. | |
76 | Event B depends on event C. | |
77 | ||
78 | NOTE: Precisely speaking, a dependency is one between whether a | |
79 | waiter for an event can be woken up and whether another waiter for | |
80 | another event can be woken up. However from now on, we will describe | |
81 | a dependency as if it's one between an event and another event for | |
82 | simplicity. | |
83 | ||
84 | And they form circular dependencies like: | |
85 | ||
86 | -> C -> A -> B - | |
87 | / \ | |
88 | \ / | |
89 | ---------------- | |
90 | ||
91 | where 'A -> B' means that event A depends on event B. | |
92 | ||
93 | Such circular dependencies lead to a deadlock since no waiter can meet | |
94 | its condition to wake up as described. | |
95 | ||
96 | CONCLUSION | |
97 | ||
98 | Circular dependencies cause a deadlock. | |
99 | ||
100 | ||
101 | How lockdep works | |
102 | ----------------- | |
103 | ||
104 | Lockdep tries to detect a deadlock by checking dependencies created by | |
105 | lock operations, acquire and release. Waiting for a lock corresponds to | |
106 | waiting for an event, and releasing a lock corresponds to triggering an | |
107 | event in the previous section. | |
108 | ||
109 | In short, lockdep does: | |
110 | ||
111 | 1. Detect a new dependency. | |
112 | 2. Add the dependency into a global graph. | |
113 | 3. Check if that makes dependencies circular. | |
114 | 4. Report a deadlock or its possibility if so. | |
115 | ||
116 | For example, consider a graph built by lockdep that looks like: | |
117 | ||
118 | A -> B - | |
119 | \ | |
120 | -> E | |
121 | / | |
122 | C -> D - | |
123 | ||
124 | where A, B,..., E are different lock classes. | |
125 | ||
126 | Lockdep will add a dependency into the graph on detection of a new | |
127 | dependency. For example, it will add a dependency 'E -> C' when a new | |
128 | dependency between lock E and lock C is detected. Then the graph will be: | |
129 | ||
130 | A -> B - | |
131 | \ | |
132 | -> E - | |
133 | / \ | |
134 | -> C -> D - \ | |
135 | / / | |
136 | \ / | |
137 | ------------------ | |
138 | ||
139 | where A, B,..., E are different lock classes. | |
140 | ||
141 | This graph contains a subgraph which demonstrates circular dependencies: | |
142 | ||
143 | -> E - | |
144 | / \ | |
145 | -> C -> D - \ | |
146 | / / | |
147 | \ / | |
148 | ------------------ | |
149 | ||
150 | where C, D and E are different lock classes. | |
151 | ||
152 | This is the condition under which a deadlock might occur. Lockdep | |
153 | reports it on detection after adding a new dependency. This is the way | |
154 | how lockdep works. | |
155 | ||
156 | CONCLUSION | |
157 | ||
158 | Lockdep detects a deadlock or its possibility by checking if circular | |
159 | dependencies were created after adding each new dependency. | |
160 | ||
161 | ||
162 | ========== | |
163 | Limitation | |
164 | ========== | |
165 | ||
166 | Limit lockdep | |
167 | ------------- | |
168 | ||
169 | Limiting lockdep to work on only typical locks e.g. spin locks and | |
170 | mutexes, which are released within the acquire context, the | |
171 | implementation becomes simple but its capacity for detection becomes | |
172 | limited. Let's check pros and cons in next section. | |
173 | ||
174 | ||
175 | Pros from the limitation | |
176 | ------------------------ | |
177 | ||
178 | Given the limitation, when acquiring a lock, locks in a held_locks | |
179 | cannot be released if the context cannot acquire it so has to wait to | |
180 | acquire it, which means all waiters for the locks in the held_locks are | |
181 | stuck. It's an exact case to create dependencies between each lock in | |
182 | the held_locks and the lock to acquire. | |
183 | ||
184 | For example: | |
185 | ||
186 | CONTEXT X | |
187 | --------- | |
188 | acquire A | |
189 | acquire B /* Add a dependency 'A -> B' */ | |
190 | release B | |
191 | release A | |
192 | ||
193 | where A and B are different lock classes. | |
194 | ||
195 | When acquiring lock A, the held_locks of CONTEXT X is empty thus no | |
196 | dependency is added. But when acquiring lock B, lockdep detects and adds | |
197 | a new dependency 'A -> B' between lock A in the held_locks and lock B. | |
198 | They can be simply added whenever acquiring each lock. | |
199 | ||
200 | And data required by lockdep exists in a local structure, held_locks | |
201 | embedded in task_struct. Forcing to access the data within the context, | |
202 | lockdep can avoid racy problems without explicit locks while handling | |
203 | the local data. | |
204 | ||
205 | Lastly, lockdep only needs to keep locks currently being held, to build | |
206 | a dependency graph. However, relaxing the limitation, it needs to keep | |
207 | even locks already released, because a decision whether they created | |
208 | dependencies might be long-deferred. | |
209 | ||
210 | To sum up, we can expect several advantages from the limitation: | |
211 | ||
212 | 1. Lockdep can easily identify a dependency when acquiring a lock. | |
213 | 2. Races are avoidable while accessing local locks in a held_locks. | |
214 | 3. Lockdep only needs to keep locks currently being held. | |
215 | ||
216 | CONCLUSION | |
217 | ||
218 | Given the limitation, the implementation becomes simple and efficient. | |
219 | ||
220 | ||
221 | Cons from the limitation | |
222 | ------------------------ | |
223 | ||
224 | Given the limitation, lockdep is applicable only to typical locks. For | |
225 | example, page locks for page access or completions for synchronization | |
226 | cannot work with lockdep. | |
227 | ||
228 | Can we detect deadlocks below, under the limitation? | |
229 | ||
230 | Example 1: | |
231 | ||
232 | CONTEXT X CONTEXT Y CONTEXT Z | |
233 | --------- --------- ---------- | |
234 | mutex_lock A | |
235 | lock_page B | |
236 | lock_page B | |
237 | mutex_lock A /* DEADLOCK */ | |
238 | unlock_page B held by X | |
239 | unlock_page B | |
240 | mutex_unlock A | |
241 | mutex_unlock A | |
242 | ||
243 | where A and B are different lock classes. | |
244 | ||
245 | No, we cannot. | |
246 | ||
247 | Example 2: | |
248 | ||
249 | CONTEXT X CONTEXT Y | |
250 | --------- --------- | |
251 | mutex_lock A | |
252 | mutex_lock A | |
253 | wait_for_complete B /* DEADLOCK */ | |
254 | complete B | |
255 | mutex_unlock A | |
256 | mutex_unlock A | |
257 | ||
258 | where A is a lock class and B is a completion variable. | |
259 | ||
260 | No, we cannot. | |
261 | ||
262 | CONCLUSION | |
263 | ||
264 | Given the limitation, lockdep cannot detect a deadlock or its | |
265 | possibility caused by page locks or completions. | |
266 | ||
267 | ||
268 | Relax the limitation | |
269 | -------------------- | |
270 | ||
271 | Under the limitation, things to create dependencies are limited to | |
272 | typical locks. However, synchronization primitives like page locks and | |
273 | completions, which are allowed to be released in any context, also | |
274 | create dependencies and can cause a deadlock. So lockdep should track | |
275 | these locks to do a better job. We have to relax the limitation for | |
276 | these locks to work with lockdep. | |
277 | ||
278 | Detecting dependencies is very important for lockdep to work because | |
279 | adding a dependency means adding an opportunity to check whether it | |
280 | causes a deadlock. The more lockdep adds dependencies, the more it | |
281 | thoroughly works. Thus Lockdep has to do its best to detect and add as | |
282 | many true dependencies into a graph as possible. | |
283 | ||
284 | For example, considering only typical locks, lockdep builds a graph like: | |
285 | ||
286 | A -> B - | |
287 | \ | |
288 | -> E | |
289 | / | |
290 | C -> D - | |
291 | ||
292 | where A, B,..., E are different lock classes. | |
293 | ||
294 | On the other hand, under the relaxation, additional dependencies might | |
295 | be created and added. Assuming additional 'FX -> C' and 'E -> GX' are | |
296 | added thanks to the relaxation, the graph will be: | |
297 | ||
298 | A -> B - | |
299 | \ | |
300 | -> E -> GX | |
301 | / | |
302 | FX -> C -> D - | |
303 | ||
304 | where A, B,..., E, FX and GX are different lock classes, and a suffix | |
305 | 'X' is added on non-typical locks. | |
306 | ||
307 | The latter graph gives us more chances to check circular dependencies | |
308 | than the former. However, it might suffer performance degradation since | |
309 | relaxing the limitation, with which design and implementation of lockdep | |
310 | can be efficient, might introduce inefficiency inevitably. So lockdep | |
311 | should provide two options, strong detection and efficient detection. | |
312 | ||
313 | Choosing efficient detection: | |
314 | ||
315 | Lockdep works with only locks restricted to be released within the | |
316 | acquire context. However, lockdep works efficiently. | |
317 | ||
318 | Choosing strong detection: | |
319 | ||
320 | Lockdep works with all synchronization primitives. However, lockdep | |
321 | suffers performance degradation. | |
322 | ||
323 | CONCLUSION | |
324 | ||
325 | Relaxing the limitation, lockdep can add additional dependencies giving | |
326 | additional opportunities to check circular dependencies. | |
327 | ||
328 | ||
329 | ============ | |
330 | Crossrelease | |
331 | ============ | |
332 | ||
333 | Introduce crossrelease | |
334 | ---------------------- | |
335 | ||
336 | In order to allow lockdep to handle additional dependencies by what | |
337 | might be released in any context, namely 'crosslock', we have to be able | |
338 | to identify those created by crosslocks. The proposed 'crossrelease' | |
339 | feature provoides a way to do that. | |
340 | ||
341 | Crossrelease feature has to do: | |
342 | ||
343 | 1. Identify dependencies created by crosslocks. | |
344 | 2. Add the dependencies into a dependency graph. | |
345 | ||
346 | That's all. Once a meaningful dependency is added into graph, then | |
347 | lockdep would work with the graph as it did. The most important thing | |
348 | crossrelease feature has to do is to correctly identify and add true | |
349 | dependencies into the global graph. | |
350 | ||
351 | A dependency e.g. 'A -> B' can be identified only in the A's release | |
352 | context because a decision required to identify the dependency can be | |
353 | made only in the release context. That is to decide whether A can be | |
354 | released so that a waiter for A can be woken up. It cannot be made in | |
355 | other than the A's release context. | |
356 | ||
357 | It's no matter for typical locks because each acquire context is same as | |
358 | its release context, thus lockdep can decide whether a lock can be | |
359 | released in the acquire context. However for crosslocks, lockdep cannot | |
360 | make the decision in the acquire context but has to wait until the | |
361 | release context is identified. | |
362 | ||
363 | Therefore, deadlocks by crosslocks cannot be detected just when it | |
364 | happens, because those cannot be identified until the crosslocks are | |
365 | released. However, deadlock possibilities can be detected and it's very | |
366 | worth. See 'APPENDIX A' section to check why. | |
367 | ||
368 | CONCLUSION | |
369 | ||
370 | Using crossrelease feature, lockdep can work with what might be released | |
371 | in any context, namely crosslock. | |
372 | ||
373 | ||
374 | Introduce commit | |
375 | ---------------- | |
376 | ||
377 | Since crossrelease defers the work adding true dependencies of | |
378 | crosslocks until they are actually released, crossrelease has to queue | |
379 | all acquisitions which might create dependencies with the crosslocks. | |
380 | Then it identifies dependencies using the queued data in batches at a | |
381 | proper time. We call it 'commit'. | |
382 | ||
383 | There are four types of dependencies: | |
384 | ||
385 | 1. TT type: 'typical lock A -> typical lock B' | |
386 | ||
387 | Just when acquiring B, lockdep can see it's in the A's release | |
388 | context. So the dependency between A and B can be identified | |
389 | immediately. Commit is unnecessary. | |
390 | ||
391 | 2. TC type: 'typical lock A -> crosslock BX' | |
392 | ||
393 | Just when acquiring BX, lockdep can see it's in the A's release | |
394 | context. So the dependency between A and BX can be identified | |
395 | immediately. Commit is unnecessary, too. | |
396 | ||
397 | 3. CT type: 'crosslock AX -> typical lock B' | |
398 | ||
399 | When acquiring B, lockdep cannot identify the dependency because | |
400 | there's no way to know if it's in the AX's release context. It has | |
401 | to wait until the decision can be made. Commit is necessary. | |
402 | ||
403 | 4. CC type: 'crosslock AX -> crosslock BX' | |
404 | ||
405 | When acquiring BX, lockdep cannot identify the dependency because | |
406 | there's no way to know if it's in the AX's release context. It has | |
407 | to wait until the decision can be made. Commit is necessary. | |
408 | But, handling CC type is not implemented yet. It's a future work. | |
409 | ||
410 | Lockdep can work without commit for typical locks, but commit step is | |
411 | necessary once crosslocks are involved. Introducing commit, lockdep | |
412 | performs three steps. What lockdep does in each step is: | |
413 | ||
414 | 1. Acquisition: For typical locks, lockdep does what it originally did | |
415 | and queues the lock so that CT type dependencies can be checked using | |
416 | it at the commit step. For crosslocks, it saves data which will be | |
417 | used at the commit step and increases a reference count for it. | |
418 | ||
419 | 2. Commit: No action is reauired for typical locks. For crosslocks, | |
420 | lockdep adds CT type dependencies using the data saved at the | |
421 | acquisition step. | |
422 | ||
423 | 3. Release: No changes are required for typical locks. When a crosslock | |
424 | is released, it decreases a reference count for it. | |
425 | ||
426 | CONCLUSION | |
427 | ||
428 | Crossrelease introduces commit step to handle dependencies of crosslocks | |
429 | in batches at a proper time. | |
430 | ||
431 | ||
432 | ============== | |
433 | Implementation | |
434 | ============== | |
435 | ||
436 | Data structures | |
437 | --------------- | |
438 | ||
439 | Crossrelease introduces two main data structures. | |
440 | ||
441 | 1. hist_lock | |
442 | ||
443 | This is an array embedded in task_struct, for keeping lock history so | |
444 | that dependencies can be added using them at the commit step. Since | |
445 | it's local data, it can be accessed locklessly in the owner context. | |
446 | The array is filled at the acquisition step and consumed at the | |
447 | commit step. And it's managed in circular manner. | |
448 | ||
449 | 2. cross_lock | |
450 | ||
451 | One per lockdep_map exists. This is for keeping data of crosslocks | |
452 | and used at the commit step. | |
453 | ||
454 | ||
455 | How crossrelease works | |
456 | ---------------------- | |
457 | ||
458 | It's the key of how crossrelease works, to defer necessary works to an | |
459 | appropriate point in time and perform in at once at the commit step. | |
460 | Let's take a look with examples step by step, starting from how lockdep | |
461 | works without crossrelease for typical locks. | |
462 | ||
463 | acquire A /* Push A onto held_locks */ | |
464 | acquire B /* Push B onto held_locks and add 'A -> B' */ | |
465 | acquire C /* Push C onto held_locks and add 'B -> C' */ | |
466 | release C /* Pop C from held_locks */ | |
467 | release B /* Pop B from held_locks */ | |
468 | release A /* Pop A from held_locks */ | |
469 | ||
470 | where A, B and C are different lock classes. | |
471 | ||
472 | NOTE: This document assumes that readers already understand how | |
473 | lockdep works without crossrelease thus omits details. But there's | |
474 | one thing to note. Lockdep pretends to pop a lock from held_locks | |
475 | when releasing it. But it's subtly different from the original pop | |
476 | operation because lockdep allows other than the top to be poped. | |
477 | ||
478 | In this case, lockdep adds 'the top of held_locks -> the lock to acquire' | |
479 | dependency every time acquiring a lock. | |
480 | ||
481 | After adding 'A -> B', a dependency graph will be: | |
482 | ||
483 | A -> B | |
484 | ||
485 | where A and B are different lock classes. | |
486 | ||
487 | And after adding 'B -> C', the graph will be: | |
488 | ||
489 | A -> B -> C | |
490 | ||
491 | where A, B and C are different lock classes. | |
492 | ||
493 | Let's performs commit step even for typical locks to add dependencies. | |
494 | Of course, commit step is not necessary for them, however, it would work | |
495 | well because this is a more general way. | |
496 | ||
497 | acquire A | |
498 | /* | |
499 | * Queue A into hist_locks | |
500 | * | |
501 | * In hist_locks: A | |
502 | * In graph: Empty | |
503 | */ | |
504 | ||
505 | acquire B | |
506 | /* | |
507 | * Queue B into hist_locks | |
508 | * | |
509 | * In hist_locks: A, B | |
510 | * In graph: Empty | |
511 | */ | |
512 | ||
513 | acquire C | |
514 | /* | |
515 | * Queue C into hist_locks | |
516 | * | |
517 | * In hist_locks: A, B, C | |
518 | * In graph: Empty | |
519 | */ | |
520 | ||
521 | commit C | |
522 | /* | |
523 | * Add 'C -> ?' | |
524 | * Answer the following to decide '?' | |
525 | * What has been queued since acquire C: Nothing | |
526 | * | |
527 | * In hist_locks: A, B, C | |
528 | * In graph: Empty | |
529 | */ | |
530 | ||
531 | release C | |
532 | ||
533 | commit B | |
534 | /* | |
535 | * Add 'B -> ?' | |
536 | * Answer the following to decide '?' | |
537 | * What has been queued since acquire B: C | |
538 | * | |
539 | * In hist_locks: A, B, C | |
540 | * In graph: 'B -> C' | |
541 | */ | |
542 | ||
543 | release B | |
544 | ||
545 | commit A | |
546 | /* | |
547 | * Add 'A -> ?' | |
548 | * Answer the following to decide '?' | |
549 | * What has been queued since acquire A: B, C | |
550 | * | |
551 | * In hist_locks: A, B, C | |
552 | * In graph: 'B -> C', 'A -> B', 'A -> C' | |
553 | */ | |
554 | ||
555 | release A | |
556 | ||
557 | where A, B and C are different lock classes. | |
558 | ||
559 | In this case, dependencies are added at the commit step as described. | |
560 | ||
561 | After commits for A, B and C, the graph will be: | |
562 | ||
563 | A -> B -> C | |
564 | ||
565 | where A, B and C are different lock classes. | |
566 | ||
567 | NOTE: A dependency 'A -> C' is optimized out. | |
568 | ||
569 | We can see the former graph built without commit step is same as the | |
570 | latter graph built using commit steps. Of course the former way leads to | |
571 | earlier finish for building the graph, which means we can detect a | |
572 | deadlock or its possibility sooner. So the former way would be prefered | |
573 | when possible. But we cannot avoid using the latter way for crosslocks. | |
574 | ||
575 | Let's look at how commit steps work for crosslocks. In this case, the | |
576 | commit step is performed only on crosslock AX as real. And it assumes | |
577 | that the AX release context is different from the AX acquire context. | |
578 | ||
579 | BX RELEASE CONTEXT BX ACQUIRE CONTEXT | |
580 | ------------------ ------------------ | |
581 | acquire A | |
582 | /* | |
583 | * Push A onto held_locks | |
584 | * Queue A into hist_locks | |
585 | * | |
586 | * In held_locks: A | |
587 | * In hist_locks: A | |
588 | * In graph: Empty | |
589 | */ | |
590 | ||
591 | acquire BX | |
592 | /* | |
593 | * Add 'the top of held_locks -> BX' | |
594 | * | |
595 | * In held_locks: A | |
596 | * In hist_locks: A | |
597 | * In graph: 'A -> BX' | |
598 | */ | |
599 | ||
600 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
601 | It must be guaranteed that the following operations are seen after | |
602 | acquiring BX globally. It can be done by things like barrier. | |
603 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
604 | ||
605 | acquire C | |
606 | /* | |
607 | * Push C onto held_locks | |
608 | * Queue C into hist_locks | |
609 | * | |
610 | * In held_locks: C | |
611 | * In hist_locks: C | |
612 | * In graph: 'A -> BX' | |
613 | */ | |
614 | ||
615 | release C | |
616 | /* | |
617 | * Pop C from held_locks | |
618 | * | |
619 | * In held_locks: Empty | |
620 | * In hist_locks: C | |
621 | * In graph: 'A -> BX' | |
622 | */ | |
623 | acquire D | |
624 | /* | |
625 | * Push D onto held_locks | |
626 | * Queue D into hist_locks | |
627 | * Add 'the top of held_locks -> D' | |
628 | * | |
629 | * In held_locks: A, D | |
630 | * In hist_locks: A, D | |
631 | * In graph: 'A -> BX', 'A -> D' | |
632 | */ | |
633 | acquire E | |
634 | /* | |
635 | * Push E onto held_locks | |
636 | * Queue E into hist_locks | |
637 | * | |
638 | * In held_locks: E | |
639 | * In hist_locks: C, E | |
640 | * In graph: 'A -> BX', 'A -> D' | |
641 | */ | |
642 | ||
643 | release E | |
644 | /* | |
645 | * Pop E from held_locks | |
646 | * | |
647 | * In held_locks: Empty | |
648 | * In hist_locks: D, E | |
649 | * In graph: 'A -> BX', 'A -> D' | |
650 | */ | |
651 | release D | |
652 | /* | |
653 | * Pop D from held_locks | |
654 | * | |
655 | * In held_locks: A | |
656 | * In hist_locks: A, D | |
657 | * In graph: 'A -> BX', 'A -> D' | |
658 | */ | |
659 | commit BX | |
660 | /* | |
661 | * Add 'BX -> ?' | |
662 | * What has been queued since acquire BX: C, E | |
663 | * | |
664 | * In held_locks: Empty | |
665 | * In hist_locks: D, E | |
666 | * In graph: 'A -> BX', 'A -> D', | |
667 | * 'BX -> C', 'BX -> E' | |
668 | */ | |
669 | ||
670 | release BX | |
671 | /* | |
672 | * In held_locks: Empty | |
673 | * In hist_locks: D, E | |
674 | * In graph: 'A -> BX', 'A -> D', | |
675 | * 'BX -> C', 'BX -> E' | |
676 | */ | |
677 | release A | |
678 | /* | |
679 | * Pop A from held_locks | |
680 | * | |
681 | * In held_locks: Empty | |
682 | * In hist_locks: A, D | |
683 | * In graph: 'A -> BX', 'A -> D', | |
684 | * 'BX -> C', 'BX -> E' | |
685 | */ | |
686 | ||
687 | where A, BX, C,..., E are different lock classes, and a suffix 'X' is | |
688 | added on crosslocks. | |
689 | ||
690 | Crossrelease considers all acquisitions after acqiuring BX are | |
691 | candidates which might create dependencies with BX. True dependencies | |
692 | will be determined when identifying the release context of BX. Meanwhile, | |
693 | all typical locks are queued so that they can be used at the commit step. | |
694 | And then two dependencies 'BX -> C' and 'BX -> E' are added at the | |
695 | commit step when identifying the release context. | |
696 | ||
697 | The final graph will be, with crossrelease: | |
698 | ||
699 | -> C | |
700 | / | |
701 | -> BX - | |
702 | / \ | |
703 | A - -> E | |
704 | \ | |
705 | -> D | |
706 | ||
707 | where A, BX, C,..., E are different lock classes, and a suffix 'X' is | |
708 | added on crosslocks. | |
709 | ||
710 | However, the final graph will be, without crossrelease: | |
711 | ||
712 | A -> D | |
713 | ||
714 | where A and D are different lock classes. | |
715 | ||
716 | The former graph has three more dependencies, 'A -> BX', 'BX -> C' and | |
717 | 'BX -> E' giving additional opportunities to check if they cause | |
718 | deadlocks. This way lockdep can detect a deadlock or its possibility | |
719 | caused by crosslocks. | |
720 | ||
721 | CONCLUSION | |
722 | ||
723 | We checked how crossrelease works with several examples. | |
724 | ||
725 | ||
726 | ============= | |
727 | Optimizations | |
728 | ============= | |
729 | ||
730 | Avoid duplication | |
731 | ----------------- | |
732 | ||
733 | Crossrelease feature uses a cache like what lockdep already uses for | |
734 | dependency chains, but this time it's for caching CT type dependencies. | |
735 | Once that dependency is cached, the same will never be added again. | |
736 | ||
737 | ||
738 | Lockless for hot paths | |
739 | ---------------------- | |
740 | ||
741 | To keep all locks for later use at the commit step, crossrelease adopts | |
742 | a local array embedded in task_struct, which makes access to the data | |
743 | lockless by forcing it to happen only within the owner context. It's | |
744 | like how lockdep handles held_locks. Lockless implmentation is important | |
745 | since typical locks are very frequently acquired and released. | |
746 | ||
747 | ||
748 | ================================================= | |
749 | APPENDIX A: What lockdep does to work aggresively | |
750 | ================================================= | |
751 | ||
752 | A deadlock actually occurs when all wait operations creating circular | |
753 | dependencies run at the same time. Even though they don't, a potential | |
754 | deadlock exists if the problematic dependencies exist. Thus it's | |
755 | meaningful to detect not only an actual deadlock but also its potential | |
756 | possibility. The latter is rather valuable. When a deadlock occurs | |
757 | actually, we can identify what happens in the system by some means or | |
758 | other even without lockdep. However, there's no way to detect possiblity | |
759 | without lockdep unless the whole code is parsed in head. It's terrible. | |
760 | Lockdep does the both, and crossrelease only focuses on the latter. | |
761 | ||
762 | Whether or not a deadlock actually occurs depends on several factors. | |
763 | For example, what order contexts are switched in is a factor. Assuming | |
764 | circular dependencies exist, a deadlock would occur when contexts are | |
765 | switched so that all wait operations creating the dependencies run | |
766 | simultaneously. Thus to detect a deadlock possibility even in the case | |
767 | that it has not occured yet, lockdep should consider all possible | |
768 | combinations of dependencies, trying to: | |
769 | ||
770 | 1. Use a global dependency graph. | |
771 | ||
772 | Lockdep combines all dependencies into one global graph and uses them, | |
773 | regardless of which context generates them or what order contexts are | |
774 | switched in. Aggregated dependencies are only considered so they are | |
775 | prone to be circular if a problem exists. | |
776 | ||
777 | 2. Check dependencies between classes instead of instances. | |
778 | ||
779 | What actually causes a deadlock are instances of lock. However, | |
780 | lockdep checks dependencies between classes instead of instances. | |
781 | This way lockdep can detect a deadlock which has not happened but | |
782 | might happen in future by others but the same class. | |
783 | ||
784 | 3. Assume all acquisitions lead to waiting. | |
785 | ||
786 | Although locks might be acquired without waiting which is essential | |
787 | to create dependencies, lockdep assumes all acquisitions lead to | |
788 | waiting since it might be true some time or another. | |
789 | ||
790 | CONCLUSION | |
791 | ||
792 | Lockdep detects not only an actual deadlock but also its possibility, | |
793 | and the latter is more valuable. | |
794 | ||
795 | ||
796 | ================================================== | |
797 | APPENDIX B: How to avoid adding false dependencies | |
798 | ================================================== | |
799 | ||
800 | Remind what a dependency is. A dependency exists if: | |
801 | ||
802 | 1. There are two waiters waiting for each event at a given time. | |
803 | 2. The only way to wake up each waiter is to trigger its event. | |
804 | 3. Whether one can be woken up depends on whether the other can. | |
805 | ||
806 | For example: | |
807 | ||
808 | acquire A | |
809 | acquire B /* A dependency 'A -> B' exists */ | |
810 | release B | |
811 | release A | |
812 | ||
813 | where A and B are different lock classes. | |
814 | ||
815 | A depedency 'A -> B' exists since: | |
816 | ||
817 | 1. A waiter for A and a waiter for B might exist when acquiring B. | |
818 | 2. Only way to wake up each is to release what it waits for. | |
819 | 3. Whether the waiter for A can be woken up depends on whether the | |
820 | other can. IOW, TASK X cannot release A if it fails to acquire B. | |
821 | ||
822 | For another example: | |
823 | ||
824 | TASK X TASK Y | |
825 | ------ ------ | |
826 | acquire AX | |
827 | acquire B /* A dependency 'AX -> B' exists */ | |
828 | release B | |
829 | release AX held by Y | |
830 | ||
831 | where AX and B are different lock classes, and a suffix 'X' is added | |
832 | on crosslocks. | |
833 | ||
834 | Even in this case involving crosslocks, the same rule can be applied. A | |
835 | depedency 'AX -> B' exists since: | |
836 | ||
837 | 1. A waiter for AX and a waiter for B might exist when acquiring B. | |
838 | 2. Only way to wake up each is to release what it waits for. | |
839 | 3. Whether the waiter for AX can be woken up depends on whether the | |
840 | other can. IOW, TASK X cannot release AX if it fails to acquire B. | |
841 | ||
842 | Let's take a look at more complicated example: | |
843 | ||
844 | TASK X TASK Y | |
845 | ------ ------ | |
846 | acquire B | |
847 | release B | |
848 | fork Y | |
849 | acquire AX | |
850 | acquire C /* A dependency 'AX -> C' exists */ | |
851 | release C | |
852 | release AX held by Y | |
853 | ||
854 | where AX, B and C are different lock classes, and a suffix 'X' is | |
855 | added on crosslocks. | |
856 | ||
857 | Does a dependency 'AX -> B' exist? Nope. | |
858 | ||
859 | Two waiters are essential to create a dependency. However, waiters for | |
860 | AX and B to create 'AX -> B' cannot exist at the same time in this | |
861 | example. Thus the dependency 'AX -> B' cannot be created. | |
862 | ||
863 | It would be ideal if the full set of true ones can be considered. But | |
864 | we can ensure nothing but what actually happened. Relying on what | |
865 | actually happens at runtime, we can anyway add only true ones, though | |
866 | they might be a subset of true ones. It's similar to how lockdep works | |
867 | for typical locks. There might be more true dependencies than what | |
868 | lockdep has detected in runtime. Lockdep has no choice but to rely on | |
869 | what actually happens. Crossrelease also relies on it. | |
870 | ||
871 | CONCLUSION | |
872 | ||
873 | Relying on what actually happens, lockdep can avoid adding false | |
874 | dependencies. |