slab分配器简明分析

这还是暑假之前写的总结... 这几天一个kernel群里老有人问关于slab方面的问题... 所以就在这里把些的总结贴一下... 献丑了...

Slab Allocator 逻辑结构如下图所示:

如图,主要结构包括 cache 以及 slabs。故相应的数据结构有 cache 描述符和 slab 描述符。
cache 描述符
          struct kmem_cache_s {
               /* full, partial first, then free */
               struct list_head         slabs_full;
               struct list_head         slabs_partial;
               struct list_head         slabs_free;
               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
            unsigned int         gfporder;
            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;
            char           name[CACHE_NAMELEN];
            struct list_head     next;
      #ifdef CONFIG_SMP
            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
};
各个字段含义如下:
slab_*                  保存slabs的链表,如上图,full、partial和empty。
objsize                 装入缓存器中的每个”对象”的大小。
flags                   决定当处理这个缓存器时,分配器的部分行为。见8.1.2
num                     每个slab包含的”对象”的数量
  spinlock             保护这个结构的自旋锁,防止并发访问
  batchcount           决定对于每个CPU的缓存器,一次所分配的”对象”的数量
  gfporder             表示slab的页面的数量。每slab有2^gfporder个页面。因为这
                       是伙伴分配器所提供的分配大小。
  gfpflags             保存当调用伙伴分配器分配页面时所用到GFP标识。
  colour               每个slab会尽可能的将”对象”保存到不同的高速缓存行。缓存器着色
                       会在8.1.5节深入讨论。
  colour_off           保持slabs对齐到的字节数。例如,对于size-X缓存器里的slab会对齐到
                       L1高速缓存。
  colour_next          下一个要使用的颜色行。当这个值达到colour时就会反绕到0。
  growing              设置这个标识可以表示这个缓存器的大小是否增加了。如果增加了,
                       则在内存紧张时,选择它来获取空闲的slabs的可能性会更小。
  dflags               在缓存器存在期间会改变的动态标识。
  ctor                 一个复杂的”对象”可以可选的提供一个构造函数来初始化每个新
                       的”对象”。这是指向那个函数的指针,而且可以是NULL。
  dtor                 析构函数的指针,可以是NULL。
  failure              在代码中不在使用这个字段,因此都初始化为0。
  name                 每个缓存器的名称
  next                 缓存器链表上的下一个缓存器。
  cpudata              每CPU数据,指向描述一小组可用”对象”的管理结构。
  num_active           在缓存器中当前活跃的”对象”的数量
  num_allocations      在缓存器中已经分配了的”对象”的数量的总数。
  high_mark            num_active能够达到的最大的值
  grown                kmem_cache_grow()被调用的次数
  reaped               缓存器被释放的次数
  allochit             分配时,从每CPU缓存中分配”对象”的次数
  allocmiss            与allochit相反
  freehit              将”对象”释放到每CPU缓存中的次数
  freemiss             与freehit相反。
  这个结构相当的大,Slab Allocator中对每种”对象”都有一个对应的cache。每个cache管理
  多个slab。Slab才是真正存放”对象”的地方。管理这些”对象”的结构就是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                 此 slab 所属于的链表。这个字段是在缓存器中的 slab_full 或者
                       slab_patial 或者 slab_free 上。
  colouroff            这是离在 slab 中的第一个”对象”的基址的着色偏移值。                          第一个对象的
                     地址是 s_mem + colouroff。
  s_mem              给出在 slab 中第一个”对象”的起始地址。
  inuse              在 slab 中的活跃”对象”的个数。
  free               存储空闲”对象”的 bufctls 数组。参见 8.2.3 中的详细介绍。
  这个结构仅仅是用来管理”对象”的,在创建 slab 时需要分配存放”对象”的内存,所需内存
  从 buddy allocator 中申请,内存大小为其所属 cache 中 gfporder 指定。显然,所申请的内
  存是连续的 2^cachep->gfporder 个页面。Slab 描述符可以存放在这个所分配的内存起始
  处,也可以放在另外的地方。如图:


 通用缓存器组
  typedef struct cache_sizes {
       size_t         cs_size;
       kmem_cache_t       *cs_cachep;
       kmem_cache_t       *cs_dmacachep;
  } cache_sizes_t;
  各字段含义如下:
  cs_size              这个通用缓存器的大小
  cs_cachep            用于在普通内存中分配”对象”的缓存器指针
  cs_dmacachep         用于在 DMA 内存中分配”对象”的缓存器指针
  在系统中静态定义了这个类型的一个数组,其主要为大小不定的一些通用结构分配内存。
  例如,如过 Slab 描述符的位置是 Off_Slab,则这个 Slab 描述符以及其后的 kmem_bufctl_t[]
  就放在这个通用缓存器组中的某一个缓存器里。
