Fixed hidden orphans by separating deorphan search into two passes

This happens in rare situations where there is a failed mdir relocation,
interrupted by a power-loss, containing the destination of a directory
rename operation, where the directory being renamed preceded the
relocating mdir in the mdir tail-list. This requires at some point for a
previous directory rename to create a cycle.

If this happens, it's possible for the half-orphan to contain the only
reference to the renamed directory. Since half-orphans contain outdated
state when viewed through the mdir tail-list, the renamed directory
appears to be a full-orphan until we fix the relocating half-orphan.
This causes littlefs to incorrectly remove the renamed directory from
the mdir tail-list, causes catastrophic problems down the line.

The source of the problem is that the two different types of orphans
really operate on two different levels of abstraction: half-orphans fix
failed mdir commits, while full-orphans fix directory removes/renames.
Conflating the two leads to situations where we attempt to fix assumed
problems about the directory tree before we have fixed problems with the
mdir state.

The fix here is to separate out the deorphan search into two passes: one
to fix half-orphans and correct any mdir-commits, restoring the mdirs
and gstate to a known good state, then two to fix failed
removes/renames.

---

This was found with the -Plinear heuristic powerloss testing, which now
runs on more geometries. The failing case was:

  test_relocations_reentrant_renames:112gg261dk1e3f3:123456789abcdefg1h1i1j1k1
  l1m1n1o1p1q1r1s1t1u1v1g2h2i2j2k2l2m2n2o2p2q2r2s2t2

Also fixed/tweaked some parts of the test framework as a part of finding
this bug:

- Fixed off-by-one in exhaustive powerloss state encoding.

- Added --gdb-powerloss-before and --gdb-powerloss-after to help debug
  state changes through a failing powerloss, maybe this should be
  expanded to any arbitrary powerloss number in the future.

- Added lfs_emubd_crc and lfs_emubd_bdcrc to get block/bd crcs for quick
  state comparisons while debugging.

- Fixed bd read/prog/erase counts not being copied during exhaustive
  powerloss testing.

- Fixed small typo in lfs_emubd trace.

2 files changed, 65 insertions, 1 deletions

diff --git a/bd/lfs_emubd.c b/bd/lfs_emubd.c
index 8b42ac5..1f7b1d0 100644
--- a/bd/lfs_emubd.c
+++ b/bd/lfs_emubd.c
@@ -452,7 +452,7 @@ int lfs_emubd_erase(const struct lfs_config *cfg, lfs_block_t block) {
         }
     }
 
-    LFS_EMUBD_TRACE("lfs_emubd_prog -> %d", 0);
+    LFS_EMUBD_TRACE("lfs_emubd_erase -> %d", 0);
     return 0;
 }
 
@@ -468,6 +468,60 @@ int lfs_emubd_sync(const struct lfs_config *cfg) {
 
 /// Additional extended API for driving test features ///
 
+static int lfs_emubd_rawcrc(const struct lfs_config *cfg,
+        lfs_block_t block, uint32_t *crc) {
+    lfs_emubd_t *bd = cfg->context;
+
+    // check if crc is valid
+    LFS_ASSERT(block < cfg->block_count);
+
+    // crc the block
+    uint32_t crc_ = 0xffffffff;
+    const lfs_emubd_block_t *b = bd->blocks[block];
+    if (b) {
+        crc_ = lfs_crc(crc_, b->data, cfg->block_size);
+    } else {
+        uint8_t erase_value = (bd->cfg->erase_value != -1)
+                ? bd->cfg->erase_value
+                : 0;
+        for (lfs_size_t i = 0; i < cfg->block_size; i++) {
+            crc_ = lfs_crc(crc_, &erase_value, 1);
+        }
+    }
+    *crc = 0xffffffff ^ crc_;
+
+    return 0;
+}
+
+int lfs_emubd_crc(const struct lfs_config *cfg,
+        lfs_block_t block, uint32_t *crc) {
+    LFS_EMUBD_TRACE("lfs_emubd_crc(%p, %"PRIu32", %p)",
+            (void*)cfg, block, crc);
+    int err = lfs_emubd_rawcrc(cfg, block, crc);
+    LFS_EMUBD_TRACE("lfs_emubd_crc -> %d", err);
+    return err;
+}
+
+int lfs_emubd_bdcrc(const struct lfs_config *cfg, uint32_t *crc) {
+    LFS_EMUBD_TRACE("lfs_emubd_bdcrc(%p, %p)", (void*)cfg, crc);
+
+    uint32_t crc_ = 0xffffffff;
+    for (lfs_block_t i = 0; i < cfg->block_count; i++) {
+        uint32_t i_crc;
+        int err = lfs_emubd_rawcrc(cfg, i, &i_crc);
+        if (err) {
+            LFS_EMUBD_TRACE("lfs_emubd_bdcrc -> %d", err);
+            return err;
+        }
+
+        crc_ = lfs_crc(crc_, &i_crc, sizeof(uint32_t));
+    }
+    *crc = 0xffffffff ^ crc_;
+
+    LFS_EMUBD_TRACE("lfs_emubd_bdcrc -> %d", 0);
+    return 0;
+}
+
 lfs_emubd_sio_t lfs_emubd_getreaded(const struct lfs_config *cfg) {
     LFS_EMUBD_TRACE("lfs_emubd_getreaded(%p)", (void*)cfg);
     lfs_emubd_t *bd = cfg->context;
@@ -591,6 +645,9 @@ int lfs_emubd_copy(const struct lfs_config *cfg, lfs_emubd_t *copy) {
     }
 
     // other state
+    copy->readed = bd->readed;
+    copy->proged = bd->proged;
+    copy->erased = bd->erased;
     copy->power_cycles = bd->power_cycles;
     copy->disk = bd->disk;
     if (copy->disk) {
diff --git a/bd/lfs_emubd.h b/bd/lfs_emubd.h
index 0fbac1f..c407475 100644
--- a/bd/lfs_emubd.h
+++ b/bd/lfs_emubd.h
@@ -181,6 +181,13 @@ int lfs_emubd_sync(const struct lfs_config *cfg);
 
 /// Additional extended API for driving test features ///
 
+// A CRC of a block for debugging purposes
+int lfs_emubd_crc(const struct lfs_config *cfg,
+        lfs_block_t block, uint32_t *crc);
+
+// A CRC of the entire block device for debugging purposes
+int lfs_emubd_bdcrc(const struct lfs_config *cfg, uint32_t *crc);
+
 // Get total amount of bytes read
 lfs_emubd_sio_t lfs_emubd_getreaded(const struct lfs_config *cfg);