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
>
