Nothing Is Secret

1. Cache的容量设计

上篇文章中介绍到CPU Cache是分级的，L1 Cache是集成在Core内部的，L2则是紧贴着Core，而L3是多个Core共享的。离Core（流水线）越近的分级速度越快，但容量也更小，并且造价愈贵。Cache的实现采用了高速的SRAM电路 (静态随机存取存储器: Static Random-Access Memory)，SRAM相对DRAM (动态随机存取存储器: Dynamic Random Access Memory)要复杂和庞大的多，即使不考虑成本能做到无限增大，但因为电路复杂度的提升其性能即访问速度必然会下降，另外也会使得CPU的面积急速膨胀。最终，CPU的每一级Cache的容量都是在设计之初考虑各方面因素折中后的结果（trade-off）。下图是AMD Zen的CCX的die shot[来源：1. Zen - Microarchitectures - AMD]，从图中我们就能看中L2及L3 Cache占据了很大一部分的面积：

一般而言L1 Cache约几十K，L2则是几百K，L3是几M或几十、几百M，但相比较内存动不动几十G的大小来说还是小了太多，根本不在一个数量级上。那么问题来了：Cache容量比内存小了太多，为什么根本不在一个数据量级的Cache能够大副度提升系统性能？

2. 局部性原理 (Principle of Locality)

简言之，程序倾向于访问（或执行）刚刚访问过的数据（执行过的指令）或与之相临近的数据（指令）

2.1 时间局部性 (Temporal locality):

刚刚被访问的地址（数据）在未来有很大的可能性被再次访问，即用过的数据可能会再次被用到

2.2 空间局部性 (Spatial locality):

刚刚被访问的地址的临近位置在未来有很大的可能被访问，以数组D[]为例，当前访问的是D[i]，那么D[i+1]有很大的可能将被访问

2.3 算法局部性：

程序代码也遵守2/8法则，即帕累托法则（Pareto principle，亦称关键少数法则），80%的时间都是在执行20%的代码

正是因为局部性原理，少量的Cache大大减少了数据的访问延迟，从而提升了整体性能。

3. Cache的放大效应

先来考虑一个问题：Cache命中率(Cache Hit) 99%与98%的差别会有多大？从数值上来看二者本身仅相差1%，性能上最终能有多大差别呢？

假设命中L1的延时为4 cycles，不命中的话需要从内存中读取数据的延时为150 cycles，那么：
99%命中率的情况: 0.99 * 4 + 0.01 * 150 = 5.46
98%命中率的情况: 0.98 * 4 + 0.02 * 150 = 6.92

后者比前者的延时多了(6.92 - 5.46) / 5.46 = 26.7% 之多。换成95%的命中率的话，延时将高达99%命中率时的一倍之多。由此看来，不命中（Cache Miss）所带的性能惩罚巨大，这也预示了未来Cache发展的趋势，即容量将越来越大，拥有GB级Cache容量的CPU将指日可待，另外增加L4分级也将是不可避免的，有兴趣的读者可进一步参阅 [2. The Next Platform: Cache Is King]。

4. Cache Miss的原因

前面说了Cache Miss的惩罚，下面说一下会导致Cache Miss的因素，可以简单归纳为3C:
1. Cold (Compulsory) Miss： 第一次访问数据时，数据根本不在Cache中
2. Conflict Miss： 因冲突导致Cache Line被驱逐出Cache，上一篇文章中提到了相关的方法，如Evict(驱逐)、Prime(装填)等，当然冲突所导致的Cache Miss只针对组相联的Cache结构（直接映射可以认为是单路组相联），而全相联的Cache结构是没有Conflict Miss的，后续还会针对此课题做详细的介绍
3. Capacity Miss： Cache的容量毕竟有限，如果程序确实需要密集访问大量内存时，Cache必然是不够的

在指定的CPU硬件上如果想提升Cache Hit的话就要从这几个因素上着手，如通过硬件预取以减少Cold Miss，通过程序算法改进及结构重组可减少2和3所带来的Cache Miss的发生概率，本文先点到为止，后面将进行详细拆解。

