Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Feedback-ID: iad51458e:Fastmail
Date:   Sat, 14 Jan 2023 16:18:57 -0800
From:   Boqun Feng <boqun.feng@gmail.com>
To:     Hillf Danton <hdanton@sina.com>
Cc:     linux-kernel@vger.kernel.org, linux-mm@kvack.org,
        Peter Zijlstra <peterz@infradead.org>,
        "Paul E. McKenney" <paulmck@kernel.org>,
        Paolo Bonzini <pbonzini@redhat.com>,
        Joel Fernandes <joel@joelfernandes.org>
Subject: Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency
 graph checks
Message-ID: <Y8NGcaMmFgxBmhXN@boqun-archlinux>
References: <20230113065955.815667-1-boqun.feng@gmail.com>
 <20230113130330.1027-1-hdanton@sina.com>
 <20230113235809.1085-1-hdanton@sina.com>
 <20230114071832.1162-1-hdanton@sina.com>
 <20230114102659.1219-1-hdanton@sina.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20230114102659.1219-1-hdanton@sina.com>
Precedence: bulk

On Sat, Jan 14, 2023 at 06:26:59PM +0800, Hillf Danton wrote:
> On Fri, 13 Jan 2023 23:32:01 -0800 Boqun Feng <boqun.feng@gmail.com>
> > On Sat, Jan 14, 2023 at 03:18:32PM +0800, Hillf Danton wrote:
> > >
> > >  	task X			task Y
> > >  	---			---
> > >  	mutex_lock(A);
> > >  				srcu_read_lock(B);
> > > 				srcu_lock_acquire(&B->dep_map);
> > > 				a) lock_map_acquire_read(&B->dep_map);
> > >  	synchronze_srcu(B);
> > > 	__synchronize_srcu(B);
> > > 	srcu_lock_sync(&B->dep_map);
> > > 	lock_map_sync(&B->dep_map);
> > > 	lock_sync(&B->dep_map);
> > > 	__lock_acquire(&B->dep_map);
> > 
> > At this time, lockdep add dependency A -> B in the dependency graph.
> > 
> > > 				b) lock_map_acquire_read(&B->dep_map);
> > > 	__lock_release(&B->dep_map);
> > > 				c) lock_map_acquire_read(&B->dep_map);
> > >  				mutex_lock(A);
> > 
> > and here, lockdep will try to add dependency B -> A into the dependency
> > graph, and find that A -> B -> A will form a circle (with strong
> > dependency), therefore lockdep knows it's a deadlock. 
> 
> Is the strong dependency applying to mode c)?
> If yes then deadlock should be also detected in the following locking
> pattern that has no deadlock.
> 
> 	cpu0			cpu1
> 	---			---
> 	mutex_lock A
> 	mutex_lock B
> 	mutex_unlock B
> 				mutex_lock B
> 				mutex_lock A

Well, of course, this is how lockdep works. Lockdep detects the
*potential* deadlocks rather than detects the deadlocks when they
really happen. Otherwise lockdep is useless.

The execution in your example shows the potential deadlocks, i.e. one
task acquires A and then acquires B, the other task acquires B and then
acquires A. Potential deadlocks mean given a correct timing, a deadlock
may happen.

Regards,
Boqun

> > 
> > >  
> > > No deadlock could be detected if taskY takes mutexA after taskX releases B,
> > 
> > The timing that taskX releases B doesn't master, since lockdep uses
> > graph to detect deadlocks rather than after-fact detection.
> > 
> > > and how taskY acquires B does not matter as per the a), b) and c) modes in
> > > the above chart, again because releasing lock can break deadlock in general.
> > 
> > I have test cases showing the above deadlock can be detected, so if you
> > think there is a deadlock that may dodge from my change, feel free to
> > add a test case in lib/locking-selftest.c ;-)
> > 
> > Regards,
> > Boqun