update_engine: Split delta_diff_generator file.
The DeltaDiffGenerator class includes both an OperationsGenerator using the
A-to-B operations and a set of common methods used also by the inplace generator.
The delta_diff_generator.{h,cc} files also include a single function to generate
the payload (GenerateUpdatePayloadFile) that centralizes the logic of generating
the operations and writing the payload.
This patch splits these three parts in different files. The common delta diff
function are moved to the delta_diff_utils.{h,cc} files. The operations generator
class that uses A-to-B operations is now in a new ab_generator.{h,cc} pair of files
that implement the ABGenerator() class. Finally, the payload file writing methods
are now in a single PayloadFile class.
This allow us to create payload files without the need to generate images and
their deltas. This will be used in a follow up CL to remove the image generation
logic from the unittests.
BUG=chromium:351589
TEST=Ran unittests. Regenerate a payload with and without this patch; got the same results.
Change-Id: I6816d2c805ba8c0c5c9423c720131a100a15ebaa
Reviewed-on: https://chromium-review.googlesource.com/280838
Reviewed-by: Alex Deymo <deymo@chromium.org>
Commit-Queue: Alex Deymo <deymo@chromium.org>
Trybot-Ready: Alex Deymo <deymo@chromium.org>
Tested-by: Alex Deymo <deymo@chromium.org>
diff --git a/payload_generator/ab_generator.cc b/payload_generator/ab_generator.cc
new file mode 100644
index 0000000..7a9c748
--- /dev/null
+++ b/payload_generator/ab_generator.cc
@@ -0,0 +1,373 @@
+// 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/ab_generator.h"
+
+#include <algorithm>
+
+#include <base/strings/stringprintf.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/delta_performer.h"
+#include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
+#include "update_engine/payload_generator/ext2_filesystem.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::unique_ptr;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+// Compare two AnnotatedOperations by the start block of the first Extent in
+// their destination extents.
+bool CompareAopsByDestination(AnnotatedOperation first_aop,
+ AnnotatedOperation second_aop) {
+ // We want empty operations to be at the end of the payload.
+ if (!first_aop.op.dst_extents().size() || !second_aop.op.dst_extents().size())
+ return ((!first_aop.op.dst_extents().size()) <
+ (!second_aop.op.dst_extents().size()));
+ uint32_t first_dst_start = first_aop.op.dst_extents(0).start_block();
+ uint32_t second_dst_start = second_aop.op.dst_extents(0).start_block();
+ return first_dst_start < second_dst_start;
+}
+
+} // namespace
+
+bool ABGenerator::GenerateOperations(
+ const PayloadGenerationConfig& config,
+ int data_file_fd,
+ off_t* data_file_size,
+ vector<AnnotatedOperation>* rootfs_ops,
+ vector<AnnotatedOperation>* kernel_ops) {
+ unique_ptr<Ext2Filesystem> old_fs = Ext2Filesystem::CreateFromFile(
+ config.source.rootfs.path);
+ unique_ptr<Ext2Filesystem> new_fs = Ext2Filesystem::CreateFromFile(
+ config.target.rootfs.path);
+
+ off_t chunk_blocks = (config.chunk_size == -1 ? -1 :
+ config.chunk_size / config.block_size);
+
+ rootfs_ops->clear();
+ TEST_AND_RETURN_FALSE(diff_utils::DeltaReadFilesystem(
+ rootfs_ops,
+ config.source.rootfs.path,
+ config.target.rootfs.path,
+ old_fs.get(),
+ new_fs.get(),
+ chunk_blocks,
+ data_file_fd,
+ data_file_size,
+ false, // skip_block_0
+ true)); // src_ops_allowed
+ LOG(INFO) << "done reading normal files";
+
+ // Read kernel partition
+ TEST_AND_RETURN_FALSE(diff_utils::DeltaCompressKernelPartition(
+ config.source.kernel.path,
+ config.target.kernel.path,
+ config.source.kernel.size,
+ config.target.kernel.size,
+ config.block_size,
+ kernel_ops,
+ data_file_fd,
+ data_file_size,
+ true)); // src_ops_allowed
+ LOG(INFO) << "done reading kernel";
+
+ TEST_AND_RETURN_FALSE(FragmentOperations(rootfs_ops,
+ config.target.rootfs.path,
+ data_file_fd,
+ data_file_size));
+ TEST_AND_RETURN_FALSE(FragmentOperations(kernel_ops,
+ config.target.kernel.path,
+ data_file_fd,
+ data_file_size));
+ SortOperationsByDestination(rootfs_ops);
+ SortOperationsByDestination(kernel_ops);
+ // TODO(alliewood): Change merge operations to use config.chunk_size once
+ // specifying chunk_size on the command line works. crbug/485397.
+ TEST_AND_RETURN_FALSE(MergeOperations(rootfs_ops,
+ kDefaultChunkSize,
+ config.target.rootfs.path,
+ data_file_fd,
+ data_file_size));
+ TEST_AND_RETURN_FALSE(MergeOperations(kernel_ops,
+ kDefaultChunkSize,
+ config.target.kernel.path,
+ data_file_fd,
+ data_file_size));
+ return true;
+}
+
+void ABGenerator::SortOperationsByDestination(
+ vector<AnnotatedOperation>* aops) {
+ sort(aops->begin(), aops->end(), CompareAopsByDestination);
+}
+
+bool ABGenerator::FragmentOperations(
+ vector<AnnotatedOperation>* aops,
+ const string& target_part_path,
+ int data_fd,
+ off_t* data_file_size) {
+ vector<AnnotatedOperation> fragmented_aops;
+ for (const AnnotatedOperation& aop : *aops) {
+ if (aop.op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) {
+ TEST_AND_RETURN_FALSE(SplitSourceCopy(aop, &fragmented_aops));
+ } else if ((aop.op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE) ||
+ (aop.op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) {
+ TEST_AND_RETURN_FALSE(SplitReplaceOrReplaceBz(aop, &fragmented_aops,
+ target_part_path, data_fd,
+ data_file_size));
+ } else {
+ fragmented_aops.push_back(aop);
+ }
+ }
+ *aops = fragmented_aops;
+ return true;
+}
+
+bool ABGenerator::SplitSourceCopy(
+ const AnnotatedOperation& original_aop,
+ vector<AnnotatedOperation>* result_aops) {
+ DeltaArchiveManifest_InstallOperation original_op = original_aop.op;
+ TEST_AND_RETURN_FALSE(original_op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+ // Keeps track of the index of curr_src_ext.
+ int curr_src_ext_index = 0;
+ Extent curr_src_ext = original_op.src_extents(curr_src_ext_index);
+ for (int i = 0; i < original_op.dst_extents_size(); i++) {
+ Extent dst_ext = original_op.dst_extents(i);
+ // The new operation which will have only one dst extent.
+ DeltaArchiveManifest_InstallOperation new_op;
+ uint64_t blocks_left = dst_ext.num_blocks();
+ while (blocks_left > 0) {
+ if (curr_src_ext.num_blocks() <= blocks_left) {
+ // If the curr_src_ext is smaller than dst_ext, add it.
+ blocks_left -= curr_src_ext.num_blocks();
+ *(new_op.add_src_extents()) = curr_src_ext;
+ if (curr_src_ext_index + 1 < original_op.src_extents().size()) {
+ curr_src_ext = original_op.src_extents(++curr_src_ext_index);
+ } else {
+ break;
+ }
+ } else {
+ // Split src_exts that are bigger than the dst_ext we're dealing with.
+ Extent first_ext;
+ first_ext.set_num_blocks(blocks_left);
+ first_ext.set_start_block(curr_src_ext.start_block());
+ *(new_op.add_src_extents()) = first_ext;
+ // Keep the second half of the split op.
+ curr_src_ext.set_num_blocks(curr_src_ext.num_blocks() - blocks_left);
+ curr_src_ext.set_start_block(curr_src_ext.start_block() + blocks_left);
+ blocks_left -= first_ext.num_blocks();
+ }
+ }
+ // Fix up our new operation and add it to the results.
+ new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+ *(new_op.add_dst_extents()) = dst_ext;
+ new_op.set_src_length(dst_ext.num_blocks() * kBlockSize);
+ new_op.set_dst_length(dst_ext.num_blocks() * kBlockSize);
+
+ AnnotatedOperation new_aop;
+ new_aop.op = new_op;
+ new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i);
+ result_aops->push_back(new_aop);
+ }
+ if (curr_src_ext_index != original_op.src_extents().size() - 1) {
+ LOG(FATAL) << "Incorrectly split SOURCE_COPY operation. Did not use all "
+ << "source extents.";
+ }
+ return true;
+}
+
+bool ABGenerator::SplitReplaceOrReplaceBz(
+ const AnnotatedOperation& original_aop,
+ vector<AnnotatedOperation>* result_aops,
+ const string& target_part_path,
+ int data_fd,
+ off_t* data_file_size) {
+ DeltaArchiveManifest_InstallOperation original_op = original_aop.op;
+ const bool is_replace =
+ original_op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE;
+ TEST_AND_RETURN_FALSE(
+ is_replace ||
+ (original_op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ));
+
+ uint32_t data_offset = original_op.data_offset();
+ for (int i = 0; i < original_op.dst_extents_size(); i++) {
+ Extent dst_ext = original_op.dst_extents(i);
+ // Make a new operation with only one dst extent.
+ DeltaArchiveManifest_InstallOperation new_op;
+ *(new_op.add_dst_extents()) = dst_ext;
+ uint32_t data_size = dst_ext.num_blocks() * kBlockSize;
+ new_op.set_dst_length(data_size);
+ // If this is a REPLACE, attempt to reuse portions of the existing blob.
+ if (is_replace) {
+ new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ new_op.set_data_length(data_size);
+ new_op.set_data_offset(data_offset);
+ data_offset += data_size;
+ }
+
+ AnnotatedOperation new_aop;
+ new_aop.op = new_op;
+ new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i);
+ TEST_AND_RETURN_FALSE(AddDataAndSetType(&new_aop, target_part_path, data_fd,
+ data_file_size));
+
+ result_aops->push_back(new_aop);
+ }
+ return true;
+}
+
+bool ABGenerator::MergeOperations(vector<AnnotatedOperation>* aops,
+ off_t chunk_size,
+ const string& target_part_path,
+ int data_fd,
+ off_t* data_file_size) {
+ vector<AnnotatedOperation> new_aops;
+ for (const AnnotatedOperation& curr_aop : *aops) {
+ if (new_aops.empty()) {
+ new_aops.push_back(curr_aop);
+ continue;
+ }
+ AnnotatedOperation& last_aop = new_aops.back();
+
+ if (last_aop.op.dst_extents_size() <= 0 ||
+ curr_aop.op.dst_extents_size() <= 0) {
+ new_aops.push_back(curr_aop);
+ continue;
+ }
+ uint32_t last_dst_idx = last_aop.op.dst_extents_size() - 1;
+ uint32_t last_end_block =
+ last_aop.op.dst_extents(last_dst_idx).start_block() +
+ last_aop.op.dst_extents(last_dst_idx).num_blocks();
+ uint32_t curr_start_block = curr_aop.op.dst_extents(0).start_block();
+ uint32_t combined_block_count =
+ last_aop.op.dst_extents(last_dst_idx).num_blocks() +
+ curr_aop.op.dst_extents(0).num_blocks();
+ bool good_op_type =
+ curr_aop.op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY ||
+ curr_aop.op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+ curr_aop.op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ;
+ if (good_op_type &&
+ last_aop.op.type() == curr_aop.op.type() &&
+ last_end_block == curr_start_block &&
+ static_cast<off_t>(combined_block_count * kBlockSize) <= chunk_size) {
+ // If the operations have the same type (which is a type that we can
+ // merge), are contiguous, are fragmented to have one destination extent,
+ // and their combined block count would be less than chunk size, merge
+ // them.
+ last_aop.name = base::StringPrintf("%s,%s",
+ last_aop.name.c_str(),
+ curr_aop.name.c_str());
+
+ ExtendExtents(last_aop.op.mutable_src_extents(),
+ curr_aop.op.src_extents());
+ if (curr_aop.op.src_length() > 0)
+ last_aop.op.set_src_length(last_aop.op.src_length() +
+ curr_aop.op.src_length());
+ ExtendExtents(last_aop.op.mutable_dst_extents(),
+ curr_aop.op.dst_extents());
+ if (curr_aop.op.dst_length() > 0)
+ last_aop.op.set_dst_length(last_aop.op.dst_length() +
+ curr_aop.op.dst_length());
+ // Set the data length to zero so we know to add the blob later.
+ if (curr_aop.op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+ curr_aop.op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+ last_aop.op.set_data_length(0);
+ }
+ } else {
+ // Otherwise just include the extent as is.
+ new_aops.push_back(curr_aop);
+ }
+ }
+
+ // Set the blobs for REPLACE/REPLACE_BZ operations that have been merged.
+ for (AnnotatedOperation& curr_aop : new_aops) {
+ if (curr_aop.op.data_length() == 0 &&
+ (curr_aop.op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+ curr_aop.op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) {
+ TEST_AND_RETURN_FALSE(AddDataAndSetType(&curr_aop, target_part_path,
+ data_fd, data_file_size));
+ }
+ }
+
+ *aops = new_aops;
+ return true;
+}
+
+bool ABGenerator::AddDataAndSetType(AnnotatedOperation* aop,
+ const string& target_part_path,
+ int data_fd,
+ off_t* data_file_size) {
+ TEST_AND_RETURN_FALSE(
+ aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+ aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+
+ chromeos::Blob data(aop->op.dst_length());
+ vector<Extent> dst_extents;
+ ExtentsToVector(aop->op.dst_extents(), &dst_extents);
+ TEST_AND_RETURN_FALSE(utils::ReadExtents(target_part_path,
+ dst_extents,
+ &data,
+ data.size(),
+ kBlockSize));
+
+ chromeos::Blob data_bz;
+ TEST_AND_RETURN_FALSE(BzipCompress(data, &data_bz));
+ CHECK(!data_bz.empty());
+
+ chromeos::Blob* data_p = nullptr;
+ DeltaArchiveManifest_InstallOperation_Type new_op_type;
+ if (data_bz.size() < data.size()) {
+ new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ;
+ data_p = &data_bz;
+ } else {
+ new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE;
+ data_p = &data;
+ }
+
+ // If the operation already points to a data blob, check whether it's
+ // identical to the new one, in which case don't add it.
+ if (aop->op.type() == new_op_type &&
+ aop->op.data_length() == data_p->size()) {
+ chromeos::Blob current_data(data_p->size());
+ ssize_t bytes_read;
+ TEST_AND_RETURN_FALSE(utils::PReadAll(data_fd,
+ current_data.data(),
+ aop->op.data_length(),
+ aop->op.data_offset(),
+ &bytes_read));
+ TEST_AND_RETURN_FALSE(bytes_read ==
+ static_cast<ssize_t>(aop->op.data_length()));
+ if (current_data == *data_p)
+ data_p = nullptr;
+ }
+
+ if (data_p) {
+ aop->op.set_type(new_op_type);
+ aop->SetOperationBlob(data_p, data_fd, data_file_size);
+ }
+
+ return true;
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/ab_generator.h b/payload_generator/ab_generator.h
new file mode 100644
index 0000000..d027f22
--- /dev/null
+++ b/payload_generator/ab_generator.h
@@ -0,0 +1,120 @@
+// 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_AB_GENERATOR_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_AB_GENERATOR_H_
+
+#include <string>
+#include <vector>
+
+#include <base/macros.h>
+#include <chromeos/secure_blob.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_utils.h"
+#include "update_engine/payload_generator/filesystem_interface.h"
+#include "update_engine/payload_generator/operations_generator.h"
+#include "update_engine/payload_generator/payload_generation_config.h"
+#include "update_engine/update_metadata.pb.h"
+
+namespace chromeos_update_engine {
+
+// The ABGenerator is an operations generator that generates payloads using the
+// A-to-B operations SOURCE_COPY and SOURCE_BSDIFF introduced in the payload
+// minor version 2 format.
+class ABGenerator : public OperationsGenerator {
+ public:
+ ABGenerator() = default;
+
+ // Generate the update payload operations for the kernel and rootfs using
+ // SOURCE_* operations, used for generating deltas for the minor version
+ // kSourceMinorPayloadVersion. This function will generate operations in the
+ // rootfs that will read blocks from the source partition in random order and
+ // write the new image on the target partition, also possibly in random order.
+ // The rootfs operations are stored in |rootfs_ops| and should be executed in
+ // that order. The kernel operations are stored in |kernel_ops|. All
+ // the offsets in the operations reference the data written to |data_file_fd|.
+ // The total amount of data written to that file is stored in
+ // |data_file_size|.
+ bool GenerateOperations(
+ const PayloadGenerationConfig& config,
+ int data_file_fd,
+ off_t* data_file_size,
+ std::vector<AnnotatedOperation>* rootfs_ops,
+ std::vector<AnnotatedOperation>* kernel_ops) override;
+
+ // Split the operations in the vector of AnnotatedOperations |aops|
+ // such that for every operation there is only one dst extent and updates
+ // |aops| with the new list of operations. All kinds of operations are
+ // fragmented except BSDIFF and SOURCE_BSDIFF operations.
+ // The |target_rootfs_part| is the filename of the new image, where the
+ // destination extents refer to. The blobs of the operations in |aops| should
+ // reference the file |data_fd| whose initial size is |*data_file_size|. The
+ // file contents and the value pointed by |data_file_size| are updated if
+ // needed.
+ static bool FragmentOperations(std::vector<AnnotatedOperation>* aops,
+ const std::string& target_rootfs_part,
+ int data_fd,
+ off_t* data_file_size);
+
+ // Takes a vector of AnnotatedOperations |aops| and sorts them by the first
+ // start block in their destination extents. Sets |aops| to a vector of the
+ // sorted operations.
+ static void SortOperationsByDestination(
+ std::vector<AnnotatedOperation>* aops);
+
+ // Takes an SOURCE_COPY install operation, |aop|, and adds one operation for
+ // each dst extent in |aop| to |ops|. The new operations added to |ops| will
+ // have only one dst extent. The src extents are split so the number of blocks
+ // in the src and dst extents are equal.
+ // E.g. we have a SOURCE_COPY operation:
+ // src extents: [(1, 3), (5, 1), (7, 1)], dst extents: [(2, 2), (6, 3)]
+ // Then we will get 2 new operations:
+ // 1. src extents: [(1, 2)], dst extents: [(2, 2)]
+ // 2. src extents: [(3, 1),(5, 1),(7, 1)], dst extents: [(6, 3)]
+ static bool SplitSourceCopy(const AnnotatedOperation& original_aop,
+ std::vector<AnnotatedOperation>* result_aops);
+
+ // Takes a REPLACE/REPLACE_BZ operation |aop|, and adds one operation for each
+ // dst extent in |aop| to |ops|. The new operations added to |ops| will have
+ // only one dst extent each, and may be either a REPLACE or REPLACE_BZ
+ // depending on whether compression is advantageous.
+ static bool SplitReplaceOrReplaceBz(
+ const AnnotatedOperation& original_aop,
+ std::vector<AnnotatedOperation>* result_aops,
+ const std::string& target_part,
+ int data_fd,
+ off_t* data_file_size);
+
+ // Takes a sorted (by first destination extent) vector of operations |aops|
+ // and merges SOURCE_COPY, REPLACE, and REPLACE_BZ operations in that vector.
+ // It will merge two operations if:
+ // - They are of the same type.
+ // - They are contiguous.
+ // - Their combined blocks do not exceed |chunk_size|.
+ static bool MergeOperations(std::vector<AnnotatedOperation>* aops,
+ off_t chunk_size,
+ const std::string& target_part,
+ int data_fd,
+ off_t* data_file_size);
+
+ private:
+ // Adds the data payload for a REPLACE/REPLACE_BZ operation |aop| by reading
+ // its output extents from |target_part_path| and appending a corresponding
+ // data blob to |data_fd|. The blob will be compressed if this is smaller than
+ // the uncompressed form, and the operation type will be set accordingly.
+ // |*data_file_size| will be updated as well. If the operation happens to have
+ // the right type and already points to a data blob, we check whether its
+ // content is identical to the new one, in which case nothing is written.
+ static bool AddDataAndSetType(AnnotatedOperation* aop,
+ const std::string& target_part_path,
+ int data_fd,
+ off_t* data_file_size);
+
+ DISALLOW_COPY_AND_ASSIGN(ABGenerator);
+};
+
+} // namespace chromeos_update_engine
+
+#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_AB_GENERATOR_H_
diff --git a/payload_generator/ab_generator_unittest.cc b/payload_generator/ab_generator_unittest.cc
new file mode 100644
index 0000000..9241701
--- /dev/null
+++ b/payload_generator/ab_generator_unittest.cc
@@ -0,0 +1,558 @@
+// 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/ab_generator.h"
+
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <string>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/payload_generator/annotated_operation.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"
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+bool ExtentEquals(Extent ext, uint64_t start_block, uint64_t num_blocks) {
+ return ext.start_block() == start_block && ext.num_blocks() == num_blocks;
+}
+
+// Tests splitting of a REPLACE/REPLACE_BZ operation.
+void TestSplitReplaceOrReplaceBzOperation(
+ DeltaArchiveManifest_InstallOperation_Type orig_type,
+ bool compressible) {
+ const size_t op_ex1_start_block = 2;
+ const size_t op_ex1_num_blocks = 2;
+ const size_t op_ex2_start_block = 6;
+ const size_t op_ex2_num_blocks = 1;
+ const size_t part_num_blocks = 7;
+
+ // Create the target partition data.
+ string part_path;
+ EXPECT_TRUE(utils::MakeTempFile(
+ "SplitReplaceOrReplaceBzTest_part.XXXXXX", &part_path, nullptr));
+ ScopedPathUnlinker part_path_unlinker(part_path);
+ const size_t part_size = part_num_blocks * kBlockSize;
+ chromeos::Blob part_data;
+ if (compressible) {
+ part_data.resize(part_size);
+ test_utils::FillWithData(&part_data);
+ } else {
+ std::mt19937 gen(12345);
+ std::uniform_int_distribution<uint8_t> dis(0, 255);
+ for (uint32_t i = 0; i < part_size; i++)
+ part_data.push_back(dis(gen));
+ }
+ ASSERT_EQ(part_size, part_data.size());
+ ASSERT_TRUE(utils::WriteFile(part_path.c_str(), part_data.data(), part_size));
+
+ // Create original operation and blob data.
+ const size_t op_ex1_offset = op_ex1_start_block * kBlockSize;
+ const size_t op_ex1_size = op_ex1_num_blocks * kBlockSize;
+ const size_t op_ex2_offset = op_ex2_start_block * kBlockSize;
+ const size_t op_ex2_size = op_ex2_num_blocks * kBlockSize;
+ DeltaArchiveManifest_InstallOperation op;
+ op.set_type(orig_type);
+ *(op.add_dst_extents()) = ExtentForRange(op_ex1_start_block,
+ op_ex1_num_blocks);
+ *(op.add_dst_extents()) = ExtentForRange(op_ex2_start_block,
+ op_ex2_num_blocks);
+ op.set_dst_length(op_ex1_num_blocks + op_ex2_num_blocks);
+
+ chromeos::Blob op_data;
+ op_data.insert(op_data.end(),
+ part_data.begin() + op_ex1_offset,
+ part_data.begin() + op_ex1_offset + op_ex1_size);
+ op_data.insert(op_data.end(),
+ part_data.begin() + op_ex2_offset,
+ part_data.begin() + op_ex2_offset + op_ex2_size);
+ chromeos::Blob op_blob;
+ if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+ op_blob = op_data;
+ } else {
+ ASSERT_TRUE(BzipCompress(op_data, &op_blob));
+ }
+ op.set_data_offset(0);
+ op.set_data_length(op_blob.size());
+
+ AnnotatedOperation aop;
+ aop.op = op;
+ aop.name = "SplitTestOp";
+
+ // Create the data file.
+ string data_path;
+ EXPECT_TRUE(utils::MakeTempFile(
+ "SplitReplaceOrReplaceBzTest_data.XXXXXX", &data_path, nullptr));
+ ScopedPathUnlinker data_path_unlinker(data_path);
+ int data_fd = open(data_path.c_str(), O_RDWR, 000);
+ EXPECT_GE(data_fd, 0);
+ ScopedFdCloser data_fd_closer(&data_fd);
+ EXPECT_TRUE(utils::WriteFile(data_path.c_str(), op_blob.data(),
+ op_blob.size()));
+ off_t data_file_size = op_blob.size();
+
+ // Split the operation.
+ vector<AnnotatedOperation> result_ops;
+ ASSERT_TRUE(ABGenerator::SplitReplaceOrReplaceBz(
+ aop, &result_ops, part_path, data_fd, &data_file_size));
+
+ // Check the result.
+ DeltaArchiveManifest_InstallOperation_Type expected_type =
+ compressible ?
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ :
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE;
+
+ ASSERT_EQ(2, result_ops.size());
+
+ EXPECT_EQ("SplitTestOp:0", result_ops[0].name);
+ DeltaArchiveManifest_InstallOperation first_op = result_ops[0].op;
+ EXPECT_EQ(expected_type, first_op.type());
+ EXPECT_EQ(op_ex1_size, first_op.dst_length());
+ EXPECT_EQ(1, first_op.dst_extents().size());
+ EXPECT_TRUE(ExtentEquals(first_op.dst_extents(0), op_ex1_start_block,
+ op_ex1_num_blocks));
+ // Obtain the expected blob.
+ chromeos::Blob first_expected_data(
+ part_data.begin() + op_ex1_offset,
+ part_data.begin() + op_ex1_offset + op_ex1_size);
+ chromeos::Blob first_expected_blob;
+ if (compressible) {
+ ASSERT_TRUE(BzipCompress(first_expected_data, &first_expected_blob));
+ } else {
+ first_expected_blob = first_expected_data;
+ }
+ EXPECT_EQ(first_expected_blob.size(), first_op.data_length());
+ // Check that the actual blob matches what's expected.
+ chromeos::Blob first_data_blob(first_op.data_length());
+ ssize_t bytes_read;
+ ASSERT_TRUE(utils::PReadAll(data_fd,
+ first_data_blob.data(),
+ first_op.data_length(),
+ first_op.data_offset(),
+ &bytes_read));
+ ASSERT_EQ(bytes_read, first_op.data_length());
+ EXPECT_EQ(first_expected_blob, first_data_blob);
+
+ EXPECT_EQ("SplitTestOp:1", result_ops[1].name);
+ DeltaArchiveManifest_InstallOperation second_op = result_ops[1].op;
+ EXPECT_EQ(expected_type, second_op.type());
+ EXPECT_EQ(op_ex2_size, second_op.dst_length());
+ EXPECT_EQ(1, second_op.dst_extents().size());
+ EXPECT_TRUE(ExtentEquals(second_op.dst_extents(0), op_ex2_start_block,
+ op_ex2_num_blocks));
+ // Obtain the expected blob.
+ chromeos::Blob second_expected_data(
+ part_data.begin() + op_ex2_offset,
+ part_data.begin() + op_ex2_offset + op_ex2_size);
+ chromeos::Blob second_expected_blob;
+ if (compressible) {
+ ASSERT_TRUE(BzipCompress(second_expected_data, &second_expected_blob));
+ } else {
+ second_expected_blob = second_expected_data;
+ }
+ EXPECT_EQ(second_expected_blob.size(), second_op.data_length());
+ // Check that the actual blob matches what's expected.
+ chromeos::Blob second_data_blob(second_op.data_length());
+ ASSERT_TRUE(utils::PReadAll(data_fd,
+ second_data_blob.data(),
+ second_op.data_length(),
+ second_op.data_offset(),
+ &bytes_read));
+ ASSERT_EQ(bytes_read, second_op.data_length());
+ EXPECT_EQ(second_expected_blob, second_data_blob);
+
+ // Check relative layout of data blobs.
+ EXPECT_EQ(first_op.data_offset() + first_op.data_length(),
+ second_op.data_offset());
+ EXPECT_EQ(second_op.data_offset() + second_op.data_length(), data_file_size);
+ // If we split a REPLACE into multiple ones, ensure reuse of preexisting blob.
+ if (!compressible &&
+ orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+ EXPECT_EQ(0, first_op.data_offset());
+ }
+}
+
+// Tests merging of REPLACE/REPLACE_BZ operations.
+void TestMergeReplaceOrReplaceBzOperations(
+ DeltaArchiveManifest_InstallOperation_Type orig_type,
+ bool compressible) {
+ const size_t first_op_num_blocks = 1;
+ const size_t second_op_num_blocks = 2;
+ const size_t total_op_num_blocks = first_op_num_blocks + second_op_num_blocks;
+ const size_t part_num_blocks = total_op_num_blocks + 2;
+
+ // Create the target partition data.
+ string part_path;
+ EXPECT_TRUE(utils::MakeTempFile(
+ "MergeReplaceOrReplaceBzTest_part.XXXXXX", &part_path, nullptr));
+ ScopedPathUnlinker part_path_unlinker(part_path);
+ const size_t part_size = part_num_blocks * kBlockSize;
+ chromeos::Blob part_data;
+ if (compressible) {
+ part_data.resize(part_size);
+ test_utils::FillWithData(&part_data);
+ } else {
+ std::mt19937 gen(12345);
+ std::uniform_int_distribution<uint8_t> dis(0, 255);
+ for (uint32_t i = 0; i < part_size; i++)
+ part_data.push_back(dis(gen));
+ }
+ ASSERT_EQ(part_size, part_data.size());
+ ASSERT_TRUE(utils::WriteFile(part_path.c_str(), part_data.data(), part_size));
+
+ // Create original operations and blob data.
+ vector<AnnotatedOperation> aops;
+ chromeos::Blob blob_data;
+ const size_t total_op_size = total_op_num_blocks * kBlockSize;
+
+ DeltaArchiveManifest_InstallOperation first_op;
+ first_op.set_type(orig_type);
+ const size_t first_op_size = first_op_num_blocks * kBlockSize;
+ first_op.set_dst_length(first_op_size);
+ *(first_op.add_dst_extents()) = ExtentForRange(0, first_op_num_blocks);
+ chromeos::Blob first_op_data(part_data.begin(),
+ part_data.begin() + first_op_size);
+ chromeos::Blob first_op_blob;
+ if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+ first_op_blob = first_op_data;
+ } else {
+ ASSERT_TRUE(BzipCompress(first_op_data, &first_op_blob));
+ }
+ first_op.set_data_offset(0);
+ first_op.set_data_length(first_op_blob.size());
+ blob_data.insert(blob_data.end(), first_op_blob.begin(), first_op_blob.end());
+ AnnotatedOperation first_aop;
+ first_aop.op = first_op;
+ first_aop.name = "first";
+ aops.push_back(first_aop);
+
+ DeltaArchiveManifest_InstallOperation second_op;
+ second_op.set_type(orig_type);
+ const size_t second_op_size = second_op_num_blocks * kBlockSize;
+ second_op.set_dst_length(second_op_size);
+ *(second_op.add_dst_extents()) = ExtentForRange(first_op_num_blocks,
+ second_op_num_blocks);
+ chromeos::Blob second_op_data(part_data.begin() + first_op_size,
+ part_data.begin() + total_op_size);
+ chromeos::Blob second_op_blob;
+ if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+ second_op_blob = second_op_data;
+ } else {
+ ASSERT_TRUE(BzipCompress(second_op_data, &second_op_blob));
+ }
+ second_op.set_data_offset(first_op_blob.size());
+ second_op.set_data_length(second_op_blob.size());
+ blob_data.insert(blob_data.end(), second_op_blob.begin(),
+ second_op_blob.end());
+ AnnotatedOperation second_aop;
+ second_aop.op = second_op;
+ second_aop.name = "second";
+ aops.push_back(second_aop);
+
+ // Create the data file.
+ string data_path;
+ EXPECT_TRUE(utils::MakeTempFile(
+ "MergeReplaceOrReplaceBzTest_data.XXXXXX", &data_path, nullptr));
+ ScopedPathUnlinker data_path_unlinker(data_path);
+ int data_fd = open(data_path.c_str(), O_RDWR, 000);
+ EXPECT_GE(data_fd, 0);
+ ScopedFdCloser data_fd_closer(&data_fd);
+ EXPECT_TRUE(utils::WriteFile(data_path.c_str(), blob_data.data(),
+ blob_data.size()));
+ off_t data_file_size = blob_data.size();
+
+ // Merge the operations.
+ EXPECT_TRUE(ABGenerator::MergeOperations(
+ &aops, 5 * kBlockSize, part_path, data_fd, &data_file_size));
+
+ // Check the result.
+ DeltaArchiveManifest_InstallOperation_Type expected_op_type =
+ compressible ?
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ :
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE;
+ EXPECT_EQ(1, aops.size());
+ DeltaArchiveManifest_InstallOperation new_op = aops[0].op;
+ EXPECT_EQ(expected_op_type, new_op.type());
+ EXPECT_FALSE(new_op.has_src_length());
+ EXPECT_EQ(total_op_num_blocks * kBlockSize, new_op.dst_length());
+ EXPECT_EQ(1, new_op.dst_extents().size());
+ EXPECT_TRUE(ExtentEquals(new_op.dst_extents(0), 0, total_op_num_blocks));
+ EXPECT_EQ("first,second", aops[0].name);
+
+ // Check to see if the blob pointed to in the new extent has what we expect.
+ chromeos::Blob expected_data(part_data.begin(),
+ part_data.begin() + total_op_size);
+ chromeos::Blob expected_blob;
+ if (compressible) {
+ ASSERT_TRUE(BzipCompress(expected_data, &expected_blob));
+ } else {
+ expected_blob = expected_data;
+ }
+ ASSERT_EQ(expected_blob.size(), new_op.data_length());
+ ASSERT_EQ(blob_data.size() + expected_blob.size(), data_file_size);
+ chromeos::Blob new_op_blob(new_op.data_length());
+ ssize_t bytes_read;
+ ASSERT_TRUE(utils::PReadAll(data_fd,
+ new_op_blob.data(),
+ new_op.data_length(),
+ new_op.data_offset(),
+ &bytes_read));
+ ASSERT_EQ(new_op.data_length(), bytes_read);
+ EXPECT_EQ(expected_blob, new_op_blob);
+}
+
+} // namespace
+
+class ABGeneratorTest : public ::testing::Test {};
+
+TEST_F(ABGeneratorTest, SplitSourceCopyTest) {
+ DeltaArchiveManifest_InstallOperation op;
+ op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+ *(op.add_src_extents()) = ExtentForRange(2, 3);
+ *(op.add_src_extents()) = ExtentForRange(6, 1);
+ *(op.add_src_extents()) = ExtentForRange(8, 4);
+ *(op.add_dst_extents()) = ExtentForRange(10, 2);
+ *(op.add_dst_extents()) = ExtentForRange(14, 3);
+ *(op.add_dst_extents()) = ExtentForRange(18, 3);
+
+ AnnotatedOperation aop;
+ aop.op = op;
+ aop.name = "SplitSourceCopyTestOp";
+ vector<AnnotatedOperation> result_ops;
+ EXPECT_TRUE(ABGenerator::SplitSourceCopy(aop, &result_ops));
+ EXPECT_EQ(result_ops.size(), 3);
+
+ EXPECT_EQ("SplitSourceCopyTestOp:0", result_ops[0].name);
+ DeltaArchiveManifest_InstallOperation first_op = result_ops[0].op;
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+ first_op.type());
+ EXPECT_EQ(kBlockSize * 2, first_op.src_length());
+ EXPECT_EQ(1, first_op.src_extents().size());
+ EXPECT_EQ(2, first_op.src_extents(0).start_block());
+ EXPECT_EQ(2, first_op.src_extents(0).num_blocks());
+ EXPECT_EQ(kBlockSize * 2, first_op.dst_length());
+ EXPECT_EQ(1, first_op.dst_extents().size());
+ EXPECT_EQ(10, first_op.dst_extents(0).start_block());
+ EXPECT_EQ(2, first_op.dst_extents(0).num_blocks());
+
+ EXPECT_EQ("SplitSourceCopyTestOp:1", result_ops[1].name);
+ DeltaArchiveManifest_InstallOperation second_op = result_ops[1].op;
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+ second_op.type());
+ EXPECT_EQ(kBlockSize * 3, second_op.src_length());
+ EXPECT_EQ(3, second_op.src_extents().size());
+ EXPECT_EQ(4, second_op.src_extents(0).start_block());
+ EXPECT_EQ(1, second_op.src_extents(0).num_blocks());
+ EXPECT_EQ(6, second_op.src_extents(1).start_block());
+ EXPECT_EQ(1, second_op.src_extents(1).num_blocks());
+ EXPECT_EQ(8, second_op.src_extents(2).start_block());
+ EXPECT_EQ(1, second_op.src_extents(2).num_blocks());
+ EXPECT_EQ(kBlockSize * 3, second_op.dst_length());
+ EXPECT_EQ(1, second_op.dst_extents().size());
+ EXPECT_EQ(14, second_op.dst_extents(0).start_block());
+ EXPECT_EQ(3, second_op.dst_extents(0).num_blocks());
+
+ EXPECT_EQ("SplitSourceCopyTestOp:2", result_ops[2].name);
+ DeltaArchiveManifest_InstallOperation third_op = result_ops[2].op;
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+ third_op.type());
+ EXPECT_EQ(kBlockSize * 3, third_op.src_length());
+ EXPECT_EQ(1, third_op.src_extents().size());
+ EXPECT_EQ(9, third_op.src_extents(0).start_block());
+ EXPECT_EQ(3, third_op.src_extents(0).num_blocks());
+ EXPECT_EQ(kBlockSize * 3, third_op.dst_length());
+ EXPECT_EQ(1, third_op.dst_extents().size());
+ EXPECT_EQ(18, third_op.dst_extents(0).start_block());
+ EXPECT_EQ(3, third_op.dst_extents(0).num_blocks());
+}
+
+TEST_F(ABGeneratorTest, SplitReplaceTest) {
+ TestSplitReplaceOrReplaceBzOperation(
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE, false);
+}
+
+TEST_F(ABGeneratorTest, SplitReplaceIntoReplaceBzTest) {
+ TestSplitReplaceOrReplaceBzOperation(
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE, true);
+}
+
+TEST_F(ABGeneratorTest, SplitReplaceBzTest) {
+ TestSplitReplaceOrReplaceBzOperation(
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, true);
+}
+
+TEST_F(ABGeneratorTest, SplitReplaceBzIntoReplaceTest) {
+ TestSplitReplaceOrReplaceBzOperation(
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, false);
+}
+
+TEST_F(ABGeneratorTest, SortOperationsByDestinationTest) {
+ vector<AnnotatedOperation> aops;
+ // One operation with multiple destination extents.
+ DeltaArchiveManifest_InstallOperation first_op;
+ *(first_op.add_dst_extents()) = ExtentForRange(6, 1);
+ *(first_op.add_dst_extents()) = ExtentForRange(10, 2);
+ AnnotatedOperation first_aop;
+ first_aop.op = first_op;
+ first_aop.name = "first";
+ aops.push_back(first_aop);
+
+ // One with no destination extent. Should end up at the end of the vector.
+ DeltaArchiveManifest_InstallOperation second_op;
+ AnnotatedOperation second_aop;
+ second_aop.op = second_op;
+ second_aop.name = "second";
+ aops.push_back(second_aop);
+
+ // One with one destination extent.
+ DeltaArchiveManifest_InstallOperation third_op;
+ *(third_op.add_dst_extents()) = ExtentForRange(3, 2);
+ AnnotatedOperation third_aop;
+ third_aop.op = third_op;
+ third_aop.name = "third";
+ aops.push_back(third_aop);
+
+ ABGenerator::SortOperationsByDestination(&aops);
+ EXPECT_EQ(aops.size(), 3);
+ EXPECT_EQ(third_aop.name, aops[0].name);
+ EXPECT_EQ(first_aop.name, aops[1].name);
+ EXPECT_EQ(second_aop.name, aops[2].name);
+}
+
+TEST_F(ABGeneratorTest, MergeSourceCopyOperationsTest) {
+ vector<AnnotatedOperation> aops;
+ DeltaArchiveManifest_InstallOperation first_op;
+ first_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+ first_op.set_src_length(kBlockSize);
+ first_op.set_dst_length(kBlockSize);
+ *(first_op.add_src_extents()) = ExtentForRange(1, 1);
+ *(first_op.add_dst_extents()) = ExtentForRange(6, 1);
+ AnnotatedOperation first_aop;
+ first_aop.op = first_op;
+ first_aop.name = "1";
+ aops.push_back(first_aop);
+
+ DeltaArchiveManifest_InstallOperation second_op;
+ second_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+ second_op.set_src_length(3 * kBlockSize);
+ second_op.set_dst_length(3 * kBlockSize);
+ *(second_op.add_src_extents()) = ExtentForRange(2, 2);
+ *(second_op.add_src_extents()) = ExtentForRange(8, 2);
+ *(second_op.add_dst_extents()) = ExtentForRange(7, 3);
+ *(second_op.add_dst_extents()) = ExtentForRange(11, 1);
+ AnnotatedOperation second_aop;
+ second_aop.op = second_op;
+ second_aop.name = "2";
+ aops.push_back(second_aop);
+
+ DeltaArchiveManifest_InstallOperation third_op;
+ third_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+ third_op.set_src_length(kBlockSize);
+ third_op.set_dst_length(kBlockSize);
+ *(third_op.add_src_extents()) = ExtentForRange(11, 1);
+ *(third_op.add_dst_extents()) = ExtentForRange(12, 1);
+ AnnotatedOperation third_aop;
+ third_aop.op = third_op;
+ third_aop.name = "3";
+ aops.push_back(third_aop);
+
+ EXPECT_TRUE(ABGenerator::MergeOperations(&aops, 5 * kBlockSize,
+ "", 0, nullptr));
+
+ EXPECT_EQ(aops.size(), 1);
+ DeltaArchiveManifest_InstallOperation first_result_op = aops[0].op;
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+ first_result_op.type());
+ EXPECT_EQ(kBlockSize * 5, first_result_op.src_length());
+ EXPECT_EQ(3, first_result_op.src_extents().size());
+ EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(0), 1, 3));
+ EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(1), 8, 2));
+ EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(2), 11, 1));
+ EXPECT_EQ(kBlockSize * 5, first_result_op.dst_length());
+ EXPECT_EQ(2, first_result_op.dst_extents().size());
+ EXPECT_TRUE(ExtentEquals(first_result_op.dst_extents(0), 6, 4));
+ EXPECT_TRUE(ExtentEquals(first_result_op.dst_extents(1), 11, 2));
+ EXPECT_EQ(aops[0].name, "1,2,3");
+}
+
+TEST_F(ABGeneratorTest, MergeReplaceOperationsTest) {
+ TestMergeReplaceOrReplaceBzOperations(
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE, false);
+}
+
+TEST_F(ABGeneratorTest, MergeReplaceOperationsToReplaceBzTest) {
+ TestMergeReplaceOrReplaceBzOperations(
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE, true);
+}
+
+TEST_F(ABGeneratorTest, MergeReplaceBzOperationsTest) {
+ TestMergeReplaceOrReplaceBzOperations(
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, true);
+}
+
+TEST_F(ABGeneratorTest, MergeReplaceBzOperationsToReplaceTest) {
+ TestMergeReplaceOrReplaceBzOperations(
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, false);
+}
+
+TEST_F(ABGeneratorTest, NoMergeOperationsTest) {
+ // Test to make sure we don't merge operations that shouldn't be merged.
+ vector<AnnotatedOperation> aops;
+ DeltaArchiveManifest_InstallOperation first_op;
+ first_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ *(first_op.add_dst_extents()) = ExtentForRange(0, 1);
+ first_op.set_data_length(kBlockSize);
+ AnnotatedOperation first_aop;
+ first_aop.op = first_op;
+ aops.push_back(first_aop);
+
+ // Should merge with first, except op types don't match...
+ DeltaArchiveManifest_InstallOperation second_op;
+ second_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ *(second_op.add_dst_extents()) = ExtentForRange(1, 2);
+ second_op.set_data_length(2 * kBlockSize);
+ AnnotatedOperation second_aop;
+ second_aop.op = second_op;
+ aops.push_back(second_aop);
+
+ // Should merge with second, except it would exceed chunk size...
+ DeltaArchiveManifest_InstallOperation third_op;
+ third_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ *(third_op.add_dst_extents()) = ExtentForRange(3, 3);
+ third_op.set_data_length(3 * kBlockSize);
+ AnnotatedOperation third_aop;
+ third_aop.op = third_op;
+ aops.push_back(third_aop);
+
+ // Should merge with third, except they aren't contiguous...
+ DeltaArchiveManifest_InstallOperation fourth_op;
+ fourth_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ *(fourth_op.add_dst_extents()) = ExtentForRange(7, 2);
+ fourth_op.set_data_length(2 * kBlockSize);
+ AnnotatedOperation fourth_aop;
+ fourth_aop.op = fourth_op;
+ aops.push_back(fourth_aop);
+
+ EXPECT_TRUE(ABGenerator::MergeOperations(
+ &aops, 4 * kBlockSize, "", 0, nullptr));
+
+ // No operations were merged, the number of ops is the same.
+ EXPECT_EQ(aops.size(), 4);
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 61ac4ad..bedfbbb 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -11,830 +11,31 @@
#include <sys/types.h>
#include <algorithm>
-#include <map>
#include <memory>
#include <string>
#include <utility>
#include <vector>
-#include <base/files/file_path.h>
-#include <base/files/file_util.h>
#include <base/logging.h>
-#include <base/strings/stringprintf.h>
-#include <base/strings/string_util.h>
-#include <bzlib.h>
-#include <chromeos/secure_blob.h>
-#include "update_engine/bzip.h"
#include "update_engine/delta_performer.h"
-#include "update_engine/file_writer.h"
-#include "update_engine/omaha_hash_calculator.h"
#include "update_engine/payload_constants.h"
-#include "update_engine/payload_generator/ext2_filesystem.h"
-#include "update_engine/payload_generator/extent_ranges.h"
+#include "update_engine/payload_generator/ab_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
#include "update_engine/payload_generator/full_update_generator.h"
#include "update_engine/payload_generator/inplace_generator.h"
-#include "update_engine/payload_generator/payload_signer.h"
-#include "update_engine/payload_generator/raw_filesystem.h"
-#include "update_engine/payload_verifier.h"
-#include "update_engine/subprocess.h"
-#include "update_engine/update_metadata.pb.h"
+#include "update_engine/payload_generator/payload_file.h"
#include "update_engine/utils.h"
-using std::map;
-using std::set;
-using std::sort;
using std::string;
using std::unique_ptr;
using std::vector;
-namespace {
-
-const uint64_t kMajorVersionNumber = 1;
-
-// The maximum destination size allowed for bsdiff. In general, bsdiff should
-// work for arbitrary big files, but the payload generation and payload
-// application requires a significant amount of RAM. We put a hard-limit of
-// 200 MiB that should not affect any released board, but will limit the
-// Chrome binary in ASan builders.
-const uint64_t kMaxBsdiffDestinationSize = 200 * 1024 * 1024; // bytes
-
-static const char* kInstallOperationTypes[] = {
- "REPLACE",
- "REPLACE_BZ",
- "MOVE",
- "BSDIFF",
- "SOURCE_COPY",
- "SOURCE_BSDIFF"
-};
-
-} // namespace
-
namespace chromeos_update_engine {
-typedef map<const DeltaArchiveManifest_InstallOperation*,
- string> OperationNameMap;
-
// bytes
const size_t kRootFSPartitionSize = static_cast<size_t>(2) * 1024 * 1024 * 1024;
const size_t kBlockSize = 4096; // bytes
-const char* const kEmptyPath = "";
-const char* const kBsdiffPath = "bsdiff";
-
-namespace {
-
-// Writes the uint64_t passed in in host-endian to the file as big-endian.
-// Returns true on success.
-bool WriteUint64AsBigEndian(FileWriter* writer, const uint64_t value) {
- uint64_t value_be = htobe64(value);
- TEST_AND_RETURN_FALSE(writer->Write(&value_be, sizeof(value_be)));
- return true;
-}
-
-// Adds each operation from |rootfs_ops| and |kernel_ops| to |out_manifest| in
-// the order they come in those vectors. reports the operations names
-void InstallOperationsToManifest(
- const vector<AnnotatedOperation>& rootfs_ops,
- const vector<AnnotatedOperation>& kernel_ops,
- DeltaArchiveManifest* out_manifest,
- OperationNameMap* out_op_name_map) {
- for (const AnnotatedOperation& aop : rootfs_ops) {
- if (DeltaDiffGenerator::IsNoopOperation(aop.op))
- continue;
- DeltaArchiveManifest_InstallOperation* new_op =
- out_manifest->add_install_operations();
- (*out_op_name_map)[new_op] = aop.name;
- *new_op = aop.op;
- }
- for (const AnnotatedOperation& aop : kernel_ops) {
- if (DeltaDiffGenerator::IsNoopOperation(aop.op))
- continue;
- DeltaArchiveManifest_InstallOperation* new_op =
- out_manifest->add_kernel_install_operations();
- (*out_op_name_map)[new_op] = aop.name;
- *new_op = aop.op;
- }
-}
-
-struct DeltaObject {
- DeltaObject(const string& in_name, const int in_type, const off_t in_size)
- : name(in_name),
- type(in_type),
- size(in_size) {}
- bool operator <(const DeltaObject& object) const {
- return (size != object.size) ? (size < object.size) : (name < object.name);
- }
- string name;
- int type;
- off_t size;
-};
-
-void ReportPayloadUsage(const DeltaArchiveManifest& manifest,
- const int64_t manifest_metadata_size,
- const OperationNameMap& op_name_map) {
- vector<DeltaObject> objects;
- off_t total_size = 0;
-
- // Rootfs install operations.
- for (int i = 0; i < manifest.install_operations_size(); ++i) {
- const DeltaArchiveManifest_InstallOperation& op =
- manifest.install_operations(i);
- objects.push_back(DeltaObject(op_name_map.find(&op)->second,
- op.type(),
- op.data_length()));
- total_size += op.data_length();
- }
-
- // Kernel install operations.
- for (int i = 0; i < manifest.kernel_install_operations_size(); ++i) {
- const DeltaArchiveManifest_InstallOperation& op =
- manifest.kernel_install_operations(i);
- objects.push_back(DeltaObject(base::StringPrintf("<kernel-operation-%d>",
- i),
- op.type(),
- op.data_length()));
- total_size += op.data_length();
- }
-
- objects.push_back(DeltaObject("<manifest-metadata>",
- -1,
- manifest_metadata_size));
- total_size += manifest_metadata_size;
-
- sort(objects.begin(), objects.end());
-
- static const char kFormatString[] = "%6.2f%% %10jd %-10s %s\n";
- for (const DeltaObject& object : objects) {
- fprintf(stderr, kFormatString,
- object.size * 100.0 / total_size,
- static_cast<intmax_t>(object.size),
- object.type >= 0 ? kInstallOperationTypes[object.type] : "-",
- object.name.c_str());
- }
- fprintf(stderr, kFormatString,
- 100.0, static_cast<intmax_t>(total_size), "", "<total>");
-}
-
-// Process a range of blocks from |range_start| to |range_end| in the extent at
-// position |*idx_p| of |extents|. If |do_remove| is true, this range will be
-// removed, which may cause the extent to be trimmed, split or removed entirely.
-// The value of |*idx_p| is updated to point to the next extent to be processed.
-// Returns true iff the next extent to process is a new or updated one.
-bool ProcessExtentBlockRange(vector<Extent>* extents, size_t* idx_p,
- const bool do_remove, uint64_t range_start,
- uint64_t range_end) {
- size_t idx = *idx_p;
- uint64_t start_block = (*extents)[idx].start_block();
- uint64_t num_blocks = (*extents)[idx].num_blocks();
- uint64_t range_size = range_end - range_start;
-
- if (do_remove) {
- if (range_size == num_blocks) {
- // Remove the entire extent.
- extents->erase(extents->begin() + idx);
- } else if (range_end == num_blocks) {
- // Trim the end of the extent.
- (*extents)[idx].set_num_blocks(num_blocks - range_size);
- idx++;
- } else if (range_start == 0) {
- // Trim the head of the extent.
- (*extents)[idx].set_start_block(start_block + range_size);
- (*extents)[idx].set_num_blocks(num_blocks - range_size);
- } else {
- // Trim the middle, splitting the remainder into two parts.
- (*extents)[idx].set_num_blocks(range_start);
- Extent e;
- e.set_start_block(start_block + range_end);
- e.set_num_blocks(num_blocks - range_end);
- idx++;
- extents->insert(extents->begin() + idx, e);
- }
- } else if (range_end == num_blocks) {
- // Done with this extent.
- idx++;
- } else {
- return false;
- }
-
- *idx_p = idx;
- return true;
-}
-
-// Remove identical corresponding block ranges in |src_extents| and
-// |dst_extents|. Used for preventing moving of blocks onto themselves during
-// MOVE operations. The value of |total_bytes| indicates the actual length of
-// content; this may be slightly less than the total size of blocks, in which
-// case the last block is only partly occupied with data. Returns the total
-// number of bytes removed.
-size_t RemoveIdenticalBlockRanges(vector<Extent>* src_extents,
- vector<Extent>* dst_extents,
- const size_t total_bytes) {
- size_t src_idx = 0;
- size_t dst_idx = 0;
- uint64_t src_offset = 0, dst_offset = 0;
- bool new_src = true, new_dst = true;
- size_t removed_bytes = 0, nonfull_block_bytes;
- bool do_remove = false;
- while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) {
- if (new_src) {
- src_offset = 0;
- new_src = false;
- }
- if (new_dst) {
- dst_offset = 0;
- new_dst = false;
- }
-
- do_remove = ((*src_extents)[src_idx].start_block() + src_offset ==
- (*dst_extents)[dst_idx].start_block() + dst_offset);
-
- uint64_t src_num_blocks = (*src_extents)[src_idx].num_blocks();
- uint64_t dst_num_blocks = (*dst_extents)[dst_idx].num_blocks();
- uint64_t min_num_blocks = std::min(src_num_blocks - src_offset,
- dst_num_blocks - dst_offset);
- uint64_t prev_src_offset = src_offset;
- uint64_t prev_dst_offset = dst_offset;
- src_offset += min_num_blocks;
- dst_offset += min_num_blocks;
-
- new_src = ProcessExtentBlockRange(src_extents, &src_idx, do_remove,
- prev_src_offset, src_offset);
- new_dst = ProcessExtentBlockRange(dst_extents, &dst_idx, do_remove,
- prev_dst_offset, dst_offset);
- if (do_remove)
- removed_bytes += min_num_blocks * kBlockSize;
- }
-
- // If we removed the last block and this block is only partly used by file
- // content, deduct the unused portion from the total removed byte count.
- if (do_remove && (nonfull_block_bytes = total_bytes % kBlockSize))
- removed_bytes -= kBlockSize - nonfull_block_bytes;
-
- return removed_bytes;
-}
-
-// Compare two AnnotatedOperations by the start block of the first Extent in
-// their destination extents.
-bool CompareAopsByDestination(AnnotatedOperation first_aop,
- AnnotatedOperation second_aop) {
- // We want empty operations to be at the end of the payload.
- if (!first_aop.op.dst_extents().size() || !second_aop.op.dst_extents().size())
- return ((!first_aop.op.dst_extents().size()) <
- (!second_aop.op.dst_extents().size()));
- uint32_t first_dst_start = first_aop.op.dst_extents(0).start_block();
- uint32_t second_dst_start = second_aop.op.dst_extents(0).start_block();
- return first_dst_start < second_dst_start;
-}
-
-} // namespace
-
-bool DeltaDiffGenerator::DeltaReadFilesystem(
- vector<AnnotatedOperation>* aops,
- const string& old_part,
- const string& new_part,
- FilesystemInterface* old_fs,
- FilesystemInterface* new_fs,
- off_t chunk_blocks,
- int data_fd,
- off_t* data_file_size,
- bool skip_block_0,
- bool src_ops_allowed) {
- ExtentRanges old_visited_blocks;
- ExtentRanges new_visited_blocks;
-
- // We can't produce a MOVE operation with a 0 block as neither source nor
- // destination, so we avoid generating an operation for the block 0 here, and
- // we will add an operation for it in the InplaceGenerator. Excluding both
- // old and new blocks ensures that identical images would still produce empty
- // deltas.
- if (skip_block_0) {
- old_visited_blocks.AddBlock(0);
- new_visited_blocks.AddBlock(0);
- }
-
- map<string, vector<Extent>> old_files_map;
- if (old_fs) {
- vector<FilesystemInterface::File> old_files;
- old_fs->GetFiles(&old_files);
- for (const FilesystemInterface::File& file : old_files)
- old_files_map[file.name] = file.extents;
- }
-
- vector<FilesystemInterface::File> new_files;
- new_fs->GetFiles(&new_files);
-
- // The processing is very straightforward here, we generate operations for
- // every file (and pseudo-file such as the metadata) in the new filesystem
- // based on the file with the same name in the old filesystem, if any.
- // Files with overlapping data blocks (like hardlinks or filesystems with tail
- // packing or compression where the blocks store more than one file) are only
- // generated once in the new image, but are also used only once from the old
- // image due to some simplifications (see below).
- for (const FilesystemInterface::File& new_file : new_files) {
- // Ignore the files in the new filesystem without blocks. Symlinks with
- // data blocks (for example, symlinks bigger than 60 bytes in ext2) are
- // handled as normal files. We also ignore blocks that were already
- // processed by a previous file.
- vector<Extent> new_file_extents = FilterExtentRanges(
- new_file.extents, new_visited_blocks);
- new_visited_blocks.AddExtents(new_file_extents);
-
- if (new_file_extents.empty())
- continue;
-
- LOG(INFO) << "Encoding file " << new_file.name << " ("
- << BlocksInExtents(new_file_extents) << " blocks)";
-
- // We can't visit each dst image inode more than once, as that would
- // duplicate work. Here, we avoid visiting each source image inode
- // more than once. Technically, we could have multiple operations
- // that read the same blocks from the source image for diffing, but
- // we choose not to avoid complexity. Eventually we will move away
- // from using a graph/cycle detection/etc to generate diffs, and at that
- // time, it will be easy (non-complex) to have many operations read
- // from the same source blocks. At that time, this code can die. -adlr
- vector<Extent> old_file_extents = FilterExtentRanges(
- old_files_map[new_file.name], old_visited_blocks);
- old_visited_blocks.AddExtents(old_file_extents);
-
- TEST_AND_RETURN_FALSE(DeltaReadFile(
- aops,
- old_part,
- new_part,
- old_file_extents,
- new_file_extents,
- new_file.name, // operation name
- chunk_blocks,
- data_fd,
- data_file_size,
- src_ops_allowed));
- }
- // Process all the blocks not included in any file. We provided all the unused
- // blocks in the old partition as available data.
- vector<Extent> new_unvisited = { ExtentForRange(0, new_fs->GetBlockCount()) };
- new_unvisited = FilterExtentRanges(new_unvisited, new_visited_blocks);
- if (new_unvisited.empty())
- return true;
-
- vector<Extent> old_unvisited;
- if (old_fs) {
- old_unvisited.push_back(ExtentForRange(0, old_fs->GetBlockCount()));
- old_unvisited = FilterExtentRanges(old_unvisited, old_visited_blocks);
- }
-
- LOG(INFO) << "Scanning " << BlocksInExtents(new_unvisited)
- << " unwritten blocks";
- TEST_AND_RETURN_FALSE(DeltaReadFile(
- aops,
- old_part,
- new_part,
- old_unvisited,
- new_unvisited,
- "<non-file-data>", // operation name
- chunk_blocks,
- data_fd,
- data_file_size,
- src_ops_allowed));
-
- return true;
-}
-
-bool DeltaDiffGenerator::DeltaReadFile(
- vector<AnnotatedOperation>* aops,
- const string& old_part,
- const string& new_part,
- const vector<Extent>& old_extents,
- const vector<Extent>& new_extents,
- const string& name,
- off_t chunk_blocks,
- int data_fd,
- off_t* data_file_size,
- bool src_ops_allowed) {
- chromeos::Blob data;
- DeltaArchiveManifest_InstallOperation operation;
-
- uint64_t total_blocks = BlocksInExtents(new_extents);
- if (chunk_blocks == -1)
- chunk_blocks = total_blocks;
-
- // If bsdiff breaks again, blacklist the problem file by using:
- // bsdiff_allowed = (name != "/foo/bar")
- //
- // TODO(dgarrett): chromium-os:15274 connect this test to the command line.
- bool bsdiff_allowed = true;
- if (static_cast<uint64_t>(chunk_blocks) * kBlockSize >
- kMaxBsdiffDestinationSize) {
- bsdiff_allowed = false;
- }
-
- if (!bsdiff_allowed) {
- LOG(INFO) << "bsdiff blacklisting: " << name;
- }
-
- for (uint64_t block_offset = 0; block_offset < total_blocks;
- block_offset += chunk_blocks) {
- // Split the old/new file in the same chunks. Note that this could drop
- // some information from the old file used for the new chunk. If the old
- // file is smaller (or even empty when there's no old file) the chunk will
- // also be empty.
- vector<Extent> old_extents_chunk = ExtentsSublist(
- old_extents, block_offset, chunk_blocks);
- vector<Extent> new_extents_chunk = ExtentsSublist(
- new_extents, block_offset, chunk_blocks);
- NormalizeExtents(&old_extents_chunk);
- NormalizeExtents(&new_extents_chunk);
-
- TEST_AND_RETURN_FALSE(ReadExtentsToDiff(old_part,
- new_part,
- old_extents_chunk,
- new_extents_chunk,
- bsdiff_allowed,
- &data,
- &operation,
- src_ops_allowed));
-
- // Check if the operation writes nothing.
- if (operation.dst_extents_size() == 0) {
- if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
- LOG(INFO) << "Empty MOVE operation ("
- << name << "), skipping";
- continue;
- } else {
- LOG(ERROR) << "Empty non-MOVE operation";
- return false;
- }
- }
-
- // Write the data
- if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE &&
- operation.type() !=
- DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) {
- operation.set_data_offset(*data_file_size);
- operation.set_data_length(data.size());
- }
-
- TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, data.data(), data.size()));
- *data_file_size += data.size();
-
- // Now, insert into the list of operations.
- AnnotatedOperation aop;
- aop.name = name;
- if (static_cast<uint64_t>(chunk_blocks) < total_blocks) {
- aop.name = base::StringPrintf("%s:%" PRIu64,
- name.c_str(), block_offset / chunk_blocks);
- }
- aop.op = operation;
- aops->emplace_back(aop);
- }
- return true;
-}
-
-bool DeltaDiffGenerator::ReadExtentsToDiff(
- const string& old_part,
- const string& new_part,
- const vector<Extent>& old_extents,
- const vector<Extent>& new_extents,
- bool bsdiff_allowed,
- chromeos::Blob* out_data,
- DeltaArchiveManifest_InstallOperation* out_op,
- bool src_ops_allowed) {
- DeltaArchiveManifest_InstallOperation operation;
- // Data blob that will be written to delta file.
- const chromeos::Blob* data_blob = nullptr;
-
- // We read blocks from old_extents and write blocks to new_extents.
- uint64_t blocks_to_read = BlocksInExtents(old_extents);
- uint64_t blocks_to_write = BlocksInExtents(new_extents);
-
- // Make copies of the extents so we can modify them.
- vector<Extent> src_extents = old_extents;
- vector<Extent> dst_extents = new_extents;
-
- // Read in bytes from new data.
- chromeos::Blob new_data;
- TEST_AND_RETURN_FALSE(utils::ReadExtents(new_part,
- new_extents,
- &new_data,
- kBlockSize * blocks_to_write,
- kBlockSize));
- TEST_AND_RETURN_FALSE(!new_data.empty());
-
-
- // Using a REPLACE is always an option.
- operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
- data_blob = &new_data;
-
- // Try compressing it with bzip2.
- chromeos::Blob new_data_bz;
- TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
- CHECK(!new_data_bz.empty());
- if (new_data_bz.size() < data_blob->size()) {
- // A REPLACE_BZ is better.
- operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
- data_blob = &new_data_bz;
- }
-
- chromeos::Blob old_data;
- chromeos::Blob empty_blob;
- chromeos::Blob bsdiff_delta;
- if (blocks_to_read > 0) {
- // Read old data.
- TEST_AND_RETURN_FALSE(
- utils::ReadExtents(old_part, src_extents, &old_data,
- kBlockSize * blocks_to_read, kBlockSize));
- if (old_data == new_data) {
- // No change in data.
- if (src_ops_allowed) {
- operation.set_type(
- DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
- } else {
- operation.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
- }
- data_blob = &empty_blob;
- } else if (bsdiff_allowed) {
- // If the source file is considered bsdiff safe (no bsdiff bugs
- // triggered), see if BSDIFF encoding is smaller.
- base::FilePath old_chunk;
- TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&old_chunk));
- ScopedPathUnlinker old_unlinker(old_chunk.value());
- TEST_AND_RETURN_FALSE(
- utils::WriteFile(old_chunk.value().c_str(),
- old_data.data(), old_data.size()));
- base::FilePath new_chunk;
- TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&new_chunk));
- ScopedPathUnlinker new_unlinker(new_chunk.value());
- TEST_AND_RETURN_FALSE(
- utils::WriteFile(new_chunk.value().c_str(),
- new_data.data(), new_data.size()));
-
- TEST_AND_RETURN_FALSE(
- BsdiffFiles(old_chunk.value(), new_chunk.value(), &bsdiff_delta));
- CHECK_GT(bsdiff_delta.size(), static_cast<chromeos::Blob::size_type>(0));
- if (bsdiff_delta.size() < data_blob->size()) {
- if (src_ops_allowed) {
- operation.set_type(
- DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF);
- } else {
- operation.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
- }
- data_blob = &bsdiff_delta;
- }
- }
- }
-
- size_t removed_bytes = 0;
- // Remove identical src/dst block ranges in MOVE operations.
- if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
- removed_bytes = RemoveIdenticalBlockRanges(
- &src_extents, &dst_extents, new_data.size());
- }
- // Set legacy src_length and dst_length fields.
- operation.set_src_length(old_data.size() - removed_bytes);
- operation.set_dst_length(new_data.size() - removed_bytes);
-
- // Embed extents in the operation.
- StoreExtents(src_extents, operation.mutable_src_extents());
- StoreExtents(dst_extents, operation.mutable_dst_extents());
-
- // Replace operations should not have source extents.
- if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
- operation.type() ==
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
- operation.clear_src_extents();
- operation.clear_src_length();
- }
-
- *out_data = std::move(*data_blob);
- *out_op = operation;
-
- return true;
-}
-
-bool DeltaDiffGenerator::DeltaCompressKernelPartition(
- const string& old_kernel_part,
- const string& new_kernel_part,
- uint64_t old_kernel_size,
- uint64_t new_kernel_size,
- uint64_t block_size,
- vector<AnnotatedOperation>* aops,
- int blobs_fd,
- off_t* blobs_length,
- bool src_ops_allowed) {
- LOG(INFO) << "Delta compressing kernel partition...";
- LOG_IF(INFO, old_kernel_part.empty()) << "Generating full kernel update...";
-
- unique_ptr<RawFilesystem> old_kernel_fs;
- if (!old_kernel_part.empty())
- old_kernel_fs = RawFilesystem::Create("<kernel-delta-operation>",
- block_size,
- old_kernel_size / block_size);
- unique_ptr<RawFilesystem> new_kernel_fs = RawFilesystem::Create(
- "<kernel-delta-operation>",
- block_size,
- new_kernel_size / block_size);
-
- TEST_AND_RETURN_FALSE(DeltaReadFilesystem(aops,
- old_kernel_part,
- new_kernel_part,
- old_kernel_fs.get(),
- new_kernel_fs.get(),
- -1, // chunk_blocks
- blobs_fd,
- blobs_length,
- false, // skip_block_0
- src_ops_allowed));
-
- LOG(INFO) << "Done delta compressing kernel partition.";
- return true;
-}
-
-bool DeltaDiffGenerator::InitializePartitionInfo(const PartitionConfig& part,
- PartitionInfo* info) {
- info->set_size(part.size);
- OmahaHashCalculator hasher;
- TEST_AND_RETURN_FALSE(hasher.UpdateFile(part.path, part.size) ==
- static_cast<off_t>(part.size));
- TEST_AND_RETURN_FALSE(hasher.Finalize());
- const chromeos::Blob& hash = hasher.raw_hash();
- info->set_hash(hash.data(), hash.size());
- LOG(INFO) << part.path << ": size=" << part.size << " hash=" << hasher.hash();
- return true;
-}
-
-bool InitializePartitionInfos(const PayloadGenerationConfig& config,
- DeltaArchiveManifest* manifest) {
- if (!config.source.kernel.path.empty()) {
- TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
- config.source.kernel,
- manifest->mutable_old_kernel_info()));
- }
- TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
- config.target.kernel,
- manifest->mutable_new_kernel_info()));
- if (!config.source.rootfs.path.empty()) {
- TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
- config.source.rootfs,
- manifest->mutable_old_rootfs_info()));
- }
- TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
- config.target.rootfs,
- manifest->mutable_new_rootfs_info()));
- return true;
-}
-
-// Stores all Extents in 'extents' into 'out'.
-void DeltaDiffGenerator::StoreExtents(
- const vector<Extent>& extents,
- google::protobuf::RepeatedPtrField<Extent>* out) {
- for (const Extent& extent : extents) {
- Extent* new_extent = out->Add();
- *new_extent = extent;
- }
-}
-
-// Stores all extents in |extents| into |out_vector|.
-void DeltaDiffGenerator::ExtentsToVector(
- const google::protobuf::RepeatedPtrField<Extent>& extents,
- vector<Extent>* out_vector) {
- out_vector->clear();
- for (int i = 0; i < extents.size(); i++) {
- out_vector->push_back(extents.Get(i));
- }
-}
-
-// Returns true if |op| is a no-op operation that doesn't do any useful work
-// (e.g., a move operation that copies blocks onto themselves).
-bool DeltaDiffGenerator::IsNoopOperation(
- const DeltaArchiveManifest_InstallOperation& op) {
- return (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE &&
- ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
-}
-
-void DeltaDiffGenerator::FilterNoopOperations(vector<AnnotatedOperation>* ops) {
- ops->erase(
- std::remove_if(
- ops->begin(), ops->end(),
- [](const AnnotatedOperation& aop){return IsNoopOperation(aop.op);}),
- ops->end());
-}
-
-bool DeltaDiffGenerator::ReorderDataBlobs(
- DeltaArchiveManifest* manifest,
- const string& data_blobs_path,
- const string& new_data_blobs_path) {
- int in_fd = open(data_blobs_path.c_str(), O_RDONLY, 0);
- TEST_AND_RETURN_FALSE_ERRNO(in_fd >= 0);
- ScopedFdCloser in_fd_closer(&in_fd);
-
- DirectFileWriter writer;
- TEST_AND_RETURN_FALSE(
- writer.Open(new_data_blobs_path.c_str(),
- O_WRONLY | O_TRUNC | O_CREAT,
- 0644) == 0);
- ScopedFileWriterCloser writer_closer(&writer);
- uint64_t out_file_size = 0;
-
- for (int i = 0; i < (manifest->install_operations_size() +
- manifest->kernel_install_operations_size()); i++) {
- DeltaArchiveManifest_InstallOperation* op = nullptr;
- if (i < manifest->install_operations_size()) {
- op = manifest->mutable_install_operations(i);
- } else {
- op = manifest->mutable_kernel_install_operations(
- i - manifest->install_operations_size());
- }
- if (!op->has_data_offset())
- continue;
- CHECK(op->has_data_length());
- chromeos::Blob buf(op->data_length());
- ssize_t rc = pread(in_fd, buf.data(), buf.size(), op->data_offset());
- TEST_AND_RETURN_FALSE(rc == static_cast<ssize_t>(buf.size()));
-
- // Add the hash of the data blobs for this operation
- TEST_AND_RETURN_FALSE(AddOperationHash(op, buf));
-
- op->set_data_offset(out_file_size);
- TEST_AND_RETURN_FALSE(writer.Write(buf.data(), buf.size()));
- out_file_size += buf.size();
- }
- return true;
-}
-
-bool DeltaDiffGenerator::AddOperationHash(
- DeltaArchiveManifest_InstallOperation* op,
- const chromeos::Blob& buf) {
- OmahaHashCalculator hasher;
- TEST_AND_RETURN_FALSE(hasher.Update(buf.data(), buf.size()));
- TEST_AND_RETURN_FALSE(hasher.Finalize());
- const chromeos::Blob& hash = hasher.raw_hash();
- op->set_data_sha256_hash(hash.data(), hash.size());
- return true;
-}
-
-bool DeltaDiffGenerator::GenerateOperations(
- const PayloadGenerationConfig& config,
- int data_file_fd,
- off_t* data_file_size,
- vector<AnnotatedOperation>* rootfs_ops,
- vector<AnnotatedOperation>* kernel_ops) {
- unique_ptr<Ext2Filesystem> old_fs = Ext2Filesystem::CreateFromFile(
- config.source.rootfs.path);
- unique_ptr<Ext2Filesystem> new_fs = Ext2Filesystem::CreateFromFile(
- config.target.rootfs.path);
-
- off_t chunk_blocks = config.chunk_size == -1 ? -1 : (
- config.chunk_size / config.block_size);
-
- rootfs_ops->clear();
- TEST_AND_RETURN_FALSE(DeltaReadFilesystem(rootfs_ops,
- config.source.rootfs.path,
- config.target.rootfs.path,
- old_fs.get(),
- new_fs.get(),
- chunk_blocks,
- data_file_fd,
- data_file_size,
- false, // skip_block_0
- true)); // src_ops_allowed
- LOG(INFO) << "done reading normal files";
-
- // Read kernel partition
- TEST_AND_RETURN_FALSE(
- DeltaCompressKernelPartition(config.source.kernel.path,
- config.target.kernel.path,
- config.source.kernel.size,
- config.target.kernel.size,
- config.block_size,
- kernel_ops,
- data_file_fd,
- data_file_size,
- true)); // src_ops_allowed
- LOG(INFO) << "done reading kernel";
-
- TEST_AND_RETURN_FALSE(FragmentOperations(rootfs_ops,
- config.target.rootfs.path,
- data_file_fd,
- data_file_size));
- TEST_AND_RETURN_FALSE(FragmentOperations(kernel_ops,
- config.target.kernel.path,
- data_file_fd,
- data_file_size));
- SortOperationsByDestination(rootfs_ops);
- SortOperationsByDestination(kernel_ops);
- // TODO(alliewood): Change merge operations to use config.chunk_size once
- // specifying chunk_size on the command line works. crbug/485397.
- TEST_AND_RETURN_FALSE(MergeOperations(rootfs_ops,
- kDefaultChunkSize,
- config.target.rootfs.path,
- data_file_fd,
- data_file_size));
- TEST_AND_RETURN_FALSE(MergeOperations(kernel_ops,
- kDefaultChunkSize,
- config.target.kernel.path,
- data_file_fd,
- data_file_size));
- return true;
-}
bool GenerateUpdatePayloadFile(
const PayloadGenerationConfig& config,
@@ -859,14 +60,13 @@
const string kTempFileTemplate("CrAU_temp_data.XXXXXX");
string temp_file_path;
- unique_ptr<ScopedPathUnlinker> temp_file_unlinker;
off_t data_file_size = 0;
LOG(INFO) << "Reading files...";
- // Create empty protobuf Manifest object
- DeltaArchiveManifest manifest;
- manifest.set_minor_version(config.minor_version);
+ // Create empty payload file object.
+ PayloadFile payload;
+ TEST_AND_RETURN_FALSE(payload.Init(config));
vector<AnnotatedOperation> rootfs_ops;
vector<AnnotatedOperation> kernel_ops;
@@ -877,17 +77,16 @@
// We don't efficiently support deltas on squashfs. For now, we will
// produce full operations in that case.
if (utils::IsSquashfsFilesystem(config.target.rootfs.path)) {
- LOG(INFO) << "Using generator FullUpdateGenerator::Run for squashfs "
- "deltas";
+ LOG(INFO) << "Using generator FullUpdateGenerator() for squashfs deltas";
strategy.reset(new FullUpdateGenerator());
} else if (utils::IsExtFilesystem(config.target.rootfs.path)) {
// Delta update (with possibly a full kernel update).
if (config.minor_version == kInPlaceMinorPayloadVersion) {
- LOG(INFO) << "Using generator InplaceGenerator::GenerateInplaceDelta";
+ LOG(INFO) << "Using generator InplaceGenerator()";
strategy.reset(new InplaceGenerator());
} else if (config.minor_version == kSourceMinorPayloadVersion) {
- LOG(INFO) << "Using generator DeltaDiffGenerator::GenerateSourceDelta";
- strategy.reset(new DeltaDiffGenerator());
+ LOG(INFO) << "Using generator ABGenerator()";
+ strategy.reset(new ABGenerator());
} else {
LOG(ERROR) << "Unsupported minor version given for delta payload: "
<< config.minor_version;
@@ -904,14 +103,16 @@
strategy.reset(new FullUpdateGenerator());
}
- {
- int data_file_fd;
- TEST_AND_RETURN_FALSE(
- utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &data_file_fd));
- temp_file_unlinker.reset(new ScopedPathUnlinker(temp_file_path));
- TEST_AND_RETURN_FALSE(data_file_fd >= 0);
- ScopedFdCloser data_file_fd_closer(&data_file_fd);
+ int data_file_fd;
+ TEST_AND_RETURN_FALSE(
+ utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &data_file_fd));
+ unique_ptr<ScopedPathUnlinker> temp_file_unlinker(
+ new ScopedPathUnlinker(temp_file_path));
+ TEST_AND_RETURN_FALSE(data_file_fd >= 0);
+
+ {
+ ScopedFdCloser data_file_fd_closer(&data_file_fd);
// Generate the operations using the strategy we selected above.
TEST_AND_RETURN_FALSE(strategy->GenerateOperations(config,
data_file_fd,
@@ -920,458 +121,22 @@
&kernel_ops));
}
- if (!config.source.ImageInfoIsEmpty())
- *(manifest.mutable_old_image_info()) = config.source.image_info;
-
- if (!config.target.ImageInfoIsEmpty())
- *(manifest.mutable_new_image_info()) = config.target.image_info;
-
// Filter the no-operations. OperationsGenerators should not output this kind
// of operations normally, but this is an extra step to fix that if
// happened.
- DeltaDiffGenerator::FilterNoopOperations(&rootfs_ops);
- DeltaDiffGenerator::FilterNoopOperations(&kernel_ops);
+ diff_utils::FilterNoopOperations(&rootfs_ops);
+ diff_utils::FilterNoopOperations(&kernel_ops);
- OperationNameMap op_name_map;
- InstallOperationsToManifest(rootfs_ops, kernel_ops, &manifest, &op_name_map);
- manifest.set_block_size(config.block_size);
-
- // Reorder the data blobs with the newly ordered manifest.
- string ordered_blobs_path;
- TEST_AND_RETURN_FALSE(utils::MakeTempFile(
- "CrAU_temp_data.ordered.XXXXXX",
- &ordered_blobs_path,
- nullptr));
- ScopedPathUnlinker ordered_blobs_unlinker(ordered_blobs_path);
- TEST_AND_RETURN_FALSE(
- DeltaDiffGenerator::ReorderDataBlobs(&manifest,
- temp_file_path,
- ordered_blobs_path));
+ // Write payload file to disk.
+ payload.AddPartitionOperations(PartitionName::kRootfs, rootfs_ops);
+ payload.AddPartitionOperations(PartitionName::kKernel, kernel_ops);
+ payload.WritePayload(output_path, temp_file_path, private_key_path,
+ metadata_size);
temp_file_unlinker.reset();
- // Check that install op blobs are in order.
- uint64_t next_blob_offset = 0;
- {
- for (int i = 0; i < (manifest.install_operations_size() +
- manifest.kernel_install_operations_size()); i++) {
- DeltaArchiveManifest_InstallOperation* op =
- i < manifest.install_operations_size() ?
- manifest.mutable_install_operations(i) :
- manifest.mutable_kernel_install_operations(
- i - manifest.install_operations_size());
- if (op->has_data_offset()) {
- if (op->data_offset() != next_blob_offset) {
- LOG(FATAL) << "bad blob offset! " << op->data_offset() << " != "
- << next_blob_offset;
- }
- next_blob_offset += op->data_length();
- }
- }
- }
-
- // Signatures appear at the end of the blobs. Note the offset in the
- // manifest
- if (!private_key_path.empty()) {
- uint64_t signature_blob_length = 0;
- TEST_AND_RETURN_FALSE(
- PayloadSigner::SignatureBlobLength(vector<string>(1, private_key_path),
- &signature_blob_length));
- DeltaDiffGenerator::AddSignatureOp(
- next_blob_offset, signature_blob_length, &manifest);
- }
-
- TEST_AND_RETURN_FALSE(InitializePartitionInfos(config, &manifest));
-
- // Serialize protobuf
- string serialized_manifest;
-
- TEST_AND_RETURN_FALSE(manifest.AppendToString(&serialized_manifest));
-
- LOG(INFO) << "Writing final delta file header...";
- DirectFileWriter writer;
- TEST_AND_RETURN_FALSE_ERRNO(writer.Open(output_path.c_str(),
- O_WRONLY | O_CREAT | O_TRUNC,
- 0644) == 0);
- ScopedFileWriterCloser writer_closer(&writer);
-
- // Write header
- TEST_AND_RETURN_FALSE(writer.Write(kDeltaMagic, strlen(kDeltaMagic)));
-
- // Write major version number
- TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer, kMajorVersionNumber));
-
- // Write protobuf length
- TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer,
- serialized_manifest.size()));
-
- // Write protobuf
- LOG(INFO) << "Writing final delta file protobuf... "
- << serialized_manifest.size();
- TEST_AND_RETURN_FALSE(writer.Write(serialized_manifest.data(),
- serialized_manifest.size()));
-
- // Append the data blobs
- LOG(INFO) << "Writing final delta file data blobs...";
- int blobs_fd = open(ordered_blobs_path.c_str(), O_RDONLY, 0);
- ScopedFdCloser blobs_fd_closer(&blobs_fd);
- TEST_AND_RETURN_FALSE(blobs_fd >= 0);
- for (;;) {
- vector<char> buf(config.block_size);
- ssize_t rc = read(blobs_fd, buf.data(), buf.size());
- if (0 == rc) {
- // EOF
- break;
- }
- TEST_AND_RETURN_FALSE_ERRNO(rc > 0);
- TEST_AND_RETURN_FALSE(writer.Write(buf.data(), rc));
- }
-
- // Write signature blob.
- if (!private_key_path.empty()) {
- LOG(INFO) << "Signing the update...";
- chromeos::Blob signature_blob;
- TEST_AND_RETURN_FALSE(PayloadSigner::SignPayload(
- output_path,
- vector<string>(1, private_key_path),
- &signature_blob));
- TEST_AND_RETURN_FALSE(writer.Write(signature_blob.data(),
- signature_blob.size()));
- }
-
- *metadata_size =
- strlen(kDeltaMagic) + 2 * sizeof(uint64_t) + serialized_manifest.size();
- ReportPayloadUsage(manifest, *metadata_size, op_name_map);
-
LOG(INFO) << "All done. Successfully created delta file with "
<< "metadata size = " << *metadata_size;
return true;
}
-// Runs the bsdiff tool on two files and returns the resulting delta in
-// 'out'. Returns true on success.
-bool DeltaDiffGenerator::BsdiffFiles(const string& old_file,
- const string& new_file,
- chromeos::Blob* out) {
- const string kPatchFile = "delta.patchXXXXXX";
- string patch_file_path;
-
- TEST_AND_RETURN_FALSE(
- utils::MakeTempFile(kPatchFile, &patch_file_path, nullptr));
-
- vector<string> cmd;
- cmd.push_back(kBsdiffPath);
- cmd.push_back(old_file);
- cmd.push_back(new_file);
- cmd.push_back(patch_file_path);
-
- int rc = 1;
- chromeos::Blob patch_file;
- TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, nullptr));
- TEST_AND_RETURN_FALSE(rc == 0);
- TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
- unlink(patch_file_path.c_str());
- return true;
-}
-
-void DeltaDiffGenerator::AddSignatureOp(uint64_t signature_blob_offset,
- uint64_t signature_blob_length,
- DeltaArchiveManifest* manifest) {
- LOG(INFO) << "Making room for signature in file";
- manifest->set_signatures_offset(signature_blob_offset);
- LOG(INFO) << "set? " << manifest->has_signatures_offset();
- // Add a dummy op at the end to appease older clients
- DeltaArchiveManifest_InstallOperation* dummy_op =
- manifest->add_kernel_install_operations();
- dummy_op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
- dummy_op->set_data_offset(signature_blob_offset);
- manifest->set_signatures_offset(signature_blob_offset);
- dummy_op->set_data_length(signature_blob_length);
- manifest->set_signatures_size(signature_blob_length);
- Extent* dummy_extent = dummy_op->add_dst_extents();
- // Tell the dummy op to write this data to a big sparse hole
- dummy_extent->set_start_block(kSparseHole);
- dummy_extent->set_num_blocks((signature_blob_length + kBlockSize - 1) /
- kBlockSize);
-}
-
-bool DeltaDiffGenerator::FragmentOperations(
- vector<AnnotatedOperation>* aops,
- const string& target_part_path,
- int data_fd,
- off_t* data_file_size) {
- vector<AnnotatedOperation> fragmented_aops;
- for (const AnnotatedOperation& aop : *aops) {
- if (aop.op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) {
- TEST_AND_RETURN_FALSE(SplitSourceCopy(aop, &fragmented_aops));
- } else if ((aop.op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_REPLACE) ||
- (aop.op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) {
- TEST_AND_RETURN_FALSE(SplitReplaceOrReplaceBz(aop, &fragmented_aops,
- target_part_path, data_fd,
- data_file_size));
- } else {
- fragmented_aops.push_back(aop);
- }
- }
- *aops = fragmented_aops;
- return true;
-}
-
-void DeltaDiffGenerator::SortOperationsByDestination(
- vector<AnnotatedOperation>* aops) {
- sort(aops->begin(), aops->end(), CompareAopsByDestination);
-}
-
-bool DeltaDiffGenerator::SplitSourceCopy(
- const AnnotatedOperation& original_aop,
- vector<AnnotatedOperation>* result_aops) {
- DeltaArchiveManifest_InstallOperation original_op = original_aop.op;
- TEST_AND_RETURN_FALSE(original_op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
- // Keeps track of the index of curr_src_ext.
- int curr_src_ext_index = 0;
- Extent curr_src_ext = original_op.src_extents(curr_src_ext_index);
- for (int i = 0; i < original_op.dst_extents_size(); i++) {
- Extent dst_ext = original_op.dst_extents(i);
- // The new operation which will have only one dst extent.
- DeltaArchiveManifest_InstallOperation new_op;
- uint64_t blocks_left = dst_ext.num_blocks();
- while (blocks_left > 0) {
- if (curr_src_ext.num_blocks() <= blocks_left) {
- // If the curr_src_ext is smaller than dst_ext, add it.
- blocks_left -= curr_src_ext.num_blocks();
- *(new_op.add_src_extents()) = curr_src_ext;
- if (curr_src_ext_index + 1 < original_op.src_extents().size()) {
- curr_src_ext = original_op.src_extents(++curr_src_ext_index);
- } else {
- break;
- }
- } else {
- // Split src_exts that are bigger than the dst_ext we're dealing with.
- Extent first_ext;
- first_ext.set_num_blocks(blocks_left);
- first_ext.set_start_block(curr_src_ext.start_block());
- *(new_op.add_src_extents()) = first_ext;
- // Keep the second half of the split op.
- curr_src_ext.set_num_blocks(curr_src_ext.num_blocks() - blocks_left);
- curr_src_ext.set_start_block(curr_src_ext.start_block() + blocks_left);
- blocks_left -= first_ext.num_blocks();
- }
- }
- // Fix up our new operation and add it to the results.
- new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
- *(new_op.add_dst_extents()) = dst_ext;
- new_op.set_src_length(dst_ext.num_blocks() * kBlockSize);
- new_op.set_dst_length(dst_ext.num_blocks() * kBlockSize);
-
- AnnotatedOperation new_aop;
- new_aop.op = new_op;
- new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i);
- result_aops->push_back(new_aop);
- }
- if (curr_src_ext_index != original_op.src_extents().size() - 1) {
- LOG(FATAL) << "Incorrectly split SOURCE_COPY operation. Did not use all "
- << "source extents.";
- }
- return true;
-}
-
-bool DeltaDiffGenerator::SplitReplaceOrReplaceBz(
- const AnnotatedOperation& original_aop,
- vector<AnnotatedOperation>* result_aops,
- const string& target_part_path,
- int data_fd,
- off_t* data_file_size) {
- DeltaArchiveManifest_InstallOperation original_op = original_aop.op;
- const bool is_replace =
- original_op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE;
- TEST_AND_RETURN_FALSE(
- is_replace ||
- (original_op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ));
-
- uint32_t data_offset = original_op.data_offset();
- for (int i = 0; i < original_op.dst_extents_size(); i++) {
- Extent dst_ext = original_op.dst_extents(i);
- // Make a new operation with only one dst extent.
- DeltaArchiveManifest_InstallOperation new_op;
- *(new_op.add_dst_extents()) = dst_ext;
- uint32_t data_size = dst_ext.num_blocks() * kBlockSize;
- new_op.set_dst_length(data_size);
- // If this is a REPLACE, attempt to reuse portions of the existing blob.
- if (is_replace) {
- new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
- new_op.set_data_length(data_size);
- new_op.set_data_offset(data_offset);
- data_offset += data_size;
- }
-
- AnnotatedOperation new_aop;
- new_aop.op = new_op;
- new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i);
- TEST_AND_RETURN_FALSE(AddDataAndSetType(&new_aop, target_part_path, data_fd,
- data_file_size));
-
- result_aops->push_back(new_aop);
- }
- return true;
-}
-
-bool DeltaDiffGenerator::MergeOperations(vector<AnnotatedOperation>* aops,
- off_t chunk_size,
- const string& target_part_path,
- int data_fd,
- off_t* data_file_size) {
- vector<AnnotatedOperation> new_aops;
- for (const AnnotatedOperation& curr_aop : *aops) {
- if (new_aops.empty()) {
- new_aops.push_back(curr_aop);
- continue;
- }
- AnnotatedOperation& last_aop = new_aops.back();
-
- if (last_aop.op.dst_extents_size() <= 0 ||
- curr_aop.op.dst_extents_size() <= 0) {
- new_aops.push_back(curr_aop);
- continue;
- }
- uint32_t last_dst_idx = last_aop.op.dst_extents_size() - 1;
- uint32_t last_end_block =
- last_aop.op.dst_extents(last_dst_idx).start_block() +
- last_aop.op.dst_extents(last_dst_idx).num_blocks();
- uint32_t curr_start_block = curr_aop.op.dst_extents(0).start_block();
- uint32_t combined_block_count =
- last_aop.op.dst_extents(last_dst_idx).num_blocks() +
- curr_aop.op.dst_extents(0).num_blocks();
- bool good_op_type =
- curr_aop.op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY ||
- curr_aop.op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
- curr_aop.op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ;
- if (good_op_type &&
- last_aop.op.type() == curr_aop.op.type() &&
- last_end_block == curr_start_block &&
- static_cast<off_t>(combined_block_count * kBlockSize) <= chunk_size) {
- // If the operations have the same type (which is a type that we can
- // merge), are contiguous, are fragmented to have one destination extent,
- // and their combined block count would be less than chunk size, merge
- // them.
- last_aop.name = base::StringPrintf("%s,%s",
- last_aop.name.c_str(),
- curr_aop.name.c_str());
-
- ExtendExtents(last_aop.op.mutable_src_extents(),
- curr_aop.op.src_extents());
- if (curr_aop.op.src_length() > 0)
- last_aop.op.set_src_length(last_aop.op.src_length() +
- curr_aop.op.src_length());
- ExtendExtents(last_aop.op.mutable_dst_extents(),
- curr_aop.op.dst_extents());
- if (curr_aop.op.dst_length() > 0)
- last_aop.op.set_dst_length(last_aop.op.dst_length() +
- curr_aop.op.dst_length());
- // Set the data length to zero so we know to add the blob later.
- if (curr_aop.op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
- curr_aop.op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
- last_aop.op.set_data_length(0);
- }
- } else {
- // Otherwise just include the extent as is.
- new_aops.push_back(curr_aop);
- }
- }
-
- // Set the blobs for REPLACE/REPLACE_BZ operations that have been merged.
- for (AnnotatedOperation& curr_aop : new_aops) {
- if (curr_aop.op.data_length() == 0 &&
- (curr_aop.op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
- curr_aop.op.type() ==
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) {
- TEST_AND_RETURN_FALSE(AddDataAndSetType(&curr_aop, target_part_path,
- data_fd, data_file_size));
- }
- }
-
- *aops = new_aops;
- return true;
-}
-
-void DeltaDiffGenerator::ExtendExtents(
- google::protobuf::RepeatedPtrField<Extent>* extents,
- const google::protobuf::RepeatedPtrField<Extent>& extents_to_add) {
- vector<Extent> extents_vector;
- vector<Extent> extents_to_add_vector;
- ExtentsToVector(*extents, &extents_vector);
- ExtentsToVector(extents_to_add, &extents_to_add_vector);
- extents_vector.insert(extents_vector.end(),
- extents_to_add_vector.begin(),
- extents_to_add_vector.end());
- NormalizeExtents(&extents_vector);
- extents->Clear();
- StoreExtents(extents_vector, extents);
-}
-
-bool DeltaDiffGenerator::AddDataAndSetType(AnnotatedOperation* aop,
- const string& target_part_path,
- int data_fd,
- off_t* data_file_size) {
- TEST_AND_RETURN_FALSE(
- aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
- aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-
- chromeos::Blob data(aop->op.dst_length());
- vector<Extent> dst_extents;
- ExtentsToVector(aop->op.dst_extents(), &dst_extents);
- TEST_AND_RETURN_FALSE(utils::ReadExtents(target_part_path,
- dst_extents,
- &data,
- data.size(),
- kBlockSize));
-
- chromeos::Blob data_bz;
- TEST_AND_RETURN_FALSE(BzipCompress(data, &data_bz));
- CHECK(!data_bz.empty());
-
- chromeos::Blob* data_p = nullptr;
- DeltaArchiveManifest_InstallOperation_Type new_op_type;
- if (data_bz.size() < data.size()) {
- new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ;
- data_p = &data_bz;
- } else {
- new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE;
- data_p = &data;
- }
-
- // If the operation already points to a data blob, check whether it's
- // identical to the new one, in which case don't add it.
- if (aop->op.type() == new_op_type &&
- aop->op.data_length() == data_p->size()) {
- chromeos::Blob current_data(data_p->size());
- ssize_t bytes_read;
- TEST_AND_RETURN_FALSE(utils::PReadAll(data_fd,
- current_data.data(),
- aop->op.data_length(),
- aop->op.data_offset(),
- &bytes_read));
- TEST_AND_RETURN_FALSE(bytes_read ==
- static_cast<ssize_t>(aop->op.data_length()));
- if (current_data == *data_p)
- data_p = nullptr;
- }
-
- if (data_p) {
- aop->op.set_type(new_op_type);
- aop->SetOperationBlob(data_p, data_fd, data_file_size);
- }
-
- return true;
-}
-
}; // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
index b3b5cee..8ba1dc0 100644
--- a/payload_generator/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -5,19 +5,9 @@
#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
#define UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
-#include <set>
#include <string>
-#include <vector>
-#include <base/macros.h>
-#include <chromeos/secure_blob.h>
-
-#include "update_engine/payload_constants.h"
-#include "update_engine/payload_generator/extent_utils.h"
-#include "update_engine/payload_generator/filesystem_interface.h"
-#include "update_engine/payload_generator/operations_generator.h"
#include "update_engine/payload_generator/payload_generation_config.h"
-#include "update_engine/update_metadata.pb.h"
// There is one function in DeltaDiffGenerator of importance to users
// of the class: GenerateDeltaUpdateFile(). Before calling it,
@@ -28,250 +18,9 @@
namespace chromeos_update_engine {
-extern const char* const kEmptyPath;
extern const size_t kBlockSize;
extern const size_t kRootFSPartitionSize;
-class DeltaDiffGenerator : public OperationsGenerator {
- public:
- DeltaDiffGenerator() = default;
-
- // These functions are public so that the unit tests can access them:
-
- // Generate the update payload operations for the kernel and rootfs using
- // SOURCE_* operations, used to generate deltas for the minor version
- // kSourceMinorPayloadVersion. This function will generate operations in the
- // rootfs that will read blocks from the source partition in random order and
- // write the new image on the target partition, also possibly in random order.
- // The rootfs operations are stored in |rootfs_ops| and should be executed in
- // that order. The kernel operations are stored in |kernel_ops|. All
- // the offsets in the operations reference the data written to |data_file_fd|.
- // The total amount of data written to that file is stored in
- // |data_file_size|.
- bool GenerateOperations(
- const PayloadGenerationConfig& config,
- int data_file_fd,
- off_t* data_file_size,
- std::vector<AnnotatedOperation>* rootfs_ops,
- std::vector<AnnotatedOperation>* kernel_ops) override;
-
- // Create operations in |aops| to produce all the files reported by |new_fs|,
- // including all the blocks not reported by any file.
- // It uses the files reported by |old_fs| and the data in |old_part| to
- // determine the best way to compress the new files (REPLACE, REPLACE_BZ,
- // COPY, BSDIFF) and writes any necessary data to the end of data_fd updating
- // data_file_size accordingly.
- static bool DeltaReadFilesystem(std::vector<AnnotatedOperation>* aops,
- const std::string& old_part,
- const std::string& new_part,
- FilesystemInterface* old_fs,
- FilesystemInterface* new_fs,
- off_t chunk_blocks,
- int data_fd,
- off_t* data_file_size,
- bool skip_block_0,
- bool src_ops_allowed);
-
- // 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
- // stored in |new_part| in the blocks described by |new_extents| and, if it
- // exists, the old version exists in |old_part| in the blocks described by
- // |old_extents|. The operations added to |aops| reference the data blob
- // in the file |data_fd|, which has length *data_file_size. *data_file_size is
- // updated appropriately. Returns true on success.
- static bool DeltaReadFile(std::vector<AnnotatedOperation>* aops,
- const std::string& old_part,
- const std::string& new_part,
- const std::vector<Extent>& old_extents,
- const std::vector<Extent>& new_extents,
- const std::string& name,
- off_t chunk_blocks,
- int data_fd,
- off_t* data_file_size,
- bool src_ops_allowed);
-
- // Reads the blocks |old_extents| from |old_part| (if it exists) and the
- // |new_extents| from |new_part| and determines the smallest way to encode
- // this |new_extents| for the diff. It stores necessary data in |out_data| and
- // fills in |out_op|. If there's no change in old and new files, it creates a
- // MOVE operation. If there is a change, the smallest of REPLACE, REPLACE_BZ,
- // or BSDIFF wins. |new_extents| must not be empty.
- // If |src_ops_allowed| is true, it will emit SOURCE_COPY and SOURCE_BSDIFF
- // operations instead of MOVE and BSDIFF, respectively.
- // Returns true on success.
- static bool ReadExtentsToDiff(const std::string& old_part,
- const std::string& new_part,
- const std::vector<Extent>& old_extents,
- const std::vector<Extent>& new_extents,
- bool bsdiff_allowed,
- chromeos::Blob* out_data,
- DeltaArchiveManifest_InstallOperation* out_op,
- bool src_ops_allowed);
-
- // Delta compresses a kernel partition |new_kernel_part| with knowledge of the
- // old kernel partition |old_kernel_part|. If |old_kernel_part| is an empty
- // string, generates a full update of the partition. The size of the old and
- // new kernel is passed in |old_kernel_size| and |new_kernel_size|. The
- // operations used to generate the new kernel are stored in the |aops|
- // vector, and the blob associated to those operations is written at the end
- // of the |blobs_fd| file, adding to the value pointed by |blobs_length| the
- // bytes written to |blobs_fd|.
- static bool DeltaCompressKernelPartition(
- const std::string& old_kernel_part,
- const std::string& new_kernel_part,
- uint64_t old_kernel_size,
- uint64_t new_kernel_size,
- uint64_t block_size,
- std::vector<AnnotatedOperation>* aops,
- int blobs_fd,
- off_t* blobs_length,
- bool src_ops_allowed);
-
- // Stores all Extents in 'extents' into 'out'.
- static void StoreExtents(const std::vector<Extent>& extents,
- google::protobuf::RepeatedPtrField<Extent>* out);
-
- // Stores all extents in |extents| into |out_vector|.
- static void ExtentsToVector(
- const google::protobuf::RepeatedPtrField<Extent>& extents,
- std::vector<Extent>* out_vector);
-
- // Install operations in the manifest may reference data blobs, which
- // are in data_blobs_path. This function creates a new data blobs file
- // with the data blobs in the same order as the referencing install
- // operations in the manifest. E.g. if manifest[0] has a data blob
- // "X" at offset 1, manifest[1] has a data blob "Y" at offset 0,
- // and data_blobs_path's file contains "YX", new_data_blobs_path
- // will set to be a file that contains "XY".
- static bool ReorderDataBlobs(DeltaArchiveManifest* manifest,
- const std::string& data_blobs_path,
- const std::string& new_data_blobs_path);
-
- // Computes a SHA256 hash of the given buf and sets the hash value in the
- // operation so that update_engine could verify. This hash should be set
- // for all operations that have a non-zero data blob. One exception is the
- // dummy operation for signature blob because the contents of the signature
- // blob will not be available at payload creation time. So, update_engine will
- // gracefully ignore the dummy signature operation.
- static bool AddOperationHash(DeltaArchiveManifest_InstallOperation* op,
- const chromeos::Blob& buf);
-
-
- // Returns true if |op| is a no-op operation that doesn't do any useful work
- // (e.g., a move operation that copies blocks onto themselves).
- static bool IsNoopOperation(const DeltaArchiveManifest_InstallOperation& op);
-
- // Filters all the operations that are no-op, maintaining the relative order
- // of the rest of the operations.
- static void FilterNoopOperations(std::vector<AnnotatedOperation>* ops);
-
- static bool InitializePartitionInfo(const PartitionConfig& partition,
- PartitionInfo* info);
-
- // Runs the bsdiff tool on two files and returns the resulting delta in
- // |out|. Returns true on success.
- static bool BsdiffFiles(const std::string& old_file,
- const std::string& new_file,
- chromeos::Blob* out);
-
- // Adds to |manifest| a dummy operation that points to a signature blob
- // located at the specified offset/length.
- static void AddSignatureOp(uint64_t signature_blob_offset,
- uint64_t signature_blob_length,
- DeltaArchiveManifest* manifest);
-
- // Takes a collection (vector or RepeatedPtrField) of Extent and
- // returns a vector of the blocks referenced, in order.
- template<typename T>
- static std::vector<uint64_t> ExpandExtents(const T& extents) {
- std::vector<uint64_t> ret;
- for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) {
- const Extent extent = GetElement(extents, i);
- if (extent.start_block() == kSparseHole) {
- ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
- } else {
- for (uint64_t block = extent.start_block();
- block < (extent.start_block() + extent.num_blocks()); block++) {
- ret.push_back(block);
- }
- }
- }
- return ret;
- }
-
- // Takes a vector of AnnotatedOperations |aops| and fragments those operations
- // such that there is only one dst extent per operation. Sets |aops| to a
- // vector of the new fragmented operations.
- static bool FragmentOperations(std::vector<AnnotatedOperation>* aops,
- const std::string& target_rootfs_part,
- int data_fd,
- off_t* data_file_size);
-
- // Takes a vector of AnnotatedOperations |aops| and sorts them by the first
- // start block in their destination extents. Sets |aops| to a vector of the
- // sorted operations.
- static void SortOperationsByDestination(
- std::vector<AnnotatedOperation>* aops);
-
- // Takes an SOURCE_COPY install operation, |aop|, and adds one operation for
- // each dst extent in |aop| to |ops|. The new operations added to |ops| will
- // have only one dst extent. The src extents are split so the number of blocks
- // in the src and dst extents are equal.
- // E.g. we have a SOURCE_COPY operation:
- // src extents: [(1, 3), (5, 1), (7, 1)], dst extents: [(2, 2), (6, 3)]
- // Then we will get 2 new operations:
- // 1. src extents: [(1, 2)], dst extents: [(2, 2)]
- // 2. src extents: [(3, 1),(5, 1),(7, 1)], dst extents: [(6, 3)]
- static bool SplitSourceCopy(const AnnotatedOperation& original_aop,
- std::vector<AnnotatedOperation>* result_aops);
-
- // Takes a REPLACE/REPLACE_BZ operation |aop|, and adds one operation for each
- // dst extent in |aop| to |ops|. The new operations added to |ops| will have
- // only one dst extent each, and may be either a REPLACE or REPLACE_BZ
- // depending on whether compression is advantageous.
- static bool SplitReplaceOrReplaceBz(
- const AnnotatedOperation& original_aop,
- std::vector<AnnotatedOperation>* result_aops,
- const std::string& target_part,
- int data_fd,
- off_t* data_file_size);
-
- // Takes a sorted (by first destination extent) vector of operations |aops|
- // and merges SOURCE_COPY, REPLACE, and REPLACE_BZ operations in that vector.
- // It will merge two operations if:
- // - They are of the same type.
- // - They are contiguous.
- // - Their combined blocks do not exceed |chunk_size|.
- static bool MergeOperations(std::vector<AnnotatedOperation>* aops,
- off_t chunk_size,
- const std::string& target_part,
- int data_fd,
- off_t* data_file_size);
-
- // Takes a pointer to extents |extents| and extents |extents_to_add|, and
- // merges them by adding |extents_to_add| to |extents| and normalizing.
- static void ExtendExtents(
- google::protobuf::RepeatedPtrField<Extent>* extents,
- const google::protobuf::RepeatedPtrField<Extent>& extents_to_add);
-
- private:
- // Adds the data payload for a REPLACE/REPLACE_BZ operation |aop| by reading
- // its output extents from |target_part_path| and appending a corresponding
- // data blob to |data_fd|. The blob will be compressed if this is smaller than
- // the uncompressed form, and the operation type will be set accordingly.
- // |*data_file_size| will be updated as well. If the operation happens to have
- // the right type and already points to a data blob, we check whether its
- // content is identical to the new one, in which case nothing is written.
- static bool AddDataAndSetType(AnnotatedOperation* aop,
- const std::string& target_part_path,
- int data_fd,
- off_t* data_file_size);
-
- DISALLOW_COPY_AND_ASSIGN(DeltaDiffGenerator);
-};
-
-// This is the only function that external users of this module should call.
// The |config| describes the payload generation request, describing both
// old and new images for delta payloads and only the new image for full
// payloads.
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
deleted file mode 100644
index 187da7a..0000000
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ /dev/null
@@ -1,1076 +0,0 @@
-// Copyright (c) 2012 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/delta_diff_generator.h"
-
-#include <fcntl.h>
-#include <sys/stat.h>
-#include <sys/types.h>
-#include <unistd.h>
-
-#include <algorithm>
-#include <cstdio>
-#include <map>
-#include <set>
-#include <sstream>
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/files/scoped_file.h>
-#include <base/logging.h>
-#include <base/strings/string_util.h>
-#include <bzlib.h>
-#include <chromeos/secure_blob.h>
-#include <gtest/gtest.h>
-
-#include "update_engine/bzip.h"
-#include "update_engine/delta_performer.h"
-#include "update_engine/payload_constants.h"
-#include "update_engine/payload_generator/extent_ranges.h"
-#include "update_engine/payload_generator/extent_utils.h"
-#include "update_engine/payload_generator/fake_filesystem.h"
-#include "update_engine/payload_generator/graph_types.h"
-#include "update_engine/subprocess.h"
-#include "update_engine/test_utils.h"
-#include "update_engine/utils.h"
-
-using std::set;
-using std::string;
-using std::unique_ptr;
-using std::vector;
-
-namespace chromeos_update_engine {
-
-namespace {
-
-// Writes the |data| in the blocks specified by |extents| on the partition
-// |part_path|. The |data| size could be smaller than the size of the blocks
-// passed.
-bool WriteExtents(const string& part_path,
- const vector<Extent>& extents,
- off_t block_size,
- const chromeos::Blob& data) {
- uint64_t offset = 0;
- base::ScopedFILE fp(fopen(part_path.c_str(), "r+"));
- TEST_AND_RETURN_FALSE(fp.get());
-
- for (const Extent& extent : extents) {
- if (offset >= data.size())
- break;
- TEST_AND_RETURN_FALSE(
- fseek(fp.get(), extent.start_block() * block_size, SEEK_SET) == 0);
- uint64_t to_write = std::min(extent.num_blocks() * block_size,
- data.size() - offset);
- TEST_AND_RETURN_FALSE(
- fwrite(data.data() + offset, 1, to_write, fp.get()) == to_write);
- offset += extent.num_blocks() * block_size;
- }
- return true;
-}
-
-bool ExtentEquals(Extent ext, uint64_t start_block, uint64_t num_blocks) {
- return ext.start_block() == start_block && ext.num_blocks() == num_blocks;
-}
-
-// Tests splitting of a REPLACE/REPLACE_BZ operation.
-void TestSplitReplaceOrReplaceBzOperation(
- DeltaArchiveManifest_InstallOperation_Type orig_type,
- bool compressible) {
- const size_t op_ex1_start_block = 2;
- const size_t op_ex1_num_blocks = 2;
- const size_t op_ex2_start_block = 6;
- const size_t op_ex2_num_blocks = 1;
- const size_t part_num_blocks = 7;
-
- // Create the target partition data.
- string part_path;
- EXPECT_TRUE(utils::MakeTempFile(
- "SplitReplaceOrReplaceBzTest_part.XXXXXX", &part_path, nullptr));
- ScopedPathUnlinker part_path_unlinker(part_path);
- const size_t part_size = part_num_blocks * kBlockSize;
- chromeos::Blob part_data;
- if (compressible) {
- part_data.resize(part_size);
- test_utils::FillWithData(&part_data);
- } else {
- std::mt19937 gen(12345);
- std::uniform_int_distribution<uint8_t> dis(0, 255);
- for (uint32_t i = 0; i < part_size; i++)
- part_data.push_back(dis(gen));
- }
- ASSERT_EQ(part_size, part_data.size());
- ASSERT_TRUE(utils::WriteFile(part_path.c_str(), part_data.data(), part_size));
-
- // Create original operation and blob data.
- const size_t op_ex1_offset = op_ex1_start_block * kBlockSize;
- const size_t op_ex1_size = op_ex1_num_blocks * kBlockSize;
- const size_t op_ex2_offset = op_ex2_start_block * kBlockSize;
- const size_t op_ex2_size = op_ex2_num_blocks * kBlockSize;
- DeltaArchiveManifest_InstallOperation op;
- op.set_type(orig_type);
- *(op.add_dst_extents()) = ExtentForRange(op_ex1_start_block,
- op_ex1_num_blocks);
- *(op.add_dst_extents()) = ExtentForRange(op_ex2_start_block,
- op_ex2_num_blocks);
- op.set_dst_length(op_ex1_num_blocks + op_ex2_num_blocks);
-
- chromeos::Blob op_data;
- op_data.insert(op_data.end(),
- part_data.begin() + op_ex1_offset,
- part_data.begin() + op_ex1_offset + op_ex1_size);
- op_data.insert(op_data.end(),
- part_data.begin() + op_ex2_offset,
- part_data.begin() + op_ex2_offset + op_ex2_size);
- chromeos::Blob op_blob;
- if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
- op_blob = op_data;
- } else {
- ASSERT_TRUE(BzipCompress(op_data, &op_blob));
- }
- op.set_data_offset(0);
- op.set_data_length(op_blob.size());
-
- AnnotatedOperation aop;
- aop.op = op;
- aop.name = "SplitTestOp";
-
- // Create the data file.
- string data_path;
- EXPECT_TRUE(utils::MakeTempFile(
- "SplitReplaceOrReplaceBzTest_data.XXXXXX", &data_path, nullptr));
- ScopedPathUnlinker data_path_unlinker(data_path);
- int data_fd = open(data_path.c_str(), O_RDWR, 000);
- EXPECT_GE(data_fd, 0);
- ScopedFdCloser data_fd_closer(&data_fd);
- EXPECT_TRUE(utils::WriteFile(data_path.c_str(), op_blob.data(),
- op_blob.size()));
- off_t data_file_size = op_blob.size();
-
- // Split the operation.
- vector<AnnotatedOperation> result_ops;
- ASSERT_TRUE(DeltaDiffGenerator::SplitReplaceOrReplaceBz(
- aop, &result_ops, part_path, data_fd, &data_file_size));
-
- // Check the result.
- DeltaArchiveManifest_InstallOperation_Type expected_type =
- compressible ?
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ :
- DeltaArchiveManifest_InstallOperation_Type_REPLACE;
-
- ASSERT_EQ(2, result_ops.size());
-
- EXPECT_EQ("SplitTestOp:0", result_ops[0].name);
- DeltaArchiveManifest_InstallOperation first_op = result_ops[0].op;
- EXPECT_EQ(expected_type, first_op.type());
- EXPECT_EQ(op_ex1_size, first_op.dst_length());
- EXPECT_EQ(1, first_op.dst_extents().size());
- EXPECT_TRUE(ExtentEquals(first_op.dst_extents(0), op_ex1_start_block,
- op_ex1_num_blocks));
- // Obtain the expected blob.
- chromeos::Blob first_expected_data(
- part_data.begin() + op_ex1_offset,
- part_data.begin() + op_ex1_offset + op_ex1_size);
- chromeos::Blob first_expected_blob;
- if (compressible) {
- ASSERT_TRUE(BzipCompress(first_expected_data, &first_expected_blob));
- } else {
- first_expected_blob = first_expected_data;
- }
- EXPECT_EQ(first_expected_blob.size(), first_op.data_length());
- // Check that the actual blob matches what's expected.
- chromeos::Blob first_data_blob(first_op.data_length());
- ssize_t bytes_read;
- ASSERT_TRUE(utils::PReadAll(data_fd,
- first_data_blob.data(),
- first_op.data_length(),
- first_op.data_offset(),
- &bytes_read));
- ASSERT_EQ(bytes_read, first_op.data_length());
- EXPECT_EQ(first_expected_blob, first_data_blob);
-
- EXPECT_EQ("SplitTestOp:1", result_ops[1].name);
- DeltaArchiveManifest_InstallOperation second_op = result_ops[1].op;
- EXPECT_EQ(expected_type, second_op.type());
- EXPECT_EQ(op_ex2_size, second_op.dst_length());
- EXPECT_EQ(1, second_op.dst_extents().size());
- EXPECT_TRUE(ExtentEquals(second_op.dst_extents(0), op_ex2_start_block,
- op_ex2_num_blocks));
- // Obtain the expected blob.
- chromeos::Blob second_expected_data(
- part_data.begin() + op_ex2_offset,
- part_data.begin() + op_ex2_offset + op_ex2_size);
- chromeos::Blob second_expected_blob;
- if (compressible) {
- ASSERT_TRUE(BzipCompress(second_expected_data, &second_expected_blob));
- } else {
- second_expected_blob = second_expected_data;
- }
- EXPECT_EQ(second_expected_blob.size(), second_op.data_length());
- // Check that the actual blob matches what's expected.
- chromeos::Blob second_data_blob(second_op.data_length());
- ASSERT_TRUE(utils::PReadAll(data_fd,
- second_data_blob.data(),
- second_op.data_length(),
- second_op.data_offset(),
- &bytes_read));
- ASSERT_EQ(bytes_read, second_op.data_length());
- EXPECT_EQ(second_expected_blob, second_data_blob);
-
- // Check relative layout of data blobs.
- EXPECT_EQ(first_op.data_offset() + first_op.data_length(),
- second_op.data_offset());
- EXPECT_EQ(second_op.data_offset() + second_op.data_length(), data_file_size);
- // If we split a REPLACE into multiple ones, ensure reuse of preexisting blob.
- if (!compressible &&
- orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
- EXPECT_EQ(0, first_op.data_offset());
- }
-}
-
-// Tests merging of REPLACE/REPLACE_BZ operations.
-void TestMergeReplaceOrReplaceBzOperations(
- DeltaArchiveManifest_InstallOperation_Type orig_type,
- bool compressible) {
- const size_t first_op_num_blocks = 1;
- const size_t second_op_num_blocks = 2;
- const size_t total_op_num_blocks = first_op_num_blocks + second_op_num_blocks;
- const size_t part_num_blocks = total_op_num_blocks + 2;
-
- // Create the target partition data.
- string part_path;
- EXPECT_TRUE(utils::MakeTempFile(
- "MergeReplaceOrReplaceBzTest_part.XXXXXX", &part_path, nullptr));
- ScopedPathUnlinker part_path_unlinker(part_path);
- const size_t part_size = part_num_blocks * kBlockSize;
- chromeos::Blob part_data;
- if (compressible) {
- part_data.resize(part_size);
- test_utils::FillWithData(&part_data);
- } else {
- std::mt19937 gen(12345);
- std::uniform_int_distribution<uint8_t> dis(0, 255);
- for (uint32_t i = 0; i < part_size; i++)
- part_data.push_back(dis(gen));
- }
- ASSERT_EQ(part_size, part_data.size());
- ASSERT_TRUE(utils::WriteFile(part_path.c_str(), part_data.data(), part_size));
-
- // Create original operations and blob data.
- vector<AnnotatedOperation> aops;
- chromeos::Blob blob_data;
- const size_t total_op_size = total_op_num_blocks * kBlockSize;
-
- DeltaArchiveManifest_InstallOperation first_op;
- first_op.set_type(orig_type);
- const size_t first_op_size = first_op_num_blocks * kBlockSize;
- first_op.set_dst_length(first_op_size);
- *(first_op.add_dst_extents()) = ExtentForRange(0, first_op_num_blocks);
- chromeos::Blob first_op_data(part_data.begin(),
- part_data.begin() + first_op_size);
- chromeos::Blob first_op_blob;
- if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
- first_op_blob = first_op_data;
- } else {
- ASSERT_TRUE(BzipCompress(first_op_data, &first_op_blob));
- }
- first_op.set_data_offset(0);
- first_op.set_data_length(first_op_blob.size());
- blob_data.insert(blob_data.end(), first_op_blob.begin(), first_op_blob.end());
- AnnotatedOperation first_aop;
- first_aop.op = first_op;
- first_aop.name = "first";
- aops.push_back(first_aop);
-
- DeltaArchiveManifest_InstallOperation second_op;
- second_op.set_type(orig_type);
- const size_t second_op_size = second_op_num_blocks * kBlockSize;
- second_op.set_dst_length(second_op_size);
- *(second_op.add_dst_extents()) = ExtentForRange(first_op_num_blocks,
- second_op_num_blocks);
- chromeos::Blob second_op_data(part_data.begin() + first_op_size,
- part_data.begin() + total_op_size);
- chromeos::Blob second_op_blob;
- if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
- second_op_blob = second_op_data;
- } else {
- ASSERT_TRUE(BzipCompress(second_op_data, &second_op_blob));
- }
- second_op.set_data_offset(first_op_blob.size());
- second_op.set_data_length(second_op_blob.size());
- blob_data.insert(blob_data.end(), second_op_blob.begin(),
- second_op_blob.end());
- AnnotatedOperation second_aop;
- second_aop.op = second_op;
- second_aop.name = "second";
- aops.push_back(second_aop);
-
- // Create the data file.
- string data_path;
- EXPECT_TRUE(utils::MakeTempFile(
- "MergeReplaceOrReplaceBzTest_data.XXXXXX", &data_path, nullptr));
- ScopedPathUnlinker data_path_unlinker(data_path);
- int data_fd = open(data_path.c_str(), O_RDWR, 000);
- EXPECT_GE(data_fd, 0);
- ScopedFdCloser data_fd_closer(&data_fd);
- EXPECT_TRUE(utils::WriteFile(data_path.c_str(), blob_data.data(),
- blob_data.size()));
- off_t data_file_size = blob_data.size();
-
- // Merge the operations.
- EXPECT_TRUE(DeltaDiffGenerator::MergeOperations(
- &aops, 5 * kBlockSize, part_path, data_fd, &data_file_size));
-
- // Check the result.
- DeltaArchiveManifest_InstallOperation_Type expected_op_type =
- compressible ?
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ :
- DeltaArchiveManifest_InstallOperation_Type_REPLACE;
- EXPECT_EQ(1, aops.size());
- DeltaArchiveManifest_InstallOperation new_op = aops[0].op;
- EXPECT_EQ(expected_op_type, new_op.type());
- EXPECT_FALSE(new_op.has_src_length());
- EXPECT_EQ(total_op_num_blocks * kBlockSize, new_op.dst_length());
- EXPECT_EQ(1, new_op.dst_extents().size());
- EXPECT_TRUE(ExtentEquals(new_op.dst_extents(0), 0, total_op_num_blocks));
- EXPECT_EQ("first,second", aops[0].name);
-
- // Check to see if the blob pointed to in the new extent has what we expect.
- chromeos::Blob expected_data(part_data.begin(),
- part_data.begin() + total_op_size);
- chromeos::Blob expected_blob;
- if (compressible) {
- ASSERT_TRUE(BzipCompress(expected_data, &expected_blob));
- } else {
- expected_blob = expected_data;
- }
- ASSERT_EQ(expected_blob.size(), new_op.data_length());
- ASSERT_EQ(blob_data.size() + expected_blob.size(), data_file_size);
- chromeos::Blob new_op_blob(new_op.data_length());
- ssize_t bytes_read;
- ASSERT_TRUE(utils::PReadAll(data_fd,
- new_op_blob.data(),
- new_op.data_length(),
- new_op.data_offset(),
- &bytes_read));
- ASSERT_EQ(new_op.data_length(), bytes_read);
- EXPECT_EQ(expected_blob, new_op_blob);
-}
-
-} // namespace
-
-class DeltaDiffGeneratorTest : public ::testing::Test {
- protected:
- const uint64_t kFilesystemSize = kBlockSize * 1024;
-
- void SetUp() override {
- old_part_path_ = "DeltaDiffGeneratorTest-old_part_path-XXXXXX";
- CreateFilesystem(&old_fs_, &old_part_path_, kFilesystemSize);
-
- new_part_path_ = "DeltaDiffGeneratorTest-new_part_path-XXXXXX";
- CreateFilesystem(&old_fs_, &new_part_path_, kFilesystemSize);
- }
-
- void TearDown() override {
- unlink(old_part_path_.c_str());
- unlink(new_part_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));
- }
-
- // Paths to old and new temporary filesystems used in the tests.
- string old_part_path_;
- string new_part_path_;
-
- // FilesystemInterface fake implementations used to mock out the file/block
- // distribution.
- unique_ptr<FakeFilesystem> old_fs_;
- unique_ptr<FakeFilesystem> new_fs_;
-};
-
-TEST_F(DeltaDiffGeneratorTest, MoveSmallTest) {
- chromeos::Blob data_blob(kBlockSize);
- 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));
-
- chromeos::Blob data;
- DeltaArchiveManifest_InstallOperation op;
- EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
- old_extents,
- new_extents,
- true, // bsdiff_allowed
- &data,
- &op,
- false)); // src_ops_allowed
- EXPECT_TRUE(data.empty());
-
- EXPECT_TRUE(op.has_type());
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
- EXPECT_FALSE(op.has_data_offset());
- EXPECT_FALSE(op.has_data_length());
- EXPECT_EQ(1, op.src_extents_size());
- EXPECT_EQ(kBlockSize, op.src_length());
- EXPECT_EQ(1, op.dst_extents_size());
- EXPECT_EQ(kBlockSize, op.dst_length());
- EXPECT_EQ(BlocksInExtents(op.src_extents()),
- BlocksInExtents(op.dst_extents()));
- EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
-}
-
-TEST_F(DeltaDiffGeneratorTest, MoveWithSameBlock) {
- // Setup the old/new files so that it has immobile chunks; we make sure to
- // utilize all sub-cases of such chunks: blocks 21--22 induce a split (src)
- // and complete removal (dst), whereas blocks 24--25 induce trimming of the
- // tail (src) and head (dst) of extents. The final block (29) is used for
- // ensuring we properly account for the number of bytes removed in cases where
- // the last block is partly filled. The detailed configuration:
- //
- // Old: [ 20 21 22 23 24 25 ] [ 28 29 ]
- // New: [ 18 ] [ 21 22 ] [ 20 ] [ 24 25 26 ] [ 29 ]
- // Same: ^^ ^^ ^^ ^^ ^^
- vector<Extent> old_extents = {
- ExtentForRange(20, 6),
- ExtentForRange(28, 2) };
- vector<Extent> new_extents = {
- ExtentForRange(18, 1),
- ExtentForRange(21, 2),
- ExtentForRange(20, 1),
- ExtentForRange(24, 3),
- ExtentForRange(29, 1) };
-
- uint64_t num_blocks = BlocksInExtents(old_extents);
- EXPECT_EQ(num_blocks, BlocksInExtents(new_extents));
-
- // The size of the data should match the total number of blocks. Each block
- // has a different content.
- chromeos::Blob file_data;
- for (uint64_t i = 0; i < num_blocks; ++i) {
- 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));
-
- chromeos::Blob data;
- DeltaArchiveManifest_InstallOperation op;
- EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
- old_extents,
- new_extents,
- true, // bsdiff_allowed
- &data,
- &op,
- false)); // src_ops_allowed
-
- EXPECT_TRUE(data.empty());
-
- EXPECT_TRUE(op.has_type());
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
- EXPECT_FALSE(op.has_data_offset());
- EXPECT_FALSE(op.has_data_length());
-
- // The expected old and new extents that actually moved. See comment above.
- old_extents = {
- ExtentForRange(20, 1),
- ExtentForRange(23, 1),
- ExtentForRange(28, 1) };
- new_extents = {
- ExtentForRange(18, 1),
- ExtentForRange(20, 1),
- ExtentForRange(26, 1) };
- num_blocks = BlocksInExtents(old_extents);
-
- EXPECT_EQ(num_blocks * kBlockSize, op.src_length());
- EXPECT_EQ(num_blocks * kBlockSize, op.dst_length());
-
- EXPECT_EQ(old_extents.size(), op.src_extents_size());
- for (int i = 0; i < op.src_extents_size(); i++) {
- EXPECT_EQ(old_extents[i].start_block(), op.src_extents(i).start_block())
- << "i == " << i;
- EXPECT_EQ(old_extents[i].num_blocks(), op.src_extents(i).num_blocks())
- << "i == " << i;
- }
-
- EXPECT_EQ(new_extents.size(), op.dst_extents_size());
- for (int i = 0; i < op.dst_extents_size(); i++) {
- EXPECT_EQ(new_extents[i].start_block(), op.dst_extents(i).start_block())
- << "i == " << i;
- EXPECT_EQ(new_extents[i].num_blocks(), op.dst_extents(i).num_blocks())
- << "i == " << i;
- }
-}
-
-TEST_F(DeltaDiffGeneratorTest, BsdiffSmallTest) {
- // Test a BSDIFF operation from block 1 to block 2.
- chromeos::Blob data_blob(kBlockSize);
- test_utils::FillWithData(&data_blob);
-
- // The old file is on a different block than the new one.
- 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));
- // Modify one byte in the new file.
- data_blob[0]++;
- EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
-
- chromeos::Blob data;
- DeltaArchiveManifest_InstallOperation op;
- EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
- old_extents,
- new_extents,
- true, // bsdiff_allowed
- &data,
- &op,
- false)); // src_ops_allowed
-
- EXPECT_FALSE(data.empty());
-
- EXPECT_TRUE(op.has_type());
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
- EXPECT_FALSE(op.has_data_offset());
- EXPECT_FALSE(op.has_data_length());
- EXPECT_EQ(1, op.src_extents_size());
- EXPECT_EQ(kBlockSize, op.src_length());
- EXPECT_EQ(1, op.dst_extents_size());
- EXPECT_EQ(kBlockSize, op.dst_length());
- EXPECT_EQ(BlocksInExtents(op.src_extents()),
- BlocksInExtents(op.dst_extents()));
- EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
-}
-
-TEST_F(DeltaDiffGeneratorTest, BsdiffNotAllowedTest) {
- // Same setup as the previous test, but this time BSDIFF operations are not
- // allowed.
- chromeos::Blob data_blob(kBlockSize);
- test_utils::FillWithData(&data_blob);
-
- // The old file is on a different block than the new one.
- 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));
- // Modify one byte in the new file.
- data_blob[0]++;
- EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
-
- chromeos::Blob data;
- DeltaArchiveManifest_InstallOperation op;
- EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
- old_extents,
- new_extents,
- false, // bsdiff_allowed
- &data,
- &op,
- false)); // src_ops_allowed
-
- EXPECT_FALSE(data.empty());
-
- // The point of this test is that we don't use BSDIFF the way the above
- // did. The rest of the details are to be caught in other tests.
- EXPECT_TRUE(op.has_type());
- EXPECT_NE(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
-}
-
-TEST_F(DeltaDiffGeneratorTest, BsdiffNotAllowedMoveTest) {
- chromeos::Blob data_blob(kBlockSize);
- test_utils::FillWithData(&data_blob);
-
- // The old file is on a different block than the new one.
- 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));
-
- chromeos::Blob data;
- DeltaArchiveManifest_InstallOperation op;
- EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
- old_extents,
- new_extents,
- false, // bsdiff_allowed
- &data,
- &op,
- false)); // src_ops_allowed
-
- EXPECT_TRUE(data.empty());
-
- // The point of this test is that we can still use a MOVE for a file
- // that is blacklisted.
- EXPECT_TRUE(op.has_type());
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
-}
-
-TEST_F(DeltaDiffGeneratorTest, ReplaceSmallTest) {
- // The old file is on a different block than the new one.
- vector<Extent> old_extents = { ExtentForRange(1, 1) };
- vector<Extent> new_extents = { ExtentForRange(2, 1) };
-
- // Make a blob that's just 1's that will compress well.
- chromeos::Blob ones(kBlockSize, 1);
-
- // Make a blob with random data that won't compress well.
- chromeos::Blob random_data;
- std::mt19937 gen(12345);
- std::uniform_int_distribution<uint8_t> dis(0, 255);
- for (uint32_t i = 0; i < kBlockSize; i++) {
- random_data.push_back(dis(gen));
- }
-
- 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,
- data_to_test));
-
- chromeos::Blob data;
- DeltaArchiveManifest_InstallOperation op;
- EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
- old_extents,
- new_extents,
- true, // bsdiff_allowed
- &data,
- &op,
- false)); // src_ops_allowed
- EXPECT_FALSE(data.empty());
-
- EXPECT_TRUE(op.has_type());
- const DeltaArchiveManifest_InstallOperation_Type expected_type =
- (i == 0 ? DeltaArchiveManifest_InstallOperation_Type_REPLACE :
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
- EXPECT_EQ(expected_type, op.type());
- EXPECT_FALSE(op.has_data_offset());
- EXPECT_FALSE(op.has_data_length());
- EXPECT_EQ(0, op.src_extents_size());
- EXPECT_FALSE(op.has_src_length());
- EXPECT_EQ(1, op.dst_extents_size());
- EXPECT_EQ(data_to_test.size(), op.dst_length());
- EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
- }
-}
-
-TEST_F(DeltaDiffGeneratorTest, SourceCopyTest) {
- // Makes sure SOURCE_COPY operations are emitted whenever src_ops_allowed
- // is true. It is the same setup as MoveSmallTest, which checks that
- // the operation is well-formed.
- chromeos::Blob data_blob(kBlockSize);
- 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));
-
- chromeos::Blob data;
- DeltaArchiveManifest_InstallOperation op;
- EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
- old_extents,
- new_extents,
- true, // bsdiff_allowed
- &data,
- &op,
- true)); // src_ops_allowed
- EXPECT_TRUE(data.empty());
-
- EXPECT_TRUE(op.has_type());
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY, op.type());
-}
-
-TEST_F(DeltaDiffGeneratorTest, SourceBsdiffTest) {
- // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
- // is true. It is the same setup as BsdiffSmallTest, which checks
- // that the operation is well-formed.
- chromeos::Blob data_blob(kBlockSize);
- test_utils::FillWithData(&data_blob);
-
- // The old file is on a different block than the new one.
- 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));
- // Modify one byte in the new file.
- data_blob[0]++;
- EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
-
- chromeos::Blob data;
- DeltaArchiveManifest_InstallOperation op;
- EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
- old_part_path_,
- new_part_path_,
- old_extents,
- new_extents,
- true, // bsdiff_allowed
- &data,
- &op,
- true)); // src_ops_allowed
-
- EXPECT_FALSE(data.empty());
- EXPECT_TRUE(op.has_type());
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF,
- op.type());
-}
-
-TEST_F(DeltaDiffGeneratorTest, ReorderBlobsTest) {
- string orig_blobs;
- EXPECT_TRUE(utils::MakeTempFile("ReorderBlobsTest.orig.XXXXXX", &orig_blobs,
- nullptr));
- ScopedPathUnlinker orig_blobs_unlinker(orig_blobs);
-
- string orig_data = "abcd";
- EXPECT_TRUE(
- utils::WriteFile(orig_blobs.c_str(), orig_data.data(), orig_data.size()));
-
- string new_blobs;
- EXPECT_TRUE(
- utils::MakeTempFile("ReorderBlobsTest.new.XXXXXX", &new_blobs, nullptr));
- ScopedPathUnlinker new_blobs_unlinker(new_blobs);
-
- DeltaArchiveManifest manifest;
- DeltaArchiveManifest_InstallOperation* op =
- manifest.add_install_operations();
- op->set_data_offset(1);
- op->set_data_length(3);
- op = manifest.add_install_operations();
- op->set_data_offset(0);
- op->set_data_length(1);
-
- EXPECT_TRUE(DeltaDiffGenerator::ReorderDataBlobs(&manifest,
- orig_blobs,
- new_blobs));
-
- string new_data;
- EXPECT_TRUE(utils::ReadFile(new_blobs, &new_data));
- EXPECT_EQ("bcda", new_data);
- EXPECT_EQ(2, manifest.install_operations_size());
- EXPECT_EQ(0, manifest.install_operations(0).data_offset());
- EXPECT_EQ(3, manifest.install_operations(0).data_length());
- EXPECT_EQ(3, manifest.install_operations(1).data_offset());
- EXPECT_EQ(1, manifest.install_operations(1).data_length());
-}
-
-TEST_F(DeltaDiffGeneratorTest, IsNoopOperationTest) {
- DeltaArchiveManifest_InstallOperation op;
- op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
- EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
- op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
- EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
- *(op.add_src_extents()) = ExtentForRange(3, 2);
- *(op.add_dst_extents()) = ExtentForRange(3, 2);
- EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
- *(op.add_src_extents()) = ExtentForRange(7, 5);
- *(op.add_dst_extents()) = ExtentForRange(7, 5);
- EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
- *(op.add_src_extents()) = ExtentForRange(20, 2);
- *(op.add_dst_extents()) = ExtentForRange(20, 1);
- *(op.add_dst_extents()) = ExtentForRange(21, 1);
- EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
- *(op.add_src_extents()) = ExtentForRange(24, 1);
- *(op.add_dst_extents()) = ExtentForRange(25, 1);
- EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
-}
-
-TEST_F(DeltaDiffGeneratorTest, FilterNoopOperations) {
- AnnotatedOperation aop1;
- aop1.op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
- *(aop1.op.add_dst_extents()) = ExtentForRange(3, 2);
- aop1.name = "aop1";
-
- AnnotatedOperation aop2 = aop1;
- aop2.name = "aop2";
-
- AnnotatedOperation noop;
- noop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
- *(noop.op.add_src_extents()) = ExtentForRange(3, 2);
- *(noop.op.add_dst_extents()) = ExtentForRange(3, 2);
- noop.name = "noop";
-
- vector<AnnotatedOperation> ops = {noop, aop1, noop, noop, aop2, noop};
- DeltaDiffGenerator::FilterNoopOperations(&ops);
- EXPECT_EQ(2u, ops.size());
- EXPECT_EQ("aop1", ops[0].name);
- EXPECT_EQ("aop2", ops[1].name);
-}
-
-TEST_F(DeltaDiffGeneratorTest, SplitSourceCopyTest) {
- DeltaArchiveManifest_InstallOperation op;
- op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
- *(op.add_src_extents()) = ExtentForRange(2, 3);
- *(op.add_src_extents()) = ExtentForRange(6, 1);
- *(op.add_src_extents()) = ExtentForRange(8, 4);
- *(op.add_dst_extents()) = ExtentForRange(10, 2);
- *(op.add_dst_extents()) = ExtentForRange(14, 3);
- *(op.add_dst_extents()) = ExtentForRange(18, 3);
-
- AnnotatedOperation aop;
- aop.op = op;
- aop.name = "SplitSourceCopyTestOp";
- vector<AnnotatedOperation> result_ops;
- EXPECT_TRUE(DeltaDiffGenerator::SplitSourceCopy(aop, &result_ops));
- EXPECT_EQ(result_ops.size(), 3);
-
- EXPECT_EQ("SplitSourceCopyTestOp:0", result_ops[0].name);
- DeltaArchiveManifest_InstallOperation first_op = result_ops[0].op;
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
- first_op.type());
- EXPECT_EQ(kBlockSize * 2, first_op.src_length());
- EXPECT_EQ(1, first_op.src_extents().size());
- EXPECT_EQ(2, first_op.src_extents(0).start_block());
- EXPECT_EQ(2, first_op.src_extents(0).num_blocks());
- EXPECT_EQ(kBlockSize * 2, first_op.dst_length());
- EXPECT_EQ(1, first_op.dst_extents().size());
- EXPECT_EQ(10, first_op.dst_extents(0).start_block());
- EXPECT_EQ(2, first_op.dst_extents(0).num_blocks());
-
- EXPECT_EQ("SplitSourceCopyTestOp:1", result_ops[1].name);
- DeltaArchiveManifest_InstallOperation second_op = result_ops[1].op;
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
- second_op.type());
- EXPECT_EQ(kBlockSize * 3, second_op.src_length());
- EXPECT_EQ(3, second_op.src_extents().size());
- EXPECT_EQ(4, second_op.src_extents(0).start_block());
- EXPECT_EQ(1, second_op.src_extents(0).num_blocks());
- EXPECT_EQ(6, second_op.src_extents(1).start_block());
- EXPECT_EQ(1, second_op.src_extents(1).num_blocks());
- EXPECT_EQ(8, second_op.src_extents(2).start_block());
- EXPECT_EQ(1, second_op.src_extents(2).num_blocks());
- EXPECT_EQ(kBlockSize * 3, second_op.dst_length());
- EXPECT_EQ(1, second_op.dst_extents().size());
- EXPECT_EQ(14, second_op.dst_extents(0).start_block());
- EXPECT_EQ(3, second_op.dst_extents(0).num_blocks());
-
- EXPECT_EQ("SplitSourceCopyTestOp:2", result_ops[2].name);
- DeltaArchiveManifest_InstallOperation third_op = result_ops[2].op;
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
- third_op.type());
- EXPECT_EQ(kBlockSize * 3, third_op.src_length());
- EXPECT_EQ(1, third_op.src_extents().size());
- EXPECT_EQ(9, third_op.src_extents(0).start_block());
- EXPECT_EQ(3, third_op.src_extents(0).num_blocks());
- EXPECT_EQ(kBlockSize * 3, third_op.dst_length());
- EXPECT_EQ(1, third_op.dst_extents().size());
- EXPECT_EQ(18, third_op.dst_extents(0).start_block());
- EXPECT_EQ(3, third_op.dst_extents(0).num_blocks());
-}
-
-TEST_F(DeltaDiffGeneratorTest, SplitReplaceTest) {
- TestSplitReplaceOrReplaceBzOperation(
- DeltaArchiveManifest_InstallOperation_Type_REPLACE, false);
-}
-
-TEST_F(DeltaDiffGeneratorTest, SplitReplaceIntoReplaceBzTest) {
- TestSplitReplaceOrReplaceBzOperation(
- DeltaArchiveManifest_InstallOperation_Type_REPLACE, true);
-}
-
-TEST_F(DeltaDiffGeneratorTest, SplitReplaceBzTest) {
- TestSplitReplaceOrReplaceBzOperation(
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, true);
-}
-
-TEST_F(DeltaDiffGeneratorTest, SplitReplaceBzIntoReplaceTest) {
- TestSplitReplaceOrReplaceBzOperation(
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, false);
-}
-
-TEST_F(DeltaDiffGeneratorTest, SortOperationsByDestinationTest) {
- vector<AnnotatedOperation> aops;
- // One operation with multiple destination extents.
- DeltaArchiveManifest_InstallOperation first_op;
- *(first_op.add_dst_extents()) = ExtentForRange(6, 1);
- *(first_op.add_dst_extents()) = ExtentForRange(10, 2);
- AnnotatedOperation first_aop;
- first_aop.op = first_op;
- first_aop.name = "first";
- aops.push_back(first_aop);
-
- // One with no destination extent. Should end up at the end of the vector.
- DeltaArchiveManifest_InstallOperation second_op;
- AnnotatedOperation second_aop;
- second_aop.op = second_op;
- second_aop.name = "second";
- aops.push_back(second_aop);
-
- // One with one destination extent.
- DeltaArchiveManifest_InstallOperation third_op;
- *(third_op.add_dst_extents()) = ExtentForRange(3, 2);
- AnnotatedOperation third_aop;
- third_aop.op = third_op;
- third_aop.name = "third";
- aops.push_back(third_aop);
-
- DeltaDiffGenerator::SortOperationsByDestination(&aops);
- EXPECT_EQ(aops.size(), 3);
- EXPECT_EQ(third_aop.name, aops[0].name);
- EXPECT_EQ(first_aop.name, aops[1].name);
- EXPECT_EQ(second_aop.name, aops[2].name);
-}
-
-TEST_F(DeltaDiffGeneratorTest, MergeSourceCopyOperationsTest) {
- vector<AnnotatedOperation> aops;
- DeltaArchiveManifest_InstallOperation first_op;
- first_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
- first_op.set_src_length(kBlockSize);
- first_op.set_dst_length(kBlockSize);
- *(first_op.add_src_extents()) = ExtentForRange(1, 1);
- *(first_op.add_dst_extents()) = ExtentForRange(6, 1);
- AnnotatedOperation first_aop;
- first_aop.op = first_op;
- first_aop.name = "1";
- aops.push_back(first_aop);
-
- DeltaArchiveManifest_InstallOperation second_op;
- second_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
- second_op.set_src_length(3 * kBlockSize);
- second_op.set_dst_length(3 * kBlockSize);
- *(second_op.add_src_extents()) = ExtentForRange(2, 2);
- *(second_op.add_src_extents()) = ExtentForRange(8, 2);
- *(second_op.add_dst_extents()) = ExtentForRange(7, 3);
- *(second_op.add_dst_extents()) = ExtentForRange(11, 1);
- AnnotatedOperation second_aop;
- second_aop.op = second_op;
- second_aop.name = "2";
- aops.push_back(second_aop);
-
- DeltaArchiveManifest_InstallOperation third_op;
- third_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
- third_op.set_src_length(kBlockSize);
- third_op.set_dst_length(kBlockSize);
- *(third_op.add_src_extents()) = ExtentForRange(11, 1);
- *(third_op.add_dst_extents()) = ExtentForRange(12, 1);
- AnnotatedOperation third_aop;
- third_aop.op = third_op;
- third_aop.name = "3";
- aops.push_back(third_aop);
-
- EXPECT_TRUE(DeltaDiffGenerator::MergeOperations(
- &aops, 5 * kBlockSize, "", 0, nullptr));
-
- EXPECT_EQ(aops.size(), 1);
- DeltaArchiveManifest_InstallOperation first_result_op = aops[0].op;
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
- first_result_op.type());
- EXPECT_EQ(kBlockSize * 5, first_result_op.src_length());
- EXPECT_EQ(3, first_result_op.src_extents().size());
- EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(0), 1, 3));
- EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(1), 8, 2));
- EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(2), 11, 1));
- EXPECT_EQ(kBlockSize * 5, first_result_op.dst_length());
- EXPECT_EQ(2, first_result_op.dst_extents().size());
- EXPECT_TRUE(ExtentEquals(first_result_op.dst_extents(0), 6, 4));
- EXPECT_TRUE(ExtentEquals(first_result_op.dst_extents(1), 11, 2));
- EXPECT_EQ(aops[0].name, "1,2,3");
-}
-
-TEST_F(DeltaDiffGeneratorTest, MergeReplaceOperationsTest) {
- TestMergeReplaceOrReplaceBzOperations(
- DeltaArchiveManifest_InstallOperation_Type_REPLACE, false);
-}
-
-TEST_F(DeltaDiffGeneratorTest, MergeReplaceOperationsToReplaceBzTest) {
- TestMergeReplaceOrReplaceBzOperations(
- DeltaArchiveManifest_InstallOperation_Type_REPLACE, true);
-}
-
-TEST_F(DeltaDiffGeneratorTest, MergeReplaceBzOperationsTest) {
- TestMergeReplaceOrReplaceBzOperations(
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, true);
-}
-
-TEST_F(DeltaDiffGeneratorTest, MergeReplaceBzOperationsToReplaceTest) {
- TestMergeReplaceOrReplaceBzOperations(
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, false);
-}
-
-TEST_F(DeltaDiffGeneratorTest, NoMergeOperationsTest) {
- // Test to make sure we don't merge operations that shouldn't be merged.
- vector<AnnotatedOperation> aops;
- DeltaArchiveManifest_InstallOperation first_op;
- first_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
- *(first_op.add_dst_extents()) = ExtentForRange(0, 1);
- first_op.set_data_length(kBlockSize);
- AnnotatedOperation first_aop;
- first_aop.op = first_op;
- aops.push_back(first_aop);
-
- // Should merge with first, except op types don't match...
- DeltaArchiveManifest_InstallOperation second_op;
- second_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
- *(second_op.add_dst_extents()) = ExtentForRange(1, 2);
- second_op.set_data_length(2 * kBlockSize);
- AnnotatedOperation second_aop;
- second_aop.op = second_op;
- aops.push_back(second_aop);
-
- // Should merge with second, except it would exceed chunk size...
- DeltaArchiveManifest_InstallOperation third_op;
- third_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
- *(third_op.add_dst_extents()) = ExtentForRange(3, 3);
- third_op.set_data_length(3 * kBlockSize);
- AnnotatedOperation third_aop;
- third_aop.op = third_op;
- aops.push_back(third_aop);
-
- // Should merge with third, except they aren't contiguous...
- DeltaArchiveManifest_InstallOperation fourth_op;
- fourth_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
- *(fourth_op.add_dst_extents()) = ExtentForRange(7, 2);
- fourth_op.set_data_length(2 * kBlockSize);
- AnnotatedOperation fourth_aop;
- fourth_aop.op = fourth_op;
- aops.push_back(fourth_aop);
-
- EXPECT_TRUE(DeltaDiffGenerator::MergeOperations(&aops, 4 * kBlockSize,
- "", 0, nullptr));
-
- // No operations were merged, the number of ops is the same.
- EXPECT_EQ(aops.size(), 4);
-}
-
-TEST_F(DeltaDiffGeneratorTest, ExtendExtentsTest) {
- DeltaArchiveManifest_InstallOperation first_op;
- *(first_op.add_src_extents()) = ExtentForRange(1, 1);
- *(first_op.add_src_extents()) = ExtentForRange(3, 1);
-
- DeltaArchiveManifest_InstallOperation second_op;
- *(second_op.add_src_extents()) = ExtentForRange(4, 2);
- *(second_op.add_src_extents()) = ExtentForRange(8, 2);
-
- DeltaDiffGenerator::ExtendExtents(first_op.mutable_src_extents(),
- second_op.src_extents());
- EXPECT_EQ(first_op.src_extents_size(), 3);
- EXPECT_TRUE(ExtentEquals(first_op.src_extents(0), 1, 1));
- EXPECT_TRUE(ExtentEquals(first_op.src_extents(1), 3, 3));
- EXPECT_TRUE(ExtentEquals(first_op.src_extents(2), 8, 2));
-}
-
-} // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
new file mode 100644
index 0000000..d53c5e0
--- /dev/null
+++ b/payload_generator/delta_diff_utils.cc
@@ -0,0 +1,556 @@
+// 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/delta_diff_utils.h"
+
+#include <algorithm>
+#include <map>
+
+#include <base/files/file_util.h>
+#include <base/format_macros.h>
+#include <base/strings/stringprintf.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/omaha_hash_calculator.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"
+#include "update_engine/payload_generator/raw_filesystem.h"
+#include "update_engine/subprocess.h"
+#include "update_engine/utils.h"
+
+using std::map;
+using std::string;
+using std::unique_ptr;
+using std::vector;
+
+namespace chromeos_update_engine {
+namespace {
+
+const char* const kBsdiffPath = "bsdiff";
+
+// The maximum destination size allowed for bsdiff. In general, bsdiff should
+// work for arbitrary big files, but the payload generation and payload
+// application requires a significant amount of RAM. We put a hard-limit of
+// 200 MiB that should not affect any released board, but will limit the
+// Chrome binary in ASan builders.
+const uint64_t kMaxBsdiffDestinationSize = 200 * 1024 * 1024; // bytes
+
+// Process a range of blocks from |range_start| to |range_end| in the extent at
+// position |*idx_p| of |extents|. If |do_remove| is true, this range will be
+// removed, which may cause the extent to be trimmed, split or removed entirely.
+// The value of |*idx_p| is updated to point to the next extent to be processed.
+// Returns true iff the next extent to process is a new or updated one.
+bool ProcessExtentBlockRange(vector<Extent>* extents, size_t* idx_p,
+ const bool do_remove, uint64_t range_start,
+ uint64_t range_end) {
+ size_t idx = *idx_p;
+ uint64_t start_block = (*extents)[idx].start_block();
+ uint64_t num_blocks = (*extents)[idx].num_blocks();
+ uint64_t range_size = range_end - range_start;
+
+ if (do_remove) {
+ if (range_size == num_blocks) {
+ // Remove the entire extent.
+ extents->erase(extents->begin() + idx);
+ } else if (range_end == num_blocks) {
+ // Trim the end of the extent.
+ (*extents)[idx].set_num_blocks(num_blocks - range_size);
+ idx++;
+ } else if (range_start == 0) {
+ // Trim the head of the extent.
+ (*extents)[idx].set_start_block(start_block + range_size);
+ (*extents)[idx].set_num_blocks(num_blocks - range_size);
+ } else {
+ // Trim the middle, splitting the remainder into two parts.
+ (*extents)[idx].set_num_blocks(range_start);
+ Extent e;
+ e.set_start_block(start_block + range_end);
+ e.set_num_blocks(num_blocks - range_end);
+ idx++;
+ extents->insert(extents->begin() + idx, e);
+ }
+ } else if (range_end == num_blocks) {
+ // Done with this extent.
+ idx++;
+ } else {
+ return false;
+ }
+
+ *idx_p = idx;
+ return true;
+}
+
+// Remove identical corresponding block ranges in |src_extents| and
+// |dst_extents|. Used for preventing moving of blocks onto themselves during
+// MOVE operations. The value of |total_bytes| indicates the actual length of
+// content; this may be slightly less than the total size of blocks, in which
+// case the last block is only partly occupied with data. Returns the total
+// number of bytes removed.
+size_t RemoveIdenticalBlockRanges(vector<Extent>* src_extents,
+ vector<Extent>* dst_extents,
+ const size_t total_bytes) {
+ size_t src_idx = 0;
+ size_t dst_idx = 0;
+ uint64_t src_offset = 0, dst_offset = 0;
+ bool new_src = true, new_dst = true;
+ size_t removed_bytes = 0, nonfull_block_bytes;
+ bool do_remove = false;
+ while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) {
+ if (new_src) {
+ src_offset = 0;
+ new_src = false;
+ }
+ if (new_dst) {
+ dst_offset = 0;
+ new_dst = false;
+ }
+
+ do_remove = ((*src_extents)[src_idx].start_block() + src_offset ==
+ (*dst_extents)[dst_idx].start_block() + dst_offset);
+
+ uint64_t src_num_blocks = (*src_extents)[src_idx].num_blocks();
+ uint64_t dst_num_blocks = (*dst_extents)[dst_idx].num_blocks();
+ uint64_t min_num_blocks = std::min(src_num_blocks - src_offset,
+ dst_num_blocks - dst_offset);
+ uint64_t prev_src_offset = src_offset;
+ uint64_t prev_dst_offset = dst_offset;
+ src_offset += min_num_blocks;
+ dst_offset += min_num_blocks;
+
+ new_src = ProcessExtentBlockRange(src_extents, &src_idx, do_remove,
+ prev_src_offset, src_offset);
+ new_dst = ProcessExtentBlockRange(dst_extents, &dst_idx, do_remove,
+ prev_dst_offset, dst_offset);
+ if (do_remove)
+ removed_bytes += min_num_blocks * kBlockSize;
+ }
+
+ // If we removed the last block and this block is only partly used by file
+ // content, deduct the unused portion from the total removed byte count.
+ if (do_remove && (nonfull_block_bytes = total_bytes % kBlockSize))
+ removed_bytes -= kBlockSize - nonfull_block_bytes;
+
+ return removed_bytes;
+}
+
+} // namespace
+
+namespace diff_utils {
+
+bool DeltaReadFilesystem(
+ vector<AnnotatedOperation>* aops,
+ const string& old_part,
+ const string& new_part,
+ FilesystemInterface* old_fs,
+ FilesystemInterface* new_fs,
+ off_t chunk_blocks,
+ int data_fd,
+ off_t* data_file_size,
+ bool skip_block_0,
+ bool src_ops_allowed) {
+ ExtentRanges old_visited_blocks;
+ ExtentRanges new_visited_blocks;
+
+ // We can't produce a MOVE operation with a 0 block as neither source nor
+ // destination, so we avoid generating an operation for the block 0 here, and
+ // we will add an operation for it in the InplaceGenerator. Excluding both
+ // old and new blocks ensures that identical images would still produce empty
+ // deltas.
+ if (skip_block_0) {
+ old_visited_blocks.AddBlock(0);
+ new_visited_blocks.AddBlock(0);
+ }
+
+ map<string, vector<Extent>> old_files_map;
+ if (old_fs) {
+ vector<FilesystemInterface::File> old_files;
+ old_fs->GetFiles(&old_files);
+ for (const FilesystemInterface::File& file : old_files)
+ old_files_map[file.name] = file.extents;
+ }
+
+ vector<FilesystemInterface::File> new_files;
+ new_fs->GetFiles(&new_files);
+
+ // The processing is very straightforward here, we generate operations for
+ // every file (and pseudo-file such as the metadata) in the new filesystem
+ // based on the file with the same name in the old filesystem, if any.
+ // Files with overlapping data blocks (like hardlinks or filesystems with tail
+ // packing or compression where the blocks store more than one file) are only
+ // generated once in the new image, but are also used only once from the old
+ // image due to some simplifications (see below).
+ for (const FilesystemInterface::File& new_file : new_files) {
+ // Ignore the files in the new filesystem without blocks. Symlinks with
+ // data blocks (for example, symlinks bigger than 60 bytes in ext2) are
+ // handled as normal files. We also ignore blocks that were already
+ // processed by a previous file.
+ vector<Extent> new_file_extents = FilterExtentRanges(
+ new_file.extents, new_visited_blocks);
+ new_visited_blocks.AddExtents(new_file_extents);
+
+ if (new_file_extents.empty())
+ continue;
+
+ LOG(INFO) << "Encoding file " << new_file.name << " ("
+ << BlocksInExtents(new_file_extents) << " blocks)";
+
+ // We can't visit each dst image inode more than once, as that would
+ // duplicate work. Here, we avoid visiting each source image inode
+ // more than once. Technically, we could have multiple operations
+ // that read the same blocks from the source image for diffing, but
+ // we choose not to avoid complexity. Eventually we will move away
+ // from using a graph/cycle detection/etc to generate diffs, and at that
+ // time, it will be easy (non-complex) to have many operations read
+ // from the same source blocks. At that time, this code can die. -adlr
+ vector<Extent> old_file_extents = FilterExtentRanges(
+ old_files_map[new_file.name], old_visited_blocks);
+ old_visited_blocks.AddExtents(old_file_extents);
+
+ TEST_AND_RETURN_FALSE(DeltaReadFile(
+ aops,
+ old_part,
+ new_part,
+ old_file_extents,
+ new_file_extents,
+ new_file.name, // operation name
+ chunk_blocks,
+ data_fd,
+ data_file_size,
+ src_ops_allowed));
+ }
+ // Process all the blocks not included in any file. We provided all the unused
+ // blocks in the old partition as available data.
+ vector<Extent> new_unvisited = { ExtentForRange(0, new_fs->GetBlockCount()) };
+ new_unvisited = FilterExtentRanges(new_unvisited, new_visited_blocks);
+ if (new_unvisited.empty())
+ return true;
+
+ vector<Extent> old_unvisited;
+ if (old_fs) {
+ old_unvisited.push_back(ExtentForRange(0, old_fs->GetBlockCount()));
+ old_unvisited = FilterExtentRanges(old_unvisited, old_visited_blocks);
+ }
+
+ LOG(INFO) << "Scanning " << BlocksInExtents(new_unvisited)
+ << " unwritten blocks";
+ TEST_AND_RETURN_FALSE(DeltaReadFile(
+ aops,
+ old_part,
+ new_part,
+ old_unvisited,
+ new_unvisited,
+ "<non-file-data>", // operation name
+ chunk_blocks,
+ data_fd,
+ data_file_size,
+ src_ops_allowed));
+
+ return true;
+}
+
+bool DeltaReadFile(
+ vector<AnnotatedOperation>* aops,
+ const string& old_part,
+ const string& new_part,
+ const vector<Extent>& old_extents,
+ const vector<Extent>& new_extents,
+ const string& name,
+ off_t chunk_blocks,
+ int data_fd,
+ off_t* data_file_size,
+ bool src_ops_allowed) {
+ chromeos::Blob data;
+ DeltaArchiveManifest_InstallOperation operation;
+
+ uint64_t total_blocks = BlocksInExtents(new_extents);
+ if (chunk_blocks == -1)
+ chunk_blocks = total_blocks;
+
+ // If bsdiff breaks again, blacklist the problem file by using:
+ // bsdiff_allowed = (name != "/foo/bar")
+ //
+ // TODO(dgarrett): chromium-os:15274 connect this test to the command line.
+ bool bsdiff_allowed = true;
+ if (static_cast<uint64_t>(chunk_blocks) * kBlockSize >
+ kMaxBsdiffDestinationSize) {
+ bsdiff_allowed = false;
+ }
+
+ if (!bsdiff_allowed) {
+ LOG(INFO) << "bsdiff blacklisting: " << name;
+ }
+
+ for (uint64_t block_offset = 0; block_offset < total_blocks;
+ block_offset += chunk_blocks) {
+ // Split the old/new file in the same chunks. Note that this could drop
+ // some information from the old file used for the new chunk. If the old
+ // file is smaller (or even empty when there's no old file) the chunk will
+ // also be empty.
+ vector<Extent> old_extents_chunk = ExtentsSublist(
+ old_extents, block_offset, chunk_blocks);
+ vector<Extent> new_extents_chunk = ExtentsSublist(
+ new_extents, block_offset, chunk_blocks);
+ NormalizeExtents(&old_extents_chunk);
+ NormalizeExtents(&new_extents_chunk);
+
+ TEST_AND_RETURN_FALSE(ReadExtentsToDiff(old_part,
+ new_part,
+ old_extents_chunk,
+ new_extents_chunk,
+ bsdiff_allowed,
+ &data,
+ &operation,
+ src_ops_allowed));
+
+ // Check if the operation writes nothing.
+ if (operation.dst_extents_size() == 0) {
+ if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+ LOG(INFO) << "Empty MOVE operation ("
+ << name << "), skipping";
+ continue;
+ } else {
+ LOG(ERROR) << "Empty non-MOVE operation";
+ return false;
+ }
+ }
+
+ // Write the data
+ if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE &&
+ operation.type() !=
+ DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) {
+ operation.set_data_offset(*data_file_size);
+ operation.set_data_length(data.size());
+ }
+
+ TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, data.data(), data.size()));
+ *data_file_size += data.size();
+
+ // Now, insert into the list of operations.
+ AnnotatedOperation aop;
+ aop.name = name;
+ if (static_cast<uint64_t>(chunk_blocks) < total_blocks) {
+ aop.name = base::StringPrintf("%s:%" PRIu64,
+ name.c_str(), block_offset / chunk_blocks);
+ }
+ aop.op = operation;
+ aops->emplace_back(aop);
+ }
+ return true;
+}
+
+bool ReadExtentsToDiff(const string& old_part,
+ const string& new_part,
+ const vector<Extent>& old_extents,
+ const vector<Extent>& new_extents,
+ bool bsdiff_allowed,
+ chromeos::Blob* out_data,
+ DeltaArchiveManifest_InstallOperation* out_op,
+ bool src_ops_allowed) {
+ DeltaArchiveManifest_InstallOperation operation;
+ // Data blob that will be written to delta file.
+ const chromeos::Blob* data_blob = nullptr;
+
+ // We read blocks from old_extents and write blocks to new_extents.
+ uint64_t blocks_to_read = BlocksInExtents(old_extents);
+ uint64_t blocks_to_write = BlocksInExtents(new_extents);
+
+ // Make copies of the extents so we can modify them.
+ vector<Extent> src_extents = old_extents;
+ vector<Extent> dst_extents = new_extents;
+
+ // Read in bytes from new data.
+ chromeos::Blob new_data;
+ TEST_AND_RETURN_FALSE(utils::ReadExtents(new_part,
+ new_extents,
+ &new_data,
+ kBlockSize * blocks_to_write,
+ kBlockSize));
+ TEST_AND_RETURN_FALSE(!new_data.empty());
+
+
+ // Using a REPLACE is always an option.
+ operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ data_blob = &new_data;
+
+ // Try compressing it with bzip2.
+ chromeos::Blob new_data_bz;
+ TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
+ CHECK(!new_data_bz.empty());
+ if (new_data_bz.size() < data_blob->size()) {
+ // A REPLACE_BZ is better.
+ operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ data_blob = &new_data_bz;
+ }
+
+ chromeos::Blob old_data;
+ chromeos::Blob empty_blob;
+ chromeos::Blob bsdiff_delta;
+ if (blocks_to_read > 0) {
+ // Read old data.
+ TEST_AND_RETURN_FALSE(
+ utils::ReadExtents(old_part, src_extents, &old_data,
+ kBlockSize * blocks_to_read, kBlockSize));
+ if (old_data == new_data) {
+ // No change in data.
+ if (src_ops_allowed) {
+ operation.set_type(
+ DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+ } else {
+ operation.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ }
+ data_blob = &empty_blob;
+ } else if (bsdiff_allowed) {
+ // If the source file is considered bsdiff safe (no bsdiff bugs
+ // triggered), see if BSDIFF encoding is smaller.
+ base::FilePath old_chunk;
+ TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&old_chunk));
+ ScopedPathUnlinker old_unlinker(old_chunk.value());
+ TEST_AND_RETURN_FALSE(
+ utils::WriteFile(old_chunk.value().c_str(),
+ old_data.data(), old_data.size()));
+ base::FilePath new_chunk;
+ TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&new_chunk));
+ ScopedPathUnlinker new_unlinker(new_chunk.value());
+ TEST_AND_RETURN_FALSE(
+ utils::WriteFile(new_chunk.value().c_str(),
+ new_data.data(), new_data.size()));
+
+ TEST_AND_RETURN_FALSE(
+ BsdiffFiles(old_chunk.value(), new_chunk.value(), &bsdiff_delta));
+ CHECK_GT(bsdiff_delta.size(), static_cast<chromeos::Blob::size_type>(0));
+ if (bsdiff_delta.size() < data_blob->size()) {
+ if (src_ops_allowed) {
+ operation.set_type(
+ DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF);
+ } else {
+ operation.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+ }
+ data_blob = &bsdiff_delta;
+ }
+ }
+ }
+
+ size_t removed_bytes = 0;
+ // Remove identical src/dst block ranges in MOVE operations.
+ if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+ removed_bytes = RemoveIdenticalBlockRanges(
+ &src_extents, &dst_extents, new_data.size());
+ }
+ // Set legacy src_length and dst_length fields.
+ operation.set_src_length(old_data.size() - removed_bytes);
+ operation.set_dst_length(new_data.size() - removed_bytes);
+
+ // Embed extents in the operation.
+ StoreExtents(src_extents, operation.mutable_src_extents());
+ StoreExtents(dst_extents, operation.mutable_dst_extents());
+
+ // Replace operations should not have source extents.
+ if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+ operation.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+ operation.clear_src_extents();
+ operation.clear_src_length();
+ }
+
+ *out_data = std::move(*data_blob);
+ *out_op = operation;
+
+ return true;
+}
+
+bool DeltaCompressKernelPartition(
+ const string& old_kernel_part,
+ const string& new_kernel_part,
+ uint64_t old_kernel_size,
+ uint64_t new_kernel_size,
+ uint64_t block_size,
+ vector<AnnotatedOperation>* aops,
+ int blobs_fd,
+ off_t* blobs_length,
+ bool src_ops_allowed) {
+ LOG(INFO) << "Delta compressing kernel partition...";
+ LOG_IF(INFO, old_kernel_part.empty()) << "Generating full kernel update...";
+
+ unique_ptr<RawFilesystem> old_kernel_fs;
+ if (!old_kernel_part.empty())
+ old_kernel_fs = RawFilesystem::Create("<kernel-delta-operation>",
+ block_size,
+ old_kernel_size / block_size);
+ unique_ptr<RawFilesystem> new_kernel_fs = RawFilesystem::Create(
+ "<kernel-delta-operation>",
+ block_size,
+ new_kernel_size / block_size);
+
+ TEST_AND_RETURN_FALSE(DeltaReadFilesystem(aops,
+ old_kernel_part,
+ new_kernel_part,
+ old_kernel_fs.get(),
+ new_kernel_fs.get(),
+ -1, // chunk_blocks
+ blobs_fd,
+ blobs_length,
+ false, // skip_block_0
+ src_ops_allowed));
+
+ LOG(INFO) << "Done delta compressing kernel partition.";
+ return true;
+}
+
+// Runs the bsdiff tool on two files and returns the resulting delta in
+// 'out'. Returns true on success.
+bool BsdiffFiles(const string& old_file,
+ const string& new_file,
+ chromeos::Blob* out) {
+ const string kPatchFile = "delta.patchXXXXXX";
+ string patch_file_path;
+
+ TEST_AND_RETURN_FALSE(
+ utils::MakeTempFile(kPatchFile, &patch_file_path, nullptr));
+
+ vector<string> cmd;
+ cmd.push_back(kBsdiffPath);
+ cmd.push_back(old_file);
+ cmd.push_back(new_file);
+ cmd.push_back(patch_file_path);
+
+ int rc = 1;
+ chromeos::Blob patch_file;
+ TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, nullptr));
+ TEST_AND_RETURN_FALSE(rc == 0);
+ TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
+ unlink(patch_file_path.c_str());
+ return true;
+}
+
+// Returns true if |op| is a no-op operation that doesn't do any useful work
+// (e.g., a move operation that copies blocks onto themselves).
+bool IsNoopOperation(const DeltaArchiveManifest_InstallOperation& op) {
+ return (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE &&
+ ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
+}
+
+void FilterNoopOperations(vector<AnnotatedOperation>* ops) {
+ ops->erase(
+ std::remove_if(
+ ops->begin(), ops->end(),
+ [](const AnnotatedOperation& aop){return IsNoopOperation(aop.op);}),
+ ops->end());
+}
+
+bool InitializePartitionInfo(const PartitionConfig& part, PartitionInfo* info) {
+ info->set_size(part.size);
+ OmahaHashCalculator hasher;
+ TEST_AND_RETURN_FALSE(hasher.UpdateFile(part.path, part.size) ==
+ static_cast<off_t>(part.size));
+ TEST_AND_RETURN_FALSE(hasher.Finalize());
+ const chromeos::Blob& hash = hasher.raw_hash();
+ info->set_hash(hash.data(), hash.size());
+ LOG(INFO) << part.path << ": size=" << part.size << " hash=" << hasher.hash();
+ return true;
+}
+
+} // namespace diff_utils
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_utils.h b/payload_generator/delta_diff_utils.h
new file mode 100644
index 0000000..aa18f16
--- /dev/null
+++ b/payload_generator/delta_diff_utils.h
@@ -0,0 +1,116 @@
+// 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_DELTA_DIFF_UTILS_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_UTILS_H_
+
+#include <string>
+#include <vector>
+
+#include <chromeos/secure_blob.h>
+
+#include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/filesystem_interface.h"
+#include "update_engine/payload_generator/payload_generation_config.h"
+#include "update_engine/update_metadata.pb.h"
+
+namespace chromeos_update_engine {
+
+namespace diff_utils {
+
+// Create operations in |aops| to produce all the files reported by |new_fs|,
+// including all the blocks not reported by any file.
+// It uses the files reported by |old_fs| and the data in |old_part| to
+// determine the best way to compress the new files (REPLACE, REPLACE_BZ,
+// COPY, BSDIFF) and writes any necessary data to the end of data_fd updating
+// data_file_size accordingly.
+bool DeltaReadFilesystem(std::vector<AnnotatedOperation>* aops,
+ const std::string& old_part,
+ const std::string& new_part,
+ FilesystemInterface* old_fs,
+ FilesystemInterface* new_fs,
+ off_t chunk_blocks,
+ int data_fd,
+ off_t* data_file_size,
+ bool skip_block_0,
+ bool src_ops_allowed);
+
+// 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
+// stored in |new_part| in the blocks described by |new_extents| and, if it
+// exists, the old version exists in |old_part| in the blocks described by
+// |old_extents|. The operations added to |aops| reference the data blob
+// in the file |data_fd|, which has length *data_file_size. *data_file_size is
+// updated appropriately. Returns true on success.
+bool DeltaReadFile(std::vector<AnnotatedOperation>* aops,
+ const std::string& old_part,
+ const std::string& new_part,
+ const std::vector<Extent>& old_extents,
+ const std::vector<Extent>& new_extents,
+ const std::string& name,
+ off_t chunk_blocks,
+ int data_fd,
+ off_t* data_file_size,
+ bool src_ops_allowed);
+
+// Reads the blocks |old_extents| from |old_part| (if it exists) and the
+// |new_extents| from |new_part| and determines the smallest way to encode
+// this |new_extents| for the diff. It stores necessary data in |out_data| and
+// fills in |out_op|. If there's no change in old and new files, it creates a
+// MOVE operation. If there is a change, the smallest of REPLACE, REPLACE_BZ,
+// or BSDIFF wins. |new_extents| must not be empty.
+// If |src_ops_allowed| is true, it will emit SOURCE_COPY and SOURCE_BSDIFF
+// operations instead of MOVE and BSDIFF, respectively.
+// Returns true on success.
+bool ReadExtentsToDiff(const std::string& old_part,
+ const std::string& new_part,
+ const std::vector<Extent>& old_extents,
+ const std::vector<Extent>& new_extents,
+ bool bsdiff_allowed,
+ chromeos::Blob* out_data,
+ DeltaArchiveManifest_InstallOperation* out_op,
+ bool src_ops_allowed);
+
+// Delta compresses a kernel partition |new_kernel_part| with knowledge of the
+// old kernel partition |old_kernel_part|. If |old_kernel_part| is an empty
+// string, generates a full update of the partition. The size of the old and
+// new kernel is passed in |old_kernel_size| and |new_kernel_size|. The
+// operations used to generate the new kernel are stored in the |aops|
+// vector, and the blob associated to those operations is written at the end
+// of the |blobs_fd| file, adding to the value pointed by |blobs_length| the
+// bytes written to |blobs_fd|.
+bool DeltaCompressKernelPartition(
+ const std::string& old_kernel_part,
+ const std::string& new_kernel_part,
+ uint64_t old_kernel_size,
+ uint64_t new_kernel_size,
+ uint64_t block_size,
+ std::vector<AnnotatedOperation>* aops,
+ int blobs_fd,
+ off_t* blobs_length,
+ bool src_ops_allowed);
+
+// Runs the bsdiff tool on two files and returns the resulting delta in
+// |out|. Returns true on success.
+bool BsdiffFiles(const std::string& old_file,
+ const std::string& new_file,
+ chromeos::Blob* out);
+
+// Returns true if |op| is a no-op operation that doesn't do any useful work
+// (e.g., a move operation that copies blocks onto themselves).
+bool IsNoopOperation(const DeltaArchiveManifest_InstallOperation& op);
+
+// Filters all the operations that are no-op, maintaining the relative order
+// of the rest of the operations.
+void FilterNoopOperations(std::vector<AnnotatedOperation>* ops);
+
+bool InitializePartitionInfo(const PartitionConfig& partition,
+ PartitionInfo* info);
+
+} // namespace diff_utils
+
+} // namespace chromeos_update_engine
+
+#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_UTILS_H_
diff --git a/payload_generator/delta_diff_utils_unittest.cc b/payload_generator/delta_diff_utils_unittest.cc
new file mode 100644
index 0000000..2157aa1
--- /dev/null
+++ b/payload_generator/delta_diff_utils_unittest.cc
@@ -0,0 +1,479 @@
+// 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/delta_diff_utils.h"
+
+#include <algorithm>
+#include <string>
+#include <vector>
+
+#include <base/files/scoped_file.h>
+#include <gtest/gtest.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"
+#include "update_engine/payload_generator/fake_filesystem.h"
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::unique_ptr;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+// Writes the |data| in the blocks specified by |extents| on the partition
+// |part_path|. The |data| size could be smaller than the size of the blocks
+// passed.
+bool WriteExtents(const string& part_path,
+ const vector<Extent>& extents,
+ off_t block_size,
+ const chromeos::Blob& data) {
+ uint64_t offset = 0;
+ base::ScopedFILE fp(fopen(part_path.c_str(), "r+"));
+ TEST_AND_RETURN_FALSE(fp.get());
+
+ for (const Extent& extent : extents) {
+ if (offset >= data.size())
+ break;
+ TEST_AND_RETURN_FALSE(
+ fseek(fp.get(), extent.start_block() * block_size, SEEK_SET) == 0);
+ uint64_t to_write = std::min(extent.num_blocks() * block_size,
+ data.size() - offset);
+ TEST_AND_RETURN_FALSE(
+ fwrite(data.data() + offset, 1, to_write, fp.get()) == to_write);
+ offset += extent.num_blocks() * block_size;
+ }
+ return true;
+}
+
+} // namespace
+
+class DeltaDiffUtilsTest : public ::testing::Test {
+ protected:
+ const uint64_t kFilesystemSize = kBlockSize * 1024;
+
+ 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);
+ }
+
+ void TearDown() override {
+ unlink(old_part_path_.c_str());
+ unlink(new_part_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));
+ }
+
+ // Paths to old and new temporary filesystems used in the tests.
+ string old_part_path_;
+ string new_part_path_;
+
+ // FilesystemInterface fake implementations used to mock out the file/block
+ // distribution.
+ unique_ptr<FakeFilesystem> old_fs_;
+ unique_ptr<FakeFilesystem> new_fs_;
+};
+
+TEST_F(DeltaDiffUtilsTest, MoveSmallTest) {
+ chromeos::Blob data_blob(kBlockSize);
+ 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));
+
+ chromeos::Blob data;
+ DeltaArchiveManifest_InstallOperation op;
+ EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+ old_part_path_,
+ new_part_path_,
+ old_extents,
+ new_extents,
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ false)); // src_ops_allowed
+ EXPECT_TRUE(data.empty());
+
+ EXPECT_TRUE(op.has_type());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
+ EXPECT_FALSE(op.has_data_offset());
+ EXPECT_FALSE(op.has_data_length());
+ EXPECT_EQ(1, op.src_extents_size());
+ EXPECT_EQ(kBlockSize, op.src_length());
+ EXPECT_EQ(1, op.dst_extents_size());
+ EXPECT_EQ(kBlockSize, op.dst_length());
+ EXPECT_EQ(BlocksInExtents(op.src_extents()),
+ BlocksInExtents(op.dst_extents()));
+ EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+}
+
+TEST_F(DeltaDiffUtilsTest, MoveWithSameBlock) {
+ // Setup the old/new files so that it has immobile chunks; we make sure to
+ // utilize all sub-cases of such chunks: blocks 21--22 induce a split (src)
+ // and complete removal (dst), whereas blocks 24--25 induce trimming of the
+ // tail (src) and head (dst) of extents. The final block (29) is used for
+ // ensuring we properly account for the number of bytes removed in cases where
+ // the last block is partly filled. The detailed configuration:
+ //
+ // Old: [ 20 21 22 23 24 25 ] [ 28 29 ]
+ // New: [ 18 ] [ 21 22 ] [ 20 ] [ 24 25 26 ] [ 29 ]
+ // Same: ^^ ^^ ^^ ^^ ^^
+ vector<Extent> old_extents = {
+ ExtentForRange(20, 6),
+ ExtentForRange(28, 2) };
+ vector<Extent> new_extents = {
+ ExtentForRange(18, 1),
+ ExtentForRange(21, 2),
+ ExtentForRange(20, 1),
+ ExtentForRange(24, 3),
+ ExtentForRange(29, 1) };
+
+ uint64_t num_blocks = BlocksInExtents(old_extents);
+ EXPECT_EQ(num_blocks, BlocksInExtents(new_extents));
+
+ // The size of the data should match the total number of blocks. Each block
+ // has a different content.
+ chromeos::Blob file_data;
+ for (uint64_t i = 0; i < num_blocks; ++i) {
+ 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));
+
+ chromeos::Blob data;
+ DeltaArchiveManifest_InstallOperation op;
+ EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+ old_part_path_,
+ new_part_path_,
+ old_extents,
+ new_extents,
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ false)); // src_ops_allowed
+
+ EXPECT_TRUE(data.empty());
+
+ EXPECT_TRUE(op.has_type());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
+ EXPECT_FALSE(op.has_data_offset());
+ EXPECT_FALSE(op.has_data_length());
+
+ // The expected old and new extents that actually moved. See comment above.
+ old_extents = {
+ ExtentForRange(20, 1),
+ ExtentForRange(23, 1),
+ ExtentForRange(28, 1) };
+ new_extents = {
+ ExtentForRange(18, 1),
+ ExtentForRange(20, 1),
+ ExtentForRange(26, 1) };
+ num_blocks = BlocksInExtents(old_extents);
+
+ EXPECT_EQ(num_blocks * kBlockSize, op.src_length());
+ EXPECT_EQ(num_blocks * kBlockSize, op.dst_length());
+
+ EXPECT_EQ(old_extents.size(), op.src_extents_size());
+ for (int i = 0; i < op.src_extents_size(); i++) {
+ EXPECT_EQ(old_extents[i].start_block(), op.src_extents(i).start_block())
+ << "i == " << i;
+ EXPECT_EQ(old_extents[i].num_blocks(), op.src_extents(i).num_blocks())
+ << "i == " << i;
+ }
+
+ EXPECT_EQ(new_extents.size(), op.dst_extents_size());
+ for (int i = 0; i < op.dst_extents_size(); i++) {
+ EXPECT_EQ(new_extents[i].start_block(), op.dst_extents(i).start_block())
+ << "i == " << i;
+ EXPECT_EQ(new_extents[i].num_blocks(), op.dst_extents(i).num_blocks())
+ << "i == " << i;
+ }
+}
+
+TEST_F(DeltaDiffUtilsTest, BsdiffSmallTest) {
+ // Test a BSDIFF operation from block 1 to block 2.
+ chromeos::Blob data_blob(kBlockSize);
+ test_utils::FillWithData(&data_blob);
+
+ // The old file is on a different block than the new one.
+ 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));
+ // Modify one byte in the new file.
+ data_blob[0]++;
+ 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_extents,
+ new_extents,
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ false)); // src_ops_allowed
+
+ EXPECT_FALSE(data.empty());
+
+ EXPECT_TRUE(op.has_type());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
+ EXPECT_FALSE(op.has_data_offset());
+ EXPECT_FALSE(op.has_data_length());
+ EXPECT_EQ(1, op.src_extents_size());
+ EXPECT_EQ(kBlockSize, op.src_length());
+ EXPECT_EQ(1, op.dst_extents_size());
+ EXPECT_EQ(kBlockSize, op.dst_length());
+ EXPECT_EQ(BlocksInExtents(op.src_extents()),
+ BlocksInExtents(op.dst_extents()));
+ EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+}
+
+TEST_F(DeltaDiffUtilsTest, BsdiffNotAllowedTest) {
+ // Same setup as the previous test, but this time BSDIFF operations are not
+ // allowed.
+ chromeos::Blob data_blob(kBlockSize);
+ test_utils::FillWithData(&data_blob);
+
+ // The old file is on a different block than the new one.
+ 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));
+ // Modify one byte in the new file.
+ data_blob[0]++;
+ 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_extents,
+ new_extents,
+ false, // bsdiff_allowed
+ &data,
+ &op,
+ false)); // src_ops_allowed
+
+ EXPECT_FALSE(data.empty());
+
+ // The point of this test is that we don't use BSDIFF the way the above
+ // did. The rest of the details are to be caught in other tests.
+ EXPECT_TRUE(op.has_type());
+ EXPECT_NE(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
+}
+
+TEST_F(DeltaDiffUtilsTest, BsdiffNotAllowedMoveTest) {
+ chromeos::Blob data_blob(kBlockSize);
+ test_utils::FillWithData(&data_blob);
+
+ // The old file is on a different block than the new one.
+ 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));
+
+ chromeos::Blob data;
+ DeltaArchiveManifest_InstallOperation op;
+ EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+ old_part_path_,
+ new_part_path_,
+ old_extents,
+ new_extents,
+ false, // bsdiff_allowed
+ &data,
+ &op,
+ false)); // src_ops_allowed
+
+ EXPECT_TRUE(data.empty());
+
+ // The point of this test is that we can still use a MOVE for a file
+ // that is blacklisted.
+ EXPECT_TRUE(op.has_type());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
+}
+
+TEST_F(DeltaDiffUtilsTest, ReplaceSmallTest) {
+ // The old file is on a different block than the new one.
+ vector<Extent> old_extents = { ExtentForRange(1, 1) };
+ vector<Extent> new_extents = { ExtentForRange(2, 1) };
+
+ // Make a blob that's just 1's that will compress well.
+ chromeos::Blob ones(kBlockSize, 1);
+
+ // Make a blob with random data that won't compress well.
+ chromeos::Blob random_data;
+ std::mt19937 gen(12345);
+ std::uniform_int_distribution<uint8_t> dis(0, 255);
+ for (uint32_t i = 0; i < kBlockSize; i++) {
+ random_data.push_back(dis(gen));
+ }
+
+ 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,
+ data_to_test));
+
+ chromeos::Blob data;
+ DeltaArchiveManifest_InstallOperation op;
+ EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+ old_part_path_,
+ new_part_path_,
+ old_extents,
+ new_extents,
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ false)); // src_ops_allowed
+ EXPECT_FALSE(data.empty());
+
+ EXPECT_TRUE(op.has_type());
+ const DeltaArchiveManifest_InstallOperation_Type expected_type =
+ (i == 0 ? DeltaArchiveManifest_InstallOperation_Type_REPLACE :
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ EXPECT_EQ(expected_type, op.type());
+ EXPECT_FALSE(op.has_data_offset());
+ EXPECT_FALSE(op.has_data_length());
+ EXPECT_EQ(0, op.src_extents_size());
+ EXPECT_FALSE(op.has_src_length());
+ EXPECT_EQ(1, op.dst_extents_size());
+ EXPECT_EQ(data_to_test.size(), op.dst_length());
+ EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+ }
+}
+
+TEST_F(DeltaDiffUtilsTest, SourceCopyTest) {
+ // Makes sure SOURCE_COPY operations are emitted whenever src_ops_allowed
+ // is true. It is the same setup as MoveSmallTest, which checks that
+ // the operation is well-formed.
+ chromeos::Blob data_blob(kBlockSize);
+ 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));
+
+ chromeos::Blob data;
+ DeltaArchiveManifest_InstallOperation op;
+ EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+ old_part_path_,
+ new_part_path_,
+ old_extents,
+ new_extents,
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ true)); // src_ops_allowed
+ EXPECT_TRUE(data.empty());
+
+ EXPECT_TRUE(op.has_type());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY, op.type());
+}
+
+TEST_F(DeltaDiffUtilsTest, SourceBsdiffTest) {
+ // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
+ // is true. It is the same setup as BsdiffSmallTest, which checks
+ // that the operation is well-formed.
+ chromeos::Blob data_blob(kBlockSize);
+ test_utils::FillWithData(&data_blob);
+
+ // The old file is on a different block than the new one.
+ 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));
+ // Modify one byte in the new file.
+ data_blob[0]++;
+ 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_extents,
+ new_extents,
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ true)); // src_ops_allowed
+
+ EXPECT_FALSE(data.empty());
+ EXPECT_TRUE(op.has_type());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF,
+ op.type());
+}
+
+TEST_F(DeltaDiffUtilsTest, IsNoopOperationTest) {
+ DeltaArchiveManifest_InstallOperation op;
+ op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ EXPECT_FALSE(diff_utils::IsNoopOperation(op));
+ op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ EXPECT_TRUE(diff_utils::IsNoopOperation(op));
+ *(op.add_src_extents()) = ExtentForRange(3, 2);
+ *(op.add_dst_extents()) = ExtentForRange(3, 2);
+ EXPECT_TRUE(diff_utils::IsNoopOperation(op));
+ *(op.add_src_extents()) = ExtentForRange(7, 5);
+ *(op.add_dst_extents()) = ExtentForRange(7, 5);
+ EXPECT_TRUE(diff_utils::IsNoopOperation(op));
+ *(op.add_src_extents()) = ExtentForRange(20, 2);
+ *(op.add_dst_extents()) = ExtentForRange(20, 1);
+ *(op.add_dst_extents()) = ExtentForRange(21, 1);
+ EXPECT_TRUE(diff_utils::IsNoopOperation(op));
+ *(op.add_src_extents()) = ExtentForRange(24, 1);
+ *(op.add_dst_extents()) = ExtentForRange(25, 1);
+ EXPECT_FALSE(diff_utils::IsNoopOperation(op));
+}
+
+TEST_F(DeltaDiffUtilsTest, FilterNoopOperations) {
+ AnnotatedOperation aop1;
+ aop1.op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ *(aop1.op.add_dst_extents()) = ExtentForRange(3, 2);
+ aop1.name = "aop1";
+
+ AnnotatedOperation aop2 = aop1;
+ aop2.name = "aop2";
+
+ AnnotatedOperation noop;
+ noop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ *(noop.op.add_src_extents()) = ExtentForRange(3, 2);
+ *(noop.op.add_dst_extents()) = ExtentForRange(3, 2);
+ noop.name = "noop";
+
+ vector<AnnotatedOperation> ops = {noop, aop1, noop, noop, aop2, noop};
+ diff_utils::FilterNoopOperations(&ops);
+ EXPECT_EQ(2u, ops.size());
+ EXPECT_EQ("aop1", ops[0].name);
+ EXPECT_EQ("aop2", ops[1].name);
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/extent_utils.cc b/payload_generator/extent_utils.cc
index 71aae1d..caacb38 100644
--- a/payload_generator/extent_utils.cc
+++ b/payload_generator/extent_utils.cc
@@ -41,12 +41,46 @@
Extent GetElement(const vector<Extent>& collection, size_t index) {
return collection[index];
}
+
Extent GetElement(
const google::protobuf::RepeatedPtrField<Extent>& collection,
size_t index) {
return collection.Get(index);
}
+void ExtendExtents(
+ google::protobuf::RepeatedPtrField<Extent>* extents,
+ const google::protobuf::RepeatedPtrField<Extent>& extents_to_add) {
+ vector<Extent> extents_vector;
+ vector<Extent> extents_to_add_vector;
+ ExtentsToVector(*extents, &extents_vector);
+ ExtentsToVector(extents_to_add, &extents_to_add_vector);
+ extents_vector.insert(extents_vector.end(),
+ extents_to_add_vector.begin(),
+ extents_to_add_vector.end());
+ NormalizeExtents(&extents_vector);
+ extents->Clear();
+ StoreExtents(extents_vector, extents);
+}
+
+// Stores all Extents in 'extents' into 'out'.
+void StoreExtents(const vector<Extent>& extents,
+ google::protobuf::RepeatedPtrField<Extent>* out) {
+ for (const Extent& extent : extents) {
+ Extent* new_extent = out->Add();
+ *new_extent = extent;
+ }
+}
+
+// Stores all extents in |extents| into |out_vector|.
+void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents,
+ vector<Extent>* out_vector) {
+ out_vector->clear();
+ for (int i = 0; i < extents.size(); i++) {
+ out_vector->push_back(extents.Get(i));
+ }
+}
+
void NormalizeExtents(vector<Extent>* extents) {
vector<Extent> new_extents;
for (const Extent& curr_ext : *extents) {
diff --git a/payload_generator/extent_utils.h b/payload_generator/extent_utils.h
index e9ab9eb..eeeed40 100644
--- a/payload_generator/extent_utils.h
+++ b/payload_generator/extent_utils.h
@@ -7,6 +7,7 @@
#include <vector>
+#include "update_engine/payload_constants.h"
#include "update_engine/update_metadata.pb.h"
// Utility functions for manipulating Extents and lists of blocks.
@@ -25,6 +26,8 @@
const google::protobuf::RepeatedPtrField<Extent>& collection,
size_t index);
+// Return the total number of blocks in a collection (vector or
+// RepeatedPtrField) of Extents.
template<typename T>
uint64_t BlocksInExtents(const T& collection) {
uint64_t ret = 0;
@@ -34,6 +37,39 @@
return ret;
}
+// Takes a collection (vector or RepeatedPtrField) of Extent and
+// returns a vector of the blocks referenced, in order.
+template<typename T>
+std::vector<uint64_t> ExpandExtents(const T& extents) {
+ std::vector<uint64_t> ret;
+ for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) {
+ const Extent extent = GetElement(extents, i);
+ if (extent.start_block() == kSparseHole) {
+ ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
+ } else {
+ for (uint64_t block = extent.start_block();
+ block < (extent.start_block() + extent.num_blocks()); block++) {
+ ret.push_back(block);
+ }
+ }
+ }
+ return ret;
+}
+
+// Stores all Extents in 'extents' into 'out'.
+void StoreExtents(const std::vector<Extent>& extents,
+ google::protobuf::RepeatedPtrField<Extent>* out);
+
+// Stores all extents in |extents| into |out_vector|.
+void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents,
+ std::vector<Extent>* out_vector);
+
+// Takes a pointer to extents |extents| and extents |extents_to_add|, and
+// merges them by adding |extents_to_add| to |extents| and normalizing.
+void ExtendExtents(
+ google::protobuf::RepeatedPtrField<Extent>* extents,
+ const google::protobuf::RepeatedPtrField<Extent>& extents_to_add);
+
// Takes a vector of extents and normalizes those extents. Expects the extents
// to be sorted by start block. E.g. if |extents| is [(1, 2), (3, 5), (10, 2)]
// then |extents| will be changed to [(1, 7), (10, 2)].
diff --git a/payload_generator/extent_utils_unittest.cc b/payload_generator/extent_utils_unittest.cc
index b9f9ef2..188164d 100644
--- a/payload_generator/extent_utils_unittest.cc
+++ b/payload_generator/extent_utils_unittest.cc
@@ -62,6 +62,24 @@
}
}
+TEST(ExtentUtilsTest, ExtendExtentsTest) {
+ DeltaArchiveManifest_InstallOperation first_op;
+ *(first_op.add_src_extents()) = ExtentForRange(1, 1);
+ *(first_op.add_src_extents()) = ExtentForRange(3, 1);
+
+ DeltaArchiveManifest_InstallOperation second_op;
+ *(second_op.add_src_extents()) = ExtentForRange(4, 2);
+ *(second_op.add_src_extents()) = ExtentForRange(8, 2);
+
+ ExtendExtents(first_op.mutable_src_extents(), second_op.src_extents());
+ vector<Extent> first_op_vec;
+ ExtentsToVector(first_op.src_extents(), &first_op_vec);
+ EXPECT_EQ((vector<Extent>{
+ ExtentForRange(1, 1),
+ ExtentForRange(3, 3),
+ ExtentForRange(8, 2)}), first_op_vec);
+}
+
TEST(ExtentUtilsTest, NormalizeExtentsSimpleList) {
// Make sure it works when there's just one extent.
vector<Extent> extents;
diff --git a/payload_generator/generate_delta_main.cc b/payload_generator/generate_delta_main.cc
index 7f7b2b8..662c1f4 100644
--- a/payload_generator/generate_delta_main.cc
+++ b/payload_generator/generate_delta_main.cc
@@ -20,6 +20,7 @@
#include "update_engine/delta_performer.h"
#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
#include "update_engine/payload_generator/payload_generation_config.h"
#include "update_engine/payload_generator/payload_signer.h"
#include "update_engine/payload_verifier.h"
@@ -190,10 +191,8 @@
old_image.kernel.path = old_kernel;
old_image.rootfs.path = old_rootfs;
CHECK(old_image.LoadImageSize());
- CHECK(DeltaDiffGenerator::InitializePartitionInfo(old_image.kernel,
- &kern_info));
- CHECK(DeltaDiffGenerator::InitializePartitionInfo(old_image.rootfs,
- &root_info));
+ CHECK(diff_utils::InitializePartitionInfo(old_image.kernel, &kern_info));
+ CHECK(diff_utils::InitializePartitionInfo(old_image.rootfs, &root_info));
install_plan.kernel_hash.assign(kern_info.hash().begin(),
kern_info.hash().end());
install_plan.rootfs_hash.assign(root_info.hash().begin(),
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index 9494d73..2ada2f3 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -14,6 +14,7 @@
#include "update_engine/payload_constants.h"
#include "update_engine/payload_generator/cycle_breaker.h"
#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
#include "update_engine/payload_generator/ext2_filesystem.h"
#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/payload_generator/graph_types.h"
@@ -74,25 +75,22 @@
const vector<Extent>& replace_extents) {
// First, expand out the blocks that op reads from
vector<uint64_t> read_blocks =
- DeltaDiffGenerator::ExpandExtents(vertex->op.src_extents());
+ ExpandExtents(vertex->op.src_extents());
{
// Expand remove_extents and replace_extents
- vector<uint64_t> remove_extents_expanded =
- DeltaDiffGenerator::ExpandExtents(remove_extents);
- vector<uint64_t> replace_extents_expanded =
- DeltaDiffGenerator::ExpandExtents(replace_extents);
+ vector<uint64_t> remove_extents_expanded = ExpandExtents(remove_extents);
+ vector<uint64_t> replace_extents_expanded = ExpandExtents(replace_extents);
CHECK_EQ(remove_extents_expanded.size(), replace_extents_expanded.size());
map<uint64_t, uint64_t> conversion;
for (vector<uint64_t>::size_type i = 0;
i < replace_extents_expanded.size(); i++) {
conversion[remove_extents_expanded[i]] = replace_extents_expanded[i];
}
- utils::ApplyMap(&read_blocks, conversion);
+ ApplyMap(&read_blocks, conversion);
for (auto& edge_prop_pair : vertex->out_edges) {
- vector<uint64_t> write_before_deps_expanded =
- DeltaDiffGenerator::ExpandExtents(
- edge_prop_pair.second.write_extents);
- utils::ApplyMap(&write_before_deps_expanded, conversion);
+ vector<uint64_t> write_before_deps_expanded = ExpandExtents(
+ edge_prop_pair.second.write_extents);
+ ApplyMap(&write_before_deps_expanded, conversion);
edge_prop_pair.second.write_extents =
CompressExtents(write_before_deps_expanded);
}
@@ -100,8 +98,7 @@
// Convert read_blocks back to extents
vertex->op.clear_src_extents();
vector<Extent> new_extents = CompressExtents(read_blocks);
- DeltaDiffGenerator::StoreExtents(new_extents,
- vertex->op.mutable_src_extents());
+ StoreExtents(new_extents, vertex->op.mutable_src_extents());
}
bool InplaceGenerator::CutEdges(Graph* graph,
@@ -141,11 +138,10 @@
// Set src/dst extents and other proto variables for copy operation
graph->back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
- DeltaDiffGenerator::StoreExtents(
- cut_edge_properties.extents,
- graph->back().op.mutable_src_extents());
- DeltaDiffGenerator::StoreExtents(cuts.back().tmp_extents,
- graph->back().op.mutable_dst_extents());
+ StoreExtents(cut_edge_properties.extents,
+ graph->back().op.mutable_src_extents());
+ StoreExtents(cuts.back().tmp_extents,
+ graph->back().op.mutable_dst_extents());
graph->back().op.set_src_length(
graph_utils::EdgeWeight(*graph, edge) * kBlockSize);
graph->back().op.set_dst_length(graph->back().op.src_length());
@@ -430,7 +426,7 @@
// blocks.
DeltaArchiveManifest_InstallOperation *op = &(*graph)[cut.new_vertex].op;
op->clear_dst_extents();
- DeltaDiffGenerator::StoreExtents(real_extents, op->mutable_dst_extents());
+ StoreExtents(real_extents, op->mutable_dst_extents());
}
return true;
}
@@ -534,11 +530,11 @@
// |new_extents| list of blocks and update the graph.
vector<AnnotatedOperation> new_aop;
vector<Extent> new_extents;
- DeltaDiffGenerator::ExtentsToVector((*graph)[cut.old_dst].op.dst_extents(),
- &new_extents);
- TEST_AND_RETURN_FALSE(DeltaDiffGenerator::DeltaReadFile(
+ ExtentsToVector((*graph)[cut.old_dst].op.dst_extents(),
+ &new_extents);
+ TEST_AND_RETURN_FALSE(diff_utils::DeltaReadFile(
&new_aop,
- kEmptyPath, // old_part
+ "", // old_part
new_part,
vector<Extent>(), // old_extents
new_extents,
@@ -701,6 +697,15 @@
return true;
}
+void InplaceGenerator::ApplyMap(vector<uint64_t>* collection,
+ const map<uint64_t, uint64_t>& the_map) {
+ for (uint64_t& elem : *collection) {
+ const auto& map_it = the_map.find(elem);
+ if (map_it != the_map.end())
+ elem = map_it->second;
+ }
+}
+
bool InplaceGenerator::GenerateOperations(
const PayloadGenerationConfig& config,
int data_file_fd,
@@ -718,16 +723,16 @@
// Temporary list of operations used to construct the dependency graph.
vector<AnnotatedOperation> aops;
TEST_AND_RETURN_FALSE(
- DeltaDiffGenerator::DeltaReadFilesystem(&aops,
- config.source.rootfs.path,
- config.target.rootfs.path,
- old_fs.get(),
- new_fs.get(),
- chunk_blocks,
- data_file_fd,
- data_file_size,
- true, // skip_block_0
- false)); // src_ops_allowed
+ diff_utils::DeltaReadFilesystem(&aops,
+ config.source.rootfs.path,
+ config.target.rootfs.path,
+ old_fs.get(),
+ new_fs.get(),
+ chunk_blocks,
+ data_file_fd,
+ data_file_size,
+ true, // skip_block_0
+ false)); // src_ops_allowed
// Convert the rootfs operations to the graph.
Graph graph;
CheckGraph(graph);
@@ -751,17 +756,16 @@
}
// Read kernel partition
- TEST_AND_RETURN_FALSE(
- DeltaDiffGenerator::DeltaCompressKernelPartition(
- config.source.kernel.path,
- config.target.kernel.path,
- config.source.kernel.size,
- config.target.kernel.size,
- config.block_size,
- kernel_ops,
- data_file_fd,
- data_file_size,
- false)); // src_ops_allowed
+ TEST_AND_RETURN_FALSE(diff_utils::DeltaCompressKernelPartition(
+ config.source.kernel.path,
+ config.target.kernel.path,
+ config.source.kernel.size,
+ config.target.kernel.size,
+ config.block_size,
+ kernel_ops,
+ data_file_fd,
+ data_file_size,
+ false)); // src_ops_allowed
LOG(INFO) << "done reading kernel";
CheckGraph(graph);
@@ -790,7 +794,7 @@
}
// Re-add the operation for the block 0.
- TEST_AND_RETURN_FALSE(DeltaDiffGenerator::DeltaReadFile(
+ TEST_AND_RETURN_FALSE(diff_utils::DeltaReadFile(
rootfs_ops,
config.source.rootfs.path,
config.target.rootfs.path,
diff --git a/payload_generator/inplace_generator.h b/payload_generator/inplace_generator.h
index 90c1fd4..158e364 100644
--- a/payload_generator/inplace_generator.h
+++ b/payload_generator/inplace_generator.h
@@ -5,6 +5,7 @@
#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
#define UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
+#include <map>
#include <set>
#include <string>
#include <vector>
@@ -187,6 +188,12 @@
const DeltaArchiveManifest_InstallOperation operation,
const std::string& op_name);
+ // Apply the transformation stored in |the_map| to the |collection| vector
+ // replacing the map keys found in |collection| with its associated value in
+ // |the_map|.
+ static void ApplyMap(std::vector<uint64_t>* collection,
+ const std::map<uint64_t, uint64_t>& the_map);
+
// Generate the update payload operations for the kernel and rootfs using
// only operations that read from the target and/or write to the target,
// hence, applying the payload "in-place" in the target partition. This method
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
index b988787..5de0df9 100644
--- a/payload_generator/inplace_generator_unittest.cc
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -4,6 +4,7 @@
#include "update_engine/payload_generator/inplace_generator.h"
+#include <map>
#include <set>
#include <sstream>
#include <string>
@@ -22,6 +23,7 @@
#include "update_engine/test_utils.h"
#include "update_engine/utils.h"
+using std::map;
using std::set;
using std::string;
using std::stringstream;
@@ -45,8 +47,8 @@
DeltaArchiveManifest_InstallOperation_Type type) {
out->op.set_type(type);
out->file_name = path;
- DeltaDiffGenerator::StoreExtents(src_extents, out->op.mutable_src_extents());
- DeltaDiffGenerator::StoreExtents(dst_extents, out->op.mutable_dst_extents());
+ StoreExtents(src_extents, out->op.mutable_src_extents());
+ StoreExtents(dst_extents, out->op.mutable_dst_extents());
}
vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
@@ -148,7 +150,7 @@
AppendBlockToExtents(&extents, 3);
AppendBlockToExtents(&extents, 5);
AppendBlockToExtents(&extents, 7);
- DeltaDiffGenerator::StoreExtents(extents,
+ StoreExtents(extents,
graph.back().op.mutable_src_extents());
blocks[3].reader = graph.size() - 1;
blocks[5].reader = graph.size() - 1;
@@ -159,7 +161,7 @@
AppendBlockToExtents(&extents, 1);
AppendBlockToExtents(&extents, 2);
AppendBlockToExtents(&extents, 4);
- DeltaDiffGenerator::StoreExtents(extents,
+ StoreExtents(extents,
graph.back().op.mutable_dst_extents());
blocks[1].writer = graph.size() - 1;
blocks[2].writer = graph.size() - 1;
@@ -173,7 +175,7 @@
AppendBlockToExtents(&extents, 1);
AppendBlockToExtents(&extents, 2);
AppendBlockToExtents(&extents, 4);
- DeltaDiffGenerator::StoreExtents(extents,
+ StoreExtents(extents,
graph.back().op.mutable_src_extents());
blocks[1].reader = graph.size() - 1;
blocks[2].reader = graph.size() - 1;
@@ -184,7 +186,7 @@
AppendBlockToExtents(&extents, 3);
AppendBlockToExtents(&extents, 5);
AppendBlockToExtents(&extents, 6);
- DeltaDiffGenerator::StoreExtents(extents,
+ StoreExtents(extents,
graph.back().op.mutable_dst_extents());
blocks[3].writer = graph.size() - 1;
blocks[5].writer = graph.size() - 1;
@@ -501,4 +503,16 @@
EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
}
+TEST_F(InplaceGeneratorTest, ApplyMapTest) {
+ vector<uint64_t> collection = {1, 2, 3, 4, 6};
+ vector<uint64_t> expected_values = {1, 2, 5, 4, 8};
+ map<uint64_t, uint64_t> value_map;
+ value_map[3] = 5;
+ value_map[6] = 8;
+ value_map[5] = 10;
+
+ InplaceGenerator::ApplyMap(&collection, value_map);
+ EXPECT_EQ(expected_values, collection);
+}
+
} // namespace chromeos_update_engine
diff --git a/payload_generator/payload_file.cc b/payload_generator/payload_file.cc
new file mode 100644
index 0000000..fe453a2
--- /dev/null
+++ b/payload_generator/payload_file.cc
@@ -0,0 +1,319 @@
+// 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/payload_file.h"
+
+#include <algorithm>
+
+#include "update_engine/file_writer.h"
+#include "update_engine/omaha_hash_calculator.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
+#include "update_engine/payload_generator/payload_signer.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+const uint64_t kMajorVersionNumber = 1;
+
+static const char* kInstallOperationTypes[] = {
+ "REPLACE",
+ "REPLACE_BZ",
+ "MOVE",
+ "BSDIFF",
+ "SOURCE_COPY",
+ "SOURCE_BSDIFF"
+};
+
+struct DeltaObject {
+ DeltaObject(const string& in_name, const int in_type, const off_t in_size)
+ : name(in_name),
+ type(in_type),
+ size(in_size) {}
+ bool operator <(const DeltaObject& object) const {
+ return (size != object.size) ? (size < object.size) : (name < object.name);
+ }
+ string name;
+ int type;
+ off_t size;
+};
+
+// Writes the uint64_t passed in in host-endian to the file as big-endian.
+// Returns true on success.
+bool WriteUint64AsBigEndian(FileWriter* writer, const uint64_t value) {
+ uint64_t value_be = htobe64(value);
+ TEST_AND_RETURN_FALSE(writer->Write(&value_be, sizeof(value_be)));
+ return true;
+}
+
+} // namespace
+
+const vector<PartitionName> PayloadFile::partition_disk_order_ = {
+ PartitionName::kRootfs,
+ PartitionName::kKernel,
+};
+
+bool PayloadFile::Init(const PayloadGenerationConfig& config) {
+ manifest_.set_minor_version(config.minor_version);
+
+ if (!config.source.ImageInfoIsEmpty())
+ *(manifest_.mutable_old_image_info()) = config.source.image_info;
+
+ if (!config.target.ImageInfoIsEmpty())
+ *(manifest_.mutable_new_image_info()) = config.target.image_info;
+
+ manifest_.set_block_size(config.block_size);
+
+ // Initialize the PartitionInfo objects if present.
+ if (!config.source.kernel.path.empty()) {
+ TEST_AND_RETURN_FALSE(diff_utils::InitializePartitionInfo(
+ config.source.kernel,
+ manifest_.mutable_old_kernel_info()));
+ }
+ TEST_AND_RETURN_FALSE(diff_utils::InitializePartitionInfo(
+ config.target.kernel,
+ manifest_.mutable_new_kernel_info()));
+ if (!config.source.rootfs.path.empty()) {
+ TEST_AND_RETURN_FALSE(diff_utils::InitializePartitionInfo(
+ config.source.rootfs,
+ manifest_.mutable_old_rootfs_info()));
+ }
+ TEST_AND_RETURN_FALSE(diff_utils::InitializePartitionInfo(
+ config.target.rootfs,
+ manifest_.mutable_new_rootfs_info()));
+ return true;
+}
+
+void PayloadFile::AddPartitionOperations(
+ PartitionName name,
+ const vector<AnnotatedOperation>& aops) {
+ aops_map_[name].insert(aops_map_[name].end(), aops.begin(), aops.end());
+}
+
+bool PayloadFile::WritePayload(const string& payload_file,
+ const string& data_blobs_path,
+ const string& private_key_path,
+ uint64_t* medatata_size_out) {
+ // Reorder the data blobs with the manifest_.
+ string ordered_blobs_path;
+ TEST_AND_RETURN_FALSE(utils::MakeTempFile(
+ "CrAU_temp_data.ordered.XXXXXX",
+ &ordered_blobs_path,
+ nullptr));
+ ScopedPathUnlinker ordered_blobs_unlinker(ordered_blobs_path);
+ TEST_AND_RETURN_FALSE(ReorderDataBlobs(data_blobs_path, ordered_blobs_path));
+
+ // Copy the operations from the aops_map_ to the manifest.
+ manifest_.clear_install_operations();
+ manifest_.clear_kernel_install_operations();
+ for (PartitionName name : partition_disk_order_) {
+ for (const AnnotatedOperation& aop : aops_map_[name]) {
+ if (name == PartitionName::kKernel) {
+ *manifest_.add_kernel_install_operations() = aop.op;
+ } else {
+ *manifest_.add_install_operations() = aop.op;
+ }
+ }
+ }
+
+ // Check that install op blobs are in order.
+ uint64_t next_blob_offset = 0;
+ {
+ for (int i = 0; i < (manifest_.install_operations_size() +
+ manifest_.kernel_install_operations_size()); i++) {
+ DeltaArchiveManifest_InstallOperation* op =
+ i < manifest_.install_operations_size() ?
+ manifest_.mutable_install_operations(i) :
+ manifest_.mutable_kernel_install_operations(
+ i - manifest_.install_operations_size());
+ if (op->has_data_offset()) {
+ if (op->data_offset() != next_blob_offset) {
+ LOG(FATAL) << "bad blob offset! " << op->data_offset() << " != "
+ << next_blob_offset;
+ }
+ next_blob_offset += op->data_length();
+ }
+ }
+ }
+
+ // Signatures appear at the end of the blobs. Note the offset in the
+ // manifest_.
+ if (!private_key_path.empty()) {
+ uint64_t signature_blob_length = 0;
+ TEST_AND_RETURN_FALSE(
+ PayloadSigner::SignatureBlobLength(vector<string>(1, private_key_path),
+ &signature_blob_length));
+ AddSignatureOp(next_blob_offset, signature_blob_length, &manifest_);
+ }
+
+ // Serialize protobuf
+ string serialized_manifest;
+ TEST_AND_RETURN_FALSE(manifest_.AppendToString(&serialized_manifest));
+
+ LOG(INFO) << "Writing final delta file header...";
+ DirectFileWriter writer;
+ TEST_AND_RETURN_FALSE_ERRNO(writer.Open(payload_file.c_str(),
+ O_WRONLY | O_CREAT | O_TRUNC,
+ 0644) == 0);
+ ScopedFileWriterCloser writer_closer(&writer);
+
+ // Write header
+ TEST_AND_RETURN_FALSE(writer.Write(kDeltaMagic, strlen(kDeltaMagic)));
+
+ // Write major version number
+ TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer, kMajorVersionNumber));
+
+ // Write protobuf length
+ TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer,
+ serialized_manifest.size()));
+
+ // Write protobuf
+ LOG(INFO) << "Writing final delta file protobuf... "
+ << serialized_manifest.size();
+ TEST_AND_RETURN_FALSE(writer.Write(serialized_manifest.data(),
+ serialized_manifest.size()));
+
+ // Append the data blobs
+ LOG(INFO) << "Writing final delta file data blobs...";
+ int blobs_fd = open(ordered_blobs_path.c_str(), O_RDONLY, 0);
+ ScopedFdCloser blobs_fd_closer(&blobs_fd);
+ TEST_AND_RETURN_FALSE(blobs_fd >= 0);
+ for (;;) {
+ vector<char> buf(1024 * 1024);
+ ssize_t rc = read(blobs_fd, buf.data(), buf.size());
+ if (0 == rc) {
+ // EOF
+ break;
+ }
+ TEST_AND_RETURN_FALSE_ERRNO(rc > 0);
+ TEST_AND_RETURN_FALSE(writer.Write(buf.data(), rc));
+ }
+
+ // Write signature blob.
+ if (!private_key_path.empty()) {
+ LOG(INFO) << "Signing the update...";
+ chromeos::Blob signature_blob;
+ TEST_AND_RETURN_FALSE(PayloadSigner::SignPayload(
+ payload_file,
+ vector<string>(1, private_key_path),
+ &signature_blob));
+ TEST_AND_RETURN_FALSE(writer.Write(signature_blob.data(),
+ signature_blob.size()));
+ }
+
+ *medatata_size_out =
+ strlen(kDeltaMagic) + 2 * sizeof(uint64_t) + serialized_manifest.size();
+ ReportPayloadUsage(*medatata_size_out);
+ return true;
+}
+
+bool PayloadFile::ReorderDataBlobs(
+ const string& data_blobs_path,
+ const string& new_data_blobs_path) {
+ int in_fd = open(data_blobs_path.c_str(), O_RDONLY, 0);
+ TEST_AND_RETURN_FALSE_ERRNO(in_fd >= 0);
+ ScopedFdCloser in_fd_closer(&in_fd);
+
+ DirectFileWriter writer;
+ TEST_AND_RETURN_FALSE(
+ writer.Open(new_data_blobs_path.c_str(),
+ O_WRONLY | O_TRUNC | O_CREAT,
+ 0644) == 0);
+ ScopedFileWriterCloser writer_closer(&writer);
+ uint64_t out_file_size = 0;
+
+ for (PartitionName name : partition_disk_order_) {
+ for (AnnotatedOperation& aop : aops_map_[name]) {
+ if (!aop.op.has_data_offset())
+ continue;
+ CHECK(aop.op.has_data_length());
+ chromeos::Blob buf(aop.op.data_length());
+ ssize_t rc = pread(in_fd, buf.data(), buf.size(), aop.op.data_offset());
+ TEST_AND_RETURN_FALSE(rc == static_cast<ssize_t>(buf.size()));
+
+ // Add the hash of the data blobs for this operation
+ TEST_AND_RETURN_FALSE(AddOperationHash(&aop.op, buf));
+
+ aop.op.set_data_offset(out_file_size);
+ TEST_AND_RETURN_FALSE(writer.Write(buf.data(), buf.size()));
+ out_file_size += buf.size();
+ }
+ }
+ return true;
+}
+
+bool PayloadFile::AddOperationHash(
+ DeltaArchiveManifest_InstallOperation* op,
+ const chromeos::Blob& buf) {
+ OmahaHashCalculator hasher;
+ TEST_AND_RETURN_FALSE(hasher.Update(buf.data(), buf.size()));
+ TEST_AND_RETURN_FALSE(hasher.Finalize());
+ const chromeos::Blob& hash = hasher.raw_hash();
+ op->set_data_sha256_hash(hash.data(), hash.size());
+ return true;
+}
+
+void PayloadFile::ReportPayloadUsage(uint64_t metadata_size) const {
+ vector<DeltaObject> objects;
+ off_t total_size = 0;
+
+ for (PartitionName name : partition_disk_order_) {
+ const auto& partition_aops = aops_map_.find(name);
+ if (partition_aops == aops_map_.end())
+ continue;
+ for (const AnnotatedOperation& aop : partition_aops->second) {
+ objects.push_back(DeltaObject(aop.name,
+ aop.op.type(),
+ aop.op.data_length()));
+ total_size += aop.op.data_length();
+ }
+ }
+
+ objects.push_back(DeltaObject("<manifest-metadata>",
+ -1,
+ metadata_size));
+ total_size += metadata_size;
+
+ std::sort(objects.begin(), objects.end());
+
+ static const char kFormatString[] = "%6.2f%% %10jd %-10s %s\n";
+ for (const DeltaObject& object : objects) {
+ fprintf(stderr, kFormatString,
+ object.size * 100.0 / total_size,
+ static_cast<intmax_t>(object.size),
+ object.type >= 0 ? kInstallOperationTypes[object.type] : "-",
+ object.name.c_str());
+ }
+ fprintf(stderr, kFormatString,
+ 100.0, static_cast<intmax_t>(total_size), "", "<total>");
+}
+
+void AddSignatureOp(uint64_t signature_blob_offset,
+ uint64_t signature_blob_length,
+ DeltaArchiveManifest* manifest) {
+ LOG(INFO) << "Making room for signature in file";
+ manifest->set_signatures_offset(signature_blob_offset);
+ LOG(INFO) << "set? " << manifest->has_signatures_offset();
+ // Add a dummy op at the end to appease older clients
+ DeltaArchiveManifest_InstallOperation* dummy_op =
+ manifest->add_kernel_install_operations();
+ dummy_op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ dummy_op->set_data_offset(signature_blob_offset);
+ manifest->set_signatures_offset(signature_blob_offset);
+ dummy_op->set_data_length(signature_blob_length);
+ manifest->set_signatures_size(signature_blob_length);
+ Extent* dummy_extent = dummy_op->add_dst_extents();
+ // Tell the dummy op to write this data to a big sparse hole
+ dummy_extent->set_start_block(kSparseHole);
+ dummy_extent->set_num_blocks((signature_blob_length + kBlockSize - 1) /
+ kBlockSize);
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/payload_file.h b/payload_generator/payload_file.h
new file mode 100644
index 0000000..150b0b0
--- /dev/null
+++ b/payload_generator/payload_file.h
@@ -0,0 +1,86 @@
+// 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_PAYLOAD_FILE_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_FILE_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/annotated_operation.h"
+#include "update_engine/payload_generator/payload_generation_config.h"
+#include "update_engine/update_metadata.pb.h"
+
+namespace chromeos_update_engine {
+
+// Class to handle the creation of a payload file. This class is the only one
+// dealing with writing the payload and its format, but has no logic about what
+// should be on it.
+class PayloadFile {
+ public:
+ // Initialize the payload file with the payload generation config. It computes
+ // required hashes of the requested partitions.
+ bool Init(const PayloadGenerationConfig& config);
+
+ // Sets the list of operations to the payload manifest. The operations
+ // reference a blob stored in the file provided to WritePayload().
+ void AddPartitionOperations(PartitionName name,
+ const std::vector<AnnotatedOperation>& aops);
+
+ // Write the payload to the |payload_file| file. The operations reference
+ // blobs in the |data_blobs_path| file and the blobs will be reordered in the
+ // payload file to match the order of the operations. The size of the metadata
+ // section of the payload is stored in |metadata_size_out|.
+ bool WritePayload(const std::string& payload_file,
+ const std::string& data_blobs_path,
+ const std::string& private_key_path,
+ uint64_t* medatata_size_out);
+
+ private:
+ FRIEND_TEST(PayloadFileTest, ReorderBlobsTest);
+
+ // Computes a SHA256 hash of the given buf and sets the hash value in the
+ // operation so that update_engine could verify. This hash should be set
+ // for all operations that have a non-zero data blob. One exception is the
+ // dummy operation for signature blob because the contents of the signature
+ // blob will not be available at payload creation time. So, update_engine will
+ // gracefully ignore the dummy signature operation.
+ static bool AddOperationHash(DeltaArchiveManifest_InstallOperation* op,
+ const chromeos::Blob& buf);
+
+ // Install operations in the manifest may reference data blobs, which
+ // are in data_blobs_path. This function creates a new data blobs file
+ // with the data blobs in the same order as the referencing install
+ // operations in the manifest. E.g. if manifest[0] has a data blob
+ // "X" at offset 1, manifest[1] has a data blob "Y" at offset 0,
+ // and data_blobs_path's file contains "YX", new_data_blobs_path
+ // will set to be a file that contains "XY".
+ bool ReorderDataBlobs(const std::string& data_blobs_path,
+ const std::string& new_data_blobs_path);
+
+ // Print in stderr the Payload usage report.
+ void ReportPayloadUsage(uint64_t metadata_size) const;
+
+ // The list of partitions in the order their blobs should appear in the
+ // payload file.
+ static const std::vector<PartitionName> partition_disk_order_;
+
+ DeltaArchiveManifest manifest_;
+
+ std::map<PartitionName, std::vector<AnnotatedOperation>> aops_map_;
+};
+
+// Adds a dummy operation that points to a signature blob located at the
+// specified offset/length.
+void AddSignatureOp(uint64_t signature_blob_offset,
+ uint64_t signature_blob_length,
+ DeltaArchiveManifest* manifest);
+
+} // namespace chromeos_update_engine
+
+#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_FILE_H_
diff --git a/payload_generator/payload_file_unittest.cc b/payload_generator/payload_file_unittest.cc
new file mode 100644
index 0000000..1d9661f
--- /dev/null
+++ b/payload_generator/payload_file_unittest.cc
@@ -0,0 +1,84 @@
+// 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/payload_file.h"
+
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_ranges.h"
+#include "update_engine/test_utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class PayloadFileTest : public ::testing::Test {
+ protected:
+ PayloadFile payload_;
+};
+
+TEST_F(PayloadFileTest, ReorderBlobsTest) {
+ string orig_blobs;
+ EXPECT_TRUE(utils::MakeTempFile("ReorderBlobsTest.orig.XXXXXX", &orig_blobs,
+ nullptr));
+ ScopedPathUnlinker orig_blobs_unlinker(orig_blobs);
+
+ // The operations have three blob and one gap (the whitespace):
+ // Rootfs operation 1: [8, 3] bcd
+ // Rootfs operation 2: [7, 1] a
+ // Kernel operation 1: [0, 6] kernel
+ string orig_data = "kernel abcd";
+ EXPECT_TRUE(
+ utils::WriteFile(orig_blobs.c_str(), orig_data.data(), orig_data.size()));
+
+ string new_blobs;
+ EXPECT_TRUE(
+ utils::MakeTempFile("ReorderBlobsTest.new.XXXXXX", &new_blobs, nullptr));
+ ScopedPathUnlinker new_blobs_unlinker(new_blobs);
+
+ vector<AnnotatedOperation> aops;
+ AnnotatedOperation aop;
+ aop.op.set_data_offset(8);
+ aop.op.set_data_length(3);
+ aops.push_back(aop);
+
+ aop.op.set_data_offset(7);
+ aop.op.set_data_length(1);
+ aops.push_back(aop);
+ payload_.AddPartitionOperations(PartitionName::kRootfs, aops);
+
+ aop.op.set_data_offset(0);
+ aop.op.set_data_length(6);
+ aops = {aop};
+ payload_.AddPartitionOperations(PartitionName::kKernel, aops);
+
+ EXPECT_TRUE(payload_.ReorderDataBlobs(orig_blobs, new_blobs));
+
+ const vector<AnnotatedOperation>& rootfs_aops =
+ payload_.aops_map_[PartitionName::kRootfs];
+ const vector<AnnotatedOperation>& kernel_aops =
+ payload_.aops_map_[PartitionName::kKernel];
+ string new_data;
+ EXPECT_TRUE(utils::ReadFile(new_blobs, &new_data));
+ // Kernel blobs should appear at the end.
+ EXPECT_EQ("bcdakernel", new_data);
+
+ EXPECT_EQ(2, rootfs_aops.size());
+ EXPECT_EQ(0, rootfs_aops[0].op.data_offset());
+ EXPECT_EQ(3, rootfs_aops[0].op.data_length());
+ EXPECT_EQ(3, rootfs_aops[1].op.data_offset());
+ EXPECT_EQ(1, rootfs_aops[1].op.data_length());
+
+ EXPECT_EQ(1, kernel_aops.size());
+ EXPECT_EQ(4, kernel_aops[0].op.data_offset());
+ EXPECT_EQ(6, kernel_aops[0].op.data_length());
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/payload_generation_config.h b/payload_generator/payload_generation_config.h
index af9afb5..0f002e1 100644
--- a/payload_generator/payload_generation_config.h
+++ b/payload_generator/payload_generation_config.h
@@ -14,7 +14,15 @@
namespace chromeos_update_engine {
+// The list different kind of partitions supported by the updater.
+enum class PartitionName {
+ kKernel,
+ kRootfs,
+};
+
struct PartitionConfig {
+ explicit PartitionConfig(PartitionName name) : name(name) {}
+
// Returns whether the PartitionConfig is not an empty image and all the
// fields are set correctly to a valid image file.
bool ValidateExists() const;
@@ -30,6 +38,8 @@
// the source image, and the size of that data it should generate for the
// target image.
uint64_t size = 0;
+
+ PartitionName name;
};
// The ImageConfig struct describes a pair of binaries kernel and rootfs and the
@@ -60,8 +70,8 @@
ImageInfo image_info;
// The updated partitions.
- PartitionConfig rootfs;
- PartitionConfig kernel;
+ PartitionConfig rootfs = PartitionConfig{PartitionName::kRootfs};
+ PartitionConfig kernel = PartitionConfig{PartitionName::kKernel};
};
// The PayloadGenerationConfig struct encapsulates all the configuration to
diff --git a/payload_generator/payload_signer.cc b/payload_generator/payload_signer.cc
index eec8d7a..8c3bc28 100644
--- a/payload_generator/payload_signer.cc
+++ b/payload_generator/payload_signer.cc
@@ -11,7 +11,7 @@
#include <openssl/pem.h>
#include "update_engine/omaha_hash_calculator.h"
-#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/payload_file.h"
#include "update_engine/payload_verifier.h"
#include "update_engine/subprocess.h"
#include "update_engine/update_metadata.pb.h"
@@ -90,9 +90,9 @@
LOG(INFO) << "Matching signature sizes already present.";
} else {
// Updates the manifest to include the signature operation.
- DeltaDiffGenerator::AddSignatureOp(payload.size() - metadata_size,
- signature_blob_size,
- &manifest);
+ AddSignatureOp(payload.size() - metadata_size,
+ signature_blob_size,
+ &manifest);
// Updates the payload to include the new manifest.
string serialized_manifest;
diff --git a/update_engine.gyp b/update_engine.gyp
index e9e5a63..9294f66 100644
--- a/update_engine.gyp
+++ b/update_engine.gyp
@@ -266,9 +266,11 @@
],
},
'sources': [
+ 'payload_generator/ab_generator.cc',
'payload_generator/annotated_operation.cc',
'payload_generator/cycle_breaker.cc',
'payload_generator/delta_diff_generator.cc',
+ 'payload_generator/delta_diff_utils.cc',
'payload_generator/ext2_filesystem.cc',
'payload_generator/extent_ranges.cc',
'payload_generator/extent_utils.cc',
@@ -276,6 +278,7 @@
'payload_generator/graph_types.cc',
'payload_generator/graph_utils.cc',
'payload_generator/inplace_generator.cc',
+ 'payload_generator/payload_file.cc',
'payload_generator/payload_generation_config.cc',
'payload_generator/payload_signer.cc',
'payload_generator/raw_filesystem.cc',
@@ -380,8 +383,9 @@
'omaha_request_params_unittest.cc',
'omaha_response_handler_action_unittest.cc',
'p2p_manager_unittest.cc',
+ 'payload_generator/ab_generator_unittest.cc',
'payload_generator/cycle_breaker_unittest.cc',
- 'payload_generator/delta_diff_generator_unittest.cc',
+ 'payload_generator/delta_diff_utils_unittest.cc',
'payload_generator/ext2_filesystem_unittest.cc',
'payload_generator/extent_ranges_unittest.cc',
'payload_generator/extent_utils_unittest.cc',
@@ -390,6 +394,7 @@
'payload_generator/graph_utils_unittest.cc',
'payload_generator/inplace_generator_unittest.cc',
'payload_generator/payload_signer_unittest.cc',
+ 'payload_generator/payload_file_unittest.cc',
'payload_generator/tarjan_unittest.cc',
'payload_generator/topological_sort_unittest.cc',
'payload_generator/verity_utils_unittest.cc',
diff --git a/utils.h b/utils.h
index bd3fda6..6a9e065 100644
--- a/utils.h
+++ b/utils.h
@@ -297,19 +297,6 @@
}
}
-template<typename ValueType>
-void ApplyMap(std::vector<ValueType>* collection,
- const std::map<ValueType, ValueType>& the_map) {
- for (typename std::vector<ValueType>::iterator it = collection->begin();
- it != collection->end(); ++it) {
- typename std::map<ValueType, ValueType>::const_iterator map_it =
- the_map.find(*it);
- if (map_it != the_map.end()) {
- *it = map_it->second;
- }
- }
-}
-
// Cgroups cpu shares constants. 1024 is the default shares a standard process
// gets and 2 is the minimum value. We set High as a value that gives the
// update-engine 2x the cpu share of a standard process.
diff --git a/utils_unittest.cc b/utils_unittest.cc
index 308345a..0d82f61 100644
--- a/utils_unittest.cc
+++ b/utils_unittest.cc
@@ -237,24 +237,6 @@
}
}
-TEST(UtilsTest, ApplyMapTest) {
- int initial_values[] = {1, 2, 3, 4, 6};
- vector<int> collection(std::begin(initial_values), std::end(initial_values));
- EXPECT_EQ(arraysize(initial_values), collection.size());
- int expected_values[] = {1, 2, 5, 4, 8};
- map<int, int> value_map;
- value_map[3] = 5;
- value_map[6] = 8;
- value_map[5] = 10;
-
- utils::ApplyMap(&collection, value_map);
-
- size_t index = 0;
- for (const int value : collection) {
- EXPECT_EQ(expected_values[index++], value);
- }
-}
-
TEST(UtilsTest, RunAsRootGetFilesystemSizeTest) {
string img;
EXPECT_TRUE(utils::MakeTempFile("img.XXXXXX", &img, nullptr));