隨風(fēng)潛入夜，潤物細(xì)無聲，TencentOS內(nèi)核團(tuán)隊今年4月在Linux社區(qū)提交的2個commit，在社區(qū)正式重視 Page Cache 問題前的幾個月前，默默完成了 Bug 的修復(fù)并優(yōu)化了性能。TencentOS內(nèi)核團(tuán)隊的 Patch 被公認(rèn)為最佳修復(fù)， Linus Torvalds 更評價其"不明覺贊，祝順利" 。本文將由淺入深解析底層原理，厘清問題的來龍去脈。

一、“悄然消失的內(nèi)核問題”

大概兩個月前，一封名為《Known and unfixed active data loss bug in MM + XFS with large folios since Dec 2021 (any kernel from 6.1 upwards)》在社區(qū)引起了一定的關(guān)注，其內(nèi)容也在筆者的朋友圈以有點(diǎn)過度反應(yīng)刷了一小波屏：自 2021 年起(6.1 內(nèi)核發(fā)布起)，Linux 內(nèi)核中啟用了 Large folio 特性的 XFS 文件系統(tǒng)(但不僅限于 XFS)有概率遭遇數(shù)據(jù)損毀問題。這乍看上去是一個頗為嚴(yán)重的 Bug，也確實引得了多個頂級 Maintainer 的關(guān)注和排查。實際上該 Bug 較難觸發(fā)，但也確實讓社區(qū)和各大一線廠家很是頭痛，Meta，Cloudflare 都表示自己遇到過該問題，并已經(jīng) Revert XFS 的 Large Folio 特性，這才能保證內(nèi)部系統(tǒng)的穩(wěn)定性。

一個多星期的討論中，社區(qū)并沒有得出明確結(jié)論或有效的重現(xiàn)方法，幾位頂級 Maintainer，包括 Matthew Wilcox(Folio，Xarray 等一系列核心組件作者)，Jens Axboe(IO_uring，CFQ 調(diào)度器等作者)，以及 Linus Torvalds 本人也參與進(jìn)入討論，目光都聚焦在了 Xarray 部分。不過大家都遲遲沒有捕捉到 Bug 所引發(fā)的具體位置或線索，只是確認(rèn) Bug 確實存在而且亟需修復(fù)。

在社區(qū)排查過程中，Jens Axboe 卻發(fā)現(xiàn)這個問題已經(jīng)在最新的 Linux 內(nèi)核上悄悄消失了。而相關(guān)的改動基本只有兩個 commit，這兩個 commit 是TencentOS內(nèi)核團(tuán)隊在今年 4 月份提交的。這也讓后續(xù)討論基本就開始圍繞這兩個 commit 展開，遇到過該問題的廠商與社區(qū)活躍開發(fā)者也開始以這兩個 commit 為基礎(chǔ)進(jìn)行討論，驗證與復(fù)現(xiàn)。不過社區(qū)的大佬們也還是花了不少時間，才最終搞清楚問題的來龍去脈，以及這兩個 commit 到底修了什么。

有趣的是這兩個 commit 的作者對問題和討論并未注意到。在約一星期后，在 LPC 參會時現(xiàn)場遇到了參與和關(guān)注該問題的一些 Maintainer 與開發(fā)人員。閑談之余才回過神來，TencentOS內(nèi)核團(tuán)隊確實發(fā)現(xiàn)過并已修復(fù)了這個問題。

我們在優(yōu)化 Page Cache 時想到過的一個潛在 Race Condition，但由于比較繁忙，并沒有特別去做 reproduce 來驗證，而是直接在一個優(yōu)化中修復(fù)了，并添加了相關(guān) comment。在討論中社區(qū)也注意到了當(dāng)時留下的 comment，并猜測這是問題的根源：

(在非持鎖階段 XArray 的內(nèi)容可能會發(fā)生變化，因此如果發(fā)現(xiàn)變化，需要撤銷上次的分配，稍后詳解)：

經(jīng)過再三的討論與驗證，TencentOS內(nèi)核團(tuán)隊的 Patch 被公認(rèn)為最佳修復(fù)，全程參與了討論的 Linus Torvalds 也給出了"不明覺贊，祝順利"的評價：

幾個 commit 也被建議合入 Linux LTS。筆者提交了經(jīng)過簡易修改的三個 Commit 供 LTS 版本使用，現(xiàn)修復(fù)并已經(jīng)一并合入 6.1 LTS，6.6 LTS，以及 TencentOS Kernel。TencentOS Kernel 4 不受影響，TencentOS Kernel 5 則已合入了該補(bǔ)丁，為業(yè)務(wù)提供穩(wěn)定的基石。

隨風(fēng)潛入夜，潤物細(xì)無聲。這并不是我們第一次解決內(nèi)核中的隱藏問題或疑難問題。隨著 Tencent OS “悟凈” 內(nèi)存節(jié)省技術(shù)對 Linux 內(nèi)核內(nèi)存管理領(lǐng)域的深究與不斷保持與社區(qū)的緊密合作，在 Swap，Memory Cgroup，頁面與熱度管理等領(lǐng)域，我們一直有著長期的上游貢獻(xiàn)，也有更多的未來規(guī)劃。這不僅讓我們對 Linux 內(nèi)核內(nèi)存管理的應(yīng)用與落地不斷深入，同時也回饋了社區(qū)。

