Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1482325 > unrolled thread

[PATCH v3 07/15] lockdep: Implement crossrelease feature

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-09-13 12:00 +0200
    Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2016-09-13 12:10 +0200
      Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2016-09-13 14:20 +0200
      Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park <max.byungchul.park@gmail.com> - 2016-09-13 17:20 +0200
    Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2016-09-13 17:10 +0200
      Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park <max.byungchul.park@gmail.com> - 2016-09-13 19:20 +0200
        Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2016-09-13 21:40 +0200
          Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2016-09-13 23:50 +0200
            Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park <max.byungchul.park@gmail.com> - 2016-09-14 03:10 +0200
          Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park <max.byungchul.park@gmail.com> - 2016-09-14 04:30 +0200
            Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park <max.byungchul.park@gmail.com> - 2016-09-14 06:50 +0200
            Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2016-09-14 10:20 +0200
              Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-09-19 04:50 +0200
                Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2016-09-19 11:00 +0200
                  Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-09-20 08:10 +0200
                    Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-09-20 08:40 +0200
                    Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-09-21 03:50 +0200
                  Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-09-22 05:10 +0200

#1482325 — [PATCH v3 07/15] lockdep: Implement crossrelease feature

Crossrelease feature calls a lock 'crosslock' if it is releasable
in any context. For crosslock, all locks having been held in the
release context of the crosslock, until eventually the crosslock
will be released, 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 |  12 +-
 include/linux/lockdep.h  | 122 +++++++++++
 include/linux/sched.h    |   5 +
 kernel/exit.c            |   9 +
 kernel/fork.c            |  20 ++
 kernel/locking/lockdep.c | 517 +++++++++++++++++++++++++++++++++++++++++++++--
 lib/Kconfig.debug        |  13 ++
 7 files changed, 682 insertions(+), 16 deletions(-)

diff --git a/include/linux/irqflags.h b/include/linux/irqflags.h
index 5dd1272..b1854fa 100644
--- a/include/linux/irqflags.h
+++ b/include/linux/irqflags.h
@@ -23,9 +23,17 @@
 # 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_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++; } 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
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index eabe013..6b3708b 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -108,6 +108,12 @@ struct lock_class {
 	unsigned long			contention_point[LOCKSTAT_POINTS];
 	unsigned long			contending_point[LOCKSTAT_POINTS];
 #endif
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+	/*
+	 * Flag to indicate whether it's a crosslock or normal.
+	 */
+	int				cross;
+#endif
 };
 
 #ifdef CONFIG_LOCK_STAT
@@ -143,6 +149,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 +164,9 @@ struct lockdep_map {
 	int				cpu;
 	unsigned long			ip;
 #endif
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+	struct cross_lock		*xlock;
+#endif
 };
 
 static inline void lockdep_copy_map(struct lockdep_map *to,
@@ -258,7 +270,82 @@ 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 plock among plocks having
+	 * been acquired since a crosslock was held. Crossrelease feature
+	 * uses chain cache between the crosslock and the first plock to
+	 * avoid building unnecessary dependencies, like how lockdep uses
+	 * a sort of chain cache for normal locks.
+	 */
+	unsigned int gen_id;
+#endif
+};
+
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+#define MAX_PLOCK_TRACE_ENTRIES		5
+
+/*
+ * This is for keeping locks waiting for commit to happen so that
+ * dependencies are actually built later at commit step.
+ *
+ * Every task_struct has an array of pend_lock. Each entiry will be
+ * added with a lock whenever lock_acquire() is called for normal lock.
+ */
+struct pend_lock {
+	/*
+	 * prev_gen_id is used to check whether any other hlock in the
+	 * current is already dealing with the xlock, with which commit
+	 * is performed. If so, this plock can be skipped.
+	 */
+	unsigned int		prev_gen_id;
+	/*
+	 * A kind of global timestamp increased and set when this plock
+	 * is inserted.
+	 */
+	unsigned int		gen_id;
+
+	int			hardirq_context;
+	int			softirq_context;
+
+	/*
+	 * Whenever irq happens, these are updated so that we can
+	 * distinguish each irq context uniquely.
+	 */
+	unsigned int		hardirq_id;
+	unsigned int		softirq_id;
+
+	/*
+	 * Seperate stack_trace data. This will be used at commit step.
+	 */
+	struct stack_trace	trace;
+	unsigned long		trace_entries[MAX_PLOCK_TRACE_ENTRIES];
+
+	/*
+	 * Seperate hlock instance. This will be used at commit step.
+	 */
+	struct held_lock	hlock;
+};
+
+/*
+ * One cross_lock per one lockdep_map.
+ *
+ * To initialize a lock as crosslock, lockdep_init_map_crosslock() should
+ * be used instead of lockdep_init_map(), where the pointer of cross_lock
+ * instance should be passed as a parameter.
+ */
+struct cross_lock {
+	unsigned int		gen_id;
+	struct list_head	xlock_entry;
+
+	/*
+	 * Seperate hlock instance. This will be used at commit step.
+	 */
+	struct held_lock	hlock;
+
+	int			ref; /* reference count */
 };
+#endif
 
 /*
  * Initialization, self-test and debugging-output methods:
@@ -281,6 +368,37 @@ 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);
+
+/*
+ * What we essencially have to initialize is 'ref'.
+ * Other members will be initialized in add_xlock().
+ */
+#define STATIC_CROSS_LOCK_INIT() \
+	{ .ref = 0,}
+
+/*
+ * Note that _name and _xlock must not be NULL.
+ */
+#define STATIC_CROSS_LOCKDEP_MAP_INIT(_name, _key, _xlock) \
+	{ .name = (_name), .key = (void *)(_key), .xlock = (_xlock), }
+
+/*
+ * 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, }
+
+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.
@@ -288,6 +406,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 253538f..592ee368 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1719,6 +1719,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;
+#endif
 #ifdef CONFIG_UBSAN
 	unsigned int in_ubsan;
 #endif
diff --git a/kernel/exit.c b/kernel/exit.c
index 9e6e135..9c69995 100644
--- a/kernel/exit.c
+++ b/kernel/exit.c
@@ -54,6 +54,7 @@
 #include <linux/writeback.h>
 #include <linux/shm.h>
 #include <linux/kcov.h>
+#include <linux/vmalloc.h>
 
 #include <asm/uaccess.h>
 #include <asm/unistd.h>
@@ -822,6 +823,14 @@ void do_exit(long code)
 	smp_mb();
 	raw_spin_unlock_wait(&tsk->pi_lock);
 
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+	if (tsk->plocks) {
+		void *tmp = tsk->plocks;
+		/* Disable crossrelease operation for current */
+		tsk->plocks = NULL;
+		vfree(tmp);
+	}
+#endif
 	/* causes final put_task_struct in finish_task_switch(). */
 	tsk->state = TASK_DEAD;
 	tsk->flags |= PF_NOFREEZE;	/* tell freezer to ignore us */
