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 17 from __future__ import print_function 18 19 import common 20 import unittest 21 22 from blockimgdiff import BlockImageDiff, EmptyImage, Transfer 23 from rangelib import RangeSet 24 25 class 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("t1", "t1", RangeSet("10-15"), RangeSet("0-5"), "t1hash", 45 "t1hash", "move", transfers) 46 t1 = Transfer("t2", "t2", RangeSet("20-25"), RangeSet("0-7"), "t2hash", 47 "t2hash", "move", transfers) 48 t2 = Transfer("t3", "t3", RangeSet("30-35"), RangeSet("0-4"), "t3hash", 49 "t3hash", "move", transfers) 50 t3 = Transfer("t4", "t4", RangeSet("0-10"), RangeSet("40-50"), "t4hash", 51 "t4hash", "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"), "t1hash", 91 "t1hash", "diff", transfers) 92 Transfer("t2", "t2", RangeSet("20-29"), RangeSet("11-15"), "t2hash", 93 "t2hash", "diff", 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"), "t1hash", 125 "t1hash", "diff", transfers) 126 t2 = Transfer("t2", "t2", RangeSet("21-25"), RangeSet("11-15"), "t2hash", 127 "t2hash", "diff", transfers) 128 t3 = Transfer("t3", "t3", RangeSet("1-5 30-39"), RangeSet("11-15 30-39"), 129 "t3hash", "t3hash", "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
