[PATCH v3 0/5] Revise crossrelease.txt

[PATCH v3 0/5] Revise crossrelease.txt

[Byungchul Park]

In this version, I've split a big one into small 5 patches so you can
review them more easily. But, choose between a big one and small 5
patches when you take it, as you prefer.

I will add a big one merging all of these.

---

Changes from v2
- Split a big patch into small 5 patches.
- Apply what Ingo pointed out.
- Leave original contents unchanged as much as possible.

Changes from v1
- Run several tools checking english spell and grammar over the text.
- Simplify the document more.

Byungchul Park (5):
  locking/Documentation: Remove meaningless examples and a note
  locking/Documentation: Fix typos and clear grammar errors
  locking/Documentation: Fix weird expressions.
  locking/Documentation: Add an example to help crossrelease.txt more
    readable
  locking/Documentation: Align crossrelease.txt with the width

 Documentation/locking/crossrelease.txt | 329 ++++++++++++++++-----------------
 1 file changed, 155 insertions(+), 174 deletions(-)

-- 
1.9.1

[PATCH v3 1/5] locking/Documentation: Remove meaningless examples and a note

[Byungchul Park]

crossrelease.txt is too verbose and includes two meaningless examples
and an unnecessary note. Remove them.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 Documentation/locking/crossrelease.txt | 48 +---------------------------------
 1 file changed, 1 insertion(+), 47 deletions(-)

diff --git a/Documentation/locking/crossrelease.txt b/Documentation/locking/crossrelease.txt
index bdf1423..0f8eb8a 100644
--- a/Documentation/locking/crossrelease.txt
+++ b/Documentation/locking/crossrelease.txt
@@ -281,31 +281,7 @@ causes a deadlock. The more lockdep adds dependencies, the more it
 thoroughly works. Thus Lockdep has to do its best to detect and add as
 many true dependencies into a graph as possible.
 
-For example, considering only typical locks, lockdep builds a graph like:
-
-   A -> B -
-           \
-            -> E
-           /
-   C -> D -
-
-   where A, B,..., E are different lock classes.
-
-On the other hand, under the relaxation, additional dependencies might
-be created and added. Assuming additional 'FX -> C' and 'E -> GX' are
-added thanks to the relaxation, the graph will be:
-
-         A -> B -
-                 \
-                  -> E -> GX
-                 /
-   FX -> C -> D -
-
-   where A, B,..., E, FX and GX are different lock classes, and a suffix
-   'X' is added on non-typical locks.
-
-The latter graph gives us more chances to check circular dependencies
-than the former. However, it might suffer performance degradation since
+However, it might suffer performance degradation since
 relaxing the limitation, with which design and implementation of lockdep
 can be efficient, might introduce inefficiency inevitably. So lockdep
 should provide two options, strong detection and efficient detection.
@@ -469,12 +445,6 @@ works without crossrelease for typical locks.
 
    where A, B and C are different lock classes.
 
-   NOTE: This document assumes that readers already understand how
-   lockdep works without crossrelease thus omits details. But there's
-   one thing to note. Lockdep pretends to pop a lock from held_locks
-   when releasing it. But it's subtly different from the original pop
-   operation because lockdep allows other than the top to be poped.
-
 In this case, lockdep adds 'the top of held_locks -> the lock to acquire'
 dependency every time acquiring a lock.
 
@@ -805,22 +775,6 @@ Remind what a dependency is. A dependency exists if:
 
 For example:
 
-   acquire A
-   acquire B /* A dependency 'A -> B' exists */
-   release B
-   release A
-
-   where A and B are different lock classes.
-
-A depedency 'A -> B' exists since:
-
-   1. A waiter for A and a waiter for B might exist when acquiring B.
-   2. Only way to wake up each is to release what it waits for.
-   3. Whether the waiter for A can be woken up depends on whether the
-      other can. IOW, TASK X cannot release A if it fails to acquire B.
-
-For another example:
-
    TASK X			   TASK Y
    ------			   ------
 				   acquire AX
-- 
1.9.1

[PATCH v3 2/5] locking/Documentation: Fix typos and clear grammar errors

[Byungchul Park]

crossrelease.txt includes many typos and grammar errors. Fix them using
a few spell checkers and grammar checkers.

Clear errors are also fixed by myself.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 Documentation/locking/crossrelease.txt | 170 ++++++++++++++++-----------------
 1 file changed, 85 insertions(+), 85 deletions(-)

diff --git a/Documentation/locking/crossrelease.txt b/Documentation/locking/crossrelease.txt
index 0f8eb8a..48ef689 100644
--- a/Documentation/locking/crossrelease.txt
+++ b/Documentation/locking/crossrelease.txt
@@ -12,10 +12,10 @@ Contents:
 
  (*) Limitation
 
-     - Limit lockdep
+     - Limiting lockdep
      - Pros from the limitation
      - Cons from the limitation
-     - Relax the limitation
+     - Relaxing the limitation
 
  (*) Crossrelease
 
@@ -32,7 +32,7 @@ Contents:
      - Avoid duplication
      - Lockless for hot paths
 
- (*) APPENDIX A: What lockdep does to work aggresively
+ (*) APPENDIX A: What lockdep does to work aggressively
 
  (*) APPENDIX B: How to avoid adding false dependencies
 
@@ -55,21 +55,21 @@ For example:
    A context going to trigger event A is waiting for event B to happen.
    A context going to trigger event B is waiting for event C to happen.
 
-A deadlock occurs when these three wait operations run at the same time,
+A deadlock occurs when these three waiters run at the same time,
 because event C cannot be triggered if event A does not happen, which in
 turn cannot be triggered if event B does not happen, which in turn
 cannot be triggered if event C does not happen. After all, no event can
 be triggered since any of them never meets its condition to wake up.
 
-A dependency might exist between two waiters and a deadlock might happen
-due to an incorrect releationship between dependencies. Thus, we must
-define what a dependency is first. A dependency exists between them if:
+A dependency might exist between two waiters and a deadlock happens
+due to an incorrect relationship between dependencies. Thus, we must
+define what a dependency is first. A dependency exists if:
 
    1. There are two waiters waiting for each event at a given time.
    2. The only way to wake up each waiter is to trigger its event.
    3. Whether one can be woken up depends on whether the other can.
 
-Each wait in the example creates its dependency like:
+Each waiter in the example creates its dependency like:
 
    Event C depends on event A.
    Event A depends on event B.
@@ -77,7 +77,7 @@ Each wait in the example creates its dependency like:
 
    NOTE: Precisely speaking, a dependency is one between whether a
    waiter for an event can be woken up and whether another waiter for
-   another event can be woken up. However from now on, we will describe
+   another event can be woken up. However, from now on, we will describe
    a dependency as if it's one between an event and another event for
    simplicity.
 
@@ -109,9 +109,9 @@ event in the previous section.
 In short, lockdep does:
 
    1. Detect a new dependency.
-   2. Add the dependency into a global graph.
+   2. Add the dependency to a global graph.
    3. Check if that makes dependencies circular.
-   4. Report a deadlock or its possibility if so.
+   4. Report the deadlock or its possibility if so.
 
 For example, consider a graph built by lockdep that looks like:
 
@@ -123,7 +123,7 @@ For example, consider a graph built by lockdep that looks like:
 
    where A, B,..., E are different lock classes.
 
-Lockdep will add a dependency into the graph on detection of a new
+Lockdep will add a dependency to the graph on detection of a new
 dependency. For example, it will add a dependency 'E -> C' when a new
 dependency between lock E and lock C is detected. Then the graph will be:
 
@@ -147,7 +147,7 @@ This graph contains a subgraph which demonstrates circular dependencies:
    \                  /
     ------------------
 
-   where C, D and E are different lock classes.
+   where C, D, and E are different lock classes.
 
 This is the condition under which a deadlock might occur. Lockdep
 reports it on detection after adding a new dependency. This is the way
@@ -163,13 +163,13 @@ dependencies were created after adding each new dependency.
 Limitation
 ==========
 
-Limit lockdep
--------------
+Limiting lockdep
+----------------
 
 Limiting lockdep to work on only typical locks e.g. spin locks and
-mutexes, which are released within the acquire context, the
+mutexes, which are released within their acquire contexts, the
 implementation becomes simple but its capacity for detection becomes
-limited. Let's check pros and cons in next section.
+limited. Let's check pros and cons in the next two sections.
 
 
 Pros from the limitation
@@ -179,7 +179,7 @@ Given the limitation, when acquiring a lock, locks in a held_locks
 cannot be released if the context cannot acquire it so has to wait to
 acquire it, which means all waiters for the locks in the held_locks are
 stuck. It's an exact case to create dependencies between each lock in
-the held_locks and the lock to acquire.
+the held_locks and the lock to acquire at the moment.
 
 For example:
 
@@ -203,8 +203,8 @@ lockdep can avoid racy problems without explicit locks while handling
 the local data.
 
 Lastly, lockdep only needs to keep locks currently being held, to build
-a dependency graph. However, relaxing the limitation, it needs to keep
-even locks already released, because a decision whether they created
+the dependency graph. However, relaxing the limitation, it needs to keep
+even locks already released, because the decision whether they created
 dependencies might be long-deferred.
 
 To sum up, we can expect several advantages from the limitation:
@@ -265,8 +265,8 @@ Given the limitation, lockdep cannot detect a deadlock or its
 possibility caused by page locks or completions.
 
 
-Relax the limitation
---------------------
+Relaxing the limitation
+-----------------------
 
 Under the limitation, things to create dependencies are limited to
 typical locks. However, synchronization primitives like page locks and
@@ -278,8 +278,8 @@ these locks to work with lockdep.
 Detecting dependencies is very important for lockdep to work because
 adding a dependency means adding an opportunity to check whether it
 causes a deadlock. The more lockdep adds dependencies, the more it
-thoroughly works. Thus Lockdep has to do its best to detect and add as
-many true dependencies into a graph as possible.
+thoroughly works. Thus, lockdep has to do its best to detect and add as
+many true dependencies to the graph as possible.
 
 However, it might suffer performance degradation since
 relaxing the limitation, with which design and implementation of lockdep
@@ -312,27 +312,27 @@ Introduce crossrelease
 In order to allow lockdep to handle additional dependencies by what
 might be released in any context, namely 'crosslock', we have to be able
 to identify those created by crosslocks. The proposed 'crossrelease'
-feature provoides a way to do that.
+feature provides a way to do that.
 
 Crossrelease feature has to do:
 
    1. Identify dependencies created by crosslocks.
-   2. Add the dependencies into a dependency graph.
+   2. Add the dependencies to the dependency graph.
 
-That's all. Once a meaningful dependency is added into graph, then
+That's all. Once a meaningful dependency is added to the graph, then
 lockdep would work with the graph as it did. The most important thing
 crossrelease feature has to do is to correctly identify and add true
-dependencies into the global graph.
+dependencies to the global graph.
 
 A dependency e.g. 'A -> B' can be identified only in the A's release
 context because a decision required to identify the dependency can be
 made only in the release context. That is to decide whether A can be
-released so that a waiter for A can be woken up. It cannot be made in
+released so that waiters for A can be woken up. That cannot be made in
 other than the A's release context.
 
 It's no matter for typical locks because each acquire context is same as
 its release context, thus lockdep can decide whether a lock can be
-released in the acquire context. However for crosslocks, lockdep cannot
+released in the acquire context. However, for crosslocks, lockdep cannot
 make the decision in the acquire context but has to wait until the
 release context is identified.
 
@@ -351,7 +351,7 @@ Introduce commit
 ----------------
 
 Since crossrelease defers the work adding true dependencies of
-crosslocks until they are actually released, crossrelease has to queue
+crosslocks until they are eventually released, crossrelease has to queue
 all acquisitions which might create dependencies with the crosslocks.
 Then it identifies dependencies using the queued data in batches at a
 proper time. We call it 'commit'.
@@ -383,7 +383,7 @@ There are four types of dependencies:
    to wait until the decision can be made. Commit is necessary.
    But, handling CC type is not implemented yet. It's a future work.
 
-Lockdep can work without commit for typical locks, but commit step is
+Lockdep can work without commit for typical locks, but the step is
 necessary once crosslocks are involved. Introducing commit, lockdep
 performs three steps. What lockdep does in each step is:
 
@@ -392,7 +392,7 @@ performs three steps. What lockdep does in each step is:
    it at the commit step. For crosslocks, it saves data which will be
    used at the commit step and increases a reference count for it.
 
-2. Commit: No action is reauired for typical locks. For crosslocks,
+2. Commit: No action is required for typical locks. For crosslocks,
    lockdep adds CT type dependencies using the data saved at the
    acquisition step.
 
@@ -418,9 +418,9 @@ Crossrelease introduces two main data structures.
 
    This is an array embedded in task_struct, for keeping lock history so
    that dependencies can be added using them at the commit step. Since
-   it's local data, it can be accessed locklessly in the owner context.
+   they are local data, they can be accessed locklessly in the owner context.
    The array is filled at the acquisition step and consumed at the
-   commit step. And it's managed in circular manner.
+   commit step. And it's managed in a circular manner.
 
 2. cross_lock
 
@@ -432,23 +432,23 @@ How crossrelease works
 ----------------------
 
 It's the key of how crossrelease works, to defer necessary works to an
-appropriate point in time and perform in at once at the commit step.
-Let's take a look with examples step by step, starting from how lockdep
-works without crossrelease for typical locks.
+appropriate point in time and perform the works at the commit step.
+Let's take a look at examples step by step, starting from how lockdep
+works for typical locks, without crossrelease.
 
-   acquire A /* Push A onto held_locks */
-   acquire B /* Push B onto held_locks and add 'A -> B' */
-   acquire C /* Push C onto held_locks and add 'B -> C' */
+   acquire A /* Push A to held_locks */
+   acquire B /* Push B to held_locks and add 'A -> B' */
+   acquire C /* Push C to held_locks and add 'B -> C' */
    release C /* Pop C from held_locks */
    release B /* Pop B from held_locks */
    release A /* Pop A from held_locks */
 
-   where A, B and C are different lock classes.
+   where A, B, and C are different lock classes.
 
-In this case, lockdep adds 'the top of held_locks -> the lock to acquire'
+Lockdep adds 'the top of held_locks -> the lock to acquire'
 dependency every time acquiring a lock.
 
-After adding 'A -> B', a dependency graph will be:
+After adding 'A -> B', the dependency graph will be:
 
    A -> B
 
@@ -458,7 +458,7 @@ And after adding 'B -> C', the graph will be:
 
    A -> B -> C
 
-   where A, B and C are different lock classes.
+   where A, B, and C are different lock classes.
 
 Let's performs commit step even for typical locks to add dependencies.
 Of course, commit step is not necessary for them, however, it would work