下面所要将到的数据结构是针对 SMP 系统进行优化所用到的数据结构:
 每 CPU cache
  typedef struct cpucache_s {
        unsigned int avail;
        unsigned int limit;
  } cpucache_t;
  avail      在这个 cpucache 上空闲”对象”的数量。
  limit      可以存在的空闲”对象”的总数。
  每个 CPU 都有一个对应的小的本地 cache,这个 cache 并不是上面所提到的 cache 描述符。
  这个 cache 仅仅是特定于某个 cache 描述符所管理的”对象”的数组。如 mm_struct 相关
  的 cache 描述符所管理的”对象”就是 mm_struct 类型的,则这个 CPU 的本地 cache 就是
  mm_struct 类型的数组。在为某 CPU 分配 cpucache_t 结构时,除了分配 cpucache_t 结构
  所需要的内存外,也分配 limit*sizeof(void *)字节的内存。当然,它们是连续的。
  如代码所示:
             ccnew = kmalloc(sizeof(void*)*limit+
                       sizeof(cpucache_t), GFP_KERNEL);
  ccnew 就是 cpucache_t *类型。
  因此 cpucache_t 结构后面就是 limit 个 void 类型的指针。                 所以 avail 还有一个作用就是作
  为空闲”对象”的索引。如在从这个 CPU 本地 cache 分配一个”对象”时就有如下代码:
             obj = cc_entry(cc)[--cc->avail];
  其中:
             #define cc_entry(cpucache) \
                  ((void **)(((cpucache_t*)(cpucache))+1))
  这个代码就可以解释上面所说的一切。
  更新每 CPU cache 信息所用到的数据结构

  typedef struct ccupdate_struct_s
  {
        kmem_cache_t *cachep;
        cpucache_t *new[NR_CPUS];
  } ccupdate_struct_t;
  cachep 是正在被更新的缓存器的指针,new 是系统中每个 CPU 的 cpucache 描述符的数组。
  当然仅有在 SMP 系统上设置 SMP 选项时才可用。
  在每 CPU cache 信息改变之后,在更新每个 CPU cache 信息时就不需要考虑并发性带来
  的一致性问题,因为每个 CPU 只为从对应的 ccpudata_struct_t->new[ID]中获取新信息来
  更新自己本地的 cache。这样就不需要用自旋锁来保护。

Slab初始化过程
静态初始化
  所谓静态初始化就是指编译内核时进行的初始化过程。
  /* internal cache of cache description objs */
  static kmem_cache_t cache_cache = {
        slabs_full:      LIST_HEAD_INIT(cache_cache.slabs_full),
        slabs_partial: LIST_HEAD_INIT(cache_cache.slabs_partial),
        slabs_free:      LIST_HEAD_INIT(cache_cache.slabs_free),
        objsize:         sizeof(kmem_cache_t),
        flags:           SLAB_NO_REAP,
        spinlock:        SPIN_LOCK_UNLOCKED,
        colour_off:      L1_CACHE_BYTES,
        name:            "kmem_cache",
  };
  之所以需要预先静态的定义一个缓存器,是因为如果内核需要创建一个缓存器,则必须要
  从某一个缓存器中分配一个 kmem_cache_t”对象”,可是这个缓存器从哪里来呢？显然,
  这是一个先有鸡还是先有蛋的问题。所以就需要预先静态的定义一个缓存器,并初始化
  一些能够在编译时初始化的字段。
 动态初始化
  所谓动态初始化,当然就是 Linux 内核被加载到内存,并开始初始化系统的阶段,对 Slab
  Allocator 进行的初始化。
  起点是在 init/main.c 文件中的 start_kernel()函数,其调用 kmem_cache_init()。
  故 kmem_cache_init()函数负责对 Slab Allocator 进一步的初始化。
        /* Initialisation - setup the `cache' cache. */
        void __init kmem_cache_init(void)
        {
             size_t left_over;
     init_MUTEX(&cache_chain_sem);
     INIT_LIST_HEAD(&cache_chain);
该函数负责计算给定大小的 slab 上能够存放多少个”对象”以及所浪费的字节数
     kmem_cache_estimate(0, cache_cache.objsize, 0,
                   &left_over, &cache_cache.num);
     if (!cache_cache.num)
            BUG();
     cache_cache.colour = left_over/cache_cache.colour_off;
     cache_cache.colour_next = 0;
}
上面粗体部分就是 cache_cache 结构中被初始化了的字段
接着会调用 kmem_cache_sizes_init()。
/* Initialisation - setup remaining internal and general caches.
  * Called after the gfp() functions have been enabled, and before smp_init().
  */
