From: Rob Browning <rlb@defaultvalue.org>
Date: Sun, 24 Apr 2016 22:52:02 +0000 (-0500)
Subject: restore: add generative --sparse testing
X-Git-Tag: 0.27.1-rc1~1^2~2
X-Git-Url: https://arthur.barton.de/cgi-bin/gitweb.cgi?p=bup.git;a=commitdiff_plain;h=b6e97ce29c7ade5bbe05b07328765c4675cfe4e8

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
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 8ff5dde..ce06d8f 100755
--- 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"