Linux 内核 | 内存管理——Slab 分配器


简介

在Linux中,伙伴分配器(buddy allocator)是以页为单位管理和分配内存。但在内核中的需求却以字节为单位(在内核中面临频繁的结构体内存分配问题)。假如我们需要动态申请一个内核结构体(占 20 字节),若仍然分配一页内存,这将严重浪费内存。那么该如何分配呢?slab 分配器专为小内存分配而生,由Sun公司的一个雇员Jeff BonwickSolaris 2.4中设计并实现。slab分配器分配内存以字节为单位,基于伙伴分配器的大内存进一步细分成小内存分配。换句话说,slab 分配器仍然从 Buddy 分配器中申请内存,之后自己对申请来的内存细分管理。

除了提供小内存外,slab 分配器的第二个任务是维护常用对象的缓存。对于内核中使用的许多结构,初始化对象所需的时间可等于或超过为其分配空间的成本。当创建一个新的slab 时,许多对象将被打包到其中并使用构造函数(如果有)进行初始化。释放对象后,它会保持其初始化状态,这样可以快速分配对象。

举例来说, 为管理与进程关联的文件系统数据, 内核必须经常生成struct fs_struct的新实例. 此类型实例占据的内存块同样需要经常回收(在进程结束时). 换句话说, 内核趋向于非常有规律地分配并释放大小为sizeof(fs_struct)的内存块. slab分配器将释放的内存块保存在一个内部列表中. 并不马上返回给伙伴系统. 在请求为该类对象分配一个新实例时, 会使用最近释放的内存块。S这有两个优点. 首先, 由于内核不必使用伙伴系统算法, 处理时间会变短. 其次, 由于该内存块仍然是”新”的,因此其仍然驻留在CPU硬件缓存的概率较高.[3]

SLAB分配器的最后一项任务是提高CPU硬件缓存的利用率。 如果将对象包装到SLAB中后仍有剩余空间,则将剩余空间用于为SLAB着色。 SLAB着色是一种尝试使不同SLAB中的对象使用CPU硬件缓存中不同行的方案。 通过将对象放置在SLAB中的不同起始偏移处,对象可能会在CPU缓存中使用不同的行,从而有助于确保来自同一SLAB缓存的对象不太可能相互刷新。 通过这种方案,原本被浪费掉的空间可以实现一项新功能。

通过命令sudo cat /proc/slabinfo可查看系统当前 slab 使用情况。以vm_area_struct结构体为例,当前系统已分配了 13014 个vm_area_struct缓存,每个大小为 216 字节,其中 active 的有 12392 个。

[root@VM-8-9-centos]# cat /proc/slabinfo
slabinfo - version: 2.1
# name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <limit> <batchcount> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail>
...
vm_area_struct     12392  13014    216   18    1 : tunables    0    0    0 : slabdata    723    723      0
mm_struct            184    200   1600   20    8 : tunables    0    0    0 : slabdata     10     10      0
shared_policy_node   5015   5015     48   85    1 : tunables    0    0    0 : slabdata     59     59      0
numa_policy           15     15    264   15    1 : tunables    0    0    0 : slabdata      1      1      0
radix_tree_node    15392  17234    584   14    2 : tunables    0    0    0 : slabdata   1231   1231      0
idr_layer_cache      240    240   2112   15    8 : tunables    0    0    0 : slabdata     16     16      0
kmalloc-8192          39     44   8192    4    8 : tunables    0    0    0 : slabdata     11     11      0
kmalloc-4096         117    144   4096    8    8 : tunables    0    0    0 : slabdata     18     18      0
kmalloc-2048         458    528   2048   16    8 : tunables    0    0    0 : slabdata     33     33      0
kmalloc-1024        1399   1424   1024   16    4 : tunables    0    0    0 : slabdata     89     89      0
kmalloc-512          763    800    512   16    2 : tunables    0    0    0 : slabdata     50     50      0
kmalloc-256         3132   3376    256   16    1 : tunables    0    0    0 : slabdata    211    211      0
kmalloc-192         2300   2352    192   21    1 : tunables    0    0    0 : slabdata    112    112      0
kmalloc-128         1376   1376    128   32    1 : tunables    0    0    0 : slabdata     43     43      0
kmalloc-96          1596   1596     96   42    1 : tunables    0    0    0 : slabdata     38     38      0
kmalloc-64         16632  20800     64   64    1 : tunables    0    0    0 : slabdata    325    325      0
kmalloc-32          1664   1664     32  128    1 : tunables    0    0    0 : slabdata     13     13      0
kmalloc-16          4608   4608     16  256    1 : tunables    0    0    0 : slabdata     18     18      0
kmalloc-8           4096   4096      8  512    1 : tunables    0    0    0 : slabdata      8      8      0
...

