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 中試圖引起程式設計師的注意, 可參考這篇文章.

OSSP 的 uuid 函式庫內有精簡的 md5/sha1 hash 實作

手邊 C++ 專案需要實現 SHA1 hash 的功能, 原本想到的是透過 OpenSSL / Botan 這類的現有函式庫來達到, 但轉念想想沒道理為了加扇窗就把整棟大樓的材料都堆進來. 就一直在網上尋找精簡的 md5/sha1 hash 實現. 不知道是鬼打牆還是怎地一直沒找到. 而事情就這麼巧, 接著在找 uuid 開源替代方案時找到 OSSP 的 uuid 專案, 裡面竟然帶有一套不依賴任何第三方函式庫的 md5/sha1 實現. 整個專案還是用 MIT 授權, 真是踏破鐵鞋無覓處...

有個小問題是 uuid 目前的 build process 不支援 Windows 平台 (以 OSSP 的宗旨來看也很合理) , 它是基於 autogen/configure 那一套 unix 標準程序的, 引用的 header 中也有包含 unistd.h 這類在 Windows 缺乏對應的文件. 不過評估了一下 porting 的功夫不會很大, 小改了一下目前在 MSVC 環境中已可建置它的 md5/sha1 hash 模組. 有時間會嘗試整個 porting. 想要導入 cmake 代替原有的 autogen, porting 完之後可以一次搞定 msvc, mingw, cygwin 三個環境.

Sourceforge: http://sourceforge.net/projects/osspuuidwin32/

跨網路資料交換

最近這一個月都在反覆實作與檢示 Client Server 之間的資料交換架構. 一般最直觀的資料交換, 就是任何一方發送資料時先經過制式的序列化 (serialization, 或稱 deflating, marshalling) 程序, 把運行時結構化的數據資料成員重新排列成平面且緊密的純二進位資料流 (binary data stream), 然後將資料流送出, 接收方再透過相對應的反序列化程序 (deserialization, 或稱 inflating, unmarshalling) 把收到的資料流重組回結構化的數據.

這樣直觀的流程套用在開發專案時會遇到一個問題: 每種需要進行資料交換的結構化數據類型都必需要撰寫其專有的序列化/反序列化程序. 這樣的需求在結構化數據類型會隨專案開發的進度而大量增加時就會變得很繁瑣. 為了解決這種窘境, 我們會希望在序列化時盡量讓輸出的資料流保有某種程度上的自述性. 也就是說不管面對何種類型的數據類型, 序列化/反序列化的做法都要能是同一套, 序列化時除了資料本身之外, 還夾帶了這些資料的型態, 彼此的結構關系這類資訊, 提供反序列化程序檢示, 賴以重組回結構化的數據. 舉一個極端的例子: 進行序列化時, 將結構數據輸出為用 JSON 或 YAML 這類資料描述語言的描述語句, 反序列化時解析這些語句重組回結構化數據. 通常這些描述語言都已有很好的各類程序語言函式庫, 可提供現成的輸出描述語句和解析語句的功能.

輸出具有自述性的資料流會有個不良影響是會導致資料流的膨脹. 原本只要夾帶資料本身, 現在要多附加資料型態和結構關係, 所以因資料膨脹導致交換效能降低是必然的結果. 那麼在效能跟繁瑣之間有沒有妥協方案呢? Google 提倡的 protobuf 就是一例. 它的運作原理是, 把資料型態和結構化關係這類額外的資訊另外寫成 .proto 的文件 (protobuf 本身的資料描述語法), 透過 protobuf 提供的編譯功能編譯這些 .proto 文件產生專有的序列化/反序列化模組, 程式運行時再透過這些模組對於該資料類型進行序列化工作. 輸出的二進位資料流的緊密度和效能就由 protobuf 來背書, 理論上會比自述性資料流來得好, 因為要傳輸的資料較密(量較少)且序列化過程中做的事較少.

