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

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

大概兩個(gè)月前，一封名為《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ù)損毀問題。這乍看上去是一個(gè)頗為嚴(yán)重的 Bug，也確實(shí)引得了多個(gè)頂級(jí) Maintainer 的關(guān)注和排查。實(shí)際上該 Bug 較難觸發(fā)，但也確實(shí)讓社區(qū)和各大一線廠家很是頭痛，Meta，Cloudflare 都表示自己遇到過該問題，并已經(jīng) Revert XFS 的 Large Folio 特性，這才能保證內(nèi)部系統(tǒng)的穩(wěn)定性。

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

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

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

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

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

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

幾個(gè) commit 也被建議合入 Linux LTS。筆者提交了經(jīng)過簡(jiǎn)易修改的三個(gè) 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)潛入夜，潤(rùn)物細(xì)無(wú)聲。這并不是我們第一次解決內(nèi)核中的隱藏問題或疑難問題。隨著 Tencent OS “悟凈” 內(nèi)存節(jié)省技術(shù)對(duì) Linux 內(nèi)核內(nèi)存管理領(lǐng)域的深究與不斷保持與社區(qū)的緊密合作，在 Swap，Memory Cgroup，頁(yè)面與熱度管理等領(lǐng)域，我們一直有著長(zhǎng)期的上游貢獻(xiàn)，也有更多的未來規(guī)劃。這不僅讓我們對(duì) Linux 內(nèi)核內(nèi)存管理的應(yīng)用與落地不斷深入，同時(shí)也回饋了社區(qū)。

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

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

這次出現(xiàn)的問題其實(shí)是一個(gè)并不罕見的內(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 提供了簡(jiǎn)單易用的仿數(shù)組 API，讓大部分內(nèi)核組件可以像使用數(shù)組一樣使用 Radix Tree。用戶可以簡(jiǎn)單通俗地可以將 Xarray 抽象理解為一個(gè)很靈活而巨大 long / void * 數(shù)組，其 Index 范圍為 unsigned long。

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

1.Xarray介紹

Xarray 基礎(chǔ)概念并不復(fù)雜，正如上文提到，可以將其抽象理解為一個(gè)靈活的數(shù)組。這里我們將數(shù)組中存儲(chǔ)的元素稱之為 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 的存儲(chǔ)類型為 void *，即 Entry 也必須是 64 位，Entry 默認(rèn)值為 NULL(0)。

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

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)

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

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

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

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

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

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

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

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

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

3.Xarray 讀取

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

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

同時(shí)為了照顧一些特殊調(diào)用者，避免重復(fù)的走樹操作，Xarray 允許將 xa_state 暴露出來，讓用戶手動(dòng)使用如 xas_load 這樣的 API 手動(dòng)維護(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 會(huì)保持指向 xa_node，可以通過 xas_reload 等操作，在一些特殊場(chǎng)景避免重復(fù)的從向上下走樹這一過程。另外 Xarray 中的數(shù)據(jù)是被 RCU 保護(hù)的，因此讀取時(shí)只需要獲取 RCU 鎖即可(這里 xas_retry 就是為了防止撞上正在被釋放的 node)。

4.Xarray 存入

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

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

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

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

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

5.Xarray Multi Index

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

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

Multi Index 的場(chǎng)景會(huì)有一個(gè)特殊問題：例如，若如果這個(gè) Multi Index Entry 覆蓋的范圍的的值只有一個(gè)值需要修改的話，那整個(gè)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 完成對(duì)這個(gè) Multi Index Entry 對(duì)應(yīng)的 slot 的 update，才可以再進(jìn)一步修改子范圍內(nèi)的 Entry。

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

Xarray 會(huì)將多個(gè) Slot 記錄為 Sibling Slot 并指向最低位的 Slot，其中再保存 Entry。不過這種用法我們?cè)诖宋恼轮袑簳r(shí)忽略。

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

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

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

6.Page Cache 對(duì) Xarray 的使用

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

