Lookahead bug?

[davidefer]

Hi
I'm working with an SPI flash with 126 usable/erasable blocks of 65536 bytes each, The page write size is 256. littlefs is V1.3.
I'm experiencing a problem while writing big files.

When I format the storage, I get the following:
Total space 8257536
Used space 262144
Free space 7995392
Where Used space = number of blocks(126) * blocks size(64KB) - free space (calculated as suggested here #45)

Now I write 4 files, 1MB each, in the sequence: file3, file2, file1, file0 (opened with LFS_O_WRONLY | LFS_O_CREAT | LFS_O_TRUNC)

I get the following after writing:
Total space 8257536
Used space 4718592
Free space 3538944

So far so good.

Now I write 5 files, again 1MB each, in the sequence: file4,file3,file2,file1,file0 ( file4 at the beginning and then the same as before).

Now I get the following LFS_WARN while writing file1:
// check if we have looked at all blocks since last ack
if (lfs->free.off == lfs->free.ack - lfs->free.begin) {
LFS_WARN("No more free space %d", lfs->free.off + lfs->free.begin);
return LFS_ERR_NOSPC;
}
lfs warn:299: No more free space 251

The call stack is the following:
lfs_alloc line 299
lfs_ctz_extend line 1149
lfs_file_write line 1655

lfs->free.begin = 192
lfs->free.size=59
lfs->free.off=59
lfs->free.ack=251

If I force the file1 to be closed, then I get the following:
Total space 8257536
Used space 5832704
Free space 2424832

Please note that the files are re-written without being deleted, but since I open them again with the truncate flag, I would expect that their space is immediately freed for writing.

I've seen that, when I reformat, the issue happens always after writing the block 125 (the last one). If I perform a different sequence, the block is different.

Could you please help? Thank you

[davidefer]

I've also implemented a windows simulation of the flash and the result is the same, so it is not flash dependent.

[davidefer]

I have simplified the test case to the following:
Here is my configuration:
read_size 256
prog_size 256
block_size 65536
block_count 128
lookahead 128

1)format
2)write 6 files, 1MB each.
After the first run, the situation is the following:
Total space 8388608
Used space 6946816
Free space 1441792

3)Write again the 6 files (each file can be opened with the truncate flag or deleted in advance), the error occurs while writing the 4th file.
After this, the situation is the following:
Total space 8388608
Used space 5832704
Free space 2555904

My suspect is that the lookahead mechanism has a bug. When a file is deleted of truncated, the lookahead information is not correctly updated and the available space is wrongly evaluated.

[davidefer]

As suspected, if I reset the lookahead upon truncating or deleting a file, the bug is fixed.
I attach my modified version (see "davidefer"), @geky please check.
P.S. I've also removed some warnings
lfs.zip

[geky]

Hi @davidefer, sorry about the delay! I wasn't able to look at github this past week.

I think the issue might just be that littlefs isn't writing out the file until it's closed, which means it keeps the old version of the file around in case power is lost.

If you add a call to lfs_file_sync (forces writing out the files) do you still get the no space error?

For example:

lfs_file_open(&lfs, &file, "file0", LFS_O_WRONLY | LFS_O_CREAT | LFS_O_TRUNC);
lfs_file_sync(&lfs, &file); // forces writing out the truncate so memory can be reused
lfs_file_write(&lfs, &file, data, 100000);
lfs_file_close(&lfs, &file);

[davidefer]

Hi geky, thanks for the answer (I was a bit worried that here nobody cares anymore ;-)

No your suggestion doesn't work. And as mentioned above, the problem occurs also if I delete the file before opening it and starting to write..

I think that the problem is really the lookahead management. When a file is truncated or deleted, the "freed" blocks are behind the lookahead "window" (or before it if you prefer), so that lfs cannot see them and it thinks the storage is full.
I guess the same problem occurs also when we have blocks' wear and lfs tries to relocate for instance the 2 cwd blocks.
So if a force a traversing of the whole storage by resetting the lookahead, everything works again because free->off points then to a freed block.

I guess an elegant solution would be to move the lookahead "window" back to the beginning of the storage as soon as reaches the end of the storage (wrap-around). The same should happen of course if, like in my case, I have a "window" as big as the storage. The number of wrap-arounds should of course be limited, otherwise we would end-up in an endless loop.

I'll perform some other tests today and I hope I manage to provide some more details, but I would be very happy if you could perform the tests yourself, or at least think about the problem. Thank you in advance.

[davidefer]

Hi @geky
I've implemented some modifications in the lookahead and tried also to simplify it. Please see the attachment.
Basically the lookahead "window" can now go from the start of the storage to the end and then wrap-around. The sequence can be repeated as long as we can erase free blocks. The sequence is interrupted if no free blocks can be erased anymore (worn out).
The mechanism relies on the assumption that the storage reports an error while trying to erase a worn-out block.
Please forgive me if I have misunderstood something, but I think now the management is simpler and should anyway conform to what you have written in your specs. I don't know if the function lfs_alloc_ack is still useful, I think not.
Please let me know your comments about the whole stuff.
lfs.zip

[geky]

Oh that is interesting.

The lookahead window should be handling wrap around. I'll see if I can reproduce and figure out what's going on. Thanks for all of the info!

