Assertion after Continuous Metadata Blocks Relocation during Deletion

[Hugh-Baoa]

During internal functional stress tests with Zephyr OS using SLC NAND flash, I encountered an issue. The main process involves repeatedly deleting, renaming, and writing files. Eventually, an assertion failure occurs during the file deletion process. Specifically, the assertion is triggered when gstate.tag is 0 and orphans is -1. The assertion failure occurs at the Heading code section. As follows:

if (lfs_tag_type3(tag) == LFS_TYPE_DIR) {
    // fix orphan
    ### err = lfs_fs_preporphans(lfs, -1);
    if (err) {
        return err;
    }
    err = lfs_fs_pred(lfs, dir.m.pair, &cwd);
    if (err) {
        return err;
    }
    err = lfs_dir_drop(lfs, &cwd, &dir.m);
    if (err) {
        return err;
    }
}

#ifndef LFS_READONLY
static int lfs_fs_preporphans(lfs_t *lfs, int8_t orphans) {
    ### LFS_ASSERT(lfs_tag_size(lfs->gstate.tag) > 0x000 || orphans >= 0);
    LFS_ASSERT(lfs_tag_size(lfs->gstate.tag) < 0x1ff || orphans <= 0);
    lfs->gstate.tag += orphans;
    lfs->gstate.tag = ((lfs->gstate.tag & ~LFS_MKTAG(0x800, 0, 0)) |
            ((uint32_t)lfs_gstate_hasorphans(&lfs->gstate) << 31));
    return 0;
}
#endif

Process diagram:

lfs_rawremove()
    |__ lfs_fs_preporphans(lfs, +1)
    |__ lfs_dir_commit()   <-- commit delete tag
    |        |__ lfs_fs_deorphan()
    |                 |__ lfs_fs_preporphans(lfs, -lfs_gstate_getorphans(&lfs->gstate))   <--- Set gstate.tag to 0
    |__ lfs_fs_preporphans(lfs, -1)    <--- Caught an assertion, expecting gstate.tag to be > 0

littlefs version: v2.8

Our team has added debug logs for verification. During the deletion process, a tag commit is required, which triggers two levels of metadata block relocation. Normally, without relocation, gstate.tag would be incremented by 1 before the commit and decremented by 1 after the commit.

However, after two levels of relocation, there is a segment in the flow post-relocation that resets gstate.tag to zero. Consequently, when the deletion process attempts to decrement gstate.tag by 1 after the final commit, it encounters an assertion failure.

I would like to ask for some advice.
What could be the possible causes of the described issue?
What is the specific purpose of the implementation in lfs_fs_preporphans?

[geky]

Hi @Hugh-Baoa, sorry about the late response. Thanks for creating an issue and finding the root cause!

This does look like a bug. I was able to reproduce and am in the process of pushing up a fix. Your summary of the issue is pretty much correct.

What could be the possible causes of the described issue?
What is the specific purpose of the implementation in lfs_fs_preporphans?

So, the purpose of lfs_fs_preporphans is to track whether or not there are orphaned mdirs on-disk. If there are orphaned mdirs after a powerloss, we need to clean them up by scanning the disk, which runs in $O(n^2)$, so we really don't want to scan unless we have to. This is implemented by lfs_fs_deorphan.

On-disk, whether or not there are orphans is stored in global-state, as a boolean "sync bit". In-device, however, we store a counter so we know when all orphans have been cleaned up without needing to deorphan.

lfs_dir_commit used to never need to deorphan, and could clean up all orphans as they were created, but this fundamentally relied on recursion. When recursion was finally eliminated (in #658), lfs_fs_deorphan as introduced as a backup plan to avoid the unbounded stack that would be necessary to track all in-flight orphans.

---

Long story short! It looks like lfs_remove was not updated to check for this. The lfs_fs_deorphan cleans up all orphans, including the intentional orphan created by lfs_remove when it deletes a directory.

I suspect this hasn't been noticed yet as directory deletion is relatively rare in embedded applications, and it requires aligning with an mdir relocation.

Fortunately the fix is relatively easy, we just need to check if there are still orphans before deleting the remove orphan.

---

The good news is this mess is all going away eventually. There's work in progress to replace the threaded filesystem tree with a unified metadata-tree, which turns littlefs into at least a DAG instead of a fully connected graph.

The amount of headache and bugs that have come from orphan corner cases have been a real pain-in-the-ass.

[geky]

I pushed up a fix here: #1099

I also increased our orphan/relocation testing to prevent a regression and hopefully catch similar bugs. We were artificially limiting what we were testing due to powerloss testing runtime, but for now I've just split the tests into reentrant/non-reentrant variants to get around this.

Will bring this into the next patch release unless you see any issue.