[RFC v2 00/13] lockdep: Implement crossrelease feature

[RFC v2 00/13] lockdep: Implement crossrelease feature

[Byungchul Park]

Change from v1
	- enhanced the document
	- removed save_stack_trace() optimizing patch
	- made this based on the seperated save_stack_trace patchset
	  https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1182242.html

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.

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.

Given that the assumption the current lockdep has 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.

My implementation makes it possible. See the last patch including the
document for more information.

---

Byungchul Park (13):
  lockdep: Refactor lookup_chain_cache()
  lockdep: Add a function building a chain between two hlocks
  lockdep: Make check_prev_add can use a stack_trace of other context
  lockdep: Make save_trace can copy from other stack_trace
  lockdep: Implement crossrelease feature
  lockdep: Apply crossrelease to completion
  pagemap.h: Remove trailing white space
  lockdep: Apply crossrelease to PG_locked lock
  cifs/file.c: Remove trailing white space
  mm/swap_state.c: Remove trailing white space
  lockdep: Call lock_acquire(release) when accessing PG_locked manually
  lockdep: Make crossrelease use save_stack_trace_norm() instead
  lockdep: Add a document describing crossrelease feature

 Documentation/locking/crossrelease.txt | 457 ++++++++++++++++++
 fs/cifs/file.c                         |   6 +-
 include/linux/completion.h             | 121 ++++-
 include/linux/irqflags.h               |  16 +-
 include/linux/lockdep.h                | 139 ++++++
 include/linux/mm_types.h               |   9 +
 include/linux/pagemap.h                | 104 +++-
 include/linux/sched.h                  |   5 +
 kernel/fork.c                          |   4 +
 kernel/locking/lockdep.c               | 852 ++++++++++++++++++++++++++++++---
 kernel/sched/completion.c              |  55 ++-
 lib/Kconfig.debug                      |  30 ++
 mm/filemap.c                           |  10 +-
 mm/ksm.c                               |   1 +
 mm/migrate.c                           |   1 +
 mm/page_alloc.c                        |   3 +
 mm/shmem.c                             |   2 +
 mm/swap_state.c                        |  12 +-
 mm/vmscan.c                            |   1 +
 19 files changed, 1706 insertions(+), 122 deletions(-)
 create mode 100644 Documentation/locking/crossrelease.txt

-- 
1.9.1

[RFC v2 01/13] lockdep: Refactor lookup_chain_cache()

[Byungchul Park]

Currently, lookup_chain_cache() provides both "lookup" and "add"
functionalities in a function. However each one is useful indivisually.
Some features, e.g. crossrelease, can use each one indivisually.
Thus, splited these functionalities into 2 functions.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/locking/lockdep.c | 125 ++++++++++++++++++++++++++++++-----------------
 1 file changed, 79 insertions(+), 46 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 716547f..efd001c 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2010,15 +2010,9 @@ struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
 	return lock_classes + chain_hlocks[chain->base + i];
 }
 
