Skip to contentSkip to conversation

lockdep: Improvements for rwlocks dependency inversion detection

PATCH In review Frederic Weisbecker 3 participants 9 messages Nov 18, 2009 – Nov 20, 2009 Locking primitives

lore
Share & tools
lore
#0 lore raw

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(-)
#1 lore raw

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

Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Ming Lei <[email protected]>
---
 include/linux/lockdep.h |    1 +
 kernel/lockdep.c        |   84 +++++++++++++++++++++++++++--------------------
 2 files changed, 49 insertions(+), 36 deletions(-)
include/linux/lockdep.h +1 -0
index 9ccf0e2..db24aa0 100644
@@ -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
maintainer
#2 lore raw

Re: [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 -> 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).

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/

http://lkml.org/lkml/2009/5/11/203

#3 lore raw

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/

http://lkml.org/lkml/2009/5/11/203

#4 lore raw

PATCH 2/2 lockdep: Don't only check recursive read locks once in a sequence

In reply to 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

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.

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
index a6f7440..13d1d54 100644
@@ -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
#5 lore raw

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 -> B

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

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
index a6f7440..13d1d54 100644
@@ -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();
#6 lore raw

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 -> B

Lockdep 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
                         |
                         Ar

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

maintainer
#7 lore raw

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

#8 lore raw

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.