Added support for handling corrupted blocks

This provides a limited form of wear leveling. While wear is
not actually balanced across blocks, the filesystem can recover
from corrupted blocks and extend the lifetime of a device nearly
as much as dynamic wear leveling.

For use-cases where wear is important, it would be better to use
a full form of dynamic wear-leveling at the block level. (or
consider a logging filesystem).

Corrupted block handling was simply added on top of the existing
logic in place for the filesystem, so it's a bit more noodly than
it may have to be, but it gets the work done.

4 files changed, 118 insertions, 5 deletions

diff --git a/tests/template.fmt b/tests/template.fmt
index f72403c..41f3420 100644
--- a/tests/template.fmt
+++ b/tests/template.fmt
@@ -13,11 +13,17 @@ void test_log(const char *s, uintmax_t v) {{
 
 void test_assert(const char *file, unsigned line,
         const char *s, uintmax_t v, uintmax_t e) {{
-    static const char *last[2] = {{0, 0}};
-    if (v != e || !(last[0] == s || last[1] == s)) {{
+    static const char *last[6] = {{0, 0}};
+    if (v != e || !(last[0] == s || last[1] == s ||
+            last[2] == s || last[3] == s ||
+            last[4] == s || last[5] == s)) {{
         test_log(s, v);
         last[0] = last[1];
-        last[1] = s;
+        last[1] = last[2];
+        last[2] = last[3];
+        last[3] = last[4];
+        last[4] = last[5];
+        last[5] = s;
     }}
 
     if (v != e) {{
diff --git a/tests/test_corrupt.sh b/tests/test_corrupt.sh
new file mode 100755
index 0000000..d79a8c8
--- /dev/null
+++ b/tests/test_corrupt.sh
@@ -0,0 +1,106 @@
+#!/bin/bash
+set -eu
+
+echo "=== Corrupt tests ==="
+
+NAMEMULT=64
+FILEMULT=1
+
+lfs_mktree() {
+tests/test.py ${1:-} << TEST
+    lfs_format(&lfs, &cfg) => 0;
+
+    lfs_mount(&lfs, &cfg) => 0;
+    for (int i = 1; i < 10; i++) {
+        for (int j = 0; j < $NAMEMULT; j++) {
+            buffer[j] = '0'+i;
+        }
+        buffer[$NAMEMULT] = '\0';
+        lfs_mkdir(&lfs, (char*)buffer) => 0;
+
+        buffer[$NAMEMULT] = '/';
+        for (int j = 0; j < $NAMEMULT; j++) {
+            buffer[j+$NAMEMULT+1] = '0'+i;
+        }
+        buffer[2*$NAMEMULT+1] = '\0';
+        lfs_file_open(&lfs, &file[0], (char*)buffer,
+                LFS_O_WRONLY | LFS_O_CREAT) => 0;
+        
+        size = $NAMEMULT;
+        for (int j = 0; j < i*$FILEMULT; j++) {
+            lfs_file_write(&lfs, &file[0], buffer, size) => size;
+        }
+
+        lfs_file_close(&lfs, &file[0]) => 0;
+    }
+    lfs_unmount(&lfs) => 0;
+TEST
+}
+
+lfs_chktree() {
+tests/test.py ${1:-} << TEST
+    lfs_mount(&lfs, &cfg) => 0;
+    for (int i = 1; i < 10; i++) {
+        for (int j = 0; j < $NAMEMULT; j++) {
+            buffer[j] = '0'+i;
+        }
+        buffer[$NAMEMULT] = '\0';
+        lfs_stat(&lfs, (char*)buffer, &info) => 0;
+        info.type => LFS_TYPE_DIR;
+
+        buffer[$NAMEMULT] = '/';
+        for (int j = 0; j < $NAMEMULT; j++) {
+            buffer[j+$NAMEMULT+1] = '0'+i;
+        }
+        buffer[2*$NAMEMULT+1] = '\0';
+        lfs_file_open(&lfs, &file[0], (char*)buffer, LFS_O_RDONLY) => 0;
+        
+        size = $NAMEMULT;
+        for (int j = 0; j < i*$FILEMULT; j++) {
+            lfs_file_read(&lfs, &file[0], rbuffer, size) => size;
+            memcmp(buffer, rbuffer, size) => 0;
+        }
+
+        lfs_file_close(&lfs, &file[0]) => 0;
+    }
+    lfs_unmount(&lfs) => 0;
+TEST
+}
+
+echo "--- Sanity check ---"
+rm -rf blocks
+lfs_mktree
+lfs_chktree
+
+echo "--- Block corruption ---"
+for i in {0..33}
+do 
+    rm -rf blocks
+    mkdir blocks
+    ln -s /dev/zero blocks/$(printf '%x' $i)
+    lfs_mktree
+    lfs_chktree
+done
+
+echo "--- Big region corruption ---"
+rm -rf blocks
+mkdir blocks
+for i in {2..255}
+do
+    ln -s /dev/zero blocks/$(printf '%x' $i)
+done
+lfs_mktree
+lfs_chktree
+
+echo "--- Alternating corruption ---"
+rm -rf blocks
+mkdir blocks
+for i in {2..511..2}
+do
+    ln -s /dev/zero blocks/$(printf '%x' $i)
+done
+lfs_mktree
+lfs_chktree
+
+echo "--- Results ---"
+tests/stats.py
diff --git a/tests/test_dirs.sh b/tests/test_dirs.sh
index c44a82a..815b88b 100755
--- a/tests/test_dirs.sh
+++ b/tests/test_dirs.sh
@@ -124,6 +124,7 @@ tests/test.py << TEST
 TEST
 
 echo "--- Directory remove ---"
+# TESTING HERE
 tests/test.py << TEST
     lfs_mount(&lfs, &cfg) => 0;
     lfs_remove(&lfs, "potato") => LFS_ERR_INVAL;
diff --git a/tests/test_format.sh b/tests/test_format.sh
index 8589a8e..b907101 100755
--- a/tests/test_format.sh
+++ b/tests/test_format.sh
@@ -10,8 +10,8 @@ tests/test.py << TEST
 TEST
 
 echo "--- Invalid superblocks ---"
-ln -f -s /dev/null blocks/0
-ln -f -s /dev/null blocks/1
+ln -f -s /dev/zero blocks/0
+ln -f -s /dev/zero blocks/1
 tests/test.py << TEST
     lfs_format(&lfs, &cfg) => LFS_ERR_CORRUPT;
 TEST