# slab 記憶體配置器
> 資料整理: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv)
## 簡介
slab 一詞源於 SunOS 原始程式碼，開發者選擇這詞彙，是相較於 "object" 或 "cache"，slab 更具辨識度，該詞彙的[原意](https://dictionary.cambridge.org/dictionary/english/slab)是針對石、木、金屬、食物等的板或片段。根據 Jeff Bonwick 發表在 1994 年的論文〈[The slab Allocator: An Object-Caching Kernel](https://www.usenix.org/conference/usenix-summer-1994-technical-conference/slab-allocator-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。
當 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](https://github.com/bbu/userland-slab-allocator) 提供文字模式的 slab 配置動態展示。
## 實作示範
儘管 Jeff Bonwick 描述的 slab 起初用於核心物件的管理，但同樣適用於使用者空間。記憶體配置器請求一個頁面大小的記憶體區塊，並將其分割成固定大小的片段。每個片段可以容納一個指標或整數，並鏈接成一個串列，串列的頭部指向第一個空閒節點。
以下是 Marek Vavrusa 提供的[實作程式碼](https://marek.vavrusa.com/memory/):
```c
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 指標。
```c
/* 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
以下是 Linux 核心的用語:
* slab: 一組包含一個或多個連續頁面的記憶體，這些頁面包含特定大小的核心物件。
* slab cache: 多個相同類型 slab 的容器。有兩種類型的 cache：
- 專用 cache: 由 Linux 核心建立，每個 cache 僅用於保存一種（常用）物件類型，例如 `mm_struct` 或 `cred_jar`
- 通用 cache: 可容納任何特定大小 (加上 padding) 的物件。通常，這些 cache 中的物件大小為 2 的冪。當呼叫 `kmalloc()` 時，返回的已配置記憶體將在這些 cache 之一（例如 `kmalloc-32`, `kmalloc-64` 等）中，實際則取決於請求的大小。
* SLOB / SLAB / SLUB: 都是 Linux 核心中可用的 slab 配置器，較新的 Linux 核心版本已棄置 slob 和 slab，因此新的 Linux 僅提供 SLUB 這個 slab 的改進版本。
要顯示不同 slab cache 的資訊，我們可執行以下命令:
```shell
$ 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` 對應的頁面。
用更細緻的案例來解說：
1. 假如申請的結構體 (貨物) 大小是 512 位元組，那麼頁面 (貨架) 可選擇 4K 位元組大小，每個頁面 (貨架) 上可存放 8 個結構體 (貨物)。
2. 假如申請的結構體 (貨物) 大小是 2050 位元組，那麼頁面 (貨架) 可選擇 8K 位元組大小，每個頁面 (貨架) 上可以存放 3 個結構體 (貨物)。
實際計算時，第二種情況的值可能不是如此，因為這樣選擇會導致較大的記憶體空間浪費，核心可能選擇更大的頁面，以減少記憶體浪費的發生。
- [ ] [`struct kmem_cache`](https://elixir.bootlin.com/linux/v6.9.2/source/mm/slab.h#L251)
該結構體是 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 object_size` : 包括 metadata 的物件大小，如果存在 metadata
* `struct 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` 等的 cache
* `KMALLOC_CGROUP`：對應於名為 `kmalloc-cg-8`, `kmalloc-cg-16` 等的 cache
* `KMALLOC_RECLAIM`：對應於名為 `kmalloc-rcl-8`, `kmalloc-rcl-16` 等的 cache
* `KMALLOC_DMA`：對應於名為 `dma-kmalloc-8`, `dma-kmalloc-16` 等的 cache
第二個索引表示該 cache 中的物件大小。索引 n 對應於 kmalloc-2^n^，其中包含大小從 $2^{n-1}+1$ 到 $2^{n}$ 的物件。
- [ ] [`struct kmem_cache_cpu`](https://elixir.bootlin.com/linux/v6.9.2/source/mm/slub.c#L384)
該結構管理目前 CPU 的有效 slab。該結構體的重要成員如下：
* `void **freelist` : 指向 slab 中下個可用物件的指標，亦即這個 slab 中的下次配置將返回此指標指向的地址
* `struct slab *slab` : 指向有效 slab 的指標
- [ ] [`struct kmem_cache_node`](https://elixir.bootlin.com/linux/v6.9.2/source/mm/slub.c#L425)
該結構體跟蹤部分 slab (亦即有空間的 slab)，而非有效的 slab。根據配置，它還跟蹤已滿的 slab。該結構體的重要成員如下：
* `unsigned long nr_partial`：部分 slab 的數量
* `struct list_head partial`：部分 slab 的串列
* `struct list_head full`：僅在設定 `CONFIG_SLUB_DEBUG` 時定義，是已滿 slab 的串列
- [ ] [`struct slab`](https://elixir.bootlin.com/linux/v6.9.2/source/mm/slab.h#L52)
該結構體包含一個 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 $\to$ freelist
* cpu_slab $\to$ partial
* node $\to$ partial
原理不難懂，就是先檢查最容易取得的空間是否有可用記憶體。以下展現 SLUB 在不同狀況下的樣貌。
- [ ] 什麼地方都沒有記憶體
按照上述順序，這個過程應該是以上三個空間中都沒有記憶體的情況。不過這也是 SLUB 剛建立後第一次配置時的情況，就是從 buddy 系統中取得一個頁面，裝到 cpu_slab $\to$ freelist 中。這步執行於 `allocate_slab()`。
這種情況的初始狀態是所有空間都是空的，但在下圖中展示二個狀態，目的是為了突出 page $\to$ freelist 指標的變化。
```
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 $\to$ page。注意在 partial 上的頁面，frozen 也是 1，但 inuse 則反映真實的配置情況而不是等於 objects。
```
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 $\to$ node 上有記憶體的情況。在該情況，我們需要從 node 上取出頁面，並將其裝入 freelist 中。該過程執行於 `new_slab_objects()` $\to$ `get_partial()` $\to$ `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 $\to$ freelist
* cpu_slab $\to$ partial
* node $\to$ partial
- [ ] 移動 freelist
該情況相對簡單，不涉及頁面的移動，只要移動 cpu_slab $\to$ freelist 即可。
```
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 $\to$ page 無法滿足配置需求時，而將這個頁面退回到 node $\to$ partial。過程由 `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 $\to$ partial
當偵測到 cpu_slab $\to$ partial 上的物件數量足夠多時，系統會將鏈結串列上的所有頁面退回到 node $\to$ partial。注意該過程會將 cpu_slab $\to$ partial 清空。
```
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 $\to$ partial 取出一個頁面加入 cpu_slab $\to$ partial
特定狀況下，我們會將 node $\to$ partial 鏈結串列中的一個頁面放到 cpu_slab $\to$ partial 上。
```
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 $\to$ partial
當一個頁面的所有空間都被配置後，該頁面就不會出現在其他位置 (除非是 Linux 啟用 `CONFIG_SLUB_DEBUG` 選項）。當釋放頁面上的一個物件時，該頁面會重新出現在 node $\to$ partial 上。
為了清晰起見，下圖展示在 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 運算，以增加攻擊者猜測的難度：
```c
/*
* 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](https://duasynt.com/blog/linux-kernel-heap-feng-shui-2022)〉清楚解釋這點，feng shui 即「風水」的拼音。
## 待整理
* [hardened_malloc](https://github.com/GrapheneOS/hardened_malloc)
* [SlabDbg](https://github.com/NeatMonster/slabdbg): GDB plug-in that makes it easier to develop Linux kernel exploits targeting the SLUB allocator.
Sign in with Wallet
Connect another wallet