Moved to brute-force deorphan without parent pointers

Removing the dependency to the parent pointer solves
many issues with non-atomic updates of children's
parent pointers with respect to any move operations.

However, this comes with an embarrassingly terrible
runtime as the only other option is to exhaustively
check every dir entry to find a child's parent.

Fortunately, deorphaning should be a relatively rare
operation.

2 files changed, 49 insertions, 0 deletions

diff --git a/tests/template.fmt b/tests/template.fmt
index fe1f648..c7668db 100644
--- a/tests/template.fmt
+++ b/tests/template.fmt
@@ -30,6 +30,14 @@ void test_assert(const char *file, unsigned line,
 #define test_assert(s, v, e) test_assert(__FILE__, __LINE__, s, v, e)
 
 
+// utility functions for traversals
+int test_count(void *p, lfs_block_t b) {{
+    unsigned *u = (unsigned*)p;
+    *u += 1;
+    return 0;
+}}
+
+
 // lfs declarations
 lfs_t lfs;
 lfs_emubd_t bd;
diff --git a/tests/test_orphan.sh b/tests/test_orphan.sh
new file mode 100755
index 0000000..b5e7ebb
--- /dev/null
+++ b/tests/test_orphan.sh
@@ -0,0 +1,41 @@
+#!/bin/bash
+set -eu
+
+echo "=== Orphan tests ==="
+rm -rf blocks
+tests/test.py << TEST
+    lfs_format(&lfs, &config) => 0;
+TEST
+
+echo "--- Orphan test ---"
+tests/test.py << TEST
+    lfs_mount(&lfs, &config) => 0;
+    lfs_mkdir(&lfs, "parent") => 0;
+    lfs_mkdir(&lfs, "parent/orphan") => 0;
+    lfs_mkdir(&lfs, "parent/child") => 0;
+    lfs_remove(&lfs, "parent/orphan") => 0;
+TEST
+# remove most recent file, this should be the update to the previous
+# linked-list entry and should orphan the child
+rm -v "blocks/$(ls -t blocks | sed -n '/^[0-9a-f]*$/p' | sed -n '1p')"
+tests/test.py << TEST
+    lfs_mount(&lfs, &config) => 0;
+    lfs_stat(&lfs, "parent/orphan", &info) => LFS_ERROR_NO_ENTRY;
+    unsigned before = 0;
+    lfs_traverse(&lfs, test_count, &before) => 0;
+    test_log("before", before);
+
+    lfs_deorphan(&lfs) => 0;
+
+    lfs_stat(&lfs, "parent/orphan", &info) => LFS_ERROR_NO_ENTRY;
+    unsigned after = 0;
+    lfs_traverse(&lfs, test_count, &after) => 0;
+    test_log("after", after);
+
+    int diff = before - after;
+    diff => 2;
+    lfs_unmount(&lfs) => 0;
+TEST
+
+echo "--- Results ---"
+tests/stats.py