| 1 | |
| 2 | |
| 3 |
|
| 4 | 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 test_kernel_read / test_kernel_write
|
| 31 |
|
| 32 | write to 0xffffffffc009a628 of 8 bytes by task 487 on cpu 0:
|
| 33 | test_kernel_write+0x1d/0x30
|
| 34 | access_thread+0x89/0xd0
|
| 35 | kthread+0x23e/0x260
|
| 36 | ret_from_fork+0x22/0x30
|
| 37 |
|
| 38 | read to 0xffffffffc009a628 of 8 bytes by task 488 on cpu 6:
|
| 39 | test_kernel_read+0x10/0x20
|
| 40 | access_thread+0x89/0xd0
|
| 41 | kthread+0x23e/0x260
|
| 42 | ret_from_fork+0x22/0x30
|
| 43 |
|
| 44 | value changed: 0x00000000000009a6 -> 0x00000000000009b2
|
| 45 |
|
| 46 | Reported by Kernel Concurrency Sanitizer on:
|
| 47 | CPU: 6 PID: 488 Comm: access_thread Not tainted 5.12.0-rc2+ #1
|
| 48 | Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
|
| 49 | ==================================================================
|
| 50 |
|
| 51 | The header of the report provides a short summary of the functions involved in
|
| 52 | the race. It is followed by the access types and stack traces of the 2 threads
|
| 53 | involved in the data race. If KCSAN also observed a value change, the observed
|
| 54 | old value and new value are shown on the "value changed" line respectively.
|
| 55 |
|
| 56 | The other less common type of data race report looks like this::
|
| 57 |
|
| 58 | ==================================================================
|
| 59 | BUG: KCSAN: data-race in test_kernel_rmw_array+0x71/0xd0
|
| 60 |
|
| 61 | race at unknown origin, with read to 0xffffffffc009bdb0 of 8 bytes by task 515 on cpu 2:
|
| 62 | test_kernel_rmw_array+0x71/0xd0
|
| 63 | access_thread+0x89/0xd0
|
| 64 | kthread+0x23e/0x260
|
| 65 | ret_from_fork+0x22/0x30
|
| 66 |
|
| 67 | value changed: 0x0000000000002328 -> 0x0000000000002329
|
| 68 |
|
| 69 | Reported by Kernel Concurrency Sanitizer on:
|
| 70 | CPU: 2 PID: 515 Comm: access_thread Not tainted 5.12.0-rc2+ #1
|
| 71 | Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
|
| 72 | ==================================================================
|
| 73 |
|
| 74 | This report is generated where it was not possible to determine the other
|
| 75 | racing thread, but a race was inferred due to the data value of the watched
|
| 76 | memory location having changed. These reports always show a "value changed"
|
| 77 | line. A common reason for reports of this type are missing instrumentation in
|
| 78 | the racing thread, but could also occur due to e.g. DMA accesses. Such reports
|
| 79 | are shown only if ``CONFIG_KCSAN_REPORT_RACE_UNKNOWN_ORIGIN=y``, which is
|
| 80 | enabled by default.
|
| 81 |
|
| 82 | Selective analysis
|
| 83 | ~~~~~~~~~~~~~~~~~~
|
| 84 |
|
| 85 | It may be desirable to disable data race detection for specific accesses,
|
| 86 | functions, compilation units, or entire subsystems. For static blacklisting,
|
| 87 | the below options are available:
|
| 88 |
|
| 89 | * KCSAN understands the ``data_race(expr)`` annotation, which tells KCSAN that
|
| 90 | any data races due to accesses in ``expr`` should be ignored and resulting
|
| 91 | behaviour when encountering a data race is deemed safe. Please see
|
| 92 | `"Marking Shared-Memory Accesses" in the LKMM`_ for more information.
|
| 93 |
|
| 94 | * Similar to ``data_race(...)``, the type qualifier ``__data_racy`` can be used
|
| 95 | to document that all data races due to accesses to a variable are intended
|
| 96 | 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 by
|
| 105 | using the function attribute ``__no_kcsan``::
|
| 106 |
|
| 107 | __no_kcsan
|
| 108 | void foo(void) {
|
| 109 | ...
|
| 110 |
|
| 111 | To dynamically limit for which functions to generate reports, see the
|
| 112 | `DebugFS interface`_ blacklist/whitelist feature.
|
| 113 |
|
| 114 | * To disable data race detection for a particular compilation unit, add to the
|
| 115 | ``Makefile``::
|
| 116 |
|
| 117 | KCSAN_SANITIZE_file.o := n
|
| 118 |
|
| 119 | * To disable data race detection for all compilation units listed in a
|
| 120 | ``Makefile``, add to the respective ``Makefile``::
|
| 121 |
|
| 122 | KCSAN_SANITIZE := n
|
| 123 |
|
| 124 | |
| 125 |
|
| 126 | Furthermore, it is possible to tell KCSAN to show or hide entire classes of
|
| 127 | data races, depending on preferences. These can be changed via the following
|
| 128 | Kconfig options:
|
| 129 |
|
| 130 | * ``CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY``: If enabled and a conflicting write
|
| 131 | is observed via a watchpoint, but the data value of the memory location was
|
| 132 | observed to remain unchanged, do not report the data race.
|
| 133 |
|
| 134 | * ``CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC``: Assume that plain aligned writes
|
| 135 | up to word size are atomic by default. Assumes that such writes are not
|
| 136 | subject to unsafe compiler optimizations resulting in data races. The option
|
| 137 | causes KCSAN to not report data races due to conflicts where the only plain
|
| 138 | accesses are aligned writes up to word size.
|
| 139 |
|
| 140 | * ``CONFIG_KCSAN_PERMISSIVE``: Enable additional permissive rules to ignore
|
| 141 | certain classes of common data races. Unlike the above, the rules are more
|
| 142 | complex involving value-change patterns, access type, and address. This
|
| 143 | option depends on ``CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=y``. For details
|
| 144 | please see the ``kernel/kcsan/permissive.h``. Testers and maintainers that
|
| 145 | only focus on reports from specific subsystems and not the whole kernel are
|
| 146 | recommended to disable this option.
|
| 147 |
|
| 148 | To use the strictest possible rules, select ``CONFIG_KCSAN_STRICT=y``, which
|
| 149 | configures KCSAN to follow the Linux-kernel memory consistency model (LKMM) as
|
| 150 | closely as possible.
|
| 151 |
|
| 152 | DebugFS interface
|
| 153 | ~~~~~~~~~~~~~~~~~
|
| 154 |
|
| 155 | The 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 KCSAN
|
| 160 | on or off, respectively.
|
| 161 |
|
| 162 | * Writing ``!some_func_name`` to ``/sys/kernel/debug/kcsan`` adds
|
| 163 | ``some_func_name`` to the report filter list, which (by default) blacklists
|
| 164 | reporting data races where either one of the top stackframes are a function
|
| 165 | 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 feature
|
| 169 | can be used to silence frequently occurring data races; the whitelist feature
|
| 170 | can help with reproduction and testing of fixes.
|
| 171 |
|
| 172 | Tuning performance
|
| 173 | ~~~~~~~~~~~~~~~~~~
|
| 174 |
|
| 175 | Core parameters that affect KCSAN's overall performance and bug detection
|
| 176 | ability are exposed as kernel command-line arguments whose defaults can also be
|
| 177 | changed via the corresponding Kconfig options.
|
| 178 |
|
| 179 | * ``kcsan.skip_watch`` (``CONFIG_KCSAN_SKIP_WATCH``): Number of per-CPU memory
|
| 180 | operations to skip, before another watchpoint is set up. Setting up
|
| 181 | watchpoints more frequently will result in the likelihood of races to be
|
| 182 | observed to increase. This parameter has the most significant impact on
|
| 183 | overall system performance and race detection ability.
|
| 184 |
|
| 185 | * ``kcsan.udelay_task`` (``CONFIG_KCSAN_UDELAY_TASK``): For tasks, the
|
| 186 | 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 to
|
| 188 | increase.
|
| 189 |
|
| 190 | * ``kcsan.udelay_interrupt`` (``CONFIG_KCSAN_UDELAY_INTERRUPT``): For
|
| 191 | interrupts, the microsecond delay to stall execution after a watchpoint has
|
| 192 | been set up. Interrupts have tighter latency requirements, and their delay
|
| 193 | should generally be smaller than the one chosen for tasks.
|
| 194 |
|
| 195 | They may be tweaked at runtime via ``/sys/module/kcsan/parameters/``.
|
| 196 |
|
| 197 | Data Races
|
| 198 | ----------
|
| 199 |
|
| 200 | In an execution, two memory accesses form a *data race* if they *conflict*,
|
| 201 | they happen concurrently in different threads, and at least one of them is a
|
| 202 | *plain access*; they *conflict* if both access the same memory location, and at
|
| 203 | least one is a write. For a more thorough discussion and definition, see `"Plain
|
| 204 | Accesses and Data Races" in the LKMM`_.
|
| 205 |
|
| 206 | |
| 207 |
|
| 208 | Relationship with the Linux-Kernel Memory Consistency Model (LKMM)
|
| 209 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
| 210 |
|
| 211 | The LKMM defines the propagation and ordering rules of various memory
|
| 212 | operations, which gives developers the ability to reason about concurrent code.
|
| 213 | Ultimately this allows to determine the possible executions of concurrent code,
|
| 214 | and if that code is free from data races.
|
| 215 |
|
| 216 | KCSAN is aware of *marked atomic operations* (``READ_ONCE``, ``WRITE_ONCE``,
|
| 217 | ``atomic_*``, etc.), and a subset of ordering guarantees implied by memory
|
| 218 | barriers. With ``CONFIG_KCSAN_WEAK_MEMORY=y``, KCSAN models load or store
|
| 219 | buffering, and can detect missing ``smp_mb()``, ``smp_wmb()``, ``smp_rmb()``,
|
| 220 | ``smp_store_release()``, and all ``atomic_*`` operations with equivalent
|
| 221 | implied barriers.
|
| 222 |
|
| 223 | Note, KCSAN will not report all data races due to missing memory ordering,
|
| 224 | specifically where a memory barrier would be required to prohibit subsequent
|
| 225 | memory operation from reordering before the barrier. Developers should
|
| 226 | therefore carefully consider the required memory ordering requirements that
|
| 227 | remain unchecked.
|
| 228 |
|
| 229 | Race Detection Beyond Data Races
|
| 230 | --------------------------------
|
| 231 |
|
| 232 | For code with complex concurrency design, race-condition bugs may not always
|
| 233 | manifest as data races. Race conditions occur if concurrently executing
|
| 234 | operations result in unexpected system behaviour. On the other hand, data races
|
| 235 | are defined at the C-language level. The following macros can be used to check
|
| 236 | properties of concurrent code where bugs would not manifest as data races.
|
| 237 |
|
| 238 | .. kernel-doc:: include/linux/kcsan-checks.h
|
| 239 | :functions: ASSERT_EXCLUSIVE_WRITER ASSERT_EXCLUSIVE_WRITER_SCOPED
|
| 240 | ASSERT_EXCLUSIVE_ACCESS ASSERT_EXCLUSIVE_ACCESS_SCOPED
|
| 241 | ASSERT_EXCLUSIVE_BITS
|
| 242 |
|
| 243 | Implementation Details
|
| 244 | ----------------------
|
| 245 |
|
| 246 | KCSAN relies on observing that two accesses happen concurrently. Crucially, we
|
| 247 | want to (a) increase the chances of observing races (especially for races that
|
| 248 | manifest rarely), and (b) be able to actually observe them. We can accomplish
|
| 249 | (a) by injecting various delays, and (b) by using address watchpoints (or
|
| 250 | breakpoints).
|
| 251 |
|
| 252 | If we deliberately stall a memory access, while we have a watchpoint for its
|
| 253 | address set up, and then observe the watchpoint to fire, two accesses to the
|
| 254 | same address just raced. Using hardware watchpoints, this is the approach taken
|
| 255 | in `DataCollider
|
| 256 | <http://usenix.org/legacy/events/osdi10/tech/full_papers/Erickson.pdf>`_.
|
| 257 | Unlike DataCollider, KCSAN does not use hardware watchpoints, but instead
|
| 258 | relies on compiler instrumentation and "soft watchpoints".
|
| 259 |
|
| 260 | In KCSAN, watchpoints are implemented using an efficient encoding that stores
|
| 261 | access type, size, and address in a long; the benefits of using "soft
|
| 262 | watchpoints" are portability and greater flexibility. KCSAN then relies on the
|
| 263 | compiler instrumenting plain accesses. For each instrumented plain access:
|
| 264 |
|
| 265 | 1. Check if a matching watchpoint exists; if yes, and at least one access is a
|
| 266 | write, then we encountered a racing access.
|
| 267 |
|
| 268 | 2. Periodically, if no matching watchpoint exists, set up a watchpoint and
|
| 269 | stall for a small randomized delay.
|
| 270 |
|
| 271 | 3. Also check the data value before the delay, and re-check the data value
|
| 272 | after delay; if the values mismatch, we infer a race of unknown origin.
|
| 273 |
|
| 274 | To detect data races between plain and marked accesses, KCSAN also annotates
|
| 275 | marked accesses, but only to check if a watchpoint exists; i.e. KCSAN never
|
| 276 | sets up a watchpoint on marked accesses. By never setting up watchpoints for
|
| 277 | marked operations, if all accesses to a variable that is accessed concurrently
|
| 278 | are properly marked, KCSAN will never trigger a watchpoint and therefore never
|
| 279 | report the accesses.
|
| 280 |
|
| 281 | Modeling Weak Memory
|
| 282 | ~~~~~~~~~~~~~~~~~~~~
|
| 283 |
|
| 284 | KCSAN's approach to detecting data races due to missing memory barriers is
|
| 285 | based on modeling access reordering (with ``CONFIG_KCSAN_WEAK_MEMORY=y``).
|
| 286 | Each plain memory access for which a watchpoint is set up, is also selected for
|
| 287 | simulated reordering within the scope of its function (at most 1 in-flight
|
| 288 | access).
|
| 289 |
|
| 290 | Once an access has been selected for reordering, it is checked along every
|
| 291 | other access until the end of the function scope. If an appropriate memory
|
| 292 | barrier is encountered, the access will no longer be considered for simulated
|
| 293 | reordering.
|
| 294 |
|
| 295 | When the result of a memory operation should be ordered by a barrier, KCSAN can
|
| 296 | then detect data races where the conflict only occurs as a result of a missing
|
| 297 | barrier. 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 |
|
| 311 | When weak memory modeling is enabled, KCSAN can consider ``x`` in ``T1`` for
|
| 312 | simulated reordering. After the write of ``flag``, ``x`` is again checked for
|
| 313 | concurrent accesses: because ``T2`` is able to proceed after the write of
|
| 314 | ``flag``, a data race is detected. With the correct barriers in place, ``x``
|
| 315 | would not be considered for reordering after the proper release of ``flag``,
|
| 316 | and no data race would be detected.
|
| 317 |
|
| 318 | Deliberate trade-offs in complexity but also practical limitations mean only a
|
| 319 | subset of data races due to missing memory barriers can be detected. With
|
| 320 | currently available compiler support, the implementation is limited to modeling
|
| 321 | the effects of "buffering" (delaying accesses), since the runtime cannot
|
| 322 | "prefetch" accesses. Also recall that watchpoints are only set up for plain
|
| 323 | accesses, and the only access type for which KCSAN simulates reordering. This
|
| 324 | means reordering of marked accesses is not modeled.
|
| 325 |
|
| 326 | A consequence of the above is that acquire operations do not require barrier
|
| 327 | instrumentation (no prefetching). Furthermore, marked accesses introducing
|
| 328 | address or control dependencies do not require special handling (the marked
|
| 329 | access cannot be reordered, later dependent accesses cannot be prefetched).
|
| 330 |
|
| 331 | Key Properties
|
| 332 | ~~~~~~~~~~~~~~
|
| 333 |
|
| 334 | 1. **Memory Overhead:** The overall memory overhead is only a few MiB
|
| 335 | depending on configuration. The current implementation uses a small array of
|
| 336 | longs to encode watchpoint information, which is negligible.
|
| 337 |
|
| 338 | 2. **Performance Overhead:** KCSAN's runtime aims to be minimal, using an
|
| 339 | efficient watchpoint encoding that does not require acquiring any shared
|
| 340 | 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 large
|
| 344 | ``KCSAN_SKIP_WATCH`` and unset ``KCSAN_SKIP_WATCH_RANDOMIZE``).
|
| 345 |
|
| 346 | 3. **Annotation Overheads:** Minimal annotations are required outside the KCSAN
|
| 347 | runtime. As a result, maintenance overheads are minimal as the kernel
|
| 348 | evolves.
|
| 349 |
|
| 350 | 4. **Detects Racy Writes from Devices:** Due to checking data values upon
|
| 351 | setting up watchpoints, racy writes from devices can also be detected.
|
| 352 |
|
| 353 | 5. **Memory Ordering:** KCSAN is aware of only a subset of LKMM ordering rules;
|
| 354 | this may result in missed data races (false negatives).
|
| 355 |
|
| 356 | 6. **Analysis Accuracy:** For observed executions, due to using a sampling
|
| 357 | strategy, the analysis is *unsound* (false negatives possible), but aims to
|
| 358 | be complete (no false positives).
|
| 359 |
|
| 360 | Alternatives Considered
|
| 361 | -----------------------
|
| 362 |
|
| 363 | An alternative data race detection approach for the kernel can be found in the
|
| 364 | `Kernel Thread Sanitizer (KTSAN)
|
| 365 | <https://github.com/google/kernel-sanitizers/blob/master/KTSAN.md>`_.
|
| 366 | KTSAN is a happens-before data race detector, which explicitly establishes the
|
| 367 | happens-before order between memory operations, which can then be used to
|
| 368 | determine data races as defined in `Data Races`_.
|
| 369 |
|
| 370 | To build a correct happens-before relation, KTSAN must be aware of all ordering
|
| 371 | rules of the LKMM and synchronization primitives. Unfortunately, any omission
|
| 372 | leads to large numbers of false positives, which is especially detrimental in
|
| 373 | the context of the kernel which includes numerous custom synchronization
|
| 374 | mechanisms. To track the happens-before relation, KTSAN's implementation
|
| 375 | requires metadata for each memory location (shadow memory), which for each page
|
| 376 | corresponds to 4 pages of shadow memory, and can translate into overhead of
|
| 377 | tens of GiB on a large system.
|