Slub 分配器的來龍去脈
slab 分配器設計的需求
在 Linux 內核的內存子系統中，夥伴系統無疑處於內存管理的核心地帶，但是如果將內存管理從邏輯上分層，它的位置則處於最底層。Buddy 是所有物理內存的管家，不論使用何種接口申請內存都要經由夥伴系統進行分配。但是，夥伴系統管理的物理內存是以頁爲單位，以 4K 頁爲例，它也包含了 4096 個字節。但是無論是內核自己還是用戶程序，在日常的使用中都很少會需要使用四千多字節大小的內存。試想如果我們僅需要爲 10 個字符的字符串分配內存，但是夥伴系統卻給了我們一頁，那這一頁剩餘沒有使用的內存就浪費了，而且這個浪費近乎奢侈。除了浪費的問題， 還有一個更需要關心的問題是，在這樣的分配情況下，如果分配非常頻繁，系統可能很快就會面臨嚴重的碎片化問題。因爲頻繁使用的數據結構也會頻繁的分配和釋放，加速生產內存碎片。另外，直接調用夥伴系統的操作對系統的數據和指令高速緩存也有很大的影響。所以，基於以上的原因，也源於現實需求，內核需要一種輕量的、快速的、靈活的新型內存分配器，最主要的是，它可以提供小塊內存的分配。爲了實現這樣的小內存分配器，Sun 公司的 J.Bonwick 首先在 Solaris 2.4 中設計並實現了 slab 分配器，並對其開源。在 Linux 中也實現了具有相同的基本設計思想的同名分配器 slab。
slab、slob 和 slub 關係
slab、slob 和 slub 都是小內存分配器，slab 是 slob 和 slub 實現的基礎，而 slob 和 slub 是針對 slab 在不同場景下的優化版本。在 slab 引入 Linux 的很多年內，其都是 Linux 內核管理對象緩衝區的主流算法。並且由於 slab 的實現非常複雜，很長一段時間內都少有對它的改動。隨着多處理器的發展和 NUMA 架構的廣泛應用，slab 的不足也逐漸顯現。slab 的緩存隊列管理複雜，其用於管理的數據結構存儲開銷大，對 NUMA 支持複雜，slab 着色機制效果不明顯。這些不足讓 slab 很難在兩種場景下提供最優的性能：小型嵌入式系統和配備有大量物理內存的大規模並行系統。對於小型嵌入式系統來說，slab 分配器的代碼量和複雜性都太高；對於大規模並行系統，slab 用於自身管理的數據結構就需要佔用很多 G 字節內存。針對 slab 的不足，內核開發人員 Christoph Lameter 在在內核版本 2.6 開發期間，引入了新的 Slub 分配器。Slub 簡化了 slab 一些複雜的設計，但保持 slab 的基本設計思想。同時，一種新的針對小型嵌入式系統的分配器 slob 也被引入，爲了適應嵌入式系統的特點，slob 進行了特別的優化，以大幅減少代碼量（slob 只有大約 600 行代碼）。
slab 層在內存管理子系統的層次
slab 層可以理解爲一個通用層，其包含了 slab、slob 和 slub，至於底層具體使用哪種分配器可以通過配置內核選項進行選擇。對於內核的其他模塊，則不需要關注底層使用了哪個分配器。因爲爲了保證內核的其他模塊都可以無縫遷移到 Slub/slob，所有分配器的接口都是相同的，它們都實現了一組特定的接口用於內存分配。下圖爲 Slab 層在內存管理中的層次圖：
邏輯上看，slab 層位於夥伴系統之上。因爲 Buddy 是最底層的分配器，Slub 需要先向 Buddy 申請內存，而不能越過 Buddy 獲取 page。從 Buddy 申請到內存後，Slub 纔可以對其進行自己的操作。
slub 分配器框架
下圖是在讀完宋牧春大俠的《圖解 Slub》後，我也總結了一張 Slub 分配器框架圖，可以大致的看到 Slub 的框架。Slub 的框架如下圖（圖片很大，可以放大）：
這篇文章（原文鏈接以置文末）中用了一個通俗易懂的例子來介紹 Slub 的工作原理，我覺的這個例子很恰當，所以這裏繼續借舉一下。
每個數組元素對應一種大小的內存，可以把一個 kmem_cache 結構體看做是一個特定大小內存的零售商，整個 Slub 系統中有很多個這樣的零售商，每個 “零售商” 只“零售”特定大小的內存，例如：有的 “零售商” 只 "零售"8Byte 大小的內存，有的只”零售 “16Byte 大小的內存。——引自 luken.《linux 內核內存管理 slub 算法(一) 原理》
Slub 的工作原理和日常生產生活的產銷環節很類似，所以爲了清晰直觀的看到其工作原理，我把這個過程畫了一幅圖來表示，如下圖：
每個零售商 (kmem_cache) 有兩個 “部門”，一個是“倉庫”：kmem_cache_node，一個“營業廳”：kmem_cache_cpu。“營業廳” 裏只保留一個 slab，只有在營業廳 (kmem_cache_cpu) 中沒有空閒內存的情況下才會從倉庫中換出其他的 slab。所謂 slab 就是零售商 (kmem_cache) 批發的連續的整頁內存，零售商把這些整頁的內存分成許多小內存，然後分別 “零售” 出去，一個 slab 可能包含多個連續的內存頁。slab 的大小和零售商有關。——引自 luken.《linux 內核內存管理 slub 算法 (一) 原理》
總的來說，Slub 就相當於零售商，它從夥伴系統 “批發” 內存，然後再零售出去。
slub 的重要數據結構
- kmem_cache
struct kmem_cache {
struct kmem_cache_cpu __percpu *cpu_slab;
/* Used for retriving partial slabs etc */
unsigned long flags;
unsigned long min_partial;
/* size = object_size + 對象後面下個空閒對象的指針的size */
int size; /* The size of an object including meta data */
int object_size; /* The size of an object without meta data */
/* object首地址 + offset = 下一個空閒對象的指針地址 */
int offset; /* Free pointer offset. */
int cpu_partial; /* Number of per cpu partial objects to keep around */
/*
* oo表示存放最優slab的order和object的數量
* 低16位表示對象數，高16位表示slab的order
*/
struct kmem_cache_order_objects oo;
/* Allocation and freeing of slabs */
struct kmem_cache_order_objects max;
/*
* 最小slab只需要足夠存放一個對象。當設備長時間運行以後，內存碎片化嚴重，
* 分配連續物理頁很難成功，如果分配最優slab失敗，就分配最小slab。
*/
struct kmem_cache_order_objects min;
gfp_t allocflags; /* gfp flags to use on each alloc */
int refcount; /* Refcount for slab cache destroy */
void (*ctor)(void *);
int inuse; /* Offset to metadata */
int align; /* Alignment */
// 當slab長度不是對象長度的整數倍的時候，尾部有剩餘部分，保存在reserved中
int reserved; /* Reserved bytes at the end of slabs */
const char *name; /* Name (only for display!) */
struct list_head list; /* List of slab caches */
int red_left_pad; /* Left redzone padding size */
#ifdef CONFIG_SYSFS
struct kobject kobj; /* For sysfs */
#endif
#ifdef CONFIG_MEMCG
struct memcg_cache_params memcg_params;
int max_attr_size; /* for propagation, maximum size of a stored attr */
#ifdef CONFIG_SYSFS
struct kset *memcg_kset;
#endif
#endif
#ifdef CONFIG_NUMA
/*
* Defragmentation by allocating from a remote node.
*/
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
struct kmem_cache_node *node[MAX_NUMNODES]; /* 每個NUMA節點都有一個kmem_cache_node */
};根據是否打開 Slub Debug，next object 指針可以有兩種方式放置，如果打開了 Slub Debug，則採用指針外置式；反之，採用指針內置式。兩種指針放置方式如下圖：
- 指針外置式
- 指針內置式
指針內置式的方法實際上是複用了 object 的前 8 個字節，因爲在 object 被分配出去之前，這一段內存具體存放什麼內容並不重要，所以可以利用這一段內存來保存下一個 free object 的地址。
- kmem_cache_cpu
struct kmem_cache_cpu {
/* 指向下一個空閒的object，用於快速找到可用對象 */
void **freelist; /* Pointer to next available object */
/*
* 要保證tid和kmem_cache是由同一個CPU訪問。
* 開啓了內核搶佔後，訪問tid和kmem_cache的CPU可能不是同一個CPU，
* 所以要檢查是否匹配，直到它們是由同一個CPU進行訪問
*/
unsigned long tid; /* Globally unique transaction id */
/* 指向當前使用的slab */
struct page *page; /* The slab from which we are allocating */
/* 指向當前cpu上緩存的部分空閒slab鏈表 */
struct page *partial; /* Partially allocated frozen slabs */
#ifdef CONFIG_SLUB_STATS
/*
* 記錄對slab操作的狀態變化，這個stat非常重要，
* 通過這個stat就大概瞭解object從申請到釋放經過了哪些步驟
*/
unsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};- kmem_cache_node
struct kmem_cache_node {
spinlock_t list_lock;
/* 此處省略掉SLAB的配置 */
#ifdef CONFIG_SLUB
/* 掛入kmem_cache_node中的slab數量 */
unsigned long nr_partial;
/* 指向當前內存節點上的部分空閒slab鏈表 */
struct list_head partial;
#ifdef CONFIG_SLUB_DEBUG
atomic_long_t nr_slabs;
atomic_long_t total_objects;
struct list_head full;
#endif
#endif
};page 中描述 Slub 信息的字段：
struct page {
/* 如果flag設置成PG_slab,表示頁屬於slub分配器 */
unsigned long flags;
union {
struct address_space *mapping;
/* 指向當前slab中第一個object */
void *s_mem; /* slab first object */
atomic_t compound_mapcount; /* first tail page */
};
union {
pgoff_t index; /* Our offset within mapping. */
/* 指向當前slab中第一個空閒的object */
void *freelist; /* sl[aou]b first free object */
};
union {
unsigned counters;
struct {
union {
atomic_t _mapcount;
unsigned int active; /* SLAB */
struct { /* SLUB */
/* 該slab中已經分配使用的object數量 */
unsigned inuse:16;
/* 該slab中的所有object數量 */
unsigned objects:15;
/*
* 如果slab在kmem_cache_cpu中，表示處於凍結狀態；
* 如果slab在kmem_cache_node的部分空閒slab鏈表中，表示處於解凍狀態
*/
unsigned frozen:1;
};
int units; /* SLOB */
};
atomic_t _refcount;
};
};
union {
/* 作爲鏈表節點加入到kmem_cache_node的部分空閒slab鏈表中
struct list_head lru; /* Pageout list */
struct dev_pagemap *pgmap;
struct { /* slub per cpu partial pages */
struct page *next; /* Next partial slab */
int pages; /* Nr of partial slabs left */
int pobjects; /* Approximate # of objects */
};
struct rcu_head rcu_head;
struct {
unsigned long compound_head; /* If bit zero is set */
unsigned int compound_dtor;
unsigned int compound_order;
};
};
union {
unsigned long private;
struct kmem_cache *slab_cache; /* SL[AU]B: Pointer to slab */
};
......
}Slub 的分配過程
Slub 的分配流程大致如下：首先從 kmem_cache_cpu 中分配，如果沒有則從 kmem_cache_cpu 的 partial 鏈表分配，如果還沒有則從 kmem_cache_node 中分配，如果 kmem_cache_node 中也沒有，則需要向夥伴系統申請內存。
Slub 的分配接口是 kmem_cache_malloc()。其分配 object 的流程大概如下：首先在 kmem_cache_cpu 所使用的 slab 中查找 free object，如果當前 slab 中有 free object，則返回這個 object。如果當前 slab 沒有 free object，就要看 Slub 是否開啓了 kmem_cache_cpu 的 Partial 隊列，如果開啓了 partial 隊列，就在 Partial 隊列中查看有沒有 free object 的 slab，如果有的話就選定這個 slab，並返回其 free object。如果 kmem_cache_cpu 的 partial 鏈表中也沒有擁有 free object 的 slab，則在 kmem_cache_node 中查找。如果 kmem_cache_node 中的 slab 有 free object，則選定這個 slab 並返回 free object。如果 kmem_cache_node 中也沒有 free object，則需要向夥伴系統申請內存，製作新的 slab。
創建 slab 緩存 (kmem_cache) 的函數分析
斗膽分析一下 slab 緩存的創建過程，新手小白分析內核代碼，分析的可能不夠深度和完整，如有不對還請各路高手指教，提前謝過。
函數調用流程：
kmem_cache_create()
——> kmem_cache_create_usercopy()
——> create_cache()
——> __kmem_cache_create()
——> kmem_cache_open()下面是每個函數的主幹分析，代碼有精簡。
kmem_cache_create()：
kmem_cache_create() 裏繼續調用了 kmem_cache_create_usercopy()。
kmem_cache_create() {
return kmem_cache_create_usercopy(name, size, align, flags, 0, 0, ctor);
}kmem_cache_create_usercopy()：
kmem_cache_create_usercopy() {
struct kmem_cache *s = NULL;
const char *cache_name;
/*
* Some allocators will constraint the set of valid flags to a subset
* of all flags. We expect them to define CACHE_CREATE_MASK in this
* case, and we'll just provide them with a sanitized version of the
* passed flags.
*/
flags &= CACHE_CREATE_MASK;
/* 定義這個緩存的名字，用於在/proc/slabinfo中顯示 */
cache_name = kstrdup_const(name, GFP_KERNEL);
/* kmem_cache結構，並返回其地址 */
s = create_cache(cache_name, size,
calculate_alignment(flags, align, size),
flags, useroffset, usersize, ctor, NULL, NULL);
return s;
}create_cache()：
create_cache() {
struct kmem_cache *s;
int err;
/* 爲kmem_cache結構申請一段內存並清零 */
s = kmem_cache_zalloc(kmem_cache, GFP_KERNEL);
/* 初始化kmem_cache結構的部分成員 */
s->name = name;
s->size = s->object_size = object_size;
s->align = align;
s->ctor = ctor;
s->useroffset = useroffset;
s->usersize = usersize;
/* 核心函數，slub/slab/slob都實現了這個函數 */
err = __kmem_cache_create(s, flags);
/* 將新創建的kmem_cache加入slab caches鏈表 */
list_add(&s->list, &slab_caches);
return s;
}__kmem_cache_create()：
__kmem_cache_create() {
int err;
/* 在kmem_cache_open中處理剩餘的結構成員，如min_partial、cpu_partial等 */
err = kmem_cache_open(s, flags);
}kmem_cache_open()：
kmem_cache_open() {
/* 設置kmem_cache中的min_partial,它表示kmem_cache_node中partial鏈表可掛入的slab數量 */
set_min_partial(s, ilog2(s->size) / 2);
/* 設置kmem_cache中的cpu_partial,它表示per cpu partial上所有slab中free object總數 */
set_cpu_partial(s);
/* 爲每個節點分配kmem_cache_node */
if (!init_kmem_cache_nodes(s))
goto error;
/* 爲kmem_cache_cpu變量創建每CPU副本 */
if (alloc_kmem_cache_cpus(s))
return 0;
}分配對象 (object) 的函數分析
函數調用流程：
kmem_cache_alloc()
——> slab_alloc()
——> slab_alloc_node()
——> __slab_alloc()
——> ___slab_alloc()kmem_cache_alloc()：
kmem_cache_alloc() {
/* 直接調用slab_alloc */
void *ret = slab_alloc(s, gfpflags, _RET_IP_);
return ret;
}slab_alloc()：
slab_alloc() {
return slab_alloc_node(s, gfpflags, NUMA_NO_NODE, addr);
}slab_alloc_node()：
slab_alloc_node() {
void *object;
struct kmem_cache_cpu *c;
struct page *page;
redo:
/*
* 要保證tid和kmem_cache是由同一個CPU訪問。但是如果配置了CONFIG_PREEMPT = y，
* 即開啓了內核搶佔後，訪問tid和kmem_cache的CPU可能不是同一個CPU，所以要檢查
* 是否匹配，直到它們是由同一個CPU進行訪問。
*
* 內核態搶佔的時機是：
* 1.中斷處理函數返回內核空間之前會檢查請求重新調度的標誌(TIF_NEED_RESCHED)，
* 如果置位則調用preempt_schedule_irq()執行搶佔。
* 2. 當內核從non-preemptible(禁止搶佔)狀態變成preemptible(允許搶佔)的時候。
*/
do {
tid = this_cpu_read(s->cpu_slab->tid); /* 訪問當前CPU的per CPU變量的副本的tid */
c = raw_cpu_ptr(s->cpu_slab);
} while (IS_ENABLED(CONFIG_PREEMPT) && /* 檢查是否開啓了內核搶佔 */
unlikely(tid != READ_ONCE(c->tid)));
barrier(); /* 內存屏障，消除指令亂序執行的影響 */
object = c->freelist; /* 下一個free object的地址 */
page = c->page; /* 當前使用的slab */
if (unlikely(!object || !node_match(page, node))) {
/* 調用核心函數__slab_alloc() */
object = __slab_alloc(s, gfpflags, node, addr, c);
stat(s, ALLOC_SLOWPATH);
} else {
void *next_object = get_freepointer_safe(s, 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);
/* 如果gfpflags標誌需要對object對象的內存清零 */
if (unlikely(slab_want_init_on_alloc(gfpflags, s)) && object)
memset(object, 0, s->object_size);
slab_post_alloc_hook(s, gfpflags, 1, &object);
return object;
}__slab_alloc()：
__slab_alloc() {
void *p;
unsigned long flags;
/*
* 關中斷。關閉當前處理器上的所有中斷處理
*
* local_irq_save()將當前的中斷狀態(開或關)
* 保存在flags中然後再禁用處理器上的中斷。
*
* 與local_irq_save不同，local_irq_disable()
* 不保存狀態而關閉本地處理器的中斷服務。
*/
local_irq_save(flags);
#ifdef CONFIG_PREEMPT
/*
* 在關中斷之前，可能已經被搶佔並被調度在不同的CPU上，
* 所以需要重新加載CPU區域的指針。
*/
c = this_cpu_ptr(s->cpu_slab);
#endif
/* 調用核心函數___slab_alloc() */
p = ___slab_alloc(s, gfpflags, node, addr, c);
/*
* 恢復本地處理器的中斷。
*
* local_irq_restore()將local_irq_save()保存的狀態值(flags)恢復，
* 注意是恢復之前的中斷狀態，不一定會開啓中斷。如果之前的狀態是
* 開中斷，就打開中斷；如果之前的狀態是關中斷，就關閉中斷。
* 而local_irq_enable()會無條件開啓中斷，所以可能會破壞之前的中
* 斷環境。所以local_irq_restore()比local_irq_enable()更安全。
*/
local_irq_restore(flags);
return p;
}slub 的 frozen（凍結）和 unfrozen（解凍）
如果 cpu1 的 kcmem_cache_cpu 的 slab 是 frozen, 那麼 cpu1 可以從該 slab 中取出或放回 obj，但是 cpu2 不能從該 slab 中取 obj, 只能把 obj 還給該 slab。另外，cpu partial 上的 slab 都是 frozen 狀態。node partial 上的 slab 都是 unfrozen。耗盡 kmem_cache_cpu 的 slab 的 obj 後解凍 slab。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/CJW8crYUqtRztavhpOR6uA