delta_diff_generator.h revision b8ccad0a8ac2632da2788b47d85e62e334bbe652
1// Copyright (c) 2012 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_DELTA_DIFF_GENERATOR_H_ 6#define UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_ 7 8#include <set> 9#include <string> 10#include <vector> 11 12#include <base/macros.h> 13 14#include "update_engine/payload_generator/graph_types.h" 15#include "update_engine/update_metadata.pb.h" 16 17// There is one function in DeltaDiffGenerator of importance to users 18// of the class: GenerateDeltaUpdateFile(). Before calling it, 19// the old and new images must be mounted. Call GenerateDeltaUpdateFile() 20// with both the mount-points of the images in addition to the paths of 21// the images (both old and new). A delta from old to new will be 22// generated and stored in output_path. 23 24namespace chromeos_update_engine { 25 26// This struct stores all relevant info for an edge that is cut between 27// nodes old_src -> old_dst by creating new vertex new_vertex. The new 28// relationship is: 29// old_src -(read before)-> new_vertex <-(write before)- old_dst 30// new_vertex is a MOVE operation that moves some existing blocks into 31// temp space. The temp extents are, by necessity, stored in new_vertex 32// (as dst extents) and old_dst (as src extents), but they are also broken 33// out into tmp_extents, as the nodes themselves may contain many more 34// extents. 35struct CutEdgeVertexes { 36 Vertex::Index new_vertex; 37 Vertex::Index old_src; 38 Vertex::Index old_dst; 39 std::vector<Extent> tmp_extents; 40}; 41 42class DeltaDiffGenerator { 43 public: 44 // Represents a disk block on the install partition. 45 struct Block { 46 // During install, each block on the install partition will be written 47 // and some may be read (in all likelihood, many will be read). 48 // The reading and writing will be performed by InstallOperations, 49 // each of which has a corresponding vertex in a graph. 50 // A Block object tells which vertex will read or write this block 51 // at install time. 52 // Generally, there will be a vector of Block objects whose length 53 // is the number of blocks on the install partition. 54 Block() : reader(Vertex::kInvalidIndex), writer(Vertex::kInvalidIndex) {} 55 Vertex::Index reader; 56 Vertex::Index writer; 57 }; 58 59 // This is the only function that external users of the class should call. 60 // old_image and new_image are paths to two image files. They should be 61 // mounted read-only at paths old_root and new_root respectively. 62 // {old,new}_kernel_part are paths to the old and new kernel partition 63 // images, respectively. 64 // private_key_path points to a private key used to sign the update. 65 // Pass empty string to not sign the update. 66 // output_path is the filename where the delta update should be written. 67 // If |chunk_size| is not -1, the delta payload is generated based on 68 // |chunk_size| chunks rather than whole files. 69 // This method computes scratch space based on |rootfs_partition_size|. 70 // |minor_version| indicates the payload minor version for a delta update. 71 // Returns true on success. Also writes the size of the metadata into 72 // |metadata_size|. 73 static bool GenerateDeltaUpdateFile(const std::string& old_root, 74 const std::string& old_image, 75 const std::string& new_root, 76 const std::string& new_image, 77 const std::string& old_kernel_part, 78 const std::string& new_kernel_part, 79 const std::string& output_path, 80 const std::string& private_key_path, 81 off_t chunk_size, 82 size_t rootfs_partition_size, 83 uint64_t minor_version, 84 const ImageInfo* old_image_info, 85 const ImageInfo* new_image_info, 86 uint64_t* metadata_size); 87 88 // These functions are public so that the unit tests can access them: 89 90 // Takes a graph, which is not a DAG, which represents the files just 91 // read from disk, and converts it into a DAG by breaking all cycles 92 // and finding temp space to resolve broken edges. 93 // The final order of the nodes is given in |final_order| 94 // Some files may need to be reread from disk, thus |fd| and 95 // |data_file_size| are be passed. 96 // If |scratch_vertex| is not kInvalidIndex, removes it from 97 // |final_order| before returning. 98 // Returns true on success. 99 static bool ConvertGraphToDag(Graph* graph, 100 const std::string& new_root, 101 int fd, 102 off_t* data_file_size, 103 std::vector<Vertex::Index>* final_order, 104 Vertex::Index scratch_vertex); 105 106 // Reads old_filename (if it exists) and a new_filename and determines 107 // the smallest way to encode this file for the diff. It stores 108 // necessary data in out_data and fills in out_op. 109 // If there's no change in old and new files, it creates a MOVE 110 // operation. If there is a change, or the old file doesn't exist, 111 // the smallest of REPLACE, REPLACE_BZ, or BSDIFF wins. 112 // new_filename must contain at least one byte. 113 // |new_filename| is read starting at |chunk_offset|. 114 // If |chunk_size| is not -1, only up to |chunk_size| bytes are diffed. 115 // Returns true on success. 116 static bool ReadFileToDiff(const std::string& old_filename, 117 const std::string& new_filename, 118 off_t chunk_offset, 119 off_t chunk_size, 120 bool bsdiff_allowed, 121 std::vector<char>* out_data, 122 DeltaArchiveManifest_InstallOperation* out_op, 123 bool gather_extents); 124 125 // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used 126 // to provide scratch space. The node writes |num_blocks| blocks starting at 127 // |start_block|The node should be marked invalid before writing all nodes to 128 // the output file. 129 static void CreateScratchNode(uint64_t start_block, 130 uint64_t num_blocks, 131 Vertex* vertex); 132 133 // Modifies blocks read by 'op' so that any blocks referred to by 134 // 'remove_extents' are replaced with blocks from 'replace_extents'. 135 // 'remove_extents' and 'replace_extents' must be the same number of blocks. 136 // Blocks will be substituted in the order listed in the vectors. 137 // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents 138 // contains blocks 6, 2, 3, 5, and replace blocks contains 139 // 12, 13, 14, 15, then op will be changed to read from: 140 // 1, 13, 14, 4, 15, 12, 7, 8 141 static void SubstituteBlocks(Vertex* vertex, 142 const std::vector<Extent>& remove_extents, 143 const std::vector<Extent>& replace_extents); 144 145 // Cuts 'edges' from 'graph' according to the AU algorithm. This means 146 // for each edge A->B, remove the dependency that B occur before A. 147 // Do this by creating a new operation X that copies from the blocks 148 // specified by the edge's properties to temp space T. Modify B to read 149 // from T rather than the blocks in the edge. Modify A to depend on X, 150 // but not on B. Free space is found by looking in 'blocks'. 151 // Returns true on success. 152 static bool CutEdges(Graph* graph, 153 const std::set<Edge>& edges, 154 std::vector<CutEdgeVertexes>* out_cuts); 155 156 // Stores all Extents in 'extents' into 'out'. 157 static void StoreExtents(const std::vector<Extent>& extents, 158 google::protobuf::RepeatedPtrField<Extent>* out); 159 160 // Creates all the edges for the graph. Writers of a block point to 161 // readers of the same block. This is because for an edge A->B, B 162 // must complete before A executes. 163 static void CreateEdges(Graph* graph, const std::vector<Block>& blocks); 164 165 // Given a topologically sorted graph |op_indexes| and |graph|, alters 166 // |op_indexes| to move all the full operations to the end of the vector. 167 // Full operations should not be depended on, so this is safe. 168 static void MoveFullOpsToBack(Graph* graph, 169 std::vector<Vertex::Index>* op_indexes); 170 171 // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is 172 // determined by the order of elements in op_indexes. 173 static void SortCutsByTopoOrder( 174 const std::vector<Vertex::Index>& op_indexes, 175 std::vector<CutEdgeVertexes>* cuts); 176 177 // Returns true iff there are no extents in the graph that refer to temp 178 // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole). 179 static bool NoTempBlocksRemain(const Graph& graph); 180 181 // Install operations in the manifest may reference data blobs, which 182 // are in data_blobs_path. This function creates a new data blobs file 183 // with the data blobs in the same order as the referencing install 184 // operations in the manifest. E.g. if manifest[0] has a data blob 185 // "X" at offset 1, manifest[1] has a data blob "Y" at offset 0, 186 // and data_blobs_path's file contains "YX", new_data_blobs_path 187 // will set to be a file that contains "XY". 188 static bool ReorderDataBlobs(DeltaArchiveManifest* manifest, 189 const std::string& data_blobs_path, 190 const std::string& new_data_blobs_path); 191 192 // Computes a SHA256 hash of the given buf and sets the hash value in the 193 // operation so that update_engine could verify. This hash should be set 194 // for all operations that have a non-zero data blob. One exception is the 195 // dummy operation for signature blob because the contents of the signature 196 // blob will not be available at payload creation time. So, update_engine will 197 // gracefully ignore the dummy signature operation. 198 static bool AddOperationHash(DeltaArchiveManifest_InstallOperation* op, 199 const std::vector<char>& buf); 200 201 // Handles allocation of temp blocks to a cut edge by converting the 202 // dest node to a full op. This removes the need for temp blocks, but 203 // comes at the cost of a worse compression ratio. 204 // For example, say we have A->B->A. It would first be cut to form: 205 // A->B->N<-A, where N copies blocks to temp space. If there are no 206 // temp blocks, this function can be called to convert it to the form: 207 // A->B. Now, A is a full operation. 208 static bool ConvertCutToFullOp(Graph* graph, 209 const CutEdgeVertexes& cut, 210 const std::string& new_root, 211 int data_fd, 212 off_t* data_file_size); 213 214 // Takes |op_indexes|, which is effectively a mapping from order in 215 // which the op is performed -> graph vertex index, and produces the 216 // reverse: a mapping from graph vertex index -> op_indexes index. 217 static void GenerateReverseTopoOrderMap( 218 const std::vector<Vertex::Index>& op_indexes, 219 std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes); 220 221 // Takes a |graph|, which has edges that must be cut, as listed in 222 // |cuts|. Cuts the edges. Maintains a list in which the operations 223 // will be performed (in |op_indexes|) and the reverse (in 224 // |reverse_op_indexes|). Cutting edges requires scratch space, and 225 // if insufficient scratch is found, the file is reread and will be 226 // send down (either as REPLACE or REPLACE_BZ). Returns true on 227 // success. 228 static bool AssignTempBlocks( 229 Graph* graph, 230 const std::string& new_root, 231 int data_fd, 232 off_t* data_file_size, 233 std::vector<Vertex::Index>* op_indexes, 234 std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes, 235 const std::vector<CutEdgeVertexes>& cuts); 236 237 // Returns true if |op| is a no-op operation that doesn't do any useful work 238 // (e.g., a move operation that copies blocks onto themselves). 239 static bool IsNoopOperation(const DeltaArchiveManifest_InstallOperation& op); 240 241 static bool InitializePartitionInfo(bool is_kernel, 242 const std::string& partition, 243 PartitionInfo* info); 244 245 // Runs the bsdiff tool on two files and returns the resulting delta in 246 // |out|. Returns true on success. 247 static bool BsdiffFiles(const std::string& old_file, 248 const std::string& new_file, 249 std::vector<char>* out); 250 251 // The |blocks| vector contains a reader and writer for each block on the 252 // filesystem that's being in-place updated. We populate the reader/writer 253 // fields of |blocks| by calling this function. 254 // For each block in |operation| that is read or written, find that block 255 // in |blocks| and set the reader/writer field to the vertex passed. 256 // |graph| is not strictly necessary, but useful for printing out 257 // error messages. 258 static bool AddInstallOpToBlocksVector( 259 const DeltaArchiveManifest_InstallOperation& operation, 260 const Graph& graph, 261 Vertex::Index vertex, 262 std::vector<DeltaDiffGenerator::Block>* blocks); 263 264 // Adds to |manifest| a dummy operation that points to a signature blob 265 // located at the specified offset/length. 266 static void AddSignatureOp(uint64_t signature_blob_offset, 267 uint64_t signature_blob_length, 268 DeltaArchiveManifest* manifest); 269 270 private: 271 // This should never be constructed. 272 DISALLOW_IMPLICIT_CONSTRUCTORS(DeltaDiffGenerator); 273}; 274 275extern const char* const kBsdiffPath; 276extern const size_t kRootFSPartitionSize; 277 278}; // namespace chromeos_update_engine 279 280#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_ 281