Edge-triggered 和 Level-triggered 用於事件處理時的意義

常在一些介紹網路事件處理的技術文章中看到 Edge-triggered 和 Level-triggered 這兩個詞, 我只知道這兩個詞是用來描述硬體中斷的處理模式, 卻不知用在軟體行為上衍生意義為何.

前幾天拜讀了 Dan Kegel 的一篇專文- The C10K problem, 講述伺服器要如何有效地處理網路上的事件通知, 這篇文章的內容對於各式處理 Network I/O 的手法和現有函式庫都講述的蠻詳盡的, 非常有價值. 文內就有解釋這兩個詞用於軟體處理事件行為的意義.

• Level-triggered 意指事件監看端 (作業系統/Kernel) 在每一次察覺到有新事件時, 都會通知事件接收端 (軟體程式). 
• Edge-triggered 則指事件監看端 (作業系統/Kernel) 在察覺到有新事件時, 會依照事件接收端 (軟體程式) 的處理狀態 (state) 來決定是否需要通知. 大致流程為: 

1. 接收端處理狀態初始為 low
2. 事件發生
3. 監看端得知接收端狀態為 low, 遂通知接收端並且設定處理狀態為 high
4. 該狀態會一直保持為 high 直到接收端將所有事件都處理完才會重置回 low, 而期間就算有新事件發生, 監看端也不會發出通知

舉一個生動一點的例子: 國王屬咐太監，如果有大臣來覲見就把它領來書房。這個例子中，國王即為事件接收端、太監則為事件監看端，而大臣的來訪即為事件。如果這個太監是按 Level-triggered 來行事，那麼每來一位大臣他就要領去書房一次。反之若太監以 Edge-triggered 來行事，當領了一位大臣去書房後，他就知道國王是「已經知道有大臣來訪」的狀態 (處理狀態為 high)，後續再有大臣來，就會直接放行請大臣自己進去、不再通知國王。直到國王再主動跟太監說「我都謁見完了」(處理狀態重置為 low)，之後太監再看到有大臣來訪才會再行通知。

如果要使用 Linux 平台上的 epoll()、或 BSD/MacOS 平台上的 kqueue() 來實作 Async I/O 時，這兩個詞的意義務必要先搞懂的。

Application Checkpointing

週末拜讀了 JServ 寫的一篇關於 porting DMTCP 到 Android 上的心得, 讓我有了一個非常好的契機去認識一門之前所不了解的技術 - Application Checkpointing.

Application Checkpointing 中的 checkpoint 概念可以想像是電動裡面的那種 checkpoint, 當玩家玩到某個進度, 或者經過某個地方時, 會自動觸發遊戲進行記錄. 當玩家過了 checkpoint 之後死亡或發生遊戲失敗, 遊戲會讓玩家在最近的一次 checkpoint 重生再次進行遊戲. Application Checkpointing 也是相同的概念, 只不過對象是 software application. Checkpoint 背後的運作原理則是先將 process 暫停, 隨即將所有運行時期的狀態, 諸如 Heap, Stack, Thread context, I/O buffer 之類的資訊全部鏡像到磁碟上. 有點類似系統休眠時發生的事, 不過粒度縮小至單一 process.

JServ 文章中提到的 DMTCP (Distributed Multi-Threaded CheckPointing) 則是一個 Linux 下的 Application Checkpoint 機制實現. 他和 0xlab 的夥伴們正嘗試把 DMTCP 整套機制 porting 到 Android 環境中, 企圖利用從 checkpoint 上再生的功能加速 Android 的開機流程.

DMTCP 的大致運作原理和使用方式都有涵蓋在該文中由 0x1ab 無私奉獻出來的投影片之內, 是非常好的 DMTCP 簡介材料. 這邊總結一下要點:

使用面:

• DMTCP 目前只運作在 Linux 之下, 需搭配 2.6.9 之後的 Linux Kernel 版本
• DMTCP 純粹運行在 user mode, 不需要任何 kernel patch 亦不需要 superuser 權限
• 任何程式不需要進行任何修改, 甚至不用重新編譯, 就能被 DMTCP 所管控
• DMTCP 授權方式為 LGPL
• DMTCP 在使用上主要會集中在四個 commandline tools, 具體使用方式可參閱這裡的 "Example Usage"

目前已知的使用限制為:

• DMTCP 會利用 SIGUSR2 這個 signal 在 DMTCP coordinator 和受控管的程式間做溝通, 若是程式也有利用到這個 signal 則會有衝突.
• DMTCP 目前只能控管與 C runtime 動態鍊結的程式.

有效分析 VC++ Debugger 丟出的 Heap Corruption 警告

