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