lkml.org 
[lkml]   [2014]   [Feb]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    SubjectRe: [RFC][PATCH 0/5] arch: atomic rework
    From
    Date
    On Wed, 2014-02-19 at 20:01 -0800, Paul E. McKenney wrote:
    > On Wed, Feb 19, 2014 at 04:53:49PM -0800, Linus Torvalds wrote:
    > > On Tue, Feb 18, 2014 at 11:47 AM, Torvald Riegel <triegel@redhat.com> wrote:
    > > > On Tue, 2014-02-18 at 09:44 -0800, Linus Torvalds wrote:
    > > >>
    > > >> Can you point to it? Because I can find a draft standard, and it sure
    > > >> as hell does *not* contain any clarity of the model. It has a *lot* of
    > > >> verbiage, but it's pretty much impossible to actually understand, even
    > > >> for somebody who really understands memory ordering.
    > > >
    > > > http://www.cl.cam.ac.uk/~mjb220/n3132.pdf
    > > > This has an explanation of the model up front, and then the detailed
    > > > formulae in Section 6. This is from 2010, and there might have been
    > > > smaller changes since then, but I'm not aware of any bigger ones.
    > >
    > > Ahh, this is different from what others pointed at. Same people,
    > > similar name, but not the same paper.
    > >
    > > I will read this version too, but from reading the other one and the
    > > standard in parallel and trying to make sense of it, it seems that I
    > > may have originally misunderstood part of the whole control dependency
    > > chain.
    > >
    > > The fact that the left side of "? :", "&&" and "||" breaks data
    > > dependencies made me originally think that the standard tried very
    > > hard to break any control dependencies. Which I felt was insane, when
    > > then some of the examples literally were about the testing of the
    > > value of an atomic read. The data dependency matters quite a bit. The
    > > fact that the other "Mathematical" paper then very much talked about
    > > consume only in the sense of following a pointer made me think so even
    > > more.
    > >
    > > But reading it some more, I now think that the whole "data dependency"
    > > logic (which is where the special left-hand side rule of the ternary
    > > and logical operators come in) are basically an exception to the rule
    > > that sequence points end up being also meaningful for ordering (ok, so
    > > C11 seems to have renamed "sequence points" to "sequenced before").
    > >
    > > So while an expression like
    > >
    > > atomic_read(p, consume) ? a : b;
    > >
    > > doesn't have a data dependency from the atomic read that forces
    > > serialization, writing
    > >
    > > if (atomic_read(p, consume))
    > > a;
    > > else
    > > b;
    > >
    > > the standard *does* imply that the atomic read is "happens-before" wrt
    > > "a", and I'm hoping that there is no question that the control
    > > dependency still acts as an ordering point.
    >
    > The control dependency should order subsequent stores, at least assuming
    > that "a" and "b" don't start off with identical stores that the compiler
    > could pull out of the "if" and merge. The same might also be true for ?:
    > for all I know. (But see below)

    I don't think this is quite true. I agree that a conditional store will
    not be executed speculatively (note that if it would happen in both the
    then and the else branch, it's not conditional); so, the store in
    "a;" (assuming it would be a store) won't happen unless the thread can
    really observe a true value for p. However, this is *this thread's*
    view of the world, but not guaranteed to constrain how any other thread
    sees the state. mo_consume does not contribute to
    inter-thread-happens-before in the same way that mo_acquire does (which
    *does* put a constraint on i-t-h-b, and thus enforces a global
    constraint that all threads have to respect).

    Is it clear which distinction I'm trying to show here?

    > That said, in this case, you could substitute relaxed for consume and get
    > the same effect. The return value from atomic_read() gets absorbed into
    > the "if" condition, so there is no dependency-ordered-before relationship,
    > so nothing for consume to do.
    >
    > One caution... The happens-before relationship requires you to trace a
    > full path between the two operations of interest. This is illustrated
    > by the following example, with both x and y initially zero:
    >
    > T1: atomic_store_explicit(&x, 1, memory_order_relaxed);
    > r1 = atomic_load_explicit(&y, memory_order_relaxed);
    >
    > T2: atomic_store_explicit(&y, 1, memory_order_relaxed);
    > r2 = atomic_load_explicit(&x, memory_order_relaxed);
    >
    > There is a happens-before relationship between T1's load and store,
    > and another happens-before relationship between T2's load and store,
    > but there is no happens-before relationship from T1 to T2, and none
    > in the other direction, either. And you don't get to assume any
    > ordering based on reasoning about these two disjoint happens-before
    > relationships.
    >
    > So it is quite possible for r1==1&&r2==1 after both threads complete.
    >
    > Which should be no surprise: This misordering can happen even on x86,
    > which would need a full smp_mb() to prevent it.
    >
    > > THAT was one of my big confusions, the discussion about control
    > > dependencies and the fact that the logical ops broke the data
    > > dependency made me believe that the standard tried to actively avoid
    > > the whole issue with "control dependencies can break ordering
    > > dependencies on some CPU's due to branch prediction and memory
    > > re-ordering by the CPU".
    > >
    > > But after all the reading, I'm starting to think that that was never
    > > actually the implication at all, and the "logical ops breaks the data
    > > dependency rule" is simply an exception to the sequence point rule.
    > > All other sequence points still do exist, and do imply an ordering
    > > that matters for "consume"
    > >
    > > Am I now reading it right?
    >
    > As long as there is an unbroken chain of -data- dependencies from the
    > consume to the later access in question, and as long as that chain
    > doesn't go through the excluded operations, yes.
    >
    > > So the clarification is basically to the statement that the "if
    > > (consume(p)) a" version *would* have an ordering guarantee between the
    > > read of "p" and "a", but the "consume(p) ? a : b" would *not* have
    > > such an ordering guarantee. Yes?
    >
    > Neither has a data-dependency guarantee, because there is no data
    > dependency from the load to either "a" or "b". After all, the value
    > loaded got absorbed into the "if" condition.

    Agreed.

    > However, according to
    > discussions earlier in this thread, the "if" variant would have a
    > control-dependency ordering guarantee for any stores in "a" and "b"
    > (but not loads!). The ?: form might also have a control-dependency
    > guarantee for any stores in "a" and "b" (again, not loads).

    Don't quite agree; see above for my opinion on this.



    \
     
     \ /
      Last update: 2014-02-20 19:01    [W:6.566 / U:0.024 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site