--- zzzz-none-000/linux-3.10.107/Documentation/memory-barriers.txt 2017-06-27 09:49:32.000000000 +0000 +++ scorpion-7490-727/linux-3.10.107/Documentation/memory-barriers.txt 2021-02-04 17:41:59.000000000 +0000 @@ -115,28 +115,28 @@ CPU 1 CPU 2 =============== =============== { A == 1; B == 2 } - A = 3; x = A; - B = 4; y = B; + A = 3; x = B; + B = 4; y = A; The set of accesses as seen by the memory system in the middle can be arranged in 24 different combinations: - STORE A=3, STORE B=4, x=LOAD A->3, y=LOAD B->4 - STORE A=3, STORE B=4, y=LOAD B->4, x=LOAD A->3 - STORE A=3, x=LOAD A->3, STORE B=4, y=LOAD B->4 - STORE A=3, x=LOAD A->3, y=LOAD B->2, STORE B=4 - STORE A=3, y=LOAD B->2, STORE B=4, x=LOAD A->3 - STORE A=3, y=LOAD B->2, x=LOAD A->3, STORE B=4 - STORE B=4, STORE A=3, x=LOAD A->3, y=LOAD B->4 + STORE A=3, STORE B=4, y=LOAD A->3, x=LOAD B->4 + STORE A=3, STORE B=4, x=LOAD B->4, y=LOAD A->3 + STORE A=3, y=LOAD A->3, STORE B=4, x=LOAD B->4 + STORE A=3, y=LOAD A->3, x=LOAD B->2, STORE B=4 + STORE A=3, x=LOAD B->2, STORE B=4, y=LOAD A->3 + STORE A=3, x=LOAD B->2, y=LOAD A->3, STORE B=4 + STORE B=4, STORE A=3, y=LOAD A->3, x=LOAD B->4 STORE B=4, ... ... and can thus result in four different combinations of values: - x == 1, y == 2 - x == 1, y == 4 - x == 3, y == 2 - x == 3, y == 4 + x == 2, y == 1 + x == 2, y == 3 + x == 4, y == 1 + x == 4, y == 3 Furthermore, the stores committed by a CPU to the memory system may not be @@ -194,18 +194,22 @@ (*) On any given CPU, dependent memory accesses will be issued in order, with respect to itself. This means that for: - Q = P; D = *Q; + WRITE_ONCE(Q, P); smp_read_barrier_depends(); D = READ_ONCE(*Q); the CPU will issue the following memory operations: Q = LOAD P, D = LOAD *Q - and always in that order. + and always in that order. On most systems, smp_read_barrier_depends() + does nothing, but it is required for DEC Alpha. The READ_ONCE() + and WRITE_ONCE() are required to prevent compiler mischief. Please + note that you should normally use something like rcu_dereference() + instead of open-coding smp_read_barrier_depends(). (*) Overlapping loads and stores within a particular CPU will appear to be ordered within that CPU. This means that for: - a = *X; *X = b; + a = READ_ONCE(*X); WRITE_ONCE(*X, b); the CPU will only issue the following sequence of memory operations: @@ -213,7 +217,7 @@ And for: - *X = c; d = *X; + WRITE_ONCE(*X, c); d = READ_ONCE(*X); the CPU will only issue: @@ -224,6 +228,12 @@ And there are a number of things that _must_ or _must_not_ be assumed: + (*) It _must_not_ be assumed that the compiler will do what you want + with memory references that are not protected by READ_ONCE() and + WRITE_ONCE(). Without them, the compiler is within its rights to + do all sorts of "creative" transformations, which are covered in + the Compiler Barrier section. + (*) It _must_not_ be assumed that independent loads and stores will be issued in the order given. This means that for: @@ -259,6 +269,50 @@ STORE *(A + 4) = Y; STORE *A = X; STORE {*A, *(A + 4) } = {X, Y}; +And there are anti-guarantees: + + (*) These guarantees do not apply to bitfields, because compilers often + generate code to modify these using non-atomic read-modify-write + sequences. Do not attempt to use bitfields to synchronize parallel + algorithms. + + (*) Even in cases where bitfields are protected by locks, all fields + in a given bitfield must be protected by one lock. If two fields + in a given bitfield are protected by different locks, the compiler's + non-atomic read-modify-write sequences can cause an update to one + field to corrupt the value of an adjacent field. + + (*) These guarantees apply only to properly aligned and sized scalar + variables. "Properly sized" currently means variables that are + the same size as "char", "short", "int" and "long". "Properly + aligned" means the natural alignment, thus no constraints for + "char", two-byte alignment for "short", four-byte alignment for + "int", and either four-byte or eight-byte alignment for "long", + on 32-bit and 64-bit systems, respectively. Note that these + guarantees were introduced into the C11 standard, so beware when + using older pre-C11 compilers (for example, gcc 4.6). The portion + of the standard containing this guarantee is Section 3.14, which + defines "memory location" as follows: + + memory location + either an object of scalar type, or a maximal sequence + of adjacent bit-fields all having nonzero width + + NOTE 1: Two threads of execution can update and access + separate memory locations without interfering with + each other. + + NOTE 2: A bit-field and an adjacent non-bit-field member + are in separate memory locations. The same applies + to two bit-fields, if one is declared inside a nested + structure declaration and the other is not, or if the two + are separated by a zero-length bit-field declaration, + or if they are separated by a non-bit-field member + declaration. It is not safe to concurrently update two + bit-fields in the same structure if all members declared + between them are also bit-fields, no matter what the + sizes of those intervening bit-fields happen to be. + ========================= WHAT ARE MEMORY BARRIERS? @@ -371,33 +425,44 @@ And a couple of implicit varieties: - (5) LOCK operations. + (5) ACQUIRE operations. This acts as a one-way permeable barrier. It guarantees that all memory - operations after the LOCK operation will appear to happen after the LOCK - operation with respect to the other components of the system. + operations after the ACQUIRE operation will appear to happen after the + ACQUIRE operation with respect to the other components of the system. + ACQUIRE operations include LOCK operations and smp_load_acquire() + operations. - Memory operations that occur before a LOCK operation may appear to happen - after it completes. + Memory operations that occur before an ACQUIRE operation may appear to + happen after it completes. - A LOCK operation should almost always be paired with an UNLOCK operation. + An ACQUIRE operation should almost always be paired with a RELEASE + operation. - (6) UNLOCK operations. + (6) RELEASE operations. This also acts as a one-way permeable barrier. It guarantees that all - memory operations before the UNLOCK operation will appear to happen before - the UNLOCK operation with respect to the other components of the system. + memory operations before the RELEASE operation will appear to happen + before the RELEASE operation with respect to the other components of the + system. RELEASE operations include UNLOCK operations and + smp_store_release() operations. - Memory operations that occur after an UNLOCK operation may appear to + Memory operations that occur after a RELEASE operation may appear to happen before it completes. - LOCK and UNLOCK operations are guaranteed to appear with respect to each - other strictly in the order specified. + The use of ACQUIRE and RELEASE operations generally precludes the need + for other sorts of memory barrier (but note the exceptions mentioned in + the subsection "MMIO write barrier"). In addition, a RELEASE+ACQUIRE + pair is -not- guaranteed to act as a full memory barrier. However, after + an ACQUIRE on a given variable, all memory accesses preceding any prior + RELEASE on that same variable are guaranteed to be visible. In other + words, within a given variable's critical section, all accesses of all + previous critical sections for that variable are guaranteed to have + completed. - The use of LOCK and UNLOCK operations generally precludes the need for - other sorts of memory barrier (but note the exceptions mentioned in the - subsection "MMIO write barrier"). + This means that ACQUIRE acts as a minimal "acquire" operation and + RELEASE acts as a minimal "release" operation. Memory barriers are only required where there's a possibility of interaction @@ -450,14 +515,14 @@ it's not always obvious that they're needed. To illustrate, consider the following sequence of events: - CPU 1 CPU 2 - =============== =============== + CPU 1 CPU 2 + =============== =============== { A == 1, B == 2, C = 3, P == &A, Q == &C } B = 4; - P = &B - Q = P; - D = *Q; + WRITE_ONCE(P, &B) + Q = READ_ONCE(P); + D = *Q; There's a clear data dependency here, and it would seem that by the end of the sequence, Q must be either &A or &B, and that: @@ -477,15 +542,15 @@ To deal with this, a data dependency barrier or better must be inserted between the address load and the data load: - CPU 1 CPU 2 - =============== =============== + CPU 1 CPU 2 + =============== =============== { A == 1, B == 2, C = 3, P == &A, Q == &C } B = 4; - P = &B - Q = P; - - D = *Q; + WRITE_ONCE(P, &B); + Q = READ_ONCE(P); + + D = *Q; This enforces the occurrence of one of the two implications, and prevents the third possibility from arising. @@ -500,25 +565,26 @@ but the old value of the variable B (2). -Another example of where data dependency barriers might by required is where a +Another example of where data dependency barriers might be required is where a number is read from memory and then used to calculate the index for an array access: - CPU 1 CPU 2 - =============== =============== + CPU 1 CPU 2 + =============== =============== { M[0] == 1, M[1] == 2, M[3] = 3, P == 0, Q == 3 } M[1] = 4; - P = 1 - Q = P; - - D = M[Q]; + WRITE_ONCE(P, 1); + Q = READ_ONCE(P); + + D = M[Q]; -The data dependency barrier is very important to the RCU system, for example. -See rcu_dereference() in include/linux/rcupdate.h. This permits the current -target of an RCU'd pointer to be replaced with a new modified target, without -the replacement target appearing to be incompletely initialised. +The data dependency barrier is very important to the RCU system, +for example. See rcu_assign_pointer() and rcu_dereference() in +include/linux/rcupdate.h. This permits the current target of an RCU'd +pointer to be replaced with a new modified target, without the replacement +target appearing to be incompletely initialised. See also the subsection on "Cache Coherency" for a more thorough example. @@ -526,26 +592,234 @@ CONTROL DEPENDENCIES -------------------- -A control dependency requires a full read memory barrier, not simply a data -dependency barrier to make it work correctly. Consider the following bit of -code: - - q = &a; - if (p) - q = &b; - - x = *q; +A load-load control dependency requires a full read memory barrier, not +simply a data dependency barrier to make it work correctly. Consider the +following bit of code: + + q = READ_ONCE(a); + if (q) { + /* BUG: No data dependency!!! */ + p = READ_ONCE(b); + } This will not have the desired effect because there is no actual data -dependency, but rather a control dependency that the CPU may short-circuit by -attempting to predict the outcome in advance. In such a case what's actually -required is: - - q = &a; - if (p) - q = &b; - - x = *q; +dependency, but rather a control dependency that the CPU may short-circuit +by attempting to predict the outcome in advance, so that other CPUs see +the load from b as having happened before the load from a. In such a +case what's actually required is: + + q = READ_ONCE(a); + if (q) { + + p = READ_ONCE(b); + } + +However, stores are not speculated. This means that ordering -is- provided +for load-store control dependencies, as in the following example: + + q = READ_ONCE(a); + if (q) { + WRITE_ONCE(b, p); + } + +Control dependencies pair normally with other types of barriers. That +said, please note that READ_ONCE() is not optional! Without the +READ_ONCE(), the compiler might combine the load from 'a' with other +loads from 'a', and the store to 'b' with other stores to 'b', with +possible highly counterintuitive effects on ordering. + +Worse yet, if the compiler is able to prove (say) that the value of +variable 'a' is always non-zero, it would be well within its rights +to optimize the original example by eliminating the "if" statement +as follows: + + q = a; + b = p; /* BUG: Compiler and CPU can both reorder!!! */ + +So don't leave out the READ_ONCE(). + +It is tempting to try to enforce ordering on identical stores on both +branches of the "if" statement as follows: + + q = READ_ONCE(a); + if (q) { + barrier(); + WRITE_ONCE(b, p); + do_something(); + } else { + barrier(); + WRITE_ONCE(b, p); + do_something_else(); + } + +Unfortunately, current compilers will transform this as follows at high +optimization levels: + + q = READ_ONCE(a); + barrier(); + WRITE_ONCE(b, p); /* BUG: No ordering vs. load from a!!! */ + if (q) { + /* WRITE_ONCE(b, p); -- moved up, BUG!!! */ + do_something(); + } else { + /* WRITE_ONCE(b, p); -- moved up, BUG!!! */ + do_something_else(); + } + +Now there is no conditional between the load from 'a' and the store to +'b', which means that the CPU is within its rights to reorder them: +The conditional is absolutely required, and must be present in the +assembly code even after all compiler optimizations have been applied. +Therefore, if you need ordering in this example, you need explicit +memory barriers, for example, smp_store_release(): + + q = READ_ONCE(a); + if (q) { + smp_store_release(&b, p); + do_something(); + } else { + smp_store_release(&b, p); + do_something_else(); + } + +In contrast, without explicit memory barriers, two-legged-if control +ordering is guaranteed only when the stores differ, for example: + + q = READ_ONCE(a); + if (q) { + WRITE_ONCE(b, p); + do_something(); + } else { + WRITE_ONCE(b, r); + do_something_else(); + } + +The initial READ_ONCE() is still required to prevent the compiler from +proving the value of 'a'. + +In addition, you need to be careful what you do with the local variable 'q', +otherwise the compiler might be able to guess the value and again remove +the needed conditional. For example: + + q = READ_ONCE(a); + if (q % MAX) { + WRITE_ONCE(b, p); + do_something(); + } else { + WRITE_ONCE(b, r); + do_something_else(); + } + +If MAX is defined to be 1, then the compiler knows that (q % MAX) is +equal to zero, in which case the compiler is within its rights to +transform the above code into the following: + + q = READ_ONCE(a); + WRITE_ONCE(b, p); + do_something_else(); + +Given this transformation, the CPU is not required to respect the ordering +between the load from variable 'a' and the store to variable 'b'. It is +tempting to add a barrier(), but this does not help. The conditional +is gone, and the barrier won't bring it back. Therefore, if you are +relying on this ordering, you should make sure that MAX is greater than +one, perhaps as follows: + + q = READ_ONCE(a); + BUILD_BUG_ON(MAX <= 1); /* Order load from a with store to b. */ + if (q % MAX) { + WRITE_ONCE(b, p); + do_something(); + } else { + WRITE_ONCE(b, r); + do_something_else(); + } + +Please note once again that the stores to 'b' differ. If they were +identical, as noted earlier, the compiler could pull this store outside +of the 'if' statement. + +You must also be careful not to rely too much on boolean short-circuit +evaluation. Consider this example: + + q = READ_ONCE(a); + if (q || 1 > 0) + WRITE_ONCE(b, 1); + +Because the first condition cannot fault and the second condition is +always true, the compiler can transform this example as following, +defeating control dependency: + + q = READ_ONCE(a); + WRITE_ONCE(b, 1); + +This example underscores the need to ensure that the compiler cannot +out-guess your code. More generally, although READ_ONCE() does force +the compiler to actually emit code for a given load, it does not force +the compiler to use the results. + +Finally, control dependencies do -not- provide transitivity. This is +demonstrated by two related examples, with the initial values of +x and y both being zero: + + CPU 0 CPU 1 + ======================= ======================= + r1 = READ_ONCE(x); r2 = READ_ONCE(y); + if (r1 > 0) if (r2 > 0) + WRITE_ONCE(y, 1); WRITE_ONCE(x, 1); + + assert(!(r1 == 1 && r2 == 1)); + +The above two-CPU example will never trigger the assert(). However, +if control dependencies guaranteed transitivity (which they do not), +then adding the following CPU would guarantee a related assertion: + + CPU 2 + ===================== + WRITE_ONCE(x, 2); + + assert(!(r1 == 2 && r2 == 1 && x == 2)); /* FAILS!!! */ + +But because control dependencies do -not- provide transitivity, the above +assertion can fail after the combined three-CPU example completes. If you +need the three-CPU example to provide ordering, you will need smp_mb() +between the loads and stores in the CPU 0 and CPU 1 code fragments, +that is, just before or just after the "if" statements. Furthermore, +the original two-CPU example is very fragile and should be avoided. + +These two examples are the LB and WWC litmus tests from this paper: +http://www.cl.cam.ac.uk/users/pes20/ppc-supplemental/test6.pdf and this +site: https://www.cl.cam.ac.uk/~pes20/ppcmem/index.html. + +In summary: + + (*) Control dependencies can order prior loads against later stores. + However, they do -not- guarantee any other sort of ordering: + Not prior loads against later loads, nor prior stores against + later anything. If you need these other forms of ordering, + use smp_rmb(), smp_wmb(), or, in the case of prior stores and + later loads, smp_mb(). + + (*) If both legs of the "if" statement begin with identical stores + to the same variable, a barrier() statement is required at the + beginning of each leg of the "if" statement. + + (*) Control dependencies require at least one run-time conditional + between the prior load and the subsequent store, and this + conditional must involve the prior load. If the compiler is able + to optimize the conditional away, it will have also optimized + away the ordering. Careful use of READ_ONCE() and WRITE_ONCE() + can help to preserve the needed conditional. + + (*) Control dependencies require that the compiler avoid reordering the + dependency into nonexistence. Careful use of READ_ONCE() or + atomic{,64}_read() can help to preserve your control dependency. + Please see the Compiler Barrier section for more information. + + (*) Control dependencies pair normally with other types of barriers. + + (*) Control dependencies do -not- provide transitivity. If you + need transitivity, use smp_mb(). SMP BARRIER PAIRING @@ -554,28 +828,45 @@ When dealing with CPU-CPU interactions, certain types of memory barrier should always be paired. A lack of appropriate pairing is almost certainly an error. -A write barrier should always be paired with a data dependency barrier or read -barrier, though a general barrier would also be viable. Similarly a read -barrier or a data dependency barrier should always be paired with at least an -write barrier, though, again, a general barrier is viable: - - CPU 1 CPU 2 - =============== =============== - a = 1; +General barriers pair with each other, though they also pair with most +other types of barriers, albeit without transitivity. An acquire barrier +pairs with a release barrier, but both may also pair with other barriers, +including of course general barriers. A write barrier pairs with a data +dependency barrier, a control dependency, an acquire barrier, a release +barrier, a read barrier, or a general barrier. Similarly a read barrier, +control dependency, or a data dependency barrier pairs with a write +barrier, an acquire barrier, a release barrier, or a general barrier: + + CPU 1 CPU 2 + =============== =============== + WRITE_ONCE(a, 1); - b = 2; x = b; - - y = a; + WRITE_ONCE(b, 2); x = READ_ONCE(b); + + y = READ_ONCE(a); Or: - CPU 1 CPU 2 - =============== =============================== + CPU 1 CPU 2 + =============== =============================== a = 1; - b = &a; x = b; - - y = *x; + WRITE_ONCE(b, &a); x = READ_ONCE(b); + + y = *x; + +Or even: + + CPU 1 CPU 2 + =============== =============================== + r1 = READ_ONCE(y); + + WRITE_ONCE(y, 1); if (r2 = READ_ONCE(x)) { + + WRITE_ONCE(y, 1); + } + + assert(r1 == 0 || r2 == 0); Basically, the read barrier always has to be there, even though it can be of the "weaker" type. @@ -584,13 +875,13 @@ match the loads after the read barrier or the data dependency barrier, and vice versa: - CPU 1 CPU 2 - =============== =============== - a = 1; }---- --->{ v = c - b = 2; } \ / { w = d - \ - c = 3; } / \ { x = a; - d = 4; }---- --->{ y = b; + CPU 1 CPU 2 + =================== =================== + WRITE_ONCE(a, 1); }---- --->{ v = READ_ONCE(c); + WRITE_ONCE(b, 2); } \ / { w = READ_ONCE(d); + \ + WRITE_ONCE(c, 3); } / \ { x = READ_ONCE(a); + WRITE_ONCE(d, 4); }---- --->{ y = READ_ONCE(b); EXAMPLES OF MEMORY BARRIER SEQUENCES @@ -880,12 +1171,12 @@ Consider: - CPU 1 CPU 2 + CPU 1 CPU 2 ======================= ======================= - LOAD B - DIVIDE } Divide instructions generally - DIVIDE } take a long time to perform - LOAD A + LOAD B + DIVIDE } Divide instructions generally + DIVIDE } take a long time to perform + LOAD A Which might appear as this: @@ -908,13 +1199,13 @@ Placing a read barrier or a data dependency barrier just before the second load: - CPU 1 CPU 2 + CPU 1 CPU 2 ======================= ======================= - LOAD B - DIVIDE - DIVIDE + LOAD B + DIVIDE + DIVIDE - LOAD A + LOAD A will force any value speculatively obtained to be reconsidered to an extent dependent on the type of barrier used. If there was no change made to the @@ -1040,10 +1331,299 @@ barrier(); -This is a general barrier - lesser varieties of compiler barrier do not exist. +This is a general barrier -- there are no read-read or write-write +variants of barrier(). However, READ_ONCE() and WRITE_ONCE() can be +thought of as weak forms of barrier() that affect only the specific +accesses flagged by the READ_ONCE() or WRITE_ONCE(). + +The barrier() function has the following effects: + + (*) Prevents the compiler from reordering accesses following the + barrier() to precede any accesses preceding the barrier(). + One example use for this property is to ease communication between + interrupt-handler code and the code that was interrupted. + + (*) Within a loop, forces the compiler to load the variables used + in that loop's conditional on each pass through that loop. + +The READ_ONCE() and WRITE_ONCE() functions can prevent any number of +optimizations that, while perfectly safe in single-threaded code, can +be fatal in concurrent code. Here are some examples of these sorts +of optimizations: + + (*) The compiler is within its rights to reorder loads and stores + to the same variable, and in some cases, the CPU is within its + rights to reorder loads to the same variable. This means that + the following code: + + a[0] = x; + a[1] = x; + + Might result in an older value of x stored in a[1] than in a[0]. + Prevent both the compiler and the CPU from doing this as follows: + + a[0] = READ_ONCE(x); + a[1] = READ_ONCE(x); + + In short, READ_ONCE() and WRITE_ONCE() provide cache coherence for + accesses from multiple CPUs to a single variable. + + (*) The compiler is within its rights to merge successive loads from + the same variable. Such merging can cause the compiler to "optimize" + the following code: + + while (tmp = a) + do_something_with(tmp); + + into the following code, which, although in some sense legitimate + for single-threaded code, is almost certainly not what the developer + intended: + + if (tmp = a) + for (;;) + do_something_with(tmp); + + Use READ_ONCE() to prevent the compiler from doing this to you: + + while (tmp = READ_ONCE(a)) + do_something_with(tmp); + + (*) The compiler is within its rights to reload a variable, for example, + in cases where high register pressure prevents the compiler from + keeping all data of interest in registers. The compiler might + therefore optimize the variable 'tmp' out of our previous example: + + while (tmp = a) + do_something_with(tmp); + + This could result in the following code, which is perfectly safe in + single-threaded code, but can be fatal in concurrent code: + + while (a) + do_something_with(a); + + For example, the optimized version of this code could result in + passing a zero to do_something_with() in the case where the variable + a was modified by some other CPU between the "while" statement and + the call to do_something_with(). + + Again, use READ_ONCE() to prevent the compiler from doing this: + + while (tmp = READ_ONCE(a)) + do_something_with(tmp); + + Note that if the compiler runs short of registers, it might save + tmp onto the stack. The overhead of this saving and later restoring + is why compilers reload variables. Doing so is perfectly safe for + single-threaded code, so you need to tell the compiler about cases + where it is not safe. + + (*) The compiler is within its rights to omit a load entirely if it knows + what the value will be. For example, if the compiler can prove that + the value of variable 'a' is always zero, it can optimize this code: + + while (tmp = a) + do_something_with(tmp); + + Into this: + + do { } while (0); + + This transformation is a win for single-threaded code because it + gets rid of a load and a branch. The problem is that the compiler + will carry out its proof assuming that the current CPU is the only + one updating variable 'a'. If variable 'a' is shared, then the + compiler's proof will be erroneous. Use READ_ONCE() to tell the + compiler that it doesn't know as much as it thinks it does: + + while (tmp = READ_ONCE(a)) + do_something_with(tmp); + + But please note that the compiler is also closely watching what you + do with the value after the READ_ONCE(). For example, suppose you + do the following and MAX is a preprocessor macro with the value 1: + + while ((tmp = READ_ONCE(a)) % MAX) + do_something_with(tmp); + + Then the compiler knows that the result of the "%" operator applied + to MAX will always be zero, again allowing the compiler to optimize + the code into near-nonexistence. (It will still load from the + variable 'a'.) -The compiler barrier has no direct effect on the CPU, which may then reorder -things however it wishes. + (*) Similarly, the compiler is within its rights to omit a store entirely + if it knows that the variable already has the value being stored. + Again, the compiler assumes that the current CPU is the only one + storing into the variable, which can cause the compiler to do the + wrong thing for shared variables. For example, suppose you have + the following: + + a = 0; + /* Code that does not store to variable a. */ + a = 0; + + The compiler sees that the value of variable 'a' is already zero, so + it might well omit the second store. This would come as a fatal + surprise if some other CPU might have stored to variable 'a' in the + meantime. + + Use WRITE_ONCE() to prevent the compiler from making this sort of + wrong guess: + + WRITE_ONCE(a, 0); + /* Code that does not store to variable a. */ + WRITE_ONCE(a, 0); + + (*) The compiler is within its rights to reorder memory accesses unless + you tell it not to. For example, consider the following interaction + between process-level code and an interrupt handler: + + void process_level(void) + { + msg = get_message(); + flag = true; + } + + void interrupt_handler(void) + { + if (flag) + process_message(msg); + } + + There is nothing to prevent the compiler from transforming + process_level() to the following, in fact, this might well be a + win for single-threaded code: + + void process_level(void) + { + flag = true; + msg = get_message(); + } + + If the interrupt occurs between these two statement, then + interrupt_handler() might be passed a garbled msg. Use WRITE_ONCE() + to prevent this as follows: + + void process_level(void) + { + WRITE_ONCE(msg, get_message()); + WRITE_ONCE(flag, true); + } + + void interrupt_handler(void) + { + if (READ_ONCE(flag)) + process_message(READ_ONCE(msg)); + } + + Note that the READ_ONCE() and WRITE_ONCE() wrappers in + interrupt_handler() are needed if this interrupt handler can itself + be interrupted by something that also accesses 'flag' and 'msg', + for example, a nested interrupt or an NMI. Otherwise, READ_ONCE() + and WRITE_ONCE() are not needed in interrupt_handler() other than + for documentation purposes. (Note also that nested interrupts + do not typically occur in modern Linux kernels, in fact, if an + interrupt handler returns with interrupts enabled, you will get a + WARN_ONCE() splat.) + + You should assume that the compiler can move READ_ONCE() and + WRITE_ONCE() past code not containing READ_ONCE(), WRITE_ONCE(), + barrier(), or similar primitives. + + This effect could also be achieved using barrier(), but READ_ONCE() + and WRITE_ONCE() are more selective: With READ_ONCE() and + WRITE_ONCE(), the compiler need only forget the contents of the + indicated memory locations, while with barrier() the compiler must + discard the value of all memory locations that it has currented + cached in any machine registers. Of course, the compiler must also + respect the order in which the READ_ONCE()s and WRITE_ONCE()s occur, + though the CPU of course need not do so. + + (*) The compiler is within its rights to invent stores to a variable, + as in the following example: + + if (a) + b = a; + else + b = 42; + + The compiler might save a branch by optimizing this as follows: + + b = 42; + if (a) + b = a; + + In single-threaded code, this is not only safe, but also saves + a branch. Unfortunately, in concurrent code, this optimization + could cause some other CPU to see a spurious value of 42 -- even + if variable 'a' was never zero -- when loading variable 'b'. + Use WRITE_ONCE() to prevent this as follows: + + if (a) + WRITE_ONCE(b, a); + else + WRITE_ONCE(b, 42); + + The compiler can also invent loads. These are usually less + damaging, but they can result in cache-line bouncing and thus in + poor performance and scalability. Use READ_ONCE() to prevent + invented loads. + + (*) For aligned memory locations whose size allows them to be accessed + with a single memory-reference instruction, prevents "load tearing" + and "store tearing," in which a single large access is replaced by + multiple smaller accesses. For example, given an architecture having + 16-bit store instructions with 7-bit immediate fields, the compiler + might be tempted to use two 16-bit store-immediate instructions to + implement the following 32-bit store: + + p = 0x00010002; + + Please note that GCC really does use this sort of optimization, + which is not surprising given that it would likely take more + than two instructions to build the constant and then store it. + This optimization can therefore be a win in single-threaded code. + In fact, a recent bug (since fixed) caused GCC to incorrectly use + this optimization in a volatile store. In the absence of such bugs, + use of WRITE_ONCE() prevents store tearing in the following example: + + WRITE_ONCE(p, 0x00010002); + + Use of packed structures can also result in load and store tearing, + as in this example: + + struct __attribute__((__packed__)) foo { + short a; + int b; + short c; + }; + struct foo foo1, foo2; + ... + + foo2.a = foo1.a; + foo2.b = foo1.b; + foo2.c = foo1.c; + + Because there are no READ_ONCE() or WRITE_ONCE() wrappers and no + volatile markings, the compiler would be well within its rights to + implement these three assignment statements as a pair of 32-bit + loads followed by a pair of 32-bit stores. This would result in + load tearing on 'foo1.b' and store tearing on 'foo2.b'. READ_ONCE() + and WRITE_ONCE() again prevent tearing in this example: + + foo2.a = foo1.a; + WRITE_ONCE(foo2.b, READ_ONCE(foo1.b)); + foo2.c = foo1.c; + +All that aside, it is never necessary to use READ_ONCE() and +WRITE_ONCE() on a variable that has been marked volatile. For example, +because 'jiffies' is marked volatile, it is never necessary to +say READ_ONCE(jiffies). The reason for this is that READ_ONCE() and +WRITE_ONCE() are implemented as volatile casts, which has no effect when +its argument is already marked volatile. + +Please note that these compiler barriers have no direct effect on the CPU, +which may then reorder things however it wishes. CPU MEMORY BARRIERS @@ -1062,14 +1642,15 @@ All memory barriers except the data dependency barriers imply a compiler barrier. Data dependencies do not impose any additional compiler ordering. -Aside: In the case of data dependencies, the compiler would be expected to -issue the loads in the correct order (eg. `a[b]` would have to load the value -of b before loading a[b]), however there is no guarantee in the C specification -that the compiler may not speculate the value of b (eg. is equal to 1) and load -a before b (eg. tmp = a[1]; if (b != 1) tmp = a[b]; ). There is also the -problem of a compiler reloading b after having loaded a[b], thus having a newer -copy of b than a[b]. A consensus has not yet been reached about these problems, -however the ACCESS_ONCE macro is a good place to start looking. +Aside: In the case of data dependencies, the compiler would be expected +to issue the loads in the correct order (eg. `a[b]` would have to load +the value of b before loading a[b]), however there is no guarantee in +the C specification that the compiler may not speculate the value of b +(eg. is equal to 1) and load a before b (eg. tmp = a[1]; if (b != 1) +tmp = a[b]; ). There is also the problem of a compiler reloading b after +having loaded a[b], thus having a newer copy of b than a[b]. A consensus +has not yet been reached about these problems, however the READ_ONCE() +macro is a good place to start looking. SMP memory barriers are reduced to compiler barriers on uniprocessor compiled systems because it is assumed that a CPU will appear to be self-consistent, @@ -1089,27 +1670,28 @@ There are some more advanced barrier functions: - (*) set_mb(var, value) + (*) smp_store_mb(var, value) This assigns the value to the variable and then inserts a full memory barrier after it, depending on the function. It isn't guaranteed to insert anything more than a compiler barrier in a UP compilation. - (*) smp_mb__before_atomic_dec(); - (*) smp_mb__after_atomic_dec(); - (*) smp_mb__before_atomic_inc(); - (*) smp_mb__after_atomic_inc(); - - These are for use with atomic add, subtract, increment and decrement - functions that don't return a value, especially when used for reference - counting. These functions do not imply memory barriers. + (*) smp_mb__before_atomic(); + (*) smp_mb__after_atomic(); + + These are for use with atomic (such as add, subtract, increment and + decrement) functions that don't return a value, especially when used for + reference counting. These functions do not imply memory barriers. + + These are also used for atomic bitop functions that do not return a + value (such as set_bit and clear_bit). As an example, consider a piece of code that marks an object as being dead and then decrements the object's reference count: obj->dead = 1; - smp_mb__before_atomic_dec(); + smp_mb__before_atomic(); atomic_dec(&obj->ref_count); This makes sure that the death mark on the object is perceived to be set @@ -1119,26 +1701,58 @@ operations" subsection for information on where to use these. - (*) smp_mb__before_clear_bit(void); - (*) smp_mb__after_clear_bit(void); + (*) lockless_dereference(); + This can be thought of as a pointer-fetch wrapper around the + smp_read_barrier_depends() data-dependency barrier. - These are for use similar to the atomic inc/dec barriers. These are - typically used for bitwise unlocking operations, so care must be taken as - there are no implicit memory barriers here either. - - Consider implementing an unlock operation of some nature by clearing a - locking bit. The clear_bit() would then need to be barriered like this: - - smp_mb__before_clear_bit(); - clear_bit( ... ); - - This prevents memory operations before the clear leaking to after it. See - the subsection on "Locking Functions" with reference to UNLOCK operation - implications. + This is also similar to rcu_dereference(), but in cases where + object lifetime is handled by some mechanism other than RCU, for + example, when the objects removed only when the system goes down. + In addition, lockless_dereference() is used in some data structures + that can be used both with and without RCU. - See Documentation/atomic_ops.txt for more information. See the "Atomic - operations" subsection for information on where to use these. + (*) dma_wmb(); + (*) dma_rmb(); + + These are for use with consistent memory to guarantee the ordering + of writes or reads of shared memory accessible to both the CPU and a + DMA capable device. + + For example, consider a device driver that shares memory with a device + and uses a descriptor status value to indicate if the descriptor belongs + to the device or the CPU, and a doorbell to notify it when new + descriptors are available: + + if (desc->status != DEVICE_OWN) { + /* do not read data until we own descriptor */ + dma_rmb(); + + /* read/modify data */ + read_data = desc->data; + desc->data = write_data; + + /* flush modifications before status update */ + dma_wmb(); + + /* assign ownership */ + desc->status = DEVICE_OWN; + + /* force memory to sync before notifying device via MMIO */ + wmb(); + + /* notify device of new descriptors */ + writel(DESC_NOTIFY, doorbell); + } + + The dma_rmb() allows us guarantee the device has released ownership + before we read the data from the descriptor, and the dma_wmb() allows + us to guarantee the data is written to the descriptor before the device + can see it now has ownership. The wmb() is needed to guarantee that the + cache coherent memory writes have completed before attempting a write to + the cache incoherent MMIO region. + + See Documentation/DMA-API.txt for more information on consistent memory. MMIO WRITE BARRIER ------------------ @@ -1167,8 +1781,8 @@ of arch specific code. -LOCKING FUNCTIONS ------------------ +ACQUIRING FUNCTIONS +------------------- The Linux kernel has a number of locking constructs: @@ -1177,67 +1791,110 @@ (*) mutexes (*) semaphores (*) R/W semaphores - (*) RCU -In all cases there are variants on "LOCK" operations and "UNLOCK" operations +In all cases there are variants on "ACQUIRE" operations and "RELEASE" operations for each construct. These operations all imply certain barriers: - (1) LOCK operation implication: + (1) ACQUIRE operation implication: - Memory operations issued after the LOCK will be completed after the LOCK - operation has completed. + Memory operations issued after the ACQUIRE will be completed after the + ACQUIRE operation has completed. - Memory operations issued before the LOCK may be completed after the LOCK - operation has completed. + Memory operations issued before the ACQUIRE may be completed after + the ACQUIRE operation has completed. An smp_mb__before_spinlock(), + combined with a following ACQUIRE, orders prior stores against + subsequent loads and stores. Note that this is weaker than smp_mb()! + The smp_mb__before_spinlock() primitive is free on many architectures. - (2) UNLOCK operation implication: + (2) RELEASE operation implication: - Memory operations issued before the UNLOCK will be completed before the - UNLOCK operation has completed. + Memory operations issued before the RELEASE will be completed before the + RELEASE operation has completed. - Memory operations issued after the UNLOCK may be completed before the - UNLOCK operation has completed. + Memory operations issued after the RELEASE may be completed before the + RELEASE operation has completed. - (3) LOCK vs LOCK implication: + (3) ACQUIRE vs ACQUIRE implication: - All LOCK operations issued before another LOCK operation will be completed - before that LOCK operation. + All ACQUIRE operations issued before another ACQUIRE operation will be + completed before that ACQUIRE operation. - (4) LOCK vs UNLOCK implication: + (4) ACQUIRE vs RELEASE implication: - All LOCK operations issued before an UNLOCK operation will be completed - before the UNLOCK operation. + All ACQUIRE operations issued before a RELEASE operation will be + completed before the RELEASE operation. - All UNLOCK operations issued before a LOCK operation will be completed - before the LOCK operation. + (5) Failed conditional ACQUIRE implication: - (5) Failed conditional LOCK implication: - - Certain variants of the LOCK operation may fail, either due to being - unable to get the lock immediately, or due to receiving an unblocked + Certain locking variants of the ACQUIRE operation may fail, either due to + being unable to get the lock immediately, or due to receiving an unblocked signal whilst asleep waiting for the lock to become available. Failed locks do not imply any sort of barrier. -Therefore, from (1), (2) and (4) an UNLOCK followed by an unconditional LOCK is -equivalent to a full barrier, but a LOCK followed by an UNLOCK is not. - -[!] Note: one of the consequences of LOCKs and UNLOCKs being only one-way - barriers is that the effects of instructions outside of a critical section - may seep into the inside of the critical section. - -A LOCK followed by an UNLOCK may not be assumed to be full memory barrier -because it is possible for an access preceding the LOCK to happen after the -LOCK, and an access following the UNLOCK to happen before the UNLOCK, and the -two accesses can themselves then cross: +[!] Note: one of the consequences of lock ACQUIREs and RELEASEs being only +one-way barriers is that the effects of instructions outside of a critical +section may seep into the inside of the critical section. + +An ACQUIRE followed by a RELEASE may not be assumed to be full memory barrier +because it is possible for an access preceding the ACQUIRE to happen after the +ACQUIRE, and an access following the RELEASE to happen before the RELEASE, and +the two accesses can themselves then cross: *A = a; - LOCK - UNLOCK + ACQUIRE M + RELEASE M *B = b; may occur as: - LOCK, STORE *B, STORE *A, UNLOCK + ACQUIRE M, STORE *B, STORE *A, RELEASE M + +When the ACQUIRE and RELEASE are a lock acquisition and release, +respectively, this same reordering can occur if the lock's ACQUIRE and +RELEASE are to the same lock variable, but only from the perspective of +another CPU not holding that lock. In short, a ACQUIRE followed by an +RELEASE may -not- be assumed to be a full memory barrier. + +Similarly, the reverse case of a RELEASE followed by an ACQUIRE does +not imply a full memory barrier. Therefore, the CPU's execution of the +critical sections corresponding to the RELEASE and the ACQUIRE can cross, +so that: + + *A = a; + RELEASE M + ACQUIRE N + *B = b; + +could occur as: + + ACQUIRE N, STORE *B, STORE *A, RELEASE M + +It might appear that this reordering could introduce a deadlock. +However, this cannot happen because if such a deadlock threatened, +the RELEASE would simply complete, thereby avoiding the deadlock. + + Why does this work? + + One key point is that we are only talking about the CPU doing + the reordering, not the compiler. If the compiler (or, for + that matter, the developer) switched the operations, deadlock + -could- occur. + + But suppose the CPU reordered the operations. In this case, + the unlock precedes the lock in the assembly code. The CPU + simply elected to try executing the later lock operation first. + If there is a deadlock, this lock operation will simply spin (or + try to sleep, but more on that later). The CPU will eventually + execute the unlock operation (which preceded the lock operation + in the assembly code), which will unravel the potential deadlock, + allowing the lock operation to succeed. + + But what if the lock is a sleeplock? In that case, the code will + try to enter the scheduler, where it will eventually encounter + a memory barrier, which will force the earlier unlock operation + to complete, again unraveling the deadlock. There might be + a sleep-unlock race, but the locking primitive needs to resolve + such races properly in any case. Locks and semaphores may not provide any guarantee of ordering on UP compiled systems, and so cannot be counted on in such a situation to actually achieve @@ -1251,33 +1908,33 @@ *A = a; *B = b; - LOCK + ACQUIRE *C = c; *D = d; - UNLOCK + RELEASE *E = e; *F = f; The following sequence of events is acceptable: - LOCK, {*F,*A}, *E, {*C,*D}, *B, UNLOCK + ACQUIRE, {*F,*A}, *E, {*C,*D}, *B, RELEASE [+] Note that {*F,*A} indicates a combined access. But none of the following are: - {*F,*A}, *B, LOCK, *C, *D, UNLOCK, *E - *A, *B, *C, LOCK, *D, UNLOCK, *E, *F - *A, *B, LOCK, *C, UNLOCK, *D, *E, *F - *B, LOCK, *C, *D, UNLOCK, {*F,*A}, *E + {*F,*A}, *B, ACQUIRE, *C, *D, RELEASE, *E + *A, *B, *C, ACQUIRE, *D, RELEASE, *E, *F + *A, *B, ACQUIRE, *C, RELEASE, *D, *E, *F + *B, ACQUIRE, *C, *D, RELEASE, {*F,*A}, *E INTERRUPT DISABLING FUNCTIONS ----------------------------- -Functions that disable interrupts (LOCK equivalent) and enable interrupts -(UNLOCK equivalent) will act as compiler barriers only. So if memory or I/O +Functions that disable interrupts (ACQUIRE equivalent) and enable interrupts +(RELEASE equivalent) will act as compiler barriers only. So if memory or I/O barriers are required in such a situation, they must be provided from some other means. @@ -1307,7 +1964,7 @@ CPU 1 =============================== set_current_state(); - set_mb(); + smp_store_mb(); STORE current->state LOAD event_indicated @@ -1348,11 +2005,26 @@ CPU 1 CPU 2 =============================== =============================== set_current_state(); STORE event_indicated - set_mb(); wake_up(); + smp_store_mb(); wake_up(); STORE current->state STORE current->state LOAD event_indicated +To repeat, this write memory barrier is present if and only if something +is actually awakened. To see this, consider the following sequence of +events, where X and Y are both initially zero: + + CPU 1 CPU 2 + =============================== =============================== + X = 1; STORE event_indicated + smp_mb(); wake_up(); + Y = 1; wait_event(wq, Y == 1); + wake_up(); load from Y sees 1, no memory barrier + load from X might see 0 + +In contrast, if a wakeup does occur, CPU 2's load from X would be guaranteed +to see 1. + The available waker functions include: complete(); @@ -1416,75 +2088,47 @@ (*) schedule() and similar imply full memory barriers. -================================= -INTER-CPU LOCKING BARRIER EFFECTS -================================= +=================================== +INTER-CPU ACQUIRING BARRIER EFFECTS +=================================== On SMP systems locking primitives give a more substantial form of barrier: one that does affect memory access ordering on other CPUs, within the context of conflict on any particular lock. -LOCKS VS MEMORY ACCESSES ------------------------- +ACQUIRES VS MEMORY ACCESSES +--------------------------- Consider the following: the system has a pair of spinlocks (M) and (Q), and three CPUs; then should the following sequence of events occur: CPU 1 CPU 2 =============================== =============================== - *A = a; *E = e; - LOCK M LOCK Q - *B = b; *F = f; - *C = c; *G = g; - UNLOCK M UNLOCK Q - *D = d; *H = h; + WRITE_ONCE(*A, a); WRITE_ONCE(*E, e); + ACQUIRE M ACQUIRE Q + WRITE_ONCE(*B, b); WRITE_ONCE(*F, f); + WRITE_ONCE(*C, c); WRITE_ONCE(*G, g); + RELEASE M RELEASE Q + WRITE_ONCE(*D, d); WRITE_ONCE(*H, h); Then there is no guarantee as to what order CPU 3 will see the accesses to *A through *H occur in, other than the constraints imposed by the separate locks on the separate CPUs. It might, for example, see: - *E, LOCK M, LOCK Q, *G, *C, *F, *A, *B, UNLOCK Q, *D, *H, UNLOCK M + *E, ACQUIRE M, ACQUIRE Q, *G, *C, *F, *A, *B, RELEASE Q, *D, *H, RELEASE M But it won't see any of: - *B, *C or *D preceding LOCK M - *A, *B or *C following UNLOCK M - *F, *G or *H preceding LOCK Q - *E, *F or *G following UNLOCK Q - - -However, if the following occurs: - - CPU 1 CPU 2 - =============================== =============================== - *A = a; - LOCK M [1] - *B = b; - *C = c; - UNLOCK M [1] - *D = d; *E = e; - LOCK M [2] - *F = f; - *G = g; - UNLOCK M [2] - *H = h; + *B, *C or *D preceding ACQUIRE M + *A, *B or *C following RELEASE M + *F, *G or *H preceding ACQUIRE Q + *E, *F or *G following RELEASE Q -CPU 3 might see: - *E, LOCK M [1], *C, *B, *A, UNLOCK M [1], - LOCK M [2], *H, *F, *G, UNLOCK M [2], *D -But assuming CPU 1 gets the lock first, CPU 3 won't see any of: - - *B, *C, *D, *F, *G or *H preceding LOCK M [1] - *A, *B or *C following UNLOCK M [1] - *F, *G or *H preceding LOCK M [2] - *A, *B, *C, *E, *F or *G following UNLOCK M [2] - - -LOCKS VS I/O ACCESSES ---------------------- +ACQUIRES VS I/O ACCESSES +------------------------ Under certain circumstances (especially involving NUMA), I/O accesses within two spinlocked sections on two different CPUs may be seen as interleaved by the @@ -1684,29 +2328,31 @@ explicit lock operations, described later). These include: xchg(); - cmpxchg(); - atomic_xchg(); - atomic_cmpxchg(); - atomic_inc_return(); - atomic_dec_return(); - atomic_add_return(); - atomic_sub_return(); - atomic_inc_and_test(); - atomic_dec_and_test(); - atomic_sub_and_test(); - atomic_add_negative(); - atomic_add_unless(); /* when succeeds (returns 1) */ + atomic_xchg(); atomic_long_xchg(); + atomic_inc_return(); atomic_long_inc_return(); + atomic_dec_return(); atomic_long_dec_return(); + atomic_add_return(); atomic_long_add_return(); + atomic_sub_return(); atomic_long_sub_return(); + atomic_inc_and_test(); atomic_long_inc_and_test(); + atomic_dec_and_test(); atomic_long_dec_and_test(); + atomic_sub_and_test(); atomic_long_sub_and_test(); + atomic_add_negative(); atomic_long_add_negative(); test_and_set_bit(); test_and_clear_bit(); test_and_change_bit(); -These are used for such things as implementing LOCK-class and UNLOCK-class + /* when succeeds */ + cmpxchg(); + atomic_cmpxchg(); atomic_long_cmpxchg(); + atomic_add_unless(); atomic_long_add_unless(); + +These are used for such things as implementing ACQUIRE-class and RELEASE-class operations and adjusting reference counters towards object destruction, and as such the implicit memory barrier effects are necessary. The following operations are potential problems as they do _not_ imply memory -barriers, but might be used for implementing such things as UNLOCK-class +barriers, but might be used for implementing such things as RELEASE-class operations: atomic_set(); @@ -1715,11 +2361,11 @@ change_bit(); With these the appropriate explicit memory barrier should be used if necessary -(smp_mb__before_clear_bit() for instance). +(smp_mb__before_atomic() for instance). The following also do _not_ imply memory barriers, and so may require explicit -memory barriers under some circumstances (smp_mb__before_atomic_dec() for +memory barriers under some circumstances (smp_mb__before_atomic() for instance): atomic_add(); @@ -1748,7 +2394,7 @@ clear_bit_unlock(); __clear_bit_unlock(); -These implement LOCK-class and UNLOCK-class operations. These should be used in +These implement ACQUIRE-class and RELEASE-class operations. These should be used in preference to other operations when implementing locking primitives, because their implementations can be optimised on many architectures. @@ -1885,8 +2531,8 @@ space should suffice for PCI. [*] NOTE! attempting to load from the same location as was written to may - cause a malfunction - consider the 16550 Rx/Tx serial registers for - example. + cause a malfunction - consider the 16550 Rx/Tx serial registers for + example. Used with prefetchable I/O memory, an mmiowb() barrier may be required to force stores to be ordered. @@ -1894,10 +2540,15 @@ Please refer to the PCI specification for more information on interactions between PCI transactions. - (*) readX_relaxed() + (*) readX_relaxed(), writeX_relaxed() - These are similar to readX(), but are not guaranteed to be ordered in any - way. Be aware that there is no I/O read barrier available. + These are similar to readX() and writeX(), but provide weaker memory + ordering guarantees. Specifically, they do not guarantee ordering with + respect to normal memory accesses (e.g. DMA buffers) nor do they guarantee + ordering with respect to LOCK or UNLOCK operations. If the latter is + required, an mmiowb() barrier can be used. Note that relaxed accesses to + the same peripheral are guaranteed to be ordered with respect to each + other. (*) ioreadX(), iowriteX() @@ -1953,19 +2604,19 @@ : +--------+ +--------+ : +--------+ +-----------+ | | | | : | | | | +--------+ - | CPU | | Memory | : | CPU | | | | | - | Core |--->| Access |----->| Cache |<-->| | | | + | CPU | | Memory | : | CPU | | | | | + | Core |--->| Access |----->| Cache |<-->| | | | | | | Queue | : | | | |--->| Memory | - | | | | : | | | | | | - +--------+ +--------+ : +--------+ | | | | + | | | | : | | | | | | + +--------+ +--------+ : +--------+ | | | | : | Cache | +--------+ : | Coherency | : | Mechanism | +--------+ +--------+ +--------+ : +--------+ | | | | | | | | : | | | | | | | CPU | | Memory | : | CPU | | |--->| Device | - | Core |--->| Access |----->| Cache |<-->| | | | - | | | Queue | : | | | | | | + | Core |--->| Access |----->| Cache |<-->| | | | + | | | Queue | : | | | | | | | | | | : | | | | +--------+ +--------+ +--------+ : +--------+ +-----------+ : @@ -2088,7 +2739,7 @@ p = &v; q = p; - + x = *q; Reads from v before v updated in cache @@ -2113,7 +2764,7 @@ p = &v; q = p; - + smp_read_barrier_depends() @@ -2175,11 +2826,11 @@ operations in exactly the order specified, so that if the CPU is, for example, given the following piece of code to execute: - a = *A; - *B = b; - c = *C; - d = *D; - *E = e; + a = READ_ONCE(*A); + WRITE_ONCE(*B, b); + c = READ_ONCE(*C); + d = READ_ONCE(*D); + WRITE_ONCE(*E, e); they would then expect that the CPU will complete the memory operation for each instruction before moving on to the next one, leading to a definite sequence of @@ -2226,12 +2877,12 @@ _own_ accesses appear to be correctly ordered, without the need for a memory barrier. For instance with the following code: - U = *A; - *A = V; - *A = W; - X = *A; - *A = Y; - Z = *A; + U = READ_ONCE(*A); + WRITE_ONCE(*A, V); + WRITE_ONCE(*A, W); + X = READ_ONCE(*A); + WRITE_ONCE(*A, Y); + Z = READ_ONCE(*A); and assuming no intervention by an external influence, it can be assumed that the final result will appear to be: @@ -2247,8 +2898,14 @@ U=LOAD *A, STORE *A=V, STORE *A=W, X=LOAD *A, STORE *A=Y, Z=LOAD *A in that order, but, without intervention, the sequence may have almost any -combination of elements combined or discarded, provided the program's view of -the world remains consistent. +combination of elements combined or discarded, provided the program's view +of the world remains consistent. Note that READ_ONCE() and WRITE_ONCE() +are -not- optional in the above example, as there are architectures +where a given CPU might reorder successive loads to the same location. +On such architectures, READ_ONCE() and WRITE_ONCE() do whatever is +necessary to prevent this, for example, on Itanium the volatile casts +used by READ_ONCE() and WRITE_ONCE() cause GCC to emit the special ld.acq +and st.rel instructions (respectively) that prevent such reordering. The compiler may also combine, discard or defer elements of the sequence before the CPU even sees them. @@ -2262,13 +2919,14 @@ *A = W; -since, without a write barrier, it can be assumed that the effect of the -storage of V to *A is lost. Similarly: +since, without either a write barrier or an WRITE_ONCE(), it can be +assumed that the effect of the storage of V to *A is lost. Similarly: *A = Y; Z = *A; -may, without a memory barrier, be reduced to: +may, without a memory barrier or an READ_ONCE() and WRITE_ONCE(), be +reduced to: *A = Y; Z = Y;