littlefs: Block-cycles/revision-count improvements

Here are the four method’s disassembly on ARM when compiling for -Os: https://godbolt.org/z/9sKP9r

Ah! I see, so you’re effectively using the lowest bit to offset one block by block_cycles/2. I initially didn’t understand what was going on.

Sorry, I probably should have explained it better. 😃 But yes, since that lowest bit dictates even/odd, it could be used to decide offsetting the eviction modulus result, and then that bit gets thrown away in the overall divide by 2 before the modulus is checked. Same overall result as making the modulus not contain the prime factor 2, but allows for better optimizations by the compiler. 😃

You could even get rid of the conditional:

// mul/div should optimize to bit-shifts if block_cycles is power-of-2
((rev + ((rev & 1)*block_cycles)) / 2) % block_cycles

Hopefully the compiler would recognize you’re either multiplying by 0 or 1 here and just reduce it to a conditional add instruction in the underlying architecture. I suppose for code readability you might actually have it a separate line:

int tmp_rev = dir->rev;
// Check to see if it's odd and add in block_cycles if we're odd in order
// to stagger the eviction of the odd directory revisions
if(tmp_rev & 1) {
    tmp_rev += block_cycles;
}
if((tmp_rev / 2) % block_cycles == 0) {
...
}

I’ll word that better in the future, if I put “should fix/resolve” it triggers GitHub’s automatic issue closing, which wasn’t what I wanted.

Ah, I see, thanks for the clarification!

Hi @dpgeorge -

This was fixed in the commit referenced by @geky above

Thanks, I did see that. But what I noticed in the message of #490 is that it says “Should help #489”. Does that mean it fixes the issue here fully, or just makes it less likely for the problem to occur?

It completely mitigates the issue I observed and captured in the original ticket here. There’s a sample case as an attachment with the LFS mount parameters to replicate the issue I saw. The commit in #490 fixes the issue with that attachment, and I’m pretty sure it’ll fix it for all cases that have the same issue (e.g. eviction, which expects a valid filesystem, during lfs_format() where there isn’t a valid filesystem yet). The eviction logic is just a counter and it runs the eviction code if it modulo X is 0. So if the existing contents caused that to occur, the eviction logic said “corrupt filesystem” and this trickled out into the lfs_format() call with the LFS_ERR_CORRUPT error code.

I should probably just mark this as closed as the fix is now in the “devel” branch. It’s just not in any formal release yet.

Hi @geky -

No problem! A few other observations I was thinking about:

• Technically when it “wraps” the revision counter (e. g. crossing 0xffff ffff to 0x0000 0000), we’ll end up with a partial period of the modulus since the modulus currently cannot directly divide into 2^32. I don’t think this is important to fix, but was something that popped into my head over the past couple of days. (This wouldn’t occur if the eviction modulus was a power of 2, but that’s not possible with the current eviction logic.)
• When you get #491 in place the compiler could decide to optimize the various moduli in the system with bit-wise AND masks depending on the static values picked by the user of the filesystem (of course it can only do that if static values are used instead of dynamic ones). The current modulus for the revision counter could never be optimized into bitwise operations by the compiler. Depending on the microcontroller and other code usages by the user of lfs, allowing the compiler to optimize this may remove extra code from the compiled binary and reduce the overall size. (The modulus operation isn’t always free from a code space perspective, or from a computation perspective.)
• The change you referenced in fe957de8 causes the pair of revisions to evict out of phase from each other. E.g. when allocating the root directory at blocks 0 and 1, block 1 will be evicted at roughly half of the revision count whereas block 0 will evict at roughly the full revision count. (It’d even out long term, but just that first eviction for a given directory would end up doing that.) I’m not sure if this was intentional or not; I think another approach would have been to do (rev >> 1) % block_cycles - e.g. discarding the lowest bit. The advantage of this approach is that it could be optimized to bit-wise operations in the static configuration case above. (Technically the current eviction logic is probably slightly better from a “lots of writes in a row perspective” since you won’t hit two erases in a row as easily for the directory pair.) (Of course, you’d need a minimum on the modulus here of 2 or something.) You could maintain the out of phase thing here (and allow it to be optimized to bit-wise operations when static configurations come along) by doing ((rev + ((rev & 1) ? block_cycles : 0)) >> 1) % block_cycles (untested math, but I think it checks out). In this case you’d still do the rev + 1 logic elsewhere. You’d need to avoid incrementing block_cycles by 1 to get the bit-wise optimization with static configs of course, so it might be better to implement a “minimum” block cycles value via a helper function getter or something?

Anyhow… I don’t know if any action needs to happen with the above thoughts - just random musings. 😃

– Tim

I did a little more investigation today, and it looks like:

• lfs_dir_alloc(…) picks up the random value for pre-defining the revision counter for the flash block.
• This gets fed down into the lfs_dir_compact(…) routine.
• This particular case (and combination with my block cycles value) causes lfs_dir_compact(…) to decide it needs to do a relocation.
• Since there wasn’t a valid filesystem here, the lfs_fs_size(…) invocation fails.

For a more normal flash erased value of all 0xff’s or 0x00’s, the initial revision gets set to 0, so the initial case always works.

It seems like the lfs_dir_alloc(…) is attempting to preserve the existing revision counter for a given block, so that lfs_dir_compact(…) later can decide whether or not it needs to move blocks or not. If it does this across the board a filesystem on top of an encrypted layer in there will end up with random counters for evicting a given flash block across all of the blocks. This isn’t strictly a problem, but in the format case it seems like it shouldn’t do this at all since there are “unknown” values in the superblock location.

Should the format case ignore the current revision counter in the superblock, or preserve it? One easy way to fix this particular case would be to do the following inside lfs_format(…):

         // create root dir
         lfs_mdir_t root;
         err = lfs_dir_alloc(lfs, &root);
         if (err) {
             goto cleanup;
         }
 
+        // Update revision to 0
+        root.rev = 0;
+
         // write one superblock
         lfs_superblock_t superblock = {
             .version     = LFS_DISK_VERSION,
             .block_size  = lfs->cfg->block_size,
             .block_count = lfs->cfg->block_count,
             .name_max    = lfs->name_max,
             .file_max    = lfs->file_max,
             .attr_max    = lfs->attr_max,
         };

Alternatively, during a lfs_format(…) only, we’d need to consider a “CORRUPT” case inside lfs_fs_size(…) to be grounds to continue formatting anyways. That’d likely need additional arguments trickled down into it though.