void __init kmem_cache_sizes_init(void)
{
     cache_sizes_t *sizes = cache_sizes;
     char name[20];
     /*
       * Fragmentation resistance on low memory - only use bigger
       * page orders on machines with more than 32MB of memory.
       */
     if (num_physpages > (32 << 20) >> PAGE_SHIFT)
            slab_break_gfp_order = BREAK_GFP_ORDER_HI;
     do {
            /* For performance, all the general caches are L1 aligned.
              * This should be particularly beneficial on SMP boxes, as it
              * eliminates "false sharing".
              * Note for systems short on memory removing the alignment will
              * allow tighter packing of the smaller caches. */
            snprintf(name, sizeof(name), "size-%Zd",sizes->cs_size);
            if (!(sizes->cs_cachep =
从 cache_cache 中获取一个缓存器描述符,并且根据参数初始化一些必要字段。
                   kmem_cache_create(name, sizes->cs_size,
                             0, SLAB_HWCACHE_ALIGN, NULL, NULL))) {
                   BUG();
            }
            /* Inc off-slab bufctl limit until the ceiling is hit. */
            if (!(OFF_SLAB(sizes->cs_cachep))) {
                   offslab_limit = sizes->cs_size-sizeof(slab_t);
                       offslab_limit /= 2;
                }
                snprintf(name, sizeof(name), "size-%Zd(DMA)",sizes->cs_size);
                sizes->cs_dmacachep = kmem_cache_create(name, sizes->cs_size, 0,
                               SLAB_CACHE_DMA|SLAB_HWCACHE_ALIGN, NULL, NULL);
                if (!sizes->cs_dmacachep)
                       BUG();
                sizes++;
           } while (sizes->cs_size);
       }
       do-while 循环中针对 cache_sizes 中的每一项调用 kmem_cache_creat 。 建立在
  NORMAL 区以及 DMA 区的固定大小的缓存器。并且间接的进一步初始化 cache_cache。
 总结初始化过程
  由于 Slab Allocator 中需要缓存器来描述管理 Slab,并且”对象”都在 Slab 之上,所谓 Slab 就
  是一组连续的页面,数量一定是二的幂次方。当系统初始化时,从 boot memory allocator
  到 buddy allocator 都是一次分配一组页面,但初始化 Slab Allocator 时,可能就会有疑问,第
  一个缓存器描述符从哪里来,因为缓存器描述符的大小远小于一个页面。所以肯定不能
  从 buddy allocator 中动态的获取 , 于是乎 , 就只能先静态的定义一个缓存描述符 , 即
  cache_cache。这样以后所需要的缓存器描述符就可以从这个专门管理缓存器描述符分
  配的缓存器中分配了。当然初始化 cache_cache 时,这个缓存器还没有 slab。是当继续初
  始化另外的数据结构时需要缓存器描述符时,发现 cache_cache 没有可用 Slab 时才会为
  其分配一个 Slab。还需要注意一点,Slab 描述符分为 On-Slab 和 Off-Slab。意思就是存储
  Slab 描述符有两种方案,一种是放在所分配的 Slab 的开始处,另外一种是放在另外的一个
  地方,放在 Slab 的开始处很容易,可以放在另外的地方,这个另外的地方是哪里呢.在这里
  就需要注意,查看源代码可以清楚 ,当”对象”的大小大于三个页面 ,并且满足一些列的额
  外的条件,(具体参考源代码,这里只考虑初始化,不考虑其他调用所指定 CFLGS_OFF_SLAB
  标识的情况)则 slab 描述符就是 Off_Slab。             又由于 slab 描述符的后面一定是 kmem_bufctl_t
  类型的数组,而 kmem_bufctl_t 数组的大小又不是一定的,所以如果 slab 描述符是 Off_Slab,
  所以就不能将 slab 描述符称为一个”对象”。                     又考虑到也许有许多常用的结构并不一定是
  定长的 , 所以 Slab Allocator 又建立了一个通用的固定大小的缓存 , 即 cache_sizes 。
  cache_sizes 中包含许多缓存器,每个缓存器的”对象”的大小都是 2 的幂次方,当然既然是
  通用,就不要求每个”对象”都恰好满足其大小,只要足够大能够容纳即可。这样就可以解
  决 slab 描述符的位置是 Off_Slab 的问题了。
  综上所述:
       系统通过静态定义的 cache_cache 来提供缓存器描述符这个”对象”的分配,然后将那
  些其管理的 Slab 的位置是 Off_Slab 的缓存器的 slab 描述符放在通用的缓存器中。
  每当创建某缓存器时就可以从 cache_cache 这个缓存器中获取缓存器描述符”对象”,当第
  一次从该缓存器上申请”对象”时,就会为其创建 Slab。
  具体 Slab Allocator 如何分配以及管理”对象”在此不详述。
  附---每 CPU”对象”缓存初始化

