☰

正确实现 FUSE readdir() 操作中的查找

tag-icon • tag-icon linux filesystems system-calls fuse
正确实现 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。

所有这些让我得出结论，这些陈述至少有一个是正确的：

  1. 我误解了 FUSE 操作的要求readdir()。
  2. 有一个更有效的解决方案可以满足我没有看到的这些要求。
  3. 内核内的文件系统有一个可以实现的更好的 API，这不需要保留所有这些状态。
  4. 文件系统并没有readdir()正确地实现等效的功能，而是以应用程序通常不关心的方式实现。
  5. 文件系统在遍历目录时确实会分配千兆字节的内存，但没人会为此烦恼。

那么是哪一个呢？

我想了解如何以满足readdir()其他文件系统实现通常满足的所有期望的方式有效地实现 FUSE 操作。

[1]：在单个文件句柄内唯一。
[2]：或者也许当readdir()被调用时start_id设置为0。

答案1

为了在并发修改和硬链接的情况下提高效率，您需要一个 cookie btree。我不知道在 POSIX 下还有其他正确的 off_t 方法。

我猜这个评论提供了大部分答案：https://github.com/facebookexperimental/eden/blob/5cc682e8ff24ef182be2dbe07e484396539e80f4/eden/fs/inodes/TreeInode.cpp#L1798-L1833

我将在此处复制它，包括其参考链接：

在对目录进行并发修改的情况下正确实现 readdir 并非易事。该函数将被多次调用。第一次读取时给出的 off_t 值要么是 0，要么是与最后一个条目的偏移量相对应的值。 （或者任意条目的偏移值，给定eekdir和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来枚举条目。

相关内容