[PATCH] lockdep: Add a document describing crossrelease feature

[Byungchul Park]

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

Signed-off-by: Byungchul Park <byungchul.park@xxxxxxx>
---
 Documentation/locking/crossrelease.txt | 276 +++++++++++++++++++++++++++++++++
 1 file changed, 276 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..98851ef
--- /dev/null
+++ b/Documentation/locking/crossrelease.txt
@@ -0,0 +1,276 @@
+Crossrelease lock dependency check
+==================================
+
+Started by Byungchul Park <byungchul.park@xxxxxxx>
+
+Contents:
+
+ (*) What is a problem?
+
+     - Original lockdep's assumptions.
+     - Original lockdep's limitation.
+
+ (*) How to solve the problem.
+
+     - What causes deadlock?
+     - Relax the assumptions.
+     - Introduce "crosslock".
+     - Introduce "commit" stage.
+     - Acquire vs commit vs release
+
+ (*) Implementation.
+
+     - Data structures.
+     - Optimizations.
+
+
+=================
+What is a problem
+=================
+
+Can we detect deadlocks descriped below with original 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 currently not checking lock dependency for lock_page(), which is
+for exclusive access to pages.
+
+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 original lockdep, even
+though we enable lock dependency check 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 original lockdep, either.
+
+
+Original lockdep's assumptions
+------------------------------
+
+Original lockdep (not crossrelease featured lockdep) assumes that,
+
+1. A lock will be unlocked within the context holding the lock.
+2. A lock has dependency with all locks already held in held_locks.
+2. Acquiring is more important than releasing, to check its dependency.
+
+
+Original lockdep's limitation
+-----------------------------
+
+Therefore, the original lockdep has limitations. It can be applied only
+to typical lock operations, e.g. spin_lock, mutex, semaphore and the
+like. Even though lock_page() can be considered as a lock, it cannot be
+used with lockdep because it violates assumptions of original lockdep.
+In the view point of original lockdep, a lock must be released within
+the context having held the lock, however, a lock using lock_page() can
+be released by different context from the context having held the lock.
+wait_for_complete() is also the case by nature, in which original
+lockdep cannot deal with it.
+
+
+========================
+How to solve the problem
+========================
+
+What causes deadlock
+--------------------
+
+Not only lock operations, but also any operations causing to wait or
+spin it e.g. all wait operations for an event, lock_page() and so on
+can cause deadlock unless it's eventually released by someone. The most
+important point here is that the waiting or spinning must be *released*
+by someone. In other words, we have to focus whether the waiting and
+spinning can be *released* or not to avoid deadlock, rather than
+waiting or spinning it itself.
+
+
+Relax the assumptions
+---------------------
+
+We can relax the assumtions the original lockdep has, which is not
+necessary to check dependency and detect a deadlock.
+
+1. 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.
+
+2. A lock has dependency with all locks in the releasing context, having
+   been held since the lock was held. Thus we can check the dependency
+   only after we identify the releasing context at first. Of course,
+   if we consider only typical lock e.g. spin lock, mutex, semaphore
+   and so on, then we can identify the releasing context at the time
+   acquiring a lock because the releasing context is same as the
+   releasing context for the typical lock. However, generally we have to
+   wait until the lock having been held will be eventually released to
+   identify the releasing context. We can say that the original lockdep
+   is a special case among all cases this crossrelease feature can deal
+   with.
+
+3. Releasing is more important than acquiring to check its dependency.
+   Compare to the third assumption of original lockdep.
+
+
+Introduce "crosslock"
+---------------------
+
+Crossrelease feature names a lock "crosslock" if it is releasable by a
+different context from the context having acquired the lock. All locks
+having been held in the context unlocking the crosslock until
+eventually the crosslock will be 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 tree and chain. That is, the original lockdep is already
+doing the so-called commit, when acquiring it. In the strict sense, the
+checking and building must be done in the releasing context, as
+described in the "What causes a deadlock" subsection above. However, it
+will work no matter which context is used for typical lock, since it's
+guarrented that the acquiring context is same as the releasing context
+as described above. So we can commit it in the acquiring context for
+typical lock.
+
+How the original lockdep works:
+
+	acquire (including commit operation) -> release
+
+What if we consider a crosslock? For crosslock, the way lockdep works
+must be changed so that the releasing context is considered instead.
+Again, the releasing context is more important than the acquiring
+context, to check dependency and detect a deadlock. Thus checking
+dependency and building the dependency tree and chain, namely commit
+must be done in the releasing context, especially for crosslock.
+
+How the crossrelease lockdep works for crosslock:
+
+	acquire -> (context may be changed) -> commit -> release
+
+
+Acquire vs commit vs release
+----------------------------
+
+The things to do when acquiring and releasing a lock will be slightly
+changed in other to make lockdep can work even for crosslock. And an
+additional stage, commit, is placed between acquire and release.
+
+1. Acquire
+
+	1) For typical lock
+
+		The lock will be added not only to held_locks of the
+		current's task_struct, but also to additional structure
+		so that the commit stage can check dependency and build
+		the dependency tree and chain with that later.
+
+	2) For crosslock
+
+		The lock will be added to a global linked list so that
+		the commit stage can check dependency and build the
+		dependency tree and chain with that later.
+
+2. Commit
+
+	1) For typical lock
+
+		N/A.
+
+	2) For crosslock
+
+		It checks dependency and builds the dependency tree and
+		chain with data saved in the acquire stage. Here, we
+		establish dependency between the crosslock we are
+		unlocking now and all locks in the context unlocking it,
+		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 the target 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, in order to build a dependency
+		chain properly.
+
+
+==============
+Implementation
+==============
+
+Data structures
+---------------
+
+Crossrelease feature introduces two new data structures.
+
+1. pend_lock (== plock)
+
+	This is for keeping locks waiting to be committed so that the
+	actual dependency tree and chain is built in the commit stage.
+	Every task_struct has an pend_lock array to keep those 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.
+
+2. cross_lock (== xlock)
+
+	This keeps some additional data only for crosslock. One
+	cross_lock exists per one 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 very frequently happened because it
+happens whenever a typical lock is acquired. So the operation is
+implemented locklessly using rcu mechanism unless the xlock instance
+can be freed or destroyed unpredictably e.g. the instance is on stack.
+
+And chain cache for crosslock is also used to avoid unnecessary checking
+and building dependency, like how the original lockdep is doing for that
+purpose.
-- 
1.9.1