5. 参考资料

1. wikichip: Zen - Microarchitectures - AMD
2. The Next Platform: Cache Is King

通过上一篇文章《通过TSC观察CPU》知道了可以通过TSC来测量CPU的内部行为，本文将介绍CPU Cache的结构及几种常用的测量手法：

Cache的分级结构

- Cache 是分级的：一般分为3级，较老的CPU如Core 2 Duo只有2级。L1是集成是core内部的，指令与数据Cache是分离的，好L1C和L1D；L2是紧贴core的；L3是多核共享的，每个core有自己的Slice，通过Ring Bus或Mesh结构互联互访
- Cache以Cache Line为访问单位，即Cache及内存的访问是以块为单位的，而不是字节单位。较新的X86 CPU的Cache Line一般是64字节。上一篇文章通过TSC观察CPU曾注意到一个有趣的测量结果：X86程序访问一个1字节与访问2个、4个及8个字节的延进均为31个指令周期，并不是线性增长的，就是这个原因
- 层级包含与否由CPU实现决定：L2一般都是包含L1的全部内容的，L3可以是Non-inclusive，也可以是Exclusive。Intel的CPU一般是包含的，但AMD的Zen系列CPU的L3就是定义为L1/L2的Victim Cache，Victim是指从L1及L2中移除的Cache项
- Cache自身的构造采用“组相联”方式

Cache不同分级的性能

在上图中看到Cache是分级的，用不同级的访问速度有很大不同，故我们可以通过制造冲突或直接Flush Cache的方式将数据从Cache中清除，从而通过前后内存访问的时间差来进行判定。

测量方法

制造冲突以清除Cache的常用手段有以下几种【参阅 1：Cache side channel attacks: CPU Design as a security problem by Anders Fog]】：

1. Evict (驱逐) + Time (测量) ： 通过制造冲突以达成被测量目标数据从cache中清除的目的
2. Prime (装填) + Probe (探测) ：与1)方法一样，只是作用对象是反的
3. Flush (冲刷) + Reload (加载) ) ：最主动和最快的办法，直接利用clflush指令刷新，然后再读取内存，此时会发生Cache Miss事件。
4. Flush (冲刷) + Flush (冲刷) ) ：与3)类似，但测量的是clflush指令针对数据在不在cache中的执行周期的不同

在条件许可的情况下，尽量采用第3种，即最快的办法。

实例：Flush + Reload

Flush即clflush指令，Visual C++中定义如下：

        extern void _mm_clflush(void const*_P);

测量代码：

        /* flush */
        _mm_clflush(&data[0]);

        /* measure cache miss latency */
        ts = rdtscp(&ui);
        m |= data[0];
        te = rdtscp(&ui);

实战：Cache Line的测量

原理：

结论：

从图中我们可以看到64字节是一个明显的分界点。

硬件预取: Hardware Prefetcher

如果你在自己的电脑上进行测试，你看到的可能不是上图所示的样子，很大的可能如下图所示，明显的分界点不是64字节而是128字节：

这是因为硬件预取即HWPrefetcher的缘故，并且硬件预取默都是开启的。硬件预取功能会在每次Cache Miss的情况下多读一个Cache Line，可以理解为每次读取两个Cache Line即64 * 2 = 128字节，但数据并不是同时到达的，第二个Cache Line的数据的到达周期会晚些，这也是为什么在128这个点上的延时会比64高。

如何关闭硬件预取

1. 通过BIOS设置： 通过BIOS选项来关闭hwprefetcher，对所有的CPU生效
2. 通过内核调试器windbg直接关闭：通过直接改写msr寄存器关闭当前核的硬件预取功能:

0: kd> rdmsr 0x1a4
msr[1a4] = 00000000`00000000
0: kd> wrmsr 0x1a4 0x0f
0: kd> ~1
1: kd> rdmsr 0x1a4
msr[1a4] = 00000000`00000000
1: kd> wrmsr 0x1a4 0x0f
1: kd> rdmsr 0x1a4
msr[1a4] = 00000000`0000000f
1: kd> ~0

实战：Cache不同分级的访问延时测量

如果我们以更大的的stride进行同样的测试则可以测量出Cache每一级的大小，即L1D，L2，LLC和内存访问的延时。下图中我们分别以1K、2K，直至64M的stride测量出来结果：

可以看到整个曲线有4个平台，分别表示L1D、L2、LLC和内存。L1D的大小为32K，L2为256K，这部分和CPUZ的输出是一致的。
但第三个平台包含了512K、1M及2M，从4M开始延进有明显的跃升，从8M之后基本稳定在高位。这里就涉及到了LLC组织的不同：L1D及L2 Cache都是与物理核（Core）绑定的，而LLC是绑定CPU的，即2核的CPU的两个核心会共享同一个LLC，整个LLC是平均分配给每个核的，然后每个核心的LLC通过Ring Bus互联，即每个核又可以访问所有的LLC。这里在4M的stride发生波动的原因有两个：
1. 当前运行测量程序的CPU核心用尽自己的LLC后会通过Ring Bus竞争访问另一个核心的LLC
2. 测量程序运行时整个操作系统也在运行，所以整个系统均会竞争使用LLC，必然会带来挤出效应，从而增大了延时

参考资料

1. CSCA: Cache side channel attacks: CPU Design as a security problem by Anders Fogh
2. HWPF: Disclosure of Hardware Prefetcher Control on Some Intel® Processors
3. SourceCode: CacheLatency Github Repo

自Pentium开始x86 CPU均引入TSC了，可提供指令级执行时间度量的64位时间戳计数寄存器，随着CPU时钟自动增加。

CPU指令

rdtsc: Read Time-Stamp Counter
rdtscp: Read Time-Stamp Counter and Processor ID

调用:

Microsoft Visual C++:

unsigned __int64 __rdtsc();
unsigned __int64 __rdtscp( unsigned int * AUX );

Linux & gcc :

extern __inline unsigned long long
__attribute__((__gnu_inline__, __always_inline__, __artificial__))
__rdtsc (void) {
  return __builtin_ia32_rdtsc ();
}
extern __inline unsigned long long
__attribute__((__gnu_inline__, __always_inline__, __artificial__))
__rdtscp (unsigned int *__A)
{
  return __builtin_ia32_rdtscp (__A);
}

示例：

1: L1 cache及内存的延迟测量:

代码：

{
    ......
    /* flush cache line */
    _mm_clflush(&data[0]);

    /* measure cache miss latency */
    ts = rdtscp(&ui);
    m |= data[0];
    te = rdtscp(&ui);
    CALC_MIN(csci[0], ts, te);

    /* measure cache hit latency */
    ts = rdtscp(&ui);
    m &= data[0];
    te = rdtscp(&ui);
      /* flush cache line */
    _mm_clflush(&data[0]);

    /* measure cache miss latency */
    ts = rdtscp(&ui);
    m |= data[0];
    te = rdtscp(&ui);
    CALC_MIN(csci[0], ts, te);

    /* measure cache hit latency */
    ts = rdtscp(&ui);
    m &= data[0];
    te = rdtscp(&ui);
    CALC_MIN(csci[1], ts, te);
    CALC_MIN(csci[1], ts, te);
}

结果：

rdtscp指令自身耗时：X86: 31 X64: 33

问题：读取1个字节与8个字节的所用的时间是一样的，为什么？

2: 常见整型运算及多条指令执行周期:

代码：

{
    ......
    /* measure mul latency */
    ts = rdtscp(&ui);
    m *= *((U32 *)&data[0]);
    te = rdtscp(&ui);
    CALC_MIN(csci[2], ts, te);

    /* measure div latnecy */
    ts = rdtscp(&ui);
    m /= *((U32 *)&data[0]);
    te = rdtscp(&ui);
    CALC_MIN(csci[3], ts, te);

    /* measure 2*mul latnecy */
    ts = rdtscp(&ui);
    m *= *((U32 *)&data[0]);
    m *= *((U32 *)&data[0]);
    te = rdtscp(&ui);
    CALC_MIN(csci2[0], ts, te);

    /* double div */
    ts = rdtscp(&ui);
    m /= *((U32 *)&data[0]);
    m /= *((U32 *)&data[0]);
    te = rdtscp(&ui);
    CALC_MIN(csci2[1], ts, te);

    /* mul + div */
    ts = rdtscp(&ui);
    m *= *((U32 *)&data[0]);
    m /= *((U32 *)&data[0]);
    te = rdtscp(&ui);
    CALC_MIN(csci2[2], ts, te);

    /* measure float mul latency */
    ts = rdtscp(&ui);
    f = f * m;
    te = rdtscp(&ui);
    CALC_MIN(csci[4], ts, te);

    /* measure float div latency */
    while (!m)
        m = rand();
    ts = rdtscp(&ui);
    f = f / m;
    te = rdtscp(&ui);
    CALC_MIN(csci[5], ts, te);
}

结果：

问题：m及n的除法运算的耗时只比m的除法多了一点，但却明显少于m的两次除法，为什么？

注意事项：

1. 考虑到CPU乱序执行的问题，rdtsc需要配合cpuid或lfence指令，以保证计这一刻流水线已排空，即rdtsc要测量的指令已执行完。后来的CPU提供了rdtscp指令，相当于cpuid + rdtsc，但cpuid指令本身的执行周期有波动，而rdtscp指令的执行更稳定。不过rdtscp不是所有的CPU都支持，使用前要通过cpuid指令查询是不是支持： 即CPUID.80000001H:EDX.RDTSCP[bit 27]是不是为1
2. 多核系统：新的CPU支持了Invariant TSC特性，可以保证在默认情况下各核心看到的TSC是一致的，否则测量代码执行时不能调度至其它核心上。另外TSC是可以通过MSR来修改的，这种情况下也要注意：
   Invariant TSC:
Software can modify the value of the time-stamp counter (TSC) of a logical processor by using the WRMSR instruction to write to the IA32_TIME_STAMP_COUNTER MSR
3. CPU降频问题：第一代TSC的实现是Varient TSC，没有考虑到降频的问题，故在低功耗TSC计数会变慢，甚至停止；后来又有了Constant TSC，解决了降频的问题，但在DEEP-C状态下依然会发生停止计数的情况，所以又有了最新的Invariant TSC的特性：
   The time stamp counter in newer processors may support an enhancement, referred to as invariant TSC.
Processor’s support for invariant TSC is indicated by CPUID.80000007H:EDX[8].
The invariant TSC will run at a constant rate in all ACPI P-, C-. and T-states. This is the architectural behavior moving forward. On processors with invariant TSC support, the OS may use the TSC for wall clock timer services (instead of ACPI or HPET timers). TSC reads are much more efficient and do not incur the overhead associated with a ring transition or access to a platform resource.
4. 指令本身的时间开销
   Pentinum Gold G5500T: 31 cycles
Core i7-7820HQ: 25 cycles
5. 权限问题（此指令可用于时序攻击，如Meltdown及Spectre）:
   CR4.TSD:
Time Stamp Disable (bit 2 of CR4) — Restricts the execution of the RDTSC instruction to procedures
running at privilege level 0 when set; allows RDTSC instruction to be executed at any privilege level when
clear. This bit also applies to the RDTSCP instruction if supported (if CPUID.80000001H:EDX[27] = 1).
6. 计数器溢出可能：计算器本身是64位的，即使是主频4G的CPU，也要100多年才会溢出，对于我们的测量来说可以不用考虑
7. 时序测量容易被干扰（线程调度、抢占、系统中断、虚拟化等），要求测量的指令序列尽量短，并且需要进行多次测量