test_blockimgdiff.py revision 186ec99eb9a5580bbd6404ba61b5210f524d65aa 
1#
2# Copyright (C) 2016 The Android Open Source Project
3#
4# Licensed under the Apache License, Version 2.0 (the "License");
5# you may not use this file except in compliance with the License.
6# You may obtain a copy of the License at
7#
8#      http://www.apache.org/licenses/LICENSE-2.0
9#
10# Unless required by applicable law or agreed to in writing, software
11# distributed under the License is distributed on an "AS IS" BASIS,
12# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13# See the License for the specific language governing permissions and
14# limitations under the License.
15#
16
17from __future__ import print_function
18
19import unittest
20
21import common
22from blockimgdiff import BlockImageDiff, EmptyImage, HeapItem, Transfer
23from rangelib import RangeSet
24
25
26class HealpItemTest(unittest.TestCase):
27
28  class Item(object):
29    def __init__(self, score):
30      self.score = score
31
32  def test_init(self):
33    item1 = HeapItem(self.Item(15))
34    item2 = HeapItem(self.Item(20))
35    item3 = HeapItem(self.Item(15))
36    self.assertTrue(item1)
37    self.assertTrue(item2)
38    self.assertTrue(item3)
39
40    self.assertNotEqual(item1, item2)
41    self.assertEqual(item1, item3)
42    # HeapItem uses negated scores.
43    self.assertGreater(item1, item2)
44    self.assertLessEqual(item1, item3)
45    self.assertTrue(item1 <= item3)
46    self.assertFalse(item2 >= item1)
47
48  def test_clear(self):
49    item = HeapItem(self.Item(15))
50    self.assertTrue(item)
51
52    item.clear()
53    self.assertFalse(item)
54
55
56class BlockImageDiffTest(unittest.TestCase):
57
58  def test_GenerateDigraphOrder(self):
59    """Make sure GenerateDigraph preserves the order.
60
61    t0: <0-5> => <...>
62    t1: <0-7> => <...>
63    t2: <0-4> => <...>
64    t3: <...> => <0-10>
65
66    t0, t1 and t2 must go before t3, i.e. t3.goes_after =
67    { t0:..., t1:..., t2:... }. But the order of t0-t2 must be preserved.
68    """
69
70    src = EmptyImage()
71    tgt = EmptyImage()
72    block_image_diff = BlockImageDiff(tgt, src)
73
74    transfers = block_image_diff.transfers
75    t0 = Transfer("t1", "t1", RangeSet("10-15"), RangeSet("0-5"), "t1hash",
76                  "t1hash", "move", transfers)
77    t1 = Transfer("t2", "t2", RangeSet("20-25"), RangeSet("0-7"), "t2hash",
78                  "t2hash", "move", transfers)
79    t2 = Transfer("t3", "t3", RangeSet("30-35"), RangeSet("0-4"), "t3hash",
80                  "t3hash", "move", transfers)
81    t3 = Transfer("t4", "t4", RangeSet("0-10"), RangeSet("40-50"), "t4hash",
82                  "t4hash", "move", transfers)
83
84    block_image_diff.GenerateDigraph()
85    t3_goes_after_copy = t3.goes_after.copy()
86
87    # Elements in the set must be in the transfer evaluation order.
88    elements = list(t3_goes_after_copy)
89    self.assertEqual(t0, elements[0])
90    self.assertEqual(t1, elements[1])
91    self.assertEqual(t2, elements[2])
92
93    # Now switch the order of t0, t1 and t2.
94    transfers[0], transfers[1], transfers[2] = (
95        transfers[2], transfers[0], transfers[1])
96    t3.goes_after.clear()
97    t3.goes_before.clear()
98    block_image_diff.GenerateDigraph()
99
100    # The goes_after must be different from last run.
101    self.assertNotEqual(t3_goes_after_copy, t3.goes_after)
102
103    # Assert that each element must agree with the transfer order.
104    elements = list(t3.goes_after)
105    self.assertEqual(t2, elements[0])
106    self.assertEqual(t0, elements[1])
107    self.assertEqual(t1, elements[2])
108
109  def test_ReviseStashSize(self):
110    """ReviseStashSize should convert transfers to 'new' commands as needed.
111
112    t1: diff <20-29> => <11-15>
113    t2: diff <11-15> => <20-29>
114    """
115
116    src = EmptyImage()
117    tgt = EmptyImage()
118    block_image_diff = BlockImageDiff(tgt, src, version=3)
119
120    transfers = block_image_diff.transfers
121    Transfer("t1", "t1", RangeSet("11-15"), RangeSet("20-29"), "t1hash",
122             "t1hash", "diff", transfers)
123    Transfer("t2", "t2", RangeSet("20-29"), RangeSet("11-15"), "t2hash",
124             "t2hash", "diff", transfers)
125
126    block_image_diff.GenerateDigraph()
127    block_image_diff.FindVertexSequence()
128    block_image_diff.ReverseBackwardEdges()
129
130    # Sufficient cache to stash 5 blocks (size * 0.8 >= 5).
131    common.OPTIONS.cache_size = 7 * 4096
132    self.assertEqual(0, block_image_diff.ReviseStashSize())
133
134    # Insufficient cache to stash 5 blocks (size * 0.8 < 5).
135    common.OPTIONS.cache_size = 6 * 4096
136    self.assertEqual(10, block_image_diff.ReviseStashSize())
137
138  def test_ReviseStashSize_bug_33687949(self):
139    """ReviseStashSize() should "free" the used stash _after_ the command.
140
141    t1: diff <1-5> => <11-15>
142    t2: diff <11-15> => <21-25>
143    t3: diff <11-15 30-39> => <1-5 30-39>
144
145    For transfer t3, the used stash "11-15" should not be freed until the
146    command finishes. Assume the allowed cache size is 12-block, it should
147    convert the command to 'new' due to insufficient cache (12 < 5 + 10).
148    """
149
150    src = EmptyImage()
151    tgt = EmptyImage()
152    block_image_diff = BlockImageDiff(tgt, src, version=3)
153
154    transfers = block_image_diff.transfers
155    t1 = Transfer("t1", "t1", RangeSet("11-15"), RangeSet("1-5"), "t1hash",
156                  "t1hash", "diff", transfers)
157    t2 = Transfer("t2", "t2", RangeSet("21-25"), RangeSet("11-15"), "t2hash",
158                  "t2hash", "diff", transfers)
159    t3 = Transfer("t3", "t3", RangeSet("1-5 30-39"), RangeSet("11-15 30-39"),
160                  "t3hash", "t3hash", "diff", transfers)
161
162    block_image_diff.GenerateDigraph()
163
164    # Instead of calling FindVertexSequence() and ReverseBackwardEdges(), we
165    # just set up the stash_before and use_stash manually. Otherwise it will
166    # reorder the transfer, which makes testing ReviseStashSize() harder.
167    t1.stash_before.append((0, RangeSet("11-15")))
168    t2.use_stash.append((0, RangeSet("11-15")))
169    t1.stash_before.append((1, RangeSet("11-15")))
170    t3.use_stash.append((1, RangeSet("11-15")))
171
172    # Insufficient cache to stash 15 blocks (size * 0.8 < 15).
173    common.OPTIONS.cache_size = 15 * 4096
174    self.assertEqual(15, block_image_diff.ReviseStashSize())
175