內(nèi)核并發(fā)消殺器KCSAN技術(shù)分析

一、KCSAN介紹

KCSAN(Kernel Concurrency Sanitizer)是一種動(dòng)態(tài)競(jìng)態(tài)檢測(cè)器，它依賴于編譯時(shí)插裝，并使用基于觀察點(diǎn)的采樣方法來檢測(cè)競(jìng)態(tài)，其主要目的是檢測(cè)數(shù)據(jù)競(jìng)爭(zhēng)。

KCSAN是一種檢測(cè)LKMM(Linux內(nèi)核內(nèi)存一致性模型)定義的數(shù)據(jù)競(jìng)爭(zhēng)(data race)的工具，同時(shí)它也可以控制報(bào)告哪種類型的數(shù)據(jù)競(jìng)爭(zhēng)。

KCSAN知道LKMM定義的所有標(biāo)記原子操作，以及LKMM尚未提到的操作，例如原子位掩碼操作(bit mask)。

KCSAN擴(kuò)展了LKMM，例如通過提供data_race()標(biāo)記，來表示存在數(shù)據(jù)競(jìng)爭(zhēng)和缺乏原子可能性。

1.1 LKMM(Linux內(nèi)核內(nèi)存一致性模型)

Linux內(nèi)核內(nèi)存模型目前在源代碼樹中的memory-barrier.txt和atomic_ops.txt文件中有非正式的定義。包含以下組成部分：

變量訪問(Variable Access)

使用READ_ONCE()、WRITE_ONCE()和ACCESS_ONCE()宏來保護(hù)從共享(但非原子)變量的加載和存儲(chǔ)；

內(nèi)存屏障(Memory Barriers)

一類同步屏障指令，是CPU或編譯器在對(duì)內(nèi)存隨機(jī)訪問的操作中的一個(gè)同步點(diǎn)，使得此點(diǎn)之前的所有讀寫操作都執(zhí)行后才可以開始執(zhí)行此點(diǎn)之后的操作。比如barrier、smp_mb/smp_wmb/smp_rmb等；

鎖操作(Locking Operations)

原子操作(Atomic Operations)

控制依賴(Control Dependencies)

Linux內(nèi)核提供了一個(gè)有限的控件依賴的概念，在某些情況下對(duì)依賴控件的存儲(chǔ)進(jìn)行優(yōu)先加載；

RCU寬限期授權(quán)關(guān)系(Grace-Period Relationships)

允許更新者等待所有已經(jīng)存在的讀側(cè)臨界區(qū)完成，再回收舊的資源；

C11原子原語 (C11 Atomics)

將原子原語的實(shí)現(xiàn)委托給編譯器；如果多個(gè)體系結(jié)構(gòu)采用這種方法，將減少體系結(jié)構(gòu)特定代碼的數(shù)量。

1.2 數(shù)據(jù)競(jìng)爭(zhēng)

為什么要關(guān)心數(shù)據(jù)競(jìng)爭(zhēng)?

C語言的發(fā)展獨(dú)立于并發(fā)性。如果給定的變量或訪問沒有任何特別之處，則變量只會(huì)在響應(yīng)當(dāng)前線程的存儲(chǔ)時(shí)發(fā)生變化。

C語言和編譯器的進(jìn)化對(duì)并發(fā)性不敏感

優(yōu)化編譯器正變得越來越豐富

因此，編譯器可以并且使用各種優(yōu)化，包括負(fù)載融合、代碼重新排序和許多其他可能導(dǎo)致并發(fā)算法故障的優(yōu)化。

讀取拆分（單次訪問多次讀?。?/p>

存儲(chǔ)拆分（單次訪問多次寫入）讀取融合（編譯器直接使用上一次對(duì)這個(gè)變量的load結(jié)果，而不是真正再去load一次）

存儲(chǔ)融合（編譯器優(yōu)化寫入變量流程，不再真實(shí)寫入）

代碼重排（把一些類似的計(jì)算歸在一起，節(jié)省占用的寄存器，改善現(xiàn)代超標(biāo)量微處理器里面各個(gè)運(yùn)算單元的利用效率）

虛擬讀?。ň幾g器優(yōu)化會(huì)導(dǎo)致多次讀取，導(dǎo)致后續(xù)加載異常）

虛擬存儲(chǔ)（編譯器優(yōu)化會(huì)導(dǎo)致多次存儲(chǔ)，導(dǎo)致后續(xù)存儲(chǔ)異常）

.....

因此需要告訴編譯器并發(fā)代碼，Linux提供內(nèi)存一致性模型，也提供檢查方法解決此類問題。

1.2.1 訪問方式

普通訪問

標(biāo)記訪問

1.2.2 同步?jīng)_突訪問的檢測(cè)條件

