Re: [PATCH] lockdep: Add a document describing crossrelease feature

[Byungchul Park]

On Fri, Jul 01, 2016 at 12:45:21PM +0200, Peter Zijlstra wrote:
> > +Crossrelease lock dependency check
> > +==================================
> > +
> > +Started by Byungchul Park <byungchul.park@xxxxxxx>
> > +
> > +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.