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