inplace_generator.h revision 8e2c4ef89b1c2c8779d003b40c70c75db1839bfb 
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#include "update_engine/payload_generator/operations_generator.h"
15
16// InplaceGenerator contains all functionality related to the inplace algorithm
17// for generating update payloads. These are the functions used when delta minor
18// version is 1.
19
20namespace chromeos_update_engine {
21
22// This struct stores all relevant info for an edge that is cut between
23// nodes old_src -> old_dst by creating new vertex new_vertex. The new
24// relationship is:
25// old_src -(read before)-> new_vertex <-(write before)- old_dst
26// new_vertex is a MOVE operation that moves some existing blocks into
27// temp space. The temp extents are, by necessity, stored in new_vertex
28// (as dst extents) and old_dst (as src extents), but they are also broken
29// out into tmp_extents, as the nodes themselves may contain many more
30// extents.
31struct CutEdgeVertexes {
32  Vertex::Index new_vertex;
33  Vertex::Index old_src;
34  Vertex::Index old_dst;
35  std::vector<Extent> tmp_extents;
36};
37
38class InplaceGenerator : public OperationsGenerator {
39 public:
40  InplaceGenerator() = default;
41
42  // Checks all the operations in the graph have a type assigned.
43  static void CheckGraph(const Graph& graph);
44
45  // Modifies blocks read by 'op' so that any blocks referred to by
46  // 'remove_extents' are replaced with blocks from 'replace_extents'.
47  // 'remove_extents' and 'replace_extents' must be the same number of blocks.
48  // Blocks will be substituted in the order listed in the vectors.
49  // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents
50  // contains blocks 6, 2, 3, 5, and replace blocks contains
51  // 12, 13, 14, 15, then op will be changed to read from:
52  // 1, 13, 14, 4, 15, 12, 7, 8
53  static void SubstituteBlocks(Vertex* vertex,
54                               const std::vector<Extent>& remove_extents,
55                               const std::vector<Extent>& replace_extents);
56
57  // Cuts 'edges' from 'graph' according to the AU algorithm. This means
58  // for each edge A->B, remove the dependency that B occur before A.
59  // Do this by creating a new operation X that copies from the blocks
60  // specified by the edge's properties to temp space T. Modify B to read
61  // from T rather than the blocks in the edge. Modify A to depend on X,
62  // but not on B. Free space is found by looking in 'blocks'.
63  // Returns true on success.
64  static bool CutEdges(Graph* graph,
65                       const std::set<Edge>& edges,
66                       std::vector<CutEdgeVertexes>* out_cuts);
67
68  // Creates all the edges for the graph. Writers of a block point to
69  // readers of the same block. This is because for an edge A->B, B
70  // must complete before A executes.
71  static void CreateEdges(Graph* graph,
72                          const std::vector<DeltaDiffGenerator::Block>& blocks);
73
74  // Takes |op_indexes|, which is effectively a mapping from order in
75  // which the op is performed -> graph vertex index, and produces the
76  // reverse: a mapping from graph vertex index -> op_indexes index.
77  static void GenerateReverseTopoOrderMap(
78      const std::vector<Vertex::Index>& op_indexes,
79      std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes);
80
81  // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is
82  // determined by the order of elements in op_indexes.
83  static void SortCutsByTopoOrder(
84      const std::vector<Vertex::Index>& op_indexes,
85      std::vector<CutEdgeVertexes>* cuts);
86
87  // Given a topologically sorted graph |op_indexes| and |graph|, alters
88  // |op_indexes| to move all the full operations to the end of the vector.
89  // Full operations should not be depended on, so this is safe.
90  static void MoveFullOpsToBack(Graph* graph,
91                                std::vector<Vertex::Index>* op_indexes);
92
93  // Returns true iff there are no extents in the graph that refer to temp
94  // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole).
95  static bool NoTempBlocksRemain(const Graph& graph);
96
97  // Takes a |graph|, which has edges that must be cut, as listed in
98  // |cuts|.  Cuts the edges. Maintains a list in which the operations
99  // will be performed (in |op_indexes|) and the reverse (in
100  // |reverse_op_indexes|).  Cutting edges requires scratch space, and
101  // if insufficient scratch is found, the file is reread and will be
102  // send down (either as REPLACE or REPLACE_BZ).  Returns true on
103  // success.
104  static bool AssignTempBlocks(
105      Graph* graph,
106      const std::string& new_part,
107      const std::string& new_root,
108      int data_fd,
109      off_t* data_file_size,
110      std::vector<Vertex::Index>* op_indexes,
111      std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes,
112      const std::vector<CutEdgeVertexes>& cuts);
113
114  // Handles allocation of temp blocks to a cut edge by converting the
115  // dest node to a full op. This removes the need for temp blocks, but
116  // comes at the cost of a worse compression ratio.
117  // For example, say we have A->B->A. It would first be cut to form:
118  // A->B->N<-A, where N copies blocks to temp space. If there are no
119  // temp blocks, this function can be called to convert it to the form:
120  // A->B. Now, A is a full operation.
121  static bool ConvertCutToFullOp(Graph* graph,
122                                 const CutEdgeVertexes& cut,
123                                 const std::string& new_part,
124                                 const std::string& new_root,
125                                 int data_fd,
126                                 off_t* data_file_size);
127
128  // Takes a graph, which is not a DAG, which represents the files just
129  // read from disk, and converts it into a DAG by breaking all cycles
130  // and finding temp space to resolve broken edges.
131  // The final order of the nodes is given in |final_order|
132  // Some files may need to be reread from disk, thus |fd| and
133  // |data_file_size| are be passed.
134  // If |scratch_vertex| is not kInvalidIndex, removes it from
135  // |final_order| before returning.
136  // Returns true on success.
137  static bool ConvertGraphToDag(Graph* graph,
138                                const std::string& new_part,
139                                const std::string& new_root,
140                                int fd,
141                                off_t* data_file_size,
142                                std::vector<Vertex::Index>* final_order,
143                                Vertex::Index scratch_vertex);
144
145  // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used
146  // to provide scratch space. The node writes |num_blocks| blocks starting at
147  // |start_block|The node should be marked invalid before writing all nodes to
148  // the output file.
149  static void CreateScratchNode(uint64_t start_block,
150                                uint64_t num_blocks,
151                                Vertex* vertex);
152
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(
161      const DeltaArchiveManifest_InstallOperation& operation,
162      const Graph& graph,
163      Vertex::Index vertex,
164      std::vector<DeltaDiffGenerator::Block>* blocks);
165
166  // Generate the update payload operations for the kernel and rootfs using
167  // only operations that read from the target and/or write to the target,
168  // hence, applying the payload "in-place" in the target partition. This method
169  // assumes that the contents of the source image are pre-copied to the target
170  // partition, up to the size of the source image. Use this method to generate
171  // a delta update with the minor version kInPlaceMinorPayloadVersion.
172  // The rootfs operations are stored in |graph| and should be executed in the
173  // |final_order| order. The kernel operations are stored in |kernel_ops|. All
174  // the offsets in the operations reference the data written to |data_file_fd|.
175  // The total amount of data written to that file is stored in
176  // |data_file_size|.
177  bool GenerateOperations(
178      const PayloadGenerationConfig& config,
179      int data_file_fd,
180      off_t* data_file_size,
181      std::vector<AnnotatedOperation>* rootfs_ops,
182      std::vector<AnnotatedOperation>* kernel_ops) override;
183
184 private:
185  DISALLOW_COPY_AND_ASSIGN(InplaceGenerator);
186};
187
188};  // namespace chromeos_update_engine
189
190#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
191