英语

内核并发清理器 (KCSAN)

内核并发清理器 (KCSAN) 是一种动态竞争检测器，它依赖于编译时插桩，并使用基于监视点的采样方法来检测竞争。KCSAN 的主要目的是检测数据竞争。

用法

GCC 和 Clang 都支持 KCSAN。对于 GCC，我们需要 11 或更高版本，对于 Clang，我们也需要 11 或更高版本。

要启用 KCSAN，请使用以下配置内核

CONFIG_KCSAN = y

KCSAN 提供了其他几个配置选项来自定义行为（有关更多信息，请参阅lib/Kconfig.kcsan中的相应帮助文本）。

错误报告

典型的数据竞争报告如下所示

==================================================================
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
==================================================================

报告的头部提供了有关竞争中涉及的函数的简短摘要。接下来是数据竞争中涉及的 2 个线程的访问类型和堆栈跟踪。如果 KCSAN 还观察到值更改，则观察到的旧值和新值将分别显示在“值已更改”行中。

另一种不太常见的数据竞争报告如下所示

==================================================================
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
==================================================================

生成此报告的原因是无法确定其他竞争线程，但由于被监视的内存位置的数据值已更改，因此推断出存在竞争。这些报告始终显示“值已更改”行。此类型报告的常见原因是竞争线程中缺少插桩，但也可能是由于 DMA 访问等原因而发生的。仅当CONFIG_KCSAN_REPORT_RACE_UNKNOWN_ORIGIN=y时才会显示此类报告，默认情况下启用此选项。

选择性分析

可能需要为特定访问、函数、编译单元或整个子系统禁用数据竞争检测。对于静态黑名单，可以使用以下选项

  • KCSAN 理解data_race(expr) 注释，该注释告诉 KCSAN 应该忽略由于expr中的访问而引起的任何数据竞争，并且当遇到数据竞争时的结果行为被认为是安全的。有关更多信息，请参阅LKMM 中的“标记共享内存访问”。

  • 与data_race(...)类似，类型限定符__data_racy可用于记录所有由于访问变量而引起的数据竞争都是预期的，并且应被 KCSAN 忽略

    struct foo {
    ...
    int __data_racy stats_counter;
    ...
};

  • 可以使用函数属性__no_kcsan来禁用整个函数的数据竞争检测

    __no_kcsan