借此機(jī)會，讓我們深入了解下 Page Cache，Xarray，和這個問題的底層細(xì)節(jié)。

二、從Xarry的基礎(chǔ)講起

這次出現(xiàn)的問題其實是一個并不罕見的內(nèi)存安全問題。出現(xiàn)問題的組件是 Linux 內(nèi)核的 Page Cache 機(jī)制，也是內(nèi)核最核心的功能之一。

Linux 內(nèi)核的 Page Cache 是由 Radix Tree 管理的，Radix Tree 在內(nèi)核中通過 Xarray 機(jī)制進(jìn)行了很好的包裝，Xarray 提供了簡單易用的仿數(shù)組 API，讓大部分內(nèi)核組件可以像使用數(shù)組一樣使用 Radix Tree。用戶可以簡單通俗地可以將 Xarray 抽象理解為一個很靈活而巨大 long / void * 數(shù)組，其 Index 范圍為 unsigned long。

Xarray 也提供了更復(fù)雜的高級 API，從而實現(xiàn)了諸如 Multi Index 復(fù)用樹節(jié)點(diǎn)，避免重復(fù)走樹等高性能特性，來更好利用 Radix Tree 的一些天生特性。Linux 內(nèi)核的 Page Cache 機(jī)制便是對 Xarray 的高級 API 利用最充分的地方之一。特別是在 Large Folio 引入后，Xarray 可以在一些場景中大幅度降低樹的高度，降低內(nèi)存使用，提升性能，不過這也是這次出現(xiàn)問題的地方。要了解這次問題的來龍去脈，讓我們從 Xarray 的基礎(chǔ)講起。

1.Xarray介紹

Xarray 基礎(chǔ)概念并不復(fù)雜，正如上文提到，可以將其抽象理解為一個靈活的數(shù)組。這里我們將數(shù)組中存儲的元素稱之為 Entry，數(shù)組元素由 Index 索引。故 Xarray 便是維護(hù)了 Index 為 Key，Entry 為 Value 的 Radix Tree 關(guān)系，且有一些基本 API 與約定：

它的 Index 可以是 unsigned long 表達(dá)的任意整數(shù)，我們這里約定為 64 位環(huán)境，即 Index 必須為 64 位整數(shù)。而數(shù)組元素 Entry 的存儲類型為 void *，即 Entry 也必須是 64 位，Entry 默認(rèn)值為 NULL(0)。

Xarray 的基本 API 所暴露的基本只有 Index 和 Entry 的概念。為了更深入了解，這里 Xarray 中可以存儲一個 Entry 的基本單位可稱之為 Slot ，一個 Slot 中存儲的 Entry 可以是一定范圍內(nèi)的整數(shù)值 Value( 0 - LONG_MAX)，或 Byte 對齊的指針 Pointer(Byte 對齊的 Pointer 末尾 3 位必為 0)，或空缺值默認(rèn)為 NULL(0)，或 Xarray 內(nèi)部值。注意到存儲的 Entry 數(shù)據(jù)有一定限制，是因為 Xarray 會利用存儲值的最后幾位 Bit 記錄額外的信息，用于辨別 Entry 的類型。這也讓 Xarray 有能力告知調(diào)用者一個 Index 所對應(yīng)的 Slot 中的 Entry 是什么類型的(Value，Pointer 或 NULL)。同時 Xarray 還可以利用數(shù)據(jù)最后的 Bit 實現(xiàn) Tag 等特性，也有一些特殊保留值，我們暫時跳過。

Xarray 最基本的 API 如下：

• void xa_init(struct xarray *xa)
• void xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
• void *xa_load(struct xarray *xa, unsigned long index)

很容易理解，使用這幾個函數(shù)即可在一個 Xarray 中完成以 64 位整數(shù)為 Index 的 long / void * 數(shù)據(jù)(Entry)存儲和讀取，若要刪除一個 Index 中的數(shù)據(jù)，存入 NULL 即可。注意存儲整數(shù)值 Value 的時候需要用 xa_mk_value(value) 進(jìn)行包裝和 Cast 到 void *。

2.Xarray 的內(nèi)部實現(xiàn)

Xarray 的頂層包裝為一個 struct xarray。其內(nèi)部最基本的結(jié)構(gòu)為 struct xa_node。一個 xa_node 有 XA_CHUNK_SIZE(默認(rèn) 64，2 ^ 6)個 Slot，即一個 64 元素的 void * 數(shù)組，每個 Slot 可以存入一個實際的 Entry 或指向下一級 xa_node(或特殊值，暫時忽略)。

在存儲一個 Index -> Entry 時，可以想像，將 64 位的 Key 分割為 6 bit 一級的 offset，每一級 offset 便可以使用一個 xa_node 進(jìn)行記錄。每 6 bit offset 對應(yīng)的 slot 指向下一級 xa_node，便可以使用該結(jié)構(gòu)以樹狀組織多個 Index 到 Value 的關(guān)系，提供快速查找。

我們不妨利用一個實際的例子來理解：比如，我們要存儲一個 Pointer(0xffff1234deadbeef)，使用的 Index 為 8772，則其對應(yīng)的 Xarray 拓?fù)浣Y(jié)構(gòu)展開如下：

