一文深入分析-內(nèi)核并發(fā)消殺器（KCSAN）
一、KCSAN介紹
KCSAN(Kernel Concurrency Sanitizer)是一種動(dòng)態(tài)競(jìng)態(tài)檢測(cè)器，它依賴于編譯時(shí)插裝，并使用基于觀察點(diǎn)的采樣方法來(lái)檢測(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，例如通過(guò)提供data_race()標(biāo)記，來(lái)表示存在數(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文件中有非正式的定義。包含以下組成部分：
變量訪問(wèn)(Variable Access)
使用READ_ONCE()、WRITE_ONCE()和ACCESS_ONCE()宏來(lái)保護(hù)從共享(但非原子)變量的加載和存儲(chǔ)；
內(nèi)存屏障(Memory Barriers)
一類同步屏障指令，是CPU或編譯器在對(duì)內(nèi)存隨機(jī)訪問(wèn)的操作中的一個(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原子原語(yǔ) (C11 Atomics)
將原子原語(yǔ)的實(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語(yǔ)言的發(fā)展獨(dú)立于并發(fā)性。如果給定的變量或訪問(wèn)沒(méi)有任何特別之處，則變量只會(huì)在響應(yīng)當(dāng)前線程的存儲(chǔ)時(shí)發(fā)生變化。
C語(yǔ)言和編譯器的進(jìn)化對(duì)并發(fā)性不敏感
優(yōu)化編譯器正變得越來(lái)越豐富
因此，編譯器可以并且使用各種優(yōu)化，包括負(fù)載融合、代碼重新排序和許多其他可能導(dǎo)致并發(fā)算法故障的優(yōu)化。
讀取拆分（單次訪問(wèn)多次讀?。?/p>
存儲(chǔ)拆分（單次訪問(wèn)多次寫入）讀取融合（編譯器直接使用上一次對(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)存一致性模型，也提供檢查方法解決此類問(wèn)題。
1.2.1 訪問(wèn)方式
普通訪問(wèn)
標(biāo)記訪問(wèn)
1.2.2 同步?jīng)_突訪問(wèn)的檢測(cè)條件
在訪問(wèn)同一個(gè)地方并且至少有一個(gè)是寫操作
至少有一個(gè)是普通訪問(wèn)（比如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)記訪問(wèn)。
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個(gè)人覺(jué)得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)?
二、依賴與配置方案
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)核的主要分支，在訪問(wèn)的內(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)存訪問(wèn)設(shè)置觀察點(diǎn)
〇 注釋標(biāo)記訪問(wèn)，僅用于檢查非標(biāo)記訪問(wèn)是否存在觀察點(diǎn)；
KCSAN從不在標(biāo)記的訪問(wèn)上設(shè)置觀察點(diǎn)；
如果對(duì)并發(fā)訪問(wèn)的變量的所有訪問(wèn)都正確地標(biāo)記了，KCSAN將永遠(yuǎn)不會(huì)觸發(fā)觀察點(diǎn)，因此永遠(yuǎn)不會(huì)報(bào)告訪問(wèn)。
●采樣: 周期性建立觀察點(diǎn)
〇默認(rèn)值:平均2000次訪問(wèn)。
3.2 KCSAN軟觀測(cè)點(diǎn)
基于地址頁(yè)索引
〇可以溢出到相鄰槽。
〇使用索引確保報(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è)寫操作且為普通訪問(wèn)；
如果判定需要觀測(cè)，加入觀察列表；
延時(shí)一段時(shí)長(zhǎng)，查看是否有訪問(wèn)、變更數(shù)據(jù)等情況；如果有，則生產(chǎn)數(shù)據(jù)表，并打印數(shù)據(jù)到控制臺(tái)；如果沒(mé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判定
五、過(guò)程與案例分析
5.1 KCSAN啟動(dòng)過(guò)程
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)打印來(lá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)行過(guò)程中，查看“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 訪問(wèn)保護(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訪問(wèn)保護(hù)；
2. smp_load_acquire/smp_store_release函數(shù)解決CPU數(shù)據(jù)同步和編譯器同步問(wèn)題，適用于同一個(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)問(wèn)題；數(shù)據(jù)競(jìng)爭(zhēng)是一個(gè)復(fù)雜問(wèn)題，用KCSAN能幫助大家快速找到數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題，進(jìn)而尋找方法解決或規(guī)避，本文更多傳遞是一種發(fā)現(xiàn)和解決此類問(wèn)題的思路。
原文作者：內(nèi)核工匠
