3

I'm trying to implement a toy file system and I'm struggling to understand how to correctly implement the readdir() operation in an efficient, scalable way. To understand the interface used by FUSE, I'm mainly reading the documentation of pyfuse3, but I don't think that my issues would be solved by using any other FUSE wrapper.

What I understand is that when my implementation for readdir() is called, I'm expected to call readdir_reply() with successive directory entries until that method returns False. While doing that, I'm expected to associate each entry with a unique[1] 64-Bit ID, called next_id. On the next call to readdir(), I'll be passed one of those IDs and I'm expected to return directory entries starting after the entry that I've previously associated with that ID.

If the directory changes (e.g. entries are added or removed) between calls to readdir(), I'm allowed to freely choose whether I want to include added items and/or omit removed items in successive calls, but all other items must keep their ID so that s won't be skipped or returned twice.

Semantically, this all seems fine to me. The simplest implementation that I can think of would just read all the directory entries into an array on opendir() and then use each entry's index in the array as its ID. To avoid having to read all entries at once, the array could be build up successively in each readdir() call. But it won't be able to clear the array until the file handle is released[2].

Modern file systems have no trouble handling directories with 10s of millions of files. I'm assuming that these implementations wouldn't be tolerated to allocate memory in the order of the number of directory entries for each directory file handle (e.g. 10 million files × 100 bytes per entry = 1 GB). These file systems generally are almost exclusively used with implementation in the kernel and not via FUSE.

All this leaves me to conclude that at least one of these statements is true:

  1. I'm misunderstanding the requirements of the FUSE readdir() operation.
  2. There is a more efficient solution to meet those requirements that I'm not seeing.
  3. File systems inside the kernel have a better API they can implement, which does not require all this state to be kept.
  4. File systems don't implement the equivalent of readdir() correctly, but in a way that applications generally don't care about.
  5. File systems just do allocate gigabytes of memory when traversing a directory but no-one's bothered by it.

So which one is it?

I would like to understand how to implement the readdir() FUSE operation efficiently in a way that meets all expectations generally met by other file system implementations.

[1]: Unique within a single file handle.
[2]: Or maybe when readdir() is called with start_id set to 0.

1

For efficiency in the presence of concurrent modification and hardlinks, you need a cookie btree on the side. I'm not aware of another off_t approach that's correct under POSIX.

I would guess this comment provides most of the answer: https://github.com/facebookexperimental/eden/blob/5cc682e8ff24ef182be2dbe07e484396539e80f4/eden/fs/inodes/TreeInode.cpp#L1798-L1833

I'll duplicate it here, including its reference links:

Implementing readdir correctly in the presence of concurrent modifications to the directory is nontrivial. This function will be called multiple times. The off_t value given is either 0, on the first read, or the value corresponding to the last entry's offset. (Or an arbitrary entry's offset value, given seekdir and telldir).

POSIX compliance requires that, given a sequence of readdir calls across the entire directory stream, all entries that are not modified are returned exactly once. Entries that are added or removed between readdir calls may be returned, but don't have to be.

Thus, off_t as an index into an ordered list of entries is not sufficient. If an entry is unlinked, the next readdir will skip entries.

One option might be to populate off_t with a hash of the entry name. off_t has 63 usable bits (minus the 0 value which is reserved for the initial request). 63 bits of SpookyHashV2 is probably sufficient in practice, but it would be possible to create a directory containing collisions, causing duplicate entries or an infinite loop. Also it's unclear how to handle the entry at off being removed before the next readdir. (How do you find where to restart in the stream?).

Today, Eden does not support hard links. Therefore, in the short term, we can store inode numbers in off_t and treat them as an index into an inode-sorted list of entries. This has quadratic time complexity without an additional index but is correct.

In the long term, especially when Eden's tree directory structure is stored in SQLite or something similar, we should maintain a seekdir/readdir cookie index and use said cookies to enumerate entries.

1
  • It took me a few days to read though all the articles and linked mail threads, but now I feel that my pain trying to implement this interface is shared by many file system developers. So my gut feeling, that implementing the interface just is really hard and often not done correctly, was right. :) Thanks for the research! – Feuermurmel Mar 11 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.