Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1543491 > unrolled thread

Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-16 15:30 +0100
    Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Peter Zijlstra <peterz@infradead.org> - 2016-12-16 17:10 +0100
    Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Peter Zijlstra <peterz@infradead.org> - 2016-12-16 18:20 +0100
      Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-16 19:20 +0100
        Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Peter Zijlstra <peterz@infradead.org> - 2016-12-16 21:20 +0100
          Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-16 23:40 +0100
    Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Peter Zijlstra <peterz@infradead.org> - 2016-12-16 18:30 +0100
      Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Nicolai Hähnle <nhaehnle@gmail.com> - 2016-12-16 19:20 +0100

#1543491 — Re: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order

Hi Peter and Chris,

(trying to combine the handoff discussion here)

On 06.12.2016 17:55, Peter Zijlstra wrote:
> On Thu, Dec 01, 2016 at 03:06:48PM +0100, Nicolai Hähnle wrote:
>> @@ -693,8 +748,12 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>>  		 * mutex_unlock() handing the lock off to us, do a trylock
>>  		 * before testing the error conditions to make sure we pick up
>>  		 * the handoff.
>> +		 *
>> +		 * For w/w locks, we always need to do this even if we're not
>> +		 * currently the first waiter, because we may have been the
>> +		 * first waiter during the unlock.
>>  		 */
>> -		if (__mutex_trylock(lock, first))
>> +		if (__mutex_trylock(lock, use_ww_ctx || first))
>>  			goto acquired;
>
> So I'm somewhat uncomfortable with this. The point is that with the
> .handoff logic it is very easy to accidentally allow:
>
> 	mutex_lock(&a);
> 	mutex_lock(&a);
>
> And I'm not sure this doesn't make that happen for ww_mutexes. We get to
> this __mutex_trylock() without first having blocked.

Okay, took me a while, but I see the problem. If we have:

	ww_mutex_lock(&a, NULL);
	ww_mutex_lock(&a, ctx);

then it's possible that another currently waiting task sets the HANDOFF 
flag between those calls and we'll allow the second ww_mutex_lock to go 
through.

The concern about picking up a handoff that we didn't request is real, 
though it cannot happen in the first iteration. Perhaps this 
__mutex_trylock can be moved to the end of the loop? See below...


>
>
>>  		/*
>> @@ -716,7 +775,20 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>>  		spin_unlock_mutex(&lock->wait_lock, flags);
>>  		schedule_preempt_disabled();
>>
>> -		if (!first && __mutex_waiter_is_first(lock, &waiter)) {
>> +		if (use_ww_ctx && ww_ctx) {
>> +			/*
>> +			 * Always re-check whether we're in first position. We
>> +			 * don't want to spin if another task with a lower
>> +			 * stamp has taken our position.
>> +			 *
>> +			 * We also may have to set the handoff flag again, if
>> +			 * our position at the head was temporarily taken away.
>> +			 */
>> +			first = __mutex_waiter_is_first(lock, &waiter);
>> +
>> +			if (first)
>> +				__mutex_set_flag(lock, MUTEX_FLAG_HANDOFF);
>> +		} else if (!first && __mutex_waiter_is_first(lock, &waiter)) {
>>  			first = true;
>>  			__mutex_set_flag(lock, MUTEX_FLAG_HANDOFF);
>>  		}
>
> So the point is that !ww_ctx entries are 'skipped' during the insertion
> and therefore, if one becomes first, it must stay first?

Yes. Actually, it should be possible to replace all the cases of 
use_ww_ctx || first with ww_ctx. Similarly, all cases of use_ww_ctx && 
ww_ctx could be replaced by just ww_ctx.

>
>> @@ -728,7 +800,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>>  		 * or we must see its unlock and acquire.
>>  		 */
>>  		if ((first && mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx, true)) ||
>> -		     __mutex_trylock(lock, first))
>> +		     __mutex_trylock(lock, use_ww_ctx || first))
>>  			break;
>>
>>  		spin_lock_mutex(&lock->wait_lock, flags);

Change this code to:

		acquired = first &&
		    mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx,
					  &waiter);
		spin_lock_mutex(&lock->wait_lock, flags);
		
		if (acquired ||
		    __mutex_trylock(lock, use_ww_ctx || first))
			break;
	}

