slab分配器

产生背景

在Linux中,伙伴分配器(buddy allocator)是以页为单位管理和分配内存.但在内核中的需求却以字节为单位(在内核中面临频繁的结构体内存分配问题, 例如 struct inodem struct task_struct).假如我们需要动态申请一个内核结构体(占 20 字节),若仍然分配一页内存,这将严重浪费内存

既然 buddy system 采用的 4KB 太大, 那我们能不能考虑以更小的尺寸(比如64/128/256B)去组织,形成一个二级分配系统呢? 假设一个object的大小是96字节,如果使用这样的二级分配器,申请时将从128字节的free list开始查找,没有则继续寻找更高order的free list. 这个思路有两个比较明显的缺点

  1. 这将在每个被使用到的128字节内存块中留下32字节难以使用的"碎片",造成内存资源的浪费.
  1. 一个object在释放后将归还到128字节的free list上,根据buddy的规则,可能被合并为更高order的内存块,如果这个object马上又要使用,则需要再次从free list上分配

除此之外, 对于频繁的分配/回收的内存段, 我们期望可以缓存和复用相同的objects,加快分配和释放的速度.

历史与简介

slab 分配器专为小内存分配而生, 基于伙伴分配器的大内存进一步细分成小内存分配.换句话说,slab 分配器仍然从 Buddy 分配器中申请内存,之后自己对申请来的内存细分管理.

slab 由Sun公司的一个雇员Jeff Bonwick在Solaris 2.4中设计并实现, 由于他公开了其方法,因而后来被Linux所借鉴,用于实现内核中更小粒度的内存分配.

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

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

slab 有很多相关的概念和内容比较容易搞混, 这里做一下区分

  1. 本文讨论是 slab allocator, 这是一个用于紧密管理小内存分配器的概念. slab allocator 有三个主流的实现 SLOB SLAB SLUB
    • SLOB 是最早出现的, 非常紧凑但不够高效/性能不好, 现在只能在嵌入式系统中看到;
    • SLAB 是 Solaris 的实现, 高缓存效率但是比较浪费内存, 并且它不断地在做一些检查和计算以确保缓存的有效性, 对于拥有大量核心的超级计算机上会浪费大量的 CPU 周期去跟踪计算内存;
    • SLUB 是当前 Linux 默认采用的分配器实现
  1. SLAB/SLUB 的内部实现中也有叫做 slab 的字段, 需要注意区分

    目前 SLAB 已经被弃用 Linux 的 SLAB 分配器已正式弃用?的回答

下文中 slab allocator 指 slab 分配器, SLUB 指 SLUB 算法(一种 slab allocator 的实现), slab 指 SLUB 中的字段

linux内核内存分配界的葵花宝典,耐心看完,功力大增,slub内存分配器: 20:13 起

下文讨论 SLAB 以及当前 Linux 使用的 slab allocator: SLUB, slab allocator 主要解决了如下的几个核心问题

  1. 解决buddy按照页的颗粒度分配小内存的碎片问题
  1. 缓存部分常用的数据结构(包括但不限于inode、dir_entry、task_struct等),减少操作系统分配、回收对象时调整内存的时间开销
  1. 通过着色更好地利用cpu硬件的高速缓存cache,允许不同缓存中的对象占用相同的缓存行,从而提高缓存的利用率并获得更好的性能

SLAB & SLUB

在slab分配器中,每一类objects拥有一个"cache"(比如inode_cache, dentry_cache, 具有相同的 sizeof).之所以叫做"cache",是因为每分配一个object,都从包含若干空闲的同类objects的区域获取,释放时也直接回到这个区域,这样可以缓存和复用相同的objects,加快分配和释放的速度

object从"cache"获取内存,"cache"的内存从buddy分配器来. 也就是说slab allocator层直接面向程序的分配需求,相当于是前端,而buddy系统则成为slab allocator的后端, 如下图所示

20230823172155

其中 kmem_cache 即上文提到的 "cache" , 是一个定义在 include/linux/slub_def.h 的结构体 kmem_cache. 这个结构体字段很多, 但我们比较关系的是两个字段 cpu_slab 以及 node

