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 
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 
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:
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 
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 
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 
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 
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 
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 
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 
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