Why are directories implemented this way ?

[X-Ryl669]

Hi,

I don't get why you have such a troublesome directory implementation.
Why don't you use a flag in metadata to say the file pointed to is a directory ?

That way, the directory will be described inside a file's content and since you already have atomic file content's replacement, you'd have atomic directory's content replacement.
This would also save a lot of memory.

You can also add some bit in each file's descriptor in the directory content to indicate if the corresponding file is valid (actually, you'd set the bit to 0 atomically when the file is deleted or moved).
That way, you can append to the directory content only the changes to the directory without actually allocating/muxing blocks. Provided you set a sentinel to 0xFFFFFFFF (all bits set), you can append to the directory's content block to add new file or modified file description.

When reading directory, you just read the "log" and report only the valid items (that will be unsorted, but that's a really small cost to pay for the gains).

After a directory content block is too much modified (typically, because too many files have changed that the "tail" containing the changelist is now bigger than the initial content) you apply the file content modification algorithm you've already designed to write a "clean" directory log and reclaim the free blocks. Since this is atomic too, you are always safe even in case of powerloss.

Usually, on embedded FS, you don't have thousands of files so this should work well.
That way, you'd have atomic move, small footprint, and good boot performance.

[geky]

Hi @X-Ryl669, these are good thoughts. Heres some quick notes:

One important note is that the file structure in littlefs doesn't actually provide atomicity by itself. Files are copy-on-write (COW), which means new revisions can use parts of the older revisions, but the actual atomic update is pushed upwards.

Usually COW filesystems (btrfs for example) push atomic updates all the way up to the root of the filesystem, where they use a little log to atomically update the entire filesystem. However, this presents a challenge for wear-leveling, since those updates all get focused into a single block.

For littlefs, we basically put that log at the metadata level. Counterintuitively, one log vs many logs takes up the same code size. It does cost more storage memory (2x for metadata), however storage is cheap and metadata is small.

Combining the metadata + directory structure lets us minimize the wasted space for logging by combining the metadata from multiple files.

I'll have to think more about what it'd look like if the dir logs were also stored in files, it's an interesting idea.

---

There's also a bunch of changes going on right now around the directory pairs planned for the 2.0 update: #85. Most notably, the directory pairs become true logs.

Though a lot of complexity comes from the fact that littlefs is trying to support more than just flash. This means a couple of things:

1. We may not be able to clear bits atomically. NAND would need to fetch and rewrite a page of flash. SD/eMMC would need to fetch, erase, and then rewrite the flash, which is definitely not atomic. And several forms of internal flash just don't support masking bits after programming them once.
2. Not all storage supports writes < block size. For SD/eMMC block size == prog size. This means atomic updates relying only on incremental logs would break down and devolve into a full COW system such as btrfs.

[X-Ryl669]

It makes sense when supporting non word-modifiable storage (or at least when the driver don't support it).

To come back to the directory as file idea:

1. Suppose you have a word A in the metadata that say if the pointed item is a file or a directory.

2. Then to create a directory, you allocate a file (like any other file) with an header storing the word A and a revision

3. To modify a directory, you allocate a new file/dir and store the word A and the updated revision in it (no need to change the old directory, so any directory operation is thus atomic). File link, size, attribute, etc... should be stored here. A special file state should be stored here too, with (at least) 3 possible value (file, directory, movelink)

4. To search in a directory, you'll have to resolve which directory is the lastest (as you have to do for new file) using the metadata pair (I think it's were old directory reclamation could happen, since when the older directory can no longer be logically selected, it's safe to reclaim)

5. To move a file from one directory to another directory (the only operation that can't be atomic by itself) is also possible via this trick:

   a. You first change the source directory to a new version with the file marked as a movelink (also storing the destination of the move).
   b. You change the destination directory with the file in its new place
   c. You finally change back the source directory actually removing the file.

With this scheme, any powerloss would not corrupt the filesystem. If the move is interrupted before a, the file is still at its old position. If it's interrupted before b, you can finish the operation next time to read this directory transparently. If it's interrupted before c, if you access the destination directory you'll see the file in there (so it appear as if the operation succeeded). If you access the source directory, you'll see the "movelink" and when checking the destination directory since the file is present in, you can safely remove the movelink.

One point here is that the "movelink" should also store the destination directory's revision, so if some other process increased the destination directory's revision, then it's safe to remove the movelink.