Linux内存之Cache_linux cache

一、 Linux内存之Cache

1.1、Cache

1.1.1、什么是Cache？

Cache存储器，是位于CPU和主存储器DRAM之间的一块高速缓冲存储器，规模较小，但是速度很快，通常由SRAM（静态存储器）组成。

Cache的功能是提高CPU数据输入输出的速率。Cache容量小但速度快，内存速度较低但容量大，通过优化调度算法，可以让系统的性能大大改善，感觉就像是又有了主存储器的内存，又有了Cache的访问速度。

1.1.2、Cache工作方式简述

CPU在访问存储器的时候，会同时把地址（虚拟地址）发送给MMU中的TLB以及Cache，CPU会在TLB中查找最终的RPN（Real Page Number），也就是真实的物理页面，如果找到了，就会返回相应的物理地址。同时，CPU通过cache编码地址中的Index，也可以很快找到相应的Cache line组，但是这个cache line 中存储的数据不一定是CPU所需要的，需要进一步检查，前面我们说了，如果TLB命中后，会返回一个真实的物理地址，将cache line中存放的地址和这个转换出来的物理地址进行比较，如果相同并且状态位匹配，那么就会发生cache命中。如果cache miss，那么CPU就需要重新从存储器中获取数据，然后再将其存放在cache line中。

1.2、程序是如何运行的？

我们先思考一个问题：我们的程序是如何运行起来的？

我们应该知道，程序是运行在RAM之中，RAM就是我们常说的DDR，我们称之为main memory（主存）。

当我们需要运行一个进程的时候，首先会从磁盘设备（eMMC,UFS,SSD等）中将可执行程序load到主存中，然后开始执行。在CPU内部存在一堆通用寄存器，如果CPU需要将一个变量（假设地址是A）加1，一般分为下面上个步骤：

• CPU从主存中读取地址A的数据到内部通用寄存器x0
• 通用寄存器x0加1
• CPU将通用寄存器x0的值写入主存。

但是在现实中，CPU通用寄存器的速度和主存之间存在着太大的差异。

因此，上面举例的三个步骤中，步骤1和步骤3实际上速度很慢（和主存相关）。当CPU试图从主存中load/store操作时，由于主存的速度限制，CPU不得不等待这漫长的65ns时间。如果我们可以提升主存的速度，那么系统将会获得很大的性能提升。

但是如今的DDR存储设备，动不动就是几个GB，如果我们采用更快的材料制作更快速度的主存，并且拥有几乎差不多的容量，那么成本将会大幅度上升，又想要大容量，又想要高速率，还想要低成本，这根本就是一个鱼和熊掌不可兼得的问题。所以，我们有了一种折中的方法，那就是制作一块速度极快，但是容量极小的存储设备，我们称之为cache memory。

在硬件上，我们将cache放置 在CPU和主存之间，作为主存数据的缓存。当CPU试图从主存中加载/存储数据的时候，CPU会首先从cache中查找对应地址的数据是否缓存在cache中，如果数据缓存在cache中，那么直接从cache中拿到数据并返回给CPU。当存在cache的时候，以上程序运行流程就变成了如下：

CPU和主存之间直接数据传输的方式转变成了CPU和cache之间直接数据传输。cache负责和主存之间的数据传输。

1.3、多级cache存储结构

cache的速度在一定程度上同样影响着系统的性能。一般情况下cache的速度可以达到1ns，几乎可以和CPU寄存器速度媲美。但是，这就满足了人们对性能的追求了吗？并没有。当cache中没有缓存我们想要的数据的时候，依然需要漫长的等待从主存中load数据。为了进一步提升性能，引入多级cache。前面提到的cache，称为L1 cache（第一级cache）。我们在L1 cache后面连接L2 cache，在L2 cache和主存之间连接L3 cache。等级越高，速度越慢，容量越大。 但是速度和主存相比而言，依然很快。

1.3.1、多级cache之间的配合工作

首先引入两个名字概念，命中和缺失。 CPU要访问的数据在cache中有缓存，称为命中，反之称为缺失。

