update_engine: Sort operations by output block.
After fragmenting SOURCE_COPY, REPLACE, and REPLACE_BZ operations,
payload generator will sort the operations by the start block of their
first destination extents. This reduces seeking when writing during
payload application.
BUG=chromium:461649
TEST=`cros flash --src-image-to-delta`, checking generated payloads
using `cros payload show --list_ops`.
CQ-DEPEND=CL:269130
Change-Id: I1e2d8e940cd0ce66a1ec62711653ba8b34b0f0a5
Reviewed-on: https://chromium-review.googlesource.com/269134
Reviewed-by: Alex Deymo <deymo@chromium.org>
Commit-Queue: 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 2d2aabc..3355c41 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -46,6 +46,7 @@
using std::max;
using std::min;
using std::set;
+using std::sort;
using std::string;
using std::unique_ptr;
using std::vector;
@@ -298,6 +299,19 @@
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::DeltaReadFiles(Graph* graph,
@@ -1043,7 +1057,6 @@
rootfs_ops->back().name = unwritten_vertex.file_name;
}
- // Fragment operations so we can sort them later.
TEST_AND_RETURN_FALSE(FragmentOperations(rootfs_ops,
config.target.rootfs_part,
data_file_fd,
@@ -1052,6 +1065,8 @@
config.target.rootfs_part,
data_file_fd,
data_file_size));
+ SortOperationsByDestination(rootfs_ops);
+ SortOperationsByDestination(kernel_ops);
return true;
}
@@ -1340,10 +1355,11 @@
*extents = new_extents;
}
-bool DeltaDiffGenerator::FragmentOperations(vector<AnnotatedOperation>* aops,
- const string& target_rootfs_part,
- int data_fd,
- off_t* data_file_size) {
+bool DeltaDiffGenerator::FragmentOperations(
+ vector<AnnotatedOperation>* aops,
+ const string& target_rootfs_part,
+ int data_fd,
+ off_t* data_file_size) {
vector<AnnotatedOperation> fragmented_aops;
for (const AnnotatedOperation& aop : *aops) {
if (aop.op.type() ==
@@ -1367,6 +1383,11 @@
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) {
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
index 6b4dc63..d34b9da 100644
--- a/payload_generator/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -234,13 +234,18 @@
// 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.
+ // 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
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
index fe15516..d62a4de 100644
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -1001,5 +1001,38 @@
EXPECT_EQ(data_file_size, second_op.data_offset() + second_op.data_length());
}
+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);
+}
+
} // namespace chromeos_update_engine