首先將 8772 對應(yīng)的二進(jìn)制表達(dá)分割為 6 bit 一級，高位全部為 0 ，最后有效的三組為 000010 001001 000100。

對于重復(fù)的 0，不需要分配 xa_node，這只需要在頂層的 xa_node 中記錄 shift 即可表達(dá)(這也就可以理解，為什么 Xarray 對于 Index 比較小的值性能會更好)，該例子中 shift = 12，即表示該 xa_node 對應(yīng)的 64 bit 中從第 13 bit 到 18 bit 這一段的 offset(000010)。也可以理解為該 xa_node 覆蓋了 0 - 262143(2 ^ (12 + 6) - 1) 這一范圍;而其中每一個 Slot 又分別對應(yīng)了對應(yīng)的子范圍：offset 為 2 的 Slot 對應(yīng)范圍為 8192 (0 + 4096 * 2) 至 12287 ( 0 + 4096 * 3 - 1) 這一范圍;8192 至 12287 這一 Node 中又有第 9 個 Slot 對應(yīng)了 8768(8192 + 64 * 9)至 8831(8192 + 64 * 10 - 1)這一范圍，當(dāng)一個范圍有數(shù)據(jù)時才有必要分配下一級 xa_node 或存入 Entry。

每個 node 都會記錄 shift 和其在 parent 中的 offset 等等信息，以實現(xiàn)各種復(fù)雜操作，這里不做贅述。

上面例子可見，存儲 Index 8772 到 Pointer 0xffff1234deadbeef 這一數(shù)據(jù)一共需要三個 xa_node 結(jié)構(gòu)進(jìn)行表示。

3.Xarray 讀取

Xarray 的讀取是一個查找的過程，從頂向下逐級走樹。Xarray 會循環(huán)使用 6 bit 作為 offset 查詢當(dāng)前級別對應(yīng)的 Slot 便可一路走到對應(yīng)的 Slot。

Xarray 使用 xa_state 這一結(jié)構(gòu)維持走樹查詢的中間狀態(tài)。xa_load 函數(shù)包裝了整個讀取走樹過程。在調(diào)用 xa_load 時會在棧上生成一個 xa_state，并重復(fù)調(diào)用 xas_start，xas_decend 等內(nèi)部函數(shù)來一層層向下查找，如上圖所示。在每一層 Node 上使用對應(yīng)的 offset 向下讀取 slot 中記錄的下一級 xa_node，直到讀到 slot 為一個值而非 node 或走到最底層時即完成了查找過程。

同時為了照顧一些特殊調(diào)用者，避免重復(fù)的走樹操作，Xarray 允許將 xa_state 暴露出來，讓用戶手動使用如 xas_load 這樣的 API 手動維護(hù) xa_state：

XA_STATE(xas, xa, index);
void *entry;

rcu_read_lock();
do {
	entry = xas_load(&xas);
} while (xas_retry(&xas, entry));
rcu_read_unlock(); 

在 xas_load 后，xas 會保持指向 xa_node，可以通過 xas_reload 等操作，在一些特殊場景避免重復(fù)的從向上下走樹這一過程。另外 Xarray 中的數(shù)據(jù)是被 RCU 保護(hù)的，因此讀取時只需要獲取 RCU 鎖即可(這里 xas_retry 就是為了防止撞上正在被釋放的 node)。

4.Xarray 存入

Xarray 的存入是個類似的過程，不過比較特殊的是查找需要處理 xa_node 的分配，其他過程雷同：

由于存入會修改 Xarray，因此必須使用鎖進(jìn)行保護(hù)(xa_lock & xa_unlock)。這一點(diǎn)和 xa_node 的分配有一定的沖突，因為在鎖臨界區(qū)中進(jìn)行內(nèi)存分配可能會失敗。不過 Xarray 在存入時依舊維護(hù)了 xa_state 這一結(jié)構(gòu)來記錄當(dāng)前存入的層級，這就讓 Xarray 可以解鎖后重新嘗試分配內(nèi)存，再上鎖后繼續(xù)使用當(dāng)前的 xa_state 進(jìn)行存入，從而提高存入成功率。

xa_state 這個暫存結(jié)構(gòu)留有相關(guān)字段用于傳遞錯誤信息和分配信息：這里用 xa_store 所對應(yīng)的高級 API xas_store 可以很好的說明它在存入時處理內(nèi)存分配的用途和用法：xas_store 會在內(nèi)部使用 xas_alloc 嘗試進(jìn)行內(nèi)存分配，分配失敗時會通過 xa_state 向調(diào)用者返回 ENOMEM。此時用戶需要手動管理 xa_state，并使用 Xarray 提供的 xas_nomem 這個函數(shù)，即可方便實現(xiàn)在釋放鎖后再次重試分配內(nèi)存，并再次調(diào)用 xas_store 這樣的操作：

XA_STATE(xas, xa, index);void *old;do {
	xas_lock_irq(&xas);
	old = xas_store(&xas, xa_mk_value(value));
	xas_unlock_irq(&xas);} while (xas_nomem(&xas, GFP_KERNEL));

如上代碼便會在 xas_store 因內(nèi)存分配失敗而通過 xa_state 返回 ENOMEM 時，釋放鎖并重試內(nèi)存分配，直到成功存入 Index -> Value(實際上 xa_store 內(nèi)部也基本上使用了一樣的處理邏輯，以保證存入的成功)。

