Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Wed, Sep 14, 2016 at 02:12:51AM +0900, Byungchul Park wrote:
> On Wed, Sep 14, 2016 at 12:05 AM, Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
> >
> >
> > So the idea is to add support for non-owner serialization primitives,
> > like completions/semaphores, and so far I've not looked at the code yet.
> > I did spend 2+ hours trying to decipher your documentation thing, but am
> > still confused, that thing is exceedingly hard to parse/read.
> >
> > So the typical scenario would be something like:
> >
> > L a     L a
> >         U a
> > W b     C b
> >
> > where L := lock, U := unlock, W := wait_for_completion and C :=
> > complete.
> >
> > On the left, the blocking thread we can easily observe the 'b depends on
> > a' relation, since we block while holding a.
> 
> I think 'a depends on b' relation.
> 
> Why does b depend on a? b depends on a's what?

b blocks while holding a. In any case, for the graph it doesn't matter,
its not a directed graph as such, all we care about is acyclic.

> > On the right however that same relation is hard to see, since by the
> 
> Yes, there's no dependency on the right side of your example.

Well, there is, its just not trivially observable. We must be able to
acquire a in order to complete b, therefore there is a dependency.

> > time we would run complete, a has already been released.
> 
> I will change your example a little bit.
> 
> W b
> ~~~~~~~ <- serialized
>         L a
>         U a
>         C b
> 
> (Remind crossrelease considers dependencies in only case that
> lock sequence serialized is observable.)

What does that mean? Any why? This is a random point in time without
actual meaning.

> There's a dependency in this case, like 'b depends on a' relation.
> 'C b' may not be hit, depending on the result of 'L a', that is,
> acquired or not.

With or without a random reference point, the dependency is there.

> > I _think_ you propose to keep track of all prior held locks and then use
> > the union of the held list on the block-chain with the prior held list
> > from the complete context.
> 
> Almost right. Only thing we need to do to consider the union is to
> connect two chains of two contexts by adding one dependency 'b -> a'.

Sure, but how do you arrive at which connection to make. The document is
entirely silent on this crucial point.

The union between the held-locks of the blocked and prev-held-locks of
the release should give a fair indication I think, but then, I've not
thought too hard on this yet.

> > The document describes you have a prior held list, and that its a
> > circular thing, but it then completely fails to specify what gets added
> > and how its used.
> 
> Why does it fail? It keeps them in the form of hlock. This data is enough
> to generate dependencies.

It fails to explain. It just barely mentions you keep them, it doesn't
mention how they're used or why.

> > Also, by it being a circular list (of indeterminate, but finite size),
> > there is the possibility of missing dependencies if they got spooled out
> > by recent activity.
> 
> Yes, right. They might be missed. It means just missing some chances to
> check a deadlock. It's all. Better than do nothing.

Sure, but you didn't specify. Again, the document is very ambiguous and
ill specified.

> > The document has an example in the section 'How cross release works'
> > (the 3rd) that simply cannot be. It lists lock action _after_ acquire,
> 
> Could you tell me more? Why cannot it be?

Once you block you cannot take more locks, that simply doesnt make
sense.

> > but you place the acquire in wait_for_completion. We _block_ there.
> >
> > Is this the general idea?
> >
> > If so, I cannot see how something like:
> >
> > W a     W b
> > C b     C a
> 
> I didn't tell it works in this case. But it can be a future work. I'm not
> sure but I don't think making it work is impossible at all. But anyway
> current implementation cannot deal with this case.

+4. 'crosslock a -> crosslock b' dependency
+
+   Creating this kind of dependency directly is unnecessary since it can
+   be covered by other kinds of dependencies.

Says something different, doesn't it?

> > On the whole 'release context' thing you want to cast lockdep in, please
> > consider something like:
> >
> > L a     L b
> > L b     L a
> > U a     U a
> > U b     U b
> >
> > Note that the release order of locks is immaterial and can generate
> > 'wrong' dependencies. Note how on both sides a is released under b,
> 
> Who said the release order is important? Wrong for what?

Well, again, you mention 'release context' without actually specifying
what you mean with that.

L a
L b
U b

and

L a
L b
U a

Here the unlocks obviously have different context. Without further
specification its simply impossible to tell what you mean.