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