1 MARKING SHARED-MEMORY ACCESSES
2 ==============================
4 This document provides guidelines for marking intentionally concurrent
5 normal accesses to shared memory, that is "normal" as in accesses that do
6 not use read-modify-write atomic operations. It also describes how to
7 document these accesses, both with comments and with special assertions
8 processed by the Kernel Concurrency Sanitizer (KCSAN). This discussion
9 builds on an earlier LWN article [1].
12 ACCESS-MARKING OPTIONS
13 ======================
15 The Linux kernel provides the following access-marking options:
17 1. Plain C-language accesses (unmarked), for example, "a = b;"
19 2. Data-race marking, for example, "data_race(a = b);"
21 3. READ_ONCE(), for example, "a = READ_ONCE(b);"
22 The various forms of atomic_read() also fit in here.
24 4. WRITE_ONCE(), for example, "WRITE_ONCE(a, b);"
25 The various forms of atomic_set() also fit in here.
28 These may be used in combination, as shown in this admittedly improbable
31 WRITE_ONCE(a, b + data_race(c + d) + READ_ONCE(e));
33 Neither plain C-language accesses nor data_race() (#1 and #2 above) place
34 any sort of constraint on the compiler's choice of optimizations [2].
35 In contrast, READ_ONCE() and WRITE_ONCE() (#3 and #4 above) restrict the
36 compiler's use of code-motion and common-subexpression optimizations.
37 Therefore, if a given access is involved in an intentional data race,
38 using READ_ONCE() for loads and WRITE_ONCE() for stores is usually
39 preferable to data_race(), which in turn is usually preferable to plain
40 C-language accesses. It is permissible to combine #2 and #3, for example,
41 data_race(READ_ONCE(a)), which will both restrict compiler optimizations
42 and disable KCSAN diagnostics.
44 KCSAN will complain about many types of data races involving plain
45 C-language accesses, but marking all accesses involved in a given data
46 race with one of data_race(), READ_ONCE(), or WRITE_ONCE(), will prevent
47 KCSAN from complaining. Of course, lack of KCSAN complaints does not
48 imply correct code. Therefore, please take a thoughtful approach
49 when responding to KCSAN complaints. Churning the code base with
50 ill-considered additions of data_race(), READ_ONCE(), and WRITE_ONCE()
53 In fact, the following sections describe situations where use of
54 data_race() and even plain C-language accesses is preferable to
55 READ_ONCE() and WRITE_ONCE().
58 Use of the data_race() Macro
59 ----------------------------
61 Here are some situations where data_race() should be used instead of
62 READ_ONCE() and WRITE_ONCE():
64 1. Data-racy loads from shared variables whose values are used only
65 for diagnostic purposes.
67 2. Data-racy reads whose values are checked against marked reload.
69 3. Reads whose values feed into error-tolerant heuristics.
71 4. Writes setting values that feed into error-tolerant heuristics.
74 Data-Racy Reads for Approximate Diagnostics
76 Approximate diagnostics include lockdep reports, monitoring/statistics
77 (including /proc and /sys output), WARN*()/BUG*() checks whose return
78 values are ignored, and other situations where reads from shared variables
79 are not an integral part of the core concurrency design.
81 In fact, use of data_race() instead READ_ONCE() for these diagnostic
82 reads can enable better checking of the remaining accesses implementing
83 the core concurrency design. For example, suppose that the core design
84 prevents any non-diagnostic reads from shared variable x from running
85 concurrently with updates to x. Then using plain C-language writes
86 to x allows KCSAN to detect reads from x from within regions of code
87 that fail to exclude the updates. In this case, it is important to use
88 data_race() for the diagnostic reads because otherwise KCSAN would give
89 false-positive warnings about these diagnostic reads.
91 If it is necessary to both restrict compiler optimizations and disable
92 KCSAN diagnostics, use both data_race() and READ_ONCE(), for example,
93 data_race(READ_ONCE(a)).
95 In theory, plain C-language loads can also be used for this use case.
96 However, in practice this will have the disadvantage of causing KCSAN
97 to generate false positives because KCSAN will have no way of knowing
98 that the resulting data race was intentional.
101 Data-Racy Reads That Are Checked Against Marked Reload
103 The values from some reads are not implicitly trusted. They are instead
104 fed into some operation that checks the full value against a later marked
105 load from memory, which means that the occasional arbitrarily bogus value
106 is not a problem. For example, if a bogus value is fed into cmpxchg(),
107 all that happens is that this cmpxchg() fails, which normally results
108 in a retry. Unless the race condition that resulted in the bogus value
109 recurs, this retry will with high probability succeed, so no harm done.
111 However, please keep in mind that a data_race() load feeding into
112 a cmpxchg_relaxed() might still be subject to load fusing on some
113 architectures. Therefore, it is best to capture the return value from
114 the failing cmpxchg() for the next iteration of the loop, an approach
115 that provides the compiler much less scope for mischievous optimizations.
116 Capturing the return value from cmpxchg() also saves a memory reference
119 In theory, plain C-language loads can also be used for this use case.
120 However, in practice this will have the disadvantage of causing KCSAN
121 to generate false positives because KCSAN will have no way of knowing
122 that the resulting data race was intentional.
125 Reads Feeding Into Error-Tolerant Heuristics
127 Values from some reads feed into heuristics that can tolerate occasional
128 errors. Such reads can use data_race(), thus allowing KCSAN to focus on
129 the other accesses to the relevant shared variables. But please note
130 that data_race() loads are subject to load fusing, which can result in
131 consistent errors, which in turn are quite capable of breaking heuristics.
132 Therefore use of data_race() should be limited to cases where some other
133 code (such as a barrier() call) will force the occasional reload.
135 Note that this use case requires that the heuristic be able to handle
136 any possible error. In contrast, if the heuristics might be fatally
137 confused by one or more of the possible erroneous values, use READ_ONCE()
138 instead of data_race().
140 In theory, plain C-language loads can also be used for this use case.
141 However, in practice this will have the disadvantage of causing KCSAN
142 to generate false positives because KCSAN will have no way of knowing
143 that the resulting data race was intentional.
146 Writes Setting Values Feeding Into Error-Tolerant Heuristics
148 The values read into error-tolerant heuristics come from somewhere,
149 for example, from sysfs. This means that some code in sysfs writes
150 to this same variable, and these writes can also use data_race().
151 After all, if the heuristic can tolerate the occasional bogus value
152 due to compiler-mangled reads, it can also tolerate the occasional
153 compiler-mangled write, at least assuming that the proper value is in
154 place once the write completes.
156 Plain C-language stores can also be used for this use case. However,
157 in kernels built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n, this
158 will have the disadvantage of causing KCSAN to generate false positives
159 because KCSAN will have no way of knowing that the resulting data race
163 Use of Plain C-Language Accesses
164 --------------------------------
166 Here are some example situations where plain C-language accesses should
167 used instead of READ_ONCE(), WRITE_ONCE(), and data_race():
169 1. Accesses protected by mutual exclusion, including strict locking
170 and sequence locking.
172 2. Initialization-time and cleanup-time accesses. This covers a
173 wide variety of situations, including the uniprocessor phase of
174 system boot, variables to be used by not-yet-spawned kthreads,
175 structures not yet published to reference-counted or RCU-protected
176 data structures, and the cleanup side of any of these situations.
178 3. Per-CPU variables that are not accessed from other CPUs.
180 4. Private per-task variables, including on-stack variables, some
181 fields in the task_struct structure, and task-private heap data.
183 5. Any other loads for which there is not supposed to be a concurrent
184 store to that same variable.
186 6. Any other stores for which there should be neither concurrent
187 loads nor concurrent stores to that same variable.
189 But note that KCSAN makes two explicit exceptions to this rule
190 by default, refraining from flagging plain C-language stores:
192 a. No matter what. You can override this default by building
193 with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n.
195 b. When the store writes the value already contained in
196 that variable. You can override this default by building
197 with CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=n.
199 c. When one of the stores is in an interrupt handler and
200 the other in the interrupted code. You can override this
201 default by building with CONFIG_KCSAN_INTERRUPT_WATCHER=y.
203 Note that it is important to use plain C-language accesses in these cases,
204 because doing otherwise prevents KCSAN from detecting violations of your
205 code's synchronization rules.
208 ACCESS-DOCUMENTATION OPTIONS
209 ============================
211 It is important to comment marked accesses so that people reading your
212 code, yourself included, are reminded of the synchronization design.
213 However, it is even more important to comment plain C-language accesses
214 that are intentionally involved in data races. Such comments are
215 needed to remind people reading your code, again, yourself included,
216 of how the compiler has been prevented from optimizing those accesses
217 into concurrency bugs.
219 It is also possible to tell KCSAN about your synchronization design.
220 For example, ASSERT_EXCLUSIVE_ACCESS(foo) tells KCSAN that any
221 concurrent access to variable foo by any other CPU is an error, even
222 if that concurrent access is marked with READ_ONCE(). In addition,
223 ASSERT_EXCLUSIVE_WRITER(foo) tells KCSAN that although it is OK for there
224 to be concurrent reads from foo from other CPUs, it is an error for some
225 other CPU to be concurrently writing to foo, even if that concurrent
226 write is marked with data_race() or WRITE_ONCE().
228 Note that although KCSAN will call out data races involving either
229 ASSERT_EXCLUSIVE_ACCESS() or ASSERT_EXCLUSIVE_WRITER() on the one hand
230 and data_race() writes on the other, KCSAN will not report the location
231 of these data_race() writes.
237 As noted earlier, the goal is to prevent the compiler from destroying
238 your concurrent algorithm, to help the human reader, and to inform
239 KCSAN of aspects of your concurrency design. This section looks at a
240 few examples showing how this can be done.
243 Lock Protection With Lockless Diagnostic Access
244 -----------------------------------------------
246 For example, suppose a shared variable "foo" is read only while a
247 reader-writer spinlock is read-held, written only while that same
248 spinlock is write-held, except that it is also read locklessly for
249 diagnostic purposes. The code might look as follows:
252 DEFINE_RWLOCK(foo_rwlock);
254 void update_foo(int newval)
256 write_lock(&foo_rwlock);
258 do_something(newval);
259 write_unlock(&foo_rwlock);
266 read_lock(&foo_rwlock);
269 read_unlock(&foo_rwlock);
273 void read_foo_diagnostic(void)
275 pr_info("Current value of foo: %d\n", data_race(foo));
278 The reader-writer lock prevents the compiler from introducing concurrency
279 bugs into any part of the main algorithm using foo, which means that
280 the accesses to foo within both update_foo() and read_foo() can (and
281 should) be plain C-language accesses. One benefit of making them be
282 plain C-language accesses is that KCSAN can detect any erroneous lockless
283 reads from or updates to foo. The data_race() in read_foo_diagnostic()
284 tells KCSAN that data races are expected, and should be silently
285 ignored. This data_race() also tells the human reading the code that
286 read_foo_diagnostic() might sometimes return a bogus value.
288 If it is necessary to suppress compiler optimization and also detect
289 buggy lockless writes, read_foo_diagnostic() can be updated as follows:
291 void read_foo_diagnostic(void)
293 pr_info("Current value of foo: %d\n", data_race(READ_ONCE(foo)));
296 Alternatively, given that KCSAN is to ignore all accesses in this function,
297 this function can be marked __no_kcsan and the data_race() can be dropped:
299 void __no_kcsan read_foo_diagnostic(void)
301 pr_info("Current value of foo: %d\n", READ_ONCE(foo));
304 However, in order for KCSAN to detect buggy lockless writes, your kernel
305 must be built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n. If you
306 need KCSAN to detect such a write even if that write did not change
307 the value of foo, you also need CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=n.
308 If you need KCSAN to detect such a write happening in an interrupt handler
309 running on the same CPU doing the legitimate lock-protected write, you
310 also need CONFIG_KCSAN_INTERRUPT_WATCHER=y. With some or all of these
311 Kconfig options set properly, KCSAN can be quite helpful, although
312 it is not necessarily a full replacement for hardware watchpoints.
313 On the other hand, neither are hardware watchpoints a full replacement
314 for KCSAN because it is not always easy to tell hardware watchpoint to
315 conditionally trap on accesses.
318 Lock-Protected Writes With Lockless Reads
319 -----------------------------------------
321 For another example, suppose a shared variable "foo" is updated only
322 while holding a spinlock, but is read locklessly. The code might look
326 DEFINE_SPINLOCK(foo_lock);
328 void update_foo(int newval)
330 spin_lock(&foo_lock);
331 WRITE_ONCE(foo, newval);
332 ASSERT_EXCLUSIVE_WRITER(foo);
333 do_something(newval);
334 spin_unlock(&foo_wlock);
340 return READ_ONCE(foo);
343 Because foo is read locklessly, all accesses are marked. The purpose
344 of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy
345 concurrent lockless write.
348 Lock-Protected Writes With Heuristic Lockless Reads
349 ---------------------------------------------------
351 For another example, suppose that the code can normally make use of
352 a per-data-structure lock, but there are times when a global lock
353 is required. These times are indicated via a global flag. The code
354 might look as follows, and is based loosely on nf_conntrack_lock(),
355 nf_conntrack_all_lock(), and nf_conntrack_all_unlock():
358 DEFINE_SPINLOCK(global_lock);
364 /* All foo structures are in the following array. */
366 struct foo *foo_array;
368 void do_something_locked(struct foo *fp)
370 /* This works even if data_race() returns nonsense. */
371 if (!data_race(global_flag)) {
372 spin_lock(&fp->f_lock);
373 if (!smp_load_acquire(&global_flag)) {
375 spin_unlock(&fp->f_lock);
378 spin_unlock(&fp->f_lock);
380 spin_lock(&global_lock);
381 /* global_lock held, thus global flag cannot be set. */
382 spin_lock(&fp->f_lock);
383 spin_unlock(&global_lock);
385 * global_flag might be set here, but begin_global()
386 * will wait for ->f_lock to be released.
389 spin_unlock(&fp->f_lock);
392 void begin_global(void)
396 spin_lock(&global_lock);
397 WRITE_ONCE(global_flag, true);
398 for (i = 0; i < nfoo; i++) {
400 * Wait for pre-existing local locks. One at
401 * a time to avoid lockdep limitations.
403 spin_lock(&fp->f_lock);
404 spin_unlock(&fp->f_lock);
408 void end_global(void)
410 smp_store_release(&global_flag, false);
411 spin_unlock(&global_lock);
414 All code paths leading from the do_something_locked() function's first
415 read from global_flag acquire a lock, so endless load fusing cannot
418 If the value read from global_flag is true, then global_flag is
419 rechecked while holding ->f_lock, which, if global_flag is now false,
420 prevents begin_global() from completing. It is therefore safe to invoke
423 Otherwise, if either value read from global_flag is true, then after
424 global_lock is acquired global_flag must be false. The acquisition of
425 ->f_lock will prevent any call to begin_global() from returning, which
426 means that it is safe to release global_lock and invoke do_something().
428 For this to work, only those foo structures in foo_array[] may be passed
429 to do_something_locked(). The reason for this is that the synchronization
430 with begin_global() relies on momentarily holding the lock of each and
433 The smp_load_acquire() and smp_store_release() are required because
434 changes to a foo structure between calls to begin_global() and
435 end_global() are carried out without holding that structure's ->f_lock.
436 The smp_load_acquire() and smp_store_release() ensure that the next
437 invocation of do_something() from do_something_locked() will see those
441 Lockless Reads and Writes
442 -------------------------
444 For another example, suppose a shared variable "foo" is both read and
445 updated locklessly. The code might look as follows:
449 int update_foo(int newval)
453 ret = xchg(&foo, newval);
454 do_something(newval);
461 return READ_ONCE(foo);
464 Because foo is accessed locklessly, all accesses are marked. It does
465 not make sense to use ASSERT_EXCLUSIVE_WRITER() in this case because
466 there really can be concurrent lockless writers. KCSAN would
467 flag any concurrent plain C-language reads from foo, and given
468 CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n, also any concurrent plain
469 C-language writes to foo.
472 Lockless Reads and Writes, But With Single-Threaded Initialization
473 ------------------------------------------------------------------
475 For yet another example, suppose that foo is initialized in a
476 single-threaded manner, but that a number of kthreads are then created
477 that locklessly and concurrently access foo. Some snippets of this code
478 might look as follows:
482 void initialize_foo(int initval, int nkthreads)
487 ASSERT_EXCLUSIVE_ACCESS(foo);
488 for (i = 0; i < nkthreads; i++)
489 kthread_run(access_foo_concurrently, ...);
492 /* Called from access_foo_concurrently(). */
493 int update_foo(int newval)
497 ret = xchg(&foo, newval);
498 do_something(newval);
502 /* Also called from access_foo_concurrently(). */
506 return READ_ONCE(foo);
509 The initialize_foo() uses a plain C-language write to foo because there
510 are not supposed to be concurrent accesses during initialization. The
511 ASSERT_EXCLUSIVE_ACCESS() allows KCSAN to flag buggy concurrent unmarked
512 reads, and the ASSERT_EXCLUSIVE_ACCESS() call further allows KCSAN to
513 flag buggy concurrent writes, even if: (1) Those writes are marked or
514 (2) The kernel was built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=y.
517 Checking Stress-Test Race Coverage
518 ----------------------------------
520 When designing stress tests it is important to ensure that race conditions
521 of interest really do occur. For example, consider the following code
526 int update_foo(int newval)
528 return xchg(&foo, newval);
531 int xor_shift_foo(int shift, int mask)
533 int old, new, newold;
535 newold = data_race(foo); /* Checked by cmpxchg(). */
538 new = (old << shift) ^ mask;
539 newold = cmpxchg(&foo, old, new);
540 } while (newold != old);
546 return READ_ONCE(foo);
549 If it is possible for update_foo(), xor_shift_foo(), and read_foo() to be
550 invoked concurrently, the stress test should force this concurrency to
551 actually happen. KCSAN can evaluate the stress test when the above code
552 is modified to read as follows:
556 int update_foo(int newval)
558 ASSERT_EXCLUSIVE_ACCESS(foo);
559 return xchg(&foo, newval);
562 int xor_shift_foo(int shift, int mask)
564 int old, new, newold;
566 newold = data_race(foo); /* Checked by cmpxchg(). */
569 new = (old << shift) ^ mask;
570 ASSERT_EXCLUSIVE_ACCESS(foo);
571 newold = cmpxchg(&foo, old, new);
572 } while (newold != old);
579 ASSERT_EXCLUSIVE_ACCESS(foo);
580 return READ_ONCE(foo);
583 If a given stress-test run does not result in KCSAN complaints from
584 each possible pair of ASSERT_EXCLUSIVE_ACCESS() invocations, the
585 stress test needs improvement. If the stress test was to be evaluated
586 on a regular basis, it would be wise to place the above instances of
587 ASSERT_EXCLUSIVE_ACCESS() under #ifdef so that they did not result in
588 false positives when not evaluating the stress test.
594 [1] "Concurrency bugs should fear the big bad data-race detector (part 2)"
595 https://lwn.net/Articles/816854/
597 [2] "Who's afraid of a big bad optimizing compiler?"
598 https://lwn.net/Articles/793253/