ACM通信

实践

C不是一门低级语言

David Chisnall
美国ACM通信，2018年7月，第61卷第7期，44-48页
10.1145 / 3209212
评论(1)

在最近的Meltdown和Spectre漏洞之后，我们有必要花些时间看看根本原因。这两个漏洞都涉及处理器通过某种访问检查投机性地执行指令，并允许攻击者通过侧通道观察结果。导致这些漏洞的特性，以及其他一些特性，被添加进来是为了让C程序员继续相信他们是在用低级语言编程，而几十年来一直不是这样。

处理器供应商并不是唯一这样做的。我们这些从事C/ c++编译器工作的人也参与了其中。

计算机科学先驱Alan Perlis这样定义底层语言:

“如果一种编程语言的程序需要关注不相关的内容，那么它就是低水平的。”⁵

虽然这个定义适用于C语言，但它并没有捕捉到人们在低级语言中所需要的东西。各种各样的属性导致人们认为一门语言是低级的。把编程语言看作属于一个连续体，一端是程序集，另一端是到星际飞船的接口企业的电脑在另一边。低级语言“接近金属”，而高级语言更接近人类的思维方式。

对于“接近金属”的语言来说，它必须提供一个抽象机器，可以很容易地映射到目标平台公开的抽象。很容易争辩C是PDP-11的底层语言。他们都描述了一个模型，在这个模型中，程序是顺序执行的，在这个模型中，内存是一个平坦的空间，甚至递增前和递增后操作符都与PDP-11寻址模式整齐地排列在一起。

回到顶部

快)时模拟器

Spectre和Meltdown漏洞的根本原因是，处理器架构师试图构建的不仅是快速处理器，而且是暴露与pmp -11相同的抽象机器的快速处理器。这很重要，因为它允许C程序员继续相信他们的语言接近底层硬件。

C代码提供了一个基本串行的抽象机器(直到C11，如果不包括非标准供应商扩展，则是一个完全串行的机器)。创建新线程是一种众所周知的昂贵的库操作，因此处理器希望让它们的执行单元忙于运行C代码，依赖于ILP(指令级并行)。他们检查相邻的操作并并行发布独立的操作。这增加了大量的复杂性(和功耗)，允许程序员编写大部分顺序的代码。相比之下，gpu在没有任何这种逻辑的情况下可以实现非常高的性能，代价是需要显式并行程序。

对高ILP的追求是幽灵党和熔毁的直接原因。现代的英特尔处理器一次最多有180条指令在运行(与顺序C抽象机器形成鲜明对比，后者期望每个操作在下一个操作开始之前完成)。C代码的一个典型启发式是，平均每七个指令有一个分支。如果您希望让这样的管道从一个线程中充满，那么您必须猜测接下来25个分支的目标。这再次增加了复杂性;这也意味着错误的猜测会导致完成的工作被丢弃，这对功耗来说不是理想的。这种被丢弃的工作有明显的副作用，这是“幽灵党”和“熔毁”攻击可以利用的。

在现代高端核心上，寄存器重命名引擎是模具面积和功率的最大消耗者之一。更糟糕的是，在运行任何指令时，它都不能关闭或电源门控，这在一个晶体管很便宜但有动力晶体管是昂贵资源的黑暗硅时代显得很不方便。这个单元在gpu上是明显不存在的，那里的并行性同样来自多个线程，而不是试图从本质上的标量代码中提取指令级并行性。如果指令没有必须重新排序的依赖项，那么就没有必要重命名寄存器。

考虑C抽象机器的内存模型的另一个核心部分:平面内存。20多年来，情况并非如此。现代处理器通常在寄存器和主存之间有三级缓存，这试图隐藏延迟。

缓存,顾名思义,对程序员隐藏所以不可见c有效地利用缓存是最重要的方法之一,在现代处理器代码运行得很快,但这是完全隐藏的抽象机器,和程序员必须依靠了解缓存的实现细节(例如,两个值64 -字节对齐可能最终在同一个缓存线)编写高效的代码。

回到顶部

优化C

底层语言的一个常见属性是速度快。特别是，它们应该很容易转换为快速代码，而不需要特别复杂的编译器。一个足够聪明的编译器可以使一门语言变快的论点，是C语言的支持者在谈到其他语言时经常忽略的。

不幸的是，提供快速代码的简单转换并不适用于C语言。尽管处理器架构师为设计能够快速运行C代码的芯片付出了巨大的努力，但C程序员所期望的性能水平只能通过难以置信的复杂编译器转换实现。Clang编译器，包括LLVM的相关部分，大约有200万行代码。即使只是计算让C快速运行所需的分析和转换传递，加起来也有近20万行(不包括注释和空行)。

---

Spectre和Meltdown漏洞的根本原因是，处理器架构师试图构建的不仅是快速处理器，而且是暴露与pmp -11相同的抽象机器的快速处理器。

---

