LWN：實(shí)現(xiàn)maple tree！
關(guān)注了就能看到更多這么棒的文章哦～
Introducing maple trees
February 12, 2021
This article was contributed by Marta Rybczyńska
DeepL assisted translation
https://lwn.net/Articles/845507/
在外界看來(lái)，Linux 內(nèi)核的內(nèi)部似乎變化很少，尤其是像內(nèi)存管理子系統(tǒng)（memory-management subsystem）這樣的子系統(tǒng)。然而，開(kāi)發(fā)人員時(shí)常需要更換內(nèi)部接口來(lái)解決某些長(zhǎng)期存在的問(wèn)題。比如，其中一個(gè)問(wèn)題就是用來(lái)保護(hù)內(nèi)存管理里的重要結(jié)構(gòu)的鎖的競(jìng)爭(zhēng)問(wèn)題，這些重要結(jié)構(gòu)是指頁(yè)表（page table）和虛擬內(nèi)存區(qū)域（VMA, virtual memory area）等。Liam Howlett 和 Matthew Wilcox 一直在開(kāi)發(fā)一種新的數(shù)據(jù)結(jié)構(gòu)，稱(chēng)為 "maple tree"，希望能取代目前用于 VMA 管理的數(shù)據(jù)結(jié)構(gòu)。這個(gè)改動(dòng)可能對(duì)內(nèi)核內(nèi)部結(jié)構(gòu)造成巨大變化，作者已經(jīng)公布了一個(gè)改動(dòng)很大的 patch set 來(lái)召喚 review。
Linux 是一個(gè)虛擬內(nèi)存(virtual-memory)系統(tǒng)。每個(gè)進(jìn)程的地址空間中包含多個(gè)虛擬內(nèi)存區(qū)域（VMA），都是由 vm_area_struct 結(jié)構(gòu)表示。每個(gè) vma 都代表一塊連續(xù)的地址空間，并且這部分區(qū)域都是屬于相同的內(nèi)存類(lèi)型，也就是可以是 anonymous memory（匿名內(nèi)存，內(nèi)容并不與某個(gè)文件對(duì)應(yīng)）、memory-mapped file（內(nèi)存映射文件），甚至是 device memory（設(shè)備內(nèi)存）。從進(jìn)程的角度來(lái)看，一個(gè) VMA 區(qū)域都是連續(xù)的，而實(shí)際上底層的物理內(nèi)存區(qū)域可能并不連續(xù)。此外，整個(gè)地址空間在各個(gè) VMA 之間是有空洞的，當(dāng)內(nèi)核需要映射產(chǎn)生一個(gè)新的區(qū)域時(shí)（例如在加載一個(gè)庫(kù)文件或者響應(yīng) mmap()調(diào)用時(shí)），內(nèi)核就會(huì)從這些空洞分配出虛擬空間從而利用起來(lái)（當(dāng)然還是會(huì)預(yù)留一些未映射的 "guard" page，有利于減少緩沖區(qū)溢出的危害）。
我們的系統(tǒng)中幾乎所有工作都涉及到內(nèi)存，所以對(duì)這些表示 VMA 的結(jié)構(gòu)的操作必須要快。這些操作包括 lookup（查找，也就是找出哪個(gè) VMA 是對(duì)應(yīng)某個(gè)虛擬地址的、確認(rèn)內(nèi)存是否被 map 過(guò)，或者尋找一個(gè)空閑區(qū)域用于分配新的 VMA），以及修改（例如，增大堆?？臻g）。
VMA 目前是通過(guò)一個(gè)紅黑樹(shù)（rbtree，red-black tree）的變種來(lái)管理的，針對(duì)紅黑樹(shù)來(lái)說(shuō)增加了一個(gè)額外的雙向鏈表，用來(lái)讓內(nèi)核遍歷某個(gè)進(jìn)程地址空間中的所有 VMA。內(nèi)核開(kāi)發(fā)者對(duì)這種數(shù)據(jù)結(jié)構(gòu)的不滿(mǎn)已經(jīng)有一段時(shí)間了，原因有很多：rbtree 不能很好地支持范圍（ranges），難以用 lockless（不需要獲取鎖）的方式來(lái)進(jìn)行操作（rbtree 需要進(jìn)行 balance 操作，這會(huì)同時(shí)影響多個(gè) item），而且 rbtree 遍歷的效率很低，這也是為什么需要一個(gè)額外的雙向鏈表。
對(duì) VMA 的操作會(huì)使用一個(gè) lock 來(lái)保護(hù)（具體來(lái)說(shuō)是一個(gè) reader/writer semaphore），這個(gè) lock 位于 struct mm_struct 中，此前名為 mmap_sem，2020 年 6 月的 5.8 版本將其改名為 mmap_lock。改名是為了能將對(duì)這個(gè) lock 的操作都用 API 包裝起來(lái)，希望將來(lái)替換的時(shí)候方便。
用戶(hù)經(jīng)常會(huì)碰到爭(zhēng)搶這個(gè) lock 的情況，尤其是那些在大型系統(tǒng)中使用多線程應(yīng)用的用戶(hù)。內(nèi)核開(kāi)發(fā)者已經(jīng)多次討論過(guò)這個(gè)問(wèn)題，在 2019 年的 Linux Storage, Filesystem, and Memory-Management Summit (LFSMM) 峰會(huì)上至少有三次討論過(guò)這個(gè)問(wèn)題。問(wèn)題的核心是，許多操作都需要獲取 lock，這包括幾乎全部的涉及 page table 和 VMA 的操作。還有其他一些相關(guān)的結(jié)構(gòu)事實(shí)上也被 mmap_lock 地保護(hù)起來(lái)（麻煩的是相關(guān)文檔也是缺失的）。開(kāi)發(fā)者們?cè)谧龅氖虑槌藢⒉幌嚓P(guān)的結(jié)構(gòu)從 mmap_lock 保護(hù)下拆分出來(lái)之外，還在考慮使用一個(gè)結(jié)構(gòu)能允許 VMA 的訪問(wèn)變成 lockless 模式，或者使用某種類(lèi)型的 range lock。當(dāng)時(shí)有人提出了 maple tree 結(jié)構(gòu)作為解決方案之一，但當(dāng)時(shí) maple tree 還處于早期開(kāi)發(fā)狀態(tài)，代碼還沒(méi)有完成。
Introducing maple trees
maple tree（取這個(gè)名字可能是借用了楓葉的形狀，意指能走向多個(gè)方向）與 rbtrees 有根本性的差異。它們屬于 B-tree 類(lèi)型(https://en.wikipedia.org/wiki/B-tree)，也就是說(shuō)它們的每個(gè)節(jié)點(diǎn)可以包含兩個(gè)以上的元素，leaf node（葉子節(jié)點(diǎn)）中最多包含 16 個(gè)元素，而 internal node（內(nèi)部節(jié)點(diǎn)）中最多包含 10 個(gè)元素。使用 B-trees 也會(huì)導(dǎo)致很少需要?jiǎng)?chuàng)建新的 node，因?yàn)?node 可能包含一些空余空間，可以隨著時(shí)間的推移而填充利用起來(lái)，這就不需要額外進(jìn)行分配了。每個(gè) node 最多需要 256 字節(jié)，這是常用的 cache line size 的整數(shù)倍。node 中增加的元素?cái)?shù)量以及 cache-aligned size 就意味著在遍歷樹(shù)時(shí)會(huì)減少 cache-miss。
maple tree 對(duì)搜索過(guò)程也有改進(jìn)，同樣是來(lái)自于 B-tree 結(jié)構(gòu)特點(diǎn)。在 B-tree 中，每個(gè) node 都有一些 key 鍵值，名為 "pivot"，它會(huì)將 node 分隔成 subtree（子樹(shù)）。在某個(gè) key 之前的 subtree 只會(huì)包含小于等于 key 的數(shù)據(jù)，而這個(gè) key 之后的子樹(shù)只包含大于 key 的值（并且小于下一個(gè) key 值）。
當(dāng)然，maple tree 的設(shè)計(jì)中也是按照 lockless 方式的要求來(lái)的，使用 read-copy-update (RCU) 方式。maple tree 是一個(gè)通用結(jié)構(gòu)，可以用在內(nèi)核的不同子系統(tǒng)中。第一個(gè)用到 maple tree 的地方就是用來(lái)替換 VMA 管理中用到的 rbtree 和雙向鏈表。作者之一 Liam Howlett 在一篇博客中解釋了設(shè)計(jì)由來(lái)(https://blogs.oracle.com/linux/the-maple-tree)。
Maple tree 提供了兩組 API：一個(gè)是簡(jiǎn)單 API ，一個(gè)是高級(jí) API。簡(jiǎn)單 API 使用 mtree_前綴來(lái)標(biāo)記相關(guān)功能，主結(jié)構(gòu) struct maple_tree 定義如下：
struct maple_tree {
spinlock_t ma_lock;
unsigned int ma_flags;
void __rcu *ma_root;
};
需要靜態(tài)初始化（static initialize）的話(huà)，可以使用 DEFINE_MTREE(name) 和 MTREE_INIT(name，flags)，后者會(huì)的 flags 目前只定義了兩個(gè) bit 選項(xiàng)，其中 MAPLE_ALLOC_RANGE 表示該樹(shù)將被用于分配 range，并且需要把多個(gè)分配區(qū)域之間的空間（gap）管理起來(lái)；MAPLE_USE_RCU 會(huì)激活 RCU mode，用在多個(gè) reader 的場(chǎng)景下。mtree_init() API 也使用相同的 flags，不過(guò)是用在動(dòng)態(tài)初始化（dynamic initialization）場(chǎng)景：
void mtree_init(struct maple_tree *mt, unsigned int ma_flags);
開(kāi)發(fā)者可以用這個(gè)函數(shù)來(lái) free 整個(gè) tree：
void mtree_destroy(struct maple_tree *mt);
可以用三個(gè)函數(shù)來(lái)給樹(shù)增加條目：mtree_insert()、mtree_insert_range()和 mtree_store_range()。前兩個(gè)函數(shù)只有在條目不存在的情況下才會(huì)添加，而第三個(gè)函數(shù)可以對(duì)現(xiàn)有的條目進(jìn)行覆蓋。它們的定義如下：
int mtree_insert(struct maple_tree *mt, unsigned long index,
void *entry, gfp_t gfp);
int mtree_insert_range(struct maple_tree *mt, unsigned long first,
unsigned long last, void *entry, gfp_t gfp);
int mtree_store_range(struct maple_tree *mt, unsigned long first,
unsigned long last, void *entry, gfp_t gfp);
mtree_insert()的參數(shù) mt 是指向 tree 的指針，index 就是 entry index，entry 是指向一個(gè)條目的的指針，有必要的話(huà)可以利用 gfp 來(lái)指定新增 tree node 的內(nèi)存分配參數(shù)（memory allocation flag）。mtree_insert_range() 會(huì)利用給出的 entry 數(shù)據(jù)來(lái)插入從 first 到 last 的一個(gè) range 范圍。這些函數(shù)成功時(shí)返回 0，否則返回負(fù)值，如果返回-EEXIST 就表示 key 已經(jīng)存在。mtree_store_range()與 mtree_insert_range()接受的參數(shù)相同，不同的是，它會(huì)替換相應(yīng) key 的任何現(xiàn)有條目。
有兩個(gè)函數(shù)可以用來(lái)從 tree 中獲取一個(gè)條目或刪除一個(gè)條目：
void *mtree_load(struct maple_tree *mt, unsigned long index);
void *mtree_erase(struct maple_tree *mt, unsigned long index);
要讀取一個(gè)條目的話(huà)，可以使用 mtree_load()，它的參數(shù)是一個(gè)指向 tree 的指針 mt ，以及所要讀取的數(shù)據(jù)的鍵值 index。該函數(shù)會(huì)返回一個(gè)指向該條目的指針，如果在 tree 中沒(méi)有找到鍵值，則返回 NULL。mtree_erase() 也是同樣的語(yǔ)法，用于從 tree 中刪除一個(gè) entry。它會(huì)從 tree 中刪除給定的 key，并返回相關(guān)的 entry，如果沒(méi)有找到，則返回 NULL。
簡(jiǎn)單的 API 不止上面這些，還有比如 mtree_alloc_range() 可以用來(lái)從 key space 中分配一個(gè) range。而高級(jí) API (用 mas_ 前綴標(biāo)記出來(lái)了) 則額外增加了遍歷整個(gè) tree 的迭代函數(shù)，以及使用 state variable 來(lái)訪問(wèn)后一個(gè)或者前一個(gè)元素。通過(guò)這種細(xì)粒度的操作，開(kāi)發(fā)者就可以根據(jù)需要來(lái)恢復(fù)中斷了的搜索。還有供開(kāi)發(fā)人員找到空閑區(qū)域或者對(duì) tree 進(jìn)行復(fù)制操作的 API。
Replacing the VMA rbtree (and more)
patch set 中不僅僅是引入了 maple tree。著重需要指出的是，這組 patch set 中有很大一部分是增加修改測(cè)試代碼，考慮到這個(gè)改動(dòng)會(huì)帶來(lái)的巨大影響，以及新的數(shù)據(jù)結(jié)構(gòu)在未來(lái)的重要性，這些測(cè)試代碼是非常值得鼓勵(lì)的。
這組 patch set 中有 70 個(gè) patch 將 VMA 的所有操作中的 rbtree 操作換成了 maple tree，其中一個(gè) patch 徹底在 VMA 中禁用了 rbtree。patch set 中另一部分代碼移除了 VMA 里的雙向鏈表。這個(gè)改動(dòng)需要修改內(nèi)核中所有直接地使用了 VMA 鏈表的代碼：體系架構(gòu)相關(guān)代碼，core dump 代碼，program 加載代碼，一些設(shè)備驅(qū)動(dòng)程序等，當(dāng)然還有 memory-management 代碼。patch set 里還刪除了 VMA cache（用來(lái)跟蹤每個(gè)進(jìn)程最近訪問(wèn)過(guò)的 VMA，從而加快 lookup 速度），這是因?yàn)槭褂?maple tree 實(shí)現(xiàn)后速度更快，不再需要 VMA cache 了。
Patch set 的第一封郵件中還包括了一些性能數(shù)據(jù) ，不過(guò)結(jié)果有些難以理解。一些 microbenchmark 的結(jié)果說(shuō)明性能提升了，而其他一些（數(shù)量較少）則說(shuō)明性能下降了。編譯內(nèi)核的時(shí)間與 5.10 內(nèi)核本身相類(lèi)似，只是多執(zhí)行了幾條指令（可能與添加的代碼有關(guān)）。Howlett 希望大家給些建議如何對(duì)這些結(jié)果進(jìn)行更深入的分析。
Current status and next steps
目前 Maple tree 還處于 RFC 階段，有一些缺點(diǎn)。比如說(shuō)，目前的實(shí)現(xiàn)不支持 32 位系統(tǒng)或 non-MMU 的平臺(tái)。不過(guò)，這些代碼已經(jīng)可以實(shí)際用起來(lái)了，內(nèi)核開(kāi)發(fā)者們可以研究一下，從而決定是否符合他們期望的方向（因?yàn)檫@組 patch set 并沒(méi)有去掉 mmap_lock ）。這個(gè) patch set 太大了，可能需要不少時(shí)間才能完成 review。
全文完
LWN 文章遵循 CC BY-SA 4.0 許可協(xié)議。
長(zhǎng)按下面二維碼關(guān)注，關(guān)注 LWN 深度文章以及開(kāi)源社區(qū)的各種新近言論～