从零到一手写操作系统（七、内存 6）linux slab）

2022-04-26 / 2022-04-26 / virginOS

从零到一手写操作系统（七、内存 6）linux slab）

如果追忆会荡起涟漪，那么今天的秋红落叶和晴空万里都归你
https://aeneag.xyz
微信公众号：技术乱舞
艾恩凝

手写操作系统目录

7.8）SLAB 分配器

slab产生的原因就是为了解决物理内存的浪费着色区也是一块动态的内存块，建立 SLAB 时才会设置它的大小，目的是为了错开不同 SLAB 中的对象地址，降低硬件 Cache 行中的地址争用，以免导致 Cache 抖动效应，整个系统性能下降

7.8.1）SLAB对象

SLAB 分配器中，它把一个内存页面或者一组连续的内存页面，划分成大小相同的块，其中这一个小的内存块就是 SLAB 对象，但是这一组连续的内存页面中不只是 SLAB 对象，还有 SLAB 管理头和着色区

着色区也是一块动态的内存块，建立 SLAB 时才会设置它的大小，目的是为了错开不同 SLAB 中的对象地址，降低硬件 Cache 行中的地址争用，以免导致 Cache 抖动效应，整个系统性能下降。

Linux 中，SLAB 管理头用 kmem_cache 结构来表示，代码如下

 1struct array_cache {
 2    unsigned int avail;
 3    unsigned int limit;
 4    void *entry[]; 
 5};
 6struct kmem_cache {
 7    //是每个CPU一个array_cache类型的变量，cpu_cache是用于管理空闲对象的 
 8    struct array_cache __percpu *cpu_cache;
 9    unsigned int size; //cache大小
10    slab_flags_t flags;//slab标志
11    unsigned int num;//对象个数
12    unsigned int gfporder;//分配内存页面的order
13    gfp_t allocflags;
14    size_t colour;//着色区大小
15    unsigned int colour_off;//着色区的开始偏移
16    const char *name;//本SLAB的名字
17    struct list_head list;//所有的SLAB都要链接起来
18    int refcount;//引用计数
19    int object_size;//对象大小
20    int align;//对齐大小
21    struct kmem_cache_node *node[MAX_NUMNODES];//指向管理kmemcache的上层结构
22};

有多少个 CPU，就会有多少个 array_cache 类型的变量。这种为每个 CPU 构造一个变量副本的同步机制，就是每 CPU 变量（per-cpu-variable）。array_cache 结构中"entry[]"表示了一个遵循 LIFO 顺序的数组，"avail"和"limit"分别指定了当前可用对象的数目和允许容纳对象的最大数目。

第一个kmem_cache

 1static struct kmem_cache kmem_cache_boot = {
 2    .batchcount = 1,
 3    .limit = BOOT_CPUCACHE_ENTRIES,
 4    .shared = 1,
 5    .size = sizeof(struct kmem_cache),
 6    .name = "kmem_cache",
 7};
 8void __init kmem_cache_init(void)
 9{
10    int i;
11    //指向静态定义的kmem_cache_boot
12    kmem_cache = &kmem_cache_boot;
13    for (i = 0; i < NUM_INIT_LISTS; i++)
14        kmem_cache_node_init(&init_kmem_cache_node[i]);
15    //建立保存kmem_cache结构的kmem_cache
16    create_boot_cache(kmem_cache, "kmem_cache",
17        offsetof(struct kmem_cache, node) +
18                  nr_node_ids * sizeof(struct kmem_cache_node *),
19                  SLAB_HWCACHE_ALIGN, 0, 0);
20    //加入全局slab_caches链表中
21    list_add(&kmem_cache->list, &slab_caches);
22    {
23        int nid;
24        for_each_online_node(nid) {
25            init_list(kmem_cache, &init_kmem_cache_node[CACHE_CACHE + nid], nid);
26            init_list(kmalloc_caches[KMALLOC_NORMAL][INDEX_NODE],                      &init_kmem_cache_node[SIZE_NODE + nid], nid);
27        }
28    }
29    //建立kmalloc函数使用的的kmem_cache
30    create_kmalloc_caches(ARCH_KMALLOC_FLAGS);
31}

