delta_diff_utils_unittest.cc revision 14158570d3995008dc93a628004118b87a6bca01 
1// Copyright 2015 The Chromium OS Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "update_engine/payload_generator/delta_diff_utils.h"
6
7#include <algorithm>
8#include <string>
9#include <vector>
10
11#include <base/files/scoped_file.h>
12#include <gtest/gtest.h>
13
14#include "update_engine/payload_generator/delta_diff_generator.h"
15#include "update_engine/payload_generator/extent_ranges.h"
16#include "update_engine/payload_generator/extent_utils.h"
17#include "update_engine/payload_generator/fake_filesystem.h"
18#include "update_engine/test_utils.h"
19#include "update_engine/utils.h"
20
21using std::string;
22using std::unique_ptr;
23using std::vector;
24
25namespace chromeos_update_engine {
26
27namespace {
28
29// Writes the |data| in the blocks specified by |extents| on the partition
30// |part_path|. The |data| size could be smaller than the size of the blocks
31// passed.
32bool WriteExtents(const string& part_path,
33                  const vector<Extent>& extents,
34                  off_t block_size,
35                  const chromeos::Blob& data) {
36  uint64_t offset = 0;
37  base::ScopedFILE fp(fopen(part_path.c_str(), "r+"));
38  TEST_AND_RETURN_FALSE(fp.get());
39
40  for (const Extent& extent : extents) {
41    if (offset >= data.size())
42      break;
43    TEST_AND_RETURN_FALSE(
44        fseek(fp.get(), extent.start_block() * block_size, SEEK_SET) == 0);
45    uint64_t to_write = std::min(extent.num_blocks() * block_size,
46                                 data.size() - offset);
47    TEST_AND_RETURN_FALSE(
48        fwrite(data.data() + offset, 1, to_write, fp.get()) == to_write);
49    offset += extent.num_blocks() * block_size;
50  }
51  return true;
52}
53
54}  // namespace
55
56class DeltaDiffUtilsTest : public ::testing::Test {
57 protected:
58  const uint64_t kFilesystemSize = kBlockSize * 1024;
59
60  void SetUp() override {
61    old_part_path_ = "DeltaDiffUtilsTest-old_part_path-XXXXXX";
62    CreateFilesystem(&old_fs_, &old_part_path_, kFilesystemSize);
63
64    new_part_path_ = "DeltaDiffUtilsTest-new_part_path-XXXXXX";
65    CreateFilesystem(&old_fs_, &new_part_path_, kFilesystemSize);
66  }
67
68  void TearDown() override {
69    unlink(old_part_path_.c_str());
70    unlink(new_part_path_.c_str());
71  }
72
73  // Create a fake filesystem of the given size and initialize the partition
74  // holding it.
75  void CreateFilesystem(unique_ptr<FakeFilesystem>* fs, string* filename,
76                        uint64_t size) {
77    string pattern = *filename;
78    ASSERT_TRUE(utils::MakeTempFile(pattern.c_str(), filename, nullptr));
79    ASSERT_EQ(0, truncate(filename->c_str(), size));
80    fs->reset(new FakeFilesystem(kBlockSize, size / kBlockSize));
81  }
82
83  // Paths to old and new temporary filesystems used in the tests.
84  string old_part_path_;
85  string new_part_path_;
86
87  // FilesystemInterface fake implementations used to mock out the file/block
88  // distribution.
89  unique_ptr<FakeFilesystem> old_fs_;
90  unique_ptr<FakeFilesystem> new_fs_;
91};
92
93TEST_F(DeltaDiffUtilsTest, MoveSmallTest) {
94  chromeos::Blob data_blob(kBlockSize);
95  test_utils::FillWithData(&data_blob);
96
97  // The old file is on a different block than the new one.
98  vector<Extent> old_extents = { ExtentForRange(11, 1) };
99  vector<Extent> new_extents = { ExtentForRange(1, 1) };
100
101  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
102  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
103
104  chromeos::Blob data;
105  DeltaArchiveManifest_InstallOperation op;
106  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
107      old_part_path_,
108      new_part_path_,
109      old_extents,
110      new_extents,
111      true,  // bsdiff_allowed
112      &data,
113      &op,
114      false));  // src_ops_allowed
115  EXPECT_TRUE(data.empty());
116
117  EXPECT_TRUE(op.has_type());
118  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
119  EXPECT_FALSE(op.has_data_offset());
120  EXPECT_FALSE(op.has_data_length());
121  EXPECT_EQ(1, op.src_extents_size());
122  EXPECT_EQ(kBlockSize, op.src_length());
123  EXPECT_EQ(1, op.dst_extents_size());
124  EXPECT_EQ(kBlockSize, op.dst_length());
125  EXPECT_EQ(BlocksInExtents(op.src_extents()),
126            BlocksInExtents(op.dst_extents()));
127  EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
128}
129
130TEST_F(DeltaDiffUtilsTest, MoveWithSameBlock) {
131  // Setup the old/new files so that it has immobile chunks; we make sure to
132  // utilize all sub-cases of such chunks: blocks 21--22 induce a split (src)
133  // and complete removal (dst), whereas blocks 24--25 induce trimming of the
134  // tail (src) and head (dst) of extents. The final block (29) is used for
135  // ensuring we properly account for the number of bytes removed in cases where
136  // the last block is partly filled. The detailed configuration:
137  //
138  // Old:  [ 20     21 22     23     24 25 ] [ 28     29 ]
139  // New:  [ 18 ] [ 21 22 ] [ 20 ] [ 24 25     26 ] [ 29 ]
140  // Same:          ^^ ^^            ^^ ^^            ^^
141  vector<Extent> old_extents = {
142      ExtentForRange(20, 6),
143      ExtentForRange(28, 2) };
144  vector<Extent> new_extents = {
145      ExtentForRange(18, 1),
146      ExtentForRange(21, 2),
147      ExtentForRange(20, 1),
148      ExtentForRange(24, 3),
149      ExtentForRange(29, 1) };
150
151  uint64_t num_blocks = BlocksInExtents(old_extents);
152  EXPECT_EQ(num_blocks, BlocksInExtents(new_extents));
153
154  // The size of the data should match the total number of blocks. Each block
155  // has a different content.
156  chromeos::Blob file_data;
157  for (uint64_t i = 0; i < num_blocks; ++i) {
158    file_data.resize(file_data.size() + kBlockSize, 'a' + i);
159  }
160
161  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, file_data));
162  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, file_data));
163
164  chromeos::Blob data;
165  DeltaArchiveManifest_InstallOperation op;
166  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
167      old_part_path_,
168      new_part_path_,
169      old_extents,
170      new_extents,
171      true,  // bsdiff_allowed
172      &data,
173      &op,
174      false));  // src_ops_allowed
175
176  EXPECT_TRUE(data.empty());
177
178  EXPECT_TRUE(op.has_type());
179  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
180  EXPECT_FALSE(op.has_data_offset());
181  EXPECT_FALSE(op.has_data_length());
182
183  // The expected old and new extents that actually moved. See comment above.
184  old_extents = {
185      ExtentForRange(20, 1),
186      ExtentForRange(23, 1),
187      ExtentForRange(28, 1) };
188  new_extents = {
189      ExtentForRange(18, 1),
190      ExtentForRange(20, 1),
191      ExtentForRange(26, 1) };
192  num_blocks = BlocksInExtents(old_extents);
193
194  EXPECT_EQ(num_blocks * kBlockSize, op.src_length());
195  EXPECT_EQ(num_blocks * kBlockSize, op.dst_length());
196
197  EXPECT_EQ(old_extents.size(), op.src_extents_size());
198  for (int i = 0; i < op.src_extents_size(); i++) {
199    EXPECT_EQ(old_extents[i].start_block(), op.src_extents(i).start_block())
200        << "i == " << i;
201    EXPECT_EQ(old_extents[i].num_blocks(), op.src_extents(i).num_blocks())
202        << "i == " << i;
203  }
204
205  EXPECT_EQ(new_extents.size(), op.dst_extents_size());
206  for (int i = 0; i < op.dst_extents_size(); i++) {
207    EXPECT_EQ(new_extents[i].start_block(), op.dst_extents(i).start_block())
208        << "i == " << i;
209    EXPECT_EQ(new_extents[i].num_blocks(), op.dst_extents(i).num_blocks())
210        << "i == " << i;
211  }
212}
213
214TEST_F(DeltaDiffUtilsTest, BsdiffSmallTest) {
215  // Test a BSDIFF operation from block 1 to block 2.
216  chromeos::Blob data_blob(kBlockSize);
217  test_utils::FillWithData(&data_blob);
218
219  // The old file is on a different block than the new one.
220  vector<Extent> old_extents = { ExtentForRange(1, 1) };
221  vector<Extent> new_extents = { ExtentForRange(2, 1) };
222
223  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
224  // Modify one byte in the new file.
225  data_blob[0]++;
226  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
227
228  chromeos::Blob data;
229  DeltaArchiveManifest_InstallOperation op;
230  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
231      old_part_path_,
232      new_part_path_,
233      old_extents,
234      new_extents,
235      true,  // bsdiff_allowed
236      &data,
237      &op,
238      false));  // src_ops_allowed
239
240  EXPECT_FALSE(data.empty());
241
242  EXPECT_TRUE(op.has_type());
243  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
244  EXPECT_FALSE(op.has_data_offset());
245  EXPECT_FALSE(op.has_data_length());
246  EXPECT_EQ(1, op.src_extents_size());
247  EXPECT_EQ(kBlockSize, op.src_length());
248  EXPECT_EQ(1, op.dst_extents_size());
249  EXPECT_EQ(kBlockSize, op.dst_length());
250  EXPECT_EQ(BlocksInExtents(op.src_extents()),
251            BlocksInExtents(op.dst_extents()));
252  EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
253}
254
255TEST_F(DeltaDiffUtilsTest, BsdiffNotAllowedTest) {
256  // Same setup as the previous test, but this time BSDIFF operations are not
257  // allowed.
258  chromeos::Blob data_blob(kBlockSize);
259  test_utils::FillWithData(&data_blob);
260
261  // The old file is on a different block than the new one.
262  vector<Extent> old_extents = { ExtentForRange(1, 1) };
263  vector<Extent> new_extents = { ExtentForRange(2, 1) };
264
265  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
266  // Modify one byte in the new file.
267  data_blob[0]++;
268  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
269
270  chromeos::Blob data;
271  DeltaArchiveManifest_InstallOperation op;
272  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
273      old_part_path_,
274      new_part_path_,
275      old_extents,
276      new_extents,
277      false,  // bsdiff_allowed
278      &data,
279      &op,
280      false));  // src_ops_allowed
281
282  EXPECT_FALSE(data.empty());
283
284  // The point of this test is that we don't use BSDIFF the way the above
285  // did. The rest of the details are to be caught in other tests.
286  EXPECT_TRUE(op.has_type());
287  EXPECT_NE(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
288}
289
290TEST_F(DeltaDiffUtilsTest, BsdiffNotAllowedMoveTest) {
291  chromeos::Blob data_blob(kBlockSize);
292  test_utils::FillWithData(&data_blob);
293
294  // The old file is on a different block than the new one.
295  vector<Extent> old_extents = { ExtentForRange(1, 1) };
296  vector<Extent> new_extents = { ExtentForRange(2, 1) };
297
298  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
299  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
300
301  chromeos::Blob data;
302  DeltaArchiveManifest_InstallOperation op;
303  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
304      old_part_path_,
305      new_part_path_,
306      old_extents,
307      new_extents,
308      false,  // bsdiff_allowed
309      &data,
310      &op,
311      false));  // src_ops_allowed
312
313  EXPECT_TRUE(data.empty());
314
315  // The point of this test is that we can still use a MOVE for a file
316  // that is blacklisted.
317  EXPECT_TRUE(op.has_type());
318  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
319}
320
321TEST_F(DeltaDiffUtilsTest, ReplaceSmallTest) {
322  // The old file is on a different block than the new one.
323  vector<Extent> old_extents = { ExtentForRange(1, 1) };
324  vector<Extent> new_extents = { ExtentForRange(2, 1) };
325
326  // Make a blob that's just 1's that will compress well.
327  chromeos::Blob ones(kBlockSize, 1);
328
329  // Make a blob with random data that won't compress well.
330  chromeos::Blob random_data;
331  std::mt19937 gen(12345);
332  std::uniform_int_distribution<uint8_t> dis(0, 255);
333  for (uint32_t i = 0; i < kBlockSize; i++) {
334    random_data.push_back(dis(gen));
335  }
336
337  for (int i = 0; i < 2; i++) {
338    chromeos::Blob data_to_test = i == 0 ? random_data : ones;
339    // The old_extents will be initialized with 0.
340    EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize,
341                             data_to_test));
342
343    chromeos::Blob data;
344    DeltaArchiveManifest_InstallOperation op;
345    EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
346        old_part_path_,
347        new_part_path_,
348        old_extents,
349        new_extents,
350        true,  // bsdiff_allowed
351        &data,
352        &op,
353        false));  // src_ops_allowed
354    EXPECT_FALSE(data.empty());
355
356    EXPECT_TRUE(op.has_type());
357    const DeltaArchiveManifest_InstallOperation_Type expected_type =
358        (i == 0 ? DeltaArchiveManifest_InstallOperation_Type_REPLACE :
359         DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
360    EXPECT_EQ(expected_type, op.type());
361    EXPECT_FALSE(op.has_data_offset());
362    EXPECT_FALSE(op.has_data_length());
363    EXPECT_EQ(0, op.src_extents_size());
364    EXPECT_FALSE(op.has_src_length());
365    EXPECT_EQ(1, op.dst_extents_size());
366    EXPECT_EQ(data_to_test.size(), op.dst_length());
367    EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
368  }
369}
370
371TEST_F(DeltaDiffUtilsTest, SourceCopyTest) {
372  // Makes sure SOURCE_COPY operations are emitted whenever src_ops_allowed
373  // is true. It is the same setup as MoveSmallTest, which checks that
374  // the operation is well-formed.
375  chromeos::Blob data_blob(kBlockSize);
376  test_utils::FillWithData(&data_blob);
377
378  // The old file is on a different block than the new one.
379  vector<Extent> old_extents = { ExtentForRange(11, 1) };
380  vector<Extent> new_extents = { ExtentForRange(1, 1) };
381
382  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
383  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
384
385  chromeos::Blob data;
386  DeltaArchiveManifest_InstallOperation op;
387  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
388      old_part_path_,
389      new_part_path_,
390      old_extents,
391      new_extents,
392      true,  // bsdiff_allowed
393      &data,
394      &op,
395      true));  // src_ops_allowed
396  EXPECT_TRUE(data.empty());
397
398  EXPECT_TRUE(op.has_type());
399  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY, op.type());
400}
401
402TEST_F(DeltaDiffUtilsTest, SourceBsdiffTest) {
403  // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
404  // is true. It is the same setup as BsdiffSmallTest, which checks
405  // that the operation is well-formed.
406  chromeos::Blob data_blob(kBlockSize);
407  test_utils::FillWithData(&data_blob);
408
409  // The old file is on a different block than the new one.
410  vector<Extent> old_extents = { ExtentForRange(1, 1) };
411  vector<Extent> new_extents = { ExtentForRange(2, 1) };
412
413  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
414  // Modify one byte in the new file.
415  data_blob[0]++;
416  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
417
418  chromeos::Blob data;
419  DeltaArchiveManifest_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      &data,
427      &op,
428      true));  // src_ops_allowed
429
430  EXPECT_FALSE(data.empty());
431  EXPECT_TRUE(op.has_type());
432  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF,
433            op.type());
434}
435
436TEST_F(DeltaDiffUtilsTest, IsNoopOperationTest) {
437  DeltaArchiveManifest_InstallOperation op;
438  op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
439  EXPECT_FALSE(diff_utils::IsNoopOperation(op));
440  op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
441  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
442  *(op.add_src_extents()) = ExtentForRange(3, 2);
443  *(op.add_dst_extents()) = ExtentForRange(3, 2);
444  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
445  *(op.add_src_extents()) = ExtentForRange(7, 5);
446  *(op.add_dst_extents()) = ExtentForRange(7, 5);
447  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
448  *(op.add_src_extents()) = ExtentForRange(20, 2);
449  *(op.add_dst_extents()) = ExtentForRange(20, 1);
450  *(op.add_dst_extents()) = ExtentForRange(21, 1);
451  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
452  *(op.add_src_extents()) = ExtentForRange(24, 1);
453  *(op.add_dst_extents()) = ExtentForRange(25, 1);
454  EXPECT_FALSE(diff_utils::IsNoopOperation(op));
455}
456
457TEST_F(DeltaDiffUtilsTest, FilterNoopOperations) {
458  AnnotatedOperation aop1;
459  aop1.op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
460  *(aop1.op.add_dst_extents()) = ExtentForRange(3, 2);
461  aop1.name = "aop1";
462
463  AnnotatedOperation aop2 = aop1;
464  aop2.name = "aop2";
465
466  AnnotatedOperation noop;
467  noop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
468  *(noop.op.add_src_extents()) = ExtentForRange(3, 2);
469  *(noop.op.add_dst_extents()) = ExtentForRange(3, 2);
470  noop.name = "noop";
471
472  vector<AnnotatedOperation> ops = {noop, aop1, noop, noop, aop2, noop};
473  diff_utils::FilterNoopOperations(&ops);
474  EXPECT_EQ(2u, ops.size());
475  EXPECT_EQ("aop1", ops[0].name);
476  EXPECT_EQ("aop2", ops[1].name);
477}
478
479}  // namespace chromeos_update_engine
480