[RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[Waiman Long]

The purpose of this patchset is to add a new class of locks called
terminal locks and converts some of the low level raw or regular
spinlocks to terminal locks. A terminal lock does not have forward
dependency and it won't allow a lock or unlock operation on another
lock. Two level nesting of terminal locks is allowed, though.

Only spinlocks that are acquired with the _irq/_irqsave variants or
acquired in an IRQ disabled context should be classified as terminal
locks.

Because of the restrictions on terminal locks, we can do simple checks on
them without using the lockdep lock validation machinery. The advantages
of making these changes are as follows:

 1) The lockdep check will be faster for terminal locks without using
    the lock validation code.
 2) It saves table entries used by the validation code and hence make
    it harder to overflow those tables.

In fact, it is possible to overflow some of the tables by running
a variety of different workloads on a debug kernel. I have seen bug
reports about exhausting MAX_LOCKDEP_KEYS, MAX_LOCKDEP_ENTRIES and
MAX_STACK_TRACE_ENTRIES. This patch will help to reduce the chance
of overflowing some of the tables.

Performance wise, there was no statistically significant difference in
performanace when doing a parallel kernel build on a debug kernel.

Below were selected output lines from the lockdep_stats files of the
patched and unpatched kernels after bootup and running parallel kernel
builds.

  Item                     Unpatched kernel  Patched kernel  % Change
  ----                     ----------------  --------------  --------
  direct dependencies           9732             8994          -7.6%
  dependency chains            18776            17033          -9.3%
  dependency chain hlocks      76044            68419         -10.0%
  stack-trace entries         110403           104341          -5.5%

There were some reductions in the size of the lockdep tables. They were
not significant, but it is still a good start to rein in the number of
entries in those tables to make it harder to overflow them.

Waiman Long (12):
  locking/lockdep: Rework lockdep_set_novalidate_class()
  locking/lockdep: Add a new terminal lock type
  locking/lockdep: Add DEFINE_TERMINAL_SPINLOCK() and related macros
  printk: Make logbuf_lock a terminal lock
  debugobjects: Mark pool_lock as a terminal lock
  debugobjects: Move printk out of db lock critical sections
  locking/lockdep: Add support for nested terminal locks
  debugobjects: Make object hash locks nested terminal locks
  lib/stackdepot: Make depot_lock a terminal spinlock
  locking/rwsem: Mark rwsem.wait_lock as a terminal lock
  cgroup: Mark the rstat percpu lock as terminal
  mm/kasan: Make quarantine_lock a terminal lock

 include/linux/lockdep.h            | 34 +++++++++++++++---
 include/linux/rwsem.h              | 11 +++++-
 include/linux/spinlock_types.h     | 34 ++++++++++++------
 kernel/cgroup/rstat.c              |  9 +++--
 kernel/locking/lockdep.c           | 67 ++++++++++++++++++++++++++++++------
 kernel/locking/lockdep_internals.h |  5 +++
 kernel/locking/lockdep_proc.c      | 11 ++++--
 kernel/locking/rwsem-xadd.c        |  1 +
 kernel/printk/printk.c             |  2 +-
 kernel/printk/printk_safe.c        |  2 +-
 lib/debugobjects.c                 | 70 ++++++++++++++++++++++++++------------
 lib/stackdepot.c                   |  2 +-
 mm/kasan/quarantine.c              |  2 +-
 13 files changed, 195 insertions(+), 55 deletions(-)

-- 
1.8.3.1

[RFC PATCH 01/12] locking/lockdep: Rework lockdep_set_novalidate_class()

[Waiman Long]

The current lockdep_set_novalidate_class() implementation is like
a hack. It assigns a special class key for that lock and calls
lockdep_init_map() twice.

This patch changes the implementation to make it more general so that
it can be used by other special lock class types. A new "type" field
is added to both the lockdep_map and lock_class structures.

The new field can now be used to designate a lock and a class object
as novalidate. The lockdep_set_novalidate_class() call, however, should
be called before lock initialization which calls lockdep_init_map().

Signed-off-by: Waiman Long <longman@redhat.com>
---
 include/linux/lockdep.h  | 14 +++++++++++---
 kernel/locking/lockdep.c | 14 +++++++-------
 2 files changed, 18 insertions(+), 10 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 1fd82ff..18f9607 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -58,8 +58,6 @@ struct lock_class_key {
 	struct lockdep_subclass_key	subkeys[MAX_LOCKDEP_SUBCLASSES];
 };
 
-extern struct lock_class_key __lockdep_no_validate__;
-
 #define LOCKSTAT_POINTS		4
 
 /*
@@ -102,6 +100,8 @@ struct lock_class {
 	int				name_version;
 	const char			*name;
 
+	unsigned int			flags;
+
 #ifdef CONFIG_LOCK_STAT
 	unsigned long			contention_point[LOCKSTAT_POINTS];
 	unsigned long			contending_point[LOCKSTAT_POINTS];
@@ -142,6 +142,12 @@ struct lock_class_stats {
 #endif
 
 /*
+ * Lockdep class flags
+ * 1) LOCKDEP_FLAG_NOVALIDATE: No full validation, just simple checks.
+ */
+#define LOCKDEP_FLAG_NOVALIDATE 	(1 << 0)
+
+/*
  * Map the lock object (the lock instance) to the lock-class object.
  * This is embedded into specific lock instances:
  */
