Linux_Kernel_SLUB分配器

SLUB算法

之前我们讲解了伙伴系统，他的层次在于分配以page为单位的页面，但在平时我们程序使用的这么大个单位的页面机会很少，我们更倾向于分配小块例如0x2e0的块,而此时如果再次调用伙伴系统的分配就有点杀鸡用牛刀的感觉，所以此时Linux内核引入小块的分配器，也就是

slab allocator

他存在着三种实现形式：slab,slob,slub

  • slab是较为古早的分配算法，其中涉及到堆块着色的问题，效率不高且较为复杂

  • slob一般用于嵌入式场景，较为轻便

  • slub目前较为主流的分配算法，因此本文主要是探究他

1. 数据结构们

struct slab

首先就是我们比较主要的数据结构slab，他曾经是被嵌入在page当中，但是目前最新内核版本6.4，他被作为一个独立的数据结构进行表示，当然实际上也是复用了page的结构体，具体如下：

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
/* Reuses the bits in struct page */
struct slab {
	unsigned long __page_flags;

#if defined(CONFIG_SLAB)
...
    /*
    this zone is been used by slab allocator which use the slab approach
    */
...
#elif defined(CONFIG_SLUB)

	struct kmem_cache *slab_cache;
	union {
		struct {
			union {
				struct list_head slab_list; 	//slab头
#ifdef CONFIG_SLUB_CPU_PARTIAL
				struct {
					struct slab *next; 			//slab链表
					int slabs;	/* Nr of slabs left */
				};
#endif
			};
			/* Double-word boundary */
			void *freelist;		/* first free object */
			union {
				unsigned long counters;
				struct {
					unsigned inuse:16;
					unsigned objects:15;
					unsigned frozen:1;
				};
			};
		};
		struct rcu_head rcu_head;
	};
	unsigned int __unused;

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

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

上面我们已经知道slab就是复用的page结构体，我们的page结构体是用来表示物理内存中的一个内存页，我们可以通过一个page结构体找到物理内存页的页框号，同样的，当我们用slab来复用page结构体的时候，我们也可以通过他来得到物理内存页的页框号，下面是其中的一些字段解释：

  1. __page_flags字段:他用来标识页面的相关信息
  2. slab_cache字段:他是一个kmem_cache类型的指针,该结构体我们下面讲解
  3. free_list:该字段指向第一个空闲的object,耗尽时为NULL
  4. slab_list:连接多个slab的双向链表
  5. inuse:已经被使用的object数
  6. objects:总共的object数
  7. frozen:标志是否（1/0）被冻结，也就是是否被cpu.slab绑定

下面的这张图就是关于目前的slab结构体的相关结构，我们慢慢来充实该图

其中freelist字段指向的块就是我们先前page页所代表的页框中的某块。

struct kmem_cache

要管理小块的分配，单单一个复用page结构的slab还不够，所以这里引入我们的管理者kmem_cache，如下

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
/*
 * Slab cache management.
 */
struct kmem_cache {
#ifndef CONFIG_SLUB_TINY
    /* 每个CPU所拥有的缓存slabs */
	struct kmem_cache_cpu __percpu *cpu_slab;
#endif
	/* Used for retrieving partial slabs, etc. */
	slab_flags_t flags;
	unsigned long min_partial;
	unsigned int size;	/* 一个包含元数据object的大小 */
	unsigned int object_size;/* 不包含元数据object的大小 */
	struct reciprocal_value reciprocal_size;
	unsigned int offset;	/* slab上空闲指针在object上的偏移 */
#ifdef CONFIG_SLUB_CPU_PARTIAL
	/* 需要保留的per cpu partial objects的数目 */
	unsigned int cpu_partial;
	/* 需要保留的per cpu partial slabs的数目 */
	unsigned int cpu_partial_slabs;
#endif
	struct kmem_cache_order_objects oo;

	/* Allocation and freeing of slabs */
	struct kmem_cache_order_objects min;
	gfp_t allocflags;	/* 每次分配时的gfp */
	int refcount;		/* 用于销毁slab_cache的引用计数器 */
	void (*ctor)(void *);
	unsigned int inuse;		/* 元数据的偏移 */
	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_GENERIC
	struct kasan_cache kasan_info;
#endif

#ifdef CONFIG_HARDENED_USERCOPY
	unsigned int useroffset;	/* Usercopy region offset */
	unsigned int usersize;		/* Usercopy region size */
#endif

	struct kmem_cache_node *node[MAX_NUMNODES];
};

其中最主要的两个字段如下：

struct kmem_cache_cpu

  • cpu_cache: 类型为kmem_cache_cpu指针，一个cpu的空闲对象缓存，其大致定义如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * 更改布局时，请确保 freelist 和 tid 仍然符合 this_cpu_cmpxchg_double() 对齐要求
 */
struct kmem_cache_cpu {
	void **freelist;	/* 指向下一个空闲object的指针的指针 */
	unsigned long tid;	/* 全局唯一的事务id */
	struct slab *slab;	/* 我们分配到的slab */
#ifdef CONFIG_SLUB_CPU_PARTIAL
	struct slab *partial;	/* Partially allocated frozen slabs */
#endif
	local_lock_t lock;	/* Protects the fields above */
#ifdef CONFIG_SLUB_STATS
	unsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};

其中有下面几点需要注意：

  1. freelist：指向下一个分配对象的指针
  2. slab：被当前使用来分配内存的slab
  3. partial：链表上为仍有一定空闲object的slab

其中slab->freelist在被kmem_cache_cpu使用时为NULL，是个无效值，只有他在处于partial链表才会有效

struct kmem_cache_node

