钻头

2021年5月26日
第19卷，第2期

钻头

薛定谔的代码

理论与实践中的未定义行为

Terence Kelly，特邀嘉宾 Weiwei Gu 和 Vladimir Maksimovski

理智与速度

未定义行为是流行编程语言中最令人困惑和危险的方面之一。“钻头”专栏的这篇文章澄清了广泛的误解，并提出了实用的技术，以消除您自己代码中的未定义行为，并查明任何软件中无意义的操作——这些技术揭示了支持财富 500 强公司业务关键型应用程序的软件中令人震惊的缺陷。

在编程语言的历史早期，出现了两种思想流派。快速排序的发明者 C.A.R. Hoare 在他的图灵奖演讲中总结了一种哲学：⁷ 每个语法正确的程序的行为都应该可以从其源代码中完全预测。为了安全、保障和程序员的理智，程序“失控”是绝对不允许的。确保行为良好定义会带来运行时开销（例如，数组边界检查），但可预测性证明了这种成本是合理的。今天，Java 等“安全”语言体现了 Hoare 的建议。

另一种哲学在需要效率和速度的领域（例如，基础设施软件）中占据主导地位。C 和 C++ 等系统编程语言为了性能而牺牲了安全性和全面的语义。尽管这些语言经过了细致的标准化，但它们没有定义所有已编译代码的行为。如果正在运行的程序违反了无数规则中的任何一条，那么一切都不可预测了。程序可能会按预期运行，或者崩溃，或者破坏无价的数据，或者为互联网恶棍服务。计算机甚至可能会着火——流氓软件可能会真正烧毁最初的 IBM PC。¹³

通过声明某些编码错误会产生未定义行为，语言标准允许编译器跳过运行时检查并积极优化。它们还将确保可预测性的负担转移到程序员身上。不幸的是，未定义行为以多种方式出现；C 标准的附录 J.2 列出了许多²，而 C++ 添加了更多³。

本文调查了最突出的陷阱，展示了来自生产软件的示例，并提出了在串行代码中预防和检测此类错误的实用方法。Hans-J. Boehm 和 Sarita V. Adve 早在Queue上发表的一篇文章中就讨论了多线程软件中的未定义行为。¹

猜测

物理直觉误导了一些开发人员，让他们相信自己可以预测执行未定义操作的软件的行为：“如果轨道缺陷导致机车脱轨，火车将会驶向某个地方”，他们这样推理，并得出结论，我们可以知道驶向哪里。如果纯粹的推理无法推断出结果，那么实验肯定必须是明确的：“就像薛定谔的猫一样，未定义的软件仅在我们观察其行为之前才处于不确定状态，然后某些事情将会发生。” 试试看，这种心态说道。

然而，预测未定义代码的行为是徒劳的。实验仅仅记录了未定义代码在过去运行时发生的情况。它们无法预测未来，届时代码会遇到更智能的编译器、升级的运行时支持、新的硬件以及执行环境中看似无关的差异。关于源代码的纯粹推理是徒劳的，因为它依赖于明确认为未定义行为不可预测的语言标准。

此外，惊讶可能在执行到达未定义操作之前很久就开始了。C++17 标准中的一段不祥的段落预示着一个镜花水月般的世界，其中因果倒置：“[如果] 执行包含未定义操作，则本国际标准对使用该输入执行该程序的实现不作任何要求（甚至对于第一个未定义操作之前的操作也是如此）”[强调]。³

体外未定义行为

图 1 中的 C/C++ 函数包含我在生产代码中反复看到的四个未定义操作；注释指示（不合理的）行为预测。开发人员可能会天真地期望合适的参数来执行 if 分支，并产生可预见的后果：图 1a 中的 null_deref(1) 会导致段错误；图 1b 中的 div_by_zero(1) 会导致硬件陷阱；图 1c 中的 uninit(1) 会读取任意“堆栈垃圾”；图 1d 中的 overflow(INT_MAX) 会导致有符号整数加法“环绕”为负值。

