Skip to contentSkip to conversation

Detect SRCU related deadlocks

PATCH In review Boqun Feng 7 participants 31 messages Jan 13, 2023 – Feb 4, 2023

Subsystems (7)
lore
Share & tools
lore

Boqun Feng

author
#0 lore raw

cover Detect SRCU related deadlocks

This is actually a leftover of the recursive read deadlock detection patchset:

	https://lore.kernel.org/lkml/[email protected]/

I resolve comments then and add more test cases, and hopefully this can fulfill the request from KVM:

	https://lore.kernel.org/lkml/[email protected]/

;-)

The patch #3 is now WIP for two reasons:

* It may conflicts with Paul's patchset on removing CONFIG_SRCU

* I haven't found a proper way to "reinit" srcu_struct when
lockdep selftest runs: cleanup_srcu_struct() needs workqueue however the tests can run before there is one.

Anyway, these selftests prove the detection actually works. And as always, feedbacks and comments are welcome!

Regards,
Boqun

Boqun Feng (3):
locking/lockdep: Introduce lock_sync()
rcu: Equip sleepable RCU with lockdep dependency graph checks
WIP: locking/lockdep: selftests: Add selftests for SRCU

 include/linux/lockdep.h  |  5 +++
 include/linux/srcu.h     | 23 +++++++++++--
 kernel/locking/lockdep.c | 34 +++++++++++++++++++
 kernel/rcu/srcutiny.c    |  2 ++
 kernel/rcu/srcutree.c    |  2 ++
 lib/locking-selftest.c   | 71 ++++++++++++++++++++++++++++++++++++++++
 6 files changed, 135 insertions(+), 2 deletions(-)
Signature · 1 line
2.38.1
author
#1 lore raw

PATCH 1/3 locking/lockdep: Introduce lock_sync()

Currently, in order to annonate functions like synchronize_srcu() for lockdep, a trick as follow can be used:

	lock_acquire();
	lock_release();

, which indicates synchronize_srcu() acts like an empty critical section that waits for other (read-side) critical sections to finish. This surely can catch some deadlock, but as discussion brought up by Paul Mckenney [1], this could introduce false positives because of irq-safe/unsafe detection. Extra tricks might help this:

	local_irq_disable(..);
	lock_acquire();
	lock_release();
	local_irq_enable(...);

But it's better that lockdep could provide an annonation for synchronize_srcu() like functions, so that people won't need to repeat the ugly tricks above. Therefore introduce lock_sync(). It's simply an lock+unlock pair with no irq safe/unsafe deadlock check, since the to-be-annontated functions don't create real critical sections therefore there is no way that irq can create extra dependencies.

[1]: https://lore.kernel.org/lkml/20180412021233.ewncg5jjuzjw3x62@tardis/

---
 include/linux/lockdep.h  |  5 +++++
 kernel/locking/lockdep.c | 34 ++++++++++++++++++++++++++++++++++
 2 files changed, 39 insertions(+)
include/linux/lockdep.h +5 -0
index 1f1099dac3f0..ba09df6a0872 100644
@@ -268,6 +268,10 @@ extern void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 
 extern void lock_release(struct lockdep_map *lock, unsigned long ip);
 
+extern void lock_sync(struct lockdep_map *lock, unsigned int subclass,
+		      int read, int check, struct lockdep_map *nest_lock,
+		      unsigned long ip);
+
 /* lock_is_held_type() returns */
 #define LOCK_STATE_UNKNOWN	-1
 #define LOCK_STATE_NOT_HELD	0
@@ -555,6 +559,7 @@ do {									\
 #define lock_map_acquire_read(l)		lock_acquire_shared_recursive(l, 0, 0, NULL, _THIS_IP_)
 #define lock_map_acquire_tryread(l)		lock_acquire_shared_recursive(l, 0, 1, NULL, _THIS_IP_)
 #define lock_map_release(l)			lock_release(l, _THIS_IP_)
+#define lock_map_sync(l)			lock_sync(l, 0, 0, 1, NULL, _THIS_IP_)
 
 #ifdef CONFIG_PROVE_LOCKING
 # define might_lock(lock)						\
kernel/locking/lockdep.c +34 -0
index e3375bc40dad..cffa026a765f 100644
@@ -5692,6 +5692,40 @@ void lock_release(struct lockdep_map *lock, unsigned long ip)
 }
 EXPORT_SYMBOL_GPL(lock_release);
 
+/*
+ * lock_sync() - A special annotation for synchronize_{s,}rcu()-like API.
+ *
+ * No actual critical section is created by the APIs annotated with this: these
+ * APIs are used to wait for one or multiple critical sections (on other CPUs
+ * or threads), and it means that calling these APIs inside these critical
+ * sections is potential deadlock.
+ *
+ * This annotation acts as an acqurie+release anontation pair with hardirqoff
+ * being 1. Since there's no critical section, no interrupt can create extra
+ * dependencies "inside" the annotation, hardirqoff == 1 allows us to avoid
+ * false positives.
+ */
+void lock_sync(struct lockdep_map *lock, unsigned subclass, int read,
+	       int check, struct lockdep_map *nest_lock, unsigned long ip)
+{
+	unsigned long flags;
+
+	if (unlikely(!lockdep_enabled()))
+		return;
+
+	raw_local_irq_save(flags);
+	check_flags(flags);
+
+	lockdep_recursion_inc();
+	__lock_acquire(lock, subclass, 0, read, check, 1, nest_lock, ip, 0, 0);
+
+	if (__lock_release(lock, ip))
+		check_chain_key(current);
+	lockdep_recursion_finish();
+	raw_local_irq_restore(flags);
+}
+EXPORT_SYMBOL_GPL(lock_sync);
+
 noinstr int lock_is_held_type(const struct lockdep_map *lock, int read)
 {
 	unsigned long flags;
Signature · 1 line
2.38.1
reviewer Acked-by on v1 1/3
#2 lore raw

Re: [PATCH 1/3] locking/lockdep: Introduce lock_sync()

Quoted 90 lines · Boqun Feng

Currently, in order to annonate functions like synchronize_srcu() for lockdep, a trick as follow can be used:

	lock_acquire();
	lock_release();

, which indicates synchronize_srcu() acts like an empty critical section that waits for other (read-side) critical sections to finish. This surely can catch some deadlock, but as discussion brought up by Paul Mckenney [1], this could introduce false positives because of irq-safe/unsafe detection. Extra tricks might help this:

	local_irq_disable(..);
	lock_acquire();
	lock_release();
	local_irq_enable(...);

But it's better that lockdep could provide an annonation for synchronize_srcu() like functions, so that people won't need to repeat the ugly tricks above. Therefore introduce lock_sync(). It's simply an lock+unlock pair with no irq safe/unsafe deadlock check, since the to-be-annontated functions don't create real critical sections therefore there is no way that irq can create extra dependencies.

[1]: https://lore.kernel.org/lkml/20180412021233.ewncg5jjuzjw3x62@tardis/

---
  include/linux/lockdep.h  |  5 +++++
  kernel/locking/lockdep.c | 34 ++++++++++++++++++++++++++++++++++
  2 files changed, 39 insertions(+)
include/linux/lockdep.h +5 -0
index 1f1099dac3f0..ba09df6a0872 100644
@@ -268,6 +268,10 @@ extern void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 
  extern void lock_release(struct lockdep_map *lock, unsigned long ip);
 
+extern void lock_sync(struct lockdep_map *lock, unsigned int subclass,
+		      int read, int check, struct lockdep_map *nest_lock,
+		      unsigned long ip);
+
  /* lock_is_held_type() returns */
  #define LOCK_STATE_UNKNOWN	-1
  #define LOCK_STATE_NOT_HELD	0
@@ -555,6 +559,7 @@ do {									\
  #define lock_map_acquire_read(l)		lock_acquire_shared_recursive(l, 0, 0, NULL, _THIS_IP_)
  #define lock_map_acquire_tryread(l)		lock_acquire_shared_recursive(l, 0, 1, NULL, _THIS_IP_)
  #define lock_map_release(l)			lock_release(l, _THIS_IP_)
+#define lock_map_sync(l)			lock_sync(l, 0, 0, 1, NULL, _THIS_IP_)
 
  #ifdef CONFIG_PROVE_LOCKING
  # define might_lock(lock)						\
kernel/locking/lockdep.c +27 -0
index e3375bc40dad..cffa026a765f 100644
@@ -5692,6 +5692,40 @@ void lock_release(struct lockdep_map *lock, unsigned long ip)
  }
  EXPORT_SYMBOL_GPL(lock_release);
 
+/*
+ * lock_sync() - A special annotation for synchronize_{s,}rcu()-like API.
+ *
+ * No actual critical section is created by the APIs annotated with this: these
+ * APIs are used to wait for one or multiple critical sections (on other CPUs
+ * or threads), and it means that calling these APIs inside these critical
+ * sections is potential deadlock.
+ *
+ * This annotation acts as an acqurie+release anontation pair with hardirqoff
+ * being 1. Since there's no critical section, no interrupt can create extra
+ * dependencies "inside" the annotation, hardirqoff == 1 allows us to avoid
+ * false positives.
+ */
+void lock_sync(struct lockdep_map *lock, unsigned subclass, int read,
+	       int check, struct lockdep_map *nest_lock, unsigned long ip)
+{
+	unsigned long flags;
+
+	if (unlikely(!lockdep_enabled()))
+		return;
+
+	raw_local_irq_save(flags);
+	check_flags(flags);
+
+	lockdep_recursion_inc();
+	__lock_acquire(lock, subclass, 0, read, check, 1, nest_lock, ip, 0, 0);
+

kernel/locking/lockdep.c void lock_release(struct lockdep_map *lock, unsigned long ip) · line 5731

Quoted 10 lines
kernel/locking/lockdep.c +7 -0
+	if (__lock_release(lock, ip))
+		check_chain_key(current);
+	lockdep_recursion_finish();
+	raw_local_irq_restore(flags);
+}
+EXPORT_SYMBOL_GPL(lock_sync);
+
  noinstr int lock_is_held_type(const struct lockdep_map *lock, int read)
  {
  	unsigned long flags;

This patch looks good to me.

author
#3 lore raw

PATCH 2/3 rcu: Equip sleepable RCU with lockdep dependency graph checks

In reply to Boqun Feng

Although all flavors of RCU are annotated correctly with lockdep as recursive read locks, their 'check' parameter of lock_acquire() is unset. It means that RCU read locks are not added into the lockdep dependency graph therefore deadlock detection based on dependency graph won't catch deadlock caused by RCU. This is fine for "non-sleepable" RCU flavors since wait-context detection and other context based detection can catch these deadlocks. However for sleepable RCU, this is limited.

Actually we can detect the deadlocks caused by SRCU by 1) making srcu_read_lock() a 'check'ed recursive read lock and 2) making synchronize_srcu() a empty write lock critical section. Even better, with the newly introduced lock_sync(), we can avoid false positives about irq-unsafe/safe. So do it.

Note that NMI safe SRCU read side critical sections are currently not annonated, since step-by-step approach can help us deal with false-positives. These may be annotated in the future.

---
 include/linux/srcu.h  | 23 +++++++++++++++++++++--
 kernel/rcu/srcutiny.c |  2 ++
 kernel/rcu/srcutree.c |  2 ++
 3 files changed, 25 insertions(+), 2 deletions(-)
include/linux/srcu.h +21 -2
index 9b9d0bbf1d3c..a1595f8c5155 100644
@@ -102,6 +102,21 @@ static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
 	return lock_is_held(&ssp->dep_map);
 }
 
+static inline void srcu_lock_acquire(struct lockdep_map *map)
+{
+	lock_map_acquire_read(map);
+}
+
+static inline void srcu_lock_release(struct lockdep_map *map)
+{
+	lock_map_release(map);
+}
+
+static inline void srcu_lock_sync(struct lockdep_map *map)
+{
+	lock_map_sync(map);
+}
+
 #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
@@ -109,6 +124,10 @@ static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
 	return 1;
 }
 
+#define srcu_lock_acquire(m) do { } while (0)
+#define srcu_lock_release(m) do { } while (0)
+#define srcu_lock_sync(m) do { } while (0)
+
 #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 #define SRCU_NMI_UNKNOWN	0x0
@@ -182,7 +201,7 @@ static inline int srcu_read_lock(struct srcu_struct *ssp) __acquires(ssp)
 
 	srcu_check_nmi_safety(ssp, false);
 	retval = __srcu_read_lock(ssp);
-	rcu_lock_acquire(&(ssp)->dep_map);
+	srcu_lock_acquire(&(ssp)->dep_map);
 	return retval;
 }
 
@@ -226,7 +245,7 @@ static inline void srcu_read_unlock(struct srcu_struct *ssp, int idx)
 {
 	WARN_ON_ONCE(idx & ~0x1);
 	srcu_check_nmi_safety(ssp, false);
-	rcu_lock_release(&(ssp)->dep_map);
+	srcu_lock_release(&(ssp)->dep_map);
 	__srcu_read_unlock(ssp, idx);
 }
 
