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