Skip to contentSkip to conversation

lockdep: add support for queued rwlock

PATCH In review Waiman Long 3 participants 6 messages Aug 6, 2014 – Aug 13, 2014

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

v7 cover lockdep: add support for queued rwlock

v6->v7:
- Add recursive read-lock with interrupt test in locking-selftest.c.

v5->v6:
- Unconditionally disallow the use of recursive read-lock in process context.
- Promote read state 3 to 2 when in interrupt context instead of doing additional check in check_deadlock().
- Fix some comments in locking-selftest.c.

v4->v5:
- Add patch 2 to update the locking selftest code to handle recursive read_lock correctly. Patch 1 has no change.

v3->v4:
- Document the new read state and move the conditional compilation code to lockdep.h.

v2->v3:
- Add a new read mode (3) for rwlock (used in lock_acquire_shared_cond_recursive()) to avoid conflict with other use cases of lock_acquire_shared_recursive().

v1->v2:
- Use less conditional & make it easier to read

With the merging of qrwlock into 3.16, it was found that the btrfs filesystem hanged readily. A fix was devised and merged into rc2 and the use of recursive read_lock call was part of the problem.

This patch series addes code to the lockdep subsystem to catch this kind of recursive read_lock calls in kernel code. It also updates the locking selftest to handle recursive read_lock correctly so that it won't complain about test failures.

Waiman Long (2):
locking/lockdep: Restrict the use of recursive read_lock() with
qrwlock
locking/selftest: Support queued rwlock

 include/linux/lockdep.h  |   10 +++++++-
 kernel/locking/lockdep.c |    6 +++++
 lib/locking-selftest.c   |   56 ++++++++++++++++++++++++++++++++++++++++-----
 3 files changed, 64 insertions(+), 8 deletions(-)
#1 lore raw

PATCH v7 1/2 locking/lockdep: Restrict the use of recursive read_lock() with qrwlock

Unlike the original unfair rwlock implementation, queued rwlock will grant lock according to the chronological sequence of the lock requests except when the lock requester is in the interrupt context. Consequently, recursive read_lock calls will now hang the process if there is a write_lock call somewhere in between the read_lock calls.

This patch updates the lockdep implementation to look for recursive read_lock calls. A new read state (3) is used to mark those read_lock call that cannot be recursively called except in the interrupt context. The new read state does exhaust the 2 bits available in held_lock:read bit field. The addition of any new read state in the future may require a redesign of how all those bits are squeezed together in the held_lock structure.

---
 include/linux/lockdep.h  |   10 +++++++++-
 kernel/locking/lockdep.c |    6 ++++++
 2 files changed, 15 insertions(+), 1 deletions(-)
include/linux/lockdep.h +9 -1
index 008388f..dadd6ba 100644
@@ -478,16 +478,24 @@ static inline void print_irqtrace_events(struct task_struct *curr)
  * on the per lock-class debug mode:
  */
 
+/*
+ * Read states in the 2-bit held_lock:read field:
+ *  0: Exclusive lock
+ *  1: Shareable lock, cannot be recursively called
+ *  2: Shareable lock, can be recursively called
+ *  3: Shareable lock, cannot be recursively called except in interrupt context
+ */
 #define lock_acquire_exclusive(l, s, t, n, i)		lock_acquire(l, s, t, 0, 1, n, i)
 #define lock_acquire_shared(l, s, t, n, i)		lock_acquire(l, s, t, 1, 1, n, i)
 #define lock_acquire_shared_recursive(l, s, t, n, i)	lock_acquire(l, s, t, 2, 1, n, i)
+#define lock_acquire_shared_irecursive(l, s, t, n, i)	lock_acquire(l, s, t, 3, 1, n, i)
 
 #define spin_acquire(l, s, t, i)		lock_acquire_exclusive(l, s, t, NULL, i)
 #define spin_acquire_nest(l, s, t, n, i)	lock_acquire_exclusive(l, s, t, n, i)
 #define spin_release(l, n, i)			lock_release(l, n, i)
 
 #define rwlock_acquire(l, s, t, i)		lock_acquire_exclusive(l, s, t, NULL, i)
