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

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

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

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.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>