這里需要注意的一點(diǎn)是，xa_state 用于記錄暫時分配的 xa_node 的是 .xa_alloc 這一字段，xas_store 則會優(yōu)先使用 xa_state 中暫存的分配。如果由于發(fā)生了其他錯誤而不得不放棄存入，xas_nomem(隱式調(diào)用 xas_destroy)來釋放 xa_state.xa_alloc 防止內(nèi)存泄露。

5.Xarray Multi Index

由于每個 xa_node 有 XA_CHUNK_SIZE (64)個 slot，也就是最多存儲 64 個值，所以如果有 64 個連續(xù)的 Key，則 Xarray 可以不分配整個 xa_node，直接在 parent 的 slot 中標(biāo)記整個 range 為一個值，如下：

在存儲一系列連續(xù)的 Index -> Entry 時，其中連續(xù)的大于 2 ^ 6 且對齊的部分可以直接跳過下一級 xa_node 的分配，直接在對應(yīng)的 slot 中存入 entry 來表達(dá)這一系列的 slot 均為同一 entry。這樣可以顯著降低連續(xù) Key 所占用的內(nèi)存與搜索時間。這一特性稱作 Multi Index Entry。值得一提的是在 Linux 內(nèi)核實際使用中 Xarray 的Multi Index Entry 特性需要用戶使用高級 API 來顯式地存儲一個 Order > 1 的 Entry 才能使能，并且 Index 必須對齊 2 的整數(shù)方倍。

Multi Index 的場景會有一個特殊問題：例如，若如果這個 Multi Index Entry 覆蓋的范圍的的值只有一個值需要修改的話，那整個Multi Index Entry 需要先分解為普通的由 xa_node 組成的扁平 slot 保存的普通 entry 才行，Xarray 也提供了相關(guān)函數(shù)和操作范式：

其中又涉及了 xa_node 的分配問題。調(diào)用者需要首先獲取 entry 的 order，隨后在鎖外使用 xas_split_alloc() 為其分配所需的 xa_node，再通過上鎖后調(diào)用 xas_split 完成對這個 Multi Index Entry 對應(yīng)的 slot 的 update，才可以再進(jìn)一步修改子范圍內(nèi)的 Entry。

另外，對于小于 2 ^ 6 的范圍的 Multi Index，其無法跳過整個 xa_node 的分配，Xarray 會使用 Sibling Slot 來讓多個 Index 指向同一個 Entry：

Xarray 會將多個 Slot 記錄為 Sibling Slot 并指向最低位的 Slot，其中再保存 Entry。不過這種用法我們在此文章中將暫時忽略。

Xarray 自然可以存儲混合的 Multi Index 和單一 Index。

在 Page Cache 中，很容易想到，基于 Xarray 的 Page Cache 可以利用 Multi Index 特性來避免為 order 6(256K)以上的大頁面分配多余的 xa_node，從而降低樹深度，降低內(nèi)存消耗，提高性能。但需要注意的是，Page Cache 中的頁面和信息都是是可以被拆碎的，所以 Page Cache 也會需要處理 Multi Index entry 被 Split，并為其分配內(nèi)存這一過程。

Multi Index Entry 的分解和內(nèi)存分配便是這次的問題出現(xiàn)的地方。

6.Page Cache 對 Xarray 的使用

Page Cache 可以視為是一個以文件內(nèi)部的 Offset 為 Index 的 Xarray，它會存儲兩種 Entry：頁面(Folio / Page)或 Shadow(注：由于歷史原因 Page / Folio 兩個名字的使用在代碼和注釋中會略有混淆，其本質(zhì)沒有區(qū)別，并不影響理解)。

Page Cache 中的頁面 Entry 即為保存文件數(shù)據(jù)的文件頁，而 Shadow 是頁面從 Page Cache 中被淘汰后所留下的一個標(biāo)記：Shadow 用于在發(fā)生頁面再入讀入時計算頁面熱度和 Workingset 相關(guān)信息，輔助 LRU 進(jìn)行 Page Cache 熱度管理，從而在內(nèi)存有限時優(yōu)先存儲更常用的數(shù)據(jù)，提高 Page Cache 的緩存命中率。其具體原理我們在此文章中不做贅述，可以參考內(nèi)核代碼 mm/workingset.c 文件中的長篇注釋。

內(nèi)存頁面(Folio)或 ·具體落實到 Xarray 中，Shadow 使用 Value 表示，頁面使用 Pointer 表示。因此通過讓 Xarray 檢測一個 Slot 中存儲的是 NULL， Value，還是 Pointer，即可知道 Page Cache 中這一 Offset 對應(yīng)的文件緩存目前是“未緩存”，“已被淘汰”，還是“被緩存”的狀態(tài)。

有了以上這些背景知識，我們不妨直接從 v6.9 及以前版本的 Linux 內(nèi)核 Page Cache 插入代碼看起。Page Cache 在插入頁面時，大量使用了 Xarray 的高級 API。我們這里提供一份刪去統(tǒng)計計數(shù)與 Trace 相關(guān)邏輯的精簡(偽)代碼，其非常完好地概括了 Page Cache 的插入流程：

