• Home
  • Annotate
  • current directory
Name Date Size #Lines LOC

..18-Mar-2022-

.gitignore A D18-Mar-202253 32

CoRR+poonceonce+Once.litmus A D18-Mar-2022311 2720

CoRW+poonceonce+Once.litmus A D18-Mar-2022324 2619

CoWR+poonceonce+Once.litmus A D18-Mar-2022324 2619

CoWW+poonceonce.litmus A D18-Mar-2022237 1914

IRIW+fencembonceonces+OnceOnce.litmus A D18-Mar-2022731 4636

IRIW+poonceonces+OnceOnce.litmus A D18-Mar-2022655 4434

ISA2+pooncelock+pooncelock+pombonce.litmus A D18-Mar-2022588 4132

ISA2+poonceonces.litmus A D18-Mar-2022598 3829

ISA2+pooncerelease+poacquirerelease+poacquireonce.litmus A D18-Mar-2022784 4031

LB+fencembonceonce+ctrlonceonce.litmus A D18-Mar-2022694 3527

LB+poacquireonce+pooncerelease.litmus A D18-Mar-2022412 3022

LB+poonceonces.litmus A D18-Mar-2022346 2921

MP+fencewmbonceonce+fencermbonceonce.litmus A D18-Mar-2022545 3124

MP+onceassign+derefonce.litmus A D18-Mar-2022593 3427

MP+polockmbonce+poacquiresilsil.litmus A D18-Mar-2022745 3528

MP+polockonce+poacquiresilsil.litmus A D18-Mar-2022681 3427

MP+polocks.litmus A D18-Mar-2022825 3629

MP+poonceonces.litmus A D18-Mar-2022386 2821

MP+pooncerelease+poacquireonce.litmus A D18-Mar-2022464 2922

MP+porevlocks.litmus A D18-Mar-2022828 3629

R+fencembonceonces.litmus A D18-Mar-2022499 3124

R+poonceonces.litmus A D18-Mar-2022388 2821

README A D18-Mar-20229.3 KiB254198

S+fencewmbonceonce+poacquireonce.litmus A D18-Mar-2022356 2821

S+poonceonces.litmus A D18-Mar-2022462 2922

SB+fencembonceonces.litmus A D18-Mar-2022499 3325

SB+poonceonces.litmus A D18-Mar-2022423 3022

SB+rfionceonce-poonceonces.litmus A D18-Mar-2022452 3325

WRC+poonceonces+Once.litmus A D18-Mar-2022465 3627

WRC+pooncerelease+fencermbonceonce+Once.litmus A D18-Mar-2022644 3930

Z6.0+pooncelock+poonceLock+pombonce.litmus A D18-Mar-2022723 4334

Z6.0+pooncelock+pooncelock+pombonce.litmus A D18-Mar-2022658 4132

Z6.0+pooncerelease+poacquirerelease+fencembonceonce.litmus A D18-Mar-2022980 4334

README

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