这个部分我并不认为是对 Slab Allocator 初始化,因为这个初始化是建立在 Slab Allocator
的基本结构完全初始化之后的。应成为关于 Slab Allocator 的每 CPU 结构初始化。
初始化的结构是 cachep->cpudata[]。
其初始化起点是由 init 进程调用 kmem_cpucache_init()所开始执行的。
具体代码不赘述(参考相关代码)
过程简述为:针对已建立的的每个缓存器,初始化其上的 cpudata[]结构。具体初始化过程
为,根据缓存器所管理的”对象”的大小,确定这个”对象”在每 CPU 上的规模,即数量。然后
从通用缓存器组中申请足以容纳 cpudata_t 结构以及所需管理”对象”的指针数组。并把
这块内存的起始地址填入以 CPU ID 为索引的 cachep->cpudata[]的元素中。

Slab的内存分配方式

     由于创建 cache 描述符以及 slab 描述符本质上都是通过 Slab Allocator 来分配相应的
cache”对象”和 slab”对象”。           所以在此并不像书本那样先讲 cache 描述符的创建过程,然后再讲
slab 描述符的分配,最后再讲”对象”的分配。                          当然 cache 描述符和 slab 描述符一定是先存在的。
但是 cache 描述符以及 slab 描述符的创建本质上也是”对象”分配。所以首先只介绍 Slab
Allocator 是如何来分配”对象”的。
     从 Slab Initialization 中可以知道,在系统初始化时就已经建立起了一个存储 cache 描述符”
对象”的缓存器以及一个通用缓存器组。有这两样就足够动态的建立更多的缓存器了。
     “对象”的分配

     先说明 UP 平台上的分配方法,当然这里提到的方法在 SMP 平台上也会用到。
#define kmem_cache_alloc_one(cachep)                        \
({                                         \
     struct list_head * slabs_partial, * entry;     \
     slab_t *slabp;                             \
                                           \
     slabs_partial = &(cachep)->slabs_partial;          \
     entry = slabs_partial->next;                   \
     if (unlikely(entry == slabs_partial)) {            \
           struct list_head * slabs_free;           \
           slabs_free = &(cachep)->slabs_free;          \
           entry = slabs_free->next;                \
           if (unlikely(entry == slabs_free))       \
                 goto alloc_new_slab;               \
           list_del(entry);                \
           list_add(entry, slabs_partial);          \
     }                                     \
                                           \
     slabp = list_entry(entry, slab_t, list);       \
     kmem_cache_alloc_one_tail(cachep, slabp);          \
})
可见,Slab Allocator 总是选择从 cache 的 slabs_partial 上的 slab 中分配,如果这个链表为空,则
从 slabs_free 上摘下一个 slab 并挂到 slabs_partial 链表上,但如果这个链表也为空,则说明这个
cache 上没有空闲的”对象”了(在 cache 刚刚创建时当然就是这种情形),那么就会执行
goto alloc_new_slab ,新分配一个 slab,然后在回到这里继续尝试分配。                        选择一个由可用”对象”
的 slab 之后,就可以调用 kmem_cache_alloc_one_tail()中这个 slab 中分配一个了。
下面来看具体的分配操作：
(为增加可读性,删除了调试部分代码)
static inline void * kmem_cache_alloc_one_tail (kmem_cache_t *cachep,
                                   slab_t *slabp)
{
      void *objp;
      /* get obj pointer */
      slabp->inuse++;
      objp = slabp->s_mem + slabp->free*cachep->objsize;
      slabp->free=slab_bufctl(slabp)[slabp->free];
      if (unlikely(slabp->free == BUFCTL_END)) {
            list_del(&slabp->list);
            list_add(&slabp->list, &cachep->slabs_full);
      }
      return objp;
}
本质上,slab 上的”对象”的组织方式像一个后进先出的栈,slabp->free 总是记录最后一个”对象”
的索引,这里的”最后”并不是分布位置的最后,而是时间上的最后。slabp->free 就像一个栈指
针。
这段代码,首先找到可用”对象”,然后更新 slabp->free。最后检查 slab 上的”对象”是否分配完,
如果是,则将该 slab 从其链表中删除,并添加到 slabs_full 链表上。                      最后返回可用”对象”的指针。
下面再来看看 SMP 平台上的分配”对象”的方法。
由于针对 SMP 平台进行了优化,即建立了每 CPU 数据结构,所以,针对”对象”,也有每 CPU”对象”
缓存,即给每个 CPU 分配了一个特定”对象”的本地”对象”数组。当需要分配某一”对象”时,其
执行这个分配的 CPU 就会尽量尝试从本地”对象”数组中分配。当然如果没有对应的 CPU”本
地””对象”数组,则就像 UP 平台那样进行”对象”分配,这种情形就不加讨论了。
相关代码如下:
#ifdef CONFIG_SMP
      {
            cpucache_t *cc = cc_data(cachep);
            if (cc) {
                  if (cc->avail) {
                      STATS_INC_ALLOCHIT(cachep);
                      objp = cc_entry(cc)[--cc->avail];
                } else {
                      STATS_INC_ALLOCMISS(cachep);
                      objp = kmem_cache_alloc_batch(cachep,cc,flags);
                      if (!objp)
                            goto alloc_new_slab_nolock;
                }
          } else {
                spin_lock(&cachep->spinlock);
                objp = kmem_cache_alloc_one(cachep);
                spin_unlock(&cachep->spinlock);
          }
    }
    显然,如果存在每 CPU”对象”缓存,则可以直接从 cachep->cpudata[CPUID]中获取一个”对
