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

當一個長時間執行的行程當掉時，實在很糟。更何況如果該行程在記憶體中保存了大量狀態時更是如此。這就是為什麼我喜愛網頁程式設計框架的原因——它們能夠在沒有顯著效能開銷的情況下，為每次頁面檢視建立新的直譯器與新的狀態，並在頁面產生結束時釋放所使用的所有資源。這本質上是一種更可靠的程式設計典範，在此典範中，記憶體洩漏、描述符洩漏，甚至偶發的隨機當機都不構成嚴重問題。然而，像 Redis 這類的系統軟體則處於光譜的另一端，那是一個絕對不該當機的世界。

幾個月前，我從同事 Dvir Volk（德維爾·沃克）那裡收到一份當機報告。當時他正在開發他的 RediSearch Redis 模組，因此並不清楚這次當機是由於模組內部的程式錯誤——或許是破壞了堆積——還是 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 進行模糊測試的目的不僅是為了觸發當機，它會將 radix tree 字典與迭代器的實作，與一個使用雜湊表與 qsort 的參考實作進行比對，以確保兩者具有完全相同的語意，但參考實作則以簡短且易於審核的方式呈現。收到當機報告後，我改進了 fuzz tester，連續執行了數天，無論有無使用 Valgrind，都進行了測試，撰寫了額外的資料模型，並建立了使用一億個鍵的測試，但儘管如此努力，我仍無法重現當機。幾天後我才會發現，我所測試的實作中根本沒有錯誤，但在當時我並不知情。我根本不可能找到一個不存在的錯誤。因此，在無法重現後，我便放棄了。

一週前，我又收到了另外兩份幾乎相同的錯誤報告。同樣地，這些位址的尾端都是以零填充的。

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 回報的當機中所存取的位址。因此，程式當機並非因為記憶體位址遭到破壞，而是因為它存取了堆積結尾之後緊接著的位址。我檢查了其他幾個 issue，發現所有案例皆是如此。基本上，堆積的尾端，在未映射位址起始處的邊界上，起到了記憶體保護的作用，以便在發生越界存取時偵測並觸發當機。這是過去某些 C 語言記憶體驗證工具常用的技巧。這類工具會提供一個可直接替換 malloc() 的實作，回傳配置在不可存取記憶體分頁邊緣的位址。如此一來，任何溢位都會立即被偵測到。

由於程式只會在這種情況下當機——也就是在釋放位於堆積尾端的 radix tree 節點時——很容易就能意識到問題是一個讀取溢位。否則你永遠無法偵測到讀取溢位：它只會存取結構外部、但仍在已映射記憶體範圍內的資料，因此這個錯誤將會是完全無害且沈默的，唯有在映射區域的尾端執行相同操作時才會顯現。終於，我有了明確的查找方向，就是這段 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 的數量參數是如何得出的。那裡肯定有問題。基本上，我看到反組譯後的執行檔與我正在閱讀的 C 函式並不相符。這怎麼可能？對緩衝區的讀取越界本不該發生，因為狀態是正常的。只有計數值在當機的實例中被錯誤地計算。當時已是深夜，而我已經為這個該死的問題不眠不休地工作了兩天，於是我決定建立一個 gist 並發到 Twitter 上，看看是否有人能解釋編譯器如何會將那樣的 C 程式碼轉成那樣的組合語言。

幸運的是，以 Node.js 聞名的朋友 Fedor Indutny（費多爾·印杜特尼）願意幫忙。他很快就意識到，為什麼 C 程式碼與組合語言無法對應其實非常明顯：我所分析的並非正確的 C 程式碼……而是同一個函式較新的版本。費多爾手邊剛好有 GCC 5.4.0，也就是回報錯誤的使用者所使用的同款編譯器，因此他試著用它來編譯較舊版本的程式碼，發現此時兩種版本所產生的程式碼完全吻合。他隨即通知我，問我是否確定這是較新的 Redis 版本。我非常確定，那就是 Redis 4.0.6。但接著我開始產生一些疑慮，於是對比了 Redis unstable 分支與 Redis 4.0 之間 rax.c 的差異。結果發現，我大約十個月前，在實作 Streams 的過程中就已經修復了這個錯誤。在將 unstable 分支的錯誤修正挑選並回移植到 Redis 4.0 的過程中，該修正被包含在一個關於 streams 的提交中，因此我一直略過了它。一切終於真相大白，我花了好幾天除錯的錯誤，在我所測試的版本中根本就不存在。

如果這只是我犯下的一個蹩腳錯誤，我又何必寫這篇部落格文章呢？因為我相信，從這整件事中仍有值得學習的教訓。

第一個教訓是，像 Redis 所能產生的這類當機報告，是系統軟體中的關鍵資產。它們讓人得以重建那些無法重現、卻在實際環境中極為罕見發生的錯誤狀態。雖然這個錯誤早已被修復，我仍能僅透過檢視錯誤報告、暫存器傾印、肇事位址與呼叫堆疊，就準確理解當時發生了什麼事。

第二個教訓是，如果你想投入系統程式設計，今天就應該學習 AMD64 組合語言，至少要能輕鬆閱讀編譯器產生的程式碼，並追蹤實際發生的情況。這往往是理解 Heisenbug(海森堡錯誤) 發生原因的唯一方法。除錯器幫不上太多忙。GDB 聲稱當機發生在 parent->size-- 這一行指令上，而這當然是不可能的。但這不能怪 GDB，現代編譯器在開啟最佳化後，所產生的程式碼幾乎難以再對應回原始碼。

另一個教訓是，做得好的 fuzz testing(模糊測試) 有多麼強大。fuzz tester 立即就能在有缺陷的版本中找到這個錯誤。同樣地，除了這個早已修復的錯誤之外，從未觀察到任何其他 radix tree 當機的事實，已說明了一切。radix tree 的實作非常複雜，然而多虧了 fuzz testing，這個如此新穎且複雜的實作中顯然已沒有錯誤。我想強調，進行模糊測試的重要性不僅在於尋找當機：那對於想要發掘零時差漏洞的資安人員來說當然很好。對於系統軟體而言，模糊測試應該根據合理的作業模型執行隨機操作，並將結果與參考實作進行比對。

最後，對我個人而言還有一個明確的教訓：下次在功能分支上工作、並進行與該功能分支無關的修正時，我需要更加謹慎。當時我抱著一種感覺，認為自己很快就會將所有內容合併回 4.0。結果並非如此，而將 radix tree 的更新與實作 Stream 相關內容放在同一個提交中，則是一個致命的錯誤。

好吧，額外的一點是，有聰明的朋友幫忙 :-) 當時我有點迷失方向，而費多爾親切的協助幫助我拼湊出謎題的最後一塊，並迅速取得進展。不要害怕尋求協助。如果你投入系統軟體，請記住它與程式設計的其他領域非常不同。這不僅僅是做些工作就能推動進展。你必須準備好花上數天時間去理解一個錯誤為何發生，一個你往往無法重現的錯誤，因為使用者值得擁有比這樣動不動就當掉的軟體更好的東西。