在一切开始之前

buddy system 只能做到按page_size 为粒度的内存分配，更加细小的内存分配使用slab分配器来实现，与申请页大小的大内存一样，slab分配器也是从页框分配器申请页框的

img

另外还有一个比较形象的图，但是比较乱：

img

slab分配器历史

https://zhuanlan.zhihu.com/p/490588193

slab的实现最早出现在Solaris 2.4版本，以Sun公司研究员Jeff Bonwick发表的论文《The Slab Allocator: An Object-Caching Kernel Memory Allocator》为雏形发展而来，现在已经在Unix和类Unix系统广泛使用了。slab的出现旨在解决以下两个问题：

  1. 内存利用率低。正如前面提到的，如果只需要分配几个字节，如果只使用伙伴系统，则至少要分配一个页面，浪费率达到99.9%；
  2. 内存分配效率低和访问时间长。使用伙伴系统，需要走的分配路径很长，遇到内存不足时，还会进行内存压缩或回收。再者，伙伴系统每次至少分配一个页框，访问内存时，容易出现cache miss的情况。使用slab分配的小内存，即使被释放了，还很有可能在cache中，这时候再分配给其他任务使用，效率有较大提升。

简单来说，slab可以认为是进程与伙伴系统之前的中间层

而后面slab分配器也演变出了两种变体，一种是slob，一种是slub

https://img-blog.csdnimg.cn/20200321065553420.png

slab分配器在大多数情况下状态良好，但其需要大量的元数据，对嵌入式系统来说，slab分配器的代码量和复杂性都过高，故开发者在slab的基础上开发了精简版slub分配器，其通过将页帧打包为组，然后再利用page结构中未使用的字段来管理这些组，试图最小化所需管理数据带来的开销。

主要是三点

1、每个node节点有三个链表，分别记录空闲slab、部分空闲slab和非空闲slab。当回收操作来不及时，三个链表记录的页框会较长时间停留到slab管理器中，不利于提高内存的使用率。针对这点，slub只保留了一个链表，就是部分空闲slub。另外就是shared共享链表可能导致一个slab持有较多slab，无法即使释放给伙伴系统。slub去掉了该链表。

2、slab为了增加分配速度，引入了一些管理数组，如每个cpu私有数据记录的是object的地址，这些object可能来自不同的slab，那么不利于slab的回收。slub改成记录一个实际可用的slub，不会影响其他slub的回收。slub分配器摒弃了很多管理数据，大大减小了内存开销。

3、出于对内存使用率的极致追求，slub去除了slab的着色做法，取而代之是slub复用，通过slub复用减轻cache冲突的情况。

而slob主要为小型的嵌入式系统设计，数据结构相对于slab来说比较简单，不会占用太多内存。

slab示意图：

img

slub示意图：

img

通过命令可以查看系统的slab相关信息

1
cat /proc/slabinfo

image-20221124175733003

slab分配器基本原理

在分析源码之前，由于slab分配器实现较为复杂，故最好能先了解一下其基本原理，非常推荐这篇文章

以下的阐述也基本摘自此篇文章

img

​ 我们要申请的小内存，就是去申请一个object，object类似buddy system那样，也是有着各种不同大小的object，如kmalloc-16 ，kmalloc-32 等，一个object中有一个指针指向下一个object从而形成链表。

img

我们将连续的整页内存，分成许多大小的object，然后再分别分配出去，这样的连续内存，称为一个slab。

每种不同大小的object由不同的kmem_cache结构体管理，可以将kmem_cache 视为零售商。

kmem_cache 又有两个部门，一个是仓库：kmem_cache_node，一个是营业厅：kmem_cache_cpu，该营业厅只保留一个slab，在没有剩余空闲内存的情况下，从仓库再批发slab换出。

而仓库管理着几个空闲链表，partial链表存访着仍有空闲空间的slab，full链表存放着分配完的slab。

kmem_cache_cpu的freelist变量中保存着下一个空闲object的地址

slab满换出的过程：

img

申请一个object之后

img

当full的slab中有object被释放时，该slab就被放入partial链表用于再次分配

img

img

当所有slab被分配完时，再从buddy system申请slab 并初始化

img

img

非常形象了，我也不好意思抄太多，不懂的建议看原文。

相关结构体

以下源码都出自v5.17的slub分配器，所以跟上面图的流程会有些小区别

kmem_cache 定义于 /include/linux/slub_def.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
 * Slab cache management.
 */