kernel/rcu/srcutiny.c +2 -0
index b12fb0cec44d..336af24e0fe3 100644
@@ -197,6 +197,8 @@ void synchronize_srcu(struct srcu_struct *ssp)
 {
 	struct rcu_synchronize rs;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			lock_is_held(&rcu_bh_lock_map) ||
 			lock_is_held(&rcu_lock_map) ||
kernel/rcu/srcutree.c +2 -0
index ca4b5dcec675..408088c73e0e 100644
@@ -1267,6 +1267,8 @@ static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
 {
 	struct rcu_synchronize rcu;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			 lock_is_held(&rcu_bh_lock_map) ||
 			 lock_is_held(&rcu_lock_map) ||
Signature · 1 line
2.38.1
maintainer Acked-by on v1 2/3
#4 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

Quoted 14 lines · Boqun Feng

Although all flavors of RCU are annotated correctly with lockdep as recursive read locks, their 'check' parameter of lock_acquire() is unset. It means that RCU read locks are not added into the lockdep dependency graph therefore deadlock detection based on dependency graph won't catch deadlock caused by RCU. This is fine for "non-sleepable" RCU flavors since wait-context detection and other context based detection can catch these deadlocks. However for sleepable RCU, this is limited.

Actually we can detect the deadlocks caused by SRCU by 1) making srcu_read_lock() a 'check'ed recursive read lock and 2) making synchronize_srcu() a empty write lock critical section. Even better, with the newly introduced lock_sync(), we can avoid false positives about irq-unsafe/safe. So do it.

Quoted 5 lines

Note that NMI safe SRCU read side critical sections are currently not annonated, since step-by-step approach can help us deal with false-positives. These may be annotated in the future.

Nice, thank you!!!

Or if you would prefer that I take the series through -rcu, please just let me know.

Thanx, Paul

Quoted 90 lines
---
 include/linux/srcu.h  | 23 +++++++++++++++++++++--
 kernel/rcu/srcutiny.c |  2 ++
 kernel/rcu/srcutree.c |  2 ++
 3 files changed, 25 insertions(+), 2 deletions(-)
include/linux/srcu.h +21 -2
index 9b9d0bbf1d3c..a1595f8c5155 100644
@@ -102,6 +102,21 @@ static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
 	return lock_is_held(&ssp->dep_map);
 }
 
+static inline void srcu_lock_acquire(struct lockdep_map *map)
+{
+	lock_map_acquire_read(map);
+}
+
+static inline void srcu_lock_release(struct lockdep_map *map)
+{
+	lock_map_release(map);
+}
+
+static inline void srcu_lock_sync(struct lockdep_map *map)
+{
+	lock_map_sync(map);
+}
+
 #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
@@ -109,6 +124,10 @@ static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
 	return 1;
 }
 
+#define srcu_lock_acquire(m) do { } while (0)
+#define srcu_lock_release(m) do { } while (0)
+#define srcu_lock_sync(m) do { } while (0)
+
 #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 #define SRCU_NMI_UNKNOWN	0x0
@@ -182,7 +201,7 @@ static inline int srcu_read_lock(struct srcu_struct *ssp) __acquires(ssp)
 
 	srcu_check_nmi_safety(ssp, false);
 	retval = __srcu_read_lock(ssp);
-	rcu_lock_acquire(&(ssp)->dep_map);
+	srcu_lock_acquire(&(ssp)->dep_map);
 	return retval;
 }
 
@@ -226,7 +245,7 @@ static inline void srcu_read_unlock(struct srcu_struct *ssp, int idx)
 {
 	WARN_ON_ONCE(idx & ~0x1);
 	srcu_check_nmi_safety(ssp, false);
-	rcu_lock_release(&(ssp)->dep_map);
+	srcu_lock_release(&(ssp)->dep_map);
 	__srcu_read_unlock(ssp, idx);
 }
 
kernel/rcu/srcutiny.c +2 -0
index b12fb0cec44d..336af24e0fe3 100644
@@ -197,6 +197,8 @@ void synchronize_srcu(struct srcu_struct *ssp)
 {
 	struct rcu_synchronize rs;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			lock_is_held(&rcu_bh_lock_map) ||
 			lock_is_held(&rcu_lock_map) ||
kernel/rcu/srcutree.c +2 -0
index ca4b5dcec675..408088c73e0e 100644
@@ -1267,6 +1267,8 @@ static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
 {
 	struct rcu_synchronize rcu;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			 lock_is_held(&rcu_bh_lock_map) ||
 			 lock_is_held(&rcu_lock_map) ||
Signature · 1 line
2.38.1
author
#5 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

Quoted 19 lines · Paul E. McKenney
Quoted 18 lines · Boqun Feng

Although all flavors of RCU are annotated correctly with lockdep as recursive read locks, their 'check' parameter of lock_acquire() is unset. It means that RCU read locks are not added into the lockdep dependency graph therefore deadlock detection based on dependency graph won't catch deadlock caused by RCU. This is fine for "non-sleepable" RCU flavors since wait-context detection and other context based detection can catch these deadlocks. However for sleepable RCU, this is limited.

Actually we can detect the deadlocks caused by SRCU by 1) making srcu_read_lock() a 'check'ed recursive read lock and 2) making synchronize_srcu() a empty write lock critical section. Even better, with the newly introduced lock_sync(), we can avoid false positives about irq-unsafe/safe. So do it.

Note that NMI safe SRCU read side critical sections are currently not annonated, since step-by-step approach can help us deal with false-positives. These may be annotated in the future.

Quoted 9 lines
Quoted 1 line

Nice, thank you!!!

Or if you would prefer that I take the series through -rcu, please just let me know.

I prefer that the first two patches go through your tree, because it reduces the synchronization among locking, rcu and KVM trees to the synchronization betwen rcu and KVM trees.

For patch #3, since it's not really ready yet, so I don't know, but I guess when it's finished, probably better go through -rcu.

Regards,
Boqun

Quoted 92 lines

Thanx, Paul

Quoted 90 lines
---
 include/linux/srcu.h  | 23 +++++++++++++++++++++--
 kernel/rcu/srcutiny.c |  2 ++
 kernel/rcu/srcutree.c |  2 ++
 3 files changed, 25 insertions(+), 2 deletions(-)
include/linux/srcu.h +21 -2
index 9b9d0bbf1d3c..a1595f8c5155 100644
@@ -102,6 +102,21 @@ static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
 	return lock_is_held(&ssp->dep_map);
 }
 
+static inline void srcu_lock_acquire(struct lockdep_map *map)
+{
+	lock_map_acquire_read(map);
+}
+
+static inline void srcu_lock_release(struct lockdep_map *map)
+{
+	lock_map_release(map);
+}
+
+static inline void srcu_lock_sync(struct lockdep_map *map)
+{
+	lock_map_sync(map);
+}
+
 #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
@@ -109,6 +124,10 @@ static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
 	return 1;
 }
 
+#define srcu_lock_acquire(m) do { } while (0)
+#define srcu_lock_release(m) do { } while (0)
+#define srcu_lock_sync(m) do { } while (0)
+
 #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 #define SRCU_NMI_UNKNOWN	0x0
@@ -182,7 +201,7 @@ static inline int srcu_read_lock(struct srcu_struct *ssp) __acquires(ssp)
 
 	srcu_check_nmi_safety(ssp, false);
 	retval = __srcu_read_lock(ssp);
-	rcu_lock_acquire(&(ssp)->dep_map);
+	srcu_lock_acquire(&(ssp)->dep_map);
 	return retval;
 }
 
@@ -226,7 +245,7 @@ static inline void srcu_read_unlock(struct srcu_struct *ssp, int idx)
 {
 	WARN_ON_ONCE(idx & ~0x1);
 	srcu_check_nmi_safety(ssp, false);
-	rcu_lock_release(&(ssp)->dep_map);
+	srcu_lock_release(&(ssp)->dep_map);
 	__srcu_read_unlock(ssp, idx);
 }
 
kernel/rcu/srcutiny.c +2 -0
index b12fb0cec44d..336af24e0fe3 100644
@@ -197,6 +197,8 @@ void synchronize_srcu(struct srcu_struct *ssp)
 {
 	struct rcu_synchronize rs;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			lock_is_held(&rcu_bh_lock_map) ||
 			lock_is_held(&rcu_lock_map) ||
kernel/rcu/srcutree.c +2 -0
index ca4b5dcec675..408088c73e0e 100644
@@ -1267,6 +1267,8 @@ static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
 {
 	struct rcu_synchronize rcu;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			 lock_is_held(&rcu_bh_lock_map) ||
 			 lock_is_held(&rcu_lock_map) ||
Signature · 1 line
2.38.1
maintainer
#6 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

Quoted 24 lines · Boqun Feng
Quoted 23 lines · Paul E. McKenney
Quoted 14 lines · Boqun Feng

Although all flavors of RCU are annotated correctly with lockdep as recursive read locks, their 'check' parameter of lock_acquire() is unset. It means that RCU read locks are not added into the lockdep dependency graph therefore deadlock detection based on dependency graph won't catch deadlock caused by RCU. This is fine for "non-sleepable" RCU flavors since wait-context detection and other context based detection can catch these deadlocks. However for sleepable RCU, this is limited.

Actually we can detect the deadlocks caused by SRCU by 1) making srcu_read_lock() a 'check'ed recursive read lock and 2) making synchronize_srcu() a empty write lock critical section. Even better, with the newly introduced lock_sync(), we can avoid false positives about irq-unsafe/safe. So do it.

Quoted 5 lines

Note that NMI safe SRCU read side critical sections are currently not annonated, since step-by-step approach can help us deal with false-positives. These may be annotated in the future.

Nice, thank you!!!

Quoted 8 lines
Quoted 4 lines

Or if you would prefer that I take the series through -rcu, please just let me know.

I prefer that the first two patches go through your tree, because it reduces the synchronization among locking, rcu and KVM trees to the synchronization betwen rcu and KVM trees.

Very well, I have queued and pushed these with the usual wordsmithing, thank you!

On the possibility of annotating __srcu_read_lock_nmisafe() and __srcu_read_unlock_nmisafe(), are those lockdep annotations themselves NMI-safe?

Quoted 2 lines

For patch #3, since it's not really ready yet, so I don't know, but I guess when it's finished, probably better go through -rcu.

Please let me know when it is ready!

Thanx, Paul

Quoted 95 lines

Regards,
Boqun

Quoted 92 lines

Thanx, Paul

Quoted 90 lines
---
 include/linux/srcu.h  | 23 +++++++++++++++++++++--
 kernel/rcu/srcutiny.c |  2 ++
 kernel/rcu/srcutree.c |  2 ++
 3 files changed, 25 insertions(+), 2 deletions(-)
include/linux/srcu.h +21 -2
index 9b9d0bbf1d3c..a1595f8c5155 100644
@@ -102,6 +102,21 @@ static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
 	return lock_is_held(&ssp->dep_map);
 }
 
+static inline void srcu_lock_acquire(struct lockdep_map *map)
+{
+	lock_map_acquire_read(map);
+}
+
+static inline void srcu_lock_release(struct lockdep_map *map)
+{
+	lock_map_release(map);
+}
+
+static inline void srcu_lock_sync(struct lockdep_map *map)
+{
+	lock_map_sync(map);
+}
+
 #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
@@ -109,6 +124,10 @@ static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
 	return 1;
 }
 
+#define srcu_lock_acquire(m) do { } while (0)
+#define srcu_lock_release(m) do { } while (0)
+#define srcu_lock_sync(m) do { } while (0)
+
 #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 #define SRCU_NMI_UNKNOWN	0x0
@@ -182,7 +201,7 @@ static inline int srcu_read_lock(struct srcu_struct *ssp) __acquires(ssp)
 
 	srcu_check_nmi_safety(ssp, false);
 	retval = __srcu_read_lock(ssp);
-	rcu_lock_acquire(&(ssp)->dep_map);
+	srcu_lock_acquire(&(ssp)->dep_map);
 	return retval;
 }
 
@@ -226,7 +245,7 @@ static inline void srcu_read_unlock(struct srcu_struct *ssp, int idx)
 {
 	WARN_ON_ONCE(idx & ~0x1);
 	srcu_check_nmi_safety(ssp, false);
-	rcu_lock_release(&(ssp)->dep_map);
+	srcu_lock_release(&(ssp)->dep_map);
 	__srcu_read_unlock(ssp, idx);
 }
 
