pellepl
GC not making much progress
I'm trying to track down a problem where the application writes 800 byte files to the filesystem until there is 20k free and then it deletes one file before creating the next. This is with a 300kB filesystem, 256 byte page, 8192 block.
After a while SPIFFS fails with -10001 (FS Full). The GC just isn't making progress for reasons that I don't understand. It selects a block to clean which has 6 deleted pages in it, but after cleaning, the new block only has 1 free page. The GC was trying to get 4 pages:
gc_check #0: run gc free_blocks:2 pfree:1 pallo:1413 pdele:74 [1488] len:1054 of 251
gc_check #1: run gc free_blocks:2 pfree:0 pallo:1413 pdele:75 [1488] len:1054 of 0
gc_check #2: run gc free_blocks:2 pfree:1 pallo:1413 pdele:74 [1488] len:1054 of 251
gc_check #3: run gc free_blocks:2 pfree:1 pallo:1413 pdele:74 [1488] len:1054 of 251
gc_check #4: run gc free_blocks:2 pfree:2 pallo:1413 pdele:73 [1488] len:1054 of 502
gc_check: finished, 1487 dirty, blocks 2 free, 1 pages free, 5 tries, res -10001
Thinking about it some more, I suspect that things are working "correctly". The trouble is that once some level of fragmentation sets in, it is very difficult to recover. In this case, the blocks have (say) 6 free pages out of 31. Unfortunately, when this block is GC'ed, the free pages are filled up with index pages. No progress has been made. It isn't clear what the right solution is.... It might be better to choose a block that will actually result in the most free pages. Maybe also adjust the amount of space in use to reflect the unrecoverable space....
Hi Philip,
sorry for not looking in to this earlier.
Yes, it is as you say - if you evacuate a data page, its index page must be updated. If the index page is not within the gc'ed block, the gain-. of the moved data page will be nothing.
I'll look into if I can add this situation when setting gc score to block candidates. Otherwise, as a quick fix, you might just bump up SPIFFS_GC_MAX_RUNS.
Always selecting the block which will yield most free pages is not optimal either. Suppose we have a large file which never changes. This file occupies one or more full blocks. If only picking high-yielding blocks, blocks covered by such a file will never be erased. This leads to that all other blocks will wear more.
I'll have a peek and see if can I come up with something intelligent in this case.
Thanks for reporting!
Cheers / Peter
2016-08-17 5:20 GMT+02:00 Philip Gladstone [email protected]:
Thinking about it some more, I suspect that things are working "correctly". The trouble is that once some level of fragmentation sets in, it is very difficult to recover. In this case, the blocks have (say) 6 free pages out of 31. Unfortunately, when this block is GC'ed, the free pages are filled up with index pages. No progress has been made. It isn't clear what the right solution is.... It might be better to choose a block that will actually result in the most free pages. Maybe also adjust the amount of space in use to reflect the unrecoverable space....
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/pellepl/spiffs/issues/99#issuecomment-240303356, or mute the thread https://github.com/notifications/unsubscribe-auth/AE3NV5mzO6AWtGoGMs57jLF4ysJDiczBks5qgn4VgaJpZM4JkaFE .
I think that what I really want is to be able to find out the amount of remaining space on the file system -- such that if this space is greater than X, then it is possible to create a file of size Y. I might use this to maintain a rolling directory of log files. I accept that, as the file system gets fragmented, there is more overhead.
I have a branch with a new test: https://github.com/pjsg/spiffs/tree/test-frag
make test FILTER=small_free_space
runs this test (it currently fails due to not being able to write file data).
Hi Philip,
Thanks, I'll check it out. Been thinking about having a more accurate SPIFFS_info - it is cumbersome. Theoretically, if you let the gc run infinite number of times, it should be able to free said number of pages, given there equally or more number of pages deleted. I cannot prove this logically/mathematically in any way - it is more of a hunch, so I might very well be wrong.
The problem is that the actual amount of free space a gc can free is dependent on the current filesystem state and the gc configs. It is hard to know beforehand what block the gc will pick, especially after a number of runs. I cannot come up with a way to get this number less than actually running the gc and see what the result was.
However, there is one old idea that would solve this. Now, spiffs orders the blocks physically. For example, page indices 0x0000-0x00ff maps to block 0, pages 0x0100-0x1ff to block 1, and so forth. If we would have a logical ordering instead, maintained in some (extra) ram by spiffs, we could move the contents of the physical block 1 to physical block 3, and map the physical block 3 to logical block 1.
Thus, when gc'ing a block, we would not have to rewrite the index pages pointing to block 1. And by that, the gc would take less time, and the SPIFFS_info would be more accurate.
I personally think this is a very good idea, and would love to do it. Though, it is a massive effort, and the file system structure would need to change (as we need to store the logical block indices in the physical blocks). Backward compatibility would be lost, and the mount function would be altered as spiffs would need more ram. This would definitely be a 0.4.0 bump.
Would this be of interest? I know NodeMCU recently bumped up the spiffs version forcing users to reflash their filesystems. As mentioned, there would be a reintegration effort also. Perhaps it would more pain then the benefits.
As they say, adding an extra level of indirection solves many computer science problems!
If you add a logical to physical block mapping, presumably you need to store the logical block number somewhere near the end of the last LU page in each physical block. Then you can build the current mapping table....
I actually feel that there are situations where the GC can make no progess. Consider a filesystem with 8 files, 8 used blocks, with each file having at least one page in each block. Once you get down to 7 deleted pages in each block with one index page in each block, whenever you run the GC, you will copy 8 index pages into the new block -- filling it up. The move of the index pages will make each of the other pages have 8 deleted pages. However, cleaning one of those will just use up the deleted pages and fill them with index pages.
As far as NodeMCU is concerned changing the format is not (AFAIK) a big deal. I suspect that most people do not rely on the FS surviving a firmware upgrade.... I also cleaned up the integration into NodeMCU so that there is a script that updates the spiffs version to the current 'master' (always assuming that the API didn't change). There is a little bit of manual work to adjust the _config.h to get any new defines.
If you add a logical to physical block mapping, presumably you need to store the logical block number somewhere near the end of the last LU page in each physical block. Then you can build the current mapping table....
Exactly. In order to ensure room for the block index, I plan to also redesign the LU page layout. My thought is to have a packed bit structure instead of just dumping the spiffs_object_id type as an array. Will be a bit more cpu overhead though.
I actually feel that there are situations where the GC can make no progess. Consider a filesystem...
Hmm, the first gc would make no free space, I agree. But wouldn't subsequent gc:s be more successful? After the first gc both indices and data pages would reside in the same block, so following gc:s should be more effective? If I understood you correctly. Which ever, indirecting the blocks would be an optimization.
The only drawback is that with current structure, spiffs can be optimized when searching for indices (open) as it is ensured that if I find a free page, the rest of the block is free and can be skipped. Should not be too big a hit though.
As far as NodeMCU is concerned changing the format is not (AFAIK) a big deal.
Ok, I guess I'll start rolling up my sleeves then ;)
I am just an user and I am not quite sure what are you talking about, but I would be grateful if you take into account that it is particular case with micro modules, and there is memory with limited write cycles, quite long write time and especially because of embedded application very high risk losing power for example with low battery. Often the main advantage it is extremely low power what mean decrease time of work / write From my point of view there is no problem to delete oldest files to make a little more free space, alternatively I need mechanism of some kind of defragmentation which I could run in time I am sure there is enough power. So I would be grateful, if there is problem, for function which simply could return information if there is space to write particular file to I could decide if I should delete more files or perform defragmentation. The only I need for now it is to the system does not hang. Additionally I am afraid of excessive manipulation of data with RAM - I am not sure if it is safe enough?
Kamil
hi @kwis2,
take into account that it is particular case with micro modules
spiffs is designed for embedded stuff from the start, so no worries. The writes are slow, this is the nature of spi nor flash.
for function which simply could return information if there is space to write particular file to I could decide if I should delete more files or perform defragmentation
Well, the gc is kind of a defragmentation. What you can do is to call SPIFFS_gc with the length of the file you want to create. If this fails, delete files, call SPIFFS_gc again. You might want to add some extra bytes to the file you want to create to be sure. Perhaps multiply the size by 1.25 or something.
I recommend having a peek on the wiki
Also, is SPIFFS_check supposed to find things? E.g. at the end of a test:
fs consistency check output begin
check: LOOKUP DELETE PAGE 0010
fs consistency check output end
If so, then should I be calling SPIFFS_check immediately after mounting a filesystem?
Hmm, to be honest I cannot remember, but my first impression is no. What test is it?
And if so, yes, you should run a check directly after mounting. From the output it seems a lookup pages points to something it is not supposed to, or vice versa.
I have been experimenting with afl (the fuzzer) against spiffs, and it is finding a bunch of interesting issues. I'm going to do a PR with the modified code so that you can explore these issues....
Ah! You do tend to find most peculiar behaviour in the code - I'm looking forward to it :) Seriously, thanks for spending time in finding these things.