linux/tools/memory-model/litmus-tests/README
<<
>>
Prefs
   1============
   2LITMUS TESTS
   3============
   4
   5CoRR+poonceonce+Once.litmus
   6        Test of read-read coherence, that is, whether or not two
   7        successive reads from the same variable are ordered.
   8
   9CoRW+poonceonce+Once.litmus
  10        Test of read-write coherence, that is, whether or not a read
  11        from a given variable followed by a write to that same variable
  12        are ordered.
  13
  14CoWR+poonceonce+Once.litmus
  15        Test of write-read coherence, that is, whether or not a write
  16        to a given variable followed by a read from that same variable
  17        are ordered.
  18
  19CoWW+poonceonce.litmus
  20        Test of write-write coherence, that is, whether or not two
  21        successive writes to the same variable are ordered.
  22
  23IRIW+fencembonceonces+OnceOnce.litmus
  24        Test of independent reads from independent writes with smp_mb()
  25        between each pairs of reads.  In other words, is smp_mb()
  26        sufficient to cause two different reading processes to agree on
  27        the order of a pair of writes, where each write is to a different
  28        variable by a different process?  This litmus test is forbidden
  29        by LKMM's propagation rule.
  30
  31IRIW+poonceonces+OnceOnce.litmus
  32        Test of independent reads from independent writes with nothing
  33        between each pairs of reads.  In other words, is anything at all
  34        needed to cause two different reading processes to agree on the
  35        order of a pair of writes, where each write is to a different
  36        variable by a different process?
  37
  38ISA2+pooncelock+pooncelock+pombonce.litmus
  39        Tests whether the ordering provided by a lock-protected S
  40        litmus test is visible to an external process whose accesses are
  41        separated by smp_mb().  This addition of an external process to
  42        S is otherwise known as ISA2.
  43
  44ISA2+poonceonces.litmus
  45        As below, but with store-release replaced with WRITE_ONCE()
  46        and load-acquire replaced with READ_ONCE().
  47
  48ISA2+pooncerelease+poacquirerelease+poacquireonce.litmus
  49        Can a release-acquire chain order a prior store against
  50        a later load?
  51
  52LB+fencembonceonce+ctrlonceonce.litmus
  53        Does a control dependency and an smp_mb() suffice for the
  54        load-buffering litmus test, where each process reads from one
  55        of two variables then writes to the other?
  56
  57LB+poacquireonce+pooncerelease.litmus
  58        Does a release-acquire pair suffice for the load-buffering
  59        litmus test, where each process reads from one of two variables then
  60        writes to the other?
  61
  62LB+poonceonces.litmus
  63        As above, but with store-release replaced with WRITE_ONCE()
  64        and load-acquire replaced with READ_ONCE().
  65
  66MP+onceassign+derefonce.litmus
  67        As below, but with rcu_assign_pointer() and an rcu_dereference().
  68
  69MP+polockmbonce+poacquiresilsil.litmus
  70        Protect the access with a lock and an smp_mb__after_spinlock()
  71        in one process, and use an acquire load followed by a pair of
  72        spin_is_locked() calls in the other process.
  73
  74MP+polockonce+poacquiresilsil.litmus
  75        Protect the access with a lock in one process, and use an
  76        acquire load followed by a pair of spin_is_locked() calls
  77        in the other process.
  78
  79MP+polocks.litmus
  80        As below, but with the second access of the writer process
  81        and the first access of reader process protected by a lock.
  82
  83MP+poonceonces.litmus
  84        As below, but without the smp_rmb() and smp_wmb().
  85
  86MP+pooncerelease+poacquireonce.litmus
  87        As below, but with a release-acquire chain.
  88
  89MP+porevlocks.litmus
  90        As below, but with the first access of the writer process
  91        and the second access of reader process protected by a lock.
  92
  93MP+fencewmbonceonce+fencermbonceonce.litmus
  94        Does a smp_wmb() (between the stores) and an smp_rmb() (between
  95        the loads) suffice for the message-passing litmus test, where one
  96        process writes data and then a flag, and the other process reads
  97        the flag and then the data.  (This is similar to the ISA2 tests,
  98        but with two processes instead of three.)
  99
 100R+fencembonceonces.litmus
 101        This is the fully ordered (via smp_mb()) version of one of
 102        the classic counterintuitive litmus tests that illustrates the
 103        effects of store propagation delays.
 104
 105R+poonceonces.litmus
 106        As above, but without the smp_mb() invocations.
 107
 108SB+fencembonceonces.litmus
 109        This is the fully ordered (again, via smp_mb() version of store
 110        buffering, which forms the core of Dekker's mutual-exclusion
 111        algorithm.
 112
 113SB+poonceonces.litmus
 114        As above, but without the smp_mb() invocations.
 115
 116SB+rfionceonce-poonceonces.litmus
 117        This litmus test demonstrates that LKMM is not fully multicopy
 118        atomic.  (Neither is it other multicopy atomic.)  This litmus test
 119        also demonstrates the "locations" debugging aid, which designates
 120        additional registers and locations to be printed out in the dump
 121        of final states in the herd7 output.  Without the "locations"
 122        statement, only those registers and locations mentioned in the
 123        "exists" clause will be printed.
 124
 125S+poonceonces.litmus
 126        As below, but without the smp_wmb() and acquire load.
 127
 128S+fencewmbonceonce+poacquireonce.litmus
 129        Can a smp_wmb(), instead of a release, and an acquire order
 130        a prior store against a subsequent store?
 131
 132WRC+poonceonces+Once.litmus
 133WRC+pooncerelease+fencermbonceonce+Once.litmus
 134        These two are members of an extension of the MP litmus-test
 135        class in which the first write is moved to a separate process.
 136        The second is forbidden because smp_store_release() is
 137        A-cumulative in LKMM.
 138
 139Z6.0+pooncelock+pooncelock+pombonce.litmus
 140        Is the ordering provided by a spin_unlock() and a subsequent
 141        spin_lock() sufficient to make ordering apparent to accesses
 142        by a process not holding the lock?
 143
 144Z6.0+pooncelock+poonceLock+pombonce.litmus
 145        As above, but with smp_mb__after_spinlock() immediately
 146        following the spin_lock().
 147
 148Z6.0+pooncerelease+poacquirerelease+fencembonceonce.litmus
 149        Is the ordering provided by a release-acquire chain sufficient
 150        to make ordering apparent to accesses by a process that does
 151        not participate in that release-acquire chain?
 152
 153A great many more litmus tests are available here:
 154
 155        https://github.com/paulmckrcu/litmus
 156
 157==================
 158LITMUS TEST NAMING
 159==================
 160
 161Litmus tests are usually named based on their contents, which means that
 162looking at the name tells you what the litmus test does.  The naming
 163scheme covers litmus tests having a single cycle that passes through
 164each process exactly once, so litmus tests not fitting this description
 165are named on an ad-hoc basis.
 166
 167The structure of a litmus-test name is the litmus-test class, a plus
 168sign ("+"), and one string for each process, separated by plus signs.
 169The end of the name is ".litmus".
 170
 171The litmus-test classes may be found in the infamous test6.pdf:
 172https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf
 173Each class defines the pattern of accesses and of the variables accessed.
 174For example, if the one process writes to a pair of variables, and
 175the other process reads from these same variables, the corresponding
 176litmus-test class is "MP" (message passing), which may be found on the
 177left-hand end of the second row of tests on page one of test6.pdf.
 178
 179The strings used to identify the actions carried out by each process are
 180complex due to a desire to have short(er) names.  Thus, there is a tool to
 181generate these strings from a given litmus test's actions.  For example,
 182consider the processes from SB+rfionceonce-poonceonces.litmus:
 183
 184        P0(int *x, int *y)
 185        {
 186                int r1;
 187                int r2;
 188
 189                WRITE_ONCE(*x, 1);
 190                r1 = READ_ONCE(*x);
 191                r2 = READ_ONCE(*y);
 192        }
 193
 194        P1(int *x, int *y)
 195        {
 196                int r3;
 197                int r4;
 198
 199                WRITE_ONCE(*y, 1);
 200                r3 = READ_ONCE(*y);
 201                r4 = READ_ONCE(*x);
 202        }
 203
 204The next step is to construct a space-separated list of descriptors,
 205interleaving descriptions of the relation between a pair of consecutive
 206accesses with descriptions of the second access in the pair.
 207
 208P0()'s WRITE_ONCE() is read by its first READ_ONCE(), which is a
 209reads-from link (rf) and internal to the P0() process.  This is
 210"rfi", which is an abbreviation for "reads-from internal".  Because
 211some of the tools string these abbreviations together with space
 212characters separating processes, the first character is capitalized,
 213resulting in "Rfi".
 214
 215P0()'s second access is a READ_ONCE(), as opposed to (for example)
 216smp_load_acquire(), so next is "Once".  Thus far, we have "Rfi Once".
 217
 218P0()'s third access is also a READ_ONCE(), but to y rather than x.
 219This is related to P0()'s second access by program order ("po"),
 220to a different variable ("d"), and both accesses are reads ("RR").
 221The resulting descriptor is "PodRR".  Because P0()'s third access is
 222READ_ONCE(), we add another "Once" descriptor.
 223
 224A from-read ("fre") relation links P0()'s third to P1()'s first
 225access, and the resulting descriptor is "Fre".  P1()'s first access is
 226WRITE_ONCE(), which as before gives the descriptor "Once".  The string
 227thus far is thus "Rfi Once PodRR Once Fre Once".
 228
 229The remainder of P1() is similar to P0(), which means we add
 230"Rfi Once PodRR Once".  Another fre links P1()'s last access to
 231P0()'s first access, which is WRITE_ONCE(), so we add "Fre Once".
 232The full string is thus:
 233
 234        Rfi Once PodRR Once Fre Once Rfi Once PodRR Once Fre Once
 235
 236This string can be given to the "norm7" and "classify7" tools to
 237produce the name:
 238
 239        $ norm7 -bell linux-kernel.bell \
 240                Rfi Once PodRR Once Fre Once Rfi Once PodRR Once Fre Once | \
 241          sed -e 's/:.*//g'
 242        SB+rfionceonce-poonceonces
 243
 244Adding the ".litmus" suffix: SB+rfionceonce-poonceonces.litmus
 245
 246The descriptors that describe connections between consecutive accesses
 247within the cycle through a given litmus test can be provided by the herd7
 248tool (Rfi, Po, Fre, and so on) or by the linux-kernel.bell file (Once,
 249Release, Acquire, and so on).
 250
 251To see the full list of descriptors, execute the following command:
 252
 253        $ diyone7 -bell linux-kernel.bell -show edges
 254