inplace_generator_unittest.cc revision 14158570d3995008dc93a628004118b87a6bca01 
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#include "update_engine/payload_generator/inplace_generator.h"
6
7#include <map>
8#include <set>
9#include <sstream>
10#include <string>
11#include <utility>
12#include <vector>
13
14#include <base/logging.h>
15#include <base/strings/string_util.h>
16#include <gtest/gtest.h>
17
18#include "update_engine/payload_generator/cycle_breaker.h"
19#include "update_engine/payload_generator/delta_diff_generator.h"
20#include "update_engine/payload_generator/extent_ranges.h"
21#include "update_engine/payload_generator/graph_types.h"
22#include "update_engine/payload_generator/graph_utils.h"
23#include "update_engine/test_utils.h"
24#include "update_engine/utils.h"
25
26using std::map;
27using std::set;
28using std::string;
29using std::stringstream;
30using std::vector;
31
32namespace chromeos_update_engine {
33
34using Block = InplaceGenerator::Block;
35
36namespace {
37
38#define OP_BSDIFF DeltaArchiveManifest_InstallOperation_Type_BSDIFF
39#define OP_MOVE DeltaArchiveManifest_InstallOperation_Type_MOVE
40#define OP_REPLACE DeltaArchiveManifest_InstallOperation_Type_REPLACE
41#define OP_REPLACE_BZ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ
42
43void GenVertex(Vertex* out,
44               const vector<Extent>& src_extents,
45               const vector<Extent>& dst_extents,
46               const string& path,
47               DeltaArchiveManifest_InstallOperation_Type type) {
48  out->op.set_type(type);
49  out->file_name = path;
50  StoreExtents(src_extents, out->op.mutable_src_extents());
51  StoreExtents(dst_extents, out->op.mutable_dst_extents());
52}
53
54vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
55  return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
56}
57
58EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
59  EdgeProperties ret;
60  ret.extents = extents;
61  return ret;
62}
63
64EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
65  EdgeProperties ret;
66  ret.write_extents = extents;
67  return ret;
68}
69
70template<typename T>
71void DumpVect(const vector<T>& vect) {
72  stringstream ss(stringstream::out);
73  for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
74       it != e; ++it) {
75    ss << *it << ", ";
76  }
77  LOG(INFO) << "{" << ss.str() << "}";
78}
79
80void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
81  vect->resize(vect->size() + 1);
82  vect->back().set_start_block(start);
83  vect->back().set_num_blocks(length);
84}
85
86void OpAppendExtent(DeltaArchiveManifest_InstallOperation* op,
87                    uint64_t start,
88                    uint64_t length) {
89  Extent* extent = op->add_src_extents();
90  extent->set_start_block(start);
91  extent->set_num_blocks(length);
92}
93
94}  // namespace
95
96class InplaceGeneratorTest : public ::testing::Test {
97};
98
99TEST_F(InplaceGeneratorTest, BlockDefaultValues) {
100  // Tests that a Block is initialized with the default values as a
101  // Vertex::kInvalidIndex. This is required by the delta generators.
102  Block block;
103  EXPECT_EQ(Vertex::kInvalidIndex, block.reader);
104  EXPECT_EQ(Vertex::kInvalidIndex, block.writer);
105}
106
107TEST_F(InplaceGeneratorTest, SubstituteBlocksTest) {
108  vector<Extent> remove_blocks;
109  AppendExtent(&remove_blocks, 3, 3);
110  AppendExtent(&remove_blocks, 7, 1);
111  vector<Extent> replace_blocks;
112  AppendExtent(&replace_blocks, 10, 2);
113  AppendExtent(&replace_blocks, 13, 2);
114  Vertex vertex;
115  DeltaArchiveManifest_InstallOperation& op = vertex.op;
116  OpAppendExtent(&op, 4, 3);
117  OpAppendExtent(&op, kSparseHole, 4);  // Sparse hole in file
118  OpAppendExtent(&op, 3, 1);
119  OpAppendExtent(&op, 7, 3);
120
121  InplaceGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
122
123  EXPECT_EQ(7, op.src_extents_size());
124  EXPECT_EQ(11, op.src_extents(0).start_block());
125  EXPECT_EQ(1, op.src_extents(0).num_blocks());
126  EXPECT_EQ(13, op.src_extents(1).start_block());
127  EXPECT_EQ(1, op.src_extents(1).num_blocks());
128  EXPECT_EQ(6, op.src_extents(2).start_block());
129  EXPECT_EQ(1, op.src_extents(2).num_blocks());
130  EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
131  EXPECT_EQ(4, op.src_extents(3).num_blocks());
132  EXPECT_EQ(10, op.src_extents(4).start_block());
133  EXPECT_EQ(1, op.src_extents(4).num_blocks());
134  EXPECT_EQ(14, op.src_extents(5).start_block());
135  EXPECT_EQ(1, op.src_extents(5).num_blocks());
136  EXPECT_EQ(8, op.src_extents(6).start_block());
137  EXPECT_EQ(2, op.src_extents(6).num_blocks());
138}
139
140TEST_F(InplaceGeneratorTest, CutEdgesTest) {
141  Graph graph;
142  vector<Block> blocks(9);
143
144  // Create nodes in graph
145  {
146    graph.resize(graph.size() + 1);
147    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
148    // Reads from blocks 3, 5, 7
149    vector<Extent> extents;
150    AppendBlockToExtents(&extents, 3);
151    AppendBlockToExtents(&extents, 5);
152    AppendBlockToExtents(&extents, 7);
153    StoreExtents(extents,
154                                     graph.back().op.mutable_src_extents());
155    blocks[3].reader = graph.size() - 1;
156    blocks[5].reader = graph.size() - 1;
157    blocks[7].reader = graph.size() - 1;
158
159    // Writes to blocks 1, 2, 4
160    extents.clear();
161    AppendBlockToExtents(&extents, 1);
162    AppendBlockToExtents(&extents, 2);
163    AppendBlockToExtents(&extents, 4);
164    StoreExtents(extents,
165                                     graph.back().op.mutable_dst_extents());
166    blocks[1].writer = graph.size() - 1;
167    blocks[2].writer = graph.size() - 1;
168    blocks[4].writer = graph.size() - 1;
169  }
170  {
171    graph.resize(graph.size() + 1);
172    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
173    // Reads from blocks 1, 2, 4
174    vector<Extent> extents;
175    AppendBlockToExtents(&extents, 1);
176    AppendBlockToExtents(&extents, 2);
177    AppendBlockToExtents(&extents, 4);
178    StoreExtents(extents,
179                                     graph.back().op.mutable_src_extents());
180    blocks[1].reader = graph.size() - 1;
181    blocks[2].reader = graph.size() - 1;
182    blocks[4].reader = graph.size() - 1;
183
184    // Writes to blocks 3, 5, 6
185    extents.clear();
186    AppendBlockToExtents(&extents, 3);
187    AppendBlockToExtents(&extents, 5);
188    AppendBlockToExtents(&extents, 6);
189    StoreExtents(extents,
190                                     graph.back().op.mutable_dst_extents());
191    blocks[3].writer = graph.size() - 1;
192    blocks[5].writer = graph.size() - 1;
193    blocks[6].writer = graph.size() - 1;
194  }
195
196  // Create edges
197  InplaceGenerator::CreateEdges(&graph, blocks);
198
199  // Find cycles
200  CycleBreaker cycle_breaker;
201  set<Edge> cut_edges;
202  cycle_breaker.BreakCycles(graph, &cut_edges);
203
204  EXPECT_EQ(1, cut_edges.size());
205  EXPECT_TRUE(cut_edges.end() != cut_edges.find(
206      std::pair<Vertex::Index, Vertex::Index>(1, 0)));
207
208  vector<CutEdgeVertexes> cuts;
209  EXPECT_TRUE(InplaceGenerator::CutEdges(&graph, cut_edges, &cuts));
210
211  EXPECT_EQ(3, graph.size());
212
213  // Check new node in graph:
214  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
215            graph.back().op.type());
216  EXPECT_EQ(2, graph.back().op.src_extents_size());
217  EXPECT_EQ(1, graph.back().op.dst_extents_size());
218  EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
219  EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
220  EXPECT_TRUE(graph.back().out_edges.empty());
221
222  // Check that old node reads from new blocks
223  EXPECT_EQ(2, graph[0].op.src_extents_size());
224  EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
225  EXPECT_EQ(2, graph[0].op.src_extents(0).num_blocks());
226  EXPECT_EQ(7, graph[0].op.src_extents(1).start_block());
227  EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks());
228
229  // And that the old dst extents haven't changed
230  EXPECT_EQ(2, graph[0].op.dst_extents_size());
231  EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block());
232  EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks());
233  EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block());
234  EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks());
235
236  // Ensure it only depends on the next node and the new temp node
237  EXPECT_EQ(2, graph[0].out_edges.size());
238  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
239  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
240                                                                  1));
241
242  // Check second node has unchanged extents
243  EXPECT_EQ(2, graph[1].op.src_extents_size());
244  EXPECT_EQ(1, graph[1].op.src_extents(0).start_block());
245  EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks());
246  EXPECT_EQ(4, graph[1].op.src_extents(1).start_block());
247  EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks());
248
249  EXPECT_EQ(2, graph[1].op.dst_extents_size());
250  EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block());
251  EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
252  EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
253  EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
254
255  // Ensure it only depends on the next node
256  EXPECT_EQ(1, graph[1].out_edges.size());
257  EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
258}
259
260TEST_F(InplaceGeneratorTest, AssignTempBlocksReuseTest) {
261  Graph graph(9);
262
263  const vector<Extent> empt;
264  uint64_t tmp = kTempBlockStart;
265  const string kFilename = "/foo";
266
267  vector<CutEdgeVertexes> cuts;
268  cuts.resize(3);
269
270  // Simple broken loop:
271  GenVertex(&graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_MOVE);
272  GenVertex(&graph[1], VectOfExt(tmp, 1), VectOfExt(0, 1), "", OP_MOVE);
273  GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(tmp, 1), "", OP_MOVE);
274  // Corresponding edges:
275  graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
276  graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
277  graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
278  // Store the cut:
279  cuts[0].old_dst = 1;
280  cuts[0].old_src = 0;
281  cuts[0].new_vertex = 2;
282  cuts[0].tmp_extents = VectOfExt(tmp, 1);
283  tmp++;
284
285  // Slightly more complex pair of loops:
286  GenVertex(&graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", OP_MOVE);
287  GenVertex(&graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", OP_MOVE);
288  GenVertex(&graph[5], VectOfExt(tmp, 3), VectOfExt(4, 3), kFilename, OP_MOVE);
289  GenVertex(&graph[6], VectOfExt(2, 2), VectOfExt(tmp, 2), "", OP_MOVE);
290  GenVertex(&graph[7], VectOfExt(7, 1), VectOfExt(tmp + 2, 1), "", OP_MOVE);
291  // Corresponding edges:
292  graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
293  graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
294  graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
295  graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
296  graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
297  graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
298  // Store the cuts:
299  cuts[1].old_dst = 5;
300  cuts[1].old_src = 3;
301  cuts[1].new_vertex = 6;
302  cuts[1].tmp_extents = VectOfExt(tmp, 2);
303  cuts[2].old_dst = 5;
304  cuts[2].old_src = 4;
305  cuts[2].new_vertex = 7;
306  cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
307
308  // Supplier of temp block:
309  GenVertex(&graph[8], empt, VectOfExt(8, 1), "", OP_REPLACE);
310
311  // Specify the final order:
312  vector<Vertex::Index> op_indexes;
313  op_indexes.push_back(2);
314  op_indexes.push_back(0);
315  op_indexes.push_back(1);
316  op_indexes.push_back(6);
317  op_indexes.push_back(3);
318  op_indexes.push_back(7);
319  op_indexes.push_back(4);
320  op_indexes.push_back(5);
321  op_indexes.push_back(8);
322
323  vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
324  InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes,
325                                                &reverse_op_indexes);
326
327  int fd;
328  EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksReuseTest.XXXXXX",
329                                  nullptr,
330                                  &fd));
331  ScopedFdCloser fd_closer(&fd);
332  off_t data_file_size = 0;
333
334  EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph,
335                                                 "/dev/zero",
336                                                 fd,
337                                                 &data_file_size,
338                                                 &op_indexes,
339                                                 &reverse_op_indexes,
340                                                 cuts));
341  EXPECT_FALSE(graph[6].valid);
342  EXPECT_FALSE(graph[7].valid);
343  EXPECT_EQ(1, graph[1].op.src_extents_size());
344  EXPECT_EQ(2, graph[1].op.src_extents(0).start_block());
345  EXPECT_EQ(1, graph[1].op.src_extents(0).num_blocks());
346  EXPECT_EQ(OP_REPLACE_BZ, graph[5].op.type());
347}
348
349TEST_F(InplaceGeneratorTest, MoveFullOpsToBackTest) {
350  Graph graph(4);
351  graph[0].file_name = "A";
352  graph[0].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
353  graph[1].file_name = "B";
354  graph[1].op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
355  graph[2].file_name = "C";
356  graph[2].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
357  graph[3].file_name = "D";
358  graph[3].op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
359
360  vector<Vertex::Index> vect(graph.size());
361
362  for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
363    vect[i] = i;
364  }
365  InplaceGenerator::MoveFullOpsToBack(&graph, &vect);
366  EXPECT_EQ(vect.size(), graph.size());
367  EXPECT_EQ(graph[vect[0]].file_name, "B");
368  EXPECT_EQ(graph[vect[1]].file_name, "D");
369  EXPECT_EQ(graph[vect[2]].file_name, "A");
370  EXPECT_EQ(graph[vect[3]].file_name, "C");
371}
372
373TEST_F(InplaceGeneratorTest, AssignTempBlocksTest) {
374  Graph graph(9);
375  const vector<Extent> empt;  // empty
376  const string kFilename = "/foo";
377
378  // Some scratch space:
379  GenVertex(&graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
380  GenVertex(&graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
381  GenVertex(&graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
382
383  // A cycle that requires 10 blocks to break:
384  GenVertex(&graph[3], VectOfExt(10, 11), VectOfExt(0, 9), "", OP_BSDIFF);
385  graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
386  GenVertex(&graph[4], VectOfExt(0, 9), VectOfExt(10, 11), "", OP_BSDIFF);
387  graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
388
389  // A cycle that requires 9 blocks to break:
390  GenVertex(&graph[5], VectOfExt(40, 11), VectOfExt(30, 10), "", OP_BSDIFF);
391  graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
392  GenVertex(&graph[6], VectOfExt(30, 10), VectOfExt(40, 11), "", OP_BSDIFF);
393  graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
394
395  // A cycle that requires 40 blocks to break (which is too many):
396  GenVertex(&graph[7],
397            VectOfExt(120, 50),
398            VectOfExt(60, 40),
399            "",
400            OP_BSDIFF);
401  graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
402  GenVertex(&graph[8],
403            VectOfExt(60, 40),
404            VectOfExt(120, 50),
405            kFilename,
406            OP_BSDIFF);
407  graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
408
409  graph_utils::DumpGraph(graph);
410
411  vector<Vertex::Index> final_order;
412
413  int fd;
414  EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksTestData.XXXXXX",
415                                  nullptr,
416                                  &fd));
417  ScopedFdCloser fd_closer(&fd);
418  off_t data_file_size = 0;
419
420  EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
421                                                  "/dev/zero",
422                                                  fd,
423                                                  &data_file_size,
424                                                  &final_order,
425                                                  Vertex::kInvalidIndex));
426
427  Graph expected_graph(12);
428  GenVertex(&expected_graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
429  GenVertex(&expected_graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
430  GenVertex(&expected_graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
431  GenVertex(&expected_graph[3],
432            VectOfExt(10, 11),
433            VectOfExt(0, 9),
434            "",
435            OP_BSDIFF);
436  expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
437  GenVertex(&expected_graph[4],
438            VectOfExt(60, 9),
439            VectOfExt(10, 11),
440            "",
441            OP_BSDIFF);
442  expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
443  expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
444  GenVertex(&expected_graph[5],
445            VectOfExt(40, 11),
446            VectOfExt(30, 10),
447            "",
448            OP_BSDIFF);
449  expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
450
451  GenVertex(&expected_graph[6],
452            VectOfExt(60, 10),
453            VectOfExt(40, 11),
454            "",
455            OP_BSDIFF);
456  expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
457  expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
458
459  GenVertex(&expected_graph[7],
460            VectOfExt(120, 50),
461            VectOfExt(60, 40),
462            "",
463            OP_BSDIFF);
464  expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
465
466  GenVertex(&expected_graph[8], empt, VectOfExt(0, 50), "/foo", OP_REPLACE_BZ);
467  expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
468
469  GenVertex(&expected_graph[9],
470            VectOfExt(0, 9),
471            VectOfExt(60, 9),
472            "",
473            OP_MOVE);
474
475  GenVertex(&expected_graph[10],
476            VectOfExt(30, 10),
477            VectOfExt(60, 10),
478            "",
479            OP_MOVE);
480  expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
481
482  EXPECT_EQ(12, graph.size());
483  EXPECT_FALSE(graph.back().valid);
484  for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
485    EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
486    if (i == 8) {
487      // special case
488    } else {
489      // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
490    }
491  }
492}
493
494TEST_F(InplaceGeneratorTest, CreateScratchNodeTest) {
495  Vertex vertex;
496  InplaceGenerator::CreateScratchNode(12, 34, &vertex);
497  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
498            vertex.op.type());
499  EXPECT_EQ(0, vertex.op.data_offset());
500  EXPECT_EQ(0, vertex.op.data_length());
501  EXPECT_EQ(1, vertex.op.dst_extents_size());
502  EXPECT_EQ(12, vertex.op.dst_extents(0).start_block());
503  EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
504}
505
506TEST_F(InplaceGeneratorTest, ApplyMapTest) {
507  vector<uint64_t> collection = {1, 2, 3, 4, 6};
508  vector<uint64_t> expected_values = {1, 2, 5, 4, 8};
509  map<uint64_t, uint64_t> value_map;
510  value_map[3] = 5;
511  value_map[6] = 8;
512  value_map[5] = 10;
513
514  InplaceGenerator::ApplyMap(&collection, value_map);
515  EXPECT_EQ(expected_values, collection);
516}
517
518}  // namespace chromeos_update_engine
519