lfs_mlist_isopen causing assert on already open file if address changes

[DevLev100]

The function lfs_mlist_isopen() only checks if the address exists. So when the address of the lfs_file_t changes the lfs thinks that this file has not been opened, but indeed it has, just the address is different.
Would it be possible to change to a memcmp check instead of a single pointer check in lfs_mlist_isopen() ?

Example code triggering the assert:

  lfs_file_t file1;
  lfs_file_t file2;
  uint8_t buffer[1];

  // works fine
  lfs_file_open(lfs_fs, &file1, "test1", LFS_O_RDONLY);
  lfs_file_read(lfs_fs, &file1, buffer, sizeof(buffer));
  memcpy(&file2, &file1, sizeof(file2));

  // this call produces an assert (lfs_mlist_isopen)
  lfs_file_read(lfs_fs, &file2, buffer, sizeof(buffer));
  

Inside lfs_mlist_isopen() instead of

 if (*p == (struct lfs_mlist*)node) {
            return true;
        }

we could do

  if(memcmp(*p, node, sizeof(*node)) == 0) {
            return true;
        }

This would make the above code not triggering an assert as I would have expected it.

I am not deep inside the lfs code so this may have some side effects I don't know of. Let me know your thoughts about it.

[geky]

Ah it's good this assert is failing here. memcpy open lfs_file_t structs isn't really supported.

littlefs maintains a linked-list (this "mlist" thing) through all open files. This isn't just used for open-file detection, but also for keeping the state of open files in-sync if neighboring files change the layout on-disk.

So even if this assert passes, moving the files will corrupt the linked-list and lead to out-of-bounds memory issues.

This is an implementation-level detail that isn't really fixable. The alternative would be for littlefs to maintain an internal array of open files which would need to either be statically defined or dynamically allocated (you may see this with other filesystems). Using an invasive linked-list like this avoids unnecessary memory usage which is convenient for the embedded space.

---

One option for OO code that needs to move lfs_file_t structs would be to dynamically allocate the struct and only move the pointer. Or propagate the requirement up that the struct/class should not be moved.

[jacobschloss]

Interesting. I think I ran into this by trying to use a std::optional<lfs_file_t> to manage if a fd had been opened/created yet or not. Not a huge deal and easy to work around, just was unexpected that the lfs_file_t was unmovable.

[geky]

Ah yeah, this probably interferes quite a bit with C++'s move semantics and RAII. You probably want to wrap lfs_file_t in your own class that deletes the move constructors to be safe.

In theory it's possible to add a sort of lfs_file_movehandle function that removes and then readds the lfs_file_t to the linked-list, but it seems low-value. Do you really want to do that much work at every move site?

[jacobschloss]

Having the option might be nice, I probably only need to move a given file handle once or twice between a layer of abstraction code and the main application (STM32H750, FreeRTOS).

May or may not be cheaper than just me wrapping the whole thing up in a std::unique_ptr (which is what I did for now). Probably some tradeoff between how often it is moved and how expensive the heap allocation is. If a lfs_file_movehandle was provided, I would use it to make a move constructor and make my RAII wrapper non-copyable and avoid the heap since I need to move it rarely. I guess this would also mean I need to lock the filesystem level mutex, which might be expensive.

I might take a look at splicing the list for fun, is the head of the linked list at the filesystem object lfs_t::mlist?

[geky]

I might take a look at splicing the list for fun, is the head of the linked list at the filesystem object lfs_t::mlist?

Yes. Internally we have lfs_mlist_append and lfs_mlist_remove. I also don't think you can really do any better than just calling one after the other (lfs_mlist_append is 2 word moves after all).

If you implement said lfs_file_movehandle, feel free to also add lfs_file_ishandleopen and create a PR. I've had reservations in the past in case littlefs drops the internal linked-list, but I think considering the state of things that's unlikely to ever happen. I've seen enough reimplementations of this that we should probably just provide the function.

I still think lfs_file_movehandle risks unnecessary cost -- programmers usually don't think of move as expensive vs memory allocation. But it's probably not my place to disallow what's possible.

Unfortunately with the v3 (#1111) work, v2 is currently in a soft feature freeze, so PRs created right now may take a long time to get merged. Though this would be useful for both v2 and v3.

[geky]

May or may not be cheaper than just me wrapping the whole thing up in a std::unique_ptr (which is what I did for now). Probably some tradeoff between how often it is moved and how expensive the heap allocation is.

Is there a way to back the unique_ptr memory with a global? Via a custom allocator? (this might be overengineering). The might match the closest with how littlefs is used in C.

In theory, lfs_file_movehandle would also let you implement a sort of fixed-size arena allocator fed by a realloced slab of memory. This is what is used by most other filesystems (well, kernels really), and it has the benefit of a fixed-sized allocator being extremely cheap.

[jacobschloss]

Is there a way to back the unique_ptr memory with a global? Via a custom allocator? (this might be overengineering). The might match the closest with how littlefs is used in C.

I think shared_ptr allows for std::allocate_shared which lets you customize how the underlying object is allocated, so could pull from some preallocated global array/arena. I haven't ever tried it.

In theory, lfs_file_movehandle would also let you implement a sort of fixed-size arena allocator fed by a realloced slab of memory. This is what is used by most other filesystems (well, kernels really), and it has the benefit of a fixed-sized allocator being extremely cheap.

I tried a simple lfs_file_movehandle that just splices the linked list at lfs_file_move.c. Some additional plumbing would hook it up to the C++ types. Worked for the single very simple test case I tried with 3 open files. Some arena allocator code could be above this, maybe in the std::allocate_shared implementation.

I might just have my LFS file handle wrapper class specialize a move constructor and splice the open file list there. I really only have like 1-3 open files, and just want to move the C++ object once or twice with some syntactic sugar, its ok if it is "expensive". I should probably clean up my littlefs C++ bindings too, they might be useful to someone.

I'll redo this inside lfs.c using lfs_mlist_remove / lfs_mlist_append and take a look at a lfs_file_ishandleopen and send a PR when it looks good. Understood about the feature freeze, no rush.

[geky]

I think the main risk is that users usually don't expect move operations to grow $O(n)$ w.r.t. the number of open files.

But most users probably just have 1-3 open files like you do, so it may be non-issue. We actually rely on this ourselves in littlefs's internals, with some internal handle-update operations running in $O(n^2)$.

In theory these things could be sped up by using a different data structure to track open files, but that would be one big can of worms (an invasive binary tree?).