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