int __filemap_add_folio(struct address_space *mapping,
		struct folio *folio, pgoff_t index, gfp_t gfp, void **shadowp)
{
	/*
	 * 設(shè)置 xa_state 中的 index，并讓其指向文件對應(yīng)的 Xarray。
	 * 每個文件的 inode 都有自己的 Xarray（&mapping->i_pages）來記錄
	 * 文件中 offset 到 Page Cache 數(shù)據(jù)頁或 Shadow 的關(guān)系。
	 */
	XA_STATE(xas, &mapping->i_pages, index);
	/*
	 * 如果是大頁（high order folio），有 folio_order > 1，這里告知
	 * Xarray 使用 Multi-Index 模式進(jìn)行存儲。
	 */
	xas_set_order(&xas, index, folio_order(folio));
	do {
		/*
		 * （1）這里 xa_get_order 會進(jìn)行一次完整無鎖走樹，獲取 index 對應(yīng)
		 * 的 entry 的 order。這里是為了下方可能需要的 split 做準(zhǔn)備。< ①  >
		 */
		unsigned int order = xa_get_order(xas.xa, xas.xa_index);
		void *entry, *old = NULL;

		/*
		 * （2）如果當(dāng)前 index 對應(yīng)的 entry 為 multi-index 且 order 大于
		 * 新需要插入的 folio，則需要進(jìn)行 split，故需要先在鎖外使用
		 * xas_split_alloc 分配所需內(nèi)存（分配 xa_node 放入 xas.xa_alloc）。
		 *
		 * 新分配 xa_node 中 slot 的默認(rèn)值為當(dāng)前 index
		 * 對應(yīng) entry 的值，由這里的 xa_load 獲取 < ②  >。
		 *
		 * 這里對應(yīng)的場景是：一個高 order folio 被淘汰時會留有一個
		 * 高 order shadow，此時如果被淘汰的 folio 只有部分子
		 * folio 被讀入，則需要將高 order shadow entry 進(jìn)行 split，
		 * 并在 Xarray 子范圍內(nèi)，存入讀入的 folio，這樣后續(xù)的其他子
		 * folio 被讀入時仍舊能找到對應(yīng)的 shadow 信息。
		 */
		if (order > folio_order(folio))
			xas_split_alloc(&xas, xa_load(xas.xa, xas.xa_index),
					order, gfp);
		/*
		 * （3）獲得 Xarray 鎖，防止并發(fā)修改，開始進(jìn)行插入。
		 * 下方的所有操作都將是可靠無競爭的。
		 */
		xas_lock_irq(&xas);
		/*
		 * （4）再次走樹遍歷并檢測要存入的 index -> folio 覆蓋區(qū)域內(nèi)有無現(xiàn)存
		 * 的任何 folio。< ③  >
		 * 若有 Pointer（xa_is_value == false），則說明已經(jīng)有部分
		 * 數(shù)據(jù)被放入 Page Cache，返回 -EEXIST 讓調(diào)用者處理這一情況。
		 * 如存在 Value（xa_is_value == true），則說明這里有 Shadow。
		 * 暫存到 old 變量中稍后并返回給調(diào)用者讓其處理熱度信息。
		 */
		xas_for_each_conflict(&xas, entry) {
			old = entry;
			if (!xa_is_value(entry)) {
				/*
				 * Xarray 內(nèi)部錯誤會存儲在 xa_state 上，
				 * 外部錯誤也可以通過 xas_set_err 存入，
				 * 并最后由 xas_error 獲取和返回。
				 */
				xas_set_err(&xas, -EEXIST);
				goto unlock;
			}
		}

		/*
		 * 如果代碼執(zhí)行到此處，old 必然為一個 shadow。
		 */
		if (old) {
			/*
			 * 將 shadow 信息返回給調(diào)用者。
			 */
			if (shadowp)
				*shadowp = old;
			/*
			 * （5）這里再次檢測現(xiàn)存 entry 的 order，因為 entry 可能在上面
			 * xa_get_order 走樹之后，獲取鎖之前，已經(jīng)被 split 或修改了。
			 * 這里需要再次使用 xa_get_order 走樹查詢當(dāng)前 shadow 的 order。
			 * < ④  >
			 */
			/* entry may have been split before we acquired lock */
			order = xa_get_order(xas.xa, xas.xa_index);
			/*
			 * （6）如果 order 仍舊大于 folio，說明該 shadow entry 未被
			 * split，對其進(jìn)行 split 。否則跳過 split。目前 split 必會分解為 order 0.
			 */
			if (order > folio_order(folio)) {
				/*
				 * 使用之前 xas_split_alloc 所分配的
				 * xa_node 填充和分解 Multi Index Entry。
				 */
				xas_split(&xas, old, order);
				xas_reset(&xas);
			}
		}

		/*
		 * （7）需要 split 的場景已經(jīng)在上面處理，
		 * 這里則是一個普通的 Xarray 插入操作。< ⑤  >
		 */
		xas_store(&xas, folio);
		if (xas_error(&xas))
			goto unlock;
unlock:
		/*
		 * （8）釋放鎖。
		 */
		xas_unlock_irq(&xas);
		/*
		 * （9）如果上面的插入因為分配內(nèi)存失敗而在 xa_state
		 * 中標(biāo)記了 ENOMEM，xas_nomem 會捕捉到這一問題
		 * 并重試申請，如果申請成功，會從循環(huán)開頭重試。
		 * 如果發(fā)生了其他問題，xas_nomem 會釋放可能存在
		 * 的 .xa_alloc 數(shù)據(jù)。
		 */
	} while (xas_nomem(&xas, gfp));

