summaryrefslogtreecommitdiffstats
path: root/Documentation/locking/crossrelease.txt
blob: bdf1423d5f99e9b5a65e293049fdf0af7675f3b7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
Crossrelease
============

Started by Byungchul Park <byungchul.park@lge.com>

Contents:

 (*) Background

     - What causes deadlock
     - How lockdep works

 (*) Limitation

     - Limit lockdep
     - Pros from the limitation
     - Cons from the limitation
     - Relax the limitation

 (*) Crossrelease

     - Introduce crossrelease
     - Introduce commit

 (*) Implementation

     - Data structures
     - How crossrelease works

 (*) Optimizations

     - Avoid duplication
     - Lockless for hot paths

 (*) APPENDIX A: What lockdep does to work aggresively

 (*) APPENDIX B: How to avoid adding false dependencies


==========
Background
==========

What causes deadlock
--------------------

A deadlock occurs when a context is waiting for an event to happen,
which is impossible because another (or the) context who can trigger the
event is also waiting for another (or the) event to happen, which is
also impossible due to the same reason.

For example:

   A context going to trigger event C is waiting for event A to happen.
   A context going to trigger event A is waiting for event B to happen.
   A context going to trigger event B is waiting for event C to happen.

A deadlock occurs when these three wait operations run at the same time,
because event C cannot be triggered if event A does not happen, which in
turn cannot be triggered if event B does not happen, which in turn
cannot be triggered if event C does not happen. After all, no event can
be triggered since any of them never meets its condition to wake up.

A dependency might exist between two waiters and a deadlock might happen
due to an incorrect releationship between dependencies. Thus, we must
define what a dependency is first. A dependency exists between them if:

   1. There are two waiters waiting for each event at a given time.
   2. The only way to wake up each waiter is to trigger its event.
   3. Whether one can be woken up depends on whether the other can.

Each wait in the example creates its dependency like:

   Event C depends on event A.
   Event A depends on event B.
   Event B depends on event C.

   NOTE: Precisely speaking, a dependency is one between whether a
   waiter for an event can be woken up and whether another waiter for
   another event can be woken up. However from now on, we will describe
   a dependency as if it's one between an event and another event for
   simplicity.

And they form circular dependencies like:

    -> C -> A -> B -
   /                \
   \                /
    ----------------

   where 'A -> B' means that event A depends on event B.

Such circular dependencies lead to a deadlock since no waiter can meet
its condition to wake up as described.

CONCLUSION

Circular dependencies cause a deadlock.


How lockdep works
-----------------

Lockdep tries to detect a deadlock by checking dependencies created by
lock operations, acquire and release. Waiting for a lock corresponds to
waiting for an event, and releasing a lock corresponds to triggering an
event in the previous section.

In short, lockdep does:

   1. Detect a new dependency.
   2. Add the dependency into a global graph.
   3. Check if that makes dependencies circular.
   4. Report a deadlock or its possibility if so.

For example, consider a graph built by lockdep that looks like:

   A -> B -
           \
            -> E
           /
   C -> D -

   where A, B,..., E are different lock classes.

Lockdep will add a dependency into the graph on detection of a new
dependency. For example, it will add a dependency 'E -> C' when a new
dependency between lock E and lock C is detected. Then the graph will be:

       A -> B -
               \
                -> E -
               /      \
    -> C -> D -        \
   /                   /
   \                  /
    ------------------

   where A, B,..., E are different lock classes.

This graph contains a subgraph which demonstrates circular dependencies:

                -> E -
               /      \
    -> C -> D -        \
   /                   /
   \                  /
    ------------------

   where C, D and E are different lock classes.

This is the condition under which a deadlock might occur. Lockdep
reports it on detection after adding a new dependency. This is the way
how lockdep works.

CONCLUSION

Lockdep detects a deadlock or its possibility by checking if circular
dependencies were created after adding each new dependency.


==========
Limitation
==========

Limit lockdep
-------------