可以看到,系统中存在的 slab 有些形如 kmalloc-xxx 的 slab,我们称其为通用型 slab,用来满足分配通用内存。其他含有具体名字的 slab 我们称其为 专用 slab,用来为特定结构体分配内存,如 vm_area_struct、mm_struct 等。

为什么要分专用和通用 slab ? 最直观的一个原因就是通用 slab 会造成内存浪费:出于 slab 管理的方便,每个 slab 管理的对象大小都是一致的,当我们需要分配一个处于 64-96字节中间大小的对象时,就必须从保存 96 字节的 slab 中分配。而对于专用的 slab,其管理的都是同一个结构体实例,申请一个就给一个恰好内存大小的对象,这就可以充分利用空间。

slab 分配器的实现源码(Linux kernel 5.10):

  • include/linux/slab_def.h
  • include/linux/slab.h
  • mm/slab.c

Slab API

与 libc 提供的内存申请 API (malloc 和 free )类似,Slab 分配器提供的 API 为 kmalloc()kfree()kmalloc()函数定义在include/linux/slab.h文件中,接收两个参数,并调用__kmalloc()函数。最终分配内存的实现是 __do_kmalloc()函数。

  • size:申请的内存大小
  • flags:参数使用 GFP_XXX来指定分配内存的具体内存域,例如 GFP_DMA 指定分配适合于DMA的内存区.
static __always_inline void *kmalloc(size_t size, gfp_t flags)
{
    ...
    return __kmalloc(size, flags);
}
// in mm/slab.c
void *__kmalloc(size_t size, gfp_t flags)
{
    return __do_kmalloc(size, flags, _RET_IP_);
}
static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,
                      unsigned long caller)
{
    ...
}

实现原理

由于slab的缓存特性,slab 分配器从 buddy 分配器中获取的物理内存称为 内存缓存(与 CPU 的硬件缓存进行区别,下文都称为缓存),使用结构体struct kmem_cache (定义在include/linux/slab_def.h文件中)描述。

struct kmem_cache {
/* 2) touched by every alloc & free from the backend */
    slab_flags_t flags;        /* constant flags */
    unsigned int num;        /* 每个 slab 中的 objs 数量 */
/* 3) cache_grow/shrink */
    /* 每个 slab 所使用的页框数量 order */
    unsigned int gfporder;
    /* force GFP flags, e.g. GFP_DMA */
    gfp_t allocflags;
    size_t colour;            /* cache colouring range */
    unsigned int colour_off;    /* colour offset */
    struct kmem_cache *freelist_cache;
    unsigned int freelist_size;
/* 4) cache creation/removal */
    const char *name;
    struct list_head list;
    int refcount;
    int object_size;
    int align;
    struct kmem_cache_node *node[MAX_NUMNODES];
};

SLAB分配器由可变数量的缓存组成,这些缓存由称为“缓存链”的双向循环链表链接在一起(如下图中的 kmem_cache 链表)。 在slab分配器的上下文中,缓存是特定类型的多个对象的管理器,例如使用cat /proc/slabinfo命令输出的mm_struct fs_cache缓存,其名字保存在kmem_cache->name中(Linux 支持单个最大的 slab 缓存大小为32MB )。kmem_cache 中所有对象的大小是相同的(object_size),并且此 kmem_cache 中所有SLAB的大小也是相同的(gfpordernum)。

每个缓存节点在内存中维护称为slab的连续页块,这些页面被切成小块,用于缓存数据结构和对象。 kmem_cachekmem_cache_node 成员记录了该kmem_cache 下的所有 slabs 列表。形成的结构如下图所示。

kmem_cache_node 定义在mm/slab.h文件中,如下所示


struct kmem_cache_node {
    spinlock_t list_lock;

#ifdef CONFIG_SLAB
    struct list_head slabs_partial;    /* partial list first, better asm code */
    struct list_head slabs_full;
    struct list_head slabs_free;
    unsigned long total_slabs;    /* 所有 slab list 的长度 */
    unsigned long free_slabs;    /* 仅 free slab list 的长度*/
    unsigned long free_objects;
    ...
#endif

};

kmem_cache_noed 记录了3种slab:

  • slabs_full :已经完全分配的 slab
  • slabs_partial: 部分分配的slab
  • slabs_free:空slab,或者没有对象被分配

以上3个链表保存的是slab 描述符,Linux kernel 使用 struct page 来描述一个slab。单个slab可以在slab链表之间移动,例如如果一个半满slab被分配了对象后变满了,就要从 slabs_partial 中被删除,同时插入到 slabs_full 中去。