@@ -466,7 +466,7 @@ well because this is a more general way.
 
    acquire A
    /*
-    * Queue A into hist_locks
+    * Queue A in hist_locks
     *
     * In hist_locks: A
     * In graph: Empty
@@ -474,7 +474,7 @@ well because this is a more general way.
 
    acquire B
    /*
-    * Queue B into hist_locks
+    * Queue B in hist_locks
     *
     * In hist_locks: A, B
     * In graph: Empty
@@ -482,7 +482,7 @@ well because this is a more general way.
 
    acquire C
    /*
-    * Queue C into hist_locks
+    * Queue C in hist_locks
     *
     * In hist_locks: A, B, C
     * In graph: Empty
@@ -524,7 +524,7 @@ well because this is a more general way.
 
    release A
 
-   where A, B and C are different lock classes.
+   where A, B, and C are different lock classes.
 
 In this case, dependencies are added at the commit step as described.
 
@@ -532,14 +532,14 @@ After commits for A, B and C, the graph will be:
 
    A -> B -> C
 
-   where A, B and C are different lock classes.
+   where A, B, and C are different lock classes.
 
    NOTE: A dependency 'A -> C' is optimized out.
 
-We can see the former graph built without commit step is same as the
-latter graph built using commit steps. Of course the former way leads to
+We can see the former graph built without the commit step is same as the
+latter graph built using commit steps. Of course, the former way leads to
 earlier finish for building the graph, which means we can detect a
-deadlock or its possibility sooner. So the former way would be prefered
+deadlock or its possibility sooner. So the former way would be preferred
 when possible. But we cannot avoid using the latter way for crosslocks.
 
 Let's look at how commit steps work for crosslocks. In this case, the
@@ -550,8 +550,8 @@ that the AX release context is different from the AX acquire context.
    ------------------		   ------------------
 				   acquire A
 				   /*
-				    * Push A onto held_locks
-				    * Queue A into hist_locks
+				    * Push A to held_locks
+				    * Queue A in hist_locks
 				    *
 				    * In held_locks: A
 				    * In hist_locks: A
@@ -574,8 +574,8 @@ that the AX release context is different from the AX acquire context.
 
    acquire C
    /*
-    * Push C onto held_locks
-    * Queue C into hist_locks
+    * Push C to held_locks
+    * Queue C in hist_locks
     *
     * In held_locks: C
     * In hist_locks: C
@@ -592,8 +592,8 @@ that the AX release context is different from the AX acquire context.
     */
 				   acquire D
 				   /*
-				    * Push D onto held_locks
-				    * Queue D into hist_locks
+				    * Push D to held_locks
+				    * Queue D in hist_locks
 				    * Add 'the top of held_locks -> D'
 				    *
 				    * In held_locks: A, D
@@ -602,8 +602,8 @@ that the AX release context is different from the AX acquire context.
 				    */
    acquire E
    /*
-    * Push E onto held_locks
-    * Queue E into hist_locks
+    * Push E to held_locks
+    * Queue E in hist_locks
     *
     * In held_locks: E
     * In hist_locks: C, E
@@ -654,10 +654,10 @@ that the AX release context is different from the AX acquire context.
 				    *           'BX -> C', 'BX -> E'
 				    */
 
-   where A, BX, C,..., E are different lock classes, and a suffix 'X' is
-   added on crosslocks.
+   where A, BX, C,..., E are different lock classes and a suffix 'X' is
+   added at crosslocks.
 
-Crossrelease considers all acquisitions after acqiuring BX are
+Crossrelease considers all acquisitions after acquiring BX are
 candidates which might create dependencies with BX. True dependencies
 will be determined when identifying the release context of BX. Meanwhile,
 all typical locks are queued so that they can be used at the commit step.
@@ -674,8 +674,8 @@ The final graph will be, with crossrelease:
       \
        -> D
 
-   where A, BX, C,..., E are different lock classes, and a suffix 'X' is
-   added on crosslocks.
+   where A, BX, C,..., E are different lock classes and a suffix 'X' is
+   added at crosslocks.
 
 However, the final graph will be, without crossrelease:
 
@@ -702,7 +702,7 @@ Avoid duplication
 
 Crossrelease feature uses a cache like what lockdep already uses for
 dependency chains, but this time it's for caching CT type dependencies.
-Once that dependency is cached, the same will never be added again.
+Once a dependency is cached, the same will never be added again.
 
 
 Lockless for hot paths
@@ -711,7 +711,7 @@ Lockless for hot paths
 To keep all locks for later use at the commit step, crossrelease adopts
 a local array embedded in task_struct, which makes access to the data
 lockless by forcing it to happen only within the owner context. It's
-like how lockdep handles held_locks. Lockless implmentation is important
+like how lockdep handles held_locks. Lockless implementation is important
 since typical locks are very frequently acquired and released.
 
 
@@ -719,22 +719,22 @@ since typical locks are very frequently acquired and released.
 APPENDIX A: What lockdep does to work aggresively
 =================================================
 
-A deadlock actually occurs when all wait operations creating circular
+A deadlock actually occurs when all waiters creating circular
 dependencies run at the same time. Even though they don't, a potential
-deadlock exists if the problematic dependencies exist. Thus it's
+deadlock exists if the problematic dependencies exist. Thus, it's
 meaningful to detect not only an actual deadlock but also its potential
 possibility. The latter is rather valuable. When a deadlock occurs
 actually, we can identify what happens in the system by some means or
-other even without lockdep. However, there's no way to detect possiblity
-without lockdep unless the whole code is parsed in head. It's terrible.
+other even without lockdep. However, there's no way to detect possibility
+without lockdep unless the whole code is parsed in the head. It's terrible.
 Lockdep does the both, and crossrelease only focuses on the latter.
 
 Whether or not a deadlock actually occurs depends on several factors.
 For example, what order contexts are switched in is a factor. Assuming
 circular dependencies exist, a deadlock would occur when contexts are
-switched so that all wait operations creating the dependencies run
-simultaneously. Thus to detect a deadlock possibility even in the case
-that it has not occured yet, lockdep should consider all possible
+switched so that all waiters creating the dependencies run
+simultaneously. Thus, to detect a deadlock possibility even in the case
+that it has not occurred yet, lockdep should consider all possible
 combinations of dependencies, trying to:
 
 1. Use a global dependency graph.
@@ -746,7 +746,7 @@ combinations of dependencies, trying to:
 
 2. Check dependencies between classes instead of instances.
 
-   What actually causes a deadlock are instances of lock. However,
+   What actually causes a deadlock are instances of locks. However,
    lockdep checks dependencies between classes instead of instances.
    This way lockdep can detect a deadlock which has not happened but
    might happen in future by others but the same class.
@@ -782,18 +782,18 @@ For example:
    release B
    release AX held by Y
 
-   where AX and B are different lock classes, and a suffix 'X' is added
-   on crosslocks.
+   where AX and B are different lock classes and a suffix 'X' is added
+   at crosslocks.
 
 Even in this case involving crosslocks, the same rule can be applied. A
-depedency 'AX -> B' exists since:
+dependency 'AX -> B' exists since:
 
    1. A waiter for AX and a waiter for B might exist when acquiring B.
-   2. Only way to wake up each is to release what it waits for.
+   2. The only way to wake up each is to release what it waits for.
    3. Whether the waiter for AX can be woken up depends on whether the
       other can. IOW, TASK X cannot release AX if it fails to acquire B.
 
-Let's take a look at more complicated example:
+Let's take a look at a more complicated example:
 
    TASK X			   TASK Y
    ------			   ------
@@ -805,21 +805,21 @@ Let's take a look at more complicated example:
    release C
    release AX held by Y
 
-   where AX, B and C are different lock classes, and a suffix 'X' is
-   added on crosslocks.
+   where AX, B, and C are different lock classes and a suffix 'X' is
+   added at crosslocks.
 
 Does a dependency 'AX -> B' exist? Nope.
 
 Two waiters are essential to create a dependency. However, waiters for
 AX and B to create 'AX -> B' cannot exist at the same time in this
-example. Thus the dependency 'AX -> B' cannot be created.
+example. Thus, the dependency 'AX -> B' cannot be created.
 
 It would be ideal if the full set of true ones can be considered. But
 we can ensure nothing but what actually happened. Relying on what
 actually happens at runtime, we can anyway add only true ones, though
 they might be a subset of true ones. It's similar to how lockdep works
 for typical locks. There might be more true dependencies than what
-lockdep has detected in runtime. Lockdep has no choice but to rely on
+lockdep has detected at runtime. Lockdep has no choice but to rely on
 what actually happens. Crossrelease also relies on it.
 
 CONCLUSION
-- 
1.9.1

[PATCH v3 3/5] locking/Documentation: Fix weird expressions.

[Byungchul Park]

Fix Weird expressions not reported by checker tools by myself.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 Documentation/locking/crossrelease.txt | 87 ++++++++++++++++++----------------
 1 file changed, 45 insertions(+), 42 deletions(-)

diff --git a/Documentation/locking/crossrelease.txt b/Documentation/locking/crossrelease.txt
index 48ef689..bb449e8 100644
--- a/Documentation/locking/crossrelease.txt
+++ b/Documentation/locking/crossrelease.txt
@@ -30,7 +30,7 @@ Contents:
  (*) Optimizations
 
      - Avoid duplication
-     - Lockless for hot paths
+     - Make hot paths lockless
 
  (*) APPENDIX A: What lockdep does to work aggressively
 
@@ -195,12 +195,11 @@ For example:
 When acquiring lock A, the held_locks of CONTEXT X is empty thus no
 dependency is added. But when acquiring lock B, lockdep detects and adds
 a new dependency 'A -> B' between lock A in the held_locks and lock B.
-They can be simply added whenever acquiring each lock.
+Dependencies can be simply added this way, whenever acquiring each lock.
 
-And data required by lockdep exists in a local structure, held_locks
-embedded in task_struct. Forcing to access the data within the context,
-lockdep can avoid racy problems without explicit locks while handling
-the local data.
+Furthermore, since data required to create a dependency can be kept in
+local task_struct, lockdep can avoid racy problems without explicit
+protection by forcing to access the data within the context.
 
 Lastly, lockdep only needs to keep locks currently being held, to build
 the dependency graph. However, relaxing the limitation, it needs to keep
@@ -210,7 +209,8 @@ dependencies might be long-deferred.
 To sum up, we can expect several advantages from the limitation:
 
    1. Lockdep can easily identify a dependency when acquiring a lock.
-   2. Races are avoidable while accessing local locks in a held_locks.
+   2. Races are avoidable without explicit protection while accessing
+      local locks in a held_locks.
    3. Lockdep only needs to keep locks currently being held.
 
 CONCLUSION
@@ -353,8 +353,9 @@ Introduce commit
 Since crossrelease defers the work adding true dependencies of
 crosslocks until they are eventually released, crossrelease has to queue
 all acquisitions which might create dependencies with the crosslocks.
-Then it identifies dependencies using the queued data in batches at a
-proper time. We call it 'commit'.
+Then lockdep can identify dependencies using the queued data in batches
+at a proper time. We call the step adding true dependencies to the graph
+in batches, 'commit'.
 
 There are four types of dependencies:
 
@@ -433,6 +434,7 @@ How crossrelease works
 
 It's the key of how crossrelease works, to defer necessary works to an
 appropriate point in time and perform the works at the commit step.
+
 Let's take a look at examples step by step, starting from how lockdep
 works for typical locks, without crossrelease.
 
@@ -460,9 +462,9 @@ And after adding 'B -> C', the graph will be:
 
    where A, B, and C are different lock classes.
 
-Let's performs commit step even for typical locks to add dependencies.
-Of course, commit step is not necessary for them, however, it would work
-well because this is a more general way.
+Let's build the graph using the commit step with the same example. Of
+course, the step is not necessary for typical locks, however, it would
+also work because this is a more general way.
 
    acquire A
    /*
@@ -526,9 +528,8 @@ well because this is a more general way.
 
    where A, B, and C are different lock classes.
 
-In this case, dependencies are added at the commit step as described.
-
-After commits for A, B and C, the graph will be:
+Dependencies are added at the commit step as described. After commits
+for A, B, and C, the graph will be:
 
    A -> B -> C
 
@@ -537,19 +538,18 @@ After commits for A, B and C, the graph will be:
    NOTE: A dependency 'A -> C' is optimized out.
 
 We can see the former graph built without the commit step is same as the
-latter graph built using commit steps. Of course, the former way leads to
+latter graph. Of course, the former way leads to
 earlier finish for building the graph, which means we can detect a
 deadlock or its possibility sooner. So the former way would be preferred
 when possible. But we cannot avoid using the latter way for crosslocks.
 
-Let's look at how commit steps work for crosslocks. In this case, the
-commit step is performed only on crosslock AX as real. And it assumes
-that the AX release context is different from the AX acquire context.
+Lastly, let's look at how commit works for crosslocks in practice.
 
    BX RELEASE CONTEXT		   BX ACQUIRE CONTEXT
    ------------------		   ------------------
 				   acquire A
 				   /*
+				    * Add 'the top of held_locks -> A'
 				    * Push A to held_locks
 				    * Queue A in hist_locks
 				    *
@@ -574,6 +574,7 @@ that the AX release context is different from the AX acquire context.
 
    acquire C
    /*
+    * Add 'the top of held_locks -> C'
     * Push C to held_locks
     * Queue C in hist_locks
     *
@@ -592,9 +593,9 @@ that the AX release context is different from the AX acquire context.
     */
 				   acquire D
 				   /*
+				    * Add 'the top of held_locks -> D'
 				    * Push D to held_locks
 				    * Queue D in hist_locks
-				    * Add 'the top of held_locks -> D'
 				    *
 				    * In held_locks: A, D
 				    * In hist_locks: A, D
@@ -602,6 +603,7 @@ that the AX release context is different from the AX acquire context.
 				    */
    acquire E
    /*
+    * Add 'the top of held_locks -> E'
     * Push E to held_locks
     * Queue E in hist_locks
     *
@@ -629,6 +631,7 @@ that the AX release context is different from the AX acquire context.
    commit BX
    /*
     * Add 'BX -> ?'
+    * Answer the following to decide '?'
     * What has been queued since acquire BX: C, E
     *
     * In held_locks: Empty
@@ -657,12 +660,12 @@ that the AX release context is different from the AX acquire context.
    where A, BX, C,..., E are different lock classes and a suffix 'X' is
    added at crosslocks.
 
-Crossrelease considers all acquisitions after acquiring BX are
-candidates which might create dependencies with BX. True dependencies
-will be determined when identifying the release context of BX. Meanwhile,
+Crossrelease considers all acquisitions following acquiring BX because
+they can create dependencies with BX. The dependencies will be
+determined in the release context of BX. Meanwhile,
 all typical locks are queued so that they can be used at the commit step.
-And then two dependencies 'BX -> C' and 'BX -> E' are added at the
-commit step when identifying the release context.
+Finally, two dependencies 'BX -> C' and 'BX -> E' will be added at the
+commit step, when identifying the release context.
 
 The final graph will be, with crossrelease:
 
@@ -705,12 +708,12 @@ dependency chains, but this time it's for caching CT type dependencies.
 Once a dependency is cached, the same will never be added again.
 
 
-Lockless for hot paths
-----------------------
+Make hot paths lockless
+-----------------------
 
 To keep all locks for later use at the commit step, crossrelease adopts
-a local array embedded in task_struct, which makes access to the data
-lockless by forcing it to happen only within the owner context. It's
+a local array embedded in task_struct, which makes the data locklessly
+accessible by forcing it to happen only within the owner context. It's
 like how lockdep handles held_locks. Lockless implementation is important
 since typical locks are very frequently acquired and released.
 
@@ -723,10 +726,10 @@ A deadlock actually occurs when all waiters creating circular
 dependencies run at the same time. Even though they don't, a potential
 deadlock exists if the problematic dependencies exist. Thus, it's
 meaningful to detect not only an actual deadlock but also its potential
-possibility. The latter is rather valuable. When a deadlock occurs
-actually, we can identify what happens in the system by some means or
-other even without lockdep. However, there's no way to detect possibility
-without lockdep unless the whole code is parsed in the head. It's terrible.
+possibility. The latter is rather valuable. When a deadlock actually
+occurs, we can identify what happens in the system by some means or
+other even without lockdep. However, there's no way to detect a possibility
+without lockdep, unless the whole code is parsed in the head. It's terrible.
 Lockdep does the both, and crossrelease only focuses on the latter.
 
 Whether or not a deadlock actually occurs depends on several factors.
@@ -775,8 +778,8 @@ Remind what a dependency is. A dependency exists if:
 
 For example:
 
-   TASK X			   TASK Y
-   ------			   ------
+   CONTEXT X			   CONTEXT Y
+   ---------			   ---------
 				   acquire AX
    acquire B /* A dependency 'AX -> B' exists */
    release B
