[PATCH 00/28] Optimize IRQ usage checks and other small bits

[PATCH 00/28] Optimize IRQ usage checks and other small bits

[Yuyang Du]

It would be desirable to optimize IRQ usage related checks as they
traverse dependency graph multiple times, especially for irq-unsafe
usage checks with backward search since most of the locks are
irq-unsafe.

This series completely removes backward dependencies. The idea is to
mark locks whether they can be reached from irq-safe locks in forward
graph traverses after irq-safe locks are encountered.

As a result, this series not only cuts the dependency list entries by
half and saves memory, but also significantly reduces both forward and
backward checks, which is briefly demonstrated on a simple workload:
Linux kernel build (i.e., make clean; reboot; make vmlinux -j8).

Results:

------
Before
------

direct dependencies:                  6900 [max: 32768]
max bfs queue depth:                   272
find-mask forwards checks:            2875
find-mask backwards checks:          50229

-----
After
-----

direct dependencies:                  3444 [max: 16384]   ( -  50 % )
max bfs queue depth:                   223                ( -  18 % )
find-mask forwards checks:             370                ( -  87 % )
find-mask backwards checks:              0                ( - 100 % )


The patches are organized as follows:

Patches 1 - 18
--------------
My previous small improvements. They are trivial but each is made for a
reason, so I still post them here. Please give them a look, Peter. I
have carried them for a while and rebased them a couple of times solving
confilicts.

Patches 19 - 28
---------------
The new IRQ check algorithm implementation is fairly long, so I tried to
divide it into as many patches as I can (actually this does not help
much). Also I tried to describe what it does in changelogs as detailed
as I can.

The performance numbers have not considered Frederic's recent big
improvements. Anyway, this series happened in parallel and I'd be happy
to rebase it.

HEAD: 7037e8d0af6c8ce5657c83e894c756ee1d33ce80

Thanks,
Yuyang

--

Yuyang Du (28):
  locking/lockdep: Change all print_*() return type to void
  locking/lockdep: Add description and explanation in lockdep design doc
  locking/lockdep: Adjust lock usage bit character checks
  locking/lockdep: Remove useless conditional macro
  locking/lockdep: Print the right depth for chain key colission
  locking/lockdep: Update obsolete struct field description
  locking/lockdep: Use lockdep_init_task for task initiation
    consistently
  locking/lockdep: Define INITIAL_CHAIN_KEY for chain keys to start with
  locking/lockdep: Change the range of class_idx in held_lock struct
  locking/lockdep: Remove unused argument in validate_chain() and
    check_deadlock()
  locking/lockdep: Update comment
  locking/lockdep: Change type of the element field in circular_queue
  locking/lockdep: Change the return type of __cq_dequeue()
  locking/lockdep: Avoid constant checks in __bfs by using offset
    reference
  locking/lockdep: Update comments on dependency search
  locking/lockdep: Add explanation to lock usage rules in lockdep design
    doc
  locking/lockdep: Remove redundant argument in check_deadlock
  locking/lockdep: Remove unused argument in __lock_release
  locking/lockdep: Optimize irq usage check when marking lock usage bit
  locking/lockdep: Refactorize check_noncircular and check_redundant
  locking/lockdep: Consolidate lock usage bit initialization
  locking/lockdep: Adjust new bit cases in mark_lock
  locking/lockdep: Update irqsafe lock bitmaps
  locking/lockdep: Remove !dir in lock irq usage check
  locking/lockdep: Implement new IRQ usage checking algorithm
  locking/lockdep: Remove __bfs
  locking/lockdep: Remove locks_before
  locking/lockdep: Reduce lock_list_entries by half

 Documentation/locking/lockdep-design.txt |  107 +++-
 include/linux/lockdep.h                  |   51 +-
 init/init_task.c                         |    2 +
 kernel/fork.c                            |    3 -
 kernel/locking/lockdep.c                 | 1033 ++++++++++++++++++------------
 kernel/locking/lockdep_internals.h       |   19 +-
 kernel/locking/lockdep_proc.c            |    1 -
 7 files changed, 757 insertions(+), 459 deletions(-)

-- 
1.8.3.1

[PATCH 01/28] locking/lockdep: Change all print_*() return type to void

[Yuyang Du]

Since none of the print_*() function's return value is necessary, change
their return type to void. No functional change.

In cases where an invariable return value is used, this change slightly
improves readability, i.e.:

	print_x();
	return 0;

is definitely better than:

	return print_x(); /* where print_x() always returns 0 */

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 197 ++++++++++++++++++++++++-----------------------
 1 file changed, 101 insertions(+), 96 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 147ae0a..4bf396b 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1422,16 +1422,15 @@ static void print_lock_trace(struct lock_trace *trace, unsigned int spaces)
  * Print a dependency chain entry (this is only done when a deadlock
  * has been detected):
  */
-static noinline int
+static noinline void
 print_circular_bug_entry(struct lock_list *target, int depth)
 {
 	if (debug_locks_silent)
-		return 0;
+		return;
 	printk("\n-> #%u", depth);
 	print_lock_name(target->class);
 	printk(KERN_CONT ":\n");
 	print_lock_trace(&target->trace, 6);
-	return 0;
 }
 
 static void
@@ -1488,7 +1487,7 @@ static void print_lock_trace(struct lock_trace *trace, unsigned int spaces)
  * When a circular dependency is detected, print the
  * header first:
  */
-static noinline int
+static noinline void
 print_circular_bug_header(struct lock_list *entry, unsigned int depth,
 			struct held_lock *check_src,
 			struct held_lock *check_tgt)
@@ -1496,7 +1495,7 @@ static void print_lock_trace(struct lock_trace *trace, unsigned int spaces)
 	struct task_struct *curr = current;
 
 	if (debug_locks_silent)
-		return 0;
+		return;
 
 	pr_warn("\n");
 	pr_warn("======================================================\n");
@@ -1514,8 +1513,6 @@ static void print_lock_trace(struct lock_trace *trace, unsigned int spaces)
 	pr_warn("\nthe existing dependency chain (in reverse order) is:\n");
 
 	print_circular_bug_entry(entry, depth);
-
-	return 0;
 }
 
 static inline int class_equal(struct lock_list *entry, void *data)
@@ -1523,7 +1520,7 @@ static inline int class_equal(struct lock_list *entry, void *data)
 	return entry->class == data;
 }
 
-static noinline int print_circular_bug(struct lock_list *this,
+static noinline void print_circular_bug(struct lock_list *this,
 				       struct lock_list *target,
 				       struct held_lock *check_src,
 				       struct held_lock *check_tgt)
@@ -1534,10 +1531,10 @@ static noinline int print_circular_bug(struct lock_list *this,
 	int depth;
 
 	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
-		return 0;
+		return;
 
 	if (!save_trace(&this->trace))
-		return 0;
+		return;
 
 	depth = get_lock_depth(target);
 
@@ -1559,21 +1556,17 @@ static noinline int print_circular_bug(struct lock_list *this,
 
 	printk("\nstack backtrace:\n");
 	dump_stack();
-
-	return 0;
 }
 
-static noinline int print_bfs_bug(int ret)
+static noinline void print_bfs_bug(int ret)
 {
 	if (!debug_locks_off_graph_unlock())
-		return 0;
+		return;
 
 	/*
 	 * Breadth-first-search failed, graph got corrupted?
 	 */
 	WARN(1, "lockdep bfs error:%d\n", ret);
-
-	return 0;
 }
 
 static int noop_count(struct lock_list *entry, void *data)
@@ -1756,7 +1749,7 @@ static void print_lock_class_header(struct lock_class *class, int depth)
  */
 static void __used
 print_shortest_lock_dependencies(struct lock_list *leaf,
-				struct lock_list *root)
+				 struct lock_list *root)
 {
 	struct lock_list *entry = leaf;
 	int depth;
@@ -1778,8 +1771,6 @@ static void print_lock_class_header(struct lock_class *class, int depth)
 		entry = get_lock_parent(entry);
 		depth--;
 	} while (entry && (depth >= 0));
-
-	return;
 }
 
 static void
@@ -1838,7 +1829,7 @@ static void print_lock_class_header(struct lock_class *class, int depth)
 	printk("\n *** DEADLOCK ***\n\n");
 }
 
-static int
+static void
 print_bad_irq_dependency(struct task_struct *curr,
 			 struct lock_list *prev_root,
 			 struct lock_list *next_root,
@@ -1851,7 +1842,7 @@ static void print_lock_class_header(struct lock_class *class, int depth)
 			 const char *irqclass)
 {
 	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
-		return 0;
+		return;
 
 	pr_warn("\n");
 	pr_warn("=====================================================\n");
@@ -1897,19 +1888,17 @@ static void print_lock_class_header(struct lock_class *class, int depth)
 
 	pr_warn("\nthe dependencies between %s-irq-safe lock and the holding lock:\n", irqclass);
 	if (!save_trace(&prev_root->trace))
-		return 0;
+		return;
 	print_shortest_lock_dependencies(backwards_entry, prev_root);
 
 	pr_warn("\nthe dependencies between the lock to be acquired");
 	pr_warn(" and %s-irq-unsafe lock:\n", irqclass);
 	if (!save_trace(&next_root->trace))
-		return 0;
+		return;
 	print_shortest_lock_dependencies(forwards_entry, next_root);
 
 	pr_warn("\nstack backtrace:\n");
 	dump_stack();
-
-	return 0;
 }
 
 static int
@@ -1926,23 +1915,28 @@ static void print_lock_class_header(struct lock_class *class, int depth)
 
 	this.class = hlock_class(prev);
 	ret = find_usage_backwards(&this, lock_flag(bit_backwards), &target_entry);
-	if (ret < 0)
-		return print_bfs_bug(ret);
+	if (ret < 0) {
+		print_bfs_bug(ret);
+		return 0;
+	}
 	if (ret == 1)
 		return ret;
 
 	that.parent = NULL;
 	that.class = hlock_class(next);
 	ret = find_usage_forwards(&that, lock_flag(bit_forwards), &target_entry1);
-	if (ret < 0)
-		return print_bfs_bug(ret);
+	if (ret < 0) {
+		print_bfs_bug(ret);
+		return 0;
+	}
 	if (ret == 1)
 		return ret;
 
-	return print_bad_irq_dependency(curr, &this, &that,
-			target_entry, target_entry1,
-			prev, next,
-			bit_backwards, bit_forwards, irqclass);
+	print_bad_irq_dependency(curr, &this, &that,
+				 target_entry, target_entry1,
+				 prev, next,
+				 bit_backwards, bit_forwards, irqclass);
+	return 0;
 }
 
 static const char *state_names[] = {
@@ -2048,8 +2042,7 @@ static inline void inc_chains(void)
 #endif
 
 static void
-print_deadlock_scenario(struct held_lock *nxt,
-			     struct held_lock *prv)
+print_deadlock_scenario(struct held_lock *nxt, struct held_lock *prv)
 {
 	struct lock_class *next = hlock_class(nxt);
 	struct lock_class *prev = hlock_class(prv);
@@ -2067,12 +2060,12 @@ static inline void inc_chains(void)
 	printk(" May be due to missing lock nesting notation\n\n");
 }
 
-static int
+static void
 print_deadlock_bug(struct task_struct *curr, struct held_lock *prev,
 		   struct held_lock *next)
 {
 	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
-		return 0;
+		return;
 
 	pr_warn("\n");
 	pr_warn("============================================\n");
@@ -2091,8 +2084,6 @@ static inline void inc_chains(void)
 
 	pr_warn("\nstack backtrace:\n");
 	dump_stack();
-
-	return 0;
 }
 
 /*
@@ -2134,7 +2125,8 @@ static inline void inc_chains(void)
 		if (nest)
 			return 2;
 
-		return print_deadlock_bug(curr, prev, next);
+		print_deadlock_bug(curr, prev, next);
+		return 0;
 	}
 	return 1;
 }
@@ -2201,10 +2193,14 @@ static inline void inc_chains(void)
 	this.class = hlock_class(next);
 	this.parent = NULL;
 	ret = check_noncircular(&this, hlock_class(prev), &target_entry);
-	if (unlikely(!ret))
-		return print_circular_bug(&this, target_entry, next, prev);
-	else if (unlikely(ret < 0))
-		return print_bfs_bug(ret);
+	if (unlikely(!ret)) {
+		print_circular_bug(&this, target_entry, next, prev);
+		return 0;
+	}
+	else if (unlikely(ret < 0)) {
+		print_bfs_bug(ret);
+		return 0;
+	}
 
 	if (!check_prev_add_irq(curr, prev, next))
 		return 0;
@@ -2245,8 +2241,10 @@ static inline void inc_chains(void)
 		debug_atomic_inc(nr_redundant);
 		return 2;
 	}
-	if (ret < 0)
-		return print_bfs_bug(ret);
+	if (ret < 0) {
+		print_bfs_bug(ret);
+		return 0;
+	}
 
 
 	if (!save_trace(&trace))
@@ -2773,8 +2771,7 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
 
 
-static void
-print_usage_bug_scenario(struct held_lock *lock)
+static void print_usage_bug_scenario(struct held_lock *lock)
 {
 	struct lock_class *class = hlock_class(lock);
 
@@ -2791,12 +2788,12 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 	printk("\n *** DEADLOCK ***\n\n");
 }
 
-static int
+static void
 print_usage_bug(struct task_struct *curr, struct held_lock *this,
 		enum lock_usage_bit prev_bit, enum lock_usage_bit new_bit)
 {
 	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
-		return 0;
+		return;
 
 	pr_warn("\n");
 	pr_warn("================================\n");
@@ -2826,8 +2823,6 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 
 	pr_warn("\nstack backtrace:\n");
 	dump_stack();
-
-	return 0;
 }
 
 /*
@@ -2837,8 +2832,10 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 valid_state(struct task_struct *curr, struct held_lock *this,
 	    enum lock_usage_bit new_bit, enum lock_usage_bit bad_bit)
 {
-	if (unlikely(hlock_class(this)->usage_mask & (1 << bad_bit)))
-		return print_usage_bug(curr, this, bad_bit, new_bit);
+	if (unlikely(hlock_class(this)->usage_mask & (1 << bad_bit))) {
+		print_usage_bug(curr, this, bad_bit, new_bit);
+		return 0;
+	}
 	return 1;
 }
 
@@ -2846,7 +2843,7 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 /*
  * print irq inversion bug:
  */
-static int
+static void
 print_irq_inversion_bug(struct task_struct *curr,
 			struct lock_list *root, struct lock_list *other,
 			struct held_lock *this, int forwards,
@@ -2857,7 +2854,7 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 	int depth;
 
 	if (!debug_locks_off_graph_unlock() || debug_locks_silent)
-		return 0;
+		return;
 
 	pr_warn("\n");
 	pr_warn("========================================================\n");
@@ -2898,13 +2895,11 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 
 	pr_warn("\nthe shortest dependencies between 2nd lock and 1st lock:\n");
 	if (!save_trace(&root->trace))
-		return 0;
+		return;
 	print_shortest_lock_dependencies(other, root);
 
 	pr_warn("\nstack backtrace:\n");
 	dump_stack();
-
-	return 0;
 }
 
 /*
@@ -2922,13 +2917,16 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 	root.parent = NULL;
 	root.class = hlock_class(this);
 	ret = find_usage_forwards(&root, lock_flag(bit), &target_entry);
-	if (ret < 0)
-		return print_bfs_bug(ret);
+	if (ret < 0) {
+		print_bfs_bug(ret);
+		return 0;
+	}
 	if (ret == 1)
 		return ret;
 
-	return print_irq_inversion_bug(curr, &root, target_entry,
-					this, 1, irqclass);
+	print_irq_inversion_bug(curr, &root, target_entry,
+				this, 1, irqclass);
+	return 0;
 }
 
 /*
@@ -2946,13 +2944,16 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 	root.parent = NULL;
 	root.class = hlock_class(this);
 	ret = find_usage_backwards(&root, lock_flag(bit), &target_entry);
-	if (ret < 0)
-		return print_bfs_bug(ret);
+	if (ret < 0) {
+		print_bfs_bug(ret);
+		return 0;
+	}
 	if (ret == 1)
 		return ret;
 
-	return print_irq_inversion_bug(curr, &root, target_entry,
-					this, 0, irqclass);
+	print_irq_inversion_bug(curr, &root, target_entry,
+				this, 0, irqclass);
+	return 0;
 }
 
 void print_irqtrace_events(struct task_struct *curr)
@@ -3495,15 +3496,15 @@ void lockdep_init_map(struct lockdep_map *lock, const char *name,
 struct lock_class_key __lockdep_no_validate__;
 EXPORT_SYMBOL_GPL(__lockdep_no_validate__);
 
-static int
+static void
 print_lock_nested_lock_not_held(struct task_struct *curr,
 				struct held_lock *hlock,
 				unsigned long ip)
 {
 	if (!debug_locks_off())
-		return 0;
+		return;
 	if (debug_locks_silent)
-		return 0;
+		return;
 
 	pr_warn("\n");
 	pr_warn("==================================\n");
@@ -3525,8 +3526,6 @@ void lockdep_init_map(struct lockdep_map *lock, const char *name,
 
 	pr_warn("\nstack backtrace:\n");
 	dump_stack();
-
-	return 0;
 }
 
 static int __lock_is_held(const struct lockdep_map *lock, int read);
@@ -3675,8 +3674,10 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	}
 	chain_key = iterate_chain_key(chain_key, class_idx);
 
-	if (nest_lock && !__lock_is_held(nest_lock, -1))
-		return print_lock_nested_lock_not_held(curr, hlock, ip);
+	if (nest_lock && !__lock_is_held(nest_lock, -1)) {
+		print_lock_nested_lock_not_held(curr, hlock, ip);
+		return 0;
+	}
 
 	if (!debug_locks_silent) {
 		WARN_ON_ONCE(depth && !hlock_class(hlock - 1)->key);
@@ -3712,14 +3713,14 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	return 1;
 }
 
-static int
-print_unlock_imbalance_bug(struct task_struct *curr, struct lockdep_map *lock,
-			   unsigned long ip)
+static void print_unlock_imbalance_bug(struct task_struct *curr,
+				       struct lockdep_map *lock,
+				       unsigned long ip)
 {
 	if (!debug_locks_off())
-		return 0;
+		return;
 	if (debug_locks_silent)
-		return 0;
+		return;
 
 	pr_warn("\n");
 	pr_warn("=====================================\n");
@@ -3737,8 +3738,6 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 
 	pr_warn("\nstack backtrace:\n");
 	dump_stack();
-
-	return 0;
 }
 
 static int match_held_lock(const struct held_lock *hlock,
@@ -3857,8 +3856,10 @@ static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
 		return 0;
 
 	hlock = find_held_lock(curr, lock, depth, &i);
-	if (!hlock)
-		return print_unlock_imbalance_bug(curr, lock, ip);
+	if (!hlock) {
+		print_unlock_imbalance_bug(curr, lock, ip);
+		return 0;
+	}
 
 	lockdep_init_map(lock, name, key, 0);
 	class = register_lock_class(lock, subclass, 0);
@@ -3898,8 +3899,10 @@ static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
 		return 0;
 
 	hlock = find_held_lock(curr, lock, depth, &i);
-	if (!hlock)
-		return print_unlock_imbalance_bug(curr, lock, ip);
+	if (!hlock) {
+		print_unlock_imbalance_bug(curr, lock, ip);
+		return 0;
+	}
 
 	curr->lockdep_depth = i;
 	curr->curr_chain_key = hlock->prev_chain_key;
@@ -3943,16 +3946,20 @@ static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
 	 * So we're all set to release this lock.. wait what lock? We don't
 	 * own any locks, you've been drinking again?
 	 */
-	if (DEBUG_LOCKS_WARN_ON(depth <= 0))
-		 return print_unlock_imbalance_bug(curr, lock, ip);
+	if (DEBUG_LOCKS_WARN_ON(depth <= 0)) {
+		print_unlock_imbalance_bug(curr, lock, ip);
+		return 0;
+	}
 
 	/*
 	 * Check whether the lock exists in the current stack
 	 * of held locks:
 	 */
 	hlock = find_held_lock(curr, lock, depth, &i);
-	if (!hlock)
-		return print_unlock_imbalance_bug(curr, lock, ip);
+	if (!hlock) {
+		print_unlock_imbalance_bug(curr, lock, ip);
+		return 0;
+	}
 
 	if (hlock->instance == lock)
 		lock_release_holdtime(hlock);
@@ -4295,14 +4302,14 @@ void lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
 EXPORT_SYMBOL_GPL(lock_unpin_lock);
 
 #ifdef CONFIG_LOCK_STAT
-static int
-print_lock_contention_bug(struct task_struct *curr, struct lockdep_map *lock,
-			   unsigned long ip)
+static void print_lock_contention_bug(struct task_struct *curr,
+				      struct lockdep_map *lock,
+				      unsigned long ip)
 {
 	if (!debug_locks_off())
-		return 0;
+		return;
 	if (debug_locks_silent)
-		return 0;
+		return;
 
 	pr_warn("\n");
 	pr_warn("=================================\n");
@@ -4320,8 +4327,6 @@ void lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
 
 	pr_warn("\nstack backtrace:\n");
 	dump_stack();
-
-	return 0;
 }
 
 static void
-- 
1.8.3.1

[PATCH 02/28] locking/lockdep: Add description and explanation in lockdep design doc

[Yuyang Du]

More words are added to lockdep design document regarding key concepts,
which should help people without lockdep experience read and understand
lockdep reports.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 Documentation/locking/lockdep-design.txt | 74 ++++++++++++++++++++++++--------
 1 file changed, 56 insertions(+), 18 deletions(-)

diff --git a/Documentation/locking/lockdep-design.txt b/Documentation/locking/lockdep-design.txt
index 39fae14..d5062fc 100644
--- a/Documentation/locking/lockdep-design.txt
+++ b/Documentation/locking/lockdep-design.txt
@@ -15,34 +15,43 @@ tens of thousands of) instantiations. For example a lock in the inode
 struct is one class, while each inode has its own instantiation of that
 lock class.
 
