slab allocator （1） —— 初始化

Posted on Edited on
前面提到过的buddy allocator通过用order列表来管理页面，从而达到减少外部碎片的效果。但是不可能每次分配都分配一页或者几页的内存，那样内存利用率太低，系统中将充满了内部碎片。所以，slab分配器也就应运而生了，其就是为了减少内部碎片而生的。具体为什么引入，以及slab的一些简介可以参考 Linux slab 分配器剖析， Fred's blog: 三月 2009。

     
     所谓的slab就是基于这么一张图的系统。简化之，其实就是一种基于后备高速缓存内存分配（参考ldd3，page247 ch 8）方式的内存管理系统。

     他的初始化由下图中的g_cpucache_up来标志，共有5个状态，按顺序依次迁移，在start_kernel -> mm_init -> kmem_cache_init中到达EARLY状态。此时slab_is_availabe()函数就返回真，也就是说此时slab系统已经就绪了。而最终的FULL状态是在kmem_cache_init_late中完成的。


上面这几个函数中可以看出，核心其实就是 kmem_cache_init。下面将重点介绍这个函数。
     这个函数很大，而且包含了很多知识点，具体可以参考《Understanding the Linux® Virtual Memory Manager》chapter 8。关于slab系统的内容很多，而且不是很好理解。先列举几个重要的数据结构。当然最核心的数据结构就是kmem_cache了，因为他巨大，所以就不在此列举了。

    1. kmem_list3
     struct kmem_list3 {
     struct list_head slabs_partial;     /* partial list first, better asm code */
     struct list_head slabs_full;
     struct list_head slabs_free;
     unsigned long free_objects;
     unsigned int free_limit;
     unsigned int colour_next;     /* Per-node cache coloring */
     spinlock_t list_lock;
     struct array_cache *shared;     /* shared per node */
     struct array_cache **alien;     /* on other nodes */
     unsigned long next_reap;     /* updated without locking */
     int free_touched;          /* updated without locking */
};
最重要的就是前3个参数，也就是我们在图1中提到的三个list：slab_full, slab_partial, slab_empty。

     2. array_cache
struct array_cache {
     unsigned int avail;
     unsigned int limit;
     unsigned int batchcount;
     unsigned int touched;
     spinlock_t lock;
     void *entry[];     /*
               * Must have this definition in here for the proper
               * alignment of array_cache. Also simplifies accessing
               * the entries.
               */
};
struct kmem_cache {
/* 1) per-cpu data, touched during every alloc/free */
     struct array_cache *array[NR_CPUS];
          ……
}
          array_cache是per CPU变量，具体可参考《Understanding the Linux® Virtual Memory Manager》chp 8.5: Per-CPU Object Cache。每一个cache，在create的时候，都会被分配一个array_cache（enable_cpucache）来提高性能。当然我们的总cache——cache_cache（从名字可以看出，它是cache的cache）也有一个这样的变量，在初始化时被填了一个__init_data initarray_cache.cache。之后在kmem_cache_init中再通过kmalloc来分配。arraycache与kmem_cache的关系大体如下图
     关于array_cache具体的内容会在另一篇笔记中作介绍slab allocator （3）—— arraycache。

     3. cache_sizes
     Gorman的书中将其称之为sizes cache。其实他就是一组定义了size的cache。在slab初始化的时候，我们会经常看到malloc_sizes这个数组，其定义如下：
struct cache_sizes malloc_sizes[] = {
#define CACHE(x) { .cs_size = (x) },
#include <linux/kmalloc_sizes.h>
     CACHE(ULONG_MAX)
#undef CACHE
};
struct cache_sizes {
     size_t               cs_size;
     struct kmem_cache     *cs_cachep;
#ifdef CONFIG_ZONE_DMA
     struct kmem_cache     *cs_dmacachep;
#endif
};
再看linux/kmalloc_sizes.h
#if (PAGE_SIZE == 4096)
     CACHE(32)
#endif
     CACHE(64)
#if L1_CACHE_BYTES < 64
     CACHE(96)
#endif
     CACHE(128)