diff --git a/kernel/fork.c b/kernel/fork.c
index 4a7ec0c..91ab81b 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -323,6 +323,14 @@ void __init fork_init(void)
 	init_task.signal->rlim[RLIMIT_NPROC].rlim_max = max_threads/2;
 	init_task.signal->rlim[RLIMIT_SIGPENDING] =
 		init_task.signal->rlim[RLIMIT_NPROC];
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+	/*
+	 * TODO: We need to make init_task also use crossrelease feature.
+	 * For simplicity, now just disable the feature for init_task.
+	 */
+	init_task.plock_index = 0;
+	init_task.plocks = NULL;
+#endif
 }
 
 int __weak arch_dup_task_struct(struct task_struct *dst,
@@ -1443,6 +1451,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;
+	p->plocks = vzalloc(sizeof(struct pend_lock) * MAX_PLOCKS_NR);
+#endif
 #endif
 
 #ifdef CONFIG_DEBUG_MUTEXES
@@ -1686,6 +1698,14 @@ bad_fork_cleanup_audit:
 bad_fork_cleanup_perf:
 	perf_event_free_task(p);
 bad_fork_cleanup_policy:
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+	if (p->plocks) {
+		void *tmp = p->plocks;
+		/* Diable crossrelease operation for current */
+		p->plocks = NULL;
+		vfree(tmp);
+	}
+#endif
 #ifdef CONFIG_NUMA
 	mpol_put(p->mempolicy);
 bad_fork_cleanup_threadgroup_lock:
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 11580ec..2c8b2c1 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -711,6 +711,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
@@ -779,6 +793,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->xlock);
 	/*
 	 * We use RCU's safe list-add method to make
 	 * parallel walking of the hash-list safe:
@@ -1771,6 +1786,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;
@@ -1936,21 +1954,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 commit 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--;
 		/*
@@ -3184,7 +3208,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;
@@ -3242,8 +3266,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__);
 
@@ -3347,7 +3390,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)
@@ -3428,6 +3472,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);
@@ -3596,6 +3643,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
@@ -4538,3 +4588,442 @@ 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
+
+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 needs to distinguish each hardirq context.
+ */
+static DEFINE_PER_CPU(unsigned int, hardirq_id);
+void crossrelease_hardirq_start(void)
+{
+	per_cpu(hardirq_id, smp_processor_id())++;
+}
+
+/*
+ * Crossrelease needs to distinguish each softirq context.
+ */
+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->cross;
+}
+
+/*
+ * 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 = list_entry_rcu(xlocks_head.next,
+			struct cross_lock, xlock_entry);
+
+	/* If empty */
+	if (&xlock->xlock_entry == &xlocks_head)
+		return (unsigned int)atomic_read(&cross_gen_id) + 1;
+
+	return READ_ONCE(xlock->gen_id);
+}
+
+/*
+ * 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 depend_before(struct held_lock *hlock)
+{
+	return hlock->read != 2 && hlock->check && !hlock->trylock;
+}
+
+/*
+ * Should we check a dependency with next one?
+ */
+static inline int depend_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.instance must be !NULL if it's used.
+	 */
+	return !!plock->hlock.instance;
+}
+
+/*
+ * Get a pend_lock from pend_lock ring buffer.
+ *
+ * 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;
+	/*
+	 *	CONTEXT 1		CONTEXT 2
+	 *	---------		---------
+	 *	acquire A (cross)
+	 *	X = atomic_inc_return()
+	 *	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ serialize
+	 *				Y = atomic_read_acquire()
+	 *				acquire B
+	 *				acquire C
+	 *
+	 * For ordering between this and all following LOCKs.
+	 * This way we ensure the order A -> B -> C when CONTEXT 2
+	 * can see Y is equal to or greater than X.
+	 *
+	 * Pairs with atomic_inc_return() in add_xlock().
+	 */
+	unsigned int gen_id = (unsigned int)atomic_read_acquire(&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;
+}
+
+/*
+ * Called from lock_acquire() in case of non-crosslock. This should be
+ * lockless if possible.
+ */
+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 (!current->plocks || !depend_before(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 &&
+			     !depend_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 (!depend_after(hlock))
+		return 1;
+
+	if (!graph_lock())
+		return 0;
+
+	xlock = hlock->instance->xlock;
+	if (!xlock)
+		goto unlock;
+
+	if (xlock->ref++)
+		goto unlock;
+
+	/*
+	 * We assign class_idx here redundantly even though following
+	 * memcpy will cover it, in order to ensure a rcu reader can
+	 * access the class_idx atomically without lock.
+	 *
+	 * Here we assume setting a word-sized variable is atomic.
+	 */
+	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 normal acquire operation.
+ * 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)
+{
+	unsigned int xid, pid;
+	u64 chain_key;
+
+	xid = xlock_class(xlock) - lock_classes;
+	chain_key = iterate_chain_key((u64)0, xid);
+	pid = plock_class(plock) - lock_classes;
+	chain_key = iterate_chain_key(chain_key, pid);
+
+	if (lookup_chain_cache(chain_key))
+		return 1;
+
+	if (!add_chain_cache_classes(xid, pid, plock->hlock.irq_context,
+				chain_key))
+		return 0;
+
+	if (!save_trace(&plock->trace, 1))
+		return 0;
+
+	if (!check_prev_add(current, &xlock->hlock, &plock->hlock, 1,
+			    NULL, &plock->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) &&
+		    !commit_plock(xlock, plock))
+			return 0;
+	} while (plock_c != plock);
+
+	return 1;
+}
+
+/*
+ * Commit function.
+ */
+void lock_commit_crosslock(struct lockdep_map *lock)
+{
+	struct cross_lock *xlock;
+	unsigned long flags;
+
+	if (!current->plocks)
+		return;
+
+	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 && !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 normal release operation.
+ * return 1: Done. No more release ops is needed.
+ */
+static int lock_release_crosslock(struct lockdep_map *lock)
+{
+	struct cross_lock *xlock;
+
+	if (!graph_lock())
+		return 0;
+
+	xlock = lock->xlock;
+	if (xlock && !--xlock->ref)
+		list_del_rcu(&xlock->xlock_entry);
+
+	graph_unlock();
+	return !!xlock;
+}
+
+static void init_map_noncrosslock(struct lockdep_map *lock)
+{
+	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->xlock = xlock;
+		graph_unlock();
+	}
+	raw_local_irq_restore(flags);
+}
+
+static void init_class_crosslock(struct lock_class *class, int cross)
+{
+	class->cross = cross;
+}
+#endif
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index b9cfdbf..ef9ca8d 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1027,6 +1027,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 any 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

[toc] | [next] | [standalone]

#1482336

On Tue, Sep 13, 2016 at 06:45:06PM +0900, Byungchul Park wrote:
> Crossrelease feature calls a lock 'crosslock' if it is releasable
> in any context. For crosslock, all locks having been held in the
> release context of the crosslock, until eventually the crosslock
> will be released, have dependency with the crosslock.
> 
> Using crossrelease feature, we can detect deadlock possibility even
> for lock_page(), wait_for_complete() and so on.
> 

Completely inadequate.

Please explain how cross-release does what it does. Talk about lock
graphs and such.

I do not have time to reverse engineer this stuff.

[toc] | [prev] | [next] | [standalone]

#1482405

On Tue, Sep 13, 2016 at 12:05:20PM +0200, Peter Zijlstra wrote:
> On Tue, Sep 13, 2016 at 06:45:06PM +0900, Byungchul Park wrote:
> > Crossrelease feature calls a lock 'crosslock' if it is releasable
> > in any context. For crosslock, all locks having been held in the
> > release context of the crosslock, until eventually the crosslock
> > will be released, have dependency with the crosslock.
> > 
> > Using crossrelease feature, we can detect deadlock possibility even
> > for lock_page(), wait_for_complete() and so on.
> > 
> 
> Completely inadequate.
> 
> Please explain how cross-release does what it does. Talk about lock
> graphs and such.
> 
> I do not have time to reverse engineer this stuff.

Blergh, I'll do it anyway.. hold on for an email asking specific
questions.

[toc] | [prev] | [next] | [standalone]

#1482577

On Tue, Sep 13, 2016 at 7:05 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, Sep 13, 2016 at 06:45:06PM +0900, Byungchul Park wrote:
>> Crossrelease feature calls a lock 'crosslock' if it is releasable
>> in any context. For crosslock, all locks having been held in the
>> release context of the crosslock, until eventually the crosslock
>> will be released, have dependency with the crosslock.
>>
>> Using crossrelease feature, we can detect deadlock possibility even
>> for lock_page(), wait_for_complete() and so on.
>>
>
> Completely inadequate.
>
> Please explain how cross-release does what it does. Talk about lock
> graphs and such.

Hello,

Could you tell me about what you intend, in detail?
I'm now asking you since I really don't know it.

The reason I reworked on documentation was to
answer your requests like "explain mathematically",
"tell how it works with graph" and so on. Should I
do anything else? I really don't know it.

If I missed something, please let me know. Then I
can do whatever you want if it's necessary.

> I do not have time to reverse engineer this stuff.

Why don't you read the document in the last patch
first? The document is my answer for your requests
you asked in version 1 thread. Insufficient?

[toc] | [prev] | [next] | [standalone]

#1482573

So the idea is to add support for non-owner serialization primitives,
like completions/semaphores, and so far I've not looked at the code yet.
I did spend 2+ hours trying to decipher your documentation thing, but am
still confused, that thing is exceedingly hard to parse/read.

So the typical scenario would be something like:

L a	L a
	U a
W b	C b

where L := lock, U := unlock, W := wait_for_completion and C :=
complete.

On the left, the blocking thread we can easily observe the 'b depends on
a' relation, since we block while holding a.

On the right however that same relation is hard to see, since by the
time we would run complete, a has already been released.

I _think_ you propose to keep track of all prior held locks and then use
the union of the held list on the block-chain with the prior held list
from the complete context.

The document describes you have a prior held list, and that its a
circular thing, but it then completely fails to specify what gets added
and how its used.

Also, by it being a circular list (of indeterminate, but finite size),
there is the possibility of missing dependencies if they got spooled out
by recent activity.

The document has an example in the section 'How cross release works'
(the 3rd) that simply cannot be. It lists lock action _after_ acquire,
but you place the acquire in wait_for_completion. We _block_ there.

Is this the general idea?

If so, I cannot see how something like:

W a	W b
C b	C a

would work, somewhere in that document it states that this would be
handled by the existing dependencies, but I cannot see how. The blocking
thread (either one) has no held context, therefore the previously
mentioned union of held and prev-held is empty.