struct kmem_cache {
	struct kmem_cache_cpu __percpu *cpu_slab; //各cpu主要用于分配的slab 即前面所说的“营业厅”
  	//对于每个CPU都有一个本地的缓冲池，当分配Object的时候优先从per-cpu中分配
	/* Used for retrieving partial slabs, etc. */
	slab_flags_t flags;
	unsigned long min_partial; // partital链表中最小的object个数，object个数应保持不低于这个值
	unsigned int size;	/* object size 包含元数据 */
	unsigned int object_size;/* object size 不包含元数据 */
	struct reciprocal_value reciprocal_size;
	unsigned int offset;	/* object指针的偏移，通过这个偏移可以找到下一个object的地址 */
#ifdef CONFIG_SLUB_CPU_PARTIAL
	/*  per cpu partial objects 的数量 */ 
	unsigned int cpu_partial;
	/* cpuslab partial链表中slab的最大数量 若超过则放入node中的普通partial链表 */
	unsigned int cpu_partial_slabs;
#endif
	struct kmem_cache_order_objects oo;//分配给slab的页帧的阶数（高16位，也就是buddy system的order） 
                                       //slab中的object数量（低16位）

	/* Allocation and freeing of slabs */
	struct kmem_cache_order_objects max;//最大分配数
	struct kmem_cache_order_objects min;//最小分配数
	gfp_t allocflags;	/* 页帧gfp标志 */
	int refcount;		/* 
		一个缓存被引用的次数
    	当创建一个新缓存时，会首先搜索已存在缓存，查看是否存在大小相近，标志位相符的，如果符合，可以复用该已存在缓存 
    	若为-1，则代表不可复用
    */
	void (*ctor)(void *);
	unsigned int inuse;		/* 已经使用的object个数（?） */
	unsigned int align;		/* 对齐用的 */
	unsigned int red_left_pad;	/* Left redzone padding size */
	const char *name;	/* 用于显示的缓存名 */
	struct list_head list;	/* 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];//各个node节点的私有slab，UMA架构的话就只有一个
};

kmem_cache_cpu 定义于 /include/linux/slub_def.h 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * When changing the layout, make sure freelist and tid are still compatible
 * with this_cpu_cmpxchg_double() alignment requirements.
 */
struct kmem_cache_cpu {
	void **freelist;	/* 指向下一个可用的object对象 */
	unsigned long tid;	/* cpu 标识 */
	struct slab *slab;	/* 准备分配的slab */
#ifdef CONFIG_SLUB_CPU_PARTIAL
	struct slab *partial;	/* partial 链表，其中的slab有空闲object */
#endif
	local_lock_t lock;	/* Protects the fields above */
#ifdef CONFIG_SLUB_STATS
	unsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};

kmem_cache_node定义于 /mm/slab.h 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;	/* 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
	unsigned long nr_partial; //partial 链表中 slab 的数量
	struct list_head partial; //当前节点的partial链表
#ifdef CONFIG_SLUB_DEBUG
	atomic_long_t nr_slabs;
	atomic_long_t total_objects;
	struct list_head full;
#endif
#endif

};

从这里也可以看出 slub 相比于 slab ，减少了相当多的管理结构，取消了着色，链表也只保留了partial

slab结构体定义于 /mm/slab.h

早期版本的slab结构体集成在struct page中，在今年一月份的一次commit中将它单独定义了

我阅读的5.17版本的源码中却没有，查看了commit，发现在一月的时候有了这样的改动

image-20221103201437873

1
2
3
4
mm: Remove slab from struct page
All members of struct slab can now be removed from struct page.
This shrinks the definition of struct page by 30 LOC, making
it easier to understand.

image-20221103201511781

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct slab {
	unsigned long __page_flags;

#if defined(CONFIG_SLAB)

	union {
		struct list_head slab_list;
		struct rcu_head rcu_head;
	};
	struct kmem_cache *slab_cache;
	void *freelist;	/* array of free object indexes */
	void *s_mem;	/* first object */
	unsigned int active;

#elif defined(CONFIG_SLUB)

	union {
		struct list_head slab_list;  //slab链表
		struct rcu_head rcu_head; //与RCU机制相关
#ifdef CONFIG_SLUB_CPU_PARTIAL
		struct {
			struct slab *next;
			int slabs;	/* Nr of slabs left */
		};
#endif
	};
	struct kmem_cache *slab_cache;
	/* Double-word boundary */
	void *freelist;		//指向第一个空object（本slab的），这与cache_cpu的freelist不同
	union {
		unsigned long counters;
		struct {
			unsigned inuse:16;	//有多少object正在被使用 
			unsigned objects:15;//object总对象数
			unsigned frozen:1;//是否被冻结（归某个cpu的partial链使用）
		};
	};
	unsigned int __unused;

#elif defined(CONFIG_SLOB) 

