571 lines · plain
1This document provides "recipes", that is, litmus tests for commonly2occurring situations, as well as a few that illustrate subtly broken but3attractive nuisances. Many of these recipes include example code from4v5.7 of the Linux kernel.5 6The first section covers simple special cases, the second section7takes off the training wheels to cover more involved examples,8and the third section provides a few rules of thumb.9 10 11Simple special cases12====================13 14This section presents two simple special cases, the first being where15there is only one CPU or only one memory location is accessed, and the16second being use of that old concurrency workhorse, locking.17 18 19Single CPU or single memory location20------------------------------------21 22If there is only one CPU on the one hand or only one variable23on the other, the code will execute in order. There are (as24usual) 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 are28 called is not defined; the object code is allowed to use either29 order or even to interleave the computations.30 312. Compilers are permitted to use the "as-if" rule. That is, a32 compiler can emit whatever code it likes for normal accesses,33 as long as the results of a single-threaded execution appear34 just as if the compiler had followed all the relevant rules.35 To see this, compile with a high level of optimization and run36 the debugger on the resulting binary.37 383. If there is only one variable but multiple CPUs, that variable39 must be properly aligned and all accesses to that variable must40 be full sized. Variables that straddle cachelines or pages void41 your full-ordering warranty, as do undersized accesses that load42 from or store to only part of the variable.43 444. If there are multiple CPUs, accesses to shared variables should45 use READ_ONCE() and WRITE_ONCE() or stronger to prevent load/store46 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 variable50 being updated by some other CPU, for example, while51 holding the update-side lock, reads from that variable52 need not use READ_ONCE().53 54 ii. When there is no possibility of a given shared variable55 being either read or updated by other CPUs, for example,56 when running during early boot, reads from that variable57 need not use READ_ONCE() and writes to that variable58 need not use WRITE_ONCE().59 60 61Locking62-------63 64Locking is well-known and straightforward, at least if you don't think65about it too hard. And the basic rule is indeed quite simple: Any CPU that66has acquired a given lock sees any changes previously seen or made by any67CPU before it released that same lock. Note that this statement is a bit68stronger than "Any CPU holding a given lock sees all changes made by any69CPU 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 the91consequence that if the final value of r0 is equal to 1, then the final92value of r1 must also be equal to 1. In contrast, the weaker rule would93say nothing about the final value of r1.94 95The converse to the basic rule also holds, as illustrated by the96following 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() acquires116mylock 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 equal118to 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 the122locking basic rule extend across multiple acquisitions of a given lock123across multiple CPUs.124 125However, it is not necessarily the case that accesses ordered by126locking 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 have154the final value of r0 be 1, the final value of z be 2, and the final155value of r1 be 0. The reason for this surprising outcome is that156CPU2() never acquired the lock, and thus did not benefit from the157lock's ordering properties.158 159Ordering can be extended to CPUs not holding the lock by careful use160of 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 acquisition188sufficiently to rule out the counter-intuitive outcome.189 190 191Taking off the training wheels192==============================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 found197here: https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf198 199 200Message passing (MP)201--------------------202 203The MP pattern has one CPU execute a pair of stores to a pair of variables204and 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-intuitive206outcome in which the first load sees the value written by the second store207but 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 seen209in the MP+poonceonces.litmus litmus test. This section therefore looks at210a number of ways of meeting this goal.211 212 213Release and acquire214~~~~~~~~~~~~~~~~~~~215 216Use of smp_store_release() and smp_load_acquire() is one way to force217the 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 the233store, while the smp_load_acquire macro orders the load against any234subsequent 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-acquire238in this way to safely initialize of a slab of the stack. Working out239the mutual-exclusion design is left as an exercise for the reader.240 241 242Assign and dereference243~~~~~~~~~~~~~~~~~~~~~~244 245Use of rcu_assign_pointer() and rcu_dereference() is quite similar to the246use of smp_store_release() and smp_load_acquire(), except that both247rcu_assign_pointer() and rcu_dereference() operate on RCU-protected248pointers. 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 of270r1 must be 1.271 272The rcu_assign_pointer() macro has the same ordering properties as does273smp_store_release(), but the rcu_dereference() macro orders the load only274against later accesses that depend on the value loaded. A dependency275is present if the value loaded determines the address of a later access276(address dependency, as shown above), the value written by a later store277(data dependency), or whether or not a later store is executed in the278first 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 invokes282rcu_assign_pointer(), and the next_prime_number() function invokes283rcu_dereference(). This combination mediates access to a bit vector284that is expanded as additional primes are needed.285 286 287Write and read memory barriers288~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~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 older292smp_wmb() and smp_rmb() APIs are still heavily used, so it is important293to 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 the311smp_rmb() macro orders prior loads against later loads. Therefore, if312the 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 contains315the 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 contains323the 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 function330perf_output_put_handle() in kernel/events/ring_buffer.c:331 332 * kernel user333 *334 * if (LOAD ->data_tail) { LOAD ->data_head335 * (A) smp_rmb() (C)336 * STORE $data LOAD $data337 * smp_wmb() (B) smp_mb() (D)338 * STORE ->data_head STORE ->data_tail339 * }340 341The B/C pairing is an example of the MP pattern using smp_wmb() on the342write 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() and346smp_wmb() would also work with smp_mb() replacing either or both of the347weaker barriers.348 349 350Load buffering (LB)351-------------------352 353The LB pattern has one CPU load from one variable and then store to a354second, while another CPU loads from the second variable and then stores355to the first. The goal is to avoid the counter-intuitive situation where356each load reads the value written by the other CPU's store. In the357absence of any ordering it is quite possible that this may happen, as358can be seen in the LB+poonceonces.litmus litmus test.359 360One way of avoiding the counter-intuitive outcome is through the use of a361control 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 memory379barrier 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 also382illustrates LB. Here is a repeat of the comment in383perf_output_put_handle() in kernel/events/ring_buffer.c, showing a384control dependency on the kernel side and a full memory barrier on385the user side:386 387 * kernel user388 *389 * if (LOAD ->data_tail) { LOAD ->data_head390 * (A) smp_rmb() (C)391 * STORE $data LOAD $data392 * smp_wmb() (B) smp_mb() (D)393 * STORE ->data_head STORE ->data_tail394 * }395 *396 * Where A pairs with D, and B pairs with C.397 398The kernel's control dependency between the load from ->data_tail399and the store to data combined with the user's full memory barrier400between the load from data and the store to ->data_tail prevents401the counter-intuitive outcome where the kernel overwrites the data402before the user gets done loading it.403 404 405Release-acquire chains406----------------------407 408Release-acquire chains are a low-overhead, flexible, and easy-to-use409method of maintaining order. However, they do have some limitations that410need 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 must432also have a final value of 1.433 434The ordering in this example is stronger than it needs to be. For435example, 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 ordered439before 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 value462of z is 2, then the final value of r1 must also be 1, but it really is463possible 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 as468well as simple and powerful, at least as memory-ordering mechanisms go.469 470 471Store buffering472---------------473 474Store buffering can be thought of as upside-down load buffering, so475that 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 the477first. 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 final495values of 0, but providing both full barriers as shown above prevents496this counter-intuitive outcome.497 498This pattern most famously appears as part of Dekker's locking499algorithm, but it has a much more practical use within the Linux kernel500of ordering wakeups. The following comment taken from waitqueue_active()501in include/linux/wait.h shows the canonical pattern:502 503 * CPU0 - waker CPU1 - waiter504 *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 call516to set_current_state(), which contains an smp_mb() barrier; the load is517"if (@cond)". The full barriers prevent the undesirable outcome where518CPU1 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 thumb524==============525 526There might seem to be no pattern governing what ordering primitives are527needed in which situations, but this is not the case. There is a pattern528based on the relation between the accesses linking successive CPUs in a529given litmus test. There are three types of linkage:530 5311. Write-to-read, where the next CPU reads the value that the532 previous CPU wrote. The LB litmus-test patterns contain only533 this type of relation. In formal memory-modeling texts, this534 relation is called "reads-from" and is usually abbreviated "rf".535 5362. Read-to-write, where the next CPU overwrites the value that the537 previous CPU read. The SB litmus test contains only this type538 of relation. In formal memory-modeling texts, this relation is539 often called "from-reads" and is sometimes abbreviated "fr".540 5413. Write-to-write, where the next CPU overwrites the value written542 by the previous CPU. The Z6.0 litmus test pattern contains a543 write-to-write relation between the last access of CPU1() and544 the first access of CPU2(). In formal memory-modeling texts,545 this relation is often called "coherence order" and is sometimes546 abbreviated "co". In the C++ standard, it is instead called547 "modification order" and often abbreviated "mo".548 549The strength of memory ordering required for a given litmus test to550avoid a counter-intuitive outcome depends on the types of relations551linking the memory accesses for the outcome in question:552 553o If all links are write-to-read links, then the weakest554 possible ordering within each CPU suffices. For example, in555 the LB litmus test, a control dependency was enough to do the556 job.557 558o If all but one of the links are write-to-read links, then a559 release-acquire chain suffices. Both the MP and the ISA2560 litmus tests illustrate this case.561 562o If more than one of the links are something other than563 write-to-read links, then a full memory barrier is required564 between each successive pair of non-write-to-read links. This565 case is illustrated by the Z6.0 litmus tests, both in the566 locking and in the release-acquire sections.567 568However, if you find yourself having to stretch these rules of thumb569to fit your situation, you should consider creating a litmus test and570running it on the model.571