• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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