Messages in this thread | | | Date | Tue, 10 Jan 2017 21:08:50 +0100 | From | Peter Zijlstra <> | Subject | 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' > + */
| |