cycle_breaker.cc revision 0103c36caa2e38e034e0d22185736b9ccfb35c58 
1//
2// Copyright (C) 2012 The Android Open Source Project
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8//      http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15//
16
17#include "update_engine/payload_generator/cycle_breaker.h"
18
19#include <inttypes.h>
20
21#include <set>
22#include <string>
23#include <utility>
24
25#include <base/strings/string_util.h>
26#include <base/strings/stringprintf.h>
27
28#include "update_engine/common/utils.h"
29#include "update_engine/payload_generator/graph_utils.h"
30#include "update_engine/payload_generator/tarjan.h"
31
32using std::make_pair;
33using std::set;
34using std::vector;
35
36namespace chromeos_update_engine {
37
38// This is the outer function from the original paper.
39void CycleBreaker::BreakCycles(const Graph& graph, set<Edge>* out_cut_edges) {
40  cut_edges_.clear();
41
42  // Make a copy, which we will modify by removing edges. Thus, in each
43  // iteration subgraph_ is the current subgraph or the original with
44  // vertices we desire. This variable was "A_K" in the original paper.
45  subgraph_ = graph;
46
47  // The paper calls for the "adjacency structure (i.e., graph) of
48  // strong (-ly connected) component K with least vertex in subgraph
49  // induced by {s, s + 1, ..., n}".
50  // We arbitrarily order each vertex by its index in the graph. Thus,
51  // each iteration, we are looking at the subgraph {s, s + 1, ..., n}
52  // and looking for the strongly connected component with vertex s.
53
54  TarjanAlgorithm tarjan;
55  skipped_ops_ = 0;
56
57  for (Graph::size_type i = 0; i < subgraph_.size(); i++) {
58    InstallOperation_Type op_type = graph[i].aop.op.type();
59    if (op_type == InstallOperation::REPLACE ||
60        op_type == InstallOperation::REPLACE_BZ) {
61      skipped_ops_++;
62      continue;
63    }
64
65    if (i > 0) {
66      // Erase node (i - 1) from subgraph_. First, erase what it points to
67      subgraph_[i - 1].out_edges.clear();
68      // Now, erase any pointers to node (i - 1)
69      for (Graph::size_type j = i; j < subgraph_.size(); j++) {
70        subgraph_[j].out_edges.erase(i - 1);
71      }
72    }
73
74    // Calculate SCC (strongly connected component) with vertex i.
75    vector<Vertex::Index> component_indexes;
76    tarjan.Execute(i, &subgraph_, &component_indexes);
77
78    // Set subgraph edges for the components in the SCC.
79    for (vector<Vertex::Index>::iterator it = component_indexes.begin();
80         it != component_indexes.end(); ++it) {
81      subgraph_[*it].subgraph_edges.clear();
82      for (vector<Vertex::Index>::iterator jt = component_indexes.begin();
83           jt != component_indexes.end(); ++jt) {
84        // If there's a link from *it -> *jt in the graph,
85        // add a subgraph_ edge
86        if (utils::MapContainsKey(subgraph_[*it].out_edges, *jt))
87          subgraph_[*it].subgraph_edges.insert(*jt);
88      }
89    }
90
91    current_vertex_ = i;
92    blocked_.clear();
93    blocked_.resize(subgraph_.size());
94    blocked_graph_.clear();
95    blocked_graph_.resize(subgraph_.size());
96    Circuit(current_vertex_, 0);
97  }
98
99  out_cut_edges->swap(cut_edges_);
100  LOG(INFO) << "Cycle breaker skipped " << skipped_ops_ << " ops.";
101  DCHECK(stack_.empty());
102}
103
104static const size_t kMaxEdgesToConsider = 2;
105
106void CycleBreaker::HandleCircuit() {
107  stack_.push_back(current_vertex_);
108  CHECK_GE(stack_.size(),
109           static_cast<vector<Vertex::Index>::size_type>(2));
110  Edge min_edge = make_pair(stack_[0], stack_[1]);
111  uint64_t min_edge_weight = std::numeric_limits<uint64_t>::max();
112  size_t edges_considered = 0;
113  for (vector<Vertex::Index>::const_iterator it = stack_.begin();
114       it != (stack_.end() - 1); ++it) {
115    Edge edge = make_pair(*it, *(it + 1));
116    if (cut_edges_.find(edge) != cut_edges_.end()) {
117      stack_.pop_back();
118      return;
119    }
120    uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge);
121    if (edge_weight < min_edge_weight) {
122      min_edge_weight = edge_weight;
123      min_edge = edge;
124    }
125    edges_considered++;
126    if (edges_considered == kMaxEdgesToConsider)
127      break;
128  }
129  cut_edges_.insert(min_edge);
130  stack_.pop_back();
131}
132
133void CycleBreaker::Unblock(Vertex::Index u) {
134  blocked_[u] = false;
135
136  for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin();
137       it != blocked_graph_[u].out_edges.end(); ) {
138    Vertex::Index w = it->first;
139    blocked_graph_[u].out_edges.erase(it++);
140    if (blocked_[w])
141      Unblock(w);
142  }
143}
144
145bool CycleBreaker::StackContainsCutEdge() const {
146  for (vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
147           e = stack_.end(); it != e; ++it) {
148    Edge edge = make_pair(*(it - 1), *it);
149    if (utils::SetContainsKey(cut_edges_, edge)) {
150      return true;
151    }
152  }
153  return false;
154}
155
156bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) {
157  // "vertex" was "v" in the original paper.
158  bool found = false;  // Was "f" in the original paper.
159  stack_.push_back(vertex);
160  blocked_[vertex] = true;
161  {
162    static int counter = 0;
163    counter++;
164    if (counter == 10000) {
165      counter = 0;
166      std::string stack_str;
167      for (Vertex::Index index : stack_) {
168        stack_str += std::to_string(index);
169        stack_str += " -> ";
170      }
171      LOG(INFO) << "stack: " << stack_str;
172    }
173  }
174
175  for (Vertex::SubgraphEdgeMap::iterator w =
176           subgraph_[vertex].subgraph_edges.begin();
177       w != subgraph_[vertex].subgraph_edges.end(); ++w) {
178    if (*w == current_vertex_) {
179      // The original paper called for printing stack_ followed by
180      // current_vertex_ here, which is a cycle. Instead, we call
181      // HandleCircuit() to break it.
182      HandleCircuit();
183      found = true;
184    } else if (!blocked_[*w]) {
185      if (Circuit(*w, depth + 1)) {
186        found = true;
187        if ((depth > kMaxEdgesToConsider) || StackContainsCutEdge())
188          break;
189      }
190    }
191  }
192
193  if (found) {
194    Unblock(vertex);
195  } else {
196    for (Vertex::SubgraphEdgeMap::iterator w =
197             subgraph_[vertex].subgraph_edges.begin();
198         w != subgraph_[vertex].subgraph_edges.end(); ++w) {
199      if (blocked_graph_[*w].out_edges.find(vertex) ==
200          blocked_graph_[*w].out_edges.end()) {
201        blocked_graph_[*w].out_edges.insert(make_pair(vertex,
202                                                      EdgeProperties()));
203      }
204    }
205  }
206  CHECK_EQ(vertex, stack_.back());
207  stack_.pop_back();
208  return found;
209}
210
211}  // namespace chromeos_update_engine
212