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@xxxxxxxxx. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@xxxxxxxxx"> email@xxxxxxxxx </a>