增加數(shù)據(jù)競爭檢測效率的混合算法

梁帥帥 李蘭英

摘? 要：針對多線程程序同時(shí)讀寫同一塊內(nèi)存產(chǎn)生的數(shù)據(jù)競爭，已有的檢測方法漏檢率和誤檢率較高，文章結(jié)合靜態(tài)RELAY法和動(dòng)態(tài)Eraser鎖集法，利用數(shù)據(jù)流的靜態(tài)法對共同鎖集的判斷和動(dòng)態(tài)法對共同鎖集的保護(hù)，有效地降低誤檢率和漏檢率。為減少因重復(fù)交織出現(xiàn)的冗余，提出使用重復(fù)檢測器減少重復(fù)檢測的數(shù)據(jù)競爭，提升了檢測性能，降低了檢測開銷。

關(guān)鍵詞：數(shù)據(jù)競爭;動(dòng)靜態(tài)檢測;重復(fù)檢測器

中圖分類號：TP311.5? ? ? 文獻(xiàn)標(biāo)識碼：A 文章編號：2096-4706（2020）17-0069-03

Abstract：In view of the data competition generated by multi-threading programs reading and writing the same memory at the same time，the existing detection methods have high miss detection rate and false detection rate. This paper combines the static RELAY method and dynamic ERASER lock set method，uses the static method of data flow to judge the common lock set and the dynamic method to protect the common lock set，so as to effectively reduce the false detection rate and missed detection rate. In order to reduce the redundancy caused by repeated interleaving，the use of duplicate detector to reduce the data competition of repeated detection is proposed，which improves the detection performance and reduces the detection overhead.

Keywords：data race;dynamic and static detection;repetitive detector

0? 引? 言

程序中并發(fā)性bug越來越多，常見的bug有四種類型：死鎖、數(shù)據(jù)競爭、原子性違背和順序違背。數(shù)據(jù)競爭指在非線程安全的情況下，多線程對同一個(gè)地址空間進(jìn)行寫操作，需花費(fèi)大量時(shí)間進(jìn)行調(diào)試和修復(fù)，很多學(xué)者提出了很多檢測方法，靜態(tài)檢測方法主要使用RELAY[1]、Locksmith、RacerX等;本文所述動(dòng)態(tài)檢測主要使用鎖級法、先發(fā)生于算法。

因很難確定程序操作實(shí)際影響到哪些內(nèi)存、被訪問的值是局部范圍還是全局范圍、是否通過參數(shù)傳遞到函數(shù)中，RELAY、Locksmith等方法能調(diào)用上下文敏感分析來確定訪問內(nèi)存的實(shí)際位置，但每個(gè)位置上持有哪些鎖，程序操作獲取和釋放了哪些鎖，這些鎖是否有可能通過參數(shù)傳入的結(jié)構(gòu)派生而來的都無法確定。RELAY、Locksmith等方法在兩個(gè)不同訪問處，鎖持有的鎖集的交集進(jìn)行判斷是否為可疑數(shù)據(jù)競爭。Flanagan等人的先發(fā)生于算法提出更新時(shí)鐘向量，通過時(shí)鐘向量狀態(tài)判斷相關(guān)讀寫訪問信息。

為提升并發(fā)缺陷相關(guān)方向的效率，降低漏檢和誤檢率，加強(qiáng)程序的正確性和可操作性，校內(nèi)相關(guān)國家自然基金課題也對并發(fā)缺陷數(shù)據(jù)競爭進(jìn)一步研究，根據(jù)學(xué)者提出的算法，本人進(jìn)行復(fù)現(xiàn)、改進(jìn)。研究時(shí)基于數(shù)據(jù)流分析和鎖集REALY方法，先進(jìn)行上下文敏感分析，計(jì)算函數(shù)相對鎖集和保護(hù)訪問集，然后判斷相關(guān)鎖集是否有交集，再使用Eraser[2]方法對相關(guān)鎖集進(jìn)行保護(hù)，如果有可疑的數(shù)據(jù)競爭將被進(jìn)行刪除，隨后再根據(jù)檢測過程中檢測出的可疑競爭所在位置的程序段進(jìn)行分步驟重復(fù)檢測，本文動(dòng)靜結(jié)合檢測方法減少了動(dòng)態(tài)檢測的漏檢率和靜態(tài)檢測的誤檢率，并解決了一些數(shù)據(jù)競爭重復(fù)檢測的問題。在檢測并發(fā)缺陷后，使用重復(fù)檢測器再一次進(jìn)行篩選，時(shí)間、空間開銷會(huì)有所減少。

