LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH v2 1/2] lockdep: Fix OOO unlock when hlocks need merging
@ 2019-05-24 20:15 Imre Deak
  2019-05-24 20:15 ` [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references Imre Deak
                   ` (2 more replies)
  0 siblings, 3 replies; 11+ messages in thread
From: Imre Deak @ 2019-05-24 20:15 UTC (permalink / raw)
  To: LKML; +Cc: Ville Syrjälä, Peter Zijlstra, Ingo Molnar, Will Deacon

The sequence

	static DEFINE_WW_CLASS(test_ww_class);

	struct ww_acquire_ctx ww_ctx;
	struct ww_mutex ww_lock_a;
	struct ww_mutex ww_lock_b;
	struct mutex lock_c;
	struct mutex lock_d;

	ww_acquire_init(&ww_ctx, &test_ww_class);

	ww_mutex_init(&ww_lock_a, &test_ww_class);
	ww_mutex_init(&ww_lock_b, &test_ww_class);

	mutex_init(&lock_c);

	ww_mutex_lock(&ww_lock_a, &ww_ctx);

	mutex_lock(&lock_c);

	ww_mutex_lock(&ww_lock_b, &ww_ctx);

	mutex_unlock(&lock_c);		(*)

	ww_mutex_unlock(&ww_lock_b);
	ww_mutex_unlock(&ww_lock_a);

	ww_acquire_fini(&ww_ctx);

triggers the following WARN in __lock_release() when doing the unlock at *:

	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - 1);

The problem is that the WARN check doesn't take into account the merging
of ww_lock_a and ww_lock_b which results in decreasing curr->lockdep_depth
by 2 not only 1.

Note that the following sequence doesn't trigger the WARN, since there
won't be any hlock merging.

	ww_acquire_init(&ww_ctx, &test_ww_class);

	ww_mutex_init(&ww_lock_a, &test_ww_class);
	ww_mutex_init(&ww_lock_b, &test_ww_class);

	mutex_init(&lock_c);
	mutex_init(&lock_d);

	ww_mutex_lock(&ww_lock_a, &ww_ctx);

	mutex_lock(&lock_c);
	mutex_lock(&lock_d);

	ww_mutex_lock(&ww_lock_b, &ww_ctx);

	mutex_unlock(&lock_d);

	ww_mutex_unlock(&ww_lock_b);
	ww_mutex_unlock(&ww_lock_a);

	mutex_unlock(&lock_c);

	ww_acquire_fini(&ww_ctx);

In general both of the above two sequences are valid and shouldn't
trigger any lockdep warning.

Fix this by taking the decrement due to the hlock merging into account
during lock release and hlock class re-setting. Merging can't happen
during lock downgrading since there won't be a new possibility to merge
hlocks in that case, so add a WARN if merging still happens then.

v2:
- Clarify the commit log and use mutex_lock() instead of mutex_trylock()
  in the example sequences for simplicity.

Cc: Ville Syrjälä <ville.syrjala@linux.intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Will Deacon <will.deacon@arm.com>
Signed-off-by: Imre Deak <imre.deak@intel.com>
---
 kernel/locking/lockdep.c | 38 +++++++++++++++++++++++++++++---------
 1 file changed, 29 insertions(+), 9 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index c40fba54e324..967352d32af1 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3714,7 +3714,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 				hlock->references = 2;
 			}
 
-			return 1;
+			return 2;
 		}
 	}
 
@@ -3920,22 +3920,33 @@ static struct held_lock *find_held_lock(struct task_struct *curr,
 }
 
 static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
-			      int idx)
+				int idx, bool *first_merged)
 {
 	struct held_lock *hlock;
+	int first_idx = idx;
 
 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
 		return 0;
 
 	for (hlock = curr->held_locks + idx; idx < depth; idx++, hlock++) {
-		if (!__lock_acquire(hlock->instance,
+		switch (__lock_acquire(hlock->instance,
 				    hlock_class(hlock)->subclass,
 				    hlock->trylock,
 				    hlock->read, hlock->check,
 				    hlock->hardirqs_off,
 				    hlock->nest_lock, hlock->acquire_ip,
-				    hlock->references, hlock->pin_count))
+				    hlock->references, hlock->pin_count)) {
+		case 0:
 			return 1;
+		case 1:
+			break;
+		case 2:
+			*first_merged = idx == first_idx;
+			break;
+		default:
+			WARN_ON(1);
+			return 0;
+		}
 	}
 	return 0;
 }
@@ -3948,6 +3959,7 @@ __lock_set_class(struct lockdep_map *lock, const char *name,
 	struct task_struct *curr = current;
 	struct held_lock *hlock;
 	struct lock_class *class;
+	bool first_merged = false;
 	unsigned int depth;
 	int i;
 
@@ -3973,14 +3985,14 @@ __lock_set_class(struct lockdep_map *lock, const char *name,
 	curr->lockdep_depth = i;
 	curr->curr_chain_key = hlock->prev_chain_key;
 
-	if (reacquire_held_locks(curr, depth, i))
+	if (reacquire_held_locks(curr, depth, i, &first_merged))
 		return 0;
 
 	/*
 	 * I took it apart and put it back together again, except now I have
 	 * these 'spare' parts.. where shall I put them.
 	 */
-	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
+	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - first_merged))
 		return 0;
 	return 1;
 }
@@ -3989,6 +4001,7 @@ static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
 {
 	struct task_struct *curr = current;
 	struct held_lock *hlock;
+	bool first_merged = false;
 	unsigned int depth;
 	int i;
 
@@ -4014,7 +4027,7 @@ static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
 	hlock->read = 1;
 	hlock->acquire_ip = ip;
 
-	if (reacquire_held_locks(curr, depth, i))
+	if (reacquire_held_locks(curr, depth, i, &first_merged))
 		return 0;
 
 	/*
@@ -4023,6 +4036,11 @@ static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
 	 */
 	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
 		return 0;
+
+	/* Merging can't happen with unchanged classes.. */
+	if (DEBUG_LOCKS_WARN_ON(first_merged))
+		return 0;
+
 	return 1;
 }
 
