路徑名查詢

本文基於 lwn.net 上發表的三篇文章：

由 Neil Brown 撰寫，Al Viro 和 Jon Corbet 協助。此後已更新，以反映核心中的更改，包括

  • 每目錄並行名稱查詢。

  • openat2() 解析限制標誌。

路徑名查詢簡介

路徑名查詢最明顯的方面，幾乎無需深入探索即可發現，就是其複雜性。它包含許多規則、特殊情況和實現替代方案，這些都可能讓粗心的讀者感到困惑。計算機科學早就熟悉這種複雜性，並擁有幫助管理它的工具。我們將廣泛使用的一種工具是“分而治之”。在分析的早期部分，我們將把符號連結（symlinks）分開處理——把它們留到最後一部分。在處理符號連結之前，我們還有另一個重要的劃分，它是基於 VFS 的鎖定方法，這將使我們能夠單獨回顧“REF-walk”和“RCU-walk”。但我們有些超前了。首先我們需要澄清一些重要的低階區別。

有兩種...

路徑名（有時也稱為“檔名”）用於標識檔案系統中的物件，大多數讀者對此都很熟悉。它們包含兩種元素：“斜槓”，即一個或多個“/”字元的序列；以及“元件”，即一個或多個非“/”字元的序列。這些形成兩種路徑。以斜槓開頭的路徑是“絕對路徑”，從檔案系統根目錄開始。其他路徑是“相對路徑”，從當前目錄開始，或者從透過檔案描述符指定給“*at()”系統呼叫（例如 openat()）的某個其他位置開始。

描述第二種路徑以元件開頭很吸引人，但這並不總是準確的：路徑名可以既沒有斜槓也沒有元件，換句話說，它可以是空的。這在 POSIX 中通常是禁止的，但 Linux 中的一些“*at()”系統呼叫在給定 AT_EMPTY_PATH 標誌時允許這樣做。例如，如果你有一個指向可執行檔案的開啟檔案描述符，你可以透過呼叫 execveat() 並傳遞該檔案描述符、一個空路徑和 AT_EMPTY_PATH 標誌來執行它。

這些路徑可以分為兩部分：最終元件和其餘部分。“其餘部分”是簡單的部分。在所有情況下，它必須標識一個已存在的目錄，否則將報告 ENOENT 或 ENOTDIR 等錯誤。

最終元件則不那麼簡單。不僅不同的系統呼叫對其解釋大相徑庭（例如，有些建立它，有些不建立），而且它甚至可能不存在：空路徑名和僅由斜槓組成的路徑名都沒有最終元件。如果它確實存在，它可能是“.”或“..”，這些與其它元件的處理方式截然不同。

如果路徑名以斜槓結尾，例如“/tmp/foo/”，可能很想認為它有一個空的最終元件。在許多方面，這會產生正確的結果，但並非總是如此。特別是，mkdir() 和 rmdir() 都建立或刪除由最終元件命名的目錄，並且它們被要求能夠處理以“/”結尾的路徑名。根據 POSIX：

包含至少一個非斜槓字元並以一個或多個尾隨斜槓字元結尾的路徑名，除非尾隨斜槓字元之前的最後一個路徑名元件命名一個現有目錄，或者是在路徑名解析後立即為一個目錄建立的目錄項，否則將無法成功解析。

Linux 路徑遍歷程式碼（主要在 fs/namei.c 中）處理所有這些問題：將路徑分解為元件，將“其餘部分”與最終元件完全分開處理，並檢查尾隨斜槓是否未在不允許的地方使用。它還解決了併發訪問的重要問題。

當一個程序正在查詢路徑名時，另一個程序可能正在進行會影響該查詢的更改。一個相當極端的例子是，如果“a/b”被重新命名為“a/c/b”，而另一個程序正在查詢“a/b/..”，那麼該程序可能會成功解析到“a/c”。大多數競態條件要微妙得多，路徑名查詢的一大部分任務就是防止它們產生破壞性影響。許多可能的競態條件在“dcache”的上下文中表現得最清楚，理解它對於理解路徑名查詢至關重要。

不僅僅是快取

“dcache”快取每個檔案系統中關於名稱的資訊，以便快速查詢。每個條目（稱為“dentry”）包含三個重要欄位：元件名稱、指向父 dentry 的指標以及指向“inode”的指標，inode 包含該父目錄中具有給定名稱的物件的更多資訊。inode 指標可以為 NULL，表示該名稱在父目錄中不存在。雖然目錄的 dentry 中可能存在指向子目錄 dentry 的連結，但該連結不用於路徑名查詢，因此在此不予考慮。

dcache 除了加速查詢之外還有許多用途。其中一個特別相關的是它與掛載表緊密整合，掛載表記錄了哪個檔案系統掛載在哪裡。掛載表實際儲存的是哪個 dentry 掛載在哪個其他 dentry 之上。

考慮 dcache 時，我們又遇到了“兩種型別”的區別：檔案系統有兩種型別。

一些檔案系統確保 dcache 中的資訊始終完全準確（儘管不一定完整）。這使得 VFS 可以在不檢查檔案系統的情況下確定特定檔案是否存在，並意味著 VFS 可以保護檔案系統免受某些競態條件和其他問題的影響。這些通常是“本地”檔案系統，例如 ext3、XFS 和 Btrfs。

