libsnapshot: Add support for Xor ops in Cow Format

This adds support for Xor Ops in the Cow Format. These represent store
possibly compressed data which must be xor'ed against the given section
of source data to be interpreted as a block in the new image. The cow
reader and writer do not have access to this data, so they assume the
provider and user of the data will handle the xor-ing.

Bug: 177104308
Test: cow_api_test (ReadWriteXor)
Change-Id: I7a313d2643773d6b81a878a3e5bc87e3bdfc387b
diff --git a/fs_mgr/libsnapshot/cow_api_test.cpp b/fs_mgr/libsnapshot/cow_api_test.cpp
index ecfdefe..7e9097e 100644
--- a/fs_mgr/libsnapshot/cow_api_test.cpp
+++ b/fs_mgr/libsnapshot/cow_api_test.cpp
@@ -140,6 +140,85 @@
     ASSERT_TRUE(iter->Done());
 }
 
+TEST_F(CowTest, ReadWriteXor) {
+    CowOptions options;
+    options.cluster_ops = 0;
+    CowWriter writer(options);
+
+    ASSERT_TRUE(writer.Initialize(cow_->fd));
+
+    std::string data = "This is some data, believe it";
+    data.resize(options.block_size, '\0');
+
+    ASSERT_TRUE(writer.AddCopy(10, 20));
+    ASSERT_TRUE(writer.AddXorBlocks(50, data.data(), data.size(), 24, 10));
+    ASSERT_TRUE(writer.AddZeroBlocks(51, 2));
+    ASSERT_TRUE(writer.Finalize());
+
+    ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
+
+    CowReader reader;
+    CowHeader header;
+    CowFooter footer;
+    ASSERT_TRUE(reader.Parse(cow_->fd));
+    ASSERT_TRUE(reader.GetHeader(&header));
+    ASSERT_TRUE(reader.GetFooter(&footer));
+    ASSERT_EQ(header.magic, kCowMagicNumber);
+    ASSERT_EQ(header.major_version, kCowVersionMajor);
+    ASSERT_EQ(header.minor_version, kCowVersionMinor);
+    ASSERT_EQ(header.block_size, options.block_size);
+    ASSERT_EQ(footer.op.num_ops, 4);
+
+    auto iter = reader.GetOpIter();
+    ASSERT_NE(iter, nullptr);
+    ASSERT_FALSE(iter->Done());
+    auto op = &iter->Get();
+
+    ASSERT_EQ(op->type, kCowCopyOp);
+    ASSERT_EQ(op->compression, kCowCompressNone);
+    ASSERT_EQ(op->data_length, 0);
+    ASSERT_EQ(op->new_block, 10);
+    ASSERT_EQ(op->source, 20);
+
+    StringSink sink;
+
+    iter->Next();
+    ASSERT_FALSE(iter->Done());
+    op = &iter->Get();
+
+    ASSERT_EQ(op->type, kCowXorOp);
+    ASSERT_EQ(op->compression, kCowCompressNone);
+    ASSERT_EQ(op->data_length, 4096);
+    ASSERT_EQ(op->new_block, 50);
+    ASSERT_EQ(op->source, 98314);  // 4096 * 24 + 10
+    ASSERT_TRUE(reader.ReadData(*op, &sink));
+    ASSERT_EQ(sink.stream(), data);
+
+    iter->Next();
+    ASSERT_FALSE(iter->Done());
+    op = &iter->Get();
+
+    // Note: the zero operation gets split into two blocks.
+    ASSERT_EQ(op->type, kCowZeroOp);
+    ASSERT_EQ(op->compression, kCowCompressNone);
+    ASSERT_EQ(op->data_length, 0);
+    ASSERT_EQ(op->new_block, 51);
+    ASSERT_EQ(op->source, 0);
+
+    iter->Next();
+    ASSERT_FALSE(iter->Done());
+    op = &iter->Get();
+
+    ASSERT_EQ(op->type, kCowZeroOp);
+    ASSERT_EQ(op->compression, kCowCompressNone);
+    ASSERT_EQ(op->data_length, 0);
+    ASSERT_EQ(op->new_block, 52);
+    ASSERT_EQ(op->source, 0);
+
+    iter->Next();
+    ASSERT_TRUE(iter->Done());
+}
+
 TEST_F(CowTest, CompressGz) {
     CowOptions options;
     options.cluster_ops = 0;
diff --git a/fs_mgr/libsnapshot/cow_format.cpp b/fs_mgr/libsnapshot/cow_format.cpp
index 3085f80..8e6bec7 100644
--- a/fs_mgr/libsnapshot/cow_format.cpp
+++ b/fs_mgr/libsnapshot/cow_format.cpp
@@ -37,6 +37,8 @@
         os << "kCowLabelOp,   ";
     else if (op.type == kCowClusterOp)
         os << "kCowClusterOp  ";
+    else if (op.type == kCowXorOp)
+        os << "kCowXorOp      ";
     else if (op.type == kCowSequenceOp)
         os << "kCowSequenceOp ";
     else if (op.type == kCowFooterOp)
@@ -61,7 +63,7 @@
 int64_t GetNextOpOffset(const CowOperation& op, uint32_t cluster_ops) {
     if (op.type == kCowClusterOp) {
         return op.source;
-    } else if (op.type == kCowReplaceOp && cluster_ops == 0) {
+    } else if ((op.type == kCowReplaceOp || op.type == kCowXorOp) && cluster_ops == 0) {
         return op.data_length;
     } else {
         return 0;
@@ -93,6 +95,7 @@
 bool IsOrderedOp(const CowOperation& op) {
     switch (op.type) {
         case kCowCopyOp:
+        case kCowXorOp:
             return true;
         default:
             return false;
diff --git a/fs_mgr/libsnapshot/cow_reader.cpp b/fs_mgr/libsnapshot/cow_reader.cpp
index ace6f59..2acd158 100644
--- a/fs_mgr/libsnapshot/cow_reader.cpp
+++ b/fs_mgr/libsnapshot/cow_reader.cpp
@@ -157,6 +157,13 @@
         // Reading a v1 version of COW which doesn't have buffer_size.
         header_.buffer_size = 0;
     }
+    uint64_t data_pos = 0;
+
+    if (header_.cluster_ops) {
+        data_pos = pos + header_.cluster_ops * sizeof(CowOperation);
+    } else {
+        data_pos = pos + sizeof(CowOperation);
+    }
 
     auto ops_buffer = std::make_shared<std::vector<CowOperation>>();
     uint64_t current_op_num = 0;
@@ -177,7 +184,11 @@
         while (current_op_num < ops_buffer->size()) {
             auto& current_op = ops_buffer->data()[current_op_num];
             current_op_num++;
+            if (current_op.type == kCowXorOp) {
+                data_loc_[current_op.new_block] = data_pos;
+            }
             pos += sizeof(CowOperation) + GetNextOpOffset(current_op, header_.cluster_ops);
+            data_pos += current_op.data_length + GetNextDataOffset(current_op, header_.cluster_ops);
 
             if (current_op.type == kCowClusterOp) {
                 break;
@@ -606,7 +617,13 @@
             return false;
     }
 
-    CowDataStream stream(this, op.source, op.data_length);
+    uint64_t offset;
+    if (op.type == kCowXorOp) {
+        offset = data_loc_[op.new_block];
+    } else {
+        offset = op.source;
+    }
+    CowDataStream stream(this, offset, op.data_length);
     decompressor->set_stream(&stream);
     decompressor->set_sink(sink);
     return decompressor->Decompress(header_.block_size);
diff --git a/fs_mgr/libsnapshot/cow_writer.cpp b/fs_mgr/libsnapshot/cow_writer.cpp
index ef30e32..5ce1d3b 100644
--- a/fs_mgr/libsnapshot/cow_writer.cpp
+++ b/fs_mgr/libsnapshot/cow_writer.cpp
@@ -58,10 +58,24 @@
     return EmitRawBlocks(new_block_start, data, size);
 }
 
-bool ICowWriter::AddXorBlocks(uint32_t /*new_block_start*/, const void* /*data*/, size_t /*size*/,
-                              uint32_t /*old_block*/, uint16_t /*offset*/) {
-    LOG(ERROR) << "AddXorBlocks not yet implemented";
-    return false;
+bool ICowWriter::AddXorBlocks(uint32_t new_block_start, const void* data, size_t size,
+                              uint32_t old_block, uint16_t offset) {
+    if (size % options_.block_size != 0) {
+        LOG(ERROR) << "AddRawBlocks: size " << size << " is not a multiple of "
+                   << options_.block_size;
+        return false;
+    }
+
+    uint64_t num_blocks = size / options_.block_size;
+    uint64_t last_block = new_block_start + num_blocks - 1;
+    if (!ValidateNewBlock(last_block)) {
+        return false;
+    }
+    if (offset >= options_.block_size) {
+        LOG(ERROR) << "AddXorBlocks: offset " << offset << " is not less than "
+                   << options_.block_size;
+    }
+    return EmitXorBlocks(new_block_start, data, size, old_block, offset);
 }
 
 bool ICowWriter::AddZeroBlocks(uint64_t new_block_start, uint64_t num_blocks) {
@@ -278,13 +292,27 @@
 }
 
 bool CowWriter::EmitRawBlocks(uint64_t new_block_start, const void* data, size_t size) {
+    return EmitBlocks(new_block_start, data, size, 0, 0, kCowReplaceOp);
+}
+
+bool CowWriter::EmitXorBlocks(uint32_t new_block_start, const void* data, size_t size,
+                              uint32_t old_block, uint16_t offset) {
+    return EmitBlocks(new_block_start, data, size, old_block, offset, kCowXorOp);
+}
+
+bool CowWriter::EmitBlocks(uint64_t new_block_start, const void* data, size_t size,
+                           uint64_t old_block, uint16_t offset, uint8_t type) {
     const uint8_t* iter = reinterpret_cast<const uint8_t*>(data);
     CHECK(!merge_in_progress_);
     for (size_t i = 0; i < size / header_.block_size; i++) {
         CowOperation op = {};
-        op.type = kCowReplaceOp;
         op.new_block = new_block_start + i;
-        op.source = next_data_pos_;
+        op.type = type;
+        if (type == kCowXorOp) {
+            op.source = (old_block + i) * header_.block_size + offset;
+        } else {
+            op.source = next_data_pos_;
+        }
 
         if (compression_) {
             auto data = Compress(iter, header_.block_size);
diff --git a/fs_mgr/libsnapshot/include/libsnapshot/cow_format.h b/fs_mgr/libsnapshot/include/libsnapshot/cow_format.h
index 464046b..c15682a 100644
--- a/fs_mgr/libsnapshot/include/libsnapshot/cow_format.h
+++ b/fs_mgr/libsnapshot/include/libsnapshot/cow_format.h
@@ -138,6 +138,8 @@
     // For Label operations, this is the value of the applied label.
     //
     // For Cluster operations, this is the length of the following data region
+    //
+    // For Xor operations, this is the byte location in the source image.
     uint64_t source;
 } __attribute__((packed));
 
@@ -148,6 +150,7 @@
 static constexpr uint8_t kCowZeroOp = 3;
 static constexpr uint8_t kCowLabelOp = 4;
 static constexpr uint8_t kCowClusterOp = 5;
+static constexpr uint8_t kCowXorOp = 6;
 static constexpr uint8_t kCowSequenceOp = 7;
 static constexpr uint8_t kCowFooterOp = -1;
 
diff --git a/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h b/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
index 6c3059c..eeaa5c6 100644
--- a/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
+++ b/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
@@ -153,6 +153,7 @@
     uint64_t num_total_data_ops_;
     uint64_t num_ordered_ops_to_merge_;
     bool has_seq_ops_;
+    std::unordered_map<uint64_t, uint64_t> data_loc_;
 };
 
 }  // namespace snapshot
diff --git a/fs_mgr/libsnapshot/include/libsnapshot/cow_writer.h b/fs_mgr/libsnapshot/include/libsnapshot/cow_writer.h
index 4a807fb..e17b5c6 100644
--- a/fs_mgr/libsnapshot/include/libsnapshot/cow_writer.h
+++ b/fs_mgr/libsnapshot/include/libsnapshot/cow_writer.h
@@ -86,6 +86,8 @@
   protected:
     virtual bool EmitCopy(uint64_t new_block, uint64_t old_block) = 0;
     virtual bool EmitRawBlocks(uint64_t new_block_start, const void* data, size_t size) = 0;
+    virtual bool EmitXorBlocks(uint32_t new_block_start, const void* data, size_t size,
+                               uint32_t old_block, uint16_t offset) = 0;
     virtual bool EmitZeroBlocks(uint64_t new_block_start, uint64_t num_blocks) = 0;
     virtual bool EmitLabel(uint64_t label) = 0;
     virtual bool EmitSequenceData(size_t num_ops, const uint32_t* data) = 0;
@@ -122,6 +124,8 @@
   protected:
     virtual bool EmitCopy(uint64_t new_block, uint64_t old_block) override;
     virtual bool EmitRawBlocks(uint64_t new_block_start, const void* data, size_t size) override;
+    virtual bool EmitXorBlocks(uint32_t new_block_start, const void* data, size_t size,
+                               uint32_t old_block, uint16_t offset) override;
     virtual bool EmitZeroBlocks(uint64_t new_block_start, uint64_t num_blocks) override;
     virtual bool EmitLabel(uint64_t label) override;
     virtual bool EmitSequenceData(size_t num_ops, const uint32_t* data) override;
@@ -129,6 +133,8 @@
   private:
     bool EmitCluster();
     bool EmitClusterIfNeeded();
+    bool EmitBlocks(uint64_t new_block_start, const void* data, size_t size, uint64_t old_block,
+                    uint16_t offset, uint8_t type);
     void SetupHeaders();
     bool ParseOptions();
     bool OpenForWrite();
diff --git a/fs_mgr/libsnapshot/include/libsnapshot/snapshot_writer.h b/fs_mgr/libsnapshot/include/libsnapshot/snapshot_writer.h
index c00dafa..b09e1ae 100644
--- a/fs_mgr/libsnapshot/include/libsnapshot/snapshot_writer.h
+++ b/fs_mgr/libsnapshot/include/libsnapshot/snapshot_writer.h
@@ -74,6 +74,8 @@
   protected:
     bool EmitCopy(uint64_t new_block, uint64_t old_block) override;
     bool EmitRawBlocks(uint64_t new_block_start, const void* data, size_t size) override;
+    bool EmitXorBlocks(uint32_t new_block_start, const void* data, size_t size, uint32_t old_block,
+                       uint16_t offset) override;
     bool EmitZeroBlocks(uint64_t new_block_start, uint64_t num_blocks) override;
     bool EmitLabel(uint64_t label) override;
     bool EmitSequenceData(size_t num_ops, const uint32_t* data) override;
@@ -102,6 +104,8 @@
   protected:
     bool EmitRawBlocks(uint64_t new_block_start, const void* data, size_t size) override;
     bool EmitZeroBlocks(uint64_t new_block_start, uint64_t num_blocks) override;
+    bool EmitXorBlocks(uint32_t new_block_start, const void* data, size_t size, uint32_t old_block,
+                       uint16_t offset) override;
     bool EmitCopy(uint64_t new_block, uint64_t old_block) override;
     bool EmitLabel(uint64_t label) override;
     bool EmitSequenceData(size_t num_ops, const uint32_t* data) override;
diff --git a/fs_mgr/libsnapshot/snapshot_writer.cpp b/fs_mgr/libsnapshot/snapshot_writer.cpp
index 34b3e87..3eda08e 100644
--- a/fs_mgr/libsnapshot/snapshot_writer.cpp
+++ b/fs_mgr/libsnapshot/snapshot_writer.cpp
@@ -106,6 +106,11 @@
     return cow_->AddRawBlocks(new_block_start, data, size);
 }
 
+bool CompressedSnapshotWriter::EmitXorBlocks(uint32_t new_block_start, const void* data,
+                                             size_t size, uint32_t old_block, uint16_t offset) {
+    return cow_->AddXorBlocks(new_block_start, data, size, old_block, offset);
+}
+
 bool CompressedSnapshotWriter::EmitZeroBlocks(uint64_t new_block_start, uint64_t num_blocks) {
     return cow_->AddZeroBlocks(new_block_start, num_blocks);
 }
@@ -157,6 +162,11 @@
     return true;
 }
 
+bool OnlineKernelSnapshotWriter::EmitXorBlocks(uint32_t, const void*, size_t, uint32_t, uint16_t) {
+    LOG(ERROR) << "EmitXorBlocks not implemented.";
+    return false;
+}
+
 bool OnlineKernelSnapshotWriter::EmitZeroBlocks(uint64_t new_block_start, uint64_t num_blocks) {
     std::string zeroes(options_.block_size, 0);
     for (uint64_t i = 0; i < num_blocks; i++) {