Page Cache 中的頁(yè)面 Entry 即為保存文件數(shù)據(jù)的文件頁(yè)，而 Shadow 是頁(yè)面從 Page Cache 中被淘汰后所留下的一個(gè)標(biāo)記：Shadow 用于在發(fā)生頁(yè)面再入讀入時(shí)計(jì)算頁(yè)面熱度和 Workingset 相關(guān)信息，輔助 LRU 進(jìn)行 Page Cache 熱度管理，從而在內(nèi)存有限時(shí)優(yōu)先存儲(chǔ)更常用的數(shù)據(jù)，提高 Page Cache 的緩存命中率。其具體原理我們?cè)诖宋恼轮胁蛔鲑樖觯梢詤⒖純?nèi)核代碼 mm/workingset.c 文件中的長(zhǎng)篇注釋。

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

有了以上這些背景知識(shí)，我們不妨直接從 v6.9 及以前版本的 Linux 內(nèi)核 Page Cache 插入代碼看起。Page Cache 在插入頁(yè)面時(shí)，大量使用了 Xarray 的高級(jí) API。我們這里提供一份刪去統(tǒng)計(jì)計(jì)數(shù)與 Trace 相關(guān)邏輯的精簡(jiǎ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，并讓其指向文件對(duì)應(yīng)的 Xarray。
	 * 每個(gè)文件的 inode 都有自己的 Xarray（&mapping->i_pages）來記錄
	 * 文件中 offset 到 Page Cache 數(shù)據(jù)頁(yè)或 Shadow 的關(guān)系。
	 */
	XA_STATE(xas, &mapping->i_pages, index);
	/*
	 * 如果是大頁(yè)（high order folio），有 folio_order > 1，這里告知
	 * Xarray 使用 Multi-Index 模式進(jìn)行存儲(chǔ)。
	 */
	xas_set_order(&xas, index, folio_order(folio));
	do {
		/*
		 * （1）這里 xa_get_order 會(huì)進(jìn)行一次完整無(wú)鎖走樹，獲取 index 對(duì)應(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 對(duì)應(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
		 * 對(duì)應(yīng) entry 的值，由這里的 xa_load 獲取 < ②  >。
		 *
		 * 這里對(duì)應(yīng)的場(chǎng)景是：一個(gè)高 order folio 被淘汰時(shí)會(huì)留有一個(gè)
		 * 高 order shadow，此時(shí)如果被淘汰的 folio 只有部分子
		 * folio 被讀入，則需要將高 order shadow entry 進(jìn)行 split，
		 * 并在 Xarray 子范圍內(nèi)，存入讀入的 folio，這樣后續(xù)的其他子
		 * folio 被讀入時(shí)仍舊能找到對(duì)應(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)行插入。
		 * 下方的所有操作都將是可靠無(wú)競(jìng)爭(zhēng)的。
		 */
		xas_lock_irq(&xas);
		/*
		 * （4）再次走樹遍歷并檢測(cè)要存入的 index -> folio 覆蓋區(qū)域內(nèi)有無(wú)現(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)部錯(cuò)誤會(huì)存儲(chǔ)在 xa_state 上，
				 * 外部錯(cuò)誤也可以通過 xas_set_err 存入，
				 * 并最后由 xas_error 獲取和返回。
				 */
				xas_set_err(&xas, -EEXIST);
				goto unlock;
			}
		}

		/*
		 * 如果代碼執(zhí)行到此處，old 必然為一個(gè) shadow。
		 */
		if (old) {
			/*
			 * 將 shadow 信息返回給調(diào)用者。
			 */
			if (shadowp)
				*shadowp = old;
			/*
			 * （5）這里再次檢測(cè)現(xiàn)存 entry 的 order，因?yàn)?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，對(duì)其進(jìn)行 split 。否則跳過 split。目前 split 必會(huì)分解為 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 的場(chǎng)景已經(jīng)在上面處理，
		 * 這里則是一個(gè)普通的 Xarray 插入操作。< ⑤  >
		 */
		xas_store(&xas, folio);
		if (xas_error(&xas))
			goto unlock;
unlock:
		/*
		 * （8）釋放鎖。
		 */
		xas_unlock_irq(&xas);
		/*
		 * （9）如果上面的插入因?yàn)榉峙鋬?nèi)存失敗而在 xa_state
		 * 中標(biāo)記了 ENOMEM，xas_nomem 會(huì)捕捉到這一問題
		 * 并重試申請(qǐng)，如果申請(qǐng)成功，會(huì)從循環(huán)開頭重試。
		 * 如果發(fā)生了其他問題，xas_nomem 會(huì)釋放可能存在
		 * 的 .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 所對(duì)應(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)有無(wú)現(xiàn)存 Folio，若有跳至步驟 8 ( ③ )。

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

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

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

(8) 解鎖 Xarray。

(9) 如果步驟 7 在鎖內(nèi)分配 xa_node 失敗了，重試分配，存入 xas.xa_alloc 并從頭再開始。如果步驟 4 或 7 因?yàn)槠渌蚴×耍尫趴赡艽嬖诘?xas.xa_alloc 并返回錯(cuò)誤。

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

三、問題發(fā)生

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

在審閱 Linux 內(nèi)核核心路徑代碼時(shí)，我們注意到了這一冗余的 Tree Walk，并認(rèn)為這一點(diǎn)作為內(nèi)核最核心的路徑之一，是非常值得優(yōu)化的，因此經(jīng)過幾個(gè)迭代和測(cè)試，對(duì)插入邏輯進(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)。
	 * 每個(gè)文件的 inode 都有自己的 Xarray（&mapping->i_pages）來記錄
	 * 文件 offset 到 Page Cache 數(shù)據(jù)頁(yè)或 Shadow 的關(guān)系。
	 */
	XA_STATE(xas, &mapping->i_pages, index);
	/*
	 * 一些稍后會(huì)用到的中間變量，表示由 xas_split_alloc 所分配
	 * 的 xa_node 所對(duì)應(yīng)的 order 和內(nèi)部填充的 entry（必為 Shadow）。
	 */
	void *alloced_shadow = NULL;
	int alloced_order = 0;
	/*
	 * 如果是大頁(yè)（high order folio），有 folio_order > 1，這里告知
	 * Xarray 使用 Multi-Index 模式進(jìn)行存儲(chǔ)。
	 */
	xas_set_order(&xas, index, folio_order(folio));
	/*
	 * 循環(huán)開始，直到插入成功或發(fā)生內(nèi)存分配失敗以外的錯(cuò)誤。
	 */
	for (;;) {
		int order = -1, split_order = 0;
		void *entry, *old = NULL;
		/*
		 * （1）這里直接鎖住 Xarray。隨后走樹遍歷（2），檢測(cè)要存入的
		 * index -> folio 覆蓋區(qū)域內(nèi)有無(wú)現(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)用者讓其處理
			 * 熱度信息。
			 *
			 * 注意此時(shí) xas_for_each_conflict 所暴露和維護(hù)的 xa_state
			 * 必然是指向 shadow 所在的 xa_node 的，所以我們可以直接
			 * 通過 xa_state 拿到 shadow entry 的 order。
			 *
			 * 這里引入了一個(gè)新的 helper：xas_get_order 直接利用
			 * xa_state 獲取該 entry 的 order，避免還需重新走樹。
			 */
			if (order == -1)
				order = xas_get_order(&xas);
		}

		/*
		 * （3）這里是針對(duì)第二次和之后的循環(huán)的一個(gè)步驟。
		 * 第一次循環(huán)這里 alloced_order 必為 0，什么都不會(huì)發(fā)生。
		 *
		 * 對(duì)于需要 split 的情況，必然需要 xas_split_alloc 進(jìn)行
		 * 內(nèi)存分配，這個(gè)分配會(huì)發(fā)生在更下方，并會(huì)記錄當(dāng)時(shí)分配
		 * 所對(duì)應(yīng)的 order 到 alloced_order 中表示已經(jīng)分配。
		 *
		 * 由于 xas_split_alloc 分配發(fā)生在鎖外，其分配的 xa_node
		 * 對(duì)應(yīng)的 shadow order 或 shadow value 可能都已經(jīng)發(fā)生變化，
		 * 這里檢測(cè)是否發(fā)生了變化，如果發(fā)生了，則清理分配數(shù)據(jù)。
		 * 并標(biāo)記 alloced_order 為 0 表示沒有可用 split 使用的內(nèi)存。
		 */
		if (alloced_order && (old != alloced_shadow || order != alloced_order)) {
			/* xas_destroy 會(huì)清理和釋放無(wú)效的 xa_node */
			xas_destroy(&xas);
			alloced_order = 0;
		}
		/*
		 * （4）如果代碼執(zhí)行到此處，old 若有值則必然為一個(gè) shadow，
		 * 也是可能需要 split 的情況。
		 */
		if (old) {
			/*
			 * 這里的 order 是在獲取 Xarray 鎖后獲得的所以是可靠的，
			 * 不需要重新檢查 entry。所以只要 order 大于新插入 folio
			 * 的 order 就肯定是需要 split。
			 *
			 * order > 0 檢查是一個(gè)優(yōu)化，可以減少對(duì)頁(yè)面信息的讀取。
			 */
			if (order > 0 && order > folio_order(folio)) {
				/*
				 * 對(duì)于需要 split 的情況，第一次循環(huán)這里 alloced_order
				 * 必為 0，也就是沒有可供 split 使用的內(nèi)存。跳到解鎖處
				 * 進(jìn)行分配。
				 * 第二次以及往后的循環(huán)這里 alloced_order 若有值，
				 * 則必然等于 entry 的 order （不等于的場(chǎng)景已經(jīng)被
				 * 步驟 3 處理)，可以安全進(jìn)行 split。
				 * 若 alloced_order 為 0，說明 xas_split_alloc 從未執(zhí)行
				 * 或者其分配的內(nèi)存已經(jīng)因?yàn)檫^期被步驟 3 釋放，申請(qǐng)
				 * 分配對(duì)應(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 的場(chǎng)景已經(jīng)在上面處理，
		 * 這里則是一個(gè)普通的 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)行分配的
		 * 時(shí)候會(huì)在這里看到 split_order != 0。
		 * （第一次循環(huán)，或上次分配的內(nèi)存被步驟 3 釋放了）
		 *
		 * 嘗試使用持鎖時(shí)獲取的 entry order (split_order)
		 * 分配所需的內(nèi)存，并使用持鎖時(shí)所記錄的 entry 值填
		 * 充新分配的 xa_node。
		 */
		if (split_order) {
			xas_split_alloc(&xas, old, split_order, gfp);
			/*
			 * 在鎖外內(nèi)存分配也失敗了，無(wú)法處理，返回錯(cuò)誤。
			 */
			if (xas_error(&xas))
				goto error;
			/*
			 * 記錄此時(shí)已分配的 xa_node 對(duì)應(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 且會(huì)走到這里，并且在 xas 中標(biāo)記了 ENOMEM，
		 * xas_nomem 會(huì)捕捉這一問題并重試申請(qǐng)，如果申請(qǐng)成功，
		 * 會(huì)從循環(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)記分配為無(wú)效并釋放分配。(步驟 3 在第一次循環(huán)時(shí)，步驟 8 從未發(fā)生過)

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

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

(6) 解鎖 Xarray。

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

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

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

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

問題的根源

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

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

通常過期數(shù)據(jù)未清理，可能會(huì)導(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ù)可能會(huì)被步驟 7 中的 xas_store() 所使用(見 Xarray 存入處的解析，xas_store 可能會(huì)需要分配內(nèi)存，并會(huì)優(yōu)先使用 xa_state 中的分配數(shù)據(jù))，而導(dǎo)致 Xarray 中數(shù)據(jù)錯(cuò)誤。

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

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

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

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

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