The alternative is not doing the union, but then you end up with endless
pointless dependencies afaict.


On the whole 'release context' thing you want to cast lockdep in, please
consider something like:

L a	L b
L b	L a
U a	U a
U b	U b

Note that the release order of locks is immaterial and can generate
'wrong' dependencies. Note how on both sides a is released under b,
failing to observe the stil obvious AB-BA deadlock.

Note that lockdep doesn't model release or anything, it models
blocked-on relations, like PI does.

[toc] | [prev] | [next] | [standalone]

#1482660

On Wed, Sep 14, 2016 at 12:05 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>
>
> So the idea is to add support for non-owner serialization primitives,
> like completions/semaphores, and so far I've not looked at the code yet.
> I did spend 2+ hours trying to decipher your documentation thing, but am
> still confused, that thing is exceedingly hard to parse/read.
>
> So the typical scenario would be something like:
>
> L a     L a
>         U a
> W b     C b
>
> where L := lock, U := unlock, W := wait_for_completion and C :=
> complete.
>
> On the left, the blocking thread we can easily observe the 'b depends on
> a' relation, since we block while holding a.

I think 'a depends on b' relation.

Why does b depend on a? b depends on a's what?

> On the right however that same relation is hard to see, since by the

Yes, there's no dependency on the right side of your example.

> time we would run complete, a has already been released.

I will change your example a little bit.

W b
~~~~~~~ <- serialized
        L a
        U a
        C b

(Remind crossrelease considers dependencies in only case that
lock sequence serialized is observable.)

There's a dependency in this case, like 'b depends on a' relation.
'C b' may not be hit, depending on the result of 'L a', that is,
acquired or not.

> I _think_ you propose to keep track of all prior held locks and then use
> the union of the held list on the block-chain with the prior held list
> from the complete context.

Almost right. Only thing we need to do to consider the union is to
connect two chains of two contexts by adding one dependency 'b -> a'.

> The document describes you have a prior held list, and that its a
> circular thing, but it then completely fails to specify what gets added
> and how its used.

Why does it fail? It keeps them in the form of hlock. This data is enough
to generate dependencies.

> Also, by it being a circular list (of indeterminate, but finite size),
> there is the possibility of missing dependencies if they got spooled out
> by recent activity.

Yes, right. They might be missed. It means just missing some chances to
check a deadlock. It's all. Better than do nothing.

Furthermore, It just only needs 10~50 entries on qemu-i386 4core since
it's optimized as far as possible so that it only considers essential ones
instead of all the prior held list. The number of entries might need to be
changed on a large system. It's future work.

> The document has an example in the section 'How cross release works'
> (the 3rd) that simply cannot be. It lists lock action _after_ acquire,

Could you tell me more? Why cannot it be?

> but you place the acquire in wait_for_completion. We _block_ there.
>
> Is this the general idea?
>
> If so, I cannot see how something like:
>
> W a     W b
> C b     C a

I didn't tell it works in this case. But it can be a future work. I'm not
sure but I don't think making it work is impossible at all. But anyway
current implementation cannot deal with this case.

> would work, somewhere in that document it states that this would be
> handled by the existing dependencies, but I cannot see how. The blocking

Nowhere I mentioned it can be handled.

However it will work if we can identify and add 'a -> b' and 'b -> a'
dependencies. It's fairly possible.

> thread (either one) has no held context, therefore the previously
> mentioned union of held and prev-held is empty.

Right, in current implementation.

> The alternative is not doing the union, but then you end up with endless
> pointless dependencies afaict.

That's a matter of whether or not we can identify additional dependencies.
I proposed the way to find certain and additional dependencies which original
lockdep missed. Of course there might be other dependencies which cannot
be identified with current implementation. It must be a future work.

> On the whole 'release context' thing you want to cast lockdep in, please
> consider something like:
>
> L a     L b
> L b     L a
> U a     U a
> U b     U b
>
> Note that the release order of locks is immaterial and can generate
> 'wrong' dependencies. Note how on both sides a is released under b,

Who said the release order is important? Wrong for what?

Using the way crossrelease works, AB-BA deadlock of course can be
detected, even though typical lock like 'a' and 'b' does not need to use
crossrelease feature at all.

On left side,
L a : queue a
L b : queue b
U a : add 'a -> b' (consider only locks having been tried since L a was held.)
U b : nop

On right side,
L b : queue b
L a : queue a
U a : nop
U b : add 'b -> a' (consider only locks having been tried since L b was held.)

AB-BA deadlock can be detected with dependencies 'a -> b' and 'b -> a'.
Fairly true dependencies can be generated with this concept, and never fail
to observe this kind of deadlock.

> failing to observe the stil obvious AB-BA deadlock.
>
> Note that lockdep doesn't model release or anything, it models
> blocked-on relations, like PI does.

As you said, current lockdep _implementation_ doesn't model it.
There are 2 parts roughly in lockdep.

1. detect(identify) dependency
2. check dependencies in graph to detect deadlock

Precisely, The first part doesn't model it. I think it's good for
optimized behavior. But it misses some dependencies.
So that's what I proposed to provide the chance to users
between more perfect detector and optimized behavior.

I think the second part works perfectly at the moment.

[toc] | [prev] | [next] | [standalone]

#1482729

On Wed, Sep 14, 2016 at 02:12:51AM +0900, Byungchul Park wrote:
> On Wed, Sep 14, 2016 at 12:05 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> >
> >
> > So the idea is to add support for non-owner serialization primitives,
> > like completions/semaphores, and so far I've not looked at the code yet.
> > I did spend 2+ hours trying to decipher your documentation thing, but am
> > still confused, that thing is exceedingly hard to parse/read.
> >
> > So the typical scenario would be something like:
> >
> > L a     L a
> >         U a
> > W b     C b
> >
> > where L := lock, U := unlock, W := wait_for_completion and C :=
> > complete.
> >
> > On the left, the blocking thread we can easily observe the 'b depends on
> > a' relation, since we block while holding a.
> 
> I think 'a depends on b' relation.
> 
> Why does b depend on a? b depends on a's what?

b blocks while holding a. In any case, for the graph it doesn't matter,
its not a directed graph as such, all we care about is acyclic.

> > On the right however that same relation is hard to see, since by the
> 
> Yes, there's no dependency on the right side of your example.

Well, there is, its just not trivially observable. We must be able to
acquire a in order to complete b, therefore there is a dependency.

> > time we would run complete, a has already been released.
> 
> I will change your example a little bit.
> 
> W b
> ~~~~~~~ <- serialized
>         L a
>         U a
>         C b
> 
> (Remind crossrelease considers dependencies in only case that
> lock sequence serialized is observable.)

What does that mean? Any why? This is a random point in time without
actual meaning.

> There's a dependency in this case, like 'b depends on a' relation.
> 'C b' may not be hit, depending on the result of 'L a', that is,
> acquired or not.

With or without a random reference point, the dependency is there.

> > I _think_ you propose to keep track of all prior held locks and then use
> > the union of the held list on the block-chain with the prior held list
> > from the complete context.
> 
> Almost right. Only thing we need to do to consider the union is to
> connect two chains of two contexts by adding one dependency 'b -> a'.

Sure, but how do you arrive at which connection to make. The document is
entirely silent on this crucial point.

The union between the held-locks of the blocked and prev-held-locks of
the release should give a fair indication I think, but then, I've not
thought too hard on this yet.

> > The document describes you have a prior held list, and that its a
> > circular thing, but it then completely fails to specify what gets added
> > and how its used.
> 
> Why does it fail? It keeps them in the form of hlock. This data is enough
> to generate dependencies.

It fails to explain. It just barely mentions you keep them, it doesn't
mention how they're used or why.

> > Also, by it being a circular list (of indeterminate, but finite size),
> > there is the possibility of missing dependencies if they got spooled out
> > by recent activity.
> 
> Yes, right. They might be missed. It means just missing some chances to
> check a deadlock. It's all. Better than do nothing.

Sure, but you didn't specify. Again, the document is very ambiguous and
ill specified.

> > The document has an example in the section 'How cross release works'
> > (the 3rd) that simply cannot be. It lists lock action _after_ acquire,
> 
> Could you tell me more? Why cannot it be?

Once you block you cannot take more locks, that simply doesnt make
sense.

> > but you place the acquire in wait_for_completion. We _block_ there.
> >
> > Is this the general idea?
> >
> > If so, I cannot see how something like:
> >
> > W a     W b
> > C b     C a
> 
> I didn't tell it works in this case. But it can be a future work. I'm not
> sure but I don't think making it work is impossible at all. But anyway
> current implementation cannot deal with this case.

