linux-kernel - Re: [PATCH v8 07/19] locking/rwsem: Implement lock handoff to prevent lock starvation

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 for Android: free password hash cracker in your pocket

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

Message-ID: <20190604091220.GA29633@tardis>
Date:   Tue, 4 Jun 2019 17:12:20 +0800
From:   Boqun Feng <boqun.feng@...il.com>
To:     Yuyang Du <duyuyang@...il.com>
Cc:     Waiman Long <longman@...hat.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Ingo Molnar <mingo@...hat.com>,
        Will Deacon <will.deacon@....com>,
        Thomas Gleixner <tglx@...utronix.de>,
        Borislav Petkov <bp@...en8.de>,
        "H. Peter Anvin" <hpa@...or.com>,
        LKML <linux-kernel@...r.kernel.org>, x86@...nel.org,
        Davidlohr Bueso <dave@...olabs.net>,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        Tim Chen <tim.c.chen@...ux.intel.com>,
        huang ying <huang.ying.caritas@...il.com>
Subject: Re: [PATCH v8 07/19] locking/rwsem: Implement lock handoff to
 prevent lock starvation

On Tue, Jun 04, 2019 at 11:26:30AM +0800, Yuyang Du wrote:
> On Tue, 4 Jun 2019 at 11:03, Yuyang Du <duyuyang@...il.com> wrote:
> >
> > Hi Waiman,
> >
> > On Tue, 21 May 2019 at 05:01, Waiman Long <longman@...hat.com> wrote:
> > >
> > > Because of writer lock stealing, it is possible that a constant
> > > stream of incoming writers will cause a waiting writer or reader to
> > > wait indefinitely leading to lock starvation.
> > >
> > > This patch implements a lock handoff mechanism to disable lock stealing
> > > and force lock handoff to the first waiter or waiters (for readers)
> > > in the queue after at least a 4ms waiting period unless it is a RT
> > > writer task which doesn't need to wait. The waiting period is used to
> > > avoid discouraging lock stealing too much to affect performance.
> >
> > I was working on a patchset to solve read-write lock deadlock
> > detection problem (https://lkml.org/lkml/2019/5/16/93).
> >
> > One of the mistakes in that work is that I considered the following
> > case as deadlock:
> 
> Sorry everyone, but let me rephrase:
> 
> One of the mistakes in that work is that I considered the following
> case as no deadlock:
> 
> >
> >   T1            T2
> >   --            --
> >
> >   down_read1    down_write2
> >
> >   down_write2   down_read1
> >

Not sure I understand the whole context here, but isn't adding a third
independent task makes this a deadlock?

	 T1            T2		T3
	 --            --		--

	 down_read1    down_write2
	 				down_write1
	 down_write2   down_read1

from the perspective of lockdep, we cannot be sure whether there will
a T3 or not.

In case that I mis-understood you, maybe your point is about in the
above case whether "down_read1" on T2 can *gauranteedly* steal (in the
sense of breaking the fairness) the read lock after Waiman modification?
If so, I will wait for Waiman's response ;-)

Regards,
Boqun

> > So I was trying to understand what really went wrong and find the
> > problem is that if I understand correctly the current rwsem design
> > isn't showing real fairness but priority in favor of write locks, and
> > thus one of the bad effects is that read locks can be starved if write
> > locks keep coming.
> >
> > Luckily, I noticed you are revamping rwsem and seem to have thought
> > about it already. I am not crystal sure what is your work's
> > ramification on the above case, so hope that you can shed some light
> > and perhaps share your thoughts on this.
> >
> > Thanks,
> > Yuyang

Download attachment "signature.asc" of type "application/pgp-signature" (489 bytes)