test/int/test_hashsplit.py

   1
   2 from __future__ import absolute_import
   3 from io import BytesIO
   4
   5 from wvpytest import *
   6
   7 from bup import hashsplit, _helpers, helpers
   8 from bup.compat import byte_int, bytes_from_uint
   9
  10
  11 def nr_regions(x, max_count=None):
  12     return list(hashsplit._nonresident_page_regions(bytearray(x), 1, max_count))
  13
  14
  15 def test_nonresident_page_regions():
  16     WVPASSEQ(nr_regions([]), [])
  17     WVPASSEQ(nr_regions([1]), [])
  18     WVPASSEQ(nr_regions([0]), [(0, 1)])
  19     WVPASSEQ(nr_regions([1, 0]), [(1, 1)])
  20     WVPASSEQ(nr_regions([0, 0]), [(0, 2)])
  21     WVPASSEQ(nr_regions([1, 0, 1]), [(1, 1)])
  22     WVPASSEQ(nr_regions([1, 0, 0]), [(1, 2)])
  23     WVPASSEQ(nr_regions([0, 1, 0]), [(0, 1), (2, 1)])
  24     WVPASSEQ(nr_regions([0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0]),
  25              [(0, 2), (5, 3), (9, 2)])
  26     WVPASSEQ(nr_regions([2, 42, 3, 101]), [(0, 2)])
  27     # Test limit
  28     WVPASSEQ(nr_regions([0, 0, 0], None), [(0, 3)])
  29     WVPASSEQ(nr_regions([0, 0, 0], 1), [(0, 1), (1, 1), (2, 1)])
  30     WVPASSEQ(nr_regions([0, 0, 0], 2), [(0, 2), (2, 1)])
  31     WVPASSEQ(nr_regions([0, 0, 0], 3), [(0, 3)])
  32     WVPASSEQ(nr_regions([0, 0, 0], 4), [(0, 3)])
  33     WVPASSEQ(nr_regions([0, 0, 1], None), [(0, 2)])
  34     WVPASSEQ(nr_regions([0, 0, 1], 1), [(0, 1), (1, 1)])
  35     WVPASSEQ(nr_regions([0, 0, 1], 2), [(0, 2)])
  36     WVPASSEQ(nr_regions([0, 0, 1], 3), [(0, 2)])
  37     WVPASSEQ(nr_regions([1, 0, 0], None), [(1, 2)])
  38     WVPASSEQ(nr_regions([1, 0, 0], 1), [(1, 1), (2, 1)])
  39     WVPASSEQ(nr_regions([1, 0, 0], 2), [(1, 2)])
  40     WVPASSEQ(nr_regions([1, 0, 0], 3), [(1, 2)])
  41     WVPASSEQ(nr_regions([1, 0, 0, 0, 1], None), [(1, 3)])
  42     WVPASSEQ(nr_regions([1, 0, 0, 0, 1], 1), [(1, 1), (2, 1), (3, 1)])
  43     WVPASSEQ(nr_regions([1, 0, 0, 0, 1], 2), [(1, 2), (3, 1)])
  44     WVPASSEQ(nr_regions([1, 0, 0, 0, 1], 3), [(1, 3)])
  45     WVPASSEQ(nr_regions([1, 0, 0, 0, 1], 4), [(1, 3)])
  46
  47
  48 def test_uncache_ours_upto():
  49     history = []
  50     def mock_fadvise_pages_done(f, ofs, len):
  51         history.append((f, ofs, len))
  52
  53     uncache_upto = hashsplit._uncache_ours_upto
  54     page_size = helpers.sc_page_size
  55     orig_pages_done = hashsplit._fadvise_pages_done
  56     try:
  57         hashsplit._fadvise_pages_done = mock_fadvise_pages_done
  58         history = []
  59         uncache_upto(42, 0, (0, 1), iter([]))
  60         WVPASSEQ([], history)
  61         uncache_upto(42, page_size, (0, 1), iter([]))
  62         WVPASSEQ([(42, 0, 1)], history)
  63         history = []
  64         uncache_upto(42, page_size, (0, 3), iter([(5, 2)]))
  65         WVPASSEQ([], history)
  66         uncache_upto(42, 2 * page_size, (0, 3), iter([(5, 2)]))
  67         WVPASSEQ([], history)
  68         uncache_upto(42, 3 * page_size, (0, 3), iter([(5, 2)]))
  69         WVPASSEQ([(42, 0, 3)], history)
  70         history = []
  71         uncache_upto(42, 5 * page_size, (0, 3), iter([(5, 2)]))
  72         WVPASSEQ([(42, 0, 3)], history)
  73         history = []
  74         uncache_upto(42, 6 * page_size, (0, 3), iter([(5, 2)]))
  75         WVPASSEQ([(42, 0, 3)], history)
  76         history = []
  77         uncache_upto(42, 7 * page_size, (0, 3), iter([(5, 2)]))
  78         WVPASSEQ([(42, 0, 3), (42, 5, 2)], history)
  79     finally:
  80         hashsplit._fadvise_pages_done = orig_pages_done
  81
  82
  83 def test_rolling_sums():
  84     WVPASS(_helpers.selftest())
  85
  86 def test_fanout_behaviour():
  87     # Drop in replacement for bupsplit, but splitting if the int value of a
  88     # byte >= BUP_BLOBBITS
  89     basebits = _helpers.blobbits()
  90     def splitbuf(buf):
  91         ofs = 0
  92         for b in buf:
  93             b = byte_int(b)
  94             ofs += 1
  95             if b >= basebits:
  96                 return ofs, b
  97         return 0, 0
  98
  99     old_splitbuf = _helpers.splitbuf
 100     _helpers.splitbuf = splitbuf
 101     old_BLOB_MAX = hashsplit.BLOB_MAX
 102     hashsplit.BLOB_MAX = 4
 103     old_BLOB_READ_SIZE = hashsplit.BLOB_READ_SIZE
 104     hashsplit.BLOB_READ_SIZE = 10
 105     old_fanout = hashsplit.fanout
 106     hashsplit.fanout = 2
 107
 108     levels = lambda f: [(len(b), l) for b, l in
 109         hashsplit.hashsplit_iter([f], True, None)]
 110     # Return a string of n null bytes
 111     z = lambda n: b'\x00' * n
 112     # Return a byte which will be split with a level of n
 113     sb = lambda n: bytes_from_uint(basebits + n)
 114
 115     split_never = BytesIO(z(16))
 116     split_first = BytesIO(z(1) + sb(3) + z(14))
 117     split_end   = BytesIO(z(13) + sb(1) + z(2))
 118     split_many  = BytesIO(sb(1) + z(3) + sb(2) + z(4) +
 119                           sb(0) + z(4) + sb(5) + z(1))
 120     WVPASSEQ(levels(split_never), [(4, 0), (4, 0), (4, 0), (4, 0)])
 121     WVPASSEQ(levels(split_first), [(2, 3), (4, 0), (4, 0), (4, 0), (2, 0)])
 122     WVPASSEQ(levels(split_end), [(4, 0), (4, 0), (4, 0), (2, 1), (2, 0)])
 123     WVPASSEQ(levels(split_many),
 124         [(1, 1), (4, 2), (4, 0), (1, 0), (4, 0), (1, 5), (1, 0)])
 125
 126     _helpers.splitbuf = old_splitbuf
 127     hashsplit.BLOB_MAX = old_BLOB_MAX
 128     hashsplit.BLOB_READ_SIZE = old_BLOB_READ_SIZE
 129     hashsplit.fanout = old_fanout