Limiting lockdep to work on only typical locks e.g. spin locks and
mutexes, which are released within the acquire context, the
implementation becomes simple but its capacity for detection becomes
limited. Let's check pros and cons in next section.


Pros from the limitation
------------------------

Given the limitation, when acquiring a lock, locks in a held_locks
cannot be released if the context cannot acquire it so has to wait to
acquire it, which means all waiters for the locks in the held_locks are
stuck. It's an exact case to create dependencies between each lock in
the held_locks and the lock to acquire.

For example:

   CONTEXT X
   ---------
   acquire A
   acquire B /* Add a dependency 'A -> B' */
   release B
   release A

   where A and B are different lock classes.

When acquiring lock A, the held_locks of CONTEXT X is empty thus no
dependency is added. But when acquiring lock B, lockdep detects and adds
a new dependency 'A -> B' between lock A in the held_locks and lock B.
They can be simply added whenever acquiring each lock.

And data required by lockdep exists in a local structure, held_locks
embedded in task_struct. Forcing to access the data within the context,
lockdep can avoid racy problems without explicit locks while handling
the local data.

Lastly, lockdep only needs to keep locks currently being held, to build
a dependency graph. However, relaxing the limitation, it needs to keep
even locks already released, because a decision whether they created
dependencies might be long-deferred.

To sum up, we can expect several advantages from the limitation:

   1. Lockdep can easily identify a dependency when acquiring a lock.
   2. Races are avoidable while accessing local locks in a held_locks.
   3. Lockdep only needs to keep locks currently being held.

CONCLUSION

Given the limitation, the implementation becomes simple and efficient.


Cons from the limitation
------------------------

Given the limitation, lockdep is applicable only to typical locks. For
example, page locks for page access or completions for synchronization
cannot work with lockdep.

Can we detect deadlocks below, under the limitation?

Example 1:

   CONTEXT X	   CONTEXT Y	   CONTEXT Z
   ---------	   ---------	   ----------
		   mutex_lock A
   lock_page B
		   lock_page B
				   mutex_lock A /* DEADLOCK */
				   unlock_page B held by X
		   unlock_page B
		   mutex_unlock A
				   mutex_unlock A

   where A and B are different lock classes.

No, we cannot.

Example 2:

   CONTEXT X		   CONTEXT Y
   ---------		   ---------
			   mutex_lock A
   mutex_lock A
			   wait_for_complete B /* DEADLOCK */
   complete B
			   mutex_unlock A
   mutex_unlock A

   where A is a lock class and B is a completion variable.

No, we cannot.

CONCLUSION

Given the limitation, lockdep cannot detect a deadlock or its
possibility caused by page locks or completions.


Relax the limitation
--------------------

Under the limitation, things to create dependencies are limited to
typical locks. However, synchronization primitives like page locks and
completions, which are allowed to be released in any context, also
create dependencies and can cause a deadlock. So lockdep should track
these locks to do a better job. We have to relax the limitation for
these locks to work with lockdep.

Detecting dependencies is very important for lockdep to work because
adding a dependency means adding an opportunity to check whether it
causes a deadlock. The more lockdep adds dependencies, the more it
thoroughly works. Thus Lockdep has to do its best to detect and add as
many true dependencies into a graph as possible.

For example, considering only typical locks, lockdep builds a graph like:

   A -> B -
           \
            -> E
           /
   C -> D -

   where A, B,..., E are different lock classes.

On the other hand, under the relaxation, additional dependencies might
be created and added. Assuming additional 'FX -> C' and 'E -> GX' are
added thanks to the relaxation, the graph will be:

         A -> B -
                 \
                  -> E -> GX
                 /
   FX -> C -> D -

   where A, B,..., E, FX and GX are different lock classes, and a suffix
   'X' is added on non-typical locks.