#if L1_CACHE_BYTES < 128
     CACHE(192)
#endif
     CACHE(256)
     CACHE(512)
     CACHE(1024)
     CACHE(2048)
     CACHE(4096)
     CACHE(8192)
     CACHE(16384)
     CACHE(32768)
     CACHE(65536)
     CACHE(131072)
     ……
          稍加分析我们就可以知道在kmalloc_sizes.h中已经定义好了一组固定size的cache了，只是他们对应的两组cache列表（cs_cachep, cs_dmacachep）还没分配。之后在我们的kmem_cache_init中对INDEX_AC和INDEX_L3的初始化，都是在为这个数组的成员初始化。
INDEX_AC：sizeof(struct arraycache_init)对应的malloc_sizes中的索引。
INDEX_L3：sizeof(struct kmem_list3)对应的malloc_sizes中的索引。
          为什么要把这两个size单独提出来做初始化，我推测是因为在kmem_cache_create到时候需要频繁的分配arraycache_init和kmem_list3，而且对于kmem_cache来说也就这两个struct是需要动态分配的，所以需要先对这两个size的cache先做初始化，以便在初始化其他malloc_sizes数组成员的时候，可以使用这两个cache来为之分配arraycache_init和kmem_list3。

          说完这些数据结构了，再回头看看kmem_cache_init的流程。其实无非就是对cache_cache，malloc_sizes做初始化，下面还有几个值得关注的点。
     1. cache_chain
          在kmem_cache_init的一开始处，有
INIT_LIST_HEAD(&cache_chain);
list_add(&cache_cache.next, &cache_chain);
尚不知这个cache_chain是作何用的，先暂且列在这里

     2. cache_estimate
     1504     for (order = 0; order < MAX_ORDER; order++) {
1505         cache_estimate(order, cache_cache.buffer_size,
1506             cache_line_size(), 0, &left_over, &cache_cache.num);
1507         if (cache_cache.num)
1508             break;
1509     }
          这个函数作用其实很简单，就是决定：(1)cache_cache.buffer_size，也就是cache_cache的object size，以及可以存储多少个object (2)slab manager存储位置（on-slab/off-slab：看看flags是否包含CFLGS_OFF_SLAB）(3)利用slab上剩余的空间，初始化coloring机制。
          一个cache_cache的slab空间分割如下图：
          其中object的size如下：
          offsetof(struct kmem_cache, nodelists) + nr_node_ids * sizeof(struct kmem_list3 *);
          其实就是sizeof(kmem_cache)。可见cache_cache的slab要分配的就是kmem_cache。最后cache_cache->slab_size = slab_mgmt_size。
          coloring scheme的初始化为：
          cache_cache.colour_off = cache_line_size();
          cache_cache.colour = left_over / cache_cache.colour_off;
     
     3. init_list
          在kmem_cache_init的最后，有
1604         for_each_online_node(nid) {
1605             init_list(&cache_cache, &initkmem_list3[CACHE_CACHE + nid], nid);
1606
1607             init_list(malloc_sizes[INDEX_AC].cs_cachep,
1608                   &initkmem_list3[SIZE_AC + nid], nid);
1609
1610             if (INDEX_AC != INDEX_L3) {
1611                 init_list(malloc_sizes[INDEX_L3].cs_cachep,
1612                       &initkmem_list3[SIZE_L3 + nid], nid);
1613             }
1614         }
          init_list写的很复杂，其实仔细理解之后，实现的内容很简单，就是为cache_cache以及两个size cache （INDEX_AC, INDEX_L3）分配kmem_list3结构体，并用memcpy将initkmem_list3中的内容拷贝过来，另外再用MAKE_ALL_LISTS -> MAKE_LIST -> list_splice 来合并initkmem_list3列表中的内容。
可见有时候，不要把复杂的问题想简单了，该仔细处理的还是要仔细处理，特别是针对这种列表结构体。

kmem_cache_init中也运用kmem_cache_create来分配cache了，但这个过于复杂，将在另一篇笔记中加以阐述slab allocator （2）—— kmem_cache_create。