@@ -4038,6 +4056,7 @@ __lock_release(struct lockdep_map *lock, int nested, unsigned long ip)
 {
 	struct task_struct *curr = current;
 	struct held_lock *hlock;
+	bool first_merged = false;
 	unsigned int depth;
 	int i;
 
@@ -4093,14 +4112,15 @@ __lock_release(struct lockdep_map *lock, int nested, unsigned long ip)
 	if (i == depth-1)
 		return 1;
 
-	if (reacquire_held_locks(curr, depth, i + 1))
+	if (reacquire_held_locks(curr, depth, i + 1, &first_merged))
 		return 0;
 
 	/*
 	 * We had N bottles of beer on the wall, we drank one, but now
 	 * there's not N-1 bottles of beer left on the wall...
+	 * Pouring two of the bottles together is acceptable.
 	 */
-	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth-1);
+	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - 1 - first_merged);
 
 	/*
 	 * Since reacquire_held_locks() would have called check_chain_key()
-- 
2.17.1


^ permalink raw reply	[flat|nested] 11+ messages in thread

* [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references
  2019-05-24 20:15 [PATCH v2 1/2] lockdep: Fix OOO unlock when hlocks need merging Imre Deak
@ 2019-05-24 20:15 ` Imre Deak
  2019-05-27 15:14   ` Peter Zijlstra
  2019-06-03 13:32   ` [tip:locking/core] locking/lockdep: " tip-bot for Imre Deak
  2019-05-27 15:02 ` [PATCH v2 1/2] lockdep: Fix OOO unlock when hlocks need merging Peter Zijlstra
  2019-06-03 13:31 ` [tip:locking/core] locking/lockdep: " tip-bot for Imre Deak
  2 siblings, 2 replies; 11+ messages in thread
From: Imre Deak @ 2019-05-24 20:15 UTC (permalink / raw)
  To: LKML; +Cc: Ville Syrjälä, Peter Zijlstra, Ingo Molnar, Will Deacon

The sequence

	static DEFINE_WW_CLASS(test_ww_class);

	struct ww_acquire_ctx ww_ctx;
	struct ww_mutex ww_lock_a;
	struct ww_mutex ww_lock_b;
	struct ww_mutex ww_lock_c;
	struct mutex lock_c;

	ww_acquire_init(&ww_ctx, &test_ww_class);

	ww_mutex_init(&ww_lock_a, &test_ww_class);
	ww_mutex_init(&ww_lock_b, &test_ww_class);
	ww_mutex_init(&ww_lock_c, &test_ww_class);

	mutex_init(&lock_c);

	ww_mutex_lock(&ww_lock_a, &ww_ctx);

	mutex_lock(&lock_c);

	ww_mutex_lock(&ww_lock_b, &ww_ctx);
	ww_mutex_lock(&ww_lock_c, &ww_ctx);

	mutex_unlock(&lock_c);	(*)

	ww_mutex_unlock(&ww_lock_c);
	ww_mutex_unlock(&ww_lock_b);
	ww_mutex_unlock(&ww_lock_a);

	ww_acquire_fini(&ww_ctx); (**)

will trigger the following error in __lock_release() when calling
mutex_release() at **:

	DEBUG_LOCKS_WARN_ON(depth <= 0)

The problem is that the hlock merging happening at * updates the
references for test_ww_class incorrectly to 3 whereas it should've
updated it to 4 (representing all the instances for ww_ctx and
ww_lock_[abc]).

Fix this by updating the references during merging correctly taking into
account that we can have non-zero references (both for the hlock that we
merge into another hlock or for the hlock we are merging into).

Cc: Ville Syrjälä <ville.syrjala@linux.intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Will Deacon <will.deacon@arm.com>
Signed-off-by: Imre Deak <imre.deak@intel.com>
---
 kernel/locking/lockdep.c | 23 +++++++++++++----------
 1 file changed, 13 insertions(+), 10 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 967352d32af1..9e2a4ab6c731 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3637,6 +3637,11 @@ print_lock_nested_lock_not_held(struct task_struct *curr,
 
 static int __lock_is_held(const struct lockdep_map *lock, int read);
 
+static int hlock_reference(int reference)
+{
+	return reference ? : 1;
+}
+
 /*
  * This gets called for every mutex_lock*()/spin_lock*() operation.
  * We maintain the dependency maps and validate the locking attempt:
@@ -3702,17 +3707,15 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	if (depth) {
 		hlock = curr->held_locks + depth - 1;
 		if (hlock->class_idx == class_idx && nest_lock) {
-			if (hlock->references) {
-				/*
-				 * Check: unsigned int references overflow.
-				 */
-				if (DEBUG_LOCKS_WARN_ON(hlock->references == UINT_MAX))
-					return 0;
+			/*
+			 * Check: unsigned int references overflow.
+			 */
+			if (DEBUG_LOCKS_WARN_ON(hlock_reference(hlock->references) >
+						UINT_MAX - hlock_reference(references)))
+				return 0;
 
-				hlock->references++;
-			} else {
-				hlock->references = 2;
-			}
+			hlock->references = hlock_reference(hlock->references) +
+					    hlock_reference(references);
 
 			return 2;
 		}
-- 
2.17.1


^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [PATCH v2 1/2] lockdep: Fix OOO unlock when hlocks need merging
  2019-05-24 20:15 [PATCH v2 1/2] lockdep: Fix OOO unlock when hlocks need merging Imre Deak
  2019-05-24 20:15 ` [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references Imre Deak
@ 2019-05-27 15:02 ` Peter Zijlstra
  2019-05-27 15:21   ` Imre Deak
  2019-06-03 13:31 ` [tip:locking/core] locking/lockdep: " tip-bot for Imre Deak
  2 siblings, 1 reply; 11+ messages in thread
From: Peter Zijlstra @ 2019-05-27 15:02 UTC (permalink / raw)
  To: Imre Deak; +Cc: LKML, Ville Syrjälä, Ingo Molnar, Will Deacon

On Fri, May 24, 2019 at 11:15:08PM +0300, Imre Deak wrote:
> 
> 	ww_mutex_lock(&ww_lock_a, &ww_ctx);
> 
> 	mutex_lock(&lock_c);
> 
> 	ww_mutex_lock(&ww_lock_b, &ww_ctx);
> 
> 	mutex_unlock(&lock_c);		(*)

> triggers the following WARN in __lock_release() when doing the unlock at *:
> 
> 	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - 1);
> 
> The problem is that the WARN check doesn't take into account the merging
> of ww_lock_a and ww_lock_b which results in decreasing curr->lockdep_depth
> by 2 not only 1.

Cute...

> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index c40fba54e324..967352d32af1 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -3714,7 +3714,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
>  				hlock->references = 2;
>  			}
>  
> -			return 1;
> +			return 2;
>  		}
>  	}
>  
> @@ -3920,22 +3920,33 @@ static struct held_lock *find_held_lock(struct task_struct *curr,
>  }
>  
>  static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
> -			      int idx)
> +				int idx, bool *first_merged)
>  {
>  	struct held_lock *hlock;
> +	int first_idx = idx;
>  
>  	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
>  		return 0;
>  
>  	for (hlock = curr->held_locks + idx; idx < depth; idx++, hlock++) {
> -		if (!__lock_acquire(hlock->instance,
> +		switch (__lock_acquire(hlock->instance,
>  				    hlock_class(hlock)->subclass,
>  				    hlock->trylock,
>  				    hlock->read, hlock->check,
>  				    hlock->hardirqs_off,
>  				    hlock->nest_lock, hlock->acquire_ip,
> -				    hlock->references, hlock->pin_count))
> +				    hlock->references, hlock->pin_count)) {
> +		case 0:
>  			return 1;
> +		case 1:
> +			break;
> +		case 2:
> +			*first_merged = idx == first_idx;
> +			break;
> +		default:
> +			WARN_ON(1);
> +			return 0;
> +		}
>  	}
>  	return 0;
>  }

Does it work for you if I change it like so?

--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3712,7 +3712,7 @@ static int __lock_acquire(struct lockdep
 				hlock->references = 2;
 			}
 
-			return 1;
+			return 2;
 		}
 	}
 
@@ -3918,22 +3918,33 @@ static struct held_lock *find_held_lock(
 }
 
 static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
-			      int idx)
+				int idx, unsigned int *merged)
 {
 	struct held_lock *hlock;
+	int first_idx = idx;
 
 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
 		return 0;
 
 	for (hlock = curr->held_locks + idx; idx < depth; idx++, hlock++) {
-		if (!__lock_acquire(hlock->instance,
+		switch (__lock_acquire(hlock->instance,
 				    hlock_class(hlock)->subclass,
 				    hlock->trylock,
 				    hlock->read, hlock->check,
 				    hlock->hardirqs_off,
 				    hlock->nest_lock, hlock->acquire_ip,
-				    hlock->references, hlock->pin_count))
+				    hlock->references, hlock->pin_count)) {
+		case 0:
 			return 1;
+		case 1:
+			break;
+		case 2:
+			*merged += (idx == first_idx);
+			break;
+		default:
+			WARN_ON(1);
+			return 0;
+		}
 	}
 	return 0;
 }
@@ -3944,9 +3955,9 @@ __lock_set_class(struct lockdep_map *loc
 		 unsigned long ip)
 {
 	struct task_struct *curr = current;
+	unsigned int depth, merged = 0
 	struct held_lock *hlock;
 	struct lock_class *class;
-	unsigned int depth;
 	int i;
 
 	if (unlikely(!debug_locks))
@@ -3971,14 +3982,14 @@ __lock_set_class(struct lockdep_map *loc
 	curr->lockdep_depth = i;
 	curr->curr_chain_key = hlock->prev_chain_key;
 
-	if (reacquire_held_locks(curr, depth, i))
+	if (reacquire_held_locks(curr, depth, i, &merged))
 		return 0;
 
 	/*
 	 * I took it apart and put it back together again, except now I have
 	 * these 'spare' parts.. where shall I put them.
 	 */
-	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
+	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged))
 		return 0;
 	return 1;
 }
@@ -3986,8 +3997,8 @@ __lock_set_class(struct lockdep_map *loc
 static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
 {
 	struct task_struct *curr = current;
+	unsigned int depth, merged = 0;
 	struct held_lock *hlock;
-	unsigned int depth;
 	int i;
 
 	if (unlikely(!debug_locks))
@@ -4012,7 +4023,7 @@ static int __lock_downgrade(struct lockd
 	hlock->read = 1;
 	hlock->acquire_ip = ip;
 
-	if (reacquire_held_locks(curr, depth, i))
+	if (reacquire_held_locks(curr, depth, i, &merged))
 		return 0;
 
 	/*
@@ -4021,6 +4032,11 @@ static int __lock_downgrade(struct lockd
 	 */
 	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
 		return 0;
+
+	/* Merging can't happen with unchanged classes.. */
+	if (DEBUG_LOCKS_WARN_ON(merged))
+		return 0;
+
 	return 1;
 }
 
@@ -4035,8 +4051,8 @@ static int
 __lock_release(struct lockdep_map *lock, int nested, unsigned long ip)
 {
 	struct task_struct *curr = current;
+	unsigned int depth, merged = 1;
 	struct held_lock *hlock;
-	unsigned int depth;
 	int i;
 
 	if (unlikely(!debug_locks))
@@ -4091,14 +4107,15 @@ __lock_release(struct lockdep_map *lock,
 	if (i == depth-1)
 		return 1;
 
-	if (reacquire_held_locks(curr, depth, i + 1))
+	if (reacquire_held_locks(curr, depth, i + 1, &merged))
 		return 0;
 
 	/*
 	 * We had N bottles of beer on the wall, we drank one, but now
 	 * there's not N-1 bottles of beer left on the wall...
+	 * Pouring two of the bottles together is acceptable.
 	 */
-	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth-1);
+	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged);
 
 	/*
 	 * Since reacquire_held_locks() would have called check_chain_key()

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references
  2019-05-24 20:15 ` [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references Imre Deak
@ 2019-05-27 15:14   ` Peter Zijlstra
  2019-05-27 15:44     ` Imre Deak
  2019-05-27 16:06     ` Peter Zijlstra
  2019-06-03 13:32   ` [tip:locking/core] locking/lockdep: " tip-bot for Imre Deak
  1 sibling, 2 replies; 11+ messages in thread
From: Peter Zijlstra @ 2019-05-27 15:14 UTC (permalink / raw)
  To: Imre Deak; +Cc: LKML, Ville Syrjälä, Ingo Molnar, Will Deacon

On Fri, May 24, 2019 at 11:15:09PM +0300, Imre Deak wrote:
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 967352d32af1..9e2a4ab6c731 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -3637,6 +3637,11 @@ print_lock_nested_lock_not_held(struct task_struct *curr,
>  
>  static int __lock_is_held(const struct lockdep_map *lock, int read);
>  
> +static int hlock_reference(int reference)
> +{
> +	return reference ? : 1;
> +}
> +
>  /*
>   * This gets called for every mutex_lock*()/spin_lock*() operation.
>   * We maintain the dependency maps and validate the locking attempt:
> @@ -3702,17 +3707,15 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
>  	if (depth) {
>  		hlock = curr->held_locks + depth - 1;
>  		if (hlock->class_idx == class_idx && nest_lock) {
> -			if (hlock->references) {
> -				/*
> -				 * Check: unsigned int references overflow.
> -				 */
> -				if (DEBUG_LOCKS_WARN_ON(hlock->references == UINT_MAX))

What tree is this against? Afaict this is still 12 bits ?!

> -					return 0;
> +			/*
> +			 * Check: unsigned int references overflow.
> +			 */
> +			if (DEBUG_LOCKS_WARN_ON(hlock_reference(hlock->references) >
> +						UINT_MAX - hlock_reference(references)))

Idem. Also very weird overflow check..

> +				return 0;
>  
> -				hlock->references++;
> -			} else {
> -				hlock->references = 2;
> -			}
> +			hlock->references = hlock_reference(hlock->references) +
> +					    hlock_reference(references);
>  
>  			return 2;
>  		}
> -- 
> 2.17.1
> 

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [PATCH v2 1/2] lockdep: Fix OOO unlock when hlocks need merging
  2019-05-27 15:02 ` [PATCH v2 1/2] lockdep: Fix OOO unlock when hlocks need merging Peter Zijlstra
@ 2019-05-27 15:21   ` Imre Deak
  0 siblings, 0 replies; 11+ messages in thread