在訪問同一個(gè)地方并且至少有一個(gè)是寫操作

至少有一個(gè)是普通訪問（比如x+42）

以下線程打鉤的是標(biāo)準(zhǔn)做法；打叉的是可能存在數(shù)據(jù)競(jìng)爭(zhēng)的情況。

1.2.3 哪些不屬于數(shù)據(jù)競(jìng)爭(zhēng)

例如：使用不對(duì)稱的鎖機(jī)制，并且使用READ_ONCE/WRITE_ONCE標(biāo)記訪問。

二、依賴與配置方案

2.1 版本支持

KCSAN支持GCC/CLANG編譯，需要GCC版本11，CLANG 12以上版本。

x86_64: >=5.8 ARM64: >=5.17

2.2 KCSAN工具鏈支持

cc-option,-fsanitize=thread --param tsan-distinguish-volatile=1

2.3 配置選項(xiàng)支持

三、工作原理與觸發(fā)條件

3.1 使用方式

檢查未標(biāo)記讀取是否寫入競(jìng)爭(zhēng)，會(huì)持續(xù)掃描內(nèi)核的主要分支，在訪問的內(nèi)存位置上設(shè)置觀察點(diǎn)，挑出導(dǎo)致數(shù)據(jù)爭(zhēng)用的數(shù)據(jù)，并將其報(bào)告給內(nèi)核日志。

●用“軟觀察點(diǎn)”查找競(jìng)爭(zhēng)

〇設(shè)置觀察點(diǎn)和失速通道；

〇如果監(jiān)測(cè)點(diǎn)已經(jīng)存在，那么競(jìng)爭(zhēng)檢查將照常進(jìn)行；

〇如果值改變了--> 競(jìng)爭(zhēng)；

〇失速通道隨機(jī)延遲，增加觀察競(jìng)爭(zhēng)狀態(tài)的機(jī)會(huì)；

默認(rèn)值:任務(wù)[1,80]us，中斷[1,20]us。

●為所有檢測(cè)內(nèi)存訪問設(shè)置觀察點(diǎn)

〇 注釋標(biāo)記訪問，僅用于檢查非標(biāo)記訪問是否存在觀察點(diǎn)；

KCSAN從不在標(biāo)記的訪問上設(shè)置觀察點(diǎn)；

如果對(duì)并發(fā)訪問的變量的所有訪問都正確地標(biāo)記了，KCSAN將永遠(yuǎn)不會(huì)觸發(fā)觀察點(diǎn)，因此永遠(yuǎn)不會(huì)報(bào)告訪問。

●采樣: 周期性建立觀察點(diǎn)

〇默認(rèn)值:平均2000次訪問。

3.2 KCSAN軟觀測(cè)點(diǎn)

基于地址頁索引

〇可以溢出到相鄰槽。

〇使用索引確保報(bào)告元數(shù)據(jù)給匹配的生產(chǎn)者/消費(fèi)者。

具有靈活、可縮放的特點(diǎn)，以數(shù)組的形式存放。

代碼片段如下：

入口函數(shù)check_access，在check_access數(shù)據(jù)地址、長(zhǎng)度、類型；在check_access函數(shù)執(zhí)行find_watchpoint判斷。需要檢測(cè)的ptr已經(jīng)插樁編譯。

3.3 KCSAN 運(yùn)行流程

進(jìn)入check_access函數(shù)，格式描述包含數(shù)據(jù)指針、長(zhǎng)度、讀寫類型；

確認(rèn)是否需要觀測(cè)，需要滿足至少一個(gè)寫操作且為普通訪問；

如果判定需要觀測(cè)，加入觀察列表；

延時(shí)一段時(shí)長(zhǎng)，查看是否有訪問、變更數(shù)據(jù)等情況；如果有，則生產(chǎn)數(shù)據(jù)表，并打印數(shù)據(jù)到控制臺(tái)；如果沒有則退出；

在步驟3，如果未發(fā)現(xiàn)合適的觀測(cè)點(diǎn)，則該數(shù)據(jù)運(yùn)行流程退出

3.4 ASSERT檢測(cè)機(jī)制

KCSAN提供有一種斷言檢測(cè)機(jī)制，檢查在數(shù)據(jù)競(jìng)爭(zhēng)模型以外的情況下提供競(jìng)爭(zhēng)檢測(cè)；

3.4.1 ASSERT集合

3.5 KCSAN特點(diǎn)

四、測(cè)試套件

4.1 KUNIT測(cè)試模型

KCSAN提供KUNIT的支持

創(chuàng)建多個(gè)access_thread線程用于測(cè)試用例函數(shù)的調(diào)用接口；