kernel/rcu/srcutiny.c +2 -0
index b12fb0cec44d..336af24e0fe3 100644
@@ -197,6 +197,8 @@ void synchronize_srcu(struct srcu_struct *ssp)
 {
 	struct rcu_synchronize rs;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			lock_is_held(&rcu_bh_lock_map) ||
 			lock_is_held(&rcu_lock_map) ||
kernel/rcu/srcutree.c +2 -0
index ca4b5dcec675..408088c73e0e 100644
@@ -1267,6 +1267,8 @@ static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
 {
 	struct rcu_synchronize rcu;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			 lock_is_held(&rcu_bh_lock_map) ||
 			 lock_is_held(&rcu_lock_map) ||
Signature · 1 line
2.38.1
maintainer
#7 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

Quoted 8 lines · Paul E. McKenney
Quoted 4 lines · Boqun Feng

On Fri, Jan 13, 2023 at 03:29:49AM -0800, Paul E. McKenney wrote:
I prefer that the first two patches go through your tree, because it reduces the synchronization among locking, rcu and KVM trees to the synchronization betwen rcu and KVM trees.

Very well, I have queued and pushed these with the usual wordsmithing, thank you!

I'm worried about this case:

CPU 0 CPU 1
-------------------- ------------------
lock A srcu lock B
srcu lock B lock A
srcu unlock B unlock A
unlock A srcu unlock B

While a bit unclean, there is nothing that downright forbids this; as long as synchronize_srcu does not happen inside lock A, no deadlock can occur.

However, if srcu is replaced with an rwlock then lockdep should and does report a deadlock. Boqun, do you get a false positive or do your patches correctly suppress this?

Paolo

author
#8 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

Quoted 19 lines · Paolo Bonzini
Quoted 8 lines · Paul E. McKenney
Quoted 4 lines · Boqun Feng

On Fri, Jan 13, 2023 at 03:29:49AM -0800, Paul E. McKenney wrote:
I prefer that the first two patches go through your tree, because it reduces the synchronization among locking, rcu and KVM trees to the synchronization betwen rcu and KVM trees.

Very well, I have queued and pushed these with the usual wordsmithing, thank you!

I'm worried about this case:

CPU 0 CPU 1
-------------------- ------------------
lock A srcu lock B
srcu lock B lock A
srcu unlock B unlock A
unlock A srcu unlock B

Quoted 3 lines

While a bit unclean, there is nothing that downright forbids this; as long as synchronize_srcu does not happen inside lock A, no deadlock can occur.

First, even with my change, lockdep won't report this as a deadlock because srcu_read_lock() is annotated as a recursive (unfair) read lock (the "read" parameter for lock_acquire() is 2) and in this case lockdep knows that it won't cause deadlock.

For SRCU, the annotation mapping that is 1) srcu_read_lock() is marked as recursive read lock and 2) synchronize_srcu() is marked as write lock sync, recursive read locks themselves cannot cause deadlocks and lockdep is aware of it.

Will add a selftest for this later.

Quoted 2 lines

However, if srcu is replaced with an rwlock then lockdep should and does report a deadlock. Boqun, do you get a false positive or do your patches

To be more precise, to have a deadlock, the read lock on CPU 0 has to be a *fair* read lock (i.e. non-recursive reader, the "read" parameter for lock_acquire is 1)

Quoted 2 lines

correctly suppress this?

I'm pretty sure that lockdep handles this ;-)

Regards,
Boqun

Quoted 2 lines

Paolo

maintainer
#9 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

Quoted 39 lines · Boqun Feng
Quoted 19 lines · Paolo Bonzini
Quoted 8 lines · Paul E. McKenney
Quoted 4 lines · Boqun Feng

On Fri, Jan 13, 2023 at 03:29:49AM -0800, Paul E. McKenney wrote:
I prefer that the first two patches go through your tree, because it reduces the synchronization among locking, rcu and KVM trees to the synchronization betwen rcu and KVM trees.

Very well, I have queued and pushed these with the usual wordsmithing, thank you!

I'm worried about this case:

CPU 0 CPU 1
-------------------- ------------------
lock A srcu lock B
srcu lock B lock A
srcu unlock B unlock A
unlock A srcu unlock B

Quoted 3 lines

While a bit unclean, there is nothing that downright forbids this; as long as synchronize_srcu does not happen inside lock A, no deadlock can occur.

First, even with my change, lockdep won't report this as a deadlock because srcu_read_lock() is annotated as a recursive (unfair) read lock (the "read" parameter for lock_acquire() is 2) and in this case lockdep knows that it won't cause deadlock.

For SRCU, the annotation mapping that is 1) srcu_read_lock() is marked as recursive read lock and 2) synchronize_srcu() is marked as write lock sync, recursive read locks themselves cannot cause deadlocks and lockdep is aware of it.

Will add a selftest for this later.

Quoted 2 lines

However, if srcu is replaced with an rwlock then lockdep should and does report a deadlock. Boqun, do you get a false positive or do your patches

Quoted 7 lines

To be more precise, to have a deadlock, the read lock on CPU 0 has to be a *fair* read lock (i.e. non-recursive reader, the "read" parameter for lock_acquire is 1)

Quoted 1 line

correctly suppress this?

I'm pretty sure that lockdep handles this ;-)

And lockdep agrees, refusing to complain about the following:

	idx = srcu_read_lock(&srcu1);
	mutex_lock(&mut1);
	mutex_unlock(&mut1);
	srcu_read_unlock(&srcu1, idx);

	mutex_lock(&mut1);
	idx = srcu_read_lock(&srcu1);
	srcu_read_unlock(&srcu1, idx);
	mutex_unlock(&mut1);

							Thanx, Paul
#10 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

In reply to Boqun Feng

On 12 Jan 2023 22:59:54 -0800 Boqun Feng <[email protected]>

Quoted 13 lines
kernel/rcu/srcutree.c +2 -0
@@ -1267,6 +1267,8 @@ static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
 {
 	struct rcu_synchronize rcu;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			 lock_is_held(&rcu_bh_lock_map) ||
 			 lock_is_held(&rcu_lock_map) ||
Signature · 1 line
2.38.1

The following deadlock is able to escape srcu_lock_sync() because the __lock_release folded in sync leaves one lock on the sync side.

	cpu9		cpu0
	---		---
	lock A		srcu_lock_acquire(&ssp->dep_map);
	srcu_lock_sync(&ssp->dep_map);
			lock A
author
#11 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

Quoted 18 lines · Hillf Danton

On 12 Jan 2023 22:59:54 -0800 Boqun Feng <[email protected]>

Quoted 13 lines
kernel/rcu/srcutree.c +2 -0
@@ -1267,6 +1267,8 @@ static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
 {
 	struct rcu_synchronize rcu;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			 lock_is_held(&rcu_bh_lock_map) ||
 			 lock_is_held(&rcu_lock_map) ||
Signature · 1 line
2.38.1

The following deadlock is able to escape srcu_lock_sync() because the __lock_release folded in sync leaves one lock on the sync side.

Quoted 5 lines
	cpu9		cpu0
	---		---
	lock A		srcu_lock_acquire(&ssp->dep_map);
	srcu_lock_sync(&ssp->dep_map);
			lock A

But isn't it just the srcu_mutex_ABBA test case in patch #3, and my run of lockdep selftest shows we can catch it. Anything subtle I'm missing?

Regards,
Boqun

#12 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

On 13 Jan 2023 09:58:10 -0800 Boqun Feng <[email protected]>

Quoted 19 lines · Hillf Danton
Quoted 18 lines

On 12 Jan 2023 22:59:54 -0800 Boqun Feng <[email protected]>

Quoted 13 lines
kernel/rcu/srcutree.c +2 -0
@@ -1267,6 +1267,8 @@ static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
 {
 	struct rcu_synchronize rcu;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			 lock_is_held(&rcu_bh_lock_map) ||
 			 lock_is_held(&rcu_lock_map) ||
Signature · 1 line
2.38.1

The following deadlock is able to escape srcu_lock_sync() because the __lock_release folded in sync leaves one lock on the sync side.

Quoted 8 lines
Quoted 5 lines
	cpu9		cpu0
	---		---
	lock A		srcu_lock_acquire(&ssp->dep_map);
	srcu_lock_sync(&ssp->dep_map);
			lock A

But isn't it just the srcu_mutex_ABBA test case in patch #3, and my run of lockdep selftest shows we can catch it. Anything subtle I'm missing?

I am leaning to not call it ABBA deadlock, because B is unlocked.

	task X		task Y
	---		---
	lock A
	lock B
			lock B
	unlock B
	wait_for_completion E

			lock A
			complete E

And no deadlock should be detected/caught after B goes home.

author
#13 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

Quoted 42 lines · Hillf Danton

On 13 Jan 2023 09:58:10 -0800 Boqun Feng <[email protected]>

Quoted 19 lines · Hillf Danton
Quoted 18 lines

On 12 Jan 2023 22:59:54 -0800 Boqun Feng <[email protected]>

Quoted 13 lines
kernel/rcu/srcutree.c +2 -0
@@ -1267,6 +1267,8 @@ static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
 {
 	struct rcu_synchronize rcu;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			 lock_is_held(&rcu_bh_lock_map) ||
 			 lock_is_held(&rcu_lock_map) ||
Signature · 1 line
2.38.1

The following deadlock is able to escape srcu_lock_sync() because the __lock_release folded in sync leaves one lock on the sync side.

Quoted 8 lines
Quoted 5 lines
	cpu9		cpu0
	---		---
	lock A		srcu_lock_acquire(&ssp->dep_map);
	srcu_lock_sync(&ssp->dep_map);
			lock A

But isn't it just the srcu_mutex_ABBA test case in patch #3, and my run of lockdep selftest shows we can catch it. Anything subtle I'm missing?

I am leaning to not call it ABBA deadlock, because B is unlocked.

	task X		task Y
	---		---
	lock A
	lock B
			lock B
	unlock B
	wait_for_completion E

			lock A
			complete E
Quoted 1 line

And no deadlock should be detected/caught after B goes home.

Your example makes me more confused.. given the case:

	task X		task Y
	---		---
	mutex_lock(A);
			srcu_read_lock(B);
	synchronze_srcu(B);
			mutex_lock(A);

isn't it a deadlock? If your example, A, B or E which one is srcu?

Regards,
Boqun

#14 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

On Fri, 13 Jan 2023 16:17:59 -0800 Boqun Feng <[email protected]>

Quoted 47 lines · Hillf Danton
Quoted 42 lines

On 13 Jan 2023 09:58:10 -0800 Boqun Feng <[email protected]>

Quoted 19 lines · Hillf Danton
Quoted 18 lines

On 12 Jan 2023 22:59:54 -0800 Boqun Feng <[email protected]>

Quoted 13 lines
kernel/rcu/srcutree.c +2 -0
@@ -1267,6 +1267,8 @@ static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
 {
 	struct rcu_synchronize rcu;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			 lock_is_held(&rcu_bh_lock_map) ||
 			 lock_is_held(&rcu_lock_map) ||
Signature · 1 line
2.38.1

The following deadlock is able to escape srcu_lock_sync() because the __lock_release folded in sync leaves one lock on the sync side.

Quoted 8 lines
Quoted 5 lines
	cpu9		cpu0
	---		---
	lock A		srcu_lock_acquire(&ssp->dep_map);
	srcu_lock_sync(&ssp->dep_map);
			lock A

But isn't it just the srcu_mutex_ABBA test case in patch #3, and my run of lockdep selftest shows we can catch it. Anything subtle I'm missing?

I am leaning to not call it ABBA deadlock, because B is unlocked.

	task X		task Y
	---		---
	lock A
	lock B
			lock B
	unlock B
	wait_for_completion E

			lock A
			complete E
Quoted 1 line

And no deadlock should be detected/caught after B goes home.

Your example makes me more confused.. given the case:

Quoted 8 lines
	task X		task Y
	---		---
	mutex_lock(A);
			srcu_read_lock(B);
	synchronze_srcu(B);
			mutex_lock(A);

isn't it a deadlock?

Yes and nope, see below.

Quoted 1 line

If your example, A, B or E which one is srcu?

A and B are mutex, and E is completion in my example to show the failure of catching deadlock in case of non-fake lock. Now see srcu after your change.

task X task Y
--- ---
mutex_lock(A);

 				srcu_read_lock(B);
				srcu_lock_acquire(&B->dep_map);
				a) lock_map_acquire_read(&B->dep_map);
 	synchronze_srcu(B);
	__synchronize_srcu(B);
	srcu_lock_sync(&B->dep_map);
	lock_map_sync(&B->dep_map);
	lock_sync(&B->dep_map);
	__lock_acquire(&B->dep_map);
				b) lock_map_acquire_read(&B->dep_map);
	__lock_release(&B->dep_map);
				c) lock_map_acquire_read(&B->dep_map);

mutex_lock(A);

No deadlock could be detected if taskY takes mutexA after taskX releases B, and how taskY acquires B does not matter as per the a), b) and c) modes in the above chart, again because releasing lock can break deadlock in general.

author
#15 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

Quoted 68 lines · Hillf Danton

On Fri, 13 Jan 2023 16:17:59 -0800 Boqun Feng <[email protected]>

Quoted 47 lines · Hillf Danton
Quoted 42 lines

On 13 Jan 2023 09:58:10 -0800 Boqun Feng <[email protected]>