	struct list_head slab_list;
	void *__unused_1;
	void freelist;		
	long units;
	unsigned int __unused_2;

#else
#error "Unexpected slab allocator configured"
#endif

	atomic_t __page_refcount;
#ifdef CONFIG_MEMCG
	unsigned long memcg_data;
#endif
};

和以前版本集成在page中差距并不大

slab&object的创建与初始化

1
2
3
4
5
6
7
8
9
10
static struct slab *new_slab(struct kmem_cache *s, gfp_t flags, int node)
{
	if (unlikely(flags & GFP_SLAB_BUG_MASK))
		flags = kmalloc_fix_flags(flags);

	WARN_ON_ONCE(s->ctor && (flags & __GFP_ZERO));

	return allocate_slab(s,
		flags & (GFP_RECLAIM_MASK | GFP_CONSTRAINT_MASK), node);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
static struct slab *allocate_slab(struct kmem_cache *s, gfp_t flags, int node)
{
	struct slab *slab;
	struct kmem_cache_order_objects oo = s->oo;
	gfp_t alloc_gfp;
	void *start, *p, *next;
	int idx;
	bool shuffle;

	flags &= gfp_allowed_mask;

	flags |= s->allocflags;

	/*
	 * Let the initial higher-order allocation fail under memory pressure
	 * so we fall-back to the minimum order allocation.
	 */
	alloc_gfp = (flags | __GFP_NOWARN | __GFP_NORETRY) & ~__GFP_NOFAIL;
	if ((alloc_gfp & __GFP_DIRECT_RECLAIM) && oo_order(oo) > oo_order(s->min))
		alloc_gfp = (alloc_gfp | __GFP_NOMEMALLOC) & ~(__GFP_RECLAIM|__GFP_NOFAIL);

	slab = alloc_slab_page(s, alloc_gfp, node, oo);
	if (unlikely(!slab)) {
		oo = s->min;
		alloc_gfp = flags;
		/*
		 * Allocation may have failed due to fragmentation.
		 * Try a lower order alloc if possible
		 */
		slab = alloc_slab_page(s, alloc_gfp, node, oo);
		if (unlikely(!slab))
			goto out;
		stat(s, ORDER_FALLBACK);
	}

	slab->objects = oo_objects(oo);

	account_slab(slab, oo_order(oo), s, flags);

	slab->slab_cache = s;

	kasan_poison_slab(slab);

	start = slab_address(slab);

	setup_slab_debug(s, slab, start);

	shuffle = shuffle_freelist(s, slab);
	/*
	shuffle_freelist：
    if (slab->objects < 2 || !s->random_seq)
		return false;
    */
	if (!shuffle) {
        //找到第一个object的地址
		start = fixup_red_left(s, start);
		start = setup_object(s, slab, start);
		slab->freelist = start;//freelist指向第一个object
        //从第一个object开始，逐个初始化object链表
		for (idx = 0, p = start; idx < slab->objects - 1; idx++) {
			next = p + s->size;//kmem_cache所存的object size（包含元数据）
			next = setup_object(s, slab, next);
			set_freepointer(s, p, next);
			p = next;
		}
		set_freepointer(s, p, NULL);//最后一个object的指针为NULL
	}

	slab->inuse = slab->objects;
	slab->frozen = 1;

out:
	if (!slab)
		return NULL;

	inc_slabs_node(s, slab_nid(slab), slab->objects);

