[RFC PATCH 02/12] locking/lockdep: Add a new terminal lock type

[Waiman Long]

A terminal lock is a lock where further locking or unlocking on another
lock is not allowed. IOW, no forward dependency is permitted.

With such a restriction in place, we don't really need to do a full
validation of the lock chain involving a terminal lock.  Instead,
we just check if there is any further locking or unlocking on another
lock when a terminal lock is being held.

Only spinlocks which are acquired by the _irq or _irqsave variants
or in IRQ disabled context should be classified as terminal locks.

By adding this new lock type, we can save entries in lock_chains[],
chain_hlocks[], list_entries[] and stack_trace[]. By marking suitable
locks as terminal, we reduce the chance of overflowing those tables
allowing them to focus on locks that can have both forward and backward
dependencies.

Signed-off-by: Waiman Long <longman@xxxxxxxxxx>
---
 include/linux/lockdep.h            | 13 ++++++++++-
 kernel/locking/lockdep.c           | 44 ++++++++++++++++++++++++++++++++++----
 kernel/locking/lockdep_internals.h |  5 +++++
 kernel/locking/lockdep_proc.c      | 11 ++++++++--
 4 files changed, 66 insertions(+), 7 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 18f9607..c5ff8c5 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -143,9 +143,16 @@ struct lock_class_stats {
 
 /*
  * Lockdep class flags
+ *
  * 1) LOCKDEP_FLAG_NOVALIDATE: No full validation, just simple checks.
+ * 2) LOCKDEP_FLAG_TERMINAL: This is a terminal lock where lock/unlock on
+ *    another lock within its critical section is not allowed.
  */
 #define LOCKDEP_FLAG_NOVALIDATE 	(1 << 0)
+#define LOCKDEP_FLAG_TERMINAL		(1 << 1)
+
+#define LOCKDEP_NOCHECK_FLAGS		(LOCKDEP_FLAG_NOVALIDATE |\
+					 LOCKDEP_FLAG_TERMINAL)
 
 /*
  * Map the lock object (the lock instance) to the lock-class object.
@@ -263,6 +270,7 @@ struct held_lock {
 	unsigned int hardirqs_off:1;
 	unsigned int references:12;					/* 32 bits */
 	unsigned int pin_count;
+	unsigned int flags;
 };
 
 /*
@@ -304,6 +312,8 @@ extern void lockdep_init_map(struct lockdep_map *lock, const char *name,
 
 #define lockdep_set_novalidate_class(lock) \
 	do { (lock)->dep_map.flags |= LOCKDEP_FLAG_NOVALIDATE; } while (0)
+#define lockdep_set_terminal_class(lock) \
+	do { (lock)->dep_map.flags |= LOCKDEP_FLAG_TERMINAL; } while (0)
 
 /*
  * Compare locking classes
@@ -419,7 +429,8 @@ static inline void lockdep_on(void)
 		do { (void)(key); } while (0)
 #define lockdep_set_subclass(lock, sub)		do { } while (0)
 
-#define lockdep_set_novalidate_class(lock) do { } while (0)
+#define lockdep_set_novalidate_class(lock)	do { } while (0)
+#define lockdep_set_terminal_class(lock)	do { } while (0)
 
 /*
  * We don't define lockdep_match_class() and lockdep_match_key() for !LOCKDEP
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 493b567..02631a0 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3020,6 +3020,16 @@ static inline int separate_irq_context(struct task_struct *curr,
 
 #endif /* defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING) */
 
+static int lock_is_terminal(struct lockdep_map *lock)
+{
+	return flags_is_terminal(lock->flags);
+}
+
+static int hlock_is_terminal(struct held_lock *hlock)
+{
+	return flags_is_terminal(hlock->flags);
+}
+
 /*
  * Mark a lock with a usage bit, and validate the state transition:
  */
@@ -3047,7 +3057,11 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 
 	hlock_class(this)->usage_mask |= new_mask;
 
