并发编程：乱序执行的那些事儿

2023-07-15 14:37 作者:小林家的垃圾王R 0人读过 | 我要投稿

并发编程：乱序执行的那些事儿

FOCUS

什么是乱序执行

乱序执行，简单说就是程序里面的代码的执行顺序，有可能会被编译器、CPU 根据某种策略调整顺序（俗称，“打乱”）——虽然从单线程的角度看，乱序执行不影响执行结果。

为什么需要乱序执行

主要原因是 CPU 内部采用流水线技术。抽象且简化地看，一个 CPU 指令的执行过程可以分成 4 个阶段：取指、译码、执行、写回。

这 4 个阶段分别由 4 个独立物理执行单元来完成。这种情况下，如果指令之间没有依赖关系，后一条指令并不需要等到前一条指令完全执行完成再开始执行。而是前一条指令完成取指之后，后一条指令便可以开始执行取指操作。

比较理想的情况如下图所示：指令之间无依赖，可以使流水线的并行度最大化。

在按序执行的情况下，一旦遇到指令依赖的情况，流水线就会停滞。比如：

指令 1: Load R3 <- R1(0) # 从内存中加载数据到 R3 寄存器指令 2: Add R3 <- R3, R1 # 加法，依赖指令 1 的执行结果指令 3: Sub R1 <- R6, R7 # 减法指令 4: Add R4 <- R6, R8 # 加法

上面的伪代码中，指令 2 依赖指令 1 的执行结果。在指令 1 执行完成之前，指令 2 无法执行，这会让流水线的执行效率大大降低。

观察到，指令 3 和指令 4 对其它指令没有依赖，可以考虑将这两条指令”乱序“到指令 2 之前。

这样，流水线执行单元就可以尽可能处于工作状态。

总的来说，通过乱序执行，合理调整指令的执行顺序，可以提高流水线的运行效率，让指令的执行能够尽可能地并行起来。

Compiler Fence

在多线程的环境下，乱序执行的存在，很容易打破一些预期，造成一些意想不到的问题。

乱序执行有两种情况：

在编译期，编译器进行指令重排。
在运行期，CPU 进行指令乱序执行。

我们先来看一个编译器指令重排的例子：

#include <atomic> // 按序递增发号器 std::atomic<int> timestamp_oracle{0}; // 当前处理的号码 int now_serving_ts{0}; int shared_value; int compute(); void memory_reorder() { // 原子地获取一个号码 int ts = timestamp_oracle.fetch_add(1); // 加锁：判断当前是否轮到这个号码，否则就循环等 while (now_serving_ts != ts); // 临界区：开始处理请求 shared_value = compute(); // 编译器 memory barrier asm volatile("" : : : "memory"); // 解锁：下一个要处理的号码 now_serving_ts = ts + 1; }

简单解释一下这段代码：

这个程序通过维护一个“发号器 timestamp_oracle”，来实现按顺序处理每个线程的请求。
每个线程先从“发号器”取一个号，然后不停判断当前是否轮到自己执行，类似自旋锁的逻辑。
每个线程执行完，将“号码”切换到下一个。

在 O1 的编译优化选项下，编译出来的汇编指令没有被重排（通过左右两边的代码行背景色就可以看出来）。

在 O2 的编译优化选项下，出现了指令被重排了，并且这里的指令重排打破了程序的预期，先切换了 now_serving_ts，再更新 shared_value，导致 shared_value 可能被并发修改。

为了阻止编译器重排这两句代码的指令，需要在它们之间插入一个 compiler fence。

asm volatile("": : :"memory");

这个是 GCC 扩展的 compiler fence 的写法。这条指令告诉编译器（GCC 官方文档）：

防止这条 fence 指令上方的内存访问操作被移到下方，同时防止下方的内存访问操作移到上面，也就是防止了乱序。
让编译器把所有缓存在寄存器中的内存变量 flush 到内存中，然后重新从内存中读取这些值。