1? FPX的算法描述

首先靜態(tài)RELAY法對符號執(zhí)行的局部和全局傳入值跟蹤內(nèi)存位置中包含的值，使用元變量x∈X表示局部和全局，符號值的集合V表示符號分析計(jì)算的值，整數(shù)init（x）是x的局部值;must（x）表示一個(gè)必須指向x的值;may（x）表示一個(gè)可能指向x中的任何左值。符號執(zhí)行跟蹤每個(gè)程序點(diǎn)上的符號映射，并使用函數(shù)更新這個(gè)符號映射。簡單賦值x：= e的函數(shù)，將當(dāng)前映射中的e計(jì)算為一個(gè)符號值，然后更新映射中的x。對于通過指針進(jìn)行的賦值，也就是?x：=e，函數(shù)將x計(jì)算為一個(gè)符號值v1，將e計(jì)算為一個(gè)符號值v2，存儲(chǔ)中更新哪些x取決于值v1。

鎖集的結(jié)果存儲(chǔ)為XLock（f）∈L，表示函數(shù)末尾的相對鎖集。將鎖和解鎖操作為鎖集函數(shù)調(diào)用，修改鎖集函數(shù)調(diào)用e（a）。lock（l）函數(shù)為（{l}，{ }）的相對鎖集摘要，unlock（l）函數(shù)為（{ }，{l}）的相對鎖集摘要，相對鎖集產(chǎn)生的摘要表從開始執(zhí)行到返回的鎖集中的變化。查找調(diào)用f后的相對鎖集，將更新后的鎖集信息傳入的相對鎖集[3]。鎖集分析完成對給定函數(shù)的所有程序點(diǎn)的相對鎖集的計(jì)算，保護(hù)訪問使用這些信息來計(jì)算函數(shù)執(zhí)行的保護(hù)訪問集合。保護(hù)訪問集合是一個(gè)triple a=（x，L，k），x值被訪問，l∈L是當(dāng)前鎖的訪問，k代表鎖的類型即讀鎖或?qū)戞i;訪問設(shè)置更新（s，L）。

當(dāng)處理完函數(shù)中的所有語句后，最后的保護(hù)訪問集將成為函數(shù)的訪問摘要。最終能計(jì)算出該線程的入口函數(shù)的保護(hù)訪問集，對于共享變量v的來自不同線程T1和T2的2個(gè)保護(hù)訪問（o，，k）和（o′，，k′），其中，o是左值被訪問，L+是進(jìn)程所獲取的鎖的集合，L-是進(jìn)程所釋放的鎖的集合。獲取保護(hù)它們的鎖集的交集，如果交集為空，則這2個(gè)訪問就構(gòu)成一個(gè)可疑的數(shù)據(jù)競爭。使用靜態(tài)檢測的數(shù)據(jù)競爭誤檢率高，所以使用動(dòng)態(tài)檢測降低誤檢率，如下述使用Eraser鎖集算法動(dòng)態(tài)檢測在靜態(tài)檢測鎖集和保護(hù)訪問集結(jié)果的基礎(chǔ)上對共享變量的保護(hù)訪問應(yīng)受到共同鎖集的保護(hù)，并不斷更新鎖集向量時(shí)鐘[4]的信息，通過線程調(diào)度發(fā)現(xiàn)真實(shí)數(shù)據(jù)競爭，然后剔除數(shù)據(jù)競爭，從而降低誤檢率。

Eraser lockset algorithm

Input：thread t's lock set and sharevarable v's candidate lock set

Output：null or a race warning

Let Lt be the set of locks held by thread t;

For each shared variable v，CL（v） stands v's candidate locks

namely the set of locks consistently protecting v.Initially， CL（v） is set to be all locks;

Let prev be the previous access to v before the current access to v.Initially，prev is nil;

Let mode（x）be a map from access x to its type，namely READ or WRITE;

foreach access a to v by thread t do

CL（v）←CL（v）∩Lt;

if CL（v）=0&&！（mode（a）=READ&&mode

（prev）=READ） then

return a race warning（v，prev，a）;

return;

