Home | History | Annotate | Download | only in payload_generator 
      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();
     43        it != extents.end(); ++it) {
     44     if (it->start_block() != kSparseHole)
     45       weight += it->num_blocks();
     46   }
     47   return weight;
     48 }
     49 
     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 
     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 
     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(); 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 
    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