SLab分配器

SLab 分配器

Buddy System 负责分配连续的物理内存页，但是如果系统遇到了小内存分配的需求，比如仅仅数十个字节的结构体等，这时候若继续使用伙伴系统，由于其最少只能分配 4KB 的内存，便会造成严重的内部碎片问题。而 SLab 分配器（SLub）便是专用于小内存分配的，它和 Buddy System 一起构成了 Chcore 的物理内存管理系统

本节内容承接上文，为大家介绍 Chcore 中 SLab 分配器的设计与具体实现，主要还是包括三个部分：

  • 回顾 SLab 分配器的基础知识与设计理念
  • 分析 Chcore 源码对 SLab 的代码实现与架构
  • 解析 Chcore 源码对 SLab 操作相关函数的具体实现

回顾：SLab 分配器的设计理念

SLab 专用于小内存的分配。和伙伴系统不同，SLab 本身不涉及对内存块的合并与分裂，而是通过一个个不同的 SLab 池，来分配不同固定大小的内存块，并且在 SLab 池内部使用链表结构串起一个个 SLab，SLab 内部又使用空闲链表的结构，便可以对所有的空闲内存块进行管理和分配

基本结构

  • SLab 是一个内存分配器，主要用于分配小块内存（32 字节到 2048 字节之间）
  • 整个系统维护了多个不同大小的 slab_pool ，每个池对应特定大小的内存块
  • 内存大小按 2 的幂次方划分：32, 64, 128, 256, 512, 1024, 2048 字节（从 2^5 到 2^11）

SLab 的内部组织

每个 slab_pool 由多个 slab 组成，每个 slab 又具有以下特点：

  • 固定大小为 128KB（SIZE_OF_ONE_SLAB）
  • 包含一个 slab_header（位于 slab 开始处）
  • 剩余空间被划分为大小相等的对象槽（slots）
  • 使用空闲链表（free_list）管理未分配的对象槽
  • 每个 slab_pool 有 current 和 partial 指针，分别指向当前 slab 以及总的 slab 链表组

SLab 的工作流程

  • 当请求分配内存时，SLAB 分配器会首先从部分使用 Slab 链表中查找是否有可用的对象
  • 如果没有，它会从空闲 Slab 链表中取出一个 slot，并将其移动到部分使用 Slab 链表
  • 如果空闲链表也为空（即 partial 为空），则会从内存中（即伙伴系统）分配一个新的 slab，然后进行上一步操作
  • 当释放内存块时，如果一个 slab 中的所有 slots 都被释放，则该 slab 会被移动到空闲 Slab 链表

有如下示意图以供参考

SLAB 分配器
Slab Pool
Slab 1
Slab 2
Slab N
对象 1
对象 2
对象 M
对象 1
对象 2
对象 M
对象 1
对象 2
对象 M
空闲 Slab 链表
部分使用 Slab 链表
满 Slab 链表

这里的对象即为内存块，在 Chcore 实现中用 slot 表示，下面会提到。实际的 SLab 分配器的设计可能用到 full_slab 链表也可能不会，具体根据其实现确定

查看本机 Slab 示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sudo cat /proc/slabinfo

kmalloc-4k           569    584   4096    8    8 : tunables    0    0    0 : slabdata     73     73      0
kmalloc-2k           752    752   2048   16    8 : tunables    0    0    0 : slabdata     47     47      0
kmalloc-1k           704    704   1024   32    8 : tunables    0    0    0 : slabdata     22     22      0
kmalloc-512         2112   2112    512   32    4 : tunables    0    0    0 : slabdata     66     66      0
kmalloc-256          768    768    256   32    2 : tunables    0    0    0 : slabdata     24     24      0
kmalloc-192         1050   1050    192   42    2 : tunables    0    0    0 : slabdata     25     25      0
kmalloc-128         1376   1376    128   32    1 : tunables    0    0    0 : slabdata     43     43      0
kmalloc-96          1134   1134     96   42    1 : tunables    0    0    0 : slabdata     27     27      0
kmalloc-64          3072   3072     64   64    1 : tunables    0    0    0 : slabdata     48     48      0
kmalloc-32          3072   3072     32  128    1 : tunables    0    0    0 : slabdata     24     24      0
kmalloc-16          6144   6144     16  256    1 : tunables    0    0    0 : slabdata     24     24      0
kmalloc-8          12288  12288      8  512    1 : tunables    0    0    0 : slabdata     24     24      0
NASM

Chcore 中 SLab 分配器的设计

同伙伴系统一样，这部分主要介绍 Chcore 中 SLab 分配器实现的核心数据结构和函数接口

核心数据结构

先上代码，看看有哪些数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * order range: [SLAB_MIN_ORDER, SLAB_MAX_ORDER]
 * ChCore prepares the slab for each order in the range.
 */
#define SLAB_MIN_ORDER (5)
#define SLAB_MAX_ORDER (11)

