update_engine: Prevent the InplaceGenerator to add MOVEs to block 0.
While we normally don't generate MOVE operations to/from the block 0,
the cycle breaker logic can use the block 0 as scratch space, creating
MOVE operations to and from the block 0.
This patch prevents it from picking the block 0 as scratch space and
logs a message when that would happend.
BUG=chromium:480751,chromium:500423
TEST=Added unittest.
Change-Id: I91f1b3c426a9d06aae5b685e2e901c7e448d8677
Reviewed-on: https://chromium-review.googlesource.com/286623
Reviewed-by: Gilad Arnold <garnold@chromium.org>
Tested-by: Alex Deymo <deymo@chromium.org>
Commit-Queue: Alex Deymo <deymo@chromium.org>
diff --git a/payload_generator/ab_generator.cc b/payload_generator/ab_generator.cc
index 2b379e1..8352927 100644
--- a/payload_generator/ab_generator.cc
+++ b/payload_generator/ab_generator.cc
@@ -38,7 +38,6 @@
chunk_blocks,
data_file_fd,
data_file_size,
- false, // skip_block_0
true)); // src_ops_allowed
LOG(INFO) << "done reading normal files";
@@ -50,7 +49,6 @@
chunk_blocks,
data_file_fd,
data_file_size,
- false, // skip_block_0
true)); // src_ops_allowed
LOG(INFO) << "done reading kernel";
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
index cfeb867..35f3e7f 100644
--- a/payload_generator/delta_diff_utils.cc
+++ b/payload_generator/delta_diff_utils.cc
@@ -145,21 +145,10 @@
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);
- }
-
TEST_AND_RETURN_FALSE(DeltaMovedAndZeroBlocks(
aops,
old_part.path,
diff --git a/payload_generator/delta_diff_utils.h b/payload_generator/delta_diff_utils.h
index 0c899a8..ee8979c 100644
--- a/payload_generator/delta_diff_utils.h
+++ b/payload_generator/delta_diff_utils.h
@@ -31,7 +31,6 @@
off_t chunk_blocks,
int data_fd,
off_t* data_file_size,
- bool skip_block_0,
bool src_ops_allowed);
// Create operations in |aops| for identical blocks that moved around in the old
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index a142449..a7f7b55 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -393,6 +393,14 @@
edge_i != edge_e; ++edge_i) {
ranges.SubtractExtents(edge_i->second.extents);
}
+
+ // Prevent using the block 0 as scratch space due to crbug.com/480751.
+ if (ranges.ContainsBlock(0)) {
+ LOG(INFO) << "Removing block 0 from the selected scratch range in vertex "
+ << i;
+ ranges.SubtractBlock(0);
+ }
+
if (ranges.blocks() == 0)
continue;
@@ -784,6 +792,38 @@
return true;
}
+bool InplaceGenerator::GenerateOperationsForPartition(
+ const PartitionConfig& old_part,
+ const PartitionConfig& new_part,
+ uint64_t partition_size,
+ size_t block_size,
+ off_t chunk_blocks,
+ int data_file_fd,
+ off_t* data_file_size,
+ vector<AnnotatedOperation>* aops) {
+ const string part_name = PartitionNameString(new_part.name);
+ LOG(INFO) << "Delta compressing " << part_name << " partition...";
+ TEST_AND_RETURN_FALSE(
+ diff_utils::DeltaReadPartition(aops,
+ old_part,
+ new_part,
+ chunk_blocks,
+ data_file_fd,
+ data_file_size,
+ false)); // src_ops_allowed
+ LOG(INFO) << "Done reading " << part_name;
+
+ TEST_AND_RETURN_FALSE(
+ ResolveReadAfterWriteDependencies(new_part,
+ partition_size,
+ block_size,
+ data_file_fd,
+ data_file_size,
+ aops));
+ LOG(INFO) << "Done reordering " << part_name;
+ return true;
+}
+
bool InplaceGenerator::GenerateOperations(
const PayloadGenerationConfig& config,
int data_file_fd,
@@ -793,65 +833,25 @@
off_t chunk_blocks = (config.chunk_size == -1 ? -1 :
config.chunk_size / config.block_size);
- // Temporary list of operations used to construct the dependency graph.
- LOG(INFO) << "Delta compressing rootfs partition...";
- TEST_AND_RETURN_FALSE(
- diff_utils::DeltaReadPartition(rootfs_ops,
- config.source.rootfs,
- config.target.rootfs,
- chunk_blocks,
- data_file_fd,
- data_file_size,
- true, // skip_block_0
- false)); // src_ops_allowed
- LOG(INFO) << "Done reading rootfs";
-
- // Read kernel partition
- LOG(INFO) << "Delta compressing kernel partition...";
- // It is safe to not skip the block 0 since we will not be using the cycle
- // breaking algorithm on this list of operations as we expect no cycles here.
- TEST_AND_RETURN_FALSE(
- diff_utils::DeltaReadPartition(kernel_ops,
- config.source.kernel,
- config.target.kernel,
- chunk_blocks,
- data_file_fd,
- data_file_size,
- false, // skip_block_0
- false)); // src_ops_allowed
- LOG(INFO) << "Done reading kernel";
-
- TEST_AND_RETURN_FALSE(
- ResolveReadAfterWriteDependencies(config.target.rootfs,
- config.rootfs_partition_size,
- config.block_size,
- data_file_fd,
- data_file_size,
- rootfs_ops));
- LOG(INFO) << "Done reordering rootfs";
-
- // The kernel partition uses the whole partition as the "filesystem_size".
- TEST_AND_RETURN_FALSE(
- ResolveReadAfterWriteDependencies(config.target.kernel,
- config.target.kernel.size,
- config.block_size,
- data_file_fd,
- data_file_size,
- kernel_ops));
- LOG(INFO) << "Done reordering kernel";
-
- // Re-add the operation for the block 0.
- TEST_AND_RETURN_FALSE(diff_utils::DeltaReadFile(
- rootfs_ops,
- config.source.rootfs.path,
- config.target.rootfs.path,
- vector<Extent>{ExtentForRange(0, 1)},
- vector<Extent>{ExtentForRange(0, 1)},
- "<block-0>", // operation name
- -1, // chunk_blocks
+ TEST_AND_RETURN_FALSE(GenerateOperationsForPartition(
+ config.source.rootfs,
+ config.target.rootfs,
+ config.rootfs_partition_size,
+ config.block_size,
+ chunk_blocks,
data_file_fd,
data_file_size,
- false)); // src_ops_allowed
+ rootfs_ops));
+
+ TEST_AND_RETURN_FALSE(GenerateOperationsForPartition(
+ config.source.kernel,
+ config.target.kernel,
+ config.target.kernel.size, // kernel "filesystem" is the whole partition.
+ config.block_size,
+ chunk_blocks,
+ data_file_fd,
+ data_file_size,
+ kernel_ops));
return true;
}
diff --git a/payload_generator/inplace_generator.h b/payload_generator/inplace_generator.h
index 3f8fe50..0c9fc2a 100644
--- a/payload_generator/inplace_generator.h
+++ b/payload_generator/inplace_generator.h
@@ -211,6 +211,23 @@
off_t* data_file_size,
std::vector<AnnotatedOperation>* aops);
+ // Generates the list of operations to update inplace from the partition
+ // |old_part| to |new_part|. The |partition_size| should be at least
+ // |new_part.size| and any extra space there could be used as scratch space.
+ // The operations generated will not write more than |chunk_blocks| blocks.
+ // The new operations will create blobs in |data_file_fd| and update
+ // the file size pointed by |data_file_size| if needed.
+ // On success, stores the new operations in |aops| and returns true.
+ static bool GenerateOperationsForPartition(
+ const PartitionConfig& old_part,
+ const PartitionConfig& new_part,
+ uint64_t partition_size,
+ size_t block_size,
+ off_t chunk_blocks,
+ int data_file_fd,
+ off_t* data_file_size,
+ std::vector<AnnotatedOperation>* aops);
+
// 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 65fb132..0c22664 100644
--- a/payload_generator/inplace_generator_unittest.cc
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -11,8 +11,10 @@
#include <utility>
#include <vector>
+#include <base/format_macros.h>
#include <base/logging.h>
#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
#include <gtest/gtest.h>
#include "update_engine/payload_generator/cycle_breaker.h"
@@ -94,6 +96,29 @@
} // namespace
class InplaceGeneratorTest : public ::testing::Test {
+ protected:
+ // Initialize |blob_path_|, |blob_file_size_| and |blob_file_fd_| variables
+ // with a new blob file. The file is closed and removed automatically when
+ // the test finishes.
+ void CreateBlobFile() {
+ // blob_fd_closer_ takes a pointer to blob_fd_. Make sure we destroy a
+ // previous instance before overriding blob_fd_.
+ blob_fd_closer_.reset();
+ EXPECT_TRUE(utils::MakeTempFile(
+ "InplaceGenerator_blob_file.XXXXXX", &blob_path_, &blob_fd_));
+ blob_path_unlinker_.reset(new ScopedPathUnlinker(blob_path_));
+ blob_fd_closer_.reset(new ScopedFdCloser(&blob_fd_));
+ blob_file_size_ = 0;
+ EXPECT_GE(blob_fd_, 0);
+ }
+
+ // Blob file name, file descriptor and file size used to store operation
+ // blobs.
+ string blob_path_;
+ int blob_fd_{-1};
+ off_t blob_file_size_{0};
+ std::unique_ptr<ScopedPathUnlinker> blob_path_unlinker_;
+ std::unique_ptr<ScopedFdCloser> blob_fd_closer_;
};
TEST_F(InplaceGeneratorTest, BlockDefaultValues) {
@@ -144,8 +169,7 @@
// Create nodes in graph
{
graph.resize(graph.size() + 1);
- graph.back().aop.op.set_type(
- DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ graph.back().aop.op.set_type(OP_MOVE);
// Reads from blocks 3, 5, 7
vector<Extent> extents;
AppendBlockToExtents(&extents, 3);
@@ -168,8 +192,7 @@
}
{
graph.resize(graph.size() + 1);
- graph.back().aop.op.set_type(
- DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ graph.back().aop.op.set_type(OP_MOVE);
// Reads from blocks 1, 2, 4
vector<Extent> extents;
AppendBlockToExtents(&extents, 1);
@@ -209,8 +232,7 @@
EXPECT_EQ(3, graph.size());
// Check new node in graph:
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
- graph.back().aop.op.type());
+ EXPECT_EQ(OP_MOVE, graph.back().aop.op.type());
EXPECT_EQ(2, graph.back().aop.op.src_extents_size());
EXPECT_EQ(1, graph.back().aop.op.dst_extents_size());
EXPECT_EQ(kTempBlockStart, graph.back().aop.op.dst_extents(0).start_block());
@@ -322,17 +344,11 @@
InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes,
&reverse_op_indexes);
- int fd;
- EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksReuseTest.XXXXXX",
- nullptr,
- &fd));
- ScopedFdCloser fd_closer(&fd);
- off_t data_file_size = 0;
-
+ CreateBlobFile();
EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph,
"/dev/zero",
- fd,
- &data_file_size,
+ blob_fd_,
+ &blob_file_size_,
&op_indexes,
&reverse_op_indexes,
cuts));
@@ -347,14 +363,13 @@
TEST_F(InplaceGeneratorTest, MoveAndSortFullOpsToBackTest) {
Graph graph(4);
graph[0].aop.name = "A";
- graph[0].aop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ graph[0].aop.op.set_type(OP_REPLACE);
graph[1].aop.name = "B";
- graph[1].aop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+ graph[1].aop.op.set_type(OP_BSDIFF);
graph[2].aop.name = "C";
- graph[2].aop.op.set_type(
- DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ graph[2].aop.op.set_type(OP_REPLACE_BZ);
graph[3].aop.name = "D";
- graph[3].aop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ graph[3].aop.op.set_type(OP_MOVE);
vector<Vertex::Index> vect(graph.size());
@@ -409,17 +424,11 @@
vector<Vertex::Index> final_order;
- int fd;
- EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksTestData.XXXXXX",
- nullptr,
- &fd));
- ScopedFdCloser fd_closer(&fd);
- off_t data_file_size = 0;
-
+ CreateBlobFile();
EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
"/dev/zero",
- fd,
- &data_file_size,
+ blob_fd_,
+ &blob_file_size_,
&final_order,
Vertex::kInvalidIndex));
@@ -493,8 +502,7 @@
TEST_F(InplaceGeneratorTest, CreateScratchNodeTest) {
Vertex vertex;
InplaceGenerator::CreateScratchNode(12, 34, &vertex);
- EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
- vertex.aop.op.type());
+ EXPECT_EQ(OP_REPLACE_BZ, vertex.aop.op.type());
EXPECT_EQ(0, vertex.aop.op.data_offset());
EXPECT_EQ(0, vertex.aop.op.data_length());
EXPECT_EQ(1, vertex.aop.op.dst_extents_size());
@@ -514,4 +522,76 @@
EXPECT_EQ(expected_values, collection);
}
+// We can't produce MOVE operations with a source or destination in the block 0.
+// This test checks that the cycle breaker procedure doesn't produce such
+// operations.
+TEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesAvoidMoveToZero) {
+ size_t block_size = 4096;
+ size_t num_blocks = 4;
+ vector<AnnotatedOperation> aops;
+
+ // Create a REPLACE_BZ for block 0, and a circular dependency among all other
+ // blocks. This situation would prefer to issue a MOVE to scratch space and
+ // the only available block is 0.
+ aops.emplace_back();
+ aops.back().name = base::StringPrintf("<bz-block-0>");
+ aops.back().op.set_type(
+ OP_REPLACE_BZ);
+ StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents());
+
+ for (size_t i = 1; i < num_blocks; i++) {
+ AnnotatedOperation aop;
+ aop.name = base::StringPrintf("<op-%" PRIuS ">", i);
+ aop.op.set_type(OP_BSDIFF);
+ StoreExtents({ExtentForRange(1 + i % (num_blocks - 1), 1)},
+ aop.op.mutable_src_extents());
+ StoreExtents({ExtentForRange(i, 1)}, aop.op.mutable_dst_extents());
+ aops.push_back(aop);
+ }
+
+ PartitionConfig part(PartitionName::kRootfs);
+ part.path = "/dev/zero";
+ part.size = num_blocks * block_size;
+
+ CreateBlobFile();
+
+ // We ran two tests here. The first one without enough blocks for the scratch
+ // space, forcing it to create a new full operation and the second case with
+ // one extra block in the partition that can be used for the move operation.
+ for (const auto part_blocks : vector<uint64_t>{num_blocks, num_blocks + 1}) {
+ SCOPED_TRACE(base::StringPrintf("Using partition_blocs=%" PRIu64,
+ part_blocks));
+ vector<AnnotatedOperation> result_aops = aops;
+ EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies(
+ part, part_blocks * block_size, block_size, blob_fd_, &blob_file_size_,
+ &result_aops));
+
+ size_t full_ops = 0;
+ for (const auto& aop : result_aops) {
+ if (aop.op.type() == OP_REPLACE || aop.op.type() == OP_REPLACE_BZ)
+ full_ops++;
+
+ if (aop.op.type() != OP_MOVE)
+ continue;
+ for (const Extent& extent : aop.op.src_extents()) {
+ EXPECT_NE(0, extent.start_block()) << "On src extents for aop: " << aop;
+ }
+ for (const Extent& extent : aop.op.dst_extents()) {
+ EXPECT_NE(0, extent.start_block()) << "On dst extents for aop: " << aop;
+ }
+ }
+
+ // If there's extra space in the partition, it should not use a new full
+ // operation for it.
+ EXPECT_EQ(part_blocks == num_blocks ? 2 : 1, full_ops);
+
+ if (HasNonfatalFailure()) {
+ LOG(INFO) << "Result operation list:";
+ for (const auto& aop : result_aops) {
+ LOG(INFO) << aop;
+ }
+ }
+ }
+}
+
} // namespace chromeos_update_engine
diff --git a/payload_generator/payload_generation_config.cc b/payload_generator/payload_generation_config.cc
index d58c9a1..0229b61 100644
--- a/payload_generator/payload_generation_config.cc
+++ b/payload_generator/payload_generation_config.cc
@@ -15,6 +15,16 @@
namespace chromeos_update_engine {
+std::string PartitionNameString(PartitionName name) {
+ switch (name) {
+ case PartitionName::kKernel:
+ return "kernel";
+ case PartitionName::kRootfs:
+ return "rootfs";
+ }
+ return "other";
+}
+
bool PartitionConfig::ValidateExists() const {
TEST_AND_RETURN_FALSE(!path.empty());
TEST_AND_RETURN_FALSE(utils::FileExists(path.c_str()));
@@ -36,17 +46,8 @@
if (!fs_interface) {
// Fall back to a RAW filesystem.
TEST_AND_RETURN_FALSE(size % kBlockSize == 0);
- std::string str_name = "other";
- switch (name) {
- case PartitionName::kKernel:
- str_name = "kernel";
- break;
- case PartitionName::kRootfs:
- str_name = "rootfs";
- break;
- }
fs_interface = RawFilesystem::Create(
- "<" + str_name + "-partition>",
+ "<" + PartitionNameString(name) + "-partition>",
kBlockSize,
size / kBlockSize);
}
diff --git a/payload_generator/payload_generation_config.h b/payload_generator/payload_generation_config.h
index f18055f..4057f75 100644
--- a/payload_generator/payload_generation_config.h
+++ b/payload_generator/payload_generation_config.h
@@ -22,6 +22,9 @@
kRootfs,
};
+// Return a string name for the PartitionName.
+std::string PartitionNameString(PartitionName name);
+
struct PartitionConfig {
explicit PartitionConfig(PartitionName name) : name(name) {}