| This document contains brief definitions of LKMM-related terms. Like most |
| glossaries, it is not intended to be read front to back (except perhaps |
| as a way of confirming a diagnosis of OCD), but rather to be searched |
| for specific terms. |
| |
| |
| Address Dependency: When the address of a later memory access is computed |
| based on the value returned by an earlier load, an "address |
| dependency" extends from that load extending to the later access. |
| Address dependencies are quite common in RCU read-side critical |
| sections: |
| |
| 1 rcu_read_lock(); |
| 2 p = rcu_dereference(gp); |
| 3 do_something(p->a); |
| 4 rcu_read_unlock(); |
| |
| In this case, because the address of "p->a" on line 3 is computed |
| from the value returned by the rcu_dereference() on line 2, the |
| address dependency extends from that rcu_dereference() to that |
| "p->a". In rare cases, optimizing compilers can destroy address |
| dependencies. Please see Documentation/RCU/rcu_dereference.rst |
| for more information. |
| |
| See also "Control Dependency" and "Data Dependency". |
| |
| Acquire: With respect to a lock, acquiring that lock, for example, |
| using spin_lock(). With respect to a non-lock shared variable, |
| a special operation that includes a load and which orders that |
| load before later memory references running on that same CPU. |
| An example special acquire operation is smp_load_acquire(), |
| but atomic_read_acquire() and atomic_xchg_acquire() also include |
| acquire loads. |
| |
| When an acquire load returns the value stored by a release store |
| to that same variable, (in other words, the acquire load "reads |
| from" the release store), then all operations preceding that |
| store "happen before" any operations following that load acquire. |
| |
| See also "Happens-Before", "Reads-From", "Relaxed", and "Release". |
| |
| Coherence (co): When one CPU's store to a given variable overwrites |
| either the value from another CPU's store or some later value, |
| there is said to be a coherence link from the second CPU to |
| the first. |
| |
| It is also possible to have a coherence link within a CPU, which |
| is a "coherence internal" (coi) link. The term "coherence |
| external" (coe) link is used when it is necessary to exclude |
| the coi case. |
| |
| See also "From-reads" and "Reads-from". |
| |
| Control Dependency: When a later store's execution depends on a test |
| of a value computed from a value returned by an earlier load, |
| a "control dependency" extends from that load to that store. |
| For example: |
| |
| 1 if (READ_ONCE(x)) |
| 2 WRITE_ONCE(y, 1); |
| |
| Here, the control dependency extends from the READ_ONCE() on |
| line 1 to the WRITE_ONCE() on line 2. Control dependencies are |
| fragile, and can be easily destroyed by optimizing compilers. |
| Please see control-dependencies.txt for more information. |
| |
| See also "Address Dependency" and "Data Dependency". |
| |
| Cycle: Memory-barrier pairing is restricted to a pair of CPUs, as the |
| name suggests. And in a great many cases, a pair of CPUs is all |
| that is required. In other cases, the notion of pairing must be |
| extended to additional CPUs, and the result is called a "cycle". |
| In a cycle, each CPU's ordering interacts with that of the next: |
| |
| CPU 0 CPU 1 CPU 2 |
| WRITE_ONCE(x, 1); WRITE_ONCE(y, 1); WRITE_ONCE(z, 1); |
| smp_mb(); smp_mb(); smp_mb(); |
| r0 = READ_ONCE(y); r1 = READ_ONCE(z); r2 = READ_ONCE(x); |
| |
| CPU 0's smp_mb() interacts with that of CPU 1, which interacts |
| with that of CPU 2, which in turn interacts with that of CPU 0 |
| to complete the cycle. Because of the smp_mb() calls between |
| each pair of memory accesses, the outcome where r0, r1, and r2 |
| are all equal to zero is forbidden by LKMM. |
| |
| See also "Pairing". |
| |
| Data Dependency: When the data written by a later store is computed based |
| on the value returned by an earlier load, a "data dependency" |
| extends from that load to that later store. For example: |
| |
| 1 r1 = READ_ONCE(x); |
| 2 WRITE_ONCE(y, r1 + 1); |
| |
| In this case, the data dependency extends from the READ_ONCE() |
| on line 1 to the WRITE_ONCE() on line 2. Data dependencies are |
| fragile and can be easily destroyed by optimizing compilers. |
| Because optimizing compilers put a great deal of effort into |
| working out what values integer variables might have, this is |
| especially true in cases where the dependency is carried through |
| an integer. |
| |
| See also "Address Dependency" and "Control Dependency". |
| |
| From-Reads (fr): When one CPU's store to a given variable happened |
| too late to affect the value returned by another CPU's |
| load from that same variable, there is said to be a from-reads |
| link from the load to the store. |
| |
| It is also possible to have a from-reads link within a CPU, which |
| is a "from-reads internal" (fri) link. The term "from-reads |
| external" (fre) link is used when it is necessary to exclude |
| the fri case. |
| |
| See also "Coherence" and "Reads-from". |
| |
| Fully Ordered: An operation such as smp_mb() that orders all of |
| its CPU's prior accesses with all of that CPU's subsequent |
| accesses, or a marked access such as atomic_add_return() |
| that orders all of its CPU's prior accesses, itself, and |
| all of its CPU's subsequent accesses. |
| |
| Happens-Before (hb): A relation between two accesses in which LKMM |
| guarantees the first access precedes the second. For more |
| detail, please see the "THE HAPPENS-BEFORE RELATION: hb" |
| section of explanation.txt. |
| |
| Marked Access: An access to a variable that uses an special function or |
| macro such as "r1 = READ_ONCE(x)" or "smp_store_release(&a, 1)". |
| |
| See also "Unmarked Access". |
| |
| Pairing: "Memory-barrier pairing" reflects the fact that synchronizing |
| data between two CPUs requires that both CPUs their accesses. |
| Memory barriers thus tend to come in pairs, one executed by |
| one of the CPUs and the other by the other CPU. Of course, |
| pairing also occurs with other types of operations, so that a |
| smp_store_release() pairs with an smp_load_acquire() that reads |
| the value stored. |
| |
| See also "Cycle". |
| |
| Reads-From (rf): When one CPU's load returns the value stored by some other |
| CPU, there is said to be a reads-from link from the second |
| CPU's store to the first CPU's load. Reads-from links have the |
| nice property that time must advance from the store to the load, |
| which means that algorithms using reads-from links can use lighter |
| weight ordering and synchronization compared to algorithms using |
| coherence and from-reads links. |
| |
| It is also possible to have a reads-from link within a CPU, which |
| is a "reads-from internal" (rfi) link. The term "reads-from |
| external" (rfe) link is used when it is necessary to exclude |
| the rfi case. |
| |
| See also Coherence" and "From-reads". |
| |
| Relaxed: A marked access that does not imply ordering, for example, a |
| READ_ONCE(), WRITE_ONCE(), a non-value-returning read-modify-write |
| operation, or a value-returning read-modify-write operation whose |
| name ends in "_relaxed". |
| |
| See also "Acquire" and "Release". |
| |
| Release: With respect to a lock, releasing that lock, for example, |
| using spin_unlock(). With respect to a non-lock shared variable, |
| a special operation that includes a store and which orders that |
| store after earlier memory references that ran on that same CPU. |
| An example special release store is smp_store_release(), but |
| atomic_set_release() and atomic_cmpxchg_release() also include |
| release stores. |
| |
| See also "Acquire" and "Relaxed". |
| |
| Unmarked Access: An access to a variable that uses normal C-language |
| syntax, for example, "a = b[2]"; |
| |
| See also "Marked Access". |
