inplace_generator.h revision 14158570d3995008dc93a628004118b87a6bca01
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 <map> 9#include <set> 10#include <string> 11#include <vector> 12 13#include "update_engine/payload_generator/delta_diff_generator.h" 14#include "update_engine/payload_generator/graph_types.h" 15#include "update_engine/payload_generator/operations_generator.h" 16 17// InplaceGenerator contains all functionality related to the inplace algorithm 18// for generating update payloads. These are the functions used when delta minor 19// version is 1. 20 21namespace chromeos_update_engine { 22 23// This struct stores all relevant info for an edge that is cut between 24// nodes old_src -> old_dst by creating new vertex new_vertex. The new 25// relationship is: 26// old_src -(read before)-> new_vertex <-(write before)- old_dst 27// new_vertex is a MOVE operation that moves some existing blocks into 28// temp space. The temp extents are, by necessity, stored in new_vertex 29// (as dst extents) and old_dst (as src extents), but they are also broken 30// out into tmp_extents, as the nodes themselves may contain many more 31// extents. 32struct CutEdgeVertexes { 33 Vertex::Index new_vertex; 34 Vertex::Index old_src; 35 Vertex::Index old_dst; 36 std::vector<Extent> tmp_extents; 37}; 38 39class InplaceGenerator : public OperationsGenerator { 40 public: 41 // Represents a disk block on the install partition. 42 struct Block { 43 // During install, each block on the install partition will be written 44 // and some may be read (in all likelihood, many will be read). 45 // The reading and writing will be performed by InstallOperations, 46 // each of which has a corresponding vertex in a graph. 47 // A Block object tells which vertex will read or write this block 48 // at install time. 49 // Generally, there will be a vector of Block objects whose length 50 // is the number of blocks on the install partition. 51 Block() : reader(Vertex::kInvalidIndex), writer(Vertex::kInvalidIndex) {} 52 Vertex::Index reader; 53 Vertex::Index writer; 54 }; 55 56 InplaceGenerator() = default; 57 58 // Checks all the operations in the graph have a type assigned. 59 static void CheckGraph(const Graph& graph); 60 61 // Modifies blocks read by 'op' so that any blocks referred to by 62 // 'remove_extents' are replaced with blocks from 'replace_extents'. 63 // 'remove_extents' and 'replace_extents' must be the same number of blocks. 64 // Blocks will be substituted in the order listed in the vectors. 65 // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents 66 // contains blocks 6, 2, 3, 5, and replace blocks contains 67 // 12, 13, 14, 15, then op will be changed to read from: 68 // 1, 13, 14, 4, 15, 12, 7, 8 69 static void SubstituteBlocks(Vertex* vertex, 70 const std::vector<Extent>& remove_extents, 71 const std::vector<Extent>& replace_extents); 72 73 // Cuts 'edges' from 'graph' according to the AU algorithm. This means 74 // for each edge A->B, remove the dependency that B occur before A. 75 // Do this by creating a new operation X that copies from the blocks 76 // specified by the edge's properties to temp space T. Modify B to read 77 // from T rather than the blocks in the edge. Modify A to depend on X, 78 // but not on B. Free space is found by looking in 'blocks'. 79 // Returns true on success. 80 static bool CutEdges(Graph* graph, 81 const std::set<Edge>& edges, 82 std::vector<CutEdgeVertexes>* out_cuts); 83 84 // Creates all the edges for the graph. Writers of a block point to 85 // readers of the same block. This is because for an edge A->B, B 86 // must complete before A executes. 87 static void CreateEdges(Graph* graph, 88 const std::vector<Block>& blocks); 89 90 // Takes |op_indexes|, which is effectively a mapping from order in 91 // which the op is performed -> graph vertex index, and produces the 92 // reverse: a mapping from graph vertex index -> op_indexes index. 93 static void GenerateReverseTopoOrderMap( 94 const std::vector<Vertex::Index>& op_indexes, 95 std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes); 96 97 // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is 98 // determined by the order of elements in op_indexes. 99 static void SortCutsByTopoOrder( 100 const std::vector<Vertex::Index>& op_indexes, 101 std::vector<CutEdgeVertexes>* cuts); 102 103 // Given a topologically sorted graph |op_indexes| and |graph|, alters 104 // |op_indexes| to move all the full operations to the end of the vector. 105 // Full operations should not be depended on, so this is safe. 106 static void MoveFullOpsToBack(Graph* graph, 107 std::vector<Vertex::Index>* op_indexes); 108 109 // Returns true iff there are no extents in the graph that refer to temp 110 // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole). 111 static bool NoTempBlocksRemain(const Graph& graph); 112 113 // Takes a |graph|, which has edges that must be cut, as listed in 114 // |cuts|. Cuts the edges. Maintains a list in which the operations 115 // will be performed (in |op_indexes|) and the reverse (in 116 // |reverse_op_indexes|). Cutting edges requires scratch space, and 117 // if insufficient scratch is found, the file is reread and will be 118 // send down (either as REPLACE or REPLACE_BZ). Returns true on 119 // success. 120 static bool AssignTempBlocks( 121 Graph* graph, 122 const std::string& new_part, 123 int data_fd, 124 off_t* data_file_size, 125 std::vector<Vertex::Index>* op_indexes, 126 std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes, 127 const std::vector<CutEdgeVertexes>& cuts); 128 129 // Handles allocation of temp blocks to a cut edge by converting the 130 // dest node to a full op. This removes the need for temp blocks, but 131 // comes at the cost of a worse compression ratio. 132 // For example, say we have A->B->A. It would first be cut to form: 133 // A->B->N<-A, where N copies blocks to temp space. If there are no 134 // temp blocks, this function can be called to convert it to the form: 135 // A->B. Now, A is a full operation. 136 static bool ConvertCutToFullOp(Graph* graph, 137 const CutEdgeVertexes& cut, 138 const std::string& new_part, 139 int data_fd, 140 off_t* data_file_size); 141 142 // Takes a graph, which is not a DAG, which represents the files just 143 // read from disk, and converts it into a DAG by breaking all cycles 144 // and finding temp space to resolve broken edges. 145 // The final order of the nodes is given in |final_order| 146 // Some files may need to be reread from disk, thus |fd| and 147 // |data_file_size| are be passed. 148 // If |scratch_vertex| is not kInvalidIndex, removes it from 149 // |final_order| before returning. 150 // Returns true on success. 151 static bool ConvertGraphToDag(Graph* graph, 152 const std::string& new_part, 153 int fd, 154 off_t* data_file_size, 155 std::vector<Vertex::Index>* final_order, 156 Vertex::Index scratch_vertex); 157 158 // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used 159 // to provide scratch space. The node writes |num_blocks| blocks starting at 160 // |start_block|The node should be marked invalid before writing all nodes to 161 // the output file. 162 static void CreateScratchNode(uint64_t start_block, 163 uint64_t num_blocks, 164 Vertex* vertex); 165 166 // The |blocks| vector contains a reader and writer for each block on the 167 // filesystem that's being in-place updated. We populate the reader/writer 168 // fields of |blocks| by calling this function. 169 // For each block in |operation| that is read or written, find that block 170 // in |blocks| and set the reader/writer field to the vertex passed. 171 // |graph| is not strictly necessary, but useful for printing out 172 // error messages. 173 static bool AddInstallOpToBlocksVector( 174 const DeltaArchiveManifest_InstallOperation& operation, 175 const Graph& graph, 176 Vertex::Index vertex, 177 std::vector<Block>* blocks); 178 179 // Add a vertex (if |existing_vertex| is kInvalidVertex) or update an 180 // |existing_vertex| with the passed |operation|. 181 // This method will also register the vertex as the reader or writer of the 182 // blocks involved in the operation updating the |blocks| vector. The 183 // |op_name| associated with the Vertex is used for logging purposes. 184 static bool AddInstallOpToGraph( 185 Graph* graph, 186 Vertex::Index existing_vertex, 187 std::vector<Block>* blocks, 188 const DeltaArchiveManifest_InstallOperation operation, 189 const std::string& op_name); 190 191 // Apply the transformation stored in |the_map| to the |collection| vector 192 // replacing the map keys found in |collection| with its associated value in 193 // |the_map|. 194 static void ApplyMap(std::vector<uint64_t>* collection, 195 const std::map<uint64_t, uint64_t>& the_map); 196 197 // Generate the update payload operations for the kernel and rootfs using 198 // only operations that read from the target and/or write to the target, 199 // hence, applying the payload "in-place" in the target partition. This method 200 // assumes that the contents of the source image are pre-copied to the target 201 // partition, up to the size of the source image. Use this method to generate 202 // a delta update with the minor version kInPlaceMinorPayloadVersion. 203 // The rootfs operations are stored in |graph| and should be executed in the 204 // |final_order| order. The kernel operations are stored in |kernel_ops|. All 205 // the offsets in the operations reference the data written to |data_file_fd|. 206 // The total amount of data written to that file is stored in 207 // |data_file_size|. 208 bool GenerateOperations( 209 const PayloadGenerationConfig& config, 210 int data_file_fd, 211 off_t* data_file_size, 212 std::vector<AnnotatedOperation>* rootfs_ops, 213 std::vector<AnnotatedOperation>* kernel_ops) override; 214 215 private: 216 DISALLOW_COPY_AND_ASSIGN(InplaceGenerator); 217}; 218 219}; // namespace chromeos_update_engine 220 221#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_ 222