Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3666035
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8581
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: LINUX

2011-05-28 01:24:31



1 一级 Cache 
首先L1 DATA CACHE 比较小,一般在16K 它是以 Cache Line的形式组织,一般一条 Cache Line 为16字节,
也就是说 以16字节对齐的方式,在内存和Cache之间传输数据。

如果内存地址是 8~23,虽然也是16字节,但是没有按照 Cache Line的方式对齐,需要将 0~15字节 和16~31字节都拷入 Cache 。也就浪费了一次。

在linux的slab实现中用L1_CACHE_ALIGN来计算。也用align = L1_CACHE_BYTES来进行计算。


2 align 
  
代码参数有效性检测之后,首先计算 align。
  
if (flags & SLAB_HWCACHE_ALIGN) {
/*
* Default alignment: as specified by the arch code.  Except if
* an object is really small, then squeeze multiple objects into
* one cacheline.
*/
ralign = cache_line_size(); 
while (size <= ralign / 2)
ralign /= 2; 
}

 取Cache Line的大小,就是上文提到的 16字节。 当然 obj的大小非常小,比一个Cache Line
还小,可以考虑多个对象公用一个 Cache Line 。如对象的大小为5个字节,对齐方式可以选择按照八字节对齐,一个Cache Line 放2个 obj。
一般会选择这个配置选项。

3  分配缓存结构   这个工作由 kmem_cache_zalloc 完成。 本质调用了kmem_cache_alloc,
这个部分单列出来。本文不描述

4 slab 管理单元的位置确定
slab描述符和空闲对象管理 部分成为 slab的管理部分,也可以称为slab头
slab的头可以放在slab自身,也可以放在 slab 之外。到底放到哪里比较合适呢?


如果slab头放在了slab 之外,那么用户申请obj时,需要首先访问 slab头,slab头提供未使用free obj的指针
然后再访问这个free obj的地址。完成这项工作需要 访问2个页块。 会带来效率上的损失。

slab头始终位于slab 也存在问题, 比如一个页面只有4K,objsize = 2K,那么slab 头在slab 上,就意味着,这个4K的页面只能够 分配一个obj。造成了内存的浪费。

Linux的策略是,大约1/8 page大小的obj,就把slab 头,分配在slab之外。

if ((size >= (PAGE_SIZE >> 3)) && !slab_early_init)
/*
* Size is large, assume best to place the slab management obj
* off-slab (should allow better packing of objs).
*/
flags |= CFLGS_OFF_SLAB;


5  计算分配多少个页面数用作 slab   : calculate_slab_order

如果 页数太少,存放的 obj个数少,那么 增加管理开销,同时 内存使用率低,如果页数太多对伙伴内存系统不好,所以需要一定的策略妥协。

这个妥协过程是有calculate_slab_order 这个函数来实现的。

从 0阶(即一页) 到kmalloc的最高阶 KMALLOC_MAX_ORDER ,挨个尝试,由cache_estimate这个函数计算 如果选用order 阶,那么能分配 多少个 obj(num),剩余空间是多少(remainder)。所谓剩余空间,就是除去slab头(如果有的话),除去 obj*num,剩下的边角料空间是多少。 需要分成两种情况去计算,分成两种情况的原因,很快就能看到

A) slab头不在slab上,即 flag & CFLGS_OFF_SLAB == 1的时候

这种情况比较简单,由于管理数据完全不在slab 上,
size_t slab_size = PAGE_SIZE << gfporder; 
nr_objs = slab_size / buffer_size; 

B)  slab头在 slab上,这种情况稍复杂,原因是 slab头里面有个除了固定大小的slab 描述符,还有个 空闲对象管理数组,这个数组的大小取决于obj的个数。 但obj的个数又取决于 slab 头大小。 

换句话,slab头的大小取决于obj的个数, obj的个数取决于 slab头的大小,

所以只能用尝试法来计算obj的个数:
 
nr_objs = (slab_size - sizeof(struct slab)) /
 (buffer_size + sizeof(kmem_bufctl_t));

            if (slab_mgmt_size(nr_objs, align) + nr_objs*buffer_size
      > slab_size)
nr_objs--;

         slab_mgmt_size 这个函数的意思很清楚 就是将slab头的大小 对齐
      return ALIGN(sizeof(struct slab)+nr_objs*sizeof(kmem_bufctl_t), align);  

   这样就能计算浪费的空间 ,总大小 - slab头大小 -  N个obj的大小。 slab头得大小需要align。 
    *left_over = slab_size - nr_objs*buffer_size - mgmt_size; 