为了进一步解释,这里举个例子来说明(此处基于[2]所用的例子进行了一些修改)。用 struct kmem_cache 结构描述的一段内存就称作一个 slab 缓存池。一个slab缓存池就像是一箱牛奶,一箱牛奶中有很多瓶牛奶,每瓶牛奶就是一个 slab 。在初始时,所有牛奶都是新的,都存在 slabs_free 链表中。分配内存的时候,就相当于从牛奶箱中拿一瓶牛奶,若把一瓶牛奶喝完,该牛奶就会被加入到 slabs_full 中不能再分配;若只喝了一半就放回到 slabs_partial 中。牛奶可能会喝完(不考虑 slab 内存 free 的情况,因为自己不能生产牛奶(捂脸)),当箱子空的时候,你就需要去超市再买一箱回来。超市就相当于buddy 分配器。

[注意]上述例子有点不严谨,实际上操作系统启动创建kmem_cache完成后,这三个链表都为空,只有在申请对象时发现没有可用的 slab 时才会创建一个新的SLAB,并加入到这三个链表中的一个中。也就是说kmem_cache中的SLAB数量是动态变化的,当SLAB数量太多时,kmem_cache会将一些SLAB释放回页框分配器中。

继续来看 page 结构体关于 slab 的部分。struct page定义在include/linux/mm_types.h文件中,与slab相关的结构体成员如下所示:

struct page {
    union {
        struct {    /* Page cache and anonymous pages */
            ...
        };

        struct {    /* slab, slob and slub */
            union {
                struct list_head slab_list;
                struct {    /* Partial pages */
                    struct page *next;

                    int pages;    /* Nr of pages left */
                    int pobjects;    /* Approximate count */
                };
            };
            struct kmem_cache *slab_cache;
            /* Double-word boundary */
            void *freelist;        /* first free object */
            union {
                void *s_mem;    /* slab: first object */
                unsigned long counters;        /* SLUB */
                ...
            };
        };
        ...
    };
};
  • void *s_mem: 指向该页框中第一个object 的地址 。
  • struct kmem_cache *slab_cache: struct kmem_cache_node结构体用其追踪所有 page 的链表。
  • struct list_head slab_list: 用于跟踪此页框属于哪个slab链表(full, free, partial),即使用此成员将list串联起来。
  • void *freelist: 用于指向页框中空闲对象链表。空闲对象链表包含页框中每个空闲对象的索引。
空闲对象链表是一个由数组制成的简单链表,它保存的地方有两种情况[6]:
1.保存在外部,会从SLAB中分配一个对象用于保存新的SLAB的空闲对象链表。
2.保存在内部,保存在这个SLAB所代表的连续页框的头部。

在空闲对象链表都是保存在内部(通常也是保存在内部)的情况下,slab 描述符描述一块连续的内存关键结构如下:

借助 freelist 以及 struct page 中的 active成员可以实现优先分配刚释放的内存。内存分配的过程如下图所示(图片引自此链接)。

Slab缓存建立过程

第一个 kmem_cache 结构体实例是定义的全局变量kmem_cache_bootmm/slab.c)。

static struct kmem_cache kmem_cache_boot = {
    .batchcount = 1,
    .limit = BOOT_CPUCACHE_ENTRIES,
    .shared = 1,
    .size = sizeof(struct kmem_cache),
    .name = "kmem_cache",
};

kmem_cache_init()函数在初始化过程中调用create_boot_cache()kmem_cache_boot进行了进一步初始化。第一个kmem cache实例用于为创建其他kmem cache实例分配空间,其大小与系统内的 node 有关。offsetof求出 kmem_cache 结构体中 node的偏移地址,再加上系统内 node 的个数乘以sizeof(struct kmem_cache_node *),这真是把内存省到极致。因kmem_cache 的成员 node 是用最大的node数定义的数组大小,这里最后只使用系统内实际的node数量来申请内存。

