lookahead window refresh issue

[gofortime]

Hi @geky ,

I found it is likely to become a performance bottleneck to refresh lookahead window on large space NAND storage. Here is my problem:

1. I use NAND with large space (up to 512MB), and now actually about 300MB dirs/files on it;
2. When refreshing lookahead window, it will read/scan all occupied blocks, which costs much time (the more time if more files on disk, the worst case is to scan almost all blocks which may take 20+ seconds in my case).

I tried to adjust the lookahead buffer size, so as to decrease the frequency of windows refreshing. This helps a lot.

Anyway, it still has chance to do window refresh (and disk scan) from time to time. So I am wondering if it is possible to totally exclude the refresh and disk scan step? Do you think it worth to maintain a full runtime bitmap in memory, and has bitmap dynamically updated when any single block allocated or freed? By doing so, we need just one time disk scan in the initialization flow, but no scan at runtime. One of the side effects is memory consumption, the full bitmap will eat more memory. Another side effect is code modification, it requires to track all ctz and dir blocks when they are freed (such as file delete). It requires ctz list traverse during remove flow I believe.

Any idea?

Thanks,
Wenjun

[guiserle]

Hi @gofortime ,

I am also interested on this feature. On my use case I have littlefs on a system which is storing relatively high amount of data on real time into a nand flash device. Due to real time requirements, every millisecond little fs takes to update lookahead buffer translates into dynamic memory required to store the data captured during the operation.

Therefore for me it is way better to spend 512 bytes of RAM in a big lookahead buffer than hoping for heap not being filled on a non-deterministic operation.

This would also greatly improve performance of lfs_fs_size as a traverse would not be needed anymore (either by counting 0's or 1's on lookahead buffer or by storing the size on RAM as proposed here: #387

I understand this may not be the priority for littlefs project right now so I was thinking on doing the modification on my side, but I don't have a complete vision on when a block may be freed so I would appreciate if someone could give me a hint on what to search.

Thanks

[geky]

I've been wanting to readdress the block allocator for a while (#75 was the first discussion). Now that global state was added in v2, it should be possible to maintain a global free-list completely atomically. However this this involves a significant rearchitecting and promises to create problems with how littlefs caches read/writes, so unfortunately I haven't been able to jump into the problem yet.

I would probably consider this the biggest flaw with littlefs right now.

---

Avoiding scans when the lookahead buffer covers the entire file is a great solution when you have the RAM available. I did not originally implement this special case as the more special cases that exist = more bugs. But considering the performance impact I understand why this special case would be valuable.

Finding all cases where blocks fall out of scope would be the biggest challenge. The most complicated part would be correctly handling CTZ skip-list updates, since these retain references to parts (prefixes specifically, data ahead of the update) of the original file. You would need to compare the original file to the updated file and mark freed blocks as freed.

Also file removes would now require traversing the file, but that is likely not a big problem.

Due to real time requirements, every millisecond little fs takes to update lookahead buffer translates into dynamic memory required to store the data captured during the operation.

Therefore for me it is way better to spend 512 bytes of RAM in a big lookahead buffer than hoping for heap not being filled on a non-deterministic operation.

That's a really interesting perspective and makes sense as a rational. Unfortunately it's the just the number of corner cases to handle properly that is a problem.

One benefit, though maybe more a crutch, of the current implementation is that it avoids a whole category of allocation bugs.

[guiserle]

Thanks @geky for taking into account this problem.

I understand handling this special case will likely introduce too much complexity and potential bugs, so I do not expect this feature to be added soon.

However, as this was a critical issue for my use case I did some modifications on the code that, for the limited use of littlefs I am using on my current project, seems to be working. I have not performed a thorough test and I assume I may have missed block deallocations so I have left current mechanism as a fallback if all blocks are allocated. You can see my modifications here: guiserle@904fa1b

Finally, I found what may be a bug not related to this topic: On lfs_alloc_reset function, lookahead buffer offset is initialized using seed modulo block_size, but I think it should be modulo block_count.

Thanks

[geky]

Oh! Good catch

[geky]

The lookahead offset initialization issue is now tracked here #484, another user with good eyes spotted it independently.