  • node[MAX_NUMNODES]:他是一个数组指针，其中每一个元素都指向一个kmem_cache_node，他是NUMA架构中每个node节点的缓存，如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * The slab lists for all objects.
 */
struct kmem_cache_node {
#ifdef CONFIG_SLAB
...
    /* for slab method */
...
#endif

#ifdef CONFIG_SLUB
	spinlock_t list_lock; 	//列表自旋锁
	unsigned long nr_partial; 	//半满slab的个数
	struct list_head partial; 	//半满slab的头
#ifdef CONFIG_SLUB_DEBUG
	atomic_long_t nr_slabs; 	//所有slab数量
	atomic_long_t total_objects; 	//总共的object数量
	struct list_head full; //满slab的头
#endif
#endif

};

我们在初始化分配器的时候，会定义一个全局变量kmalloc_caches，如下：

1
2
3
struct kmem_cache *kmalloc_caches[NR_KMALLOC_TYPES][KMALLOC_SHIFT_HIGH + 1] __ro_after_init =
{ /* initialization for https://bugs.llvm.org/show_bug.cgi?id=42570 */ };
EXPORT_SYMBOL(kmalloc_caches);

其中他的行为以下枚举类型

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
/*
 * Whenever changing this, take care of that kmalloc_type() and
 * create_kmalloc_caches() still work as intended.
 *
 * KMALLOC_NORMAL can contain only unaccounted objects whereas KMALLOC_CGROUP
 * is for accounted but unreclaimable and non-dma objects. All the other
 * kmem caches can have both accounted and unaccounted objects.
 */
enum kmalloc_cache_type {
	KMALLOC_NORMAL = 0,
#ifndef CONFIG_ZONE_DMA
	KMALLOC_DMA = KMALLOC_NORMAL,
#endif
#ifndef CONFIG_MEMCG_KMEM
	KMALLOC_CGROUP = KMALLOC_NORMAL,
#endif
#ifdef CONFIG_SLUB_TINY
	KMALLOC_RECLAIM = KMALLOC_NORMAL,
#else
	KMALLOC_RECLAIM,
#endif
#ifdef CONFIG_ZONE_DMA
	KMALLOC_DMA,
#endif
#ifdef CONFIG_MEMCG_KMEM
	KMALLOC_CGROUP,
#endif
	NR_KMALLOC_TYPES
};

他的值主要靠编译时期的配置来决定管理不同内存段的slab，例如64位的dma,normal等等。

然后我们的列主要是以下部分

1
2
#define KMALLOC_SHIFT_HIGH	(PAGE_SHIFT + 1)
#define PAGE_SHIFT	12

所以说我们的kmalloc_caches共有14列，行数需通过配置来决定

下面我们来完善上面的图

2.分配过程

首先我们拿__kmalloc函数来分析，他的实现如下，调用另一个函数__do_kmalloc_node

1
2
3
4
void *__kmalloc(size_t size, gfp_t flags)
{
	return __do_kmalloc_node(size, flags, NUMA_NO_NODE, _RET_IP_);
}

之后该函数又调用其他函数,我超上面白写了，调用链如下：

1
2
3
4
5
6
7
__kmalloc
	__do_kmalloc_node 	//在这一部分会通过传递的标志和大小来从kmalloc_caches数组中传入合适的kmem_cache数据结构
		__kmem_cache_alloc_node
			slab_alloc_node
				__slab_alloc_node 	//若cpu_slab->freelist非空，则直接分配，到这里停止
					__slab_alloc
						___slab_alloc

下面我们来首先分析slab_alloc_node函数，如下：

slab_alloc_node

一切尽在注释中:happy:

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
/*
 * 内联快速路径，以便分配函数（kmalloc、kmem_cache_alloc）将快速路径折叠到其函数中。
 * 因此，对于可以在快速路径上满足的请求，没有函数调用开销
 * 快速路径的工作原理是首先检查是否可以使用无锁空闲列表。
 * 如果没有，则调用 __slab_alloc 来进行缓慢的处理。
 * 否则，我们可以简单地从无锁空闲列表中选择下一个对象
 */
static __fastpath_inline void *slab_alloc_node(struct kmem_cache *s, struct list_lru *lru,
		gfp_t gfpflags, int node, unsigned long addr, size_t orig_size)
{
	void *object;
	struct obj_cgroup *objcg = NULL;
	bool init = false;

	s = slab_pre_alloc_hook(s, lru, &objcg, 1, gfpflags);
	if (!s)
		return NULL;
/**
 * kfence_alloc() - allocate a KFENCE object with a low probability
 * @s:     struct kmem_cache with object requirements
 * @size:  exact size of the object to allocate (can be less than @s->size
 *         e.g. for kmalloc caches)
 * @flags: GFP flags
 *
 * Return:
 * * NULL     - 若为空，则我们接着进行常规分配,
 * * non-NULL - 若不为空，则返回一个 KFENCE object.
 *
 * kfence_alloc() 应该插入到堆分配快速路径中，
 * 允许它使用静态分支以较低的概率透明地返回 KFENCE 分配的对象
 * （概率由 kfence.sample_interval 启动参数控制）.
 */
	object = kfence_alloc(s, orig_size, gfpflags);
	if (unlikely(object))
		goto out;

	object = __slab_alloc_node(s, gfpflags, node, addr, orig_size);

/*
 * If the object has been wiped upon free, 确保object的freelist指针被清0来充分初始化.
 */
	maybe_wipe_obj_freeptr(s, object);
	init = slab_want_init_on_alloc(gfpflags, s);

out:
	/*
	 * When init equals 'true', like for kzalloc() family, only
	 * @orig_size bytes might be zeroed instead of s->object_size
	 */
	slab_post_alloc_hook(s, objcg, gfpflags, 1, &object, init, orig_size);

	return object;
}

上面注释可以看到，首先会调用kfence_alloc进行检测，若通过则进如核心分配函数，否则直接转到out，接着转到我们的核心函数__slab_alloc_node,通过他获取object的之后，再调用maybe_wipe_obj_freeptr,他把所获得的object的freelist指针清空来进行初始化，然后调用slab_want_init_on_alloc函数，他通过判断标志位是否含有__GFP_ZERO来进行赋0值的清空操作。

__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
static __always_inline void *__slab_alloc_node(struct kmem_cache *s,
		gfp_t gfpflags, int node, unsigned long addr, size_t orig_size)
{
	struct kmem_cache_cpu *c;
	struct slab *slab;
	unsigned long tid;
	void *object;

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

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

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

	object = c->freelist;
	slab = c->slab;

	if (!USE_LOCKLESS_FAST_PATH() ||
	    unlikely(!object || !slab || !node_match(slab, node))) { 	//如果object和slab为空或者slab与node不匹配
		object = __slab_alloc(s, gfpflags, node, addr, c, orig_size); //分配新slab然后获取其中的object
	} else {
		void *next_object = get_freepointer_safe(s, object); 	//得到当前object连接的下一个free object

		/*
		 * 仅当没有其他操作并且我们使用正确的处理器时，cmpxchg 才会匹配。
          * cmpxchg 以原子方式执行以下操作（没有锁语义！） 
          * 1. 将第一个指针重新定位到当前每个 cpu 区域。 
          * 2. 验证 tid 和 freelist 是否未更改 
          * 3. 如果未更改，则替换 tid 和 freelist 由于这没有锁定语义，
          * 因此只能防止在该 cpu 上执行的代码，s而不能防止其他 cpu 的访问。
		 */
		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);  	//若发生了改变，则证明我们现在换了个cpu运行，因此重新在当前cpu分配object
			goto redo;
		}
		prefetch_freepointer(s, next_object); 	//若没改变，则设置freepointer指向分配object的下一个object
		stat(s, ALLOC_FASTPATH);
	}

	return object;
}

