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

Groups > linux.kernel > #1435002 > unrolled thread

[PATCH] lockdep: Add a document describing crossrelease feature

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

  [PATCH] lockdep: Add a document describing crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-07-01 06:20 +0200
    Re: [PATCH] lockdep: Add a document describing crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2016-07-01 12:50 +0200
      Re: [PATCH] lockdep: Add a document describing crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-07-04 08:50 +0200
        Re: [PATCH] lockdep: Add a document describing crossrelease feature Boqun Feng <boqun.feng@gmail.com> - 2016-07-06 02:50 +0200
          Re: [PATCH] lockdep: Add a document describing crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-07-06 04:20 +0200
            Re: [PATCH] lockdep: Add a document describing crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-07-06 07:40 +0200
              Re: [PATCH] lockdep: Add a document describing crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2016-07-06 10:00 +0200
                Re: [PATCH] lockdep: Add a document describing crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-07-06 10:20 +0200

#1435002 — [PATCH] lockdep: Add a document describing crossrelease feature

Crossrelease feature introduces new concept and data structure. Thus a
document helping understand it is necessary. So added it.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 Documentation/locking/crossrelease.txt | 276 +++++++++++++++++++++++++++++++++
 1 file changed, 276 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..98851ef
--- /dev/null
+++ b/Documentation/locking/crossrelease.txt
@@ -0,0 +1,276 @@
+Crossrelease lock dependency check
+==================================
+
+Started by Byungchul Park <byungchul.park@lge.com>
+
+Contents:
+
+ (*) What is a problem?
+
+     - Original lockdep's assumptions.
+     - Original lockdep's limitation.
+
+ (*) How to solve the problem.
+
+     - What causes deadlock?
+     - Relax the assumptions.
+     - Introduce "crosslock".
+     - Introduce "commit" stage.
+     - Acquire vs commit vs release
+
+ (*) Implementation.
+
+     - Data structures.
+     - Optimizations.
+
+
+=================
+What is a problem
+=================
+
+Can we detect deadlocks descriped below with original 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 currently not checking lock dependency for lock_page(), which is
+for exclusive access to pages.
+
+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 original lockdep, even
+though we enable lock dependency check 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 original lockdep, either.
+
+
+Original lockdep's assumptions
+------------------------------
+
+Original lockdep (not crossrelease featured lockdep) assumes that,
+
+1. A lock will be unlocked within the context holding the lock.
+2. A lock has dependency with all locks already held in held_locks.
+2. Acquiring is more important than releasing, to check its dependency.
+
+
+Original lockdep's limitation
+-----------------------------
+
+Therefore, the original lockdep has limitations. It can be applied only
+to typical lock operations, e.g. spin_lock, mutex, semaphore and the
+like. Even though lock_page() can be considered as a lock, it cannot be
+used with lockdep because it violates assumptions of original lockdep.
+In the view point of original lockdep, a lock must be released within
+the context having held the lock, however, a lock using lock_page() can
+be released by different context from the context having held the lock.
+wait_for_complete() is also the case by nature, in which original
+lockdep cannot deal with it.
+
+
+========================
+How to solve the problem
+========================
+
+What causes deadlock
+--------------------
+
+Not only lock operations, but also any operations causing to wait or
+spin it e.g. all wait operations for an event, lock_page() and so on
+can cause deadlock unless it's eventually released by someone. The most
+important point here is that the waiting or spinning must be *released*
+by someone. In other words, we have to focus whether the waiting and
+spinning can be *released* or not to avoid deadlock, rather than
+waiting or spinning it itself.
+
+
+Relax the assumptions
+---------------------
+
+We can relax the assumtions the original lockdep has, which is not
+necessary to check dependency and detect a deadlock.
+
+1. 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.
+
+2. A lock has dependency with all locks in the releasing context, having
+   been held since the lock was held. Thus we can check the dependency
+   only after we identify the releasing context at first. Of course,
+   if we consider only typical lock e.g. spin lock, mutex, semaphore
+   and so on, then we can identify the releasing context at the time
+   acquiring a lock because the releasing context is same as the
+   releasing context for the typical lock. However, generally we have to
+   wait until the lock having been held will be eventually released to
+   identify the releasing context. We can say that the original lockdep
+   is a special case among all cases this crossrelease feature can deal
+   with.
+
+3. Releasing is more important than acquiring to check its dependency.
+   Compare to the third assumption of original lockdep.
+
+
+Introduce "crosslock"
+---------------------
+
+Crossrelease feature names a lock "crosslock" if it is releasable by a
+different context from the context having acquired the lock. All locks
+having been held in the context unlocking the crosslock until
+eventually the crosslock will be 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 tree and chain. That is, the original lockdep is already
+doing the so-called commit, when acquiring it. In the strict sense, the
+checking and building must be done in the releasing context, as
+described in the "What causes a deadlock" subsection above. However, it
+will work no matter which context is used for typical lock, since it's
+guarrented that the acquiring context is same as the releasing context
+as described above. So we can commit it in the acquiring context for
+typical lock.
+
+How the original lockdep works:
+
+	acquire (including commit operation) -> release
+
+What if we consider a crosslock? For crosslock, the way lockdep works
+must be changed so that the releasing context is considered instead.
+Again, the releasing context is more important than the acquiring
+context, to check dependency and detect a deadlock. Thus checking
+dependency and building the dependency tree and chain, namely commit
+must be done in the releasing context, especially for crosslock.
+
+How the crossrelease lockdep works for crosslock:
+
+	acquire -> (context may be changed) -> commit -> release
+
+
+Acquire vs commit vs release
+----------------------------
+
+The things to do when acquiring and releasing a lock will be slightly
+changed in other to make lockdep can work even for crosslock. And an
+additional stage, commit, is placed between acquire and release.
+
+1. Acquire
+
+	1) For typical lock
+
+		The lock will be added not only to held_locks of the
+		current's task_struct, but also to additional structure
+		so that the commit stage can check dependency and build
+		the dependency tree and chain with that later.
+
+	2) For crosslock
+
+		The lock will be added to a global linked list so that
+		the commit stage can check dependency and build the
+		dependency tree and chain with that later.
+
+2. Commit
+
+	1) For typical lock
+
+		N/A.
+
+	2) For crosslock
+
+		It checks dependency and builds the dependency tree and
+		chain with data saved in the acquire stage. Here, we
+		establish dependency between the crosslock we are
+		unlocking now and all locks in the context unlocking it,
+		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 the target 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, in order to build a dependency
+		chain properly.
+
+
+==============
+Implementation
+==============
+
+Data structures
+---------------
+
+Crossrelease feature introduces two new data structures.
+
+1. pend_lock (== plock)
+
+	This is for keeping locks waiting to be committed so that the
+	actual dependency tree and chain is built in the commit stage.
+	Every task_struct has an pend_lock array to keep those 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.
+
+2. cross_lock (== xlock)
+
+	This keeps some additional data only for crosslock. One
+	cross_lock exists per one 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 very frequently happened because it
+happens whenever a typical lock is acquired. So the operation is
+implemented locklessly using rcu mechanism unless the xlock instance
+can be freed or destroyed unpredictably e.g. the instance is on stack.
+
+And chain cache for crosslock is also used to avoid unnecessary checking
+and building dependency, like how the original lockdep is doing for that
+purpose.
-- 
1.9.1

