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