Merge changes from topic "CowSequenceOp"
* changes:
libsnapshot: Switch merge to CowRevMergeOpItr
libsnapshot: Add seq op support to inspect_cow
libsnapshot: Add CowRevMergeOpIter
libsnapshot: Add IsOrderedOp
libsnapshot: Cleanup iterators
libsnapshot: Add Sequence Ops
diff --git a/fs_mgr/libsnapshot/cow_api_test.cpp b/fs_mgr/libsnapshot/cow_api_test.cpp
index b75b154..7f7e40a 100644
--- a/fs_mgr/libsnapshot/cow_api_test.cpp
+++ b/fs_mgr/libsnapshot/cow_api_test.cpp
@@ -981,6 +981,137 @@
ASSERT_EQ(num_clusters, 1);
}
+TEST_F(CowTest, BigSeqOp) {
+ CowOptions options;
+ CowWriter writer(options);
+ const int seq_len = std::numeric_limits<uint16_t>::max() / sizeof(uint32_t) + 1;
+ uint32_t sequence[seq_len];
+ for (int i = 0; i < seq_len; i++) {
+ sequence[i] = i + 1;
+ }
+
+ ASSERT_TRUE(writer.Initialize(cow_->fd));
+
+ ASSERT_TRUE(writer.AddSequenceData(seq_len, sequence));
+ ASSERT_TRUE(writer.AddZeroBlocks(1, seq_len));
+ ASSERT_TRUE(writer.Finalize());
+
+ ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
+
+ CowReader reader;
+ ASSERT_TRUE(reader.Parse(cow_->fd));
+ auto iter = reader.GetRevMergeOpIter();
+
+ for (int i = 0; i < seq_len; i++) {
+ ASSERT_TRUE(!iter->Done());
+ const auto& op = iter->Get();
+
+ ASSERT_EQ(op.new_block, seq_len - i);
+
+ iter->Next();
+ }
+ ASSERT_TRUE(iter->Done());
+}
+
+TEST_F(CowTest, RevMergeOpItrTest) {
+ CowOptions options;
+ options.cluster_ops = 5;
+ options.num_merge_ops = 1;
+ CowWriter writer(options);
+ uint32_t sequence[] = {2, 10, 6, 7, 3, 5};
+
+ ASSERT_TRUE(writer.Initialize(cow_->fd));
+
+ ASSERT_TRUE(writer.AddSequenceData(6, sequence));
+ ASSERT_TRUE(writer.AddCopy(6, 3));
+ ASSERT_TRUE(writer.AddZeroBlocks(12, 1));
+ ASSERT_TRUE(writer.AddZeroBlocks(8, 1));
+ ASSERT_TRUE(writer.AddZeroBlocks(11, 1));
+ ASSERT_TRUE(writer.AddCopy(3, 5));
+ ASSERT_TRUE(writer.AddCopy(2, 1));
+ ASSERT_TRUE(writer.AddZeroBlocks(4, 1));
+ ASSERT_TRUE(writer.AddZeroBlocks(9, 1));
+ ASSERT_TRUE(writer.AddCopy(5, 6));
+ ASSERT_TRUE(writer.AddZeroBlocks(1, 1));
+ ASSERT_TRUE(writer.AddCopy(10, 2));
+ ASSERT_TRUE(writer.AddCopy(7, 4));
+ ASSERT_TRUE(writer.Finalize());
+
+ // New block in cow order is 6, 12, 8, 11, 3, 2, 4, 9, 5, 1, 10, 7
+ // New block in merge order is 2, 10, 6, 7, 3, 5, 12, 11, 9, 8, 4, 1
+ // RevMergeOrder is 1, 4, 8, 9, 11, 12, 5, 3, 7, 6, 10, 2
+ // new block 2 is "already merged", so will be left out.
+
+ std::vector<uint64_t> revMergeOpSequence = {1, 4, 8, 9, 11, 12, 5, 3, 7, 6, 10};
+
+ ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
+
+ CowReader reader;
+ ASSERT_TRUE(reader.Parse(cow_->fd));
+ auto iter = reader.GetRevMergeOpIter();
+ auto expected_new_block = revMergeOpSequence.begin();
+
+ while (!iter->Done() && expected_new_block != revMergeOpSequence.end()) {
+ const auto& op = iter->Get();
+
+ ASSERT_EQ(op.new_block, *expected_new_block);
+
+ iter->Next();
+ expected_new_block++;
+ }
+ ASSERT_EQ(expected_new_block, revMergeOpSequence.end());
+ ASSERT_TRUE(iter->Done());
+}
+
+TEST_F(CowTest, LegacyRevMergeOpItrTest) {
+ CowOptions options;
+ options.cluster_ops = 5;
+ options.num_merge_ops = 1;
+ CowWriter writer(options);
+
+ ASSERT_TRUE(writer.Initialize(cow_->fd));
+
+ ASSERT_TRUE(writer.AddCopy(2, 1));
+ ASSERT_TRUE(writer.AddCopy(10, 2));
+ ASSERT_TRUE(writer.AddCopy(6, 3));
+ ASSERT_TRUE(writer.AddCopy(7, 4));
+ ASSERT_TRUE(writer.AddCopy(3, 5));
+ ASSERT_TRUE(writer.AddCopy(5, 6));
+ ASSERT_TRUE(writer.AddZeroBlocks(12, 1));
+ ASSERT_TRUE(writer.AddZeroBlocks(8, 1));
+ ASSERT_TRUE(writer.AddZeroBlocks(11, 1));
+ ASSERT_TRUE(writer.AddZeroBlocks(4, 1));
+ ASSERT_TRUE(writer.AddZeroBlocks(9, 1));
+ ASSERT_TRUE(writer.AddZeroBlocks(1, 1));
+
+ ASSERT_TRUE(writer.Finalize());
+
+ // New block in cow order is 2, 10, 6, 7, 3, 5, 12, 8, 11, 4, 9, 1
+ // New block in merge order is 2, 10, 6, 7, 3, 5, 12, 11, 9, 8, 4, 1
+ // RevMergeOrder is 1, 4, 8, 9, 11, 12, 5, 3, 7, 6, 10, 2
+ // new block 2 is "already merged", so will be left out.
+
+ std::vector<uint64_t> revMergeOpSequence = {1, 4, 8, 9, 11, 12, 5, 3, 7, 6, 10};
+
+ ASSERT_EQ(lseek(cow_->fd, 0, SEEK_SET), 0);
+
+ CowReader reader;
+ ASSERT_TRUE(reader.Parse(cow_->fd));
+ auto iter = reader.GetRevMergeOpIter();
+ auto expected_new_block = revMergeOpSequence.begin();
+
+ while (!iter->Done() && expected_new_block != revMergeOpSequence.end()) {
+ const auto& op = iter->Get();
+
+ ASSERT_EQ(op.new_block, *expected_new_block);
+
+ iter->Next();
+ expected_new_block++;
+ }
+ ASSERT_EQ(expected_new_block, revMergeOpSequence.end());
+ ASSERT_TRUE(iter->Done());
+}
+
} // namespace snapshot
} // namespace android
diff --git a/fs_mgr/libsnapshot/cow_format.cpp b/fs_mgr/libsnapshot/cow_format.cpp
index 0753c49..3085f80 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 == kCowSequenceOp)
+ os << "kCowSequenceOp ";
else if (op.type == kCowFooterOp)
os << "kCowFooterOp ";
else
@@ -81,6 +83,16 @@
case kCowLabelOp:
case kCowClusterOp:
case kCowFooterOp:
+ case kCowSequenceOp:
+ return true;
+ default:
+ return false;
+ }
+}
+
+bool IsOrderedOp(const CowOperation& op) {
+ switch (op.type) {
+ case kCowCopyOp:
return true;
default:
return false;
diff --git a/fs_mgr/libsnapshot/cow_reader.cpp b/fs_mgr/libsnapshot/cow_reader.cpp
index 2349e4a..b3198a0 100644
--- a/fs_mgr/libsnapshot/cow_reader.cpp
+++ b/fs_mgr/libsnapshot/cow_reader.cpp
@@ -19,6 +19,9 @@
#include <limits>
#include <optional>
+#include <set>
+#include <unordered_map>
+#include <unordered_set>
#include <vector>
#include <android-base/file.h>
@@ -127,7 +130,10 @@
return false;
}
- return ParseOps(label);
+ if (!ParseOps(label)) {
+ return false;
+ }
+ return PrepMergeOps();
}
bool CowReader::ParseOps(std::optional<uint64_t> label) {
@@ -201,6 +207,8 @@
current_op_num--;
done = true;
break;
+ } else if (current_op.type == kCowSequenceOp) {
+ has_seq_ops_ = true;
}
}
@@ -251,7 +259,7 @@
LOG(ERROR) << "ops checksum does not match";
return false;
}
- SHA256(ops_buffer.get()->data(), footer_->op.ops_size, csum);
+ SHA256(ops_buffer->data(), footer_->op.ops_size, csum);
if (memcmp(csum, footer_->data.ops_checksum, sizeof(csum)) != 0) {
LOG(ERROR) << "ops checksum does not match";
return false;
@@ -264,138 +272,165 @@
return true;
}
-void CowReader::InitializeMerge() {
- uint64_t num_copy_ops = 0;
+//
+// This sets up the data needed for MergeOpIter. MergeOpIter presents
+// data in the order we intend to merge in.
+//
+// We merge all order sensitive ops up front, and sort the rest to allow for
+// batch merging. Order sensitive ops can either be presented in their proper
+// order in the cow, or be ordered by sequence ops (kCowSequenceOp), in which
+// case we want to merge those ops first, followed by any ops not specified by
+// new_block value by the sequence op, in sorted order.
+// We will re-arrange the vector in such a way that
+// kernel can batch merge. Ex:
+//
+// Existing COW format; All the copy operations
+// are at the beginning.
+// =======================================
+// Copy-op-1 - cow_op->new_block = 1
+// Copy-op-2 - cow_op->new_block = 2
+// Copy-op-3 - cow_op->new_block = 3
+// Replace-op-4 - cow_op->new_block = 6
+// Replace-op-5 - cow_op->new_block = 4
+// Replace-op-6 - cow_op->new_block = 8
+// Replace-op-7 - cow_op->new_block = 9
+// Zero-op-8 - cow_op->new_block = 7
+// Zero-op-9 - cow_op->new_block = 5
+// =======================================
+//
+// First find the operation which isn't a copy-op
+// and then sort all the operations in descending order
+// with the key being cow_op->new_block (source block)
+//
+// The data-structure will look like:
+//
+// =======================================
+// Copy-op-1 - cow_op->new_block = 1
+// Copy-op-2 - cow_op->new_block = 2
+// Copy-op-3 - cow_op->new_block = 3
+// Replace-op-7 - cow_op->new_block = 9
+// Replace-op-6 - cow_op->new_block = 8
+// Zero-op-8 - cow_op->new_block = 7
+// Replace-op-4 - cow_op->new_block = 6
+// Zero-op-9 - cow_op->new_block = 5
+// Replace-op-5 - cow_op->new_block = 4
+// =======================================
+//
+// Daemon will read the above data-structure in reverse-order
+// when reading metadata. Thus, kernel will get the metadata
+// in the following order:
+//
+// ========================================
+// Replace-op-5 - cow_op->new_block = 4
+// Zero-op-9 - cow_op->new_block = 5
+// Replace-op-4 - cow_op->new_block = 6
+// Zero-op-8 - cow_op->new_block = 7
+// Replace-op-6 - cow_op->new_block = 8
+// Replace-op-7 - cow_op->new_block = 9
+// Copy-op-3 - cow_op->new_block = 3
+// Copy-op-2 - cow_op->new_block = 2
+// Copy-op-1 - cow_op->new_block = 1
+// ===========================================
+//
+// When merging begins, kernel will start from the last
+// metadata which was read: In the above format, Copy-op-1
+// will be the first merge operation.
+//
+// Now, batching of the merge operations happens only when
+// 1: origin block numbers in the base device are contiguous
+// (cow_op->new_block) and,
+// 2: cow block numbers which are assigned by daemon in ReadMetadata()
+// are contiguous. These are monotonically increasing numbers.
+//
+// When both (1) and (2) are true, kernel will batch merge the operations.
+// In the above case, we have to ensure that the copy operations
+// are merged first before replace operations are done. Hence,
+// we will not change the order of copy operations. Since,
+// cow_op->new_block numbers are contiguous, we will ensure that the
+// cow block numbers assigned in ReadMetadata() for these respective copy
+// operations are not contiguous forcing kernel to issue merge for each
+// copy operations without batch merging.
+//
+// For all the other operations viz. Replace and Zero op, the cow block
+// numbers assigned by daemon will be contiguous allowing kernel to batch
+// merge.
+//
+// The final format after assiging COW block numbers by the daemon will
+// look something like:
+//
+// =========================================================
+// Replace-op-5 - cow_op->new_block = 4 cow-block-num = 2
+// Zero-op-9 - cow_op->new_block = 5 cow-block-num = 3
+// Replace-op-4 - cow_op->new_block = 6 cow-block-num = 4
+// Zero-op-8 - cow_op->new_block = 7 cow-block-num = 5
+// Replace-op-6 - cow_op->new_block = 8 cow-block-num = 6
+// Replace-op-7 - cow_op->new_block = 9 cow-block-num = 7
+// Copy-op-3 - cow_op->new_block = 3 cow-block-num = 9
+// Copy-op-2 - cow_op->new_block = 2 cow-block-num = 11
+// Copy-op-1 - cow_op->new_block = 1 cow-block-num = 13
+// ==========================================================
+//
+// Merge sequence will look like:
+//
+// Merge-1 - Batch-merge { Copy-op-1, Copy-op-2, Copy-op-3 }
+// Merge-2 - Batch-merge {Replace-op-7, Replace-op-6, Zero-op-8,
+// Replace-op-4, Zero-op-9, Replace-op-5 }
+//==============================================================
+bool CowReader::PrepMergeOps() {
+ auto merge_op_blocks = std::make_shared<std::vector<uint32_t>>();
+ std::set<int, std::greater<int>> other_ops;
+ auto seq_ops_set = std::unordered_set<uint32_t>();
+ auto block_map = std::make_shared<std::unordered_map<uint32_t, int>>();
+ int num_seqs = 0;
+ size_t read;
- // Remove all the metadata operations
- ops_->erase(std::remove_if(ops_.get()->begin(), ops_.get()->end(),
- [](CowOperation& op) { return IsMetadataOp(op); }),
- ops_.get()->end());
-
- set_total_data_ops(ops_->size());
- // We will re-arrange the vector in such a way that
- // kernel can batch merge. Ex:
- //
- // Existing COW format; All the copy operations
- // are at the beginning.
- // =======================================
- // Copy-op-1 - cow_op->new_block = 1
- // Copy-op-2 - cow_op->new_block = 2
- // Copy-op-3 - cow_op->new_block = 3
- // Replace-op-4 - cow_op->new_block = 6
- // Replace-op-5 - cow_op->new_block = 4
- // Replace-op-6 - cow_op->new_block = 8
- // Replace-op-7 - cow_op->new_block = 9
- // Zero-op-8 - cow_op->new_block = 7
- // Zero-op-9 - cow_op->new_block = 5
- // =======================================
- //
- // First find the operation which isn't a copy-op
- // and then sort all the operations in descending order
- // with the key being cow_op->new_block (source block)
- //
- // The data-structure will look like:
- //
- // =======================================
- // Copy-op-1 - cow_op->new_block = 1
- // Copy-op-2 - cow_op->new_block = 2
- // Copy-op-3 - cow_op->new_block = 3
- // Replace-op-7 - cow_op->new_block = 9
- // Replace-op-6 - cow_op->new_block = 8
- // Zero-op-8 - cow_op->new_block = 7
- // Replace-op-4 - cow_op->new_block = 6
- // Zero-op-9 - cow_op->new_block = 5
- // Replace-op-5 - cow_op->new_block = 4
- // =======================================
- //
- // Daemon will read the above data-structure in reverse-order
- // when reading metadata. Thus, kernel will get the metadata
- // in the following order:
- //
- // ========================================
- // Replace-op-5 - cow_op->new_block = 4
- // Zero-op-9 - cow_op->new_block = 5
- // Replace-op-4 - cow_op->new_block = 6
- // Zero-op-8 - cow_op->new_block = 7
- // Replace-op-6 - cow_op->new_block = 8
- // Replace-op-7 - cow_op->new_block = 9
- // Copy-op-3 - cow_op->new_block = 3
- // Copy-op-2 - cow_op->new_block = 2
- // Copy-op-1 - cow_op->new_block = 1
- // ===========================================
- //
- // When merging begins, kernel will start from the last
- // metadata which was read: In the above format, Copy-op-1
- // will be the first merge operation.
- //
- // Now, batching of the merge operations happens only when
- // 1: origin block numbers in the base device are contiguous
- // (cow_op->new_block) and,
- // 2: cow block numbers which are assigned by daemon in ReadMetadata()
- // are contiguous. These are monotonically increasing numbers.
- //
- // When both (1) and (2) are true, kernel will batch merge the operations.
- // In the above case, we have to ensure that the copy operations
- // are merged first before replace operations are done. Hence,
- // we will not change the order of copy operations. Since,
- // cow_op->new_block numbers are contiguous, we will ensure that the
- // cow block numbers assigned in ReadMetadata() for these respective copy
- // operations are not contiguous forcing kernel to issue merge for each
- // copy operations without batch merging.
- //
- // For all the other operations viz. Replace and Zero op, the cow block
- // numbers assigned by daemon will be contiguous allowing kernel to batch
- // merge.
- //
- // The final format after assiging COW block numbers by the daemon will
- // look something like:
- //
- // =========================================================
- // Replace-op-5 - cow_op->new_block = 4 cow-block-num = 2
- // Zero-op-9 - cow_op->new_block = 5 cow-block-num = 3
- // Replace-op-4 - cow_op->new_block = 6 cow-block-num = 4
- // Zero-op-8 - cow_op->new_block = 7 cow-block-num = 5
- // Replace-op-6 - cow_op->new_block = 8 cow-block-num = 6
- // Replace-op-7 - cow_op->new_block = 9 cow-block-num = 7
- // Copy-op-3 - cow_op->new_block = 3 cow-block-num = 9
- // Copy-op-2 - cow_op->new_block = 2 cow-block-num = 11
- // Copy-op-1 - cow_op->new_block = 1 cow-block-num = 13
- // ==========================================================
- //
- // Merge sequence will look like:
- //
- // Merge-1 - Batch-merge { Copy-op-1, Copy-op-2, Copy-op-3 }
- // Merge-2 - Batch-merge {Replace-op-7, Replace-op-6, Zero-op-8,
- // Replace-op-4, Zero-op-9, Replace-op-5 }
- //==============================================================
-
- num_copy_ops = FindNumCopyops();
-
- std::sort(ops_.get()->begin() + num_copy_ops, ops_.get()->end(),
- [](CowOperation& op1, CowOperation& op2) -> bool {
- return op1.new_block > op2.new_block;
- });
-
- if (header_.num_merge_ops > 0) {
- ops_->erase(ops_.get()->begin(), ops_.get()->begin() + header_.num_merge_ops);
- }
-
- num_copy_ops = FindNumCopyops();
- set_copy_ops(num_copy_ops);
-}
-
-uint64_t CowReader::FindNumCopyops() {
- uint64_t num_copy_ops = 0;
-
- for (uint64_t i = 0; i < ops_->size(); i++) {
+ for (int i = 0; i < ops_->size(); i++) {
auto& current_op = ops_->data()[i];
- if (current_op.type != kCowCopyOp) {
- break;
+
+ if (current_op.type == kCowSequenceOp) {
+ size_t seq_len = current_op.data_length / sizeof(uint32_t);
+
+ merge_op_blocks->resize(merge_op_blocks->size() + seq_len);
+ if (!GetRawBytes(current_op.source, &merge_op_blocks->data()[num_seqs],
+ current_op.data_length, &read)) {
+ PLOG(ERROR) << "Failed to read sequence op!";
+ return false;
+ }
+ for (int j = num_seqs; j < num_seqs + seq_len; j++) {
+ seq_ops_set.insert(merge_op_blocks->data()[j]);
+ }
+ num_seqs += seq_len;
}
- num_copy_ops += 1;
+
+ if (IsMetadataOp(current_op)) {
+ continue;
+ }
+
+ if (!has_seq_ops_ && IsOrderedOp(current_op)) {
+ merge_op_blocks->emplace_back(current_op.new_block);
+ } else if (seq_ops_set.count(current_op.new_block) == 0) {
+ other_ops.insert(current_op.new_block);
+ }
+ block_map->insert({current_op.new_block, i});
+ }
+ if (merge_op_blocks->size() > header_.num_merge_ops)
+ num_ordered_ops_to_merge_ = merge_op_blocks->size() - header_.num_merge_ops;
+ else
+ num_ordered_ops_to_merge_ = 0;
+ merge_op_blocks->reserve(merge_op_blocks->size() + other_ops.size());
+ for (auto block : other_ops) {
+ merge_op_blocks->emplace_back(block);
}
- return num_copy_ops;
+ num_total_data_ops_ = merge_op_blocks->size();
+ if (header_.num_merge_ops > 0) {
+ merge_op_blocks->erase(merge_op_blocks->begin(),
+ merge_op_blocks->begin() + header_.num_merge_ops);
+ }
+
+ block_map_ = block_map;
+ merge_op_blocks_ = merge_op_blocks;
+ return true;
}
bool CowReader::GetHeader(CowHeader* header) {
@@ -430,11 +465,11 @@
CowOpIter::CowOpIter(std::shared_ptr<std::vector<CowOperation>>& ops) {
ops_ = ops;
- op_iter_ = ops_.get()->begin();
+ op_iter_ = ops_->begin();
}
bool CowOpIter::Done() {
- return op_iter_ == ops_.get()->end();
+ return op_iter_ == ops_->end();
}
void CowOpIter::Next() {
@@ -447,9 +482,11 @@
return (*op_iter_);
}
-class CowOpReverseIter final : public ICowOpReverseIter {
+class CowRevMergeOpIter final : public ICowOpIter {
public:
- explicit CowOpReverseIter(std::shared_ptr<std::vector<CowOperation>> ops);
+ explicit CowRevMergeOpIter(std::shared_ptr<std::vector<CowOperation>> ops,
+ std::shared_ptr<std::vector<uint32_t>> merge_op_blocks,
+ std::shared_ptr<std::unordered_map<uint32_t, int>> map);
bool Done() override;
const CowOperation& Get() override;
@@ -457,34 +494,41 @@
private:
std::shared_ptr<std::vector<CowOperation>> ops_;
- std::vector<CowOperation>::reverse_iterator op_riter_;
+ std::shared_ptr<std::vector<uint32_t>> merge_op_blocks_;
+ std::shared_ptr<std::unordered_map<uint32_t, int>> map_;
+ std::vector<uint32_t>::reverse_iterator block_riter_;
};
-CowOpReverseIter::CowOpReverseIter(std::shared_ptr<std::vector<CowOperation>> ops) {
+CowRevMergeOpIter::CowRevMergeOpIter(std::shared_ptr<std::vector<CowOperation>> ops,
+ std::shared_ptr<std::vector<uint32_t>> merge_op_blocks,
+ std::shared_ptr<std::unordered_map<uint32_t, int>> map) {
ops_ = ops;
- op_riter_ = ops_.get()->rbegin();
+ merge_op_blocks_ = merge_op_blocks;
+ map_ = map;
+
+ block_riter_ = merge_op_blocks->rbegin();
}
-bool CowOpReverseIter::Done() {
- return op_riter_ == ops_.get()->rend();
+bool CowRevMergeOpIter::Done() {
+ return block_riter_ == merge_op_blocks_->rend();
}
-void CowOpReverseIter::Next() {
+void CowRevMergeOpIter::Next() {
CHECK(!Done());
- op_riter_++;
+ block_riter_++;
}
-const CowOperation& CowOpReverseIter::Get() {
+const CowOperation& CowRevMergeOpIter::Get() {
CHECK(!Done());
- return (*op_riter_);
+ return ops_->data()[map_->at(*block_riter_)];
}
std::unique_ptr<ICowOpIter> CowReader::GetOpIter() {
return std::make_unique<CowOpIter>(ops_);
}
-std::unique_ptr<ICowOpReverseIter> CowReader::GetRevOpIter() {
- return std::make_unique<CowOpReverseIter>(ops_);
+std::unique_ptr<ICowOpIter> CowReader::GetRevMergeOpIter() {
+ return std::make_unique<CowRevMergeOpIter>(ops_, merge_op_blocks_, block_map_);
}
bool CowReader::GetRawBytes(uint64_t offset, void* buffer, size_t len, size_t* read) {
diff --git a/fs_mgr/libsnapshot/cow_writer.cpp b/fs_mgr/libsnapshot/cow_writer.cpp
index 526fede..51505bf 100644
--- a/fs_mgr/libsnapshot/cow_writer.cpp
+++ b/fs_mgr/libsnapshot/cow_writer.cpp
@@ -76,9 +76,8 @@
return EmitLabel(label);
}
-bool ICowWriter::AddSequenceData(size_t /*num_ops*/, const uint32_t* /*data*/) {
- LOG(ERROR) << "AddSequenceData not yet implemented";
- return false;
+bool ICowWriter::AddSequenceData(size_t num_ops, const uint32_t* data) {
+ return EmitSequenceData(num_ops, data);
}
bool ICowWriter::ValidateNewBlock(uint64_t new_block) {
@@ -103,7 +102,7 @@
header_.footer_size = sizeof(CowFooter);
header_.op_size = sizeof(CowOperation);
header_.block_size = options_.block_size;
- header_.num_merge_ops = 0;
+ header_.num_merge_ops = options_.num_merge_ops;
header_.cluster_ops = options_.cluster_ops;
header_.buffer_size = 0;
footer_ = {};
@@ -337,6 +336,26 @@
return WriteOperation(op) && Sync();
}
+bool CowWriter::EmitSequenceData(size_t num_ops, const uint32_t* data) {
+ CHECK(!merge_in_progress_);
+ size_t to_add = 0;
+ size_t max_ops = std::numeric_limits<uint16_t>::max() / sizeof(uint32_t);
+ while (num_ops > 0) {
+ CowOperation op = {};
+ op.type = kCowSequenceOp;
+ op.source = next_data_pos_;
+ to_add = std::min(num_ops, max_ops);
+ op.data_length = static_cast<uint16_t>(to_add * sizeof(uint32_t));
+ if (!WriteOperation(op, data, op.data_length)) {
+ PLOG(ERROR) << "AddSequenceData: write failed";
+ return false;
+ }
+ num_ops -= to_add;
+ data += to_add;
+ }
+ return true;
+}
+
bool CowWriter::EmitCluster() {
CowOperation op = {};
op.type = kCowClusterOp;
diff --git a/fs_mgr/libsnapshot/include/libsnapshot/cow_format.h b/fs_mgr/libsnapshot/include/libsnapshot/cow_format.h
index 000e5e1..464046b 100644
--- a/fs_mgr/libsnapshot/include/libsnapshot/cow_format.h
+++ b/fs_mgr/libsnapshot/include/libsnapshot/cow_format.h
@@ -148,6 +148,7 @@
static constexpr uint8_t kCowZeroOp = 3;
static constexpr uint8_t kCowLabelOp = 4;
static constexpr uint8_t kCowClusterOp = 5;
+static constexpr uint8_t kCowSequenceOp = 7;
static constexpr uint8_t kCowFooterOp = -1;
static constexpr uint8_t kCowCompressNone = 0;
@@ -184,7 +185,10 @@
int64_t GetNextOpOffset(const CowOperation& op, uint32_t cluster_size);
int64_t GetNextDataOffset(const CowOperation& op, uint32_t cluster_size);
+// Ops that are internal to the Cow Format and not OTA data
bool IsMetadataOp(const CowOperation& op);
+// Ops that have dependencies on old blocks, and must take care in their merge order
+bool IsOrderedOp(const CowOperation& op);
} // namespace snapshot
} // namespace android
diff --git a/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h b/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
index 669e58a..05f7066 100644
--- a/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
+++ b/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
@@ -19,6 +19,7 @@
#include <functional>
#include <memory>
#include <optional>
+#include <unordered_map>
#include <android-base/unique_fd.h>
#include <libsnapshot/cow_format.h>
@@ -27,7 +28,6 @@
namespace snapshot {
class ICowOpIter;
-class ICowOpReverseIter;
// A ByteSink object handles requests for a buffer of a specific size. It
// always owns the underlying buffer. It's designed to minimize potential
@@ -75,8 +75,8 @@
// Return an iterator for retrieving CowOperation entries.
virtual std::unique_ptr<ICowOpIter> GetOpIter() = 0;
- // Return an reverse iterator for retrieving CowOperation entries.
- virtual std::unique_ptr<ICowOpReverseIter> GetRevOpIter() = 0;
+ // Return an iterator for retrieving CowOperation entries in merge order
+ virtual std::unique_ptr<ICowOpIter> GetRevMergeOpIter() = 0;
// Get decoded bytes from the data section, handling any decompression.
// All retrieved data is passed to the sink.
@@ -98,21 +98,6 @@
virtual void Next() = 0;
};
-// Reverse Iterate over a sequence of COW operations.
-class ICowOpReverseIter {
- public:
- virtual ~ICowOpReverseIter() {}
-
- // True if there are more items to read, false otherwise.
- virtual bool Done() = 0;
-
- // Read the current operation.
- virtual const CowOperation& Get() = 0;
-
- // Advance to the next item.
- virtual void Next() = 0;
-};
-
class CowReader : public ICowReader {
public:
CowReader();
@@ -135,25 +120,21 @@
// whose lifetime depends on the CowOpIter object; the return
// value of these will never be null.
std::unique_ptr<ICowOpIter> GetOpIter() override;
- std::unique_ptr<ICowOpReverseIter> GetRevOpIter() override;
+ std::unique_ptr<ICowOpIter> GetRevMergeOpIter() override;
bool ReadData(const CowOperation& op, IByteSink* sink) override;
bool GetRawBytes(uint64_t offset, void* buffer, size_t len, size_t* read);
- void InitializeMerge();
+ uint64_t get_num_total_data_ops() { return num_total_data_ops_; }
- // Number of copy, replace, and zero ops. Set if InitializeMerge is called.
- void set_total_data_ops(uint64_t size) { total_data_ops_ = size; }
- uint64_t total_data_ops() { return total_data_ops_; }
- // Number of copy ops. Set if InitializeMerge is called.
- void set_copy_ops(uint64_t size) { copy_ops_ = size; }
- uint64_t total_copy_ops() { return copy_ops_; }
+ uint64_t get_num_ordered_ops_to_merge() { return num_ordered_ops_to_merge_; }
void CloseCowFd() { owned_fd_ = {}; }
private:
bool ParseOps(std::optional<uint64_t> label);
+ bool PrepMergeOps();
uint64_t FindNumCopyops();
android::base::unique_fd owned_fd_;
@@ -163,8 +144,11 @@
uint64_t fd_size_;
std::optional<uint64_t> last_label_;
std::shared_ptr<std::vector<CowOperation>> ops_;
- uint64_t total_data_ops_;
- uint64_t copy_ops_;
+ std::shared_ptr<std::vector<uint32_t>> merge_op_blocks_;
+ std::shared_ptr<std::unordered_map<uint32_t, int>> block_map_;
+ uint64_t num_total_data_ops_;
+ uint64_t num_ordered_ops_to_merge_;
+ bool has_seq_ops_;
};
} // namespace snapshot
diff --git a/fs_mgr/libsnapshot/include/libsnapshot/cow_writer.h b/fs_mgr/libsnapshot/include/libsnapshot/cow_writer.h
index fbe6461..4a807fb 100644
--- a/fs_mgr/libsnapshot/include/libsnapshot/cow_writer.h
+++ b/fs_mgr/libsnapshot/include/libsnapshot/cow_writer.h
@@ -38,6 +38,9 @@
uint32_t cluster_ops = 200;
bool scratch_space = true;
+
+ // Preset the number of merged ops. Only useful for testing.
+ uint64_t num_merge_ops = 0;
};
// Interface for writing to a snapuserd COW. All operations are ordered; merges
@@ -85,6 +88,7 @@
virtual bool EmitRawBlocks(uint64_t new_block_start, const void* data, size_t size) = 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;
bool ValidateNewBlock(uint64_t new_block);
@@ -120,6 +124,7 @@
virtual bool EmitRawBlocks(uint64_t new_block_start, const void* data, size_t size) 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;
private:
bool EmitCluster();
diff --git a/fs_mgr/libsnapshot/include/libsnapshot/snapshot_writer.h b/fs_mgr/libsnapshot/include/libsnapshot/snapshot_writer.h
index bf5ce8b..c00dafa 100644
--- a/fs_mgr/libsnapshot/include/libsnapshot/snapshot_writer.h
+++ b/fs_mgr/libsnapshot/include/libsnapshot/snapshot_writer.h
@@ -76,6 +76,7 @@
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 EmitLabel(uint64_t label) override;
+ bool EmitSequenceData(size_t num_ops, const uint32_t* data) override;
private:
android::base::unique_fd cow_device_;
@@ -103,6 +104,7 @@
bool EmitZeroBlocks(uint64_t new_block_start, uint64_t num_blocks) 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;
private:
android::base::unique_fd snapshot_fd_;
diff --git a/fs_mgr/libsnapshot/inspect_cow.cpp b/fs_mgr/libsnapshot/inspect_cow.cpp
index 1dc61af..ed86c87 100644
--- a/fs_mgr/libsnapshot/inspect_cow.cpp
+++ b/fs_mgr/libsnapshot/inspect_cow.cpp
@@ -40,8 +40,18 @@
LOG(ERROR) << "\t -s Run Silent";
LOG(ERROR) << "\t -d Attempt to decompress";
LOG(ERROR) << "\t -b Show data for failed decompress\n";
+ LOG(ERROR) << "\t -m Show ops in reverse merge order\n";
}
+enum OpIter { Normal, RevMerge };
+
+struct Options {
+ bool silent;
+ bool decompress;
+ bool show_bad;
+ OpIter iter_type;
+};
+
// Sink that always appends to the end of a string.
class StringSink : public IByteSink {
public:
@@ -78,7 +88,7 @@
}
}
-static bool Inspect(const std::string& path, bool silent, bool decompress, bool show_bad) {
+static bool Inspect(const std::string& path, Options opt) {
android::base::unique_fd fd(open(path.c_str(), O_RDONLY));
if (fd < 0) {
PLOG(ERROR) << "open failed: " << path;
@@ -100,7 +110,7 @@
bool has_footer = false;
if (reader.GetFooter(&footer)) has_footer = true;
- if (!silent) {
+ if (!opt.silent) {
std::cout << "Major version: " << header.major_version << "\n";
std::cout << "Minor version: " << header.minor_version << "\n";
std::cout << "Header size: " << header.header_size << "\n";
@@ -116,19 +126,24 @@
}
}
- auto iter = reader.GetOpIter();
+ std::unique_ptr<ICowOpIter> iter;
+ if (opt.iter_type == Normal) {
+ iter = reader.GetOpIter();
+ } else if (opt.iter_type == RevMerge) {
+ iter = reader.GetRevMergeOpIter();
+ }
StringSink sink;
bool success = true;
while (!iter->Done()) {
const CowOperation& op = iter->Get();
- if (!silent) std::cout << op << "\n";
+ if (!opt.silent) std::cout << op << "\n";
- if (decompress && op.type == kCowReplaceOp && op.compression != kCowCompressNone) {
+ if (opt.decompress && op.type == kCowReplaceOp && op.compression != kCowCompressNone) {
if (!reader.ReadData(op, &sink)) {
std::cerr << "Failed to decompress for :" << op << "\n";
success = false;
- if (show_bad) ShowBad(reader, op);
+ if (opt.show_bad) ShowBad(reader, op);
}
sink.Reset();
}
@@ -144,19 +159,24 @@
int main(int argc, char** argv) {
int ch;
- bool silent = false;
- bool decompress = false;
- bool show_bad = false;
- while ((ch = getopt(argc, argv, "sdb")) != -1) {
+ struct android::snapshot::Options opt;
+ opt.silent = false;
+ opt.decompress = false;
+ opt.show_bad = false;
+ opt.iter_type = android::snapshot::Normal;
+ while ((ch = getopt(argc, argv, "sdbm")) != -1) {
switch (ch) {
case 's':
- silent = true;
+ opt.silent = true;
break;
case 'd':
- decompress = true;
+ opt.decompress = true;
break;
case 'b':
- show_bad = true;
+ opt.show_bad = true;
+ break;
+ case 'm':
+ opt.iter_type = android::snapshot::RevMerge;
break;
default:
android::snapshot::usage();
@@ -169,7 +189,7 @@
return 1;
}
- if (!android::snapshot::Inspect(argv[optind], silent, decompress, show_bad)) {
+ if (!android::snapshot::Inspect(argv[optind], opt)) {
return 1;
}
return 0;
diff --git a/fs_mgr/libsnapshot/snapshot_writer.cpp b/fs_mgr/libsnapshot/snapshot_writer.cpp
index 080f3b7..34b3e87 100644
--- a/fs_mgr/libsnapshot/snapshot_writer.cpp
+++ b/fs_mgr/libsnapshot/snapshot_writer.cpp
@@ -114,6 +114,10 @@
return cow_->AddLabel(label);
}
+bool CompressedSnapshotWriter::EmitSequenceData(size_t num_ops, const uint32_t* data) {
+ return cow_->AddSequenceData(num_ops, data);
+}
+
bool CompressedSnapshotWriter::Initialize() {
return cow_->Initialize(cow_device_);
}
@@ -183,6 +187,11 @@
return true;
}
+bool OnlineKernelSnapshotWriter::EmitSequenceData(size_t, const uint32_t*) {
+ // Not Needed
+ return true;
+}
+
std::unique_ptr<FileDescriptor> OnlineKernelSnapshotWriter::OpenReader() {
unique_fd fd(dup(snapshot_fd_.get()));
if (fd < 0) {
diff --git a/fs_mgr/libsnapshot/snapuserd.cpp b/fs_mgr/libsnapshot/snapuserd.cpp
index 03c2ef6..e578a76 100644
--- a/fs_mgr/libsnapshot/snapuserd.cpp
+++ b/fs_mgr/libsnapshot/snapuserd.cpp
@@ -266,14 +266,15 @@
void Snapuserd::CheckMergeCompletionStatus() {
if (!merge_initiated_) {
- SNAP_LOG(INFO) << "Merge was not initiated. Total-data-ops: " << reader_->total_data_ops();
+ SNAP_LOG(INFO) << "Merge was not initiated. Total-data-ops: "
+ << reader_->get_num_total_data_ops();
return;
}
struct CowHeader* ch = reinterpret_cast<struct CowHeader*>(mapped_addr_);
SNAP_LOG(INFO) << "Merge-status: Total-Merged-ops: " << ch->num_merge_ops
- << " Total-data-ops: " << reader_->total_data_ops();
+ << " Total-data-ops: " << reader_->get_num_total_data_ops();
}
/*
@@ -352,7 +353,6 @@
return false;
}
- reader_->InitializeMerge();
SNAP_LOG(DEBUG) << "Merge-ops: " << header.num_merge_ops;
if (!MmapMetadata()) {
@@ -361,7 +361,7 @@
}
// Initialize the iterator for reading metadata
- cowop_riter_ = reader_->GetRevOpIter();
+ std::unique_ptr<ICowOpIter> cowop_rm_iter = reader_->GetRevMergeOpIter();
exceptions_per_area_ = (CHUNK_SIZE << SECTOR_SHIFT) / sizeof(struct disk_exception);
@@ -379,23 +379,18 @@
// this memset will ensure that metadata read is completed.
memset(de_ptr.get(), 0, (exceptions_per_area_ * sizeof(struct disk_exception)));
- while (!cowop_riter_->Done()) {
- const CowOperation* cow_op = &cowop_riter_->Get();
+ while (!cowop_rm_iter->Done()) {
+ const CowOperation* cow_op = &cowop_rm_iter->Get();
struct disk_exception* de =
reinterpret_cast<struct disk_exception*>((char*)de_ptr.get() + offset);
- if (IsMetadataOp(*cow_op)) {
- cowop_riter_->Next();
- continue;
- }
-
metadata_found = true;
// This loop will handle all the replace and zero ops.
// We will handle the copy ops later as it requires special
// handling of assigning chunk-id's. Furthermore, we make
// sure that replace/zero and copy ops are not batch merged; hence,
// the bump in the chunk_id before break of this loop
- if (cow_op->type == kCowCopyOp) {
+ if (IsOrderedOp(*cow_op)) {
data_chunk_id = GetNextAllocatableChunkId(data_chunk_id);
break;
}
@@ -415,7 +410,7 @@
chunk_vec_.push_back(std::make_pair(ChunkToSector(data_chunk_id), cow_op));
num_ops += 1;
offset += sizeof(struct disk_exception);
- cowop_riter_->Next();
+ cowop_rm_iter->Next();
SNAP_LOG(DEBUG) << num_ops << ":"
<< " Old-chunk: " << de->old_chunk << " New-chunk: " << de->new_chunk;
@@ -432,7 +427,7 @@
sizeof(struct disk_exception));
memset(de_ptr.get(), 0, (exceptions_per_area_ * sizeof(struct disk_exception)));
- if (cowop_riter_->Done()) {
+ if (cowop_rm_iter->Done()) {
vec_.push_back(std::move(de_ptr));
}
}
@@ -445,18 +440,15 @@
std::map<uint64_t, const CowOperation*> map;
std::set<uint64_t> dest_blocks;
size_t pending_copy_ops = exceptions_per_area_ - num_ops;
- uint64_t total_copy_ops = reader_->total_copy_ops();
+ uint64_t total_copy_ops = reader_->get_num_ordered_ops_to_merge();
SNAP_LOG(DEBUG) << " Processing copy-ops at Area: " << vec_.size()
<< " Number of replace/zero ops completed in this area: " << num_ops
<< " Pending copy ops for this area: " << pending_copy_ops;
- while (!cowop_riter_->Done()) {
+
+ while (!cowop_rm_iter->Done()) {
do {
- const CowOperation* cow_op = &cowop_riter_->Get();
- if (IsMetadataOp(*cow_op)) {
- cowop_riter_->Next();
- continue;
- }
+ const CowOperation* cow_op = &cowop_rm_iter->Get();
// We have two cases specific cases:
//
@@ -572,8 +564,8 @@
map[cow_op->new_block] = cow_op;
dest_blocks.insert(cow_op->source);
prev_id = cow_op->new_block;
- cowop_riter_->Next();
- } while (!cowop_riter_->Done() && pending_copy_ops);
+ cowop_rm_iter->Next();
+ } while (!cowop_rm_iter->Done() && pending_copy_ops);
data_chunk_id = GetNextAllocatableChunkId(data_chunk_id);
SNAP_LOG(DEBUG) << "Batch Merge copy-ops of size: " << map.size()
@@ -611,7 +603,7 @@
sizeof(struct disk_exception));
memset(de_ptr.get(), 0, (exceptions_per_area_ * sizeof(struct disk_exception)));
- if (cowop_riter_->Done()) {
+ if (cowop_rm_iter->Done()) {
vec_.push_back(std::move(de_ptr));
SNAP_LOG(DEBUG) << "ReadMetadata() completed; Number of Areas: " << vec_.size();
}
@@ -661,7 +653,7 @@
<< " Replace-ops: " << replace_ops << " Zero-ops: " << zero_ops
<< " Copy-ops: " << copy_ops << " Areas: " << vec_.size()
<< " Num-ops-merged: " << header.num_merge_ops
- << " Total-data-ops: " << reader_->total_data_ops();
+ << " Total-data-ops: " << reader_->get_num_total_data_ops();
// Total number of sectors required for creating dm-user device
num_sectors_ = ChunkToSector(data_chunk_id);
diff --git a/fs_mgr/libsnapshot/snapuserd.h b/fs_mgr/libsnapshot/snapuserd.h
index 212c78e..5d86e4f 100644
--- a/fs_mgr/libsnapshot/snapuserd.h
+++ b/fs_mgr/libsnapshot/snapuserd.h
@@ -306,8 +306,6 @@
uint32_t exceptions_per_area_;
uint64_t num_sectors_;
- std::unique_ptr<ICowOpIter> cowop_iter_;
- std::unique_ptr<ICowOpReverseIter> cowop_riter_;
std::unique_ptr<CowReader> reader_;
// Vector of disk exception which is a