SLUB算法
之前我们讲解了伙伴系统，他的层次在于分配以page为单位的页面，但在平时我们程序使用的这么大个单位的页面机会很少，我们更倾向于分配小块例如0x2e0的块,而此时如果再次调用伙伴系统的分配就有点杀鸡用牛刀的感觉，所以此时Linux内核引入小块的分配器，也就是
slab allocator
他存在着三种实现形式：slab,slob,slub
1. 数据结构们
struct slab
首先就是我们比较主要的数据结构slab，他曾经是被嵌入在page当中，但是目前最新内核版本6.4，他被作为一个独立的数据结构进行表示，当然实际上也是复用了page的结构体，具体如下：
/* 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结构体的时候，我们也可以通过他来得到物理内存页的页框号，下面是其中的一些字段解释：
__page_flags字段:他用来标识页面的相关信息slab_cache字段:他是一个kmem_cache类型的指针,该结构体我们下面讲解free_list:该字段指向第一个空闲的object,耗尽时为NULLslab_list:连接多个slab的双向链表inuse:已经被使用的object数objects:总共的object数frozen:标志是否（1/0）被冻结，也就是是否被cpu.slab绑定
下面的这张图就是关于目前的slab结构体的相关结构，我们慢慢来充实该图
其中freelist字段指向的块就是我们先前page页所代表的页框中的某块。
struct kmem_cache
要管理小块的分配，单单一个复用page结构的slab还不够，所以这里引入我们的管理者kmem_cache，如下
/*
* 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的空闲对象缓存，其大致定义如下:
/*
* 更改布局时，请确保 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
};
其中有下面几点需要注意：
- freelist：指向下一个分配对象的指针
- slab：被当前使用来分配内存的slab
- partial：链表上为仍有一定空闲object的slab
其中slab->freelist在被kmem_cache_cpu使用时为NULL，是个无效值，只有他在处于partial链表才会有效
struct kmem_cache_node
node[MAX_NUMNODES]:他是一个数组指针，其中每一个元素都指向一个kmem_cache_node，他是NUMA架构中每个node节点的缓存，如下：
/*
* 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，如下：
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);
其中他的行为以下枚举类型
/*
* 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等等。
然后我们的列主要是以下部分
#define KMALLOC_SHIFT_HIGH (PAGE_SHIFT + 1)
#define PAGE_SHIFT 12
所以说我们的kmalloc_caches共有14列，行数需通过配置来决定
下面我们来完善上面的图
2.分配过程
首先我们拿__kmalloc函数来分析，他的实现如下，调用另一个函数__do_kmalloc_node
void *__kmalloc(size_t size, gfp_t flags)
{
return __do_kmalloc_node(size, flags, NUMA_NO_NODE, _RET_IP_);
}
之后该函数又调用其他函数,我超上面白写了，调用链如下：
__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:
/*
* 内联快速路径，以便分配函数（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
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
/*
* ___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
接下来就是咱们的重磅函数，如下：
/*
* 慢路径. 无锁空闲列表为空或者我们需要执行调试职责.
*
* 如果新对象已释放到常规空闲列表，处理速度仍然非常快。
* 在这种情况下，我们只需将常规空闲列表接管为无锁空闲列表，然后取消常规空闲列表。
*
* 如果这不起作用，那么我们就回到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
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
/*
* 运行到这里说明在上面获取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
#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
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的地址，如下：
/*
* 返回空闲列表指针 (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
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
下面介绍以下激活函数
/*
* 完成移除 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
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
/*
* 走到这里说明没有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
/* 保存 get_partial() 调用链参数的结构 */
struct partial_context {
struct slab **slab;
gfp_t flags;
unsigned int orig_size;
};
下面就是allocate_slab函数,也就是转到了咱们的伙伴系统分配page/slab
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
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
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
/**
* 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
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二维数组的列下标（这代码码的还挺好看
/*
* 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
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的运行过程
- 判断size，若大于了1页的范围，则调用kmalloc_large,然后使用伙伴系统的接口
- 这里说明size小于1页，我们调用kmalloc_index来获取相应kmalloc_caches的下标，然后调用kmalloc_trace来作为slab_alloc_node的上层接口来返回object
4.释放过程
咱们从比较通用的接口讲起
do_slab_free
该函数并不复杂，也就是在多cpu的情况下释放一个或多个object,整体函数表现为快路径
/*
* 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，该处的函数也就是慢路径
/*
* 慢速路径处理。 这可能仍然会被频繁调用，
* 因为在大多数处理负载中对象的生命周期比 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相关
/**
* kfree - free previously allocated memory
* @object: pointer returned by kmalloc() or kmem_cache_alloc()
*
* If home.php?mod=space&uid=245521 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
static inline struct folio *virt_to_folio(const void *x)
{
struct page *page = virt_to_page(x);
return page_folio(page);
}
通过我们的虚拟地址来获得我们相应物理地址所对应的page结构体
/**
* 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
大页面则使用伙伴系统的接口，将其直接释放至伙伴系统之中
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
调用了另一个函数
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
这里也是直接调用了我们之前所讲述的较为关键的释放函数
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
[复制链接]
发表于 2023-7-18 23:14
