378 lines · plain
1.. SPDX-License-Identifier: GPL-2.02.. Copyright (C) 2019, Google LLC.3 4Kernel Concurrency Sanitizer (KCSAN)5====================================6 7The Kernel Concurrency Sanitizer (KCSAN) is a dynamic race detector, which8relies on compile-time instrumentation, and uses a watchpoint-based sampling9approach to detect races. KCSAN's primary purpose is to detect `data races`_.10 11Usage12-----13 14KCSAN is supported by both GCC and Clang. With GCC we require version 11 or15later, and with Clang also require version 11 or later.16 17To enable KCSAN configure the kernel with::18 19 CONFIG_KCSAN = y20 21KCSAN provides several other configuration options to customize behaviour (see22the respective help text in ``lib/Kconfig.kcsan`` for more info).23 24Error reports25~~~~~~~~~~~~~26 27A typical data race report looks like this::28 29 ==================================================================30 BUG: KCSAN: data-race in test_kernel_read / test_kernel_write31 32 write to 0xffffffffc009a628 of 8 bytes by task 487 on cpu 0:33 test_kernel_write+0x1d/0x3034 access_thread+0x89/0xd035 kthread+0x23e/0x26036 ret_from_fork+0x22/0x3037 38 read to 0xffffffffc009a628 of 8 bytes by task 488 on cpu 6:39 test_kernel_read+0x10/0x2040 access_thread+0x89/0xd041 kthread+0x23e/0x26042 ret_from_fork+0x22/0x3043 44 value changed: 0x00000000000009a6 -> 0x00000000000009b245 46 Reported by Kernel Concurrency Sanitizer on:47 CPU: 6 PID: 488 Comm: access_thread Not tainted 5.12.0-rc2+ #148 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/201449 ==================================================================50 51The header of the report provides a short summary of the functions involved in52the race. It is followed by the access types and stack traces of the 2 threads53involved in the data race. If KCSAN also observed a value change, the observed54old value and new value are shown on the "value changed" line respectively.55 56The other less common type of data race report looks like this::57 58 ==================================================================59 BUG: KCSAN: data-race in test_kernel_rmw_array+0x71/0xd060 61 race at unknown origin, with read to 0xffffffffc009bdb0 of 8 bytes by task 515 on cpu 2:62 test_kernel_rmw_array+0x71/0xd063 access_thread+0x89/0xd064 kthread+0x23e/0x26065 ret_from_fork+0x22/0x3066 67 value changed: 0x0000000000002328 -> 0x000000000000232968 69 Reported by Kernel Concurrency Sanitizer on:70 CPU: 2 PID: 515 Comm: access_thread Not tainted 5.12.0-rc2+ #171 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/201472 ==================================================================73 74This report is generated where it was not possible to determine the other75racing thread, but a race was inferred due to the data value of the watched76memory location having changed. These reports always show a "value changed"77line. A common reason for reports of this type are missing instrumentation in78the racing thread, but could also occur due to e.g. DMA accesses. Such reports79are shown only if ``CONFIG_KCSAN_REPORT_RACE_UNKNOWN_ORIGIN=y``, which is80enabled by default.81 82Selective analysis83~~~~~~~~~~~~~~~~~~84 85It may be desirable to disable data race detection for specific accesses,86functions, compilation units, or entire subsystems. For static blacklisting,87the below options are available:88 89* KCSAN understands the ``data_race(expr)`` annotation, which tells KCSAN that90 any data races due to accesses in ``expr`` should be ignored and resulting91 behaviour when encountering a data race is deemed safe. Please see92 `"Marking Shared-Memory Accesses" in the LKMM`_ for more information.93 94* Similar to ``data_race(...)``, the type qualifier ``__data_racy`` can be used95 to document that all data races due to accesses to a variable are intended96 and should be ignored by KCSAN::97 98 struct foo {99 ...100 int __data_racy stats_counter;101 ...102 };103 104* Disabling data race detection for entire functions can be accomplished by105 using the function attribute ``__no_kcsan``::106 107 __no_kcsan108 void foo(void) {109 ...110 111 To dynamically limit for which functions to generate reports, see the112 `DebugFS interface`_ blacklist/whitelist feature.113 114* To disable data race detection for a particular compilation unit, add to the115 ``Makefile``::116 117 KCSAN_SANITIZE_file.o := n118 119* To disable data race detection for all compilation units listed in a120 ``Makefile``, add to the respective ``Makefile``::121 122 KCSAN_SANITIZE := n123 124.. _"Marking Shared-Memory Accesses" in the LKMM: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/memory-model/Documentation/access-marking.txt125 126Furthermore, it is possible to tell KCSAN to show or hide entire classes of127data races, depending on preferences. These can be changed via the following128Kconfig options:129 130* ``CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY``: If enabled and a conflicting write131 is observed via a watchpoint, but the data value of the memory location was132 observed to remain unchanged, do not report the data race.133 134* ``CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC``: Assume that plain aligned writes135 up to word size are atomic by default. Assumes that such writes are not136 subject to unsafe compiler optimizations resulting in data races. The option137 causes KCSAN to not report data races due to conflicts where the only plain138 accesses are aligned writes up to word size.139 140* ``CONFIG_KCSAN_PERMISSIVE``: Enable additional permissive rules to ignore141 certain classes of common data races. Unlike the above, the rules are more142 complex involving value-change patterns, access type, and address. This143 option depends on ``CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=y``. For details144 please see the ``kernel/kcsan/permissive.h``. Testers and maintainers that145 only focus on reports from specific subsystems and not the whole kernel are146 recommended to disable this option.147 148To use the strictest possible rules, select ``CONFIG_KCSAN_STRICT=y``, which149configures KCSAN to follow the Linux-kernel memory consistency model (LKMM) as150closely as possible.151 152DebugFS interface153~~~~~~~~~~~~~~~~~154 155The file ``/sys/kernel/debug/kcsan`` provides the following interface:156 157* Reading ``/sys/kernel/debug/kcsan`` returns various runtime statistics.158 159* Writing ``on`` or ``off`` to ``/sys/kernel/debug/kcsan`` allows turning KCSAN160 on or off, respectively.161 162* Writing ``!some_func_name`` to ``/sys/kernel/debug/kcsan`` adds163 ``some_func_name`` to the report filter list, which (by default) blacklists164 reporting data races where either one of the top stackframes are a function165 in the list.166 167* Writing either ``blacklist`` or ``whitelist`` to ``/sys/kernel/debug/kcsan``168 changes the report filtering behaviour. For example, the blacklist feature169 can be used to silence frequently occurring data races; the whitelist feature170 can help with reproduction and testing of fixes.171 172Tuning performance173~~~~~~~~~~~~~~~~~~174 175Core parameters that affect KCSAN's overall performance and bug detection176ability are exposed as kernel command-line arguments whose defaults can also be177changed via the corresponding Kconfig options.178 179* ``kcsan.skip_watch`` (``CONFIG_KCSAN_SKIP_WATCH``): Number of per-CPU memory180 operations to skip, before another watchpoint is set up. Setting up181 watchpoints more frequently will result in the likelihood of races to be182 observed to increase. This parameter has the most significant impact on183 overall system performance and race detection ability.184 185* ``kcsan.udelay_task`` (``CONFIG_KCSAN_UDELAY_TASK``): For tasks, the186 microsecond delay to stall execution after a watchpoint has been set up.187 Larger values result in the window in which we may observe a race to188 increase.189 190* ``kcsan.udelay_interrupt`` (``CONFIG_KCSAN_UDELAY_INTERRUPT``): For191 interrupts, the microsecond delay to stall execution after a watchpoint has192 been set up. Interrupts have tighter latency requirements, and their delay193 should generally be smaller than the one chosen for tasks.194 195They may be tweaked at runtime via ``/sys/module/kcsan/parameters/``.196 197Data Races198----------199 200In an execution, two memory accesses form a *data race* if they *conflict*,201they happen concurrently in different threads, and at least one of them is a202*plain access*; they *conflict* if both access the same memory location, and at203least one is a write. For a more thorough discussion and definition, see `"Plain204Accesses and Data Races" in the LKMM`_.205 206.. _"Plain Accesses and Data Races" in the LKMM: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/memory-model/Documentation/explanation.txt#n1922207 208Relationship with the Linux-Kernel Memory Consistency Model (LKMM)209~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~210 211The LKMM defines the propagation and ordering rules of various memory212operations, which gives developers the ability to reason about concurrent code.213Ultimately this allows to determine the possible executions of concurrent code,214and if that code is free from data races.215 216KCSAN is aware of *marked atomic operations* (``READ_ONCE``, ``WRITE_ONCE``,217``atomic_*``, etc.), and a subset of ordering guarantees implied by memory218barriers. With ``CONFIG_KCSAN_WEAK_MEMORY=y``, KCSAN models load or store219buffering, and can detect missing ``smp_mb()``, ``smp_wmb()``, ``smp_rmb()``,220``smp_store_release()``, and all ``atomic_*`` operations with equivalent221implied barriers.222 223Note, KCSAN will not report all data races due to missing memory ordering,224specifically where a memory barrier would be required to prohibit subsequent225memory operation from reordering before the barrier. Developers should226therefore carefully consider the required memory ordering requirements that227remain unchecked.228 229Race Detection Beyond Data Races230--------------------------------231 232For code with complex concurrency design, race-condition bugs may not always233manifest as data races. Race conditions occur if concurrently executing234operations result in unexpected system behaviour. On the other hand, data races235are defined at the C-language level. The following macros can be used to check236properties of concurrent code where bugs would not manifest as data races.237 238.. kernel-doc:: include/linux/kcsan-checks.h239 :functions: ASSERT_EXCLUSIVE_WRITER ASSERT_EXCLUSIVE_WRITER_SCOPED240 ASSERT_EXCLUSIVE_ACCESS ASSERT_EXCLUSIVE_ACCESS_SCOPED241 ASSERT_EXCLUSIVE_BITS242 243Implementation Details244----------------------245 246KCSAN relies on observing that two accesses happen concurrently. Crucially, we247want to (a) increase the chances of observing races (especially for races that248manifest rarely), and (b) be able to actually observe them. We can accomplish249(a) by injecting various delays, and (b) by using address watchpoints (or250breakpoints).251 252If we deliberately stall a memory access, while we have a watchpoint for its253address set up, and then observe the watchpoint to fire, two accesses to the254same address just raced. Using hardware watchpoints, this is the approach taken255in `DataCollider256<http://usenix.org/legacy/events/osdi10/tech/full_papers/Erickson.pdf>`_.257Unlike DataCollider, KCSAN does not use hardware watchpoints, but instead258relies on compiler instrumentation and "soft watchpoints".259 260In KCSAN, watchpoints are implemented using an efficient encoding that stores261access type, size, and address in a long; the benefits of using "soft262watchpoints" are portability and greater flexibility. KCSAN then relies on the263compiler instrumenting plain accesses. For each instrumented plain access:264 2651. Check if a matching watchpoint exists; if yes, and at least one access is a266 write, then we encountered a racing access.267 2682. Periodically, if no matching watchpoint exists, set up a watchpoint and269 stall for a small randomized delay.270 2713. Also check the data value before the delay, and re-check the data value272 after delay; if the values mismatch, we infer a race of unknown origin.273 274To detect data races between plain and marked accesses, KCSAN also annotates275marked accesses, but only to check if a watchpoint exists; i.e. KCSAN never276sets up a watchpoint on marked accesses. By never setting up watchpoints for277marked operations, if all accesses to a variable that is accessed concurrently278are properly marked, KCSAN will never trigger a watchpoint and therefore never279report the accesses.280 281Modeling Weak Memory282~~~~~~~~~~~~~~~~~~~~283 284KCSAN's approach to detecting data races due to missing memory barriers is285based on modeling access reordering (with ``CONFIG_KCSAN_WEAK_MEMORY=y``).286Each plain memory access for which a watchpoint is set up, is also selected for287simulated reordering within the scope of its function (at most 1 in-flight288access).289 290Once an access has been selected for reordering, it is checked along every291other access until the end of the function scope. If an appropriate memory292barrier is encountered, the access will no longer be considered for simulated293reordering.294 295When the result of a memory operation should be ordered by a barrier, KCSAN can296then detect data races where the conflict only occurs as a result of a missing297barrier. Consider the example::298 299 int x, flag;300 void T1(void)301 {302 x = 1; // data race!303 WRITE_ONCE(flag, 1); // correct: smp_store_release(&flag, 1)304 }305 void T2(void)306 {307 while (!READ_ONCE(flag)); // correct: smp_load_acquire(&flag)308 ... = x; // data race!309 }310 311When weak memory modeling is enabled, KCSAN can consider ``x`` in ``T1`` for312simulated reordering. After the write of ``flag``, ``x`` is again checked for313concurrent accesses: because ``T2`` is able to proceed after the write of314``flag``, a data race is detected. With the correct barriers in place, ``x``315would not be considered for reordering after the proper release of ``flag``,316and no data race would be detected.317 318Deliberate trade-offs in complexity but also practical limitations mean only a319subset of data races due to missing memory barriers can be detected. With320currently available compiler support, the implementation is limited to modeling321the effects of "buffering" (delaying accesses), since the runtime cannot322"prefetch" accesses. Also recall that watchpoints are only set up for plain323accesses, and the only access type for which KCSAN simulates reordering. This324means reordering of marked accesses is not modeled.325 326A consequence of the above is that acquire operations do not require barrier327instrumentation (no prefetching). Furthermore, marked accesses introducing328address or control dependencies do not require special handling (the marked329access cannot be reordered, later dependent accesses cannot be prefetched).330 331Key Properties332~~~~~~~~~~~~~~333 3341. **Memory Overhead:** The overall memory overhead is only a few MiB335 depending on configuration. The current implementation uses a small array of336 longs to encode watchpoint information, which is negligible.337 3382. **Performance Overhead:** KCSAN's runtime aims to be minimal, using an339 efficient watchpoint encoding that does not require acquiring any shared340 locks in the fast-path. For kernel boot on a system with 8 CPUs:341 342 - 5.0x slow-down with the default KCSAN config;343 - 2.8x slow-down from runtime fast-path overhead only (set very large344 ``KCSAN_SKIP_WATCH`` and unset ``KCSAN_SKIP_WATCH_RANDOMIZE``).345 3463. **Annotation Overheads:** Minimal annotations are required outside the KCSAN347 runtime. As a result, maintenance overheads are minimal as the kernel348 evolves.349 3504. **Detects Racy Writes from Devices:** Due to checking data values upon351 setting up watchpoints, racy writes from devices can also be detected.352 3535. **Memory Ordering:** KCSAN is aware of only a subset of LKMM ordering rules;354 this may result in missed data races (false negatives).355 3566. **Analysis Accuracy:** For observed executions, due to using a sampling357 strategy, the analysis is *unsound* (false negatives possible), but aims to358 be complete (no false positives).359 360Alternatives Considered361-----------------------362 363An alternative data race detection approach for the kernel can be found in the364`Kernel Thread Sanitizer (KTSAN)365<https://github.com/google/kernel-sanitizers/blob/master/KTSAN.md>`_.366KTSAN is a happens-before data race detector, which explicitly establishes the367happens-before order between memory operations, which can then be used to368determine data races as defined in `Data Races`_.369 370To build a correct happens-before relation, KTSAN must be aware of all ordering371rules of the LKMM and synchronization primitives. Unfortunately, any omission372leads to large numbers of false positives, which is especially detrimental in373the context of the kernel which includes numerous custom synchronization374mechanisms. To track the happens-before relation, KTSAN's implementation375requires metadata for each memory location (shadow memory), which for each page376corresponds to 4 pages of shadow memory, and can translate into overhead of377tens of GiB on a large system.378