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 
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 
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 
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 
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|.
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>
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 
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 
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