1MARKING SHARED-MEMORY ACCESSES 2============================== 3 4This document provides guidelines for marking intentionally concurrent 5normal accesses to shared memory, that is "normal" as in accesses that do 6not use read-modify-write atomic operations. It also describes how to 7document these accesses, both with comments and with special assertions 8processed by the Kernel Concurrency Sanitizer (KCSAN). This discussion 9builds on an earlier LWN article [1]. 10 11 12ACCESS-MARKING OPTIONS 13====================== 14 15The Linux kernel provides the following access-marking options: 16 171. Plain C-language accesses (unmarked), for example, "a = b;" 18 192. Data-race marking, for example, "data_race(a = b);" 20 213. READ_ONCE(), for example, "a = READ_ONCE(b);" 22 The various forms of atomic_read() also fit in here. 23 244. WRITE_ONCE(), for example, "WRITE_ONCE(a, b);" 25 The various forms of atomic_set() also fit in here. 26 27 28These may be used in combination, as shown in this admittedly improbable 29example: 30 31 WRITE_ONCE(a, b + data_race(c + d) + READ_ONCE(e)); 32 33Neither plain C-language accesses nor data_race() (#1 and #2 above) place 34any sort of constraint on the compiler's choice of optimizations [2]. 35In contrast, READ_ONCE() and WRITE_ONCE() (#3 and #4 above) restrict the 36compiler's use of code-motion and common-subexpression optimizations. 37Therefore, if a given access is involved in an intentional data race, 38using READ_ONCE() for loads and WRITE_ONCE() for stores is usually 39preferable to data_race(), which in turn is usually preferable to plain 40C-language accesses. 41 42KCSAN will complain about many types of data races involving plain 43C-language accesses, but marking all accesses involved in a given data 44race with one of data_race(), READ_ONCE(), or WRITE_ONCE(), will prevent 45KCSAN from complaining. Of course, lack of KCSAN complaints does not 46imply correct code. Therefore, please take a thoughtful approach 47when responding to KCSAN complaints. Churning the code base with 48ill-considered additions of data_race(), READ_ONCE(), and WRITE_ONCE() 49is unhelpful. 50 51In fact, the following sections describe situations where use of 52data_race() and even plain C-language accesses is preferable to 53READ_ONCE() and WRITE_ONCE(). 54 55 56Use of the data_race() Macro 57---------------------------- 58 59Here are some situations where data_race() should be used instead of 60READ_ONCE() and WRITE_ONCE(): 61 621. Data-racy loads from shared variables whose values are used only 63 for diagnostic purposes. 64 652. Data-racy reads whose values are checked against marked reload. 66 673. Reads whose values feed into error-tolerant heuristics. 68 694. Writes setting values that feed into error-tolerant heuristics. 70 71 72Data-Racy Reads for Approximate Diagnostics 73 74Approximate diagnostics include lockdep reports, monitoring/statistics 75(including /proc and /sys output), WARN*()/BUG*() checks whose return 76values are ignored, and other situations where reads from shared variables 77are not an integral part of the core concurrency design. 78 79In fact, use of data_race() instead READ_ONCE() for these diagnostic 80reads can enable better checking of the remaining accesses implementing 81the core concurrency design. For example, suppose that the core design 82prevents any non-diagnostic reads from shared variable x from running 83concurrently with updates to x. Then using plain C-language writes 84to x allows KCSAN to detect reads from x from within regions of code 85that fail to exclude the updates. In this case, it is important to use 86data_race() for the diagnostic reads because otherwise KCSAN would give 87false-positive warnings about these diagnostic reads. 88 89In theory, plain C-language loads can also be used for this use case. 90However, in practice this will have the disadvantage of causing KCSAN 91to generate false positives because KCSAN will have no way of knowing 92that the resulting data race was intentional. 93 94 95Data-Racy Reads That Are Checked Against Marked Reload 96 97The values from some reads are not implicitly trusted. They are instead 98fed into some operation that checks the full value against a later marked 99load from memory, which means that the occasional arbitrarily bogus value 100is not a problem. For example, if a bogus value is fed into cmpxchg(), 101all that happens is that this cmpxchg() fails, which normally results 102in a retry. Unless the race condition that resulted in the bogus value 103recurs, this retry will with high probability succeed, so no harm done. 104 105However, please keep in mind that a data_race() load feeding into 106a cmpxchg_relaxed() might still be subject to load fusing on some 107architectures. Therefore, it is best to capture the return value from 108the failing cmpxchg() for the next iteration of the loop, an approach 109that provides the compiler much less scope for mischievous optimizations. 110Capturing the return value from cmpxchg() also saves a memory reference 111in many cases. 112 113In theory, plain C-language loads can also be used for this use case. 114However, in practice this will have the disadvantage of causing KCSAN 115to generate false positives because KCSAN will have no way of knowing 116that the resulting data race was intentional. 117 118 119Reads Feeding Into Error-Tolerant Heuristics 120 121Values from some reads feed into heuristics that can tolerate occasional 122errors. Such reads can use data_race(), thus allowing KCSAN to focus on 123the other accesses to the relevant shared variables. But please note 124that data_race() loads are subject to load fusing, which can result in 125consistent errors, which in turn are quite capable of breaking heuristics. 126Therefore use of data_race() should be limited to cases where some other 127code (such as a barrier() call) will force the occasional reload. 128 129In theory, plain C-language loads can also be used for this use case. 130However, in practice this will have the disadvantage of causing KCSAN 131to generate false positives because KCSAN will have no way of knowing 132that the resulting data race was intentional. 133 134 135Writes Setting Values Feeding Into Error-Tolerant Heuristics 136 137The values read into error-tolerant heuristics come from somewhere, 138for example, from sysfs. This means that some code in sysfs writes 139to this same variable, and these writes can also use data_race(). 140After all, if the heuristic can tolerate the occasional bogus value 141due to compiler-mangled reads, it can also tolerate the occasional 142compiler-mangled write, at least assuming that the proper value is in 143place once the write completes. 144 145Plain C-language stores can also be used for this use case. However, 146in kernels built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n, this 147will have the disadvantage of causing KCSAN to generate false positives 148because KCSAN will have no way of knowing that the resulting data race 149was intentional. 150 151 152Use of Plain C-Language Accesses 153-------------------------------- 154 155Here are some example situations where plain C-language accesses should 156used instead of READ_ONCE(), WRITE_ONCE(), and data_race(): 157 1581. Accesses protected by mutual exclusion, including strict locking 159 and sequence locking. 160 1612. 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. 166 1673. Per-CPU variables that are not accessed from other CPUs. 168 1694. Private per-task variables, including on-stack variables, some 170 fields in the task_struct structure, and task-private heap data. 171 1725. Any other loads for which there is not supposed to be a concurrent 173 store to that same variable. 174 1756. Any other stores for which there should be neither concurrent 176 loads nor concurrent stores to that same variable. 177 178 But note that KCSAN makes two explicit exceptions to this rule 179 by default, refraining from flagging plain C-language stores: 180 181 a. No matter what. You can override this default by building 182 with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n. 183 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. 187 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. 191 192Note that it is important to use plain C-language accesses in these cases, 193because doing otherwise prevents KCSAN from detecting violations of your 194code's synchronization rules. 195 196 197ACCESS-DOCUMENTATION OPTIONS 198============================ 199 200It is important to comment marked accesses so that people reading your 201code, yourself included, are reminded of the synchronization design. 202However, it is even more important to comment plain C-language accesses 203that are intentionally involved in data races. Such comments are 204needed to remind people reading your code, again, yourself included, 205of how the compiler has been prevented from optimizing those accesses 206into concurrency bugs. 207 208It is also possible to tell KCSAN about your synchronization design. 209For example, ASSERT_EXCLUSIVE_ACCESS(foo) tells KCSAN that any 210concurrent access to variable foo by any other CPU is an error, even 211if that concurrent access is marked with READ_ONCE(). In addition, 212ASSERT_EXCLUSIVE_WRITER(foo) tells KCSAN that although it is OK for there 213to be concurrent reads from foo from other CPUs, it is an error for some 214other CPU to be concurrently writing to foo, even if that concurrent 215write is marked with data_race() or WRITE_ONCE(). 216 217Note that although KCSAN will call out data races involving either 218ASSERT_EXCLUSIVE_ACCESS() or ASSERT_EXCLUSIVE_WRITER() on the one hand 219and data_race() writes on the other, KCSAN will not report the location 220of these data_race() writes. 221 222 223EXAMPLES 224======== 225 226As noted earlier, the goal is to prevent the compiler from destroying 227your concurrent algorithm, to help the human reader, and to inform 228KCSAN of aspects of your concurrency design. This section looks at a 229few examples showing how this can be done. 230 231 232Lock Protection With Lockless Diagnostic Access 233----------------------------------------------- 234 235For example, suppose a shared variable "foo" is read only while a 236reader-writer spinlock is read-held, written only while that same 237spinlock is write-held, except that it is also read locklessly for 238diagnostic purposes. The code might look as follows: 239 240 int foo; 241 DEFINE_RWLOCK(foo_rwlock); 242 243 void update_foo(int newval) 244 { 245 write_lock(&foo_rwlock); 246 foo = newval; 247 do_something(newval); 248 write_unlock(&foo_rwlock); 249 } 250 251 int read_foo(void) 252 { 253 int ret; 254 255 read_lock(&foo_rwlock); 256 do_something_else(); 257 ret = foo; 258 read_unlock(&foo_rwlock); 259 return ret; 260 } 261 262 void read_foo_diagnostic(void) 263 { 264 pr_info("Current value of foo: %d\n", data_race(foo)); 265 } 266 267The reader-writer lock prevents the compiler from introducing concurrency 268bugs into any part of the main algorithm using foo, which means that 269the accesses to foo within both update_foo() and read_foo() can (and 270should) be plain C-language accesses. One benefit of making them be 271plain C-language accesses is that KCSAN can detect any erroneous lockless 272reads from or updates to foo. The data_race() in read_foo_diagnostic() 273tells KCSAN that data races are expected, and should be silently 274ignored. This data_race() also tells the human reading the code that 275read_foo_diagnostic() might sometimes return a bogus value. 276 277However, please note that your kernel must be built with 278CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n in order for KCSAN to 279detect a buggy lockless write. If you need KCSAN to detect such a 280write even if that write did not change the value of foo, you also 281need CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=n. If you need KCSAN to 282detect such a write happening in an interrupt handler running on the 283same CPU doing the legitimate lock-protected write, you also need 284CONFIG_KCSAN_INTERRUPT_WATCHER=y. With some or all of these Kconfig 285options set properly, KCSAN can be quite helpful, although it is not 286necessarily a full replacement for hardware watchpoints. On the other 287hand, neither are hardware watchpoints a full replacement for KCSAN 288because it is not always easy to tell hardware watchpoint to conditionally 289trap on accesses. 290 291 292Lock-Protected Writes With Lockless Reads 293----------------------------------------- 294 295For another example, suppose a shared variable "foo" is updated only 296while holding a spinlock, but is read locklessly. The code might look 297as follows: 298 299 int foo; 300 DEFINE_SPINLOCK(foo_lock); 301 302 void update_foo(int newval) 303 { 304 spin_lock(&foo_lock); 305 WRITE_ONCE(foo, newval); 306 ASSERT_EXCLUSIVE_WRITER(foo); 307 do_something(newval); 308 spin_unlock(&foo_wlock); 309 } 310 311 int read_foo(void) 312 { 313 do_something_else(); 314 return READ_ONCE(foo); 315 } 316 317Because foo is read locklessly, all accesses are marked. The purpose 318of the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy 319concurrent lockless write. 320 321 322Lock-Protected Writes With Heuristic Lockless Reads 323--------------------------------------------------- 324 325For another example, suppose that the code can normally make use of 326a per-data-structure lock, but there are times when a global lock 327is required. These times are indicated via a global flag. The code 328might look as follows, and is based loosely on nf_conntrack_lock(), 329nf_conntrack_all_lock(), and nf_conntrack_all_unlock(): 330 331 bool global_flag; 332 DEFINE_SPINLOCK(global_lock); 333 struct foo { 334 spinlock_t f_lock; 335 int f_data; 336 }; 337 338 /* All foo structures are in the following array. */ 339 int nfoo; 340 struct foo *foo_array; 341 342 void do_something_locked(struct foo *fp) 343 { 344 /* This works even if data_race() returns nonsense. */ 345 if (!data_race(global_flag)) { 346 spin_lock(&fp->f_lock); 347 if (!smp_load_acquire(&global_flag)) { 348 do_something(fp); 349 spin_unlock(&fp->f_lock); 350 return; 351 } 352 spin_unlock(&fp->f_lock); 353 } 354 spin_lock(&global_lock); 355 /* global_lock held, thus global flag cannot be set. */ 356 spin_lock(&fp->f_lock); 357 spin_unlock(&global_lock); 358 /* 359 * global_flag might be set here, but begin_global() 360 * will wait for ->f_lock to be released. 361 */ 362 do_something(fp); 363 spin_unlock(&fp->f_lock); 364 } 365 366 void begin_global(void) 367 { 368 int i; 369 370 spin_lock(&global_lock); 371 WRITE_ONCE(global_flag, true); 372 for (i = 0; i < nfoo; i++) { 373 /* 374 * Wait for pre-existing local locks. One at 375 * a time to avoid lockdep limitations. 376 */ 377 spin_lock(&fp->f_lock); 378 spin_unlock(&fp->f_lock); 379 } 380 } 381 382 void end_global(void) 383 { 384 smp_store_release(&global_flag, false); 385 spin_unlock(&global_lock); 386 } 387 388All code paths leading from the do_something_locked() function's first 389read from global_flag acquire a lock, so endless load fusing cannot 390happen. 391 392If the value read from global_flag is true, then global_flag is 393rechecked while holding ->f_lock, which, if global_flag is now false, 394prevents begin_global() from completing. It is therefore safe to invoke 395do_something(). 396 397Otherwise, if either value read from global_flag is true, then after 398global_lock is acquired global_flag must be false. The acquisition of 399->f_lock will prevent any call to begin_global() from returning, which 400means that it is safe to release global_lock and invoke do_something(). 401 402For this to work, only those foo structures in foo_array[] may be passed 403to do_something_locked(). The reason for this is that the synchronization 404with begin_global() relies on momentarily holding the lock of each and 405every foo structure. 406 407The smp_load_acquire() and smp_store_release() are required because 408changes to a foo structure between calls to begin_global() and 409end_global() are carried out without holding that structure's ->f_lock. 410The smp_load_acquire() and smp_store_release() ensure that the next 411invocation of do_something() from do_something_locked() will see those 412changes. 413 414 415Lockless Reads and Writes 416------------------------- 417 418For another example, suppose a shared variable "foo" is both read and 419updated locklessly. The code might look as follows: 420 421 int foo; 422 423 int update_foo(int newval) 424 { 425 int ret; 426 427 ret = xchg(&foo, newval); 428 do_something(newval); 429 return ret; 430 } 431 432 int read_foo(void) 433 { 434 do_something_else(); 435 return READ_ONCE(foo); 436 } 437 438Because foo is accessed locklessly, all accesses are marked. It does 439not make sense to use ASSERT_EXCLUSIVE_WRITER() in this case because 440there really can be concurrent lockless writers. KCSAN would 441flag any concurrent plain C-language reads from foo, and given 442CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n, also any concurrent plain 443C-language writes to foo. 444 445 446Lockless Reads and Writes, But With Single-Threaded Initialization 447------------------------------------------------------------------ 448 449For yet another example, suppose that foo is initialized in a 450single-threaded manner, but that a number of kthreads are then created 451that locklessly and concurrently access foo. Some snippets of this code 452might look as follows: 453 454 int foo; 455 456 void initialize_foo(int initval, int nkthreads) 457 { 458 int i; 459 460 foo = initval; 461 ASSERT_EXCLUSIVE_ACCESS(foo); 462 for (i = 0; i < nkthreads; i++) 463 kthread_run(access_foo_concurrently, ...); 464 } 465 466 /* Called from access_foo_concurrently(). */ 467 int update_foo(int newval) 468 { 469 int ret; 470 471 ret = xchg(&foo, newval); 472 do_something(newval); 473 return ret; 474 } 475 476 /* Also called from access_foo_concurrently(). */ 477 int read_foo(void) 478 { 479 do_something_else(); 480 return READ_ONCE(foo); 481 } 482 483The initialize_foo() uses a plain C-language write to foo because there 484are not supposed to be concurrent accesses during initialization. The 485ASSERT_EXCLUSIVE_ACCESS() allows KCSAN to flag buggy concurrent unmarked 486reads, and the ASSERT_EXCLUSIVE_ACCESS() call further allows KCSAN to 487flag buggy concurrent writes, even if: (1) Those writes are marked or 488(2) The kernel was built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=y. 489 490 491Checking Stress-Test Race Coverage 492---------------------------------- 493 494When designing stress tests it is important to ensure that race conditions 495of interest really do occur. For example, consider the following code 496fragment: 497 498 int foo; 499 500 int update_foo(int newval) 501 { 502 return xchg(&foo, newval); 503 } 504 505 int xor_shift_foo(int shift, int mask) 506 { 507 int old, new, newold; 508 509 newold = data_race(foo); /* Checked by cmpxchg(). */ 510 do { 511 old = newold; 512 new = (old << shift) ^ mask; 513 newold = cmpxchg(&foo, old, new); 514 } while (newold != old); 515 return old; 516 } 517 518 int read_foo(void) 519 { 520 return READ_ONCE(foo); 521 } 522 523If it is possible for update_foo(), xor_shift_foo(), and read_foo() to be 524invoked concurrently, the stress test should force this concurrency to 525actually happen. KCSAN can evaluate the stress test when the above code 526is modified to read as follows: 527 528 int foo; 529 530 int update_foo(int newval) 531 { 532 ASSERT_EXCLUSIVE_ACCESS(foo); 533 return xchg(&foo, newval); 534 } 535 536 int xor_shift_foo(int shift, int mask) 537 { 538 int old, new, newold; 539 540 newold = data_race(foo); /* Checked by cmpxchg(). */ 541 do { 542 old = newold; 543 new = (old << shift) ^ mask; 544 ASSERT_EXCLUSIVE_ACCESS(foo); 545 newold = cmpxchg(&foo, old, new); 546 } while (newold != old); 547 return old; 548 } 549 550 551 int read_foo(void) 552 { 553 ASSERT_EXCLUSIVE_ACCESS(foo); 554 return READ_ONCE(foo); 555 } 556 557If a given stress-test run does not result in KCSAN complaints from 558each possible pair of ASSERT_EXCLUSIVE_ACCESS() invocations, the 559stress test needs improvement. If the stress test was to be evaluated 560on a regular basis, it would be wise to place the above instances of 561ASSERT_EXCLUSIVE_ACCESS() under #ifdef so that they did not result in 562false positives when not evaluating the stress test. 563 564 565REFERENCES 566========== 567 568[1] "Concurrency bugs should fear the big bad data-race detector (part 2)" 569 https://lwn.net/Articles/816854/ 570 571[2] "Who's afraid of a big bad optimizing compiler?" 572 https://lwn.net/Articles/793253/ 573