The latter graph gives us more chances to check circular dependencies
than the former. However, it might suffer performance degradation since
relaxing the limitation, with which design and implementation of lockdep
can be efficient, might introduce inefficiency inevitably. So lockdep
should provide two options, strong detection and efficient detection.

Choosing efficient detection:

   Lockdep works with only locks restricted to be released within the
   acquire context. However, lockdep works efficiently.

Choosing strong detection:

   Lockdep works with all synchronization primitives. However, lockdep
   suffers performance degradation.

CONCLUSION

Relaxing the limitation, lockdep can add additional dependencies giving
additional opportunities to check circular dependencies.


============
Crossrelease
============

Introduce crossrelease
----------------------

In order to allow lockdep to handle additional dependencies by what
might be released in any context, namely 'crosslock', we have to be able
to identify those created by crosslocks. The proposed 'crossrelease'
feature provoides a way to do that.

Crossrelease feature has to do:

   1. Identify dependencies created by crosslocks.
   2. Add the dependencies into a dependency graph.

That's all. Once a meaningful dependency is added into graph, then
lockdep would work with the graph as it did. The most important thing
crossrelease feature has to do is to correctly identify and add true
dependencies into the global graph.

A dependency e.g. 'A -> B' can be identified only in the A's release
context because a decision required to identify the dependency can be
made only in the release context. That is to decide whether A can be
released so that a waiter for A can be woken up. It cannot be made in
other than the A's release context.

It's no matter for typical locks because each acquire context is same as
its release context, thus lockdep can decide whether a lock can be
released in the acquire context. However for crosslocks, lockdep cannot
make the decision in the acquire context but has to wait until the
release context is identified.

Therefore, deadlocks by crosslocks cannot be detected just when it
happens, because those cannot be identified until the crosslocks are
released. However, deadlock possibilities can be detected and it's very
worth. See 'APPENDIX A' section to check why.

CONCLUSION

Using crossrelease feature, lockdep can work with what might be released
in any context, namely crosslock.


Introduce commit
----------------

Since crossrelease defers the work adding true dependencies of
crosslocks until they are actually released, crossrelease has to queue
all acquisitions which might create dependencies with the crosslocks.
Then it identifies dependencies using the queued data in batches at a
proper time. We call it 'commit'.

There are four types of dependencies:

1. TT type: 'typical lock A -> typical lock B'

   Just when acquiring B, lockdep can see it's in the A's release
   context. So the dependency between A and B can be identified
   immediately. Commit is unnecessary.

2. TC type: 'typical lock A -> crosslock BX'

   Just when acquiring BX, lockdep can see it's in the A's release
   context. So the dependency between A and BX can be identified
   immediately. Commit is unnecessary, too.

3. CT type: 'crosslock AX -> typical lock B'

   When acquiring B, lockdep cannot identify the dependency because
   there's no way to know if it's in the AX's release context. It has
   to wait until the decision can be made. Commit is necessary.

4. CC type: 'crosslock AX -> crosslock BX'

   When acquiring BX, lockdep cannot identify the dependency because
   there's no way to know if it's in the AX's release context. It has
   to wait until the decision can be made. Commit is necessary.
   But, handling CC type is not implemented yet. It's a future work.

Lockdep can work without commit for typical locks, but commit step is
necessary once crosslocks are involved. Introducing commit, lockdep
performs three steps. What lockdep does in each step is:

1. Acquisition: For typical locks, lockdep does what it originally did
   and queues the lock so that CT type dependencies can be checked using
   it at the commit step. For crosslocks, it saves data which will be
   used at the commit step and increases a reference count for it.

2. Commit: No action is reauired for typical locks. For crosslocks,
   lockdep adds CT type dependencies using the data saved at the
   acquisition step.

3. Release: No changes are required for typical locks. When a crosslock
   is released, it decreases a reference count for it.

CONCLUSION

Crossrelease introduces commit step to handle dependencies of crosslocks
in batches at a proper time.


==============
Implementation
==============

Data structures
---------------

Crossrelease introduces two main data structures.

