lfs_file_write following lfs_file_sync is really heavy operation

[petri-lipponen-suunto]

I have a code that saves data from streaming sensors for later retrieval. The backend is a 1 Gb NAND flash with blocksize of 128 kB (MT29). I've been experimenting with the regular flushing of the file to make sure that it is up-to-date in case something goes wrong and have bumped into following issue:

When the device has saved a largish amount of data to the flash, the lfs_file_write following lfs_file_sync takes a really long time (seconds). I've attached a log demonstrating the issue that shows the sync when about 40 kB has been written into the file. The sync itself is quite fast, but the lfs_file_write after the sync (lines 15-984) seems to consist of reading of 80 kB and writing 40 kB which obviously is a very heavy operation in 256 byte pieces over SPI.

I'm quite confused about the behaviour and would like to know more: is this my mis-understanding of the littlefs operation or is there a bug? I would not think that the FS needs to copy the whole file when flushing it...

I'm currently using LittleFS v.2.4.0 (from git tag) but noticed this already a version or two ago.

write_and_sync.log

[petri-lipponen-suunto]

I've studied this a bit further and found out that the lfs_file_write following lfs_file_sync seems to copy the last partial block of the file to a new block. Since block size is 128kB it will be really heavy operation. I've attached a log of a simple test case that I did. The test does:

1. Write to a file 10 bytes at the time and time the operation (TIME_DEBUGGER rows on the log).
2. Every 500 bytes call lfs_file_sync

As can be seen in the log the write following lfs_file_sync is small when file size is small or a bit over 131072 bytes, and gets progressively heavier on every sync towads the 128kB limit. At worst the write takes more than 2500 ms!

I'm contemplating calling the sync only when the file size is a bit over multiple of 128 kB (-8 bytes overhead?) but it sounds like a bit of a kludge. If there is any way to improve this in LittleFS, that would be great!

flush_test.txt

[petri-lipponen-suunto]

I also tried setting the metadata_max configuration (created by the #502) to 4 kB, but it did not affect the "write after sync" -performance.

[petri-lipponen-suunto]

Just found this comment in another issue:

#344 (comment)

which explains this issue. I'm +1 for either of the suggested improvements since the current situation is quite difficult with large block size (= NAND chips).

For now I've implemented the lfs_file_sync call when going over to new block but I think that may cause wasting blocks (I haven't confirmed if that is the case).

[simon88]

Hi @petri-lipponen-suunto
I have the same issue. When you say you sync every new block you mean you call sync_file every 128kB?

[geky]

@petri-lipponen-suunto, sorry for not responding, this flew under my radar.

The proposal in #344 (comment) is in the works, but is unfortunately a part of a larger set of changes which will take some time to land.

I have the same issue. When you say you sync every new block you mean you call sync_file every 128kB?

I'm curious if they figured it out, because the correct alignment is unfortunately excruciatingly complicated.

Calling sync after the first 128KiB works, but the next block will contain a pointer and have only 128KiB-4B of data. The math gets real ugly and is explained a bit more in DESIGN.md.

But let me emphasize, the math gets real ugly.

To avoid any wasted blocks, you need to sync when $\mathit{off}$ is zero, where:

$$ n = \left\lfloor \frac{N - \frac{w}{8} \left(\mathrm{popcount}\left(\frac{N}{B-2\frac{w}{8}}-1\right)+2\right)}{B-2\frac{w}{8}} \right\rfloor $$

$$ \mathit{off} = N - \left(B - 2\frac{w}{8}\right)n - \frac{w}{8}\mathrm{popcount}(n) $$

Where $N$ is the current file size, $B$ is the block size, and $w$ is the word size (32 bits).

For @petri-lipponen-suunto, this may have gone unnoticed because this ends up pretty close to just 128KiB. Overflow would result in copying only a couple of extra words in each block, but it does end up with more block erases than are necessary.

[simon88]

@geky nice, I'll try to syncas soon as I got zero offset, keep you in touch 👍

[andyp1per]

@petri-lipponen-suunto, sorry for not responding, this flew under my radar.

The proposal in #344 (comment) is in the works, but is unfortunately a part of a larger set of changes which will take some time to land.

I have the same issue. When you say you sync every new block you mean you call sync_file every 128kB?

