Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1203958 > unrolled thread

[Question] lockdep: Is nested lock handled correctly?

Back to article view | Back to linux.kernel

Contents

  [Question] lockdep: Is nested lock handled correctly? Boqun Feng <boqun.feng@gmail.com> - 2015-08-10 12:00 +0200
    Re: [Question] lockdep: Is nested lock handled correctly? Peter Zijlstra <peterz@infradead.org> - 2015-08-10 13:50 +0200
      Re: [Question] lockdep: Is nested lock handled correctly? Boqun Feng <boqun.feng@gmail.com> - 2015-08-10 15:50 +0200
        Re: [Question] lockdep: Is nested lock handled correctly? Peter Zijlstra <peterz@infradead.org> - 2015-08-10 16:30 +0200
          Re: [Question] lockdep: Is nested lock handled correctly? Boqun Feng <boqun.feng@gmail.com> - 2015-08-11 03:40 +0200

#1203958 — [Question] lockdep: Is nested lock handled correctly?

Hi Peter and Ingo,

I'm now learning the code of lockdep and find that nested lock may not
be handled correctly because we fail to take held_lock merging into
consideration. I come up with an example and hope that could explain my
concern.

Please consider this lock/unlock sequence, I also put a patch ading this
sequence as a test into locking-selftest:

(lock_X1 and lock_X2 belong to the same lock class X, lock_Y1 belongs to
another lock class Y)

spin_lock(&lock_X1);
spin_lock(&lock_Y1);
spin_lock_nested_lock(&lock_X2, &lock_X1);
spin_unlock(&lock_Y1);
spin_unlock(&lock_X2);
spin_unlock(&lock_X1);


This is totally legal in current lockdep rules, right? But the states of
curr->held_locks stack after each lock/unlock show something
interesting:

0.	Initially:
	curr->held_locks is empty, curr->lockdep_depth: 0

1.	spin_lock(&lock_X1);
	curr->held_locks: H1(X), curr->lockdep_depth: 1

	H1(X) means a held_lock structure with ->class_idx pointing the
	class_idx of class X.

2.	spin_lock(&lock_Y1);
	curr->held_locks: H1(X)--H2(Y), curr->lockdep_depth: 2

3.	spin_lock_nested_lock(&lock_X2, &lock_X1);
	curr->held_locks: H1(X)--H2(Y)--H3(X),
	curr->lockdep_depth: 3

4.	spin_unlock(&lock_Y1);
	curr->held_locks: H1(X, references=2), curr->lockdep_depth:1
	
	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - 1) in
	__lock_release() will be triggered, because lockdep_depth
	changes from 3 to 1!

...

This could happen in current lockdep code, and the reason is that when
releasing H2 in __lock_release(), lockdep will call __lock_acquire() to
"reacquire" H3, and __lock_acquire() detects H3 and H1 belong to the
same class, so it will merge H3 into H1.

Therefore "After releasing a held_lock in the stack, the lockdep_depth
will decrease by 1" is not true!

Besides, this hlock-merge-after-release also makes the reference
counting of held_lock goes wrong. Please consider this sequence:

spin_lock(&lock_X1);
spin_lock(&lock_Y1);
spin_lock_nested_lock(&lock_X2, &lock_X1);
spin_lock_nested_lock(&lock_X3, &lock_X2);
spin_unlock(&lock_Y1);
spin_unlock(&lock_X3);
spin_unlock(&lock_X2);
spin_unlock(&lock_X1);

After spin_unlock(&lock_Y1), the curr->held_locks will become:

curr->held_locks: H1(X, references=2), curr->lockdep_depth: 1

But, in fact, we have -three- locks held now.


It seems to me that our current code don't take
hlock-merge-after-release into consideration and this is a problem. Am I
missing something here?

Looking forward to your insight ;-)


Add a patch for test case, which is based on current tip/locking/core.
I compiled the kernel with CONFIG_DEBUG_LOCKING_API_SELFTESTS and
CONFIG_PROVE_LOCKING, and the test fails because
DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - 1) is triggered.

Thanks and Best Regards,
Boqun

