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
42 KCSAN will complain about many types of data races involving plain
43 C-language accesses, but marking all accesses involved in a given data
44 race with one of data_race(), READ_ONCE(), or WRITE_ONCE(), will prevent
45 KCSAN from complaining. Of course, lack of KCSAN complaints does not
46 imply correct code. Therefore, please take a thoughtful approach
47 when responding to KCSAN complaints. Churning the code base with
48 ill-considered additions of data_race(), READ_ONCE(), and WRITE_ONCE()
51 In fact, the following sections describe situations where use of
52 data_race() and even plain C-language accesses is preferable to
53 READ_ONCE() and WRITE_ONCE().
56 Use of the data_race() Macro
57 ----------------------------
59 Here are some situations where data_race() should be used instead of
60 READ_ONCE() and WRITE_ONCE():
62 1. Data-racy loads from shared variables whose values are used only
63 for diagnostic purposes.
65 2. Data-racy reads whose values are checked against marked reload.
67 3. Reads whose values feed into error-tolerant heuristics.
69 4. Writes setting values that feed into error-tolerant heuristics.
72 Data-Racy Reads for Approximate Diagnostics
74 Approximate diagnostics include lockdep reports, monitoring/statistics
75 (including /proc and /sys output), WARN*()/BUG*() checks whose return
76 values are ignored, and other situations where reads from shared variables
77 are not an integral part of the core concurrency design.
79 In fact, use of data_race() instead READ_ONCE() for these diagnostic
80 reads can enable better checking of the remaining accesses implementing
81 the core concurrency design. For example, suppose that the core design
82 prevents any non-diagnostic reads from shared variable x from running
83 concurrently with updates to x. Then using plain C-language writes
84 to x allows KCSAN to detect reads from x from within regions of code
85 that fail to exclude the updates. In this case, it is important to use
86 data_race() for the diagnostic reads because otherwise KCSAN would give
87 false-positive warnings about these diagnostic reads.
89 In theory, plain C-language loads can also be used for this use case.
90 However, in practice this will have the disadvantage of causing KCSAN
91 to generate false positives because KCSAN will have no way of knowing
92 that the resulting data race was intentional.
95 Data-Racy Reads That Are Checked Against Marked Reload
97 The values from some reads are not implicitly trusted. They are instead
98 fed into some operation that checks the full value against a later marked
99 load from memory, which means that the occasional arbitrarily bogus value
100 is not a problem. For example, if a bogus value is fed into cmpxchg(),
101 all that happens is that this cmpxchg() fails, which normally results
102 in a retry. Unless the race condition that resulted in the bogus value
103 recurs, this retry will with high probability succeed, so no harm done.
105 However, please keep in mind that a data_race() load feeding into
106 a cmpxchg_relaxed() might still be subject to load fusing on some
107 architectures. Therefore, it is best to capture the return value from
108 the failing cmpxchg() for the next iteration of the loop, an approach
109 that provides the compiler much less scope for mischievous optimizations.
110 Capturing the return value from cmpxchg() also saves a memory reference
113 In theory, plain C-language loads can also be used for this use case.
114 However, in practice this will have the disadvantage of causing KCSAN
115 to generate false positives because KCSAN will have no way of knowing
116 that the resulting data race was intentional.
119 Reads Feeding Into Error-Tolerant Heuristics
121 Values from some reads feed into heuristics that can tolerate occasional
122 errors. Such reads can use data_race(), thus allowing KCSAN to focus on
123 the other accesses to the relevant shared variables. But please note
124 that data_race() loads are subject to load fusing, which can result in
125 consistent errors, which in turn are quite capable of breaking heuristics.
126 Therefore use of data_race() should be limited to cases where some other
127 code (such as a barrier() call) will force the occasional reload.
129 In theory, plain C-language loads can also be used for this use case.
130 However, in practice this will have the disadvantage of causing KCSAN
131 to generate false positives because KCSAN will have no way of knowing
132 that the resulting data race was intentional.
135 Writes Setting Values Feeding Into Error-Tolerant Heuristics
137 The values read into error-tolerant heuristics come from somewhere,
138 for example, from sysfs. This means that some code in sysfs writes
139 to this same variable, and these writes can also use data_race().
140 After all, if the heuristic can tolerate the occasional bogus value
141 due to compiler-mangled reads, it can also tolerate the occasional
142 compiler-mangled write, at least assuming that the proper value is in
143 place once the write completes.
145 Plain C-language stores can also be used for this use case. However,
146 in kernels built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n, this
147 will have the disadvantage of causing KCSAN to generate false positives
148 because KCSAN will have no way of knowing that the resulting data race
152 Use of Plain C-Language Accesses
153 --------------------------------
155 Here are some example situations where plain C-language accesses should
156 used instead of READ_ONCE(), WRITE_ONCE(), and data_race():
158 1. Accesses protected by mutual exclusion, including strict locking
159 and sequence locking.
161 2. Initialization-time and cleanup-time accesses. This covers a
162 wide variety of situations, including the uniprocessor phase of
163 system boot, variables to be used by not-yet-spawned kthreads,
164 structures not yet published to reference-counted or RCU-protected
165 data structures, and the cleanup side of any of these situations.
167 3. Per-CPU variables that are not accessed from other CPUs.
169 4. Private per-task variables, including on-stack variables, some
170 fields in the task_struct structure, and task-private heap data.
172 5. Any other loads for which there is not supposed to be a concurrent
173 store to that same variable.
175 6. Any other stores for which there should be neither concurrent
176 loads nor concurrent stores to that same variable.
178 But note that KCSAN makes two explicit exceptions to this rule
179 by default, refraining from flagging plain C-language stores:
181 a. No matter what. You can override this default by building
182 with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n.
184 b. When the store writes the value already contained in
185 that variable. You can override this default by building
186 with CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=n.
188 c. When one of the stores is in an interrupt handler and
189 the other in the interrupted code. You can override this
190 default by building with CONFIG_KCSAN_INTERRUPT_WATCHER=y.
192 Note that it is important to use plain C-language accesses in these cases,
193 because doing otherwise prevents KCSAN from detecting violations of your
194 code's synchronization rules.
197 ACCESS-DOCUMENTATION OPTIONS
198 ============================
200 It is important to comment marked accesses so that people reading your
201 code, yourself included, are reminded of the synchronization design.
202 However, it is even more important to comment plain C-language accesses
203 that are intentionally involved in data races. Such comments are
204 needed to remind people reading your code, again, yourself included,
205 of how the compiler has been prevented from optimizing those accesses
206 into concurrency bugs.
208 It is also possible to tell KCSAN about your synchronization design.
209 For example, ASSERT_EXCLUSIVE_ACCESS(foo) tells KCSAN that any
210 concurrent access to variable foo by any other CPU is an error, even
211 if that concurrent access is marked with READ_ONCE(). In addition,
212 ASSERT_EXCLUSIVE_WRITER(foo) tells KCSAN that although it is OK for there
213 to be concurrent reads from foo from other CPUs, it is an error for some
214 other CPU to be concurrently writing to foo, even if that concurrent
215 write is marked with data_race() or WRITE_ONCE().
217 Note that although KCSAN will call out data races involving either
218 ASSERT_EXCLUSIVE_ACCESS() or ASSERT_EXCLUSIVE_WRITER() on the one hand
219 and data_race() writes on the other, KCSAN will not report the location
220 of these data_race() writes.
226 As noted earlier, the goal is to prevent the compiler from destroying
227 your concurrent algorithm, to help the human reader, and to inform
228 KCSAN of aspects of your concurrency design. This section looks at a
229 few examples showing how this can be done.
232 Lock Protection With Lockless Diagnostic Access
233 -----------------------------------------------
235 For example, suppose a shared variable "foo" is read only while a
236 reader-writer spinlock is read-held, written only while that same
237 spinlock is write-held, except that it is also read locklessly for
238 diagnostic purposes. The code might look as follows:
241 DEFINE_RWLOCK(foo_rwlock);
243 void update_foo(int newval)
245 write_lock(&foo_rwlock);
247 do_something(newval);
248 write_unlock(&foo_rwlock);
255 read_lock(&foo_rwlock);
258 read_unlock(&foo_rwlock);
262 int read_foo_diagnostic(void)
264 return data_race(foo);
267 The reader-writer lock prevents the compiler from introducing concurrency
268 bugs into any part of the main algorithm using foo, which means that
269 the accesses to foo within both update_foo() and read_foo() can (and
270 should) be plain C-language accesses. One benefit of making them be
271 plain C-language accesses is that KCSAN can detect any erroneous lockless
272 reads from or updates to foo. The data_race() in read_foo_diagnostic()
273 tells KCSAN that data races are expected, and should be silently
274 ignored. This data_race() also tells the human reading the code that
275 read_foo_diagnostic() might sometimes return a bogus value.
277 However, please note that your kernel must be built with
278 CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n in order for KCSAN to
279 detect a buggy lockless write. If you need KCSAN to detect such a
280 write even if that write did not change the value of foo, you also
281 need CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=n. If you need KCSAN to
282 detect such a write happening in an interrupt handler running on the
283 same CPU doing the legitimate lock-protected write, you also need
284 CONFIG_KCSAN_INTERRUPT_WATCHER=y. With some or all of these Kconfig
285 options set properly, KCSAN can be quite helpful, although it is not
286 necessarily a full replacement for hardware watchpoints. On the other
287 hand, neither are hardware watchpoints a full replacement for KCSAN
288 because it is not always easy to tell hardware watchpoint to conditionally
292 Lock-Protected Writes With Lockless Reads
293 -----------------------------------------
295 For another example, suppose a shared variable "foo" is updated only
296 while holding a spinlock, but is read locklessly. The code might look
300 DEFINE_SPINLOCK(foo_lock);
302 void update_foo(int newval)
304 spin_lock(&foo_lock);
305 WRITE_ONCE(foo, newval);
306 ASSERT_EXCLUSIVE_WRITER(foo);
307 do_something(newval);
308 spin_unlock(&foo_wlock);
314 return READ_ONCE(foo);
317 Because foo is read locklessly, all accesses are marked. The purpose
318 of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy
319 concurrent lockless write.
322 Lockless Reads and Writes
323 -------------------------
325 For another example, suppose a shared variable "foo" is both read and
326 updated locklessly. The code might look as follows:
330 int update_foo(int newval)
334 ret = xchg(&foo, newval);
335 do_something(newval);
342 return READ_ONCE(foo);
345 Because foo is accessed locklessly, all accesses are marked. It does
346 not make sense to use ASSERT_EXCLUSIVE_WRITER() in this case because
347 there really can be concurrent lockless writers. KCSAN would
348 flag any concurrent plain C-language reads from foo, and given
349 CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n, also any concurrent plain
350 C-language writes to foo.
353 Lockless Reads and Writes, But With Single-Threaded Initialization
354 ------------------------------------------------------------------
356 For yet another example, suppose that foo is initialized in a
357 single-threaded manner, but that a number of kthreads are then created
358 that locklessly and concurrently access foo. Some snippets of this code
359 might look as follows:
363 void initialize_foo(int initval, int nkthreads)
368 ASSERT_EXCLUSIVE_ACCESS(foo);
369 for (i = 0; i < nkthreads; i++)
370 kthread_run(access_foo_concurrently, ...);
373 /* Called from access_foo_concurrently(). */
374 int update_foo(int newval)
378 ret = xchg(&foo, newval);
379 do_something(newval);
383 /* Also called from access_foo_concurrently(). */
387 return READ_ONCE(foo);
390 The initialize_foo() uses a plain C-language write to foo because there
391 are not supposed to be concurrent accesses during initialization. The
392 ASSERT_EXCLUSIVE_ACCESS() allows KCSAN to flag buggy concurrent unmarked
393 reads, and the ASSERT_EXCLUSIVE_ACCESS() call further allows KCSAN to
394 flag buggy concurrent writes, even if: (1) Those writes are marked or
395 (2) The kernel was built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=y.
398 Checking Stress-Test Race Coverage
399 ----------------------------------
401 When designing stress tests it is important to ensure that race conditions
402 of interest really do occur. For example, consider the following code
407 int update_foo(int newval)
409 return xchg(&foo, newval);
412 int xor_shift_foo(int shift, int mask)
414 int old, new, newold;
416 newold = data_race(foo); /* Checked by cmpxchg(). */
419 new = (old << shift) ^ mask;
420 newold = cmpxchg(&foo, old, new);
421 } while (newold != old);
427 return READ_ONCE(foo);
430 If it is possible for update_foo(), xor_shift_foo(), and read_foo() to be
431 invoked concurrently, the stress test should force this concurrency to
432 actually happen. KCSAN can evaluate the stress test when the above code
433 is modified to read as follows:
437 int update_foo(int newval)
439 ASSERT_EXCLUSIVE_ACCESS(foo);
440 return xchg(&foo, newval);
443 int xor_shift_foo(int shift, int mask)
445 int old, new, newold;
447 newold = data_race(foo); /* Checked by cmpxchg(). */
450 new = (old << shift) ^ mask;
451 ASSERT_EXCLUSIVE_ACCESS(foo);
452 newold = cmpxchg(&foo, old, new);
453 } while (newold != old);
460 ASSERT_EXCLUSIVE_ACCESS(foo);
461 return READ_ONCE(foo);
464 If a given stress-test run does not result in KCSAN complaints from
465 each possible pair of ASSERT_EXCLUSIVE_ACCESS() invocations, the
466 stress test needs improvement. If the stress test was to be evaluated
467 on a regular basis, it would be wise to place the above instances of
468 ASSERT_EXCLUSIVE_ACCESS() under #ifdef so that they did not result in
469 false positives when not evaluating the stress test.
475 [1] "Concurrency bugs should fear the big bad data-race detector (part 2)"
476 https://lwn.net/Articles/816854/
478 [2] "Who's afraid of a big bad optimizing compiler?"
479 https://lwn.net/Articles/793253/