payload_generator/merge_sequence_generator.cc - platform/system/update_engine - Git at Google

 //
 // Copyright (C) 2020 The Android Open Source Project
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //      http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.
 //

 #include "update_engine/payload_generator/merge_sequence_generator.h"

 #include <algorithm>
 #include <limits>

 #include "update_engine/payload_generator/extent_ranges.h"
 #include "update_engine/payload_generator/extent_utils.h"
 #include "update_engine/update_metadata.pb.h"

 namespace chromeos_update_engine {

 CowMergeOperation CreateCowMergeOperation(const Extent& src_extent,
                                           const Extent& dst_extent,
                                           CowMergeOperation::Type op_type,
                                           uint32_t src_offset) {
   CowMergeOperation ret;
   ret.set_type(op_type);
   *ret.mutable_src_extent() = src_extent;
   *ret.mutable_dst_extent() = dst_extent;
   ret.set_src_offset(src_offset);
   return ret;
 }

 std::ostream& operator<<(std::ostream& os,
                          const CowMergeOperation& merge_operation) {
   os << "CowMergeOperation src extent: "
      << ExtentsToString({merge_operation.src_extent()})
      << ", dst extent: " << ExtentsToString({merge_operation.dst_extent()});
   if (merge_operation.has_src_offset()) {
     os << ", src offset: " << merge_operation.src_offset();
   }
   os << " op_type: ";
   if (merge_operation.type() == CowMergeOperation::COW_COPY) {
     os << "COW_COPY";
   } else if (merge_operation.type() == CowMergeOperation::COW_XOR) {
     os << "COW_XOR";
   } else {
     os << merge_operation.type();
   }
   return os;
 }

 // The OTA generation guarantees that all blocks in the dst extent will be
 // written only once. So we can use it to order the CowMergeOperation.
 bool operator<(const CowMergeOperation& op1, const CowMergeOperation& op2) {
   return op1.dst_extent().start_block() < op2.dst_extent().start_block();
 }

 bool operator==(const CowMergeOperation& op1, const CowMergeOperation& op2) {
   return op1.type() == op2.type() && op1.src_extent() == op2.src_extent() &&
          op1.dst_extent() == op2.dst_extent();
 }

 template <typename T>
 constexpr T GetDifference(T first, T second) {
   T abs_diff = (first > second) ? (first - second) : (second - first);
   return abs_diff;
 }

 CowMergeOperation::Type GetCowOpType(InstallOperation::Type install_op_type) {
   switch (install_op_type) {
     case InstallOperation::SOURCE_COPY:
       return CowMergeOperation::COW_COPY;
     case InstallOperation::SOURCE_BSDIFF:
     case InstallOperation::BROTLI_BSDIFF:
     case InstallOperation::PUFFDIFF:
       return CowMergeOperation::COW_XOR;
     default:
       CHECK(false) << "Unknown install op type: " << install_op_type;
       return CowMergeOperation::COW_REPLACE;
   }
 }

 void SplitSelfOverlapping(const Extent& src_extent,
                           const Extent& dst_extent,
                           std::vector<CowMergeOperation>* sequence) {
   CHECK_EQ(src_extent.num_blocks(), dst_extent.num_blocks());
   if (src_extent.start_block() == dst_extent.start_block()) {
     sequence->emplace_back(CreateCowMergeOperation(
         src_extent, dst_extent, CowMergeOperation::COW_COPY));
     return;
   }

   const size_t diff =
       GetDifference(src_extent.start_block(), dst_extent.start_block());
   for (size_t i = 0; i < src_extent.num_blocks(); i += diff) {
     auto num_blocks = std::min<size_t>(diff, src_extent.num_blocks() - i);
     sequence->emplace_back(CreateCowMergeOperation(
         ExtentForRange(i + src_extent.start_block(), num_blocks),
         ExtentForRange(i + dst_extent.start_block(), num_blocks),
         CowMergeOperation::COW_COPY));
   }
 }

 static bool ProcessXorOps(std::vector<CowMergeOperation>* sequence,
                           const AnnotatedOperation& aop) {
   const auto size_before = sequence->size();
   sequence->insert(sequence->end(), aop.xor_ops.begin(), aop.xor_ops.end());
   std::for_each(
       sequence->begin() + size_before,
       sequence->end(),
       [](CowMergeOperation& op) {
         CHECK_EQ(op.type(), CowMergeOperation::COW_XOR);
         // If |src_offset| is greater than 0, then we are reading 1
         // extra block at the end of src_extent. This dependency must
         // be honored during merge sequence generation, or we can end
         // up with a corrupted device after merge.
         if (op.src_offset() > 0) {
           if (op.src_extent().num_blocks() == op.dst_extent().num_blocks()) {
             op.mutable_src_extent()->set_num_blocks(
                 op.src_extent().num_blocks() + 1);
           }
           CHECK_EQ(op.src_extent().num_blocks(),
                    op.dst_extent().num_blocks() + 1);
         }
         CHECK_NE(op.src_extent().start_block(),
                  std::numeric_limits<uint64_t>::max());
       });
   return true;
 }

 static bool ProcessCopyOps(std::vector<CowMergeOperation>* sequence,
                            const AnnotatedOperation& aop) {
   CHECK_EQ(GetCowOpType(aop.op.type()), CowMergeOperation::COW_COPY);
   if (aop.op.dst_extents().size() != 1) {
     std::vector<Extent> out_extents;
     ExtentsToVector(aop.op.dst_extents(), &out_extents);
     LOG(ERROR)
         << "The dst extents for source_copy are expected to be contiguous,"
         << " dst extents: " << ExtentsToString(out_extents);
     return false;
   }
   // Split the source extents.
   size_t used_blocks = 0;
   for (const auto& src_extent : aop.op.src_extents()) {
     // The dst_extent in the merge sequence will be a subset of
     // InstallOperation's dst_extent. This will simplify the OTA -> COW
     // conversion when we install the payload.
     Extent dst_extent =
         ExtentForRange(aop.op.dst_extents(0).start_block() + used_blocks,
                        src_extent.num_blocks());
     // Self-overlapping operation, must split into multiple non
     // self-overlapping ops
     if (ExtentRanges::ExtentsOverlap(src_extent, dst_extent)) {
       SplitSelfOverlapping(src_extent, dst_extent, sequence);
     } else {
       sequence->emplace_back(CreateCowMergeOperation(
           src_extent, dst_extent, CowMergeOperation::COW_COPY));
     }
     used_blocks += src_extent.num_blocks();
   }

   if (used_blocks != aop.op.dst_extents(0).num_blocks()) {
     LOG(ERROR) << "Number of blocks in src extents doesn't equal to the"
                << " ones in the dst extents, src blocks " << used_blocks
                << ", dst blocks " << aop.op.dst_extents(0).num_blocks();
     return false;
   }
   return true;
 }

 std::unique_ptr<MergeSequenceGenerator> MergeSequenceGenerator::Create(
     const std::vector<AnnotatedOperation>& aops,
     std::string_view partition_name) {
   std::vector<CowMergeOperation> sequence;

   for (const auto& aop : aops) {
     if (aop.op.type() == InstallOperation::SOURCE_COPY) {
       if (!ProcessCopyOps(&sequence, aop)) {
         return nullptr;
       }
     } else if (!aop.xor_ops.empty()) {
       if (!ProcessXorOps(&sequence, aop)) {
         return nullptr;
       }
     }
   }

   return std::unique_ptr<MergeSequenceGenerator>(
       new MergeSequenceGenerator(sequence, partition_name));
 }

 template <typename T>
 CowMergeOperation MaxOutDegree(
     const T& nodes,
     const std::map<CowMergeOperation, std::set<CowMergeOperation>>&
         merge_after) {
   // Rationale for this algorithm:
   // We only need to remove nodes from the graph if the graph contains a cycle.
   // Any graph of N nodes has cycle iff number of edges >= N.
   // So, to restore the graph back to an acyclic state, we need to keep removing
   // edges until we have <N edges left. To minimize the number of nodes removed,
   // we always remove the node with maximum out degree.
   CowMergeOperation best;
   size_t max_out_degree = 0;
   const auto has_xor =
       std::any_of(nodes.begin(),
                   nodes.end(),
                   [&merge_after](const CowMergeOperation& node) {
                     if (node.type() != CowMergeOperation::COW_XOR) {
                       return false;
                     }
                     auto it = merge_after.find(node);
                     if (it == merge_after.end()) {
                       return false;
                     }
                     return it->second.size() > 0;
                   });
   for (const auto& op : nodes) {
     if (has_xor && op.type() != CowMergeOperation::COW_XOR) {
       continue;
     }
     const auto out_degree = merge_after.at(op).size();
     if (out_degree > max_out_degree) {
       best = op;
       max_out_degree = out_degree;
     } else if (out_degree == max_out_degree) {
       if (op.src_extent().num_blocks() < best.src_extent().num_blocks()) {
         best = op;
       }
     }
   }
   CHECK_NE(max_out_degree, 0UL);
   return best;
 }

 template <typename T>
 struct MapKeyIterator {
   MapKeyIterator<T>& operator++() {
     ++it;
     return *this;
   }
   MapKeyIterator<T>& operator--() {
     --it;
     return *this;
   }
   bool operator==(const MapKeyIterator<T>& rhs) const { return it == rhs.it; }
   bool operator!=(const MapKeyIterator<T>& rhs) const { return it != rhs.it; }
   auto&& operator->() const { return it->first; }
   auto&& operator*() const { return it->first; }
   T it;
 };

 template <typename T, typename U>
 struct MapKeyRange {
   auto begin() const {
     return MapKeyIterator<typename std::map<T, U>::const_iterator>{map.begin()};
   }
   auto end() const {
     return MapKeyIterator<typename std::map<T, U>::const_iterator>{map.end()};
   }
   std::map<T, U> map;
 };

 CowMergeOperation MaxOutDegree(
     const std::map<CowMergeOperation, int>& incoming_edges,
     const std::map<CowMergeOperation, std::set<CowMergeOperation>>&
         merge_after) {
   return MaxOutDegree(MapKeyRange<CowMergeOperation, int>{incoming_edges},
                       merge_after);
 }

 // Given a potentially cyclic graph, return a node to remove to break cycles
 // |incoming_edges| stores nodes' in degree, and |merge_after| is an outgoing
 // edge list. For example, |merge_after[a]| returns all nodes which `a` has an
 // out going edge to.
 // The only requirement of this function is to return a node which is in
 // |incoming_edges| . As long as this is satisfied, merge sequence generation
 // will work. Caller will keep removing nodes returned by this function until
 // the graph has no cycles. However, the choice of which node to remove can
 // greatly impact COW sizes. Nodes removed from the graph will be converted to a
 // COW_REPLACE operation, taking more disk space. So this function should try to
 // pick a node which minimizes number of nodes we have to remove. (Modulo the
 // weight of each node, which is how many blocks a CowMergeOperation touches)
 CowMergeOperation PickConvertToRaw(
     const std::map<CowMergeOperation, int>& incoming_edges,
     const std::map<CowMergeOperation, std::set<CowMergeOperation>>&
         merge_after) {
   return MaxOutDegree(incoming_edges, merge_after);
 }

 std::map<CowMergeOperation, std::set<CowMergeOperation>>
 MergeSequenceGenerator::FindDependency(
     const std::vector<CowMergeOperation>& operations) {
   LOG(INFO) << "Finding dependencies";

   // Since the OTA operation may reuse some source blocks, use the binary
   // search on sorted dst extents to find overlaps.
   std::map<CowMergeOperation, std::set<CowMergeOperation>> merge_after;
   for (const auto& op : operations) {
     // lower bound (inclusive): dst extent's end block >= src extent's start
     // block.
     const auto lower_it = std::lower_bound(
         operations.begin(),
         operations.end(),
         op,
         [](const CowMergeOperation& it, const CowMergeOperation& op) {
           auto dst_end_block =
               it.dst_extent().start_block() + it.dst_extent().num_blocks() - 1;
           return dst_end_block < op.src_extent().start_block();
         });
     // upper bound: dst extent's start block > src extent's end block
     const auto upper_it = std::upper_bound(
         lower_it,
         operations.end(),
         op,
         [](const CowMergeOperation& op, const CowMergeOperation& it) {
           auto src_end_block =
               op.src_extent().start_block() + op.src_extent().num_blocks() - 1;
           return src_end_block < it.dst_extent().start_block();
         });

     // TODO(xunchang) skip inserting the empty set to merge_after.
     if (lower_it == upper_it) {
       merge_after.insert({op, {}});
     } else {
       std::set<CowMergeOperation> operations(lower_it, upper_it);
       auto it = operations.find(op);
       if (it != operations.end()) {
         LOG(INFO) << "Self overlapping " << op;
         operations.erase(it);
       }
       auto ret = merge_after.emplace(op, std::move(operations));
       // Check the insertion indeed happens.
       CHECK(ret.second) << op;
     }
   }

   return merge_after;
 }

 bool MergeSequenceGenerator::Generate(
     std::vector<CowMergeOperation>* sequence) const {
   sequence->clear();

   LOG(INFO) << "Generating sequence";

   // Use the non-DFS version of the topology sort. So we can control the
   // operations to discard to break cycles; thus yielding a deterministic
   // sequence.
   std::map<CowMergeOperation, int> incoming_edges;
   for (const auto& it : merge_after_) {
     for (const auto& blocked : it.second) {
       // Value is default initialized to 0.
       incoming_edges[blocked] += 1;
     }
   }

   // Technically, we can use std::unordered_set or just a std::vector. but
   // std::set gives the benefit where operations are sorted by dst blocks. This
   // will ensure that operations that do not have dependency constraints appear
   // in increasing block order. Such order would help snapuserd batch merges and
   // improve boot time, but isn't strictly needed for correctness.
   std::set<CowMergeOperation> free_operations;
   for (const auto& op : operations_) {
     if (incoming_edges.find(op) == incoming_edges.end()) {
       free_operations.insert(op);
     }
   }

   std::vector<CowMergeOperation> merge_sequence;
   std::set<CowMergeOperation> convert_to_raw;
   while (!incoming_edges.empty()) {
     if (!free_operations.empty()) {
       merge_sequence.insert(
           merge_sequence.end(), free_operations.begin(), free_operations.end());
     } else {
       auto to_convert = PickConvertToRaw(incoming_edges, merge_after_);
       // The operation we pick must be one of the nodes not already in merge
       // sequence.
       CHECK(incoming_edges.find(to_convert) != incoming_edges.end());

       free_operations.insert(to_convert);
       convert_to_raw.insert(to_convert);
       LOG(INFO) << "Converting operation to raw " << to_convert;
     }

     std::set<CowMergeOperation> next_free_operations;
     for (const auto& op : free_operations) {
       incoming_edges.erase(op);

       // Now that this particular operation is merged, other operations
       // blocked by this one may be free. Decrement the count of blocking
       // operations, and set up the free operations for the next iteration.
       for (const auto& blocked : merge_after_.at(op)) {
         auto it = incoming_edges.find(blocked);
         if (it == incoming_edges.end()) {
           continue;
         }

         auto blocking_transfer_count = &it->second;
         if (*blocking_transfer_count <= 0) {
           LOG(ERROR) << "Unexpected count in merge after map "
                      << blocking_transfer_count;
           return false;
         }
         // This operation is no longer blocked by anyone. Add it to the merge
         // sequence in the next iteration.
         *blocking_transfer_count -= 1;
         if (*blocking_transfer_count == 0) {
           next_free_operations.insert(blocked);
         }
       }
     }

     LOG(INFO) << "Remaining transfers " << incoming_edges.size()
               << ", free transfers " << free_operations.size()
               << ", merge_sequence size " << merge_sequence.size();
     free_operations = std::move(next_free_operations);
   }

   if (!free_operations.empty()) {
     merge_sequence.insert(
         merge_sequence.end(), free_operations.begin(), free_operations.end());
   }

   CHECK_EQ(operations_.size(), merge_sequence.size() + convert_to_raw.size());

   size_t blocks_in_sequence = 0;
   for (const CowMergeOperation& transfer : merge_sequence) {
     blocks_in_sequence += transfer.dst_extent().num_blocks();
   }

   size_t blocks_in_raw = 0;
   for (const CowMergeOperation& transfer : convert_to_raw) {
     blocks_in_raw += transfer.dst_extent().num_blocks();
   }

   LOG(INFO) << "Blocks in merge sequence " << blocks_in_sequence
             << ", blocks in raw " << blocks_in_raw << ", partition "
             << partition_name_;
   if (!ValidateSequence(merge_sequence)) {
     LOG(ERROR) << "Invalid Sequence";
     return false;
   }

   *sequence = std::move(merge_sequence);
   return true;
 }

 bool MergeSequenceGenerator::ValidateSequence(
     const std::vector<CowMergeOperation>& sequence) {
   LOG(INFO) << "Validating merge sequence";
   ExtentRanges visited;
   for (const auto& op : sequence) {
     // If |src_offset| is greater than zero, dependency should include 1 extra
     // block at end of src_extent, as the OP actually references data past
     // original src_extent.
     if (op.src_offset() > 0) {
       CHECK_EQ(op.src_extent().num_blocks(), op.dst_extent().num_blocks() + 1)
           << op;
     } else {
       CHECK_EQ(op.src_extent().num_blocks(), op.dst_extent().num_blocks())
           << op;
     }
     if (visited.OverlapsWithExtent(op.src_extent())) {
       LOG(ERROR) << "Transfer violates the merge sequence " << op
                  << "Visited extent ranges: ";
       visited.Dump();
       return false;
     }

     CHECK(!visited.OverlapsWithExtent(op.dst_extent()))
         << "dst extent should write only once.";
     visited.AddExtent(op.dst_extent());
   }

   return true;
 }

 }  // namespace chromeos_update_engine
	//
	// Copyright (C) 2020 The Android Open Source Project
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.
	//

	#include "update_engine/payload_generator/merge_sequence_generator.h"

	#include <algorithm>
	#include <limits>

	#include "update_engine/payload_generator/extent_ranges.h"
	#include "update_engine/payload_generator/extent_utils.h"
	#include "update_engine/update_metadata.pb.h"

	namespace chromeos_update_engine {

	CowMergeOperation CreateCowMergeOperation(const Extent& src_extent,
	const Extent& dst_extent,
	CowMergeOperation::Type op_type,
	uint32_t src_offset) {
	CowMergeOperation ret;
	ret.set_type(op_type);
	*ret.mutable_src_extent() = src_extent;
	*ret.mutable_dst_extent() = dst_extent;
	ret.set_src_offset(src_offset);
	return ret;
	}

	std::ostream& operator<<(std::ostream& os,
	const CowMergeOperation& merge_operation) {
	os << "CowMergeOperation src extent: "
	<< ExtentsToString({merge_operation.src_extent()})
	<< ", dst extent: " << ExtentsToString({merge_operation.dst_extent()});
	if (merge_operation.has_src_offset()) {
	os << ", src offset: " << merge_operation.src_offset();
	}
	os << " op_type: ";
	if (merge_operation.type() == CowMergeOperation::COW_COPY) {
	os << "COW_COPY";
	} else if (merge_operation.type() == CowMergeOperation::COW_XOR) {
	os << "COW_XOR";
	} else {
	os << merge_operation.type();
	}
	return os;
	}

	// The OTA generation guarantees that all blocks in the dst extent will be
	// written only once. So we can use it to order the CowMergeOperation.
	bool operator<(const CowMergeOperation& op1, const CowMergeOperation& op2) {
	return op1.dst_extent().start_block() < op2.dst_extent().start_block();
	}

	bool operator==(const CowMergeOperation& op1, const CowMergeOperation& op2) {
	return op1.type() == op2.type() && op1.src_extent() == op2.src_extent() &&
	op1.dst_extent() == op2.dst_extent();
	}

	template <typename T>
	constexpr T GetDifference(T first, T second) {
	T abs_diff = (first > second) ? (first - second) : (second - first);
	return abs_diff;
	}

	CowMergeOperation::Type GetCowOpType(InstallOperation::Type install_op_type) {
	switch (install_op_type) {
	case InstallOperation::SOURCE_COPY:
	return CowMergeOperation::COW_COPY;
	case InstallOperation::SOURCE_BSDIFF:
	case InstallOperation::BROTLI_BSDIFF:
	case InstallOperation::PUFFDIFF:
	return CowMergeOperation::COW_XOR;
	default:
	CHECK(false) << "Unknown install op type: " << install_op_type;
	return CowMergeOperation::COW_REPLACE;
	}
	}

	void SplitSelfOverlapping(const Extent& src_extent,
	const Extent& dst_extent,
	std::vector<CowMergeOperation>* sequence) {
	CHECK_EQ(src_extent.num_blocks(), dst_extent.num_blocks());
	if (src_extent.start_block() == dst_extent.start_block()) {
	sequence->emplace_back(CreateCowMergeOperation(
	src_extent, dst_extent, CowMergeOperation::COW_COPY));
	return;
	}

	const size_t diff =
	GetDifference(src_extent.start_block(), dst_extent.start_block());
	for (size_t i = 0; i < src_extent.num_blocks(); i += diff) {
	auto num_blocks = std::min<size_t>(diff, src_extent.num_blocks() - i);
	sequence->emplace_back(CreateCowMergeOperation(
	ExtentForRange(i + src_extent.start_block(), num_blocks),
	ExtentForRange(i + dst_extent.start_block(), num_blocks),
	CowMergeOperation::COW_COPY));
	}
	}

	static bool ProcessXorOps(std::vector<CowMergeOperation>* sequence,
	const AnnotatedOperation& aop) {
	const auto size_before = sequence->size();
	sequence->insert(sequence->end(), aop.xor_ops.begin(), aop.xor_ops.end());
	std::for_each(
	sequence->begin() + size_before,
	sequence->end(),
	[](CowMergeOperation& op) {
	CHECK_EQ(op.type(), CowMergeOperation::COW_XOR);
	// If \|src_offset\| is greater than 0, then we are reading 1
	// extra block at the end of src_extent. This dependency must
	// be honored during merge sequence generation, or we can end
	// up with a corrupted device after merge.
	if (op.src_offset() > 0) {
	if (op.src_extent().num_blocks() == op.dst_extent().num_blocks()) {
	op.mutable_src_extent()->set_num_blocks(
	op.src_extent().num_blocks() + 1);
	}
	CHECK_EQ(op.src_extent().num_blocks(),
	op.dst_extent().num_blocks() + 1);
	}
	CHECK_NE(op.src_extent().start_block(),
	std::numeric_limits<uint64_t>::max());
	});
	return true;
	}

	static bool ProcessCopyOps(std::vector<CowMergeOperation>* sequence,
	const AnnotatedOperation& aop) {
	CHECK_EQ(GetCowOpType(aop.op.type()), CowMergeOperation::COW_COPY);
	if (aop.op.dst_extents().size() != 1) {
	std::vector<Extent> out_extents;
	ExtentsToVector(aop.op.dst_extents(), &out_extents);
	LOG(ERROR)
	<< "The dst extents for source_copy are expected to be contiguous,"
	<< " dst extents: " << ExtentsToString(out_extents);
	return false;
	}
	// Split the source extents.
	size_t used_blocks = 0;
	for (const auto& src_extent : aop.op.src_extents()) {
	// The dst_extent in the merge sequence will be a subset of
	// InstallOperation's dst_extent. This will simplify the OTA -> COW
	// conversion when we install the payload.
	Extent dst_extent =
	ExtentForRange(aop.op.dst_extents(0).start_block() + used_blocks,
	src_extent.num_blocks());
	// Self-overlapping operation, must split into multiple non
	// self-overlapping ops
	if (ExtentRanges::ExtentsOverlap(src_extent, dst_extent)) {
	SplitSelfOverlapping(src_extent, dst_extent, sequence);
	} else {
	sequence->emplace_back(CreateCowMergeOperation(
	src_extent, dst_extent, CowMergeOperation::COW_COPY));
	}
	used_blocks += src_extent.num_blocks();
	}

	if (used_blocks != aop.op.dst_extents(0).num_blocks()) {
	LOG(ERROR) << "Number of blocks in src extents doesn't equal to the"
	<< " ones in the dst extents, src blocks " << used_blocks
	<< ", dst blocks " << aop.op.dst_extents(0).num_blocks();
	return false;
	}
	return true;
	}

	std::unique_ptr<MergeSequenceGenerator> MergeSequenceGenerator::Create(
	const std::vector<AnnotatedOperation>& aops,
	std::string_view partition_name) {
	std::vector<CowMergeOperation> sequence;

	for (const auto& aop : aops) {
	if (aop.op.type() == InstallOperation::SOURCE_COPY) {
	if (!ProcessCopyOps(&sequence, aop)) {
	return nullptr;
	}
	} else if (!aop.xor_ops.empty()) {
	if (!ProcessXorOps(&sequence, aop)) {
	return nullptr;
	}
	}
	}

	return std::unique_ptr<MergeSequenceGenerator>(
	new MergeSequenceGenerator(sequence, partition_name));
	}

	template <typename T>
	CowMergeOperation MaxOutDegree(
	const T& nodes,
	const std::map<CowMergeOperation, std::set<CowMergeOperation>>&
	merge_after) {
	// Rationale for this algorithm:
	// We only need to remove nodes from the graph if the graph contains a cycle.
	// Any graph of N nodes has cycle iff number of edges >= N.
	// So, to restore the graph back to an acyclic state, we need to keep removing
	// edges until we have <N edges left. To minimize the number of nodes removed,
	// we always remove the node with maximum out degree.
	CowMergeOperation best;
	size_t max_out_degree = 0;
	const auto has_xor =
	std::any_of(nodes.begin(),
	nodes.end(),
	[&merge_after](const CowMergeOperation& node) {
	if (node.type() != CowMergeOperation::COW_XOR) {
	return false;
	}
	auto it = merge_after.find(node);
	if (it == merge_after.end()) {
	return false;
	}
	return it->second.size() > 0;
	});
	for (const auto& op : nodes) {
	if (has_xor && op.type() != CowMergeOperation::COW_XOR) {
	continue;
	}
	const auto out_degree = merge_after.at(op).size();
	if (out_degree > max_out_degree) {
	best = op;
	max_out_degree = out_degree;
	} else if (out_degree == max_out_degree) {
	if (op.src_extent().num_blocks() < best.src_extent().num_blocks()) {
	best = op;
	}
	}
	}
	CHECK_NE(max_out_degree, 0UL);
	return best;
	}

	template <typename T>
	struct MapKeyIterator {
	MapKeyIterator<T>& operator++() {
	++it;
	return *this;
	}
	MapKeyIterator<T>& operator--() {
	--it;
	return *this;
	}
	bool operator==(const MapKeyIterator<T>& rhs) const { return it == rhs.it; }
	bool operator!=(const MapKeyIterator<T>& rhs) const { return it != rhs.it; }
	auto&& operator->() const { return it->first; }
	auto&& operator*() const { return it->first; }
	T it;
	};

	template <typename T, typename U>
	struct MapKeyRange {
	auto begin() const {
	return MapKeyIterator<typename std::map<T, U>::const_iterator>{map.begin()};
	}
	auto end() const {
	return MapKeyIterator<typename std::map<T, U>::const_iterator>{map.end()};
	}
	std::map<T, U> map;
	};

	CowMergeOperation MaxOutDegree(
	const std::map<CowMergeOperation, int>& incoming_edges,
	const std::map<CowMergeOperation, std::set<CowMergeOperation>>&
	merge_after) {
	return MaxOutDegree(MapKeyRange<CowMergeOperation, int>{incoming_edges},
	merge_after);
	}

	// Given a potentially cyclic graph, return a node to remove to break cycles
	// \|incoming_edges\| stores nodes' in degree, and \|merge_after\| is an outgoing
	// edge list. For example, \|merge_after[a]\| returns all nodes which `a` has an
	// out going edge to.
	// The only requirement of this function is to return a node which is in
	// \|incoming_edges\| . As long as this is satisfied, merge sequence generation
	// will work. Caller will keep removing nodes returned by this function until
	// the graph has no cycles. However, the choice of which node to remove can
	// greatly impact COW sizes. Nodes removed from the graph will be converted to a
	// COW_REPLACE operation, taking more disk space. So this function should try to
	// pick a node which minimizes number of nodes we have to remove. (Modulo the
	// weight of each node, which is how many blocks a CowMergeOperation touches)
	CowMergeOperation PickConvertToRaw(
	const std::map<CowMergeOperation, int>& incoming_edges,
	const std::map<CowMergeOperation, std::set<CowMergeOperation>>&
	merge_after) {
	return MaxOutDegree(incoming_edges, merge_after);
	}

	std::map<CowMergeOperation, std::set<CowMergeOperation>>
	MergeSequenceGenerator::FindDependency(
	const std::vector<CowMergeOperation>& operations) {
	LOG(INFO) << "Finding dependencies";

	// Since the OTA operation may reuse some source blocks, use the binary
	// search on sorted dst extents to find overlaps.
	std::map<CowMergeOperation, std::set<CowMergeOperation>> merge_after;
	for (const auto& op : operations) {
	// lower bound (inclusive): dst extent's end block >= src extent's start
	// block.
	const auto lower_it = std::lower_bound(
	operations.begin(),
	operations.end(),
	op,
	[](const CowMergeOperation& it, const CowMergeOperation& op) {
	auto dst_end_block =
	it.dst_extent().start_block() + it.dst_extent().num_blocks() - 1;
	return dst_end_block < op.src_extent().start_block();
	});
	// upper bound: dst extent's start block > src extent's end block
	const auto upper_it = std::upper_bound(
	lower_it,
	operations.end(),
	op,
	[](const CowMergeOperation& op, const CowMergeOperation& it) {
	auto src_end_block =
	op.src_extent().start_block() + op.src_extent().num_blocks() - 1;
	return src_end_block < it.dst_extent().start_block();
	});

	// TODO(xunchang) skip inserting the empty set to merge_after.
	if (lower_it == upper_it) {
	merge_after.insert({op, {}});
	} else {
	std::set<CowMergeOperation> operations(lower_it, upper_it);
	auto it = operations.find(op);
	if (it != operations.end()) {
	LOG(INFO) << "Self overlapping " << op;
	operations.erase(it);
	}
	auto ret = merge_after.emplace(op, std::move(operations));
	// Check the insertion indeed happens.
	CHECK(ret.second) << op;
	}
	}

	return merge_after;
	}

	bool MergeSequenceGenerator::Generate(
	std::vector<CowMergeOperation>* sequence) const {
	sequence->clear();

	LOG(INFO) << "Generating sequence";

	// Use the non-DFS version of the topology sort. So we can control the
	// operations to discard to break cycles; thus yielding a deterministic
	// sequence.
	std::map<CowMergeOperation, int> incoming_edges;
	for (const auto& it : merge_after_) {
	for (const auto& blocked : it.second) {
	// Value is default initialized to 0.
	incoming_edges[blocked] += 1;
	}
	}

	// Technically, we can use std::unordered_set or just a std::vector. but
	// std::set gives the benefit where operations are sorted by dst blocks. This
	// will ensure that operations that do not have dependency constraints appear
	// in increasing block order. Such order would help snapuserd batch merges and
	// improve boot time, but isn't strictly needed for correctness.
	std::set<CowMergeOperation> free_operations;
	for (const auto& op : operations_) {
	if (incoming_edges.find(op) == incoming_edges.end()) {
	free_operations.insert(op);
	}
	}

	std::vector<CowMergeOperation> merge_sequence;
	std::set<CowMergeOperation> convert_to_raw;
	while (!incoming_edges.empty()) {
	if (!free_operations.empty()) {
	merge_sequence.insert(
	merge_sequence.end(), free_operations.begin(), free_operations.end());
	} else {
	auto to_convert = PickConvertToRaw(incoming_edges, merge_after_);
	// The operation we pick must be one of the nodes not already in merge
	// sequence.
	CHECK(incoming_edges.find(to_convert) != incoming_edges.end());

	free_operations.insert(to_convert);
	convert_to_raw.insert(to_convert);
	LOG(INFO) << "Converting operation to raw " << to_convert;
	}

	std::set<CowMergeOperation> next_free_operations;
	for (const auto& op : free_operations) {
	incoming_edges.erase(op);

	// Now that this particular operation is merged, other operations
	// blocked by this one may be free. Decrement the count of blocking
	// operations, and set up the free operations for the next iteration.
	for (const auto& blocked : merge_after_.at(op)) {
	auto it = incoming_edges.find(blocked);
	if (it == incoming_edges.end()) {
	continue;
	}

	auto blocking_transfer_count = &it->second;
	if (*blocking_transfer_count <= 0) {
	LOG(ERROR) << "Unexpected count in merge after map "
	<< blocking_transfer_count;
	return false;
	}
	// This operation is no longer blocked by anyone. Add it to the merge
	// sequence in the next iteration.
	*blocking_transfer_count -= 1;
	if (*blocking_transfer_count == 0) {
	next_free_operations.insert(blocked);
	}
	}
	}

	LOG(INFO) << "Remaining transfers " << incoming_edges.size()
	<< ", free transfers " << free_operations.size()
	<< ", merge_sequence size " << merge_sequence.size();
	free_operations = std::move(next_free_operations);
	}

	if (!free_operations.empty()) {
	merge_sequence.insert(
	merge_sequence.end(), free_operations.begin(), free_operations.end());
	}

	CHECK_EQ(operations_.size(), merge_sequence.size() + convert_to_raw.size());

	size_t blocks_in_sequence = 0;
	for (const CowMergeOperation& transfer : merge_sequence) {
	blocks_in_sequence += transfer.dst_extent().num_blocks();
	}

	size_t blocks_in_raw = 0;
	for (const CowMergeOperation& transfer : convert_to_raw) {
	blocks_in_raw += transfer.dst_extent().num_blocks();
	}

	LOG(INFO) << "Blocks in merge sequence " << blocks_in_sequence
	<< ", blocks in raw " << blocks_in_raw << ", partition "
	<< partition_name_;
	if (!ValidateSequence(merge_sequence)) {
	LOG(ERROR) << "Invalid Sequence";
	return false;
	}

	*sequence = std::move(merge_sequence);
	return true;
	}

	bool MergeSequenceGenerator::ValidateSequence(
	const std::vector<CowMergeOperation>& sequence) {
	LOG(INFO) << "Validating merge sequence";
	ExtentRanges visited;
	for (const auto& op : sequence) {
	// If \|src_offset\| is greater than zero, dependency should include 1 extra
	// block at end of src_extent, as the OP actually references data past
	// original src_extent.
	if (op.src_offset() > 0) {
	CHECK_EQ(op.src_extent().num_blocks(), op.dst_extent().num_blocks() + 1)
	<< op;
	} else {
	CHECK_EQ(op.src_extent().num_blocks(), op.dst_extent().num_blocks())
	<< op;
	}
	if (visited.OverlapsWithExtent(op.src_extent())) {
	LOG(ERROR) << "Transfer violates the merge sequence " << op
	<< "Visited extent ranges: ";
	visited.Dump();
	return false;
	}

	CHECK(!visited.OverlapsWithExtent(op.dst_extent()))
	<< "dst extent should write only once.";
	visited.AddExtent(op.dst_extent());
	}

	return true;
	}

	} // namespace chromeos_update_engine