测试这些预测会将您拉入镜中世界。使用 Clang 11.0.0 编译并使用旨在练习 if 和 else 分支的参数调用每个函数，会打破天真的期望。函数 null_deref() 不会段错误，div_by_zero() 不会陷阱，并且所有四个函数始终返回 47，而与 x 参数无关。就好像 if 分支消失了一样——事实上它们确实消失了：编译器发出的汇编代码完全没有算术运算、比较、分支和倒霉的数字。所有四个函数都编译为相同的双指令序列，该序列返回相同的常量。如果这段代码是一只猫，那么它是柴郡猫，而不是薛定谔的猫，几乎完全消失了，只留下一个挥之不去的 return 47 来嘲笑困惑的程序员。

数学认知人士可能会怀疑编译器利用了 20 世纪 60 年代的一个晦涩证明：返回 int 的函数始终可以返回 47，因为所有数字都等于 47。⁴⁷ 实际上，编译器的推理如下：C 和 C++ 语言标准规定执行不得到达未定义的代码；图 1 中的 if 分支显然执行未定义的操作；因此，if 分支必须是不可达的，可以省略。这种省略并非 Clang 独有——包括 GCC 在内的其他编译器也采取类似行动——并且根据标准，这完全合法：如前所述，可达的未定义代码会使保修失效，“甚至对于第一个未定义操作之前的操作也是如此。”

对于标准而言，消除未定义的代码不会造成任何损害；在实践中，它可能是有益的。正如通过坏疽肢体的循环可能是致命的一样，执行包含未定义操作的代码路径可能会引发混乱。幸运的是，编译器以南北战争战地外科医生的冷酷眼光看待此类代码路径：对于患者而言，用一条好腿活着总比因一条坏腿而死好。

图 2 显示，截肢的程度不仅限于单个错误指令；它是无限的。函数 sumdiv() 旨在计算整数的除数之和，但变量 s 未初始化。因此，递增 s 是未定义的，因此整个函数可能会简化为 return 47（GCC 10.2.1 就是这样编译它的）。从图 2 中消除的逻辑可能已经任意复杂了。编译器不会消除不透明的函数调用，这些调用可能会 exit()，从而使未定义的操作无法到达。然而，任何数量的普通逻辑都可能被无情地砍掉。一个小小的不小心造成的未定义操作会使编译器丢弃您的鸿篇巨制、您的毕生心血、您最辉煌的代码，这些代码花费了惊人的辛勤劳动和泪水——一切都在眨眼间消失得无影无踪，而您却毫不知情或不同意。随着编译器变得越来越智能，截肢的范围将会扩大。

当然，标准仅仅是允许但没有要求编译器删除未定义的代码路径；编译器可以对这些路径做任何事情。同样，尝试预测或控制未定义代码在编译或执行时的结果是愚蠢的。

采取行动

程序员应该如何应对未定义行为的威胁？

有些人对他们的编译器怒斥，坚持认为未定义的代码应该按照错误作者的意图行事。⁶ 这种咆哮并没有达到预期的效果。相反，编译器编写者已经发出通知，他们将继续利用语言标准授予的自由。⁹

其他开发人员禁用编译器优化，希望从未定义的操作中获得可预测的行为，就像某些版本的 Linux 内核和一些开源程序所做的那样。¹⁴ 这种方法依赖于特定编译器的非标准、不可移植的功能，并且会降低性能。类似的方法是为特定的未定义操作指定结果。例如，GCC 的 -fwrapv 标志确保有符号整数加法在溢出时环绕。¹² 此类标志不可移植，并且是影响范围内所有算术运算的钝器。虽然它可能非常适合激励程序员使用 -fwrapv 的少数操作，但代码其他部分中的溢出环绕可能会像没有 -fwrapv 的结果一样让程序员感到惊讶。

当然，正确的方法是编写行为可根据相关语言标准预测的软件。勤奋的程序员仔细研究标准，并利用工具将未定义的操作排除在他们的代码之外。

标记无意义的代码

现代编译器是查找未定义代码的最简单但功能最强大的工具之一，但要充分利用编译器需要技巧。这里使用 GCC 来演示关键技术；其他优秀的编译器也提供类似的功能。