void __init kmem_cache_init(void)
{
    int i;

    kmem_cache = &kmem_cache_boot;

    // NUM_INIT_LISTS 为 2 * 系统内的节点数量
    // 初始化 kmem_cache_node 结构体
    for (i = 0; i < NUM_INIT_LISTS; i++)
        kmem_cache_node_init(&init_kmem_cache_node[i]);
    // 完成第一个kmem cache实例kmem_cache的初始化
    // 第一个kmem cache实例用于为创建其他kmem cache实例分配空间
    create_boot_cache(kmem_cache, "kmem_cache",
        offsetof(struct kmem_cache, node) +
                  nr_node_ids * sizeof(struct kmem_cache_node *),
                  SLAB_HWCACHE_ALIGN, 0, 0);
    // kmem cache实例加入slab_caches链表
    list_add(&kmem_cache->list, &slab_caches);
    slab_state = PARTIAL;

    kmalloc_caches[KMALLOC_NORMAL][INDEX_NODE] = create_kmalloc_cache(
                kmalloc_info[INDEX_NODE].name[KMALLOC_NORMAL],
                kmalloc_info[INDEX_NODE].size,
                ARCH_KMALLOC_FLAGS, 0,
                kmalloc_info[INDEX_NODE].size);
    slab_state = PARTIAL_NODE;
    setup_kmalloc_cache_index_table();

    slab_early_init = 0;

    /* 5) Replace the bootstrap kmem_cache_node */
    {
        int nid;

        for_each_online_node(nid) {
            init_list(kmem_cache, &init_kmem_cache_node[CACHE_CACHE + nid], nid);

            init_list(kmalloc_caches[KMALLOC_NORMAL][INDEX_NODE],
                      &init_kmem_cache_node[SIZE_NODE + nid], nid);
        }
    }

    create_kmalloc_caches(ARCH_KMALLOC_FLAGS);
}

slab_cache 作为链接所有 kmem_cache 的链表头,使用宏LIST_HEAD(slab_caches)定义在文件mm/slab_common.c中;在 kmem_cache 初始化后,都将通过 list_add 将其添加到链表中。