Quoted 19 lines · Hillf Danton
Quoted 18 lines

On 12 Jan 2023 22:59:54 -0800 Boqun Feng <[email protected]>

Quoted 13 lines
kernel/rcu/srcutree.c +2 -0
@@ -1267,6 +1267,8 @@ static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
 {
 	struct rcu_synchronize rcu;
 
+	srcu_lock_sync(&ssp->dep_map);
+
 	RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
 			 lock_is_held(&rcu_bh_lock_map) ||
 			 lock_is_held(&rcu_lock_map) ||
Signature · 1 line
2.38.1

The following deadlock is able to escape srcu_lock_sync() because the __lock_release folded in sync leaves one lock on the sync side.

Quoted 8 lines
Quoted 5 lines
	cpu9		cpu0
	---		---
	lock A		srcu_lock_acquire(&ssp->dep_map);
	srcu_lock_sync(&ssp->dep_map);
			lock A

But isn't it just the srcu_mutex_ABBA test case in patch #3, and my run of lockdep selftest shows we can catch it. Anything subtle I'm missing?

I am leaning to not call it ABBA deadlock, because B is unlocked.

	task X		task Y
	---		---
	lock A
	lock B
			lock B
	unlock B
	wait_for_completion E

			lock A
			complete E
Quoted 1 line

And no deadlock should be detected/caught after B goes home.

Your example makes me more confused.. given the case:

Quoted 8 lines
	task X		task Y
	---		---
	mutex_lock(A);
			srcu_read_lock(B);
	synchronze_srcu(B);
			mutex_lock(A);

isn't it a deadlock?

Yes and nope, see below.

Quoted 1 line

If your example, A, B or E which one is srcu?

A and B are mutex, and E is completion in my example to show the failure of catching deadlock in case of non-fake lock. Now see srcu after your change.

(quoted diff) +0 -0
 	task X			task Y
 	---			---
 	mutex_lock(A);
 				srcu_read_lock(B);
Quoted 8 lines
				srcu_lock_acquire(&B->dep_map);
				a) lock_map_acquire_read(&B->dep_map);
 	synchronze_srcu(B);
	__synchronize_srcu(B);
	srcu_lock_sync(&B->dep_map);
	lock_map_sync(&B->dep_map);
	lock_sync(&B->dep_map);
	__lock_acquire(&B->dep_map);

At this time, lockdep add dependency A -> B in the dependency graph.

Quoted 4 lines
				b) lock_map_acquire_read(&B->dep_map);
	__lock_release(&B->dep_map);
				c) lock_map_acquire_read(&B->dep_map);

mutex_lock(A);

and here, lockdep will try to add dependency B -> A into the dependency graph, and find that A -> B -> A will form a circle (with strong dependency), therefore lockdep knows it's a deadlock.

Quoted 2 lines

No deadlock could be detected if taskY takes mutexA after taskX releases B,

The timing that taskX releases B doesn't master, since lockdep uses graph to detect deadlocks rather than after-fact detection.

Quoted 2 lines

and how taskY acquires B does not matter as per the a), b) and c) modes in the above chart, again because releasing lock can break deadlock in general.

I have test cases showing the above deadlock can be detected, so if you think there is a deadlock that may dodge from my change, feel free to add a test case in lib/locking-selftest.c ;-)

Regards,
Boqun

#16 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

On Fri, 13 Jan 2023 23:32:01 -0800 Boqun Feng <[email protected]>

Quoted 17 lines · Hillf Danton
Quoted 5 lines
(quoted diff) +0 -0
 	task X			task Y
 	---			---
 	mutex_lock(A);
 				srcu_read_lock(B);
Quoted 8 lines
				srcu_lock_acquire(&B->dep_map);
				a) lock_map_acquire_read(&B->dep_map);
 	synchronze_srcu(B);
	__synchronize_srcu(B);
	srcu_lock_sync(&B->dep_map);
	lock_map_sync(&B->dep_map);
	lock_sync(&B->dep_map);
	__lock_acquire(&B->dep_map);

At this time, lockdep add dependency A -> B in the dependency graph.

Quoted 8 lines
Quoted 4 lines
				b) lock_map_acquire_read(&B->dep_map);
	__lock_release(&B->dep_map);
				c) lock_map_acquire_read(&B->dep_map);

mutex_lock(A);

and here, lockdep will try to add dependency B -> A into the dependency graph, and find that A -> B -> A will form a circle (with strong dependency), therefore lockdep knows it's a deadlock.

Is the strong dependency applying to mode c)?
If yes then deadlock should be also detected in the following locking pattern that has no deadlock.

	cpu0			cpu1
	---			---
	mutex_lock A
	mutex_lock B
	mutex_unlock B
				mutex_lock B
				mutex_lock A
Quoted 16 lines
Quoted 3 lines

No deadlock could be detected if taskY takes mutexA after taskX releases B,

The timing that taskX releases B doesn't master, since lockdep uses graph to detect deadlocks rather than after-fact detection.

Quoted 2 lines

and how taskY acquires B does not matter as per the a), b) and c) modes in the above chart, again because releasing lock can break deadlock in general.

I have test cases showing the above deadlock can be detected, so if you think there is a deadlock that may dodge from my change, feel free to add a test case in lib/locking-selftest.c ;-)

Regards,
Boqun

author
#17 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

Quoted 31 lines · Hillf Danton

On Fri, 13 Jan 2023 23:32:01 -0800 Boqun Feng <[email protected]>

Quoted 17 lines · Hillf Danton
Quoted 5 lines
(quoted diff) +0 -0
 	task X			task Y
 	---			---
 	mutex_lock(A);
 				srcu_read_lock(B);
Quoted 8 lines
				srcu_lock_acquire(&B->dep_map);
				a) lock_map_acquire_read(&B->dep_map);
 	synchronze_srcu(B);
	__synchronize_srcu(B);
	srcu_lock_sync(&B->dep_map);
	lock_map_sync(&B->dep_map);
	lock_sync(&B->dep_map);
	__lock_acquire(&B->dep_map);

At this time, lockdep add dependency A -> B in the dependency graph.

Quoted 8 lines
Quoted 4 lines
				b) lock_map_acquire_read(&B->dep_map);
	__lock_release(&B->dep_map);
				c) lock_map_acquire_read(&B->dep_map);

mutex_lock(A);

and here, lockdep will try to add dependency B -> A into the dependency graph, and find that A -> B -> A will form a circle (with strong dependency), therefore lockdep knows it's a deadlock.

Is the strong dependency applying to mode c)?
If yes then deadlock should be also detected in the following locking pattern that has no deadlock.

Quoted 7 lines
	cpu0			cpu1
	---			---
	mutex_lock A
	mutex_lock B
	mutex_unlock B
				mutex_lock B
				mutex_lock A

Well, of course, this is how lockdep works. Lockdep detects the *potential* deadlocks rather than detects the deadlocks when they really happen. Otherwise lockdep is useless.

The execution in your example shows the potential deadlocks, i.e. one task acquires A and then acquires B, the other task acquires B and then acquires A. Potential deadlocks mean given a correct timing, a deadlock may happen.

Regards,
Boqun

Quoted 16 lines
Quoted 16 lines
Quoted 3 lines

No deadlock could be detected if taskY takes mutexA after taskX releases B,

The timing that taskX releases B doesn't master, since lockdep uses graph to detect deadlocks rather than after-fact detection.

Quoted 2 lines

and how taskY acquires B does not matter as per the a), b) and c) modes in the above chart, again because releasing lock can break deadlock in general.

I have test cases showing the above deadlock can be detected, so if you think there is a deadlock that may dodge from my change, feel free to add a test case in lib/locking-selftest.c ;-)

Regards,
Boqun

reviewer
#18 lore raw

Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks

In reply to Boqun Feng
Quoted 39 lines · Boqun Feng

Although all flavors of RCU are annotated correctly with lockdep as recursive read locks, their 'check' parameter of lock_acquire() is unset. It means that RCU read locks are not added into the lockdep dependency graph therefore deadlock detection based on dependency graph won't catch deadlock caused by RCU. This is fine for "non-sleepable" RCU flavors since wait-context detection and other context based detection can catch these deadlocks. However for sleepable RCU, this is limited.

Actually we can detect the deadlocks caused by SRCU by 1) making srcu_read_lock() a 'check'ed recursive read lock and 2) making synchronize_srcu() a empty write lock critical section. Even better, with the newly introduced lock_sync(), we can avoid false positives about irq-unsafe/safe. So do it.

Note that NMI safe SRCU read side critical sections are currently not annonated, since step-by-step approach can help us deal with false-positives. These may be annotated in the future.

---
  include/linux/srcu.h  | 23 +++++++++++++++++++++--
  kernel/rcu/srcutiny.c |  2 ++
  kernel/rcu/srcutree.c |  2 ++
  3 files changed, 25 insertions(+), 2 deletions(-)
include/linux/srcu.h +6 -0
index 9b9d0bbf1d3c..a1595f8c5155 100644
@@ -102,6 +102,21 @@ static inline int srcu_read_lock_held(const struct srcu_struct *ssp)
  	return lock_is_held(&ssp->dep_map);
  }
 
+static inline void srcu_lock_acquire(struct lockdep_map *map)
+{
+	lock_map_acquire_read(map);
+}
+
+static inline void srcu_lock_release(struct lockdep_map *map)

include/linux/srcu.h static inline int srcu_read_lock_held(const struct srcu_struct *ssp) · line 120

Quoted 10 lines
include/linux/srcu.h +9 -0
+{
+	lock_map_release(map);
+}
+
+static inline void srcu_lock_sync(struct lockdep_map *map)
+{
+	lock_map_sync(map);
+}
+
  #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */

It would be nice if a comment is added to document the difference between the 2 sets of rcu_lock_* and srcu_lock_* functions. It is described in patch description, but it is not easy to figure that out just by looking at the source files.

Cheers,
Longman

author
#19 lore raw

PATCH 3/3 WIP: locking/lockdep: selftests: Add selftests for SRCU

In reply to Boqun Feng
---
 lib/locking-selftest.c | 71 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 71 insertions(+)
lib/locking-selftest.c +71 -0
index 8d24279fad05..5fc206a2f9f1 100644
@@ -60,6 +60,7 @@ __setup("debug_locks_verbose=", setup_debug_locks_verbose);
 #define LOCKTYPE_RTMUTEX 0x20
 #define LOCKTYPE_LL	0x40
 #define LOCKTYPE_SPECIAL 0x80
+#define LOCKTYPE_SRCU	0x100
 
 static struct ww_acquire_ctx t, t2;
 static struct ww_mutex o, o2, o3;
@@ -100,6 +101,13 @@ static DEFINE_RT_MUTEX(rtmutex_D);
 
 #endif
 
