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.txt
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, then all operations preceding that store
37	happen before any operations following that load acquire.
38
39	See also "Relaxed" and "Release".
40
41Coherence (co):  When one CPU's store to a given variable overwrites
42	either the value from another CPU's store or some later value,
43	there is said to be a coherence link from the second CPU to
44	the first.
45
46	It is also possible to have a coherence link within a CPU, which
47	is a "coherence internal" (coi) link.  The term "coherence
48	external" (coe) link is used when it is necessary to exclude
49	the coi case.
50
51	See also "From-reads" and "Reads-from".
52
53Control Dependency:  When a later store's execution depends on a test
54	of a value computed from a value returned by an earlier load,
55	a "control dependency" extends from that load to that store.
56	For example:
57
58	 1 if (READ_ONCE(x))
59	 2   WRITE_ONCE(y, 1);
60
61	 Here, the control dependency extends from the READ_ONCE() on
62	 line 1 to the WRITE_ONCE() on line 2.	Control dependencies are
63	 fragile, and can be easily destroyed by optimizing compilers.
64	 Please see control-dependencies.txt for more information.
65
66	 See also "Address Dependency" and "Data Dependency".
67
68Cycle:	Memory-barrier pairing is restricted to a pair of CPUs, as the
69	name suggests.	And in a great many cases, a pair of CPUs is all
70	that is required.  In other cases, the notion of pairing must be
71	extended to additional CPUs, and the result is called a "cycle".
72	In a cycle, each CPU's ordering interacts with that of the next:
73
74	CPU 0                CPU 1                CPU 2
75	WRITE_ONCE(x, 1);    WRITE_ONCE(y, 1);    WRITE_ONCE(z, 1);
76	smp_mb();            smp_mb();            smp_mb();
77	r0 = READ_ONCE(y);   r1 = READ_ONCE(z);   r2 = READ_ONCE(x);
78
79	CPU 0's smp_mb() interacts with that of CPU 1, which interacts
80	with that of CPU 2, which in turn interacts with that of CPU 0
81	to complete the cycle.	Because of the smp_mb() calls between
82	each pair of memory accesses, the outcome where r0, r1, and r2
83	are all equal to zero is forbidden by LKMM.
84
85	See also "Pairing".
86
87Data Dependency:  When the data written by a later store is computed based
88	on the value returned by an earlier load, a "data dependency"
89	extends from that load to that later store.  For example:
90
91	 1 r1 = READ_ONCE(x);
92	 2 WRITE_ONCE(y, r1 + 1);
93
94	In this case, the data dependency extends from the READ_ONCE()
95	on line 1 to the WRITE_ONCE() on line 2.  Data dependencies are
96	fragile and can be easily destroyed by optimizing compilers.
97	Because optimizing compilers put a great deal of effort into
98	working out what values integer variables might have, this is
99	especially true in cases where the dependency is carried through
100	an integer.
101
102	See also "Address Dependency" and "Control Dependency".
103
104From-Reads (fr):  When one CPU's store to a given variable happened
105	too late to affect the value returned by another CPU's
106	load from that same variable, there is said to be a from-reads
107	link from the load to the store.
108
109	It is also possible to have a from-reads link within a CPU, which
110	is a "from-reads internal" (fri) link.  The term "from-reads
111	external" (fre) link is used when it is necessary to exclude
112	the fri case.
113
114	See also "Coherence" and "Reads-from".
115
116Fully Ordered:  An operation such as smp_mb() that orders all of
117	its CPU's prior accesses with all of that CPU's subsequent
118	accesses, or a marked access such as atomic_add_return()
119	that orders all of its CPU's prior accesses, itself, and
120	all of its CPU's subsequent accesses.
121
122Marked Access:  An access to a variable that uses an special function or
123	macro such as "r1 = READ_ONCE(x)" or "smp_store_release(&a, 1)".
124
125	See also "Unmarked Access".
126
127Pairing: "Memory-barrier pairing" reflects the fact that synchronizing
128	data between two CPUs requires that both CPUs their accesses.
129	Memory barriers thus tend to come in pairs, one executed by
130	one of the CPUs and the other by the other CPU.  Of course,
131	pairing also occurs with other types of operations, so that a
132	smp_store_release() pairs with an smp_load_acquire() that reads
133	the value stored.
134
135	See also "Cycle".
136
137Reads-From (rf):  When one CPU's load returns the value stored by some other
138	CPU, there is said to be a reads-from link from the second
139	CPU's store to the first CPU's load.  Reads-from links have the
140	nice property that time must advance from the store to the load,
141	which means that algorithms using reads-from links can use lighter
142	weight ordering and synchronization compared to algorithms using
143	coherence and from-reads links.
144
145	It is also possible to have a reads-from link within a CPU, which
146	is a "reads-from internal" (rfi) link.	The term "reads-from
147	external" (rfe) link is used when it is necessary to exclude
148	the rfi case.
149
150	See also Coherence" and "From-reads".
151
152Relaxed:  A marked access that does not imply ordering, for example, a
153	READ_ONCE(), WRITE_ONCE(), a non-value-returning read-modify-write
154	operation, or a value-returning read-modify-write operation whose
155	name ends in "_relaxed".
156
157	See also "Acquire" and "Release".
158
159Release:  With respect to a lock, releasing that lock, for example,
160	using spin_unlock().  With respect to a non-lock shared variable,
161	a special operation that includes a store and which orders that
162	store after earlier memory references that ran on that same CPU.
163	An example special release store is smp_store_release(), but
164	atomic_set_release() and atomic_cmpxchg_release() also include
165	release stores.
166
167	See also "Acquire" and "Relaxed".
168
169Unmarked Access:  An access to a variable that uses normal C-language
170	syntax, for example, "a = b[2]";
171
172	See also "Marked Access".
173