该函数若是在较为理想的情况下会直接从cpu_slab的freelist进行分配,否则会通过__slab_alloc分配新的slab

__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
/*
 * ___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, unsigned int orig_size)
{
	void *p;

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

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

上面函数也没干啥，就是重新获取cpu_slab用来防止cpu切换，这里调用___slab_alloc

___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
/*
 * 慢路径. 无锁空闲列表为空或者我们需要执行调试职责.
 *
 * 如果新对象已释放到常规空闲列表，处理速度仍然非常快。
 * 在这种情况下，我们只需将常规空闲列表接管为无锁空闲列表，然后取消常规空闲列表。
 *
 * 如果这不起作用，那么我们就回到partial列表。
 * 我们将空闲列表的第一个元素作为现在要分配的对象，并将空闲列表的其余部分移动到无锁空闲列表。
 *
 * 如果我们无法从部分slab列表中获取新的slab，那么我们需要分配一个新的slab。 
 * 这是最慢的路径，因为它涉及对页面分配器的调用和新slab的设置。
 *
 * 当我们知道抢占已被禁用时要使用的 __slab_alloc 版本（批量分配就是这种情况）。
 */
static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
			  unsigned long addr, struct kmem_cache_cpu *c, unsigned int orig_size)
{
	void *freelist;
	struct slab *slab;
	unsigned long flags;
	struct partial_context pc;

	stat(s, ALLOC_SLOWPATH);

	...
        
}

下面我们将一步一步解析该部分源码，内核设计他时刚好自行将其分了块，我们就根据这些块来讲解：

:one: reread_slab

1
2
3
4
5
6
7
8
9
10
11
12
reread_slab:

	slab = READ_ONCE(c->slab); 			//首先再次获取依次目前cpu上的slab指针
	if (!slab) {
		/*
		 * 如果节点不在线或者没有正常内存，则忽略节点约束
		 */
		if (unlikely(node != NUMA_NO_NODE &&
			     !node_isset(node, slab_nodes)))
			node = NUMA_NO_NODE;
		goto new_slab; 					//跳转到new_slab标签
	}

:two:redo

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
/* 
 * 运行到这里说明在上面获取cpu的slab时他不为空，
 * 这里我目前推测是因为切换cpu后重新或取的当前struct kmem_cache_cpu下的slab
 */
redo:

	if (unlikely(!node_match(slab, node))) {
		/*
		 * 与上面相同，但 node_match() 为 false 已经意味着 node != NUMA_NO_NODE
		 */
		if (!node_isset(node, slab_nodes)) { 	//查看是否与对应标识为匹配，若匹配则设置node = NUMA_NO_NODE
			node = NUMA_NO_NODE;
		} else { 							//否则跳转到下一标签
			stat(s, ALLOC_NODE_MISMATCH);
			goto deactivate_slab;
		}
	}

	/*
	 * 按理说，我们应该搜索 PFMEMALLOC 的页面，
	 * 但现在，当页面离开per_cpu 分配器时，我们正在丢失 pfmemalloc 信息
	 */
	if (unlikely(!pfmemalloc_match(slab, gfpflags)))
		goto deactivate_slab;

	/* 必须再次检查 c->slab 以防我们被抢占并且它发生了变化 */
	local_lock_irqsave(&s->cpu_slab->lock, flags); 	//锁住了，免得切换cpu
	if (unlikely(slab != c->slab)) {
		local_unlock_irqrestore(&s->cpu_slab->lock, flags); 	//若发现切换了，则我们解锁了重新回到reread_slab标签
		goto reread_slab;
	}
	freelist = c->freelist; 	//到这里说明还没切换cpu，所以这里获取cpu的freelist
	if (freelist) 	//若存在per_cpu->freelist，则跳转到load_freelist标签
		goto load_freelist;

	freelist = get_freelist(s, slab); 	//否则调用该函数，传入kmem_cache和slab来获取slab->freelist

	if (!freelist) { 		//若仍获取不到空闲freelist
		c->slab = NULL; 	
		c->tid = next_tid(c->tid);
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		stat(s, DEACTIVATE_BYPASS);
		goto new_slab; 		//跳转到new_slab标签
	}

	stat(s, ALLOC_REFILL);