+#ifdef CONFIG_SRCU
+static struct lock_class_key srcu_A_key;
+static struct lock_class_key srcu_B_key;
+static struct srcu_struct srcu_A;
+static struct srcu_struct srcu_B;
+#endif
+
 /*
  * Locks that we initialize dynamically as well so that
  * e.g. X1 and X2 becomes two instances of the same class,
@@ -1418,6 +1426,12 @@ static void reset_locks(void)
 	memset(&ww_lockdep.acquire_key, 0, sizeof(ww_lockdep.acquire_key));
 	memset(&ww_lockdep.mutex_key, 0, sizeof(ww_lockdep.mutex_key));
 	local_irq_enable();
+
+#ifdef CONFIG_SRCU
+	__init_srcu_struct(&srcu_A, "srcuA", &srcu_A_key);
+	__init_srcu_struct(&srcu_B, "srcuB", &srcu_B_key);
+#endif
+
 }
 
 #undef I
@@ -2360,6 +2374,58 @@ static void ww_tests(void)
 	pr_cont("\n");
 }
 
+static void srcu_ABBA(void)
+{
+	int ia, ib;
+
+	ia = srcu_read_lock(&srcu_A);
+	synchronize_srcu(&srcu_B);
+	srcu_read_unlock(&srcu_A, ia);
+
+	ib = srcu_read_lock(&srcu_B);
+	synchronize_srcu(&srcu_A);
+	srcu_read_unlock(&srcu_B, ib); // should fail
+}
+
+static void srcu_mutex_ABBA(void)
+{
+	int ia;
+
+	mutex_lock(&mutex_A);
+	synchronize_srcu(&srcu_A);
+	mutex_unlock(&mutex_A);
+
+	ia = srcu_read_lock(&srcu_A);
+	mutex_lock(&mutex_A);
+	mutex_unlock(&mutex_A);
+	srcu_read_unlock(&srcu_A, ia); // should fail
+}
+
+static void srcu_irqsafe(void)
+{
+	int ia;
+
+	HARDIRQ_ENTER();
+	ia = srcu_read_lock(&srcu_A);
+	srcu_read_unlock(&srcu_A, ia);
+	HARDIRQ_EXIT();
+
+	synchronize_srcu(&srcu_A); // should NOT fail
+}
+
+static void srcu_tests(void)
+{
+	printk("  --------------------------------------------------------------------------\n");
+	printk("  | SRCU tests |\n");
+	printk("  ---------------\n");
+	print_testname("ABBA read-sync/read-sync");
+	dotest(srcu_ABBA, FAILURE, LOCKTYPE_SRCU);
+	print_testname("ABBA mutex-sync/read-mutex");
+	dotest(srcu_mutex_ABBA, FAILURE, LOCKTYPE_SRCU);
+	print_testname("Irqsafe synchronize_srcu");
+	dotest(srcu_irqsafe, SUCCESS, LOCKTYPE_SRCU);
+	pr_cont("\n");
+}
 
 /*
  * <in hardirq handler>
@@ -2881,6 +2947,10 @@ void locking_selftest(void)
 	printk("  --------------------------------------------------------------------------\n");
 
 	init_shared_classes();
+#ifdef CONFIG_SRCU
+	__init_srcu_struct(&srcu_A, "srcuA", &srcu_A_key);
+	__init_srcu_struct(&srcu_B, "srcuB", &srcu_B_key);
+#endif
 	lockdep_set_selftest_task(current);
 
 	DO_TESTCASE_6R("A-A deadlock", AA);
@@ -2965,6 +3035,7 @@ void locking_selftest(void)
 	DO_TESTCASE_6x2x2RW("irq read-recursion #3", irq_read_recursion3);
 
 	ww_tests();
+	srcu_tests();
 
 	force_read_lock_recursive = 0;
 	/*
Signature · 1 line
2.38.1
#20 lore raw

cover KVM: Make use of SRCU deadlock detection support

In reply to Boqun Feng
Quoted 11 lines · Boqun Feng

This is actually a leftover of the recursive read deadlock detection patchset:

        https://lore.kernel.org/lkml/[email protected]/

I resolve comments then and add more test cases, and hopefully this can fulfill the request from KVM:

        https://lore.kernel.org/lkml/[email protected]/

;-)

It definitely seems to work; thank you! I can revert some of the recent fixes from the KVM tree, apply your patches, and then I can trigger the lockdep warnings. To make it reliably trigger, we need to artificially call synchronize_srcu(&kvm->srcu) under kvm->lock on KVM init, because the circumstances under which that happens are a bit esoteric and don't always happen otherwise, so lockdep wouldn't notice.

Quoted 7 lines

The patch #3 is now WIP for two reasons:

* It may conflicts with Paul's patchset on removing CONFIG_SRCU

* I haven't found a proper way to "reinit" srcu_struct when
lockdep selftest runs: cleanup_srcu_struct() needs workqueue however the tests can run before there is one.

Understood. I think the KVM series which follows can stand alone and go via the KVM tree separately. As and when your series gets merged, it'll serve to protect against regressions.

Thanks again!

David Woodhouse (3):
KVM: Show lockdep the kvm->mutex vs. kvm->srcu ordering rule
KVM: selftests: Use enum for test numbers in xen_shinfo_test
KVM: selftests: Add EVTCHNOP_send slow path test to xen_shinfo_test

 .../testing/selftests/kvm/x86_64/xen_shinfo_test.c | 165 ++++++++++++++-------
 virt/kvm/kvm_main.c                                |  10 ++
 2 files changed, 124 insertions(+), 51 deletions(-)
#21 lore raw

PATCH 1/3 KVM: Show lockdep the kvm->mutex vs. kvm->srcu ordering rule

From: David Woodhouse <[email protected]>

Lockdep is learning to spot deadlocks with sleepable RCU vs. mutexes, which can occur where one code path calls synchronize_scru() with a mutex held, while another code path attempts to obtain the same mutex while in a read-side section.

Since lockdep isn't very good at reading the English prose in Documentation/virt/kvm/locking.rst, give it a demonstration by calling synchronize_scru(&kvm->srcu) while holding kvm->lock in kvm_create_vm(). The cases where this happens naturally are relatively esoteric and may not happen otherwise.

---
 virt/kvm/kvm_main.c | 10 ++++++++++
 1 file changed, 10 insertions(+)
virt/kvm/kvm_main.c +10 -0
index 13e88297f999..285b3c5a6364 100644
@@ -1173,6 +1173,16 @@ static struct kvm *kvm_create_vm(unsigned long type, const char *fdname)
 	if (init_srcu_struct(&kvm->irq_srcu))
 		goto out_err_no_irq_srcu;
 
+#ifdef CONFIG_LOCKDEP
+	/*
+	 * Ensure lockdep knows that it's not permitted to lock kvm->lock
+	 * from a SRCU read section on kvm->srcu.
+	 */
+	mutex_lock(&kvm->lock);
+	synchronize_srcu(&kvm->srcu);
+	mutex_unlock(&kvm->lock);
+#endif
+
 	refcount_set(&kvm->users_count, 1);
 	for (i = 0; i < KVM_ADDRESS_SPACE_NUM; i++) {
 		for (j = 0; j < 2; j++) {
Signature · 1 line
2.35.3
#22 lore raw

PATCH 2/3 KVM: selftests: Use enum for test numbers in xen_shinfo_test

In reply to David Woodhouse

From: David Woodhouse <[email protected]>

The xen_shinfo_test started off with very few iterations, and the numbers we used in GUEST_SYNC() were precisely mapped to the RUNSTATE_xxx values anyway to start with.

It has since grown quite a few more tests, and it's kind of awful to be handling them all as bare numbers. Especially when I want to add a new test in the middle. Define an enum for the test stages, and use it both in the guest code and the host switch statement.

No functional change, if I can count to 24.

---
 .../selftests/kvm/x86_64/xen_shinfo_test.c    | 134 +++++++++++-------
 1 file changed, 83 insertions(+), 51 deletions(-)
tools/testing/selftests/kvm/x86_64/xen_shinfo_test.c +83 -51
index 721f6a693799..644d614a9965 100644
@@ -44,6 +44,36 @@
 #define EVTCHN_TEST2 66
 #define EVTCHN_TIMER 13
 
+enum {
+	TEST_INJECT_VECTOR = 0,
+	TEST_RUNSTATE_runnable,
+	TEST_RUNSTATE_blocked,
+	TEST_RUNSTATE_offline,
+	TEST_RUNSTATE_ADJUST,
+	TEST_RUNSTATE_DATA,
+	TEST_STEAL_TIME,
+	TEST_EVTCHN_MASKED,
+	TEST_EVTCHN_UNMASKED,
+	TEST_EVTCHN_SLOWPATH,
+	TEST_EVTCHN_SEND_IOCTL,
+	TEST_EVTCHN_HCALL,
+	TEST_EVTCHN_HCALL_EVENTFD,
+	TEST_TIMER_SETUP,
+	TEST_TIMER_WAIT,
+	TEST_TIMER_RESTORE,
+	TEST_POLL_READY,
+	TEST_POLL_TIMEOUT,
+	TEST_POLL_MASKED,
+	TEST_POLL_WAKE,
+	TEST_TIMER_PAST,
+	TEST_LOCKING_SEND_RACE,
+	TEST_LOCKING_POLL_RACE,
+	TEST_LOCKING_POLL_TIMEOUT,
+	TEST_DONE,
+
+	TEST_GUEST_SAW_IRQ,
+};
+
 #define XEN_HYPERCALL_MSR	0x40000000
 
 #define MIN_STEAL_TIME		50000
@@ -147,7 +177,7 @@ static void evtchn_handler(struct ex_regs *regs)
 	vi->evtchn_pending_sel = 0;
 	guest_saw_irq = true;
 
-	GUEST_SYNC(0x20);
+	GUEST_SYNC(TEST_GUEST_SAW_IRQ);
 }
 
 static void guest_wait_for_irq(void)
@@ -168,41 +198,41 @@ static void guest_code(void)
 	);
 
 	/* Trigger an interrupt injection */
-	GUEST_SYNC(0);
+	GUEST_SYNC(TEST_INJECT_VECTOR);
 
 	guest_wait_for_irq();
 
 	/* Test having the host set runstates manually */
-	GUEST_SYNC(RUNSTATE_runnable);
+	GUEST_SYNC(TEST_RUNSTATE_runnable);
 	GUEST_ASSERT(rs->time[RUNSTATE_runnable] != 0);
 	GUEST_ASSERT(rs->state == 0);
 
-	GUEST_SYNC(RUNSTATE_blocked);
+	GUEST_SYNC(TEST_RUNSTATE_blocked);
 	GUEST_ASSERT(rs->time[RUNSTATE_blocked] != 0);
 	GUEST_ASSERT(rs->state == 0);
 
-	GUEST_SYNC(RUNSTATE_offline);
+	GUEST_SYNC(TEST_RUNSTATE_offline);
 	GUEST_ASSERT(rs->time[RUNSTATE_offline] != 0);
 	GUEST_ASSERT(rs->state == 0);
 
 	/* Test runstate time adjust */
-	GUEST_SYNC(4);
+	GUEST_SYNC(TEST_RUNSTATE_ADJUST);
 	GUEST_ASSERT(rs->time[RUNSTATE_blocked] == 0x5a);
 	GUEST_ASSERT(rs->time[RUNSTATE_offline] == 0x6b6b);
 
 	/* Test runstate time set */
-	GUEST_SYNC(5);
+	GUEST_SYNC(TEST_RUNSTATE_DATA);
 	GUEST_ASSERT(rs->state_entry_time >= 0x8000);
 	GUEST_ASSERT(rs->time[RUNSTATE_runnable] == 0);
 	GUEST_ASSERT(rs->time[RUNSTATE_blocked] == 0x6b6b);
 	GUEST_ASSERT(rs->time[RUNSTATE_offline] == 0x5a);
 
 	/* sched_yield() should result in some 'runnable' time */
-	GUEST_SYNC(6);
+	GUEST_SYNC(TEST_STEAL_TIME);
 	GUEST_ASSERT(rs->time[RUNSTATE_runnable] >= MIN_STEAL_TIME);
 
 	/* Attempt to deliver a *masked* interrupt */
-	GUEST_SYNC(7);
+	GUEST_SYNC(TEST_EVTCHN_MASKED);
 
 	/* Wait until we see the bit set */
 	struct shared_info *si = (void *)SHINFO_VADDR;
@@ -210,21 +240,21 @@ static void guest_code(void)
 		__asm__ __volatile__ ("rep nop" : : : "memory");
 
 	/* Now deliver an *unmasked* interrupt */
-	GUEST_SYNC(8);
+	GUEST_SYNC(TEST_EVTCHN_UNMASKED);
 
 	guest_wait_for_irq();
 
 	/* Change memslots and deliver an interrupt */
-	GUEST_SYNC(9);
+	GUEST_SYNC(TEST_EVTCHN_SLOWPATH);
 
 	guest_wait_for_irq();
 
 	/* Deliver event channel with KVM_XEN_HVM_EVTCHN_SEND */
-	GUEST_SYNC(10);
+	GUEST_SYNC(TEST_EVTCHN_SEND_IOCTL);
 
 	guest_wait_for_irq();
 
-	GUEST_SYNC(11);
+	GUEST_SYNC(TEST_EVTCHN_HCALL);
 
 	/* Our turn. Deliver event channel (to ourselves) with
 	 * EVTCHNOP_send hypercall. */
@@ -240,7 +270,7 @@ static void guest_code(void)
 
 	guest_wait_for_irq();
 
-	GUEST_SYNC(12);
+	GUEST_SYNC(TEST_EVTCHN_HCALL_EVENTFD);
 
 	/* Deliver "outbound" event channel to an eventfd which
 	 * happens to be one of our own irqfds. */
@@ -255,7 +285,7 @@ static void guest_code(void)
 
 	guest_wait_for_irq();
 
-	GUEST_SYNC(13);
+	GUEST_SYNC(TEST_TIMER_SETUP);
 
 	/* Set a timer 100ms in the future. */
 	__asm__ __volatile__ ("vmcall" :
@@ -264,17 +294,17 @@ static void guest_code(void)
 			      "D" (rs->state_entry_time + 100000000));
 	GUEST_ASSERT(rax == 0);
 
-	GUEST_SYNC(14);
+	GUEST_SYNC(TEST_TIMER_WAIT);
 
 	/* Now wait for the timer */
 	guest_wait_for_irq();
 
-	GUEST_SYNC(15);
+	GUEST_SYNC(TEST_TIMER_RESTORE);
 
 	/* The host has 'restored' the timer. Just wait for it. */
 	guest_wait_for_irq();
 
-	GUEST_SYNC(16);
+	GUEST_SYNC(TEST_POLL_READY);
 
 	/* Poll for an event channel port which is already set */
 	u32 ports[1] = { EVTCHN_TIMER };
@@ -292,7 +322,7 @@ static void guest_code(void)
 
 	GUEST_ASSERT(rax == 0);
 