I'm curious if they figured it out, because the correct alignment is unfortunately excruciatingly complicated.

Calling sync after the first 128KiB works, but the next block will contain a pointer and have only 128KiB-4B of data. The math gets real ugly and is explained a bit more in DESIGN.md.

But let me emphasize, the math gets real ugly.

To avoid any wasted blocks, you need to sync when o f f is zero, where:

n = ⌊ N − w 8 ( p o p c o u n t ( N B − 2 w 8 − 1 ) + 2 ) B − 2 w 8 ⌋

o f f = N − ( B − 2 w 8 ) n − w 8 p o p c o u n t ( n )

Where N is the current file size, B is the block size, and w is the word size (32 bits).

For @petri-lipponen-suunto, this may have gone unnoticed because this ends up pretty close to just 128KiB. Overflow would result in copying only a couple of extra words in each block, but it does end up with more block erases than are necessary.

@geky I tried this. Something must be wrong because the value of off is never anywhere close to 0. Is w8 32*8 or 32? I tried both, makes no difference.

[andyp1per]

For anyone looking at this the equation is wrong, it should be:

 n = (N − (w/8) (popcount(N/(B − 2(w/8)) − 1 ) + 2))/(B − 2(w/8))
off = N − (B − 2(w/8)) n − (w/8)popcount( n ) 

[andyp1per]

@geky I can't make this work with your maths. The offset is never zero (I think to be expected as there's some kind of accounting at the beginning of the block)? But the equation for filesize in your DESIGN which you would expect to be the maximum filesize for a given number of blocks does not seem to work when you plug it back in the offset. I wrote the following python script:

#!/usr/bin/env python3

import argparse

parser = argparse.ArgumentParser(description='file size calculator for littlefs')
parser.add_argument('--block', type=int, default=None, help='block')
parser.add_argument('--filesize', type=int, default=None, help='filesize')

args = parser.parse_args()

if args.block is None and args.filesize is None:
    print("Must specicy --block or --filesize")
    sys.exit(1)

def bitsoncount(x):
    y = int(x)
    return bin(y).count('1')

def filesize(block):
    return 1024*128*block-4*(2*block - bitsoncount(block))

def offset(N):
    B = 128*1024
    n = (N - 4 * (bitsoncount(N/(B - 2 * 4) -1) + 2))/(B - 2 * 4)
    block = int(n)
    return N - (B - 2*4) * block - 4 * bitsoncount(block)

if args.block is not None:
    print(filesize(args.block))
else:
    print(offset(args.filesize))

which gives:

andy@Eagle:~/github/ardupilot-master$ ./Tools/scripts/littlefs_fs.py --block 1
131068

which seems reasonable, but then I would expect this to yield an offset at the end of the block, but it does not:

andy@Eagle:~/github/ardupilot-master$ ./Tools/scripts/littlefs_fs.py --filesize 131068
131068
andy@Eagle:~/github/ardupilot-master$ ./Tools/scripts/littlefs_fs.py --filesize 131070
131070
andy@Eagle:~/github/ardupilot-master$ ./Tools/scripts/littlefs_fs.py --filesize 131072
4

so something is messed up somewhere

[andyp1per]

Ok, I think I have it figured out. offset is never zero - its always the offset to the next write point in the block so towards the end of the block it grows until it reaches the block size - at the point the next write address is in the next block past the pointer allocations. So really you need to sync at the point that offset goes past the end of the block and into the next one. I'm sure you can calculate this from knowing the actual files size and the actual allocated number of blocks, but its not super-easy since blocks are not necessarily contiguous.

So I think probably the thing to do is when the amount of data exceeds that left in the block (blocksize - current offset), write only that amount of data and then call sync.

[geky]

Ah, you're right. My bad, it's been a while since I've looked at this math.

The above equations for n and off are for mapping file offsets to block + block offset. You're right this is almost never zero because of the CTZ skip-list pointers.

You would want to either subtract ctz(n)+1 from the final offset or use this modified formula:

usage = N − (B − 2(w/8)) n - 2(w/8) − (w/8)popcount(n-1) 

$$ \mathit{usage} = N - \left(B - 2\frac{w}{8}\right)n - 2\frac{w}{8} - \frac{w}{8}\mathrm{popcount}(n-1) $$

Note also that block 0 is a special case.