inplace_generator_unittest.cc revision 703022b71fc6a89796f2f97448b1a419007a52ca 
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/test_utils.h"
22#include "update_engine/utils.h"
23
24using std::set;
25using std::string;
26using std::stringstream;
27using std::vector;
28
29namespace chromeos_update_engine {
30
31typedef DeltaDiffGenerator::Block Block;
32
33namespace {
34
35#define OP_BSDIFF DeltaArchiveManifest_InstallOperation_Type_BSDIFF
36#define OP_MOVE DeltaArchiveManifest_InstallOperation_Type_MOVE
37#define OP_REPLACE DeltaArchiveManifest_InstallOperation_Type_REPLACE
38#define OP_REPLACE_BZ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ
39
40void GenVertex(Vertex* out,
41               const vector<Extent>& src_extents,
42               const vector<Extent>& dst_extents,
43               const string& path,
44               DeltaArchiveManifest_InstallOperation_Type type) {
45  out->op.set_type(type);
46  out->file_name = path;
47  DeltaDiffGenerator::StoreExtents(src_extents, out->op.mutable_src_extents());
48  DeltaDiffGenerator::StoreExtents(dst_extents, out->op.mutable_dst_extents());
49}
50
51vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
52  return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
53}
54
55EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
56  EdgeProperties ret;
57  ret.extents = extents;
58  return ret;
59}
60
61EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
62  EdgeProperties ret;
63  ret.write_extents = extents;
64  return ret;
65}
66
67template<typename T>
68void DumpVect(const vector<T>& vect) {
69  stringstream ss(stringstream::out);
70  for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
71       it != e; ++it) {
72    ss << *it << ", ";
73  }
74  LOG(INFO) << "{" << ss.str() << "}";
75}
76
77void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
78  vect->resize(vect->size() + 1);
79  vect->back().set_start_block(start);
80  vect->back().set_num_blocks(length);
81}
82
83void OpAppendExtent(DeltaArchiveManifest_InstallOperation* op,
84                    uint64_t start,
85                    uint64_t length) {
86  Extent* extent = op->add_src_extents();
87  extent->set_start_block(start);
88  extent->set_num_blocks(length);
89}
90
91}  // namespace
92
93class InplaceGeneratorTest : public ::testing::Test {
94};
95
96TEST_F(InplaceGeneratorTest, SubstituteBlocksTest) {
97  vector<Extent> remove_blocks;
98  AppendExtent(&remove_blocks, 3, 3);
99  AppendExtent(&remove_blocks, 7, 1);
100  vector<Extent> replace_blocks;
101  AppendExtent(&replace_blocks, 10, 2);
102  AppendExtent(&replace_blocks, 13, 2);
103  Vertex vertex;
104  DeltaArchiveManifest_InstallOperation& op = vertex.op;
105  OpAppendExtent(&op, 4, 3);
106  OpAppendExtent(&op, kSparseHole, 4);  // Sparse hole in file
107  OpAppendExtent(&op, 3, 1);
108  OpAppendExtent(&op, 7, 3);
109
110  InplaceGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
111
112  EXPECT_EQ(7, op.src_extents_size());
113  EXPECT_EQ(11, op.src_extents(0).start_block());
114  EXPECT_EQ(1, op.src_extents(0).num_blocks());
115  EXPECT_EQ(13, op.src_extents(1).start_block());
116  EXPECT_EQ(1, op.src_extents(1).num_blocks());
117  EXPECT_EQ(6, op.src_extents(2).start_block());
118  EXPECT_EQ(1, op.src_extents(2).num_blocks());
119  EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
120  EXPECT_EQ(4, op.src_extents(3).num_blocks());
121  EXPECT_EQ(10, op.src_extents(4).start_block());
122  EXPECT_EQ(1, op.src_extents(4).num_blocks());
123  EXPECT_EQ(14, op.src_extents(5).start_block());
124  EXPECT_EQ(1, op.src_extents(5).num_blocks());
125  EXPECT_EQ(8, op.src_extents(6).start_block());
126  EXPECT_EQ(2, op.src_extents(6).num_blocks());
127}
128
129TEST_F(InplaceGeneratorTest, CutEdgesTest) {
130  Graph graph;
131  vector<Block> blocks(9);
132
133  // Create nodes in graph
134  {
135    graph.resize(graph.size() + 1);
136    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
137    // Reads from blocks 3, 5, 7
138    vector<Extent> extents;
139    graph_utils::AppendBlockToExtents(&extents, 3);
140    graph_utils::AppendBlockToExtents(&extents, 5);
141    graph_utils::AppendBlockToExtents(&extents, 7);
142    DeltaDiffGenerator::StoreExtents(extents,
143                                     graph.back().op.mutable_src_extents());
144    blocks[3].reader = graph.size() - 1;
145    blocks[5].reader = graph.size() - 1;
146    blocks[7].reader = graph.size() - 1;
147
148    // Writes to blocks 1, 2, 4
149    extents.clear();
150    graph_utils::AppendBlockToExtents(&extents, 1);
151    graph_utils::AppendBlockToExtents(&extents, 2);
152    graph_utils::AppendBlockToExtents(&extents, 4);
153    DeltaDiffGenerator::StoreExtents(extents,
154                                     graph.back().op.mutable_dst_extents());
155    blocks[1].writer = graph.size() - 1;
156    blocks[2].writer = graph.size() - 1;
157    blocks[4].writer = graph.size() - 1;
158  }
159  {
160    graph.resize(graph.size() + 1);
161    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
162    // Reads from blocks 1, 2, 4
163    vector<Extent> extents;
164    graph_utils::AppendBlockToExtents(&extents, 1);
165    graph_utils::AppendBlockToExtents(&extents, 2);
166    graph_utils::AppendBlockToExtents(&extents, 4);
167    DeltaDiffGenerator::StoreExtents(extents,
168                                     graph.back().op.mutable_src_extents());
169    blocks[1].reader = graph.size() - 1;
170    blocks[2].reader = graph.size() - 1;
171    blocks[4].reader = graph.size() - 1;
172
173    // Writes to blocks 3, 5, 6
174    extents.clear();
175    graph_utils::AppendBlockToExtents(&extents, 3);
176    graph_utils::AppendBlockToExtents(&extents, 5);
177    graph_utils::AppendBlockToExtents(&extents, 6);
178    DeltaDiffGenerator::StoreExtents(extents,
179                                     graph.back().op.mutable_dst_extents());
180    blocks[3].writer = graph.size() - 1;
181    blocks[5].writer = graph.size() - 1;
182    blocks[6].writer = graph.size() - 1;
183  }
184
185  // Create edges
186  InplaceGenerator::CreateEdges(&graph, blocks);
187
188  // Find cycles
189  CycleBreaker cycle_breaker;
190  set<Edge> cut_edges;
191  cycle_breaker.BreakCycles(graph, &cut_edges);
192
193  EXPECT_EQ(1, cut_edges.size());
194  EXPECT_TRUE(cut_edges.end() != cut_edges.find(
195      std::pair<Vertex::Index, Vertex::Index>(1, 0)));
196
197  vector<CutEdgeVertexes> cuts;
198  EXPECT_TRUE(InplaceGenerator::CutEdges(&graph, cut_edges, &cuts));
199
200  EXPECT_EQ(3, graph.size());
201
202  // Check new node in graph:
203  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
204            graph.back().op.type());
205  EXPECT_EQ(2, graph.back().op.src_extents_size());
206  EXPECT_EQ(1, graph.back().op.dst_extents_size());
207  EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
208  EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
209  EXPECT_TRUE(graph.back().out_edges.empty());
210
211  // Check that old node reads from new blocks
212  EXPECT_EQ(2, graph[0].op.src_extents_size());
213  EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
214  EXPECT_EQ(2, graph[0].op.src_extents(0).num_blocks());
215  EXPECT_EQ(7, graph[0].op.src_extents(1).start_block());
216  EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks());
217
218  // And that the old dst extents haven't changed
219  EXPECT_EQ(2, graph[0].op.dst_extents_size());
220  EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block());
221  EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks());
222  EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block());
223  EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks());
224
225  // Ensure it only depends on the next node and the new temp node
226  EXPECT_EQ(2, graph[0].out_edges.size());
227  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
228  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
229                                                                  1));
230
231  // Check second node has unchanged extents
232  EXPECT_EQ(2, graph[1].op.src_extents_size());
233  EXPECT_EQ(1, graph[1].op.src_extents(0).start_block());
234  EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks());
235  EXPECT_EQ(4, graph[1].op.src_extents(1).start_block());
236  EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks());
237
238  EXPECT_EQ(2, graph[1].op.dst_extents_size());
239  EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block());
240  EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
241  EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
242  EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
243
244  // Ensure it only depends on the next node
245  EXPECT_EQ(1, graph[1].out_edges.size());
246  EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
247}
248
249TEST_F(InplaceGeneratorTest, RunAsRootAssignTempBlocksReuseTest) {
250  // AssignTempBlocks(Graph* graph,
251  // const string& new_root,
252  // int data_fd,
253  // off_t* data_file_size,
254  // vector<Vertex::Index>* op_indexes,
255  // vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
256  // const vector<CutEdgeVertexes>& cuts
257  Graph graph(9);
258
259  const vector<Extent> empt;
260  uint64_t tmp = kTempBlockStart;
261  const string kFilename = "/foo";
262
263  vector<CutEdgeVertexes> cuts;
264  cuts.resize(3);
265
266  // Simple broken loop:
267  GenVertex(&graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_MOVE);
268  GenVertex(&graph[1], VectOfExt(tmp, 1), VectOfExt(0, 1), "", OP_MOVE);
269  GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(tmp, 1), "", OP_MOVE);
270  // Corresponding edges:
271  graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
272  graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
273  graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
274  // Store the cut:
275  cuts[0].old_dst = 1;
276  cuts[0].old_src = 0;
277  cuts[0].new_vertex = 2;
278  cuts[0].tmp_extents = VectOfExt(tmp, 1);
279  tmp++;
280
281  // Slightly more complex pair of loops:
282  GenVertex(&graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", OP_MOVE);
283  GenVertex(&graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", OP_MOVE);
284  GenVertex(&graph[5], VectOfExt(tmp, 3), VectOfExt(4, 3), kFilename, OP_MOVE);
285  GenVertex(&graph[6], VectOfExt(2, 2), VectOfExt(tmp, 2), "", OP_MOVE);
286  GenVertex(&graph[7], VectOfExt(7, 1), VectOfExt(tmp + 2, 1), "", OP_MOVE);
287  // Corresponding edges:
288  graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
289  graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
290  graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
291  graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
292  graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
293  graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
294  // Store the cuts:
295  cuts[1].old_dst = 5;
296  cuts[1].old_src = 3;
297  cuts[1].new_vertex = 6;
298  cuts[1].tmp_extents = VectOfExt(tmp, 2);
299  cuts[2].old_dst = 5;
300  cuts[2].old_src = 4;
301  cuts[2].new_vertex = 7;
302  cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
303
304  // Supplier of temp block:
305  GenVertex(&graph[8], empt, VectOfExt(8, 1), "", OP_REPLACE);
306
307  // Specify the final order:
308  vector<Vertex::Index> op_indexes;
309  op_indexes.push_back(2);
310  op_indexes.push_back(0);
311  op_indexes.push_back(1);
312  op_indexes.push_back(6);
313  op_indexes.push_back(3);
314  op_indexes.push_back(7);
315  op_indexes.push_back(4);
316  op_indexes.push_back(5);
317  op_indexes.push_back(8);
318
319  vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
320  InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes,
321                                                &reverse_op_indexes);
322
323  // Prepare the filesystem with the minimum required for this to work
324  string temp_dir;
325  EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksReuseTest.XXXXXX",
326                                       &temp_dir));
327  ScopedDirRemover temp_dir_remover(temp_dir);
328
329  chromeos::Blob temp_data(kBlockSize * 3);
330  test_utils::FillWithData(&temp_data);
331  EXPECT_TRUE(test_utils::WriteFileVector(temp_dir + kFilename, temp_data));
332  ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
333
334  int fd;
335  EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksReuseTest.XXXXXX",
336                                  nullptr,
337                                  &fd));
338  ScopedFdCloser fd_closer(&fd);
339  off_t data_file_size = 0;
340
341  EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph,
342                                                 temp_dir,
343                                                 fd,
344                                                 &data_file_size,
345                                                 &op_indexes,
346                                                 &reverse_op_indexes,
347                                                 cuts));
348  EXPECT_FALSE(graph[6].valid);
349  EXPECT_FALSE(graph[7].valid);
350  EXPECT_EQ(1, graph[1].op.src_extents_size());
351  EXPECT_EQ(2, graph[1].op.src_extents(0).start_block());
352  EXPECT_EQ(1, graph[1].op.src_extents(0).num_blocks());
353  EXPECT_EQ(OP_REPLACE_BZ, graph[5].op.type());
354}
355
356TEST_F(InplaceGeneratorTest, MoveFullOpsToBackTest) {
357  Graph graph(4);
358  graph[0].file_name = "A";
359  graph[0].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
360  graph[1].file_name = "B";
361  graph[1].op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
362  graph[2].file_name = "C";
363  graph[2].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
364  graph[3].file_name = "D";
365  graph[3].op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
366
367  vector<Vertex::Index> vect(graph.size());
368
369  for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
370    vect[i] = i;
371  }
372  InplaceGenerator::MoveFullOpsToBack(&graph, &vect);
373  EXPECT_EQ(vect.size(), graph.size());
374  EXPECT_EQ(graph[vect[0]].file_name, "B");
375  EXPECT_EQ(graph[vect[1]].file_name, "D");
376  EXPECT_EQ(graph[vect[2]].file_name, "A");
377  EXPECT_EQ(graph[vect[3]].file_name, "C");
378}
379
380TEST_F(InplaceGeneratorTest, RunAsRootAssignTempBlocksTest) {
381  Graph graph(9);
382  const vector<Extent> empt;  // empty
383  const string kFilename = "/foo";
384
385  // Some scratch space:
386  GenVertex(&graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
387  GenVertex(&graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
388  GenVertex(&graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
389
390  // A cycle that requires 10 blocks to break:
391  GenVertex(&graph[3], VectOfExt(10, 11), VectOfExt(0, 9), "", OP_BSDIFF);
392  graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
393  GenVertex(&graph[4], VectOfExt(0, 9), VectOfExt(10, 11), "", OP_BSDIFF);
394  graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
395
396  // A cycle that requires 9 blocks to break:
397  GenVertex(&graph[5], VectOfExt(40, 11), VectOfExt(30, 10), "", OP_BSDIFF);
398  graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
399  GenVertex(&graph[6], VectOfExt(30, 10), VectOfExt(40, 11), "", OP_BSDIFF);
400  graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
401
402  // A cycle that requires 40 blocks to break (which is too many):
403  GenVertex(&graph[7],
404            VectOfExt(120, 50),
405            VectOfExt(60, 40),
406            "",
407            OP_BSDIFF);
408  graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
409  GenVertex(&graph[8],
410            VectOfExt(60, 40),
411            VectOfExt(120, 50),
412            kFilename,
413            OP_BSDIFF);
414  graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
415
416  graph_utils::DumpGraph(graph);
417
418  vector<Vertex::Index> final_order;
419
420
421  // Prepare the filesystem with the minimum required for this to work
422  string temp_dir;
423  EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksTest.XXXXXX",
424                                       &temp_dir));
425  ScopedDirRemover temp_dir_remover(temp_dir);
426
427  chromeos::Blob temp_data(kBlockSize * 50);
428  test_utils::FillWithData(&temp_data);
429  EXPECT_TRUE(test_utils::WriteFileVector(temp_dir + kFilename, temp_data));
430  ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
431
432  int fd;
433  EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksTestData.XXXXXX",
434                                  nullptr,
435                                  &fd));
436  ScopedFdCloser fd_closer(&fd);
437  off_t data_file_size = 0;
438
439
440  EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
441                                                  temp_dir,
442                                                  fd,
443                                                  &data_file_size,
444                                                  &final_order,
445                                                  Vertex::kInvalidIndex));
446
447
448  Graph expected_graph(12);
449  GenVertex(&expected_graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
450  GenVertex(&expected_graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
451  GenVertex(&expected_graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
452  GenVertex(&expected_graph[3],
453            VectOfExt(10, 11),
454            VectOfExt(0, 9),
455            "",
456            OP_BSDIFF);
457  expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
458  GenVertex(&expected_graph[4],
459            VectOfExt(60, 9),
460            VectOfExt(10, 11),
461            "",
462            OP_BSDIFF);
463  expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
464  expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
465  GenVertex(&expected_graph[5],
466            VectOfExt(40, 11),
467            VectOfExt(30, 10),
468            "",
469            OP_BSDIFF);
470  expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
471
472  GenVertex(&expected_graph[6],
473            VectOfExt(60, 10),
474            VectOfExt(40, 11),
475            "",
476            OP_BSDIFF);
477  expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
478  expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
479
480  GenVertex(&expected_graph[7],
481            VectOfExt(120, 50),
482            VectOfExt(60, 40),
483            "",
484            OP_BSDIFF);
485  expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
486
487  GenVertex(&expected_graph[8], empt, VectOfExt(0, 50), "/foo", OP_REPLACE_BZ);
488  expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
489
490  GenVertex(&expected_graph[9],
491            VectOfExt(0, 9),
492            VectOfExt(60, 9),
493            "",
494            OP_MOVE);
495
496  GenVertex(&expected_graph[10],
497            VectOfExt(30, 10),
498            VectOfExt(60, 10),
499            "",
500            OP_MOVE);
501  expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
502
503  EXPECT_EQ(12, graph.size());
504  EXPECT_FALSE(graph.back().valid);
505  for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
506    EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
507    if (i == 8) {
508      // special case
509    } else {
510      // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
511    }
512  }
513}
514
515// Test that sparse holes are not used as scratch. More specifically, test that
516// if all full operations write to sparse holes and there's no extra scratch
517// space, delta operations that need scratch are converted to full. See
518// crbug.com/238440.
519TEST_F(InplaceGeneratorTest, RunAsRootNoSparseAsTempTest) {
520  Graph graph(3);
521  const vector<Extent> kEmpty;
522  const string kFilename = "/foo";
523
524  // Make sure this sparse hole is not used as scratch.
525  GenVertex(&graph[0], kEmpty, VectOfExt(kSparseHole, 1), "", OP_REPLACE);
526
527  // Create a single-block cycle.
528  GenVertex(&graph[1], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_BSDIFF);
529  graph[1].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
530  GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(0, 1), kFilename, OP_BSDIFF);
531  graph[2].out_edges[1] = EdgeWithReadDep(VectOfExt(0, 1));
532
533  graph_utils::DumpGraph(graph);
534
535  vector<Vertex::Index> final_order;
536
537  // Prepare the filesystem with the minimum required for this to work.
538  string temp_dir;
539  EXPECT_TRUE(utils::MakeTempDirectory("NoSparseAsTempTest.XXXXXX",
540                                       &temp_dir));
541  ScopedDirRemover temp_dir_remover(temp_dir);
542
543  chromeos::Blob temp_data(kBlockSize);
544  test_utils::FillWithData(&temp_data);
545  EXPECT_TRUE(test_utils::WriteFileVector(temp_dir + kFilename, temp_data));
546  ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
547
548  int fd = -1;
549  EXPECT_TRUE(utils::MakeTempFile("NoSparseAsTempTestData.XXXXXX",
550                                  nullptr,
551                                  &fd));
552  ScopedFdCloser fd_closer(&fd);
553  off_t data_file_size = 0;
554
555  EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
556                                                  temp_dir,
557                                                  fd,
558                                                  &data_file_size,
559                                                  &final_order,
560                                                  Vertex::kInvalidIndex));
561
562  ASSERT_EQ(4, graph.size());
563
564  // The second BSDIFF operation must have been converted to a full operation
565  // (due to insufficient scratch space).
566  EXPECT_TRUE(graph[2].op.type() == OP_REPLACE ||
567              graph[2].op.type() == OP_REPLACE_BZ);
568
569  // The temporary node created for breaking the cycle must have been marked as
570  // invalid.
571  EXPECT_FALSE(graph[3].valid);
572}
573
574// Test that sparse holes are not used as scratch. More specifically, test that
575// if scratch space comes only from full operations writing to real blocks as
576// well as sparse holes, only the real blocks are utilized. See
577// crbug.com/238440.
578TEST_F(InplaceGeneratorTest, NoSparseAsTempTest) {
579  Graph graph;
580  vector<Block> blocks(4);
581
582  // Create nodes in |graph|.
583  {
584    graph.resize(graph.size() + 1);
585    graph.back().op.set_type(
586        DeltaArchiveManifest_InstallOperation_Type_REPLACE);
587
588    // Write to a sparse hole -- basically a no-op to ensure sparse holes are
589    // not used as scratch.
590    vector<Extent> extents;
591    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
592    DeltaDiffGenerator::StoreExtents(extents,
593                                     graph.back().op.mutable_dst_extents());
594  }
595  {
596    graph.resize(graph.size() + 1);
597    graph.back().op.set_type(OP_REPLACE);
598
599    // Scratch space: write to block 0 with sparse holes around.
600    vector<Extent> extents;
601    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
602    graph_utils::AppendBlockToExtents(&extents, 0);
603    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
604    DeltaDiffGenerator::StoreExtents(extents,
605                                     graph.back().op.mutable_dst_extents());
606    blocks[0].writer = graph.size() - 1;
607  }
608  {
609    graph.resize(graph.size() + 1);
610    graph.back().op.set_type(OP_REPLACE);
611
612    // Write to a sparse hole.
613    vector<Extent> extents;
614    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
615    DeltaDiffGenerator::StoreExtents(extents,
616                                     graph.back().op.mutable_dst_extents());
617  }
618  // Create a two-node cycle between (2, sparse, sparse) and (1, sparse, 3).
619  {
620    graph.resize(graph.size() + 1);
621    graph.back().op.set_type(OP_MOVE);
622    // Read from (2, sparse, sparse).
623    vector<Extent> extents;
624    graph_utils::AppendBlockToExtents(&extents, 2);
625    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
626    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
627    DeltaDiffGenerator::StoreExtents(extents,
628                                     graph.back().op.mutable_src_extents());
629    blocks[2].reader = graph.size() - 1;
630
631    // Write to (1, sparse, 3).
632    extents.clear();
633    graph_utils::AppendBlockToExtents(&extents, 1);
634    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
635    graph_utils::AppendBlockToExtents(&extents, 3);
636    DeltaDiffGenerator::StoreExtents(extents,
637                                     graph.back().op.mutable_dst_extents());
638    blocks[1].writer = graph.size() - 1;
639    blocks[3].writer = graph.size() - 1;
640  }
641  {
642    graph.resize(graph.size() + 1);
643    graph.back().op.set_type(OP_MOVE);
644    // Read from (1, sparse, 3).
645    vector<Extent> extents;
646    graph_utils::AppendBlockToExtents(&extents, 1);
647    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
648    graph_utils::AppendBlockToExtents(&extents, 3);
649    DeltaDiffGenerator::StoreExtents(extents,
650                                     graph.back().op.mutable_src_extents());
651    blocks[1].reader = graph.size() - 1;
652    blocks[3].reader = graph.size() - 1;
653
654    // Write to (2, sparse, sparse).
655    extents.clear();
656    graph_utils::AppendBlockToExtents(&extents, 2);
657    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
658    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
659    DeltaDiffGenerator::StoreExtents(extents,
660                                     graph.back().op.mutable_dst_extents());
661    blocks[2].writer = graph.size() - 1;
662  }
663
664  graph_utils::DumpGraph(graph);
665
666  // Create edges
667  InplaceGenerator::CreateEdges(&graph, blocks);
668
669  graph_utils::DumpGraph(graph);
670
671  vector<Vertex::Index> final_order;
672  off_t data_file_size = 0;
673  EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
674                                                  "/non/existent/dir",
675                                                  -1,
676                                                  &data_file_size,
677                                                  &final_order,
678                                                  Vertex::kInvalidIndex));
679
680  // Check for a single temporary node writing to scratch.
681  ASSERT_EQ(6, graph.size());
682  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
683            graph[5].op.type());
684  EXPECT_EQ(1, graph[5].op.src_extents_size());
685  ASSERT_EQ(1, graph[5].op.dst_extents_size());
686  EXPECT_EQ(0, graph[5].op.dst_extents(0).start_block());
687  EXPECT_EQ(1, graph[5].op.dst_extents(0).num_blocks());
688
689  // Make sure the cycle nodes still read from and write to sparse holes.
690  for (int i = 3; i < 5; i++) {
691    ASSERT_GE(graph[i].op.src_extents_size(), 2);
692    EXPECT_EQ(kSparseHole, graph[i].op.src_extents(1).start_block());
693    ASSERT_GE(graph[i].op.dst_extents_size(), 2);
694    EXPECT_EQ(kSparseHole, graph[i].op.dst_extents(1).start_block());
695  }
696}
697
698TEST_F(InplaceGeneratorTest, CreateScratchNodeTest) {
699  Vertex vertex;
700  InplaceGenerator::CreateScratchNode(12, 34, &vertex);
701  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
702            vertex.op.type());
703  EXPECT_EQ(0, vertex.op.data_offset());
704  EXPECT_EQ(0, vertex.op.data_length());
705  EXPECT_EQ(1, vertex.op.dst_extents_size());
706  EXPECT_EQ(12, vertex.op.dst_extents(0).start_block());
707  EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
708}
709
710}  // namespace chromeos_update_engine
711