开发人员可能期望 GCC 的 -Wall 标志名副其实，但它实际上只启用了可用警告的一小部分。-Wextra 添加了更多警告，但许多警告必须单独请求。例如，-Wall 和 -Wextra 都没有激活 -Wnull-dereference 检查。此外，某些警告依赖于优化。例如，-Wall 和 -Wextra 都会警告使用未初始化的变量，但仅当也启用优化时，GCC 才会执行所需的分析。¹² 曾经，作者之一遇到一个利润丰厚的专有程序，该程序在测试时使用警告但没有优化进行编译，而在生产时使用优化但没有警告进行编译。在这个代码中，近 100 个未初始化的变量错误已经逃避检测多年，开发人员在学习以更具信息量的方式进行编译后，匆忙修复了这些错误。

编译器警告如何找到图 1 中的四个错误？无论优化级别或警告标志如何，GCC 10.2.1 始终警告除以零的情况。当同时使用优化和 -Wall -Wextra 调用时，它会警告使用未初始化的变量。优化和 -Wnull-dereference 一起揭示了图 1a 中的错误。-Wsuggest-attribute=const 提供的警告引起了人们对图 1d 中错误溢出测试的注意。

图 3 说明了一个阴险的错误，当责任落在模块之间的裂缝中时，就会出现这种错误。图 3a 中的函数假定其调用者已初始化通过引用传递的数据。然而，图 3b 中的调用者假定被调用者会初始化它，因此 main() 使用了未初始化的变量 a、b 和 c。编译器通常分别考虑翻译单元（.c 文件），因此它们无法发现像这样的错误，这种错误并非完全存在于任何一个翻译单元中。幸运的是，使用 GCC 的 -flto 标志编译和链接这两个文件会产生警告，这是链接时优化的副作用。

防止缺陷的最佳方法是通过“编译时卫生”尽早、自动且廉价地捕获错误。¹⁰ 除了以调试/测试模式和生产模式构建软件外，还要添加第三种“最大警告”模式：调用 gcc --help=warnings 以获取可用标志的完整列表，每个标志都在手册中进行了完整描述。¹² 努力实现尽可能多地启用警告的干净构建；使用禁用优化 (-O0) 和再次使用 -O2 或 -O3 进行编译。尝试使用链接时优化等功能来捕获跨越翻译单元的错误。

为了获得奖励积分，还可以使用优秀的 lint 类工具或静态分析器，如 Coverity⁵，它可以更深入地检查代码，并查找比大多数编译器更广泛的错误。GCC 和 Clang 也有静态分析器，可以超越普通的编译器检查。例如，GCC 的 -fanalyzer 功能旨在查找释放后使用错误。

像考虑洗礼的猫一样，一些开发人员将编译时卫生视为通过清晰且眼前的苦难来购买可疑的假设虔诚的方式。诚然，第一次使用启用最大警告的旧代码进行构建时，它通常会喷出令人望而生畏的诊断洪流；有些是虚假的，所有都需要时间来修复或消除。然而，投入精力清理构建通常会修复一些真正的错误。这也是了解更多关于编程语言的好方法，编译器比大多数程序员更了解编程语言。从长远来看，维护干净的最大警告构建会获得丰厚的回报，并且如果从程序诞生的那天起就强制执行此不变性，则尤其容易。

案例研究：Redis

编译时卫生在应用于经过全面测试的工业强度软件时证明了其真正的价值。Redis 是一种开源 NoSQL 数据库，广泛用于商业上重要的应用程序。¹¹ 默认情况下，Redis 使用 GCC 的 -Wall、-Wextra 和其他一些警告标志进行构建，但其构建系统可以轻松添加更多标志。

使用几乎所有 GCC 警告标志构建 Redis 版本 6.2-rc2 会产生十几个关于 NULL 指针解引用的警告；图 4 显示了一个错误。第 333-354 行的 for 循环在指针变量 ln 为 NULL 时终止；它在第 370 行被解引用。此错误首次出现在候选版本 5.0-rc4（2018 年 8 月）和常规（非候选）版本 5.0.0（2018 年 10 月）中。它仍然存在于版本 6.0.11（2021 年 2 月）中。人类审计员很容易忽略这样的错误。测试可能无法捕获它，这是由于测试覆盖率差——或者因为编译器删除了未定义的代码路径。捕获此类错误的简单且万无一失的方法是 -Wnull-dereference 标志，GCC 自 2016 年 4 月起就支持该标志。

