| 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 |