EA Blog

原文地址：
What Every C Programmer Should Know About Undefined Behavior #1/3
原作者：Chris Lattner

导言

人们发现，使用LLCM开启优化选项编译代码有时会生成SIGTRQAP信号，如果你的代码在x86架构的系统上被编译，那么LLVM在会产生“ud2”信号，这与__builtin_trap()生成的指令相同，这其中存在的几个问题都与C代码中的未定义行为和LLVM对其的处理方式有关。

这篇博客（三篇中的第一篇）试图解释其中的一些问题，以便你可以更好的理解这其中的权衡和复杂性，也许也能学到更多有关于C语言的黑暗面。（怎么翻，”坏的一面“？）因为事实证明C语言并不像许多有经验的C程序员，尤其是那些关注底层程序编程和运行的人所想的那样，是一门“高级汇编语言”，C++和Objective-C也在C语言中直接继承了许多问题。

未定义行为的介绍

LLVM IR和C语言都有“未定义行为”的概念。未定义行为是个相当广泛的话题，有许多细节需要我们注意。我所找到的最好的介绍未定义行为的文章是JoHn RegeHr’s的一篇博客。这篇文章简明扼要的说明了C语言中许多看起来合理的事情实际上都隐含着未定义行为，这是常见的程序错误来源。C语言中的任何未定义行为都得会使编译器编译代码和程序运行时做出完全意想不到的事情，甚至可能造成相当严重的后果。再次强烈推荐JoHn RegeHr’s的文章

C语言中存在未定义行为是因为C语言的设计者希望C能够成为一种极为高效的底层编程语言。相反，许多像Java这类的“安全”语言则避免了未定义行为，因为它们希望自己的语言能在不同的功能实现中抽象出安全可重复的语句，哪怕要牺牲部分的性能。虽说这两种方法都不是什么“正确的目标”，但如果你是一个C程序员，你真的应该了解什么是未定义行为。

在深入讨论细节之前，值得简要阐述编译器如何普遍的编译出性能良好的c程序，从上层视野来看，编译器通过以下方式生成高性能的程序：a.优化基础算法的性能，比如寄存器的分配和调度；b.掌握一些魔法技巧，比如窥孔优化（peephole optimizations[1]），循环变换（Loop transformations[2]）等，并在合适的时候使用它们；c.善于消除不必要的抽象，例如c中的宏重复，c++中的函数内联和消除临时对象等；d.不出差错（不要改变程序本来的功能）。

虽然以上任何一种优化听起来都微不足道，但事实证明，在关键循环体中或者某些复用率极高的代码块中节省哪怕一个时钟周期都可能使程序运行效率提高10%或者使其耗电量减少10%。

C中未定义行为的优点，带实例

在我们正式开始深入了解未定义行为不为人知的一面和LLVM作为C编译器时的策略和行为之前，我认为先讨论几个有关未定义行为的特定程序例子，以及它们如何通过未定义行为获得比在Java这类安全语言中更加优良的性能会很有帮助。你可以将这看作是一种未定义行为给予的优化机会，也可以看成是一种要求更多的检查和保护机制的“开销”（因为未定义行为定义化需要引入更多的操作，检查和保护机制，这是一种开销）。虽然编译器中的优化器有时可以消除其中一些开销，但要在更加普适的情况下这样做，就需要解决停机问题和许多其他“有趣的挑战”

值得指出的是，Clang和GCC对一些C标准未定义的行为做了约束，而我接下来要讨论的例子在C标准和上述编译器中都被视作未定义行为。

**使用未初始化的变量：**通常认为使用未初始化的变量是C程序中bug的来源之一。有许多工具可以捕捉到这种错误，从编译器警告到静态和动态分析器。但使用未初始化的变量可以提高程序的性能，因为不需要再变量进入其作用域时将他们全部初始化。对于大多数标量变量（整形，浮点数，字符，指针等基本数据类型），初始化实际上不会造成程序多大的开销，但是对栈数组和malloc分配的内存进行初始化会产生存储空间的memset操作，这个操作的开销很大，一是覆盖的内存空间可能相当大，特别是在这个内存空间已被完全覆写的情况下，二是在内存不足的情况下，可能会导致其覆盖一些我们想保存的内容甚至直接导致出错。

