Linux 内存管理（一）Cache

分类于 ， ， 阅读次数： Waline： 本文字数： 4.8k 阅读时长 ≈ 18 分钟

原图

声明： 本文转载自 Cache 的基本原理 和 Cache 组织方式

多级 cache 存储结构

我们在 L1 cache 后面连接 L2 cache，在 L2 cache 和主存之间连接 L3 cache。等级越高，速度越慢，容量越大。不同等级 cache 速度之间关系如下：

经过 3 级 cache 的缓冲，各级 cache 和主存之间的速度最萌差也逐级减小。在一个真实的系统上，各级 cache 之间硬件上是如何关联的呢？我们看下 Cortex-A53 架构上各级 cache 之间的硬件抽象框图如下：

在 Cortex-A53 架构上，L1 cache 分为单独的 instruction cache（ICache）和 data cache（DCache）。L1 cache 是 CPU 私有的，每个 CPU 都有一个 L1 cache。一个 cluster 内的所有 CPU 共享一个 L2 cache，L2 cache 不区分指令和数据，都可以缓存。所有 cluster 之间共享 L3 cache。L3 cache 通过总线和主存相连。

多级 cache 之间的配合工作

首先引入两个名词概念，命中和缺失。 CPU 要访问的数据在 cache 中有缓存，称为“命中” (hit)，反之则称为“缺失” (miss)。多级 cache 之间是如何配合工作的呢？我们假设现在考虑的系统只有两级 cache。

  • inclusive cache（某一地址的数据可能存在多级缓存中） 当 CPU 试图从某地址 load 数据时，首先从 L1 cache 中查询是否命中，如果命中则把数据返回给 CPU 如果 L1 cache 缺失，则继续从 L2 cache 中查找。当 L2 cache 命中时，数据会返回给 L1 cache 以及 CPU 如果 L2 cache 也缺失，很不幸，我们需要从主存中 load 数据，将数据返回给 L2 cache、L1 cache 及 CPU

  • exclusive cache 这种 cache 保证某一地址的数据缓存只会存在于多级 cache 其中一级

直接映射缓存 (Direct mapped cache)

cache 的大小称之为 cahe size。我们将 cache 平均分成相等的很多块，每一个块大小称之为 cache line。现在的硬件设计中，一般 cache line 的大小是 4-128 Byts。

注意，cache line 是 cache 和主存（非 CPU）之间数据传输的最小单位。

我们假设下面的讲解都是针对 64 Bytes 大小的 cache，并且 cache line 大小是 8 字节。我们可以类似把这块 cache 想想成一个数组，数组总共 8 个元素，每个元素大小是 8 字节。就像下图这样。

现在我们考虑一个问题，CPU 从 0x0654 地址读取一个字节，cache 控制器是如何判断数据是否在 cache 中命中呢？现在硬件采取的做法是对地址进行散列（可以理解成地址取模操作）。我们接下来看看是如何做到的？

我们一共有 8 行 cache line，cache line 大小是 8 Bytes。所以我们可以利用地址低 3 bits（如上图地址蓝色部分）用来寻址 8 bytes 中某一字节，我们称这部分 bit 组合为 offset。同理，8 行 cache line，为了覆盖所有行。我们需要 3 bits（如上图地址黄色部分）查找某一行，这部分地址部分称之为 index。

如果两个不同的地址，其地址的 bit3-bit5 如果完全一样的话，那么这两个地址经过硬件散列之后都会找到同一个 cache line。所以，我们又引入 tag array 区域。每一个 cache line 都对应唯一一个 tag，tag 中保存的是整个地址位宽去除 index 和 offset 使用的 bit 剩余部分（如上图地址绿色部分）。

tag、index 和 offset 三者组合就可以唯一确定一个地址了。因此，当我们根据地址中 index 位找到 cache line 后，取出当前 cache line 对应的 tag，然后和地址中的 tag 进行比较，如果相等，这说明 cache 命中。如果不相等，说明当前 cache line 存储的是其他地址的数据，这就是 cache 缺失。

我们可以从图中看到 tag 旁边还有一个 valid bit，这个 bit 用来表示 cache line 中数据是否有效（例如：1 代表有效；0 代表无效）。所以，上述比较 tag 确认 cache line 是否命中之前还会检查 valid bit 是否有效。只有在有效的情况下，比较 tag 才有意义。如果无效，直接判定 cache 缺失。

  • offset 用于在一个 cache line 里确定是哪一个字节
  • index 寻址 cache line（确定是哪一个 cache line）
  • tag array 全地址匹配
  • valid bit 表示 cache 中的数据是否有效