接下来我们分析 calculate_slab_order 。 
比较难懂的地方是if(flags & CFLGS_OFF_SLAB) 这个循环体。我查阅很多资料,我的分析结果如下:
offslab_limit = size - sizeof(struct slab);
offslab_limit /= sizeof(kmem_bufctl_t);
这两行代码的意思是,如果slab头 大小等于管理对象obj的大小,那么,最多有offslab_limit 。
如果cache_estimate 算出来的num > offslab_limit ,表示obj的数目太多了,导致 slab头中的
kmem_bufctl_t 数组太大 ,导致slab头的总大小太大, 大于了对象obj的size。 

网上传播的一种解释是,obj的大小为size,他的flag为CFLGS_OFF_SLAB,那么slab头大小 如果大于obj的大小
那么,分配slab头的时候,他的flag必然也会是CFLGS_OFF_SLAB 。也就是说,分配obj,必须分配 obj的 slab头,分配slab头的时候,发现又必须分配slab头的slab头,从而陷入了死循环。这是一种说法。

深入Linux内核架构中也提到了 如果num大于 offslab_limit ,需要将gfporder --,重新计算。但是我查看了几个内核版本,并没有发现 代码中存在将gfporder--,以满足num < offslab_limit 。

我的理解是,这种限制实际是一种建议性质的软限制,纵然num >offslab_limit,也存在其他的机制保证不会出现死循环,这个机制就是 下面的slab_break_gfp_order 。

#define BREAK_GFP_ORDER_HI 1
#define BREAK_GFP_ORDER_LO 0
static int slab_break_gfp_order = BREAK_GFP_ORDER_LO;
如果内存数大于32M, slab_break_gfp_order  = 1,
否则,slab_break_gfp_order =0

if (gfporder >= slab_break_gfp_order)
break;
这条if语句的含义是对于小的obj, 占用的页数要低于 2^1个,即,小的obj 分配2个页面即可。
我们可以想见,如果obj的size >512,即 slab头在slab外,那么,实际的num个数非常少,只有最多3个,
不会造成 slab头的大小大于 512。也就不会造成死循环。

slab_break_gfp_order 这个限制,也决定了对于大于8192字节(2页)的obj, 一个slab只能管理一个obj。
注(非常感谢palals的日志,他的日志slab分配器系列作品写得非常优秀,以至于我都觉得我没有写这篇博文的      必要

calculate_slab_order
----------------------------------------------------------------------
for (gfporder = 0; gfporder <= KMALLOC_MAX_ORDER; gfporder++) {
unsigned int num;
size_t remainder;

cache_estimate(gfporder, size, align, flags, &remainder, &num);
if (!num)
continue;

if (flags & CFLGS_OFF_SLAB) {
/*
* Max number of objs-per-slab for caches which
* use off-slab slabs. Needed to avoid a possible
* looping condition in cache_grow().
*/
offslab_limit = size - sizeof(struct slab);
offslab_limit /= sizeof(kmem_bufctl_t);

  if (num > offslab_limit)
break;
}

/* Found something acceptable - save it away */
cachep->num = num;
cachep->gfporder = gfporder;
left_over = remainder;

/*
* A VFS-reclaimable slab tends to have most allocations
* as GFP_NOFS and we really don't want to have to be allocating
* higher-order pages when we are unable to shrink dcache.
*/
if (flags & SLAB_RECLAIM_ACCOUNT)
break;

/*
* Large number of objects is good, but very large slabs are
* currently bad for the gfp()s.
*/
if (gfporder >= slab_break_gfp_order)
break;

/*
* Acceptable internal fragmentation?
*/
如果浪费的空间小于总空间的1/8, OK,可以跳出循环
if (left_over * 8 <= (PAGE_SIZE << gfporder))
break;
}
return left_over;
}

 kmem_cache_create
---------------------------------------------------------------------------
slab_size = ALIGN(cachep->num * sizeof(kmem_bufctl_t)
 + sizeof(struct slab), align);   //slab头的大小
如果发现剩余空间大于 slab头需要的大小,那么就改变最初的决策,即哪怕obj的大小大于512,仍然将
slab头放入slab。

6 计算颜色或着色。

cachep->colour_off = cache_line_size();  // colour_off 等于 cache line的大小。
cachep->colour = left_over / cachep->colour_off; // 不同颜色值的个数。、
所谓不同颜色值的 含义是,不同颜色值得obj  在L1 Data Cache的位置不同。 

cachep->slab_size = slab_size;  
slab_size 保存的是slab头的大小,如果slab头位于slab上,则,需要align,否则,不需要。

cachep->buffer_size = size; 
buffer_size 是指 obj对象的大小,当然是通过align 之后的大小。

所谓着色,就是防止同样的obj 映射到同一个缓存的Line,这样的话,就会出现频繁的换入缓存,换出缓存。
但是,如果obj的个数很多的话,因为颜色的个数有限还是会出现换入换出。着色的意义并不是象想的那么大。
具体可以参看 CSDN 博文 slab着色--一种必然认输的妥协。





阅读(4732) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~