算法檢測后有大量的數(shù)據(jù)競爭重復(fù)檢測，在上述動(dòng)靜態(tài)檢測后加一個(gè)檢測器，來過濾重復(fù)檢測，描述如下：檢測器由多個(gè)步驟組成，最重要的步驟是預(yù)測步驟和驗(yàn)證步驟。預(yù)測步驟檢查動(dòng)態(tài)的執(zhí)行，基于動(dòng)態(tài)檢測模式預(yù)測潛在的重復(fù)數(shù)據(jù)競爭;驗(yàn)證步驟主動(dòng)控制線程調(diào)度[5]，驗(yàn)證許多重新執(zhí)行中的數(shù)據(jù)競爭。第一步可能會(huì)產(chǎn)生許多重復(fù)的數(shù)據(jù)競爭，給第二步帶來許多重復(fù)的新執(zhí)行，這將影響并發(fā)性數(shù)據(jù)競爭檢測的效率。在第一步中預(yù)測潛在的競爭（兩個(gè)數(shù)據(jù)競爭），如果S1->S3->S2之間的潛在競爭已經(jīng)被檢測，則無需再次檢測S1->S3和S3->S2之間的其他兩個(gè)潛在競爭。比如S1-> S3->S2的實(shí)例iS1->iS3->iS2表示兩個(gè)線程之間的三個(gè)內(nèi)存訪問事件，S1->S3的實(shí)例iS1->iS3表示兩個(gè)線程之間的兩個(gè)內(nèi)存訪問事件，而實(shí)例iS1->iS3無需檢測，因?yàn)榱硪籭S1->iS3->iS2已經(jīng)包含了這個(gè)實(shí)例。如果S1->S3和S3-> S2在檢測時(shí)沒有進(jìn)行重復(fù)檢測，那么效率會(huì)得到明顯提高。檢測器算法描述如下：

Dynamic detector after Eraser detect Event 1、Event 2、Event 3.

Let detect the set of lock by FPX

For search Datarace in the set lock and detect repeat

If search （Event 1—>Event 3）∩（Event 1—>Event 2—> Event 3） = Event 1—> Event 3

Return Event 1—>Event 2—>Event 3

Break repeat lock

Elseif Event 2—>Event 3∩（Event 1—> Event 2—>Event 3） = Event 2—> Event 3

Return Event 1—>Event 2—>Event 3

Break repeat lock

Return Event 1—>Event 2—>Event 3

2? 實(shí)驗(yàn)結(jié)果分析

RELAY算法能檢測數(shù)據(jù)競爭，誤檢率高，但相對于一般檢測方法漏檢率低，檢測出程序中的數(shù)據(jù)競爭即報(bào)錯(cuò)。針對誤檢問題動(dòng)態(tài)使用Eraser鎖集算法，因?qū)︽i集的時(shí)鐘向量信息不斷更新，最終獲取時(shí)鐘信息判斷數(shù)據(jù)競爭，因此誤檢率較低。

對相關(guān)論文重新實(shí)現(xiàn)了這些檢測工具和算法。對比實(shí)驗(yàn)在同一環(huán)境下進(jìn)行，保證了實(shí)驗(yàn)結(jié)果具有可比性。對FPX、RaceChecker和RaceFuzzer進(jìn)行驗(yàn)證，結(jié)果如表1所示，其中前三列表示檢測工具RaceChecker、FPX、RaceFuzzer檢測出的數(shù)據(jù)競爭對數(shù)目，RC、FPX、RF表示RC和FPX、RaceFuzzer檢測過程中的潛在可疑的數(shù)據(jù)競爭對數(shù)。為評測和對比分析FPX對目標(biāo)程序的性能影響，在fft、lu、radix等程序上分別運(yùn)行來檢測驗(yàn)證RaceFuzzer[6]、RaceChecker和FPX。

表2是在動(dòng)靜態(tài)檢測方法檢測前的重復(fù)數(shù)據(jù)競爭數(shù)量和使用重復(fù)數(shù)據(jù)競爭檢測器檢測后的數(shù)據(jù)競爭數(shù)量對比表，其中檢測工具檢測程序5 000行左右，在檢測器下，檢測重復(fù)數(shù)據(jù)競爭前和檢測重復(fù)數(shù)據(jù)競爭后的數(shù)據(jù)對比。

為了更能清晰地看出重復(fù)檢測器檢測效率的提升，如圖1所示，沒有檢測前的數(shù)據(jù)競爭數(shù)量和使用重復(fù)檢測器后的數(shù)據(jù)競爭的數(shù)量效率對比，在多種檢測方法下，針對三種不同的檢測器重復(fù)檢測出的數(shù)據(jù)競爭數(shù)目有所減少，開銷效率提升4%，但還存在一些問題有待繼續(xù)研究，例如檢測器檢測的數(shù)據(jù)競爭，在必要條件非常高的時(shí)候，有檢測器的開銷是否比沒有檢測器的開銷還要大。