1.背景

buddy system 算法分配的物理内存是以page frame 作为基本的管理粒度，这种方式适合处理大内存请求的分配。
对于处理小内存请求，比如几十字节到几百字节，采用buddy system 申请一整个page frame来存会比较浪费。
而在page frame 中分配小内存容易引人内存碎片化问题。这是由于请求的内存的大小与分配的内存大小不匹配导致的。
通常的解决方案提供几何分布大小的内存，即内存大小是2的N 次幂，而不是要存的实际数据的大小。这样内存碎片化总是小于50%。
Linux 采用Slab 分配器，用于分配小size 和频繁使用数据结构的内存分配。

image.png

2.Slab 分配器原理

主要目的
1）消除小size内存分配由buddy system 引起的内存碎片化问题
i. 两套小内存的cache, 内存size 从2^5,到217
ii. 两套cache 分别称为size-N和size-N(DMA), size为分配的内存的大小。
iii. kmalloc()用于分配这样的object.
2）缓存常使用的对象
省去内核分配，初始化，释放object 的过程的时间开销。
i.创建新的slab 时，object 就包装好并初始化；
ii. 释放object时，会让object 处于已初始化的状态，这样分配的时候会很快
3）通过让object 对其到L1 或L2 cache ,以充分利用硬件cache
i. color slab 尝试让不同slab的object 使用不同的cache line.
ii. 将object 放在slab中不同的起始偏移
iii. 确保同一个slab cache的object 之间不会互相flush 对方的cache.

image.png

slab 分配器构成
1）slab 分配器由各种各样的cache链接到一个cache chain的双向环形链表；
2） cache: 每个cache 是特定类型的object 的管理器；各种cache 通过链表链接起来；
3） slab: 每个cache 划分成包含一个到多个的连续page frame 内存的slabs;
4） object: 每个slab 被划分成小块的cache 管理的的objects

image.png

3.Slab分配器API

3.1 通用cache

kmalloc() 和kfree() 从通用的sizes cache 中分配一块内存和释放内存
3.2 专用cache
kmem_cache_*
1）kmem_cache_create(), kmem_cache_destory() 创建和销毁cache
2）kmem_cache_alloc(), kmem_cache_free() 分配和释放object
3）kmem_cache_reap()
4）kmem_cache_shrink()

image.png

4.Slab分配器实现

4.1 cache 描述符-struct kmem_cache_t

每种cache由一个 struct kmem_cache_t的结构描述

image.png
成员struct kmem_list3 lists 包含三个slab list

image.png
两种cache

1）专用cache-称之为kmem_cache
i. object 是 kernel 使用，cache_cache 容纳这种类型cache
ii.kmem_cache_create() 创建专用的cache
根据参数，决定slab 描述符放slab 内部还是外部;
从cache_cache 中分配新的cache
并插入到cache_chain 链表中
iii. kmem_cache_destory 销毁cache,从cache_chain中移除，常用于module 加载常见自己的cache, 卸载时销毁
xi. kmem_cache_shrink 销毁一个cache 中的所有slabs

2）专用cache- size cache
object 用kmalloc 分配
初始化阶段，kmem_cache_init 创建好通用cache

4.2 slab 描述符-struct slab

slab 描述符

image.png
确定归属的slab 或cache-page 与 slab，cache 关系
1）通过struct page中的list 确定一个object 归属的cache和slab
2）page->list 的next 确定cache, prev 确定slab

image.png
可能位于两种可能的位置
1）外部Slab描述符-OFF_SLAB
保存于slab 之外

image.png

2）内部Slab描述符-ON_SLAB
保存于slab 内部，位于分配给slab的第一个page frame 的起始

image.png

4.3 cache 与slab 之间关系

full slab , partial full slab,和free slab 分别链接到cache 的list 中

image.png

4.4 object

初始化object
1）创建slab 时，slab 中的所有object 就完成初始化；
2）若有构造函数，会为每个object 调用一次；
3）一旦object 释放时，object 会被设置为初始化状态；
4）kmem_cache_init_objs() 负责初始化objects
分配object-kmem_cache_alloc
1）kmem_cache_alloc（）负责分配一个object
2）基本步骤
i. 做基本check
ii. 选择一个从哪个slab list 分配slab, 要么slabs_partial , 要么slabs_free.
iii. 若没有slabs_free ，则增加cache 空间，创建为slabs_free创建新的slab.
iiii. 从选择的slab 中分配一个object.
Note: SMP 需要做额外一步，在分配一个object 之前，检查 per-CPU cache 中是否有一个可用。若有则使用，若没有则批量分配batchcount 个object，放入per-CPU cache中。
image.png
释放object kmem_cache_free
1）UP 情况，直接将object 返回给slab
2）SMP 情况，object 返回给per-CPU cache
3）两者都会调用destructor

4.5 kmalloc/kfree-通用cache-sizes cache

分配两套小内存分配的caches
一套用于DMA，size-N(DMA)cache，一套正常用途-size-N cache，可通过/proc/slabinfo 查看
每个size cache的信息通过保存在struct cache_sizes结构

image.png

cs_size 是内存的大小
cs_cachep是正常内存使用的cache
cs_dmacachep 是用于DMA 的cache
cache_sizes 数组

image.png
kmalloc
从size_cache 中分配最接近请求大小的2^N的大小的匹配的内存

image.png