1 // Copyright (C) 2018 The Android Open Source Project
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //      http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include <optional>
16 #include <tuple>
17 
18 #include <gmock/gmock.h>
19 #include <gtest/gtest.h>
20 #include <libdm/dm.h>
21 #include <liblp/builder.h>
22 #include <liblp/property_fetcher.h>
23 
24 #include <libsnapshot/test_helpers.h>
25 
26 #include "dm_snapshot_internals.h"
27 #include "partition_cow_creator.h"
28 #include "utility.h"
29 
30 using namespace android::fs_mgr;
31 
32 using chromeos_update_engine::InstallOperation;
33 using UeExtent = chromeos_update_engine::Extent;
34 using google::protobuf::RepeatedPtrField;
35 using ::testing::Matches;
36 using ::testing::Pointwise;
37 using ::testing::Truly;
38 
39 namespace android {
40 namespace snapshot {
41 
42 // @VsrTest = 3.7.6
43 class PartitionCowCreatorTest : public ::testing::Test {
44   public:
SetUp()45     void SetUp() override {
46         SKIP_IF_NON_VIRTUAL_AB();
47         SnapshotTestPropertyFetcher::SetUp();
48     }
TearDown()49     void TearDown() override {
50         RETURN_IF_NON_VIRTUAL_AB();
51         SnapshotTestPropertyFetcher::TearDown();
52     }
53 };
54 
TEST_F(PartitionCowCreatorTest,IntersectSelf)55 TEST_F(PartitionCowCreatorTest, IntersectSelf) {
56     constexpr uint64_t super_size = 1_MiB;
57     constexpr uint64_t partition_size = 40_KiB;
58 
59     auto builder_a = MetadataBuilder::New(super_size, 1_KiB, 2);
60     ASSERT_NE(builder_a, nullptr);
61     auto system_a = builder_a->AddPartition("system_a", LP_PARTITION_ATTR_READONLY);
62     ASSERT_NE(system_a, nullptr);
63     ASSERT_TRUE(builder_a->ResizePartition(system_a, partition_size));
64 
65     auto builder_b = MetadataBuilder::New(super_size, 1_KiB, 2);
66     ASSERT_NE(builder_b, nullptr);
67     auto system_b = builder_b->AddPartition("system_b", LP_PARTITION_ATTR_READONLY);
68     ASSERT_NE(system_b, nullptr);
69     ASSERT_TRUE(builder_b->ResizePartition(system_b, partition_size));
70 
71     PartitionCowCreator creator{.target_metadata = builder_b.get(),
72                                 .target_suffix = "_b",
73                                 .target_partition = system_b,
74                                 .current_metadata = builder_a.get(),
75                                 .current_suffix = "_a"};
76     auto ret = creator.Run();
77     ASSERT_TRUE(ret.has_value());
78     ASSERT_EQ(partition_size, ret->snapshot_status.device_size());
79     ASSERT_EQ(partition_size, ret->snapshot_status.snapshot_size());
80 }
81 
TEST_F(PartitionCowCreatorTest,Holes)82 TEST_F(PartitionCowCreatorTest, Holes) {
83     const auto& opener = test_device->GetPartitionOpener();
84 
85     constexpr auto slack_space = 1_MiB;
86     constexpr auto big_size = (kSuperSize - slack_space) / 2;
87     constexpr auto small_size = big_size / 2;
88 
89     BlockDeviceInfo super_device("super", kSuperSize, 0, 0, 4_KiB);
90     std::vector<BlockDeviceInfo> devices = {super_device};
91     auto source = MetadataBuilder::New(devices, "super", 1_KiB, 2);
92     auto system = source->AddPartition("system_a", 0);
93     ASSERT_NE(nullptr, system);
94     ASSERT_TRUE(source->ResizePartition(system, big_size));
95     auto vendor = source->AddPartition("vendor_a", 0);
96     ASSERT_NE(nullptr, vendor);
97     ASSERT_TRUE(source->ResizePartition(vendor, big_size));
98     // Create a hole between system and vendor
99     ASSERT_TRUE(source->ResizePartition(system, small_size));
100     auto source_metadata = source->Export();
101     ASSERT_NE(nullptr, source_metadata);
102     ASSERT_TRUE(FlashPartitionTable(opener, fake_super, *source_metadata.get()));
103 
104     auto target = MetadataBuilder::NewForUpdate(opener, "super", 0, 1);
105     // Shrink vendor
106     vendor = target->FindPartition("vendor_b");
107     ASSERT_NE(nullptr, vendor);
108     ASSERT_TRUE(target->ResizePartition(vendor, small_size));
109     // Grow system to take hole & saved space from vendor
110     system = target->FindPartition("system_b");
111     ASSERT_NE(nullptr, system);
112     ASSERT_TRUE(target->ResizePartition(system, big_size * 2 - small_size));
113 
114     PartitionCowCreator creator{.target_metadata = target.get(),
115                                 .target_suffix = "_b",
116                                 .target_partition = system,
117                                 .current_metadata = source.get(),
118                                 .current_suffix = "_a"};
119     auto ret = creator.Run();
120     ASSERT_TRUE(ret.has_value());
121 }
122 
TEST_F(PartitionCowCreatorTest,CowSize)123 TEST_F(PartitionCowCreatorTest, CowSize) {
124     using InstallOperation = chromeos_update_engine::InstallOperation;
125     using RepeatedInstallOperationPtr = google::protobuf::RepeatedPtrField<InstallOperation>;
126     using Extent = chromeos_update_engine::Extent;
127 
128     constexpr uint64_t super_size = 50_MiB;
129     constexpr uint64_t partition_size = 40_MiB;
130 
131     auto builder_a = MetadataBuilder::New(super_size, 1_KiB, 2);
132     ASSERT_NE(builder_a, nullptr);
133     auto system_a = builder_a->AddPartition("system_a", LP_PARTITION_ATTR_READONLY);
134     ASSERT_NE(system_a, nullptr);
135     ASSERT_TRUE(builder_a->ResizePartition(system_a, partition_size));
136 
137     auto builder_b = MetadataBuilder::New(super_size, 1_KiB, 2);
138     ASSERT_NE(builder_b, nullptr);
139     auto system_b = builder_b->AddPartition("system_b", LP_PARTITION_ATTR_READONLY);
140     ASSERT_NE(system_b, nullptr);
141     ASSERT_TRUE(builder_b->ResizePartition(system_b, partition_size));
142 
143     const uint64_t block_size = builder_b->logical_block_size();
144     const uint64_t chunk_size = kSnapshotChunkSize * dm::kSectorSize;
145     ASSERT_EQ(chunk_size, block_size);
146 
147     auto cow_device_size = [](const std::vector<InstallOperation>& iopv, MetadataBuilder* builder_a,
148                               MetadataBuilder* builder_b, Partition* system_b) {
149         PartitionUpdate update;
150         *update.mutable_operations() = RepeatedInstallOperationPtr(iopv.begin(), iopv.end());
151 
152         PartitionCowCreator creator{.target_metadata = builder_b,
153                                     .target_suffix = "_b",
154                                     .target_partition = system_b,
155                                     .current_metadata = builder_a,
156                                     .current_suffix = "_a",
157                                     .update = &update};
158 
159         auto ret = creator.Run();
160 
161         if (ret.has_value()) {
162             return ret->snapshot_status.cow_file_size() + ret->snapshot_status.cow_partition_size();
163         }
164         return std::numeric_limits<uint64_t>::max();
165     };
166 
167     std::vector<InstallOperation> iopv;
168     InstallOperation iop;
169     Extent* e;
170 
171     // No data written, no operations performed
172     ASSERT_EQ(2 * chunk_size, cow_device_size(iopv, builder_a.get(), builder_b.get(), system_b));
173 
174     // No data written
175     e = iop.add_dst_extents();
176     e->set_start_block(0);
177     e->set_num_blocks(0);
178     iopv.push_back(iop);
179     ASSERT_EQ(2 * chunk_size, cow_device_size(iopv, builder_a.get(), builder_b.get(), system_b));
180 
181     e = iop.add_dst_extents();
182     e->set_start_block(1);
183     e->set_num_blocks(0);
184     iopv.push_back(iop);
185     ASSERT_EQ(2 * chunk_size, cow_device_size(iopv, builder_a.get(), builder_b.get(), system_b));
186 
187     // Fill the first block
188     e = iop.add_dst_extents();
189     e->set_start_block(0);
190     e->set_num_blocks(1);
191     iopv.push_back(iop);
192     ASSERT_EQ(3 * chunk_size, cow_device_size(iopv, builder_a.get(), builder_b.get(), system_b));
193 
194     // Fill the second block
195     e = iop.add_dst_extents();
196     e->set_start_block(1);
197     e->set_num_blocks(1);
198     iopv.push_back(iop);
199     ASSERT_EQ(4 * chunk_size, cow_device_size(iopv, builder_a.get(), builder_b.get(), system_b));
200 
201     // Jump to 5th block and write 2
202     e = iop.add_dst_extents();
203     e->set_start_block(5);
204     e->set_num_blocks(2);
205     iopv.push_back(iop);
206     ASSERT_EQ(6 * chunk_size, cow_device_size(iopv, builder_a.get(), builder_b.get(), system_b));
207 }
208 
TEST_F(PartitionCowCreatorTest,Zero)209 TEST_F(PartitionCowCreatorTest, Zero) {
210     constexpr uint64_t super_size = 1_MiB;
211     auto builder_a = MetadataBuilder::New(super_size, 1_KiB, 2);
212     ASSERT_NE(builder_a, nullptr);
213 
214     auto builder_b = MetadataBuilder::New(super_size, 1_KiB, 2);
215     ASSERT_NE(builder_b, nullptr);
216     auto system_b = builder_b->AddPartition("system_b", LP_PARTITION_ATTR_READONLY);
217     ASSERT_NE(system_b, nullptr);
218 
219     PartitionCowCreator creator{.target_metadata = builder_b.get(),
220                                 .target_suffix = "_b",
221                                 .target_partition = system_b,
222                                 .current_metadata = builder_a.get(),
223                                 .current_suffix = "_a",
224                                 .update = nullptr};
225 
226     auto ret = creator.Run();
227 
228     ASSERT_EQ(0u, ret->snapshot_status.device_size());
229     ASSERT_EQ(0u, ret->snapshot_status.snapshot_size());
230     ASSERT_EQ(0u, ret->snapshot_status.cow_file_size());
231     ASSERT_EQ(0u, ret->snapshot_status.cow_partition_size());
232 }
233 
TEST_F(PartitionCowCreatorTest,CompressionEnabled)234 TEST_F(PartitionCowCreatorTest, CompressionEnabled) {
235     constexpr uint64_t super_size = 1_MiB;
236     auto builder_a = MetadataBuilder::New(super_size, 1_KiB, 2);
237     ASSERT_NE(builder_a, nullptr);
238 
239     auto builder_b = MetadataBuilder::New(super_size, 1_KiB, 2);
240     ASSERT_NE(builder_b, nullptr);
241     auto system_b = builder_b->AddPartition("system_b", LP_PARTITION_ATTR_READONLY);
242     ASSERT_NE(system_b, nullptr);
243     ASSERT_TRUE(builder_b->ResizePartition(system_b, 128_KiB));
244 
245     PartitionUpdate update;
246     update.set_estimate_cow_size(256_KiB);
247 
248     PartitionCowCreator creator{.target_metadata = builder_b.get(),
249                                 .target_suffix = "_b",
250                                 .target_partition = system_b,
251                                 .current_metadata = builder_a.get(),
252                                 .current_suffix = "_a",
253                                 .using_snapuserd = true,
254                                 .update = &update};
255 
256     auto ret = creator.Run();
257     ASSERT_TRUE(ret.has_value());
258     ASSERT_EQ(ret->snapshot_status.cow_file_size(), 1458176);
259 }
260 
TEST_F(PartitionCowCreatorTest,CompressionWithNoManifest)261 TEST_F(PartitionCowCreatorTest, CompressionWithNoManifest) {
262     constexpr uint64_t super_size = 1_MiB;
263     auto builder_a = MetadataBuilder::New(super_size, 1_KiB, 2);
264     ASSERT_NE(builder_a, nullptr);
265 
266     auto builder_b = MetadataBuilder::New(super_size, 1_KiB, 2);
267     ASSERT_NE(builder_b, nullptr);
268     auto system_b = builder_b->AddPartition("system_b", LP_PARTITION_ATTR_READONLY);
269     ASSERT_NE(system_b, nullptr);
270     ASSERT_TRUE(builder_b->ResizePartition(system_b, 128_KiB));
271 
272     PartitionUpdate update;
273 
274     PartitionCowCreator creator{.target_metadata = builder_b.get(),
275                                 .target_suffix = "_b",
276                                 .target_partition = system_b,
277                                 .current_metadata = builder_a.get(),
278                                 .current_suffix = "_a",
279                                 .using_snapuserd = true,
280                                 .update = nullptr};
281 
282     auto ret = creator.Run();
283     ASSERT_FALSE(ret.has_value());
284 }
285 
TEST(DmSnapshotInternals,CowSizeCalculator)286 TEST(DmSnapshotInternals, CowSizeCalculator) {
287     SKIP_IF_NON_VIRTUAL_AB();
288 
289     DmSnapCowSizeCalculator cc(512, 8);
290     unsigned long int b;
291 
292     // Empty COW
293     ASSERT_EQ(cc.cow_size_sectors(), 16);
294 
295     // First chunk written
296     for (b = 0; b < 4_KiB; ++b) {
297         cc.WriteByte(b);
298         ASSERT_EQ(cc.cow_size_sectors(), 24);
299     }
300 
301     // Second chunk written
302     for (b = 4_KiB; b < 8_KiB; ++b) {
303         cc.WriteByte(b);
304         ASSERT_EQ(cc.cow_size_sectors(), 32);
305     }
306 
307     // Leave a hole and write 5th chunk
308     for (b = 16_KiB; b < 20_KiB; ++b) {
309         cc.WriteByte(b);
310         ASSERT_EQ(cc.cow_size_sectors(), 40);
311     }
312 
313     // Write a byte that would surely overflow the counter
314     cc.WriteChunk(std::numeric_limits<uint64_t>::max());
315     ASSERT_FALSE(cc.cow_size_sectors().has_value());
316 }
317 
BlocksToExtents(const std::vector<uint64_t> & blocks,google::protobuf::RepeatedPtrField<UeExtent> * extents)318 void BlocksToExtents(const std::vector<uint64_t>& blocks,
319                      google::protobuf::RepeatedPtrField<UeExtent>* extents) {
320     for (uint64_t block : blocks) {
321         AppendExtent(extents, block, 1);
322     }
323 }
324 
325 template <typename T>
ExtentsToBlocks(const T & extents)326 std::vector<uint64_t> ExtentsToBlocks(const T& extents) {
327     std::vector<uint64_t> blocks;
328     for (const auto& extent : extents) {
329         for (uint64_t offset = 0; offset < extent.num_blocks(); ++offset) {
330             blocks.push_back(extent.start_block() + offset);
331         }
332     }
333     return blocks;
334 }
335 
CreateCopyOp(const std::vector<uint64_t> & src_blocks,const std::vector<uint64_t> & dst_blocks)336 InstallOperation CreateCopyOp(const std::vector<uint64_t>& src_blocks,
337                               const std::vector<uint64_t>& dst_blocks) {
338     InstallOperation op;
339     op.set_type(InstallOperation::SOURCE_COPY);
340     BlocksToExtents(src_blocks, op.mutable_src_extents());
341     BlocksToExtents(dst_blocks, op.mutable_dst_extents());
342     return op;
343 }
344 
345 // ExtentEqual(tuple<UeExtent, UeExtent>)
346 MATCHER(ExtentEqual, "") {
347     auto&& [a, b] = arg;
348     return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
349 }
350 
351 struct OptimizeOperationTestParam {
352     InstallOperation input;
353     std::optional<InstallOperation> expected_output;
354 };
355 
356 class OptimizeOperationTest : public ::testing::TestWithParam<OptimizeOperationTestParam> {
SetUp()357     void SetUp() override { SKIP_IF_NON_VIRTUAL_AB(); }
358 };
TEST_P(OptimizeOperationTest,Test)359 TEST_P(OptimizeOperationTest, Test) {
360     InstallOperation actual_output;
361     EXPECT_EQ(GetParam().expected_output.has_value(),
362               OptimizeSourceCopyOperation(GetParam().input, &actual_output))
363             << "OptimizeSourceCopyOperation should "
364             << (GetParam().expected_output.has_value() ? "succeed" : "fail");
365     if (!GetParam().expected_output.has_value()) return;
366     EXPECT_THAT(actual_output.src_extents(),
367                 Pointwise(ExtentEqual(), GetParam().expected_output->src_extents()));
368     EXPECT_THAT(actual_output.dst_extents(),
369                 Pointwise(ExtentEqual(), GetParam().expected_output->dst_extents()));
370 }
371 
GetOptimizeOperationTestParams()372 std::vector<OptimizeOperationTestParam> GetOptimizeOperationTestParams() {
373     return {
374             {CreateCopyOp({}, {}), CreateCopyOp({}, {})},
375             {CreateCopyOp({1, 2, 4}, {1, 2, 4}), CreateCopyOp({}, {})},
376             {CreateCopyOp({1, 2, 3}, {4, 5, 6}), std::nullopt},
377             {CreateCopyOp({3, 2}, {1, 2}), CreateCopyOp({3}, {1})},
378             {CreateCopyOp({5, 6, 3, 4, 1, 2}, {1, 2, 3, 4, 5, 6}),
379              CreateCopyOp({5, 6, 1, 2}, {1, 2, 5, 6})},
380             {CreateCopyOp({1, 2, 3, 5, 5, 6}, {5, 6, 3, 4, 1, 2}),
381              CreateCopyOp({1, 2, 5, 5, 6}, {5, 6, 4, 1, 2})},
382             {CreateCopyOp({1, 2, 5, 6, 9, 10}, {1, 4, 5, 6, 7, 8}),
383              CreateCopyOp({2, 9, 10}, {4, 7, 8})},
384             {CreateCopyOp({2, 3, 3, 4, 4}, {1, 2, 3, 4, 5}), CreateCopyOp({2, 3, 4}, {1, 2, 5})},
385     };
386 }
387 
388 INSTANTIATE_TEST_CASE_P(Snapshot, OptimizeOperationTest,
389                         ::testing::ValuesIn(GetOptimizeOperationTestParams()));
390 
391 }  // namespace snapshot
392 }  // namespace android
393