其他檔案系統不提供該保證，因為它們不能。這些通常是跨網路共享的檔案系統，無論是像 NFS 和 9P 這樣的遠端檔案系統，還是像 ocfs2 或 cephfs 這樣的叢集檔案系統。這些檔案系統允許 VFS 重新驗證快取的資訊，並且必須提供自己的保護以防止棘手的競態條件。VFS 可以透過 dentry 中設定的 DCACHE_OP_REVALIDATE 標誌來檢測這些檔案系統。

REF-walk：使用引用計數和自旋鎖的簡單併發管理

在對所有這些劃分進行了仔細分類之後，我們現在可以開始研究路徑遍歷的實際過程。特別是，我們將從路徑名中“其餘部分”的處理開始，並重點關注“REF-walk”併發管理方法。如果你忽略所有僅在設定了“LOOKUP_RCU”（表示使用 RCU-walk）時執行的地方，此程式碼可以在 link_path_walk() 函式中找到。

REF-walk 在鎖和引用計數方面相當“強硬”。雖然不像過去“大核心鎖”時代那樣強硬，但肯定不害怕在需要時獲取鎖。它使用了各種不同的併發控制機制。這裡假設讀者對各種原語有背景知識，或者可以從其他地方（例如 Meet the Lockers）瞭解它們。

REF-walk 使用的鎖定機制包括：

dentry->d_lockref

這使用 lockref 原語來提供自旋鎖和引用計數。這個原語的特別之處在於，概念上的“鎖定；增加引用計數；解鎖”序列通常可以透過單個原子記憶體操作完成。

持有 dentry 的引用可確保 dentry 不會突然被釋放並用於其他目的，從而使各種欄位中的值按預期執行。它還在一定程度上保護了對 inode 的 ->d_inode 引用。

dentry 及其 inode 之間的關聯是相當永久的。例如，當檔案重新命名時，dentry 和 inode 會一起移動到新位置。當檔案建立時，dentry 最初將是負的（即 d_inode 為 NULL），並將在建立過程中分配給新的 inode。

當檔案被刪除時，這可以在快取中透過兩種方式反映：一是將 d_inode 設定為 NULL，二是從用於在父目錄中查詢名稱的雜湊表（稍後描述）中移除它。如果 dentry 仍在被使用，則使用第二種選項，因為在檔案被刪除後繼續使用開啟的檔案是完全合法的，並且保留 dentry 有助於此。如果 dentry 沒有被其他方式使用（即 d_lockref 中的引用計數為 1），則只有此時才會將 d_inode 設定為 NULL。這樣做對於非常常見的情況效率更高。

因此，只要持有對 dentry 的計數引用，非 NULL 的 ->d_inode 值就不會被改變。

dentry->d_lock

d_lock 是上述 d_lockref 中自旋鎖的同義詞。就我們的目的而言，持有此鎖可防止 dentry 被重新命名或解除連結。特別是，它的父項（d_parent）和它的名稱（d_name）不能被改變，並且它不能從 dentry 雜湊表中移除。

在目錄中查詢名稱時，REF-walk 會對它在雜湊表中找到的每個候選 dentry 獲取 d_lock，然後檢查父項和名稱是否正確。因此，它在快取中搜索時不會鎖定父項；它只鎖定子項。

當查詢給定名稱的父項（以處理“..”）時，REF-walk 可以獲取 d_lock 以獲取對 d_parent 的穩定引用，但它首先嚐試一種更輕量級的方法。正如在 dget_parent() 中所見，如果可以獲取對父項的引用，並且隨後發現 d_parent 沒有改變，那麼實際上沒有必要對子項獲取鎖。

rename_lock

在給定目錄中查詢給定名稱涉及從兩個值（名稱和目錄的 dentry）計算雜湊值，訪問雜湊表中的相應槽位，並搜尋在那裡找到的連結串列。

當 dentry 被重新命名時，名稱和父 dentry 都可以更改，因此雜湊值也幾乎肯定會更改。這將把 dentry 移動到雜湊表中的不同鏈。如果檔名搜尋碰巧正在查詢以這種方式移動的 dentry，它最終可能會沿著錯誤的鏈繼續搜尋，從而錯過正確鏈的一部分。

名稱查詢過程（d_lookup()）*不*嘗試阻止這種情況發生，而只是在發生時檢測到它。rename_lock 是一個 seqlock，每當有 dentry 被重新命名時，它都會更新。如果 d_lookup 發現在它掃描雜湊表中的一個鏈失敗時發生了重新命名，它會簡單地重試。

rename_lock 也用於檢測和防禦在解析“..”時（父目錄被移到根目錄之外，繞過 path_equal() 檢查）針對 LOOKUP_BENEATH 和 LOOKUP_IN_ROOT 的潛在攻擊。如果在查詢過程中 rename_lock 被更新，並且路徑遇到“..”，則表示發生了潛在攻擊，handle_dots() 將以 -EAGAIN 退出。

inode->i_rwsem

i_rwsem 是一個讀/寫訊號量，它將對特定目錄的所有更改序列化。這確保了例如 unlink() 和 rename() 不能同時發生。它還在檔案系統被要求查詢當前不在 dcache 中的名稱時，或者（可選地）在使用 readdir() 檢索目錄中的條目列表時，保持目錄的穩定。

