On Fri, Jan 20, 2023 at 10:51:45AM +0900, Byungchul Park wrote: > 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. Do you have the test cases showing DEPT can detect this? Regards, Boqun > > > 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 > >