管理 kmem_cache

建好了第一个 kmem_cache，以后 kmem_cache 越来越多，而且我们并没有看到 kmem_cache 结构中有任何指向内存页面的字段，但在 kmem_cache 结构中有个保存 kmem_cache_node 结构的指针数组。

kmem_cache_node 结构是每个内存节点对应一个，它就是用来管理 kmem_cache 结构的，它开始是静态定义的，初始化时建立了第一个 kmem_cache 结构之后，init_list 函数负责一个个分配内存空间，代码如下所示。

 1#define NUM_INIT_LISTS (2 * MAX_NUMNODES)
 2//定义的kmem_cache_node结构数组
 3static struct kmem_cache_node __initdata init_kmem_cache_node[NUM_INIT_LISTS];
 4struct kmem_cache_node {
 5    spinlock_t list_lock;//自旋锁
 6    struct list_head slabs_partial;//有一部分空闲对象的kmem_cache结构
 7    struct list_head slabs_full;//没有空闲对象的kmem_cache结构
 8    struct list_head slabs_free;//对象全部空闲kmem_cache结构
 9    unsigned long total_slabs; //一共多少kmem_cache结构
10    unsigned long free_slabs;  //空闲的kmem_cache结构
11    unsigned long free_objects;//空闲的对象
12    unsigned int free_limit;
13};
14static void __init init_list(struct kmem_cache *cachep, struct kmem_cache_node *list,
15                int nodeid)
16{
17    struct kmem_cache_node *ptr;
18    //分配新的 kmem_cache_node 结构的空间
19    ptr = kmalloc_node(sizeof(struct kmem_cache_node), GFP_NOWAIT, nodeid);
20    BUG_ON(!ptr);
21    //复制初始时的静态kmem_cache_node结构
22    memcpy(ptr, list, sizeof(struct kmem_cache_node));
23    spin_lock_init(&ptr->list_lock);
24    MAKE_ALL_LISTS(cachep, ptr, nodeid);
25    //设置kmem_cache_node的地址
26    cachep->node[nodeid] = ptr;
27}

cache_grow_begin 函数获取内存页面，然后用获取的页面来存放对象

 1static void slab_map_pages(struct kmem_cache *cache, struct page *page,void *freelist)
 2{
 3    //页面结构指向kmem_cache结构
 4    page->slab_cache = cache;
 5    //指向空闲对象的链表
 6    page->freelist = freelist;
 7}
 8static struct page *cache_grow_begin(struct kmem_cache *cachep,
 9                gfp_t flags, int nodeid)
10{
11    void *freelist;
12    size_t offset;
13    gfp_t local_flags;
14    int page_node;
15    struct kmem_cache_node *n;
16    struct page *page;
17
18    WARN_ON_ONCE(cachep->ctor && (flags & __GFP_ZERO));
19    local_flags = flags & (GFP_CONSTRAINT_MASK|GFP_RECLAIM_MASK);
20    //获取页面
21    page = kmem_getpages(cachep, local_flags, nodeid);
22    //获取页面所在的内存节点号
23    page_node = page_to_nid(page);
24    //根据内存节点获取对应kmem_cache_node结构
25    n = get_node(cachep, page_node);
26    //分配管理空闲对象的数据结构
27    freelist = alloc_slabmgmt(cachep, page, offset,
28            local_flags & ~GFP_CONSTRAINT_MASK, page_node);
29    //让页面中相关的字段指向kmem_cache和空闲对象
30    slab_map_pages(cachep, page, freelist);
31    //初始化空闲对象管理数据
32    cache_init_objs(cachep, page);
33    return page;
34}
35
36static void cache_grow_end(struct kmem_cache *cachep, struct page *page)
37{
38    struct kmem_cache_node *n;
39    void *list = NULL;
40    if (!page)
41        return;
42    //初始化结page构的slab_list链表
43    INIT_LIST_HEAD(&page->slab_list);
44    //根据内存节点获取对应kmem_cache_node结构.
45    n = get_node(cachep, page_to_nid(page));
46    spin_lock(&n->list_lock);
47    //slab计数增加
48    n->total_slabs++;
49    if (!page->active) {
50        //把这个page结构加入到kmem_cache_node结构的空闲链表中
51        list_add_tail(&page->slab_list, &n->slabs_free);
52        n->free_slabs++;
53    } 
54    spin_unlock(&n->list_lock);
55}