	return slab;
}

1
2
3
4
5
6
7
8
9
10
11
12
static void *setup_object(struct kmem_cache *s, struct slab *slab,
				void *object)
{
	setup_object_debug(s, slab, object);
	object = kasan_init_slab_obj(s, object);
	if (unlikely(s->ctor)) {
		kasan_unpoison_object_data(s, object);
		s->ctor(object);
		kasan_poison_object_data(s, object);
	}
	return object;
}

这个时候我们就可以画出个大概的图👀

limage-20221125215451571

申请object

slab申请和释放的入口 kmem_cache_alloc 与 kmem_cache_free

如果我们去查看kmalloc源码 会发现其调用链为 kmalloc->__kmalloc -> kmalloc_slab ->slab_alloc ->slab_alloc_node

底层函数都是一样的

1
2
#define allocate_mm()	(kmem_cache_alloc(mm_cachep, GFP_KERNEL))
#define free_mm(mm)	(kmem_cache_free(mm_cachep, (mm)))

kmem_cache_alloc 定义于 /mm/slub.c

1
2
3
4
5
6
7
8
9
void *kmem_cache_alloc(struct kmem_cache *s, gfp_t gfpflags)
{
	void *ret = slab_alloc(s, gfpflags, _RET_IP_, s->object_size);

	trace_kmem_cache_alloc(_RET_IP_, ret, s->object_size,
				s->size, gfpflags);

	return ret;
}

slab_alloc

1
2
3
4
5
static __always_inline void *slab_alloc(struct kmem_cache *s,
		gfp_t gfpflags, unsigned long addr, size_t orig_size)
{
	return slab_alloc_node(s, gfpflags, NUMA_NO_NODE, addr, orig_size);
}

slab_alloc_node (快分配路径)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*
   内联快速路径，以便分配函数（kmalloc、kmem_cache_alloc）将快速路径折叠到它们的函数中。 因此，对于可以在快速路径上得到满足的请求，没有函数调用开销。
 *
   快速路径首先检查是否可以使用无锁freelist。
   如果不是，则调用 __slab_alloc 进行慢分配处理。
 *
   否则我们可以简单地从无锁空闲列表中选择下一个对象。
 */
static __always_inline void *slab_alloc_node(struct kmem_cache *s,
		gfp_t gfpflags, int node, unsigned long addr, size_t orig_size)
{
	void *object;
	struct kmem_cache_cpu *c;
	struct slab *slab;
	unsigned long tid;
	struct obj_cgroup *objcg = NULL;
	bool init = false;
	
	s = slab_pre_alloc_hook(s, &objcg, 1, gfpflags);//预处理的hook函数
	if (!s)
		return NULL;

	object = kfence_alloc(s, orig_size, gfpflags);//优先使用kfence_alloc 分配,貌似与kfence内存池有关,mark
	if (unlikely(object))
		goto out;

redo:
	/*
	 必须通过这个 cpu ptr 读取 kmem_cache cpu 数据。启用抢占。我们可能会在从一个 cpu 区域读取时在 cpus 之间来回切换。只要我们在执行 cmpxchg 时再次使用原始 cpu 就没有关系。
	 *
	 我们必须保证在同一个 cpu 上检索到 tid 和 kmem_cache_cpu。我们首先读取 kmem_cache_cpu 指针并使用它来读取 tid。如果我们在两次读取之间被抢占并切换到另一个 cpu，那没关系，因为这两个 cpu 仍然与同一个 cpu 关联，稍后 cmpxchg 将验证 cpu。
	 */
    
    //获得当前cpu_slab 与 tid
	c = raw_cpu_ptr(s->cpu_slab);
	tid = READ_ONCE(c->tid);

	/*
	 这里使用的 Irqless 对象分配/释放算法取决于获取 cpu_slab 数据的顺序。 tid 应该在 c 上的任何内容之前获取，以保证与前一个 tid 关联的对象和 slab 不会与当前 tid 一起使用。如果我们先获取 tid，对象和 slab 可能与下一个 tid 关联，我们的分配/释放请求将失败。在这种情况下，我们将重试。所以，没问题。
	 */
    //barrier内存屏障 用于保证内存访问按严格的顺序来
	barrier();

	/*
	 每个 cpu 和每个 cpu 队列上的每个操作的事务 ID 是全局唯一的。因此，他们可以保证 cmpxchg_double 出现在正确的处理器上，并且在其间的链表上没有任何操作。
	 */

	object = c->freelist;//获取当前的第一个free object
	slab = c->slab;//获取当前的cpu slab
	/*
	 我们不能在 PREEMPT_RT 上使用无锁快速路径，因为如果慢速路径已采用 local_lock_irqsave()，则它无法防止 irq 处理程序中的快速路径操作。所以我们需要采取使用local_lock的慢速路径。如果有合适的cpu freelist还是比较快的。
	 */
	if (IS_ENABLED(CONFIG_PREEMPT_RT) ||
        //当前slab为空或object为空或node与slab不匹配(也就是当前slab不在当前node中)
        //使用 __slab_alloc 慢分配(从 node cache中分配)        
	    unlikely(!object || !slab || !node_match(slab, node))) {
		object = __slab_alloc(s, gfpflags, node, addr, c);
	} else {
        //slab不为空且object不为空且node与slab匹配
        //获得当前freelist->object的下一个object
		void *next_object = get_freepointer_safe(s, object);
	
		/*
		 cmpxchg 只有在没有额外的操作并且我们在正确的处理器上时才会匹配。 cmpxchg 自动执行以下操作（没有锁定语义！）
         1. 将第一个指针重新定位到当前的每个 cpu 区域。
         2.验证tid和freelist没有变化
         3. 如果没有改变，替换 tid 和 freelist
		 *
		 因为这没有锁语义，所以保护只是防止代码在这个 cpu 上执行 * 而不是 * 被其他 cpu 访问。.
		 */
        //将freelist->object 解链, free-list->object=next_object
		if (unlikely(!this_cpu_cmpxchg_double(
				s->cpu_slab->freelist, s->cpu_slab->tid,
				object, tid,
				next_object, next_tid(tid)))) {

			note_cmpxchg_failure("slab_alloc", s, tid);
			goto redo;
		}
        
		prefetch_freepointer(s, next_object);//数据预取
		stat(s, ALLOC_FASTPATH);//状态保存
	}
	
	maybe_wipe_obj_freeptr(s, object);//将object的指针(指向下一个object的)初始化为0 
	init = slab_want_init_on_alloc(gfpflags, s);

out:
	slab_post_alloc_hook(s, objcg, gfpflags, 1, &object, init);

	return object;
}

__slab_alloc 慢分配路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 ___slab_alloc() 的包装，用于尚未禁用抢占的上下文。 
 通过重新获取每个 cpu 区域指针来补偿可能的 cpu 更改。
 */
static void *__slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
			  unsigned long addr, struct kmem_cache_cpu *c)
{
	void *p;

#ifdef CONFIG_PREEMPT_COUNT
	/*
	 在禁用抢占之前，我们可能已经被抢占并重新安排在不同的 cpu 上。 需要重新加载 cpu 区域指针。
	 */
	c = slub_get_cpu_ptr(s->cpu_slab);//重新获取cpu_slab 
#endif

	p = ___slab_alloc(s, gfpflags, node, addr, c);
#ifdef CONFIG_PREEMPT_COUNT
	slub_put_cpu_ptr(s->cpu_slab);
#endif
	return p;
}

