1aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 2aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Copyright (C) 2015 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// 16cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 17cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/payload_generator/inplace_generator.h" 18cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 19cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <algorithm> 20cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <map> 21cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <set> 22cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <string> 23cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <utility> 24cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <vector> 25cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 2639910dcd1d68987ccee7c3031dc269233a8490bbAlex Deymo#include "update_engine/common/utils.h" 2739910dcd1d68987ccee7c3031dc269233a8490bbAlex Deymo#include "update_engine/payload_consumer/payload_constants.h" 28cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/payload_generator/cycle_breaker.h" 29cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/payload_generator/delta_diff_generator.h" 3014158570d3995008dc93a628004118b87a6bca01Alex Deymo#include "update_engine/payload_generator/delta_diff_utils.h" 311beda780333ce51d7872603b70712772eb2383fbAlex Deymo#include "update_engine/payload_generator/extent_ranges.h" 32cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/payload_generator/graph_types.h" 33cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/payload_generator/graph_utils.h" 34cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/payload_generator/topological_sort.h" 35cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/update_metadata.pb.h" 36cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 37cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::make_pair; 38cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::map; 39cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::pair; 40cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::set; 41cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::string; 42cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::vector; 43cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 44cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodnamespace chromeos_update_engine { 45cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 466b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymousing Block = InplaceGenerator::Block; 47cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 483b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymonamespace { 493b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo 5038818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo// The only PayloadVersion supported by this implementation. 5138818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymoconst PayloadVersion kInPlacePayloadVersion{kChromeOSMajorPayloadVersion, 5238818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo kInPlaceMinorPayloadVersion}; 5338818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo 54cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// This class allocates non-existent temp blocks, starting from 55cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// kTempBlockStart. Other code is responsible for converting these 56cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// temp blocks into real blocks, as the client can't read or write to 57cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// these blocks. 58cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodclass DummyExtentAllocator { 59cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood public: 60cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> Allocate(const uint64_t block_count) { 61cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> ret(1); 62cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ret[0].set_start_block(next_block_); 63cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ret[0].set_num_blocks(block_count); 64cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood next_block_ += block_count; 65cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return ret; 66cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 67cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 68cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood private: 69cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood uint64_t next_block_{kTempBlockStart}; 70cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood}; 71cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 72cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// Takes a vector of blocks and returns an equivalent vector of Extent 73cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// objects. 74cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvector<Extent> CompressExtents(const vector<uint64_t>& blocks) { 75cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> new_extents; 76cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (uint64_t block : blocks) { 775c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&new_extents, block); 78cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 79cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return new_extents; 80cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 81cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 823b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo// Helper class to compare two operations by start block of the first Extent in 833b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo// their destination extents given the index of the operations in the graph. 843b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymoclass IndexedInstallOperationsDstComparator { 853b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo public: 863b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo explicit IndexedInstallOperationsDstComparator(Graph* graph) 873b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo : graph_(graph) {} 883b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo 893b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo // Compares the operations in the vertex a and b of graph_. 903b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo bool operator()(size_t a, size_t b) const { 913b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo return diff_utils::CompareAopsByDestination((*graph_)[a].aop, 923b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo (*graph_)[b].aop); 933b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo } 943b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo 953b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo private: 963b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo const Graph* const graph_; 973b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo}; 983b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo 993b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo} // namespace 1003b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo 101477aec2166a571cbe28081d806c3226e8b31b6e9Alex Deymovoid InplaceGenerator::CheckGraph(const Graph& graph) { 102477aec2166a571cbe28081d806c3226e8b31b6e9Alex Deymo for (const Vertex& v : graph) { 1033b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo CHECK(v.aop.op.has_type()); 104477aec2166a571cbe28081d806c3226e8b31b6e9Alex Deymo } 105477aec2166a571cbe28081d806c3226e8b31b6e9Alex Deymo} 106477aec2166a571cbe28081d806c3226e8b31b6e9Alex Deymo 107cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvoid InplaceGenerator::SubstituteBlocks( 108cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex* vertex, 109cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Extent>& remove_extents, 110cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Extent>& replace_extents) { 111cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // First, expand out the blocks that op reads from 112cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<uint64_t> read_blocks = 1133b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo ExpandExtents(vertex->aop.op.src_extents()); 114cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood { 115cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Expand remove_extents and replace_extents 11614158570d3995008dc93a628004118b87a6bca01Alex Deymo vector<uint64_t> remove_extents_expanded = ExpandExtents(remove_extents); 11714158570d3995008dc93a628004118b87a6bca01Alex Deymo vector<uint64_t> replace_extents_expanded = ExpandExtents(replace_extents); 118cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK_EQ(remove_extents_expanded.size(), replace_extents_expanded.size()); 119cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood map<uint64_t, uint64_t> conversion; 120cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (vector<uint64_t>::size_type i = 0; 121cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood i < replace_extents_expanded.size(); i++) { 122cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood conversion[remove_extents_expanded[i]] = replace_extents_expanded[i]; 123cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 12414158570d3995008dc93a628004118b87a6bca01Alex Deymo ApplyMap(&read_blocks, conversion); 125cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (auto& edge_prop_pair : vertex->out_edges) { 12614158570d3995008dc93a628004118b87a6bca01Alex Deymo vector<uint64_t> write_before_deps_expanded = ExpandExtents( 12714158570d3995008dc93a628004118b87a6bca01Alex Deymo edge_prop_pair.second.write_extents); 12814158570d3995008dc93a628004118b87a6bca01Alex Deymo ApplyMap(&write_before_deps_expanded, conversion); 129cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood edge_prop_pair.second.write_extents = 130cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CompressExtents(write_before_deps_expanded); 131cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 132cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 133cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Convert read_blocks back to extents 1343b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo vertex->aop.op.clear_src_extents(); 135cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> new_extents = CompressExtents(read_blocks); 1363b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(new_extents, vertex->aop.op.mutable_src_extents()); 137cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 138cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 139cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodbool InplaceGenerator::CutEdges(Graph* graph, 140cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const set<Edge>& edges, 141cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<CutEdgeVertexes>* out_cuts) { 142cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood DummyExtentAllocator scratch_allocator; 143cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<CutEdgeVertexes> cuts; 144cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts.reserve(edges.size()); 145cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 146cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood uint64_t scratch_blocks_used = 0; 147cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (const Edge& edge : edges) { 148cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts.resize(cuts.size() + 1); 149cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> old_extents = 150cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[edge.first].out_edges[edge.second].extents; 151cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Choose some scratch space 152cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood scratch_blocks_used += graph_utils::EdgeWeight(*graph, edge); 153cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts.back().tmp_extents = 154cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, edge)); 155cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // create vertex to copy original->scratch 156cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts.back().new_vertex = graph->size(); 1579b244df41f1bdaddd87b7dbd8e1559556059ed1bAlex Deymo graph->emplace_back(); 158cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts.back().old_src = edge.first; 159cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts.back().old_dst = edge.second; 160cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 161cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EdgeProperties& cut_edge_properties = 162cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[edge.first].out_edges.find(edge.second)->second; 163cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 164cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // This should never happen, as we should only be cutting edges between 165cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // real file nodes, and write-before relationships are created from 166cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // a real file node to a temp copy node: 167cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK(cut_edge_properties.write_extents.empty()) 168cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood << "Can't cut edge that has write-before relationship."; 169cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 170cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // make node depend on the copy operation 171cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[edge.first].out_edges.insert(make_pair(graph->size() - 1, 172cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cut_edge_properties)); 173cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 174cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Set src/dst extents and other proto variables for copy operation 175a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph->back().aop.op.set_type(InstallOperation::MOVE); 17614158570d3995008dc93a628004118b87a6bca01Alex Deymo StoreExtents(cut_edge_properties.extents, 1773b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph->back().aop.op.mutable_src_extents()); 17814158570d3995008dc93a628004118b87a6bca01Alex Deymo StoreExtents(cuts.back().tmp_extents, 1793b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph->back().aop.op.mutable_dst_extents()); 1803b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph->back().aop.op.set_src_length( 181cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph_utils::EdgeWeight(*graph, edge) * kBlockSize); 1823b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph->back().aop.op.set_dst_length(graph->back().aop.op.src_length()); 183cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 184cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // make the dest node read from the scratch space 185cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood SubstituteBlocks( 186cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood &((*graph)[edge.second]), 187cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[edge.first].out_edges[edge.second].extents, 188cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts.back().tmp_extents); 189cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 190cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // delete the old edge 191cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK_EQ(static_cast<Graph::size_type>(1), 192cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[edge.first].out_edges.erase(edge.second)); 193cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 194cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Add an edge from dst to copy operation 195cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EdgeProperties write_before_edge_properties; 196cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood write_before_edge_properties.write_extents = cuts.back().tmp_extents; 197cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[edge.second].out_edges.insert( 198cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood make_pair(graph->size() - 1, write_before_edge_properties)); 199cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 200cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood out_cuts->swap(cuts); 201cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return true; 202cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 203cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 204cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// Creates all the edges for the graph. Writers of a block point to 205cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// readers of the same block. This is because for an edge A->B, B 206cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// must complete before A executes. 207cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvoid InplaceGenerator::CreateEdges( 208cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph* graph, 2096b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo const vector<Block>& blocks) { 2106b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo for (vector<Block>::size_type i = 0; 211cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood i < blocks.size(); i++) { 212cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Blocks with both a reader and writer get an edge 213cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (blocks[i].reader == Vertex::kInvalidIndex || 214cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[i].writer == Vertex::kInvalidIndex) 215cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood continue; 216cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Don't have a node depend on itself 217cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (blocks[i].reader == blocks[i].writer) 218cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood continue; 219cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // See if there's already an edge we can add onto 220cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex::EdgeMap::iterator edge_it = 221cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader); 222cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (edge_it == (*graph)[blocks[i].writer].out_edges.end()) { 223cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // No existing edge. Create one 224cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[blocks[i].writer].out_edges.insert( 225cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood make_pair(blocks[i].reader, EdgeProperties())); 226cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood edge_it = (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader); 227cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK(edge_it != (*graph)[blocks[i].writer].out_edges.end()); 228cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 2295c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&edge_it->second.extents, i); 230cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 231cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 232cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 233cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodnamespace { 234cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 235cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodclass SortCutsByTopoOrderLess { 236cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood public: 237cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood explicit SortCutsByTopoOrderLess( 238cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<vector<Vertex::Index>::size_type>& table) 239cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood : table_(table) {} 240cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood bool operator()(const CutEdgeVertexes& a, const CutEdgeVertexes& b) { 241cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return table_[a.old_dst] < table_[b.old_dst]; 242cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 243cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood private: 244cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<vector<Vertex::Index>::size_type>& table_; 245cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood}; 246cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 247cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} // namespace 248cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 249cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvoid InplaceGenerator::GenerateReverseTopoOrderMap( 250cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Vertex::Index>& op_indexes, 251cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<vector<Vertex::Index>::size_type>* reverse_op_indexes) { 252cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<vector<Vertex::Index>::size_type> table(op_indexes.size()); 253cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (vector<Vertex::Index>::size_type i = 0, e = op_indexes.size(); 254cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood i != e; ++i) { 255cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex::Index node = op_indexes[i]; 256cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (table.size() < (node + 1)) { 257cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood table.resize(node + 1); 258cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 259cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood table[node] = i; 260cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 261cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood reverse_op_indexes->swap(table); 262cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 263cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 264cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvoid InplaceGenerator::SortCutsByTopoOrder( 265cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Vertex::Index>& op_indexes, 266cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<CutEdgeVertexes>* cuts) { 267cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // first, make a reverse lookup table. 268cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<vector<Vertex::Index>::size_type> table; 269cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenerateReverseTopoOrderMap(op_indexes, &table); 270cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood SortCutsByTopoOrderLess less(table); 271cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood sort(cuts->begin(), cuts->end(), less); 272cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 273cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 2743b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymovoid InplaceGenerator::MoveAndSortFullOpsToBack( 2753b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo Graph* graph, 2763b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo vector<Vertex::Index>* op_indexes) { 277cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index> ret; 278cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index> full_ops; 279cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ret.reserve(op_indexes->size()); 2803b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo for (auto op_index : *op_indexes) { 281a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation_Type type = (*graph)[op_index].aop.op.type(); 282a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo if (type == InstallOperation::REPLACE || 283a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo type == InstallOperation::REPLACE_BZ) { 2843b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo full_ops.push_back(op_index); 285cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } else { 2863b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo ret.push_back(op_index); 287cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 288cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 289cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "Stats: " << full_ops.size() << " full ops out of " 290cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood << (full_ops.size() + ret.size()) << " total ops."; 2913b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo // Sort full ops according to their dst_extents. 2923b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo sort(full_ops.begin(), full_ops.end(), 2933b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo IndexedInstallOperationsDstComparator(graph)); 294cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ret.insert(ret.end(), full_ops.begin(), full_ops.end()); 295cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes->swap(ret); 296cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 297cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 298cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodnamespace { 299cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 300cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodtemplate<typename T> 301cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodbool TempBlocksExistInExtents(const T& extents) { 302cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (int i = 0, e = extents.size(); i < e; ++i) { 3035c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo Extent extent = GetElement(extents, i); 304cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood uint64_t start = extent.start_block(); 305cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood uint64_t num = extent.num_blocks(); 306cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (start >= kTempBlockStart || (start + num) >= kTempBlockStart) { 307cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(ERROR) << "temp block!"; 308cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(ERROR) << "start: " << start << ", num: " << num; 309cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(ERROR) << "kTempBlockStart: " << kTempBlockStart; 310cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(ERROR) << "returning true"; 311cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return true; 312cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 313cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // check for wrap-around, which would be a bug: 314cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK(start <= (start + num)); 315cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 316cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return false; 317cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 318cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 319cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// Converts the cuts, which must all have the same |old_dst| member, 320cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// to full. It does this by converting the |old_dst| to REPLACE or 321cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// REPLACE_BZ, dropping all incoming edges to |old_dst|, and marking 322cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// all temp nodes invalid. 323cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodbool ConvertCutsToFull( 324cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph* graph, 325568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood const string& new_part, 3268cc502dacbccdab96824d42287f230ce04004784Sen Jiang BlobFileWriter* blob_file, 327cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index>* op_indexes, 328cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, 329cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<CutEdgeVertexes>& cuts) { 330cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK(!cuts.empty()); 331cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood set<Vertex::Index> deleted_nodes; 332cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (const CutEdgeVertexes& cut : cuts) { 333cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood TEST_AND_RETURN_FALSE(InplaceGenerator::ConvertCutToFullOp( 334cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph, 335cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cut, 336568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood new_part, 3378cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file)); 338cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood deleted_nodes.insert(cut.new_vertex); 339cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 340cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood deleted_nodes.insert(cuts[0].old_dst); 341cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 342cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index> new_op_indexes; 343cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood new_op_indexes.reserve(op_indexes->size()); 344cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (Vertex::Index vertex_index : *op_indexes) { 345cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (utils::SetContainsKey(deleted_nodes, vertex_index)) 346cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood continue; 347cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood new_op_indexes.push_back(vertex_index); 348cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 349cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood new_op_indexes.push_back(cuts[0].old_dst); 350cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes->swap(new_op_indexes); 351cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood InplaceGenerator::GenerateReverseTopoOrderMap(*op_indexes, 352cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood reverse_op_indexes); 353cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return true; 354cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 355cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 356cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// Tries to assign temp blocks for a collection of cuts, all of which share 357cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// the same old_dst member. If temp blocks can't be found, old_dst will be 358cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// converted to a REPLACE or REPLACE_BZ operation. Returns true on success, 359cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// which can happen even if blocks are converted to full. Returns false 360cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood// on exceptional error cases. 361cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodbool AssignBlockForAdjoiningCuts( 362cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph* graph, 363568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood const string& new_part, 3648cc502dacbccdab96824d42287f230ce04004784Sen Jiang BlobFileWriter* blob_file, 365cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index>* op_indexes, 366cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, 367cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<CutEdgeVertexes>& cuts) { 368cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK(!cuts.empty()); 369cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const Vertex::Index old_dst = cuts[0].old_dst; 370cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Calculate # of blocks needed 371cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood uint64_t blocks_needed = 0; 372cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<uint64_t> cuts_blocks_needed(cuts.size()); 373cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) { 374cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood uint64_t cut_blocks_needed = 0; 375cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (const Extent& extent : cuts[i].tmp_extents) { 376cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cut_blocks_needed += extent.num_blocks(); 377cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 378cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks_needed += cut_blocks_needed; 379cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts_blocks_needed[i] = cut_blocks_needed; 380cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 381cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 382cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Find enough blocks 383cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ExtentRanges scratch_ranges; 384cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Each block that's supplying temp blocks and the corresponding blocks: 385cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood typedef vector<pair<Vertex::Index, ExtentRanges>> SupplierVector; 386cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood SupplierVector block_suppliers; 387cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood uint64_t scratch_blocks_found = 0; 388cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (vector<Vertex::Index>::size_type i = (*reverse_op_indexes)[old_dst] + 1, 389cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood e = op_indexes->size(); i < e; ++i) { 390cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex::Index test_node = (*op_indexes)[i]; 391cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (!(*graph)[test_node].valid) 392cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood continue; 393cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // See if this node has sufficient blocks 394cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ExtentRanges ranges; 3953b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo ranges.AddRepeatedExtents((*graph)[test_node].aop.op.dst_extents()); 396cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ranges.SubtractExtent(ExtentForRange( 397cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood kTempBlockStart, kSparseHole - kTempBlockStart)); 3983b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo ranges.SubtractRepeatedExtents((*graph)[test_node].aop.op.src_extents()); 399cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // For now, for simplicity, subtract out all blocks in read-before 400cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // dependencies. 401cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (Vertex::EdgeMap::const_iterator edge_i = 402cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[test_node].out_edges.begin(), 403cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood edge_e = (*graph)[test_node].out_edges.end(); 404cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood edge_i != edge_e; ++edge_i) { 405cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ranges.SubtractExtents(edge_i->second.extents); 406cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 407896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 408896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // Prevent using the block 0 as scratch space due to crbug.com/480751. 409896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo if (ranges.ContainsBlock(0)) { 410896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo LOG(INFO) << "Removing block 0 from the selected scratch range in vertex " 411896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo << i; 412896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo ranges.SubtractBlock(0); 413896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 414896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 415cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (ranges.blocks() == 0) 416cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood continue; 417cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 418cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (ranges.blocks() + scratch_blocks_found > blocks_needed) { 419cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // trim down ranges 420cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> new_ranges = ranges.GetExtentsForBlockCount( 421cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks_needed - scratch_blocks_found); 422cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ranges = ExtentRanges(); 423cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ranges.AddExtents(new_ranges); 424cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 425cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood scratch_ranges.AddRanges(ranges); 426cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood block_suppliers.push_back(make_pair(test_node, ranges)); 427cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood scratch_blocks_found += ranges.blocks(); 428cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (scratch_ranges.blocks() >= blocks_needed) 429cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood break; 430cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 431cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (scratch_ranges.blocks() < blocks_needed) { 432cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "Unable to find sufficient scratch"; 433cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood TEST_AND_RETURN_FALSE(ConvertCutsToFull(graph, 434568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood new_part, 4358cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file, 436cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes, 437cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood reverse_op_indexes, 438cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts)); 439cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return true; 440cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 441cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Use the scratch we found 442cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood TEST_AND_RETURN_FALSE(scratch_ranges.blocks() == scratch_blocks_found); 443cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 444cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Make all the suppliers depend on this node 445cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (const auto& index_range_pair : block_suppliers) { 446cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph_utils::AddReadBeforeDepExtents( 447cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood &(*graph)[index_range_pair.first], 448cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood old_dst, 449cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood index_range_pair.second.GetExtentsForBlockCount( 450cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood index_range_pair.second.blocks())); 451cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 452cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 453cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Replace temp blocks in each cut 454cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) { 455cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const CutEdgeVertexes& cut = cuts[i]; 456cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> real_extents = 457cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood scratch_ranges.GetExtentsForBlockCount(cuts_blocks_needed[i]); 458cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood scratch_ranges.SubtractExtents(real_extents); 459cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 460cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Fix the old dest node w/ the real blocks 461cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood InplaceGenerator::SubstituteBlocks(&(*graph)[old_dst], 462cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cut.tmp_extents, 463cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood real_extents); 464cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 465cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Fix the new node w/ the real blocks. Since the new node is just a 466cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // copy operation, we can replace all the dest extents w/ the real 467cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // blocks. 468a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation* op = &(*graph)[cut.new_vertex].aop.op; 469cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op->clear_dst_extents(); 47014158570d3995008dc93a628004118b87a6bca01Alex Deymo StoreExtents(real_extents, op->mutable_dst_extents()); 471cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 472cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return true; 473cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 474cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 475cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} // namespace 476cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 477cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodbool InplaceGenerator::AssignTempBlocks( 478cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph* graph, 479568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood const string& new_part, 4808cc502dacbccdab96824d42287f230ce04004784Sen Jiang BlobFileWriter* blob_file, 481cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index>* op_indexes, 482cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, 483cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<CutEdgeVertexes>& cuts) { 484cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK(!cuts.empty()); 485cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 486cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // group of cuts w/ the same old_dst: 487cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<CutEdgeVertexes> cuts_group; 488cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 489cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (vector<CutEdgeVertexes>::size_type i = cuts.size() - 1, e = 0; 490cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood true ; --i) { 491cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "Fixing temp blocks in cut " << i 492cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood << ": old dst: " << cuts[i].old_dst << " new vertex: " 493cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood << cuts[i].new_vertex << " path: " 4943b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo << (*graph)[cuts[i].old_dst].aop.name; 495cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 496cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (cuts_group.empty() || (cuts_group[0].old_dst == cuts[i].old_dst)) { 497cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts_group.push_back(cuts[i]); 498cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } else { 499cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK(!cuts_group.empty()); 500cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph, 501568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood new_part, 5028cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file, 503cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes, 504cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood reverse_op_indexes, 505cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts_group)); 506cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts_group.clear(); 507cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts_group.push_back(cuts[i]); 508cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 509cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 510cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (i == e) { 511cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // break out of for() loop 512cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood break; 513cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 514cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 515cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK(!cuts_group.empty()); 516cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph, 517568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood new_part, 5188cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file, 519cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes, 520cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood reverse_op_indexes, 521cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts_group)); 522cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return true; 523cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 524cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 525cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodbool InplaceGenerator::NoTempBlocksRemain(const Graph& graph) { 526cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood size_t idx = 0; 527cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (Graph::const_iterator it = graph.begin(), e = graph.end(); it != e; 528cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ++it, ++idx) { 529cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (!it->valid) 530cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood continue; 531a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo const InstallOperation& op = it->aop.op; 532cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (TempBlocksExistInExtents(op.dst_extents()) || 533cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood TempBlocksExistInExtents(op.src_extents())) { 534cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "bad extents in node " << idx; 535cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "so yeah"; 536cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return false; 537cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 538cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 539cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Check out-edges: 540cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (const auto& edge_prop_pair : it->out_edges) { 541cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (TempBlocksExistInExtents(edge_prop_pair.second.extents) || 542cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood TempBlocksExistInExtents(edge_prop_pair.second.write_extents)) { 543cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "bad out edge in node " << idx; 544cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "so yeah"; 545cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return false; 546cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 547cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 548cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 549cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return true; 550cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 551cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 552cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodbool InplaceGenerator::ConvertCutToFullOp(Graph* graph, 553cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const CutEdgeVertexes& cut, 554568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood const string& new_part, 5558cc502dacbccdab96824d42287f230ce04004784Sen Jiang BlobFileWriter* blob_file) { 556cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Drop all incoming edges, keep all outgoing edges 557cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 558cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Keep all outgoing edges 559a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo if ((*graph)[cut.old_dst].aop.op.type() != InstallOperation::REPLACE_BZ && 560a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo (*graph)[cut.old_dst].aop.op.type() != InstallOperation::REPLACE) { 561cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex::EdgeMap out_edges = (*graph)[cut.old_dst].out_edges; 562cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph_utils::DropWriteBeforeDeps(&out_edges); 563cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 5646b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo // Replace the operation with a REPLACE or REPLACE_BZ to generate the same 5656b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo // |new_extents| list of blocks and update the graph. 5666b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo vector<AnnotatedOperation> new_aop; 5676b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo vector<Extent> new_extents; 5683b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo ExtentsToVector((*graph)[cut.old_dst].aop.op.dst_extents(), 56914158570d3995008dc93a628004118b87a6bca01Alex Deymo &new_extents); 57014158570d3995008dc93a628004118b87a6bca01Alex Deymo TEST_AND_RETURN_FALSE(diff_utils::DeltaReadFile( 5716b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo &new_aop, 57214158570d3995008dc93a628004118b87a6bca01Alex Deymo "", // old_part 573568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood new_part, 5746b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo vector<Extent>(), // old_extents 5756b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo new_extents, 5763b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo (*graph)[cut.old_dst].aop.name, 5776b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo -1, // chunk_blocks, forces to have a single operation. 57838818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo kInPlacePayloadVersion, 57938818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo blob_file)); 5806b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo TEST_AND_RETURN_FALSE(new_aop.size() == 1); 5816b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo TEST_AND_RETURN_FALSE(AddInstallOpToGraph( 5826b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo graph, cut.old_dst, nullptr, new_aop.front().op, new_aop.front().name)); 583cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 584cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[cut.old_dst].out_edges = out_edges; 585cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 586cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Right now we don't have doubly-linked edges, so we have to scan 587cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // the whole graph. 588cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph_utils::DropIncomingEdgesTo(graph, cut.old_dst); 589cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 590cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 591cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Delete temp node 592cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[cut.old_src].out_edges.erase(cut.new_vertex); 593cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK((*graph)[cut.old_dst].out_edges.find(cut.new_vertex) == 594cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[cut.old_dst].out_edges.end()); 595cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[cut.new_vertex].valid = false; 596cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "marked node invalid: " << cut.new_vertex; 597cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return true; 598cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 599cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 600cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodbool InplaceGenerator::ConvertGraphToDag(Graph* graph, 6016b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo const string& new_part, 6028cc502dacbccdab96824d42287f230ce04004784Sen Jiang BlobFileWriter* blob_file, 6036b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo vector<Vertex::Index>* final_order, 6046b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo Vertex::Index scratch_vertex) { 605cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CycleBreaker cycle_breaker; 606cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "Finding cycles..."; 607cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood set<Edge> cut_edges; 608cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cycle_breaker.BreakCycles(*graph, &cut_edges); 609cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "done finding cycles"; 610477aec2166a571cbe28081d806c3226e8b31b6e9Alex Deymo CheckGraph(*graph); 611cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 612cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Calculate number of scratch blocks needed 613cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 614cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "Cutting cycles..."; 615cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<CutEdgeVertexes> cuts; 616cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood TEST_AND_RETURN_FALSE(CutEdges(graph, cut_edges, &cuts)); 617cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "done cutting cycles"; 618cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "There are " << cuts.size() << " cuts."; 619477aec2166a571cbe28081d806c3226e8b31b6e9Alex Deymo CheckGraph(*graph); 620cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 621cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "Creating initial topological order..."; 622cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood TopologicalSort(*graph, final_order); 623cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "done with initial topo order"; 624477aec2166a571cbe28081d806c3226e8b31b6e9Alex Deymo CheckGraph(*graph); 625cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 626cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "Moving full ops to the back"; 6273b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo MoveAndSortFullOpsToBack(graph, final_order); 628cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "done moving full ops to back"; 629cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 630cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<vector<Vertex::Index>::size_type> inverse_final_order; 631cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenerateReverseTopoOrderMap(*final_order, &inverse_final_order); 632cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 633cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood SortCutsByTopoOrder(*final_order, &cuts); 634cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 635cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (!cuts.empty()) 636cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood TEST_AND_RETURN_FALSE(AssignTempBlocks(graph, 637568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood new_part, 6388cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file, 639cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood final_order, 640cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood &inverse_final_order, 641cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts)); 642cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "Making sure all temp blocks have been allocated"; 643cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 644cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Remove the scratch node, if any 645cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (scratch_vertex != Vertex::kInvalidIndex) { 646cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood final_order->erase(final_order->begin() + 647cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood inverse_final_order[scratch_vertex]); 648cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*graph)[scratch_vertex].valid = false; 649cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenerateReverseTopoOrderMap(*final_order, &inverse_final_order); 650cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 651cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 652cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph_utils::DumpGraph(*graph); 653cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CHECK(NoTempBlocksRemain(*graph)); 654cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "done making sure all temp blocks are allocated"; 655cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return true; 656cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 657cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 658cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvoid InplaceGenerator::CreateScratchNode(uint64_t start_block, 659cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood uint64_t num_blocks, 660cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex* vertex) { 6613b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo vertex->aop.name = "<scratch>"; 662a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo vertex->aop.op.set_type(InstallOperation::REPLACE_BZ); 6633b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo vertex->aop.op.set_data_offset(0); 6643b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo vertex->aop.op.set_data_length(0); 6653b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo Extent* extent = vertex->aop.op.add_dst_extents(); 666cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood extent->set_start_block(start_block); 667cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood extent->set_num_blocks(num_blocks); 668cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 669cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 670cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodbool InplaceGenerator::AddInstallOpToBlocksVector( 671a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo const InstallOperation& operation, 672cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const Graph& graph, 673cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex::Index vertex, 6746b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo vector<Block>* blocks) { 675cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // See if this is already present. 676cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood TEST_AND_RETURN_FALSE(operation.dst_extents_size() > 0); 677cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 678cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood enum BlockField { READER = 0, WRITER, BLOCK_FIELD_COUNT }; 679cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (int field = READER; field < BLOCK_FIELD_COUNT; field++) { 680cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const int extents_size = 681cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (field == READER) ? operation.src_extents_size() : 682cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood operation.dst_extents_size(); 683cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const char* past_participle = (field == READER) ? "read" : "written"; 684cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const google::protobuf::RepeatedPtrField<Extent>& extents = 685cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (field == READER) ? operation.src_extents() : operation.dst_extents(); 6866b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo Vertex::Index Block::*access_type = (field == READER) ? 6876b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo &Block::reader : &Block::writer; 688cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 689cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (int i = 0; i < extents_size; i++) { 690cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const Extent& extent = extents.Get(i); 691cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (uint64_t block = extent.start_block(); 692cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood block < (extent.start_block() + extent.num_blocks()); block++) { 693cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if ((*blocks)[block].*access_type != Vertex::kInvalidIndex) { 694cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(FATAL) << "Block " << block << " is already " 695cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood << past_participle << " by " 696cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood << (*blocks)[block].*access_type << "(" 6973b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo << graph[(*blocks)[block].*access_type].aop.name 698cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood << ") and also " << vertex << "(" 6993b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo << graph[vertex].aop.name << ")"; 700cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 701cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood (*blocks)[block].*access_type = vertex; 702cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 703cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 704cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 705cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return true; 706cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 707cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 708a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymobool InplaceGenerator::AddInstallOpToGraph(Graph* graph, 709a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo Vertex::Index existing_vertex, 710a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo vector<Block>* blocks, 711a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo const InstallOperation operation, 712a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo const string& op_name) { 7136b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo Vertex::Index vertex = existing_vertex; 7146b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo if (vertex == Vertex::kInvalidIndex) { 7156b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo graph->emplace_back(); 7166b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo vertex = graph->size() - 1; 7176b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo } 7183b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo (*graph)[vertex].aop.op = operation; 7193b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo CHECK((*graph)[vertex].aop.op.has_type()); 7203b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo (*graph)[vertex].aop.name = op_name; 7216b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo 7226b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo if (blocks) 7236b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo TEST_AND_RETURN_FALSE(InplaceGenerator::AddInstallOpToBlocksVector( 7243b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo (*graph)[vertex].aop.op, 7256b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo *graph, 7266b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo vertex, 7276b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo blocks)); 7286b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo return true; 7296b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo} 7306b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo 73114158570d3995008dc93a628004118b87a6bca01Alex Deymovoid InplaceGenerator::ApplyMap(vector<uint64_t>* collection, 73214158570d3995008dc93a628004118b87a6bca01Alex Deymo const map<uint64_t, uint64_t>& the_map) { 73314158570d3995008dc93a628004118b87a6bca01Alex Deymo for (uint64_t& elem : *collection) { 73414158570d3995008dc93a628004118b87a6bca01Alex Deymo const auto& map_it = the_map.find(elem); 73514158570d3995008dc93a628004118b87a6bca01Alex Deymo if (map_it != the_map.end()) 73614158570d3995008dc93a628004118b87a6bca01Alex Deymo elem = map_it->second; 73714158570d3995008dc93a628004118b87a6bca01Alex Deymo } 73814158570d3995008dc93a628004118b87a6bca01Alex Deymo} 73914158570d3995008dc93a628004118b87a6bca01Alex Deymo 740f6165357bfbb74b22a4da5780a474f439611e167Alex Deymobool InplaceGenerator::ResolveReadAfterWriteDependencies( 741f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo const PartitionConfig& new_part, 742f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo uint64_t partition_size, 743f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo size_t block_size, 7448cc502dacbccdab96824d42287f230ce04004784Sen Jiang BlobFileWriter* blob_file, 745f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo vector<AnnotatedOperation>* aops) { 746f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo // Convert the operations to the graph. 747f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo Graph graph; 748f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo CheckGraph(graph); 749f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo vector<Block> blocks(new_part.size / block_size); 750f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo for (const auto& aop : *aops) { 751f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo AddInstallOpToGraph( 752f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo &graph, Vertex::kInvalidIndex, &blocks, aop.op, aop.name); 753f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo } 754f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo CheckGraph(graph); 755f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo 756f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo // Final scratch block (if there's space) 757f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo Vertex::Index scratch_vertex = Vertex::kInvalidIndex; 758f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo if (blocks.size() < (partition_size / block_size)) { 759f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo scratch_vertex = graph.size(); 760f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo graph.emplace_back(); 761f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo size_t scratch_blocks = (partition_size / block_size) - blocks.size(); 762f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo LOG(INFO) << "Added " << scratch_blocks << " scratch space blocks."; 763f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo CreateScratchNode(blocks.size(), scratch_blocks, &graph.back()); 764f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo } 765f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo CheckGraph(graph); 766f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo 767f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo LOG(INFO) << "Creating edges..."; 768f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo CreateEdges(&graph, blocks); 769f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo LOG(INFO) << "Done creating edges"; 770f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo CheckGraph(graph); 771f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo 772f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo vector<Vertex::Index> final_order; 773f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo TEST_AND_RETURN_FALSE(ConvertGraphToDag( 774f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo &graph, 775f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo new_part.path, 7768cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file, 777f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo &final_order, 778f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo scratch_vertex)); 779f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo 780f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo // Copy operations over to the |aops| vector in the final_order generated by 781f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo // the topological sort. 782f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo aops->clear(); 783f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo aops->reserve(final_order.size()); 784f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo for (const Vertex::Index vertex_index : final_order) { 785f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo const Vertex& vertex = graph[vertex_index]; 7863b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo aops->push_back(vertex.aop); 787f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo } 788f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo return true; 789f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo} 790f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo 791ebdf17d4202c67933764135bfc1cece629829201Sen Jiangbool InplaceGenerator::GenerateOperations( 792ebdf17d4202c67933764135bfc1cece629829201Sen Jiang const PayloadGenerationConfig& config, 793896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo const PartitionConfig& old_part, 794896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo const PartitionConfig& new_part, 7958cc502dacbccdab96824d42287f230ce04004784Sen Jiang BlobFileWriter* blob_file, 796896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo vector<AnnotatedOperation>* aops) { 797625406cee9a90ac2ed895f480286b7f0e8497f38Sen Jiang TEST_AND_RETURN_FALSE(old_part.name == new_part.name); 79838818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo TEST_AND_RETURN_FALSE(config.version.major == kInPlacePayloadVersion.major); 79938818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo TEST_AND_RETURN_FALSE(config.version.minor == kInPlacePayloadVersion.minor); 800625406cee9a90ac2ed895f480286b7f0e8497f38Sen Jiang 801ebdf17d4202c67933764135bfc1cece629829201Sen Jiang ssize_t hard_chunk_blocks = (config.hard_chunk_size == -1 ? -1 : 802ebdf17d4202c67933764135bfc1cece629829201Sen Jiang config.hard_chunk_size / config.block_size); 803ebdf17d4202c67933764135bfc1cece629829201Sen Jiang size_t soft_chunk_blocks = config.soft_chunk_size / config.block_size; 804ebdf17d4202c67933764135bfc1cece629829201Sen Jiang uint64_t partition_size = new_part.size; 805625406cee9a90ac2ed895f480286b7f0e8497f38Sen Jiang if (new_part.name == kLegacyPartitionNameRoot) 806ebdf17d4202c67933764135bfc1cece629829201Sen Jiang partition_size = config.rootfs_partition_size; 807ebdf17d4202c67933764135bfc1cece629829201Sen Jiang 808625406cee9a90ac2ed895f480286b7f0e8497f38Sen Jiang LOG(INFO) << "Delta compressing " << new_part.name << " partition..."; 80938818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo TEST_AND_RETURN_FALSE(diff_utils::DeltaReadPartition(aops, 81038818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo old_part, 81138818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo new_part, 81238818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo hard_chunk_blocks, 81338818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo soft_chunk_blocks, 81438818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo config.version, 81538818fbf1f2f937051b5bcc01ff74539a3c9b27dAlex Deymo blob_file)); 816625406cee9a90ac2ed895f480286b7f0e8497f38Sen Jiang LOG(INFO) << "Done reading " << new_part.name; 8179b244df41f1bdaddd87b7dbd8e1559556059ed1bAlex Deymo 818f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo TEST_AND_RETURN_FALSE( 819ebdf17d4202c67933764135bfc1cece629829201Sen Jiang ResolveReadAfterWriteDependencies(new_part, 820ebdf17d4202c67933764135bfc1cece629829201Sen Jiang partition_size, 821ebdf17d4202c67933764135bfc1cece629829201Sen Jiang config.block_size, 822ebdf17d4202c67933764135bfc1cece629829201Sen Jiang blob_file, 823ebdf17d4202c67933764135bfc1cece629829201Sen Jiang aops)); 824625406cee9a90ac2ed895f480286b7f0e8497f38Sen Jiang LOG(INFO) << "Done reordering " << new_part.name; 825896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo return true; 826896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo} 827f6165357bfbb74b22a4da5780a474f439611e167Alex Deymo 828cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood}; // namespace chromeos_update_engine 829