요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
.. SPDX-License-Identifier: GPL-2.0
.. Copyright (C) 2019, Google LLC.
Kernel Concurrency Sanitizer (KCSAN)
====================================
The Kernel Concurrency Sanitizer (KCSAN) is a dynamic race detector, which
relies on compile-time instrumentation, and uses a watchpoint-based sampling
approach to detect races. KCSAN's primary purpose is to detect `data races`_.
Usage
-----
KCSAN is supported by both GCC and Clang. With GCC we require version 11 or
later, and with Clang also require version 11 or later.
To enable KCSAN configure the kernel with::
CONFIG_KCSAN = y
KCSAN provides several other configuration options to customize behaviour (see
the respective help text in ``lib/Kconfig.kcsan`` for more info).
Error reports
~~~~~~~~~~~~~
A typical data race report looks like this::
==================================================================
BUG: KCSAN: data-race in test_kernel_read / test_kernel_write
write to 0xffffffffc009a628 of 8 bytes by task 487 on cpu 0:
test_kernel_write+0x1d/0x30
access_thread+0x89/0xd0
kthread+0x23e/0x260
ret_from_fork+0x22/0x30
read to 0xffffffffc009a628 of 8 bytes by task 488 on cpu 6:
test_kernel_read+0x10/0x20
access_thread+0x89/0xd0
kthread+0x23e/0x260
ret_from_fork+0x22/0x30
value changed: 0x00000000000009a6 -> 0x00000000000009b2
Reported by Kernel Concurrency Sanitizer on:
CPU: 6 PID: 488 Comm: access_thread Not tainted 5.12.0-rc2+ #1
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
==================================================================
The header of the report provides a short summary of the functions involved in
the race. It is followed by the access types and stack traces of the 2 threads
involved in the data race. If KCSAN also observed a value change, the observed
old value and new value are shown on the "value changed" line respectively.
The other less common type of data race report looks like this::
==================================================================
BUG: KCSAN: data-race in test_kernel_rmw_array+0x71/0xd0
race at unknown origin, with read to 0xffffffffc009bdb0 of 8 bytes by task 515 on cpu 2:
test_kernel_rmw_array+0x71/0xd0
access_thread+0x89/0xd0
kthread+0x23e/0x260
ret_from_fork+0x22/0x30
value changed: 0x0000000000002328 -> 0x0000000000002329
Reported by Kernel Concurrency Sanitizer on:
CPU: 2 PID: 515 Comm: access_thread Not tainted 5.12.0-rc2+ #1
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
==================================================================
This report is generated where it was not possible to determine the other
racing thread, but a race was inferred due to the data value of the watched
memory location having changed. These reports always show a "value changed"
line. A common reason for reports of this type are missing instrumentation in
the racing thread, but could also occur due to e.g. DMA accesses. Such reports
are shown only if ``CONFIG_KCSAN_REPORT_RACE_UNKNOWN_ORIGIN=y``, which is
enabled by default.
Selective analysis
~~~~~~~~~~~~~~~~~~
It may be desirable to disable data race detection for specific accesses,
functions, compilation units, or entire subsystems. For static blacklisting,
the below options are available:
* KCSAN understands the ``data_race(expr)`` annotation, which tells KCSAN that
any data races due to accesses in ``expr`` should be ignored and resulting
behaviour when encountering a data race is deemed safe. Please see
`"Marking Shared-Memory Accesses" in the LKMM`_ for more information.
* Similar to ``data_race(...)``, the type qualifier ``__data_racy`` can be used
to document that all data races due to accesses to a variable are intended
and should be ignored by KCSAN::
struct foo {
...
int __data_racy stats_counter;
...
};
* Disabling data race detection for entire functions can be accomplished by
using the function attribute ``__no_kcsan``::
__no_kcsan
void foo(void) {
...
To dynamically limit for which functions to generate reports, see the
`DebugFS interface`_ blacklist/whitelist feature.
* To disable data race detection for a particular compilation unit, add to the
``Makefile``::
KCSAN_SANITIZE_file.o := n
* To disable data race detection for all compilation units listed in a
``Makefile``, add to the respective ``Makefile``::
KCSAN_SANITIZE := n
.. _"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.txt
Furthermore, it is possible to tell KCSAN to show or hide entire classes of
data races, depending on preferences. These can be changed via the following
Kconfig options:
* ``CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY``: If enabled and a conflicting write
is observed via a watchpoint, but the data value of the memory location was
observed to remain unchanged, do not report the data race.
* ``CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC``: Assume that plain aligned writes
up to word size are atomic by default. Assumes that such writes are not
subject to unsafe compiler optimizations resulting in data races. The option
causes KCSAN to not report data races due to conflicts where the only plain
accesses are aligned writes up to word size.
* ``CONFIG_KCSAN_PERMISSIVE``: Enable additional permissive rules to ignore
certain classes of common data races. Unlike the above, the rules are more
complex involving value-change patterns, access type, and address. This
option depends on ``CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=y``. For details
please see the ``kernel/kcsan/permissive.h``. Testers and maintainers that
only focus on reports from specific subsystems and not the whole kernel are
recommended to disable this option.
To use the strictest possible rules, select ``CONFIG_KCSAN_STRICT=y``, which
configures KCSAN to follow the Linux-kernel memory consistency model (LKMM) as
closely as possible.
DebugFS interface
~~~~~~~~~~~~~~~~~
The file ``/sys/kernel/debug/kcsan`` provides the following interface:
* Reading ``/sys/kernel/debug/kcsan`` returns various runtime statistics.
* Writing ``on`` or ``off`` to ``/sys/kernel/debug/kcsan`` allows turning KCSAN
on or off, respectively.
* Writing ``!some_func_name`` to ``/sys/kernel/debug/kcsan`` adds
``some_func_name`` to the report filter list, which (by default) blacklists
reporting data races where either one of the top stackframes are a function
in the list.
* Writing either ``blacklist`` or ``whitelist`` to ``/sys/kernel/debug/kcsan``
changes the report filtering behaviour. For example, the blacklist feature
can be used to silence frequently occurring data races; the whitelist feature
can help with reproduction and testing of fixes.
Tuning performance
~~~~~~~~~~~~~~~~~~
Core parameters that affect KCSAN's overall performance and bug detection
ability are exposed as kernel command-line arguments whose defaults can also be
changed via the corresponding Kconfig options.
* ``kcsan.skip_watch`` (``CONFIG_KCSAN_SKIP_WATCH``): Number of per-CPU memory
operations to skip, before another watchpoint is set up. Setting up
watchpoints more frequently will result in the likelihood of races to be
observed to increase. This parameter has the most significant impact on
overall system performance and race detection ability.
* ``kcsan.udelay_task`` (``CONFIG_KCSAN_UDELAY_TASK``): For tasks, the
microsecond delay to stall execution after a watchpoint has been set up.
Larger values result in the window in which we may observe a race to
increase.
* ``kcsan.udelay_interrupt`` (``CONFIG_KCSAN_UDELAY_INTERRUPT``): For
interrupts, the microsecond delay to stall execution after a watchpoint has
been set up. Interrupts have tighter latency requirements, and their delay
should generally be smaller than the one chosen for tasks.
They may be tweaked at runtime via ``/sys/module/kcsan/parameters/``.
Data Races
----------
In an execution, two memory accesses form a *data race* if they *conflict*,
they happen concurrently in different threads, and at least one of them is a
*plain access*; they *conflict* if both access the same memory location, and at
least one is a write. For a more thorough discussion and definition, see `"Plain
Accesses and Data Races" in the LKMM`_.
.. _"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?id=8f6629c004b193d23612641c3607e785819e97ab#n2164
Relationship with the Linux-Kernel Memory Consistency Model (LKMM)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The LKMM defines the propagation and ordering rules of various memory
operations, which gives developers the ability to reason about concurrent code.
Ultimately this allows to determine the possible executions of concurrent code,
and if that code is free from data races.
KCSAN is aware of *marked atomic operations* (``READ_ONCE``, ``WRITE_ONCE``,
``atomic_*``, etc.), and a subset of ordering guarantees implied by memory
barriers. With ``CONFIG_KCSAN_WEAK_MEMORY=y``, KCSAN models load or store
buffering, and can detect missing ``smp_mb()``, ``smp_wmb()``, ``smp_rmb()``,
``smp_store_release()``, and all ``atomic_*`` operations with equivalent
implied barriers.
Note, KCSAN will not report all data races due to missing memory ordering,
specifically where a memory barrier would be required to prohibit subsequent
memory operation from reordering before the barrier. Developers should
therefore carefully consider the required memory ordering requirements that
remain unchecked.
Race Detection Beyond Data Races
--------------------------------
For code with complex concurrency design, race-condition bugs may not always
manifest as data races. Race conditions occur if concurrently executing
operations result in unexpected system behaviour. On the other hand, data races
are defined at the C-language level. The following macros can be used to check
properties of concurrent code where bugs would not manifest as data races.
.. kernel-doc:: include/linux/kcsan-checks.h
:functions: ASSERT_EXCLUSIVE_WRITER ASSERT_EXCLUSIVE_WRITER_SCOPED
ASSERT_EXCLUSIVE_ACCESS ASSERT_EXCLUSIVE_ACCESS_SCOPED
ASSERT_EXCLUSIVE_BITS
Implementation Details
----------------------
KCSAN relies on observing that two accesses happen concurrently. Crucially, we
want to (a) increase the chances of observing races (especially for races that
manifest rarely), and (b) be able to actually observe them. We can accomplish
(a) by injecting various delays, and (b) by using address watchpoints (or
breakpoints).
If we deliberately stall a memory access, while we have a watchpoint for its
address set up, and then observe the watchpoint to fire, two accesses to the
same address just raced. Using hardware watchpoints, this is the approach taken
in `DataCollider
<http://usenix.org/legacy/events/osdi10/tech/full_papers/Erickson.pdf>`_.
Unlike DataCollider, KCSAN does not use hardware watchpoints, but instead
relies on compiler instrumentation and "soft watchpoints".
In KCSAN, watchpoints are implemented using an efficient encoding that stores
access type, size, and address in a long; the benefits of using "soft
watchpoints" are portability and greater flexibility. KCSAN then relies on the
compiler instrumenting plain accesses. For each instrumented plain access:
1. Check if a matching watchpoint exists; if yes, and at least one access is a
write, then we encountered a racing access.
2. Periodically, if no matching watchpoint exists, set up a watchpoint and
stall for a small randomized delay.
3. Also check the data value before the delay, and re-check the data value
after delay; if the values mismatch, we infer a race of unknown origin.
To detect data races between plain and marked accesses, KCSAN also annotates
marked accesses, but only to check if a watchpoint exists; i.e. KCSAN never
sets up a watchpoint on marked accesses. By never setting up watchpoints for
marked operations, if all accesses to a variable that is accessed concurrently
are properly marked, KCSAN will never trigger a watchpoint and therefore never
report the accesses.
Modeling Weak Memory
~~~~~~~~~~~~~~~~~~~~
KCSAN's approach to detecting data races due to missing memory barriers is
based on modeling access reordering (with ``CONFIG_KCSAN_WEAK_MEMORY=y``).
Each plain memory access for which a watchpoint is set up, is also selected for
simulated reordering within the scope of its function (at most 1 in-flight
access).
Once an access has been selected for reordering, it is checked along every
other access until the end of the function scope. If an appropriate memory
barrier is encountered, the access will no longer be considered for simulated
reordering.
When the result of a memory operation should be ordered by a barrier, KCSAN can
then detect data races where the conflict only occurs as a result of a missing
barrier. Consider the example::
int x, flag;
void T1(void)
{
x = 1; // data race!
WRITE_ONCE(flag, 1); // correct: smp_store_release(&flag, 1)
}
void T2(void)
{
while (!READ_ONCE(flag)); // correct: smp_load_acquire(&flag)
... = x; // data race!
}
When weak memory modeling is enabled, KCSAN can consider ``x`` in ``T1`` for
simulated reordering. After the write of ``flag``, ``x`` is again checked for
concurrent accesses: because ``T2`` is able to proceed after the write of
``flag``, a data race is detected. With the correct barriers in place, ``x``
would not be considered for reordering after the proper release of ``flag``,
and no data race would be detected.
Deliberate trade-offs in complexity but also practical limitations mean only a
subset of data races due to missing memory barriers can be detected. With
currently available compiler support, the implementation is limited to modeling
the effects of "buffering" (delaying accesses), since the runtime cannot
"prefetch" accesses. Also recall that watchpoints are only set up for plain
accesses, and the only access type for which KCSAN simulates reordering. This
means reordering of marked accesses is not modeled.
A consequence of the above is that acquire operations do not require barrier
instrumentation (no prefetching). Furthermore, marked accesses introducing
address or control dependencies do not require special handling (the marked
access cannot be reordered, later dependent accesses cannot be prefetched).
Key Properties
~~~~~~~~~~~~~~
1. **Memory Overhead:** The overall memory overhead is only a few MiB
depending on configuration. The current implementation uses a small array of
longs to encode watchpoint information, which is negligible.
2. **Performance Overhead:** KCSAN's runtime aims to be minimal, using an
efficient watchpoint encoding that does not require acquiring any shared
locks in the fast-path. For kernel boot on a system with 8 CPUs:
- 5.0x slow-down with the default KCSAN config;
- 2.8x slow-down from runtime fast-path overhead only (set very large
``KCSAN_SKIP_WATCH`` and unset ``KCSAN_SKIP_WATCH_RANDOMIZE``).
3. **Annotation Overheads:** Minimal annotations are required outside the KCSAN
runtime. As a result, maintenance overheads are minimal as the kernel
evolves.
4. **Detects Racy Writes from Devices:** Due to checking data values upon
setting up watchpoints, racy writes from devices can also be detected.
5. **Memory Ordering:** KCSAN is aware of only a subset of LKMM ordering rules;
this may result in missed data races (false negatives).
6. **Analysis Accuracy:** For observed executions, due to using a sampling
strategy, the analysis is *unsound* (false negatives possible), but aims to
be complete (no false positives).
Alternatives Considered
-----------------------
An alternative data race detection approach for the kernel can be found in the
`Kernel Thread Sanitizer (KTSAN)
<https://github.com/google/kernel-sanitizers/blob/master/KTSAN.md>`_.
KTSAN is a happens-before data race detector, which explicitly establishes the
happens-before order between memory operations, which can then be used to
determine data races as defined in `Data Races`_.
To build a correct happens-before relation, KTSAN must be aware of all ordering
rules of the LKMM and synchronization primitives. Unfortunately, any omission
leads to large numbers of false positives, which is especially detrimental in
the context of the kernel which includes numerous custom synchronization
mechanisms. To track the happens-before relation, KTSAN's implementation
requires metadata for each memory location (shadow memory), which for each page
corresponds to 4 pages of shadow memory, and can translate into overhead of
tens of GiB on a large system.
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
KCSAN 개요와 활성화
1-23SPDX 라이선스 식별자: GPL-2.0
저작권 (C) 2019, Google LLC.
Kernel Concurrency Sanitizer (KCSAN)
Kernel Concurrency Sanitizer(KCSAN)는 compile-time instrumentation에 의존하고 watchpoint 기반 sampling 방식으로 race를 탐지하는 동적 race detector입니다. KCSAN의 주된 목적은 `data race`를 탐지하는 것입니다.
사용법
KCSAN은 GCC와 Clang 모두 지원합니다. GCC는 version 11 이상, Clang도 version 11 이상이 필요합니다.
KCSAN을 활성화하려면 kernel을 다음과 같이 구성하십시오.
CONFIG_KCSAN = yKCSAN은 동작을 사용자 지정하는 여러 configuration option도 제공합니다. 자세한 내용은 `lib/Kconfig.kcsan`의 각 help text를 참조하십시오.
data race report 해석
24-81Error report
일반적인 data race report는 다음과 같습니다.
==================================================================
BUG: KCSAN: data-race in test_kernel_read / test_kernel_write
write to 0xffffffffc009a628 of 8 bytes by task 487 on cpu 0:
test_kernel_write+0x1d/0x30
access_thread+0x89/0xd0
kthread+0x23e/0x260
ret_from_fork+0x22/0x30
read to 0xffffffffc009a628 of 8 bytes by task 488 on cpu 6:
test_kernel_read+0x10/0x20
access_thread+0x89/0xd0
kthread+0x23e/0x260
ret_from_fork+0x22/0x30
value changed: 0x00000000000009a6 -> 0x00000000000009b2
Reported by Kernel Concurrency Sanitizer on:
CPU: 6 PID: 488 Comm: access_thread Not tainted 5.12.0-rc2+ #1
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
==================================================================report header는 race에 관련된 함수를 짧게 요약합니다. 이어서 data race에 관련된 두 thread의 access type과 stack trace가 나옵니다. KCSAN이 value change도 관찰했다면 `value changed` 줄에 관찰한 old value와 new value를 차례로 표시합니다.
덜 일반적인 다른 유형의 data race report는 다음과 같습니다.
==================================================================
BUG: KCSAN: data-race in test_kernel_rmw_array+0x71/0xd0
race at unknown origin, with read to 0xffffffffc009bdb0 of 8 bytes by task 515 on cpu 2:
test_kernel_rmw_array+0x71/0xd0
access_thread+0x89/0xd0
kthread+0x23e/0x260
ret_from_fork+0x22/0x30
value changed: 0x0000000000002328 -> 0x0000000000002329
Reported by Kernel Concurrency Sanitizer on:
CPU: 2 PID: 515 Comm: access_thread Not tainted 5.12.0-rc2+ #1
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
==================================================================상대 thread stack 없이 race를 추론할 때 출력되는 필드를 정리했습니다.
두 diagnostic 형식에서 확인할 수 있는 동시성 단서를 비교합니다.
다른 racing thread를 확인할 수 없지만 관찰 중인 memory location의 data value가 바뀌어 race를 추론한 경우 이 report를 생성합니다. 이 report에는 항상 `value changed` 줄이 있습니다. 흔한 원인은 racing thread의 instrumentation 누락이지만 DMA access 등으로도 발생할 수 있습니다. 기본적으로 활성화되는 `CONFIG_KCSAN_REPORT_RACE_UNKNOWN_ORIGIN=y`일 때만 이 report를 표시합니다.
선택적 분석과 report class
82-151선택적 분석
특정 access, function, compilation unit 또는 subsystem 전체의 data race 탐지를 비활성화하고 싶을 수 있습니다. 정적 blacklist에는 다음 option을 사용할 수 있습니다.
KCSAN은 `data_race(expr)` annotation을 이해합니다. 이는 `expr` 안의 access에서 생기는 data race를 무시하고 data race를 만났을 때의 결과 동작이 안전한 것으로 간주하라고 KCSAN에 알립니다. 자세한 내용은 LKMM의 'Marking Shared-Memory Accesses'를 참조하십시오.
`data_race(...)`와 비슷하게 `__data_racy` type qualifier를 사용하면 variable access에서 생기는 모든 data race가 의도된 것이며 KCSAN이 무시해야 함을 문서화할 수 있습니다.
struct foo {
...
int __data_racy stats_counter;
...
};function 전체의 data race 탐지는 `__no_kcsan` function attribute로 비활성화할 수 있습니다.
__no_kcsan
void foo(void) {
...report를 생성할 function을 동적으로 제한하려면 DebugFS interface의 blacklist/whitelist 기능을 참조하십시오.
특정 compilation unit의 data race 탐지를 비활성화하려면 `Makefile`에 다음을 추가하십시오.
KCSAN_SANITIZE_file.o := n`Makefile`에 나열된 모든 compilation unit의 data race 탐지를 비활성화하려면 해당 `Makefile`에 다음을 추가하십시오.
KCSAN_SANITIZE := nLKMM의 Marking Shared-Memory Accesses: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/memory-model/Documentation/access-marking.txt
또한 선호에 따라 data race class 전체를 표시하거나 숨기도록 KCSAN에 지시할 수 있습니다. 다음 Kconfig option으로 바꿀 수 있습니다.
`CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY`: 활성화한 상태에서 watchpoint를 통해 충돌하는 write를 관찰했지만 memory location의 data value가 바뀌지 않았다면 data race를 보고하지 않습니다.
`CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC`: word size 이하의 plain aligned write를 기본적으로 atomic이라고 가정합니다. 이런 write가 data race를 일으키는 unsafe compiler optimization의 대상이 아니라고 가정합니다. 유일한 plain access가 word size 이하의 aligned write인 충돌은 KCSAN이 보고하지 않습니다.
`CONFIG_KCSAN_PERMISSIVE`: 흔한 data race의 특정 class를 무시하는 추가 permissive rule을 활성화합니다. 앞 option들과 달리 value-change pattern, access type, address를 함께 다루는 더 복잡한 규칙입니다. `CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=y`에 의존합니다. 자세한 내용은 `kernel/kcsan/permissive.h`를 참조하십시오. kernel 전체가 아니라 특정 subsystem report만 보는 tester와 maintainer는 이 option을 비활성화하는 것이 좋습니다.
가능한 가장 엄격한 규칙을 사용하려면 `CONFIG_KCSAN_STRICT=y`를 선택하십시오. KCSAN이 Linux-kernel memory consistency model(LKMM)을 최대한 가깝게 따르도록 구성합니다.
DebugFS 제어와 성능 조정
152-196DebugFS interface
`/sys/kernel/debug/kcsan` 파일은 다음 interface를 제공합니다.
파일을 읽으면 여러 runtime statistic을 반환합니다.
파일에 `on` 또는 `off`를 쓰면 각각 KCSAN을 켜거나 끌 수 있습니다.
`!some_func_name`을 쓰면 `some_func_name`을 report filter list에 추가합니다. 기본적으로 top stack frame 중 하나라도 list의 function이면 해당 data race report를 blacklist합니다.
`blacklist` 또는 `whitelist`를 쓰면 report filtering 동작을 바꿉니다. blacklist로 자주 발생하는 data race를 숨길 수 있고 whitelist로 수정 사항을 재현하고 test하는 데 도움을 받을 수 있습니다.
성능 조정
KCSAN의 전체 성능과 bug 탐지 능력에 영향을 주는 핵심 parameter는 kernel command-line argument로 노출되며, 대응하는 Kconfig option으로 기본값도 바꿀 수 있습니다.
`kcsan.skip_watch`(`CONFIG_KCSAN_SKIP_WATCH`): 다음 watchpoint를 설정하기 전에 건너뛸 CPU별 memory operation 수입니다. watchpoint를 더 자주 설정하면 race를 관찰할 가능성이 높아집니다. 전체 system 성능과 race 탐지 능력에 가장 큰 영향을 줍니다.
`kcsan.udelay_task`(`CONFIG_KCSAN_UDELAY_TASK`): task에서 watchpoint를 설정한 뒤 실행을 멈출 microsecond delay입니다. 값이 클수록 race를 관찰할 수 있는 window가 커집니다.
`kcsan.udelay_interrupt`(`CONFIG_KCSAN_UDELAY_INTERRUPT`): interrupt에서 watchpoint를 설정한 뒤 실행을 멈출 microsecond delay입니다. interrupt는 latency 요구가 더 엄격하므로 일반적으로 task보다 작은 delay를 선택해야 합니다.
이 값들은 runtime에 `/sys/module/kcsan/parameters/`를 통해 조정할 수 있습니다.
data race 정의와 LKMM 관계
197-228Data Race
한 실행에서 두 memory access가 충돌하고, 서로 다른 thread에서 동시에 발생하며, 둘 중 하나 이상이 plain access이면 data race를 이룹니다. 두 access가 같은 memory location을 다루고 하나 이상이 write이면 충돌합니다. 더 자세한 논의와 정의는 LKMM의 'Plain Accesses and Data Races'를 참조하십시오.
LKMM의 Plain Accesses and Data Races: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/memory-model/Documentation/explanation.txt?id=8f6629c004b193d23612641c3607e785819e97ab#n2164
Linux-Kernel Memory Consistency Model(LKMM)과의 관계
LKMM은 여러 memory operation의 propagation과 ordering rule을 정의해 개발자가 concurrent code를 추론할 수 있게 합니다. 궁극적으로 concurrent code의 가능한 실행과 data race가 없는지를 판단할 수 있습니다.
KCSAN은 `READ_ONCE`, `WRITE_ONCE`, `atomic_*` 같은 marked atomic operation과 memory barrier가 내포하는 ordering guarantee 일부를 인식합니다. `CONFIG_KCSAN_WEAK_MEMORY=y`에서는 load 또는 store buffering을 modeling하며 누락된 `smp_mb()`, `smp_wmb()`, `smp_rmb()`, `smp_store_release()` 및 동등한 barrier를 내포하는 모든 `atomic_*` operation을 탐지할 수 있습니다.
KCSAN은 memory ordering 누락으로 생기는 모든 data race를 보고하지는 않습니다. 특히 이후 memory operation이 barrier 앞으로 reorder되는 것을 막기 위해 barrier가 필요한 경우가 그렇습니다. 개발자는 검사되지 않고 남는 memory ordering 요구 사항을 주의 깊게 고려해야 합니다.
data race를 넘어선 race 탐지
229-242Data Race를 넘어선 race 탐지
복잡한 concurrency design의 코드에서는 race-condition bug가 항상 data race로 나타나지는 않습니다. race condition은 동시에 실행되는 operation이 예상하지 못한 system 동작을 만들 때 발생하는 반면 data race는 C language 수준에서 정의됩니다. 다음 macro로 bug가 data race로 나타나지 않는 concurrent code property를 검사할 수 있습니다.
.. kernel-doc:: include/linux/kcsan-checks.h
:functions: ASSERT_EXCLUSIVE_WRITER ASSERT_EXCLUSIVE_WRITER_SCOPED
ASSERT_EXCLUSIVE_ACCESS ASSERT_EXCLUSIVE_ACCESS_SCOPED
ASSERT_EXCLUSIVE_BITSsoft watchpoint 기반 구현
243-280구현 세부 사항
KCSAN은 두 access가 동시에 발생함을 관찰하는 데 의존합니다. 특히 드물게 나타나는 race까지 관찰할 가능성을 높이고 실제로 관찰할 수 있어야 합니다. 여러 delay를 주입해 첫 목표를 달성하고 address watchpoint 또는 breakpoint로 두 번째 목표를 달성할 수 있습니다.
memory access를 의도적으로 멈추고 해당 address의 watchpoint를 설정한 상태에서 watchpoint가 발동하는 것을 관찰하면 같은 address에 대한 두 access가 방금 race한 것입니다. hardware watchpoint를 쓰는 DataCollider도 이 방식을 사용합니다. KCSAN은 DataCollider와 달리 hardware watchpoint를 사용하지 않고 compiler instrumentation과 `soft watchpoint`에 의존합니다.
KCSAN의 watchpoint는 access type, size, address를 long 하나에 저장하는 효율적인 encoding으로 구현됩니다. soft watchpoint는 portability와 더 큰 flexibility를 제공합니다. compiler는 plain access를 instrumentation하며 각 instrumented plain access에서 다음을 수행합니다.
1. 일치하는 watchpoint가 있는지 확인합니다. 있고 access 중 하나 이상이 write이면 racing access를 만난 것입니다.
2. 일치하는 watchpoint가 없으면 주기적으로 watchpoint를 설정하고 작은 random delay 동안 멈춥니다.
3. delay 전 data value와 delay 후 data value를 다시 확인합니다. 값이 다르면 origin을 알 수 없는 race를 추론합니다.
plain access와 marked access 사이의 data race를 탐지하기 위해 KCSAN은 marked access에도 annotation을 지정하지만 watchpoint 존재 여부만 검사합니다. marked access에는 watchpoint를 설정하지 않습니다. 동시에 접근하는 variable의 모든 access가 올바르게 marked되어 있으면 KCSAN은 watchpoint를 발동시키지 않으므로 해당 access를 보고하지 않습니다.
weak memory modeling
281-330Weak Memory modeling
memory barrier 누락으로 인한 data race 탐지는 `CONFIG_KCSAN_WEAK_MEMORY=y`를 사용한 access reordering modeling을 기반으로 합니다. watchpoint가 설정된 각 plain memory access는 function scope 안에서 simulated reordering 대상으로도 선택되며, 동시에 진행 중인 access는 최대 하나입니다.
reordering 대상으로 선택된 access는 function scope가 끝날 때까지 다른 모든 access와 함께 검사됩니다. 적절한 memory barrier를 만나면 더 이상 simulated reordering 대상으로 보지 않습니다.
memory operation 결과가 barrier로 order되어야 할 때 KCSAN은 barrier 누락으로 인해 충돌하는 data race를 탐지할 수 있습니다. 다음 예를 보십시오.
int x, flag;
void T1(void)
{
x = 1; // data race!
WRITE_ONCE(flag, 1); // correct: smp_store_release(&flag, 1)
}
void T2(void)
{
while (!READ_ONCE(flag)); // correct: smp_load_acquire(&flag)
... = x; // data race!
}weak memory modeling을 활성화하면 KCSAN은 T1의 `x`를 simulated reordering 대상으로 볼 수 있습니다. `flag` write 뒤 `x`의 concurrent access를 다시 검사합니다. T2가 `flag` write 후 진행할 수 있으므로 data race를 탐지합니다. 올바른 barrier가 있으면 `flag`를 적절히 release한 뒤 `x`를 reordering 대상으로 보지 않으므로 data race를 탐지하지 않습니다.
의도적으로 complexity를 절충한 점과 실질적 한계 때문에 memory barrier 누락으로 생기는 data race 일부만 탐지할 수 있습니다. 현재 compiler 지원에서는 runtime이 access를 prefetch할 수 없으므로 buffering, 즉 access 지연의 효과만 modeling합니다. watchpoint는 plain access에만 설정되고 KCSAN이 reordering을 simulate하는 유일한 access type도 plain access입니다. marked access의 reordering은 modeling하지 않습니다.
따라서 acquire operation에는 barrier instrumentation이 필요하지 않습니다. prefetch가 없기 때문입니다. address 또는 control dependency를 만드는 marked access도 특별히 처리할 필요가 없습니다. marked access는 reorder될 수 없고 이후 dependent access는 prefetch될 수 없습니다.
핵심 특성과 절충점
331-359핵심 특성
1. Memory overhead: configuration에 따라 전체 memory overhead는 몇 MiB에 불과합니다. 현재 구현은 작은 long array로 watchpoint 정보를 encode하므로 무시할 수 있는 수준입니다.
2. Performance overhead: KCSAN runtime은 fast path에서 shared lock을 잡을 필요가 없는 효율적 watchpoint encoding을 사용해 비용을 최소화합니다. CPU 8개 system에서 kernel boot는 기본 KCSAN config로 5.0배 느려지고, 매우 큰 `KCSAN_SKIP_WATCH`를 설정하고 `KCSAN_SKIP_WATCH_RANDOMIZE`를 해제해 runtime fast-path overhead만 측정하면 2.8배 느려집니다.
3. Annotation overhead: KCSAN runtime 밖에는 최소한의 annotation만 필요하므로 kernel이 발전해도 maintenance overhead가 작습니다.
4. Device의 racy write 탐지: watchpoint 설정 시 data value를 검사하므로 device의 racy write도 탐지할 수 있습니다.
5. Memory ordering: KCSAN은 LKMM ordering rule 일부만 인식하므로 data race를 놓치는 false negative가 생길 수 있습니다.
6. 분석 정확도: sampling 전략 때문에 관찰된 실행에 대한 분석은 sound하지 않아 false negative가 가능하지만 complete하게, 즉 false positive가 없도록 하는 것을 목표로 합니다.
검토한 대안 KTSAN
360-377검토한 대안
kernel의 다른 data race 탐지 방식은 `Kernel Thread Sanitizer(KTSAN) <https://github.com/google/kernel-sanitizers/blob/master/KTSAN.md>`에서 볼 수 있습니다. KTSAN은 memory operation 사이의 happens-before order를 명시적으로 세우고 이를 사용해 'Data Race'에서 정의한 race를 판단하는 happens-before data race detector입니다.
올바른 happens-before relation을 만들려면 KTSAN이 LKMM의 모든 ordering rule과 synchronization primitive를 알아야 합니다. 하나라도 빠지면 false positive가 대량으로 생기며 custom synchronization mechanism이 많은 kernel에서는 특히 해롭습니다. happens-before relation을 추적하려면 memory location마다 metadata, 즉 shadow memory가 필요합니다. 각 page마다 shadow memory 4page가 필요하므로 큰 system에서는 수십 GiB의 overhead로 이어질 수 있습니다.
요약과 해설
kcsan.rst:1-377KCSAN은 compiler instrumentation과 soft watchpoint를 이용해 동시에 충돌하는 memory access를 sampling합니다. marked atomic operation과 barrier 일부를 인식하며, value change를 이용해 instrumentation되지 않은 write나 DMA에서 비롯된 unknown-origin race도 추론할 수 있습니다.
sampling detector이므로 false negative는 가능하지만 false positive를 만들지 않는 것을 목표로 합니다. report filter와 delay·watch 주기를 조정할 때는 탐지 확률과 성능을 함께 고려하고, KCSAN이 확인하지 못하는 LKMM ordering 요구 사항은 별도로 검토해야 합니다.