当CPU试图从某地址载入数据时，首先从L1 cache中查询是否命中，如果命中则把数据返回给CPU，如果L1 cache缺失，则继续从L2 cache中查找。当L2 cache命中时，数据会返回给L1 cache及CPU。如果L2 cache中也缺失，很遗憾，我们需要从主存中加载数据，将数据返回给L2 cache、L1 cache和CPU。这种多级cache的工作方式称为inclusive cache（某一地址的数据可能存在多级缓存中）。与inclusive cache对应的是exclusive cache，这种cache保证某一地址的数据缓存只会存在于多级cache的其中一级，也就是说任意地址的数据不可能同时在L1和L2 cache中。

1.4、cache的结构

cache是一个存储器，一个cache里面分好几块，官方叫法就是分成好几路，然后每一块小的cache里面，分成好几个cache line，不同块中的相同位置的cache line，组成了一个组，这个就是cache的基本结构了。

如上图所示，这个cache中有4路（块），每一路有4个cache line，总共有4组。

• 组：相同索引域的cache line组成一个组
• 路：在组相连结构的cache中，cache被分成几个相同大小的块
• cache line：cache line是cache中最小的访问单元

除了上面的内容，cache中还有几个概念，是由于查询cache是否命中的重要概念

• cache地址编码：处理器访问cache，就需要靠cache的地址编码，分成三部分，分别是偏移域（offset）、索引域（index）和标记域（tag）
• 偏移域（offset）：用于查找某一个cache line中的具体字节
• 索引域（index）：用于查找数据是在cache中的哪一个组中
• 标记（tag）：用于判断cache line中存放的数据是否和处理器想要的一致，每一个cache line都有它唯一的一个tag值。

举个例子：在一个32KB的4路组相连的cache中，其中cache line为32Byte，请画出这个cache的结构图

每一路（每一块）的大小就是cache的总大小除以路数：32KB/4 = 8KB
每一路（每一块）包含的cache line数目等于块大小除以cache line大小：8KB/32Byte = 256

1
2
3
4
5

1.4.1、如何判断cache是否命中？

如果CPU从0x0654地址读取一个字节，cache控制器是如何判断数据是否在cache中命中的呢？我们如何根据地址在有限大小的cache中查找数据呢？

如上图，我们一共有8行cache line，cache line大小是8 Bytes。所以我们可以利用地址低3 bits（蓝色部分）用来寻址8 bytes中某一个字节，我们称这部分bit组合为offset。同理，为了覆盖所有cache line，我们需要3 bits（黄色部分）查找某一行，这部分地址称为index。所以，当两个地址的bit3、bit4、bit5的值完全一样，那么说明这两个地址都会找到同一个cache line，所以，当我么找到了cache line之后，只代表我们访问的地址对应的数据可能存在这个cache line中。 所以，我们又引入了tag array区域。每一个cache line都对应唯一的一个tag，tag中保存的是整个地址位宽减去index和offset的长度。这样tag、index、offset三者组合就可以确定唯一的地址了。

所以，当我们根据地址中index位找到cache line后，取出当前cache line对应的tag，然后和地址中的tag进行比较，如果相等，就说明cache命中了，否则就是缺失。上面我们提出了一个问题，为什么硬件cache line不做成一个字节？ 这样会导致硬件成本的上升，原本8字节对应一个tag，现在需要8个tag，占用了很多内存。

1.5、cache的映射方式

1.5.1、直接映射缓存

直接映射的方式比较简单，我们先看一张图：

我们把整个cache只分成一个块，那么一个组就只有一个cache line，这种方式就叫做直接映射方式。
上面那个图，假设cache只有4个cache line。那么直接映射的地址就是0x0到0x30，这段内存地址直接映射到cache中。如果cpu要访问0x40到0x70，那么又会把0x40到0x70的地址直接映射到cache里，这个时候，0x0到0x30这段内存地址的数据就需要从cache里面踢出去，否则0x40到0x70的地址就没办法映射。cache的直接映射有可能会发生严重的高速缓存颠簸，性能会很差。

void add_array(int *data1, int *data2, int result, int size)
{
	int i;
	for (i == 0; i < size; i++) {
		result = data1[i] + data2[i];
	}
}
1
2
3
4
5
6
7

假使上面的程序，result、data1、data2分别指向0x00，0x40和0x80的地址，并且它们都会使用到同一个cache line

