diff options
Diffstat (limited to 'tools/memory-model/litmus-tests')
30 files changed, 1078 insertions, 0 deletions
diff --git a/tools/memory-model/litmus-tests/CoRR+poonceonce+Once.litmus b/tools/memory-model/litmus-tests/CoRR+poonceonce+Once.litmus new file mode 100644 index 000000000000..967f9f2a6226 --- /dev/null +++ b/tools/memory-model/litmus-tests/CoRR+poonceonce+Once.litmus @@ -0,0 +1,26 @@ +C CoRR+poonceonce+Once + +(* + * Result: Never + * + * Test of read-read coherence, that is, whether or not two successive + * reads from the same variable are ordered. + *) + +{} + +P0(int *x) +{ + WRITE_ONCE(*x, 1); +} + +P1(int *x) +{ + int r0; + int r1; + + r0 = READ_ONCE(*x); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 1:r1=0) diff --git a/tools/memory-model/litmus-tests/CoRW+poonceonce+Once.litmus b/tools/memory-model/litmus-tests/CoRW+poonceonce+Once.litmus new file mode 100644 index 000000000000..4635739f3974 --- /dev/null +++ b/tools/memory-model/litmus-tests/CoRW+poonceonce+Once.litmus @@ -0,0 +1,25 @@ +C CoRW+poonceonce+Once + +(* + * Result: Never + * + * Test of read-write coherence, that is, whether or not a read from + * a given variable and a later write to that same variable are ordered. + *) + +{} + +P0(int *x) +{ + int r0; + + r0 = READ_ONCE(*x); + WRITE_ONCE(*x, 1); +} + +P1(int *x) +{ + WRITE_ONCE(*x, 2); +} + +exists (x=2 /\ 0:r0=2) diff --git a/tools/memory-model/litmus-tests/CoWR+poonceonce+Once.litmus b/tools/memory-model/litmus-tests/CoWR+poonceonce+Once.litmus new file mode 100644 index 000000000000..bb068c92d8da --- /dev/null +++ b/tools/memory-model/litmus-tests/CoWR+poonceonce+Once.litmus @@ -0,0 +1,25 @@ +C CoWR+poonceonce+Once + +(* + * Result: Never + * + * Test of write-read coherence, that is, whether or not a write to a + * given variable and a later read from that same variable are ordered. + *) + +{} + +P0(int *x) +{ + int r0; + + WRITE_ONCE(*x, 1); + r0 = READ_ONCE(*x); +} + +P1(int *x) +{ + WRITE_ONCE(*x, 2); +} + +exists (x=1 /\ 0:r0=2) diff --git a/tools/memory-model/litmus-tests/CoWW+poonceonce.litmus b/tools/memory-model/litmus-tests/CoWW+poonceonce.litmus new file mode 100644 index 000000000000..0d9f0a958799 --- /dev/null +++ b/tools/memory-model/litmus-tests/CoWW+poonceonce.litmus @@ -0,0 +1,18 @@ +C CoWW+poonceonce + +(* + * Result: Never + * + * Test of write-write coherence, that is, whether or not two successive + * writes to the same variable are ordered. + *) + +{} + +P0(int *x) +{ + WRITE_ONCE(*x, 1); + WRITE_ONCE(*x, 2); +} + +exists (x=1) diff --git a/tools/memory-model/litmus-tests/IRIW+mbonceonces+OnceOnce.litmus b/tools/memory-model/litmus-tests/IRIW+mbonceonces+OnceOnce.litmus new file mode 100644 index 000000000000..50d5db9ea983 --- /dev/null +++ b/tools/memory-model/litmus-tests/IRIW+mbonceonces+OnceOnce.litmus @@ -0,0 +1,45 @@ +C IRIW+mbonceonces+OnceOnce + +(* + * Result: Never + * + * Test of independent reads from independent writes with smp_mb() + * between each pairs of reads. In other words, is smp_mb() sufficient to + * cause two different reading processes to agree on the order of a pair + * of writes, where each write is to a different variable by a different + * process? + *) + +{} + +P0(int *x) +{ + WRITE_ONCE(*x, 1); +} + +P1(int *x, int *y) +{ + int r0; + int r1; + + r0 = READ_ONCE(*x); + smp_mb(); + r1 = READ_ONCE(*y); +} + +P2(int *y) +{ + WRITE_ONCE(*y, 1); +} + +P3(int *x, int *y) +{ + int r0; + int r1; + + r0 = READ_ONCE(*y); + smp_mb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 1:r1=0 /\ 3:r0=1 /\ 3:r1=0) diff --git a/tools/memory-model/litmus-tests/IRIW+poonceonces+OnceOnce.litmus b/tools/memory-model/litmus-tests/IRIW+poonceonces+OnceOnce.litmus new file mode 100644 index 000000000000..4b54dd6a6cd9 --- /dev/null +++ b/tools/memory-model/litmus-tests/IRIW+poonceonces+OnceOnce.litmus @@ -0,0 +1,43 @@ +C IRIW+poonceonces+OnceOnce + +(* + * Result: Sometimes + * + * Test of independent reads from independent writes with nothing + * between each pairs of reads. In other words, is anything at all + * needed to cause two different reading processes to agree on the order + * of a pair of writes, where each write is to a different variable by a + * different process? + *) + +{} + +P0(int *x) +{ + WRITE_ONCE(*x, 1); +} + +P1(int *x, int *y) +{ + int r0; + int r1; + + r0 = READ_ONCE(*x); + r1 = READ_ONCE(*y); +} + +P2(int *y) +{ + WRITE_ONCE(*y, 1); +} + +P3(int *x, int *y) +{ + int r0; + int r1; + + r0 = READ_ONCE(*y); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 1:r1=0 /\ 3:r0=1 /\ 3:r1=0) diff --git a/tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus b/tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file mode 100644 index 000000000000..7a39a0aaa976 --- /dev/null +++ b/tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus @@ -0,0 +1,41 @@ +C ISA2+pooncelock+pooncelock+pombonce.litmus + +(* + * Result: Sometimes + * + * This test shows that the ordering provided by a lock-protected S + * litmus test (P0() and P1()) are not visible to external process P2(). + * This is likely to change soon. + *) + +{} + +P0(int *x, int *y, spinlock_t *mylock) +{ + spin_lock(mylock); + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); + spin_unlock(mylock); +} + +P1(int *y, int *z, spinlock_t *mylock) +{ + int r0; + + spin_lock(mylock); + r0 = READ_ONCE(*y); + WRITE_ONCE(*z, 1); + spin_unlock(mylock); +} + +P2(int *x, int *z) +{ + int r1; + int r2; + + r2 = READ_ONCE(*z); + smp_mb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 2:r2=1 /\ 2:r1=0) diff --git a/tools/memory-model/litmus-tests/ISA2+poonceonces.litmus b/tools/memory-model/litmus-tests/ISA2+poonceonces.litmus new file mode 100644 index 000000000000..b321aa6f4ea5 --- /dev/null +++ b/tools/memory-model/litmus-tests/ISA2+poonceonces.litmus @@ -0,0 +1,37 @@ +C ISA2+poonceonces + +(* + * Result: Sometimes + * + * Given a release-acquire chain ordering the first process's store + * against the last process's load, is ordering preserved if all of the + * smp_store_release() invocations are replaced by WRITE_ONCE() and all + * of the smp_load_acquire() invocations are replaced by READ_ONCE()? + *) + +{} + +P0(int *x, int *y) +{ + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); +} + +P1(int *y, int *z) +{ + int r0; + + r0 = READ_ONCE(*y); + WRITE_ONCE(*z, 1); +} + +P2(int *x, int *z) +{ + int r0; + int r1; + + r0 = READ_ONCE(*z); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 2:r0=1 /\ 2:r1=0) diff --git a/tools/memory-model/litmus-tests/ISA2+pooncerelease+poacquirerelease+poacquireonce.litmus b/tools/memory-model/litmus-tests/ISA2+pooncerelease+poacquirerelease+poacquireonce.litmus new file mode 100644 index 000000000000..025b0462ec9b --- /dev/null +++ b/tools/memory-model/litmus-tests/ISA2+pooncerelease+poacquirerelease+poacquireonce.litmus @@ -0,0 +1,39 @@ +C ISA2+pooncerelease+poacquirerelease+poacquireonce + +(* + * Result: Never + * + * This litmus test demonstrates that a release-acquire chain suffices + * to order P0()'s initial write against P2()'s final read. The reason + * that the release-acquire chain suffices is because in all but one + * case (P2() to P0()), each process reads from the preceding process's + * write. In memory-model-speak, there is only one non-reads-from + * (AKA non-rf) link, so release-acquire is all that is needed. + *) + +{} + +P0(int *x, int *y) +{ + WRITE_ONCE(*x, 1); + smp_store_release(y, 1); +} + +P1(int *y, int *z) +{ + int r0; + + r0 = smp_load_acquire(y); + smp_store_release(z, 1); +} + +P2(int *x, int *z) +{ + int r0; + int r1; + + r0 = smp_load_acquire(z); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 2:r0=1 /\ 2:r1=0) diff --git a/tools/memory-model/litmus-tests/LB+ctrlonceonce+mbonceonce.litmus b/tools/memory-model/litmus-tests/LB+ctrlonceonce+mbonceonce.litmus new file mode 100644 index 000000000000..de6708229dd1 --- /dev/null +++ b/tools/memory-model/litmus-tests/LB+ctrlonceonce+mbonceonce.litmus @@ -0,0 +1,34 @@ +C LB+ctrlonceonce+mbonceonce + +(* + * Result: Never + * + * This litmus test demonstrates that lightweight ordering suffices for + * the load-buffering pattern, in other words, preventing all processes + * reading from the preceding process's write. In this example, the + * combination of a control dependency and a full memory barrier are enough + * to do the trick. (But the full memory barrier could be replaced with + * another control dependency and order would still be maintained.) + *) + +{} + +P0(int *x, int *y) +{ + int r0; + + r0 = READ_ONCE(*x); + if (r0) + WRITE_ONCE(*y, 1); +} + +P1(int *x, int *y) +{ + int r0; + + r0 = READ_ONCE(*y); + smp_mb(); + WRITE_ONCE(*x, 1); +} + +exists (0:r0=1 /\ 1:r0=1) diff --git a/tools/memory-model/litmus-tests/LB+poacquireonce+pooncerelease.litmus b/tools/memory-model/litmus-tests/LB+poacquireonce+pooncerelease.litmus new file mode 100644 index 000000000000..07b9904b0e49 --- /dev/null +++ b/tools/memory-model/litmus-tests/LB+poacquireonce+pooncerelease.litmus @@ -0,0 +1,29 @@ +C LB+poacquireonce+pooncerelease + +(* + * Result: Never + * + * Does a release-acquire pair suffice for the load-buffering litmus + * test, where each process reads from one of two variables then writes + * to the other? + *) + +{} + +P0(int *x, int *y) +{ + int r0; + + r0 = READ_ONCE(*x); + smp_store_release(y, 1); +} + +P1(int *x, int *y) +{ + int r0; + + r0 = smp_load_acquire(y); + WRITE_ONCE(*x, 1); +} + +exists (0:r0=1 /\ 1:r0=1) diff --git a/tools/memory-model/litmus-tests/LB+poonceonces.litmus b/tools/memory-model/litmus-tests/LB+poonceonces.litmus new file mode 100644 index 000000000000..74c49cb3c37b --- /dev/null +++ b/tools/memory-model/litmus-tests/LB+poonceonces.litmus @@ -0,0 +1,28 @@ +C LB+poonceonces + +(* + * Result: Sometimes + * + * Can the counter-intuitive outcome for the load-buffering pattern + * be prevented even with no explicit ordering? + *) + +{} + +P0(int *x, int *y) +{ + int r0; + + r0 = READ_ONCE(*x); + WRITE_ONCE(*y, 1); +} + +P1(int *x, int *y) +{ + int r0; + + r0 = READ_ONCE(*y); + WRITE_ONCE(*x, 1); +} + +exists (0:r0=1 /\ 1:r0=1) diff --git a/tools/memory-model/litmus-tests/MP+onceassign+derefonce.litmus b/tools/memory-model/litmus-tests/MP+onceassign+derefonce.litmus new file mode 100644 index 000000000000..97731b4bbdd8 --- /dev/null +++ b/tools/memory-model/litmus-tests/MP+onceassign+derefonce.litmus @@ -0,0 +1,34 @@ +C MP+onceassign+derefonce + +(* + * Result: Never + * + * This litmus test demonstrates that rcu_assign_pointer() and + * rcu_dereference() suffice to ensure that an RCU reader will not see + * pre-initialization garbage when it traverses an RCU-protected data + * structure containing a newly inserted element. + *) + +{ +y=z; +z=0; +} + +P0(int *x, int **y) +{ + WRITE_ONCE(*x, 1); + rcu_assign_pointer(*y, x); +} + +P1(int *x, int **y) +{ + int *r0; + int r1; + + rcu_read_lock(); + r0 = rcu_dereference(*y); + r1 = READ_ONCE(*r0); + rcu_read_unlock(); +} + +exists (1:r0=x /\ 1:r1=0) diff --git a/tools/memory-model/litmus-tests/MP+polocks.litmus b/tools/memory-model/litmus-tests/MP+polocks.litmus new file mode 100644 index 000000000000..712a4fcdf6ce --- /dev/null +++ b/tools/memory-model/litmus-tests/MP+polocks.litmus @@ -0,0 +1,35 @@ +C MP+polocks + +(* + * Result: Never + * + * This litmus test demonstrates how lock acquisitions and releases can + * stand in for smp_load_acquire() and smp_store_release(), respectively. + * In other words, when holding a given lock (or indeed after releasing a + * given lock), a CPU is not only guaranteed to see the accesses that other + * CPUs made while previously holding that lock, it is also guaranteed + * to see all prior accesses by those other CPUs. + *) + +{} + +P0(int *x, int *y, spinlock_t *mylock) +{ + WRITE_ONCE(*x, 1); + spin_lock(mylock); + WRITE_ONCE(*y, 1); + spin_unlock(mylock); +} + +P1(int *x, int *y, spinlock_t *mylock) +{ + int r0; + int r1; + + spin_lock(mylock); + r0 = READ_ONCE(*y); + spin_unlock(mylock); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 1:r1=0) diff --git a/tools/memory-model/litmus-tests/MP+poonceonces.litmus b/tools/memory-model/litmus-tests/MP+poonceonces.litmus new file mode 100644 index 000000000000..b2b60b84fb9d --- /dev/null +++ b/tools/memory-model/litmus-tests/MP+poonceonces.litmus @@ -0,0 +1,27 @@ +C MP+poonceonces + +(* + * Result: Maybe + * + * Can the counter-intuitive message-passing outcome be prevented with + * no ordering at all? + *) + +{} + +P0(int *x, int *y) +{ + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); +} + +P1(int *x, int *y) +{ + int r0; + int r1; + + r0 = READ_ONCE(*y); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 1:r1=0) diff --git a/tools/memory-model/litmus-tests/MP+pooncerelease+poacquireonce.litmus b/tools/memory-model/litmus-tests/MP+pooncerelease+poacquireonce.litmus new file mode 100644 index 000000000000..d52c68429722 --- /dev/null +++ b/tools/memory-model/litmus-tests/MP+pooncerelease+poacquireonce.litmus @@ -0,0 +1,28 @@ +C MP+pooncerelease+poacquireonce + +(* + * Result: Never + * + * This litmus test demonstrates that smp_store_release() and + * smp_load_acquire() provide sufficient ordering for the message-passing + * pattern. + *) + +{} + +P0(int *x, int *y) +{ + WRITE_ONCE(*x, 1); + smp_store_release(y, 1); +} + +P1(int *x, int *y) +{ + int r0; + int r1; + + r0 = smp_load_acquire(y); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 1:r1=0) diff --git a/tools/memory-model/litmus-tests/MP+porevlocks.litmus b/tools/memory-model/litmus-tests/MP+porevlocks.litmus new file mode 100644 index 000000000000..72c9276b363e --- /dev/null +++ b/tools/memory-model/litmus-tests/MP+porevlocks.litmus @@ -0,0 +1,35 @@ +C MP+porevlocks + +(* + * Result: Never + * + * This litmus test demonstrates how lock acquisitions and releases can + * stand in for smp_load_acquire() and smp_store_release(), respectively. + * In other words, when holding a given lock (or indeed after releasing a + * given lock), a CPU is not only guaranteed to see the accesses that other + * CPUs made while previously holding that lock, it is also guaranteed to + * see all prior accesses by those other CPUs. + *) + +{} + +P0(int *x, int *y, spinlock_t *mylock) +{ + int r0; + int r1; + + r0 = READ_ONCE(*y); + spin_lock(mylock); + r1 = READ_ONCE(*x); + spin_unlock(mylock); +} + +P1(int *x, int *y, spinlock_t *mylock) +{ + spin_lock(mylock); + WRITE_ONCE(*x, 1); + spin_unlock(mylock); + WRITE_ONCE(*y, 1); +} + +exists (0:r0=1 /\ 0:r1=0) diff --git a/tools/memory-model/litmus-tests/MP+wmbonceonce+rmbonceonce.litmus b/tools/memory-model/litmus-tests/MP+wmbonceonce+rmbonceonce.litmus new file mode 100644 index 000000000000..c078f38ff27a --- /dev/null +++ b/tools/memory-model/litmus-tests/MP+wmbonceonce+rmbonceonce.litmus @@ -0,0 +1,30 @@ +C MP+wmbonceonce+rmbonceonce + +(* + * Result: Never + * + * This litmus test demonstrates that smp_wmb() and smp_rmb() provide + * sufficient ordering for the message-passing pattern. However, it + * is usually better to use smp_store_release() and smp_load_acquire(). + *) + +{} + +P0(int *x, int *y) +{ + WRITE_ONCE(*x, 1); + smp_wmb(); + WRITE_ONCE(*y, 1); +} + +P1(int *x, int *y) +{ + int r0; + int r1; + + r0 = READ_ONCE(*y); + smp_rmb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 1:r1=0) diff --git a/tools/memory-model/litmus-tests/R+mbonceonces.litmus b/tools/memory-model/litmus-tests/R+mbonceonces.litmus new file mode 100644 index 000000000000..a0e884ad2132 --- /dev/null +++ b/tools/memory-model/litmus-tests/R+mbonceonces.litmus @@ -0,0 +1,30 @@ +C R+mbonceonces + +(* + * Result: Never + * + * This is the fully ordered (via smp_mb()) version of one of the classic + * counterintuitive litmus tests that illustrates the effects of store + * propagation delays. Note that weakening either of the barriers would + * cause the resulting test to be allowed. + *) + +{} + +P0(int *x, int *y) +{ + WRITE_ONCE(*x, 1); + smp_mb(); + WRITE_ONCE(*y, 1); +} + +P1(int *x, int *y) +{ + int r0; + + WRITE_ONCE(*y, 2); + smp_mb(); + r0 = READ_ONCE(*x); +} + +exists (y=2 /\ 1:r0=0) diff --git a/tools/memory-model/litmus-tests/R+poonceonces.litmus b/tools/memory-model/litmus-tests/R+poonceonces.litmus new file mode 100644 index 000000000000..5386f128a131 --- /dev/null +++ b/tools/memory-model/litmus-tests/R+poonceonces.litmus @@ -0,0 +1,27 @@ +C R+poonceonces + +(* + * Result: Sometimes + * + * This is the unordered (thus lacking smp_mb()) version of one of the + * classic counterintuitive litmus tests that illustrates the effects of + * store propagation delays. + *) + +{} + +P0(int *x, int *y) +{ + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); +} + +P1(int *x, int *y) +{ + int r0; + + WRITE_ONCE(*y, 2); + r0 = READ_ONCE(*x); +} + +exists (y=2 /\ 1:r0=0) diff --git a/tools/memory-model/litmus-tests/README b/tools/memory-model/litmus-tests/README new file mode 100644 index 000000000000..04096fb8b8d9 --- /dev/null +++ b/tools/memory-model/litmus-tests/README @@ -0,0 +1,131 @@ +This directory contains the following litmus tests: + +CoRR+poonceonce+Once.litmus + Test of read-read coherence, that is, whether or not two + successive reads from the same variable are ordered. + +CoRW+poonceonce+Once.litmus + Test of read-write coherence, that is, whether or not a read + from a given variable followed by a write to that same variable + are ordered. + +CoWR+poonceonce+Once.litmus + Test of write-read coherence, that is, whether or not a write + to a given variable followed by a read from that same variable + are ordered. + +CoWW+poonceonce.litmus + Test of write-write coherence, that is, whether or not two + successive writes to the same variable are ordered. + +IRIW+mbonceonces+OnceOnce.litmus + Test of independent reads from independent writes with smp_mb() + between each pairs of reads. In other words, is smp_mb() + sufficient to cause two different reading processes to agree on + the order of a pair of writes, where each write is to a different + variable by a different process? + +IRIW+poonceonces+OnceOnce.litmus + Test of independent reads from independent writes with nothing + between each pairs of reads. In other words, is anything at all + needed to cause two different reading processes to agree on the + order of a pair of writes, where each write is to a different + variable by a different process? + +ISA2+pooncelock+pooncelock+pombonce.litmus + Tests whether the ordering provided by a lock-protected S + litmus test is visible to an external process whose accesses are + separated by smp_mb(). This addition of an external process to + S is otherwise known as ISA2. + +ISA2+poonceonces.litmus + As below, but with store-release replaced with WRITE_ONCE() + and load-acquire replaced with READ_ONCE(). + +ISA2+pooncerelease+poacquirerelease+poacquireonce.litmus + Can a release-acquire chain order a prior store against + a later load? + +LB+ctrlonceonce+mbonceonce.litmus + Does a control dependency and an smp_mb() suffice for the + load-buffering litmus test, where each process reads from one + of two variables then writes to the other? + +LB+poacquireonce+pooncerelease.litmus + Does a release-acquire pair suffice for the load-buffering + litmus test, where each process reads from one of two variables then + writes to the other? + +LB+poonceonces.litmus + As above, but with store-release replaced with WRITE_ONCE() + and load-acquire replaced with READ_ONCE(). + +MP+onceassign+derefonce.litmus + As below, but with rcu_assign_pointer() and an rcu_dereference(). + +MP+polocks.litmus + As below, but with the second access of the writer process + and the first access of reader process protected by a lock. + +MP+poonceonces.litmus + As below, but without the smp_rmb() and smp_wmb(). + +MP+pooncerelease+poacquireonce.litmus + As below, but with a release-acquire chain. + +MP+porevlocks.litmus + As below, but with the first access of the writer process + and the second access of reader process protected by a lock. + +MP+wmbonceonce+rmbonceonce.litmus + Does a smp_wmb() (between the stores) and an smp_rmb() (between + the loads) suffice for the message-passing litmus test, where one + process writes data and then a flag, and the other process reads + the flag and then the data. (This is similar to the ISA2 tests, + but with two processes instead of three.) + +R+mbonceonces.litmus + This is the fully ordered (via smp_mb()) version of one of + the classic counterintuitive litmus tests that illustrates the + effects of store propagation delays. + +R+poonceonces.litmus + As above, but without the smp_mb() invocations. + +SB+mbonceonces.litmus + This is the fully ordered (again, via smp_mb() version of store + buffering, which forms the core of Dekker's mutual-exclusion + algorithm. + +SB+poonceonces.litmus + As above, but without the smp_mb() invocations. + +S+poonceonces.litmus + As below, but without the smp_wmb() and acquire load. + +S+wmbonceonce+poacquireonce.litmus + Can a smp_wmb(), instead of a release, and an acquire order + a prior store against a subsequent store? + +WRC+poonceonces+Once.litmus +WRC+pooncerelease+rmbonceonce+Once.litmus + These two are members of an extension of the MP litmus-test class + in which the first write is moved to a separate process. + +Z6.0+pooncelock+pooncelock+pombonce.litmus + Is the ordering provided by a spin_unlock() and a subsequent + spin_lock() sufficient to make ordering apparent to accesses + by a process not holding the lock? + +Z6.0+pooncelock+poonceLock+pombonce.litmus + As above, but with smp_mb__after_spinlock() immediately + following the spin_lock(). + +Z6.0+pooncerelease+poacquirerelease+mbonceonce.litmus + Is the ordering provided by a release-acquire chain sufficient + to make ordering apparent to accesses by a process that does + not participate in that release-acquire chain? + +A great many more litmus tests are available here: + + https://github.com/paulmckrcu/litmus diff --git a/tools/memory-model/litmus-tests/S+poonceonces.litmus b/tools/memory-model/litmus-tests/S+poonceonces.litmus new file mode 100644 index 000000000000..8c9c2f81a580 --- /dev/null +++ b/tools/memory-model/litmus-tests/S+poonceonces.litmus @@ -0,0 +1,28 @@ +C S+poonceonces + +(* + * Result: Sometimes + * + * Starting with a two-process release-acquire chain ordering P0()'s + * first store against P1()'s final load, if the smp_store_release() + * is replaced by WRITE_ONCE() and the smp_load_acquire() replaced by + * READ_ONCE(), is ordering preserved? + *) + +{} + +P0(int *x, int *y) +{ + WRITE_ONCE(*x, 2); + WRITE_ONCE(*y, 1); +} + +P1(int *x, int *y) +{ + int r0; + + r0 = READ_ONCE(*y); + WRITE_ONCE(*x, 1); +} + +exists (x=2 /\ 1:r0=1) diff --git a/tools/memory-model/litmus-tests/S+wmbonceonce+poacquireonce.litmus b/tools/memory-model/litmus-tests/S+wmbonceonce+poacquireonce.litmus new file mode 100644 index 000000000000..c53350205d28 --- /dev/null +++ b/tools/memory-model/litmus-tests/S+wmbonceonce+poacquireonce.litmus @@ -0,0 +1,27 @@ +C S+wmbonceonce+poacquireonce + +(* + * Result: Never + * + * Can a smp_wmb(), instead of a release, and an acquire order a prior + * store against a subsequent store? + *) + +{} + +P0(int *x, int *y) +{ + WRITE_ONCE(*x, 2); + smp_wmb(); + WRITE_ONCE(*y, 1); +} + +P1(int *x, int *y) +{ + int r0; + + r0 = smp_load_acquire(y); + WRITE_ONCE(*x, 1); +} + +exists (x=2 /\ 1:r0=1) diff --git a/tools/memory-model/litmus-tests/SB+mbonceonces.litmus b/tools/memory-model/litmus-tests/SB+mbonceonces.litmus new file mode 100644 index 000000000000..74b874ffa8da --- /dev/null +++ b/tools/memory-model/litmus-tests/SB+mbonceonces.litmus @@ -0,0 +1,32 @@ +C SB+mbonceonces + +(* + * Result: Never + * + * This litmus test demonstrates that full memory barriers suffice to + * order the store-buffering pattern, where each process writes to the + * variable that the preceding process reads. (Locking and RCU can also + * suffice, but not much else.) + *) + +{} + +P0(int *x, int *y) +{ + int r0; + + WRITE_ONCE(*x, 1); + smp_mb(); + r0 = READ_ONCE(*y); +} + +P1(int *x, int *y) +{ + int r0; + + WRITE_ONCE(*y, 1); + smp_mb(); + r0 = READ_ONCE(*x); +} + +exists (0:r0=0 /\ 1:r0=0) diff --git a/tools/memory-model/litmus-tests/SB+poonceonces.litmus b/tools/memory-model/litmus-tests/SB+poonceonces.litmus new file mode 100644 index 000000000000..10d550730b25 --- /dev/null +++ b/tools/memory-model/litmus-tests/SB+poonceonces.litmus @@ -0,0 +1,29 @@ +C SB+poonceonces + +(* + * Result: Sometimes + * + * This litmus test demonstrates that at least some ordering is required + * to order the store-buffering pattern, where each process writes to the + * variable that the preceding process reads. + *) + +{} + +P0(int *x, int *y) +{ + int r0; + + WRITE_ONCE(*x, 1); + r0 = READ_ONCE(*y); +} + +P1(int *x, int *y) +{ + int r0; + + WRITE_ONCE(*y, 1); + r0 = READ_ONCE(*x); +} + +exists (0:r0=0 /\ 1:r0=0) diff --git a/tools/memory-model/litmus-tests/WRC+poonceonces+Once.litmus b/tools/memory-model/litmus-tests/WRC+poonceonces+Once.litmus new file mode 100644 index 000000000000..6a2bc12a1af1 --- /dev/null +++ b/tools/memory-model/litmus-tests/WRC+poonceonces+Once.litmus @@ -0,0 +1,35 @@ +C WRC+poonceonces+Once + +(* + * Result: Sometimes + * + * This litmus test is an extension of the message-passing pattern, + * where the first write is moved to a separate process. Note that this + * test has no ordering at all. + *) + +{} + +P0(int *x) +{ + WRITE_ONCE(*x, 1); +} + +P1(int *x, int *y) +{ + int r0; + + r0 = READ_ONCE(*x); + WRITE_ONCE(*y, 1); +} + +P2(int *x, int *y) +{ + int r0; + int r1; + + r0 = READ_ONCE(*y); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 2:r0=1 /\ 2:r1=0) diff --git a/tools/memory-model/litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus b/tools/memory-model/litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus new file mode 100644 index 000000000000..97fcbffde9a0 --- /dev/null +++ b/tools/memory-model/litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus @@ -0,0 +1,36 @@ +C WRC+pooncerelease+rmbonceonce+Once + +(* + * Result: Never + * + * This litmus test is an extension of the message-passing pattern, where + * the first write is moved to a separate process. Because it features + * a release and a read memory barrier, it should be forbidden. + *) + +{} + +P0(int *x) +{ + WRITE_ONCE(*x, 1); +} + +P1(int *x, int *y) +{ + int r0; + + r0 = READ_ONCE(*x); + smp_store_release(y, 1); +} + +P2(int *x, int *y) +{ + int r0; + int r1; + + r0 = READ_ONCE(*y); + smp_rmb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 2:r0=1 /\ 2:r1=0) diff --git a/tools/memory-model/litmus-tests/Z6.0+pooncelock+poonceLock+pombonce.litmus b/tools/memory-model/litmus-tests/Z6.0+pooncelock+poonceLock+pombonce.litmus new file mode 100644 index 000000000000..415248fb6699 --- /dev/null +++ b/tools/memory-model/litmus-tests/Z6.0+pooncelock+poonceLock+pombonce.litmus @@ -0,0 +1,42 @@ +C Z6.0+pooncelock+poonceLock+pombonce + +(* + * Result: Never + * + * This litmus test demonstrates how smp_mb__after_spinlock() may be + * used to ensure that accesses in different critical sections for a + * given lock running on different CPUs are nevertheless seen in order + * by CPUs not holding that lock. + *) + +{} + +P0(int *x, int *y, spinlock_t *mylock) +{ + spin_lock(mylock); + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); + spin_unlock(mylock); +} + +P1(int *y, int *z, spinlock_t *mylock) +{ + int r0; + + spin_lock(mylock); + smp_mb__after_spinlock(); + r0 = READ_ONCE(*y); + WRITE_ONCE(*z, 1); + spin_unlock(mylock); +} + +P2(int *x, int *z) +{ + int r1; + + WRITE_ONCE(*z, 2); + smp_mb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ z=2 /\ 2:r1=0) diff --git a/tools/memory-model/litmus-tests/Z6.0+pooncelock+pooncelock+pombonce.litmus b/tools/memory-model/litmus-tests/Z6.0+pooncelock+pooncelock+pombonce.litmus new file mode 100644 index 000000000000..10a2aa04cd07 --- /dev/null +++ b/tools/memory-model/litmus-tests/Z6.0+pooncelock+pooncelock+pombonce.litmus @@ -0,0 +1,40 @@ +C Z6.0+pooncelock+pooncelock+pombonce + +(* + * Result: Sometimes + * + * This example demonstrates that a pair of accesses made by different + * processes each while holding a given lock will not necessarily be + * seen as ordered by a third process not holding that lock. + *) + +{} + +P0(int *x, int *y, spinlock_t *mylock) +{ + spin_lock(mylock); + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); + spin_unlock(mylock); +} + +P1(int *y, int *z, spinlock_t *mylock) +{ + int r0; + + spin_lock(mylock); + r0 = READ_ONCE(*y); + WRITE_ONCE(*z, 1); + spin_unlock(mylock); +} + +P2(int *x, int *z) +{ + int r1; + + WRITE_ONCE(*z, 2); + smp_mb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ z=2 /\ 2:r1=0) diff --git a/tools/memory-model/litmus-tests/Z6.0+pooncerelease+poacquirerelease+mbonceonce.litmus b/tools/memory-model/litmus-tests/Z6.0+pooncerelease+poacquirerelease+mbonceonce.litmus new file mode 100644 index 000000000000..a20fc3fafb53 --- /dev/null +++ b/tools/memory-model/litmus-tests/Z6.0+pooncerelease+poacquirerelease+mbonceonce.litmus @@ -0,0 +1,42 @@ +C Z6.0+pooncerelease+poacquirerelease+mbonceonce + +(* + * Result: Sometimes + * + * This litmus test shows that a release-acquire chain, while sufficient + * when there is but one non-reads-from (AKA non-rf) link, does not suffice + * if there is more than one. Of the three processes, only P1() reads from + * P0's write, which means that there are two non-rf links: P1() to P2() + * is a write-to-write link (AKA a "coherence" or just "co" link) and P2() + * to P0() is a read-to-write link (AKA a "from-reads" or just "fr" link). + * When there are two or more non-rf links, you typically will need one + * full barrier for each non-rf link. (Exceptions include some cases + * involving locking.) + *) + +{} + +P0(int *x, int *y) +{ + WRITE_ONCE(*x, 1); + smp_store_release(y, 1); +} + +P1(int *y, int *z) +{ + int r0; + + r0 = smp_load_acquire(y); + smp_store_release(z, 1); +} + +P2(int *x, int *z) +{ + int r1; + + WRITE_ONCE(*z, 2); + smp_mb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ z=2 /\ 2:r1=0) |