Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1555888 > unrolled thread

Re: [PATCH v4 15/15] lockdep: Crossrelease feature documentation

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH v4 15/15] lockdep: Crossrelease feature documentation Peter Zijlstra <peterz@infradead.org> - 2017-01-10 21:10 +0100
    Re: [PATCH v4 15/15] lockdep: Crossrelease feature documentation Byungchul Park <byungchul.park@lge.com> - 2017-01-11 02:40 +0100

#1555888 — Re: [PATCH v4 15/15] lockdep: Crossrelease feature documentation

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'
> +    */

[toc] | [next] | [standalone]

#1556132

On Tue, Jan 10, 2017 at 09:08:50PM +0100, Peter Zijlstra wrote:
> But I still feel this document is very hard to read and presents things
> backwards.

I admit it. I think I need to modify the document more.. I will try it.

> 
> > +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.

Sure. The dependency 'AX -> B' might exist in that case. Then we can
add the dependency once we detect it, in other words, once we prove it's
a true dependency. But we cannot add it before we prove it, though it
might be a true one, because it might not be a true one.

> 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).

Exactly.

> 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.

Thank you.

> > +
> > +   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.

I will consider that more.

> 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.

So do I.

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

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web