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

[Byungchul Park]

On Tue, Sep 20, 2016 at 02:50:38PM +0900, Byungchul Park wrote:
> On Mon, Sep 19, 2016 at 10:50:09AM +0200, Peter Zijlstra wrote:
> > On Mon, Sep 19, 2016 at 11:41:02AM +0900, Byungchul Park wrote:
> > 
> > > > But since these threads are independently scheduled there is no point in
> > > > transferring the point in time thread A does W to thread B. There is no
> > > > relation there.
> > > > 
> > > > B could have already executed the complete or it could not yet have
> > > > started execution at all or anything in between, entirely random.
> > > 
> > > Of course B could have already executed the complete or it could not yet
> > > have started execution at all or anything in between. But it's not entirely
> > > random.
> > > 
> > > It might be a random point since they are independently scheduled, but it's
> > > not entirely random. And it's a random point among valid points which lockdep
> > > needs to consider. For example,
> > > 
> > > 
> > > CONTEXT 1			CONTEXT 2(forked one)
> > > =========			=====================
> > > (a)				acquire F
> > > acquire A			acquire G
> > > acquire B			wait_for_completion Z
> > > acquire C
> > > (b)				acquire H
> > > fork 2				acquire I
> > > acquire D			acquire J
> > > complete Z			acquire K
> > > 
> > 
> > I'm hoping you left out the releases for brevity? Because calling fork()
> > with locks held is _really_ poor form.
> 
> Exactly. Sorry. I shouldn't have omitted releases.
> 
> > 
> > > I can provide countless examples with which I can say you're wrong.
> > > In this case, all acquires between (a) and (b) must be ignored when
> > > generating dependencies with complete operation of Z.
> > 
> > I still don't get the point. Why does this matter?
> > 
> > Sure, A-C are irrelevant in this example, but I don't see how they're
> > differently irrelevant from a whole bunch of other prior state action.
> > 
> > 
> > Earlier you said the algorithm for selecting the dependency is the first
> > acquire observed in the completing thread after the
> > wait_for_completion(). Is this correct?
> 
> Sorry for insufficient description.
> 
> held_locks of left context will be,
> 
> time 1: a
> time 2: a, x[0]
> time 3: a, x[1]
> ...
> time n: b
> 
> Between time 1 and time (n-1), 'a' will be the first among held_locks. At
> time n, 'b' will be the fist among held_locks. So 'a' and 'b' should be
> connected to 'z' if we ignore IRQ context. (I will explain it soon.)
> 
> Acquire x[i] is also valid one but crossrelease doesn't take it into
> account since original lockdep will cover using 'a -> x[i]'. So only
> connections we need are 'z -> a' and 'z -> b'.
> 
> > 
> > 
> > 				W z
> > 
> > 	A a
> > 	for (i<0;i<many;i++) {
> > 	  A x[i]
> > 	  R x[i]
> > 	}
> > 	R a
> > 
> > 	<IRQ>
> > 	  A b
> > 	  R b
> > 	  C z
> > 	</IRQ>
> 
> My crossrelease implementation distinguishes each IRQ from normal context
> or other IRQs in different timeline, even though they might share
> held_locks. So in this example, precisely speaking, there are two different
> contexts. One is normal context and the other is IRQ context. So only 'A b'
> is related with 'W z' in this example.
> 
> > 
> > That would be 'a' in this case, but that isn't at all related. Its just
> > as irrelevant as your A-C. And we can pick @many as big as needed to
> > flush the prev held cyclic buffer (although I've no idea how that
> > matters either).
> 
> I designed crossrelease so that x[i] is not added into ring buffer because
> adding 'z -> a' is sufficient and x[i] doesn't need to be taken into
> account in this case.
> 
> > 
> > What we want here is to link z to b, no? That is the last, not the first
> 
> Exactly right. Only 'z -> b' must be added under considering IRQ context.
> That is the first among held_locks in the IRQ context.
> 
> > acquire, it also is independent of when W happened.
> 
> If the IRQ is really random, then it can happen before W z and it can also
> happen after W z. We cannot determine the time. Then we need to consider all
> combination and possibility. It's a key point. We have to consider
> dependencies for all possibility.
> 
> However, we don't know what synchronizes the flow. So it must be based on
> what actually happened, to identify true dependencies.
> 
> > 
> > At the same time, picking the last is no guarantee either, since that
> > can equally miss dependencies. Suppose the IRQ handler did:
> > 
> > 	<IRQ>
> > 	  A c
> > 	  R c
> > 	  A b
> > 	  R b
> > 	  C z
> > 	</IRQ>
> > 
> 
> time 1: c (in held_locks)
> time 2: b (in held_locks)
> 
> So 'c' and 'b' can be the first among held_locks at each moment.
> So 'z -> b' and 'z -> c' will be added.
> 
> > instead. We'd miss the z depends on c relation, and since they're
> > independent lock sections, lockdep wouldn't make a b-c relation either.
> > 
> > 
> > Clearly I'm still missing stuff...
> 
> Sorry for insufficient description. I tried to describ crossrelease in as
> much detail as possible, really.
> 
> The reason why I consider only the first among valid locks in held_locks is
> simple. For example,
> 
> Context 1
> A a -> A b -> A crosslock -> R a -> R b

Here, '->' represents the order executing A(cquire)s and R(elease)s.

_Not_ dependency.

> 
> Context 2
> A c -> A d -> R d -> R the crosslock -> R c
> 
> If 'A c' after 'A crosslock' is possible, then 'A crosslock' does not only
> depends on 'A c' but also 'A d'. But all dependencies we need to add is only
> 'crosslock -> c' because 'crosslock -> d' will be covered by 'crosslock ->
> c' and 'a -> b'. 'a -> b' is added by original lockdep.