This changes the trylock to always be under the wait_lock, but we 
previously had that at the beginning of the loop anyway. It also removes 
back-to-back calls to __mutex_trylock when going through the loop; and 
for the first iteration, there is a __mutex_trylock under wait_lock 
already before adding ourselves to the wait list.

What do you think?

Nicolai

[toc] | [next] | [standalone]

#1543558

On Fri, Dec 16, 2016 at 03:19:43PM +0100, Nicolai Hähnle wrote:
> Hi Peter and Chris,
> 
> (trying to combine the handoff discussion here)
> 
> On 06.12.2016 17:55, Peter Zijlstra wrote:
> >On Thu, Dec 01, 2016 at 03:06:48PM +0100, Nicolai Hähnle wrote:
> >>@@ -693,8 +748,12 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
> >> 		 * mutex_unlock() handing the lock off to us, do a trylock
> >> 		 * before testing the error conditions to make sure we pick up
> >> 		 * the handoff.
> >>+		 *
> >>+		 * For w/w locks, we always need to do this even if we're not
> >>+		 * currently the first waiter, because we may have been the
> >>+		 * first waiter during the unlock.
> >> 		 */
> >>-		if (__mutex_trylock(lock, first))
> >>+		if (__mutex_trylock(lock, use_ww_ctx || first))
> >> 			goto acquired;
> >
> >So I'm somewhat uncomfortable with this. The point is that with the
> >.handoff logic it is very easy to accidentally allow:
> >
> >	mutex_lock(&a);
> >	mutex_lock(&a);
> >
> >And I'm not sure this doesn't make that happen for ww_mutexes. We get to
> >this __mutex_trylock() without first having blocked.
> 
> Okay, took me a while, but I see the problem. If we have:
> 
> 	ww_mutex_lock(&a, NULL);
> 	ww_mutex_lock(&a, ctx);
> 
> then it's possible that another currently waiting task sets the HANDOFF flag
> between those calls and we'll allow the second ww_mutex_lock to go through.

Its worse, __mutex_trylock() doesn't check if MUTEX_FLAG_HANDOFF is set,
if .handoff == true && __owner_task() == current, we 'acquire'.

And since 'use_ww_ctx' is unconditionally true for ww_mutex_lock(), the
sequence:

	ww_mutex_lock(&a, ...);
	ww_mutex_lock(&a, ...);

will 'work'.

[toc] | [prev] | [next] | [standalone]

#1543604

On Fri, Dec 16, 2016 at 03:19:43PM +0100, Nicolai Hähnle wrote:
> The concern about picking up a handoff that we didn't request is real,
> though it cannot happen in the first iteration. Perhaps this __mutex_trylock
> can be moved to the end of the loop? See below...


> >>@@ -728,7 +800,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
> >> 		 * or we must see its unlock and acquire.
> >> 		 */
> >> 		if ((first && mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx, true)) ||
> >>-		     __mutex_trylock(lock, first))
> >>+		     __mutex_trylock(lock, use_ww_ctx || first))
> >> 			break;
> >>
> >> 		spin_lock_mutex(&lock->wait_lock, flags);
> 
> Change this code to:
> 
> 		acquired = first &&
> 		    mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx,
> 					  &waiter);
> 		spin_lock_mutex(&lock->wait_lock, flags);
> 		
> 		if (acquired ||
> 		    __mutex_trylock(lock, use_ww_ctx || first))
> 			break;

			goto acquired;

will work lots better.

> 	}
> 
> This changes the trylock to always be under the wait_lock, but we previously
> had that at the beginning of the loop anyway. 

> It also removes back-to-back
> calls to __mutex_trylock when going through the loop;

Yeah, I had that explicitly. It allows taking the mutex when
mutex_unlock() is still holding the wait_lock.

> and for the first
> iteration, there is a __mutex_trylock under wait_lock already before adding
> ourselves to the wait list.

Correct.

[toc] | [prev] | [next] | [standalone]

#1543652