cache_grow_begin 函数会为 kmem_cache 结构分配用来存放对象的页面，随后会调用与之对应的 cache_grow_end 函数，把这页面挂载到 kmem_cache_node 结构的链表中，并让页面指向 kmem_cache 结构。

7.8.2）SLAB分配对象的过程

根据请求分配对象的大小，查找对应的 kmem_cache 结构，接着从这个结构中获取 arry_cache 结构，然后分配对象。如果没有空闲对象了，就需要在 kmem_cache 对应的 kmem_cache_node 结构中查找有空闲对象的 kmem_cache。如果还是没找到，最后就要分配内存页面新增 kmem_cache 结构了。

SLAB 分配接口

内核中，用的最多的是 kmalloc 函数，经常用于分配小的缓冲区，或者数据结构分配实例空间，这个函数就是 SLAB 分配接口，它是用来分配对象的，这个对象就是一小块内存空间。

 1static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,unsigned long caller)
 2{
 3    struct kmem_cache *cachep;
 4    void *ret;
 5    if (unlikely(size > KMALLOC_MAX_CACHE_SIZE))
 6        return NULL;
 7    //查找size对应的kmem_cache
 8    cachep = kmalloc_slab(size, flags);
 9    if (unlikely(ZERO_OR_NULL_PTR(cachep)))
10        return cachep;
11    //分配对象
12    ret = slab_alloc(cachep, flags, caller);
13    return ret;
14}
15
16void *__kmalloc(size_t size, gfp_t flags)
17{
18    return __do_kmalloc(size, flags, _RET_IP_);
19}
20static __always_inline void *kmalloc(size_t size, gfp_t flags)
21{
22    return __kmalloc(size, flags);
23}

__do_kmalloc 函数中，查找出分配大小对应的 kmem_cache 结构，然后调用 slab_alloc 函数进行分配。

查找 kmem_cache 结构

 1enum kmalloc_cache_type {
 2    KMALLOC_NORMAL = 0,
 3    KMALLOC_RECLAIM,
 4#ifdef CONFIG_ZONE_DMA
 5    KMALLOC_DMA,
 6#endif
 7    NR_KMALLOC_TYPES
 8};
 9struct kmem_cache *kmalloc_caches[NR_KMALLOC_TYPES][KMALLOC_SHIFT_HIGH + 1] __ro_after_init ={ static u8 size_index[24] __ro_after_init = {
10    3,  /* 8 */
11    4,  /* 16 */
12    5,  /* 24 */
13    5,  /* 32 */
14    6,  /* 40 */
15    6,  /* 48 */
16    6,  /* 56 */
17    6,  /* 64 */
18    1,  /* 72 */
19    1,  /* 80 */
20    1,  /* 88 */
21    1,  /* 96 */
22    7,  /* 104 */
23    7,  /* 112 */
24    7,  /* 120 */
25    7,  /* 128 */
26    2,  /* 136 */
27    2,  /* 144 */
28    2,  /* 152 */
29    2,  /* 160 */
30    2,  /* 168 */
31    2,  /* 176 */
32    2,  /* 184 */
33    2   /* 192 */
34};
35//根据分配标志返回枚举类型，其实是0、1、2其中之一
36static __always_inline enum kmalloc_cache_type kmalloc_type(gfp_t flags)
37{
38#ifdef CONFIG_ZONE_DMA
39    if (likely((flags & (__GFP_DMA | __GFP_RECLAIMABLE)) == 0))
40        return KMALLOC_NORMAL;
41    return flags & __GFP_DMA ? KMALLOC_DMA : KMALLOC_RECLAIM;
42#else
43    return flags & __GFP_RECLAIMABLE ? KMALLOC_RECLAIM : KMALLOC_NORMAL;
44#endif
45}
46struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags)
47{
48    unsigned int index;
49    //计算出index
50    if (size <= 192) {
51        if (!size)
52            return ZERO_SIZE_PTR;
53        index = size_index[size_index_elem(size)];
54    } else {
55        if (WARN_ON_ONCE(size > KMALLOC_MAX_CACHE_SIZE))
56            return NULL;
57        index = fls(size - 1);
58    }
59    return kmalloc_caches[kmalloc_type(flags)][index];
60}

