1 MARKING SHARED-MEMORY ACCESSES
2 ==============================
3
4 This document provides guidelines for marking
5 normal accesses to shared memory, that is "nor
6 not use read-modify-write atomic operations.
7 document these accesses, both with comments an
8 processed by the Kernel Concurrency Sanitizer
9 builds on an earlier LWN article [1] and Linux
10 session [2].
11
12
13 ACCESS-MARKING OPTIONS
14 ======================
15
16 The Linux kernel provides the following access
17
18 1. Plain C-language accesses (unmarked),
19
20 2. Data-race marking, for example, "data_
21
22 3. READ_ONCE(), for example, "a = READ_ON
23 The various forms of atomic_read() als
24
25 4. WRITE_ONCE(), for example, "WRITE_ONCE
26 The various forms of atomic_set() also
27
28 5. __data_racy, for example "int __data_r
29
30 6. KCSAN's negative-marking assertions, A
31 and ASSERT_EXCLUSIVE_WRITER(), are des
32 "ACCESS-DOCUMENTATION OPTIONS" section
33
34 These may be used in combination, as shown in
35 example:
36
37 WRITE_ONCE(a, b + data_race(c + d) + R
38
39 Neither plain C-language accesses nor data_rac
40 any sort of constraint on the compiler's choic
41 In contrast, READ_ONCE() and WRITE_ONCE() (#3
42 compiler's use of code-motion and common-subex
43 Therefore, if a given access is involved in an
44 using READ_ONCE() for loads and WRITE_ONCE() f
45 preferable to data_race(), which in turn is us
46 C-language accesses. It is permissible to com
47 data_race(READ_ONCE(a)), which will both restr
48 and disable KCSAN diagnostics.
49
50 KCSAN will complain about many types of data r
51 C-language accesses, but marking all accesses
52 race with one of data_race(), READ_ONCE(), or
53 KCSAN from complaining. Of course, lack of KC
54 imply correct code. Therefore, please take a
55 when responding to KCSAN complaints. Churning
56 ill-considered additions of data_race(), READ_
57 is unhelpful.
58
59 In fact, the following sections describe situa
60 data_race() and even plain C-language accesses
61 READ_ONCE() and WRITE_ONCE().
62
63
64 Use of the data_race() Macro
65 ----------------------------
66
67 Here are some situations where data_race() sho
68 READ_ONCE() and WRITE_ONCE():
69
70 1. Data-racy loads from shared variables
71 for diagnostic purposes.
72
73 2. Data-racy reads whose values are check
74
75 3. Reads whose values feed into error-tol
76
77 4. Writes setting values that feed into e
78
79
80 Data-Racy Reads for Approximate Diagnostics
81
82 Approximate diagnostics include lockdep report
83 (including /proc and /sys output), WARN*()/BUG
84 values are ignored, and other situations where
85 are not an integral part of the core concurren
86
87 In fact, use of data_race() instead READ_ONCE(
88 reads can enable better checking of the remain
89 the core concurrency design. For example, sup
90 prevents any non-diagnostic reads from shared
91 concurrently with updates to x. Then using pl
92 to x allows KCSAN to detect reads from x from
93 that fail to exclude the updates. In this cas
94 data_race() for the diagnostic reads because o
95 false-positive warnings about these diagnostic
96
97 If it is necessary to both restrict compiler o
98 KCSAN diagnostics, use both data_race() and RE
99 data_race(READ_ONCE(a)).
100
101 In theory, plain C-language loads can also be
102 However, in practice this will have the disadv
103 to generate false positives because KCSAN will
104 that the resulting data race was intentional.
105
106
107 Data-Racy Reads That Are Checked Against Marke
108
109 The values from some reads are not implicitly
110 fed into some operation that checks the full v
111 load from memory, which means that the occasio
112 is not a problem. For example, if a bogus val
113 all that happens is that this cmpxchg() fails,
114 in a retry. Unless the race condition that re
115 recurs, this retry will with high probability
116
117 However, please keep in mind that a data_race(
118 a cmpxchg_relaxed() might still be subject to
119 architectures. Therefore, it is best to captu
120 the failing cmpxchg() for the next iteration o
121 that provides the compiler much less scope for
122 Capturing the return value from cmpxchg() also
123 in many cases.
124
125 In theory, plain C-language loads can also be
126 However, in practice this will have the disadv
127 to generate false positives because KCSAN will
128 that the resulting data race was intentional.
129
130
131 Reads Feeding Into Error-Tolerant Heuristics
132
133 Values from some reads feed into heuristics th
134 errors. Such reads can use data_race(), thus
135 the other accesses to the relevant shared vari
136 that data_race() loads are subject to load fus
137 consistent errors, which in turn are quite cap
138 Therefore use of data_race() should be limited
139 code (such as a barrier() call) will force the
140
141 Note that this use case requires that the heur
142 any possible error. In contrast, if the heuri
143 confused by one or more of the possible errone
144 instead of data_race().
145
146 In theory, plain C-language loads can also be
147 However, in practice this will have the disadv
148 to generate false positives because KCSAN will
149 that the resulting data race was intentional.
150
151
152 Writes Setting Values Feeding Into Error-Toler
153
154 The values read into error-tolerant heuristics
155 for example, from sysfs. This means that some
156 to this same variable, and these writes can al
157 After all, if the heuristic can tolerate the o
158 due to compiler-mangled reads, it can also tol
159 compiler-mangled write, at least assuming that
160 place once the write completes.
161
162 Plain C-language stores can also be used for t
163 in kernels built with CONFIG_KCSAN_ASSUME_PLAI
164 will have the disadvantage of causing KCSAN to
165 because KCSAN will have no way of knowing that
166 was intentional.
167
168
169 Use of Plain C-Language Accesses
170 --------------------------------
171
172 Here are some example situations where plain C
173 used instead of READ_ONCE(), WRITE_ONCE(), and
174
175 1. Accesses protected by mutual exclusion
176 and sequence locking.
177
178 2. Initialization-time and cleanup-time a
179 wide variety of situations, including
180 system boot, variables to be used by n
181 structures not yet published to refere
182 data structures, and the cleanup side
183
184 3. Per-CPU variables that are not accesse
185
186 4. Private per-task variables, including
187 fields in the task_struct structure, a
188
189 5. Any other loads for which there is not
190 store to that same variable.
191
192 6. Any other stores for which there shoul
193 loads nor concurrent stores to that sa
194
195 But note that KCSAN makes two explicit
196 by default, refraining from flagging p
197
198 a. No matter what. You can overr
199 with CONFIG_KCSAN_ASSUME_PLAIN
200
201 b. When the store writes the valu
202 that variable. You can overri
203 with CONFIG_KCSAN_REPORT_VALUE
204
205 c. When one of the stores is in a
206 the other in the interrupted c
207 default by building with CONFI
208
209 Note that it is important to use plain C-langu
210 because doing otherwise prevents KCSAN from de
211 code's synchronization rules.
212
213
214 Use of __data_racy
215 ------------------
216
217 Adding the __data_racy type qualifier to the d
218 causes KCSAN to treat all accesses to that var
219 enclosed by data_race(). However, __data_racy
220 compiler, though one could imagine hardened ke
221 __data_racy type qualifier as if it was the vo
222
223 Note well that __data_racy is subject to the s
224 rules as are other type qualifiers such as con
225 For example:
226
227 int __data_racy *p; // Pointer to data
228 int *__data_racy p; // Data-racy point
229
230
231 ACCESS-DOCUMENTATION OPTIONS
232 ============================
233
234 It is important to comment marked accesses so
235 code, yourself included, are reminded of the s
236 However, it is even more important to comment
237 that are intentionally involved in data races.
238 needed to remind people reading your code, aga
239 of how the compiler has been prevented from op
240 into concurrency bugs.
241
242 It is also possible to tell KCSAN about your s
243 For example, ASSERT_EXCLUSIVE_ACCESS(foo) tell
244 concurrent access to variable foo by any other
245 if that concurrent access is marked with READ_
246 ASSERT_EXCLUSIVE_WRITER(foo) tells KCSAN that
247 to be concurrent reads from foo from other CPU
248 other CPU to be concurrently writing to foo, e
249 write is marked with data_race() or WRITE_ONCE
250
251 Note that although KCSAN will call out data ra
252 ASSERT_EXCLUSIVE_ACCESS() or ASSERT_EXCLUSIVE_
253 and data_race() writes on the other, KCSAN wil
254 of these data_race() writes.
255
256
257 EXAMPLES
258 ========
259
260 As noted earlier, the goal is to prevent the c
261 your concurrent algorithm, to help the human r
262 KCSAN of aspects of your concurrency design.
263 few examples showing how this can be done.
264
265
266 Lock Protection With Lockless Diagnostic Acces
267 ----------------------------------------------
268
269 For example, suppose a shared variable "foo" i
270 reader-writer spinlock is read-held, written o
271 spinlock is write-held, except that it is also
272 diagnostic purposes. The code might look as f
273
274 int foo;
275 DEFINE_RWLOCK(foo_rwlock);
276
277 void update_foo(int newval)
278 {
279 write_lock(&foo_rwlock);
280 foo = newval;
281 do_something(newval);
282 write_unlock(&foo_rwlock);
283 }
284
285 int read_foo(void)
286 {
287 int ret;
288
289 read_lock(&foo_rwlock);
290 do_something_else();
291 ret = foo;
292 read_unlock(&foo_rwlock);
293 return ret;
294 }
295
296 void read_foo_diagnostic(void)
297 {
298 pr_info("Current value of foo:
299 }
300
301 The reader-writer lock prevents the compiler f
302 bugs into any part of the main algorithm using
303 the accesses to foo within both update_foo() a
304 should) be plain C-language accesses. One ben
305 plain C-language accesses is that KCSAN can de
306 reads from or updates to foo. The data_race()
307 tells KCSAN that data races are expected, and
308 ignored. This data_race() also tells the huma
309 read_foo_diagnostic() might sometimes return a
310
311 If it is necessary to suppress compiler optimi
312 buggy lockless writes, read_foo_diagnostic() c
313
314 void read_foo_diagnostic(void)
315 {
316 pr_info("Current value of foo:
317 }
318
319 Alternatively, given that KCSAN is to ignore a
320 this function can be marked __no_kcsan and the
321
322 void __no_kcsan read_foo_diagnostic(vo
323 {
324 pr_info("Current value of foo:
325 }
326
327 However, in order for KCSAN to detect buggy lo
328 must be built with CONFIG_KCSAN_ASSUME_PLAIN_W
329 need KCSAN to detect such a write even if that
330 the value of foo, you also need CONFIG_KCSAN_R
331 If you need KCSAN to detect such a write happe
332 running on the same CPU doing the legitimate l
333 also need CONFIG_KCSAN_INTERRUPT_WATCHER=y. W
334 Kconfig options set properly, KCSAN can be qui
335 it is not necessarily a full replacement for h
336 On the other hand, neither are hardware watchp
337 for KCSAN because it is not always easy to tel
338 conditionally trap on accesses.
339
340
341 Lock-Protected Writes With Lockless Reads
342 -----------------------------------------
343
344 For another example, suppose a shared variable
345 while holding a spinlock, but is read lockless
346 as follows:
347
348 int foo;
349 DEFINE_SPINLOCK(foo_lock);
350
351 void update_foo(int newval)
352 {
353 spin_lock(&foo_lock);
354 WRITE_ONCE(foo, newval);
355 ASSERT_EXCLUSIVE_WRITER(foo);
356 do_something(newval);
357 spin_unlock(&foo_wlock);
358 }
359
360 int read_foo(void)
361 {
362 do_something_else();
363 return READ_ONCE(foo);
364 }
365
366 Because foo is read locklessly, all accesses a
367 of the ASSERT_EXCLUSIVE_WRITER() is to allow K
368 concurrent write, whether marked or not.
369
370
371 Lock-Protected Writes With Heuristic Lockless
372 ----------------------------------------------
373
374 For another example, suppose that the code can
375 a per-data-structure lock, but there are times
376 is required. These times are indicated via a
377 might look as follows, and is based loosely on
378 nf_conntrack_all_lock(), and nf_conntrack_all_
379
380 bool global_flag;
381 DEFINE_SPINLOCK(global_lock);
382 struct foo {
383 spinlock_t f_lock;
384 int f_data;
385 };
386
387 /* All foo structures are in the follo
388 int nfoo;
389 struct foo *foo_array;
390
391 void do_something_locked(struct foo *f
392 {
393 /* This works even if data_rac
394 if (!data_race(global_flag)) {
395 spin_lock(&fp->f_lock)
396 if (!smp_load_acquire(
397 do_something(f
398 spin_unlock(&f
399 return;
400 }
401 spin_unlock(&fp->f_loc
402 }
403 spin_lock(&global_lock);
404 /* global_lock held, thus glob
405 spin_lock(&fp->f_lock);
406 spin_unlock(&global_lock);
407 /*
408 * global_flag might be set he
409 * will wait for ->f_lock to b
410 */
411 do_something(fp);
412 spin_unlock(&fp->f_lock);
413 }
414
415 void begin_global(void)
416 {
417 int i;
418
419 spin_lock(&global_lock);
420 WRITE_ONCE(global_flag, true);
421 for (i = 0; i < nfoo; i++) {
422 /*
423 * Wait for pre-existi
424 * a time to avoid loc
425 */
426 spin_lock(&fp->f_lock)
427 spin_unlock(&fp->f_loc
428 }
429 }
430
431 void end_global(void)
432 {
433 smp_store_release(&global_flag
434 spin_unlock(&global_lock);
435 }
436
437 All code paths leading from the do_something_l
438 read from global_flag acquire a lock, so endle
439 happen.
440
441 If the value read from global_flag is true, th
442 rechecked while holding ->f_lock, which, if gl
443 prevents begin_global() from completing. It i
444 do_something().
445
446 Otherwise, if either value read from global_fl
447 global_lock is acquired global_flag must be fa
448 ->f_lock will prevent any call to begin_global
449 means that it is safe to release global_lock a
450
451 For this to work, only those foo structures in
452 to do_something_locked(). The reason for this
453 with begin_global() relies on momentarily hold
454 every foo structure.
455
456 The smp_load_acquire() and smp_store_release()
457 changes to a foo structure between calls to be
458 end_global() are carried out without holding t
459 The smp_load_acquire() and smp_store_release()
460 invocation of do_something() from do_something
461 changes.
462
463
464 Lockless Reads and Writes
465 -------------------------
466
467 For another example, suppose a shared variable
468 updated locklessly. The code might look as fo
469
470 int foo;
471
472 int update_foo(int newval)
473 {
474 int ret;
475
476 ret = xchg(&foo, newval);
477 do_something(newval);
478 return ret;
479 }
480
481 int read_foo(void)
482 {
483 do_something_else();
484 return READ_ONCE(foo);
485 }
486
487 Because foo is accessed locklessly, all access
488 not make sense to use ASSERT_EXCLUSIVE_WRITER(
489 there really can be concurrent lockless writer
490 flag any concurrent plain C-language reads fro
491 CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n, als
492 C-language writes to foo.
493
494
495 Lockless Reads and Writes, But With Single-Thr
496 ----------------------------------------------
497
498 For yet another example, suppose that foo is i
499 single-threaded manner, but that a number of k
500 that locklessly and concurrently access foo.
501 might look as follows:
502
503 int foo;
504
505 void initialize_foo(int initval, int n
506 {
507 int i;
508
509 foo = initval;
510 ASSERT_EXCLUSIVE_ACCESS(foo);
511 for (i = 0; i < nkthreads; i++
512 kthread_run(access_foo
513 }
514
515 /* Called from access_foo_concurrently
516 int update_foo(int newval)
517 {
518 int ret;
519
520 ret = xchg(&foo, newval);
521 do_something(newval);
522 return ret;
523 }
524
525 /* Also called from access_foo_concurr
526 int read_foo(void)
527 {
528 do_something_else();
529 return READ_ONCE(foo);
530 }
531
532 The initialize_foo() uses a plain C-language w
533 are not supposed to be concurrent accesses dur
534 ASSERT_EXCLUSIVE_ACCESS() allows KCSAN to flag
535 reads, and the ASSERT_EXCLUSIVE_ACCESS() call
536 flag buggy concurrent writes, even if: (1) Th
537 (2) The kernel was built with CONFIG_KCSAN_ASS
538
539
540 Checking Stress-Test Race Coverage
541 ----------------------------------
542
543 When designing stress tests it is important to
544 of interest really do occur. For example, con
545 fragment:
546
547 int foo;
548
549 int update_foo(int newval)
550 {
551 return xchg(&foo, newval);
552 }
553
554 int xor_shift_foo(int shift, int mask)
555 {
556 int old, new, newold;
557
558 newold = data_race(foo); /* Ch
559 do {
560 old = newold;
561 new = (old << shift) ^
562 newold = cmpxchg(&foo,
563 } while (newold != old);
564 return old;
565 }
566
567 int read_foo(void)
568 {
569 return READ_ONCE(foo);
570 }
571
572 If it is possible for update_foo(), xor_shift_
573 invoked concurrently, the stress test should f
574 actually happen. KCSAN can evaluate the stres
575 is modified to read as follows:
576
577 int foo;
578
579 int update_foo(int newval)
580 {
581 ASSERT_EXCLUSIVE_ACCESS(foo);
582 return xchg(&foo, newval);
583 }
584
585 int xor_shift_foo(int shift, int mask)
586 {
587 int old, new, newold;
588
589 newold = data_race(foo); /* Ch
590 do {
591 old = newold;
592 new = (old << shift) ^
593 ASSERT_EXCLUSIVE_ACCES
594 newold = cmpxchg(&foo,
595 } while (newold != old);
596 return old;
597 }
598
599
600 int read_foo(void)
601 {
602 ASSERT_EXCLUSIVE_ACCESS(foo);
603 return READ_ONCE(foo);
604 }
605
606 If a given stress-test run does not result in
607 each possible pair of ASSERT_EXCLUSIVE_ACCESS(
608 stress test needs improvement. If the stress
609 on a regular basis, it would be wise to place
610 ASSERT_EXCLUSIVE_ACCESS() under #ifdef so that
611 false positives when not evaluating the stress
612
613
614 REFERENCES
615 ==========
616
617 [1] "Concurrency bugs should fear the big bad
618 https://lwn.net/Articles/816854/
619
620 [2] "The Kernel Concurrency Sanitizer"
621 https://www.linuxfoundation.org/webinars/t
622
623 [3] "Who's afraid of a big bad optimizing comp
624 https://lwn.net/Articles/793253/
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.