Calculating worst case time littleFS will take to save all files in case of shutdown

[i-g-g-y]

Hello people.

I was wondering if there is a way to calculate the worst case time that littleFS needs to save all data before shutdown?

Given the config of filesystem, the hw used and its configuration, the known usage profile, is there a way to calculate reliably the worst case needed to save al data?

So far I have been measuring the sync times (I do a batch sync for all files periodically) and for 16 files I get lots of times in a few miliseconds, than one big jump around 350ms and if the system runs for long I catch up to two spikes in one sync batch.

This is statistics on a per-file basis:

This is how the "batch sync" typically looks like:

SYNC file 0, duration: 4
SYNC file 1, duration: 4
SYNC file 2, duration: 4
SYNC file 3, duration: 4
SYNC file 4, duration: 4
SYNC file 5, duration: 3
SYNC file 6, duration: 352
SYNC file 7, duration: 2
SYNC file 8, duration: 4
SYNC file 9, duration: 4
SYNC file 10, duration: 4
SYNC file 11, duration: 3
SYNC file 12, duration: 4
SYNC file 13, duration: 4
SYNC file 14, duration: 4
SYNC file 15, duration: 4
SYNC LOG file: 0

But sometimes:

SYNC file 0: 0, duration: 352
SYNC file 1: 0, duration: 4
SYNC file 2: 0, duration: 4
SYNC file 3: 0, duration: 4
SYNC file 4: 0, duration: 4
SYNC file 5: 0, duration: 4
SYNC file 6: 0, duration: 4
SYNC file 7: 0, duration: 4
SYNC file 8: 0, duration: 3
SYNC file 9: 0, duration: 4
SYNC file 10: 0, duration: 4
SYNC file 11: 0, duration: 3
SYNC file 12: 0, duration: 4
SYNC file 13: 0, duration: 3
SYNC file 14: 0, duration: 352
SYNC file 15: 0, duration: 4

Statistics for the 16-file batch-sync:

I do have a hard limit to save all data and I worry how long can it actually take in case of worst case.

[i-g-g-y]

Another thing I would be interested about is, if there is a specific parameter/config that can influence this save time?

[geky]

Hi @i-g-g-y, thanks for creating an issue, this is an interesting question.

Unfortunately, worst-case sync time is very difficult to predict in littlefs's design. littlefs relies on a lot of amortized work, due to moving everything onto disk (vs RAM).

The two main concerns:

1. Mdir compaction - $O(b^2)$ - periodically, littlefs needs to "compact" metadata logs. This is currently $O(b^2)$, where $b$ is the block size, and may be needed for every mdir up to the mroot.
2. Lookahead scans - $O(f)$ - when allocating blocks (during mdir relocation or data flush), littlefs needs to periodically scan the filesystem $f$ to figure out what blocks are free.

So if you know the number of blocks in the filesystems $f$, you could in theory calculate a worst-case sync time of $O(f\cdot(f+b^2))$. But this would be an extremely pessimistic estimate.

---

The good news, both of these can be offloaded via lfs_fs_gc. If you have idle cycles, calling lfs_fs_gc can move both of these spikes of the critical path.

Two other things to consider:

1. metadata_max can be used to artificial limit the mdir size and control the mdir compaction spike, at the cost of wasting some amount of metadata storage.

