inplace_generator.h 12 KB

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