-	if (!save_trace(hlock_class(this)->usage_traces + new_bit))
+	/*
+	 * We don't need to save the stack trace for terminal locks.
+	 */
+	if (!hlock_is_terminal(this) &&
+	    !save_trace(hlock_class(this)->usage_traces + new_bit))
 		return 0;
 
 	switch (new_bit) {
@@ -3215,9 +3229,6 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	if (unlikely(!debug_locks))
 		return 0;
 
-	if (!prove_locking || (lock->flags & LOCKDEP_FLAG_NOVALIDATE))
-		check = 0;
-
 	if (subclass < NR_LOCKDEP_CACHING_CLASSES)
 		class = lock->class_cache[subclass];
 	/*
@@ -3229,6 +3240,9 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 			return 0;
 	}
 
+	if (!prove_locking || (class->flags & LOCKDEP_NOCHECK_FLAGS))
+		check = 0;
+
 	debug_class_ops_inc(class);
 
 	if (very_verbose(class)) {
@@ -3255,6 +3269,13 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 
 	if (depth) {
 		hlock = curr->held_locks + depth - 1;
+
+		/*
+		 * Warn if the previous lock is a terminal lock.
+		 */
+		if (DEBUG_LOCKS_WARN_ON(hlock_is_terminal(hlock)))
+			return 0;
+
 		if (hlock->class_idx == class_idx && nest_lock) {
 			if (hlock->references) {
 				/*
@@ -3294,6 +3315,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	hlock->holdtime_stamp = lockstat_clock();
 #endif
 	hlock->pin_count = pin_count;
+	hlock->flags = class->flags;
 
 	if (check && !mark_irqflags(curr, hlock))
 		return 0;
@@ -3636,6 +3658,14 @@ static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
 	if (i == depth-1)
 		return 1;
 
+	/*
+	 * Unlock of an outer lock is not allowed while holding a terminal
+	 * lock.
+	 */
+	hlock = curr->held_locks + depth - 1;
+	if (DEBUG_LOCKS_WARN_ON(hlock_is_terminal(hlock)))
+		return 0;
+
 	if (reacquire_held_locks(curr, depth, i + 1))
 		return 0;
 
@@ -4093,6 +4123,12 @@ void lock_acquired(struct lockdep_map *lock, unsigned long ip)
 		return;
 
 	raw_local_irq_save(flags);
+
+	/*
+	 * A terminal lock should only be used with IRQ disabled.
+	 */
+	DEBUG_LOCKS_WARN_ON(lock_is_terminal(lock) &&
+			    !irqs_disabled_flags(flags));
 	check_flags(flags);
 	current->lockdep_recursion = 1;
 	__lock_acquired(lock, ip);
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 88c847a..271fba8 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -212,3 +212,8 @@ static inline unsigned long debug_class_ops_read(struct lock_class *class)
 # define debug_atomic_read(ptr)		0
 # define debug_class_ops_inc(ptr)	do { } while (0)
 #endif
+
+static inline unsigned int flags_is_terminal(unsigned int flags)
+{
+	return flags & LOCKDEP_FLAG_TERMINAL;
+}
diff --git a/kernel/locking/lockdep_proc.c b/kernel/locking/lockdep_proc.c
index 3d31f9b..37fbd41 100644
--- a/kernel/locking/lockdep_proc.c
+++ b/kernel/locking/lockdep_proc.c
@@ -78,7 +78,10 @@ static int l_show(struct seq_file *m, void *v)
 	get_usage_chars(class, usage);
 	seq_printf(m, " %s", usage);
 
-	seq_printf(m, ": ");
+	/*
+	 * Print terminal lock status
+	 */
+	seq_printf(m, "%c: ", flags_is_terminal(class->flags) ? 'T' : ' ');
 	print_name(m, class);
 	seq_puts(m, "\n");
 
@@ -208,7 +211,7 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
 		      nr_irq_read_safe = 0, nr_irq_read_unsafe = 0,
 		      nr_softirq_read_safe = 0, nr_softirq_read_unsafe = 0,
 		      nr_hardirq_read_safe = 0, nr_hardirq_read_unsafe = 0,
-		      sum_forward_deps = 0;
+		      nr_nocheck = 0, sum_forward_deps = 0;
 
 	list_for_each_entry(class, &all_lock_classes, lock_entry) {
 
@@ -240,6 +243,8 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
 			nr_hardirq_read_safe++;
 		if (class->usage_mask & LOCKF_ENABLED_HARDIRQ_READ)
 			nr_hardirq_read_unsafe++;
+		if (class->flags & LOCKDEP_NOCHECK_FLAGS)
+			nr_nocheck++;
 
 #ifdef CONFIG_PROVE_LOCKING
 		sum_forward_deps += lockdep_count_forward_deps(class);
@@ -318,6 +323,8 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
 			nr_uncategorized);
 	seq_printf(m, " unused locks:                  %11lu\n",
 			nr_unused);
+	seq_printf(m, " unchecked locks:               %11lu\n",
+			nr_nocheck);
 	seq_printf(m, " max locking depth:             %11u\n",
 			max_lockdep_depth);
 #ifdef CONFIG_PROVE_LOCKING
-- 
1.8.3.1