Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 1 | // Copyright 2015 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_INPLACE_GENERATOR_H_ |
| 6 | #define UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_ |
| 7 | |
| 8 | #include <set> |
| 9 | #include <string> |
| 10 | #include <vector> |
| 11 | |
| 12 | #include "update_engine/payload_generator/delta_diff_generator.h" |
| 13 | #include "update_engine/payload_generator/graph_types.h" |
| 14 | |
| 15 | // InplaceGenerator contains all functionality related to the inplace algorithm |
| 16 | // for generating update payloads. These are the functions used when delta minor |
| 17 | // version is 1. |
| 18 | |
| 19 | namespace chromeos_update_engine { |
| 20 | |
Alex Deymo | f1cbe17 | 2015-03-05 15:58:37 -0800 | [diff] [blame^] | 21 | // This struct stores all relevant info for an edge that is cut between |
| 22 | // nodes old_src -> old_dst by creating new vertex new_vertex. The new |
| 23 | // relationship is: |
| 24 | // old_src -(read before)-> new_vertex <-(write before)- old_dst |
| 25 | // new_vertex is a MOVE operation that moves some existing blocks into |
| 26 | // temp space. The temp extents are, by necessity, stored in new_vertex |
| 27 | // (as dst extents) and old_dst (as src extents), but they are also broken |
| 28 | // out into tmp_extents, as the nodes themselves may contain many more |
| 29 | // extents. |
| 30 | struct CutEdgeVertexes { |
| 31 | Vertex::Index new_vertex; |
| 32 | Vertex::Index old_src; |
| 33 | Vertex::Index old_dst; |
| 34 | std::vector<Extent> tmp_extents; |
| 35 | }; |
| 36 | |
Allie Wood | cd514b5 | 2015-02-19 13:56:07 -0800 | [diff] [blame] | 37 | class InplaceGenerator { |
| 38 | public: |
| 39 | // Modifies blocks read by 'op' so that any blocks referred to by |
| 40 | // 'remove_extents' are replaced with blocks from 'replace_extents'. |
| 41 | // 'remove_extents' and 'replace_extents' must be the same number of blocks. |
| 42 | // Blocks will be substituted in the order listed in the vectors. |
| 43 | // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents |
| 44 | // contains blocks 6, 2, 3, 5, and replace blocks contains |
| 45 | // 12, 13, 14, 15, then op will be changed to read from: |
| 46 | // 1, 13, 14, 4, 15, 12, 7, 8 |
| 47 | static void SubstituteBlocks(Vertex* vertex, |
| 48 | const std::vector<Extent>& remove_extents, |
| 49 | const std::vector<Extent>& replace_extents); |
| 50 | |
| 51 | // Cuts 'edges' from 'graph' according to the AU algorithm. This means |
| 52 | // for each edge A->B, remove the dependency that B occur before A. |
| 53 | // Do this by creating a new operation X that copies from the blocks |
| 54 | // specified by the edge's properties to temp space T. Modify B to read |
| 55 | // from T rather than the blocks in the edge. Modify A to depend on X, |
| 56 | // but not on B. Free space is found by looking in 'blocks'. |
| 57 | // Returns true on success. |
| 58 | static bool CutEdges(Graph* graph, |
| 59 | const std::set<Edge>& edges, |
| 60 | std::vector<CutEdgeVertexes>* out_cuts); |
| 61 | |
| 62 | // Creates all the edges for the graph. Writers of a block point to |
| 63 | // readers of the same block. This is because for an edge A->B, B |
| 64 | // must complete before A executes. |
| 65 | static void CreateEdges(Graph* graph, |
| 66 | const std::vector<DeltaDiffGenerator::Block>& blocks); |
| 67 | |
| 68 | // Takes |op_indexes|, which is effectively a mapping from order in |
| 69 | // which the op is performed -> graph vertex index, and produces the |
| 70 | // reverse: a mapping from graph vertex index -> op_indexes index. |
| 71 | static void GenerateReverseTopoOrderMap( |
| 72 | const std::vector<Vertex::Index>& op_indexes, |
| 73 | std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes); |
| 74 | |
| 75 | // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is |
| 76 | // determined by the order of elements in op_indexes. |
| 77 | static void SortCutsByTopoOrder( |
| 78 | const std::vector<Vertex::Index>& op_indexes, |
| 79 | std::vector<CutEdgeVertexes>* cuts); |
| 80 | |
| 81 | // Given a topologically sorted graph |op_indexes| and |graph|, alters |
| 82 | // |op_indexes| to move all the full operations to the end of the vector. |
| 83 | // Full operations should not be depended on, so this is safe. |
| 84 | static void MoveFullOpsToBack(Graph* graph, |
| 85 | std::vector<Vertex::Index>* op_indexes); |
| 86 | |
| 87 | // Returns true iff there are no extents in the graph that refer to temp |
| 88 | // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole). |
| 89 | static bool NoTempBlocksRemain(const Graph& graph); |
| 90 | |
| 91 | // Takes a |graph|, which has edges that must be cut, as listed in |
| 92 | // |cuts|. Cuts the edges. Maintains a list in which the operations |
| 93 | // will be performed (in |op_indexes|) and the reverse (in |
| 94 | // |reverse_op_indexes|). Cutting edges requires scratch space, and |
| 95 | // if insufficient scratch is found, the file is reread and will be |
| 96 | // send down (either as REPLACE or REPLACE_BZ). Returns true on |
| 97 | // success. |
| 98 | static bool AssignTempBlocks( |
| 99 | Graph* graph, |
| 100 | const std::string& new_root, |
| 101 | int data_fd, |
| 102 | off_t* data_file_size, |
| 103 | std::vector<Vertex::Index>* op_indexes, |
| 104 | std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes, |
| 105 | const std::vector<CutEdgeVertexes>& cuts); |
| 106 | |
| 107 | // Handles allocation of temp blocks to a cut edge by converting the |
| 108 | // dest node to a full op. This removes the need for temp blocks, but |
| 109 | // comes at the cost of a worse compression ratio. |
| 110 | // For example, say we have A->B->A. It would first be cut to form: |
| 111 | // A->B->N<-A, where N copies blocks to temp space. If there are no |
| 112 | // temp blocks, this function can be called to convert it to the form: |
| 113 | // A->B. Now, A is a full operation. |
| 114 | static bool ConvertCutToFullOp(Graph* graph, |
| 115 | const CutEdgeVertexes& cut, |
| 116 | const std::string& new_root, |
| 117 | int data_fd, |
| 118 | off_t* data_file_size); |
| 119 | |
| 120 | // Takes a graph, which is not a DAG, which represents the files just |
| 121 | // read from disk, and converts it into a DAG by breaking all cycles |
| 122 | // and finding temp space to resolve broken edges. |
| 123 | // The final order of the nodes is given in |final_order| |
| 124 | // Some files may need to be reread from disk, thus |fd| and |
| 125 | // |data_file_size| are be passed. |
| 126 | // If |scratch_vertex| is not kInvalidIndex, removes it from |
| 127 | // |final_order| before returning. |
| 128 | // Returns true on success. |
| 129 | static bool ConvertGraphToDag(Graph* graph, |
| 130 | const std::string& new_root, |
| 131 | int fd, |
| 132 | off_t* data_file_size, |
| 133 | std::vector<Vertex::Index>* final_order, |
| 134 | Vertex::Index scratch_vertex); |
| 135 | |
| 136 | // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used |
| 137 | // to provide scratch space. The node writes |num_blocks| blocks starting at |
| 138 | // |start_block|The node should be marked invalid before writing all nodes to |
| 139 | // the output file. |
| 140 | static void CreateScratchNode(uint64_t start_block, |
| 141 | uint64_t num_blocks, |
| 142 | Vertex* vertex); |
| 143 | |
| 144 | // The |blocks| vector contains a reader and writer for each block on the |
| 145 | // filesystem that's being in-place updated. We populate the reader/writer |
| 146 | // fields of |blocks| by calling this function. |
| 147 | // For each block in |operation| that is read or written, find that block |
| 148 | // in |blocks| and set the reader/writer field to the vertex passed. |
| 149 | // |graph| is not strictly necessary, but useful for printing out |
| 150 | // error messages. |
| 151 | static bool AddInstallOpToBlocksVector( |
| 152 | const DeltaArchiveManifest_InstallOperation& operation, |
| 153 | const Graph& graph, |
| 154 | Vertex::Index vertex, |
| 155 | std::vector<DeltaDiffGenerator::Block>* blocks); |
| 156 | |
| 157 | private: |
| 158 | // This should never be constructed. |
| 159 | DISALLOW_IMPLICIT_CONSTRUCTORS(InplaceGenerator); |
| 160 | }; |
| 161 | |
| 162 | }; // namespace chromeos_update_engine |
| 163 | |
| 164 | #endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_ |