149ab51b0SPaul E. McKenneyMARKING SHARED-MEMORY ACCESSES 249ab51b0SPaul E. McKenney============================== 349ab51b0SPaul E. McKenney 449ab51b0SPaul E. McKenneyThis document provides guidelines for marking intentionally concurrent 549ab51b0SPaul E. McKenneynormal accesses to shared memory, that is "normal" as in accesses that do 649ab51b0SPaul E. McKenneynot use read-modify-write atomic operations. It also describes how to 749ab51b0SPaul E. McKenneydocument these accesses, both with comments and with special assertions 849ab51b0SPaul E. McKenneyprocessed by the Kernel Concurrency Sanitizer (KCSAN). This discussion 949ab51b0SPaul E. McKenneybuilds on an earlier LWN article [1]. 1049ab51b0SPaul E. McKenney 1149ab51b0SPaul E. McKenney 1249ab51b0SPaul E. McKenneyACCESS-MARKING OPTIONS 1349ab51b0SPaul E. McKenney====================== 1449ab51b0SPaul E. McKenney 1549ab51b0SPaul E. McKenneyThe Linux kernel provides the following access-marking options: 1649ab51b0SPaul E. McKenney 1749ab51b0SPaul E. McKenney1. Plain C-language accesses (unmarked), for example, "a = b;" 1849ab51b0SPaul E. McKenney 1949ab51b0SPaul E. McKenney2. Data-race marking, for example, "data_race(a = b);" 2049ab51b0SPaul E. McKenney 2149ab51b0SPaul E. McKenney3. READ_ONCE(), for example, "a = READ_ONCE(b);" 2249ab51b0SPaul E. McKenney The various forms of atomic_read() also fit in here. 2349ab51b0SPaul E. McKenney 2449ab51b0SPaul E. McKenney4. WRITE_ONCE(), for example, "WRITE_ONCE(a, b);" 2549ab51b0SPaul E. McKenney The various forms of atomic_set() also fit in here. 2649ab51b0SPaul E. McKenney 2749ab51b0SPaul E. McKenney 2849ab51b0SPaul E. McKenneyThese may be used in combination, as shown in this admittedly improbable 2949ab51b0SPaul E. McKenneyexample: 3049ab51b0SPaul E. McKenney 3149ab51b0SPaul E. McKenney WRITE_ONCE(a, b + data_race(c + d) + READ_ONCE(e)); 3249ab51b0SPaul E. McKenney 3349ab51b0SPaul E. McKenneyNeither plain C-language accesses nor data_race() (#1 and #2 above) place 3449ab51b0SPaul E. McKenneyany sort of constraint on the compiler's choice of optimizations [2]. 3549ab51b0SPaul E. McKenneyIn contrast, READ_ONCE() and WRITE_ONCE() (#3 and #4 above) restrict the 3649ab51b0SPaul E. McKenneycompiler's use of code-motion and common-subexpression optimizations. 3749ab51b0SPaul E. McKenneyTherefore, if a given access is involved in an intentional data race, 3849ab51b0SPaul E. McKenneyusing READ_ONCE() for loads and WRITE_ONCE() for stores is usually 3949ab51b0SPaul E. McKenneypreferable to data_race(), which in turn is usually preferable to plain 4049ab51b0SPaul E. McKenneyC-language accesses. 4149ab51b0SPaul E. McKenney 4249ab51b0SPaul E. McKenneyKCSAN will complain about many types of data races involving plain 4349ab51b0SPaul E. McKenneyC-language accesses, but marking all accesses involved in a given data 4449ab51b0SPaul E. McKenneyrace with one of data_race(), READ_ONCE(), or WRITE_ONCE(), will prevent 4549ab51b0SPaul E. McKenneyKCSAN from complaining. Of course, lack of KCSAN complaints does not 4649ab51b0SPaul E. McKenneyimply correct code. Therefore, please take a thoughtful approach 4749ab51b0SPaul E. McKenneywhen responding to KCSAN complaints. Churning the code base with 4849ab51b0SPaul E. McKenneyill-considered additions of data_race(), READ_ONCE(), and WRITE_ONCE() 4949ab51b0SPaul E. McKenneyis unhelpful. 5049ab51b0SPaul E. McKenney 5149ab51b0SPaul E. McKenneyIn fact, the following sections describe situations where use of 5249ab51b0SPaul E. McKenneydata_race() and even plain C-language accesses is preferable to 5349ab51b0SPaul E. McKenneyREAD_ONCE() and WRITE_ONCE(). 5449ab51b0SPaul E. McKenney 5549ab51b0SPaul E. McKenney 5649ab51b0SPaul E. McKenneyUse of the data_race() Macro 5749ab51b0SPaul E. McKenney---------------------------- 5849ab51b0SPaul E. McKenney 5949ab51b0SPaul E. McKenneyHere are some situations where data_race() should be used instead of 6049ab51b0SPaul E. McKenneyREAD_ONCE() and WRITE_ONCE(): 6149ab51b0SPaul E. McKenney 6249ab51b0SPaul E. McKenney1. Data-racy loads from shared variables whose values are used only 6349ab51b0SPaul E. McKenney for diagnostic purposes. 6449ab51b0SPaul E. McKenney 6549ab51b0SPaul E. McKenney2. Data-racy reads whose values are checked against marked reload. 6649ab51b0SPaul E. McKenney 6749ab51b0SPaul E. McKenney3. Reads whose values feed into error-tolerant heuristics. 6849ab51b0SPaul E. McKenney 6949ab51b0SPaul E. McKenney4. Writes setting values that feed into error-tolerant heuristics. 7049ab51b0SPaul E. McKenney 7149ab51b0SPaul E. McKenney 7249ab51b0SPaul E. McKenneyData-Racy Reads for Approximate Diagnostics 7349ab51b0SPaul E. McKenney 7449ab51b0SPaul E. McKenneyApproximate diagnostics include lockdep reports, monitoring/statistics 7549ab51b0SPaul E. McKenney(including /proc and /sys output), WARN*()/BUG*() checks whose return 7649ab51b0SPaul E. McKenneyvalues are ignored, and other situations where reads from shared variables 7749ab51b0SPaul E. McKenneyare not an integral part of the core concurrency design. 7849ab51b0SPaul E. McKenney 7949ab51b0SPaul E. McKenneyIn fact, use of data_race() instead READ_ONCE() for these diagnostic 8049ab51b0SPaul E. McKenneyreads can enable better checking of the remaining accesses implementing 8149ab51b0SPaul E. McKenneythe core concurrency design. For example, suppose that the core design 8249ab51b0SPaul E. McKenneyprevents any non-diagnostic reads from shared variable x from running 8349ab51b0SPaul E. McKenneyconcurrently with updates to x. Then using plain C-language writes 8449ab51b0SPaul E. McKenneyto x allows KCSAN to detect reads from x from within regions of code 8549ab51b0SPaul E. McKenneythat fail to exclude the updates. In this case, it is important to use 8649ab51b0SPaul E. McKenneydata_race() for the diagnostic reads because otherwise KCSAN would give 8749ab51b0SPaul E. McKenneyfalse-positive warnings about these diagnostic reads. 8849ab51b0SPaul E. McKenney 8949ab51b0SPaul E. McKenneyIn theory, plain C-language loads can also be used for this use case. 9049ab51b0SPaul E. McKenneyHowever, in practice this will have the disadvantage of causing KCSAN 9149ab51b0SPaul E. McKenneyto generate false positives because KCSAN will have no way of knowing 9249ab51b0SPaul E. McKenneythat the resulting data race was intentional. 9349ab51b0SPaul E. McKenney 9449ab51b0SPaul E. McKenney 9549ab51b0SPaul E. McKenneyData-Racy Reads That Are Checked Against Marked Reload 9649ab51b0SPaul E. McKenney 9749ab51b0SPaul E. McKenneyThe values from some reads are not implicitly trusted. They are instead 9849ab51b0SPaul E. McKenneyfed into some operation that checks the full value against a later marked 9949ab51b0SPaul E. McKenneyload from memory, which means that the occasional arbitrarily bogus value 10049ab51b0SPaul E. McKenneyis not a problem. For example, if a bogus value is fed into cmpxchg(), 10149ab51b0SPaul E. McKenneyall that happens is that this cmpxchg() fails, which normally results 10249ab51b0SPaul E. McKenneyin a retry. Unless the race condition that resulted in the bogus value 10349ab51b0SPaul E. McKenneyrecurs, this retry will with high probability succeed, so no harm done. 10449ab51b0SPaul E. McKenney 10549ab51b0SPaul E. McKenneyHowever, please keep in mind that a data_race() load feeding into 10649ab51b0SPaul E. McKenneya cmpxchg_relaxed() might still be subject to load fusing on some 10749ab51b0SPaul E. McKenneyarchitectures. Therefore, it is best to capture the return value from 10849ab51b0SPaul E. McKenneythe failing cmpxchg() for the next iteration of the loop, an approach 10949ab51b0SPaul E. McKenneythat provides the compiler much less scope for mischievous optimizations. 11049ab51b0SPaul E. McKenneyCapturing the return value from cmpxchg() also saves a memory reference 11149ab51b0SPaul E. McKenneyin many cases. 11249ab51b0SPaul E. McKenney 11349ab51b0SPaul E. McKenneyIn theory, plain C-language loads can also be used for this use case. 11449ab51b0SPaul E. McKenneyHowever, in practice this will have the disadvantage of causing KCSAN 11549ab51b0SPaul E. McKenneyto generate false positives because KCSAN will have no way of knowing 11649ab51b0SPaul E. McKenneythat the resulting data race was intentional. 11749ab51b0SPaul E. McKenney 11849ab51b0SPaul E. McKenney 11949ab51b0SPaul E. McKenneyReads Feeding Into Error-Tolerant Heuristics 12049ab51b0SPaul E. McKenney 12149ab51b0SPaul E. McKenneyValues from some reads feed into heuristics that can tolerate occasional 12249ab51b0SPaul E. McKenneyerrors. Such reads can use data_race(), thus allowing KCSAN to focus on 12349ab51b0SPaul E. McKenneythe other accesses to the relevant shared variables. But please note 12449ab51b0SPaul E. McKenneythat data_race() loads are subject to load fusing, which can result in 12549ab51b0SPaul E. McKenneyconsistent errors, which in turn are quite capable of breaking heuristics. 12649ab51b0SPaul E. McKenneyTherefore use of data_race() should be limited to cases where some other 12749ab51b0SPaul E. McKenneycode (such as a barrier() call) will force the occasional reload. 12849ab51b0SPaul E. McKenney 12949ab51b0SPaul E. McKenneyIn theory, plain C-language loads can also be used for this use case. 13049ab51b0SPaul E. McKenneyHowever, in practice this will have the disadvantage of causing KCSAN 13149ab51b0SPaul E. McKenneyto generate false positives because KCSAN will have no way of knowing 13249ab51b0SPaul E. McKenneythat the resulting data race was intentional. 13349ab51b0SPaul E. McKenney 13449ab51b0SPaul E. McKenney 13549ab51b0SPaul E. McKenneyWrites Setting Values Feeding Into Error-Tolerant Heuristics 13649ab51b0SPaul E. McKenney 13749ab51b0SPaul E. McKenneyThe values read into error-tolerant heuristics come from somewhere, 13849ab51b0SPaul E. McKenneyfor example, from sysfs. This means that some code in sysfs writes 13949ab51b0SPaul E. McKenneyto this same variable, and these writes can also use data_race(). 14049ab51b0SPaul E. McKenneyAfter all, if the heuristic can tolerate the occasional bogus value 14149ab51b0SPaul E. McKenneydue to compiler-mangled reads, it can also tolerate the occasional 14249ab51b0SPaul E. McKenneycompiler-mangled write, at least assuming that the proper value is in 14349ab51b0SPaul E. McKenneyplace once the write completes. 14449ab51b0SPaul E. McKenney 14549ab51b0SPaul E. McKenneyPlain C-language stores can also be used for this use case. However, 14649ab51b0SPaul E. McKenneyin kernels built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n, this 14749ab51b0SPaul E. McKenneywill have the disadvantage of causing KCSAN to generate false positives 14849ab51b0SPaul E. McKenneybecause KCSAN will have no way of knowing that the resulting data race 14949ab51b0SPaul E. McKenneywas intentional. 15049ab51b0SPaul E. McKenney 15149ab51b0SPaul E. McKenney 15249ab51b0SPaul E. McKenneyUse of Plain C-Language Accesses 15349ab51b0SPaul E. McKenney-------------------------------- 15449ab51b0SPaul E. McKenney 15549ab51b0SPaul E. McKenneyHere are some example situations where plain C-language accesses should 15649ab51b0SPaul E. McKenneyused instead of READ_ONCE(), WRITE_ONCE(), and data_race(): 15749ab51b0SPaul E. McKenney 15849ab51b0SPaul E. McKenney1. Accesses protected by mutual exclusion, including strict locking 15949ab51b0SPaul E. McKenney and sequence locking. 16049ab51b0SPaul E. McKenney 16149ab51b0SPaul E. McKenney2. Initialization-time and cleanup-time accesses. This covers a 16249ab51b0SPaul E. McKenney wide variety of situations, including the uniprocessor phase of 16349ab51b0SPaul E. McKenney system boot, variables to be used by not-yet-spawned kthreads, 16449ab51b0SPaul E. McKenney structures not yet published to reference-counted or RCU-protected 16549ab51b0SPaul E. McKenney data structures, and the cleanup side of any of these situations. 16649ab51b0SPaul E. McKenney 16749ab51b0SPaul E. McKenney3. Per-CPU variables that are not accessed from other CPUs. 16849ab51b0SPaul E. McKenney 16949ab51b0SPaul E. McKenney4. Private per-task variables, including on-stack variables, some 17049ab51b0SPaul E. McKenney fields in the task_struct structure, and task-private heap data. 17149ab51b0SPaul E. McKenney 17249ab51b0SPaul E. McKenney5. Any other loads for which there is not supposed to be a concurrent 17349ab51b0SPaul E. McKenney store to that same variable. 17449ab51b0SPaul E. McKenney 17549ab51b0SPaul E. McKenney6. Any other stores for which there should be neither concurrent 17649ab51b0SPaul E. McKenney loads nor concurrent stores to that same variable. 17749ab51b0SPaul E. McKenney 17849ab51b0SPaul E. McKenney But note that KCSAN makes two explicit exceptions to this rule 17949ab51b0SPaul E. McKenney by default, refraining from flagging plain C-language stores: 18049ab51b0SPaul E. McKenney 18149ab51b0SPaul E. McKenney a. No matter what. You can override this default by building 18249ab51b0SPaul E. McKenney with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n. 18349ab51b0SPaul E. McKenney 18449ab51b0SPaul E. McKenney b. When the store writes the value already contained in 18549ab51b0SPaul E. McKenney that variable. You can override this default by building 18649ab51b0SPaul E. McKenney with CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=n. 18749ab51b0SPaul E. McKenney 18849ab51b0SPaul E. McKenney c. When one of the stores is in an interrupt handler and 18949ab51b0SPaul E. McKenney the other in the interrupted code. You can override this 19049ab51b0SPaul E. McKenney default by building with CONFIG_KCSAN_INTERRUPT_WATCHER=y. 19149ab51b0SPaul E. McKenney 19249ab51b0SPaul E. McKenneyNote that it is important to use plain C-language accesses in these cases, 19349ab51b0SPaul E. McKenneybecause doing otherwise prevents KCSAN from detecting violations of your 19449ab51b0SPaul E. McKenneycode's synchronization rules. 19549ab51b0SPaul E. McKenney 19649ab51b0SPaul E. McKenney 19749ab51b0SPaul E. McKenneyACCESS-DOCUMENTATION OPTIONS 19849ab51b0SPaul E. McKenney============================ 19949ab51b0SPaul E. McKenney 20049ab51b0SPaul E. McKenneyIt is important to comment marked accesses so that people reading your 20149ab51b0SPaul E. McKenneycode, yourself included, are reminded of the synchronization design. 20249ab51b0SPaul E. McKenneyHowever, it is even more important to comment plain C-language accesses 20349ab51b0SPaul E. McKenneythat are intentionally involved in data races. Such comments are 20449ab51b0SPaul E. McKenneyneeded to remind people reading your code, again, yourself included, 20549ab51b0SPaul E. McKenneyof how the compiler has been prevented from optimizing those accesses 20649ab51b0SPaul E. McKenneyinto concurrency bugs. 20749ab51b0SPaul E. McKenney 20849ab51b0SPaul E. McKenneyIt is also possible to tell KCSAN about your synchronization design. 20949ab51b0SPaul E. McKenneyFor example, ASSERT_EXCLUSIVE_ACCESS(foo) tells KCSAN that any 21049ab51b0SPaul E. McKenneyconcurrent access to variable foo by any other CPU is an error, even 21149ab51b0SPaul E. McKenneyif that concurrent access is marked with READ_ONCE(). In addition, 21249ab51b0SPaul E. McKenneyASSERT_EXCLUSIVE_WRITER(foo) tells KCSAN that although it is OK for there 21349ab51b0SPaul E. McKenneyto be concurrent reads from foo from other CPUs, it is an error for some 21449ab51b0SPaul E. McKenneyother CPU to be concurrently writing to foo, even if that concurrent 21549ab51b0SPaul E. McKenneywrite is marked with data_race() or WRITE_ONCE(). 21649ab51b0SPaul E. McKenney 21749ab51b0SPaul E. McKenneyNote that although KCSAN will call out data races involving either 21849ab51b0SPaul E. McKenneyASSERT_EXCLUSIVE_ACCESS() or ASSERT_EXCLUSIVE_WRITER() on the one hand 21949ab51b0SPaul E. McKenneyand data_race() writes on the other, KCSAN will not report the location 22049ab51b0SPaul E. McKenneyof these data_race() writes. 22149ab51b0SPaul E. McKenney 22249ab51b0SPaul E. McKenney 22349ab51b0SPaul E. McKenneyEXAMPLES 22449ab51b0SPaul E. McKenney======== 22549ab51b0SPaul E. McKenney 22649ab51b0SPaul E. McKenneyAs noted earlier, the goal is to prevent the compiler from destroying 22749ab51b0SPaul E. McKenneyyour concurrent algorithm, to help the human reader, and to inform 22849ab51b0SPaul E. McKenneyKCSAN of aspects of your concurrency design. This section looks at a 22949ab51b0SPaul E. McKenneyfew examples showing how this can be done. 23049ab51b0SPaul E. McKenney 23149ab51b0SPaul E. McKenney 23249ab51b0SPaul E. McKenneyLock Protection With Lockless Diagnostic Access 23349ab51b0SPaul E. McKenney----------------------------------------------- 23449ab51b0SPaul E. McKenney 23549ab51b0SPaul E. McKenneyFor example, suppose a shared variable "foo" is read only while a 23649ab51b0SPaul E. McKenneyreader-writer spinlock is read-held, written only while that same 23749ab51b0SPaul E. McKenneyspinlock is write-held, except that it is also read locklessly for 23849ab51b0SPaul E. McKenneydiagnostic purposes. The code might look as follows: 23949ab51b0SPaul E. McKenney 24049ab51b0SPaul E. McKenney int foo; 24149ab51b0SPaul E. McKenney DEFINE_RWLOCK(foo_rwlock); 24249ab51b0SPaul E. McKenney 24349ab51b0SPaul E. McKenney void update_foo(int newval) 24449ab51b0SPaul E. McKenney { 24549ab51b0SPaul E. McKenney write_lock(&foo_rwlock); 24649ab51b0SPaul E. McKenney foo = newval; 24749ab51b0SPaul E. McKenney do_something(newval); 24849ab51b0SPaul E. McKenney write_unlock(&foo_rwlock); 24949ab51b0SPaul E. McKenney } 25049ab51b0SPaul E. McKenney 25149ab51b0SPaul E. McKenney int read_foo(void) 25249ab51b0SPaul E. McKenney { 25349ab51b0SPaul E. McKenney int ret; 25449ab51b0SPaul E. McKenney 25549ab51b0SPaul E. McKenney read_lock(&foo_rwlock); 25649ab51b0SPaul E. McKenney do_something_else(); 25749ab51b0SPaul E. McKenney ret = foo; 25849ab51b0SPaul E. McKenney read_unlock(&foo_rwlock); 25949ab51b0SPaul E. McKenney return ret; 26049ab51b0SPaul E. McKenney } 26149ab51b0SPaul E. McKenney 2621846a7faSPaul E. McKenney void read_foo_diagnostic(void) 26349ab51b0SPaul E. McKenney { 2641846a7faSPaul E. McKenney pr_info("Current value of foo: %d\n", data_race(foo)); 26549ab51b0SPaul E. McKenney } 26649ab51b0SPaul E. McKenney 26749ab51b0SPaul E. McKenneyThe reader-writer lock prevents the compiler from introducing concurrency 26849ab51b0SPaul E. McKenneybugs into any part of the main algorithm using foo, which means that 26949ab51b0SPaul E. McKenneythe accesses to foo within both update_foo() and read_foo() can (and 27049ab51b0SPaul E. McKenneyshould) be plain C-language accesses. One benefit of making them be 27149ab51b0SPaul E. McKenneyplain C-language accesses is that KCSAN can detect any erroneous lockless 27249ab51b0SPaul E. McKenneyreads from or updates to foo. The data_race() in read_foo_diagnostic() 27349ab51b0SPaul E. McKenneytells KCSAN that data races are expected, and should be silently 27449ab51b0SPaul E. McKenneyignored. This data_race() also tells the human reading the code that 27549ab51b0SPaul E. McKenneyread_foo_diagnostic() might sometimes return a bogus value. 27649ab51b0SPaul E. McKenney 27749ab51b0SPaul E. McKenneyHowever, please note that your kernel must be built with 27849ab51b0SPaul E. McKenneyCONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n in order for KCSAN to 27949ab51b0SPaul E. McKenneydetect a buggy lockless write. If you need KCSAN to detect such a 28049ab51b0SPaul E. McKenneywrite even if that write did not change the value of foo, you also 28149ab51b0SPaul E. McKenneyneed CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=n. If you need KCSAN to 28249ab51b0SPaul E. McKenneydetect such a write happening in an interrupt handler running on the 28349ab51b0SPaul E. McKenneysame CPU doing the legitimate lock-protected write, you also need 28449ab51b0SPaul E. McKenneyCONFIG_KCSAN_INTERRUPT_WATCHER=y. With some or all of these Kconfig 28549ab51b0SPaul E. McKenneyoptions set properly, KCSAN can be quite helpful, although it is not 28649ab51b0SPaul E. McKenneynecessarily a full replacement for hardware watchpoints. On the other 28749ab51b0SPaul E. McKenneyhand, neither are hardware watchpoints a full replacement for KCSAN 28849ab51b0SPaul E. McKenneybecause it is not always easy to tell hardware watchpoint to conditionally 28949ab51b0SPaul E. McKenneytrap on accesses. 29049ab51b0SPaul E. McKenney 29149ab51b0SPaul E. McKenney 29249ab51b0SPaul E. McKenneyLock-Protected Writes With Lockless Reads 29349ab51b0SPaul E. McKenney----------------------------------------- 29449ab51b0SPaul E. McKenney 29549ab51b0SPaul E. McKenneyFor another example, suppose a shared variable "foo" is updated only 29649ab51b0SPaul E. McKenneywhile holding a spinlock, but is read locklessly. The code might look 29749ab51b0SPaul E. McKenneyas follows: 29849ab51b0SPaul E. McKenney 29949ab51b0SPaul E. McKenney int foo; 30049ab51b0SPaul E. McKenney DEFINE_SPINLOCK(foo_lock); 30149ab51b0SPaul E. McKenney 30249ab51b0SPaul E. McKenney void update_foo(int newval) 30349ab51b0SPaul E. McKenney { 30449ab51b0SPaul E. McKenney spin_lock(&foo_lock); 30549ab51b0SPaul E. McKenney WRITE_ONCE(foo, newval); 30649ab51b0SPaul E. McKenney ASSERT_EXCLUSIVE_WRITER(foo); 30749ab51b0SPaul E. McKenney do_something(newval); 30849ab51b0SPaul E. McKenney spin_unlock(&foo_wlock); 30949ab51b0SPaul E. McKenney } 31049ab51b0SPaul E. McKenney 31149ab51b0SPaul E. McKenney int read_foo(void) 31249ab51b0SPaul E. McKenney { 31349ab51b0SPaul E. McKenney do_something_else(); 31449ab51b0SPaul E. McKenney return READ_ONCE(foo); 31549ab51b0SPaul E. McKenney } 31649ab51b0SPaul E. McKenney 31749ab51b0SPaul E. McKenneyBecause foo is read locklessly, all accesses are marked. The purpose 31849ab51b0SPaul E. McKenneyof the ASSERT_EXCLUSIVE_WRITER() is to allow KCSAN to check for a buggy 31949ab51b0SPaul E. McKenneyconcurrent lockless write. 32049ab51b0SPaul E. McKenney 32149ab51b0SPaul E. McKenney 322*436eef23SPaul E. McKenneyLock-Protected Writes With Heuristic Lockless Reads 323*436eef23SPaul E. McKenney--------------------------------------------------- 324*436eef23SPaul E. McKenney 325*436eef23SPaul E. McKenneyFor another example, suppose that the code can normally make use of 326*436eef23SPaul E. McKenneya per-data-structure lock, but there are times when a global lock 327*436eef23SPaul E. McKenneyis required. These times are indicated via a global flag. The code 328*436eef23SPaul E. McKenneymight look as follows, and is based loosely on nf_conntrack_lock(), 329*436eef23SPaul E. McKenneynf_conntrack_all_lock(), and nf_conntrack_all_unlock(): 330*436eef23SPaul E. McKenney 331*436eef23SPaul E. McKenney bool global_flag; 332*436eef23SPaul E. McKenney DEFINE_SPINLOCK(global_lock); 333*436eef23SPaul E. McKenney struct foo { 334*436eef23SPaul E. McKenney spinlock_t f_lock; 335*436eef23SPaul E. McKenney int f_data; 336*436eef23SPaul E. McKenney }; 337*436eef23SPaul E. McKenney 338*436eef23SPaul E. McKenney /* All foo structures are in the following array. */ 339*436eef23SPaul E. McKenney int nfoo; 340*436eef23SPaul E. McKenney struct foo *foo_array; 341*436eef23SPaul E. McKenney 342*436eef23SPaul E. McKenney void do_something_locked(struct foo *fp) 343*436eef23SPaul E. McKenney { 344*436eef23SPaul E. McKenney /* This works even if data_race() returns nonsense. */ 345*436eef23SPaul E. McKenney if (!data_race(global_flag)) { 346*436eef23SPaul E. McKenney spin_lock(&fp->f_lock); 347*436eef23SPaul E. McKenney if (!smp_load_acquire(&global_flag)) { 348*436eef23SPaul E. McKenney do_something(fp); 349*436eef23SPaul E. McKenney spin_unlock(&fp->f_lock); 350*436eef23SPaul E. McKenney return; 351*436eef23SPaul E. McKenney } 352*436eef23SPaul E. McKenney spin_unlock(&fp->f_lock); 353*436eef23SPaul E. McKenney } 354*436eef23SPaul E. McKenney spin_lock(&global_lock); 355*436eef23SPaul E. McKenney /* global_lock held, thus global flag cannot be set. */ 356*436eef23SPaul E. McKenney spin_lock(&fp->f_lock); 357*436eef23SPaul E. McKenney spin_unlock(&global_lock); 358*436eef23SPaul E. McKenney /* 359*436eef23SPaul E. McKenney * global_flag might be set here, but begin_global() 360*436eef23SPaul E. McKenney * will wait for ->f_lock to be released. 361*436eef23SPaul E. McKenney */ 362*436eef23SPaul E. McKenney do_something(fp); 363*436eef23SPaul E. McKenney spin_unlock(&fp->f_lock); 364*436eef23SPaul E. McKenney } 365*436eef23SPaul E. McKenney 366*436eef23SPaul E. McKenney void begin_global(void) 367*436eef23SPaul E. McKenney { 368*436eef23SPaul E. McKenney int i; 369*436eef23SPaul E. McKenney 370*436eef23SPaul E. McKenney spin_lock(&global_lock); 371*436eef23SPaul E. McKenney WRITE_ONCE(global_flag, true); 372*436eef23SPaul E. McKenney for (i = 0; i < nfoo; i++) { 373*436eef23SPaul E. McKenney /* 374*436eef23SPaul E. McKenney * Wait for pre-existing local locks. One at 375*436eef23SPaul E. McKenney * a time to avoid lockdep limitations. 376*436eef23SPaul E. McKenney */ 377*436eef23SPaul E. McKenney spin_lock(&fp->f_lock); 378*436eef23SPaul E. McKenney spin_unlock(&fp->f_lock); 379*436eef23SPaul E. McKenney } 380*436eef23SPaul E. McKenney } 381*436eef23SPaul E. McKenney 382*436eef23SPaul E. McKenney void end_global(void) 383*436eef23SPaul E. McKenney { 384*436eef23SPaul E. McKenney smp_store_release(&global_flag, false); 385*436eef23SPaul E. McKenney spin_unlock(&global_lock); 386*436eef23SPaul E. McKenney } 387*436eef23SPaul E. McKenney 388*436eef23SPaul E. McKenneyAll code paths leading from the do_something_locked() function's first 389*436eef23SPaul E. McKenneyread from global_flag acquire a lock, so endless load fusing cannot 390*436eef23SPaul E. McKenneyhappen. 391*436eef23SPaul E. McKenney 392*436eef23SPaul E. McKenneyIf the value read from global_flag is true, then global_flag is 393*436eef23SPaul E. McKenneyrechecked while holding ->f_lock, which, if global_flag is now false, 394*436eef23SPaul E. McKenneyprevents begin_global() from completing. It is therefore safe to invoke 395*436eef23SPaul E. McKenneydo_something(). 396*436eef23SPaul E. McKenney 397*436eef23SPaul E. McKenneyOtherwise, if either value read from global_flag is true, then after 398*436eef23SPaul E. McKenneyglobal_lock is acquired global_flag must be false. The acquisition of 399*436eef23SPaul E. McKenney->f_lock will prevent any call to begin_global() from returning, which 400*436eef23SPaul E. McKenneymeans that it is safe to release global_lock and invoke do_something(). 401*436eef23SPaul E. McKenney 402*436eef23SPaul E. McKenneyFor this to work, only those foo structures in foo_array[] may be passed 403*436eef23SPaul E. McKenneyto do_something_locked(). The reason for this is that the synchronization 404*436eef23SPaul E. McKenneywith begin_global() relies on momentarily holding the lock of each and 405*436eef23SPaul E. McKenneyevery foo structure. 406*436eef23SPaul E. McKenney 407*436eef23SPaul E. McKenneyThe smp_load_acquire() and smp_store_release() are required because 408*436eef23SPaul E. McKenneychanges to a foo structure between calls to begin_global() and 409*436eef23SPaul E. McKenneyend_global() are carried out without holding that structure's ->f_lock. 410*436eef23SPaul E. McKenneyThe smp_load_acquire() and smp_store_release() ensure that the next 411*436eef23SPaul E. McKenneyinvocation of do_something() from do_something_locked() will see those 412*436eef23SPaul E. McKenneychanges. 413*436eef23SPaul E. McKenney 414*436eef23SPaul E. McKenney 41549ab51b0SPaul E. McKenneyLockless Reads and Writes 41649ab51b0SPaul E. McKenney------------------------- 41749ab51b0SPaul E. McKenney 41849ab51b0SPaul E. McKenneyFor another example, suppose a shared variable "foo" is both read and 41949ab51b0SPaul E. McKenneyupdated locklessly. The code might look as follows: 42049ab51b0SPaul E. McKenney 42149ab51b0SPaul E. McKenney int foo; 42249ab51b0SPaul E. McKenney 42349ab51b0SPaul E. McKenney int update_foo(int newval) 42449ab51b0SPaul E. McKenney { 42549ab51b0SPaul E. McKenney int ret; 42649ab51b0SPaul E. McKenney 42749ab51b0SPaul E. McKenney ret = xchg(&foo, newval); 42849ab51b0SPaul E. McKenney do_something(newval); 42949ab51b0SPaul E. McKenney return ret; 43049ab51b0SPaul E. McKenney } 43149ab51b0SPaul E. McKenney 43249ab51b0SPaul E. McKenney int read_foo(void) 43349ab51b0SPaul E. McKenney { 43449ab51b0SPaul E. McKenney do_something_else(); 43549ab51b0SPaul E. McKenney return READ_ONCE(foo); 43649ab51b0SPaul E. McKenney } 43749ab51b0SPaul E. McKenney 43849ab51b0SPaul E. McKenneyBecause foo is accessed locklessly, all accesses are marked. It does 43949ab51b0SPaul E. McKenneynot make sense to use ASSERT_EXCLUSIVE_WRITER() in this case because 44049ab51b0SPaul E. McKenneythere really can be concurrent lockless writers. KCSAN would 44149ab51b0SPaul E. McKenneyflag any concurrent plain C-language reads from foo, and given 44249ab51b0SPaul E. McKenneyCONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=n, also any concurrent plain 44349ab51b0SPaul E. McKenneyC-language writes to foo. 44449ab51b0SPaul E. McKenney 44549ab51b0SPaul E. McKenney 44649ab51b0SPaul E. McKenneyLockless Reads and Writes, But With Single-Threaded Initialization 44749ab51b0SPaul E. McKenney------------------------------------------------------------------ 44849ab51b0SPaul E. McKenney 44949ab51b0SPaul E. McKenneyFor yet another example, suppose that foo is initialized in a 45049ab51b0SPaul E. McKenneysingle-threaded manner, but that a number of kthreads are then created 45149ab51b0SPaul E. McKenneythat locklessly and concurrently access foo. Some snippets of this code 45249ab51b0SPaul E. McKenneymight look as follows: 45349ab51b0SPaul E. McKenney 45449ab51b0SPaul E. McKenney int foo; 45549ab51b0SPaul E. McKenney 45649ab51b0SPaul E. McKenney void initialize_foo(int initval, int nkthreads) 45749ab51b0SPaul E. McKenney { 45849ab51b0SPaul E. McKenney int i; 45949ab51b0SPaul E. McKenney 46049ab51b0SPaul E. McKenney foo = initval; 46149ab51b0SPaul E. McKenney ASSERT_EXCLUSIVE_ACCESS(foo); 46249ab51b0SPaul E. McKenney for (i = 0; i < nkthreads; i++) 46349ab51b0SPaul E. McKenney kthread_run(access_foo_concurrently, ...); 46449ab51b0SPaul E. McKenney } 46549ab51b0SPaul E. McKenney 46649ab51b0SPaul E. McKenney /* Called from access_foo_concurrently(). */ 46749ab51b0SPaul E. McKenney int update_foo(int newval) 46849ab51b0SPaul E. McKenney { 46949ab51b0SPaul E. McKenney int ret; 47049ab51b0SPaul E. McKenney 47149ab51b0SPaul E. McKenney ret = xchg(&foo, newval); 47249ab51b0SPaul E. McKenney do_something(newval); 47349ab51b0SPaul E. McKenney return ret; 47449ab51b0SPaul E. McKenney } 47549ab51b0SPaul E. McKenney 47649ab51b0SPaul E. McKenney /* Also called from access_foo_concurrently(). */ 47749ab51b0SPaul E. McKenney int read_foo(void) 47849ab51b0SPaul E. McKenney { 47949ab51b0SPaul E. McKenney do_something_else(); 48049ab51b0SPaul E. McKenney return READ_ONCE(foo); 48149ab51b0SPaul E. McKenney } 48249ab51b0SPaul E. McKenney 48349ab51b0SPaul E. McKenneyThe initialize_foo() uses a plain C-language write to foo because there 48449ab51b0SPaul E. McKenneyare not supposed to be concurrent accesses during initialization. The 48549ab51b0SPaul E. McKenneyASSERT_EXCLUSIVE_ACCESS() allows KCSAN to flag buggy concurrent unmarked 48649ab51b0SPaul E. McKenneyreads, and the ASSERT_EXCLUSIVE_ACCESS() call further allows KCSAN to 48749ab51b0SPaul E. McKenneyflag buggy concurrent writes, even if: (1) Those writes are marked or 48849ab51b0SPaul E. McKenney(2) The kernel was built with CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC=y. 48949ab51b0SPaul E. McKenney 49049ab51b0SPaul E. McKenney 49149ab51b0SPaul E. McKenneyChecking Stress-Test Race Coverage 49249ab51b0SPaul E. McKenney---------------------------------- 49349ab51b0SPaul E. McKenney 49449ab51b0SPaul E. McKenneyWhen designing stress tests it is important to ensure that race conditions 49549ab51b0SPaul E. McKenneyof interest really do occur. For example, consider the following code 49649ab51b0SPaul E. McKenneyfragment: 49749ab51b0SPaul E. McKenney 49849ab51b0SPaul E. McKenney int foo; 49949ab51b0SPaul E. McKenney 50049ab51b0SPaul E. McKenney int update_foo(int newval) 50149ab51b0SPaul E. McKenney { 50249ab51b0SPaul E. McKenney return xchg(&foo, newval); 50349ab51b0SPaul E. McKenney } 50449ab51b0SPaul E. McKenney 50549ab51b0SPaul E. McKenney int xor_shift_foo(int shift, int mask) 50649ab51b0SPaul E. McKenney { 50749ab51b0SPaul E. McKenney int old, new, newold; 50849ab51b0SPaul E. McKenney 50949ab51b0SPaul E. McKenney newold = data_race(foo); /* Checked by cmpxchg(). */ 51049ab51b0SPaul E. McKenney do { 51149ab51b0SPaul E. McKenney old = newold; 51249ab51b0SPaul E. McKenney new = (old << shift) ^ mask; 51349ab51b0SPaul E. McKenney newold = cmpxchg(&foo, old, new); 51449ab51b0SPaul E. McKenney } while (newold != old); 51549ab51b0SPaul E. McKenney return old; 51649ab51b0SPaul E. McKenney } 51749ab51b0SPaul E. McKenney 51849ab51b0SPaul E. McKenney int read_foo(void) 51949ab51b0SPaul E. McKenney { 52049ab51b0SPaul E. McKenney return READ_ONCE(foo); 52149ab51b0SPaul E. McKenney } 52249ab51b0SPaul E. McKenney 52349ab51b0SPaul E. McKenneyIf it is possible for update_foo(), xor_shift_foo(), and read_foo() to be 52449ab51b0SPaul E. McKenneyinvoked concurrently, the stress test should force this concurrency to 52549ab51b0SPaul E. McKenneyactually happen. KCSAN can evaluate the stress test when the above code 52649ab51b0SPaul E. McKenneyis modified to read as follows: 52749ab51b0SPaul E. McKenney 52849ab51b0SPaul E. McKenney int foo; 52949ab51b0SPaul E. McKenney 53049ab51b0SPaul E. McKenney int update_foo(int newval) 53149ab51b0SPaul E. McKenney { 53249ab51b0SPaul E. McKenney ASSERT_EXCLUSIVE_ACCESS(foo); 53349ab51b0SPaul E. McKenney return xchg(&foo, newval); 53449ab51b0SPaul E. McKenney } 53549ab51b0SPaul E. McKenney 53649ab51b0SPaul E. McKenney int xor_shift_foo(int shift, int mask) 53749ab51b0SPaul E. McKenney { 53849ab51b0SPaul E. McKenney int old, new, newold; 53949ab51b0SPaul E. McKenney 54049ab51b0SPaul E. McKenney newold = data_race(foo); /* Checked by cmpxchg(). */ 54149ab51b0SPaul E. McKenney do { 54249ab51b0SPaul E. McKenney old = newold; 54349ab51b0SPaul E. McKenney new = (old << shift) ^ mask; 54449ab51b0SPaul E. McKenney ASSERT_EXCLUSIVE_ACCESS(foo); 54549ab51b0SPaul E. McKenney newold = cmpxchg(&foo, old, new); 54649ab51b0SPaul E. McKenney } while (newold != old); 54749ab51b0SPaul E. McKenney return old; 54849ab51b0SPaul E. McKenney } 54949ab51b0SPaul E. McKenney 55049ab51b0SPaul E. McKenney 55149ab51b0SPaul E. McKenney int read_foo(void) 55249ab51b0SPaul E. McKenney { 55349ab51b0SPaul E. McKenney ASSERT_EXCLUSIVE_ACCESS(foo); 55449ab51b0SPaul E. McKenney return READ_ONCE(foo); 55549ab51b0SPaul E. McKenney } 55649ab51b0SPaul E. McKenney 55749ab51b0SPaul E. McKenneyIf a given stress-test run does not result in KCSAN complaints from 55849ab51b0SPaul E. McKenneyeach possible pair of ASSERT_EXCLUSIVE_ACCESS() invocations, the 55949ab51b0SPaul E. McKenneystress test needs improvement. If the stress test was to be evaluated 56049ab51b0SPaul E. McKenneyon a regular basis, it would be wise to place the above instances of 56149ab51b0SPaul E. McKenneyASSERT_EXCLUSIVE_ACCESS() under #ifdef so that they did not result in 56249ab51b0SPaul E. McKenneyfalse positives when not evaluating the stress test. 56349ab51b0SPaul E. McKenney 56449ab51b0SPaul E. McKenney 56549ab51b0SPaul E. McKenneyREFERENCES 56649ab51b0SPaul E. McKenney========== 56749ab51b0SPaul E. McKenney 56849ab51b0SPaul E. McKenney[1] "Concurrency bugs should fear the big bad data-race detector (part 2)" 56949ab51b0SPaul E. McKenney https://lwn.net/Articles/816854/ 57049ab51b0SPaul E. McKenney 57149ab51b0SPaul E. McKenney[2] "Who's afraid of a big bad optimizing compiler?" 57249ab51b0SPaul E. McKenney https://lwn.net/Articles/793253/ 573