Loading...
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
66LB+unlocklockonceonce+poacquireonce.litmus
67 Does a unlock+lock pair provides ordering guarantee between a
68 load and a store?
69
70MP+onceassign+derefonce.litmus
71 As below, but with rcu_assign_pointer() and an rcu_dereference().
72
73MP+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
78MP+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
83MP+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
87MP+poonceonces.litmus
88 As below, but without the smp_rmb() and smp_wmb().
89
90MP+pooncerelease+poacquireonce.litmus
91 As below, but with a release-acquire chain.
92
93MP+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
97MP+unlocklockonceonce+fencermbonceonce.litmus
98 Does a unlock+lock pair provides ordering guarantee between a
99 store and another store?
100
101MP+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
108R+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
113R+poonceonces.litmus
114 As above, but without the smp_mb() invocations.
115
116SB+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
121SB+poonceonces.litmus
122 As above, but without the smp_mb() invocations.
123
124SB+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
133S+poonceonces.litmus
134 As below, but without the smp_wmb() and acquire load.
135
136S+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
140WRC+poonceonces+Once.litmus
141WRC+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
147Z6.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
152Z6.0+pooncelock+poonceLock+pombonce.litmus
153 As above, but with smp_mb__after_spinlock() immediately
154 following the spin_lock().
155
156Z6.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
161A great many more litmus tests are available here:
162
163 https://github.com/paulmckrcu/litmus
164
165==================
166LITMUS TEST NAMING
167==================
168
169Litmus tests are usually named based on their contents, which means that
170looking at the name tells you what the litmus test does. The naming
171scheme covers litmus tests having a single cycle that passes through
172each process exactly once, so litmus tests not fitting this description
173are named on an ad-hoc basis.
174
175The structure of a litmus-test name is the litmus-test class, a plus
176sign ("+"), and one string for each process, separated by plus signs.
177The end of the name is ".litmus".
178
179The litmus-test classes may be found in the infamous test6.pdf:
180https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf
181Each class defines the pattern of accesses and of the variables accessed.
182For example, if the one process writes to a pair of variables, and
183the other process reads from these same variables, the corresponding
184litmus-test class is "MP" (message passing), which may be found on the
185left-hand end of the second row of tests on page one of test6.pdf.
186
187The strings used to identify the actions carried out by each process are
188complex due to a desire to have short(er) names. Thus, there is a tool to
189generate these strings from a given litmus test's actions. For example,
190consider 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
212The next step is to construct a space-separated list of descriptors,
213interleaving descriptions of the relation between a pair of consecutive
214accesses with descriptions of the second access in the pair.
215
216P0()'s WRITE_ONCE() is read by its first READ_ONCE(), which is a
217reads-from link (rf) and internal to the P0() process. This is
218"rfi", which is an abbreviation for "reads-from internal". Because
219some of the tools string these abbreviations together with space
220characters separating processes, the first character is capitalized,
221resulting in "Rfi".
222
223P0()'s second access is a READ_ONCE(), as opposed to (for example)
224smp_load_acquire(), so next is "Once". Thus far, we have "Rfi Once".
225
226P0()'s third access is also a READ_ONCE(), but to y rather than x.
227This is related to P0()'s second access by program order ("po"),
228to a different variable ("d"), and both accesses are reads ("RR").
229The resulting descriptor is "PodRR". Because P0()'s third access is
230READ_ONCE(), we add another "Once" descriptor.
231
232A from-read ("fre") relation links P0()'s third to P1()'s first
233access, and the resulting descriptor is "Fre". P1()'s first access is
234WRITE_ONCE(), which as before gives the descriptor "Once". The string
235thus far is thus "Rfi Once PodRR Once Fre Once".
236
237The remainder of P1() is similar to P0(), which means we add
238"Rfi Once PodRR Once". Another fre links P1()'s last access to
239P0()'s first access, which is WRITE_ONCE(), so we add "Fre Once".
240The full string is thus:
241
242 Rfi Once PodRR Once Fre Once Rfi Once PodRR Once Fre Once
243
244This string can be given to the "norm7" and "classify7" tools to
245produce 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
252Adding the ".litmus" suffix: SB+rfionceonce-poonceonces.litmus
253
254The descriptors that describe connections between consecutive accesses
255within the cycle through a given litmus test can be provided by the herd7
256tool (Rfi, Po, Fre, and so on) or by the linux-kernel.bell file (Once,
257Release, Acquire, and so on).
258
259To see the full list of descriptors, execute the following command:
260
261 $ diyone7 -bell linux-kernel.bell -show edges
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
66LB+unlocklockonceonce+poacquireonce.litmus
67 Does a unlock+lock pair provides ordering guarantee between a
68 load and a store?
69
70MP+onceassign+derefonce.litmus
71 As below, but with rcu_assign_pointer() and an rcu_dereference().
72
73MP+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
78MP+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
83MP+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
87MP+poonceonces.litmus
88 As below, but without the smp_rmb() and smp_wmb().
89
90MP+pooncerelease+poacquireonce.litmus
91 As below, but with a release-acquire chain.
92
93MP+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
97MP+unlocklockonceonce+fencermbonceonce.litmus
98 Does a unlock+lock pair provides ordering guarantee between a
99 store and another store?
100
101MP+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
108R+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
113R+poonceonces.litmus
114 As above, but without the smp_mb() invocations.
115
116SB+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
121SB+poonceonces.litmus
122 As above, but without the smp_mb() invocations.
123
124SB+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
133S+poonceonces.litmus
134 As below, but without the smp_wmb() and acquire load.
135
136S+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
140WRC+poonceonces+Once.litmus
141WRC+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
147Z6.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
152Z6.0+pooncelock+poonceLock+pombonce.litmus
153 As above, but with smp_mb__after_spinlock() immediately
154 following the spin_lock().
155
156Z6.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
161A great many more litmus tests are available here:
162
163 https://github.com/paulmckrcu/litmus
164
165==================
166LITMUS TEST NAMING
167==================
168
169Litmus tests are usually named based on their contents, which means that
170looking at the name tells you what the litmus test does. The naming
171scheme covers litmus tests having a single cycle that passes through
172each process exactly once, so litmus tests not fitting this description
173are named on an ad-hoc basis.
174
175The structure of a litmus-test name is the litmus-test class, a plus
176sign ("+"), and one string for each process, separated by plus signs.
177The end of the name is ".litmus".
178
179The litmus-test classes may be found in the infamous test6.pdf:
180https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf
181Each class defines the pattern of accesses and of the variables accessed.
182For example, if the one process writes to a pair of variables, and
183the other process reads from these same variables, the corresponding
184litmus-test class is "MP" (message passing), which may be found on the
185left-hand end of the second row of tests on page one of test6.pdf.
186
187The strings used to identify the actions carried out by each process are
188complex due to a desire to have short(er) names. Thus, there is a tool to
189generate these strings from a given litmus test's actions. For example,
190consider 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
212The next step is to construct a space-separated list of descriptors,
213interleaving descriptions of the relation between a pair of consecutive
214accesses with descriptions of the second access in the pair.
215
216P0()'s WRITE_ONCE() is read by its first READ_ONCE(), which is a
217reads-from link (rf) and internal to the P0() process. This is
218"rfi", which is an abbreviation for "reads-from internal". Because
219some of the tools string these abbreviations together with space
220characters separating processes, the first character is capitalized,
221resulting in "Rfi".
222
223P0()'s second access is a READ_ONCE(), as opposed to (for example)
224smp_load_acquire(), so next is "Once". Thus far, we have "Rfi Once".
225
226P0()'s third access is also a READ_ONCE(), but to y rather than x.
227This is related to P0()'s second access by program order ("po"),
228to a different variable ("d"), and both accesses are reads ("RR").
229The resulting descriptor is "PodRR". Because P0()'s third access is
230READ_ONCE(), we add another "Once" descriptor.
231
232A from-read ("fre") relation links P0()'s third to P1()'s first
233access, and the resulting descriptor is "Fre". P1()'s first access is
234WRITE_ONCE(), which as before gives the descriptor "Once". The string
235thus far is thus "Rfi Once PodRR Once Fre Once".
236
237The remainder of P1() is similar to P0(), which means we add
238"Rfi Once PodRR Once". Another fre links P1()'s last access to
239P0()'s first access, which is WRITE_ONCE(), so we add "Fre Once".
240The full string is thus:
241
242 Rfi Once PodRR Once Fre Once Rfi Once PodRR Once Fre Once
243
244This string can be given to the "norm7" and "classify7" tools to
245produce 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
252Adding the ".litmus" suffix: SB+rfionceonce-poonceonces.litmus
253
254The descriptors that describe connections between consecutive accesses
255within the cycle through a given litmus test can be provided by the herd7
256tool (Rfi, Po, Fre, and so on) or by the linux-kernel.bell file (Once,
257Release, Acquire, and so on).
258
259To see the full list of descriptors, execute the following command:
260
261 $ diyone7 -bell linux-kernel.bell -show edges