用顾虑造句:我看slab算法中"着色"[cachep

我看slab算法中"着色"[cachep->colour_off]的物理意义

文章来源:http://gliethttp.cublog.cn[转载请声明出处]

  对于arm9处理器,当使用指令控制协处理器cp15打开数据缓存(DCache)时,arm9内部的
数据总线上的数据就都会被缓存到arm9内部的物理cache中,对于arm9处理器at91rm9200来说,dcache大小为16k,
物理分布情况是这样的:"每条cpu物理cache缓存线数据大小为32字节,一共512条,即:16K",
cpu访问cpu内部dcache区的速度远远高于访问外部sdram,此时,arm9处理器操作的所有数据将直接来自于
dcache-16k的cpu内部高速物理缓存,处理器将只与处理器内部的dcache打交道,dcache将外设物理内存中的数据读到dcache中,同时将dcache中原有的数据回写到相应地址对应的物理内存中,只有其他物理内存地址使用相应高速缓存线发生冲突时,相应缓存线上的数据才会回写到相应地址对应的物理内存,否则一旦读入dcache,所有读写操作都将只在dcache中进行,不会对物理内存操作,直到因为高速缓存线发生冲突时,才将高速缓存线上的数据回写的物理内存,那么仅仅16k的dcache又是怎么和几十M的外设物理内存进行一一映射的呢?
那就是:"16K一组",对于at91rm9200来说,外设物理内存被分成一个个16k的段,
每个段相对于该段的偏移内存,将共用一根cpu物理cache缓存线,
如:arm9处理器有512条物理cache缓存线,每条缓存线32字节,数据按块传输,一次传输一条缓存线大小字节,
  0,    16k,    32k,    48k,    64k,...使用第0根cpu物理cache缓存线
 32, 16k+32, 32K+32, 48k+32, 64k+32,...使用第1根cpu物理cache缓存线
 64, 16k+64, 32K+64, 48k+64, 64k+64,...使用第2根cpu物理cache缓存线
...
16k-64,16k+16k-64,32k+16k-64,48k+16k-64,64k+16k-64,...使用第510根cpu物理cache缓存线
16k-32,16k+16k-32,32k+16k-32,48k+16k-32,64k+16k-32,...使用第511根cpu物理cache缓存线
举例说明一下:
物理内存地址:0x20000000,0x20000003,0x20000020,0x20000030,0x20004000,0x20004003,0x20004020,0x20004030
如果对如上地址有数据读、写操作,那么cpu将自动正这些物理地址数据映射到arm9内部的dcache
对应的缓存线的32字节上,那怎么运算的呢,来看看,
//1.物理内存0x20000000
相对16k的地址 :A=0x20000000%(512*32)=0
第几根缓存线号:B=A/32=0
第几个缓存字节:C=A%32=0
解释:内存0x20000000将和第0根cpu物理cache缓存线的第0个字节进行数据交互
//2.物理内存0x20000003
相对16k的地址 :A=0x20000003%(512*32)=3
第几根缓存线号:B=A/32=0
第几个缓存字节:C=A%32=3
解释:内存0x20000003将和第0根cpu物理cache缓存线的第3个字节进行数据交互
//3.物理内存0x20000020
相对16k的地址 :A=0x20000020%(512*32)=0x20
第几根缓存线号:B=A/32=1
第几个缓存字节:C=A%32=0
解释:内存0x20000020将和第1根cpu物理cache缓存线的第0个字节进行数据交互
//4.物理内存0x20000030
相对16k的地址 :A=0x20000030%(512*32)=0x30
第几根缓存线号:B=A/32=1
第几个缓存字节:C=A%32=0x10
解释:内存0x20000030将和第1根cpu物理cache缓存线的第16个字节进行数据交互

因为缓存线是块传输,所以位于第0根cpu物理cache缓存线上的32个字节数据,
如有有一个字节发生了读、写操作,那么和它处在第0根cpu物理cache缓存线上的其他数据也将
一并将物理内存上对应的数据读、写到该缓存线的32字节上.[gliethttp]

//5.物理内存0x20004000
相对16k的地址 :A=0x20004000%(512*32)=0
第几根缓存线号:B=A/32=0
第几个缓存字节:C=A%32=0
解释:内存0x20004000将和第0根cpu物理cache缓存线的第0个字节进行数据交互
//6.物理内存0x20004003
相对16k的地址 :A=0x20004003%(512*32)=3
第几根缓存线号:B=A/32=0
第几个缓存字节:C=A%32=3
解释:内存0x20004003将和第0根cpu物理cache缓存线的第3个字节进行数据交互
//7.物理内存0x20004020
相对16k的地址 :A=0x20004020%(512*32)=0x20
第几根缓存线号:B=A/32=1
第几个缓存字节:C=A%32=0
解释:内存0x20004020将和第1根cpu物理cache缓存线的第0个字节进行数据交互
//8.物理内存0x20004030
相对16k的地址 :A=0x20004030%(512*32)=0x30
第几根缓存线号:B=A/32=1
第几个缓存字节:C=A%32=0x10
解释:内存0x20004030将和第1根cpu物理cache缓存线的第16个字节进行数据交互

因为缓存线是块传输,所以位于第1根cpu物理cache缓存线上的32个字节数据,
如有有一个字节发生了读、写操作,那么和它处在第1根cpu物理cache缓存线上的其他数据也将
一并将物理内存上对应的数据读、写到该缓存线的32字节上.[gliethttp]

比如cpu正在对0x20000003地址进行读写操作,突然有一个地址指针指向了0x20004003,并且
需要读取0x20004003内存处的地址,cpu检测到冲突,因为此时位于第0根cpu物理cache缓存线上的32个字节数据
有效地址空间是0x20000000~0x2000001f,而另一个地址段下的物理内存需要使用第0根cpu物理cache缓存线
,cpu执行写回操作,将现在第0根cpu物理cache缓存线上的32字节数据,块传输到物理内存0x20000000~0x2000001f上,
之后将0x20004000~0x2000401f物理内存段上的32字节数据,块传输到第0根cpu物理cache缓存线上.[gliethttp]
这样就完成了冲突之后的一次切换[向旧地址段回写cache line中数据、新地址段数据置入cache line]

从上面的几个数据,可以清晰的看到,我们应该尽量让一个slab所管理的每个对象和cpu物理cache缓存线
对齐,使用size = (size+align-1)&(~(align-1));//其中align=L1_CACHE_BYTES=32字节(arm9处理器)

将size调整为32字节的整倍数,进而将slab中管理的对象调整成与cpu物理cache缓存线对齐,
如果不对齐会使cpu物理cache缓存线进行频繁的32字节块数据转换传输,进而降低cpu的数据有效吞吐量,
如:slab管理的size=30字节,不进行cpu物理cache缓存线对齐,假设该slab的第一个对象X0位于第10根
cpu物理cache缓存线的0~29字节,那么相邻的对象X1就会使用cpu物理cache缓存线的第10根[30,31]和第11根[0,27],
当对对象X0进行内存读写操作时,将不会有什么牺牲,因为每次cache line块传输都是有意义的,
但是当对象X1被分配使用时,对对象X1进行的内存读写操作,将会进行4次cache line的块传输,[换出和换入]
看上去好像也都是有意义的传输,但是,如果我们将size=30字节数据调整成32字节对齐,
那么X1对象将和X0对象一样,只需要2次cache line块传输就可以了.[gliethttp]
所以应该让一个slab所管理的众多对象,独立使用若干根cpu物理cache缓存线,不要出现对象之间
共用某根cpu物理cache缓存线的现象,尽量然他们使用不用的cache line.

"着色"[cachep->colour_off]概念的也正是基于以上原因被提出的,既然一个slab内部的所有对象已经
进行了cpu物理cache缓存线对齐,那么"着色"的概念又是提给谁的呢?
先看看cachep中用到的几种结构:
kmem_bufctl_t对象控制数组就像fat文件系统中的fat表,它是一个空闲区域的索引,
slabp->free是空闲对象控制数组kmem_bufctl_t的一个起始索引号,后面串链着所有空闲数组号
cachep->colour为本cache"着色"所能活动的的最范围值,该值根据一个slab中所能剩余的无用空闲空间大小
决定,对于使用arm9处理器cpu物理cache缓存线对齐flag标志的cache来说,cachep->colour = left_over / 32;
至于详细的理解,需要另一篇文章单独完成,这篇单独文章仍可以在我的博客http://gliethttp.cublog.cn中找到.

假设:cachep->colour=4;又因为该cache是比较受linux欢迎的结构,所以salb通过kmem_cache_grow()函数调用
生长了4次,也就是前3次申请的到3个slab中每个slab管理的对象都已经被干光光,因为每个slab至少占用1页(4k)
,所以4次就用掉了16k空间,因为arm9的cpu物理cache缓存线总大小为16k,这时"着色"开始发挥最大作用,
按最好的情况说,前4次申请的空间刚好一一对应上cpu物理cache缓存线的0~16k,那么每个slab因为"着色"的原因,
都在slab的最前面空出cachep->colour_next*32字节空间,如果是都是第一次,那么分别为G=0,G=32,G=64,G=96,
假设slab对象的大小为32字节,那么这16k空间中将会有4个对象是部分相交,
G=0的slab不与任何其他对象相交,
G=32的slab中有1个相交,和G=0中的第1个对象相交,
G=64的slab中有2个相交,和G=0中的第2个对象相交,以及G=32中的第1个对象相交,
G=96的slab中有3个相交,和G=0中的第3个对象相交,以及G=32中的第2个对象相交,以及G=64中的第1个对象相交
这样这4个对象的效率只是部分受到影响,当然对于剩下的其他对象,他们的cpu物理cache缓存线那是肯定都是4个交的,
避免不了的,假如没有释放前4个中的任何一个对象的同时,又要申请对象,那么将会进行第5次生长,
这时cachep->colour_next=0;回0,这样第5次生长的slab最前面的空闲空间为0字节,他会和同样空闲为0的G0相交,
G=0的slab与1个对象相交,其他的各自增加1次,
继续增长下去,当增长到9次时,此时所有对象相交,但是"着色"将一直能保证同一个cache类中包含的多个slab链中的对象的前cachep->colour个对象仅仅是部分相交,这样前几个对象对应的cache line的换入、换出的频率就少于cachep->colour之后满负载对象的cache line的换入、换出的频率.所以"着色"只能挽救其中的"一小撮"对象,
至于具体多少个,要根据对象的大小、slab页地址情况以及slab生长的数量综合考虑.[gliethttp]
于是为了这"一小撮"对象就整了个"着色"概念出来,不过slab可能是这样想的:"能救一个是一个".
话又说回来了,cachep->colour使用的是slab申请的若干page页中空闲出来的未用空间,
从这个角度来说,"着色"机制还"变废为宝"了,对,"着色"机制就是一种不怎么牺牲的前提下,"尽量变废为宝"的策略.