HackMDslab 記憶體配置器
資料整理: jserv
簡介
slab 一詞源於 SunOS 原始程式碼，開發者選擇這詞彙，是相較於 "object" 或 "cache"，slab 更具辨識度，該詞彙的原意是針對石、木、金屬、食物等的板或片段。根據 Jeff Bonwick 發表在 1994 年的論文〈The slab Allocator: An Object-Caching Kernel〉，記憶體配置器管理記憶體區域 (arenas) 的策略可區分為 sequential-fit, buddy 和 segregated-storage 這三個手法。slab 配置器屬於 segregated-storage。本文為了讓讀者易於對照論文，像是 cache, object, slab 和 buffer 一類的術語，保留原文。
所有的 slab 具有相同的空間，通常設定為為記憶體管理單元 (MMU) 的頁面 (page) 的大小，在 POSIX 相容的系統上，可藉由 sysconf(_SC_PAGESIZE) 查詢。slab 的記憶體從後端配置器中設定，這意味著從更大的記憶體區塊 (block) 中請求記憶體，通常至少是一個頁面的大小。一個 slab 包含多個大小相同的 buffer，slab 的資料部分(slab Data) 置於 slab 的結尾，以減少非法記憶體存取導致的損壞風險。一個 cache 包含多個 slab，cache 中的 slab 透過雙向鏈結串列連接，freelist 指標指向至少有個空閒 buffer 的 slab。
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
當 buffer 被釋放時，配置器會檢查 slab 中剩餘的空閒 buffer 的數量。若一個 slab 中所有的 buffer 都被釋放，則將該 slab 移到鏈結串列的末尾，確保 freelist 指標指向至少有一個空閒 buffer 的 slab。若 cache 中的 slab 數量低於一定的閾值（工作集 [work set] 大小），該 slab 不會立即返回後端配置器，以降低重新設定和初始化 slab 的開銷。
Buffer 大小會事先定義，例如 8B, 16B, 32B, 48B 等，每個大小對應一個包含雙向鏈結串列的 cache。設定記憶體時，配置器會將請求的大小匹配到不小於該請求的最小 buffer 大小，然後從對應的 cache 中找到有空閒 buffer 的 slab 進行設定。超過半頁大小的請求，直接從後端配置器設定。
釋放記憶體時，配置器藉由檢查是否對齊頁面大小來區分 buffer 和大型 object 的地址。buffer 不用對齊頁面大小，而大型 object 則要對齊頁面大小。這樣即可避免使用雜湊表進行映射的需求，確保記憶體管理的高效。
userland-slab-allocator 提供文字模式的 slab 配置動態展示。
實作示範
儘管 Jeff Bonwick 描述的 slab 起初用於核心物件的管理，但同樣適用於使用者空間。記憶體配置器請求一個頁面大小的記憶體區塊，並將其分割成固定大小的片段。每個片段可以容納一個指標或整數，並鏈接成一個串列，串列的頭部指向第一個空閒節點。
以下是 Marek Vavrusa 提供的實作程式碼:
struct slab {
void **head;
};
/* Create page-aligned slab */
struct slab *slab = NULL;
posix_memalign(&slab, page_size, page_size);
slab->head = (void **) ((char *) slab + sizeof(struct slab));
/* Create a NULL-terminated slab freelist */
char* item = (char *) slab->head;
for (unsigned i = 0; i < item_count; ++i) {
*((void **) item) = item + item_size;
item += item_size;
}
*((void **) item) = NULL;
記憶體的配置操作只需取出鏈結串列的開頭，而記憶體釋放操作則相當於將一個新的開頭節點置入鏈結串列。這裡可留意到一個技巧：若 slab 對齊到頁面大小的邊界，可藉由向下取整數到頁面大小，以較低的成本來獲取 slab 指標。
/* Free an element */
struct slab *slab = (void *) ((size_t) ptr & PAGESIZE_BITS);
*((void **) ptr) = (void *) slab->head;
slab->head = (void **) ptr;
/* Allocate an element */
if ((item = slab->head)) {
slab->head = (void **) *item;
} else {
/* No elements left. */
}
Linux 核心的 slab
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
以下是 Linux 核心的用語:
- slab: 一組包含一個或多個連續頁面的記憶體，這些頁面包含特定大小的核心物件。
- slab cache: 多個相同類型 slab 的容器。有兩種類型的 cache：
- 專用 cache: 由 Linux 核心建立，每個 cache 僅用於保存一種（常用）物件類型，例如
mm_struct或cred_jar - 通用 cache: 可容納任何特定大小 (加上 padding) 的物件。通常，這些 cache 中的物件大小為 2 的冪。當呼叫
kmalloc()時，返回的已配置記憶體將在這些 cache 之一（例如kmalloc-32,kmalloc-64等）中，實際則取決於請求的大小。
- 專用 cache: 由 Linux 核心建立，每個 cache 僅用於保存一種（常用）物件類型，例如
- SLOB / SLAB / SLUB: 都是 Linux 核心中可用的 slab 配置器，較新的 Linux 核心版本已棄置 slob 和 slab，因此新的 Linux 僅提供 SLUB 這個 slab 的改進版本。
要顯示不同 slab cache 的資訊，我們可執行以下命令:
$ sudo cat /proc/slabinfo
參考輸出:
slabinfo - version: 2.1
# name <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab>
...
kmalloc-8k 1700 1700 8192 4 8
kmalloc-4k 6329 6552 4096 8 8
kmalloc-2k 20791 20896 2048 16 8
kmalloc-1k 20906 20960 1024 32 8
kmalloc-512 337585 506176 512 64 8
kmalloc-256 85546 89472 256 64 4
kmalloc-128 297466 302272 128 64 2
kmem_cache_node 1070 1088 128 64 2
kmem_cache 896 896 256 64 4
SLUB 配置器
我們專注於 SLUB 配置器，不僅因它是 Linux 核心預設的記憶體配置器，而且針對多核處理器進行調整。
Linux 核心中的記憶體配置會比使用者模式中略為單純，因為 metadata 通常不與資料主體存在放同一個空間 (例如使用者模式的 heap)，而是儲存在不同的結構中。
每個 CPU 都有一個有效的 slab 用於每種類型的物件。這意味著，當在某個 CPU 上配置某種類型/大小的物件時，僅從該 CPU 的有效 slab 中配置空間，直到沒有更多的空閒空間。當沒有更多空間時，另一個 slab 將被標記為該 CPU 的有效 slab。需要注意的是，不同的處理器有不同的有效的 slab。
在 SLUB 配置器中，kmem_cache 結構體負責分類管理。說到分類，我們總是按照某些屬性進行分類，對應到真實世界，就是說賣場中各項商品的用途。
SLUB 的分類依據是什麼呢？首先是按照名字分類。呼叫 kmem_cache_create() 時，首個參數是 name，而這個名字保存在 kmem_cache 結構體的 name 成員中。我們可藉由以下命令查看系統中 SLUB 的分類：
$ cat /proc/slabinfo
隨即可見 task_struct 和 inode_cache 等資訊。
另一種分類方式是按照大小。我們可在上述命令的輸出中看到 kmalloc-512 和 kmalloc-256 等字樣，這些是按照大小配置的記憶體快取。
按照名字分類隱含按大小分類的意義，這裡單獨列出是為了強調 SLUB 中對大小的計算，也就是進行預先存取 (prefetch) 的依據，後者的目的是提高系統性能。在解釋其作法前，我們回顧現實生活的案例：超級市場中，貨架上琳瑯滿目的商品都可算是預先存取，超市按照估計預先將商品放在貨架上，等待顧客購買。若每種商品貨架上只有一個，於是眾多顧客購買後，就要等待商家補貨，方可滿足購物需求，預先存取則可節省顧客的平均購買時間。
再來看商場服務人員的工作：在顧客購買商品的過程，服務人員也會持續補充貨架。倘若每當一個商品被拿走，服務人員就去倉庫取一個商品補充，那未免太繁瑣。因此，當貨架上的商品賣完時，服務人員才會去倉庫取出一批商品補充貨架。換言之，預先存取可降低服務人員的工作負擔。
不過前述的「一批」商品的數量該是多少？若拿太少，就不能提升每次取貨的效率，而若拿多，則貨架上放不下。生活中如此，Linux 核心也有對應的考量。
記憶體管理模組具備多個層次，SLUB 配置器建立在頁面配置器之上，因此可理解為頁面是 SLUB 的貨架。超市貨物上架前，應當做好以下估算：
- 貨架的大小
- 貨架上能放多少貨物
SLUB 同樣需要計算以下：
- 用多大的頁面來作為貨架
- 每個頁面中可以放多少對象
這些資料都保存在 kmem_cache 結構體中，整個計算過程在 calculate_sizes() 函式。注意：這裡說的頁面不是單個的實體頁面，而是核心中 struct page 對應的頁面。
用更細緻的案例來解說：
- 假如申請的結構體 (貨物) 大小是 512 位元組，那麼頁面 (貨架) 可選擇 4K 位元組大小，每個頁面 (貨架) 上可存放 8 個結構體 (貨物)。
- 假如申請的結構體 (貨物) 大小是 2050 位元組，那麼頁面 (貨架) 可選擇 8K 位元組大小，每個頁面 (貨架) 上可以存放 3 個結構體 (貨物)。
實際計算時，第二種情況的值可能不是如此，因為這樣選擇會導致較大的記憶體空間浪費，核心可能選擇更大的頁面，以減少記憶體浪費的發生。
該結構體是 slab cache 的存取介面。每種類型的物件都有一個對應的 kmem_cache 實例，並且每個大小的通用 cache 也有一個實例。它用來管理給定物件類型/大小的所有 slab。
+------------------------------+
|name |
| (char *) |
+------------------------------+
|object_size | = original object size
|inuse | = ALIGN(object_size, sizeof(void *))
|size | = ALIGN(inuse + padding + debug space, s->align)
|align |
|offset |
| (int) |
|reserved |
+------------------------------+
|oo |
|min |
|max |
| (kmem_cache_order_objects) |
| +--------------------------+
| |order |
| |order_objects |
+---+--------------------------+
該結構體的重要成員：
const char *name: slab cache 的名稱，如kmalloc-32等unsigned int object_size: cache 中物件的大小unsigned int size: 包括 metadata 的物件大小，如果存在 metadatastruct kmem_cache_cpu __percpu *cpu_slab: 指向struct kmem_cache_cpu的指標，並非尋常的指標，而是個__per_cpu指標，意味著地址空間不同，即需要額外的運算來取得kmem_cache_cpu物件的實際地址struct kmem_cache_node *node[MAX_NUMNODES]: 指向kmem_cache_node結構體陣列的指標unsigned int offset: 在物件中的偏移量，指向下個空閒物件的指標儲存位置（當物件在 freelist 中時）。unsigned long random：僅在設定CONFIG_SLAB_FREELIST_HARDENED時存在，用於變更 freelist 中指標的地址unsigned int *random_seq：僅在設定CONFIG_SLAB_FREELIST_RANDOM時存在。這是一個隨機序列，以確保初始 freelist (建立 slab 時包含所有物件) 並非循序，而是隨機順序。換言之，意味著物件不會在開始時按順序配置
名為 slab_caches 的變數是個包含所有 slab cache 的雙向鏈結串列。名為 kmalloc_caches 的變數則包含所有的 kmalloc (通用) cache，其第一個索引表示 kmalloc 的 cache 類型，如下：
KMALLOC_NORMAL= 0: 對應於名為kmalloc-8,kmalloc-16等的 cacheKMALLOC_CGROUP：對應於名為kmalloc-cg-8,kmalloc-cg-16等的 cacheKMALLOC_RECLAIM：對應於名為kmalloc-rcl-8,kmalloc-rcl-16等的 cacheKMALLOC_DMA：對應於名為dma-kmalloc-8,dma-kmalloc-16等的 cache
第二個索引表示該 cache 中的物件大小。索引 n 對應於 kmalloc-2n，其中包含大小從
該結構管理目前 CPU 的有效 slab。該結構體的重要成員如下：
void **freelist: 指向 slab 中下個可用物件的指標，亦即這個 slab 中的下次配置將返回此指標指向的地址struct slab *slab: 指向有效 slab 的指標
該結構體跟蹤部分 slab (亦即有空間的 slab)，而非有效的 slab。根據配置，它還跟蹤已滿的 slab。該結構體的重要成員如下：
unsigned long nr_partial：部分 slab 的數量struct list_head partial：部分 slab 的串列struct list_head full：僅在設定CONFIG_SLUB_DEBUG時定義，是已滿 slab 的串列
該結構體包含一個 slab 的 metadata，包含以下：
struct kmem_cache *slab_cache: 該 slab 所屬的 slab cache，由 kmem_cache 表示void *freelist: slab 中第一個空閒物件
建立 kmem_cache 結構體
kmem_cache 結構體是 SLUB 進行配置時的中心節點。在該節點上，我們可獲得所有關於這個 SLUB 的資訊。前述 kmem_cache 結構體內部的成員在建立後就不會改變，主要用來儲存 SLUB 的大小資訊，這裡我們關注以下：
- cpu_slab
- NUMA node
可見 SLUB 引入二個層級來管理記憶體：per-CPU 層級和 NUMA 節點 層級。下圖展示 kmem_cache 剛建立時的樣貌，可見一切都剛開始，內容都是空的。
kmem_cache
+------------------------------+
|name |
| (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| |tid | #cpu
| | (unsigned long) |
| |freelist (void **) | NULL
| |page (struct page *) | NULL
| |partial (struct page *) | NULL
+---+--------------------------+
|node[MAX_NUMNODES] |
| (struct kmem_cache_node*) |
| +--------------------------+
| |list_lock |
| | (spinlock_t) |
| |nr_partial | 0
| | (unsigned long) |
| |partial | empty
| | (struct list_head) |
+---+--------------------------+
配置記憶體
由於採用分層設計，SLUB 配置時根據每個層次是否存在記憶體區分為幾種情況。在 Linux 核心運作過程，SLUB 按照以下順序檢查是否有可用的記憶體：
- cpu_slab
- cpu_slab
- node
原理不難懂，就是先檢查最容易取得的空間是否有可用記憶體。以下展現 SLUB 在不同狀況下的樣貌。
- 什麼地方都沒有記憶體
按照上述順序，這個過程應該是以上三個空間中都沒有記憶體的情況。不過這也是 SLUB 剛建立後第一次配置時的情況，就是從 buddy 系統中取得一個頁面，裝到 cpu_slab allocate_slab()。
這種情況的初始狀態是所有空間都是空的，但在下圖中展示二個狀態，目的是為了突出 page
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist |
| | (void **) |
| | |
| |page +--|--->+--------+--------+--------+--------+
| | (struct page *) | | | | | | |
| | +-------------------|--+ +--------+--------+--------+--------+
| | |freelist ---+ |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| |partial | = NULL
| | (struct page *) |
+---+--------------------------+
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist ------|----+ = page->freelist
| | (void **) | |
| | | v
| |page | +--------+--------+--------+--------+
| | (struct page *) | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| |partial | = NULL
| | (struct page *) |
+---+--------------------------+
- freelist 上有記憶體
該情況也稱為 fast path，因為在該情況下，只需移動 freelist 指標即可，這步執行於 slab_alloc_node()。
下圖展示 freelist 從 a 移動到 A。注意 freelist 保存的是一個鏈結串列，而非線性儲存，因此指標的變化不一定是後移。
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | | a A
| |freelist ------|-------------+..................
| | (void **) | | .
| | | v v
| |page | +--------+--------+--------+--------+
| | (struct page *) | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| | |
| |partial | = NULL
| | (struct page *) |
+---+--------------------------+
- partial 上有記憶體
這時需要從 partial 中找到可用的頁面，裝到 freelist 上。這步執行於 ___slab_alloc() 和 get_freelist()。
下面二圖分別展現裝之前和之後的變化，可見原來在 partial 中的頁面 A，安裝後移到 cpu_slab
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist | = NULL
| | (void **) |
| |page | = NULL
| | (struct page *) |
| | |
| |partial ------|--->+-----------+ +-----------+
| | (struct page *) | |A next|---->|B next|
| | | +-----------+ +-----------+
| | | |pobjectsA | = |pobjectsB | + objectsA
| | | | | | |
| | | |inuse < | |inuse < |
| | | | objectsA | | objectsB |
| | | |frozen = 1 | |frozen = 1 |
| | | +-----------+ +-----------+
+---+--------------------------+
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist ------|----+ = page->freelist
| | (void **) | |
| | | v
| |page | +--------+--------+--------+--------+
| | (struct page *) A | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| | |
| |partial ------|--->+-----------+
| | (struct page *) | |B next|
| | | +-----------+
| | | |pobjectsB | = objectsB
| | | | |
| | | |inuse < |
| | | | objectsB |
| | | |frozen = 1 |
| | | +-----------+
+---+--------------------------+
- node 上有記憶體
看完 freelist 和 partial，最後我們來看 cpu_slab new_slab_objects() get_partial() get_partial_node()。
注意在某些情況下，不僅會將頁面裝入 freelist 中，還會取出多個頁面裝入 partial 中，避免下次配置時找不到可用的記憶體。下圖展示的頁面 B 就是從 node 轉移到 partial 上。此外，在 node 上的頁面中，frozen 為 0。
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist | = NULL
| | (void **) |
| |page | = NULL
| | (struct page *) |
| | |
| |partial | = NULL
| | (struct page *) |
| | |
+---+--------------------------+
|node[MAX_NUMNODES] |
| (struct kmem_cache_node*) |
| +--------------------------+
| |nr_partial = 3 |
| | (unsigned long) |
| |partial ----|--->+-----------+ +-----------+ +-----------+
| | (struct list_head) | |A lru|---->|B lru|---->| lru|
+---+--------------------------+ +-----------+ +-----------+ +-----------+
|inuse < | |inuse < |
| objects | | objects |
|frozen = 0 | |frozen = 0 |
+-----------+ +-----------+
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist ------|----+ = page->freelist
| | (void **) | |
| | | v
| |page | +--------+--------+--------+--------+
| | (struct page *) A | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| | |
| |partial ------|--->+-----------+
| | (struct page *) | |B next|
| | | +-----------+
| | | |pobjects | = objects
| | | | |
| | | |inuse < |
| | | | objects |
| | | |frozen = 1 |
| | | +-----------+
| | |
+---+--------------------------+
|node[MAX_NUMNODES] |
| (struct kmem_cache_node*) |
| +--------------------------+
| |nr_partial = 1 |
| | (unsigned long) |
| |partial ----|--->+-----------+
| | (struct list_head) | |C lru|
+---+--------------------------+ +-----------+
釋放記憶體
釋放雖然是配置的另一面，但在細節與 SLUB 配置略有不同。由於 SLUB 的設計是個鏈結串列，所以無論需要釋放記憶體對應的頁面在哪個地方，都是在 freelist 鏈結串列的開頭插入一個物件。因此，單個物件的釋放沒有太大區別。區別在於釋放物件後，需要將對應的頁面移動到適當的位置。
SLUB 釋放記憶體階段需要在以下三個位置之間移動頁面：
- cpu_slab
- cpu_slab
- node
- 移動 freelist
該情況相對簡單，不涉及頁面的移動，只要移動 cpu_slab
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | | obj
| |freelist ------|-------------+..................
| | (void **) | | .
| | | v v
| |page | +--------+--------+--------+--------+
| | (struct page *) | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| | |
| |partial | = NULL
| | (struct page *) |
+---+--------------------------+
- 替換 cpu_slab->page
該情況發生於配置記憶體時，當 cpu_slab deactivate_slab() 實作。
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist ------|----+ = page->freelist
| | (void **) | |
| | | v
| |page | +--------+--------+--------+--------+
| | (struct page *) A | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| | |
| |partial ------|--->+-----------+
| | (struct page *) | |B next|
| | | +-----------+
| | | |pobjects | = objects
| | | | |
| | | |inuse < |
| | | | objects |
| | | |frozen = 1 |
| | | +-----------+
| | |
+---+--------------------------+
|node[MAX_NUMNODES] |
| (struct kmem_cache_node*) |
| +--------------------------+
| |nr_partial = 1 |
| | (unsigned long) |
| |partial ----|--->+-----------+
| | (struct list_head) | |C lru|
+---+--------------------------+ +-----------+
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist | = NULL
| | (void **) |
| |page | = NULL
| | (struct page *) |
| | |
| |partial ------|--->+-----------+
| | (struct page *) | |B next|
| | | +-----------+
| | | |pobjects | = objects
| | | | |
| | | |inuse < |
| | | | objects |
| | | |frozen = 1 |
| | | +-----------+
| | |
+---+--------------------------+
|node[MAX_NUMNODES] |
| (struct kmem_cache_node*) |
| +--------------------------+
| |nr_partial = 1 |
| | (unsigned long) |
| |partial ----|--->+-----------+ +-----------+
| | (struct list_head) | |A lru|---->|C lru|
+---+--------------------------+ +-----------+ +-----------+
|inuse < |
| objects |
|frozen = 0 |
+-----------+
- 解凍 cpu_slab
當偵測到 cpu_slab
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist ------|----+ = page->freelist
| | (void **) | |
| | | v
| |page | +--------+--------+--------+--------+
| | (struct page *) A | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| | |
| |partial ------|--->+-----------+ +-----------+
| | (struct page *) | |B next|---->|C next|
| | | +-----------+ +-----------+
| | | |pobjectsA | = |pobjectsB | + objectsA
| | | | | | |
| | | |inuse < | |inuse < |
| | | | objectsA | | objectsB |
| | | |frozen = 1 | |frozen = 1 |
| | | +-----------+ +-----------+
| | |
+---+--------------------------+
|node[MAX_NUMNODES] |
| (struct kmem_cache_node*) |
| +--------------------------+
| |nr_partial = 1 |
| | (unsigned long) |
| |partial ----|--->+-----------+
| | (struct list_head) | |D lru|
+---+--------------------------+ +-----------+
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist ------|----+ = page->freelist
| | (void **) | |
| | | v
| |page | +--------+--------+--------+--------+
| | (struct page *) A | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| | |
| |partial | = NULL
| | (struct page *) |
| | |
+---+--------------------------+
|node[MAX_NUMNODES] |
| (struct kmem_cache_node*) |
| +--------------------------+
| |nr_partial = 1 |
| | (unsigned long) |
| |partial ----|--->+-----------+ +-----------+ +-----------+
| | (struct list_head) | |B lru|---->|C lru|---->|D lru|
+---+--------------------------+ +-----------+ +-----------+ +-----------+
|inuse < | |inuse < |
| objects | | objects |
|frozen = 0 | |frozen = 0 |
+-----------+ +-----------+
- 從 node
特定狀況下，我們會將 node
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist ------|----+ = page->freelist
| | (void **) | |
| | | v
| |page | +--------+--------+--------+--------+
| | (struct page *) A | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| | |
| |partial ------|--->+-----------+
| | (struct page *) | |B next|
| | | +-----------+
| | | |pobjectsB | = objectsB
| | | | |
| | | |inuse < |
| | | | objectsB |
| | | |frozen = 1 |
| | | +-----------+
| | |
+---+--------------------------+
|node[MAX_NUMNODES] |
| (struct kmem_cache_node*) |
| +--------------------------+
| |nr_partial = 3 |
| | (unsigned long) |
| |partial ----|--->+-----------+ +-----------+
| | (struct list_head) | |C lru|---->|D lru|
+---+--------------------------+ +-----------+ +-----------+
|inuse < |
| objects |
|frozen = 0 |
+-----------+
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist ------|----+ = page->freelist
| | (void **) | |
| | | v
| |page | +--------+--------+--------+--------+
| | (struct page *) A | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| | |
| |partial ------|--->+-----------+ +-----------+
| | (struct page *) | |C next|---->|B next|
| | | +-----------+ +-----------+
| | | |pobjectsC | = |pobjectsB | + objectsC
| | | | | | |
| | | |inuse < | |inuse < |
| | | | objectsC | | objectsB |
| | | |frozen = 1 | |frozen = 1 |
| | | +-----------+ +-----------+
| | |
+---+--------------------------+
|node[MAX_NUMNODES] |
| (struct kmem_cache_node*) |
| +--------------------------+
| |nr_partial = 1 |
| | (unsigned long) |
| |partial ----|--->+-----------+
| | (struct list_head) | |C lru|
+---+--------------------------+ +-----------+
- 將頁面加入 node
當一個頁面的所有空間都被配置後，該頁面就不會出現在其他位置 (除非是 Linux 啟用 CONFIG_SLUB_DEBUG 選項）。當釋放頁面上的一個物件時，該頁面會重新出現在 node
為了清晰起見，下圖展示在 Linux 核心在啟用 CONFIG_SLUB_DEBUG 時，node->full 鏈結串列的開頭，以表示頁面的移動情況。
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist ------|----+ = page->freelist
| | (void **) | |
| | | v
| |page | +--------+--------+--------+--------+
| | (struct page *) A | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| | |
| |partial ------|--->+-----------+
| | (struct page *) | |B next|
| | | +-----------+
| | | |pobjectsB | = objectsB
| | | | |
| | | |inuse < |
| | | | objectsB |
| | | |frozen = 1 |
| | | +-----------+
| | |
+---+--------------------------+
|node[MAX_NUMNODES] |
| (struct kmem_cache_node*) |
| +--------------------------+
| |nr_partial = 3 |
| | (unsigned long) |
| |partial ----|--->+-----------+ +-----------+
| | (struct list_head) | |C lru|---->|D lru|
| +--------------------------+ +-----------+ +-----------+
| |full ----|--->+-----------+
| | (struct list_head) | |E lru|
+---+--------------------------+ +-----------+
kmem_cache
+------------------------------+
|name (char *) |
+------------------------------+
|cpu_slab | * per cpu variable pointer
| (struct kmem_cache_cpu*) |
| +--------------------------+
| |stat[NR_SLUB_STAT_ITEMS] |
| | (unsigned) |
| +--------------------------+
| |tid (unsigned long) |
| | |
| |freelist ------|----+ = page->freelist
| | (void **) | |
| | | v
| |page | +--------+--------+--------+--------+
| | (struct page *) A | | | | | |
| | +----------------------+ +--------+--------+--------+--------+
| | |freelist = NULL |
| | |inuse = objects |
| | |frozen = 1 |
| | +----------------------+
| | |
| |partial ------|--->+-----------+
| | (struct page *) | |B next|
| | | +-----------+
| | | |pobjectsB | = objectsB
| | | | |
| | | |inuse < |
| | | | objectsB |
| | | |frozen = 1 |
| | | +-----------+
| | |
+---+--------------------------+
|node[MAX_NUMNODES] |
| (struct kmem_cache_node*) |
| +--------------------------+
| |nr_partial = 3 |
| | (unsigned long) |
| |partial ----|--->+-----------+ +-----------+ +-----------+
| | (struct list_head) | |E lru|---->|C lru|---->|D lru|
| +--------------------------+ +-----------+ +-----------+ +-----------+
| |full | = NULL
| | (struct list_head) |
+---+--------------------------+
SLUB 的安全強化機制
一些與 freelist 相關的核心選項如下：
CONFIG_SLAB_FREELIST_HARDENED
亦即安全強化的的 freelist，啟用此選項後，freelist 中的指標將通過與每個 cache 的隨機數 (s->random) 和指標儲存地址 (ptr_addr) 進行 XOR 運算，以增加攻擊者猜測的難度：
/*
* Returns freelist pointer (ptr). With hardening, this is obfuscated
* with an XOR of the address where the pointer is held and a per-cache
* random number.
*/
static inline void *freelist_ptr(const struct kmem_cache *s, void *ptr,
unsigned long ptr_addr)
{
#ifdef CONFIG_SLAB_FREELIST_HARDENED
/* ... */
return (void *)((unsigned long)ptr ^ s->random ^
swab((unsigned long)kasan_reset_tag((void *)ptr_addr)));
#else
return ptr;
#endif
}
若存在一個漏洞允許攻擊者覆蓋這些指標，為了成功攻擊，他們需要知道 s->random 和 ptr_addr（這有可能發生，但難度更大）。
CONFIG_SLAB_FREELIST_RANDOMIZATION
對 freelist 進行隨機化，在 Linux v4.8 中引入，啟用後，freelist 中區塊的初始順序不再是連續的。亦即原本當 slab 建立時，所有區塊都是空閒的，且是 freelist 的一部分。但若若啟用 CONFIG_SLAB_FREELIST_RANDOMIZATION 選項，配置將不再按它們在 slab 中的順序 (第一個配置返回 slab 中的第一個區塊，依此類推)，而是按隨機順序。這由每個 cache 隨機序列（s->random_seq）決定（在 cache 初始化時定義），並且 cache 中的每個 slab 都從這個序列中隨機選擇一個起點 (這樣不同 slab 中的配置不會從相同的偏移量開始)。
此舉減輕核心 heap overflow 的風險，在此之前，若易受攻擊的物件和目標物件一個接一個地配置，它們總是相鄰的，因此很容易被攻擊者所利用。然而，這可透過配置許多目標物件，然後釋放其中一個，接著配置一個易受攻擊的物件來輕易繞過。事實上，易受攻擊的物件將被目標物件包圍，然後我們可觸發 heap overflow，並覆蓋其中一個目標物件。Michael S 和 Vitaly Nikolenko 撰寫的文章〈Linux kernel heap feng shui in 2022〉清楚解釋這點，feng shui 即「風水」的拼音。
待整理
- hardened_malloc
- SlabDbg: GDB plug-in that makes it easier to develop Linux kernel exploits targeting the SLUB allocator.