• 第一次读取data1的值即0x40地址的值时，由于不在cache里面，所以读取从0x40到0x4f地址的数据填充到cache里面
• 当读取data2的值即0x80地址的值时，由于不在cache里面，所以需要读取0x80到0x8f地址的数据填充到cache里面，由于之前cache里面已经保存了0x40地址的数据，所以数据发生了替换
• 当data1和data2相加后，需要把结果赋值给result，写入到0x00中，这时cache又发生了替换
• 所以当cache使用直接映射缓存时，会发生严重的cache颠簸（不断发生cache line替换），严重影响性能。

1.5.2、全关联

当cache只有一个组，即主存中只有一个地址与n个cache line对应，称为全关联

1.5.3、组相连

为了解决cache直接映射方式中的高速缓存颠簸问题，组相连的高速缓存结构在现代处理器中得到了广泛的应用。

上图是两路cache，每一路cache都有4个cache line，每个组有两个cache line可以提供高速缓存行替换
当要发生高速缓存颠簸情况的时候，就有50%的概率可以不被替换，从而减小了高速缓存颠簸。

1.6、虚拟cache和物理cache

1.6.1、物理cache

当处理器查询MMU和TLB得到物理地址之后，只用物理地址去查询高速缓存，我们称为物理高速缓存。使用物理高速缓存的缺点就是处理器在查询MMU和TLB之后才能够访问高速缓存，增加了延迟。

1.6.2、虚拟cache

CPU使用虚拟地址来寻址高速缓存，我们成为虚拟高速缓存。处理器在寻址时，首先把虚拟地址发送到高速缓存中，若在高速缓存里找到需要的数据，那么就不再需要访问TLB和物理内存。处理器在寻址时，首先把虚拟地址发送到高速缓存中，若在高速缓存里找到需要的数据，那么就不再需要访问TLB和物理内存。

1.7、cache的分类

在查询cache的时候使用了index和tag，那么查询cache时用的是虚拟地址还是物理地址的index？当找到cache组的时候，我们用的是虚拟地址还是物理地址的tag来匹配cache line呢？

cache可以设计成通过虚拟地址来访问，也可以设计成通过物理地址来访问，这个在CPU设计时就确定下来了，并且对cache的管理有很大的影响。cache可以分成以下三类：

• VIVT(Virtual Index Virtual Tag) : 使用虚拟地址的index和tag，相当于虚拟高速缓存
• PIPT(Physical Index Physical Tag) : 使用物理地址的index和tag，相当于物理高速缓存
• VIPT(Virtual Index Physical Tag) : 使用虚拟地址的index和物理地址的tag

在早期的ARM处理器中采用的是VIVT的方式，不经过MMU的翻译，直接使用虚拟地址的index和tag来查找cache line，这种方式会导致cache别人的问题。也就是一个物理地址的内容可能出现在多个cache line中，当系统改变了虚拟地址到物理地址的映射时，需要清洗和无效这些cache，导致系统性能下降

1.7.1、VIPT的工作原理

现在很多cortex系列的处理器的L1 data cache采用VIPT方式，即CPU输出的虚拟地址同时会发送到TLB/MMU单元进行地址翻译，以及在高速缓存中进行索引和查询高速缓存。在TLB/MMU单元里，会把虚拟页帧号（VPN）翻译成物理页帧号（PFN），与此同时，虚拟地址的索引域和偏移会用来查询高速缓存。这样高速缓存和TLB/MMU可以同时工作，当TLB/MMU完成地址翻译后，再用物理标记域来匹配高速缓存行。采用VIPT方式的好处之一是在多任务操作系统中，修改了虚拟地址到物理地址映射关系，不需要把相应的高速缓存进行无效操作。

1.7.2、VIVT（虚拟高速缓存）造成的重名同名问题

重名问题：（不同虚拟地址指向相同的物理地址）
重名问题是怎么产生的呢？我们知道，在操作系统中，多个不同的虚拟地址有可能映射相同的物理地址。由于采用VIPI架构，那么这些不同的虚拟地址会占用高速缓存中不同的高速缓存行（cache line），但是它们对应的是相同的物理地址，这样会引发问题：一是浪费了高速缓存空间，造成高速缓存等效容量的减少，减低整体性能；第二，在执行写操作的时候，只更新其中一个虚拟地址对应的高速缓存，而其他虚拟地址对应的高速缓存并没有更新。那么处理器访问其他虚拟地址可能得到旧数据。

