restore: add generative --sparse testing

Add t/sparse-test-data to automatically generate cases that might trip
up "restore --sparse", and use it in test-sparse-files.sh.  This change
causes the current --sparse code to fail if you run enough trials,
but not as quickly as the existing "bup random" based test.

As compared to the existing "bup random" test, this one should evaluate
larger sparse regions much more often.

Thanks to Frank Gevaerts for help evaluating the fix.

Signed-off-by: Rob Browning <rlb@defaultvalue.org>

diff --git a/t/sparse-test-data b/t/sparse-test-data
new file mode 100755 (executable)
index 0000000..b58234f
--- /dev/null
+++ b/t/sparse-test-data
@@ -0,0 +1,90 @@
+#!/usr/bin/env python
+
+from random import randint
+from sys import stderr, stdout
+import sys
+
+
+def smaller_region(max_offset):
+    start = randint(0, max_offset)
+    return (start, min(max_offset, randint(start + 1, start + 5)))
+
+
+def possibly_larger_region(max_offset, min_sparse_len):
+    start = randint(0, max_offset)
+    return (start, min(max_offset, randint(start + 1,
+                                           start + 3 * min_sparse_len)))
+
+
+def initial_region(max_offset, min_sparse_len):
+    start = 0
+    return (start, min(max_offset, randint(start + 1,
+                                           start + 3 * min_sparse_len)))
+
+
+def final_region(max_offset, min_sparse_len):
+    start = max(0, randint(max_offset - 3 * min_sparse_len,
+                           max_offset - 1))
+    return (start, max_offset)
+
+
+def region_around_min_len(max_offset, min_sparse_len):
+    start = randint(0, max_offset)
+    return (start, min(max_offset, randint(start + min_sparse_len - 5,
+                                           start + min_sparse_len + 5)))
+
+
+generators = []
+
+def random_region():
+    global generators
+    return generators[randint(0, len(generators) - 1)]()
+    
+
+out = stdout
+
+if len(sys.argv) == 2:
+    out = open(sys.argv[1], 'wb')
+elif len(sys.argv):
+    print >> stderr, "Usage: sparse-test-data [FILE]"
+
+bup_read_size = 2 ** 16
+bup_min_sparse_len = 512
+out_size = randint(0, bup_read_size * 10)
+
+generators = (lambda : smaller_region(out_size),
+              lambda : possibly_larger_region(out_size, bup_min_sparse_len),
+              lambda : initial_region(out_size, bup_min_sparse_len),
+              lambda : final_region(out_size, bup_min_sparse_len),
+              lambda : region_around_min_len(out_size, bup_min_sparse_len))
+
+sparse = []
+sparse.append(random_region())
+sparse.append(random_region())
+
+# Handle overlaps
+if sparse[1][0] < sparse[0][0]:
+    sparse[0], sparse[1] = sparse[1], sparse[0]
+
+sparse_offsets = []
+sparse_offsets.append(sparse[0][0])
+if sparse[1][0] <= sparse[0][1]:
+    sparse_offsets.append(max(sparse[0][1], sparse[1][1]))
+else:
+    sparse_offsets.extend((sparse[0][1], sparse[1][0], sparse[1][1]))
+
+if sparse[1][1] != out_size:
+    sparse_offsets.append(out_size)
+
+# Now sparse_offsets indicates where to start/stop zero runs
+data = 'x'
+pos = 0
+print >> stderr, 'offsets:', sparse_offsets
+for offset in sparse_offsets:
+    count = offset - pos
+    print >> stderr, 'write:', 'x' if data == 'x' else '0', count
+    out.write(data * (offset - pos))
+    pos += count
+    data = '\0' if data == 'x' else 'x'
+
+out.close()

diff --git a/t/test-sparse-files.sh b/t/test-sparse-files.sh
index 8ff5ddeff303a729800eab4bc1860c5f3624ea37..ce06d8f5d82c2f6dca33e68978a8152d48e8eb10 100755 (executable)
--- a/t/test-sparse-files.sh
+++ b/t/test-sparse-files.sh
@@ -127,4 +127,19 @@ WVPASS rm -r restore
 WVPASS bup restore --sparse -C restore "src/latest/$(pwd)/"
 WVPASS "$top/t/compare-trees" -c src/ restore/src/
 
 WVPASS bup restore --sparse -C restore "src/latest/$(pwd)/"
 WVPASS "$top/t/compare-trees" -c src/ restore/src/
 

+WVSTART "sparse file restore --sparse (random sparse regions)"
+WVPASS rm -rf "$BUP_DIR" src
+WVPASS bup init
+WVPASS mkdir src
+for sparse_dataset in 0 1 2 3 4 5 6 7 8 9
+do
+    WVPASS "$top/t/sparse-test-data" "src/foo-$sparse_dataset"
+done
+WVPASS bup index src
+WVPASS bup save -n src src
+WVPASS rm -r restore
+WVPASS bup restore --sparse -C restore "src/latest/$(pwd)/"
+WVPASS "$top/t/compare-trees" -c src/ restore/src/
+
+

 WVPASS rm -rf "$tmpdir"
 WVPASS rm -rf "$tmpdir"