[译] C 不是一门低层（low-level）语言（acmqueue, 2018）

Published at 2019-11-23 | Last Update 2021-01-31

译者序

本文翻译自 C Is Not a Low-Level Language，acmqueue Volume 16， issue 2（2018.04.30），原文副标题为 Your computer is not a fast PDP-11。作者 David Chisnall。

本文观点非常独特，甚至招来了老牌黑客 Eric S. Raymond（开源运动发起者之一，开源 领袖，代表作《大教堂和大集市》等）写了一篇长文作为回帖：Embrace the SICK。

由于译者水平有限，本文不免存在遗漏或错误之处。如有疑问，请查阅原文。

以下是译文。

---

• 译者序
• 1. 什么是低层语言？
  • 1.1 低层语言：定义
  • 1.2 抽象机器
• 2. 快速 PDP-11 模拟器
  • 2.1 C 抽象机器
  • 2.2 指令集并行（ILP）
  • 2.3 寄存器重命名引擎
  • 2.4 扁平内存和缓存
• 3. 优化 C
  • 3.1 编译器复杂度
  • 3.2 指令矢量化
  • 3.3 结构体填充
  • 3.4 SROA 和 loop unswitching（循环外提）
  • 3.5 未初始化变量、未定义行为和未定义值
  • 3.6 小结
• 4. 理解 C
  • 4.1 初始化结构体时，填充部分是否会被初始化？
  • 4.2 内存模型和指针
• 5. 设想一个 Non-C 处理器
  • 5.1 Sun/Oracle UltraSPARC
  • 5.2 ARM SVE
  • 5.3 缓存一致性、对象可变/不可变性、GC
  • 5.4 专门为速度设计的处理器
  • References

---

有必要花时间思考最近的 Meltdown 和 Spectre 漏洞产生的根本原因。

这两个漏洞都与处理器的预测执行（speculatively executing）相关：预测执行中的 的指令会经过某些类型的访问检查（access check），使得攻击者可以通过一个旁路 （side channel）来观测执行结果。

导致这些漏洞的特性（features），以及其他一些东西，助长了 C 程序员们的如下观念： 他们是在用一门低层语言进行编程（programming in a low-level language）。而事 实上，这种观念以及错了几十年了。

处理器厂商并不是唯一需要对此负责的。那些开发 C/C++ 编译器的人也助长了 这种错误观念。

1. 什么是低层语言？

1.1 低层语言：定义

计算机科学的先驱 Alan Perlis 给低层语言（low-level languages）下的定义是：

如果用一门语言编写的程序需要处理不相关的东西，那这就是一门低层语言。

“A programming language is low level when its programs require attention to the irrelevant.” [5]

虽然 C 语言适用于这个定义，但是，它并没有传达出到人们期望从一门低层语言中获得 什么。

很多语言属性（attributes）都会导致人们认为某种语言是低层语言。我们不妨想象这 样一个场景：各种编程语言排列在一个 continuum（连续统一体，任何相邻的两个实体都非 常相似，但最两端的两个实体却差异非常大。译者注）之上，continuum 的一端是汇编语 言，另一端是通往 Starship Enterprise 的计算机的接口（interface）。低层语言“靠近金 属”（close to the metal），而高级语言更靠近人类的思考方式。

1.2 抽象机器

一门语言要“靠近金属”，那它必须提供一种抽象机器（abstract machine），该机器能 够方便地映射到目标平台暴露的抽象（abstractions exposed by the target platform）。 基于以上分析，我们很容易得出这样一个结论：对于 PDP-11 来说，C 是一门低层语言。 二者都描述了这样一个模型：

• 程序是顺序执行的（programs executed sequentially）
• 内存空间是扁平的（memory was a flat space）

甚至 C 语言的前递增（++i）和后递增（i++）运算符都能一个萝卜一个坑地对应到 PDP-11 的不同寻址模式。

2. 快速 PDP-11 模拟器

Spectre 和 Meltdown 漏洞的根本原因是：处理器架构（processor architects）不仅在 试图构建快速处理器（fast processors），而且是与 PDP-11 暴露相同抽象机器的快 速处理器（fast processors that expose the same abstract machine as a PDP-11）。 这是其本质原因，因为它令 C 程序员们继续认为：这是一门靠近底层硬件的编程语言。

2.1 C 抽象机器

C 代码提供的是一个大部分情况下都是串行执行的（mostly serial）抽象机器（到了 C11 之后已经是一个完全串行的机器 —— 如果不包含任何非标准的厂商扩展的话）。

