1aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 2aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Copyright (C) 2012 The Android Open Source Project 3aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 4aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Licensed under the Apache License, Version 2.0 (the "License"); 5aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// you may not use this file except in compliance with the License. 6aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// You may obtain a copy of the License at 7aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 8aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// http://www.apache.org/licenses/LICENSE-2.0 9aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 10aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Unless required by applicable law or agreed to in writing, software 11aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// distributed under the License is distributed on an "AS IS" BASIS, 12aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// See the License for the specific language governing permissions and 14aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// limitations under the License. 15aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 1635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 17161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo#include "update_engine/payload_generator/cycle_breaker.h" 18161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo 1921ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes#include <inttypes.h> 20161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo 2135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes#include <set> 22072359ca138504065e1e0c1189eb38c09576d324Alex Vakulenko#include <string> 2335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes#include <utility> 24161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo 2575039d7397f03dff77bdf4e26398049ff88edc4cAlex Vakulenko#include <base/strings/string_util.h> 2675039d7397f03dff77bdf4e26398049ff88edc4cAlex Vakulenko#include <base/strings/stringprintf.h> 27161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo 2839910dcd1d68987ccee7c3031dc269233a8490bbAlex Deymo#include "update_engine/common/utils.h" 29161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo#include "update_engine/payload_generator/graph_utils.h" 30161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo#include "update_engine/payload_generator/tarjan.h" 3135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 3235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyesusing std::make_pair; 3335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyesusing std::set; 3435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyesusing std::vector; 3535a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 3635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyesnamespace chromeos_update_engine { 3735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 3835a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes// This is the outer function from the original paper. 3935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyesvoid CycleBreaker::BreakCycles(const Graph& graph, set<Edge>* out_cut_edges) { 4035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes cut_edges_.clear(); 41161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo 4235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // Make a copy, which we will modify by removing edges. Thus, in each 4335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // iteration subgraph_ is the current subgraph or the original with 4435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // vertices we desire. This variable was "A_K" in the original paper. 4535a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes subgraph_ = graph; 46161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo 4735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // The paper calls for the "adjacency structure (i.e., graph) of 4835a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // strong (-ly connected) component K with least vertex in subgraph 4935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // induced by {s, s + 1, ..., n}". 5035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // We arbitrarily order each vertex by its index in the graph. Thus, 5135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // each iteration, we are looking at the subgraph {s, s + 1, ..., n} 5235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // and looking for the strongly connected component with vertex s. 5335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 5435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes TarjanAlgorithm tarjan; 55182a9f51c753810c5985ac70c5da5b98b35b6cd4Andrew de los Reyes skipped_ops_ = 0; 56161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo 5735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes for (Graph::size_type i = 0; i < subgraph_.size(); i++) { 58a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation_Type op_type = graph[i].aop.op.type(); 59a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo if (op_type == InstallOperation::REPLACE || 60a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo op_type == InstallOperation::REPLACE_BZ) { 61182a9f51c753810c5985ac70c5da5b98b35b6cd4Andrew de los Reyes skipped_ops_++; 62182a9f51c753810c5985ac70c5da5b98b35b6cd4Andrew de los Reyes continue; 63182a9f51c753810c5985ac70c5da5b98b35b6cd4Andrew de los Reyes } 64182a9f51c753810c5985ac70c5da5b98b35b6cd4Andrew de los Reyes 6535a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes if (i > 0) { 6635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // Erase node (i - 1) from subgraph_. First, erase what it points to 6735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes subgraph_[i - 1].out_edges.clear(); 6835a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // Now, erase any pointers to node (i - 1) 6935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes for (Graph::size_type j = i; j < subgraph_.size(); j++) { 7035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes subgraph_[j].out_edges.erase(i - 1); 7135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 7235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 7335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 7435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // Calculate SCC (strongly connected component) with vertex i. 7535a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes vector<Vertex::Index> component_indexes; 7635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes tarjan.Execute(i, &subgraph_, &component_indexes); 7735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 7835a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // Set subgraph edges for the components in the SCC. 7935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes for (vector<Vertex::Index>::iterator it = component_indexes.begin(); 8035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes it != component_indexes.end(); ++it) { 8135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes subgraph_[*it].subgraph_edges.clear(); 8235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes for (vector<Vertex::Index>::iterator jt = component_indexes.begin(); 8335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes jt != component_indexes.end(); ++jt) { 8435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // If there's a link from *it -> *jt in the graph, 8535a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // add a subgraph_ edge 8635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes if (utils::MapContainsKey(subgraph_[*it].out_edges, *jt)) 8735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes subgraph_[*it].subgraph_edges.insert(*jt); 88161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo } 8935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 9035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 9135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes current_vertex_ = i; 9235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes blocked_.clear(); 9335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes blocked_.resize(subgraph_.size()); 9435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes blocked_graph_.clear(); 9535a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes blocked_graph_.resize(subgraph_.size()); 9621ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes Circuit(current_vertex_, 0); 9735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 98161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo 9935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes out_cut_edges->swap(cut_edges_); 100182a9f51c753810c5985ac70c5da5b98b35b6cd4Andrew de los Reyes LOG(INFO) << "Cycle breaker skipped " << skipped_ops_ << " ops."; 10135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes DCHECK(stack_.empty()); 10235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes} 10335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 10421ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyesstatic const size_t kMaxEdgesToConsider = 2; 10521ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes 10635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyesvoid CycleBreaker::HandleCircuit() { 10735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes stack_.push_back(current_vertex_); 1080f9547d10fc3df51c8dd3828a495e89ed0260037Mike Frysinger CHECK_GE(stack_.size(), 109f329b933db41d26644a97afef928eb1b319d6d99Alex Deymo static_cast<vector<Vertex::Index>::size_type>(2)); 11035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes Edge min_edge = make_pair(stack_[0], stack_[1]); 111a3cf75a1d01aeb03d2341600ebff3db0a8316200Alex Vakulenko uint64_t min_edge_weight = std::numeric_limits<uint64_t>::max(); 11221ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes size_t edges_considered = 0; 11335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes for (vector<Vertex::Index>::const_iterator it = stack_.begin(); 11435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes it != (stack_.end() - 1); ++it) { 11535a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes Edge edge = make_pair(*it, *(it + 1)); 11635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes if (cut_edges_.find(edge) != cut_edges_.end()) { 11735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes stack_.pop_back(); 11835a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes return; 11935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 12009e56d64202d2148b95008c5bd18cf719ec0f40cAndrew de los Reyes uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge); 12135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes if (edge_weight < min_edge_weight) { 12235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes min_edge_weight = edge_weight; 12335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes min_edge = edge; 12435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 12545109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes edges_considered++; 12645109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes if (edges_considered == kMaxEdgesToConsider) 12745109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes break; 12835a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 12935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes cut_edges_.insert(min_edge); 13035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes stack_.pop_back(); 13135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes} 13235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 13335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyesvoid CycleBreaker::Unblock(Vertex::Index u) { 13435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes blocked_[u] = false; 13535a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 13635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin(); 13735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes it != blocked_graph_[u].out_edges.end(); ) { 13835a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes Vertex::Index w = it->first; 13935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes blocked_graph_[u].out_edges.erase(it++); 14035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes if (blocked_[w]) 14135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes Unblock(w); 14235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 14335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes} 14435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 14545109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyesbool CycleBreaker::StackContainsCutEdge() const { 146f329b933db41d26644a97afef928eb1b319d6d99Alex Deymo for (vector<Vertex::Index>::const_iterator it = ++stack_.begin(), 147182a9f51c753810c5985ac70c5da5b98b35b6cd4Andrew de los Reyes e = stack_.end(); it != e; ++it) { 14845109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes Edge edge = make_pair(*(it - 1), *it); 14945109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes if (utils::SetContainsKey(cut_edges_, edge)) { 15045109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes return true; 15145109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes } 15245109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes } 15345109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes return false; 15445109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes} 15545109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes 15621ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyesbool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) { 15735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // "vertex" was "v" in the original paper. 15835a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes bool found = false; // Was "f" in the original paper. 15935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes stack_.push_back(vertex); 16035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes blocked_[vertex] = true; 16121ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes { 16221ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes static int counter = 0; 16321ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes counter++; 16421ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes if (counter == 10000) { 16521ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes counter = 0; 16621ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes std::string stack_str; 167072359ca138504065e1e0c1189eb38c09576d324Alex Vakulenko for (Vertex::Index index : stack_) { 168072359ca138504065e1e0c1189eb38c09576d324Alex Vakulenko stack_str += std::to_string(index); 169072359ca138504065e1e0c1189eb38c09576d324Alex Vakulenko stack_str += " -> "; 17021ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes } 17121ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes LOG(INFO) << "stack: " << stack_str; 17221ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes } 17321ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes } 17435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 17535a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes for (Vertex::SubgraphEdgeMap::iterator w = 17635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes subgraph_[vertex].subgraph_edges.begin(); 17735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes w != subgraph_[vertex].subgraph_edges.end(); ++w) { 17835a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes if (*w == current_vertex_) { 17935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // The original paper called for printing stack_ followed by 18035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // current_vertex_ here, which is a cycle. Instead, we call 18135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes // HandleCircuit() to break it. 18235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes HandleCircuit(); 18335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes found = true; 18435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } else if (!blocked_[*w]) { 18521ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes if (Circuit(*w, depth + 1)) { 18635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes found = true; 18721ab31c8a18d9e764e4395ecbac5a440fb86621bAndrew de los Reyes if ((depth > kMaxEdgesToConsider) || StackContainsCutEdge()) 18845109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes break; 18945109894d635776ce4b814bcd043ae8add8b0e1eAndrew de los Reyes } 19035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 19135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 19235a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 19335a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes if (found) { 19435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes Unblock(vertex); 19535a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } else { 19635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes for (Vertex::SubgraphEdgeMap::iterator w = 19735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes subgraph_[vertex].subgraph_edges.begin(); 19835a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes w != subgraph_[vertex].subgraph_edges.end(); ++w) { 1998a51e5c4d3386aeed55b0af1993a00f60856a3e2Andrew de los Reyes if (blocked_graph_[*w].out_edges.find(vertex) == 2008a51e5c4d3386aeed55b0af1993a00f60856a3e2Andrew de los Reyes blocked_graph_[*w].out_edges.end()) { 2018a51e5c4d3386aeed55b0af1993a00f60856a3e2Andrew de los Reyes blocked_graph_[*w].out_edges.insert(make_pair(vertex, 2028a51e5c4d3386aeed55b0af1993a00f60856a3e2Andrew de los Reyes EdgeProperties())); 2038a51e5c4d3386aeed55b0af1993a00f60856a3e2Andrew de los Reyes } 20435a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 20535a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes } 20635a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes CHECK_EQ(vertex, stack_.back()); 20735a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes stack_.pop_back(); 20835a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes return found; 20935a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes} 21035a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes 21135a7af1126cf132d28d2100b24ee476084acd974Andrew de los Reyes} // namespace chromeos_update_engine 212