1aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 2aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Copyright (C) 2009 The Android Open Source Project 3aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 4aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Licensed under the Apache License, Version 2.0 (the "License"); 5aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// you may not use this file except in compliance with the License. 6aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// You may obtain a copy of the License at 7aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 8aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// http://www.apache.org/licenses/LICENSE-2.0 9aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 10aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Unless required by applicable law or agreed to in writing, software 11aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// distributed under the License is distributed on an "AS IS" BASIS, 12aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// See the License for the specific language governing permissions and 14aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// limitations under the License. 15aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 160ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes 17161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo#include "update_engine/payload_generator/graph_utils.h" 180ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes 191bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes#include <string> 201bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes#include <utility> 211bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes#include <vector> 221bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes 231bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes#include <base/logging.h> 2405735a1879a553153458aae0a25fa5d42e3e408fBen Chan#include <base/macros.h> 251bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes 2639910dcd1d68987ccee7c3031dc269233a8490bbAlex Deymo#include "update_engine/payload_consumer/payload_constants.h" 27477aec2166a571cbe28081d806c3226e8b31b6e9Alex Deymo#include "update_engine/payload_generator/annotated_operation.h" 285c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo#include "update_engine/payload_generator/extent_utils.h" 29161c4a132743f15fc4757112b673085c2a7a7f29Alex Deymo 301bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyesusing std::make_pair; 311bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyesusing std::pair; 321bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyesusing std::string; 330ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyesusing std::vector; 340ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes 350ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyesnamespace chromeos_update_engine { 360ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyesnamespace graph_utils { 370ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes 3809e56d64202d2148b95008c5bd18cf719ec0f40cAndrew de los Reyesuint64_t EdgeWeight(const Graph& graph, const Edge& edge) { 3909e56d64202d2148b95008c5bd18cf719ec0f40cAndrew de los Reyes uint64_t weight = 0; 400ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes const vector<Extent>& extents = 410ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes graph[edge.first].out_edges.find(edge.second)->second.extents; 420ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes for (vector<Extent>::const_iterator it = extents.begin(); 430ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes it != extents.end(); ++it) { 44b10320d4f76a2d263566f6eed471921382fae800Andrew de los Reyes if (it->start_block() != kSparseHole) 45b10320d4f76a2d263566f6eed471921382fae800Andrew de los Reyes weight += it->num_blocks(); 460ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes } 470ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes return weight; 480ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes} 490ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes 501bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyesvoid AddReadBeforeDep(Vertex* src, 511bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes Vertex::Index dst, 521bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes uint64_t block) { 531bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst); 541bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes if (edge_it == src->out_edges.end()) { 551bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes // Must create new edge 561bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes pair<Vertex::EdgeMap::iterator, bool> result = 571bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes src->out_edges.insert(make_pair(dst, EdgeProperties())); 581bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes CHECK(result.second); 591bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes edge_it = result.first; 601bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes } 611bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes AppendBlockToExtents(&edge_it->second.extents, block); 621bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes} 631bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes 641bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyesvoid AddReadBeforeDepExtents(Vertex* src, 651bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes Vertex::Index dst, 661bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes const vector<Extent>& extents) { 671bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes // TODO(adlr): Be more efficient than adding each block individually. 681bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end(); 691bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes it != e; ++it) { 701bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes const Extent& extent = *it; 711bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes for (uint64_t block = extent.start_block(), 721bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes block_end = extent.start_block() + extent.num_blocks(); 731bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes block != block_end; ++block) { 741bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes AddReadBeforeDep(src, dst, block); 751bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes } 761bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes } 771bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes} 781bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes 791bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyesvoid DropWriteBeforeDeps(Vertex::EdgeMap* edge_map) { 801bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes // Specially crafted for-loop for the map-iterate-delete dance. 811bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes for (Vertex::EdgeMap::iterator it = edge_map->begin(); 821bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes it != edge_map->end(); ) { 831bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes if (!it->second.write_extents.empty()) 841bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes it->second.write_extents.clear(); 851bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes if (it->second.extents.empty()) { 861bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes // Erase *it, as it contains no blocks 871bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes edge_map->erase(it++); 881bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes } else { 891bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes ++it; 901bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes } 911bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes } 921bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes} 931bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes 941bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes// For each node N in graph, drop all edges N->|index|. 951bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyesvoid DropIncomingEdgesTo(Graph* graph, Vertex::Index index) { 961bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes // This would be much more efficient if we had doubly-linked 971bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes // edges in the graph. 981bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) { 991bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes it->out_edges.erase(index); 1001bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes } 1011bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes} 1021bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes 1031bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyesnamespace { 1041bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyestemplate<typename T> 1051bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyesvoid DumpExtents(const T& field, int prepend_space_count) { 1061bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes string header(prepend_space_count, ' '); 1071bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes for (int i = 0, e = field.size(); i != e; ++i) { 1081bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes LOG(INFO) << header << "(" << GetElement(field, i).start_block() << ", " 1091bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes << GetElement(field, i).num_blocks() << ")"; 1101bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes } 1111bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes} 1121bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes 1131bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyesvoid DumpOutEdges(const Vertex::EdgeMap& out_edges) { 1141bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes for (Vertex::EdgeMap::const_iterator it = out_edges.begin(), 1151bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes e = out_edges.end(); it != e; ++it) { 1161bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes LOG(INFO) << " " << it->first << " read-before:"; 1171bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes DumpExtents(it->second.extents, 6); 1181bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes LOG(INFO) << " write-before:"; 1191bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes DumpExtents(it->second.write_extents, 6); 1201bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes } 1211bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes} 122d2779df63aaad8b65fc5d4badee7dbc9bed7f2b6Alex Vakulenko} // namespace 1231bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes 1241bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyesvoid DumpGraph(const Graph& graph) { 1251bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes LOG(INFO) << "Graph length: " << graph.size(); 1261bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes for (Graph::size_type i = 0, e = graph.size(); i != e; ++i) { 1278e447e02eb60955bc1f982f0d20b7f0d2689e0dbDarin Petkov LOG(INFO) << i 1281bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes << (graph[i].valid ? "" : "-INV") 1293b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo << ": " << graph[i].aop.name 1303b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo << ": " << InstallOperationTypeName(graph[i].aop.op.type()); 1311bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes LOG(INFO) << " src_extents:"; 1323b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo DumpExtents(graph[i].aop.op.src_extents(), 4); 1331bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes LOG(INFO) << " dst_extents:"; 1343b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo DumpExtents(graph[i].aop.op.dst_extents(), 4); 1351bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes LOG(INFO) << " out edges:"; 1361bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes DumpOutEdges(graph[i].out_edges); 1371bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes } 1381bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes} 1391bc16ab20eabba1785d2b99aa90494bbe7601740Andrew de los Reyes 1400ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes} // namespace graph_utils 1410ce161b06c0430de62658e1f6bcea7a4a97eddf7Andrew de los Reyes} // namespace chromeos_update_engine 142