-/*
- * Look up a dependency chain. If the key is not present yet then
- * add it and return 1 - in this case the new dependency chain is
- * validated. If the key is already hashed, return 0.
- * (On return with 1 graph_lock is held.)
- */
-static inline int lookup_chain_cache(struct task_struct *curr,
-				     struct held_lock *hlock,
-				     u64 chain_key)
+static inline int add_chain_cache(struct task_struct *curr,
+				  struct held_lock *hlock,
+				  u64 chain_key)
 {
 	struct lock_class *class = hlock_class(hlock);
 	struct hlist_head *hash_head = chainhashentry(chain_key);
@@ -2027,46 +2021,18 @@ static inline int lookup_chain_cache(struct task_struct *curr,
 	int i, j;
 
 	/*
+	 * Allocate a new chain entry from the static array, and add
+	 * it to the hash:
+	 */
+
+	/*
 	 * We might need to take the graph lock, ensure we've got IRQs
 	 * disabled to make this an IRQ-safe lock.. for recursion reasons
 	 * lockdep won't complain about its own locking errors.
 	 */
 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
 		return 0;
-	/*
-	 * We can walk it lock-free, because entries only get added
-	 * to the hash:
-	 */
-	hlist_for_each_entry_rcu(chain, hash_head, entry) {
-		if (chain->chain_key == chain_key) {
-cache_hit:
-			debug_atomic_inc(chain_lookup_hits);
-			if (very_verbose(class))
-				printk("\nhash chain already cached, key: "
-					"%016Lx tail class: [%p] %s\n",
-					(unsigned long long)chain_key,
-					class->key, class->name);
-			return 0;
-		}
-	}
-	if (very_verbose(class))
-		printk("\nnew hash chain, key: %016Lx tail class: [%p] %s\n",
-			(unsigned long long)chain_key, class->key, class->name);
-	/*
-	 * Allocate a new chain entry from the static array, and add
-	 * it to the hash:
-	 */
-	if (!graph_lock())
-		return 0;
-	/*
-	 * We have to walk the chain again locked - to avoid duplicates:
-	 */
-	hlist_for_each_entry(chain, hash_head, entry) {
-		if (chain->chain_key == chain_key) {
-			graph_unlock();
-			goto cache_hit;
-		}
-	}
+
 	if (unlikely(nr_lock_chains >= MAX_LOCKDEP_CHAINS)) {
 		if (!debug_locks_off_graph_unlock())
 			return 0;
@@ -2102,6 +2068,72 @@ cache_hit:
 	return 1;
 }
 
+/*
+ * Look up a dependency chain.
+ */
+static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
+{
+	struct hlist_head *hash_head = chainhashentry(chain_key);
+	struct lock_chain *chain;
+
+	/*
+	 * We can walk it lock-free, because entries only get added
+	 * to the hash:
+	 */
+	hlist_for_each_entry_rcu(chain, hash_head, entry) {
+		if (chain->chain_key == chain_key) {
+			debug_atomic_inc(chain_lookup_hits);
+			return chain;
+		}
+	}
+	return NULL;
+}
+
+/*
+ * If the key is not present yet in dependency chain cache then
+ * add it and return 1 - in this case the new dependency chain is
+ * validated. If the key is already hashed, return 0.
+ * (On return with 1 graph_lock is held.)
+ */
+static inline int lookup_chain_cache_add(struct task_struct *curr,
+					 struct held_lock *hlock,
+					 u64 chain_key)
+{
+	struct lock_class *class = hlock_class(hlock);
+	struct lock_chain *chain = lookup_chain_cache(chain_key);
+
+	if (chain) {
+cache_hit:
+		if (very_verbose(class))
+			printk("\nhash chain already cached, key: "
+					"%016Lx tail class: [%p] %s\n",
+					(unsigned long long)chain_key,
+					class->key, class->name);
+		return 0;
+	}
+
+	if (very_verbose(class))
+		printk("\nnew hash chain, key: %016Lx tail class: [%p] %s\n",
+			(unsigned long long)chain_key, class->key, class->name);
+
+	if (!graph_lock())
+		return 0;
+
+	/*
+	 * We have to walk the chain again locked - to avoid duplicates:
+	 */
+	chain = lookup_chain_cache(chain_key);
+	if (chain) {
+		graph_unlock();
+		goto cache_hit;
+	}
+
+	if (!add_chain_cache(curr, hlock, chain_key))
+		return 0;
+
+	return 1;
+}
+
 static int validate_chain(struct task_struct *curr, struct lockdep_map *lock,
 		struct held_lock *hlock, int chain_head, u64 chain_key)
 {
@@ -2112,11 +2144,11 @@ static int validate_chain(struct task_struct *curr, struct lockdep_map *lock,
 	 *
 	 * We look up the chain_key and do the O(N^2) check and update of
 	 * the dependencies only if this is a new dependency chain.
-	 * (If lookup_chain_cache() returns with 1 it acquires
+	 * (If lookup_chain_cache_add() return with 1 it acquires
 	 * graph_lock for us)
 	 */
 	if (!hlock->trylock && hlock->check &&
-	    lookup_chain_cache(curr, hlock, chain_key)) {
+	    lookup_chain_cache_add(curr, hlock, chain_key)) {
 		/*
 		 * Check whether last held lock:
 		 *
@@ -2147,9 +2179,10 @@ static int validate_chain(struct task_struct *curr, struct lockdep_map *lock,
 		if (!chain_head && ret != 2)
 			if (!check_prevs_add(curr, hlock))
 				return 0;
+
 		graph_unlock();
 	} else
-		/* after lookup_chain_cache(): */
+		/* after lookup_chain_cache_add(): */
 		if (unlikely(!debug_locks))
 			return 0;
 
-- 
1.9.1

[RFC v2 02/13] lockdep: Add a function building a chain between two hlocks

[Byungchul Park]

add_chain_cache() can only be used by current context since it
depends on a task's held_locks which is not protected by lock.
However, it would be useful if a dependency chain can be built
in any context. This patch makes the chain building not depend
on its context.

Especially, crossrelease feature wants to do this. Crossrelease
feature introduces a additional dependency chain consisting of 2
lock classes using 2 hlock instances, to connect dependency
between different contexts.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/locking/lockdep.c | 57 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 57 insertions(+)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index efd001c..4d51208 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2010,6 +2010,63 @@ struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
 	return lock_classes + chain_hlocks[chain->base + i];
 }
 
+/*
+ * This can make it possible to build a chain between just two
+ * specified hlocks rather than between already held locks of
+ * the current task and newly held lock, which can be done by
+ * add_chain_cache().
+ *
+ * add_chain_cache() must be done within the lock owner's context,
+ * however this can be called in any context if two racy-less hlock
+ * instances were already taken by caller. Thus this can be useful
+ * when building a chain between two hlocks regardless of context.
+ */
+static inline int add_chain_cache_2hlocks(struct held_lock *prev,
+					  struct held_lock *next,
+					  u64 chain_key)
+{
+	struct hlist_head *hash_head = chainhashentry(chain_key);
+	struct lock_chain *chain;
+
+	/*
+	 * Allocate a new chain entry from the static array, and add
+	 * it to the hash:
+	 */
+
+	/*
+	 * We might need to take the graph lock, ensure we've got IRQs
+	 * disabled to make this an IRQ-safe lock.. for recursion reasons
+	 * lockdep won't complain about its own locking errors.
+	 */
+	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
+		return 0;
+
+	if (unlikely(nr_lock_chains >= MAX_LOCKDEP_CHAINS)) {
+		if (!debug_locks_off_graph_unlock())
+			return 0;
+
+		print_lockdep_off("BUG: MAX_LOCKDEP_CHAINS too low!");
+		dump_stack();
+		return 0;
+	}
+
+	chain = lock_chains + nr_lock_chains++;
+	chain->chain_key = chain_key;
+	chain->irq_context = next->irq_context;
+	chain->depth = 2;
+	if (likely(nr_chain_hlocks + chain->depth <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
+		chain->base = nr_chain_hlocks;
+		nr_chain_hlocks += chain->depth;
+		chain_hlocks[chain->base] = prev->class_idx - 1;
+		chain_hlocks[chain->base + 1] = next->class_idx -1;
+	}
+	hlist_add_head_rcu(&chain->entry, hash_head);
+	debug_atomic_inc(chain_lookup_misses);
+	inc_chains();
+
+	return 1;
+}
+
 static inline int add_chain_cache(struct task_struct *curr,
 				  struct held_lock *hlock,
 				  u64 chain_key)
-- 
1.9.1

[RFC v2 03/13] lockdep: Make check_prev_add can use a stack_trace of other context

[Byungchul Park]

Currently, check_prev_add() can only save its current context's stack
trace. But it would be useful if a seperated stack_trace can be taken
and used in check_prev_add(). Crossrelease feature can use
check_prev_add() with another context's stack_trace.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/locking/lockdep.c | 16 +++++++++-------
 1 file changed, 9 insertions(+), 7 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 4d51208..c596bef 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1822,7 +1822,8 @@ check_deadlock(struct task_struct *curr, struct held_lock *next,
  */
 static int
 check_prev_add(struct task_struct *curr, struct held_lock *prev,
-	       struct held_lock *next, int distance, int *stack_saved)
+	       struct held_lock *next, int distance, int *stack_saved,
+	       struct stack_trace *own_trace)
 {
 	struct lock_list *entry;
 	int ret;
@@ -1883,7 +1884,7 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 		}
 	}
 
-	if (!*stack_saved) {
+	if (!own_trace && stack_saved && !*stack_saved) {
 		if (!save_trace(&trace))
 			return 0;
 		*stack_saved = 1;
@@ -1895,14 +1896,14 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 	 */
 	ret = add_lock_to_list(hlock_class(prev), hlock_class(next),
 			       &hlock_class(prev)->locks_after,
-			       next->acquire_ip, distance, &trace);
+			       next->acquire_ip, distance, own_trace ?: &trace);
 
 	if (!ret)
 		return 0;
 
 	ret = add_lock_to_list(hlock_class(next), hlock_class(prev),
 			       &hlock_class(next)->locks_before,
-			       next->acquire_ip, distance, &trace);
+			       next->acquire_ip, distance, own_trace ?: &trace);
 	if (!ret)
 		return 0;
 
@@ -1911,7 +1912,8 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 	 */
 	if (verbose(hlock_class(prev)) || verbose(hlock_class(next))) {
 		/* We drop graph lock, so another thread can overwrite trace. */
-		*stack_saved = 0;
+		if (stack_saved)
+			*stack_saved = 0;
 		graph_unlock();
 		printk("\n new dependency: ");
 		print_lock_name(hlock_class(prev));
@@ -1960,8 +1962,8 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)
 		 * added:
 		 */
 		if (hlock->read != 2 && hlock->check) {
-			if (!check_prev_add(curr, hlock, next,
-						distance, &stack_saved))
+			if (!check_prev_add(curr, hlock, next, distance,
+						&stack_saved, NULL))
 				return 0;
 			/*
 			 * Stop after the first non-trylock entry,
-- 
1.9.1

[RFC v2 04/13] lockdep: Make save_trace can copy from other stack_trace

[Byungchul Park]

Currently, save_trace() can only save current context's stack trace.
However, it would be useful if it can save(copy from) another context's
stack trace. Especially, it can be used by crossrelease feature.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/locking/lockdep.c | 22 ++++++++++++++--------
 1 file changed, 14 insertions(+), 8 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index c596bef..b03014b 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -389,7 +389,7 @@ static void print_lockdep_off(const char *bug_msg)
 #endif
 }
 
-static int save_trace(struct stack_trace *trace)
+static int save_trace(struct stack_trace *trace, struct stack_trace *copy)
 {
 	trace->nr_entries = 0;
 	trace->max_entries = MAX_STACK_TRACE_ENTRIES - nr_stack_trace_entries;
@@ -397,7 +397,13 @@ static int save_trace(struct stack_trace *trace)
 
 	trace->skip = 3;
 
-	save_stack_trace(trace);
+	if (copy) {
+		trace->nr_entries = min(copy->nr_entries, trace->max_entries);
+		trace->skip = copy->skip;
+		memcpy(trace->entries, copy->entries,
+				trace->nr_entries * sizeof(unsigned long));
+	} else
+		save_stack_trace(trace);
 
 	/*
 	 * Some daft arches put -1 at the end to indicate its a full trace.
@@ -1201,7 +1207,7 @@ static noinline int print_circular_bug(struct lock_list *this,
 	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
 		return 0;
 
-	if (!save_trace(&this->trace))
+	if (!save_trace(&this->trace, NULL))
 		return 0;
 
 	depth = get_lock_depth(target);
@@ -1547,13 +1553,13 @@ print_bad_irq_dependency(struct task_struct *curr,
 
 	printk("\nthe dependencies between %s-irq-safe lock", irqclass);
 	printk(" and the holding lock:\n");
-	if (!save_trace(&prev_root->trace))
+	if (!save_trace(&prev_root->trace, NULL))
 		return 0;
 	print_shortest_lock_dependencies(backwards_entry, prev_root);
 
 	printk("\nthe dependencies between the lock to be acquired");
 	printk(" and %s-irq-unsafe lock:\n", irqclass);
-	if (!save_trace(&next_root->trace))
+	if (!save_trace(&next_root->trace, NULL))
 		return 0;
 	print_shortest_lock_dependencies(forwards_entry, next_root);
 
@@ -1885,7 +1891,7 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 	}
 
 	if (!own_trace && stack_saved && !*stack_saved) {
-		if (!save_trace(&trace))
+		if (!save_trace(&trace, NULL))
 			return 0;
 		*stack_saved = 1;
 	}
@@ -2436,7 +2442,7 @@ print_irq_inversion_bug(struct task_struct *curr,
 	lockdep_print_held_locks(curr);
 
 	printk("\nthe shortest dependencies between 2nd lock and 1st lock:\n");
-	if (!save_trace(&root->trace))
+	if (!save_trace(&root->trace, NULL))
 		return 0;
 	print_shortest_lock_dependencies(other, root);
 
@@ -3015,7 +3021,7 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 
 	hlock_class(this)->usage_mask |= new_mask;
 
-	if (!save_trace(hlock_class(this)->usage_traces + new_bit))
+	if (!save_trace(hlock_class(this)->usage_traces + new_bit, NULL))
 		return 0;
 
 	switch (new_bit) {
-- 
1.9.1

[RFC v2 05/13] lockdep: Implement crossrelease feature

[Byungchul Park]

Crossrelease feature calls a lock "crosslock" if it is releasable
by a different context from the context which held the lock. For
crosslock, all locks having been held in the context unlocking the
crosslock, until eventually the crosslock will be unlocked, have
dependency with the crosslock.

Using crossrelease feature, we can detect deadlock possibility even
for lock_page(), wait_for_complete() and so on.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 include/linux/irqflags.h |  16 +-
 include/linux/lockdep.h  | 139 +++++++++++
 include/linux/sched.h    |   5 +
 kernel/fork.c            |   4 +
 kernel/locking/lockdep.c | 632 +++++++++++++++++++++++++++++++++++++++++++++--
 lib/Kconfig.debug        |  13 +
 6 files changed, 791 insertions(+), 18 deletions(-)

diff --git a/include/linux/irqflags.h b/include/linux/irqflags.h
index 5dd1272..83eebe1 100644
--- a/include/linux/irqflags.h
+++ b/include/linux/irqflags.h
@@ -23,10 +23,18 @@
 # define trace_softirq_context(p)	((p)->softirq_context)
 # define trace_hardirqs_enabled(p)	((p)->hardirqs_enabled)
 # define trace_softirqs_enabled(p)	((p)->softirqs_enabled)
-# define trace_hardirq_enter()	do { current->hardirq_context++; } while (0)
-# define trace_hardirq_exit()	do { current->hardirq_context--; } while (0)
-# define lockdep_softirq_enter()	do { current->softirq_context++; } while (0)
-# define lockdep_softirq_exit()	do { current->softirq_context--; } while (0)
+# define trace_hardirq_enter()		\
+do {					\
+	current->hardirq_context++;	\
+	crossrelease_hardirq_start();	\
+} while (0)
+# define trace_hardirq_exit()		do { current->hardirq_context--; } while (0)
+# define lockdep_softirq_enter()	\
+do {					\
+	current->softirq_context++;	\
+	crossrelease_softirq_start();	\
+} while (0)
+# define lockdep_softirq_exit()		do { current->softirq_context--; } while (0)
 # define INIT_TRACE_IRQFLAGS	.softirqs_enabled = 1,
 #else
 # define trace_hardirqs_on()		do { } while (0)
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 4dca42f..1bf513e 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -108,6 +108,19 @@ struct lock_class {
 	unsigned long			contention_point[LOCKSTAT_POINTS];
 	unsigned long			contending_point[LOCKSTAT_POINTS];
 #endif
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+	/*
+	 * A flag to check if this lock class is releasable in
+	 * a differnet context from the context acquiring it.
+	 */
+	int				crosslock;
+
+	/*
+	 * When building a dependency chain, this help any classes
+	 * already established the chain can be skipped.
+	 */
+	unsigned int			skip_gen_id;
+#endif
 };
 
 #ifdef CONFIG_LOCK_STAT
@@ -143,6 +156,9 @@ struct lock_class_stats lock_stats(struct lock_class *class);
 void clear_lock_stats(struct lock_class *class);
 #endif
 
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+struct cross_lock;
+#endif
 /*
  * Map the lock object (the lock instance) to the lock-class object.
  * This is embedded into specific lock instances:
@@ -155,6 +171,15 @@ struct lockdep_map {
 	int				cpu;
 	unsigned long			ip;
 #endif
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+	struct cross_lock		*xlock;
+
+	/*
+	 * A flag to check if this lockdep_map is releasable in
+	 * a differnet context from the context acquiring it.
+	 */
+	int				cross;
+#endif
 };
 
 static inline void lockdep_copy_map(struct lockdep_map *to,
@@ -256,8 +281,90 @@ struct held_lock {
 	unsigned int hardirqs_off:1;
 	unsigned int references:12;					/* 32 bits */
 	unsigned int pin_count;
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+	/*
+	 * This is used to find out the first lock acquired since
+	 * a crosslock was held. In the crossrelease feature, we
+	 * build and use a dependency chain between the crosslock
+	 * and the first normal(non-crosslock) lock acquired
+	 * since the crosslock was held.
+	 */
+	unsigned int gen_id;
+#endif
 };
 
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+#define MAX_PLOCK_TRACE_ENTRIES		5
+
+/*
+ * This is for keeping locks waiting to commit those
+ * so that an actual dependency chain is built, when
+ * commiting a crosslock.
+ *
+ * Every task_struct has an array of this pending lock
+ * to keep those locks. These pending locks will be
+ * added whenever lock_acquire() is called for
+ * normal(non-crosslock) lock and will be
+ * flushed(committed) at proper time.
+ */
+struct pend_lock {
+	/*
+	 * This is used to find out the first lock acquired since
+	 * a crosslock was held. In the crossrelease feature, we
+	 * build and use a dependency chain between the crosslock
+	 * and the first normal(non-crosslock) lock acquired
+	 * since the crosslock was held.
+	 */
+	unsigned int		prev_gen_id;
+	unsigned int		gen_id;
+
+	int			hardirq_context;
+	int			softirq_context;
+
+	/*
+	 * Whenever irq occures, these ids will be updated so that
+	 * we can distinguish each irq context uniquely.
+	 */
+	unsigned int		hardirq_id;
+	unsigned int		softirq_id;
+
+	/*
+	 * Seperated stack_trace data. This will be used when
+	 * building a dependency chain for a crosslock, say,
+	 * commit.
+	 */
+	struct stack_trace	trace;
+	unsigned long		trace_entries[MAX_PLOCK_TRACE_ENTRIES];
+
+	/*
+	 * Seperated hlock instance. This will be used when
+	 * building a dependency chain for a crosslock, say,
+	 * commit.
+	 */
+	struct held_lock	hlock;
+};
+
+/*
+ * One cross_lock per one lockdep_map. For crosslock,
+ * lockdep_init_map_crosslock() should be used instead of
+ * lockdep_init_map(), where the pointer of this cross_lock
+ * instance should be passed as a parameter.
+ */
+struct cross_lock {
+	unsigned int		gen_id;
+	struct list_head	xlock_entry;
+
+	/*
+	 * Seperated hlock instance. This will be used when
+	 * building a dependency chain for a crosslock, say,
+	 * commit.
+	 */
+	struct held_lock	hlock;
+
+	int			ref; /* reference count */
+};
+#endif
+
 /*
  * Initialization, self-test and debugging-output methods:
  */
@@ -280,6 +387,34 @@ extern void lockdep_on(void);
 extern void lockdep_init_map(struct lockdep_map *lock, const char *name,
 			     struct lock_class_key *key, int subclass);
 
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+extern void lockdep_init_map_crosslock(struct lockdep_map *lock,
+				       struct cross_lock *xlock,
+				       const char *name,
+				       struct lock_class_key *key,
+				       int subclass);
+extern void lock_commit_crosslock(struct lockdep_map *lock);
+
+/*
+ * A member which we essencially have to initialize is ref.
+ * Other members will be initialized in add_xlock().
+ */
+#define STATIC_CROSS_LOCK_INIT() \
+	{ .ref = 0,}
+
+#define STATIC_CROSS_LOCKDEP_MAP_INIT(_name, _key, _xlock) \
+	{ .name = (_name), .key = (void *)(_key), .xlock = (_xlock), .cross = 1, }
+
+/*
+ * To initialize a lockdep_map statically use this macro.
+ * Note that _name must not be NULL.
+ */
+#define STATIC_LOCKDEP_MAP_INIT(_name, _key) \
+	{ .name = (_name), .key = (void *)(_key), .xlock = NULL, .cross = 0, }
+
+extern void crossrelease_hardirq_start(void);
+extern void crossrelease_softirq_start(void);
+#else
 /*
  * To initialize a lockdep_map statically use this macro.
  * Note that _name must not be NULL.
@@ -287,6 +422,10 @@ extern void lockdep_init_map(struct lockdep_map *lock, const char *name,
 #define STATIC_LOCKDEP_MAP_INIT(_name, _key) \
 	{ .name = (_name), .key = (void *)(_key), }
 
+void crossrelease_hardirq_start(void) {}
+void crossrelease_softirq_start(void) {}
+#endif
+
 /*
  * Reinitialize a lock key - for cases where there is special locking or
  * special initialization of locks so that the validator gets the scope
diff --git a/include/linux/sched.h b/include/linux/sched.h
index a10494a..6e45761 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1644,6 +1644,11 @@ struct task_struct {
 	struct held_lock held_locks[MAX_LOCK_DEPTH];
 	gfp_t lockdep_reclaim_gfp;
 #endif
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+#define MAX_PLOCKS_NR 1024UL
+	int plock_index;
+	struct pend_lock plocks[MAX_PLOCKS_NR];
+#endif
 #ifdef CONFIG_UBSAN
 	unsigned int in_ubsan;
 #endif
diff --git a/kernel/fork.c b/kernel/fork.c
index 2e391c7..eb18c47 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1404,6 +1404,10 @@ static struct task_struct *copy_process(unsigned long clone_flags,
 	p->lockdep_depth = 0; /* no locks held yet */
 	p->curr_chain_key = 0;
 	p->lockdep_recursion = 0;
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+	p->plock_index = 0;
+	memset(p->plocks, 0x0, sizeof(struct pend_lock) * MAX_PLOCKS_NR);
+#endif
 #endif
 
 #ifdef CONFIG_DEBUG_MUTEXES
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index b03014b..12903f9 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -739,6 +739,20 @@ look_up_lock_class(struct lockdep_map *lock, unsigned int subclass)
 	return NULL;
 }
 
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+static int cross_class(struct lock_class *class);
+static void init_map_noncrosslock(struct lockdep_map *lock);
+static void init_class_crosslock(struct lock_class *class, int cross);
+static int lock_acquire_crosslock(struct held_lock *hlock);
+static int lock_release_crosslock(struct lockdep_map *lock);
+#else
+static inline int cross_class(struct lock_class *class) { return 0; }
+static inline void init_map_noncrosslock(struct lockdep_map *lock) {}
+static inline void init_class_crosslock(struct lock_class *class, int cross) {}
+static inline int lock_acquire_crosslock(struct held_lock *hlock) { return 0; }
+static inline int lock_release_crosslock(struct lockdep_map *lock) { return 0; }
+#endif
+
 /*
  * Register a lock's class in the hash-table, if the class is not present
  * yet. Otherwise we look it up. We cache the result in the lock object
@@ -807,6 +821,7 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
 	INIT_LIST_HEAD(&class->locks_before);
 	INIT_LIST_HEAD(&class->locks_after);
 	class->name_version = count_matching_names(class);
+	init_class_crosslock(class, lock->cross);
 	/*
 	 * We use RCU's safe list-add method to make
 	 * parallel walking of the hash-list safe:
@@ -1799,6 +1814,9 @@ check_deadlock(struct task_struct *curr, struct held_lock *next,
 		if (nest)
 			return 2;
 
+		if (cross_class(hlock_class(prev)))
+			continue;
+
 		return print_deadlock_bug(curr, prev, next);
 	}
 	return 1;
@@ -1964,21 +1982,27 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)
 		int distance = curr->lockdep_depth - depth + 1;
 		hlock = curr->held_locks + depth - 1;
 		/*
-		 * Only non-recursive-read entries get new dependencies
-		 * added:
+		 * Only non-crosslock entries get new dependencies added.
+		 * Crosslock entries will be added by commiting later:
 		 */
-		if (hlock->read != 2 && hlock->check) {
-			if (!check_prev_add(curr, hlock, next, distance,
-						&stack_saved, NULL))
-				return 0;
+		if (!cross_class(hlock_class(hlock))) {
 			/*
-			 * Stop after the first non-trylock entry,
-			 * as non-trylock entries have added their
-			 * own direct dependencies already, so this
-			 * lock is connected to them indirectly:
+			 * Only non-recursive-read entries get new dependencies
+			 * added:
 			 */
-			if (!hlock->trylock)
-				break;
+			if (hlock->read != 2 && hlock->check) {
+				if (!check_prev_add(curr, hlock, next, distance,
+							&stack_saved, NULL))
+					return 0;
+				/*
+				 * Stop after the first non-trylock entry,
+				 * as non-trylock entries have added their
+				 * own direct dependencies already, so this
+				 * lock is connected to them indirectly:
+				 */
+				if (!hlock->trylock)
+					break;
+			}
 		}
 		depth--;
 		/*
@@ -3064,7 +3088,7 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 /*
  * Initialize a lock instance's lock-class mapping info:
  */
-void lockdep_init_map(struct lockdep_map *lock, const char *name,
+static void __lockdep_init_map(struct lockdep_map *lock, const char *name,
 		      struct lock_class_key *key, int subclass)
 {
 	int i;
@@ -3122,8 +3146,27 @@ void lockdep_init_map(struct lockdep_map *lock, const char *name,
 		raw_local_irq_restore(flags);
 	}
 }
+
+void lockdep_init_map(struct lockdep_map *lock, const char *name,
+		      struct lock_class_key *key, int subclass)
+{
+	init_map_noncrosslock(lock);
+	__lockdep_init_map(lock, name, key, subclass);
+}
 EXPORT_SYMBOL_GPL(lockdep_init_map);
 
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+static void init_map_crosslock(struct lockdep_map *lock, struct cross_lock *xlock);
+void lockdep_init_map_crosslock(struct lockdep_map *lock,
+		      struct cross_lock *xlock, const char *name,
+		      struct lock_class_key *key, int subclass)
+{
+	init_map_crosslock(lock, xlock);
+	__lockdep_init_map(lock, name, key, subclass);
+}
+EXPORT_SYMBOL_GPL(lockdep_init_map_crosslock);
+#endif
+
 struct lock_class_key __lockdep_no_validate__;
 EXPORT_SYMBOL_GPL(__lockdep_no_validate__);
 
@@ -3227,7 +3270,8 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 
 	class_idx = class - lock_classes + 1;
 
-	if (depth) {
+	/* TODO: nest_lock is not implemented for crosslock yet. */
+	if (depth && !cross_class(class)) {
 		hlock = curr->held_locks + depth - 1;
 		if (hlock->class_idx == class_idx && nest_lock) {
 			if (hlock->references)
@@ -3308,6 +3352,9 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	if (!validate_chain(curr, lock, hlock, chain_head, chain_key))
 		return 0;
 
+	if (lock_acquire_crosslock(hlock))
+		return 1;
+
 	curr->curr_chain_key = chain_key;
 	curr->lockdep_depth++;
 	check_chain_key(curr);
@@ -3476,6 +3523,9 @@ __lock_release(struct lockdep_map *lock, int nested, unsigned long ip)
 	if (unlikely(!debug_locks))
 		return 0;
 
+	if (lock_release_crosslock(lock))
+		return 1;
+
 	depth = curr->lockdep_depth;
 	/*
 	 * So we're all set to release this lock.. wait what lock? We don't
@@ -4396,3 +4446,557 @@ void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
 	dump_stack();
 }
 EXPORT_SYMBOL_GPL(lockdep_rcu_suspicious);
+
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+
+/*
+ * Crossrelease feature call a lock which is releasable by a
+ * different context from the context having acquired the lock,
+ * crosslock. For crosslock, all locks being held in the context
+ * unlocking the crosslock, until eventually the crosslock will
+ * be unlocked, have dependency with the crosslock. That's a key
+ * idea to implement crossrelease feature.
+ *
+ * Crossrelease feature introduces 2 new data structures.
+ *
+ * 1. pend_lock (== plock)
+ *
+ *	This is for keeping locks waiting to commit those so
+ *	that an actual dependency chain is built, when commiting
+ *	a crosslock.
+ *
+ *	Every task_struct has an array of this pending lock to
+ *	keep those locks. These pending locks will be added
+ *	whenever lock_acquire() is called for normal(non-crosslock)
+ *	lock and will be flushed(committed) at proper time.
+ *
+ * 2. cross_lock (== xlock)
+ *
+ *	This keeps some additional data only for crosslock. There
+ *	is one cross_lock per one lockdep_map for crosslock.
+ *	lockdep_init_map_crosslock() should be used instead of
+ *	lockdep_init_map() to use the lock as a crosslock.
+ *
+ * Acquiring and releasing sequence for crossrelease feature:
+ *
+ * 1. Acquire
+ *
+ *	All validation check is performed for all locks.
+ *
+ *	1) For non-crosslock (normal lock)
+ *
+ *		The hlock will be added not only to held_locks
+ *		of the current's task_struct, but also to
+ *		pend_lock array of the task_struct, so that
+ *		a dependency chain can be built with the lock
+ *		when doing commit.
+ *
+ *	2) For crosslock
+ *
+ *		The hlock will be added only to the cross_lock
+ *		of the lock's lockdep_map instead of held_locks,
+ *		so that a dependency chain can be built with
+ *		the lock when doing commit. And this lock is
+ *		added to the xlocks_head list.
+ *
+ * 2. Commit (only for crosslock)
+ *
+ *	This establishes a dependency chain between the lock
+ *	unlocking it now and all locks having held in the context
+ *	unlocking it since the lock was held, even though it tries
+ *	to avoid building a chain unnecessarily as far as possible.
+ *
+ * 3. Release
+ *
+ *	1) For non-crosslock (normal lock)
+ *
+ *		No change.
+ *
+ *	2) For crosslock
+ *
+ *		Just Remove the lock from xlocks_head list. Release
+ *		operation should be used with commit operation
+ *		together for crosslock, in order to build a
+ *		dependency chain properly.
+ */
+
+static LIST_HEAD(xlocks_head);
+
+/*
+ * Whenever a crosslock is held, cross_gen_id will be increased.
+ */
+static atomic_t cross_gen_id; /* Can be wrapped */
+
+/* Implement a circular buffer - for internal use */
+#define cir_p(n, i)		((i) ? (i) - 1 : (n) - 1)
+#define cir_n(n, i)		((i) == (n) - 1 ? 0 : (i) + 1)
+#define p_idx_p(i)		cir_p(MAX_PLOCKS_NR, i)
+#define p_idx_n(i)		cir_n(MAX_PLOCKS_NR, i)
+#define p_idx(t)		((t)->plock_index)
+
+/* For easy access to plock */
+#define plock(t, i)		((t)->plocks + (i))
+#define plock_prev(t, p)	plock(t, p_idx_p((p) - (t)->plocks))
+#define plock_curr(t)		plock(t, p_idx(t))
+#define plock_incr(t)		({p_idx(t) = p_idx_n(p_idx(t));})
+
+/*
+ * Crossrelease also need to distinguish each hardirq context, not
+ * only identify its depth.
+ */
+static DEFINE_PER_CPU(unsigned int, hardirq_id);
+void crossrelease_hardirq_start(void)
+{
+	per_cpu(hardirq_id, smp_processor_id())++;
+}
+
+/*
+ * Crossrelease also need to distinguish each softirq context, not
+ * only identify its depth.
+ */
+static DEFINE_PER_CPU(unsigned int, softirq_id);
+void crossrelease_softirq_start(void)
+{
+	per_cpu(softirq_id, smp_processor_id())++;
+}
+
+static int cross_class(struct lock_class *class)
+{
+	if (!class)
+		return 0;
+
+	return class->crosslock;
+}
+
+/*
+ * This is needed to decide the relationship between
+ * wrapable variables.
+ */
+static inline int before(unsigned int a, unsigned int b)
+{
+	return (int)(a - b) < 0;
+}
+
+static inline struct lock_class *plock_class(struct pend_lock *plock)
+{
+	return hlock_class(&plock->hlock);
+}
+
+static inline struct lock_class *xlock_class(struct cross_lock *xlock)
+{
+	return hlock_class(&xlock->hlock);
+}
+
+/*
+ * To find the earlist crosslock among all crosslocks not released yet
+ */
+static unsigned int gen_id_begin(void)
+{
+	struct cross_lock *xlock;
+	unsigned int gen_id;
+	unsigned int min = (unsigned int)atomic_read(&cross_gen_id) + 1;
+
+	list_for_each_entry_rcu(xlock, &xlocks_head, xlock_entry) {
+		gen_id = READ_ONCE(xlock->gen_id);
+		if (before(gen_id, min))
+			min = gen_id;
+	}
+
+	return min;
+}
+
+/*
+ * To find the latest crosslock among all crosslocks already released
+ */
+static inline unsigned int gen_id_done(void)
+{
+	return gen_id_begin() - 1;
+}
+
+/*
+ * Should we check a dependency with previous one?
+ */
+static inline int dep_before(struct held_lock *hlock)
+{
+	return hlock->read != 2 && hlock->check && !hlock->trylock;
+}
+
+/*
+ * Should we check a dependency with next one?
+ */
+static inline int dep_after(struct held_lock *hlock)
+{
+	return hlock->read != 2 && hlock->check;
+}
+
+/*
+ * Check if the plock is used at least once after initializaion.
+ * Remind pend_lock is implemented as a ring buffer.
+ */
+static inline int plock_used(struct pend_lock *plock)
+{
+	/*
+	 * plock->hlock.class_idx must be !NULL and
+	 * plock->hlock.instance must be !NULL,
+	 * if it was used once.
+	 */
+	return plock->hlock.instance ? 1 : 0;
+}
+
+/*
+ * Get a pend_lock from pend_lock ring buffer and provide it
+ * to caller.
+ *
+ * No contention. Irq disable is only required.
+ */
+static struct pend_lock *alloc_plock(unsigned int gen_id_done)
+{
+	struct task_struct *curr = current;
+	struct pend_lock *plock = plock_curr(curr);
+
+	if (plock_used(plock) && before(gen_id_done, plock->gen_id)) {
+		printk_once("crossrelease: plock pool is full.\n");
+		return NULL;
+	}
+
+	plock_incr(curr);
+	return plock;
+}
+
+/*
+ * No contention. Irq disable is only required.
+ */
+static void add_plock(struct held_lock *hlock, unsigned int prev_gen_id,
+		unsigned int gen_id_done)
+{
+	struct task_struct *curr = current;
+	int cpu = smp_processor_id();
+	struct pend_lock *plock;
+	unsigned int gen_id = (unsigned int)atomic_read(&cross_gen_id);
+
+	plock = alloc_plock(gen_id_done);
+
+	if (plock) {
+		/* Initialize pend_lock's members here */
+		memcpy(&plock->hlock, hlock, sizeof(struct held_lock));
+		plock->prev_gen_id = prev_gen_id;
+		plock->gen_id = gen_id;
+		plock->hardirq_context = curr->hardirq_context;
+		plock->softirq_context = curr->softirq_context;
+		plock->hardirq_id = per_cpu(hardirq_id, cpu);
+		plock->softirq_id = per_cpu(softirq_id, cpu);
+
+		plock->trace.nr_entries = 0;
+		plock->trace.max_entries = MAX_PLOCK_TRACE_ENTRIES;
+		plock->trace.entries = plock->trace_entries;
+		plock->trace.skip = 3;
+		save_stack_trace(&plock->trace);
+	}
+}
+
+/*
+ * No contention. Irq disable is only required.
+ */
+static int same_context_plock(struct pend_lock *plock)
+{
+	struct task_struct *curr = current;
+	int cpu = smp_processor_id();
+
+	/* In the case of hardirq context */
+	if (curr->hardirq_context) {
+		if (plock->hardirq_id != per_cpu(hardirq_id, cpu) ||
+		    plock->hardirq_context != curr->hardirq_context)
+			return 0;
+	/* In the case of softriq context */
+	} else if (curr->softirq_context) {
+		if (plock->softirq_id != per_cpu(softirq_id, cpu) ||
+		    plock->softirq_context != curr->softirq_context)
+			return 0;
+	/* In the case of process context */
+	} else {
+		if (plock->hardirq_context != 0 ||
+		    plock->softirq_context != 0)
+			return 0;
+	}
+	return 1;
+}
+
+/*
+ * We try to avoid adding a pend_lock unnecessarily so that
+ * the overhead adding pend_lock and building a dependency
+ * chain when commiting it unnecessarily, can be reduced.
+ */
+static int check_dup_plock(struct held_lock *hlock)
+{
+	struct task_struct *curr = current;
+	struct lock_class *class = hlock_class(hlock);
+	struct pend_lock *plock_c = plock_curr(curr);
+	struct pend_lock *plock = plock_c;
+
+	do {
+		plock = plock_prev(curr, plock);
+
+		if (!plock_used(plock))
+			break;
+		/*
+		 * This control dependency of LOAD cross_gen_id
+		 * orders between the LOAD and all LOCK operations
+		 * causing STORE following this.
+		 *
+		 * It pairs with atomic_inc_return() in add_xlock().
+		 */
+		if (plock->gen_id != (unsigned int)atomic_read(&cross_gen_id))
+			break;
+		if (same_context_plock(plock) &&
+		    hlock_class(&plock->hlock) == class)
+			return 1;
+	} while (plock_c != plock);
+
+	return 0;
+}
+
+/*
+ * This will be called when lock_acquire() is called for
+ * non-crosslock. It should be implemented locklessly as far
+ * as possible since it is called very frequently.
+ */
+static void check_add_plock(struct held_lock *hlock)
+{
+	struct held_lock *prev;
+	struct held_lock *start;
+	struct cross_lock *xlock;
+	struct lock_chain *chain;
+	unsigned int id;
+	unsigned int gen_id;
+	unsigned int gen_id_e;
+	u64 chain_key;
+
+	if (!dep_before(hlock) || check_dup_plock(hlock))
+		return;
+
+	gen_id = (unsigned int)atomic_read(&cross_gen_id);
+	gen_id_e = gen_id_done();
+	start = current->held_locks;
+
+	list_for_each_entry_rcu(xlock, &xlocks_head, xlock_entry) {
+		id = xlock_class(xlock) - lock_classes;
+		chain_key = iterate_chain_key((u64)0, id);
+		id = hlock_class(hlock) - lock_classes;
+		chain_key = iterate_chain_key(chain_key, id);
+		chain = lookup_chain_cache(chain_key);
+
+		if (!chain) {
+			for (prev = hlock - 1; prev >= start &&
+			     !dep_before(prev); prev--);
+
+			if (prev < start)
+				add_plock(hlock, gen_id_e, gen_id_e);
+			else if (prev->gen_id != gen_id)
+				add_plock(hlock, prev->gen_id, gen_id_e);
+
+			break;
+		}
+	}
+}
+
+/*
+ * This will be called when lock_acquire() is called for crosslock.
+ */
+static int add_xlock(struct held_lock *hlock)
+{
+	struct cross_lock *xlock;
+	unsigned int gen_id;
+
+	if (!dep_after(hlock))
+		return 1;
+
+	if (!graph_lock())
+		return 0;
+
+	xlock = hlock->instance->xlock;
+	if (!xlock)
+		goto unlock;
+
+	if (xlock->ref++)
+		goto unlock;
+
+	/*
+	 * We do assign operation for class_idx here redundantly
+	 * even though memcpy will also be performed soon, to
+	 * ensure a rcu reader can access this class_idx atomically
+	 * without lock.
+	 *
+	 * Here we assume setting a word-sized variable to a value
+	 * is an atomic operation.
+	 */
+	xlock->hlock.class_idx = hlock->class_idx;
+	gen_id = (unsigned int)atomic_inc_return(&cross_gen_id);
+	WRITE_ONCE(xlock->gen_id, gen_id);
+	memcpy(&xlock->hlock, hlock, sizeof(struct held_lock));
+	INIT_LIST_HEAD(&xlock->xlock_entry);
+	list_add_tail_rcu(&xlock->xlock_entry, &xlocks_head);
+unlock:
+	graph_unlock();
+	return 1;
+}
+
+/*
+ * return 0: Need to do non-crossrelease acquire ops.
+ * return 1: Done. No more acquire ops is needed.
+ */
+static int lock_acquire_crosslock(struct held_lock *hlock)
+{
+	unsigned int gen_id = (unsigned int)atomic_read(&cross_gen_id);
+
+	hlock->gen_id = gen_id;
+
+	if (cross_class(hlock_class(hlock)))
+		return add_xlock(hlock);
+
+	check_add_plock(hlock);
+	return 0;
+}
+
+static int commit_plock(struct cross_lock *xlock, struct pend_lock *plock)
+{
+	struct stack_trace trace;
+	unsigned int id;
+	u64 chain_key;
+
+	id = xlock_class(xlock) - lock_classes;
+	chain_key = iterate_chain_key((u64)0, id);
+	id = plock_class(plock) - lock_classes;
+	chain_key = iterate_chain_key(chain_key, id);
+
+	if (lookup_chain_cache(chain_key))
+		return 1;
+
+	if (!add_chain_cache_2hlocks(&xlock->hlock, &plock->hlock, chain_key))
+		return 0;
+
+	if (!save_trace(&trace, &plock->trace))
+		return 0;
+
+	if (!check_prev_add(current, &xlock->hlock, &plock->hlock, 1,
+			    NULL, &trace))
+		return 0;
+
+	return 1;
+}
+
+static int commit_plocks(struct cross_lock *xlock)
+{
+	struct task_struct *curr = current;
+	struct pend_lock *plock_c = plock_curr(curr);
+	struct pend_lock *plock = plock_c;
+
+	do {
+		plock = plock_prev(curr, plock);
+
+		if (!plock_used(plock))
+			break;
+
+		if (before(plock->gen_id, xlock->gen_id))
+			break;
+
+		if (same_context_plock(plock) &&
+		    before(plock->prev_gen_id, xlock->gen_id) &&
+		    plock_class(plock)->skip_gen_id != xlock->gen_id &&
+		    !commit_plock(xlock, plock))
+			return 0;
+	} while (plock_c != plock);
+
+	return 1;
+}
+
+/* Need to be protected using graph_lock() by caller */
+static void mark_skip_classes(struct lock_class *class, unsigned int id)
+{
+	struct lock_list *entry;
+
+	list_for_each_entry(entry, &class->locks_after, entry)
+		entry->class->skip_gen_id = id;
+}
+
+/*
+ * lock_commit_crosslock is a function for doing commit.
+ */
+void lock_commit_crosslock(struct lockdep_map *lock)
+{
+	struct cross_lock *xlock;
+	unsigned long flags;
+
+	if (unlikely(current->lockdep_recursion))
+		return;
+
+	raw_local_irq_save(flags);
+	check_flags(flags);
+	current->lockdep_recursion = 1;
+
+	if (unlikely(!debug_locks))
+		return;
+
+	if (!graph_lock())
+		return;
+
+	xlock = lock->xlock;
+	if (xlock && xlock->ref > 0) {
+		mark_skip_classes(xlock_class(xlock), xlock->gen_id);
+		if (!commit_plocks(xlock))
+			return;
+	}
+
+	graph_unlock();
+	current->lockdep_recursion = 0;
+	raw_local_irq_restore(flags);
+}
+EXPORT_SYMBOL_GPL(lock_commit_crosslock);
+
+/*
+ * return 0: Need to do non-crossrelease release ops.
+ * return 1: Done. No more release ops is needed.
+ */
+static int lock_release_crosslock(struct lockdep_map *lock)
+{
+	struct cross_lock *xlock;
+	int ret = lock->cross;
+
+	if (!graph_lock())
+		return 0;
+
+	xlock = lock->xlock;
+	if (xlock && !--xlock->ref)
+		list_del_rcu(&xlock->xlock_entry);
+
+	graph_unlock();
+	return ret;
+}
+
+static void init_map_noncrosslock(struct lockdep_map *lock)
+{
+	lock->cross = 0;
+	lock->xlock = NULL;
+}
+
+static void init_map_crosslock(struct lockdep_map *lock, struct cross_lock *xlock)
+{
+	unsigned long flags;
+
+	BUG_ON(!lock || !xlock);
+
+	raw_local_irq_save(flags);
+	if (graph_lock()) {
+		memset(xlock, 0x0, sizeof(struct cross_lock));
+		lock->cross = 1;
+		lock->xlock = xlock;
+		graph_unlock();
+	}
+	raw_local_irq_restore(flags);
+}
+
+static void init_class_crosslock(struct lock_class *class, int cross)
+{
+	class->crosslock = cross;
+	class->skip_gen_id = gen_id_done();
+}
+#endif
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 8bfd1ac..bb8bf88 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -993,6 +993,19 @@ config DEBUG_LOCK_ALLOC
 	 spin_lock_init()/mutex_init()/etc., or whether there is any lock
 	 held during task exit.
 
+config LOCKDEP_CROSSRELEASE
+	bool "Lock debugging: allow other context to unlock a lock"
+	depends on TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT
+	select LOCKDEP
+	select TRACE_IRQFLAGS
+	default n
+	help
+	 This allows a context to unlock a lock held by another context.
+	 Normally a lock must be unlocked by the context holding the lock.
+	 However relexing this constraint helps locks like (un)lock_page()
+	 or wait_for_complete() can use lock correctness detector using
+	 lockdep.
+
 config PROVE_LOCKING
 	bool "Lock debugging: prove locking correctness"
 	depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT
-- 
1.9.1

[RFC v2 06/13] lockdep: Apply crossrelease to completion

[Byungchul Park]

wait_for_complete() and its family can cause deadlock. Nevertheless, it
cannot use the lock correntness validator because complete() will be
called in different context from the context calling wait_for_complete(),
which violates original lockdep's assumption.

However, thanks to CONFIG_LOCKDEP_CROSSRELEASE, we can apply the lockdep
detector to wait_for_complete() and complete(). Applied it.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 include/linux/completion.h | 121 +++++++++++++++++++++++++++++++++++++++++----
 kernel/locking/lockdep.c   |  18 +++++++
 kernel/sched/completion.c  |  55 ++++++++++++---------
 lib/Kconfig.debug          |   8 +++
 4 files changed, 169 insertions(+), 33 deletions(-)

diff --git a/include/linux/completion.h b/include/linux/completion.h
index 5d5aaae..67a27af 100644
--- a/include/linux/completion.h
+++ b/include/linux/completion.h
@@ -9,6 +9,9 @@
  */
 
 #include <linux/wait.h>
+#ifdef CONFIG_LOCKDEP_COMPLETE
+#include <linux/lockdep.h>
+#endif
 
 /*
  * struct completion - structure used to maintain state for a "completion"
@@ -25,10 +28,53 @@
 struct completion {
 	unsigned int done;
 	wait_queue_head_t wait;
+#ifdef CONFIG_LOCKDEP_COMPLETE
+	struct lockdep_map map;
+	struct cross_lock xlock;
+#endif
 };
 
+#ifdef CONFIG_LOCKDEP_COMPLETE
+static inline void complete_acquire(struct completion *x)
+{
+	lock_acquire_exclusive(&x->map, 0, 0, NULL, _RET_IP_);
+}
+
+static inline void complete_release(struct completion *x)
+{
+	lock_release(&x->map, 0, _RET_IP_);
+}
+
+static inline void complete_release_commit(struct completion *x)
+{
+	lock_commit_crosslock(&x->map);
+}
+
+#define init_completion(x)				\
+do {							\
+	static struct lock_class_key __key;		\
+	lockdep_init_map_crosslock(&(x)->map,		\
+			&(x)->xlock,			\
+			"(complete)" #x,		\
+			&__key, 0);			\
+	__init_completion(x);				\
+} while (0)
+#else
+#define init_completion(x) __init_completion(x)
+static inline void complete_acquire(struct completion *x, int try) {}
+static inline void complete_release(struct completion *x) {}
+static inline void complete_release_commit(struct completion *x) {}
+#endif
+
+#ifdef CONFIG_LOCKDEP_COMPLETE
+#define COMPLETION_INITIALIZER(work) \
+	{ 0, __WAIT_QUEUE_HEAD_INITIALIZER((work).wait), \
+	STATIC_CROSS_LOCKDEP_MAP_INIT("(complete)" #work, &(work), \
+	&(work).xlock), STATIC_CROSS_LOCK_INIT()}
+#else
 #define COMPLETION_INITIALIZER(work) \
 	{ 0, __WAIT_QUEUE_HEAD_INITIALIZER((work).wait) }
+#endif
 
 #define COMPLETION_INITIALIZER_ONSTACK(work) \
 	({ init_completion(&work); work; })
@@ -70,7 +116,7 @@ struct completion {
  * This inline function will initialize a dynamically created completion
  * structure.
  */
-static inline void init_completion(struct completion *x)
+static inline void __init_completion(struct completion *x)
 {
 	x->done = 0;
 	init_waitqueue_head(&x->wait);
@@ -88,18 +134,75 @@ static inline void reinit_completion(struct completion *x)
 	x->done = 0;
 }
 
-extern void wait_for_completion(struct completion *);
-extern void wait_for_completion_io(struct completion *);
-extern int wait_for_completion_interruptible(struct completion *x);
-extern int wait_for_completion_killable(struct completion *x);
-extern unsigned long wait_for_completion_timeout(struct completion *x,
+extern void __wait_for_completion(struct completion *);
+extern void __wait_for_completion_io(struct completion *);
+extern int __wait_for_completion_interruptible(struct completion *x);
+extern int __wait_for_completion_killable(struct completion *x);
+extern unsigned long __wait_for_completion_timeout(struct completion *x,
 						   unsigned long timeout);
-extern unsigned long wait_for_completion_io_timeout(struct completion *x,
+extern unsigned long __wait_for_completion_io_timeout(struct completion *x,
 						    unsigned long timeout);
-extern long wait_for_completion_interruptible_timeout(
+extern long __wait_for_completion_interruptible_timeout(
 	struct completion *x, unsigned long timeout);
-extern long wait_for_completion_killable_timeout(
+extern long __wait_for_completion_killable_timeout(
 	struct completion *x, unsigned long timeout);
+
+static inline void wait_for_completion(struct completion *x)
+{
+	complete_acquire(x);
+	__wait_for_completion(x);
+	complete_release(x);
+}
+
+static inline void wait_for_completion_io(struct completion *x)
+{
+	complete_acquire(x);
+	__wait_for_completion_io(x);
+	complete_release(x);
+}
+
+static inline int wait_for_completion_interruptible(struct completion *x)
+{
+	int ret;
+	complete_acquire(x);
+	ret = __wait_for_completion_interruptible(x);
+	complete_release(x);
+	return ret;
+}
+
+static inline int wait_for_completion_killable(struct completion *x)
+{
+	int ret;
+	complete_acquire(x);
+	ret = __wait_for_completion_killable(x);
+	complete_release(x);
+	return ret;
+}
+
+static inline unsigned long wait_for_completion_timeout(struct completion *x,
+		unsigned long timeout)
+{
+	return __wait_for_completion_timeout(x, timeout);
+}
+
+static inline unsigned long wait_for_completion_io_timeout(struct completion *x,
+		unsigned long timeout)
+{
+	return __wait_for_completion_io_timeout(x, timeout);
+}
+
+static inline long wait_for_completion_interruptible_timeout(
+	struct completion *x, unsigned long timeout)
+{
+	return __wait_for_completion_interruptible_timeout(x, timeout);
+}
+
+static inline long wait_for_completion_killable_timeout(
+	struct completion *x, unsigned long timeout)
+{
+	return __wait_for_completion_killable_timeout(x, timeout);
+}
+
 extern bool try_wait_for_completion(struct completion *x);
 extern bool completion_done(struct completion *x);
 
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 12903f9..ea19108 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4694,6 +4694,12 @@ static void add_plock(struct held_lock *hlock, unsigned int prev_gen_id,
 	}
 }
 
+#ifdef CONFIG_LOCKDEP_COMPLETE
+static int xlock_might_onstack = 1;
+#else
+static int xlock_might_onstack = 0;
+#endif
+
 /*
  * No contention. Irq disable is only required.
  */
@@ -4774,6 +4780,15 @@ static void check_add_plock(struct held_lock *hlock)
 	if (!dep_before(hlock) || check_dup_plock(hlock))
 		return;
 
+	/*
+	 * If a xlock instance is on stack, it can be
+	 * overwritten randomly after escaping the
+	 * stack fraem, so we cannot refer rcu protected
+	 * list without holding lock.
+	 */
+	if (xlock_might_onstack && !graph_lock())
+		return;
+
 	gen_id = (unsigned int)atomic_read(&cross_gen_id);
 	gen_id_e = gen_id_done();
 	start = current->held_locks;
@@ -4797,6 +4812,9 @@ static void check_add_plock(struct held_lock *hlock)
 			break;
 		}
 	}
+
+	if (xlock_might_onstack)
+		graph_unlock();
 }
 
 /*
diff --git a/kernel/sched/completion.c b/kernel/sched/completion.c
index 8d0f35d..b695699 100644
--- a/kernel/sched/completion.c
+++ b/kernel/sched/completion.c
@@ -31,6 +31,11 @@ void complete(struct completion *x)
 	unsigned long flags;
 
 	spin_lock_irqsave(&x->wait.lock, flags);
+	/*
+	 * Actual lock dependency building should be
+	 * performed when complete() is called.
+	 */
+	complete_release_commit(x);
 	x->done++;
 	__wake_up_locked(&x->wait, TASK_NORMAL, 1);
 	spin_unlock_irqrestore(&x->wait.lock, flags);
@@ -108,7 +113,7 @@ wait_for_common_io(struct completion *x, long timeout, int state)
 }
 
 /**
- * wait_for_completion: - waits for completion of a task
+ * __wait_for_completion: - waits for completion of a task
  * @x:  holds the state of this particular completion
  *
  * This waits to be signaled for completion of a specific task. It is NOT
@@ -117,14 +122,14 @@ wait_for_common_io(struct completion *x, long timeout, int state)
  * See also similar routines (i.e. wait_for_completion_timeout()) with timeout
  * and interrupt capability. Also see complete().
  */
-void __sched wait_for_completion(struct completion *x)
+void __sched __wait_for_completion(struct completion *x)
 {
 	wait_for_common(x, MAX_SCHEDULE_TIMEOUT, TASK_UNINTERRUPTIBLE);
 }
-EXPORT_SYMBOL(wait_for_completion);
+EXPORT_SYMBOL(__wait_for_completion);
 
 /**
- * wait_for_completion_timeout: - waits for completion of a task (w/timeout)
+ * __wait_for_completion_timeout: - waits for completion of a task (w/timeout)
  * @x:  holds the state of this particular completion
  * @timeout:  timeout value in jiffies
  *
@@ -136,28 +141,28 @@ EXPORT_SYMBOL(wait_for_completion);
  * till timeout) if completed.
  */
 unsigned long __sched
-wait_for_completion_timeout(struct completion *x, unsigned long timeout)
+__wait_for_completion_timeout(struct completion *x, unsigned long timeout)
 {
 	return wait_for_common(x, timeout, TASK_UNINTERRUPTIBLE);
 }
-EXPORT_SYMBOL(wait_for_completion_timeout);
+EXPORT_SYMBOL(__wait_for_completion_timeout);
 
 /**
- * wait_for_completion_io: - waits for completion of a task
+ * __wait_for_completion_io: - waits for completion of a task
  * @x:  holds the state of this particular completion
  *
  * This waits to be signaled for completion of a specific task. It is NOT
  * interruptible and there is no timeout. The caller is accounted as waiting
  * for IO (which traditionally means blkio only).
  */
-void __sched wait_for_completion_io(struct completion *x)
+void __sched __wait_for_completion_io(struct completion *x)
 {
 	wait_for_common_io(x, MAX_SCHEDULE_TIMEOUT, TASK_UNINTERRUPTIBLE);
 }
-EXPORT_SYMBOL(wait_for_completion_io);
+EXPORT_SYMBOL(__wait_for_completion_io);
 
 /**
- * wait_for_completion_io_timeout: - waits for completion of a task (w/timeout)
+ * __wait_for_completion_io_timeout: - waits for completion of a task (w/timeout)
  * @x:  holds the state of this particular completion
  * @timeout:  timeout value in jiffies
  *
@@ -170,14 +175,14 @@ EXPORT_SYMBOL(wait_for_completion_io);
  * till timeout) if completed.
  */
 unsigned long __sched
-wait_for_completion_io_timeout(struct completion *x, unsigned long timeout)
+__wait_for_completion_io_timeout(struct completion *x, unsigned long timeout)
 {
 	return wait_for_common_io(x, timeout, TASK_UNINTERRUPTIBLE);
 }
-EXPORT_SYMBOL(wait_for_completion_io_timeout);
+EXPORT_SYMBOL(__wait_for_completion_io_timeout);
 
 /**
- * wait_for_completion_interruptible: - waits for completion of a task (w/intr)
+ * __wait_for_completion_interruptible: - waits for completion of a task (w/intr)
  * @x:  holds the state of this particular completion
  *
  * This waits for completion of a specific task to be signaled. It is
@@ -185,17 +190,18 @@ EXPORT_SYMBOL(wait_for_completion_io_timeout);
  *
  * Return: -ERESTARTSYS if interrupted, 0 if completed.
  */
-int __sched wait_for_completion_interruptible(struct completion *x)
+int __sched __wait_for_completion_interruptible(struct completion *x)
 {
 	long t = wait_for_common(x, MAX_SCHEDULE_TIMEOUT, TASK_INTERRUPTIBLE);
+
 	if (t == -ERESTARTSYS)
 		return t;
 	return 0;
 }
-EXPORT_SYMBOL(wait_for_completion_interruptible);
+EXPORT_SYMBOL(__wait_for_completion_interruptible);
 
 /**
- * wait_for_completion_interruptible_timeout: - waits for completion (w/(to,intr))
+ * __wait_for_completion_interruptible_timeout: - waits for completion (w/(to,intr))
  * @x:  holds the state of this particular completion
  * @timeout:  timeout value in jiffies
  *
@@ -206,15 +212,15 @@ EXPORT_SYMBOL(wait_for_completion_interruptible);
  * or number of jiffies left till timeout) if completed.
  */
 long __sched
-wait_for_completion_interruptible_timeout(struct completion *x,
+__wait_for_completion_interruptible_timeout(struct completion *x,
 					  unsigned long timeout)
 {
 	return wait_for_common(x, timeout, TASK_INTERRUPTIBLE);
 }
-EXPORT_SYMBOL(wait_for_completion_interruptible_timeout);
+EXPORT_SYMBOL(__wait_for_completion_interruptible_timeout);
 
 /**
- * wait_for_completion_killable: - waits for completion of a task (killable)
+ * __wait_for_completion_killable: - waits for completion of a task (killable)
  * @x:  holds the state of this particular completion
  *
  * This waits to be signaled for completion of a specific task. It can be
@@ -222,17 +228,18 @@ EXPORT_SYMBOL(wait_for_completion_interruptible_timeout);
  *
  * Return: -ERESTARTSYS if interrupted, 0 if completed.
  */
-int __sched wait_for_completion_killable(struct completion *x)
+int __sched __wait_for_completion_killable(struct completion *x)
 {
 	long t = wait_for_common(x, MAX_SCHEDULE_TIMEOUT, TASK_KILLABLE);
+
 	if (t == -ERESTARTSYS)
 		return t;
 	return 0;
 }
-EXPORT_SYMBOL(wait_for_completion_killable);
+EXPORT_SYMBOL(__wait_for_completion_killable);
 
 /**
- * wait_for_completion_killable_timeout: - waits for completion of a task (w/(to,killable))
+ * __wait_for_completion_killable_timeout: - waits for completion of a task (w/(to,killable))
  * @x:  holds the state of this particular completion
  * @timeout:  timeout value in jiffies
  *
@@ -244,12 +251,12 @@ EXPORT_SYMBOL(wait_for_completion_killable);
  * or number of jiffies left till timeout) if completed.
  */
 long __sched
-wait_for_completion_killable_timeout(struct completion *x,
+__wait_for_completion_killable_timeout(struct completion *x,
 				     unsigned long timeout)
 {
 	return wait_for_common(x, timeout, TASK_KILLABLE);
 }
-EXPORT_SYMBOL(wait_for_completion_killable_timeout);
+EXPORT_SYMBOL(__wait_for_completion_killable_timeout);
 
 /**
  *	try_wait_for_completion - try to decrement a completion without blocking
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index bb8bf88..b5946c7 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1006,6 +1006,14 @@ config LOCKDEP_CROSSRELEASE
 	 or wait_for_complete() can use lock correctness detector using
 	 lockdep.
 
+config LOCKDEP_COMPLETE
+	bool "Lock debugging: allow complete to use deadlock detector"
+	select LOCKDEP_CROSSRELEASE
+	default n
+	help
+	 A deadlock caused by wait and complete can be detected by lockdep
+	 using crossrelease feature.
+
 config PROVE_LOCKING
 	bool "Lock debugging: prove locking correctness"
 	depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT
-- 
1.9.1

[RFC v2 07/13] pagemap.h: Remove trailing white space

[Byungchul Park]

Trailing white space is not accepted in kernel coding style. Remove
them.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 include/linux/pagemap.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/linux/pagemap.h b/include/linux/pagemap.h
index 92395a0..c0049d9 100644
--- a/include/linux/pagemap.h
+++ b/include/linux/pagemap.h
@@ -513,7 +513,7 @@ static inline void wake_up_page(struct page *page, int bit)
 	__wake_up_bit(page_waitqueue(page), &page->flags, bit);
 }
 
-/* 
+/*
  * Wait for a page to be unlocked.
  *
  * This must be called with the caller "holding" the page,
@@ -526,7 +526,7 @@ static inline void wait_on_page_locked(struct page *page)
 		wait_on_page_bit(compound_head(page), PG_locked);
 }
 
-/* 
+/*
  * Wait for a page to complete writeback
  */
 static inline void wait_on_page_writeback(struct page *page)
-- 
1.9.1

[RFC v2 08/13] lockdep: Apply crossrelease to PG_locked lock

[Byungchul Park]

lock_page() and its family can cause deadlock. Nevertheless, it cannot
use the lock correctness validator becasue unlock_page() can be called
in different context from the context calling lock_page(), which
violates original lockdep's assumption.

However, thanks to CONFIG_LOCKDEP_CROSSRELEASE, we can apply the lockdep
detector to lock_page() using PG_locked. Applied it.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 include/linux/mm_types.h |  9 +++++
 include/linux/pagemap.h  | 95 +++++++++++++++++++++++++++++++++++++++++++++---
 lib/Kconfig.debug        |  9 +++++
 mm/filemap.c             |  4 +-
 mm/page_alloc.c          |  3 ++
 5 files changed, 112 insertions(+), 8 deletions(-)

diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
index 624b78b..ab33ee3 100644
--- a/include/linux/mm_types.h
+++ b/include/linux/mm_types.h
@@ -15,6 +15,10 @@
 #include <asm/page.h>
 #include <asm/mmu.h>
 
+#ifdef CONFIG_LOCKDEP_PAGELOCK
+#include <linux/lockdep.h>
+#endif
+
 #ifndef AT_VECTOR_SIZE_ARCH
 #define AT_VECTOR_SIZE_ARCH 0
 #endif
@@ -215,6 +219,11 @@ struct page {
 #ifdef LAST_CPUPID_NOT_IN_PAGE_FLAGS
 	int _last_cpupid;
 #endif
+
+#ifdef CONFIG_LOCKDEP_PAGELOCK
+	struct lockdep_map map;
+	struct cross_lock xlock;
+#endif
 }
 /*
  * The struct page can be forced to be double word aligned so that atomic ops
diff --git a/include/linux/pagemap.h b/include/linux/pagemap.h
index c0049d9..2fc4af1 100644
--- a/include/linux/pagemap.h
+++ b/include/linux/pagemap.h
@@ -14,6 +14,9 @@
 #include <linux/bitops.h>
 #include <linux/hardirq.h> /* for in_interrupt() */
 #include <linux/hugetlb_inline.h>
+#ifdef CONFIG_LOCKDEP_PAGELOCK
+#include <linux/lockdep.h>
+#endif
 
 /*
  * Bits in mapping->flags.  The lower __GFP_BITS_SHIFT bits are the page
@@ -441,26 +444,81 @@ static inline pgoff_t linear_page_index(struct vm_area_struct *vma,
 	return pgoff >> (PAGE_CACHE_SHIFT - PAGE_SHIFT);
 }
 
+#ifdef CONFIG_LOCKDEP_PAGELOCK
+#define lock_page_init(p)					\
+do {								\
+	static struct lock_class_key __key;			\
+	lockdep_init_map_crosslock(&(p)->map, &(p)->xlock,	\
+			"(PG_locked)" #p, &__key, 0);		\
+} while (0)
+
+static inline void lock_page_acquire(struct page *page, int try)
+{
+	page = compound_head(page);
+	lock_acquire_exclusive(&page->map, 0, try, NULL, _RET_IP_);
+}
+
+static inline void lock_page_release(struct page *page)
+{
+	page = compound_head(page);
+	/*
+	 * Calling lock_commit_crosslock() is necessary
+	 * for cross-releasable lock when the lock is
+	 * releasing before calling lock_release().
+	 */
+	lock_commit_crosslock(&page->map);
+	lock_release(&page->map, 0, _RET_IP_);
+}
+#else
+static inline void lock_page_init(struct page *page) {}
+static inline void lock_page_free(struct page *page) {}
+static inline void lock_page_acquire(struct page *page, int try) {}
+static inline void lock_page_release(struct page *page) {}
+#endif
+
 extern void __lock_page(struct page *page);
 extern int __lock_page_killable(struct page *page);
 extern int __lock_page_or_retry(struct page *page, struct mm_struct *mm,
 				unsigned int flags);
-extern void unlock_page(struct page *page);
+extern void do_raw_unlock_page(struct page *page);
 
-static inline int trylock_page(struct page *page)
+static inline void unlock_page(struct page *page)
+{
+	lock_page_release(page);
+	do_raw_unlock_page(page);
+}
+
+static inline int do_raw_trylock_page(struct page *page)
 {
 	page = compound_head(page);
 	return (likely(!test_and_set_bit_lock(PG_locked, &page->flags)));
 }
 
+static inline int trylock_page(struct page *page)
+{
+	if (do_raw_trylock_page(page)) {
+		lock_page_acquire(page, 1);
+		return 1;
+	}
+	return 0;
+}
+
 /*
  * lock_page may only be called if we have the page's inode pinned.
  */
 static inline void lock_page(struct page *page)
 {
 	might_sleep();
-	if (!trylock_page(page))
+
+	if (!do_raw_trylock_page(page))
 		__lock_page(page);
+	/*
+	 * The acquire function must be after actual lock operation
+	 * for crossrelease lock, because the lock instance is
+	 * searched by release operation in any context and more
+	 * than two instances acquired make it confused.
+	 */
+	lock_page_acquire(page, 0);
 }
 
 /*
@@ -470,9 +528,22 @@ static inline void lock_page(struct page *page)
  */
 static inline int lock_page_killable(struct page *page)
 {
+	int ret;
+
 	might_sleep();
-	if (!trylock_page(page))
-		return __lock_page_killable(page);
+
+	if (!do_raw_trylock_page(page)) {
+		ret = __lock_page_killable(page);
+		if (ret)
+			return ret;
+	}
+	/*
+	 * The acquire function must be after actual lock operation
+	 * for crossrelease lock, because the lock instance is
+	 * searched by release operation in any context and more
+	 * than two instances acquired make it confused.
+	 */
+	lock_page_acquire(page, 0);
 	return 0;
 }
 
@@ -487,7 +558,19 @@ static inline int lock_page_or_retry(struct page *page, struct mm_struct *mm,
 				     unsigned int flags)
 {
 	might_sleep();
-	return trylock_page(page) || __lock_page_or_retry(page, mm, flags);
+
+	if (do_raw_trylock_page(page) || __lock_page_or_retry(page, mm, flags)) {
+		/*
+		 * The acquire function must be after actual lock operation
+		 * for crossrelease lock, because the lock instance is
+		 * searched by release operation in any context and more
+		 * than two instances acquired make it confused.
+		 */
+		lock_page_acquire(page, 0);
+		return 1;
+	}
+
+	return 0;
 }
 
 /*
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index b5946c7..ee7faca 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1014,6 +1014,15 @@ config LOCKDEP_COMPLETE
 	 A deadlock caused by wait and complete can be detected by lockdep
 	 using crossrelease feature.
 
+config LOCKDEP_PAGELOCK
+	bool "Lock debugging: allow PG_locked lock to use deadlock detector"
+	select LOCKDEP_CROSSRELEASE
+	default n
+	help
+	 PG_locked lock is a kind of cross-released lock. This makes
+	 PG_locked lock possible to use deadlock detector, using
+	 crossrelease feature.
+
 config PROVE_LOCKING
 	bool "Lock debugging: prove locking correctness"
 	depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT
diff --git a/mm/filemap.c b/mm/filemap.c
index 3461d97..47fc5c0 100644
--- a/mm/filemap.c
+++ b/mm/filemap.c
@@ -814,7 +814,7 @@ EXPORT_SYMBOL_GPL(add_page_wait_queue);
  * The mb is necessary to enforce ordering between the clear_bit and the read
  * of the waitqueue (to avoid SMP races with a parallel wait_on_page_locked()).
  */
-void unlock_page(struct page *page)
+void do_raw_unlock_page(struct page *page)
 {
 	page = compound_head(page);
 	VM_BUG_ON_PAGE(!PageLocked(page), page);
@@ -822,7 +822,7 @@ void unlock_page(struct page *page)
 	smp_mb__after_atomic();
 	wake_up_page(page, PG_locked);
 }
-EXPORT_SYMBOL(unlock_page);
+EXPORT_SYMBOL(do_raw_unlock_page);
 
 /**
  * end_page_writeback - end writeback against a page
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 838ca8bb..17ed9a8 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -4538,6 +4538,9 @@ void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
 		} else {
 			__init_single_pfn(pfn, zone, nid);
 		}
+#ifdef CONFIG_LOCKDEP_PAGELOCK
+		lock_page_init(pfn_to_page(pfn));
+#endif
 	}
 }
 
-- 
1.9.1

[RFC v2 09/13] cifs/file.c: Remove trailing white space

[Byungchul Park]

Trailing white space is not accepted in kernel coding style. Remove
them.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 fs/cifs/file.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fs/cifs/file.c b/fs/cifs/file.c
index ff882ae..bcf9ead 100644
--- a/fs/cifs/file.c
+++ b/fs/cifs/file.c
@@ -3851,7 +3851,7 @@ void cifs_oplock_break(struct work_struct *work)
  * In the non-cached mode (mount with cache=none), we shunt off direct read and write requests
  * so this method should never be called.
  *
- * Direct IO is not yet supported in the cached mode. 
+ * Direct IO is not yet supported in the cached mode.
  */
 static ssize_t
 cifs_direct_io(struct kiocb *iocb, struct iov_iter *iter, loff_t pos)
-- 
1.9.1

[RFC v2 10/13] mm/swap_state.c: Remove trailing white space

[Byungchul Park]

Trailing white space is not accepted in kernel coding style. Remove
them.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 mm/swap_state.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/mm/swap_state.c b/mm/swap_state.c
index 69cb246..3fb7013 100644
--- a/mm/swap_state.c
+++ b/mm/swap_state.c
@@ -156,7 +156,7 @@ void __delete_from_swap_cache(struct page *page)
  * @page: page we want to move to swap
  *
  * Allocate swap space for the page and add the page to the
- * swap cache.  Caller needs to hold the page lock. 
+ * swap cache.  Caller needs to hold the page lock.
  */
 int add_to_swap(struct page *page, struct list_head *list)
 {
@@ -229,9 +229,9 @@ void delete_from_swap_cache(struct page *page)
 	page_cache_release(page);
 }
 
-/* 
- * If we are the only user, then try to free up the swap cache. 
- * 
+/*
+ * If we are the only user, then try to free up the swap cache.
+ *
  * Its ok to check for PageSwapCache without the page lock
  * here because we are going to recheck again inside
  * try_to_free_swap() _with_ the lock.
@@ -245,7 +245,7 @@ static inline void free_swap_cache(struct page *page)
 	}
 }
 
-/* 
+/*
  * Perform a free_page(), also freeing any swap cache associated with
  * this page if it is the last user of the page.
  */
-- 
1.9.1

[RFC v2 11/13] lockdep: Call lock_acquire(release) when accessing PG_locked manually

[Byungchul Park]

The PG_locked bit can be updated through SetPageLocked() or
ClearPageLocked(), not by lock_page() and unlock_page().
SetPageLockded() and ClearPageLocked() also have to be considered to
get balanced between acquring and releasing the PG_locked lock.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 fs/cifs/file.c          | 4 ++++
 include/linux/pagemap.h | 5 ++++-
 mm/filemap.c            | 6 ++++--
 mm/ksm.c                | 1 +
 mm/migrate.c            | 1 +
 mm/shmem.c              | 2 ++
 mm/swap_state.c         | 2 ++
 mm/vmscan.c             | 1 +
 8 files changed, 19 insertions(+), 3 deletions(-)

diff --git a/fs/cifs/file.c b/fs/cifs/file.c
index bcf9ead..7b250c1 100644
--- a/fs/cifs/file.c
+++ b/fs/cifs/file.c
@@ -3392,12 +3392,14 @@ readpages_get_pages(struct address_space *mapping, struct list_head *page_list,
 	 * PG_locked without checking it first.
 	 */
 	__SetPageLocked(page);
+	lock_page_acquire(page, 1);
 	rc = add_to_page_cache_locked(page, mapping,
 				      page->index, gfp);
 
 	/* give up if we can't stick it in the cache */
 	if (rc) {
 		__ClearPageLocked(page);
+		lock_page_release(page);
 		return rc;
 	}
 
@@ -3419,8 +3421,10 @@ readpages_get_pages(struct address_space *mapping, struct list_head *page_list,
 			break;
 
 		__SetPageLocked(page);
+		lock_page_acquire(page, 1);
 		if (add_to_page_cache_locked(page, mapping, page->index, gfp)) {
 			__ClearPageLocked(page);
+			lock_page_release(page);
 			break;
 		}
 		list_move_tail(&page->lru, tmplist);
diff --git a/include/linux/pagemap.h b/include/linux/pagemap.h
index 2fc4af1..f92972c 100644
--- a/include/linux/pagemap.h
+++ b/include/linux/pagemap.h
@@ -760,9 +760,12 @@ static inline int add_to_page_cache(struct page *page,
 	int error;
 
 	__SetPageLocked(page);
+	lock_page_acquire(page, 1);
 	error = add_to_page_cache_locked(page, mapping, offset, gfp_mask);
-	if (unlikely(error))
+	if (unlikely(error)) {
 		__ClearPageLocked(page);
+		lock_page_release(page);
+	}
 	return error;
 }
 
diff --git a/mm/filemap.c b/mm/filemap.c
index 47fc5c0..7acce5e 100644
--- a/mm/filemap.c
+++ b/mm/filemap.c
@@ -690,11 +690,13 @@ int add_to_page_cache_lru(struct page *page, struct address_space *mapping,
 	int ret;
 
 	__SetPageLocked(page);
+	lock_page_acquire(page, 1);
 	ret = __add_to_page_cache_locked(page, mapping, offset,
 					 gfp_mask, &shadow);
-	if (unlikely(ret))
+	if (unlikely(ret)) {
 		__ClearPageLocked(page);
-	else {
+		lock_page_release(page);
+	} else {
 		/*
 		 * The page might have been evicted from cache only
 		 * recently, in which case it should be activated like
diff --git a/mm/ksm.c b/mm/ksm.c
index ca6d2a0..c89debd 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -1869,6 +1869,7 @@ struct page *ksm_might_need_to_copy(struct page *page,
 		SetPageDirty(new_page);
 		__SetPageUptodate(new_page);
 		__SetPageLocked(new_page);
+		lock_page_acquire(new_page, 1);
 	}
 
 	return new_page;
diff --git a/mm/migrate.c b/mm/migrate.c
index 3ad0fea..9aab7c4 100644
--- a/mm/migrate.c
+++ b/mm/migrate.c
@@ -1773,6 +1773,7 @@ int migrate_misplaced_transhuge_page(struct mm_struct *mm,
 
 	/* Prepare a page as a migration target */
 	__SetPageLocked(new_page);
+	lock_page_acquire(new_page, 1);
 	SetPageSwapBacked(new_page);
 
 	/* anon mapping, we can simply copy page->mapping to the new page: */
diff --git a/mm/shmem.c b/mm/shmem.c
index 440e2a7..da35ca8 100644
--- a/mm/shmem.c
+++ b/mm/shmem.c
@@ -1090,6 +1090,7 @@ static int shmem_replace_page(struct page **pagep, gfp_t gfp,
 	flush_dcache_page(newpage);
 
 	__SetPageLocked(newpage);
+	lock_page_acquire(newpage, 1);
 	SetPageUptodate(newpage);
 	SetPageSwapBacked(newpage);
 	set_page_private(newpage, swap_index);
@@ -1283,6 +1284,7 @@ repeat:
 
 		__SetPageSwapBacked(page);
 		__SetPageLocked(page);
+		lock_page_acquire(page, 1);
 		if (sgp == SGP_WRITE)
 			__SetPageReferenced(page);
 
diff --git a/mm/swap_state.c b/mm/swap_state.c
index 3fb7013..200edbf 100644
--- a/mm/swap_state.c
+++ b/mm/swap_state.c
@@ -358,6 +358,7 @@ struct page *__read_swap_cache_async(swp_entry_t entry, gfp_t gfp_mask,
 
 		/* May fail (-ENOMEM) if radix-tree node allocation failed. */
 		__SetPageLocked(new_page);
+		lock_page_acquire(new_page, 1);
 		SetPageSwapBacked(new_page);
 		err = __add_to_swap_cache(new_page, entry);
 		if (likely(!err)) {
@@ -372,6 +373,7 @@ struct page *__read_swap_cache_async(swp_entry_t entry, gfp_t gfp_mask,
 		radix_tree_preload_end();
 		ClearPageSwapBacked(new_page);
 		__ClearPageLocked(new_page);
+		lock_page_release(new_page);
 		/*
 		 * add_to_swap_cache() doesn't return -EEXIST, so we can safely
 		 * clear SWAP_HAS_CACHE flag.
diff --git a/mm/vmscan.c b/mm/vmscan.c
index 71b1c29..5baff91 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -1199,6 +1199,7 @@ lazyfree:
 		 * waiting on the page lock, because there are no references.
 		 */
 		__ClearPageLocked(page);
+		lock_page_release(page);
 free_it:
 		if (ret == SWAP_LZFREE)
 			count_vm_event(PGLAZYFREED);
-- 
1.9.1

[RFC v2 12/13] lockdep: Make crossrelease use save_stack_trace_norm() instead

[Byungchul Park]

Currently crossrelease feature uses save_stack_trace() to save
backtrace. However it has much overhead. So this patch makes it
use save_stack_trace_norm() instead, which has smaller overhead.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/locking/lockdep.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index ea19108..fd7865b 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4690,7 +4690,7 @@ static void add_plock(struct held_lock *hlock, unsigned int prev_gen_id,
 		plock->trace.max_entries = MAX_PLOCK_TRACE_ENTRIES;
 		plock->trace.entries = plock->trace_entries;
 		plock->trace.skip = 3;
-		save_stack_trace(&plock->trace);
+		save_stack_trace_norm(&plock->trace);
 	}
 }
 
-- 
1.9.1

[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@lge.com>
---
 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@lge.com>
+
+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

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

[Byungchul Park]

On Thu, Jul 07, 2016 at 06:30:03PM +0900, Byungchul Park wrote:
> Crossrelease feature introduces new concept and data structure. Thus
> the document is necessary. So added it.

Any opinions about this suggestion?

> 
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
>  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@lge.com>
> +
> +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

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

[Byungchul Park]

On Mon, Jul 18, 2016 at 10:39:19AM +0900, Byungchul Park wrote:
> On Thu, Jul 07, 2016 at 06:30:03PM +0900, Byungchul Park wrote:
> > Crossrelease feature introduces new concept and data structure. Thus
> > the document is necessary. So added it.
> 
> Any opinions about this suggestion?

Just to be sure, I have to enhance this document more yet, however I'm sure
I already introduced the general outline through this document. It was the
purpose of this premature document which I sent early even though it's not
perfect yet.

> 
> > 
> > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > ---
> >  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@lge.com>
> > +
> > +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

Re: [RFC v2 00/13] lockdep: Implement crossrelease feature

[Byungchul Park]

+cc Nikolay Borisov <kernel@kyup.com>

who might be interested in this patchset.

[Revised document] Crossrelease lockdep

[Byungchul Park]

Hello,

I rewrote the document so that the need of crossrelease feature can be
described logically. I think it's more important than to post specific
implementation. Could you let me know your opinions about this?

Thanks,
Byungchul

----->8-----

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

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

Contents:

 (*) Background.

     - What causes deadlock.
     - What lockdep detects.
     - How lockdep works.

 (*) Limitation.

     - Limit to typical lock.
     - Pros from the limitation.
     - Cons from the limitation.

 (*) Generalization.

     - Relax the limitation.

 (*) Crossrelease.

     - Introduce crossrelease.
     - Introduce commit.

 (*) Implementation.

     - Data structures.
     - How crossrelease works.

 (*) Optimizations.

     - Avoid duplication.
     - Avoid lock contention.


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

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

A deadlock occurs when a context is waiting for an event to be issued
which cannot be issued because the context or another context who can
issue the event is also waiting for an event to be issued which cannot
be issued. Single context or more than one context both waiting for an
event and issuing an event may paricipate in a deadlock.

For example,

A context who can issue event D is waiting for event A to be issued.
A context who can issue event A is waiting for event B to be issued.
A context who can issue event B is waiting for event C to be issued.
A context who can issue event C is waiting for event D to be issued.

A deadlock occurs when these four operations are run at a time because
event D cannot be issued if event A isn't issued which in turn cannot be
issued if event B isn't issued which in turn cannot be issued if event C
isn't issued which in turn cannot be issued if event D isn't issued. No
event can be issued since any of them never meets its precondition.

We can easily recognize that each wait operation creates a dependency
between two issuings e.g. between issuing D and issuing A like, 'event D
cannot be issued if event A isn't issued', in other words, 'issuing
event D depends on issuing event A'. So the whole example can be
rewritten in terms of dependency,

Do an operation making 'event D cannot be issued if event A isn't issued'.
Do an operation making 'event A cannot be issued if event B isn't issued'.
Do an operation making 'event B cannot be issued if event C isn't issued'.
Do an operation making 'event C cannot be issued if event D isn't issued'.

or,

Do an operation making 'issuing event D depends on issuing event A'.
Do an operation making 'issuing event A depends on issuing event B'.
Do an operation making 'issuing event B depends on issuing event C'.
Do an operation making 'issuing event C depends on issuing event D'.

What causes a deadlock is a set of dependencies a chain of which forms a
cycle, which means that issuing event D depending on issuing event A
depending on issuing event B depending on issuing event C depending on
issuing event D, finally depends on issuing event D itself, which means
no event can be issued.

Any set of operations creating dependencies causes a deadlock. The set
of lock operations e.g. acquire and release is an example. Waiting for a
lock to be released corresponds to waiting for an event and releasing a
lock corresponds to issuing an event. So the description of dependency
above can be altered to one in terms of lock.

In terms of event, issuing event A depends on issuing event B if,

	Event A cannot be issued if event B isn't issued.

In terms of lock, releasing lock A depends on releasing lock B if,

	Lock A cannot be released if lock B isn't released.

CONCLUSION

A set of dependencies a chain of which forms a cycle, causes a deadlock,
no matter what creates the dependencies.


What lockdep detects
--------------------

A deadlock actually occurs only when all operations creating problematic
dependencies are run at a time. However, even if it has not happend, the
deadlock potentially can occur if the problematic dependencies obviously
exist. Thus it's meaningful to detect not only an actual deadlock but
also its possibility. Lockdep does the both.

Whether a deadlock actually occurs or not depends on several factors,
which means a deadlock may not occur even though problematic
dependencies exist. For example, what order contexts are switched in is
a factor. A deadlock will occur when contexts are switched so that all
operations causing a deadlock become run simultaneously.

Lockdep tries to detect a deadlock or its possibility aggressively,
though it also tries to avoid false positive detections. So lockdep is
designed to consider all possible combinations of dependencies so that
it can detect all potential possibilities of deadlock in advance. What
lockdep tries in order to consider all possibilities are,

1. Use a global dependency graph including all dependencies.

   What lockdep checks is based on dependencies instead of what actually
   happened. So no matter which context or call path a new dependency is
   detected in, it's just referred to as a global factor.

2. Use lock classes than lock instances when checking dependencies.

   What actually causes a deadlock is lock instances. However, lockdep
   uses lock classes than its instances when checking dependencies since
   any instance of a same lock class can be altered anytime.

So lockdep detects both an actual deadlock and its possibility. But the
latter is more valuable than the former. When a deadlock actually
occures, 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 does, the fisrt one is more valuable,

1. Detecting and reporting deadlock possibility.
2. Detecting and reporting a deadlock actually occured.


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

What lockdep should do, to detect a deadlock or its possibility are,

1. Detect a new dependency created.
2. Keep the dependency in a global data structure esp. graph.
3. Check if any of all possible chains of dependencies forms a cycle.
4. Report a deadlock or its possibility if a cycle is detected.

A graph used by lockdep to keep all dependencies looks like,

A -> B -        -> F -> G
        \      /
         -> E -        -> L
        /      \      /
C -> D -        -> H -
                      \
                       -> I -> K
                      /
                   J -

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

Lockdep adds a dependency into graph when a new dependency is detected.
For example, it adds a dependency 'A -> B' when a dependency between
releasing lock A and releasing lock B, which has not been added yet, is
detected. It does same thing on other dependencies, too. See 'What
causes deadlock' section.

NOTE: Precisely speaking, a dependency is one between releasing a lock
and releasing another lock as described in 'What causes deadlock'
section. However from now on, we will describe a dependency as if it's
one between a lock and another lock for simplicity. Then 'A -> B' can be
described as a dependency between lock A and lock B.

We already checked how a problematic set of dependencies causes a
deadlock in 'What causes deadlock' section. This time let's check if a
deadlock or its possibility can be detected using a problematic set of
dependencies. Assume that 'A -> B', 'B -> E' and 'E -> A' were added in
the sequence into graph. Then the graph finally will be,

 -> A -> B -> E -
/                \
\                /
 ----------------

where A, B and E are different lock classes.

>From adding three dependencies, a cycle was created which means, by
definition of dependency, the situation 'lock E must be released to
release lock B which in turn must be released to release lock A which in
turn must be released to release lock E which in turn must be released
to release B and so on infinitely' can happen.

Once the situation happens, no lock can be released since any of them
can never meet each precondition. It's a deadlock. Lockdep can detect a
deadlock or its possibility with checking if a cycle was created after
adding each dependency into graph. This is how lockdep detects a
deadlock or its possibility.

CONCLUSION

Lockdep detects a deadlock or its possibility with checking if a cycle
was created after adding each dependency into graph.


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

Limit to typical lock
---------------------

Limiting what lockdep has to consider to only ones satisfying the
following condition, the implementation of adding dependencies becomes
simple while its capacity for detection becomes limited. Typical lock
e.g. spin lock and mutex is the case. Let's check what pros and cons of
it are, in next section.

	A lock should be released within the context holding the lock.

CONCLUSION

Limiting what lockdep has to consider to typical lock e.g. spin lock and
mutex, the implmentation becomes simple while it has a limited capacity.


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

Given the limitation, when acquiring a lock, any lock being in
held_locks of the acquire context cannot be released if the lock to
acquire was not released yet. Yes. It's the exact case to add a new
dependency 'A -> B' into graph, where lock A represents each lock being
in held_locks and lock B represents the lock to acquire.

For example, only considering typical lock,

	PROCESS 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, there's nothing in held_locks of PROCESS X thus
no dependency is added. When acquiring lock B, lockdep detects and adds
a new dependency 'A -> B' between lock A being in held_locks and lock B.
And when acquiring lock C, lockdep also adds another dependency 'B -> C'
for same reason. They are added when acquiring each lock, simply.

NOTE: Even though every lock being in held_locks depends on the lock to
acquire, lockdep does not add all dependencies between them because all
of them can be covered by other dependencies except one dependency
between the lock on top of held_locks and the lock to acquire, which
must be added.

Besides, we can expect several advantages from the limitation.

1. Any lock being in held_locks cannot be released unconditionally if
   the context is stuck, thus we can easily identify a dependency when
   acquiring a lock.

2. Considering only locks being in local held_locks of a single context
   makes some races avoidable, even though it fails of course when
   modifying its global dependency graph.

3. To build a dependency graph, lockdep only needs to keep locks not
   released yet. However relaxing the limitation, it might need to keep
   even locks already released, additionally. See 'Crossrelease' section.

CONCLUSION

Given the limitation, the implementation becomes simple and efficient.


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

Given the limitation, lockdep is applicable only to typical lock. For
example, page lock for page access or completion for synchronization
cannot play with lockdep having the limitation. However since page lock
or completion also causes a deadlock, it would be better to detect a
deadlock or its possibility even for them.

Can we detect deadlocks below with lockdep having the limitation?

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

where A and B are different lock classes.

No, we cannot.

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 held by X
			unlock_page B
			mutex_unlock A

where A and B are different lock classes.

No, we cannot.

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

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 lock or completion.


==============
Generalization
==============

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

Detecting and adding new 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. More dependencies lockdep adds, more
throughly it can work. Therefore Lockdep has to do its best to add as
many true dependencies as possible.

Relaxing the limitation, lockdep can add additional dependencies since
it makes lockdep deal with additional ones creating the dependencies e.g.
page lock or completion, which might be released in any context. Even so,
it needs to be noted that behaviors adding dependencies created by
typical lock don't need to be changed at all.

For example, only considering typical lock, 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, and upper case letters
represent typical lock.

After the relaxing, the graph will have additional dependencies like,

A -> B -        -> F -> G
        \      /
         -> E -        -> L -> c
        /      \      /
C -> D -        -> H -
               /      \
            a -        -> I -> K
                      /
              b -> J -

where a, b, c, A, B,..., L are different lock classes, and upper case
letters represent typical lock while lower case letters represent
non-typical lock e.g. page lock and completion.

However, it might suffer performance degradation since relaxing the
limitation with which design and implementation of lockdep become
efficient might introduce inefficiency inevitably. Each option, that is,
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.

In the latter, of course, some contexts are not allowed if they
themselves cause a deadlock. 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 a cycle of a dependency chain, meaning a
deadlock. Otherwise, any contexts are allowed to release it.

CONCLUSION

Relaxing the limitation, lockdep adds additional dependencies and gets
additional chances to check if they cause a deadlock. It makes lockdep
additionally deal with what might be released in any context.


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

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

To allow lockdep to add additional dependencies created by what might be
released in any context, which we call 'crosslock', it's necessary to
introduce a new feature which makes it possible to identify and add the
dependencies. We call the feature 'crossrelease'. Crossrelease feature
has to do,

1. Identify a new dependency created by crosslock.
2. Add the dependency into graph when identifying it.

That's all. Once a meaningful dependency is added into graph, lockdep
will work with the graph as it did. So the most important thing to do is
to identify a dependency created by crosslock. Remind what a dependency
is. For example, Lock A depends on lock B if 'lock A cannot be released
if lock B isn't released'. See 'What causes deadlock' section.

By definition, a lock depends on every lock having been added into
held_locks in the lock's release context since the lock was acquired,
because the lock cannot be released if the release context is stuck by
any of dependent locks, not released. So lockdep should technically
consider release contexts of locks to identify dependencies.

It's no matter of course to typical lock because acquire context is same
as release context for typical lock, which means lockdep would work with
considering only acquire contexts for typical lock. However, for
crosslock, lockdep cannot identify release context and any dependency
until the crosslock will be actually released.

Regarding crosslock, lockdep has to record all history by queueing all
locks potentially creating dependencies so that real dependencies can be
added using the history recorded when identifying release context. We
call it 'commit', that is, to add dependencies in batches. See
'Introduce commit' section.

Of course, some actual deadlocks caused by crosslock cannot be detected
at the time it happened, because the deadlocks cannot be indentified and
detected until the crosslock will be actually released. But this way
deadlock possibility can be detected and it's worth just possibility
detection of deadlock. See 'What lockdep does' section.

CONCLUSION

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


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

Crossrelease feature names it 'commit' to identify and add dependencies
into graph in batches. Lockdep is already doing what commit does when
acquiring a lock, for typical lock. However, that way must be changed
for crosslock so that it identifies the crosslock's release context
first and then does commit.

The main reason why lockdep performs additional step, namely commit, for
crosslock is that some dependencies by crosslock cannot be identified
until the crosslock's release context is eventually identified, though
some other dependencies by crosslock can. There are four kinds of
dependencies to consider.

1. 'typical lock A -> typical lock B' dependency

   Just when acquiring lock B, lockdep can identify the dependency
   between lock A and lock B as it did. Commit is unnecessary.

2. 'typical lock A -> crosslock b' dependency

   Just when acquiring crosslock b, lockdep can identify the dependency
   between lock A and crosslock B as well. Commit is unnecessary, too.

3. 'crosslock a -> typical lock B' dependency

   When acquiring lock B, lockdep cannot identify the dependency. It can
   be identified only when crosslock a is released. Commit is necessary.

4. 'crosslock a -> crosslock b' dependency

   Creating this kind of dependency directly is unnecessary since it can
   be covered by other kinds of dependencies.

Lockdep works without commit during dealing with only typical locks.
However, it needs to perform commit step, once at least one crosslock is
acquired, until all crosslocks in progress are released. Introducing
commit, lockdep performs three steps i.e. acquire, commit and release.
What lockdep should do in each step is like,

1. Acquire

   1) For typical lock

	Lockdep does what it originally does and queues the lock so
	that lockdep can check dependencies using it at commit step.

   2) For crosslock

	The crosslock is added to a global linked list so that lockdep
	can check dependencies using it at commit step.

2. Commit

   1) For typical lock

	N/A.

   2) For crosslock

	Lockdep checks and adds dependencies using data saved at acquire
	step, as if the dependencies were added without commit 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

Lockdep can detect a deadlock or its possibility caused by what might be
released in any context, using commit step, where it checks and adds
dependencies in batches.


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

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

Crossrelease feature introduces two main data structures.

1. pend_lock (or plock)

   This is an array embedded in task_struct, for keeping locks queued so
   that real dependencies can be added using them at commit step. So
   this data can be accessed locklessly within the owner context. The
   array is filled when acquiring a typical lock and consumed when doing
   commit. And it's managed in circular manner.

2. cross_lock (or xlock)

   This is a global linked list, for keeping all crosslocks in progress.
   The list grows when acquiring a crosslock and is shrunk when
   releasing the crosslock. lockdep_init_map_crosslock() should be used
   to initialize a crosslock instance instead of lockdep_init_map() so
   that lockdep can recognize it as crosslock.

CONCLUSION

Crossrelease feature uses 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 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 lock.

	RELEASE CONTEXT of A (= ACQUIRE CONTEXT of A)
	--------------------
	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, and upper case letters
represent typical lock.

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

A -> B

where A and B are different lock classes, and upper case letters
represent typical lock.

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

A -> B -> C

where A, B and C are different lock classes, and upper case letters
represent typical lock.

What if applying commit on typical locks? It's not necessary for typical
lock. Just for showing what commit does.

	RELEASE CONTEXT of A (= ACQUIRE CONTEXT of A)
	--------------------
	acquire A -> mark A as started (nothing before, no queueing)

	acquire B -> mark B as started and queue B

	acquire C -> mark C as started and queue C

	release C -> commit C (nothing queued since C started)

	release B -> commit B -> add a dependency 'B -> C'

	release A -> commit A -> add dependencies 'A -> B' and 'A -> C'

where A, B and C are different lock classes, and upper case letters
represent typical lock.

After doing commit A, B and C, the dependency graph becomes like,

A -> B -> C

where A, B and C are different lock classes, and upper case letters
represent typical lock.

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

Here we can see the final graph is same as the graph built without
commit. Of course the former way leads to finish building the graph
earlier than the latter way, 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 using commit, for crosslock.

Let's look at how commit works for crosslock.

	RELEASE CONTEXT of a	ACQUIRE CONTEXT of a
	--------------------	--------------------
				acquire a -> mark a as started

	(serialized by some means e.g. barrier)

	acquire D -> queue D
				acquire B -> queue B
	release D
				acquire C -> add 'B -> C' and queue C
	acquire E -> queue E
				acquire D -> add 'C -> D' and queue D
	release E
				release D
	release a -> commit a -> add 'a -> D' and 'a -> E'
				release C

				release B

where a, B,..., E are different lock classes, and upper case letters
represent typical lock while lower case letters represent crosslock.

When acquiring crosslock a, no dependency can be added since there's
nothing in the held_locks. However, crossrelease feature marks the
crosslock as started, which means all locks to acquire from now are
candidates which might create new dependencies later when identifying
release context.

When acquiring lock B, lockdep does what it originally does for typical
lock and additionally queues the lock for later commit to refer to
because it might be a dependent lock of the crosslock. It does same
thing on lock C, D and E. And then two dependencies 'a -> D' and 'a -> E'
are added when identifying the release context, at commit step.

The final graph is, with crossrelease feature using commit,

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

where a, B,..., E are different lock classes, and upper case letters
represent typical lock while lower case letters represent crosslock.

However, without crossrelease feature, the final graph will be,

B -> C -> D

where B and C are different lock classes, and upper case letters
represent typical lock.

The former graph has two more dependencies 'a -> D' and 'a -> E' giving
additional chances to check if they cause a deadlock. This way lockdep
can detect a deadlock or its possibility caused by crosslock. Again,
behaviors adding dependencies created by only typical locks are not
changed at all.

CONCLUSION

Crossrelease works using commit for crosslock, leaving behaviors adding
dependencies between only typical locks unchanged.


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

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

Crossrelease feature uses a cache like what lockdep already uses for
dependency chains, but this time it's for caching one dependency like
'crosslock -> typical lock' crossing between two different context. Once
that dependency is cached, same dependency will never be added any more.
Even queueing unnecessary locks is also prevented based on the cache.

CONCLUSION

Crossrelease does not add any duplicate dependency.


Avoid lock contention
---------------------

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 each array to be accessed only within each own
context. It's like how held_locks is accessed. Lockless implmentation is
important since typical locks are very frequently accessed.

CONCLUSION

Crossrelease avoids lock contection as far as possible.

Re: [Revised document] Crossrelease lockdep

[Byungchul Park]

On Fri, Aug 19, 2016 at 09:39:59PM +0900, Byungchul Park wrote:
> Hello,
> 
> I rewrote the document so that the need of crossrelease feature can be
> described logically. I think it's more important than to post specific
> implementation. Could you let me know your opinions about this?
> 
> Thanks,
> Byungchul
> 
> ----->8-----
> 
> Crossrelease
> ============
> 
> Started by Byungchul Park <byungchul.park@lge.com>
> 
> Contents:
> 
>  (*) Background.
> 
>      - What causes deadlock.
>      - What lockdep detects.
>      - How lockdep works.
> 
>  (*) Limitation.
> 
>      - Limit to typical lock.
>      - Pros from the limitation.
>      - Cons from the limitation.
> 
>  (*) Generalization.
> 
>      - Relax the limitation.
> 
>  (*) Crossrelease.
> 
>      - Introduce crossrelease.
>      - Introduce commit.
> 
>  (*) Implementation.
> 
>      - Data structures.
>      - How crossrelease works.
> 
>  (*) Optimizations.
> 
>      - Avoid duplication.
>      - Avoid lock contention.
> 
> 
> ==========
> Background
> ==========
> 
> What causes deadlock
> --------------------
> 
> A deadlock occurs when a context is waiting for an event to be issued
> which cannot be issued because the context or another context who can
> issue the event is also waiting for an event to be issued which cannot
> be issued. Single context or more than one context both waiting for an
> event and issuing an event may paricipate in a deadlock.
> 
> For example,
> 
> A context who can issue event D is waiting for event A to be issued.
> A context who can issue event A is waiting for event B to be issued.
> A context who can issue event B is waiting for event C to be issued.
> A context who can issue event C is waiting for event D to be issued.
> 
> A deadlock occurs when these four operations are run at a time because
> event D cannot be issued if event A isn't issued which in turn cannot be
> issued if event B isn't issued which in turn cannot be issued if event C
> isn't issued which in turn cannot be issued if event D isn't issued. No
> event can be issued since any of them never meets its precondition.
> 
> We can easily recognize that each wait operation creates a dependency
> between two issuings e.g. between issuing D and issuing A like, 'event D
> cannot be issued if event A isn't issued', in other words, 'issuing
> event D depends on issuing event A'. So the whole example can be
> rewritten in terms of dependency,
> 
> Do an operation making 'event D cannot be issued if event A isn't issued'.
> Do an operation making 'event A cannot be issued if event B isn't issued'.
> Do an operation making 'event B cannot be issued if event C isn't issued'.
> Do an operation making 'event C cannot be issued if event D isn't issued'.
> 
> or,
> 
> Do an operation making 'issuing event D depends on issuing event A'.
> Do an operation making 'issuing event A depends on issuing event B'.
> Do an operation making 'issuing event B depends on issuing event C'.
> Do an operation making 'issuing event C depends on issuing event D'.
> 
> What causes a deadlock is a set of dependencies a chain of which forms a
> cycle, which means that issuing event D depending on issuing event A
> depending on issuing event B depending on issuing event C depending on
> issuing event D, finally depends on issuing event D itself, which means
> no event can be issued.
> 
> Any set of operations creating dependencies causes a deadlock. The set
                                            ^^^
                                            can
> of lock operations e.g. acquire and release is an example. Waiting for a
> lock to be released corresponds to waiting for an event and releasing a
> lock corresponds to issuing an event. So the description of dependency
> above can be altered to one in terms of lock.
> 
> In terms of event, issuing event A depends on issuing event B if,
> 
> 	Event A cannot be issued if event B isn't issued.
> 
> In terms of lock, releasing lock A depends on releasing lock B if,
> 
> 	Lock A cannot be released if lock B isn't released.
> 
> CONCLUSION
> 
> A set of dependencies a chain of which forms a cycle, causes a deadlock,
> no matter what creates the dependencies.
> 
> 
> What lockdep detects
> --------------------
> 
> A deadlock actually occurs only when all operations creating problematic
> dependencies are run at a time. However, even if it has not happend, the
> deadlock potentially can occur if the problematic dependencies obviously
> exist. Thus it's meaningful to detect not only an actual deadlock but
> also its possibility. Lockdep does the both.
> 
> Whether a deadlock actually occurs or not depends on several factors,
> which means a deadlock may not occur even though problematic
> dependencies exist. For example, what order contexts are switched in is
> a factor. A deadlock will occur when contexts are switched so that all
> operations causing a deadlock become run simultaneously.
> 
> Lockdep tries to detect a deadlock or its possibility aggressively,
> though it also tries to avoid false positive detections. So lockdep is
> designed to consider all possible combinations of dependencies so that
> it can detect all potential possibilities of deadlock in advance. What
> lockdep tries in order to consider all possibilities are,
> 
> 1. Use a global dependency graph including all dependencies.
> 
>    What lockdep checks is based on dependencies instead of what actually
>    happened. So no matter which context or call path a new dependency is
>    detected in, it's just referred to as a global factor.
> 
> 2. Use lock classes than lock instances when checking dependencies.
> 
>    What actually causes a deadlock is lock instances. However, lockdep
>    uses lock classes than its instances when checking dependencies since
>    any instance of a same lock class can be altered anytime.
> 
> So lockdep detects both an actual deadlock and its possibility. But the
> latter is more valuable than the former. When a deadlock actually
> occures, 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 does, the fisrt one is more valuable,
> 
> 1. Detecting and reporting deadlock possibility.
> 2. Detecting and reporting a deadlock actually occured.
> 
> 
> How lockdep works
> -----------------
> 
> What lockdep should do, to detect a deadlock or its possibility are,
> 
> 1. Detect a new dependency created.
> 2. Keep the dependency in a global data structure esp. graph.
> 3. Check if any of all possible chains of dependencies forms a cycle.
> 4. Report a deadlock or its possibility if a cycle is detected.
> 
> A graph used by lockdep to keep all dependencies looks like,
> 
> A -> B -        -> F -> G
>         \      /
>          -> E -        -> L
>         /      \      /
> C -> D -        -> H -
>                       \
>                        -> I -> K
>                       /
>                    J -
> 
> where A, B,..., L are different lock classes.
> 
> Lockdep adds a dependency into graph when a new dependency is detected.
> For example, it adds a dependency 'A -> B' when a dependency between
> releasing lock A and releasing lock B, which has not been added yet, is
> detected. It does same thing on other dependencies, too. See 'What
> causes deadlock' section.
> 
> NOTE: Precisely speaking, a dependency is one between releasing a lock
> and releasing another lock as described in 'What causes deadlock'
> section. However from now on, we will describe a dependency as if it's
> one between a lock and another lock for simplicity. Then 'A -> B' can be
> described as a dependency between lock A and lock B.
> 
> We already checked how a problematic set of dependencies causes a
> deadlock in 'What causes deadlock' section. This time let's check if a
> deadlock or its possibility can be detected using a problematic set of
> dependencies. Assume that 'A -> B', 'B -> E' and 'E -> A' were added in
> the sequence into graph. Then the graph finally will be,
> 
>  -> A -> B -> E -
> /                \
> \                /
>  ----------------
> 
> where A, B and E are different lock classes.
> 
> >From adding three dependencies, a cycle was created which means, by
> definition of dependency, the situation 'lock E must be released to
> release lock B which in turn must be released to release lock A which in
> turn must be released to release lock E which in turn must be released
> to release B and so on infinitely' can happen.
> 
> Once the situation happens, no lock can be released since any of them
> can never meet each precondition. It's a deadlock. Lockdep can detect a
> deadlock or its possibility with checking if a cycle was created after
> adding each dependency into graph. This is how lockdep detects a
> deadlock or its possibility.
> 
> CONCLUSION
> 
> Lockdep detects a deadlock or its possibility with checking if a cycle
> was created after adding each dependency into graph.
> 
> 
> ==========
> Limitation
> ==========
> 
> Limit to typical lock
> ---------------------
> 
> Limiting what lockdep has to consider to only ones satisfying the
> following condition, the implementation of adding dependencies becomes
> simple while its capacity for detection becomes limited. Typical lock
> e.g. spin lock and mutex is the case. Let's check what pros and cons of
> it are, in next section.
> 
> 	A lock should be released within the context holding the lock.
> 
> CONCLUSION
> 
> Limiting what lockdep has to consider to typical lock e.g. spin lock and
> mutex, the implmentation becomes simple while it has a limited capacity.
> 
> 
> Pros from the limitation
> ------------------------
> 
> Given the limitation, when acquiring a lock, any lock being in
> held_locks of the acquire context cannot be released if the lock to
> acquire was not released yet. Yes. It's the exact case to add a new
> dependency 'A -> B' into graph, where lock A represents each lock being
> in held_locks and lock B represents the lock to acquire.
> 
> For example, only considering typical lock,
> 
> 	PROCESS 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, there's nothing in held_locks of PROCESS X thus
> no dependency is added. When acquiring lock B, lockdep detects and adds
> a new dependency 'A -> B' between lock A being in held_locks and lock B.
> And when acquiring lock C, lockdep also adds another dependency 'B -> C'
> for same reason. They are added when acquiring each lock, simply.
> 
> NOTE: Even though every lock being in held_locks depends on the lock to
> acquire, lockdep does not add all dependencies between them because all
> of them can be covered by other dependencies except one dependency
> between the lock on top of held_locks and the lock to acquire, which
> must be added.
> 
> Besides, we can expect several advantages from the limitation.
> 
> 1. Any lock being in held_locks cannot be released unconditionally if
>    the context is stuck, thus we can easily identify a dependency when
>    acquiring a lock.
> 
> 2. Considering only locks being in local held_locks of a single context
>    makes some races avoidable, even though it fails of course when
>    modifying its global dependency graph.
> 
> 3. To build a dependency graph, lockdep only needs to keep locks not
>    released yet. However relaxing the limitation, it might need to keep
>    even locks already released, additionally. See 'Crossrelease' section.
> 
> CONCLUSION
> 
> Given the limitation, the implementation becomes simple and efficient.
> 
> 
> Cons from the limitation
> ------------------------
> 
> Given the limitation, lockdep is applicable only to typical lock. For
> example, page lock for page access or completion for synchronization
> cannot play with lockdep having the limitation. However since page lock
> or completion also causes a deadlock, it would be better to detect a
> deadlock or its possibility even for them.
> 
> Can we detect deadlocks below with lockdep having the limitation?
> 
> 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
> 
> where A and B are different lock classes.
> 
> No, we cannot.
> 
> 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 held by X
> 			unlock_page B
> 			mutex_unlock A
> 
> where A and B are different lock classes.
> 
> No, we cannot.
> 
> 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
> 
> 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 lock or completion.
> 
> 
> ==============
> Generalization
> ==============
> 
> Relax the limitation
> --------------------
> 
> Detecting and adding new 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. More dependencies lockdep adds, more
> throughly it can work. Therefore Lockdep has to do its best to add as
> many true dependencies as possible.
> 
> Relaxing the limitation, lockdep can add additional dependencies since
> it makes lockdep deal with additional ones creating the dependencies e.g.
> page lock or completion, which might be released in any context. Even so,
> it needs to be noted that behaviors adding dependencies created by
> typical lock don't need to be changed at all.
> 
> For example, only considering typical lock, 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, and upper case letters
> represent typical lock.
> 
> After the relaxing, the graph will have additional dependencies like,
> 
> A -> B -        -> F -> G
>         \      /
>          -> E -        -> L -> c
>         /      \      /
> C -> D -        -> H -
>                /      \
>             a -        -> I -> K
>                       /
>               b -> J -
> 
> where a, b, c, A, B,..., L are different lock classes, and upper case
> letters represent typical lock while lower case letters represent
> non-typical lock e.g. page lock and completion.
> 
> However, it might suffer performance degradation since relaxing the
> limitation with which design and implementation of lockdep become
> efficient might introduce inefficiency inevitably. Each option, that is,
> 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.
> 
> In the latter, of course, some contexts are not allowed if they
> themselves cause a deadlock. 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 a cycle of a dependency chain, meaning a
> deadlock. Otherwise, any contexts are allowed to release it.
> 
> CONCLUSION
> 
> Relaxing the limitation, lockdep adds additional dependencies and gets
> additional chances to check if they cause a deadlock. It makes lockdep
> additionally deal with what might be released in any context.
> 
> 
> ============
> Crossrelease
> ============
> 
> Introduce crossrelease
> ----------------------
> 
> To allow lockdep to add additional dependencies created by what might be
> released in any context, which we call 'crosslock', it's necessary to
> introduce a new feature which makes it possible to identify and add the
> dependencies. We call the feature 'crossrelease'. Crossrelease feature
> has to do,
> 
> 1. Identify a new dependency created by crosslock.
> 2. Add the dependency into graph when identifying it.
> 
> That's all. Once a meaningful dependency is added into graph, lockdep
> will work with the graph as it did. So the most important thing to do is
> to identify a dependency created by crosslock. Remind what a dependency
> is. For example, Lock A depends on lock B if 'lock A cannot be released
> if lock B isn't released'. See 'What causes deadlock' section.
> 
> By definition, a lock depends on every lock having been added into
> held_locks in the lock's release context since the lock was acquired,
> because the lock cannot be released if the release context is stuck by
> any of dependent locks, not released. So lockdep should technically
> consider release contexts of locks to identify dependencies.
> 
> It's no matter of course to typical lock because acquire context is same
> as release context for typical lock, which means lockdep would work with
> considering only acquire contexts for typical lock. However, for
> crosslock, lockdep cannot identify release context and any dependency
> until the crosslock will be actually released.
> 
> Regarding crosslock, lockdep has to record all history by queueing all
> locks potentially creating dependencies so that real dependencies can be
> added using the history recorded when identifying release context. We
> call it 'commit', that is, to add dependencies in batches. See
> 'Introduce commit' section.
> 
> Of course, some actual deadlocks caused by crosslock cannot be detected
> at the time it happened, because the deadlocks cannot be indentified and
> detected until the crosslock will be actually released. But this way
> deadlock possibility can be detected and it's worth just possibility
> detection of deadlock. See 'What lockdep does' section.
> 
> CONCLUSION
> 
> With crossrelease feature, lockdep can works with what might be released
> in any context, namely, crosslock.
> 
> 
> Introduce commit
> ----------------
> 
> Crossrelease feature names it 'commit' to identify and add dependencies
> into graph in batches. Lockdep is already doing what commit does when
> acquiring a lock, for typical lock. However, that way must be changed
> for crosslock so that it identifies the crosslock's release context
> first and then does commit.
> 
> The main reason why lockdep performs additional step, namely commit, for
> crosslock is that some dependencies by crosslock cannot be identified
> until the crosslock's release context is eventually identified, though
> some other dependencies by crosslock can. There are four kinds of
> dependencies to consider.
> 
> 1. 'typical lock A -> typical lock B' dependency
> 
>    Just when acquiring lock B, lockdep can identify the dependency
>    between lock A and lock B as it did. Commit is unnecessary.
> 
> 2. 'typical lock A -> crosslock b' dependency
> 
>    Just when acquiring crosslock b, lockdep can identify the dependency
>    between lock A and crosslock B as well. Commit is unnecessary, too.
> 
> 3. 'crosslock a -> typical lock B' dependency
> 
>    When acquiring lock B, lockdep cannot identify the dependency. It can
>    be identified only when crosslock a is released. Commit is necessary.
> 
> 4. 'crosslock a -> crosslock b' dependency
> 
>    Creating this kind of dependency directly is unnecessary since it can
>    be covered by other kinds of dependencies.
> 
> Lockdep works without commit during dealing with only typical locks.
> However, it needs to perform commit step, once at least one crosslock is
> acquired, until all crosslocks in progress are released. Introducing
> commit, lockdep performs three steps i.e. acquire, commit and release.
> What lockdep should do in each step is like,
> 
> 1. Acquire
> 
>    1) For typical lock
> 
> 	Lockdep does what it originally does and queues the lock so
> 	that lockdep can check dependencies using it at commit step.
> 
>    2) For crosslock
> 
> 	The crosslock is added to a global linked list so that lockdep
> 	can check dependencies using it at commit step.
> 
> 2. Commit
> 
>    1) For typical lock
> 
> 	N/A.
> 
>    2) For crosslock
> 
> 	Lockdep checks and adds dependencies using data saved at acquire
> 	step, as if the dependencies were added without commit 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
> 
> Lockdep can detect a deadlock or its possibility caused by what might be
> released in any context, using commit step, where it checks and adds
> dependencies in batches.
> 
> 
> ==============
> Implementation
> ==============
> 
> Data structures
> ---------------
> 
> Crossrelease feature introduces two main data structures.
> 
> 1. pend_lock (or plock)
> 
>    This is an array embedded in task_struct, for keeping locks queued so
>    that real dependencies can be added using them at commit step. So
>    this data can be accessed locklessly within the owner context. The
>    array is filled when acquiring a typical lock and consumed when doing
>    commit. And it's managed in circular manner.
> 
> 2. cross_lock (or xlock)
> 
>    This is a global linked list, for keeping all crosslocks in progress.
>    The list grows when acquiring a crosslock and is shrunk when
>    releasing the crosslock. lockdep_init_map_crosslock() should be used
>    to initialize a crosslock instance instead of lockdep_init_map() so
>    that lockdep can recognize it as crosslock.
> 
> CONCLUSION
> 
> Crossrelease feature uses 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 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 lock.
> 
> 	RELEASE CONTEXT of A (= ACQUIRE CONTEXT of A)
> 	--------------------
> 	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, and upper case letters
> represent typical lock.
> 
> After adding 'A -> B', the dependency graph will be,
> 
> A -> B
> 
> where A and B are different lock classes, and upper case letters
> represent typical lock.
> 
> And after adding 'B -> C', the graph will be,
> 
> A -> B -> C
> 
> where A, B and C are different lock classes, and upper case letters
> represent typical lock.
> 
> What if applying commit on typical locks? It's not necessary for typical
> lock. Just for showing what commit does.
> 
> 	RELEASE CONTEXT of A (= ACQUIRE CONTEXT of A)
> 	--------------------
> 	acquire A -> mark A as started (nothing before, no queueing)
> 
> 	acquire B -> mark B as started and queue B
> 
> 	acquire C -> mark C as started and queue C
> 
> 	release C -> commit C (nothing queued since C started)
> 
> 	release B -> commit B -> add a dependency 'B -> C'
> 
> 	release A -> commit A -> add dependencies 'A -> B' and 'A -> C'
> 
> where A, B and C are different lock classes, and upper case letters
> represent typical lock.
> 
> After doing commit A, B and C, the dependency graph becomes like,
> 
> A -> B -> C
> 
> where A, B and C are different lock classes, and upper case letters
> represent typical lock.
> 
> NOTE: A dependency 'A -> C' is optimized out.
> 
> Here we can see the final graph is same as the graph built without
> commit. Of course the former way leads to finish building the graph
> earlier than the latter way, 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 using commit, for crosslock.
> 
> Let's look at how commit works for crosslock.
> 
> 	RELEASE CONTEXT of a	ACQUIRE CONTEXT of a
> 	--------------------	--------------------
> 				acquire a -> mark a as started
> 
> 	(serialized by some means e.g. barrier)
> 
> 	acquire D -> queue D
> 				acquire B -> queue B
> 	release D
> 				acquire C -> add 'B -> C' and queue C
> 	acquire E -> queue E
> 				acquire D -> add 'C -> D' and queue D
> 	release E
> 				release D
> 	release a -> commit a -> add 'a -> D' and 'a -> E'
> 				release C
> 
> 				release B
> 
> where a, B,..., E are different lock classes, and upper case letters
> represent typical lock while lower case letters represent crosslock.
> 
> When acquiring crosslock a, no dependency can be added since there's
> nothing in the held_locks. However, crossrelease feature marks the
> crosslock as started, which means all locks to acquire from now are
> candidates which might create new dependencies later when identifying
> release context.
> 
> When acquiring lock B, lockdep does what it originally does for typical
> lock and additionally queues the lock for later commit to refer to
> because it might be a dependent lock of the crosslock. It does same
> thing on lock C, D and E. And then two dependencies 'a -> D' and 'a -> E'
> are added when identifying the release context, at commit step.
> 
> The final graph is, with crossrelease feature using commit,
> 
> B -> C -
>         \
>          -> D
>         /
>      a -
>         \
>          -> E
> 
> where a, B,..., E are different lock classes, and upper case letters
> represent typical lock while lower case letters represent crosslock.
> 
> However, without crossrelease feature, the final graph will be,
> 
> B -> C -> D
> 
> where B and C are different lock classes, and upper case letters
> represent typical lock.
> 
> The former graph has two more dependencies 'a -> D' and 'a -> E' giving
> additional chances to check if they cause a deadlock. This way lockdep
> can detect a deadlock or its possibility caused by crosslock. Again,
> behaviors adding dependencies created by only typical locks are not
> changed at all.
> 
> CONCLUSION
> 
> Crossrelease works using commit for crosslock, leaving behaviors adding
> dependencies between only typical locks unchanged.
> 
> 
> =============
> Optimizations
> =============
> 
> Avoid duplication
> -----------------
> 
> Crossrelease feature uses a cache like what lockdep already uses for
> dependency chains, but this time it's for caching one dependency like
> 'crosslock -> typical lock' crossing between two different context. Once
> that dependency is cached, same dependency will never be added any more.
> Even queueing unnecessary locks is also prevented based on the cache.
> 
> CONCLUSION
> 
> Crossrelease does not add any duplicate dependency.
> 
> 
> Avoid lock contention
> ---------------------
> 
> 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 each array to be accessed only within each own
> context. It's like how held_locks is accessed. Lockless implmentation is
> important since typical locks are very frequently accessed.
> 
> CONCLUSION
> 
> Crossrelease avoids lock contection as far as possible.

Re: [Revised document] Crossrelease lockdep

[Byungchul Park]

Please let me know your opinions. I'm planning to post next spin if you
agree with at least the concept. I omitted many things about e.g.
synchronization, set theory and so on, since I don't want it to be too
lengthy document, so focused on only essential thingy. Please let me know
if you think there are logical problems in the document. I might be able
to answer it. It would be appreciated if you check the document.

Thanks,
Byungchul