	if (xas_error(&xas))
		goto error;
	return 0;
error:
	return xas_error(&xas);
}

述代碼可以大致總結(jié)為如下步驟：

(1) 獲取當(dāng)前 Page Cache 中 Index 所對應(yīng)的 Entry Order( ① )。

(2) 如果 Entry Order 大于要新插入的 Folio Order，在鎖外分配 split 所需的 xa_node，用當(dāng)前 entry 填充并暫存入 xas.xa_alloc( ② )。

(3) 鎖住 Xarray。

(4) (上鎖后)檢查要新插入的 Index -> Folio 所覆蓋的范圍內(nèi)有無現(xiàn)存 Folio，若有跳至步驟 8 ( ③ )。

(5) (上鎖后)再次檢查當(dāng)前 Index 對應(yīng)的 Entry Order，防止上鎖前發(fā)生變更( ④ )。

(6) (上鎖后)如果 Entry Order 仍舊大于 Folio Order，Split，使用步驟 2 分配的 xa_node。

(7) (上鎖后)已經(jīng)處理可能需要 Split 的場景，直接存儲 Index -> Folio( ⑤ )。

(8) 解鎖 Xarray。

(9) 如果步驟 7 在鎖內(nèi)分配 xa_node 失敗了，重試分配，存入 xas.xa_alloc 并從頭再開始。如果步驟 4 或 7 因為其他原因失敗了，釋放可能存在的 xas.xa_alloc 并返回錯誤。

以上便是 6.9 以前內(nèi)核的 Page Cache 插入邏輯，雖然是 Linux 內(nèi)核熱度很高的一個核心路徑，但其中潛藏了一個 Bug 和性能問題。

三、問題發(fā)生

不知讀者是否注意到，在上文代碼中介紹的 6.9 和以前版本的 Linux Kenel Page Cache 插入流程中，每次插入至少有三次 Tree Walk。即使是不需要 Split 的場景，① ③ ④ 都是獨(dú)立發(fā)生的 Tree Walk，因為其不共享 xa_state。如果發(fā)生了 split，② 也會進(jìn)行走樹，同時 xas_reset 重置 xa_state 導(dǎo)致 ⑤ 也會是獨(dú)立的走樹：一共有 5 次獨(dú)立的 Tree Walk。這其實是都不必要的，也是我們最開始注意到的問題。

在審閱 Linux 內(nèi)核核心路徑代碼時，我們注意到了這一冗余的 Tree Walk，并認(rèn)為這一點(diǎn)作為內(nèi)核最核心的路徑之一，是非常值得優(yōu)化的，因此經(jīng)過幾個迭代和測試，對插入邏輯進(jìn)行了如下重構(gòu)(已經(jīng)合入 v6.10)：