对于第 2 点，有时候我们只需要刷新部分变量。刷新所有寄存器并不一定完全符合我们的预期，并且会引入不必要的开销。GCC 支持指定变量的 compiler fence。

write(x) asm volatile("": "=m"(y) : "m"(x):) read(y)

中间的内联汇编指令告诉编译器不要把 write(x) 和 read(y) 这两个操作乱序。

CPU Fence

先来看一个例子：

int x = 0; int y = 0; int r0, r1; // CPU1 void f1() { x = 1; asm volatile("": : :"memory"); r0 = y; } // CPU2 void f2() { y = 1; asm volatile("": : :"memory"); r1 = x; }

上面的例子中，由于 compiler fence 的存在，编译器不会对函数 f1 和函数 f2 内部的指令进行重排。

此时，如果 CPU 执行时也没有乱序，是不可能出现 r0 == 0 && r1 == 0 的情况的。不幸的是，由于 CPU 乱序执行的存在，这种情况是可能发生的。看下面这个例子：

#include <iostream> #include <thread> int x = 0; int y = 0; int r0 = 100; int r1 = 100; void f1() { x = 1; asm volatile("": : :"memory"); r0 = y; } void f2() { y = 1; asm volatile("": : :"memory"); r1 = x; } void init() { x = 0; y = 0; r0 = 100; r1 = 100; } bool check() { return r0 == 0 && r1 == 0; } std::atomic<bool> wait1{true}; std::atomic<bool> wait2{true}; std::atomic<bool> stop{false}; void loop1() { while(!stop.load(std::memory_order_relaxed)) { while (wait1.load(std::memory_order_relaxed)); asm volatile("" ::: "memory"); f1(); asm volatile("" ::: "memory"); wait1.store(true, std::memory_order_relaxed); } } void loop2() { while (!stop.load(std::memory_order_relaxed)) { while (wait2.load(std::memory_order_relaxed)); asm volatile("" ::: "memory"); f2(); asm volatile("" ::: "memory"); wait2.store(true, std::memory_order_relaxed); } } int main() { std::thread thread1(loop1); std::thread thread2(loop2); long count = 0; while(true) { count++; init(); asm volatile("" ::: "memory"); wait1.store(false, std::memory_order_relaxed); wait2.store(false, std::memory_order_relaxed); while (!wait1.load(std::memory_order_relaxed)); while (!wait2.load(std::memory_order_relaxed)); asm volatile("" ::: "memory"); if (check()) { std::cout << "test count " << count << ": r0 == " << r0 << " && r1 == " << r1 << std::endl; break; } else { if (count % 10000 == 0) { std::cout << "test count " << count << ": OK" << std::endl; } } } stop.store(true); wait1.store(false); wait2.store(false); thread1.join(); thread2.join(); return 0; }

上面的程序可以很轻易就运行出 r0 == 0 && r1 == 0 的结果，比如：

test count 56: r0 == 0 && r1 == 0

为了防止 CPU 乱序执行，需要使用 CPU fence。我们可以将函数 f1 和 f2 中的 compiler fence 修改为 CPU fence：

void f1() { x = 1; asm volatile("mfence": : :"memory"); r0 = y; } void f2() { y = 1; asm volatile("mfence": : :"memory"); r1 = x; }

如此，便不会出现 r0 == 0 && r1 == 0 的情况了。

总结

指令乱序执行主要由两种因素导致：

编译期指令重排。
运行期 CPU 乱序执行。

无论是编译期的指令重排还是 CPU 的乱序执行，主要都是为了让 CPU 内部的指令流水线可以“充满”，提高指令执行的并行度。

上面举的插入 fence 的例子都是使用了 GCC 的扩展语法，实际上 C++ 标准库已经提供了类似的封装：std::atomic_thread_fence，跨平台且可读性更好。

