Re: [RFC tip/locking/lockdep v4 16/17] lockdep: Documention for recursive read lock detection reasoning

[Boqun Feng]

On Wed, Jan 24, 2018 at 05:05:49PM -0800, Randy Dunlap wrote:
> On 01/09/2018 06:38 AM, Boqun Feng wrote:
> > As now we support recursive read lock deadlock detection, add related
> > explanation in the Documentation/lockdep/lockdep-desgin.txt:
> > 
> > *	Definition of recursive read locks, non-recursive locks, strong
> > 	dependency path and notions of -(**)->.
> > 
> > *	Lockdep's assumption.
> > 
> > *	Informal proof of recursive read lock deadlock detection.
> > 
> > Signed-off-by: Boqun Feng <boqun.feng@xxxxxxxxx>
> > ---
> >  Documentation/locking/lockdep-design.txt | 170 +++++++++++++++++++++++++++++++
> >  1 file changed, 170 insertions(+)
> > 
> > diff --git a/Documentation/locking/lockdep-design.txt b/Documentation/locking/lockdep-design.txt
> > index 382bc25589c2..0e674305f96a 100644
> > --- a/Documentation/locking/lockdep-design.txt
> > +++ b/Documentation/locking/lockdep-design.txt
> > @@ -284,3 +284,173 @@ Run the command and save the output, then compare against the output from
> >  a later run of this command to identify the leakers.  This same output
> >  can also help you find situations where runtime lock initialization has
> >  been omitted.
> > +
> > +Recursive Read Deadlock Detection:
> > +----------------------------------
> > +Lockdep now is equipped with deadlock detection for recursive read locks.
> > +
> > +Recursive read locks, as their name indicates, are the locks able to be
> > +acquired recursively, unlike non-recursive read locks, recursive read locks
> 
>             recursively. Unlike
> 
> > +only get blocked by current write lock *holders* other than write lock
> > +*waiters*, for example:
> > +
> > +	TASK A:			TASK B:
> > +
> > +	read_lock(X);
> > +
> > +				write_lock(X);
> > +
> > +	read_lock(X);
> > +
> > +is not a deadlock for recursive read locks, as while the task B is waiting for
> > +the lock X, the second read_lock() doesn't need to wait because it's a recursive
> > +read lock.
> > +
> > +Note that a lock can be a write lock(exclusive lock), a non-recursive read lock
> > +(non-recursive shared lock) or a recursive read lock(recursive shared lock),
> > +depending on the API used to acquire it(more detailedly, the value of the
> 
>                                            more specifically,
> 
> > +'read' parameter for lock_acquire(...)). In other words, a single lock instance
> > +have three types of acquisition depending on the acquisition functions:
> 
>    has three types
> 
> > +exclusive, non-recursive read, and recursive read.
> > +
> > +That said, recursive read locks could introduce deadlocks too, considering the
> > +following:
> > +
> > +	TASK A:			TASK B:
> > +
> > +	read_lock(X);
> > +				read_lock(Y);
> > +	write_lock(Y);
> > +				write_lock(X);
> > +
> > +, neither task could get the write locks because the corresponding read locks
> > +are held by each other.
> > +
> > +Lockdep could detect recursive read lock related deadlocks. The dependencies(edges)
> > +in the lockdep graph are classified into four categories:
> > +
> > +1) -(NN)->: non-recursive to non-recursive dependency, non-recursive locks include
> > +            non-recursive read locks, write locks and exclusive locks(e.g. spinlock_t),
> 
>                                                                               spinlock_t).
> 
> > +	    they are treated equally in deadlock detection. "X -(NN)-> Y" means
> 
>             They
> 
> > +            X -> Y and both X and Y are non-recursive locks.
> > +
> > +2) -(RN)->: recursive to non-recursive dependency, recursive locks means recursive read
> > +	    locks. "X -(RN)-> Y" means X -> Y and X is recursive read lock and
> > +            Y is non-recursive lock.
> > +
> > +3) -(NR)->: non-recursive to recursive dependency, "X -(NR)-> Y" means X -> Y and X is
> > +            non-recursive lock and Y is recursive lock.
> > +
> > +4) -(RR)->: recursive to recursive dependency, "X -(RR)-> Y" means X -> Y and both X
> > +            and Y are recursive locks.
> > +
> > +Note that given two locks, they may have multiple dependencies between them, for example:
> > +
> > +	TASK A:
> > +
> > +	read_lock(X);
> > +	write_lock(Y);
> > +	...
> > +
> > +	TASK B:
> > +
> > +	write_lock(X);
> > +	write_lock(Y);
> > +
> > +, we have both X -(RN)-> Y and X -(NN)-> Y in the dependency graph.
> > +
> > +And obviously a non-recursive lock can block the corresponding recursive lock,
> > +and vice versa. Besides a non-recursive lock may block the other non-recursive
> > +lock of the same instance(e.g. a write lock may block a corresponding
> > +non-recursive read lock and vice versa).
> > +
> > +We use -(*N)-> for edges that is either -(RN)-> or -(NN)->, the similar for -(N*)->,
> > +-(*R)-> and -(R*)->
> > +
> > +A "path" is a series of conjunct dependency edges in the graph. And we define a
> > +"strong" path, which indicates the strong dependency throughout each dependency
> > +in the path, as the path that doesn't have two conjunct edges(dependencies) as
> > +-(*R)-> and -(R*)->. IOW, a "strong" path is a path from a lock walking to another
> > +through the lock dependencies, and if X -> Y -> Z in the path(where X, Y, Z are
> > +locks), if the walk from X to Y is through a -(NR)-> or -(RR)-> dependency, the
> > +walk from Y to Z must not be through a -(RN)-> or -(RR)-> dependency, otherwise
> > +it's not a strong path.
> > +
> > +We now prove that if a strong path forms a circle, then we have a potential deadlock.
> > +By "forms a circle", it means for a set of locks A0,A1...An, there is a path from
> > +A0 to An:
> > +
> > +	A0 -> A1 -> ... -> An
> > +
> > +and there is also a dependency An->A0. And as the circle is formed by a strong path,
> > +so there is no two conjunct dependency edges as -(*R)-> and -(R*)->.
> 
> I would say:
>       there are no two
> 

