lkml.org 
[lkml]   [2009]   [Dec]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: Async resume patch (was: Re: [GIT PULL] PM updates for 2.6.33)


    On Wed, 9 Dec 2009, Alan Stern wrote:
    >
    > That could be attributed to reordering on CPU2, so let's take CPU2's
    > peculiarities out of the picture (initially everything is set to 0):
    >
    > CPU1 CPU2
    > ---- ----
    > if (x == 1) z = y;
    > y = 5; mb();
    > x = 1;
    >
    > This gets at the heart of the question: Can a write move up past a
    > control dependency?
    > [ .. ]
    > Can z end up equal to 5 in any of these examples?

    In any _practical_ microarchitecture I know of, the above will never
    result in 'z' being 5, even though CPU1 doesn't really have a memory
    barrier. But if I read the alpha memory ordering guarantees rigth, then at
    least in theory you really can end up with z=5.

    Let me write that as five events (with the things in brackets being what
    the alpha memory ordering manual calls them):

    - A is "read of x returns 1" on CPU1 [ P1:R(x,1) ]
    - B is "write of value 5 to y" on CPU1 [ P1:W(y,5) ]
    - C is "read of y returns 5" on CPU2 [ P2:R(y,5) ]
    - D is "write of value 1 to x" on CPU2 [ P2:W(x,1) ]
    - 'MB' is the mb() on CPU2 [ P2:MB ]

    (The write of 'z' is irrelevant, we can think of it as a register, the end
    result is the same).

    And yes, if I read the alpha memory ordering rules correctly, you really
    can end up with z=5, although I don't think you will ever find an alpha
    _implementation_ that does it.

    Why?

    The alpha memory ordering literally defines ordering in two ways:

    - "location access order". But that is _only_ defined per actual
    location, so while 'x' can have a location access order specified by
    seeing certain values, there is no "location access order" for two
    different memory locations (x and y).

    The alpha architecture manual uses "A << B" to say "event A" is before
    "event B" when there is a defined ordering.

    So in the example above, there is a location access ordering between

    P2:W(x,1) << P1:R(x, 1)

    and

    P2:R(y,5) << P1:W(y,5)

    ie you have D << A and B << C.

    Good so far, but that doesn't define anything else: there's only
    ordering between the pairs (D,A) and (B,C), nothing between them.

    - "Processor issue order" for two instruction is _only_ defined by either
    (a) memory barriers or (b) accesses to the _same_ locations. The alpha
    architecture manual uses "A < B" to say that "event A" is before "event
    B" in processor issue order.

    So there is a "Processor issue order" on CPU2 due to the memory
    barrier: P2:R(y,5) < P2:MB < P2:W(x,1), or put another way C < MB < D:
    C < D.

    Now, the question is, can we actually get the behaviour of reading 5 on
    CPU2 (ie P2:R(y,5)), and that is only possible if we can find an ordering
    that satisfies all the constraints. We have

    D << A
    B << C
    C < D

    and it seems to be that it is a possible situation: "B C D A"
    really does satisfy all the constraints afaik.

    So yes, according to the actual alpha architecture memory ordering rules,
    you can see '5' from that first read of 'y'. DESPITE having a mb() on
    CPU2.

    In order to not see 5, you need to also specify "A < B", and the _only_
    way to do that processor issue order specification is with a memory
    barrier (or if the locations are the same, which they aren't).

    "Causality" simply is nowhere in the officially defined alpha memory
    ordering. The fact that we test 'x == 1' and conditionally do the write
    simply doesn't enter the picture. I suspect you'd have a really hard time
    not having causality in practice, but there _are_ things that can break
    causality (value prediction etc), so it's not like you'd have to actually
    violate physics of reality to do it.

    IOW, you could at least in theory implement a CPU that does every
    instruction speculatively in parallel, and then validates the end result
    afterwards according to the architecture rules. And that CPU would require
    the memory barrier on alpha.

    (On x86, 'causality' is defined to be part of the memory ordering rules,
    so on x86, you _do_ have a 'A < B' relationship. But not on alpha).

    Linus


    \
     
     \ /
      Last update: 2009-12-09 22:57    [W:9.091 / U:0.220 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site