2. littlefs3 (#1111, unstable) is currently in the works to address some of these performance issues. Notably it brings mdir compaction down from $O(b^2)$ to $O(b \log b)$.

[i-g-g-y]

Hello.

Thanks for feedback.
For completeness, let me state I work on a 8meg qspi nor memory. The times you are seeing are for this memory.

With the equations provided, I understand the trend, but do not really know how to tie them to milliseconds. I think I can get all the data needed for calculation, but I have no idea how deep the internal processes in littleFS (compaction?) can go.

I have all my files in root and I don't know why sometimes there is a single 350ms event and why sometimes there are two 350ms events? Can there be three, is there a limit to the internal process per iteration or does it work until completely done?

With the proposal to try and shorten the spikes, I would need a way to calculate the worst case to know the final capability of the system and then compare this to the space trade-off.

Calling lfs_fs_gc might be a solution, but is it deterministic? What happens if I call it and then right after the call I get a shutdown, how long does it take to complete and how much time will I need to save all the data?

Is there a flowchart I could follow to calculate the longest time path?

[geky]

I have all my files in root and I don't know why sometimes there is a single 350ms event and why sometimes there are two 350ms events? Can there be three, is there a limit to the internal process per iteration or does it work until completely done?

Ah, so two possibilities:

1. If file metadata spans multiple blocks, littlefs stores it in a linked-list of mdirs (btree in littlefs3). Each mdir is a log that needs to be compacted when full, and these compactions can chain if you're unlucky.

   Predicting how many mdirs there will be in a system is already tricky. In practice littlefs splits mdirs when they would exceed 1/2 a block when full. This adapts to whatever block size you have, but to find the worst-case size probably requires a full understanding of the low-level metadata on-disk (SPEC.md ?)

2. Even if you only have one mdir, littlefs will insert mdirs into the "superblock chain" to avoid wearing out the root blocks. This is described in more detail here: Top root block(s) wear leveling #1020 (comment)

   The superblock chain is interesting in that it's in theory unbounded, but in practice likely to be small. If you know how much data you're writing between syncs $w$, sync size $m$, disk size $d$, block size $b$, block_cycles $r$, and flash's erase cycles $e$ (in datasheet), you can use this formula:

   n = 1 + \log_{rb/2m}{\frac{ed}{\max(w,b)}}
   

   Where $n$ would be the length of the mroot chain when all of storage should be exhausted.

   For something like 4KiB writes, 16 byte syncs, 8MiB disk, 4KiB blocks, $r$=100 , $e$=100000, this would give you.... ~3 mdirs.

   But this gets hard to predict because there's so many variables involved. Not to mention flash doesn't just stop working at exactly 100000 erase cycles.

You could turn both of these off by disabling wear-leveling (block_cycles=-1), but that would also disable wear-leveling.

EDIT: The above math didn't render because GitHub is stupid (github#17325). Here's the formula again:

$$n = 1 + \log_{rb/2m}{\frac{ed}{\max(w,b)}}$$

---

Calling lfs_fs_gc might be a solution, but is it deterministic? What happens if I call it and then right after the call I get a shutdown, how long does it take to complete and how much time will I need to save all the data?

Ah, that is a good point. Worst case lfs_fs_gc will be stuck doing all of the above work.

littlefs3 has an option for incremental gc, which would be a bit more graceful (allowing you to abort during powerloss), but that's stuck in littlefs3 jail at the moment.

Is there a flowchart I could follow to calculate the longest time path?

Unfortunately not really. You may be able to tell from the random links the documentation is not very mature at the moment. And despite its name, littlefs is still a complex system under the hood.

[i-g-g-y]

Hello,

Thanks for the insight, very interesting.

I am having issues reproducing the results, can you explain syncs and sync_size, not sure I am doing it right:

Would constantly running lfs_fs_gc decrease the burden in case of power failure?

What would you do to get the speediest way to save all data in case of power fail?

[geky]

Ah, I think you want 1 + (LN((B9*B6)/MAX(B5,B7)) / LN((B8*B7)/(2*B4)))

I think you have $w$ and $m$ switched:

• $w$ - write (between syncs) - 4096 bytes or whatever the amount you write is
• $m$ - size of metadata written during sync: ~4 words = ~16 bytes (ctz head + ctz len + commit tag + crc)

The base of the logarithm should be very large (multiple digits), which is what makes the algorithm work.

Would constantly running lfs_fs_gc decrease the burden in case of power failure?

What lfs_fs_gc does is it guarantees that after lfs3_fs_gc any write work is as cheap as possible. So yes, I think. But littlefs is single-threaded, so running lfs_fs_gc risks locking up the filesystem if you want to write some last minute data during a powerloss event. It's not the greatest of APIs for this purpose.

littlefs3 improves this and would allow aborting lfs_fs_gc during powerloss, but again littlefs3 jail.

What would you do to get the speediest way to save all data in case of power fail?

I don't know of anything else that would speed up file sync. This is unfortunately something that's not well explored. Mostly users have been interesting in worst case latency if there are idle cycles available to comfortably run lfs_fs_gc.

[i-g-g-y]

Hello Geky.

Let me first express my gratitude for the support you are giving on this topic, it is much appreciated.

I followed your advice, and now I am getting better numbers in excel. For a 4-byte write every second, I get a grand total of 2400-bytes between syncs (sync every 10 minutes). The length of mroot chain evaluates to ~3, but what does this mean in terms of a worst case time penalty?

I do have a fairly capable mcu, so I could run lfs_fs_gc, what might be potentially missing is to know when it needs to be run? I can call it every loop, as long as it will not cause excessive wear in my application, the target lifetime for the entire flash is 20 years and I never log faster than every 10 minutes (slow processes). Currently I am increasing pressure on the file system by writing much faster, but this is to accelerate tests.

Running lfs_fs_gc on a regular basis, would then be a "best effort strategy", to be able to save as much as possible in the case of a
power fail event. I will test now with a reduced metadata_max as an attempt to reduce the save times in case of a power failure. Any advice for a good trade-off value? I am targeting ~32 files and have around 400ms time to save them all. Not sure this is even possible.

Edit: had to properly correct equation, new image showing result.