Alex Deymo | aea4c1c | 2015-08-19 20:24:43 -0700 | [diff] [blame] | 1 | // |
| 2 | // Copyright (C) 2015 The Android Open Source Project |
| 3 | // |
| 4 | // Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | // you may not use this file except in compliance with the License. |
| 6 | // You may obtain a copy of the License at |
| 7 | // |
| 8 | // http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | // |
| 10 | // Unless required by applicable law or agreed to in writing, software |
| 11 | // distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | // See the License for the specific language governing permissions and |
| 14 | // limitations under the License. |
| 15 | // |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 16 | |
| 17 | #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_ |
| 18 | #define UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_ |
| 19 | |
Alex Deymo | 1415857 | 2015-06-13 03:37:08 -0700 | [diff] [blame] | 20 | #include <map> |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 21 | #include <set> |
| 22 | #include <string> |
| 23 | #include <vector> |
| 24 | |
Sen Jiang | 8cc502d | 2015-08-10 10:04:54 -0700 | [diff] [blame] | 25 | #include "update_engine/payload_generator/blob_file_writer.h" |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 26 | #include "update_engine/payload_generator/delta_diff_generator.h" |
| 27 | #include "update_engine/payload_generator/graph_types.h" |
Alex Deymo | 477aec2 | 2015-03-24 23:40:48 -0700 | [diff] [blame] | 28 | #include "update_engine/payload_generator/operations_generator.h" |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 29 | |
| 30 | // InplaceGenerator contains all functionality related to the inplace algorithm |
| 31 | // for generating update payloads. These are the functions used when delta minor |
| 32 | // version is 1. |
| 33 | |
| 34 | namespace chromeos_update_engine { |
| 35 | |
Alex Deymo | f1cbe17 | 2015-03-05 15:58:37 -0800 | [diff] [blame] | 36 | // This struct stores all relevant info for an edge that is cut between |
| 37 | // nodes old_src -> old_dst by creating new vertex new_vertex. The new |
| 38 | // relationship is: |
| 39 | // old_src -(read before)-> new_vertex <-(write before)- old_dst |
| 40 | // new_vertex is a MOVE operation that moves some existing blocks into |
| 41 | // temp space. The temp extents are, by necessity, stored in new_vertex |
| 42 | // (as dst extents) and old_dst (as src extents), but they are also broken |
| 43 | // out into tmp_extents, as the nodes themselves may contain many more |
| 44 | // extents. |
| 45 | struct CutEdgeVertexes { |
| 46 | Vertex::Index new_vertex; |
| 47 | Vertex::Index old_src; |
| 48 | Vertex::Index old_dst; |
| 49 | std::vector<Extent> tmp_extents; |
| 50 | }; |
| 51 | |
Alex Deymo | 477aec2 | 2015-03-24 23:40:48 -0700 | [diff] [blame] | 52 | class InplaceGenerator : public OperationsGenerator { |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 53 | public: |
Alex Deymo | 6b9e38e | 2015-06-05 00:26:37 +0200 | [diff] [blame] | 54 | // Represents a disk block on the install partition. |
| 55 | struct Block { |
| 56 | // During install, each block on the install partition will be written |
| 57 | // and some may be read (in all likelihood, many will be read). |
| 58 | // The reading and writing will be performed by InstallOperations, |
| 59 | // each of which has a corresponding vertex in a graph. |
| 60 | // A Block object tells which vertex will read or write this block |
| 61 | // at install time. |
| 62 | // Generally, there will be a vector of Block objects whose length |
| 63 | // is the number of blocks on the install partition. |
| 64 | Block() : reader(Vertex::kInvalidIndex), writer(Vertex::kInvalidIndex) {} |
| 65 | Vertex::Index reader; |
| 66 | Vertex::Index writer; |
| 67 | }; |
| 68 | |
Alex Deymo | 477aec2 | 2015-03-24 23:40:48 -0700 | [diff] [blame] | 69 | InplaceGenerator() = default; |
| 70 | |
| 71 | // Checks all the operations in the graph have a type assigned. |
| 72 | static void CheckGraph(const Graph& graph); |
| 73 | |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 74 | // Modifies blocks read by 'op' so that any blocks referred to by |
| 75 | // 'remove_extents' are replaced with blocks from 'replace_extents'. |
| 76 | // 'remove_extents' and 'replace_extents' must be the same number of blocks. |
| 77 | // Blocks will be substituted in the order listed in the vectors. |
| 78 | // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents |
| 79 | // contains blocks 6, 2, 3, 5, and replace blocks contains |
| 80 | // 12, 13, 14, 15, then op will be changed to read from: |
| 81 | // 1, 13, 14, 4, 15, 12, 7, 8 |
| 82 | static void SubstituteBlocks(Vertex* vertex, |
| 83 | const std::vector<Extent>& remove_extents, |
| 84 | const std::vector<Extent>& replace_extents); |
| 85 | |
| 86 | // Cuts 'edges' from 'graph' according to the AU algorithm. This means |
| 87 | // for each edge A->B, remove the dependency that B occur before A. |
| 88 | // Do this by creating a new operation X that copies from the blocks |
| 89 | // specified by the edge's properties to temp space T. Modify B to read |
| 90 | // from T rather than the blocks in the edge. Modify A to depend on X, |
| 91 | // but not on B. Free space is found by looking in 'blocks'. |
| 92 | // Returns true on success. |
| 93 | static bool CutEdges(Graph* graph, |
| 94 | const std::set<Edge>& edges, |
| 95 | std::vector<CutEdgeVertexes>* out_cuts); |
| 96 | |
| 97 | // Creates all the edges for the graph. Writers of a block point to |
| 98 | // readers of the same block. This is because for an edge A->B, B |
| 99 | // must complete before A executes. |
Amin Hassani | 232f8f9 | 2019-01-14 16:15:31 -0800 | [diff] [blame] | 100 | static void CreateEdges(Graph* graph, const std::vector<Block>& blocks); |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 101 | |
| 102 | // Takes |op_indexes|, which is effectively a mapping from order in |
| 103 | // which the op is performed -> graph vertex index, and produces the |
| 104 | // reverse: a mapping from graph vertex index -> op_indexes index. |
| 105 | static void GenerateReverseTopoOrderMap( |
| 106 | const std::vector<Vertex::Index>& op_indexes, |
| 107 | std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes); |
| 108 | |
| 109 | // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is |
| 110 | // determined by the order of elements in op_indexes. |
Amin Hassani | 232f8f9 | 2019-01-14 16:15:31 -0800 | [diff] [blame] | 111 | static void SortCutsByTopoOrder(const std::vector<Vertex::Index>& op_indexes, |
| 112 | std::vector<CutEdgeVertexes>* cuts); |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 113 | |
| 114 | // Given a topologically sorted graph |op_indexes| and |graph|, alters |
| 115 | // |op_indexes| to move all the full operations to the end of the vector. |
| 116 | // Full operations should not be depended on, so this is safe. |
Alex Deymo | 3b2c7d0 | 2015-07-16 16:08:16 -0700 | [diff] [blame] | 117 | static void MoveAndSortFullOpsToBack(Graph* graph, |
Amin Hassani | 232f8f9 | 2019-01-14 16:15:31 -0800 | [diff] [blame] | 118 | std::vector<Vertex::Index>* op_indexes); |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 119 | |
| 120 | // Returns true iff there are no extents in the graph that refer to temp |
| 121 | // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole). |
| 122 | static bool NoTempBlocksRemain(const Graph& graph); |
| 123 | |
| 124 | // Takes a |graph|, which has edges that must be cut, as listed in |
| 125 | // |cuts|. Cuts the edges. Maintains a list in which the operations |
| 126 | // will be performed (in |op_indexes|) and the reverse (in |
| 127 | // |reverse_op_indexes|). Cutting edges requires scratch space, and |
| 128 | // if insufficient scratch is found, the file is reread and will be |
| 129 | // send down (either as REPLACE or REPLACE_BZ). Returns true on |
| 130 | // success. |
| 131 | static bool AssignTempBlocks( |
| 132 | Graph* graph, |
Allie Wood | 5687345 | 2015-03-27 17:48:40 -0700 | [diff] [blame] | 133 | const std::string& new_part, |
Sen Jiang | 8cc502d | 2015-08-10 10:04:54 -0700 | [diff] [blame] | 134 | BlobFileWriter* blob_file, |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 135 | std::vector<Vertex::Index>* op_indexes, |
| 136 | std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes, |
| 137 | const std::vector<CutEdgeVertexes>& cuts); |
| 138 | |
| 139 | // Handles allocation of temp blocks to a cut edge by converting the |
| 140 | // dest node to a full op. This removes the need for temp blocks, but |
| 141 | // comes at the cost of a worse compression ratio. |
| 142 | // For example, say we have A->B->A. It would first be cut to form: |
| 143 | // A->B->N<-A, where N copies blocks to temp space. If there are no |
| 144 | // temp blocks, this function can be called to convert it to the form: |
| 145 | // A->B. Now, A is a full operation. |
| 146 | static bool ConvertCutToFullOp(Graph* graph, |
| 147 | const CutEdgeVertexes& cut, |
Allie Wood | 5687345 | 2015-03-27 17:48:40 -0700 | [diff] [blame] | 148 | const std::string& new_part, |
Sen Jiang | 8cc502d | 2015-08-10 10:04:54 -0700 | [diff] [blame] | 149 | BlobFileWriter* blob_file); |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 150 | |
| 151 | // Takes a graph, which is not a DAG, which represents the files just |
| 152 | // read from disk, and converts it into a DAG by breaking all cycles |
| 153 | // and finding temp space to resolve broken edges. |
| 154 | // The final order of the nodes is given in |final_order| |
| 155 | // Some files may need to be reread from disk, thus |fd| and |
| 156 | // |data_file_size| are be passed. |
| 157 | // If |scratch_vertex| is not kInvalidIndex, removes it from |
| 158 | // |final_order| before returning. |
| 159 | // Returns true on success. |
| 160 | static bool ConvertGraphToDag(Graph* graph, |
Allie Wood | 5687345 | 2015-03-27 17:48:40 -0700 | [diff] [blame] | 161 | const std::string& new_part, |
Sen Jiang | 8cc502d | 2015-08-10 10:04:54 -0700 | [diff] [blame] | 162 | BlobFileWriter* blob_file, |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 163 | std::vector<Vertex::Index>* final_order, |
| 164 | Vertex::Index scratch_vertex); |
| 165 | |
| 166 | // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used |
| 167 | // to provide scratch space. The node writes |num_blocks| blocks starting at |
| 168 | // |start_block|The node should be marked invalid before writing all nodes to |
| 169 | // the output file. |
| 170 | static void CreateScratchNode(uint64_t start_block, |
| 171 | uint64_t num_blocks, |
| 172 | Vertex* vertex); |
| 173 | |
| 174 | // The |blocks| vector contains a reader and writer for each block on the |
| 175 | // filesystem that's being in-place updated. We populate the reader/writer |
| 176 | // fields of |blocks| by calling this function. |
| 177 | // For each block in |operation| that is read or written, find that block |
| 178 | // in |blocks| and set the reader/writer field to the vertex passed. |
| 179 | // |graph| is not strictly necessary, but useful for printing out |
| 180 | // error messages. |
Alex Deymo | a12ee11 | 2015-08-12 22:19:32 -0700 | [diff] [blame] | 181 | static bool AddInstallOpToBlocksVector(const InstallOperation& operation, |
| 182 | const Graph& graph, |
| 183 | Vertex::Index vertex, |
| 184 | std::vector<Block>* blocks); |
Alex Deymo | 6b9e38e | 2015-06-05 00:26:37 +0200 | [diff] [blame] | 185 | |
| 186 | // Add a vertex (if |existing_vertex| is kInvalidVertex) or update an |
| 187 | // |existing_vertex| with the passed |operation|. |
| 188 | // This method will also register the vertex as the reader or writer of the |
| 189 | // blocks involved in the operation updating the |blocks| vector. The |
| 190 | // |op_name| associated with the Vertex is used for logging purposes. |
Alex Deymo | a12ee11 | 2015-08-12 22:19:32 -0700 | [diff] [blame] | 191 | static bool AddInstallOpToGraph(Graph* graph, |
| 192 | Vertex::Index existing_vertex, |
| 193 | std::vector<Block>* blocks, |
Chih-Hung Hsieh | 5c6bb1d | 2016-07-27 13:33:15 -0700 | [diff] [blame] | 194 | const InstallOperation& operation, |
Alex Deymo | a12ee11 | 2015-08-12 22:19:32 -0700 | [diff] [blame] | 195 | const std::string& op_name); |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 196 | |
Alex Deymo | 1415857 | 2015-06-13 03:37:08 -0700 | [diff] [blame] | 197 | // Apply the transformation stored in |the_map| to the |collection| vector |
| 198 | // replacing the map keys found in |collection| with its associated value in |
| 199 | // |the_map|. |
| 200 | static void ApplyMap(std::vector<uint64_t>* collection, |
| 201 | const std::map<uint64_t, uint64_t>& the_map); |
| 202 | |
Alex Deymo | f616535 | 2015-07-16 15:15:57 -0700 | [diff] [blame] | 203 | // Resolve all read-after-write dependencies in the operation list |aops|. The |
| 204 | // operations in |aops| are such that they generate the desired |new_part| if |
| 205 | // applied reading always from the original image. This function reorders the |
| 206 | // operations and generates new operations when needed to make these |
| 207 | // operations produce the same |new_part| result when applied in-place. |
| 208 | // The new operations will create blobs in |data_file_fd| and update |
| 209 | // the file size pointed by |data_file_size| if needed. |
| 210 | // On success, stores the new operations in |aops| in the right order and |
| 211 | // returns true. |
| 212 | static bool ResolveReadAfterWriteDependencies( |
Alex Deymo | 05871fa | 2016-06-01 01:32:58 -0700 | [diff] [blame] | 213 | const PartitionConfig& old_part, |
Alex Deymo | f616535 | 2015-07-16 15:15:57 -0700 | [diff] [blame] | 214 | const PartitionConfig& new_part, |
| 215 | uint64_t partition_size, |
| 216 | size_t block_size, |
Sen Jiang | 8cc502d | 2015-08-10 10:04:54 -0700 | [diff] [blame] | 217 | BlobFileWriter* blob_file, |
Alex Deymo | f616535 | 2015-07-16 15:15:57 -0700 | [diff] [blame] | 218 | std::vector<AnnotatedOperation>* aops); |
| 219 | |
Sen Jiang | ebdf17d | 2015-08-19 11:53:27 -0700 | [diff] [blame] | 220 | // Generate the update payload operations for the given partition using |
Alex Deymo | 9b244df | 2015-03-11 21:51:18 -0700 | [diff] [blame] | 221 | // only operations that read from the target and/or write to the target, |
| 222 | // hence, applying the payload "in-place" in the target partition. This method |
| 223 | // assumes that the contents of the source image are pre-copied to the target |
| 224 | // partition, up to the size of the source image. Use this method to generate |
| 225 | // a delta update with the minor version kInPlaceMinorPayloadVersion. |
Sen Jiang | ebdf17d | 2015-08-19 11:53:27 -0700 | [diff] [blame] | 226 | // The operations are stored in |aops|. All the offsets in the operations |
| 227 | // reference the data written to |blob_file|. |
Amin Hassani | 232f8f9 | 2019-01-14 16:15:31 -0800 | [diff] [blame] | 228 | bool GenerateOperations(const PayloadGenerationConfig& config, |
| 229 | const PartitionConfig& old_part, |
| 230 | const PartitionConfig& new_part, |
| 231 | BlobFileWriter* blob_file, |
| 232 | std::vector<AnnotatedOperation>* aops) override; |
Alex Deymo | 9b244df | 2015-03-11 21:51:18 -0700 | [diff] [blame] | 233 | |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 234 | private: |
Alex Deymo | 477aec2 | 2015-03-24 23:40:48 -0700 | [diff] [blame] | 235 | DISALLOW_COPY_AND_ASSIGN(InplaceGenerator); |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 236 | }; |
| 237 | |
| 238 | }; // namespace chromeos_update_engine |
| 239 | |
| 240 | #endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_ |