# Linux slob/slab/slub Date: 2020-07-11 ### 概述 Linux初始化通过`bootmem`/`memblock`引导内存分配进行内存管理，支持`buddy system`完成相关初始化后，将物理内存分配的功能转交给`buddy system`，`buddy system`是以`page`为单位分配方式。 对于内核要经常创建的对象， 如`task_struct`，`fs_struct`, `mm_struct` 通常会放到高速缓存中，保留基本结构,从而可以重复使用他们, 这里需要用到`slab`分配器。 `slab`分配器 - 通过 `buddy system` 申请空闲页 - 将申请到页处理为更小的分配单元,为其他子系统提供缓冲区存放内核对象 - 缓存经常使用的对象，释放后保存器初始状态，再次分配对象速度会很快 - 充分利用硬件高速缓存 ### 历史发展 - 1991 Initial K&R allocator - 1996 SLAB allocator - 2003 SLOB allocator - 2004 NUMA SLAB - 2007 SLUB allocator - 2008 SLOB mulitlist - 2011 SLUB fastpath rework - 2013 Common slab code - 2014 SLUBification of SLAB ... ### 常用的分配器 - SLOB: K&R allocator (1991-1999) - SLAB: Solaris type allocator (1999-2008) - SLUB: Unqueued allocator (2008-today #### SLOB - 简单的空闲对象列表管理 - 遍历列表查找合适的空间，没有的话申请向伙伴系统申请page增加堆栈大小. - 碎片化严重 - 优化: 按照不同大小多个链表，减少碎片。 ##### 原理图 ![](/wp-content/uploads/2020/07/slob.png) ![](https://garlicspace.com/wp-content/uploads/2020/07/slob-1024x738.png) 可以看到通过`page`中的`freelist`将一个`pageframe`中的空闲块一个一个链接起来. ##### 具体实现 ###### 涉及文件 slob初期代码可以查看 [slob: introduce the SLOB allocator](https://lwn.net/Articles/157944/) ```C /mm/slab.h /include/linux/slab.h /mm/slob.c /mm/slab_common.c 与分配策略无关 ``` ##### 数据结构 标准的`kmem_cache`文件结构 ```C struct kmem_cache { ... } ``` `SLOB` 原有结构在`/mm/slob.c` ```C struct slob_block { slobidx_t units; }; typedef struct slob_block slob_t; #define SLOB_BREAK1 256 #define SLOB_BREAK2 1024 static LIST_HEAD(free_slob_small); static LIST_HEAD(free_slob_medium); static LIST_HEAD(free_slob_large); ``` 可以看在原有一条`freelist`的基础上增加为了三条`free`_slob_`*`, 根据`slab`大小, 通过大小`256`,`1024`分为三段。 ###### 相关代码 - 核心流程首先从`free_slob_small`, `free_slob_medium`, `free_slob_large`,通过`slob_page_alloc`查找空闲块, 没有的话通过`slob_new_pages`申请新页 ```C static void *slob_alloc(size_t size, gfp_t gfp, int align, int node, int align_offset) { ... if (size < SLOB_BREAK1) slob_list = &free_slob_small; else if (size < SLOB_BREAK2) slob_list = &free_slob_medium; else slob_list = &free_slob_large; list_for_each_entry(sp, slob_list, slab_list) { ... b = slob_page_alloc(sp, size, align, align_offset,\ &page_removed_from_list); ... } if (!b) { b = slob_new_pages(gfp & ~__GFP_ZERO, 0, node); ... } } ``` - 支持NUMA，新版本可以看到相关节点参数 ```C #ifdef CONFIG_NUMA void *__kmalloc_node(size_t size, gfp_t gfp, int node) { return __do_kmalloc_node(size, gfp, node, _RET_IP_); } EXPORT_SYMBOL(__kmalloc_node); void *kmem_cache_alloc_node(struct kmem_cache *cachep, gfp_t gfp, int node) { return slob_alloc_node(cachep, gfp, node); } EXPORT_SYMBOL(kmem_cache_alloc_node); #endif ``` - 根据`PAGE_SIZE`判断使用 `slob`还是`buddy system` ```C static void *slob_alloc_node(struct kmem_cache *c, gfp_t flags, int node) { ... if (c->size < PAGE_SIZE) { b = slob_alloc(c->size, flags, c->align, node, 0); ... } else { b = slob_new_pages(flags, get_order(c->size), node); ... } ... } ``` #### SLAB - 本地队列存储热点数据 - 每个cpu和每个节点分配队列。 - 远程节点的队列。 - 复杂的数据结构。 - 基于对象的内存策略。 - 指数增长节点\*nr\_cpus, 大量的内存被缓存。 - 每个处理器都必须每2HZ扫描其每个slab缓存的队列。 ##### 原理图 ![](https://garlicspace.com/wp-content/uploads/2020/07/slab-1-1024x772.png) 1. 针对一个页面中的free `object`的管理， 使用`freelist`做为索引数组 2. `page->active`保存了索引数组的最大长度。 3. 通过设置`Coloring`更好支持硬件缓存, 将对象放置在`slab`中的不同起始偏移处，使得这些对象落在`CPU`高速缓存中不同的行，减少碰撞(`collide`)。 ![](https://garlicspace.com/wp-content/uploads/2020/07/slab-1024x771.png) 1. 每个`cpu`分配一个`array_cache`缓存结构,被称为`cpu_cache`, (cpu\_cache 是`per-CPU`变量, 缓存可以不使用自旋锁，从而增加处理效率) 2. 针对`NUMA`结构，缓存结构针对每个节点为了一个节点缓存`kmem_cache_node`, 通过三个`queue`(`parital_list`, `full_list`, `empty_list`)维护`slab`信息。 3. `CPU` Cache有每个`CPU`单独使用的`L1 cache` , `L2 cache` ,共享使用的 `L3 cache`, 结构中维护了本地节点`per-CPU`的array\_cache, 节点共享的缓冲`kmem_cache_node`的`shared`,及远程节点缓冲的 `alien`。 4. `RedZone`调试标识, 每一个对象末尾, 增加这个标识， 如果这个标识被修改, 判断是否发生缓冲区溢出 5. `last caller`调试标识,位于`RedZone`之后, `2.6`版本引入, 用于存放析构对象函数. 6. `Poinsing`调试标识，通过创建和释放`slab`，将要感染的对象填充`0x5A`, 分配时检查， 如果被改变， 就知道之前是否使用过 7. `Payload`就是缓存的`object` * * * 在分析`shared` , `alien` 过程中发现一个特殊数字`0xbaadf00d`, `0xBAADF00D`\-`bad food`在微软的`LocalAlloc`\-`LMEM_FIXED`函数中使用，用以在已启用调试堆的情况下，标识未初始化的分配堆内存。 来自 [wiki - Hexspeak](https://zh.wikipedia.org/wiki/Hexspeak),看来贡献者应该有对`windows`开发比较了解。 ##### 具体实现 ###### 涉及文件 现有版本中涉及文件([v5.8-rc3](https://elixir.bootlin.com/linux/v5.8-rc3/source/mm/slob.c#L637)) ```C /mm/slab.h /include/linux/slab_def.h /mm/slab.c /mm/slab_common.c 与分配策略无关 ``` ##### 数据结构 可以看到缓冲主要分为两部分， 一部分是`per-CPU`变量, 一部分保存的是节点缓存 ```C struct kmem_cache { struct array_cache __percpu *cpu_cache; ... struct kmem_cache_node *node[MAX_NUMNODES]; }; ``` 节点缓存区使用了`slabs_partial`, `slabs_full`, `slabs_free`管理`slabs` ```C struct kmem_cache_node { spinlock_t list_lock; ... struct list_head slabs_partial; struct list_head slabs_full; struct list_head slabs_free; ... }; ``` 下面这个是`CPU`缓存结构 ```C struct array_cache { unsigned int avail; unsigned int limit; unsigned int batchcount; unsigned int touched; void *entry[]; }; ``` 可以看到默认情况下, 其他CPU的缓存,`alien`缓存, 特别的多出一个自旋锁`lock` ```C struct alien_cache { spinlock_t lock; struct array_cache ac; }; static int use_alien_caches __read_mostly = 1; static int __init noaliencache_setup(char *s) { use_alien_caches = 0; return 1; } ``` ###### 相关代码 - `freelist`管理相关 下面是初始化时的代码片段在文件`/mm/slab.c`中, 可以看到对`page->freelist`和`page->s_mem`的设置, ```C static void cache_init_objs(struct kmem_cache *cachep, struct page *page) { ... if (!shuffled && OBJFREELIST_SLAB(cachep)) { page->freelist = index_to_obj(cachep, page, cachep->num - 1) + obj_offset(cachep); } ... for (i = 0; i < cachep->num; i++) { objp = index_to_obj(cachep, page, i); ... if (!shuffled) set_free_obj(page, i, i); } ... } ``` ```C static inline void set_free_obj(struct page *page, unsigned int idx, freelist_idx_t val) { ((freelist_idx_t *)(page->freelist))[idx] = val; } ``` ```C static inline void *index_to_obj(struct kmem_cache *cache, struct page *page, unsigned int idx) { return page->s_mem + cache->size * idx; } ``` 通过`page->active`设置索引数组的大小 ```C static void *slab_get_obj(struct kmem_cache *cachep, struct page *page) { void *objp; objp = index_to_obj(cachep, page, get_free_obj(page, page->active)); page->active++; return objp; } static void slab_put_obj(struct kmem_cache *cachep, struct page *page, void *objp) { unsigned int objnr = obj_to_index(cachep, page, objp); ... page->active--; if (!page->freelist) page->freelist = objp + obj_offset(cachep); set_free_obj(page, page->active, objnr); } ``` - 缓存分配 可以看到分配顺序是先取`cpu`缓存, 通过`cache_alloc_refill`后还有一个回填到`CPU`缓存的动作。 ```C static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags) { ... ac = cpu_cache_get(cachep); ... objp = cache_alloc_refill(cachep, flags); ac = cpu_cache_get(cachep); ... return objp; } ``` `CPU`缓冲处理很简单高效 ```C static inline struct array_cache *cpu_cache_get(struct kmem_cache *cachep) { return this_cpu_ptr(cachep->cpu_cache); } ``` 如果不使用`cpu`缓存， 就判断节点`share`出来的缓存通过`transfer_objects`直接拷贝了, 否则话就会通过上面提到的`slab_paritial`或者`slab_free`将进行`batchcount`分配, 如果还是没有就直接调用`cache_grow_begin` 申请物理页面了。 ```C static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags) { ... shared = READ_ONCE(n->shared); if (!n->free_objects && (!shared || !shared->avail)) goto direct_grow; shared = READ_ONCE(n->shared); if (shared && transfer_objects(ac, shared, batchcount)) { shared->touched = 1; goto alloc_done; } while (batchcount > 0) { page = get_first_slab(n, false); if (!page) goto must_grow; ... 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: ... 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); ... } ... return ac->entry[--ac->avail]; } ``` ```C static int transfer_objects(struct array_cache *to, struct array_cache *from, unsigned int max) { ... memcpy(to->entry + to->avail, from->entry + from->avail -nr, sizeof(void *) *nr); ... } ``` 针对跨节点情况， 如果是设置了`SLAB_MEM_SPREAD`, 分散到各个`cpu`缓存进行分配, 可以使用`cpuset_slab_spread_node`, `mempolicy_slab_node`两个方法得到节点编号, 通过 `__cache_alloc_node`进行分配。 ```C static void *alternate_node_alloc(struct kmem_cache *cachep, gfp_t flags) { ... nid_alloc = nid_here = numa_mem_id(); if (cpuset_do_slab_mem_spread() && (cachep->flags & SLAB_MEM_SPREAD)) nid_alloc = cpuset_slab_spread_node(); else if (current->mempolicy) nid_alloc = mempolicy_slab_node(); ... if (nid_alloc != nid_here) return ____cache_alloc_node(cachep, flags, nid_alloc); return NULL; } ``` - 缓冲扫描 , `2HZ`扫描一次 ```C #define REAPTIMEOUT_AC (2*HZ) #define REAPTIMEOUT_NODE (4*HZ) static void cache_reap(struct work_struct *w) { ... schedule_delayed_work_on(smp_processor_id(), work, round_jiffies_relative(REAPTIMEOUT_AC)); } ``` 我的机器 1s = 100HZ, 所以 1HZ 约等于 `10`ms, 也就是`20ms`进行以此缓冲扫描回收空闲对象 ```Bash [root@centosgpt ~]# cat /proc/interrupts | grep timer && \ sleep 1 && cat /proc/interrupts | grep timer 0: 4 0 IO-APIC 2-edge timer LOC: 8475 8291 Local timer interrupts HVS: 0 0 Hyper-V stimer0 interrupts 0: 4 0 IO-APIC 2-edge timer LOC: 8577 8390 Local timer interrupts HVS: 0 0 Hyper-V stimer0 interrupts [root@centosgpt ~]# ``` - shared 与 alien 释放`alient`远程缓冲时会先放到`shared` 缓冲中 ```C static void __drain_alien_cache(struct kmem_cache *cachep, struct array_cache *ac, int node, struct list_head *list) { ... if (n->shared) transfer_objects(n->shared, ac, ac->limit); ... } ``` ### SLUB - `Unqueued` 无队列的设计 (针对`SLAB`) - 队列就是一个单页面中的`slab`队列。 页面与CPU关联 - 使用`per-CPU` partials链表 - 在一个`cpu`完成实现快速通道 - 基于页面的策略。 - 多个级别的碎片整理功能。 - 当前的默认`slab`分配器。 ##### 原理说明 ![](https://garlicspace.com/wp-content/uploads/2020/07/slub-1024x767.png) 1. 相比`slab`, `slub`结构进行了精简, `per-cpu`缓存结构体简化 2. `cpu node` 结构简化, 使用`partial_list` 3. `FrozenPagelock`:`page->frozen` 设置为1仅能存放在指定`cpu`的`partial list`中 4. `Payload`就是缓存的`object` 5. `RedZone`调试标识, 增加这个标识， 如果这个标识被修改, 判断是否发生缓冲区溢出, 如果启用填写`0xcc`,不启用仅作填充(`Padding`)`0xbb` 6. `Poinsing`调试标识，通过创建和释放`slab`，将要感染的对象填充`0x5A`, 分配时检查， 如果被改变， 就知道之前是否使用过 7. `Tracking/Debugging`, 存放`SLAB_STORE_USER`相关数据存储最后的拥有者信息 8. `Free Pointer`，一个大小为sizeof(void\*)指针, 在设置`Poison`时，填充`POISON_FREE`(`0x6b`) 9. `Padding` 填充数据 `0x5a` ##### 具体实现 ###### 涉及文件 ```C /mm/slab.h /include/linux/slub_def.h /mm/slub.c /mm/slab_common.c 与分配策略无关 ``` ##### 数据结构 可以看到和 `slab`使用同样结构`kmem_cache`, 缓冲主要分为两部分， 一部分是`per-CPU`变量, 一部分保存的是节点缓存,不过`cpu_slab`类型略有调整 ```C struct kmem_cache { struct kmem_cache_cpu __percpu *cpu_slab; ... struct kmem_cache_node *node[MAX_NUMNODES]; }; ``` 也就是这个结构直接挂在了页面`page` ```C struct kmem_cache_cpu { void **freelist; unsigned long tid; struct page *page; #ifdef CONFIG_SLUB_CPU_PARTIAL struct page *partial; /* Partially allocated frozen slabs */ #endif ... }; ``` 节点保存一个`partial`指针做为`Cpu`缓存的备份 ```C struct kmem_cache_node { spinlock_t list_lock; ... unsigned long nr_partial; struct list_head partial; ... }; ``` ###### 相关代码 - 缓冲申请 先去`per-CPU`的cpu\_slab, 取不到通过 `__slab_alloc`再申请 ```C static __always_inline void *slab_alloc_node(struct kmem_cache *s, gfp_t gfpflags, int node, unsigned long addr) { ... do { ... c = raw_cpu_ptr(s->cpu_slab); } while (...); ... if (...) { object = __slab_alloc(s, gfpflags, node, addr, c); stat(s, ALLOC_SLOWPATH); } else { ... } ... } ``` 配置了`CONFIG_SLUB_CPU_PARTIAL`, 从`per-CPU`的`partial`申请 ```C static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node, unsigned long addr, struct kmem_cache_cpu *c) { ... if (slub_percpu_partial(c)) { page = c->page = slub_percpu_partial(c); slub_set_percpu_partial(c, page); stat(s, CPU_PARTIAL_ALLOC); ... } ... freelist = new_slab_objects(s, gfpflags, node, &c); ... } ``` 否则需要考虑从备用节点`parital`申请或重新申请页 ```C static inline void *new_slab_objects(struct kmem_cache *s, gfp_t flags, int node, struct kmem_cache_cpu **pc) { ... freelist = get_partial(s, flags, node, c); ... page = new_slab(s, flags, node); ... } ``` 从当前节点寻找`partial`，找不到如果存在其他节点寻找其他节点上`partial` ```C static void *get_partial(struct kmem_cache *s, gfp_t flags, int node, struct kmem_cache_cpu *c) { ... object = get_partial_node(s, get_node(s, searchnode), c, flags); ... return get_any_partial(s, flags, c); } ``` 备用节点没有可用直接申请物理页面 ```C static struct page *new_slab(struct kmem_cache *s, gfp_t flags, int node) { ... return allocate_slab(s, flags & (GFP_RECLAIM_MASK | GFP_CONSTRAINT_MASK), node); } static struct page *allocate_slab(struct kmem_cache *s, gfp_t flags, int node) { ... page = alloc_slab_page(s, alloc_gfp, node, oo); ... } ``` ### 参考及引用 Christoph Lameter [Slab allocators in the Linux Kernel: SLAB, SLOB, SLUB](https://events.static.linuxfound.org/sites/events/files/slides/slaballocators.pdf) [linux内存源码分析 - SLAB分配器概述](https://www.cnblogs.com/tolimit/p/4566189.html) [Linux slab allocator and cache performance](https://stackoverflow.com/questions/46731933/linux-slab-allocator-and-cache-performance/57345687#57345687) [cache coloring on slab memory management in Linux kernel ](https://stackoverflow.com/questions/15016359/cache-coloring-on-slab-memory-management-in-linux-kernel)([v5.8-rc3](https://elixir.bootlin.com/linux/v5.8-rc3/source/mm/slob.c#L637))