Groups > linux.kernel > #1445151 > unrolled thread

Re: [RFC v2 13/13] lockdep: Add a document describing crossrelease feature

Started by	Byungchul Park <byungchul.park@lge.com>
First post	2016-07-18 03:50 +0200
Last post	2016-07-18 09:10 +0200
Articles	2 — 1 participant

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.

  Re: [RFC v2 13/13] lockdep: Add a document describing crossrelease  feature Byungchul Park <byungchul.park@lge.com> - 2016-07-18 03:50 +0200
    Re: [RFC v2 13/13] lockdep: Add a document describing crossrelease  feature Byungchul Park <byungchul.park@lge.com> - 2016-07-18 09:10 +0200

#1445151 — Re: [RFC v2 13/13] lockdep: Add a document describing crossrelease feature

From	Byungchul Park <byungchul.park@lge.com>
Date	2016-07-18 03:50 +0200
Subject	Re: [RFC v2 13/13] lockdep: Add a document describing crossrelease feature
Message-ID	<rW5QZ-88J-1@gated-at.bofh.it>

On Thu, Jul 07, 2016 at 06:30:03PM +0900, Byungchul Park wrote:
> Crossrelease feature introduces new concept and data structure. Thus
> the document is necessary. So added it.

Any opinions about this suggestion?