Agreed. I've applied other fixes in your comments. Thank you!

Regards,
Boqun

> > +
> > +
> > +To understand the actual proof, let's look into lockdep's assumption:
> > +
> > +For each lockdep dependency A -> B, there may exist a case where someone is
> > +trying to acquire B with A held, and the existence of such a case is
> > +independent to the existences of cases for other lockdep dependencies.
> > +
> > +For example if we have two functions func1 and func2:
> > +
> > +	void func1(...) {
> > +		lock(A);
> > +		lock(B);
> > +		unlock(A);
> > +		unlock(B);
> > +
> > +		lock(C);
> > +		lock(A);
> > +		unlock(A);
> > +		unlock(C);
> > +	}
> > +
> > +	void func2(...) {
> > +		lock(B);
> > +		lock(C);
> > +		unlock(C);
> > +		unlock(B);
> > +	}
> > +
> > +lockdep will generate dependencies: A->B, B->C and C->A, and assume that:
> > +
> > +	there may exist a case where someone is trying to acquire B with A held,
> > +	there may exist a case where someone is trying to acquire C with B held,
> > +	and there may exist a case where someone is trying to acquire A with C held,
> > +
> > +and those three cases exists *independently*, meaning they can happen at the
> 
>                          exist
> 
> > +same time(which requires func1() being called simultaneously by two CPUs or
> > +tasks, which may be impossible due to other constraints in the real life)
> 
>                                                                        life).
> 
> > +
> > +
> > +With this assumption, we can prove that if a strong dependency path forms a circle,
> > +then it indicate a deadlock as far as lockdep is concerned.
> 
>            indicates
> 
> > +
> > +For a strong dependency circle like:
> > +
> > +	A0 -> A1 -> ... -> An
> > +	^                  |
> > +	|                  |
> > +	+------------------+
> > +, lockdep assumes that
> ...
> 
> 
> -- 
> ~Randy

Attachment: signature.asc
Description: PGP signature