掛接console跟蹤點(diǎn)，該跟蹤點(diǎn)監(jiān)控串口輸出數(shù)據(jù)；如果有數(shù)據(jù)競(jìng)爭(zhēng)報(bào)錯(cuò)，可以捕獲并判斷；

啟動(dòng)測(cè)試用例接口函數(shù)，實(shí)現(xiàn)測(cè)試函數(shù)的掛接并提供超時(shí)判定（缺省執(zhí)行500毫秒）；

在執(zhí)行超時(shí)以后，判斷輸出是否與預(yù)想一致；并給出判斷結(jié)果。

4.2 測(cè)試條件

1. 配置CONFIG_KCSAN_KUNIT_TEST=y使能KUNIT

2. KCSAN功能正常開啟

4.3 測(cè)試環(huán)境

QEMU Linux 6.11 core 4 GCC11

測(cè)試覆蓋：

1. 不同條件下的數(shù)據(jù)競(jìng)爭(zhēng)data_race

2.斷言函數(shù)數(shù)據(jù)競(jìng)爭(zhēng)assert_exclusive_x

3. barrier/lock判定

五、過程與案例分析

5.1 KCSAN啟動(dòng)過程

1. 在完成KCSAN配置后，系統(tǒng)啟動(dòng)時(shí)有“kcsan：enable early”打?。?/p>

2.后臺(tái)會(huì)實(shí)時(shí)進(jìn)行觀測(cè)點(diǎn)的監(jiān)控與比對(duì)，如果比中會(huì)有”BUG：KCSAN”控制臺(tái)打印來描述數(shù)據(jù)競(jìng)爭(zhēng)的信息；這些信息包括調(diào)用函數(shù)、數(shù)據(jù)競(jìng)爭(zhēng)地址、CPU號(hào)、進(jìn)程號(hào)等；可在不同的測(cè)試場(chǎng)景進(jìn)行壓力測(cè)試；

3.在運(yùn)行過程中，查看“KCSAN kernel debug”節(jié)點(diǎn)查看當(dāng)前的狀態(tài)，這些狀態(tài)信息包括觀測(cè)點(diǎn)、數(shù)據(jù)競(jìng)爭(zhēng)、ASSERT報(bào)錯(cuò)等一系列信息；

5.2 案例一

描述：IGMP協(xié)議timer超時(shí)與事件函數(shù)在讀寫mr_ifc_count變量的數(shù)據(jù)競(jìng)爭(zhēng)

net: igmp: fix data-race in igmp_ifc_timer_expire()

解決辦法：

1. igmp_ifc_event/ igmp_ifc_timer_expire函數(shù)在讀寫mr_ifc_count變量存在數(shù)據(jù)競(jìng)爭(zhēng)，需要使用LLKM 訪問保護(hù)；

2. 修改調(diào)用mr_ifc_count點(diǎn),使用READ_ONCE/WRITE_ONCE保證編譯器的一致性;

3. mr_ifc_count和in_dev->mr_ifc_count值不等時(shí)啟動(dòng)重傳機(jī)制；

5.3 案例二

描述：在taskstats_exit()中分配和測(cè)試任務(wù)統(tǒng)計(jì)時(shí)，會(huì)有一個(gè)競(jìng)爭(zhēng)在讀寫sig->stats

When assiging and testing taskstats in taskstats_exit() there's a race when writing and reading sig->stats

解決辦法：

1. 結(jié)構(gòu)體成員sig->stats存在數(shù)據(jù)競(jìng)爭(zhēng)，需要使用LLKM訪問保護(hù)；

2. smp_load_acquire/smp_store_release函數(shù)解決CPU數(shù)據(jù)同步和編譯器同步問題，適用于同一個(gè)函數(shù)內(nèi)部的數(shù)據(jù)競(jìng)爭(zhēng)；

六、總結(jié)

本文從工作原理、運(yùn)行流程、測(cè)試方式等多個(gè)方面介紹了KCSAN，旨在讓讀者能夠?qū)CSAN運(yùn)行有一個(gè)直觀的認(rèn)識(shí)，利用KCSAN在產(chǎn)品中解決一些數(shù)據(jù)競(jìng)爭(zhēng)問題；數(shù)據(jù)競(jìng)爭(zhēng)是一個(gè)復(fù)雜問題，用KCSAN能幫助大家快速找到數(shù)據(jù)競(jìng)爭(zhēng)問題，進(jìn)而尋找方法解決或規(guī)避，本文更多傳遞是一種發(fā)現(xiàn)和解決此類問題的思路。

消殺器技術(shù)在不斷地迭代和更新，也讓大家多一份探尋世界、改變世界的機(jī)會(huì)；借此機(jī)會(huì)，站在巨人的肩膀上，讓大家看得更遠(yuǎn)、走得更遠(yuǎn)，愿大家都有一個(gè)美好的明天。

審核編輯：劉清