Linux 5.7.7
[linux/fpc-iii.git] / tools / memory-model / Documentation / recipes.txt
blob7fe8d7aa30290b48da3ad258c0cc5ad612b6a977
1 This document provides "recipes", that is, litmus tests for commonly
2 occurring situations, as well as a few that illustrate subtly broken but
3 attractive nuisances.  Many of these recipes include example code from
4 v4.13 of the Linux kernel.
6 The first section covers simple special cases, the second section
7 takes off the training wheels to cover more involved examples,
8 and the third section provides a few rules of thumb.
11 Simple special cases
12 ====================
14 This section presents two simple special cases, the first being where
15 there is only one CPU or only one memory location is accessed, and the
16 second being use of that old concurrency workhorse, locking.
19 Single CPU or single memory location
20 ------------------------------------
22 If there is only one CPU on the one hand or only one variable
23 on the other, the code will execute in order.  There are (as
24 usual) some things to be careful of:
26 1.      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.
31 2.      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.
38 3.      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.
44 4.      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:
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().
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().
61 Locking
62 -------
64 Locking is well-known and straightforward, at least if you don't think
65 about it too hard.  And the basic rule is indeed quite simple: Any CPU that
66 has acquired a given lock sees any changes previously seen or made by any
67 CPU before it released that same lock.  Note that this statement is a bit
68 stronger than "Any CPU holding a given lock sees all changes made by any
69 CPU during the time that CPU was holding this same lock".  For example,
70 consider the following pair of code fragments:
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         }
81         void CPU1(void)
82         {
83                 spin_lock(&mylock);
84                 r0 = READ_ONCE(y);
85                 spin_unlock(&mylock);
86                 r1 = READ_ONCE(x);
87         }
89 The basic rule guarantees that if CPU0() acquires mylock before CPU1(),
90 then both r0 and r1 must be set to the value 1.  This also has the
91 consequence that if the final value of r0 is equal to 1, then the final
92 value of r1 must also be equal to 1.  In contrast, the weaker rule would
93 say nothing about the final value of r1.
95 The converse to the basic rule also holds, as illustrated by the
96 following litmus test:
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         }
107         void CPU1(void)
108         {
109                 spin_lock(&mylock);
110                 WRITE_ONCE(x, 1);
111                 spin_unlock(&mylock);
112                 WRITE_ONCE(y, 1);
113         }
115 This converse to the basic rule guarantees that if CPU0() acquires
116 mylock before CPU1(), then both r0 and r1 must be set to the value 0.
117 This also has the consequence that if the final value of r1 is equal
118 to 0, then the final value of r0 must also be equal to 0.  In contrast,
119 the weaker rule would say nothing about the final value of r0.
121 These examples show only a single pair of CPUs, but the effects of the
122 locking basic rule extend across multiple acquisitions of a given lock
123 across multiple CPUs.
125 However, it is not necessarily the case that accesses ordered by
126 locking will be seen as ordered by CPUs not holding that lock.
127 Consider this example:
129         /* See Z6.0+pooncerelease+poacquirerelease+fencembonceonce.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         }
138         void CPU1(void)
139         {
140                 spin_lock(&mylock);
141                 r0 = READ_ONCE(y);
142                 WRITE_ONCE(z, 1);
143                 spin_unlock(&mylock);
144         }
146         void CPU2(void)
147         {
148                 WRITE_ONCE(z, 2);
149                 smp_mb();
150                 r1 = READ_ONCE(x);
151         }
153 Counter-intuitive though it might be, it is quite possible to have
154 the final value of r0 be 1, the final value of z be 2, and the final
155 value of r1 be 0.  The reason for this surprising outcome is that
156 CPU2() never acquired the lock, and thus did not benefit from the
157 lock's ordering properties.
159 Ordering can be extended to CPUs not holding the lock by careful use
160 of smp_mb__after_spinlock():
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         }
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         }
180         void CPU2(void)
181         {
182                 WRITE_ONCE(z, 2);
183                 smp_mb();
184                 r1 = READ_ONCE(x);
185         }
187 This addition of smp_mb__after_spinlock() strengthens the lock acquisition
188 sufficiently to rule out the counter-intuitive outcome.
191 Taking off the training wheels
192 ==============================
194 This section looks at more complex examples, including message passing,
195 load buffering, release-acquire chains, store buffering.
196 Many classes of litmus tests have abbreviated names, which may be found
197 here: https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf
200 Message passing (MP)
201 --------------------
203 The MP pattern has one CPU execute a pair of stores to a pair of variables
204 and another CPU execute a pair of loads from this same pair of variables,
205 but in the opposite order.  The goal is to avoid the counter-intuitive
206 outcome in which the first load sees the value written by the second store
207 but the second load does not see the value written by the first store.
208 In the absence of any ordering, this goal may not be met, as can be seen
209 in the MP+poonceonces.litmus litmus test.  This section therefore looks at
210 a number of ways of meeting this goal.
213 Release and acquire
214 ~~~~~~~~~~~~~~~~~~~
216 Use of smp_store_release() and smp_load_acquire() is one way to force
217 the desired MP ordering.  The general approach is shown below:
219         /* See MP+pooncerelease+poacquireonce.litmus. */
220         void CPU0(void)
221         {
222                 WRITE_ONCE(x, 1);
223                 smp_store_release(&y, 1);
224         }
226         void CPU1(void)
227         {
228                 r0 = smp_load_acquire(&y);
229                 r1 = READ_ONCE(x);
230         }
232 The smp_store_release() macro orders any prior accesses against the
233 store, while the smp_load_acquire macro orders the load against any
234 subsequent accesses.  Therefore, if the final value of r0 is the value 1,
235 the final value of r1 must also be the value 1.
237 The init_stack_slab() function in lib/stackdepot.c uses release-acquire
238 in this way to safely initialize of a slab of the stack.  Working out
239 the mutual-exclusion design is left as an exercise for the reader.
242 Assign and dereference
243 ~~~~~~~~~~~~~~~~~~~~~~
245 Use of rcu_assign_pointer() and rcu_dereference() is quite similar to the
246 use of smp_store_release() and smp_load_acquire(), except that both
247 rcu_assign_pointer() and rcu_dereference() operate on RCU-protected
248 pointers.  The general approach is shown below:
250         /* See MP+onceassign+derefonce.litmus. */
251         int z;
252         int *y = &z;
253         int x;
255         void CPU0(void)
256         {
257                 WRITE_ONCE(x, 1);
258                 rcu_assign_pointer(y, &x);
259         }
261         void CPU1(void)
262         {
263                 rcu_read_lock();
264                 r0 = rcu_dereference(y);
265                 r1 = READ_ONCE(*r0);
266                 rcu_read_unlock();
267         }
269 In this example, if the final value of r0 is &x then the final value of
270 r1 must be 1.
272 The rcu_assign_pointer() macro has the same ordering properties as does
273 smp_store_release(), but the rcu_dereference() macro orders the load only
274 against later accesses that depend on the value loaded.  A dependency
275 is 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
278 first place (control dependency).  Note that the term "data dependency"
279 is sometimes casually used to cover both address and data dependencies.
281 In lib/prime_numbers.c, the expand_to_next_prime() function invokes
282 rcu_assign_pointer(), and the next_prime_number() function invokes
283 rcu_dereference().  This combination mediates access to a bit vector
284 that is expanded as additional primes are needed.
287 Write and read memory barriers
288 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
290 It is usually better to use smp_store_release() instead of smp_wmb()
291 and to use smp_load_acquire() instead of smp_rmb().  However, the older
292 smp_wmb() and smp_rmb() APIs are still heavily used, so it is important
293 to understand their use cases.  The general approach is shown below:
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         }
303         void CPU1(void)
304         {
305                 r0 = READ_ONCE(y);
306                 smp_rmb();
307                 r1 = READ_ONCE(x);
308         }
310 The smp_wmb() macro orders prior stores against later stores, and the
311 smp_rmb() macro orders prior loads against later loads.  Therefore, if
312 the final value of r0 is 1, the final value of r1 must also be 1.
314 The xlog_state_switch_iclogs() function in fs/xfs/xfs_log.c contains
315 the following write-side code fragment:
317         log->l_curr_block -= log->l_logBBsize;
318         ASSERT(log->l_curr_block >= 0);
319         smp_wmb();
320         log->l_curr_cycle++;
322 And the xlog_valid_lsn() function in fs/xfs/xfs_log_priv.h contains
323 the corresponding read-side code fragment:
325         cur_cycle = READ_ONCE(log->l_curr_cycle);
326         smp_rmb();
327         cur_block = READ_ONCE(log->l_curr_block);
329 Alternatively, consider the following comment in function
330 perf_output_put_handle() in kernel/events/ring_buffer.c:
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          *   }
341 The B/C pairing is an example of the MP pattern using smp_wmb() on the
342 write side and smp_rmb() on the read side.
344 Of course, given that smp_mb() is strictly stronger than either smp_wmb()
345 or smp_rmb(), any code fragment that would work with smp_rmb() and
346 smp_wmb() would also work with smp_mb() replacing either or both of the
347 weaker barriers.
350 Load buffering (LB)
351 -------------------
353 The LB pattern has one CPU load from one variable and then store to a
354 second, while another CPU loads from the second variable and then stores
355 to the first.  The goal is to avoid the counter-intuitive situation where
356 each load reads the value written by the other CPU's store.  In the
357 absence of any ordering it is quite possible that this may happen, as
358 can be seen in the LB+poonceonces.litmus litmus test.
360 One way of avoiding the counter-intuitive outcome is through the use of a
361 control dependency paired with a full memory barrier:
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         }
371         void CPU1(void)
372         {
373                 r1 = READ_ONCE(y);
374                 smp_mb();
375                 WRITE_ONCE(x, 1);
376         }
378 This pairing of a control dependency in CPU0() with a full memory
379 barrier in CPU1() prevents r0 and r1 from both ending up equal to 1.
381 The A/D pairing from the ring-buffer use case shown earlier also
382 illustrates LB.  Here is a repeat of the comment in
383 perf_output_put_handle() in kernel/events/ring_buffer.c, showing a
384 control dependency on the kernel side and a full memory barrier on
385 the user side:
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.
398 The kernel's control dependency between the load from ->data_tail
399 and the store to data combined with the user's full memory barrier
400 between the load from data and the store to ->data_tail prevents
401 the counter-intuitive outcome where the kernel overwrites the data
402 before the user gets done loading it.
405 Release-acquire chains
406 ----------------------
408 Release-acquire chains are a low-overhead, flexible, and easy-to-use
409 method of maintaining order.  However, they do have some limitations that
410 need to be fully understood.  Here is an example that maintains order:
412         /* See ISA2+pooncerelease+poacquirerelease+poacquireonce.litmus. */
413         void CPU0(void)
414         {
415                 WRITE_ONCE(x, 1);
416                 smp_store_release(&y, 1);
417         }
419         void CPU1(void)
420         {
421                 r0 = smp_load_acquire(y);
422                 smp_store_release(&z, 1);
423         }
425         void CPU2(void)
426         {
427                 r1 = smp_load_acquire(z);
428                 r2 = READ_ONCE(x);
429         }
431 In this case, if r0 and r1 both have final values of 1, then r2 must
432 also have a final value of 1.
434 The ordering in this example is stronger than it needs to be.  For
435 example, ordering would still be preserved if CPU1()'s smp_load_acquire()
436 invocation was replaced with READ_ONCE().
438 It is tempting to assume that CPU0()'s store to x is globally ordered
439 before CPU1()'s store to z, but this is not the case:
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         }
448         void CPU1(void)
449         {
450                 r0 = smp_load_acquire(y);
451                 smp_store_release(&z, 1);
452         }
454         void CPU2(void)
455         {
456                 WRITE_ONCE(z, 2);
457                 smp_mb();
458                 r1 = READ_ONCE(x);
459         }
461 One might hope that if the final value of r0 is 1 and the final value
462 of z is 2, then the final value of r1 must also be 1, but it really is
463 possible for r1 to have the final value of 0.  The reason, of course,
464 is that in this version, CPU2() is not part of the release-acquire chain.
465 This situation is accounted for in the rules of thumb below.
467 Despite this limitation, release-acquire chains are low-overhead as
468 well as simple and powerful, at least as memory-ordering mechanisms go.
471 Store buffering
472 ---------------
474 Store buffering can be thought of as upside-down load buffering, so
475 that one CPU first stores to one variable and then loads from a second,
476 while another CPU stores to the second variable and then loads from the
477 first.  Preserving order requires nothing less than full barriers:
479         /* See SB+fencembonceonces.litmus. */
480         void CPU0(void)
481         {
482                 WRITE_ONCE(x, 1);
483                 smp_mb();
484                 r0 = READ_ONCE(y);
485         }
487         void CPU1(void)
488         {
489                 WRITE_ONCE(y, 1);
490                 smp_mb();
491                 r1 = READ_ONCE(x);
492         }
494 Omitting either smp_mb() will allow both r0 and r1 to have final
495 values of 0, but providing both full barriers as shown above prevents
496 this counter-intuitive outcome.
498 This pattern most famously appears as part of Dekker's locking
499 algorithm, but it has a much more practical use within the Linux kernel
500 of ordering wakeups.  The following comment taken from waitqueue_active()
501 in include/linux/wait.h shows the canonical pattern:
503  *      CPU0 - waker                    CPU1 - waiter
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);
514 On CPU0, the store is to @cond and the load is in waitqueue_active().
515 On CPU1, prepare_to_wait() contains both a store to wq_head and a call
516 to set_current_state(), which contains an smp_mb() barrier; the load is
517 "if (@cond)".  The full barriers prevent the undesirable outcome where
518 CPU1 puts the waiting task to sleep and CPU0 fails to wake it up.
520 Note that use of locking can greatly simplify this pattern.
523 Rules of thumb
524 ==============
526 There might seem to be no pattern governing what ordering primitives are
527 needed in which situations, but this is not the case.  There is a pattern
528 based on the relation between the accesses linking successive CPUs in a
529 given litmus test.  There are three types of linkage:
531 1.      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".
536 2.      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".
541 3.      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".
549 The strength of memory ordering required for a given litmus test to
550 avoid a counter-intuitive outcome depends on the types of relations
551 linking the memory accesses for the outcome in question:
553 o       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.
558 o       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.
562 o       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.
568 However, if you find yourself having to stretch these rules of thumb
569 to fit your situation, you should consider creating a litmus test and
570 running it on the model.