linux-kernel - Re: [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Tue, 9 Aug 2016 13:36:19 -0400
From:	Waiman Long <waiman.long@....com>
To:	Peter Zijlstra <peterz@...radead.org>
CC:	Ingo Molnar <mingo@...hat.com>, <linux-kernel@...r.kernel.org>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Ding Tianhong <dingtianhong@...wei.com>,
	Jason Low <jason.low2@....com>,
	Davidlohr Bueso <dave@...olabs.net>,
	"Paul E. McKenney" <paulmck@...ibm.com>,
	Thomas Gleixner <tglx@...utronix.de>,
	Will Deacon <Will.Deacon@....com>,
	Tim Chen <tim.c.chen@...ux.intel.com>,
	Imre Deak <imre.deak@...el.com>,
	Waiman Long <Waiman.Long@...com>
Subject: Re: [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic_spin()

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