這與 d_lock 具有互補作用：目錄上的 i_rwsem 保護該目錄中的所有名稱，而名稱上的 d_lock 僅保護目錄中的一個名稱。對 dcache 的大多數更改都會在相關目錄 inode 上持有 i_rwsem，並在更改發生時短暫地對一個或多個 dentry 獲取 d_lock。一個例外是當空閒 dentry 因記憶體壓力而從 dcache 中移除時。這使用 d_lock，但 i_rwsem 不起作用。

該訊號量以兩種不同的方式影響路徑名查詢。首先，它防止在目錄中查詢名稱時發生更改。walk_component() 首先使用 lookup_fast()，後者反過來檢查名稱是否在快取中，僅使用 d_lock 鎖定。如果未找到名稱，則 walk_component() 會回退到 lookup_slow()，後者在 i_rwsem 上獲取共享鎖，再次檢查名稱是否不在快取中，然後呼叫檔案系統以獲取確定性答案。無論結果如何，新的 dentry 都將被新增到快取中。

其次，當路徑名查詢到達最終元件時，有時需要在執行最後一次查詢之前對 i_rwsem 獲取排他鎖，以便實現所需的排他性。路徑查詢如何選擇獲取或不獲取 i_rwsem 是後續章節中討論的問題之一。

如果兩個執行緒同時嘗試查詢同一個名稱（一個尚未在 dcache 中的名稱），i_rwsem 上的共享鎖將無法阻止它們同時新增具有相同名稱的新 dentry。由於這會導致混淆，因此採用了額外一層的互鎖，基於一個輔助雜湊表（in_lookup_hashtable）和一個每 dentry 標誌位（DCACHE_PAR_LOOKUP）。

要在僅持有 i_rwsem 共享鎖的情況下向快取新增新的 dentry，執行緒必須呼叫 d_alloc_parallel()。這會分配一個 dentry，在其中儲存所需的名稱和父項，檢查主雜湊表或輔助雜湊表中是否已存在匹配的 dentry，如果不存在，則將新分配的 dentry 儲存在輔助雜湊表中，並設定 DCACHE_PAR_LOOKUP。

如果在主雜湊表中找到匹配的 dentry，則返回該 dentry，呼叫者便可知它在與另一個執行緒新增條目的競爭中失敗了。如果在任何快取中都沒有找到匹配的 dentry，則返回新分配的 dentry，呼叫者可以透過 DCACHE_PAR_LOOKUP 的存在來檢測這一點。在這種情況下，它知道它贏得了任何競爭，現在負責要求檔案系統執行查詢並找到匹配的 inode。當查詢完成時，它必須呼叫 d_lookup_done()，該函式會清除標誌並執行其他一些內部管理工作，包括從輔助雜湊表中移除 dentry——它通常已經新增到主雜湊表中了。請注意，一個 struct waitqueue_head 會傳遞給 d_alloc_parallel()，並且必須在 waitqueue_head 仍在作用域內時呼叫 d_lookup_done()。

如果在輔助雜湊表中找到匹配的 dentry，d_alloc_parallel() 還有更多工作要做。它首先等待 DCACHE_PAR_LOOKUP 被清除，使用傳遞給贏得競態的 d_alloc_parallel() 例項的 wait_queue，該 wait_queue 將由對 d_lookup_done() 的呼叫喚醒。然後它檢查 dentry 是否已新增到主雜湊表。如果已新增，則返回該 dentry，呼叫者只是看到它在任何競爭中失敗了。如果它尚未新增到主雜湊表，最可能的解釋是使用 d_splice_alias() 添加了其他 dentry。無論如何，d_alloc_parallel() 會從頭開始重複所有查詢，並且通常會從主雜湊表中返回一些東西。

mnt->mnt_count

mnt_count 是“mount”結構上的每 CPU 引用計數器。這裡的“每 CPU”意味著增加計數成本很低，因為它只使用 CPU 本地記憶體，但檢查計數是否為零成本很高，因為它需要檢查每個 CPU。獲取 mnt_count 引用可防止掛載結構因常規解除安裝操作而消失，但不會阻止“惰性”解除安裝。因此，持有 mnt_count 並不能確保掛載保留在名稱空間中，特別是不能穩定到掛載點 dentry 的連結。然而，它確實確保了 mount 資料結構保持一致，並且它提供了對掛載檔案系統根 dentry 的引用。因此，透過 ->mnt_count 的引用提供了對已掛載 dentry 的穩定引用，但不是對掛載點 dentry 的穩定引用。

mount_lock

mount_lock 是一個全域性的 seqlock，有點像 rename_lock。它可用於檢查是否對任何掛載點進行了任何更改。

在向下遍歷樹（遠離根）時，此鎖用於在跨越掛載點時檢查跨越是否安全。也就是說，讀取 seqlock 中的值，然後程式碼查詢當前目錄上掛載的掛載點（如果有），並增加 mnt_count。最後，將 mount_lock 中的值與舊值進行比較。如果沒有更改，則跨越是安全的。如果發生了更改，則 mnt_count 遞減，整個過程重新嘗試。

當透過遵循“..”連結向上遍歷樹（朝向根）時，需要更加小心。在這種情況下，seqlock（包含計數器和自旋鎖）被完全鎖定，以防止在向上移動時對任何掛載點進行任何更改。此鎖定是穩定到掛載點 dentry 的連結所必需的，而掛載本身的引用計數無法保證這一點。

