Date:   Mon, 19 Sep 2016 12:00:53 +0900
From:   Byungchul Park <byungchul.park@....com>
To:     Nilay Vaish <nilayvaish@...il.com>
Cc:     peterz@...radead.org, mingo@...nel.org, tglx@...utronix.de,
        walken@...gle.com, boqun.feng@...il.com, kirill@...temov.name,
        Linux Kernel list <linux-kernel@...r.kernel.org>,
        linux-mm@...ck.org, iamjoonsoo.kim@....com,
        akpm@...ux-foundation.org, npiggin@...il.com
Subject: Re: [PATCH v3 15/15] lockdep: Crossrelease feature documentation

On Fri, Sep 16, 2016 at 10:47:06AM -0500, Nilay Vaish wrote:
> On 13 September 2016 at 04:45, Byungchul Park <byungchul.park@....com> wrote:
> > This document describes the concept of crossrelease feature, which
> > generalizes what causes a deadlock and how can detect a deadlock.
> >
> > Signed-off-by: Byungchul Park <byungchul.park@....com>
> > ---
> >  Documentation/locking/crossrelease.txt | 785 +++++++++++++++++++++++++++++++++
> >  1 file changed, 785 insertions(+)
> >  create mode 100644 Documentation/locking/crossrelease.txt
> >
> > diff --git a/Documentation/locking/crossrelease.txt b/Documentation/locking/crossrelease.txt
> > new file mode 100644
> > index 0000000..78558af
> > --- /dev/null
> > +++ b/Documentation/locking/crossrelease.txt
> > @@ -0,0 +1,785 @@
> > +Crossrelease
> > +============
> > +
> > +Started by Byungchul Park <byungchul.park@....com>
> > +
> > +Contents:
> > +
> > + (*) Background.
> > +
> > +     - What causes deadlock.
> > +     - What lockdep detects.
> > +     - How lockdep works.
> > +
> > + (*) Limitation.
> > +
> > +     - Limit to typical lock.
> > +     - Pros from the limitation.
> > +     - Cons from the limitation.
> > +
> > + (*) Generalization.
> > +
> > +     - Relax the limitation.
> > +
> > + (*) Crossrelease.
> > +
> > +     - Introduce crossrelease.
> > +     - Introduce commit.
> > +
> > + (*) Implementation.
> > +
> > +     - Data structures.
> > +     - How crossrelease works.
> > +
> > + (*) Optimizations.
> > +
> > +     - Avoid duplication.
> > +     - Avoid lock contention.
> > +
> > +
> > +==========
> > +Background
> > +==========
> > +
> > +What causes deadlock
> > +--------------------
> > +
> > +A deadlock occurs when a context is waiting for an event to be issued
> > +which cannot be issued because the context or another context who can
> > +issue the event is also waiting for an event to be issued which cannot
> > +be issued.
> 
> I think 'some event happened' and 'context triggered an event' is
> better than 'some event issued' or 'context issued an event'.  I think
> 'happen' and 'trigger' are more widely used words when we talk about
> events.  For example, I would prefer the following version of the
> above:
> 
> A deadlock occurs when a context is waiting for an event to happen,
> which cannot happen because the context which can trigger the event is
> also waiting for an event to happen which cannot happen either.

Thank you very much for your comments.
I will check it and add my opinions later. :)

Thank you,
Byungchul

