[PATCH 0/2 v6] lockdep: add support for queued rwlock

[PATCH 0/2 v6] lockdep: add support for queued rwlock

[Waiman Long]

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   |   12 ++++++------
 3 files changed, 21 insertions(+), 7 deletions(-)

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

[Waiman Long]

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.

Signed-off-by: Waiman Long <Waiman.Long@hp.com>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
---
 include/linux/lockdep.h  |   10 +++++++++-
 kernel/locking/lockdep.c |    6 ++++++
 2 files changed, 15 insertions(+), 1 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 008388f..dadd6ba 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -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)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index d24e433..097f8ad 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -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,
-- 
1.7.1

[PATCH 2/2 v6] locking/selftest: Support queued rwlock

[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.

Signed-off-by: Waiman Long <Waiman.Long@hp.com>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
---
 lib/locking-selftest.c |   12 ++++++------
 1 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 872a15a..9a33688 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -267,19 +267,19 @@ GENERATE_TESTCASE(AA_rsem)
 #undef E
 
 /*
- * Special-case for read-locking, they are
+ * Special-case for read-locking, they are not
  * allowed to recurse on the same lock class:
  */
 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 rsem_AA1(void)
@@ -1069,7 +1069,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 +1830,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");
-- 
1.7.1

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

[Peter Zijlstra]

[-- Attachment #1: Type: text/plain, Size: 1557 bytes --]

On Tue, Jul 29, 2014 at 02:53:19PM -0400, Waiman Long wrote:
> 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.
> 
> Signed-off-by: Waiman Long <Waiman.Long@hp.com>
> Signed-off-by: Peter Zijlstra <peterz@infradead.org>
> ---
>  lib/locking-selftest.c |   12 ++++++------
>  1 files changed, 6 insertions(+), 6 deletions(-)
> 
> diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
> index 872a15a..9a33688 100644
> --- a/lib/locking-selftest.c
> +++ b/lib/locking-selftest.c
> @@ -267,19 +267,19 @@ GENERATE_TESTCASE(AA_rsem)
>  #undef E
>  
>  /*
> - * Special-case for read-locking, they are
> + * Special-case for read-locking, they are not
>   * allowed to recurse on the same lock class:
>   */
>  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
>  }

Maybe I wasn't clear; but I meant you should extend the lock tests to
cover the full qrwlock semantics.

That means we also need tests like:

	RL(X1);
	IRQ_ENTER();
	RL(X2);
	IRQ_EXIT();

To fully validate that in_interrupt exception to fairness etc..

[-- Attachment #2: Type: application/pgp-signature, Size: 836 bytes --]

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

[Shuah Khan]

On Tue, Aug 5, 2014 at 7:28 AM, Peter Zijlstra <peterz@infradead.org> wrote:

> Maybe I wasn't clear; but I meant you should extend the lock tests to
> cover the full qrwlock semantics.
>
> That means we also need tests like:
>
>         RL(X1);
>         IRQ_ENTER();
>         RL(X2);
>         IRQ_EXIT();
>
> To fully validate that in_interrupt exception to fairness etc..

A bit off topic for this patch, however relevant for tests in general.
Is there a reason why these locking selftests need to be under lib?
Can they be consolidated under tools/testing/selftests?

-- Shuah

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

[Peter Zijlstra]

[-- Attachment #1: Type: text/plain, Size: 739 bytes --]

On Tue, Aug 05, 2014 at 08:07:28AM -0600, Shuah Khan wrote:
> On Tue, Aug 5, 2014 at 7:28 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> 
> > Maybe I wasn't clear; but I meant you should extend the lock tests to
> > cover the full qrwlock semantics.
> >
> > That means we also need tests like:
> >
> >         RL(X1);
> >         IRQ_ENTER();
> >         RL(X2);
> >         IRQ_EXIT();
> >
> > To fully validate that in_interrupt exception to fairness etc..
> 
> A bit off topic for this patch, however relevant for tests in general.
> Is there a reason why these locking selftests need to be under lib?
> Can they be consolidated under tools/testing/selftests?

tools/ seems wrong as its very much not userspace.

[-- Attachment #2: Type: application/pgp-signature, Size: 836 bytes --]

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

[Maarten Lankhorst]

op 05-08-14 16:41, Peter Zijlstra schreef:
> On Tue, Aug 05, 2014 at 08:07:28AM -0600, Shuah Khan wrote:
>> On Tue, Aug 5, 2014 at 7:28 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>>
>>> Maybe I wasn't clear; but I meant you should extend the lock tests to
>>> cover the full qrwlock semantics.
>>>
>>> That means we also need tests like:
>>>
>>>         RL(X1);
>>>         IRQ_ENTER();
>>>         RL(X2);
>>>         IRQ_EXIT();
>>>
>>> To fully validate that in_interrupt exception to fairness etc..
>> A bit off topic for this patch, however relevant for tests in general.
>> Is there a reason why these locking selftests need to be under lib?
>> Can they be consolidated under tools/testing/selftests?
> tools/ seems wrong as its very much not userspace.
Could be moved to kernel/locking though now that all other locking moved there. :-)

~Maarten

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

[Peter Zijlstra]

[-- Attachment #1: Type: text/plain, Size: 577 bytes --]

On Tue, Aug 05, 2014 at 04:44:34PM +0200, Maarten Lankhorst wrote:
> op 05-08-14 16:41, Peter Zijlstra schreef:

> >> A bit off topic for this patch, however relevant for tests in general.
> >> Is there a reason why these locking selftests need to be under lib?
> >> Can they be consolidated under tools/testing/selftests?
> > tools/ seems wrong as its very much not userspace.
> Could be moved to kernel/locking though now that all other locking moved there. :-)

Yes, I suppose we could do that; IIRC the reason I left it where it is
is because there are more tests in lib/.

[-- Attachment #2: Type: application/pgp-signature, Size: 836 bytes --]

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

[Shuah Khan]

On Tue, Aug 5, 2014 at 8:54 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, Aug 05, 2014 at 04:44:34PM +0200, Maarten Lankhorst wrote:
>> op 05-08-14 16:41, Peter Zijlstra schreef:
>
>> >> A bit off topic for this patch, however relevant for tests in general.
>> >> Is there a reason why these locking selftests need to be under lib?
>> >> Can they be consolidated under tools/testing/selftests?
>> > tools/ seems wrong as its very much not userspace.
>> Could be moved to kernel/locking though now that all other locking moved there. :-)
>
> Yes, I suppose we could do that; IIRC the reason I left it where it is
> is because there are more tests in lib/.

Maybe if tools doesn't sounds right, we could move testing from under tools
and have it be testing

We have several selftests spread around in the kernel tree. It makes it easier
to pull them under a single make target devtest. I sent in a patch add devtest
target that runs tests that are under tools/testing/selftests a couple of
weeks ago, hopefully it will be included in 3.17. I am working towards pulling
more kernel selftests that exist under this devtest umbrella. That is
the motivation
behind starting this conversation. :)

-- Shuah

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

[Peter Zijlstra]

[-- Attachment #1: Type: text/plain, Size: 791 bytes --]

On Tue, Aug 05, 2014 at 09:05:53AM -0600, Shuah Khan wrote:
> Maybe if tools doesn't sounds right, we could move testing from under tools
> and have it be testing

No, tools/testing/ is all userspace stuff afaict.

> We have several selftests spread around in the kernel tree. It makes it easier
> to pull them under a single make target devtest. I sent in a patch add devtest
> target that runs tests that are under tools/testing/selftests a couple of
> weeks ago, hopefully it will be included in 3.17. I am working towards pulling
> more kernel selftests that exist under this devtest umbrella. That is
> the motivation

A link to the patch might've been useful.. but no that's pointless,
there is no userspace component to locking-selftest, so your build/run
target is bloody pointless.

[-- Attachment #2: Type: application/pgp-signature, Size: 836 bytes --]

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

[Shuah Khan]

On Tue, Aug 5, 2014 at 9:25 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, Aug 05, 2014 at 09:05:53AM -0600, Shuah Khan wrote:
>> Maybe if tools doesn't sounds right, we could move testing from under tools
>> and have it be testing
>
> No, tools/testing/ is all userspace stuff afaict.
>
>> We have several selftests spread around in the kernel tree. It makes it easier
>> to pull them under a single make target devtest. I sent in a patch add devtest
>> target that runs tests that are under tools/testing/selftests a couple of
>> weeks ago, hopefully it will be included in 3.17. I am working towards pulling
>> more kernel selftests that exist under this devtest umbrella. That is
>> the motivation
>
> A link to the patch might've been useful.. but no that's pointless,
> there is no userspace component to locking-selftest, so your build/run
> target is bloody pointless.

Makes sense. Thanks,
-- Shuah

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

[Waiman Long]

On 08/05/2014 09:28 AM, Peter Zijlstra wrote:
> On Tue, Jul 29, 2014 at 02:53:19PM -0400, Waiman Long wrote:
>> 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.
>>
> Maybe I wasn't clear; but I meant you should extend the lock tests to
> cover the full qrwlock semantics.
>
> That means we also need tests like:
>
> 	RL(X1);
> 	IRQ_ENTER();
> 	RL(X2);
> 	IRQ_EXIT();
>
> To fully validate that in_interrupt exception to fairness etc..

Sorry for misinterpretation. I have just sent out an updated patch with 
additional self tests to verify that recursive read-lock is allowed 
under interrupt context.

-Longman