test_blockimgdiff.py revision 304ee27e889d0b16c66a9b5d2faed379f8cad627 
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 common
20import unittest
21
22from blockimgdiff import BlockImageDiff, EmptyImage, Transfer
23from rangelib import RangeSet
24
25class BlockImageDiffTest(unittest.TestCase):
26
27  def test_GenerateDigraphOrder(self):
28    """Make sure GenerateDigraph preserves the order.
29
30    t0: <0-5> => <...>
31    t1: <0-7> => <...>
32    t2: <0-4> => <...>
33    t3: <...> => <0-10>
34
35    t0, t1 and t2 must go before t3, i.e. t3.goes_after =
36    { t0:..., t1:..., t2:... }. But the order of t0-t2 must be preserved.
37    """
38
39    src = EmptyImage()
40    tgt = EmptyImage()
41    block_image_diff = BlockImageDiff(tgt, src)
42
43    transfers = block_image_diff.transfers
44    t0 = Transfer(
45        "t1", "t1", RangeSet("10-15"), RangeSet("0-5"), "move", transfers)
46    t1 = Transfer(
47        "t2", "t2", RangeSet("20-25"), RangeSet("0-7"), "move", transfers)
48    t2 = Transfer(
49        "t3", "t3", RangeSet("30-35"), RangeSet("0-4"), "move", transfers)
50    t3 = Transfer(
51        "t4", "t4", RangeSet("0-10"), RangeSet("40-50"), "move", transfers)
52
53    block_image_diff.GenerateDigraph()
54    t3_goes_after_copy = t3.goes_after.copy()
55
56    # Elements in the set must be in the transfer evaluation order.
57    elements = list(t3_goes_after_copy)
58    self.assertEqual(t0, elements[0])
59    self.assertEqual(t1, elements[1])
60    self.assertEqual(t2, elements[2])
61
62    # Now switch the order of t0, t1 and t2.
63    transfers[0], transfers[1], transfers[2] = (
64        transfers[2], transfers[0], transfers[1])
65    t3.goes_after.clear()
66    t3.goes_before.clear()
67    block_image_diff.GenerateDigraph()
68
69    # The goes_after must be different from last run.
70    self.assertNotEqual(t3_goes_after_copy, t3.goes_after)
71
72    # Assert that each element must agree with the transfer order.
73    elements = list(t3.goes_after)
74    self.assertEqual(t2, elements[0])
75    self.assertEqual(t0, elements[1])
76    self.assertEqual(t1, elements[2])
77
78  def test_ReviseStashSize(self):
79    """ReviseStashSize should convert transfers to 'new' commands as needed.
80
81    t1: diff <20-29> => <11-15>
82    t2: diff <11-15> => <20-29>
83    """
84
85    src = EmptyImage()
86    tgt = EmptyImage()
87    block_image_diff = BlockImageDiff(tgt, src, version=3)
88
89    transfers = block_image_diff.transfers
90    Transfer("t1", "t1", RangeSet("11-15"), RangeSet("20-29"), "diff",
91             transfers)
92    Transfer("t2", "t2", RangeSet("20-29"), RangeSet("11-15"), "diff",
93             transfers)
94
95    block_image_diff.GenerateDigraph()
96    block_image_diff.FindVertexSequence()
97    block_image_diff.ReverseBackwardEdges()
98
99    # Sufficient cache to stash 5 blocks (size * 0.8 >= 5).
100    common.OPTIONS.cache_size = 7 * 4096
101    self.assertEqual(0, block_image_diff.ReviseStashSize())
102
103    # Insufficient cache to stash 5 blocks (size * 0.8 < 5).
104    common.OPTIONS.cache_size = 6 * 4096
105    self.assertEqual(10, block_image_diff.ReviseStashSize())
106
107  def test_ReviseStashSize_bug_33687949(self):
108    """ReviseStashSize() should "free" the used stash _after_ the command.
109
110    t1: diff <1-5> => <11-15>
111    t2: diff <11-15> => <21-25>
112    t3: diff <11-15 30-39> => <1-5 30-39>
113
114    For transfer t3, the used stash "11-15" should not be freed until the
115    command finishes. Assume the allowed cache size is 12-block, it should
116    convert the command to 'new' due to insufficient cache (12 < 5 + 10).
117    """
118
119    src = EmptyImage()
120    tgt = EmptyImage()
121    block_image_diff = BlockImageDiff(tgt, src, version=3)
122
123    transfers = block_image_diff.transfers
124    t1 = Transfer("t1", "t1", RangeSet("11-15"), RangeSet("1-5"), "diff",
125                  transfers)
126    t2 = Transfer("t2", "t2", RangeSet("21-25"), RangeSet("11-15"), "diff",
127                  transfers)
128    t3 = Transfer("t3", "t3", RangeSet("1-5 30-39"), RangeSet("11-15 30-39"),
129                  "diff", transfers)
130
131    block_image_diff.GenerateDigraph()
132
133    # Instead of calling FindVertexSequence() and ReverseBackwardEdges(), we
134    # just set up the stash_before and use_stash manually. Otherwise it will
135    # reorder the transfer, which makes testing ReviseStashSize() harder.
136    t1.stash_before.append((0, RangeSet("11-15")))
137    t2.use_stash.append((0, RangeSet("11-15")))
138    t1.stash_before.append((1, RangeSet("11-15")))
139    t3.use_stash.append((1, RangeSet("11-15")))
140
141    # Insufficient cache to stash 15 blocks (size * 0.8 < 15).
142    common.OPTIONS.cache_size = 15 * 4096
143    self.assertEqual(15, block_image_diff.ReviseStashSize())
144