The current implementation is supposed to wrap around at least once before stopping. The lfs_alloc_ack function is what currently marks the next wraparound point. Though if you're implementation is simpler (and works haha) we should definitely adopt that.

[geky]

Ok! I think I figured out what's going wrong. Sorry it took so long. The lookahead buffer is wrapping around correctly, but the problem is when the lookahead buffer is being populated.

You managed to find an interesting case where the lookahead buffer is populated before the file gets deleted, but littlefs trusts the buffer and assumes the blocks from before the delete are still in use.

Turns out there's a simple workaround in the existing implementation, which is to just push the ack marking to the end of the lookahead window, effectively discrediting the current lookahead region:

 static void lfs_alloc_ack(lfs_t *lfs) {
-    lfs->free.ack = lfs->free.off-1 + lfs->free.begin + lfs->cfg->block_count;
+    lfs->free.ack = lfs->free.size-1 + lfs->free.begin + lfs->cfg->block_count;
 }

I need to put your example into a test case first, but I think this is the best approach for now.

Your solution works as well since it always discredits the lookahead window, but if I understand the approach correctly, that means littlefs would need to fetch the lookahead every erase (which is roughly every allocation). Populating the lookahead buffer is expensive, so we want to get as many allocations out of it as we can.

I should also mention that littlefs does not rely on the block device reporting corrupt blocks, instead littlefs always verifies the data at program time. This is why the lfs_alloc_ack is a separate function called from higher layers.

[geky]

Ah, whoops, actually my workaround is broken. We can't trust any blocks after the offset during an ack because they may become used during a multi-block allocation (dir pair allocation, or when we hit a worn out block).

But what does work is eagerly scanning ahead in our allocator. Since alloc acks are usually tightly coupled to allocations of one or two blocks, this lets us properly rescan every set of allocations.

Does that make sense?

I put together a fix and added tests for both your issue and the case where we trust bad blocks and have a multi-block allocation at the same time over here: 89a7630. Let me know if that works for you.

[davidefer]

Hi @geky thanx for your fix, it works.
Actually my last solution didn't travers all the time but just as often as your solution.

The problem with your implementation is that the free.begin variable is never reset after the mounting. That means that begin and ack grow steadily and at one point in time they will overflow (ok one could argue that it takes very long, but anyway the problem is there and depending on the application it may become painful).
I've tried to initialize the begin variable with a value closed to the overflow and I get an assert almost immediately.
static int lfs_ctz_extend(lfs_t *lfs,
lfs_cache_t *rcache, lfs_cache_t *pcache,
lfs_block_t head, lfs_size_t size,
lfs_block_t *block, lfs_off_t *off) {
while (true) {
// go ahead and grab a block
lfs_block_t nblock;
int err = lfs_alloc(lfs, &nblock);
if (err) {
return err;
}
LFS_ASSERT(nblock >= 2 && nblock <= lfs->cfg->block_count);
nblock is zero.

In my solution the free.* variables are always within the range 0...number of blocks in the storage (and actually ack was useless). The only problem is that I have to limit the number of wrap-arounds with the erase block test.

I think we should find a solution for your problem. What do you think?

[geky]

Oh, that's not good. What value did you initialize the lookahead with? I can't seem to reproduce the overflow failure. Are you able to post the code to set the lookahead up so it fails?

You have a good point there should be a test for the overflow. I tacked one onto the fix-lookahead-doublecheck-trust branch here: 6a89ecb. (But it's currently passing?).

The operations on the pointers into the lookahead windows should all be able to handle overflow correctly.

[geky]

Reading through your implementation again it makes sense now. Thanks for explaining.

There's still the issue that we don't know if a block is bad at erase time. But that's easily fixable by moving your lfs->free.wrapAroundAllowed = 1 into the lfs_alloc_ack function.

The only other downside is you do waste some of the lookahead on the last pass if the block device is say 1.5x the lookahead, but I don't think that's worth worrying about.

Just double checking, are you testing the overflow without changes? Some of the changes such as lfs->free.off < lfs->free.size will cause problems if lfs->free.off is allowed to overflow.

[davidefer]

Hi @geky I'm working with the version 89a7630 (see above)

Here are my settings (some defines set into the cfg struct)
#define LFS_read_size 256 // read cache size
#define LFS_prog_size 256 // flash page size
#define LFS_block_size 65536 // erasable flash block size
#define LFS_block_start (2UL) // the first block used by LFS
#define LFS_block_end (127UL) // the last block used by LFS
#define LFS_block_count (LFS_block_end-LFS_block_start+1UL)
#define LFS_lookahead (32UL*1UL) // free blocks cache, must be a multiple of 32

In lfs_mount I initialize begin as follow:
lfs->free.begin = 0x100000000- (32 * 32);// EFFS_lookahead*32

Size will always be 32 (lookahead) so that begin is a multiple of 32.
The assert happens then while writing the first 1MB file.
When I set LFS_block_start to 0 then everything works (but I cannot use the first 2 blocks!)

[geky]

So it does. Looks like it is an issue with the modulus math when the pointer size is not a multiple of the block device size (2^32 vs 65536-2).

I think you're right that we should just avoid the overflow behaviour at this point. It's caused enough problems. I've modified the lookahead so now it should always keep the begin variable inside the block device. To make this work I also changed how the ack works to just be a counter that counts down every block that is allocated.

Does this work for you? f935fc0

Thoughts?