slab着色与cpu硬件高速缓存

学习LKD的时候，在内存管理一章的slab小节中，对于slab的着色只是一笔带过，并没有详细叙述，只好翻看了很多资料，稍微有了点儿概念，其实关键在于分清所谓的cache（高速缓存，包含多个slab块）和硬件高速缓存的概念。
        slab的设计原理和主体代码不难理解，相应的内存管理效率提升原理也不难理解，问题在于slab着色的原理和用途。我们都知道slab中，相同大小的对象倾向于存放在硬件高速缓存内部相同的cache line中，由此产生的问题是，不同slab中，相同大小的对象很可能最终映射到相同的cache line中，当进行针对这两个对象的读操作时，就出现了两个对象在cache line和RAM之间来回不停切换的现象，更糟糕的是，剩下的一些cache line可能正在无所事事，着色的主要目的就是避免类似的现象发生。
     由于slab是采用空间换时间的方式提高分配效率，因此在slab块中会存在没有用处的字节，我们称作free，另外，由于要和硬件缓存内部的cache line对齐，还存在一个对齐因子的概念，称作aln，能够使用的颜色数据为free / aln+1，free个无用字节被划分为着色域和着色补偿域两部分，分别位于slab块的头和尾，着色域后面紧跟着slab描述符+对象描述符，接下来就是每个对象了，对于对象大小相同的不同slab块，着色域和着色补偿域的大小分别为col x aln和free-col x aln，其中col表示当前slab块的颜色数，当col x aln=free时，代表颜色数已经分配完，新的对象大小相同的slab生成时，col数目从0开始新一轮的循环。这样，就使得对象大小相同的不同slab块中的对象拥有不同的位移量，确保它们不会被映射到硬件缓存内部相同的cache line中。以上是理想情况，当free < aln时，颜色数只有1个，依然无法避免冲突。
     小小总结一下，slab着色功能的高效性是建立在颜色数很多的情况下，但细心的人也会想到，当对象大小相同的slab数目远远超过颜色数时，着色仍然避免不了出现冲突。基于这一点考虑，再加上slab的复杂结构和诸如缓存队列等复杂的层次结构带来的高内存占用，Linux内核小组在2.6.23以及之后的内核版本中，采用slub算法替代了slab算法，按照Linux内核小组人员的说法，slub较slab提升了5%~10%的性能并减少了50%的内核缓存占用，也就是说，不仅仅从时间，而且从空间上都较slab算法有了改善，slub完全兼容slab的接口，内核的其他模块无需修改代码就可以从新的内核缓存分配算法中收益。

 

     同一硬件高速缓存行可以映射 RAM 中多个不同的块，相同大小的对象倾向于存放在高速缓存内相同的偏移量处。在不同 slab 内具有相同偏移量的对象最终很可能映射到同一高速缓存行中。而使用 slab 分配器的对象通常是频繁使用的小对象，高速缓存的硬件可能因此而花费内存周期在同一高速缓存行与 RAM 内存单元之间来来往往的传送两个对象。

 

如下例：假设 cache 行为 32Bytes ， CPU 包含 512 个 cache 行（缓存大小 16K ）。

 

     假设对象 A,B 均为 32B ，且 A 的地址从 0 开始， B 的地址从 16K 开始，则根据组相联或直接相联映射方式（全相联方式很少使用）， A,B 对象很可能映射到 cache 的第 0 行 ，此时，如果 CPU 交替的访问 A,B 各 50 次，每一次访问 cache 第 0 行都失效，从而需要从内存传送数据。而 slab 着色就是为解决该问题产生的，不同的颜色代表了不同的起始对象偏移量，对于 B 对象，如果将其位置偏移向右偏移 32B ，则其可能会被映射到 cache 的第 1 行上，这样交替的访问 A,B 各 50 次，只需要 2 次内存访问即可。

     这里的偏移量就代表了 slab 着色中的一种颜色，不同的颜色代表了不同的偏移量，尽量使得不同的对象的对应到不同的硬件高速缓存行上，以最大限度的提高效率。实际的情况比上面的例子要复杂得多， slab 的着色还要考虑内存对齐等因素，以及 slab内未用字节的大小，只有当未用字节数足够大时，着色才起作用。

对cache line和colour的进一步解释 [re: lucian_yao]

一个L1 DATA CACHE相当于一块小的内存，我们假设它为16K大，它会与一般物理内存交互。
它和内存交互一般一次传输16个字节(32个字节),也就是:


CACHE 字节0-15一次写到/读取物理内存 ，字节16-31一次写到/读取物理内存.32-47 ... ...

这些一次被传输的字节被称为cache line。
--------------------------------------------------------------

另外，cache写到物理内存的位置不是任意的，
我们假定内存为64K,那么cache地址0的数值只能和物理内存的地址0, 16K, 32K交互；cache地址1的数值只能和物理内存的地址1, 16K+1, 32K+1交互
。。。 。。。cache地址16K-1的数值只能和物理内存的地址6K-1, 16K+16K-1, 32K+16K -1交互

这说明了两点:

(1)假设对象A的一个字段长为16个字节，如果它放在物理地址 0-15,那么它将和cache的第一个cache line 交互，如果放在物理地址 8-23,那么
如果CPU要访问这个字段，必须将第一个和第二个cache line 都读入，才能获得这个字段的信息，显然这样速度慢，所以一般字段需要cache line对齐，
在这里就是16个字节对齐。


(2)关于colour


一般一个对象某些字段访问频繁些。
假定一个cache(这个cache指slab的cache,不是上面提到CPU的L1 DATA CACHE)占用5个页面也就是20K.
假定其中对象大小为32个字节，前16个字节访问频繁许多。

假定对象A起始于物理地址0，对象C起始于31,对象B起始于物理地址16K,那么对象A，对象B的前16个字节都和第一个cache line 交互，后16个字节都和第二个cache line 交互
对象C前16个字节与第3个cache交互。

我们假定内核访问A后就访问B,再访问A,交错进行，并且前16个字节次数都是50次，后16个为10次。C也是。

这样第一个cache line 要交互100次，第二个20次，一共120次。

如果让对象B向后移动16个字节，也就是对象B的前16个字节与第二个cache line 交互，后16个与第3个交互。
那么第一个为2次，因为只有开头结尾2次要与内存交互，其它每次都在L1 DATACACHE 中写就可以了。第2个cache line为20次左右(后面的只须在CACHE中读写),第3个cache line为20次，
3个line一共才41次，你不妨仔细模拟一下。

所以进行错位能降低CACHE的交互次数，从而提高CPU处理速度能力。

这个错位(也就是上面的16个字节)就是colour.