@@ -785,18 +788,18 @@ For example:
    where AX and B are different lock classes and a suffix 'X' is added
    at crosslocks.
 
-Even in this case involving crosslocks, the same rule can be applied. A
-dependency 'AX -> B' exists since:
+Here, a dependency 'AX -> B' exists since:
 
    1. A waiter for AX and a waiter for B might exist when acquiring B.
    2. The only way to wake up each is to release what it waits for.
    3. Whether the waiter for AX can be woken up depends on whether the
-      other can. IOW, TASK X cannot release AX if it fails to acquire B.
+      other can. In other words, CONTEXT X cannot release AX if it fails
+      to acquire B.
 
 Let's take a look at a more complicated example:
 
-   TASK X			   TASK Y
-   ------			   ------
+   CONTEXT X			   CONTEXT Y
+   ---------			   ---------
    acquire B
    release B
    fork Y
@@ -818,8 +821,8 @@ It would be ideal if the full set of true ones can be considered. But
 we can ensure nothing but what actually happened. Relying on what
 actually happens at runtime, we can anyway add only true ones, though
 they might be a subset of true ones. It's similar to how lockdep works
-for typical locks. There might be more true dependencies than what
-lockdep has detected at runtime. Lockdep has no choice but to rely on
+for typical locks. There might be more true dependencies than lockdep
+has detected. Lockdep has no choice but to rely on
 what actually happens. Crossrelease also relies on it.
 
 CONCLUSION
-- 
1.9.1

[PATCH v3 4/5] locking/Documentation: Add an example to help crossrelease.txt more readable

[Byungchul Park]

Add an example explaining the rationale that the limitation that old
lockdep implies, can be relaxed.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 Documentation/locking/crossrelease.txt | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

diff --git a/Documentation/locking/crossrelease.txt b/Documentation/locking/crossrelease.txt
index bb449e8..dac56f4 100644
--- a/Documentation/locking/crossrelease.txt
+++ b/Documentation/locking/crossrelease.txt
@@ -281,6 +281,29 @@ causes a deadlock. The more lockdep adds dependencies, the more it
 thoroughly works. Thus, lockdep has to do its best to detect and add as
 many true dependencies to the graph as possible.
 
+For example:
+
+   CONTEXT X			   CONTEXT Y
+   ---------			   ---------
+				   acquire A
+   acquire B /* A dependency 'A -> B' exists */
+   release B
+   release A held by Y
+
+   where A and B are different lock classes.
+
+In this case, a dependency 'A -> B' exists since:
+
+   1. A waiter for A and a waiter for B might exist when acquiring B.
+   2. The only way to wake up each is to release what it waits for.
+   3. Whether the waiter for A can be woken up depends on whether the
+      other can. In other words, CONTEXT X cannot release A if it fails
+      to acquire B.
+
+Considering only typical locks, lockdep builds nothing. However,
+relaxing the limitation, a dependency 'A -> B' can be added, giving us
+more chances to check circular dependencies.
+
 However, it might suffer performance degradation since
 relaxing the limitation, with which design and implementation of lockdep
 can be efficient, might introduce inefficiency inevitably. So lockdep
-- 
1.9.1

[PATCH v3 5/5] locking/Documentation: Align crossrelease.txt with the width

[Byungchul Park]

No change of contents at all. Only adjust the width.

(Please merge this to another after the review.)

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 Documentation/locking/crossrelease.txt | 59 +++++++++++++++++-----------------
 1 file changed, 30 insertions(+), 29 deletions(-)

diff --git a/Documentation/locking/crossrelease.txt b/Documentation/locking/crossrelease.txt
index dac56f4..c6d628b 100644
--- a/Documentation/locking/crossrelease.txt
+++ b/Documentation/locking/crossrelease.txt
@@ -61,9 +61,9 @@ turn cannot be triggered if event B does not happen, which in turn
 cannot be triggered if event C does not happen. After all, no event can
 be triggered since any of them never meets its condition to wake up.
 
-A dependency might exist between two waiters and a deadlock happens
-due to an incorrect relationship between dependencies. Thus, we must
-define what a dependency is first. A dependency exists if:
+A dependency might exist between two waiters and a deadlock happens due
+to an incorrect relationship between dependencies. Thus, we must define
+what a dependency is first. A dependency exists if:
 
    1. There are two waiters waiting for each event at a given time.
    2. The only way to wake up each waiter is to trigger its event.
@@ -304,10 +304,10 @@ Considering only typical locks, lockdep builds nothing. However,
 relaxing the limitation, a dependency 'A -> B' can be added, giving us
 more chances to check circular dependencies.
 
-However, it might suffer performance degradation since
-relaxing the limitation, with which design and implementation of lockdep
-can be efficient, might introduce inefficiency inevitably. So lockdep
-should provide two options, strong detection and efficient detection.
+However, it might suffer performance degradation since relaxing the
+limitation, with which design and implementation of lockdep can be
+efficient, might introduce inefficiency inevitably. So lockdep should
+provide two options, strong detection and efficient detection.
 
 Choosing efficient detection:
 
@@ -404,8 +404,8 @@ There are four types of dependencies:
 
    When acquiring BX, lockdep cannot identify the dependency because
    there's no way to know if it's in the AX's release context. It has
-   to wait until the decision can be made. Commit is necessary.
-   But, handling CC type is not implemented yet. It's a future work.
+   to wait until the decision can be made. Commit is necessary. But,
+   handling CC type is not implemented yet. It's a future work.
 
 Lockdep can work without commit for typical locks, but the step is
 necessary once crosslocks are involved. Introducing commit, lockdep
@@ -442,9 +442,9 @@ Crossrelease introduces two main data structures.
 
    This is an array embedded in task_struct, for keeping lock history so
    that dependencies can be added using them at the commit step. Since
-   they are local data, they can be accessed locklessly in the owner context.
-   The array is filled at the acquisition step and consumed at the
-   commit step. And it's managed in a circular manner.
+   they are local data, they can be accessed locklessly in the owner
+   context. The array is filled at the acquisition step and consumed at
+   the commit step. And it's managed in a circular manner.
 
 2. cross_lock
 
@@ -470,8 +470,8 @@ works for typical locks, without crossrelease.
 
    where A, B, and C are different lock classes.
 
-Lockdep adds 'the top of held_locks -> the lock to acquire'
-dependency every time acquiring a lock.
+Lockdep adds 'the top of held_locks -> the lock to acquire' dependency
+every time acquiring a lock.
 
 After adding 'A -> B', the dependency graph will be:
 
@@ -561,10 +561,10 @@ for A, B, and C, the graph will be:
    NOTE: A dependency 'A -> C' is optimized out.
 
 We can see the former graph built without the commit step is same as the
-latter graph. Of course, the former way leads to
-earlier finish for building the graph, which means we can detect a
-deadlock or its possibility sooner. So the former way would be preferred
-when possible. But we cannot avoid using the latter way for crosslocks.
+latter graph. Of course, the former way leads to earlier finish for
+building the graph, which means we can detect a deadlock or its
+possibility sooner. So the former way would be preferred when possible.
+But we cannot avoid using the latter way for crosslocks.
 
 Lastly, let's look at how commit works for crosslocks in practice.
 
@@ -685,10 +685,10 @@ Lastly, let's look at how commit works for crosslocks in practice.
 
 Crossrelease considers all acquisitions following acquiring BX because
 they can create dependencies with BX. The dependencies will be
-determined in the release context of BX. Meanwhile,
-all typical locks are queued so that they can be used at the commit step.
-Finally, two dependencies 'BX -> C' and 'BX -> E' will be added at the
-commit step, when identifying the release context.
+determined in the release context of BX. Meanwhile, all typical locks
+are queued so that they can be used at the commit step. Finally, two
+dependencies 'BX -> C' and 'BX -> E' will be added at the commit step,
+when identifying the release context.
 
 The final graph will be, with crossrelease:
 
@@ -737,8 +737,8 @@ Make hot paths lockless
 To keep all locks for later use at the commit step, crossrelease adopts
 a local array embedded in task_struct, which makes the data locklessly
 accessible by forcing it to happen only within the owner context. It's
-like how lockdep handles held_locks. Lockless implementation is important
-since typical locks are very frequently acquired and released.
+like how lockdep handles held_locks. Lockless implementation is
+important since typical locks are very frequently acquired and released.
 
 
 =================================================
@@ -751,9 +751,10 @@ deadlock exists if the problematic dependencies exist. Thus, it's
 meaningful to detect not only an actual deadlock but also its potential
 possibility. The latter is rather valuable. When a deadlock actually
 occurs, we can identify what happens in the system by some means or
-other even without lockdep. However, there's no way to detect a possibility
-without lockdep, unless the whole code is parsed in the head. It's terrible.
-Lockdep does the both, and crossrelease only focuses on the latter.
+other even without lockdep. However, there's no way to detect a
+possibility without lockdep, unless the whole code is parsed in the head.
+It's terrible. Lockdep does the both, and crossrelease only focuses on
+the latter.
 
 Whether or not a deadlock actually occurs depends on several factors.
 For example, what order contexts are switched in is a factor. Assuming
@@ -845,8 +846,8 @@ we can ensure nothing but what actually happened. Relying on what
 actually happens at runtime, we can anyway add only true ones, though
 they might be a subset of true ones. It's similar to how lockdep works
 for typical locks. There might be more true dependencies than lockdep
-has detected. Lockdep has no choice but to rely on
-what actually happens. Crossrelease also relies on it.
+has detected. Lockdep has no choice but to rely on what actually happens.
+Crossrelease also relies on it.
 
 CONCLUSION
 
-- 
1.9.1

[PATCH] locking/Documentation: Revise Documentation/locking/crossrelease.txt

[Byungchul Park]

Revise Documentation/locking/crossrelease.txt to improve its readability.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 Documentation/locking/crossrelease.txt | 329 ++++++++++++++++-----------------
 1 file changed, 155 insertions(+), 174 deletions(-)

diff --git a/Documentation/locking/crossrelease.txt b/Documentation/locking/crossrelease.txt
index bdf1423..c6d628b 100644
--- a/Documentation/locking/crossrelease.txt
+++ b/Documentation/locking/crossrelease.txt
@@ -12,10 +12,10 @@ Contents:
 
  (*) Limitation
 
-     - Limit lockdep
+     - Limiting lockdep
      - Pros from the limitation
      - Cons from the limitation
-     - Relax the limitation
+     - Relaxing the limitation
 
  (*) Crossrelease
 
@@ -30,9 +30,9 @@ Contents:
  (*) Optimizations
 
      - Avoid duplication
-     - Lockless for hot paths
+     - Make hot paths lockless
 
- (*) APPENDIX A: What lockdep does to work aggresively
+ (*) APPENDIX A: What lockdep does to work aggressively
 
  (*) APPENDIX B: How to avoid adding false dependencies
 
@@ -55,21 +55,21 @@ For example:
    A context going to trigger event A is waiting for event B to happen.
    A context going to trigger event B is waiting for event C to happen.
 
-A deadlock occurs when these three wait operations run at the same time,
+A deadlock occurs when these three waiters run at the same time,
 because event C cannot be triggered if event A does not happen, which in
 turn cannot be triggered if event B does not happen, which in turn
 cannot be triggered if event C does not happen. After all, no event can
 be triggered since any of them never meets its condition to wake up.
 
-A dependency might exist between two waiters and a deadlock might happen
-due to an incorrect releationship between dependencies. Thus, we must
-define what a dependency is first. A dependency exists between them if:
+A dependency might exist between two waiters and a deadlock happens due
+to an incorrect relationship between dependencies. Thus, we must define
+what a dependency is first. A dependency exists if:
 
    1. There are two waiters waiting for each event at a given time.
    2. The only way to wake up each waiter is to trigger its event.
    3. Whether one can be woken up depends on whether the other can.
 
-Each wait in the example creates its dependency like:
+Each waiter in the example creates its dependency like:
 
    Event C depends on event A.
    Event A depends on event B.
@@ -77,7 +77,7 @@ Each wait in the example creates its dependency like:
 
    NOTE: Precisely speaking, a dependency is one between whether a
    waiter for an event can be woken up and whether another waiter for
-   another event can be woken up. However from now on, we will describe
+   another event can be woken up. However, from now on, we will describe
    a dependency as if it's one between an event and another event for
    simplicity.
 
@@ -109,9 +109,9 @@ event in the previous section.
 In short, lockdep does:
 
    1. Detect a new dependency.
-   2. Add the dependency into a global graph.
+   2. Add the dependency to a global graph.
    3. Check if that makes dependencies circular.
-   4. Report a deadlock or its possibility if so.
+   4. Report the deadlock or its possibility if so.
 
 For example, consider a graph built by lockdep that looks like:
 
@@ -123,7 +123,7 @@ For example, consider a graph built by lockdep that looks like:
 
    where A, B,..., E are different lock classes.
 
-Lockdep will add a dependency into the graph on detection of a new
+Lockdep will add a dependency to the graph on detection of a new
 dependency. For example, it will add a dependency 'E -> C' when a new
 dependency between lock E and lock C is detected. Then the graph will be:
 
@@ -147,7 +147,7 @@ This graph contains a subgraph which demonstrates circular dependencies:
    \                  /
     ------------------
 
-   where C, D and E are different lock classes.
+   where C, D, and E are different lock classes.
 
 This is the condition under which a deadlock might occur. Lockdep
 reports it on detection after adding a new dependency. This is the way
@@ -163,13 +163,13 @@ dependencies were created after adding each new dependency.
 Limitation
 ==========
 
-Limit lockdep
--------------
+Limiting lockdep
+----------------
 
 Limiting lockdep to work on only typical locks e.g. spin locks and
-mutexes, which are released within the acquire context, the
+mutexes, which are released within their acquire contexts, the
 implementation becomes simple but its capacity for detection becomes
-limited. Let's check pros and cons in next section.
+limited. Let's check pros and cons in the next two sections.
 
 
 Pros from the limitation
@@ -179,7 +179,7 @@ Given the limitation, when acquiring a lock, locks in a held_locks
 cannot be released if the context cannot acquire it so has to wait to
 acquire it, which means all waiters for the locks in the held_locks are
 stuck. It's an exact case to create dependencies between each lock in
-the held_locks and the lock to acquire.
+the held_locks and the lock to acquire at the moment.
 
 For example:
 
@@ -195,22 +195,22 @@ For example:
 When acquiring lock A, the held_locks of CONTEXT X is empty thus no
 dependency is added. But when acquiring lock B, lockdep detects and adds
 a new dependency 'A -> B' between lock A in the held_locks and lock B.
-They can be simply added whenever acquiring each lock.
+Dependencies can be simply added this way, whenever acquiring each lock.
 
-And data required by lockdep exists in a local structure, held_locks
-embedded in task_struct. Forcing to access the data within the context,
-lockdep can avoid racy problems without explicit locks while handling
-the local data.
+Furthermore, since data required to create a dependency can be kept in
+local task_struct, lockdep can avoid racy problems without explicit
+protection by forcing to access the data within the context.
 
 Lastly, lockdep only needs to keep locks currently being held, to build
-a dependency graph. However, relaxing the limitation, it needs to keep
-even locks already released, because a decision whether they created
+the dependency graph. However, relaxing the limitation, it needs to keep
+even locks already released, because the decision whether they created
 dependencies might be long-deferred.
 
 To sum up, we can expect several advantages from the limitation:
 
    1. Lockdep can easily identify a dependency when acquiring a lock.
