Home | History | Annotate | Download | only in payload_generator 
      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.
     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 
    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 
    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 
    145 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 
    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