Documentation/dev-tools/kcsan.rst

   1 .. SPDX-License-Identifier: GPL-2.0
   2 .. Copyright (C) 2019, Google LLC.
   3
   4 The Kernel Concurrency Sanitizer (KCSAN)
   5 ========================================
   6
   7 The Kernel Concurrency Sanitizer (KCSAN) is a dynamic race detector, which
   8 relies on compile-time instrumentation, and uses a watchpoint-based sampling
   9 approach to detect races. KCSAN's primary purpose is to detect `data races`_.
  10
  11 Usage
  12 -----
  13
  14 KCSAN is supported by both GCC and Clang. With GCC we require version 11 or
  15 later, and with Clang also require version 11 or later.
  16
  17 To enable KCSAN configure the kernel with::
  18
  19     CONFIG_KCSAN = y
  20
  21 KCSAN provides several other configuration options to customize behaviour (see
  22 the respective help text in ``lib/Kconfig.kcsan`` for more info).
  23
  24 Error reports
  25 ~~~~~~~~~~~~~
  26
  27 A typical data race report looks like this::
  28
  29     ==================================================================
  30     BUG: KCSAN: data-race in generic_permission / kernfs_refresh_inode
  31
  32     write to 0xffff8fee4c40700c of 4 bytes by task 175 on cpu 4:
  33      kernfs_refresh_inode+0x70/0x170
  34      kernfs_iop_permission+0x4f/0x90
  35      inode_permission+0x190/0x200
  36      link_path_walk.part.0+0x503/0x8e0
  37      path_lookupat.isra.0+0x69/0x4d0
  38      filename_lookup+0x136/0x280
  39      user_path_at_empty+0x47/0x60
  40      vfs_statx+0x9b/0x130
  41      __do_sys_newlstat+0x50/0xb0
  42      __x64_sys_newlstat+0x37/0x50
  43      do_syscall_64+0x85/0x260
  44      entry_SYSCALL_64_after_hwframe+0x44/0xa9
  45
  46     read to 0xffff8fee4c40700c of 4 bytes by task 166 on cpu 6:
  47      generic_permission+0x5b/0x2a0
  48      kernfs_iop_permission+0x66/0x90
  49      inode_permission+0x190/0x200
  50      link_path_walk.part.0+0x503/0x8e0
  51      path_lookupat.isra.0+0x69/0x4d0
  52      filename_lookup+0x136/0x280
  53      user_path_at_empty+0x47/0x60
  54      do_faccessat+0x11a/0x390
  55      __x64_sys_access+0x3c/0x50
  56      do_syscall_64+0x85/0x260
  57      entry_SYSCALL_64_after_hwframe+0x44/0xa9
  58
  59     Reported by Kernel Concurrency Sanitizer on:
  60     CPU: 6 PID: 166 Comm: systemd-journal Not tainted 5.3.0-rc7+ #1
  61     Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.12.0-1 04/01/2014
  62     ==================================================================
  63
  64 The header of the report provides a short summary of the functions involved in
  65 the race. It is followed by the access types and stack traces of the 2 threads
  66 involved in the data race.
  67
  68 The other less common type of data race report looks like this::
  69
  70     ==================================================================
  71     BUG: KCSAN: data-race in e1000_clean_rx_irq+0x551/0xb10
  72
  73     race at unknown origin, with read to 0xffff933db8a2ae6c of 1 bytes by interrupt on cpu 0:
  74      e1000_clean_rx_irq+0x551/0xb10
  75      e1000_clean+0x533/0xda0
  76      net_rx_action+0x329/0x900
  77      __do_softirq+0xdb/0x2db
  78      irq_exit+0x9b/0xa0
  79      do_IRQ+0x9c/0xf0
  80      ret_from_intr+0x0/0x18
  81      default_idle+0x3f/0x220
  82      arch_cpu_idle+0x21/0x30
  83      do_idle+0x1df/0x230
  84      cpu_startup_entry+0x14/0x20
  85      rest_init+0xc5/0xcb
  86      arch_call_rest_init+0x13/0x2b
  87      start_kernel+0x6db/0x700
  88
  89     Reported by Kernel Concurrency Sanitizer on:
  90     CPU: 0 PID: 0 Comm: swapper/0 Not tainted 5.3.0-rc7+ #2
  91     Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.12.0-1 04/01/2014
  92     ==================================================================
  93
  94 This report is generated where it was not possible to determine the other
  95 racing thread, but a race was inferred due to the data value of the watched
  96 memory location having changed. These can occur either due to missing
  97 instrumentation or e.g. DMA accesses. These reports will only be generated if
  98 ``CONFIG_KCSAN_REPORT_RACE_UNKNOWN_ORIGIN=y`` (selected by default).
  99
 100 Selective analysis
 101 ~~~~~~~~~~~~~~~~~~
 102
 103 It may be desirable to disable data race detection for specific accesses,
 104 functions, compilation units, or entire subsystems.  For static blacklisting,
 105 the below options are available:
 106
 107 * KCSAN understands the ``data_race(expr)`` annotation, which tells KCSAN that
 108   any data races due to accesses in ``expr`` should be ignored and resulting
 109   behaviour when encountering a data race is deemed safe.
 110
 111 * Disabling data race detection for entire functions can be accomplished by
 112   using the function attribute ``__no_kcsan``::
 113
 114     __no_kcsan
 115     void foo(void) {
 116         ...
 117
 118   To dynamically limit for which functions to generate reports, see the
 119   `DebugFS interface`_ blacklist/whitelist feature.
 120
 121 * To disable data race detection for a particular compilation unit, add to the
 122   ``Makefile``::
 123
 124     KCSAN_SANITIZE_file.o := n
 125
 126 * To disable data race detection for all compilation units listed in a
 127   ``Makefile``, add to the respective ``Makefile``::
 128
 129     KCSAN_SANITIZE := n
 130
 131 Furthermore, it is possible to tell KCSAN to show or hide entire classes of
 132 data races, depending on preferences. These can be changed via the following
 133 Kconfig options:
 134
 135 * ``CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY``: If enabled and a conflicting write
 136   is observed via a watchpoint, but the data value of the memory location was
 137   observed to remain unchanged, do not report the data race.
 138
 139 * ``CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC``: Assume that plain aligned writes
 140   up to word size are atomic by default. Assumes that such writes are not
 141   subject to unsafe compiler optimizations resulting in data races. The option
 142   causes KCSAN to not report data races due to conflicts where the only plain
 143   accesses are aligned writes up to word size.
 144
 145 DebugFS interface
 146 ~~~~~~~~~~~~~~~~~
 147
 148 The file ``/sys/kernel/debug/kcsan`` provides the following interface:
 149
 150 * Reading ``/sys/kernel/debug/kcsan`` returns various runtime statistics.
 151
 152 * Writing ``on`` or ``off`` to ``/sys/kernel/debug/kcsan`` allows turning KCSAN
 153   on or off, respectively.
 154
 155 * Writing ``!some_func_name`` to ``/sys/kernel/debug/kcsan`` adds
 156   ``some_func_name`` to the report filter list, which (by default) blacklists
 157   reporting data races where either one of the top stackframes are a function
 158   in the list.
 159
 160 * Writing either ``blacklist`` or ``whitelist`` to ``/sys/kernel/debug/kcsan``
 161   changes the report filtering behaviour. For example, the blacklist feature
 162   can be used to silence frequently occurring data races; the whitelist feature
 163   can help with reproduction and testing of fixes.
 164
 165 Tuning performance
 166 ~~~~~~~~~~~~~~~~~~
 167
 168 Core parameters that affect KCSAN's overall performance and bug detection
 169 ability are exposed as kernel command-line arguments whose defaults can also be
 170 changed via the corresponding Kconfig options.
 171
 172 * ``kcsan.skip_watch`` (``CONFIG_KCSAN_SKIP_WATCH``): Number of per-CPU memory
 173   operations to skip, before another watchpoint is set up. Setting up
 174   watchpoints more frequently will result in the likelihood of races to be
 175   observed to increase. This parameter has the most significant impact on
 176   overall system performance and race detection ability.
 177
 178 * ``kcsan.udelay_task`` (``CONFIG_KCSAN_UDELAY_TASK``): For tasks, the
 179   microsecond delay to stall execution after a watchpoint has been set up.
 180   Larger values result in the window in which we may observe a race to
 181   increase.
 182
 183 * ``kcsan.udelay_interrupt`` (``CONFIG_KCSAN_UDELAY_INTERRUPT``): For
 184   interrupts, the microsecond delay to stall execution after a watchpoint has
 185   been set up. Interrupts have tighter latency requirements, and their delay
 186   should generally be smaller than the one chosen for tasks.
 187
 188 They may be tweaked at runtime via ``/sys/module/kcsan/parameters/``.
 189
 190 Data Races
 191 ----------
 192
 193 In an execution, two memory accesses form a *data race* if they *conflict*,
 194 they happen concurrently in different threads, and at least one of them is a
 195 *plain access*; they *conflict* if both access the same memory location, and at
 196 least one is a write. For a more thorough discussion and definition, see `"Plain
 197 Accesses and Data Races" in the LKMM`_.
 198
 199 .. _"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#n1922
 200
 201 Relationship with the Linux-Kernel Memory Consistency Model (LKMM)
 202 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 203
 204 The LKMM defines the propagation and ordering rules of various memory
 205 operations, which gives developers the ability to reason about concurrent code.
 206 Ultimately this allows to determine the possible executions of concurrent code,
 207 and if that code is free from data races.
 208
 209 KCSAN is aware of *marked atomic operations* (``READ_ONCE``, ``WRITE_ONCE``,
 210 ``atomic_*``, etc.), but is oblivious of any ordering guarantees and simply
 211 assumes that memory barriers are placed correctly. In other words, KCSAN
 212 assumes that as long as a plain access is not observed to race with another
 213 conflicting access, memory operations are correctly ordered.
 214
 215 This means that KCSAN will not report *potential* data races due to missing
 216 memory ordering. Developers should therefore carefully consider the required
 217 memory ordering requirements that remain unchecked. If, however, missing
 218 memory ordering (that is observable with a particular compiler and
 219 architecture) leads to an observable data race (e.g. entering a critical
 220 section erroneously), KCSAN would report the resulting data race.
 221
 222 Race Detection Beyond Data Races
 223 --------------------------------
 224
 225 For code with complex concurrency design, race-condition bugs may not always
 226 manifest as data races. Race conditions occur if concurrently executing
 227 operations result in unexpected system behaviour. On the other hand, data races
 228 are defined at the C-language level. The following macros can be used to check
 229 properties of concurrent code where bugs would not manifest as data races.
 230
 231 .. kernel-doc:: include/linux/kcsan-checks.h
 232     :functions: ASSERT_EXCLUSIVE_WRITER ASSERT_EXCLUSIVE_WRITER_SCOPED
 233                 ASSERT_EXCLUSIVE_ACCESS ASSERT_EXCLUSIVE_ACCESS_SCOPED
 234                 ASSERT_EXCLUSIVE_BITS
 235
 236 Implementation Details
 237 ----------------------
 238
 239 KCSAN relies on observing that two accesses happen concurrently. Crucially, we
 240 want to (a) increase the chances of observing races (especially for races that
 241 manifest rarely), and (b) be able to actually observe them. We can accomplish
 242 (a) by injecting various delays, and (b) by using address watchpoints (or
 243 breakpoints).
 244
 245 If we deliberately stall a memory access, while we have a watchpoint for its
 246 address set up, and then observe the watchpoint to fire, two accesses to the
 247 same address just raced. Using hardware watchpoints, this is the approach taken
 248 in `DataCollider
 249 <http://usenix.org/legacy/events/osdi10/tech/full_papers/Erickson.pdf>`_.
 250 Unlike DataCollider, KCSAN does not use hardware watchpoints, but instead
 251 relies on compiler instrumentation and "soft watchpoints".
 252
 253 In KCSAN, watchpoints are implemented using an efficient encoding that stores
 254 access type, size, and address in a long; the benefits of using "soft
 255 watchpoints" are portability and greater flexibility. KCSAN then relies on the
 256 compiler instrumenting plain accesses. For each instrumented plain access:
 257
 258 1. Check if a matching watchpoint exists; if yes, and at least one access is a
 259    write, then we encountered a racing access.
 260
 261 2. Periodically, if no matching watchpoint exists, set up a watchpoint and
 262    stall for a small randomized delay.
 263
 264 3. Also check the data value before the delay, and re-check the data value
 265    after delay; if the values mismatch, we infer a race of unknown origin.
 266
 267 To detect data races between plain and marked accesses, KCSAN also annotates
 268 marked accesses, but only to check if a watchpoint exists; i.e. KCSAN never
 269 sets up a watchpoint on marked accesses. By never setting up watchpoints for
 270 marked operations, if all accesses to a variable that is accessed concurrently
 271 are properly marked, KCSAN will never trigger a watchpoint and therefore never
 272 report the accesses.
 273
 274 Key Properties
 275 ~~~~~~~~~~~~~~
 276
 277 1. **Memory Overhead:**  The overall memory overhead is only a few MiB
 278    depending on configuration. The current implementation uses a small array of
 279    longs to encode watchpoint information, which is negligible.
 280
 281 2. **Performance Overhead:** KCSAN's runtime aims to be minimal, using an
 282    efficient watchpoint encoding that does not require acquiring any shared
 283    locks in the fast-path. For kernel boot on a system with 8 CPUs:
 284
 285    - 5.0x slow-down with the default KCSAN config;
 286    - 2.8x slow-down from runtime fast-path overhead only (set very large
 287      ``KCSAN_SKIP_WATCH`` and unset ``KCSAN_SKIP_WATCH_RANDOMIZE``).
 288
 289 3. **Annotation Overheads:** Minimal annotations are required outside the KCSAN
 290    runtime. As a result, maintenance overheads are minimal as the kernel
 291    evolves.
 292
 293 4. **Detects Racy Writes from Devices:** Due to checking data values upon
 294    setting up watchpoints, racy writes from devices can also be detected.
 295
 296 5. **Memory Ordering:** KCSAN is *not* explicitly aware of the LKMM's ordering
 297    rules; this may result in missed data races (false negatives).
 298
 299 6. **Analysis Accuracy:** For observed executions, due to using a sampling
 300    strategy, the analysis is *unsound* (false negatives possible), but aims to
 301    be complete (no false positives).
 302
 303 Alternatives Considered
 304 -----------------------
 305
 306 An alternative data race detection approach for the kernel can be found in the
 307 `Kernel Thread Sanitizer (KTSAN) <https://github.com/google/ktsan/wiki>`_.
 308 KTSAN is a happens-before data race detector, which explicitly establishes the
 309 happens-before order between memory operations, which can then be used to
 310 determine data races as defined in `Data Races`_.
 311
 312 To build a correct happens-before relation, KTSAN must be aware of all ordering
 313 rules of the LKMM and synchronization primitives. Unfortunately, any omission
 314 leads to large numbers of false positives, which is especially detrimental in
 315 the context of the kernel which includes numerous custom synchronization
 316 mechanisms. To track the happens-before relation, KTSAN's implementation
 317 requires metadata for each memory location (shadow memory), which for each page
 318 corresponds to 4 pages of shadow memory, and can translate into overhead of
 319 tens of GiB on a large system.