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