從 radix tree 到 xarray

今天我們來討論一下內核中從radix tree到xarray結構的演變。 radix tree現在普遍應用於page cache中，用於搜索頁高速緩存。但是在Linux內核4.20版本之後便被xarray結構所替代。 xarray數據結構是2018 LSFMM峯會上最後一個文件系統會議的主題。它是內核的基數樹的一個新API。這個會議由Matthew Wilcox領導，是由他創造了xarray。這篇文章中我們會就page cache的含義到radix樹的結構，再到xarray的興起這一演變過程進行講解。

一、page cache

CPU想要訪問外部存儲介質譬如磁盤上的文件，首先要將文件的內容拷貝到內存中，但是由於硬件或者軟件設計上的限制，我們從磁盤到內存的傳輸速度比較慢，這時候我們便使用一些空餘內存，也就是DDR上的一部分空間來緩存一部分磁盤上的文件內容，這個部分空餘的內存我們就叫做page cache。用戶啓動read的系統調用之後，會從用戶層到VFS層面之後再到文件系統中，在文件系統的讀接口中會首先查看page cache中是否有用戶需要的文件內容，如果有就直接讀取，如果沒有在通過IO操作下發請求從磁盤讀取，然後放到page cache中，方便下次訪問。

這個原理和CPU中的硬件cache有點像，不過硬件cache是CPU緩存內存的數據。因爲內存有限我們不能緩存全部數據，只需要把調用的內容緩存起來就可以了，這種方式叫做demand paging（按需取頁）。在page cache中緩存了很多的頁，怎麼查找和管理呢？這時候就要關注一下address_space結構體，一個address_space管理了一個文件在內存中緩存的所有pages，這部分緩存也是頁高速緩存。這個address_space可不是進程虛擬地址空間的address space，但是兩者之間也是有很多聯繫的。mmap映射會將文件的一部分內容映射到虛擬地址空間的VMA，如果有5個進程，每個進程mmap同一個文件兩次（文件的不同部分），就會有10個VMA，但address_space只有一個，虛擬空間的VMA使用的是rbtree，下面會介紹到爲什麼不在rbtree上去做xarray。在inode的結構體中會有一個i_mapping指向這個結構體。下面看下這個結構體的內容：

host指向address_space對應文件的inode。
address_space中的page cache之前一直是用radix tree的數據結構組織的，tree_lock是訪問這個radix tree的spinlcok（現在已換成xarray）。
i_mmap是管理address_space所屬文件的多個VMAs映射的，用priority search tree的數據結構組織，i_mmap_lock是訪問這個priority search tree的spinlcok。
nrpages是address_space中含有的page frames的總數。
a_ops是關於page cache如何與磁盤（backing store）交互的一系列operations。

二、radix tree基本架構

我們現在介紹完了大體框架，現在來聊一下第一個主角radix tree。

radix tree採用的是key-value的方式插入和查找的，即利用一個長整型的數據快速找到其對應的對象指針。存儲和查找效率比較高，如內核中的內存管理、IDR等機制都在使用。下面咱們來看一下主要的數據結構。

shift成員用於指向當前節點slots的單位;

offset表示該節點在父節點的slot中偏移值;
count 表示當前節點有多少個slot已經被使用;
exceptional表示當前節點有多少個exceptional節點;
parent 指向父節點; 參數 root 指向根節點;
slots是個指針數組, 該數組既可以存儲下一級的節點, 也可以用於存儲即將插入的對象指針;
tags 用於標識當前節點;

這裏主要挑選一些重要的數據進行說明。

Radix tree是一個多叉搜索樹，存在插入、刪除、查找等操作，這系列的操作的時間複雜度是O(k)，樹的葉子結點是實際的數據條目，每個節點都有固定的指針數目指向子節點，這些指針也成爲了槽位slot，Linux內核使用radix樹快速定位文件緩存頁，下圖是一個普通的radix樹的樣例，樹的分叉是4，樹高爲4，樹的每個葉子節點可以快速定位8位文件內偏移，也就是可以定位4x4x4x4=256頁，圖中虛線爲搜索路徑。

圖1 四叉radix樹

在Linux的radix樹每個節點有64個slot，與數據類型long對應，也就是key，下面是一個3級節點的radix樹，每個數據條目一般可用3個6位的鍵值進行索引，一級使用6位，鍵值從左到右分別代表第1--3層的節點位置，沒有子節點的以及root節點在圖中不顯示。

圖2 3級節點radix樹

Radix樹每個節點有多少個slot主要取決於RADIX_TREE_MAP_SHIFT ，參考上面的宏定義，取值一般爲6，標識每個節點有2^6=64個節點，RADIX_TREE_MAP_SIZE，表示1個葉子結點可映射的頁數，如：1<<6=64，表示1個slot可映射64頁。當樹高爲1時，64個slot對應64個頁，當樹高爲2時，對應64*64個頁。

