lockdep: Improvements for rwlocks dependency inversion detection
cover lockdep: Improvements for rwlocks dependency inversion detection
Hi,
This is two patches to improve rwlocks dependency inversion detection. If you ack these I can also add test suites for the particular treated usecases.
Thanks,
Frederic.
Frederic Weisbecker (2):
lockdep: Include recursive read-locks dependencies in the tree
lockdep: Don't only check recursive read locks once
include/linux/lockdep.h | 1 + kernel/lockdep.c | 88 ++++++++++++++++++++++++++-------------------- 2 files changed, 51 insertions(+), 38 deletions(-)
PATCH 1/2 lockdep: Include recursive read-locks dependencies in the tree
Currently, recursive read locks are checked in two ways:
- walk through the locks held by the current task and check possible deadlock.
- if the recursive read lock is not already present in the lock held by the current task, check its dependencies against the tree.
But this recursive read lock will never be added to the tree of dependencies. It means that the following sequence:
A = rwlock (Ar: taken as read recursive, Aw: taken as write) B = normal lock
Ar -> B
B -> Aw
won't ever be detected as a lock inversion.
This patch fixes it by inserting the recursive read locks into the tree of dependencies and enhancing the circular checks (check the class and the read attribute collision).
--- include/linux/lockdep.h | 1 + kernel/lockdep.c | 84 +++++++++++++++++++++++++++-------------------- 2 files changed, 49 insertions(+), 36 deletions(-)
include/linux/lockdep.h +1 -0
@@ -149,6 +149,7 @@ struct lock_list {struct lock_class *class;struct stack_trace trace;int distance; +int read;/* * The parent field is used to implement breadth-first search, and the
kernel/lockdep.c +48 -36
147 lines not on this page · raw message
Signature · 1 line
1.6.2.3
Peter Zijlstra
maintainerRe: [PATCH 1/2] lockdep: Include recursive read-locks dependencies in the tree
Quoted 14 lines · Frederic Weisbecker
Currently, recursive read locks are checked in two ways:
- walk through the locks held by the current task and check possible deadlock.
- if the recursive read lock is not already present in the lock held by the current task, check its dependencies against the tree.
But this recursive read lock will never be added to the tree of dependencies. It means that the following sequence:
A = rwlock (Ar: taken as read recursive, Aw: taken as write) B = normal lock
Quoted 7 lines
Ar -> B
B -> Awwon't ever be detected as a lock inversion.
This patch fixes it by inserting the recursive read locks into the tree of dependencies and enhancing the circular checks (check the class and the read attribute collision).
There were some very funny corner cases with IRQ state vs recursive locks, I don't seen any of that mentioned here.
Bot ego and I poked at it at various times, but neither of us managed to actually finish it due to getting distracted with other bits I guess.
http://programming.kicks-ass.net/kernel-patches/cpu-hotplug/
Re: [PATCH 1/2] lockdep: Include recursive read-locks dependencies in the tree
Quoted 18 lines · Peter Zijlstra
Quoted 17 lines · Frederic Weisbecker
Currently, recursive read locks are checked in two ways:
- walk through the locks held by the current task and check possible deadlock.
- if the recursive read lock is not already present in the lock held by the current task, check its dependencies against the tree.
But this recursive read lock will never be added to the tree of dependencies. It means that the following sequence:
A = rwlock (Ar: taken as read recursive, Aw: taken as write) B = normal lock
Ar -> B
B -> Aw
Quoted 7 lines
Quoted 4 lines
won't ever be detected as a lock inversion.
This patch fixes it by inserting the recursive read locks into the tree of dependencies and enhancing the circular checks (check the class and the read attribute collision).There were some very funny corner cases with IRQ state vs recursive locks, I don't seen any of that mentioned here.
Ah right. I forgot these cases... I probably need to do some other checks in check_usage().
I'll have a look at it.
Thanks.
Quoted 6 lines
Bot ego and I poked at it at various times, but neither of us managed to actually finish it due to getting distracted with other bits I guess.
http://programming.kicks-ass.net/kernel-patches/cpu-hotplug/
PATCH 2/2 lockdep: Don't only check recursive read locks once in a sequence
In reply to Frederic WeisbeckerSay we have the following locks:
A (rwlock, Aw: writelock, Ar: recursive read lock) B (normal lock)
and the following sequences:
Ar -> B -> Ar
Aw -> B
This won't be detected as a lock inversion because in the sequence of locks held by the current task, if we have a same class acquired as read-recursive several times, only the first one will be checked in the tree (although all of them are checked for deadlocks in the current held sequence).
Fix it by always adding recursive read locks in the dependency tree.
--- kernel/lockdep.c | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-)
kernel/lockdep.c +2 -2
@@ -1949,9 +1949,9 @@ static int validate_chain(struct task_struct *curr, struct lockdep_map *lock, hlock->read =2 ;/* * Add dependency only if this lock is not the head -* of the chain, and if it's not a secondary read-lock: +* of the chain. */ -if (!chain_head && ret !=2 ) +if (!chain_head)if (!check_prevs_add (curr, hlock))return 0 ;graph_unlock ();
Signature · 1 line
1.6.2.3
Re: [PATCH 2/2] lockdep: Don't only check recursive read locks once in a sequence
Quoted 9 lines · Frederic Weisbecker
Say we have the following locks:
A (rwlock, Aw: writelock, Ar: recursive read lock) B (normal lock)and the following sequences:
Ar -> B -> Ar
Aw -> BThis won't be detected as a lock inversion
"""
read-preference <==> read-recursive ability (rwlock)
otherwise ==> read-recursive disability (rwsem)
"""
If "B -> Ar" is always after "Ar", it's NOT a really lock inversion because rwlock is read-preference, we can ignore all "Ar" which are after "B".
If sometimes "B -> Ar" is not after "Ar",
then we have these sequences:
B -> Ar
Aw -> B
Lockdep can detects it now(without this patch applied).
Maybe I have misunderstood your patch.
Quoted 32 lines
because in the sequence
of locks held by the current task, if we have a same class acquired as read-recursive several times, only the first one will be checked in the tree (although all of them are checked for deadlocks in the current held sequence).Fix it by always adding recursive read locks in the dependency tree.
Signed-off-by Frederic Weisbecker <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Thomas Gleixner <[email protected]>Cc Ming Lei <[email protected]>--- kernel/lockdep.c | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-)kernel/lockdep.c +2
-2@@ -1949,9 +1949,9 @@ static int validate_chain(struct task_struct *curr, struct lockdep_map *lock, hlock->read =2 ;/* * Add dependency only if this lock is not the head -* of the chain, and if it's not a secondary read-lock: +* of the chain. */ -if (!chain_head && ret !=2 ) +if (!chain_head)if (!check_prevs_add (curr, hlock))return 0 ;graph_unlock ();
Re: [PATCH 2/2] lockdep: Don't only check recursive read locks once in a sequence
Quoted 9 lines · Lai Jiangshan
Quoted 8 lines · Frederic Weisbecker
Say we have the following locks:
A (rwlock, Aw: writelock, Ar: recursive read lock) B (normal lock)and the following sequences:
Ar -> B -> Ar
Aw -> B
Quoted 6 lines
Quoted 1 line
This won't be detected as a lock inversion
"""
read-preference <==> read-recursive ability (rwlock)
otherwise ==> read-recursive disability (rwsem)
"""
I don't understand the idea of "read-preference". And btw I don't understand why rwsem read locks are not considered as recursive in lockdep.
Quoted 3 lines
If "B -> Ar" is always after "Ar", it's NOT a really lock inversion because rwlock is read-preference, we can ignore all "Ar" which are after "B".
It's not a lock inversion in itself because it's legal to have:
Ar -> B -> Ar
Quoted 8 lines
If sometimes "B -> Ar" is not after "Ar",
then we have these sequences:
B -> Ar
Aw -> BLockdep can detects it now(without this patch applied).
Maybe I have misunderstood your patch.
Well.
In my example we have this sequence first:
Ar -> B -> Ar
And this second one:
Aw -> B
In the lockdep tree, the read lock won't even be registered, so we'll just have Aw -> B in the tree.
If we insert these in the tree, we'll have one branch that will look like that:
Aw
|
B
|
ArLike we do with any other kind of lock. We just plug the dependencies between them. We know that B depends on Aw, but Ar also depends on B. Although the merged sequence might never happen, there is still a risk and the above is not legal.
Peter Zijlstra
maintainerRe: [PATCH 2/2] lockdep: Don't only check recursive read locks once in a sequence
Quoted 3 lines · Frederic Weisbecker
And btw I
don't understand why rwsem read locks are not considered as recursive in lockdep.
Because they're not.
rwsems are FIFO fair, so a double read can deadlock when there's a pending writer inbetween.
Re: [PATCH 2/2] lockdep: Don't only check recursive read locks once in a sequence
Quoted 10 lines · Peter Zijlstra
Quoted 3 lines · Frederic Weisbecker
And btw I
don't understand why rwsem read locks are not considered as recursive in lockdep.Because they're not.
rwsems are FIFO fair, so a double read can deadlock when there's a pending writer inbetween.
Aah ok. That's the subtle thing I was missing :)
Thanks.