What Every C Programmer Should Know About Undefined Behavior #3/3

Saturday, May 21, 2011
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html
翻译：刘晓佳

在本系列的第一篇文章中，我们介绍了什么是C程序中的未定义行为，并且分析了在某些情况下，这种未定义行为能够使C语言比“安全”语言有更好的性能。在第二篇文章中，我们着重于那些未定义行为导致的，令人感到惊讶的Bug，和那些C程序员对此所持有的误解。本文，我们来看看编译器所面临的一些挑战，即为这些设计陷阱提供警告。此外在带走我们的惊讶的同时，还要讨论一些帮助我们赢得性能的LLVM和Clang提供的工具。

当基于未定义行为做优化时，为什么不能发出警告？

人们常常疑问，当编译器充分利用未定义行为做优化时，明明知道这种情况极有可能是用户代码的一个bug，为何不产生发出警告呢。这样做带来的挑战是1）很可能会产生太多没用的警告信息-因为当没有bug时这些优化总是执行,2)仅仅当人们需要时才发出警告是相当棘手的一件事，3）没有一种很好的方式告诉用户如何将一系列优化结合起来揭示优化的时机。让我们逐一解释：

1. 发出的警告很难真正有用
   我们来看个例子吧：当优化“zero_array”（系列第一部分中的）时，产生一个“优化器认为p和p[i]不是别名的”警告时没有多大用处的，即使这样无效的类型转换bugs是通过基于别名分析得到的。
   
   1. float *P;
   2. void zero_array() {
   3.    int i;
   4.    for (i = 0; i < 10000; ++i)
   5.       P[i] = 0.0f;
   6. }

   除了上述误判问题之外，优化器并没有足够的信息来产生一个合理的警告。首先，它致力于完全不同于C的一种代码的抽象化的表示形式（LLVM IR）。其次，优化器试图用循环外部的P来存储数据，却并不知道更高层面上，编译器的TBAA通过分析已经解决了指针别名查询。是的，这就是那些编译器使用者所抱怨的，但它确实很难解决。

2. 很难做到在人们需要时才发出警告
   Clang为一些简单而明显的未定义行为实现了警告，比如“x人们并不想从死代码中得到任何未定义行为的警告（这里还有另外一个例子）
   死代码有几种形式：以出人意料的方式进行展开的宏，cases语句无法运行到的部分（我们也曾抱怨某些情况下需要控制流分析来发现这一点）。基于C中Switch结构本来就没有适当的组织的事实，警告也没什么用。
   Clang中解决该问题的方式是增加了为处理“运行时行为”警告的功能，同时如果后面运行时我们发现这些块儿是不可执行的，这些警告将不会被通告。对于程序员来说，这就好比一场军备竞赛，因为总是会遇到一些我们未预料到的语法，而在前端这样做的后果就是，无法捕获到所有想要捕获的情况。
3. Explaining a series of optimizations that exposed an opportunity
   如果从前端产生好的警告有难度的话，我们可以从优化器来产生。这里产生有用的警告面临的最大问题是数据的追踪。编译器优化器完成了许多优化操作，每一个操作都修改了代码使得它们更加规范化，运行的更快。比如，如果内联器打算内联某个函数时，也就揭示了一个现在是优化“X*2/2”的时机。
   我提供了几个相对简单而完备的例子来阐释这些优化操作，它们生效的地方往往是宏实例化，内联，和其他一些抽象清除活动。事实上，确实人们一般不会犯如此糊涂的错误。对于这意味着为了将问题反馈给用户代码，它将不得不精确重现编译器是如何得到正在运行的中间代码的。我们需要像下面这样表达：
   
   1. 警告：三级内联之后（可能出现在文件的链接时间优化期间），将一般的子表达式消除，将这些事情放到循环之外来做且证明这13个指针不会重名后，我们发现一种未定义行为的情况。这可能是由于代码里有一个bug，也可能因为宏展开和内联操作和之前我们并没有证明是死代码的无法运行到的无效代码。

   不幸的是，我们并没有内部跟踪程序来产生这些警告，即使我们这样做了，编译器也没有一个很好的用户接口来向程序员传达这些信息。
   最终，未定义行为对优化器来说很有价值，因为它说“该操作无效-你可以假定什么也没发生过”。在“*P”的情况下告诉优化器P不能为空指针。在“NULL”情况下(常量传递或内联之后产生)，会告诉优化器该代码无法运行到。这里重要的是，因为无法解决中止问题，编译器无法知道代码是真正死掉了，还是被一系列优化所引起的一个bug。因为没有更好的方式来区分这两种情况，几乎所有的警告都是误报。

Clang处理未定义行为的方法

之前对于未定义行为的无能为力，你可能会很好奇Clang和LLVM如何来改善这种状况。我已经提及一部分内容:Clang静态分析器，Klee工程，和-fcatch-undefined-behavior标志，这类工具用来跟踪上面那些bug特别有用。但是这些工具被接受度很低，因此我们能做的是在编译器里直接提供这些功能来代替使用这些工具，即便编译器受限于没有动态信息和将花费更多的编译时间。

Clang改善代码的第一步是默认打开大量的警告提示。受过良好训练的开发者会加上“-Wall –Wextra”之类的选项来编译，而大部分人并不了解这些标志，或者嫌这样太麻烦。默认打开更多的警告更多时候会引起更多的bug。

第二步是为代码中很明显的未定义行为产生许多警告来捕获一般的错误（包括null的解引用，越界的移位，等等）。上面提及的这些警告，实际上貌似运行的很好。

第三步是LLVM优化器使得未定义行为不那么自由了。尽管标准认为任何未定义行为对程序没有约束效应，但这并没有什么用处，对开发者来说并不是什么可利用的友好行为。相反，LLVM优化器以一些完全不同的方式来处理这些优化：