mount_lock 也用於檢測和防禦在解析“..”時（父目錄被移到根目錄之外，繞過 path_equal() 檢查）針對 LOOKUP_BENEATH 和 LOOKUP_IN_ROOT 的潛在攻擊。如果在查詢過程中 mount_lock 被更新，並且路徑遇到“..”，則表示發生了潛在攻擊，handle_dots() 將以 -EAGAIN 退出。

RCU

最後，全域性（但極其輕量級的）RCU 讀鎖會不時地持有，以確保某些資料結構不會意外地被釋放。

特別是在掃描 dcache 雜湊表和掛載點雜湊表中的鏈時持有。

結合 struct nameidata

在路徑遍歷的整個過程中，當前狀態儲存在 struct nameidata 中，“namei”是傳統名稱——追溯到 Unix 第一版——用於將“名稱”轉換為“inode”的函式。struct nameidata 包含（除其他欄位外）：

struct path path

一個 path 包含一個 struct vfsmount（嵌入在 struct mount 中）和一個 struct dentry。它們共同記錄遍歷的當前狀態。它們最初指向起點（當前工作目錄、根目錄或由檔案描述符標識的某個其他目錄），並在每一步中更新。透過 d_lockref 和 mnt_count 的引用始終被持有。

struct qstr last

這是一個字串及其長度（即 *不* 以 nul 終止），它是路徑名中的“下一個”元件。

int last_type

這是一個 LAST_NORM、LAST_ROOT、LAST_DOT 或 LAST_DOTDOT 之一。last 欄位僅在型別為 LAST_NORM 時有效。

struct path root

這用於儲存對檔案系統有效根的引用。通常不需要該引用，因此此欄位僅在首次使用時或請求非標準根時才分配。在 nameidata 中保留引用可確保在整個路徑遍歷過程中只有一個根生效，即使它與 chroot() 系統呼叫發生競態。

應該注意的是，在 LOOKUP_IN_ROOT 或 LOOKUP_BENEATH 的情況下，有效根成為傳遞給 openat2()（暴露這些 LOOKUP_ 標誌的函式）的目錄檔案描述符。

當滿足以下兩個條件之一時，需要根目錄：（1）路徑名或符號連結以“/”開頭；或（2）正在處理“..”元件，因為從根目錄的“..”必須始終停留在根目錄。使用的值通常是呼叫程序的當前根目錄。可以提供替代根，例如當 sysctl() 呼叫 file_open_root() 時，以及當 NFSv4 或 Btrfs 呼叫 mount_subtree() 時。在每種情況下，路徑名都在檔案系統的特定部分中查詢，並且不允許查詢逃離該子樹。它的工作方式有點像區域性 chroot()。

忽略符號連結的處理，我們現在可以描述“link_path_walk()”函式，它處理除最終元件之外的所有內容的查詢，如下所示：

給定一個路徑 (name) 和一個 nameidata 結構 (nd)，檢查當前目錄是否具有執行許可權，然後將 name 推進一個元件，同時更新 last_type 和 last。如果這是最終元件，則返回，否則呼叫 walk_component() 並從頭開始重複。

walk_component() 甚至更簡單。如果元件是 LAST_DOTS，它會呼叫 handle_dots()，後者執行已描述的必要鎖定。如果它發現一個 LAST_NORM 元件，它首先呼叫“lookup_fast()”，該函式只在 dcache 中查詢，但如果檔案系統是那種型別的檔案系統，它會要求檔案系統重新驗證結果。如果這沒有得到好的結果，它會呼叫“lookup_slow()”，該函式獲取 i_rwsem 的共享鎖，重新檢查快取，然後要求檔案系統找到最終答案。

作為 walk_component() 的最後一步，step_into() 將直接從 walk_component() 或 handle_dots() 中呼叫。它呼叫 handle_mounts() 來檢查和處理掛載點，其中會建立一個新的 struct path，包含對新 dentry 的計數引用以及對新 vfsmount 的引用（僅當其與之前的 vfsmount 不同時才計數）。然後，如果存在符號連結，step_into() 呼叫 pick_link() 來處理它，否則它會在 struct nameidata 中安裝新的 struct path，並丟棄不需要的引用。

這種“手把手”的順序——在釋放對前一個 dentry 的引用之前獲取對新 dentry 的引用——可能看起來很明顯，但值得指出，以便我們能在“RCU-walk”版本中識別出它的類似物。

處理最終元件

link_path_walk() 只遍歷到設定 nd->last 和 nd->last_type 以引用路徑的最終元件。它不會在最後一次呼叫 walk_component()。處理該最終元件的任務留給呼叫者解決。這些呼叫者是 path_lookupat()、path_parentat() 和 path_openat()，它們各自處理不同系統呼叫的不同要求。

path_parentat() 顯然是最簡單的——它只是在 link_path_walk() 周圍包裝了一些內務處理，並向呼叫者返回父目錄和最終元件。呼叫者要麼旨在建立名稱（透過 filename_create()），要麼刪除或重新命名名稱（在這種情況下使用 user_path_parent()）。他們將使用 i_rwsem 來排除其他更改，同時他們驗證並執行其操作。