例如，在C语言中，处理大量数据意味着编写一个循环，按顺序处理每个元素。要在现代CPU上以最佳方式运行，编译器必须首先确定循环迭代是独立的。C限制关键字可以帮助这里。它保证通过一个指针进行的写操作不会干扰通过另一个指针进行的读操作(或者，如果发生了干扰，程序员很乐意看到程序给出意外的结果)。这些信息比Fortran之类的语言要有限得多，这也是C语言在高性能计算领域未能取代Fortran的主要原因。

一旦编译器确定循环迭代是独立的，那么下一步就是尝试向量化结果，因为现代处理器在向量代码中获得的吞吐量是在标量代码中获得的吞吐量的4到8倍。用于此类处理器的低级语言将具有任意长度的本机向量类型。LLVM IR(中间表示)恰恰具有这一点，因为将一个大的向量操作分割成较小的向量操作总是比构造更大的向量操作更容易。

此时优化器必须与C内存布局保证作斗争。C保证具有相同前缀的结构可以互换使用，并且它向语言公开结构字段的偏移量。这意味着编译器不能自由地对字段重新排序或插入填充以改进向量化(例如，将数组的结构转换为结构的数组或反之亦然)。对于底层语言来说，这未必是个问题，因为对数据结构布局的细粒度控制是底层语言的一个特性，但它确实使C语言的速度变得更加困难。

C语言还要求在结构的末尾填充，因为它保证数组中没有填充。填充是C规范中特别复杂的部分，与该语言的其他部分交互很差。例如，你必须能够比较两个结构体使用类型无关比较(例如，memcmp)，所以一个副本结构体必须保留其填充。在一些实验中，在某些工作负载上，有相当多的总运行时花费在复制填充上(填充的大小和对齐方式通常很别扭)。

考虑C编译器执行的两个核心优化:SROA(聚合的标量替换)和循环取消切换。SROA试图取代结构体(以及固定长度的数组)使用单个变量。这允许编译器将访问视为独立的，如果可以证明结果永远不可见，则完全省略操作。这在某些情况下有删除填充的副作用，但在其他情况下没有。

第二个优化是循环取消切换，它将一个包含条件的循环转换为两个路径都有循环的条件。这改变了流控制，与程序员知道在低级语言代码运行时将执行什么代码的想法相矛盾。它还可能导致C语言中未指定值和未定义行为的概念出现严重问题。

在C语言中，从未初始化的变量中读取的值是一个未指定的值，并且每次读取时允许为任何值。这很重要，因为它允许页面的惰性回收等行为:例如，在FreeBSD上malloc实现通知操作系统页面当前未使用，操作系统使用对页面的第一次写入作为不再使用的提示。读到新mallocEd内存最初可能读取旧值;然后，操作系统可以重用底层的物理页面;然后在下次写入到该页的不同位置时，将其替换为新的零页。从同一位置进行的第二次读取将得到一个零值。

如果使用了流控制的未指定值(例如，将其用作类中的条件)如果语句)，那么结果是未定义的行为:任何事情都被允许发生。考虑循环取消切换优化，这次是在循环最终被执行零次的情况下。在最初的版本中，循环的整个主体都是死代码。在未切换的版本中，变量上现在有一个分支，可以未初始化。一些死代码被转换为未定义的行为。这只是仔细研究C语义后发现的许多不合理的优化之一。

总而言之，让C代码快速运行是有可能的，但前提是要花费数千人的时间来构建一个足够智能的编译器，而且即使这样，也必须违反某些语言规则。编译器作者让C程序员假装他们在写“接近金属”的代码，但如果他们想让C程序员继续相信他们在使用一种快速的语言，就必须生成行为非常不同的机器代码。

回到顶部

理解C

底层语言的一个关键属性是程序员可以很容易地理解语言的抽象机器如何映射到底层物理机器。这在PDP-11上当然是正确的，在PDP-11中，每个C表达式都简单地映射到一个或两个指令。类似地，编译器直接将局部变量降低到堆栈槽中，并将原语类型映射到PDP-11可以本机操作的对象。

从那以后，C的实现变得越来越复杂，以维持C可以轻松映射到底层硬件并提供快速代码的假象。2015年一项针对C程序员、编译器作者和标准委员会成员的调查提出了几个关于C语言可理解性的问题。^3.例如，C允许实现向结构(但不向数组)插入填充，以确保所有字段对目标都有一个有用的对齐方式。如果你将一个结构归零，然后设置一些字段，填充位是否都为零?根据调查结果，36%的人确定他们会，29%的人不知道。取决于编译器(和优化级别)，可能是，也可能不是。

这是一个相当简单的例子，但是相当一部分程序员要么相信错误的东西，要么不确定。当引入指针时，C语言的语义变得更加混乱。BCPL模型相当简单:值就是单词。每个单词要么是一些数据，要么是一些数据的地址。内存是按地址索引的存储单元的平面数组。

相反，C模型旨在允许在各种目标上实现，包括分段的体系结构(其中指针可能是段ID和偏移量)，甚至是垃圾回收的虚拟机。C规范小心地限制了指针上的有效操作，以避免这类系统出现问题。对缺陷报告2601的回应包含了指针出处在指针的定义中:

允许实现跟踪位模式的起源，并将表示不确定值的那些与表示确定值的那些区别对待。它们也可能将基于不同起源的指针视为不同的，即使它们在位上是相同的。

不幸的是,这个词出处完全没有出现在C11规范中，所以由编译器写来决定它的含义。例如，GNU编译器集合(GCC)和Clang在转换为整数并返回的指针是否通过强制转换保留其来源上是不同的。编译器可以自由地确定两个指针的指向不同malloc结果或堆栈分配的比较总是不相等的，即使指针的位比较可能显示它们描述相同的地址。

这些误解并非纯粹的学术性质。例如，从有符号整数溢出(C中未定义的行为)和在空检查之前解引用指针的代码中可以观察到安全漏洞，这些代码向编译器表明指针不可能为空，因为解引用空指针在C中是未定义的行为，因此可以假定不会发生(CVE-2009-1897)。

鉴于这些问题，很难说程序员能够准确地理解C程序如何映射到底层架构。

回到顶部

想象一个非c处理器

针对Spectre和Meltdown的修复方案带来了巨大的性能损失，在很大程度上抵消了过去十年在微架构方面的进步。也许现在是时候停止让C代码变快了，而应该考虑编程模型在设计为快速的处理器上看起来会是什么样子。

我们有许多没有关注传统C代码的设计示例来提供一些灵感。例如，高度多线程芯片，如Sun/Oracle的UltraSPARC Tx系列，不需要太多的缓存来保持执行单元满。研究处理器²将这个概念扩展到大量的硬件调度线程。这些设计背后的关键思想是，有了足够的高级并行性，就可以挂起正在等待内存数据的线程，用其他执行单元的指令填充执行单元。这种设计的问题是C程序往往只有很少的忙线程。

ARM的标量向量扩展(SVE)和伯克利的类似工作⁴提供了程序和硬件之间更好的接口。传统的向量单元公开固定大小的向量操作，并期望编译器尝试将算法映射到可用的单元大小。相比之下，SVE接口希望程序员描述可用的并行度，并依靠硬件将其映射到可用的执行单元数量。从C中使用这个是复杂的，因为自动向量化器必须从循环结构中推断可用的并行度。从函数式的映射操作为它生成代码非常简单:映射数组的长度就是可用的并行度。

缓存很大，但它们的大小并不是造成其复杂性的唯一原因。的缓存一致性协议是现代CPU中最难做到既快速又正确的部分之一。所涉及的大部分复杂性来自于支持一种语言，在这种语言中，数据理所当然地既要共享又要可变。相比之下，考虑一个Erlang风格的抽象机器，其中每个对象要么是线程本地的，要么是不可变的(Erlang甚至对此进行了简化，每个线程只有一个可变的对象)。这种系统的缓存一致性协议有两种情况:可变的或共享的。要将软件线程迁移到不同的处理器，则需要显式地使其缓存失效，但这是一种相对不常见的操作。

不可变对象可以进一步简化缓存，以及使一些操作更便宜。Sun实验室的Project Maxwell指出，缓存中的对象和年轻代中分配的对象几乎是相同的集合。如果对象在需要从缓存中删除之前已经失效，那么永远不要将它们写回主存可以节省大量的电力。Maxwell项目提出了一个年轻一代的垃圾收集器(和分配器)，它将运行在缓存中，并允许内存快速回收。有了堆上的不可变对象和可变堆栈，垃圾收集器就变成了一种非常简单的状态机，在硬件上实现起来很简单，而且可以更有效地使用相对较小的缓存。

一个纯粹为了速度而不是为了在速度和C支持之间妥协而设计的处理器，可能会支持大量的线程，具有广泛的向量单位，并且具有更简单的内存模型。在这样的系统上运行C代码会有问题，因此，考虑到世界上遗留的大量C代码，它不太可能取得商业上的成功。

在软件开发中有一个普遍的误区，认为并行编程是困难的。这对艾伦·凯(Alan Kay)来说是一个惊喜，他能够教小孩子一种演员模型语言，他们用这种语言编写有200多个线程的工作程序。这对Erlang程序员来说是一个惊喜，他们通常编写带有数千个并行组件的程序。更准确地说，用类似C语言的抽象机器进行并行编程是困难的，而且考虑到并行硬件的流行，从多核cpu到多核gpu，这只是另一种说法，即C语言不能很好地映射到现代硬件。

相关文章
在queue.acm.org

跨语言互操作性的挑战
David Chisnall
https://queue.acm.org/detail.cfm?id=2543971

在苹果里发现不止一条虫子
迈克平淡
https://queue.acm.org/detail.cfm?id=2620662

为代码编码
弗里德里希·斯泰曼和托马斯Kühne
https://queue.acm.org/detail.cfm?id=1113336

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2018 ACM, Inc.

---

评论

---

显示1评论