这里的一个get_freelist函数是将当前cpu的slab->free_list返回，或者停用该slab

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
#ifndef CONFIG_SLUB_TINY
/*
 * 检查slab->freelist，并将空闲列表转移到per_CPU的空闲列表或停用该slab。
 *
 * 如果返回值不为 NULL，slab 仍会被冻结。
 *
 * 如果此函数返回 NULL，则该slab已被解冻
 */
static inline void *get_freelist(struct kmem_cache *s, struct slab *slab)
{
	struct slab new;
	unsigned long counters;
	void *freelist;

	lockdep_assert_held(this_cpu_ptr(&s->cpu_slab->lock)); 	

	do {
		freelist = slab->freelist;
		counters = slab->counters;

		new.counters = counters;
		VM_BUG_ON(!new.frozen);

		new.inuse = slab->objects;
		new.frozen = freelist != NULL;

	} while (!__cmpxchg_double_slab(s, slab,
		freelist, counters,
		NULL, new.counters,
		"get_freelist"));

	return freelist;
}

:three:load_freelist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
load_freelist:

	lockdep_assert_held(this_cpu_ptr(&s->cpu_slab->lock));

	/*
	 * freelist指向要使用的对象列表。 
	 * slab指向从中获取对象的slab。 
	 * 该slab 必须被冻结才能让per_CPU 分配工作。
	 */
	VM_BUG_ON(!c->slab->frozen);
	c->freelist = get_freepointer(s, freelist); 		//获取freelist指向的object的下一块object，并且设置他
	c->tid = next_tid(c->tid); 							//设置tid
	local_unlock_irqrestore(&s->cpu_slab->lock, flags); 	
	return freelist;

这里的get_freepointer函数最终会调用下面这个freelist_ptr，且参数为本kmem_cache和当前object指向的下一个object的地址，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
 * 返回空闲列表指针 (ptr)。
 * 通过强化，可以通过指针所在地址和每个缓存随机数的异或来进行混淆。
 */
static inline void *freelist_ptr(const struct kmem_cache *s, void *ptr,
				 unsigned long ptr_addr)
{
#ifdef CONFIG_SLAB_FREELIST_HARDENED
	/*
	 * 当 CONFIG_KASAN_SW/HW_TAGS 启用时，ptr_addr 可能会被标记.
     * 通常，这不会导致任何问题，因为 set_freepointer() 和 get_freepointer() 都是使用具有相同标记的指针调用的。
     * 但是，CONFIG_SLUB_DEBUG 代码存在一些问题。 
     * 例如，当 __free_slub() 迭代缓存中的对象时，它将未标记的指针传递给 check_object()。 
     * check_object() 又用一个未标记的指针调用 get_freepointer()，这会导致 freepointer 被错误地恢复。
	 */
	return (void *)((unsigned long)ptr ^ s->random ^
			swab((unsigned long)kasan_reset_tag((void *)ptr_addr)));
#else
	return ptr;
#endif
}

一般如果我们运行到这里就可以返回一个空闲object了，但是本函数代码还并未结束

:four:deactivate_slab

1
2
3
4
5
6
7
8
9
10
11
12
13
14
deactivate_slab:

	local_lock_irqsave(&s->cpu_slab->lock, flags);
	if (slab != c->slab) {     //同步检查
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		goto reread_slab; 	//若中间切换了CPU，则跳转到reread_slab
	}
	freelist = c->freelist; 	 //保存第一个object指针
	c->slab = NULL; 			//设置当前kmem_cache_cpu字段为NULL，且tid转换
	c->freelist = NULL;
	c->tid = next_tid(c->tid);
	local_unlock_irqrestore(&s->cpu_slab->lock, flags);
	deactivate_slab(s, slab, freelist); 	//激活该slab

下面介绍以下激活函数

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
/*
 * 完成移除 cpu slab。 
 * 将cpu的空闲列表与slab的空闲列表合并，解冻slab并将其放入正确的列表中。 
 * 假设该slab已经被调用者安全地从kmem_cache_cpu中取出。
 */
