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
30 using std::make_pair;
31 using std::pair;
32 using std::string;
33 using std::vector;
34
35 namespace chromeos_update_engine {
36 namespace graph_utils {
37
EdgeWeight(const Graph & graph,const Edge & edge)38 uint64_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
AddReadBeforeDep(Vertex * src,Vertex::Index dst,uint64_t block)50 void 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
AddReadBeforeDepExtents(Vertex * src,Vertex::Index dst,const vector<Extent> & extents)64 void 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
DropWriteBeforeDeps(Vertex::EdgeMap * edge_map)79 void 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|.
DropIncomingEdgesTo(Graph * graph,Vertex::Index index)95 void 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
103 namespace {
104 template<typename T>
DumpExtents(const T & field,int prepend_space_count)105 void DumpExtents(const T& field, int prepend_space_count) {
106 string header(prepend_space_count, ' ');
107 for (int i = 0, e = field.size(); i != e; ++i) {
108 LOG(INFO) << header << "(" << GetElement(field, i).start_block() << ", "
109 << GetElement(field, i).num_blocks() << ")";
110 }
111 }
112
DumpOutEdges(const Vertex::EdgeMap & out_edges)113 void 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
DumpGraph(const Graph & graph)124 void 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