update_engine: Split fragmented SOURCE_COPY ops.
Splits SOURCE_COPY operations with multiple destination extents into
individual SOURCE_COPY operations with only one destination extent each.
Also normalizes the extent lists before splitting the operation.
BUG=chromium:461641
TEST=`cros flash --src-image-to-delta` and unit tests.
CQ-DEPEND=CL:267360
Change-Id: I4d4fbe36165d98df7f36e4a1ddacc9b62ee97002
Reviewed-on: https://chromium-review.googlesource.com/267697
Reviewed-by: Alex Deymo <deymo@chromium.org>
Commit-Queue: Allie Wood <alliewood@chromium.org>
Trybot-Ready: Allie Wood <alliewood@chromium.org>
Tested-by: Allie Wood <alliewood@chromium.org>
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 50238e3..19e7aae 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -524,6 +524,9 @@
dst_extents.push_back(*dst_extent);
}
+ NormalizeExtents(&src_extents);
+ NormalizeExtents(&dst_extents);
+
// Figure out how many blocks we need to write to dst_extents.
uint64_t blocks_to_write = 0;
for (uint32_t i = 0; i < dst_extents.size(); i++)
@@ -1041,6 +1044,11 @@
rootfs_ops->back().op = unwritten_vertex.op;
rootfs_ops->back().name = unwritten_vertex.file_name;
}
+
+ // Fragment operations so we can sort them later.
+ FragmentOperations(rootfs_ops);
+ FragmentOperations(kernel_ops);
+
return true;
}
@@ -1308,4 +1316,86 @@
extents->end());
}
+void DeltaDiffGenerator::NormalizeExtents(vector<Extent>* extents) {
+ vector<Extent> new_extents;
+ for (const Extent& curr_ext : *extents) {
+ if (new_extents.empty()) {
+ new_extents.push_back(curr_ext);
+ continue;
+ }
+ Extent& last_ext = new_extents.back();
+ if (last_ext.start_block() + last_ext.num_blocks() ==
+ curr_ext.start_block()) {
+ // If the extents are touching, we want to combine them.
+ last_ext.set_num_blocks(last_ext.num_blocks() + curr_ext.num_blocks());
+ } else {
+ // Otherwise just include the extent as is.
+ new_extents.push_back(curr_ext);
+ }
+ }
+ *extents = new_extents;
+}
+
+void DeltaDiffGenerator::FragmentOperations(vector<AnnotatedOperation>* aops) {
+ vector<AnnotatedOperation> fragmented_aops;
+ for (const AnnotatedOperation& aop : *aops) {
+ if (aop.op.type() ==
+ DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) {
+ SplitSourceCopy(aop.op, &fragmented_aops);
+ } else {
+ fragmented_aops.push_back(aop);
+ }
+ }
+ *aops = fragmented_aops;
+}
+
+void DeltaDiffGenerator::SplitSourceCopy(
+ const DeltaArchiveManifest_InstallOperation& original_op,
+ vector<AnnotatedOperation>* result_aops) {
+ // 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;
+ 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.";
+ }
+}
+
}; // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
index 45039db..77bca6a 100644
--- a/payload_generator/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -227,6 +227,32 @@
// Takes a vector of extents and removes extents that begin in a sparse hole.
static void ClearSparseHoles(std::vector<Extent>* extents);
+ // 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)].
+ static void NormalizeExtents(std::vector<Extent>* extents);
+
+ // 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. This is only called when delta
+ // minor version is 2.
+ // Currently, this only modifies SOURCE_COPY operations, but it will
+ // eventually fragment all operations.
+ static void FragmentOperations(std::vector<AnnotatedOperation>* aops);
+
+ // Takes an SOURCE_COPY install operation, |original_op|, and adds one
+ // operation for each dst extent in |original_op| 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 void SplitSourceCopy(
+ const DeltaArchiveManifest_InstallOperation& original_op,
+ std::vector<AnnotatedOperation>* ops);
+
private:
DISALLOW_COPY_AND_ASSIGN(DeltaDiffGenerator);
};
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
index 4769242..99b5d08 100644
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -798,4 +798,78 @@
EXPECT_EQ(extents[1], ExtentForRange(29, 1));
}
+TEST_F(DeltaDiffGeneratorTest, NormalizeExtentsTest) {
+ vector<Extent> extents;
+ AddExtent(0, 3, &extents);
+ // Make sure it works when there's just one extent.
+ DeltaDiffGenerator::NormalizeExtents(&extents);
+ EXPECT_EQ(extents.size(), 1);
+ EXPECT_EQ(extents[0], ExtentForRange(0, 3));
+ AddExtent(3, 2, &extents);
+ AddExtent(5, 1, &extents);
+ AddExtent(8, 4, &extents);
+ AddExtent(13, 1, &extents);
+ AddExtent(14, 2, &extents);
+ DeltaDiffGenerator::NormalizeExtents(&extents);
+ EXPECT_EQ(extents.size(), 3);
+ EXPECT_EQ(extents[0], ExtentForRange(0, 6));
+ EXPECT_EQ(extents[1], ExtentForRange(8, 4));
+ EXPECT_EQ(extents[2], ExtentForRange(13, 3));
+}
+
+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);
+
+ vector<AnnotatedOperation> result_ops;
+ DeltaDiffGenerator::SplitSourceCopy(op, &result_ops);
+ EXPECT_EQ(result_ops.size(), 3);
+
+ 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().Get(0).start_block());
+ EXPECT_EQ(2, first_op.src_extents().Get(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().Get(0).start_block());
+ EXPECT_EQ(2, first_op.dst_extents().Get(0).num_blocks());
+
+ 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().Get(0).start_block());
+ EXPECT_EQ(1, second_op.src_extents().Get(0).num_blocks());
+ EXPECT_EQ(6, second_op.src_extents().Get(1).start_block());
+ EXPECT_EQ(1, second_op.src_extents().Get(1).num_blocks());
+ EXPECT_EQ(8, second_op.src_extents().Get(2).start_block());
+ EXPECT_EQ(1, second_op.src_extents().Get(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().Get(0).start_block());
+ EXPECT_EQ(3, second_op.dst_extents().Get(0).num_blocks());
+
+ 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().Get(0).start_block());
+ EXPECT_EQ(3, third_op.src_extents().Get(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().Get(0).start_block());
+ EXPECT_EQ(3, third_op.dst_extents().Get(0).num_blocks());
+}
+
} // namespace chromeos_update_engine