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..a0ec17f
--- /dev/null
+++ b/t/sparse-test-data
@@ -0,0 +1,94 @@
+#!/bin/sh
+"""": # -*-python-*-
+bup_python="$(dirname "$0")/../cmd/bup-python" || exit $?
+exec "$bup_python" "$0" ${1+"$@"}
+"""
+
+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 5112ddabd1904cf1f1181ed06ae8b5645f67f0d9..54ecb8268b5602947e6fc5d7bfb87d5919aa645c 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/
 
+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"