作者丨smcdef源码丨http://www.wowotech.net/memory_management/458.html今天探索的话题是缓存。我们围绕几个问题展开。为什么需要缓存？如何判断一个数据是否命中缓存？缓存有哪些类型，有什么区别？对于没有接触过底层技术的朋友，可能没有听说过缓存。毕竟缓存的存在对程序员来说是透明的。在接触缓存之前，为您准备段代码分析。intarr[10][128]；对于(i=0;i<10;i++)对于(j=0;j<128;j++);arr[i][j]=1;如果你学过C/C++语言，这段代码自然不会陌生。所以干脆把arr数组的所有元素都设置为1。有没有想过这段代码有下面这样的写法。intarr[10][128];for(i=0;i<128;i++)for(j=0;j<10;j++);arr[j][i]=1;功能是一模一样的，但是我们一直在重复第一种写法（可能很多书也建议这样编码），有没有想过这是什么原因？文章的主角是缓存，想必你已经猜到答案了。那么缓存是如何影响这两段代码的呢？为什么我们需要高速缓存？在思考缓存是什么之前，我们先思考第一个问题：我们的程序是如何工作的？我们应该知道程序运行在RAM中，而RAM就是我们常说的DDR（如DDR3、DDR4等）。我们称之为主存（mainmemory）。当我们需要运行一个进程时，我们会先将可执行程序从Flash设备（如eMMC、UFS等）加载到主存中，然后开始执行。CPU内部有一堆通用寄存器（registers）。如果CPU需要给一个变量加1（假设地址为A），一般分为以下三个步骤：CPU从主存中读取地址A的数据到内部通用寄存器x0（其中之一ARM64架构的通用寄存器）。通用寄存器x0加1。CPU将通用寄存器x0的值写入主存。我们可以这样表述这个过程：实际上，在现实中，CPU通用寄存器和主存的速度是有很大差别的。两者之间的速度大致如下：CPU寄存器的速度一般小于1ns，主存的速度一般在65ns左右。速度相差近百倍。所以，上面举例的3个步骤中，第1步和第3步其实很慢。当CPU尝试从主存加载/存储时，由于主存的速度限制，CPU不得不等待这漫长的65ns时间。如果我们能够提高主存的速度，系统的性能将会得到很大的提升。现在的DDR存储设备动辄只有几GB，容量很大。如果我们使用更快的材料来制造更快的主存储器，并且具有几乎相同的容量。其成本将大幅上升。我们正在努力提高主内存的速度和容量，并希望它便宜，这有点牵强。因此，我们有一个折衷的方法，就是做一个速度极快但容量极小的存储设备。那么它的成本就不会太高。我们称这种存储设备为缓存内存。在硬件上，我们将缓存放在CPU和主存之间，作为主存数据的缓存。当CPU试图从主存加载/存储数据时，CPU会先从缓存中检查对应地址的数据是否缓存在缓存中。如果它的数据缓存在缓存中，则直接从缓存中获取数据返回给CPU。当有缓存时，上述程序运行的例子流程将变为：CPU与主存直接传输数据，改为CPU与缓存直接传输数据。Cache负责主存与主存之间的数据传输。多级缓存内存缓存的速度也在一定程度上影响着系统的性能。一般来说，缓存的速度可以达到1ns，几乎可以与CPU寄存器的速度媲美。然而，这是否满足了人们对性能的追求呢？一点也不。当我们想要的数据没有缓存在缓存中时，从主存中加载数据仍然需要很长时间。为了进一步提高性能，引入了多级缓存。前述缓存称为L1缓存（一级缓存）。我们在L1缓存后面连接L2缓存，在L2缓存和主存之间连接L3缓存。等级越高，速度越慢，容量越大。但是速度相对于主存还是非常快的。各级缓存速度之间的关系如下：经过三级缓存缓冲后，每级缓存与主存的最小速度差也逐渐减小。在真实系统中，各级缓存在硬件上是如何关联的？我们来看一下Cortex-A53架构上各级缓存之间的硬件抽象框图如下：在Cortex-A53架构上，L1缓存分为独立的指令缓存（ICache）和数据缓存（DCache）。一级缓存是CPU私有的，每个CPU都有一个一级缓存。一个集群中的所有CPU共享一个L2缓存，不管是指令还是数据都可以缓存。L3缓存在所有集群之间共享。L3缓存通过总线连接到主存。多级缓存之间的协作首先引入两个名词概念，hit和miss。CPU要访问的数据缓存在缓存中，称为“命中”，反之称为“未命中”。多级缓存如何协同工作？我们假设所考虑的系统现在只有两级缓存。当CPU试图从某个地址加载数据时，它首先检查它是否从L1缓存中命中，如果命中则将数据返回给CPU。如果一级缓存不存在，则继续从二级缓存开始查找。当二级缓存命中时，数据返回给一级缓存和CPU。如果二级缓存也缺失，不幸的是，我们需要从主存中加载数据，并将数据返回给二级缓存、一级缓存和CPU。这种多级缓存工作方式称为包容性缓存。某个地址的数据可以存储在多级缓存中。与inclusivecache相对应的是exclusivecache，它保证了某个地址的数据缓存只会存在于多级缓存的一级中。也就是说，任何地址的数据都不能同时缓存在L1和L2缓存中。直接映射缓存（Directmappedcache）我们继续介绍一些缓存相关的术语。缓存的大小称为缓存大小，表示缓存可以缓存的最大数据的大小。我们将缓存分成许多相等的块。每个块的大小称为一个缓存行，它的大小就是缓存行大小。例如，一个64字节的缓存。如果我们把64Bytes平均分成64块，那么cacheline就是1byte，一共有64条cacheline。如果我们把64Bytes平均分成8个block，那么cacheline就是8个bytes，一共有8个cacheline。在目前的硬件设计中，一般缓存行的大小为4-128Byts。为什么没有1字节？原因我们稍后再说。这里要注意的一点是缓存行是缓存和主存之间数据传输的最小单位。这意味着什么？当CPU试图加载一个字节的数据时，如果缓存缺失，缓存控制器会一次性从主存中加载缓存行大小的数据到缓存中。例如，缓存行大小为8个字节。即使CPU读取了一个字节，缓存丢失后，缓存也会从主存中加载8个字节来填满整个缓存行。为什么？稍后我会明白的。我们假设下面的解释都是针对64Bytes的缓存，缓存行大小为8字节。我们可以把这个缓存看成一个数组。该数组共有8个元素，每个元素的大小为8个字节。如下图：现在我们考虑一个问题，CPU从地址0x0654读取一个字节，缓存控制器如何判断数据是否命中缓存？与主内存相比，缓存大小是微不足道的。所以缓存必须只缓存主存中非常小的一部分数据。我们如何根据地址在有限大小的缓存中查找数据？现在硬件采用的做法是对地址进行哈希处理（可以理解为地址取模运算）。接下来我们看看它是怎么做的？我们一共有8条cacheline，cacheline的大小是8Bytes。所以我们可以用地址的低3位（如上图中地址蓝色部分所示）来寻址8个字节中的某个字节。我们称这部分为位组合偏移量。同样，8行cacheline，为了覆盖所有行。我们需要3位（如上图中地址黄色部分）来找到某一行，这部分地址称为索引。现在我们知道，如果两个不同的地址具有完全相同的地址的bit3-bit5，那么这两个地址经过硬件哈希后会找到相同的缓存行。因此，当我们找到缓存行时，仅仅意味着我们访问的地址对应的数据可能存在于这个缓存行中，但也有可能是其他地址对应的数据。因此，我们引入标签数组区域，标签数组与数据数组一一对应。每条缓存线对应一个唯一的tag，tag存储的是整个地址位宽减去index和offset使用的bits的剩余部分（如上图中地址绿色部分）。标记、索引和偏移量的组合可以唯一确定一个地址。因此，当我们根据地址中的索引位找到cacheline时，我们取出当前cacheline对应的tag，然后与address中的tag进行比较。如果它们相等，则意味着缓存命中。如果不相等，说明当前cacheline在其他地址存储了数据，即cachemiss。上图中我们看到tag的值为0x19，等于地址中的tag部分，所以这次访问会命中。由于tag的引入，回答了我们之前的一个问题“为什么硬件缓存行不做成一个字节？”。这样会导致硬件成本增加，因为本来8个字节对应一个tag，现在需要8个tag，占用内存很大。从图中我们可以看出，在tag的旁边有一个valid位，用来表示cacheline中的数据是否有效（例如：1表示有效；0表示无效）。系统刚启动时，缓存中的数据应该是无效的，因为还没有缓存数据。缓存控制器可以根据有效位来确认当前缓存行数据是否有效。因此，上面的比较标签在确认是否命中缓存行之前，也会检查valid位是否有效。比较标签只有在它们有效时才有意义。如果无效，则直接判定缓存丢失。在上面的示例中，缓存大小为64字节，缓存行大小为8字节。offset、index、tag分别使用3位、3位和42位（假设地址宽度为48位）。现在让我们看另一个例子：512Bytes缓存大小，64Bytes缓存行大小。按照前面的地址划分方式，offset、index、tag分别使用6位、3位和39位。如下图所示：直接映射缓存的优缺点直接映射缓存在硬件设计上会更简单，因此成本会更低。根据直接映射缓存的工作方式，我们可以画出主存地址0x00-0x88对应的缓存分布图：可以看出地址0x00-0x3f对应的数据可以覆盖整个缓存。地址0x40-0x7f的数据也覆盖了整个缓存。现在我们来思考一个问题，如果一个程序试图依次访问地址0x00、0x40、0x80，那么缓存中的数据会发生什么情况呢？首先我们要明白，0x00、0x40、0x80地址中的index部分是一样的。所以这三个地址对应的cacheline是相同的。因此，当我们访问0x00地址时，cache就会丢失，然后数据就会从主存加载到cache中的cacheline0。当我们访问地址0x40时，我们仍然索引到缓存中第0行的缓存行。由于此时cacheline存放的是地址0x00对应的数据，所以此时cache仍然会缺失。然后从主存中加载0x40地址数据到第一个缓存行。同理，如果继续访问0x80地址，缓存还是会丢失。这相当于每次访问数据时都从主存中读取，所以缓存的存在并不能提高性能。当访问地址0x40时，缓存在地址0x00的数据将被替换。这种现象称为缓存抖动（cachethrashing）。为了解决这个问题，我们引入了多路集合关联缓存。我们首先研究最简单的双向集合相联缓存的工作原理。对于双向set-associatedcache，我们仍然假设缓存大小为64Bytes，缓存行大小为8Bytes。路是什么概念。我们把缓存平均分成多个部分，每个部分是一种方式。所以，双向集相联缓存（Two-waysetassociativecache）就是把缓存分成两部分，每部分32Bytes。如下图所示：缓存分为2路，每路包含4条缓存行。我们将具有相同索引的所有缓存行分组为一个组。比如上图中的一个group有两条cacheline，一共有4个group。我们仍然假设从地址0x0654读取一个字节的数据。由于cachelinesize是8Bytes，所以offset需要3bits，和之前的直接映射cache一样。区别在于索引。在双向set-associatedcache中，索引只需要2位，因为在一种方式下只有4条cacheline。上面的例子是根据index（从0开始计数）找到第二条cacheline，第二条cacheline对应两条cacheline，分别对应0路和1路。因此索引也可以称为集合索引（groupindex）。先根据索引找到set，然后取出group中所有cacheline对应的tag，与地址中的tag部分进行比较。如果其中一个相等，则表示命中。因此，双向set-associatedcache和direct-mappedcache最大的区别就是首地址对应的数据可以对应两个cacheline，而direct-mappedcache中的一个地址只对应一个cache线。那么这到底有什么用呢？双向集合关联缓存的优缺点双向集合关联缓存的硬件成本高于直接映射缓存。因为每次比较tag都需要比较多个cacheline对应的tag（有的硬件可能还会进行并行比较来提高比较速度，增加了硬件设计的复杂度）。为什么我们需要双向集关联缓存？因为它可以帮助减少缓存抖动的可能性。那么它是如何降低的呢？根据双向组连接缓存的工作方式，我们可以画出主存地址0x00-0x4f对应的缓存分布图：我们还是考虑直接映射缓存区的问题“如果一个程序试图访问按顺序地址0x00、0x40、0x80，缓存中的数据会发生什么变化？”。现在地址0x00的数据可以加载到way1，0x40可以加载到way0，这样是不是在一定程度上避免了直接映射缓存的尴尬情况？在双向组关联缓存的情况下，地址0x00和0x40处的数据缓存在缓存中。试想一下，如果我们是4路set-associatedcache，后面继续访问0x80，也有可能被缓存了。因此，当缓存大小不变时，group-associativecache在最坏情况下的性能提升与direct-mappedcache相同。大多数情况下，group-associatedcache的效果要好于direct-mappedcache。同时，它降低了缓存抖动的频率。在某种程度上，直接映射缓存是组关联??缓存的一种特例，其中每个组只有一个缓存行。因此，直接映射缓存也可以称为单向组关联缓存。全关联缓存（Fullassociativecache）既然组关联缓存那么好，如果所有的缓存行都在一个组里。性能不是更好吗。是的，这种缓存就是全链接缓存。我们仍然以64Byts缓存为例。由于所有缓存行都在一个组中，因此地址中不需要设置索引部分。因为，可供你选择的只有一组，间接意味着你别无选择。我们将地址的标记部分与所有缓存行对应的标记进行比较（硬件可能并行或串行比较）。哪个标签更相等意味着命中某个缓存行。因此，在全链接缓存中，任何地址的数据都可以缓存在任何缓存行中。因此，这可以最大限度地减少缓存抖动的频率。但硬件成本也较高。一个4-wayset-associatedcache实例问题考虑这样一个问题，大小为32KB的4-wayset-associatedcache，cachelinesize为32Bytes。请思考问题：有多少组？假设地址宽度为48位，index、offset、tag分别占用多少位？一共有4条路，所以每条路的大小都是8KB。高速缓存行大小为32字节，因此有256个组（8KB/32字节）。由于高速缓存行大小为32字节，因此偏移量需要5位。总共有256组，所以索引需要8位，剩下的就是tag部分，占35位。这个缓存可以画出如下：缓存分配策略缓存分配策略（Cacheallocationpolicy）是指我们应该在什么时候为数据分配缓存行。缓存分配策略分为读和写两种情况。读取分配（readallocation）当CPU读取数据时，会发生cachemiss。在这种情况下，会分配一个缓存行来缓存从主存读取的数据。默认情况下，所有缓存都支持读取分配。写分配（writeallocation）当CPU写数据，发生cachemiss时，会考虑写分配策略。当我们不支持writeallocation时，write命令只会更新主存数据，然后就结束了。当支持写分配时，我们先从主存加载数据到缓存行（相当于先做一个读分配动作），然后更新缓存行中的数据。缓存更新策略缓存更新策略（Cacheupdatepolicy）是指当缓存命中发生时写操作应该如何更新数据。有两种类型的缓存更新策略：直写式和回写式。直写（writethrough）当CPU执行store指令命中缓存时，我们更新缓存中的数据，同时更新主存中的数据。高速缓存和主存中的数据总是一致的。回写（writeback）当CPU执行store指令命中缓存时，我们只更新缓存中的数据。并且在每个cacheline中都会有一个bit来记录数据是否被修改过，称为dirtybit（通过上一张图看，cacheline旁边有一个D就是dirtybit）。我们将设置脏位。主内存中的数据仅在替换高速缓存行或指示清理操作时更新。因此，主存中的数据可能是未修改的数据，而修改后的数据则位于缓存行中。高速缓存和主存中的数据可能不一致。同时思考一个问题，为什么cachelinesize是cachecontroller和主存之间数据传输的最小单位？这也是因为每个缓存行只有一个脏位。这个脏位表示整个缓存行是否被修改。示例假设我们有一个64Bytes的直接映射缓存，缓存行大小为8Bytes，使用了写分配和回写机制。当CPU从地址0x2a读取一个字节时，缓存中的数据会发生怎样的变化？假设当前缓存状态如下图所示：根据索引找到对应的缓存行，对应标签部分的有效位合法，但是标签的值不相等，所以一个失踪发生。此时我们需要从地址0x28加载8个字节的数据到缓存行中。但是，我们发现设置了当前缓存行的脏位。因此，不能简单地丢弃缓存行中的数据。由于回写机制，我们需要将缓存中的数据0x11223344写入地址0x0128（这个地址是根据tag中的值和所在的缓存行计算出来的）。流程如下图所示：当回写操作完成后，我们将主存中从地址0x28开始的8个字节加载到缓存行中，并清除脏位。然后根据偏移量找到0x52返回给CPU。