创建新线程是一个库操作（library operation），而且已知开销很大，因此处理器希望依 靠指令级并行（ILP，instruction-level parallelism）来使其执行单元（execution units）持续执行 C 代码。处理器会对相邻的操作（adjacent operations）进行检查，为 其中一些操作发射（issue）独立指令以使其并行执行。在继续允许程序员编写大部分情况 下都是顺序执行的代码（mostly sequential code）的前提下，这显著增加了处理器的复杂 度（和功耗）。与此相反，GPU 取得了极高的性能而没有涉及任何此类逻辑，而它的代价是 需要编写显式的并行程序。

2.2 指令集并行（ILP）

对高度的指令级并行（high ILP）的追求，是产生 Spectre 和 Meltdown 漏洞的直接 原因。

一个现代 Intel 处理器可以在同一时刻并行执行多达 180 条指令（与此形成强烈对比 的是顺序执行的 C 抽象机器，该机器期望每个操作执行完成之后，下一个操作才 会执行）。根据一些典型的统计，C 代码中平均每 7 条指令就会有一个分支。因此， 在单线程的情况下要让处理器的流水线（pipeline）达到饱和，那就需要猜测随后 的 25 个分支的目标。

180 / 7 ≈ 25 （译者注）

这再一次增加了复杂度；而且这也意味着，那些猜错的结果随后就直接丢弃了，从功耗的角 度来说也不是理想的方式。这些被丢弃的尝试有着可见的副作用，Spectre 和 Meltdown 攻击就是利用了这些副作用。

2.3 寄存器重命名引擎

在一个现代高端处理器上，寄存器重命名（register rename）引擎最消耗 die area 和功耗的。更糟糕的是，只要有任何指令正在执行，就无法将其关闭或降低功能（power gated），这在硅的灰暗年代 —— 也就是晶体管（transistors）非常便宜，而功率晶体管（ powered transistors）非常昂贵 —— 的年代非常不方便。

寄存器重命名单元在 GPU 上并不 存在，对于后者，并行依靠的是多个线程并行而不是尝试从本质上是标量的代码（ intrinsically scalar code）中提取指令级并行。

如果指令之间没有任何关联，无需重排 序（reorder），那寄存器重命名（register renaming）就不需要。

2.4 扁平内存和缓存

考虑 C 抽象机器的内存模型中另一个核心部分：扁平内存（flat memory）。在过去 的二十多年中，这一点其实也是不成立的。

现代处理器通常在寄存器和主存之间有三级 缓存（three levels of cache），其目的是为了隐藏延迟（hide latency）。

缓存（cache），如其名字所示，对程序员是隐藏的，因此对 C 是不可见的。有效地使用缓 存对于在现代处理器上快速地执行代码非常重要，抽象机器完全隐藏了缓存，但是 程序员必须知道缓存的实现细节（例如，两个 64 字节对齐的值可能会被放到同一 个缓存行）才能写出高效的代码。

3. 优化 C

人们普遍认为，低层语言的一大优势是快（fast）。尤其重要的一点是，将这些语言转换成 能够快速执行的代码，应该不需要特别复杂的编译器。在讨论其他一些语言时，有些人会认 为一个足够优秀的编译器可以使得一门语言变得快速，但当讨论到 C 时，这一点经常 不再成立。

3.1 编译器复杂度

通过简单的转换（simple translation）就能变成快速代码（fast code）对 C 是 不成立的。

尽管处理器架构师在设计能够快速运行 C 代码的芯片上投入了艰苦卓绝的 努力，但 C 程序员期望的性能水平并非来源于此，而是来自复杂地难以想象的编译器变换（ compiler transforms）。Clang 编译器，连同 LLVM 中相关的部分，大概有 200 万行代码 。即使只统计其中和快速执行 C 相关的分析和变换代码，也有将近 20 万行（不包 含注释和空行）。

3.2 指令矢量化

例如，在 C 中，处理大量数据通常是写一个循环，在循环中顺序地处理每个元素。

要在现代 CPU 上最优地执行这段代码，编译器必须首先判断每次迭代是不是独立的。这里 C 的 restrict 关键字可能会排上用场。restric 保证一个指针的写操作不会与另一个 指针的读操作彼此产生任何影响（或者如果有，程序就会得到无法预期的结果）。相比于 Fortran 这样的语言，C 中这类信息太不通用了（far more limited），这也是为什么 C 无法在高性能计算领域取代 Fortran 的一个重要原因。