检查大约 50 个 -Wfloat-equal 警告会导致明显的故意除以零，这可能是未定义的，具体取决于语言方言和实现。图 5 中的代码在第 526 行除以零，以完成标准 signbit() 宏可以正确、可移植且简洁地完成的任务。

其他警告突出了通常伴随错误的混乱。例如，-Wduplicated-branches 产生三个警告，其中两个警告指的是图 6 中的代码。图 6a 中跨越第 1734-1738 行的冗长而复杂的 else if 条件没有任何作用，因为它触发的操作与最终的 else 相同（第 1739 行和 1741 行是相同的）。这种异常现象起源于对 23 个文件进行 1,500 多次更改的提交；如果未自动检测到，则通过大型更新渗透的错误往往会累积。图 6b 第 3176 行中类似的过度简化，三元运算符，可能反映了程序员的疲劳而不是意图。自 2017 年 5 月以来，GCC 一直支持 -Wduplicated-branches。

激活并注意超出 -Wall 和 -Wextra 的编译器警告将会在这些 Redis 错误（以及此处未报告的其他几个错误）首次编写后几分钟内消除它们。

深入挖掘

除了在构建时警告错误外，编译器还可以检测程序以在运行时检测未定义行为。查看 GCC 的 -fsanitize 和 Clang 中的类似功能。⁴ Valgrind 等独立工具可以在测试期间捕获内存错误和其他类型的错误。测试的主要局限性在于它依赖于输入来练习代码——如果您认为修复编译器警告是一件苦差事，请尝试编写测试输入来覆盖大型程序中的每个执行路径。并且测试无法触发编译器消除的代码路径上的故障，因为这些代码路径包含未定义的操作。

位

本专栏中的代码示例可在 https://queue.org.cn/downloads/2021/Drill_Bits_04_sample_code.tar.gz 获取。源文件作为 C 或 C++ 都是有效的。Shell 脚本编译并运行每个示例。另一个脚本在“最大警告”模式下编译一个简单的程序。为图 1 和图 2 的示例提供了预编译的汇编代码。

钻研

尝试一些涉及本专栏示例代码、开源项目和语言标准的练习。您将从研究高度简化的代码、真实的生产代码和只有语言律师才会喜欢的文档中获得不同的见解。

1. 重写图 1d 中的代码以测试溢出而不导致溢出。

2. 您可以从 Clang、Intel 或 Microsoft 编译器获得关于图 1 中错误的有用警告吗？

3. 编写几个未定义操作的小例子。确定检测每个操作的最简单编译器标志集。

4. Intel 汇编语言包括称为 UD、UD1 和 UD2 的特殊“未定义”指令。⁸ 您的编译器会发出它们吗？何时发出？

5. 考虑 C17² 或 C++17³ 标准中列举的未定义操作。原则上静态可检测的操作有多少？您的编译器检测到多少？有多少是静态检测不可能的（例如，由于不可判定性）？

6. 去开源项目中寻找错误。您一天能找到多少个错误？

7. 去钓鱼：Grep 源代码中可能在错误附近注释中出现的单词（例如，overflow、careful、check 等）。寻找视觉上的危险信号（例如，奇怪的缩进）。这些启发式方法是否找到了任何错误？

https://xkcd.com/45/

第 22 条军规：实现 `memmove()`

自 1989 年起，C 语言标准就强制要求使用 memmove() 库函数，该函数将 n 个字节从一个内存区域复制到另一个（可能重叠的）区域

void *memmove(void *dest, const void *src, size_t n);

其效果就像源数组首先被复制到一个临时数组，然后再从那里复制到目标数组一样。聪明的实现避免使用临时数组，而是直接“向前”或“向后”复制，具体取决于给定数组是否重叠以及如何重叠；请参阅 P.J. Plauger 的著作《标准 C 库》中的示例代码。

不幸的是，C 标准规定跨不同数组的指针算术和指针比较是未定义的。这种限制根植于 20 世纪 80 年代的 Intel x86 分段内存模型，它排除了以可移植的良好定义的 C 代码编写 memmove() 的明智方法。当给定数组不同时，Plauger 的代码执行未定义的比较，因此在技术上是不可移植的。

