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