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