tools/memory-model/litmus-tests/README

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