**有符号整形溢出：**如果对一个有符号整形（例如int类型）进行算数运算时造成溢出，那么结果是未定义的。例如：”INT_MAX+1”不保证等于”INT_MIN”.这种未定义允许编译器进行某称类型的优化，这些优化能给一些代码带来很大的性能优化。比如：”X+1>X”可以被优化为”TRUE”,”X*2/2”可以被优化为”X”,因为整形溢出是未定义的，这就意味着编译器既可以假设溢出是不存在的，又可以自己假设溢出之后应该是什么值，来进行一些特定的优化。尽管这些优化看起来微不足道，但是这些优化通常会在内敛和宏展开中发挥作用。这种优化的一个重要的应用是在“≤”循环中，例如：

for(int i = 0; i <= N; i++){……}

在这个循环中，由于整形溢出是未定义的，编译器可以直接假设循环将恰好进行N+1次，从而穷用广泛的循环优化。另一方面，如果整形溢出并非是未定义的，而是被定义为回绕（即从INT_MAX回到INT_MIN时），那么编译器必须假设该循环有可能无限执行（在N=INT_MAX时），基于编译器不能修改程序原本的功能的原则，编译器必须禁用掉这些重要的循环优化。这种优化在64位的平台上影响颇深，因为许多代码都使用“int”作为归纳变量（induction variables [3]）。

值得注意的是，与有符号整形不同，无符号整形的溢出被定义为2的补码回绕溢出（也就是从最大值回绕至最小值），因此C程序员可以放心的假设并利用这个特性。将有符号整形的溢出定义为回绕溢出的代价是某些类型的优化将会失效（例如在64位目标平台上，在循环中存在大量的符号位扩展操作）。Clang和GCC都接受使用”-fwrapv”标志来强制将有符号整形溢出视为被定义的行为（除了INT_MIN除以-1的操作）。

**超量位移：**比如将一个uint32_t类型变量左移或者右移32位或者更多位的操作是未定义的。我猜测这个行为未定义的原因是不同的CPU在进行超量位移操作时会有不同的行为。例如x86处理器将32位整形变量的移位量截断为5位，也就是进行一个%32的操作，因此32位位移相当于0位位移;而PowerPC上的32位整形的移位被截断到6位，因此32位位移的结果总为0。由于这些硬件差异，C语言对于这种行为没有定义(因此如果你真的在PowerPC上移32位可能会格式化你的硬盘，并且不保证最终结果是0)。定义这个未定义行为的开销是编译器需要生成一个额外的指令（例如and指令），这将使它们在移位指令上的开销是同规格CPU的两倍。

**野指针的解引用和数组越界访问：**解引用随机指针（Ramdom pointers[4]）和越界访问数组是C语言程序种常见的错误。为了消除这种未定义行为，每个数组访问都必须进行范围检查并修改ABI，以确保范围的合法性。野指针的解引用和数组越界访问对于许多应用程序来说代价非常高昂，同时也会破坏每个现有C库的二进制兼容性。

**解引用空指针：**与普遍认识相反，C语言种解引用一个空指针是未定义行为，它既不会被定义为陷阱函数以便操作系统将其作为异常处理，也不会被定义为一个指向0地址的指针，即使你将一个页面的地址定位0，空指针也不指向它。这完全违反了禁止解引用野指针和将空指针作为哨兵的规则。空指针解引用的未定义行使编译器可以进行广泛的优化。与之相比，Java不允许编译器进行任何有副作用的对编译器无法证明非空的指针的解引用的操作。这对于调度和其他优化产生了很大的负面影响。在C语言种，空指针的未定义性是的许多简单的标量优化可以通过宏扩展和内敛的方式产生效果。