From: Imre Deak @ 2019-05-27 15:21 UTC (permalink / raw)
  To: Peter Zijlstra; +Cc: LKML, Ville Syrjälä, Ingo Molnar, Will Deacon

On Mon, May 27, 2019 at 05:02:51PM +0200, Peter Zijlstra wrote:
> On Fri, May 24, 2019 at 11:15:08PM +0300, Imre Deak wrote:
> > 
> > 	ww_mutex_lock(&ww_lock_a, &ww_ctx);
> > 
> > 	mutex_lock(&lock_c);
> > 
> > 	ww_mutex_lock(&ww_lock_b, &ww_ctx);
> > 
> > 	mutex_unlock(&lock_c);		(*)
> 
> > triggers the following WARN in __lock_release() when doing the unlock at *:
> > 
> > 	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - 1);
> > 
> > The problem is that the WARN check doesn't take into account the merging
> > of ww_lock_a and ww_lock_b which results in decreasing curr->lockdep_depth
> > by 2 not only 1.
> 
> Cute...
> 
> > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > index c40fba54e324..967352d32af1 100644
> > --- a/kernel/locking/lockdep.c
> > +++ b/kernel/locking/lockdep.c
> > @@ -3714,7 +3714,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
> >  				hlock->references = 2;
> >  			}
> >  
> > -			return 1;
> > +			return 2;
> >  		}
> >  	}
> >  
> > @@ -3920,22 +3920,33 @@ static struct held_lock *find_held_lock(struct task_struct *curr,
> >  }
> >  
> >  static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
> > -			      int idx)
> > +				int idx, bool *first_merged)
> >  {
> >  	struct held_lock *hlock;
> > +	int first_idx = idx;
> >  
> >  	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
> >  		return 0;
> >  
> >  	for (hlock = curr->held_locks + idx; idx < depth; idx++, hlock++) {
> > -		if (!__lock_acquire(hlock->instance,
> > +		switch (__lock_acquire(hlock->instance,
> >  				    hlock_class(hlock)->subclass,
> >  				    hlock->trylock,
> >  				    hlock->read, hlock->check,
> >  				    hlock->hardirqs_off,
> >  				    hlock->nest_lock, hlock->acquire_ip,
> > -				    hlock->references, hlock->pin_count))
> > +				    hlock->references, hlock->pin_count)) {
> > +		case 0:
> >  			return 1;
> > +		case 1:
> > +			break;
> > +		case 2:
> > +			*first_merged = idx == first_idx;
> > +			break;
> > +		default:
> > +			WARN_ON(1);
> > +			return 0;
> > +		}
> >  	}
> >  	return 0;
> >  }
> 
> Does it work for you if I change it like so?

Yep, works this way, and yes thought later that canceling *first_merged
for idx!=first_idx was a bit strange (even if it still worked).