-   2. Races are avoidable while accessing local locks in a held_locks.
+   2. Races are avoidable without explicit protection while accessing
+      local locks in a held_locks.
    3. Lockdep only needs to keep locks currently being held.
 
 CONCLUSION
@@ -265,8 +265,8 @@ Given the limitation, lockdep cannot detect a deadlock or its
 possibility caused by page locks or completions.
 
 
-Relax the limitation
---------------------
+Relaxing the limitation
+-----------------------
 
 Under the limitation, things to create dependencies are limited to
 typical locks. However, synchronization primitives like page locks and
@@ -278,37 +278,36 @@ these locks to work with lockdep.
 Detecting dependencies is very important for lockdep to work because
 adding a dependency means adding an opportunity to check whether it
 causes a deadlock. The more lockdep adds dependencies, the more it
-thoroughly works. Thus Lockdep has to do its best to detect and add as
-many true dependencies into a graph as possible.
+thoroughly works. Thus, lockdep has to do its best to detect and add as
+many true dependencies to the graph as possible.
 
-For example, considering only typical locks, lockdep builds a graph like:
+For example:
 
-   A -> B -
-           \
-            -> E
-           /
-   C -> D -
+   CONTEXT X			   CONTEXT Y
+   ---------			   ---------
+				   acquire A
+   acquire B /* A dependency 'A -> B' exists */
+   release B
+   release A held by Y
 
-   where A, B,..., E are different lock classes.
+   where A and B are different lock classes.
 
-On the other hand, under the relaxation, additional dependencies might
-be created and added. Assuming additional 'FX -> C' and 'E -> GX' are
-added thanks to the relaxation, the graph will be:
+In this case, a dependency 'A -> B' exists since:
 
-         A -> B -
-                 \
-                  -> E -> GX
-                 /
-   FX -> C -> D -
+   1. A waiter for A and a waiter for B might exist when acquiring B.
+   2. The only way to wake up each is to release what it waits for.
+   3. Whether the waiter for A can be woken up depends on whether the
+      other can. In other words, CONTEXT X cannot release A if it fails
+      to acquire B.
 
-   where A, B,..., E, FX and GX are different lock classes, and a suffix
-   'X' is added on non-typical locks.
+Considering only typical locks, lockdep builds nothing. However,
+relaxing the limitation, a dependency 'A -> B' can be added, giving us
+more chances to check circular dependencies.
 
-The latter graph gives us more chances to check circular dependencies
-than the former. However, it might suffer performance degradation since
-relaxing the limitation, with which design and implementation of lockdep
-can be efficient, might introduce inefficiency inevitably. So lockdep
-should provide two options, strong detection and efficient detection.
+However, it might suffer performance degradation since relaxing the
+limitation, with which design and implementation of lockdep can be
+efficient, might introduce inefficiency inevitably. So lockdep should
+provide two options, strong detection and efficient detection.
 
 Choosing efficient detection:
 
@@ -336,27 +335,27 @@ Introduce crossrelease
 In order to allow lockdep to handle additional dependencies by what
 might be released in any context, namely 'crosslock', we have to be able
 to identify those created by crosslocks. The proposed 'crossrelease'
-feature provoides a way to do that.
+feature provides a way to do that.
 
 Crossrelease feature has to do:
 
    1. Identify dependencies created by crosslocks.
-   2. Add the dependencies into a dependency graph.
+   2. Add the dependencies to the dependency graph.
 
-That's all. Once a meaningful dependency is added into graph, then
+That's all. Once a meaningful dependency is added to the graph, then
 lockdep would work with the graph as it did. The most important thing
 crossrelease feature has to do is to correctly identify and add true
-dependencies into the global graph.
+dependencies to the global graph.
 
 A dependency e.g. 'A -> B' can be identified only in the A's release
 context because a decision required to identify the dependency can be
 made only in the release context. That is to decide whether A can be
-released so that a waiter for A can be woken up. It cannot be made in
+released so that waiters for A can be woken up. That cannot be made in
 other than the A's release context.
 
 It's no matter for typical locks because each acquire context is same as
 its release context, thus lockdep can decide whether a lock can be
-released in the acquire context. However for crosslocks, lockdep cannot
+released in the acquire context. However, for crosslocks, lockdep cannot
 make the decision in the acquire context but has to wait until the
 release context is identified.
 
@@ -375,10 +374,11 @@ Introduce commit
 ----------------
 
 Since crossrelease defers the work adding true dependencies of
-crosslocks until they are actually released, crossrelease has to queue
+crosslocks until they are eventually released, crossrelease has to queue
 all acquisitions which might create dependencies with the crosslocks.
-Then it identifies dependencies using the queued data in batches at a
-proper time. We call it 'commit'.
+Then lockdep can identify dependencies using the queued data in batches
+at a proper time. We call the step adding true dependencies to the graph
+in batches, 'commit'.
 
 There are four types of dependencies:
 
@@ -404,10 +404,10 @@ There are four types of dependencies:
 
    When acquiring BX, lockdep cannot identify the dependency because
    there's no way to know if it's in the AX's release context. It has
-   to wait until the decision can be made. Commit is necessary.
-   But, handling CC type is not implemented yet. It's a future work.
+   to wait until the decision can be made. Commit is necessary. But,
+   handling CC type is not implemented yet. It's a future work.
 
-Lockdep can work without commit for typical locks, but commit step is
+Lockdep can work without commit for typical locks, but the step is
 necessary once crosslocks are involved. Introducing commit, lockdep
 performs three steps. What lockdep does in each step is:
 
@@ -416,7 +416,7 @@ performs three steps. What lockdep does in each step is:
    it at the commit step. For crosslocks, it saves data which will be
    used at the commit step and increases a reference count for it.
 
-2. Commit: No action is reauired for typical locks. For crosslocks,
+2. Commit: No action is required for typical locks. For crosslocks,
    lockdep adds CT type dependencies using the data saved at the
    acquisition step.
 
@@ -442,9 +442,9 @@ Crossrelease introduces two main data structures.
 
    This is an array embedded in task_struct, for keeping lock history so
    that dependencies can be added using them at the commit step. Since
-   it's local data, it can be accessed locklessly in the owner context.
-   The array is filled at the acquisition step and consumed at the
-   commit step. And it's managed in circular manner.
+   they are local data, they can be accessed locklessly in the owner
+   context. The array is filled at the acquisition step and consumed at
+   the commit step. And it's managed in a circular manner.
 
 2. cross_lock
 
@@ -456,29 +456,24 @@ How crossrelease works
 ----------------------
 
 It's the key of how crossrelease works, to defer necessary works to an
-appropriate point in time and perform in at once at the commit step.
-Let's take a look with examples step by step, starting from how lockdep
-works without crossrelease for typical locks.
+appropriate point in time and perform the works at the commit step.
+
+Let's take a look at examples step by step, starting from how lockdep
+works for typical locks, without crossrelease.
 
-   acquire A /* Push A onto held_locks */
-   acquire B /* Push B onto held_locks and add 'A -> B' */
-   acquire C /* Push C onto held_locks and add 'B -> C' */
+   acquire A /* Push A to held_locks */
+   acquire B /* Push B to held_locks and add 'A -> B' */
+   acquire C /* Push C to held_locks and add 'B -> C' */
    release C /* Pop C from held_locks */
    release B /* Pop B from held_locks */
    release A /* Pop A from held_locks */
 
-   where A, B and C are different lock classes.
+   where A, B, and C are different lock classes.
 
-   NOTE: This document assumes that readers already understand how
-   lockdep works without crossrelease thus omits details. But there's
-   one thing to note. Lockdep pretends to pop a lock from held_locks
-   when releasing it. But it's subtly different from the original pop
-   operation because lockdep allows other than the top to be poped.
+Lockdep adds 'the top of held_locks -> the lock to acquire' dependency
+every time acquiring a lock.
 
-In this case, lockdep adds 'the top of held_locks -> the lock to acquire'
-dependency every time acquiring a lock.
-
-After adding 'A -> B', a dependency graph will be:
+After adding 'A -> B', the dependency graph will be:
 
    A -> B
 
@@ -488,15 +483,15 @@ And after adding 'B -> C', the graph will be:
 
    A -> B -> C
 
-   where A, B and C are different lock classes.
+   where A, B, and C are different lock classes.
 
-Let's performs commit step even for typical locks to add dependencies.
-Of course, commit step is not necessary for them, however, it would work
-well because this is a more general way.
+Let's build the graph using the commit step with the same example. Of
+course, the step is not necessary for typical locks, however, it would
+also work because this is a more general way.
 
    acquire A
    /*
-    * Queue A into hist_locks
+    * Queue A in hist_locks
     *
     * In hist_locks: A
     * In graph: Empty
@@ -504,7 +499,7 @@ well because this is a more general way.
 
    acquire B
    /*
-    * Queue B into hist_locks
+    * Queue B in hist_locks
     *
     * In hist_locks: A, B
     * In graph: Empty
@@ -512,7 +507,7 @@ well because this is a more general way.
 
    acquire C
    /*
-    * Queue C into hist_locks
+    * Queue C in hist_locks
     *
     * In hist_locks: A, B, C
     * In graph: Empty
@@ -554,34 +549,32 @@ well because this is a more general way.
 
    release A
 
-   where A, B and C are different lock classes.
-
-In this case, dependencies are added at the commit step as described.
+   where A, B, and C are different lock classes.
 
-After commits for A, B and C, the graph will be:
+Dependencies are added at the commit step as described. After commits
+for A, B, and C, the graph will be:
 
    A -> B -> C
 
-   where A, B and C are different lock classes.
+   where A, B, and C are different lock classes.
 
    NOTE: A dependency 'A -> C' is optimized out.
 
-We can see the former graph built without commit step is same as the
-latter graph built using commit steps. Of course the former way leads to
-earlier finish for building the graph, which means we can detect a
-deadlock or its possibility sooner. So the former way would be prefered
-when possible. But we cannot avoid using the latter way for crosslocks.
+We can see the former graph built without the commit step is same as the
+latter graph. Of course, the former way leads to earlier finish for
+building the graph, which means we can detect a deadlock or its
+possibility sooner. So the former way would be preferred when possible.
+But we cannot avoid using the latter way for crosslocks.
 
-Let's look at how commit steps work for crosslocks. In this case, the
-commit step is performed only on crosslock AX as real. And it assumes
-that the AX release context is different from the AX acquire context.
+Lastly, let's look at how commit works for crosslocks in practice.
 
    BX RELEASE CONTEXT		   BX ACQUIRE CONTEXT
    ------------------		   ------------------
 				   acquire A
 				   /*
-				    * Push A onto held_locks
-				    * Queue A into hist_locks
+				    * Add 'the top of held_locks -> A'
+				    * Push A to held_locks
+				    * Queue A in hist_locks
 				    *
 				    * In held_locks: A
 				    * In hist_locks: A
@@ -604,8 +597,9 @@ that the AX release context is different from the AX acquire context.
 
    acquire C
    /*
-    * Push C onto held_locks
-    * Queue C into hist_locks
+    * Add 'the top of held_locks -> C'
+    * Push C to held_locks
+    * Queue C in hist_locks
     *
     * In held_locks: C
     * In hist_locks: C
@@ -622,9 +616,9 @@ that the AX release context is different from the AX acquire context.
     */
 				   acquire D
 				   /*
-				    * Push D onto held_locks
-				    * Queue D into hist_locks
 				    * Add 'the top of held_locks -> D'
+				    * Push D to held_locks
+				    * Queue D in hist_locks
 				    *
 				    * In held_locks: A, D
 				    * In hist_locks: A, D
@@ -632,8 +626,9 @@ that the AX release context is different from the AX acquire context.
 				    */
    acquire E
    /*
-    * Push E onto held_locks
-    * Queue E into hist_locks
+    * Add 'the top of held_locks -> E'
+    * Push E to held_locks
+    * Queue E in hist_locks
     *
     * In held_locks: E
     * In hist_locks: C, E
@@ -659,6 +654,7 @@ that the AX release context is different from the AX acquire context.
    commit BX
    /*
     * Add 'BX -> ?'
+    * Answer the following to decide '?'
     * What has been queued since acquire BX: C, E
     *
     * In held_locks: Empty
@@ -684,15 +680,15 @@ that the AX release context is different from the AX acquire context.
 				    *           'BX -> C', 'BX -> E'
 				    */
 
-   where A, BX, C,..., E are different lock classes, and a suffix 'X' is
-   added on crosslocks.
+   where A, BX, C,..., E are different lock classes and a suffix 'X' is
+   added at crosslocks.
 
-Crossrelease considers all acquisitions after acqiuring BX are
-candidates which might create dependencies with BX. True dependencies
-will be determined when identifying the release context of BX. Meanwhile,
-all typical locks are queued so that they can be used at the commit step.
-And then two dependencies 'BX -> C' and 'BX -> E' are added at the
-commit step when identifying the release context.
+Crossrelease considers all acquisitions following acquiring BX because
+they can create dependencies with BX. The dependencies will be
+determined in the release context of BX. Meanwhile, all typical locks
+are queued so that they can be used at the commit step. Finally, two
+dependencies 'BX -> C' and 'BX -> E' will be added at the commit step,
+when identifying the release context.
 
 The final graph will be, with crossrelease:
 
@@ -704,8 +700,8 @@ The final graph will be, with crossrelease:
       \
        -> D
 
-   where A, BX, C,..., E are different lock classes, and a suffix 'X' is
-   added on crosslocks.
+   where A, BX, C,..., E are different lock classes and a suffix 'X' is
+   added at crosslocks.
 
 However, the final graph will be, without crossrelease:
 
@@ -732,39 +728,40 @@ Avoid duplication
 
 Crossrelease feature uses a cache like what lockdep already uses for
 dependency chains, but this time it's for caching CT type dependencies.
-Once that dependency is cached, the same will never be added again.
+Once a dependency is cached, the same will never be added again.
 
 
-Lockless for hot paths
-----------------------
+Make hot paths lockless
+-----------------------
 
 To keep all locks for later use at the commit step, crossrelease adopts
-a local array embedded in task_struct, which makes access to the data
-lockless by forcing it to happen only within the owner context. It's
-like how lockdep handles held_locks. Lockless implmentation is important
-since typical locks are very frequently acquired and released.
+a local array embedded in task_struct, which makes the data locklessly
+accessible by forcing it to happen only within the owner context. It's
+like how lockdep handles held_locks. Lockless implementation is
+important since typical locks are very frequently acquired and released.
 
 
 =================================================
 APPENDIX A: What lockdep does to work aggresively
 =================================================
 
-A deadlock actually occurs when all wait operations creating circular
+A deadlock actually occurs when all waiters creating circular
 dependencies run at the same time. Even though they don't, a potential
-deadlock exists if the problematic dependencies exist. Thus it's
+deadlock exists if the problematic dependencies exist. Thus, it's
 meaningful to detect not only an actual deadlock but also its potential
-possibility. The latter is rather valuable. When a deadlock occurs
-actually, we can identify what happens in the system by some means or
-other even without lockdep. However, there's no way to detect possiblity
-without lockdep unless the whole code is parsed in head. It's terrible.
-Lockdep does the both, and crossrelease only focuses on the latter.
+possibility. The latter is rather valuable. When a deadlock actually
+occurs, we can identify what happens in the system by some means or
+other even without lockdep. However, there's no way to detect a
+possibility without lockdep, unless the whole code is parsed in the head.
+It's terrible. Lockdep does the both, and crossrelease only focuses on
+the latter.
 
 Whether or not a deadlock actually occurs depends on several factors.
 For example, what order contexts are switched in is a factor. Assuming
 circular dependencies exist, a deadlock would occur when contexts are
