1.. _rcu_dereference_doc:
2
3PROPER CARE AND FEEDING OF RETURN VALUES FROM rcu_dereference()
4===============================================================
5
6Most of the time, you can use values from rcu_dereference() or one of
7the similar primitives without worries.  Dereferencing (prefix "*"),
8field selection ("->"), assignment ("="), address-of ("&"), addition and
9subtraction of constants, and casts all work quite naturally and safely.
10
11It is nevertheless possible to get into trouble with other operations.
12Follow these rules to keep your RCU code working properly:
13
14-	You must use one of the rcu_dereference() family of primitives
15	to load an RCU-protected pointer, otherwise CONFIG_PROVE_RCU
16	will complain.  Worse yet, your code can see random memory-corruption
17	bugs due to games that compilers and DEC Alpha can play.
18	Without one of the rcu_dereference() primitives, compilers
19	can reload the value, and won't your code have fun with two
20	different values for a single pointer!  Without rcu_dereference(),
21	DEC Alpha can load a pointer, dereference that pointer, and
22	return data preceding initialization that preceded the store of
23	the pointer.
24
25	In addition, the volatile cast in rcu_dereference() prevents the
26	compiler from deducing the resulting pointer value.  Please see
27	the section entitled "EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH"
28	for an example where the compiler can in fact deduce the exact
29	value of the pointer, and thus cause misordering.
30
31-	In the special case where data is added but is never removed
32	while readers are accessing the structure, READ_ONCE() may be used
33	instead of rcu_dereference().  In this case, use of READ_ONCE()
34	takes on the role of the lockless_dereference() primitive that
35	was removed in v4.15.
36
37-	You are only permitted to use rcu_dereference on pointer values.
38	The compiler simply knows too much about integral values to
39	trust it to carry dependencies through integer operations.
40	There are a very few exceptions, namely that you can temporarily
41	cast the pointer to uintptr_t in order to:
42
43	-	Set bits and clear bits down in the must-be-zero low-order
44		bits of that pointer.  This clearly means that the pointer
45		must have alignment constraints, for example, this does
46		-not- work in general for char* pointers.
47
48	-	XOR bits to translate pointers, as is done in some
49		classic buddy-allocator algorithms.
50
51	It is important to cast the value back to pointer before
52	doing much of anything else with it.
53
54-	Avoid cancellation when using the "+" and "-" infix arithmetic
55	operators.  For example, for a given variable "x", avoid
56	"(x-(uintptr_t)x)" for char* pointers.	The compiler is within its
57	rights to substitute zero for this sort of expression, so that
58	subsequent accesses no longer depend on the rcu_dereference(),
59	again possibly resulting in bugs due to misordering.
60
61	Of course, if "p" is a pointer from rcu_dereference(), and "a"
62	and "b" are integers that happen to be equal, the expression
63	"p+a-b" is safe because its value still necessarily depends on
64	the rcu_dereference(), thus maintaining proper ordering.
65
66-	If you are using RCU to protect JITed functions, so that the
67	"()" function-invocation operator is applied to a value obtained
68	(directly or indirectly) from rcu_dereference(), you may need to
69	interact directly with the hardware to flush instruction caches.
70	This issue arises on some systems when a newly JITed function is
71	using the same memory that was used by an earlier JITed function.
72
73-	Do not use the results from relational operators ("==", "!=",
74	">", ">=", "<", or "<=") when dereferencing.  For example,
75	the following (quite strange) code is buggy::
76
77		int *p;
78		int *q;
79
80		...
81
82		p = rcu_dereference(gp)
83		q = &global_q;
84		q += p > &oom_p;
85		r1 = *q;  /* BUGGY!!! */
86
87	As before, the reason this is buggy is that relational operators
88	are often compiled using branches.  And as before, although
89	weak-memory machines such as ARM or PowerPC do order stores
90	after such branches, but can speculate loads, which can again
91	result in misordering bugs.
92
93-	Be very careful about comparing pointers obtained from
94	rcu_dereference() against non-NULL values.  As Linus Torvalds
95	explained, if the two pointers are equal, the compiler could
96	substitute the pointer you are comparing against for the pointer
97	obtained from rcu_dereference().  For example::
98
99		p = rcu_dereference(gp);
100		if (p == &default_struct)
101			do_default(p->a);
102
103	Because the compiler now knows that the value of "p" is exactly
104	the address of the variable "default_struct", it is free to
105	transform this code into the following::
106
107		p = rcu_dereference(gp);
108		if (p == &default_struct)
109			do_default(default_struct.a);
110
111	On ARM and Power hardware, the load from "default_struct.a"
112	can now be speculated, such that it might happen before the
113	rcu_dereference().  This could result in bugs due to misordering.
114
115	However, comparisons are OK in the following cases:
116
117	-	The comparison was against the NULL pointer.  If the
118		compiler knows that the pointer is NULL, you had better
119		not be dereferencing it anyway.  If the comparison is
120		non-equal, the compiler is none the wiser.  Therefore,
121		it is safe to compare pointers from rcu_dereference()
122		against NULL pointers.
123
124	-	The pointer is never dereferenced after being compared.
125		Since there are no subsequent dereferences, the compiler
126		cannot use anything it learned from the comparison
127		to reorder the non-existent subsequent dereferences.
128		This sort of comparison occurs frequently when scanning
129		RCU-protected circular linked lists.
130
131		Note that if checks for being within an RCU read-side
132		critical section are not required and the pointer is never
133		dereferenced, rcu_access_pointer() should be used in place
134		of rcu_dereference().
135
136	-	The comparison is against a pointer that references memory
137		that was initialized "a long time ago."  The reason
138		this is safe is that even if misordering occurs, the
139		misordering will not affect the accesses that follow
140		the comparison.  So exactly how long ago is "a long
141		time ago"?  Here are some possibilities:
142
143		-	Compile time.
144
145		-	Boot time.
146
147		-	Module-init time for module code.
148
149		-	Prior to kthread creation for kthread code.
150
151		-	During some prior acquisition of the lock that
152			we now hold.
153
154		-	Before mod_timer() time for a timer handler.
155
156		There are many other possibilities involving the Linux
157		kernel's wide array of primitives that cause code to
158		be invoked at a later time.
159
160	-	The pointer being compared against also came from
161		rcu_dereference().  In this case, both pointers depend
162		on one rcu_dereference() or another, so you get proper
163		ordering either way.
164
165		That said, this situation can make certain RCU usage
166		bugs more likely to happen.  Which can be a good thing,
167		at least if they happen during testing.  An example
168		of such an RCU usage bug is shown in the section titled
169		"EXAMPLE OF AMPLIFIED RCU-USAGE BUG".
170
171	-	All of the accesses following the comparison are stores,
172		so that a control dependency preserves the needed ordering.
173		That said, it is easy to get control dependencies wrong.
174		Please see the "CONTROL DEPENDENCIES" section of
175		Documentation/memory-barriers.txt for more details.
176
177	-	The pointers are not equal -and- the compiler does
178		not have enough information to deduce the value of the
179		pointer.  Note that the volatile cast in rcu_dereference()
180		will normally prevent the compiler from knowing too much.
181
182		However, please note that if the compiler knows that the
183		pointer takes on only one of two values, a not-equal
184		comparison will provide exactly the information that the
185		compiler needs to deduce the value of the pointer.
186
187-	Disable any value-speculation optimizations that your compiler
188	might provide, especially if you are making use of feedback-based
189	optimizations that take data collected from prior runs.  Such
190	value-speculation optimizations reorder operations by design.
191
192	There is one exception to this rule:  Value-speculation
193	optimizations that leverage the branch-prediction hardware are
194	safe on strongly ordered systems (such as x86), but not on weakly
195	ordered systems (such as ARM or Power).  Choose your compiler
196	command-line options wisely!
197
198
199EXAMPLE OF AMPLIFIED RCU-USAGE BUG
200----------------------------------
201
202Because updaters can run concurrently with RCU readers, RCU readers can
203see stale and/or inconsistent values.  If RCU readers need fresh or
204consistent values, which they sometimes do, they need to take proper
205precautions.  To see this, consider the following code fragment::
206
207	struct foo {
208		int a;
209		int b;
210		int c;
211	};
212	struct foo *gp1;
213	struct foo *gp2;
214
215	void updater(void)
216	{
217		struct foo *p;
218
219		p = kmalloc(...);
220		if (p == NULL)
221			deal_with_it();
222		p->a = 42;  /* Each field in its own cache line. */
223		p->b = 43;
224		p->c = 44;
225		rcu_assign_pointer(gp1, p);
226		p->b = 143;
227		p->c = 144;
228		rcu_assign_pointer(gp2, p);
229	}
230
231	void reader(void)
232	{
233		struct foo *p;
234		struct foo *q;
235		int r1, r2;
236
237		p = rcu_dereference(gp2);
238		if (p == NULL)
239			return;
240		r1 = p->b;  /* Guaranteed to get 143. */
241		q = rcu_dereference(gp1);  /* Guaranteed non-NULL. */
242		if (p == q) {
243			/* The compiler decides that q->c is same as p->c. */
244			r2 = p->c; /* Could get 44 on weakly order system. */
245		}
246		do_something_with(r1, r2);
247	}
248
249You might be surprised that the outcome (r1 == 143 && r2 == 44) is possible,
250but you should not be.  After all, the updater might have been invoked
251a second time between the time reader() loaded into "r1" and the time
252that it loaded into "r2".  The fact that this same result can occur due
253to some reordering from the compiler and CPUs is beside the point.
254
255But suppose that the reader needs a consistent view?
256
257Then one approach is to use locking, for example, as follows::
258
259	struct foo {
260		int a;
261		int b;
262		int c;
263		spinlock_t lock;
264	};
265	struct foo *gp1;
266	struct foo *gp2;
267
268	void updater(void)
269	{
270		struct foo *p;
271
272		p = kmalloc(...);
273		if (p == NULL)
274			deal_with_it();
275		spin_lock(&p->lock);
276		p->a = 42;  /* Each field in its own cache line. */
277		p->b = 43;
278		p->c = 44;
279		spin_unlock(&p->lock);
280		rcu_assign_pointer(gp1, p);
281		spin_lock(&p->lock);
282		p->b = 143;
283		p->c = 144;
284		spin_unlock(&p->lock);
285		rcu_assign_pointer(gp2, p);
286	}
287
288	void reader(void)
289	{
290		struct foo *p;
291		struct foo *q;
292		int r1, r2;
293
294		p = rcu_dereference(gp2);
295		if (p == NULL)
296			return;
297		spin_lock(&p->lock);
298		r1 = p->b;  /* Guaranteed to get 143. */
299		q = rcu_dereference(gp1);  /* Guaranteed non-NULL. */
300		if (p == q) {
301			/* The compiler decides that q->c is same as p->c. */
302			r2 = p->c; /* Locking guarantees r2 == 144. */
303		}
304		spin_unlock(&p->lock);
305		do_something_with(r1, r2);
306	}
307
308As always, use the right tool for the job!
309
310
311EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH
312-----------------------------------------
313
314If a pointer obtained from rcu_dereference() compares not-equal to some
315other pointer, the compiler normally has no clue what the value of the
316first pointer might be.  This lack of knowledge prevents the compiler
317from carrying out optimizations that otherwise might destroy the ordering
318guarantees that RCU depends on.  And the volatile cast in rcu_dereference()
319should prevent the compiler from guessing the value.
320
321But without rcu_dereference(), the compiler knows more than you might
322expect.  Consider the following code fragment::
323
324	struct foo {
325		int a;
326		int b;
327	};
328	static struct foo variable1;
329	static struct foo variable2;
330	static struct foo *gp = &variable1;
331
332	void updater(void)
333	{
334		initialize_foo(&variable2);
335		rcu_assign_pointer(gp, &variable2);
336		/*
337		 * The above is the only store to gp in this translation unit,
338		 * and the address of gp is not exported in any way.
339		 */
340	}
341
342	int reader(void)
343	{
344		struct foo *p;
345
346		p = gp;
347		barrier();
348		if (p == &variable1)
349			return p->a; /* Must be variable1.a. */
350		else
351			return p->b; /* Must be variable2.b. */
352	}
353
354Because the compiler can see all stores to "gp", it knows that the only
355possible values of "gp" are "variable1" on the one hand and "variable2"
356on the other.  The comparison in reader() therefore tells the compiler
357the exact value of "p" even in the not-equals case.  This allows the
358compiler to make the return values independent of the load from "gp",
359in turn destroying the ordering between this load and the loads of the
360return values.  This can result in "p->b" returning pre-initialization
361garbage values.
362
363In short, rcu_dereference() is -not- optional when you are going to
364dereference the resulting pointer.
365
366
367WHICH MEMBER OF THE rcu_dereference() FAMILY SHOULD YOU USE?
368------------------------------------------------------------
369
370First, please avoid using rcu_dereference_raw() and also please avoid
371using rcu_dereference_check() and rcu_dereference_protected() with a
372second argument with a constant value of 1 (or true, for that matter).
373With that caution out of the way, here is some guidance for which
374member of the rcu_dereference() to use in various situations:
375
3761.	If the access needs to be within an RCU read-side critical
377	section, use rcu_dereference().  With the new consolidated
378	RCU flavors, an RCU read-side critical section is entered
379	using rcu_read_lock(), anything that disables bottom halves,
380	anything that disables interrupts, or anything that disables
381	preemption.
382
3832.	If the access might be within an RCU read-side critical section
384	on the one hand, or protected by (say) my_lock on the other,
385	use rcu_dereference_check(), for example::
386
387		p1 = rcu_dereference_check(p->rcu_protected_pointer,
388					   lockdep_is_held(&my_lock));
389
390
3913.	If the access might be within an RCU read-side critical section
392	on the one hand, or protected by either my_lock or your_lock on
393	the other, again use rcu_dereference_check(), for example::
394
395		p1 = rcu_dereference_check(p->rcu_protected_pointer,
396					   lockdep_is_held(&my_lock) ||
397					   lockdep_is_held(&your_lock));
398
3994.	If the access is on the update side, so that it is always protected
400	by my_lock, use rcu_dereference_protected()::
401
402		p1 = rcu_dereference_protected(p->rcu_protected_pointer,
403					       lockdep_is_held(&my_lock));
404
405	This can be extended to handle multiple locks as in #3 above,
406	and both can be extended to check other conditions as well.
407
4085.	If the protection is supplied by the caller, and is thus unknown
409	to this code, that is the rare case when rcu_dereference_raw()
410	is appropriate.  In addition, rcu_dereference_raw() might be
411	appropriate when the lockdep expression would be excessively
412	complex, except that a better approach in that case might be to
413	take a long hard look at your synchronization design.  Still,
414	there are data-locking cases where any one of a very large number
415	of locks or reference counters suffices to protect the pointer,
416	so rcu_dereference_raw() does have its place.
417
418	However, its place is probably quite a bit smaller than one
419	might expect given the number of uses in the current kernel.
420	Ditto for its synonym, rcu_dereference_check( ... , 1), and
421	its close relative, rcu_dereference_protected(... , 1).
422
423
424SPARSE CHECKING OF RCU-PROTECTED POINTERS
425-----------------------------------------
426
427The sparse static-analysis tool checks for direct access to RCU-protected
428pointers, which can result in "interesting" bugs due to compiler
429optimizations involving invented loads and perhaps also load tearing.
430For example, suppose someone mistakenly does something like this::
431
432	p = q->rcu_protected_pointer;
433	do_something_with(p->a);
434	do_something_else_with(p->b);
435
436If register pressure is high, the compiler might optimize "p" out
437of existence, transforming the code to something like this::
438
439	do_something_with(q->rcu_protected_pointer->a);
440	do_something_else_with(q->rcu_protected_pointer->b);
441
442This could fatally disappoint your code if q->rcu_protected_pointer
443changed in the meantime.  Nor is this a theoretical problem:  Exactly
444this sort of bug cost Paul E. McKenney (and several of his innocent
445colleagues) a three-day weekend back in the early 1990s.
446
447Load tearing could of course result in dereferencing a mashup of a pair
448of pointers, which also might fatally disappoint your code.
449
450These problems could have been avoided simply by making the code instead
451read as follows::
452
453	p = rcu_dereference(q->rcu_protected_pointer);
454	do_something_with(p->a);
455	do_something_else_with(p->b);
456
457Unfortunately, these sorts of bugs can be extremely hard to spot during
458review.  This is where the sparse tool comes into play, along with the
459"__rcu" marker.  If you mark a pointer declaration, whether in a structure
460or as a formal parameter, with "__rcu", which tells sparse to complain if
461this pointer is accessed directly.  It will also cause sparse to complain
462if a pointer not marked with "__rcu" is accessed using rcu_dereference()
463and friends.  For example, ->rcu_protected_pointer might be declared as
464follows::
465
466	struct foo __rcu *rcu_protected_pointer;
467
468Use of "__rcu" is opt-in.  If you choose not to use it, then you should
469ignore the sparse warnings.
470