[toc] | [next] | [standalone]

#1435251

So I really could not understand your initial changelogs, this text
seem to be somewhat better, so let me try and comment on this.

On Fri, Jul 01, 2016 at 01:15:38PM +0900, Byungchul Park wrote:

> +++ b/Documentation/locking/crossrelease.txt
> @@ -0,0 +1,276 @@
> +Crossrelease lock dependency check
> +==================================
> +
> +Started by Byungchul Park <byungchul.park@lge.com>
> +
> +Contents:
> +
> + (*) What is a problem?
> +
> +     - Original lockdep's assumptions.
> +     - Original lockdep's limitation.

Their form doesn't make sense if we ever commit this. Nobody knows or
cares about an 'original' lockdep. There is only now.

> +Original lockdep's assumptions
> +------------------------------
> +
> +Original lockdep (not crossrelease featured lockdep) assumes that,
> +
> +1. A lock will be unlocked within the context holding the lock.

This is lock owner semantics; that is, each lock has a clear owner.
Which is a sane assumption, and a hard requirement for PI. Remember, all
this comes from the RT tree.

!owner locks cannot do PI and thus cannot be used for code you want to
provide deterministic behaviour with.

> +2. A lock has dependency with all locks already held in held_locks.

That's not really an assumption, given 1, this is a fact. An owner lock
can only depend on locks currently held. This is a corner stone of
proving things.