-switched so that all wait operations creating the dependencies run
-simultaneously. Thus to detect a deadlock possibility even in the case
-that it has not occured yet, lockdep should consider all possible
+switched so that all waiters creating the dependencies run
+simultaneously. Thus, to detect a deadlock possibility even in the case
+that it has not occurred yet, lockdep should consider all possible
 combinations of dependencies, trying to:
 
 1. Use a global dependency graph.
@@ -776,7 +773,7 @@ combinations of dependencies, trying to:
 
 2. Check dependencies between classes instead of instances.
 
-   What actually causes a deadlock are instances of lock. However,
+   What actually causes a deadlock are instances of locks. However,
    lockdep checks dependencies between classes instead of instances.
    This way lockdep can detect a deadlock which has not happened but
    might happen in future by others but the same class.
@@ -805,44 +802,28 @@ Remind what a dependency is. A dependency exists if:
 
 For example:
 
-   acquire A
-   acquire B /* A dependency 'A -> B' exists */
-   release B
-   release A
-
-   where A and B are different lock classes.
-
-A depedency 'A -> B' exists since:
-
-   1. A waiter for A and a waiter for B might exist when acquiring B.
-   2. Only way to wake up each is to release what it waits for.
-   3. Whether the waiter for A can be woken up depends on whether the
-      other can. IOW, TASK X cannot release A if it fails to acquire B.
-
-For another example:
-
-   TASK X			   TASK Y
-   ------			   ------
+   CONTEXT X			   CONTEXT Y
+   ---------			   ---------
 				   acquire AX
    acquire B /* A dependency 'AX -> B' exists */
    release B
    release AX held by Y
 
-   where AX and B are different lock classes, and a suffix 'X' is added
-   on crosslocks.
+   where AX and B are different lock classes and a suffix 'X' is added
+   at crosslocks.
 
-Even in this case involving crosslocks, the same rule can be applied. A
-depedency 'AX -> B' exists since:
+Here, a dependency 'AX -> B' exists since:
 
    1. A waiter for AX and a waiter for B might exist when acquiring B.
-   2. Only way to wake up each is to release what it waits for.
+   2. The only way to wake up each is to release what it waits for.
    3. Whether the waiter for AX can be woken up depends on whether the
-      other can. IOW, TASK X cannot release AX if it fails to acquire B.
+      other can. In other words, CONTEXT X cannot release AX if it fails
+      to acquire B.
 
-Let's take a look at more complicated example:
+Let's take a look at a more complicated example:
 
-   TASK X			   TASK Y
-   ------			   ------
+   CONTEXT X			   CONTEXT Y
+   ---------			   ---------
    acquire B
    release B
    fork Y
@@ -851,22 +832,22 @@ Let's take a look at more complicated example:
    release C
    release AX held by Y
 
-   where AX, B and C are different lock classes, and a suffix 'X' is
-   added on crosslocks.
+   where AX, B, and C are different lock classes and a suffix 'X' is
+   added at crosslocks.
 
 Does a dependency 'AX -> B' exist? Nope.
 
 Two waiters are essential to create a dependency. However, waiters for
 AX and B to create 'AX -> B' cannot exist at the same time in this
-example. Thus the dependency 'AX -> B' cannot be created.
+example. Thus, the dependency 'AX -> B' cannot be created.
 
 It would be ideal if the full set of true ones can be considered. But
 we can ensure nothing but what actually happened. Relying on what
 actually happens at runtime, we can anyway add only true ones, though
 they might be a subset of true ones. It's similar to how lockdep works
-for typical locks. There might be more true dependencies than what
-lockdep has detected in runtime. Lockdep has no choice but to rely on
-what actually happens. Crossrelease also relies on it.
+for typical locks. There might be more true dependencies than lockdep
+has detected. Lockdep has no choice but to rely on what actually happens.
+Crossrelease also relies on it.
 
 CONCLUSION
 
-- 
1.9.1

Re: [PATCH] locking/Documentation: Revise Documentation/locking/crossrelease.txt

[Byungchul Park]

This is the big one including all of version 3.

You can take only this.

Thanks,
Byungchul