-	GUEST_SYNC(17);
+	GUEST_SYNC(TEST_POLL_TIMEOUT);
 
 	/* Poll for an unset port and wait for the timeout. */
 	p.timeout = 100000000;
@@ -304,7 +334,7 @@ static void guest_code(void)
 
 	GUEST_ASSERT(rax == 0);
 
-	GUEST_SYNC(18);
+	GUEST_SYNC(TEST_POLL_MASKED);
 
 	/* A timer will wake the masked port we're waiting on, while we poll */
 	p.timeout = 0;
@@ -316,7 +346,7 @@ static void guest_code(void)
 
 	GUEST_ASSERT(rax == 0);
 
-	GUEST_SYNC(19);
+	GUEST_SYNC(TEST_POLL_WAKE);
 
 	/* A timer wake an *unmasked* port which should wake us with an
 	 * actual interrupt, while we're polling on a different port. */
@@ -332,17 +362,17 @@ static void guest_code(void)
 
 	guest_wait_for_irq();
 
-	GUEST_SYNC(20);
+	GUEST_SYNC(TEST_TIMER_PAST);
 
 	/* Timer should have fired already */
 	guest_wait_for_irq();
 
-	GUEST_SYNC(21);
+	GUEST_SYNC(TEST_LOCKING_SEND_RACE);
 	/* Racing host ioctls */
 
 	guest_wait_for_irq();
 
-	GUEST_SYNC(22);
+	GUEST_SYNC(TEST_LOCKING_POLL_RACE);
 	/* Racing vmcall against host ioctl */
 
 	ports[0] = 0;
@@ -375,12 +405,12 @@ static void guest_code(void)
 	 * expiring while the event channel was invalid.
 	 */
 	if (!guest_saw_irq) {
-		GUEST_SYNC(23);
+		GUEST_SYNC(TEST_LOCKING_POLL_TIMEOUT);
 		goto wait_for_timer;
 	}
 	guest_saw_irq = false;
 
-	GUEST_SYNC(24);
+	GUEST_SYNC(TEST_DONE);
 }
 
 static int cmp_timespec(struct timespec *a, struct timespec *b)
@@ -439,6 +469,7 @@ int main(int argc, char *argv[])
 	bool verbose;
 	int ret;
 
+	printf("TEST_DONE is %d\n", TEST_DONE);
 	verbose = argc > 1 && (!strncmp(argv[1], "-v", 3) ||
 			       !strncmp(argv[1], "--verbose", 10));
 
@@ -649,25 +680,26 @@ int main(int argc, char *argv[])
 					    "runstate times don't add up");
 
 			switch (uc.args[1]) {
-			case 0:
+			case TEST_INJECT_VECTOR:
 				if (verbose)
 					printf("Delivering evtchn upcall\n");
 				evtchn_irq_expected = true;
 				vinfo->evtchn_upcall_pending = 1;
 				break;
 
-			case RUNSTATE_runnable...RUNSTATE_offline:
+			case TEST_RUNSTATE_runnable...TEST_RUNSTATE_offline:
 				TEST_ASSERT(!evtchn_irq_expected, "Event channel IRQ not seen");
 				if (!do_runstate_tests)
 					goto done;
 				if (verbose)
 					printf("Testing runstate %s\n", runstate_names[uc.args[1]]);
 				rst.type = KVM_XEN_VCPU_ATTR_TYPE_RUNSTATE_CURRENT;
-				rst.u.runstate.state = uc.args[1];
+				rst.u.runstate.state = uc.args[1] + RUNSTATE_runnable -
+					TEST_RUNSTATE_runnable;
 				vcpu_ioctl(vcpu, KVM_XEN_VCPU_SET_ATTR, &rst);
 				break;
 
-			case 4:
+			case TEST_RUNSTATE_ADJUST:
 				if (verbose)
 					printf("Testing RUNSTATE_ADJUST\n");
 				rst.type = KVM_XEN_VCPU_ATTR_TYPE_RUNSTATE_ADJUST;
@@ -682,7 +714,7 @@ int main(int argc, char *argv[])
 				vcpu_ioctl(vcpu, KVM_XEN_VCPU_SET_ATTR, &rst);
 				break;
 
-			case 5:
+			case TEST_RUNSTATE_DATA:
 				if (verbose)
 					printf("Testing RUNSTATE_DATA\n");
 				rst.type = KVM_XEN_VCPU_ATTR_TYPE_RUNSTATE_DATA;
@@ -694,7 +726,7 @@ int main(int argc, char *argv[])
 				vcpu_ioctl(vcpu, KVM_XEN_VCPU_SET_ATTR, &rst);
 				break;
 
-			case 6:
+			case TEST_STEAL_TIME:
 				if (verbose)
 					printf("Testing steal time\n");
 				/* Yield until scheduler delay exceeds target */
@@ -704,7 +736,7 @@ int main(int argc, char *argv[])
 				} while (get_run_delay() < rundelay);
 				break;
 
-			case 7:
+			case TEST_EVTCHN_MASKED:
 				if (!do_eventfd_tests)
 					goto done;
 				if (verbose)
@@ -714,7 +746,7 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 8:
+			case TEST_EVTCHN_UNMASKED:
 				if (verbose)
 					printf("Testing unmasked event channel\n");
 				/* Unmask that, but deliver the other one */
@@ -725,7 +757,7 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 9:
+			case TEST_EVTCHN_SLOWPATH:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
 				shinfo->evtchn_pending[1] = 0;
@@ -738,7 +770,7 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 10:
+			case TEST_EVTCHN_SEND_IOCTL:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
 				if (!do_evtchn_tests)
@@ -758,7 +790,7 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 11:
+			case TEST_EVTCHN_HCALL:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
 				shinfo->evtchn_pending[1] = 0;
@@ -769,7 +801,7 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 12:
+			case TEST_EVTCHN_HCALL_EVENTFD:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
 				shinfo->evtchn_pending[0] = 0;
@@ -780,7 +812,7 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 13:
+			case TEST_TIMER_SETUP:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
 				shinfo->evtchn_pending[1] = 0;
@@ -789,7 +821,7 @@ int main(int argc, char *argv[])
 					printf("Testing guest oneshot timer\n");
 				break;
 
-			case 14:
+			case TEST_TIMER_WAIT:
 				memset(&tmr, 0, sizeof(tmr));
 				tmr.type = KVM_XEN_VCPU_ATTR_TYPE_TIMER;
 				vcpu_ioctl(vcpu, KVM_XEN_VCPU_GET_ATTR, &tmr);
@@ -803,7 +835,7 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 15:
+			case TEST_TIMER_RESTORE:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
 				shinfo->evtchn_pending[0] = 0;
@@ -817,7 +849,7 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 16:
+			case TEST_POLL_READY:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
 
@@ -827,14 +859,14 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 17:
+			case TEST_POLL_TIMEOUT:
 				if (verbose)
 					printf("Testing SCHEDOP_poll timeout\n");
 				shinfo->evtchn_pending[0] = 0;
 				alarm(1);
 				break;
 
-			case 18:
+			case TEST_POLL_MASKED:
 				if (verbose)
 					printf("Testing SCHEDOP_poll wake on masked event\n");
 
@@ -843,7 +875,7 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 19:
+			case TEST_POLL_WAKE:
 				shinfo->evtchn_pending[0] = shinfo->evtchn_mask[0] = 0;
 				if (verbose)
 					printf("Testing SCHEDOP_poll wake on unmasked event\n");
@@ -860,7 +892,7 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 20:
+			case TEST_TIMER_PAST:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
 				/* Read timer and check it is no longer pending */
@@ -877,7 +909,7 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
-			case 21:
+			case TEST_LOCKING_SEND_RACE:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
 				alarm(0);
@@ -899,7 +931,7 @@ int main(int argc, char *argv[])
 					__vm_ioctl(vm, KVM_XEN_HVM_EVTCHN_SEND, &uxe);
 				break;
 
-			case 22:
+			case TEST_LOCKING_POLL_RACE:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
 
@@ -914,7 +946,7 @@ int main(int argc, char *argv[])
 				vcpu_ioctl(vcpu, KVM_XEN_VCPU_SET_ATTR, &tmr);
 				break;
 
-			case 23:
+			case TEST_LOCKING_POLL_TIMEOUT:
 				/*
 				 * Optional and possibly repeated sync point.
 				 * Injecting the timer IRQ may fail if the
@@ -936,7 +968,7 @@ int main(int argc, char *argv[])
 							 SHINFO_RACE_TIMEOUT * 1000000000ULL;
 				vcpu_ioctl(vcpu, KVM_XEN_VCPU_SET_ATTR, &tmr);
 				break;
-			case 24:
+			case TEST_DONE:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
 
@@ -947,7 +979,7 @@ int main(int argc, char *argv[])
 				TEST_ASSERT(ret == 0, "pthread_join() failed: %s", strerror(ret));
 				goto done;
 
-			case 0x20:
+			case TEST_GUEST_SAW_IRQ:
 				TEST_ASSERT(evtchn_irq_expected, "Unexpected event channel IRQ");
 				evtchn_irq_expected = false;
 				break;
Signature · 1 line
2.35.3
#23 lore raw

Re: [PATCH 2/3] KVM: selftests: Use enum for test numbers in xen_shinfo_test

Quoted 8 lines · David Woodhouse
tools/testing/selftests/kvm/x86_64/xen_shinfo_test.c +0 -0
@@ -439,6 +469,7 @@ int main(int argc, char *argv[])
         bool verbose;
         int ret;


+       printf("TEST_DONE is %d\n", TEST_DONE);
        verbose = argc > 1 && (!strncmp(argv[1], "-v", 3) || !strncmp(argv[1], "--verbose", 10));

Dammit.

#24 lore raw

PATCH 3/3 KVM: selftests: Add EVTCHNOP_send slow path test to xen_shinfo_test

In reply to David Woodhouse

From: David Woodhouse <[email protected]>

When kvm_xen_evtchn_send() takes the slow path because the shinfo GPC needs to be revalidated, it used to violate the SRCU vs. kvm->lock locking rules and potentially cause a deadlock.

Now that lockdep is learning to catch such things, make sure that code path is exercised by the selftest.

---
 .../selftests/kvm/x86_64/xen_shinfo_test.c    | 31 +++++++++++++++++++
 1 file changed, 31 insertions(+)
tools/testing/selftests/kvm/x86_64/xen_shinfo_test.c +31 -0
index 644d614a9965..3adc2e11b094 100644
@@ -29,6 +29,9 @@
 #define DUMMY_REGION_GPA	(SHINFO_REGION_GPA + (3 * PAGE_SIZE))
 #define DUMMY_REGION_SLOT	11
 
+#define DUMMY_REGION_GPA_2	(SHINFO_REGION_GPA + (4 * PAGE_SIZE))
+#define DUMMY_REGION_SLOT_2	12
+
 #define SHINFO_ADDR	(SHINFO_REGION_GPA)
 #define VCPU_INFO_ADDR	(SHINFO_REGION_GPA + 0x40)
 #define PVTIME_ADDR	(SHINFO_REGION_GPA + PAGE_SIZE)
@@ -57,6 +60,7 @@ enum {
 	TEST_EVTCHN_SLOWPATH,
 	TEST_EVTCHN_SEND_IOCTL,
 	TEST_EVTCHN_HCALL,
+	TEST_EVTCHN_HCALL_SLOWPATH,
 	TEST_EVTCHN_HCALL_EVENTFD,
 	TEST_TIMER_SETUP,
 	TEST_TIMER_WAIT,
@@ -270,6 +274,20 @@ static void guest_code(void)
 
 	guest_wait_for_irq();
 
+	GUEST_SYNC(TEST_EVTCHN_HCALL_SLOWPATH);
+
+	/* Same again, but this time the host has messed with memslots
+	 * so it should take the slow path in kvm_xen_set_evtchn(). */
+	__asm__ __volatile__ ("vmcall" :
+			      "=a" (rax) :
+			      "a" (__HYPERVISOR_event_channel_op),
+			      "D" (EVTCHNOP_send),
+			      "S" (&s));
+
+	GUEST_ASSERT(rax == 0);
+
+	guest_wait_for_irq();
+
 	GUEST_SYNC(TEST_EVTCHN_HCALL_EVENTFD);
 
 	/* Deliver "outbound" event channel to an eventfd which
@@ -801,6 +819,19 @@ int main(int argc, char *argv[])
 				alarm(1);
 				break;
 
+			case TEST_EVTCHN_HCALL_SLOWPATH:
+				TEST_ASSERT(!evtchn_irq_expected,
+					    "Expected event channel IRQ but it didn't happen");
+				shinfo->evtchn_pending[0] = 0;
+
+				if (verbose)
+					printf("Testing guest EVTCHNOP_send direct to evtchn after memslot change\n");
+				vm_userspace_mem_region_add(vm, VM_MEM_SRC_ANONYMOUS,
+							    DUMMY_REGION_GPA_2, DUMMY_REGION_SLOT_2, 1, 0);
+				evtchn_irq_expected = true;
+				alarm(1);
+				break;
+
 			case TEST_EVTCHN_HCALL_EVENTFD:
 				TEST_ASSERT(!evtchn_irq_expected,
 					    "Expected event channel IRQ but it didn't happen");
Signature · 1 line
2.35.3
#25 lore raw

Re: [PATCH 3/3] KVM: selftests: Add EVTCHNOP_send slow path test to xen_shinfo_test

Quoted 9 lines · David Woodhouse
tools/testing/selftests/kvm/x86_64/xen_shinfo_test.c +1 -0
@@ -57,6 +60,7 @@ enum {
 	TEST_EVTCHN_SLOWPATH,
 	TEST_EVTCHN_SEND_IOCTL,
 	TEST_EVTCHN_HCALL,
+	TEST_EVTCHN_HCALL_SLOWPATH,
 	TEST_EVTCHN_HCALL_EVENTFD,
 	TEST_TIMER_SETUP,
 	TEST_TIMER_WAIT,

tools/testing/selftests/kvm/x86_64/xen_shinfo_test.c static void guest_code(void) · line 280

Quoted 7 lines
tools/testing/selftests/kvm/x86_64/xen_shinfo_test.c +4 -0
@@ -270,6 +274,20 @@ static void guest_code(void)
 
 	guest_wait_for_irq();
 
+	GUEST_SYNC(TEST_EVTCHN_HCALL_SLOWPATH);
+
+	/* Same again, but this time the host has messed with memslots
+	 * so it should take the slow path in kvm_xen_set_evtchn(). */
	/*
	 * https://lore.kernel.org/all/CA+55aFyQYJerovMsSoSKS7PessZBr4vNp-3QUUwhqk4A4_jcbg@mail.gmail.com
	 */