接下来 kmalloc_caches 是 struct kmem_cache *的一个二维数组指针(定义在mm/slab_common.c),其使用 kmalloc_info 中保存的信息生成不同 size 的 kmem_cache。kmalloc_info 的定义如下:类似一个 map,例如其中一个元素是{“kmalloc-96”,96},“kmalloc-96”为 kmem_cache 的 name,96 为 object 的大小。此处调用 create_kmalloc_cache是创建一个 记录kmem_cache_node的 kmem_cache(对 INDEX_NODE 展开为 INDEX_NODE kmalloc_index(sizeof(struct kmem_cache_node))

#define INIT_KMALLOC_INFO(__size, __short_size)            \
{                                \
    .name[KMALLOC_NORMAL]  = "kmalloc-" #__short_size,    \
    .name[KMALLOC_RECLAIM] = "kmalloc-rcl-" #__short_size,    \
    .size = __size,                        \
}
#endif

const struct kmalloc_info_struct kmalloc_info[] __initconst = {
    INIT_KMALLOC_INFO(0, 0),
    INIT_KMALLOC_INFO(96, 96),
    INIT_KMALLOC_INFO(192, 192),
    INIT_KMALLOC_INFO(8, 8),
    ...
    INIT_KMALLOC_INFO(67108864, 64M)
};

create_kmalloc_cache()函数首先调用函数 kmem_cache_zalloc(kmem_cache, GFP_NOWAIT);从 kmem_cache 中申请一个 slab 用来保存记录 struct kmem_cache_node实例的 kmem_cache。之后再调用create_boot_cache()函数对从 kmem_cacha slab 中申请来的 kmem_cache 进行初始化,并再添加到 slab_caches 链表中。

struct kmem_cache *__init create_kmalloc_cache(const char *name,
        unsigned int size, slab_flags_t flags,
        unsigned int useroffset, unsigned int usersize)
{
    struct kmem_cache *s = kmem_cache_zalloc(kmem_cache, GFP_NOWAIT);
    ...
    create_boot_cache(s, name, size, flags, useroffset, usersize);
    list_add(&s->list, &slab_caches);
    s->refcount = 1;
    return s;
}

此时 kmem_cache 形成的结构如下图。这部分可能有些绕,为了便于区分,此处额外添加了一个名为 vm_area_struct 的 kmem_cache。

[问题] 图中有一点不严谨的地方。按照代码逻辑来看,记录 kmem_cache_node的 kmem_cache 的 name 并不为 “kmem_cache_node”,而是 "kmalloc-sizeof(struct kmem_cache_node)",为什么这里不使用专用的 slab 来为 kmem_cache_node 来分配内存呢? 按道理有多少 kmem_cache 实例就需要多少 kmem_cache_node 实例,为什么 kmem_cache 有专用的 slab,而 kmem_cache_node 没有? 百思不得其解,望大佬赐教,万分感激!

专用的 slab 的初始化分布在不同子系统所在的源文件中。以 vm_area_struct 为例,其初始化在__init proc_caches_init(void) 函数(定义在文件kernel/fork.c中)中被调用,代码如下所示。

void __init proc_caches_init(void)
{
    unsigned int mm_size;

    sighand_cachep = kmem_cache_create("sighand_cache",
            sizeof(struct sighand_struct), 0,
            SLAB_HWCACHE_ALIGN|SLAB_PANIC|SLAB_TYPESAFE_BY_RCU|
            SLAB_ACCOUNT, sighand_ctor);
    signal_cachep = kmem_cache_create("signal_cache",
            sizeof(struct signal_struct), 0,
            SLAB_HWCACHE_ALIGN|SLAB_PANIC|SLAB_ACCOUNT,
            NULL);
    files_cachep = kmem_cache_create("files_cache",
            sizeof(struct files_struct), 0,
            SLAB_HWCACHE_ALIGN|SLAB_PANIC|SLAB_ACCOUNT,
            NULL);
    fs_cachep = kmem_cache_create("fs_cache",
            sizeof(struct fs_struct), 0,
            SLAB_HWCACHE_ALIGN|SLAB_PANIC|SLAB_ACCOUNT,
            NULL);
    ...
    vm_area_cachep = KMEM_CACHE(vm_area_struct, SLAB_PANIC|SLAB_ACCOUNT);

}

其他通用的 kmem_cache(name 为 kmalloc-xxx)的初始化在函数new_kmalloc_cache()(定义在mm/slab_common.c文件中)中调用,如下。

static void __init
new_kmalloc_cache(int idx, enum kmalloc_cache_type type, slab_flags_t flags)
{
    if (type == KMALLOC_RECLAIM)
        flags |= SLAB_RECLAIM_ACCOUNT;

    kmalloc_caches[type][idx] = create_kmalloc_cache(
                    kmalloc_info[idx].name[type],
                    kmalloc_info[idx].size, flags, 0,
                    kmalloc_info[idx].size);
}

Slab缓存分配过程

根据以上的分析可推断,kmem_cache_zalloc()函数实现了从 slab 中分配内存的功能。其调用流程如下

kmem_cache_zalloc(include/linux/slab.h)
    kmem_cache_alloc(mm/slab.c)
        slab_alloc(mm/slab.c)
            __do_cache_alloc(mm/slab.c)
                ____cache_alloc(mm/slab.c)
                    cpu_cache_get(mm/slab.c)
                    cache_alloc_refill(mm/slab.c)

____cache_alloc()函数实现如下,slab 分配器首先会从 array_cache中查找是否存在可用 obj (下面会详细介绍 struct array_cache),若有直接分配,若无则调用 cache_alloc_refill()函数尝试从 3 个 slabs_(free/partial/full)中寻找可用的内存,并将其填充到 array_cache 中,再次进行分配。

static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
{
    void *objp;
    struct array_cache *ac;
    ...
    ac = cpu_cache_get(cachep);
    if (likely(ac->avail)) {
        ac->touched = 1;
        objp = ac->entry[--ac->avail];

        STATS_INC_ALLOCHIT(cachep);
        goto out;
    }

    STATS_INC_ALLOCMISS(cachep);
    objp = cache_alloc_refill(cachep, flags);

    ac = cpu_cache_get(cachep);

out:
    if (objp)
        kmemleak_erase(&ac->entry[ac->avail]);
    return objp;
}

struct array_cache 本地 CPU 空闲对象链表

在 kmem_cache 结构体中还有一个成员struct array_cache __percpu *cpu_cache;。其用来为每个CPU维护一个空间对象链表(Per CPU 相关内容参考此链接)。这能带来如下好处:

  • 提高硬件缓存的命中率。每个CPU都有它们自己的硬件高速缓存(在多核CPU下,通常 L1/L2 为 CPU 单独占有,L2/L3为所有CPU核共享的)。当此CPU上释放对象时,又再次申请一个相同大小的对象时,原对象很可能还在这个CPU的硬件高速缓存中。内核为每个CPU维护一个这样的链表,当需要新的对象时,会优先尝试从当前CPU的本地CPU空闲对象链表获取相应大小的对象,这样就能更快地分配对象。
  • 减少锁的竞争。假设多个CPU同时申请一个大小的slab,这时候如果没有本地CPU空闲对象链表,就会导致分配流程是互斥的,需要上锁,就导致分配效率低。
    struct array_cache定义在文件mm/slab.c文件中,如下所示:

    struct array_cache {
      unsigned int avail;
      unsigned int limit;
      unsigned int batchcount;
      unsigned int touched;
      void *entry[];
    };
  • avail: 表示当前可用对象的数量
  • limit:可拥有的最大对象数
  • batchcount:要从 slab_list 转移进本地高速缓存对象的数量,或从本地高速缓存中转移出去的 obj 数量
  • touched: 是否在收缩后访问过
  • entry: 伪数组,保存释放的对象指针

本地CPU空闲对象链表在系统初始化完成后是一个空的链表,只有释放对象时才会将对象加入这个链表。链表对象个数是有限制的(最大值就是limit),链表数超过这个值时,会将 batchcount 个数的对象返回到所有CPU共享的空闲对象链表(也是这样一个结构)中。

所有 CPU 共享的空闲对象链表

struct kmem_cache_node结构体中同样存在一个 array_cache的成员 struct array_cache shared;*,其构成一个所有 CPU 共享的缓存。

在此基础上,一个常规的对象申请流程是这样的:

  • 内核首先会从本地 CPU 空闲对象链表中尝试获取一个对象用于分配:如果失败,则检查所有CPU共享的空闲对象链表链表中是否存在,并且空闲链表中是否存在空闲对象,若有就转移 batchcount 个空闲对象到本地 CPU空闲对象链表中;
  • 如果第 1 步失败,就尝试从 SLAB中分配;这时如果还失败,kmem_cache会尝试从页框分配器中获取一组连续的页框建立一个新的SLAB,然后从新的SLAB中获取一个对象。

对象释放流程如下[6]:

  • 首先会先将对象释放到本地CPU空闲对象链表中,如果本地CPU空闲对象链表中对象过多,kmem_cache 会将本地CPU空闲对象链表中的batchcount个对象移动到所有CPU共享的空闲对象链表链表中,
  • 如果所有CPU共享的空闲对象链表链表的对象也太多了,kmem_cache也会把所有CPU共享的空闲对象链表链表中 batchcount 个数的对象移回它们自己所属的SLAB中,
  • 这时如果SLAB中空闲对象太多,kmem_cache会整理出一些空闲的SLAB,将这些SLAB所占用的页框释放回页框分配器中。

array_cache 填充

在了解上述空闲对象分配的过程后,我们参考代码来进一步理解,cache_alloc_refill()函数实现如下:

static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)
{
    int batchcount;
    struct kmem_cache_node *n;
    struct array_cache *ac, *shared;
    int node;
    void *list = NULL;
    struct page *page;

    
    ac = cpu_cache_get(cachep);
    batchcount = ac->batchcount;
    if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
        batchcount = BATCHREFILL_LIMIT;
    }
    n = get_node(cachep, node);

    BUG_ON(ac->avail > 0 || !n);
    shared = READ_ONCE(n->shared);
    if (!n->free_objects && (!shared || !shared->avail))
        goto direct_grow;  // 没有空闲对象,并且 没有共享空闲对象 可分配

    spin_lock(&n->list_lock);
    shared = READ_ONCE(n->shared);

    /* See if we can refill from the shared array */
    if (shared && transfer_objects(ac, shared, batchcount)) {
        shared->touched = 1;
        goto alloc_done;
    }

    while (batchcount > 0) {
        /* Get slab alloc is to come from. */
        page = get_first_slab(n, false);
        if (!page)
            goto must_grow;

        check_spinlock_acquired(cachep);

        batchcount = alloc_block(cachep, ac, page, batchcount);
        fixup_slab_list(cachep, n, page, &list);
    }

