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(); it != extents.end();
43 ++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, Vertex::Index dst, uint64_t block) {
51 Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst);
52 if (edge_it == src->out_edges.end()) {
53 // Must create new edge
54 pair<Vertex::EdgeMap::iterator, bool> result =
55 src->out_edges.insert(make_pair(dst, EdgeProperties()));
56 CHECK(result.second);
57 edge_it = result.first;
58 }
59 AppendBlockToExtents(&edge_it->second.extents, block);
60 }
61
AddReadBeforeDepExtents(Vertex * src,Vertex::Index dst,const vector<Extent> & extents)62 void AddReadBeforeDepExtents(Vertex* src,
63 Vertex::Index dst,
64 const vector<Extent>& extents) {
65 // TODO(adlr): Be more efficient than adding each block individually.
66 for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
67 it != e;
68 ++it) {
69 const Extent& extent = *it;
70 for (uint64_t block = extent.start_block(),
71 block_end = extent.start_block() + extent.num_blocks();
72 block != block_end;
73 ++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 (const auto& extent : field) {
108 LOG(INFO) << header << "(" << extent.start_block() << ", "
109 << extent.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();
116 it != e;
117 ++it) {
118 LOG(INFO) << " " << it->first << " read-before:";
119 DumpExtents(it->second.extents, 6);
120 LOG(INFO) << " write-before:";
121 DumpExtents(it->second.write_extents, 6);
122 }
123 }
124 } // namespace
125
DumpGraph(const Graph & graph)126 void DumpGraph(const Graph& graph) {
127 LOG(INFO) << "Graph length: " << graph.size();
128 for (Graph::size_type i = 0, e = graph.size(); i != e; ++i) {
129 LOG(INFO) << i << (graph[i].valid ? "" : "-INV") << ": "
130 << graph[i].aop.name << ": "
131 << InstallOperationTypeName(graph[i].aop.op.type());
132 LOG(INFO) << " src_extents:";
133 DumpExtents(graph[i].aop.op.src_extents(), 4);
134 LOG(INFO) << " dst_extents:";
135 DumpExtents(graph[i].aop.op.dst_extents(), 4);
136 LOG(INFO) << " out edges:";
137 DumpOutEdges(graph[i].out_edges);
138 }
139 }
140
141 } // namespace graph_utils
142 } // namespace chromeos_update_engine
143