graph_utils.cc revision d8b67f49d7f8ae291cd4fa901b2d3767137704e7 
1//
2// Copyright (C) 2009 The Android Open Source Project
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8//      http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15//
16
17#include "update_engine/payload_generator/graph_utils.h"
18
19#include <string>
20#include <utility>
21#include <vector>
22
23#include <base/logging.h>
24#include <base/macros.h>
25
26#include "update_engine/payload_consumer/payload_constants.h"
27#include "update_engine/payload_generator/annotated_operation.h"
28#include "update_engine/payload_generator/extent_utils.h"
29
30using std::make_pair;
31using std::pair;
32using std::string;
33using std::vector;
34
35namespace chromeos_update_engine {
36namespace graph_utils {
37
38uint64_t EdgeWeight(const Graph& graph, const Edge& edge) {
39  uint64_t weight = 0;
40  const vector<Extent>& extents =
41      graph[edge.first].out_edges.find(edge.second)->second.extents;
42  for (vector<Extent>::const_iterator it = extents.begin();
43       it != extents.end(); ++it) {
44    if (it->start_block() != kSparseHole)
45      weight += it->num_blocks();
46  }
47  return weight;
48}
49
50void AddReadBeforeDep(Vertex* src,
51                      Vertex::Index dst,
52                      uint64_t block) {
53  Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst);
54  if (edge_it == src->out_edges.end()) {
55    // Must create new edge
56    pair<Vertex::EdgeMap::iterator, bool> result =
57        src->out_edges.insert(make_pair(dst, EdgeProperties()));
58    CHECK(result.second);
59    edge_it = result.first;
60  }
61  AppendBlockToExtents(&edge_it->second.extents, block);
62}
63
64void AddReadBeforeDepExtents(Vertex* src,
65                             Vertex::Index dst,
66                             const vector<Extent>& extents) {
67  // TODO(adlr): Be more efficient than adding each block individually.
68  for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
69       it != e; ++it) {
70    const Extent& extent = *it;
71    for (uint64_t block = extent.start_block(),
72             block_end = extent.start_block() + extent.num_blocks();
73         block != block_end; ++block) {
74      AddReadBeforeDep(src, dst, block);
75    }
76  }
77}
78
79void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map) {
80  // Specially crafted for-loop for the map-iterate-delete dance.
81  for (Vertex::EdgeMap::iterator it = edge_map->begin();
82       it != edge_map->end(); ) {
83    if (!it->second.write_extents.empty())
84      it->second.write_extents.clear();
85    if (it->second.extents.empty()) {
86      // Erase *it, as it contains no blocks
87      edge_map->erase(it++);
88    } else {
89      ++it;
90    }
91  }
92}
93
94// For each node N in graph, drop all edges N->|index|.
95void DropIncomingEdgesTo(Graph* graph, Vertex::Index index) {
96  // This would be much more efficient if we had doubly-linked
97  // edges in the graph.
98  for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
99    it->out_edges.erase(index);
100  }
101}
102
103namespace {
104template<typename T>
105void DumpExtents(const T& field, int prepend_space_count) {
106  string header(prepend_space_count, ' ');
107  for (const auto& extent : field) {
108    LOG(INFO) << header << "(" << extent.start_block() << ", "
109              << extent.num_blocks() << ")";
110  }
111}
112
113void DumpOutEdges(const Vertex::EdgeMap& out_edges) {
114  for (Vertex::EdgeMap::const_iterator it = out_edges.begin(),
115           e = out_edges.end(); it != e; ++it) {
116    LOG(INFO) << "    " << it->first << " read-before:";
117    DumpExtents(it->second.extents, 6);
118    LOG(INFO) << "      write-before:";
119    DumpExtents(it->second.write_extents, 6);
120  }
121}
122}  // namespace
123
124void DumpGraph(const Graph& graph) {
125  LOG(INFO) << "Graph length: " << graph.size();
126  for (Graph::size_type i = 0, e = graph.size(); i != e; ++i) {
127    LOG(INFO) << i
128              << (graph[i].valid ? "" : "-INV")
129              << ": " << graph[i].aop.name
130              << ": " << InstallOperationTypeName(graph[i].aop.op.type());
131    LOG(INFO) << "  src_extents:";
132    DumpExtents(graph[i].aop.op.src_extents(), 4);
133    LOG(INFO) << "  dst_extents:";
134    DumpExtents(graph[i].aop.op.dst_extents(), 4);
135    LOG(INFO) << "  out edges:";
136    DumpOutEdges(graph[i].out_edges);
137  }
138}
139
140}  // namespace graph_utils
141}  // namespace chromeos_update_engine
142