lockdep: Is nested lock handled correctly?
Subsystems (2)
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(+)
lib/locking-selftest.c +15 -0
@@ -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" );/*
Signature · 1 line
2.5.0
Peter Zijlstra
maintainerQuoted 21 lines · Boqun Feng
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_lockmerging 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_X1andlock_X2belong to the same lock class X,lock_Y1belongs 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);
Quoted 1 line
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?
Hi Peter,
Quoted 11 lines · Peter Zijlstra
Quoted 10 lines · Boqun Feng
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_lockmerging 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:
Quoted 6 lines
Quoted 6 lines
(
lock_X1andlock_X2belong to the same lock class X,lock_Y1belongs 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().
Quoted 9 lines
Quoted 6 lines
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.
Quoted 1 line
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
Peter Zijlstra
maintainerQuoted 42 lines · Boqun Feng
Hi Peter,
Quoted 11 lines · Peter Zijlstra
Quoted 10 lines · Boqun Feng
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_lockmerging 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:
Quoted 6 lines
Quoted 6 lines
(
lock_X1andlock_X2belong to the same lock class X,lock_Y1belongs 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().Quoted 9 lines
Quoted 6 lines
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.
Quoted 1 line
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.
Quoted 5 lines
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;
?
Hi Peter,
Quoted 1 line · Peter Zijlstra
On Mon, Aug 10, 2015 at 09:49:24PM +0800, Boqun Feng wrote:
<snip>
Quoted 11 lines
Quoted 9 lines
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.
Quoted 7 lines
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():
kernel/locking/lockdep.c +13 -0
@@ -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