编译器确定循环的每次迭代都是独立的之后，下一步就是尝试对结果进行向量化/矢量化（ vectorize the result），因为相比于标量代码（scalar code），现代处理器的矢量代码 （vector code ）可以取得四倍到八倍的性能。为这种处理器设计的低层语言（low-level language）能够支持任意长度的原生矢量类型。LLVM IR（intermediate representation） 就是一个例子，将一个大矢量的操作拆分成很多小矢量，永远要比构建大矢量操作简单。

3.3 结构体填充

但在这里，优化器必须首先保证 C 的内存布局。

C 保证 structures with the same prefix（同一结构体的不同引用？）可以无差别的使用 ，而且它将结构体字段的偏移（offset）暴露到语言中。这意味着编译器无法随意对结构体 字段进行重排序或者插入填充来提高矢量性（例如，将一个数组结构体转换成一个结构体数 组，或者相反）。对于低层语言来说，这些不一定是一个问题，因为对于低层语言来说，对 数据结构布局的细粒度控制属于特性（feature），但对于 C 来说，这会导致生产快速代码 更加困难。

C 还需要对结构体的结尾处进行填充，因为它不保证对数组进行填充。在 C 规范中，填 充是一个特别复杂的部分，而且与这门语言的其他部分衔接地非常差。例如，要保证程 序员能够用类型无关的（type-oblivious）方式（例如，memcpy）比较两个结构体变量 ，因此结构体的拷贝必须要保留它的填充。在一些实验中发现，对于某些 workload，总运 行时的相当一部分都花在拷贝这些填充上（通常都是一些 size 和对齐都很糟糕的结构体）。

3.4 SROA 和 loop unswitching（循环外提）

考虑 C 编译器的两个核心优化：

1. SROA（scalar replacement of aggregates，聚合体标量替换）
2. loop unswitching（循环外提）

SROA 尝试将结构体（以及固定长度数组）替换为独立变量。这使得编译器能够将对结 构体不同字段的访问变成独立的，甚至，如果能证明对结果没有影响，那可以完全去掉去结 构体的访问。在某些情况下，这项优化会涉及删除填充，但并非所有情况。

第二项优化，循环外提，将一个包含条件判断的循环转换成一个包含循环的条件判断 —— 在 if 和 else 中都复制一份这个循环。这改变了流的控制（flow control）， 与程序员所假设的低层语言执行方式相违背。另外，考虑到 C 的未定义值（unspecified values）和未定义行为（undefined behavior）概念时，这还会产生严重的问题。

3.5 未初始化变量、未定义行为和未定义值

在 C 中，读取未初始化变量（uninitialized variable）得到的是一个未定义值（ unspecified value），并且每次读取时，这个值可以是任意的。

这一点非常重要，因为它 使得惰性回收页面（lazy recycling of pages）之类的行为成为可能：例如在 FreeBSD 中 ，malloc 的实现通知操作系统这些页面当前是未使用的，而操作系统向这些页面的第一 次写操作则宣告这些页面开始被使用了。对新分配出来的内存（newly malloced memory） 的读操作可能会读到老数据（old value）；之后，操作系统可能会重用底层的物理页；然 后，对这个页面的某个不同位置的一次写操作会将这个页面初始化为零（zeroed page）。 从同一位置的第二次读操作读到的就是零值（zero value）。

如果流控制（flow control）中使用了一个未定义值（例如，if 语句中的条件变量 ），那结果将是未定义行为（undefined behavior）：任何行为都可能会发生（anything is allowed to happen）。考虑循环不会被执行（或者说，执行 0 次）情况下的循环外提优 化：

• 没有优化的版本中，整个循环体都是死代码
• 循环外提优化之后，在循环的外面会有一层条件判断，而这个值可能是未初始化的。原来 的死代码（dead code）现在变成了未定义行为（undefined behavior）代码

只要深入查看 C 的语义，就会发现还有很多的优化会产生类似的错误结果。

3.6 小结

最后总结一下：让 C 代码快速地运行是可能的，但需要为此投入几千“人·年”（ person-year）的精力开发一个足够智能的编译器 —— 而且即便如此，还得包含一些与 C 语 言规范不兼容的（violate）实现。

如果编译器开发者想让 C 程序员继续相信自己使用的是 一门快速语言，那他们就需要使后者继续相信自己是在编写“靠近金属”的代码，但同时编 译器又必须生成行为与此迥异的代码。

4. 理解 C

低层语言的最大特点之一是：程序员能够轻松地理解这门语言的抽象机器是如何映射到底 层的物理机器的。