+4. 'crosslock a -> crosslock b' dependency
+
+   Creating this kind of dependency directly is unnecessary since it can
+   be covered by other kinds of dependencies.

Says something different, doesn't it?

> > On the whole 'release context' thing you want to cast lockdep in, please
> > consider something like:
> >
> > L a     L b
> > L b     L a
> > U a     U a
> > U b     U b
> >
> > Note that the release order of locks is immaterial and can generate
> > 'wrong' dependencies. Note how on both sides a is released under b,
> 
> Who said the release order is important? Wrong for what?

Well, again, you mention 'release context' without actually specifying
what you mean with that.

L a
L b
U b

and

L a
L b
U a

Here the unlocks obviously have different context. Without further
specification its simply impossible to tell what you mean.

[toc] | [prev] | [next] | [standalone]

#1482797

On Tue, Sep 13, 2016 at 09:38:29PM +0200, Peter Zijlstra wrote:

> > > I _think_ you propose to keep track of all prior held locks and then use
> > > the union of the held list on the block-chain with the prior held list
> > > from the complete context.
> > 
> > Almost right. Only thing we need to do to consider the union is to
> > connect two chains of two contexts by adding one dependency 'b -> a'.
> 
> Sure, but how do you arrive at which connection to make. The document is
> entirely silent on this crucial point.
> 
> The union between the held-locks of the blocked and prev-held-locks of
> the release should give a fair indication I think, but then, I've not
> thought too hard on this yet.

s/union/intersection/

those that are in both sets.

[toc] | [prev] | [next] | [standalone]

#1482862

On Wed, Sep 14, 2016 at 6:42 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, Sep 13, 2016 at 09:38:29PM +0200, Peter Zijlstra wrote:
>
>> > > I _think_ you propose to keep track of all prior held locks and then use
>> > > the union of the held list on the block-chain with the prior held list
>> > > from the complete context.
>> >
>> > Almost right. Only thing we need to do to consider the union is to
>> > connect two chains of two contexts by adding one dependency 'b -> a'.
>>
>> Sure, but how do you arrive at which connection to make. The document is
>> entirely silent on this crucial point.
>>
>> The union between the held-locks of the blocked and prev-held-locks of
>> the release should give a fair indication I think, but then, I've not
>> thought too hard on this yet.
>
> s/union/intersection/
>
> those that are in both sets.

Precisely speaking, I introduces separate chains.

For example,

1. Held-locks of the blocked,
A -> B -> C (which original lockdep builds)

2. Prev-held-locks of the release
G -> H -> I (which original lockdep builds, too)

3. Cross chain (which I introduced newly)
C -> G

Then the 'A -> B -> C -> G -> H -> I' can be traversed
when bfs is performed.

-- 
Thanks,
Byungchul

[toc] | [prev] | [next] | [standalone]

#1482882

On Wed, Sep 14, 2016 at 4:38 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Wed, Sep 14, 2016 at 02:12:51AM +0900, Byungchul Park wrote:
>> On Wed, Sep 14, 2016 at 12:05 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>> >
>> >
>> > So the idea is to add support for non-owner serialization primitives,
>> > like completions/semaphores, and so far I've not looked at the code yet.
>> > I did spend 2+ hours trying to decipher your documentation thing, but am
>> > still confused, that thing is exceedingly hard to parse/read.
>> >
>> > So the typical scenario would be something like:
>> >
>> > L a     L a
>> >         U a
>> > W b     C b
>> >
>> > where L := lock, U := unlock, W := wait_for_completion and C :=
>> > complete.
>> >
>> > On the left, the blocking thread we can easily observe the 'b depends on
>> > a' relation, since we block while holding a.
>>
>> I think 'a depends on b' relation.
>>
>> Why does b depend on a? b depends on a's what?
>
> b blocks while holding a. In any case, for the graph it doesn't matter,
> its not a directed graph as such, all we care about is acyclic.

It's a directed graph.The meaning of backward traverse is different
from the meaning of forward traverse, isn't it?

>> > On the right however that same relation is hard to see, since by the
>>
>> Yes, there's no dependency on the right side of your example.
>
> Well, there is, its just not trivially observable. We must be able to
> acquire a in order to complete b, therefore there is a dependency.

No. We cannot say there is a dependency unconditionally. There can
be a dependency or not.

L a     L a
        U a
~~~~~~~~~ what if serialized by something?
W b     C b

If something we don't recognize serializes locks, which ensures
'W b' happens after 'L a , U a' in the other context, then there's
no dependency here.

We should say 'b depends on a' in only case that the sequence
'W b and then L a and then C b, where last two ops are in same
context' _actually_ happened at least once. Otherwise, it might
add a false dependency.

It's same as how original lockdep works with typical locks. It adds
a dependency only when a lock is actually hit.

>> > time we would run complete, a has already been released.
>>
>> I will change your example a little bit.
>>
>> W b
>> ~~~~~~~ <- serialized
>>         L a
>>         U a
>>         C b
>>
>> (Remind crossrelease considers dependencies in only case that
>> lock sequence serialized is observable.)
>
> What does that mean? Any why? This is a random point in time without
> actual meaning.

It's not random point. We have to consider meaningful sequences among
those which are globally observable. That's why we need to serialize
those locks. For example,

W b
L a
U a
C b

Once this sequence is observable globally, we can say 'It's possible to
run in this sequence. Is this sequence problematic or not?'.

L a
U a
W b
C b

If only this sequence can be observable, we should not assume
this sequence can be changed. However once the former sequence
happens, it has a possibility to hit the same sequence again later.
So we can check deadlock possibility with the sequence,

_not randomly_.

>> There's a dependency in this case, like 'b depends on a' relation.
>> 'C b' may not be hit, depending on the result of 'L a', that is,
>> acquired or not.
>
> With or without a random reference point, the dependency is there.

The dependency might not be there.

>> > I _think_ you propose to keep track of all prior held locks and then use
>> > the union of the held list on the block-chain with the prior held list
>> > from the complete context.
>>
>> Almost right. Only thing we need to do to consider the union is to
>> connect two chains of two contexts by adding one dependency 'b -> a'.
>
> Sure, but how do you arrive at which connection to make. The document is
> entirely silent on this crucial point.

We need to connect between the crosslock and the first lock among
locks having been acquired since the crosslock was held. Others will be
connected each other by original lockdep.

By the way, does my document miss this description? If so, sorry.
I will check and update it.

> The union between the held-locks of the blocked and prev-held-locks of
> the release should give a fair indication I think, but then, I've not
> thought too hard on this yet.

I make the union only If actually the lock sequence happened once so
that it's globally visible.

>> > The document describes you have a prior held list, and that its a
>> > circular thing, but it then completely fails to specify what gets added
>> > and how its used.
>>
>> Why does it fail? It keeps them in the form of hlock. This data is enough
>> to generate dependencies.
>
> It fails to explain. It just barely mentions you keep them, it doesn't
> mention how they're used or why.

Okay. I need to explain more about that.

>> > Also, by it being a circular list (of indeterminate, but finite size),
>> > there is the possibility of missing dependencies if they got spooled out
>> > by recent activity.
>>
>> Yes, right. They might be missed. It means just missing some chances to
>> check a deadlock. It's all. Better than do nothing.
>
> Sure, but you didn't specify. Again, the document is very ambiguous and
> ill specified.

Yes, I need to supplement the latter half as you said. I will do it.

>
>> > The document has an example in the section 'How cross release works'
>> > (the 3rd) that simply cannot be. It lists lock action _after_ acquire,
>>
>> Could you tell me more? Why cannot it be?
>
> Once you block you cannot take more locks, that simply doesnt make
> sense.

No. Peter.. lockdep check possibilities. All lockdep operations are
performed assuming this same sequence can happen again later but in
a little bit different order between more than two contexts so that actual
deadlock can happen then.

No doubt, it cannot take more locks while blocked at the time. But it's
not important for lockdep to work.

>> > but you place the acquire in wait_for_completion. We _block_ there.
>> >
>> > Is this the general idea?
>> >
>> > If so, I cannot see how something like:
>> >
>> > W a     W b
>> > C b     C a
>>
>> I didn't tell it works in this case. But it can be a future work. I'm not
>> sure but I don't think making it work is impossible at all. But anyway
>> current implementation cannot deal with this case.
>
> +4. 'crosslock a -> crosslock b' dependency
> +
> +   Creating this kind of dependency directly is unnecessary since it can
> +   be covered by other kinds of dependencies.
>
> Says something different, doesn't it?

Really sorry. I made you much confused. I will update it.

