payload_generator/cycle_breaker.cc

//
// Copyright (C) 2012 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

#include "update_engine/payload_generator/cycle_breaker.h"

#include <inttypes.h>

#include <limits>
#include <set>
#include <string>
#include <utility>

#include <base/stl_util.h>
#include <base/strings/string_util.h>
#include <base/strings/stringprintf.h>

#include "update_engine/payload_generator/graph_utils.h"
#include "update_engine/payload_generator/tarjan.h"

using std::make_pair;
using std::set;
using std::vector;

namespace chromeos_update_engine {

// This is the outer function from the original paper.
void CycleBreaker::BreakCycles(const Graph& graph, set<Edge>* out_cut_edges) {
  cut_edges_.clear();

  // Make a copy, which we will modify by removing edges. Thus, in each
  // iteration subgraph_ is the current subgraph or the original with
  // vertices we desire. This variable was "A_K" in the original paper.
  subgraph_ = graph;

  // The paper calls for the "adjacency structure (i.e., graph) of
  // strong (-ly connected) component K with least vertex in subgraph
  // induced by {s, s + 1, ..., n}".
  // We arbitrarily order each vertex by its index in the graph. Thus,
  // each iteration, we are looking at the subgraph {s, s + 1, ..., n}
  // and looking for the strongly connected component with vertex s.

  TarjanAlgorithm tarjan;
  skipped_ops_ = 0;

  for (Graph::size_type i = 0; i < subgraph_.size(); i++) {
    InstallOperation::Type op_type = graph[i].aop.op.type();
    if (op_type == InstallOperation::REPLACE ||
        op_type == InstallOperation::REPLACE_BZ) {
      skipped_ops_++;
      continue;
    }

    if (i > 0) {
      // Erase node (i - 1) from subgraph_. First, erase what it points to
      subgraph_[i - 1].out_edges.clear();
      // Now, erase any pointers to node (i - 1)
      for (Graph::size_type j = i; j < subgraph_.size(); j++) {
        subgraph_[j].out_edges.erase(i - 1);
      }
    }

    // Calculate SCC (strongly connected component) with vertex i.
    vector<Vertex::Index> component_indexes;
    tarjan.Execute(i, &subgraph_, &component_indexes);

    // Set subgraph edges for the components in the SCC.
    for (vector<Vertex::Index>::iterator it = component_indexes.begin();
         it != component_indexes.end();
         ++it) {
      subgraph_[*it].subgraph_edges.clear();
      for (vector<Vertex::Index>::iterator jt = component_indexes.begin();
           jt != component_indexes.end();
           ++jt) {
        // If there's a link from *it -> *jt in the graph,
        // add a subgraph_ edge
        if (base::ContainsKey(subgraph_[*it].out_edges, *jt))
          subgraph_[*it].subgraph_edges.insert(*jt);
      }
    }

    current_vertex_ = i;
    blocked_.clear();
    blocked_.resize(subgraph_.size());
    blocked_graph_.clear();
    blocked_graph_.resize(subgraph_.size());
    Circuit(current_vertex_, 0);
  }

  out_cut_edges->swap(cut_edges_);
  LOG(INFO) << "Cycle breaker skipped " << skipped_ops_ << " ops.";
  DCHECK(stack_.empty());
}

static const size_t kMaxEdgesToConsider = 2;

void CycleBreaker::HandleCircuit() {
  stack_.push_back(current_vertex_);
  CHECK_GE(stack_.size(), static_cast<vector<Vertex::Index>::size_type>(2));
  Edge min_edge = make_pair(stack_[0], stack_[1]);
  uint64_t min_edge_weight = std::numeric_limits<uint64_t>::max();
  size_t edges_considered = 0;
  for (vector<Vertex::Index>::const_iterator it = stack_.begin();
       it != (stack_.end() - 1);
       ++it) {
    Edge edge = make_pair(*it, *(it + 1));
    if (cut_edges_.find(edge) != cut_edges_.end()) {
      stack_.pop_back();
      return;
    }
    uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge);
    if (edge_weight < min_edge_weight) {
      min_edge_weight = edge_weight;
      min_edge = edge;
    }
    edges_considered++;
    if (edges_considered == kMaxEdgesToConsider)
      break;
  }
  cut_edges_.insert(min_edge);
  stack_.pop_back();
}

void CycleBreaker::Unblock(Vertex::Index u) {
  blocked_[u] = false;

  for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin();
       it != blocked_graph_[u].out_edges.end();) {
    Vertex::Index w = it->first;
    blocked_graph_[u].out_edges.erase(it++);
    if (blocked_[w])
      Unblock(w);
  }
}

bool CycleBreaker::StackContainsCutEdge() const {
  for (vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
                                             e = stack_.end();
       it != e;
       ++it) {
    Edge edge = make_pair(*(it - 1), *it);
    if (base::ContainsKey(cut_edges_, edge)) {
      return true;
    }
  }
  return false;
}

bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) {
  // "vertex" was "v" in the original paper.
  bool found = false;  // Was "f" in the original paper.
  stack_.push_back(vertex);
  blocked_[vertex] = true;
  {
    static int counter = 0;
    counter++;
    if (counter == 10000) {
      counter = 0;
      std::string stack_str;
      for (Vertex::Index index : stack_) {
        stack_str += std::to_string(index);
        stack_str += " -> ";
      }
      LOG(INFO) << "stack: " << stack_str;
    }
  }

  for (Vertex::SubgraphEdgeMap::iterator w =
           subgraph_[vertex].subgraph_edges.begin();
       w != subgraph_[vertex].subgraph_edges.end();
       ++w) {
    if (*w == current_vertex_) {
      // The original paper called for printing stack_ followed by
      // current_vertex_ here, which is a cycle. Instead, we call
      // HandleCircuit() to break it.
      HandleCircuit();
      found = true;
    } else if (!blocked_[*w]) {
      if (Circuit(*w, depth + 1)) {
        found = true;
        if ((depth > kMaxEdgesToConsider) || StackContainsCutEdge())
          break;
      }
    }
  }

  if (found) {
    Unblock(vertex);
  } else {
    for (Vertex::SubgraphEdgeMap::iterator w =
             subgraph_[vertex].subgraph_edges.begin();
         w != subgraph_[vertex].subgraph_edges.end();
         ++w) {
      if (blocked_graph_[*w].out_edges.find(vertex) ==
          blocked_graph_[*w].out_edges.end()) {
        blocked_graph_[*w].out_edges.insert(
            make_pair(vertex, EdgeProperties()));
      }
    }
  }
  CHECK_EQ(vertex, stack_.back());
  stack_.pop_back();
  return found;
}

}  // namespace chromeos_update_engine