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