On Sat, Nov 11, 2017 at 10:33:34PM +0900, Byungchul Park wrote:
> Revise Documentation/locking/crossrelease.txt to improve its readability.
> 
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
>  Documentation/locking/crossrelease.txt | 329 ++++++++++++++++-----------------
>  1 file changed, 155 insertions(+), 174 deletions(-)
> 
> diff --git a/Documentation/locking/crossrelease.txt b/Documentation/locking/crossrelease.txt
> index bdf1423..c6d628b 100644
> --- a/Documentation/locking/crossrelease.txt
> +++ b/Documentation/locking/crossrelease.txt
> @@ -12,10 +12,10 @@ Contents:
>  
>   (*) Limitation
>  
> -     - Limit lockdep
> +     - Limiting lockdep
>       - Pros from the limitation
>       - Cons from the limitation
> -     - Relax the limitation
> +     - Relaxing the limitation
>  
>   (*) Crossrelease
>  
> @@ -30,9 +30,9 @@ Contents:
>   (*) Optimizations
>  
>       - Avoid duplication
> -     - Lockless for hot paths
> +     - Make hot paths lockless
>  
> - (*) APPENDIX A: What lockdep does to work aggresively
> + (*) APPENDIX A: What lockdep does to work aggressively
>  
>   (*) APPENDIX B: How to avoid adding false dependencies
>  
> @@ -55,21 +55,21 @@ For example:
>     A context going to trigger event A is waiting for event B to happen.
>     A context going to trigger event B is waiting for event C to happen.
>  
> -A deadlock occurs when these three wait operations run at the same time,
> +A deadlock occurs when these three waiters run at the same time,
>  because event C cannot be triggered if event A does not happen, which in
>  turn cannot be triggered if event B does not happen, which in turn
>  cannot be triggered if event C does not happen. After all, no event can
>  be triggered since any of them never meets its condition to wake up.
>  
> -A dependency might exist between two waiters and a deadlock might happen
> -due to an incorrect releationship between dependencies. Thus, we must
> -define what a dependency is first. A dependency exists between them if:
> +A dependency might exist between two waiters and a deadlock happens due
> +to an incorrect relationship between dependencies. Thus, we must define
> +what a dependency is first. A dependency exists if:
>  
>     1. There are two waiters waiting for each event at a given time.
>     2. The only way to wake up each waiter is to trigger its event.
>     3. Whether one can be woken up depends on whether the other can.
>  
> -Each wait in the example creates its dependency like:
> +Each waiter in the example creates its dependency like:
>  
>     Event C depends on event A.
>     Event A depends on event B.
> @@ -77,7 +77,7 @@ Each wait in the example creates its dependency like:
>  
>     NOTE: Precisely speaking, a dependency is one between whether a
>     waiter for an event can be woken up and whether another waiter for
> -   another event can be woken up. However from now on, we will describe
> +   another event can be woken up. However, from now on, we will describe
>     a dependency as if it's one between an event and another event for
>     simplicity.
>  
> @@ -109,9 +109,9 @@ event in the previous section.
>  In short, lockdep does:
>  
>     1. Detect a new dependency.
> -   2. Add the dependency into a global graph.
> +   2. Add the dependency to a global graph.
>     3. Check if that makes dependencies circular.
> -   4. Report a deadlock or its possibility if so.
> +   4. Report the deadlock or its possibility if so.
>  
>  For example, consider a graph built by lockdep that looks like:
>  
> @@ -123,7 +123,7 @@ For example, consider a graph built by lockdep that looks like:
>  
>     where A, B,..., E are different lock classes.
>  
> -Lockdep will add a dependency into the graph on detection of a new
> +Lockdep will add a dependency to the graph on detection of a new
>  dependency. For example, it will add a dependency 'E -> C' when a new
>  dependency between lock E and lock C is detected. Then the graph will be:
>  
> @@ -147,7 +147,7 @@ This graph contains a subgraph which demonstrates circular dependencies:
>     \                  /
>      ------------------
>  
> -   where C, D and E are different lock classes.
> +   where C, D, and E are different lock classes.
>  
>  This is the condition under which a deadlock might occur. Lockdep
>  reports it on detection after adding a new dependency. This is the way
> @@ -163,13 +163,13 @@ dependencies were created after adding each new dependency.
>  Limitation
>  ==========
>  
> -Limit lockdep
> --------------
> +Limiting lockdep
> +----------------
>  
>  Limiting lockdep to work on only typical locks e.g. spin locks and
> -mutexes, which are released within the acquire context, the
> +mutexes, which are released within their acquire contexts, the
>  implementation becomes simple but its capacity for detection becomes
> -limited. Let's check pros and cons in next section.
> +limited. Let's check pros and cons in the next two sections.
>  
>  
>  Pros from the limitation
> @@ -179,7 +179,7 @@ Given the limitation, when acquiring a lock, locks in a held_locks
>  cannot be released if the context cannot acquire it so has to wait to
>  acquire it, which means all waiters for the locks in the held_locks are
>  stuck. It's an exact case to create dependencies between each lock in
> -the held_locks and the lock to acquire.
> +the held_locks and the lock to acquire at the moment.
>  
>  For example:
>  
> @@ -195,22 +195,22 @@ For example:
>  When acquiring lock A, the held_locks of CONTEXT X is empty thus no
>  dependency is added. But when acquiring lock B, lockdep detects and adds
>  a new dependency 'A -> B' between lock A in the held_locks and lock B.
> -They can be simply added whenever acquiring each lock.
> +Dependencies can be simply added this way, whenever acquiring each lock.
>  
> -And data required by lockdep exists in a local structure, held_locks
> -embedded in task_struct. Forcing to access the data within the context,
> -lockdep can avoid racy problems without explicit locks while handling
> -the local data.
> +Furthermore, since data required to create a dependency can be kept in
> +local task_struct, lockdep can avoid racy problems without explicit
> +protection by forcing to access the data within the context.
>  
>  Lastly, lockdep only needs to keep locks currently being held, to build
> -a dependency graph. However, relaxing the limitation, it needs to keep
> -even locks already released, because a decision whether they created
> +the dependency graph. However, relaxing the limitation, it needs to keep
> +even locks already released, because the decision whether they created
>  dependencies might be long-deferred.
>  
>  To sum up, we can expect several advantages from the limitation:
>  
>     1. Lockdep can easily identify a dependency when acquiring a lock.
> -   2. Races are avoidable while accessing local locks in a held_locks.
> +   2. Races are avoidable without explicit protection while accessing
> +      local locks in a held_locks.
>     3. Lockdep only needs to keep locks currently being held.
>  
>  CONCLUSION
> @@ -265,8 +265,8 @@ Given the limitation, lockdep cannot detect a deadlock or its
>  possibility caused by page locks or completions.
>  
>  
> -Relax the limitation
> ---------------------
> +Relaxing the limitation
> +-----------------------
>  
>  Under the limitation, things to create dependencies are limited to
>  typical locks. However, synchronization primitives like page locks and
> @@ -278,37 +278,36 @@ these locks to work with lockdep.
>  Detecting dependencies is very important for lockdep to work because
>  adding a dependency means adding an opportunity to check whether it
>  causes a deadlock. The more lockdep adds dependencies, the more it
> -thoroughly works. Thus Lockdep has to do its best to detect and add as
> -many true dependencies into a graph as possible.
> +thoroughly works. Thus, lockdep has to do its best to detect and add as
> +many true dependencies to the graph as possible.
>  
> -For example, considering only typical locks, lockdep builds a graph like:
> +For example:
>  
> -   A -> B -
> -           \
> -            -> E
> -           /
> -   C -> D -
> +   CONTEXT X			   CONTEXT Y
> +   ---------			   ---------
> +				   acquire A
> +   acquire B /* A dependency 'A -> B' exists */
> +   release B
> +   release A held by Y
>  
> -   where A, B,..., E are different lock classes.
> +   where A and B are different lock classes.
>  
> -On the other hand, under the relaxation, additional dependencies might
> -be created and added. Assuming additional 'FX -> C' and 'E -> GX' are
> -added thanks to the relaxation, the graph will be:
> +In this case, a dependency 'A -> B' exists since:
>  
> -         A -> B -
> -                 \
> -                  -> E -> GX
> -                 /
> -   FX -> C -> D -
> +   1. A waiter for A and a waiter for B might exist when acquiring B.
> +   2. The only way to wake up each is to release what it waits for.
> +   3. Whether the waiter for A can be woken up depends on whether the
> +      other can. In other words, CONTEXT X cannot release A if it fails
> +      to acquire B.
>  
> -   where A, B,..., E, FX and GX are different lock classes, and a suffix
> -   'X' is added on non-typical locks.
> +Considering only typical locks, lockdep builds nothing. However,
> +relaxing the limitation, a dependency 'A -> B' can be added, giving us
> +more chances to check circular dependencies.
>  
> -The latter graph gives us more chances to check circular dependencies
> -than the former. However, it might suffer performance degradation since
> -relaxing the limitation, with which design and implementation of lockdep
> -can be efficient, might introduce inefficiency inevitably. So lockdep
> -should provide two options, strong detection and efficient detection.
> +However, it might suffer performance degradation since relaxing the
> +limitation, with which design and implementation of lockdep can be
> +efficient, might introduce inefficiency inevitably. So lockdep should
> +provide two options, strong detection and efficient detection.
>  
>  Choosing efficient detection:
>  
> @@ -336,27 +335,27 @@ Introduce crossrelease
>  In order to allow lockdep to handle additional dependencies by what
>  might be released in any context, namely 'crosslock', we have to be able
>  to identify those created by crosslocks. The proposed 'crossrelease'
> -feature provoides a way to do that.
> +feature provides a way to do that.
>  
>  Crossrelease feature has to do:
>  
>     1. Identify dependencies created by crosslocks.
> -   2. Add the dependencies into a dependency graph.
> +   2. Add the dependencies to the dependency graph.
>  
> -That's all. Once a meaningful dependency is added into graph, then
> +That's all. Once a meaningful dependency is added to the graph, then
>  lockdep would work with the graph as it did. The most important thing
>  crossrelease feature has to do is to correctly identify and add true
> -dependencies into the global graph.
> +dependencies to the global graph.
>  
>  A dependency e.g. 'A -> B' can be identified only in the A's release
>  context because a decision required to identify the dependency can be
>  made only in the release context. That is to decide whether A can be
> -released so that a waiter for A can be woken up. It cannot be made in
> +released so that waiters for A can be woken up. That cannot be made in
>  other than the A's release context.
>  
>  It's no matter for typical locks because each acquire context is same as
>  its release context, thus lockdep can decide whether a lock can be
> -released in the acquire context. However for crosslocks, lockdep cannot
> +released in the acquire context. However, for crosslocks, lockdep cannot
>  make the decision in the acquire context but has to wait until the
>  release context is identified.
>  
> @@ -375,10 +374,11 @@ Introduce commit
>  ----------------
>  
>  Since crossrelease defers the work adding true dependencies of
> -crosslocks until they are actually released, crossrelease has to queue
> +crosslocks until they are eventually released, crossrelease has to queue
>  all acquisitions which might create dependencies with the crosslocks.
> -Then it identifies dependencies using the queued data in batches at a
> -proper time. We call it 'commit'.
> +Then lockdep can identify dependencies using the queued data in batches
> +at a proper time. We call the step adding true dependencies to the graph
> +in batches, 'commit'.
>  
>  There are four types of dependencies:
>  
> @@ -404,10 +404,10 @@ There are four types of dependencies:
>  
>     When acquiring BX, lockdep cannot identify the dependency because
>     there's no way to know if it's in the AX's release context. It has
> -   to wait until the decision can be made. Commit is necessary.
> -   But, handling CC type is not implemented yet. It's a future work.
> +   to wait until the decision can be made. Commit is necessary. But,
> +   handling CC type is not implemented yet. It's a future work.
>  
> -Lockdep can work without commit for typical locks, but commit step is
> +Lockdep can work without commit for typical locks, but the step is
>  necessary once crosslocks are involved. Introducing commit, lockdep
>  performs three steps. What lockdep does in each step is:
>  
> @@ -416,7 +416,7 @@ performs three steps. What lockdep does in each step is:
>     it at the commit step. For crosslocks, it saves data which will be
>     used at the commit step and increases a reference count for it.
>  
> -2. Commit: No action is reauired for typical locks. For crosslocks,
> +2. Commit: No action is required for typical locks. For crosslocks,
>     lockdep adds CT type dependencies using the data saved at the
>     acquisition step.
>  
> @@ -442,9 +442,9 @@ Crossrelease introduces two main data structures.
>  
>     This is an array embedded in task_struct, for keeping lock history so
>     that dependencies can be added using them at the commit step. Since
> -   it's local data, it can be accessed locklessly in the owner context.
> -   The array is filled at the acquisition step and consumed at the
> -   commit step. And it's managed in circular manner.
> +   they are local data, they can be accessed locklessly in the owner
> +   context. The array is filled at the acquisition step and consumed at
> +   the commit step. And it's managed in a circular manner.
>  
>  2. cross_lock
>  
> @@ -456,29 +456,24 @@ How crossrelease works
>  ----------------------
>  
>  It's the key of how crossrelease works, to defer necessary works to an
> -appropriate point in time and perform in at once at the commit step.
> -Let's take a look with examples step by step, starting from how lockdep
> -works without crossrelease for typical locks.
> +appropriate point in time and perform the works at the commit step.
> +
> +Let's take a look at examples step by step, starting from how lockdep
> +works for typical locks, without crossrelease.
>  
> -   acquire A /* Push A onto held_locks */
> -   acquire B /* Push B onto held_locks and add 'A -> B' */
> -   acquire C /* Push C onto held_locks and add 'B -> C' */
> +   acquire A /* Push A to held_locks */
> +   acquire B /* Push B to held_locks and add 'A -> B' */
> +   acquire C /* Push C to held_locks and add 'B -> C' */
>     release C /* Pop C from held_locks */
>     release B /* Pop B from held_locks */
>     release A /* Pop A from held_locks */
>  
> -   where A, B and C are different lock classes.
> +   where A, B, and C are different lock classes.
>  
> -   NOTE: This document assumes that readers already understand how
> -   lockdep works without crossrelease thus omits details. But there's
> -   one thing to note. Lockdep pretends to pop a lock from held_locks
> -   when releasing it. But it's subtly different from the original pop
> -   operation because lockdep allows other than the top to be poped.
> +Lockdep adds 'the top of held_locks -> the lock to acquire' dependency
> +every time acquiring a lock.
>  
> -In this case, lockdep adds 'the top of held_locks -> the lock to acquire'
> -dependency every time acquiring a lock.
> -
> -After adding 'A -> B', a dependency graph will be:
> +After adding 'A -> B', the dependency graph will be:
>  
>     A -> B
>  
> @@ -488,15 +483,15 @@ And after adding 'B -> C', the graph will be:
>  
>     A -> B -> C
>  
> -   where A, B and C are different lock classes.
> +   where A, B, and C are different lock classes.
>  
> -Let's performs commit step even for typical locks to add dependencies.
> -Of course, commit step is not necessary for them, however, it would work
> -well because this is a more general way.
> +Let's build the graph using the commit step with the same example. Of
> +course, the step is not necessary for typical locks, however, it would
> +also work because this is a more general way.
>  
>     acquire A
>     /*
> -    * Queue A into hist_locks
> +    * Queue A in hist_locks
>      *
>      * In hist_locks: A
>      * In graph: Empty
> @@ -504,7 +499,7 @@ well because this is a more general way.
>  
>     acquire B
>     /*
> -    * Queue B into hist_locks
> +    * Queue B in hist_locks
>      *
>      * In hist_locks: A, B
>      * In graph: Empty
> @@ -512,7 +507,7 @@ well because this is a more general way.
>  
>     acquire C
>     /*
> -    * Queue C into hist_locks
> +    * Queue C in hist_locks
>      *
>      * In hist_locks: A, B, C
>      * In graph: Empty
> @@ -554,34 +549,32 @@ well because this is a more general way.
>  
>     release A
>  
> -   where A, B and C are different lock classes.
> -
> -In this case, dependencies are added at the commit step as described.
> +   where A, B, and C are different lock classes.
>  
> -After commits for A, B and C, the graph will be:
> +Dependencies are added at the commit step as described. After commits
> +for A, B, and C, the graph will be:
>  
>     A -> B -> C
>  
> -   where A, B and C are different lock classes.
> +   where A, B, and C are different lock classes.
>  
>     NOTE: A dependency 'A -> C' is optimized out.
>  
> -We can see the former graph built without commit step is same as the
> -latter graph built using commit steps. Of course the former way leads to
> -earlier finish for building the graph, which means we can detect a
> -deadlock or its possibility sooner. So the former way would be prefered
> -when possible. But we cannot avoid using the latter way for crosslocks.
> +We can see the former graph built without the commit step is same as the
> +latter graph. Of course, the former way leads to earlier finish for
> +building the graph, which means we can detect a deadlock or its
> +possibility sooner. So the former way would be preferred when possible.
> +But we cannot avoid using the latter way for crosslocks.
>  
> -Let's look at how commit steps work for crosslocks. In this case, the
> -commit step is performed only on crosslock AX as real. And it assumes
> -that the AX release context is different from the AX acquire context.
> +Lastly, let's look at how commit works for crosslocks in practice.
>  
>     BX RELEASE CONTEXT		   BX ACQUIRE CONTEXT
>     ------------------		   ------------------
>  				   acquire A
>  				   /*
> -				    * Push A onto held_locks
> -				    * Queue A into hist_locks
> +				    * Add 'the top of held_locks -> A'
> +				    * Push A to held_locks
> +				    * Queue A in hist_locks
>  				    *
>  				    * In held_locks: A
>  				    * In hist_locks: A
> @@ -604,8 +597,9 @@ that the AX release context is different from the AX acquire context.
>  
>     acquire C
>     /*
> -    * Push C onto held_locks
> -    * Queue C into hist_locks
> +    * Add 'the top of held_locks -> C'
> +    * Push C to held_locks
> +    * Queue C in hist_locks
>      *
>      * In held_locks: C
>      * In hist_locks: C
> @@ -622,9 +616,9 @@ that the AX release context is different from the AX acquire context.
>      */
>  				   acquire D
>  				   /*
> -				    * Push D onto held_locks
> -				    * Queue D into hist_locks
>  				    * Add 'the top of held_locks -> D'
> +				    * Push D to held_locks
> +				    * Queue D in hist_locks
>  				    *
>  				    * In held_locks: A, D
>  				    * In hist_locks: A, D
> @@ -632,8 +626,9 @@ that the AX release context is different from the AX acquire context.
>  				    */
>     acquire E
>     /*
> -    * Push E onto held_locks
> -    * Queue E into hist_locks
> +    * Add 'the top of held_locks -> E'
> +    * Push E to held_locks
> +    * Queue E in hist_locks
>      *
>      * In held_locks: E
>      * In hist_locks: C, E
> @@ -659,6 +654,7 @@ that the AX release context is different from the AX acquire context.
>     commit BX
>     /*
>      * Add 'BX -> ?'
> +    * Answer the following to decide '?'
>      * What has been queued since acquire BX: C, E
>      *
>      * In held_locks: Empty
> @@ -684,15 +680,15 @@ that the AX release context is different from the AX acquire context.
>  				    *           'BX -> C', 'BX -> E'
>  				    */
>  
> -   where A, BX, C,..., E are different lock classes, and a suffix 'X' is
> -   added on crosslocks.
> +   where A, BX, C,..., E are different lock classes and a suffix 'X' is
> +   added at crosslocks.
>  
> -Crossrelease considers all acquisitions after acqiuring BX are
> -candidates which might create dependencies with BX. True dependencies
> -will be determined when identifying the release context of BX. Meanwhile,
> -all typical locks are queued so that they can be used at the commit step.
> -And then two dependencies 'BX -> C' and 'BX -> E' are added at the
> -commit step when identifying the release context.
> +Crossrelease considers all acquisitions following acquiring BX because
> +they can create dependencies with BX. The dependencies will be
> +determined in the release context of BX. Meanwhile, all typical locks
> +are queued so that they can be used at the commit step. Finally, two
> +dependencies 'BX -> C' and 'BX -> E' will be added at the commit step,
> +when identifying the release context.
>  
>  The final graph will be, with crossrelease:
>  
> @@ -704,8 +700,8 @@ The final graph will be, with crossrelease:
>        \
>         -> D
>  
> -   where A, BX, C,..., E are different lock classes, and a suffix 'X' is
> -   added on crosslocks.
> +   where A, BX, C,..., E are different lock classes and a suffix 'X' is
> +   added at crosslocks.
>  
>  However, the final graph will be, without crossrelease:
>  
> @@ -732,39 +728,40 @@ Avoid duplication
>  
>  Crossrelease feature uses a cache like what lockdep already uses for
>  dependency chains, but this time it's for caching CT type dependencies.
> -Once that dependency is cached, the same will never be added again.
> +Once a dependency is cached, the same will never be added again.
>  
>  
> -Lockless for hot paths
> -----------------------
> +Make hot paths lockless
> +-----------------------
>  
>  To keep all locks for later use at the commit step, crossrelease adopts
> -a local array embedded in task_struct, which makes access to the data
> -lockless by forcing it to happen only within the owner context. It's
> -like how lockdep handles held_locks. Lockless implmentation is important
> -since typical locks are very frequently acquired and released.
> +a local array embedded in task_struct, which makes the data locklessly
> +accessible by forcing it to happen only within the owner context. It's
> +like how lockdep handles held_locks. Lockless implementation is
> +important since typical locks are very frequently acquired and released.
>  
>  
>  =================================================
>  APPENDIX A: What lockdep does to work aggresively
>  =================================================
>  
> -A deadlock actually occurs when all wait operations creating circular
> +A deadlock actually occurs when all waiters creating circular
>  dependencies run at the same time. Even though they don't, a potential
> -deadlock exists if the problematic dependencies exist. Thus it's
> +deadlock exists if the problematic dependencies exist. Thus, it's
>  meaningful to detect not only an actual deadlock but also its potential
> -possibility. The latter is rather valuable. When a deadlock occurs
> -actually, we can identify what happens in the system by some means or
> -other even without lockdep. However, there's no way to detect possiblity
> -without lockdep unless the whole code is parsed in head. It's terrible.
> -Lockdep does the both, and crossrelease only focuses on the latter.
> +possibility. The latter is rather valuable. When a deadlock actually
> +occurs, we can identify what happens in the system by some means or
> +other even without lockdep. However, there's no way to detect a
> +possibility without lockdep, unless the whole code is parsed in the head.
> +It's terrible. Lockdep does the both, and crossrelease only focuses on
> +the latter.
>  
>  Whether or not a deadlock actually occurs depends on several factors.
>  For example, what order contexts are switched in is a factor. Assuming
>  circular dependencies exist, a deadlock would occur when contexts are
> -switched so that all wait operations creating the dependencies run
> -simultaneously. Thus to detect a deadlock possibility even in the case
> -that it has not occured yet, lockdep should consider all possible
> +switched so that all waiters creating the dependencies run
> +simultaneously. Thus, to detect a deadlock possibility even in the case
> +that it has not occurred yet, lockdep should consider all possible
>  combinations of dependencies, trying to:
>  
>  1. Use a global dependency graph.
> @@ -776,7 +773,7 @@ combinations of dependencies, trying to:
>  
>  2. Check dependencies between classes instead of instances.
>  
> -   What actually causes a deadlock are instances of lock. However,
> +   What actually causes a deadlock are instances of locks. However,
>     lockdep checks dependencies between classes instead of instances.
>     This way lockdep can detect a deadlock which has not happened but
>     might happen in future by others but the same class.
> @@ -805,44 +802,28 @@ Remind what a dependency is. A dependency exists if:
>  
>  For example:
>  
> -   acquire A
> -   acquire B /* A dependency 'A -> B' exists */
> -   release B
> -   release A
> -
> -   where A and B are different lock classes.
> -
> -A depedency 'A -> B' exists since:
> -
> -   1. A waiter for A and a waiter for B might exist when acquiring B.
> -   2. Only way to wake up each is to release what it waits for.
> -   3. Whether the waiter for A can be woken up depends on whether the
> -      other can. IOW, TASK X cannot release A if it fails to acquire B.
> -
> -For another example:
> -
> -   TASK X			   TASK Y
> -   ------			   ------
> +   CONTEXT X			   CONTEXT Y
> +   ---------			   ---------
>  				   acquire AX
>     acquire B /* A dependency 'AX -> B' exists */
>     release B
>     release AX held by Y
>  
> -   where AX and B are different lock classes, and a suffix 'X' is added
> -   on crosslocks.
> +   where AX and B are different lock classes and a suffix 'X' is added
> +   at crosslocks.
>  
> -Even in this case involving crosslocks, the same rule can be applied. A
> -depedency 'AX -> B' exists since:
> +Here, a dependency 'AX -> B' exists since:
>  
>     1. A waiter for AX and a waiter for B might exist when acquiring B.
> -   2. Only way to wake up each is to release what it waits for.
> +   2. The only way to wake up each is to release what it waits for.
>     3. Whether the waiter for AX can be woken up depends on whether the
> -      other can. IOW, TASK X cannot release AX if it fails to acquire B.
> +      other can. In other words, CONTEXT X cannot release AX if it fails
> +      to acquire B.
>  
> -Let's take a look at more complicated example:
> +Let's take a look at a more complicated example:
>  
> -   TASK X			   TASK Y
> -   ------			   ------
> +   CONTEXT X			   CONTEXT Y
> +   ---------			   ---------
>     acquire B
>     release B
>     fork Y
> @@ -851,22 +832,22 @@ Let's take a look at more complicated example:
>     release C
>     release AX held by Y
>  
> -   where AX, B and C are different lock classes, and a suffix 'X' is
> -   added on crosslocks.
> +   where AX, B, and C are different lock classes and a suffix 'X' is
> +   added at crosslocks.
>  
>  Does a dependency 'AX -> B' exist? Nope.
>  
>  Two waiters are essential to create a dependency. However, waiters for
>  AX and B to create 'AX -> B' cannot exist at the same time in this
> -example. Thus the dependency 'AX -> B' cannot be created.
> +example. Thus, the dependency 'AX -> B' cannot be created.
>  
>  It would be ideal if the full set of true ones can be considered. But
>  we can ensure nothing but what actually happened. Relying on what
>  actually happens at runtime, we can anyway add only true ones, though
>  they might be a subset of true ones. It's similar to how lockdep works
> -for typical locks. There might be more true dependencies than what
> -lockdep has detected in runtime. Lockdep has no choice but to rely on
> -what actually happens. Crossrelease also relies on it.
> +for typical locks. There might be more true dependencies than lockdep
> +has detected. Lockdep has no choice but to rely on what actually happens.
> +Crossrelease also relies on it.
>  
>  CONCLUSION
>  
> -- 
> 1.9.1