path_lookupat() 也差不多簡單——它用於需要現有物件的情況，例如透過 stat() 或 chmod()。它本質上只是透過呼叫 lookup_last() 來對最終元件呼叫 walk_component()。path_lookupat() 只返回最終的 dentry。值得注意的是，當設定了標誌 LOOKUP_MOUNTPOINT 時，path_lookupat() 將在 nameidata 中取消設定 LOOKUP_JUMPED，以便在隨後的路徑遍歷中不會呼叫 d_weak_revalidate()。這在解除安裝不可訪問的檔案系統（例如由宕機的 NFS 伺服器提供的檔案系統）時很重要。

最後，path_openat() 用於 open() 系統呼叫；它在以“open_last_lookups()”開頭的輔助函式中包含了處理 O_CREAT（帶或不帶 O_EXCL）、最終“/”字元和尾隨符號連結等不同微妙之處所需的所有複雜性。我們將在本系列的最後一部分重新探討這一點，該部分重點關注這些符號連結。“open_last_lookups()”有時會（但並非總是）獲取 i_rwsem，具體取決於它發現的內容。

這些函式，或呼叫它們的函式，都需要警惕最終元件不是 LAST_NORM 的可能性。如果查詢的目標是建立某個東西，那麼 last_type 的任何值（除了 LAST_NORM）都將導致錯誤。例如，如果 path_parentat() 報告 LAST_DOTDOT，那麼呼叫者就不會嘗試建立該名稱。它們還透過測試 last.name[last.len] 來檢查尾隨斜槓。如果最終元件之外有任何字元，那它必須是一個尾隨斜槓。

重新驗證和自動掛載

除了符號連結之外，“REF-walk”過程還有兩個尚未涵蓋的部分。一個是處理陳舊的快取條目，另一個是自動掛載。

在需要的檔案系統上，查詢例程將呼叫 ->d_revalidate() dentry 方法以確保快取資訊是當前的。這通常會確認有效性或從伺服器更新一些詳細資訊。在某些情況下，它可能會發現路徑上游發生了變化，並且以前認為有效的東西實際上並非如此。發生這種情況時，整個路徑的查詢會被中止，並設定“LOOKUP_REVAL”標誌進行重試。這會強制重新驗證更徹底。我們將在下一篇文章中看到有關此重試過程的更多詳細資訊。

自動掛載點是檔案系統中的位置，在這些位置上嘗試查詢名稱可能會觸發該查詢的處理方式發生變化，特別是透過在該處掛載檔案系統。這些內容在 Linux 文件樹中的 autofs - 工作原理 中有更詳細的介紹，但此處需要特別指出一些與路徑查詢相關的注意事項。

Linux VFS 有一個“託管”dentry 的概念。關於這些 dentry，有三點可能有趣的地方，它們對應於 dentry->d_flags 中可能設定的三個不同標誌：

DCACHE_MANAGE_TRANSIT

如果設定了此標誌，則檔案系統已請求在處理任何可能的掛載點之前呼叫 d_manage() dentry 操作。這可以提供兩種特定服務：

它可以阻塞以避免競態條件。如果正在解除安裝一個自動掛載點，d_manage() 函式通常會等待該過程完成，然後才允許新的查詢繼續並可能觸發新的自動掛載。

它可以選擇性地只允許某些程序透過掛載點。當伺服器程序管理自動掛載時，它可能需要訪問目錄而不觸發正常的自動掛載處理。該伺服器程序可以向 autofs 檔案系統表明身份，然後 autofs 將透過返回 -EISDIR 來給予其透過 d_manage() 的特殊許可權。

DCACHE_MOUNTED

此標誌設定在每個被掛載的 dentry 上。由於 Linux 支援多個檔案系統名稱空間，因此 dentry 可能並未在此名稱空間中掛載，而是在其他名稱空間中掛載。因此，此標誌被視為一個提示，而非承諾。

如果此標誌已設定，並且 d_manage() 未返回 -EISDIR，則呼叫 lookup_mnt() 來檢查掛載雜湊表（尊重前面描述的 mount_lock），並可能返回新的 vfsmount 和新的 dentry（兩者均帶有計數引用）。

DCACHE_NEED_AUTOMOUNT

如果 d_manage() 允許我們走到這一步，並且 lookup_mnt() 沒有找到掛載點，那麼這個標誌會觸發呼叫 d_automount() dentry 操作。

鑑於 d_automount() 操作可以任意複雜，並且可能與伺服器程序等進行通訊，它最終應該要麼報告發生錯誤，要麼報告沒有要掛載的內容，或者提供一個包含新的 dentry 和 vfsmount 的更新的 struct path。

在後一種情況下，將呼叫 finish_automount() 以安全地將新掛載點安裝到掛載表中。

這裡沒有新的重要鎖定，並且重要的是，在此處理過程中不持有任何鎖（僅持有計數引用），因為這極有可能導致長時間延遲。這在下次我們研究對延遲特別敏感的 RCU-walk 時將變得更加重要。

RCU-walk - Linux 中更快的路徑名查詢

RCU-walk 是 Linux 中執行路徑名查詢的另一種演算法。它在許多方面與 REF-walk 相似，並且兩者共享相當多的程式碼。RCU-walk 的顯著區別在於它如何允許併發訪問的可能性。

我們注意到 REF-walk 很複雜，因為它有許多細節和特殊情況。RCU-walk 透過簡單地拒絕處理某些情況來降低這種複雜性——它反而回退到 REF-walk。RCU-walk 的困難來自另一個方向：不熟悉。依賴 RCU 時的鎖定規則與傳統鎖定截然不同，因此當我們遇到這些規則時，我們將花費更多時間。

