On Thu, Jan 19, 2023 at 07:07:59PM -0800, Boqun Feng wrote: > On Thu, Jan 19, 2023 at 06:23:49PM -0800, Boqun Feng wrote: > > 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? > > > > Just tried the following on your latest GitHub branch, I commented all > but one deadlock case. Lockdep CAN detect it but DEPT CANNOT detect it. > Feel free to double check. > In case anyone else want to try, let me explain a little bit how to verify the behavior of the detectors. With the change, the only test that runs is dotest(queued_read_lock_hardirq_RE_Er, FAILURE, LOCKTYPE_RWLOCK); "FAILURE" indicates selftests think lockdep should report a deadlock, therefore for lockdep if all goes well, you will see: [...] hardirq read-lock/lock-read: ok | If you expect lockdep to print a full splat in the test (lockdep is silent by default), you can add "debug_locks_verbose=2" in the kernel command line, "2" mean RWLOCK testsuite. Regards, Boqun > Regards, > Boqun