@@ -149,6 +155,7 @@ struct lockdep_map {
 	struct lock_class_key		*key;
 	struct lock_class		*class_cache[NR_LOCKDEP_CACHING_CLASSES];
 	const char			*name;
+	unsigned int			flags;
 #ifdef CONFIG_LOCK_STAT
 	int				cpu;
 	unsigned long			ip;
@@ -296,7 +303,8 @@ extern void lockdep_init_map(struct lockdep_map *lock, const char *name,
 				 (lock)->dep_map.key, sub)
 
 #define lockdep_set_novalidate_class(lock) \
-	lockdep_set_class_and_name(lock, &__lockdep_no_validate__, #lock)
+	do { (lock)->dep_map.flags |= LOCKDEP_FLAG_NOVALIDATE; } while (0)
+
 /*
  * Compare locking classes
  */
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 1efada2..493b567 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -692,10 +692,11 @@ static int count_matching_names(struct lock_class *new_class)
 	hlist_for_each_entry_rcu(class, hash_head, hash_entry) {
 		if (class->key == key) {
 			/*
-			 * Huh! same key, different name? Did someone trample
-			 * on some memory? We're most confused.
+			 * Huh! same key, different name or flags? Did someone
+			 * trample on some memory? We're most confused.
 			 */
-			WARN_ON_ONCE(class->name != lock->name);
+			WARN_ON_ONCE((class->name  != lock->name) ||
+				     (class->flags != lock->flags));
 			return class;
 		}
 	}
@@ -788,6 +789,7 @@ static bool assign_lock_key(struct lockdep_map *lock)
 	debug_atomic_inc(nr_unused_locks);
 	class->key = key;
 	class->name = lock->name;
+	class->flags = lock->flags;
 	class->subclass = subclass;
 	INIT_LIST_HEAD(&class->lock_entry);
 	INIT_LIST_HEAD(&class->locks_before);
@@ -3108,6 +3110,7 @@ static void __lockdep_init_map(struct lockdep_map *lock, const char *name,
 		return;
 	}
 
+	lock->flags = 0;
 	lock->name = name;
 
 	/*
@@ -3152,9 +3155,6 @@ void lockdep_init_map(struct lockdep_map *lock, const char *name,
 }
 EXPORT_SYMBOL_GPL(lockdep_init_map);
 
-struct lock_class_key __lockdep_no_validate__;
-EXPORT_SYMBOL_GPL(__lockdep_no_validate__);
-
 static int
 print_lock_nested_lock_not_held(struct task_struct *curr,
 				struct held_lock *hlock,
@@ -3215,7 +3215,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	if (unlikely(!debug_locks))
 		return 0;
 
-	if (!prove_locking || lock->key == &__lockdep_no_validate__)
+	if (!prove_locking || (lock->flags & LOCKDEP_FLAG_NOVALIDATE))
 		check = 0;
 
 	if (subclass < NR_LOCKDEP_CACHING_CLASSES)
-- 
1.8.3.1

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

[RFC PATCH 03/12] locking/lockdep: Add DEFINE_TERMINAL_SPINLOCK() and related macros

[Waiman Long]

Add new DEFINE_RAW_TERMINAL_SPINLOCK() and DEFINE_TERMINAL_SPINLOCK()
macro to define a raw terminal spinlock and a terminal spinlock.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 include/linux/spinlock_types.h | 34 +++++++++++++++++++++++-----------
 kernel/printk/printk_safe.c    |  2 +-
 2 files changed, 24 insertions(+), 12 deletions(-)

diff --git a/include/linux/spinlock_types.h b/include/linux/spinlock_types.h
index 24b4e6f..6a8086e 100644
--- a/include/linux/spinlock_types.h
+++ b/include/linux/spinlock_types.h
@@ -33,9 +33,10 @@
 #define SPINLOCK_OWNER_INIT	((void *)-1L)
 
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
-# define SPIN_DEP_MAP_INIT(lockname)	.dep_map = { .name = #lockname }
+# define SPIN_DEP_MAP_INIT(lockname, f) .dep_map = { .name = #lockname, \
+						     .flags = f }
 #else
-# define SPIN_DEP_MAP_INIT(lockname)
+# define SPIN_DEP_MAP_INIT(lockname, f)
 #endif
 
 #ifdef CONFIG_DEBUG_SPINLOCK
@@ -47,16 +48,22 @@
 # define SPIN_DEBUG_INIT(lockname)
 #endif
 
-#define __RAW_SPIN_LOCK_INITIALIZER(lockname)	\
-	{					\
-	.raw_lock = __ARCH_SPIN_LOCK_UNLOCKED,	\
-	SPIN_DEBUG_INIT(lockname)		\
-	SPIN_DEP_MAP_INIT(lockname) }
+#define __RAW_SPIN_LOCK_INITIALIZER(lockname, f)	\
+	{						\
+	.raw_lock = __ARCH_SPIN_LOCK_UNLOCKED,		\
+	SPIN_DEBUG_INIT(lockname)			\
+	SPIN_DEP_MAP_INIT(lockname, f) }
 
 #define __RAW_SPIN_LOCK_UNLOCKED(lockname)	\
-	(raw_spinlock_t) __RAW_SPIN_LOCK_INITIALIZER(lockname)
+	(raw_spinlock_t) __RAW_SPIN_LOCK_INITIALIZER(lockname, 0)
+
+#define __RAW_TERMINAL_SPIN_LOCK_UNLOCKED(lockname)	\
+	(raw_spinlock_t) __RAW_SPIN_LOCK_INITIALIZER(lockname, \
+						     LOCKDEP_FLAG_TERMINAL)
 
 #define DEFINE_RAW_SPINLOCK(x)	raw_spinlock_t x = __RAW_SPIN_LOCK_UNLOCKED(x)
+#define DEFINE_RAW_TERMINAL_SPINLOCK(x)	\
+		raw_spinlock_t x = __RAW_TERMINAL_SPIN_LOCK_UNLOCKED(x)
 
 typedef struct spinlock {
 	union {
@@ -72,13 +79,18 @@
 	};
 } spinlock_t;
 
-#define __SPIN_LOCK_INITIALIZER(lockname) \
-	{ { .rlock = __RAW_SPIN_LOCK_INITIALIZER(lockname) } }
+#define __SPIN_LOCK_INITIALIZER(lockname, f) \
+	{ { .rlock = __RAW_SPIN_LOCK_INITIALIZER(lockname, f) } }
 
 #define __SPIN_LOCK_UNLOCKED(lockname) \
-	(spinlock_t ) __SPIN_LOCK_INITIALIZER(lockname)
+	(spinlock_t) __SPIN_LOCK_INITIALIZER(lockname, 0)
+
+#define __TERMINAL_SPIN_LOCK_UNLOCKED(lockname) \
+	(spinlock_t) __SPIN_LOCK_INITIALIZER(lockname, LOCKDEP_FLAG_TERMINAL)
 
 #define DEFINE_SPINLOCK(x)	spinlock_t x = __SPIN_LOCK_UNLOCKED(x)
+#define DEFINE_TERMINAL_SPINLOCK(x) \
+				spinlock_t x = __TERMINAL_SPIN_LOCK_UNLOCKED(x)
 
 #include <linux/rwlock_types.h>
 
diff --git a/kernel/printk/printk_safe.c b/kernel/printk/printk_safe.c
index 0913b4d..8ff1033 100644
--- a/kernel/printk/printk_safe.c
+++ b/kernel/printk/printk_safe.c
@@ -192,7 +192,7 @@ static void report_message_lost(struct printk_safe_seq_buf *s)
 static void __printk_safe_flush(struct irq_work *work)
 {
 	static raw_spinlock_t read_lock =
-		__RAW_SPIN_LOCK_INITIALIZER(read_lock);
+		__RAW_SPIN_LOCK_UNLOCKED(read_lock);
 	struct printk_safe_seq_buf *s =
 		container_of(work, struct printk_safe_seq_buf, work);
 	unsigned long flags;
-- 
1.8.3.1

[RFC PATCH 04/12] printk: Make logbuf_lock a terminal lock

[Waiman Long]

By making logbuf_lock a terminal lock, it reduces the performance
overhead when lockdep is enabled.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/printk/printk.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/printk/printk.c b/kernel/printk/printk.c
index 1b2a029..6b63fda 100644
--- a/kernel/printk/printk.c
+++ b/kernel/printk/printk.c
@@ -367,7 +367,7 @@ __packed __aligned(4)
  * within the scheduler's rq lock. It must be released before calling
  * console_unlock() or anything else that might wake up a process.
  */
-DEFINE_RAW_SPINLOCK(logbuf_lock);
+DEFINE_RAW_TERMINAL_SPINLOCK(logbuf_lock);
 
 /*
  * Helper macros to lock/unlock logbuf_lock and switch between
-- 
1.8.3.1

[RFC PATCH 05/12] debugobjects: Mark pool_lock as a terminal lock

[Waiman Long]

By marking the internal pool_lock as a terminal lock, lockdep will be
able to skip full validation to improve locking performance.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 lib/debugobjects.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/debugobjects.c b/lib/debugobjects.c
index 70935ed..403dd95 100644
--- a/lib/debugobjects.c
+++ b/lib/debugobjects.c
@@ -39,7 +39,7 @@ struct debug_bucket {
 
 static struct debug_obj		obj_static_pool[ODEBUG_POOL_SIZE] __initdata;
 
-static DEFINE_RAW_SPINLOCK(pool_lock);
+static DEFINE_RAW_TERMINAL_SPINLOCK(pool_lock);
 
 static HLIST_HEAD(obj_pool);
 static HLIST_HEAD(obj_to_free);
-- 
1.8.3.1

[RFC PATCH 06/12] debugobjects: Move printk out of db lock critical sections

[Waiman Long]

The db->lock is a raw spinlock and so the lock hold time is supposed
to be short. This will not be the case when printk() is being involved
in some of the critical sections. In order to avoid the long hold time,
in case some messages need to be printed, the debug_object_is_on_stack()
and debug_print_object() calls are now moved out of those critical
sections.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 lib/debugobjects.c | 61 +++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 42 insertions(+), 19 deletions(-)

diff --git a/lib/debugobjects.c b/lib/debugobjects.c
index 403dd95..4216d3d 100644
--- a/lib/debugobjects.c
+++ b/lib/debugobjects.c
@@ -376,6 +376,8 @@ static void debug_object_is_on_stack(void *addr, int onstack)
 	struct debug_bucket *db;
 	struct debug_obj *obj;
 	unsigned long flags;
+	bool debug_printobj = false;
+	bool debug_chkstack = false;
 
 	fill_pool();
 
@@ -392,7 +394,7 @@ static void debug_object_is_on_stack(void *addr, int onstack)
 			debug_objects_oom();
 			return;
 		}
-		debug_object_is_on_stack(addr, onstack);
+		debug_chkstack = true;
 	}
 
 	switch (obj->state) {
@@ -403,20 +405,25 @@ static void debug_object_is_on_stack(void *addr, int onstack)
 		break;
 
 	case ODEBUG_STATE_ACTIVE:
-		debug_print_object(obj, "init");
 		state = obj->state;
 		raw_spin_unlock_irqrestore(&db->lock, flags);
+		debug_print_object(obj, "init");
 		debug_object_fixup(descr->fixup_init, addr, state);
 		return;
 
 	case ODEBUG_STATE_DESTROYED:
-		debug_print_object(obj, "init");
+		debug_printobj = true;
 		break;
 	default:
 		break;
 	}
 
 	raw_spin_unlock_irqrestore(&db->lock, flags);
+	if (debug_chkstack)
+		debug_object_is_on_stack(addr, onstack);
+	if (debug_printobj)
+		debug_print_object(obj, "init");
+
 }
 
 /**
@@ -474,6 +481,8 @@ int debug_object_activate(void *addr, struct debug_obj_descr *descr)
 
 	obj = lookup_object(addr, db);
 	if (obj) {
+		bool debug_printobj = false;
+
 		switch (obj->state) {
 		case ODEBUG_STATE_INIT:
 		case ODEBUG_STATE_INACTIVE:
@@ -482,14 +491,14 @@ int debug_object_activate(void *addr, struct debug_obj_descr *descr)
 			break;
 
 		case ODEBUG_STATE_ACTIVE:
-			debug_print_object(obj, "activate");
 			state = obj->state;
 			raw_spin_unlock_irqrestore(&db->lock, flags);
+			debug_print_object(obj, "activate");
 			ret = debug_object_fixup(descr->fixup_activate, addr, state);
 			return ret ? 0 : -EINVAL;
 
 		case ODEBUG_STATE_DESTROYED:
-			debug_print_object(obj, "activate");
+			debug_printobj = true;
 			ret = -EINVAL;
 			break;
 		default:
@@ -497,10 +506,13 @@ int debug_object_activate(void *addr, struct debug_obj_descr *descr)
 			break;
 		}
 		raw_spin_unlock_irqrestore(&db->lock, flags);
+		if (debug_printobj)
+			debug_print_object(obj, "activate");
 		return ret;
 	}
 
 	raw_spin_unlock_irqrestore(&db->lock, flags);
+
 	/*
 	 * We are here when a static object is activated. We
 	 * let the type specific code confirm whether this is
@@ -532,6 +544,7 @@ void debug_object_deactivate(void *addr, struct debug_obj_descr *descr)
 	struct debug_bucket *db;
 	struct debug_obj *obj;
 	unsigned long flags;
+	bool debug_printobj = false;
 
 	if (!debug_objects_enabled)
 		return;
@@ -549,24 +562,27 @@ void debug_object_deactivate(void *addr, struct debug_obj_descr *descr)
 			if (!obj->astate)
 				obj->state = ODEBUG_STATE_INACTIVE;
 			else
-				debug_print_object(obj, "deactivate");
+				debug_printobj = true;
 			break;
 
 		case ODEBUG_STATE_DESTROYED:
-			debug_print_object(obj, "deactivate");
+			debug_printobj = true;
 			break;
 		default:
 			break;
 		}
-	} else {
+	}
+
+	raw_spin_unlock_irqrestore(&db->lock, flags);
+	if (!obj) {
 		struct debug_obj o = { .object = addr,
 				       .state = ODEBUG_STATE_NOTAVAILABLE,
 				       .descr = descr };
 
 		debug_print_object(&o, "deactivate");
+	} else if (debug_printobj) {
+		debug_print_object(obj, "deactivate");
 	}
-
-	raw_spin_unlock_irqrestore(&db->lock, flags);
 }
 EXPORT_SYMBOL_GPL(debug_object_deactivate);
 
@@ -581,6 +597,7 @@ void debug_object_destroy(void *addr, struct debug_obj_descr *descr)
 	struct debug_bucket *db;
 	struct debug_obj *obj;
 	unsigned long flags;
+	bool debug_printobj = false;
 
 	if (!debug_objects_enabled)
 		return;
@@ -600,20 +617,22 @@ void debug_object_destroy(void *addr, struct debug_obj_descr *descr)
 		obj->state = ODEBUG_STATE_DESTROYED;
 		break;
 	case ODEBUG_STATE_ACTIVE:
-		debug_print_object(obj, "destroy");
 		state = obj->state;
 		raw_spin_unlock_irqrestore(&db->lock, flags);
+		debug_print_object(obj, "destroy");
 		debug_object_fixup(descr->fixup_destroy, addr, state);
 		return;
 
 	case ODEBUG_STATE_DESTROYED:
-		debug_print_object(obj, "destroy");
+		debug_printobj = true;
 		break;
 	default:
 		break;
 	}
 out_unlock:
 	raw_spin_unlock_irqrestore(&db->lock, flags);
+	if (debug_printobj)
+		debug_print_object(obj, "destroy");
 }
 EXPORT_SYMBOL_GPL(debug_object_destroy);
 
@@ -642,9 +661,9 @@ void debug_object_free(void *addr, struct debug_obj_descr *descr)
 
 	switch (obj->state) {
 	case ODEBUG_STATE_ACTIVE:
-		debug_print_object(obj, "free");
 		state = obj->state;
 		raw_spin_unlock_irqrestore(&db->lock, flags);
+		debug_print_object(obj, "free");
 		debug_object_fixup(descr->fixup_free, addr, state);
 		return;
 	default:
@@ -717,6 +736,7 @@ void debug_object_assert_init(void *addr, struct debug_obj_descr *descr)
 	struct debug_bucket *db;
 	struct debug_obj *obj;
 	unsigned long flags;
+	bool debug_printobj = false;
 
 	if (!debug_objects_enabled)
 		return;
@@ -732,22 +752,25 @@ void debug_object_assert_init(void *addr, struct debug_obj_descr *descr)
 			if (obj->astate == expect)
 				obj->astate = next;
 			else
-				debug_print_object(obj, "active_state");
+				debug_printobj = true;
 			break;
 
 		default:
-			debug_print_object(obj, "active_state");
+			debug_printobj = true;
 			break;
 		}
-	} else {
+	}
+
+	raw_spin_unlock_irqrestore(&db->lock, flags);
+	if (!obj) {
 		struct debug_obj o = { .object = addr,
 				       .state = ODEBUG_STATE_NOTAVAILABLE,
 				       .descr = descr };
 
 		debug_print_object(&o, "active_state");
+	} else if (debug_printobj) {
+		debug_print_object(obj, "active_state");
 	}
-
-	raw_spin_unlock_irqrestore(&db->lock, flags);
 }
 EXPORT_SYMBOL_GPL(debug_object_active_state);
 
@@ -783,10 +806,10 @@ static void __debug_check_no_obj_freed(const void *address, unsigned long size)
 
 			switch (obj->state) {
 			case ODEBUG_STATE_ACTIVE:
-				debug_print_object(obj, "free");
 				descr = obj->descr;
 				state = obj->state;
 				raw_spin_unlock_irqrestore(&db->lock, flags);
+				debug_print_object(obj, "free");
 				debug_object_fixup(descr->fixup_free,
 						   (void *) oaddr, state);
 				goto repeat;
-- 
1.8.3.1

[RFC PATCH 07/12] locking/lockdep: Add support for nested terminal locks

[Waiman Long]

There are use cases where we want to allow 2-level nesting of one
terminal lock underneath another one. So the terminal lock type is now
extended to support a new nested terminal lock where it can allow the
acquisition of another regular terminal lock underneath it.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 include/linux/lockdep.h            |  9 ++++++++-
 kernel/locking/lockdep.c           | 15 +++++++++++++--
 kernel/locking/lockdep_internals.h |  2 +-
 3 files changed, 22 insertions(+), 4 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index c5ff8c5..ed4d177 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -147,12 +147,16 @@ struct lock_class_stats {
  * 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.
+ * 3) LOCKDEP_FLAG_TERMINAL_NESTED: This is a terminal lock that allows
+ *    one more regular terminal lock to be nested underneath it.
  */
 #define LOCKDEP_FLAG_NOVALIDATE 	(1 << 0)
 #define LOCKDEP_FLAG_TERMINAL		(1 << 1)
+#define LOCKDEP_FLAG_TERMINAL_NESTED	(1 << 2)
 
 #define LOCKDEP_NOCHECK_FLAGS		(LOCKDEP_FLAG_NOVALIDATE |\
-					 LOCKDEP_FLAG_TERMINAL)
+					 LOCKDEP_FLAG_TERMINAL   |\
+					 LOCKDEP_FLAG_TERMINAL_NESTED)
 
 /*
  * Map the lock object (the lock instance) to the lock-class object.
@@ -314,6 +318,8 @@ extern void lockdep_init_map(struct lockdep_map *lock, const char *name,
 	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)
+#define lockdep_set_terminal_nested_class(lock) \
+	do { (lock)->dep_map.flags |= LOCKDEP_FLAG_TERMINAL_NESTED; } while (0)
 
 /*
  * Compare locking classes
@@ -431,6 +437,7 @@ static inline void lockdep_on(void)
 
 #define lockdep_set_novalidate_class(lock)	do { } while (0)
 #define lockdep_set_terminal_class(lock)	do { } while (0)
+#define lockdep_set_terminal_nested_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 02631a0..2b75613 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3268,13 +3268,24 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	class_idx = class - lock_classes + 1;
 
 	if (depth) {
+		int prev_type;
+
 		hlock = curr->held_locks + depth - 1;
 
 		/*
-		 * Warn if the previous lock is a terminal lock.
+		 * Warn if the previous lock is a terminal lock or the
+		 * previous lock is a nested terminal lock and the current
+		 * one isn't a regular terminal lock.
 		 */
