最近看了一篇 Paper - Watching for Software Inefficiencies with Witch媚送，覺得作者排查性能問題的思路很不錯匾旭，這里記錄一下。
什么是無效處理
對于性能調(diào)優(yōu)來說尽棕，我們會關(guān)注很多指標(biāo)答憔，這里味赃，WITCH 主要關(guān)注的是系統(tǒng)的 infficiencies，也就是無效的處理虐拓。通常的無效處理可能包括：
- 計算了一個不會被使用的結(jié)果
- 重復(fù)計算了某一個結(jié)果
- 無效的數(shù)據(jù)移動
- 過分的同步
大家都知道心俗，無效處理會對系統(tǒng)性能造成影響，我們需要盡量避免蓉驹。雖然現(xiàn)在編譯器在很多時候都能對代碼做很多優(yōu)化城榛，但僅僅靠編譯器是不夠的，我們還需要其他的方法來檢查發(fā)現(xiàn)系統(tǒng)無效處理的地方态兴。
WITCH 的設(shè)計與實現(xiàn)
要排查系統(tǒng)性能問題狠持，對我來說，最先想到的就是使用 perf 這類型的工具瞻润，但無論是 perf 還是 vtune喘垂，它們都是基于采樣的，是一種 Coarse-grained profiler绍撞，雖然對系統(tǒng)影響較小正勒，但并不精確，在一些情況下面其實并不能很好的發(fā)現(xiàn)無效處理傻铣。
另一種就是 Fine-grained profiler章贞，譬如 DeadSpy，它們會詳細(xì)的分析動態(tài)指令非洲，從而發(fā)現(xiàn)無效處理阱驾，但也會給系統(tǒng)造成非常大的負(fù)擔(dān)就谜，是的系統(tǒng)性能下降。
而對于 WITCH 來說里覆，它融合了 Coarse-grained 和 Find-grained，核心想法就是先用 PUMs 對系統(tǒng)進(jìn)行采樣缆瓣，然后使用 hardware debug registers 來給采樣的地址加上斷點喧枷，當(dāng)后續(xù)系統(tǒng)訪問到這些地址的時候，觸發(fā)對應(yīng)的判斷程序弓坞，看是否是無效處理隧甚。
WITCH 的原理非常簡單，但要做好渡冻，其實還需要處理很多問題戚扳。在繼續(xù)開始之前，我們可以先簡單介紹一下系統(tǒng)調(diào)優(yōu)里面一些背景知識族吻。
常用術(shù)語
-
Hardware Performance Monitoring Units
也就是通常說的 PMU∶苯瑁現(xiàn)代的 CPU 都會提供很多硬件事件的計數(shù)器，譬如 loads超歌，stores砍艾，CPU cycles 等。當(dāng)計數(shù)器的值超過了一個閾值之后巍举，PMU 就會觸發(fā)一個溢出中斷脆荷，這個中斷就會被 profiler（譬如 perf）給捕捉到并且處理。
-
Hardware Debug Registers
Hardware debug registers 其實就可以認(rèn)為是我們在用 gdb 調(diào)試的時候設(shè)置的斷點懊悯。當(dāng)程序的 Program counter (PC) 運行到某一個地址或者是一條指令訪問到了一個特定的地址蜓谋，hardware debug registers 就會捕獲 CPU 的執(zhí)行。在現(xiàn)代的 x86 架構(gòu)中炭分，通常有 4 個 debug registers桃焕。
-
Linux Perf events_
Linux 提供了一套標(biāo)準(zhǔn)的接口用來對 PMU 進(jìn)行采用和編程，主要使用的是
perf_event_open和相關(guān)的ioctl調(diào)用欠窒。當(dāng) PMU 的事件溢出之后覆旭，Linux 內(nèi)核會給相關(guān)的線程發(fā)送信號，并且將取樣的 PMU 數(shù)據(jù)追加到一個循環(huán) buffer 里面岖妄。 -
Call Path Profiling
當(dāng)對應(yīng)事件觸發(fā)的時候型将，我們能通過 Call path profiling 拿到當(dāng)前的 calling context，也就是整個事件的調(diào)用鏈荐虐。一個 calling context 從入口函數(shù)（譬如 main 或者線程開始函數(shù)）的 instruction pointer (IP) 開始七兜，然后到觸發(fā)這個事件的指令這里結(jié)束。
-
Watchpoint
Watchpoint 就是類似于 gdb 里面的斷點設(shè)置福扬。我們可以設(shè)置 write
W_TRAP以及 read-or-writeRW_TRAP腕铸。
例子
這里我們用 WITCH 的 DeadCraft 來說明下 WITCH 是如何工作的惜犀，DeadCraft 主要是用來檢查 dead store。所謂 dead store狠裹，就是當(dāng)我們給一個地址設(shè)置了一個值扁远，然后馬上又用一個新的值在同樣的地址設(shè)置了，那么這個就是 dead store泻轰。如果我們設(shè)置了一個值疙渣，但后面馬上就 load 讀取了，這個就不是 dead store俗冻。
上面是 WITCH 用來檢查 dead store 的流程：
- PMU store event 的計數(shù)器溢出礁叔，觸發(fā)中斷
- WITCH 捕獲到了信號，得到 calling context C-watch 以及地址 M迄薄，跟 AccessType 合成一個 tuple <C-watch, M, AccessType> 發(fā)送給 DeadCraft
- DeadCraft 讓 WITCH 去監(jiān)控后續(xù)對地址 M 的 load 或者 store
- WITCH 給設(shè)置一個
RW_TRAP的 watchpoint - 后續(xù)程序訪問到 M琅关，watchpoint 捕獲
- WITCH 處理，得到 calling context C-trap讥蔽，并且將 <C-trap, M, AccessType> 給 DeadCraft
- 如果 AccessType 是 store涣易，那么 DeadCraft 就認(rèn)為這個是一個 dead store，并且將這次 dead store 設(shè)置為 <C-watch, C-trap>
實現(xiàn)
上面說到了 WITCH 一個簡單的例子勤篮，這里說下 WITCH 是如何實現(xiàn)的都毒， WITCH 主要是基于 HPCToolkit，主要有：
- PMU Sampling : 在 Intel CPU 上碰缔，主要設(shè)置
MEM_UOPS_RETIRED:ALL_STORES和MEM_UOPS_RETIRED:ALL_LOADSRegistration - Watchpoint : WITCH 會自動確定機(jī)器上面的 hardware debug registers账劲，使用 Linux
perf_event接口去注冊一個 watchpoint 事件HW_BREAKPOINT。WITCH 會注冊一個 signal handler 去捕獲 watchpoint 拋出的異常金抡。WITCH 也會把采樣周期設(shè)置為 1 瀑焦，用來保證只要訪問到了監(jiān)控的內(nèi)存就會跑出異常，被 WITCH 捕獲梗肝。 - Precise PC : 當(dāng) watchpoint 觸發(fā)的時候榛瓮，其實在 signal handler 里面得到的 PC（Context PC） 并不是當(dāng)前觸發(fā)中斷的 PC （Precise PC），而是在 Precise PC 之前的一條指令巫击。WITCH 使用 Last Branch Record （LBR）來得到 precise PC禀晓。
- Fast Watchpoint Replacement : WITCH 需要經(jīng)常的關(guān)閉 watchpoint，并且關(guān)掉所有跟這些 watchpoint 相關(guān)的內(nèi)核資源坝锰，WITCH 給
perf_eventioctl 接口加了個PERF_EVENT_IOC_MODIFY_ATTRIBUTES粹懒。 - Stack Addresses : WITCH 會用 sigaltstack 機(jī)制來用一個額外的 signal stack 處理 PMU 以及 watchpoint 的 signal。
挑戰(zhàn)
上面整個流程看起來是很簡單顷级，但實際還是有很多困難需要克服的凫乖，最大的困難就是采樣其實并不是精確的。譬如如下的例子：
1: for (int i = 1; i <= 100K; i++) {
2: arrya[i] = 0;
3: }
4: for (int j = 1; j <= 100K; j++) {
5: arrya[j] = j;
6: }
假設(shè)采樣周期是 10K，我們就只有一個 hardware debug register帽芽，那么 WITCH 會在第一個 array[10K] 的時候設(shè)置一個 watchpoint删掀，然后在 array[20K] 會有第二次采樣，但這時候已經(jīng)沒有空間設(shè)置 watchpoint 了导街。
如果采用最通常的做法披泪，后面的替換掉最老的，這個是不能工作的搬瑰。譬如當(dāng)我們在第一個循環(huán)最后 array[100K] 設(shè)置了 watchpoint 之后付呕，下一個在第二個循環(huán) array[10K] 會覆蓋掉之前的，但這時候其實是沒法發(fā)現(xiàn) dead store 的跌捆。為了解決這個問題，WITCH 引入概率機(jī)制來決定對于某一次采樣象颖，是否需要設(shè)置 watchpoint佩厚。
假設(shè)系統(tǒng)有 N 個 debug register，對于第 k 次采樣说订，k > N抄瓦，按照 N / k 的概率替換掉 N 里面的一個 watchpoint。也就是說陶冷，任何采樣都有 N / k 的概率來被監(jiān)控到钙姊。只要 watchpoint 被處罰，概率就被重置為 1埂伦。具體的推導(dǎo)可以詳細(xì)參考 paper煞额。當(dāng)然，paper 里面還說了其他很多的困難沾谜，這里就不一一說明了膊毁。
小結(jié)
總的來說，WITCH 的思路還是挺不錯的基跑，Paper 作者也通過它來找到了一些軟件中的無效處理婚温。我也在 Github 上面找到了 WITCH ，本來想試試媳否，看能不能找找 TiKV 中的無效處理栅螟，但一看安裝說明，需要裝一個定制版本的 Linux篱竭，就只好先打消了這個念頭力图，后面在嘗試吧。如果你對這塊很感興趣室抽，想在 TiKV 里面試試搪哪，歡迎聯(lián)系我 tl@pingcap.com。