上面的例子中，cache size 是 64 Bytes 并且 cache line size 是 8 bytes。offset、index 和 tag 分别使用 3 bits、3 bits 和 42 bits（假设地址宽度是 48 bits）。我们现在再看一个例子：512 Bytes cache size，64 Bytes cache line size。根据之前的地址划分方法，offset、index 和 tag 分别使用 6 bits、3 bits 和 39 bits。如下图所示。

直接映射缓存的优缺点

直接映射缓存在硬件设计上会更加简单，因此成本上也会较低。根据直接映射缓存的工作方式，我们可以画出主存地址 0x00-0x88 地址对应的 cache 分布图。

我们可以看到，地址 0x00-0x3f 地址处对应的数据可以覆盖整个 cache。0x40-0x7f 地址的数据也同样是覆盖整个 cache。我们现在思考一个问题，如果一个程序试图依次访问地址 0x00、0x40、0x80，cache 中的数据，每次访问数据都要从主存中读取，所以 cache 的存在并没有对性能有什么提升。这种现象叫做 cache 颠簸（cache thrashing）。针对这个问题，我们引入多路组相连缓存。

两路组相连缓存 (Two-way set associative cache)

我们依然假设 64 Bytes cache size，cache line size 是 8 Bytes。什么是路（way）的概念。我们将 cache 平均分成多份，每一份就是一路。因此，两路组相连缓存就是将 cache 平均分成 2 份，每份 32 Bytes。如下图所示。

cache 被分成 2 路，每路包含 4 行 cache line。我们将所有索引一样的 cache line 组合在一起称之为组。例如，上图中一个组有两个 cache line，总共 4 个组。我们依然假设从地址 0x0654 地址读取一个字节数据。由于 cache line size 是 8 Bytes，因此 offset 需要 3 bits，这和之前直接映射缓存一样。不一样的地方是 index，在两路组相连缓存中，index 只需要 2 bits，因为一路只有 4 行 cache line。上面的例子根据 index 找到第 2 行 cache line（从 0 开始计算），第 2 行对应 2 个 cache line，分别对应 way 0 和 way 1。因此 index 也可以称作 set index（组索引）。先根据 index 找到 set，然后将组内的所有 cache line 对应的 tag 取出来和地址中的 tag 部分对比，如果其中一个相等就意味着命中。

因此，两路组相连缓存较直接映射缓存最大的差异就是：第一个地址对应的数据可以对应 2 个 cache line，而直接映射缓存一个地址只对应一个 cache line。那么这究竟有什么好处呢？

两路组相连缓存优缺点

两路组相连缓存的硬件成本相对于直接映射缓存更高。因为其每次比较 tag 的时候需要比较多个 cache line 对应的 tag（某些硬件可能还会做并行比较，增加比较速度，这就增加了硬件设计复杂度）。好处是可以有助于降低 cache 颠簸可能性。根据两路组相连缓存的工作方式，我们可以画出主存地址 0x00-0x4f 地址对应的 cache 分布图。

全相连缓存 (Full associative cache)

既然组相连缓存那么好，如果所有的 cache line 都在一个组内。岂不是性能更好。是的，这种缓存就是全相连缓存。

这可以最大程度的降低 cache 颠簸的频率。但是硬件成本上也是更高。

Cache 分配策略 (Cache allocation policy)

cache 的分配策略是指我们什么情况下应该为数据分配 cache line。cache 分配策略分为读和写两种情况。

  • 读分配 (read allocation) 当 CPU 读数据时，发生 cache 缺失，这种情况下都会分配一个 cache line 缓存从主存读取的数据。默认情况下，cache 都支持读分配

  • 写分配 (write allocation) 当 CPU 写数据发生 cache 缺失时，才会考虑写分配策略。当我们不支持写分配的情况下，写指令只会更新主存数据，然后就结束了。当支持写分配的时候，我们首先从主存中加载数据到 cache line 中（相当于先做个读分配动作），然后会更新 cache line 中的数据

Cache 更新策略 (Cache update policy)

