linux-kernel - Re: [PATCH 5/6] kernel/locking: Prevent slowpath writers getting held up by fastpath

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: <20171005144256.GF11088@arm.com>
Date:   Thu, 5 Oct 2017 15:42:57 +0100
From:   Will Deacon <will.deacon@....com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     linux-kernel@...r.kernel.org, linux-arm-kernel@...ts.infradead.org,
        Jeremy.Linton@....com, mingo@...hat.com, longman@...hat.com,
        boqun.feng@...il.com, paulmck@...ux.vnet.ibm.com
Subject: Re: [PATCH 5/6] kernel/locking: Prevent slowpath writers getting
 held up by fastpath

HI Peter,

Thanks for having a look.

On Thu, Oct 05, 2017 at 03:56:18PM +0200, Peter Zijlstra wrote:
> On Thu, Oct 05, 2017 at 01:54:56PM +0100, Will Deacon wrote:
> > When a prospective writer takes the qrwlock locking slowpath due to the
> > lock being held, it attempts to cmpxchg the wmode field from 0 to
> > _QW_WAITING so that concurrent lockers also take the slowpath and queue
> > on the spinlock accordingly, allowing the lockers to drain.
> > 
> > Unfortunately, this isn't fair, because a fastpath writer that comes in
> > after the lock is made available but before the _QW_WAITING flag is set
> > can effectively jump the queue. If there is a steady stream of prospective
> > writers, then the waiter will be held off indefinitely.
> > 
> > This patch restores fairness by separating _QW_WAITING and _QW_LOCKED
> > into two bits in the wmode byte and having the waiter set _QW_WAITING
> > unconditionally. This then forces the slow-path for concurrent lockers,
> > but requires that a writer unlock operation performs an
> > atomic_sub_release instead of a store_release so that the waiting status
> > is preserved.
> 
> > diff --git a/include/asm-generic/qrwlock.h b/include/asm-generic/qrwlock.h
> > index 02c0a768e6b0..8b7edef500e5 100644
> > --- a/include/asm-generic/qrwlock.h
> > +++ b/include/asm-generic/qrwlock.h
> > @@ -41,7 +41,7 @@
> >   *       +----+----+----+----+
> >   */
> >  #define	_QW_WAITING	1		/* A writer is waiting	   */
> > -#define	_QW_LOCKED	0xff		/* A writer holds the lock */
> > +#define	_QW_LOCKED	2		/* A writer holds the lock */
> >  #define	_QW_WMASK	0xff		/* Writer mask		   */
> >  #define	_QR_SHIFT	8		/* Reader count shift	   */
> >  #define _QR_BIAS	(1U << _QR_SHIFT)
> > @@ -134,7 +134,7 @@ static inline void queued_read_unlock(struct qrwlock *lock)
> >   */
> >  static inline void queued_write_unlock(struct qrwlock *lock)
> >  {
> > -	smp_store_release(&lock->wmode, 0);
> > +	(void)atomic_sub_return_release(_QW_LOCKED, &lock->cnts);
> >  }
> 
> That is a fairly painful hit on x86. Changes a regular store into an
> "LOCK XADD" +20 cycles right there.

Yeah, I mentioned that in the cover letter which is also why it's at the end
of the series ;) However, it's worth noting that this is the same as the
reader unlock path and, as it stands, there's a real risk of writer
starvation with the current code which isn't great for a queued lock.

> Can't we steal one of the reader bits for waiting?

I considered this at LPC and somehow convinced myself it didn't work, but
actually all it's really doing is making the _QW_LOCKED bit a byte, so it
should work fine.

I'll work that into v2.

Will