lfs_remove periodically takes a long time

[ststltnk]

We experience a very long operation on every n-th lfs_remove call.

littlefs version v2.5.0 (reproducable also on v2.2.0).

Our use-case:

1. Create a logs directory
2. Create 000 directory inside logs
3. Write 100 files with 200-300 bytes in each of them
4. Create 001 directory inside logs
5. Write 100 files with 200-300 bytes in each of them
   <...>

When there are 7-9k files we start deleting them one by one. First five removes take 10ms to complete but the 6th remove takes around 6 seconds.
In this case lfs_dir_relocatingcommit sets dir->count to 0 and this triggers lfs_fs_pred
which reads 3 MB of data from flash.
This repeats every 6th delete.

We tried changing that there are only 50 files in one directory before moving to the next.
In this case, every 16th remove operation triggers lfs_fs_pred.

A snippet of our configuration:

	read_size = 128
	prog-size = 128
	cache-size = 512
	lookahead-size = 1024
	block-cycles = 2048
	block-size = 4096

Flash has 3978 blocks.

Is there a way to tweak when lfs_fs_pred occurs, or reduce the amount of time it takes?

[Xenoamor]

I don't know why this happens but I've found the less files you can have the better. Is there any way to reduce the number of files you have as 7-9k is a huge amount

[geky]

To give a bit more info:

lfs_fs_pred is called when a directory block is empty. LittleFS removes empty directory blocks, but in order to do this it needs to find the directory block's predecessor, which requires a O(n) search through the directory linked-list. Each directory block contains multiple files, which is why this only occurs every ~6 file removes. This should take ~the same amount of time as lfs_mount.

Though it may be possible that you are also hitting the performance spike that is metadata garbage collection (#203). If you have a reproducible test case it may be worth decreasing metadata_max to see if that helps.

Also consider increasing your block_size. Counter-intuitively, larger blocks may mean less traversal during lfs_fs_pread and friends.

Sorry that all I can offer are more-or-less hacks. This is an area of LittleFS that I'm working to improve on.

[tim-nordell-nimbelink]

@ststltnk Also, #557 can help, but it may not be "mainlined" in the future (per the comments in the PR about potential restructuring later breaking it). It could be a stop-gap for you allowing fastish removal of an entire folder of files at a time.