graph_utils.cc revision 5c6c65570013bbdbd67f9bf6391dd295ef5b5ee6 
1// Copyright (c) 2009 The Chromium OS Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "update_engine/payload_generator/graph_utils.h"
6
7#include <string>
8#include <utility>
9#include <vector>
10
11#include <base/logging.h>
12#include <base/macros.h>
13
14#include "update_engine/payload_constants.h"
15#include "update_engine/payload_generator/annotated_operation.h"
16#include "update_engine/payload_generator/extent_utils.h"
17
18using std::make_pair;
19using std::pair;
20using std::string;
21using std::vector;
22
23namespace chromeos_update_engine {
24namespace graph_utils {
25
26uint64_t EdgeWeight(const Graph& graph, const Edge& edge) {
27  uint64_t weight = 0;
28  const vector<Extent>& extents =
29      graph[edge.first].out_edges.find(edge.second)->second.extents;
30  for (vector<Extent>::const_iterator it = extents.begin();
31       it != extents.end(); ++it) {
32    if (it->start_block() != kSparseHole)
33      weight += it->num_blocks();
34  }
35  return weight;
36}
37
38void AddReadBeforeDep(Vertex* src,
39                      Vertex::Index dst,
40                      uint64_t block) {
41  Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst);
42  if (edge_it == src->out_edges.end()) {
43    // Must create new edge
44    pair<Vertex::EdgeMap::iterator, bool> result =
45        src->out_edges.insert(make_pair(dst, EdgeProperties()));
46    CHECK(result.second);
47    edge_it = result.first;
48  }
49  AppendBlockToExtents(&edge_it->second.extents, block);
50}
51
52void AddReadBeforeDepExtents(Vertex* src,
53                             Vertex::Index dst,
54                             const vector<Extent>& extents) {
55  // TODO(adlr): Be more efficient than adding each block individually.
56  for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
57       it != e; ++it) {
58    const Extent& extent = *it;
59    for (uint64_t block = extent.start_block(),
60             block_end = extent.start_block() + extent.num_blocks();
61         block != block_end; ++block) {
62      AddReadBeforeDep(src, dst, block);
63    }
64  }
65}
66
67void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map) {
68  // Specially crafted for-loop for the map-iterate-delete dance.
69  for (Vertex::EdgeMap::iterator it = edge_map->begin();
70       it != edge_map->end(); ) {
71    if (!it->second.write_extents.empty())
72      it->second.write_extents.clear();
73    if (it->second.extents.empty()) {
74      // Erase *it, as it contains no blocks
75      edge_map->erase(it++);
76    } else {
77      ++it;
78    }
79  }
80}
81
82// For each node N in graph, drop all edges N->|index|.
83void DropIncomingEdgesTo(Graph* graph, Vertex::Index index) {
84  // This would be much more efficient if we had doubly-linked
85  // edges in the graph.
86  for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
87    it->out_edges.erase(index);
88  }
89}
90
91namespace {
92template<typename T>
93void DumpExtents(const T& field, int prepend_space_count) {
94  string header(prepend_space_count, ' ');
95  for (int i = 0, e = field.size(); i != e; ++i) {
96    LOG(INFO) << header << "(" << GetElement(field, i).start_block() << ", "
97              << GetElement(field, i).num_blocks() << ")";
98  }
99}
100
101void DumpOutEdges(const Vertex::EdgeMap& out_edges) {
102  for (Vertex::EdgeMap::const_iterator it = out_edges.begin(),
103           e = out_edges.end(); it != e; ++it) {
104    LOG(INFO) << "    " << it->first << " read-before:";
105    DumpExtents(it->second.extents, 6);
106    LOG(INFO) << "      write-before:";
107    DumpExtents(it->second.write_extents, 6);
108  }
109}
110}  // namespace
111
112void DumpGraph(const Graph& graph) {
113  LOG(INFO) << "Graph length: " << graph.size();
114  for (Graph::size_type i = 0, e = graph.size(); i != e; ++i) {
115    LOG(INFO) << i
116              << (graph[i].valid ? "" : "-INV")
117              << ": " << graph[i].file_name
118              << " " << graph[i].chunk_size << "@" << graph[i].chunk_offset
119              << ": " << InstallOperationTypeName(graph[i].op.type());
120    LOG(INFO) << "  src_extents:";
121    DumpExtents(graph[i].op.src_extents(), 4);
122    LOG(INFO) << "  dst_extents:";
123    DumpExtents(graph[i].op.dst_extents(), 4);
124    LOG(INFO) << "  out edges:";
125    DumpOutEdges(graph[i].out_edges);
126  }
127}
128
129}  // namespace graph_utils
130}  // namespace chromeos_update_engine
131