void foo(void) {
    ...

    要动态限制为哪些函数生成报告，请参阅DebugFS 接口黑名单/白名单功能。

  • 要禁用特定编译单元的数据竞争检测，请添加到Makefile中

    KCSAN_SANITIZE_file.o := n

  • 要禁用 Makefile 中列出的所有编译单元的数据竞争检测，请添加到相应的 Makefile 中

    KCSAN_SANITIZE := n

此外，还可以根据偏好，告知 KCSAN 显示或隐藏整个数据竞争类别。这些可以通过以下 Kconfig 选项进行更改

  • CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY: 如果启用，并且通过监视点观察到冲突写入，但是观察到内存位置的数据值保持不变，则不报告数据竞争。

  • CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC：默认情况下，假定最大字长的简单对齐写入是原子的。假定此类写入不会受到不安全的编译器优化而导致数据竞争。此选项导致 KCSAN 不报告由于冲突而导致的数据竞争，其中唯一的简单访问是最大字长的对齐写入。

  • CONFIG_KCSAN_PERMISSIVE：启用其他宽松规则以忽略某些常见的数据竞争类别。与上述规则不同，这些规则更复杂，涉及值更改模式、访问类型和地址。此选项依赖于CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=y。有关详细信息，请参阅kernel/kcsan/permissive.h。建议仅关注来自特定子系统而非整个内核的报告的测试人员和维护人员禁用此选项。

要使用尽可能严格的规则，请选择CONFIG_KCSAN_STRICT=y，该选项将 KCSAN 配置为尽可能遵循 Linux 内核内存一致性模型 (LKMM)。

DebugFS 接口

文件/sys/kernel/debug/kcsan提供以下接口

  • 读取 /sys/kernel/debug/kcsan 返回各种运行时统计信息。

  • 写入on或off到/sys/kernel/debug/kcsan允许分别打开或关闭 KCSAN。

  • 写入 !some_func_name 到 /sys/kernel/debug/kcsan 将 some_func_name 添加到报告筛选列表，该列表（默认情况下）会将其中一个顶部堆栈帧是列表中的函数的报告的数据竞争列入黑名单。

  • 写入 blacklist 或 whitelist 到 /sys/kernel/debug/kcsan 会更改报告筛选行为。例如，黑名单功能可用于使频繁发生的数据竞争静默；白名单功能可以帮助修复的重现和测试。

调整性能

影响 KCSAN 整体性能和错误检测能力的核心参数作为内核命令行参数公开，这些参数的默认值也可以通过相应的 Kconfig 选项进行更改。

  • kcsan.skip_watch (CONFIG_KCSAN_SKIP_WATCH)：在设置另一个监视点之前要跳过的每个 CPU 的内存操作数。更频繁地设置监视点将导致观察到竞争的可能性增加。此参数对整体系统性能和竞争检测能力的影响最大。

  • kcsan.udelay_task (CONFIG_KCSAN_UDELAY_TASK)：对于任务，设置监视点后暂停执行的微秒延迟。较大的值会导致我们可能观察到竞争的窗口增加。

  • kcsan.udelay_interrupt (CONFIG_KCSAN_UDELAY_INTERRUPT)：对于中断，设置监视点后暂停执行的微秒延迟。中断具有更严格的延迟要求，并且它们的延迟通常应小于为任务选择的延迟。

它们可以在运行时通过 /sys/module/kcsan/parameters/ 进行调整。

数据竞争

在执行过程中，如果两个内存访问冲突，它们在不同的线程中同时发生，并且至少其中一个是简单访问，则它们会形成数据竞争；如果两者都访问相同的内存位置，并且至少一个是写入，则它们会冲突。有关更详细的讨论和定义，请参阅LKMM 中的“简单访问和数据竞争”。

与 Linux 内核内存一致性模型 (LKMM) 的关系

LKMM 定义了各种内存操作的传播和排序规则，这使开发人员能够推理并发代码。最终，这允许确定并发代码的可能执行，以及该代码是否没有数据竞争。

KCSAN 知道标记的原子操作（READ_ONCE、WRITE_ONCE、atomic_* 等）以及内存屏障隐含的排序保证的子集。使用CONFIG_KCSAN_WEAK_MEMORY=y，KCSAN 可以模拟加载或存储缓冲，并可以检测丢失的 smp_mb()、smp_wmb()、smp_rmb()、smp_store_release() 和所有具有等效隐含屏障的 atomic_* 操作。

请注意，由于缺少内存排序，KCSAN 不会报告所有数据竞争，特别是需要内存屏障来禁止后续内存操作在屏障之前重新排序的情况。因此，开发人员应仔细考虑仍然未检查的所需内存排序要求。

超出数据竞争的竞争检测

对于具有复杂并发设计的代码，竞争条件错误可能并不总是表现为数据竞争。如果并发执行的操作导致意外的系统行为，则会发生竞争条件。另一方面，数据竞争是在 C 语言级别定义的。以下宏可用于检查并发代码的属性，其中错误不会表现为数据竞争。

ASSERT_EXCLUSIVE_WRITER

ASSERT_EXCLUSIVE_WRITER (var)

断言对 var 没有并发写入

参数

var

要断言的变量

描述

断言对 var 没有并发写入；允许其他读取器。此断言可用于指定并发代码的属性，其中违规无法被检测为正常的数据竞争。

例如，如果我们只有一个写入器，但有多个并发读取器，为了避免数据竞争，所有这些访问都必须标记；即使并发标记的写入与单个写入器竞争也是错误。不幸的是，由于被标记，它们不再是数据竞争。对于这种情况，我们可以使用以下宏

void writer(void) {
        spin_lock(&update_foo_lock);
        ASSERT_EXCLUSIVE_WRITER(shared_foo);
        WRITE_ONCE(shared_foo, ...);
        spin_unlock(&update_foo_lock);
}
void reader(void) {
        // update_foo_lock does not need to be held!
        ... = READ_ONCE(shared_foo);
}

注意

如果适用，ASSERT_EXCLUSIVE_WRITER_SCOPED() 会执行更彻底的检查，如果存在明确的范围，在该范围内不应存在并发写入。

ASSERT_EXCLUSIVE_WRITER_SCOPED

ASSERT_EXCLUSIVE_WRITER_SCOPED (var)

断言在作用域内对 var 没有并发写入

参数

var

要断言的变量

描述

ASSERT_EXCLUSIVE_WRITER() 的作用域变体。

断言在引入它的作用域的持续时间内，对 var 没有并发写入。与多个 ASSERT_EXCLUSIVE_WRITER() 相比，这提供了一种更好地完全覆盖封闭作用域的方法，并增加了 KCSAN 检测到竞争访问的可能性。

例如，它允许查找仅由于作用域本身内的状态更改而发生的竞争条件错误

void writer(void) {
        spin_lock(&update_foo_lock);
        {
                ASSERT_EXCLUSIVE_WRITER_SCOPED(shared_foo);
                WRITE_ONCE(shared_foo, 42);
                ...
                // shared_foo should still be 42 here!
        }
        spin_unlock(&update_foo_lock);
}
void buggy(void) {
        if (READ_ONCE(shared_foo) == 42)
                WRITE_ONCE(shared_foo, 1); // bug!
}
ASSERT_EXCLUSIVE_ACCESS

ASSERT_EXCLUSIVE_ACCESS (var)

断言对 var 没有并发访问

参数

var

要断言的变量

描述

断言对 var 没有并发访问（没有读取器或写入器）。此断言可用于指定并发代码的属性，其中违规无法被检测为正常的数据竞争。

例如，在确定对象没有其他用户后，期望独占访问，但实际上并未释放对象。我们可以检查此属性是否如下所示

if (refcount_dec_and_test(&obj->refcnt)) {
        ASSERT_EXCLUSIVE_ACCESS(*obj);
        do_some_cleanup(obj);
        release_for_reuse(obj);
}

  1. 如果适用，ASSERT_EXCLUSIVE_ACCESS_SCOPED() 会执行更彻底的检查，如果存在明确的范围，在该范围内不应存在并发访问。

  2. 对于释放对象的情况，KASAN 更适合检测释放后使用错误。

注意

ASSERT_EXCLUSIVE_ACCESS_SCOPED

ASSERT_EXCLUSIVE_ACCESS_SCOPED (var)

断言在作用域内对 var 没有并发访问

参数

var

要断言的变量

描述

ASSERT_EXCLUSIVE_ACCESS() 的作用域变体。

断言在引入它的作用域的整个持续时间内，对 var 没有并发访问（没有读取器或写入器）。与多个 ASSERT_EXCLUSIVE_ACCESS() 相比，这提供了一种更好地完全覆盖封闭作用域的方法，并增加了 KCSAN 检测到竞争访问的可能性。

ASSERT_EXCLUSIVE_BITS

ASSERT_EXCLUSIVE_BITS (var, mask)

断言对 var 中位子集的并发写入

参数

var

要断言的变量

mask

仅检查对 mask 中设置的位的修改

描述

ASSERT_EXCLUSIVE_WRITER() 的位粒度变体。

断言对 var 中位子集没有并发写入；允许并发读取器。与其他（字粒度）断言相比，此断言捕获了更详细的位级属性。仅检查 mask 中设置的位是否存在并发修改，同时忽略其余的位，即忽略对 ~mask 位的并发写入（或读取）。

对于某些位不能并发修改，但其他位应该并发修改的变量，请使用此选项。

例如，对于某些位在初始化后是只读的，但其他位仍可以并发修改的变量。读取器可能希望断言以下情况为真

ASSERT_EXCLUSIVE_BITS(flags, READ_ONLY_MASK);
foo = (READ_ONCE(flags) & READ_ONLY_MASK) >> READ_ONLY_SHIFT;

ASSERT_EXCLUSIVE_BITS(flags, READ_ONLY_MASK);
foo = (flags & READ_ONLY_MASK) >> READ_ONLY_SHIFT;

另一个可以使用它的示例是，当只有在持有适当的锁时才能修改 var 的某些位，但其他位仍然可以并发修改时。其他位可能会并发更改的写入器可以使用以下断言

spin_lock(&foo_lock);
ASSERT_EXCLUSIVE_BITS(flags, FOO_MASK);
old_flags = flags;
new_flags = (old_flags & ~FOO_MASK) | (new_foo << FOO_SHIFT);
if (cmpxchg(&flags, old_flags, new_flags) != old_flags) { ... }
spin_unlock(&foo_lock);

注意

紧随 ASSERT_EXCLUSIVE_BITS() 的访问假定仅访问掩码位，并且 KCSAN 乐观地假设它是安全的，即使存在数据竞争，并且从 KCSAN 的角度来看，使用 READ_ONCE() 是可选的。但是，我们警告说，这样做可能仍然是明智的，因为当涉及到位操作时，我们无法推断所有编译器优化（在读取器和写入器侧）。如果您确定不会出现任何问题，我们可以简单地将上述内容写为

实现细节

KCSAN 依赖于观察到两次访问同时发生。至关重要的是，我们希望 (a) 增加观察到竞争的机会（特别是对于很少出现的竞争），以及 (b) 能够实际观察到它们。我们可以通过注入各种延迟来实现 (a)，并通过使用地址观察点（或断点）来实现 (b)。

如果我们故意停止内存访问，同时为它的地址设置了观察点，然后观察到观察点触发，则对同一地址的两次访问刚刚竞争。使用硬件观察点，这是 DataCollider 中采用的方法。与 DataCollider 不同，KCSAN 不使用硬件观察点，而是依赖于编译器插桩和“软观察点”。

在 KCSAN 中，观察点使用高效的编码实现，该编码将访问类型、大小和地址存储在一个长整型中；使用“软观察点”的好处是可移植性和更大的灵活性。然后，KCSAN 依赖于编译器来对普通访问进行插桩。对于每个插桩的普通访问

  1. 检查是否存在匹配的观察点；如果存在，且至少有一个访问是写入，则我们遇到了竞争访问。

  2. 定期地，如果不存在匹配的观察点，则设置一个观察点并延迟一小段随机时间。

  3. 还检查延迟之前的数据值，并在延迟之后重新检查数据值；如果值不匹配，则我们会推断出未知来源的竞争。

为了检测普通访问和标记访问之间的数据竞争，KCSAN 还会注释标记访问，但仅用于检查是否存在观察点；即 KCSAN 永远不会在标记访问上设置观察点。通过从不在标记操作上设置观察点，如果所有对并发访问的变量的访问都正确标记，则 KCSAN 将永远不会触发观察点，因此永远不会报告访问。

模拟弱内存

KCSAN 检测由于缺少内存屏障导致的数据竞争的方法基于模拟访问重新排序（使用 CONFIG_KCSAN_WEAK_MEMORY=y）。为每个设置观察点的普通内存访问，也会在其函数的作用域内选择模拟重新排序（最多 1 个正在进行的访问）。

一旦选择了重新排序的访问，就会检查函数作用域结束之前的每个其他访问。如果遇到适当的内存屏障，则该访问将不再被视为模拟重新排序。

当内存操作的结果应由屏障排序时，KCSAN 可以检测到仅由于缺少屏障而发生冲突的数据竞争。考虑以下示例

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!
}