-The validator tracks the 'state' of lock-classes, and it tracks
-dependencies between different lock-classes. The validator maintains a
-rolling proof that the state and the dependencies are correct.
-
-Unlike an lock instantiation, the lock-class itself never goes away: when
-a lock-class is used for the first time after bootup it gets registered,
-and all subsequent uses of that lock-class will be attached to this
-lock-class.
+The validator tracks the 'usage state' of lock-classes, and it tracks
+the dependencies between different lock-classes. A dependency can be
+understood as lock order, where L1 -> L2 suggests L2 is attempted to be
+acquired with L1 held. From lockdep's perspective, the two locks (L1 and
+L2) are not necessarily related, but just means that order ever
+happened. The validator maintains a continuing effort to prove that the
+lock usages and their dependencies are correct or the validator will
+shoot a splat if they are incorrect.
+
+Unlike a lock instance, a lock-class itself never goes away: when a
+lock-class's instance is used for the first time after bootup the class gets
+registered, and all (subsequent) instances of that lock-class will be mapped
+to the lock-class.
 
 State
 -----
 
-The validator tracks lock-class usage history into 4 * nSTATEs + 1 separate
-state bits:
+The validator tracks lock-class usage history and divides the usage into
+(4 usages * n STATEs + 1) categories:
 
+where the 4 usages can be:
 - 'ever held in STATE context'
 - 'ever held as readlock in STATE context'
 - 'ever held with STATE enabled'
 - 'ever held as readlock with STATE enabled'
 
-Where STATE can be either one of (kernel/locking/lockdep_states.h)
- - hardirq
- - softirq
+where the n STATEs are coded in kernel/locking/lockdep_states.h and as of
+now they include:
+- hardirq
+- softirq
 
+where the last 1 category is:
 - 'ever used'                                       [ == !unused        ]
 