1. hist_lock

   This is an array embedded in task_struct, for keeping lock history so
   that dependencies can be added using them at the commit step. Since
   it's local data, it can be accessed locklessly in the owner context.
   The array is filled at the acquisition step and consumed at the
   commit step. And it's managed in circular manner.

2. cross_lock

   One per lockdep_map exists. This is for keeping data of crosslocks
   and used at the commit step.


How crossrelease works
----------------------

It's the key of how crossrelease works, to defer necessary works to an
appropriate point in time and perform in at once at the commit step.
Let's take a look with examples step by step, starting from how lockdep
works without crossrelease for typical locks.

   acquire A /* Push A onto held_locks */
   acquire B /* Push B onto held_locks and add 'A -> B' */
   acquire C /* Push C onto held_locks and add 'B -> C' */
   release C /* Pop C from held_locks */
   release B /* Pop B from held_locks */
   release A /* Pop A from held_locks */

   where A, B and C are different lock classes.

   NOTE: This document assumes that readers already understand how
   lockdep works without crossrelease thus omits details. But there's
   one thing to note. Lockdep pretends to pop a lock from held_locks
   when releasing it. But it's subtly different from the original pop
   operation because lockdep allows other than the top to be poped.

In this case, lockdep adds 'the top of held_locks -> the lock to acquire'
dependency every time acquiring a lock.

After adding 'A -> B', a dependency graph will be:

   A -> B

   where A and B are different lock classes.

And after adding 'B -> C', the graph will be:

   A -> B -> C

   where A, B and C are different lock classes.

Let's performs commit step even for typical locks to add dependencies.
Of course, commit step is not necessary for them, however, it would work
well because this is a more general way.

   acquire A
   /*
    * Queue A into hist_locks
    *
    * In hist_locks: A
    * In graph: Empty
    */

   acquire B
   /*
    * Queue B into hist_locks
    *
    * In hist_locks: A, B
    * In graph: Empty
    */

   acquire C
   /*
    * Queue C into hist_locks
    *
    * In hist_locks: A, B, C
    * In graph: Empty
    */

   commit C
   /*
    * Add 'C -> ?'
    * Answer the following to decide '?'
    * What has been queued since acquire C: Nothing
    *
    * In hist_locks: A, B, C
    * In graph: Empty
    */

   release C

   commit B
   /*
    * Add 'B -> ?'
    * Answer the following to decide '?'
    * What has been queued since acquire B: C
    *
    * In hist_locks: A, B, C
    * In graph: 'B -> C'
    */

   release B

   commit A
   /*
    * Add 'A -> ?'
    * Answer the following to decide '?'
    * What has been queued since acquire A: B, C
    *
    * In hist_locks: A, B, C
    * In graph: 'B -> C', 'A -> B', 'A -> C'
    */

   release A

   where A, B and C are different lock classes.

In this case, dependencies are added at the commit step as described.

After commits for A, B and C, the graph will be:

   A -> B -> C

   where A, B and C are different lock classes.

   NOTE: A dependency 'A -> C' is optimized out.

We can see the former graph built without commit step is same as the
latter graph built using commit steps. Of course the former way leads to
earlier finish for building the graph, which means we can detect a
deadlock or its possibility sooner. So the former way would be prefered
when possible. But we cannot avoid using the latter way for crosslocks.