must_grow:
    n->free_objects -= ac->avail;
alloc_done:
    spin_unlock(&n->list_lock);
    fixup_objfreelist_debug(cachep, &list);

direct_grow:
    if (unlikely(!ac->avail)) {
        /* Check if we can use obj in pfmemalloc slab */
        if (sk_memalloc_socks()) {
            void *obj = cache_alloc_pfmemalloc(cachep, n, flags);

            if (obj)
                return obj;
        }

        page = cache_grow_begin(cachep, gfp_exact_node(flags), node);

        ac = cpu_cache_get(cachep);
        if (!ac->avail && page)
            alloc_block(cachep, ac, page, batchcount);
        cache_grow_end(cachep, page);

        if (!ac->avail)
            return NULL;
    }
    ac->touched = 1;

    return ac->entry[--ac->avail];
}
  • transfer_objects():从全局共享空闲对象中转移空闲对象到本地 CPU 空闲对象链表上
  • get_first_slab() : 从 slab 中获取空闲 slab
  • alloc_block() : 从空闲 slab 中获取 空闲对象,转移到 本地 CPU 空闲对象链表上
  • cache_grow_begin():当 slab 中都没有空闲对象时,开始从 buddy 系统中获取内存

上面描述的对象申请的过程与cache_alloc_refill()函数实现的功能基本是一致的。

继续 kmalloc API

了解 slab 基本原理后,我们再回头看当 kmalloc API 的处理流程。我比较关心的是 kmalloc 并没有传入 name,slab系统怎么知道选择哪个 kmem_cache?还是每个_ kmem_cache_ 实例的大小都会不一样? 因为专用的 slab 通过 kmem_cache_alloc()函数进行内存申请。例如,在kernel/fork.c文件中,vm_area_alloc()函数的功能是申请一个 vm_area_struct结构体实例,通过vma = kmem_cache_alloc(vm_area_cachep, GFP_KERNEL);来完成该过程。

