linux-kernel - Re: [RFC] locking/mutex: Fix starvation of sleeping waiters

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]

Message-ID: <1468969065.10247.10.camel@j-VirtualBox>
Date:	Tue, 19 Jul 2016 15:57:45 -0700
From:	Jason Low <jason.low2@....com>
To:	imre.deak@...el.com
Cc:	jason.low2@....com, Peter Zijlstra <peterz@...radead.org>,
	linux-kernel@...r.kernel.org, Ingo Molnar <mingo@...hat.com>,
	Chris Wilson <chris@...is-wilson.co.uk>,
	Daniel Vetter <daniel.vetter@...el.com>,
	Ville Syrj??l?? <ville.syrjala@...ux.intel.com>,
	Waiman Long <Waiman.Long@....com>,
	Davidlohr Bueso <dave@...olabs.net>
Subject: Re: [RFC] locking/mutex: Fix starvation of sleeping waiters

On Tue, 2016-07-19 at 19:53 +0300, Imre Deak wrote:
> On ma, 2016-07-18 at 10:47 -0700, Jason Low wrote:
> > On Mon, 2016-07-18 at 19:15 +0200, Peter Zijlstra wrote:

> > > I think we went over this before, that will also completely destroy
> > > performance under a number of workloads.
> > 
> > Yup, once a thread becomes a waiter, all other threads will need to
> > follow suit, so this change would effectively disable optimistic
> > spinning in some workloads.
> > 
> > A few months ago, we worked on patches that allow the waiter to
> > return
> > to optimistic spinning to help reduce starvation. Longman sent out a
> > version 3 patch set, and it sounded like we were fine with the
> > concept.
> 
> Thanks, with v4 he just sent I couldn't trigger the above problem.
> 
> However this only works if mutex spinning is enabled, if it's disabled
> I still hit the problem due to the other forms of lock stealing. So
> could we prevent these if mutex spinning is anyway disabled?

Good point, when optimistic spinning is disabled, waiters could still
get starved because other threads could steal the lock in the fastpath
and the waiter wouldn't be able to spin for the lock.

One option to address this is by enforcing a ceiling on the amount of
"time" a waiter needs to wait on the lock to avoid starvation when
optimistic spinning is disabled. This would be better than just
unconditionally disabling the fastpath whenever there is a waiter,
because that could reduce performance by quite a bit.

Instead, we can still allow threads to acquire the lock in the fastpath
if there are waiters, but yield the lock to a waiter if the waiter loops
too many times waiting for the lock in the slowpath in the
!CONFIG_MUTEX_OPTIMISTIC_SPINNING case.

I can send out an initial patch for this.

Jason