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