[本篇網誌文章亦於 Medium 上實驗性提供：https://medium.com/antirez/a-short-tale-of-a-read-overflow-b9210d339cff]

當一個長時間執行的行程當掉時，實在很讓人困擾。如果這個行程還在記憶體裡 holding 著大量狀態，那就更糟了。這也是為什麼我喜歡那種網頁程式框架，它能在幾乎不犧牲效能的情況下，為每一次頁面請求建立全新的直譯器與狀態，並在頁面產生結束後釋放所有用到的資源。這本質上是一種更可靠的程式設計典範，在這個典範裡，記憶體洩漏、描述符洩漏，甚至偶爾出現的隨機當機，都不算是嚴重的問題。然而，像 Redis 這樣的系統軟體則位於光譜的另一端，那一端充斥著絕對不該當掉的東西。

幾個月前，我收到同事 Dvir Volk 回報的當機報告。當時他正在開發 RediSearch 這個 Redis 模組，所以還不清楚這次當機究竟是模組內部的程式錯誤、可能是弄壞了 heap，還是 Redis 本身的臭蟲。不過，看起來很像是 radix tree 實作中一個真實的問題：

=== REDIS BUG REPORT START: Cut & paste starting from here ===
# Redis 999.999.999 crashed by signal: 11
# Crashed running the instuction at: 0x7fceb6eb5af5
# Accessing address: 0x7fce9c400000
| Backtrace:
| redis-server *:7016 [cluster](raxRemoveChild+0xd3)[0x49af53]
| redis-server *:7016 [cluster](raxRemove+0x34f)[0x49b34f
| redis-server *:7016 [cluster](slotToKeyUpdateKey+0x1ad)[0x4415dd]

radix tree 裡充滿了 memmove() 呼叫，而 Redis 正好是在試圖存取一個尾端被詭異地以零填充的記憶體位址時當掉的：0x7fce9c400000。我當下的第一個想法是，我肯定在哪裡把記憶體搬移搞錯了，導致位址被零覆寫，進而在程式試圖解參考該位址時造成當機。

我對自己的 radix tree 實作其實頗為自豪。不是因為實作本身，雖然這是個複雜的資料結構，但也還不到火箭科學的程度。而是因為它附帶的那個 fuzz tester，它能夠涵蓋全部的原始碼（這部分很簡單），以及大量不那麼直觀的狀態（這部分才真的有趣）。這個 fuzz tester 做 fuzzing 的目的不只是為了觸發當機，它會將 radix tree 字典與迭代器的實作，和一個使用 hash table 與 qsort 的參考實作拿來比對，兩者應具備完全相同的語意，只是參考實作更短，也更容易審核。收到當機報告後，我改進了 fuzz tester，跑了好幾天，無論有沒有搭配 Valgrind 都跑過，也寫了額外的資料模型，用一億個 key 來建立測試，但儘管如此努力，我還是無法重現當機。幾天後我才會發現，我當時測試的實作根本沒有臭蟲，只是那時我還不知道。我當然不可能找到一個根本不存在的臭蟲。所以在重現失敗後，我就放棄了。

一週前，我又收到了另外兩份幾乎一模一樣的臭蟲報告。而且，位址同樣都是以零填充作結。

Dvir crash: Accessing address: 0x7fce9c400000
Issue 4605: Accessing address: 0x7f2959e00000
Issue 4642: Accessing address: 0x7f0e9b800000

是時候把原始碼裡每一處 memmove、memcpy、realloc 呼叫都仔細讀過一遍，試著找出是否有什麼問題是 fuzz tester 沒能抓到的。我什麼也沒找到，但接著在檢查 Redis 當機報告時，我注意到一件奇怪的事。當機時 Redis 會列出行程的記憶體映射區域，像是這樣：

*** Preparing to test memory region 7f0e8c400000 (255852544 bytes)

現在，如果你把 255852544 加到 0x7f0e8c400000 上，結果會是 0x7f0e9b800000，正好就是 issue 4642 回報的當機存取位址。所以程式當掉並不是因為記憶體位址被破壞，而是因為它存取了緊接在 heap 尾端之後的位址。我檢查了其他幾個 issue，發現全部都是相同的狀況。基本上，heap 的尾端、也就是未映射位址範圍起點的邊界，正好扮演了記憶體守衛的角色，一旦有超出邊界的存取，就會被偵測並觸發當機。這是過去某些 C 語言記憶體檢測工具常用的技巧。這類工具會提供一個可直接替換 malloc() 的版本，回傳位於不可存取記憶體分頁邊緣的位址。任何溢位都會立刻以這種方式被偵測到。

因為程式只有在那種情況下才會當掉，也就是在釋放位於 heap 尾端的 radix tree 節點時，很容易就能判斷問題是讀取溢位（read overflow）。否則你是永遠偵測不到讀取溢位的：它只會去存取結構以外的資料，但仍在已映射的記憶體範圍內，所以這個臭蟲完全無害且沈默，只有在映射區域尾端執行相同操作時才會現形。終於，我有了明確的切入點，就是這段 C 程式碼：

/* 3. Remove the edge and the pointer by memmoving the remaining children pointer and edge bytes one position before. */
int taillen = parent->size - (e - parent->data) - 1;
debugf("raxRemoveChild tail len: %d\n", taillen);
memmove(e,e+1,taillen);
/* Since we have one data byte less, also child pointers start one byte before now. */
memmove(((char*)cp)-1,cp,(parent->size-taillen-1)*sizeof(raxNode**));
/* Move the remaining "tail" pointer at the right position
as well. */
size_t valuelen = (parent->iskey && !parent->isnull) ? sizeof(void*) : 0;
memmove(((char*)c)-1,c+1,taillen*sizeof(raxNode**)+valuelen);
/* 4. Update size. */
parent->size--;

我請使用者把產生當機報告的 redis-server 執行檔寄給我，讀取其反組譯後的程式碼後，很明顯地，許多 CPU 暫存器——同樣也包含在 Redis 當機報告中——仍然保留著上述變數的值！請注意，CPU 暫存器 RDI、RSI、RDX 是用來傳遞 memmove 的前三個參數的。在其中一次當機中，我們看到：

parent = RBP = 7f2959dffff
Checking RDI, RSI, RDX we extract the memmove() arguments:
memmove(00007f2959dffff4,00007f2959dffffd,0000000000000008);
The memmove will go out of bound accessing up to 7f2959e00004.

於是我有了證據。但還有更多，檢查其他暫存器後，我也能重建節點標頭，藉此了解 memmove 的 count 參數是如何得出的。那裡肯定有某個地方不對勁。基本上，我看到反組譯後的執行檔與我正在閱讀的 C 函式對不起來。這怎麼可能？對緩衝區的讀取本不該發生，因為當時的狀態是正常的。只有 count 在當掉的實例中被錯誤地計算出來。那時已是深夜，而我為了這個該死的問題已經連續工作了兩天沒停，所以我決定建一個 gist 並發到 Twitter 上，看看有沒有人能解釋，為什麼編譯器會把那樣的 C 程式碼轉成那樣的組合語言。

我很幸運，我那位以 Node.js 聞名的朋友 Fedor Indutny 願意幫忙。他很快就發現，為什麼 C 和組合語言對不起來其實非常明顯：我當時分析的根本不是正確的 C 程式碼……而是同一個函式的較新版本。Fedor 手邊剛好有 GCC 5.4.0，也就是回報臭蟲的使用者所使用的同一版編譯器，所以他試著用它來編譯舊版的程式碼，發現這時兩種產出的程式碼就完全吻合了。他傳訊息問我，是否確定這是較新的 Redis 版本。我非常確定，那就是 Redis 4.0.6。但接著我開始產生一些懷疑，於是拿 Redis unstable 分支與 Redis 4.0 的 rax.c 來做 diff。結果發現，我大約十個月前在實作 Streams 的過程中，就已經修掉了這個臭蟲。在把 unstable 的修正挑出來 backport 到 Redis 4.0 的 cherry-picking 過程中，這個修正被包在一個關於 streams 的 commit 裡，所以我一直略過它。一切終於水落石出，我花了好幾天除錯的是一個在我測試的版本中根本不存在的臭蟲。

如果這只是我犯的一個蠢錯誤，那我為何還要寫這篇網誌文章？因為我相信，這整件事中有值得學習的教訓。

第一個教訓是，像 Redis 能夠產出的那種當機報告，是系統軟體的重要資產。它們讓你得以重建那些你無法重現、卻在實際環境中極少發生的臭蟲狀態。雖然這個臭蟲早就已經修掉了，我還是能光靠臭蟲報告、暫存器傾印、肇事位址與呼叫堆疊，就精確地理解當時發生了什麼事。

第二個教訓是，如果你想投入系統程式設計，今天就該學會 AMD64 組合語言，至少要能輕鬆讀懂編譯器產生的程式碼，並追蹤實際發生的事情。這往往是在面對 heisenbug 時，唯一能搞清楚狀況的方法。除錯器幫不上太多忙。GDB 宣稱當機發生在 parent->size-- 這個指令上，這當然是不可能的。但這不能怪 GDB，在開啟最佳化的情況下，現代編譯器產生的程式碼本來就很難再對應回原始碼。

另一個教訓是，做得好的 fuzz testing 有多麼強大。在有問題的版本上，fuzz tester 立刻就找到了這個臭蟲。類似地，除了這個很久以前就已修掉的臭蟲之外，再也沒有觀察到任何 radix tree 的當機，這本身就很能說明問題。radix tree 的實作非常複雜，但多虧了 fuzz testing，這個既新又複雜的實作 apparent 上沒有任何臭蟲。我想強調，做 fuzzing 不該只是為了找出當機：那對想挖掘零時差漏洞的資安人員來說很好，但對系統軟體而言，fuzzing 應該根據合理的作業模型來執行隨機操作，並將結果與參考實作進行比對。

最後，對我自己有一個明確的教訓：下次在 feature 分支上工作、並做出與該分支特性無關的修正時，我得更小心一點。當時我心裡想著會盡快把所有東西合併回 4.0。結果並非如此，而把 radix tree 的更新放進同一個實作 Stream 功能的 commit 裡，是個致命的錯誤。

好吧，再加一點，有聰明的朋友幫忙真好 :-) 當時我有點卡住了，而 Fyodor 親切的協助幫我拼上了拼圖的最後一塊，讓我能迅速向前推進。不要害怕尋求協助。如果你投入系統軟體，請記住它與程式設計的其他領域非常不同。這不只是做些工作就能把事情往前推。你必須做好準備，花上好幾天去搞懂一個臭蟲為何發生，一個你往往無法重現的臭蟲，因為使用者值得擁有比那樣動不動就當掉更好的軟體。