Function lfs_dir_read read from same memory twice

[dsabala]

Hey,

I suspect this is due to design constraints (low RAM usage), but why does lfs_dir_read read the same blocks / pages twice? I'm trying to speed up my naive ls shell utility (listing files in directory) and I'm tracing calls to the .read callback.

00:00:04.936 lfs_dir_read(0x2000185c, 0x200003c0, 0x200047e4)
00:00:04.936 Read start block 1001 off 4096
00:00:04.936 Read start block 1001 off 2048
00:00:04.937 Read start block 1001 off 0
00:00:04.937 Read start block 1001 off 4096
00:00:04.938 Read start block 1001 off 2048
00:00:04.939 Read start block 1001 off 0
00:00:04.939 lfs_dir_read -> 1

[dsabala]

It looks like there is one way to lower the time of listing files by setting metadata_max = 2 * page size.
Unfortunately I have to use NAND FLASH memory because that's our design. It has 2KB page and 128KB block.

Normal metadata, listing names and size of 20 files (each ~212KB) takes 326ms.
When set metadata_max = 2 * 2KB then listing 200 files (each ~212KB) takes 46ms.

[dsabala]

Here is my naive benchmark, I wonder how much space I am wasting using 2KB metadata? Allocated blocks counter is equal in both tests

Normal metadata:
Content of filesystem: 20 files each ~217 KB (+1 small file 4 B) = 4.15 MB
Block usage: 50 blocks allocated / 1024 blocks available (each block 128 KB)
50 * 128 KB = 6.25 MB
Time of listing 20 files = 326 ms = 16.3 ms / file

4KB metadata:
Content of filesystem: 20 files each ~208 KB (+1 small file 4 B) = 3.97 MB
Block usage: 50 blocks allocated / 1024 blocks available (each block 128 KB)
50 * 128 KB = 6.25 MB
Time of listing 20 files = 13 ms = 0.65 ms / file

[dsabala]

I ran more benchmarks, and this approach scales well for our use case. I tested with 450 files and the performance is acceptable. I don’t fully understand LittleFS yet, but it seems that file size combined with the erase-block size is the biggest effective memory capacity issue. Two erase blocks = 256 KB, my file is 203 KB, so each file spans two blocks, which now feels intuitive. With 450 files occupying 930 blocks, about 77% of the memory is used effectively and 23% is "wasted".

To improve efficiency, I could adjust the data format (JPEG images) to better align with the 128 KB block size, or switch to a more suitable memory type with smaller erase blocks.

Is it possible to fit more than one file in one NAND FLASH sector (erasable sector 128KB, page 2KB) in littlefs, assuming we use the 2KB metadata option?

BTW for anyone interested in details, here is related PR: #502

[geky]

Hi @dsabala,

To give some context, littlefs organizes storage into separate metadata and data blocks, and only works on blocks. It doesn't have a concept of pages, which simplifies bookkeeping, but has some severe performance implications, as you've noticed. (littlefs was originally designed around the geometry of NOR flash, and it shows.) DESIGN.md has more info on littlefs2.

You also may have noticed littlefs3 being mentioned (#1111, wip, unstable), it's an ongoing reimplementation of littlefs that tries to solve these performance issues. I think it does help here (metadata lookup $O(n) \rightarrow O(n\log n)$), but how much is an open question.

Performance

I suspect this is due to design constraints (low RAM usage), but why does lfs_dir_read read the same blocks / pages twice? I'm trying to speed up my naive ls shell utility (listing files in directory) and I'm tracing calls to the .read callback.

@BenBE had a good explanation in #2 (comment), the bottleneck here is that we need to scan the metadata log to find information about each file on each lfs_dir_read call.

Though two clarifications:

1. It doesn't really matter what type of operations you do. Even just syncing files will eventually fill up the metadata log with commits that increase scan time. This unfortunately means littlefs may perform better after format, which can be deceptive.

2. The metadata log is limited to one block, and the directory is a linked-list of logs (B-tree in littlefs3). The theory in littlefs2 was that this puts an upper bound on the $O(b)$ scan cost, but this doesn't really help with NAND's 128KiB blocks.

The good news: littlefs3 reduces this by adopting self-balancing trees (rbyds) based on the Dhara FTL. This drops metadata lookup down to $O(\log b)$, though there is some concern on how this performs on devices with poor read granularity (I think the NAND flash you described supports byte-level reads, but they're less performant). There's still a bottleneck around $O(b)$ "mdir fetch" (finding the entry point in the log), but this should only happen once per mdir in the directory, and is cached in lfs3_dir_t.

The bad news: littlefs3 is still unstable, so you may need to rely on workarounds like metadata_max in the meantime.

I wonder how much space I am wasting using 2KB metadata? Allocated blocks counter is equal in both tests

metadata_max works by telling littlefs to just ignore the rest of the block, so in theory you're wasting 126KiB of storage per metadata block, but due to (1) files sharing metadata blocks, and (2) littlefs rounding up to the nearest block, you may not notice if you only have a few files.

However, littlefs won't be using the full block for logging, so you will be erasing blocks more frequently than is theoretically necessary. So it's still not a great solution (but pragmatically useful).

Disk usage

Two erase blocks = 256 KB, my file is 203 KB, so each file spans two blocks, which now feels intuitive. With 450 files occupying 930 blocks, about 77% of the memory is used effectively and 23% is "wasted".

That is certainly an awkward size to design around when you consider littlefs is organized into blocks!

littlefs3 has some improvements here, notably it now supports arbitrary pieces of files (fragments) being inlined in the shared metadata blocks (mdirs). However metadata has a ~4x overhead, so trying to inline the extra 53KiB would actually be worse than 2 blocks + padding.

I don't think it's possible to avoid this waste with littlefs's design, short of packing everything into an archive format. On the plus side that'd be a great target for compression.

I could adjust the data format (JPEG images) to better align with the 128 KB block size

Just a quick note, in littlefs2, only the first block in a file uses the full 128KiB. After that the math gets a bit complicated. The second block uses 128KiB-4B for example.

In littlefs3 things get simpler and 2*128KiB uses 2 data blocks + 1 mdir.

or switch to a more suitable memory type with smaller erase blocks.

The interesting thing here is that the reason for the awkward block size is it allows for much cheaper storage. I've noticed quite a few users happy with the metadata_max, because even though it wastes a significant amount of storage, you're not necessarily wasting money vs more flexible storage options.

---

It would be interesting to explore a sort of "subblock" ("page"?) concept in the future, with blocks < the physical erase block. But to do that would require intra-block garbage collection, and it's not clear it can be made performant with littlefs's design (we'd need to traverse the entire filesystem to see if any subblocks are still in use, which sounds bad, but we already traverse for block allocation and you could probably gc multiple blocks in one traversal, so maybe it could work?).

Such a feature would also provide (1) static wear-leveling, (2) filesystem shrinking, and surprisingly (3) XIP/fixed block allocation (#692), so it's definitely a high-value + high-effort feature.

Still, I think it will be out-of-scope for littlefs3 due to the time/effort required.

[geky]

Still, I think it will be out-of-scope for littlefs3 due to the time/effort required.

Wait, to be clear, the above subblock idea is in theory entirely possible with both littlefs2 and littlefs3's design (the question is if it's performant), but it's out-of-scope for the planned work before littlefs3 stabilization. The idea can always be explored later.