[PATCH 0/2] lockdep: Improvements for rwlocks dependency inversion detection

[PATCH 0/2] lockdep: Improvements for rwlocks dependency inversion detection

[Frederic Weisbecker]

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

[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

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

Signed-off-by: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Ming Lei <tom.leiming@gmail.com>
---
 include/linux/lockdep.h |    1 +
 kernel/lockdep.c        |   84 +++++++++++++++++++++++++++--------------------
 2 files changed, 49 insertions(+), 36 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 9ccf0e2..db24aa0 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -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
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index f5dcd36..a6f7440 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -818,8 +818,8 @@ static struct lock_list *alloc_list_entry(void)
 /*
  * Add a new dependency to the head of the list:
  */
-static int add_lock_to_list(struct lock_class *class, struct lock_class *this,
-			    struct list_head *head, unsigned long ip, int distance)
+static int add_lock_to_list(struct held_lock *this, struct list_head *head,
+			    unsigned long ip, int distance)
 {
 	struct lock_list *entry;
 	/*
@@ -833,8 +833,9 @@ static int add_lock_to_list(struct lock_class *class, struct lock_class *this,
 	if (!save_trace(&entry->trace))
 		return 0;
 
-	entry->class = this;
+	entry->class = hlock_class(this);
 	entry->distance = distance;
+	entry->read = this->read;
 	/*
 	 * Since we never remove from the dependency list, the list can
 	 * be walked lockless by other CPUs, it's only allocation
@@ -1087,9 +1088,34 @@ print_circular_bug_header(struct lock_list *entry, unsigned int depth,
 	return 0;
 }
 
-static inline int class_equal(struct lock_list *entry, void *data)
+static inline int lock_match(struct lock_list *entry, void *data)
 {
-	return entry->class == data;
+	struct held_lock *hl = data;
+
+	/* First eliminate class mismatch */
+	if (entry->class != hlock_class(hl))
+		return 0;
+
+	/*
+	 * If one of those is a write lock, whatever sequence
+	 * we have would be a deadlock
+	 */
+	if (!entry->read || !hl->read)
+		return 1;
+
+	/*
+	 * If the dependency to test is either read -> read-recursive
+	 * or read-recursive -> read-recursive, this won't lead to a
+	 * deadlock
+	 */
+	if (entry->read == 2)
+		return 0;
+
+	/*
+	 * If the dependency to test is either read-recursive -> read
+	 * or read -> read, this would be a deadlock
+	 */
+	return 1;
 }
 
 static noinline int print_circular_bug(struct lock_list *this,
@@ -1201,14 +1227,14 @@ unsigned long lockdep_count_backward_deps(struct lock_class *class)
  * lead to <target>. Print an error and return 0 if it does.
  */
 static noinline int
-check_noncircular(struct lock_list *root, struct lock_class *target,
+check_noncircular(struct lock_list *root, struct held_lock *target,
 		struct lock_list **target_entry)
 {
 	int result;
 
 	debug_atomic_inc(&nr_cyclic_checks);
 
-	result = __bfs_forwards(root, target, class_equal, target_entry);
+	result = __bfs_forwards(root, target, lock_match, target_entry);
 
 	return result;
 }
@@ -1654,7 +1680,9 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 	 */
 	this.class = hlock_class(next);
 	this.parent = NULL;
-	ret = check_noncircular(&this, hlock_class(prev), &target_entry);
+	this.read = next->read;
+
+	ret = check_noncircular(&this, prev, &target_entry);
 	if (unlikely(!ret))
 		return print_circular_bug(&this, target_entry, next, prev);
 	else if (unlikely(ret < 0))
@@ -1664,16 +1692,6 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 		return 0;
 
 	/*
-	 * For recursive read-locks we do all the dependency checks,
-	 * but we dont store read-triggered dependencies (only
-	 * write-triggered dependencies). This ensures that only the
-	 * write-side dependencies matter, and that if for example a
-	 * write-lock never takes any other locks, then the reads are
-	 * equivalent to a NOP.
-	 */
-	if (next->read == 2 || prev->read == 2)
-		return 1;
-	/*
 	 * Is the <prev> -> <next> dependency already present?
 	 *
 	 * (this may occur even though this is a new chain: consider
@@ -1693,15 +1711,13 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
 	 * Ok, all validations passed, add the new lock
 	 * to the previous lock's dependency list:
 	 */
-	ret = add_lock_to_list(hlock_class(prev), hlock_class(next),
-			       &hlock_class(prev)->locks_after,
+	ret = add_lock_to_list(next, &hlock_class(prev)->locks_after,
 			       next->acquire_ip, distance);
 
 	if (!ret)
 		return 0;
 
-	ret = add_lock_to_list(hlock_class(next), hlock_class(prev),
-			       &hlock_class(next)->locks_before,
+	ret = add_lock_to_list(prev, &hlock_class(next)->locks_before,
 			       next->acquire_ip, distance);
 	if (!ret)
 		return 0;
@@ -1752,22 +1768,18 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)
 	for (;;) {
 		int distance = curr->lockdep_depth - depth + 1;
 		hlock = curr->held_locks + depth-1;
+
+		if (!check_prev_add(curr, hlock, next, distance))
+			return 0;
 		/*
-		 * Only non-recursive-read entries get new dependencies
-		 * added:
+		 * Stop after the first non-trylock entry,
+		 * as non-trylock entries have added their
+		 * own direct dependencies already, so this
+		 * lock is connected to them indirectly:
 		 */
-		if (hlock->read != 2) {
-			if (!check_prev_add(curr, hlock, next, distance))
-				return 0;
-			/*
-			 * Stop after the first non-trylock entry,
-			 * as non-trylock entries have added their
-			 * own direct dependencies already, so this
-			 * lock is connected to them indirectly:
-			 */
-			if (!hlock->trylock)
-				break;
-		}
+		if (!hlock->trylock)
+			break;
+
 		depth--;
 		/*
 		 * End of lock-stack?
-- 
1.6.2.3

Re: [PATCH 1/2] lockdep: Include recursive read-locks dependencies in the tree

[Peter Zijlstra]

On Wed, 2009-11-18 at 02:06 +0100, Frederic Weisbecker wrote:
> 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).

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

Re: [PATCH 1/2] lockdep: Include recursive read-locks dependencies in the tree

[Frederic Weisbecker]

On Wed, Nov 18, 2009 at 11:26:05AM +0100, Peter Zijlstra wrote:
> On Wed, 2009-11-18 at 02:06 +0100, Frederic Weisbecker wrote:
> > 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).
> 
> 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.

 
> 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

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

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

Signed-off-by: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Ming Lei <tom.leiming@gmail.com>
---
 kernel/lockdep.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index a6f7440..13d1d54 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -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();
-- 
1.6.2.3

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

[Lai Jiangshan]

Frederic Weisbecker wrote:
> 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.

> 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 <fweisbec@gmail.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Ming Lei <tom.leiming@gmail.com>
> ---
>  kernel/lockdep.c |    4 ++--
>  1 files changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/lockdep.c b/kernel/lockdep.c
> index a6f7440..13d1d54 100644
> --- a/kernel/lockdep.c
> +++ b/kernel/lockdep.c
> @@ -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

[Frederic Weisbecker]

On Wed, Nov 18, 2009 at 05:43:03PM +0800, Lai Jiangshan wrote:
> Frederic Weisbecker wrote:
> > 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)
> """



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.


 
> 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



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

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

[Peter Zijlstra]

On Thu, 2009-11-19 at 16:55 +0100, Frederic Weisbecker wrote:
> 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

[Frederic Weisbecker]

On Thu, Nov 19, 2009 at 06:13:48PM +0100, Peter Zijlstra wrote:
> On Thu, 2009-11-19 at 16:55 +0100, Frederic Weisbecker wrote:
> > 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.