glossary.txt (7457B)
1This document contains brief definitions of LKMM-related terms. Like most 2glossaries, it is not intended to be read front to back (except perhaps 3as a way of confirming a diagnosis of OCD), but rather to be searched 4for specific terms. 5 6 7Address Dependency: When the address of a later memory access is computed 8 based on the value returned by an earlier load, an "address 9 dependency" extends from that load extending to the later access. 10 Address dependencies are quite common in RCU read-side critical 11 sections: 12 13 1 rcu_read_lock(); 14 2 p = rcu_dereference(gp); 15 3 do_something(p->a); 16 4 rcu_read_unlock(); 17 18 In this case, because the address of "p->a" on line 3 is computed 19 from the value returned by the rcu_dereference() on line 2, the 20 address dependency extends from that rcu_dereference() to that 21 "p->a". In rare cases, optimizing compilers can destroy address 22 dependencies. Please see Documentation/RCU/rcu_dereference.rst 23 for more information. 24 25 See also "Control Dependency" and "Data Dependency". 26 27Acquire: With respect to a lock, acquiring that lock, for example, 28 using spin_lock(). With respect to a non-lock shared variable, 29 a special operation that includes a load and which orders that 30 load before later memory references running on that same CPU. 31 An example special acquire operation is smp_load_acquire(), 32 but atomic_read_acquire() and atomic_xchg_acquire() also include 33 acquire loads. 34 35 When an acquire load returns the value stored by a release store 36 to that same variable, (in other words, the acquire load "reads 37 from" the release store), then all operations preceding that 38 store "happen before" any operations following that load acquire. 39 40 See also "Happens-Before", "Reads-From", "Relaxed", and "Release". 41 42Coherence (co): When one CPU's store to a given variable overwrites 43 either the value from another CPU's store or some later value, 44 there is said to be a coherence link from the second CPU to 45 the first. 46 47 It is also possible to have a coherence link within a CPU, which 48 is a "coherence internal" (coi) link. The term "coherence 49 external" (coe) link is used when it is necessary to exclude 50 the coi case. 51 52 See also "From-reads" and "Reads-from". 53 54Control Dependency: When a later store's execution depends on a test 55 of a value computed from a value returned by an earlier load, 56 a "control dependency" extends from that load to that store. 57 For example: 58 59 1 if (READ_ONCE(x)) 60 2 WRITE_ONCE(y, 1); 61 62 Here, the control dependency extends from the READ_ONCE() on 63 line 1 to the WRITE_ONCE() on line 2. Control dependencies are 64 fragile, and can be easily destroyed by optimizing compilers. 65 Please see control-dependencies.txt for more information. 66 67 See also "Address Dependency" and "Data Dependency". 68 69Cycle: Memory-barrier pairing is restricted to a pair of CPUs, as the 70 name suggests. And in a great many cases, a pair of CPUs is all 71 that is required. In other cases, the notion of pairing must be 72 extended to additional CPUs, and the result is called a "cycle". 73 In a cycle, each CPU's ordering interacts with that of the next: 74 75 CPU 0 CPU 1 CPU 2 76 WRITE_ONCE(x, 1); WRITE_ONCE(y, 1); WRITE_ONCE(z, 1); 77 smp_mb(); smp_mb(); smp_mb(); 78 r0 = READ_ONCE(y); r1 = READ_ONCE(z); r2 = READ_ONCE(x); 79 80 CPU 0's smp_mb() interacts with that of CPU 1, which interacts 81 with that of CPU 2, which in turn interacts with that of CPU 0 82 to complete the cycle. Because of the smp_mb() calls between 83 each pair of memory accesses, the outcome where r0, r1, and r2 84 are all equal to zero is forbidden by LKMM. 85 86 See also "Pairing". 87 88Data Dependency: When the data written by a later store is computed based 89 on the value returned by an earlier load, a "data dependency" 90 extends from that load to that later store. For example: 91 92 1 r1 = READ_ONCE(x); 93 2 WRITE_ONCE(y, r1 + 1); 94 95 In this case, the data dependency extends from the READ_ONCE() 96 on line 1 to the WRITE_ONCE() on line 2. Data dependencies are 97 fragile and can be easily destroyed by optimizing compilers. 98 Because optimizing compilers put a great deal of effort into 99 working out what values integer variables might have, this is 100 especially true in cases where the dependency is carried through 101 an integer. 102 103 See also "Address Dependency" and "Control Dependency". 104 105From-Reads (fr): When one CPU's store to a given variable happened 106 too late to affect the value returned by another CPU's 107 load from that same variable, there is said to be a from-reads 108 link from the load to the store. 109 110 It is also possible to have a from-reads link within a CPU, which 111 is a "from-reads internal" (fri) link. The term "from-reads 112 external" (fre) link is used when it is necessary to exclude 113 the fri case. 114 115 See also "Coherence" and "Reads-from". 116 117Fully Ordered: An operation such as smp_mb() that orders all of 118 its CPU's prior accesses with all of that CPU's subsequent 119 accesses, or a marked access such as atomic_add_return() 120 that orders all of its CPU's prior accesses, itself, and 121 all of its CPU's subsequent accesses. 122 123Happens-Before (hb): A relation between two accesses in which LKMM 124 guarantees the first access precedes the second. For more 125 detail, please see the "THE HAPPENS-BEFORE RELATION: hb" 126 section of explanation.txt. 127 128Marked Access: An access to a variable that uses an special function or 129 macro such as "r1 = READ_ONCE(x)" or "smp_store_release(&a, 1)". 130 131 See also "Unmarked Access". 132 133Pairing: "Memory-barrier pairing" reflects the fact that synchronizing 134 data between two CPUs requires that both CPUs their accesses. 135 Memory barriers thus tend to come in pairs, one executed by 136 one of the CPUs and the other by the other CPU. Of course, 137 pairing also occurs with other types of operations, so that a 138 smp_store_release() pairs with an smp_load_acquire() that reads 139 the value stored. 140 141 See also "Cycle". 142 143Reads-From (rf): When one CPU's load returns the value stored by some other 144 CPU, there is said to be a reads-from link from the second 145 CPU's store to the first CPU's load. Reads-from links have the 146 nice property that time must advance from the store to the load, 147 which means that algorithms using reads-from links can use lighter 148 weight ordering and synchronization compared to algorithms using 149 coherence and from-reads links. 150 151 It is also possible to have a reads-from link within a CPU, which 152 is a "reads-from internal" (rfi) link. The term "reads-from 153 external" (rfe) link is used when it is necessary to exclude 154 the rfi case. 155 156 See also Coherence" and "From-reads". 157 158Relaxed: A marked access that does not imply ordering, for example, a 159 READ_ONCE(), WRITE_ONCE(), a non-value-returning read-modify-write 160 operation, or a value-returning read-modify-write operation whose 161 name ends in "_relaxed". 162 163 See also "Acquire" and "Release". 164 165Release: With respect to a lock, releasing that lock, for example, 166 using spin_unlock(). With respect to a non-lock shared variable, 167 a special operation that includes a store and which orders that 168 store after earlier memory references that ran on that same CPU. 169 An example special release store is smp_store_release(), but 170 atomic_set_release() and atomic_cmpxchg_release() also include 171 release stores. 172 173 See also "Acquire" and "Relaxed". 174 175Unmarked Access: An access to a variable that uses normal C-language 176 syntax, for example, "a = b[2]"; 177 178 See also "Marked Access".