Re: [PATCH] locking/Documentation: Revise Documentation/locking/crossrelease.txt

[Byungchul Park]

On Sat, Nov 11, 2017 at 10:45:24PM +0900, Byungchul Park wrote:
> This is the big one including all of version 3.
> 
> You can take only this.

Hello Ingo,

Could you consider this?

I want to offer a better base to someone who helps the doc enhanced. Of
course, in the case you agree with this modification..

I did my best to keep meaningful original contents as much as possible.

Give your opinion, please.

Thanks,
Byungchul

> Thanks,
> Byungchul
> 
> On Sat, Nov 11, 2017 at 10:33:34PM +0900, Byungchul Park wrote:
> > Revise Documentation/locking/crossrelease.txt to improve its readability.
> > 
> > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > ---
> >  Documentation/locking/crossrelease.txt | 329 ++++++++++++++++-----------------
> >  1 file changed, 155 insertions(+), 174 deletions(-)
> > 
> > diff --git a/Documentation/locking/crossrelease.txt b/Documentation/locking/crossrelease.txt
> > index bdf1423..c6d628b 100644
> > --- a/Documentation/locking/crossrelease.txt
> > +++ b/Documentation/locking/crossrelease.txt
> > @@ -12,10 +12,10 @@ Contents:
> >  
> >   (*) Limitation
> >  
> > -     - Limit lockdep
> > +     - Limiting lockdep
> >       - Pros from the limitation
> >       - Cons from the limitation
> > -     - Relax the limitation
> > +     - Relaxing the limitation
> >  
> >   (*) Crossrelease
> >  
> > @@ -30,9 +30,9 @@ Contents:
> >   (*) Optimizations
> >  
> >       - Avoid duplication
> > -     - Lockless for hot paths
> > +     - Make hot paths lockless
> >  
> > - (*) APPENDIX A: What lockdep does to work aggresively
> > + (*) APPENDIX A: What lockdep does to work aggressively
> >  
> >   (*) APPENDIX B: How to avoid adding false dependencies
> >  
> > @@ -55,21 +55,21 @@ For example:
> >     A context going to trigger event A is waiting for event B to happen.
> >     A context going to trigger event B is waiting for event C to happen.
> >  
> > -A deadlock occurs when these three wait operations run at the same time,
> > +A deadlock occurs when these three waiters run at the same time,
> >  because event C cannot be triggered if event A does not happen, which in
> >  turn cannot be triggered if event B does not happen, which in turn
> >  cannot be triggered if event C does not happen. After all, no event can
> >  be triggered since any of them never meets its condition to wake up.
> >  
> > -A dependency might exist between two waiters and a deadlock might happen
> > -due to an incorrect releationship between dependencies. Thus, we must
> > -define what a dependency is first. A dependency exists between them if:
> > +A dependency might exist between two waiters and a deadlock happens due
> > +to an incorrect relationship between dependencies. Thus, we must define
> > +what a dependency is first. A dependency exists if:
> >  
> >     1. There are two waiters waiting for each event at a given time.
> >     2. The only way to wake up each waiter is to trigger its event.
> >     3. Whether one can be woken up depends on whether the other can.
> >  
> > -Each wait in the example creates its dependency like:
> > +Each waiter in the example creates its dependency like:
> >  
> >     Event C depends on event A.
> >     Event A depends on event B.
> > @@ -77,7 +77,7 @@ Each wait in the example creates its dependency like:
> >  
> >     NOTE: Precisely speaking, a dependency is one between whether a
> >     waiter for an event can be woken up and whether another waiter for
> > -   another event can be woken up. However from now on, we will describe
> > +   another event can be woken up. However, from now on, we will describe
> >     a dependency as if it's one between an event and another event for
> >     simplicity.
> >  
> > @@ -109,9 +109,9 @@ event in the previous section.
> >  In short, lockdep does:
> >  
> >     1. Detect a new dependency.
> > -   2. Add the dependency into a global graph.
> > +   2. Add the dependency to a global graph.
> >     3. Check if that makes dependencies circular.
> > -   4. Report a deadlock or its possibility if so.
> > +   4. Report the deadlock or its possibility if so.
> >  
> >  For example, consider a graph built by lockdep that looks like:
> >  
> > @@ -123,7 +123,7 @@ For example, consider a graph built by lockdep that looks like:
> >  
> >     where A, B,..., E are different lock classes.
> >  
> > -Lockdep will add a dependency into the graph on detection of a new
> > +Lockdep will add a dependency to the graph on detection of a new
> >  dependency. For example, it will add a dependency 'E -> C' when a new
> >  dependency between lock E and lock C is detected. Then the graph will be:
> >  
> > @@ -147,7 +147,7 @@ This graph contains a subgraph which demonstrates circular dependencies:
> >     \                  /
> >      ------------------
> >  
> > -   where C, D and E are different lock classes.
> > +   where C, D, and E are different lock classes.
> >  
> >  This is the condition under which a deadlock might occur. Lockdep
> >  reports it on detection after adding a new dependency. This is the way
> > @@ -163,13 +163,13 @@ dependencies were created after adding each new dependency.
> >  Limitation
> >  ==========
> >  
> > -Limit lockdep
> > --------------
> > +Limiting lockdep
> > +----------------
> >  
> >  Limiting lockdep to work on only typical locks e.g. spin locks and
> > -mutexes, which are released within the acquire context, the
> > +mutexes, which are released within their acquire contexts, the
> >  implementation becomes simple but its capacity for detection becomes
> > -limited. Let's check pros and cons in next section.
> > +limited. Let's check pros and cons in the next two sections.
> >  
> >  
> >  Pros from the limitation
> > @@ -179,7 +179,7 @@ Given the limitation, when acquiring a lock, locks in a held_locks
> >  cannot be released if the context cannot acquire it so has to wait to
> >  acquire it, which means all waiters for the locks in the held_locks are
> >  stuck. It's an exact case to create dependencies between each lock in
> > -the held_locks and the lock to acquire.
> > +the held_locks and the lock to acquire at the moment.
> >  
> >  For example:
> >  
> > @@ -195,22 +195,22 @@ For example:
> >  When acquiring lock A, the held_locks of CONTEXT X is empty thus no
> >  dependency is added. But when acquiring lock B, lockdep detects and adds
> >  a new dependency 'A -> B' between lock A in the held_locks and lock B.
> > -They can be simply added whenever acquiring each lock.
> > +Dependencies can be simply added this way, whenever acquiring each lock.
> >  
> > -And data required by lockdep exists in a local structure, held_locks
> > -embedded in task_struct. Forcing to access the data within the context,
> > -lockdep can avoid racy problems without explicit locks while handling
> > -the local data.
> > +Furthermore, since data required to create a dependency can be kept in
> > +local task_struct, lockdep can avoid racy problems without explicit
> > +protection by forcing to access the data within the context.
> >  
> >  Lastly, lockdep only needs to keep locks currently being held, to build
> > -a dependency graph. However, relaxing the limitation, it needs to keep
> > -even locks already released, because a decision whether they created
> > +the dependency graph. However, relaxing the limitation, it needs to keep
> > +even locks already released, because the decision whether they created
> >  dependencies might be long-deferred.
> >  
> >  To sum up, we can expect several advantages from the limitation:
> >  
> >     1. Lockdep can easily identify a dependency when acquiring a lock.
> > -   2. Races are avoidable while accessing local locks in a held_locks.
> > +   2. Races are avoidable without explicit protection while accessing
> > +      local locks in a held_locks.
> >     3. Lockdep only needs to keep locks currently being held.
> >  
> >  CONCLUSION
> > @@ -265,8 +265,8 @@ Given the limitation, lockdep cannot detect a deadlock or its
> >  possibility caused by page locks or completions.
> >  
> >  
> > -Relax the limitation
> > ---------------------
> > +Relaxing the limitation
> > +-----------------------
> >  
> >  Under the limitation, things to create dependencies are limited to
> >  typical locks. However, synchronization primitives like page locks and
> > @@ -278,37 +278,36 @@ these locks to work with lockdep.
> >  Detecting dependencies is very important for lockdep to work because
> >  adding a dependency means adding an opportunity to check whether it
> >  causes a deadlock. The more lockdep adds dependencies, the more it
> > -thoroughly works. Thus Lockdep has to do its best to detect and add as
> > -many true dependencies into a graph as possible.
> > +thoroughly works. Thus, lockdep has to do its best to detect and add as
> > +many true dependencies to the graph as possible.
> >  
> > -For example, considering only typical locks, lockdep builds a graph like:
> > +For example:
> >  
> > -   A -> B -
> > -           \
> > -            -> E
> > -           /
> > -   C -> D -
> > +   CONTEXT X			   CONTEXT Y
> > +   ---------			   ---------
> > +				   acquire A
> > +   acquire B /* A dependency 'A -> B' exists */
> > +   release B
> > +   release A held by Y
> >  
> > -   where A, B,..., E are different lock classes.
> > +   where A and B are different lock classes.
> >  
> > -On the other hand, under the relaxation, additional dependencies might
> > -be created and added. Assuming additional 'FX -> C' and 'E -> GX' are
> > -added thanks to the relaxation, the graph will be:
> > +In this case, a dependency 'A -> B' exists since:
> >  
> > -         A -> B -
> > -                 \
> > -                  -> E -> GX
> > -                 /
> > -   FX -> C -> D -
> > +   1. A waiter for A and a waiter for B might exist when acquiring B.
> > +   2. The only way to wake up each is to release what it waits for.
> > +   3. Whether the waiter for A can be woken up depends on whether the
> > +      other can. In other words, CONTEXT X cannot release A if it fails
> > +      to acquire B.
> >  
> > -   where A, B,..., E, FX and GX are different lock classes, and a suffix
> > -   'X' is added on non-typical locks.
> > +Considering only typical locks, lockdep builds nothing. However,
> > +relaxing the limitation, a dependency 'A -> B' can be added, giving us
> > +more chances to check circular dependencies.
> >  
> > -The latter graph gives us more chances to check circular dependencies
> > -than the former. However, it might suffer performance degradation since
> > -relaxing the limitation, with which design and implementation of lockdep
> > -can be efficient, might introduce inefficiency inevitably. So lockdep
> > -should provide two options, strong detection and efficient detection.
> > +However, it might suffer performance degradation since relaxing the
> > +limitation, with which design and implementation of lockdep can be
> > +efficient, might introduce inefficiency inevitably. So lockdep should
> > +provide two options, strong detection and efficient detection.
> >  
> >  Choosing efficient detection:
> >  
> > @@ -336,27 +335,27 @@ Introduce crossrelease
> >  In order to allow lockdep to handle additional dependencies by what
> >  might be released in any context, namely 'crosslock', we have to be able
> >  to identify those created by crosslocks. The proposed 'crossrelease'
> > -feature provoides a way to do that.
> > +feature provides a way to do that.
> >  
> >  Crossrelease feature has to do:
> >  
> >     1. Identify dependencies created by crosslocks.
> > -   2. Add the dependencies into a dependency graph.
> > +   2. Add the dependencies to the dependency graph.
> >  
> > -That's all. Once a meaningful dependency is added into graph, then
> > +That's all. Once a meaningful dependency is added to the graph, then
> >  lockdep would work with the graph as it did. The most important thing
> >  crossrelease feature has to do is to correctly identify and add true
> > -dependencies into the global graph.
> > +dependencies to the global graph.
> >  
> >  A dependency e.g. 'A -> B' can be identified only in the A's release
> >  context because a decision required to identify the dependency can be
> >  made only in the release context. That is to decide whether A can be
> > -released so that a waiter for A can be woken up. It cannot be made in
> > +released so that waiters for A can be woken up. That cannot be made in
> >  other than the A's release context.
> >  
> >  It's no matter for typical locks because each acquire context is same as
> >  its release context, thus lockdep can decide whether a lock can be
> > -released in the acquire context. However for crosslocks, lockdep cannot
> > +released in the acquire context. However, for crosslocks, lockdep cannot
> >  make the decision in the acquire context but has to wait until the
> >  release context is identified.
> >  
> > @@ -375,10 +374,11 @@ Introduce commit
> >  ----------------
> >  
> >  Since crossrelease defers the work adding true dependencies of
> > -crosslocks until they are actually released, crossrelease has to queue
> > +crosslocks until they are eventually released, crossrelease has to queue
> >  all acquisitions which might create dependencies with the crosslocks.
> > -Then it identifies dependencies using the queued data in batches at a
> > -proper time. We call it 'commit'.
> > +Then lockdep can identify dependencies using the queued data in batches
> > +at a proper time. We call the step adding true dependencies to the graph
> > +in batches, 'commit'.
> >  
> >  There are four types of dependencies:
> >  
> > @@ -404,10 +404,10 @@ There are four types of dependencies:
> >  
> >     When acquiring BX, lockdep cannot identify the dependency because
> >     there's no way to know if it's in the AX's release context. It has
> > -   to wait until the decision can be made. Commit is necessary.
> > -   But, handling CC type is not implemented yet. It's a future work.
> > +   to wait until the decision can be made. Commit is necessary. But,
> > +   handling CC type is not implemented yet. It's a future work.
> >  
> > -Lockdep can work without commit for typical locks, but commit step is
> > +Lockdep can work without commit for typical locks, but the step is
> >  necessary once crosslocks are involved. Introducing commit, lockdep
> >  performs three steps. What lockdep does in each step is:
> >  
> > @@ -416,7 +416,7 @@ performs three steps. What lockdep does in each step is:
> >     it at the commit step. For crosslocks, it saves data which will be
> >     used at the commit step and increases a reference count for it.
> >  
> > -2. Commit: No action is reauired for typical locks. For crosslocks,
> > +2. Commit: No action is required for typical locks. For crosslocks,
> >     lockdep adds CT type dependencies using the data saved at the
> >     acquisition step.
> >  
> > @@ -442,9 +442,9 @@ Crossrelease introduces two main data structures.
> >  
> >     This is an array embedded in task_struct, for keeping lock history so
> >     that dependencies can be added using them at the commit step. Since
> > -   it's local data, it can be accessed locklessly in the owner context.
> > -   The array is filled at the acquisition step and consumed at the
> > -   commit step. And it's managed in circular manner.
> > +   they are local data, they can be accessed locklessly in the owner
> > +   context. The array is filled at the acquisition step and consumed at
> > +   the commit step. And it's managed in a circular manner.
> >  
> >  2. cross_lock
> >  
> > @@ -456,29 +456,24 @@ How crossrelease works
> >  ----------------------
> >  
> >  It's the key of how crossrelease works, to defer necessary works to an
> > -appropriate point in time and perform in at once at the commit step.
> > -Let's take a look with examples step by step, starting from how lockdep
> > -works without crossrelease for typical locks.
> > +appropriate point in time and perform the works at the commit step.
> > +
> > +Let's take a look at examples step by step, starting from how lockdep
> > +works for typical locks, without crossrelease.
> >  
> > -   acquire A /* Push A onto held_locks */
> > -   acquire B /* Push B onto held_locks and add 'A -> B' */
> > -   acquire C /* Push C onto held_locks and add 'B -> C' */
> > +   acquire A /* Push A to held_locks */
> > +   acquire B /* Push B to held_locks and add 'A -> B' */
> > +   acquire C /* Push C to held_locks and add 'B -> C' */
> >     release C /* Pop C from held_locks */
> >     release B /* Pop B from held_locks */
> >     release A /* Pop A from held_locks */
> >  
> > -   where A, B and C are different lock classes.
> > +   where A, B, and C are different lock classes.
> >  
> > -   NOTE: This document assumes that readers already understand how
> > -   lockdep works without crossrelease thus omits details. But there's
> > -   one thing to note. Lockdep pretends to pop a lock from held_locks
> > -   when releasing it. But it's subtly different from the original pop
> > -   operation because lockdep allows other than the top to be poped.
> > +Lockdep adds 'the top of held_locks -> the lock to acquire' dependency
> > +every time acquiring a lock.
> >  
> > -In this case, lockdep adds 'the top of held_locks -> the lock to acquire'
> > -dependency every time acquiring a lock.
> > -
> > -After adding 'A -> B', a dependency graph will be:
> > +After adding 'A -> B', the dependency graph will be:
> >  
> >     A -> B
> >  
> > @@ -488,15 +483,15 @@ And after adding 'B -> C', the graph will be:
> >  
> >     A -> B -> C
> >  
> > -   where A, B and C are different lock classes.
> > +   where A, B, and C are different lock classes.
> >  
> > -Let's performs commit step even for typical locks to add dependencies.
> > -Of course, commit step is not necessary for them, however, it would work
> > -well because this is a more general way.
> > +Let's build the graph using the commit step with the same example. Of
> > +course, the step is not necessary for typical locks, however, it would
> > +also work because this is a more general way.
> >  
> >     acquire A
> >     /*
> > -    * Queue A into hist_locks
> > +    * Queue A in hist_locks
> >      *
> >      * In hist_locks: A
> >      * In graph: Empty
> > @@ -504,7 +499,7 @@ well because this is a more general way.
> >  
> >     acquire B
> >     /*
> > -    * Queue B into hist_locks
> > +    * Queue B in hist_locks
> >      *
> >      * In hist_locks: A, B
> >      * In graph: Empty
> > @@ -512,7 +507,7 @@ well because this is a more general way.
> >  
> >     acquire C
> >     /*
> > -    * Queue C into hist_locks
> > +    * Queue C in hist_locks
> >      *
> >      * In hist_locks: A, B, C
> >      * In graph: Empty
> > @@ -554,34 +549,32 @@ well because this is a more general way.
> >  
> >     release A
> >  
> > -   where A, B and C are different lock classes.
> > -
> > -In this case, dependencies are added at the commit step as described.
> > +   where A, B, and C are different lock classes.
> >  
> > -After commits for A, B and C, the graph will be:
> > +Dependencies are added at the commit step as described. After commits
> > +for A, B, and C, the graph will be:
> >  
> >     A -> B -> C
> >  
> > -   where A, B and C are different lock classes.
> > +   where A, B, and C are different lock classes.
> >  
> >     NOTE: A dependency 'A -> C' is optimized out.
> >  
> > -We can see the former graph built without commit step is same as the
> > -latter graph built using commit steps. Of course the former way leads to
> > -earlier finish for building the graph, which means we can detect a
> > -deadlock or its possibility sooner. So the former way would be prefered
> > -when possible. But we cannot avoid using the latter way for crosslocks.
> > +We can see the former graph built without the commit step is same as the
> > +latter graph. Of course, the former way leads to earlier finish for
> > +building the graph, which means we can detect a deadlock or its
> > +possibility sooner. So the former way would be preferred when possible.
> > +But we cannot avoid using the latter way for crosslocks.
> >  
> > -Let's look at how commit steps work for crosslocks. In this case, the
> > -commit step is performed only on crosslock AX as real. And it assumes
> > -that the AX release context is different from the AX acquire context.
> > +Lastly, let's look at how commit works for crosslocks in practice.
> >  
> >     BX RELEASE CONTEXT		   BX ACQUIRE CONTEXT
> >     ------------------		   ------------------
> >  				   acquire A
> >  				   /*
> > -				    * Push A onto held_locks
> > -				    * Queue A into hist_locks
> > +				    * Add 'the top of held_locks -> A'
> > +				    * Push A to held_locks
> > +				    * Queue A in hist_locks
> >  				    *
> >  				    * In held_locks: A
> >  				    * In hist_locks: A
> > @@ -604,8 +597,9 @@ that the AX release context is different from the AX acquire context.
> >  
> >     acquire C
> >     /*
> > -    * Push C onto held_locks
> > -    * Queue C into hist_locks
> > +    * Add 'the top of held_locks -> C'
> > +    * Push C to held_locks
> > +    * Queue C in hist_locks
> >      *
> >      * In held_locks: C
> >      * In hist_locks: C
> > @@ -622,9 +616,9 @@ that the AX release context is different from the AX acquire context.
> >      */
> >  				   acquire D
> >  				   /*
> > -				    * Push D onto held_locks
> > -				    * Queue D into hist_locks
> >  				    * Add 'the top of held_locks -> D'
> > +				    * Push D to held_locks
> > +				    * Queue D in hist_locks
> >  				    *
> >  				    * In held_locks: A, D
> >  				    * In hist_locks: A, D
> > @@ -632,8 +626,9 @@ that the AX release context is different from the AX acquire context.
> >  				    */
> >     acquire E
> >     /*
> > -    * Push E onto held_locks
> > -    * Queue E into hist_locks
> > +    * Add 'the top of held_locks -> E'
> > +    * Push E to held_locks
> > +    * Queue E in hist_locks
> >      *
> >      * In held_locks: E
> >      * In hist_locks: C, E
> > @@ -659,6 +654,7 @@ that the AX release context is different from the AX acquire context.
> >     commit BX
> >     /*
> >      * Add 'BX -> ?'
> > +    * Answer the following to decide '?'
> >      * What has been queued since acquire BX: C, E
> >      *
> >      * In held_locks: Empty
> > @@ -684,15 +680,15 @@ that the AX release context is different from the AX acquire context.
> >  				    *           'BX -> C', 'BX -> E'
> >  				    */
> >  
> > -   where A, BX, C,..., E are different lock classes, and a suffix 'X' is
> > -   added on crosslocks.
> > +   where A, BX, C,..., E are different lock classes and a suffix 'X' is
> > +   added at crosslocks.
> >  
> > -Crossrelease considers all acquisitions after acqiuring BX are
> > -candidates which might create dependencies with BX. True dependencies
> > -will be determined when identifying the release context of BX. Meanwhile,
> > -all typical locks are queued so that they can be used at the commit step.
> > -And then two dependencies 'BX -> C' and 'BX -> E' are added at the
> > -commit step when identifying the release context.
> > +Crossrelease considers all acquisitions following acquiring BX because
> > +they can create dependencies with BX. The dependencies will be
> > +determined in the release context of BX. Meanwhile, all typical locks
> > +are queued so that they can be used at the commit step. Finally, two
> > +dependencies 'BX -> C' and 'BX -> E' will be added at the commit step,
> > +when identifying the release context.
> >  
> >  The final graph will be, with crossrelease:
> >  
> > @@ -704,8 +700,8 @@ The final graph will be, with crossrelease:
> >        \
> >         -> D
> >  
> > -   where A, BX, C,..., E are different lock classes, and a suffix 'X' is
> > -   added on crosslocks.
> > +   where A, BX, C,..., E are different lock classes and a suffix 'X' is
> > +   added at crosslocks.
> >  
> >  However, the final graph will be, without crossrelease:
> >  
> > @@ -732,39 +728,40 @@ Avoid duplication
> >  
> >  Crossrelease feature uses a cache like what lockdep already uses for
> >  dependency chains, but this time it's for caching CT type dependencies.
> > -Once that dependency is cached, the same will never be added again.
> > +Once a dependency is cached, the same will never be added again.
> >  
> >  
> > -Lockless for hot paths
> > -----------------------
> > +Make hot paths lockless
> > +-----------------------
> >  
> >  To keep all locks for later use at the commit step, crossrelease adopts
> > -a local array embedded in task_struct, which makes access to the data
> > -lockless by forcing it to happen only within the owner context. It's
> > -like how lockdep handles held_locks. Lockless implmentation is important
> > -since typical locks are very frequently acquired and released.
> > +a local array embedded in task_struct, which makes the data locklessly
> > +accessible by forcing it to happen only within the owner context. It's
> > +like how lockdep handles held_locks. Lockless implementation is
> > +important since typical locks are very frequently acquired and released.
> >  
> >  
> >  =================================================
> >  APPENDIX A: What lockdep does to work aggresively
> >  =================================================
> >  
> > -A deadlock actually occurs when all wait operations creating circular
> > +A deadlock actually occurs when all waiters creating circular
> >  dependencies run at the same time. Even though they don't, a potential
> > -deadlock exists if the problematic dependencies exist. Thus it's
> > +deadlock exists if the problematic dependencies exist. Thus, it's
> >  meaningful to detect not only an actual deadlock but also its potential
> > -possibility. The latter is rather valuable. When a deadlock occurs
> > -actually, we can identify what happens in the system by some means or
> > -other even without lockdep. However, there's no way to detect possiblity
> > -without lockdep unless the whole code is parsed in head. It's terrible.
> > -Lockdep does the both, and crossrelease only focuses on the latter.
> > +possibility. The latter is rather valuable. When a deadlock actually
> > +occurs, we can identify what happens in the system by some means or
> > +other even without lockdep. However, there's no way to detect a
> > +possibility without lockdep, unless the whole code is parsed in the head.
> > +It's terrible. Lockdep does the both, and crossrelease only focuses on
> > +the latter.
> >  
> >  Whether or not a deadlock actually occurs depends on several factors.
> >  For example, what order contexts are switched in is a factor. Assuming
> >  circular dependencies exist, a deadlock would occur when contexts are
> > -switched so that all wait operations creating the dependencies run
> > -simultaneously. Thus to detect a deadlock possibility even in the case
> > -that it has not occured yet, lockdep should consider all possible
> > +switched so that all waiters creating the dependencies run
> > +simultaneously. Thus, to detect a deadlock possibility even in the case
> > +that it has not occurred yet, lockdep should consider all possible
> >  combinations of dependencies, trying to:
> >  
> >  1. Use a global dependency graph.
> > @@ -776,7 +773,7 @@ combinations of dependencies, trying to:
> >  
> >  2. Check dependencies between classes instead of instances.
> >  
> > -   What actually causes a deadlock are instances of lock. However,
> > +   What actually causes a deadlock are instances of locks. However,
> >     lockdep checks dependencies between classes instead of instances.
> >     This way lockdep can detect a deadlock which has not happened but
> >     might happen in future by others but the same class.
> > @@ -805,44 +802,28 @@ Remind what a dependency is. A dependency exists if:
> >  
> >  For example:
> >  
> > -   acquire A
> > -   acquire B /* A dependency 'A -> B' exists */
> > -   release B
> > -   release A
> > -
> > -   where A and B are different lock classes.
> > -
> > -A depedency 'A -> B' exists since:
> > -
> > -   1. A waiter for A and a waiter for B might exist when acquiring B.
> > -   2. Only way to wake up each is to release what it waits for.
> > -   3. Whether the waiter for A can be woken up depends on whether the
> > -      other can. IOW, TASK X cannot release A if it fails to acquire B.
> > -
> > -For another example:
> > -
> > -   TASK X			   TASK Y
> > -   ------			   ------
> > +   CONTEXT X			   CONTEXT Y
> > +   ---------			   ---------
> >  				   acquire AX
> >     acquire B /* A dependency 'AX -> B' exists */
> >     release B
> >     release AX held by Y
> >  
> > -   where AX and B are different lock classes, and a suffix 'X' is added
> > -   on crosslocks.
> > +   where AX and B are different lock classes and a suffix 'X' is added
> > +   at crosslocks.
> >  
> > -Even in this case involving crosslocks, the same rule can be applied. A
> > -depedency 'AX -> B' exists since:
> > +Here, a dependency 'AX -> B' exists since:
> >  
> >     1. A waiter for AX and a waiter for B might exist when acquiring B.
> > -   2. Only way to wake up each is to release what it waits for.
> > +   2. The only way to wake up each is to release what it waits for.
> >     3. Whether the waiter for AX can be woken up depends on whether the
> > -      other can. IOW, TASK X cannot release AX if it fails to acquire B.
> > +      other can. In other words, CONTEXT X cannot release AX if it fails
> > +      to acquire B.
> >  
> > -Let's take a look at more complicated example:
> > +Let's take a look at a more complicated example:
> >  
> > -   TASK X			   TASK Y
> > -   ------			   ------
> > +   CONTEXT X			   CONTEXT Y
> > +   ---------			   ---------
> >     acquire B
> >     release B
> >     fork Y
> > @@ -851,22 +832,22 @@ Let's take a look at more complicated example:
> >     release C
> >     release AX held by Y
> >  
> > -   where AX, B and C are different lock classes, and a suffix 'X' is
> > -   added on crosslocks.
> > +   where AX, B, and C are different lock classes and a suffix 'X' is
> > +   added at crosslocks.
> >  
> >  Does a dependency 'AX -> B' exist? Nope.
> >  
> >  Two waiters are essential to create a dependency. However, waiters for
> >  AX and B to create 'AX -> B' cannot exist at the same time in this
> > -example. Thus the dependency 'AX -> B' cannot be created.
> > +example. Thus, the dependency 'AX -> B' cannot be created.
> >  
> >  It would be ideal if the full set of true ones can be considered. But
> >  we can ensure nothing but what actually happened. Relying on what
> >  actually happens at runtime, we can anyway add only true ones, though
> >  they might be a subset of true ones. It's similar to how lockdep works
> > -for typical locks. There might be more true dependencies than what
> > -lockdep has detected in runtime. Lockdep has no choice but to rely on
> > -what actually happens. Crossrelease also relies on it.
> > +for typical locks. There might be more true dependencies than lockdep
> > +has detected. Lockdep has no choice but to rely on what actually happens.
> > +Crossrelease also relies on it.
> >  
> >  CONCLUSION
> >  
> > -- 
> > 1.9.1