封装的___slab_alloc函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
//进入条件 当前slab为空或object为空或node与slab不匹配(也就是当前slab不在当前node中)
static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
			  unsigned long addr, struct kmem_cache_cpu *c)
{
	void *freelist;
	struct slab *slab;
	unsigned long flags;

	stat(s, ALLOC_SLOWPATH);

reread_slab:

	slab = READ_ONCE(c->slab);
	if (!slab) {//没有可用的slab 需要申请新slab
		/*
		 如果node不在线或者没有正常的内存，忽略node的约束限制
		 */
		if (unlikely(node != NUMA_NO_NODE &&
			     !node_isset(node, slab_nodes)))
			node = NUMA_NO_NODE;
		goto new_slab;
	}
redo:

	if (unlikely(!node_match(slab, node))) {
        //node与当前slab不匹配
		/*
		 * same as above but node_match() being false already
		 * implies node != NUMA_NO_NODE
		 */
		if (!node_isset(node, slab_nodes)) {
			node = NUMA_NO_NODE;
			goto redo;
		} else {
			stat(s, ALLOC_NODE_MISMATCH);
			goto deactivate_slab;// 移除 当前slab
		}
	}

    //以下为node与当前slab匹配
    
	/*
	 按理说，我们应该搜索 PFMEMALLOC 的 slab 页面，但现在，当页面离开 per-cpu 分配器时，我们正在丢失 pfmemalloc 信息
	 */
	if (unlikely(!pfmemalloc_match(slab, gfpflags)))
		goto deactivate_slab; //如果当前slAB是PF_MEMALLOC,调用deactivate_slab

	/* 必须再次检查 c->slab 以防我们被抢占并且它发生了变化 */
	local_lock_irqsave(&s->cpu_slab->lock, flags);
	if (unlikely(slab != c->slab)) { //检查slab是否被抢占
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		goto reread_slab;
	}
	freelist = c->freelist;//获取当前cpu_slab的freelist 
	if (freelist)
		goto load_freelist;// 这里正常来说应该是空(?),不是很懂

	freelist = get_freelist(s, slab);//重新获取

	if (!freelist) {
        //如果freelist->object为空,slab置空 并去新建slab
		c->slab = NULL;
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);//该slab解锁
		stat(s, DEACTIVATE_BYPASS);
		goto new_slab;
	}

	stat(s, ALLOC_REFILL);