static void deactivate_slab(struct kmem_cache *s, struct slab *slab,
			    void *freelist)
{
	enum slab_modes { M_NONE, M_PARTIAL, M_FREE, M_FULL_NOLIST };
	struct kmem_cache_node *n = get_node(s, slab_nid(slab));
	int free_delta = 0;
	enum slab_modes mode = M_NONE;
	void *nextfree, *freelist_iter, *freelist_tail;
	int tail = DEACTIVATE_TO_HEAD;
	unsigned long flags = 0;
	struct slab new;
	struct slab old;

	if (slab->freelist) {
		stat(s, DEACTIVATE_REMOTE_FREES);
		tail = DEACTIVATE_TO_TAIL;
	}

	/*
	 * 第一阶段：将cpu的freelist上的对象统计为free_delta，并记住freelist_tail中的最后一个对象，以供后续拼接。
	 */
	freelist_tail = NULL;
	freelist_iter = freelist;
    /*
     * 将freelist剩下的破损部分给截掉
     */
	while (freelist_iter) {
		nextfree = get_freepointer(s, freelist_iter); 	

		/*
		 * 如果“nextfree”无效，则“freelist_iter”处的对象可能已经损坏。 
		 * 因此，通过跳过从“freelist_iter”开始的所有对象来隔离它们
		 */
		if (freelist_corrupted(s, slab, &freelist_iter, nextfree))
			break;

		freelist_tail = freelist_iter;
		free_delta++;

		freelist_iter = nextfree;
	}

	/*
	 * 第二阶段：解冻slab，同时将per-cpu的空闲列表拼接到slab的空闲列表的头部。
	 *
	 * 确保slab已解冻，而列表的存在反映了解冻期间对象的实际数量。
	 *
	 * 我们首先执行 cmpxchg 持有锁，并在成功时插入列表。 
	 * 如果存在不匹配，则slab不会解冻，并且slab中的对象数量可能已更改。 
	 * 然后释放锁定并再次重试 cmpxchg。
	 */
redo:

	old.freelist = READ_ONCE(slab->freelist);
	old.counters = READ_ONCE(slab->counters);
	VM_BUG_ON(!old.frozen);

	/* 确定slab的目标状态 */
	new.counters = old.counters;
	if (freelist_tail) {
		new.inuse -= free_delta;
		set_freepointer(s, freelist_tail, old.freelist);
		new.freelist = freelist;
	} else
		new.freelist = old.freelist;

	new.frozen = 0; 	//frozen设为0来标识解冻

	if (!new.inuse && n->nr_partial >= s->min_partial) { 	//如果说激活slab的已被使用的块数量为0且partial块数量大于最小partial块数量
		mode = M_FREE; 			//则设置该mode来在之后的流程中释放它
	} else if (new.freelist) {
		mode = M_PARTIAL; 		//反之若存在空闲对象，则可以设置该mode来将其添加到partial链表当中
		/*
		 * 使用自旋锁消除了 acquire_slab() 看到被冻结的平板的可能性
		 */
		spin_lock_irqsave(&n->list_lock, flags);
	} else {
		mode = M_FULL_NOLIST;
	}


	if (!cmpxchg_double_slab(s, slab,
				old.freelist, old.counters,
				new.freelist, new.counters,
				"unfreezing slab")) {
		if (mode == M_PARTIAL)
			spin_unlock_irqrestore(&n->list_lock, flags);
		goto redo;
	}


	if (mode == M_PARTIAL) {
		add_partial(n, slab, tail);
		spin_unlock_irqrestore(&n->list_lock, flags);
		stat(s, tail);
	} else if (mode == M_FREE) {
		stat(s, DEACTIVATE_EMPTY);
		discard_slab(s, slab);
		stat(s, FREE_SLAB);
	} else if (mode == M_FULL_NOLIST) {
		stat(s, DEACTIVATE_FULL);
	}
}

:five:new_slab

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
new_slab:

	if (slub_percpu_partial(c)) { 			//如果有部分链表
		local_lock_irqsave(&s->cpu_slab->lock, flags);
		if (unlikely(c->slab)) { 		//若c->slab非空，这里说明切换了cpu，所以回到前面重新读
			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返回给c->slab
		slub_set_percpu_partial(c, slab); 			//将partial链条的下一个slab作为partial头返回
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		stat(s, CPU_PARTIAL_ALLOC);
		goto redo; 			//跳转到redo标签
	}

:six:new_object

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
/*
 * 走到这里说明没有partial链表了
 */
new_objects:

	pc.flags = gfpflags;
	pc.slab = &slab;
	pc.orig_size = orig_size;
	freelist = get_partial(s, node, &pc); 		//调用get_partial，这里会从kmem_cache_node中的partial链表来获取slab
	if (freelist) 			//如果获取成功，则直接去到 check_new_slab标签
		goto check_new_slab;

	slub_put_cpu_ptr(s->cpu_slab); 	
	slab = new_slab(s, gfpflags, node); 	//该函数最终会调用到allocate_slab,使用伙伴系统来分配slab
	c = slub_get_cpu_ptr(s->cpu_slab);

	if (unlikely(!slab)) {
		slab_out_of_memory(s, gfpflags, node);
		return NULL;
	}

	stat(s, ALLOC_SLAB);

	if (kmem_cache_debug(s)) { 	//若设置了相应标志位
		freelist = alloc_single_from_new_slab(s, slab, orig_size); 	//这里直接从slab中获取object

		if (unlikely(!freelist))
			goto new_objects;

		if (s->flags & SLAB_STORE_USER)
			set_track(s, freelist, TRACK_ALLOC, addr);

		return freelist;
	}

	/*
	 * 还没有其他对该slab的引用，因此我们可以在没有 cmpxchg 的情况下自由地使用它
	 */
	freelist = slab->freelist;  		//将该slab的object赋给freelist，然后冻结自己
	slab->freelist = NULL;
	slab->inuse = slab->objects;
	slab->frozen = 1;

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

这里介绍一下其中struct partial_context

1
2
3
4
5
6
/* 保存 get_partial() 调用链参数的结构 */
struct partial_context {
	struct slab **slab;
	gfp_t flags;
	unsigned int orig_size;
};

下面就是allocate_slab函数,也就是转到了咱们的伙伴系统分配page/slab

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
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;

	/*
	 * 让初始的高阶分配在内存压力下失败，以便我们回退到最小阶分配。
	 */
	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;

	slab = alloc_slab_page(alloc_gfp, node, oo);
	if (unlikely(!slab)) {
		oo = s->min;
		alloc_gfp = flags;
		/*
		 * 分配可能由于碎片而失败。 如果可能的话尝试较低顺序的分配
		 */
		slab = alloc_slab_page(alloc_gfp, node, oo);
		if (unlikely(!slab))
			return NULL;
		stat(s, ORDER_FALLBACK);
	}

	slab->objects = oo_objects(oo);
	slab->inuse = 0;
	slab->frozen = 0;

	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);

	if (!shuffle) {
		start = fixup_red_left(s, start);
		start = setup_object(s, start);
		slab->freelist = start;
		for (idx = 0, p = start; idx < slab->objects - 1; idx++) {
			next = p + s->size;
			next = setup_object(s, next);
			set_freepointer(s, p, next);
			p = next;
		}
		set_freepointer(s, p, NULL);
	}

	return slab;
}

