OLD | NEW |
1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_DELTA_DIFF_GENERATOR_H__ | 5 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_DELTA_DIFF_GENERATOR_H__ |
6 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_DELTA_DIFF_GENERATOR_H__ | 6 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_DELTA_DIFF_GENERATOR_H__ |
7 | 7 |
8 #include <string> | 8 #include <string> |
9 #include <vector> | 9 #include <vector> |
10 #include "base/basictypes.h" | 10 #include "base/basictypes.h" |
11 #include "update_engine/graph_types.h" | 11 #include "update_engine/graph_types.h" |
12 #include "update_engine/update_metadata.pb.h" | 12 #include "update_engine/update_metadata.pb.h" |
13 | 13 |
14 // There is one function in DeltaDiffGenerator of importance to users | 14 // There is one function in DeltaDiffGenerator of importance to users |
15 // of the class: GenerateDeltaUpdateFile(). Before calling it, | 15 // of the class: GenerateDeltaUpdateFile(). Before calling it, |
16 // the old and new images must be mounted. Call GenerateDeltaUpdateFile() | 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 | 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 | 18 // the images (both old and new). A delta from old to new will be |
19 // generated and stored in output_path. | 19 // generated and stored in output_path. |
20 | 20 |
21 namespace chromeos_update_engine { | 21 namespace chromeos_update_engine { |
22 | 22 |
| 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 |
23 class DeltaDiffGenerator { | 39 class DeltaDiffGenerator { |
24 public: | 40 public: |
25 // Represents a disk block on the install partition. | 41 // Represents a disk block on the install partition. |
26 struct Block { | 42 struct Block { |
27 // During install, each block on the install partition will be written | 43 // During install, each block on the install partition will be written |
28 // and some may be read (in all likelihood, many will be read). | 44 // and some may be read (in all likelihood, many will be read). |
29 // The reading and writing will be performed by InstallOperations, | 45 // The reading and writing will be performed by InstallOperations, |
30 // each of which has a corresponding vertex in a graph. | 46 // each of which has a corresponding vertex in a graph. |
31 // A Block object tells which vertex will read or write this block | 47 // A Block object tells which vertex will read or write this block |
32 // at install time. | 48 // at install time. |
(...skipping 17 matching lines...) Expand all Loading... |
50 const std::string& old_image, | 66 const std::string& old_image, |
51 const std::string& new_root, | 67 const std::string& new_root, |
52 const std::string& new_image, | 68 const std::string& new_image, |
53 const std::string& old_kernel_part, | 69 const std::string& old_kernel_part, |
54 const std::string& new_kernel_part, | 70 const std::string& new_kernel_part, |
55 const std::string& output_path, | 71 const std::string& output_path, |
56 const std::string& private_key_path); | 72 const std::string& private_key_path); |
57 | 73 |
58 // These functions are public so that the unit tests can access them: | 74 // These functions are public so that the unit tests can access them: |
59 | 75 |
| 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. |
| 82 // Returns true on success. |
| 83 static bool ConvertGraphToDag(Graph* graph, |
| 84 const std::string& new_root, |
| 85 int fd, |
| 86 off_t* data_file_size, |
| 87 std::vector<Vertex::Index>* final_order); |
| 88 |
60 // Reads old_filename (if it exists) and a new_filename and determines | 89 // Reads old_filename (if it exists) and a new_filename and determines |
61 // the smallest way to encode this file for the diff. It stores | 90 // the smallest way to encode this file for the diff. It stores |
62 // necessary data in out_data and fills in out_op. | 91 // necessary data in out_data and fills in out_op. |
63 // If there's no change in old and new files, it creates a MOVE | 92 // If there's no change in old and new files, it creates a MOVE |
64 // operation. If there is a change, or the old file doesn't exist, | 93 // operation. If there is a change, or the old file doesn't exist, |
65 // the smallest of REPLACE, REPLACE_BZ, or BSDIFF wins. | 94 // the smallest of REPLACE, REPLACE_BZ, or BSDIFF wins. |
66 // new_filename must contain at least one byte. | 95 // new_filename must contain at least one byte. |
67 // Returns true on success. | 96 // Returns true on success. |
68 static bool ReadFileToDiff(const std::string& old_filename, | 97 static bool ReadFileToDiff(const std::string& old_filename, |
69 const std::string& new_filename, | 98 const std::string& new_filename, |
70 std::vector<char>* out_data, | 99 std::vector<char>* out_data, |
71 DeltaArchiveManifest_InstallOperation* out_op); | 100 DeltaArchiveManifest_InstallOperation* out_op); |
72 | 101 |
73 // Modifies blocks read by 'op' so that any blocks referred to by | 102 // Modifies blocks read by 'op' so that any blocks referred to by |
74 // 'remove_extents' are replaced with blocks from 'replace_extents'. | 103 // 'remove_extents' are replaced with blocks from 'replace_extents'. |
75 // 'remove_extents' and 'replace_extents' must be the same number of blocks. | 104 // 'remove_extents' and 'replace_extents' must be the same number of blocks. |
76 // Blocks will be substituted in the order listed in the vectors. | 105 // Blocks will be substituted in the order listed in the vectors. |
77 // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents | 106 // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents |
78 // contains blocks 6, 2, 3, 5, and replace blocks contains | 107 // contains blocks 6, 2, 3, 5, and replace blocks contains |
79 // 12, 13, 14, 15, then op will be changed to read from: | 108 // 12, 13, 14, 15, then op will be changed to read from: |
80 // 1, 13, 14, 4, 15, 12, 7, 8 | 109 // 1, 13, 14, 4, 15, 12, 7, 8 |
81 static void SubstituteBlocks(DeltaArchiveManifest_InstallOperation* op, | 110 static void SubstituteBlocks(Vertex* vertex, |
82 const std::vector<Extent>& remove_extents, | 111 const std::vector<Extent>& remove_extents, |
83 const std::vector<Extent>& replace_extents); | 112 const std::vector<Extent>& replace_extents); |
84 | 113 |
85 // Cuts 'edges' from 'graph' according to the AU algorithm. This means | 114 // Cuts 'edges' from 'graph' according to the AU algorithm. This means |
86 // for each edge A->B, remove the dependency that B occur before A. | 115 // for each edge A->B, remove the dependency that B occur before A. |
87 // Do this by creating a new operation X that copies from the blocks | 116 // Do this by creating a new operation X that copies from the blocks |
88 // specified by the edge's properties to temp space T. Modify B to read | 117 // specified by the edge's properties to temp space T. Modify B to read |
89 // from T rather than the blocks in the edge. Modify A to depend on X, | 118 // from T rather than the blocks in the edge. Modify A to depend on X, |
90 // but not on B. Free space is found by looking in 'blocks'. | 119 // but not on B. Free space is found by looking in 'blocks'. |
91 // Returns true on success. | 120 // Returns true on success. |
92 static bool CutEdges(Graph* graph, | 121 static bool CutEdges(Graph* graph, |
93 const std::vector<Block>& blocks, | 122 const std::set<Edge>& edges, |
94 const std::set<Edge>& edges); | 123 std::vector<CutEdgeVertexes>* out_cuts); |
95 | 124 |
96 // Stores all Extents in 'extents' into 'out'. | 125 // Stores all Extents in 'extents' into 'out'. |
97 static void StoreExtents(std::vector<Extent>& extents, | 126 static void StoreExtents(const std::vector<Extent>& extents, |
98 google::protobuf::RepeatedPtrField<Extent>* out); | 127 google::protobuf::RepeatedPtrField<Extent>* out); |
99 | 128 |
100 // Creates all the edges for the graph. Writers of a block point to | 129 // Creates all the edges for the graph. Writers of a block point to |
101 // readers of the same block. This is because for an edge A->B, B | 130 // readers of the same block. This is because for an edge A->B, B |
102 // must complete before A executes. | 131 // must complete before A executes. |
103 static void CreateEdges(Graph* graph, const std::vector<Block>& blocks); | 132 static void CreateEdges(Graph* graph, const std::vector<Block>& blocks); |
| 133 |
| 134 // Given a topologically sorted graph |op_indexes| and |graph|, alters |
| 135 // |op_indexes| to move all the full operations to the end of the vector. |
| 136 // Full operations should not be depended on, so this is safe. |
| 137 static void MoveFullOpsToBack(Graph* graph, |
| 138 std::vector<Vertex::Index>* op_indexes); |
| 139 |
| 140 // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is |
| 141 // determined by the order of elements in op_indexes. |
| 142 static void SortCutsByTopoOrder(std::vector<Vertex::Index>& op_indexes, |
| 143 std::vector<CutEdgeVertexes>* cuts); |
| 144 |
| 145 // Returns true iff there are no extents in the graph that refer to temp |
| 146 // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole). |
| 147 static bool NoTempBlocksRemain(const Graph& graph); |
104 | 148 |
105 // Install operations in the manifest may reference data blobs, which | 149 // Install operations in the manifest may reference data blobs, which |
106 // are in data_blobs_path. This function creates a new data blobs file | 150 // are in data_blobs_path. This function creates a new data blobs file |
107 // with the data blobs in the same order as the referencing install | 151 // with the data blobs in the same order as the referencing install |
108 // operations in the manifest. E.g. if manifest[0] has a data blob | 152 // operations in the manifest. E.g. if manifest[0] has a data blob |
109 // "X" at offset 1, manifest[1] has a data blob "Y" at offset 0, | 153 // "X" at offset 1, manifest[1] has a data blob "Y" at offset 0, |
110 // and data_blobs_path's file contains "YX", new_data_blobs_path | 154 // and data_blobs_path's file contains "YX", new_data_blobs_path |
111 // will set to be a file that contains "XY". | 155 // will set to be a file that contains "XY". |
112 static bool ReorderDataBlobs(DeltaArchiveManifest* manifest, | 156 static bool ReorderDataBlobs(DeltaArchiveManifest* manifest, |
113 const std::string& data_blobs_path, | 157 const std::string& data_blobs_path, |
114 const std::string& new_data_blobs_path); | 158 const std::string& new_data_blobs_path); |
| 159 |
| 160 // Handles allocation of temp blocks to a cut edge by converting the |
| 161 // dest node to a full op. This removes the need for temp blocks, but |
| 162 // comes at the cost of a worse compression ratio. |
| 163 // For example, say we have A->B->A. It would first be cut to form: |
| 164 // A->B->N<-A, where N copies blocks to temp space. If there are no |
| 165 // temp blocks, this function can be called to convert it to the form: |
| 166 // A->B. Now, A is a full operation. |
| 167 static bool ConvertCutToFullOp(Graph* graph, |
| 168 const CutEdgeVertexes& cut, |
| 169 const std::string& new_root, |
| 170 int data_fd, |
| 171 off_t* data_file_size); |
| 172 |
| 173 // Takes |op_indexes|, which is effectively a mapping from order in |
| 174 // which the op is performed -> graph vertex index, and produces the |
| 175 // reverse: a mapping from graph vertex index -> op_indexes index. |
| 176 static void GenerateReverseTopoOrderMap( |
| 177 std::vector<Vertex::Index>& op_indexes, |
| 178 std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes); |
| 179 |
| 180 // Takes a |graph|, which has edges that must be cut, as listed in |
| 181 // |cuts|. Cuts the edges. Maintains a list in which the operations |
| 182 // will be performed (in |op_indexes|) and the reverse (in |
| 183 // |reverse_op_indexes|). Cutting edges requires scratch space, and |
| 184 // if insufficient scratch is found, the file is reread and will be |
| 185 // send down (either as REPLACE or REPLACE_BZ). Returns true on |
| 186 // success. |
| 187 static bool AssignTempBlocks( |
| 188 Graph* graph, |
| 189 const std::string& new_root, |
| 190 int data_fd, |
| 191 off_t* data_file_size, |
| 192 std::vector<Vertex::Index>* op_indexes, |
| 193 std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes, |
| 194 std::vector<CutEdgeVertexes>& cuts); |
115 | 195 |
116 private: | 196 private: |
117 // This should never be constructed | 197 // This should never be constructed |
118 DISALLOW_IMPLICIT_CONSTRUCTORS(DeltaDiffGenerator); | 198 DISALLOW_IMPLICIT_CONSTRUCTORS(DeltaDiffGenerator); |
119 }; | 199 }; |
120 | 200 |
121 extern const char* const kBsdiffPath; | 201 extern const char* const kBsdiffPath; |
122 extern const char* const kBspatchPath; | 202 extern const char* const kBspatchPath; |
123 extern const char* const kDeltaMagic; | 203 extern const char* const kDeltaMagic; |
124 | 204 |
125 }; // namespace chromeos_update_engine | 205 }; // namespace chromeos_update_engine |
126 | 206 |
127 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_DELTA_DIFF_GENERATOR_H__ | 207 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_DELTA_DIFF_GENERATOR_H__ |
OLD | NEW |