Documentation/locking/crossrelease.txt

   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.