/* The size of one slab is 128K. */
#define SIZE_OF_ONE_SLAB (128*1024)

/* slab_header resides in the beginning of each slab (i.e., occupies the first slot). */
struct slab_header {
        /* The list of free slots, which can be converted to struct slab_slot_list. */
        void *free_list_head;
        /* Partial slab list. */
        struct list_head node;

        int order;
        unsigned short total_free_cnt; /* MAX: 65536 */
        unsigned short current_free_cnt;
};

/* Each free slot in one slab is regarded as slab_slot_list. */
struct slab_slot_list {
        void *next_free;
};

struct slab_pointer {
        struct slab_header *current_slab;
        struct list_head partial_slab_list;
};

/* slab_pool is also static. We do not add the static modifier due to unit test.
 */
struct slab_pointer slab_pool[SLAB_MAX_ORDER + 1];
static struct lock slabs_locks[SLAB_MAX_ORDER + 1];

C

Chcore 中的 SLab 分配器设定大体服从书上的安排，以内存池为单元，先看宏定义：

  • SLAB_MIN_ORDER & SLAB_MIN_ORDER ：表示 SLab 分配器可以操作的内存块大小，从 2^5 到 2^11 字节
  • SIZE_OF_ONE_SLAB ：表示每个 slab 的大小，在 Chcore 中是 128KB

接下来我们再分析其核心数据结构的实现：

slab_pointer

即 Chcore 中表示 slab 池的数据结构，这个也可以在下面对 slab_pool 的定义中看见。其数据成员即我们之前介绍的 current 和 partial 指针，在这里以 slab_header 和 list_head 的形式出现

slab_header

是 Chcore 中代表一个个具体的 slab 的对象，其成员包含：

  • void *free_list_head ：内部空闲 slot 的链表
  • struct list_head node ：partial 中表示自身的节点

如何由节点反过来得到其处于的 slab？

在 chcore 之中采用的是内存对齐+元数据的方式，具体而言，元数据为：

  • 在每一个 slab 块的开头，维护一个其中内存槽 slot 的 free list head
  • 在每一个内存槽 slot 之中，存一个 next_free 的指针
  • slab 由 buddy sys 分配，保证 slab header 地址按 page 对齐

这样，当我想要 free addr 时, 可以找到对应的 page, 进而找到 slab header, 进而得到 free_list，最后在 free_list 之中插入这个 slot, 然后由这个 slab 的空闲 slot 个数判断是否是 full → partial, partial→free, 从而进行插入 partial list 或者把 slab 空间归还给 buddy sys 的操作

  • int order ：该 slab 的阶数
  • total_free_cnt & current_free_cnt ：总的空闲块数 & 当前空闲块数

最后是 slot 自身

slab_slot_list

仅包含一个 void *next_free 指针，它们串起来得到每个 slab 内部的空闲块链表

核心函数接口

Chcore 的 SLab 分配器的实现包含了较多的辅助函数，这里只介绍重要的几个接口：

1
2
3
void init_slab(void);
void *alloc_in_slab(unsigned long, size_t *);
void free_in_slab(void *addr);
C

从上到下函数接口的功能依次为：

  • init_slab ：初始化 SLab 分配器
  • alloc_in_slab ：在 slab 中申请分配内存
  • free_in_slab ：释放相应的内存

Chcore 源码对 SLab 功能的具体实现

同伙伴系统一样，这部分解析 Chcore 源码对 SLab 功能函数的具体实现，主要内容即为上面部分提到的三个函数，其中又会涉及到其他辅助函数，根据重要程度串起来讲解

init_slab

源码

1
2
3
4
5
6
7
8
9
10
11
12
void init_slab(void)
{
        int order;

        /* slab obj size: 32, 64, 128, 256, 512, 1024, 2048 */
        for (order = SLAB_MIN_ORDER; order <= SLAB_MAX_ORDER; order++) {
                lock_init(&slabs_locks[order]);
                slab_pool[order].current_slab = NULL;
                init_list_head(&(slab_pool[order].partial_slab_list));
        }
        kdebug("mm: finish initing slab allocators\n");
}
C

解析

初始化函数和伙伴系统比起来简单了许多，直接用一个 for 循环去过一遍所有 slab 池即可：

  • 初始化 32~ 2048 字节为 slot 的各个 slab, 每一个 slab 为 SIZE_OF_ONE_SLAB=128K 大小
  • 初始化对应的锁
  • 对全局变量的 slab array 的 current_slab partial_slab_list 初始化

alloc_in_slab

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
void *alloc_in_slab(unsigned long size, size_t *real_size)
{
        int order;

        BUG_ON(size > order_to_size(SLAB_MAX_ORDER));

        order = (int)size_to_order(size);
        if (order < SLAB_MIN_ORDER)
                order = SLAB_MIN_ORDER;

#if ENABLE_MEMORY_USAGE_COLLECTING == ON
        if (real_size)
                *real_size = 1 << order;
#endif

        return alloc_in_slab_impl(order);
}