-		if (DEBUG_LOCKS_WARN_ON(hlock_is_terminal(hlock)))
+		prev_type = hlock_is_terminal(hlock);
+		if (DEBUG_LOCKS_WARN_ON((prev_type == LOCKDEP_FLAG_TERMINAL) ||
+			((prev_type == LOCKDEP_FLAG_TERMINAL_NESTED) &&
+			 (flags_is_terminal(class->flags) !=
+				LOCKDEP_FLAG_TERMINAL)))) {
+			pr_warn("Terminal lock error: prev lock = %s, curr lock = %s\n",
+				hlock->instance->name, class->name);
 			return 0;
+		}
 
 		if (hlock->class_idx == class_idx && nest_lock) {
 			if (hlock->references) {
diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
index 271fba8..abe646a 100644
--- a/kernel/locking/lockdep_internals.h
+++ b/kernel/locking/lockdep_internals.h
@@ -215,5 +215,5 @@ static inline unsigned long debug_class_ops_read(struct lock_class *class)
 
 static inline unsigned int flags_is_terminal(unsigned int flags)
 {
-	return flags & LOCKDEP_FLAG_TERMINAL;
+	return flags & (LOCKDEP_FLAG_TERMINAL|LOCKDEP_FLAG_TERMINAL_NESTED);
 }
-- 
1.8.3.1

[RFC PATCH 08/12] debugobjects: Make object hash locks nested terminal locks

[Waiman Long]

By making the object hash locks nested terminal locks, we can avoid
a bunch of unnecessary lockdep validations as well as saving space
in the lockdep tables.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 lib/debugobjects.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/lib/debugobjects.c b/lib/debugobjects.c
index 4216d3d..3182d15 100644
--- a/lib/debugobjects.c
+++ b/lib/debugobjects.c
@@ -1129,8 +1129,13 @@ void __init debug_objects_early_init(void)
 {
 	int i;
 
-	for (i = 0; i < ODEBUG_HASH_SIZE; i++)
+	/*
+	 * Make the obj_hash locks nested terminal locks.
+	 */
+	for (i = 0; i < ODEBUG_HASH_SIZE; i++) {
 		raw_spin_lock_init(&obj_hash[i].lock);
+		lockdep_set_terminal_nested_class(&obj_hash[i].lock);
+	}
 
 	for (i = 0; i < ODEBUG_POOL_SIZE; i++)
 		hlist_add_head(&obj_static_pool[i].node, &obj_pool);
-- 
1.8.3.1

[RFC PATCH 09/12] lib/stackdepot: Make depot_lock a terminal spinlock

[Waiman Long]

By defining depot_lock as a terminal spinlock, it reduces the
lockdep overhead when this lock is being used.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 lib/stackdepot.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/stackdepot.c b/lib/stackdepot.c
index e513459..fb17888 100644
--- a/lib/stackdepot.c
+++ b/lib/stackdepot.c
@@ -78,7 +78,7 @@ struct stack_record {
 static int depot_index;
 static int next_slab_inited;
 static size_t depot_offset;
-static DEFINE_SPINLOCK(depot_lock);
+static DEFINE_TERMINAL_SPINLOCK(depot_lock);
 
 static bool init_stack_slab(void **prealloc)
 {
-- 
1.8.3.1

[RFC PATCH 10/12] locking/rwsem: Mark rwsem.wait_lock as a terminal lock

[Waiman Long]

The wait_lock in a rwsem is always acquired with IRQ disabled. For the
rwsem-xadd.c implementation, no other lock will be called while holding
the wait_lock. So it satisfies the condition of being a terminal lock.
By marking it as terminal,  the lockdep overhead will be reduced.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 include/linux/rwsem.h       | 11 ++++++++++-
 kernel/locking/rwsem-xadd.c |  1 +
 2 files changed, 11 insertions(+), 1 deletion(-)

diff --git a/include/linux/rwsem.h b/include/linux/rwsem.h
index 67dbb57..a2a2385 100644
--- a/include/linux/rwsem.h
+++ b/include/linux/rwsem.h
@@ -77,16 +77,25 @@ static inline int rwsem_is_locked(struct rw_semaphore *sem)
 # define __RWSEM_DEP_MAP_INIT(lockname)
 #endif
 
+/*
+ * The wait_lock is marked as a terminal lock to reduce lockdep overhead
+ * when the rwsem-xadd.c is used. This is implied when
+ * CONFIG_RWSEM_SPIN_ON_OWNER is true. The rwsem-spinlock.c implementation
+ * allows calling wake_up_process() while holding the wait_lock. So it
+ * can't be marked as terminal in this case.
+ */
 #ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 #define __RWSEM_OPT_INIT(lockname) , .osq = OSQ_LOCK_UNLOCKED, .owner = NULL
+#define __RWSEM_WAIT_LOCK_INIT(x)	__RAW_TERMINAL_SPIN_LOCK_UNLOCKED(x)
 #else
 #define __RWSEM_OPT_INIT(lockname)
+#define __RWSEM_WAIT_LOCK_INIT(x)	__RAW_SPIN_LOCK_UNLOCKED(x)
 #endif
 
 #define __RWSEM_INITIALIZER(name)				\
 	{ __RWSEM_INIT_COUNT(name),				\
 	  .wait_list = LIST_HEAD_INIT((name).wait_list),	\
-	  .wait_lock = __RAW_SPIN_LOCK_UNLOCKED(name.wait_lock)	\
+	  .wait_lock = __RWSEM_WAIT_LOCK_INIT(name.wait_lock)	\
 	  __RWSEM_OPT_INIT(name)				\
 	  __RWSEM_DEP_MAP_INIT(name) }
 
diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
index 09b1800..3dbe593 100644
--- a/kernel/locking/rwsem-xadd.c
+++ b/kernel/locking/rwsem-xadd.c
@@ -85,6 +85,7 @@ void __init_rwsem(struct rw_semaphore *sem, const char *name,
 #endif
 	atomic_long_set(&sem->count, RWSEM_UNLOCKED_VALUE);
 	raw_spin_lock_init(&sem->wait_lock);
+	lockdep_set_terminal_class(&sem->wait_lock);
 	INIT_LIST_HEAD(&sem->wait_list);
 #ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 	sem->owner = NULL;
-- 
1.8.3.1

[RFC PATCH 11/12] cgroup: Mark the rstat percpu lock as terminal

[Waiman Long]

By classifying the cgroup rstat percpu locks as terminal locks, it
reduces the lockdep overhead when these locks are being used.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/cgroup/rstat.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/kernel/cgroup/rstat.c b/kernel/cgroup/rstat.c
index d503d1a..47f7ffb 100644
--- a/kernel/cgroup/rstat.c
+++ b/kernel/cgroup/rstat.c
@@ -291,8 +291,13 @@ void __init cgroup_rstat_boot(void)
 {
 	int cpu;
 
-	for_each_possible_cpu(cpu)
-		raw_spin_lock_init(per_cpu_ptr(&cgroup_rstat_cpu_lock, cpu));
+	for_each_possible_cpu(cpu) {
+		raw_spinlock_t *cgroup_rstat_percpu_lock =
+				per_cpu_ptr(&cgroup_rstat_cpu_lock, cpu);
+
+		raw_spin_lock_init(cgroup_rstat_percpu_lock);
+		lockdep_set_terminal_class(cgroup_rstat_percpu_lock);
+	}
 
 	BUG_ON(cgroup_rstat_init(&cgrp_dfl_root.cgrp));
 }
-- 
1.8.3.1

[RFC PATCH 12/12] mm/kasan: Make quarantine_lock a terminal lock

[Waiman Long]

By making quarantine_lock a terminal spinlock, it reduces the lockdep
overhead when this lock is being used.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 mm/kasan/quarantine.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
index b209dba..c9d36ab 100644
--- a/mm/kasan/quarantine.c
+++ b/mm/kasan/quarantine.c
@@ -103,7 +103,7 @@ static void qlist_move_all(struct qlist_head *from, struct qlist_head *to)
 static int quarantine_tail;
 /* Total size of all objects in global_quarantine across all batches. */
 static unsigned long quarantine_size;
-static DEFINE_RAW_SPINLOCK(quarantine_lock);
+static DEFINE_RAW_TERMINAL_SPINLOCK(quarantine_lock);
 DEFINE_STATIC_SRCU(remove_cache_srcu);
 
 /* Maximum size of the global queue. */
-- 
1.8.3.1

Re: [RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[Ingo Molnar]

* Waiman Long <longman@redhat.com> wrote:

> The purpose of this patchset is to add a new class of locks called
> terminal locks and converts some of the low level raw or regular
> spinlocks to terminal locks. A terminal lock does not have forward
> dependency and it won't allow a lock or unlock operation on another
> lock. Two level nesting of terminal locks is allowed, though.
> 
> Only spinlocks that are acquired with the _irq/_irqsave variants or
> acquired in an IRQ disabled context should be classified as terminal
> locks.
> 
> Because of the restrictions on terminal locks, we can do simple checks on
> them without using the lockdep lock validation machinery. The advantages
> of making these changes are as follows:
> 
>  1) The lockdep check will be faster for terminal locks without using
>     the lock validation code.
>  2) It saves table entries used by the validation code and hence make
>     it harder to overflow those tables.
> 
> In fact, it is possible to overflow some of the tables by running
> a variety of different workloads on a debug kernel. I have seen bug
> reports about exhausting MAX_LOCKDEP_KEYS, MAX_LOCKDEP_ENTRIES and
> MAX_STACK_TRACE_ENTRIES. This patch will help to reduce the chance
> of overflowing some of the tables.
> 
> Performance wise, there was no statistically significant difference in
> performanace when doing a parallel kernel build on a debug kernel.

Could you please measure a locking intense workload instead, such as:

   $ perf stat --null --sync --repeat 10 perf bench sched messaging

and profile which locks used there could be marked terminal, and measure 
the before/after performance impact?

> Below were selected output lines from the lockdep_stats files of the
> patched and unpatched kernels after bootup and running parallel kernel
> builds.
> 
>   Item                     Unpatched kernel  Patched kernel  % Change
>   ----                     ----------------  --------------  --------
>   direct dependencies           9732             8994          -7.6%
>   dependency chains            18776            17033          -9.3%
>   dependency chain hlocks      76044            68419         -10.0%
>   stack-trace entries         110403           104341          -5.5%

That's pretty impressive!

> There were some reductions in the size of the lockdep tables. They were
> not significant, but it is still a good start to rein in the number of
> entries in those tables to make it harder to overflow them.

Agreed.

BTW., if you are interested in more radical approaches to optimize 
lockdep, we could also add a static checker via objtool driven call graph 
analysis, and mark those locks terminal that we can prove are terminal.

This would require the unified call graph of the kernel image and of all 
modules to be examined in a final pass, but that's within the principal 
scope of objtool. (This 'final pass' could also be done during bootup, at 
least in initial versions.)

Note that beyond marking it 'terminal' such a static analysis pass would 
also allow the detection of obvious locking bugs at the build (or boot) 
stage already - plus it would allow the disabling of lockdep for 
self-contained locks that don't interact with anything else.

I.e. the static analysis pass would 'augment' lockdep and leave only 
those locks active for runtime lockdep tracking whose dependencies it 
cannot prove to be correct yet.

Thanks,

	Ingo

Re: [RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[Waiman Long]

On 11/09/2018 03:04 AM, Ingo Molnar wrote:
> * Waiman Long <longman@redhat.com> wrote:
>
>> The purpose of this patchset is to add a new class of locks called
>> terminal locks and converts some of the low level raw or regular
>> spinlocks to terminal locks. A terminal lock does not have forward
>> dependency and it won't allow a lock or unlock operation on another
>> lock. Two level nesting of terminal locks is allowed, though.
>>
>> Only spinlocks that are acquired with the _irq/_irqsave variants or
>> acquired in an IRQ disabled context should be classified as terminal
>> locks.
>>
>> Because of the restrictions on terminal locks, we can do simple checks on
>> them without using the lockdep lock validation machinery. The advantages
>> of making these changes are as follows:
>>
>>  1) The lockdep check will be faster for terminal locks without using
>>     the lock validation code.
>>  2) It saves table entries used by the validation code and hence make
>>     it harder to overflow those tables.
>>
>> In fact, it is possible to overflow some of the tables by running
>> a variety of different workloads on a debug kernel. I have seen bug
>> reports about exhausting MAX_LOCKDEP_KEYS, MAX_LOCKDEP_ENTRIES and
>> MAX_STACK_TRACE_ENTRIES. This patch will help to reduce the chance
>> of overflowing some of the tables.
>>
>> Performance wise, there was no statistically significant difference in
>> performanace when doing a parallel kernel build on a debug kernel.
> Could you please measure a locking intense workload instead, such as:
>
>    $ perf stat --null --sync --repeat 10 perf bench sched messaging
>
> and profile which locks used there could be marked terminal, and measure 
> the before/after performance impact?

I will run the test. It will probably be done after the LPC next week.

>> Below were selected output lines from the lockdep_stats files of the
>> patched and unpatched kernels after bootup and running parallel kernel
>> builds.
>>
>>   Item                     Unpatched kernel  Patched kernel  % Change
>>   ----                     ----------------  --------------  --------
>>   direct dependencies           9732             8994          -7.6%
>>   dependency chains            18776            17033          -9.3%
>>   dependency chain hlocks      76044            68419         -10.0%
>>   stack-trace entries         110403           104341          -5.5%
> That's pretty impressive!
>
>> There were some reductions in the size of the lockdep tables. They were
>> not significant, but it is still a good start to rein in the number of
>> entries in those tables to make it harder to overflow them.
> Agreed.
>
> BTW., if you are interested in more radical approaches to optimize 
> lockdep, we could also add a static checker via objtool driven call graph 
> analysis, and mark those locks terminal that we can prove are terminal.
>
> This would require the unified call graph of the kernel image and of all 
> modules to be examined in a final pass, but that's within the principal 
> scope of objtool. (This 'final pass' could also be done during bootup, at 
> least in initial versions.)
>
> Note that beyond marking it 'terminal' such a static analysis pass would 
> also allow the detection of obvious locking bugs at the build (or boot) 
> stage already - plus it would allow the disabling of lockdep for 
> self-contained locks that don't interact with anything else.
>
> I.e. the static analysis pass would 'augment' lockdep and leave only 
> those locks active for runtime lockdep tracking whose dependencies it 
> cannot prove to be correct yet.

It is a pretty interesting idea to use objtool to scan for locks. The
list of locks that I marked as terminal in this patch was found by
looking at /proc/lockdep for those that only have backward dependencies,
but no forward dependency. I focused on those with a large number of BDs
and check the code to see if they could marked as terminal. This is a
rather labor intensive process and is subject to error. It would be nice
if it can be done by an automated tool. So I am going to look into that,
but it won't be part of this initial patchset, though.

I sent this patchset out to see if anyone has any objection to it. It
seems you don't have any objection to that. So I am going to move ahead
to do more testing and performance analysis.

Thanks,
Longman

Re: [RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[Peter Zijlstra]

On Fri, Nov 09, 2018 at 09:04:12AM +0100, Ingo Molnar wrote:
> BTW., if you are interested in more radical approaches to optimize 
> lockdep, we could also add a static checker via objtool driven call graph 
> analysis, and mark those locks terminal that we can prove are terminal.
> 
> This would require the unified call graph of the kernel image and of all 
> modules to be examined in a final pass, but that's within the principal 
> scope of objtool. (This 'final pass' could also be done during bootup, at 
> least in initial versions.)

Something like this is needed for objtool LTO support as well. I just
dread the build time 'regressions' this will introduce :/

The final link pass is already by far the most expensive part (as
measured in wall-time) of building a kernel, adding more work there
would really suck :/

Re: [RFC PATCH 01/12] locking/lockdep: Rework lockdep_set_novalidate_class()

[Peter Zijlstra]

On Thu, Nov 08, 2018 at 03:34:17PM -0500, Waiman Long wrote:
> The current lockdep_set_novalidate_class() implementation is like
> a hack. It assigns a special class key for that lock and calls
> lockdep_init_map() twice.

Ideally it would go away.. it is not thing that should be used.

> This patch changes the implementation to make it more general so that
> it can be used by other special lock class types. A new "type" field
> is added to both the lockdep_map and lock_class structures.
> 
> The new field can now be used to designate a lock and a class object
> as novalidate. The lockdep_set_novalidate_class() call, however, should
> be called before lock initialization which calls lockdep_init_map().

I don't really feel like this is something that should be made easier or
better.

> @@ -102,6 +100,8 @@ struct lock_class {
>  	int				name_version;
>  	const char			*name;
>  
> +	unsigned int			flags;
> +
>  #ifdef CONFIG_LOCK_STAT
>  	unsigned long			contention_point[LOCKSTAT_POINTS];
>  	unsigned long			contending_point[LOCKSTAT_POINTS];

Esp. not at the cost of growing the data structures.

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

[Peter Zijlstra]

On Thu, Nov 08, 2018 at 03:34:18PM -0500, Waiman Long wrote:
> 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.

> @@ -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;
>  };

I'm thinking we can easily steal some bits off of the pin_count field if
we have to.

Re: [RFC PATCH 07/12] locking/lockdep: Add support for nested terminal locks

[Peter Zijlstra]

On Thu, Nov 08, 2018 at 03:34:23PM -0500, Waiman Long wrote:
> There are use cases where we want to allow 2-level nesting of one
> terminal lock underneath another one. So the terminal lock type is now
> extended to support a new nested terminal lock where it can allow the
> acquisition of another regular terminal lock underneath it.

You're stretching things here... If you're allowing things under it, it
is no longer a terminal lock.

Why would you want to do such a thing?

Re: [RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[Waiman Long]

On 11/10/2018 09:10 AM, Peter Zijlstra wrote:
> On Fri, Nov 09, 2018 at 09:04:12AM +0100, Ingo Molnar wrote:
>> BTW., if you are interested in more radical approaches to optimize 
>> lockdep, we could also add a static checker via objtool driven call graph 
>> analysis, and mark those locks terminal that we can prove are terminal.
>>
>> This would require the unified call graph of the kernel image and of all 
>> modules to be examined in a final pass, but that's within the principal 
>> scope of objtool. (This 'final pass' could also be done during bootup, at 
>> least in initial versions.)
> Something like this is needed for objtool LTO support as well. I just
> dread the build time 'regressions' this will introduce :/
>
> The final link pass is already by far the most expensive part (as
> measured in wall-time) of building a kernel, adding more work there
> would really suck :/

I think the idea is to make objtool have the capability to do that. It
doesn't mean we need to turn it on by default in every build.

Cheers,
Longman

Re: [RFC PATCH 01/12] locking/lockdep: Rework lockdep_set_novalidate_class()

[Waiman Long]

On 11/10/2018 09:14 AM, Peter Zijlstra wrote:
> On Thu, Nov 08, 2018 at 03:34:17PM -0500, Waiman Long wrote:
>> The current lockdep_set_novalidate_class() implementation is like
>> a hack. It assigns a special class key for that lock and calls
>> lockdep_init_map() twice.
> Ideally it would go away.. it is not thing that should be used.

Yes, I agree. Right now, lockdep_set_novalidate_class() is used in

drivers/base/core.c:    lockdep_set_novalidate_class(&dev->mutex);
drivers/md/bcache/btree.c:      lockdep_set_novalidate_class(&b->lock);
drivers/md/bcache/btree.c:     
lockdep_set_novalidate_class(&b->write_lock);

Do you know the history behind making them novalidate?

>
>> This patch changes the implementation to make it more general so that
>> it can be used by other special lock class types. A new "type" field
>> is added to both the lockdep_map and lock_class structures.
>>
>> The new field can now be used to designate a lock and a class object
>> as novalidate. The lockdep_set_novalidate_class() call, however, should
>> be called before lock initialization which calls lockdep_init_map().
> I don't really feel like this is something that should be made easier or
> better.

I am not saying that this patch make lockdep_set_novalidate_class()
easier to use. It is that terminal locks will share similar code path
and so I rework it so that they can checked together in one test instead
of 2 separate tests.

>> @@ -102,6 +100,8 @@ struct lock_class {
>>  	int				name_version;
>>  	const char			*name;
>>  
>> +	unsigned int			flags;
>> +
>>  #ifdef CONFIG_LOCK_STAT
>>  	unsigned long			contention_point[LOCKSTAT_POINTS];
>>  	unsigned long			contending_point[LOCKSTAT_POINTS];
> Esp. not at the cost of growing the data structures.
>
>

I did reduce the size by 16 bytes for 64-bit architecture in my previous
lockdep patch. Now I claw back 8 bytes for this new functionality.

Cheers,
Longman

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

[Waiman Long]

On 11/10/2018 09:17 AM, Peter Zijlstra wrote:
> On Thu, Nov 08, 2018 at 03:34:18PM -0500, Waiman Long wrote:
>> 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.
>> @@ -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;
>>  };
> I'm thinking we can easily steal some bits off of the pin_count field if
> we have to.

OK, I will take a look at that.

Cheers,
Longman

Re: [RFC PATCH 07/12] locking/lockdep: Add support for nested terminal locks

[Waiman Long]

On 11/10/2018 09:20 AM, Peter Zijlstra wrote:
> On Thu, Nov 08, 2018 at 03:34:23PM -0500, Waiman Long wrote:
>> There are use cases where we want to allow 2-level nesting of one
>> terminal lock underneath another one. So the terminal lock type is now
>> extended to support a new nested terminal lock where it can allow the
>> acquisition of another regular terminal lock underneath it.
> You're stretching things here... If you're allowing things under it, it
> is no longer a terminal lock.
>
> Why would you want to do such a thing?

A majority of the gain in debugobjects is to make the hash lock a kind
of terminal lock. Yes, I may be stretching it a bit here. I will take
back the nesting patch and consider doing that in a future patch.

Cheers,
Longman

Re: [RFC PATCH 01/12] locking/lockdep: Rework lockdep_set_novalidate_class()

[Peter Zijlstra]

On Sat, Nov 10, 2018 at 07:26:51PM -0500, Waiman Long wrote:
> On 11/10/2018 09:14 AM, Peter Zijlstra wrote:
> > On Thu, Nov 08, 2018 at 03:34:17PM -0500, Waiman Long wrote:
> >> The current lockdep_set_novalidate_class() implementation is like
> >> a hack. It assigns a special class key for that lock and calls
> >> lockdep_init_map() twice.
> > Ideally it would go away.. it is not thing that should be used.
> 
> Yes, I agree. Right now, lockdep_set_novalidate_class() is used in
> 
> drivers/base/core.c:    lockdep_set_novalidate_class(&dev->mutex);
> drivers/md/bcache/btree.c:      lockdep_set_novalidate_class(&b->lock);
> drivers/md/bcache/btree.c:     
> lockdep_set_novalidate_class(&b->write_lock);
> 
> Do you know the history behind making them novalidate?

Only of the driver/base/core.c one; there the locking order depends on
the hardware and we never quite found a way to annotate that sanely. I
forgot most details though.

The other stuff I only 'recently' found out about :-( And ideally would
have never made it into the tree, but alas.

Re: [RFC PATCH 07/12] locking/lockdep: Add support for nested terminal locks

[Peter Zijlstra]

On Sat, Nov 10, 2018 at 07:30:54PM -0500, Waiman Long wrote:
> On 11/10/2018 09:20 AM, Peter Zijlstra wrote:
> > On Thu, Nov 08, 2018 at 03:34:23PM -0500, Waiman Long wrote:
> >> There are use cases where we want to allow 2-level nesting of one
> >> terminal lock underneath another one. So the terminal lock type is now
> >> extended to support a new nested terminal lock where it can allow the
> >> acquisition of another regular terminal lock underneath it.
> > You're stretching things here... If you're allowing things under it, it
> > is no longer a terminal lock.
> >
> > Why would you want to do such a thing?
> 
> A majority of the gain in debugobjects is to make the hash lock a kind
> of terminal lock. Yes, I may be stretching it a bit here. I will take
> back the nesting patch and consider doing that in a future patch.

Maybe try and write a better changelog? I'm not following, but that
could also be because I've been awake for almost 20 hours :/

Re: [RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[Ingo Molnar]

* Waiman Long <longman@redhat.com> wrote:

> On 11/10/2018 09:10 AM, Peter Zijlstra wrote:
> > On Fri, Nov 09, 2018 at 09:04:12AM +0100, Ingo Molnar wrote:
> >> BTW., if you are interested in more radical approaches to optimize 
> >> lockdep, we could also add a static checker via objtool driven call graph 
> >> analysis, and mark those locks terminal that we can prove are terminal.
> >>
> >> This would require the unified call graph of the kernel image and of all 
> >> modules to be examined in a final pass, but that's within the principal 
> >> scope of objtool. (This 'final pass' could also be done during bootup, at 
> >> least in initial versions.)
> >
> > Something like this is needed for objtool LTO support as well. I just
> > dread the build time 'regressions' this will introduce :/
> >
> > The final link pass is already by far the most expensive part (as
> > measured in wall-time) of building a kernel, adding more work there
> > would really suck :/
> 
> I think the idea is to make objtool have the capability to do that. It
> doesn't mean we need to turn it on by default in every build.

Yeah.

Also note that much of the objtool legwork would be on a per file basis 
which is reasonably parallelized already. On x86 it's also already done 
for every ORC build i.e. every distro build and the incremental overhead 
from also extracting locking dependencies should be reasonably small.

The final search of the global graph would be serialized but still 
reasonably fast as these are all 'class' level dependencies which are 
much less numerous than runtime dependencies.

I.e. I think we are talking about tens of thousands of dependencies, not 
tens of millions.

At least in theory. ;-)

Thanks,

	Ingo

Re: [RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[Ingo Molnar]

* Waiman Long <longman@redhat.com> wrote:

> > Could you please measure a locking intense workload instead, such as:
> >
> >    $ perf stat --null --sync --repeat 10 perf bench sched messaging
> >
> > and profile which locks used there could be marked terminal, and measure 
> > the before/after performance impact?
> 
> I will run the test. It will probably be done after the LPC next week.

Thanks!

> >> Below were selected output lines from the lockdep_stats files of the
> >> patched and unpatched kernels after bootup and running parallel kernel
> >> builds.
> >>
> >>   Item                     Unpatched kernel  Patched kernel  % Change
> >>   ----                     ----------------  --------------  --------
> >>   direct dependencies           9732             8994          -7.6%
> >>   dependency chains            18776            17033          -9.3%
> >>   dependency chain hlocks      76044            68419         -10.0%
> >>   stack-trace entries         110403           104341          -5.5%
> > That's pretty impressive!
> >
> >> There were some reductions in the size of the lockdep tables. They were
> >> not significant, but it is still a good start to rein in the number of
> >> entries in those tables to make it harder to overflow them.
> > Agreed.
> >
> > BTW., if you are interested in more radical approaches to optimize 
> > lockdep, we could also add a static checker via objtool driven call graph 
> > analysis, and mark those locks terminal that we can prove are terminal.
> >
> > This would require the unified call graph of the kernel image and of all 
> > modules to be examined in a final pass, but that's within the principal 
> > scope of objtool. (This 'final pass' could also be done during bootup, at 
> > least in initial versions.)
> >
> > Note that beyond marking it 'terminal' such a static analysis pass would 
> > also allow the detection of obvious locking bugs at the build (or boot) 
> > stage already - plus it would allow the disabling of lockdep for 
> > self-contained locks that don't interact with anything else.
> >
> > I.e. the static analysis pass would 'augment' lockdep and leave only 
> > those locks active for runtime lockdep tracking whose dependencies it 
> > cannot prove to be correct yet.
> 
> It is a pretty interesting idea to use objtool to scan for locks. The
> list of locks that I marked as terminal in this patch was found by
> looking at /proc/lockdep for those that only have backward dependencies,
> but no forward dependency. I focused on those with a large number of BDs
> and check the code to see if they could marked as terminal. This is a
> rather labor intensive process and is subject to error.

Yeah.

> [...] It would be nice if it can be done by an automated tool. So I am 
> going to look into that, but it won't be part of this initial patchset, 
> though.

Of course!

> I sent this patchset out to see if anyone has any objection to it. It
> seems you don't have any objection to that. So I am going to move ahead
> to do more testing and performance analysis.

The one worry I have is that this interim solution removes the benefit of 
a proper static analysis method.

But if you promise to make a serious effort on the static analysis 
tooling as well (which should have awesome performance results and 
automate the manual markup), then I have no fundamental objections to the 
interim approach either.

If static analysis works as well as I expect it to then in principle we 
might even be able to have lockdep enabled in production kernels: it 
would only add overhead to locks that are overly complex - which would 
create incentives to improve those dependencies.

Thanks,

	Ingo

Re: [RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[Josh Poimboeuf]

On Mon, Nov 12, 2018 at 06:10:33AM +0100, Ingo Molnar wrote:
> 
> * Waiman Long <longman@redhat.com> wrote:
> 
> > On 11/10/2018 09:10 AM, Peter Zijlstra wrote:
> > > On Fri, Nov 09, 2018 at 09:04:12AM +0100, Ingo Molnar wrote:
> > >> BTW., if you are interested in more radical approaches to optimize 
> > >> lockdep, we could also add a static checker via objtool driven call graph 
> > >> analysis, and mark those locks terminal that we can prove are terminal.
> > >>
> > >> This would require the unified call graph of the kernel image and of all 
> > >> modules to be examined in a final pass, but that's within the principal 
> > >> scope of objtool. (This 'final pass' could also be done during bootup, at 
> > >> least in initial versions.)
> > >
> > > Something like this is needed for objtool LTO support as well. I just
> > > dread the build time 'regressions' this will introduce :/
> > >
> > > The final link pass is already by far the most expensive part (as
> > > measured in wall-time) of building a kernel, adding more work there
> > > would really suck :/
> > 
> > I think the idea is to make objtool have the capability to do that. It
> > doesn't mean we need to turn it on by default in every build.
> 
> Yeah.
> 
> Also note that much of the objtool legwork would be on a per file basis 
> which is reasonably parallelized already. On x86 it's also already done 
> for every ORC build i.e. every distro build and the incremental overhead 
> from also extracting locking dependencies should be reasonably small.
> 
> The final search of the global graph would be serialized but still 
> reasonably fast as these are all 'class' level dependencies which are 
> much less numerous than runtime dependencies.
> 
> I.e. I think we are talking about tens of thousands of dependencies, not 
> tens of millions.
> 
> At least in theory. ;-)

Generating a unified call graph sounds very expensive (and very far
beyond what objtool can do today).  Also, what about function pointers?

BTW there's another kernel static analysis tool which attempts to create
such a call graph already: smatch.

-- 
Josh

Re: [RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[Ingo Molnar]

* Josh Poimboeuf <jpoimboe@redhat.com> wrote:

> On Mon, Nov 12, 2018 at 06:10:33AM +0100, Ingo Molnar wrote:
> > 
> > * Waiman Long <longman@redhat.com> wrote:
> > 
> > > On 11/10/2018 09:10 AM, Peter Zijlstra wrote:
> > > > On Fri, Nov 09, 2018 at 09:04:12AM +0100, Ingo Molnar wrote:
> > > >> BTW., if you are interested in more radical approaches to optimize 
> > > >> lockdep, we could also add a static checker via objtool driven call graph 
> > > >> analysis, and mark those locks terminal that we can prove are terminal.
> > > >>
> > > >> This would require the unified call graph of the kernel image and of all 
> > > >> modules to be examined in a final pass, but that's within the principal 
> > > >> scope of objtool. (This 'final pass' could also be done during bootup, at 
> > > >> least in initial versions.)
> > > >
> > > > Something like this is needed for objtool LTO support as well. I just
> > > > dread the build time 'regressions' this will introduce :/
> > > >
> > > > The final link pass is already by far the most expensive part (as
> > > > measured in wall-time) of building a kernel, adding more work there
> > > > would really suck :/
> > > 
> > > I think the idea is to make objtool have the capability to do that. It
> > > doesn't mean we need to turn it on by default in every build.
> > 
> > Yeah.
> > 
> > Also note that much of the objtool legwork would be on a per file basis 
> > which is reasonably parallelized already. On x86 it's also already done 
> > for every ORC build i.e. every distro build and the incremental overhead 
> > from also extracting locking dependencies should be reasonably small.
> > 
> > The final search of the global graph would be serialized but still 
> > reasonably fast as these are all 'class' level dependencies which are 
> > much less numerous than runtime dependencies.
> > 
> > I.e. I think we are talking about tens of thousands of dependencies, not 
> > tens of millions.
> > 
> > At least in theory. ;-)
> 
> Generating a unified call graph sounds very expensive (and very far
> beyond what objtool can do today).

Well, objtool already goes through the instruction stream and recognizes 
function calls - so it can in effect generate a stream of "function x 
called by function y" data, correct?

>  Also, what about function pointers?

So maybe it's possible to enumerate all potential values for function 
pointers with a reasonably simple compiler plugin and work from there?

One complication would be function pointers encoded as opaque data 
types...

> BTW there's another kernel static analysis tool which attempts to 
> create such a call graph already: smatch.

It's not included in the kernel tree though and I'd expect tight coupling 
(or at least lock-step improvements) between tooling and lockdep here.

Thanks,

	Ingo

Re: [RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[Josh Poimboeuf]

On Mon, Nov 12, 2018 at 07:30:50AM +0100, Ingo Molnar wrote:
> 
> * Josh Poimboeuf <jpoimboe@redhat.com> wrote:
> 
> > On Mon, Nov 12, 2018 at 06:10:33AM +0100, Ingo Molnar wrote:
> > > 
> > > * Waiman Long <longman@redhat.com> wrote:
> > > 
> > > > On 11/10/2018 09:10 AM, Peter Zijlstra wrote:
> > > > > On Fri, Nov 09, 2018 at 09:04:12AM +0100, Ingo Molnar wrote:
> > > > >> BTW., if you are interested in more radical approaches to optimize 
> > > > >> lockdep, we could also add a static checker via objtool driven call graph 
> > > > >> analysis, and mark those locks terminal that we can prove are terminal.
> > > > >>
> > > > >> This would require the unified call graph of the kernel image and of all 
> > > > >> modules to be examined in a final pass, but that's within the principal 
> > > > >> scope of objtool. (This 'final pass' could also be done during bootup, at 
> > > > >> least in initial versions.)
> > > > >
> > > > > Something like this is needed for objtool LTO support as well. I just
> > > > > dread the build time 'regressions' this will introduce :/
> > > > >
> > > > > The final link pass is already by far the most expensive part (as
> > > > > measured in wall-time) of building a kernel, adding more work there
> > > > > would really suck :/
> > > > 
> > > > I think the idea is to make objtool have the capability to do that. It
> > > > doesn't mean we need to turn it on by default in every build.
> > > 
> > > Yeah.
> > > 
> > > Also note that much of the objtool legwork would be on a per file basis 
> > > which is reasonably parallelized already. On x86 it's also already done 
> > > for every ORC build i.e. every distro build and the incremental overhead 
> > > from also extracting locking dependencies should be reasonably small.
> > > 
> > > The final search of the global graph would be serialized but still 
> > > reasonably fast as these are all 'class' level dependencies which are 
> > > much less numerous than runtime dependencies.
> > > 
> > > I.e. I think we are talking about tens of thousands of dependencies, not 
> > > tens of millions.
> > > 
> > > At least in theory. ;-)
> > 
> > Generating a unified call graph sounds very expensive (and very far
> > beyond what objtool can do today).
> 
> Well, objtool already goes through the instruction stream and recognizes 
> function calls - so it can in effect generate a stream of "function x 
> called by function y" data, correct?

Yeah, though it would be quite simple to get the same data with a simple
awk script at link time.

> >  Also, what about function pointers?
> 
> So maybe it's possible to enumerate all potential values for function 
> pointers with a reasonably simple compiler plugin and work from there?

I think this would be somewhere between very difficult and impossible to
do properly.  I can't even imagine how this would be implemented in a
compiler plugin.  But I'd love to be proven wrong on that.

> One complication would be function pointers encoded as opaque data 
> types...
> 
> > BTW there's another kernel static analysis tool which attempts to 
> > create such a call graph already: smatch.
> 
> It's not included in the kernel tree though and I'd expect tight coupling 
> (or at least lock-step improvements) between tooling and lockdep here.

Fair enough.  Smatch's call tree isn't perfect anyway, but I don't think
perfect is attainable.

-- 
Josh

Re: [RFC PATCH 00/12] locking/lockdep: Add a new class of terminal locks

[Waiman Long]

On 11/12/2018 02:22 PM, Josh Poimboeuf wrote:
> On Mon, Nov 12, 2018 at 07:30:50AM +0100, Ingo Molnar wrote:
>> * Josh Poimboeuf <jpoimboe@redhat.com> wrote:
>>
>>> On Mon, Nov 12, 2018 at 06:10:33AM +0100, Ingo Molnar wrote:
>>>> * Waiman Long <longman@redhat.com> wrote:
>>>>
>>>>> On 11/10/2018 09:10 AM, Peter Zijlstra wrote:
>>>>>> On Fri, Nov 09, 2018 at 09:04:12AM +0100, Ingo Molnar wrote:
>>>>>>> BTW., if you are interested in more radical approaches to optimize 
>>>>>>> lockdep, we could also add a static checker via objtool driven call graph 
>>>>>>> analysis, and mark those locks terminal that we can prove are terminal.
>>>>>>>
>>>>>>> This would require the unified call graph of the kernel image and of all 
>>>>>>> modules to be examined in a final pass, but that's within the principal 
>>>>>>> scope of objtool. (This 'final pass' could also be done during bootup, at 
>>>>>>> least in initial versions.)
>>>>>> Something like this is needed for objtool LTO support as well. I just
>>>>>> dread the build time 'regressions' this will introduce :/
>>>>>>
>>>>>> The final link pass is already by far the most expensive part (as
>>>>>> measured in wall-time) of building a kernel, adding more work there
>>>>>> would really suck :/
>>>>> I think the idea is to make objtool have the capability to do that. It
>>>>> doesn't mean we need to turn it on by default in every build.
>>>> Yeah.
>>>>
>>>> Also note that much of the objtool legwork would be on a per file basis 
>>>> which is reasonably parallelized already. On x86 it's also already done 
>>>> for every ORC build i.e. every distro build and the incremental overhead 
>>>> from also extracting locking dependencies should be reasonably small.
>>>>
>>>> The final search of the global graph would be serialized but still 
>>>> reasonably fast as these are all 'class' level dependencies which are 
>>>> much less numerous than runtime dependencies.
>>>>
>>>> I.e. I think we are talking about tens of thousands of dependencies, not 
>>>> tens of millions.
>>>>
>>>> At least in theory. ;-)
>>> Generating a unified call graph sounds very expensive (and very far
>>> beyond what objtool can do today).
>> Well, objtool already goes through the instruction stream and recognizes 
>> function calls - so it can in effect generate a stream of "function x 
>> called by function y" data, correct?
> Yeah, though it would be quite simple to get the same data with a simple
> awk script at link time.
>
>>>  Also, what about function pointers?
>> So maybe it's possible to enumerate all potential values for function 
>> pointers with a reasonably simple compiler plugin and work from there?
> I think this would be somewhere between very difficult and impossible to
> do properly.  I can't even imagine how this would be implemented in a
> compiler plugin.  But I'd love to be proven wrong on that.

I would say we have to assume for the worst when a function pointer is
being called while holding a lock unless we are able to find out all its
possible targets.

Cheers,
Longman