On 16.12.2016 18:15, Peter Zijlstra wrote:
> On Fri, Dec 16, 2016 at 03:19:43PM +0100, Nicolai Hähnle wrote:
>> The concern about picking up a handoff that we didn't request is real,
>> though it cannot happen in the first iteration. Perhaps this __mutex_trylock
>> can be moved to the end of the loop? See below...
>
>
>>>> @@ -728,7 +800,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>>>> 		 * or we must see its unlock and acquire.
>>>> 		 */
>>>> 		if ((first && mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx, true)) ||
>>>> -		     __mutex_trylock(lock, first))
>>>> +		     __mutex_trylock(lock, use_ww_ctx || first))
>>>> 			break;
>>>>
>>>> 		spin_lock_mutex(&lock->wait_lock, flags);
>>
>> Change this code to:
>>
>> 		acquired = first &&
>> 		    mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx,
>> 					  &waiter);
>> 		spin_lock_mutex(&lock->wait_lock, flags);
>> 		
>> 		if (acquired ||
>> 		    __mutex_trylock(lock, use_ww_ctx || first))
>> 			break;
>
> 			goto acquired;
>
> will work lots better.

Wasn't explicit enough, sorry. The idea was to get rid of the acquired 
label and change things so that all paths exit the loop with wait_lock 
held. That seems cleaner to me.


>> 	}
>>
>> This changes the trylock to always be under the wait_lock, but we previously
>> had that at the beginning of the loop anyway.
>
>> It also removes back-to-back
>> calls to __mutex_trylock when going through the loop;
>
> Yeah, I had that explicitly. It allows taking the mutex when
> mutex_unlock() is still holding the wait_lock.

mutex_optimistic_spin() already calls __mutex_trylock, and for the 
no-spin case, __mutex_unlock_slowpath() only calls wake_up_q() after 
releasing the wait_lock.

So I don't see the purpose of the back-to-back __mutex_trylocks, 
especially considering that if the first one succeeds, we immediately 
take the wait_lock anyway.

Nicolai



>> and for the first
>> iteration, there is a __mutex_trylock under wait_lock already before adding
>> ourselves to the wait list.
>
> Correct.
>

[toc] | [prev] | [next] | [standalone]

#1543731

On Fri, Dec 16, 2016 at 07:11:41PM +0100, Nicolai Hähnle wrote:
> mutex_optimistic_spin() already calls __mutex_trylock, and for the no-spin
> case, __mutex_unlock_slowpath() only calls wake_up_q() after releasing the
> wait_lock.

mutex_optimistic_spin() is a no-op when !CONFIG_MUTEX_SPIN_ON_OWNER

[toc] | [prev] | [next] | [standalone]

#1543813

On 16.12.2016 21:00, Peter Zijlstra wrote:
> On Fri, Dec 16, 2016 at 07:11:41PM +0100, Nicolai Hähnle wrote:
>> mutex_optimistic_spin() already calls __mutex_trylock, and for the no-spin
>> case, __mutex_unlock_slowpath() only calls wake_up_q() after releasing the
>> wait_lock.
>
> mutex_optimistic_spin() is a no-op when !CONFIG_MUTEX_SPIN_ON_OWNER

Does this change the conclusion in a meaningful way? I did mention the 
no-spin case in the very part you quoted...

Again, AFAIU we're talking about the part of my proposal that turns what 
is effectively

	__mutex_trylock(lock, ...);
	spin_lock_mutex(&lock->wait_lock, flags);

(independent of whether the trylock succeeds or not!) into

	spin_lock_mutex(&lock->wait_lock, flags);
	__mutex_trylock(lock, ...);

in an effort to streamline the code overall.

Also AFAIU, you're concerned that spin_lock_mutex(...) has to wait for 
an unlock from mutex_unlock(), but when does that actually happen with 
relevant probability?

When we spin optimistically, that could happen -- except that 
__mutex_trylock is already called in mutex_optimistic_spin, so it 
doesn't matter. When we don't spin -- whether due to .config or !first 
-- then the chance of overlap with mutex_unlock is exceedingly small.

Even if we do overlap, we'll have to wait for mutex_unlock to release 
the wait_lock anyway! So what good does acquiring the lock first really do?

Anyway, this is really more of an argument about whether there's really 
a good reason to calling __mutex_trylock twice in that loop. I don't 
think there is, your arguments certainly haven't been convincing, but 
the issue can be side-stepped for this patch by keeping the trylock 
calls as they are and just setting first = true unconditionally for 
ww_ctx != NULL (but keep the logic for when to set the HANDOFF flag 
as-is). Should probably rename the variable s/first/handoff/ then.

Nicolai

[toc] | [prev] | [next] | [standalone]

#1543607

