What is the maximum stack depth of LFS?

[Johnxjj]

I see a recursive function in the file system.

[e107steved]

From readme.md (the front page):

The filesystem contains no unbounded recursion and dynamic memory is limited to configurable buffers that can be provided statically.

Other than that, it's going to be rather processor-dependent. And there are the hardware-level access routines to allow for.

[blomnik]

Memory consuption depends on which API function you use. In my project on AVR8 avarage stack depth is about 500 bytes. But it is really important for me to know calculated (is it possible?) amount of memory required. May be author knows something?

[e107steved]

Stack usage is going to depend not only on the chosen processor, but on the compiler used and the compile options chosen; so I don't see any alternative to measuring it.
The usual technique is to fill the stack area with a known value, exercise your program, and see how much of the stack area has been overwritten.
Possibly @geky can indicate which code paths are likely to use the most stack, when he gets a chance

[zacwbond]

I would also like to know about the worst-case call chain along with a process by which it could be triggered.

We've seen filesystem corruption errors occasionally in the field, and I suspect it's due to some unusual lfs code path blowing out the stack. After rebooting, the filesystem (usually a single file) is in a corrupt state and can't be used without either deleting the corrupt file or, in some cases, reformatting the filesystem.

[blomnik]

@zacwbond, hello!
I had a similar problem in my project (avr-gcc 5.4.0 + avr-libc 2.0.0 + Atmega2560) and, you are right, it is a stack overflow problem. I noticed, that most intensive stack usage is on block relocation while writing. At least, I had no other "heavy" cases. Hope it helps you.

[geky]

Ah, sorry for the late response. Unfortunately littlefs's stack usage is an area that needs quite a bit of work. There are quite a few corner cases that can lead to different stack uses, and other than best practices such as no on-stack arrays, I don't have more in-depth info.

The relocation logic is definitely the path to be the most concerned about, as it is written recursively. It should be tail-recursive, but whether or not that gets optimized away is at the whim of the compiler. (It only recurses if bad blocks are detected while relocating another bad block, this is rare but I realize it is still an important concern for small stacks).

What should be done is this piece of logic should be rewritten as a proper loop.

After that it may be interesting to explore more the stack usage in-depth. It will just be a bit tricky given all the routes littlefs can take.

[geky]

I put up a PR that should remove all recursion in littlefs, there turned out to be more places with recursion than I thought, though these were bounded by runtime behavior: #658

The current maximum depth measured by GCC's -fstack-usage flag for Arm Thumb is 1264 B. Though as @blomnik notes this varies significantly across compiler/architecture and which function you call. Even more so because AVR is an 8-bit/16-bit processor vs Thumb's 32-bits. Arm Aarch64 (64-bit) is 2064 B for example. I don't have an AVR compiler handy but I'd be interested to know if someone measures it.

Also worth noting I haven't spent any time optimization the stack usage. There may be some low-hanging fruit to reduce this further but I haven't looked.