linux-kernel - Re: [PATCH RFC v7 00/23] DEPT(Dependency Tracker)

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: <1674179505-26987-1-git-send-email-byungchul.park@lge.com>
Date:   Fri, 20 Jan 2023 10:51:45 +0900
From:   Byungchul Park <byungchul.park@....com>
To:     boqun.feng@...il.com
Cc:     linux-kernel@...r.kernel.org, torvalds@...ux-foundation.org,
        damien.lemoal@...nsource.wdc.com, linux-ide@...r.kernel.org,
        adilger.kernel@...ger.ca, linux-ext4@...r.kernel.org,
        mingo@...hat.com, peterz@...radead.org, will@...nel.org,
        tglx@...utronix.de, rostedt@...dmis.org, joel@...lfernandes.org,
        sashal@...nel.org, daniel.vetter@...ll.ch, duyuyang@...il.com,
        johannes.berg@...el.com, tj@...nel.org, tytso@....edu,
        willy@...radead.org, david@...morbit.com, amir73il@...il.com,
        gregkh@...uxfoundation.org, kernel-team@....com,
        linux-mm@...ck.org, akpm@...ux-foundation.org, mhocko@...nel.org,
        minchan@...nel.org, hannes@...xchg.org, vdavydov.dev@...il.com,
        sj@...nel.org, jglisse@...hat.com, dennis@...nel.org, cl@...ux.com,
        penberg@...nel.org, rientjes@...gle.com, vbabka@...e.cz,
        ngupta@...are.org, linux-block@...r.kernel.org,
        paolo.valente@...aro.org, josef@...icpanda.com,
        linux-fsdevel@...r.kernel.org, viro@...iv.linux.org.uk,
        jack@...e.cz, jlayton@...nel.org, dan.j.williams@...el.com,
        hch@...radead.org, djwong@...nel.org,
        dri-devel@...ts.freedesktop.org, rodrigosiqueiramelo@...il.com,
        melissa.srw@...il.com, hamohammed.sa@...il.com,
        42.hyeyoo@...il.com, chris.p.wilson@...el.com,
        gwan-gyeong.mun@...el.com, max.byungchul.park@...il.com,
        longman@...hat.com
Subject: Re: [PATCH RFC v7 00/23] DEPT(Dependency Tracker)

Boqun wrote:
> On Thu, Jan 19, 2023 at 01:33:58PM +0000, Matthew Wilcox wrote:
> > On Thu, Jan 19, 2023 at 03:23:08PM +0900, Byungchul Park wrote:
> > > Boqun wrote:
> > > > *Looks like the DEPT dependency graph doesn't handle the
> > > > fair/unfair readers as lockdep current does. Which bring the
> > > > next question.
> > > 
> > > No. DEPT works better for unfair read. It works based on wait/event. So
> > > read_lock() is considered a potential wait waiting on write_unlock()
> > > while write_lock() is considered a potential wait waiting on either
> > > write_unlock() or read_unlock(). DEPT is working perfect for it.
> > > 
> > > For fair read (maybe you meant queued read lock), I think the case
> > > should be handled in the same way as normal lock. I might get it wrong.
> > > Please let me know if I miss something.
> > 
> > From the lockdep/DEPT point of view, the question is whether:
> > 
> >	read_lock(A)
> >	read_lock(A)
> > 
> > can deadlock if a writer comes in between the two acquisitions and
> > sleeps waiting on A to be released.  A fair lock will block new
> > readers when a writer is waiting, while an unfair lock will allow
> > new readers even while a writer is waiting.
> > 
> 
> To be more accurate, a fair reader will wait if there is a writer
> waiting for other reader (fair or not) to unlock, and an unfair reader
> won't.

What a kind guys, both of you! Thanks.

I asked to check if there are other subtle things than this. Fortunately,
I already understand what you guys shared.

> In kernel there are read/write locks that can have both fair and unfair
> readers (e.g. queued rwlock). Regarding deadlocks,
> 
> 	T0		T1		T2
> 	--		--		--
> 	fair_read_lock(A);
> 			write_lock(B);
> 					write_lock(A);
> 	write_lock(B);
> 			unfair_read_lock(A);

With the DEPT's point of view (let me re-write the scenario):

	T0		T1		T2
	--		--		--
	fair_read_lock(A);
			write_lock(B);
					write_lock(A);
	write_lock(B);
			unfair_read_lock(A);
	write_unlock(B);
	read_unlock(A);
			read_unlock(A);
			write_unlock(B);
					write_unlock(A);

T0: read_unlock(A) cannot happen if write_lock(B) is stuck by a B owner
    not doing either write_unlock(B) or read_unlock(B). In other words:

      1. read_unlock(A) happening depends on write_unlock(B) happening.
      2. read_unlock(A) happening depends on read_unlock(B) happening.

T1: write_unlock(B) cannot happen if unfair_read_lock(A) is stuck by a A
    owner not doing write_unlock(A). In other words:

      3. write_unlock(B) happening depends on write_unlock(A) happening.

1, 2 and 3 give the following dependencies:

    1. read_unlock(A) -> write_unlock(B)
    2. read_unlock(A) -> read_unlock(B)
    3. write_unlock(B) -> write_unlock(A)

There's no circular dependency so it's safe. DEPT doesn't report this.

> the above is not a deadlock, since T1's unfair reader can "steal" the
> lock. However the following is a deadlock:
> 
> 	T0		T1		T2
> 	--		--		--
> 	unfair_read_lock(A);
> 			write_lock(B);
> 					write_lock(A);
> 	write_lock(B);
> 			fair_read_lock(A);
> 
> , since T'1 fair reader will wait.

With the DEPT's point of view (let me re-write the scenario):

	T0		T1		T2
	--		--		--
	unfair_read_lock(A);
			write_lock(B);
					write_lock(A);
	write_lock(B);
			fair_read_lock(A);
	write_unlock(B);
	read_unlock(A);
			read_unlock(A);
			write_unlock(B);
					write_unlock(A);

T0: read_unlock(A) cannot happen if write_lock(B) is stuck by a B owner
    not doing either write_unlock(B) or read_unlock(B). In other words:

      1. read_unlock(A) happening depends on write_unlock(B) happening.
      2. read_unlock(A) happening depends on read_unlock(B) happening.

T1: write_unlock(B) cannot happen if fair_read_lock(A) is stuck by a A
    owner not doing either write_unlock(A) or read_unlock(A). In other
    words:

      3. write_unlock(B) happening depends on write_unlock(A) happening.
      4. write_unlock(B) happening depends on read_unlock(A) happening.

1, 2, 3 and 4 give the following dependencies:

    1. read_unlock(A) -> write_unlock(B)
    2. read_unlock(A) -> read_unlock(B)
    3. write_unlock(B) -> write_unlock(A)
    4. write_unlock(B) -> read_unlock(A)

With 1 and 4, there's a circular dependency so DEPT definitely report
this as a problem.

REMIND: DEPT focuses on waits and events.

> FWIW, lockdep is able to catch this (figuring out which is deadlock and
> which is not) since two years ago, plus other trivial deadlock detection
> for read/write locks. Needless to say, if lib/lock-selftests.c was given
> a try, one could find it out on one's own.
> 
> Regards,
> Boqun
>