> +2. Acquiring is more important than releasing, to check its dependency.

s/2/3/

That's not an assumption; that's a hard requirement. Since the acquire
is the one blocking, you _have_ to check for cycles before you block,
otherwise you'll hit the deadlock and not get a report, because you're
deadlocked.

> +Original lockdep's limitation
> +-----------------------------
> +
> +Therefore, the original lockdep has limitations. It can be applied only
> +to typical lock operations, e.g. spin_lock, mutex, semaphore and the

This is wrong, semaphores are very much not covered by lockdep since
they do not have owner semantics (what you call crossmuck). (this is
the distinction between a binary semaphore and a mutex)

> +What causes deadlock
> +--------------------
> +
> +Not only lock operations, but also any operations causing to wait or
> +spin it e.g. all wait operations for an event, lock_page() and so on
> +can cause deadlock unless it's eventually released by someone. The most
> +important point here is that the waiting or spinning must be *released*
> +by someone. In other words, we have to focus whether the waiting and
> +spinning can be *released* or not to avoid deadlock, rather than
> +waiting or spinning it itself.

But since its the blocking that _is_ the deadlock, you'll never get your
report.

IOW, you rely on future behaviour to tell if now can make forwards
progress. This already implies a well formed program. You're inverting
causality.

> +Relax the assumptions
> +---------------------
> +
> +We can relax the assumtions the original lockdep has, which is not
> +necessary to check dependency and detect a deadlock.
> +
> +1. 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.

You fail to say how this preserves correctness. By relaxing this you
loose the held_lock dependencies and you destroy the entire proof that
currently underpins lockdep.

> +2. A lock has dependency with all locks in the releasing context, having
> +   been held since the lock was held.

But you cannot tell this. The 'since the lock was held' thing fully
depends on timing and is not fundamentally correct.

			lock(A)
			unlock(A)
	lock(A)
	wait_for(B)
	unlock(A)
			wake(B)

Between the wait_for(B) and wake(B), _nothing_ has been held, yet still
there's the deadlock potential.

And note that if the timing was 'right', you would never get to wake(B)
because deadlock, so you'd never establish that there would be a
deadlock.

>                                        Thus we can check the dependency
> +   only after we identify the releasing context at first. Of course,
> +   if we consider only typical lock e.g. spin lock, mutex, semaphore
> +   and so on, then we can identify the releasing context at the time
> +   acquiring a lock because the releasing context is same as the
> +   releasing context for the typical lock. However, generally we have to
> +   wait until the lock having been held will be eventually released to
> +   identify the releasing context. We can say that the original lockdep
> +   is a special case among all cases this crossrelease feature can deal
> +   with.

I'm not sure you can say this at all; you've no proof of correctness
from which this special case flows.

> +3. Releasing is more important than acquiring to check its dependency.
> +   Compare to the third assumption of original lockdep.

Again, you're inverting causality afaict. You depend on the future
happening to say now is correct.

> +Introduce "crosslock"
> +---------------------
> +
> +Crossrelease feature names a lock "crosslock" if it is releasable by a
> +different context from the context having acquired the lock. All locks
> +having been held in the context unlocking the crosslock until
> +eventually the crosslock will be unlocked, have dependency with the
> +crosslock. That's the key idea to implement crossrelease feature.