不难发现 kmalloc_caches 就是个全局的二维数组，kmalloc_slab 函数只是根据分配大小和分配标志计算出了数组下标，最后取出其中 kmem_cache 结构指针

kmalloc_caches 中的 kmem_cache建立

 1struct kmem_cache *__init create_kmalloc_cache(const char *name,
 2        unsigned int size, slab_flags_t flags,
 3        unsigned int useroffset, unsigned int usersize)
 4{
 5    //从第一个kmem_cache中分配一个对象放kmem_cache
 6    struct kmem_cache *s = kmem_cache_zalloc(kmem_cache, GFP_NOWAIT);
 7
 8    if (!s)
 9        panic("Out of memory when creating slab %s\n", name);
10    //设置s的对齐参数，处理s的freelist就是arr_cache
11    create_boot_cache(s, name, size, flags, useroffset, usersize);
12    list_add(&s->list, &slab_caches);
13    s->refcount = 1;
14    return s;
15}
16//新建一个kmem_cache
17static void __init new_kmalloc_cache(int idx, enum kmalloc_cache_type type, slab_flags_t flags)
18{
19    if (type == KMALLOC_RECLAIM)
20        flags |= SLAB_RECLAIM_ACCOUNT;
21        //根据kmalloc_info中信息建立一个kmem_cache
22    kmalloc_caches[type][idx] = create_kmalloc_cache(
23                    kmalloc_info[idx].name[type],
24                    kmalloc_info[idx].size, flags, 0,
25                    kmalloc_info[idx].size);
26}
27//建立所有的kmalloc_caches中的kmem_cache
28void __init create_kmalloc_caches(slab_flags_t flags)
29{
30    int i;
31    enum kmalloc_cache_type type;
32    for (type = KMALLOC_NORMAL; type <= KMALLOC_RECLAIM; type++) {
33        for (i = KMALLOC_SHIFT_LOW; i <= KMALLOC_SHIFT_HIGH; i++) {
34            if (!kmalloc_caches[type][i])
35                //建立一个新的kmem_cache
36                new_kmalloc_cache(i, type, flags);
37            if (KMALLOC_MIN_SIZE <= 32 && i == 6 &&
38                    !kmalloc_caches[type][1])
39                new_kmalloc_cache(1, type, flags);
40            if (KMALLOC_MIN_SIZE <= 64 && i == 7 &&
41                    !kmalloc_caches[type][2])
42                new_kmalloc_cache(2, type, flags);
43        }
44    }
45}

__do_kmalloc 函数中根据分配对象大小查找的所有 kmem_cache 结构，我们就建立好了，保存在 kmalloc_caches 数组中。

分配对象

