[PATCH] locking/lockdep: Fix expected depth value in __lock_release()

[PATCH] locking/lockdep: Fix expected depth value in __lock_release()

[j.glisse]

From: Jérôme Glisse <jglisse@redhat.com>

In __lock_release() we are removing one entry from the stack and
rebuilding the hash chain by re-adding entry above the entry we
just removed. If the entry removed was between 2 entry of same
class then this 2 entry might be coalesced into one single entry
which in turns means that the lockdep_depth value will not be
incremented and thus the expected lockdep_depth value after this
operation will be wrong triggering an unjustified WARN_ONCE() at
the end of __lock_release().

This patch adjust the expect depth value by decrementing it if
what was previously 2 entry inside the stack are coalesced into
only one entry.

Note that __lock_set_class() does not suffer from same issue as
it adds a new class and thus can not lead to coalescing of stack
entry.

Signed-off-by: Jérôme Glisse <jglisse@redhat.com>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Sasha Levin <sasha.levin@oracle.com>
---
 kernel/locking/lockdep.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 4e49cc4..cac5e21 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3428,6 +3428,8 @@ found_it:
 	curr->curr_chain_key = hlock->prev_chain_key;
 
 	for (i++; i < depth; i++) {
+		int tmp = curr->lockdep_depth;
+
 		hlock = curr->held_locks + i;
 		if (!__lock_acquire(hlock->instance,
 			hlock_class(hlock)->subclass, hlock->trylock,
@@ -3435,6 +3437,13 @@ found_it:
 				hlock->nest_lock, hlock->acquire_ip,
 				hlock->references, hlock->pin_count))
 			return 0;
+		/*
+		 * If nest_lock is true and the lock we just removed allow two
+		 * lock of same class to be consolidated in only one held_lock
+		 * then the lockdep_depth count will not increase as we expect
+		 * it to. So adjust the expected depth value accordingly.
+		 */
+		depth -= (curr->lockdep_depth == tmp);
 	}
 
 	/*
-- 
1.8.3.1

Re: [PATCH] locking/lockdep: Fix expected depth value in __lock_release()

[Peter Zijlstra]

On Mon, Oct 19, 2015 at 03:30:28PM -0400, j.glisse@gmail.com wrote:
> From: Jérôme Glisse <jglisse@redhat.com>
> 
> In __lock_release() we are removing one entry from the stack and
> rebuilding the hash chain by re-adding entry above the entry we
> just removed. If the entry removed was between 2 entry of same
> class then this 2 entry might be coalesced into one single entry
> which in turns means that the lockdep_depth value will not be
> incremented and thus the expected lockdep_depth value after this
> operation will be wrong triggering an unjustified WARN_ONCE() at
> the end of __lock_release().

This is the nest_lock stuff, right? Where it checks:

  if (hlock->class_idx == class_idx && nest_lock) {
	...
	return 1;
  }

What code did you find that triggered this? That is, what code is taking
nested locks with other locks in the middle? (Not wrong per-se, just
curious how that would come about).

> This patch adjust the expect depth value by decrementing it if
> what was previously 2 entry inside the stack are coalesced into
> only one entry.

Would it not make more sense to scan the entire hlock stack on
__lock_acquire() and avoid getting collapsible entries in the first
place?

Something like so...

---
 kernel/locking/lockdep.c | 22 ++++++++++++++--------
 1 file changed, 14 insertions(+), 8 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 4e49cc4c9952..6fcd98b86e7b 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3125,15 +3125,21 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 
 	class_idx = class - lock_classes + 1;
 
-	if (depth) {
-		hlock = curr->held_locks + depth - 1;
-		if (hlock->class_idx == class_idx && nest_lock) {
-			if (hlock->references)
-				hlock->references++;
-			else
-				hlock->references = 2;
+	if (depth && nest_lock) {
+		int i;
 
-			return 1;
+		for (i = depth; i; --i) {
+			hlock = curr->held_locks + i - 1;
+			if (hlock->class_idx == class_idx &&
+			    hlock->nest_lock == nest_lock) {
+
+				if (hlock->references)
+					hlock->references++;
+				else
+					hlock->references = 2;
+
+				return 1;
+			}
 		}
 	}
 

Re: [PATCH] locking/lockdep: Fix expected depth value in __lock_release()

[Jerome Glisse]

On Tue, Oct 20, 2015 at 02:18:53PM +0200, Peter Zijlstra wrote:
> On Mon, Oct 19, 2015 at 03:30:28PM -0400, j.glisse@gmail.com wrote:
> > From: Jérôme Glisse <jglisse@redhat.com>
> > 
> > In __lock_release() we are removing one entry from the stack and
> > rebuilding the hash chain by re-adding entry above the entry we
> > just removed. If the entry removed was between 2 entry of same
> > class then this 2 entry might be coalesced into one single entry
> > which in turns means that the lockdep_depth value will not be
> > incremented and thus the expected lockdep_depth value after this
> > operation will be wrong triggering an unjustified WARN_ONCE() at
> > the end of __lock_release().
> 
> This is the nest_lock stuff, right? Where it checks:
> 
>   if (hlock->class_idx == class_idx && nest_lock) {
> 	...
> 	return 1;
>   }

Yes this code.

> 
> What code did you find that triggered this? That is, what code is taking
> nested locks with other locks in the middle? (Not wrong per-se, just
> curious how that would come about).

Well i am not able to reproduce myself but it happens as part of
mm_drop_all_locks() as to which lock does trigger i am unsure as
all the i_mmap_rwsem are taken one after the other and same for
anon_vma rwsem so they should already coalesce properly. My guess
is that code calling all lock also have a mutex and once all vma
lock are drop the mutex coalesce with mm_all_locks_mutex.

> 
> > This patch adjust the expect depth value by decrementing it if
> > what was previously 2 entry inside the stack are coalesced into
> > only one entry.
> 
> Would it not make more sense to scan the entire hlock stack on
> __lock_acquire() and avoid getting collapsible entries in the first
> place?
> 
> Something like so...

It would work too, probably more compute intensive than my solution
but this is lockdep code so i guess it is fine. Also dunno if we loose
any valuable information by not keeping the stack ordered so one
can check order in whick lock are taken.

> 
> ---
>  kernel/locking/lockdep.c | 22 ++++++++++++++--------
>  1 file changed, 14 insertions(+), 8 deletions(-)
> 
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 4e49cc4c9952..6fcd98b86e7b 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -3125,15 +3125,21 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
>  
>  	class_idx = class - lock_classes + 1;
>  
> -	if (depth) {
> -		hlock = curr->held_locks + depth - 1;
> -		if (hlock->class_idx == class_idx && nest_lock) {
> -			if (hlock->references)
> -				hlock->references++;
> -			else
> -				hlock->references = 2;
> +	if (depth && nest_lock) {
> +		int i;
>  
> -			return 1;
> +		for (i = depth; i; --i) {
> +			hlock = curr->held_locks + i - 1;
> +			if (hlock->class_idx == class_idx &&
> +			    hlock->nest_lock == nest_lock) {
> +
> +				if (hlock->references)
> +					hlock->references++;
> +				else
> +					hlock->references = 2;
> +
> +				return 1;
> +			}
>  		}
>  	}
>  

Re: [PATCH] locking/lockdep: Fix expected depth value in __lock_release()

[Peter Zijlstra]

On Tue, Oct 20, 2015 at 08:42:19AM -0400, Jerome Glisse wrote:
> On Tue, Oct 20, 2015 at 02:18:53PM +0200, Peter Zijlstra wrote:

> > What code did you find that triggered this? That is, what code is taking
> > nested locks with other locks in the middle? (Not wrong per-se, just
> > curious how that would come about).
> 
> Well i am not able to reproduce myself but it happens as part of
> mm_drop_all_locks() as to which lock does trigger i am unsure as
> all the i_mmap_rwsem are taken one after the other and same for
> anon_vma rwsem so they should already coalesce properly. My guess
> is that code calling all lock also have a mutex and once all vma
> lock are drop the mutex coalesce with mm_all_locks_mutex.

Ah yes, mm_all_locks_mutex looks like a likely candidate.

Curious, this code is ancient, and I've never seen a report of this
triggering.

> > > This patch adjust the expect depth value by decrementing it if
> > > what was previously 2 entry inside the stack are coalesced into
> > > only one entry.
> > 
> > Would it not make more sense to scan the entire hlock stack on
> > __lock_acquire() and avoid getting collapsible entries in the first
> > place?
> > 
> > Something like so...
> 
> It would work too, probably more compute intensive than my solution
> but this is lockdep code so i guess it is fine. Also dunno if we loose
> any valuable information by not keeping the stack ordered so one
> can check order in whick lock are taken.

Right; its a little bit more expensive, but only for acquires with
nest_lock set, which should be rare.

As to the order; since they're all of the same class, its fine to
collapse them.

However the proposed alternative avoids 'strange' boundary cases like:

	mutex_lock(&top_lock);

	for (...) {
		mutex_lock_nest_lock(&obj->lock1, &top_lock);
		mutex_lock_nest_lock(&obj->lock2, &top_lock);
	}

Which would currently result in running our of lock stack space real
quick since it would never be able to collapse.

In any case, can you 'test' the proposed alternative in any way?

Re: [PATCH] locking/lockdep: Fix expected depth value in __lock_release()

[Jerome Glisse]

On Tue, Oct 20, 2015 at 03:07:29PM +0200, Peter Zijlstra wrote:
> On Tue, Oct 20, 2015 at 08:42:19AM -0400, Jerome Glisse wrote:
> > On Tue, Oct 20, 2015 at 02:18:53PM +0200, Peter Zijlstra wrote:
> 
> > > What code did you find that triggered this? That is, what code is taking
> > > nested locks with other locks in the middle? (Not wrong per-se, just
> > > curious how that would come about).
> > 
> > Well i am not able to reproduce myself but it happens as part of
> > mm_drop_all_locks() as to which lock does trigger i am unsure as
> > all the i_mmap_rwsem are taken one after the other and same for
> > anon_vma rwsem so they should already coalesce properly. My guess
> > is that code calling all lock also have a mutex and once all vma
> > lock are drop the mutex coalesce with mm_all_locks_mutex.
> 
> Ah yes, mm_all_locks_mutex looks like a likely candidate.
> 
> Curious, this code is ancient, and I've never seen a report of this
> triggering.
> 
> > > > This patch adjust the expect depth value by decrementing it if
> > > > what was previously 2 entry inside the stack are coalesced into
> > > > only one entry.
> > > 
> > > Would it not make more sense to scan the entire hlock stack on
> > > __lock_acquire() and avoid getting collapsible entries in the first
> > > place?
> > > 
> > > Something like so...
> > 
> > It would work too, probably more compute intensive than my solution
> > but this is lockdep code so i guess it is fine. Also dunno if we loose
> > any valuable information by not keeping the stack ordered so one
> > can check order in whick lock are taken.
> 
> Right; its a little bit more expensive, but only for acquires with
> nest_lock set, which should be rare.
> 
> As to the order; since they're all of the same class, its fine to
> collapse them.
> 
> However the proposed alternative avoids 'strange' boundary cases like:
> 
> 	mutex_lock(&top_lock);
> 
> 	for (...) {
> 		mutex_lock_nest_lock(&obj->lock1, &top_lock);
> 		mutex_lock_nest_lock(&obj->lock2, &top_lock);
> 	}
> 
> Which would currently result in running our of lock stack space real
> quick since it would never be able to collapse.
> 
> In any case, can you 'test' the proposed alternative in any way?

I will ask for it to be tested probably gonna take couple days before
i hear back. I will report as soon as i have confirmation.

Cheers,
Jérôme