int __filemap_add_folio(struct address_space *mapping,
		struct folio *folio, pgoff_t index, gfp_t gfp, void **shadowp)
{
	/*
	 * 設(shè)置 xa_state 中的 index，并讓其指向 Xarray 的頂部節(jié)點(diǎn)。
	 * 每個文件的 inode 都有自己的 Xarray（&mapping->i_pages）來記錄
	 * 文件 offset 到 Page Cache 數(shù)據(jù)頁或 Shadow 的關(guān)系。
	 */
	XA_STATE(xas, &mapping->i_pages, index);
	/*
	 * 一些稍后會用到的中間變量，表示由 xas_split_alloc 所分配
	 * 的 xa_node 所對應(yīng)的 order 和內(nèi)部填充的 entry（必為 Shadow）。
	 */
	void *alloced_shadow = NULL;
	int alloced_order = 0;
	/*
	 * 如果是大頁（high order folio），有 folio_order > 1，這里告知
	 * Xarray 使用 Multi-Index 模式進(jìn)行存儲。
	 */
	xas_set_order(&xas, index, folio_order(folio));
	/*
	 * 循環(huán)開始，直到插入成功或發(fā)生內(nèi)存分配失敗以外的錯誤。
	 */
	for (;;) {
		int order = -1, split_order = 0;
		void *entry, *old = NULL;
		/*
		 * （1）這里直接鎖住 Xarray。隨后走樹遍歷（2），檢測要存入的
		 * index -> folio 覆蓋區(qū)域內(nèi)有無現(xiàn)存的任何 folio。< ①  >
		 */
		xas_lock_irq(&xas);
		xas_for_each_conflict(&xas, entry) {
			/*
			 * 若有 Pointer（xa_is_value == false），則說明已經(jīng)有部分
			 * 數(shù)據(jù)被放入 Page Cache，返回 -EEXIST 讓調(diào)用者處理這一情況。
			 */
			old = entry;
			if (!xa_is_value(entry)) {
				xas_set_err(&xas, -EEXIST);
				goto unlock;
			}
			/*
			 * 如存在 Value（xa_is_value == true），則說明這里有
			 * Shadow。暫存到 old 變量中稍后并返回給調(diào)用者讓其處理
			 * 熱度信息。
			 *
			 * 注意此時 xas_for_each_conflict 所暴露和維護(hù)的 xa_state
			 * 必然是指向 shadow 所在的 xa_node 的，所以我們可以直接
			 * 通過 xa_state 拿到 shadow entry 的 order。
			 *
			 * 這里引入了一個新的 helper：xas_get_order 直接利用
			 * xa_state 獲取該 entry 的 order，避免還需重新走樹。
			 */
			if (order == -1)
				order = xas_get_order(&xas);
		}

		/*
		 * （3）這里是針對第二次和之后的循環(huán)的一個步驟。
		 * 第一次循環(huán)這里 alloced_order 必為 0，什么都不會發(fā)生。
		 *
		 * 對于需要 split 的情況，必然需要 xas_split_alloc 進(jìn)行
		 * 內(nèi)存分配，這個分配會發(fā)生在更下方，并會記錄當(dāng)時分配
		 * 所對應(yīng)的 order 到 alloced_order 中表示已經(jīng)分配。
		 *
		 * 由于 xas_split_alloc 分配發(fā)生在鎖外，其分配的 xa_node
		 * 對應(yīng)的 shadow order 或 shadow value 可能都已經(jīng)發(fā)生變化，
		 * 這里檢測是否發(fā)生了變化，如果發(fā)生了，則清理分配數(shù)據(jù)。
		 * 并標(biāo)記 alloced_order 為 0 表示沒有可用 split 使用的內(nèi)存。
		 */
		if (alloced_order && (old != alloced_shadow || order != alloced_order)) {
			/* xas_destroy 會清理和釋放無效的 xa_node */
			xas_destroy(&xas);
			alloced_order = 0;
		}
		/*
		 * （4）如果代碼執(zhí)行到此處，old 若有值則必然為一個 shadow，
		 * 也是可能需要 split 的情況。
		 */
		if (old) {
			/*
			 * 這里的 order 是在獲取 Xarray 鎖后獲得的所以是可靠的，
			 * 不需要重新檢查 entry。所以只要 order 大于新插入 folio
			 * 的 order 就肯定是需要 split。
			 *
			 * order > 0 檢查是一個優(yōu)化，可以減少對頁面信息的讀取。
			 */
			if (order > 0 && order > folio_order(folio)) {
				/*
				 * 對于需要 split 的情況，第一次循環(huán)這里 alloced_order
				 * 必為 0，也就是沒有可供 split 使用的內(nèi)存。跳到解鎖處
				 * 進(jìn)行分配。
				 * 第二次以及往后的循環(huán)這里 alloced_order 若有值，
				 * 則必然等于 entry 的 order （不等于的場景已經(jīng)被
				 * 步驟 3 處理)，可以安全進(jìn)行 split。
				 * 若 alloced_order 為 0，說明 xas_split_alloc 從未執(zhí)行
				 * 或者其分配的內(nèi)存已經(jīng)因為過期被步驟 3 釋放，申請
				 * 分配對應(yīng) order 的內(nèi)存，跳至步驟（6）。
				 */
				if (!alloced_order) {
					split_order = order;
					goto unlock;
				}
				/*
				 * 使用下方 xas_split_alloc 所分配的 xa_node 填充
				 * 和分解 Multi Index Entry。
				 */
				xas_split(&xas, old, order);
				xas_reset(&xas);
			}
			/*
			 * 將 shadow 信息返回給調(diào)用者。
			 */
			if (shadowp)
				*shadowp = old;
		}

		/*
		 * （5）需要 split 的場景已經(jīng)在上面處理，
		 * 這里則是一個普通的 Xarray 插入操作。< ⑤  >
		 */
		xas_store(&xas, folio);
		if (xas_error(&xas))
			goto unlock;
unlock:
		/* （6）釋放鎖 */
		xas_unlock_irq(&xas);

		/*
		 * （7）在步驟 4 split 需要 xas_split_alloc 進(jìn)行分配的
		 * 時候會在這里看到 split_order != 0。
		 * （第一次循環(huán)，或上次分配的內(nèi)存被步驟 3 釋放了）
		 *
		 * 嘗試使用持鎖時獲取的 entry order (split_order)
		 * 分配所需的內(nèi)存，并使用持鎖時所記錄的 entry 值填
		 * 充新分配的 xa_node。
		 */
		if (split_order) {
			xas_split_alloc(&xas, old, split_order, gfp);
			/*
			 * 在鎖外內(nèi)存分配也失敗了，無法處理，返回錯誤。
			 */
			if (xas_error(&xas))
				goto error;
			/*
			 * 記錄此時已分配的 xa_node 對應(yīng)的 order 和 entry。
			 */
			alloced_shadow = old;
			alloced_order = split_order;
			/*
			 * 重開始循環(huán)。
			 */
			xas_reset(&xas);
			continue;
		}
		/*
		 * （8）如果上面的 xas_store 分配內(nèi)存失敗，則 split_order
		 * 必然為 0 且會走到這里，并且在 xas 中標(biāo)記了 ENOMEM，
		 * xas_nomem 會捕捉這一問題并重試申請，如果申請成功，
		 * 會從循環(huán)開頭重試，否則 break。
		 */
		if (!xas_nomem(&xas, gfp))
			break;
	}