:seven:check_new_slab

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
check_new_slab:

	if (kmem_cache_debug(s)) {
		/*
		 * 对于这里的调试缓存，我们必须通过 alloc_single_from_partial() 因此只需存储跟踪信息并返回对象
		 */
		if (s->flags & SLAB_STORE_USER)
			set_track(s, freelist, TRACK_ALLOC, addr);

		return freelist;
	}

	if (unlikely(!pfmemalloc_match(slab, gfpflags))) {
		/*
		 * 对于 !pfmemalloc_match() 情况，我们不加载空闲列表，这样我们就不会更容易地进行进一步的不匹配分配。
		 */
		deactivate_slab(s, slab, get_freepointer(s, freelist));
		return freelist;
	}

:eight:retry_load_slab

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
retry_load_slab:

	local_lock_irqsave(&s->cpu_slab->lock, flags);
	if (unlikely(c->slab)) { 		//若per-cpu的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); 	//使其flush_slab不活动

		stat(s, CPUSLAB_FLUSH);

		goto retry_load_slab;
	}
	c->slab = slab; 	//附上我们的新获得的slab

	goto load_freelist; 	//跳回该标签进行分配

3.kmalloc相关

我们接触的比较多的那就直接是这个kmalloc了，其他的一些顶层接口包括他都会调用上面讲的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
/**
 * kmalloc - 分配内核内存
 * @size: 需要的内存大小
 * @flags: 描述分配上下文
 *
 * kmalloc 是为小于内核页大小的对象分配内存的常规方法。
 *
 * 分配的对象地址至少与 ARCH_KMALLOC_MINALIGN 字节对齐。 
 * 对于两个字节的幂的@size，也保证对齐至少到该大小。
 *
 * @flags 参数可能是定义在下面位置的 GFP 标志之一
 * include/linux/gfp_types.h and described at
 * :ref:`Documentation/core-api/mm-api.rst <mm-api-gfp-flags>`
 *
 * @flags 的推荐用法描述于
 * :ref:`Documentation/core-api/memory-allocation.rst <memory_allocation>`
 *
 * 以下是最有用的 GFP 标志的简要概述
 *
 * %GFP_KERNEL
 *	分配普通内核内存，可睡眠
 *
 * %GFP_NOWAIT
 *	无法睡眠的分配
 *
 * %GFP_ATOMIC
 *	不会配置sleep。 可以使用应急池。
 *
 *  还可以通过在以下一个或多个附加 @flags 中进行“或”运算来设置不同的标志： 
 *
 * %__GFP_ZERO
 *	返回前填充0. Also see kzalloc().
 *
 * %__GFP_HIGH
 *	该分配有着高权限并且或许会使用紧急池.
 *
 * %__GFP_NOFAIL
 *	表明这个分配绝不允许失败（使用前三思）.
 *
 * %__GFP_NORETRY
 *	如果内存并非紧急需要，那么在第一时间放弃他
 *
 * %__GFP_NOWARN
 *	如果分配失败，不爆出警告
 *
 * %__GFP_RETRY_MAYFAIL
 *	非常努力地尝试成功分配但最终失败。
 */
static __always_inline __alloc_size(1) void *kmalloc(size_t size, gfp_t flags)
{
	if (__builtin_constant_p(size) && size) { 	//判断size在编译时是否为常量，若是则返回1，否则返回0
		unsigned int index;

		if (size > KMALLOC_MAX_CACHE_SIZE) 	//如果size大小大于一页，则调用kmalloc_large
			return kmalloc_large(size, flags);

		index = kmalloc_index(size);
		return kmalloc_trace(
				kmalloc_caches[kmalloc_type(flags)][index],
				flags, size);
	}
	return __kmalloc(size, flags);
}

解释一下其中所用到的几个函数

kmalloc_large

1
2
3
4
5
6
7
8
void *kmalloc_large(size_t size, gfp_t flags)
{
	void *ret = __kmalloc_large_node(size, flags, NUMA_NO_NODE);

	trace_kmalloc(_RET_IP_, ret, size, PAGE_SIZE << get_order(size),
		      flags, NUMA_NO_NODE);
	return ret;
}

其中调用的__kmalloc_large_node函数是先判断size属于的order大小，然后再调用伙伴系统的接口alloc_pages_node来获取相应的页再转为地址返回

kmalloc_index

实际上就是调用了__kmalloc_index，大致含义就是返回相应size所对应的kmem_caches二维数组的列下标（这代码码的还挺好看

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
/*
 * Figure out which kmalloc slab an allocation of a certain size
 * belongs to.
 * 0 = zero alloc
 * 1 =  65 .. 96 bytes
 * 2 = 129 .. 192 bytes
 * n = 2^(n-1)+1 .. 2^n
 *
 * 注意：__kmalloc_index() 是编译时优化的，而不是运行时优化的； 
 * 典型用法是通过 kmalloc_index() 进行，因此在编译时进行评估。
 * !size_is_constant 的调用者只能是测试模块，可以容忍 __kmalloc_index() 的运行时开销。 
 * 另请参阅 kmalloc_slab()。
 */
