數據範圍化的動態數據競爭檢測的製作方法
2023-05-10 09:21:16 2
專利名稱：數據範圍化的動態數據競爭檢測的製作方法
技術領域：
本發明涉及計算機領域，尤其涉及數據競爭檢測技術。
背景技術：
對共享存儲器的多處理器的並發編程可包括多個線程訪問相同數據的能力。該多個線程在多個處理器上、多個邏輯處理器核上、或附連到處理器之間所共享的存儲器的其他並行性類別上執行。共享存儲器模型是多線程通信的最通常部署的方法。在這些系統中， 並發線程可嘗試訪問以及修改共享存儲器中的相同數據。這可導致數據競爭條件，該數據競爭條件可在並發編程和所存儲的數據中造成其他不合需要的或潛在的有害影響。當至少兩個並發線程訪問相同存儲器位置而沒有同步時，數據競爭在多線程的程序中發生，其中訪問中的至少一個是寫操作。數據競爭指示編程出錯，由於多線程編程的非確定性特徵而可能難以隔離該編程出錯。對線程的調度是時序敏感的，並且甚至在用相同輸入來重複執行並發程序時也難以再現數據競爭。使得事情更困難的是，數據競爭常常導致共享數據結構中的存儲器被破壞但不導致直接的程序失敗，並且由數據競爭導致的漏洞可能直到並發程序的稍後所執行的部分作為代碼的不相關部分中的神秘失敗才表明。研究者已嘗試開發用於檢測並發程序中的數據競爭的自動化工具。靜態數據競爭檢測技術一般通過推論所有執行路徑上的數據競爭來提供並發程序的全面覆蓋。然而，靜態技術往往對假設過渡估計，這可導致大量被錯誤檢測的競爭。動態數據競爭檢測技術比靜態技術更精確，但其覆蓋限於執行路徑並且在運行時期間交錯發生。然而，在特定非託管程序中，動態技術常常招致使性能開銷衰減多達兩百倍的減緩。大量性能開銷實際上阻止了對動態數據競爭檢測器的大規模採用。
發明內容
提供本發明內容是為了以簡化的形式介紹將在以下具體實施方式
中進一步描述的一些概念。本發明內容並不旨在標識出所要求保護的主題的關鍵特徵或必要特徵，也不旨在用於限定所要求保護的主題的範圍。公開了帶有減小運行時開銷的數據範圍化能力的動態共享存儲器數據競爭檢測工具。該工具允許用戶使用對庫中所提供的作為競爭檢測工具的一部分的函數的顯式調用來將對存儲器位置的分析限制於其感興趣的堆和/或棧變量。操縱應用程式代碼來在所有存儲器指令處插入探測，並且與數據競爭檢測庫連結以執行數據範圍化的競爭檢測。本發明涉及數據範圍化的動態數據競爭檢測器，該檢測器可測試定義的共享存儲器位置子集上的數據競爭。與數據競爭檢測器一起使用的數據檢測方法包括定義開發者選擇的目標存儲器位置，在該目標存儲器位置啟動數據競爭檢測器，以及監視對該目標存儲器位置內的應用程式的存儲器訪問以供數據競爭。數據競爭檢測器應用一算法來監視該目標存儲器位置，並在常見鎖或同步沒有保護該目標存儲器位置內的並發訪問的情況下發出競爭條件警告。在一個示例中，數據競爭檢測器包括執行組件以及庫組件。執行組件啟動應用程式連同數據競爭檢測器。庫組件實現數據競爭檢測引擎，並提供應用程式接口用於定義目標存儲器位置和其他功能。該方法僅監視對所定義的目標存儲器位置中的應用程式的存儲器訪問，因此減小了開銷。開發者可定義該目標存儲器位置以覆蓋其中數據競爭被懷疑的區域。同樣，該方法可使用更廣泛定義的目標存儲器位置集合來重複、或對所定義的目標存儲器位置的另一集合重複，直到開發者對所實現的數據競爭漏洞覆蓋量滿意。
包括、合併在本發明書內並構成其一部分的附圖提供了對各實施例的進一步理解。附圖示出各實施例，並且與說明書一起用於解釋本發明的原理。其他實施例和各實施例的許多預期優點將隨著參考下面的詳細描述進行更好的理解而得到認識。附圖的元素不一定相對於彼此是比例正確的。相同的附圖標記指代對應的類似部分。圖1是示出示例計算設備的框圖。圖2是示出圖1的計算設備的多核處理系統的示例的示意圖。圖3是示出動態地檢測在圖2的系統上所執行的多線程應用程式中發生的數據競爭的示例方法的框圖。圖4是示出適於實現圖3的方法的示例數據競爭檢測器的框圖。
具體實施例方式在以下詳細描述中，對附圖進行了參考，附圖構成了實施例的一部分且在其中作為示例示出了可在其中實踐本發明的各特定實施例。可以理解，可以使用其它實施例並且可以做出結構上或邏輯上的改變而不背離本發明的範圍。因此，以下詳細描述並不旨在限制，並且本發明的範圍由所附權利要求來限定。應理解，此處描述的各示例性實施例的特徵可相互組合，除非另外具體註明。圖1示出了可用作操作環境並且包括諸如計算設備100之類的計算設備的示例性計算機系統。在一基本配置中，計算設備100通常包括具有至少兩個處理單元(即，處理器 102)的處理器體系結構以及存儲器104。取決於計算設備的確切配置和類型，存儲器104可以是易失性的(如隨機存取存儲器(RAM))、非易失性的(諸如只讀存儲器(ROM)、快閃記憶體等) 或兩者的某種組合。該計算設備可採取若干形式中的一種或多種。這些形式包括個人計算機、伺服器、手持式設備、消費電子產品能(諸如視頻遊戲控制臺)或其他設備。計算設備100還可具有附加特徵或功能。例如，計算設備100還可包括附加存儲 (可移動和/或不可移動)，包括但不限於磁碟或光碟或固態存儲器，或者閃速存儲設備， 諸如可移動存儲108和不可移動存儲110。計算機存儲介質包括以用於存儲諸如計算機可讀指令、數據結構、程序模塊或其他數據等的任何合適的方法或技術實現的易失性和非易失性、可移動和不可移動介質。存儲器104、可移動存儲108和不可移動存儲110都是計算機存儲介質的示例。計算機存儲介質包括，但不限於，RAM、R0M、EEPR0M、快閃記憶體或其它存儲器技術、CD-ROM、數字多功能盤(DVD)或其它光碟存儲、磁帶盒、磁帶、磁碟存儲或其它磁性存儲設備、通用串行總線(USB)快閃記憶體驅動器、快閃記憶體卡、或能用於存儲所需信息且可以由計算設備100訪問的任何其它介質。任何這樣的計算機存儲介質都可以是計算設備100的一部分。
計算設備100包括允許計算設備100諸如經由計算機網絡與其它計算機/應用程式115通信的一個或多個通信連接114。計算設備100還可包括諸如鍵盤、定點設備(例如，滑鼠)、筆、語音輸入設備、觸摸輸入設備等的輸入設備112。計算設備100還可包括諸如顯示器、揚聲器、印表機等的輸出設備111。計算設備100可被配置成運行作業系統軟體程序以及一個或多個軟體應用程式， 這些構成系統平臺。在一個示例中，計算設備100包括被稱為託管的或運行時環境的軟體組件。託管環境可被包括為作業系統的一部分或者可在稍後被包括為軟體下載。託管環境通常包括針對常見編程問題的預先編碼的解決方案以幫助軟體開發者創建諸如應用程式等在託管環境中運行的軟體程序。另外，計算設備可被配置成運行非託管代碼，諸如以諸如特定形式的Basic、C++以及其他的非託管語言建立的應用程式。一般而言，存儲器104被組織成包括代碼段、棧段以及堆段的供示出的三個段。代碼段被配置成存儲經編譯的電腦程式的代碼，它一般包括用戶定義的函數以及系統函數。棧是存儲供與電腦程式一起使用的數據的存儲器段。棧存儲為函數內的自動變量分配的數據。數據以後進先出(LIFO)方法被存儲在該棧中。堆也是存儲供與電腦程式一起使用的數據的存儲器段，但被用於動態存儲器分配。存儲器段的塊按任意次序來分配和釋放，並且分配的模式以及塊的大小直到運行時才知道。棧包括在運行時之前被聲明並初始化的變量所存儲的地方，而堆包括在運行時創建或初始化的變量所存儲的地方。數據競爭條件在並發線程嘗試訪問棧和堆中的變量時發生。被配置成在計算設備100上執行的計算機應用程式包括至少一個過程(或任務)， 該至少一個過程(或任務)是執行程序。每一過程提供用於執行該程序的資源。一個或多個線程在該過程的上下文中運行。線程是作業系統在處理器102中向其分配時間的基本單元。線程是為執行而調度的過程內的實體。過程的各線程可共享其虛擬地址空間和系統資源。每一線程可包括異常處理程序、調度優先級、線程位置存儲、唯一線程標識符、以及直到該線程被調度的線程上下文(或線程狀態)。線程上下文包括線程的機器寄存器集、內核棧、線程環境塊、以及與該線程對應的過程的地址空間中的用戶棧。在並行應用程式中，可在處理器102上並發地執行各線程。圖2是可在計算設備100中被實現為用於並發執行各線程的處理器102的示例多核處理器200。這一示例包括在單個管芯202上實現的多核。構想了其中處理器102存在於分開的晶片上或甚至存在於分開的計算機系統上等的其他示例。圖2的示例包括四個物理處理器核204、206、208、210，或僅僅是四個物理核，其中這些物理核中的每一個可用於處理至少一個應用程式線程，而至少一個其他物理核並發地處理另一線程。如圖所示，物理核 204、206、208、210與管芯202上的存儲器控制器212和高速緩存214相鄰。高速緩存的一個示例可包括共享的三級高速緩存。在管芯202的示例中，隊列216被設置在管芯上的存儲器控制器212與高速緩存214之間。所示配置表示包括當前在「Nehalem」的指定下可用的處理器的晶片，該「Nehalem」可從加利福尼亞州聖克拉拉的英特爾(Intel)公司獲得。管芯202可包括其他特徵218或諸如存儲器接口、雜項輸入/輸出塊、專有互連、擴展卡接口之類的特徵的組合。在該示例中，每一物理核能夠有效地且並發地執行並發過程的多個線程。這些物理核常常被稱為「同時多線程化」或常常簡稱為「SMT」核，並且在單個物理核上並發執行的線程與單個物理核共享所包括的硬體資源。在多核處理系統200的示例中，每一物理核能夠進行多線程化。多線程化技術旨在通過線程級和指令級並行化來增加核效率。能夠進行多線程化之類的每一物理核可向作業系統呈現與並發執行的線程一樣多的邏輯核。在多核處理系統200的示例中，每一物理核204、206、208、210能夠並發執行兩個線程，並由此向作業系統提供八個並發邏輯核。計算設備100理論上可執行與設備100中有的邏輯核一樣多的並發線程。在作業系統的示例中，在來自華盛頓州雷德蒙市微軟的「Windows 7」指定下可用的作業系統在單個計算設備100上支持超過六十四個邏輯核。動態數據競爭檢測是並發應用程式的開發者所使用的技術，該技術檢測在並發應用程式的一個執行中對共享存儲器位置的無序的衝突訪問。動態數據競爭檢測器是被設計成與執行目標應用程式一起運行以便測試目標應用程式中對共享變量的多線程的並發訪問的工具或引擎。動態數據競爭檢測常常在工業應用程式的測試版測試期間執行。動態數據競爭檢測器在傳統上被分類為發生之前(happens-before)檢測器和基於鎖具(lockset-based)的檢測器，並且各自具有與另一個相比的優點和缺點。基於鎖具的檢測器是有效的，但它們可報告假肯定，即在不存在數據競爭時錯誤地報告，而發生之前檢測器不報告假肯定。發生之前檢測器更通用並可應用於非基於鎖的同步形式的應用程式，但與基於鎖具的檢測器相比，發生之前檢測器實現起來較低效並更可能遭受假否定，即當存在數據競爭時不能報告。混合動態競爭檢測器被設計成結合每類檢測器的優點同時減小負面影響。儘管這樣的混合數據競爭檢測器包括數據競爭檢測和運行時開銷的改進，但數據競爭檢測器中的大量運行時開銷仍然是研究者的顧慮。一般地，在動態數據競爭檢測器中存在至少兩個主開銷源。首先，檢測器操縱存儲器操作以及由目標應用程式執行的同步操作。由此，高性能成本由運行時執行的數量增長的額外指令產生。第二，檢測器還維護由目標應用程式訪問的供與檢測算法一起使用的每一存儲器位置的元數據。維護這一元數據招致額外的存儲器成本，從而進一步增加開銷。例如，在發生之前檢測算法中的存儲器消耗可為大小為η的數組使用8η字節。動態數據競爭檢測器的設計者嘗試通過減小覆蓋來減小運行時開銷。一種動態數據競爭檢測技術通過僅對目標應用程式的執行期間所選擇的存儲器訪問進行採樣和分析來減小開銷。各採樣技術一般難以捕捉數據競爭，因為大多數存儲器訪問不導致數據競爭，而一種採樣技術嘗試捕捉多個訪問以便檢測數據競爭。為解決對兩個數據競爭訪問的採樣的降低的概率，研究者創建新的且更複雜的檢測算法。例如，研究者開發了冷區域 (cold-region)假設數據競爭可能發生在程序的不頻繁訪問的區域。該假設假定測試好的應用程式的熱區域中的數據競爭已經被找到且是固定的或者可能是良性的。對檢測算法中的函數的採樣速率通過該函數被執行得多頻繁來確定，並且該函數被執行得越頻繁，則越少的訪問被採樣。圖3示出了本發明的數據範圍化的動態數據競爭檢測技術的示例方法300，該技術可測試定義的共享存儲器位置子集上的數據競爭。該方法包括在302處定義開發者選擇的目標存儲器位置，在方法300的一個示例中在304處啟動數據競爭檢測器，以及在306處監視對目標存儲器位置內的應用程式的存儲器訪問用於數據競爭。該方法300僅監視對定義的位置中的應用程式的存儲器訪問，而不是採樣對存儲器中所有位置的訪問。該方法可使用更廣泛定義的目標存儲器位置集合來重複、或對所定義的目標存儲器位置的另一集合重複，直到開發者對所實現的數據競爭漏洞覆蓋量滿意。數據競爭檢測的方法300包括與基於採樣的數據競爭檢測相比的若干優點，此處列出三個優點。第一，方法300給予程式設計師用於聚焦於感興趣的特定存儲器位置的更多控制，而基於採樣的檢測與程式設計師的交互有限。第二，方法300可基於程式設計師的知識或估計來提供對「可疑」存儲器區域的覆蓋，而基於採樣的檢測對全部代碼區域只有部分覆蓋，這可能相應地忽視某些數據競爭。第三，方法300允許程式設計師增量式地擴展覆蓋，而基於採樣的檢測傾向於在不同的運行重複相同的覆蓋。方法300可被實現成要在計算設備100上運行的工具。在一個示例中，該工具是軟體程序或軟體包的一部分。該軟體程序可被包括在計算機可讀存儲介質中，該計算機可讀存儲介質存儲用於控制計算設備(諸如計算設備100)以執行方法300的計算機可執行代碼。在一個示例中，該工具可以是集成開發環境或IDE的一部分。IDE可包括代碼編輯器、編譯器、構建工具、調試器、以及用於開發和測試應用程式的其他工具。IDE的示例可在來自微軟的「VisualStudio」的交易指定下獲得。軟體程序還可以是可與一個或多個IDE 包一起使用的分開的產品、或被用作獨立的產品。圖4示出可用於實現方法300的示例數據競爭檢測器400。在一個示例中，數據競爭檢測器400包括執行組件402以及庫組件404。可被簡稱為DataRaceDetector. exe(數據競爭檢測器.exe)的執行組件402啟動數據競爭檢測器400。可被簡稱為 DataRaceDetector. dll (數據競爭檢測器.dll)的庫組件404實現數據競爭檢測引擎406， 並提供應用程式接口(API)用於定義目標存儲器位置和其他函數。庫組件404提供API，該API允許開發者提供輸入408來將目標存儲器位置410 定義成存儲器104的堆或棧407內的位置子集並可實現方法300的302。目標存儲器位置 410可以用另一個所接收到的輸入408來重新定義，以便添加或移除目標存儲器位置、或改變以定義一組新的目標存儲器位置。如果目標存儲器位置410在堆上，則庫函數(或用於操縱所選擇的函數的專用庫) 使用庫組件404來調用。例如，C語言的庫函數，諸如malloc或相關函數calloc或realloc 可用於定義目標存儲器位置410。C語言中的malloc函數可用於分配固定大小的存儲器， calloc函數分配並初始化該存儲器，以及realloc函數允許調整所分配的存儲器的大小。在檢測器400在該堆上分配目標存儲器位置的特定示例中，顯示函數調用存儲器中所存儲的數據競爭檢測庫中的分配函數。分別調用函數調用DRD_mall0C、DRD_ calloc 以及 DRD_realloc而非 C 庫函數 malloc 、calloc 或 realloc ，以指定在運行時將由檢測器400來監視的所分配的目標存儲器位置410。數據競爭檢測庫中的函數具有與其對應的C庫函數相同或通常與其類似的類型的籤名。另外，所分配的目標存儲器位置410可通過_DRD_free 來釋放，該_DRD_free 還可包括與C庫函數free 相同或相似類型的籤名。在一個示例中，堆分配可被截取並定向到數據競爭檢測庫以供其對應的函數。數據競爭檢測庫總是檢查從其堆中所分配的存儲器位置中的錯誤。這也允許對是否應為數據競爭而跟蹤存儲器位置的有效查找。如果該目標是該棧上所分配的局部變量，則函數_DRD_ target variable， saddress (變量地址)>，〈variable， s size (變量大小)>)被顯式地插在變量聲明之後，以指定帶有給定地址的變量是該目標。在退出函數調用時，可通過調用_DRD_cIeanTarget variable' s address〉，〈variable，s size 從競爭檢測列表中移除該棧上的目標。目標位置被記錄在存儲器中所創建的地址查找表中，並且目標變量通過運行時系統被分配在該棧上。作為說明，以下示例將連結的列表的頭節點以及長度列表的長度定義為目標
在這一示例中，直到達到_DRD_target的調用之後才開始對局部變量的檢測。數據檢測器400可通過執行基於目標應用程式414的原始二進位代碼來修改或重寫的應用程式二進位代碼412來啟動，並且可用於實現方法300的304。執行組件402通過在存儲器訪問操作處插入探測函數以及通過將同步操作繞道至可執行的重寫的應用程式二進位代碼412來修改原始二進位代碼414。在一個示例中，探測函數被插入每一存儲器訪問操作處，並且每一同步操作被繞道。執行組件402隨後啟動重寫的應用程式二進位代碼 412。表1示出如何重寫原始應用程式二進位代碼的示例。表權利要求
1.一種檢測應用程式中的數據競爭的方法，所述方法包括使用至少一個處理器基於接收到存儲器的輸入來定義所選擇的目標存儲器位置；以及使用所述至少一個處理器來監視對所選擇的目標存儲器位置內的所述應用程式的存儲器訪問用於數據競爭。
2.如權利要求1所述的方法，其特徵在於，所選擇的目標存儲器位置被包括在所述存儲器的堆或棧的其中一個上。
3.如權利要求1所述的方法，其特徵在於，定義所選擇的目標存儲器位置包括截取堆分配並將所截取的堆分配定向到所述存儲器中的存儲器選擇機制。
4.如權利要求1所述的方法，其特徵在於，堆上所選擇的目標存儲器位置使用與包括 malloc, calloc和realloc的標準堆分配例程對應的數據競爭檢測庫函數來分配。
5.如權利要求1所述的方法，其特徵在於，棧上所選擇的目標存儲器位置使用具有作為變量的目標位置的數據競爭檢測庫函數來分配。
6.如權利要求5所述的方法，其特徵在於，棧上所選擇的目標存儲器位置的地址被記錄在所述存儲器中所存儲的表中。
7.如權利要求1所述的方法，其特徵在於，還包括用所述處理器來執行所述應用程式的應用程式二進位代碼。
8.如權利要求1所述的方法，其特徵在於，對於更廣泛定義的目標存儲器位置集合重複所述方法。
9.如權利要求1所述的方法，其特徵在於，監視存儲器訪問包括如果常見鎖或同步沒有保護所選擇的目標存儲器位置內的並發訪問，則發出警告。
10.如權利要求1所述的方法，其特徵在於，監視存儲器訪問包括使用所述至少一個處理器來將數據競爭檢測算法應用於所述應用程式二進位代碼。
11.一種存儲用於控制計算設備以便使用目標應用程式來執行一種方法的計算機可執行指令的計算機可讀存儲介質，所述方法包括基於所接收的輸入來定義所選擇的目標存儲器位置；啟動所述目標應用程式；以及監視對所選擇的目標存儲器位置內所述目標應用程式的存儲器訪問用於數據競爭。
12.如權利要求11所述的計算機可讀存儲介質，其特徵在於，包括用於接收被用於定義所選擇的目標存儲器位置的輸入的應用程式接口。
13.如權利要求12所述的計算機可讀存儲介質，其特徵在於，所述應用程式接口被包括在所述計算機可執行指令的庫組件中。
14.如權利要求11所述的計算機可讀存儲介質，其特徵在於，所選擇的目標存儲器位置包括所述目標應用程式能訪問的棧或堆的存儲器位置子集。
15.如權利要求11所述的計算機可讀存儲介質，其特徵在於，定義所選擇的目標存儲器位置包括基於所述目標存儲器位置是否被分配在所述堆或棧上來訪問數據競爭檢測庫函數。
16.如權利要求15所述的計算機可讀存儲介質，其特徵在於，所述數據競爭檢測庫包括與包括malloc、calloc和realloc的標準堆分配例程對應的至少一個庫函數，並且棧上所選擇的目標存儲器位置使用具有作為變量的目標位置的數據競爭檢測庫函數來分配。
17.如權利要求16所述的計算機可讀存儲介質，其特徵在於，對所述目標應用程式的啟動使用包括在所述計算機可執行指令的執行組件內的數據競爭檢測器來執行。
18.如權利要求11所述的計算機可讀存儲介質，其特徵在於，監視存儲器訪問包括如果常見鎖或同步沒有保護所選擇的目標存儲器位置內的並發訪問，則發出警告。
19.一種存儲開發工具的包括計算機可執行指令的計算機可讀存儲介質，所述指令用於控制具有被配置成使用並發線程來執行所選擇的目標應用程式的多個邏輯核的計算設備，所述開發工具被配置成執行一種方法，所述方法包括使用數據競爭檢測庫函數基於所接收的輸入來定義所選擇的目標存儲器位置；其中，堆上所選擇的目標存儲器位置使用與包括malloc、calloc和realloc的標準堆分配例程對應的數據競爭檢測庫函數來分配；其中，棧上所選擇的目標存儲器位置使用具有作為變量的目標位置的數據競爭檢測庫函數來分配；使用執行組件基於目標應用程式的二進位程序來啟動重寫的二進位程序；以及監視對所選擇的目標存儲器位置內的二進位應用程式的存儲器訪問用於數據競爭，並且對沒有用同步來保護的每一併發存儲器訪問發出警告。
20.如權利要求19所述的計算機可讀存儲器，其特徵在於，還包括重新定義所選擇的目標存儲器位置，以及重複對所述二進位應用程式的存儲器訪問的監視。
全文摘要
本發明描述了數據範圍化的動態數據競爭檢測。公開了帶有減小運行時開銷的數據範圍化能力的動態共享存儲器數據競爭檢測工具。該工具允許用戶使用對庫中所提供的作為競爭檢測工具的一部分的函數的顯式調用來將對存儲器位置的分析限制於其感興趣的堆和/或棧變量。操縱應用程式代碼來在所有存儲器指令處插入探測，並且與數據競爭檢測庫連結以執行數據範圍化的競爭檢測。
文檔編號G06F11/36GK102314394SQ20111019078
公開日2012年1月11日 申請日期2011年6月27日 優先權日2010年6月25日
發明者H·沙菲, K·S·賽德奇, Y·張 申請人:微軟公司