-When locking rules are violated, these state bits are presented in the
-locking error messages, inside curlies. A contrived example:
+When locking rules are violated, these usage bits are presented in the
+locking error messages, inside curlies, with a total of 2 * n STATEs bits.
+A contrived example:
 
    modprobe/2287 is trying to acquire lock:
     (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
@@ -51,15 +60,44 @@ locking error messages, inside curlies. A contrived example:
     (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
 
 
-The bit position indicates STATE, STATE-read, for each of the states listed
-above, and the character displayed in each indicates:
+For a given lock, the bit positions from left to right indicate the usage
+of the lock and readlock (if exists), for each of the n STATEs listed
+above respectively, and the character displayed at each bit position
+indicates:
 
    '.'  acquired while irqs disabled and not in irq context
    '-'  acquired in irq context
    '+'  acquired with irqs enabled
    '?'  acquired in irq context with irqs enabled.
 
-Unused mutexes cannot be part of the cause of an error.
+The bits are illustrated with an example:
+
+    (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
+                         ||||
+                         ||| \-> softirq disabled and not in softirq context
+                         || \--> acquired in softirq context
+                         | \---> hardirq disabled and not in hardirq context
+                          \----> acquired in hardirq context
+
+
+For a given STATE, whether the lock is ever acquired in that STATE
+context and whether that STATE is enabled yields four possible cases as
+shown in the table below. The bit character is able to indicate which
+exact case is for the lock as of the reporting time.
+
+   -------------------------------------------
+  |              | irq enabled | irq disabled |
+  |-------------------------------------------|
+  | ever in irq  |      ?      |       -      |
+  |-------------------------------------------|
+  | never in irq |      +      |       .      |
+   -------------------------------------------
+
+The character '-' suggests irq is disabled because if otherwise the
+charactor '?' would have been shown instead. Similar deduction can be
+applied for '+' too.
+
+Unused locks (e.g., mutexes) cannot be part of the cause of an error.
 
 
 Single-lock state rules:
-- 
1.8.3.1

Re: [PATCH 02/28] locking/lockdep: Add description and explanation in lockdep design doc

[Peter Zijlstra]

On Wed, Apr 24, 2019 at 06:19:08PM +0800, Yuyang Du wrote:
> +Unlike a lock instance, a lock-class itself never goes away: when a
> +lock-class's instance is used for the first time after bootup the class gets
> +registered, and all (subsequent) instances of that lock-class will be mapped
> +to the lock-class.

That's not entirely accurate anymore. Bart van Assche recently added
lockdep_{,un}register_key().

Re: [PATCH 02/28] locking/lockdep: Add description and explanation in lockdep design doc

[Yuyang Du]

Thank you very much for review.

You mean class can go away? Before Bart's addition, it can go away.
Right? I think maybe the original point of "never go away" in that
context did not intend to talk about a class's real disappearance.

Anyway, the points should be made comprehensive. You want me to resend
the patch or you modify it?

On Thu, 25 Apr 2019 at 22:01, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Wed, Apr 24, 2019 at 06:19:08PM +0800, Yuyang Du wrote:
> > +Unlike a lock instance, a lock-class itself never goes away: when a
> > +lock-class's instance is used for the first time after bootup the class gets
> > +registered, and all (subsequent) instances of that lock-class will be mapped
> > +to the lock-class.
>
> That's not entirely accurate anymore. Bart van Assche recently added
> lockdep_{,un}register_key().

[PATCH 03/28] locking/lockdep: Adjust lock usage bit character checks

[Yuyang Du]

The lock usage bit characters are defined and determined with tricks.
Add some explanation to make it a bit clearer, then adjust the logic to
check the usage, which optimizes the code a bit.

No functional change.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 21 ++++++++++++++++-----
 1 file changed, 16 insertions(+), 5 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 4bf396b..ba0080a 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -499,15 +499,26 @@ static inline unsigned long lock_flag(enum lock_usage_bit bit)
 
 static char get_usage_char(struct lock_class *class, enum lock_usage_bit bit)
 {
+	/*
+	 * The usage character defaults to '.' (i.e., irqs disabled and not in
+	 * irq context), which is the safest usage category.
+	 */
 	char c = '.';
 
-	if (class->usage_mask & lock_flag(bit + LOCK_USAGE_DIR_MASK))
+	/*
+	 * The order of the following usage checks matters, which will
+	 * result in the outcome character as follows:
+	 *
+	 * - '+': irq is enabled and not in irq context
+	 * - '-': in irq context and irq is disabled
+	 * - '?': in irq context and irq is enabled
+	 */
+	if (class->usage_mask & lock_flag(bit + LOCK_USAGE_DIR_MASK)) {
 		c = '+';
-	if (class->usage_mask & lock_flag(bit)) {
-		c = '-';
-		if (class->usage_mask & lock_flag(bit + LOCK_USAGE_DIR_MASK))
+		if (class->usage_mask & lock_flag(bit))
 			c = '?';
-	}
+	} else if (class->usage_mask & lock_flag(bit))
+		c = '-';
 
 	return c;
 }
-- 
1.8.3.1

[PATCH 04/28] locking/lockdep: Remove useless conditional macro

[Yuyang Du]

Since #defined(CONFIG_PROVE_LOCKING) is used in the scope of #ifdef
CONFIG_PROVE_LOCKING, it can be removed.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index ba0080a..2cc2a15 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1669,7 +1669,7 @@ unsigned long lockdep_count_backward_deps(struct lock_class *class)
 	return result;
 }
 
-#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
+#if defined(CONFIG_TRACE_IRQFLAGS)
 /*
  * Forwards and backwards subgraph searching, for the purposes of
  * proving that two subgraphs can be connected by a new dependency
@@ -2050,7 +2050,7 @@ static inline void inc_chains(void)
 	nr_process_chains++;
 }
 
-#endif
+#endif /* CONFIG_TRACE_IRQFLAGS */
 
 static void
 print_deadlock_scenario(struct held_lock *nxt, struct held_lock *prv)
@@ -2723,7 +2723,7 @@ static inline int validate_chain(struct task_struct *curr,
 static void print_lock_trace(struct lock_trace *trace, unsigned int spaces)
 {
 }
-#endif
+#endif /* CONFIG_PROVE_LOCKING */
 
 /*
  * We are building curr_chain_key incrementally, so double-check
-- 
1.8.3.1

[PATCH 05/28] locking/lockdep: Print the right depth for chain key colission

[Yuyang Du]

Since chains are separated by irq context, so when printing a chain the
depth should be consistent with it.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 2cc2a15..e001dfb 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2409,10 +2409,11 @@ static u64 print_chain_key_iteration(int class_idx, u64 chain_key)
 	struct held_lock *hlock;
 	u64 chain_key = 0;
 	int depth = curr->lockdep_depth;
-	int i;
+	int i = get_first_held_lock(curr, hlock_next);
 
-	printk("depth: %u\n", depth + 1);
-	for (i = get_first_held_lock(curr, hlock_next); i < depth; i++) {
+	printk("depth: %u (irq_context %u)\n", depth - i + 1,
+		hlock_next->irq_context);
+	for (; i < depth; i++) {
 		hlock = curr->held_locks + i;
 		chain_key = print_chain_key_iteration(hlock->class_idx, chain_key);
 
-- 
1.8.3.1

[PATCH 06/28] locking/lockdep: Update obsolete struct field description

[Yuyang Du]

The lock_chain struct definition has outdated comment, update it and add
struct member description.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 include/linux/lockdep.h | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 6e2377e..851d44f 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -203,11 +203,17 @@ struct lock_list {
 	struct lock_list		*parent;
 };
 
-/*
- * We record lock dependency chains, so that we can cache them:
+/**
+ * struct lock_chain - lock dependency chain record
+ *
+ * @irq_context: the same as irq_context in held_lock below
+ * @depth:       the number of held locks in this chain
+ * @base:        the index in chain_hlocks for this chain
+ * @entry:       the collided lock chains in lock_chain hash list
+ * @chain_key:   the hash key of this lock_chain
  */
 struct lock_chain {
-	/* see BUILD_BUG_ON()s in lookup_chain_cache() */
+	/* see BUILD_BUG_ON()s in add_chain_cache() */
 	unsigned int			irq_context :  2,
 					depth       :  6,
 					base	    : 24;
-- 
1.8.3.1

[PATCH 07/28] locking/lockdep: Use lockdep_init_task for task initiation consistently

[Yuyang Du]

Despite that there is a lockdep_init_task() which does nothing, lockdep
initiates tasks by assigning lockdep fields and does so inconsistently. Fix
this by using lockdep_init_task().

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 include/linux/lockdep.h  |  7 ++++++-
 init/init_task.c         |  2 ++
 kernel/fork.c            |  3 ---
 kernel/locking/lockdep.c | 11 ++++++++---
 4 files changed, 16 insertions(+), 7 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 851d44f..751a2cc 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -287,6 +287,8 @@ struct held_lock {
 extern asmlinkage void lockdep_sys_exit(void);
 extern void lockdep_set_selftest_task(struct task_struct *task);
 
+extern inline void lockdep_init_task(struct task_struct *task);
+
 extern void lockdep_off(void);
 extern void lockdep_on(void);
 
@@ -411,6 +413,10 @@ static inline void lock_set_subclass(struct lockdep_map *lock,
 
 #else /* !CONFIG_LOCKDEP */
 
+static inline void lockdep_init_task(struct task_struct *task)
+{
+}
+
 static inline void lockdep_off(void)
 {
 }
@@ -503,7 +509,6 @@ enum xhlock_context_t {
 	{ .name = (_name), .key = (void *)(_key), }
 
 static inline void lockdep_invariant_state(bool force) {}
-static inline void lockdep_init_task(struct task_struct *task) {}
 static inline void lockdep_free_task(struct task_struct *task) {}
 
 #ifdef CONFIG_LOCK_STAT
diff --git a/init/init_task.c b/init/init_task.c
index c70ef65..1b15cb9 100644
--- a/init/init_task.c
+++ b/init/init_task.c
@@ -166,6 +166,8 @@ struct task_struct init_task
 	.softirqs_enabled = 1,
 #endif
 #ifdef CONFIG_LOCKDEP
+	.lockdep_depth = 0, /* no locks held yet */
+	.curr_chain_key = 0,
 	.lockdep_recursion = 0,
 #endif
 #ifdef CONFIG_FUNCTION_GRAPH_TRACER
diff --git a/kernel/fork.c b/kernel/fork.c
index 9dcd18a..8ec9e78 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1868,9 +1868,6 @@ static __latent_entropy struct task_struct *copy_process(
 	p->pagefault_disabled = 0;
 
 #ifdef CONFIG_LOCKDEP
-	p->lockdep_depth = 0; /* no locks held yet */
-	p->curr_chain_key = 0;
-	p->lockdep_recursion = 0;
 	lockdep_init_task(p);
 #endif
 
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index e001dfb..4ce0e39 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -358,6 +358,13 @@ static inline u64 iterate_chain_key(u64 key, u32 idx)
 	return k0 | (u64)k1 << 32;
 }
 
+inline void lockdep_init_task(struct task_struct *task)
+{
+	task->lockdep_depth = 0; /* no locks held yet */
+	task->curr_chain_key = 0;
+	task->lockdep_recursion = 0;
+}
+
 void lockdep_off(void)
 {
 	current->lockdep_recursion++;
@@ -4483,9 +4490,7 @@ void lockdep_reset(void)
 	int i;
 
 	raw_local_irq_save(flags);
-	current->curr_chain_key = 0;
-	current->lockdep_depth = 0;
-	current->lockdep_recursion = 0;
+	lockdep_init_task(current);
 	memset(current->held_locks, 0, MAX_LOCK_DEPTH*sizeof(struct held_lock));
 	nr_hardirq_chains = 0;
 	nr_softirq_chains = 0;
-- 
1.8.3.1

[PATCH 08/28] locking/lockdep: Define INITIAL_CHAIN_KEY for chain keys to start with

[Yuyang Du]

Chain keys are computed using Jenkins hash function, which needs an initial
hash to start with. Dedicate a macro to make this clear and configurable. A
later patch changes this initial chain key.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 include/linux/lockdep.h  |  1 +
 init/init_task.c         |  2 +-
 kernel/locking/lockdep.c | 18 +++++++++---------
 3 files changed, 11 insertions(+), 10 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 751a2cc..bb47d7c 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -229,6 +229,7 @@ struct lock_chain {
  * bitfield and hitting the BUG in hlock_class().
  */
 #define MAX_LOCKDEP_KEYS		((1UL << MAX_LOCKDEP_KEYS_BITS) - 1)
+#define INITIAL_CHAIN_KEY		0
 
 struct held_lock {
 	/*
diff --git a/init/init_task.c b/init/init_task.c
index 1b15cb9..afa6ad7 100644
--- a/init/init_task.c
+++ b/init/init_task.c
@@ -167,7 +167,7 @@ struct task_struct init_task
 #endif
 #ifdef CONFIG_LOCKDEP
 	.lockdep_depth = 0, /* no locks held yet */
-	.curr_chain_key = 0,
+	.curr_chain_key = INITIAL_CHAIN_KEY,
 	.lockdep_recursion = 0,
 #endif
 #ifdef CONFIG_FUNCTION_GRAPH_TRACER
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 4ce0e39..3055ea7 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -361,7 +361,7 @@ static inline u64 iterate_chain_key(u64 key, u32 idx)
 inline void lockdep_init_task(struct task_struct *task)
 {
 	task->lockdep_depth = 0; /* no locks held yet */
-	task->curr_chain_key = 0;
+	task->curr_chain_key = INITIAL_CHAIN_KEY;
 	task->lockdep_recursion = 0;
 }
 
@@ -852,7 +852,7 @@ static bool class_lock_list_valid(struct lock_class *c, struct list_head *h)
 static bool check_lock_chain_key(struct lock_chain *chain)
 {
 #ifdef CONFIG_PROVE_LOCKING
-	u64 chain_key = 0;
+	u64 chain_key = INITIAL_CHAIN_KEY;
 	int i;
 
 	for (i = chain->base; i < chain->base + chain->depth; i++)
@@ -2414,7 +2414,7 @@ static u64 print_chain_key_iteration(int class_idx, u64 chain_key)
 print_chain_keys_held_locks(struct task_struct *curr, struct held_lock *hlock_next)
 {
 	struct held_lock *hlock;
-	u64 chain_key = 0;
+	u64 chain_key = INITIAL_CHAIN_KEY;
 	int depth = curr->lockdep_depth;
 	int i = get_first_held_lock(curr, hlock_next);
 
@@ -2434,7 +2434,7 @@ static u64 print_chain_key_iteration(int class_idx, u64 chain_key)
 static void print_chain_keys_chain(struct lock_chain *chain)
 {
 	int i;
-	u64 chain_key = 0;
+	u64 chain_key = INITIAL_CHAIN_KEY;
 	int class_id;
 
 	printk("depth: %u\n", chain->depth);
@@ -2742,7 +2742,7 @@ static void check_chain_key(struct task_struct *curr)
 #ifdef CONFIG_DEBUG_LOCKDEP
 	struct held_lock *hlock, *prev_hlock = NULL;
 	unsigned int i;
-	u64 chain_key = 0;
+	u64 chain_key = INITIAL_CHAIN_KEY;
 
 	for (i = 0; i < curr->lockdep_depth; i++) {
 		hlock = curr->held_locks + i;
@@ -2766,7 +2766,7 @@ static void check_chain_key(struct task_struct *curr)
 
 		if (prev_hlock && (prev_hlock->irq_context !=
 							hlock->irq_context))
-			chain_key = 0;
+			chain_key = INITIAL_CHAIN_KEY;
 		chain_key = iterate_chain_key(chain_key, hlock->class_idx);
 		prev_hlock = hlock;
 	}
@@ -3681,14 +3681,14 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 		/*
 		 * How can we have a chain hash when we ain't got no keys?!
 		 */
-		if (DEBUG_LOCKS_WARN_ON(chain_key != 0))
+		if (DEBUG_LOCKS_WARN_ON(chain_key != INITIAL_CHAIN_KEY))
 			return 0;
 		chain_head = 1;
 	}
 
 	hlock->prev_chain_key = chain_key;
 	if (separate_irq_context(curr, hlock)) {
-		chain_key = 0;
+		chain_key = INITIAL_CHAIN_KEY;
 		chain_head = 1;
 	}
 	chain_key = iterate_chain_key(chain_key, class_idx);
@@ -4530,7 +4530,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
 	return;
 
 recalc:
-	chain_key = 0;
+	chain_key = INITIAL_CHAIN_KEY;
 	for (i = chain->base; i < chain->base + chain->depth; i++)
 		chain_key = iterate_chain_key(chain_key, chain_hlocks[i] + 1);
 	if (chain->depth && chain->chain_key == chain_key)
-- 
1.8.3.1

[PATCH 09/28] locking/lockdep: Change the range of class_idx in held_lock struct

[Yuyang Du]

held_lock->class_idx is used to point to the class of the held lock. The
index is shifted by 1 to make index 0 mean no class, which results in class
index shifting back and forth but is not worth doing so.

The reason is: (1) there will be no "no-class" held_lock to begin with, and
(2) index 0 seems to be used for error checking, but if something wrong
indeed happended, the index can't be counted on to distinguish it as that
something won't set the class_idx to 0 on purpose to tell us it is wrong.

Therefore, change the index to start from 0. This saves a lot of
back-and-forth shifts and save a slot back to lock_classes.

Since index 0 is now used for lock class, we change the initial chain key to
-1 to avoid key collision, which is due to the fact that __jhash_mix(0, 0, 0) = 0.
Actually, the initial chain key can be any arbitrary value other than 0.

In addition, we maintain a bitmap to keep track of the used lock classes,
and we check the validity of the held lock against that bitmap.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 include/linux/lockdep.h  | 14 ++++++------
 kernel/locking/lockdep.c | 59 ++++++++++++++++++++++++++++++++----------------
 2 files changed, 46 insertions(+), 27 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index bb47d7c..7c2fefa 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -223,13 +223,8 @@ struct lock_chain {
 };
 
 #define MAX_LOCKDEP_KEYS_BITS		13
-/*
- * Subtract one because we offset hlock->class_idx by 1 in order
- * to make 0 mean no class. This avoids overflowing the class_idx
- * bitfield and hitting the BUG in hlock_class().
- */
-#define MAX_LOCKDEP_KEYS		((1UL << MAX_LOCKDEP_KEYS_BITS) - 1)
-#define INITIAL_CHAIN_KEY		0
+#define MAX_LOCKDEP_KEYS		(1UL << MAX_LOCKDEP_KEYS_BITS)
+#define INITIAL_CHAIN_KEY		-1
 
 struct held_lock {
 	/*
@@ -254,6 +249,11 @@ struct held_lock {
 	u64 				waittime_stamp;
 	u64				holdtime_stamp;
 #endif
+	/*
+	 * class_idx is zero-indexed; it points to the element in
+	 * lock_classes this held lock instance belongs to. class_idx is in
+	 * the range from 0 to (MAX_LOCKDEP_KEYS-1) inclusive.
+	 */
 	unsigned int			class_idx:MAX_LOCKDEP_KEYS_BITS;
 	/*
 	 * The lock-stack is unified in that the lock chains of interrupt
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 3055ea7..3a2b0da 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -150,17 +150,28 @@ static inline int debug_locks_off_graph_unlock(void)
 static
 #endif
 struct lock_class lock_classes[MAX_LOCKDEP_KEYS];
+static DECLARE_BITMAP(lock_classes_in_use, MAX_LOCKDEP_KEYS);
 
 static inline struct lock_class *hlock_class(struct held_lock *hlock)
 {
-	if (!hlock->class_idx) {
+	unsigned int class_idx = hlock->class_idx;
+
+	/* Don't re-read hlock->class_idx, can't use READ_ONCE() on bitfield */
+	barrier();
+
+	if (!test_bit(class_idx, lock_classes_in_use)) {
 		/*
 		 * Someone passed in garbage, we give up.
 		 */
 		DEBUG_LOCKS_WARN_ON(1);
 		return NULL;
 	}
-	return lock_classes + hlock->class_idx - 1;
+
+	/*
+	 * At this point, if the passed hlock->class_idx is still garbage,
+	 * we just have to live with it
+	 */
+	return lock_classes + class_idx;
 }
 
 #ifdef CONFIG_LOCK_STAT
@@ -589,19 +600,22 @@ static void print_lock(struct held_lock *hlock)
 	/*
 	 * We can be called locklessly through debug_show_all_locks() so be
 	 * extra careful, the hlock might have been released and cleared.
+	 *
+	 * If this indeed happens, lets pretend it does not hurt to continue
+	 * to print the lock unless the hlock class_idx does not point to a
+	 * registered class. The rationale here is: since we don't attempt
+	 * to distinguish whether we are in this situation, if it just
+	 * happened we can't count on class_idx to tell either.
 	 */
-	unsigned int class_idx = hlock->class_idx;
+	struct lock_class *lock = hlock_class(hlock);
 
-	/* Don't re-read hlock->class_idx, can't use READ_ONCE() on bitfields: */
-	barrier();
-
-	if (!class_idx || (class_idx - 1) >= MAX_LOCKDEP_KEYS) {
+	if (!lock) {
 		printk(KERN_CONT "<RELEASED>\n");
 		return;
 	}
 
 	printk(KERN_CONT "%p", hlock->instance);
-	print_lock_name(lock_classes + class_idx - 1);
+	print_lock_name(lock);
 	printk(KERN_CONT ", at: %pS\n", (void *)hlock->acquire_ip);
 }
 
@@ -856,7 +870,7 @@ static bool check_lock_chain_key(struct lock_chain *chain)
 	int i;
 
 	for (i = chain->base; i < chain->base + chain->depth; i++)
-		chain_key = iterate_chain_key(chain_key, chain_hlocks[i] + 1);
+		chain_key = iterate_chain_key(chain_key, chain_hlocks[i]);
 	/*
 	 * The 'unsigned long long' casts avoid that a compiler warning
 	 * is reported when building tools/lib/lockdep.
@@ -1131,6 +1145,7 @@ static bool is_dynamic_key(const struct lock_class_key *key)
 		return NULL;
 	}
 	nr_lock_classes++;
+	__set_bit(class - lock_classes, lock_classes_in_use);
 	debug_atomic_inc(nr_unused_locks);
 	class->key = key;
 	class->name = lock->name;
@@ -2440,7 +2455,7 @@ static void print_chain_keys_chain(struct lock_chain *chain)
 	printk("depth: %u\n", chain->depth);
 	for (i = 0; i < chain->depth; i++) {
 		class_id = chain_hlocks[chain->base + i];
-		chain_key = print_chain_key_iteration(class_id + 1, chain_key);
+		chain_key = print_chain_key_iteration(class_id, chain_key);
 
 		print_lock_name(lock_classes + class_id);
 		printk("\n");
@@ -2491,7 +2506,7 @@ static int check_no_collision(struct task_struct *curr,
 	}
 
 	for (j = 0; j < chain->depth - 1; j++, i++) {
-		id = curr->held_locks[i].class_idx - 1;
+		id = curr->held_locks[i].class_idx;
 
 		if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] != id)) {
 			print_collision(curr, hlock, chain);
@@ -2574,7 +2589,7 @@ static inline int add_chain_cache(struct task_struct *curr,
 	if (likely(nr_chain_hlocks + chain->depth <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
 		chain->base = nr_chain_hlocks;
 		for (j = 0; j < chain->depth - 1; j++, i++) {
-			int lock_id = curr->held_locks[i].class_idx - 1;
+			int lock_id = curr->held_locks[i].class_idx;
 			chain_hlocks[chain->base + j] = lock_id;
 		}
 		chain_hlocks[chain->base + j] = class - lock_classes;
@@ -2758,10 +2773,12 @@ static void check_chain_key(struct task_struct *curr)
 				(unsigned long long)hlock->prev_chain_key);
 			return;
 		}
+
 		/*
-		 * Whoops ran out of static storage again?
+		 * hlock->class_idx can't go beyond MAX_LOCKDEP_KEYS, but is
+		 * it registered lock class index?
 		 */
-		if (DEBUG_LOCKS_WARN_ON(hlock->class_idx > MAX_LOCKDEP_KEYS))
+		if (DEBUG_LOCKS_WARN_ON(!test_bit(hlock->class_idx, lock_classes_in_use)))
 			return;
 
 		if (prev_hlock && (prev_hlock->irq_context !=
@@ -3609,7 +3626,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	if (DEBUG_LOCKS_WARN_ON(depth >= MAX_LOCK_DEPTH))
 		return 0;
 
-	class_idx = class - lock_classes + 1;
+	class_idx = class - lock_classes;
 
 	if (depth) {
 		hlock = curr->held_locks + depth - 1;
@@ -3671,9 +3688,9 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	 * the hash, not class->key.
 	 */
 	/*
-	 * Whoops, we did it again.. ran straight out of our static allocation.
+	 * Whoops, we did it again.. class_idx is invalid.
 	 */
-	if (DEBUG_LOCKS_WARN_ON(class_idx > MAX_LOCKDEP_KEYS))
+	if (DEBUG_LOCKS_WARN_ON(!test_bit(class_idx, lock_classes_in_use)))
 		return 0;
 
 	chain_key = curr->curr_chain_key;
@@ -3788,7 +3805,7 @@ static int match_held_lock(const struct held_lock *hlock,
 		if (DEBUG_LOCKS_WARN_ON(!hlock->nest_lock))
 			return 0;
 
-		if (hlock->class_idx == class - lock_classes + 1)
+		if (hlock->class_idx == class - lock_classes)
 			return 1;
 	}
 
@@ -3882,7 +3899,7 @@ static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
 
 	lockdep_init_map(lock, name, key, 0);
 	class = register_lock_class(lock, subclass, 0);
-	hlock->class_idx = class - lock_classes + 1;
+	hlock->class_idx = class - lock_classes;
 
 	curr->lockdep_depth = i;
 	curr->curr_chain_key = hlock->prev_chain_key;
@@ -4532,7 +4549,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
 recalc:
 	chain_key = INITIAL_CHAIN_KEY;
 	for (i = chain->base; i < chain->base + chain->depth; i++)
-		chain_key = iterate_chain_key(chain_key, chain_hlocks[i] + 1);
+		chain_key = iterate_chain_key(chain_key, chain_hlocks[i]);
 	if (chain->depth && chain->chain_key == chain_key)
 		return;
 	/* Overwrite the chain key for concurrent RCU readers. */
@@ -4606,6 +4623,7 @@ static void zap_class(struct pending_free *pf, struct lock_class *class)
 		WRITE_ONCE(class->key, NULL);
 		WRITE_ONCE(class->name, NULL);
 		nr_lock_classes--;
+		__clear_bit(class - lock_classes, lock_classes_in_use);
 	} else {
 		WARN_ONCE(true, "%s() failed for class %s\n", __func__,
 			  class->name);
@@ -4951,6 +4969,7 @@ void __init lockdep_init(void)
 
 	printk(" memory used by lock dependency info: %zu kB\n",
 	       (sizeof(lock_classes) +
+		sizeof(lock_classes_in_use) +
 		sizeof(classhash_table) +
 		sizeof(list_entries) +
 		sizeof(list_entries_in_use) +
-- 
1.8.3.1

[PATCH 10/28] locking/lockdep: Remove unused argument in validate_chain() and check_deadlock()

[Yuyang Du]

The lockdep_map argument in them is not used, remove it.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
Reviewed-by: Bart Van Assche <bvanassche@acm.org>
---
 kernel/locking/lockdep.c | 17 ++++++++---------
 1 file changed, 8 insertions(+), 9 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 3a2b0da..ec4043b 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2128,8 +2128,7 @@ static inline void inc_chains(void)
  * Returns: 0 on deadlock detected, 1 on OK, 2 on recursive read
  */
 static int
-check_deadlock(struct task_struct *curr, struct held_lock *next,
-	       struct lockdep_map *next_instance, int read)
+check_deadlock(struct task_struct *curr, struct held_lock *next, int read)
 {
 	struct held_lock *prev;
 	struct held_lock *nest = NULL;
@@ -2279,7 +2278,6 @@ static inline void inc_chains(void)
 		return 0;
 	}
 
-
 	if (!save_trace(&trace))
 		return 0;
 
@@ -2679,8 +2677,9 @@ static inline int lookup_chain_cache_add(struct task_struct *curr,
 	return 1;
 }
 
-static int validate_chain(struct task_struct *curr, struct lockdep_map *lock,
-		struct held_lock *hlock, int chain_head, u64 chain_key)
+static int validate_chain(struct task_struct *curr,
+			  struct held_lock *hlock,
+			  int chain_head, u64 chain_key)
 {
 	/*
 	 * Trylock needs to maintain the stack of held locks, but it
@@ -2706,7 +2705,7 @@ static int validate_chain(struct task_struct *curr, struct lockdep_map *lock,
 		 * any of these scenarios could lead to a deadlock. If
 		 * All validations
 		 */
-		int ret = check_deadlock(curr, hlock, lock, hlock->read);
+		int ret = check_deadlock(curr, hlock, hlock->read);
 
 		if (!ret)
 			return 0;
@@ -2737,8 +2736,8 @@ static int validate_chain(struct task_struct *curr, struct lockdep_map *lock,
 }
 #else
 static inline int validate_chain(struct task_struct *curr,
-	       	struct lockdep_map *lock, struct held_lock *hlock,
-		int chain_head, u64 chain_key)
+				 struct held_lock *hlock,
+				 int chain_head, u64 chain_key)
 {
 	return 1;
 }
@@ -3720,7 +3719,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 		WARN_ON_ONCE(!hlock_class(hlock)->key);
 	}
 
-	if (!validate_chain(curr, lock, hlock, chain_head, chain_key))
+	if (!validate_chain(curr, hlock, chain_head, chain_key))
 		return 0;
 
 	curr->curr_chain_key = chain_key;
-- 
1.8.3.1

[PATCH 11/28] locking/lockdep: Update comment

[Yuyang Du]

An out-of-nowhere comment is removed. While at it, add more explanatory
comments. Such a trivial patch!

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index ec4043b..0543872 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2700,10 +2700,16 @@ static int validate_chain(struct task_struct *curr,
 		 * - is softirq-safe, if this lock is hardirq-unsafe
 		 *
 		 * And check whether the new lock's dependency graph
-		 * could lead back to the previous lock.
+		 * could lead back to the previous lock:
 		 *
-		 * any of these scenarios could lead to a deadlock. If
-		 * All validations
+		 * - within the current held-lock stack
+		 * - across our accumulated lock dependency records
+		 *
+		 * any of these scenarios could lead to a deadlock.
+		 */
+		/*
+		 * The simple case: does the current hold the same lock
+		 * already?
 		 */
 		int ret = check_deadlock(curr, hlock, hlock->read);
 
-- 
1.8.3.1

[PATCH 12/28] locking/lockdep: Change type of the element field in circular_queue

[Yuyang Du]

The element field is an array in struct circular_queue to keep track of locks
in the search. Making it the same type as the locks avoids type cast. Also
fix a typo and elaborate the comment above struct circular_queue.

No functional change.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
Reviewed-by: Bart Van Assche <bvanassche@acm.org>
---
 kernel/locking/lockdep.c | 23 +++++++++++++----------
 1 file changed, 13 insertions(+), 10 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 0543872..683aaf60 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1257,13 +1257,16 @@ static int add_lock_to_list(struct lock_class *this,
 #define CQ_MASK				(MAX_CIRCULAR_QUEUE_SIZE-1)
 
 /*
- * The circular_queue and helpers is used to implement the
- * breadth-first search(BFS)algorithem, by which we can build
- * the shortest path from the next lock to be acquired to the
- * previous held lock if there is a circular between them.
+ * The circular_queue and helpers are used to implement the graph
+ * breadth-first search (BFS) algorithm, by which we can determine whether
+ * there is a path from the next lock to be acquired to a previous held
+ * lock, which indicates that adding the <prev> -> <next> lock dependency
+ * produces a circle in the lock dependency graph. Breadth-first search
+ * instead of depth-first search is used for finding the shortest circular
+ * path.
  */
 struct circular_queue {
-	unsigned long element[MAX_CIRCULAR_QUEUE_SIZE];
+	struct lock_list *element[MAX_CIRCULAR_QUEUE_SIZE];
 	unsigned int  front, rear;
 };
 
@@ -1289,7 +1292,7 @@ static inline int __cq_full(struct circular_queue *cq)
 	return ((cq->rear + 1) & CQ_MASK) == cq->front;
 }
 
-static inline int __cq_enqueue(struct circular_queue *cq, unsigned long elem)
+static inline int __cq_enqueue(struct circular_queue *cq, struct lock_list *elem)
 {
 	if (__cq_full(cq))
 		return -1;
@@ -1299,7 +1302,7 @@ static inline int __cq_enqueue(struct circular_queue *cq, unsigned long elem)
 	return 0;
 }
 
-static inline int __cq_dequeue(struct circular_queue *cq, unsigned long *elem)
+static inline int __cq_dequeue(struct circular_queue *cq, struct lock_list **elem)
 {
 	if (__cq_empty(cq))
 		return -1;
@@ -1377,12 +1380,12 @@ static int __bfs(struct lock_list *source_entry,
 		goto exit;
 
 	__cq_init(cq);
-	__cq_enqueue(cq, (unsigned long)source_entry);
+	__cq_enqueue(cq, source_entry);
 
 	while (!__cq_empty(cq)) {
 		struct lock_list *lock;
 
-		__cq_dequeue(cq, (unsigned long *)&lock);
+		__cq_dequeue(cq, &lock);
 
 		if (!lock->class) {
 			ret = -2;
@@ -1406,7 +1409,7 @@ static int __bfs(struct lock_list *source_entry,
 					goto exit;
 				}
 
-				if (__cq_enqueue(cq, (unsigned long)entry)) {
+				if (__cq_enqueue(cq, entry)) {
 					ret = -1;
 					goto exit;
 				}
-- 
1.8.3.1

[PATCH 13/28] locking/lockdep: Change the return type of __cq_dequeue()

[Yuyang Du]

With the change, we can slightly adjust the code to iterate the queue in BFS
search, which simplifies the code. No functional change.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 21 +++++++++++++--------
 1 file changed, 13 insertions(+), 8 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 683aaf60..225eeeb 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1302,14 +1302,21 @@ static inline int __cq_enqueue(struct circular_queue *cq, struct lock_list *elem
 	return 0;
 }
 
-static inline int __cq_dequeue(struct circular_queue *cq, struct lock_list **elem)
+/*
+ * Dequeue an element from the circular_queue, return the lock if the queue
+ * is not empty, or NULL if otherwise
+ */
+static inline struct lock_list * __cq_dequeue(struct circular_queue *cq)
 {
+	struct lock_list * lock;
+
 	if (__cq_empty(cq))
-		return -1;
+		return NULL;
 
-	*elem = cq->element[cq->front];
+	lock = cq->element[cq->front];
 	cq->front = (cq->front + 1) & CQ_MASK;
-	return 0;
+
+	return lock;
 }
 
 static inline unsigned int  __cq_get_elem_count(struct circular_queue *cq)
@@ -1361,6 +1368,7 @@ static int __bfs(struct lock_list *source_entry,
 		 int forward)
 {
 	struct lock_list *entry;
+	struct lock_list *lock;
 	struct list_head *head;
 	struct circular_queue *cq = &lock_cq;
 	int ret = 1;
@@ -1382,10 +1390,7 @@ static int __bfs(struct lock_list *source_entry,
 	__cq_init(cq);
 	__cq_enqueue(cq, source_entry);
 
-	while (!__cq_empty(cq)) {
-		struct lock_list *lock;
-
-		__cq_dequeue(cq, &lock);
+	while ((lock = __cq_dequeue(cq))) {
 
 		if (!lock->class) {
 			ret = -2;
-- 
1.8.3.1

[PATCH 14/28] locking/lockdep: Avoid constant checks in __bfs by using offset reference

[Yuyang Du]

In search of a dependency in the lock graph, there is contant checks for
forward or backward search. Directly reference the field offset of the
struct that differentiates the type of search to avoid those checks.

No functional change.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 33 +++++++++++++++++++++------------
 1 file changed, 21 insertions(+), 12 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 225eeeb..16f524c 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1361,11 +1361,25 @@ static inline int get_lock_depth(struct lock_list *child)
 	return depth;
 }
 
+/*
+ * Return the forward or backward dependency list.
+ *
+ * @lock:   the lock_list to get its class's dependency list
+ * @offset: the offset to struct lock_class to determine whether it is
+ *          locks_after or locks_before
+ */
+static inline struct list_head *get_dep_list(struct lock_list *lock, int offset)
+{
+	void *lock_class = lock->class;
+
+	return lock_class + offset;
+}
+
 static int __bfs(struct lock_list *source_entry,
 		 void *data,
 		 int (*match)(struct lock_list *entry, void *data),
 		 struct lock_list **target_entry,
-		 int forward)
+		 int offset)
 {
 	struct lock_list *entry;
 	struct lock_list *lock;
@@ -1379,11 +1393,7 @@ static int __bfs(struct lock_list *source_entry,
 		goto exit;
 	}
 
-	if (forward)
-		head = &source_entry->class->locks_after;
-	else
-		head = &source_entry->class->locks_before;
-
+	head = get_dep_list(source_entry, offset);
 	if (list_empty(head))
 		goto exit;
 
@@ -1397,10 +1407,7 @@ static int __bfs(struct lock_list *source_entry,
 			goto exit;
 		}
 
-		if (forward)
-			head = &lock->class->locks_after;
-		else
-			head = &lock->class->locks_before;
+		head = get_dep_list(lock, offset);
 
 		DEBUG_LOCKS_WARN_ON(!irqs_disabled());
 
@@ -1433,7 +1440,8 @@ static inline int __bfs_forwards(struct lock_list *src_entry,
 			int (*match)(struct lock_list *entry, void *data),
 			struct lock_list **target_entry)
 {
-	return __bfs(src_entry, data, match, target_entry, 1);
+	return __bfs(src_entry, data, match, target_entry,
+		     offsetof(struct lock_class, locks_after));
 
 }
 
@@ -1442,7 +1450,8 @@ static inline int __bfs_backwards(struct lock_list *src_entry,
 			int (*match)(struct lock_list *entry, void *data),
 			struct lock_list **target_entry)
 {
-	return __bfs(src_entry, data, match, target_entry, 0);
+	return __bfs(src_entry, data, match, target_entry,
+		     offsetof(struct lock_class, locks_before));
 
 }
 
-- 
1.8.3.1

[PATCH 15/28] locking/lockdep: Update comments on dependency search

[Yuyang Du]

The breadth-first search is implemented as flat-out non-recursive now, but
the comments are still describing it as recursive, update the comments in
that regard.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 21 ++++++++++-----------
 1 file changed, 10 insertions(+), 11 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 16f524c..d153b97 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1375,6 +1375,10 @@ static inline struct list_head *get_dep_list(struct lock_list *lock, int offset)
 	return lock_class + offset;
 }
 
+/*
+ * Forward- or backward-dependency search, used for both circular dependency
+ * checking and hardirq-unsafe/softirq-unsafe checking.
+ */
 static int __bfs(struct lock_list *source_entry,
 		 void *data,
 		 int (*match)(struct lock_list *entry, void *data),
@@ -1455,12 +1459,6 @@ static inline int __bfs_backwards(struct lock_list *src_entry,
 
 }
 
-/*
- * Recursive, forwards-direction lock-dependency checking, used for
- * both noncyclic checking and for hardirq-unsafe/softirq-unsafe
- * checking.
- */
-
 static void print_lock_trace(struct lock_trace *trace, unsigned int spaces)
 {
 	unsigned long *entries = stack_trace + trace->offset;
@@ -2182,7 +2180,7 @@ static inline void inc_chains(void)
 
 /*
  * There was a chain-cache miss, and we are about to add a new dependency
- * to a previous lock. We recursively validate the following rules:
+ * to a previous lock. We validate the following rules:
  *
  *  - would the adding of the <prev> -> <next> dependency create a
  *    circular dependency in the graph? [== circular deadlock]
@@ -2233,11 +2231,12 @@ static inline void inc_chains(void)
 	/*
 	 * Prove that the new <prev> -> <next> dependency would not
 	 * create a circular dependency in the graph. (We do this by
-	 * forward-recursing into the graph starting at <next>, and
-	 * checking whether we can reach <prev>.)
+	 * a breadth-first search into the graph starting at <next>,
+	 * which checks whether we can reach <prev>.)
 	 *
-	 * We are using global variables to control the recursion, to
-	 * keep the stackframe size of the recursive functions low:
+	 * The search is limited by the size of the circular queue (i.e.,
+	 * MAX_CIRCULAR_QUEUE_SIZE) which keeps track of a breadth of nodes
+	 * in the graph whose neighbours are to be checked.
 	 */
 	this.class = hlock_class(next);
 	this.parent = NULL;
-- 
1.8.3.1

[PATCH 16/28] locking/lockdep: Add explanation to lock usage rules in lockdep design doc

[Yuyang Du]

The irq usage and lock dependency rules that if violated a deacklock may
happen are explained in more detail.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 Documentation/locking/lockdep-design.txt | 33 ++++++++++++++++++++++----------
 1 file changed, 23 insertions(+), 10 deletions(-)

diff --git a/Documentation/locking/lockdep-design.txt b/Documentation/locking/lockdep-design.txt
index d5062fc..e1187d8 100644
--- a/Documentation/locking/lockdep-design.txt
+++ b/Documentation/locking/lockdep-design.txt
@@ -103,14 +103,24 @@ Unused locks (e.g., mutexes) cannot be part of the cause of an error.
 Single-lock state rules:
 ------------------------
 
+A lock is irq-safe means it was ever used in an irq context, while a lock
+is irq-unsafe means it was ever acquired with irq enabled.
+
 A softirq-unsafe lock-class is automatically hardirq-unsafe as well. The
-following states are exclusive, and only one of them is allowed to be
-set for any lock-class:
+following states must be exclusive: only one of them is allowed to be set
+for any lock-class based on its usage:
+
+ <hardirq-safe> or <hardirq-unsafe>
+ <softirq-safe> or <softirq-unsafe>
 
- <hardirq-safe> and <hardirq-unsafe>
- <softirq-safe> and <softirq-unsafe>
+This is because if a lock can be used in irq context (irq-safe) then it
+cannot be ever acquired with irq enabled (irq-unsafe). Otherwise, a
+deadlock may happen. For example, in the scenario that after this lock
+was acquired but before released, if the context is interrupted this
+lock will be attempted to acquire twice, which creates a deadlock,
+referred to as lock recursion deadlock.
 
-The validator detects and reports lock usage that violate these
+The validator detects and reports lock usage that violates these
 single-lock state rules.
 
 Multi-lock dependency rules:
@@ -119,15 +129,18 @@ Multi-lock dependency rules:
 The same lock-class must not be acquired twice, because this could lead
 to lock recursion deadlocks.
 
-Furthermore, two locks may not be taken in different order:
+Furthermore, two locks can not be taken in inverse order:
 
  <L1> -> <L2>
  <L2> -> <L1>
 
-because this could lead to lock inversion deadlocks. (The validator
-finds such dependencies in arbitrary complexity, i.e. there can be any
-other locking sequence between the acquire-lock operations, the
-validator will still track all dependencies between locks.)
+because this could lead to a deadlock - referred to as lock inversion
+deadlock - as attempts to acquire the two locks form a circle which
+could lead to the two contexts waiting for each other permanently.  The
+validator will find such dependency circle in arbitrary complexity,
+i.e., there can be any other locking sequence between the acquire-lock
+operations; the validator will still find whether these locks can be
+acquired in a circular fashion.
 
 Furthermore, the following usage based lock dependencies are not allowed
 between any two lock-classes:
-- 
1.8.3.1

[PATCH 17/28] locking/lockdep: Remove redundant argument in check_deadlock

[Yuyang Du]

In check_deadlock(), the third argument read comes from the second
argument hlock so that it can be removed. No functional change.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index d153b97..eb85183 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2143,7 +2143,7 @@ static inline void inc_chains(void)
  * Returns: 0 on deadlock detected, 1 on OK, 2 on recursive read
  */
 static int
-check_deadlock(struct task_struct *curr, struct held_lock *next, int read)
+check_deadlock(struct task_struct *curr, struct held_lock *next)
 {
 	struct held_lock *prev;
 	struct held_lock *nest = NULL;
@@ -2162,7 +2162,7 @@ static inline void inc_chains(void)
 		 * Allow read-after-read recursion of the same
 		 * lock class (i.e. read_lock(lock)+read_lock(lock)):
 		 */
-		if ((read == 2) && prev->read)
+		if ((next->read == 2) && prev->read)
 			return 2;
 
 		/*
@@ -2727,7 +2727,7 @@ static int validate_chain(struct task_struct *curr,
 		 * The simple case: does the current hold the same lock
 		 * already?
 		 */
-		int ret = check_deadlock(curr, hlock, hlock->read);
+		int ret = check_deadlock(curr, hlock);
 
 		if (!ret)
 			return 0;
-- 
1.8.3.1

[PATCH 18/28] locking/lockdep: Remove unused argument in __lock_release

[Yuyang Du]

The @nested is not used in __release_lock so remove it despite that it
is not used in lock_release in the first place.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index eb85183..6e79bd6 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3988,7 +3988,7 @@ static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
  * @nested is an hysterical artifact, needs a tree wide cleanup.
  */
 static int
-__lock_release(struct lockdep_map *lock, int nested, unsigned long ip)
+__lock_release(struct lockdep_map *lock, unsigned long ip)
 {
 	struct task_struct *curr = current;
 	struct held_lock *hlock;
@@ -4276,7 +4276,7 @@ void lock_release(struct lockdep_map *lock, int nested,
 	check_flags(flags);
 	current->lockdep_recursion = 1;
 	trace_lock_release(lock, ip);
-	if (__lock_release(lock, nested, ip))
+	if (__lock_release(lock, ip))
 		check_chain_key(current);
 	current->lockdep_recursion = 0;
 	raw_local_irq_restore(flags);
-- 
1.8.3.1

[PATCH 19/28] locking/lockdep: Optimize irq usage check when marking lock usage bit

[Yuyang Du]

The basic rule concerning IRQ usage related deadlock is to find whether
there is a direct or indirect dependency from an IRQ safe lock to an IRQ
unsafe lock, where an IRQ safe lock means the lock is ever used in IRQ
context (i.e., LOCK_USED_IN_*) while an IRQ unsafe lock means the lock
is ever acquired with IRQ enabled (i.e., LOCK_ENABLED_IN_*).

This rule is checked to find violation at two points:

 - When marking a new IRQ usage bit
 - When adding a new dependency

At each point, a check may take two searches through the dependency
graph:

 - Forward search: walk forwards the dependency graph, try to find an unsafe lock.
 - Backward search: walk backwards the dependency graph, try to find a safe lock.

If graph search/searches are successful, then there is a rule violation.
The current checks are effective albeit they can be significantly
optimized.

----------
Lock usage
----------

Any lock class can be marked as in three exclusive usage states:

 - IRQ safe or IRQ unsafe
 - Lock used (with the LOCK_USED bit marked only), which is neither safe
   nor unsafe, but can transition to either one above state

A lock can not be in both IRQ safe and unsafe states, if so it is a
simple violation of the rule by the node itself, which can be easily
found when marking IRQ usage. Therefore, this violation quest is left
out in the following.

Note that with read-write locks considered, the exclusiveness is a bit
more complex, which will be discussed in later patches.

----------------
Dependency graph
----------------

When checking the rule, the current dependency graph is composed of
nodes of the three exclusive types, and of directed edges as follows,
presumably it has no violation:

 - Edges from safe node to safe node
 - Edges from unsafe node to safe node
 - Edges from unsafe node to unsafe node

 - Edges from used node to safe node
 - Edges from used node to unsafe node
 - Edges from used node to used node
 - Edges from safe node to used node
 - Edges from unsafe node to used node

The first three types are fixed; edges will not change the type over
time. If the graph has only fixed-type edges, checking the rule would be
so easy: just check the direct dependencies involved at the two checking
points, there is even no need to search the entire graph, because a
violation could only be a direct dependency from a safe lock to an
unsafe lock.

The other five types are uncertain. If a used node transitions to other
states, the involved edge types will be altered.

----------------------
New checking algorithm
----------------------

First, two exclusive substates are added to the used state (they will be
discussed later):

 - Reachable from IRQ safe nodes
 - Unreachable from IRQ safe nodes

The new checking algorithm at the two checking points as follows:

1. When adding a new dependency from prev lock to next lock:

 - If prev is in unsafe then done. There is no worry to have any
   new violation from prev forwards so a forward search is not needed. A
   backward search for safe node is not needed either because prev is like
   a shield for next since there has been no safe node to prev.

 - If the prev is in safe state:
   * If next is safe, do a forward search for unsafe node from next
   * If next is unsafe, one violation is found
   * If next is used, do a forward search for unsafe node from next

 - If prev is in used state:
   * If prev is reachable from safe state, do a forward search for
     unsafe states from next
   * If prev is unreachable from safe state, done

A forward search for unsafe node traverses the graph as the current
forward search does. In addition, after a safe-state node or denpendency
is newly added to the graph, if a used node is encountered not marked as
reachable from safe state, then mark it reachable.

2. When marking a new usage bit for a lock

 - Used: this happens only when initializing the lock's usage bit. At
   this time, this node should have no any dependency so nothing needs
   to be done

 - Safe from used:
   * if the node is reachable from safe node, done
   * if the node is unreachable from safe node, do a forward search for unsafe node

 - Unsafe from used:
   * If the node is reachable from safe node, then a violation is found
   * If the node is unreachable from safe node, done

With this new algorithm, the checking efficiency can be improved
significantly. Backward searches are avoided; some forward search cases
are saved as well. As a result, backward dependencies are not needed any
more.

The following patches implement this new IRQ usage checking algorithm.

This starter patch defines and initializes irqsafe_lock and
irqsafe_distance fields in lock_class, which keep track of the irqsafe
locks that reach this lock class. In addition, four bitmaps are declared
to keep track of the irqsafe locks.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 include/linux/lockdep.h  | 14 ++++++++++++++
 kernel/locking/lockdep.c | 14 ++++++++++++++
 2 files changed, 28 insertions(+)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 7c2fefa..0e209b8 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -72,6 +72,11 @@ struct lock_trace {
 };
 
 #define LOCKSTAT_POINTS		4
+/*
+ * For hardirq and softirq, each has one for irqsafe lock that reaches
+ * this lock and one for irqsafe-read lock that reaches this lock.
+ */
+#define LOCK_IRQ_SAFE_LOCKS	4
 
 /*
  * The lock-class itself. The order of the structure members matters.
@@ -114,6 +119,15 @@ struct lock_class {
 	int				name_version;
 	const char			*name;
 
+	/*
+	 * irqsafe_lock indicates whether there is an IRQ safe lock
+	 * reaches this lock_class in the dependency graph, and if so
+	 * points to it; irqsafe_distance measures the distance from the
+	 * IRQ safe locks, used for keeping the shortest.
+	 */
+	struct lock_class		*irqsafe_lock[LOCK_IRQ_SAFE_LOCKS];
+	int				irqsafe_distance[LOCK_IRQ_SAFE_LOCKS];
+
 #ifdef CONFIG_LOCK_STAT
 	unsigned long			contention_point[LOCKSTAT_POINTS];
 	unsigned long			contending_point[LOCKSTAT_POINTS];
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 6e79bd6..a3138c9 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1101,6 +1101,7 @@ static bool is_dynamic_key(const struct lock_class_key *key)
 	struct lockdep_subclass_key *key;
 	struct hlist_head *hash_head;
 	struct lock_class *class;
+	int i;
 
 	DEBUG_LOCKS_WARN_ON(!irqs_disabled());
 
@@ -1153,6 +1154,9 @@ static bool is_dynamic_key(const struct lock_class_key *key)
 	WARN_ON_ONCE(!list_empty(&class->locks_before));
 	WARN_ON_ONCE(!list_empty(&class->locks_after));
 	class->name_version = count_matching_names(class);
+	for (i = 0; i < ARRAY_SIZE(class->irqsafe_distance); i++)
+		class->irqsafe_distance[i] = INT_MAX;
+
 	/*
 	 * We use RCU's safe list-add method to make
 	 * parallel walking of the hash-list safe:
@@ -2896,6 +2900,10 @@ static void print_usage_bug_scenario(struct held_lock *lock)
 	return 1;
 }
 
+static DECLARE_BITMAP(lock_classes_hardirq_safe, MAX_LOCKDEP_KEYS);
+static DECLARE_BITMAP(lock_classes_hardirq_safe_read, MAX_LOCKDEP_KEYS);
+static DECLARE_BITMAP(lock_classes_softirq_safe, MAX_LOCKDEP_KEYS);
+static DECLARE_BITMAP(lock_classes_softirq_safe_read, MAX_LOCKDEP_KEYS);
 
 /*
  * print irq inversion bug:
@@ -5001,6 +5009,12 @@ void __init lockdep_init(void)
 		+ sizeof(lock_chains)
 		+ sizeof(lock_chains_in_use)
 		+ sizeof(chain_hlocks)
+#ifdef CONFIG_TRACE_IRQFLAGS
+		+ sizeof(lock_classes_hardirq_safe)
+		+ sizeof(lock_classes_hardirq_safe_read)
+		+ sizeof(lock_classes_softirq_safe)
+		+ sizeof(lock_classes_softirq_safe_read)
+#endif
 #endif
 		) / 1024
 		);
-- 
1.8.3.1

Re: [PATCH 19/28] locking/lockdep: Optimize irq usage check when marking lock usage bit

[Peter Zijlstra]

On Wed, Apr 24, 2019 at 06:19:25PM +0800, Yuyang Du wrote:

After only a quick read of these next patches; this is the one that
worries me most.

You did mention Frederic's patches, but I'm not entirely sure you're
aware why he's doing them. He's preparing to split the softirq state
into one state per softirq vector.

See here:

  https://lkml.kernel.org/r/20190228171242.32144-14-frederic@kernel.org
  https://lkml.kernel.org/r/20190228171242.32144-15-frederic@kernel.org

IOW he's going to massively explode this storage.


> diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> index 7c2fefa..0e209b8 100644
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> @@ -72,6 +72,11 @@ struct lock_trace {
>  };
>  
>  #define LOCKSTAT_POINTS		4
> +/*
> + * For hardirq and softirq, each has one for irqsafe lock that reaches
> + * this lock and one for irqsafe-read lock that reaches this lock.
> + */
> +#define LOCK_IRQ_SAFE_LOCKS	4

This is going to be 2*(1+10) if I counted correctly.

>  /*
>   * The lock-class itself. The order of the structure members matters.
> @@ -114,6 +119,15 @@ struct lock_class {
>  	int				name_version;
>  	const char			*name;
>  
> +	/*
> +	 * irqsafe_lock indicates whether there is an IRQ safe lock
> +	 * reaches this lock_class in the dependency graph, and if so
> +	 * points to it; irqsafe_distance measures the distance from the
> +	 * IRQ safe locks, used for keeping the shortest.
> +	 */
> +	struct lock_class		*irqsafe_lock[LOCK_IRQ_SAFE_LOCKS];
> +	int				irqsafe_distance[LOCK_IRQ_SAFE_LOCKS];

Which makes this 264 additional bytes to struct lock_class, which is
immense, given that we're talking about 8192 instances of this, for a
total of over 2M of data.

> +
>  #ifdef CONFIG_LOCK_STAT
>  	unsigned long			contention_point[LOCKSTAT_POINTS];
>  	unsigned long			contending_point[LOCKSTAT_POINTS];
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 6e79bd6..a3138c9 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -1101,6 +1101,7 @@ static bool is_dynamic_key(const struct lock_class_key *key)
>  	struct lockdep_subclass_key *key;
>  	struct hlist_head *hash_head;
>  	struct lock_class *class;
> +	int i;
>  
>  	DEBUG_LOCKS_WARN_ON(!irqs_disabled());
>  
> @@ -1153,6 +1154,9 @@ static bool is_dynamic_key(const struct lock_class_key *key)
>  	WARN_ON_ONCE(!list_empty(&class->locks_before));
>  	WARN_ON_ONCE(!list_empty(&class->locks_after));
>  	class->name_version = count_matching_names(class);
> +	for (i = 0; i < ARRAY_SIZE(class->irqsafe_distance); i++)
> +		class->irqsafe_distance[i] = INT_MAX;
> +
>  	/*
>  	 * We use RCU's safe list-add method to make
>  	 * parallel walking of the hash-list safe:
> @@ -2896,6 +2900,10 @@ static void print_usage_bug_scenario(struct held_lock *lock)
>  	return 1;
>  }
>  
> +static DECLARE_BITMAP(lock_classes_hardirq_safe, MAX_LOCKDEP_KEYS);
> +static DECLARE_BITMAP(lock_classes_hardirq_safe_read, MAX_LOCKDEP_KEYS);
> +static DECLARE_BITMAP(lock_classes_softirq_safe, MAX_LOCKDEP_KEYS);
> +static DECLARE_BITMAP(lock_classes_softirq_safe_read, MAX_LOCKDEP_KEYS);

That will need being written like:

#define LOCKDEP_STATE(__STATE)								\
	static DECLARE_BITMAP(lock_classes_##__STATE##_safe, MAX_LOCKDEP_KEYS);		\
	static DECLARE_BITMAP(lock_classes_##__STATE##_safe_read, MAX_LOCKDEP_KEYS);
#include "lockdep_states.h"
#undef LOCKDEP_STATE

And will thereby generate 22 bitmaps, each being 1kb of storage.

>  /*
>   * print irq inversion bug:
> @@ -5001,6 +5009,12 @@ void __init lockdep_init(void)
>  		+ sizeof(lock_chains)
>  		+ sizeof(lock_chains_in_use)
>  		+ sizeof(chain_hlocks)
> +#ifdef CONFIG_TRACE_IRQFLAGS
> +		+ sizeof(lock_classes_hardirq_safe)
> +		+ sizeof(lock_classes_hardirq_safe_read)
> +		+ sizeof(lock_classes_softirq_safe)
> +		+ sizeof(lock_classes_softirq_safe_read)

another macro generator here.

> +#endif
>  #endif
>  		) / 1024
>  		);

Now, I would normally not care too much about memory costs for a debug
feature, except there's architectures that need to keep their image size
small, see the comment that goes along with CONFIG_LOCKDEP_SMALL in
lockdep_internals.h.

Re: [PATCH 19/28] locking/lockdep: Optimize irq usage check when marking lock usage bit

[Yuyang Du]

Thanks for review.

On Fri, 26 Apr 2019 at 03:32, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Wed, Apr 24, 2019 at 06:19:25PM +0800, Yuyang Du wrote:
>
> After only a quick read of these next patches; this is the one that
> worries me most.
>
> You did mention Frederic's patches, but I'm not entirely sure you're
> aware why he's doing them. He's preparing to split the softirq state
> into one state per softirq vector.
>
> See here:
>
>   https://lkml.kernel.org/r/20190228171242.32144-14-frederic@kernel.org
>   https://lkml.kernel.org/r/20190228171242.32144-15-frederic@kernel.org
>
> IOW he's going to massively explode this storage.

If I understand correctly, he is not going to.

First of all, we can divide the whole usage thing into tracking and checking.

Frederic's fine-grained soft vector state is applied to usage
tracking, i.e., which specific vectors a lock is used or enabled.

But for usage checking, which vectors are does not really matter. So,
the current size of the arrays and bitmaps are good enough. Right?

Re: [PATCH 19/28] locking/lockdep: Optimize irq usage check when marking lock usage bit

[Peter Zijlstra]

On Fri, Apr 26, 2019 at 02:57:37PM +0800, Yuyang Du wrote:
> Thanks for review.
> 
> On Fri, 26 Apr 2019 at 03:32, Peter Zijlstra <peterz@infradead.org> wrote:
> >
> > On Wed, Apr 24, 2019 at 06:19:25PM +0800, Yuyang Du wrote:
> >
> > After only a quick read of these next patches; this is the one that
> > worries me most.
> >
> > You did mention Frederic's patches, but I'm not entirely sure you're
> > aware why he's doing them. He's preparing to split the softirq state
> > into one state per softirq vector.
> >
> > See here:
> >
> >   https://lkml.kernel.org/r/20190228171242.32144-14-frederic@kernel.org
> >   https://lkml.kernel.org/r/20190228171242.32144-15-frederic@kernel.org
> >
> > IOW he's going to massively explode this storage.
> 
> If I understand correctly, he is not going to.
> 
> First of all, we can divide the whole usage thing into tracking and checking.
> 
> Frederic's fine-grained soft vector state is applied to usage
> tracking, i.e., which specific vectors a lock is used or enabled.
> 
> But for usage checking, which vectors are does not really matter. So,
> the current size of the arrays and bitmaps are good enough. Right?

Frederic? My understanding was that he really was going to split the
whole thing. The moment you allow masking individual soft vectors, you
get per-vector dependency chains.

Re: [PATCH 19/28] locking/lockdep: Optimize irq usage check when marking lock usage bit

[Yuyang Du]

On Tue, 30 Apr 2019 at 20:12, Peter Zijlstra <peterz@infradead.org> wrote:
> > > IOW he's going to massively explode this storage.
> >
> > If I understand correctly, he is not going to.
> >
> > First of all, we can divide the whole usage thing into tracking and checking.
> >
> > Frederic's fine-grained soft vector state is applied to usage
> > tracking, i.e., which specific vectors a lock is used or enabled.
> >
> > But for usage checking, which vectors are does not really matter. So,
> > the current size of the arrays and bitmaps are good enough. Right?
>
> Frederic? My understanding was that he really was going to split the
> whole thing. The moment you allow masking individual soft vectors, you
> get per-vector dependency chains.

It seems so. What I understand is: for IRQ usage, the difference is:

Each lock has a new usage mask:

        softirq10, ..., softirq1, hardirq

where softirq1 | softirq2 | ... | softirq10 = softirq

where softirq, exactly what was, virtually is used in the checking.
This is mainly because, any irq vector has any usage, the lock has
that usage, be it hard or soft.

If that is right, hardirq can be split too (why not if softirq does
:)). So, maybe a bitmap to do them all for tracking, and optionally
maintain aggregate softirq and hardirq for checking as before.
Regardless, may irq-safe reachability thing is not affected.

And for the chain, which is mainly for caching does not really matter
split or not (either way, the outcome will be the same?), because
there will be a hash for a chain anyway, which is the same. Right?

Re: [PATCH 19/28] locking/lockdep: Optimize irq usage check when marking lock usage bit

[Yuyang Du]

On Mon, 6 May 2019 at 11:05, Yuyang Du <duyuyang@gmail.com> wrote:
>
> On Tue, 30 Apr 2019 at 20:12, Peter Zijlstra <peterz@infradead.org> wrote:
> > > > IOW he's going to massively explode this storage.
> > >
> > > If I understand correctly, he is not going to.
> > >
> > > First of all, we can divide the whole usage thing into tracking and checking.
> > >
> > > Frederic's fine-grained soft vector state is applied to usage
> > > tracking, i.e., which specific vectors a lock is used or enabled.
> > >
> > > But for usage checking, which vectors are does not really matter. So,
> > > the current size of the arrays and bitmaps are good enough. Right?
> >
> > Frederic? My understanding was that he really was going to split the
> > whole thing. The moment you allow masking individual soft vectors, you
> > get per-vector dependency chains.
>
> It seems so. What I understand is: for IRQ usage, the difference is:
>
> Each lock has a new usage mask:
>
>         softirq10, ..., softirq1, hardirq
>
> where softirq1 | softirq2 | ... | softirq10 = softirq
>
> where softirq, exactly what was, virtually is used in the checking.
> This is mainly because, any irq vector has any usage, the lock has
> that usage, be it hard or soft.
>
> If that is right, hardirq can be split too (why not if softirq does
> :)). So, maybe a bitmap to do them all for tracking, and optionally
> maintain aggregate softirq and hardirq for checking as before.
> Regardless, may irq-safe reachability thing is not affected.
>
> And for the chain, which is mainly for caching does not really matter
> split or not (either way, the outcome will be the same?), because
> there will be a hash for a chain anyway, which is the same. Right?

Oh, another look at the patch, I was wrong, it can be very different
if consider: used in vector X vs. enabled on vector Y (which is ok),
when enablement can be so fine-grained as well, which is actually the
point of the patch, though no difference for now :(

Re: [PATCH 19/28] locking/lockdep: Optimize irq usage check when marking lock usage bit

[Frederic Weisbecker]

On Tue, Apr 30, 2019 at 02:11:48PM +0200, Peter Zijlstra wrote:
> On Fri, Apr 26, 2019 at 02:57:37PM +0800, Yuyang Du wrote:
> > Thanks for review.
> > 
> > On Fri, 26 Apr 2019 at 03:32, Peter Zijlstra <peterz@infradead.org> wrote:
> > >
> > > On Wed, Apr 24, 2019 at 06:19:25PM +0800, Yuyang Du wrote:
> > >
> > > After only a quick read of these next patches; this is the one that
> > > worries me most.
> > >
> > > You did mention Frederic's patches, but I'm not entirely sure you're
> > > aware why he's doing them. He's preparing to split the softirq state
> > > into one state per softirq vector.
> > >
> > > See here:
> > >
> > >   https://lkml.kernel.org/r/20190228171242.32144-14-frederic@kernel.org
> > >   https://lkml.kernel.org/r/20190228171242.32144-15-frederic@kernel.org
> > >
> > > IOW he's going to massively explode this storage.
> > 
> > If I understand correctly, he is not going to.
> > 
> > First of all, we can divide the whole usage thing into tracking and checking.
> > 
> > Frederic's fine-grained soft vector state is applied to usage
> > tracking, i.e., which specific vectors a lock is used or enabled.
> > 
> > But for usage checking, which vectors are does not really matter. So,
> > the current size of the arrays and bitmaps are good enough. Right?
> 
> Frederic? My understanding was that he really was going to split the
> whole thing. The moment you allow masking individual soft vectors, you
> get per-vector dependency chains.

Right, so in my patchset there is indeed individual soft vectors masked
so we indeed need per vector checks. For example a lock taken in HRTIMER
softirq shouldn't be a problem if it is concurrently taken while BLOCK softirq
is enabled. And for that we expand the usage_mask so that the 4 bits currently
used for general SOFTIRQ are now multiplied by NR_SOFTIRQ (10) because we need to
track the USED and ENABLED_IN bits for each of them.

The end result is:

4 hard irq bits + 4 * 10 softirq bits + LOCK_USED bit = 45 bits.

Not sure that answers the question as I'm a bit lost in the debate...

Re: [PATCH 19/28] locking/lockdep: Optimize irq usage check when marking lock usage bit

[Yuyang Du]

On Tue, 7 May 2019 at 09:47, Frederic Weisbecker <frederic@kernel.org> wrote:
> > > But for usage checking, which vectors are does not really matter. So,
> > > the current size of the arrays and bitmaps are good enough. Right?
> >
> > Frederic? My understanding was that he really was going to split the
> > whole thing. The moment you allow masking individual soft vectors, you
> > get per-vector dependency chains.
>
> Right, so in my patchset there is indeed individual soft vectors masked
> so we indeed need per vector checks. For example a lock taken in HRTIMER
> softirq shouldn't be a problem if it is concurrently taken while BLOCK softirq
> is enabled. And for that we expand the usage_mask so that the 4 bits currently
> used for general SOFTIRQ are now multiplied by NR_SOFTIRQ (10) because we need to
> track the USED and ENABLED_IN bits for each of them.
>
> The end result is:
>
> 4 hard irq bits + 4 * 10 softirq bits + LOCK_USED bit = 45 bits.
>
> Not sure that answers the question as I'm a bit lost in the debate...

It was really I was lost: I didn't realize the enabling (or disabling)
is going to be fine-grained as well until I read this changelog:

Disabling the softirqs is currently an all-or-nothing operation: either
all softirqs are enabled or none of them. However we plan to introduce a
per vector granularity of this ability to improve latency response and
make each softirq vector interruptible by the others.

Sorry for the confusion I made :)

[PATCH 20/28] locking/lockdep: Refactorize check_noncircular and check_redundant

[Yuyang Du]

These two functions now handle different check results themselves. A new
check_path function is added to check whether there is a path in the
dependency graph. No functional change.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 98 +++++++++++++++++++++++++++++++-----------------
 1 file changed, 63 insertions(+), 35 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index a3138c9..4d42124 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1681,33 +1681,79 @@ unsigned long lockdep_count_backward_deps(struct lock_class *class)
 }
 
 /*
- * Prove that the dependency graph starting at <entry> can not
- * lead to <target>. Print an error and return 0 if it does.
+ * Check that the dependency graph starting at <src> can lead to
+ * <target> or not. Print an error and return 0 if it does.
  */
 static noinline int
-check_noncircular(struct lock_list *root, struct lock_class *target,
-		struct lock_list **target_entry)
+check_path(struct lock_class *target, struct lock_list *src_entry,
+	   struct lock_list **target_entry)
 {
-	int result;
+	int ret;
+
+	ret = __bfs_forwards(src_entry, (void *)target, class_equal,
+			     target_entry);
+
+	if (unlikely(ret < 0))
+		print_bfs_bug(ret);
+
+	return ret;
+}
+
+/*
+ * Prove that the dependency graph starting at <src> can not
+ * lead to <target>. If it can, there is a circle when adding
+ * <target> -> <src> dependency.
+ *
+ * Print an error and return 0 if it does.
+ */
+static noinline int
+check_noncircular(struct held_lock *src, struct held_lock *target)
+{
+	int ret;
+	struct lock_list *uninitialized_var(target_entry);
+	struct lock_list src_entry = {
+		.class = hlock_class(src),
+		.parent = NULL,
+	};
 
 	debug_atomic_inc(nr_cyclic_checks);
 
-	result = __bfs_forwards(root, target, class_equal, target_entry);
+	ret = check_path(hlock_class(target), &src_entry, &target_entry);
 
-	return result;
+	if (unlikely(!ret))
+		print_circular_bug(&src_entry, target_entry, src, target);
+
+	return ret;
 }
 
+/*
+ * Check that the dependency graph starting at <src> can lead to
+ * <target> or not. If it can, <src> -> <target> dependency is already
+ * in the graph.
+ *
+ * Print an error and return 2 if it does or 1 if it does not.
+ */
 static noinline int
-check_redundant(struct lock_list *root, struct lock_class *target,
-		struct lock_list **target_entry)
+check_redundant(struct held_lock *src, struct held_lock *target)
 {
-	int result;
+	int ret;
+	struct lock_list *uninitialized_var(target_entry);
+	struct lock_list src_entry = {
+		.class = hlock_class(src),
+		.parent = NULL,
+	};
 
 	debug_atomic_inc(nr_redundant_checks);
 
-	result = __bfs_forwards(root, target, class_equal, target_entry);
+	ret = check_path(hlock_class(target), &src_entry, &target_entry);
 
-	return result;
+	if (!ret) {
+		debug_atomic_inc(nr_redundant);
+		ret = 2;
+	} else if (ret < 0)
+		ret = 0;
+
+	return ret;
 }
 
 #if defined(CONFIG_TRACE_IRQFLAGS)
@@ -2208,9 +2254,7 @@ static inline void inc_chains(void)
 check_prev_add(struct task_struct *curr, struct held_lock *prev,
 	       struct held_lock *next, int distance)
 {
-	struct lock_list *uninitialized_var(target_entry);
 	struct lock_list *entry;
-	struct lock_list this;
 	struct lock_trace trace;
 	int ret;
 
@@ -2242,17 +2286,9 @@ static inline void inc_chains(void)
 	 * MAX_CIRCULAR_QUEUE_SIZE) which keeps track of a breadth of nodes
 	 * in the graph whose neighbours are to be checked.
 	 */
-	this.class = hlock_class(next);
-	this.parent = NULL;
-	ret = check_noncircular(&this, hlock_class(prev), &target_entry);
-	if (unlikely(!ret)) {
-		print_circular_bug(&this, target_entry, next, prev);
-		return 0;
-	}
-	else if (unlikely(ret < 0)) {
-		print_bfs_bug(ret);
+	ret = check_noncircular(next, prev);
+	if (unlikely(ret <= 0))
 		return 0;
-	}
 
 	if (!check_prev_add_irq(curr, prev, next))
 		return 0;
@@ -2286,17 +2322,9 @@ static inline void inc_chains(void)
 	/*
 	 * Is the <prev> -> <next> link redundant?
 	 */
-	this.class = hlock_class(prev);
-	this.parent = NULL;
-	ret = check_redundant(&this, hlock_class(next), &target_entry);
-	if (!ret) {
-		debug_atomic_inc(nr_redundant);
-		return 2;
-	}
-	if (ret < 0) {
-		print_bfs_bug(ret);
-		return 0;
-	}
+	ret = check_redundant(prev, next);
+	if (ret != 1)
+		return ret;
 
 	if (!save_trace(&trace))
 		return 0;
-- 
1.8.3.1

Re: [PATCH 20/28] locking/lockdep: Refactorize check_noncircular and check_redundant

[Peter Zijlstra]

On Wed, Apr 24, 2019 at 06:19:26PM +0800, Yuyang Du wrote:
> These two functions now handle different check results themselves. A new
> check_path function is added to check whether there is a path in the
> dependency graph. No functional change.

This looks good, however I completely forgot we still had the redundant
thing.

It was added for cross-release (which has since been reverted) which
would generate a lot of redundant links (IIRC) but having it makes the
reports more convoluted -- basically, if we had an A-B-C relation, then
A-C will not be added to the graph because it is already covered. This
then means any report will include B, even though a shorter cycle might
have been possible.

Maybe we should make the whole redundant check depend on LOCKDEP_SMALL
for now.

Re: [PATCH 20/28] locking/lockdep: Refactorize check_noncircular and check_redundant

[Yuyang Du]

Thanks for review.

On Fri, 26 Apr 2019 at 03:48, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Wed, Apr 24, 2019 at 06:19:26PM +0800, Yuyang Du wrote:
> > These two functions now handle different check results themselves. A new
> > check_path function is added to check whether there is a path in the
> > dependency graph. No functional change.
>
> This looks good, however I completely forgot we still had the redundant
> thing.
>
> It was added for cross-release (which has since been reverted) which
> would generate a lot of redundant links (IIRC) but having it makes the
> reports more convoluted -- basically, if we had an A-B-C relation, then
> A-C will not be added to the graph because it is already covered. This
> then means any report will include B, even though a shorter cycle might
> have been possible.
>
> Maybe we should make the whole redundant check depend on LOCKDEP_SMALL
> for now.

Sure. I can do that.

[PATCH 21/28] locking/lockdep: Consolidate lock usage bit initialization

[Yuyang Du]

Lock usage bit initialization is consolidated into one function
mark_usage(). Trivial readability improvement. No functional change.

Signed-off-by: Yuyang Du <duyuyang@gmail.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 4d42124..c08ec88 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3354,8 +3354,12 @@ void trace_softirqs_off(unsigned long ip)
 		debug_atomic_inc(redundant_softirqs_off);
 }
 
-static int mark_irqflags(struct task_struct *curr, struct held_lock *hlock)
+static int
+mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
 {
+	if (!check)
+		goto lock_used;
+
 	/*
 	 * If non-trylock use in a hardirq or softirq context, then
 	 * mark the lock as used in these contexts:
@@ -3399,6 +3403,11 @@ static int mark_irqflags(struct task_struct *curr, struct held_lock *hlock)
 		}
 	}
 
+lock_used:
+	/* mark it as used: */
+	if (!mark_lock(curr, hlock, LOCK_USED))
+		return 0;
+
 	return 1;
 }
 
@@ -3440,8 +3449,8 @@ int mark_lock_irq(struct task_struct *curr, struct held_lock *this,
 	return 1;
 }
 
-static inline int mark_irqflags(struct task_struct *curr,
-		struct held_lock *hlock)
+static inline int
+mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
 {
 	return 1;
 }
@@ -3727,11 +3736,8 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 #endif
 	hlock->pin_count = pin_count;
 
-	if (check && !mark_irqflags(curr, hlock))
-		return 0;
-
-	/* mark it as used: */
-	if (!mark_lock(curr, hlock, LOCK_USED))
+	/* Initialize the lock usage bit */
+	if (!mark_usage(curr, hlock, check))
 		return 0;
 
 	/*
-- 
1.8.3.1

[PATCH 22/28] locking/lockdep: Adjust new bit cases in mark_lock

[Yuyang Du]

The new bit can be any possible lock usage except it is garbage, so the
cases in switch can be made simpler. Warn early on if wrong usage bit is
passed without taking locks. No functional change.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 21 +++++++--------------
 1 file changed, 7 insertions(+), 14 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index c08ec88..291cc9c 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3476,6 +3476,11 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 {
 	unsigned int new_mask = 1 << new_bit, ret = 1;
 
+	if (new_bit >= LOCK_USAGE_STATES) {
+		WARN_ON(1);
+		return 0;
+	}
+
 	/*
 	 * If already set then do not dirty the cacheline,
 	 * nor do any checks:
@@ -3499,25 +3504,13 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 		return 0;
 
 	switch (new_bit) {
-#define LOCKDEP_STATE(__STATE)			\
-	case LOCK_USED_IN_##__STATE:		\
-	case LOCK_USED_IN_##__STATE##_READ:	\
-	case LOCK_ENABLED_##__STATE:		\
-	case LOCK_ENABLED_##__STATE##_READ:
-#include "lockdep_states.h"
-#undef LOCKDEP_STATE
-		ret = mark_lock_irq(curr, this, new_bit);
-		if (!ret)
-			return 0;
-		break;
 	case LOCK_USED:
 		debug_atomic_dec(nr_unused_locks);
 		break;
 	default:
-		if (!debug_locks_off_graph_unlock())
+		ret = mark_lock_irq(curr, this, new_bit);
+		if (!ret)
 			return 0;
-		WARN_ON(1);
-		return 0;
 	}
 
 	graph_unlock();
-- 
1.8.3.1

Re: [PATCH 22/28] locking/lockdep: Adjust new bit cases in mark_lock

[Peter Zijlstra]

On Wed, Apr 24, 2019 at 06:19:28PM +0800, Yuyang Du wrote:
> The new bit can be any possible lock usage except it is garbage, so the

s/except it/except when it/ ?

> cases in switch can be made simpler. Warn early on if wrong usage bit is
> passed without taking locks. No functional change.
> 
> Signed-off-by: Yuyang Du <duyuyang@gmail.com>
> ---
>  kernel/locking/lockdep.c | 21 +++++++--------------
>  1 file changed, 7 insertions(+), 14 deletions(-)
> 
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index c08ec88..291cc9c 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -3476,6 +3476,11 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
>  {
>  	unsigned int new_mask = 1 << new_bit, ret = 1;
>  
> +	if (new_bit >= LOCK_USAGE_STATES) {
> +		WARN_ON(1);

Does that want to be DEBUG_LOCKS_WARN_ON() ?

> +		return 0;
> +	}
> +
>  	/*
>  	 * If already set then do not dirty the cacheline,
>  	 * nor do any checks:
> @@ -3499,25 +3504,13 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
>  		return 0;
>  
>  	switch (new_bit) {
> -#define LOCKDEP_STATE(__STATE)			\
> -	case LOCK_USED_IN_##__STATE:		\
> -	case LOCK_USED_IN_##__STATE##_READ:	\
> -	case LOCK_ENABLED_##__STATE:		\
> -	case LOCK_ENABLED_##__STATE##_READ:
> -#include "lockdep_states.h"
> -#undef LOCKDEP_STATE
> -		ret = mark_lock_irq(curr, this, new_bit);
> -		if (!ret)
> -			return 0;
> -		break;
>  	case LOCK_USED:
>  		debug_atomic_dec(nr_unused_locks);
>  		break;
>  	default:
> -		if (!debug_locks_off_graph_unlock())
> +		ret = mark_lock_irq(curr, this, new_bit);
> +		if (!ret)
>  			return 0;
> -		WARN_ON(1);
> -		return 0;
>  	}
>  
>  	graph_unlock();
> -- 
> 1.8.3.1
> 

Re: [PATCH 22/28] locking/lockdep: Adjust new bit cases in mark_lock

[Yuyang Du]

Thanks for review.

On Fri, 26 Apr 2019 at 03:52, Peter Zijlstra <peterz@infradead.org> wrote:
> > +     if (new_bit >= LOCK_USAGE_STATES) {
> > +             WARN_ON(1);
>
> Does that want to be DEBUG_LOCKS_WARN_ON() ?

Indeed, it was.

[PATCH 23/28] locking/lockdep: Update irqsafe lock bitmaps

[Yuyang Du]

The bitmaps keep track of which locks are irqsafe. Update the bitmaps
when there is new irqsafe usage and when an irqsafe lock is zapped.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 39 ++++++++++++++++++++++++++++++++++++++-
 1 file changed, 38 insertions(+), 1 deletion(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 291cc9c..1b78216 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3107,6 +3107,7 @@ typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
 	int excl_bit = exclusive_bit(new_bit);
 	int read = new_bit & LOCK_USAGE_READ_MASK;
 	int dir = new_bit & LOCK_USAGE_DIR_MASK;
+	struct lock_class *lock = hlock_class(this);
 
 	/*
 	 * mark USED_IN has to look forwards -- to ensure no dependency
@@ -3119,6 +3120,25 @@ typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
 		check_usage_backwards : check_usage_forwards;
 
 	/*
+	 * The bit is already marked so that we update the bitmaps
+	 * before validation.
+	 */
+	if (!dir) {
+		unsigned long *bitmaps[4] = {
+			lock_classes_hardirq_safe,
+			lock_classes_hardirq_safe_read,
+			lock_classes_softirq_safe,
+			lock_classes_softirq_safe_read
+		};
+		int index = (new_bit >> 2) << 1;
+
+		if (read)
+		       index += 1;
+
+		__set_bit(lock - lock_classes, bitmaps[index]);
+	}
+
+	/*
 	 * Validate that this particular lock does not have conflicting
 	 * usage states.
 	 */
@@ -3146,7 +3166,7 @@ typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
 			return 0;
 	}
 
-	if (state_verbose(new_bit, hlock_class(this)))
+	if (state_verbose(new_bit, lock))
 		return 2;
 
 	return 1;
@@ -4650,6 +4670,22 @@ static void remove_class_from_lock_chains(struct pending_free *pf,
 	}
 }
 
+static inline void remove_irqsafe_lock_bitmap(struct lock_class *class)
+{
+#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
+	unsigned long usage = class->usage_mask;
+
+	if (usage & LOCKF_USED_IN_HARDIRQ)
+		__clear_bit(class - lock_classes, lock_classes_hardirq_safe);
+	if (usage & LOCKF_USED_IN_HARDIRQ_READ)
+		__clear_bit(class - lock_classes, lock_classes_hardirq_safe_read);
+	if (usage & LOCKF_USED_IN_SOFTIRQ)
+		__clear_bit(class - lock_classes, lock_classes_softirq_safe);
+	if (usage & LOCKF_USED_IN_SOFTIRQ_READ)
+		__clear_bit(class - lock_classes, lock_classes_softirq_safe_read);
+#endif
+}
+
 /*
  * Remove all references to a lock class. The caller must hold the graph lock.
  */
@@ -4680,6 +4716,7 @@ static void zap_class(struct pending_free *pf, struct lock_class *class)
 		WRITE_ONCE(class->name, NULL);
 		nr_lock_classes--;
 		__clear_bit(class - lock_classes, lock_classes_in_use);
+		remove_irqsafe_lock_bitmap(class);
 	} else {
 		WARN_ONCE(true, "%s() failed for class %s\n", __func__,
 			  class->name);
-- 
1.8.3.1

Re: [PATCH 23/28] locking/lockdep: Update irqsafe lock bitmaps

[Peter Zijlstra]

On Wed, Apr 24, 2019 at 06:19:29PM +0800, Yuyang Du wrote:
> The bitmaps keep track of which locks are irqsafe. Update the bitmaps
> when there is new irqsafe usage and when an irqsafe lock is zapped.
> 
> Signed-off-by: Yuyang Du <duyuyang@gmail.com>
> ---
>  kernel/locking/lockdep.c | 39 ++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 38 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 291cc9c..1b78216 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -3107,6 +3107,7 @@ typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
>  	int excl_bit = exclusive_bit(new_bit);
>  	int read = new_bit & LOCK_USAGE_READ_MASK;
>  	int dir = new_bit & LOCK_USAGE_DIR_MASK;
> +	struct lock_class *lock = hlock_class(this);
>  
>  	/*
>  	 * mark USED_IN has to look forwards -- to ensure no dependency
> @@ -3119,6 +3120,25 @@ typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
>  		check_usage_backwards : check_usage_forwards;
>  
>  	/*
> +	 * The bit is already marked so that we update the bitmaps
> +	 * before validation.
> +	 */
> +	if (!dir) {
> +		unsigned long *bitmaps[4] = {
> +			lock_classes_hardirq_safe,
> +			lock_classes_hardirq_safe_read,
> +			lock_classes_softirq_safe,
> +			lock_classes_softirq_safe_read

That again should be something CPP magic using lockdep_states.h.

Also, that array can be static const, right? It's just an index into the
static bitmaps.

> +		};
> +		int index = (new_bit >> 2) << 1;
> +
> +		if (read)
> +		       index += 1;
> +
> +		__set_bit(lock - lock_classes, bitmaps[index]);
> +	}
> +
> +	/*
>  	 * Validate that this particular lock does not have conflicting
>  	 * usage states.
>  	 */
> @@ -3146,7 +3166,7 @@ typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
>  			return 0;
>  	}
>  
> -	if (state_verbose(new_bit, hlock_class(this)))
> +	if (state_verbose(new_bit, lock))
>  		return 2;
>  
>  	return 1;
> @@ -4650,6 +4670,22 @@ static void remove_class_from_lock_chains(struct pending_free *pf,
>  	}
>  }
>  
> +static inline void remove_irqsafe_lock_bitmap(struct lock_class *class)
> +{
> +#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
> +	unsigned long usage = class->usage_mask;
> +
> +	if (usage & LOCKF_USED_IN_HARDIRQ)
> +		__clear_bit(class - lock_classes, lock_classes_hardirq_safe);
> +	if (usage & LOCKF_USED_IN_HARDIRQ_READ)
> +		__clear_bit(class - lock_classes, lock_classes_hardirq_safe_read);
> +	if (usage & LOCKF_USED_IN_SOFTIRQ)
> +		__clear_bit(class - lock_classes, lock_classes_softirq_safe);
> +	if (usage & LOCKF_USED_IN_SOFTIRQ_READ)
> +		__clear_bit(class - lock_classes, lock_classes_softirq_safe_read);

More CPP foo required here. Also, do we really need to test, we could
just unconditionally clear the bits.

> +#endif
> +}

Re: [PATCH 23/28] locking/lockdep: Update irqsafe lock bitmaps

[Yuyang Du]

Thanks for review.

On Fri, 26 Apr 2019 at 03:55, Peter Zijlstra <peterz@infradead.org> wrote:
> > +     if (!dir) {
> > +             unsigned long *bitmaps[4] = {
> > +                     lock_classes_hardirq_safe,
> > +                     lock_classes_hardirq_safe_read,
> > +                     lock_classes_softirq_safe,
> > +                     lock_classes_softirq_safe_read
>
> That again should be something CPP magic using lockdep_states.h.

Yes.

> Also, that array can be static const, right? It's just an index into the
> static bitmaps.

Sure.

[...]
> > +static inline void remove_irqsafe_lock_bitmap(struct lock_class *class)
> > +{
> > +#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
> > +     unsigned long usage = class->usage_mask;
> > +
> > +     if (usage & LOCKF_USED_IN_HARDIRQ)
> > +             __clear_bit(class - lock_classes, lock_classes_hardirq_safe);
> > +     if (usage & LOCKF_USED_IN_HARDIRQ_READ)
> > +             __clear_bit(class - lock_classes, lock_classes_hardirq_safe_read);
> > +     if (usage & LOCKF_USED_IN_SOFTIRQ)
> > +             __clear_bit(class - lock_classes, lock_classes_softirq_safe);
> > +     if (usage & LOCKF_USED_IN_SOFTIRQ_READ)
> > +             __clear_bit(class - lock_classes, lock_classes_softirq_safe_read);
>
> More CPP foo required here.

Definitely.

> Also, do we really need to test, we could
> just unconditionally clear the bits.

Actually, these tests are used later for another cause: we want to
know which safe usage may be changed by zapping this lock.

[PATCH 24/28] locking/lockdep: Remove !dir in lock irq usage check

[Yuyang Du]

In mark_lock_irq(), the following checks are performed:

   ----------------------------------
  |   ->      | unsafe | read unsafe |
  |----------------------------------|
  | safe      |  F  B  |    F* B*    |
  |----------------------------------|
  | read safe |  F? B* |      -      |
   ----------------------------------

Where:
F: check_usage_forwards
B: check_usage_backwards
*: check enabled by STRICT_READ_CHECKS
?: check enabled by the !dir condition

From checking point of view, the special F? case does not make sense,
whereas it perhaps is made for peroformance concern. As later patch will
address this issue, remove this exception, which makes the checks
consistent later.

With STRICT_READ_CHECKS = 1 which is default, there is no functional
change.

Signed-off-by: Yuyang Du <duyuyang@gmail.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 1b78216..2f24028 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3149,7 +3149,7 @@ typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
 	 * Validate that the lock dependencies don't have conflicting usage
 	 * states.
 	 */
-	if ((!read || !dir || STRICT_READ_CHECKS) &&
+	if ((!read || STRICT_READ_CHECKS) &&
 			!usage(curr, this, excl_bit, state_name(new_bit & ~LOCK_USAGE_READ_MASK)))
 		return 0;
 
-- 
1.8.3.1

Re: [PATCH 24/28] locking/lockdep: Remove !dir in lock irq usage check

[Peter Zijlstra]

On Wed, Apr 24, 2019 at 06:19:30PM +0800, Yuyang Du wrote:
> In mark_lock_irq(), the following checks are performed:
> 
>    ----------------------------------
>   |   ->      | unsafe | read unsafe |
>   |----------------------------------|
>   | safe      |  F  B  |    F* B*    |
>   |----------------------------------|
>   | read safe |  F? B* |      -      |
>    ----------------------------------
> 
> Where:
> F: check_usage_forwards
> B: check_usage_backwards
> *: check enabled by STRICT_READ_CHECKS
> ?: check enabled by the !dir condition
> 
> From checking point of view, the special F? case does not make sense,
> whereas it perhaps is made for peroformance concern. As later patch will
> address this issue, remove this exception, which makes the checks
> consistent later.
> 
> With STRICT_READ_CHECKS = 1 which is default, there is no functional
> change.

Oh man.. thinking required and it is way late.. anyway this whole read
stuff made me remember we had a patch set on readlocks last year.

  https://lkml.kernel.org/r/20180411135110.9217-1-boqun.feng@gmail.com

I remember reviewing that a few times and then it dropped on the floor,
probably because Spectre crap or something sucked up all my time again :/

Sorry Boqun!

Re: [PATCH 24/28] locking/lockdep: Remove !dir in lock irq usage check

[Yuyang Du]

Thanks for review.

On Fri, 26 Apr 2019 at 04:03, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Wed, Apr 24, 2019 at 06:19:30PM +0800, Yuyang Du wrote:
> > In mark_lock_irq(), the following checks are performed:
> >
> >    ----------------------------------
> >   |   ->      | unsafe | read unsafe |
> >   |----------------------------------|
> >   | safe      |  F  B  |    F* B*    |
> >   |----------------------------------|
> >   | read safe |  F? B* |      -      |
> >    ----------------------------------
> >
> > Where:
> > F: check_usage_forwards
> > B: check_usage_backwards
> > *: check enabled by STRICT_READ_CHECKS
> > ?: check enabled by the !dir condition
> >
> > From checking point of view, the special F? case does not make sense,
> > whereas it perhaps is made for peroformance concern. As later patch will
> > address this issue, remove this exception, which makes the checks
> > consistent later.
> >
> > With STRICT_READ_CHECKS = 1 which is default, there is no functional
> > change.
>
> Oh man.. thinking required and it is way late.. anyway this whole read
> stuff made me remember we had a patch set on readlocks last year.
>
>   https://lkml.kernel.org/r/20180411135110.9217-1-boqun.feng@gmail.com
>
> I remember reviewing that a few times and then it dropped on the floor,
> probably because Spectre crap or something sucked up all my time again :/
>
> Sorry Boqun!

Oh man, I thought about the read-write lock stuff, but I didn't know
Boqun's patch. Let me hurt my brain looking at that patch.

Re: [PATCH 24/28] locking/lockdep: Remove !dir in lock irq usage check

[Boqun Feng]

On Fri, Apr 26, 2019, at 3:06 PM, Yuyang Du wrote:
> Thanks for review.
> 
> On Fri, 26 Apr 2019 at 04:03, Peter Zijlstra <peterz@infradead.org> wrote:
> >
> > On Wed, Apr 24, 2019 at 06:19:30PM +0800, Yuyang Du wrote:
> > > In mark_lock_irq(), the following checks are performed:
> > >
> > >    ----------------------------------
> > >   |   ->      | unsafe | read unsafe |
> > >   |----------------------------------|
> > >   | safe      |  F  B  |    F* B*    |
> > >   |----------------------------------|
> > >   | read safe |  F? B* |      -      |
> > >    ----------------------------------
> > >
> > > Where:
> > > F: check_usage_forwards
> > > B: check_usage_backwards
> > > *: check enabled by STRICT_READ_CHECKS
> > > ?: check enabled by the !dir condition
> > >
> > > From checking point of view, the special F? case does not make sense,
> > > whereas it perhaps is made for peroformance concern. As later patch will
> > > address this issue, remove this exception, which makes the checks
> > > consistent later.
> > >
> > > With STRICT_READ_CHECKS = 1 which is default, there is no functional
> > > change.
> >
> > Oh man.. thinking required and it is way late.. anyway this whole read
> > stuff made me remember we had a patch set on readlocks last year.
> >
> >   https://lkml.kernel.org/r/20180411135110.9217-1-boqun.feng@gmail.com
> >
> > I remember reviewing that a few times and then it dropped on the floor,
> > probably because Spectre crap or something sucked up all my time again :/
> >
> > Sorry Boqun!
> 

That's all right. I was also too busy to send another spin...

> Oh man, I thought about the read-write lock stuff, but I didn't know
> Boqun's patch. Let me hurt my brain looking at that patch.
>

Yuyang,  a few about the status, I've changed a little on the algorithm, the
latest code is at 

          git://git.kernel.org/pub/scm/linux/kernel/git/boqun/linux.git   arr-rfc-wip

but unfortunately, I haven't got time to rework the comments and documents, so
be aware of this inconsistency.

Feel free to ask me any question, and I will try to send out a fresh spin in next month.

Regards,
Boqun

Re: [PATCH 24/28] locking/lockdep: Remove !dir in lock irq usage check

[Peter Zijlstra]

On Thu, Apr 25, 2019 at 10:03:36PM +0200, Peter Zijlstra wrote:
> On Wed, Apr 24, 2019 at 06:19:30PM +0800, Yuyang Du wrote:
> > In mark_lock_irq(), the following checks are performed:
> > 
> >    ----------------------------------
> >   |   ->      | unsafe | read unsafe |
> >   |----------------------------------|
> >   | safe      |  F  B  |    F* B*    |
> >   |----------------------------------|
> >   | read safe |  F? B* |      -      |
> >    ----------------------------------
> > 
> > Where:
> > F: check_usage_forwards
> > B: check_usage_backwards
> > *: check enabled by STRICT_READ_CHECKS
> > ?: check enabled by the !dir condition
> > 
> > From checking point of view, the special F? case does not make sense,
> > whereas it perhaps is made for peroformance concern. As later patch will
> > address this issue, remove this exception, which makes the checks
> > consistent later.
> > 
> > With STRICT_READ_CHECKS = 1 which is default, there is no functional
> > change.
> 
> Oh man.. thinking required and it is way late.. anyway this whole read
> stuff made me remember we had a patch set on readlocks last year.
> 
>   https://lkml.kernel.org/r/20180411135110.9217-1-boqun.feng@gmail.com
> 
> I remember reviewing that a few times and then it dropped on the floor,
> probably because Spectre crap or something sucked up all my time again :/

So if we look at Boqun's patches (as posted, I haven't looked at his
github, but I'm assuming this hasn't changed with the 'Shared' state),
we'll find he'll only does either 1 backward or 1 foward search (which
is already an improvement over the current state).

His mark_lock_irq() looks like:

static int
mark_lock_irq(struct task_struct *curr, struct *held_lock *this,
		enum lock_usage_bit new_bit)
{
	int excl_bit = exclusive_bit(new_bit);

+       if (new_bit & 2) {
+               /*
+                * mark ENABLED has to look backwards -- to ensure no dependee
+                * has USED_IN state, which, again, would allow recursion
+                * deadlocks.
+                */
+               if (!check_usage_backwards(curr, this, new_bit, excl_bit))
			return 0;
+       } else {
+               /*
+                * mark USED_IN has to look forwards -- to ensure no dependency
+                * has ENABLED state, which would allow recursion deadlocks.
+                */
+               if (!check_usage_forwards(curr, this, new_bit, excl_bit))
			return 0;
	}

	return 1;
}

Where '& 2' would read '& LOCK_USAGE_DIR_MASK' in the current code.

Now, I'm thinking you're proposing to replace the backward search for
USED_IN/safe with your reachable-safe state, which, if done on his
'strong' links, should still work.

That is; I _think_ the two patch-sets are not in conceptual conflict.

Of course; I could have missed something; I've just read both patchsets
again, and it's a bit much :-)

[PATCH 25/28] locking/lockdep: Implement new IRQ usage checking algorithm

[Yuyang Du]

The read-write locks make checks much more complex, we elaborate on all
possible cases in the following two tables, one for marking a new IRQ
usage and the other for adding a new dependency.

When reasoning all the cases in checking, these two factors are taken
into consideration. Firstly, if a lock is irqsafe or irqsafe read, it is
not necessary to mark it as reachable from any locks. Secondly, IRQ safe
for read lock is weak compared to IRQ safe lock in terms of checking IRQ
usage rules violation. As a result, if a lock is reachable from safe
lock, it is not necesary to record reachable from safe read lock.

1. Marking a new IRQ usage for a lock:

   ------------------------------------------------------------------------------
  |   dir    | new usage |  reachable  |     bad usage     |   check   |  reach  |
  |------------------------------------------------------------------------------|
  |          |           |             |   safe -> unsafe  |   done    |   done  |
  |          |           |    safe     |-----------------------------------------|
  |          |           |             | safe -> unsafe rd |   done    |   done  |
  |          |           |-------------------------------------------------------|
  |          |           |             |   safe -> unsafe  |   done    |   safe  |
  |          |   safe    |   safe rd   |-----------------------------------------|
  |          |           |             | safe -> unsafe rd | unsafe rd |   safe  |
  | forward  |           |-------------------------------------------------------|
  |          |           |             |   safe -> unsafe  |  unsafe   |   safe  |
  |          |           | unreachable |-----------------------------------------|
  |          |           |             | safe -> unsafe rd | unsafe rd |   safe  |
  |          |-------------------------------------------------------------------|
  |          |           |    safe     | safe rd -> unsafe |   done    |   done  |
  |          |           |-------------------------------------------------------|
  |          |  safe rd  |   safe rd   | safe rd -> unsafe |   done    |   done  |
  |          |           |-------------------------------------------------------|
  |          |           | unreachable | safe rd -> unsafe |  unsafe   | safe rd |
  |------------------------------------------------------------------------------|
  |          |           |             |   safe -> unsafe  | violation |    -    |
  |          |           |    safe     |-----------------------------------------|
  |          |           |             | safe rd -> unsafe | violation |    -    |
  |          |           |-------------------------------------------------------|
  |          |           |             |   safe -> unsafe  | violation |    -    |
  |          |   unsafe  |   safe rd   |-----------------------------------------|
  |          |           |             | safe rd -> unsafe | violation |    -    |
  | backward |           |-------------------------------------------------------|
  |          |           |             |   safe -> unsafe  |   done    |    -    |
  |          |           | unreachable |-----------------------------------------|
  |          |           |             | safe rd -> unsafe |   done    |    -    |
  |          |-------------------------------------------------------------------|
  |          |           |    safe     | safe -> unsafe rd | violation |    -    |
  |          |           |-------------------------------------------------------|
  |          | unsafe rd |   safe rd   | safe -> unsafe rd |   done    |    -    |
  |          |           |-------------------------------------------------------|
  |          |           | unreachable | safe -> unsafe rd |   done    |    -    |
   ------------------------------------------------------------------------------

where:
 - column "reachable" means whether the lock is previously reachable from
   safe or safe read locks
 - column "check" means what lock to search forward or nothing needs to be done
 - column "reach" means what lock to mark as reachable from this new usage

2. Adding a new dependency from prev to next:

   -----------------------------------------------------------------------------
  |           prev         |    next     |        check        |       reach    |
  |-----------------------------------------------------------------------------|
  |           safe         |    safe     |        done         |       done     |
  |-----------------------------------------------------------------------------|
  |           safe         |  safe rd    |       [unsafe]      |       safe     |
  |-----------------------------------------------------------------------------|
  |           safe         |   unsafe    |      violation      |       done     |
  |-----------------------------------------------------------------------------|
  |           safe         |  unsafe rd  |       unsafe        |       safe     |
  |-----------------------------------------------------------------------------|
  |           safe         |    used     |       unsafe        |       safe     |
  |-----------------------------------------------------------------------------|
  |        safe read       |    safe     |        done         |       done     |
  |-----------------------------------------------------------------------------|
  |        safe read       |   safe rd   |        done         |       done     |
  |-----------------------------------------------------------------------------|
  |        safe read       |   unsafe    |      violation      |       done     |
  |-----------------------------------------------------------------------------|
  |        safe read       |  unsafe rd  |       unsafe        |     safe rd    |
  |-----------------------------------------------------------------------------|
  |        safe read       |    used     |       unsafe        |     safe rd    |
  |-----------------------------------------------------------------------------|
  |         unsafe         |     -       |        done         |       done     |
  |-----------------------------------------------------------------------------|
  |       unsafe read      |     -       |        done         |     safe rd?   |
  |-----------------------------------------------------------------------------|
  |          used and safe reachable     |        the same as prev is safe      |
  |-----------------------------------------------------------------------------|
  |          used safe reachable rd      |     the same as prev is safe read    |
  |-----------------------------------------------------------------------------|
  |        just used       |                      done                          |
   -----------------------------------------------------------------------------

where:
 - column "prev" indicate the prev lock's usage type
 - column "next" indicate the next lock's usage type
 - columns "check" and "reach" mean the same as above table
 - "(rd)" means the same for the read case
 - "[unsafe]" means the check is not necessary
 - "safe rd?" means it is needed to mark reachable for the read case

It is worth noting that when adding a new dependency or marking a new
usage bit, if a conflicting usage is found, we don't continue to search
the graph for more conflicting usages or for marking reachable nodes,
which results in that we can miss more conflicting usages, however, the
missed ones are related to the one we found but have different
dependency paths. This bahavior is exactly the same as the current
checks.

It is also worth noting that because an irqsafe lock can be zapped
unfortunately, if it once reached a lock, it might need to be replaced
after zapping. To do so, we have to do a full forward graph traverse for
all the IRQ safe locks. This is heavy, but consider that irqsafe locks
are not too many and that zapping locks does not happen on a regular
basis, this should be affordable.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c           | 494 +++++++++++++++++++++++--------------
 kernel/locking/lockdep_internals.h |  15 +-
 kernel/locking/lockdep_proc.c      |   1 -
 3 files changed, 314 insertions(+), 196 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 2f24028..06ae87f 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1365,6 +1365,33 @@ static inline int get_lock_depth(struct lock_list *child)
 	return depth;
 }
 
+static void
+mark_safe_lock(bool reach, struct lock_class *lock, int index, int distance,
+	       struct lock_class *safe_lock)
+{
+	int read = index % 2;
+	int shift = LOCK_USAGE_CONTEXT_SHIFT * (index >> 1);
+	unsigned long usage = lock->usage_mask;
+	unsigned long safe_mask = LOCKF_USED_IN_HARDIRQ << shift,
+		      safe_read_mask = LOCKF_USED_IN_HARDIRQ_READ << shift;
+
+	if (!reach)
+		return;
+
+	/*
+	 * If a lock itself is irqsafe, it is unnecessary to set it is an
+	 * irqsafe reachable lock.
+	 */
+	if (usage & safe_mask || (read && (usage & safe_read_mask)))
+		return;
+
+	/* Check whether this new distance is shorter */
+	if (lock->irqsafe_distance[index] > distance) {
+		lock->irqsafe_lock[index] = safe_lock;
+		lock->irqsafe_distance[index] = distance;
+	}
+}
+
 /*
  * Return the forward or backward dependency list.
  *
@@ -1383,11 +1410,10 @@ static inline struct list_head *get_dep_list(struct lock_list *lock, int offset)
  * Forward- or backward-dependency search, used for both circular dependency
  * checking and hardirq-unsafe/softirq-unsafe checking.
  */
-static int __bfs(struct lock_list *source_entry,
-		 void *data,
+static int __bfs(struct lock_list *source_entry, void *data,
 		 int (*match)(struct lock_list *entry, void *data),
-		 struct lock_list **target_entry,
-		 int offset)
+		 struct lock_list **target_entry, int offset, int index,
+		 int distance, struct lock_class *safe_lock, bool reach)
 {
 	struct lock_list *entry;
 	struct lock_list *lock;
@@ -1395,6 +1421,8 @@ static int __bfs(struct lock_list *source_entry,
 	struct circular_queue *cq = &lock_cq;
 	int ret = 1;
 
+	mark_safe_lock(reach, source_entry->class, index, distance++, safe_lock);
+
 	if (match(source_entry, data)) {
 		*target_entry = source_entry;
 		ret = 0;
@@ -1422,6 +1450,10 @@ static int __bfs(struct lock_list *source_entry,
 		list_for_each_entry_rcu(entry, head, entry) {
 			if (!lock_accessed(entry)) {
 				unsigned int cq_depth;
+
+				mark_safe_lock(reach, entry->class, index,
+					       distance++, safe_lock);
+
 				mark_lock_accessed(entry, lock);
 				if (match(entry, data)) {
 					*target_entry = entry;
@@ -1443,23 +1475,15 @@ static int __bfs(struct lock_list *source_entry,
 	return ret;
 }
 
-static inline int __bfs_forwards(struct lock_list *src_entry,
-			void *data,
-			int (*match)(struct lock_list *entry, void *data),
-			struct lock_list **target_entry)
+static inline int __bfs_forwards(struct lock_list *src_entry, void *data,
+				 int (*match)(struct lock_list *entry, void *data),
+				 struct lock_list **target_entry, int index,
+				 int distance, struct lock_class *safe_lock,
+				 bool reach)
 {
 	return __bfs(src_entry, data, match, target_entry,
-		     offsetof(struct lock_class, locks_after));
-
-}
-
-static inline int __bfs_backwards(struct lock_list *src_entry,
-			void *data,
-			int (*match)(struct lock_list *entry, void *data),
-			struct lock_list **target_entry)
-{
-	return __bfs(src_entry, data, match, target_entry,
-		     offsetof(struct lock_class, locks_before));
+		     offsetof(struct lock_class, locks_after),
+		     index, distance, safe_lock, reach);
 
 }
 
@@ -1632,7 +1656,8 @@ static unsigned long __lockdep_count_forward_deps(struct lock_list *this)
 	unsigned long  count = 0;
 	struct lock_list *uninitialized_var(target_entry);
 
-	__bfs_forwards(this, (void *)&count, noop_count, &target_entry);
+	__bfs_forwards(this, (void *)&count, noop_count, &target_entry,
+		       0, 0, NULL, false);
 
 	return count;
 }
@@ -1653,33 +1678,6 @@ unsigned long lockdep_count_forward_deps(struct lock_class *class)
 	return ret;
 }
 
-static unsigned long __lockdep_count_backward_deps(struct lock_list *this)
-{
-	unsigned long  count = 0;
-	struct lock_list *uninitialized_var(target_entry);
-
-	__bfs_backwards(this, (void *)&count, noop_count, &target_entry);
-
-	return count;
-}
-
-unsigned long lockdep_count_backward_deps(struct lock_class *class)
-{
-	unsigned long ret, flags;
-	struct lock_list this;
-
-	this.parent = NULL;
-	this.class = class;
-
-	raw_local_irq_save(flags);
-	arch_spin_lock(&lockdep_lock);
-	ret = __lockdep_count_backward_deps(&this);
-	arch_spin_unlock(&lockdep_lock);
-	raw_local_irq_restore(flags);
-
-	return ret;
-}
-
 /*
  * Check that the dependency graph starting at <src> can lead to
  * <target> or not. Print an error and return 0 if it does.
@@ -1691,7 +1689,7 @@ unsigned long lockdep_count_backward_deps(struct lock_class *class)
 	int ret;
 
 	ret = __bfs_forwards(src_entry, (void *)target, class_equal,
-			     target_entry);
+			     target_entry, 0, 0, NULL, false);
 
 	if (unlikely(ret < 0))
 		print_bfs_bug(ret);
@@ -1768,11 +1766,11 @@ static inline int usage_match(struct lock_list *entry, void *mask)
 	return entry->class->usage_mask & *(unsigned long *)mask;
 }
 
-
-
 /*
- * Find a node in the forwards-direction dependency sub-graph starting
- * at @root->class that matches @bit.
+ * Find a node in the forward-direction dependency sub-graph starting
+ * at @root->class that matches @mask, meanwhile update
+ * irqsafe_lock[@index] and irqsafe_distance[@index] of the reached
+ * locks if this path is shorter.
  *
  * Return 0 if such a node exists in the subgraph, and put that node
  * into *@target_entry.
@@ -1782,38 +1780,19 @@ static inline int usage_match(struct lock_list *entry, void *mask)
  */
 static int
 find_usage_forwards(struct lock_list *root, unsigned long usage_mask,
-			struct lock_list **target_entry)
+		    struct lock_list **target_entry, int index, int distance,
+		    struct lock_class *safe_lock)
 {
-	int result;
+	int ret;
 
 	debug_atomic_inc(nr_find_usage_forwards_checks);
 
-	result = __bfs_forwards(root, &usage_mask, usage_match, target_entry);
-
-	return result;
-}
-
-/*
- * Find a node in the backwards-direction dependency sub-graph starting
- * at @root->class that matches @bit.
- *
- * Return 0 if such a node exists in the subgraph, and put that node
- * into *@target_entry.
- *
- * Return 1 otherwise and keep *@target_entry unchanged.
- * Return <0 on error.
- */
-static int
-find_usage_backwards(struct lock_list *root, unsigned long usage_mask,
-			struct lock_list **target_entry)
-{
-	int result;
-
-	debug_atomic_inc(nr_find_usage_backwards_checks);
-
-	result = __bfs_backwards(root, &usage_mask, usage_match, target_entry);
+	ret = __bfs_forwards(root, (void *)&usage_mask, usage_match, target_entry,
+			     index, distance, safe_lock, true);
+	if (ret < 0)
+		print_bfs_bug(ret);
 
-	return result;
+	return ret;
 }
 
 static void print_lock_class_header(struct lock_class *class, int depth)
@@ -1999,44 +1978,6 @@ static void print_lock_class_header(struct lock_class *class, int depth)
 	dump_stack();
 }
 
-static int
-check_usage(struct task_struct *curr, struct held_lock *prev,
-	    struct held_lock *next, enum lock_usage_bit bit_backwards,
-	    enum lock_usage_bit bit_forwards, const char *irqclass)
-{
-	int ret;
-	struct lock_list this, that;
-	struct lock_list *uninitialized_var(target_entry);
-	struct lock_list *uninitialized_var(target_entry1);
-
-	this.parent = NULL;
-
-	this.class = hlock_class(prev);
-	ret = find_usage_backwards(&this, lock_flag(bit_backwards), &target_entry);
-	if (ret < 0) {
-		print_bfs_bug(ret);
-		return 0;
-	}
-	if (ret == 1)
-		return ret;
-
-	that.parent = NULL;
-	that.class = hlock_class(next);
-	ret = find_usage_forwards(&that, lock_flag(bit_forwards), &target_entry1);
-	if (ret < 0) {
-		print_bfs_bug(ret);
-		return 0;
-	}
-	if (ret == 1)
-		return ret;
-
-	print_bad_irq_dependency(curr, &this, &that,
-				 target_entry, target_entry1,
-				 prev, next,
-				 bit_backwards, bit_forwards, irqclass);
-	return 0;
-}
-
 static const char *state_names[] = {
 #define LOCKDEP_STATE(__STATE) \
 	__stringify(__STATE),
@@ -2070,30 +2011,131 @@ static int exclusive_bit(int new_bit)
 	return state | (dir ^ LOCK_USAGE_DIR_MASK);
 }
 
-static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
-			   struct held_lock *next, enum lock_usage_bit bit)
+static int
+check_usage(struct task_struct *curr, struct held_lock *prev,
+	    struct held_lock *next, unsigned long mask,
+	    enum lock_usage_bit bit_backwards, enum lock_usage_bit bit_forwards,
+	    int index, int distance, struct lock_class *safe_lock)
 {
-	/*
-	 * Prove that the new dependency does not connect a hardirq-safe
-	 * lock with a hardirq-unsafe lock - to achieve this we search
-	 * the backwards-subgraph starting at <prev>, and the
-	 * forwards-subgraph starting at <next>:
-	 */
-	if (!check_usage(curr, prev, next, bit,
-			   exclusive_bit(bit), state_name(bit)))
-		return 0;
+	int ret;
+	struct lock_list this, that;
+	struct lock_list *uninitialized_var(target_entry);
+	struct lock_list *uninitialized_var(target_entry1);
+	const char *irqclass = state_name(bit_backwards);
 
-	bit++; /* _READ */
+	that.parent = NULL;
+	that.class = hlock_class(next);
+	ret = find_usage_forwards(&that, mask, &target_entry1, index, distance,
+				  safe_lock);
+	if (ret != 0)
+		return ret;
 
 	/*
-	 * Prove that the new dependency does not connect a hardirq-safe-read
-	 * lock with a hardirq-unsafe lock - to achieve this we search
-	 * the backwards-subgraph starting at <prev>, and the
-	 * forwards-subgraph starting at <next>:
+	 * To print out the dependencies of this conflicting usage, we
+	 * have to do a forward search from the IRQ safe or IRQ safe
+	 * read lock to this lock; the chance we are here is very small.
 	 */
-	if (!check_usage(curr, prev, next, bit,
-			   exclusive_bit(bit), state_name(bit)))
+	this.parent = NULL;
+	this.class = safe_lock;
+	/* If prev is the target, the search will return right away anyway */
+	ret = check_path(hlock_class(prev), &this, &target_entry);
+	if (unlikely(ret != 0)) {
+		if (unlikely(ret == 1)) {
+			/* Surprisingly the path does not exist */
+			if (!debug_locks_off_graph_unlock())
+				return 0;
+			WARN_ON_ONCE(1);
+		}
 		return 0;
+	}
+
+	print_bad_irq_dependency(curr, &this, &that,
+				 target_entry, target_entry1,
+				 prev, next,
+				 bit_backwards, bit_forwards, irqclass);
+	return 0;
+}
+
+static inline bool safe_usage(struct lock_class *lock, unsigned long mask,
+			      int index, int *distance,
+			      struct lock_class **safe_lock)
+{
+	unsigned long usage = lock->usage_mask;
+
+	if (usage & mask)
+		return true;
+
+	if (lock->irqsafe_distance[index] < INT_MAX) {
+		WARN_ON_ONCE(!lock->irqsafe_lock[index]);
+
+		if (distance)
+			*distance += lock->irqsafe_distance[index];
+		if (safe_lock)
+			*safe_lock = lock->irqsafe_lock[index];
+		return true;
+	}
+
+	return false;
+}
+
+/*
+ * Prove that the new dependency does not connect:
+ *  -      irq-safe lock -> irq-unsafe lock
+ *  - irq-safe read lock -> irq-unsafe lock
+ *  -      irq-safe lock -> irq-unsafe read lock
+ *
+ *  Return 0 if it does or 1 if not.
+ */
+static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
+			   struct held_lock *next, int context)
+{
+	int index = context << 1, distance = 1, distance_read = 1;
+	int shift = LOCK_USAGE_CONTEXT_SHIFT * context;
+	int safe_bit = LOCK_USED_IN_HARDIRQ + shift;
+	int safe_read_bit = LOCK_USED_IN_HARDIRQ_READ + shift;
+	int unsafe_bit = LOCK_ENABLED_HARDIRQ + shift;
+	struct lock_class *safe_lock = hlock_class(prev);
+	struct lock_class *safe_lock_read = hlock_class(prev);
+	unsigned long safe_mask = LOCKF_USED_IN_HARDIRQ << shift;
+	unsigned long safe_read_mask = LOCKF_USED_IN_HARDIRQ_READ << shift;
+	unsigned long unsafe_mask = LOCKF_ENABLED_HARDIRQ << shift;
+	unsigned long unsafe_read_mask = LOCKF_ENABLED_HARDIRQ_READ << shift;
+	bool prev_safe = safe_usage(hlock_class(prev), safe_mask, index,
+				    &distance, &safe_lock);
+	bool prev_safe_read = safe_usage(hlock_class(prev), safe_read_mask,
+					 index+1, &distance_read, &safe_lock_read);
+	bool next_safe = safe_usage(hlock_class(next), safe_mask, index, NULL, NULL);
+	bool next_safe_read = safe_usage(hlock_class(next), safe_read_mask,
+					 index+1, NULL, NULL);
+
+	if (hlock_class(prev)->usage_mask & unsafe_mask)
+		return 1;
+
+	if (hlock_class(prev)->usage_mask & unsafe_read_mask)
+		goto check_read;
+
+	if (prev_safe) {
+		if (next_safe)
+			return 1;
+		/*
+		 * If next_usage & unsafe_mask, a conflicting usage is
+		 * found already, but we check to print the bad
+		 * dependency.
+		 */
+		return check_usage(curr, prev, next, unsafe_mask, safe_bit,
+				   unsafe_bit, index, distance, safe_lock);
+	}
+
+check_read:
+	if (prev_safe_read) {
+		if (next_safe || next_safe_read)
+			return 1;
+
+		/* Ditto */
+		return check_usage(curr, prev, next, unsafe_mask,
+				   safe_read_bit, unsafe_bit, index + 1,
+				   distance_read, safe_lock_read);
+	}
 
 	return 1;
 }
@@ -2103,7 +2145,7 @@ static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
 		struct held_lock *next)
 {
 #define LOCKDEP_STATE(__STATE)						\
-	if (!check_irq_usage(curr, prev, next, LOCK_USED_IN_##__STATE))	\
+	if (!check_irq_usage(curr, prev, next, LOCK_CONTEXT_##__STATE))	\
 		return 0;
 #include "lockdep_states.h"
 #undef LOCKDEP_STATE
@@ -2340,12 +2382,6 @@ static inline void inc_chains(void)
 	if (!ret)
 		return 0;
 
-	ret = add_lock_to_list(hlock_class(prev), hlock_class(next),
-			       &hlock_class(next)->locks_before,
-			       next->acquire_ip, distance, &trace);
-	if (!ret)
-		return 0;
-
 	return 2;
 }
 
@@ -2995,30 +3031,54 @@ static void print_usage_bug_scenario(struct held_lock *lock)
 	dump_stack();
 }
 
-/*
- * Prove that in the forwards-direction subgraph starting at <this>
- * there is no lock matching <mask>:
- */
+#define STRICT_READ_CHECKS	1
+
 static int
 check_usage_forwards(struct task_struct *curr, struct held_lock *this,
-		     enum lock_usage_bit bit, const char *irqclass)
+		     enum lock_usage_bit new_bit, enum lock_usage_bit excl_bit)
 {
-	int ret;
+	int ret, context = new_bit >> 2;
+	int index = new_bit >> 1; /* new_bit is USED_IN */
+	int shift = LOCK_USAGE_CONTEXT_SHIFT * context;
+	int read = new_bit & LOCK_USAGE_READ_MASK;
 	struct lock_list root;
 	struct lock_list *uninitialized_var(target_entry);
+	unsigned long mask = LOCKF_ENABLED_HARDIRQ << shift;
+	const char *irqclass = state_name(new_bit & ~LOCK_USAGE_READ_MASK);
 
+	if (!read) {
+		/*
+		 * This lock was just marked USED_IN and hence becomes a
+		 * new IRQ safe lock. If it was already reachable from
+		 * an IRQ safe lock, the locks forward the graph have
+		 * been proven no conflicting usage.
+		 */
+		if (hlock_class(this)->irqsafe_lock[index])
+			return 1;
+		if (STRICT_READ_CHECKS)
+			mask |= (LOCKF_ENABLED_HARDIRQ_READ << shift);
+	} else {
+		if (!STRICT_READ_CHECKS)
+			return 1;
+		if (hlock_class(this)->irqsafe_lock[index])
+			return 1;
+		if (hlock_class(this)->irqsafe_lock[++index])
+			return 1;
+	}
+
+	/*
+	 * If it was unreachable from an IRQ safe lock before, a forward
+	 * search for IRQ unsafe lock is needed.
+	 */
 	root.parent = NULL;
 	root.class = hlock_class(this);
-	ret = find_usage_forwards(&root, lock_flag(bit), &target_entry);
-	if (ret < 0) {
-		print_bfs_bug(ret);
-		return 0;
-	}
-	if (ret == 1)
+	ret = find_usage_forwards(&root, mask, &target_entry, index, 0,
+				  hlock_class(this));
+	if (ret != 0)
 		return ret;
 
-	print_irq_inversion_bug(curr, &root, target_entry,
-				this, 1, irqclass);
+	print_irq_inversion_bug(curr, &root, target_entry, this, 1, irqclass);
+
 	return 0;
 }
 
@@ -3028,24 +3088,47 @@ static void print_usage_bug_scenario(struct held_lock *lock)
  */
 static int
 check_usage_backwards(struct task_struct *curr, struct held_lock *this,
-		      enum lock_usage_bit bit, const char *irqclass)
+		      enum lock_usage_bit new_bit, enum lock_usage_bit excl_bit)
 {
-	int ret;
+	int ret, index = (new_bit >> 2) << 1; /* new_bit is ENABLED */
+	int read = new_bit & LOCK_USAGE_READ_MASK;
 	struct lock_list root;
 	struct lock_list *uninitialized_var(target_entry);
+	const char *irqclass = state_name(new_bit & ~LOCK_USAGE_READ_MASK);
 
+	/*
+	 * This lock was just marked ENABLED and hence becomes a new IRQ
+	 * unsafe lock. If it was proven unreachable from an IRQ safe lock
+	 * before, there is no conflicting usage.
+	 */
+	if (!hlock_class(this)->irqsafe_lock[index]) {
+		if (!hlock_class(this)->irqsafe_lock[++index] || read)
+			return 1;
+	}
+
+	/*
+	 * This lock was proven reachable from an IRQ safe lock before,
+	 * a conflicting usage is thus found.
+	 *
+	 * To print out the dependencies of this conflicting usage, we
+	 * have to do a forward search from the IRQ safe lock to this
+	 * lock; the chance we are here is very small.
+	 */
 	root.parent = NULL;
-	root.class = hlock_class(this);
-	ret = find_usage_backwards(&root, lock_flag(bit), &target_entry);
-	if (ret < 0) {
-		print_bfs_bug(ret);
+	root.class = hlock_class(this)->irqsafe_lock[index];
+	ret = check_path(hlock_class(this), &root, &target_entry);
+	if (unlikely(ret != 0)) {
+		if (unlikely(ret == 1)) {
+			/* Surprisingly the path does not exist */
+			if (!debug_locks_off_graph_unlock())
+				return 0;
+			WARN_ON_ONCE(1);
+		}
 		return 0;
 	}
-	if (ret == 1)
-		return ret;
 
-	print_irq_inversion_bug(curr, &root, target_entry,
-				this, 0, irqclass);
+	print_irq_inversion_bug(curr, target_entry, &root, this, 0, irqclass);
+
 	return 0;
 }
 
@@ -3082,8 +3165,6 @@ static int SOFTIRQ_verbose(struct lock_class *class)
 	return 0;
 }
 
-#define STRICT_READ_CHECKS	1
-
 static int (*state_verbose_f[])(struct lock_class *class) = {
 #define LOCKDEP_STATE(__STATE) \
 	__STATE##_verbose,
@@ -3098,7 +3179,8 @@ static inline int state_verbose(enum lock_usage_bit bit,
 }
 
 typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
-			     enum lock_usage_bit bit, const char *name);
+			     enum lock_usage_bit new_bit,
+			     enum lock_usage_bit excl_bit);
 
 static int
 mark_lock_irq(struct task_struct *curr, struct held_lock *this,
@@ -3114,7 +3196,7 @@ typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
 	 * has ENABLED state, which would allow recursion deadlocks.
 	 *
 	 * mark ENABLED has to look backwards -- to ensure no dependee
-	 * has USED_IN state, which, again, would allow  recursion deadlocks.
+	 * has USED_IN state, which, again, would allow recursion deadlocks.
 	 */
 	check_usage_f usage = dir ?
 		check_usage_backwards : check_usage_forwards;
@@ -3145,27 +3227,17 @@ typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
 	if (!valid_state(curr, this, new_bit, excl_bit))
 		return 0;
 
+	if (!read && !valid_state(curr, this, new_bit,
+				  excl_bit + LOCK_USAGE_READ_MASK))
+		return 0;
+
 	/*
 	 * Validate that the lock dependencies don't have conflicting usage
 	 * states.
 	 */
-	if ((!read || STRICT_READ_CHECKS) &&
-			!usage(curr, this, excl_bit, state_name(new_bit & ~LOCK_USAGE_READ_MASK)))
+	if (!usage(curr, this, new_bit, excl_bit))
 		return 0;
 
-	/*
-	 * Check for read in write conflicts
-	 */
-	if (!read) {
-		if (!valid_state(curr, this, new_bit, excl_bit + LOCK_USAGE_READ_MASK))
-			return 0;
-
-		if (STRICT_READ_CHECKS &&
-			!usage(curr, this, excl_bit + LOCK_USAGE_READ_MASK,
-				state_name(new_bit + LOCK_USAGE_READ_MASK)))
-			return 0;
-	}
-
 	if (state_verbose(new_bit, lock))
 		return 2;
 
@@ -4673,16 +4745,60 @@ static void remove_class_from_lock_chains(struct pending_free *pf,
 static inline void remove_irqsafe_lock_bitmap(struct lock_class *class)
 {
 #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
+	int i, j, count = 0;
+	DECLARE_BITMAP(irqsafe_locks, 4);
 	unsigned long usage = class->usage_mask;
+	unsigned long *bitmaps[4] = {
+		lock_classes_hardirq_safe,
+		lock_classes_hardirq_safe_read,
+		lock_classes_softirq_safe,
+		lock_classes_softirq_safe_read
+	};
 
-	if (usage & LOCKF_USED_IN_HARDIRQ)
+	if (usage & LOCKF_USED_IN_HARDIRQ) {
 		__clear_bit(class - lock_classes, lock_classes_hardirq_safe);
-	if (usage & LOCKF_USED_IN_HARDIRQ_READ)
+		__set_bit(0, irqsafe_locks);
+	}
+	if (usage & LOCKF_USED_IN_HARDIRQ_READ) {
 		__clear_bit(class - lock_classes, lock_classes_hardirq_safe_read);
-	if (usage & LOCKF_USED_IN_SOFTIRQ)
+		__set_bit(1, irqsafe_locks);
+	}
+	if (usage & LOCKF_USED_IN_SOFTIRQ) {
 		__clear_bit(class - lock_classes, lock_classes_softirq_safe);
-	if (usage & LOCKF_USED_IN_SOFTIRQ_READ)
+		__set_bit(2, irqsafe_locks);
+	}
+	if (usage & LOCKF_USED_IN_SOFTIRQ_READ) {
 		__clear_bit(class - lock_classes, lock_classes_softirq_safe_read);
+		__set_bit(3, irqsafe_locks);
+	}
+
+	if (bitmap_empty(irqsafe_locks, 4))
+		return;
+
+	for_each_set_bit(i, lock_classes_in_use, ARRAY_SIZE(lock_classes)) {
+		for_each_set_bit(j, irqsafe_locks, 4) {
+			if (lock_classes[i].irqsafe_lock[j] == class) {
+				lock_classes[i].irqsafe_lock[j] = NULL;
+				lock_classes[i].irqsafe_distance[j] = INT_MAX;
+				count++;
+			}
+		}
+	}
+
+	if (!count)
+		return;
+
+	for_each_set_bit(j, irqsafe_locks, 4) {
+		for_each_set_bit(i, bitmaps[j], ARRAY_SIZE(lock_classes)) {
+			struct lock_list root;
+			struct lock_list *uninitialized_var(target_entry);
+			struct lock_class *lock = lock_classes + i;
+
+			root.parent = NULL;
+			root.class = lock;
+			find_usage_forwards(&root, 0, &target_entry, j, 0, lock);
+		}
+	}
 #endif
 }
 
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 2b3ffd4..30d021b 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -25,6 +25,7 @@ enum lock_usage_bit {
 #define LOCK_USAGE_READ_MASK 1
 #define LOCK_USAGE_DIR_MASK  2
 #define LOCK_USAGE_STATE_MASK (~(LOCK_USAGE_READ_MASK | LOCK_USAGE_DIR_MASK))
+#define LOCK_USAGE_CONTEXT_SHIFT   4
 
 /*
  * Usage-state bitmasks:
@@ -66,6 +67,14 @@ enum {
 	0;
 #undef LOCKDEP_STATE
 
+enum {
+#define LOCKDEP_STATE(__STATE)		\
+	LOCK_CONTEXT_##__STATE,
+#include "lockdep_states.h"
+#undef LOCKDEP_STATE
+	LOCK_CONTEXTS
+};
+
 /*
  * CONFIG_LOCKDEP_SMALL is defined for sparc. Sparc requires .text,
  * .data and .bss to fit in required 32MB limit for the kernel. With
@@ -131,18 +140,12 @@ extern void get_usage_chars(struct lock_class *class,
 
 #ifdef CONFIG_PROVE_LOCKING
 extern unsigned long lockdep_count_forward_deps(struct lock_class *);
-extern unsigned long lockdep_count_backward_deps(struct lock_class *);
 #else
 static inline unsigned long
 lockdep_count_forward_deps(struct lock_class *class)
 {
 	return 0;
 }
-static inline unsigned long
-lockdep_count_backward_deps(struct lock_class *class)
-{
-	return 0;
-}
 #endif
 
 #ifdef CONFIG_DEBUG_LOCKDEP
diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
index 9c49ec6..7b5fe77 100644
--- a/kernel/locking/lockdep_proc.c
+++ b/kernel/locking/lockdep_proc.c
@@ -72,7 +72,6 @@ static int l_show(struct seq_file *m, void *v)
 #endif
 #ifdef CONFIG_PROVE_LOCKING
 	seq_printf(m, " FD:%5ld", lockdep_count_forward_deps(class));
-	seq_printf(m, " BD:%5ld", lockdep_count_backward_deps(class));
 #endif
 
 	get_usage_chars(class, usage);
-- 
1.8.3.1

[PATCH 26/28] locking/lockdep: Remove __bfs

[Yuyang Du]

Since there is no need for backward dependecy searching, remove this
extra function layer.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 40 +++++++---------------------------------
 1 file changed, 7 insertions(+), 33 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 06ae87f..acaa3b3 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1393,27 +1393,13 @@ static inline int get_lock_depth(struct lock_list *child)
 }
 
 /*
- * Return the forward or backward dependency list.
- *
- * @lock:   the lock_list to get its class's dependency list
- * @offset: the offset to struct lock_class to determine whether it is
- *          locks_after or locks_before
- */
-static inline struct list_head *get_dep_list(struct lock_list *lock, int offset)
-{
-	void *lock_class = lock->class;
-
-	return lock_class + offset;
-}
-
-/*
- * Forward- or backward-dependency search, used for both circular dependency
+ * Forward-dependency search, used for both circular dependency
  * checking and hardirq-unsafe/softirq-unsafe checking.
  */
-static int __bfs(struct lock_list *source_entry, void *data,
-		 int (*match)(struct lock_list *entry, void *data),
-		 struct lock_list **target_entry, int offset, int index,
-		 int distance, struct lock_class *safe_lock, bool reach)
+static int __bfs_forwards(struct lock_list *source_entry, void *data,
+			  int (*match)(struct lock_list *entry, void *data),
+			  struct lock_list **target_entry, int index,
+			  int distance, struct lock_class *safe_lock, bool reach)
 {
 	struct lock_list *entry;
 	struct lock_list *lock;
@@ -1429,7 +1415,7 @@ static int __bfs(struct lock_list *source_entry, void *data,
 		goto exit;
 	}
 
-	head = get_dep_list(source_entry, offset);
+	head = &source_entry->class->locks_after;
 	if (list_empty(head))
 		goto exit;
 
@@ -1443,7 +1429,7 @@ static int __bfs(struct lock_list *source_entry, void *data,
 			goto exit;
 		}
 
-		head = get_dep_list(lock, offset);
+		head = &lock->class->locks_after;
 
 		DEBUG_LOCKS_WARN_ON(!irqs_disabled());
 
@@ -1475,18 +1461,6 @@ static int __bfs(struct lock_list *source_entry, void *data,
 	return ret;
 }
 
-static inline int __bfs_forwards(struct lock_list *src_entry, void *data,
-				 int (*match)(struct lock_list *entry, void *data),
-				 struct lock_list **target_entry, int index,
-				 int distance, struct lock_class *safe_lock,
-				 bool reach)
-{
-	return __bfs(src_entry, data, match, target_entry,
-		     offsetof(struct lock_class, locks_after),
-		     index, distance, safe_lock, reach);
-
-}
-
 static void print_lock_trace(struct lock_trace *trace, unsigned int spaces)
 {
 	unsigned long *entries = stack_trace + trace->offset;
-- 
1.8.3.1

Re: [PATCH 26/28] locking/lockdep: Remove __bfs

[Peter Zijlstra]

On Wed, Apr 24, 2019 at 06:19:32PM +0800, Yuyang Du wrote:
> Since there is no need for backward dependecy searching, remove this
> extra function layer.

OK, so $subject confused the heck out of me, I thought you were going to
remove the whole bfs machinery. May I suggest retaining
__bfs_backwards() in the previous patch (which I'm _waay_ to tired for
to look at now) and calling this patch: "Remove __bfs_backwards()".

Re: [PATCH 26/28] locking/lockdep: Remove __bfs

[Yuyang Du]

Thanks for review.

On Fri, 26 Apr 2019 at 04:07, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Wed, Apr 24, 2019 at 06:19:32PM +0800, Yuyang Du wrote:
> > Since there is no need for backward dependecy searching, remove this
> > extra function layer.
>
> OK, so $subject confused the heck out of me, I thought you were going to
> remove the whole bfs machinery. May I suggest retaining
> __bfs_backwards() in the previous patch (which I'm _waay_ to tired for
> to look at now) and calling this patch: "Remove __bfs_backwards()".

Sure thing.

[PATCH 27/28] locking/lockdep: Remove locks_before

[Yuyang Du]

Since the backward dependencies are always empty, remove the
locks_before field in lock_class struct and its occurrences.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 include/linux/lockdep.h  |  5 ++---
 kernel/locking/lockdep.c | 15 +++------------
 2 files changed, 5 insertions(+), 15 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 0e209b8..d0a587c 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -97,10 +97,9 @@ struct lock_class {
 
 	/*
 	 * These fields represent a directed graph of lock dependencies,
-	 * to every node we attach a list of "forward" and a list of
-	 * "backward" graph nodes.
+	 * to every node we attach a list of "forward" graph nodes.
 	 */
-	struct list_head		locks_after, locks_before;
+	struct list_head		locks_after;
 
 	struct lockdep_subclass_key	*key;
 	unsigned int			subclass;
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index acaa3b3..fa6611e 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -823,8 +823,7 @@ static bool in_list(struct list_head *e, struct list_head *h)
 }
 
 /*
- * Check whether entry @e occurs in any of the locks_after or locks_before
- * lists.
+ * Check whether entry @e occurs in any of the locks_after list.
  */
 static bool in_any_class_list(struct list_head *e)
 {
@@ -833,8 +832,7 @@ static bool in_any_class_list(struct list_head *e)
 
 	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
 		class = &lock_classes[i];
-		if (in_list(e, &class->locks_after) ||
-		    in_list(e, &class->locks_before))
+		if (in_list(e, &class->locks_after))
 			return true;
 	}
 	return false;
@@ -922,8 +920,6 @@ static bool __check_data_structures(void)
 	/* Check whether all classes have valid lock lists. */
 	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
 		class = &lock_classes[i];
-		if (!class_lock_list_valid(class, &class->locks_before))
-			return false;
 		if (!class_lock_list_valid(class, &class->locks_after))
 			return false;
 	}
@@ -1021,7 +1017,6 @@ static void init_data_structures_once(void)
 	for (i = 0; i < ARRAY_SIZE(lock_classes); i++) {
 		list_add_tail(&lock_classes[i].lock_entry, &free_lock_classes);
 		INIT_LIST_HEAD(&lock_classes[i].locks_after);
-		INIT_LIST_HEAD(&lock_classes[i].locks_before);
 	}
 }
 
@@ -1151,7 +1146,6 @@ static bool is_dynamic_key(const struct lock_class_key *key)
 	class->key = key;
 	class->name = lock->name;
 	class->subclass = subclass;
-	WARN_ON_ONCE(!list_empty(&class->locks_before));
 	WARN_ON_ONCE(!list_empty(&class->locks_after));
 	class->name_version = count_matching_names(class);
 	for (i = 0; i < ARRAY_SIZE(class->irqsafe_distance); i++)
@@ -4798,8 +4792,7 @@ static void zap_class(struct pending_free *pf, struct lock_class *class)
 		nr_list_entries--;
 		list_del_rcu(&entry->entry);
 	}
-	if (list_empty(&class->locks_after) &&
-	    list_empty(&class->locks_before)) {
+	if (list_empty(&class->locks_after)) {
 		list_move_tail(&class->lock_entry, &pf->zapped);
 		hlist_del_rcu(&class->hash_entry);
 		WRITE_ONCE(class->key, NULL);
@@ -4822,11 +4815,9 @@ static void reinit_class(struct lock_class *class)
 
 	WARN_ON_ONCE(!class->lock_entry.next);
 	WARN_ON_ONCE(!list_empty(&class->locks_after));
-	WARN_ON_ONCE(!list_empty(&class->locks_before));
 	memset(p + offset, 0, sizeof(*class) - offset);
 	WARN_ON_ONCE(!class->lock_entry.next);
 	WARN_ON_ONCE(!list_empty(&class->locks_after));
-	WARN_ON_ONCE(!list_empty(&class->locks_before));
 }
 
 static inline int within(const void *addr, void *start, unsigned long size)
-- 
1.8.3.1

[PATCH 28/28] locking/lockdep: Reduce lock_list_entries by half

[Yuyang Du]

The forward and backward dependencies consume the same number of
list_entries. Since backward dependencies are removed, the max number of
list_entries can be halved safely: MAX_LOCKDEP_ENTRIES /= 2, which goes
from 16384 to 8192 or 32768 to 16384.

Besides memory space reduction, the performance gain is also promising
with this new IRQ usage checking algorithm. We briefly show the
performance improvement on a simple workload: Linux kernel build (i.e.,
make clean; reboot; make vmlinux -j8). It is expected that for complex
real-world workloads with heavier lock usage and bigger dependency
graph, the benefits should be more.

Results:

------
Before
------

direct dependencies:                  6900 [max: 32768]
max bfs queue depth:                   272
find-mask forwards checks:            2875
find-mask backwards checks:          50229

-----
After
-----

direct dependencies:                  3444 [max: 16384]   ( -  50 % )
max bfs queue depth:                   223                ( -  18 % )
find-mask forwards checks:             370                ( -  87 % )
find-mask backwards checks:              0                ( - 100 % )

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep_internals.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 30d021b..3b4b3dd 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -92,11 +92,11 @@ enum {
  * table (if it's not there yet), and we check it for lock order
  * conflicts and deadlocks.
  */
-#define MAX_LOCKDEP_ENTRIES	16384UL
+#define MAX_LOCKDEP_ENTRIES	8194UL
 #define MAX_LOCKDEP_CHAINS_BITS	15
 #define MAX_STACK_TRACE_ENTRIES	262144UL
 #else
-#define MAX_LOCKDEP_ENTRIES	32768UL
+#define MAX_LOCKDEP_ENTRIES	16384UL
 
 #define MAX_LOCKDEP_CHAINS_BITS	16
 
-- 
1.8.3.1

Re: [PATCH 00/28] Optimize IRQ usage checks and other small bits

[Peter Zijlstra]

On Wed, Apr 24, 2019 at 06:19:06PM +0800, Yuyang Du wrote:
> Yuyang Du (28):
>   locking/lockdep: Change all print_*() return type to void
>   locking/lockdep: Add description and explanation in lockdep design doc
>   locking/lockdep: Adjust lock usage bit character checks
>   locking/lockdep: Remove useless conditional macro
>   locking/lockdep: Print the right depth for chain key colission
>   locking/lockdep: Update obsolete struct field description
>   locking/lockdep: Use lockdep_init_task for task initiation
>     consistently
>   locking/lockdep: Define INITIAL_CHAIN_KEY for chain keys to start with
>   locking/lockdep: Change the range of class_idx in held_lock struct
>   locking/lockdep: Remove unused argument in validate_chain() and
>     check_deadlock()
>   locking/lockdep: Update comment
>   locking/lockdep: Change type of the element field in circular_queue
>   locking/lockdep: Change the return type of __cq_dequeue()
>   locking/lockdep: Avoid constant checks in __bfs by using offset
>     reference
>   locking/lockdep: Update comments on dependency search
>   locking/lockdep: Add explanation to lock usage rules in lockdep design
>     doc
>   locking/lockdep: Remove redundant argument in check_deadlock
>   locking/lockdep: Remove unused argument in __lock_release

Those look really good (but don't readily apply to tip/locking/core) now
let me try and look at the real changes..

>   locking/lockdep: Optimize irq usage check when marking lock usage bit
>   locking/lockdep: Refactorize check_noncircular and check_redundant
>   locking/lockdep: Consolidate lock usage bit initialization
>   locking/lockdep: Adjust new bit cases in mark_lock
>   locking/lockdep: Update irqsafe lock bitmaps
>   locking/lockdep: Remove !dir in lock irq usage check
>   locking/lockdep: Implement new IRQ usage checking algorithm
>   locking/lockdep: Remove __bfs
>   locking/lockdep: Remove locks_before
>   locking/lockdep: Reduce lock_list_entries by half

Re: [PATCH 00/28] Optimize IRQ usage checks and other small bits

[Yuyang Du]

Thanks for review.

On Fri, 26 Apr 2019 at 02:56, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Wed, Apr 24, 2019 at 06:19:06PM +0800, Yuyang Du wrote:
> > Yuyang Du (28):
> >   locking/lockdep: Change all print_*() return type to void
> >   locking/lockdep: Add description and explanation in lockdep design doc
> >   locking/lockdep: Adjust lock usage bit character checks
> >   locking/lockdep: Remove useless conditional macro
> >   locking/lockdep: Print the right depth for chain key colission
> >   locking/lockdep: Update obsolete struct field description
> >   locking/lockdep: Use lockdep_init_task for task initiation
> >     consistently
> >   locking/lockdep: Define INITIAL_CHAIN_KEY for chain keys to start with
> >   locking/lockdep: Change the range of class_idx in held_lock struct
> >   locking/lockdep: Remove unused argument in validate_chain() and
> >     check_deadlock()
> >   locking/lockdep: Update comment
> >   locking/lockdep: Change type of the element field in circular_queue
> >   locking/lockdep: Change the return type of __cq_dequeue()
> >   locking/lockdep: Avoid constant checks in __bfs by using offset
> >     reference
> >   locking/lockdep: Update comments on dependency search
> >   locking/lockdep: Add explanation to lock usage rules in lockdep design
> >     doc
> >   locking/lockdep: Remove redundant argument in check_deadlock
> >   locking/lockdep: Remove unused argument in __lock_release
>
> Those look really good (but don't readily apply to tip/locking/core) now
> let me try and look at the real changes..

Swell.