	if (xas_error(&xas))
		goto error;

	return 0;
error:
	return xas_error(&xas);
}

代碼大致可以分為下述步驟：

(1) 首先直接鎖 Xarray。

(2) (上鎖后)遍歷所需插入的 Index -> Folio 所覆蓋區(qū)域，若有 Folio，直接返回 -EEXIST，若有 Shadow，直接利用遍歷所用的 xa_state 獲取 shadow 的值與 order。

(3) (上鎖后)檢查步驟 8 (xas_split_alloc) 中分配內(nèi)存所用的 order 和 shadow 是否和步驟 2 剛看到的一致，若不一致，標(biāo)記分配為無效并釋放分配。(步驟 3 在第一次循環(huán)時，步驟 8 從未發(fā)生過)

(4) (上鎖后)如果 shadow order 大于 folio order，若步驟 8 未執(zhí)行或分配已失效，申請分配，跳至步驟 6，否則使用進(jìn)行 split。

(5) (上鎖后)已經(jīng)處理可能需要 split 的場景，直接存儲 Index -> Folio ⑤。

(6) 解鎖 Xarray。

(7) 如果步驟 4 申請了為 split 分配內(nèi)存，在此處使用步驟 2 所獲取的 shadow 和 order 通過 xas_split_alloc 分配 xa_node，并從頭開始循環(huán)。

(8) 如果步驟 5 在存儲時內(nèi)存分配失敗了，重試分配內(nèi)存，并從頭再開始循環(huán)。

新的插入邏輯確實更繞一點(diǎn)，不過在樂觀情況下(實際測試中樂觀情況占比幾乎是絕對性的壓倒的，即便是高壓力的并發(fā)場景)，若不涉及 split，只需要步驟 2 這里進(jìn)行一次走樹即可，這基本上已經(jīng)是理論上的最佳方式，大大節(jié)省了 Page Cache 插入時的開銷。而在需要 split 的場景，我們也節(jié)省了走樹的次數(shù)。

通過這一優(yōu)化，我們極大提升了大文件在 Page Cache 中的讀入性能，一個簡單的 fio 測試便有了約 10% 的性能提升，這一組 Patch 也以性能優(yōu)化為由合入了 6.10。

問題的根源

那么，問題出在哪里呢?答案就是 xas_split_alloc：xas_split_alloc 分配的數(shù)據(jù)因為發(fā)生在鎖外，所以其可能是過期的，并且過期數(shù)據(jù)必須及時釋放。

v6.9 之前的插入邏輯中，雖然會檢查 shadow 是否有過被 split，但如果已經(jīng)發(fā)生了 split，它僅僅是跳過了對 split 的調(diào)用，并未釋放 xas_split_alloc 可能產(chǎn)生的過期數(shù)據(jù)(6.9 中的步驟(6))。

通常過期數(shù)據(jù)未清理，可能會導(dǎo)致 leak，而非 corruption。但 Xarray 使用 xa_state 暫存分配數(shù)據(jù)，而 xa_state 中，xas_alloc() 和 xas_split_alloc() 都是使用 .xa_alloc 這一字段來記錄所分配的 xa_node。這就導(dǎo)致在 6.9 的代碼中，步驟 2 中xas_split_alloc() 所分配的過期數(shù)據(jù)可能會被步驟 7 中的 xas_store() 所使用(見 Xarray 存入處的解析，xas_store 可能會需要分配內(nèi)存，并會優(yōu)先使用 xa_state 中的分配數(shù)據(jù))，而導(dǎo)致 Xarray 中數(shù)據(jù)錯誤。

而在我們在新版本中，步驟(3)會檢查 xas_split_alloc 分配的數(shù)據(jù)是否依舊和當(dāng)前的 entry 完全對得上，并及時進(jìn)行釋放，讓后面的 xas_store 不會看到 xa_state 中的過期信息而錯誤使用它，并加以 comment 記錄了這一疑點(diǎn)，并且對 entry 值與 order 的完全匹配檢查也杜絕了其他可能的問題。

不過由于工作比較繁忙，我們并沒有過于糾結(jié)這一問題是否值得復(fù)現(xiàn)，而是與社區(qū)合作將這一變更以性能優(yōu)化的名義進(jìn)行了合入。

四、社區(qū)報告與修復(fù)

到了今年 9 月份，社區(qū)終于有人正式 highlight 了這一潛藏了許久的 Bug：

這個 Bug 本身復(fù)現(xiàn)概率很低，雖不能說是什么驚天問題，但這類 race 問題確實總是令人非常頭痛，有時也會成為上游開發(fā)的 Blocker。因為缺乏 reproducer，同時沒有有效的 debug 信息，社區(qū)很大程度上也只能盲猜。就像開頭我們已經(jīng)介紹過的，這一問題讓社區(qū)的幾位 Maintainer 都頗為困惑。不過由于我們的優(yōu)化和 Fix Patch 已經(jīng)在幾個月前就合入了，上游開發(fā)并未受阻，F(xiàn)ix 也很快就回合到 LTS，最終為這一問題畫上了句號，并順帶讓更多運(yùn)行 Linux 的設(shè)備，都能快那么一點(diǎn)點(diǎn)。