1This document provides "recipes", that is, litmus tests for commonly 2occurring situations, as well as a few that illustrate subtly broken but 3attractive nuisances. Many of these recipes include example code from 4v5.7 of the Linux kernel. 5 6The first section covers simple special cases, the second section 7takes off the training wheels to cover more involved examples, 8and the third section provides a few rules of thumb. 9 10 11Simple special cases 12==================== 13 14This section presents two simple special cases, the first being where 15there is only one CPU or only one memory location is accessed, and the 16second being use of that old concurrency workhorse, locking. 17 18 19Single CPU or single memory location 20------------------------------------ 21 22If there is only one CPU on the one hand or only one variable 23on the other, the code will execute in order. There are (as 24usual) some things to be careful of: 25 261. Some aspects of the C language are unordered. For example, 27 in the expression "f(x) + g(y)", the order in which f and g are 28 called is not defined; the object code is allowed to use either 29 order or even to interleave the computations. 30 312. Compilers are permitted to use the "as-if" rule. That is, a 32 compiler can emit whatever code it likes for normal accesses, 33 as long as the results of a single-threaded execution appear 34 just as if the compiler had followed all the relevant rules. 35 To see this, compile with a high level of optimization and run 36 the debugger on the resulting binary. 37 383. If there is only one variable but multiple CPUs, that variable 39 must be properly aligned and all accesses to that variable must 40 be full sized. Variables that straddle cachelines or pages void 41 your full-ordering warranty, as do undersized accesses that load 42 from or store to only part of the variable. 43 444. If there are multiple CPUs, accesses to shared variables should 45 use READ_ONCE() and WRITE_ONCE() or stronger to prevent load/store 46 tearing, load/store fusing, and invented loads and stores. 47 There are exceptions to this rule, including: 48 49 i. When there is no possibility of a given shared variable 50 being updated by some other CPU, for example, while 51 holding the update-side lock, reads from that variable 52 need not use READ_ONCE(). 53 54 ii. When there is no possibility of a given shared variable 55 being either read or updated by other CPUs, for example, 56 when running during early boot, reads from that variable 57 need not use READ_ONCE() and writes to that variable 58 need not use WRITE_ONCE(). 59 60 61Locking 62------- 63 64Locking is well-known and straightforward, at least if you don't think 65about it too hard. And the basic rule is indeed quite simple: Any CPU that 66has acquired a given lock sees any changes previously seen or made by any 67CPU before it released that same lock. Note that this statement is a bit 68stronger than "Any CPU holding a given lock sees all changes made by any 69CPU during the time that CPU was holding this same lock". For example, 70consider the following pair of code fragments: 71 72 /* See MP+polocks.litmus. */ 73 void CPU0(void) 74 { 75 WRITE_ONCE(x, 1); 76 spin_lock(&mylock); 77 WRITE_ONCE(y, 1); 78 spin_unlock(&mylock); 79 } 80 81 void CPU1(void) 82 { 83 spin_lock(&mylock); 84 r0 = READ_ONCE(y); 85 spin_unlock(&mylock); 86 r1 = READ_ONCE(x); 87 } 88 89The basic rule guarantees that if CPU0() acquires mylock before CPU1(), 90then both r0 and r1 must be set to the value 1. This also has the 91consequence that if the final value of r0 is equal to 1, then the final 92value of r1 must also be equal to 1. In contrast, the weaker rule would 93say nothing about the final value of r1. 94 95The converse to the basic rule also holds, as illustrated by the 96following litmus test: 97 98 /* See MP+porevlocks.litmus. */ 99 void CPU0(void) 100 { 101 r0 = READ_ONCE(y); 102 spin_lock(&mylock); 103 r1 = READ_ONCE(x); 104 spin_unlock(&mylock); 105 } 106 107 void CPU1(void) 108 { 109 spin_lock(&mylock); 110 WRITE_ONCE(x, 1); 111 spin_unlock(&mylock); 112 WRITE_ONCE(y, 1); 113 } 114 115This converse to the basic rule guarantees that if CPU0() acquires 116mylock before CPU1(), then both r0 and r1 must be set to the value 0. 117This also has the consequence that if the final value of r1 is equal 118to 0, then the final value of r0 must also be equal to 0. In contrast, 119the weaker rule would say nothing about the final value of r0. 120 121These examples show only a single pair of CPUs, but the effects of the 122locking basic rule extend across multiple acquisitions of a given lock 123across multiple CPUs. 124 125However, it is not necessarily the case that accesses ordered by 126locking will be seen as ordered by CPUs not holding that lock. 127Consider this example: 128 129 /* See Z6.0+pooncelock+pooncelock+pombonce.litmus. */ 130 void CPU0(void) 131 { 132 spin_lock(&mylock); 133 WRITE_ONCE(x, 1); 134 WRITE_ONCE(y, 1); 135 spin_unlock(&mylock); 136 } 137 138 void CPU1(void) 139 { 140 spin_lock(&mylock); 141 r0 = READ_ONCE(y); 142 WRITE_ONCE(z, 1); 143 spin_unlock(&mylock); 144 } 145 146 void CPU2(void) 147 { 148 WRITE_ONCE(z, 2); 149 smp_mb(); 150 r1 = READ_ONCE(x); 151 } 152 153Counter-intuitive though it might be, it is quite possible to have 154the final value of r0 be 1, the final value of z be 2, and the final 155value of r1 be 0. The reason for this surprising outcome is that 156CPU2() never acquired the lock, and thus did not benefit from the 157lock's ordering properties. 158 159Ordering can be extended to CPUs not holding the lock by careful use 160of smp_mb__after_spinlock(): 161 162 /* See Z6.0+pooncelock+poonceLock+pombonce.litmus. */ 163 void CPU0(void) 164 { 165 spin_lock(&mylock); 166 WRITE_ONCE(x, 1); 167 WRITE_ONCE(y, 1); 168 spin_unlock(&mylock); 169 } 170 171 void CPU1(void) 172 { 173 spin_lock(&mylock); 174 smp_mb__after_spinlock(); 175 r0 = READ_ONCE(y); 176 WRITE_ONCE(z, 1); 177 spin_unlock(&mylock); 178 } 179 180 void CPU2(void) 181 { 182 WRITE_ONCE(z, 2); 183 smp_mb(); 184 r1 = READ_ONCE(x); 185 } 186 187This addition of smp_mb__after_spinlock() strengthens the lock acquisition 188sufficiently to rule out the counter-intuitive outcome. 189 190 191Taking off the training wheels 192============================== 193 194This section looks at more complex examples, including message passing, 195load buffering, release-acquire chains, store buffering. 196Many classes of litmus tests have abbreviated names, which may be found 197here: https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf 198 199 200Message passing (MP) 201-------------------- 202 203The MP pattern has one CPU execute a pair of stores to a pair of variables 204and another CPU execute a pair of loads from this same pair of variables, 205but in the opposite order. The goal is to avoid the counter-intuitive 206outcome in which the first load sees the value written by the second store 207but the second load does not see the value written by the first store. 208In the absence of any ordering, this goal may not be met, as can be seen 209in the MP+poonceonces.litmus litmus test. This section therefore looks at 210a number of ways of meeting this goal. 211 212 213Release and acquire 214~~~~~~~~~~~~~~~~~~~ 215 216Use of smp_store_release() and smp_load_acquire() is one way to force 217the desired MP ordering. The general approach is shown below: 218 219 /* See MP+pooncerelease+poacquireonce.litmus. */ 220 void CPU0(void) 221 { 222 WRITE_ONCE(x, 1); 223 smp_store_release(&y, 1); 224 } 225 226 void CPU1(void) 227 { 228 r0 = smp_load_acquire(&y); 229 r1 = READ_ONCE(x); 230 } 231 232The smp_store_release() macro orders any prior accesses against the 233store, while the smp_load_acquire macro orders the load against any 234subsequent accesses. Therefore, if the final value of r0 is the value 1, 235the final value of r1 must also be the value 1. 236 237The init_stack_slab() function in lib/stackdepot.c uses release-acquire 238in this way to safely initialize of a slab of the stack. Working out 239the mutual-exclusion design is left as an exercise for the reader. 240 241 242Assign and dereference 243~~~~~~~~~~~~~~~~~~~~~~ 244 245Use of rcu_assign_pointer() and rcu_dereference() is quite similar to the 246use of smp_store_release() and smp_load_acquire(), except that both 247rcu_assign_pointer() and rcu_dereference() operate on RCU-protected 248pointers. The general approach is shown below: 249 250 /* See MP+onceassign+derefonce.litmus. */ 251 int z; 252 int *y = &z; 253 int x; 254 255 void CPU0(void) 256 { 257 WRITE_ONCE(x, 1); 258 rcu_assign_pointer(y, &x); 259 } 260 261 void CPU1(void) 262 { 263 rcu_read_lock(); 264 r0 = rcu_dereference(y); 265 r1 = READ_ONCE(*r0); 266 rcu_read_unlock(); 267 } 268 269In this example, if the final value of r0 is &x then the final value of 270r1 must be 1. 271 272The rcu_assign_pointer() macro has the same ordering properties as does 273smp_store_release(), but the rcu_dereference() macro orders the load only 274against later accesses that depend on the value loaded. A dependency 275is present if the value loaded determines the address of a later access 276(address dependency, as shown above), the value written by a later store 277(data dependency), or whether or not a later store is executed in the 278first place (control dependency). Note that the term "data dependency" 279is sometimes casually used to cover both address and data dependencies. 280 281In lib/math/prime_numbers.c, the expand_to_next_prime() function invokes 282rcu_assign_pointer(), and the next_prime_number() function invokes 283rcu_dereference(). This combination mediates access to a bit vector 284that is expanded as additional primes are needed. 285 286 287Write and read memory barriers 288~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 289 290It is usually better to use smp_store_release() instead of smp_wmb() 291and to use smp_load_acquire() instead of smp_rmb(). However, the older 292smp_wmb() and smp_rmb() APIs are still heavily used, so it is important 293to understand their use cases. The general approach is shown below: 294 295 /* See MP+fencewmbonceonce+fencermbonceonce.litmus. */ 296 void CPU0(void) 297 { 298 WRITE_ONCE(x, 1); 299 smp_wmb(); 300 WRITE_ONCE(y, 1); 301 } 302 303 void CPU1(void) 304 { 305 r0 = READ_ONCE(y); 306 smp_rmb(); 307 r1 = READ_ONCE(x); 308 } 309 310The smp_wmb() macro orders prior stores against later stores, and the 311smp_rmb() macro orders prior loads against later loads. Therefore, if 312the final value of r0 is 1, the final value of r1 must also be 1. 313 314The xlog_state_switch_iclogs() function in fs/xfs/xfs_log.c contains 315the following write-side code fragment: 316 317 log->l_curr_block -= log->l_logBBsize; 318 ASSERT(log->l_curr_block >= 0); 319 smp_wmb(); 320 log->l_curr_cycle++; 321 322And the xlog_valid_lsn() function in fs/xfs/xfs_log_priv.h contains 323the corresponding read-side code fragment: 324 325 cur_cycle = READ_ONCE(log->l_curr_cycle); 326 smp_rmb(); 327 cur_block = READ_ONCE(log->l_curr_block); 328 329Alternatively, consider the following comment in function 330perf_output_put_handle() in kernel/events/ring_buffer.c: 331 332 * kernel user 333 * 334 * if (LOAD ->data_tail) { LOAD ->data_head 335 * (A) smp_rmb() (C) 336 * STORE $data LOAD $data 337 * smp_wmb() (B) smp_mb() (D) 338 * STORE ->data_head STORE ->data_tail 339 * } 340 341The B/C pairing is an example of the MP pattern using smp_wmb() on the 342write side and smp_rmb() on the read side. 343 344Of course, given that smp_mb() is strictly stronger than either smp_wmb() 345or smp_rmb(), any code fragment that would work with smp_rmb() and 346smp_wmb() would also work with smp_mb() replacing either or both of the 347weaker barriers. 348 349 350Load buffering (LB) 351------------------- 352 353The LB pattern has one CPU load from one variable and then store to a 354second, while another CPU loads from the second variable and then stores 355to the first. The goal is to avoid the counter-intuitive situation where 356each load reads the value written by the other CPU's store. In the 357absence of any ordering it is quite possible that this may happen, as 358can be seen in the LB+poonceonces.litmus litmus test. 359 360One way of avoiding the counter-intuitive outcome is through the use of a 361control dependency paired with a full memory barrier: 362 363 /* See LB+fencembonceonce+ctrlonceonce.litmus. */ 364 void CPU0(void) 365 { 366 r0 = READ_ONCE(x); 367 if (r0) 368 WRITE_ONCE(y, 1); 369 } 370 371 void CPU1(void) 372 { 373 r1 = READ_ONCE(y); 374 smp_mb(); 375 WRITE_ONCE(x, 1); 376 } 377 378This pairing of a control dependency in CPU0() with a full memory 379barrier in CPU1() prevents r0 and r1 from both ending up equal to 1. 380 381The A/D pairing from the ring-buffer use case shown earlier also 382illustrates LB. Here is a repeat of the comment in 383perf_output_put_handle() in kernel/events/ring_buffer.c, showing a 384control dependency on the kernel side and a full memory barrier on 385the user side: 386 387 * kernel user 388 * 389 * if (LOAD ->data_tail) { LOAD ->data_head 390 * (A) smp_rmb() (C) 391 * STORE $data LOAD $data 392 * smp_wmb() (B) smp_mb() (D) 393 * STORE ->data_head STORE ->data_tail 394 * } 395 * 396 * Where A pairs with D, and B pairs with C. 397 398The kernel's control dependency between the load from ->data_tail 399and the store to data combined with the user's full memory barrier 400between the load from data and the store to ->data_tail prevents 401the counter-intuitive outcome where the kernel overwrites the data 402before the user gets done loading it. 403 404 405Release-acquire chains 406---------------------- 407 408Release-acquire chains are a low-overhead, flexible, and easy-to-use 409method of maintaining order. However, they do have some limitations that 410need to be fully understood. Here is an example that maintains order: 411 412 /* See ISA2+pooncerelease+poacquirerelease+poacquireonce.litmus. */ 413 void CPU0(void) 414 { 415 WRITE_ONCE(x, 1); 416 smp_store_release(&y, 1); 417 } 418 419 void CPU1(void) 420 { 421 r0 = smp_load_acquire(y); 422 smp_store_release(&z, 1); 423 } 424 425 void CPU2(void) 426 { 427 r1 = smp_load_acquire(z); 428 r2 = READ_ONCE(x); 429 } 430 431In this case, if r0 and r1 both have final values of 1, then r2 must 432also have a final value of 1. 433 434The ordering in this example is stronger than it needs to be. For 435example, ordering would still be preserved if CPU1()'s smp_load_acquire() 436invocation was replaced with READ_ONCE(). 437 438It is tempting to assume that CPU0()'s store to x is globally ordered 439before CPU1()'s store to z, but this is not the case: 440 441 /* See Z6.0+pooncerelease+poacquirerelease+mbonceonce.litmus. */ 442 void CPU0(void) 443 { 444 WRITE_ONCE(x, 1); 445 smp_store_release(&y, 1); 446 } 447 448 void CPU1(void) 449 { 450 r0 = smp_load_acquire(y); 451 smp_store_release(&z, 1); 452 } 453 454 void CPU2(void) 455 { 456 WRITE_ONCE(z, 2); 457 smp_mb(); 458 r1 = READ_ONCE(x); 459 } 460 461One might hope that if the final value of r0 is 1 and the final value 462of z is 2, then the final value of r1 must also be 1, but it really is 463possible for r1 to have the final value of 0. The reason, of course, 464is that in this version, CPU2() is not part of the release-acquire chain. 465This situation is accounted for in the rules of thumb below. 466 467Despite this limitation, release-acquire chains are low-overhead as 468well as simple and powerful, at least as memory-ordering mechanisms go. 469 470 471Store buffering 472--------------- 473 474Store buffering can be thought of as upside-down load buffering, so 475that one CPU first stores to one variable and then loads from a second, 476while another CPU stores to the second variable and then loads from the 477first. Preserving order requires nothing less than full barriers: 478 479 /* See SB+fencembonceonces.litmus. */ 480 void CPU0(void) 481 { 482 WRITE_ONCE(x, 1); 483 smp_mb(); 484 r0 = READ_ONCE(y); 485 } 486 487 void CPU1(void) 488 { 489 WRITE_ONCE(y, 1); 490 smp_mb(); 491 r1 = READ_ONCE(x); 492 } 493 494Omitting either smp_mb() will allow both r0 and r1 to have final 495values of 0, but providing both full barriers as shown above prevents 496this counter-intuitive outcome. 497 498This pattern most famously appears as part of Dekker's locking 499algorithm, but it has a much more practical use within the Linux kernel 500of ordering wakeups. The following comment taken from waitqueue_active() 501in include/linux/wait.h shows the canonical pattern: 502 503 * CPU0 - waker CPU1 - waiter 504 * 505 * for (;;) { 506 * @cond = true; prepare_to_wait(&wq_head, &wait, state); 507 * smp_mb(); // smp_mb() from set_current_state() 508 * if (waitqueue_active(wq_head)) if (@cond) 509 * wake_up(wq_head); break; 510 * schedule(); 511 * } 512 * finish_wait(&wq_head, &wait); 513 514On CPU0, the store is to @cond and the load is in waitqueue_active(). 515On CPU1, prepare_to_wait() contains both a store to wq_head and a call 516to set_current_state(), which contains an smp_mb() barrier; the load is 517"if (@cond)". The full barriers prevent the undesirable outcome where 518CPU1 puts the waiting task to sleep and CPU0 fails to wake it up. 519 520Note that use of locking can greatly simplify this pattern. 521 522 523Rules of thumb 524============== 525 526There might seem to be no pattern governing what ordering primitives are 527needed in which situations, but this is not the case. There is a pattern 528based on the relation between the accesses linking successive CPUs in a 529given litmus test. There are three types of linkage: 530 5311. Write-to-read, where the next CPU reads the value that the 532 previous CPU wrote. The LB litmus-test patterns contain only 533 this type of relation. In formal memory-modeling texts, this 534 relation is called "reads-from" and is usually abbreviated "rf". 535 5362. Read-to-write, where the next CPU overwrites the value that the 537 previous CPU read. The SB litmus test contains only this type 538 of relation. In formal memory-modeling texts, this relation is 539 often called "from-reads" and is sometimes abbreviated "fr". 540 5413. Write-to-write, where the next CPU overwrites the value written 542 by the previous CPU. The Z6.0 litmus test pattern contains a 543 write-to-write relation between the last access of CPU1() and 544 the first access of CPU2(). In formal memory-modeling texts, 545 this relation is often called "coherence order" and is sometimes 546 abbreviated "co". In the C++ standard, it is instead called 547 "modification order" and often abbreviated "mo". 548 549The strength of memory ordering required for a given litmus test to 550avoid a counter-intuitive outcome depends on the types of relations 551linking the memory accesses for the outcome in question: 552 553o If all links are write-to-read links, then the weakest 554 possible ordering within each CPU suffices. For example, in 555 the LB litmus test, a control dependency was enough to do the 556 job. 557 558o If all but one of the links are write-to-read links, then a 559 release-acquire chain suffices. Both the MP and the ISA2 560 litmus tests illustrate this case. 561 562o If more than one of the links are something other than 563 write-to-read links, then a full memory barrier is required 564 between each successive pair of non-write-to-read links. This 565 case is illustrated by the Z6.0 litmus tests, both in the 566 locking and in the release-acquire sections. 567 568However, if you find yourself having to stretch these rules of thumb 569to fit your situation, you should consider creating a litmus test and 570running it on the model. 571