First off my sincere apologies for being so horribly slow with this :/

I did spend some time thinking about this thing during the Christmas
holidays, but have not yet managed to write a coherent text on it like I
promised I'd do.

That said; I think I now mostly understand what and why.

But I still feel this document is very hard to read and presents things
backwards.

+Let's take a look at more complicated example.
+
+   TASK X			   TASK Y
+   ------			   ------
+   acquire B
+
+   release B
+
+   acquire C
+
+   release C
+   (1)
+   fork Y
+				   acquire AX
+   acquire D
+   /* A dependency 'AX -> D' exists */
+				   acquire F
+   release D
+				   acquire G
+				   /* A dependency 'F -> G' exists */
+   acquire E
+   /* A dependency 'AX -> E' exists */
+				   acquire H
+				   /* A dependency 'G -> H' exists */
+   release E
+				   release H
+   release AX held by Y
+				   release G
+
+				   release F
+
+   where AX, B, C,..., H are different lock classes, and a suffix 'X' is
+   added on crosslocks.
+
+Does a dependency 'AX -> B' exist? Nope.

I think the above without the "fork Y" line is a much more interesting
example, because then the answer becomes: maybe.

This all boils down to the asynchonous nature of the primitive. There is
no well defined point other than what is observed (as I think you tried
to point out in our earlier exchanges).

The "acquire AX" point is entirely random wrt any action in other
threads, _however_ the time between "acquire" and "release" of any
'lock' is the only time we can be certain of things.

+==============
+Implementation
+==============
+
+Data structures
+---------------
+
+Crossrelease feature introduces two main data structures.
+
+1. pend_lock

I'm not sure 'pending' is the right name here, but I'll consider that
more when I review the code patches.

+
+   This is an array embedded in task_struct, for keeping locks queued so
+   that real dependencies can be added using them at commit step. Since
+   it's local data, it can be accessed locklessly in the owner context.
+   The array is filled at acquire step and consumed at commit step. And
+   it's managed in circular manner.
+
+2. cross_lock
+
+   This is a global linked list, for keeping all crosslocks in progress.
+   The list grows at acquire step and is shrunk at release step.

FWIW, this is a perfect example of why I say the document is written
backwards. At this point there is no demonstrated need or use for this
list.

+
+CONCLUSION
+
+Crossrelease feature introduces two main data structures.
+
+1. A pend_lock array for queueing typical locks in circular manner.
+2. A cross_lock linked list for managing crosslocks in progress.
+
+
+How crossrelease works
+----------------------
+
+Let's take a look at how crossrelease feature works step by step,
+starting from how lockdep works without crossrelease feaure.
+

+
+Let's look at how commit works for crosslocks.
+
+   AX's RELEASE CONTEXT		   AX's ACQUIRE CONTEXT
+   --------------------		   --------------------
+				   acquire AX
+				   /*
+				    * 1. Mark AX as started
+				    *
+				    * (No queuing for crosslocks)
+				    *
+				    * In pend_lock: Empty
+				    * In graph: Empty
+				    */
+
+   (serialized by some means e.g. barrier)
+
+   acquire D
+   /*
+    * (No marking for typical locks)
+    *
+    * 1. Queue D
+    *
+    * In pend_lock: D
+    * In graph: Empty
+    */
+				   acquire B
+				   /*
+				    * (No marking for typical locks)
+				    *
+				    * 1. Queue B
+				    *
+				    * In pend_lock: B
+				    * In graph: Empty
+				    */
+   release D
+   /*
+    * (No commit for typical locks)
+    *
+    * In pend_lock: D
+    * In graph: Empty
+    */
+				   acquire C
+				   /*
+				    * (No marking for typical locks)
+				    *
+				    * 1. Add 'B -> C' of TT type
+				    * 2. Queue C
+				    *
+				    * In pend_lock: B, C
+				    * In graph: 'B -> C'
+				    */
+   acquire E
+   /*
+    * (No marking for typical locks)
+    *
+    * 1. Queue E
+    *
+    * In pend_lock: D, E
+    * In graph: 'B -> C'
+    */
+				   acquire D
+				   /*
+				    * (No marking for typical locks)
+				    *
+				    * 1. Add 'C -> D' of TT type
+				    * 2. Queue D
+				    *
+				    * In pend_lock: B, C, D
+				    * In graph: 'B -> C', 'C -> D'
+				    */
+   release E
+   /*
+    * (No commit for typical locks)
+    *
+    * In pend_lock: D, E
+    * In graph: 'B -> C', 'C -> D'
+    */
+				   release D
+				   /*
+				    * (No commit for typical locks)
+				    *
+				    * In pend_lock: B, C, D
+				    * In graph: 'B -> C', 'C -> D'
+				    */
+   release AX
+   /*
+    * 1. Commit AX (= Add 'AX -> ?')
+    *   a. What queued since AX was marked: D, E
+    *   b. Add 'AX -> D' of CT type
+    *   c. Add 'AX -> E' of CT type

OK, so commit adds multiple dependencies, that makes more sense.
Previously I understood commit to only add a single dependency, which
does not make sense (except in the special case where there is but one).

I dislike how I have to reconstruct this from an example instead of
first having had the rules stated though.

+    *
+    * In pend_lock: D, E
+    * In graph: 'B -> C', 'C -> D',
+    *           'AX -> D', 'AX -> E'
+    */

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>