lkml.org 
[lkml]   [2017]   [Sep]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: Memory-ordering recipes
    On Thu, Sep 21, 2017 at 02:45:31PM +0200, Peter Zijlstra wrote:
    > On Sun, Sep 17, 2017 at 04:05:09PM -0700, Paul E. McKenney wrote:
    >
    > > So what litmus tests are needed? Here is my initial set:
    > >
    > > 1. Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB

    I grouped the expansions of all of these names at the end.

    > > Lots of variety here, can in some cases substitute:
    > >
    > > a. READ_ONCE() for smp_load_acquire()
    > > b. WRITE_ONCE() for smp_store_release()
    > > c. Dependencies for both smp_load_acquire() and
    > > smp_store_release().
    > > d. smp_wmb() for smp_store_release() in first thread
    > > of ISA2 and Z6.2.
    > > e. smp_rmb() for smp_load_acquire() in last thread of ISA2.

    The key point of these is to illustrate patterns that require only
    the lightest ordering.

    > > 2. MP (see test6.pdf for nickname translation)
    > >
    > > a. smp_store_release() / smp_load_acquire()
    > > b. rcu_assign_pointer() / rcu_dereference()
    > > c. smp_wmb() / smp_rmb()
    > > d. Replacing either of the above with smp_mb()

    This one is a workhorse, used very frequently.

    > > 3. SB
    > >
    > > a. smp_mb(), as in lockless wait-wakeup coordination.
    > > And as in sys_membarrier()-scheduler coordination,
    > > for that matter.

    This is also used frequently, for example, in lockless wait-wakeup
    situations.

    > > Others?

    Someone (quite rightly) suggested adding some single-variable SC
    examples, which I will do.

    > So I have no idea what you're proposing here. The above is just a bunch
    > of words without meaning :-(

    As Boqun said on IRC, this URL is your friend:

    https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf

    Many of the names seem quite arbitrary, but the abbreviation can be useful.

    ISA2 is the first one on page 2, and has this pattern of reads and
    writes:

    CPU 0 CPU 1 CPU 2

    WRITE_ONCE(x, 1); r1 = READ_ONCE(y); r2 = READ_ONCE(z);
    WRITE_ONCE(y, 1); WRITE_ONCE(z, 1); r3 = READ_ONCE(x);

    BUG_ON(r1 == 1 && r2 == 1 && r3 == 0);

    Arbitrary ordering can be added to all of these litmus-test patterns,
    for example, the writes to y and z might become smp_store_release()
    and the read from z might become smp_load_acquire(). Or, alternatively,
    smp_mb() might be placed between accesses on all thread CPUs. The key
    point is that "ISA2" identifies not a specific litmus test, but instead a
    family of them with the same pattern of reads, writes and RMW operations,
    but with different ordering properties.

    Z6.3 is the second one on page 2:

    CPU 0 CPU 1 CPU 2

    WRITE_ONCE(x, 2); r1 = READ_ONCE(y); r2 = READ_ONCE(z);
    WRITE_ONCE(y, 1); WRITE_ONCE(z, 1); WRITE_ONCE(x, 1);

    BUG_ON(r1 == 1 && r2 == 1 && x == 2);

    LB is the last on on the extreme left of page 1. "LB" stands for
    "load buffering", and each CPU's first access is a load and last
    access is a store:

    CPU 0 CPU 1

    r1 = READ_ONCE(x); r2 = READ_ONCE(y);
    WRITE_ONCE(y, 1); WRITE_ONCE(x, 1);

    BUG_ON(r1 == 1 && r2 == 1);

    3.LB is simply a three-CPU extension of LB, and "LB" by itself is
    sometimes used to cover an arbitrary number of CPUs:

    CPU 0 CPU 1 CPU 2

    r1 = READ_ONCE(x); r2 = READ_ONCE(y); r3 = READ_ONCE(z);
    WRITE_ONCE(y, 1); WRITE_ONCE(z, 1); WRITE_ONCE(x, 1);

    BUG_ON(r1 == 1 && r2 == 1 && r3 == 1);

    MP is the second on the extreme left of page 1. "MP" stands for "message
    passing", and is used very heavily. The idea is that "x" is the message
    (sent by CPU 0), and "y" is a flag saying that the message is ready to
    be received (by CPU 1).

    CPU 0 CPU 1

    WRITE_ONCE(x, 1); r1 = READ_ONCE(y);
    WRITE_ONCE(y, 1); r1 = READ_ONCE(x);

    BUG_ON(r1 == 1 && r2 == 0);

    SB is the fourth on the extreme left of page 1. "SB" stands for "store
    buffering" because systems without store buffers won't reorder this one.

    CPU 0 CPU 1

    WRITE_ONCE(x, 1); WRITE_ONCE(y, 1);
    r1 = READ_ONCE(y); r2 = READ_ONCE(x);

    BUG_ON(r1 == 0 && r2 == 0);

    Does that help?

    Oh, and the actual recipes would include ordering as indicated by
    the sub-bullets.

    Thanx, Paul

    \
     
     \ /
      Last update: 2017-09-21 19:35    [W:3.130 / U:0.008 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site