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 <boqun.f...@gmail.com>
> ---
>  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(

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 <boqun.f...@gmail.com>
> > ---
> >  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);
> > 

[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 <boqun.f...@gmail.com>
---
 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 i

[RFC tip/locking/lockdep v6 04/20] lockdep: Redefine LOCK_*_STATE* bits

[Boqun Feng]

There are three types of lock acquisitions: write, non-recursive read
and recursive read, among which write locks and non-recursive read locks
have no difference from a viewpoint for deadlock detections, because a
write acquisition of the corresponding lock on an independent CPU or
task makes a non-recursive read lock act as a write lock in the sense of
deadlock. So we could treat them as the same type (named as
"non-recursive lock") in lockdep.

As in the irq lock inversion detection (safe->unsafe deadlock
detection), we used to differ write lock with read lock (non-recursive
and recursive ones), such a classification could be improved as
non-recursive read lock behaves the same as write lock, so this patch
redefines the meanings of LOCK_{USED_IN, ENABLED}_STATE*.

old:
LOCK_* : stands for write lock
LOCK_*_READ: stands for read lock(non-recursive and recursive)
new:
LOCK_* : stands for non-recursive(write lock and non-recursive
read lock)
LOCK_*_RR: stands for recursive read lock

Such a change is needed for a future improvement on recursive read
related irq inversion deadlock detection.

Signed-off-by: Boqun Feng <boqun.f...@gmail.com>
---
 Documentation/locking/lockdep-design.txt |  6 +++---
 kernel/locking/lockdep.c | 28 ++--
 kernel/locking/lockdep_internals.h   | 16 
 kernel/locking/lockdep_proc.c| 12 ++--
 4 files changed, 31 insertions(+), 31 deletions(-)

diff --git a/Documentation/locking/lockdep-design.txt 
b/Documentation/locking/lockdep-design.txt
index 6bb9e90e2c4f..53ede30ce16d 100644
--- a/Documentation/locking/lockdep-design.txt
+++ b/Documentation/locking/lockdep-design.txt
@@ -30,9 +30,9 @@ State
 The validator tracks lock-class usage history into 4n + 1 separate state bits:
 
 - 'ever held in STATE context'
-- 'ever held as readlock in STATE context'
+- 'ever held as recursive readlock in STATE context'
 - 'ever held with STATE enabled'
-- 'ever held as readlock with STATE enabled'
+- 'ever held as recurisve readlock with STATE enabled'
 
 Where STATE can be either one of (kernel/locking/lockdep_states.h)
  - hardirq
@@ -51,7 +51,7 @@ locking error messages, inside curlies. A contrived example:
 (_locks[i].lock){-.-...}, at: [] mutex_lock+0x21/0x24
 
 
-The bit position indicates STATE, STATE-read, for each of the states listed
+The bit position indicates STATE, STATE-RR, for each of the states listed
 above, and the character displayed in each indicates:
 
'.'  acquired while irqs disabled and not in irq context
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index f39a071ef0a8..14af2327b52a 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -448,10 +448,10 @@ DEFINE_PER_CPU(struct lockdep_stats, lockdep_stats);
  */
 
 #define __USAGE(__STATE)   \
-   [LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE)"-W",   \
-   [LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON-W", \
-   [LOCK_USED_IN_##__STATE##_READ] = "IN-"__stringify(__STATE)"-R",\
-   [LOCK_ENABLED_##__STATE##_READ] = __stringify(__STATE)"-ON-R",
+   [LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE),   \
+   [LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON",   \
+   [LOCK_USED_IN_##__STATE##_RR] = "IN-"__stringify(__STATE)"-RR", \
+   [LOCK_ENABLED_##__STATE##_RR] = __stringify(__STATE)"-ON-RR",
 
 static const char *usage_str[] =
 {
@@ -492,7 +492,7 @@ void get_usage_chars(struct lock_class *class, char 
usage[LOCK_USAGE_CHARS])
 
 #define LOCKDEP_STATE(__STATE) 
\
usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE); \
-   usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_READ);
+   usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_RR);
 #include "lockdep_states.h"
 #undef LOCKDEP_STATE
 
@@ -1645,7 +1645,7 @@ static const char *state_names[] = {
 
 static const char *state_rnames[] = {
 #define LOCKDEP_STATE(__STATE) \
-   __stringify(__STATE)"-READ",
+   __stringify(__STATE)"-RR",
 #include "lockdep_states.h"
 #undef LOCKDEP_STATE
 };
@@ -3039,14 +3039,14 @@ static int mark_irqflags(struct task_struct *curr, 
struct held_lock *hlock)
 * mark the lock as used in these contexts:
 */
if (!hlock->trylock) {
-   if (hlock->read) {
+   if (hlock->read == 2) {
if (curr->hardirq_context)
if (!mark_lock(curr, hlock,
-   LOCK_USED_IN_HARDIRQ_READ))
+   LOCK

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

[Boqun Feng]

On Sat, Feb 24, 2018 at 11:53:20PM +0100, Andrea Parri wrote:
> On Thu, Feb 22, 2018 at 03:09:03PM +0800, 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.
> 
> Once again... much appreciated!!, thanks for sharing.
> 

np ;-)

> 
> > 
> > Signed-off-by: Boqun Feng <boqun.f...@gmail.com>
> > Cc: Randy Dunlap <rdun...@infradead.org>
> > ---
> >  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..fd8a8d97ce58 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
> > +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 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.
> > +
> > +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).
> > +   They are treated equally in deadlock detection. "X -(NN)-> Y" means
> > +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);
> >

[RFC tip/locking/lockdep v5 03/17] lockdep: Redefine LOCK_*_STATE* bits

[Boqun Feng]

There are three types of lock acquisitions: write, non-recursive read
and recursive read, among which write locks and non-recursive read locks
have no difference from a viewpoint for deadlock detections, because a
write acquisition of the corresponding lock on an independent CPU or
task makes a non-recursive read lock act as a write lock in the sense of
deadlock. So we could treat them as the same type(named as
"non-recursive lock") in lockdep.

As in the irq lock inversion detection(safe->unsafe deadlock detection),
we used to differ write lock with read lock(non-recursive and
recursive ones), such a classification could be improved as
non-recursive read lock behaves the same as write lock, so this patch
redefines the meanings of LOCK_{USED_IN, ENABLED}_STATE*.

old:
LOCK_* : stands for write lock
LOCK_*_READ: stands for read lock(non-recursive and recursive)
new:
LOCK_* : stands for non-recursive(write lock and non-recursive
read lock)
LOCK_*_RR: stands for recursive read lock

Such a change is needed for a future improvement on recursive read
related irq inversion deadlock detection.

Signed-off-by: Boqun Feng <boqun.f...@gmail.com>
---
 Documentation/locking/lockdep-design.txt |  6 +++---
 kernel/locking/lockdep.c | 28 ++--
 kernel/locking/lockdep_internals.h   | 16 
 kernel/locking/lockdep_proc.c| 12 ++--
 4 files changed, 31 insertions(+), 31 deletions(-)

diff --git a/Documentation/locking/lockdep-design.txt 
b/Documentation/locking/lockdep-design.txt
index 9de1c158d44c..382bc25589c2 100644
--- a/Documentation/locking/lockdep-design.txt
+++ b/Documentation/locking/lockdep-design.txt
@@ -30,9 +30,9 @@ State
 The validator tracks lock-class usage history into 4n + 1 separate state bits:
 
 - 'ever held in STATE context'
-- 'ever held as readlock in STATE context'
+- 'ever held as recursive readlock in STATE context'
 - 'ever held with STATE enabled'
-- 'ever held as readlock with STATE enabled'
+- 'ever held as recurisve readlock with STATE enabled'
 
 Where STATE can be either one of (kernel/locking/lockdep_states.h)
  - hardirq
@@ -51,7 +51,7 @@ locking error messages, inside curlies. A contrived example:
 (_locks[i].lock){-.-...}, at: [] mutex_lock+0x21/0x24
 
 
-The bit position indicates STATE, STATE-read, for each of the states listed
+The bit position indicates STATE, STATE-RR, for each of the states listed
 above, and the character displayed in each indicates:
 
'.'  acquired while irqs disabled and not in irq context
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index c80f8276ceaa..5e6bf8d6954d 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -448,10 +448,10 @@ DEFINE_PER_CPU(struct lockdep_stats, lockdep_stats);
  */
 
 #define __USAGE(__STATE)   \
-   [LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE)"-W",   \
-   [LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON-W", \
-   [LOCK_USED_IN_##__STATE##_READ] = "IN-"__stringify(__STATE)"-R",\
-   [LOCK_ENABLED_##__STATE##_READ] = __stringify(__STATE)"-ON-R",
+   [LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE),   \
+   [LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON",   \
+   [LOCK_USED_IN_##__STATE##_RR] = "IN-"__stringify(__STATE)"-RR", \
+   [LOCK_ENABLED_##__STATE##_RR] = __stringify(__STATE)"-ON-RR",
 
 static const char *usage_str[] =
 {
@@ -492,7 +492,7 @@ void get_usage_chars(struct lock_class *class, char 
usage[LOCK_USAGE_CHARS])
 
 #define LOCKDEP_STATE(__STATE) 
\
usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE); \
-   usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_READ);
+   usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_RR);
 #include "lockdep_states.h"
 #undef LOCKDEP_STATE
 
@@ -1645,7 +1645,7 @@ static const char *state_names[] = {
 
 static const char *state_rnames[] = {
 #define LOCKDEP_STATE(__STATE) \
-   __stringify(__STATE)"-READ",
+   __stringify(__STATE)"-RR",
 #include "lockdep_states.h"
 #undef LOCKDEP_STATE
 };
@@ -3039,14 +3039,14 @@ static int mark_irqflags(struct task_struct *curr, 
struct held_lock *hlock)
 * mark the lock as used in these contexts:
 */
if (!hlock->trylock) {
-   if (hlock->read) {
+   if (hlock->read == 2) {
if (curr->hardirq_context)
if (!mark_lock(curr, hlock,
-   LOCK_USED_IN_HARDIRQ_READ))
+   LOCK

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

[Boqun Feng]

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.f...@gmail.com>
Cc: Randy Dunlap <rdun...@infradead.org>
---
 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..fd8a8d97ce58 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
+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 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.
+
+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).
+   They are treated equally in deadlock detection. "X -(NN)-> Y" means
+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

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.f...@gmail.com>
> > ---
> >  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 loc

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

[Boqun Feng]

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.f...@gmail.com>
---
 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
+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
+'read' parameter for lock_acquire(...)). In other words, a single lock instance
+have three types of acquisition depending on the acquisition functions:
+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),
+   they are treated equally in deadlock detection. "X -(NN)-> Y" means
+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 fo

[RFC tip/locking/lockdep v4 03/17] lockdep: Redefine LOCK_*_STATE* bits

[Boqun Feng]

There are three types of lock acquisitions: write, non-recursive read
and recursive read, among which write locks and non-recursive read locks
have no difference from a viewpoint for deadlock detections, because a
write acquisition of the corresponding lock on an independent CPU or
task makes a non-recursive read lock act as a write lock in the sense of
deadlock. So we could treat them as the same type(named as
"non-recursive lock") in lockdep.

As in the irq lock inversion detection(safe->unsafe deadlock detection),
we used to differ write lock with read lock(non-recursive and
recursive ones), such a classification could be improved as
non-recursive read lock behaves the same as write lock, so this patch
redefines the meanings of LOCK_{USED_IN, ENABLED}_STATE*.

old:
LOCK_* : stands for write lock
LOCK_*_READ: stands for read lock(non-recursive and recursive)
new:
LOCK_* : stands for non-recursive(write lock and non-recursive
read lock)
LOCK_*_RR: stands for recursive read lock

Such a change is needed for a future improvement on recursive read
related irq inversion deadlock detection.

Signed-off-by: Boqun Feng <boqun.f...@gmail.com>
---
 Documentation/locking/lockdep-design.txt |  6 +++---
 kernel/locking/lockdep.c | 28 ++--
 kernel/locking/lockdep_internals.h   | 16 
 kernel/locking/lockdep_proc.c| 12 ++--
 4 files changed, 31 insertions(+), 31 deletions(-)

diff --git a/Documentation/locking/lockdep-design.txt 
b/Documentation/locking/lockdep-design.txt
index 9de1c158d44c..382bc25589c2 100644
--- a/Documentation/locking/lockdep-design.txt
+++ b/Documentation/locking/lockdep-design.txt
@@ -30,9 +30,9 @@ State
 The validator tracks lock-class usage history into 4n + 1 separate state bits:
 
 - 'ever held in STATE context'
-- 'ever held as readlock in STATE context'
+- 'ever held as recursive readlock in STATE context'
 - 'ever held with STATE enabled'
-- 'ever held as readlock with STATE enabled'
+- 'ever held as recurisve readlock with STATE enabled'
 
 Where STATE can be either one of (kernel/locking/lockdep_states.h)
  - hardirq
@@ -51,7 +51,7 @@ locking error messages, inside curlies. A contrived example:
 (_locks[i].lock){-.-...}, at: [] mutex_lock+0x21/0x24
 
 
-The bit position indicates STATE, STATE-read, for each of the states listed
+The bit position indicates STATE, STATE-RR, for each of the states listed
 above, and the character displayed in each indicates:
 
'.'  acquired while irqs disabled and not in irq context
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 0f2bba043a83..8767830664aa 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -447,10 +447,10 @@ DEFINE_PER_CPU(struct lockdep_stats, lockdep_stats);
  */
 
 #define __USAGE(__STATE)   \
-   [LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE)"-W",   \
-   [LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON-W", \
-   [LOCK_USED_IN_##__STATE##_READ] = "IN-"__stringify(__STATE)"-R",\
-   [LOCK_ENABLED_##__STATE##_READ] = __stringify(__STATE)"-ON-R",
+   [LOCK_USED_IN_##__STATE] = "IN-"__stringify(__STATE),   \
+   [LOCK_ENABLED_##__STATE] = __stringify(__STATE)"-ON",   \
+   [LOCK_USED_IN_##__STATE##_RR] = "IN-"__stringify(__STATE)"-RR", \
+   [LOCK_ENABLED_##__STATE##_RR] = __stringify(__STATE)"-ON-RR",
 
 static const char *usage_str[] =
 {
@@ -491,7 +491,7 @@ void get_usage_chars(struct lock_class *class, char 
usage[LOCK_USAGE_CHARS])
 
 #define LOCKDEP_STATE(__STATE) 
\
usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE); \
-   usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_READ);
+   usage[i++] = get_usage_char(class, LOCK_USED_IN_##__STATE##_RR);
 #include "lockdep_states.h"
 #undef LOCKDEP_STATE
 
@@ -1640,7 +1640,7 @@ static const char *state_names[] = {
 
 static const char *state_rnames[] = {
 #define LOCKDEP_STATE(__STATE) \
-   __stringify(__STATE)"-READ",
+   __stringify(__STATE)"-RR",
 #include "lockdep_states.h"
 #undef LOCKDEP_STATE
 };
@@ -3034,14 +3034,14 @@ static int mark_irqflags(struct task_struct *curr, 
struct held_lock *hlock)
 * mark the lock as used in these contexts:
 */
if (!hlock->trylock) {
-   if (hlock->read) {
+   if (hlock->read == 2) {
if (curr->hardirq_context)
if (!mark_lock(curr, hlock,
-   LOCK_USED_IN_HARDIRQ_READ))
+   LOCK

Re: [PATCH] doc: memory-barriers: reStructure Text

[Boqun Feng]

On Wed, Jan 03, 2018 at 03:04:36PM +0530, afzal mohammed wrote:
> Let PDF & HTML's be created out of memory-barriers Text by
> reStructuring.
> 
> reStructuring done were,
> 1. Section headers modification, lower header case except start
> 2. Removal of manual index(contents section), since it now gets created
>automatically for html/pdf
> 3. Internal cross reference for easy navigation
> 4. Alignment adjustments
> 5. Strong emphasis made wherever there was emphasis earlier (through
>other ways), strong was chosen as normal emphasis showed in italics,
>which was felt to be not enough & strong showed it in bold
> 6. ASCII text & code snippets in literal blocks
> 7. Backquotes for inline instances in the paragraph's where they are
>expressed not in English, but in C, pseudo-code, file path etc.
> 8. Notes section created out of the earlier notes
> 9. Manual numbering replaced by auto-numbering
> 10.Bibliography (References section) made such that it can be
>cross-linked
> 
> Signed-off-by: afzal mohammed 
> ---
> 
> Hi,
> 
> With this change, pdf & html could be generated. There certainly are
> improvements to be made, but thought of first knowing whether migrating
> memory-barriers from txt to rst is welcome.
> 
> The location chosen is "Documentation/kernel-hacking", i was unsure
> where this should reside & there was no .rst file in top-level directory
> "Documentation", so put it into one of the existing folder that seemed
> to me as not that unsuitable.
> 
> Other files refer to memory-barrier.txt, those also needs to be
> adjusted based on where .rst can reside.
> 

How do you plan to handle the external references? For example, the
following LWN articles has a link this file:

https://lwn.net/Articles/718628/

And changing the name and/or location will break that link, AFAIK.

Regards,
Boqun

> afzal
> 
> 
[...]


signature.asc
Description: PGP signature

Re: [PATCH] documentation: Fix two-CPU control-dependency example

[Boqun Feng]

On Thu, Jul 20, 2017 at 04:07:14PM -0700, Paul E. McKenney wrote:
[...]
> > 
> > So if I respin the patch with the extern, would you still feel reluctant?
> 
> Yes, because I am not seeing how this change helps.  What is this telling
> the reader that the original did not, and how does it help the reader
> generate good concurrent code?
> 

One thing I think we probably should do is to make READ_ONCE() semantics
more clear, i.e. call it out that in our conceptual model for kernel
programming we always rely on the compiler to be serious about the
return value of READ_ONCE(). I didn't find the comment before
READ_ONCE() or memory-barriers.txt talking about something similar.

Or am I the only one having this kinda semantics guarantee in mind?

Regards,
Boqun

>   Thanx, Paul
> 
--
To unsubscribe from this list: send the line "unsubscribe linux-doc" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] documentation: Fix two-CPU control-dependency example

[Boqun Feng]

On Wed, Jul 19, 2017 at 10:47:04PM -0700, Paul E. McKenney wrote:
[...]
> > Hi Paul,
> > 
> > I know the compiler could optimize atomics in very interesting ways, but
> > this case is about volatile, so I guess our case is still fine? ;-)
> 
> Hello, Boqun,
> 
> When I asked that question, the answer I got was "the compiler must
> emit the load instruction, but is under no obligation to actually use the
> value loaded".
> 
> I don't happen to like that answer, by the way.  ;-)
> 

Me neither, seems to me the kernel happens to work well at
compiler-optimization's mercy ;-/

With claim like that, compiler could do optimization as turning:

struct task_struct *owner;

for (;;) {
owner = READ_ONCE(lock->owner);
if (owner && !mutex_spin_on_owner(lock, owner))
break;
/* ... */

into:

struct task_struct *owner;

owner = READ_ONCE(lock->owner);

for (;;READ_ONCE(lock->owner)) {
if (owner && !mutex_spin_on_owner(lock, owner))
break;
/* ... */

Because the load executed in every loop, and they just happen to choose
not to use the values. And this is within their rights!

Regards,
Boqun

>   Thanx, Paul
> 
> > > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0062r1.html
> > > 
> > 
> > Great material to wake up mind in the morning! Thanks.
> > 
> > Regards,
> > Boqun
> > 
> > > What are your thoughts on this?
> > > 
> > >   Thanx, Paul
> > > 
> > > > Thanks, Akira
> > > > 
> > > > > That said, I very much welcome critical reviews of 
> > > > > memory-barriers.txt,
> > > > > so please do feel free to continue doing that!
> > > > > 
> > > > >   Thanx, Paul
> > > > > 
> > > > > 
> > > > 
> > > 
> > 
> 
--
To unsubscribe from this list: send the line "unsubscribe linux-doc" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] documentation: Fix two-CPU control-dependency example

[Boqun Feng]

On Wed, Jul 19, 2017 at 02:56:02PM -0700, Paul E. McKenney wrote:
> On Thu, Jul 20, 2017 at 06:33:26AM +0900, Akira Yokosawa wrote:
> > On 2017/07/20 2:43, Paul E. McKenney wrote:
> > > On Mon, Jul 17, 2017 at 05:24:42PM +0900, Akira Yokosawa wrote:
> > >> >From b798b9b631e237d285aa8699da00bfb8ced33bea Mon Sep 17 00:00:00 2001
> > >> From: Akira Yokosawa 
> > >> Date: Mon, 17 Jul 2017 16:25:33 +0900
> > >> Subject: [PATCH] documentation: Fix two-CPU control-dependency example
> > >>
> > >> In commit 5646f7acc95f ("memory-barriers: Fix control-ordering
> > >> no-transitivity example"), the operator in "if" statement of
> > >> the two-CPU example was modified from ">=" to ">".
> > >> Now the example misses the point because there is no party
> > >> who will modify "x" nor "y". So each CPU performs only the
> > >> READ_ONCE().
> > >>
> > >> The point of this example is to use control dependency for ordering,
> > >> and the WRITE_ONCE() should always be executed.
> > >>
> > >> So it was correct prior to the above mentioned commit. Partial
> > >> revert of the commit (with context adjustments regarding other
> > >> changes thereafter) restores the point.
> > >>
> > >> Note that the three-CPU example demonstrating the lack of
> > >> transitivity stands regardless of this partial revert.
> > >>
> > >> Signed-off-by: Akira Yokosawa 
> > > 
> > > Hello, Akira,
> > > 
> > > You are quite right that many compilers would generate straightforward
> > > code for the code fragment below, and in that case, the assertion could
> > > never trigger due to either TSO or control dependencies, depending on
> > > the architecture this was running on.
> > > 
> > > However, if the compiler was too smart for our good, it could figure
> > > out that "x" and "y" only take on the values zero and one, so that
> > > the "if" would always be taken.  At that point, the compiler could
> > > simply ignore the "if" with the result shown below.
> > > 
> > >> ---
> > >>  Documentation/memory-barriers.txt | 2 +-
> > >>  1 file changed, 1 insertion(+), 1 deletion(-)
> > >>
> > >> diff --git a/Documentation/memory-barriers.txt 
> > >> b/Documentation/memory-barriers.txt
> > >> index c4ddfcd..c1ebe99 100644
> > >> --- a/Documentation/memory-barriers.txt
> > >> +++ b/Documentation/memory-barriers.txt
> > >> @@ -851,7 +851,7 @@ demonstrated by two related examples, with the 
> > >> initial values of
> > >>  CPU 0 CPU 1
> > >>  ===   ===
> > >>  r1 = READ_ONCE(x);r2 = READ_ONCE(y);
> > >> -if (r1 > 0)   if (r2 > 0)
> > >> +if (r1 >= 0)  if (r2 >= 0)
> > >>WRITE_ONCE(y, 1); WRITE_ONCE(x, 1);
> > >>
> > >>  assert(!(r1 == 1 && r2 == 1));
> > > 
> > > Original program:
> > > 
> > >   CPU 0 CPU 1
> > >   ===   ===
> > >   r1 = READ_ONCE(x);r2 = READ_ONCE(y);
> > >   if (r1 >= 0)  if (r2 >= 0)
> > > WRITE_ONCE(y, 1); WRITE_ONCE(x, 1);
> > > 
> > >   assert(!(r1 == 1 && r2 == 1));
> > > 
> > > Enthusiastically optimized program:
> > > 
> > >   CPU 0 CPU 1
> > >   ===   ===
> > >   r1 = READ_ONCE(x);r2 = READ_ONCE(y);
> > >   WRITE_ONCE(y, 1); WRITE_ONCE(x, 1);
> > > 
> > >   assert(!(r1 == 1 && r2 == 1));
> > > 
> > > This optimized version could trigger the assertion.
> > > 
> > > So we do need to stick with the ">" comparison.
> > 
> > Well but,
> > 
> > Current example:
> > 
> > CPU 0 CPU 1
> > ===   ===
> > r1 = READ_ONCE(x);r2 = READ_ONCE(y);
> > if (r1 > 0)   if (r2 > 0)
> >   WRITE_ONCE(y, 1); WRITE_ONCE(x, 1);
> > 
> > assert(!(r1 == 1 && r2 == 1));
> > 
> > Such a clever compiler might be able to prove that "x" and "y"
> > are never modified and end up in the following:
> > 

Hi Akira,

I wouldn't call that compiler a clever one, it's a broken one ;-)

So here is the thing: READ_ONCE() is a *volatile* load, which means the
compiler has to generate code that actually does a load, so the values
of r1 and r2 depend on the loads, therefore, a sane compiler will not 
optimize the if()s out because the volatile semantics of READ_ONCE().
Otherwise, I think we have a lot more to worry about than this case.

> > CPU 0 CPU 1
> > ===   ===
> > r1 = READ_ONCE(x);r2 = READ_ONCE(y);
> > 
> > assert(!(r1 == 1 && r2 == 1));
> > 
> > This means it is impossible to describe this example in C,
> > doesn't it?
> 
> That is a matter of some debate, but it has gotten increasingly more
> difficult to get C to do one's bidding over the decades.
> 
> > What am I missing here?
> 
> The compiler has to work harder in your