Let's look at how commit steps work for crosslocks. In this case, the
commit step is performed only on crosslock AX as real. And it assumes
that the AX release context is different from the AX acquire context.

   BX RELEASE CONTEXT		   BX ACQUIRE CONTEXT
   ------------------		   ------------------
				   acquire A
				   /*
				    * Push A onto held_locks
				    * Queue A into hist_locks
				    *
				    * In held_locks: A
				    * In hist_locks: A
				    * In graph: Empty
				    */

				   acquire BX
				   /*
				    * Add 'the top of held_locks -> BX'
				    *
				    * In held_locks: A
				    * In hist_locks: A
				    * In graph: 'A -> BX'
				    */

   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   It must be guaranteed that the following operations are seen after
   acquiring BX globally. It can be done by things like barrier.
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

   acquire C
   /*
    * Push C onto held_locks
    * Queue C into hist_locks
    *
    * In held_locks: C
    * In hist_locks: C
    * In graph: 'A -> BX'
    */

   release C
   /*
    * Pop C from held_locks
    *
    * In held_locks: Empty
    * In hist_locks: C
    * In graph: 'A -> BX'
    */
				   acquire D
				   /*
				    * Push D onto held_locks
				    * Queue D into hist_locks
				    * Add 'the top of held_locks -> D'
				    *
				    * In held_locks: A, D
				    * In hist_locks: A, D
				    * In graph: 'A -> BX', 'A -> D'
				    */
   acquire E
   /*
    * Push E onto held_locks
    * Queue E into hist_locks
    *
    * In held_locks: E
    * In hist_locks: C, E
    * In graph: 'A -> BX', 'A -> D'
    */

   release E
   /*
    * Pop E from held_locks
    *
    * In held_locks: Empty
    * In hist_locks: D, E
    * In graph: 'A -> BX', 'A -> D'
    */
				   release D
				   /*
				    * Pop D from held_locks
				    *
				    * In held_locks: A
				    * In hist_locks: A, D
				    * In graph: 'A -> BX', 'A -> D'
				    */
   commit BX
   /*
    * Add 'BX -> ?'
    * What has been queued since acquire BX: C, E
    *
    * In held_locks: Empty
    * In hist_locks: D, E
    * In graph: 'A -> BX', 'A -> D',
    *           'BX -> C', 'BX -> E'
    */

   release BX
   /*
    * In held_locks: Empty
    * In hist_locks: D, E
    * In graph: 'A -> BX', 'A -> D',
    *           'BX -> C', 'BX -> E'
    */
				   release A
				   /*
				    * Pop A from held_locks
				    *
				    * In held_locks: Empty
				    * In hist_locks: A, D
				    * In graph: 'A -> BX', 'A -> D',
				    *           'BX -> C', 'BX -> E'
				    */

   where A, BX, C,..., E are different lock classes, and a suffix 'X' is
   added on crosslocks.

Crossrelease considers all acquisitions after acqiuring BX are
candidates which might create dependencies with BX. True dependencies
will be determined when identifying the release context of BX. Meanwhile,
all typical locks are queued so that they can be used at the commit step.
And then two dependencies 'BX -> C' and 'BX -> E' are added at the
commit step when identifying the release context.

The final graph will be, with crossrelease:

               -> C
              /
       -> BX -
      /       \
   A -         -> E
      \
       -> D

   where A, BX, C,..., E are different lock classes, and a suffix 'X' is
   added on crosslocks.

However, the final graph will be, without crossrelease:

   A -> D

   where A and D are different lock classes.

The former graph has three more dependencies, 'A -> BX', 'BX -> C' and
'BX -> E' giving additional opportunities to check if they cause
deadlocks. This way lockdep can detect a deadlock or its possibility
caused by crosslocks.

CONCLUSION

We checked how crossrelease works with several examples.


=============
Optimizations
=============

Avoid duplication
-----------------

Crossrelease feature uses a cache like what lockdep already uses for
dependency chains, but this time it's for caching CT type dependencies.
Once that dependency is cached, the same will never be added again.


Lockless for hot paths
----------------------

To keep all locks for later use at the commit step, crossrelease adopts
a local array embedded in task_struct, which makes access to the data
lockless by forcing it to happen only within the owner context. It's
like how lockdep handles held_locks. Lockless implmentation is important
since typical locks are very frequently acquired and released.


=================================================
APPENDIX A: What lockdep does to work aggresively
=================================================

