1 //
2 // Copyright (C) 2020 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 #include <algorithm>
18 #include <vector>
19
20 #include <gtest/gtest.h>
21
22 #include "update_engine/payload_consumer/payload_constants.h"
23 #include "update_engine/payload_generator/extent_ranges.h"
24 #include "update_engine/payload_generator/extent_utils.h"
25 #include "update_engine/payload_generator/merge_sequence_generator.h"
26
27 namespace chromeos_update_engine {
28 class MergeSequenceGeneratorTest : public ::testing::Test {
29 protected:
VerifyTransfers(MergeSequenceGenerator * generator,const std::vector<CowMergeOperation> & expected)30 void VerifyTransfers(MergeSequenceGenerator* generator,
31 const std::vector<CowMergeOperation>& expected) {
32 ASSERT_EQ(expected, generator->operations_);
33 }
34
FindDependency(std::vector<CowMergeOperation> transfers,std::map<CowMergeOperation,std::set<CowMergeOperation>> * result)35 void FindDependency(
36 std::vector<CowMergeOperation> transfers,
37 std::map<CowMergeOperation, std::set<CowMergeOperation>>* result) {
38 std::sort(transfers.begin(), transfers.end());
39 MergeSequenceGenerator generator(std::move(transfers));
40 ASSERT_TRUE(generator.FindDependency(result));
41 }
42
GenerateSequence(std::vector<CowMergeOperation> transfers,const std::vector<CowMergeOperation> & expected)43 void GenerateSequence(std::vector<CowMergeOperation> transfers,
44 const std::vector<CowMergeOperation>& expected) {
45 std::sort(transfers.begin(), transfers.end());
46 MergeSequenceGenerator generator(std::move(transfers));
47 std::vector<CowMergeOperation> sequence;
48 ASSERT_TRUE(generator.Generate(&sequence));
49 ASSERT_EQ(expected, sequence);
50 }
51 };
52
TEST_F(MergeSequenceGeneratorTest,Create)53 TEST_F(MergeSequenceGeneratorTest, Create) {
54 std::vector<AnnotatedOperation> aops{{"file1", {}}, {"file2", {}}};
55 aops[0].op.set_type(InstallOperation::SOURCE_COPY);
56 *aops[0].op.add_src_extents() = ExtentForRange(10, 10);
57 *aops[0].op.add_dst_extents() = ExtentForRange(30, 10);
58
59 aops[1].op.set_type(InstallOperation::SOURCE_COPY);
60 *aops[1].op.add_src_extents() = ExtentForRange(20, 10);
61 *aops[1].op.add_dst_extents() = ExtentForRange(40, 10);
62
63 auto generator = MergeSequenceGenerator::Create(aops);
64 ASSERT_TRUE(generator);
65 std::vector<CowMergeOperation> expected = {
66 CreateCowMergeOperation(ExtentForRange(10, 10), ExtentForRange(30, 10)),
67 CreateCowMergeOperation(ExtentForRange(20, 10), ExtentForRange(40, 10))};
68 VerifyTransfers(generator.get(), expected);
69
70 *aops[1].op.add_src_extents() = ExtentForRange(30, 5);
71 *aops[1].op.add_dst_extents() = ExtentForRange(50, 5);
72 generator = MergeSequenceGenerator::Create(aops);
73 ASSERT_FALSE(generator);
74 }
75
TEST_F(MergeSequenceGeneratorTest,Create_SplitSource)76 TEST_F(MergeSequenceGeneratorTest, Create_SplitSource) {
77 InstallOperation op;
78 op.set_type(InstallOperation::SOURCE_COPY);
79 *(op.add_src_extents()) = ExtentForRange(2, 3);
80 *(op.add_src_extents()) = ExtentForRange(6, 1);
81 *(op.add_src_extents()) = ExtentForRange(8, 4);
82 *(op.add_dst_extents()) = ExtentForRange(10, 8);
83
84 AnnotatedOperation aop{"file1", op};
85 auto generator = MergeSequenceGenerator::Create({aop});
86 ASSERT_TRUE(generator);
87 std::vector<CowMergeOperation> expected = {
88 CreateCowMergeOperation(ExtentForRange(2, 3), ExtentForRange(10, 3)),
89 CreateCowMergeOperation(ExtentForRange(6, 1), ExtentForRange(13, 1)),
90 CreateCowMergeOperation(ExtentForRange(8, 4), ExtentForRange(14, 4))};
91 VerifyTransfers(generator.get(), expected);
92 }
93
TEST_F(MergeSequenceGeneratorTest,FindDependency)94 TEST_F(MergeSequenceGeneratorTest, FindDependency) {
95 std::vector<CowMergeOperation> transfers = {
96 CreateCowMergeOperation(ExtentForRange(10, 10), ExtentForRange(15, 10)),
97 CreateCowMergeOperation(ExtentForRange(40, 10), ExtentForRange(50, 10)),
98 };
99
100 std::map<CowMergeOperation, std::set<CowMergeOperation>> merge_after;
101 FindDependency(transfers, &merge_after);
102 ASSERT_EQ(std::set<CowMergeOperation>(), merge_after.at(transfers[0]));
103 ASSERT_EQ(std::set<CowMergeOperation>(), merge_after.at(transfers[1]));
104
105 transfers = {
106 CreateCowMergeOperation(ExtentForRange(10, 10), ExtentForRange(25, 10)),
107 CreateCowMergeOperation(ExtentForRange(24, 5), ExtentForRange(35, 5)),
108 CreateCowMergeOperation(ExtentForRange(30, 10), ExtentForRange(15, 10)),
109 };
110
111 FindDependency(transfers, &merge_after);
112 ASSERT_EQ(std::set<CowMergeOperation>({transfers[2]}),
113 merge_after.at(transfers[0]));
114 ASSERT_EQ(std::set<CowMergeOperation>({transfers[0], transfers[2]}),
115 merge_after.at(transfers[1]));
116 ASSERT_EQ(std::set<CowMergeOperation>({transfers[0], transfers[1]}),
117 merge_after.at(transfers[2]));
118 }
119
TEST_F(MergeSequenceGeneratorTest,FindDependencyEdgeCase)120 TEST_F(MergeSequenceGeneratorTest, FindDependencyEdgeCase) {
121 std::vector<CowMergeOperation> transfers = {
122 CreateCowMergeOperation(ExtentForRange(10, 10), ExtentForRange(15, 10)),
123 CreateCowMergeOperation(ExtentForRange(40, 10), ExtentForRange(50, 10)),
124 CreateCowMergeOperation(ExtentForRange(59, 10), ExtentForRange(60, 10)),
125 };
126
127 std::map<CowMergeOperation, std::set<CowMergeOperation>> merge_after;
128 FindDependency(transfers, &merge_after);
129 ASSERT_EQ(std::set<CowMergeOperation>(), merge_after.at(transfers[0]));
130 ASSERT_EQ(std::set<CowMergeOperation>(), merge_after.at(transfers[1]));
131 ASSERT_EQ(merge_after[transfers[2]].size(), 1U);
132 }
133
TEST_F(MergeSequenceGeneratorTest,FindDependency_ReusedSourceBlocks)134 TEST_F(MergeSequenceGeneratorTest, FindDependency_ReusedSourceBlocks) {
135 std::vector<CowMergeOperation> transfers = {
136 CreateCowMergeOperation(ExtentForRange(5, 10), ExtentForRange(15, 10)),
137 CreateCowMergeOperation(ExtentForRange(6, 5), ExtentForRange(30, 5)),
138 CreateCowMergeOperation(ExtentForRange(50, 5), ExtentForRange(5, 5)),
139 };
140
141 std::map<CowMergeOperation, std::set<CowMergeOperation>> merge_after;
142 FindDependency(transfers, &merge_after);
143 ASSERT_EQ(std::set<CowMergeOperation>({transfers[2]}),
144 merge_after.at(transfers[0]));
145 ASSERT_EQ(std::set<CowMergeOperation>({transfers[2]}),
146 merge_after.at(transfers[1]));
147 }
148
TEST_F(MergeSequenceGeneratorTest,ValidateSequence)149 TEST_F(MergeSequenceGeneratorTest, ValidateSequence) {
150 std::vector<CowMergeOperation> transfers = {
151 CreateCowMergeOperation(ExtentForRange(10, 10), ExtentForRange(15, 10)),
152 CreateCowMergeOperation(ExtentForRange(30, 10), ExtentForRange(40, 10)),
153 };
154
155 // Self overlapping
156 ASSERT_TRUE(MergeSequenceGenerator::ValidateSequence(transfers));
157
158 transfers = {
159 CreateCowMergeOperation(ExtentForRange(30, 10), ExtentForRange(20, 10)),
160 CreateCowMergeOperation(ExtentForRange(15, 10), ExtentForRange(10, 10)),
161 };
162 ASSERT_FALSE(MergeSequenceGenerator::ValidateSequence(transfers));
163 }
164
TEST_F(MergeSequenceGeneratorTest,GenerateSequenceNoCycles)165 TEST_F(MergeSequenceGeneratorTest, GenerateSequenceNoCycles) {
166 std::vector<CowMergeOperation> transfers = {
167 CreateCowMergeOperation(ExtentForRange(10, 10), ExtentForRange(15, 10)),
168 // file3 should merge before file2
169 CreateCowMergeOperation(ExtentForRange(40, 5), ExtentForRange(25, 5)),
170 CreateCowMergeOperation(ExtentForRange(25, 10), ExtentForRange(30, 10)),
171 };
172
173 std::vector<CowMergeOperation> expected{
174 transfers[0], transfers[2], transfers[1]};
175 GenerateSequence(transfers, expected);
176 }
177
TEST_F(MergeSequenceGeneratorTest,GenerateSequenceWithCycles)178 TEST_F(MergeSequenceGeneratorTest, GenerateSequenceWithCycles) {
179 std::vector<CowMergeOperation> transfers = {
180 CreateCowMergeOperation(ExtentForRange(25, 10), ExtentForRange(30, 10)),
181 CreateCowMergeOperation(ExtentForRange(30, 10), ExtentForRange(40, 10)),
182 CreateCowMergeOperation(ExtentForRange(40, 10), ExtentForRange(25, 10)),
183 CreateCowMergeOperation(ExtentForRange(10, 10), ExtentForRange(15, 10)),
184 };
185
186 // file 1,2,3 form a cycle. And file3, whose dst ext has smallest offset, will
187 // be converted to raw blocks
188 std::vector<CowMergeOperation> expected{
189 transfers[3], transfers[1], transfers[0]};
190 GenerateSequence(transfers, expected);
191 }
192
TEST_F(MergeSequenceGeneratorTest,GenerateSequenceMultipleCycles)193 TEST_F(MergeSequenceGeneratorTest, GenerateSequenceMultipleCycles) {
194 std::vector<CowMergeOperation> transfers = {
195 // cycle 1
196 CreateCowMergeOperation(ExtentForRange(10, 10), ExtentForRange(25, 10)),
197 CreateCowMergeOperation(ExtentForRange(24, 5), ExtentForRange(35, 5)),
198 CreateCowMergeOperation(ExtentForRange(30, 10), ExtentForRange(15, 10)),
199 // cycle 2
200 CreateCowMergeOperation(ExtentForRange(55, 10), ExtentForRange(60, 10)),
201 CreateCowMergeOperation(ExtentForRange(60, 10), ExtentForRange(70, 10)),
202 CreateCowMergeOperation(ExtentForRange(70, 10), ExtentForRange(55, 10)),
203 };
204
205 // file 3, 6 will be converted to raw.
206 std::vector<CowMergeOperation> expected{
207 transfers[1], transfers[0], transfers[4], transfers[3]};
208 GenerateSequence(transfers, expected);
209 }
210
ValidateSplitSequence(const Extent & src_extent,const Extent & dst_extent)211 void ValidateSplitSequence(const Extent& src_extent, const Extent& dst_extent) {
212 std::vector<CowMergeOperation> sequence;
213 SplitSelfOverlapping(src_extent, dst_extent, &sequence);
214 ExtentRanges src_extent_set;
215 src_extent_set.AddExtent(src_extent);
216 ExtentRanges dst_extent_set;
217 dst_extent_set.AddExtent(dst_extent);
218
219 size_t src_block_count = 0;
220 size_t dst_block_count = 0;
221 std::cout << "src_extent: " << src_extent << " dst_extent: " << dst_extent
222 << '\n';
223 for (const auto& merge_op : sequence) {
224 src_extent_set.SubtractExtent(merge_op.src_extent());
225 dst_extent_set.SubtractExtent(merge_op.dst_extent());
226 src_block_count += merge_op.src_extent().num_blocks();
227 dst_block_count += merge_op.dst_extent().num_blocks();
228 std::cout << merge_op.src_extent() << " -> " << merge_op.dst_extent()
229 << '\n';
230 ASSERT_FALSE(ExtentRanges::ExtentsOverlap(merge_op.src_extent(),
231 merge_op.dst_extent()));
232 }
233 std::cout << '\n';
234 // Check that all blocks are covered
235 ASSERT_EQ(src_extent_set.extent_set().size(), 0UL);
236 ASSERT_EQ(dst_extent_set.extent_set().size(), 0UL);
237
238 // Check that the split didn't cover extra blocks
239 ASSERT_EQ(src_block_count, src_extent.num_blocks());
240 ASSERT_EQ(dst_block_count, dst_extent.num_blocks());
241 }
242
TEST_F(MergeSequenceGeneratorTest,SplitSelfOverlappingTest)243 TEST_F(MergeSequenceGeneratorTest, SplitSelfOverlappingTest) {
244 auto a = ExtentForRange(25, 16);
245 auto b = ExtentForRange(30, 16);
246 ValidateSplitSequence(a, b);
247 ValidateSplitSequence(b, a);
248 }
249
250 } // namespace chromeos_update_engine
251