明確的角色劃分

管理併發最簡單的方法是強制阻止任何其他執行緒更改給定執行緒正在檢視的資料結構。在沒有其他執行緒會想到更改資料並且許多不同執行緒希望同時讀取的情況下，這可能會非常昂貴。即使使用允許多個併發讀取器的鎖，簡單地更新當前讀取器數量的計數也可能帶來不必要的開銷。因此，當讀取其他程序未更改的共享資料結構時，目標是完全避免向記憶體寫入任何內容。不獲取鎖，不增加計數，不留下任何痕跡。

已經描述的 REF-walk 機制顯然不遵循這一原則，但它確實設計用於可能存在其他執行緒修改資料的情況。相比之下，RCU-walk 旨在處理常見情況：存在大量頻繁讀取器而只有偶爾寫入器。這在檔案系統樹的所有部分可能不常見，但在許多部分會是這樣。對於其他部分，重要的是 RCU-walk 可以快速回退到使用 REF-walk。

路徑名查詢總是以 RCU-walk 模式開始，但只有當它查詢的內容在快取中且穩定時才保持該模式。它輕快地沿著快取的檔案系統映像向下“舞蹈”，不留下任何痕跡，並仔細觀察其位置，以確保它不會出錯。如果它發現某些東西已更改或正在更改，或者某些東西不在快取中，那麼它會嘗試優雅地停止並切換到 REF-walk。

這種停止需要獲取對當前 vfsmount 和 dentry 的計數引用，並確保這些仍然有效——即使用 REF-walk 遍歷路徑也會找到相同的條目。這是 RCU-walk 必須保證的一個不變式。它只能做出 REF-walk 在同時遍歷樹時也能做出的決策，例如選擇下一步。如果優雅停止成功，路徑的其餘部分將由可靠但略顯遲緩的 REF-walk 處理。如果 RCU-walk 發現它無法優雅停止，它會簡單地放棄並使用 REF-walk 從頭開始重新啟動。

這種“嘗試 RCU-walk，如果失敗則嘗試 REF-walk”的模式可以清楚地在 filename_lookup()、filename_parentat()、do_filp_open() 和 do_file_open_root() 等函式中看到。這四個函式大致對應於我們前面遇到的三個 path_*() 函式，每個函式都呼叫 link_path_walk()。path_*() 函式會使用不同的模式標誌進行呼叫，直到找到一個有效模式。它們首先在設定了 LOOKUP_RCU 的情況下呼叫，以請求“RCU-walk”。如果失敗並返回錯誤 ECHILD，它們會再次在沒有特殊標誌的情況下呼叫，以請求“REF-walk”。如果其中任何一個報告錯誤 ESTALE，則會進行最後一次嘗試，設定 LOOKUP_REVAL（且不設定 LOOKUP_RCU），以確保快取中找到的條目被強制重新驗證——通常只有當檔案系統確定它們太舊而不可信時才重新驗證條目。

LOOKUP_RCU 嘗試可能會在內部放棄該標誌並切換到 REF-walk，但此後絕不會嘗試切換回 RCU-walk。阻礙 RCU-walk 的地方更有可能靠近葉子，因此切換回來幾乎不會有任何好處。

RCU 和 Seqlocks：快速輕量

RCU 對 RCU-walk 模式至關重要，這並不奇怪。rcu_read_lock() 在 RCU-walk 遍歷路徑的整個過程中都被持有。它提供的具體保證是，在持有鎖期間，關鍵資料結構——dentries、inodes、super_blocks 和 mounts——不會被釋放。它們可能以某種方式被解除連結或失效，但記憶體不會被重新利用，因此各個欄位中的值仍然有意義。這是 RCU 提供的唯一保證；其他一切都使用 seqlock 完成。

正如我們上面看到的，REF-walk 持有對當前 dentry 和當前 vfsmount 的計數引用，並且在獲取對“下一個”dentry 或 vfsmount 的引用之前不會釋放這些引用。它有時也會獲取 d_lock 自旋鎖。獲取這些引用和鎖是為了防止某些更改發生。RCU-walk 不得獲取這些引用或鎖，因此無法阻止此類更改。相反，它會檢查是否發生了更改，如果發生了更改，則中止或重試。

為了保持上述不變式（即 RCU-walk 只能做出 REF-walk 也能做出的決策），它必須在 REF-walk 持有引用的相同或附近位置進行檢查。因此，當 REF-walk 增加引用計數或獲取自旋鎖時，RCU-walk 會使用 read_seqcount_begin() 或類似函式取樣 seqlock 的狀態。當 REF-walk 減少計數或釋放鎖時，RCU-walk 會使用 read_seqcount_retry() 或類似函式檢查取樣的狀態是否仍然有效。

然而，seqlock 還有更多內容。如果 RCU-walk 訪問受 seqlock 保護的結構中兩個不同的欄位，或者兩次訪問同一個欄位，則無法先驗保證這些訪問之間存在任何一致性。當需要一致性時（通常是這樣），RCU-walk 必須複製一份，然後使用 read_seqcount_retry() 來驗證該副本。