> 
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -3712,7 +3712,7 @@ static int __lock_acquire(struct lockdep
>  				hlock->references = 2;
>  			}
>  
> -			return 1;
> +			return 2;
>  		}
>  	}
>  
> @@ -3918,22 +3918,33 @@ static struct held_lock *find_held_lock(
>  }
>  
>  static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
> -			      int idx)
> +				int idx, unsigned int *merged)
>  {
>  	struct held_lock *hlock;
> +	int first_idx = idx;
>  
>  	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
>  		return 0;
>  
>  	for (hlock = curr->held_locks + idx; idx < depth; idx++, hlock++) {
> -		if (!__lock_acquire(hlock->instance,
> +		switch (__lock_acquire(hlock->instance,
>  				    hlock_class(hlock)->subclass,
>  				    hlock->trylock,
>  				    hlock->read, hlock->check,
>  				    hlock->hardirqs_off,
>  				    hlock->nest_lock, hlock->acquire_ip,
> -				    hlock->references, hlock->pin_count))
> +				    hlock->references, hlock->pin_count)) {
> +		case 0:
>  			return 1;
> +		case 1:
> +			break;
> +		case 2:
> +			*merged += (idx == first_idx);
> +			break;
> +		default:
> +			WARN_ON(1);
> +			return 0;
> +		}
>  	}
>  	return 0;
>  }
> @@ -3944,9 +3955,9 @@ __lock_set_class(struct lockdep_map *loc
>  		 unsigned long ip)
>  {
>  	struct task_struct *curr = current;
> +	unsigned int depth, merged = 0
>  	struct held_lock *hlock;
>  	struct lock_class *class;
> -	unsigned int depth;
>  	int i;
>  
>  	if (unlikely(!debug_locks))
> @@ -3971,14 +3982,14 @@ __lock_set_class(struct lockdep_map *loc
>  	curr->lockdep_depth = i;
>  	curr->curr_chain_key = hlock->prev_chain_key;
>  
> -	if (reacquire_held_locks(curr, depth, i))
> +	if (reacquire_held_locks(curr, depth, i, &merged))
>  		return 0;
>  
>  	/*
>  	 * I took it apart and put it back together again, except now I have
>  	 * these 'spare' parts.. where shall I put them.
>  	 */
> -	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
> +	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged))
>  		return 0;
>  	return 1;
>  }
> @@ -3986,8 +3997,8 @@ __lock_set_class(struct lockdep_map *loc
>  static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
>  {
>  	struct task_struct *curr = current;
> +	unsigned int depth, merged = 0;
>  	struct held_lock *hlock;
> -	unsigned int depth;
>  	int i;
>  
>  	if (unlikely(!debug_locks))
> @@ -4012,7 +4023,7 @@ static int __lock_downgrade(struct lockd
>  	hlock->read = 1;
>  	hlock->acquire_ip = ip;
>  
> -	if (reacquire_held_locks(curr, depth, i))
> +	if (reacquire_held_locks(curr, depth, i, &merged))
>  		return 0;
>  
>  	/*
> @@ -4021,6 +4032,11 @@ static int __lock_downgrade(struct lockd
>  	 */
>  	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
>  		return 0;
> +
> +	/* Merging can't happen with unchanged classes.. */
> +	if (DEBUG_LOCKS_WARN_ON(merged))
> +		return 0;
> +
>  	return 1;
>  }
>  
> @@ -4035,8 +4051,8 @@ static int
>  __lock_release(struct lockdep_map *lock, int nested, unsigned long ip)
>  {
>  	struct task_struct *curr = current;
> +	unsigned int depth, merged = 1;
>  	struct held_lock *hlock;
> -	unsigned int depth;
>  	int i;
>  
>  	if (unlikely(!debug_locks))
> @@ -4091,14 +4107,15 @@ __lock_release(struct lockdep_map *lock,
>  	if (i == depth-1)
>  		return 1;
>  
> -	if (reacquire_held_locks(curr, depth, i + 1))
> +	if (reacquire_held_locks(curr, depth, i + 1, &merged))
>  		return 0;
>  
>  	/*
>  	 * We had N bottles of beer on the wall, we drank one, but now
>  	 * there's not N-1 bottles of beer left on the wall...
> +	 * Pouring two of the bottles together is acceptable.
>  	 */
> -	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth-1);
> +	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged);
>  
>  	/*
>  	 * Since reacquire_held_locks() would have called check_chain_key()

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references
  2019-05-27 15:14   ` Peter Zijlstra
@ 2019-05-27 15:44     ` Imre Deak
  2019-05-27 16:10       ` Peter Zijlstra
  2019-05-27 16:06     ` Peter Zijlstra
  1 sibling, 1 reply; 11+ messages in thread
From: Imre Deak @ 2019-05-27 15:44 UTC (permalink / raw)
  To: Peter Zijlstra; +Cc: LKML, Ville Syrjälä, Ingo Molnar, Will Deacon

On Mon, May 27, 2019 at 05:14:38PM +0200, Peter Zijlstra wrote:
> On Fri, May 24, 2019 at 11:15:09PM +0300, Imre Deak wrote:
> > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > index 967352d32af1..9e2a4ab6c731 100644
> > --- a/kernel/locking/lockdep.c
> > +++ b/kernel/locking/lockdep.c
> > @@ -3637,6 +3637,11 @@ print_lock_nested_lock_not_held(struct task_struct *curr,
> >  
> >  static int __lock_is_held(const struct lockdep_map *lock, int read);
> >  
> > +static int hlock_reference(int reference)
> > +{
> > +	return reference ? : 1;
> > +}
> > +
> >  /*
> >   * This gets called for every mutex_lock*()/spin_lock*() operation.
> >   * We maintain the dependency maps and validate the locking attempt:
> > @@ -3702,17 +3707,15 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
> >  	if (depth) {
> >  		hlock = curr->held_locks + depth - 1;
> >  		if (hlock->class_idx == class_idx && nest_lock) {
> > -			if (hlock->references) {
> > -				/*
> > -				 * Check: unsigned int references overflow.
> > -				 */
> > -				if (DEBUG_LOCKS_WARN_ON(hlock->references == UINT_MAX))
> 
> What tree is this against?

I just used our
	git://anongit.freedesktop.org/drm-tip
and the most recent upstream commit in that is:

$ git merge-base drm-tip origin/master
6b0538da5a6ca2129b93cea5afc997226875c402

which has the commit
commit a188339ca5a396acc588e5851ed7e19f66b0ebd9
Author: Linus Torvalds <torvalds@linux-foundation.org>
Date:   Sun May 19 15:47:09 2019 -0700

    Linux 5.2-rc1


> Afaict this is still 12 bits ?!

In the above tree I see
	unsigned int references;
in held_lock which is 32 bits.

> 
> > -					return 0;
> > +			/*
> > +			 * Check: unsigned int references overflow.
> > +			 */
> > +			if (DEBUG_LOCKS_WARN_ON(hlock_reference(hlock->references) >
> > +						UINT_MAX - hlock_reference(references)))
> 
> Idem. Also very weird overflow check..

We could have instead (replacing the addition itself too below):

	if (DEBUG_LOCKS_WARN_ON(
		check_add_overflow(hlock_reference(hlock->references),
				   hlock_reference(references),
				   &hlock_references)))
		return 0;

by having hlock_reference() take and return unsigned int too.

> 
> > +				return 0;
> >  
> > -				hlock->references++;
> > -			} else {
> > -				hlock->references = 2;
> > -			}
> > +			hlock->references = hlock_reference(hlock->references) +
> > +					    hlock_reference(references);
> >  
> >  			return 2;
> >  		}
> > -- 
> > 2.17.1
> > 

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references
  2019-05-27 15:14   ` Peter Zijlstra
  2019-05-27 15:44     ` Imre Deak
@ 2019-05-27 16:06     ` Peter Zijlstra
  2019-05-27 16:21       ` Imre Deak
  1 sibling, 1 reply; 11+ messages in thread
From: Peter Zijlstra @ 2019-05-27 16:06 UTC (permalink / raw)
  To: Imre Deak; +Cc: LKML, Ville Syrjälä, Ingo Molnar, Will Deacon

On Mon, May 27, 2019 at 05:14:38PM +0200, Peter Zijlstra wrote:
> On Fri, May 24, 2019 at 11:15:09PM +0300, Imre Deak wrote:
> > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > index 967352d32af1..9e2a4ab6c731 100644
> > --- a/kernel/locking/lockdep.c
> > +++ b/kernel/locking/lockdep.c
> > @@ -3637,6 +3637,11 @@ print_lock_nested_lock_not_held(struct task_struct *curr,
> >  
> >  static int __lock_is_held(const struct lockdep_map *lock, int read);
> >  
> > +static int hlock_reference(int reference)
> > +{
> > +	return reference ? : 1;
> > +}
> > +
> >  /*
> >   * This gets called for every mutex_lock*()/spin_lock*() operation.
> >   * We maintain the dependency maps and validate the locking attempt:
> > @@ -3702,17 +3707,15 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
> >  	if (depth) {
> >  		hlock = curr->held_locks + depth - 1;
> >  		if (hlock->class_idx == class_idx && nest_lock) {
> > -			if (hlock->references) {
> > -				/*
> > -				 * Check: unsigned int references overflow.
> > -				 */
> > -				if (DEBUG_LOCKS_WARN_ON(hlock->references == UINT_MAX))
> 
> What tree is this against? Afaict this is still 12 bits ?!
> 
> > -					return 0;
> > +			/*
> > +			 * Check: unsigned int references overflow.
> > +			 */
> > +			if (DEBUG_LOCKS_WARN_ON(hlock_reference(hlock->references) >
> > +						UINT_MAX - hlock_reference(references)))
> 
> Idem. Also very weird overflow check..
> 
> > +				return 0;
> >  
> > -				hlock->references++;
> > -			} else {
> > -				hlock->references = 2;
> > -			}
> > +			hlock->references = hlock_reference(hlock->references) +
> > +					    hlock_reference(references);
> >  
> >  			return 2;
> >  		}