当启用弱内存建模时，KCSAN 可以考虑 T1 中的 x 进行模拟重新排序。在写入 flag 后，再次检查 x 是否存在并发访问：因为 T2 能够在写入 flag 后继续，所以检测到数据竞争。如果正确设置了屏障，则在正确释放 flag 后，将不再考虑 x 进行重新排序，并且不会检测到数据竞争。

复杂性方面的有意权衡以及实际限制意味着只能检测到由于缺少内存屏障而导致的数据竞争的子集。由于目前可用的编译器支持，该实现仅限于模拟“缓冲”（延迟访问）的效果，因为运行时无法“预取”访问。还要记住，观察点仅为普通访问设置，并且 KCSAN 模拟重新排序的唯一访问类型。这意味着不模拟标记访问的重新排序。

上述情况的一个结果是，获取操作不需要屏障插桩（没有预取）。此外，引入地址或控制依赖项的标记访问不需要特殊处理（不能重新排序标记访问，也不能预取稍后依赖的访问）。

关键属性

  1. 内存开销：总体内存开销只有几个 MiB，具体取决于配置。当前实现使用一个小的长整型数组来编码观察点信息，这可以忽略不计。

  2. 性能开销： KCSAN 的运行时目标是最小化开销，它使用一种高效的观察点编码，在快速路径中不需要获取任何共享锁。在具有 8 个 CPU 的系统上进行内核引导时：

    • 使用默认 KCSAN 配置，速度降低 5.0 倍；

    • 仅运行时快速路径开销导致速度降低 2.8 倍（设置非常大的 KCSAN_SKIP_WATCH 并取消设置 KCSAN_SKIP_WATCH_RANDOMIZE）。

  3. 注释开销： 在 KCSAN 运行时之外，只需要最少的注释。因此，随着内核的演进，维护开销是最小的。

  4. 检测来自设备的竞争写入： 由于在设置观察点时会检查数据值，因此也可以检测到来自设备的竞争写入。

  5. 内存排序： KCSAN 只了解 LKMM 排序规则的一个子集；这可能会导致错过数据竞争（假阴性）。

  6. 分析准确性： 对于观察到的执行，由于使用了采样策略，分析是不健全的（可能存在假阴性），但目标是完整的（没有假阳性）。

考虑的替代方案

内核的另一种数据竞争检测方法可以在内核线程清理器 (KTSAN)中找到。 KTSAN 是一种 happens-before 数据竞争检测器，它显式地建立内存操作之间的 happens-before 顺序，然后可以使用该顺序来确定数据竞争中定义的数据竞争。

为了构建正确的 happens-before 关系，KTSAN 必须知道 LKMM 的所有排序规则和同步原语。不幸的是，任何遗漏都会导致大量的误报，这在包含许多自定义同步机制的内核环境中尤其不利。为了跟踪 happens-before 关系，KTSAN 的实现需要每个内存位置的元数据（影子内存），对于每个页面，这对应于 4 个页面的影子内存，并且在大型系统上可能会转化为数十 GiB 的开销。