tools/testing/selftests/kvm/x86_64/xen_shinfo_test.c static void guest_code(void) · line 287

Quoted 7 lines
tools/testing/selftests/kvm/x86_64/xen_shinfo_test.c +7 -0
+	__asm__ __volatile__ ("vmcall" :
+			      "=a" (rax) :
+			      "a" (__HYPERVISOR_event_channel_op),
+			      "D" (EVTCHNOP_send),
+			      "S" (&s));
+
+	GUEST_ASSERT(rax == 0);

There's a lot of copy+paste in this file, and we really should do VMMCALL when running on AMD. That's easy to do with some changes that are in the queue for 6.3. I'll repost these selftest patches on top of a few patches to add helpers for doing hypercalls using the Xen ABI.

#26 lore raw

Re: [PATCH 0/3] KVM: Make use of SRCU deadlock detection support

In reply to David Woodhouse
Quoted 8 lines · David Woodhouse

David Woodhouse (3):
KVM: Show lockdep the kvm->mutex vs. kvm->srcu ordering rule
KVM: selftests: Use enum for test numbers in xen_shinfo_test
KVM: selftests: Add EVTCHNOP_send slow path test to xen_shinfo_test

 .../testing/selftests/kvm/x86_64/xen_shinfo_test.c | 165 ++++++++++++++-------
 virt/kvm/kvm_main.c                                |  10 ++
 2 files changed, 124 insertions(+), 51 deletions(-)

As mentioned in patch three, I'm going to repost the selftests changes on top of other cleanups, and will plan on applying them next week if all goes well.

Paolo, do you want to grab the KVM change directly?

author
#27 lore raw

[PATCH 4/3] locking/lockdep: Improve the deadlock scenario print for sync and read lock

In reply to Boqun Feng

Lock scenario print is always a weak spot of lockdep splats. Improvement can be made if we rework the dependency search and the error printing.

However without touching the graph search, we can improve a little for the circular deadlock case, since we have the to-be-added lock dependency, and know whether these two locks are read/write/sync.

In order to know whether a held_lock is sync or not, a bit was "stolen" from ->references, which reduce our limit for the same lock class nesting from 2^12 to 2^11, and it should still be good enough.

Besides, since we now have bit in held_lock for sync, we don't need the "hardirqoffs being 1" trick, and also we can avoid the __lock_release() if we jump out of __lock_acquire() before the held_lock stored.

With these changes, a deadlock case evolved with read lock and sync gets a better print-out from:

	[...]  Possible unsafe locking scenario:
	[...]
	[...]        CPU0                    CPU1
	[...]        ----                    ----
	[...]   lock(srcuA);
	[...]                                lock(srcuB);
	[...]                                lock(srcuA);
	[...]   lock(srcuB);

to

	[...]  Possible unsafe locking scenario:
	[...]
	[...]        CPU0                    CPU1
	[...]        ----                    ----
	[...]   rlock(srcuA);
	[...]                                lock(srcuB);
	[...]                                lock(srcuA);
	[...]   sync(srcuB);
---
 include/linux/lockdep.h  |  3 ++-
 kernel/locking/lockdep.c | 48 ++++++++++++++++++++++++++--------------
 2 files changed, 34 insertions(+), 17 deletions(-)
include/linux/lockdep.h +2 -1
index ba09df6a0872..febd7ecc225c 100644
@@ -134,7 +134,8 @@ struct held_lock {
 	unsigned int read:2;        /* see lock_acquire() comment */
 	unsigned int check:1;       /* see lock_acquire() comment */
 	unsigned int hardirqs_off:1;
-	unsigned int references:12;					/* 32 bits */
+	unsigned int sync:1;
+	unsigned int references:11;					/* 32 bits */
 	unsigned int pin_count;
 };
 
kernel/locking/lockdep.c +32 -16

120 lines not on this page · raw message

Signature · 1 line
2.38.1
reviewer
#28 lore raw

Re: [PATCH 4/3] locking/lockdep: Improve the deadlock scenario print for sync and read lock

Quoted 87 lines · Boqun Feng

Lock scenario print is always a weak spot of lockdep splats. Improvement can be made if we rework the dependency search and the error printing.

However without touching the graph search, we can improve a little for the circular deadlock case, since we have the to-be-added lock dependency, and know whether these two locks are read/write/sync.

In order to know whether a held_lock is sync or not, a bit was "stolen" from ->references, which reduce our limit for the same lock class nesting from 2^12 to 2^11, and it should still be good enough.

Besides, since we now have bit in held_lock for sync, we don't need the "hardirqoffs being 1" trick, and also we can avoid the __lock_release() if we jump out of __lock_acquire() before the held_lock stored.

With these changes, a deadlock case evolved with read lock and sync gets a better print-out from:

	[...]  Possible unsafe locking scenario:
	[...]
	[...]        CPU0                    CPU1
	[...]        ----                    ----
	[...]   lock(srcuA);
	[...]                                lock(srcuB);
	[...]                                lock(srcuA);
	[...]   lock(srcuB);

to

	[...]  Possible unsafe locking scenario:
	[...]
	[...]        CPU0                    CPU1
	[...]        ----                    ----
	[...]   rlock(srcuA);
	[...]                                lock(srcuB);
	[...]                                lock(srcuA);
	[...]   sync(srcuB);
---
  include/linux/lockdep.h  |  3 ++-
  kernel/locking/lockdep.c | 48 ++++++++++++++++++++++++++--------------
  2 files changed, 34 insertions(+), 17 deletions(-)
include/linux/lockdep.h +2 -1
index ba09df6a0872..febd7ecc225c 100644
@@ -134,7 +134,8 @@ struct held_lock {
  	unsigned int read:2;        /* see lock_acquire() comment */
  	unsigned int check:1;       /* see lock_acquire() comment */
  	unsigned int hardirqs_off:1;
-	unsigned int references:12;					/* 32 bits */
+	unsigned int sync:1;
+	unsigned int references:11;					/* 32 bits */
  	unsigned int pin_count;
  };
 