>> > On the whole 'release context' thing you want to cast lockdep in, please
>> > consider something like:
>> >
>> > L a     L b
>> > L b     L a
>> > U a     U a
>> > U b     U b
>> >
>> > Note that the release order of locks is immaterial and can generate
>> > 'wrong' dependencies. Note how on both sides a is released under b,
>>
>> Who said the release order is important? Wrong for what?
>
> Well, again, you mention 'release context' without actually specifying
> what you mean with that.
>
> L a
> L b
> U b
>
> and
>
> L a
> L b
> U a
>
> Here the unlocks obviously have different context. Without further
> specification its simply impossible to tell what you mean.

I mentioned what the release context means in the document. Or
I don't understand what you are asking now.

-- 
Thanks,
Byungchul

[toc] | [prev] | [next] | [standalone]

#1482914

On Wed, Sep 14, 2016 at 11:27 AM, Byungchul Park
<max.byungchul.park@gmail.com> wrote:
> On Wed, Sep 14, 2016 at 4:38 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>> On Wed, Sep 14, 2016 at 02:12:51AM +0900, Byungchul Park wrote:
>>> On Wed, Sep 14, 2016 at 12:05 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>>> >
>>> >
>>> > So the idea is to add support for non-owner serialization primitives,
>>> > like completions/semaphores, and so far I've not looked at the code yet.
>>> > I did spend 2+ hours trying to decipher your documentation thing, but am
>>> > still confused, that thing is exceedingly hard to parse/read.
>>> >
>>> > So the typical scenario would be something like:
>>> >
>>> > L a     L a
>>> >         U a
>>> > W b     C b
>>> >
>>> > where L := lock, U := unlock, W := wait_for_completion and C :=
>>> > complete.
>>> >
>>> > On the left, the blocking thread we can easily observe the 'b depends on
>>> > a' relation, since we block while holding a.
>>>
>>> I think 'a depends on b' relation.
>>>
>>> Why does b depend on a? b depends on a's what?
>>
>> b blocks while holding a. In any case, for the graph it doesn't matter,
>> its not a directed graph as such, all we care about is acyclic.
>
> It's a directed graph.The meaning of backward traverse is different
> from the meaning of forward traverse, isn't it?
>
>>> > On the right however that same relation is hard to see, since by the
>>>
>>> Yes, there's no dependency on the right side of your example.
>>
>> Well, there is, its just not trivially observable. We must be able to
>> acquire a in order to complete b, therefore there is a dependency.
>
> No. We cannot say there is a dependency unconditionally. There can
> be a dependency or not.
>
> L a     L a
>         U a
> ~~~~~~~~~ what if serialized by something?
> W b     C b
>
> If something we don't recognize serializes locks, which ensures
> 'W b' happens after 'L a , U a' in the other context, then there's
> no dependency here.
>
> We should say 'b depends on a' in only case that the sequence
> 'W b and then L a and then C b, where last two ops are in same
> context' _actually_ happened at least once. Otherwise, it might
> add a false dependency.
>
> It's same as how original lockdep works with typical locks. It adds
> a dependency only when a lock is actually hit.
>
>>> > time we would run complete, a has already been released.
>>>
>>> I will change your example a little bit.
>>>
>>> W b
>>> ~~~~~~~ <- serialized
>>>         L a
>>>         U a
>>>         C b
>>>
>>> (Remind crossrelease considers dependencies in only case that
>>> lock sequence serialized is observable.)
>>
>> What does that mean? Any why? This is a random point in time without
>> actual meaning.
>
> It's not random point. We have to consider meaningful sequences among
> those which are globally observable. That's why we need to serialize
> those locks. For example,
>
> W b
> L a
> U a
> C b
>
> Once this sequence is observable globally, we can say 'It's possible to
> run in this sequence. Is this sequence problematic or not?'.
>
> L a
> U a
> W b
> C b
>
> If only this sequence can be observable, we should not assume
> this sequence can be changed. However once the former sequence
> happens, it has a possibility to hit the same sequence again later.
> So we can check deadlock possibility with the sequence,
>
> _not randomly_.
>
>>> There's a dependency in this case, like 'b depends on a' relation.
>>> 'C b' may not be hit, depending on the result of 'L a', that is,
>>> acquired or not.
>>
>> With or without a random reference point, the dependency is there.
>
> The dependency might not be there.
>
>>> > I _think_ you propose to keep track of all prior held locks and then use
>>> > the union of the held list on the block-chain with the prior held list
>>> > from the complete context.
>>>
>>> Almost right. Only thing we need to do to consider the union is to
>>> connect two chains of two contexts by adding one dependency 'b -> a'.
>>
>> Sure, but how do you arrive at which connection to make. The document is
>> entirely silent on this crucial point.
>
> We need to connect between the crosslock and the first lock among
> locks having been acquired since the crosslock was held. Others will be
> connected each other by original lockdep.
>
> By the way, does my document miss this description? If so, sorry.
> I will check and update it.
>
>> The union between the held-locks of the blocked and prev-held-locks of
>> the release should give a fair indication I think, but then, I've not
>> thought too hard on this yet.
>
> I make the union only If actually the lock sequence happened once so
> that it's globally visible.
>
>>> > The document describes you have a prior held list, and that its a
>>> > circular thing, but it then completely fails to specify what gets added
>>> > and how its used.
>>>
>>> Why does it fail? It keeps them in the form of hlock. This data is enough
>>> to generate dependencies.
>>
>> It fails to explain. It just barely mentions you keep them, it doesn't
>> mention how they're used or why.
>
> Okay. I need to explain more about that.
>
>>> > Also, by it being a circular list (of indeterminate, but finite size),
>>> > there is the possibility of missing dependencies if they got spooled out
>>> > by recent activity.
>>>
>>> Yes, right. They might be missed. It means just missing some chances to
>>> check a deadlock. It's all. Better than do nothing.
>>
>> Sure, but you didn't specify. Again, the document is very ambiguous and
>> ill specified.
>
> Yes, I need to supplement the latter half as you said. I will do it.
>
>>
>>> > The document has an example in the section 'How cross release works'
>>> > (the 3rd) that simply cannot be. It lists lock action _after_ acquire,
>>>
>>> Could you tell me more? Why cannot it be?
>>
>> Once you block you cannot take more locks, that simply doesnt make
>> sense.
>
> No. Peter.. lockdep check possibilities. All lockdep operations are
> performed assuming this same sequence can happen again later but in
> a little bit different order between more than two contexts so that actual
> deadlock can happen then.

I can see what you are talking about. you are only talking about
wait_for_completion. wait_for_completion is a case more complicated
than lock_page. Could we talk about lock_page first if you don't mind?
And then move to wait_for_complete next?