On Fri, Dec 16, 2016 at 03:19:43PM +0100, Nicolai Hähnle wrote:
> >>@@ -716,7 +775,20 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
> >> 		spin_unlock_mutex(&lock->wait_lock, flags);
> >> 		schedule_preempt_disabled();
> >>
> >>-		if (!first && __mutex_waiter_is_first(lock, &waiter)) {
> >>+		if (use_ww_ctx && ww_ctx) {
> >>+			/*
> >>+			 * Always re-check whether we're in first position. We
> >>+			 * don't want to spin if another task with a lower
> >>+			 * stamp has taken our position.
> >>+			 *
> >>+			 * We also may have to set the handoff flag again, if
> >>+			 * our position at the head was temporarily taken away.
> >>+			 */
> >>+			first = __mutex_waiter_is_first(lock, &waiter);
> >>+
> >>+			if (first)
> >>+				__mutex_set_flag(lock, MUTEX_FLAG_HANDOFF);
> >>+		} else if (!first && __mutex_waiter_is_first(lock, &waiter)) {
> >> 			first = true;
> >> 			__mutex_set_flag(lock, MUTEX_FLAG_HANDOFF);
> >> 		}
> >
> >So the point is that !ww_ctx entries are 'skipped' during the insertion
> >and therefore, if one becomes first, it must stay first?
> 
> Yes. Actually, it should be possible to replace all the cases of use_ww_ctx
> || first with ww_ctx. Similarly, all cases of use_ww_ctx && ww_ctx could be
> replaced by just ww_ctx.


I'm not seeing how "use_ww_ctx || first" -> "ww_ctx" works. And while
"use_ww_ctx && ww_ctx" -> "ww_ctx" is correct, it didn't work right on
some older GCCs, they choked on value propagation for ww_ctx and kept
emitting code even if we passed in NULL. Hence use_ww_ctx.

Arnd is now looking to raise the minimum supported GCC version, so maybe
we should look at that again if he gets anywhere.

[toc] | [prev] | [next] | [standalone]

#1543654

On 16.12.2016 18:20, Peter Zijlstra wrote:
> On Fri, Dec 16, 2016 at 03:19:43PM +0100, Nicolai Hähnle wrote:
>>>> @@ -716,7 +775,20 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>>>> 		spin_unlock_mutex(&lock->wait_lock, flags);
>>>> 		schedule_preempt_disabled();
>>>>
>>>> -		if (!first && __mutex_waiter_is_first(lock, &waiter)) {
>>>> +		if (use_ww_ctx && ww_ctx) {
>>>> +			/*
>>>> +			 * Always re-check whether we're in first position. We
>>>> +			 * don't want to spin if another task with a lower
>>>> +			 * stamp has taken our position.
>>>> +			 *
>>>> +			 * We also may have to set the handoff flag again, if
>>>> +			 * our position at the head was temporarily taken away.
>>>> +			 */
>>>> +			first = __mutex_waiter_is_first(lock, &waiter);
>>>> +
>>>> +			if (first)
>>>> +				__mutex_set_flag(lock, MUTEX_FLAG_HANDOFF);
>>>> +		} else if (!first && __mutex_waiter_is_first(lock, &waiter)) {
>>>> 			first = true;
>>>> 			__mutex_set_flag(lock, MUTEX_FLAG_HANDOFF);
>>>> 		}
>>>
>>> So the point is that !ww_ctx entries are 'skipped' during the insertion
>>> and therefore, if one becomes first, it must stay first?
>>
>> Yes. Actually, it should be possible to replace all the cases of use_ww_ctx
>> || first with ww_ctx. Similarly, all cases of use_ww_ctx && ww_ctx could be
>> replaced by just ww_ctx.
>
>
> I'm not seeing how "use_ww_ctx || first" -> "ww_ctx" works.

My bad, missing the '|| first'.


> And while
> "use_ww_ctx && ww_ctx" -> "ww_ctx" is correct, it didn't work right on
> some older GCCs, they choked on value propagation for ww_ctx and kept
> emitting code even if we passed in NULL. Hence use_ww_ctx.

Okay, I'll stick with use_ww_ctx. Thanks for the explanation.

Nicolai


> Arnd is now looking to raise the minimum supported GCC version, so maybe
> we should look at that again if he gets anywhere.
>

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web