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 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.
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:
- I'm misunderstanding the requirements of the FUSE
- There is a more efficient solution to meet those requirements that I'm not seeing.
- File systems inside the kernel have a better API they can implement, which does not require all this state to be kept.
- File systems don't implement the equivalent of
readdir()correctly, but in a way that applications generally don't care about.
- 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.
: Unique within a single file handle.
: Or maybe when
readdir() is called with
start_id set to