Re: [RFC tip/locking/lockdep v6 01/20] lockdep/Documention: Recursive read lock detection reasoning

[Boqun Feng]

(Copy more people)

On Wed, Apr 11, 2018 at 09:50:51PM +0800, Boqun Feng wrote:
> This patch add the documentation piece for the reasoning of deadlock
> detection related to recursive read lock. The following sections are
> added:
> 
> * Explain what is a recursive read lock, and what deadlock cases
>   they could introduce.
> 
> * Introduce the notations for different types of dependencies, and
>   the definition of strong paths.
> 
> * Proof for a closed strong path is both sufficient and necessary
>   for deadlock detections with recursive read locks involved. The
>   proof could also explain why we call the path "strong"
> 
> Signed-off-by: Boqun Feng 
> ---
>  Documentation/locking/lockdep-design.txt | 178 
> +++
>  1 file changed, 178 insertions(+)
> 
> diff --git a/Documentation/locking/lockdep-design.txt 
> b/Documentation/locking/lockdep-design.txt
> index 9de1c158d44c..6bb9e90e2c4f 100644
> --- a/Documentation/locking/lockdep-design.txt
> +++ b/Documentation/locking/lockdep-design.txt
> @@ -284,3 +284,181 @@ 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 locks:
> +-
> +
> +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
> +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. However if the read_lock() is non-recursive read lock, then the 
> above
> +case is a deadlock, because even if the write_lock() in TASK B can not get 
> the
> +lock, but it can block the second read_lock() in TASK A.
> +
> +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 lock operations used to acquire it (more 
> specifically,
> +the value of the 'read' parameter for lock_acquire()). In other words, a 
> single
> +lock instance has three types of acquisition depending on the acquisition
> +functions: exclusive, non-recursive read, and recursive read.
> +
> +To be concise, we call that write locks and non-recursive read locks as
> +"non-recursive" locks and recursive read locks as "recursive" locks.
> +
> +Recursive locks don't block each other, while non-recursive locks do (this is
> +even true for two non-recursive read locks). A non-recursive lock can block 
> the
> +corresponding recursive lock, and vice versa.
> +
> +A deadlock case with recursive locks involved is as follow:
> +
> + TASK A: TASK B:
> +
> + read_lock(X);
> + read_lock(Y);
> + write_lock(Y);
> + write_lock(X);
> +
> +Task A is waiting for task B to read_unlock() Y and task B is waiting for 
> task
> +A to read_unlock() X.
> +
> +Dependency types and strong dependency paths:
> +-
> +In order to detect deadlocks as above, lockdep needs to track different 
> dependencies.
> +There are 4 categories for dependency edges in the lockdep graph:
> +
> +1) -(NN)->: non-recursive to non-recursive dependency. "X -(NN)-> Y" means
> +X -> Y and both X and Y are non-recursive locks.
> +
> +2) -(RN)->: recursive to non-recursive dependency. "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.
> +
> +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 

Re: [RFC tip/locking/lockdep v6 01/20] lockdep/Documention: Recursive read lock detection reasoning

[Boqun Feng]

On Sat, Apr 14, 2018 at 05:38:54PM -0700, Randy Dunlap wrote:
> Hi,
> 

Hello Randy,

> Just a few typos etc. below...
> 

Thanks! I fixed those typos according to your comments.

> On 04/11/2018 06:50 AM, Boqun Feng wrote:
> > Signed-off-by: Boqun Feng 
> > ---
> >  Documentation/locking/lockdep-design.txt | 178 
> > +++
> >  1 file changed, 178 insertions(+)
> > 
> > diff --git a/Documentation/locking/lockdep-design.txt 
> > b/Documentation/locking/lockdep-design.txt
> > index 9de1c158d44c..6bb9e90e2c4f 100644
> > --- a/Documentation/locking/lockdep-design.txt
> > +++ b/Documentation/locking/lockdep-design.txt
> > @@ -284,3 +284,181 @@ 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 locks:
> > +-
> > +
> > +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
> > +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. However if the read_lock() is non-recursive read lock, then the 
> > above
> > +case is a deadlock, because even if the write_lock() in TASK B can not get 
> > the
> > +lock, but it can block the second read_lock() in TASK A.
> > +
> > +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 lock operations used to acquire it (more 
> > specifically,
> > +the value of the 'read' parameter for lock_acquire()). In other words, a 
> > single
> > +lock instance has three types of acquisition depending on the acquisition
> > +functions: exclusive, non-recursive read, and recursive read.
> > +
> > +To be concise, we call that write locks and non-recursive read locks as
> > +"non-recursive" locks and recursive read locks as "recursive" locks.
> > +
> > +Recursive locks don't block each other, while non-recursive locks do (this 
> > is
> > +even true for two non-recursive read locks). A non-recursive lock can 
> > block the
> > +corresponding recursive lock, and vice versa.
> > +
> > +A deadlock case with recursive locks involved is as follow:
> > +
> > +   TASK A: TASK B:
> > +
> > +   read_lock(X);
> > +   read_lock(Y);
> > +   write_lock(Y);
> > +   write_lock(X);
> > +
> > +Task A is waiting for task B to read_unlock() Y and task B is waiting for 
> > task
> > +A to read_unlock() X.
> > +
> > +Dependency types and strong dependency paths:
> > +-
> > +In order to detect deadlocks as above, lockdep needs to track different 
> > dependencies.
> > +There are 4 categories for dependency edges in the lockdep graph:
> > +
> > +1) -(NN)->: non-recursive to non-recursive dependency. "X -(NN)-> Y" means
> > +X -> Y and both X and Y are non-recursive locks.
> > +
> > +2) -(RN)->: recursive to non-recursive dependency. "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.
> > +
> > +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*)->. In other words, a "strong" path is a path from a lock
> > +walking to another through the lock dependencies, and if X 