kernel/locking/lockdep.c +6 -1
index cffa026a765f..4031d87f6829 100644
@@ -1880,6 +1880,8 @@ print_circular_lock_scenario(struct held_lock *src,
  	struct lock_class *source = hlock_class(src);
  	struct lock_class *target = hlock_class(tgt);
  	struct lock_class *parent = prt->class;
+	int src_read = src->read;
+	int tgt_read = tgt->read;
 
  	/*
  	 * A direct locking problem where unsafe_class lock is taken
@@ -1907,7 +1909,10 @@ print_circular_lock_scenario(struct held_lock *src,
  	printk(" Possible unsafe locking scenario:\n\n");
  	printk("       CPU0                    CPU1\n");
  	printk("       ----                    ----\n");
-	printk("  lock(");
+	if (tgt_read != 0)
+		printk("  rlock(");
+	else
+		printk("  lock(");
  	__print_lock_name(target);
  	printk(KERN_CONT ");\n");
  	printk("                               lock(");
@@ -1916,7 +1921,12 @@ print_circular_lock_scenario(struct held_lock *src,
  	printk("                               lock(");
  	__print_lock_name(target);
  	printk(KERN_CONT ");\n");

kernel/locking/lockdep.c print_circular_lock_scenario(struct held_lock *src, · line 1932

Quoted 10 lines
kernel/locking/lockdep.c +6 -1
-	printk("  lock(");
+	if (src_read != 0)
+		printk("  rlock(");
+	else if (src->sync)
+		printk("  sync(");
+	else
+		printk("  lock(");
  	__print_lock_name(source);
  	printk(KERN_CONT ");\n");
  	printk("\n *** DEADLOCK ***\n\n");

src can be sync() but not the target. Is there a reason why that is the case?

Quoted 43 lines
kernel/locking/lockdep.c +11 -3
@@ -4530,7 +4540,13 @@ mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
  					return 0;
  		}
  	}
-	if (!hlock->hardirqs_off) {
+
+	/*
+	 * For lock_sync(), don't mark the ENABLED usage, since lock_sync()
+	 * creates no critical section and no extra dependency can be introduced
+	 * by interrupts
+	 */
+	if (!hlock->hardirqs_off && !hlock->sync) {
  		if (hlock->read) {
  			if (!mark_lock(curr, hlock,
  					LOCK_ENABLED_HARDIRQ_READ))
@@ -4909,7 +4925,7 @@ static int __lock_is_held(const struct lockdep_map *lock, int read);
  static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
  			  int trylock, int read, int check, int hardirqs_off,
  			  struct lockdep_map *nest_lock, unsigned long ip,
-			  int references, int pin_count)
+			  int references, int pin_count, int sync)
  {
  	struct task_struct *curr = current;
  	struct lock_class *class = NULL;
@@ -4960,7 +4976,8 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 
  	class_idx = class - lock_classes;
 
-	if (depth) { /* we're holding locks */
+	if (depth && !sync) {
+		/* we're holding locks and the new held lock is not a sync */
  		hlock = curr->held_locks + depth - 1;
  		if (hlock->class_idx == class_idx && nest_lock) {
  			if (!references)
@@ -4994,6 +5011,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
  	hlock->trylock = trylock;
  	hlock->read = read;
  	hlock->check = check;
+	hlock->sync = !!sync;
  	hlock->hardirqs_off = !!hardirqs_off;
  	hlock->references = references;
  #ifdef CONFIG_LOCK_STAT

kernel/locking/lockdep.c static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass, · line 5082

Quoted 10 lines
kernel/locking/lockdep.c +4 -0
@@ -5055,6 +5073,10 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
  	if (!validate_chain(curr, hlock, chain_head, chain_key))
  		return 0;
 
+	/* For lock_sync(), we are done here since no actual critical section */
+	if (hlock->sync)
+		return 1;
+
  	curr->curr_chain_key = chain_key;
  	curr->lockdep_depth++;
  	check_chain_key(curr);

Even with sync, there is still a corresponding lock_acquire() and lock_release(), you can't exit here without increasing lockdep_depth. That can cause underflow.

Cheers,
Longman

author
#29 lore raw

Re: [PATCH 4/3] locking/lockdep: Improve the deadlock scenario print for sync and read lock

Quoted 91 lines · Waiman Long
Quoted 90 lines · Boqun Feng

Lock scenario print is always a weak spot of lockdep splats. Improvement can be made if we rework the dependency search and the error printing.

However without touching the graph search, we can improve a little for the circular deadlock case, since we have the to-be-added lock dependency, and know whether these two locks are read/write/sync.

In order to know whether a held_lock is sync or not, a bit was "stolen" from ->references, which reduce our limit for the same lock class nesting from 2^12 to 2^11, and it should still be good enough.

Besides, since we now have bit in held_lock for sync, we don't need the "hardirqoffs being 1" trick, and also we can avoid the __lock_release() if we jump out of __lock_acquire() before the held_lock stored.

With these changes, a deadlock case evolved with read lock and sync gets a better print-out from:

	[...]  Possible unsafe locking scenario:
	[...]
	[...]        CPU0                    CPU1
	[...]        ----                    ----
	[...]   lock(srcuA);
	[...]                                lock(srcuB);
	[...]                                lock(srcuA);
	[...]   lock(srcuB);

to

	[...]  Possible unsafe locking scenario:
	[...]
	[...]        CPU0                    CPU1
	[...]        ----                    ----
	[...]   rlock(srcuA);
	[...]                                lock(srcuB);
	[...]                                lock(srcuA);
	[...]   sync(srcuB);
---
  include/linux/lockdep.h  |  3 ++-
  kernel/locking/lockdep.c | 48 ++++++++++++++++++++++++++--------------
  2 files changed, 34 insertions(+), 17 deletions(-)
include/linux/lockdep.h +2 -1
index ba09df6a0872..febd7ecc225c 100644
@@ -134,7 +134,8 @@ struct held_lock {
  	unsigned int read:2;        /* see lock_acquire() comment */
  	unsigned int check:1;       /* see lock_acquire() comment */
  	unsigned int hardirqs_off:1;
-	unsigned int references:12;					/* 32 bits */
+	unsigned int sync:1;
+	unsigned int references:11;					/* 32 bits */
  	unsigned int pin_count;
  };
kernel/locking/lockdep.c +10 -2
index cffa026a765f..4031d87f6829 100644
@@ -1880,6 +1880,8 @@ print_circular_lock_scenario(struct held_lock *src,
  	struct lock_class *source = hlock_class(src);
  	struct lock_class *target = hlock_class(tgt);
  	struct lock_class *parent = prt->class;
+	int src_read = src->read;
+	int tgt_read = tgt->read;
  	/*
  	 * A direct locking problem where unsafe_class lock is taken
@@ -1907,7 +1909,10 @@ print_circular_lock_scenario(struct held_lock *src,
  	printk(" Possible unsafe locking scenario:\n\n");
  	printk("       CPU0                    CPU1\n");
  	printk("       ----                    ----\n");
-	printk("  lock(");
+	if (tgt_read != 0)
+		printk("  rlock(");
+	else
+		printk("  lock(");
  	__print_lock_name(target);
  	printk(KERN_CONT ");\n");
  	printk("                               lock(");
@@ -1916,7 +1921,12 @@ print_circular_lock_scenario(struct held_lock *src,
  	printk("                               lock(");
  	__print_lock_name(target);
  	printk(KERN_CONT ");\n");
-	printk("  lock(");
+	if (src_read != 0)
+		printk("  rlock(");
+	else if (src->sync)
+		printk("  sync(");
Quoted 9 lines

kernel/locking/lockdep.c print_circular_lock_scenario(struct held_lock *src, · line 1932

Quoted 5 lines
kernel/locking/lockdep.c +2 -0
+	else
+		printk("  lock(");
  	__print_lock_name(source);
  	printk(KERN_CONT ");\n");
  	printk("\n *** DEADLOCK ***\n\n");

src can be sync() but not the target. Is there a reason why that is the case?

The functions annotated by sync() don't create real critical sections, so no lock dependency can be created from a sync(), for example:

	synchronize_srcu(A);
	mutex_lock(B);

no dependency from A to B. In the scenario case, if we see a dependency target -> source, the target cannot be a lock_sync(). I will add better documentation later.

Quoted 47 lines
Quoted 47 lines
kernel/locking/lockdep.c +14 -3
@@ -4530,7 +4540,13 @@ mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
  					return 0;
  		}
  	}
-	if (!hlock->hardirqs_off) {
+
+	/*
+	 * For lock_sync(), don't mark the ENABLED usage, since lock_sync()
+	 * creates no critical section and no extra dependency can be introduced
+	 * by interrupts
+	 */
+	if (!hlock->hardirqs_off && !hlock->sync) {
  		if (hlock->read) {
  			if (!mark_lock(curr, hlock,
  					LOCK_ENABLED_HARDIRQ_READ))
@@ -4909,7 +4925,7 @@ static int __lock_is_held(const struct lockdep_map *lock, int read);
  static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
  			  int trylock, int read, int check, int hardirqs_off,
  			  struct lockdep_map *nest_lock, unsigned long ip,
-			  int references, int pin_count)
+			  int references, int pin_count, int sync)
  {
  	struct task_struct *curr = current;
  	struct lock_class *class = NULL;
@@ -4960,7 +4976,8 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
  	class_idx = class - lock_classes;
-	if (depth) { /* we're holding locks */
+	if (depth && !sync) {
+		/* we're holding locks and the new held lock is not a sync */
  		hlock = curr->held_locks + depth - 1;
  		if (hlock->class_idx == class_idx && nest_lock) {
  			if (!references)
@@ -4994,6 +5011,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
  	hlock->trylock = trylock;
  	hlock->read = read;
  	hlock->check = check;
+	hlock->sync = !!sync;
  	hlock->hardirqs_off = !!hardirqs_off;
  	hlock->references = references;
  #ifdef CONFIG_LOCK_STAT
@@ -5055,6 +5073,10 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
  	if (!validate_chain(curr, hlock, chain_head, chain_key))
  		return 0;
+	/* For lock_sync(), we are done here since no actual critical section */
+	if (hlock->sync)
+		return 1;
Quoted 9 lines

kernel/locking/lockdep.c static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass, · line 5082

Quoted 4 lines
kernel/locking/lockdep.c +1 -0
+
  	curr->curr_chain_key = chain_key;
  	curr->lockdep_depth++;
  	check_chain_key(curr);

Even with sync, there is still a corresponding lock_acquire() and lock_release(), you can't exit here without increasing lockdep_depth. That can cause underflow.

I actually remove the __lock_release() in lock_sync() in this patch, so I think it's OK. But I must admit the whole submission is to give David something to see whether the output is an improvement, so I probably should separate the output changes and the lock_sync() internall into two patches (and the later can also be folded into the introduction patch).

Regards,
Boqun

Quoted 3 lines

Cheers,
Longman

reviewer
#30 lore raw

Re: [PATCH 4/3] locking/lockdep: Improve the deadlock scenario print for sync and read lock

Quoted 103 lines · Boqun Feng
Quoted 90 lines · Waiman Long
Quoted 89 lines · Boqun Feng

Lock scenario print is always a weak spot of lockdep splats. Improvement can be made if we rework the dependency search and the error printing.

However without touching the graph search, we can improve a little for the circular deadlock case, since we have the to-be-added lock dependency, and know whether these two locks are read/write/sync.

In order to know whether a held_lock is sync or not, a bit was "stolen" from ->references, which reduce our limit for the same lock class nesting from 2^12 to 2^11, and it should still be good enough.

Besides, since we now have bit in held_lock for sync, we don't need the "hardirqoffs being 1" trick, and also we can avoid the __lock_release() if we jump out of __lock_acquire() before the held_lock stored.

With these changes, a deadlock case evolved with read lock and sync gets a better print-out from:

	[...]  Possible unsafe locking scenario:
	[...]
	[...]        CPU0                    CPU1
	[...]        ----                    ----
	[...]   lock(srcuA);
	[...]                                lock(srcuB);
	[...]                                lock(srcuA);
	[...]   lock(srcuB);

to

	[...]  Possible unsafe locking scenario:
	[...]
	[...]        CPU0                    CPU1
	[...]        ----                    ----
	[...]   rlock(srcuA);
	[...]                                lock(srcuB);
	[...]                                lock(srcuA);
	[...]   sync(srcuB);
---
   include/linux/lockdep.h  |  3 ++-
   kernel/locking/lockdep.c | 48 ++++++++++++++++++++++++++--------------
   2 files changed, 34 insertions(+), 17 deletions(-)
include/linux/lockdep.h +2 -1
index ba09df6a0872..febd7ecc225c 100644
@@ -134,7 +134,8 @@ struct held_lock {
   	unsigned int read:2;        /* see lock_acquire() comment */
   	unsigned int check:1;       /* see lock_acquire() comment */
   	unsigned int hardirqs_off:1;
-	unsigned int references:12;					/* 32 bits */
+	unsigned int sync:1;
+	unsigned int references:11;					/* 32 bits */
   	unsigned int pin_count;
   };
kernel/locking/lockdep.c +9 -2
index cffa026a765f..4031d87f6829 100644
@@ -1880,6 +1880,8 @@ print_circular_lock_scenario(struct held_lock *src,
   	struct lock_class *source = hlock_class(src);
   	struct lock_class *target = hlock_class(tgt);
   	struct lock_class *parent = prt->class;
+	int src_read = src->read;
+	int tgt_read = tgt->read;
   	/*
   	 * A direct locking problem where unsafe_class lock is taken
@@ -1907,7 +1909,10 @@ print_circular_lock_scenario(struct held_lock *src,
   	printk(" Possible unsafe locking scenario:\n\n");
   	printk("       CPU0                    CPU1\n");
   	printk("       ----                    ----\n");
-	printk("  lock(");
+	if (tgt_read != 0)
+		printk("  rlock(");
+	else
+		printk("  lock(");
   	__print_lock_name(target);
   	printk(KERN_CONT ");\n");
   	printk("                               lock(");
@@ -1916,7 +1921,12 @@ print_circular_lock_scenario(struct held_lock *src,
   	printk("                               lock(");
   	__print_lock_name(target);
   	printk(KERN_CONT ");\n");
-	printk("  lock(");
+	if (src_read != 0)
+		printk("  rlock(");
+	else if (src->sync)
Quoted 9 lines

kernel/locking/lockdep.c print_circular_lock_scenario(struct held_lock *src, · line 1932

Quoted 6 lines
kernel/locking/lockdep.c +3 -0
+		printk("  sync(");
+	else
+		printk("  lock(");
   	__print_lock_name(source);
   	printk(KERN_CONT ");\n");
   	printk("\n *** DEADLOCK ***\n\n");

src can be sync() but not the target. Is there a reason why that is the case?

The functions annotated by sync() don't create real critical sections, so no lock dependency can be created from a sync(), for example:

Quoted 6 lines
	synchronize_srcu(A);
	mutex_lock(B);

no dependency from A to B. In the scenario case, if we see a dependency target -> source, the target cannot be a lock_sync(). I will add better documentation later.

Right, the dependency won't happen since you reduce lock_sync() to mostly do validate_chain() without actually storing it in the lock chain which I did miss in my initial review. Without that, a dependency may happen if an NMI happens between lock_acquire() and lock_release() in lock_sync().

Quoted 54 lines
Quoted 45 lines
Quoted 45 lines
kernel/locking/lockdep.c +13 -3
@@ -4530,7 +4540,13 @@ mark_usage(struct task_struct *curr, struct held_lock *hlock, int check)
   					return 0;
   		}
   	}
-	if (!hlock->hardirqs_off) {
+
+	/*
+	 * For lock_sync(), don't mark the ENABLED usage, since lock_sync()
+	 * creates no critical section and no extra dependency can be introduced
+	 * by interrupts
+	 */
+	if (!hlock->hardirqs_off && !hlock->sync) {
   		if (hlock->read) {
   			if (!mark_lock(curr, hlock,
   					LOCK_ENABLED_HARDIRQ_READ))
@@ -4909,7 +4925,7 @@ static int __lock_is_held(const struct lockdep_map *lock, int read);
   static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
   			  int trylock, int read, int check, int hardirqs_off,
   			  struct lockdep_map *nest_lock, unsigned long ip,
-			  int references, int pin_count)
+			  int references, int pin_count, int sync)
   {
   	struct task_struct *curr = current;
   	struct lock_class *class = NULL;
@@ -4960,7 +4976,8 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
   	class_idx = class - lock_classes;
-	if (depth) { /* we're holding locks */
+	if (depth && !sync) {
+		/* we're holding locks and the new held lock is not a sync */
   		hlock = curr->held_locks + depth - 1;
   		if (hlock->class_idx == class_idx && nest_lock) {
   			if (!references)
@@ -4994,6 +5011,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
   	hlock->trylock = trylock;
   	hlock->read = read;
   	hlock->check = check;
+	hlock->sync = !!sync;
   	hlock->hardirqs_off = !!hardirqs_off;
   	hlock->references = references;
   #ifdef CONFIG_LOCK_STAT
@@ -5055,6 +5073,10 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
   	if (!validate_chain(curr, hlock, chain_head, chain_key))
   		return 0;
+	/* For lock_sync(), we are done here since no actual critical section */
+	if (hlock->sync)
Quoted 9 lines

kernel/locking/lockdep.c static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass, · line 5082

Quoted 5 lines
kernel/locking/lockdep.c +2 -0
+		return 1;
+
   	curr->curr_chain_key = chain_key;
   	curr->lockdep_depth++;
   	check_chain_key(curr);

Even with sync, there is still a corresponding lock_acquire() and lock_release(), you can't exit here without increasing lockdep_depth. That can cause underflow.

Quoted 6 lines

I actually remove the __lock_release() in lock_sync() in this patch, so I think it's OK. But I must admit the whole submission is to give David something to see whether the output is an improvement, so I probably should separate the output changes and the lock_sync() internall into two patches (and the later can also be folded into the introduction patch).

I saw that now. You may not need to separate it into 2 patches since there is some dependency between the two. You do have to document the 2 different changes in your patch description.

Cheers,
Longman