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