Re: [RFC tip/locking/lockdep v6 01/20] lockdep/Documention: Recursive read lock detection reasoning

[Randy Dunlap]

Hi,

Just a few typos etc. below...

On 04/11/2018 06:50 AM, Boqun Feng wrote:
> Signed-off-by: Boqun Feng 
> ---
>  Documentation/locking/lockdep-design.txt | 178 
> +++
>  1 file changed, 178 insertions(+)
> 
> diff --git a/Documentation/locking/lockdep-design.txt 
> b/Documentation/locking/lockdep-design.txt
> index 9de1c158d44c..6bb9e90e2c4f 100644
> --- a/Documentation/locking/lockdep-design.txt
> +++ b/Documentation/locking/lockdep-design.txt
> @@ -284,3 +284,181 @@ 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 locks:
> +-
> +
> +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
> +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. However if the read_lock() is non-recursive read lock, then the 
> above
> +case is a deadlock, because even if the write_lock() in TASK B can not get 
> the
> +lock, but it can block the second read_lock() in TASK A.
> +
> +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 lock operations used to acquire it (more 
> specifically,
> +the value of the 'read' parameter for lock_acquire()). In other words, a 
> single
> +lock instance has three types of acquisition depending on the acquisition
> +functions: exclusive, non-recursive read, and recursive read.
> +
> +To be concise, we call that write locks and non-recursive read locks as
> +"non-recursive" locks and recursive read locks as "recursive" locks.
> +
> +Recursive locks don't block each other, while non-recursive locks do (this is
> +even true for two non-recursive read locks). A non-recursive lock can block 
> the
> +corresponding recursive lock, and vice versa.
> +
> +A deadlock case with recursive locks involved is as follow:
> +
> + TASK A: TASK B:
> +
> + read_lock(X);
> + read_lock(Y);
> + write_lock(Y);
> + write_lock(X);
> +
> +Task A is waiting for task B to read_unlock() Y and task B is waiting for 
> task
> +A to read_unlock() X.
> +
> +Dependency types and strong dependency paths:
> +-
> +In order to detect deadlocks as above, lockdep needs to track different 
> dependencies.
> +There are 4 categories for dependency edges in the lockdep graph:
> +
> +1) -(NN)->: non-recursive to non-recursive dependency. "X -(NN)-> Y" means
> +X -> Y and both X and Y are non-recursive locks.
> +
> +2) -(RN)->: recursive to non-recursive dependency. "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.
> +
> +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*)->. In other words, 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 will see why the path is called "strong" in next section.
> +
> +Recursive Read Deadlock Detection:
> 

[RFC tip/locking/lockdep v6 01/20] lockdep/Documention: Recursive read lock detection reasoning

[Boqun Feng]

This patch add the documentation piece for the reasoning of deadlock
detection related to recursive read lock. The following sections are
added:

*   Explain what is a recursive read lock, and what deadlock cases
they could introduce.

*   Introduce the notations for different types of dependencies, and
the definition of strong paths.

*   Proof for a closed strong path is both sufficient and necessary
for deadlock detections with recursive read locks involved. The
proof could also explain why we call the path "strong"

Signed-off-by: Boqun Feng 
---
 Documentation/locking/lockdep-design.txt | 178 +++
 1 file changed, 178 insertions(+)

diff --git a/Documentation/locking/lockdep-design.txt 
b/Documentation/locking/lockdep-design.txt
index 9de1c158d44c..6bb9e90e2c4f 100644
--- a/Documentation/locking/lockdep-design.txt
+++ b/Documentation/locking/lockdep-design.txt
@@ -284,3 +284,181 @@ 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 locks:
+-
+
+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
+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. However if the read_lock() is non-recursive read lock, then the 
above
+case is a deadlock, because even if the write_lock() in TASK B can not get the
+lock, but it can block the second read_lock() in TASK A.
+
+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 lock operations used to acquire it (more specifically,
+the value of the 'read' parameter for lock_acquire()). In other words, a single
+lock instance has three types of acquisition depending on the acquisition
+functions: exclusive, non-recursive read, and recursive read.
+
+To be concise, we call that write locks and non-recursive read locks as
+"non-recursive" locks and recursive read locks as "recursive" locks.
+
+Recursive locks don't block each other, while non-recursive locks do (this is
+even true for two non-recursive read locks). A non-recursive lock can block the
+corresponding recursive lock, and vice versa.
+
+A deadlock case with recursive locks involved is as follow:
+
+   TASK A: TASK B:
+
+   read_lock(X);
+   read_lock(Y);
+   write_lock(Y);
+   write_lock(X);
+
+Task A is waiting for task B to read_unlock() Y and task B is waiting for task
+A to read_unlock() X.
+
+Dependency types and strong dependency paths:
+-
+In order to detect deadlocks as above, lockdep needs to track different 
dependencies.
+There are 4 categories for dependency edges in the lockdep graph:
+
+1) -(NN)->: non-recursive to non-recursive dependency. "X -(NN)-> Y" means
+X -> Y and both X and Y are non-recursive locks.
+
+2) -(RN)->: recursive to non-recursive dependency. "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.
+
+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*)->. In other words, 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)->