I think you wanted something like this: ?

--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3731,6 +3731,11 @@ print_lock_nested_lock_not_held(struct t
 
 static int __lock_is_held(const struct lockdep_map *lock, int read);
 
+static inline int hlock_references(struct held_lock *hlock)
+{
+	return hlock->references ? : 1;
+}
+
 /*
  * This gets called for every mutex_lock*()/spin_lock*() operation.
  * We maintain the dependency maps and validate the locking attempt:
@@ -3796,17 +3801,14 @@ static int __lock_acquire(struct lockdep
 	if (depth) {
 		hlock = curr->held_locks + depth - 1;
 		if (hlock->class_idx == class_idx && nest_lock) {
-			if (hlock->references) {
-				/*
-				 * Check: unsigned int references:12, overflow.
-				 */
-				if (DEBUG_LOCKS_WARN_ON(hlock->references == (1 << 12)-1))
-					return 0;
-
-				hlock->references++;
-			} else {
-				hlock->references = 2;
-			}
+			if (!references)
+				references++;
+
+			hlock->references = hlock_references(hlock) + references;
+
+			/* Overflow */
+			if (DEBUG_LOCKS_WARN_ON(hlock->references < references))
+				return 0;
 
 			return 2;
 		}

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references
  2019-05-27 15:44     ` Imre Deak
@ 2019-05-27 16:10       ` Peter Zijlstra
  0 siblings, 0 replies; 11+ messages in thread
From: Peter Zijlstra @ 2019-05-27 16:10 UTC (permalink / raw)
  To: Imre Deak; +Cc: LKML, Ville Syrjälä, Ingo Molnar, Will Deacon

On Mon, May 27, 2019 at 06:44:29PM +0300, Imre Deak wrote:
> On Mon, May 27, 2019 at 05:14:38PM +0200, Peter Zijlstra wrote:
> > On Fri, May 24, 2019 at 11:15:09PM +0300, Imre Deak wrote:

> > > -				if (DEBUG_LOCKS_WARN_ON(hlock->references == UINT_MAX))
> > 
> > What tree is this against?
> 
> I just used our
> 	git://anongit.freedesktop.org/drm-tip
> and the most recent upstream commit in that is:
> 

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/lockdep.h#n270

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references
  2019-05-27 16:06     ` Peter Zijlstra
@ 2019-05-27 16:21       ` Imre Deak
  0 siblings, 0 replies; 11+ messages in thread
From: Imre Deak @ 2019-05-27 16:21 UTC (permalink / raw)
  To: Peter Zijlstra; +Cc: LKML, Ville Syrjälä, Ingo Molnar, Will Deacon

On Mon, May 27, 2019 at 06:06:18PM +0200, Peter Zijlstra wrote:
> On Mon, May 27, 2019 at 05:14:38PM +0200, Peter Zijlstra wrote:
> > On Fri, May 24, 2019 at 11:15:09PM +0300, Imre Deak wrote:
> > > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > > index 967352d32af1..9e2a4ab6c731 100644
> > > --- a/kernel/locking/lockdep.c
> > > +++ b/kernel/locking/lockdep.c
> > > @@ -3637,6 +3637,11 @@ print_lock_nested_lock_not_held(struct task_struct *curr,
> > >  
> > >  static int __lock_is_held(const struct lockdep_map *lock, int read);
> > >  
> > > +static int hlock_reference(int reference)
> > > +{
> > > +	return reference ? : 1;
> > > +}
> > > +
> > >  /*
> > >   * This gets called for every mutex_lock*()/spin_lock*() operation.
> > >   * We maintain the dependency maps and validate the locking attempt:
> > > @@ -3702,17 +3707,15 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
> > >  	if (depth) {
> > >  		hlock = curr->held_locks + depth - 1;
> > >  		if (hlock->class_idx == class_idx && nest_lock) {
> > > -			if (hlock->references) {
> > > -				/*
> > > -				 * Check: unsigned int references overflow.
> > > -				 */
> > > -				if (DEBUG_LOCKS_WARN_ON(hlock->references == UINT_MAX))
> > 
> > What tree is this against? Afaict this is still 12 bits ?!
> > 
> > > -					return 0;
> > > +			/*
> > > +			 * Check: unsigned int references overflow.
> > > +			 */
> > > +			if (DEBUG_LOCKS_WARN_ON(hlock_reference(hlock->references) >
> > > +						UINT_MAX - hlock_reference(references)))
> > 
> > Idem. Also very weird overflow check..
> > 
> > > +				return 0;
> > >  
> > > -				hlock->references++;
> > > -			} else {
> > > -				hlock->references = 2;
> > > -			}
> > > +			hlock->references = hlock_reference(hlock->references) +
> > > +					    hlock_reference(references);
> > >  
> > >  			return 2;
> > >  		}
> 
> I think you wanted something like this: ?
> 
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -3731,6 +3731,11 @@ print_lock_nested_lock_not_held(struct t
>  
>  static int __lock_is_held(const struct lockdep_map *lock, int read);
>  
> +static inline int hlock_references(struct held_lock *hlock)
> +{
> +	return hlock->references ? : 1;
> +}
> +
>  /*
>   * This gets called for every mutex_lock*()/spin_lock*() operation.
>   * We maintain the dependency maps and validate the locking attempt:
> @@ -3796,17 +3801,14 @@ static int __lock_acquire(struct lockdep
>  	if (depth) {
>  		hlock = curr->held_locks + depth - 1;
>  		if (hlock->class_idx == class_idx && nest_lock) {
> -			if (hlock->references) {
> -				/*
> -				 * Check: unsigned int references:12, overflow.
> -				 */
> -				if (DEBUG_LOCKS_WARN_ON(hlock->references == (1 << 12)-1))
> -					return 0;
> -
> -				hlock->references++;
> -			} else {
> -				hlock->references = 2;
> -			}
> +			if (!references)
> +				references++;
> +
> +			hlock->references = hlock_references(hlock) + references;
> +
> +			/* Overflow */
> +			if (DEBUG_LOCKS_WARN_ON(hlock->references < references))
> +				return 0;