> 
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
>  Documentation/locking/crossrelease.txt | 457 +++++++++++++++++++++++++++++++++
>  1 file changed, 457 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..51b583b
> --- /dev/null
> +++ b/Documentation/locking/crossrelease.txt
> @@ -0,0 +1,457 @@
> +Crossrelease dependency check
> +=============================
> +
> +Started by Byungchul Park <byungchul.park@lge.com>
> +
> +Contents:
> +
> + (*) Introduction.
> +
> +     - What the lockdep checks.
> +
> + (*) What is a problem?
> +
> +     - Examples.
> +     - Lockdep's assumption.
> +     - Lockdep's limitation.
> +
> + (*) How to solve the problem.
> +
> +     - What causes deadlock?
> +     - Relax the assumption.
> +     - Relax the limitation.
> +
> + (*) Implementation.
> +
> +     - Introduce crosslock.
> +     - Introduce commit stage.
> +     - Acquire vs commit vs release.
> +     - Data structures.
> +
> + (*) Optimizations.
> +
> +
> +============
> +Introduction
> +============
> +
> +What the lockdep checks
> +-----------------------
> +
> +Lockdep checks dependency between locks and reports it if a deadlock
> +possibility is detected in advance or if an actual deadlock occures at
> +the time checking it.
> +
> +The former is more valuable because the possibility detection without
> +lockdep is much harder. When an actual deadlock occures, we can identify
> +what happens in the system by some means or other, even without lockdep.
> +
> +It checks dependency between locks (exactly lock classes, see
> +Documentation/locking/lockdep-design.txt for more) and builds the
> +relationship between them when the lock is acquired. Eventually it forms
> +the global dependency graph which connects between related locks based
> +on dependency they have, like e.g.
> +
> +A - B -       - F - G
> +       \     /
> +        - E -       - L
> +       /     \     /
> +C - D -       - H -
> +                   \
> +                    - I - K
> +                   /
> +                J -
> +
> +where A, B, C,..., L are different lock classes.
> +
> +Lockdep basically works based on this global dependency graph. The more
> +nodes it has, the stronger check can be performed.
> +
> +For example, lockdep can detect a deadlock when acquiring a C class lock
> +while it already held a K class lock, because it forms a cycle which
> +means deadlock, like
> +
> +A - B -       - F - G
> +       \     /
> +        - E -       - L
> +       /     \     /
> +C - D -       - H -
> +|                  \
> +|                   - I - K
> +|                  /      |
> +|               J -       |
> ++-------------------------+
> +
> +where A, B, C,..., L are different lock classes.
> +
> +If any of nodes making up the cycle was not built into the graph, we
> +cannot detect this kind of deadlock because there's no cycle. For
> +example, it might be
> +
> +A - B -       - F - G
> +       \     /
> +        - E -       L
> +       /
> +C - D -
> +|
> +|                   - I - K
> +|                  /      |
> +|               J -       |
> ++-------------------------+
> +
> +where A, B, C,..., L are different lock classes.
> +
> +Adding nodes and edges gives us additional opportunity to check if it
> +causes deadlock or not, so makes the detection stronger.
> +
> +
> +=================
> +What is a problem
> +=================
> +
> +Examples
> +--------
> +
> +Can we detect deadlocks descriped below, with lockdep? No.
> +
> +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
> +
> +We are not checking the dependency for lock_page() at all now.
> +
> +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
> +					(B was held by PROCESS X)
> +			unlock_page B
> +			mutex_unlock A
> +
> +We cannot detect this kind of deadlock with lockdep, even though we
> +apply the dependency check using lockdep on lock_page().
> +
> +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
> +
> +wait_for_complete() and complete() also can cause a deadlock, however
> +we cannot detect it with lockdep, either.
> +
> +
> +lockdep's assumption
> +--------------------
> +
> +Lockdep (not crossrelease featured one) assumes that,
> +
> +	A lock will be unlocked within the context holding the lock.
> +
> +Thus we can say that a lock has dependency with all locks being already
> +in held_locks. So we can check dependency and build the dependency graph
> +when acquiring it.
> +
> +
> +lockdep's limitation
> +--------------------
> +
> +It can be applied only to typical lock operations, e.g. spin_lock,
> +mutex and so on. However, e.g. lock_page() cannot play with the lockdep
> +thingy because it violates assumptions of lockdep, even though it's
> +considered as a lock for the page access.
> +
> +In the view point of lockdep, it must be released within the context
> +which held the lock, however, the page lock can be released by different
> +context from the context which held it. Another example,
> +wait_for_complete() and complete() are also the case by nature, which
> +the lockdep cannot deal with.
> +
> +
> +========================
> +How to solve the problem
> +========================
> +
> +What causes deadlock
> +--------------------
> +
> +Not only lock operations, but also any operations causing to wait or
> +spin for something can cause deadlock unless it's eventually *released*
> +by someone. The important point here is that the waiting or spinning
> +must be *released* by someone. In other words, we have to focus whether
> +the waiting or spinning can be *released* or not to check a deadlock
> +possibility, rather than the waiting or spinning itself.
> +
> +In this point of view, typical lock is a special case where the acquire
> +context is same as the release context, so no matter in which context
> +the checking is performed for typical lock.
> +
> +Of course, in order to be able to report deadlock imediately at the time
> +real deadlock actually occures, the checking must be performed before
> +actual blocking or spinning happens when acquiring it. However, deadlock
> +*possibility* can be detected and reported even the checking is done
> +when releasing it, which means the time we can identify the release
> +context.
> +
> +
> +Relax the assumption
> +--------------------
> +
> +Since whether waiting or spinning can be released or not is more
> +important to check deadlock possibility as decribed above, we can relax
> +the assumtion the lockdep has.
> +
> +	A lock can be unlocked in any context, unless the context
> +	itself causes a deadlock e.g. acquiring a lock in irq-safe
> +	context before releasing the lock in irq-unsafe context.
> +
> +A lock has dependency with all locks in the release context, having been
> +held since the lock was held. Thus basically we can check the dependency
> +only after we identify the release context at first. Of course, we can
> +identify the release context at the time acquiring a lock for typical
> +lock because the acquire context is same as the release context.
> +
> +However, generally if we cannot identify the release context at the time
> +acquiring a lock, we have to wait until the lock having been held will
> +be eventually released to identify the release context.
> +
> +
> +Relax the limitation
> +--------------------
> +
> +Given that the assumption is relaxed, we can check dependency and detect
> +deadlock possibility not only for typical lock, but also for lock_page()
> +using PG_locked, wait_for_xxx() and so on which might be released by
> +different context from the context which held the lock.
> +
> +
> +==============
> +Implementation
> +==============
> +
> +Introduce crosslock
> +-------------------
> +
> +Crossrelease feature names a lock "crosslock" if it is releasable by a
> +different context from the context which held the lock. All locks
> +having been held in the context unlocking the crosslock, since the
> +crosslock was held until eventually it's unlocked, have dependency with
> +the crosslock. That's the key idea to implement crossrelease feature.
> +
> +
> +Introduce commit stage
> +----------------------
> +
> +Crossrelease feature names it "commit", to check dependency and build
> +the dependency graph and chain in batches. Lockdep already performs what
> +the commit does, when acquiring a lock. This way it works for typical
> +lock, since it's guarrented that the acquire context is same as the
> +release context for that. However, that way must be changed for
> +crosslock so that it identify the release context when releasing the
> +crosslock and then performs the commit.
> +
> +Let's demonstrate it though several examples.
> +
> +The below is how the current lockdep works for typical lock. Note that
> +context 1 == context 2 for typical lock.
> +
> +	CONTEXT 1	CONTEXT 2
> +	acquiring A	releasing A
> +	-------------	-------------
> +	acquire A	acquire A
> +
> +	acquire B	acquire B -> build "A - B"
> +
> +	acquire C	acquire C -> build "A - C"
> +
> +	release C	release C
> +
> +	release B	release B
> +
> +	release A	release A
> +
> +After building "A - B", the dependency graph forms like,
> +
> +A - B
> +
> +And after building "A - C", the dependency graph forms like,
> +
> +    - B
> +   /
> +A -
> +   \
> +    - C
> +
> +What if we apply the commit to lockdep for typical lock? Of course, it's
> +not necessary for typical lock. Just a example for what the commit does.
> +
> +	CONTEXT 1	CONTEXT 2
> +	acquiring A	releasing A
> +	-------------	-------------
> +	acquire A	acquire A -> mark A started
> +
> +	acquire B	acquire B -> queue B
> +
> +	acquire C	acquire C -> queue C
> +
> +	release C	release C
> +
> +	release B	release B
> +
> +	release A	release A -> commit A (build "A - B", "A - C")
> +
> +After commiting A, the dependency graph forms like, at a time
> +
> +    - B
> +   /
> +A -
> +   \
> +    - C
> +
> +Here we can see both the former and the latter end in building a same
> +dependency graph consisting of "A - B" and "A - C". Of course, the
> +former can build the graph earlier than the latter, which means the
> +former can detect a deadlock sooner, maybe, as soon as possible. So the
> +former would be prefered if possible.
> +
> +Let's look at the way the commit works for crosslock.
> +
> +	CONTEXT 1	CONTEXT 2
> +	acquiring A	releasing A
> +	-------------	-------------
> +	lock A
> +	acquire A -> mark A started
> +
> +	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ <- serialized by some means
> +
> +			acquire X -> queue X
> +			lock X
> +	acquire B
> +			release X
> +	acquire C
> +			acquire Y -> queue Y
> +	release C
> +			release Y
> +	release B
> +			release A -> commit A (build "A - X", "A - Y")
> +
> +where A is a crosslock and the others are typical locks.
> +
> +Since a crosslock is held, it starts to queue all candidates whenever
> +acquiring typical lock, and keep it until finally it will be released.
> +Then it can commit all proper candidates queued until now. In other
> +words, it checks dependency and builds the dependency graph and chain
> +at the commit stage.
> +
> +And it is serialized so that the sequence, A -> X -> Y can be seen,
> +using atomic operations and proper barriers.
> +
> +
> +Acquire vs commit vs release
> +----------------------------
> +
> +What the lockdep should do in each stage to make it work even for
> +crosslock is like, (Note that it does not change any current logic
> +by which lockdep works, but only adds additional detection capability.)
> +
> +1. Acquire
> +
> +	1) For typical lock
> +
> +		It's queued into additional data structure so that the
> +		commit stage can check depedndency and build the
> +		dependency graph and chain with this later.
> +
> +	2) For crosslock
> +
> +		It's added to the global linked list so that the commit
> +		stage can check dependency and build the dependency
> +		graph and chain with this later.
> +
> +2. Commit
> +
> +	1) For typical lock
> +
> +		N/A.
> +
> +	2) For crosslock
> +
> +		It checks dependency and builds the dependency graph and
> +		chain with data saved in the acquire stage. Here, we
> +		establish dependency between the crosslock we are
> +		unlocking now and all locks in that context, having been
> +		held since the lock was held. Of course, it avoids
> +		unnecessary checking and building as far as possible.
> +
> +3. Release
> +
> +	1) For typical lock
> +
> +		No change.
> +
> +	2) For crosslock
> +
> +		Just remove this crosslock from the global linked list,
> +		to which the crosslock was added at acquire stage.
> +		Release operation should be used with commit operation
> +		together for crosslock.
> +
> +
> +Data structures
> +---------------
> +
> +Crossrelease feature introduces two new data structures.
> +
> +1. pend_lock (or plock)
> +
> +	This is for keeping locks waiting to be committed so that the
> +	actual dependency graph and chain can be built in the commit
> +	stage. Every task_struct has a pend_lock array to keep these
> +	locks. pend_lock entry will be consumed and filled whenever
> +	lock_acquire() is called for typical lock and will be flushed,
> +	namely committed at proper time. And this array is managed by
> +	circular buffer mean.
> +
> +2. cross_lock (or xlock)
> +
> +	This keeps some additional data only for crosslock. One
> +	instance exists per one crosslock's lockdep_map.
> +	lockdep_init_map_crosslock() should be used instead of
> +	lockdep_init_map() to use a lock as a crosslock.
> +
> +
> +=============
> +Optimizations
> +=============
> +
> +Adding a pend_lock is an operation which very frequently happened
> +because it happens whenever a typical lock is acquired. So the operation
> +is implemented locklessly using rcu mechanism if possible. Unfortunitly,
> +we cannot apply this optimization if any object managed by rcu e.g.
> +xlock is on stack or somewhere else where it can be freed or destroyed
> +unpredictably.
> +
> +And chain cache for crosslock is also used to avoid unnecessary checking
> +and building dependency, like how the lockdep is already doing for that
> +purpose for typical lock.
> +
> -- 
> 1.9.1