-#define rwlock_acquire_read(l, s, t, i)		lock_acquire_shared_recursive(l, s, t, NULL, i)
+#define rwlock_acquire_read(l, s, t, i)		lock_acquire_shared_irecursive(l, s, t, NULL, i)
 #define rwlock_release(l, n, i)			lock_release(l, n, i)
 
 #define seqcount_acquire(l, s, t, i)		lock_acquire_exclusive(l, s, t, NULL, i)
kernel/locking/lockdep.c +6 -0
index d24e433..097f8ad 100644
@@ -3595,6 +3595,12 @@ void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	raw_local_irq_save(flags);
 	check_flags(flags);
 
+	/*
+	 * An interrupt recursive read in interrupt context can be considered
+	 * to be the same as a recursive read from checking perspective.
+	 */
+	if ((read == 3) && in_interrupt())
+		read = 2;
 	current->lockdep_recursion = 1;
 	trace_lock_acquire(lock, subclass, trylock, read, check, nest_lock, ip);
 	__lock_acquire(lock, subclass, trylock, read, check,
Signature · 1 line
1.7.1
#2 lore raw

[tip:locking/core] locking/lockdep: Restrict the use of recursive read_lock() with qrwlock

locking/lockdep: Restrict the use of recursive read_lock() with qrwlock
Commit-ID:  f0bab73cb539fb803c4d419951e8d28aa4964f8f
Gitweb:     http://git.kernel.org/tip/f0bab73cb539fb803c4d419951e8d28aa4964f8f
Author:     Waiman Long <[email protected]>
AuthorDate: Wed, 6 Aug 2014 13:22:01 -0400
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 13 Aug 2014 10:33:34 +0200

locking/lockdep: Restrict the use of recursive read_lock() with qrwlock

Unlike the original unfair rwlock implementation, queued rwlock will grant lock according to the chronological sequence of the lock requests except when the lock requester is in the interrupt context. Consequently, recursive read_lock calls will now hang the process if there is a write_lock call somewhere in between the read_lock calls.

This patch updates the lockdep implementation to look for recursive read_lock calls. A new read state (3) is used to mark those read_lock call that cannot be recursively called except in the interrupt context. The new read state does exhaust the 2 bits available in held_lock:read bit field. The addition of any new read state in the future may require a redesign of how all those bits are squeezed together in the held_lock structure.

---
 include/linux/lockdep.h  | 10 +++++++++-
 kernel/locking/lockdep.c |  6 ++++++
 2 files changed, 15 insertions(+), 1 deletion(-)
include/linux/lockdep.h +9 -1
index f388481..b5a84b62 100644
@@ -478,16 +478,24 @@ static inline void print_irqtrace_events(struct task_struct *curr)
  * on the per lock-class debug mode:
  */
 
+/*
+ * Read states in the 2-bit held_lock:read field:
+ *  0: Exclusive lock
+ *  1: Shareable lock, cannot be recursively called
+ *  2: Shareable lock, can be recursively called
+ *  3: Shareable lock, cannot be recursively called except in interrupt context
+ */
 #define lock_acquire_exclusive(l, s, t, n, i)		lock_acquire(l, s, t, 0, 1, n, i)
 #define lock_acquire_shared(l, s, t, n, i)		lock_acquire(l, s, t, 1, 1, n, i)
 #define lock_acquire_shared_recursive(l, s, t, n, i)	lock_acquire(l, s, t, 2, 1, n, i)
+#define lock_acquire_shared_irecursive(l, s, t, n, i)	lock_acquire(l, s, t, 3, 1, n, i)
 
 #define spin_acquire(l, s, t, i)		lock_acquire_exclusive(l, s, t, NULL, i)
 #define spin_acquire_nest(l, s, t, n, i)	lock_acquire_exclusive(l, s, t, n, i)
 #define spin_release(l, n, i)			lock_release(l, n, i)
 
 #define rwlock_acquire(l, s, t, i)		lock_acquire_exclusive(l, s, t, NULL, i)
-#define rwlock_acquire_read(l, s, t, i)		lock_acquire_shared_recursive(l, s, t, NULL, i)
+#define rwlock_acquire_read(l, s, t, i)		lock_acquire_shared_irecursive(l, s, t, NULL, i)
 #define rwlock_release(l, n, i)			lock_release(l, n, i)
 
 #define seqcount_acquire(l, s, t, i)		lock_acquire_exclusive(l, s, t, NULL, i)
kernel/locking/lockdep.c +6 -0
index 88d0d44..420ba68 100644
@@ -3597,6 +3597,12 @@ void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	raw_local_irq_save(flags);
 	check_flags(flags);
 
+	/*
+	 * An interrupt recursive read in interrupt context can be considered
+	 * to be the same as a recursive read from checking perspective.
+	 */
+	if ((read == 3) && in_interrupt())
+		read = 2;
 	current->lockdep_recursion = 1;
 	trace_lock_acquire(lock, subclass, trylock, read, check, nest_lock, ip);
 	__lock_acquire(lock, subclass, trylock, read, check,
#3 lore raw

PATCH v7 2/2 locking/selftest: Support queued rwlock

In reply to Waiman Long

The queued rwlock does not support the use of recursive read-lock in the process context. With changes in the lockdep code to check and disallow recursive read-lock, it is also necessary for the locking selftest to be updated to change the process context recursive read locking results from SUCCESS to FAILURE for rwlock.

---
 lib/locking-selftest.c |   56 ++++++++++++++++++++++++++++++++++++++++++------
 1 files changed, 49 insertions(+), 7 deletions(-)
lib/locking-selftest.c +49 -7
index 872a15a..62af709 100644
@@ -267,19 +267,46 @@ GENERATE_TESTCASE(AA_rsem)
 #undef E
 
 /*
- * Special-case for read-locking, they are
- * allowed to recurse on the same lock class:
+ * Special-case for read-locking, they are not allowed to
+ * recurse on the same lock class except under interrupt context:
  */
 static void rlock_AA1(void)
 {
 	RL(X1);
-	RL(X1); // this one should NOT fail
+	RL(X1); // this one should fail
 }
 
 static void rlock_AA1B(void)
 {
 	RL(X1);
-	RL(X2); // this one should NOT fail
+	RL(X2); // this one should fail
+}
+
+static void rlock_AHA1(void)
+{
+	RL(X1);
+	HARDIRQ_ENTER();
+	RL(X1);	// this one should NOT fail
+	HARDIRQ_EXIT();
+}
+
+static void rlock_AHA1B(void)
+{
+	RL(X1);
+	HARDIRQ_ENTER();
+	RL(X2);	// this one should NOT fail
+	HARDIRQ_EXIT();
+}
+
+static void rlock_ASAHA1(void)
+{
+	RL(X1);
+	SOFTIRQ_ENTER();
+	RL(X1);	// this one should NOT fail
+	HARDIRQ_ENTER();
+	RL(X1);	// this one should NOT fail
+	HARDIRQ_EXIT();
+	SOFTIRQ_EXIT();
 }
 
 static void rsem_AA1(void)
@@ -1069,7 +1096,7 @@ static inline void print_testname(const char *testname)
 	print_testname(desc);					\
 	dotest(name##_spin, FAILURE, LOCKTYPE_SPIN);		\
 	dotest(name##_wlock, FAILURE, LOCKTYPE_RWLOCK);		\
-	dotest(name##_rlock, SUCCESS, LOCKTYPE_RWLOCK);		\
+	dotest(name##_rlock, FAILURE, LOCKTYPE_RWLOCK);		\
 	dotest(name##_mutex, FAILURE, LOCKTYPE_MUTEX);		\
 	dotest(name##_wsem, FAILURE, LOCKTYPE_RWSEM);		\
 	dotest(name##_rsem, FAILURE, LOCKTYPE_RWSEM);		\
@@ -1830,14 +1857,14 @@ void locking_selftest(void)
 	printk("  --------------------------------------------------------------------------\n");
 	print_testname("recursive read-lock");
 	printk("             |");
-	dotest(rlock_AA1, SUCCESS, LOCKTYPE_RWLOCK);
+	dotest(rlock_AA1, FAILURE, LOCKTYPE_RWLOCK);
 	printk("             |");
 	dotest(rsem_AA1, FAILURE, LOCKTYPE_RWSEM);
 	printk("\n");
 
 	print_testname("recursive read-lock #2");
 	printk("             |");
-	dotest(rlock_AA1B, SUCCESS, LOCKTYPE_RWLOCK);
+	dotest(rlock_AA1B, FAILURE, LOCKTYPE_RWLOCK);
 	printk("             |");
 	dotest(rsem_AA1B, FAILURE, LOCKTYPE_RWSEM);
 	printk("\n");
@@ -1856,6 +1883,21 @@ void locking_selftest(void)
 	dotest(rsem_AA3, FAILURE, LOCKTYPE_RWSEM);
 	printk("\n");
 
+	print_testname("recursive rlock with interrupt");
+	printk("             |");
+	dotest(rlock_AHA1, SUCCESS, LOCKTYPE_RWLOCK);
+	printk("\n");
+
+	print_testname("recursive rlock with interrupt #2");
+	printk("             |");
+	dotest(rlock_AHA1B, SUCCESS, LOCKTYPE_RWLOCK);
+	printk("\n");
+
+	print_testname("recursive rlock with interrupt #3");
+	printk("             |");
+	dotest(rlock_ASAHA1, SUCCESS, LOCKTYPE_RWLOCK);
+	printk("\n");
+
 	printk("  --------------------------------------------------------------------------\n");
 
 	/*
Signature · 1 line
1.7.1
maintainer
#4 lore raw

Re: [PATCH v7 2/2] locking/selftest: Support queued rwlock

Quoted 21 lines · Waiman Long

The queued rwlock does not support the use of recursive read-lock in the process context. With changes in the lockdep code to check and disallow recursive read-lock, it is also necessary for the locking selftest to be updated to change the process context recursive read locking results from SUCCESS to FAILURE for rwlock.

lib/locking-selftest.c +16 -0
+static void rlock_AHA1(void)
+{
+	RL(X1);
+	HARDIRQ_ENTER();
+	RL(X1);	// this one should NOT fail
+	HARDIRQ_EXIT();
+}
+
+static void rlock_AHA1B(void)
+{
+	RL(X1);
+	HARDIRQ_ENTER();
+	RL(X2);	// this one should NOT fail
+	HARDIRQ_EXIT();
+}
+

lib/locking-selftest.c GENERATE_TESTCASE(AA_rsem) · line 310

Quoted 10 lines
lib/locking-selftest.c +9 -0
+static void rlock_ASAHA1(void)
+{
+	RL(X1);
+	SOFTIRQ_ENTER();
+	RL(X1);	// this one should NOT fail
+	HARDIRQ_ENTER();
+	RL(X1);	// this one should NOT fail
+	HARDIRQ_EXIT();
+	SOFTIRQ_EXIT();
 }

Thanks!

#5 lore raw

[tip:locking/core] locking/selftest: Support queued rwlock

In reply to Waiman Long
locking/selftest: Support queued rwlock
Commit-ID:  ae17ea0ec7d8fa64fbb773a52b2df5ba4766bcb8
Gitweb:     http://git.kernel.org/tip/ae17ea0ec7d8fa64fbb773a52b2df5ba4766bcb8
Author:     Waiman Long <[email protected]>
AuthorDate: Wed, 6 Aug 2014 13:22:02 -0400
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 13 Aug 2014 10:33:35 +0200

locking/selftest: Support queued rwlock

The queued rwlock does not support the use of recursive read-lock in the process context. With changes in the lockdep code to check and disallow recursive read-lock, it is also necessary for the locking selftest to be updated to change the process context recursive read locking results from SUCCESS to FAILURE for rwlock.

---
 lib/locking-selftest.c | 56 +++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 49 insertions(+), 7 deletions(-)
lib/locking-selftest.c +49 -7
index 872a15a..62af709 100644
@@ -267,19 +267,46 @@ GENERATE_TESTCASE(AA_rsem)
 #undef E
 
 /*
- * Special-case for read-locking, they are
- * allowed to recurse on the same lock class:
+ * Special-case for read-locking, they are not allowed to
+ * recurse on the same lock class except under interrupt context:
  */
 static void rlock_AA1(void)
 {
 	RL(X1);
-	RL(X1); // this one should NOT fail
+	RL(X1); // this one should fail
 }
 
 static void rlock_AA1B(void)
 {
 	RL(X1);
-	RL(X2); // this one should NOT fail
+	RL(X2); // this one should fail
+}
+
+static void rlock_AHA1(void)
+{
+	RL(X1);
+	HARDIRQ_ENTER();
+	RL(X1);	// this one should NOT fail
+	HARDIRQ_EXIT();
+}
+
+static void rlock_AHA1B(void)
+{
+	RL(X1);
+	HARDIRQ_ENTER();
+	RL(X2);	// this one should NOT fail
+	HARDIRQ_EXIT();
+}
+
+static void rlock_ASAHA1(void)
+{
+	RL(X1);
+	SOFTIRQ_ENTER();
+	RL(X1);	// this one should NOT fail
+	HARDIRQ_ENTER();
+	RL(X1);	// this one should NOT fail
+	HARDIRQ_EXIT();
+	SOFTIRQ_EXIT();
 }
 
 static void rsem_AA1(void)
@@ -1069,7 +1096,7 @@ static inline void print_testname(const char *testname)
 	print_testname(desc);					\
 	dotest(name##_spin, FAILURE, LOCKTYPE_SPIN);		\
 	dotest(name##_wlock, FAILURE, LOCKTYPE_RWLOCK);		\
-	dotest(name##_rlock, SUCCESS, LOCKTYPE_RWLOCK);		\
+	dotest(name##_rlock, FAILURE, LOCKTYPE_RWLOCK);		\
 	dotest(name##_mutex, FAILURE, LOCKTYPE_MUTEX);		\
 	dotest(name##_wsem, FAILURE, LOCKTYPE_RWSEM);		\
 	dotest(name##_rsem, FAILURE, LOCKTYPE_RWSEM);		\
@@ -1830,14 +1857,14 @@ void locking_selftest(void)
 	printk("  --------------------------------------------------------------------------\n");
 	print_testname("recursive read-lock");
 	printk("             |");
-	dotest(rlock_AA1, SUCCESS, LOCKTYPE_RWLOCK);
+	dotest(rlock_AA1, FAILURE, LOCKTYPE_RWLOCK);
 	printk("             |");
 	dotest(rsem_AA1, FAILURE, LOCKTYPE_RWSEM);
 	printk("\n");
 
 	print_testname("recursive read-lock #2");
 	printk("             |");
-	dotest(rlock_AA1B, SUCCESS, LOCKTYPE_RWLOCK);
+	dotest(rlock_AA1B, FAILURE, LOCKTYPE_RWLOCK);
 	printk("             |");
 	dotest(rsem_AA1B, FAILURE, LOCKTYPE_RWSEM);
 	printk("\n");
@@ -1856,6 +1883,21 @@ void locking_selftest(void)
 	dotest(rsem_AA3, FAILURE, LOCKTYPE_RWSEM);
 	printk("\n");
 
+	print_testname("recursive rlock with interrupt");
+	printk("             |");
+	dotest(rlock_AHA1, SUCCESS, LOCKTYPE_RWLOCK);
+	printk("\n");
+
+	print_testname("recursive rlock with interrupt #2");
+	printk("             |");
+	dotest(rlock_AHA1B, SUCCESS, LOCKTYPE_RWLOCK);
+	printk("\n");
+
+	print_testname("recursive rlock with interrupt #3");
+	printk("             |");
+	dotest(rlock_ASAHA1, SUCCESS, LOCKTYPE_RWLOCK);
+	printk("\n");
+
 	printk("  --------------------------------------------------------------------------\n");
 
 	/*