Re: [patch] mm: fix anon_vma races

[Nick Piggin]

On Sat, Oct 18, 2008 at 10:00:30AM -0700, Linus Torvalds wrote:
> 
> 
> On Sat, 18 Oct 2008, Nick Piggin wrote:
> > 
> > I think it can be called transitive. Basically (assumememory starts off zeroed)
> 
> Alpha is transitive. It has a notion of "processor issue order" and 
> "location access order", and the ordering those two creates is a 
> transitive "before" and "after" ordering.
> 
> The issue with alpha is not that it wouldn't be transitive - the issue is 
> that *local* read dependencies do not cause a "processor issue order"!

That's fine. That's not so different to most other weakly ordered processor
having control dependencies not appearing in-order. So long as stores
propogate according to causality.

 
> So this creates a "location access" event on 'x' on alpha, call it "event 
> A".
> 
> > CPU1
> > if (x == 1) {
> >   fence
> >   y := 1
> > }
> 
> This has two events: let's call the read of 'x' "B", and "C" is the write 
> to 'y'.
> 
> And according to the alpha rules, we now have:
> 
>  - A << B
> 
>    Because we saw a '1' in B, we now have a "location access ordering" 
>    on the _same_ variable between A and B.
> 
>  - B < C
> 
>    Because we have the fence in between the read and the write, we now 
>    have a "processor issue order" between B and C (despite the fact that 
>    they are different variables).
> 
> And now, the alpha definition of "before" means that we can declare that A 
> is before C.
> 
> But on alpha, we really do need that fence, even if the address of 'y' was 
> somehow directly data-dependent on 'x'. THAT is what makes alpha special, 
> not any odd ordering rules.
> 
> > CPU2
> > if (y == 1) {
> >   fence
> >   assert(x == 1)
> > }
> 
> So again, we now have two events: the access of 'y' is "D", and the access 
> of x is "E". And again, according to the alpha rules, we have two 
> orderings:
> 
>  - C << D
> 
>    Because we saw a '1' in D, we have another "location access ordering" 
>    on the variably 'y' between C and D.
> 
>  - D < E
> 
>    Because of the fence, we have a "processor issue ordering" between D 
>    and E.
> 
> And for the same reason as above, we now get that C is "before" E 
> according to the alpha ordering rules. And because the definition of 
> "before" is transitive, then A is before E.
> 
> And that, in turn, means that that assert() can never trigger, because if 
> it triggered, then by the access ordering rules that would imply that E << 
> A, which would mean that E is "before" A, which in turn would violate the 
> whole chain we just got to.
> 
> So while the alpha architecture manual doesn't have the exact sequence 
> mentioned above (it only has nine so-called "Litmus tests"), it's fairly 
> close to Litmus test 3, and the ordering on alpha is very clear: it's all 
> transitive and causal (ie "before" can never be "after").

OK, good.

 
> > Apparently pairwise ordering is more interesting than just a theoretical
> > thing, and not just restricted to Alpha's funny caches.
> 
> Nobody does just pairwise ordering, afaik. It's an insane model. Everybody 
> does some form of transitive ordering.
 
We were chatting with Andy Glew a while back, and he said it actually can
be quite beneficial for HW designers (but I imagine that is the same as a
lot of "insane" things) ;)

I remember though that you said Linux should be pairwise-safe. I think
that's wrong (for more reasons than this anon-vma race), which is why
I got concerned and started off this subthread.

I think Linux probably has a lot of problems in a pairwise consistency
model, so I'd just like to check if we acutally attempt to supportany
architecture where that is the case.

x86, powerpc, alpha are good ;) That gives me hope.

Thanks,
Nick
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/