graph_utils.cc revision 6b9e38ef1180efe55e4a82bb18536d1b53fe493d
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 << ": " << InstallOperationTypeName(graph[i].op.type()); 119 LOG(INFO) << " src_extents:"; 120 DumpExtents(graph[i].op.src_extents(), 4); 121 LOG(INFO) << " dst_extents:"; 122 DumpExtents(graph[i].op.dst_extents(), 4); 123 LOG(INFO) << " out edges:"; 124 DumpOutEdges(graph[i].out_edges); 125 } 126} 127 128} // namespace graph_utils 129} // namespace chromeos_update_engine 130