Linux 平板分配器和缓存性能

Question

来自指南理解linux内核第3版，第8.2.10章，Slab着色-

We know from Chapter 2 that the same hardware cache line maps many different blocks of RAM. In this chapter, we have also seen that objects of the same size end up being stored at the same offset within a cache. Objects that have the same offset within different slabs will, with a relatively high probability, end up mapped in the same cache line. The cache hardware might therefore waste memory cycles transferring two objects from the same cache line back and forth to different RAM locations, while other cache lines go underutilized. The slab allocator tries to reduce this unpleasant cache behavior by a policy called slab coloring : different arbitrary values called colors are assigned to the slabs.

(1) 我无法理解平板着色试图解决的问题。当正常进程访问数据时，如果它不在缓存中并且遇到缓存未命中，则将数据与进程尝试访问的数据周围地址的数据一起提取到缓存中以提高性能。怎么会发生相同的特定缓存行不断交换的情况？一个进程在两个不同内存区域的内存区域中不断访问相同偏移量的两个不同数据地址的可能性非常低。即使它确实发生了，缓存策略通常会根据某些议程（例如 LRU、随机等）选择要交换的行。不存在根据被访问地址的最低有效位匹配来选择逐出行的策略.

(2) 我无法理解 slab 着色的方式，它从 slab 的末尾到开头获取空闲字节，并导致第一个具有不同偏移量的不同 slab对象，解决缓存交换问题？

[已解决] 经过小规模调查后，我相信我找到了问题的答案。答案已发布。

Answer 1

假设你有一个 256 KB 的缓存，它使用了一个超级简单的算法，其中缓存行 = (real address AND 0x3FFFFF)。

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

通过偏移 slab，不同的 slab 共享相同缓存行标签的可能性降低。如果 Slab 1 和 Slab 2 都持有 32 字节的对象，而 Slab 2 偏移 8 字节，它的缓存标签将永远不会与 Slab 1 的完全相等。

我确定我有一些细节错误，但请相信它的价值。

Answer 2

我想我明白了，答案与关联性有关。

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

现在，从 link Understanding CPU Caching and performance

From page 377 of Henessey and Patterson, the cache placement formula is as follows: (Block address) MOD (Number of sets in cache)

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

因此，通过为不同平板中的对象保持不同的偏移量（颜色），平板对象可能会到达缓存中的不同集合，并且不会碰撞到同一个集合，整体缓存性能提升

编辑： 此外，如果缓存是直接映射的，那么根据维基百科，CPU Cache，没有缓存替换策略存在并且模数计算产生内存块将存储到的缓存块：

Direct-mapped cache In this cache organization, each location in main memory can go in only one entry in the cache. Therefore, a direct-mapped cache can also be called a "one-way set associative" cache. It does not have a replacement policy as such, since there is no choice of which cache entry's contents to evict. This means that if two locations map to the same entry, they may continually knock each other out. Although simpler, a direct-mapped cache needs to be much larger than an associative one to give comparable performance, and it is more unpredictable. Let x be block number in cache, y be block number of memory, and nbe number of blocks in cache, then mapping is done with the help of the equation x = y mod n.

Answer 3

经过多次研究和思考，我得到的解释似乎更合理，而不仅仅是具体的地址示例。首先要学习缓存、标签、集合、线路分配等基础知识

从linux内核代码可以确定colour_off的单位是cache_line_size。 colour_off是基本偏移单位，colour是struct kmem_cache.

中colour_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

所以我们可以分两种情况来分析。 首先是缓存 > slab。 你看到 slab 1 slab2 slab3 ... 不可能发生碰撞，主要是因为缓存足够大，除了 slab1 和 slab5 可能发生碰撞。所以着色机制在提高性能的情况下并不是那么清晰。但是对于slab1和slab5，我们就直接忽略了，不解释为什么，相信看完下面的你就会明白了。

其次是slab > cache. 空行表示 color_off 或缓存行。很明显，slab1 和 slab2 不可能在 tick 和 slab2 slab3 标记的线上发生碰撞。我们确保着色机制优化了两个相邻 slab 之间的两条线，更不用说 slab1 vs slab3 优化更多的线，2+2 = 4 线，你可以数一下。

总而言之，着色机制通过尽可能使用原本无用的内存来优化缓存性能（具体只是优化colour_off开头和结尾的一些行，而不是其他仍然可能发生冲突的行）。

Linux 平板分配器和缓存性能

Linux slab allocator and cache performance

linux

memory

memory-management

linux-kernel

slab