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

Groups > linux.kernel > #1362874 > unrolled thread

[PATCH v3 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue

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

  [PATCH v3 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue Waiman Long <Waiman.Long@hpe.com> - 2016-03-22 18:50 +0100
    Re: [PATCH v3 2/3] locking/mutex: Enable optimistic spinning of  woken task in wait queue Peter Zijlstra <peterz@infradead.org> - 2016-03-29 17:50 +0200
      Re: [PATCH v3 2/3] locking/mutex: Enable optimistic spinning of  woken task in wait queue Peter Zijlstra <peterz@infradead.org> - 2016-03-29 18:50 +0200
        Re: [PATCH v3 2/3] locking/mutex: Enable optimistic spinning of woken  task in wait queue Waiman Long <waiman.long@hpe.com> - 2016-03-31 22:50 +0200
      Re: [PATCH v3 2/3] locking/mutex: Enable optimistic spinning of woken  task in wait queue Waiman Long <waiman.long@hpe.com> - 2016-03-31 23:00 +0200

#1362874 — [PATCH v3 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue

Ding Tianhong reported a live-lock situation where a constant stream
of incoming optimistic spinners blocked a task in the wait list from
getting the mutex.

This patch attempts to fix this live-lock condition by enabling the
woken task in the wait queue to enter into an optimistic spinning
loop itself in parallel with the regular spinners in the OSQ. This
should prevent the live-lock condition from happening.

Running the AIM7 benchmarks on a 4-socket E7-4820 v3 system (with ext4
filesystem), the additional spinning of the waiter-spinning improved
performance for the following workloads at high user count:

  Workload	% Improvement
  --------	-------------
  alltests	    3.9%
  disk		    3.4%
  fserver	    2.0%
  long		    3.8%
  new_fserver	   10.5%

The other workloads were about the same as before.

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 kernel/locking/mutex.c |   16 +++++++++++++++-
 1 files changed, 15 insertions(+), 1 deletions(-)

diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index 5dd6171..5c0acee 100644
--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -538,6 +538,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	struct task_struct *task = current;
 	struct mutex_waiter waiter;
 	unsigned long flags;
+	bool  acquired = false;	/* True if the lock is acquired */
 	int ret;
 
 	preempt_disable();
@@ -568,7 +569,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 
 	lock_contended(&lock->dep_map, ip);
 
-	for (;;) {
+	while (!acquired) {
 		/*
 		 * Lets try to take the lock again - this is needed even if
 		 * we get here for the first time (shortly after failing to
@@ -603,6 +604,15 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		/* didn't get the lock, go to sleep: */
 		spin_unlock_mutex(&lock->wait_lock, flags);
 		schedule_preempt_disabled();
+
+		/*
+		 * Optimistically spinning on the mutex without the wait lock
+		 * The state has to be set to running to avoid another waker
+		 * spinning on the on_cpu flag while the woken waiter is
+		 * spinning on the mutex.
+		 */
+		acquired = mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx,
+						 true);
 		spin_lock_mutex(&lock->wait_lock, flags);
 	}
 	__set_task_state(task, TASK_RUNNING);
@@ -613,6 +623,9 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		atomic_set(&lock->count, 0);
 	debug_mutex_free_waiter(&waiter);
 
+	if (acquired)
+		goto unlock;
+
 skip_wait:
 	/* got the lock - cleanup and rejoice! */
 	lock_acquired(&lock->dep_map, ip);
@@ -623,6 +636,7 @@ skip_wait:
 		ww_mutex_set_context_slowpath(ww, ww_ctx);
 	}
 
+unlock:
 	spin_unlock_mutex(&lock->wait_lock, flags);
 	preempt_enable();
 	return 0;
-- 
1.7.1

[toc] | [next] | [standalone]

#1366400 — Re: [PATCH v3 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue

On Tue, Mar 22, 2016 at 01:46:43PM -0400, Waiman Long wrote:
> Ding Tianhong reported a live-lock situation where a constant stream
> of incoming optimistic spinners blocked a task in the wait list from
> getting the mutex.
> 
> This patch attempts to fix this live-lock condition by enabling the
> woken task in the wait queue to enter into an optimistic spinning
> loop itself in parallel with the regular spinners in the OSQ. This
> should prevent the live-lock condition from happening.

I would very much like a few words on how fairness is preserved.

Because while the waiter remains on the wait_list while it spins, and
therefore unlock()s will only wake it, and we'll only contend with the
one waiter, the fact that we have two spinners is not fair or starvation
proof at all.

By adding the waiter to the OSQ we get only a single spinner and force
'fairness' by queuing.

I say 'fairness' because the OSQ (need_resched) cancellation can still
take the waiter out again and let even more new spinners in.

> diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
> index 5dd6171..5c0acee 100644
> --- a/kernel/locking/mutex.c
> +++ b/kernel/locking/mutex.c
> @@ -538,6 +538,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>  	struct task_struct *task = current;
>  	struct mutex_waiter waiter;
>  	unsigned long flags;
> +	bool  acquired = false;	/* True if the lock is acquired */

Superfluous space there.

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

#1366467 — Re: [PATCH v3 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue

On Tue, Mar 29, 2016 at 05:39:35PM +0200, Peter Zijlstra wrote:
> On Tue, Mar 22, 2016 at 01:46:43PM -0400, Waiman Long wrote:
> > Ding Tianhong reported a live-lock situation where a constant stream
> > of incoming optimistic spinners blocked a task in the wait list from
> > getting the mutex.
> > 
> > This patch attempts to fix this live-lock condition by enabling the
> > woken task in the wait queue to enter into an optimistic spinning
> > loop itself in parallel with the regular spinners in the OSQ. This
> > should prevent the live-lock condition from happening.
> 
> I would very much like a few words on how fairness is preserved.
> 
> Because while the waiter remains on the wait_list while it spins, and
> therefore unlock()s will only wake it, and we'll only contend with the
> one waiter, the fact that we have two spinners is not fair or starvation
> proof at all.

Alternatively, we can say this is good enough until proven deficient,
but then we should still very much document this.

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

#1368689 — Re: [PATCH v3 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue

On 03/29/2016 12:42 PM, Peter Zijlstra wrote:
> On Tue, Mar 29, 2016 at 05:39:35PM +0200, Peter Zijlstra wrote:
>> On Tue, Mar 22, 2016 at 01:46:43PM -0400, Waiman Long wrote:
>>> Ding Tianhong reported a live-lock situation where a constant stream
>>> of incoming optimistic spinners blocked a task in the wait list from
>>> getting the mutex.
>>>
>>> This patch attempts to fix this live-lock condition by enabling the
>>> woken task in the wait queue to enter into an optimistic spinning
>>> loop itself in parallel with the regular spinners in the OSQ. This
>>> should prevent the live-lock condition from happening.
>> I would very much like a few words on how fairness is preserved.
>>
>> Because while the waiter remains on the wait_list while it spins, and
>> therefore unlock()s will only wake it, and we'll only contend with the
>> one waiter, the fact that we have two spinners is not fair or starvation
>> proof at all.
> Alternatively, we can say this is good enough until proven deficient,
> but then we should still very much document this.

Yes, we can certainly do that.

Cheers,
Longman

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

#1368745 — Re: [PATCH v3 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue

On 03/29/2016 11:39 AM, Peter Zijlstra wrote:
> On Tue, Mar 22, 2016 at 01:46:43PM -0400, Waiman Long wrote:
>> Ding Tianhong reported a live-lock situation where a constant stream
>> of incoming optimistic spinners blocked a task in the wait list from
>> getting the mutex.
>>
>> This patch attempts to fix this live-lock condition by enabling the
>> woken task in the wait queue to enter into an optimistic spinning
>> loop itself in parallel with the regular spinners in the OSQ. This
>> should prevent the live-lock condition from happening.
> I would very much like a few words on how fairness is preserved.
>
> Because while the waiter remains on the wait_list while it spins, and
> therefore unlock()s will only wake it, and we'll only contend with the
> one waiter, the fact that we have two spinners is not fair or starvation
> proof at all.
>
> By adding the waiter to the OSQ we get only a single spinner and force
> 'fairness' by queuing.
>
> I say 'fairness' because the OSQ (need_resched) cancellation can still
> take the waiter out again and let even more new spinners in.
>

In my v1 patch, I added a flag in the mutex structure to signal that the 
waiter is spinning and the OSQ spinner should yield to address this 
fairness issue. I took it out in my later patchs as you said you want to 
make the patch simpler.

Yes, I do agree that it is not guaranteed that the waiter spinner will 
have a decent chance to get the lock, but I think it is still better 
than queuing at the end of the OSQ as the time slice may expire before 
the waiter bubbles up to the beginning of the queue. This can be 
especially problematic if the waiter has lower priority which means 
shorter time slice.

What do you think about the idea of adding a flag as in my v1 patch? For 
64-bit systems, there is a 4-byte hole below osq and so it won't 
increase the structure size. There will be a 4-byte increase in size for 
32-bit systems, though.

Alternatively, I can certainly add a bit more comments to explain the 
situation and the choice that we made.

>> diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
>> index 5dd6171..5c0acee 100644
>> --- a/kernel/locking/mutex.c
>> +++ b/kernel/locking/mutex.c
>> @@ -538,6 +538,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>>   	struct task_struct *task = current;
>>   	struct mutex_waiter waiter;
>>   	unsigned long flags;
>> +	bool  acquired = false;	/* True if the lock is acquired */
> Superfluous space there.

OK, will remove that.

Cheers,
Longman

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web