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