CPU分支预执行及其漏洞

现代CPU为了不让自己的pipeline停下来，都实现了分支预测和分支预执行（speculative execution），这的确能够显著加快代码的执行速度。有一些代码的优化策略，也依赖CPU的这个特性。

#include <algorithm>
#include <ctime>
#include <iostream>

int main(int argc, char **argv){
    // 随机产生整数
    const unsigned arraySize = 32768;
    int data[arraySize];
    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! 排序后下面的Loop运行将更快
    if(argc==2)
        std::sort(data, data + arraySize);

    // 测试部分
    clock_t start = clock();
    long long sum = 0;
    for (unsigned i = 0; i < 100000; ++i){
        // 主要计算部分，选一半元素参与计算
        for (unsigned c = 0; c < arraySize; ++c){
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double gap = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
    std::cout << gap << std::endl;
    std::cout << "sum = " << sum << std::endl;
    return 0;
}

$ g++ -O0 test.cpp && ./a.out
21.2729
sum = 314931600000
$ g++ -O0 test.cpp && ./a.out sorted
7.65179
sum = 314931600000

将data排序后再进行后面的计算，比未排序的版本快3倍左右。（如果使用-O3，就看不到这个效果了）

这就是CPU分支预测的效果。CPU主要根据if分支的历史执行记录，判断可能命中的下一条语句的地址，并预先开始执行。如果data是排序的，那么CPU预测的命中率就会很高，如果data中的数据是随机的，CPU预测命中率就只能在50%左右。这就是上面测试结果的原因！

预执行不仅能够加速，还带来了漏洞，比如meltdown和spectre。它们的基本原理，都是通过预执行机制，影响到了cache，然后通过side channel攻击，得到了本不应该得到的数据。被预执行的代码，也许在正常执行过程中，是根本没有机会执行的，或者只要真正执行，就会出现错误！有人将speculative execution翻译为投机执行。投机执行是现代处理器为了最大化执行性能而启用的固有属性，软件无法关闭它。

以下两个视频，用于深入了解由CPU cache和speculative exectuion引入的漏洞：