一些无锁编程、追求极致性能的场景可能会需要手动在合适的地方插入合适 fence，这里涉及的细节太多，非常容易出错。原子变量操作根据不同的 memory order 会自动插入合适的 fence，建议优先考虑使用原子变量。

发布于 2021-09-25 16:59

并发

评论千万条，友善第一条

6 条评论

默认

Intel CPU漏洞技术解读：都是缓存惹的祸！

云杉网络

技术创造价值

背景

2017年6月1日，Google的安全团队向Intel、AMD、ARM报了一个硬件级的漏洞，造成的危害是内核数据泄露，修复该漏洞的代价是至少30%的性能损失。2017年末Linux内核社区推出了KPTI「Kernel Page Table Isolation」补丁，Linus Torvalds在内核邮件列表上毫不留情地抨击了Intel。

安全人员将这两个漏洞命名为Meltdown和Spectre；Meltdown目前只存在于Intel的处理器和部分ARM处理器，Spectre存在于一切有乱序执行的现代处理器架构里面，包括AMD。从原理上来说漏洞无法彻底修复。

本次的漏洞会对所有云厂商造成较大影响，已经有迹象表明有黑客在利用漏洞攻击云系统。Microsoft Azure中国区已发布公告称，将于北京时间2018 年 1 月 4 日上午 11:30 开始自动重启受影响的虚拟机，并全部关闭向部分客户开放的自助维护窗口；AWS也发送了通知邮件声称本周五将进行重大安全更新。

原因

一切还是要从CPU指令执行的框架——流水线说起。Intel当然不至于明知你要用一个用户态的进程读取Kernel内存还会给你许可。但现代CPU流水线的设计，尤其是和性能优化相关的流水线的特性，让这一切充满了变数。

给所有还没有看过云杉网络连载的系列文章《x86高性能编程笺注系列》的读者一点背景知识的介绍：

x86 CPU为了优化性能，在处理器架构方面做了很多努力。诸如“多级缓存”这一类的特性，是大家都比较熟悉的概念。还有一些特性，比如分支预测和乱序执行，也都是一些可以从并行性等方面有效提升程序性能的特性，并且它们也都是组成流水线的几个关键环节。即便你暂时还不能准确理解其含义，但望文生义，也能看出来这肯定是两个熵增的过程。熵增带来无序，无序就会带来更多漏洞。

缓存的困境

讲缓存，必然先挂一张memory hierarchy镇楼：

不过我要说的和这个没太大关系。现在需要考虑的是，如果能读取到内核地址的内容，那这部分内容最终肯定是跑到缓存中去了，因为真正直接和CPU核心交互的存储器，就是缓存。这对一级缓存（L1 Cache，业内也常用缩写L1$，取cash之音）提出的要求就是，必须要非常快，唯有如此才能跟上CPU处理核心的速度。

Side Notes: 为什么在不考虑成本的情况下缓存不是越大越好，也是因为当缓存规模越大，查找某一特定数据就会越慢。而缓存首先要满足的要求就是快，其他的都是次要的。

根据内核的基本知识我们知道，进程运行时都有一个虚拟地址「Virtual address」和其所对应的物理地址「physical address」。

从虚拟地址到物理地址的翻译转换也由CPU通过page table完成。Page table并不储存在CPU里，但近期查找到的Page table entry「PTE」都像数据一样，缓存在了CPU中的translation lookaside buffer「TLB」里。为了不再过多堆砌术语和名词，画张图说明一下：

当CPU根据程序要求需要读取某个地址上的数据时，首先会在L1 Cache中查找。为了适应CPU的速度，L1缓存实现为Virtually indexed physically tagged「VIPT」的形式，即用虚拟地址即可直接读取该虚拟地址对应的物理地址的内容，而不再需要多加一道转换的工序。

如果L1 Cache miss，则会在下级缓存中查找。但越过L1 Cache之后，对L2$和L3$的速度要求就不再这么严苛。此时CPU core给出的虚拟地址请求会先通过TLB转换为物理地址，再送入下级缓存中查找。而检查进程有没有权限读取某一地址这一过程，仅在地址转换的时候发生，而这种转换和检查是需要时间的，所以有意地安排在了L1 Cache之后。

