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

[Boqun Feng <boqun.feng@gmail.com>]

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.

Regards,
Boqun

------------------------------------------->8
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index cd89138d62ba..f38e4109e013 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -2375,6 +2375,7 @@ static void ww_tests(void)
  */
 static void queued_read_lock_hardirq_RE_Er(void)
 {
+	// T0
 	HARDIRQ_ENTER();
 	read_lock(&rwlock_A);
 	LOCK(B);
@@ -2382,12 +2383,17 @@ static void queued_read_lock_hardirq_RE_Er(void)
 	read_unlock(&rwlock_A);
 	HARDIRQ_EXIT();
 
+	// T1
 	HARDIRQ_DISABLE();
 	LOCK(B);
 	read_lock(&rwlock_A);
 	read_unlock(&rwlock_A);
 	UNLOCK(B);
 	HARDIRQ_ENABLE();
+
+	// T2
+	write_lock_irq(&rwlock_A);
+	write_unlock_irq(&rwlock_A);
 }
 
 /*
@@ -2455,6 +2461,7 @@ static void queued_read_lock_tests(void)
 	dotest(queued_read_lock_hardirq_RE_Er, FAILURE, LOCKTYPE_RWLOCK);
 	pr_cont("\n");
 
+#if 0
 	print_testname("hardirq lock-read/read-lock");
 	dotest(queued_read_lock_hardirq_ER_rE, SUCCESS, LOCKTYPE_RWLOCK);
 	pr_cont("\n");
@@ -2462,6 +2469,7 @@ static void queued_read_lock_tests(void)
 	print_testname("hardirq inversion");
 	dotest(queued_read_lock_hardirq_inversion, FAILURE, LOCKTYPE_RWLOCK);
 	pr_cont("\n");
+#endif
 }
 
 static void fs_reclaim_correct_nesting(void)
@@ -2885,6 +2893,7 @@ void locking_selftest(void)
 	init_shared_classes();
 	lockdep_set_selftest_task(current);
 
+#if 0
 	DO_TESTCASE_6R("A-A deadlock", AA);
 	DO_TESTCASE_6R("A-B-B-A deadlock", ABBA);
 	DO_TESTCASE_6R("A-B-B-C-C-A deadlock", ABBCCA);
@@ -2967,6 +2976,7 @@ void locking_selftest(void)
 	DO_TESTCASE_6x2x2RW("irq read-recursion #3", irq_read_recursion3);
 
 	ww_tests();
+#endif
 
 	force_read_lock_recursive = 0;
 	/*
@@ -2975,6 +2985,7 @@ void locking_selftest(void)
 	if (IS_ENABLED(CONFIG_QUEUED_RWLOCKS))
 		queued_read_lock_tests();
 
+#if 0
 	fs_reclaim_tests();
 
 	/* Wait context test cases that are specific for RAW_LOCK_NESTING */
@@ -2987,6 +2998,7 @@ void locking_selftest(void)
 	dotest(hardirq_deadlock_softirq_not_deadlock, FAILURE, LOCKTYPE_SPECIAL);
 	pr_cont("\n");
 
+#endif
 	if (unexpected_testcase_failures) {
 		printk("-----------------------------------------------------------------\n");
 		debug_locks = 0;