delta_diff_generator.h revision fffd23e1ed1903beeb893640c611001175380186 
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_constants.h"
16#include "update_engine/payload_generator/graph_types.h"
17#include "update_engine/payload_generator/graph_utils.h"
18#include "update_engine/update_metadata.pb.h"
19
20// There is one function in DeltaDiffGenerator of importance to users
21// of the class: GenerateDeltaUpdateFile(). Before calling it,
22// the old and new images must be mounted. Call GenerateDeltaUpdateFile()
23// with both the mount-points of the images in addition to the paths of
24// the images (both old and new). A delta from old to new will be
25// generated and stored in output_path.
26
27namespace chromeos_update_engine {
28
29extern const char* const kEmptyPath;
30extern const size_t kBlockSize;
31extern const size_t kRootFSPartitionSize;
32
33// The minor version used by the in-place delta generator algorithm.
34extern const uint32_t kInPlaceMinorPayloadVersion;
35
36// The minor version used by the A to B delta generator algorithm.
37extern const uint32_t kSourceMinorPayloadVersion;
38
39// This struct stores all relevant info for an edge that is cut between
40// nodes old_src -> old_dst by creating new vertex new_vertex. The new
41// relationship is:
42// old_src -(read before)-> new_vertex <-(write before)- old_dst
43// new_vertex is a MOVE operation that moves some existing blocks into
44// temp space. The temp extents are, by necessity, stored in new_vertex
45// (as dst extents) and old_dst (as src extents), but they are also broken
46// out into tmp_extents, as the nodes themselves may contain many more
47// extents.
48struct CutEdgeVertexes {
49  Vertex::Index new_vertex;
50  Vertex::Index old_src;
51  Vertex::Index old_dst;
52  std::vector<Extent> tmp_extents;
53};
54
55class DeltaDiffGenerator {
56 public:
57  // Represents a disk block on the install partition.
58  struct Block {
59    // During install, each block on the install partition will be written
60    // and some may be read (in all likelihood, many will be read).
61    // The reading and writing will be performed by InstallOperations,
62    // each of which has a corresponding vertex in a graph.
63    // A Block object tells which vertex will read or write this block
64    // at install time.
65    // Generally, there will be a vector of Block objects whose length
66    // is the number of blocks on the install partition.
67    Block() : reader(Vertex::kInvalidIndex), writer(Vertex::kInvalidIndex) {}
68    Vertex::Index reader;
69    Vertex::Index writer;
70  };
71
72  // This is the only function that external users of the class should call.
73  // old_image and new_image are paths to two image files. They should be
74  // mounted read-only at paths old_root and new_root respectively.
75  // {old,new}_kernel_part are paths to the old and new kernel partition
76  // images, respectively.
77  // private_key_path points to a private key used to sign the update.
78  // Pass empty string to not sign the update.
79  // output_path is the filename where the delta update should be written.
80  // If |chunk_size| is not -1, the delta payload is generated based on
81  // |chunk_size| chunks rather than whole files.
82  // This method computes scratch space based on |rootfs_partition_size|.
83  // |minor_version| indicates the payload minor version for a delta update.
84  // Returns true on success. Also writes the size of the metadata into
85  // |metadata_size|.
86  static bool GenerateDeltaUpdateFile(const std::string& old_root,
87                                      const std::string& old_image,
88                                      const std::string& new_root,
89                                      const std::string& new_image,
90                                      const std::string& old_kernel_part,
91                                      const std::string& new_kernel_part,
92                                      const std::string& output_path,
93                                      const std::string& private_key_path,
94                                      off_t chunk_size,
95                                      size_t rootfs_partition_size,
96                                      uint32_t minor_version,
97                                      const ImageInfo* old_image_info,
98                                      const ImageInfo* new_image_info,
99                                      uint64_t* metadata_size);
100
101  // These functions are public so that the unit tests can access them:
102
103  // For a given regular file which must exist at new_root + path, and
104  // may exist at old_root + path, creates a new InstallOperation and
105  // adds it to the graph. Also, populates the |blocks| array as
106  // necessary, if |blocks| is non-null.  Also, writes the data
107  // necessary to send the file down to the client into data_fd, which
108  // has length *data_file_size. *data_file_size is updated
109  // appropriately. If |existing_vertex| is no kInvalidIndex, use that
110  // rather than allocating a new vertex. Returns true on success.
111  static bool DeltaReadFile(Graph* graph,
112                            Vertex::Index existing_vertex,
113                            std::vector<Block>* blocks,
114                            const std::string& old_root,
115                            const std::string& new_root,
116                            const std::string& path,
117                            off_t chunk_offset,
118                            off_t chunk_size,
119                            int data_fd,
120                            off_t* data_file_size,
121                            bool src_ops_allowed);
122
123  // Reads old_filename (if it exists) and a new_filename and determines
124  // the smallest way to encode this file for the diff. It stores
125  // necessary data in out_data and fills in out_op.
126  // If there's no change in old and new files, it creates a MOVE
127  // operation. If there is a change, or the old file doesn't exist,
128  // the smallest of REPLACE, REPLACE_BZ, or BSDIFF wins.
129  // new_filename must contain at least one byte.
130  // |new_filename| is read starting at |chunk_offset|.
131  // If |chunk_size| is not -1, only up to |chunk_size| bytes are diffed.
132  // If |src_ops_allowed| is true, it will emit SOURCE_COPY and SOURCE_BSDIFF
133  // operations instead of MOVE and BSDIFF, respectively.
134  // Returns true on success.
135  static bool ReadFileToDiff(const std::string& old_filename,
136                             const std::string& new_filename,
137                             off_t chunk_offset,
138                             off_t chunk_size,
139                             bool bsdiff_allowed,
140                             chromeos::Blob* out_data,
141                             DeltaArchiveManifest_InstallOperation* out_op,
142                             bool gather_extents,
143                             bool src_ops_allowed);
144
145  // Stores all Extents in 'extents' into 'out'.
146  static void StoreExtents(const std::vector<Extent>& extents,
147                           google::protobuf::RepeatedPtrField<Extent>* out);
148
149  // Install operations in the manifest may reference data blobs, which
150  // are in data_blobs_path. This function creates a new data blobs file
151  // with the data blobs in the same order as the referencing install
152  // operations in the manifest. E.g. if manifest[0] has a data blob
153  // "X" at offset 1, manifest[1] has a data blob "Y" at offset 0,
154  // and data_blobs_path's file contains "YX", new_data_blobs_path
155  // will set to be a file that contains "XY".
156  static bool ReorderDataBlobs(DeltaArchiveManifest* manifest,
157                               const std::string& data_blobs_path,
158                               const std::string& new_data_blobs_path);
159
160  // Computes a SHA256 hash of the given buf and sets the hash value in the
161  // operation so that update_engine could verify. This hash should be set
162  // for all operations that have a non-zero data blob. One exception is the
163  // dummy operation for signature blob because the contents of the signature
164  // blob will not be available at payload creation time. So, update_engine will
165  // gracefully ignore the dummy signature operation.
166  static bool AddOperationHash(DeltaArchiveManifest_InstallOperation* op,
167                               const chromeos::Blob& buf);
168
169
170  // Returns true if |op| is a no-op operation that doesn't do any useful work
171  // (e.g., a move operation that copies blocks onto themselves).
172  static bool IsNoopOperation(const DeltaArchiveManifest_InstallOperation& op);
173
174  static bool InitializePartitionInfo(bool is_kernel,
175                                      const std::string& partition,
176                                      PartitionInfo* info);
177
178  // Runs the bsdiff tool on two files and returns the resulting delta in
179  // |out|. Returns true on success.
180  static bool BsdiffFiles(const std::string& old_file,
181                          const std::string& new_file,
182                          chromeos::Blob* out);
183
184  // Adds to |manifest| a dummy operation that points to a signature blob
185  // located at the specified offset/length.
186  static void AddSignatureOp(uint64_t signature_blob_offset,
187                             uint64_t signature_blob_length,
188                             DeltaArchiveManifest* manifest);
189
190  // Takes |graph| and returns a vertex order with the vertex indices of
191  // |graph|, in the order they appear. Returns |true| on success.
192  static std::vector<Vertex::Index> OrderIndices(const Graph& graph);
193
194  // Takes a collection (vector or RepeatedPtrField) of Extent and
195  // returns a vector of the blocks referenced, in order.
196  template<typename T>
197  static std::vector<uint64_t> ExpandExtents(const T& extents) {
198    std::vector<uint64_t> ret;
199    for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) {
200      const Extent extent = graph_utils::GetElement(extents, i);
201      if (extent.start_block() == kSparseHole) {
202        ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
203      } else {
204        for (uint64_t block = extent.start_block();
205             block < (extent.start_block() + extent.num_blocks()); block++) {
206          ret.push_back(block);
207        }
208      }
209    }
210    return ret;
211  }
212
213  static void CheckGraph(const Graph& graph);
214
215 private:
216  // This should never be constructed.
217  DISALLOW_IMPLICIT_CONSTRUCTORS(DeltaDiffGenerator);
218};
219
220};  // namespace chromeos_update_engine
221
222#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
223