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

[Byungchul Park <byungchul.park@lge.com>]

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