slab_alloc 函数开始探索对象的分配过程，slab_alloc 函数的第一个参数就 kmem_cache 结构的指针，表示从该 kmem_cache 结构中分配对象

 1static __always_inline void *slab_alloc(struct kmem_cache *cachep, gfp_t flags, unsigned long caller)
 2{
 3    unsigned long save_flags;
 4    void *objp;
 5    //关中断
 6    local_irq_save(save_flags);
 7    //分配对象
 8    objp = __do_cache_alloc(cachep, flags);
 9    //恢复中断
10    local_irq_restore(save_flags);
11    return objp;
12}
13static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
14{
15    void *objp;
16    struct array_cache *ac;
17    //获取当前cpu在cachep结构中的array_cache结构的指针
18    ac = cpu_cache_get(cachep);
19    //如果ac中的avail不为0,说明当前kmem_cache结构中freelist是有空闲对象
20    if (likely(ac->avail)) {
21        ac->touched = 1;
22        //空间对象的地址保存在ac->entry
23        objp = ac->entry[--ac->avail];
24        goto out;
25    }
26    objp = cache_alloc_refill(cachep, flags);
27out:
28    return objp;
29}
30static __always_inline void *__do_cache_alloc(struct kmem_cache *cachep, gfp_t flags)
31{
32    return ____cache_alloc(cachep, flags);
33}

真正做事的函数是 ____cache_alloc 函数，它首先获取了当前 kmem_cache 结构中指向 array_cache 结构的指针，找到它里面空闲对象的地址，然后在 array_cache 结构中取出一个空闲对象地址返回，这样就分配成功了。

如果 array_cache 结构中没有空闲对象了，就会调用 cache_alloc_refill 函数

 1static struct page *get_first_slab(struct kmem_cache_node *n, bool pfmemalloc)
 2{
 3    struct page *page;
 4    assert_spin_locked(&n->list_lock);
 5    //首先从kmem_cache_node结构中的slabs_partial链表上查看有没有page
 6    page = list_first_entry_or_null(&n->slabs_partial, struct page,slab_list);
 7    if (!page) {
 8    //如果没有
 9        n->free_touched = 1;
10    //从kmem_cache_node结构中的slabs_free链表上查看有没有page
11        page = list_first_entry_or_null(&n->slabs_free, struct page,slab_list);
12        if (page)
13            n->free_slabs--; //空闲slab计数减一
14    }
15    //返回page
16    return page;
17}
18static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)
19{
20    int batchcount;
21    struct kmem_cache_node *n;
22    struct array_cache *ac, *shared;
23    int node;
24    void *list = NULL;
25    struct page *page;
26    //获取内存节点
27    node = numa_mem_id();
28    ac = cpu_cache_get(cachep);
29    batchcount = ac->batchcount;
30    //获取cachep所属的kmem_cache_node
31    n = get_node(cachep, node);
32    shared = READ_ONCE(n->shared);
33    if (!n->free_objects && (!shared || !shared->avail))
34        goto direct_grow;
35    while (batchcount > 0) {
36        //获取kmem_cache_node结构中其它kmem_cache,返回的是page，而page会指向kmem_cache
37        page = get_first_slab(n, false);
38        if (!page)
39            goto must_grow;
40        batchcount = alloc_block(cachep, ac, page, batchcount);
41    }
42must_grow:
43    n->free_objects -= ac->avail;
44direct_grow:
45    if (unlikely(!ac->avail)) {
46        //分配新的kmem_cache并初始化
47        page = cache_grow_begin(cachep, gfp_exact_node(flags), node);
48        ac = cpu_cache_get(cachep);
49        if (!ac->avail && page)
50            alloc_block(cachep, ac, page, batchcount);
51        //让page挂载到kmem_cache_node结构的slabs_list链表上
52        cache_grow_end(cachep, page);
53        if (!ac->avail)
54            return NULL;
55    }
56    ac->touched = 1;
57    //重新分配
58    return ac->entry[--ac->avail];
59}