专家很容易触犯指针操作的限制。Steve Maguire 的著作《编写可靠的代码》提供了一个令人难忘的讽刺示例。与 memmove() 不同，当给定重叠数组时，标准 memcpy() 会产生未定义的行为。Maguire 展示了如何实现谨慎的 memcpy()，该函数试图通过使用断言来检查重叠来避免未定义的行为。不幸的是，断言中的指针算术和指针比较本身是未定义的。

Plauger 和 Maguire 的著作非常出色，并且他们前面提到的代码在一个理智的世界中将是无可指责的。C 语言标准委员会意识到了这种情况，并且已经考虑进行更改，例如，声明遥远的指针操作的结果是实现定义的，而不是未定义的。

致谢

谷歌 C++ 标准委员会成员 Hans Boehm 对早期草案提供了宝贵的反馈。

参考文献

1. Boehm, H.-J., Adve, S. V. 2011. You Don't Know Jack about Shared Variables or Memory Models. acmqueue 9(12); https://queue.org.cn/detail.cfm?id=2088916.

2. C17 语言标准 (N2176)。2017 年 11 月；https://web.archive.org/web/20181230041359/http://www.open-std.org/jtc1/sc22/wg14/www/abq/c17_updated_proposed_fdis.pdf。最官方的版本需要支付高昂的费用：https://www.iso.org/standard/74528.html。

3. C++17 语言标准 (N4660)。2017；https://web.archive.org/web/20170325025026/http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4660.pdf。尽管 C 和 C++ 标准使用的措辞不同，但它们在未定义行为方面采取了几乎相同的立场。

4. Clang 编译器用户手册。2021；https://clang.llvm.net.cn/docs/UsersManual.html。

5. Coverity Scan。2021。Synopsys；https://scan.coverity.com/。

6. GCC Bugzilla。2007。关于 GCC 优化的辩论，（所谓的）错误 30475；https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475。

7. Hoare, C. A. R. 1981. The emperor's old clothes. 1980 Turing Award Lecture. Communications of the 24(2), 75–83; https://doi.org/10.1145/358549.358561.

8. 英特尔公司。2020。Intel 64 and IA-32 Architectures Software Developer's Manual, Combined Volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D and 4. Order Number 325462-073US, 2640, Table A-1; https://software.intel.com/content/dam/develop/external/us/en/documents-tps/325462-sdm-vol-1-2abcd-3abcd.pdf.

9. Lattner, C. 2011. What every C programmer should know about undefined behavior. The LLVM Project Blog; https://blog.llvm.net.cn/2011/05/what-every-c-programmer-should-know.html.

10. Maguire, S. 1993. Writing Solid Code: Microsoft Techniques for Developing Bug-Free C Programs, 202. Microsoft Press。

11. Redis。2021；https://redis.ac.cn; https://github.com/redis/redis。

12. Stallman, R. M., et al. 2020. Using the GNU Compiler Collection. GNU Press; https://gcc.gnu.org/onlinedocs/gcc-10.2.0/gcc.pdf。

13. van der Linden, P. 1994. Expert C Programming: Deep C Secrets, page 15. Prentice Hall 。

14. Wang, X., Chen, H., Cheung, A., Jia, Z., Zeldovich, N., Kaashoek, M. F. 2012. Undefined behavior: What happened to my code? In Proceedings of the Asian-Pacific Conference on Systems, 9; https://dl.acm.org/doi/10.5555/2387841.2387850。

47. 维基百科。47；https://en.wikipedia.org/wiki/47_(number), https://web.archive.org/web/20060901185414/http://www.pomona.edu/welcome/trek/47trek.shtml。

TERENCE KELLY ([email protected]) 已经在理论和实践中与未定义行为作斗争，最近与罗切斯特大学的 Weiwei Gu 和 Vladimir Maksimovski 一起。像考虑洗礼的猫一样，作者期待提交针对其 Redis 最大警告构建发出的若干诊断的修复程序。

最初发表于 Queue vol. 19, no. 2—
在数字图书馆中评论本文

钻头

钻头