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@xxxxxxxxx. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>