目前已實現基於 JSON 自述的序列化程序, 正朝 protobuf 前進. 由於需要交換的結構化數據都是用 XML Schema 定義, 所以要做 protobuf 的實現必需先克服由 XML Schema 自動生成 .proto 文件的這一步.

如何查看編譯器預先定義的巨集 (Predefined Macro) 有哪些?

建立跨平台且能兼容各家編譯器的 C/C++ 軟體專案時會需要知道各家 Compiler 在不同平台上分別會設定哪些 Predefined Macro, 以便後續於程式碼中利用.

目前 GNU 和 LLVM-Clang 的 Compiler 不管是 Unix 上或是 Windows 上的 cygwin/mingw 環境中, 都可透過同樣的方式去取得 Predefined Macro 列表:

    <gcc|g++|clang> -dM -E -x <c|c++> <input file>    

例如:

    clang -dM -E -x c /dev/null    

    g++ -dM -E -x c++ /dev/null    

而微軟的 cl 所定義的巨集可以直接查看 msdn 文件.

備忘: Unicode, UTF-8, CESU-8

最近都在跟 Redis 打交道, 我們的專案內部的字串資料都是用 wchar_t 的型式來操作的, 沒想到一考慮到跨平台就要面臨 Windows 和 Unix 對於 wchar_t 長度各自表述的問題. 又為了省空間 (字串純英數的比例較大), 在從資料庫存取字串時, 都加上了 UTF-8 (正確來說, 是 CESU-8) 轉換. 費了很多意料之外的時間在處理這些相關問題. 簡單整理了幾點注意事項備忘:

• Unicode 定義中, 一個字碼單位稱為一個 code point. 每 65,535 個 code points 組成一個 plane. 而目前總共定義有 17 個 planes. 最常用的字碼都集中在第一個 plane 中 (plane #0), 該 plane 又稱為 BMP (Basic Multilingual Plane).
• Windows 中的 wchar_t 長度是 16 bits, 使用 UTF-16 編碼. 16 bits 只有辦法涵蓋一個 plane 的字碼量, 因此正常來說就是映射到 BMP 的字碼. 罕見情況下需要使用其它 plane 中的字碼時, 就用連續的兩個 wchar_t 來表示一個 Unicode code point (稱為 Surrogate Pair, 代理對). 所以不要認為 Windows 系統上所有的 wchar_t 字串  raw bytes 長度除以 2 就是字串長. 有機會陰溝裡翻船.
• Unix 中的 wchar_t 長度是 32 bits, 使用 UTF-32 編碼. 因為 32 bits 已經可以涵蓋所有 planes 所有 code points. 所以 Unix 上一個 wchar_t 一定就對應到一個 Unicode code point.
• UTF-8 轉換理論上要能函蓋所有 code points, 但實際上大多數的 UTF-8 轉換實作都只針對 BMP 中的 code points. 意即每次讀入一個 UTF-16 2bytes 轉換為 UTF-8 1~3bytes, 且不考慮 Surrogate Pair, 因此 Surrogate Pair 的兩個 wchar_t 會被錯誤地當成兩個獨立的 UTF-16 字碼進行轉換. 現今漸漸改用 CESU-8 這個詞來稱呼這種較簡略且非正規的轉換法. CESU 為 Compatibility Encoding Scheme for UTF-16 的縮寫.
• Modified UTF-8 原理其實跟 CESU-8 是幾乎相同的 (所以正確來說, 應該叫 Modified CESU-8), 只差在 UTF-16 中的 NULL (即 0x0000) 並不轉換為 (0x00), 而是 (0xC080) 的雙字節, 以避免該 (0x00) 被當成字串結尾.
• 包含 Orcale, Java, Dalvik, Tcl, 等等重量級的軟體專案, 其中號稱的 UTF-8 轉換, 其實都只有達到 CESU-8 或 Modified UTF-8 的程度.

References:

1. http://en.wikipedia.org/wiki/Unicode
2. http://en.wikipedia.org/wiki/UTF-8
3. http://en.wikipedia.org/wiki/CESU-8