Anyway even in wait_complete, It's possible like,
(even though it's not much meaningful in case of wait_for_completion)

(Triger complete context to start)
acquire A
wait_for_completion A
   acquire another (e.g. wait.lock)
   release it
   ...
   (actually sleep)

Not much meaningful in wait_for_completion, though it's not wrong.
And this is much meaningful to another crosslock like lock_page.
The target I'm mainly focusing is page lock.

> No doubt, it cannot take more locks while blocked at the time. But it's
> not important for lockdep to work.
>
>>> > but you place the acquire in wait_for_completion. We _block_ there.
>>> >
>>> > Is this the general idea?
>>> >
>>> > If so, I cannot see how something like:
>>> >
>>> > W a     W b
>>> > C b     C a
>>>
>>> I didn't tell it works in this case. But it can be a future work. I'm not
>>> sure but I don't think making it work is impossible at all. But anyway
>>> current implementation cannot deal with this case.
>>
>> +4. 'crosslock a -> crosslock b' dependency
>> +
>> +   Creating this kind of dependency directly is unnecessary since it can
>> +   be covered by other kinds of dependencies.
>>
>> Says something different, doesn't it?
>
> Really sorry. I made you much confused. I will update it.
>
>>> > On the whole 'release context' thing you want to cast lockdep in, please
>>> > consider something like:
>>> >
>>> > L a     L b
>>> > L b     L a
>>> > U a     U a
>>> > U b     U b
>>> >
>>> > Note that the release order of locks is immaterial and can generate
>>> > 'wrong' dependencies. Note how on both sides a is released under b,
>>>
>>> Who said the release order is important? Wrong for what?
>>
>> Well, again, you mention 'release context' without actually specifying
>> what you mean with that.
>>
>> L a
>> L b
>> U b
>>
>> and
>>
>> L a
>> L b
>> U a
>>
>> Here the unlocks obviously have different context. Without further
>> specification its simply impossible to tell what you mean.
>
> I mentioned what the release context means in the document. Or
> I don't understand what you are asking now.
>
> --
> Thanks,
> Byungchul



-- 
Thanks,
Byungchul

[toc] | [prev] | [next] | [standalone]

#1483074

On Wed, Sep 14, 2016 at 11:27:22AM +0900, Byungchul Park wrote:
> > Well, there is, its just not trivially observable. We must be able to
> > acquire a in order to complete b, therefore there is a dependency.
> 
> No. We cannot say there is a dependency unconditionally. There can
> be a dependency or not.
> 
> L a     L a
>         U a
> ~~~~~~~~~ what if serialized by something?

Well, there's no serialization in the example, so no what if.

> W b     C b
> 
> If something we don't recognize serializes locks, which ensures
> 'W b' happens after 'L a , U a' in the other context, then there's
> no dependency here.

Its not there.

> We should say 'b depends on a' in only case that the sequence
> 'W b and then L a and then C b, where last two ops are in same
> context' _actually_ happened at least once. Otherwise, it might
> add a false dependency.
> 
> It's same as how original lockdep works with typical locks. It adds
> a dependency only when a lock is actually hit.

But since these threads are independently scheduled there is no point in
transferring the point in time thread A does W to thread B. There is no
relation there.

B could have already executed the complete or it could not yet have
started execution at all or anything in between, entirely random.

> > What does that mean? Any why? This is a random point in time without
> > actual meaning.
> 
> It's not random point. We have to consider meaningful sequences among
> those which are globally observable. That's why we need to serialize
> those locks.

Serialize how? there is no serialization.

> For example,
> 
> W b
> L a
> U a
> C b
> 
> Once this sequence is observable globally, we can say 'It's possible to
> run in this sequence. Is this sequence problematic or not?'.
> 
> L a
> U a
> W b
> C b
> 
> If only this sequence can be observable, we should not assume
> this sequence can be changed. However once the former sequence
> happens, it has a possibility to hit the same sequence again later.
> So we can check deadlock possibility with the sequence,
> 
> _not randomly_.

I still don't get it.

> We need to connect between the crosslock and the first lock among
> locks having been acquired since the crosslock was held.

Which can be _any_ lock in the history of that thread. It could be
rq->lock from getting the thread scheduled.

> Others will be
> connected each other by original lockdep.
> 
> By the way, does my document miss this description? If so, sorry.
> I will check and update it.

I couldn't find anything useful, but then I could not understand most of
what was written, and I tried hard :-(

[toc] | [prev] | [next] | [standalone]

#1486102

On Wed, Sep 14, 2016 at 10:11:17AM +0200, Peter Zijlstra wrote:
> On Wed, Sep 14, 2016 at 11:27:22AM +0900, Byungchul Park wrote:
> > > Well, there is, its just not trivially observable. We must be able to
> > > acquire a in order to complete b, therefore there is a dependency.
> > 
> > No. We cannot say there is a dependency unconditionally. There can
> > be a dependency or not.
> > 
> > L a     L a
> >         U a
> > ~~~~~~~~~ what if serialized by something?
> 
> Well, there's no serialization in the example, so no what if.

It was a korean traditional holliday for a week so I'm late.

I mean we cannot _ensure_ there's no serialization while lockdep works.
In _the_ case you suggested, you'are right if only those code exists.
But it's meaningless.

> > W b     C b
> > 
> > If something we don't recognize serializes locks, which ensures
> > 'W b' happens after 'L a , U a' in the other context, then there's
> > no dependency here.
> 
> Its not there.
> 
> > We should say 'b depends on a' in only case that the sequence
> > 'W b and then L a and then C b, where last two ops are in same
> > context' _actually_ happened at least once. Otherwise, it might
> > add a false dependency.
> > 
> > It's same as how original lockdep works with typical locks. It adds
> > a dependency only when a lock is actually hit.
> 
> But since these threads are independently scheduled there is no point in
> transferring the point in time thread A does W to thread B. There is no
> relation there.
> 
> B could have already executed the complete or it could not yet have
> started execution at all or anything in between, entirely random.

Of course B could have already executed the complete or it could not yet
have started execution at all or anything in between. But it's not entirely
random.

It might be a random point since they are independently scheduled, but it's
not entirely random. And it's a random point among valid points which lockdep
needs to consider. For example,


CONTEXT 1			CONTEXT 2(forked one)
=========			=====================
(a)				acquire F
acquire A			acquire G
acquire B			wait_for_completion Z
acquire C
(b)				acquire H
fork 2				acquire I
acquire D			acquire J
complete Z			acquire K


I can provide countless examples with which I can say you're wrong.
In this case, all acquires between (a) and (b) must be ignored when
generating dependencies with complete operation of Z. It's never random.

Ideally, it would be of course the best to consider all points (not random
points) after (b) which are valid points which lockdep needs to work with.
But I think it's impossible to parse and identify all synchronizations and
forks in kernel code, furthermore, new synchronization interface can be
introduced in future.

So IMHO it would be the second best to consider random points among valid
points, which anyway actually happened so it's guarrented that it has a
depenency with Z.

It's similar to how lockdep works for typical lock e.g. spin lock. Current
lockdep builds dependecy graph based on call paths which actually happened
in each context, which might be different from each run. Even current
lockdep doesn't parse all code and identify dependencies but works based on
actual call paths in runtime which can be random but will eventually cover
it almost (not perfect).

> > > What does that mean? Any why? This is a random point in time without
> > > actual meaning.
> > 
> > It's not random point. We have to consider meaningful sequences among
> > those which are globally observable. That's why we need to serialize
> > those locks.
> 
> Serialize how? there is no serialization.

I mean I did it in my crossrelease implementation.

> 
> > For example,
> > 
> > W b
> > L a
> > U a
> > C b
> > 
> > Once this sequence is observable globally, we can say 'It's possible to
> > run in this sequence. Is this sequence problematic or not?'.
> > 
> > L a
> > U a
> > W b
> > C b
> > 
> > If only this sequence can be observable, we should not assume
> > this sequence can be changed. However once the former sequence
> > happens, it has a possibility to hit the same sequence again later.
> > So we can check deadlock possibility with the sequence,
> > 
> > _not randomly_.
> 
> I still don't get it.
> 
> > We need to connect between the crosslock and the first lock among
> > locks having been acquired since the crosslock was held.
> 
> Which can be _any_ lock in the history of that thread. It could be
> rq->lock from getting the thread scheduled.

I think I already answered it. Right?

> 
> > Others will be
> > connected each other by original lockdep.
> > 
> > By the way, does my document miss this description? If so, sorry.
> > I will check and update it.
> 
> I couldn't find anything useful, but then I could not understand most of
> what was written, and I tried hard :-(

Thank you for trying it.

[toc] | [prev] | [next] | [standalone]

#1486270

On Mon, Sep 19, 2016 at 11:41:02AM +0900, Byungchul Park wrote:

> > But since these threads are independently scheduled there is no point in
> > transferring the point in time thread A does W to thread B. There is no
> > relation there.
> > 
> > B could have already executed the complete or it could not yet have
> > started execution at all or anything in between, entirely random.
> 
> Of course B could have already executed the complete or it could not yet
> have started execution at all or anything in between. But it's not entirely
> random.
> 
> It might be a random point since they are independently scheduled, but it's
> not entirely random. And it's a random point among valid points which lockdep
> needs to consider. For example,
> 
> 
> CONTEXT 1			CONTEXT 2(forked one)
> =========			=====================
> (a)				acquire F
> acquire A			acquire G
> acquire B			wait_for_completion Z
> acquire C
> (b)				acquire H
> fork 2				acquire I
> acquire D			acquire J
> complete Z			acquire K
> 

I'm hoping you left out the releases for brevity? Because calling fork()
with locks held is _really_ poor form.

> I can provide countless examples with which I can say you're wrong.
> In this case, all acquires between (a) and (b) must be ignored when
> generating dependencies with complete operation of Z.

I still don't get the point. Why does this matter?

Sure, A-C are irrelevant in this example, but I don't see how they're
differently irrelevant from a whole bunch of other prior state action.


Earlier you said the algorithm for selecting the dependency is the first
acquire observed in the completing thread after the
wait_for_completion(). Is this correct?


				W z

	A a
	for (i<0;i<many;i++) {
	  A x[i]
	  R x[i]
	}
	R a

	<IRQ>
	  A b
	  R b
	  C z
	</IRQ>

That would be 'a' in this case, but that isn't at all related. Its just
as irrelevant as your A-C. And we can pick @many as big as needed to
flush the prev held cyclic buffer (although I've no idea how that
matters either).

What we want here is to link z to b, no? That is the last, not the first
acquire, it also is independent of when W happened.

At the same time, picking the last is no guarantee either, since that
can equally miss dependencies. Suppose the IRQ handler did:

	<IRQ>
	  A c
	  R c
	  A b
	  R b
	  C z
	</IRQ>

instead. We'd miss the z depends on c relation, and since they're
independent lock sections, lockdep wouldn't make a b-c relation either.


Clearly I'm still missing stuff...

[toc] | [prev] | [next] | [standalone]

#1487078

On Mon, Sep 19, 2016 at 10:50:09AM +0200, Peter Zijlstra wrote:
> On Mon, Sep 19, 2016 at 11:41:02AM +0900, Byungchul Park wrote:
> 
> > > But since these threads are independently scheduled there is no point in
> > > transferring the point in time thread A does W to thread B. There is no
> > > relation there.
> > > 
> > > B could have already executed the complete or it could not yet have
> > > started execution at all or anything in between, entirely random.
> > 
> > Of course B could have already executed the complete or it could not yet
> > have started execution at all or anything in between. But it's not entirely
> > random.
> > 
> > It might be a random point since they are independently scheduled, but it's
> > not entirely random. And it's a random point among valid points which lockdep
> > needs to consider. For example,
> > 
> > 
> > CONTEXT 1			CONTEXT 2(forked one)
> > =========			=====================
> > (a)				acquire F
> > acquire A			acquire G
> > acquire B			wait_for_completion Z
> > acquire C
> > (b)				acquire H
> > fork 2				acquire I
> > acquire D			acquire J
> > complete Z			acquire K
> > 
> 
> I'm hoping you left out the releases for brevity? Because calling fork()
> with locks held is _really_ poor form.

Exactly. Sorry. I shouldn't have omitted releases.

> 
> > I can provide countless examples with which I can say you're wrong.
> > In this case, all acquires between (a) and (b) must be ignored when
> > generating dependencies with complete operation of Z.
> 
> I still don't get the point. Why does this matter?
> 
> Sure, A-C are irrelevant in this example, but I don't see how they're
> differently irrelevant from a whole bunch of other prior state action.
> 
> 
> Earlier you said the algorithm for selecting the dependency is the first
> acquire observed in the completing thread after the
> wait_for_completion(). Is this correct?

Sorry for insufficient description.

held_locks of left context will be,

time 1: a
time 2: a, x[0]
time 3: a, x[1]
...
time n: b

Between time 1 and time (n-1), 'a' will be the first among held_locks. At
time n, 'b' will be the fist among held_locks. So 'a' and 'b' should be
connected to 'z' if we ignore IRQ context. (I will explain it soon.)

Acquire x[i] is also valid one but crossrelease doesn't take it into
account since original lockdep will cover using 'a -> x[i]'. So only
connections we need are 'z -> a' and 'z -> b'.

> 
> 
> 				W z
> 
> 	A a
> 	for (i<0;i<many;i++) {
> 	  A x[i]
> 	  R x[i]
> 	}
> 	R a
> 
> 	<IRQ>
> 	  A b
> 	  R b
> 	  C z
> 	</IRQ>

My crossrelease implementation distinguishes each IRQ from normal context
or other IRQs in different timeline, even though they might share
held_locks. So in this example, precisely speaking, there are two different
contexts. One is normal context and the other is IRQ context. So only 'A b'
is related with 'W z' in this example.

> 
> That would be 'a' in this case, but that isn't at all related. Its just
> as irrelevant as your A-C. And we can pick @many as big as needed to
> flush the prev held cyclic buffer (although I've no idea how that
> matters either).

I designed crossrelease so that x[i] is not added into ring buffer because
adding 'z -> a' is sufficient and x[i] doesn't need to be taken into
account in this case.

> 
> What we want here is to link z to b, no? That is the last, not the first

Exactly right. Only 'z -> b' must be added under considering IRQ context.
That is the first among held_locks in the IRQ context.

> acquire, it also is independent of when W happened.

If the IRQ is really random, then it can happen before W z and it can also
happen after W z. We cannot determine the time. Then we need to consider all
combination and possibility. It's a key point. We have to consider
dependencies for all possibility.

However, we don't know what synchronizes the flow. So it must be based on
what actually happened, to identify true dependencies.

> 
> At the same time, picking the last is no guarantee either, since that
> can equally miss dependencies. Suppose the IRQ handler did:
> 
> 	<IRQ>
> 	  A c
> 	  R c
> 	  A b
> 	  R b
> 	  C z
> 	</IRQ>
> 

time 1: c (in held_locks)
time 2: b (in held_locks)

So 'c' and 'b' can be the first among held_locks at each moment.
So 'z -> b' and 'z -> c' will be added.

> instead. We'd miss the z depends on c relation, and since they're
> independent lock sections, lockdep wouldn't make a b-c relation either.
> 
> 
> Clearly I'm still missing stuff...

Sorry for insufficient description. I tried to describ crossrelease in as
much detail as possible, really.

The reason why I consider only the first among valid locks in held_locks is
simple. For example,

Context 1
A a -> A b -> A crosslock -> R a -> R b

Context 2
A c -> A d -> R d -> R the crosslock -> R c

If 'A c' after 'A crosslock' is possible, then 'A crosslock' does not only
depends on 'A c' but also 'A d'. But all dependencies we need to add is only
'crosslock -> c' because 'crosslock -> d' will be covered by 'crosslock ->
c' and 'a -> b'. 'a -> b' is added by original lockdep.

[toc] | [prev] | [next] | [standalone]

#1487094

On Tue, Sep 20, 2016 at 02:50:38PM +0900, Byungchul Park wrote:
> On Mon, Sep 19, 2016 at 10:50:09AM +0200, Peter Zijlstra wrote:
> > On Mon, Sep 19, 2016 at 11:41:02AM +0900, Byungchul Park wrote:
> > 
> > > > But since these threads are independently scheduled there is no point in
> > > > transferring the point in time thread A does W to thread B. There is no
> > > > relation there.
> > > > 
> > > > B could have already executed the complete or it could not yet have
> > > > started execution at all or anything in between, entirely random.
> > > 
> > > Of course B could have already executed the complete or it could not yet
> > > have started execution at all or anything in between. But it's not entirely
> > > random.
> > > 
> > > It might be a random point since they are independently scheduled, but it's
> > > not entirely random. And it's a random point among valid points which lockdep
> > > needs to consider. For example,
> > > 
> > > 
> > > CONTEXT 1			CONTEXT 2(forked one)
> > > =========			=====================
> > > (a)				acquire F
> > > acquire A			acquire G
> > > acquire B			wait_for_completion Z
> > > acquire C
> > > (b)				acquire H
> > > fork 2				acquire I
> > > acquire D			acquire J
> > > complete Z			acquire K
> > > 
> > 
> > I'm hoping you left out the releases for brevity? Because calling fork()
> > with locks held is _really_ poor form.
> 
> Exactly. Sorry. I shouldn't have omitted releases.
> 
> > 
> > > I can provide countless examples with which I can say you're wrong.
> > > In this case, all acquires between (a) and (b) must be ignored when
> > > generating dependencies with complete operation of Z.
> > 
> > I still don't get the point. Why does this matter?
> > 
> > Sure, A-C are irrelevant in this example, but I don't see how they're
> > differently irrelevant from a whole bunch of other prior state action.
> > 
> > 
> > Earlier you said the algorithm for selecting the dependency is the first
> > acquire observed in the completing thread after the
> > wait_for_completion(). Is this correct?
> 
> Sorry for insufficient description.
> 
> held_locks of left context will be,
> 
> time 1: a
> time 2: a, x[0]
> time 3: a, x[1]
> ...
> time n: b
> 
> Between time 1 and time (n-1), 'a' will be the first among held_locks. At
> time n, 'b' will be the fist among held_locks. So 'a' and 'b' should be
> connected to 'z' if we ignore IRQ context. (I will explain it soon.)
> 
> Acquire x[i] is also valid one but crossrelease doesn't take it into
> account since original lockdep will cover using 'a -> x[i]'. So only
> connections we need are 'z -> a' and 'z -> b'.
> 
> > 
> > 
> > 				W z
> > 
> > 	A a
> > 	for (i<0;i<many;i++) {
> > 	  A x[i]
> > 	  R x[i]
> > 	}
> > 	R a
> > 
> > 	<IRQ>
> > 	  A b
> > 	  R b
> > 	  C z
> > 	</IRQ>
> 
> My crossrelease implementation distinguishes each IRQ from normal context
> or other IRQs in different timeline, even though they might share
> held_locks. So in this example, precisely speaking, there are two different
> contexts. One is normal context and the other is IRQ context. So only 'A b'
> is related with 'W z' in this example.
> 
> > 
> > That would be 'a' in this case, but that isn't at all related. Its just
> > as irrelevant as your A-C. And we can pick @many as big as needed to
> > flush the prev held cyclic buffer (although I've no idea how that
> > matters either).
> 
> I designed crossrelease so that x[i] is not added into ring buffer because
> adding 'z -> a' is sufficient and x[i] doesn't need to be taken into
> account in this case.
> 
> > 
> > What we want here is to link z to b, no? That is the last, not the first
> 
> Exactly right. Only 'z -> b' must be added under considering IRQ context.
> That is the first among held_locks in the IRQ context.
> 
> > acquire, it also is independent of when W happened.
> 
> If the IRQ is really random, then it can happen before W z and it can also
> happen after W z. We cannot determine the time. Then we need to consider all
> combination and possibility. It's a key point. We have to consider
> dependencies for all possibility.
> 
> However, we don't know what synchronizes the flow. So it must be based on
> what actually happened, to identify true dependencies.
> 
> > 
> > At the same time, picking the last is no guarantee either, since that
> > can equally miss dependencies. Suppose the IRQ handler did:
> > 
> > 	<IRQ>
> > 	  A c
> > 	  R c
> > 	  A b
> > 	  R b
> > 	  C z
> > 	</IRQ>
> > 
> 
> time 1: c (in held_locks)
> time 2: b (in held_locks)
> 
> So 'c' and 'b' can be the first among held_locks at each moment.
> So 'z -> b' and 'z -> c' will be added.
> 
> > instead. We'd miss the z depends on c relation, and since they're
> > independent lock sections, lockdep wouldn't make a b-c relation either.
> > 
> > 
> > Clearly I'm still missing stuff...
> 
> Sorry for insufficient description. I tried to describ crossrelease in as
> much detail as possible, really.
> 
> The reason why I consider only the first among valid locks in held_locks is
> simple. For example,
> 
> Context 1
> A a -> A b -> A crosslock -> R a -> R b

Here, '->' represents the order executing A(cquire)s and R(elease)s.

_Not_ dependency.

> 
> Context 2
> A c -> A d -> R d -> R the crosslock -> R c
> 
> If 'A c' after 'A crosslock' is possible, then 'A crosslock' does not only
> depends on 'A c' but also 'A d'. But all dependencies we need to add is only
> 'crosslock -> c' because 'crosslock -> d' will be covered by 'crosslock ->
> c' and 'a -> b'. 'a -> b' is added by original lockdep.

[toc] | [prev] | [next] | [standalone]

#1487756

On Tue, Sep 20, 2016 at 02:50:38PM +0900, Byungchul Park wrote:
> On Mon, Sep 19, 2016 at 10:50:09AM +0200, Peter Zijlstra wrote:
> > On Mon, Sep 19, 2016 at 11:41:02AM +0900, Byungchul Park wrote:
> > 
> > > > But since these threads are independently scheduled there is no point in
> > > > transferring the point in time thread A does W to thread B. There is no
> > > > relation there.
> > > > 
> > > > B could have already executed the complete or it could not yet have
> > > > started execution at all or anything in between, entirely random.
> > > 
> > > Of course B could have already executed the complete or it could not yet
> > > have started execution at all or anything in between. But it's not entirely
> > > random.
> > > 
> > > It might be a random point since they are independently scheduled, but it's
> > > not entirely random. And it's a random point among valid points which lockdep
> > > needs to consider. For example,
> > > 
> > > 
> > > CONTEXT 1			CONTEXT 2(forked one)
> > > =========			=====================
> > > (a)				acquire F
> > > acquire A			acquire G
> > > acquire B			wait_for_completion Z
> > > acquire C
> > > (b)				acquire H
> > > fork 2				acquire I
> > > acquire D			acquire J
> > > complete Z			acquire K
> > > 
> > 
> > I'm hoping you left out the releases for brevity? Because calling fork()
> > with locks held is _really_ poor form.
> 
> Exactly. Sorry. I shouldn't have omitted releases.
> 
> > 
> > > I can provide countless examples with which I can say you're wrong.
> > > In this case, all acquires between (a) and (b) must be ignored when
> > > generating dependencies with complete operation of Z.
> > 
> > I still don't get the point. Why does this matter?
> > 
> > Sure, A-C are irrelevant in this example, but I don't see how they're
> > differently irrelevant from a whole bunch of other prior state action.
> > 
> > 
> > Earlier you said the algorithm for selecting the dependency is the first
> > acquire observed in the completing thread after the
> > wait_for_completion(). Is this correct?
> 
> Sorry for insufficient description.
> 
> held_locks of left context will be,
> 
> time 1: a
> time 2: a, x[0]
> time 3: a, x[1]
> ...
> time n: b
> 
> Between time 1 and time (n-1), 'a' will be the first among held_locks. At
> time n, 'b' will be the fist among held_locks. So 'a' and 'b' should be
> connected to 'z' if we ignore IRQ context. (I will explain it soon.)
> 
> Acquire x[i] is also valid one but crossrelease doesn't take it into
> account since original lockdep will cover using 'a -> x[i]'. So only

... since lockdep will cover 'z -> x[i]' using 'z -> a' and 'a -> x[i]' ...

> connections we need are 'z -> a' and 'z -> b'.
> 
> > 
> > 
> > 				W z
> > 
> > 	A a
> > 	for (i<0;i<many;i++) {
> > 	  A x[i]
> > 	  R x[i]
> > 	}
> > 	R a
> > 
> > 	<IRQ>
> > 	  A b
> > 	  R b
> > 	  C z
> > 	</IRQ>
> 
> My crossrelease implementation distinguishes each IRQ from normal context
> or other IRQs in different timeline, even though they might share
> held_locks. So in this example, precisely speaking, there are two different
> contexts. One is normal context and the other is IRQ context. So only 'A b'
> is related with 'W z' in this example.
> 
> > 
> > That would be 'a' in this case, but that isn't at all related. Its just
> > as irrelevant as your A-C. And we can pick @many as big as needed to
> > flush the prev held cyclic buffer (although I've no idea how that
> > matters either).
> 
> I designed crossrelease so that x[i] is not added into ring buffer because
> adding 'z -> a' is sufficient and x[i] doesn't need to be taken into
> account in this case.
> 
> > 
> > What we want here is to link z to b, no? That is the last, not the first
> 
> Exactly right. Only 'z -> b' must be added under considering IRQ context.
> That is the first among held_locks in the IRQ context.
> 
> > acquire, it also is independent of when W happened.
> 
> If the IRQ is really random, then it can happen before W z and it can also
> happen after W z. We cannot determine the time. Then we need to consider all
> combination and possibility. It's a key point. We have to consider
> dependencies for all possibility.

                       possibilities.

> 
> However, we don't know what synchronizes the flow. So it must be based on
                   ^^^
                 generally

> what actually happened, to identify true dependencies.
> 
> > 
> > At the same time, picking the last is no guarantee either, since that
> > can equally miss dependencies. Suppose the IRQ handler did:
> > 
> > 	<IRQ>
> > 	  A c
> > 	  R c
> > 	  A b
> > 	  R b
> > 	  C z
> > 	</IRQ>
> > 
> 
> time 1: c (in held_locks)
> time 2: b (in held_locks)
> 
> So 'c' and 'b' can be the first among held_locks at each moment.
                 ^^^^^^
                   are

> So 'z -> b' and 'z -> c' will be added.
> 
> > instead. We'd miss the z depends on c relation, and since they're
> > independent lock sections, lockdep wouldn't make a b-c relation either.
> > 
> > 
> > Clearly I'm still missing stuff...
> 
> Sorry for insufficient description. I tried to describ crossrelease in as
> much detail as possible, really.
> 
> The reason why I consider only the first among valid locks in held_locks is
> simple. For example,
> 
> Context 1
> A a -> A b -> A crosslock -> R a -> R b

I meant,

Context 1
=========
A a
A b
A crosslock
R a
R b

> 
> Context 2
> A c -> A d -> R d -> R the crosslock -> R c

Context 2
=========
A c
A d
R d
R the crosslock
R c

> 
> If 'A c' after 'A crosslock' is possible, then 'A crosslock' does not only
> depends on 'A c' but also 'A d'. But all dependencies we need to add is only
> 'crosslock -> c' because 'crosslock -> d' will be covered by 'crosslock ->
> c' and 'a -> b'. Here, 'a -> b' is added by original lockdep.

[toc] | [prev] | [next] | [standalone]

#1488515

On Mon, Sep 19, 2016 at 10:50:09AM +0200, Peter Zijlstra wrote:
> Clearly I'm still missing stuff...

By the way.. do I have to explain more? Lack of explanation?

It would be the best to consider 'all valid acquires', which can occur
deadlock, but it looks impossible without parsing all code in head.

So it would be the safest to rely on 'acquires which actually happened',
even though it might be 'random acquires' among all valid acquires.

This conservative appoach is exactly same as how original lockdep is doing.
Let me explain more if you doubt it.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web