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