Re: [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic_spin()

[Waiman Long]

On 08/08/2016 01:26 PM, Peter Zijlstra wrote:
> On Mon, Jul 18, 2016 at 04:39:24PM -0400, Waiman Long wrote:
> > @@ -302,22 +306,42 @@ static inline bool mutex_try_to_acquire(struct mutex *lock)
> >    *
> >    * Returns true when the lock was taken, otherwise false, indicating
> >    * that we need to jump to the slowpath and sleep.
> > + *
> > + * The waiter flag is set to true if the spinner is a waiter in the wait
> > + * queue. As the waiter has slept for a while, it should have priority to
> > + * get the lock over the regular spinners. So going to wait at the end of
> > + * the OSQ isn't fair to the waiter.
> If the OSQ lock were a full FIFO it would in fact be fair, but its not
> and things can drop out the middle and go (back) to sleep.
>
> This has nothing to do with the end or not.

Yes, the OSQ is not strictly FIFO, but the wait queue is. There is a 
much higher chance of lock starvation if the waiter is put at the end of 
the OSQ instead of in front of it. I will change the wordings to 
illustrate this fact.

> > Instead, it will spin on the lock
> > + * directly and concurrently with the spinner at the head of the OSQ, if
> > + * present.
> Note that this isn't starvation proof in any way.

Patch 1 by itself isn't starvation-proof. Coupled with patch 3 that put 
the waiter-spinner in front of OSQ, we will have a much higher chance to 
avoid lock starvation. We can also completely block optimistic spinning 
if the waiter can't get the lock after a certain number of wakeup-sleep 
cycles, if the goal is to make it starvation proof.

> >      There may be a bit more cacheline contention in this case.
> This is relevant how ?

It is just that there will be one more CPU contending on the lock cacheline.

> > + * The waiter also needs to set the lock to -1 instead of 0 on lock
> > + * acquisition.
> This is unrelated to the previous bits and thus should not be in the
> same paragraph. Also, a 'why' would be more helpful.

Will explain a bit more in the comments.

Regards,
Longman