1. 如果采取好的方式，某些未定义行为可以变换成隐含的陷阱操作。例如，在Clang中，该C++函数：
   
   1. int *foo(long x) {
   2.     return new int[x];
   3. }

   编译为X86-64的机器代码：

   1. __Z3fool:
   2.         movl $4, %ecx
   3.         movq %rdi, %rax
   4.         mulq %rcx
   5.         movq $-1, %rdi        # Set the size to -1 on overflow
   6.         cmovnoq %rax, %rdi    # Which causes 'new' to throw std::bad_alloc
   7.         jmp __Znam

   而GCC产生的机器代码是：

   1. __Z3fool:
   2.         salq $2, %rdi
   3.         jmp __Znam             # Security bug on overflow!

   区别在于Clang中我们决定花一些时间来阻止潜在的可能会引起缓存区溢出和漏洞利用（new运算符花费的代价比较昂贵，开销不被注意到）的整数溢出bug。至少在2005年GCC已经意识到这个问题了，但到目前为止还没有解决。

2. 针对一个未定义值的运算应当考虑产生一个未定义值而不是未定义行为。区别在于，未定义值不会格式化你的硬盘分区或者产生其它的无法预料的结果。有效的改进是当给定任何未定义值时四则运算产生同样的输出结果。比如，优化器假定“undef & 1”的结果是高位有一些0，最低位是未定义的。这意味((undef & 1) >> 1)，在LLVM中定义为0，而不是未定义的。
3. 动态执行未定义操作（比如有符号整数溢出）的四则运算会产生一个逻辑陷阱值，从而影响了基于它的后续计算，但这并不会破坏你的整个程序。这意味着从未定义操作后续的操作都可能被影响，但不会破坏你的整个程序。这也就是为何优化器最后要删除操作未初始化变量的代码。
4. 向NULL地址读写都转变成一个__builtin_trap()调用（该调用最终像x86上的“ud2”指令一样转变为自陷指令）。这一过程在优化的代码中一直进行（就像其它的转换如内联和常数传递），而且由于这些语句是很明显的无法运行的代码，我们用该转换来删除含有它们的语句块。

   从学术的角度讲这是正确的，我们很快发现人们确实偶尔解引用null指针，让落入下一个函数开头的代码执行 使得该问题很难理解。从性能的角度讲，揭示它最重要的方面在于殃及后续的代码。为此，clang把它转变成运行时trap：如果其中之一实际中可运行了，程序就立即停止，而且可以被调试。这样做的缺点在于通过这些操作和这些条件使代码变得膨胀起来。

5. 如果程序员的意图很明确（比如当P是一指向float类型的指针而去进行（int *）p操作）优化器会努力做正确的事。在很多情况下都很有用处，但实际上你并不想依赖它，有很多这样的例子，你可能认为它们是很明显的，不会经过很长一系列的变换。
6. 像第一部分描述的zero_array和set/call这样没有任何对用户的暗示就被优化的例子,优化很少会发生这种情况。我们这样做是因为没有任何有用的东西要说，真实的代码被优化器破坏的情况很罕见。

我们所能做的主要的改进是有关trap插入的。我认为增加一警告标志将非常有趣，每当产生一个trap指令时都会引起优化器警告。这对一些代码库来说也许是噪音，但对别的也许很有用。这里首要限制因素是使优化器产生警告的部件：除非调试信息打开，否则并没有有用的源码位置信息。

另一个更重要的限制因素是警告不会含有任何追踪信息能够解释某操作是三次展开一个循环，然后通过四层函数调用内联它的结果。顶多我们能指出原始操作的文件、行、列，这在某些情况下很有用，在另外一些情况下极其混乱。不管怎样，对于我们这并不是优先要实现的，因为a）这可能并不是很愉快的事情，b）默认不能够开启，c）有大量的工作要实现。

使用更安全的C方言（和其它选项）

如果你并不关心“终极性能”，最终的选择是使用不同的编译器标志来使用C中那些晦涩的语法消除未定义行为。比如，使用-fwrapv标志来消除有符号整数溢出导致的未定义行为（注意这并不会消除整数溢出这一安全缺陷）。-fno-strict-aliasing标志使基于重名分析的类型失效，因此你可以忽略这些类型准则。如果有需要的话，我们能增加一个标志到Clang中来把所有的局部变量归零，插入“与”操作在每次移位之前，等等。不幸的是，并没有一种易于处理的方式在不改变ABI和不损害性能的前提下来完全消除C中的未定义行为。另外如果这样作，那这就不是C语言，而是一种类似C但是却是不可移植的晦涩的类C语言。

如果说不在乎是否在编写写C的不可移植的晦涩代码，-ftrapv和-fcatch-undefined-behavior标志就是你的武器库中很有用的查找这种bug的武器。在调试模式下使用它们是一种很好的查找相关bug的方式。如果你要建立严格安全的应用，这些标志在你的产品代码中非常有用。尽管它们不能保证能找到所有的bug，但它们确实在寻找bug方面非常有用。

最后，一个现实的问题是C并不是一门安全的语言，尽管很流行很成功，但许多人并不理解这门语言是如何工作的。在1989年之前的几十年演化过程中，C从一种在PDP之上的底层系统编程语言逐渐演化变成一门试图靠打破人们的期待来提供合适性能的底层编程语言。一方面，这些C语言存在的"作弊行为"使得代码的性能更好。另一方面，它们也常常是最突然的，出现在最坏的时间把你弄个措手不及。

C远远不是一个可移植汇编语言。希望该讨论至少能够从编译器实现的角度来帮助理解C的未定义行为背后的问题。