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 <array>
19 #include <initializer_list>
20 
21 #include <gtest/gtest.h>
22 
23 #include "update_engine/common/cow_operation_convert.h"
24 #include "update_engine/payload_generator/extent_ranges.h"
25 #include "update_engine/update_metadata.pb.h"
26 
27 namespace chromeos_update_engine {
28 using OperationList = ::google::protobuf::RepeatedPtrField<
29     ::chromeos_update_engine::InstallOperation>;
30 using MergeOplist = ::google::protobuf::RepeatedPtrField<
31     ::chromeos_update_engine::CowMergeOperation>;
32 
operator <<(std::ostream & out,CowOperation::Type op)33 std::ostream& operator<<(std::ostream& out, CowOperation::Type op) {
34   switch (op) {
35     case CowOperation::Type::CowCopy:
36       out << "CowCopy";
37       break;
38     case CowOperation::Type::CowReplace:
39       out << "CowReplace";
40       break;
41     default:
42       out << op;
43       break;
44   }
45   return out;
46 }
47 
operator <<(std::ostream & out,const CowOperation & c)48 std::ostream& operator<<(std::ostream& out, const CowOperation& c) {
49   out << "{" << c.op << ", " << c.src_block << ", " << c.dst_block << ", "
50       << c.block_count << "}";
51   return out;
52 }
53 
54 class CowOperationConvertTest : public testing::Test {
55  public:
VerifyCowMergeOp(const std::vector<CowOperation> & cow_ops)56   void VerifyCowMergeOp(const std::vector<CowOperation>& cow_ops) {
57     // Build a set of all extents covered by InstallOps.
58     ExtentRanges src_extent_set;
59     ExtentRanges dst_extent_set;
60     for (auto&& op : operations_) {
61       src_extent_set.AddRepeatedExtents(op.src_extents());
62       dst_extent_set.AddRepeatedExtents(op.dst_extents());
63     }
64     ExtentRanges modified_extents;
65     for (auto&& cow_op : cow_ops) {
66       if (cow_op.op == CowOperation::CowCopy) {
67         for (size_t i = 0; i < cow_op.block_count; i++) {
68           ASSERT_TRUE(src_extent_set.ContainsBlock(cow_op.src_block + i));
69           // converted operations should be conflict free.
70           ASSERT_FALSE(modified_extents.ContainsBlock(cow_op.src_block + i))
71               << "SOURCE_COPY operation " << cow_op
72               << " read from a modified block";
73         }
74       }
75       for (size_t i = 0; i < cow_op.block_count; i++) {
76         ASSERT_TRUE(dst_extent_set.ContainsBlock(cow_op.dst_block + i));
77       }
78       dst_extent_set.SubtractExtent(
79           ExtentForRange(cow_op.dst_block, cow_op.block_count));
80       modified_extents.AddExtent(
81           ExtentForRange(cow_op.dst_block, cow_op.block_count));
82     }
83     // The generated CowOps should cover all extents in InstallOps.
84     ASSERT_EQ(dst_extent_set.blocks(), 0UL);
85     // It's possible that src_extent_set is non-empty, because some operations
86     // will be converted to CowReplace, and we don't count the source extent for
87     // those.
88   }
89   OperationList operations_;
90   MergeOplist merge_operations_;
91 };
92 
AddOperation(OperationList * operations,::chromeos_update_engine::InstallOperation_Type op_type,std::initializer_list<std::array<int,2>> src_extents,std::initializer_list<std::array<int,2>> dst_extents)93 void AddOperation(OperationList* operations,
94                   ::chromeos_update_engine::InstallOperation_Type op_type,
95                   std::initializer_list<std::array<int, 2>> src_extents,
96                   std::initializer_list<std::array<int, 2>> dst_extents) {
97   auto&& op = operations->Add();
98   op->set_type(op_type);
99   for (const auto& extent : src_extents) {
100     *op->add_src_extents() = ExtentForRange(extent[0], extent[1]);
101   }
102   for (const auto& extent : dst_extents) {
103     *op->add_dst_extents() = ExtentForRange(extent[0], extent[1]);
104   }
105 }
106 
AddMergeOperation(MergeOplist * operations,::chromeos_update_engine::CowMergeOperation_Type op_type,std::array<int,2> src_extent,std::array<int,2> dst_extent)107 void AddMergeOperation(MergeOplist* operations,
108                        ::chromeos_update_engine::CowMergeOperation_Type op_type,
109                        std::array<int, 2> src_extent,
110                        std::array<int, 2> dst_extent) {
111   auto&& op = operations->Add();
112   op->set_type(op_type);
113   *op->mutable_src_extent() = ExtentForRange(src_extent[0], src_extent[1]);
114   *op->mutable_dst_extent() = ExtentForRange(dst_extent[0], dst_extent[1]);
115 }
116 
TEST_F(CowOperationConvertTest,NoConflict)117 TEST_F(CowOperationConvertTest, NoConflict) {
118   AddOperation(
119       &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{30, 1}});
120   AddOperation(
121       &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{20, 1}});
122   AddOperation(
123       &operations_, InstallOperation::SOURCE_COPY, {{0, 1}}, {{10, 1}});
124 
125   AddMergeOperation(
126       &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {30, 1});
127   AddMergeOperation(
128       &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {20, 1});
129   AddMergeOperation(
130       &merge_operations_, CowMergeOperation::COW_COPY, {0, 1}, {10, 1});
131 
132   auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
133   ASSERT_EQ(cow_ops.size(), 3UL);
134   ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) {
135     return cow_op.op == CowOperation::CowCopy;
136   }));
137   VerifyCowMergeOp(cow_ops);
138 }
139 
TEST_F(CowOperationConvertTest,CowReplace)140 TEST_F(CowOperationConvertTest, CowReplace) {
141   AddOperation(
142       &operations_, InstallOperation::SOURCE_COPY, {{30, 1}}, {{0, 1}});
143   AddOperation(
144       &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{30, 1}});
145   AddOperation(
146       &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{20, 1}});
147   AddOperation(
148       &operations_, InstallOperation::SOURCE_COPY, {{0, 1}}, {{10, 1}});
149 
150   AddMergeOperation(
151       &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {30, 1});
152   AddMergeOperation(
153       &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {20, 1});
154   AddMergeOperation(
155       &merge_operations_, CowMergeOperation::COW_COPY, {0, 1}, {10, 1});
156 
157   auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
158   ASSERT_EQ(cow_ops.size(), 4UL);
159   // Expect 3 COW_COPY and 1 COW_REPLACE
160   ASSERT_EQ(std::count_if(cow_ops.begin(),
161                           cow_ops.end(),
162                           [](auto&& cow_op) {
163                             return cow_op.op == CowOperation::CowCopy;
164                           }),
165             3);
166   ASSERT_EQ(std::count_if(cow_ops.begin(),
167                           cow_ops.end(),
168                           [](auto&& cow_op) {
169                             return cow_op.op == CowOperation::CowReplace;
170                           }),
171             1);
172   VerifyCowMergeOp(cow_ops);
173 }
174 
TEST_F(CowOperationConvertTest,ReOrderSourceCopy)175 TEST_F(CowOperationConvertTest, ReOrderSourceCopy) {
176   AddOperation(
177       &operations_, InstallOperation::SOURCE_COPY, {{30, 1}}, {{20, 1}});
178   AddOperation(
179       &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{10, 1}});
180   AddOperation(
181       &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{0, 1}});
182 
183   AddMergeOperation(
184       &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {0, 1});
185   AddMergeOperation(
186       &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {10, 1});
187   AddMergeOperation(
188       &merge_operations_, CowMergeOperation::COW_COPY, {30, 1}, {20, 1});
189 
190   auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
191   ASSERT_EQ(cow_ops.size(), 3UL);
192   // Expect 3 COW_COPY
193   ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) {
194     return cow_op.op == CowOperation::CowCopy;
195   }));
196   VerifyCowMergeOp(cow_ops);
197 }
198 
TEST_F(CowOperationConvertTest,InterleavingSrcExtent)199 TEST_F(CowOperationConvertTest, InterleavingSrcExtent) {
200   AddOperation(&operations_,
201                InstallOperation::SOURCE_COPY,
202                {{30, 5}, {35, 5}},
203                {{20, 10}});
204   AddOperation(
205       &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{10, 1}});
206   AddOperation(
207       &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{0, 1}});
208 
209   AddMergeOperation(
210       &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {0, 1});
211   AddMergeOperation(
212       &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {10, 1});
213   AddMergeOperation(
214       &merge_operations_, CowMergeOperation::COW_COPY, {30, 5}, {20, 5});
215   AddMergeOperation(
216       &merge_operations_, CowMergeOperation::COW_COPY, {35, 5}, {25, 5});
217 
218   auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
219   // Expect 4 COW_COPY
220   ASSERT_EQ(cow_ops.size(), 12UL);
221   ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) {
222     return cow_op.op == CowOperation::CowCopy;
223   }));
224   VerifyCowMergeOp(cow_ops);
225 }
226 
TEST_F(CowOperationConvertTest,SelfOverlappingOperation)227 TEST_F(CowOperationConvertTest, SelfOverlappingOperation) {
228   AddOperation(
229       &operations_, InstallOperation::SOURCE_COPY, {{20, 10}}, {{25, 10}});
230 
231   AddMergeOperation(
232       &merge_operations_, CowMergeOperation::COW_COPY, {20, 10}, {25, 10});
233 
234   auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
235   // Expect 10 COW_COPY
236   ASSERT_EQ(cow_ops.size(), 10UL);
237   ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) {
238     return cow_op.op == CowOperation::CowCopy;
239   }));
240   VerifyCowMergeOp(cow_ops);
241 }
242 
TEST_F(CowOperationConvertTest,CowReplaceCoalesce)243 TEST_F(CowOperationConvertTest, CowReplaceCoalesce) {
244   AddOperation(
245       &operations_, InstallOperation::SOURCE_COPY, {{30, 10}}, {{0, 10}});
246 
247   AddMergeOperation(
248       &merge_operations_, CowMergeOperation::COW_COPY, {30, 1}, {0, 1});
249   AddMergeOperation(
250       &merge_operations_, CowMergeOperation::COW_COPY, {31, 1}, {1, 1});
251   AddMergeOperation(
252       &merge_operations_, CowMergeOperation::COW_COPY, {32, 1}, {2, 1});
253 
254   auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
255   for (const auto& op : cow_ops) {
256     LOG(INFO) << op;
257   }
258   ASSERT_EQ(cow_ops.size(), 4UL);
259   // Expect 3 COW_COPY and 1 COW_REPLACE
260   ASSERT_EQ(std::count_if(cow_ops.begin(),
261                           cow_ops.end(),
262                           [](auto&& cow_op) {
263                             return cow_op.op == CowOperation::CowCopy;
264                           }),
265             3);
266   ASSERT_EQ(std::count_if(cow_ops.begin(),
267                           cow_ops.end(),
268                           [](auto&& cow_op) {
269                             return cow_op.op == CowOperation::CowReplace;
270                           }),
271             1);
272   VerifyCowMergeOp(cow_ops);
273 }
274 
TEST_F(CowOperationConvertTest,CowReplaceDifferenceSrc)275 TEST_F(CowOperationConvertTest, CowReplaceDifferenceSrc) {
276   AddOperation(
277       &operations_, InstallOperation::SOURCE_COPY, {{30, 10}}, {{0, 10}});
278   AddOperation(
279       &operations_, InstallOperation::SOURCE_COPY, {{100, 10}}, {{10, 10}});
280 
281   auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
282   for (const auto& op : cow_ops) {
283     LOG(INFO) << op;
284   }
285   ASSERT_EQ(cow_ops.size(), 2UL);
286   // |src_block| matters. Even for ReplaceOperation.
287   // As update_engine still need to know where the data come from.
288   ASSERT_EQ(cow_ops[0].op, CowOperation::CowReplace);
289   ASSERT_EQ(cow_ops[0].src_block, 30UL);
290   ASSERT_EQ(cow_ops[0].dst_block, 0UL);
291   ASSERT_EQ(cow_ops[0].block_count, 10UL);
292 
293   ASSERT_EQ(cow_ops[1].op, CowOperation::CowReplace);
294   ASSERT_EQ(cow_ops[1].src_block, 100UL);
295   ASSERT_EQ(cow_ops[1].dst_block, 10UL);
296   ASSERT_EQ(cow_ops[1].block_count, 10UL);
297   VerifyCowMergeOp(cow_ops);
298 }
299 
300 }  // namespace chromeos_update_engine
301