Linux slab分配器和缓存性能

Question

Linux slab分配器和缓存性能

linuxmemorymemory-managementlinux-kernelslab

3

来自指南《理解Linux内核第三版》，第8.2.10章，Slab着色-

我们从第二章知道，同一硬件高速缓存行映射许多不同的RAM块。在本章中，我们还看到，相同大小的对象最终被存储在高速缓存的相同偏移量处。在不同slab内具有相同偏移量的对象将以相对较高的概率被映射到相同的高速缓存行中。因此，高速缓存硬件可能会浪费内存周期将同一高速缓存行中的两个对象来回传输到不同的RAM位置，而其他高速缓存行则未充分利用。slab分配器通过一种称为slab着色的策略来减少这种不良的高速缓存行为：将不同的任意值分配给slab，称为颜色。

(1) 我无法理解板块着色试图解决的问题。当正常进程访问数据时，如果数据不在缓存中并且遇到缓存未命中，则数据将与进程尝试访问的数据地址周围的数据一起提取到缓存中以提高性能。如何出现同一特定缓存行不断被交换的情况？进程保持访问两个不同的数据地址，位于两个不同内存区域的内存区域中相同偏移量的概率非常低。即使发生这种情况，缓存策略通常会根据某些议程（例如LRU，随机等）选择要交换的行。不存在这样的策略，可以根据正在访问的地址的最低有效位的匹配选择驱逐行。 (2) 我无法理解板块着色是如何从板块末尾到开头获取空闲字节，并导致第一个对象具有不同偏移量的不同板块来解决缓存交换问题的。 [已解决] 经过小调查，我相信我找到了我的问题的答案。答案已发布。

- izac89

3个回答

1

我想我明白了，答案与结合律有关。

缓存可以分成几个集合，每个集合只能缓存其中某一种类型的内存块。例如，set0将包含地址为8的倍数的内存块，set1将包含地址为12的倍数的内存块。这样做是为了提高缓存性能，避免每个地址都在整个缓存中搜索的情况。这样只需要搜索缓存的某个特定集合。

现在，从链接Understanding CPU Caching and performance中

引用：

从Henessey和Patterson的第377页上，缓存放置公式如下：（块地址）MOD（缓存中的集合数）

让我们来看一下内存块地址0x10000008（来自颜色为C的slabX）和内存块地址0x20000009（来自颜色为Z的slabY）。对于大多数N（cache中的集合数），计算<address> MOD <N>将产生不同的值，从而得到不同的集合以缓存数据。如果这些地址具有相同的最低有效位值（例如0x10000008和0x20000008），则对于大多数N，计算将产生相同的值，因此块将碰撞到同一个缓存集合中。

因此，通过在不同slab中的对象中保持不同的偏移量（颜色），slab对象将潜在地到达缓存中的不同集合，并且不会碰撞到同一集合中，从而提高整体缓存性能。

编辑: 此外，如果缓存是直接映射的，则根据维基百科CPU Cache，不存在缓存替换策略，并且模运算会产生内存块将被存储到的缓存块：

直接映射缓存在这种缓存组织中，主存储器中的每个位置只能进入缓存中的一个条目。因此，直接映射缓存也可以称为“单路组相联”缓存。它没有实际的替换策略，因为没有选择要驱逐哪个高速缓存条目的内容。这意味着，如果两个位置映射到同一条目，则它们可能不断地互相击败。虽然更简单，但直接映射缓存需要比关联缓存大得多才能提供相当的性能，并且它更加不可预测。设x为缓存中的块编号，y为内存块编号，n为缓存中的块数，则使用方程式x = y mod n进行映射。

- izac89

有用的信息。另外，如果能添加一些关于颜色如何在物理内存地址的集合位上结束的信息那就更好了（记住还有块偏移位和标记位）。可能需要对某个典型高速缓存进行具体示例的分析。 - YNG

我最近找到了原因。我看了你的回答，非常抱歉它不能说服我。除了举一个具体的例子之外，还有很多其他的答案。是的，也许对于这种情况来说是正确的。着色为所有块添加偏移量，避免两行（即A与B）的碰撞。但这肯定会导致A与C（另一个块/行，也有偏移）的碰撞。那么最终它是如何工作的呢？ - Victor Choy

0

假设你有一个256 KB的缓存，并且它使用一个超级简单的算法，其中缓存行=（真实地址AND 0x3FFFFF）。

现在，如果每个兆字节边界都有起始块，那么Slab 1中的第20项将会将Slab 2中的第20项从缓存中踢出，因为它们使用相同的缓存行标记。

通过偏移块，不太可能出现不同的块共享相同的缓存行标记。如果Slab 1和Slab 2都持有32字节对象，并且Slab 2偏移8字节，则其缓存标记永远不会完全等于Slab 1的。

我确定我的一些细节是错误的，但这就是它的价值所在。

- Zan Lynx

让我看看我是否正确理解了你的意思；考虑到 slab0 切片地址为 0x0、0x20、0x40 等等。slab1 切片地址为 0x8、0x28、0x48 等等。使用你提供的简单缓存行，不会浪费任何缓存行，因为没有两个地址会给出相同的结果，对吗？ - izac89

在了解了缓存策略和缓存组织之后，我并不认为你的回答符合缓存基础知识。选择要交换的行是根据许多可能的策略之一进行选择的，例如LRU，而不是根据地址的最低有效位的匹配来选择，我找不到任何这样的策略。 - izac89

@user2162550：搜索“false sharing”和缓存。 - Zan Lynx

我找到了答案，它与缓存关联性有关。你的回答是一个很好的参考，但缓存关联级别精确定位了我的问题。 - izac89

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Victor Choy · Accepted Answer

经过多次学习和思考，我得到了一种似乎更为合理的解释，不仅仅基于具体的地址示例。首先，你必须学习基础知识，如缓存、标记、集合和行分配。

可以确定的是，在 Linux 内核代码中，color_off 的单位是 cache_line_size。color_off 是基本偏移量单位，color 是 struct kmem_cache 中 color_off 的数量。

int  __kmem_cache_create (struct kmem_cache *cachep, unsigned long flags)
   cachep->align = ralign;
   cachep->colour_off = cache_line_size();  // colour_off's unit is cache_line_size
    /* Offset must be a multiple of the alignment. */
   if (cachep->colour_off < cachep->align)
      cachep->colour_off = cachep->align;
   .....
   err = setup_cpu_cache(cachep, gfp);

https://elixir.bootlin.com/linux/v4.6/source/mm/slab.c#L2056

所以我们可以分析两种情况。第一种情况是cache>slab。

你看，除了slab1和slab5可能会发生碰撞外，slab1、slab2、slab3等都没有碰撞的可能性，因为cache足够大。因此，在这种情况下，着色机制并不能明显提高性能。但对于slab1和slab5，我们只需要忽略它们即可，我相信在阅读以下内容后，您就能理解为什么要这样做。 第二种情况是slab>cache。

一个空行表示color_off或cache line。显然，slab1和slab2在由tick标记的行上没有碰撞的可能性，slab2和slab3也是如此。我们确保颜色机制优化了两个相邻slab之间的两条线路，而不是更多的slab1和slab3，它们优化了更多的线路，2+2=4条线路，您可以计算一下。

总结一下，着色机制通过尽可能地使用原本无用的内存，详细地对开头和结尾的一些颜色关掉行进行优化（而不是其他可能仍然会发生冲突的行），从而优化缓存性能。