[PATCH v4 15/15] lockdep: Crossrelease feature documentation

[Byungchul Park]

This document describes the concept of crossrelease feature, which
generalizes what causes a deadlock and how can detect a deadlock.

Signed-off-by: Byungchul Park <byungchul.park@xxxxxxx>
---
 Documentation/locking/crossrelease.txt | 1053 ++++++++++++++++++++++++++++++++
 1 file changed, 1053 insertions(+)
 create mode 100644 Documentation/locking/crossrelease.txt

diff --git a/Documentation/locking/crossrelease.txt b/Documentation/locking/crossrelease.txt
new file mode 100644
index 0000000..7170b2f
--- /dev/null
+++ b/Documentation/locking/crossrelease.txt
@@ -0,0 +1,1053 @@
+Crossrelease
+============
+
+Started by Byungchul Park <byungchul.park@xxxxxxx>
+
+Contents:
+
+ (*) Background.
+
+     - What causes deadlock.
+     - What lockdep detects.
+     - How lockdep works.
+
+ (*) Limitation.
+
+     - Limit to typical locks.
+     - Pros from the limitation.
+     - Cons from the limitation.
+
+ (*) Generalization.
+
+     - Relax the limitation.
+
+ (*) Crossrelease.
+
+     - Introduce crossrelease.
+     - Pick true dependencies.
+     - Introduce commit.
+
+ (*) Implementation.
+
+     - Data structures.
+     - How crossrelease works.
+
+ (*) Optimizations.
+
+     - Avoid duplication.
+     - Lockless for hot paths.
+
+
+==========
+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. Single or more contexts
+paricipate in such a deadlock.
+
+For example,
+
+   A context going to trigger event D 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 context going to trigger event C is waiting for event D to happen.
+
+A deadlock occurs when these four wait operations run at the same time,
+because event D 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, which in turn cannot be
+triggered if event D does not happen. After all, no event can be
+triggered since any of them never meets its precondition to wake up.
+
+In terms of dependency, a wait for an event creates a dependency if the
+context is going to wake up another waiter by triggering an proper event.
+In other words, a dependency exists if,
+
+   COND 1. There are two waiters waiting for each event at the same time.
+   COND 2. Only way to wake up each waiter is to trigger its events.
+   COND 3. Whether one can be woken up depends on whether the other can.
+
+Each wait in the example creates its dependency like,
+
+   Event D depends on event A.
+   Event A depends on event B.
+   Event B depends on event C.
+   Event C depends on event D.
+
+   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, so e.g. 'event D depends on event A'.
+
+And they form circular dependencies like,
+
+    -> D -> A -> B -> C -
+   /                     \
+   \                     /
+    ---------------------
+
+   where A, B,..., D are different events, and '->' represents 'depends
+   on'.
+
+Such circular dependencies lead to a deadlock since no waiter can meet
+its precondition to wake up if they run simultaneously, as described.
+
+CONCLUSION
+
+Circular dependencies cause a deadlock.
+
+
+What lockdep detects
+--------------------
+
+Lockdep tries to detect a deadlock by checking dependencies created by
+lock operations e.i. acquire and release. Waiting for a lock to be
+released corresponds to waiting for an event to happen, and releasing a
+lock corresponds to triggering an event. See 'What causes deadlock'
+section.
+
+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. Lockdep does the both.
+
+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 problematic
+dependencies run simultaneously.
+
+To detect a potential possibility which means a deadlock has not
+happened yet but might happen in future, lockdep considers all possible
+combinations of dependencies so that its potential possibility can be
+detected in advance. To do this, lockdep is 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 classes.
+
+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 and generates dependencies, since it might be true some time
+   or another. Potential possibilities can be checked in this way.
+
+Lockdep detects both an actual deadlock and its possibility. But the
+latter is more valuable than the former. 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.
+
+CONCLUSION
+
+Lockdep detects and reports,
+
+   1. A deadlock possibility.
+   2. A deadlock which actually occured.
+
+
+How lockdep works
+-----------------
+
+Lockdep does,
+
+   1. Detect a new dependency created.
+   2. Keep the dependency in a global data structure, graph.
+   3. Check if circular dependencies exist.
+   4. Report a deadlock or its possibility if so.
+
+A graph built by lockdep looks like, e.g.
+
+   A -> B -        -> F -> G
+           \      /
+            -> E -        -> L
+           /      \      /
+   C -> D -        -> H -
+                         \
+                          -> I -> K
+                         /
+                      J -
+
+   where A, B,..., L are different lock classes.
+
+Lockdep will add a dependency into graph when a new dependency is
+detected. For example, it will add a dependency 'K -> J' when a new
+dependency between lock K and lock J is detected. Then the graph will be,
+
+   A -> B -        -> F -> G
+           \      /
+            -> E -        -> L
+           /      \      /
+   C -> D -        -> H -
+                         \
+                          -> I -> K -
+                         /           \
+                   -> J -             \
+                  /                   /
+                  \                  /
+                   ------------------
+
+   where A, B,..., L are different lock classes.
+
+Now, circular dependencies are detected like,
+
+           -> I -> K -
+          /           \
+    -> J -             \
+   /                   /
+   \                  /
+    ------------------
+
+   where J, I and K are different lock classes.
+
+As decribed in 'What causes deadlock', this is the condition under which
+a deadlock might occur. Lockdep detects a deadlock or its possibility by
+checking if circular dependencies were created after adding each new
+dependency into the global graph. 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 to typical locks
+----------------------
+
+Limiting lockdep to checking dependencies only on typical locks e.g.
+spin locks and mutexes, which should be released within the acquire
+context, the implementation of detecting and adding dependencies becomes
+simple but its capacity for detection becomes limited. Let's check what
+its pros and cons are, in next section.
+
+CONCLUSION
+
+Limiting lockdep to working on typical locks e.g. spin locks and mutexes,
+the implmentation becomes simple but limits its capacity.
+
+
+Pros from the limitation
+------------------------
+
+Given the limitation, when acquiring a lock, locks in the held_locks of
+the context cannot be released if the context fails to acquire it and
+has to wait for it. It also makes waiters for the locks in the
+held_locks stuck. It's the exact case to create a dependency 'A -> B',
+where lock A is each lock in held_locks and lock B is the lock to
+acquire. See 'What casues deadlock' section.
+
+For example,
+
+   CONTEXT X
+   ---------
+   acquire A
+
+   acquire B /* Add a dependency 'A -> B' */
+
+   acquire C /* Add a dependency 'B -> C' */
+
+   release C
+
+   release B
+
+   release A
+
+   where A, B and C are different lock classes.
+
+When acquiring lock A, the held_locks of CONTEXT X is empty thus no
+dependency is added. When acquiring lock B, lockdep detects and adds
+a new dependency 'A -> B' between lock A in held_locks and lock B. When
+acquiring lock C, lockdep also adds another dependency 'B -> C' for the
+same reason. They can be simply added whenever acquiring each lock.
+
+And most data required by lockdep exists in a local structure e.i.
+'task_struct -> held_locks'. Forcing to access those 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
+the dependency graph. However relaxing the limitation, it might need to
+keep even locks already released, because the decision of whether they
+created dependencies might be long-deferred. See 'Crossrelease' section.
+
+To sum up, we can expect several advantages from the limitation.
+
+1. Lockdep can easily identify a dependency when acquiring a lock.
+2. Requiring only local locks makes many races avoidable.
+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 play with lockdep under the limitation.
+
+Can we detect deadlocks below, under the limitation?
+
+Example 1:
+
+   CONTEXT X		   CONTEXT Y
+   ---------		   ---------
+   mutext_lock A
+			   lock_page B
+   lock_page B
+			   mutext_lock A /* DEADLOCK */
+   unlock_page B
+			   mutext_unlock A
+   mutex_unlock A
+			   unlock_page B
+
+   where A is a lock class and B is a page lock.
+
+No, we cannot.
+
+Example 2:
+
+   CONTEXT X	   CONTEXT Y	   CONTEXT Z
+   ---------	   ---------	   ----------
+		   mutex_lock A
+   lock_page B
+		   lock_page B
+				   mutext_lock A /* DEADLOCK */
+				   mutext_unlock A
+				   unlock_page B held by X
+		   unlock_page B
+		   mutex_unlock A
+
+   where A is a lock class and B is a page lock.
+
+No, we cannot.
+
+Example 3:
+
+   CONTEXT X		   CONTEXT Y
+   ---------		   ---------
+			   mutex_lock A
+   mutex_lock A
+   mutex_unlock A
+			   wait_for_complete B /* DEADLOCK */
+   complete B
+			   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.
+
+
+==============
+Generalization
+==============
+
+Relax the limitation
+--------------------
+
+Under the limitation, things to create dependencies are limited to
+typical locks. However, e.g. page locks and completions which are not
+typical locks also create dependencies and cause a deadlock. Therefore
+it would be better for lockdep to detect a deadlock or its possibility
+even for them.
+
+Detecting and adding dependencies into graph is very important for
+lockdep to work because adding a dependency means adding a chance to
+check if it causes a deadlock. The more lockdep adds dependencies, the
+more it thoroughly works. Therefore Lockdep has to do its best to add as
+many true dependencies as possible into the graph.
+
+Relaxing the limitation, lockdep can add more dependencies since
+additional things e.g. page locks or completions create additional
+dependencies. However even so, it needs to be noted that the relaxation
+does not affect the behavior of adding dependencies for typical locks.
+
+For example, considering only typical locks, lockdep builds a graph like,
+
+   A -> B -        -> F -> G
+           \      /
+            -> E -        -> L
+           /      \      /
+   C -> D -        -> H -
+                         \
+                          -> I -> K
+                         /
+                      J -
+
+   where A, B,..., L are different lock classes.
+
+On the other hand, under the relaxation, additional dependencies might
+be created and added. Assuming additional 'MX -> H', 'L -> NX' and
+'OX -> J' dependencies are added thanks to the relaxation, the graph
+will be, giving additional chances to check circular dependencies,
+
+   A -> B -        -> F -> G
+           \      /
+            -> E -        -> L -> NX
+           /      \      /
+   C -> D -        -> H -
+                  /      \
+              MX -        -> I -> K
+                         /
+                   -> J -
+                  /
+              OX -
+
+   where A, B,..., L, MX, NX and OX are different lock classes, and
+   a suffix 'X' is added on non-typical locks e.g. page locks and
+   completions.
+
+However, it might suffer performance degradation since relaxing the
+limitation with which design and implementation of lockdep could be
+efficient might introduce inefficiency inevitably. Each option, strong
+detection or efficient detection, has its pros and cons, thus the right
+of choice between two options should be given to users.
+
+Choosing efficient detection, lockdep only deals with locks satisfying,
+
+   A lock should be released within the context holding the lock.
+
+Choosing strong detection, lockdep deals with any locks satisfying,
+
+   A lock can be released in any context.
+
+The latter, of course, doesn't allow illegal contexts to release a lock.
+For example, acquiring a lock in irq-safe context before releasing the
+lock in irq-unsafe context is not allowed, which after all ends in
+circular dependencies, meaning a deadlock. Otherwise, any contexts are
+allowed to release it.
+
+CONCLUSION
+
+Relaxing the limitation, lockdep can add additional dependencies and
+get additional chances to check if they cause deadlocks.
+
+
+============
+Crossrelease
+============
+
+Introduce crossrelease
+----------------------
+
+To allow lockdep to handle additional dependencies by what might be
+released in any context, namely 'crosslock', a new feature 'crossrelease'
+is introduced. Thanks to the feature, now lockdep can identify such
+dependencies. Crossrelease feature has to do,
+
+   1. Identify dependencies by crosslocks.
+   2. Add the dependencies into graph.
+
+That's all. Once a meaningful dependency is added into graph, then
+lockdep would work with the graph as it did. So 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 contexts than the A's release context. See 'What causes deadlock'
+section to remind what a dependency is.
+
+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 lockdep has to queue all acquisitions which might create
+dependencies until the decision can be made, so that they can be used
+when it proves they are the right ones. We call the step 'commit'. See
+'Introduce commit' section.
+
+Of course, some actual deadlocks caused by crosslocks cannot be detected
+just when it happens, because the deadlocks cannot be identified until
+the crosslocks is actually released. However, deadlock possibilities can
+be detected in this way. It's worth possibility detection of deadlock.
+See 'What lockdep does' section.
+
+CONCLUSION
+
+With crossrelease feature, lockdep can work with what might be released
+in any context, namely crosslock.
+
+
+Pick true dependencies
+----------------------
+
+Remind what a dependency is. A dependency exists if,
+
+   COND 1. There are two waiters waiting for each event at the same time.
+   COND 2. Only way to wake up each waiter is to trigger its events.
+   COND 3. Whether one can be woken up depends on whether the other can.
+
+For example,
+
+   TASK X
+   ------
+   acquire A
+
+   acquire B /* A dependency 'A -> B' exists */
+
+   acquire C /* A dependency 'B -> C' exists */
+
+   release C
+
+   release B
+
+   release A
+
+   where A, B and C 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 of them 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 cannot acquire B.
+
+Other dependencies 'B -> C' and 'A -> C' also exist for the same reason.
+But the second is ignored since it's covered by 'A -> B' and 'B -> C'.
+
+For another example,
+
+   TASK X			   TASK Y
+   ------			   ------
+				   acquire AX
+   acquire D
+   /* A dependency 'AX -> D' exists */
+				   acquire B
+   release D
+				   acquire C
+				   /* A dependency 'B -> C' exists */
+   acquire E
+   /* A dependency 'AX -> E' exists */
+				   acquire D
+				   /* A dependency 'C -> D' exists */
+   release E
+				   release D
+   release AX held by Y
+				   release C
+
+				   release B
+
+   where AX, B, C,..., E are different lock classes, and a suffix 'X' is
+   added on crosslocks.
+
+Even in this case involving crosslocks, the same rules can be applied. A
+depedency 'AX -> D' exists since,
+
+   1. A waiter for AX and a waiter for D might exist when acquiring D.
+   2. Only way to wake up each of them 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 cannot acquire D.
+
+The same rules can be applied to other dependencies, too.
+
+Let's take a look at more complicated example.
+
+   TASK X			   TASK Y
+   ------			   ------
+   acquire B
+
+   release B
+
+   acquire C
+
+   release C
+   (1)
+   fork Y
+				   acquire AX
+   acquire D
+   /* A dependency 'AX -> D' exists */
+				   acquire F
+   release D
+				   acquire G
+				   /* A dependency 'F -> G' exists */
+   acquire E
+   /* A dependency 'AX -> E' exists */
+				   acquire H
+				   /* A dependency 'G -> H' exists */
+   release E
+				   release H
+   release AX held by Y
+				   release G
+
+				   release F
+
+   where AX, B, C,..., H are different lock classes, and a suffix 'X' is
+   added on crosslocks.
+
+Does a dependency 'AX -> B' exist? Nope.
+
+Two waiters, one is for AX and the other is for B, are essential
+elements to create the dependency 'AX -> B'. However in this example,
+these two waiters cannot exist at the same time. Thus the dependency
+'AX -> B' cannot be created.
+
+In fact, AX depends on all acquisitions after (1) in TASK X e.i. D and E,
+but excluding all acquisitions before (1) in the context e.i. A and C.
+Thus only 'AX -> D' and 'AX -> E' are true dependencies by AX.
+
+It would be ideal if the full set of true ones can be added. But parsing
+the whole code is necessary to do it, which is impossible. Relying on
+what actually happens at runtime, we can anyway add only true ones even
+though they might be a subset of the full set. This way we can avoid
+adding false ones.
+
+It's similar to how lockdep works for typical locks. Ideally there might
+be more true dependencies than ones being in the gloabl dependency graph,
+however, lockdep has no choice but to rely on what actually happens
+since otherwise it's almost impossible.
+
+CONCLUSION
+
+Relying on what actually happens, adding false dependencies can be
+avoided.
+
+
+Introduce commit
+----------------
+
+Crossrelease feature names it 'commit' to identify and add dependencies
+into graph in batches. Lockdep is already doing what commit is supposed
+to do, when acquiring a lock for typical locks. However, that way must
+be changed for crosslocks so that it identifies a crosslock's release
+context first, then does commit.
+
+There are four types of dependencies.
+
+1. TT type: 'Typical lock A -> Typical lock B' dependency
+
+   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' dependency
+
+   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' dependency
+
+   When acquiring B, lockdep cannot identify the dependency because
+   there's no way to know whether 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' dependency
+
+   If there is a typical lock acting as a bridge so that 'AX -> a lock'
+   and 'the lock -> BX' can be added, then this dependency can be
+   detected. But direct ways are not implemented yet. It's a future work.
+
+Lockdep works even without commit for typical locks. However, commit
+step is necessary once crosslocks are involved, until all crosslocks in
+progress are released. Introducing commit, lockdep performs three steps
+i.e. acquire, commit and release. What lockdep does in each step is,
+
+1. Acquire
+
+   1) For typical lock
+
+      Lockdep does what it originally did and queues the lock so that
+      lockdep can check CT type dependencies using it at commit step.
+
+   2) For crosslock
+
+      The crosslock is added to a global linked list so that lockdep can
+      check CT type dependencies using it at commit step.
+
+2. Commit
+
+   1) For typical lock
+
+      N/A.
+
+   2) For crosslock
+
+      Lockdep checks and adds CT Type dependencies using data saved at
+      acquire step.
+
+3. Release
+
+   1) For typical lock
+
+      No change.
+
+   2) For crosslock
+
+      Lockdep just remove the crosslock from the global linked list, to
+      which it was added at acquire step.
+
+CONCLUSION
+
+Crossrelease feature introduces commit step to handle dependencies by
+crosslocks in batches, which lockdep cannot handle in its original way.
+
+
+==============
+Implementation
+==============
+
+Data structures
+---------------
+
+Crossrelease feature introduces two main data structures.
+
+1. pend_lock
+
+   This is an array embedded in task_struct, for keeping locks queued so
+   that real dependencies can be added using them at commit step. Since
+   it's local data, it can be accessed locklessly in the owner context.
+   The array is filled at acquire step and consumed at commit step. And
+   it's managed in circular manner.
+
+2. cross_lock
+
+   This is a global linked list, for keeping all crosslocks in progress.
+   The list grows at acquire step and is shrunk at release step.
+
+CONCLUSION
+
+Crossrelease feature introduces two main data structures.
+
+1. A pend_lock array for queueing typical locks in circular manner.
+2. A cross_lock linked list for managing crosslocks in progress.
+
+
+How crossrelease works
+----------------------
+
+Let's take a look at how crossrelease feature works step by step,
+starting from how lockdep works without crossrelease feaure.
+
+For example, the below is how lockdep works for typical locks.
+
+   A's RELEASE CONTEXT (= A's ACQUIRE CONTEXT)
+   -------------------------------------------
+   acquire A
+
+   acquire B /* Add 'A -> B' */
+
+   acquire C /* Add 'B -> C' */
+
+   release C
+
+   release B
+
+   release A
+
+   where A, B and C are different lock classes.
+
+After adding 'A -> B', the 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.
+
+What if we use commit step to add dependencies even for typical locks?
+Commit step is not necessary for them, however it anyway would work well,
+because this is a more general way.
+
+   A's RELEASE CONTEXT (= A's ACQUIRE CONTEXT)
+   -------------------------------------------
+   acquire A
+   /*
+    * 1. Mark A as started
+    * 2. Queue A
+    *
+    * In pend_lock: A
+    * In graph: Empty
+    */
+
+   acquire B
+   /*
+    * 1. Mark B as started
+    * 2. Queue B
+    *
+    * In pend_lock: A, B
+    * In graph: Empty
+    */
+
+   acquire C
+   /*
+    * 1. Mark C as started
+    * 2. Queue C
+    *
+    * In pend_lock: A, B, C
+    * In graph: Empty
+    */
+
+   release C
+   /*
+    * 1. Commit C (= Add 'C -> ?')
+    *   a. What queued since C was marked: Nothing
+    *   b. Add nothing
+    *
+    * In pend_lock: A, B, C
+    * In graph: Empty
+    */
+
+   release B
+   /*
+    * 1. Commit B (= Add 'B -> ?')
+    *   a. What queued since B was marked: C
+    *   b. Add 'B -> C'
+    *
+    * In pend_lock: A, B, C
+    * In graph: 'B -> C'
+    */
+
+   release A
+   /*
+    * 1. Commit A (= Add 'A -> ?')
+    *   a. What queued since A was marked: B, C
+    *   b. Add 'A -> B'
+    *   c. Add 'A -> C'
+    *
+    * In pend_lock: A, B, C
+    * In graph: 'B -> C', 'A -> B', 'A -> C'
+    */
+
+   where A, B and C are different lock classes.
+
+After doing commit A, B and C, the dependency graph becomes like,
+
+   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
+if possible. But we cannot avoid using the latter way for crosslocks.
+
+Let's look at how commit works for crosslocks.
+
+   AX's RELEASE CONTEXT		   AX's ACQUIRE CONTEXT
+   --------------------		   --------------------
+				   acquire AX
+				   /*
+				    * 1. Mark AX as started
+				    *
+				    * (No queuing for crosslocks)
+				    *
+				    * In pend_lock: Empty
+				    * In graph: Empty
+				    */
+
+   (serialized by some means e.g. barrier)
+
+   acquire D
+   /*
+    * (No marking for typical locks)
+    *
+    * 1. Queue D
+    *
+    * In pend_lock: D
+    * In graph: Empty
+    */
+				   acquire B
+				   /*
+				    * (No marking for typical locks)
+				    *
+				    * 1. Queue B
+				    *
+				    * In pend_lock: B
+				    * In graph: Empty
+				    */
+   release D
+   /*
+    * (No commit for typical locks)
+    *
+    * In pend_lock: D
+    * In graph: Empty
+    */
+				   acquire C
+				   /*
+				    * (No marking for typical locks)
+				    *
+				    * 1. Add 'B -> C' of TT type
+				    * 2. Queue C
+				    *
+				    * In pend_lock: B, C
+				    * In graph: 'B -> C'
+				    */
+   acquire E
+   /*
+    * (No marking for typical locks)
+    *
+    * 1. Queue E
+    *
+    * In pend_lock: D, E
+    * In graph: 'B -> C'
+    */
+				   acquire D
+				   /*
+				    * (No marking for typical locks)
+				    *
+				    * 1. Add 'C -> D' of TT type
+				    * 2. Queue D
+				    *
+				    * In pend_lock: B, C, D
+				    * In graph: 'B -> C', 'C -> D'
+				    */
+   release E
+   /*
+    * (No commit for typical locks)
+    *
+    * In pend_lock: D, E
+    * In graph: 'B -> C', 'C -> D'
+    */
+				   release D
+				   /*
+				    * (No commit for typical locks)
+				    *
+				    * In pend_lock: B, C, D
+				    * In graph: 'B -> C', 'C -> D'
+				    */
+   release AX
+   /*
+    * 1. Commit AX (= Add 'AX -> ?')
+    *   a. What queued since AX was marked: D, E
+    *   b. Add 'AX -> D' of CT type
+    *   c. Add 'AX -> E' of CT type
+    *
+    * In pend_lock: D, E
+    * In graph: 'B -> C', 'C -> D',
+    *           'AX -> D', 'AX -> E'
+    */
+				   release C
+				   /*
+				    * (No commit for typical locks)
+				    *
+				    * In pend_lock: B, C, D
+				    * In graph: 'B -> C', 'C -> D',
+				    *           'AX -> D', 'AX -> E'
+				    */
+
+				   release B
+				   /*
+				    * (No commit for typical locks)
+				    *
+				    * In pend_lock: B, C, D
+				    * In graph: 'B -> C', 'C -> D',
+				    *           'AX -> D', 'AX -> E'
+				    */
+
+   where AX, B, C,..., E are different lock classes, and a suffix 'X' is
+   added on crosslocks.
+
+When acquiring crosslock AX, crossrelease feature marks AX as started,
+which means all acquisitions from now are candidates which might create
+dependencies with AX. True dependencies will be determined when
+identifying the AX's release context.
+
+When acquiring typical lock B, lockdep queues B so that it can be used
+at commit step later since any crosslocks in progress might depends on B.
+The same thing is done on lock C, D and E. And then two dependencies
+'AX -> D' and 'AX -> E' are added at commit step, when identifying the
+AX's release context.
+
+The final graph is, with crossrelease feature using commit,
+
+   B -> C -
+           \
+            -> D
+           /
+       AX -
+           \
+            -> E
+
+   where AX, B, C,..., E are different lock classes, and a suffix 'X' is
+   added on crosslocks.
+
+However, without crossrelease feature, the final graph would be,
+
+   B -> C -> D
+
+   where B and C are different lock classes.
+
+The former graph has two more dependencies 'AX -> D' and 'AX -> E'
+giving additional chances to check if they cause deadlocks. This way
+lockdep can detect a deadlock or its possibility caused by crosslocks.
+Again, crossrelease feature does not affect the behavior of adding
+dependencies for typical locks.
+
+CONCLUSION
+
+Crossrelease works well for crosslock, thanks to commit step.
+
+
+=============
+Optimizations
+=============
+
+Avoid duplication
+-----------------
+
+Crossrelease feature uses a cache like what lockdep is already using for
+dependency chains, but this time it's for caching a dependency of CT
+type, crossing between two different context. Once that dependency is
+cached, same dependencies will never be added again. Queueing
+unnecessary locks is also prevented based on the cache.
+
+CONCLUSION
+
+Crossrelease does not add any duplicate dependencies.
+
+
+Lockless for hot paths
+----------------------
+
+To keep all typical locks for later use, crossrelease feature adopts a
+local array embedded in task_struct, which makes accesses to arrays
+lockless by forcing the accesses to happen only within the owner context.
+It's like how lockdep accesses held_locks. Lockless implmentation is
+important since typical locks are very frequently acquired and released.
+
+CONCLUSION
+
+Crossrelease is designed to use no lock for hot paths.
+
-- 
1.9.1