最近一次進行專案 refactoring 之後發現使用 VC++ Debugger 進行程式除錯時, 有時 Debugger 會丟出 Heap Corruption 警示. 具體來說是跳出如下視窗:



同時 Visual Studio 的 Output window 中會出現:

"HEAP: Free Heap block xxxxxxxx modified at xxxxxxxx after it was freed"
的警告語句. 但這樣的 Debugger Break 只會發生在進行除錯時, 若是直接運行程式則不會有影響. 仔細做了一下功課之後發現這個 Debugger Break 的發生的原因是: 某塊曾經被 malloc/new 出來的 heap block, 在經過 free/delete 釋放之後, 其內容又被改動到.

一般來說, 只要是 OS 分配給你的 heap block, 一定都位於可讀寫的 virtual page 裡面. 因此就算是被釋放掉的區塊內容受到竄改, 實際運作時也不會觸發任何異常. 不過以程式寫作的觀點來看, 區塊已被釋放掉但內容卻受到竄改, 這高度暗示了程式中有 dangling pointer 的存在, 必需即早正視和排除. Windows 的 Debug CRT 函式庫為了讓 programmer 提早注意到這個問題, 在釋放 heap block 時會多動一點手腳: 在釋放前先把這個 heap block 裡面的內容全部填上一些制式的 pattern. 下次透過 malloc/new 獲得這些曾被釋放過的 heap block 時, 檢查看看裡面是否還保有那樣的 pattern, 藉以斷定內容是否被竄改過(*1), 若有就會觸發 Break.

正因這樣的警示只會在 Debugger 配合 Debug CRT 使用的情況下才會出現, 也許有些 programmer 對此抱持姑息的心態. 但 dangling pointer 就像是一顆不知啥時會爆炸的炸彈, 所以最好是一發現就盡全力去排除掉. 但在排除上會遇到一個問題: 在 Debugger Break 的那個中斷點上, Debug CRT 只能提出內容被竄改的結論, 但卻無法告訴你是哪行代碼在什麼時候竄改的. 根據這樣的情資一樣很難推估問題點. 網上一陣訪查之後發現很多人推薦使用微軟的一個 gflags 除錯工具來開啟 full heap validation 的功能. 實際試用過之後真得馬上幫我找出了問題點. 真是一個很神奇的工具. 整理心得如下:

1. gflags 是 Debugging Tools for Windows 套件其中的一隻工具程式, 而 Debugging Tools for Windows 目前只能靠安裝 Windows SDK for Windows 8 Release Preview 來安裝. 沒有單獨的安裝程式.
2. 安裝好了之後 gflags.exe 預設是位於 C:\Program Files\Windows Kits\8.0\Debuggers\x86 之下, 直接點擊執行會帶出 GUI 界面, 它也支援命令列模式. 使用命令列模式時建議用系統管理員身份來執行命令列, 不然每次執行 gflags 指令時, 顯示結果都會出現在另外開啟的命令列中, 馬上就消失.
3. 簡易用法 - 針對目標程式開啟 full heap validation 功能:

   gflags /p /enable xxxx.exe /full

   關閉 validation:

   gflags /p /disable xxxx.exe 

   開關後原程式不需要重編或做任何改動. 作業系統只要一偵測到有 xxxx.exe 這個執行檔在運作, 就會對它套用特別的 allocation 程序. 更多用法請參考這篇文章和這篇文章.
4. gflags 支援的命令列參數說明

根據這篇 msdn 文章的解釋, gflags 開啟的 full heap validation 原理是把所有 malloc/new 獲得的 heap block 都獨立安排在一個 virtual page 的最後面, 與邊界貼齊. 在該 virtual page 之後馬上安插一個不可存取的 page. 當 heap block 被釋放後, 也保證馬上將原 page 設定為不可讀寫. 若是有 dangling pointer 意圖存取曾被釋放過尚未被領用、或超過原 allocation 長度以後的內容, 馬上會觸發 page fault, 強制程式結束. 這樣就能第一時間發現問題點. 若 dangling pointer 的存取形態不是一般的向後超出, 而是向前超出怎麼辦? 這時可以參考命令列參數中的 /backwards 功能, 把 heap block 內容改成向前貼齊一個 page 的邊界. 由這樣的原理我們可以想像, 這樣的 heap blocks 會以非常鬆散的方式排列在記憶體中(每個 page 只放一個 allocation 單位). 所以當程式運作於 full heap validation 模式時, 會比原本多佔用數十倍的記憶體.

*1: Debug CRT 還會在其它一些特定時候填寫制式 pattern 到 heap 或 stack 中試圖引起程式設計師的注意, 可參考這篇文章.