举个例子，比如我们的cache使用的是VIPI，VA1映射到PA，VA2也映射到PA，那么在cache中有可能同时缓存了VA1和VA2两个虚拟地址。当程序往VA1虚拟地址写入数据的时候，PA的内容会被更改，但是虚拟地址VA2对应的cache里面还保存着旧数据，当CPU去读取VA2的值时，读到就是旧地址。一个物理地址在VIPI中就保存了两份数据，这样会产生歧义。

同名问题：（相同的虚拟地址指向不同的物理地址）
同名问题是怎么产生的呢？ 同名问题指的是相同的虚拟地址对应着不同的物理地址。因为操作系统中不同的进程会存在很多相同的虚拟地址，而这些相同的虚拟地址在经过MMU转换后得到不同的物理地址，这样就产生了同名问题。

同名问题最常出现的地方就是进程切换。当一个进程切换到另一个进程时，新进程使用虚拟地址来访问cache的话，新进程会访问到旧进程遗留下来的高速缓存，这些高速缓存数据对于新进程来说是错误和没用的，解决办法就是在进程切换时把旧进程遗留下来的高速缓存都设置为无效，这样就能保证新进程执行时得到一个干净的虚拟高速缓存。同样，TLB也需要设置为无效，因为新进程在切换后得到一个旧进程使用的TLB，里面存放了旧进程和虚拟地址到物理地址的转换结果。

重名问题实际上是多个虚拟地址映射到同一个物理地址引发的歧义问题，而同名问题是一个虚拟地址可能因为进程切换等原因映射到不同的物理地址而引发的问题。

1.7.3、VIPT的重名问题

采用VIPT方式也有可能导致高速缓存别人的问题。

使用虚拟地址的index来查找高速缓存的cache line，这时有可能导致多个高速缓存组映射到同一个物理地址上。
以Linux内核为例，它是以4KB大小为一个页面进行管理的，那么对于一个页来说，虚拟地址和物理地址的低

1.8、cache一致性

什么是cache一致性？

cache一致性，需要保证系统中所有的CPU、所有的bus主从，例如GPU、DMA等，他们观察到的内存是一直的。举个例子，外设都用DMA，如果你的软件通过CPU来产生一些数据，然后相通过DMA来搬移这些数据到外设，如果CPU和DMA看到的数据不一致，比如CPU产生的数据还在cache里，而DMA却从内存中直接去搬移数据，那么DMA就会看到一个旧的数据，那么就产生了数据的不一致性。

1.8.1、cache一致性的解决方案

一般情况下实现系统cahce一致性有三种方案

• 关闭cache
  这是最简单的办法，但是它会严重影响性能。以上面那个例子为例，CPU产生数据，然后把数据先放入到DMA buffer里，如果采用关闭cache的方式，那么CPU在产生数据的过程中，CPU不能利用cache，这就会严重影响到性能
• 软件管理cache一致性
  这是最常用的方式。软件需要在合适的时候去clean or flush dirty cache，或者invalidata old data
  优点：硬件RTL实现简单
  缺点：软件复杂度增加，软件需要手动clean/flush cache或者invalidate cache
  增加调试难度
  降低性能，增加功耗
• 硬件管理cache一致性
  对于多核之间的cache一致性，通常的做法就是在多核里实现一个MESI协议，实现一种snoop的控制单元。

1.8.2、MESI协议

目前，ARM或者x86等处理器广泛使用MESI协议来维护高速缓存一致性。MESI协议的名字源于该名字使用修改（Modified, M），独占（Exclusive， E），共享（Shared，S）和失效（Invalid， I）四个状态。高速缓存中的状态比如是上述四个状态中的一个。MESI状态机的转换是硬件自动实现的

高速缓存行（cache line）中有两个标志：脏（dirty）和干净（valid）。它们很好地描述了高速缓存和内存之间的数据关系，如数据是否有效、数据是否被修改过。在MESI协议中，每个高速缓存行有四个状态，可以使用高速缓存行中的2位地址来表示这些状态（00 01 10 11）。