static void *alloc_in_slab_impl(int order)
{
        struct slab_header *current_slab;
        struct slab_slot_list *free_list;
        void *next_slot;

        lock(&slabs_locks[order]);

        current_slab = slab_pool[order].current_slab;
        /* When serving the first allocation request. */
        if (unlikely(current_slab == NULL)) {
                current_slab = init_slab_cache(order, SIZE_OF_ONE_SLAB);
                if (current_slab == NULL) {
                        unlock(&slabs_locks[order]);
                        return NULL;
                }
                slab_pool[order].current_slab = current_slab;
        }

        free_list = (struct slab_slot_list *)current_slab->free_list_head;
        BUG_ON(free_list == NULL);

        next_slot = free_list->next_free;
        current_slab->free_list_head = next_slot;

        current_slab->current_free_cnt -= 1;
        /* When current_slab is full, choose a new slab as the current one. */
        if (unlikely(current_slab->current_free_cnt == 0))
                choose_new_current_slab(&slab_pool[order], order);

        unlock(&slabs_locks[order]);

        return (void *)free_list;
}

static void choose_new_current_slab(struct slab_pointer *pool, int order)
{
        struct list_head *list;

        list = &(pool->partial_slab_list);
        if (list_empty(list)) {
                pool->current_slab = NULL;
        } else {
                struct slab_header *slab;

                slab = (struct slab_header *)list_entry(
                        list->next, struct slab_header, node);
                pool->current_slab = slab;
                list_del(list->next);
        }
}
C

解析

注意到源码将参数检查和核心实现分为了两部分，其中核心实现单独用了一个辅助函数，对外的接口则为 alloc_in_slab 本身

二者视作一起看，其核心逻辑如下：

  • 参数检查，确保 order 符合范围，太大则报错，太小则向上补到最小值
  • 加锁，确保并发安全性
  • 若 current 为空，则为首次分配，需要先 init 一下（注意这里是直接使用的内部接口，保持了外界的无感知，也简化了这里的代码逻辑）
  • 随后直接从 current 的 slab 的空闲链表中取出一块 slot 作为返回值，同时处理相应字段，如空闲块数量减一，修改 list_head 等
  • 若当前 slab 已满，则换新的 slab，通过 choose_new_current_slab 进行操作，方式依然是通过定义好的 list 操作宏直接操作相应的链表
  • 解锁，完成分配

逻辑图可以作如下参考，便于理解阅读：

为空
失败
成功
非空
是
否
alloc_in_slab
计算 order
alloc_in_slab_impl
获取锁
检查 current_slab
init_slab_cache
解锁返回 NULL
设置 current_slab
获取 free_list
更新 free_list_head
减少 free_cnt
是否已满?
choose_new_current_slab
解锁
返回分配的内存

free_in_slab

最后是 free 的操作，为 slab 拼上最后一块拼图

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void free_in_slab(void *addr)
{
        struct page *page;
        struct slab_header *slab;
        struct slab_slot_list *slot;
        int order;

        slot = (struct slab_slot_list *)addr;
        page = virt_to_page(addr);
        if (!page) {
                kdebug("invalid page in %s", __func__);
                return;
        }

        slab = page->slab;
        order = slab->order;
        lock(&slabs_locks[order]);

        try_insert_full_slab_to_partial(slab);

#if ENABLE_DETECTING_DOUBLE_FREE_IN_SLAB == ON
        /*
         * SLAB double free detection: check whether the slot to free is
         * already in the free list.
         */
        if (check_slot_is_free(slab, slot) == 1) {
                kinfo("SLAB: double free detected. Address is %p\n",
                      (unsigned long)slot);
                BUG_ON(1);
        }
#endif

        slot->next_free = slab->free_list_head;
        slab->free_list_head = slot;
        slab->current_free_cnt += 1;

        try_return_slab_to_buddy(slab, order);

        unlock(&slabs_locks[order]);
}
C

解析

整体上还是走的“获取信息——转到相应 object——根据情况分类讨论作对应操作”

梳理一下 free_in_slab 的实现逻辑：

  • 处理参数，通过地址转换拿到 slot、page、slab 等对象
  • 上锁
  • 检查现在的 slab 是否是 full 的，如果是，那么在 free 前还得把它放回 partial
  • 进行 free 操作，即把链表头插回来、设置 slab 空闲链表、以及空闲数加一
  • 检查现在的 slab 是否是空的，如果是，那么物归原主——还给 buddy 大人
  • 解锁，完成 free 全部操作

至此，SLab 分配器源码解析结束

ChCore > 内存管理 > 物理内存管理
#OS #ChCore #源码解析
SLab分配器
http://example.com/2025/02/13/SLab/
作者
思源南路世一劈
发布于
2025年2月13日
许可协议