在 PDP-11 上，这一点显然是成立的，每个 C 表达 式都能够映射到一条或两条指令。类似地，编译器能够直接将局部变量（local variable）放到栈槽（stack slot）上，以及将 primitive 类型映射成 PDP-11 能够原 生操作的东西。

自此之后，为了维持 C 能够轻松地映射到底层硬件以及 C 能够产生快速代码 的幻象，C 的实现开始变得越来越复杂。

4.1 初始化结构体时，填充部分是否会被初始化？

2015 年一份针对 C 程序员、编译器开发者和标准委员 会成员的调查揭示了几个对 C 的理解的问题。

例如，C 允许实现中对结构体插入填充（但 不允许对数组）来保证所有字段在目标平台上都有良好的对齐。如果用 0 初始化结构体 内存，然后设置某些字段的值，那填充的比特也会被 0 初始化吗？

根据调查的结果，36%的被调查者认为会，29% 的回答不知道。答案是，这和编译器的实现 （以及优化级别）相关，有的会被初始化，有的不会。

这是一个非常细节的例子，但很大一部分程序员对此的理解要么是错的，要么是不知道。

4.2 内存模型和指针

当介绍指针时，C 的语义会更加令人困惑。BCPL 模型非常简单：values are words。

1. 每个 word 要么是一段数据，要么是一段数据的地址
2. 内存是一段扁平的存储单元数组（flat array of storage cells），用地址索引（ indexed by address）

相比之下，C 模型在设计中允许在不同平台上实现，包括 segmented architectures （其中一个指针可能是一个 segment ID 和一个 offset），甚至带垃圾回收 的虚拟机。C 规范中仔细严格地限制了指针操作，以避免在这类系统上发生问题。作为对 Defect Report 260 [1] 的回应，指针的定义中引入了 pointer provenance（来源）的 概念：

“Implementations are permitted to track the origins of a bit pattern and treat those representing an indeterminate value as distinct from those representing a determined value. They may also treat pointers based on different origins as distinct even though they are bitwise identical.”

不幸的是，“provenance” 一词并未出现在 C11 规范中，因此其只能由编译器的实现来 决定。例如，如果一个指针先转换成整形再转换回指针，那最后这个指针是否还保留了它的 provenance？GCC (GNU Compiler Collection) 和 Clang 对此的实现就是不同的。编译器 完全决定了两次不同的 malloc 或栈分配（stack allocations）得到的结果是不同的 ，即使按位对比（bitwise comparison）显式这两个指针指向的是同一个地址。

这个误解本质上并不完全是学术性质的。例如，在有符号整形溢出（signed integer overflow，这在 C 中是未定义行为）和没有检查指针是否为空就解引用（dereferenced a pointer before a null check）的代码中发现了安全漏洞。对于后者（CVE-2009-1897）， 代码中没有检查指针是否为空就对其解引用，这给编译器的暗示就是这个指针不可能为空，因为在 C 中空指针的解引用是未定义行为，因此不可能会发生。

以上漏洞的修复。译者注。

diff --git a/drivers/net/tun.c b/drivers/net/tun.c
index b393536..027f7ab 100644
--- a/drivers/net/tun.c
+++ b/drivers/net/tun.c
@@ -486,12 +486,14 @@ static unsigned int tun_chr_poll(struct file *file, poll_table * wait)
 {
 	struct tun_file *tfile = file->private_data;
 	struct tun_struct *tun = __tun_get(tfile);
-	struct sock *sk = tun->sk;
+	struct sock *sk;
 	unsigned int mask = 0;

 	if (!tun)
 		return POLLERR;

+	sk = tun->sk;
+
 	DBG(KERN_INFO "%s: tun_chr_poll\n", tun->dev->name);

鉴于以上这些问题，很难说程序员充分理解了他们的 C 程序将如何映射到底层架构。

5. 设想一个 Non-C 处理器

Spectre 和 Meltdown 漏洞的修复方案会导致严重的性能下降，抹平了过去十年微架构领 域的一大部分进展。

也许现在是时候停止继续让 C 代码变快的努力了，而应该思考： 如果要在处理器上设计一个快速的编程模型，那这个模型应该是什么样子？

已经有很多没有遵循传统的 C 代码的设计例子，它们可以提供一些 inspiration。

5.1 Sun/Oracle UltraSPARC

高度多线程的芯片（比如 Sun/Oracle 的 UltraSPARC)，不需要大量缓存来使它们的执行单 元保持饱和。研究型处理器 [2] 已经将这种概念扩展到数量非常庞大的的硬件调度线程。

