Avoid conflict of self-overlapping ops
When generating OTA, self-overlapping SOURCE_COPY operations are
allowed.(such as [20-30] -> [25-35]) These operations might cause
conflicts during merge, handle them in ConvertToCowOperations.
Test: treehugger
Change-Id: I4df9ce9e54f8512cae0aa0f4bcf9bcf8c01fd254
diff --git a/common/cow_operation_convert.cc b/common/cow_operation_convert.cc
index db17b5f..6b64a9c 100644
--- a/common/cow_operation_convert.cc
+++ b/common/cow_operation_convert.cc
@@ -30,6 +30,7 @@
merge_operations) {
ExtentRanges merge_extents;
std::vector<CowOperation> converted;
+ ExtentRanges modified_extents;
// We want all CowCopy ops to be done first, before any COW_REPLACE happen.
// Therefore we add these ops in 2 separate loops. This is because during
@@ -42,10 +43,29 @@
merge_extents.AddExtent(merge_op.dst_extent());
const auto& src_extent = merge_op.src_extent();
const auto& dst_extent = merge_op.dst_extent();
- for (uint64_t i = 0; i < src_extent.num_blocks(); i++) {
- converted.push_back({CowOperation::CowCopy,
- src_extent.start_block() + i,
- dst_extent.start_block() + i});
+ // Add blocks in reverse order to avoid merge conflicts on self-overlapping
+ // Ops.
+ // For example: SOURCE_COPY [20 - 30] -> [25 - 35] If blocks are added in
+ // forward order, then 20->25 is performed first, destroying block 25, which
+ // is neede by a later operation.
+ if (src_extent.start_block() < dst_extent.start_block()) {
+ for (uint64_t i = src_extent.num_blocks(); i > 0; i--) {
+ auto src_block = src_extent.start_block() + i - 1;
+ auto dst_block = dst_extent.start_block() + i - 1;
+ CHECK(!modified_extents.ContainsBlock(src_block))
+ << "block " << src_block << " is modified by previous CowCopy";
+ converted.push_back({CowOperation::CowCopy, src_block, dst_block});
+ modified_extents.AddBlock(dst_block);
+ }
+ } else {
+ for (uint64_t i = 0; i < src_extent.num_blocks(); i++) {
+ auto src_block = src_extent.start_block() + i;
+ auto dst_block = dst_extent.start_block() + i;
+ CHECK(!modified_extents.ContainsBlock(src_block))
+ << "block " << src_block << " is modified by previous CowCopy";
+ converted.push_back({CowOperation::CowCopy, src_block, dst_block});
+ modified_extents.AddBlock(dst_block);
+ }
}
}
// COW_REPLACE are added after COW_COPY, because replace might modify blocks
diff --git a/common/cow_operation_convert_unittest.cc b/common/cow_operation_convert_unittest.cc
index b70dcdf..93173fe 100644
--- a/common/cow_operation_convert_unittest.cc
+++ b/common/cow_operation_convert_unittest.cc
@@ -68,7 +68,6 @@
EXPECT_FALSE(modified_extents.ContainsBlock(cow_op.src_block))
<< "SOURCE_COPY operation " << cow_op
<< " read from a modified block";
- src_extent_set.SubtractExtent(ExtentForRange(cow_op.src_block, 1));
}
EXPECT_TRUE(dst_extent_set.ContainsBlock(cow_op.dst_block));
dst_extent_set.SubtractExtent(ExtentForRange(cow_op.dst_block, 1));
@@ -217,4 +216,21 @@
}));
VerifyCowMergeOp(cow_ops);
}
+
+TEST_F(CowOperationConvertTest, SelfOverlappingOperation) {
+ AddOperation(
+ &operations_, InstallOperation::SOURCE_COPY, {{20, 10}}, {{25, 10}});
+
+ AddMergeOperation(
+ &merge_operations_, CowMergeOperation::COW_COPY, {20, 10}, {25, 10});
+
+ auto cow_ops = ConvertToCowOperations(operations_, merge_operations_);
+ // Expect 10 COW_COPY
+ ASSERT_EQ(cow_ops.size(), 10UL);
+ ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) {
+ return cow_op.op == CowOperation::CowCopy;
+ }));
+ VerifyCowMergeOp(cow_ops);
+}
+
} // namespace chromeos_update_engine