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