[toc] | [next] | [standalone]

#1445265

From	Byungchul Park <byungchul.park@lge.com>
Date	2016-07-18 09:10 +0200
Message-ID	<rWaQG-352-31@gated-at.bofh.it>
In reply to	#1445151

On Mon, Jul 18, 2016 at 10:39:19AM +0900, Byungchul Park wrote:
> On Thu, Jul 07, 2016 at 06:30:03PM +0900, Byungchul Park wrote:
> > Crossrelease feature introduces new concept and data structure. Thus
> > the document is necessary. So added it.
> 
> Any opinions about this suggestion?

Just to be sure, I have to enhance this document more yet, however I'm sure
I already introduced the general outline through this document. It was the
purpose of this premature document which I sent early even though it's not
perfect yet.

> 
> > 
> > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > ---
> >  Documentation/locking/crossrelease.txt | 457 +++++++++++++++++++++++++++++++++
> >  1 file changed, 457 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..51b583b
> > --- /dev/null
> > +++ b/Documentation/locking/crossrelease.txt
> > @@ -0,0 +1,457 @@
> > +Crossrelease dependency check
> > +=============================
> > +
> > +Started by Byungchul Park <byungchul.park@lge.com>
> > +
> > +Contents:
> > +
> > + (*) Introduction.
> > +
> > +     - What the lockdep checks.
> > +
> > + (*) What is a problem?
> > +
> > +     - Examples.
> > +     - Lockdep's assumption.
> > +     - Lockdep's limitation.
> > +
> > + (*) How to solve the problem.
> > +
> > +     - What causes deadlock?
> > +     - Relax the assumption.
> > +     - Relax the limitation.
> > +
> > + (*) Implementation.
> > +
> > +     - Introduce crosslock.
> > +     - Introduce commit stage.
> > +     - Acquire vs commit vs release.
> > +     - Data structures.
> > +
> > + (*) Optimizations.
> > +
> > +
> > +============
> > +Introduction
> > +============
> > +
> > +What the lockdep checks
> > +-----------------------
> > +
> > +Lockdep checks dependency between locks and reports it if a deadlock
> > +possibility is detected in advance or if an actual deadlock occures at
> > +the time checking it.
> > +
> > +The former is more valuable because the possibility detection without
> > +lockdep is much harder. When an actual deadlock occures, we can identify
> > +what happens in the system by some means or other, even without lockdep.
> > +
> > +It checks dependency between locks (exactly lock classes, see
> > +Documentation/locking/lockdep-design.txt for more) and builds the
> > +relationship between them when the lock is acquired. Eventually it forms
> > +the global dependency graph which connects between related locks based
> > +on dependency they have, like e.g.
> > +
> > +A - B -       - F - G
> > +       \     /
> > +        - E -       - L
> > +       /     \     /
> > +C - D -       - H -
> > +                   \
> > +                    - I - K
> > +                   /
> > +                J -
> > +
> > +where A, B, C,..., L are different lock classes.
> > +
> > +Lockdep basically works based on this global dependency graph. The more
> > +nodes it has, the stronger check can be performed.
> > +
> > +For example, lockdep can detect a deadlock when acquiring a C class lock
> > +while it already held a K class lock, because it forms a cycle which
> > +means deadlock, like
> > +
> > +A - B -       - F - G
> > +       \     /
> > +        - E -       - L
> > +       /     \     /
> > +C - D -       - H -
> > +|                  \
> > +|                   - I - K
> > +|                  /      |
> > +|               J -       |
> > ++-------------------------+
> > +
> > +where A, B, C,..., L are different lock classes.
> > +
> > +If any of nodes making up the cycle was not built into the graph, we
> > +cannot detect this kind of deadlock because there's no cycle. For
> > +example, it might be
> > +
> > +A - B -       - F - G
> > +       \     /
> > +        - E -       L
> > +       /
> > +C - D -
> > +|
> > +|                   - I - K
> > +|                  /      |
> > +|               J -       |
> > ++-------------------------+
> > +
> > +where A, B, C,..., L are different lock classes.
> > +
> > +Adding nodes and edges gives us additional opportunity to check if it
> > +causes deadlock or not, so makes the detection stronger.
> > +
> > +
> > +=================
> > +What is a problem
> > +=================
> > +
> > +Examples
> > +--------
> > +
> > +Can we detect deadlocks descriped below, with lockdep? No.
> > +
> > +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
> > +
> > +We are not checking the dependency for lock_page() at all now.
> > +
> > +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
> > +					(B was held by PROCESS X)
> > +			unlock_page B
> > +			mutex_unlock A
> > +
> > +We cannot detect this kind of deadlock with lockdep, even though we
> > +apply the dependency check using lockdep on lock_page().
> > +
> > +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
> > +
> > +wait_for_complete() and complete() also can cause a deadlock, however
> > +we cannot detect it with lockdep, either.
> > +
> > +
> > +lockdep's assumption
> > +--------------------
> > +
> > +Lockdep (not crossrelease featured one) assumes that,
> > +
> > +	A lock will be unlocked within the context holding the lock.
> > +
> > +Thus we can say that a lock has dependency with all locks being already
> > +in held_locks. So we can check dependency and build the dependency graph
> > +when acquiring it.
> > +
> > +
> > +lockdep's limitation
> > +--------------------
> > +
> > +It can be applied only to typical lock operations, e.g. spin_lock,
> > +mutex and so on. However, e.g. lock_page() cannot play with the lockdep
> > +thingy because it violates assumptions of lockdep, even though it's
> > +considered as a lock for the page access.
> > +
> > +In the view point of lockdep, it must be released within the context
> > +which held the lock, however, the page lock can be released by different
> > +context from the context which held it. Another example,
> > +wait_for_complete() and complete() are also the case by nature, which
> > +the lockdep cannot deal with.
> > +
> > +
> > +========================
> > +How to solve the problem
> > +========================
> > +
> > +What causes deadlock
> > +--------------------
> > +
> > +Not only lock operations, but also any operations causing to wait or
> > +spin for something can cause deadlock unless it's eventually *released*
> > +by someone. The important point here is that the waiting or spinning
> > +must be *released* by someone. In other words, we have to focus whether
> > +the waiting or spinning can be *released* or not to check a deadlock
> > +possibility, rather than the waiting or spinning itself.
> > +
> > +In this point of view, typical lock is a special case where the acquire
> > +context is same as the release context, so no matter in which context
> > +the checking is performed for typical lock.
> > +
> > +Of course, in order to be able to report deadlock imediately at the time
> > +real deadlock actually occures, the checking must be performed before
> > +actual blocking or spinning happens when acquiring it. However, deadlock
> > +*possibility* can be detected and reported even the checking is done
> > +when releasing it, which means the time we can identify the release
> > +context.
> > +
> > +
> > +Relax the assumption
> > +--------------------
> > +
> > +Since whether waiting or spinning can be released or not is more
> > +important to check deadlock possibility as decribed above, we can relax
> > +the assumtion the lockdep has.
> > +
> > +	A lock can be unlocked in any context, unless the context
> > +	itself causes a deadlock e.g. acquiring a lock in irq-safe
> > +	context before releasing the lock in irq-unsafe context.
> > +
> > +A lock has dependency with all locks in the release context, having been
> > +held since the lock was held. Thus basically we can check the dependency
> > +only after we identify the release context at first. Of course, we can
> > +identify the release context at the time acquiring a lock for typical
> > +lock because the acquire context is same as the release context.
> > +
> > +However, generally if we cannot identify the release context at the time
> > +acquiring a lock, we have to wait until the lock having been held will
> > +be eventually released to identify the release context.
> > +
> > +
> > +Relax the limitation
> > +--------------------
> > +
> > +Given that the assumption is relaxed, we can check dependency and detect
> > +deadlock possibility not only for typical lock, but also for lock_page()
> > +using PG_locked, wait_for_xxx() and so on which might be released by
> > +different context from the context which held the lock.
> > +
> > +
> > +==============
> > +Implementation
> > +==============
> > +
> > +Introduce crosslock
> > +-------------------
> > +
> > +Crossrelease feature names a lock "crosslock" if it is releasable by a
> > +different context from the context which held the lock. All locks
> > +having been held in the context unlocking the crosslock, since the
> > +crosslock was held until eventually it's unlocked, have dependency with
> > +the crosslock. That's the key idea to implement crossrelease feature.
> > +
> > +
> > +Introduce commit stage
> > +----------------------
> > +
> > +Crossrelease feature names it "commit", to check dependency and build
> > +the dependency graph and chain in batches. Lockdep already performs what
> > +the commit does, when acquiring a lock. This way it works for typical
> > +lock, since it's guarrented that the acquire context is same as the
> > +release context for that. However, that way must be changed for
> > +crosslock so that it identify the release context when releasing the
> > +crosslock and then performs the commit.
> > +
> > +Let's demonstrate it though several examples.
> > +
> > +The below is how the current lockdep works for typical lock. Note that
> > +context 1 == context 2 for typical lock.
> > +
> > +	CONTEXT 1	CONTEXT 2
> > +	acquiring A	releasing A
> > +	-------------	-------------
> > +	acquire A	acquire A
> > +
> > +	acquire B	acquire B -> build "A - B"
> > +
> > +	acquire C	acquire C -> build "A - C"
> > +
> > +	release C	release C
> > +
> > +	release B	release B
> > +
> > +	release A	release A
> > +
> > +After building "A - B", the dependency graph forms like,
> > +
> > +A - B
> > +
> > +And after building "A - C", the dependency graph forms like,
> > +
> > +    - B
> > +   /
> > +A -
> > +   \
> > +    - C
> > +
> > +What if we apply the commit to lockdep for typical lock? Of course, it's
> > +not necessary for typical lock. Just a example for what the commit does.
> > +
> > +	CONTEXT 1	CONTEXT 2
> > +	acquiring A	releasing A
> > +	-------------	-------------
> > +	acquire A	acquire A -> mark A started
> > +
> > +	acquire B	acquire B -> queue B
> > +
> > +	acquire C	acquire C -> queue C
> > +
> > +	release C	release C
> > +
> > +	release B	release B
> > +
> > +	release A	release A -> commit A (build "A - B", "A - C")
> > +
> > +After commiting A, the dependency graph forms like, at a time
> > +
> > +    - B
> > +   /
> > +A -
> > +   \
> > +    - C
> > +
> > +Here we can see both the former and the latter end in building a same
> > +dependency graph consisting of "A - B" and "A - C". Of course, the
> > +former can build the graph earlier than the latter, which means the
> > +former can detect a deadlock sooner, maybe, as soon as possible. So the
> > +former would be prefered if possible.
> > +
> > +Let's look at the way the commit works for crosslock.
> > +
> > +	CONTEXT 1	CONTEXT 2
> > +	acquiring A	releasing A
> > +	-------------	-------------
> > +	lock A
> > +	acquire A -> mark A started
> > +
> > +	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ <- serialized by some means
> > +
> > +			acquire X -> queue X
> > +			lock X
> > +	acquire B
> > +			release X
> > +	acquire C
> > +			acquire Y -> queue Y
> > +	release C
> > +			release Y
> > +	release B
> > +			release A -> commit A (build "A - X", "A - Y")
> > +
> > +where A is a crosslock and the others are typical locks.
> > +
> > +Since a crosslock is held, it starts to queue all candidates whenever
> > +acquiring typical lock, and keep it until finally it will be released.
> > +Then it can commit all proper candidates queued until now. In other
> > +words, it checks dependency and builds the dependency graph and chain
> > +at the commit stage.
> > +
> > +And it is serialized so that the sequence, A -> X -> Y can be seen,
> > +using atomic operations and proper barriers.
> > +
> > +
> > +Acquire vs commit vs release
> > +----------------------------
> > +
> > +What the lockdep should do in each stage to make it work even for
> > +crosslock is like, (Note that it does not change any current logic
> > +by which lockdep works, but only adds additional detection capability.)
> > +
> > +1. Acquire
> > +
> > +	1) For typical lock
> > +
> > +		It's queued into additional data structure so that the
> > +		commit stage can check depedndency and build the
> > +		dependency graph and chain with this later.
> > +
> > +	2) For crosslock
> > +
> > +		It's added to the global linked list so that the commit
> > +		stage can check dependency and build the dependency
> > +		graph and chain with this later.
> > +
> > +2. Commit
> > +
> > +	1) For typical lock
> > +
> > +		N/A.
> > +
> > +	2) For crosslock
> > +
> > +		It checks dependency and builds the dependency graph and
> > +		chain with data saved in the acquire stage. Here, we
> > +		establish dependency between the crosslock we are
> > +		unlocking now and all locks in that context, having been
> > +		held since the lock was held. Of course, it avoids
> > +		unnecessary checking and building as far as possible.
> > +
> > +3. Release
> > +
> > +	1) For typical lock
> > +
> > +		No change.
> > +
> > +	2) For crosslock
> > +
> > +		Just remove this crosslock from the global linked list,
> > +		to which the crosslock was added at acquire stage.
> > +		Release operation should be used with commit operation
> > +		together for crosslock.
> > +
> > +
> > +Data structures
> > +---------------
> > +
> > +Crossrelease feature introduces two new data structures.
> > +
> > +1. pend_lock (or plock)
> > +
> > +	This is for keeping locks waiting to be committed so that the
> > +	actual dependency graph and chain can be built in the commit
> > +	stage. Every task_struct has a pend_lock array to keep these
> > +	locks. pend_lock entry will be consumed and filled whenever
> > +	lock_acquire() is called for typical lock and will be flushed,
> > +	namely committed at proper time. And this array is managed by
> > +	circular buffer mean.
> > +
> > +2. cross_lock (or xlock)
> > +
> > +	This keeps some additional data only for crosslock. One
> > +	instance exists per one crosslock's lockdep_map.
> > +	lockdep_init_map_crosslock() should be used instead of
> > +	lockdep_init_map() to use a lock as a crosslock.
> > +
> > +
> > +=============
> > +Optimizations
> > +=============
> > +
> > +Adding a pend_lock is an operation which very frequently happened
> > +because it happens whenever a typical lock is acquired. So the operation
> > +is implemented locklessly using rcu mechanism if possible. Unfortunitly,
> > +we cannot apply this optimization if any object managed by rcu e.g.
> > +xlock is on stack or somewhere else where it can be freed or destroyed
> > +unpredictably.
> > +
> > +And chain cache for crosslock is also used to avoid unnecessary checking
> > +and building dependency, like how the lockdep is already doing for that
> > +purpose for typical lock.
> > +
> > -- 
> > 1.9.1

[toc] | [prev] | [standalone]

csiph-web