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