> 
> > +Single context or more than one context both waiting for an
> > +event and issuing an event may paricipate in a deadlock.
> 
> I am not able to make sense of the line above.
> 
> > +
> > +For example,
> > +
> > +A context who can issue event D is waiting for event A to be issued.
> > +A context who can issue event A is waiting for event B to be issued.
> > +A context who can issue event B is waiting for event C to be issued.
> > +A context who can issue event C is waiting for event D to be issued.
> > +
> > +A deadlock occurs when these four operations are run at a time because
> > +event D cannot be issued if event A isn't issued which in turn cannot be
> > +issued if event B isn't issued which in turn cannot be issued if event C
> > +isn't issued which in turn cannot be issued if event D isn't issued. No
> > +event can be issued since any of them never meets its precondition.
> > +
> > +We can easily recognize that each wait operation creates a dependency
> > +between two issuings e.g. between issuing D and issuing A like, 'event D
> > +cannot be issued if event A isn't issued', in other words, 'issuing
> > +event D depends on issuing event A'. So the whole example can be
> > +rewritten in terms of dependency,
> > +
> > +Do an operation making 'event D cannot be issued if event A isn't issued'.
> > +Do an operation making 'event A cannot be issued if event B isn't issued'.
> > +Do an operation making 'event B cannot be issued if event C isn't issued'.
> > +Do an operation making 'event C cannot be issued if event D isn't issued'.
> > +
> > +or,
> 
> I think we can remove the text above.  The example only needs to be
> provided once.
> 
> > +
> > +Do an operation making 'issuing event D depends on issuing event A'.
> > +Do an operation making 'issuing event A depends on issuing event B'.
> > +Do an operation making 'issuing event B depends on issuing event C'.
> > +Do an operation making 'issuing event C depends on issuing event D'.
> > +
> > +What causes a deadlock is a set of dependencies a chain of which forms a
> > +cycle, which means that issuing event D depending on issuing event A
> > +depending on issuing event B depending on issuing event C depending on
> > +issuing event D, finally depends on issuing event D itself, which means
> > +no event can be issued.
> > +
> > +Any set of operations creating dependencies causes a deadlock. The set
> > +of lock operations e.g. acquire and release is an example. Waiting for a
> > +lock to be released corresponds to waiting for an event and releasing a
> > +lock corresponds to issuing an event. So the description of dependency
> > +above can be altered to one in terms of lock.
> > +
> > +In terms of event, issuing event A depends on issuing event B if,
> > +
> > +       Event A cannot be issued if event B isn't issued.
> > +
> > +In terms of lock, releasing lock A depends on releasing lock B if,
> > +
> > +       Lock A cannot be released if lock B isn't released.
> > +
> > +CONCLUSION
> > +
> > +A set of dependencies a chain of which forms a cycle, causes a deadlock,
> 
> I think 'a chain of' is not required in the sentence above.
> 
> > +no matter what creates the dependencies.
> > +
> > +
> > +What lockdep detects
> > +--------------------
> > +
> > +A deadlock actually occurs only when all operations creating problematic
> 
> Instead of 'problematic', I would use 'cyclic'.
> 
> > +dependencies are run at a time. However, even if it has not happend, the
> 
> dependencies happen at run time.  However, even if they don't, the
> 
> > +deadlock potentially can occur if the problematic dependencies obviously
> 
> remove obviously
> 
> > +exist. Thus it's meaningful to detect not only an actual deadlock but
> > +also its possibility. Lockdep does the both.
> > +
> > +Whether a deadlock actually occurs or not depends on several factors,
> > +which means a deadlock may not occur even though problematic
> 
> cyclic instead of problematic
> 
> > +dependencies exist. For example, what order contexts are switched in is
> > +a factor. A deadlock will occur when contexts are switched so that all
> > +operations causing a deadlock become run simultaneously.
> 
> delete become.
> 
> > +
> > +Lockdep tries to detect a deadlock or its possibility aggressively,
> > +though it also tries to avoid false positive detections. So lockdep is
> > +designed to consider all possible combinations of dependencies so that
> > +it can detect all potential possibilities of deadlock in advance. What
> > +lockdep tries in order to consider all possibilities are,
> > +
> > +1. Use a global dependency graph including all dependencies.
> > +
> > +   What lockdep checks is based on dependencies instead of what actually
> > +   happened. So no matter which context or call path a new dependency is
> > +   detected in, it's just referred to as a global factor.
> 
> Can you explain more what 'global factor' means?
> 
> 
> > +
> > +2. Use lock classes than lock instances when checking dependencies.
> > +
> > +   What actually causes a deadlock is lock instances. However, lockdep
> > +   uses lock classes than its instances when checking dependencies since
> > +   any instance of a same lock class can be altered anytime.
> 
> I am unable to make sense of the sentence above.  Do you want to say
> the following:
> 
> However, lockdep uses lock classes than its instances when checking
> dependencies since instances from the same lock class behave in the
> same (or similar) fashion.
> 
> > +
> > +So lockdep detects both an actual deadlock and its possibility. But the
> > +latter is more valuable than the former. When a deadlock actually
> > +occures, 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.
> > +
> > +CONCLUSION
> > +
> > +Lockdep does, the fisrt one is more valuable,
> > +
> > +1. Detecting and reporting deadlock possibility.
> > +2. Detecting and reporting a deadlock actually occured.
> > +
> > +
> > +How lockdep works
> > +-----------------
> > +
> > +What lockdep should do, to detect a deadlock or its possibility are,
> > +
> > +1. Detect a new dependency created.
> > +2. Keep the dependency in a global data structure esp. graph.
> > +3. Check if any of all possible chains of dependencies forms a cycle.
> > +4. Report a deadlock or its possibility if a cycle is detected.
> > +
> > +A graph used by lockdep to keep all dependencies looks like,
> > +
> > +A -> B -        -> F -> G
> > +        \      /
> > +         -> E -        -> L
> > +        /      \      /
> > +C -> D -        -> H -
> > +                      \
> > +                       -> I -> K
> > +                      /
> > +                   J -
> > +
> > +where A, B,..., L are different lock classes.
> > +
> > +Lockdep adds a dependency into graph when a new dependency is detected.
> > +For example, it adds a dependency 'A -> B' when a dependency between
> > +releasing lock A and releasing lock B, which has not been added yet, is
> > +detected. It does same thing on other dependencies, too. See 'What
> > +causes deadlock' section.
> 
> Just from the text above I am not able to understand at what point the
> dependency A-> B is added.  If I was implementing lockdep, I would
> probably track all the locks that can be acquired between acquisition
> and release of A.  For example,
> 
> acquire A
> 
> if (/* some condition */)
>     acquire B
> else
>     acquire C
> 
> release A
> 
> 
> I would add to the dependency graph that 'release A' depends on
> 'acquire B' and 'acquire C'.
> 
> > +
> > +NOTE: Precisely speaking, a dependency is one between releasing a lock
> > +and releasing another lock as described in 'What causes deadlock'
> > +section. However from now on, we will describe a dependency as if it's
> > +one between a lock and another lock for simplicity. Then 'A -> B' can be
> > +described as a dependency between lock A and lock B.
> > +
> > +We already checked how a problematic set of dependencies causes a
> > +deadlock in 'What causes deadlock' section. This time let's check if a
> > +deadlock or its possibility can be detected using a problematic set of
> > +dependencies. Assume that 'A -> B', 'B -> E' and 'E -> A' were added in
> > +the sequence into graph. Then the graph finally will be,
> > +
> > + -> A -> B -> E -
> > +/                \
> > +\                /
> > + ----------------
> > +
> > +where A, B and E are different lock classes.
> > +
> > +From adding three dependencies, a cycle was created which means, by
> > +definition of dependency, the situation 'lock E must be released to
> > +release lock B which in turn must be released to release lock A which in
> > +turn must be released to release lock E which in turn must be released
> > +to release B and so on infinitely' can happen.
> > +
> > +Once the situation happens, no lock can be released since any of them
> > +can never meet each precondition. It's a deadlock. Lockdep can detect a
> > +deadlock or its possibility with checking if a cycle was created after
> > +adding each dependency into graph. This is how lockdep detects a
> > +deadlock or its possibility.
> 
> I think the text here is just repeating what was said above in the
> 'What causes deadlock' section.  You probably should remove of the
> text here.
> 
> > +
> > +CONCLUSION
> > +
> > +Lockdep detects a deadlock or its possibility with checking if a cycle
> > +was created after adding each dependency into graph.
> > +
> > +
> > +==========
> > +Limitation
> > +==========
> > +
> > +Limit to typical lock
> > +---------------------
> > +
> > +Limiting what lockdep has to consider to only ones satisfying the
> > +following condition, the implementation of adding dependencies becomes
> > +simple while its capacity for detection becomes limited. Typical lock
> > +e.g. spin lock and mutex is the case. Let's check what pros and cons of
> > +it are, in next section.
> > +
> > +       A lock should be released within the context holding the lock.
> 
> I would rephrase the above in the following way:  Lockdep is limited
> to checking dependencies on locks that are released within the context
> that acquired them.  This makes adding dependencies simple but limits
> lockdep's capacity for detection.
> 
> 
> > +
> > +CONCLUSION
> > +
> > +Limiting what lockdep has to consider to typical lock e.g. spin lock and
> > +mutex, the implmentation becomes simple while it has a limited capacity.
> 
> I would drop the conclusion altogether.  The above paragraph is too
> small to require a conclusion.
> 
> > +
> > +
> > +Pros from the limitation
> > +------------------------
> > +
> > +Given the limitation, when acquiring a lock, any lock being in
> > +held_locks of the acquire context cannot be released if the lock to
> 
> What does held_locks mean here?  Is it some structure maintained by
> the Linux kernel?
> 
> > +acquire was not released yet. Yes. It's the exact case to add a new
> > +dependency 'A -> B' into graph, where lock A represents each lock being
> > +in held_locks and lock B represents the lock to acquire.
> > +
> > +For example, only considering typical lock,
> > +
> > +       PROCESS X
> > +       --------------
> > +       acquire A
> > +
> > +       acquire B -> add a dependency 'A -> B'
> > +
> > +       acquire C -> add a dependency 'B -> C'
> > +
> > +       release C
> > +
> > +       release B
> > +
> > +       release A
> > +
> > +where A, B and C are different lock classes.
> > +
> > +When acquiring lock A, there's nothing in held_locks of PROCESS X thus
> > +no dependency is added. When acquiring lock B, lockdep detects and adds
> > +a new dependency 'A -> B' between lock A being in held_locks and lock B.
> > +And when acquiring lock C, lockdep also adds another dependency 'B -> C'
> > +for same reason. They are added when acquiring each lock, simply.
> > +
> > +NOTE: Even though every lock being in held_locks depends on the lock to
> > +acquire, lockdep does not add all dependencies between them because all
> > +of them can be covered by other dependencies except one dependency
> > +between the lock on top of held_locks and the lock to acquire, which
> > +must be added.
> 
> I am unable to understand the above sentence.  Can you break it into
> two more sentences?
> 
> > +
> > +Besides, we can expect several advantages from the limitation.
> > +
> > +1. Any lock being in held_locks cannot be released unconditionally if
> > +   the context is stuck, thus we can easily identify a dependency when
> > +   acquiring a lock.
> > +
> > +2. Considering only locks being in local held_locks of a single context
> > +   makes some races avoidable, even though it fails of course when
> > +   modifying its global dependency graph.
> > +
> > +3. To build a dependency graph, lockdep only needs to keep locks not
> > +   released yet. However relaxing the limitation, it might need to keep
> > +   even locks already released, additionally. See 'Crossrelease' section.
> > +
> > +CONCLUSION
> > +
> > +Given the limitation, the implementation becomes simple and efficient.
> > +
> > +
> > +Cons from the limitation
> > +------------------------
> > +
> > +Given the limitation, lockdep is applicable only to typical lock. For
> > +example, page lock for page access or completion for synchronization
> > +cannot play with lockdep having the limitation. However since page lock
> > +or completion also causes a deadlock, it would be better to detect a
> > +deadlock or its possibility even for them.
> > +
> > +Can we detect deadlocks below with lockdep having the limitation?
> > +
> > +Example 1:
> > +
> > +       PROCESS X       PROCESS Y
> > +       --------------  --------------
> > +       mutext_lock A
> > +                       lock_page B
> > +       lock_page B
> > +                       mutext_lock A // DEADLOCK
> > +       unlock_page B
> > +                       mutext_unlock A
> > +       mutex_unlock A
> > +                       unlock_page B
> > +
> > +where A and B are different lock classes.
> 
> I think the formatting is slightly off.  The events corresponding to
> process Y should be shifted more towards right.  The vertical ordering
> would still clearly indicate the order in which the events happened.
> 
> 
> > +
> > +No, we cannot.
> 
> I do not follow this example.  The context that acquired the mutex A
> or lock B also released it.  Should not lockdep be able to detect
> this?  I am guessing I have misunderstood which events occurred in
> which context.   Here is what I think the example is showing:
> 
> X acquired mutex A --> Y acquired lock B --> X tries to acquire B -->
> Y tries to acquire A -->  X and Y are in a deadlock since each of them
> holds a resource that the other needs.
> 
> > +
> > +Example 2:
> > +
> > +       PROCESS X       PROCESS Y       PROCESS Z
> > +       --------------  --------------  --------------
> > +                       mutex_lock A
> > +       lock_page B
> > +                       lock_page B
> > +                                       mutext_lock A // DEADLOCK
> > +                                       mutext_unlock A
> > +
> > +                                       unlock_page B held by X
> > +                       unlock_page B
> > +                       mutex_unlock A
> > +
> > +where A and B are different lock classes.
> > +
> > +No, we cannot.
> > +
> > +Example 3:
> > +
> > +       PROCESS X       PROCESS Y
> > +       --------------  --------------
> > +                       mutex_lock A
> > +       mutex_lock A
> > +       mutex_unlock A
> > +                       wait_for_complete B // DEADLOCK
> > +       complete B
> > +                       mutex_unlock A
> > +
> > +where A is a lock class and B is a completion variable.
> > +
> > +No, we cannot.
> > +
> > +CONCLUSION
> > +
> > +Given the limitation, lockdep cannot detect a deadlock or its
> > +possibility caused by page lock or completion.
> > +
> > +
> > +==============
> > +Generalization
> > +==============
> > +
> > +Relax the limitation
> > +--------------------
> > +
> > +Detecting and adding new dependencies into graph is very important for
> > +lockdep to work because adding a dependency means adding a chance to
> > +check if it causes a deadlock. More dependencies lockdep adds, more
> > +throughly it can work. Therefore Lockdep has to do its best to add as
> > +many true dependencies as possible.
> > +
> > +Relaxing the limitation, lockdep can add additional dependencies since
> > +it makes lockdep deal with additional ones creating the dependencies e.g.
> > +page lock or completion, which might be released in any context. Even so,
> > +it needs to be noted that behaviors adding dependencies created by
> > +typical lock don't need to be changed at all.
> > +
> > +For example, only considering typical lock, lockdep builds a graph like,
> > +
> > +A -> B -        -> F -> G
> > +        \      /
> > +         -> E -        -> L
> > +        /      \      /
> > +C -> D -        -> H -
> > +                      \
> > +                       -> I -> K
> > +                      /
> > +                   J -
> > +
> > +where A, B,..., L are different lock classes, and upper case letters
> > +represent typical lock.
> > +
> > +After the relaxing, the graph will have additional dependencies like,
> > +
> > +A -> B -        -> F -> G
> > +        \      /
> > +         -> E -        -> L -> c
> > +        /      \      /
> > +C -> D -        -> H -
> > +               /      \
> > +            a -        -> I -> K
> > +                      /
> > +              b -> J -
> > +
> > +where a, b, c, A, B,..., L are different lock classes, and upper case
> > +letters represent typical lock while lower case letters represent
> > +non-typical lock e.g. page lock and completion.
> > +
> > +However, it might suffer performance degradation since relaxing the
> > +limitation with which design and implementation of lockdep become
> > +efficient might introduce inefficiency inevitably. Each option, that is,
> > +strong detection or efficient detection has its pros and cons, thus the
> > +right of choice between two options should be given to users.
> > +
> > +Choosing efficient detection, lockdep only deals with locks satisfying,
> > +
> > +       A lock should be released within the context holding the lock.
> > +
> > +Choosing strong detection, lockdep deals with any locks satisfying,
> > +
> > +       A lock can be released in any context.
> > +
> > +In the latter, of course, some contexts are not allowed if they
> > +themselves cause a deadlock. For example, acquiring a lock in irq-safe
> > +context before releasing the lock in irq-unsafe context is not allowed,
> > +which after all ends in a cycle of a dependency chain, meaning a
> > +deadlock. Otherwise, any contexts are allowed to release it.
> > +
> > +CONCLUSION
> > +
> > +Relaxing the limitation, lockdep adds additional dependencies and gets
> > +additional chances to check if they cause a deadlock. It makes lockdep
> > +additionally deal with what might be released in any context.
> > +
> > +
> > +============
> > +Crossrelease
> > +============
> > +
> > +Introduce crossrelease
> > +----------------------
> > +
> > +To allow lockdep to add additional dependencies created by what might be
> > +released in any context, which we call 'crosslock', it's necessary to
> > +introduce a new feature which makes it possible to identify and add the
> > +dependencies. We call the feature 'crossrelease'. Crossrelease feature
> > +has to do,
> > +
> > +1. Identify a new dependency created by crosslock.
> > +2. Add the dependency into graph when identifying it.
> > +
> > +That's all. Once a meaningful dependency is added into graph, lockdep
> > +will work with the graph as it did. So the most important thing to do is
> > +to identify a dependency created by crosslock. Remind what a dependency
> > +is. For example, Lock A depends on lock B if 'lock A cannot be released
> > +if lock B isn't released'. See 'What causes deadlock' section.
> > +
> > +By definition, a lock depends on every lock having been added into
> > +held_locks in the lock's release context since the lock was acquired,
> > +because the lock cannot be released if the release context is stuck by
> > +any of dependent locks, not released. So lockdep should technically
> > +consider release contexts of locks to identify dependencies.
> > +
> > +It's no matter of course to typical lock because acquire context is same
> > +as release context for typical lock, which means lockdep would work with
> > +considering only acquire contexts for typical lock. However, for
> > +crosslock, lockdep cannot identify release context and any dependency
> > +until the crosslock will be actually released.
> > +
> > +Regarding crosslock, lockdep has to record all history by queueing all
> > +locks potentially creating dependencies so that real dependencies can be
> > +added using the history recorded when identifying release context. We
> > +call it 'commit', that is, to add dependencies in batches. See
> > +'Introduce commit' section.
> > +
> > +Of course, some actual deadlocks caused by crosslock cannot be detected
> > +at the time it happened, because the deadlocks cannot be indentified and
> > +detected until the crosslock will be actually released. But this way
> > +deadlock possibility can be detected and it's worth just possibility
> > +detection of deadlock. See 'What lockdep does' section.
> > +
> > +CONCLUSION
> > +
> > +With crossrelease feature, lockdep can works with what might be released
> > +in any context, namely, crosslock.
> > +
> > +
> > +Introduce commit
> > +----------------
> > +
> > +Crossrelease feature names it 'commit' to identify and add dependencies
> > +into graph in batches. Lockdep is already doing what commit does when
> > +acquiring a lock, for typical lock. However, that way must be changed
> > +for crosslock so that it identifies the crosslock's release context
> > +first and then does commit.
> > +
> > +The main reason why lockdep performs additional step, namely commit, for
> > +crosslock is that some dependencies by crosslock cannot be identified
> > +until the crosslock's release context is eventually identified, though
> > +some other dependencies by crosslock can. There are four kinds of
> > +dependencies to consider.
> > +
> > +1. 'typical lock A -> typical lock B' dependency
> > +
> > +   Just when acquiring lock B, lockdep can identify the dependency
> > +   between lock A and lock B as it did. Commit is unnecessary.
> > +
> > +2. 'typical lock A -> crosslock b' dependency
> > +
> > +   Just when acquiring crosslock b, lockdep can identify the dependency
> > +   between lock A and crosslock B as well. Commit is unnecessary, too.
> > +
> > +3. 'crosslock a -> typical lock B' dependency
> > +
> > +   When acquiring lock B, lockdep cannot identify the dependency. It can
> > +   be identified only when crosslock a is released. Commit is necessary.
> > +
> > +4. 'crosslock a -> crosslock b' dependency
> > +
> > +   Creating this kind of dependency directly is unnecessary since it can
> > +   be covered by other kinds of dependencies.
> > +
> > +Lockdep works without commit during dealing with only typical locks.
> > +However, it needs to perform commit step, once at least one crosslock is
> > +acquired, until all crosslocks in progress are released. Introducing
> > +commit, lockdep performs three steps i.e. acquire, commit and release.
> > +What lockdep should do in each step is like,
> > +
> > +1. Acquire
> > +
> > +   1) For typical lock
> > +
> > +       Lockdep does what it originally does and queues the lock so
> > +       that lockdep can check dependencies using it at commit step.
> > +
> > +   2) For crosslock
> > +
> > +       The crosslock is added to a global linked list so that lockdep
> > +       can check dependencies using it at commit step.
> > +
> > +2. Commit
> > +
> > +   1) For typical lock
> > +
> > +       N/A.
> > +
> > +   2) For crosslock
> > +
> > +       Lockdep checks and adds dependencies using data saved at acquire
> > +       step, as if the dependencies were added without commit step.
> > +
> > +3. Release
> > +
> > +   1) For typical lock
> > +
> > +       No change.
> > +
> > +   2) For crosslock
> > +
> > +       Lockdep just remove the crosslock from the global linked list,
> > +       to which it was added at acquire step.
> > +
> > +CONCLUSION
> > +
> > +Lockdep can detect a deadlock or its possibility caused by what might be
> > +released in any context, using commit step, where it checks and adds
> > +dependencies in batches.
> > +
> > +
> > +==============
> > +Implementation
> > +==============
> > +
> > +Data structures
> > +---------------
> > +
> > +Crossrelease feature introduces two main data structures.
> > +
> > +1. pend_lock (or plock)
> > +
> > +   This is an array embedded in task_struct, for keeping locks queued so
> > +   that real dependencies can be added using them at commit step. So
> > +   this data can be accessed locklessly within the owner context. The
> > +   array is filled when acquiring a typical lock and consumed when doing
> > +   commit. And it's managed in circular manner.
> > +
> > +2. cross_lock (or xlock)
> > +
> > +   This is a global linked list, for keeping all crosslocks in progress.
> > +   The list grows when acquiring a crosslock and is shrunk when
> > +   releasing the crosslock. lockdep_init_map_crosslock() should be used
> > +   to initialize a crosslock instance instead of lockdep_init_map() so
> > +   that lockdep can recognize it as crosslock.
> > +
> > +CONCLUSION
> > +
> > +Crossrelease feature uses 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.
> > +
> 
> Drop these conclusion, not need at all.
> 
> 
> > +
> > +How crossrelease works
> > +----------------------
> > +
> > +Let's take look at how crossrelease feature works step by step, starting
> > +from how lockdep works without crossrelease feaure.
> > +
> > +For example, the below is how lockdep works for typical lock.
> > +
> > +       RELEASE CONTEXT of A (= ACQUIRE CONTEXT of A)
> > +       --------------------
> > +       acquire A
> > +
> > +       acquire B -> add a dependency 'A -> B'
> > +
> > +       acquire C -> add a dependency 'B -> C'
> > +
> > +       release C
> > +
> > +       release B
> > +
> > +       release A
> > +
> > +where A, B and C are different lock classes, and upper case letters
> > +represent typical lock.
> > +
> > +After adding 'A -> B', the dependency graph will be,
> > +
> > +A -> B
> > +
> > +where A and B are different lock classes, and upper case letters
> > +represent typical lock.
> > +
> > +And after adding 'B -> C', the graph will be,
> > +
> > +A -> B -> C
> > +
> > +where A, B and C are different lock classes, and upper case letters
> > +represent typical lock.
> > +
> > +What if applying commit on typical locks? It's not necessary for typical
> > +lock. Just for showing what commit does.
> > +
> > +       RELEASE CONTEXT of A (= ACQUIRE CONTEXT of A)
> > +       --------------------
> > +       acquire A -> mark A as started (nothing before, no queueing)
> > +
> > +       acquire B -> mark B as started and queue B
> > +
> > +       acquire C -> mark C as started and queue C
> > +
> > +       release C -> commit C (nothing queued since C started)
> > +
> > +       release B -> commit B -> add a dependency 'B -> C'
> > +
> > +       release A -> commit A -> add dependencies 'A -> B' and 'A -> C'
> > +
> > +where A, B and C are different lock classes, and upper case letters
> > +represent typical lock.
> > +
> > +After doing commit A, B and C, the dependency graph becomes like,
> > +
> > +A -> B -> C
> > +
> > +where A, B and C are different lock classes, and upper case letters
> > +represent typical lock.
> > +
> > +NOTE: A dependency 'A -> C' is optimized out.
> > +
> > +Here we can see the final graph is same as the graph built without
> > +commit. Of course the former way leads to finish building the graph
> > +earlier than the latter way, which means we can detect a deadlock or its
> > +possibility sooner. So the former way would be prefered if possible. But
> > +we cannot avoid using the latter way using commit, for crosslock.
> > +
> > +Let's look at how commit works for crosslock.
> > +
> > +       RELEASE CONTEXT of a    ACQUIRE CONTEXT of a
> > +       --------------------    --------------------
> > +                               acquire a -> mark a as started
> > +
> > +       (serialized by some means e.g. barrier)
> > +
> > +       acquire D -> queue D
> > +                               acquire B -> queue B
> > +       release D
> > +                               acquire C -> add 'B -> C' and queue C
> > +       acquire E -> queue E
> > +                               acquire D -> add 'C -> D' and queue D
> > +       release E
> > +                               release D
> > +       release a -> commit a -> add 'a -> D' and 'a -> E'
> > +                               release C
> > +
> > +                               release B
> > +
> > +where a, B,..., E are different lock classes, and upper case letters
> > +represent typical lock while lower case letters represent crosslock.
> > +
> > +When acquiring crosslock a, no dependency can be added since there's
> > +nothing in the held_locks. However, crossrelease feature marks the
> > +crosslock as started, which means all locks to acquire from now are
> > +candidates which might create new dependencies later when identifying
> > +release context.
> > +
> > +When acquiring lock B, lockdep does what it originally does for typical
> > +lock and additionally queues the lock for later commit to refer to
> > +because it might be a dependent lock of the crosslock. It does same
> > +thing on lock C, D and E. And then two dependencies 'a -> D' and 'a -> E'
> > +are added when identifying the release context, at commit step.
> > +
> > +The final graph is, with crossrelease feature using commit,
> > +
> > +B -> C -
> > +        \
> > +         -> D
> > +        /
> > +     a -
> > +        \
> > +         -> E
> > +
> 
> Would not the graph also contain edges a->B and a->C, which lockdep
> would add as it usually does?
> 
> 
> > +where a, B,..., E are different lock classes, and upper case letters
> > +represent typical lock while lower case letters represent crosslock.
> > +
> > +However, without crossrelease feature, the final graph will be,
> > +
> > +B -> C -> D
> > +
> > +where B and C are different lock classes, and upper case letters
> > +represent typical lock.
> > +
> > +The former graph has two more dependencies 'a -> D' and 'a -> E' giving
> > +additional chances to check if they cause a deadlock. This way lockdep
> > +can detect a deadlock or its possibility caused by crosslock. Again,
> > +behaviors adding dependencies created by only typical locks are not
> > +changed at all.
> > +
> > +CONCLUSION
> > +
> > +Crossrelease works using commit for crosslock, leaving behaviors adding
> > +dependencies between only typical locks unchanged.
> > +
> > +
> > +=============
> > +Optimizations
> > +=============
> > +
> > +Avoid duplication
> > +-----------------
> > +
> > +Crossrelease feature uses a cache like what lockdep already uses for
> > +dependency chains, but this time it's for caching one dependency like
> > +'crosslock -> typical lock' crossing between two different context. Once
> > +that dependency is cached, same dependency will never be added any more.
> > +Even queueing unnecessary locks is also prevented based on the cache.
> > +
> > +CONCLUSION
> > +
> > +Crossrelease does not add any duplicate dependency.
> > +
> 
> No need for conclusion.
> 
> > +
> > +Avoid lock contention
> > +---------------------
> > +
> > +To keep all typical locks for later use, crossrelease feature adopts a
> > +local array embedded in task_struct, which makes accesses to arrays
> > +lockless by forcing each array to be accessed only within each own
> > +context. It's like how held_locks is accessed. Lockless implmentation is
> > +important since typical locks are very frequently accessed.
> > +
> > +CONCLUSION
> > +
> > +Crossrelease avoids lock contection as far as possible.
> > --
> > 1.9.1
> >
> 
> 
> No need for conclusion.
> 
> 
> Overall, I think I have generally understood what you are trying to do
> and how are doing it.  I think now I'll be able to better review the
> patches with actual.
> 
> Thanks!
> Nilay

Powered by blists - more mailing lists