test/int/thashsplit.py

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