============================
LINUX KERNEL MEMORY BARRIERS
============================
By: David Howells <dhowells@redhat.com>
Paul E. McKenney <paulmck@linux.ibm.com>
Will Deacon <will.deacon@arm.com>
Peter Zijlstra <peterz@infradead.org>
==========
DISCLAIMER
==========
This document is not a specification; it is intentionally (for the sake of
brevity) and unintentionally (due to being human) incomplete. This document is
meant as a guide to using the various memory barriers provided by Linux, but
in case of any doubt (and there are many) please ask. Some doubts may be
resolved by referring to the formal memory consistency model and related
documentation at tools/memory-model/. Nevertheless, even this memory
model should be viewed as the collective opinion of its maintainers rather
than as an infallible oracle.
To repeat, this document is not a specification of what Linux expects from
hardware.
The purpose of this document is twofold:
(1) to specify the minimum functionality that one can rely on for any
particular barrier, and
(2) to provide a guide as to how to use the barriers that are available.
Note that an architecture can provide more than the minimum requirement
for any particular barrier, but if the architecture provides less than
that, that architecture is incorrect.
Note also that it is possible that a barrier may be a no-op for an
architecture because the way that arch works renders an explicit barrier
unnecessary in that case.
========
CONTENTS
========
(*) Abstract memory access model.
- Device operations.
- Guarantees.
(*) What are memory barriers?
- Varieties of memory barrier.
- What may not be assumed about memory barriers?
- Address-dependency barriers (historical).
- Control dependencies.
- SMP barrier pairing.
- Examples of memory barrier sequences.
- Read memory barriers vs load speculation.
- Multicopy atomicity.
(*) Explicit kernel barriers.
- Compiler barrier.
- CPU memory barriers.
(*) Implicit kernel memory barriers.
- Lock acquisition functions.
- Interrupt disabling functions.
- Sleep and wake-up functions.
- Miscellaneous functions.
(*) Inter-CPU acquiring barrier effects.
- Acquires vs memory accesses.
(*) Where are memory barriers needed?
- Interprocessor interaction.
- Atomic operations.
- Accessing devices.
- Interrupts.
(*) Kernel I/O barrier effects.
(*) Assumed minimum execution ordering model.
(*) The effects of the cpu cache.
- Cache coherency vs DMA.
- Cache coherency vs MMIO.
(*) The things CPUs get up to.
- And then there's the Alpha.
- Virtual Machine Guests.
(*) Example uses.
- Circular buffers.
(*) References.
============================
ABSTRACT MEMORY ACCESS MODEL
============================
Consider the following abstract model of the system:
: :
: :
: :
+-------+ : +--------+ : +-------+
| | : | | : | |
| | : | | : | |
| CPU 1 |<----->| Memory |<----->| CPU 2 |
| | : | | : | |
| | : | | : | |
+-------+ : +--------+ : +-------+
^ : ^ : ^
| : | : |
| : | : |
| : v : |
| : +--------+ : |
| : | | : |
| : | | : |
+---------->| Device |<----------+
: | | :
: | | :
: +--------+ :
: :
Each CPU executes a program that generates memory access operations. In the
abstract CPU, memory operation ordering is very relaxed, and a CPU may actually
perform the memory operations in any order it likes, provided program causality
appears to be maintained. Similarly, the compiler may also arrange the
instructions it emits in any order it likes, provided it doesn't affect the
apparent operation of the program.
So in the above diagram, the effects of the memory operations performed by a
CPU are perceived by the rest of the system as the operations cross the
interface between the CPU and rest of the system (the dotted lines).
For example, consider the following sequence of events:
CPU 1 CPU 2
=============== ===============
{ A == 1; B == 2 }
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, 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 == 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
perceived by the loads made by another CPU in the same order as the stores were
committed.
As a further example, consider this sequence of events:
CPU 1 CPU 2
=============== ===============
{ A == 1, B == 2, C == 3, P == &A, Q == &C }
B = 4; Q = P;
P = &B; D = *Q;
There is an obvious address dependency here, as the value loaded into D depends
on the address retrieved from P by CPU 2. At the end of the sequence, any of
the following results are possible:
(Q == &A) and (D == 1)
(Q == &B) and (D == 2)
(Q == &B) and (D == 4)
Note that CPU 2 will never try and load C into D because the CPU will load P
into Q before issuing the load of *Q.
DEVICE OPERATIONS
-----------------
Some devices present their control interfaces as collections of memory
locations, but the order in which the control registers are accessed is very
important. For instance, imagine an ethernet card with a set of internal
registers that are accessed through an address port register (A) and a data
port register (D). To read internal register 5, the following code might then
be used:
*A = 5;
x = *D;
but this might show up as either of the following two sequences:
STORE *A = 5, x = LOAD *D
x = LOAD *D, STORE *A = 5
the second of which will almost certainly result in a malfunction, since it set
the address _after_ attempting to read the register.
GUARANTEES
----------
There are some minimal guarantees that may be expected of a CPU:
(*) On any given CPU, dependent memory accesses will be issued in order, with
respect to itself. This means that for:
Q = READ_ONCE(P); D = READ_ONCE(*Q);
the CPU will issue the following memory operations:
Q = LOAD P, D = LOAD *Q
and always in that order. However, on DEC Alpha, READ_ONCE() also
emits a memory-barrier instruction, so that a DEC Alpha CPU will
instead issue the following memory operations:
Q = LOAD P, MEMORY_BARRIER, D = LOAD *Q, MEMORY_BARRIER
Whether on DEC Alpha or not, the READ_ONCE() also prevents compiler
mischief.
(*) Overlapping loads and stores within a particular CPU will appear to be
ordered within that CPU. This means that for:
a = READ_ONCE(*X); WRITE_ONCE(*X, b);
the CPU will only issue the following sequence of memory operations:
a = LOAD *X, STORE *X = b
And for:
WRITE_ONCE(*X, c); d = READ_ONCE(*X);
the CPU will only issue:
STORE *X = c, d = LOAD *X
(Loads and stores overlap if they are targeted at overlapping pieces of
memory).
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:
X = *A; Y = *B; *D = Z;
we may get any of the following sequences:
X = LOAD *A, Y = LOAD *B, STORE *D = Z
X = LOAD *A, STORE *D = Z, Y = LOAD *B
Y = LOAD *B, X = LOAD *A, STORE *D = Z
Y = LOAD *B, STORE *D = Z, X = LOAD *A
STORE *D = Z, X = LOAD *A, Y = LOAD *B
STORE *D = Z, Y = LOAD *B, X = LOAD *A
(*) It _must_ be assumed that overlapping memory accesses may be merged or
discarded. This means that for:
X = *A; Y = *(A + 4);
we may get any one of the following sequences:
X = LOAD *A; Y = LOAD *(A + 4);
Y = LOAD *(A + 4); X = LOAD *A;
{X, Y} = LOAD {*A, *(A + 4) };
And for:
*A = X; *(A + 4) = Y;
we may get any of:
STORE *A = X; STORE *(A + 4) = Y;
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?
=========================
As can be seen above, independent memory operations are effectively performed
in random order, but this can be a problem for CPU-CPU interaction and for I/O.
What is required is some way of intervening to instruct the compiler and the
CPU to restrict the order.
Memory barriers are such interventions. They impose a perceived partial
ordering over the memory operations on either side of the barrier.
Such enforcement is important because the CPUs and other devices in a system
can use a variety of tricks to improve performance, including reordering,
deferral and combination of memory operations; speculative loads; speculative
branch prediction and various types of caching. Memory barriers are used to
override or suppress these tricks, allowing the code to sanely control the
interaction of multiple CPUs and/or devices.
VARIETIES OF MEMORY BARRIER
---------------------------
Memory barriers come in four basic varieties:
(1) Write (or store) memory barriers.
A write memory barrier gives a guarantee that all the STORE operations
specified before the barrier will appear to happen before all the STORE
operations specified after the barrier with respect to the other
components of the system.
A write barrier is a partial ordering on stores only; it is not required
to have any effect on loads.
A CPU can be viewed as committing a sequence of store operations to the
memory system as time progresses. All stores _before_ a write barrier
will occur _before_ all the stores after the write barrier.
[!] Note that write barriers should normally be paired with read or
address-dependency barriers; see the "SMP barrier pairing" subsection.
(2) Address-dependency barriers (historical).
[!] This section is marked as HISTORICAL: it covers the long-obsolete
smp_read_barrier_depends() macro, the semantics of which are now
implicit in all marked accesses. For more up-to-date information,
including how compiler transformations can sometimes break address
dependencies, see Documentation/RCU/rcu_dereference.rst.
An address-dependency barrier is a weaker form of read barrier. In the
case where two loads are performed such that the second depends on the
result of the first (eg: the first load retrieves the address to which
the second load will be directed), an address-dependency barrier would
be required to make sure that the target of the second load is updated
after the address obtained by the first load is accessed.
An address-dependency barrier is a partial ordering on interdependent
loads only; it is not required to have any effect on stores, independent
loads or overlapping loads.
As mentioned in (1), the other CPUs in the system can be viewed as
committing sequences of stores to the memory system that the CPU being
considered can then perceive. An address-dependency barrier issued by
the CPU under consideration guarantees that for any load preceding it,
if that load touches one of a sequence of stores from another CPU, then
by the time the barrier completes, the effects of all the stores prior to
that touched by the load will be perceptible to any loads issued after
the address-dependency barrier.
See the "Examples of memory barrier sequences" subsection for diagrams
showing the ordering constraints.
[!] Note that the first load really has to have an _address_ dependency and
not a control dependency. If the address for the second load is dependent
on the first load, but the dependency is through a conditional rather than
actually loading the address itself, then it's a _control_ dependency and
a full read barrier or better is required. See the "Control dependencies"
subsection for more information.
[!] Note that address-dependency barriers should normally be paired with
write barriers; see the "SMP barrier pairing" subsection.
[!] Kernel release v5.9 removed kernel APIs for explicit address-
dependency barriers. Nowadays, APIs for marking loads from shared
variables such as READ_ONCE() and rcu_dereference() provide implicit
address-dependency barriers.
(3) Read (or load) memory barriers.
A read barrier is an address-dependency barrier plus a guarantee that all
the LOAD operations specified before the barrier will appear to happen
before all the LOAD operations specified after the barrier with respect to
the other components of the system.
A read barrier is a partial ordering on loads only; it is not required to
have any effect on stores.
Read memory barriers imply address-dependency barriers, and so can
substitute for them.
[!] Note that read barriers should normally be paired with write barriers;
see the "SMP barrier pairing" subsection.
(4) General memory barriers.
A general memory barrier gives a guarantee that all the LOAD and STORE
operations specified before the barrier will appear to happen before all
the LOAD and STORE operations specified after the barrier with respect to
the other components of the system.
A general memory barrier is a partial ordering over both loads and stores.
General memory barriers imply both read and write memory barriers, and so
can substitute for either.
And a couple of implicit varieties:
(5) ACQUIRE operations.
This acts as a one-way permeable barrier. It guarantees that all memory
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 both smp_load_acquire()
and smp_cond_load_acquire() operations.
Memory operations that occur before an ACQUIRE operation may appear to
happen after it completes.
An ACQUIRE operation should almost always be paired with a RELEASE
operation.
(6) RELEASE operations.
This also acts as a one-way permeable barrier. It guarantees that all
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 a RELEASE operation may appear to
happen before it completes.
The use of ACQUIRE and RELEASE operations generally precludes the need
for other sorts of memory 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.
This means that ACQUIRE acts as a minimal "acquire" operation and
RELEASE acts as a minimal "release" operation.
A subset of the atomic operations described in atomic_t.txt have ACQUIRE and
RELEASE variants in addition to fully-ordered and relaxed (no barrier
semantics) definitions. For compound atomics performing both a load and a
store, ACQUIRE semantics apply only to the load and RELEASE semantics apply
only to the store portion of the operation.
Memory barriers are only required where there's a possibility of interaction
between two CPUs or between a CPU and a device. If it can be guaranteed that
there won't be any such interaction in any particular piece of code, then
memory barriers are unnecessary in that piece of code.
Note that these are the _minimum_ guarantees. Different architectures may give
more substantial guarantees, but they may _not_ be relied upon outside of arch
specific code.
WHAT MAY NOT BE ASSUMED ABOUT MEMORY BARRIERS?
----------------------------------------------
There are certain things that the Linux kernel memory barriers do not guarantee:
(*) There is no guarantee that any of the memory accesses specified before a
memory barrier will be _complete_ by the completion of a memory barrier
instruction; the barrier can be considered to draw a line in that CPU's
access queue that accesses of the appropriate type may not cross.
(*) There is no guarantee that issuing a memory barrier on one CPU will have
any direct effect on another CPU or any other hardware in the system. The
indirect effect will be the order in which the second CPU sees the effects
of the first CPU's accesses occur, but see the next point:
(*) There is no guarantee that a CPU will see the correct order of effects
from a second CPU's accesses, even _if_ the second CPU uses a memory
barrier, unless the first CPU _also_ uses a matching memory barrier (see
the subsection on "SMP Barrier Pairing").
(*) There is no guarantee that some intervening piece of off-the-CPU
hardware[*] will not reorder the memory accesses. CPU cache coherency
mechanisms should propagate the indirect effects of a memory barrier
between CPUs, but might not do so in order.
[*] For information on bus mastering DMA and coherency please read:
Documentation/driver-api/pci/pci.rst
Documentation/core-api/dma-api-howto.rst
Documentation/core-api/dma-api.rst
ADDRESS-DEPENDENCY BARRIERS (HISTORICAL)
----------------------------------------
[!] This section is marked as HISTORICAL: it covers the long-obsolete
smp_read_barrier_depends() macro, the semantics of which are now implicit
in all marked accesses. For more up-to-date information, including
how compiler transformations can sometimes break address dependencies,
see Documentation/RCU/rcu_dereference.rst.
As of v4.15 of the Linux kernel, an smp_mb() was added to READ_ONCE() for
DEC Alpha, which means that about the only people who need to pay attention
to this section are those working on DEC Alpha architecture-specific code
and those working on READ_ONCE() itself. For those who need it, and for
those who are interested in the history, here is the story of
address-dependency barriers.
[!] While address dependencies are observed in both load-to-load and
load-to-store relations, address-dependency barriers are not necessary
for load-to-store situations.
The requirement of address-dependency barriers is a little subtle, and
it's not always obvious that they're needed. To illustrate, consider the
following sequence of events:
CPU 1 CPU 2
=============== ===============
{ A == 1, B == 2, C == 3, P == &A, Q == &C }
B = 4;
<write barrier>
WRITE_ONCE(P, &B);
Q = READ_ONCE_OLD(P);
D = *Q;
[!] READ_ONCE_OLD() corresponds to READ_ONCE() of pre-4.15 kernel, which
doesn't imply an address-dependency barrier.
There's a clear address dependency here, and it would seem that by the end of
the sequence, Q must be either &A or &B, and that:
(Q == &A) implies (D == 1)
(Q == &B) implies (D == 4)
But! CPU 2's perception of P may be updated _before_ its perception of B, thus
leading to the following situation:
(Q == &B) and (D == 2) ????
While this may seem like a failure of coherency or causality maintenance, it
isn't, and this behaviour can be observed on certain real CPUs (such as the DEC
Alpha).
To deal with this, READ_ONCE() provides an implicit address-dependency barrier
since kernel release v4.15:
CPU 1 CPU 2
=============== ===============
{ A == 1, B == 2, C == 3, P == &A, Q == &C }
B = 4;
<write barrier>
WRITE_ONCE(P, &B);
Q = READ_ONCE(P);
<implicit address-dependency barrier>
D = *Q;
This enforces the occurrence of one of the two implications, and prevents the
third possibility from arising.
[!] Note that this extremely counterintuitive situation arises most easily on
machines with split caches, so that, for example, one cache bank processes
even-numbered cache lines and the other bank processes odd-numbered cache
lines. The pointer P might be stored in an odd-numbered cache line, and the
variable B might be stored in an even-numbered cache line. Then, if the
even-numbered bank of the reading CPU's cache is extremely busy while the
odd-numbered bank is idle, one can see the new value of the pointer P (&B),
but the old value of the variable B (2).
An address-dependency barrier is not required to order dependent writes
because the CPUs that the Linux kernel supports don't do writes until they
are certain (1) that the write will actually happen, (2) of the location of
the write, and (3) of the value to be written.
But please carefully read the "CONTROL DEPENDENCIES" section and the
Documentation/RCU/rcu_dereference.rst file: The compiler can and does break
dependencies in a great many highly creative ways.
CPU 1 CPU 2
=============== ===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;
<write barrier>
WRITE_ONCE(P, &B);
Q = READ_ONCE_OLD(P);
WRITE_ONCE(*Q, 5);
Therefore, no address-dependency barrier is required to order the read into
Q with the store into *Q. In other words, this outcome is prohibited,
even without an implicit address-dependency barrier of modern READ_ONCE():
(Q == &B) && (B == 4)
Please note that this pattern should be rare. After all, the whole point
of dependency ordering is to -prevent- writes to the data structure, along
with the expensive cache misses associated with those writes. This pattern
can be used to record rare error conditions and the like, and the CPUs'
naturally occurring ordering prevents such records from being lost.
Note well that the ordering provided by an address dependency is local to
the CPU containing it. See the section on "Multicopy atomicity" for
more information.
The address-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.
CONTROL DEPENDENCIES
--------------------
Control dependencies can be a bit tricky because current compilers do
not understand them. The purpose of this section is to help you prevent
the compiler's ignorance from breaking your code.
A load-load control dependency requires a full read memory barrier, not
simply an (implicit) address-dependency barrier to make it work correctly.
Consider the following bit of code:
q = READ_ONCE(a);
<implicit address-dependency barrier>
if (q) {
/* BUG: No address dependency!!! */
p = READ_ONCE(b);
}
This will not have the desired effect because there is no actual address
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) {
<read barrier>
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, 1);
}
Control dependencies pair normally with other types of barriers.
That said, please note that neither READ_ONCE() nor WRITE_ONCE()
are optional! Without the READ_ONCE(), the compiler might combine the
load from 'a' with other loads from 'a'. Without the WRITE_ONCE(),
the compiler might combine the store to 'b' with other stores to 'b'.
Either can result in 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 = 1; /* 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, 1);
do_something();
} else {
barrier();
WRITE_ONCE(b, 1);
do_something_else();
}
Unfortunately, current compilers will transform this as follows at high
optimization levels:
q = READ_ONCE(a);
barrier();
WRITE_ONCE(b, 1); /* BUG: No ordering vs. load from a!!! */
if (q) {
/* WRITE_ONCE(b, 1); -- moved up, BUG!!! */
do_something();
} else {
/* WRITE_ONCE(b, 1); -- 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, 1);
do_something();
} else {
smp_store_release(&b, 1);
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, 1);
do_something();
} else {
WRITE_ONCE(b, 2);
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, 1);
do_something();
} else {
WRITE_ONCE(b, 2);
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, 2);
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, 1);
do_something();
} else {
WRITE_ONCE(b, 2);
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.
In addition, control dependencies apply only to the then-clause and
else-clause of the if-statement in question. In particular, it does
not necessarily apply to code following the if-statement:
q = READ_ONCE(a);
if (q) {
WRITE_ONCE(b, 1);
} else {
WRITE_ONCE(b, 2);
}
WRITE_ONCE(c, 1); /* BUG: No ordering against the read from 'a'. */
It is tempting to argue that there in fact is ordering because the
compiler cannot reorder volatile accesses and also cannot reorder
the writes to 'b' with the condition. Unfortunately for this line
of reasoning, the compiler might compile the two writes to 'b' as
conditional-move instructions, as in this fanciful pseudo-assembly
language:
ld r1,a
cmp r1,$0
cmov,ne r4,$1
cmov,eq r4,$2
st r4,b
st $1,c
A weakly ordered CPU would have no dependency of any sort between the load
from 'a' and the store to 'c'. The control dependencies would extend
only to the pair of cmov instructions and the store depending on them.
In short, control dependencies apply only to the stores in the then-clause
and else-clause of the if-statement in question (including functions
invoked by those two clauses), not to code following that if-statement.
Note well that the ordering provided by a control dependency is local
to the CPU containing it. See the section on "Multicopy atomicity"
for more information.
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, then those stores must be ordered, either by
preceding both of them with smp_mb() or by using smp_store_release()
to carry out the stores. Please note that it is -not- sufficient
to use barrier() at beginning of each leg of the "if" statement
because, as shown by the example above, optimizing compilers can
destroy the control dependency while respecting the letter of the
barrier() law.
(*) 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 apply only to the then-clause and else-clause
of the if-statement containing the control dependency, including
any functions that these two clauses call. Control dependencies
do -not- apply to code following the if-statement containing the
control dependency.
(*) Control dependencies pair normally with other types of barriers.
(*) Control dependencies do -not- provide multicopy atomicity. If you
need all the CPUs to see a given store at the same time, use smp_mb().
(*) Compilers do not understand control dependencies. It is therefore
your job to ensure that they do not break your code.
SMP BARRIER PAIRING
-------------------
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.
General barriers pair with each other, though they also pair with most
other types of barriers, albeit without multicopy atomicity. 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 an address-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 an address-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);
<write barrier>
WRITE_ONCE(b, 2); x = READ_ONCE(b);
<read barrier>
y = READ_ONCE(a);
Or:
CPU 1 CPU 2
=============== ===============================
a = 1;
<write barrier>
WRITE_ONCE(b, &a); x = READ_ONCE(b);
<implicit address-dependency barrier>
y = *x;
Or even:
CPU 1 CPU 2
=============== ===============================
r1 = READ_ONCE(y);
<general barrier>
WRITE_ONCE(x, 1); if (r2 = READ_ONCE(x)) {
<implicit control dependency>
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.
[!] Note that the stores before the write barrier would normally be expected to
match the loads after the read barrier or the address-dependency barrier, and
vice versa:
CPU 1 CPU 2
=================== ===================
WRITE_ONCE(a, 1); }---- --->{ v = READ_ONCE(c);
WRITE_ONCE(b, 2); } \ / { w = READ_ONCE(d);
<write barrier> \ <read barrier>
WRITE_ONCE(c, 3); } / \ { x = READ_ONCE(a);
WRITE_ONCE(d, 4); }---- --->{ y = READ_ONCE(b);
EXAMPLES OF MEMORY BARRIER SEQUENCES
------------------------------------
Firstly, write barriers act as partial orderings on store operations.
Consider the following sequence of events:
CPU 1
=======================
STORE A = 1
STORE B = 2
STORE C = 3
<write barrier>
STORE D = 4
STORE E = 5
This sequence of events is committed to the memory coherence system in an order
that the rest of the system might perceive as the unordered set of { STORE A,
STORE B, STORE C } all occurring before the unordered set of { STORE D, STORE E
}:
+-------+ : :
| | +------+
| |------>| C=3 | } /\
| | : +------+ }----- \ -----> Events perceptible to
| | : | A=1 | } \/ the rest of the system
| | : +------+ }
| CPU 1 | : | B=2 | }
| | +------+ }
| | wwwwwwwwwwwwwwww } <--- At this point the write barrier
| | +------+ } requires all stores prior to the
| | : | E=5 | } barrier to be committed before
| | : +------+ } further stores may take place
| |------>| D=4 | }
| | +------+
+-------+ : :
|
| Sequence in which stores are committed to the
| memory system by CPU 1
V
Secondly, address-dependency barriers act as partial orderings on address-
dependent loads. Consider the following sequence of events:
CPU 1 CPU 2
======================= =======================
{ B = 7; X = 9; Y = 8; C = &Y }
STORE A = 1
STORE B = 2
<write barrier>
STORE C = &B LOAD X
STORE D = 4 LOAD C (gets &B)
LOAD *C (reads B)
Without intervention, CPU 2 may perceive the events on CPU 1 in some
effectively random order, despite the write barrier issued by CPU 1:
+-------+ : : : :
| | +------+ +-------+ | Sequence of update
| |------>| B=2 |----- --->| Y->8 | | of perception on
| | : +------+ \ +-------+ | CPU 2
| CPU 1 | : | A=1 | \ --->| C->&Y | V
| | +------+ | +-------+
| | wwwwwwwwwwwwwwww | : :
| | +------+ | : :
| | : | C=&B |--- | : : +-------+
| | : +------+ \ | +-------+ | |
| |------>| D=4 | ----------->| C->&B |------>| |
| | +------+ | +-------+ | |
+-------+ : : | : : | |
| : : | |
| : : | CPU 2 |
| +-------+ | |
Apparently incorrect ---> | | B->7 |------>| |
perception of B (!) | +-------+ | |
| : : | |
| +-------+ | |
The load of X holds ---> \ | X->9 |------>| |
up the maintenance \ +-------+ | |
of coherence of B ----->| B->2 | +-------+
+-------+
: :
In the above example, CPU 2 perceives that B is 7, despite the load of *C
(which would be B) coming after the LOAD of C.
If, however, an address-dependency barrier were to be placed between the load
of C and the load of *C (ie: B) on CPU 2:
CPU 1 CPU 2
======================= =======================
{ B = 7; X = 9; Y = 8; C = &Y }
STORE A = 1
STORE B = 2
<write barrier>
STORE C = &B LOAD X
STORE D = 4 LOAD C (gets &B)
<address-dependency barrier>
LOAD *C (reads B)
then the following will occur:
+-------+ : : : :
| | +------+ +-------+
| |------>| B=2 |----- --->| Y->8 |
| | : +------+ \ +-------+
| CPU 1 | : | A=1 | \ --->| C->&Y |
| | +------+ | +-------+
| | wwwwwwwwwwwwwwww | : :
| | +------+ | : :
| | : | C=&B |--- | : : +-------+
| | : +------+ \ | +-------+ | |
| |------>| D=4 | ----------->| C->&B |------>| |
| | +------+ | +-------+ | |
+-------+ : : | : : | |
| : : | |
| : : | CPU 2 |
| +-------+ | |
| | X->9 |------>| |
| +-------+ | |
Makes sure all effects ---> \ aaaaaaaaaaaaaaaaa | |
prior to the store of C \ +-------+ | |
are perceptible to ----->| B->2 |------>| |
subsequent loads +-------+ | |
: : +-------+
And thirdly, a read barrier acts as a partial order on loads. Consider the
following sequence of events:
CPU 1 CPU 2
======================= =======================
{ A = 0, B = 9 }
STORE A=1
<write barrier>
STORE B=2
LOAD B
LOAD A
Without intervention, CPU 2 may then choose to perceive the events on CPU 1 in
some effectively random order, despite the write barrier issued by CPU 1:
+-------+ : : : :
| | +------+ +-------+
| |------>| A=1 |------ --->| A->0 |
| | +------+ \ +-------+
| CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 |
| | +------+ | +-------+
| |------>| B=2 |--- | : :
| | +------+ \ | : : +-------+
+-------+ : : \ | +-------+ | |
---------->| B->2 |------>| |
| +-------+ | CPU 2 |
| | A->0 |------>| |
| +-------+ | |
| : : +-------+
\ : :
\ +-------+
---->| A->1 |
+-------+
: :
If, however, a read barrier were to be placed between the load of B and the
load of A on CPU 2:
CPU 1 CPU 2
======================= =======================
{ A = 0, B = 9 }
STORE A=1
<write barrier>
STORE B=2
LOAD B
<read barrier>
LOAD A
then the partial ordering imposed by CPU 1 will be perceived correctly by CPU
2:
+-------+ : : : :
| | +------+ +-------+
| |------>| A=1 |------ --->| A->0 |
| | +------+ \ +-------+
| CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 |
| | +------+ | +-------+
| |------>| B=2 |--- | : :
| | +------+ \ | : : +-------+
+-------+ : : \ | +-------+ | |
---------->| B->2 |------>| |
| +-------+ | CPU 2 |
| : : | |
| : : | |
At this point the read ----> \ rrrrrrrrrrrrrrrrr | |
barrier causes all effects \ +-------+ | |
prior to the storage of B ---->| A->1 |------>| |
to be perceptible to CPU 2 +-------+ | |
: : +-------+
To illustrate this more completely, consider what could happen if the code
contained a load of A either side of the read barrier:
CPU 1 CPU 2
======================= =======================
{ A = 0, B = 9 }
STORE A=1
<write barrier>
STORE B=2
LOAD B
LOAD A [first load of A]
<read barrier>
LOAD A [second load of A]
Even though the two loads of A both occur after the load of B, they may both
come up with different values:
+-------+ : : : :
| | +------+ +-------+
| |------>| A=1 |------ --->| A->0 |
| | +------+ \ +-------+
| CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 |
| | +------+ | +-------+
| |------>| B=2 |--- | : :
| | +------+ \ | : : +-------+
+-------+ : : \ | +-------+ | |
---------->| B->2 |------>| |
| +-------+ | CPU 2 |
| : : | |
| : : | |
| +-------+ | |
| | A->0 |------>| 1st |
| +-------+ | |
At this point the read ----> \ rrrrrrrrrrrrrrrrr | |
barrier causes all effects \ +-------+ | |
prior to the storage of B ---->| A->1 |------>| 2nd |
to be perceptible to CPU 2 +-------+ | |
: : +-------+
But it may be that the update to A from CPU 1 becomes perceptible to CPU 2
before the read barrier completes anyway:
+-------+ : : : :
| | +------+ +-------+
| |------>| A=1 |------ --->| A->0 |
| | +------+ \ +-------+
| CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 |
| | +------+ | +-------+
| |------>| B=2 |--- | : :
| | +------+ \ | : : +-------+
+-------+ : : \ | +-------+ | |
---------->| B->2 |------>| |
| +-------+ | CPU 2 |
| : : | |
\ : : | |
\ +-------+ | |
---->| A->1 |------>| 1st |
+-------+ | |
rrrrrrrrrrrrrrrrr | |
+-------+ | |
| A->1 |------>| 2nd |
+-------+ | |
: : +-------+
The guarantee is that the second load will always come up with A == 1 if the
load of B came up with B == 2. No such guarantee exists for the first load of
A; that may come up with either A == 0 or A == 1.
READ MEMORY BARRIERS VS LOAD SPECULATION
----------------------------------------
Many CPUs speculate with loads: that is they see that they will need to load an
item from memory, and they find a time where they're not using the bus for any
other loads, and so do the load in advance - even though they haven't actually
got to that point in the instruction execution flow yet. This permits the
actual load instruction to potentially complete immediately because the CPU
already has the value to hand.
It may turn out that the CPU didn't actually need the value - perhaps because a
branch circumvented the load - in which case it can discard the value or just
cache it for later use.
Consider:
CPU 1 CPU 2
======================= =======================
LOAD B
DIVIDE } Divide instructions generally
DIVIDE } take a long time to perform
LOAD A
Which might appear as this:
: : +-------+
+-------+ | |
--->| B->2 |------>| |
+-------+ | CPU 2 |
: :DIVIDE | |
+-------+ | |
The CPU being busy doing a ---> --->| A->0 |~~~~ | |
division speculates on the +-------+ ~ | |
LOAD of A : : ~ | |
: :DIVIDE | |
: : ~ | |
Once the divisions are complete --> : : ~-->| |
the CPU can then perform the : : | |
LOAD with immediate effect : : +-------+
Placing a read barrier or an address-dependency barrier just before the second
load:
CPU 1 CPU 2
======================= =======================
LOAD B
DIVIDE
DIVIDE
<read barrier>
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
speculated memory location, then the speculated value will just be used:
: : +-------+
+-------+ | |
--->| B->2 |------>| |
+-------+ | CPU 2 |
: :DIVIDE | |
+-------+ | |
The CPU being busy doing a ---> --->| A->0 |~~~~ | |
division speculates on the +-------+ ~ | |
LOAD of A : : ~ | |
: :DIVIDE | |
: : ~ | |
: : ~ | |
rrrrrrrrrrrrrrrr~ | |
: : ~ | |
: : ~-->| |
: : | |
: : +-------+
but if there was an update or an invalidation from another CPU pending, then
the speculation will be cancelled and the value reloaded:
: : +-------+
+-------+ | |
--->| B->2 |------>| |
+-------+ | CPU 2 |
: :DIVIDE | |
+-------+ | |
The CPU being busy doing a ---> --->| A->0 |~~~~ | |
division speculates on the +-------+ ~ | |
LOAD of A : : ~ | |
: :DIVIDE | |
: : ~ | |
: : ~ | |
rrrrrrrrrrrrrrrrr | |
+-------+ | |
The speculation is discarded ---> --->| A->1 |------>| |
and an updated value is +-------+ | |
retrieved : : +-------+
MULTICOPY ATOMICITY
--------------------
Multicopy atomicity is a deeply intuitive notion about ordering that is
not always provided by real computer systems, namely that a given store
becomes visible at the same time to all CPUs, or, alternatively, that all
CPUs agree on the order in which all stores become visible. However,
support of full multicopy atomicity would rule out valuable hardware
optimizations, so a weaker form called ``other multicopy atomicity''
instead guarantees only that a given store becomes visible at the same
time to all -other- CPUs. The remainder of this document discusses this
weaker form, but for brevity will call it simply ``multicopy atomicity''.
The following example demonstrates multicopy atomicity:
CPU 1 CPU 2 CPU 3
======================= ======================= =======================
{ X = 0, Y = 0 }
STORE X=1 r1=LOAD X (reads 1) LOAD Y (reads 1)
<general barrier> <read barrier>
STORE Y=r1 LOAD X
Suppose that CPU 2's load from X returns 1, which it then stores to Y,
and CPU 3's load from Y returns 1. This indicates that CPU 1's store
to X precedes CPU 2's load from X and that CPU 2's store to Y precedes
CPU 3's load from Y. In addition, the memory barriers guarantee that
CPU 2 executes its load before its store, and CPU 3 loads from Y before
it loads from X. The question is then "Can CPU 3's load from X return 0?"
Because CPU 3's load from X in some sense comes after CPU 2's load, it
is natural to expect that CPU 3's load from X must therefore return 1.
This expectation follows from multicopy atomicity: if a load executing
on CPU B follows a load from the same variable executing on CPU A (and
CPU A did not originally store the value which it read), then on
multicopy-atomic systems, CPU B's load must return either the same value
that CPU A's load did or some later value. However, the Linux kernel
does not require systems to be multicopy atomic.
The use of a general memory barrier in the example above compensates
for any lack of multicopy atomicity. In the example, if CPU 2's load
from X returns 1 and CPU 3's load from Y returns 1, then CPU 3's load
from X must indeed also return 1.
However, dependencies, read barriers, and write barriers are not always
able to compensate for non-multicopy atomicity. For example, suppose
that CPU 2's general barrier is removed from the above example, leaving
only the data dependency shown below:
CPU 1 CPU 2 CPU 3
======================= ======================= =======================
{ X = 0, Y = 0 }
STORE X=1 r1=LOAD X (reads 1) LOAD Y (reads 1)
<data dependency> <read barrier>
STORE Y=r1 LOAD X (reads 0)
This substitution allows non-multicopy atomicity to run rampant: in
this example, it is perfectly legal for CPU 2's load from X to return 1,
CPU 3's load from Y to return 1, and its load from X to return 0.
The key point is that although CPU 2's data dependency orders its load
and store, it does not guarantee to order CPU 1's store. Thus, if this
example runs on a non-multicopy-atomic system where CPUs 1 and 2 share a
store buffer or a level of cache, CPU 2 might have early access to CPU 1's
writes. General barriers are therefore required to ensure that all CPUs
agree on the combined order of multiple accesses.
General barriers can compensate not only for non-multicopy atomicity,
but can also generate additional ordering that can ensure that -all-
CPUs will perceive the same order of -all- operations. In contrast, a
chain of release-acquire pairs do not provide this additional ordering,
which means that only those CPUs on the chain are guaranteed to agree
on the combined order of the accesses. For example, switching to C code
in deference to the ghost of Herman Hollerith:
int u, v, x, y, z;
void cpu0(void)
{
r0 = smp_load_acquire(&x);
WRITE_ONCE(u, 1);
smp_store_release(&y, 1);
}
void cpu1(void)
{
r1 = smp_load_acquire(&y);
r4 = READ_ONCE(v);
r5 = READ_ONCE(u);
smp_store_release(&z, 1);
}
void cpu2(void)
{
r2 = smp_load_acquire(&z);
smp_store_release(&x, 1);
}
void cpu3(void)
{
WRITE_ONCE(v, 1);
smp_mb();
r3 = READ_ONCE(u);
}
Because cpu0(), cpu1(), and cpu2() participate in a chain of
smp_store_release()/smp_load_acquire() pairs, the following outcome
is prohibited:
r0 == 1 && r1 == 1 && r2 == 1
Furthermore, because of the release-acquire relationship between cpu0()
and cpu1(), cpu1() must see cpu0()'s writes, so that the following
outcome is prohibited:
r1 == 1 && r5 == 0
However, the ordering provided by a release-acquire chain is local
to the CPUs participating in that chain and does not apply to cpu3(),
at least aside from stores. Therefore, the following outcome is possible:
r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0
As an aside, the following outcome is also possible:
r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0 && r5 == 1
Although cpu0(), cpu1(), and cpu2() will see their respective reads and
writes in order, CPUs not involved in the release-acquire chain might
well disagree on the order. This disagreement stems from the fact that
the weak memory-barrier instructions used to implement smp_load_acquire()
and smp_store_release() are not required to order prior stores against
subsequent loads in all cases. This means that cpu3() can see cpu0()'s
store to u as happening -after- cpu1()'s load from v, even though
both cpu0() and cpu1() agree that these two operations occurred in the
intended order.
However, please keep in mind that smp_load_acquire() is not magic.
In particular, it simply reads from its argument with ordering. It does
-not- ensure that any particular value will be read. Therefore, the
following outcome is possible:
r0 == 0 && r1 == 0 && r2 == 0 && r5 == 0
Note that this outcome can happen even on a mythical sequentially
consistent system where nothing is ever reordered.
To reiterate, if your code requires full ordering of all operations,
use general barriers throughout.
========================
EXPLICIT KERNEL BARRIERS
========================
The Linux kernel has a variety of different barriers that act at different
levels:
(*) Compiler barrier.
(*) CPU memory barriers.
COMPILER BARRIER
----------------
The Linux kernel has an explicit compiler barrier function that prevents the
compiler from moving the memory accesses either side of it to the other side:
barrier();
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'.)
(*) 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
--> --------------------
--> maximum size reached
--> --------------------