static __always_inline unsigned int __kmalloc_index(size_t size,
						    bool size_is_constant)
{
	if (!size)
		return 0;

	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 (!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;
}

kmalloc_trace

1
2
3
4
5
6
7
8
9
10
void *kmalloc_trace(struct kmem_cache *s, gfp_t gfpflags, size_t size)
{
	void *ret = __kmem_cache_alloc_node(s, gfpflags, NUMA_NO_NODE, 		//该函数相当于一个跳板，实际上仅仅是调用一个slab_alloc_node获取一个object
					    size, _RET_IP_);

	trace_kmalloc(_RET_IP_, ret, size, s->size, gfpflags, NUMA_NO_NODE);

	ret = kasan_kmalloc(s, ret, size, gfpflags);
	return ret;
}

上面的kesan_kmalloc具体并不参与分配过程，他主要用来对内存进行安全检测，下面是搜索到的解释

Kernel Address SANitizer(KASAN)是一种动态内存安全错误检测工具，主要功能是 检查内存越界访问和使用已释放内存的问题

因此，来整理一下kmalloc的运行过程

  1. 判断size，若大于了1页的范围，则调用kmalloc_large,然后使用伙伴系统的接口
  2. 这里说明size小于1页，我们调用kmalloc_index来获取相应kmalloc_caches的下标，然后调用kmalloc_trace来作为slab_alloc_node的上层接口来返回object

4.释放过程

咱们从比较通用的接口讲起

do_slab_free

该函数并不复杂，也就是在多cpu的情况下释放一个或多个object,整体函数表现为快路径

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
/*
 * Fastpath 具有强制内联功能，可生成 kfree 和 kmem_cache_free，
 * 无需额外的函数调用即可执行快速路径释放。
 *
 * 仅当我们释放该处理器的当前 cpu slab时，快速路径才可能实现。 
 * 如果我们之前刚刚分配过该项目，通常会出现这种情况。
 *
 * 如果快速路径不可行，则返回到 __slab_free ，我们在其中进行各种特殊处理。
 *
 * 通过指定 head 和 tail ptr 以及对象计数 (cnt)，
 * 可以批量释放具有多个对象（全部指向同一块）的空闲列表。 
 * 通过设置尾指针指示批量释放。
 */
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;
	struct kmem_cache_cpu *c;
	unsigned long tid;
	void **freelist;

redo:
	/*
	 * 确定每个 cpu 板当前的 cpus。 之后cpu可能会改变。 
	 * 但这并不重要，因为数据是通过该指针检索的。 
	 * 如果 cmpxchg 期间我们位于同一个 cpu 上，则释放将会成功。
	 */
	c = raw_cpu_ptr(s->cpu_slab);
	tid = READ_ONCE(c->tid);

	/* Same with comment on barrier() in slab_alloc_node() */
	barrier();

	if (unlikely(slab != c->slab)) { 	//如果传入的slab并不是当前cpu的slab，则调用下面函数
		__slab_free(s, slab, head, tail_obj, cnt, addr);
		return;
	}
 	/*
 	 * 这里说明途中cpu的slab和传入的slab相同，那么就需要进行锁操作来防止不同cpu的访问
 	 */
	if (USE_LOCKLESS_FAST_PATH()) { 	//该宏时根据编译选项来确定真假，但实际上均是使用锁来固定当前处理的该slab被锁在自身原来的cpu上
		freelist = READ_ONCE(c->freelist);

		set_freepointer(s, tail_obj, freelist); 	//头插c->freelist

		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 {
		/* Update the free list under the local lock */
		local_lock(&s->cpu_slab->lock);
		c = this_cpu_ptr(s->cpu_slab);
		if (unlikely(slab != c->slab)) {
			local_unlock(&s->cpu_slab->lock);
			goto redo;
		}
		tid = c->tid;
		freelist = c->freelist;

		set_freepointer(s, tail_obj, freelist);
		c->freelist = head;
		c->tid = next_tid(tid);

		local_unlock(&s->cpu_slab->lock);
	}
	stat(s, FREE_FASTPATH);
}

__slab_free

此处object属于的slab并不是当前cpu的slab，该处的函数也就是慢路径

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
/*
 * 慢速路径处理。 这可能仍然会被频繁调用，
 * 因为在大多数处理负载中对象的生命周期比 cpu slab更长。
 *
 * 所以我们还是尝试减少cache line的使用。 
 * 只需拿起板锁并释放该物品即可。 
 * 如果不需要额外的partial slab处理，那么我们可以立即返回。
 */
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 (IS_ENABLED(CONFIG_SLUB_TINY) || kmem_cache_debug(s)) { 	//这里判断编译参数，以及对于kmem_cache的设置
		free_to_partial_list(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); 	//将tail头插在slab->freelist上
		new.counters = counters;
		was_frozen = new.frozen;
		new.inuse -= cnt;
		if ((!new.inuse || !prior) && !was_frozen) { 	//如果说（new中即将没有了使用的object或原slab的空闲块本身就为空）并且（该new没有被冻结）

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

				/*
				 * Slab 之前没有出现在列表中，并且将部分为空。我们可以推迟列表移动而是冻结它。也就是链入cpu_slab
				 */
				new.frozen = 1;

			} else { /* 需要从list中删除 */

				n = get_node(s, slab_nid(slab));
				/*
				 * 推测性地获取list_lock。 
				 * 如果 cmpxchg 不成功，那么我们可以删除 list_lock 而不进行任何处理.
				 *
				 * 否则list_lock将与更新slab列表的其他处理器同步。
				 */
				spin_lock_irqsave(&n->list_lock, flags);

			}
		}

	} while (!cmpxchg_double_slab(s, slab,
		prior, counters,
		head, new.counters,
		"__slab_free")); 		//这里的判断条件是只要满足slab->freelist == prior 并且满足slab->counters == counters ，然后将其分别赋值为head和new.counters,然后就继续运行
	if (likely(!n)) {			//这里分空表示上面的do-while中没有运行到从list删除的部分

		if (likely(was_frozen)) { 	//如果曾经被冻结
			/*
			 * 未采取列表锁定，因此不需要列表活动。
			 */
			stat(s, FREE_FROZEN);
		} else if (new.frozen) {
			/*
			 * 如果我们刚刚冻结了该slab，我们就将他放入cpu的部分列表
			 */
			put_cpu_partial(s, slab, 1);
			stat(s, CPU_PARTIAL_FREE);
		}

		return;
	}
	/*
	 * 如果slab上的对象都是空闲的并且slab_alloc_node的部分列表数量大于最小的限制
	 */
	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial)) 
		goto slab_empty;

	/*
	 * 留在slab中的objects。 如果之前不在partial list中，则添加它。
	 */
	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) { 	//prior不为空说明slab本来应该在partial链表上 	
		/*
		 * Slab on the partial list.
		 */
		remove_partial(n, slab);
		stat(s, FREE_REMOVE_PARTIAL);
	} else { 	//为空则说明在full链表
		/* 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); 	//释放这一张slab
}

5.kfree相关

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
/**
 * kfree - free previously allocated memory
 * @object: pointer returned by kmalloc() or kmem_cache_alloc()
 *
 * If @object is NULL, no operation is performed.
 */
void kfree(const void *object)
{
	struct folio *folio;
	struct slab *slab;
	struct kmem_cache *s;

	trace_kfree(_RET_IP_, object);

	if (unlikely(ZERO_OR_NULL_PTR(object))) 	//对于传入指针的检测
		return;

	folio = virt_to_folio(object);
	if (unlikely(!folio_test_slab(folio))) {
		free_large_kmalloc(folio, (void *)object);
		return;
	}

	slab = folio_slab(folio);
	s = slab->slab_cache;
	__kmem_cache_free(s, (void *)object, _RET_IP_);
}

virt_to_folio

1
2
3
4
5
6
static inline struct folio *virt_to_folio(const void *x)
{
	struct page *page = virt_to_page(x);

	return page_folio(page);
}

通过我们的虚拟地址来获得我们相应物理地址所对应的page结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * page_folio - Converts from page to folio.
 * @p: The page.
 *
 * 每个page都是folio的一部分。 不能在 NULL 指针上调用此函数。
 *
 * 上下文：@page 上不需要引用，也不需要锁定。 
 * 如果调用者不持有引用，则此调用可能会与作品集拆分竞争，
 * 因此在获得作品集上的引用后，应重新检查作品集是否仍包含此页面。
 * Return: 包含该page的folio结构体
 */
#define page_folio(p)		(_Generic((p),				\
	const struct page *:	(const struct folio *)_compound_head(p), \
	struct page *:		(struct folio *)_compound_head(p)))

