Fix a bug where merge sequence is incorrect

Bug: 200076590
Bug: 177104308

Test: th
Change-Id: Ie6373f01bdbc3705b77c55ba32dacdddf7111b9f
diff --git a/payload_consumer/vabc_partition_writer.cc b/payload_consumer/vabc_partition_writer.cc
index a5d03d9..07eff92 100644
--- a/payload_consumer/vabc_partition_writer.cc
+++ b/payload_consumer/vabc_partition_writer.cc
@@ -97,7 +97,8 @@
                                size_t next_op_index) {
   xor_map_ = ComputeXorMap(partition_update_.merge_operations());
   TEST_AND_RETURN_FALSE(install_plan != nullptr);
-  if (source_may_exist) {
+  if (source_may_exist && install_part_.source_size > 0) {
+    TEST_AND_RETURN_FALSE(!install_part_.source_path.empty());
     TEST_AND_RETURN_FALSE(verified_source_fd_.Open());
   }
   std::optional<std::string> source_path;
@@ -155,15 +156,28 @@
   std::vector<uint32_t> blocks_merge_order;
   for (const auto& merge_op : merge_sequence) {
     const auto& dst_extent = merge_op.dst_extent();
+    const auto& src_extent = merge_op.src_extent();
     // In place copy are basically noops, they do not need to be "merged" at
     // all, don't include them in merge sequence.
     if (merge_op.type() == CowMergeOperation::COW_COPY &&
         merge_op.src_extent() == merge_op.dst_extent()) {
       continue;
     }
-    // libsnapshot prefers blocks in reverse order
-    for (int i = dst_extent.num_blocks() - 1; i >= 0; i--) {
-      blocks_merge_order.push_back(dst_extent.start_block() + i);
+    // libsnapshot prefers blocks in reverse order, so if this isn't a self
+    // overlapping OP, writing block in reverser order
+    // If this is a self-overlapping op and |dst_extent| comes after
+    // |src_extent|, we must write in reverse order for correctness.
+    // If this is self-overlapping op and |dst_extent| comes before
+    // |src_extent|, we must write in ascending order for correctness.
+    if (ExtentRanges::ExtentsOverlap(src_extent, dst_extent) &&
+        dst_extent.start_block() < src_extent.start_block()) {
+      for (size_t i = 0; i < dst_extent.num_blocks(); i++) {
+        blocks_merge_order.push_back(dst_extent.start_block() + i);
+      }
+    } else {
+      for (int i = dst_extent.num_blocks() - 1; i >= 0; i--) {
+        blocks_merge_order.push_back(dst_extent.start_block() + i);
+      }
     }
   }
   return cow_writer->AddSequenceData(blocks_merge_order.size(),
diff --git a/payload_consumer/vabc_partition_writer_unittest.cc b/payload_consumer/vabc_partition_writer_unittest.cc
index d77006e..a39098a 100644
--- a/payload_consumer/vabc_partition_writer_unittest.cc
+++ b/payload_consumer/vabc_partition_writer_unittest.cc
@@ -41,10 +41,13 @@
 using testing::Sequence;
 using utils::GetReadonlyZeroBlock;
 
+namespace {
+
 static constexpr auto& fake_part_name = "fake_part";
+static constexpr size_t FAKE_PART_SIZE = 4096 * 50;
 class VABCPartitionWriterTest : public ::testing::Test {
  public:
-  void SetUp() override {}
+  void SetUp() override { ftruncate(source_part_.fd, FAKE_PART_SIZE); }
 
  protected:
   void AddMergeOp(PartitionUpdate* partition,
@@ -68,34 +71,35 @@
   PartitionUpdate partition_update_;
   InstallPlan install_plan_;
   TemporaryFile source_part_;
-  InstallPlan::Partition install_part_{
-      .name = fake_part_name,
-      .source_path = source_part_.path,
-  };
+  InstallPlan::Partition install_part_{.name = fake_part_name,
+                                       .source_path = source_part_.path,
+                                       .source_size = FAKE_PART_SIZE};
 };
 
 TEST_F(VABCPartitionWriterTest, MergeSequenceWriteTest) {
   AddMergeOp(&partition_update_, {5, 1}, {10, 1}, CowMergeOperation::COW_COPY);
-  AddMergeOp(&partition_update_, {10, 1}, {15, 1}, CowMergeOperation::COW_XOR);
+  AddMergeOp(&partition_update_, {12, 2}, {13, 2}, CowMergeOperation::COW_XOR);
   AddMergeOp(&partition_update_, {15, 1}, {20, 1}, CowMergeOperation::COW_COPY);
   AddMergeOp(&partition_update_, {20, 1}, {25, 1}, CowMergeOperation::COW_COPY);
+  AddMergeOp(&partition_update_, {42, 5}, {40, 5}, CowMergeOperation::COW_XOR);
   VABCPartitionWriter writer_{
       partition_update_, install_part_, &dynamic_control_, kBlockSize};
   EXPECT_CALL(dynamic_control_, OpenCowWriter(fake_part_name, _, false))
-      .WillOnce(Invoke(
-          [](const std::string&, const std::optional<std::string>&, bool) {
-            auto cow_writer =
-                std::make_unique<android::snapshot::MockSnapshotWriter>(
-                    android::snapshot::CowOptions{});
-            auto expected_merge_sequence = {10, 15, 20, 25};
-            EXPECT_CALL(*cow_writer, Initialize()).WillOnce(Return(true));
-            EXPECT_CALL(*cow_writer, EmitSequenceData(_, _))
-                .With(Args<1, 0>(ElementsAreArray(expected_merge_sequence)))
-                .WillOnce(Return(true));
-            ON_CALL(*cow_writer, EmitCopy(_, _)).WillByDefault(Return(true));
-            ON_CALL(*cow_writer, EmitLabel(_)).WillByDefault(Return(true));
-            return cow_writer;
-          }));
+      .WillOnce(Invoke([](const std::string&,
+                          const std::optional<std::string>&,
+                          bool) {
+        auto cow_writer =
+            std::make_unique<android::snapshot::MockSnapshotWriter>(
+                android::snapshot::CowOptions{});
+        auto expected_merge_sequence = {10, 14, 13, 20, 25, 40, 41, 42, 43, 44};
+        EXPECT_CALL(*cow_writer, Initialize()).WillOnce(Return(true));
+        EXPECT_CALL(*cow_writer, EmitSequenceData(_, _))
+            .With(Args<1, 0>(ElementsAreArray(expected_merge_sequence)))
+            .WillOnce(Return(true));
+        ON_CALL(*cow_writer, EmitCopy(_, _)).WillByDefault(Return(true));
+        ON_CALL(*cow_writer, EmitLabel(_)).WillByDefault(Return(true));
+        return cow_writer;
+      }));
   ASSERT_TRUE(writer_.Init(&install_plan_, true, 0));
 }
 
@@ -198,4 +202,6 @@
       *install_op, nullptr, patch_data.data(), patch_data.size()));
 }
 
+}  // namespace
+
 }  // namespace chromeos_update_engine