在 FUSE readdir() 操作中正確實現查找
我正在嘗試實現一個玩具文件系統，並且我正在努力理解如何以
readdir()一種高效、可擴展的方式正確地實現該操作。要了解 FUSE 使用的介面，我主要閱讀pyfuse3的文件，但我認為我的問題不會通過使用任何其他 FUSE 包裝器來解決。我的理解是，當我的實現
readdir()被呼叫時，我應該readdir_reply()使用連續的目錄條目來呼叫，直到該方法返回False. 在這樣做的同時，我希望將每個條目與一個唯一的$$ 1 $$64 位 ID，稱為
next_id. 在下一次呼叫 時readdir()，我將收到其中一個 ID，並且我應該返回從我之前與該 ID 關聯的條目之後開始的目錄條目。 如果目錄在呼叫 之間發生變化（例如添加或刪除條目）readdir()，我可以自由選擇是否要在後續呼叫中包含添加的項目和/或忽略刪除的項目，但所有其他項目必須保留其 ID，以便s 不會被跳過或返回兩次。從語義上講，這一切對我來說似乎都很好。我能想到的最簡單的實現就是將所有目錄條目讀入一個數組
opendir()，然後使用數組中每個條目的索引作為其 ID。為了避免一次讀取所有條目，可以在每次readdir()呼叫中連續建構數組。但是直到釋放文件句柄才能清除數組$$ 2 $$. 現代文件系統可以輕鬆處理包含數千萬文件的目錄。我假設不能容忍這些實現按照每個目錄文件句柄的目錄條目數的順序分配記憶體（例如，1000 萬個文件 × 每個條目 100 字節 = 1 GB）。這些文件系統通常幾乎專門用於核心中的實現，而不是通過 FUSE。
所有這一切讓我得出結論，這些陳述中至少有一個是正確的：
- 我誤解了 FUSE
readdir()操作的要求。- 有一個更有效的解決方案可以滿足我沒有看到的那些要求。
- 核心中的文件系統有更好的 API 可以實現，不需要保留所有這些狀態。
- 文件系統沒有
readdir()正確地實現等價物，但是以應用程序通常不關心的方式實現。- 文件系統在遍歷目錄時只是分配了千兆字節的記憶體，但沒有人被它打擾。
那麼是哪一個呢？
我想了解如何以
readdir()滿足其他文件系統實現通常滿足的所有期望的方式有效地實現 FUSE 操作。$$ 1 $$: 在單個文件句柄中唯一。
$$ 2 $$: 或者當
readdir()被呼叫時start_id設置為0.
為了在存在並發修改和硬連結的情況下提高效率，您需要一個 cookie btree。我不知道在 POSIX 下正確的另一種 off_t 方法。
我猜這個評論提供了大部分答案：https ://github.com/facebookexperimental/eden/blob/5cc682e8ff24ef182be2dbe07e484396539e80f4/eden/fs/inodes/TreeInode.cpp#L1798-L1833
我將在這裡複製它，包括它的參考連結：
在存在對目錄的並發修改的情況下正確實現 readdir 並非易事。該函式將被多次呼叫。給定的 off_t 值在第一次讀取時是 0，或者是對應於最後一個條目的偏移量的值。（或任意條目的偏移值，給定 seekdir 和 telldir）。
POSIX 合規性要求，給定整個目錄流中的一系列 readdir 呼叫，所有未修改的條目都只返回一次。在 readdir 呼叫之間添加或刪除的條目可能會被返回，但並非必須如此。
因此，off_t 作為條目有序列表的索引是不夠的。如果條目未連結，則下一個 readdir 將跳過條目。
一種選擇可能是用條目名稱的雜湊填充 off_t。off_t 有 63 個可用位（減去為初始請求保留的 0 值）。在實踐中，63 位的 SpookyHashV2 可能就足夠了，但可能會創建一個包含衝突的目錄，從而導致重複條目或無限循環。此外，還不清楚如何處理
off在下一個 readdir 之前被刪除的條目。（您如何在流中找到重新啟動的位置？）。今天，Eden 不支持硬連結。因此，在短期內，我們可以將 inode 編號儲存在 off_t 中，並將它們視為索引到按 inode 排序的條目列表中。這在沒有附加索引的情況下具有二次時間複雜度，但它是正確的。
從長遠來看，尤其是當 Eden 的樹形目錄結構儲存在 SQLite 或類似的東西中時，我們應該維護一個 seekdir/readdir cookie 索引並使用該 cookie 來列舉條目。