struct kmem_cache {
    struct kmem_cache_cpu *cpu_slab;
    const char *name;   /* Name (only for display!) */
    struct kmem_cache_node *node[MAX_NUMNODES];
};

struct kmem_cache_cpu {
    /*指向下面page指向的slab中的第一个free object*/
     void **freelist;
    /* Globally unique transaction id */
     unsigned long tid;
    /*指向当前正在使用的slab*/
     struct page *page;
    /*本地slab缓存池中的partial slab链表*/
     struct page *partial;
};

struct kmem_cache_node {
#ifdef CONFIG_SLAB
    /*kmem_cache_node数据结构的自旋锁,可能涉及到多核访问*/
    raw_spinlock_t list_lock;
    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;  /* length of all slab lists */
    unsigned long free_slabs;   /* length of free slab list only */
    unsigned long free_objects;
    unsigned int free_limit;
    unsigned int colour_next;   /* Per-node cache coloring */
    struct array_cache *shared; /* shared per node */
    struct alien_cache **alien; /* on other nodes */
    unsigned long next_reap;    /* updated without locking */
    int free_touched;       /* updated without locking */
#endif

#ifdef CONFIG_SLUB
    /*kmem_cache_node数据结构的自旋锁,可能涉及到多核访问*/
    spinlock_t list_lock;
    /*node中slab的数量*/
    unsigned long nr_partial;
    struct list_head partial;
#endif
};

SLAB 和 SLUB 的差别就在于 CONFIG_SLAB 与 CONFIG_SLUB 的选择, 对应结构体 kmem_cache_node 中 SLAB 具有 slabs_free(全空), slabs_partial(部分空), slabs_full(全满), 但是 SLUB 只有 partial(部分空).

SLUB内存分配器是在SLAB的基础上进行了改进和简化.SLUB设计的目标是进一步减少内存分配和回收的开销,因此它仅使用了一个链表_即partial链表,而去除了SLAB中的slab_full链表.

下图是 kmem_cache 结构体展开的设计架构图, 下面具体介绍一下每一部分的内容.

20230823173224

分配与回收

下面的介绍为 SLAB 分配算法, 所以有 partial 和 full, SLUB 就是把 slabs_full 去掉的简化

其中 cpu_slab 为当前 CPU 正在使用的 slab, 该 slab 包含一个 void **freelist, 等分为了一个个小的 object. 用于当前内存地址的分配/回收

20230823174724

后续内存块更新之后, 需要维护 cpu_slab 中的 free_list 指针, 以便可以迅速找到第一个可用的内存块

20230823175019

如果分配了很多个内存块, 那么当前 cpu 的 slab 满, 将 slab 移动到 slab_full 中

这一部分链表的转移需要 spinlock 自旋锁, 因为多核 CPU

20230823180041

如果此时 slabs_full 当中的某一个 slab 的内存块需要被释放, 则释放当前内存块并将 slab 转移至 slabs_partial 中

20230823181122

当 cpu 中的 slab 的每一个 object 全部分配了之后, 将该 slab 转移至 slabs_full

20230823181240

移动之后如下图所示

20230823181530

API使用

/*分配一块给某个数据结构使用的缓存描述符
  name:对象的名字   size:对象的实际大小  align:对齐要求,通常填0,创建是自动选择.   flags:可选标志位    ctor: 构造函数 */
struct kmem_cache *kmem_cache_create(const char *name, size_t size, size_t align, unsigned long flags, void (*ctor)(void*));

/*销毁kmem_cache_create分配的kmem_cache*/
int kmem_cache_destroy( struct kmem_cache *cachep);

/*从kmem_cache中分配一个object  flags参数:GFP_KERNEL为常用的可睡眠的,GFP_ATOMIC从不睡眠 GFP_NOFS等等等*/
void* kmem_cache_alloc(struct kmem_cache* cachep, gfp_t flags);

/*释放object,把它返还给原先的slab*/
void kmem_cache_free(struct kmem_cache* cachep,  void* objp);

参考

zood