0001 This document contains brief definitions of LKMM-related terms. Like most
0002 glossaries, it is not intended to be read front to back (except perhaps
0003 as a way of confirming a diagnosis of OCD), but rather to be searched
0004 for specific terms.
0005
0006
0007 Address Dependency: When the address of a later memory access is computed
0008 based on the value returned by an earlier load, an "address
0009 dependency" extends from that load extending to the later access.
0010 Address dependencies are quite common in RCU read-side critical
0011 sections:
0012
0013 1 rcu_read_lock();
0014 2 p = rcu_dereference(gp);
0015 3 do_something(p->a);
0016 4 rcu_read_unlock();
0017
0018 In this case, because the address of "p->a" on line 3 is computed
0019 from the value returned by the rcu_dereference() on line 2, the
0020 address dependency extends from that rcu_dereference() to that
0021 "p->a". In rare cases, optimizing compilers can destroy address
0022 dependencies. Please see Documentation/RCU/rcu_dereference.rst
0023 for more information.
0024
0025 See also "Control Dependency" and "Data Dependency".
0026
0027 Acquire: With respect to a lock, acquiring that lock, for example,
0028 using spin_lock(). With respect to a non-lock shared variable,
0029 a special operation that includes a load and which orders that
0030 load before later memory references running on that same CPU.
0031 An example special acquire operation is smp_load_acquire(),
0032 but atomic_read_acquire() and atomic_xchg_acquire() also include
0033 acquire loads.
0034
0035 When an acquire load returns the value stored by a release store
0036 to that same variable, (in other words, the acquire load "reads
0037 from" the release store), then all operations preceding that
0038 store "happen before" any operations following that load acquire.
0039
0040 See also "Happens-Before", "Reads-From", "Relaxed", and "Release".
0041
0042 Coherence (co): When one CPU's store to a given variable overwrites
0043 either the value from another CPU's store or some later value,
0044 there is said to be a coherence link from the second CPU to
0045 the first.
0046
0047 It is also possible to have a coherence link within a CPU, which
0048 is a "coherence internal" (coi) link. The term "coherence
0049 external" (coe) link is used when it is necessary to exclude
0050 the coi case.
0051
0052 See also "From-reads" and "Reads-from".
0053
0054 Control Dependency: When a later store's execution depends on a test
0055 of a value computed from a value returned by an earlier load,
0056 a "control dependency" extends from that load to that store.
0057 For example:
0058
0059 1 if (READ_ONCE(x))
0060 2 WRITE_ONCE(y, 1);
0061
0062 Here, the control dependency extends from the READ_ONCE() on
0063 line 1 to the WRITE_ONCE() on line 2. Control dependencies are
0064 fragile, and can be easily destroyed by optimizing compilers.
0065 Please see control-dependencies.txt for more information.
0066
0067 See also "Address Dependency" and "Data Dependency".
0068
0069 Cycle: Memory-barrier pairing is restricted to a pair of CPUs, as the
0070 name suggests. And in a great many cases, a pair of CPUs is all
0071 that is required. In other cases, the notion of pairing must be
0072 extended to additional CPUs, and the result is called a "cycle".
0073 In a cycle, each CPU's ordering interacts with that of the next:
0074
0075 CPU 0 CPU 1 CPU 2
0076 WRITE_ONCE(x, 1); WRITE_ONCE(y, 1); WRITE_ONCE(z, 1);
0077 smp_mb(); smp_mb(); smp_mb();
0078 r0 = READ_ONCE(y); r1 = READ_ONCE(z); r2 = READ_ONCE(x);
0079
0080 CPU 0's smp_mb() interacts with that of CPU 1, which interacts
0081 with that of CPU 2, which in turn interacts with that of CPU 0
0082 to complete the cycle. Because of the smp_mb() calls between
0083 each pair of memory accesses, the outcome where r0, r1, and r2
0084 are all equal to zero is forbidden by LKMM.
0085
0086 See also "Pairing".
0087
0088 Data Dependency: When the data written by a later store is computed based
0089 on the value returned by an earlier load, a "data dependency"
0090 extends from that load to that later store. For example:
0091
0092 1 r1 = READ_ONCE(x);
0093 2 WRITE_ONCE(y, r1 + 1);
0094
0095 In this case, the data dependency extends from the READ_ONCE()
0096 on line 1 to the WRITE_ONCE() on line 2. Data dependencies are
0097 fragile and can be easily destroyed by optimizing compilers.
0098 Because optimizing compilers put a great deal of effort into
0099 working out what values integer variables might have, this is
0100 especially true in cases where the dependency is carried through
0101 an integer.
0102
0103 See also "Address Dependency" and "Control Dependency".
0104
0105 From-Reads (fr): When one CPU's store to a given variable happened
0106 too late to affect the value returned by another CPU's
0107 load from that same variable, there is said to be a from-reads
0108 link from the load to the store.
0109
0110 It is also possible to have a from-reads link within a CPU, which
0111 is a "from-reads internal" (fri) link. The term "from-reads
0112 external" (fre) link is used when it is necessary to exclude
0113 the fri case.
0114
0115 See also "Coherence" and "Reads-from".
0116
0117 Fully Ordered: An operation such as smp_mb() that orders all of
0118 its CPU's prior accesses with all of that CPU's subsequent
0119 accesses, or a marked access such as atomic_add_return()
0120 that orders all of its CPU's prior accesses, itself, and
0121 all of its CPU's subsequent accesses.
0122
0123 Happens-Before (hb): A relation between two accesses in which LKMM
0124 guarantees the first access precedes the second. For more
0125 detail, please see the "THE HAPPENS-BEFORE RELATION: hb"
0126 section of explanation.txt.
0127
0128 Marked Access: An access to a variable that uses an special function or
0129 macro such as "r1 = READ_ONCE(x)" or "smp_store_release(&a, 1)".
0130
0131 See also "Unmarked Access".
0132
0133 Pairing: "Memory-barrier pairing" reflects the fact that synchronizing
0134 data between two CPUs requires that both CPUs their accesses.
0135 Memory barriers thus tend to come in pairs, one executed by
0136 one of the CPUs and the other by the other CPU. Of course,
0137 pairing also occurs with other types of operations, so that a
0138 smp_store_release() pairs with an smp_load_acquire() that reads
0139 the value stored.
0140
0141 See also "Cycle".
0142
0143 Reads-From (rf): When one CPU's load returns the value stored by some other
0144 CPU, there is said to be a reads-from link from the second
0145 CPU's store to the first CPU's load. Reads-from links have the
0146 nice property that time must advance from the store to the load,
0147 which means that algorithms using reads-from links can use lighter
0148 weight ordering and synchronization compared to algorithms using
0149 coherence and from-reads links.
0150
0151 It is also possible to have a reads-from link within a CPU, which
0152 is a "reads-from internal" (rfi) link. The term "reads-from
0153 external" (rfe) link is used when it is necessary to exclude
0154 the rfi case.
0155
0156 See also Coherence" and "From-reads".
0157
0158 Relaxed: A marked access that does not imply ordering, for example, a
0159 READ_ONCE(), WRITE_ONCE(), a non-value-returning read-modify-write
0160 operation, or a value-returning read-modify-write operation whose
0161 name ends in "_relaxed".
0162
0163 See also "Acquire" and "Release".
0164
0165 Release: With respect to a lock, releasing that lock, for example,
0166 using spin_unlock(). With respect to a non-lock shared variable,
0167 a special operation that includes a store and which orders that
0168 store after earlier memory references that ran on that same CPU.
0169 An example special release store is smp_store_release(), but
0170 atomic_set_release() and atomic_cmpxchg_release() also include
0171 release stores.
0172
0173 See also "Acquire" and "Relaxed".
0174
0175 Unmarked Access: An access to a variable that uses normal C-language
0176 syntax, for example, "a = b[2]";
0177
0178 See also "Marked Access".
