OLD | NEW |
1 // Copyright (c) 2009 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2009 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "update_engine/graph_utils.h" | 5 #include "update_engine/graph_utils.h" |
6 #include "base/basictypes.h" | |
7 | 6 |
| 7 #include <string> |
| 8 #include <utility> |
| 9 #include <vector> |
| 10 |
| 11 #include <base/basictypes.h> |
| 12 #include <base/logging.h> |
| 13 |
| 14 using std::make_pair; |
| 15 using std::pair; |
| 16 using std::string; |
8 using std::vector; | 17 using std::vector; |
9 | 18 |
10 namespace chromeos_update_engine { | 19 namespace chromeos_update_engine { |
11 | 20 |
12 namespace graph_utils { | 21 namespace graph_utils { |
13 | 22 |
14 uint64_t EdgeWeight(const Graph& graph, const Edge& edge) { | 23 uint64_t EdgeWeight(const Graph& graph, const Edge& edge) { |
15 uint64_t weight = 0; | 24 uint64_t weight = 0; |
16 const vector<Extent>& extents = | 25 const vector<Extent>& extents = |
17 graph[edge.first].out_edges.find(edge.second)->second.extents; | 26 graph[edge.first].out_edges.find(edge.second)->second.extents; |
(...skipping 20 matching lines...) Expand all Loading... |
38 extent.set_num_blocks(extent.num_blocks() + 1); | 47 extent.set_num_blocks(extent.num_blocks() + 1); |
39 return; | 48 return; |
40 } | 49 } |
41 } | 50 } |
42 Extent new_extent; | 51 Extent new_extent; |
43 new_extent.set_start_block(block); | 52 new_extent.set_start_block(block); |
44 new_extent.set_num_blocks(1); | 53 new_extent.set_num_blocks(1); |
45 extents->push_back(new_extent); | 54 extents->push_back(new_extent); |
46 } | 55 } |
47 | 56 |
| 57 void AddReadBeforeDep(Vertex* src, |
| 58 Vertex::Index dst, |
| 59 uint64_t block) { |
| 60 Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst); |
| 61 if (edge_it == src->out_edges.end()) { |
| 62 // Must create new edge |
| 63 pair<Vertex::EdgeMap::iterator, bool> result = |
| 64 src->out_edges.insert(make_pair(dst, EdgeProperties())); |
| 65 CHECK(result.second); |
| 66 edge_it = result.first; |
| 67 } |
| 68 AppendBlockToExtents(&edge_it->second.extents, block); |
| 69 } |
| 70 |
| 71 void AddReadBeforeDepExtents(Vertex* src, |
| 72 Vertex::Index dst, |
| 73 const vector<Extent>& extents) { |
| 74 // TODO(adlr): Be more efficient than adding each block individually. |
| 75 for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end(); |
| 76 it != e; ++it) { |
| 77 const Extent& extent = *it; |
| 78 for (uint64_t block = extent.start_block(), |
| 79 block_end = extent.start_block() + extent.num_blocks(); |
| 80 block != block_end; ++block) { |
| 81 AddReadBeforeDep(src, dst, block); |
| 82 } |
| 83 } |
| 84 } |
| 85 |
| 86 void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map) { |
| 87 // Specially crafted for-loop for the map-iterate-delete dance. |
| 88 for (Vertex::EdgeMap::iterator it = edge_map->begin(); |
| 89 it != edge_map->end(); ) { |
| 90 if (!it->second.write_extents.empty()) |
| 91 it->second.write_extents.clear(); |
| 92 if (it->second.extents.empty()) { |
| 93 // Erase *it, as it contains no blocks |
| 94 edge_map->erase(it++); |
| 95 } else { |
| 96 ++it; |
| 97 } |
| 98 } |
| 99 } |
| 100 |
| 101 // For each node N in graph, drop all edges N->|index|. |
| 102 void DropIncomingEdgesTo(Graph* graph, Vertex::Index index) { |
| 103 // This would be much more efficient if we had doubly-linked |
| 104 // edges in the graph. |
| 105 for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) { |
| 106 it->out_edges.erase(index); |
| 107 } |
| 108 } |
| 109 |
| 110 Extent GetElement(const std::vector<Extent>& collection, size_t index) { |
| 111 return collection[index]; |
| 112 } |
| 113 Extent GetElement( |
| 114 const google::protobuf::RepeatedPtrField<Extent>& collection, |
| 115 size_t index) { |
| 116 return collection.Get(index); |
| 117 } |
| 118 |
| 119 namespace { |
| 120 template<typename T> |
| 121 void DumpExtents(const T& field, int prepend_space_count) { |
| 122 string header(prepend_space_count, ' '); |
| 123 for (int i = 0, e = field.size(); i != e; ++i) { |
| 124 LOG(INFO) << header << "(" << GetElement(field, i).start_block() << ", " |
| 125 << GetElement(field, i).num_blocks() << ")"; |
| 126 } |
| 127 } |
| 128 |
| 129 void DumpOutEdges(const Vertex::EdgeMap& out_edges) { |
| 130 for (Vertex::EdgeMap::const_iterator it = out_edges.begin(), |
| 131 e = out_edges.end(); it != e; ++it) { |
| 132 LOG(INFO) << " " << it->first << " read-before:"; |
| 133 DumpExtents(it->second.extents, 6); |
| 134 LOG(INFO) << " write-before:"; |
| 135 DumpExtents(it->second.write_extents, 6); |
| 136 } |
| 137 } |
| 138 } // namespace {} |
| 139 |
| 140 void DumpGraph(const Graph& graph) { |
| 141 LOG(INFO) << "Graph length: " << graph.size(); |
| 142 for (Graph::size_type i = 0, e = graph.size(); i != e; ++i) { |
| 143 string type_str = "UNK"; |
| 144 switch(graph[i].op.type()) { |
| 145 case DeltaArchiveManifest_InstallOperation_Type_BSDIFF: |
| 146 type_str = "BSDIFF"; |
| 147 break; |
| 148 case DeltaArchiveManifest_InstallOperation_Type_MOVE: |
| 149 type_str = "MOVE"; |
| 150 break; |
| 151 case DeltaArchiveManifest_InstallOperation_Type_REPLACE: |
| 152 type_str = "REPLACE"; |
| 153 break; |
| 154 case DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ: |
| 155 type_str = "REPLACE_BZ"; |
| 156 break; |
| 157 } |
| 158 LOG(INFO) << i |
| 159 << (graph[i].valid ? "" : "-INV") |
| 160 << ": " << graph[i].file_name |
| 161 << ": " << type_str; |
| 162 LOG(INFO) << " src_extents:"; |
| 163 DumpExtents(graph[i].op.src_extents(), 4); |
| 164 LOG(INFO) << " dst_extents:"; |
| 165 DumpExtents(graph[i].op.dst_extents(), 4); |
| 166 LOG(INFO) << " out edges:"; |
| 167 DumpOutEdges(graph[i].out_edges); |
| 168 } |
| 169 } |
| 170 |
48 } // namespace graph_utils | 171 } // namespace graph_utils |
49 | 172 |
| 173 bool operator==(const Extent& a, const Extent& b) { |
| 174 return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks(); |
| 175 } |
| 176 |
50 } // namespace chromeos_update_engine | 177 } // namespace chromeos_update_engine |
OLD | NEW |