而 kmalloc() 只是适用于分配通用的 slab。之前已经提到 kmalloc 会调用到 __do_kmalloc()函数,其实现如下:

static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,
                      unsigned long caller)
{
    struct kmem_cache *cachep;
    void *ret;

    if (unlikely(size > KMALLOC_MAX_CACHE_SIZE))
        return NULL;
    cachep = kmalloc_slab(size, flags);
    if (unlikely(ZERO_OR_NULL_PTR(cachep)))
        return cachep;
    ret = slab_alloc(cachep, flags, caller);

    ret = kasan_kmalloc(cachep, ret, size, flags);
    trace_kmalloc(caller, ret,
              size, cachep->size, flags);

    return ret;
}

kmalloc_slab()根据申请的 size 获取到对应的 kmem_cache。继续深入,kmalloc_slab()函数实现如下。

struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags)
{
    unsigned int index;

    if (size <= 192) {
        if (!size)
            return ZERO_SIZE_PTR;

        index = size_index[size_index_elem(size)];
    } else {
        if (WARN_ON_ONCE(size > KMALLOC_MAX_CACHE_SIZE))
            return NULL;
        index = fls(size - 1);
    }

    return kmalloc_caches[kmalloc_type(flags)][index];
}

首先计算出在对应的 index,用于索引之前介绍的全局二维数组 _kmalloc_caches_。 流程如下:

首先,对于size 小于 192B的申请,则从 size_index 中查找索引。size_index_elem()函数和 size_index 数组的定义如下,为了方便比对,这里再次给出 kmalloc_info 数组的前 7 个元素。通过分析可以发现,在分配小于 192 的 obj 时,会向上对齐,例如,9~16 字节的 obj 保存到 16 字节的kmem_cache中,65-96字节的 obj 保存到 96字节的 mem_cache中。

static u8 size_index[24] __ro_after_init = {
    3,    /* 8 */     4,    /* 16 */    5,    /* 24 */    5,    /* 32 */    6,    /* 40 */    
    6,    /* 48 */    6,    /* 56 */    6,    /* 64 */    1,    /* 72 */    1,    /* 80 */    
    1,    /* 88 */    1,    /* 96 */    7,    /* 104 */    7,    /* 112 */   7,    /* 120 */    
    7,    /* 128 */    2,    /* 136 */    2,    /* 144 */    2,    /* 152 */    2,    /* 160 */    
    2,    /* 168 */    2,    /* 176 */    2,    /* 184 */   2    /* 192 */
};
static inline unsigned int size_index_elem(unsigned int bytes)
{
    return (bytes - 1) / 8;
}

const struct kmalloc_info_struct kmalloc_info[] __initconst = {
    INIT_KMALLOC_INFO(0, 0),
    INIT_KMALLOC_INFO(96, 96),
    INIT_KMALLOC_INFO(192, 192),
    INIT_KMALLOC_INFO(8, 8),
    INIT_KMALLOC_INFO(16, 16),
    INIT_KMALLOC_INFO(32, 32),
    INIT_KMALLOC_INFO(64, 64),
    INIT_KMALLOC_INFO(128, 128),
    ...
}

对于高于 192 字节的 obj 分配,则调用fls()函数,其作用是得出 最高有效位(二进制下,最低向高位,最后一个 1的位置)。例如 fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32。此处不进一步分析。

kfree

接下来简单分析一下释放通用型 slab 对象时 如何根据一个指针找到待释放的对象,并对其进行释放操作的过程。kfree()函数如下,根据一个指针找到待释放的对象由函数virt_to_cache()函数实现。

void kfree(const void *objp)
{
    struct kmem_cache *c;
    unsigned long flags;

    trace_kfree(_RET_IP_, objp);

    if (unlikely(ZERO_OR_NULL_PTR(objp)))
        return;
    local_irq_save(flags);
    kfree_debugcheck(objp);
    c = virt_to_cache(objp);
    if (!c) {
        local_irq_restore(flags);
        return;
    }
    debug_check_no_locks_freed(objp, c->object_size);

    debug_check_no_obj_freed(objp, c->object_size);
    __cache_free(c, (void *)objp, _RET_IP_);
    local_irq_restore(flags);
}

virt_to_cache()函数定义在mm/slab.h文件中,调用 virt_to_head_page()函数获得该虚拟地址对应的 page 描述符,然后由 page->slab_cache 反向获取到对应的 kmem_cache。

static inline struct kmem_cache *virt_to_cache(const void *obj)
{
    struct page *page;

    page = virt_to_head_page(obj);
    if (WARN_ONCE(!PageSlab(page), "%s: Object is not a Slab page!\n",
                    __func__))
        return NULL;
    return page->slab_cache;
}