Tags是一個二維數組，RADIX_TREE_MAX_TAGS爲3代表的是3種tag類型，RADIX_TREE_TAG_LONGS定義slot數佔用的long類型長度個數。加入這個值爲64，也就是3*64的數組，這樣每一行代表一種tag的集合，假如tag[0]代表PAGE_CACHE_DIRTY，假如我們查到當前節點的tags[0]值爲1，那麼它的子樹節點就存在PAGE_CACHE_DIRTY節點，在我們查找PG_dirty的頁面時，就不用遍歷整個樹了，可以提高查找效率。Radix樹提供了一些關於tag的操作函數。這個大家可以去內核的/lib/radix-tree.c官網上去查看源碼。這裏就不細講了。

經過上面對radix樹的結構講解，看代碼就比較容易了。下面說說radix樹的基本操作插入、查找和刪除。

插入函數：

EXPORT_SYMBOL(radix_tree_insert);

①首先根據插入的條目的index值，創建對應的樹節點;

②之後將條目插入到節點的槽位slot中。

①計算當前樹的最大shift的爲多少, 即目前可以計量的單位爲多大(側面反應了樹的深度), maxindex變量保存當前樹能存儲index值範圍;

②如果當前條目的index值已經超過了當前樹所能計量的範圍, 則需要調用該函數拓展樹的深度, 使其可以順利插入條目;

③在shift>0的情況, 如果子節點爲空則繼續創建節點(新創建的節點會記錄該節點shift值和在其父節點的offset值), 並將其掛slot下(*slot = node_to_entry(child););

④根據index獲取node節點slots對應位置的值給child, 並返回了該位置的offset;

⑤形參記錄下要插入的節點和slot地址;

這個函數主要是將條目指針掛載到對應slot的上, 而且對當前節點中slot使用情況進行了計數，比較簡單。

查找函數：

①首先是計算了當前樹最大index範圍, 如果查找的index值超過該範圍, 則說明該index對應條目不在該樹中;

②節點指針的最後兩位是代表指針指向的節點類型，判斷是否是內部節點，也就是是否有下一級指向的節點，根據index從父節點開始獲取存儲了條目的葉子節點node(通過while循環), 因爲條目都存儲在葉子節點的slots中，當最後找到了對應條目後, 經過判斷髮現已經不是樹的節點則退出循環，radix_tree_descend對index進行了一個移位運算，進行shift值的移位運算。

舉個例子，查找index值是1550的item, 當shift爲6時, 則計算出的offset爲24, 獲取該父節點slots偏移爲24的值, 發現還是一個節點, 再次計算偏移, 1550%64後得到值爲14, 獲取該父節點slot指向的子節點偏移爲14的值, 發現該值不是一個節點, 則退出。在這其中便看到了一些關於RCU的操作。

刪除函數：

EXPORT_SYMBOL(radix_tree_delete_item);

①通過 index調用查找函數查找到對應的條目, 返回值即是;

②如果entry存在則繼續向下執行刪除函數;

③根據節點地址和對應的slot地址刪除該條目;

①根據slot地址獲取在slots中的偏移值;

②更換slot, 該函數的第二個參數表示條目, 賦值爲NULL, 表示清空了該slot下記錄的條目; 並且對slot計數進行減一操作;

③刪除node, 如果節點slots已經沒有掛載條目則需要進行刪除操作;

①如果該節點的slots上還有條目則, 判斷該節點是否爲root節點, 不是則立即返回, 否則將基數縮小到最小高度;

②根據該節點的信息, 對其父節點slots上對應的位置進行清零並進行計數減一操作;

③釋放該節點內存，接下來對刪除節點的父節點進行操作(因爲它父節點slots如果沒有掛有其他節點也需要刪除)。radix_tree_shrink功能是縮減樹的高度, 去除一些沒有使用的節點。

在數據庫中也有一種Adaptive Radix Tree（自適應基數/前綴樹，ART），這裏每個節點可以存儲任意長度的鍵切片，並不像Linux中固定64，有興趣的同學可以研究一下。

三、RCU機制

Radix樹中還有一個重要的特性是RCU（Read-Copy Update）。因爲頁高速緩存在各進程間不斷被訪問，需要考慮併發的情況，單獨使用鎖的機制不能滿足對讀取速度的需求，便採用RCU機制。RCU的基本思想是先創建一箇舊數據的空間，然後將數據更新到這個空間，最後再用新的數據替換掉舊的數據。以一個鏈表爲例：

此時一個指針p指向3這個節點，使用RCU來更新這個節點數據。首先分配一段內存空間來存儲用指針q來指向

然後將p指向的節點的數據以及與下一個節點4的關係都copy到q指向的內存地址中。

之後我們更新這個節點數據將3改成5。

修改完成後就要將更新發布，在發佈之後讀到的數據是更新後的，在發佈前讀到的是更新之前的數據。

等到所有引用舊數據的read動作結束後便釋放這部分內存區域。