cache 更新策略是指当发生 cache 命中时，写操作应该如何更新数据。cache 更新策略分成两种：写直通和回写。

  • 写直通 (write through) 当 CPU 执行 store 指令并在 cache 命中时，我们更新 cache 中的数据并且更新主存中的数据。cache 和主存的数据始终保持一致

  • 写回 (write back) 当 CPU 执行 store 指令并在 cache 命中时，我们只更新 cache 中的数据。并且每个 cache line 中会有一个 bit 位记录数据是否被修改过，称之为 dirty bit（翻翻前面的图片，cache line 旁边有一个 D 就是 dirty bit）。我们会将 dirty bit 置位。主存中的数据只会在 cache line 被替换或者显示的 clean 操作时更新。因此，主存中的数据可能是未修改的数据，而修改的数据躺在 cache 中。cache 和主存的数据可能不一致

同时思考个问题，为什么 cache line 大小是 cache 控制器和主存之间数据传输的最小单位呢？这也是因为每个 cache line 只有一个 dirty bit。这一个 dirty bit 代表着整个 cache line 是否被修改的状态。

Cache 地址

我们都知道 cache 控制器根据地址查找判断是否命中，这里的地址究竟是虚拟地址 (virtual address，VA) 还是物理地址 (physical address，PA)？

虚拟高速缓存 (VIVT)

我们首先介绍的是虚拟高速缓存，这种 cache 硬件设计简单。在 cache 诞生之初，大部分的处理器都使用这种方式。虚拟高速缓存以虚拟地址作为查找对象。如下图所示。

虚拟地址直接送到 cache 控制器，如果 cache hit。直接从 cache 中返回数据给 CPU。如果 cache miss，则把虚拟地址发往 MMU，经过 MMU 转换成物理地址，根据物理地址从主存 (main memory) 读取数据。 但是，正是使用了虚拟地址作为 tag，所以引入很多软件使用上的问题。 操作系统在管理高速缓存正确工作的过程中，主要会面临两个问题。歧义 (ambiguity) 和别名 (alias)。为了保证系统的正确工作，操作系统负责避免出现歧义和别名。

  • 歧义 (ambiguity)
    歧义是指不同的数据在 cache 中具有相同的 tag 和 index，这就产生了歧义（不同进程相同虚拟地址映射了不同物理地址）。当我们切换进程的时候，可以选择 flush 所有的 cache。flush cache 操作有两种：
    - 使主存储器有效。针对 write back 高速缓存，首先应该使主存储器有效，保证已经修改数据的 cacheline 写回主存储器，避免修改的数据丢失
    - 使高速缓存无效。保证切换后的进程不会错误的命中上一个进程的缓存数据

    因此，切换后的进程刚开始执行的时候，将会由于大量的 cache miss 导致性能损失。

  • 别名 (alias) 当不同的虚拟地址映射相同的物理地址，通俗点来说就是指同一个物理地址的数据被加载到不同的 cacheline 中就会出现别名现象。

针对共享数据所在页的映射方式采用 nocache 映射。例如上面的例子中，0x2000 和 0x4000 映射物理地址 0x8000 的时候都采用 nocache 的方式，这样不通过 cache 的访问，肯定可以避免这种问题。

物理高速缓存 (PIPT)

基于对 VIVT 高速缓存的认识，我们知道 VIVT 高速缓存存在歧义和名别两大问题。主要问题原因是：tag 取自虚拟地址导致歧义，index 取自虚拟地址导致别名。所以，如果想让操作系统少操心，最简单的方法是 tag 和 index 都取自物理地址。物理的地址 tag 部分是独一无二的，因此肯定不会导致歧义。而针对同一个物理地址，index 也是唯一的，因此加载到 cache 中也是唯一的 cacheline，所以也不会存在别名。我们称这种 cache 为物理高速缓存，简称 PIPT(Physically Indexed Physically Tagged)。PIPT 工作原理如下图所示。

CPU 发出的虚拟地址经过 MMU 转换成物理地址，物理地址发往 cache 控制器查找确认是否命中 cache。虽然 PIPT 方式在软件层面基本不需要维护，但是硬件设计上比 VIVT 复杂很多。因此硬件成本也更高。同时，由于虚拟地址每次都要翻译成物理地址，因此在查找性能上没有 VIVT 方式简洁高效，毕竟 PIPT 方式需要等待虚拟地址转换物理地址完成后才能去查找 cache。 在 Linux 内核中，可以看到针对 PIPT 高速缓存的管理函数都是空函数，无需任何的管理。

物理标记的虚拟高速缓存 (VIPT)

为了提升 cache 查找性能，我们不想等到虚拟地址转换物理地址完成后才能查找 cache。因此，我们可以使用虚拟地址对应的 index 位查找 cache，与此同时（硬件上同时进行）将虚拟地址发到 MMU 转换成物理地址。当 MMU 转换完成，同时 cache 控制器也查找完成，此时比较 cacheline 对应的 tag 和物理地址 tag 域，以此判断是否命中 cache。我们称这种高速缓存为 VIPT(Virtually Indexed Physically Tagged)。

