blob: d76f679fdf75cace5ae3c100b051bca4f764b64f [file] [log] [blame]
 // // Copyright (C) 2012 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/cycle_breaker.h" #include #include #include #include #include #include #include #include #include "update_engine/payload_generator/graph_utils.h" #include "update_engine/payload_generator/tarjan.h" using std::make_pair; using std::set; using std::vector; namespace chromeos_update_engine { // This is the outer function from the original paper. void CycleBreaker::BreakCycles(const Graph& graph, set* out_cut_edges) { cut_edges_.clear(); // Make a copy, which we will modify by removing edges. Thus, in each // iteration subgraph_ is the current subgraph or the original with // vertices we desire. This variable was "A_K" in the original paper. subgraph_ = graph; // The paper calls for the "adjacency structure (i.e., graph) of // strong (-ly connected) component K with least vertex in subgraph // induced by {s, s + 1, ..., n}". // We arbitrarily order each vertex by its index in the graph. Thus, // each iteration, we are looking at the subgraph {s, s + 1, ..., n} // and looking for the strongly connected component with vertex s. TarjanAlgorithm tarjan; skipped_ops_ = 0; for (Graph::size_type i = 0; i < subgraph_.size(); i++) { InstallOperation_Type op_type = graph[i].aop.op.type(); if (op_type == InstallOperation::REPLACE || op_type == InstallOperation::REPLACE_BZ) { skipped_ops_++; continue; } if (i > 0) { // Erase node (i - 1) from subgraph_. First, erase what it points to subgraph_[i - 1].out_edges.clear(); // Now, erase any pointers to node (i - 1) for (Graph::size_type j = i; j < subgraph_.size(); j++) { subgraph_[j].out_edges.erase(i - 1); } } // Calculate SCC (strongly connected component) with vertex i. vector component_indexes; tarjan.Execute(i, &subgraph_, &component_indexes); // Set subgraph edges for the components in the SCC. for (vector::iterator it = component_indexes.begin(); it != component_indexes.end(); ++it) { subgraph_[*it].subgraph_edges.clear(); for (vector::iterator jt = component_indexes.begin(); jt != component_indexes.end(); ++jt) { // If there's a link from *it -> *jt in the graph, // add a subgraph_ edge if (base::ContainsKey(subgraph_[*it].out_edges, *jt)) subgraph_[*it].subgraph_edges.insert(*jt); } } current_vertex_ = i; blocked_.clear(); blocked_.resize(subgraph_.size()); blocked_graph_.clear(); blocked_graph_.resize(subgraph_.size()); Circuit(current_vertex_, 0); } out_cut_edges->swap(cut_edges_); LOG(INFO) << "Cycle breaker skipped " << skipped_ops_ << " ops."; DCHECK(stack_.empty()); } static const size_t kMaxEdgesToConsider = 2; void CycleBreaker::HandleCircuit() { stack_.push_back(current_vertex_); CHECK_GE(stack_.size(), static_cast::size_type>(2)); Edge min_edge = make_pair(stack_[0], stack_[1]); uint64_t min_edge_weight = std::numeric_limits::max(); size_t edges_considered = 0; for (vector::const_iterator it = stack_.begin(); it != (stack_.end() - 1); ++it) { Edge edge = make_pair(*it, *(it + 1)); if (cut_edges_.find(edge) != cut_edges_.end()) { stack_.pop_back(); return; } uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge); if (edge_weight < min_edge_weight) { min_edge_weight = edge_weight; min_edge = edge; } edges_considered++; if (edges_considered == kMaxEdgesToConsider) break; } cut_edges_.insert(min_edge); stack_.pop_back(); } void CycleBreaker::Unblock(Vertex::Index u) { blocked_[u] = false; for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin(); it != blocked_graph_[u].out_edges.end();) { Vertex::Index w = it->first; blocked_graph_[u].out_edges.erase(it++); if (blocked_[w]) Unblock(w); } } bool CycleBreaker::StackContainsCutEdge() const { for (vector::const_iterator it = ++stack_.begin(), e = stack_.end(); it != e; ++it) { Edge edge = make_pair(*(it - 1), *it); if (base::ContainsKey(cut_edges_, edge)) { return true; } } return false; } bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) { // "vertex" was "v" in the original paper. bool found = false; // Was "f" in the original paper. stack_.push_back(vertex); blocked_[vertex] = true; { static int counter = 0; counter++; if (counter == 10000) { counter = 0; std::string stack_str; for (Vertex::Index index : stack_) { stack_str += std::to_string(index); stack_str += " -> "; } LOG(INFO) << "stack: " << stack_str; } } for (Vertex::SubgraphEdgeMap::iterator w = subgraph_[vertex].subgraph_edges.begin(); w != subgraph_[vertex].subgraph_edges.end(); ++w) { if (*w == current_vertex_) { // The original paper called for printing stack_ followed by // current_vertex_ here, which is a cycle. Instead, we call // HandleCircuit() to break it. HandleCircuit(); found = true; } else if (!blocked_[*w]) { if (Circuit(*w, depth + 1)) { found = true; if ((depth > kMaxEdgesToConsider) || StackContainsCutEdge()) break; } } } if (found) { Unblock(vertex); } else { for (Vertex::SubgraphEdgeMap::iterator w = subgraph_[vertex].subgraph_edges.begin(); w != subgraph_[vertex].subgraph_edges.end(); ++w) { if (blocked_graph_[*w].out_edges.find(vertex) == blocked_graph_[*w].out_edges.end()) { blocked_graph_[*w].out_edges.insert( make_pair(vertex, EdgeProperties())); } } } CHECK_EQ(vertex, stack_.back()); stack_.pop_back(); return found; } } // namespace chromeos_update_engine