---
 lib/locking-selftest.c | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 872a15a..00042f9 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -1716,6 +1716,16 @@ static void ww_test_spin_context(void)
 	U(A);
 }
 
+static void bad_order_nested_spin_lock(void)
+{
+	raw_spin_lock(&lock_X1);
+	raw_spin_lock(&lock_Y1);
+	raw_spin_lock_nest_lock(&lock_X2, &lock_X1);
+	raw_spin_unlock(&lock_Y1); /* bad order here */
+	raw_spin_unlock(&lock_X2);
+	raw_spin_unlock(&lock_X1);
+}
+
 static void ww_tests(void)
 {
 	printk("  --------------------------------------------------------------------------\n");
@@ -1856,6 +1866,11 @@ void locking_selftest(void)
 	dotest(rsem_AA3, FAILURE, LOCKTYPE_RWSEM);
 	printk("\n");
 
+	print_testname("nested spin lock with bad order");
+	printk("|");
+	dotest(bad_order_nested_spin_lock, SUCCESS, LOCKTYPE_SPIN);
+	printk("\n");
+
 	printk("  --------------------------------------------------------------------------\n");
 
 	/*
-- 
2.5.0


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1204184

On Mon, Aug 10, 2015 at 05:52:47PM +0800, Boqun Feng wrote:
> Hi Peter and Ingo,
> 
> I'm now learning the code of lockdep and find that nested lock may not
> be handled correctly because we fail to take held_lock merging into
> consideration. I come up with an example and hope that could explain my
> concern.
> 
> Please consider this lock/unlock sequence, I also put a patch ading this
> sequence as a test into locking-selftest:
> 
> (lock_X1 and lock_X2 belong to the same lock class X, lock_Y1 belongs to
> another lock class Y)
> 
> spin_lock(&lock_X1);
> spin_lock(&lock_Y1);
> spin_lock_nested_lock(&lock_X2, &lock_X1);
> spin_unlock(&lock_Y1);
> spin_unlock(&lock_X2);
> spin_unlock(&lock_X1);
> 
> 
> This is totally legal in current lockdep rules, right? 

Yuck, I'd say no. That's quite horrible.

Why would you ever want to do that?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1204287

Hi Peter,

On Mon, Aug 10, 2015 at 01:42:28PM +0200, Peter Zijlstra wrote:
> On Mon, Aug 10, 2015 at 05:52:47PM +0800, Boqun Feng wrote:
> > Hi Peter and Ingo,
> > 
> > I'm now learning the code of lockdep and find that nested lock may not
> > be handled correctly because we fail to take held_lock merging into
> > consideration. I come up with an example and hope that could explain my
> > concern.
> > 
> > Please consider this lock/unlock sequence, I also put a patch ading this
> > sequence as a test into locking-selftest:
> > 
> > (lock_X1 and lock_X2 belong to the same lock class X, lock_Y1 belongs to
> > another lock class Y)
> > 
> > spin_lock(&lock_X1);
> > spin_lock(&lock_Y1);
> > spin_lock_nested_lock(&lock_X2, &lock_X1);

Sorry for the typo here.. should be spin_lock_nest_lock().

> > spin_unlock(&lock_Y1);
> > spin_unlock(&lock_X2);
> > spin_unlock(&lock_X1);
> > 
> > 
> > This is totally legal in current lockdep rules, right? 
> 
> Yuck, I'd say no. That's quite horrible.
> 

I admit that I didn't find this is horrible at first, but now I agree
with you, this is not a rational locking order. Thank you.

> Why would you ever want to do that?

Though I don't want to have a locking order like that either, we can't
stop others from using that order(maybe a good design review will) and
lockdep yells something -unrelated- in such an order.

I think we can either let lockdep complain if some one uses this
locking order or clean up current code a little bit to tolarent this.

If you really think we should do something about it, I can write the
patch and add test cases.

Thank you anyway.

Regards,
Boqun
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1204330

On Mon, Aug 10, 2015 at 09:49:24PM +0800, Boqun Feng wrote:
> Hi Peter,
> 
> On Mon, Aug 10, 2015 at 01:42:28PM +0200, Peter Zijlstra wrote:
> > On Mon, Aug 10, 2015 at 05:52:47PM +0800, Boqun Feng wrote:
> > > Hi Peter and Ingo,
> > > 
> > > I'm now learning the code of lockdep and find that nested lock may not
> > > be handled correctly because we fail to take held_lock merging into
> > > consideration. I come up with an example and hope that could explain my
> > > concern.
> > > 
> > > Please consider this lock/unlock sequence, I also put a patch ading this
> > > sequence as a test into locking-selftest:
> > > 
> > > (lock_X1 and lock_X2 belong to the same lock class X, lock_Y1 belongs to
> > > another lock class Y)
> > > 
> > > spin_lock(&lock_X1);
> > > spin_lock(&lock_Y1);
> > > spin_lock_nested_lock(&lock_X2, &lock_X1);
> 
> Sorry for the typo here.. should be spin_lock_nest_lock().
> 
> > > spin_unlock(&lock_Y1);
> > > spin_unlock(&lock_X2);
> > > spin_unlock(&lock_X1);
> > > 
> > > 
> > > This is totally legal in current lockdep rules, right? 
> > 
> > Yuck, I'd say no. That's quite horrible.
> > 
> 
> I admit that I didn't find this is horrible at first, but now I agree
> with you, this is not a rational locking order. Thank you.
> 
> > Why would you ever want to do that?
> 
> Though I don't want to have a locking order like that either, we can't
> stop others from using that order(maybe a good design review will) and
> lockdep yells something -unrelated- in such an order.
> 
> I think we can either let lockdep complain if some one uses this
> locking order or clean up current code a little bit to tolarent this.
> 
> If you really think we should do something about it, I can write the
> patch and add test cases.


Maybe something like the below in __lock_acquire():

	/* Daft bugger, can't guard a nesting order with the same lock class */
	if (DEBUG_LOCKS_WARN_ON(lock == nest_lock))
		return 0;

?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1204675

Hi Peter,

On Mon, Aug 10, 2015 at 04:24:17PM +0200, Peter Zijlstra wrote:
> On Mon, Aug 10, 2015 at 09:49:24PM +0800, Boqun Feng wrote:

<snip>

> > Though I don't want to have a locking order like that either, we can't
> > stop others from using that order(maybe a good design review will) and
> > lockdep yells something -unrelated- in such an order.
> > 
> > I think we can either let lockdep complain if some one uses this
> > locking order or clean up current code a little bit to tolarent this.
> > 
> > If you really think we should do something about it, I can write the
> > patch and add test cases.
> 
> 
> Maybe something like the below in __lock_acquire():
> 
> 	/* Daft bugger, can't guard a nesting order with the same lock class */
> 	if (DEBUG_LOCKS_WARN_ON(lock == nest_lock))
> 		return 0;
> 
> ?

I may not understand this well.. but I think this may not detect the
problem. The problem is:

A correct nesting order get disturbed by other locks acquired before the
nested lock acquired and release before the nested, which makes two
held_lock structures merged during __lock_acquire().


I think we can detect this in __lock_release():

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 8acfbf7..e75f622 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3427,6 +3427,19 @@ found_it:
        curr->lockdep_depth = i;
        curr->curr_chain_key = hlock->prev_chain_key;
 
+       /*
+        * We are going to "reacquire" the rest of stack, but we find out
+        * __lock_acquire() will merge the next hlock into prev_hlock,
+        * which means this is not a good time to release this lock and lock
+        * users might need to reconsider the locking design.
+        */
+       if (prev_hlock && (i+1) < depth) {
+               hlock = curr->held_locks + i + 1;
+               if (DEBUG_LOCKS_WARN_ON(hlock->nest_lock &&
+                               hlock->class_idx == prev_hlock->class_idx))
+                       return 0;
+       }
+
        for (i++; i < depth; i++) {
                hlock = curr->held_locks + i;
                if (!__lock_acquire(hlock->instance,


Regards,
Boqun
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web