玻尔百科推测执行是现代高性能计算的基石，它是一种巧妙的策略，允许处理器根据对未来的预测来执行工作。正是这种对速度不懈的追求，带来了我们日常所依赖的计算能力的惊人进步。然而，这种性能的提升并非没有代价。Spectre 和 Meltdown 等漏洞的发现，揭示了这种方法存在一个根本性缺陷，表明这些推测行为的“幽灵”可能被迫泄露敏感信息，从而将一项性能特性转变为严重的安全风险。本文将揭开推测执行的神秘面纱，深入探讨其机制和广泛影响。
本次探索分为两个主要部分。首先，“原理与机制”一章将带领我们深入处理器核心，解释分支预测器如何进行预测，重排序缓冲区如何管理混乱，以及这种抽象中的裂缝如何引发瞬态执行攻击。随后，“应用与跨学科联系”一章将拓宽视野，审视推测执行对计算机安全、操作系统与编译器的设计，乃至我们对算法性能的基本理解所产生的深远影响。读完本文，您将不仅理解推测执行的工作原理，还将明白它如何在现代计算栈的每一层之间创造出复杂而迷人的对话。
要理解推测执行，就需要踏上一段深入现代处理器心脏的旅程。那是一个充满惊人巧思的地方，对速度的追求迫使工程师们与预言订立契约。这是一个关于赌博的故事，一个用于管理这场赌博的美丽而复杂的系统，以及那些将这一性能奇迹变为安全雷区的幽灵般副作用的发现。
想象一位繁忙厨房中的主厨。餐厅有固定菜单，但顾客在每道菜上都可以做出选择。食客想要汤还是沙拉？鱼还是牛排？一个缓慢而有条不紊的厨师会等待每一份订单确认后再开始准备下一道菜。这样做安全，但缓慢。然而，一位真正高效的主厨会做出猜测。“这位顾客看起来像是吃牛排的人，”他们可能会这样想，然后在服务员带回订单之前就开始煎肉。
如果猜对了，上菜速度会快上几分钟。如果猜错了，煎好的牛排就被浪费了，厨师必须迅速转向做鱼。这就是推测执行的本质。现代处理器在不懈追求性能的过程中，就像这位不耐烦的主厨。它们一个接一个地执行程序——也就是指令序列。然而，许多指令是条件分支——程序道路上的“if-then-else”岔路口。处理器要么等待，直到弄清程序实际会走哪条路，这意味着停顿流水线并浪费宝贵的时间；要么它可以预测路径，并开始执行来自那个被预测的未来的指令。
这个预测由一个非凡的硬件部件——分支预测器——完成。它就像厨师的直觉，但由硅和统计数据构成。它记录了过去分支走向的历史，并利用这些历史对未来做出惊人准确的猜测。但“惊人准确”并不完美。当预测器出错时——即发生错误预测——处理器就浪费了工作。所有来自错误执行路径的指令结果都必须被丢弃。这种清理工作的成本直接打击了性能，是为一次糟糕的赌注付出的实实在在的代价。
进行猜测很容易。真正的天才在于构建一个系统，它允许你大胆猜测，同时确保任何错误都不会成为永久、不可逆转的灾难。这是处理器复杂的控制逻辑的工作，是一场由缓冲区和标签精心编排的芭蕾，旨在将推测世界与真实的架构世界分离开来。
这场戏剧的核心角色是重排序缓冲区 (Reorder Buffer, ROB)。可以把它想象成一个暂存区，或者一本临时账本。当指令被取来后，它们按原始程序顺序被放入 ROB。然而，处理器的执行单元可以从 ROB 中挑选指令来执行，只要它们的输入数据准备就绪，即使这些指令在预测路径的遥远下游。这被称为乱序执行。
这些推测执行的结果并不会被写入处理器的最终、官方状态（架构寄存器或内存）。相反，它们被保存在 ROB 中。只有当一条指令到达 ROB 的队首，并且它之前的所有指令（包括所有分支）都已被确认为正确时，它的结果才会被“提交”或“引退”——即在架构上正式生效。
这种按序引退是处理器的神来之笔。它使得微架构在内部可以是一个混乱、乱序、推测的狂热世界，同时对外部世界呈现一个平静、完全顺序且正确的假象。
如果发生错误预测会怎样？过程异常简单。处理器在 ROB 中识别出预测错误的分支指令，然后简单地清空该指令及其后的所有指令。它们所有的临时结果都被丢弃，仿佛从未发生过。接着，处理器将其状态恢复到分支指令处设置的检查点，并从正确的路径开始取指。
但是，对于那些效果不易撤销的指令该怎么办呢？向寄存器写入一个值是一回事，但如果指令是告诉外部设备发射导弹，或更新一个关键的控制与状态寄存器 (CSR) 呢？这些操作可能是不可逆的。如果允许一条推测指令执行这样的副作用，而最终推测被证明是错误的，那将是灾难性的。
解决方案是 ROB 哲学的延伸：缓冲一切。当一条推测性的内存存储或对 CSR 的写入被执行时，其效果不会立即生效。相反，它被放入一个特殊的暂存区，比如存储缓冲区，并用其 ROB 条目进行标记。只有当该指令被确认为非推测性的，并从 ROB 队首引退时，它的操作才最终被释放并对外部世界可见。如果该指令被冲刷掉，其在副作用缓冲区中的条目也会被简单地丢弃。无害，无过。
同样的逻辑也适用于异常，比如访问无效内存地址导致的页错误。如果一条推测指令导致了错误，处理器不会立即惊慌并调用操作系统。它会悄悄地将这个错误记录在该指令的 ROB 条目中。如果该指令最终被证明在错误的路径上，这个错误会随指令一同被丢弃——它是一个从未在架构上发生过的幻象错误。如果路径是正确的，处理器会等到该指令到达 ROB 队首时才发出警报。正是这种纪律性实现了精确异常，这是现代计算的基石之一。
几十年来，这种在狂热的、推测性的微架构和宁静的、有序的架构状态之间的优雅分离被认为是一种完美的抽象。我们相信，只要最终的寄存器和内存值是正确的，芯片内部的瞬态混乱就是不可见且无关紧要的。
我们错了。
关键的疏忽在于，推测执行，即使在被冲刷后，仍然会留下足迹。这些不是对架构状态（程序员可见的官方状态）的改变，而是对微架构状态——处理器内部组件配置——的改变。其中最重要的是缓存层次结构。
缓存是小而快的存储体，用于存放最近使用的数据以加速访问。当处理器从主内存的某个地址加载数据时，它会在缓存中放置一个副本。下次需要该数据时，它可以从快速的缓存中获取，而不是从缓慢的主内存。这种访问时间的差异——一次快速命中与一次缓慢未命中——是显著的。
这就是漏洞的关键所在：一条推测执行的加载指令，即使后来被冲刷掉，仍然可以将数据带入缓存。加载的架构结果被丢弃了，但微架构的副作用——缓存现在持有来自那个特定地址的数据——会持续一小段时间。一个拥有精确秒表的攻击者可以测量后续内存访问的时间。通过发现哪个访问异常地快，他们可以推断出哪个地址被推测性地触碰过，从而泄露本应被隐藏的信息。这是一种时序侧信道攻击。一个瞬态指令的幽灵揭示了它从未正式知晓的秘密。
这个根本性的缺陷——通过微架构副作用泄露信息——催生了一系列漏洞。其中最臭名昭著的两个是 Spectre 和 Meltdown，它们以略微不同的方式利用了这个缺陷。
Spectre 攻击通过操纵处理器的预测器来工作。攻击者的目标是诱使处理器错误推测，并以一种非预期的方式执行一段现有的、有效的代码——一个“gadget”。
想象一段从数组中读取的代码：value = array[index]。代码包含一个安全检查：if (index array_length)。这是一个条件分支。攻击者可以通过反复使用有效的、在边界内的索引来调用此代码，“训练”分支预测器。然后，他们提供一个指向内存中秘密位置的越界索引。过度热心的分支预测器，受其训练的影响，猜测“在边界内”并推测性地执行 array[index] 加载。这个推测性加载读取了秘密数据。随后，另一条推测指令使用这个秘密值来访问第二个数组（一个探针数组），将一个缓存行缓存到由秘密值决定的地址。处理器很快发现其错误，冲刷整个序列，并执行正确的路径。但为时已晚。依赖于秘密数据的缓存足迹依然存在，攻击者可以用他们的秒表找到它。
Spectre 的决定性特征是它利用控制流错误预测。它胁迫处理器在一条本不应走的路径上瞬态地执行架构上有效的指令。在一个拥有完美预测（准确率 ）的假想世界里，这类漏洞将完全消失。
Meltdown 利用了一个不同的、更直接的硬件缺陷：内存访问和权限检查之间的竞争条件。在一个安全的系统中，用户程序被禁止读取操作系统的内核内存。任何这样做的尝试都必须引发硬件故障。
然而，在某些处理器上，乱序执行造成了一个致命的竞争。当用户程序发出从一个被禁止的内核地址加载的指令时，处理器会启动这个过程。它会从内存中取出数据，甚至将其转发给依赖的瞬态指令，而这一切都发生在权限检查硬件完成其工作并发出警报之前。片刻之后，故障被检测到，指令被标记，在引退时，CPU 会正确地冲刷该操作并向操作系统报告故障，从而维护了架构契约。
但在那个数据获取和故障检测之间的微小瞬态窗口中，秘密的内核数据已经被一个依赖的 gadget 用来创建了缓存侧信道，就像在 Spectre 中一样。Meltdown 不需要欺骗分支预测器。它依赖于处理器对一个根本上非法行为的延迟反应。这就是为什么即使在我们拥有完美预测器（）的思想实验中，Meltdown 仍然会存在的原因。
这些漏洞的发现引发了全行业的缓解措施争夺战。这些修复措施揭示了性能与安全之间的深刻矛盾。
软件缓解措施通常涉及将控制依赖转换为数据依赖。例如，编译器可以使用掩码来使越界索引无效，而不是使用分支，从而迫使处理器在计算内存地址之前等待边界检查的结果。另一种方法是插入特殊的“栅栏”指令 (lfence)，它充当屏障，明确告诉处理器暂停推测，直到所有先前的指令都得到解决。
硬件设计者提出了更根本的改变，例如为推测数据创建隔离的“瞬态缓冲区”，这些数据在指令被确认为正确之前不会触及主缓存。然而，即使是这些复杂的修复也并非万灵药。推测在许多微架构结构中都留下了痕跡——TLB、分支预测器本身、资源争用——留下了一片潜在的“残余”时序信道的景观。
归根结底，推测执行是一个强大的工具，它源于一个简单而绝妙的想法：不要等待，要预测。它代表了一种根本性的权衡。几十年来，我们为等式的一边——性能——进行优化，却没有意识到对另一边——安全——的微妙代价。计算机架构师面临的持续挑战是重新平衡这个等式，构建不仅速度惊人，而且可被证明是安全的机器，同时又不放弃使它们如此之快的魔力。
在探索了推测执行那美丽而复杂的时钟般机制之后，人们可能会倾向于认为它只是一个巧妙但自成体系的技巧，是处理器核心内部的私事。这大错特错。让处理器去梦想未来——在指令到期之前执行它们——这个决定在计算栈的每一层都激起了涟漪。它不仅仅是硬件的一个特性；它是一个重塑了安全格局、操作系统设计、编译器构建艺术，乃至算法理论的基本原则。在本章中，我们将踏上一段旅程，看看这一个想法是如何在机器的最深层次和我们软件的最高层次之间创造出一段迷人且时而危险的对话。
推测执行的契约似乎很简单：如果处理器猜错了，它会抹去其错误的所有痕跡。架构状态——我们的程序可以看到的寄存器和内存——被无可挑剔地恢复了。但那些程序无法看到的东西呢？微架构状态又如何呢？想象一个幽灵穿过一个房间。它不留下任何架构足迹，但它的经过可能会让空气变冷或留下淡淡的气味。处理器的推测性“幽灵”——瞬态指令——也做着类似的事情。它们在缓存、转译后备缓冲器 (TLB) 和分支预测器的状态中留下了微弱的痕跡。一个敏锐的观察者，通过测量缓存的“温度”，可以了解到幽灵在做什么。这就是瞬态执行侧信道攻击的起源。
这类攻击的成功与否通常归结为与时间的赛跑。一条由错误预测的分支产生的推测指令，其生命周期是有限的。它必须在处理器发现错误预测并冲刷它之前完成其任务——例如，将秘密从内存加载到缓存中。这是否可能取决于一个微妙的时间平衡。如果分支很快得到解析，瞬态窗口就很短。相反，如果决定分支结果的指令具有长延迟（比如一个缓慢的除法操作），瞬态窗口就会延长，因为错误预测被发现得更晚。这个更长的窗口给了攻击 gadget 更多的时间在被冲刷前执行并留下侧信道痕跡。
这些原理催生了如今著名的几类漏洞。在像 Spectre 这样的攻击中，处理器被诱骗错误预测一个分支，并推测性地执行一段它本不应执行的有效代码（一个“gadget”）。例如，你代码中一个简单的边界检查 if (i n) 可能成为一个入口。攻击者可以训练分支预测器，让它预期 i 会在边界内，然后提供一个越界的 i。处理器遵循其训练，推测性地执行 if 块内的代码，瞬态地执行一次越界读取，将信息泄漏到缓存中。
更引人注目的是 Meltdown 式的漏洞，在这种漏洞中，推测执行似乎可以绕过基本的硬件保护规则。想象一个用户程序试图读取操作系统私有的、仅主管模式可访问的内存中的一个秘密地址。在架构上，这是被禁止的，并且会导致故障。但在具有某些推测行为的处理器上，加载操作可能会瞬态执行，在权限检查完成并冲刷该操作之前，将秘密数据带入缓存。架构上的故障被避免了，但微架构的损害已经造成。这迫使我们从根本上重新思考用户程序和操作系统之间的边界，需要在控制权在特权级别之间传递时（无论是在进入内核 (ECALL) 时还是返回用户态时）使用硬件栅栏来序列化执行并清理预测器状态。
操作系统是机器资源的主宰，但它也必须遵守硬件的规则。推测执行为这份契约增加了一系列引人入胜的新条款。思考一下异常。当一条推测指令导致故障时，比如一个地址转换不在缓存中的 TLB 未命中，会发生什么？如果处理器立即停机并跳转到操作系统，它可能是在响应一个来自错误预测路径的幻象事件。
相反，硬件以非凡的优雅处理了这个问题。一次推测性的 TLB 未命中被记录为一个微架构事件。该指令被标记，但处理器继续执行。只有当该指令到达执行流水线的队首，并被确认为在正确的执行路径上时，这次未命中才会被提升为一次“精确的”架构异常，此时操作系统才被正式通知。如果该指令被冲刷掉，这个故障也随之消失，从未打扰过操作系统 [@problem_d:3640520]。这种优雅的舞蹈确保了操作系统只处理现实，而不是处理器的推测性梦想。
在多核世界中，这种舞蹈变得更加复杂。推测并非私事。一个核心的瞬态行为可能对另一个核心产生非常真实的后果。考虑一种用于自旋锁的常见性能优化，称为 test-and-test-and-set (TTAS)，即一个核心首先在一个紧密循环中读取一个锁变量，只有当锁看起来空闲时才尝试进行昂贵的原子写操作。这避免了一致性流量的风暴。但真的如此吗？如果一个分支预测器错误预测，并在锁正忙时推测性地执行原子 test-and-set 指令，它将发出一个真实的、请求缓存行独占所有权的请求，从而产生一致性流量并使其他核心上的副本失效。锁并未被获取，但性能成本已经付出了。
干扰可能更加微妙。像 Load-Linked/Store-Conditional (LL/SC) 这样的原子操作依赖于一个核心“预留”一个内存地址，并且只有在没有其他核心在此期间写入该地址的情况下，其存储操作才能成功。令人惊讶的是，另一个核心上的一次推测性存储——一个后来被冲刷掉且从未在架构上发生的存储——仍然可以产生一致性失效，从而破坏第一个核心的预留，导致其 SC 失败。一个核心的瞬态幽灵惊扰了另一个核心非常真实的原子操作。
编译器是翻译官，将我们抽象的人类逻辑转换为处理器能理解的具体指令。有了推测执行，这个翻译任务增加了一个新的、关键的维度：安全。一个看似无害的优化可能会无意中创建一个 Spectre gadget。例如，一个执行边界检查消除 (BCE) 的编译器可能会证明一个循环的索引 i 永远不会超过数组边界 n，并且为了性能，移除 if (i n) 检查。这很棒，因为它消除了可能被错误预测的分支本身，有效地蒸发了一个潜在的漏洞。
但编译器也可以成为防御者。意识到推测的危险，它可以采取主动措施。当面临一个潜在的 gadget 时，它可以插入一个特殊的推测屏障指令（如 x86 上的 LFENCE）。这个指令就像一堵墙，迫使处理器在被允许推测性地执行屏障之后的任何指令之前，先解析前面的分支。这有效地关闭了瞬态窗口，并消除了威胁。
一种更复杂的防御是让编译器将代码重写为数据无关的。编译器可以将依赖于秘密的访问 P[secret] 转换为访问所有可能的位置，其方式是最终结果相同，但内存访问模式与秘密值无关。现在，幽灵访问了每一个房间，让观察者无从知晓哪一个房间藏有宝藏。
最后，我们来到了最令人惊讶的前沿：推测对算法设计本身的影响。几十年来，我们被教导要用渐进复杂度来评判算法。一个 的算法在根本上优于一个 的算法。但总是这样吗？
考虑在大型有序数组中搜索的经典任务。二分搜索是教科书中的 冠军。然而，它的访问模式完全不可预测：它从中间跳到四分之一处，再到八分之三处，依此类推。对于现代处理器来说，这是一场噩梦。每次内存访问都可能是缓存未命中，每个条件分支对分支预测器来说都是抛硬币，导致频繁且昂贵的流水线冲刷。
现在考虑“更慢”的跳跃搜索，其复杂度为 。它的工作方式是首先以大的固定步幅向前跳跃，然后进行小范围的线性扫描。对于处理器来说，这是一个梦想。控制流高度可预测——一个几乎肯定会继续的循环——因此分支很少被错误预测。内存访问也是可预测的——要么是顺序的，要么是固定步幅的——硬件预取器可以提前运行，在数据被需要之前就将其带入缓存。推测执行放大了这些优势，隐藏了内存延迟并避免了分支惩罚。结果如何？在真实世界中，在一个现实的成本模型下，“更慢”的跳跃搜索实际上可能胜过“更快”的二分搜索。跳跃搜索优雅、可预测的结构，与推测性、乱序执行机器的优势更为匹配。
这教给我们一个深刻的教训：我们编程的机器并非我们教科书中的简单随机存取机。它是一个复杂、推测性的野兽，奖励可预测性。即使是普通的函数调用也依赖于一个专门的推测结构——返回地址栈 (RAS)，它本身也需要一个复杂的检查点机制，以确保在错误预测后能够正确恢复。
从我们操作系统的安全到我们排序算法的性能，推测执行都留下了其不可磨灭的印记。它是一种强大、美丽且时而危险的力量，将计算机科学中不同的领域编织在一起，提醒我们，要真正理解任何一个部分，我们必须欣赏它与整体的联系。