Yes, it works.

>  
>  			return 2;
>  		}

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [tip:locking/core] locking/lockdep: Fix OOO unlock when hlocks need merging
  2019-05-24 20:15 [PATCH v2 1/2] lockdep: Fix OOO unlock when hlocks need merging Imre Deak
  2019-05-24 20:15 ` [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references Imre Deak
  2019-05-27 15:02 ` [PATCH v2 1/2] lockdep: Fix OOO unlock when hlocks need merging Peter Zijlstra
@ 2019-06-03 13:31 ` tip-bot for Imre Deak
  2 siblings, 0 replies; 11+ messages in thread
From: tip-bot for Imre Deak @ 2019-06-03 13:31 UTC (permalink / raw)
  To: linux-tip-commits
  Cc: peterz, tglx, hpa, torvalds, linux-kernel, mingo, will.deacon, imre.deak

Commit-ID:  8c8889d8eaf4501ae4aaf870b6f8f55db5d5109a
Gitweb:     https://git.kernel.org/tip/8c8889d8eaf4501ae4aaf870b6f8f55db5d5109a
Author:     Imre Deak <imre.deak@intel.com>
AuthorDate: Fri, 24 May 2019 23:15:08 +0300
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Mon, 3 Jun 2019 12:32:29 +0200

locking/lockdep: Fix OOO unlock when hlocks need merging

The sequence

	static DEFINE_WW_CLASS(test_ww_class);

	struct ww_acquire_ctx ww_ctx;
	struct ww_mutex ww_lock_a;
	struct ww_mutex ww_lock_b;
	struct mutex lock_c;
	struct mutex lock_d;

	ww_acquire_init(&ww_ctx, &test_ww_class);

	ww_mutex_init(&ww_lock_a, &test_ww_class);
	ww_mutex_init(&ww_lock_b, &test_ww_class);

	mutex_init(&lock_c);

	ww_mutex_lock(&ww_lock_a, &ww_ctx);

	mutex_lock(&lock_c);

	ww_mutex_lock(&ww_lock_b, &ww_ctx);

	mutex_unlock(&lock_c);		(*)

	ww_mutex_unlock(&ww_lock_b);
	ww_mutex_unlock(&ww_lock_a);

	ww_acquire_fini(&ww_ctx);

triggers the following WARN in __lock_release() when doing the unlock at *:

	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - 1);

The problem is that the WARN check doesn't take into account the merging
of ww_lock_a and ww_lock_b which results in decreasing curr->lockdep_depth
by 2 not only 1.

Note that the following sequence doesn't trigger the WARN, since there
won't be any hlock merging.

	ww_acquire_init(&ww_ctx, &test_ww_class);

	ww_mutex_init(&ww_lock_a, &test_ww_class);
	ww_mutex_init(&ww_lock_b, &test_ww_class);

	mutex_init(&lock_c);
	mutex_init(&lock_d);

	ww_mutex_lock(&ww_lock_a, &ww_ctx);

	mutex_lock(&lock_c);
	mutex_lock(&lock_d);

	ww_mutex_lock(&ww_lock_b, &ww_ctx);

	mutex_unlock(&lock_d);

	ww_mutex_unlock(&ww_lock_b);
	ww_mutex_unlock(&ww_lock_a);

	mutex_unlock(&lock_c);

	ww_acquire_fini(&ww_ctx);

In general both of the above two sequences are valid and shouldn't
trigger any lockdep warning.

Fix this by taking the decrement due to the hlock merging into account
during lock release and hlock class re-setting. Merging can't happen
during lock downgrading since there won't be a new possibility to merge
hlocks in that case, so add a WARN if merging still happens then.

Signed-off-by: Imre Deak <imre.deak@intel.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Will Deacon <will.deacon@arm.com>
Cc: ville.syrjala@linux.intel.com
Link: https://lkml.kernel.org/r/20190524201509.9199-1-imre.deak@intel.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/locking/lockdep.c | 41 +++++++++++++++++++++++++++++------------
 1 file changed, 29 insertions(+), 12 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 2168e94715b9..6c97f67ec321 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3808,7 +3808,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 				hlock->references = 2;
 			}
 
-			return 1;
+			return 2;
 		}
 	}
 
@@ -4011,22 +4011,33 @@ out:
 }
 
 static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
-			      int idx)
+				int idx, unsigned int *merged)
 {
 	struct held_lock *hlock;
+	int first_idx = idx;
 
 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
 		return 0;
 
 	for (hlock = curr->held_locks + idx; idx < depth; idx++, hlock++) {
-		if (!__lock_acquire(hlock->instance,
+		switch (__lock_acquire(hlock->instance,
 				    hlock_class(hlock)->subclass,
 				    hlock->trylock,
 				    hlock->read, hlock->check,
 				    hlock->hardirqs_off,
 				    hlock->nest_lock, hlock->acquire_ip,
-				    hlock->references, hlock->pin_count))
+				    hlock->references, hlock->pin_count)) {
+		case 0:
 			return 1;
+		case 1:
+			break;
+		case 2:
+			*merged += (idx == first_idx);
+			break;
+		default:
+			WARN_ON(1);
+			return 0;
+		}
 	}
 	return 0;
 }
@@ -4037,9 +4048,9 @@ __lock_set_class(struct lockdep_map *lock, const char *name,
 		 unsigned long ip)
 {
 	struct task_struct *curr = current;
+	unsigned int depth, merged = 0;
 	struct held_lock *hlock;
 	struct lock_class *class;
-	unsigned int depth;
 	int i;
 
 	if (unlikely(!debug_locks))
@@ -4066,14 +4077,14 @@ __lock_set_class(struct lockdep_map *lock, const char *name,
 	curr->lockdep_depth = i;
 	curr->curr_chain_key = hlock->prev_chain_key;
 
-	if (reacquire_held_locks(curr, depth, i))
+	if (reacquire_held_locks(curr, depth, i, &merged))
 		return 0;
 
 	/*
 	 * I took it apart and put it back together again, except now I have
 	 * these 'spare' parts.. where shall I put them.
 	 */
-	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
+	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged))
 		return 0;
 	return 1;
 }
@@ -4081,8 +4092,8 @@ __lock_set_class(struct lockdep_map *lock, const char *name,
 static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
 {
 	struct task_struct *curr = current;
+	unsigned int depth, merged = 0;
 	struct held_lock *hlock;
-	unsigned int depth;
 	int i;
 
 	if (unlikely(!debug_locks))
@@ -4109,7 +4120,11 @@ static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
 	hlock->read = 1;
 	hlock->acquire_ip = ip;
 
-	if (reacquire_held_locks(curr, depth, i))
+	if (reacquire_held_locks(curr, depth, i, &merged))
+		return 0;
+
+	/* Merging can't happen with unchanged classes.. */
+	if (DEBUG_LOCKS_WARN_ON(merged))
 		return 0;
 
 	/*
@@ -4118,6 +4133,7 @@ static int __lock_downgrade(struct lockdep_map *lock, unsigned long ip)
 	 */
 	if (DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth))
 		return 0;
+
 	return 1;
 }
 
@@ -4132,8 +4148,8 @@ static int
 __lock_release(struct lockdep_map *lock, unsigned long ip)
 {
 	struct task_struct *curr = current;
+	unsigned int depth, merged = 1;
 	struct held_lock *hlock;
-	unsigned int depth;
 	int i;
 
 	if (unlikely(!debug_locks))
@@ -4192,14 +4208,15 @@ __lock_release(struct lockdep_map *lock, unsigned long ip)
 	if (i == depth-1)
 		return 1;
 
-	if (reacquire_held_locks(curr, depth, i + 1))
+	if (reacquire_held_locks(curr, depth, i + 1, &merged))
 		return 0;
 
 	/*
 	 * We had N bottles of beer on the wall, we drank one, but now
 	 * there's not N-1 bottles of beer left on the wall...
+	 * Pouring two of the bottles together is acceptable.
 	 */
-	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth-1);
+	DEBUG_LOCKS_WARN_ON(curr->lockdep_depth != depth - merged);
 
 	/*
 	 * Since reacquire_held_locks() would have called check_chain_key()

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [tip:locking/core] locking/lockdep: Fix merging of hlocks with non-zero references
  2019-05-24 20:15 ` [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references Imre Deak
  2019-05-27 15:14   ` Peter Zijlstra
@ 2019-06-03 13:32   ` tip-bot for Imre Deak
  1 sibling, 0 replies; 11+ messages in thread
From: tip-bot for Imre Deak @ 2019-06-03 13:32 UTC (permalink / raw)
  To: linux-tip-commits
  Cc: tglx, torvalds, will.deacon, ville.syrjala, mingo, hpa,
	imre.deak, linux-kernel, peterz

Commit-ID:  d9349850e188b8b59e5322fda17ff389a1c0cd7d
Gitweb:     https://git.kernel.org/tip/d9349850e188b8b59e5322fda17ff389a1c0cd7d
Author:     Imre Deak <imre.deak@intel.com>
AuthorDate: Fri, 24 May 2019 23:15:09 +0300
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Mon, 3 Jun 2019 12:32:56 +0200

locking/lockdep: Fix merging of hlocks with non-zero references

The sequence

	static DEFINE_WW_CLASS(test_ww_class);

	struct ww_acquire_ctx ww_ctx;
	struct ww_mutex ww_lock_a;
	struct ww_mutex ww_lock_b;
	struct ww_mutex ww_lock_c;
	struct mutex lock_c;

	ww_acquire_init(&ww_ctx, &test_ww_class);

	ww_mutex_init(&ww_lock_a, &test_ww_class);
	ww_mutex_init(&ww_lock_b, &test_ww_class);
	ww_mutex_init(&ww_lock_c, &test_ww_class);

	mutex_init(&lock_c);

	ww_mutex_lock(&ww_lock_a, &ww_ctx);

	mutex_lock(&lock_c);

	ww_mutex_lock(&ww_lock_b, &ww_ctx);
	ww_mutex_lock(&ww_lock_c, &ww_ctx);

	mutex_unlock(&lock_c);	(*)

	ww_mutex_unlock(&ww_lock_c);
	ww_mutex_unlock(&ww_lock_b);
	ww_mutex_unlock(&ww_lock_a);

	ww_acquire_fini(&ww_ctx); (**)

will trigger the following error in __lock_release() when calling
mutex_release() at **:

	DEBUG_LOCKS_WARN_ON(depth <= 0)

The problem is that the hlock merging happening at * updates the
references for test_ww_class incorrectly to 3 whereas it should've
updated it to 4 (representing all the instances for ww_ctx and
ww_lock_[abc]).

Fix this by updating the references during merging correctly taking into
account that we can have non-zero references (both for the hlock that we
merge into another hlock or for the hlock we are merging into).

Signed-off-by: Imre Deak <imre.deak@intel.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: =?UTF-8?q?Ville=20Syrj=C3=A4l=C3=A4?= <ville.syrjala@linux.intel.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Will Deacon <will.deacon@arm.com>
Link: https://lkml.kernel.org/r/20190524201509.9199-2-imre.deak@intel.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/locking/lockdep.c | 18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 6c97f67ec321..48a840adb281 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -3796,17 +3796,17 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	if (depth) {
 		hlock = curr->held_locks + depth - 1;
 		if (hlock->class_idx == class_idx && nest_lock) {
-			if (hlock->references) {
-				/*
-				 * Check: unsigned int references:12, overflow.
-				 */
-				if (DEBUG_LOCKS_WARN_ON(hlock->references == (1 << 12)-1))
-					return 0;
+			if (!references)
+				references++;
 
+			if (!hlock->references)
 				hlock->references++;
-			} else {
-				hlock->references = 2;
-			}
+
+			hlock->references += references;
+
+			/* Overflow */
+			if (DEBUG_LOCKS_WARN_ON(hlock->references < references))
+				return 0;
 
 			return 2;
 		}

^ permalink raw reply	[flat|nested] 11+ messages in thread

end of thread, other threads:[~2019-06-03 13:33 UTC | newest]

Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-05-24 20:15 [PATCH v2 1/2] lockdep: Fix OOO unlock when hlocks need merging Imre Deak
2019-05-24 20:15 ` [PATCH v2 2/2] lockdep: Fix merging of hlocks with non-zero references Imre Deak
2019-05-27 15:14   ` Peter Zijlstra
2019-05-27 15:44     ` Imre Deak
2019-05-27 16:10       ` Peter Zijlstra
2019-05-27 16:06     ` Peter Zijlstra
2019-05-27 16:21       ` Imre Deak
2019-06-03 13:32   ` [tip:locking/core] locking/lockdep: " tip-bot for Imre Deak
2019-05-27 15:02 ` [PATCH v2 1/2] lockdep: Fix OOO unlock when hlocks need merging Peter Zijlstra
2019-05-27 15:21   ` Imre Deak
2019-06-03 13:31 ` [tip:locking/core] locking/lockdep: " tip-bot for Imre Deak

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).