delta_diff_utils_unittest.cc revision 2d3b2d635e50c6886e285afb86c3187d9e0bd360 
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    return diff_utils::DeltaMovedAndZeroBlocks(
119        &aops_,
120        old_part_.path,
121        new_part_.path,
122        old_part_.size / block_size_,
123        new_part_.size / block_size_,
124        chunk_blocks,
125        src_ops_allowed,
126        blob_fd_,
127        &blob_size_,
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  DeltaArchiveManifest_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(DeltaArchiveManifest_InstallOperation_Type_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  DeltaArchiveManifest_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(DeltaArchiveManifest_InstallOperation_Type_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  DeltaArchiveManifest_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(DeltaArchiveManifest_InstallOperation_Type_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  DeltaArchiveManifest_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(DeltaArchiveManifest_InstallOperation_Type_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  DeltaArchiveManifest_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(DeltaArchiveManifest_InstallOperation_Type_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    DeltaArchiveManifest_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 DeltaArchiveManifest_InstallOperation_Type expected_type =
415        (i == 0 ? DeltaArchiveManifest_InstallOperation_Type_REPLACE :
416         DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
417    EXPECT_EQ(expected_type, op.type());
418    EXPECT_FALSE(op.has_data_offset());
419    EXPECT_FALSE(op.has_data_length());
420    EXPECT_EQ(0, op.src_extents_size());
421    EXPECT_FALSE(op.has_src_length());
422    EXPECT_EQ(1, op.dst_extents_size());
423    EXPECT_EQ(data_to_test.size(), op.dst_length());
424    EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
425  }
426}
427
428TEST_F(DeltaDiffUtilsTest, SourceCopyTest) {
429  // Makes sure SOURCE_COPY operations are emitted whenever src_ops_allowed
430  // is true. It is the same setup as MoveSmallTest, which checks that
431  // the operation is well-formed.
432  chromeos::Blob data_blob(kBlockSize);
433  test_utils::FillWithData(&data_blob);
434
435  // The old file is on a different block than the new one.
436  vector<Extent> old_extents = { ExtentForRange(11, 1) };
437  vector<Extent> new_extents = { ExtentForRange(1, 1) };
438
439  EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
440  EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
441
442  chromeos::Blob data;
443  DeltaArchiveManifest_InstallOperation op;
444  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
445      old_part_.path,
446      new_part_.path,
447      old_extents,
448      new_extents,
449      true,  // bsdiff_allowed
450      &data,
451      &op,
452      true));  // src_ops_allowed
453  EXPECT_TRUE(data.empty());
454
455  EXPECT_TRUE(op.has_type());
456  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY, op.type());
457}
458
459TEST_F(DeltaDiffUtilsTest, SourceBsdiffTest) {
460  // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
461  // is true. It is the same setup as BsdiffSmallTest, which checks
462  // that the operation is well-formed.
463  chromeos::Blob data_blob(kBlockSize);
464  test_utils::FillWithData(&data_blob);
465
466  // The old file is on a different block than the new one.
467  vector<Extent> old_extents = { ExtentForRange(1, 1) };
468  vector<Extent> new_extents = { ExtentForRange(2, 1) };
469
470  EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
471  // Modify one byte in the new file.
472  data_blob[0]++;
473  EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
474
475  chromeos::Blob data;
476  DeltaArchiveManifest_InstallOperation op;
477  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
478      old_part_.path,
479      new_part_.path,
480      old_extents,
481      new_extents,
482      true,  // bsdiff_allowed
483      &data,
484      &op,
485      true));  // src_ops_allowed
486
487  EXPECT_FALSE(data.empty());
488  EXPECT_TRUE(op.has_type());
489  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF,
490            op.type());
491}
492
493TEST_F(DeltaDiffUtilsTest, IsNoopOperationTest) {
494  DeltaArchiveManifest_InstallOperation op;
495  op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
496  EXPECT_FALSE(diff_utils::IsNoopOperation(op));
497  op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
498  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
499  *(op.add_src_extents()) = ExtentForRange(3, 2);
500  *(op.add_dst_extents()) = ExtentForRange(3, 2);
501  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
502  *(op.add_src_extents()) = ExtentForRange(7, 5);
503  *(op.add_dst_extents()) = ExtentForRange(7, 5);
504  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
505  *(op.add_src_extents()) = ExtentForRange(20, 2);
506  *(op.add_dst_extents()) = ExtentForRange(20, 1);
507  *(op.add_dst_extents()) = ExtentForRange(21, 1);
508  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
509  *(op.add_src_extents()) = ExtentForRange(24, 1);
510  *(op.add_dst_extents()) = ExtentForRange(25, 1);
511  EXPECT_FALSE(diff_utils::IsNoopOperation(op));
512}
513
514TEST_F(DeltaDiffUtilsTest, FilterNoopOperations) {
515  AnnotatedOperation aop1;
516  aop1.op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
517  *(aop1.op.add_dst_extents()) = ExtentForRange(3, 2);
518  aop1.name = "aop1";
519
520  AnnotatedOperation aop2 = aop1;
521  aop2.name = "aop2";
522
523  AnnotatedOperation noop;
524  noop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
525  *(noop.op.add_src_extents()) = ExtentForRange(3, 2);
526  *(noop.op.add_dst_extents()) = ExtentForRange(3, 2);
527  noop.name = "noop";
528
529  vector<AnnotatedOperation> ops = {noop, aop1, noop, noop, aop2, noop};
530  diff_utils::FilterNoopOperations(&ops);
531  EXPECT_EQ(2u, ops.size());
532  EXPECT_EQ("aop1", ops[0].name);
533  EXPECT_EQ("aop2", ops[1].name);
534}
535
536// Test the simple case where all the blocks are different and no new blocks are
537// zeroed.
538TEST_F(DeltaDiffUtilsTest, NoZeroedOrUniqueBlocksDetected) {
539  InitializePartitionWithUniqueBlocks(old_part_, block_size_, 5);
540  InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
541
542  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
543                                         false));  // src_ops_allowed
544
545  EXPECT_EQ(0, old_visited_blocks_.blocks());
546  EXPECT_EQ(0, new_visited_blocks_.blocks());
547  EXPECT_EQ(0, blob_size_);
548  EXPECT_TRUE(aops_.empty());
549}
550
551// Test that when the partitions have identical blocks in the same positions no
552// MOVE operation is performed and all the blocks are handled.
553TEST_F(DeltaDiffUtilsTest, IdenticalPartitionsDontMove) {
554  InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
555  InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
556
557  // Mark some of the blocks as already visited.
558  vector<Extent> already_visited = {ExtentForRange(5, 10),
559                                    ExtentForRange(25, 10)};
560  old_visited_blocks_.AddExtents(already_visited);
561  new_visited_blocks_.AddExtents(already_visited);
562
563  // Most of the blocks rest in the same place, but there's no need for MOVE
564  // operations on those blocks.
565  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
566                                         false));  // src_ops_allowed
567
568  EXPECT_EQ(kDefaultBlockCount, old_visited_blocks_.blocks());
569  EXPECT_EQ(kDefaultBlockCount, new_visited_blocks_.blocks());
570  EXPECT_EQ(0, blob_size_);
571  EXPECT_TRUE(aops_.empty());
572}
573
574// Test that when the partitions have identical blocks in the same positions
575// MOVE operation is performed and all the blocks are handled.
576TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedFromSource) {
577  // We use a smaller partition for this test.
578  old_part_.size = kBlockSize * 50;
579  new_part_.size = kBlockSize * 50;
580
581  InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
582  InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
583
584  // Mark some of the blocks as already visited.
585  vector<Extent> already_visited = {ExtentForRange(5, 5),
586                                    ExtentForRange(25, 7)};
587  old_visited_blocks_.AddExtents(already_visited);
588  new_visited_blocks_.AddExtents(already_visited);
589
590  // Override some of the old blocks with different data.
591  vector<Extent> different_blocks = {ExtentForRange(40, 5)};
592  EXPECT_TRUE(WriteExtents(old_part_.path, different_blocks, kBlockSize,
593                           chromeos::Blob(5 * kBlockSize, 'a')));
594
595  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(10,  // chunk_blocks
596                                         true));  // src_ops_allowed
597
598  ExtentRanges expected_ranges;
599  expected_ranges.AddExtent(ExtentForRange(0, 50));
600  expected_ranges.SubtractExtents(different_blocks);
601
602  EXPECT_EQ(expected_ranges.extent_set(), old_visited_blocks_.extent_set());
603  EXPECT_EQ(expected_ranges.extent_set(), new_visited_blocks_.extent_set());
604  EXPECT_EQ(0, blob_size_);
605
606  // We expect all the blocks that we didn't override with |different_blocks|
607  // and that we didn't mark as visited in |already_visited| to match and have a
608  // SOURCE_COPY operation chunked at 10 blocks.
609  vector<Extent> expected_op_extents = {
610      ExtentForRange(0, 5),
611      ExtentForRange(10, 10),
612      ExtentForRange(20, 5),
613      ExtentForRange(32, 8),
614      ExtentForRange(45, 5),
615  };
616
617  EXPECT_EQ(expected_op_extents.size(), aops_.size());
618  for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) {
619    SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i));
620    const AnnotatedOperation& aop = aops_[i];
621    EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
622              aop.op.type());
623    EXPECT_EQ(1, aop.op.src_extents_size());
624    EXPECT_EQ(expected_op_extents[i], aop.op.src_extents(0));
625    EXPECT_EQ(1, aop.op.dst_extents_size());
626    EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0));
627  }
628}
629
630TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedInOder) {
631  // We use a smaller partition for this test.
632  old_part_.size = block_size_ * 50;
633  new_part_.size = block_size_ * 50;
634
635  // Create two identical partitions with 5 copies of the same unique "file".
636  chromeos::Blob file_data(block_size_ * 10, 'a');
637  for (size_t offset = 0; offset < file_data.size(); offset += block_size_)
638    file_data[offset] = 'a' + offset / block_size_;
639
640  chromeos::Blob partition_data(old_part_.size);
641  for (size_t offset = 0; offset < partition_data.size();
642       offset += file_data.size()) {
643    std::copy(file_data.begin(), file_data.end(),
644              partition_data.begin() + offset);
645  }
646  EXPECT_TRUE(test_utils::WriteFileVector(old_part_.path, partition_data));
647  EXPECT_TRUE(test_utils::WriteFileVector(new_part_.path, partition_data));
648
649  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
650                                         true));  // src_ops_allowed
651
652  // There should be only one SOURCE_COPY, for the whole partition and the
653  // source extents should cover only the first copy of the source file since
654  // we prefer to re-read files (maybe cached) instead of continue reading the
655  // rest of the partition.
656  EXPECT_EQ(1, aops_.size());
657  const AnnotatedOperation& aop = aops_[0];
658  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
659            aop.op.type());
660  EXPECT_EQ(5, aop.op.src_extents_size());
661  for (int i = 0; i < aop.op.src_extents_size(); ++i) {
662    EXPECT_EQ(ExtentForRange(0, 10), aop.op.src_extents(i));
663  }
664
665  EXPECT_EQ(1, aop.op.dst_extents_size());
666  EXPECT_EQ(ExtentForRange(0, 50), aop.op.dst_extents(0));
667
668  EXPECT_EQ(0, blob_size_);
669}
670
671// Test that all blocks with zeros are handled separately using REPLACE_BZ
672// operations unless they are not moved.
673TEST_F(DeltaDiffUtilsTest, ZeroBlocksUseReplaceBz) {
674  InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
675  InitializePartitionWithUniqueBlocks(new_part_, block_size_, 5);
676
677  // We set four ranges of blocks with zeros: a single block, a range that fits
678  // in the chunk size, a range that doesn't and finally a range of zeros that
679  // was also zeros in the old image.
680  vector<Extent> new_zeros = {
681      ExtentForRange(10, 1),
682      ExtentForRange(20, 4),
683      // The last range is split since the old image has zeros in part of it.
684      ExtentForRange(30, 20),
685  };
686  chromeos::Blob zeros_data(BlocksInExtents(new_zeros) * block_size_, '\0');
687  EXPECT_TRUE(WriteExtents(new_part_.path, new_zeros, block_size_, zeros_data));
688
689  vector<Extent> old_zeros = vector<Extent>{ExtentForRange(43, 7)};
690  EXPECT_TRUE(WriteExtents(old_part_.path, old_zeros, block_size_, zeros_data));
691
692  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(5,  // chunk_blocks
693                                         false));  // src_ops_allowed
694
695  // Zeroed blocks from old_visited_blocks_ were copied over, so me actually
696  // use them regardless of the trivial MOVE operation not being emitted.
697  EXPECT_EQ(old_zeros,
698            old_visited_blocks_.GetExtentsForBlockCount(
699                old_visited_blocks_.blocks()));
700
701  // All the new zeroed blocks should be used, part with REPLACE_BZ and part
702  // trivial MOVE operations (not included).
703  EXPECT_EQ(new_zeros,
704            new_visited_blocks_.GetExtentsForBlockCount(
705                new_visited_blocks_.blocks()));
706
707  vector<Extent> expected_op_extents = {
708      ExtentForRange(10, 1),
709      ExtentForRange(20, 4),
710      // This range should be split.
711      ExtentForRange(30, 5),
712      ExtentForRange(35, 5),
713      ExtentForRange(40, 3),
714  };
715
716  EXPECT_EQ(expected_op_extents.size(), aops_.size());
717  for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) {
718    SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i));
719    const AnnotatedOperation& aop = aops_[i];
720    EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
721              aop.op.type());
722    EXPECT_EQ(0, aop.op.src_extents_size());
723    EXPECT_EQ(1, aop.op.dst_extents_size());
724    EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0));
725  }
726  EXPECT_NE(0, blob_size_);
727}
728
729TEST_F(DeltaDiffUtilsTest, ShuffledBlocksAreTracked) {
730  vector<uint64_t> permutation = {0, 1, 5, 6, 7, 2, 3, 4, 9, 10, 11, 12, 8};
731  vector<Extent> perm_extents;
732  for (uint64_t x : permutation)
733    AppendBlockToExtents(&perm_extents, x);
734
735  // We use a smaller partition for this test.
736  old_part_.size = block_size_ * permutation.size();
737  new_part_.size = block_size_ * permutation.size();
738  InitializePartitionWithUniqueBlocks(new_part_, block_size_, 123);
739
740  // We initialize the old_part_ with the blocks from new_part but in the
741  // |permutation| order. Block i in the old_part_ will contain the same data
742  // as block permutation[i] in the new_part_.
743  chromeos::Blob new_contents;
744  EXPECT_TRUE(utils::ReadFile(new_part_.path, &new_contents));
745  EXPECT_TRUE(WriteExtents(old_part_.path, perm_extents, block_size_,
746                           new_contents));
747
748  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
749                                         true));  // src_ops_allowed
750
751  EXPECT_EQ(permutation.size(), old_visited_blocks_.blocks());
752  EXPECT_EQ(permutation.size(), new_visited_blocks_.blocks());
753
754  // There should be only one SOURCE_COPY, with a complicate list of extents.
755  EXPECT_EQ(1, aops_.size());
756  const AnnotatedOperation& aop = aops_[0];
757  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
758            aop.op.type());
759  vector<Extent> aop_src_extents;
760  ExtentsToVector(aop.op.src_extents(), &aop_src_extents);
761  EXPECT_EQ(perm_extents, aop_src_extents);
762
763  EXPECT_EQ(1, aop.op.dst_extents_size());
764  EXPECT_EQ(ExtentForRange(0, permutation.size()), aop.op.dst_extents(0));
765
766  EXPECT_EQ(0, blob_size_);
767}
768
769}  // namespace chromeos_update_engine
770