虚拟地址到 page 描述符的相关实现如下(include/linux/mm.h)。

static inline struct page *virt_to_head_page(const void *x)
{
    struct page *page = virt_to_page(x);

    return compound_head(page);
}

// arch/arm64/include/asm/memory.h
#define virt_to_page(x)        pfn_to_page(virt_to_pfn(x))
#define virt_to_pfn(x)        __phys_to_pfn(__virt_to_phys((unsigned long)(x)))
#define __virt_to_phys(x)    __virt_to_phys_nodebug(x)

// __is_lm_address 检查是否为线性映射(linear map)
// 0xffff_8000_0000_0000 - 0xffff_8008_0000_0000:线性映射区域映射内存
// 0xffff_8000_0000_0000向下的 kernel space virtual addr 是给  kernel image 使用的[8]
// 这对应 __lm_to_phys 和 __kimg_to_phys 两个宏。
#define __virt_to_phys_nodebug(x) ({                    \
    phys_addr_t __x = (phys_addr_t)(__tag_reset(x));        \
    __is_lm_address(__x) ? __lm_to_phys(__x) : __kimg_to_phys(__x);    \
})

#define __is_lm_address(addr)    (((u64)(addr) ^ PAGE_OFFSET) < (PAGE_END - PAGE_OFFSET))

#define __lm_to_phys(addr)    (((addr) & ~PAGE_OFFSET) + PHYS_OFFSET)
#define __kimg_to_phys(addr)    ((addr) - kimage_voffset)

虚拟地址与物理地址转换的过程这里不详细介绍,之后会专门用一篇文章来梳理。

继续回到kfree()函数,virt_to_cache()函数获取到了虚拟地址所对应的 kmem_cache,接下来调用__cache_free()函数来释放内存。

static __always_inline void __cache_free(struct kmem_cache *cachep, void *objp,
                     unsigned long caller)
{
    ...
    ___cache_free(cachep, objp, caller);
}

void ___cache_free(struct kmem_cache *cachep, void *objp,
        unsigned long caller)
{
    struct array_cache *ac = cpu_cache_get(cachep);

    check_irq_off();
    if (unlikely(slab_want_init_on_free(cachep)))
        // 释放时初始化对象
        memset(objp, 0, cachep->object_size);
    ...
    if (nr_online_nodes > 1 && cache_free_alien(cachep, objp))
        return;

    if (ac->avail < ac->limit) {
        STATS_INC_FREEHIT(cachep);
    } else {
        STATS_INC_FREEMISS(cachep);
        cache_flusharray(cachep, ac);
    }

    if (sk_memalloc_socks()) {
        struct page *page = virt_to_head_page(objp);

        if (unlikely(PageSlabPfmemalloc(page))) {
            cache_free_pfmemalloc(cachep, page, objp);
            return;
        }
    }

    __free_one(ac, objp);
}

以上代码实现与我们之前分析的对象回收过程是一致的

  • 本地 CPU 缓存数量未超过 limit 则直接回收到本地 CPU 空闲缓存中,调用 __free_one()函数
  • 若超过则调用cache_flusharray()向全局 CPU 共享空闲缓存中移动

cache_flusharray()函数首先判断是否存在全局共享缓存,若存在并且全局共享缓存空闲对象未超过限制,则向全局缓存中移动

若不满足上述条件则调用free_block()函数向 slab 中释放空闲对象。同时根据释放情况,调整对应的slab 到 slabs_free 或 slabs_partial 链表中。

static void cache_flusharray(struct kmem_cache *cachep, struct array_cache *ac)
{
    ...
    if (n->shared) {
        struct array_cache *shared_array = n->shared;
        int max = shared_array->limit - shared_array->avail;
        if (max) {
            if (batchcount > max)
                batchcount = max;
            memcpy(&(shared_array->entry[shared_array->avail]),
                   ac->entry, sizeof(void *) * batchcount);
            shared_array->avail += batchcount;
            goto free_done;
        }
    }

    free_block(cachep, ac->entry, batchcount, node, &list);
    ...
}

参考资料

[1]. Linux kernel 5.10.20 源码
[2]. Linux内核内存管理算法Buddy和Slab
[3]. slab分配器--Linux内存管理 (二十二)
[4]. The Slab Allocator in the Linux kernel
[5]. kernel doc # Chapter 8  Slab Allocator
[6]. linux内存源码分析 - SLAB分配器概述
[7]. 优雅的slab内存分配器(二)——slab初始化kmem_cache_init
[8]. linux kernel中的virt_to_phys代码解读

声明:一丁点儿的网络日志|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - Linux 内核 | 内存管理——Slab 分配器


勿在浮沙筑高台,每天进步一丁点儿!