1 //
2 // Copyright (C) 2015 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 "update_engine/payload_generator/delta_diff_utils.h"
18
19 #include <algorithm>
20 #include <random>
21 #include <string>
22 #include <vector>
23
24 #include <base/files/scoped_file.h>
25 #include <base/format_macros.h>
26 #include <android-base/stringprintf.h>
27 #include <bsdiff/patch_writer.h>
28 #include <gtest/gtest.h>
29 #include <puffin/common.h>
30
31 #include "update_engine/payload_generator/deflate_utils.h"
32 #include "update_engine/payload_generator/filesystem_interface.h"
33 #include "update_engine/common/test_utils.h"
34 #include "update_engine/common/utils.h"
35 #include "update_engine/payload_generator/delta_diff_generator.h"
36 #include "update_engine/payload_generator/extent_ranges.h"
37 #include "update_engine/payload_generator/extent_utils.h"
38 #include "update_engine/payload_generator/fake_filesystem.h"
39
40 using std::string;
41 using std::vector;
42
43 namespace chromeos_update_engine {
44
45 namespace {
46
47 // Writes the |data| in the blocks specified by |extents| on the partition
48 // |part_path|. The |data| size could be smaller than the size of the blocks
49 // passed.
WriteExtents(const string & part_path,const vector<Extent> & extents,off_t block_size,const brillo::Blob & data)50 bool WriteExtents(const string& part_path,
51 const vector<Extent>& extents,
52 off_t block_size,
53 const brillo::Blob& data) {
54 uint64_t offset = 0;
55 base::ScopedFILE fp(fopen(part_path.c_str(), "r+"));
56 TEST_AND_RETURN_FALSE(fp.get());
57
58 for (const Extent& extent : extents) {
59 if (offset >= data.size())
60 break;
61 TEST_AND_RETURN_FALSE(
62 fseek(fp.get(), extent.start_block() * block_size, SEEK_SET) == 0);
63 uint64_t to_write =
64 std::min(static_cast<uint64_t>(extent.num_blocks()) * block_size,
65 static_cast<uint64_t>(data.size()) - offset);
66 TEST_AND_RETURN_FALSE(fwrite(data.data() + offset, 1, to_write, fp.get()) ==
67 to_write);
68 offset += extent.num_blocks() * block_size;
69 }
70 return true;
71 }
72
73 // Create a fake filesystem of the given |size| and initialize the partition
74 // holding it in the PartitionConfig |part|.
CreatePartition(PartitionConfig * part,ScopedTempFile * part_file,uint64_t block_size,off_t size)75 void CreatePartition(PartitionConfig* part,
76 ScopedTempFile* part_file,
77 uint64_t block_size,
78 off_t size) {
79 part->path = part_file->path();
80 ASSERT_EQ(0, ftruncate(part_file->fd(), size));
81 part_file->CloseFd();
82 part->fs_interface.reset(new FakeFilesystem(block_size, size / block_size));
83 part->size = size;
84 }
85
86 // Writes to the |partition| path blocks such they are all different and they
87 // include the tag passed in |tag|, making them also different to any other
88 // block on a partition initialized with this function with a different tag.
89 // The |block_size| should be a divisor of the partition size.
90 // Returns whether the function succeeded writing the partition.
InitializePartitionWithUniqueBlocks(const PartitionConfig & part,uint64_t block_size,uint64_t tag)91 bool InitializePartitionWithUniqueBlocks(const PartitionConfig& part,
92 uint64_t block_size,
93 uint64_t tag) {
94 TEST_AND_RETURN_FALSE(part.size % block_size == 0);
95 size_t num_blocks = part.size / block_size;
96 brillo::Blob file_data(part.size);
97 for (size_t i = 0; i < num_blocks; ++i) {
98 string prefix = android::base::StringPrintf(
99 "block tag 0x%.16" PRIx64 ", block number %16" PRIuS " ", tag, i);
100 brillo::Blob block_data(prefix.begin(), prefix.end());
101 TEST_AND_RETURN_FALSE(prefix.size() <= block_size);
102 block_data.resize(block_size, 'X');
103 std::copy(block_data.begin(),
104 block_data.end(),
105 file_data.begin() + i * block_size);
106 }
107 return test_utils::WriteFileVector(part.path, file_data);
108 }
109
110 } // namespace
111
112 class DeltaDiffUtilsTest : public ::testing::Test {
113 protected:
114 const uint64_t kDefaultBlockCount = 128;
115
SetUp()116 void SetUp() override {
117 CreatePartition(&old_part_,
118 &old_part_file_,
119 block_size_,
120 block_size_ * kDefaultBlockCount);
121 CreatePartition(&new_part_,
122 &new_part_file_,
123 block_size_,
124 block_size_ * kDefaultBlockCount);
125 }
126
127 // Helper function to call DeltaMovedAndZeroBlocks() using this class' data
128 // members. This simply avoids repeating all the arguments that never change.
RunDeltaMovedAndZeroBlocks(ssize_t chunk_blocks,uint32_t minor_version)129 bool RunDeltaMovedAndZeroBlocks(ssize_t chunk_blocks,
130 uint32_t minor_version) {
131 BlobFileWriter blob_file(tmp_blob_file_.fd(), &blob_size_);
132 PayloadVersion version(kBrilloMajorPayloadVersion, minor_version);
133 ExtentRanges old_zero_blocks;
134 return diff_utils::DeltaMovedAndZeroBlocks(&aops_,
135 old_part_.path,
136 new_part_.path,
137 old_part_.size / block_size_,
138 new_part_.size / block_size_,
139 chunk_blocks,
140 {.version = version},
141 &blob_file,
142 &old_visited_blocks_,
143 &new_visited_blocks_,
144 &old_zero_blocks);
145 }
146
147 // Old and new temporary partitions used in the tests. These are initialized
148 // with
149 PartitionConfig old_part_{"part"};
150 PartitionConfig new_part_{"part"};
151 ScopedTempFile old_part_file_{"DeltaDiffUtilsTest-old_part-XXXXXX", true};
152 ScopedTempFile new_part_file_{"DeltaDiffUtilsTest-new_part-XXXXXX", true};
153
154 // The file holding the output blob from the various diff utils functions.
155 ScopedTempFile tmp_blob_file_{"DeltaDiffUtilsTest-blob-XXXXXX", true};
156 off_t blob_size_{0};
157
158 size_t block_size_{kBlockSize};
159
160 // Default input/output arguments used when calling DeltaMovedAndZeroBlocks().
161 vector<AnnotatedOperation> aops_;
162 ExtentRanges old_visited_blocks_;
163 ExtentRanges new_visited_blocks_;
164 };
165
TEST_F(DeltaDiffUtilsTest,SkipVerityExtentsTest)166 TEST_F(DeltaDiffUtilsTest, SkipVerityExtentsTest) {
167 new_part_.verity.hash_tree_extent = ExtentForRange(20, 30);
168 new_part_.verity.fec_extent = ExtentForRange(40, 50);
169
170 BlobFileWriter blob_file(tmp_blob_file_.fd(), &blob_size_);
171 ASSERT_TRUE(diff_utils::DeltaReadPartition(
172 &aops_,
173 old_part_,
174 new_part_,
175 -1,
176 -1,
177 {.version = PayloadVersion(kMaxSupportedMajorPayloadVersion,
178 kVerityMinorPayloadVersion)},
179 &blob_file));
180 for (const auto& aop : aops_) {
181 new_visited_blocks_.AddRepeatedExtents(aop.op.dst_extents());
182 }
183 for (const auto& extent : new_visited_blocks_.extent_set()) {
184 ASSERT_FALSE(ExtentRanges::ExtentsOverlap(
185 extent, new_part_.verity.hash_tree_extent));
186 ASSERT_FALSE(
187 ExtentRanges::ExtentsOverlap(extent, new_part_.verity.fec_extent));
188 }
189 }
190
TEST_F(DeltaDiffUtilsTest,ReplaceSmallTest)191 TEST_F(DeltaDiffUtilsTest, ReplaceSmallTest) {
192 // The old file is on a different block than the new one.
193 vector<Extent> old_extents = {ExtentForRange(1, 1)};
194 vector<Extent> new_extents = {ExtentForRange(2, 1)};
195
196 // Make a blob that's just 1's that will compress well.
197 brillo::Blob ones(kBlockSize, 1);
198
199 // Make a blob with random data that won't compress well.
200 brillo::Blob random_data;
201 std::mt19937 gen(12345);
202 std::uniform_int_distribution<uint16_t> dis(0, 255);
203 for (uint32_t i = 0; i < kBlockSize; i++) {
204 random_data.push_back(static_cast<uint8_t>(dis(gen)));
205 }
206
207 for (int i = 0; i < 2; i++) {
208 brillo::Blob data_to_test = i == 0 ? random_data : ones;
209 // The old_extents will be initialized with 0.
210 ASSERT_TRUE(
211 WriteExtents(new_part_.path, new_extents, kBlockSize, data_to_test));
212
213 brillo::Blob data;
214 AnnotatedOperation aop;
215 InstallOperation& op = aop.op;
216 ASSERT_TRUE(diff_utils::ReadExtentsToDiff(
217 old_part_.path,
218 new_part_.path,
219 old_extents,
220 new_extents,
221 {}, // old_file
222 {}, // new_file
223 {.version = PayloadVersion(kBrilloMajorPayloadVersion,
224 kSourceMinorPayloadVersion)},
225 &data,
226 &aop));
227 ASSERT_FALSE(data.empty());
228
229 ASSERT_TRUE(op.has_type());
230 const InstallOperation::Type expected_type =
231 (i == 0 ? InstallOperation::REPLACE : InstallOperation::REPLACE_BZ);
232 ASSERT_EQ(expected_type, op.type());
233 ASSERT_FALSE(op.has_data_offset());
234 ASSERT_FALSE(op.has_data_length());
235 ASSERT_EQ(0, op.src_extents_size());
236 ASSERT_FALSE(op.has_src_length());
237 ASSERT_EQ(1, op.dst_extents_size());
238 ASSERT_FALSE(op.has_dst_length());
239 ASSERT_EQ(1U, utils::BlocksInExtents(op.dst_extents()));
240 }
241 }
242
TEST_F(DeltaDiffUtilsTest,SourceCopyTest)243 TEST_F(DeltaDiffUtilsTest, SourceCopyTest) {
244 // Makes sure SOURCE_COPY operations are emitted whenever src_ops_allowed
245 // is true. It is the same setup as MoveSmallTest, which checks that
246 // the operation is well-formed.
247 brillo::Blob data_blob(kBlockSize);
248 test_utils::FillWithData(&data_blob);
249
250 // The old file is on a different block than the new one.
251 vector<Extent> old_extents = {ExtentForRange(11, 1)};
252 vector<Extent> new_extents = {ExtentForRange(1, 1)};
253
254 ASSERT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
255 ASSERT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
256
257 brillo::Blob data;
258 AnnotatedOperation aop;
259 ASSERT_TRUE(diff_utils::ReadExtentsToDiff(
260 old_part_.path,
261 new_part_.path,
262 old_extents,
263 new_extents,
264 {}, // old_deflates
265 {}, // new_deflates
266 {.version = PayloadVersion(kBrilloMajorPayloadVersion,
267 kSourceMinorPayloadVersion)},
268 &data,
269 &aop));
270 InstallOperation& op = aop.op;
271 ASSERT_TRUE(data.empty());
272
273 ASSERT_TRUE(op.has_type());
274 ASSERT_EQ(InstallOperation::SOURCE_COPY, op.type());
275 }
276
TEST_F(DeltaDiffUtilsTest,SourceBsdiffTest)277 TEST_F(DeltaDiffUtilsTest, SourceBsdiffTest) {
278 // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
279 // is true. It is the same setup as BsdiffSmallTest, which checks
280 // that the operation is well-formed.
281 brillo::Blob data_blob(kBlockSize);
282 test_utils::FillWithData(&data_blob);
283
284 // The old file is on a different block than the new one.
285 vector<Extent> old_extents = {ExtentForRange(1, 1)};
286 vector<Extent> new_extents = {ExtentForRange(2, 1)};
287
288 ASSERT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
289 // Modify one byte in the new file.
290 data_blob[0]++;
291 ASSERT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
292
293 brillo::Blob data;
294 AnnotatedOperation aop;
295 ASSERT_TRUE(diff_utils::ReadExtentsToDiff(
296 old_part_.path,
297 new_part_.path,
298 old_extents,
299 new_extents,
300 {}, // old_deflates
301 {}, // new_deflates
302 {.version = PayloadVersion(kBrilloMajorPayloadVersion,
303 kSourceMinorPayloadVersion)},
304 &data,
305 &aop));
306 auto& op = aop.op;
307 ASSERT_FALSE(data.empty());
308 ASSERT_TRUE(op.has_type());
309 ASSERT_EQ(InstallOperation::SOURCE_BSDIFF, op.type());
310 }
311
TEST_F(DeltaDiffUtilsTest,BrotliBsdiffTest)312 TEST_F(DeltaDiffUtilsTest, BrotliBsdiffTest) {
313 // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
314 // is true. It is the same setup as BsdiffSmallTest, which checks
315 // that the operation is well-formed.
316 brillo::Blob data_blob(kBlockSize);
317 test_utils::FillWithData(&data_blob);
318
319 // The old file is on a different block than the new one.
320 vector<Extent> old_extents = {ExtentForRange(1, 1)};
321 vector<Extent> new_extents = {ExtentForRange(2, 1)};
322
323 ASSERT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
324 // Modify one byte in the new file.
325 data_blob[0]++;
326 ASSERT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
327
328 brillo::Blob data;
329 AnnotatedOperation aop;
330
331 std::vector<puffin::BitExtent> empty;
332 PayloadGenerationConfig config{
333 .version = PayloadVersion(kBrilloMajorPayloadVersion,
334 kBrotliBsdiffMinorPayloadVersion)};
335 ASSERT_TRUE(diff_utils::ReadExtentsToDiff(old_part_.path,
336 new_part_.path,
337 old_extents,
338 new_extents,
339 {}, // old_file
340 {}, // new_file
341 config,
342 &data,
343 &aop));
344 auto& op = aop.op;
345 ASSERT_FALSE(data.empty());
346 ASSERT_TRUE(op.has_type());
347 ASSERT_EQ(InstallOperation::BROTLI_BSDIFF, op.type());
348 }
349
TEST_F(DeltaDiffUtilsTest,GenerateBestDiffOperation_Zucchini)350 TEST_F(DeltaDiffUtilsTest, GenerateBestDiffOperation_Zucchini) {
351 // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
352 // is true. It is the same setup as BsdiffSmallTest, which checks
353 // that the operation is well-formed.
354 brillo::Blob dst_data_blob(kBlockSize);
355 test_utils::FillWithData(&dst_data_blob);
356
357 // The old file is on a different block than the new one.
358 vector<Extent> old_extents = {ExtentForRange(1, 1)};
359 vector<Extent> new_extents = {ExtentForRange(2, 1)};
360
361 ASSERT_TRUE(
362 WriteExtents(old_part_.path, old_extents, kBlockSize, dst_data_blob));
363 // Modify one byte in the new file.
364 brillo::Blob src_data_blob = dst_data_blob;
365 src_data_blob[0]++;
366 ASSERT_TRUE(
367 WriteExtents(new_part_.path, new_extents, kBlockSize, src_data_blob));
368
369 brillo::Blob data = dst_data_blob; // Fake the full operation
370 AnnotatedOperation aop;
371 // Zucchini is only enabled on files with certain extensions
372 aop.name = "data.so";
373
374 const FilesystemInterface::File empty;
375 PayloadGenerationConfig config{
376 .version = PayloadVersion(kBrilloMajorPayloadVersion,
377 kZucchiniMinorPayloadVersion)};
378 diff_utils::BestDiffGenerator best_diff_generator(src_data_blob,
379 dst_data_blob,
380 old_extents,
381 new_extents,
382 empty,
383 empty,
384 config);
385 ASSERT_TRUE(best_diff_generator.GenerateBestDiffOperation(
386 {{InstallOperation::ZUCCHINI, 1024 * 1024}}, &aop, &data));
387
388 auto& op = aop.op;
389 ASSERT_FALSE(data.empty());
390 ASSERT_TRUE(op.has_type());
391 ASSERT_EQ(InstallOperation::ZUCCHINI, op.type());
392 }
393
TEST_F(DeltaDiffUtilsTest,GenerateBestDiffOperation_FullOperationBetter)394 TEST_F(DeltaDiffUtilsTest, GenerateBestDiffOperation_FullOperationBetter) {
395 // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
396 // is true. It is the same setup as BsdiffSmallTest, which checks
397 // that the operation is well-formed.
398 brillo::Blob dst_data_blob(kBlockSize);
399 test_utils::FillWithData(&dst_data_blob);
400
401 // The old file is on a different block than the new one.
402 vector<Extent> old_extents = {ExtentForRange(1, 1)};
403 vector<Extent> new_extents = {ExtentForRange(2, 1)};
404
405 ASSERT_TRUE(
406 WriteExtents(old_part_.path, old_extents, kBlockSize, dst_data_blob));
407 // Modify one byte in the new file.
408 brillo::Blob src_data_blob = dst_data_blob;
409 src_data_blob[0]++;
410 ASSERT_TRUE(
411 WriteExtents(new_part_.path, new_extents, kBlockSize, src_data_blob));
412
413 brillo::Blob data(1);
414 test_utils::FillWithData(&data); // Fake the full operation
415 AnnotatedOperation aop;
416 aop.op.set_type(InstallOperation::REPLACE_XZ);
417
418 const FilesystemInterface::File empty;
419 PayloadGenerationConfig config{
420 .version = PayloadVersion(kBrilloMajorPayloadVersion,
421 kZucchiniMinorPayloadVersion)};
422 diff_utils::BestDiffGenerator best_diff_generator(src_data_blob,
423 dst_data_blob,
424 old_extents,
425 new_extents,
426 empty,
427 empty,
428 config);
429 ASSERT_TRUE(best_diff_generator.GenerateBestDiffOperation(
430 {{InstallOperation::ZUCCHINI, 1024 * 1024}}, &aop, &data));
431
432 auto& op = aop.op;
433 ASSERT_EQ(1u, data.size());
434 ASSERT_TRUE(op.has_type());
435 ASSERT_EQ(InstallOperation::REPLACE_XZ, op.type());
436 }
437
TEST_F(DeltaDiffUtilsTest,PreferReplaceTest)438 TEST_F(DeltaDiffUtilsTest, PreferReplaceTest) {
439 brillo::Blob data_blob(kBlockSize);
440 vector<Extent> extents = {ExtentForRange(1, 1)};
441
442 // Write something in the first 50 bytes so that REPLACE_BZ will be slightly
443 // larger than BROTLI_BSDIFF.
444 std::iota(data_blob.begin(), data_blob.begin() + 50, 0);
445 ASSERT_TRUE(WriteExtents(old_part_.path, extents, kBlockSize, data_blob));
446 // Shift the first 50 bytes in the new file by one.
447 std::iota(data_blob.begin(), data_blob.begin() + 50, 1);
448 ASSERT_TRUE(WriteExtents(new_part_.path, extents, kBlockSize, data_blob));
449
450 brillo::Blob data;
451 AnnotatedOperation aop;
452
453 const FilesystemInterface::File empty;
454 PayloadGenerationConfig config{
455 .version = PayloadVersion(kMaxSupportedMajorPayloadVersion,
456 kMaxSupportedMinorPayloadVersion)};
457 ASSERT_TRUE(diff_utils::ReadExtentsToDiff(old_part_.path,
458 new_part_.path,
459 extents,
460 extents,
461 empty, // old_file
462 empty, // new_file
463 config,
464 &data,
465 &aop));
466 auto& op = aop.op;
467 ASSERT_FALSE(data.empty());
468 ASSERT_TRUE(op.has_type());
469 ASSERT_EQ(InstallOperation::REPLACE_BZ, op.type());
470 }
471
472 // Test the simple case where all the blocks are different and no new blocks are
473 // zeroed.
TEST_F(DeltaDiffUtilsTest,NoZeroedOrUniqueBlocksDetected)474 TEST_F(DeltaDiffUtilsTest, NoZeroedOrUniqueBlocksDetected) {
475 InitializePartitionWithUniqueBlocks(old_part_, block_size_, 5);
476 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
477
478 ASSERT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks
479 kSourceMinorPayloadVersion));
480
481 ASSERT_EQ(0U, old_visited_blocks_.blocks());
482 ASSERT_EQ(0U, new_visited_blocks_.blocks());
483 ASSERT_EQ(0, blob_size_);
484 ASSERT_TRUE(aops_.empty());
485 }
486
487 // Test that when the partitions have identical blocks in the same positions
488 // MOVE operation is performed and all the blocks are handled.
TEST_F(DeltaDiffUtilsTest,IdenticalBlocksAreCopiedFromSource)489 TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedFromSource) {
490 // We use a smaller partition for this test.
491 old_part_.size = kBlockSize * 50;
492 new_part_.size = kBlockSize * 50;
493
494 InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
495 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
496
497 // Mark some of the blocks as already visited.
498 vector<Extent> already_visited = {ExtentForRange(5, 5),
499 ExtentForRange(25, 7)};
500 old_visited_blocks_.AddExtents(already_visited);
501 new_visited_blocks_.AddExtents(already_visited);
502
503 // Override some of the old blocks with different data.
504 vector<Extent> different_blocks = {ExtentForRange(40, 5)};
505 ASSERT_TRUE(WriteExtents(old_part_.path,
506 different_blocks,
507 kBlockSize,
508 brillo::Blob(5 * kBlockSize, 'a')));
509
510 ASSERT_TRUE(RunDeltaMovedAndZeroBlocks(10, // chunk_blocks
511 kSourceMinorPayloadVersion));
512
513 ExtentRanges expected_ranges;
514 expected_ranges.AddExtent(ExtentForRange(0, 50));
515 expected_ranges.SubtractExtents(different_blocks);
516
517 ASSERT_EQ(expected_ranges.extent_set(), old_visited_blocks_.extent_set());
518 ASSERT_EQ(expected_ranges.extent_set(), new_visited_blocks_.extent_set());
519 ASSERT_EQ(0, blob_size_);
520
521 // We expect all the blocks that we didn't override with |different_blocks|
522 // and that we didn't mark as visited in |already_visited| to match and have a
523 // SOURCE_COPY operation chunked at 10 blocks.
524 vector<Extent> expected_op_extents = {
525 ExtentForRange(0, 5),
526 ExtentForRange(10, 10),
527 ExtentForRange(20, 5),
528 ExtentForRange(32, 8),
529 ExtentForRange(45, 5),
530 };
531
532 ASSERT_EQ(expected_op_extents.size(), aops_.size());
533 for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) {
534 SCOPED_TRACE(
535 android::base::StringPrintf("Failed on operation number %" PRIuS, i));
536 const AnnotatedOperation& aop = aops_[i];
537 ASSERT_EQ(InstallOperation::SOURCE_COPY, aop.op.type());
538 ASSERT_EQ(1, aop.op.src_extents_size());
539 ASSERT_EQ(expected_op_extents[i], aop.op.src_extents(0));
540 ASSERT_EQ(1, aop.op.dst_extents_size());
541 ASSERT_EQ(expected_op_extents[i], aop.op.dst_extents(0));
542 }
543 }
544
TEST_F(DeltaDiffUtilsTest,IdenticalBlocksAreCopiedInOder)545 TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedInOder) {
546 // We use a smaller partition for this test.
547 old_part_.size = block_size_ * 50;
548 new_part_.size = block_size_ * 50;
549
550 // Create two identical partitions with 5 copies of the same unique "file".
551 brillo::Blob file_data(block_size_ * 10, 'a');
552 for (size_t offset = 0; offset < file_data.size(); offset += block_size_)
553 file_data[offset] = 'a' + offset / block_size_;
554
555 brillo::Blob partition_data(old_part_.size);
556 for (size_t offset = 0; offset < partition_data.size();
557 offset += file_data.size()) {
558 std::copy(
559 file_data.begin(), file_data.end(), partition_data.begin() + offset);
560 }
561 ASSERT_TRUE(test_utils::WriteFileVector(old_part_.path, partition_data));
562 ASSERT_TRUE(test_utils::WriteFileVector(new_part_.path, partition_data));
563
564 ASSERT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks
565 kSourceMinorPayloadVersion));
566
567 // There should be only one SOURCE_COPY, for the whole partition and the
568 // source extents should cover only the first copy of the source file since
569 // we prefer to re-read files (maybe cached) instead of continue reading the
570 // rest of the partition.
571 ASSERT_EQ(1U, aops_.size());
572 const AnnotatedOperation& aop = aops_[0];
573 ASSERT_EQ(InstallOperation::SOURCE_COPY, aop.op.type());
574 ASSERT_EQ(5, aop.op.src_extents_size());
575 for (int i = 0; i < aop.op.src_extents_size(); ++i) {
576 ASSERT_EQ(ExtentForRange(0, 10), aop.op.src_extents(i));
577 }
578
579 ASSERT_EQ(1, aop.op.dst_extents_size());
580 ASSERT_EQ(ExtentForRange(0, 50), aop.op.dst_extents(0));
581
582 ASSERT_EQ(0, blob_size_);
583 }
584
585 // Test that all blocks with zeros are handled separately using REPLACE_BZ
586 // operations unless they are not moved.
TEST_F(DeltaDiffUtilsTest,ZeroBlocksUseReplaceBz)587 TEST_F(DeltaDiffUtilsTest, ZeroBlocksUseReplaceBz) {
588 InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
589 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 5);
590
591 // We set four ranges of blocks with zeros: a single block, a range that fits
592 // in the chunk size, a range that doesn't and finally a range of zeros that
593 // was also zeros in the old image.
594 vector<Extent> new_zeros = {
595 ExtentForRange(10, 1),
596 ExtentForRange(20, 4),
597 // The last range is split since the old image has zeros in part of it.
598 ExtentForRange(30, 20),
599 };
600 brillo::Blob zeros_data(utils::BlocksInExtents(new_zeros) * block_size_,
601 '\0');
602 ASSERT_TRUE(WriteExtents(new_part_.path, new_zeros, block_size_, zeros_data));
603
604 vector<Extent> old_zeros = vector<Extent>{ExtentForRange(43, 7)};
605 ASSERT_TRUE(WriteExtents(old_part_.path, old_zeros, block_size_, zeros_data));
606
607 ASSERT_TRUE(RunDeltaMovedAndZeroBlocks(5, // chunk_blocks
608 kSourceMinorPayloadVersion));
609
610 // Zeroed blocks from |old_visited_blocks_| were copied over.
611 ASSERT_EQ(old_zeros,
612 old_visited_blocks_.GetExtentsForBlockCount(
613 old_visited_blocks_.blocks()));
614
615 // All the new zeroed blocks should be used with REPLACE_BZ.
616 ASSERT_EQ(new_zeros,
617 new_visited_blocks_.GetExtentsForBlockCount(
618 new_visited_blocks_.blocks()));
619
620 vector<Extent> expected_op_extents = {
621 ExtentForRange(10, 1),
622 ExtentForRange(20, 4),
623 // This range should be split.
624 ExtentForRange(30, 5),
625 ExtentForRange(35, 5),
626 ExtentForRange(40, 5),
627 ExtentForRange(45, 5),
628 };
629
630 ASSERT_EQ(expected_op_extents.size(), aops_.size());
631 for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) {
632 SCOPED_TRACE(
633 android::base::StringPrintf("Failed on operation number %" PRIuS, i));
634 const AnnotatedOperation& aop = aops_[i];
635 ASSERT_EQ(InstallOperation::REPLACE_BZ, aop.op.type());
636 ASSERT_EQ(0, aop.op.src_extents_size());
637 ASSERT_EQ(1, aop.op.dst_extents_size());
638 ASSERT_EQ(expected_op_extents[i], aop.op.dst_extents(0));
639 }
640 ASSERT_NE(0, blob_size_);
641 }
642
TEST_F(DeltaDiffUtilsTest,ShuffledBlocksAreTracked)643 TEST_F(DeltaDiffUtilsTest, ShuffledBlocksAreTracked) {
644 vector<uint64_t> permutation = {0, 1, 5, 6, 7, 2, 3, 4, 9, 10, 11, 12, 8};
645 vector<Extent> perm_extents;
646 for (uint64_t x : permutation)
647 AppendBlockToExtents(&perm_extents, x);
648
649 // We use a smaller partition for this test.
650 old_part_.size = block_size_ * permutation.size();
651 new_part_.size = block_size_ * permutation.size();
652 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 123);
653
654 // We initialize the old_part_ with the blocks from new_part but in the
655 // |permutation| order. Block i in the old_part_ will contain the same data
656 // as block permutation[i] in the new_part_.
657 brillo::Blob new_contents;
658 ASSERT_TRUE(utils::ReadFile(new_part_.path, &new_contents));
659 ASSERT_TRUE(
660 WriteExtents(old_part_.path, perm_extents, block_size_, new_contents));
661
662 ASSERT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks
663 kSourceMinorPayloadVersion));
664
665 ASSERT_EQ(permutation.size(), old_visited_blocks_.blocks());
666 ASSERT_EQ(permutation.size(), new_visited_blocks_.blocks());
667
668 // There should be only one SOURCE_COPY, with a complicate list of extents.
669 ASSERT_EQ(1U, aops_.size());
670 const AnnotatedOperation& aop = aops_[0];
671 ASSERT_EQ(InstallOperation::SOURCE_COPY, aop.op.type());
672 vector<Extent> aop_src_extents;
673 ExtentsToVector(aop.op.src_extents(), &aop_src_extents);
674 ASSERT_EQ(perm_extents, aop_src_extents);
675
676 ASSERT_EQ(1, aop.op.dst_extents_size());
677 ASSERT_EQ(ExtentForRange(0, permutation.size()), aop.op.dst_extents(0));
678
679 ASSERT_EQ(0, blob_size_);
680 }
681
TEST_F(DeltaDiffUtilsTest,IsExtFilesystemTest)682 TEST_F(DeltaDiffUtilsTest, IsExtFilesystemTest) {
683 ASSERT_TRUE(diff_utils::IsExtFilesystem(
684 test_utils::GetBuildArtifactsPath("gen/disk_ext2_1k.img")));
685 ASSERT_TRUE(diff_utils::IsExtFilesystem(
686 test_utils::GetBuildArtifactsPath("gen/disk_ext2_4k.img")));
687 }
688
TEST_F(DeltaDiffUtilsTest,GetOldFileEmptyTest)689 TEST_F(DeltaDiffUtilsTest, GetOldFileEmptyTest) {
690 ASSERT_TRUE(diff_utils::GetOldFile({}, "filename").name.empty());
691 }
692
TEST_F(DeltaDiffUtilsTest,GetOldFileTest)693 TEST_F(DeltaDiffUtilsTest, GetOldFileTest) {
694 std::map<string, FilesystemInterface::File> old_files_map;
695 auto file_list = {
696 "filename",
697 "filename.zip",
698 "version1.1",
699 "version2.0",
700 "version",
701 "update_engine",
702 "delta_generator",
703 };
704 for (const auto& name : file_list) {
705 FilesystemInterface::File file;
706 file.name = name;
707 old_files_map.emplace(name, file);
708 }
709
710 // Always return exact match if possible.
711 for (const auto& name : file_list)
712 ASSERT_EQ(diff_utils::GetOldFile(old_files_map, name).name, name);
713
714 ASSERT_EQ(diff_utils::GetOldFile(old_files_map, "file_name").name,
715 "filename");
716 ASSERT_EQ(diff_utils::GetOldFile(old_files_map, "filename_new.zip").name,
717 "filename.zip");
718 ASSERT_EQ(diff_utils::GetOldFile(old_files_map, "version1.2").name,
719 "version1.1");
720 ASSERT_EQ(diff_utils::GetOldFile(old_files_map, "version3.0").name,
721 "version2.0");
722 ASSERT_EQ(diff_utils::GetOldFile(old_files_map, "_version").name, "version");
723 ASSERT_EQ(
724 diff_utils::GetOldFile(old_files_map, "update_engine_unittest").name,
725 "update_engine");
726 ASSERT_EQ(diff_utils::GetOldFile(old_files_map, "bin/delta_generator").name,
727 "delta_generator");
728 // Check file name with minimum size.
729 ASSERT_EQ(diff_utils::GetOldFile(old_files_map, "a").name, "filename");
730 }
731
TEST_F(DeltaDiffUtilsTest,XorOpsSourceNotAligned)732 TEST_F(DeltaDiffUtilsTest, XorOpsSourceNotAligned) {
733 ScopedTempFile patch_file;
734 bsdiff::BsdiffPatchWriter writer{patch_file.path()};
735 ASSERT_TRUE(writer.Init(kBlockSize * 10));
736 ASSERT_TRUE(writer.AddControlEntry(ControlEntry(0, 0, 123 + kBlockSize)));
737 ASSERT_TRUE(writer.AddControlEntry(ControlEntry(kBlockSize, 0, 0)));
738 ASSERT_TRUE(writer.Close());
739
740 std::string patch_data;
741 utils::ReadFile(patch_file.path(), &patch_data);
742
743 AnnotatedOperation aop;
744 *aop.op.add_src_extents() = ExtentForRange(50, 10);
745 *aop.op.add_dst_extents() = ExtentForRange(500, 10);
746
747 diff_utils::PopulateXorOps(
748 &aop,
749 reinterpret_cast<const uint8_t*>(patch_data.data()),
750 patch_data.size());
751 for (const auto& op : aop.xor_ops) {
752 ASSERT_EQ(op.type(), CowMergeOperation::COW_XOR);
753 }
754 ASSERT_EQ(aop.xor_ops.size(), 1UL) << "Only 1 block can possibly be XORed";
755 ASSERT_EQ(aop.xor_ops[0].src_extent().num_blocks(), 1UL);
756 ASSERT_EQ(aop.xor_ops[0].src_extent().start_block(), 51UL);
757 ASSERT_EQ(aop.xor_ops[0].src_offset(), 123UL);
758
759 ASSERT_EQ(aop.xor_ops[0].dst_extent().num_blocks(), 1UL);
760 ASSERT_EQ(aop.xor_ops[0].dst_extent().start_block(), 500UL);
761 }
762
TEST_F(DeltaDiffUtilsTest,XorOpsTargetNotAligned)763 TEST_F(DeltaDiffUtilsTest, XorOpsTargetNotAligned) {
764 ScopedTempFile patch_file;
765 bsdiff::BsdiffPatchWriter writer{patch_file.path()};
766 ASSERT_TRUE(writer.Init(kBlockSize * 10));
767 ASSERT_TRUE(writer.AddControlEntry(
768 ControlEntry(0, kBlockSize - 456, 123 + kBlockSize)));
769 ASSERT_TRUE(writer.AddControlEntry(ControlEntry(kBlockSize + 456, 0, 0)));
770 ASSERT_TRUE(writer.Close());
771
772 std::string patch_data;
773 utils::ReadFile(patch_file.path(), &patch_data);
774
775 AnnotatedOperation aop;
776 *aop.op.add_src_extents() = ExtentForRange(50, 10);
777 *aop.op.add_dst_extents() = ExtentForRange(500, 10);
778
779 diff_utils::PopulateXorOps(
780 &aop,
781 reinterpret_cast<const uint8_t*>(patch_data.data()),
782 patch_data.size());
783 for (const auto& op : aop.xor_ops) {
784 ASSERT_EQ(op.type(), CowMergeOperation::COW_XOR);
785 }
786 ASSERT_EQ(aop.xor_ops.size(), 1UL) << "Only 1 block can possibly be XORed";
787 ASSERT_EQ(aop.xor_ops[0].src_extent().num_blocks(), 1UL);
788 ASSERT_EQ(aop.xor_ops[0].src_extent().start_block(), 51UL);
789 ASSERT_EQ(aop.xor_ops[0].src_offset(), 123UL + 456UL);
790
791 ASSERT_EQ(aop.xor_ops[0].dst_extent().num_blocks(), 1UL);
792 ASSERT_EQ(aop.xor_ops[0].dst_extent().start_block(), 501UL);
793 }
794
TEST_F(DeltaDiffUtilsTest,XorOpsStrided)795 TEST_F(DeltaDiffUtilsTest, XorOpsStrided) {
796 ScopedTempFile patch_file;
797 bsdiff::BsdiffPatchWriter writer{patch_file.path()};
798 ASSERT_TRUE(writer.Init(kBlockSize * 10));
799 ASSERT_TRUE(writer.AddControlEntry(ControlEntry(0, kBlockSize - 456, 123)));
800 ASSERT_TRUE(
801 writer.AddControlEntry(ControlEntry(kBlockSize * 10 + 456, 0, 0)));
802 ASSERT_TRUE(writer.Close());
803
804 std::string patch_data;
805 utils::ReadFile(patch_file.path(), &patch_data);
806
807 AnnotatedOperation aop;
808 *aop.op.add_src_extents() = ExtentForRange(50, 5);
809 *aop.op.add_src_extents() = ExtentForRange(60, 5);
810
811 *aop.op.add_dst_extents() = ExtentForRange(500, 2);
812 *aop.op.add_dst_extents() = ExtentForRange(600, 2);
813 *aop.op.add_dst_extents() = ExtentForRange(700, 7);
814
815 diff_utils::PopulateXorOps(
816 &aop,
817 reinterpret_cast<const uint8_t*>(patch_data.data()),
818 patch_data.size());
819 ASSERT_EQ(aop.xor_ops.size(), 4UL);
820 for (const auto& op : aop.xor_ops) {
821 ASSERT_EQ(op.type(), CowMergeOperation::COW_XOR);
822 }
823 for (const auto& op : aop.xor_ops) {
824 ASSERT_EQ(op.src_offset(), 123UL + 456UL);
825 LOG(INFO) << op.src_extent() << ", " << op.dst_extent();
826 }
827 ASSERT_EQ(aop.xor_ops[0].src_extent().num_blocks(), 2UL);
828 ASSERT_EQ(aop.xor_ops[0].src_extent().start_block(), 50UL);
829
830 ASSERT_EQ(aop.xor_ops[0].dst_extent().num_blocks(), 1UL);
831 ASSERT_EQ(aop.xor_ops[0].dst_extent().start_block(), 501UL);
832
833 ASSERT_EQ(aop.xor_ops[1].src_extent().num_blocks(), 3UL);
834 ASSERT_EQ(aop.xor_ops[1].src_extent().start_block(), 51UL);
835
836 ASSERT_EQ(aop.xor_ops[1].dst_extent().num_blocks(), 2UL);
837 ASSERT_EQ(aop.xor_ops[1].dst_extent().start_block(), 600UL);
838
839 ASSERT_EQ(aop.xor_ops[2].src_extent().num_blocks(), 3UL);
840 ASSERT_EQ(aop.xor_ops[2].src_extent().start_block(), 53UL);
841
842 ASSERT_EQ(aop.xor_ops[2].dst_extent().num_blocks(), 2UL);
843 ASSERT_EQ(aop.xor_ops[2].dst_extent().start_block(), 700UL);
844
845 ASSERT_EQ(aop.xor_ops[3].src_extent().num_blocks(), 6UL);
846 ASSERT_EQ(aop.xor_ops[3].src_extent().start_block(), 60UL);
847
848 ASSERT_EQ(aop.xor_ops[3].dst_extent().num_blocks(), 5UL);
849 ASSERT_EQ(aop.xor_ops[3].dst_extent().start_block(), 702UL);
850 }
851
TEST_F(DeltaDiffUtilsTest,FindAndCompactDeflates)852 TEST_F(DeltaDiffUtilsTest, FindAndCompactDeflates) {
853 std::vector<puffin::BitExtent> bit_extents{{114122 * 8 * kBlockSize, 1024},
854 {114122 * 8 * kBlockSize, 1024}};
855
856 std::vector<Extent> extents = {ExtentForRange(114122, 295),
857 ExtentForRange(114418, 16654),
858 ExtentForRange(131102, 1),
859 ExtentForRange(131104, 307),
860 ExtentForRange(131414, 4143),
861 ExtentForRange(135559, 8528)};
862 std::vector<puffin::BitExtent> out_deflates;
863 ASSERT_TRUE(deflate_utils::FindAndCompactDeflates(
864 extents, bit_extents, &out_deflates));
865 }
866
867 } // namespace chromeos_update_engine
868