A deadlock actually occurs when all wait operations creating circular
dependencies run at the same time. Even though they don't, a potential
deadlock exists if the problematic dependencies exist. Thus it's
meaningful to detect not only an actual deadlock but also its potential
possibility. The latter is rather valuable. When a deadlock occurs
actually, we can identify what happens in the system by some means or
other even without lockdep. However, there's no way to detect possiblity
without lockdep unless the whole code is parsed in head. It's terrible.
Lockdep does the both, and crossrelease only focuses on the latter.

Whether or not a deadlock actually occurs depends on several factors.
For example, what order contexts are switched in is a factor. Assuming
circular dependencies exist, a deadlock would occur when contexts are
switched so that all wait operations creating the dependencies run
simultaneously. Thus to detect a deadlock possibility even in the case
that it has not occured yet, lockdep should consider all possible
combinations of dependencies, trying to:

1. Use a global dependency graph.

   Lockdep combines all dependencies into one global graph and uses them,
   regardless of which context generates them or what order contexts are
   switched in. Aggregated dependencies are only considered so they are
   prone to be circular if a problem exists.

2. Check dependencies between classes instead of instances.

   What actually causes a deadlock are instances of lock. However,
   lockdep checks dependencies between classes instead of instances.
   This way lockdep can detect a deadlock which has not happened but
   might happen in future by others but the same class.

3. Assume all acquisitions lead to waiting.

   Although locks might be acquired without waiting which is essential
   to create dependencies, lockdep assumes all acquisitions lead to
   waiting since it might be true some time or another.

CONCLUSION

Lockdep detects not only an actual deadlock but also its possibility,
and the latter is more valuable.


==================================================
APPENDIX B: How to avoid adding false dependencies
==================================================

Remind what a dependency is. A dependency exists if:

   1. There are two waiters waiting for each event at a given time.
   2. The only way to wake up each waiter is to trigger its event.
   3. Whether one can be woken up depends on whether the other can.

For example:

   acquire A
   acquire B /* A dependency 'A -> B' exists */
   release B
   release A

   where A and B are different lock classes.

A depedency 'A -> B' exists since:

   1. A waiter for A and a waiter for B might exist when acquiring B.
   2. Only way to wake up each is to release what it waits for.
   3. Whether the waiter for A can be woken up depends on whether the
      other can. IOW, TASK X cannot release A if it fails to acquire B.

For another example:

   TASK X			   TASK Y
   ------			   ------
				   acquire AX
   acquire B /* A dependency 'AX -> B' exists */
   release B
   release AX held by Y

   where AX and B are different lock classes, and a suffix 'X' is added
   on crosslocks.

Even in this case involving crosslocks, the same rule can be applied. A
depedency 'AX -> B' exists since:

   1. A waiter for AX and a waiter for B might exist when acquiring B.
   2. Only way to wake up each is to release what it waits for.
   3. Whether the waiter for AX can be woken up depends on whether the
      other can. IOW, TASK X cannot release AX if it fails to acquire B.

Let's take a look at more complicated example:

   TASK X			   TASK Y
   ------			   ------
   acquire B
   release B
   fork Y
				   acquire AX
   acquire C /* A dependency 'AX -> C' exists */
   release C
   release AX held by Y

   where AX, B and C are different lock classes, and a suffix 'X' is
   added on crosslocks.

Does a dependency 'AX -> B' exist? Nope.

Two waiters are essential to create a dependency. However, waiters for
AX and B to create 'AX -> B' cannot exist at the same time in this
example. Thus the dependency 'AX -> B' cannot be created.

It would be ideal if the full set of true ones can be considered. But
we can ensure nothing but what actually happened. Relying on what
actually happens at runtime, we can anyway add only true ones, though
they might be a subset of true ones. It's similar to how lockdep works
for typical locks. There might be more true dependencies than what
lockdep has detected in runtime. Lockdep has no choice but to rely on
what actually happens. Crossrelease also relies on it.

CONCLUSION

Relying on what actually happens, lockdep can avoid adding false
dependencies.