Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 1 | // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #include "update_engine/cycle_breaker.h" |
Andrew de los Reyes | 21ab31c | 2010-08-19 14:59:00 -0700 | [diff] [blame] | 6 | #include <inttypes.h> |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 7 | #include <set> |
| 8 | #include <utility> |
Andrew de los Reyes | 21ab31c | 2010-08-19 14:59:00 -0700 | [diff] [blame] | 9 | #include "base/string_util.h" |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 10 | #include "update_engine/graph_utils.h" |
| 11 | #include "update_engine/tarjan.h" |
| 12 | #include "update_engine/utils.h" |
| 13 | |
| 14 | using std::make_pair; |
| 15 | using std::set; |
| 16 | using std::vector; |
| 17 | |
| 18 | namespace chromeos_update_engine { |
| 19 | |
| 20 | // This is the outer function from the original paper. |
| 21 | void CycleBreaker::BreakCycles(const Graph& graph, set<Edge>* out_cut_edges) { |
| 22 | cut_edges_.clear(); |
| 23 | |
| 24 | // Make a copy, which we will modify by removing edges. Thus, in each |
| 25 | // iteration subgraph_ is the current subgraph or the original with |
| 26 | // vertices we desire. This variable was "A_K" in the original paper. |
| 27 | subgraph_ = graph; |
| 28 | |
| 29 | // The paper calls for the "adjacency structure (i.e., graph) of |
| 30 | // strong (-ly connected) component K with least vertex in subgraph |
| 31 | // induced by {s, s + 1, ..., n}". |
| 32 | // We arbitrarily order each vertex by its index in the graph. Thus, |
| 33 | // each iteration, we are looking at the subgraph {s, s + 1, ..., n} |
| 34 | // and looking for the strongly connected component with vertex s. |
| 35 | |
| 36 | TarjanAlgorithm tarjan; |
Andrew de los Reyes | 182a9f5 | 2010-10-05 16:33:51 -0700 | [diff] [blame^] | 37 | skipped_ops_ = 0; |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 38 | |
| 39 | for (Graph::size_type i = 0; i < subgraph_.size(); i++) { |
Andrew de los Reyes | 182a9f5 | 2010-10-05 16:33:51 -0700 | [diff] [blame^] | 40 | DeltaArchiveManifest_InstallOperation_Type op_type = graph[i].op.type(); |
| 41 | if (op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE || |
| 42 | op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) { |
| 43 | skipped_ops_++; |
| 44 | continue; |
| 45 | } |
| 46 | |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 47 | if (i > 0) { |
| 48 | // Erase node (i - 1) from subgraph_. First, erase what it points to |
| 49 | subgraph_[i - 1].out_edges.clear(); |
| 50 | // Now, erase any pointers to node (i - 1) |
| 51 | for (Graph::size_type j = i; j < subgraph_.size(); j++) { |
| 52 | subgraph_[j].out_edges.erase(i - 1); |
| 53 | } |
| 54 | } |
| 55 | |
| 56 | // Calculate SCC (strongly connected component) with vertex i. |
| 57 | vector<Vertex::Index> component_indexes; |
| 58 | tarjan.Execute(i, &subgraph_, &component_indexes); |
| 59 | |
| 60 | // Set subgraph edges for the components in the SCC. |
| 61 | for (vector<Vertex::Index>::iterator it = component_indexes.begin(); |
| 62 | it != component_indexes.end(); ++it) { |
| 63 | subgraph_[*it].subgraph_edges.clear(); |
| 64 | for (vector<Vertex::Index>::iterator jt = component_indexes.begin(); |
| 65 | jt != component_indexes.end(); ++jt) { |
| 66 | // If there's a link from *it -> *jt in the graph, |
| 67 | // add a subgraph_ edge |
| 68 | if (utils::MapContainsKey(subgraph_[*it].out_edges, *jt)) |
| 69 | subgraph_[*it].subgraph_edges.insert(*jt); |
| 70 | } |
| 71 | } |
| 72 | |
| 73 | current_vertex_ = i; |
| 74 | blocked_.clear(); |
| 75 | blocked_.resize(subgraph_.size()); |
| 76 | blocked_graph_.clear(); |
| 77 | blocked_graph_.resize(subgraph_.size()); |
Andrew de los Reyes | 21ab31c | 2010-08-19 14:59:00 -0700 | [diff] [blame] | 78 | Circuit(current_vertex_, 0); |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 79 | } |
| 80 | |
| 81 | out_cut_edges->swap(cut_edges_); |
Andrew de los Reyes | 182a9f5 | 2010-10-05 16:33:51 -0700 | [diff] [blame^] | 82 | LOG(INFO) << "Cycle breaker skipped " << skipped_ops_ << " ops."; |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 83 | DCHECK(stack_.empty()); |
| 84 | } |
| 85 | |
Andrew de los Reyes | 21ab31c | 2010-08-19 14:59:00 -0700 | [diff] [blame] | 86 | static const size_t kMaxEdgesToConsider = 2; |
| 87 | |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 88 | void CycleBreaker::HandleCircuit() { |
| 89 | stack_.push_back(current_vertex_); |
| 90 | CHECK_GE(stack_.size(), 2); |
| 91 | Edge min_edge = make_pair(stack_[0], stack_[1]); |
Andrew de los Reyes | 09e56d6 | 2010-04-23 13:45:53 -0700 | [diff] [blame] | 92 | uint64_t min_edge_weight = kuint64max; |
Andrew de los Reyes | 21ab31c | 2010-08-19 14:59:00 -0700 | [diff] [blame] | 93 | size_t edges_considered = 0; |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 94 | for (vector<Vertex::Index>::const_iterator it = stack_.begin(); |
| 95 | it != (stack_.end() - 1); ++it) { |
| 96 | Edge edge = make_pair(*it, *(it + 1)); |
| 97 | if (cut_edges_.find(edge) != cut_edges_.end()) { |
| 98 | stack_.pop_back(); |
| 99 | return; |
| 100 | } |
Andrew de los Reyes | 09e56d6 | 2010-04-23 13:45:53 -0700 | [diff] [blame] | 101 | uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge); |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 102 | if (edge_weight < min_edge_weight) { |
| 103 | min_edge_weight = edge_weight; |
| 104 | min_edge = edge; |
| 105 | } |
Andrew de los Reyes | 4510989 | 2010-07-26 13:49:31 -0700 | [diff] [blame] | 106 | edges_considered++; |
| 107 | if (edges_considered == kMaxEdgesToConsider) |
| 108 | break; |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 109 | } |
| 110 | cut_edges_.insert(min_edge); |
| 111 | stack_.pop_back(); |
| 112 | } |
| 113 | |
| 114 | void CycleBreaker::Unblock(Vertex::Index u) { |
| 115 | blocked_[u] = false; |
| 116 | |
| 117 | for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin(); |
| 118 | it != blocked_graph_[u].out_edges.end(); ) { |
| 119 | Vertex::Index w = it->first; |
| 120 | blocked_graph_[u].out_edges.erase(it++); |
| 121 | if (blocked_[w]) |
| 122 | Unblock(w); |
| 123 | } |
| 124 | } |
| 125 | |
Andrew de los Reyes | 4510989 | 2010-07-26 13:49:31 -0700 | [diff] [blame] | 126 | bool CycleBreaker::StackContainsCutEdge() const { |
| 127 | for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(), |
Andrew de los Reyes | 182a9f5 | 2010-10-05 16:33:51 -0700 | [diff] [blame^] | 128 | e = stack_.end(); it != e; ++it) { |
Andrew de los Reyes | 4510989 | 2010-07-26 13:49:31 -0700 | [diff] [blame] | 129 | Edge edge = make_pair(*(it - 1), *it); |
| 130 | if (utils::SetContainsKey(cut_edges_, edge)) { |
| 131 | return true; |
| 132 | } |
| 133 | } |
| 134 | return false; |
| 135 | } |
| 136 | |
Andrew de los Reyes | 21ab31c | 2010-08-19 14:59:00 -0700 | [diff] [blame] | 137 | bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) { |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 138 | // "vertex" was "v" in the original paper. |
| 139 | bool found = false; // Was "f" in the original paper. |
| 140 | stack_.push_back(vertex); |
| 141 | blocked_[vertex] = true; |
Andrew de los Reyes | 21ab31c | 2010-08-19 14:59:00 -0700 | [diff] [blame] | 142 | { |
| 143 | static int counter = 0; |
| 144 | counter++; |
| 145 | if (counter == 10000) { |
| 146 | counter = 0; |
| 147 | std::string stack_str; |
| 148 | for (vector<Vertex::Index>::const_iterator it = stack_.begin(); |
| 149 | it != stack_.end(); ++it) { |
| 150 | stack_str += StringPrintf("%lu -> ", |
| 151 | static_cast<long unsigned int>(*it)); |
| 152 | } |
| 153 | LOG(INFO) << "stack: " << stack_str; |
| 154 | } |
| 155 | } |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 156 | |
| 157 | for (Vertex::SubgraphEdgeMap::iterator w = |
| 158 | subgraph_[vertex].subgraph_edges.begin(); |
| 159 | w != subgraph_[vertex].subgraph_edges.end(); ++w) { |
| 160 | if (*w == current_vertex_) { |
| 161 | // The original paper called for printing stack_ followed by |
| 162 | // current_vertex_ here, which is a cycle. Instead, we call |
| 163 | // HandleCircuit() to break it. |
| 164 | HandleCircuit(); |
| 165 | found = true; |
| 166 | } else if (!blocked_[*w]) { |
Andrew de los Reyes | 21ab31c | 2010-08-19 14:59:00 -0700 | [diff] [blame] | 167 | if (Circuit(*w, depth + 1)) { |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 168 | found = true; |
Andrew de los Reyes | 21ab31c | 2010-08-19 14:59:00 -0700 | [diff] [blame] | 169 | if ((depth > kMaxEdgesToConsider) || StackContainsCutEdge()) |
Andrew de los Reyes | 4510989 | 2010-07-26 13:49:31 -0700 | [diff] [blame] | 170 | break; |
| 171 | } |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 172 | } |
| 173 | } |
| 174 | |
| 175 | if (found) { |
| 176 | Unblock(vertex); |
| 177 | } else { |
| 178 | for (Vertex::SubgraphEdgeMap::iterator w = |
| 179 | subgraph_[vertex].subgraph_edges.begin(); |
| 180 | w != subgraph_[vertex].subgraph_edges.end(); ++w) { |
Andrew de los Reyes | 8a51e5c | 2010-07-26 13:40:03 -0700 | [diff] [blame] | 181 | if (blocked_graph_[*w].out_edges.find(vertex) == |
| 182 | blocked_graph_[*w].out_edges.end()) { |
| 183 | blocked_graph_[*w].out_edges.insert(make_pair(vertex, |
| 184 | EdgeProperties())); |
| 185 | } |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 186 | } |
| 187 | } |
| 188 | CHECK_EQ(vertex, stack_.back()); |
| 189 | stack_.pop_back(); |
| 190 | return found; |
| 191 | } |
| 192 | |
| 193 | } // namespace chromeos_update_engine |