_all_ locks? That implies infinite storage, which is hardly feasible. If
you limit it, the limit would seem arbitrary and you loose your proof
(in so far as I can see, because you're not actually giving any).


Please, give a coherent, mathematical proof of correctness.

Because I'm not seeing how this thing would work.

[toc] | [prev] | [next] | [standalone]

#1436127

On Fri, Jul 01, 2016 at 12:45:21PM +0200, Peter Zijlstra wrote:
> > +Crossrelease lock dependency check
> > +==================================
> > +
> > +Started by Byungchul Park <byungchul.park@lge.com>
> > +
> > +Contents:
> > +
> > + (*) What is a problem?
> > +
> > +     - Original lockdep's assumptions.
> > +     - Original lockdep's limitation.
> 
> Their form doesn't make sense if we ever commit this. Nobody knows or
> cares about an 'original' lockdep. There is only now.

Right. I wonder what word would be proper. Basic? Or just lockdep?

> > +Original lockdep's assumptions
> > +------------------------------
> > +
> > +Original lockdep (not crossrelease featured lockdep) assumes that,
> > +
> > +1. A lock will be unlocked within the context holding the lock.
> 
> This is lock owner semantics; that is, each lock has a clear owner.
> Which is a sane assumption, and a hard requirement for PI. Remember, all
> this comes from the RT tree.

I agree it's hard requirment for PI.

> 
> !owner locks cannot do PI and thus cannot be used for code you want to
> provide deterministic behaviour with.

I am sorry for that I don't understand this sentence. Could you explain
it more?

> > +2. A lock has dependency with all locks already held in held_locks.
> 
> That's not really an assumption, given 1, this is a fact. An owner lock
> can only depend on locks currently held. This is a corner stone of
> proving things.

Yes, given 1, it's a fact. I need to modify this assumption section.

> 
> > +2. Acquiring is more important than releasing, to check its dependency.
> 
> s/2/3/
> 
> That's not an assumption; that's a hard requirement. Since the acquire
> is the one blocking, you _have_ to check for cycles before you block,
> otherwise you'll hit the deadlock and not get a report, because you're
> deadlocked.

I don't think that's a *hard* requirement, even though that's required
in order to be able to report the deadlock before hitting it actually.
I agree that we can report the actual deadlock only if we check it before
the blocking operation is actually executed, as the current lockdep can
report it before the actual deadlock happens. It's very good.

However, there's another valuable thing lockdep mechanism can provides.
It can report a deadlock possibility based on the dependency built even
though actual deadlock does not happen.

Of cource it would be the best if it can report both the actual deadlock
and the deadlock possibility. So I also think we should focus acquiring
rather than releasing for typical lock since we can always report the
deadlock.

However, for any other locks which can be released by different context
for the context it was held by, we cannot detect any deadlock focusing
acquiring because we don't know where it will be released. However we can
detect the deadlock possibility if we consider the releasing so that we
can identify the releasing context, even though this way we cannot report
the actual deadlock for the crosslock. I think, detecting the deadlock
possibility is more valuable than doing nothing, unless it harms original
lockdep's current capability.

> > +Original lockdep's limitation
> > +-----------------------------
> > +
> > +Therefore, the original lockdep has limitations. It can be applied only
> > +to typical lock operations, e.g. spin_lock, mutex, semaphore and the
> 
> This is wrong, semaphores are very much not covered by lockdep since
> they do not have owner semantics (what you call crossmuck). (this is
> the distinction between a binary semaphore and a mutex)

Sorry for missing it. And please don't use the word like muck.

> > +What causes deadlock
> > +--------------------
> > +
> > +Not only lock operations, but also any operations causing to wait or
> > +spin it e.g. all wait operations for an event, lock_page() and so on
> > +can cause deadlock unless it's eventually released by someone. The most
> > +important point here is that the waiting or spinning must be *released*
> > +by someone. In other words, we have to focus whether the waiting and
> > +spinning can be *released* or not to avoid deadlock, rather than
> > +waiting or spinning it itself.
> 
> But since its the blocking that _is_ the deadlock, you'll never get your
> report.

Yes right. So I also think it is better to leave current implementation
unchanged for typical lock. However it would be better to detect the
deadlock possibility than doing nothing for crosslock.

> > +Relax the assumptions
> > +---------------------
> > +
> > +We can relax the assumtions the original lockdep has, which is not
> > +necessary to check dependency and detect a deadlock.
> > +
> > +1. 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.
> 
> You fail to say how this preserves correctness. By relaxing this you

Yes, I have to add more description about that.

> loose the held_lock dependencies and you destroy the entire proof that
> currently underpins lockdep.

I've never touch the current proof the lockdep uses. Just *added*
additional detection capability to detect the deadlock possibility for
crosslock for which currently we are doing nothing.

> > +2. A lock has dependency with all locks in the releasing context, having
> > +   been held since the lock was held.
> 
> But you cannot tell this. The 'since the lock was held' thing fully
> depends on timing and is not fundamentally correct.
> 
> 			lock(A)
> 			unlock(A)
> 	lock(A)
> 	wait_for(B)
> 	unlock(A)
> 			wake(B)
> 
> Between the wait_for(B) and wake(B), _nothing_ has been held, yet still
> there's the deadlock potential.

Crossreleas feature can detect this situation as a deadlock. wait_for()
is not an actual lock, but we can make it detectable by using acquring and
releasing semantics on wait_for() and wake().

> And note that if the timing was 'right', you would never get to wake(B)
> because deadlock, so you'd never establish that there would be a
> deadlock.

If a deadlock actually happens, then we cannot establish it as you said.
Remind that current lockdep does nothing for this situation. But at least
crossrelease feature can detect this deadlock possibility at the time the
dependency tree(graph) is built, which is better than doing nothing.

> >                                        Thus we can check the dependency
> > +   only after we identify the releasing context at first. Of course,
> > +   if we consider only typical lock e.g. spin lock, mutex, semaphore
> > +   and so on, then we can identify the releasing context at the time
> > +   acquiring a lock because the releasing context is same as the
> > +   releasing context for the typical lock. However, generally we have to
> > +   wait until the lock having been held will be eventually released to
> > +   identify the releasing context. We can say that the original lockdep
> > +   is a special case among all cases this crossrelease feature can deal
> > +   with.
> 
> I'm not sure you can say this at all; you've no proof of correctness
> from which this special case flows.

I need to modify and reinforce this description so that does not make you
confused.

> > +Introduce "crosslock"
> > +---------------------
> > +
> > +Crossrelease feature names a lock "crosslock" if it is releasable by a
> > +different context from the context having acquired the lock. All locks
> > +having been held in the context unlocking the crosslock until
> > +eventually the crosslock will be unlocked, have dependency with the
> > +crosslock. That's the key idea to implement crossrelease feature.
> 
> _all_ locks? That implies infinite storage, which is hardly feasible. If

Right. Basically it tries to consider all lock, but crossfeature builds
cache chain and check if the consideration is duplicated or not, and only
consider necessary ones. At least, on my qemu machine it works well without
any problem and detect problematic deadlock situation I mentioned.

> you limit it, the limit would seem arbitrary and you loose your proof
> (in so far as I can see, because you're not actually giving any).

I will give more description about implementation next spin.

[toc] | [prev] | [next] | [standalone]

#1437347

[Multipart message — attachments visible in raw view] — view raw

On Mon, Jul 04, 2016 at 03:42:59PM +0900, Byungchul Park wrote:
[snip]
> > > +2. A lock has dependency with all locks in the releasing context, having
> > > +   been held since the lock was held.
> > 
> > But you cannot tell this. The 'since the lock was held' thing fully
> > depends on timing and is not fundamentally correct.
> > 
> > 			lock(A)
> > 			unlock(A)
> > 	lock(A)
> > 	wait_for(B)
> > 	unlock(A)
> > 			wake(B)
> > 
> > Between the wait_for(B) and wake(B), _nothing_ has been held, yet still
> > there's the deadlock potential.
> 
> Crossreleas feature can detect this situation as a deadlock. wait_for()
> is not an actual lock, but we can make it detectable by using acquring and
> releasing semantics on wait_for() and wake().
> 
> > And note that if the timing was 'right', you would never get to wake(B)
> > because deadlock, so you'd never establish that there would be a
> > deadlock.
> 
> If a deadlock actually happens, then we cannot establish it as you said.
> Remind that current lockdep does nothing for this situation. But at least
> crossrelease feature can detect this deadlock possibility at the time the
> dependency tree(graph) is built, which is better than doing nothing.
> 

Confused, how?

Say the sequence of events is as follow:

(two tasks are initially with no lock held)

	Task 1		Task 2
	=============	====================
			lock(A)
			unlock(A)
	lock(A)
	wait_for(B) // acquire
			wake(B) // commit + release
	unlock(A)

by the time, the commit are called, the dependency tree will be built,
and we will find there is _no_ lock held before wake(B). Therefore at
the release stage, you will end up only adding dependency chain A->B in
the lockdep, right? And it looks like neither Task1 or Task2 will break
the dependency chain A->B. So how can crossrelease detect the potential
deadlock?

It will be better, that you could provide some samples that crossrelease
can detect after your confirmation.

Regards,
Boqun

[toc] | [prev] | [next] | [standalone]

#1437369

On Wed, Jul 06, 2016 at 08:49:43AM +0800, Boqun Feng wrote:
> On Mon, Jul 04, 2016 at 03:42:59PM +0900, Byungchul Park wrote:
> [snip]
> > > > +2. A lock has dependency with all locks in the releasing context, having
> > > > +   been held since the lock was held.
> > > 
> > > But you cannot tell this. The 'since the lock was held' thing fully
> > > depends on timing and is not fundamentally correct.
> > > 
> > > 			lock(A)
> > > 			unlock(A)
> > > 	lock(A)
> > > 	wait_for(B)
> > > 	unlock(A)
> > > 			wake(B)
> > > 
> > > Between the wait_for(B) and wake(B), _nothing_ has been held, yet still
> > > there's the deadlock potential.

I mis-understood this sentence. However, anyway this does not cause
deadlock. Of course it's deadlock if an example below actually happens.

We should not presume that the below can happen, once the above happened
because some dependencies between these contexts may prevent the below.
Therefore we should decide to check only when the actual problematic
sequence happens like below.

lock(A)
wait_for(B)
~~~~~~~~~~~~~~~~~~~~~~~~ <- serialized by atomic operation
		lock(A)
		unlock(A)
		wake(B)
unlock(A)

So I meant crossrelease can detect this deadlock if actually deadlock
causable sequence happens at least once. I tried to avoid false positive
detection, in other words, I made lockdep's detection stronger only with
true positive ones.

Of course I want this crosslock to be stronger than current
implementation. However I have no idea to make even what peterz's example
can be detected regarding all dependency with avoiding false positive
detection. It should be a future work. But it will be not simple or
impossible.

> > 
> > Crossreleas feature can detect this situation as a deadlock. wait_for()
> > is not an actual lock, but we can make it detectable by using acquring and
> > releasing semantics on wait_for() and wake().
> > 
> > > And note that if the timing was 'right', you would never get to wake(B)
> > > because deadlock, so you'd never establish that there would be a
> > > deadlock.
> > 
> > If a deadlock actually happens, then we cannot establish it as you said.
> > Remind that current lockdep does nothing for this situation. But at least
> > crossrelease feature can detect this deadlock possibility at the time the
> > dependency tree(graph) is built, which is better than doing nothing.
> > 
> 
> Confused, how?

And I am sorry for making you confused.

> 
> Say the sequence of events is as follow:
> 
> (two tasks are initially with no lock held)
> 
> 	Task 1		Task 2
> 	=============	====================
> 			lock(A)
> 			unlock(A)
> 	lock(A)
> 	wait_for(B) // acquire
> 			wake(B) // commit + release
> 	unlock(A)
> 

As you know this is not actual deadlock.

> by the time, the commit are called, the dependency tree will be built,
> and we will find there is _no_ lock held before wake(B). Therefore at
> the release stage, you will end up only adding dependency chain A->B in
> the lockdep, right? And it looks like neither Task1 or Task2 will break
> the dependency chain A->B. So how can crossrelease detect the potential
> deadlock?

It's similar to how the crossrelease work, but a little bit different.
I will reinforce and resend the document later.

> 
> It will be better, that you could provide some samples that crossrelease
> can detect after your confirmation.

Yes I will.

Thank you,
Byungchul

> 
> Regards,
> Boqun

[toc] | [prev] | [next] | [standalone]

#1437429

On Wed, Jul 06, 2016 at 11:17:10AM +0900, Byungchul Park wrote:
> 
> lock(A)
> wait_for(B)
> ~~~~~~~~~~~~~~~~~~~~~~~~ <- serialized by atomic operation
> 		lock(A)
> 		unlock(A)
> 		wake(B)
> unlock(A)

By the way, I have a question. Is there anyone who could answer it?

I want to serialize between two context's lock operations, for example,

	context A	context B
	--------------	--------------
	lock A
	lock B		...
	lock C
	atomic_inc_return
	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ <- serialization
			atomic_read
			lock D
	...		lock E
			lock F

so that we can see these in the order like A -> B -> C -> D -> E -> F.

atomic_inc_return() is used after lock C in context A, and atomic_read()
is used before lock D in context B. And I want to make it serialized when
the atomic_read() can see the increased value.

Can I use smp_mb__after_atomic() just after atomic_read() or should I use
smp_mb()? I think anyway I have to choose one of them for that ordering.

Thank you,
Byungchul

[toc] | [prev] | [next] | [standalone]

#1437520

On Wed, Jul 06, 2016 at 02:33:29PM +0900, Byungchul Park wrote:
> On Wed, Jul 06, 2016 at 11:17:10AM +0900, Byungchul Park wrote:
> > 
> > lock(A)
> > wait_for(B)
> > ~~~~~~~~~~~~~~~~~~~~~~~~ <- serialized by atomic operation
> > 		lock(A)
> > 		unlock(A)
> > 		wake(B)
> > unlock(A)
> 
> By the way, I have a question. Is there anyone who could answer it?
> 
> I want to serialize between two context's lock operations, for example,
> 
> 	context A	context B
> 	--------------	--------------
> 	lock A
> 	lock B		...
> 	lock C
> 	atomic_inc_return
> 	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ <- serialization
> 			atomic_read
> 			lock D
> 	...		lock E
> 			lock F
> 
> so that we can see these in the order like A -> B -> C -> D -> E -> F.
> 
> atomic_inc_return() is used after lock C in context A, and atomic_read()
> is used before lock D in context B. And I want to make it serialized when
> the atomic_read() can see the increased value.
> 
> Can I use smp_mb__after_atomic() just after atomic_read() 

No. atomic_set() and atomic_read() are not RmW operations.

> or should I use
> smp_mb()? I think anyway I have to choose one of them for that ordering.

smp_load_acquire(), if that observes the increment it will ensure D
comes after etc..

Also, atomic_read() _could_ be enough, if its part of a control
dependency, because LOCK very much involves a store, so the load->store
order provided by the control dependency will already order things.

[toc] | [prev] | [next] | [standalone]

#1437532

On Wed, Jul 06, 2016 at 09:56:08AM +0200, Peter Zijlstra wrote:
> On Wed, Jul 06, 2016 at 02:33:29PM +0900, Byungchul Park wrote:
> > On Wed, Jul 06, 2016 at 11:17:10AM +0900, Byungchul Park wrote:
> > > 
> > > lock(A)
> > > wait_for(B)
> > > ~~~~~~~~~~~~~~~~~~~~~~~~ <- serialized by atomic operation
> > > 		lock(A)
> > > 		unlock(A)
> > > 		wake(B)
> > > unlock(A)
> > 
> > By the way, I have a question. Is there anyone who could answer it?
> > 
> > I want to serialize between two context's lock operations, for example,
> > 
> > 	context A	context B
> > 	--------------	--------------
> > 	lock A
> > 	lock B		...
> > 	lock C
> > 	atomic_inc_return
> > 	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ <- serialization
> > 			atomic_read
> > 			lock D
> > 	...		lock E
> > 			lock F
> > 
> > so that we can see these in the order like A -> B -> C -> D -> E -> F.
> > 
> > atomic_inc_return() is used after lock C in context A, and atomic_read()
> > is used before lock D in context B. And I want to make it serialized when
> > the atomic_read() can see the increased value.
> > 
> > Can I use smp_mb__after_atomic() just after atomic_read() 
> 
> No. atomic_set() and atomic_read() are not RmW operations.
> 
> > or should I use
> > smp_mb()? I think anyway I have to choose one of them for that ordering.
> 
> smp_load_acquire(), if that observes the increment it will ensure D
> comes after etc..
> 
> Also, atomic_read() _could_ be enough, if its part of a control
> dependency, because LOCK very much involves a store, so the load->store
> order provided by the control dependency will already order things.

Indeed. Thank you very much.

I can rely on the control dependency if possible. I will check it.

Thank you,
Byungchul

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web