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 return out;
51 }
52
53 class CowOperationConvertTest : public testing::Test {
54 public:
VerifyCowMergeOp(const std::vector<CowOperation> & cow_ops)55 void VerifyCowMergeOp(const std::vector<CowOperation>& cow_ops) {
56 // Build a set of all extents covered by InstallOps.
57 ExtentRanges src_extent_set;
58 ExtentRanges dst_extent_set;
59 for (auto&& op : operations_) {
60 src_extent_set.AddRepeatedExtents(op.src_extents());
61 dst_extent_set.AddRepeatedExtents(op.dst_extents());
62 }
63 ExtentRanges modified_extents;
64 for (auto&& cow_op : cow_ops) {
65 if (cow_op.op == CowOperation::CowCopy) {
66 EXPECT_TRUE(src_extent_set.ContainsBlock(cow_op.src_block));
67 // converted operations should be conflict free.
68 EXPECT_FALSE(modified_extents.ContainsBlock(cow_op.src_block))
69 << "SOURCE_COPY operation " << cow_op
70 << " read from a modified block";
71 }
72 EXPECT_TRUE(dst_extent_set.ContainsBlock(cow_op.dst_block));
73 dst_extent_set.SubtractExtent(ExtentForRange(cow_op.dst_block, 1));
74 modified_extents.AddBlock(cow_op.dst_block);
75 }
76 // The generated CowOps should cover all extents in InstallOps.
77 EXPECT_EQ(dst_extent_set.blocks(), 0UL);
78 // It's possible that src_extent_set is non-empty, because some operations
79 // will be converted to CowReplace, and we don't count the source extent for
80 // those.
81 }
82 OperationList operations_;
83 MergeOplist merge_operations_;
84 };
85
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)86 void AddOperation(OperationList* operations,
87 ::chromeos_update_engine::InstallOperation_Type op_type,
88 std::initializer_list<std::array<int, 2>> src_extents,
89 std::initializer_list<std::array<int, 2>> dst_extents) {
90 auto&& op = operations->Add();
91 op->set_type(op_type);
92 for (const auto& extent : src_extents) {
93 *op->add_src_extents() = ExtentForRange(extent[0], extent[1]);
94 }
95 for (const auto& extent : dst_extents) {
96 *op->add_dst_extents() = ExtentForRange(extent[0], extent[1]);
97 }
98 }
99
AddMergeOperation(MergeOplist * operations,::chromeos_update_engine::CowMergeOperation_Type op_type,std::array<int,2> src_extent,std::array<int,2> dst_extent)100 void AddMergeOperation(MergeOplist* operations,
101 ::chromeos_update_engine::CowMergeOperation_Type op_type,
102 std::array<int, 2> src_extent,
103 std::array<int, 2> dst_extent) {
104 auto&& op = operations->Add();
105 op->set_type(op_type);
106 *op->mutable_src_extent() = ExtentForRange(src_extent[0], src_extent[1]);
107 *op->mutable_dst_extent() = ExtentForRange(dst_extent[0], dst_extent[1]);
108 }
109
TEST_F(CowOperationConvertTest,NoConflict)110 TEST_F(CowOperationConvertTest, NoConflict) {
111 AddOperation(
112 &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{30, 1}});
113 AddOperation(
114 &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{20, 1}});
115 AddOperation(
116 &operations_, InstallOperation::SOURCE_COPY, {{0, 1}}, {{10, 1}});
117
118 AddMergeOperation(
119 &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {30, 1});
120 AddMergeOperation(
121 &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {20, 1});
122 AddMergeOperation(
123 &merge_operations_, CowMergeOperation::COW_COPY, {0, 1}, {10, 1});
124
125 auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
126 ASSERT_EQ(cow_ops.size(), 3UL);
127 ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) {
128 return cow_op.op == CowOperation::CowCopy;
129 }));
130 VerifyCowMergeOp(cow_ops);
131 }
132
TEST_F(CowOperationConvertTest,CowReplace)133 TEST_F(CowOperationConvertTest, CowReplace) {
134 AddOperation(
135 &operations_, InstallOperation::SOURCE_COPY, {{30, 1}}, {{0, 1}});
136 AddOperation(
137 &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{30, 1}});
138 AddOperation(
139 &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{20, 1}});
140 AddOperation(
141 &operations_, InstallOperation::SOURCE_COPY, {{0, 1}}, {{10, 1}});
142
143 AddMergeOperation(
144 &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {30, 1});
145 AddMergeOperation(
146 &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {20, 1});
147 AddMergeOperation(
148 &merge_operations_, CowMergeOperation::COW_COPY, {0, 1}, {10, 1});
149
150 auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
151 ASSERT_EQ(cow_ops.size(), 4UL);
152 // Expect 3 COW_COPY and 1 COW_REPLACE
153 ASSERT_EQ(std::count_if(cow_ops.begin(),
154 cow_ops.end(),
155 [](auto&& cow_op) {
156 return cow_op.op == CowOperation::CowCopy;
157 }),
158 3);
159 ASSERT_EQ(std::count_if(cow_ops.begin(),
160 cow_ops.end(),
161 [](auto&& cow_op) {
162 return cow_op.op == CowOperation::CowReplace;
163 }),
164 1);
165 VerifyCowMergeOp(cow_ops);
166 }
167
TEST_F(CowOperationConvertTest,ReOrderSourceCopy)168 TEST_F(CowOperationConvertTest, ReOrderSourceCopy) {
169 AddOperation(
170 &operations_, InstallOperation::SOURCE_COPY, {{30, 1}}, {{20, 1}});
171 AddOperation(
172 &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{10, 1}});
173 AddOperation(
174 &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{0, 1}});
175
176 AddMergeOperation(
177 &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {0, 1});
178 AddMergeOperation(
179 &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {10, 1});
180 AddMergeOperation(
181 &merge_operations_, CowMergeOperation::COW_COPY, {30, 1}, {20, 1});
182
183 auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
184 ASSERT_EQ(cow_ops.size(), 3UL);
185 // Expect 3 COW_COPY
186 ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) {
187 return cow_op.op == CowOperation::CowCopy;
188 }));
189 VerifyCowMergeOp(cow_ops);
190 }
191
TEST_F(CowOperationConvertTest,InterleavingSrcExtent)192 TEST_F(CowOperationConvertTest, InterleavingSrcExtent) {
193 AddOperation(&operations_,
194 InstallOperation::SOURCE_COPY,
195 {{30, 5}, {35, 5}},
196 {{20, 10}});
197 AddOperation(
198 &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{10, 1}});
199 AddOperation(
200 &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{0, 1}});
201
202 AddMergeOperation(
203 &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {0, 1});
204 AddMergeOperation(
205 &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {10, 1});
206 AddMergeOperation(
207 &merge_operations_, CowMergeOperation::COW_COPY, {30, 5}, {20, 5});
208 AddMergeOperation(
209 &merge_operations_, CowMergeOperation::COW_COPY, {35, 5}, {25, 5});
210
211 auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
212 // Expect 4 COW_COPY
213 ASSERT_EQ(cow_ops.size(), 12UL);
214 ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) {
215 return cow_op.op == CowOperation::CowCopy;
216 }));
217 VerifyCowMergeOp(cow_ops);
218 }
219
TEST_F(CowOperationConvertTest,SelfOverlappingOperation)220 TEST_F(CowOperationConvertTest, SelfOverlappingOperation) {
221 AddOperation(
222 &operations_, InstallOperation::SOURCE_COPY, {{20, 10}}, {{25, 10}});
223
224 AddMergeOperation(
225 &merge_operations_, CowMergeOperation::COW_COPY, {20, 10}, {25, 10});
226
227 auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
228 // Expect 10 COW_COPY
229 ASSERT_EQ(cow_ops.size(), 10UL);
230 ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) {
231 return cow_op.op == CowOperation::CowCopy;
232 }));
233 VerifyCowMergeOp(cow_ops);
234 }
235
236 } // namespace chromeos_update_engine
237