inplace_generator.h revision f1cbe1783dd025bd7243a8df12f20548196cc023
1// Copyright 2015 The Chromium OS Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_ 6#define UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_ 7 8#include <set> 9#include <string> 10#include <vector> 11 12#include "update_engine/payload_generator/delta_diff_generator.h" 13#include "update_engine/payload_generator/graph_types.h" 14 15// InplaceGenerator contains all functionality related to the inplace algorithm 16// for generating update payloads. These are the functions used when delta minor 17// version is 1. 18 19namespace chromeos_update_engine { 20 21// This struct stores all relevant info for an edge that is cut between 22// nodes old_src -> old_dst by creating new vertex new_vertex. The new 23// relationship is: 24// old_src -(read before)-> new_vertex <-(write before)- old_dst 25// new_vertex is a MOVE operation that moves some existing blocks into 26// temp space. The temp extents are, by necessity, stored in new_vertex 27// (as dst extents) and old_dst (as src extents), but they are also broken 28// out into tmp_extents, as the nodes themselves may contain many more 29// extents. 30struct CutEdgeVertexes { 31 Vertex::Index new_vertex; 32 Vertex::Index old_src; 33 Vertex::Index old_dst; 34 std::vector<Extent> tmp_extents; 35}; 36 37class InplaceGenerator { 38 public: 39 // Modifies blocks read by 'op' so that any blocks referred to by 40 // 'remove_extents' are replaced with blocks from 'replace_extents'. 41 // 'remove_extents' and 'replace_extents' must be the same number of blocks. 42 // Blocks will be substituted in the order listed in the vectors. 43 // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents 44 // contains blocks 6, 2, 3, 5, and replace blocks contains 45 // 12, 13, 14, 15, then op will be changed to read from: 46 // 1, 13, 14, 4, 15, 12, 7, 8 47 static void SubstituteBlocks(Vertex* vertex, 48 const std::vector<Extent>& remove_extents, 49 const std::vector<Extent>& replace_extents); 50 51 // Cuts 'edges' from 'graph' according to the AU algorithm. This means 52 // for each edge A->B, remove the dependency that B occur before A. 53 // Do this by creating a new operation X that copies from the blocks 54 // specified by the edge's properties to temp space T. Modify B to read 55 // from T rather than the blocks in the edge. Modify A to depend on X, 56 // but not on B. Free space is found by looking in 'blocks'. 57 // Returns true on success. 58 static bool CutEdges(Graph* graph, 59 const std::set<Edge>& edges, 60 std::vector<CutEdgeVertexes>* out_cuts); 61 62 // Creates all the edges for the graph. Writers of a block point to 63 // readers of the same block. This is because for an edge A->B, B 64 // must complete before A executes. 65 static void CreateEdges(Graph* graph, 66 const std::vector<DeltaDiffGenerator::Block>& blocks); 67 68 // Takes |op_indexes|, which is effectively a mapping from order in 69 // which the op is performed -> graph vertex index, and produces the 70 // reverse: a mapping from graph vertex index -> op_indexes index. 71 static void GenerateReverseTopoOrderMap( 72 const std::vector<Vertex::Index>& op_indexes, 73 std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes); 74 75 // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is 76 // determined by the order of elements in op_indexes. 77 static void SortCutsByTopoOrder( 78 const std::vector<Vertex::Index>& op_indexes, 79 std::vector<CutEdgeVertexes>* cuts); 80 81 // Given a topologically sorted graph |op_indexes| and |graph|, alters 82 // |op_indexes| to move all the full operations to the end of the vector. 83 // Full operations should not be depended on, so this is safe. 84 static void MoveFullOpsToBack(Graph* graph, 85 std::vector<Vertex::Index>* op_indexes); 86 87 // Returns true iff there are no extents in the graph that refer to temp 88 // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole). 89 static bool NoTempBlocksRemain(const Graph& graph); 90 91 // Takes a |graph|, which has edges that must be cut, as listed in 92 // |cuts|. Cuts the edges. Maintains a list in which the operations 93 // will be performed (in |op_indexes|) and the reverse (in 94 // |reverse_op_indexes|). Cutting edges requires scratch space, and 95 // if insufficient scratch is found, the file is reread and will be 96 // send down (either as REPLACE or REPLACE_BZ). Returns true on 97 // success. 98 static bool AssignTempBlocks( 99 Graph* graph, 100 const std::string& new_root, 101 int data_fd, 102 off_t* data_file_size, 103 std::vector<Vertex::Index>* op_indexes, 104 std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes, 105 const std::vector<CutEdgeVertexes>& cuts); 106 107 // Handles allocation of temp blocks to a cut edge by converting the 108 // dest node to a full op. This removes the need for temp blocks, but 109 // comes at the cost of a worse compression ratio. 110 // For example, say we have A->B->A. It would first be cut to form: 111 // A->B->N<-A, where N copies blocks to temp space. If there are no 112 // temp blocks, this function can be called to convert it to the form: 113 // A->B. Now, A is a full operation. 114 static bool ConvertCutToFullOp(Graph* graph, 115 const CutEdgeVertexes& cut, 116 const std::string& new_root, 117 int data_fd, 118 off_t* data_file_size); 119 120 // Takes a graph, which is not a DAG, which represents the files just 121 // read from disk, and converts it into a DAG by breaking all cycles 122 // and finding temp space to resolve broken edges. 123 // The final order of the nodes is given in |final_order| 124 // Some files may need to be reread from disk, thus |fd| and 125 // |data_file_size| are be passed. 126 // If |scratch_vertex| is not kInvalidIndex, removes it from 127 // |final_order| before returning. 128 // Returns true on success. 129 static bool ConvertGraphToDag(Graph* graph, 130 const std::string& new_root, 131 int fd, 132 off_t* data_file_size, 133 std::vector<Vertex::Index>* final_order, 134 Vertex::Index scratch_vertex); 135 136 // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used 137 // to provide scratch space. The node writes |num_blocks| blocks starting at 138 // |start_block|The node should be marked invalid before writing all nodes to 139 // the output file. 140 static void CreateScratchNode(uint64_t start_block, 141 uint64_t num_blocks, 142 Vertex* vertex); 143 144 // The |blocks| vector contains a reader and writer for each block on the 145 // filesystem that's being in-place updated. We populate the reader/writer 146 // fields of |blocks| by calling this function. 147 // For each block in |operation| that is read or written, find that block 148 // in |blocks| and set the reader/writer field to the vertex passed. 149 // |graph| is not strictly necessary, but useful for printing out 150 // error messages. 151 static bool AddInstallOpToBlocksVector( 152 const DeltaArchiveManifest_InstallOperation& operation, 153 const Graph& graph, 154 Vertex::Index vertex, 155 std::vector<DeltaDiffGenerator::Block>* blocks); 156 157 private: 158 // This should never be constructed. 159 DISALLOW_IMPLICIT_CONSTRUCTORS(InplaceGenerator); 160}; 161 162}; // namespace chromeos_update_engine 163 164#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_ 165