Re: [PATCH] locking/Documentation: Revise Documentation/locking/crossrelease.txt

[Ingo Molnar]

* Byungchul Park <byungchul.park@lge.com> wrote:

> On Sat, Nov 11, 2017 at 10:45:24PM +0900, Byungchul Park wrote:
> > This is the big one including all of version 3.
> > 
> > You can take only this.
> 
> Hello Ingo,
> 
> Could you consider this?

Yeah, I'll have a look in a few days, but right now we are in the middle of the 
merge window.

Thanks,

	Ingo

Re: [PATCH] locking/Documentation: Revise Documentation/locking/crossrelease.txt

[Byungchul Park]

On 11/16/2017 4:22 PM, Ingo Molnar wrote:
> 
> * Byungchul Park <byungchul.park@lge.com> wrote:
> 
>> On Sat, Nov 11, 2017 at 10:45:24PM +0900, Byungchul Park wrote:
>>> This is the big one including all of version 3.
>>>
>>> You can take only this.
>>
>> Hello Ingo,
>>
>> Could you consider this?
> 
> Yeah, I'll have a look in a few days, but right now we are in the middle of the
> merge window.

Thank you very much.

> 
> Thanks,
> 
> 	Ingo
> 

-- 
Thanks,
Byungchul

Re: [PATCH] locking/Documentation: Revise Documentation/locking/crossrelease.txt

[Byungchul Park]

On Thu, Nov 16, 2017 at 08:22:37AM +0100, Ingo Molnar wrote:
> 
> * Byungchul Park <byungchul.park@lge.com> wrote:
> 
> > On Sat, Nov 11, 2017 at 10:45:24PM +0900, Byungchul Park wrote:
> > > This is the big one including all of version 3.
> > > 
> > > You can take only this.
> > 
> > Hello Ingo,
> > 
> > Could you consider this?
> 
> Yeah, I'll have a look in a few days, but right now we are in the middle of the 
> merge window.

Excuse me but, could you take a look?