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 
32 using std::make_pair;
33 using std::set;
34 using std::vector;
35 
36 namespace chromeos_update_engine {
37 
38 // This is the outer function from the original paper.
BreakCycles(const Graph & graph,set<Edge> * out_cut_edges)39 void 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 
104 static const size_t kMaxEdgesToConsider = 2;
105 
HandleCircuit()106 void 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 
Unblock(Vertex::Index u)133 void 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 
StackContainsCutEdge() const145 bool 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 
Circuit(Vertex::Index vertex,Vertex::Index depth)156 bool 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