下面是一段folio的介绍

Linux 中的每个物理地址都有一个 struct page。 结构页是一种相当弱的数据类型； 当页面实际上是尾页并且没有映射时，很容易查看（例如）页面->映射。 Folios 是分离 struct page 的某些角色的开始。 从概念上讲，folios 获取 struct page 的内容（尾页部分除外）并将它们移动到 struct folio 中。 这并不是补丁集实际要做的事情，因为我还不够受虐狂，无法一次性完成所有这些更改。

我们可以（而且应该）走得更远。 我们需要了解内存（当前）是如何分配和使用的。 映射到用户空间的任何内存都需要有脏位和锁定位，有引用计数和映射计数。

引用的kernelnewbie,不知道他在说什么，初步判定是用来优化以往的page结构提出的新特性，这里是返回了folio结构体供我们kfree使用

free_large_kmalloc

大页面则使用伙伴系统的接口，将其直接释放至伙伴系统之中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void free_large_kmalloc(struct folio *folio, void *object)
{
	unsigned int order = folio_order(folio);

	if (WARN_ON_ONCE(order == 0))
		pr_warn_once("object pointer: 0x%p\n", object);

	kmemleak_free(object);
	kasan_kfree_large(object);
	kmsan_kfree_large(object);

	mod_lruvec_page_state(folio_page(folio, 0), NR_SLAB_UNRECLAIMABLE_B,
			      -(PAGE_SIZE << order));
	__free_pages(folio_page(folio, 0), order);
}

__kmem_cache_free

调用了另一个函数

1
2
3
4
void __kmem_cache_free(struct kmem_cache *s, void *x, unsigned long caller)
{
	slab_free(s, virt_to_slab(x), x, NULL, &x, 1, caller);
}

slab_free

这里也是直接调用了我们之前所讲述的较为关键的释放函数

1
2
3
4
5
6
7
8
9
10
11
12
static __fastpath_inline void slab_free(struct kmem_cache *s, struct slab *slab,
				      void *head, void *tail, void **p, int cnt,
				      unsigned long addr)
{
	memcg_slab_free_hook(s, slab, p, cnt);
	/*
	 * 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);
}

-1.参考

arttnba3师傅博客

kernel doc 中文版

kernel new bies

LWN

Linux Kernel
#Linux #kernel #source
Linux_Kernel_SLUB分配器
https://peiandhao.github.io/2023/07/18/Linux-Kernel-SLUB分配器/
作者
peiwithhao
发布于
2023年7月18日
许可协议