graph_utils.cc revision 05735a1879a553153458aae0a25fa5d42e3e408f 
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
16using std::make_pair;
17using std::pair;
18using std::string;
19using std::vector;
20
21namespace chromeos_update_engine {
22
23namespace graph_utils {
24
25uint64_t EdgeWeight(const Graph& graph, const Edge& edge) {
26  uint64_t weight = 0;
27  const vector<Extent>& extents =
28      graph[edge.first].out_edges.find(edge.second)->second.extents;
29  for (vector<Extent>::const_iterator it = extents.begin();
30       it != extents.end(); ++it) {
31    if (it->start_block() != kSparseHole)
32      weight += it->num_blocks();
33  }
34  return weight;
35}
36
37void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) {
38  // First try to extend the last extent in |extents|, if any.
39  if (!extents->empty()) {
40    Extent& extent = extents->back();
41    uint64_t next_block = extent.start_block() == kSparseHole ?
42        kSparseHole : extent.start_block() + extent.num_blocks();
43    if (next_block == block) {
44      extent.set_num_blocks(extent.num_blocks() + 1);
45      return;
46    }
47  }
48  // If unable to extend the last extent, append a new single-block extent.
49  Extent new_extent;
50  new_extent.set_start_block(block);
51  new_extent.set_num_blocks(1);
52  extents->push_back(new_extent);
53}
54
55void AddReadBeforeDep(Vertex* src,
56                      Vertex::Index dst,
57                      uint64_t block) {
58  Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst);
59  if (edge_it == src->out_edges.end()) {
60    // Must create new edge
61    pair<Vertex::EdgeMap::iterator, bool> result =
62        src->out_edges.insert(make_pair(dst, EdgeProperties()));
63    CHECK(result.second);
64    edge_it = result.first;
65  }
66  AppendBlockToExtents(&edge_it->second.extents, block);
67}
68
69void AddReadBeforeDepExtents(Vertex* src,
70                             Vertex::Index dst,
71                             const vector<Extent>& extents) {
72  // TODO(adlr): Be more efficient than adding each block individually.
73  for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
74       it != e; ++it) {
75    const Extent& extent = *it;
76    for (uint64_t block = extent.start_block(),
77             block_end = extent.start_block() + extent.num_blocks();
78         block != block_end; ++block) {
79      AddReadBeforeDep(src, dst, block);
80    }
81  }
82}
83
84void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map) {
85  // Specially crafted for-loop for the map-iterate-delete dance.
86  for (Vertex::EdgeMap::iterator it = edge_map->begin();
87       it != edge_map->end(); ) {
88    if (!it->second.write_extents.empty())
89      it->second.write_extents.clear();
90    if (it->second.extents.empty()) {
91      // Erase *it, as it contains no blocks
92      edge_map->erase(it++);
93    } else {
94      ++it;
95    }
96  }
97}
98
99// For each node N in graph, drop all edges N->|index|.
100void DropIncomingEdgesTo(Graph* graph, Vertex::Index index) {
101  // This would be much more efficient if we had doubly-linked
102  // edges in the graph.
103  for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
104    it->out_edges.erase(index);
105  }
106}
107
108Extent GetElement(const std::vector<Extent>& collection, size_t index) {
109  return collection[index];
110}
111Extent GetElement(
112    const google::protobuf::RepeatedPtrField<Extent>& collection,
113    size_t index) {
114  return collection.Get(index);
115}
116
117namespace {
118template<typename T>
119void DumpExtents(const T& field, int prepend_space_count) {
120  string header(prepend_space_count, ' ');
121  for (int i = 0, e = field.size(); i != e; ++i) {
122    LOG(INFO) << header << "(" << GetElement(field, i).start_block() << ", "
123              << GetElement(field, i).num_blocks() << ")";
124  }
125}
126
127void DumpOutEdges(const Vertex::EdgeMap& out_edges) {
128  for (Vertex::EdgeMap::const_iterator it = out_edges.begin(),
129           e = out_edges.end(); it != e; ++it) {
130    LOG(INFO) << "    " << it->first << " read-before:";
131    DumpExtents(it->second.extents, 6);
132    LOG(INFO) << "      write-before:";
133    DumpExtents(it->second.write_extents, 6);
134  }
135}
136}  // namespace
137
138void DumpGraph(const Graph& graph) {
139  LOG(INFO) << "Graph length: " << graph.size();
140  for (Graph::size_type i = 0, e = graph.size(); i != e; ++i) {
141    string type_str = "UNK";
142    switch (graph[i].op.type()) {
143      case DeltaArchiveManifest_InstallOperation_Type_BSDIFF:
144        type_str = "BSDIFF";
145        break;
146      case DeltaArchiveManifest_InstallOperation_Type_MOVE:
147        type_str = "MOVE";
148        break;
149      case DeltaArchiveManifest_InstallOperation_Type_REPLACE:
150        type_str = "REPLACE";
151        break;
152      case DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ:
153        type_str = "REPLACE_BZ";
154        break;
155    }
156    LOG(INFO) << i
157              << (graph[i].valid ? "" : "-INV")
158              << ": " << graph[i].file_name
159              << " " << graph[i].chunk_size << "@" << graph[i].chunk_offset
160              << ": " << type_str;
161    LOG(INFO) << "  src_extents:";
162    DumpExtents(graph[i].op.src_extents(), 4);
163    LOG(INFO) << "  dst_extents:";
164    DumpExtents(graph[i].op.dst_extents(), 4);
165    LOG(INFO) << "  out edges:";
166    DumpOutEdges(graph[i].out_edges);
167  }
168}
169
170}  // namespace graph_utils
171
172bool operator==(const Extent& a, const Extent& b) {
173  return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
174}
175
176}  // namespace chromeos_update_engine
177