load_freelist:
	//返回freelist的object,并让freelist指向下一个object
	lockdep_assert_held(this_cpu_ptr(&s->cpu_slab->lock));

	/*
	 freelist 是指向要使用的object list。
	 slab 是指向从中获取object的slab。 
	 必须冻结该 slab 才能使每个 cpu 分配正常工作。
	 */
	VM_BUG_ON(!c->slab->frozen);
	c->freelist = get_freepointer(s, freelist);
	c->tid = next_tid(c->tid);
	local_unlock_irqrestore(&s->cpu_slab->lock, flags);
	return freelist;

deactivate_slab:
	//移除当前slab
	local_lock_irqsave(&s->cpu_slab->lock, flags);
	if (slab != c->slab) {
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		goto reread_slab;
	}
	freelist = c->freelist;
	c->slab = NULL;
	c->freelist = NULL;
	local_unlock_irqrestore(&s->cpu_slab->lock, flags);
	deactivate_slab(s, slab, freelist);

new_slab:
	//获取新的slab
	if (slub_percpu_partial(c)) {
		local_lock_irqsave(&s->cpu_slab->lock, flags);
		if (unlikely(c->slab)) {
			local_unlock_irqrestore(&s->cpu_slab->lock, flags);
			goto reread_slab;
		}
		if (unlikely(!slub_percpu_partial(c))) {
			local_unlock_irqrestore(&s->cpu_slab->lock, flags);
			/* we were preempted and partial list got empty */
			goto new_objects;
		}

		slab = c->slab = slub_percpu_partial(c);//从partial链表中获取slab
		slub_set_percpu_partial(c, slab);
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		stat(s, CPU_PARTIAL_ALLOC);//记录
		goto redo;
	}

new_objects:
	//尝试从kmem_cache_node的partial链表中分配page
	freelist = get_partial(s, gfpflags, node, &slab);
	if (freelist)
		goto check_new_slab;

	slub_put_cpu_ptr(s->cpu_slab);
	slab = new_slab(s, gfpflags, node);
	c = slub_get_cpu_ptr(s->cpu_slab);

	if (unlikely(!slab)) {
		slab_out_of_memory(s, gfpflags, node);//调用buddy system，分配slab
		return NULL;
	}

	/*
	 * No other reference to the slab yet so we can
	 * muck around with it freely without cmpxchg
	 */
	freelist = slab->freelist;
	slab->freelist = NULL;

	stat(s, ALLOC_SLAB);

check_new_slab:
	//检查从node中获取的slab 
	if (kmem_cache_debug(s)) {
		if (!alloc_debug_processing(s, slab, freelist, addr)) {
			/* Slab failed checks. Next slab needed */
			goto new_slab;
		} else {
			/*
			 * For debug case, we don't load freelist so that all
			 * allocations go through alloc_debug_processing()
			 */
			goto return_single;
		}
	}

	if (unlikely(!pfmemalloc_match(slab, gfpflags)))
		/*
		 * For !pfmemalloc_match() case we don't load freelist so that
		 * we don't make further mismatched allocations easier.
		 */
		goto return_single;

retry_load_slab:

	local_lock_irqsave(&s->cpu_slab->lock, flags);
	if (unlikely(c->slab)) {
		void *flush_freelist = c->freelist;
		struct slab *flush_slab = c->slab;

		c->slab = NULL;
		c->freelist = NULL;
		c->tid = next_tid(c->tid);

		local_unlock_irqrestore(&s->cpu_slab->lock, flags);

		deactivate_slab(s, flush_slab, flush_freelist);

		stat(s, CPUSLAB_FLUSH);

		goto retry_load_slab;
	}
	c->slab = slab;

	goto load_freelist;

return_single:

	deactivate_slab(s, slab, get_freepointer(s, freelist));
	return freelist;
}

deactivate_slab()主要是将slab放回node,解冻该slab,并根据情况判断是否直接释放该slab放回buddy system

释放object

接口为kmem_cache_free 函数

1
2
3
4
5
6
7
8
void kmem_cache_free(struct kmem_cache *s, void *x)
{
	s = cache_from_obj(s, x);
	if (!s)
		return;
	trace_kmem_cache_free(_RET_IP_, x, s->name);
	slab_free(s, virt_to_slab(x), x, NULL, 1, _RET_IP_);
}