象”,如果没有,则这次分配就退化为 UP 平台上的获取一个”对象”的过程。                                     但是也有可能每 CPU
“对象 ”缓存使用完了 , 这时 , 就会对 这个缓存进行补充 , 调用 kmem_cache_alloc_batch() 从
cachep 中分配 batch 个”对象”,补充入这个缓存中。当然这时的分配过程和 UP 平台上的分配
“对象”的方法是一样的。总之,最后的”对象”的来处一定是从每 CPU”对象”缓存中获取的。
具体的 cache 和 slab 描述符的创建过程参见具体代码。
    “对象”的释放

    不管是 UP 平台还是 SMP 平台,释放一个对象的函数都是一个,即 kmem_cache_free_one()。
    只不过,UP 平台是直接调用 kmem_cache_free_one()来释放”对象”。
    但由于 SMP 平台有每 CPU”对象”缓存,所以在释放一个”对象”时,最好的情况是直接归还
    给这个每 CPU”对象”缓存,只有在不存在相应的每 CPU”对象”缓存或者每 CPU”对象”缓存
    的 可 用 ” 对 象 ” 超 过 limit, 才 会 直 接 释 放 掉 , 只 不 过 对 于 后 者 , 要 反 复 调 用
    kmem_cache_free_one()来释放 batch 个每 CPU”对象”缓存中的”对象”。
    下面只列出 kmem_cache_free_one()函数。
    (为了可读性,删除了调试代码)
    static inline void kmem_cache_free_one(kmem_cache_t *cachep, void *objp)
    {
          slab_t* slabp;
          slabp = GET_PAGE_SLAB(virt_to_page(objp));
          {
                unsigned int objnr = (objp-slabp->s_mem)/cachep->objsize;
                slab_bufctl(slabp)[objnr] = slabp->free;
                slabp->free = objnr;
          }
     /* fixup slab chains */
     {
           int inuse = slabp->inuse;
           if (unlikely(!--slabp->inuse)) {
                 /* Was partial or full, now empty. */
                 list_del(&slabp->list);
                 list_add(&slabp->list, &cachep->slabs_free);
           } else if (unlikely(inuse == cachep->num)) {
                 /* Was full. */
                 list_del(&slabp->list);
                 list_add(&slabp->list, &cachep->slabs_partial);
           }
     }
  }
  这段简单的代码的意思是不言而喻的,再次不赘述。
  在此,需要注意的是,slab 上的页面和所属 slab 以及所属 cache 的关系。如图:

  附:

  通用缓存器组中的内存分配:
  这个函数的接口是 kmalloc(),实质是和普通的”对象”分配是一样的,但是因为这里的缓存
  器是通用的,所以分配的内存的大小是参差不齐的。 ,在需要分配一片内存时,就寻找一              故
  个足以容纳需要分配的数据所占的内存的缓存器,并在这个缓存器上分配内存给它。显
  然这样会产生内部碎片,但是相比其他的分配方案,这在性能以及碎片率上都有会很好的
  表现。
通用缓存器组中的内存释放:
这个函数的接口是 kfree(),本质同一般的”对象”释放一样。不赘述。
这两个函数参见 slab.c 中的具体代码。不列出讨论。