read_seqcount_retry() 不僅檢查序列號，還強制設定記憶體屏障，以確保 CPU 或編譯器不會將 *呼叫之前* 的任何記憶體讀取指令延遲到 *呼叫之後*。一個簡單的例子可以在 slow_dentry_cmp() 中看到，對於不使用簡單位元組級名稱相等性的檔案系統，該函式會呼叫檔案系統來將名稱與 dentry 進行比較。長度和名稱指標被複制到區域性變數中，然後呼叫 read_seqcount_retry() 以確認兩者一致，然後才呼叫 ->d_compare()。當使用標準檔名比較時，則呼叫 dentry_cmp()。值得注意的是，它 *不* 使用 read_seqcount_retry()，而是有一個詳細的註釋解釋為什麼不需要一致性保證。隨後的 read_seqcount_retry() 將足以捕獲此時可能發生的任何問題。

在簡單回顧了 seqlock 之後，我們可以看看 RCU-walk 如何使用 seqlock 的更大圖景。

mount_lock 和 nd->m_seq

我們在 REF-walk 中已經遇到過 mount_lock seqlock，它用於確保安全地跨越掛載點。RCU-walk 也為此目的使用它，但用途遠不止於此。

RCU-walk 在向下遍歷樹時，不獲取每個 vfsmount 的計數引用，而是在遍歷開始時取樣 mount_lock 的狀態，並將此初始序列號儲存在 struct nameidata 的 m_seq 欄位中。這一個鎖和一個序列號用於驗證對所有 vfsmounts 的所有訪問以及所有掛載點交叉。由於掛載表的更改相對較少，因此在發生任何“掛載”或“解除安裝”時，回退到 REF-walk 是合理的。

在 RCU-walk 序列結束時，m_seq 會被檢查（使用 read_seqretry()），無論是在路徑的其餘部分切換到 REF-walk 還是到達路徑末尾。在向下遍歷掛載點（在 __follow_mount_rcu() 中）或向上遍歷（在 follow_dotdot_rcu() 中）時也會檢查它。如果發現它已更改，則整個 RCU-walk 序列將被中止，並由 REF-walk 再次處理路徑。

如果 RCU-walk 發現 mount_lock 沒有改變，那麼它可以確定，如果 REF-walk 對每個 vfsmount 都取得了計數引用，結果也會相同。這確保了不變式成立，至少對於 vfsmount 結構而言。

dentry->d_seq 和 nd->seq

RCU-walk 不在 d_reflock 上獲取計數或鎖，而是取樣每個 dentry 的 d_seq seqlock，並將序列號儲存在 nameidata 結構的 seq 欄位中，因此 nd->seq 應該始終是 nd->dentry 的當前序列號。在複製之後、使用 dentry 的名稱、父級或 inode 之前，需要重新驗證此數字。

名稱的處理我們已經看過，而父項只在 follow_dotdot_rcu() 中訪問，該函式相當簡單地遵循所需的模式，儘管它處理了三種不同的情況。

當不在掛載點時，會遵循 d_parent 並收集其 d_seq。當我們在掛載點時，我們會改為遵循 mnt->mnt_mountpoint 連結以獲取新的 dentry 並收集其 d_seq。然後，在最終找到要遵循的 d_parent 後，我們必須檢查是否已到達掛載點，如果到達，則必須找到該掛載點並遵循 mnt->mnt_root 連結。這可能意味著一種有些不尋常但肯定可能發生的情況，即路徑查詢的起點位於檔案系統的某個已掛載部分，因此從根目錄不可見。

儲存在 ->d_inode 中的 inode 指標更有趣一些。inode 總是需要至少訪問兩次，一次是確定它是否為 NULL，另一次是驗證訪問許可權。符號連結處理也需要一個經過驗證的 inode 指標。與其在每次訪問時都重新驗證，不如在第一次訪問時複製一份，並將其儲存在 nameidata 的 inode 欄位中，從那裡可以安全訪問而無需進一步驗證。

lookup_fast() 是 RCU 模式下唯一使用的查詢例程，因為 lookup_slow() 太慢且需要鎖。正是在 lookup_fast() 中，我們發現了對當前 dentry 重要的“手遞手”跟蹤。

當前的 dentry 和當前的 seq 數字被傳遞給 __d_lookup_rcu()，該函式在成功時返回一個新的 dentry 和一個新的 seq 數字。lookup_fast() 隨後複製 inode 指標並重新驗證新的 seq 數字。然後它最後一次使用舊的 seq 數字驗證舊的 dentry，然後才繼續。獲取新 dentry 的 seq 數字然後檢查舊 dentry 的 seq 數字的這個過程，與我們在 REF-walk 中看到的在釋放舊 dentry 的計數引用之前獲取新 dentry 的計數引用這一過程完全相同。

無 inode->i_rwsem 甚至無 rename_lock

訊號量是一種相當重量級的鎖，只有在允許休眠時才能獲取。由於 rcu_read_lock() 禁止休眠，因此 inode->i_rwsem 在 RCU-walk 中不起作用。如果其他執行緒獲取 i_rwsem 並以 RCU-walk 需要注意的方式修改目錄，結果將是 RCU-walk 未能找到它正在尋找的 dentry，或者它會找到一個 read_seqretry() 無法驗證的 dentry。在這兩種情況下，它都會降級到 REF-walk 模式，該模式可以獲取所需的任何鎖。

