slub分配器
- 内存管理
- 2023-08-13
- 7热度
- 0评论
伙伴系统内存分配是以物理页面4KB为单位，但是实际使用的时候不会一下使用到4KB。实际使用中很多情况会以字节为单位。因此为了更精确的划分使用内存，linux内核在伙伴系统之上使用slab分配器来进行管理。截止目前linux内核中从最初slab发展到现在，衍生了slub，slob三种方式。Linux内核通过配置，选择其中一种。本章节主要围绕slub分配器进行说明。
乒乓球的管理
某公司的组织架构如上，公司划分为多个中心（事业部），各事业部再划分为多个二级部门，员工所在的部门就在各二级部门。
公司有一批数量有限的乒乓球作为全公司的公有资产，提供给员工用于日常借用。乒乓球以盒装为单位，每盒有4个，并对盒和球都进行了编号，球归还是也要与盒子对应。为了有限管理这批乒乓球，假设有如下规定：
- 兵乓球被借出去需要明确知道谁借出去了，便于兵乓球资产追溯管理。
- 闲置的球能尽快收回，以便其他人能够使用，使兵乓球利用最大化。
- 员工在借用乒乓球时需要经过部门->中心->公司各级领导的审批。
当前出现一个问题，就是员工想打球的时候，每次都要跨多级走流程，时间周期比较长。好不容易有个空闲个时间想打个球，等漫长的流程走完活又来了，没时间打了，但是也不能提前先把球借了，闲置屯着，这样别人想打也打不了，每个人都这样，那实际想打球的也无球可打。
为了解决这个问题，小明同学于是设计了这么一套方案，让员工想打球的时候能够快速获得兵乓球，也让公司的球能够利用最大化。
借球
部门主管向公司申请一盒的球（每盒有4个），然后将球分给D同学。并将该盒乒乓球做标记，在部门内部宣导，此后谁要是向借用球，可直接从该盒从获取，自觉做好登记皆可（不再需要走漫长流程）。
有一天部门集体运动，一下子需要多个球，部门主管发现原来的一盒已经不够了，所以又向公司再借了3盒（公司以盒为单位借出，方便管理）。
1、2、3号盒球已经全部借出，所以部门没有再管理了（盒子没啥好管理的，由对应借出的同学共同保管盒子，盒子变成没人要的“孩子”），部门当前管理的是4号盒子（盒子里面还有球，如果还有谁要借，自己拿并自觉做好登记就行）。
还球
借球人借球时需记住自己从那个盒子里面拿的球，还球时需要找到对应的盒子还球。1号、2号、3号盒分别有人归还了球，但是还没有还满，此前的空盒子是不需要管理的，但是现在盒子里面现在有球了，那必须得管理起来了（一旦盒子非空，就需要管理起来了），直接退还给公司也不行啊，一个是盒子没还满，另外一个就是下次又有大需求量还得走流程申请慢。
所以索性部门先将这些盒子管理起来，当前部门累计球数有9个球，闲置在二级部门太多球，也不行，每个二级部门都闲置很多球，球总有耗尽的时候，就有可能其他二级部门的员工没法获得球了，于是公司做了规定，每个部门闲置的球数不能大于4个，因此只有1号和2号盒子可以继续由部门管理，而3号盒子可以不归还公司，但可以由中心先保管。
当盒子不再为空时，先由部门进行管理，当部门的球数闲置超过一定数量后，需要交给由中心管理，交给中心管理的单位也是以盒子为单位（还球的人是根据盒子编号找还球的），这样的好处就是，当有该中心的其他二级部门需要借用球是，发现部门没球了，可以先中心是否有球，如果中心有，那就从中心拿就行，不用从公司申请，这样流程虽然没这么快，但相比跟公司申请的流程也有些优化。
长期进行下去，中心可能会很多个盒子，同时有些盒子是满的（球都还完了），中心也不能由太多闲置球，否则其他中心就可能没法从公司申请到球了，所以公司规定，对中心管理的盒子数量进行了闲置，如盒子数量不能超过10个，当超过10个时，满盒子的球需要归还给公司。
再论借球
当二级部门员工进行借球时，可以从4号盒子免报备申请直接登记拿球就好，这样的借球周期是最短的。而1号和2号盒子虽也归部门管理，但是员工不能从这些盒子里面拿，为了管理效率，二级部门只开个了一个盒子的权限（免报备直接登记即可获取），所以借球只能先从4号盒子拿，当4号盒子被拿完了之后，就需要跟主管报备，看部门还没有备用，发现还有，那就将1号盒子再拿出去，此后大家就又可以从1号盒子免报备借球。当部门没有备用球了，就先问中心有没有，如果中心有，那就将先用中心的，从中心拿到的盒子就归部门管理了。如果中心也没有了，那就只能走流程从公司申请了。
slub 基本原理
一块缓存 = nslab，slab = m * obj，slab = k page。系统从伙伴系统中分配一个或多个连续的物理页组成一个slab，然后将slab切分为n个相同大小的内存（obj），提供给linux内核系统使用，这些相同obj大小组成一个集合。
可以通过cat /proc/slabinfo查看系统中slab的信息。
- actives_objs:已经分配出去的对象数量
- num_objs:一共有多少个对象，包含使用的和未使用的。
- objsize:每个对象的大小是多少，单位是字节
- objperslab:每个slab中的对象数量是多少。
- pagesperslab:每个slab对应的page数量
- limit/batchcount/sharedfactor：这些是可调整的参数，使用slub分配器没有使用
- actives_slabs: 非游离状态的slab数量
- nums_slabs:一共有多少slab
- sharedavail:待记录
slub函数接口
关键数据结构
设计思想
为什么kmem_cache中分为每个cpu分配对应有缓存池，每个节点有对应的缓存池。每个cpu分配的缓存池又再划分为当前正在使用的缓存slab，以及备用缓存slab（Per-CPU partial）？
访问Per-CPU slab是不需要加锁的，所以获取速度很快。访问node slab是需要加锁的，因为这是多个cpu共享的slab，访问速度慢。
而中间的Partial slab是方便Current slab的，系统分配slab必须要从current slab中分区对象，当current slab对象使用完时，就会从依次L2从L3中获取新的slab变成Per-CPU current。因为L3是需要加锁，为了进一步解决这速率问题，中间加了Per-CPU partial slab，当Per-CPU current slab中的所有对象被分配完后将会被移除变成游离状态，而当系统释放当前处理游离状态的full slab中对象时其就会变成部分full 对象的slab，其会被再次从游离状态添加到链表中等待系统从中分配，因此这个slab就会被添加到Partial slab链表中，当下次current slab中没有可用对象时，再将其Partial 链表中的slab置为current slab，这样就不用从Node Partial slab中获取，减少锁的使用，提高系统使用率。
kmem_cache
struct kmem_cache是管理slub分配器的的基础数据结构。
struct kmem_cache {
struct kmem_cache_cpu __percpu *cpu_slab; 一个cpu对应一个本地内存缓存池
slab_flags_t flags;
unsigned long min_partial; 限制struct kmem_cache_node中partial链表slab的数量，如果slab数量超过这个值，那么多余的slab需要被释放会伙伴系统。
unsigned int size; 分配object的大小，包含一些管理数据。
unsigned int object_size; object对象的内存大小，用户层每次分配大小。
struct reciprocal_value reciprocal_size;
unsigned int offset; 用于寻找object的地址
#ifdef CONFIG_SLUB_CPU_PARTIAL
/* Number of per cpu partial objects to keep around */
unsigned int cpu_partial; 每CPU中slab的空闲对象最大值，当超过这个值，需要将slab转移到kmem_cache_node的partial链表
#endif
struct kmem_cache_order_objects oo; 低16代表一个slab中的object数量，高16代表一个slab需要多个page数量。
/* Allocation and freeing of slabs */
struct kmem_cache_order_objects max;
struct kmem_cache_order_objects min;
gfp_t allocflags; /* gfp flags to use on each alloc */
int refcount; /* Refcount for slab cache destroy */
void (*ctor)(void *);
unsigned int inuse; /* Offset to metadata */
unsigned int align; /* Alignment */
unsigned int red_left_pad; /* Left redzone padding size */
const char *name; /* Name (only for display!) */
struct list_head list; /* List of slab caches */
#ifdef CONFIG_SYSFS
struct kobject kobj; /* For sysfs */
#endif
#ifdef CONFIG_SLAB_FREELIST_HARDENED
unsigned long random;
#endif
#ifdef CONFIG_NUMA
/*
* Defragmentation by allocating from a remote node.
*/
unsigned int remote_node_defrag_ratio;
#endif
#ifdef CONFIG_SLAB_FREELIST_RANDOM
unsigned int *random_seq;
#endif
#ifdef CONFIG_KASAN
struct kasan_cache kasan_info;
#endif
unsigned int useroffset; /* Usercopy region offset */
unsigned int usersize; /* Usercopy region size */
struct kmem_cache_node *node[MAX_NUMNODES];NUMA系统中，每个node都有一个slab缓存池。
};
kmem_cache_cpu
每个cpu都有个自己的slab缓存池，使用struct kmem_cache_cpu来描述每个cpu自己所属的缓存池.
struct kmem_cache_cpu {
void **freelist; 指向下一个可用的object地址
unsigned long tid; /* Globally unique transaction id */
struct page *page; 指向当前正在使用的slab地址，只有一个slab。复用struct page来描述一个slab
#ifdef CONFIG_SLUB_CPU_PARTIAL
struct page *partial; 指向slab中只有一部分空闲object的地址，可能存在多个部分空闲对象的slab，slab直接通过struct page中的next链表进行串联起来。
与上一个的区别：这是一个slab集合，而上一个只有一个slab，表示正在使用的slab ，当正在使用的slab中object对象全部用完后，就会变成一个full slab将会被游离出去，而当slab中某个object被释放后，就变成了存在部分空闲对象的slab，这个slab将会被重新被添加到partial中去。
#endif
local_lock_t lock; /* Protects the fields above */
#ifdef CONFIG_SLUB_STATS
unsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};
kmem_cache_node
struct kmem_cache_node {
spinlock_t list_lock;
#ifdef CONFIG_SLUB
unsigned long nr_partial; 节点中slab的数量
struct list_head partial; 用于将各个slab串起来的链表
#ifdef CONFIG_SLUB_DEBUG
atomic_long_t nr_slabs;
atomic_long_t total_objects;
struct list_head full;
#endif
#endif
};
struct page
复用struct page结构体来描述slub。
struct page {
unsigned long flags; 设置标志位，PG_slab，表示页属于SLUB内存管理器
union {
struct { /* slab, slob and slub */
union {
struct list_head slab_list; 用于将slab添加到partial部分空闲链表
struct { /* Partial pages */
struct page *next;
int pages; /* Nr of pages left */
int pobjects; /* Approximate count */
};
};
struct kmem_cache *slab_cache; /* not slob */索引page所所属的kmem_cache
void *freelist; /* first free object */ 指向slab中第一个空闲对象
union {
void *s_mem; /* slab: first object */
unsigned long counters; /* SLUB */
struct { /* SLUB */
unsigned inuse:16; 当前slab已分配对象的数量
unsigned objects:15; 当slab所包含对象的总数
unsigned frozen:1; slab是否缓存到Per-CPU缓存池（冻结），
};
};
};
} _struct_page_alignment;
slub重要概念
内核中通过一下配置来使能SLUB内存管理。
CONFIG_SLUB_DEBUG=y
CONFIG_SLUB=y
CONFIG_SLAB_MERGE_DEFAULT=y
CONFIG_SLUB_CPU_PARTIAL=y
CONFIG_MEMCG_KMEM=y
# CONFIG_SLAB_FREELIST_RANDOM is not set
# CONFIG_SLAB_FREELIST_HARDENED is not set
对象内存组织
对象的内部组织如上，有两种布局方式，主要区别是指向下一个空闲对象的指针存储方式不同。当flags设置了SLAB_TYPESAFE_BY_RCU/SLAB_POISON/ctor构造函数不为空则使用第一种方式，即下一个空闲对象的指针放到当前空闲对象的末端，占据8个字节（64bit）空间；反之使用第二种方式，复用当前对象的空间，存放下一个对象的地址再起始地址。
同时如果使能了CONFIG_SLUB_DEBUG，对象内部的布局会新增用于跟踪分配/释放的用户，便于调试。下面是4个对象的示意图。
struct kmem_cache_cpu::freelist和struct page::freelist这两个都是用于指向第一个空闲对象的地址，其中struct page * page->freelist指向内存节点空闲链表slab中的第一个空闲对象，当这个slab被设置为活动slab后，表示当前该slab正在被使用，page->frozen=1，表示已经处于冻结，那么page->freelist=NULL，slab中第一个空闲对象地址被存放到cpu_slab->freelist中。在分配对象时，值需要将当前freelist地址返回，让后将freelist地址更新到下一个空闲对象的起始地址即可。
slub的挂载和活动的slub
系统中的Slub的可以认为被挂载在4个地方：
- 正在使用的slub（只有一个slub）：cpu_slab->page指向的slub。
- Per-CPU partial上的slub：cpu_slab->partial指向的slub，用链表组织起来，可以存在多个。
- Node节点partial的slub：node->partial指向的slub，用链表组织起来，每个节点对应一个链表，每个链表有可以多个slub。
- 游离状态的slub：前三种slub中的至少还有有部分对象未被使用，处于空闲，当slub中所有对象都被用完时，将会移除，相当于游离状态，如果打开了SLUB_DEBUG，这些slub会被串到链表上。
分配内存对象，都是从kmem_cache中cpu_slab->freelist上获取，该slub为正在使用的slub，也称为活动的slub（自己命名的），即使当cpu_slab->freelist为空或者cpu_slab->page为空，从Per-CPU partial或者Node partial中获取slub时，其就会被设置为活动的slub。
创建kmem_cache
分配slub cache
第一次分配
Slub刚创建的时候并没有实际分配内存，所以kmem_cache中无论时cpu_slab还是node节点中，都没有slab缓存，第一次申请的时候会从伙伴系统分配页面生成一个slab，然后取其中一个object返回给系统。此后，在没有分配完成当前slab中的object时，分配内存直接返回freelist就是对应的空闲object内存。
从Per CPU partial中分配获取
从当前活动的slab中无法分配到object，那就从Per CPU partial上进行获取一个slab进行分配，设置为活动的slab，此前的活动的slab就会被游离出去（full slab，如果开了SLUB DEBUG，会添加到这个debug链表中，如果没有开，就相当于没有要的孩子，当释放对象的时候会通过对应的slab描述符号相关成员找出来。）。
从Node Partial中获取
如果从Per CPU partial中依旧没法后去到slab，就会从node partial中获取slab，然后将其设置为活动的slab，此前活动的slab设置为游离状态。
释放slub cache
- Slab中对象部分被使用（非游离）：① ② ③场景
（1）释放了obj后，slab中还存在部分obj未释放：直接释放，建立好空闲obj之间的联系即可。
（2）释放了obj后，slab所有的obj都为空闲：如果在node partial上，nr_partial>min_partial,表明节点上存在的slab数量超过上限，空闲的slab会回收到伙伴系统中；如果是在Per-CPU partial上，管理的slab中空闲object数量大于cpu_partial（kmem_cache成员），将该slab移动到node partial链表上管理。 - Slab中对象全部被使用（游离）：④⑤场景
释放了obj之后，slab变成部分空闲的slab，由于此前是处于游离状态，没有添加到对应链表管理（未开SLUB DEBUG），当变成部分空闲是，就需要将其进行管理。首先尝试将slab添加到Per-CPU partial中，如果Per-CPU超过阈值没法管理了，就添加到Node parital中。
kmalloc
函数接口
kmalloc实现
static __always_inline void *kmalloc(size_t size, gfp_t flags)
{
1.判断参数是否为常数
if (__builtin_constant_p(size)) {
#ifndef CONFIG_SLOB
unsigned int index;
#endif
if (size > KMALLOC_MAX_CACHE_SIZE)
return kmalloc_large(size, flags);
#ifndef CONFIG_SLOB
index = kmalloc_index(size);
if (!index)
return ZERO_SIZE_PTR;
return kmem_cache_alloc_trace(
kmalloc_caches[kmalloc_type(flags)][index],
flags, size);
#endif
}
return __kmalloc(size, flags);
2.直接走这里
}
void *__kmalloc(size_t size, gfp_t flags)
{
struct kmem_cache *s;
void *ret;
1.如果分配空间大于KMALLOC_MAX_CACHE_SIZE，直接从伙伴系统进行分配
if (unlikely(size > KMALLOC_MAX_CACHE_SIZE))
return kmalloc_large(size, flags);
2.创建slab的数据结构，实际上建立的是全局kmem_cache
s = kmalloc_slab(size, flags);
if (unlikely(ZERO_OR_NULL_PTR(s)))
return s;
3.slab分配器
ret = slab_alloc(s, flags, _RET_IP_, size);
trace_kmalloc(_RET_IP_, ret, size, s->size, flags);
ret = kasan_kmalloc(s, ret, size, flags);
return ret;
}
struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags)
{
unsigned int index;
struct kmem_cache *s = NULL;
if (size <= 192) {
if (!size)
return ZERO_SIZE_PTR;
1.根据分配大小找到对应的index系数，用于后续查找对应的kmem_cache
index = size_index[size_index_elem(size)];
} else {
if (WARN_ON_ONCE(size > KMALLOC_MAX_CACHE_SIZE))
return NULL;
index = fls(size - 1);
}
trace_android_vh_kmalloc_slab(index, flags, &s);
if (s)
return s;
2.在全局kmalloc_caches数组中找到对应的kmem_cache示例返回。
return kmalloc_caches[kmalloc_type(flags)][index];
}
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 */
};
启动阶段创建kmem_cache
系统启动初期调用create_kmalloc_caches创建多个管理不同大小对应的kmem_cache，最大的size一般是8K，也就是对应的是kmalloc-8192，当系统通过kmalloc申请内存时，会直接从其中获取。
void __init create_kmalloc_caches(slab_flags_t flags)
{
int i;
enum kmalloc_cache_type type;
if (android_kmalloc_64_create)
for (type = KMALLOC_NORMAL; type <= KMALLOC_RECLAIM; type++)
new_kmalloc_cache(6, type, flags);
/*
* Including KMALLOC_CGROUP if CONFIG_MEMCG_KMEM defined
*/
for (type = KMALLOC_NORMAL; type <= KMALLOC_RECLAIM; type++) {
for (i = KMALLOC_SHIFT_LOW; i <= KMALLOC_SHIFT_HIGH; i++) {
if (!kmalloc_caches[type][i])
new_kmalloc_cache(i, type, flags);
/*
* Caches that are not of the two-to-the-power-of size.
* These have to be created immediately after the
* earlier power of two caches
*/
if (KMALLOC_MIN_SIZE <= 32 && i == 6 &&
!kmalloc_caches[type][1])
new_kmalloc_cache(1, type, flags);
if (KMALLOC_MIN_SIZE <= 64 && i == 7 &&
!kmalloc_caches[type][2])
new_kmalloc_cache(2, type, flags);
}
}
/* Kmalloc array is now usable */
slab_state = UP;
#ifdef CONFIG_ZONE_DMA
for (i = 0; i <= KMALLOC_SHIFT_HIGH; i++) {
struct kmem_cache *s = kmalloc_caches[KMALLOC_NORMAL][i];
if (s) {
kmalloc_caches[KMALLOC_DMA][i] = create_kmalloc_cache(
kmalloc_info[i].name[KMALLOC_DMA],
kmalloc_info[i].size,
SLAB_CACHE_DMA | flags, 0,
kmalloc_info[i].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(16, 16),
INIT_KMALLOC_INFO(32, 32),
INIT_KMALLOC_INFO(64, 64),
INIT_KMALLOC_INFO(128, 128),
INIT_KMALLOC_INFO(256, 256),
INIT_KMALLOC_INFO(512, 512),
INIT_KMALLOC_INFO(1024, 1k),
INIT_KMALLOC_INFO(2048, 2k),
INIT_KMALLOC_INFO(4096, 4k),
INIT_KMALLOC_INFO(8192, 8k),
INIT_KMALLOC_INFO(16384, 16k),
INIT_KMALLOC_INFO(32768, 32k),
INIT_KMALLOC_INFO(65536, 64k),
INIT_KMALLOC_INFO(131072, 128k),
INIT_KMALLOC_INFO(262144, 256k),
INIT_KMALLOC_INFO(524288, 512k),
INIT_KMALLOC_INFO(1048576, 1M),
INIT_KMALLOC_INFO(2097152, 2M),
INIT_KMALLOC_INFO(4194304, 4M),
INIT_KMALLOC_INFO(8388608, 8M),
INIT_KMALLOC_INFO(16777216, 16M),
INIT_KMALLOC_INFO(33554432, 32M)
};
static __always_inline unsigned int __kmalloc_index(size_t size,
bool size_is_constant)
{
if (!size)
return 0;
if (android_kmalloc_64_create && size <= 64)
return 6;
if (size <= KMALLOC_MIN_SIZE)
return KMALLOC_SHIFT_LOW;
if (KMALLOC_MIN_SIZE <= 32 && size > 64 && size <= 96)
return 1;
if (KMALLOC_MIN_SIZE <= 64 && size > 128 && size <= 192)
return 2;
if (size <= 8) return 3;
if (size <= 16) return 4;
if (size <= 32) return 5;
if (size <= 64) return 6;
if (size <= 128) return 7;
if (size <= 256) return 8;
if (size <= 512) return 9;
if (size <= 1024) return 10;
if (size <= 2 * 1024) return 11;
if (size <= 4 * 1024) return 12;
if (size <= 8 * 1024) return 13;
if (size <= 16 * 1024) return 14;
if (size <= 32 * 1024) return 15;
if (size <= 64 * 1024) return 16;
if (size <= 128 * 1024) return 17;
if (size <= 256 * 1024) return 18;
if (size <= 512 * 1024) return 19;
if (size <= 1024 * 1024) return 20;
if (size <= 2 * 1024 * 1024) return 21;
if (size <= 4 * 1024 * 1024) return 22;
if (size <= 8 * 1024 * 1024) return 23;
if (size <= 16 * 1024 * 1024) return 24;
if (size <= 32 * 1024 * 1024) return 25;
if ((IS_ENABLED(CONFIG_CC_IS_GCC) || CONFIG_CLANG_VERSION >= 110000)
&& !IS_ENABLED(CONFIG_PROFILE_ALL_BRANCHES) && size_is_constant)
BUILD_BUG_ON_MSG(1, \\\\\\\"unexpected size in kmalloc_index()\\\\\\\");
else
BUG();
/* Will never be reached. Needed because the compiler may complain */
return -1;
}