update_engine: Handle moved and zero blocks in payload generation.
Delta generation uses only the file name to detect when files changed.
Therefore, renaming a file doesn't get detected and the new name is
assumed to be a new file. On the other hand, free-space blocks are
often just zeros so they can be easilly encoded independently from the
rest.
This patch detects blocks that moved and blocks with zeros and handles
those blocks beforehand regardless of where are they in the filesystem
(file data, metadata, free space, etc). For blocks that moved,
SOURCE_COPY or MOVE operations are created as needed. For blocks with
zeros we use REPLACE_BZ operations.
Blocks processed in this way will be excluded from other files,
metadata or free space processing done. This solves perfomance issues
when trying to process with bsdiff files with very long runs of zeros.
CQ-DEPEND=CL:283643
BUG=chromium:504445
TEST=Unittest added. Run delta_generator between cid canary 7195 and
7201 and it doesn't take forever to finish.
Change-Id: I892fe7456608e83a2946133da335eb4fbd19a645
Reviewed-on: https://chromium-review.googlesource.com/283172
Commit-Queue: Alex Deymo <deymo@chromium.org>
Trybot-Ready: Alex Deymo <deymo@chromium.org>
Tested-by: Alex Deymo <deymo@chromium.org>
Reviewed-by: Alex Deymo <deymo@chromium.org>
Reviewed-by: Gilad Arnold <garnold@chromium.org>
diff --git a/payload_generator/block_mapping.cc b/payload_generator/block_mapping.cc
new file mode 100644
index 0000000..734f44f
--- /dev/null
+++ b/payload_generator/block_mapping.cc
@@ -0,0 +1,149 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/payload_generator/block_mapping.h"
+
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <functional>
+#include <string>
+#include <vector>
+
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace {
+
+size_t HashValue(const chromeos::Blob& blob) {
+ std::hash<string> hash_fn;
+ return hash_fn(string(blob.begin(), blob.end()));
+}
+
+} // namespace
+
+namespace chromeos_update_engine {
+
+BlockMapping::BlockId BlockMapping::AddBlock(const chromeos::Blob& block_data) {
+ return AddBlock(-1, 0, block_data);
+}
+
+BlockMapping::BlockId BlockMapping::AddDiskBlock(int fd, off_t byte_offset) {
+ chromeos::Blob blob(block_size_);
+ ssize_t bytes_read = 0;
+ if (!utils::PReadAll(fd, blob.data(), block_size_, byte_offset, &bytes_read))
+ return -1;
+ if (static_cast<size_t>(bytes_read) != block_size_)
+ return -1;
+ return AddBlock(fd, byte_offset, blob);
+}
+
+bool BlockMapping::AddManyDiskBlocks(int fd,
+ off_t initial_byte_offset,
+ size_t num_blocks,
+ std::vector<BlockId>* block_ids) {
+ bool ret = true;
+ block_ids->resize(num_blocks);
+ for (size_t block = 0; block < num_blocks; block++) {
+ (*block_ids)[block] = AddDiskBlock(
+ fd, initial_byte_offset + block * block_size_);
+ ret = ret && (*block_ids)[block] != -1;
+ }
+ return ret;
+}
+
+BlockMapping::BlockId BlockMapping::AddBlock(int fd,
+ off_t byte_offset,
+ const chromeos::Blob& block_data) {
+ if (block_data.size() != block_size_)
+ return -1;
+ size_t h = HashValue(block_data);
+
+ // We either reuse a UniqueBlock or create a new one. If we need a new
+ // UniqueBlock it could also be part of a new or existing bucket (if there is
+ // a hash collision).
+ vector<UniqueBlock> *bucket = nullptr;
+
+ auto mapping_it = mapping_.find(h);
+ if (mapping_it == mapping_.end()) {
+ bucket = &mapping_[h];
+ } else {
+ for (UniqueBlock& existing_block : mapping_it->second) {
+ bool equals = false;
+ if (!existing_block.CompareData(block_data, &equals))
+ return -1;
+ if (equals)
+ return existing_block.block_id;
+ }
+ bucket = &mapping_it->second;
+ }
+
+ // No existing block was found at this point, so we create and fill in a new
+ // one.
+ bucket->emplace_back();
+ UniqueBlock *new_ublock = &bucket->back();
+
+ new_ublock->times_read = 1;
+ new_ublock->fd = fd;
+ new_ublock->byte_offset = byte_offset;
+ new_ublock->block_id = used_block_ids++;
+ // We need to cache blocks that are not referencing any disk location.
+ if (fd == -1)
+ new_ublock->block_data = block_data;
+
+ return new_ublock->block_id;
+}
+
+bool BlockMapping::UniqueBlock::CompareData(const chromeos::Blob& other_block,
+ bool* equals) {
+ if (!block_data.empty()) {
+ *equals = block_data == other_block;
+ return true;
+ }
+ const size_t block_size = other_block.size();
+ chromeos::Blob blob(block_size);
+ ssize_t bytes_read = 0;
+ if (!utils::PReadAll(fd, blob.data(), block_size, byte_offset, &bytes_read))
+ return false;
+ if (static_cast<size_t>(bytes_read) != block_size)
+ return false;
+ *equals = blob == other_block;
+
+ // We increase the number of times we had to read this block from disk and
+ // we cache this block based on that. This caching method is optimized for
+ // the common use case of having two partitions that share blocks between them
+ // but have few repeated blocks inside each partition, such as the block
+ // with all zeros or duplicated files.
+ times_read++;
+ if (times_read > 3)
+ block_data = std::move(blob);
+ return true;
+}
+
+bool MapPartitionBlocks(const string& old_part,
+ const string& new_part,
+ size_t old_size,
+ size_t new_size,
+ size_t block_size,
+ vector<BlockMapping::BlockId>* old_block_ids,
+ vector<BlockMapping::BlockId>* new_block_ids) {
+ BlockMapping mapping(block_size);
+ if (mapping.AddBlock(chromeos::Blob(block_size, '\0')) != 0)
+ return false;
+ int old_fd = HANDLE_EINTR(open(old_part.c_str(), O_RDONLY));
+ int new_fd = HANDLE_EINTR(open(new_part.c_str(), O_RDONLY));
+ ScopedFdCloser old_fd_closer(&old_fd);
+ ScopedFdCloser new_fd_closer(&new_fd);
+
+ TEST_AND_RETURN_FALSE(mapping.AddManyDiskBlocks(
+ old_fd, 0, old_size / block_size, old_block_ids));
+ TEST_AND_RETURN_FALSE(mapping.AddManyDiskBlocks(
+ new_fd, 0, new_size / block_size, new_block_ids));
+ return true;
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/block_mapping.h b/payload_generator/block_mapping.h
new file mode 100644
index 0000000..2cfca56
--- /dev/null
+++ b/payload_generator/block_mapping.h
@@ -0,0 +1,100 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_BLOCK_MAPPING_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_BLOCK_MAPPING_H_
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include <chromeos/secure_blob.h>
+#include <gtest/gtest_prod.h> // for FRIEND_TEST
+
+#include "update_engine/payload_generator/payload_generation_config.h"
+
+namespace chromeos_update_engine {
+
+// BlockMapping allows to map data blocks (chromeos::Blobs of block_size size)
+// into unique integer values called "block ids". This mapping differs from a
+// hash function in that two blocks with the same data will have the same id but
+// also two blocks with the same id will have the same data. This is only valid
+// in the context of the same BlockMapping instance.
+class BlockMapping {
+ public:
+ using BlockId = int64_t;
+
+ explicit BlockMapping(size_t block_size) : block_size_(block_size) {}
+
+ // Add a single data block to the mapping. Returns its unique block id.
+ // In case of error returns -1.
+ BlockId AddBlock(const chromeos::Blob& block_data);
+
+ // Add a block from disk reading it from the file descriptor |fd| from the
+ // offset in bytes |byte_offset|. The data block may or may not be cached, so
+ // the file descriptor must be available until the BlockMapping is destroyed.
+ // Returns the unique block id of the added block or -1 in case of error.
+ BlockId AddDiskBlock(int fd, off_t byte_offset);
+
+ // This is a helper method to add |num_blocks| contiguous blocks reading them
+ // from the file descriptor |fd| starting at offset |initial_byte_offset|.
+ // Returns whether it succeeded to add all the disk blocks and stores in
+ // |block_ids| the block id for each one of the added blocks.
+ bool AddManyDiskBlocks(int fd, off_t initial_byte_offset, size_t num_blocks,
+ std::vector<BlockId>* block_ids);
+
+ private:
+ FRIEND_TEST(BlockMappingTest, BlocksAreNotKeptInMemory);
+
+ // Add a single block passed in |block_data|. If |fd| is not -1, the block
+ // can be discarded to save RAM and retrieved later from |fd| at the position
+ // |byte_offset|.
+ BlockId AddBlock(int fd, off_t byte_offset, const chromeos::Blob& block_data);
+
+ size_t block_size_;
+
+ BlockId used_block_ids{0};
+
+ // The UniqueBlock represents the data of a block associated to a unique
+ // block id.
+ struct UniqueBlock {
+ chromeos::Blob block_data;
+
+ // The block id assigned to this unique block.
+ BlockId block_id;
+
+ // The location on this unique block on disk (if not cached in block_data).
+ int fd{-1};
+ off_t byte_offset{0};
+
+ // Number of times we have seen this data block. Used for caching.
+ uint32_t times_read{0};
+
+ // Compares the UniqueBlock data with the other_block data and stores if
+ // they are equal in |equals|. Returns whether there was an error reading
+ // the block from disk while comparing it.
+ bool CompareData(const chromeos::Blob& other_block, bool* equals);
+ };
+
+ // A mapping from hash values to possible block ids.
+ std::map<size_t, std::vector<UniqueBlock>> mapping_;
+};
+
+// Maps the blocks of the old and new partitions |old_part| and |new_part| whose
+// size in bytes are |old_size| and |new_size| into block ids where two blocks
+// with the same data will have the same block id and vice versa, regardless of
+// the partition they are on.
+// The block ids number 0 corresponds to the block with all zeros, but any
+// other block id number is assigned randomly.
+bool MapPartitionBlocks(const std::string& old_part,
+ const std::string& new_part,
+ size_t old_size,
+ size_t new_size,
+ size_t block_size,
+ std::vector<BlockMapping::BlockId>* old_block_ids,
+ std::vector<BlockMapping::BlockId>* new_block_ids);
+
+} // namespace chromeos_update_engine
+
+#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_BLOCK_MAPPING_H_
diff --git a/payload_generator/block_mapping_unittest.cc b/payload_generator/block_mapping_unittest.cc
new file mode 100644
index 0000000..699ac60
--- /dev/null
+++ b/payload_generator/block_mapping_unittest.cc
@@ -0,0 +1,122 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/payload_generator/block_mapping.h"
+
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <string>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+} // namespace
+
+class BlockMappingTest : public ::testing::Test {
+ protected:
+ void SetUp() override {
+ EXPECT_TRUE(utils::MakeTempFile("BlockMappingTest_old.XXXXXX",
+ &old_part_path_,
+ nullptr));
+ EXPECT_TRUE(utils::MakeTempFile("BlockMappingTest_new.XXXXXX",
+ &new_part_path_,
+ nullptr));
+
+ old_part_unlinker_.reset(new ScopedPathUnlinker(old_part_path_));
+ new_part_unlinker_.reset(new ScopedPathUnlinker(new_part_path_));
+ }
+
+ // Old new partition files used in testing.
+ string old_part_path_;
+ string new_part_path_;
+ std::unique_ptr<ScopedPathUnlinker> old_part_unlinker_;
+ std::unique_ptr<ScopedPathUnlinker> new_part_unlinker_;
+
+ size_t block_size_{1024};
+ BlockMapping bm_{block_size_}; // BlockMapping under test.
+};
+
+TEST_F(BlockMappingTest, FirstAddedBlockIsZero) {
+ chromeos::Blob blob(block_size_);
+ // The BlockMapping just assigns the block ids in order, so it doesn't matter
+ // what are the contents of the first block.
+ blob[0] = 42;
+ EXPECT_EQ(0, bm_.AddBlock(blob));
+ blob[0] = 5;
+ EXPECT_EQ(1, bm_.AddBlock(blob));
+}
+
+TEST_F(BlockMappingTest, BlocksAreNotKeptInMemory) {
+ test_utils::WriteFileString(old_part_path_, string(block_size_, 'a'));
+ int old_fd = HANDLE_EINTR(open(old_part_path_.c_str(), O_RDONLY));
+ ScopedFdCloser old_fd_closer(&old_fd);
+
+ EXPECT_EQ(0, bm_.AddDiskBlock(old_fd, 0));
+
+ // Check that the block_data is not stored on memory if we just used the block
+ // once.
+ for (const auto& it : bm_.mapping_) {
+ for (const BlockMapping::UniqueBlock& ublock : it.second) {
+ EXPECT_TRUE(ublock.block_data.empty());
+ }
+ }
+
+ chromeos::Blob block(block_size_, 'a');
+ for (int i = 0; i < 5; ++i) {
+ // Re-add the same block 5 times.
+ EXPECT_EQ(0, bm_.AddBlock(block));
+ }
+
+ for (const auto& it : bm_.mapping_) {
+ for (const BlockMapping::UniqueBlock& ublock : it.second) {
+ EXPECT_FALSE(ublock.block_data.empty());
+ // The block was loaded from disk only 4 times, and after that the counter
+ // is not updated anymore.
+ EXPECT_EQ(4, ublock.times_read);
+ }
+ }
+}
+
+TEST_F(BlockMappingTest, MapPartitionBlocks) {
+ // A string with 10 blocks where all the blocks are different.
+ string old_contents(10 * block_size_, '\0');
+ for (size_t i = 0; i < old_contents.size(); ++i)
+ old_contents[i] = 4 + i / block_size_;
+ test_utils::WriteFileString(old_part_path_, old_contents);
+
+ // A string including the block with all zeros and overlapping some of the
+ // other blocks in old_contents.
+ string new_contents(6 * block_size_, '\0');
+ for (size_t i = 0; i < new_contents.size(); ++i)
+ new_contents[i] = i / block_size_;
+ test_utils::WriteFileString(new_part_path_, new_contents);
+
+ vector<BlockMapping::BlockId> old_ids, new_ids;
+ EXPECT_TRUE(MapPartitionBlocks(old_part_path_,
+ new_part_path_,
+ old_contents.size(),
+ new_contents.size(),
+ block_size_,
+ &old_ids,
+ &new_ids));
+
+ EXPECT_EQ((vector<BlockMapping::BlockId>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}),
+ old_ids);
+ EXPECT_EQ((vector<BlockMapping::BlockId>{0, 11, 12, 13, 1, 2}),
+ new_ids);
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
index 6c15919..2d56b68 100644
--- a/payload_generator/delta_diff_utils.cc
+++ b/payload_generator/delta_diff_utils.cc
@@ -13,6 +13,7 @@
#include "update_engine/bzip.h"
#include "update_engine/omaha_hash_calculator.h"
+#include "update_engine/payload_generator/block_mapping.h"
#include "update_engine/payload_generator/delta_diff_generator.h"
#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/payload_generator/extent_utils.h"
@@ -21,7 +22,6 @@
using std::map;
using std::string;
-using std::unique_ptr;
using std::vector;
namespace chromeos_update_engine {
@@ -160,6 +160,19 @@
new_visited_blocks.AddBlock(0);
}
+ TEST_AND_RETURN_FALSE(DeltaMovedAndZeroBlocks(
+ aops,
+ old_part.path,
+ new_part.path,
+ old_part.fs_interface ? old_part.fs_interface->GetBlockCount() : 0,
+ new_part.fs_interface->GetBlockCount(),
+ chunk_blocks,
+ src_ops_allowed,
+ data_fd,
+ data_file_size,
+ &old_visited_blocks,
+ &new_visited_blocks));
+
map<string, vector<Extent>> old_files_map;
if (old_part.fs_interface) {
vector<FilesystemInterface::File> old_files;
@@ -249,6 +262,152 @@
return true;
}
+bool DeltaMovedAndZeroBlocks(
+ vector<AnnotatedOperation>* aops,
+ const string& old_part,
+ const string& new_part,
+ size_t old_num_blocks,
+ size_t new_num_blocks,
+ off_t chunk_blocks,
+ bool src_ops_allowed,
+ int data_fd,
+ off_t* data_file_size,
+ ExtentRanges* old_visited_blocks,
+ ExtentRanges* new_visited_blocks) {
+ vector<BlockMapping::BlockId> old_block_ids;
+ vector<BlockMapping::BlockId> new_block_ids;
+ TEST_AND_RETURN_FALSE(MapPartitionBlocks(old_part,
+ new_part,
+ old_num_blocks * kBlockSize,
+ new_num_blocks * kBlockSize,
+ kBlockSize,
+ &old_block_ids,
+ &new_block_ids));
+
+ // For minor-version=1, we map all the blocks that didn't move, regardless of
+ // the contents since they are already copied and no operation is required.
+ if (!src_ops_allowed) {
+ uint64_t num_blocks = std::min(old_num_blocks, new_num_blocks);
+ for (uint64_t block = 0; block < num_blocks; block++) {
+ if (old_block_ids[block] == new_block_ids[block] &&
+ !old_visited_blocks->ContainsBlock(block) &&
+ !new_visited_blocks->ContainsBlock(block)) {
+ old_visited_blocks->AddBlock(block);
+ new_visited_blocks->AddBlock(block);
+ }
+ }
+ }
+
+ // A mapping from the block_id to the list of block numbers with that block id
+ // in the old partition. This is used to lookup where in the old partition
+ // is a block from the new partition.
+ map<BlockMapping::BlockId, vector<uint64_t>> old_blocks_map;
+
+ for (uint64_t block = old_num_blocks; block-- > 0; ) {
+ if (old_block_ids[block] != 0 && !old_visited_blocks->ContainsBlock(block))
+ old_blocks_map[old_block_ids[block]].push_back(block);
+ }
+
+ // The collection of blocks in the new partition with just zeros. This is a
+ // common case for free-space that's also problematic for bsdiff, so we want
+ // to optimize it using REPLACE_BZ operations. The blob for a REPLACE_BZ of
+ // just zeros is so small that it doesn't make sense to spend the I/O reading
+ // zeros from the old partition.
+ vector<Extent> new_zeros;
+
+ vector<Extent> old_identical_blocks;
+ vector<Extent> new_identical_blocks;
+
+ for (uint64_t block = 0; block < new_num_blocks; block++) {
+ // Only produce operations for blocks that were not yet visited.
+ if (new_visited_blocks->ContainsBlock(block))
+ continue;
+ if (new_block_ids[block] == 0) {
+ AppendBlockToExtents(&new_zeros, block);
+ continue;
+ }
+
+ auto old_blocks_map_it = old_blocks_map.find(new_block_ids[block]);
+ // Check if the block exists in the old partition at all.
+ if (old_blocks_map_it == old_blocks_map.end() ||
+ old_blocks_map_it->second.empty())
+ continue;
+
+ AppendBlockToExtents(&old_identical_blocks,
+ old_blocks_map_it->second.back());
+ AppendBlockToExtents(&new_identical_blocks, block);
+ // We can't reuse source blocks in minor version 1 because the cycle
+ // breaking algorithm doesn't support that.
+ if (!src_ops_allowed)
+ old_blocks_map_it->second.pop_back();
+ }
+
+ // Produce operations for the zero blocks split per output extent.
+ size_t num_ops = aops->size();
+ new_visited_blocks->AddExtents(new_zeros);
+ for (Extent extent : new_zeros) {
+ TEST_AND_RETURN_FALSE(DeltaReadFile(
+ aops,
+ "",
+ new_part,
+ vector<Extent>(), // old_extents
+ vector<Extent>{extent}, // new_extents
+ "<zeros>",
+ chunk_blocks,
+ data_fd,
+ data_file_size,
+ src_ops_allowed));
+ }
+ LOG(INFO) << "Produced " << (aops->size() - num_ops) << " operations for "
+ << BlocksInExtents(new_zeros) << " zeroed blocks";
+
+ // Produce MOVE/SOURCE_COPY operations for the moved blocks.
+ num_ops = aops->size();
+ if (chunk_blocks == -1)
+ chunk_blocks = new_num_blocks;
+ uint64_t used_blocks = 0;
+ old_visited_blocks->AddExtents(old_identical_blocks);
+ new_visited_blocks->AddExtents(new_identical_blocks);
+ for (Extent extent : new_identical_blocks) {
+ // We split the operation at the extent boundary or when bigger than
+ // chunk_blocks.
+ for (uint64_t op_block_offset = 0; op_block_offset < extent.num_blocks();
+ op_block_offset += chunk_blocks) {
+ aops->emplace_back();
+ AnnotatedOperation* aop = &aops->back();
+ aop->name = "<identical-blocks>";
+ aop->op.set_type(src_ops_allowed ?
+ DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY :
+ DeltaArchiveManifest_InstallOperation_Type_MOVE);
+
+ uint64_t chunk_num_blocks =
+ std::min(extent.num_blocks() - op_block_offset,
+ static_cast<uint64_t>(chunk_blocks));
+
+ // The current operation represents the move/copy operation for the
+ // sublist starting at |used_blocks| of length |chunk_num_blocks| where
+ // the src and dst are from |old_identical_blocks| and
+ // |new_identical_blocks| respectively.
+ StoreExtents(
+ ExtentsSublist(old_identical_blocks, used_blocks, chunk_num_blocks),
+ aop->op.mutable_src_extents());
+
+ Extent* op_dst_extent = aop->op.add_dst_extents();
+ op_dst_extent->set_start_block(extent.start_block() + op_block_offset);
+ op_dst_extent->set_num_blocks(chunk_num_blocks);
+ CHECK(
+ vector<Extent>{*op_dst_extent} == // NOLINT(whitespace/braces)
+ ExtentsSublist(new_identical_blocks, used_blocks, chunk_num_blocks));
+
+ used_blocks += chunk_num_blocks;
+ }
+ }
+ LOG(INFO) << "Produced " << (aops->size() - num_ops) << " operations for "
+ << used_blocks << " identical blocks moved";
+
+ return true;
+}
+
bool DeltaReadFile(
vector<AnnotatedOperation>* aops,
const string& old_part,
diff --git a/payload_generator/delta_diff_utils.h b/payload_generator/delta_diff_utils.h
index 0be8666..d85249d 100644
--- a/payload_generator/delta_diff_utils.h
+++ b/payload_generator/delta_diff_utils.h
@@ -11,6 +11,7 @@
#include <chromeos/secure_blob.h>
#include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/payload_generator/payload_generation_config.h"
#include "update_engine/update_metadata.pb.h"
@@ -33,6 +34,29 @@
bool skip_block_0,
bool src_ops_allowed);
+// Create operations in |aops| for identical blocks that moved around in the old
+// and new partition and also handle zeroed blocks. The old and new partition
+// are stored in the |old_part| and |new_part| files and have |old_num_blocks|
+// and |new_num_blocks| respectively. The maximum operation size is
+// |chunk_blocks| blocks, or unlimited if |chunk_blocks| is -1. The blobs of the
+// produced operations are stored in the |data_fd| file whose size is updated
+// in the value pointed by |data_file_size|.
+// The collections |old_visited_blocks| and |new_visited_blocks| state what
+// blocks already have operations reading or writing them and only operations
+// for unvisited blocks are produced by this function updating both collections
+// with the used blocks.
+bool DeltaMovedAndZeroBlocks(std::vector<AnnotatedOperation>* aops,
+ const std::string& old_part,
+ const std::string& new_part,
+ size_t old_num_blocks,
+ size_t new_num_blocks,
+ off_t chunk_blocks,
+ bool src_ops_allowed,
+ int data_fd,
+ off_t* data_file_size,
+ ExtentRanges* old_visited_blocks,
+ ExtentRanges* new_visited_blocks);
+
// For a given file |name| append operations to |aops| to produce it in the
// |new_part|. The file will be split in chunks of |chunk_blocks| blocks each
// or treated as a single chunk if |chunk_blocks| is -1. The file data is
diff --git a/payload_generator/delta_diff_utils_unittest.cc b/payload_generator/delta_diff_utils_unittest.cc
index 2157aa1..3b1d44d 100644
--- a/payload_generator/delta_diff_utils_unittest.cc
+++ b/payload_generator/delta_diff_utils_unittest.cc
@@ -9,6 +9,8 @@
#include <vector>
#include <base/files/scoped_file.h>
+#include <base/format_macros.h>
+#include <base/strings/stringprintf.h>
#include <gtest/gtest.h>
#include "update_engine/payload_generator/delta_diff_generator.h"
@@ -19,7 +21,6 @@
#include "update_engine/utils.h"
using std::string;
-using std::unique_ptr;
using std::vector;
namespace chromeos_update_engine {
@@ -51,61 +52,117 @@
return true;
}
+// Create a fake filesystem of the given |size| and initialize the partition
+// holding it in the PartitionConfig |part|.
+void CreatePartition(PartitionConfig* part, const string& pattern,
+ uint64_t block_size, off_t size) {
+ int fd = -1;
+ ASSERT_TRUE(utils::MakeTempFile(pattern.c_str(), &part->path, &fd));
+ ASSERT_EQ(0, ftruncate(fd, size));
+ ASSERT_EQ(0, close(fd));
+ part->fs_interface.reset(new FakeFilesystem(block_size, size / block_size));
+ part->size = size;
+}
+
+// Writes to the |partition| path blocks such they are all different and they
+// include the tag passed in |tag|, making them also different to any other
+// block on a partition initialized with this function with a different tag.
+// The |block_size| should be a divisor of the partition size.
+// Returns whether the function succeeded writing the partition.
+bool InitializePartitionWithUniqueBlocks(const PartitionConfig& part,
+ uint64_t block_size,
+ uint64_t tag) {
+ TEST_AND_RETURN_FALSE(part.size % block_size == 0);
+ size_t num_blocks = part.size / block_size;
+ chromeos::Blob file_data(part.size);
+ for (size_t i = 0; i < num_blocks; ++i) {
+ string prefix = base::StringPrintf(
+ "block tag 0x%.16" PRIx64 ", block number %16" PRIuS " ", tag, i);
+ chromeos::Blob block_data(prefix.begin(), prefix.end());
+ TEST_AND_RETURN_FALSE(prefix.size() <= block_size);
+ block_data.resize(block_size, 'X');
+ std::copy(block_data.begin(), block_data.end(),
+ file_data.begin() + i * block_size);
+ }
+ return test_utils::WriteFileVector(part.path, file_data);
+}
+
} // namespace
class DeltaDiffUtilsTest : public ::testing::Test {
protected:
- const uint64_t kFilesystemSize = kBlockSize * 1024;
+ const uint64_t kDefaultBlockCount = 128;
void SetUp() override {
- old_part_path_ = "DeltaDiffUtilsTest-old_part_path-XXXXXX";
- CreateFilesystem(&old_fs_, &old_part_path_, kFilesystemSize);
-
- new_part_path_ = "DeltaDiffUtilsTest-new_part_path-XXXXXX";
- CreateFilesystem(&old_fs_, &new_part_path_, kFilesystemSize);
+ CreatePartition(&old_part_, "DeltaDiffUtilsTest-old_part-XXXXXX",
+ block_size_, block_size_ * kDefaultBlockCount);
+ CreatePartition(&new_part_, "DeltaDiffUtilsTest-old_part-XXXXXX",
+ block_size_, block_size_ * kDefaultBlockCount);
+ ASSERT_TRUE(utils::MakeTempFile("DeltaDiffUtilsTest-blob-XXXXXX",
+ &blob_path_,
+ &blob_fd_));
}
void TearDown() override {
- unlink(old_part_path_.c_str());
- unlink(new_part_path_.c_str());
+ unlink(old_part_.path.c_str());
+ unlink(new_part_.path.c_str());
+ if (blob_fd_ != -1)
+ close(blob_fd_);
+ unlink(blob_path_.c_str());
}
- // Create a fake filesystem of the given size and initialize the partition
- // holding it.
- void CreateFilesystem(unique_ptr<FakeFilesystem>* fs, string* filename,
- uint64_t size) {
- string pattern = *filename;
- ASSERT_TRUE(utils::MakeTempFile(pattern.c_str(), filename, nullptr));
- ASSERT_EQ(0, truncate(filename->c_str(), size));
- fs->reset(new FakeFilesystem(kBlockSize, size / kBlockSize));
+ // Helper function to call DeltaMovedAndZeroBlocks() using this class' data
+ // members. This simply avoid repeating all the arguments that never change.
+ bool RunDeltaMovedAndZeroBlocks(off_t chunk_blocks,
+ bool src_ops_allowed) {
+ return diff_utils::DeltaMovedAndZeroBlocks(
+ &aops_,
+ old_part_.path,
+ new_part_.path,
+ old_part_.size / block_size_,
+ new_part_.size / block_size_,
+ chunk_blocks,
+ src_ops_allowed,
+ blob_fd_,
+ &blob_size_,
+ &old_visited_blocks_,
+ &new_visited_blocks_);
}
- // Paths to old and new temporary filesystems used in the tests.
- string old_part_path_;
- string new_part_path_;
+ // Old and new temporary partitions used in the tests. These are initialized
+ // with
+ PartitionConfig old_part_{PartitionName::kRootfs};
+ PartitionConfig new_part_{PartitionName::kRootfs};
- // FilesystemInterface fake implementations used to mock out the file/block
- // distribution.
- unique_ptr<FakeFilesystem> old_fs_;
- unique_ptr<FakeFilesystem> new_fs_;
+ // The file holding the output blob from the various diff utils functions.
+ string blob_path_;
+ int blob_fd_{-1};
+ off_t blob_size_{0};
+
+ size_t block_size_{kBlockSize};
+
+ // Default input/output arguments used when calling DeltaMovedAndZeroBlocks().
+ vector<AnnotatedOperation> aops_;
+ ExtentRanges old_visited_blocks_;
+ ExtentRanges new_visited_blocks_;
};
TEST_F(DeltaDiffUtilsTest, MoveSmallTest) {
- chromeos::Blob data_blob(kBlockSize);
+ chromeos::Blob data_blob(block_size_);
test_utils::FillWithData(&data_blob);
// The old file is on a different block than the new one.
vector<Extent> old_extents = { ExtentForRange(11, 1) };
vector<Extent> new_extents = { ExtentForRange(1, 1) };
- EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
- EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
chromeos::Blob data;
DeltaArchiveManifest_InstallOperation op;
EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
+ old_part_.path,
+ new_part_.path,
old_extents,
new_extents,
true, // bsdiff_allowed
@@ -158,14 +215,14 @@
file_data.resize(file_data.size() + kBlockSize, 'a' + i);
}
- EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, file_data));
- EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, file_data));
+ EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, file_data));
+ EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, file_data));
chromeos::Blob data;
DeltaArchiveManifest_InstallOperation op;
EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
+ old_part_.path,
+ new_part_.path,
old_extents,
new_extents,
true, // bsdiff_allowed
@@ -220,16 +277,16 @@
vector<Extent> old_extents = { ExtentForRange(1, 1) };
vector<Extent> new_extents = { ExtentForRange(2, 1) };
- EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
// Modify one byte in the new file.
data_blob[0]++;
- EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
chromeos::Blob data;
DeltaArchiveManifest_InstallOperation op;
EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
+ old_part_.path,
+ new_part_.path,
old_extents,
new_extents,
true, // bsdiff_allowed
@@ -262,16 +319,16 @@
vector<Extent> old_extents = { ExtentForRange(1, 1) };
vector<Extent> new_extents = { ExtentForRange(2, 1) };
- EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
// Modify one byte in the new file.
data_blob[0]++;
- EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
chromeos::Blob data;
DeltaArchiveManifest_InstallOperation op;
EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
+ old_part_.path,
+ new_part_.path,
old_extents,
new_extents,
false, // bsdiff_allowed
@@ -295,14 +352,14 @@
vector<Extent> old_extents = { ExtentForRange(1, 1) };
vector<Extent> new_extents = { ExtentForRange(2, 1) };
- EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
- EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
chromeos::Blob data;
DeltaArchiveManifest_InstallOperation op;
EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
+ old_part_.path,
+ new_part_.path,
old_extents,
new_extents,
false, // bsdiff_allowed
@@ -337,14 +394,14 @@
for (int i = 0; i < 2; i++) {
chromeos::Blob data_to_test = i == 0 ? random_data : ones;
// The old_extents will be initialized with 0.
- EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize,
+ EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize,
data_to_test));
chromeos::Blob data;
DeltaArchiveManifest_InstallOperation op;
EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
+ old_part_.path,
+ new_part_.path,
old_extents,
new_extents,
true, // bsdiff_allowed
@@ -379,14 +436,14 @@
vector<Extent> old_extents = { ExtentForRange(11, 1) };
vector<Extent> new_extents = { ExtentForRange(1, 1) };
- EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
- EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
chromeos::Blob data;
DeltaArchiveManifest_InstallOperation op;
EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
+ old_part_.path,
+ new_part_.path,
old_extents,
new_extents,
true, // bsdiff_allowed
@@ -410,16 +467,16 @@
vector<Extent> old_extents = { ExtentForRange(1, 1) };
vector<Extent> new_extents = { ExtentForRange(2, 1) };
- EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
// Modify one byte in the new file.
data_blob[0]++;
- EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+ EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
chromeos::Blob data;
DeltaArchiveManifest_InstallOperation op;
EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
+ old_part_.path,
+ new_part_.path,
old_extents,
new_extents,
true, // bsdiff_allowed
@@ -476,4 +533,237 @@
EXPECT_EQ("aop2", ops[1].name);
}
+// Test the simple case where all the blocks are different and no new blocks are
+// zeroed.
+TEST_F(DeltaDiffUtilsTest, NoZeroedOrUniqueBlocksDetected) {
+ InitializePartitionWithUniqueBlocks(old_part_, block_size_, 5);
+ InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
+
+ EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks
+ false)); // src_ops_allowed
+
+ EXPECT_EQ(0, old_visited_blocks_.blocks());
+ EXPECT_EQ(0, new_visited_blocks_.blocks());
+ EXPECT_EQ(0, blob_size_);
+ EXPECT_TRUE(aops_.empty());
+}
+
+// Test that when the partitions have identical blocks in the same positions no
+// MOVE operation is performed and all the blocks are handled.
+TEST_F(DeltaDiffUtilsTest, IdenticalPartitionsDontMove) {
+ InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
+ InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
+
+ // Mark some of the blocks as already visited.
+ vector<Extent> already_visited = {ExtentForRange(5, 10),
+ ExtentForRange(25, 10)};
+ old_visited_blocks_.AddExtents(already_visited);
+ new_visited_blocks_.AddExtents(already_visited);
+
+ // Most of the blocks rest in the same place, but there's no need for MOVE
+ // operations on those blocks.
+ EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks
+ false)); // src_ops_allowed
+
+ EXPECT_EQ(kDefaultBlockCount, old_visited_blocks_.blocks());
+ EXPECT_EQ(kDefaultBlockCount, new_visited_blocks_.blocks());
+ EXPECT_EQ(0, blob_size_);
+ EXPECT_TRUE(aops_.empty());
+}
+
+// Test that when the partitions have identical blocks in the same positions
+// MOVE operation is performed and all the blocks are handled.
+TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedFromSource) {
+ // We use a smaller partition for this test.
+ old_part_.size = kBlockSize * 50;
+ new_part_.size = kBlockSize * 50;
+
+ InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
+ InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
+
+ // Mark some of the blocks as already visited.
+ vector<Extent> already_visited = {ExtentForRange(5, 5),
+ ExtentForRange(25, 7)};
+ old_visited_blocks_.AddExtents(already_visited);
+ new_visited_blocks_.AddExtents(already_visited);
+
+ // Override some of the old blocks with different data.
+ vector<Extent> different_blocks = {ExtentForRange(40, 5)};
+ EXPECT_TRUE(WriteExtents(old_part_.path, different_blocks, kBlockSize,
+ chromeos::Blob(5 * kBlockSize, 'a')));
+
+ EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(10, // chunk_blocks
+ true)); // src_ops_allowed
+
+ ExtentRanges expected_ranges;
+ expected_ranges.AddExtent(ExtentForRange(0, 50));
+ expected_ranges.SubtractExtents(different_blocks);
+
+ EXPECT_EQ(expected_ranges.extent_set(), old_visited_blocks_.extent_set());
+ EXPECT_EQ(expected_ranges.extent_set(), new_visited_blocks_.extent_set());
+ EXPECT_EQ(0, blob_size_);
+
+ // We expect all the blocks that we didn't override with |different_blocks|
+ // and that we didn't mark as visited in |already_visited| to match and have a
+ // SOURCE_COPY operation chunked at 10 blocks.
+ vector<Extent> expected_op_extents = {
+ ExtentForRange(0, 5),
+ ExtentForRange(10, 10),
+ ExtentForRange(20, 5),
+ ExtentForRange(32, 8),
+ ExtentForRange(45, 5),
+ };
+
+ EXPECT_EQ(expected_op_extents.size(), aops_.size());
+ for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) {
+ SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i));
+ const AnnotatedOperation& aop = aops_[i];
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+ aop.op.type());
+ EXPECT_EQ(1, aop.op.src_extents_size());
+ EXPECT_EQ(expected_op_extents[i], aop.op.src_extents(0));
+ EXPECT_EQ(1, aop.op.dst_extents_size());
+ EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0));
+ }
+}
+
+TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedInOder) {
+ // We use a smaller partition for this test.
+ old_part_.size = block_size_ * 50;
+ new_part_.size = block_size_ * 50;
+
+ // Create two identical partitions with 5 copies of the same unique "file".
+ chromeos::Blob file_data(block_size_ * 10, 'a');
+ for (size_t offset = 0; offset < file_data.size(); offset += block_size_)
+ file_data[offset] = 'a' + offset / block_size_;
+
+ chromeos::Blob partition_data(old_part_.size);
+ for (size_t offset = 0; offset < partition_data.size();
+ offset += file_data.size()) {
+ std::copy(file_data.begin(), file_data.end(),
+ partition_data.begin() + offset);
+ }
+ EXPECT_TRUE(test_utils::WriteFileVector(old_part_.path, partition_data));
+ EXPECT_TRUE(test_utils::WriteFileVector(new_part_.path, partition_data));
+
+ EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks
+ true)); // src_ops_allowed
+
+ // There should be only one SOURCE_COPY, for the whole partition and the
+ // source extents should cover only the first copy of the source file since
+ // we prefer to re-read files (maybe cached) instead of continue reading the
+ // rest of the partition.
+ EXPECT_EQ(1, aops_.size());
+ const AnnotatedOperation& aop = aops_[0];
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+ aop.op.type());
+ EXPECT_EQ(5, aop.op.src_extents_size());
+ for (int i = 0; i < aop.op.src_extents_size(); ++i) {
+ EXPECT_EQ(ExtentForRange(0, 10), aop.op.src_extents(i));
+ }
+
+ EXPECT_EQ(1, aop.op.dst_extents_size());
+ EXPECT_EQ(ExtentForRange(0, 50), aop.op.dst_extents(0));
+
+ EXPECT_EQ(0, blob_size_);
+}
+
+// Test that all blocks with zeros are handled separately using REPLACE_BZ
+// operations unless they are not moved.
+TEST_F(DeltaDiffUtilsTest, ZeroBlocksUseReplaceBz) {
+ InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
+ InitializePartitionWithUniqueBlocks(new_part_, block_size_, 5);
+
+ // We set four ranges of blocks with zeros: a single block, a range that fits
+ // in the chunk size, a range that doesn't and finally a range of zeros that
+ // was also zeros in the old image.
+ vector<Extent> new_zeros = {
+ ExtentForRange(10, 1),
+ ExtentForRange(20, 4),
+ // The last range is split since the old image has zeros in part of it.
+ ExtentForRange(30, 20),
+ };
+ chromeos::Blob zeros_data(BlocksInExtents(new_zeros) * block_size_, '\0');
+ EXPECT_TRUE(WriteExtents(new_part_.path, new_zeros, block_size_, zeros_data));
+
+ vector<Extent> old_zeros = vector<Extent>{ExtentForRange(43, 7)};
+ EXPECT_TRUE(WriteExtents(old_part_.path, old_zeros, block_size_, zeros_data));
+
+ EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(5, // chunk_blocks
+ false)); // src_ops_allowed
+
+ // Zeroed blocks from old_visited_blocks_ were copied over, so me actually
+ // use them regardless of the trivial MOVE operation not being emitted.
+ EXPECT_EQ(old_zeros,
+ old_visited_blocks_.GetExtentsForBlockCount(
+ old_visited_blocks_.blocks()));
+
+ // All the new zeroed blocks should be used, part with REPLACE_BZ and part
+ // trivial MOVE operations (not included).
+ EXPECT_EQ(new_zeros,
+ new_visited_blocks_.GetExtentsForBlockCount(
+ new_visited_blocks_.blocks()));
+
+ vector<Extent> expected_op_extents = {
+ ExtentForRange(10, 1),
+ ExtentForRange(20, 4),
+ // This range should be split.
+ ExtentForRange(30, 5),
+ ExtentForRange(35, 5),
+ ExtentForRange(40, 3),
+ };
+
+ EXPECT_EQ(expected_op_extents.size(), aops_.size());
+ for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) {
+ SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i));
+ const AnnotatedOperation& aop = aops_[i];
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
+ aop.op.type());
+ EXPECT_EQ(0, aop.op.src_extents_size());
+ EXPECT_EQ(1, aop.op.dst_extents_size());
+ EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0));
+ }
+ EXPECT_NE(0, blob_size_);
+}
+
+TEST_F(DeltaDiffUtilsTest, ShuffledBlocksAreTracked) {
+ vector<uint64_t> permutation = {0, 1, 5, 6, 7, 2, 3, 4, 9, 10, 11, 12, 8};
+ vector<Extent> perm_extents;
+ for (uint64_t x : permutation)
+ AppendBlockToExtents(&perm_extents, x);
+
+ // We use a smaller partition for this test.
+ old_part_.size = block_size_ * permutation.size();
+ new_part_.size = block_size_ * permutation.size();
+ InitializePartitionWithUniqueBlocks(new_part_, block_size_, 123);
+
+ // We initialize the old_part_ with the blocks from new_part but in the
+ // |permutation| order. Block i in the old_part_ will contain the same data
+ // as block permutation[i] in the new_part_.
+ chromeos::Blob new_contents;
+ EXPECT_TRUE(utils::ReadFile(new_part_.path, &new_contents));
+ EXPECT_TRUE(WriteExtents(old_part_.path, perm_extents, block_size_,
+ new_contents));
+
+ EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks
+ true)); // src_ops_allowed
+
+ EXPECT_EQ(permutation.size(), old_visited_blocks_.blocks());
+ EXPECT_EQ(permutation.size(), new_visited_blocks_.blocks());
+
+ // There should be only one SOURCE_COPY, with a complicate list of extents.
+ EXPECT_EQ(1, aops_.size());
+ const AnnotatedOperation& aop = aops_[0];
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+ aop.op.type());
+ vector<Extent> aop_src_extents;
+ ExtentsToVector(aop.op.src_extents(), &aop_src_extents);
+ EXPECT_EQ(perm_extents, aop_src_extents);
+
+ EXPECT_EQ(1, aop.op.dst_extents_size());
+ EXPECT_EQ(ExtentForRange(0, permutation.size()), aop.op.dst_extents(0));
+
+ EXPECT_EQ(0, blob_size_);
+}
+
} // namespace chromeos_update_engine
diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
index d86bcfc..9151efe 100644
--- a/payload_generator/extent_ranges.cc
+++ b/payload_generator/extent_ranges.cc
@@ -180,6 +180,23 @@
}
}
+bool ExtentRanges::ContainsBlock(uint64_t block) const {
+ auto lower = extent_set_.lower_bound(ExtentForRange(block, 1));
+ // The block could be on the extent before the one in |lower|.
+ if (lower != extent_set_.begin())
+ lower--;
+ // Any extent starting at block+1 or later is not interesting, so this is the
+ // upper limit.
+ auto upper = extent_set_.lower_bound(ExtentForRange(block + 1, 0));
+ for (auto iter = lower; iter != upper; ++iter) {
+ if (iter->start_block() <= block &&
+ block < iter->start_block() + iter->num_blocks()) {
+ return true;
+ }
+ }
+ return false;
+}
+
void ExtentRanges::Dump() const {
LOG(INFO) << "ExtentRanges Dump. blocks: " << blocks_;
for (ExtentSet::const_iterator it = extent_set_.begin(),
@@ -223,7 +240,7 @@
return out;
}
-vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents,
+vector<Extent> FilterExtentRanges(const vector<Extent>& extents,
const ExtentRanges& ranges) {
vector<Extent> result;
const ExtentRanges::ExtentSet& extent_set = ranges.extent_set();
diff --git a/payload_generator/extent_ranges.h b/payload_generator/extent_ranges.h
index fc15149..f14bb61 100644
--- a/payload_generator/extent_ranges.h
+++ b/payload_generator/extent_ranges.h
@@ -48,6 +48,9 @@
void AddRanges(const ExtentRanges& ranges);
void SubtractRanges(const ExtentRanges& ranges);
+ // Returns whether the block |block| is in this ExtentRange.
+ bool ContainsBlock(uint64_t block) const;
+
static bool ExtentsOverlapOrTouch(const Extent& a, const Extent& b);
static bool ExtentsOverlap(const Extent& a, const Extent& b);
diff --git a/payload_generator/extent_ranges_unittest.cc b/payload_generator/extent_ranges_unittest.cc
index b7036a5..2cda195 100644
--- a/payload_generator/extent_ranges_unittest.cc
+++ b/payload_generator/extent_ranges_unittest.cc
@@ -256,6 +256,25 @@
}
}
+TEST(ExtentRangesTest, ContainsBlockTest) {
+ ExtentRanges ranges;
+ EXPECT_FALSE(ranges.ContainsBlock(123));
+
+ ranges.AddExtent(ExtentForRange(10, 10));
+ ranges.AddExtent(ExtentForRange(100, 1));
+
+ EXPECT_FALSE(ranges.ContainsBlock(9));
+ EXPECT_TRUE(ranges.ContainsBlock(10));
+ EXPECT_TRUE(ranges.ContainsBlock(15));
+ EXPECT_TRUE(ranges.ContainsBlock(19));
+ EXPECT_FALSE(ranges.ContainsBlock(20));
+
+ // Test for an extent with just the block we are requesting.
+ EXPECT_FALSE(ranges.ContainsBlock(99));
+ EXPECT_TRUE(ranges.ContainsBlock(100));
+ EXPECT_FALSE(ranges.ContainsBlock(101));
+}
+
TEST(ExtentRangesTest, FilterExtentRangesEmptyRanges) {
ExtentRanges ranges;
EXPECT_EQ(vector<Extent>(),