[这篇博文也以实验形式发布在 Medium 上：https://medium.com/antirez/a-short-tale-of-a-read-overflow-b9210d339cff]

一个长时间运行的进程崩溃了，确实让人很不爽。尤其是当这个进程在内存中保存了大量状态时更是如此。这也是我喜欢这样一类 Web 编程框架的原因：它们能够在没有明显性能开销的情况下，为每次页面视图创建一个新的解释器和新的状态，并在页面生成结束时释放所使用的全部资源。这是一种天生更可靠的编程范式，在这种范式下，内存泄漏、描述符泄漏，甚至偶尔发生的随机崩溃，都不算什么严重问题。然而，像 Redis 这样的系统软件处于光谱的另一端——那里的一切都不应该崩溃。

几个月前，我收到了同事 Dvir Volk（迪维尔·沃尔克）发来的一份崩溃报告。他当时正在开发自己的 RediSearch Redis module，因此还无法确定崩溃是由 module 内部的编程错误导致的（也许是破坏了堆），还是 Redis 内部的 bug。不过，看起来很像是 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 的情况；我还编写了额外的数据模型，并创建了使用 1 亿个键的测试。但尽管付出了这些努力，我仍然无法重现崩溃。几天后我才发现，正在测试的实现根本没有 bug；但当时我还不知道这一点。我当然永远找不到一个并不存在的 bug。所以在无法重现之后，我放弃了。

一周前，我又收到了另外两份几乎完全相同的 bug 报告。这一次，地址同样被零填充。

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 节点时才以这种方式崩溃，因此很容易意识到问题是读取越界。否则，你永远无法检测到读取越界：它只会访问结构体之外、但仍处于已映射内存中的数据，所以这个 bug 完全无害且悄无声息，除非恰好在映射区域末尾执行同样的操作。最后，我终于有了明确的查找方向，就是下面这段 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 二进制文件发给我。通过阅读反汇编代码，我很快确认，Redis 崩溃报告中也包含的许多 CPU 寄存器仍然保存着上面那些变量的值！注意，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 代码……而是同一个函数的更新版本。Fedor 手头正好有 GCC 5.4.0，也就是报告该 bug 的用户所使用的同一个编译器，于是他尝试用它编译较旧版本的代码，结果发现这时生成的两份代码完全匹配。他联系我，问我是否确定这是一个最近版本的 Redis。我对此绝对确信：那是 Redis 4.0.6。但随后我开始产生了一些疑问，于是对比了 Redis unstable 分支和 Redis 4.0 中的 rax.c。事情的真相是：大约十个月前，在实现 Streams 的过程中，我已经修复了这个 bug。在将修复从 unstable 回移植到 Redis 4.0 的过程中，这个修复被包含在一个关于 streams 的提交里，所以我一直把它跳过了。一切终于真相大白：我花了好几天调试一个在所测试版本中根本不存在的 bug。

如果这只是我的一个低级错误，我为什么还要费心写这篇博文？因为我相信，这一切都能给我们带来一些值得吸取的教训。

第一个教训是，像 Redis 能够生成的这种崩溃报告，对于系统软件来说是一项关键资产。它们能让你重建那些无法复现、却偶尔会在实际环境中发生的 bug 的状态。虽然这个 bug 已经修复了，但只要查看 bug 报告、寄存器转储、出错地址和调用栈，我就能够准确理解到底发生了什么。

第二个教训是：如果你想从事系统编程，那么今天就应该学习 AMD64 汇编，至少要能够轻松阅读编译器生成的代码，并跟踪正在发生的事情。这往往是理解 heisenbug(海森堡 bug)期间发生了什么的唯一办法。调试器帮不上太多忙。GDB 声称崩溃发生在指令 parent->size-- 上，这当然不可能。但这不能怪 GDB：现代编译器在开启优化后生成的代码，很难再与源代码对应起来。

另一个教训是，完善的 fuzz testing(模糊测试)有多么强大。fuzz tester 在损坏的版本中立即找到了这个 bug。同样，除了这个早已修复的 bug 之外，再也没有观察到 radix tree 崩溃这一事实，本身就说明了一切。radix tree 的实现非常复杂，但得益于 fuzz testing，显然这个既新又复杂的实现中并没有 bug。我想强调的是，进行 fuzzing 不应只是为了寻找崩溃：那对于希望发现零日漏洞的安全人员来说当然很好。系统软件的 fuzzing 应当根据合理的操作模型执行随机操作，并将结果与参考实现进行比较。

最后，对我来说还有一个明确的教训：下次在 feature branch 上工作，并修复那些并非 feature branch 特有的问题时，我需要更加谨慎。当时我一直觉得自己会尽快把所有改动合并回 4.0。但事实并非如此，而且把 radix tree 的更新与实现 Stream 功能的内容放在同一个提交中，是一个致命错误。

好吧，还有一个加分项：拥有聪明的朋友来帮忙 :-) 当时我有点不知所措，而 Fyodor（费多尔）的热心帮助让我解开了谜题的最后一块，并迅速继续推进。不要害怕寻求帮助。如果你参与系统软件开发，请记住，它与编程的其他领域非常不同。并不是说你完成一些工作，就能把事情不断推进下去。你必须做好花上数天时间去弄清楚一个 bug 为何发生的准备——而且这个 bug 往往还无法复现，因为用户值得拥有比动不动就这样崩溃的软件更好的东西。