如果你使用的是LLVM编译器，那么你可以使用volatile关键字修饰空指针并解引用该野指针来使你的程序崩溃，如果你希望的话。因为volatile可以使空指针不被编译器优化。目前还没有一种标准或者编译器选项使空指针的访问被视为有效的访问或者使编译器被告知空指针的访问是被允许的。

**违规类型转换：*在C语言种，将一个int类型的指针强制转换位float类型的指针并对其进行解引用操作（将int类型的值视为float类型的值进行访问）是未定义行为。C语言要求这种类型转换必须通过memcy函数进行，而非使用指针强制转换，如果你不想导致未定义行为的话。这种类型转换的规则比较复杂，涉及到char,向量、联合等多种情况的处理等等，我并不想在此过深的探讨它。

这种未定义行为使得编译器可以进行“基于类型的别名分析”(Type-Based Alias Analysis ,TBAA),从而进行广泛的内存访问优化，显著提高生成代码的性能。例如，这个规则运行Clang将以下函数：

float *P;
void zero_array(){
	int i;
	for(i=0;i<10000;++i){
		P[i] = 0.0f;
	}
}

优化为”memset(P,0,40000)”。这个优化也可以使得很多加载操作可以被提到循环外，消除常见的公共子表达式等。这种未定义行为可以通过编译选项“-fno-strict-aliasing”来禁用，从而阻止编译器进行TBAA。当添加这个选项时，Clang必须将这段代码编译成10000个4字节的存储操作，因为它必须假设所有的存储操作都可能改变P的值，比如：

int main(){
	P = (float*)&P;
	zero_array();
}

像这种类型滥用的情况是比较少见的，因此C标准委员会认为，与其能够带来的性能优化相比，合理的类型转换下的未预料结果是可接受的。与之相比，由于不允许进行不安全的指针类型转换，Java可以获得基于类型优化的好处却不会受到这些缺点的影响。

总之，我希望这能是你意识到C语言中的未定义行为能够带来很多性能上的优化。包括序列点违规（sequence point violations[5]）例如“foo(i,++i)”,多线程程序中的竞争条件（race conditions in multithreaded programs[6]）违反restrict（violating 'restrict[7]），除以0等等。

在下一篇文章中，我们将讨论C语言的未定义行为在非唯性能追求的程序中的可怕，在最后一篇中，我们将讨论LLVM和Calng是如何处理未定义行为的。

[1] peephole optimizations是一种常见的编译器优化技术，它尝试在一段代码块中寻找可以被替换简化的部分并进行相应的优化，比如合并多个指令，执行同等效果的，效率更高的指令，删除无用的指令等。

[2]Loop transformations也是一种编译器优化计数，它尝试通过改变循环结构或者改变循环体执行顺序来优化程序的性能，包括Loop fusion循环合并，Loop distribution循环分解,Loop interchange循环交替，Loop unrolling循环展开，Loop tiling循环分块等

[3]induction variables指在循环中用于计数或者迭代的变量

[4]Random pointer通常指指向位置或者不确定内存位置的指针,如NULL指针、指向已释放内存的指针等

*[5] sequence point violations指一个语句中有着未定义执行顺序的多条表达式*

*[6]race conditions in multithreaded programs指由多个线程的程序尝试同时访问共享资源，最终结果使不确定的*

[7]violating 'restrict’,指通过restrict限定的指针存在别名，可能会造成一些不可预知的错误

#2/3

在上一篇文章中，我们讨论了什么是未定义行为，以及它如何允许C编译器较之其他“安全”语言做出更好的性能优化。本篇文章将讨论C程序的“不安全”之处。解释一些未定义行为可能导致的意外影响。在第三部分中，我们将讨论友好的编译器可以采取那些措施来减少这些意外，即使它们并没有义务这样做。

我愿意将这一节的标题定为“为什么C程序员总是害怕未定义行为”

相互作用的编译优化会导致意外的结果

现代编译优化器有许多顺序执行的优化，有时也会进行迭代，并随着时间与编译器一同变化（例如新版本发布）。并且，不同的编译器基本都有着大不相同的优化器。因为各个优化的执行顺序不同，先前生效的优化经常会导致意外的结果。