儘管 rename_lock 可以被 RCU-walk 使用，因為它不需要任何休眠，但 RCU-walk 不會費心使用它。REF-walk 使用 rename_lock 來防止在搜尋 dcache 中的雜湊鏈時發生變化。這可能導致未能找到實際存在的內容。當 RCU-walk 未能在 dentry 快取中找到某些內容時，無論它是否真的存在，它都會降級到 REF-walk 模式，並使用適當的鎖重新嘗試。這巧妙地處理了所有情況，因此新增額外的 rename_lock 檢查不會帶來顯著價值。

unlazy walk() 和 complete_walk()

“降級到 REF-walk”通常涉及呼叫 unlazy_walk()，之所以這樣命名是因為“RCU-walk”有時也被稱為“lazy walk”。當沿著路徑到達當前的 vfsmount/dentry 對似乎已成功進行，但下一步出現問題時，會呼叫 unlazy_walk()。這可能發生在以下情況：dcache 中找不到下一個名稱；在持有 rcu_read_lock()（禁止休眠）時無法完成許可權檢查或名稱重新驗證；發現自動掛載點；或者涉及符號連結的幾種情況。它也會在查詢到達最終元件或路徑的末尾時（取決於使用的特定查詢方式）從 complete_walk() 呼叫。

不觸發呼叫 unlazy_walk() 而退出 RCU-walk 的其他原因包括髮現無法立即處理的不一致性，例如 mount_lock 或其中一個 d_seq 序列鎖報告更改。在這些情況下，相關函式將返回 -ECHILD，這將向上滲透直到觸發從頂部使用 REF-walk 的新嘗試。

對於那些 unlazy_walk() 是一個選項的情況，它本質上是對其持有的每個指標（vfsmount、dentry 以及可能的某些符號連結）進行引用，然後驗證相關序列鎖是否未被更改。如果發生了更改，它也會以 -ECHILD 中止，否則到 REF-walk 的轉換成功，查詢過程繼續。

對這些指標進行引用並不像簡單地遞增計數器那麼簡單。如果你已經有了一個引用（通常透過另一個物件間接獲得），它可以用作第二個引用，但如果你根本沒有計數引用，它就不夠了。對於 dentry->d_lockref，除非它被明確標記為“dead”（這涉及到將計數器設定為 -128），否則遞增引用計數器以獲取引用是安全的。lockref_get_not_dead() 實現了這一點。

對於 mnt->mnt_count，只要隨後使用 mount_lock 來驗證引用，獲取引用就是安全的。如果該驗證失敗，則可能不安全以呼叫 mnt_put() 的標準方式直接刪除該引用——解除安裝可能已經進展得太遠。因此，legitimize_mnt() 中的程式碼，當它發現所獲得的引用可能不安全時，會檢查 MNT_SYNC_UMOUNT 標誌以確定簡單的 mnt_put() 是否正確，或者它是否應該只是遞減計數並假裝這一切從未發生過。

檔案系統中的注意事項

RCU-walk 幾乎完全依賴於快取資訊，並且通常根本不會呼叫檔案系統。然而，除了前面提到的元件名稱比較之外，檔案系統可能被包含在 RCU-walk 中的兩個地方，並且它必須知道要小心。

如果檔案系統具有非標準的許可權檢查要求——例如可能需要與伺服器檢查的網路檔案系統——則 i_op->permission 介面可能會在 RCU-walk 期間被呼叫。在這種情況下，會傳遞一個額外的“MAY_NOT_BLOCK”標誌，以便它知道不能休眠，而是如果不能及時完成則返回 -ECHILD。i_op->permission 獲得了 inode 指標，而不是 dentry，因此它不需要擔心進一步的一致性檢查。但是，如果它訪問任何其他檔案系統資料結構，它必須確保它們在僅持有 rcu_read_lock() 的情況下可以安全訪問。這通常意味著它們必須使用 kfree_rcu() 或類似方式釋放。

如果檔案系統可能需要重新驗證 dcache 條目，那麼 d_op->d_revalidate 也可能在 RCU-walk 中被呼叫。這個介面確實傳遞了 dentry，但無法訪問 inode 或來自 nameidata 的 seq 號，因此在訪問 dentry 中的欄位時需要格外小心。這種“格外小心”通常涉及使用 READ_ONCE() 來訪問欄位，並在使用之前驗證結果是否非 NULL。這種模式可以在 nfs_lookup_revalidate() 中看到。

一對模式

在 REF-walk 和 RCU-walk 的細節中，以及在整體上，有幾個相關的模式值得注意。

第一個是“快速嘗試並檢查，如果失敗則慢速嘗試”。我們可以在高層方法中看到這一點，即首先嚐試 RCU-walk，然後嘗試 REF-walk，以及在 unlazy_walk() 用於將剩餘路徑切換到 REF-walk 的地方。我們之前在 dget_parent() 遵循“..”連結時也看到了這一點。它嘗試一種快速方式獲取引用，然後在需要時回退到獲取鎖。

第二種模式是“快速嘗試並檢查，如果失敗則重複嘗試”。這在 REF-walk 中使用 rename_lock 和 mount_lock 時可見。RCU-walk 不使用這種模式——如果出現任何問題，中止並嘗試更穩健的方法要安全得多。

這裡的重點是“快速嘗試並檢查”。它可能應該是“快速且仔細地嘗試，然後檢查”。需要檢查這一事實提醒我們系統是動態的，只有有限數量的東西是完全安全的。整個過程中最常見的錯誤原因是假設某物是安全的，而實際上它並非如此。有時有必要仔細考慮究竟是什麼保證了每次訪問的安全性。