libsnapshot: Switch merge to CowRevMergeOpItr
This switches merge code over from using the old RevOpItr to the new
MergeRevOpItr. Since there are no other users, RevOpItr is no longer
needed.
Changed names of copy_ops_ and total_data_ops_ to more accurately
reflect their meaning.
Bug: 177104308
Test: cow_snapuserd_test
Change-Id: Ic053be4877cfdc86656551f5a3d5d95f3825f937
diff --git a/fs_mgr/libsnapshot/cow_reader.cpp b/fs_mgr/libsnapshot/cow_reader.cpp
index 57d108f..b3198a0 100644
--- a/fs_mgr/libsnapshot/cow_reader.cpp
+++ b/fs_mgr/libsnapshot/cow_reader.cpp
@@ -413,154 +413,26 @@
}
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);
}
- merge_op_blocks_ = merge_op_blocks;
+
+ 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;
-
- if (header_.num_merge_ops > 0) {
- merge_op_blocks_->erase(merge_op_blocks_->begin(),
- merge_op_blocks_->begin() + header_.num_merge_ops);
- }
+ merge_op_blocks_ = merge_op_blocks;
return true;
}
-void CowReader::InitializeMerge() {
- uint64_t num_copy_ops = 0;
-
- // 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++) {
- auto& current_op = ops_->data()[i];
- if (current_op.type != kCowCopyOp) {
- break;
- }
- num_copy_ops += 1;
- }
-
- return num_copy_ops;
-}
-
bool CowReader::GetHeader(CowHeader* header) {
*header = header_;
return true;
@@ -610,38 +482,6 @@
return (*op_iter_);
}
-class CowOpReverseIter final : public ICowOpIter {
- public:
- explicit CowOpReverseIter(std::shared_ptr<std::vector<CowOperation>> ops);
-
- bool Done() override;
- const CowOperation& Get() override;
- void Next() override;
-
- private:
- std::shared_ptr<std::vector<CowOperation>> ops_;
- std::vector<CowOperation>::reverse_iterator op_riter_;
-};
-
-CowOpReverseIter::CowOpReverseIter(std::shared_ptr<std::vector<CowOperation>> ops) {
- ops_ = ops;
- op_riter_ = ops_.get()->rbegin();
-}
-
-bool CowOpReverseIter::Done() {
- return op_riter_ == ops_.get()->rend();
-}
-
-void CowOpReverseIter::Next() {
- CHECK(!Done());
- op_riter_++;
-}
-
-const CowOperation& CowOpReverseIter::Get() {
- CHECK(!Done());
- return (*op_riter_);
-}
-
class CowRevMergeOpIter final : public ICowOpIter {
public:
explicit CowRevMergeOpIter(std::shared_ptr<std::vector<CowOperation>> ops,
@@ -687,10 +527,6 @@
return std::make_unique<CowOpIter>(ops_);
}
-std::unique_ptr<ICowOpIter> 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_);
}
diff --git a/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h b/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
index cdfe2f1..05f7066 100644
--- a/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
+++ b/fs_mgr/libsnapshot/include/libsnapshot/cow_reader.h
@@ -75,9 +75,6 @@
// 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<ICowOpIter> GetRevOpIter() = 0;
-
// Return an iterator for retrieving CowOperation entries in merge order
virtual std::unique_ptr<ICowOpIter> GetRevMergeOpIter() = 0;
@@ -123,21 +120,15 @@
// 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> 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_ = {}; }
@@ -155,8 +146,8 @@
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>> block_map_;
- uint64_t total_data_ops_;
- uint64_t copy_ops_;
+ uint64_t num_total_data_ops_;
+ uint64_t num_ordered_ops_to_merge_;
bool has_seq_ops_;
};
diff --git a/fs_mgr/libsnapshot/snapuserd.cpp b/fs_mgr/libsnapshot/snapuserd.cpp
index fc1a9b7..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
- std::unique_ptr<ICowOpIter> 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,16 +379,11 @@
// 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
@@ -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);