VIPT 以物理地址部分位作为 tag，因此我们不会存在歧义问题。但是，采用虚拟地址作为 index，所以可能依然存在别名问题。是否存在别名问题，需要考虑 cache 的结构，我们需要分情况考虑。

  • VIPT Cache 为什么不存在歧义 在这里重点介绍下为什么 VIPT Cache 不存在歧义。假设以 32 位 CPU 为例，页表映射最小单位是 4KB。我们假设虚拟地址<12:4>位（这是一个有别名问题的 VIPT Cache) 作为 index，于此同时将虚拟地址<31:12>发送到 MMU 转换得到物理地址的<31:12>，这里我们把<31:12>作为 tag，并不是<31:13>。这地方很关键，也就是说 VIPT 的 tag 取决于物理页大小的剩余位数，而不是去掉 index 和 offset 的剩余位数。物理 tag 是惟一的，所以不存在歧义。

  • VIPT Cache 什么情况不存在别名 我们知道 VIPT 的优点是查找 cache 和 MMU 转换虚拟地址同时进行，所以性能上有所提升。歧义问题虽然不存在了，但是别名问题依旧可能存在，那么什么情况下别名问题不会存在呢？Linux 系统中映射最小的单位是页，一页大小是 4KB。那么意味着虚拟地址和其映射的物理地址的位<11...0>是一样的。针对直接映射高速缓存，如果 cache 的 size 小于等于 4KB，是否就意味着无论使用虚拟地址还是物理地址的低位查找 cache 结果都是一样呢？是的，因为虚拟地址和物理地址对应的 index 是一样的。这种情况，VIPT 实际上相当于 PIPT，软件维护上和 PIPT 一样。如果示例是一个四路组相连高速缓存呢？只要满足一路的 cache 的大小小于等于 4KB，那么也不会出现别名问题。

  • VIPT Cache 的别名问题 假设系统使用的是直接映射高速缓存，cache 大小是 8KB，cacheline 大小是 256 字节。这种情况下的 VIPT 就存在别名问题。因为 index 来自虚拟地址位<12...8>，虚拟地址和物理地址的位<11...8>是一样的，但是 bit12 却不一定相等。 假设虚拟地址 0x0000 和虚拟地址 0x1000 都映射相同的物理地址 0x4000。那么程序读取 0x0000 时，系统将会从物理地址 0x4000 的数据加载到第 0x00 行 cacheline。然后程序读取 0x1000 数据，再次把物理地址 0x4000 的数据加载到第 0x10 行 cacheline。这不，别名出现了。相同物理地址的数据被加载到不同 cacheline 中。

如何解决 VIPT Cache 别名问题

我们接着上面的例子说明。首先出现问题的场景是共享映射，也就是多个虚拟地址映射同一个物理地址才可能出现问题。我们需要想办法避免相同的物理地址数据加载到不同的 cacheline 中。如何做到呢？那我们就避免上个例子中 0x1000 映射 0x4000 的情况发生。我们可以将虚拟地址 0x2000 映射到物理地址 0x4000，而不是用虚拟地址 0x1000。0x2000 对应第 0x00 行 cacheline，这样就避免了别名现象出现。因此，在建立共享映射的时候，返回的虚拟地址都是按照 cache 大小对齐的地址，这样就没问题了。如果是多路组相连高速缓存的话，返回的虚拟地址必须是满足一路 cache 大小对齐。在 Linux 的实现中，就是通过这种方法解决别名问题。

不存在的 PIVT 高速缓存

按照排列组合来说，应该还存在一种 PIVT 方式的高速缓存。因为 PIVT 没有任何优点，却包含以上的所有缺点。

总结

VIVT Cache 问题太多，软件维护成本过高，是最难管理的高速缓存。所以现在基本只存在历史的文章中。现在我们基本看不到硬件还在使用这种方式的 cache。现在使用的方式是 PIPT 或者 VIPT。如果多路组相连高速缓存的一路的大小小于等于 4KB，一般硬件采用 VIPT 方式，因为这样相当于 PIPT，岂不美哉。当然，如果一路大小大于 4KB，一般采用 PIPT 方式，也不排除 VIPT 方式，这就需要操作系统多操点心了。

参考文献

https://zhuanlan.zhihu.com/p/102293437
https://zhuanlan.zhihu.com/p/107096130