[本文也已在 Medium 上试验性发布：https://medium.com/antirez/a-short-tale-of-a-read-overflow-b9210d339cff]

长时间运行的进程一旦崩溃，就相当糟糕。如果这个进程还在内存中承载了大量状态，那就更糟了。正因如此，我喜欢那些 Web 编程框架——它们无需付出太大的性能代价，就能为每一次页面访问创建全新的解释器和状态，并在页面生成结束后释放所有用到的资源。这是一种本质上更可靠的编程范式，在这种范式下，内存泄漏、描述符泄漏，甚至偶尔的随机崩溃，都算不上严重问题。然而，像 Redis 这样的系统软件则处在光谱的另一端，那是一个绝不该发生崩溃的世界。

几个月前，我收到了同事 Dvir Volk 发来的一份崩溃报告。当时他正在开发 RediSearch 这个 Redis 模块，所以一开始并不清楚这次崩溃究竟是模块内部的编程错误——比如破坏了堆——还是 Redis 自身的 bug。不过，它看起来很像是基数树实现中的一个实实在在的问题：

=== 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]

基数树里到处都是 memmove() 调用，而 Redis 崩溃时正好在尝试访问一个尾部被大量零填充、看起来很奇怪的内存地址：0x7fce9c400000。我的第一反应是，我肯定是在某处做错了内存搬运，导致地址被零覆盖，最终在程序试图解引用该地址时引发了崩溃。

我对自己的基数树实现还是相当自豪的。倒不是因为实现本身——虽然要实现这样一个复杂的数据结构并不简单，但也算不上什么高深学问——而是因为随之配套的模糊测试器。它不仅能覆盖全部源代码（这倒不难），更能覆盖大量非平凡的状态（这才真正有意思）。这个模糊测试器做模糊测试的目的并不只是为了触发崩溃，而是将基数树字典和迭代器的实现，与一个使用哈希表和 qsort 的参考实现进行对比，两者在语义上完全一致，但参考实现更短、也更容易审计。收到崩溃报告后，我改进了模糊测试器，接连跑了好几天，无论是否配合 Valgrind，还编写了额外的数据模型，用上亿个键来做测试，但即便如此，我依然无法复现这次崩溃。几天后我才发现，我当时测试的实现里根本就没有这个 bug，只是当时我还不知道罢了。一个本来就不存在的 bug，我自然永远也找不到。于是，在复现失败后，我放弃了。

一周前，我又收到了另外两份几乎一模一样的 bug 报告。同样，相关地址的尾部都是被零填充的。

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

是时候把源码里每一个 memmove、memcpy、realloc 调用都细读一遍了，看看是否有模糊测试器因某种原因未能捕捉到的问题。我一无所获，但在检查 Redis 崩溃报告时，我注意到了一个奇怪的地方。崩溃时，Redis 会报告进程的内存映射区域，像下面这样：

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

现在，如果把 255852544 加到 0x7f0e8c400000 上，结果正好是 0x7f0e9b800000，也就是 issue 4642 中崩溃报告里访问的地址。可见，程序崩溃并不是因为内存地址被破坏，而是因为它访问了紧跟在堆末尾之后的地址。我检查了其他几个 issue，发现情况完全相同。基本上，堆的末尾、未映射地址起始处的边界，正好起到了内存守卫的作用，一旦发生越界访问就会触发崩溃。这是过去某些 C 语言内存检查工具常用的一种技术。这类工具会提供一个可直接替换 malloc() 的实现，返回位于不可访问内存页边缘的分配地址。这样，任何溢出都会被立刻检测到。

由于程序只会在这种情况下崩溃——也就是在堆末尾释放基数树节点时——很容易就能意识到，问题是一次读越界。否则你是永远检测不到读越界的：它只是会访问结构之外、但仍处于已映射内存中的数据，因此这个 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 二进制文件发给我，读取反汇编代码后可以清楚地看到，许多 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，也就是报告 bug 的用户所用的同一个编译器，于是他用它编译了旧版本的代码，发现这次生成的代码与那两个版本完全吻合了。他联系了我，问我是否确定那是较新的 Redis 版本。我非常确定，那就是 Redis 4.0.6。但随后我开始有些怀疑，便对比了 Redis unstable 分支与 Redis 4.0 中 rax.c 的差异。原来，大约十个月前，我在实现 Streams 的过程中就已经修复了这个 bug。在将 unstable 分支的 bug 修复 cherry-pick 回 Redis 4.0 的过程中，这个修复被包含在一个关于 streams 的提交里，所以我一直在跳过它。一切终于水落石出——我花了好几天时间调试的，竟是一个在我测试的版本中根本不存在的 bug。

如果这仅仅是我犯的一个愚蠢错误，那我又何必写这篇博客呢？因为我相信，这件事中仍有值得吸取的教训。

第一个教训是，像 Redis 能够生成的那种崩溃报告，是系统软件的关键资产。它们让你得以重构那些无法复现、却在实际环境中极少发生的 bug 的状态。尽管这个 bug 其实早已修复，我依然能够仅凭 bug 报告、寄存器转储、出错地址和调用栈，就准确弄清到底发生了什么。

第二个教训是，如果你想涉足系统编程，今天就应该去学 AMD64 汇编，至少要能自如地阅读编译器生成的代码、跟上到底发生了什么。这往往是理解 heisenbug 发生原因的唯一途径。调试器帮不上太大忙。GDB 曾声称崩溃发生在 parent->size-- 这一行上，这当然是不可能的。但这不能怪 GDB，现代编译器在开启优化后生成的代码，很难再与源代码一一对应。

另一个教训是，做得好的模糊测试有多么强大。模糊测试器立刻就能在有缺陷的版本中找到这个 bug。同样地，除了这个很久以前就已修复的 bug 之外，再也没有观测到过基数树的崩溃，这本身就说明了很多问题。基数树的实现非常复杂，但多亏了模糊测试，这个如此新颖又如此复杂的实现中似乎已经没有 bug 了。我想强调，做模糊测试的重要性不仅仅在于发现崩溃——那对想要挖掘零日漏洞的安全人员来说很有用。对于系统软件而言，模糊测试应该按照合理的操作模型执行随机操作，并将结果与参考实现进行对比。

最后，对我个人而言还有一个明确的教训：下次在特性分支上工作、并修复那些并非该分支特有的问题时，我需要更加小心。当时我总觉得会很快把所有东西都合并回 4.0。结果并非如此，而把对基数树的更新放进同一个实现 Stream 功能的提交中，是一个致命的错误。

好吧，额外的一点是，有聪明的朋友帮忙 :-) 在那个节点上我有点迷茫了，而 Fyodor 的热心帮助让我拼上了拼图的最后一块，得以迅速推进。不要害怕寻求帮助。如果你投身于系统软件，请记住，它与编程的其他领域截然不同。不是说你做些工作就能不断向前推进。你必须做好准备，花上数天时间去弄明白一个 bug 为何会发生——一个你往往无法复现的 bug，因为用户理应得到比动不动就崩溃的软件更好的东西。