[RFC v2 13/13] lockdep: Add a document describing crossrelease feature

[Byungchul Park]

Crossrelease feature introduces new concept and data structure. Thus
the document is necessary. So added it.

Signed-off-by: Byungchul Park <byungchul.park@xxxxxxx>
---
 Documentation/locking/crossrelease.txt | 457 +++++++++++++++++++++++++++++++++
 1 file changed, 457 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..51b583b
--- /dev/null
+++ b/Documentation/locking/crossrelease.txt
@@ -0,0 +1,457 @@
+Crossrelease dependency check
+=============================
+
+Started by Byungchul Park <byungchul.park@xxxxxxx>
+
+Contents:
+
+ (*) Introduction.
+
+     - What the lockdep checks.
+
+ (*) What is a problem?
+
+     - Examples.
+     - Lockdep's assumption.
+     - Lockdep's limitation.
+
+ (*) How to solve the problem.
+
+     - What causes deadlock?
+     - Relax the assumption.
+     - Relax the limitation.
+
+ (*) Implementation.
+
+     - Introduce crosslock.
+     - Introduce commit stage.
+     - Acquire vs commit vs release.
+     - Data structures.
+
+ (*) Optimizations.
+
+
+============
+Introduction
+============
+
+What the lockdep checks
+-----------------------
+
+Lockdep checks dependency between locks and reports it if a deadlock
+possibility is detected in advance or if an actual deadlock occures at
+the time checking it.
+
+The former is more valuable because the possibility detection without
+lockdep is much harder. When an actual deadlock occures, we can identify
+what happens in the system by some means or other, even without lockdep.
+
+It checks dependency between locks (exactly lock classes, see
+Documentation/locking/lockdep-design.txt for more) and builds the
+relationship between them when the lock is acquired. Eventually it forms
+the global dependency graph which connects between related locks based
+on dependency they have, like e.g.
+
+A - B -       - F - G
+       \     /
+        - E -       - L
+       /     \     /
+C - D -       - H -
+                   \
+                    - I - K
+                   /
+                J -
+
+where A, B, C,..., L are different lock classes.
+
+Lockdep basically works based on this global dependency graph. The more
+nodes it has, the stronger check can be performed.
+
+For example, lockdep can detect a deadlock when acquiring a C class lock
+while it already held a K class lock, because it forms a cycle which
+means deadlock, like
+
+A - B -       - F - G
+       \     /
+        - E -       - L
+       /     \     /
+C - D -       - H -
+|                  \
+|                   - I - K
+|                  /      |
+|               J -       |
++-------------------------+
+
+where A, B, C,..., L are different lock classes.
+
+If any of nodes making up the cycle was not built into the graph, we
+cannot detect this kind of deadlock because there's no cycle. For
+example, it might be
+
+A - B -       - F - G
+       \     /
+        - E -       L
+       /
+C - D -
+|
+|                   - I - K
+|                  /      |
+|               J -       |
++-------------------------+
+
+where A, B, C,..., L are different lock classes.
+
+Adding nodes and edges gives us additional opportunity to check if it
+causes deadlock or not, so makes the detection stronger.
+
+
+=================
+What is a problem
+=================
+
+Examples
+--------
+
+Can we detect deadlocks descriped below, with lockdep? No.
+
+Example 1)
+
+	PROCESS X	PROCESS 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
+
+We are not checking the dependency for lock_page() at all now.
+
+Example 2)
+
+	PROCESS X	PROCESS Y	PROCESS Z
+	--------------	--------------	--------------
+			mutex_lock A
+	lock_page B
+			lock_page B
+					mutext_lock A // DEADLOCK
+					mutext_unlock A
+					unlock_page B
+					(B was held by PROCESS X)
+			unlock_page B
+			mutex_unlock A
+
+We cannot detect this kind of deadlock with lockdep, even though we
+apply the dependency check using lockdep on lock_page().
+
+Example 3)
+
+	PROCESS X	PROCESS Y
+	--------------	--------------
+			mutex_lock A
+	mutex_lock A
+	mutex_unlock A
+			wait_for_complete B // DEADLOCK
+	complete B
+			mutex_unlock A
+
+wait_for_complete() and complete() also can cause a deadlock, however
+we cannot detect it with lockdep, either.
+
+
+lockdep's assumption
+--------------------
+
+Lockdep (not crossrelease featured one) assumes that,
+
+	A lock will be unlocked within the context holding the lock.
+
+Thus we can say that a lock has dependency with all locks being already
+in held_locks. So we can check dependency and build the dependency graph
+when acquiring it.
+
+
+lockdep's limitation
+--------------------
+
+It can be applied only to typical lock operations, e.g. spin_lock,
+mutex and so on. However, e.g. lock_page() cannot play with the lockdep
+thingy because it violates assumptions of lockdep, even though it's
+considered as a lock for the page access.
+
+In the view point of lockdep, it must be released within the context
+which held the lock, however, the page lock can be released by different
+context from the context which held it. Another example,
+wait_for_complete() and complete() are also the case by nature, which
+the lockdep cannot deal with.
+
+
+========================
+How to solve the problem
+========================
+
+What causes deadlock
+--------------------
+
+Not only lock operations, but also any operations causing to wait or
+spin for something can cause deadlock unless it's eventually *released*
+by someone. The important point here is that the waiting or spinning
+must be *released* by someone. In other words, we have to focus whether
+the waiting or spinning can be *released* or not to check a deadlock
+possibility, rather than the waiting or spinning itself.
+
+In this point of view, typical lock is a special case where the acquire
+context is same as the release context, so no matter in which context
+the checking is performed for typical lock.
+
+Of course, in order to be able to report deadlock imediately at the time
+real deadlock actually occures, the checking must be performed before
+actual blocking or spinning happens when acquiring it. However, deadlock
+*possibility* can be detected and reported even the checking is done
+when releasing it, which means the time we can identify the release
+context.
+
+
+Relax the assumption
+--------------------
+
+Since whether waiting or spinning can be released or not is more
+important to check deadlock possibility as decribed above, we can relax
+the assumtion the lockdep has.
+
+	A lock can be unlocked in any context, unless the context
+	itself causes a deadlock e.g. acquiring a lock in irq-safe
+	context before releasing the lock in irq-unsafe context.
+
+A lock has dependency with all locks in the release context, having been
+held since the lock was held. Thus basically we can check the dependency
+only after we identify the release context at first. Of course, we can
+identify the release context at the time acquiring a lock for typical
+lock because the acquire context is same as the release context.
+
+However, generally if we cannot identify the release context at the time
+acquiring a lock, we have to wait until the lock having been held will
+be eventually released to identify the release context.
+
+
+Relax the limitation
+--------------------
+
+Given that the assumption is relaxed, we can check dependency and detect
+deadlock possibility not only for typical lock, but also for lock_page()
+using PG_locked, wait_for_xxx() and so on which might be released by
+different context from the context which held the lock.
+
+
+==============
+Implementation
+==============
+
+Introduce crosslock
+-------------------
+
+Crossrelease feature names a lock "crosslock" if it is releasable by a
+different context from the context which held the lock. All locks
+having been held in the context unlocking the crosslock, since the
+crosslock was held until eventually it's unlocked, have dependency with
+the crosslock. That's the key idea to implement crossrelease feature.
+
+
+Introduce commit stage
+----------------------
+
+Crossrelease feature names it "commit", to check dependency and build
+the dependency graph and chain in batches. Lockdep already performs what
+the commit does, when acquiring a lock. This way it works for typical
+lock, since it's guarrented that the acquire context is same as the
+release context for that. However, that way must be changed for
+crosslock so that it identify the release context when releasing the
+crosslock and then performs the commit.
+
+Let's demonstrate it though several examples.
+
+The below is how the current lockdep works for typical lock. Note that
+context 1 == context 2 for typical lock.
+
+	CONTEXT 1	CONTEXT 2
+	acquiring A	releasing A
+	-------------	-------------
+	acquire A	acquire A
+
+	acquire B	acquire B -> build "A - B"
+
+	acquire C	acquire C -> build "A - C"
+
+	release C	release C
+
+	release B	release B
+
+	release A	release A
+
+After building "A - B", the dependency graph forms like,
+
+A - B
+
+And after building "A - C", the dependency graph forms like,
+
+    - B
+   /
+A -
+   \
+    - C
+
+What if we apply the commit to lockdep for typical lock? Of course, it's
+not necessary for typical lock. Just a example for what the commit does.
+
+	CONTEXT 1	CONTEXT 2
+	acquiring A	releasing A
+	-------------	-------------
+	acquire A	acquire A -> mark A started
+
+	acquire B	acquire B -> queue B
+
+	acquire C	acquire C -> queue C
+
+	release C	release C
+
+	release B	release B
+
+	release A	release A -> commit A (build "A - B", "A - C")
+
+After commiting A, the dependency graph forms like, at a time
+
+    - B
+   /
+A -
+   \
+    - C
+
+Here we can see both the former and the latter end in building a same
+dependency graph consisting of "A - B" and "A - C". Of course, the
+former can build the graph earlier than the latter, which means the
+former can detect a deadlock sooner, maybe, as soon as possible. So the
+former would be prefered if possible.
+
+Let's look at the way the commit works for crosslock.
+
+	CONTEXT 1	CONTEXT 2
+	acquiring A	releasing A
+	-------------	-------------
+	lock A
+	acquire A -> mark A started
+
+	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ <- serialized by some means
+
+			acquire X -> queue X
+			lock X
+	acquire B
+			release X
+	acquire C
+			acquire Y -> queue Y
+	release C
+			release Y
+	release B
+			release A -> commit A (build "A - X", "A - Y")
+
+where A is a crosslock and the others are typical locks.
+
+Since a crosslock is held, it starts to queue all candidates whenever
+acquiring typical lock, and keep it until finally it will be released.
+Then it can commit all proper candidates queued until now. In other
+words, it checks dependency and builds the dependency graph and chain
+at the commit stage.
+
+And it is serialized so that the sequence, A -> X -> Y can be seen,
+using atomic operations and proper barriers.
+
+
+Acquire vs commit vs release
+----------------------------
+
+What the lockdep should do in each stage to make it work even for
+crosslock is like, (Note that it does not change any current logic
+by which lockdep works, but only adds additional detection capability.)
+
+1. Acquire
+
+	1) For typical lock
+
+		It's queued into additional data structure so that the
+		commit stage can check depedndency and build the
+		dependency graph and chain with this later.
+
+	2) For crosslock
+
+		It's added to the global linked list so that the commit
+		stage can check dependency and build the dependency
+		graph and chain with this later.
+
+2. Commit
+
+	1) For typical lock
+
+		N/A.
+
+	2) For crosslock
+
+		It checks dependency and builds the dependency graph and
+		chain with data saved in the acquire stage. Here, we
+		establish dependency between the crosslock we are
+		unlocking now and all locks in that context, having been
+		held since the lock was held. Of course, it avoids
+		unnecessary checking and building as far as possible.
+
+3. Release
+
+	1) For typical lock
+
+		No change.
+
+	2) For crosslock
+
+		Just remove this crosslock from the global linked list,
+		to which the crosslock was added at acquire stage.
+		Release operation should be used with commit operation
+		together for crosslock.
+
+
+Data structures
+---------------
+
+Crossrelease feature introduces two new data structures.
+
+1. pend_lock (or plock)
+
+	This is for keeping locks waiting to be committed so that the
+	actual dependency graph and chain can be built in the commit
+	stage. Every task_struct has a pend_lock array to keep these
+	locks. pend_lock entry will be consumed and filled whenever
+	lock_acquire() is called for typical lock and will be flushed,
+	namely committed at proper time. And this array is managed by
+	circular buffer mean.
+
+2. cross_lock (or xlock)
+
+	This keeps some additional data only for crosslock. One
+	instance exists per one crosslock's lockdep_map.
+	lockdep_init_map_crosslock() should be used instead of
+	lockdep_init_map() to use a lock as a crosslock.
+
+
+=============
+Optimizations
+=============
+
+Adding a pend_lock is an operation which very frequently happened
+because it happens whenever a typical lock is acquired. So the operation
+is implemented locklessly using rcu mechanism if possible. Unfortunitly,
+we cannot apply this optimization if any object managed by rcu e.g.
+xlock is on stack or somewhere else where it can be freed or destroyed
+unpredictably.
+
+And chain cache for crosslock is also used to avoid unnecessary checking
+and building dependency, like how the lockdep is already doing for that
+purpose for typical lock.
+
-- 
1.9.1