我们来看一个简单的例子（根据一个在linux内核中发现的可利用bug简化而来）：

void contains_null_cheak(int *P){
	int dead = *P;
	if(p==0) return;
	*P = 4;
}

在这个例子中，代码“清晰的”检查了P是否是空指针。如果编译器先执行“无效代码清除”(Dead Code Elimination[1]),再执行“冗余与空指令消除”（Redundant Null Check Elimination[2]）,那么我们将看到代码进行如下变化：

void contains_null_cheak(int *P){
	//int dead = *P; delete
	if(p==0) return;
	*P = 4;
}

然后:

void contains_null_check_after_DCE_and_RNCE(int *P) {
  if (P == 0)   // 指针被保留，程序正常运行
    return;
  *P = 4;
}

在这种情况下，代码能够正常运行，但是，如果编译器先运行“RNCE”，再运行”DCE”。那么情况就会变成这样：

void contains_null_check_after_RNCE(int *P) {
  int dead = *P;
  if (false)  // 上面对P进行过解引用，因此编译器可以认为P不可能是一个空指针
    return;
  *P = 4;
}

然后无效代码清除优化开始工作：

void contains_null_check_after_RNCE_and_DCE(int *P) {
  //int dead = *P; delete
  //if (false)
  //  return;
  *P = 4;
}

对很多程序员来说，编译器对空指针检查代码的删除是很意外的事情，然后它们大概会认为这是编译器的bug😅,然而先运行RNCE再运行DCE和先运行DCE再运行RNCE在C标准中都是完全合法的，并且这两种优化都对各种应用程序的性能非常重要。

虽然这个例子是人为且简单的，但这种情况在内联中经常发生，内联函数会给编译器相当多的优化机会。这意味着如果优化器决定内联一个函数，各种本地优化就会启动，从而改变代码的行为。这在标准上是完全有效的，并且在实践中对性能非常重要。

未定义行为和安全不搭嘎

C编程语言系列被广泛的用于各种高度要求安全性的代码，比如内核，setuid守护程序(setuid daemons[3])，web浏览器等等。这类代码经常面临着恶意输入和所有可能导致漏洞的bug。

C语言有着易于理解代码运作过程的优点。然而，未定义行为会破坏这个优点。毕竟，大多数程序员会认为上面提到的“contains_null_check”函数应该会进行空指针检查。虽然这个例子不算相当可怕（如果传递了一个空指针，带啊吗可能会在为空指针指向地址赋值时崩溃，但这相对好调试），但是也一样与许多看起来非常合理的C代码实际上是完全无效的。这个问题已经影响了许多项目（包括Linux内核、OpenSSL、glibc等等），甚至让CERT(Computer Emergency Response Team[4])发布了针对GCC的漏洞通告(尽管我认为，所有利用未定义行为进行优化的C编译器都存在这个问题，而绝不仅仅是GCC)。

让我们看一个示例代码：

void process_something(int size) {
  // Catch integer overflow.
  if (size > size+1)
    abort();
  ...
  // Error checking from this code elided.
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

这段代码在开头检查了传入size的大小已确保malloc开辟的内存空间足够容纳从文件中读取的数据（因为数组末尾需要加上空终止字符），如果发生整形溢出则会退出。然而，这正是我们之前提到过的编译器优化示例。这意味着编译器可以完全合法的将这段代码转换为：

void process_something(int *data, int size) {
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

这个示例告诉我们，在64位平台上编译时，当”size”等于INT_MAX时，很可能导致一个可利用的安全漏洞。并且这个漏洞是十分隐蔽可怕的：代码审计员阅读代码时很大可能会认为溢出检查在正常运行，如果测试代码的人员没有专门测试过溢出问题，他们也不会发现这个漏洞。代码看似正常安全的运行，直到有人开始利用这个漏洞。幸运的是，这种情况下的修复很简单，只需要使用“size == INT_MAX”或者类似的方法就能够修复。