libsnapshot: Add function to verify merge sequence
This adds a function that verifies that the merge sequence does not
attempt to use blocks that have already been overwritten. It prints the
first such conflict to the logs.
Additionally, this adds a forwards merge iterator, and the ability to
ignore current progress in a merge for the purposes of verifying the
whole sequence.
This can be accessed via the VerifyMergeOps Function in Cow Reader, or
by using inspect_cow -v [COWFILE]
Include merged ops in inspect_cow listing with -a, and view ops in merge
order with -n
Bug: 200076590
Test: cow_api_test.InvalidMergeOrderTets
Change-Id: I893b9f8a8803cb6dd53225ec34224167b9fe2fda
diff --git a/fs_mgr/libsnapshot/cow_api_test.cpp b/fs_mgr/libsnapshot/cow_api_test.cpp
index 6066309..ba4044f 100644
--- a/fs_mgr/libsnapshot/cow_api_test.cpp
+++ b/fs_mgr/libsnapshot/cow_api_test.cpp
@@ -1171,18 +1171,18 @@
ASSERT_TRUE(writer.Initialize(cow_->fd));
ASSERT_TRUE(writer.AddSequenceData(6, sequence));
- ASSERT_TRUE(writer.AddCopy(6, 3));
+ ASSERT_TRUE(writer.AddCopy(6, 13));
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.AddCopy(3, 15));
+ ASSERT_TRUE(writer.AddCopy(2, 11));
ASSERT_TRUE(writer.AddZeroBlocks(4, 1));
ASSERT_TRUE(writer.AddZeroBlocks(9, 1));
- ASSERT_TRUE(writer.AddCopy(5, 6));
+ ASSERT_TRUE(writer.AddCopy(5, 16));
ASSERT_TRUE(writer.AddZeroBlocks(1, 1));
- ASSERT_TRUE(writer.AddCopy(10, 2));
- ASSERT_TRUE(writer.AddCopy(7, 4));
+ ASSERT_TRUE(writer.AddCopy(10, 12));
+ ASSERT_TRUE(writer.AddCopy(7, 14));
ASSERT_TRUE(writer.Finalize());
// New block in cow order is 6, 12, 8, 11, 3, 2, 4, 9, 5, 1, 10, 7
@@ -1219,12 +1219,12 @@
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.AddCopy(2, 11));
+ ASSERT_TRUE(writer.AddCopy(10, 12));
+ ASSERT_TRUE(writer.AddCopy(6, 13));
+ ASSERT_TRUE(writer.AddCopy(7, 14));
+ ASSERT_TRUE(writer.AddCopy(3, 15));
+ ASSERT_TRUE(writer.AddCopy(5, 16));
ASSERT_TRUE(writer.AddZeroBlocks(12, 1));
ASSERT_TRUE(writer.AddZeroBlocks(8, 1));
ASSERT_TRUE(writer.AddZeroBlocks(11, 1));
@@ -1260,6 +1260,39 @@
ASSERT_TRUE(iter->Done());
}
+TEST_F(CowTest, InvalidMergeOrderTest) {
+ CowOptions options;
+ options.cluster_ops = 5;
+ options.num_merge_ops = 1;
+ std::string data = "This is some data, believe it";
+ data.resize(options.block_size, '\0');
+ auto writer = std::make_unique<CowWriter>(options);
+ CowReader reader;
+
+ ASSERT_TRUE(writer->Initialize(cow_->fd));
+
+ ASSERT_TRUE(writer->AddCopy(3, 2));
+ ASSERT_TRUE(writer->AddCopy(2, 1));
+ ASSERT_TRUE(writer->AddLabel(1));
+ ASSERT_TRUE(writer->Finalize());
+ ASSERT_TRUE(reader.Parse(cow_->fd));
+ ASSERT_TRUE(reader.VerifyMergeOps());
+
+ ASSERT_TRUE(writer->InitializeAppend(cow_->fd, 1));
+ ASSERT_TRUE(writer->AddCopy(4, 2));
+ ASSERT_TRUE(writer->Finalize());
+ ASSERT_TRUE(reader.Parse(cow_->fd));
+ ASSERT_FALSE(reader.VerifyMergeOps());
+
+ writer = std::make_unique<CowWriter>(options);
+ ASSERT_TRUE(writer->Initialize(cow_->fd));
+ ASSERT_TRUE(writer->AddCopy(2, 1));
+ ASSERT_TRUE(writer->AddXorBlocks(3, &data, data.size(), 1, 1));
+ ASSERT_TRUE(writer->Finalize());
+ ASSERT_TRUE(reader.Parse(cow_->fd));
+ ASSERT_FALSE(reader.VerifyMergeOps());
+}
+
} // namespace snapshot
} // namespace android
diff --git a/fs_mgr/libsnapshot/cow_format.cpp b/fs_mgr/libsnapshot/cow_format.cpp
index 8e6bec7..94c4109 100644
--- a/fs_mgr/libsnapshot/cow_format.cpp
+++ b/fs_mgr/libsnapshot/cow_format.cpp
@@ -56,7 +56,10 @@
os << (int)op.compression << "?, ";
os << "data_length:" << op.data_length << ",\t";
os << "new_block:" << op.new_block << ",\t";
- os << "source:" << op.source << ")";
+ os << "source:" << op.source;
+ if (op.type == kCowXorOp)
+ os << " (block:" << op.source / BLOCK_SZ << " offset:" << op.source % BLOCK_SZ << ")";
+ os << ")";
return os;
}
diff --git a/fs_mgr/libsnapshot/cow_reader.cpp b/fs_mgr/libsnapshot/cow_reader.cpp
index 773d978..e8f0153 100644
--- a/fs_mgr/libsnapshot/cow_reader.cpp
+++ b/fs_mgr/libsnapshot/cow_reader.cpp
@@ -58,6 +58,7 @@
cow->last_label_ = last_label_;
cow->ops_ = ops_;
cow->merge_op_blocks_ = merge_op_blocks_;
+ cow->merge_op_start_ = merge_op_start_;
cow->block_map_ = block_map_;
cow->num_total_data_ops_ = num_total_data_ops_;
cow->num_ordered_ops_to_merge_ = num_ordered_ops_to_merge_;
@@ -468,8 +469,7 @@
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);
+ merge_op_start_ = header_.num_merge_ops;
}
block_map_ = block_map;
@@ -477,6 +477,44 @@
return true;
}
+bool CowReader::VerifyMergeOps() {
+ auto itr = GetMergeOpIter(true);
+ std::unordered_map<uint64_t, CowOperation> overwritten_blocks;
+ while (!itr->Done()) {
+ CowOperation op = itr->Get();
+ uint64_t block;
+ bool offset;
+ if (op.type == kCowCopyOp) {
+ block = op.source;
+ offset = false;
+ } else if (op.type == kCowXorOp) {
+ block = op.source / BLOCK_SZ;
+ offset = (op.source % BLOCK_SZ) != 0;
+ } else {
+ itr->Next();
+ continue;
+ }
+
+ CowOperation* overwrite = nullptr;
+ if (overwritten_blocks.count(block)) {
+ overwrite = &overwritten_blocks[block];
+ LOG(ERROR) << "Invalid Sequence! Block needed for op:\n"
+ << op << "\noverwritten by previously merged op:\n"
+ << *overwrite;
+ }
+ if (offset && overwritten_blocks.count(block + 1)) {
+ overwrite = &overwritten_blocks[block + 1];
+ LOG(ERROR) << "Invalid Sequence! Block needed for op:\n"
+ << op << "\noverwritten by previously merged op:\n"
+ << *overwrite;
+ }
+ if (overwrite != nullptr) return false;
+ overwritten_blocks[op.new_block] = op;
+ itr->Next();
+ }
+ return true;
+}
+
bool CowReader::GetHeader(CowHeader* header) {
*header = header_;
return true;
@@ -530,7 +568,8 @@
public:
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);
+ std::shared_ptr<std::unordered_map<uint32_t, int>> map,
+ uint64_t start);
bool Done() override;
const CowOperation& Get() override;
@@ -541,20 +580,67 @@
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_;
+ uint64_t start_;
};
-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) {
+class CowMergeOpIter final : public ICowOpIter {
+ public:
+ explicit CowMergeOpIter(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, uint64_t start);
+
+ bool Done() override;
+ const CowOperation& Get() override;
+ void Next() override;
+
+ private:
+ 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_;
+ std::vector<uint32_t>::iterator block_iter_;
+ uint64_t start_;
+};
+
+CowMergeOpIter::CowMergeOpIter(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,
+ uint64_t start) {
ops_ = ops;
merge_op_blocks_ = merge_op_blocks;
map_ = map;
+ start_ = start;
+
+ block_iter_ = merge_op_blocks->begin() + start;
+}
+
+bool CowMergeOpIter::Done() {
+ return block_iter_ == merge_op_blocks_->end();
+}
+
+void CowMergeOpIter::Next() {
+ CHECK(!Done());
+ block_iter_++;
+}
+
+const CowOperation& CowMergeOpIter::Get() {
+ CHECK(!Done());
+ return ops_->data()[map_->at(*block_iter_)];
+}
+
+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,
+ uint64_t start) {
+ ops_ = ops;
+ merge_op_blocks_ = merge_op_blocks;
+ map_ = map;
+ start_ = start;
block_riter_ = merge_op_blocks->rbegin();
}
bool CowRevMergeOpIter::Done() {
- return block_riter_ == merge_op_blocks_->rend();
+ return block_riter_ == merge_op_blocks_->rend() - start_;
}
void CowRevMergeOpIter::Next() {
@@ -571,8 +657,14 @@
return std::make_unique<CowOpIter>(ops_);
}
-std::unique_ptr<ICowOpIter> CowReader::GetRevMergeOpIter() {
- return std::make_unique<CowRevMergeOpIter>(ops_, merge_op_blocks_, block_map_);
+std::unique_ptr<ICowOpIter> CowReader::GetRevMergeOpIter(bool ignore_progress) {
+ return std::make_unique<CowRevMergeOpIter>(ops_, merge_op_blocks_, block_map_,
+ ignore_progress ? 0 : merge_op_start_);
+}
+
+std::unique_ptr<ICowOpIter> CowReader::GetMergeOpIter(bool ignore_progress) {
+ return std::make_unique<CowMergeOpIter>(ops_, merge_op_blocks_, block_map_,
+ ignore_progress ? 0 : merge_op_start_);
}
bool CowReader::GetRawBytes(uint64_t offset, void* buffer, size_t len, size_t* read) {
diff --git a/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h b/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
index 0786e82..4d09be9 100644
--- a/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
+++ b/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
@@ -75,8 +75,11 @@
// Return an iterator for retrieving CowOperation entries.
virtual std::unique_ptr<ICowOpIter> GetOpIter() = 0;
+ // Return an iterator for retrieving CowOperation entries in reverse merge order
+ virtual std::unique_ptr<ICowOpIter> GetRevMergeOpIter(bool ignore_progress) = 0;
+
// Return an iterator for retrieving CowOperation entries in merge order
- virtual std::unique_ptr<ICowOpIter> GetRevMergeOpIter() = 0;
+ virtual std::unique_ptr<ICowOpIter> GetMergeOpIter(bool ignore_progress) = 0;
// Get decoded bytes from the data section, handling any decompression.
// All retrieved data is passed to the sink.
@@ -109,6 +112,7 @@
bool Parse(android::base::borrowed_fd fd, std::optional<uint64_t> label = {});
bool InitForMerge(android::base::unique_fd&& fd);
+ bool VerifyMergeOps();
bool GetHeader(CowHeader* header) override;
bool GetFooter(CowFooter* footer) override;
@@ -120,7 +124,8 @@
// 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<ICowOpIter> GetRevMergeOpIter() override;
+ std::unique_ptr<ICowOpIter> GetRevMergeOpIter(bool ignore_progress = false) override;
+ std::unique_ptr<ICowOpIter> GetMergeOpIter(bool ignore_progress = false) override;
bool ReadData(const CowOperation& op, IByteSink* sink) override;
@@ -152,6 +157,7 @@
std::optional<uint64_t> last_label_;
std::shared_ptr<std::vector<CowOperation>> ops_;
std::shared_ptr<std::vector<uint32_t>> merge_op_blocks_;
+ uint64_t merge_op_start_;
std::shared_ptr<std::unordered_map<uint32_t, int>> block_map_;
uint64_t num_total_data_ops_;
uint64_t num_ordered_ops_to_merge_;
diff --git a/fs_mgr/libsnapshot/inspect_cow.cpp b/fs_mgr/libsnapshot/inspect_cow.cpp
index 3c0ba16..548ba00 100644
--- a/fs_mgr/libsnapshot/inspect_cow.cpp
+++ b/fs_mgr/libsnapshot/inspect_cow.cpp
@@ -44,10 +44,13 @@
LOG(ERROR) << "\t -b Show data for failed decompress";
LOG(ERROR) << "\t -l Show ops";
LOG(ERROR) << "\t -m Show ops in reverse merge order";
- LOG(ERROR) << "\t -o Shows sequence op block order\n";
+ LOG(ERROR) << "\t -n Show ops in merge order";
+ LOG(ERROR) << "\t -a Include merged ops in any merge order listing";
+ LOG(ERROR) << "\t -o Shows sequence op block order";
+ LOG(ERROR) << "\t -v Verifies merge order has no conflicts\n";
}
-enum OpIter { Normal, RevMerge };
+enum OpIter { Normal, RevMerge, Merge };
struct Options {
bool silent;
@@ -55,7 +58,9 @@
bool show_ops;
bool show_bad;
bool show_seq;
+ bool verify_sequence;
OpIter iter_type;
+ bool include_merged;
};
// Sink that always appends to the end of a string.
@@ -132,11 +137,21 @@
}
}
+ if (opt.verify_sequence) {
+ if (reader.VerifyMergeOps()) {
+ std::cout << "\nMerge sequence is consistent.\n";
+ } else {
+ std::cout << "\nMerge sequence is inconsistent!\n";
+ }
+ }
+
std::unique_ptr<ICowOpIter> iter;
if (opt.iter_type == Normal) {
iter = reader.GetOpIter();
} else if (opt.iter_type == RevMerge) {
- iter = reader.GetRevMergeOpIter();
+ iter = reader.GetRevMergeOpIter(opt.include_merged);
+ } else if (opt.iter_type == Merge) {
+ iter = reader.GetMergeOpIter(opt.include_merged);
}
StringSink sink;
bool success = true;
@@ -188,7 +203,9 @@
opt.decompress = false;
opt.show_bad = false;
opt.iter_type = android::snapshot::Normal;
- while ((ch = getopt(argc, argv, "sdbmol")) != -1) {
+ opt.verify_sequence = false;
+ opt.include_merged = false;
+ while ((ch = getopt(argc, argv, "sdbmnolva")) != -1) {
switch (ch) {
case 's':
opt.silent = true;
@@ -202,12 +219,21 @@
case 'm':
opt.iter_type = android::snapshot::RevMerge;
break;
+ case 'n':
+ opt.iter_type = android::snapshot::Merge;
+ break;
case 'o':
opt.show_seq = true;
break;
case 'l':
opt.show_ops = true;
break;
+ case 'v':
+ opt.verify_sequence = true;
+ break;
+ case 'a':
+ opt.include_merged = true;
+ break;
default:
android::snapshot::usage();
}