这种设计背后的核心理念是：只要有足够的高级别并行度（high-level parallelism）， 就可以将那些等待从内存读取数据的线程挂起，然后用其他线程的指令来填充执行单元。

这种设计的问题是，可能导致 C 程序产生几个繁忙线程（busy threads）。

5.2 ARM SVE

ARM 的 SVE (Scalar Vector Extensions) —— 以及 Berkeley 的类似工作 [4] —— 提供了另一种 程序和硬件之间更好的接口的尝试。

传统矢量单元暴露几种固定大小（fixed-sized）的矢量操作， 期望编译器将算法映射到几种可用的单位大小。相比之下，SVE 接口由程序员描述可用的并 行级别，依赖硬件将它们映射到可用的执行单元。在 C 中使用这种接口比较复杂，因为自 动向量化器（autovectorizer ）必须从循环结构中推断可用的并行级别。但在函数式风格 的语言中用 map 操作产生这种代码非常容易：映射之后的数组长度就是可用的并行程度。

5.3 缓存一致性、对象可变/不可变性、GC

缓存很大，但大小并不是它们如此复杂的唯一原因。

缓存一致性协议是现代 CPU 最难的部分，因为要同时保证缓存的快速和正确。这里涉 及的大部分复杂度来自于要支持这样一种语言：无条件地期望数据同时是共享的和可变的 （shared and mutable）。

作为对比，考虑 Erlang 风格的机器，其中的每个对象要么是线程私有的（thread-local），要么是不可变 的（immutable ）（实际上 Erlang 的模型更加简化：每个线程只有一个可变对象）。 为这样的系统设计一套缓存一致性协议需要考虑两方面：可变性和共享性。一个软件线程从 一个处理器迁移到另一个处理器需要将它的缓存显式地置为无效，但这是一个相对不寻常的 操作。

不可变对象能够进一步简化缓存，并且可以使几种操作开销更低。Sub Lab 的 Project Maxwell noted that the objects in the cache and the objects that would be allocated in a young generation are almost the same set. 如果对象在需要被驱逐出缓存之前就无效了，那就无需将它们写回内存，这 可以节省大量的功耗。Project Maxwell 提出了一种 young-generation garbage collector (and allocator)，可以在缓存中运行，使得内存可以被快速回收。有了存储不 可变对象的堆和一个存储可变对象的栈（mutable stack），GC 就变成了一个非常简单的状 态机，很容易在硬件上实现，最终会使得缓存更新，并且使用更加高效。

5.4 专门为速度设计的处理器

一个专门为速度 —— 而不是为了在速度和支持 C 之间取得折中 —— 而设计的处理器，可能 会：

• 支持大量的线程
• 有很宽的向量单元（wide vector units）
• 有更简单的内存模型

在这样的系统上执行 C 代码会有问题，考虑到世界上既有的大量 C 代码，这样的处理器 在商业上不太可能会取得成功。

在软件开发领域流传着一个神话：并行编程很难。

Alan Kay 对此可能会很吃惊，因为他能够用一种 actor 模型语言来教很多小孩编程，而且 他们已经写出了已经在使用中的、包含 200 多个线程的程序。Erlang 程序员对此也会很吃 惊，因为他们已经习惯了编程几千个并行组件的程序。因此，更准确说法应该是：用那些有 着和 C 类似的抽象机器的语言进行并行编程很难，而且考虑到如今流行的并行硬件，从多 核 CPU 到众核 GPU，也从另一方面说明了 C 并不能很好的映射到现代硬件。

References

1. C Defect Report 260. 2004; http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm.
2. Chadwick, G. A. 2013. Communication centric, multi-core, fine-grained processor architecture. Technical Report 832. University of Cambridge, Computer Laboratory; http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-832.pdf.
3. Memarian, K., Matthiesen, J., Lingard, J., Nienhuis, K., Chisnall, D. Watson, R. N. M., Sewell, P. 2016. Into the depths of C: elaborating the de facto standards. Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation: 1-15; http://dl.acm.org/authorize?N04455.
4. Ou, A., Nguyen, Q., Lee, Y., Asanović, K. 2014. A case for MVPs: mixed-precision vector processors. Second International Workshop on Parallelism in Mobile Platforms at the 41st International Symposium on Computer Architecture.
5. Perlis, A. 1982. Epigrams on programming. ACM SIGPLAN Notices 17(9).