1.8.3、MESI的操作

1.8.3.1 初始化状态为I的cache line

1.8.3.1.1、发起读操作

我们假设CPU0发起本地读请求，CPU0发出读PrRd请求，因为本地cache line是无效状态，所以呢，在总线上产生一个BusRd信号，然后广播给其它的CPU，其它CPU会鉴定到该请求并且检查它们的缓存来判断是否拥有该副本，下面分四种情况来考虑。

• 如果CPU1发现本地cache，并且这个cache line的状态为S，那么在总线上回复一个FlushOpt信号，即把当前cache line的内容发现到总线上，那么刚才发出PrRd读信号的CPU0就能得到这个cache line的数据，然后CPU0的状态就由I变成了S，CPU1的状态依旧是S，保持不变
• 假设CPU2发现本地副本并且高速缓存行的状态为E，则在总线上回复FlushOpt信号，即把当前cache line的内容发送到总线上，CPU2上的cache line的状态由E变成了S，CPU0状态由I变成了S。
• 假设CPU3发现本地副本并且cache line的状态为M，将数据更新到内存，然后CPU0再获取到这个cache line中的数据，状态由I变成S，CPU3状态由M变成S。
• 如果CPU1、CPU2、CPU3上的cache line都没有缓存数据，状态都是I，那么CPU0会从内存中读取数据到L1 cache，然后把cache line状态设置为E。

1.8.3.1.2、收到总线读信号

• 如果一个处于状态I的cache line收到一个总线读操作，它的状态不变，并且回应一个ACK信号，表示：我这没有数据副本。

1.8.3.1.3、发起写操作

我们假设CPU0发起本地写请求

• 由于本地cache line是无效的，所以CPU0发现BusRdX信号到总线上，这种情况本地写操作变成了总线写了，我们要看其他CPU的情况
• 其他CPU收到CPU0的写请求，先检查自己的cache中是否有缓存副本，广播应答信号。
• 假设CPU1上有这份数据的副本，且状态为S，CPU1收到CPU0的写信号，会恢复一个flushopt信号，把数据发送到总线上，然后把自己的cache line设置为无效，状态变成I，然后广播应答信号
• 假设CPU2上有这份数据的副本，且状态为E，CPU2收到CPU0的写信号后，会恢复一个flushopt信号，把数据发送到总线上，然后把自己的cache line设置为无效，状态变成I，然后广播应答信号
• 假设CPU3上有这份数据的副本，状态为M，CPU3收到CPU0的写信号后，会把自己cache line的内存flush为内存，然后自己的状态变成I，然后广播应答信号
• 若其他CPU上也没有这份数据的副本，也要广播一个应答信号
• CPU0会收到其他CPU的所有应答信号，确认其他CPU上没有这个数据的缓存副本后，CPU会从总线上或者内存中读取这个数据

1.8.3.1.4、收到总线写操作

如果处于I状态的cache line收到一个总线写操作，因为它本来就没有有效的数据副本，所以它的状态不变，回应一个ACK信号

1.8.3.2、初始化状态为M的cache line

• 收到一个总线读的信号
  假设CPU0上的cache line的状态为M，而在其他CPU上没有这个数据的副本，当CPU1想要读这份数据时，CPU1会发起一次总线读操作，如果CPU0上有这个数据的副本，那么CPU0收到信号后把cache line的内容发送到总线上，然后CPU1就获取这个cache line的内容。另外，CPU0会把相关内容发送到主内存中，把cache line的内容写入主内存中。CPU0的状态从M变成S
• 收到一个总线写的信号
  假设CPU0上有副本并且状态为M，而其他CPU上没有这个数据的副本。如果CPU1想要更新（写）这份数据，CPU1就会发起一个总线写操作。
  1、如果CPU0上有这个数据的副本，COU0收到总线写信号后，把自己的cache line的内容发送到内存控制器，并把该cache line的内容写入到主存中，CPU0上cache line状态变成I
  2、CPU1从总线或者内存中读取回数据到本地cache line，然后修改自己本地cache line的内容，CPU1的状态变成M

1.8.3.3、初始化状态为S的cache line

1.8.3.4、初始化状态为E的cache line