请问,slab算法中gfporder怎么计算的?

Question

kmem_cache_create(...)
{
...

do {
        unsigned int break_flag = 0;
cal_wastage:
        kmem_cache_estimate(cachep->gfporder, size, flags,
                        &left_over, &cachep->num);
        if (break_flag)
            break;
        if (cachep->gfporder >= MAX_GFP_ORDER)
            break;
        if (!cachep->num)
            goto next;
        if (flags & CFLGS_OFF_SLAB && cachep->num > offslab_limit) {
            /* Oops, this num of objs will cause problems. */
            cachep->gfporder--;
            break_flag++;
            goto cal_wastage;
        }

        /*
         * Large num of objs is good, but v. large slabs are currently
         * bad for the gfp()s.
         */
        if (cachep->gfporder >= slab_break_gfp_order)
            break;

        if ((left_over* <= (PAGE_SIZE<<cachep->gfporder))
            break;    /* Acceptable internal fragmentation. */
next:
        cachep->gfporder++;
    } while (1);
...
}

gfporder++后，怎么能够再去kmem_cache_estimate()?
kmem_cache_estimate()中，页已经分配好了啊?

没看懂gfporder是怎么计算的
请教
bow

Answer 1

slab 管理

slab分配器在内存分配中起的作用

slab分配器通过页面级分配器获得页块后，做进一步的精细分配,
将这个页块分割成一个个的对象，有点类似c中的malloc
c, mfree的作用。

cache描述符

struct kmem_cache_s {
       /* 1) each alloc & free */
       /* full, partial first, then free */
       struct list_head slabs;
       struct list_head *firstnotfull;
       unsigned int objsize;
       unsigned int flags; /* constant flags */
       unsigned int num; /* # of objs per slab */
       spinlock_t spinlock;
       #ifdef CONFIG_SMP
       unsigned int batchcount;
       #endif

       /* 2) slab additions /removals */
       /* order of pgs per slab (2^n) */
       unsigned int gfporder;

       /* force GFP flags, e.g. GFP_DMA */
       unsigned int gfpflags;

       size_t colour; /* cache colouring range */
       unsigned int colour_off; /* colour offset */
       unsigned int colour_next; /* cache colouring */
       kmem_cache_t *slabp_cache;
       unsigned int growing;
       unsigned int dflags; /* dynamic flags */

       /* constructor func */
       void (*ctor)(void *, kmem_cache_t *, unsigned long);

       /* de-constructor func */
       void (*dtor)(void *, kmem_cache_t *, unsigned long);

       unsigned long failures;

       /* 3) cache creation/removal */
       char name[CACHE_NAMELEN];
       struct list_head next;
       #ifdef CONFIG_SMP
       /* 4) per-cpu data */
       cpucache_t *cpudata[NR_CPUS];
       #endif
       #if STATS
       unsigned long num_active;
       unsigned long num_allocations;
       unsigned long high_mark;
       unsigned long grown;
       unsigned long reaped;
       unsigned long errors;
       #ifdef CONFIG_SMP
       atomic_t allochit;
       atomic_t allocmiss;
       atomic_t freehit;
       atomic_t freemiss;
       #endif
       #endif
};

slabs用它将这个cache的slab连成一个链表
firstnotfull指向第一个不满的slab,当分配(复用)对象的时候，首先考虑在它指向的slab里分配.
objsize该cache中对象大小
flags
num对象个数

gfporder该cache中slab一个占用多少页面，当构造新的slab,按照这个大小向页面级分配器申请页面。
gfpflags申请页面时，向页面级分配器提出的要求，例如是否要求申请DMA的页面，是否要求申请是原子的(即页面分配器在分配的时候不能被阻塞)
colour  colour的范围，这个cache的slab依次用0,1,...,colour-1,0,1,...为颜色。
colour_off这个cache中colour粒度，例如为一个L1-CACHE线。
colour_next下一个colour数，当cache分配一个新的slab时，采用这个colour,也就是colour * colour_off为slab空出的字节数
slabp_cache 当这个cache中的slab,其管理部分(slab描述符和kmem_bufctl_t数组)放在slab外面时，这个指针指向放置的通用cache
growing
dflags
ctor 指向对象的构造器，在这个cache创建一个新的slab时，对里面所有的对象都进行一次构造调用(参见slab的设计思想中关于对象复用部分)
dtor 指向对象的析构器，在这个cache销毁一个slab时，对里面所有的对象都进行一次析构调用
failures

name 这个cache的名字
next 用它和其它的cache串成一个链，在这个链上按照时钟算法定期地回收某个cache的部分slab

slab描述符

typedef struct slab_s {
   struct list_head list;
   unsigned long colouroff;
   void *s_mem; /* including colour offset */
   unsigned int inuse; /* num of objs active in slab */
   kmem_bufctl_t free;
} slab_t;

list用于链表，这个链表将cache中所有的slab连接起来
colouroff这个slab中第一个对象距离slab起始位置(也就是页块起始位置)的字节数，实际上s_mem=页块首地址+colouroff
s_mem这个slab中第一个对象的起始位置
inuse这个slab中被使用的对象个数，用于调整slab格局，当inuse=0说明这个slab全空，将这个slab从部分满的slab段中移动到全空的slab段中
free第一个未用对象的ID, 当在这个slab"分配"(复用)对象时，首先用这个ID的对象。

通用cache索引结构
用这个结构组成的数组cache_sizes给不同尺寸的通用cache提供索引
typedef struct cache_sizes {
size_t cs_size;
kmem_cache_t *cs_cachep;
kmem_cache_t *cs_dmacachep;
} cache_sizes_t;
cs_size通用cache的对象尺寸
cs_cachep指向一个通用cache, 它的对象尺寸为cs_size
cs_dmacachep指向一个通用DMA的cache, 它的对象尺寸为cs_size

Slab分配器的结构

Slab 分配器用于管理内核的核心对象。

它有若干个 cache 组成。每个 cache 管理一个特定类的对象。

每个cache有若干个 slab (Slab分配器的名字可能就是怎么来的)组成,每个 slab
实际上就是若干个页面组成的一个页块。这个页块被细分成许多对象。
cache为管理这些slab, 通过 cache描述符( kmem_cache_t )以及指针将这些 slab
连起来。

验证
cache的数据结构中下面这个字段:
struct  kmem_cache_s {

struct list_headslabs;
... ...
}

与slab结构中下面字段:

typedef struct slab_s {
struct list_headlist;
...
} slab_t;

共同构成这个链表.
slab如何管理它的对象

一个 slab 通过自己的 kmem_bufctl_t 数组，来管理它的空闲对象。这个数组的元素和该 slab中的对象是一一对应的。
初始化一个slab时，每个对象都是空的，所以这个数组每个元素(除最后一个)都指向下一个:
在kmem_cache_init_objs中
static inline void kmem_cache_init_objs (kmem_cache_t * cachep, slab_t * slabp, unsigned long ctor_flags)
{
int i;

for (i = 0; i < cachep->num; i++) {
.. ...
slab_bufctl(slabp)[ i ] = i+1;
}
slab_bufctl(slabp)[i-1] = BUFCTL_END;
... ...
}

分配对象时，在下面的语句中，

objp = slabp->s_mem + slabp->free*cachep->objsize;
slabp->free=slab_bufctl(slabp)[slabp->free];

取出free的数值1，计算对象1的位置即可。然后将free指向3.
回收(应该说将对象置为未用)时，将数组中对象对应的元素插入链表头即可:
slab_bufctl(slabp)[objnr] = slabp->free;
slabp->free = objnr;

cache如何管理它的slab

格局

一个cache的所有 slab 通过指针连成一个队列，这些 slab的排列始终保持一个格局: 全满的，部分满的，和全空的。
另外，cache 描述符有一个指针始终指向第一个不满的slab(首先可能是部分满的，其次是全空的),当它指向描述符本身的时候，说明没有不满的 slab了。当 slab 是否满的状态有变化时，cache会调整它的位置，以保持上述格局，例如一个部分满的 slab由于它的最后一个对象被设置为不使用，即它为全空的了，那么它将被调整到全空的slab部分中。

当分配一个新的对象时，cache 首先通过 firstnotfull 找到它的第一个不满的slab, 在那么分配对象。如果没有不满的slab,
则向页面级分配器申请一个页块，然后初始化为一个slab.

回收对象

当回收一个对象时，即便在这之后，这个对象所在的 slab 为全空，cache也不会将这个 slab
占用的页块还给页面级分配器。

回收slab

slab分配器算法提供两种回收slab的方式，一种是回收某个特定的cache的所有全空的slab,直到有用户又在该cache分配新的 slab为止( kmem_cache_shrink);一种是对所有的 cache 采用时钟算法，每次选择一个比较合适的 cache,回收它部分的空 slab( kmem_cache_reap ).

验证

每次分配的时候总是考察从firstnotfull指向的第一个不满的slab：
#define kmem_cache_alloc_one(cachep)
({                       
slab_t*slabp;            
                     
/* Get slab alloc is to come from. */
{
struct list_head* p = cachep->firstnotfull;/*<----------这里*/
if (p == &cachep->slabs)
goto
  alloc_new_slab;/*<---------如果这个指针指向cache了，说明没有不满的slab了，?br>簿褪撬狄?凑飧鯿ache的slab全满了，要么就没有slab,这个时候要分配新的slab*/
               
slabp = list_entry(p,slab_t, list);
}
kmem_cache_alloc_one_tail(cachep, slabp);

})

在后面的kmem_cache_alloc_one_tail函数中在这个firstnotfull指向的slab中分配一个对象，如果这个slab因此而满了，则将firstnotfull指向下一个不满的slab:
static inline void * kmem_cache_alloc_one_tail (kmem_cache_t *cachep, slab_t *slabp)
{
... ...
slabp->free=slab_bufctl(slabp)[slabp->free];
if (slabp->free == BUFCTL_END)/*<-------现在满了，指向下一个*/
/* slab now full: move to next slab for next alloc */
cachep->firstnotfull = slabp->list.next;
  ... ...
}

下面看看"释放"一个对象时，是如何保持队列的格局的:
static inline void kmem_cache_free_one(kmem_cache_t *cachep, void *objp)
{
  ... ...
  if (slabp->inuse-- ==cachep->num)/*<-----原来是满的，现在"释放"一个,变得部分满了，则将它调整到部分满的队列部分中去*/

goto moveslab_partial;

if(!slabp->inuse)/*<-------原来只有一个在使用，现在这个也释放了，因而全空了，则调整到全空的队列部分中去*/
  goto moveslab_free;
  return;

moveslab_partial:
/* was full.
* Even if the page is now empty, we can set c_firstnotfull to
* slabp: there are no partial slabs in this case
*/
{
struct list_head *t =
  cachep->firstnotfull;/*<-----将这个slab插到firstnotfull指向的位置就可以了,?br>床糠致?亩恿型凡?/

cachep->firstnotfull = &slabp->list;

if (slabp->list.next == t)
   return;
list_del(&slabp->list);
list_add_tail(&slabp->list, t);
return;
}

  moveslab_free:
/*
* was partial, now empty.
* c_firstnotfull might point to slabp
* FIXME: optimize
*/
{
struct list_head *t = cachep->firstnotfull->prev;

list_del(&slabp->list);

list_add_tail(&slabp->list,&cachep->slabs);/*<--------插到整个队列尾部就可以了*/
if (cachep->firstnotfull == &slabp->list)
cachep->firstnotfull = t->next;

return;

}

}

slab的管理部分
slab描述符和管理空闲对象用的数组(kmem_bufctl_t)不妨被称为slab的管理部分

slab的管理部分放置的位置
1. 管理部分可以和对象都放在slab里
2. 管理部分也可以放到slab外面(在某个通用的cache中，见通用cache)

1. 如果对象比较大，那么把管理部分放到slab里面，会浪费slab大量空间。举一个极端的例子，对象大小为2K, 页块为4K,那么如果把管理部分放到slab里面，这个页块就只能放一个对象，浪费的空间=4k-2k-管理部分的尺寸接近2K!

2. 但是放在外面会带来一些小小的效率上的损失。
如果管理部分和对象放在两个地方，那么一定是在不同的页块中。于是用户申请一个对象时，首先要访问slab管理部分，然后提供指向未用对象的指针，然后用户访问这个对象的地址。这样，完成一个流程需要访问两个页块，也就是在TLB上要"踩"上两个脚印(footprint).

如果管理部分和对象放在一个slab中，因而很有可能在一个页块中，因此完成这个流程只需在TLB上踩上一个脚印。在引起TLB失效的可能性上，前者比后者大，因而效率低。

Color
slab算法中利用slab的剩余空间来做平移，第1个slab不平移；第2个slab平移1个colour粒度；...;周而复始.
void __init kmem_cache_init(void)
{
  size_t left_over;
  init_MUTEX(&cache_chain_sem);
  INIT_LIST_HEAD(&cache_chain);
  kmem_cache_estimate(0, cache_cache.objsize, 0,
&left_over,&cache_cache.num);/*<----------left_over是最多可以空出多少地方供colour使用*/
  if (!cache_cache.num)
     BUG();
  cache_cache.colour =
   left_over/cache_cache.colour_off;/*<--------这里colour是最大colour的粒度，colour_off是粒度单位*/
  cache_cache.colour_next =0;/*<----------------------------------下一个slab用的colour粒度*/
}

在一个cache中每增加一个slab,就要平移一个colour,在下面的函数kmem_cache_grow中:
...
offset =cachep->colour_next;/*<--------------------------offset是colour粒度*/
cachep->colour_next++;/*<-------------------------准备再下一个slab用的colour*/

if (cachep->colour_next >=cachep->colour)/*<-----周而复始的使用colour*/
   cachep->colour_next = 0;
offset *=cachep->colour_off;/*<-----------------乘以粒度单位colour_off才是位移的字节数*/

-------------------------------------
在后面的if (!(slabp = kmem_cache_slabmgmt(cachep, objp, offset,local_flags)))
中用了这个offset,kmem_cache_slabmgmt用于分配一个slab管理部分，包括slab描
述符和控制数组，如果这些结构在这个slab页面里面的话，就要用到colour了:
static inline slab_t * kmem_cache_slabmgmt (kmem_cache_t *cachep,void *objp, int colour_off, int local_flags)
{
...
if (OFF_SLAB(cachep)) {
... ...
  }
  else
  {/*<--------------------------slab管理部分放在slab页面里,用到colour*/
... ...
slabp =objp+colour_off;/*<--------------------slab描述符平移了colour_off个字节，即上面的offset个字节*/
colour_off += L1_CACHE_ALIGN(cachep->num * sizeof(kmem_bufctl_t) +sizeof(slab_t));
                /*<-----slab中对象还在slab描述符和控制数组之后*/

}
slabp->inuse = 0;
slabp->colouroff = colour_off;
slabp->s_mem =objp+colour_off;/*<--------------这里指向的就是slab中对象开始的位置*/
return slabp;
}

在slab算法中提到两个cache
一个是指CPU中的CACHE,我们知道i386一般有一个L1 DATA CACHE, 本质上一块硬件内存.cache line指的是这个CACHE被划分成许多部分，每部分16字节或者32字节(或其它)，它和一般内存(L2 CACHE)交互一次至少读/写这样一个部分，这个部分被称为cache line.而且这些cache line和一般内存交互的部分是被严格限制的，每个cache line只能和一般内存中的很小一部分交互.一个是slab中的cache,它被用来管理一个类的对象，是一个数据结构，它其中的colour的概念恰恰是为了配合L1 DATA CACHE的cache line这么个机制的。

  一个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.

释放(将对象至于未用状态,但不析构)kfree/kmem_cache_free /kmem_cache_free_one
-------------------------------------------------------------------------------------
这里的释放指的是将对象设为未用状态，而没有析构和空间回收的操作,以备将来复用。通过映射得到对象所在的cache和slab(前者只在 kfree中使用)改动slab管理空闲对象的数组链表，将slabp->free指向该对象即可。为了保证这个cache中的slab格局(满，部分满，全空),必要的时候，要调整这个slab在链表中的位置，具体地说：
slab原本是满的，那么需要将它移动到部分满的slab中去(goto moveslab_partial)
slab原本是部分满的，现在空了，那么将它移动到空的slab中去(moveslab_free)
~~~~~~~~
空间回收
~~~~~~
所谓空间回收包括两个工作:
slab分配器把slab中的对象析构(如果有析构器的话)
将占用的页面交还给页面级分配器
slab的回收 kmem_slab_destroy
--------------------------------------------------
如果其中的对象有析构函数，则对这个slab中每个对象调用析构函数将这个slab占用的页面交还给页面级分配器.如果这个slab的管理部分在外面的话，还要到通用cache中free它的管理部分(将这个管理部分设为未用)

cache的页面回收:__kmem_cache_shrink
------------------------------------------------------
特点是针对某个特定的cache,将它的全空的slab全部回收从这个cache的最后一个slab往前考察(注意cache的slab的格局),回收所有全空的slab kmem_slab_destroy,除非有其它用户在这个cache分配新的slab(这部分我还没有仔细考虑).

cache的页面回收: kmem_cache_reap
------------------------------------------
在所有cache范围内考察，每次选择一个cache, 回收它的部分空的slab,这实际上是个垃圾回收的工作。所有在使用的cache描述符构成一个循环链表。为公平起见，reap采用时钟算法，每次从当前指针位置遍历 REAP_SCANLEN 个cache(当然可能中途结束遍历),对这些cache进行考察，选出最佳的cache,对它的页面进行回收:
(1)排除一些当前不能回收的cache
(2)计算剩下的cache中，每个cache可回收的slab个数，以及权重pages
(3)选出其中权重最大的，如果某个cache的可回收的slab个数已经达到要求(>=REAP_PERFECT),就结束遍历，对这个cache进行回收
回收:不回收这个cache中所有的空的slab, 只回收约80%, 方式和 __kmem_cache_shrink 一样

注:
用户接口指外部用户可以调用的接口，其它为内部调用接口
蓝色字是slab分配器的一件主要工作
绿色字是一件工作中的主要线索

一般分配一个对象，首先要创建一个cache来管理所有同类的对象(通用cache除外)。如果有cache了，那么就在其中分配一个对象。

(用户接口)
初始化一个cache (kmem_cache_create )
------------------------------------
在进行一些合法性检查之后，首先在cache_cache中分配这个cache的描述符。
然后对一些尺寸进行处理，包括:size至少是字对齐的 对象对齐方式至少是字对齐的，如果要求是CACHE对齐，那么方式为CACHE对齐，或者是1/2CACHE对齐(如果对象尺寸<=1/2 cache line的话)考虑这个cache的slab的管理部分是否放在slab里面.
找到一个合适的页块的大小，cache中每个slab将获得这样大小的页块。同时计算剩余的空间(kmem_cache_estimate以及外面的循环)
接下来的工作是:
如果剩余空间比slab管理部分大，那么即使开始要求管理部分放在外面，现在还是将它们移动到slab里面.计算颜色的相关数据
对这个cache的描述符进行一些初始化(包括slab的链表)将它加到链表里，以便用时钟算法进行回收

(用户接口)
在一个cache中分配一个对象(kmem_cache_alloc/__kmem_cache_alloc)
-------------------------------------------
(在宏中kmem_cache_alloc_one)
考虑first_not_full指向的不满的slab
●如果指向描述符本身，说明该cache都是满的slab(或者没有slab),于是分配一个新的slab(跳转到alloc_new_slab然后调用kmem_cache_grow)
●如果有不满的slab，那么在这个slab中分配(复用)一个对象(kmem_cache_alloc_one_tail)

为某个cache分配一个新的slab(kmem_cache_grow)
------------------------------------------
检查是否合法(例如在中断中必须使用原子的页面分配，即不能在页面分配的时候睡眠)一些设置(包括新的colour的设置)
从页面分配器那里获得页面(调用kmem_getpages)两个初始化:
这个slab的管理部分的初始化(kmem_cache_slabmgmt),包括管理部分的位置的选取，数组的初始化等
对这个新slab中所有对象初始化(如果有构造函数的话)(kmem_cache_init_objs),回顾一下slab分配器的特点可以知道在一开始的时候需要对所有对象进行初始化

还有一个特别重要的工作:
将所有对象映射到它所在的cache和slab原因是:在释放某个对象的时候，一般slab分配器的用户只提供对象的指针，而slab分配器必须知道它所在的cache描述符和slab描述符才好操作。

将这个slab串到cache的队列里
采用的方法: 对象 --->它所在的页面 ----> cache 和 slab
第一个映射很容易(页对齐即可)在这个函数里主要设置第二个映射, 临时借用了page结构里的一个链表结构(这个结构list在页面级分配器管理空闲页面用，现在不使用)next, prev分配用来指向cache, slab.