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