如果是kree的话

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void kfree(const void *x)
{
	struct folio *folio;
	struct slab *slab;
	void *object = (void *)x;

	trace_kfree(_RET_IP_, x);

	if (unlikely(ZERO_OR_NULL_PTR(x)))
		return;

	folio = virt_to_folio(x);//通过虚拟地址找到对应的物理页的folio
    /*
    folio 只是封装了 struct page 的一个容器，确保这个 page 不会是一个 tail page。因此，它可以用来以 single page 或更大的 page 为单位来指代内存区域。
     * page_folio - Converts from page to folio.
 * @p: The page.
 *
 * Every page is part of a folio.  This function cannot be called on a
 * NULL pointer.
 *
 * Context: No reference, nor lock is required on @page.  If the caller
 * does not hold a reference, this call may race with a folio split, so
 * it should re-check the folio still contains this page after gaining
 * a reference on the folio.
 * Return: The folio which contains this page.
    */
	if (unlikely(!folio_test_slab(folio))) {
		free_large_kmalloc(folio, object);
		return;
	}
	slab = folio_slab(folio);
	slab_free(slab->slab_cache, slab, object, NULL, 1, _RET_IP_);
}
EXPORT_SYMBOL(kfree);

slab_free 封装了do_slab_free

1
2
3
4
5
6
7
8
9
10
11
12
//要释放的object就是参数 void * head
static __always_inline void slab_free(struct kmem_cache *s, struct slab *slab,
				      void *head, void *tail, int cnt,
				      unsigned long addr)
{
	/*
	 * With KASAN enabled slab_free_freelist_hook modifies the freelist
	 * to remove objects, whose reuse must be delayed.
	 */
	if (slab_free_freelist_hook(s, &head, &tail, &cnt))
		do_slab_free(s, slab, head, tail, cnt, addr);
}

do_slab_free (快速路径)

从这里就可以看出slab分配是 LIFO的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*
 * 带强制内联的快速路径可生成 kfree 和 kmem_cache_free，无需额外的函数调用即可执行快速路径释放。
  *
  * 仅当我们释放到该处理器的当前 cpu slab 时，fastpath 才有可能。 如果我们之前刚刚分配了项目，通常就是这种情况。
  *
  * 如果无法使用快速路径，则退回到 __slab_free，我们将在其中处理各种特殊处理。
  *
  通过指定 head 和 tail ptr，加上对象计数 (cnt)，可以批量释放具有多个对象（全部指向同一个 slab）的自由列表。 设置尾指针指示的批量释放。
 */
static __always_inline void do_slab_free(struct kmem_cache *s,
				struct slab *slab, void *head, void *tail,
				int cnt, unsigned long addr)
{
	void *tail_obj = tail ? : head; //object 为 head， 前面slab_free传入的tail为null，那么tail_obj记录的就是待插入的object
	struct kmem_cache_cpu *c;
	unsigned long tid;

	/* memcg_slab_free_hook() is already called for bulk free. */
	if (!tail)//
		memcg_slab_free_hook(s, &head, 1);
redo:
	/*
	 * 确定当前每个 cpu slab 的 cpus。
* cpu 之后可能会发生变化。 然而，这并不重要，因为数据是通过该指针检索的。 如果我们在 cmpxchg 期间在同一个 cpu 上，那么 free 将会成功。
	 */
	c = raw_cpu_ptr(s->cpu_slab);//获取当前cpu_cache
	tid = READ_ONCE(c->tid);//获取tid

	/* Same with comment on barrier() in slab_alloc_node() */
	barrier();//内存屏障 用于保证顺序性

	if (likely(slab == c->slab)) {//当前释放的slab就是cpu_cache->slab
#ifndef CONFIG_PREEMPT_RT
		void **freelist = READ_ONCE(c->freelist);//read once 
        // 也就是读取了 *(cpu_cache->freelist)

		set_freepointer(s, tail_obj, freelist);//将释放的object的指针指向freelist 
		// freelist指向当前待释放的object
		if (unlikely(!this_cpu_cmpxchg_double(
				s->cpu_slab->freelist, s->cpu_slab->tid,
				freelist, tid,
				head, next_tid(tid)))) {

			note_cmpxchg_failure("slab_free", s, tid);
			goto redo;
		}
#else /* CONFIG_PREEMPT_RT */
		/*
		 我们不能在 PREEMPT_RT 上使用无锁快速路径，因为如果慢速路径已经采用了 local_lock_irqsave()，那么在 irq 处理程序中它不会受到快速路径操作的保护。 所以我们需要取local_lock。 我们不应该简单地遵从 __slab_free() 因为它根本不会使用 cpu freelist。
		 */
		void **freelist;

		local_lock(&s->cpu_slab->lock);
		c = this_cpu_ptr(s->cpu_slab);//获取当前cpu_cache
		if (unlikely(slab != c->slab)) {
			local_unlock(&s->cpu_slab->lock);
			goto redo;
		}
		tid = c->tid;
		freelist = c->freelist;//cpu_cache->freelist

		set_freepointer(s, tail_obj, freelist);//将释放的object的尾指针指向freelist 
		c->freelist = head;//设置freelist为当前objec
		c->tid = next_tid(tid);

		local_unlock(&s->cpu_slab->lock);
#endif
		stat(s, FREE_FASTPATH);
	} else
        //不是本cpu_cache的 ,进入慢分配
		__slab_free(s, slab, head, tail_obj, cnt, addr);

}

