payload_generator/graph_utils.cc

//
// Copyright (C) 2009 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/graph_utils.h"

#include <string>
#include <utility>
#include <vector>

#include <base/logging.h>
#include <base/macros.h>

#include "update_engine/payload_constants.h"
#include "update_engine/payload_generator/annotated_operation.h"
#include "update_engine/payload_generator/extent_utils.h"

using std::make_pair;
using std::pair;
using std::string;
using std::vector;

namespace chromeos_update_engine {
namespace graph_utils {

uint64_t EdgeWeight(const Graph& graph, const Edge& edge) {
  uint64_t weight = 0;
  const vector<Extent>& extents =
      graph[edge.first].out_edges.find(edge.second)->second.extents;
  for (vector<Extent>::const_iterator it = extents.begin();
       it != extents.end(); ++it) {
    if (it->start_block() != kSparseHole)
      weight += it->num_blocks();
  }
  return weight;
}

void AddReadBeforeDep(Vertex* src,
                      Vertex::Index dst,
                      uint64_t block) {
  Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst);
  if (edge_it == src->out_edges.end()) {
    // Must create new edge
    pair<Vertex::EdgeMap::iterator, bool> result =
        src->out_edges.insert(make_pair(dst, EdgeProperties()));
    CHECK(result.second);
    edge_it = result.first;
  }
  AppendBlockToExtents(&edge_it->second.extents, block);
}

void AddReadBeforeDepExtents(Vertex* src,
                             Vertex::Index dst,
                             const vector<Extent>& extents) {
  // TODO(adlr): Be more efficient than adding each block individually.
  for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
       it != e; ++it) {
    const Extent& extent = *it;
    for (uint64_t block = extent.start_block(),
             block_end = extent.start_block() + extent.num_blocks();
         block != block_end; ++block) {
      AddReadBeforeDep(src, dst, block);
    }
  }
}

void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map) {
  // Specially crafted for-loop for the map-iterate-delete dance.
  for (Vertex::EdgeMap::iterator it = edge_map->begin();
       it != edge_map->end(); ) {
    if (!it->second.write_extents.empty())
      it->second.write_extents.clear();
    if (it->second.extents.empty()) {
      // Erase *it, as it contains no blocks
      edge_map->erase(it++);
    } else {
      ++it;
    }
  }
}

// For each node N in graph, drop all edges N->|index|.
void DropIncomingEdgesTo(Graph* graph, Vertex::Index index) {
  // This would be much more efficient if we had doubly-linked
  // edges in the graph.
  for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
    it->out_edges.erase(index);
  }
}

namespace {
template<typename T>
void DumpExtents(const T& field, int prepend_space_count) {
  string header(prepend_space_count, ' ');
  for (int i = 0, e = field.size(); i != e; ++i) {
    LOG(INFO) << header << "(" << GetElement(field, i).start_block() << ", "
              << GetElement(field, i).num_blocks() << ")";
  }
}

void DumpOutEdges(const Vertex::EdgeMap& out_edges) {
  for (Vertex::EdgeMap::const_iterator it = out_edges.begin(),
           e = out_edges.end(); it != e; ++it) {
    LOG(INFO) << "    " << it->first << " read-before:";
    DumpExtents(it->second.extents, 6);
    LOG(INFO) << "      write-before:";
    DumpExtents(it->second.write_extents, 6);
  }
}
}  // namespace

void DumpGraph(const Graph& graph) {
  LOG(INFO) << "Graph length: " << graph.size();
  for (Graph::size_type i = 0, e = graph.size(); i != e; ++i) {
    LOG(INFO) << i
              << (graph[i].valid ? "" : "-INV")
              << ": " << graph[i].aop.name
              << ": " << InstallOperationTypeName(graph[i].aop.op.type());
    LOG(INFO) << "  src_extents:";
    DumpExtents(graph[i].aop.op.src_extents(), 4);
    LOG(INFO) << "  dst_extents:";
    DumpExtents(graph[i].aop.op.dst_extents(), 4);
    LOG(INFO) << "  out edges:";
    DumpOutEdges(graph[i].out_edges);
  }
}

}  // namespace graph_utils
}  // namespace chromeos_update_engine