Home | History | Annotate | Download | only in payload_generator
      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 
     36 using std::string;
     37 using std::vector;
     38 
     39 namespace chromeos_update_engine {
     40 
     41 namespace {
     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.
     46 bool 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|.
     71 void 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.
     86 bool 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 
    106 class 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     version.imgdiff_allowed = true;  // Assume no fingerprint mismatch.
    135     return diff_utils::DeltaMovedAndZeroBlocks(&aops_,
    136                                                old_part_.path,
    137                                                new_part_.path,
    138                                                old_part_.size / block_size_,
    139                                                new_part_.size / block_size_,
    140                                                chunk_blocks,
    141                                                version,
    142                                                &blob_file,
    143                                                &old_visited_blocks_,
    144                                                &new_visited_blocks_);
    145   }
    146 
    147   // Old and new temporary partitions used in the tests. These are initialized
    148   // with
    149   PartitionConfig old_part_{"part"};
    150   PartitionConfig new_part_{"part"};
    151 
    152   // The file holding the output blob from the various diff utils functions.
    153   string blob_path_;
    154   int blob_fd_{-1};
    155   off_t blob_size_{0};
    156 
    157   size_t block_size_{kBlockSize};
    158 
    159   // Default input/output arguments used when calling DeltaMovedAndZeroBlocks().
    160   vector<AnnotatedOperation> aops_;
    161   ExtentRanges old_visited_blocks_;
    162   ExtentRanges new_visited_blocks_;
    163 };
    164 
    165 TEST_F(DeltaDiffUtilsTest, MoveSmallTest) {
    166   brillo::Blob data_blob(block_size_);
    167   test_utils::FillWithData(&data_blob);
    168 
    169   // The old file is on a different block than the new one.
    170   vector<Extent> old_extents = { ExtentForRange(11, 1) };
    171   vector<Extent> new_extents = { ExtentForRange(1, 1) };
    172 
    173   EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
    174   EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
    175 
    176   brillo::Blob data;
    177   InstallOperation op;
    178   EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
    179       old_part_.path,
    180       new_part_.path,
    181       old_extents,
    182       new_extents,
    183       PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
    184       &data,
    185       &op));
    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 
    201 TEST_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       PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
    243       &data,
    244       &op));
    245 
    246   EXPECT_TRUE(data.empty());
    247 
    248   EXPECT_TRUE(op.has_type());
    249   EXPECT_EQ(InstallOperation::MOVE, op.type());
    250   EXPECT_FALSE(op.has_data_offset());
    251   EXPECT_FALSE(op.has_data_length());
    252 
    253   // The expected old and new extents that actually moved. See comment above.
    254   old_extents = {
    255       ExtentForRange(20, 1),
    256       ExtentForRange(23, 1),
    257       ExtentForRange(28, 1) };
    258   new_extents = {
    259       ExtentForRange(18, 1),
    260       ExtentForRange(20, 1),
    261       ExtentForRange(26, 1) };
    262   num_blocks = BlocksInExtents(old_extents);
    263 
    264   EXPECT_EQ(num_blocks * kBlockSize, op.src_length());
    265   EXPECT_EQ(num_blocks * kBlockSize, op.dst_length());
    266 
    267   EXPECT_EQ(old_extents.size(), static_cast<size_t>(op.src_extents_size()));
    268   for (int i = 0; i < op.src_extents_size(); i++) {
    269     EXPECT_EQ(old_extents[i].start_block(), op.src_extents(i).start_block())
    270         << "i == " << i;
    271     EXPECT_EQ(old_extents[i].num_blocks(), op.src_extents(i).num_blocks())
    272         << "i == " << i;
    273   }
    274 
    275   EXPECT_EQ(new_extents.size(), static_cast<size_t>(op.dst_extents_size()));
    276   for (int i = 0; i < op.dst_extents_size(); i++) {
    277     EXPECT_EQ(new_extents[i].start_block(), op.dst_extents(i).start_block())
    278         << "i == " << i;
    279     EXPECT_EQ(new_extents[i].num_blocks(), op.dst_extents(i).num_blocks())
    280         << "i == " << i;
    281   }
    282 }
    283 
    284 TEST_F(DeltaDiffUtilsTest, BsdiffSmallTest) {
    285   // Test a BSDIFF operation from block 1 to block 2.
    286   brillo::Blob data_blob(kBlockSize);
    287   test_utils::FillWithData(&data_blob);
    288 
    289   // The old file is on a different block than the new one.
    290   vector<Extent> old_extents = { ExtentForRange(1, 1) };
    291   vector<Extent> new_extents = { ExtentForRange(2, 1) };
    292 
    293   EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
    294   // Modify one byte in the new file.
    295   data_blob[0]++;
    296   EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
    297 
    298   brillo::Blob data;
    299   InstallOperation op;
    300   EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
    301       old_part_.path,
    302       new_part_.path,
    303       old_extents,
    304       new_extents,
    305       PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
    306       &data,
    307       &op));
    308 
    309   EXPECT_FALSE(data.empty());
    310 
    311   EXPECT_TRUE(op.has_type());
    312   EXPECT_EQ(InstallOperation::BSDIFF, op.type());
    313   EXPECT_FALSE(op.has_data_offset());
    314   EXPECT_FALSE(op.has_data_length());
    315   EXPECT_EQ(1, op.src_extents_size());
    316   EXPECT_EQ(kBlockSize, op.src_length());
    317   EXPECT_EQ(1, op.dst_extents_size());
    318   EXPECT_EQ(kBlockSize, op.dst_length());
    319   EXPECT_EQ(BlocksInExtents(op.src_extents()),
    320             BlocksInExtents(op.dst_extents()));
    321   EXPECT_EQ(1U, BlocksInExtents(op.dst_extents()));
    322 }
    323 
    324 TEST_F(DeltaDiffUtilsTest, ReplaceSmallTest) {
    325   // The old file is on a different block than the new one.
    326   vector<Extent> old_extents = { ExtentForRange(1, 1) };
    327   vector<Extent> new_extents = { ExtentForRange(2, 1) };
    328 
    329   // Make a blob that's just 1's that will compress well.
    330   brillo::Blob ones(kBlockSize, 1);
    331 
    332   // Make a blob with random data that won't compress well.
    333   brillo::Blob random_data;
    334   std::mt19937 gen(12345);
    335   std::uniform_int_distribution<uint8_t> dis(0, 255);
    336   for (uint32_t i = 0; i < kBlockSize; i++) {
    337     random_data.push_back(dis(gen));
    338   }
    339 
    340   for (int i = 0; i < 2; i++) {
    341     brillo::Blob data_to_test = i == 0 ? random_data : ones;
    342     // The old_extents will be initialized with 0.
    343     EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize,
    344                              data_to_test));
    345 
    346     brillo::Blob data;
    347     InstallOperation op;
    348     EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
    349         old_part_.path,
    350         new_part_.path,
    351         old_extents,
    352         new_extents,
    353         PayloadVersion(kChromeOSMajorPayloadVersion,
    354                        kInPlaceMinorPayloadVersion),
    355         &data,
    356         &op));
    357     EXPECT_FALSE(data.empty());
    358 
    359     EXPECT_TRUE(op.has_type());
    360     const InstallOperation_Type expected_type =
    361         (i == 0 ? InstallOperation::REPLACE : InstallOperation::REPLACE_BZ);
    362     EXPECT_EQ(expected_type, op.type());
    363     EXPECT_FALSE(op.has_data_offset());
    364     EXPECT_FALSE(op.has_data_length());
    365     EXPECT_EQ(0, op.src_extents_size());
    366     EXPECT_FALSE(op.has_src_length());
    367     EXPECT_EQ(1, op.dst_extents_size());
    368     EXPECT_EQ(data_to_test.size(), op.dst_length());
    369     EXPECT_EQ(1U, BlocksInExtents(op.dst_extents()));
    370   }
    371 }
    372 
    373 TEST_F(DeltaDiffUtilsTest, SourceCopyTest) {
    374   // Makes sure SOURCE_COPY operations are emitted whenever src_ops_allowed
    375   // is true. It is the same setup as MoveSmallTest, which checks that
    376   // the operation is well-formed.
    377   brillo::Blob data_blob(kBlockSize);
    378   test_utils::FillWithData(&data_blob);
    379 
    380   // The old file is on a different block than the new one.
    381   vector<Extent> old_extents = { ExtentForRange(11, 1) };
    382   vector<Extent> new_extents = { ExtentForRange(1, 1) };
    383 
    384   EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
    385   EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
    386 
    387   brillo::Blob data;
    388   InstallOperation op;
    389   EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
    390       old_part_.path,
    391       new_part_.path,
    392       old_extents,
    393       new_extents,
    394       PayloadVersion(kChromeOSMajorPayloadVersion, kSourceMinorPayloadVersion),
    395       &data,
    396       &op));
    397   EXPECT_TRUE(data.empty());
    398 
    399   EXPECT_TRUE(op.has_type());
    400   EXPECT_EQ(InstallOperation::SOURCE_COPY, op.type());
    401 }
    402 
    403 TEST_F(DeltaDiffUtilsTest, SourceBsdiffTest) {
    404   // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
    405   // is true. It is the same setup as BsdiffSmallTest, which checks
    406   // that the operation is well-formed.
    407   brillo::Blob data_blob(kBlockSize);
    408   test_utils::FillWithData(&data_blob);
    409 
    410   // The old file is on a different block than the new one.
    411   vector<Extent> old_extents = { ExtentForRange(1, 1) };
    412   vector<Extent> new_extents = { ExtentForRange(2, 1) };
    413 
    414   EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
    415   // Modify one byte in the new file.
    416   data_blob[0]++;
    417   EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
    418 
    419   brillo::Blob data;
    420   InstallOperation op;
    421   EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
    422       old_part_.path,
    423       new_part_.path,
    424       old_extents,
    425       new_extents,
    426       PayloadVersion(kChromeOSMajorPayloadVersion, kSourceMinorPayloadVersion),
    427       &data,
    428       &op));
    429 
    430   EXPECT_FALSE(data.empty());
    431   EXPECT_TRUE(op.has_type());
    432   EXPECT_EQ(InstallOperation::SOURCE_BSDIFF, op.type());
    433 }
    434 
    435 TEST_F(DeltaDiffUtilsTest, IsNoopOperationTest) {
    436   InstallOperation op;
    437   op.set_type(InstallOperation::REPLACE_BZ);
    438   EXPECT_FALSE(diff_utils::IsNoopOperation(op));
    439   op.set_type(InstallOperation::MOVE);
    440   EXPECT_TRUE(diff_utils::IsNoopOperation(op));
    441   *(op.add_src_extents()) = ExtentForRange(3, 2);
    442   *(op.add_dst_extents()) = ExtentForRange(3, 2);
    443   EXPECT_TRUE(diff_utils::IsNoopOperation(op));
    444   *(op.add_src_extents()) = ExtentForRange(7, 5);
    445   *(op.add_dst_extents()) = ExtentForRange(7, 5);
    446   EXPECT_TRUE(diff_utils::IsNoopOperation(op));
    447   *(op.add_src_extents()) = ExtentForRange(20, 2);
    448   *(op.add_dst_extents()) = ExtentForRange(20, 1);
    449   *(op.add_dst_extents()) = ExtentForRange(21, 1);
    450   EXPECT_TRUE(diff_utils::IsNoopOperation(op));
    451   *(op.add_src_extents()) = ExtentForRange(24, 1);
    452   *(op.add_dst_extents()) = ExtentForRange(25, 1);
    453   EXPECT_FALSE(diff_utils::IsNoopOperation(op));
    454 }
    455 
    456 TEST_F(DeltaDiffUtilsTest, FilterNoopOperations) {
    457   AnnotatedOperation aop1;
    458   aop1.op.set_type(InstallOperation::REPLACE_BZ);
    459   *(aop1.op.add_dst_extents()) = ExtentForRange(3, 2);
    460   aop1.name = "aop1";
    461 
    462   AnnotatedOperation aop2 = aop1;
    463   aop2.name = "aop2";
    464 
    465   AnnotatedOperation noop;
    466   noop.op.set_type(InstallOperation::MOVE);
    467   *(noop.op.add_src_extents()) = ExtentForRange(3, 2);
    468   *(noop.op.add_dst_extents()) = ExtentForRange(3, 2);
    469   noop.name = "noop";
    470 
    471   vector<AnnotatedOperation> ops = {noop, aop1, noop, noop, aop2, noop};
    472   diff_utils::FilterNoopOperations(&ops);
    473   EXPECT_EQ(2u, ops.size());
    474   EXPECT_EQ("aop1", ops[0].name);
    475   EXPECT_EQ("aop2", ops[1].name);
    476 }
    477 
    478 // Test the simple case where all the blocks are different and no new blocks are
    479 // zeroed.
    480 TEST_F(DeltaDiffUtilsTest, NoZeroedOrUniqueBlocksDetected) {
    481   InitializePartitionWithUniqueBlocks(old_part_, block_size_, 5);
    482   InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
    483 
    484   EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
    485                                          kInPlaceMinorPayloadVersion));
    486 
    487   EXPECT_EQ(0U, old_visited_blocks_.blocks());
    488   EXPECT_EQ(0U, new_visited_blocks_.blocks());
    489   EXPECT_EQ(0, blob_size_);
    490   EXPECT_TRUE(aops_.empty());
    491 }
    492 
    493 // Test that when the partitions have identical blocks in the same positions no
    494 // MOVE operation is performed and all the blocks are handled.
    495 TEST_F(DeltaDiffUtilsTest, IdenticalPartitionsDontMove) {
    496   InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
    497   InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
    498 
    499   // Mark some of the blocks as already visited.
    500   vector<Extent> already_visited = {ExtentForRange(5, 10),
    501                                     ExtentForRange(25, 10)};
    502   old_visited_blocks_.AddExtents(already_visited);
    503   new_visited_blocks_.AddExtents(already_visited);
    504 
    505   // Most of the blocks rest in the same place, but there's no need for MOVE
    506   // operations on those blocks.
    507   EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
    508                                          kInPlaceMinorPayloadVersion));
    509 
    510   EXPECT_EQ(kDefaultBlockCount, old_visited_blocks_.blocks());
    511   EXPECT_EQ(kDefaultBlockCount, new_visited_blocks_.blocks());
    512   EXPECT_EQ(0, blob_size_);
    513   EXPECT_TRUE(aops_.empty());
    514 }
    515 
    516 // Test that when the partitions have identical blocks in the same positions
    517 // MOVE operation is performed and all the blocks are handled.
    518 TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedFromSource) {
    519   // We use a smaller partition for this test.
    520   old_part_.size = kBlockSize * 50;
    521   new_part_.size = kBlockSize * 50;
    522 
    523   InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
    524   InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
    525 
    526   // Mark some of the blocks as already visited.
    527   vector<Extent> already_visited = {ExtentForRange(5, 5),
    528                                     ExtentForRange(25, 7)};
    529   old_visited_blocks_.AddExtents(already_visited);
    530   new_visited_blocks_.AddExtents(already_visited);
    531 
    532   // Override some of the old blocks with different data.
    533   vector<Extent> different_blocks = {ExtentForRange(40, 5)};
    534   EXPECT_TRUE(WriteExtents(old_part_.path, different_blocks, kBlockSize,
    535                            brillo::Blob(5 * kBlockSize, 'a')));
    536 
    537   EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(10,  // chunk_blocks
    538                                          kSourceMinorPayloadVersion));
    539 
    540   ExtentRanges expected_ranges;
    541   expected_ranges.AddExtent(ExtentForRange(0, 50));
    542   expected_ranges.SubtractExtents(different_blocks);
    543 
    544   EXPECT_EQ(expected_ranges.extent_set(), old_visited_blocks_.extent_set());
    545   EXPECT_EQ(expected_ranges.extent_set(), new_visited_blocks_.extent_set());
    546   EXPECT_EQ(0, blob_size_);
    547 
    548   // We expect all the blocks that we didn't override with |different_blocks|
    549   // and that we didn't mark as visited in |already_visited| to match and have a
    550   // SOURCE_COPY operation chunked at 10 blocks.
    551   vector<Extent> expected_op_extents = {
    552       ExtentForRange(0, 5),
    553       ExtentForRange(10, 10),
    554       ExtentForRange(20, 5),
    555       ExtentForRange(32, 8),
    556       ExtentForRange(45, 5),
    557   };
    558 
    559   EXPECT_EQ(expected_op_extents.size(), aops_.size());
    560   for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) {
    561     SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i));
    562     const AnnotatedOperation& aop = aops_[i];
    563     EXPECT_EQ(InstallOperation::SOURCE_COPY, aop.op.type());
    564     EXPECT_EQ(1, aop.op.src_extents_size());
    565     EXPECT_EQ(expected_op_extents[i], aop.op.src_extents(0));
    566     EXPECT_EQ(1, aop.op.dst_extents_size());
    567     EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0));
    568   }
    569 }
    570 
    571 TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedInOder) {
    572   // We use a smaller partition for this test.
    573   old_part_.size = block_size_ * 50;
    574   new_part_.size = block_size_ * 50;
    575 
    576   // Create two identical partitions with 5 copies of the same unique "file".
    577   brillo::Blob file_data(block_size_ * 10, 'a');
    578   for (size_t offset = 0; offset < file_data.size(); offset += block_size_)
    579     file_data[offset] = 'a' + offset / block_size_;
    580 
    581   brillo::Blob partition_data(old_part_.size);
    582   for (size_t offset = 0; offset < partition_data.size();
    583        offset += file_data.size()) {
    584     std::copy(file_data.begin(), file_data.end(),
    585               partition_data.begin() + offset);
    586   }
    587   EXPECT_TRUE(test_utils::WriteFileVector(old_part_.path, partition_data));
    588   EXPECT_TRUE(test_utils::WriteFileVector(new_part_.path, partition_data));
    589 
    590   EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
    591                                          kSourceMinorPayloadVersion));
    592 
    593   // There should be only one SOURCE_COPY, for the whole partition and the
    594   // source extents should cover only the first copy of the source file since
    595   // we prefer to re-read files (maybe cached) instead of continue reading the
    596   // rest of the partition.
    597   EXPECT_EQ(1U, aops_.size());
    598   const AnnotatedOperation& aop = aops_[0];
    599   EXPECT_EQ(InstallOperation::SOURCE_COPY, aop.op.type());
    600   EXPECT_EQ(5, aop.op.src_extents_size());
    601   for (int i = 0; i < aop.op.src_extents_size(); ++i) {
    602     EXPECT_EQ(ExtentForRange(0, 10), aop.op.src_extents(i));
    603   }
    604 
    605   EXPECT_EQ(1, aop.op.dst_extents_size());
    606   EXPECT_EQ(ExtentForRange(0, 50), aop.op.dst_extents(0));
    607 
    608   EXPECT_EQ(0, blob_size_);
    609 }
    610 
    611 // Test that all blocks with zeros are handled separately using REPLACE_BZ
    612 // operations unless they are not moved.
    613 TEST_F(DeltaDiffUtilsTest, ZeroBlocksUseReplaceBz) {
    614   InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
    615   InitializePartitionWithUniqueBlocks(new_part_, block_size_, 5);
    616 
    617   // We set four ranges of blocks with zeros: a single block, a range that fits
    618   // in the chunk size, a range that doesn't and finally a range of zeros that
    619   // was also zeros in the old image.
    620   vector<Extent> new_zeros = {
    621       ExtentForRange(10, 1),
    622       ExtentForRange(20, 4),
    623       // The last range is split since the old image has zeros in part of it.
    624       ExtentForRange(30, 20),
    625   };
    626   brillo::Blob zeros_data(BlocksInExtents(new_zeros) * block_size_, '\0');
    627   EXPECT_TRUE(WriteExtents(new_part_.path, new_zeros, block_size_, zeros_data));
    628 
    629   vector<Extent> old_zeros = vector<Extent>{ExtentForRange(43, 7)};
    630   EXPECT_TRUE(WriteExtents(old_part_.path, old_zeros, block_size_, zeros_data));
    631 
    632   EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(5,  // chunk_blocks
    633                                          kInPlaceMinorPayloadVersion));
    634 
    635   // Zeroed blocks from old_visited_blocks_ were copied over, so me actually
    636   // use them regardless of the trivial MOVE operation not being emitted.
    637   EXPECT_EQ(old_zeros,
    638             old_visited_blocks_.GetExtentsForBlockCount(
    639                 old_visited_blocks_.blocks()));
    640 
    641   // All the new zeroed blocks should be used, part with REPLACE_BZ and part
    642   // trivial MOVE operations (not included).
    643   EXPECT_EQ(new_zeros,
    644             new_visited_blocks_.GetExtentsForBlockCount(
    645                 new_visited_blocks_.blocks()));
    646 
    647   vector<Extent> expected_op_extents = {
    648       ExtentForRange(10, 1),
    649       ExtentForRange(20, 4),
    650       // This range should be split.
    651       ExtentForRange(30, 5),
    652       ExtentForRange(35, 5),
    653       ExtentForRange(40, 3),
    654   };
    655 
    656   EXPECT_EQ(expected_op_extents.size(), aops_.size());
    657   for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) {
    658     SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i));
    659     const AnnotatedOperation& aop = aops_[i];
    660     EXPECT_EQ(InstallOperation::REPLACE_BZ, aop.op.type());
    661     EXPECT_EQ(0, aop.op.src_extents_size());
    662     EXPECT_EQ(1, aop.op.dst_extents_size());
    663     EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0));
    664   }
    665   EXPECT_NE(0, blob_size_);
    666 }
    667 
    668 TEST_F(DeltaDiffUtilsTest, ShuffledBlocksAreTracked) {
    669   vector<uint64_t> permutation = {0, 1, 5, 6, 7, 2, 3, 4, 9, 10, 11, 12, 8};
    670   vector<Extent> perm_extents;
    671   for (uint64_t x : permutation)
    672     AppendBlockToExtents(&perm_extents, x);
    673 
    674   // We use a smaller partition for this test.
    675   old_part_.size = block_size_ * permutation.size();
    676   new_part_.size = block_size_ * permutation.size();
    677   InitializePartitionWithUniqueBlocks(new_part_, block_size_, 123);
    678 
    679   // We initialize the old_part_ with the blocks from new_part but in the
    680   // |permutation| order. Block i in the old_part_ will contain the same data
    681   // as block permutation[i] in the new_part_.
    682   brillo::Blob new_contents;
    683   EXPECT_TRUE(utils::ReadFile(new_part_.path, &new_contents));
    684   EXPECT_TRUE(WriteExtents(old_part_.path, perm_extents, block_size_,
    685                            new_contents));
    686 
    687   EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
    688                                          kSourceMinorPayloadVersion));
    689 
    690   EXPECT_EQ(permutation.size(), old_visited_blocks_.blocks());
    691   EXPECT_EQ(permutation.size(), new_visited_blocks_.blocks());
    692 
    693   // There should be only one SOURCE_COPY, with a complicate list of extents.
    694   EXPECT_EQ(1U, aops_.size());
    695   const AnnotatedOperation& aop = aops_[0];
    696   EXPECT_EQ(InstallOperation::SOURCE_COPY, aop.op.type());
    697   vector<Extent> aop_src_extents;
    698   ExtentsToVector(aop.op.src_extents(), &aop_src_extents);
    699   EXPECT_EQ(perm_extents, aop_src_extents);
    700 
    701   EXPECT_EQ(1, aop.op.dst_extents_size());
    702   EXPECT_EQ(ExtentForRange(0, permutation.size()), aop.op.dst_extents(0));
    703 
    704   EXPECT_EQ(0, blob_size_);
    705 }
    706 
    707 TEST_F(DeltaDiffUtilsTest, IsExtFilesystemTest) {
    708   EXPECT_TRUE(diff_utils::IsExtFilesystem(
    709       test_utils::GetBuildArtifactsPath("gen/disk_ext2_1k.img")));
    710   EXPECT_TRUE(diff_utils::IsExtFilesystem(
    711       test_utils::GetBuildArtifactsPath("gen/disk_ext2_4k.img")));
    712 }
    713 
    714 }  // namespace chromeos_update_engine
    715