__slab_free (慢分配函数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
*
 * Slow path handling. This may still be called frequently since objects
 * have a longer lifetime than the cpu slabs in most processing loads.
 *
 * So we still attempt to reduce cache line usage. Just take the slab
 * lock and free the item. If there is no additional partial slab
 * handling required then we can return immediately.
 */
static void __slab_free(struct kmem_cache *s, struct slab *slab,
			void *head, void *tail, int cnt,
			unsigned long addr)

{
	void *prior;
	int was_frozen;
	struct slab new;
	unsigned long counters;
	struct kmem_cache_node *n = NULL;
	unsigned long flags;

	stat(s, FREE_SLOWPATH);

	if (kfence_free(head))
		return;

	if (kmem_cache_debug(s) &&
	    !free_debug_processing(s, slab, head, tail, cnt, addr))
		return;

	do {
		if (unlikely(n)) {
			spin_unlock_irqrestore(&n->list_lock, flags);
			n = NULL;
		}
		prior = slab->freelist;
		counters = slab->counters;
		set_freepointer(s, tail, prior);
		new.counters = counters;
		was_frozen = new.frozen;
		new.inuse -= cnt;
		if ((!new.inuse || !prior) && !was_frozen) {

			if (kmem_cache_has_cpu_partial(s) && !prior) {

				/*
				 * Slab was on no list before and will be
				 * partially empty
				 * We can defer the list move and instead
				 * freeze it.
				 */
				new.frozen = 1;

			} else { /* Needs to be taken off a list */

				n = get_node(s, slab_nid(slab));
				/*
				 * Speculatively acquire the list_lock.
				 * If the cmpxchg does not succeed then we may
				 * drop the list_lock without any processing.
				 *
				 * Otherwise the list_lock will synchronize with
				 * other processors updating the list of slabs.
				 */
				spin_lock_irqsave(&n->list_lock, flags);

			}
		}

	} while (!cmpxchg_double_slab(s, slab,
		prior, counters,
		head, new.counters,
		"__slab_free"));

	if (likely(!n)) {

		if (likely(was_frozen)) {
			/*
			 * The list lock was not taken therefore no list
			 * activity can be necessary.
			 */
			stat(s, FREE_FROZEN);
		} else if (new.frozen) {
			/*
			 * If we just froze the slab then put it onto the
			 * per cpu partial list.
			 */
			put_cpu_partial(s, slab, 1);
			stat(s, CPU_PARTIAL_FREE);
		}

		return;
	}

	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial))
		goto slab_empty;

	/*
	 * Objects left in the slab. If it was not on the partial list before
	 * then add it.
	 */
	if (!kmem_cache_has_cpu_partial(s) && unlikely(!prior)) {
		remove_full(s, n, slab);
		add_partial(n, slab, DEACTIVATE_TO_TAIL);
		stat(s, FREE_ADD_PARTIAL);
	}
	spin_unlock_irqrestore(&n->list_lock, flags);
	return;

slab_empty:
	if (prior) {
		/*
		 * Slab on the partial list.
		 */
		remove_partial(n, slab);
		stat(s, FREE_REMOVE_PARTIAL);
	} else {
		/* Slab must be on the full list */
		remove_full(s, n, slab);
	}

	spin_unlock_irqrestore(&n->list_lock, flags);
	stat(s, FREE_SLAB);
	discard_slab(s, slab);
}

参考资料

https://zhuanlan.zhihu.com/p/490588193

https://evilpan.com/2020/03/21/linux-slab/

https://cloud.tencent.com/developer/article/1622988

https://bbs.pediy.com/thread-269149.htm#msg_header_h3_18

https://www.cnblogs.com/tolimit/p/4654109.html

https://blog.csdn.net/lukuen/article/details/6935068?spm=1001.2014.3001.5506

https://www.51cto.com/article/412757.html

http://www.wowotech.net/memory_management/426.html

https://www.cnblogs.com/sky-heaven/p/16527927.html kfence相关