重要的是，RCU中的read不用像rwlock中的read那樣，在write操作期間必須spin等待了。rcu_read_lock(),rcu_read_unlock()作用是禁止和啓用搶佔.因爲在讀者臨界區,不允許發生上下文切換. rcu_dereference()本身都是原子操作.因爲只是爲了cache一致性,插上了內存屏障.可以讓其它的讀者/寫者可以看到保護指針的最新值，radix樹接口中要時刻注意RCU的安全保護，這個令radix樹的使用上比較不便，這裏只是大致敘述一下，就不詳細展開了，起一個輔助理解的作用。

四、XRRAY的選擇

內核中使用的樹的類型比較多，如上面敘述的radix樹，VMA使用的rbtree，以及今年提出的maple tree。XRRAY的出現是由Matthew Wilcox領導，他認爲內核的基數樹是一個很好的數據結構，但是它的用戶數量遠遠少於人們的預期。相反，各種內核子系統已經實現了自己的數據結構來解決相同的問題。他試圖通過轉換其中一些子系統來解決此問題，於是便有了內核4.20之後版本中出現的XRRAY，在一次演講中他對比了其他的一些內核中使用的樹，比如說rbtree，也許會疑惑爲什麼單獨選擇在radix樹的基礎上改造，而不是其他的樹結構。演講中提到了一部分。

rbtree有着幾個相對應的缺點。首先他並不是RCU安全的。現在的VMA搜索問題，在虛擬內存區，任務的地址空間是一組不重疊的虛擬內存區域，當前存儲在增強的rbtree中，但是必須要mmap_sem鎖定才能walk tree。其次使用紅黑樹會涉及大量的代碼編寫問題，因爲必須編寫屬於自己的搜索接口等。談論到內核中使用的另外一種樹Btree，它對密集索引的效率不如radix樹高，實際上他的效率也大約只有基數樹的一半，因此Matthew Wilcox選擇了radix樹做基礎。

正如上面講述的radix樹的框架，他的搜索效率還有RCU安全的特性對於搜索頁面緩存來說也是至關重要的，不過radix樹有幾個需要解決的關鍵點。保持現有的基數樹數據結構不變，因爲它幾乎沒有問題。但是，描述其操作的結構已從樹更改爲數組，所以我們需要做接口適配。它的行爲很像一個自動調整大小的數組。基數樹要求用戶自己進行鎖定；XArray默認情況下會處理自身的鎖定，從而簡化了使用它的任務。刪除“預加載”機制，該機制使得用戶在獲取鎖之前預分配內存；它增加了複雜性，幾乎沒有任何實際價值。

XARRAY有以下幾個特點：保持基數樹的數據結構不變，將結構更改爲數組，默認情況下提供鎖定，刪除內存預加載，使內存分配標誌明確，向用戶隱藏實施細節並且提供兩個級別的API-普通和高級，方便人們使用。目前page cache已經轉換完成，IDR也轉換了大部分。簡單的API是在高級API的基礎上實現的，只管拿來使用，不必擔心鎖的問題。下面是一部分接口與radix樹的對比。

在include/linux/radix-tree.h中您可以看到它已被Xarray取代。

在include/linux/xarray.h您可以檢查相應的結構聲明。

這裏可以看出和radix樹結構的相似點和區別。例如radix樹使用的node節點、tags，而xarray使用的是entry、marks，只不過換了一個名字而已，結構屬性都差不多。

下面介紹一下一些基本的函數：

1. 初始化一個XArray數組，xa_init(&array);

2. 在XArray裏存放一個值：

void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp);

這個函數會把參數給出的entry，放到請求的index這個地方。如果xarray需要分配內存，會使用給定的gfp來分配。如果成功，返回值是之前存放在index的值。刪除一個entry可以通過在這裏存放NULL來實現，或者調用void *xa_erase(struct xarray *xa, unsigned long index);

xa_store的變體：xa_insert用於存放但不覆蓋現有的entry。另一個變體：xa_cmpxchng，只有當存的值和old參數匹配上時，纔會將entry存在index處。

void *xa_cmpxchg(struct xarray *xa, unsigned long index, void *old,void *entry, gfp_t gfp);

xa_insert和xa_cmpxchng都會返回存入的值。

3、用xa_load()從XArray裏取出一個值

void *xa_load(struct xarray *xa, unsigned long index);

下面以一個查找函數爲例：

①主要進行一個結構格式的轉換，由xarray 轉換成xa_state ，存儲更多的數據，內部含有index數據。

②根據轉換成的xa_state結構中的信息進行搜索，這裏會爲防止失敗有一個retry的動作。

①獲得開始節點；

②判斷是否是一個節點，如果是便先轉換一下數據格式xa_node這種數據格式由之前的宏定義可以看出與radix樹的聯繫，之後由xas_descend進行移位操作，這個函數與之前的radix_tree_descend非常相似。

xas_descend函數同樣是對index進行了移位的操作。

溫故而知新，大致就是這個意思吧。由此可見接口確實比radix簡潔很多。每個不爲NULL的指針都可以標記多達3位的額外信息，可以通過xas_get_mark（），xa_set_mark（）和xa_clear_mark（）進行訪問。您還可以通過調用xas_find（），xas_next（）或xas_for_each（）來遍歷數組中的指針。