L1缓存这种必须求“快”的特性，成了整个事件的楔子。

分支预测

分支预测是一种提高流水线执行效率的手段。在遇到if..else..这种程序执行的分支时，可以通过以往的历史记录判断哪一分支是最可能被执行的分支，并在分支判断条件真正返回判断结果之前提前执行分支的代码。详情可以在上面提到的连载文章中阅读。

需要强调的是，提前执行的分支代码，即便事后证明不是正确的分支，其执行过程中所读取的数据也可以进入L1缓存。在Intel的官网文档《Intel® 64 and IA-32 Architectures Optimization Reference Manual》第2.3.5.2节中指：

L1 DCache Loads:
- Be carried out speculatively, before preceding branches are resolved.
- Take cache misses out of order and in an overlapped manner.

Show you the [伪] code:

if (likely(A < B)) { value = *(kernel_address_pointer);}

当分支判断条件A < B被预测为真时，CPU会去提前执行对内核地址的读取。当实际条件为A > B时，虽然内核的值不会真正写入寄存器（没有retire），但会存入L1 Cache，再加之上一节介绍的，获取L1 Cache的值毋须地址转换，毋须权限检查，这就为内核信息的泄漏创造了可能。

从理论上来讲，如果可以控制程序的分支判断，并且可以获取L1缓存中的数据（这个没有直接方法，但可以通过其他间接手法）的话，就完全可以获取内核信息。而分支预测这种特性是不能随随便便就关闭的，这也就是这次问题会如此棘手的原因。

乱序执行

还有一个原因是乱序执行，但原理大致类似。乱序执行是Intel在1995年首次引入Pentium Pro处理器的机制。其过程首先是将我们在汇编代码中看到的指令“打散”，成为更细粒度的微指令「micro-operations」，更小的指令粒度将会带来更多的乱序排列的组合，CPU真正执行的是这些微指令。

没有数据依赖的微指令在有相应执行资源的情况下乱序并行执行，进而提升程序的并行程度，提高程序性能。但引入的问题是，读取内核数据的微指令可能会在流水线发出exception之前将内核数据写入L1 Cache。与分支选择一样，为通过用户态进程获取内核代码提供了可能。

限于篇幅，更详细的内容读者可以在国外安全团队发布的消息中获取。

后续

刚刚查阅之前连载中的一些细节的时候，看到在“流水线”那一章里写过这样一段话：

在面对问题的时候，人总是会倾向于引入一个更复杂的机制来解决问题，多级流水线就是一个例子。复杂可以反映出技术的改良，但“复杂”本身就是一个新的问题。这也许就是矛盾永远不会消失，技术也不会停止进步的原因。但“为学日益，为道日损”，愈发复杂的机制总会在某个时机之下发生大破大立，但可能现在时机还没有到来:D

很难讲现在是不是就是所谓的那个“时机”。虽然对整个行业都产生了负面影响，但我对此仍保持乐观。因为这就是事物自然发展的一个正常过程。性能损失并不是一件坏事，尤其是对牙膏厂的用户来说。

◆◆◆

作者简介

张攀

一个不耽误码字的网工

张攀，云杉网络工程师，专注于x86网络软件的开发与性能优化，深度参与ONF/OPNFV/ONOS等组织及社区，曾任ONF测试工作组副主席。

编辑于 2018-01-05 14:12

漏洞

安全漏洞

评论千万条，友善第一条

6 条评论

默认

并发编程：乱序执行的那些事儿

并发编程：乱序执行的那些事儿

什么是乱序执行

为什么需要乱序执行

Compiler Fence

CPU Fence

总结

Intel CPU漏洞技术解读：都是缓存惹的祸！

背景

原因

缓存的困境

分支预测

乱序执行

后续