inplace_generator_unittest.cc revision 05871fab8b32938ad66ce230250ff6db5563bd7a 
1//
2// Copyright (C) 2015 The Android Open Source Project
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8//      http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15//
16
17#include "update_engine/payload_generator/inplace_generator.h"
18
19#include <map>
20#include <set>
21#include <sstream>
22#include <string>
23#include <utility>
24#include <vector>
25
26#include <base/format_macros.h>
27#include <base/logging.h>
28#include <base/strings/string_util.h>
29#include <base/strings/stringprintf.h>
30#include <gtest/gtest.h>
31
32#include "update_engine/common/test_utils.h"
33#include "update_engine/common/utils.h"
34#include "update_engine/payload_generator/cycle_breaker.h"
35#include "update_engine/payload_generator/delta_diff_generator.h"
36#include "update_engine/payload_generator/delta_diff_utils.h"
37#include "update_engine/payload_generator/extent_ranges.h"
38#include "update_engine/payload_generator/graph_types.h"
39#include "update_engine/payload_generator/graph_utils.h"
40
41using std::map;
42using std::set;
43using std::string;
44using std::stringstream;
45using std::vector;
46
47namespace chromeos_update_engine {
48
49using Block = InplaceGenerator::Block;
50
51namespace {
52
53void GenVertex(Vertex* out,
54               const vector<Extent>& src_extents,
55               const vector<Extent>& dst_extents,
56               const string& path,
57               InstallOperation_Type type) {
58  out->aop.op.set_type(type);
59  out->aop.name = path;
60  StoreExtents(src_extents, out->aop.op.mutable_src_extents());
61  StoreExtents(dst_extents, out->aop.op.mutable_dst_extents());
62}
63
64vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
65  return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
66}
67
68EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
69  EdgeProperties ret;
70  ret.extents = extents;
71  return ret;
72}
73
74EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
75  EdgeProperties ret;
76  ret.write_extents = extents;
77  return ret;
78}
79
80template<typename T>
81void DumpVect(const vector<T>& vect) {
82  stringstream ss(stringstream::out);
83  for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
84       it != e; ++it) {
85    ss << *it << ", ";
86  }
87  LOG(INFO) << "{" << ss.str() << "}";
88}
89
90void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
91  vect->resize(vect->size() + 1);
92  vect->back().set_start_block(start);
93  vect->back().set_num_blocks(length);
94}
95
96void OpAppendExtent(InstallOperation* op, uint64_t start, uint64_t length) {
97  Extent* extent = op->add_src_extents();
98  extent->set_start_block(start);
99  extent->set_num_blocks(length);
100}
101
102}  // namespace
103
104class InplaceGeneratorTest : public ::testing::Test {
105 protected:
106  // Initialize |blob_path_|, |blob_file_size_| and |blob_file_fd_| variables
107  // with a new blob file. The file is closed and removed automatically when
108  // the test finishes.
109  void CreateBlobFile() {
110    // blob_fd_closer_ takes a pointer to blob_fd_. Make sure we destroy a
111    // previous instance before overriding blob_fd_.
112    blob_fd_closer_.reset();
113    EXPECT_TRUE(utils::MakeTempFile(
114        "InplaceGenerator_blob_file.XXXXXX", &blob_path_, &blob_fd_));
115    blob_path_unlinker_.reset(new ScopedPathUnlinker(blob_path_));
116    blob_fd_closer_.reset(new ScopedFdCloser(&blob_fd_));
117    blob_file_size_ = 0;
118    EXPECT_GE(blob_fd_, 0);
119    blob_file_.reset(new BlobFileWriter(blob_fd_, &blob_file_size_));
120  }
121
122  // Dump the list of operations |aops| in case of test failure.
123  void DumpAopsOnFailure(const vector<AnnotatedOperation>& aops) {
124    if (HasNonfatalFailure()) {
125      LOG(INFO) << "Result operation list:";
126      for (const auto& aop : aops) {
127        LOG(INFO) << aop;
128      }
129    }
130  }
131
132  // Blob file name, file descriptor and file size used to store operation
133  // blobs.
134  string blob_path_;
135  int blob_fd_{-1};
136  off_t blob_file_size_{0};
137  std::unique_ptr<BlobFileWriter> blob_file_;
138  std::unique_ptr<ScopedPathUnlinker> blob_path_unlinker_;
139  std::unique_ptr<ScopedFdCloser> blob_fd_closer_;
140};
141
142TEST_F(InplaceGeneratorTest, BlockDefaultValues) {
143  // Tests that a Block is initialized with the default values as a
144  // Vertex::kInvalidIndex. This is required by the delta generators.
145  Block block;
146  EXPECT_EQ(Vertex::kInvalidIndex, block.reader);
147  EXPECT_EQ(Vertex::kInvalidIndex, block.writer);
148}
149
150TEST_F(InplaceGeneratorTest, SubstituteBlocksTest) {
151  vector<Extent> remove_blocks;
152  AppendExtent(&remove_blocks, 3, 3);
153  AppendExtent(&remove_blocks, 7, 1);
154  vector<Extent> replace_blocks;
155  AppendExtent(&replace_blocks, 10, 2);
156  AppendExtent(&replace_blocks, 13, 2);
157  Vertex vertex;
158  InstallOperation& op = vertex.aop.op;
159  OpAppendExtent(&op, 4, 3);
160  OpAppendExtent(&op, kSparseHole, 4);  // Sparse hole in file
161  OpAppendExtent(&op, 3, 1);
162  OpAppendExtent(&op, 7, 3);
163
164  InplaceGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
165
166  EXPECT_EQ(7, op.src_extents_size());
167  EXPECT_EQ(11U, op.src_extents(0).start_block());
168  EXPECT_EQ(1U, op.src_extents(0).num_blocks());
169  EXPECT_EQ(13U, op.src_extents(1).start_block());
170  EXPECT_EQ(1U, op.src_extents(1).num_blocks());
171  EXPECT_EQ(6U, op.src_extents(2).start_block());
172  EXPECT_EQ(1U, op.src_extents(2).num_blocks());
173  EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
174  EXPECT_EQ(4U, op.src_extents(3).num_blocks());
175  EXPECT_EQ(10U, op.src_extents(4).start_block());
176  EXPECT_EQ(1U, op.src_extents(4).num_blocks());
177  EXPECT_EQ(14U, op.src_extents(5).start_block());
178  EXPECT_EQ(1U, op.src_extents(5).num_blocks());
179  EXPECT_EQ(8U, op.src_extents(6).start_block());
180  EXPECT_EQ(2U, op.src_extents(6).num_blocks());
181}
182
183TEST_F(InplaceGeneratorTest, CutEdgesTest) {
184  Graph graph;
185  vector<Block> blocks(9);
186
187  // Create nodes in graph
188  {
189    graph.resize(graph.size() + 1);
190    graph.back().aop.op.set_type(InstallOperation::MOVE);
191    // Reads from blocks 3, 5, 7
192    vector<Extent> extents;
193    AppendBlockToExtents(&extents, 3);
194    AppendBlockToExtents(&extents, 5);
195    AppendBlockToExtents(&extents, 7);
196    StoreExtents(extents, graph.back().aop.op.mutable_src_extents());
197    blocks[3].reader = graph.size() - 1;
198    blocks[5].reader = graph.size() - 1;
199    blocks[7].reader = graph.size() - 1;
200
201    // Writes to blocks 1, 2, 4
202    extents.clear();
203    AppendBlockToExtents(&extents, 1);
204    AppendBlockToExtents(&extents, 2);
205    AppendBlockToExtents(&extents, 4);
206    StoreExtents(extents, graph.back().aop.op.mutable_dst_extents());
207    blocks[1].writer = graph.size() - 1;
208    blocks[2].writer = graph.size() - 1;
209    blocks[4].writer = graph.size() - 1;
210  }
211  {
212    graph.resize(graph.size() + 1);
213    graph.back().aop.op.set_type(InstallOperation::MOVE);
214    // Reads from blocks 1, 2, 4
215    vector<Extent> extents;
216    AppendBlockToExtents(&extents, 1);
217    AppendBlockToExtents(&extents, 2);
218    AppendBlockToExtents(&extents, 4);
219    StoreExtents(extents, graph.back().aop.op.mutable_src_extents());
220    blocks[1].reader = graph.size() - 1;
221    blocks[2].reader = graph.size() - 1;
222    blocks[4].reader = graph.size() - 1;
223
224    // Writes to blocks 3, 5, 6
225    extents.clear();
226    AppendBlockToExtents(&extents, 3);
227    AppendBlockToExtents(&extents, 5);
228    AppendBlockToExtents(&extents, 6);
229    StoreExtents(extents, graph.back().aop.op.mutable_dst_extents());
230    blocks[3].writer = graph.size() - 1;
231    blocks[5].writer = graph.size() - 1;
232    blocks[6].writer = graph.size() - 1;
233  }
234
235  // Create edges
236  InplaceGenerator::CreateEdges(&graph, blocks);
237
238  // Find cycles
239  CycleBreaker cycle_breaker;
240  set<Edge> cut_edges;
241  cycle_breaker.BreakCycles(graph, &cut_edges);
242
243  EXPECT_EQ(1U, cut_edges.size());
244  EXPECT_TRUE(cut_edges.end() != cut_edges.find(
245      std::pair<Vertex::Index, Vertex::Index>(1, 0)));
246
247  vector<CutEdgeVertexes> cuts;
248  EXPECT_TRUE(InplaceGenerator::CutEdges(&graph, cut_edges, &cuts));
249
250  EXPECT_EQ(3U, graph.size());
251
252  // Check new node in graph:
253  EXPECT_EQ(InstallOperation::MOVE, graph.back().aop.op.type());
254  EXPECT_EQ(2, graph.back().aop.op.src_extents_size());
255  EXPECT_EQ(1, graph.back().aop.op.dst_extents_size());
256  EXPECT_EQ(kTempBlockStart, graph.back().aop.op.dst_extents(0).start_block());
257  EXPECT_EQ(2U, graph.back().aop.op.dst_extents(0).num_blocks());
258  EXPECT_TRUE(graph.back().out_edges.empty());
259
260  // Check that old node reads from new blocks
261  EXPECT_EQ(2, graph[0].aop.op.src_extents_size());
262  EXPECT_EQ(kTempBlockStart, graph[0].aop.op.src_extents(0).start_block());
263  EXPECT_EQ(2U, graph[0].aop.op.src_extents(0).num_blocks());
264  EXPECT_EQ(7U, graph[0].aop.op.src_extents(1).start_block());
265  EXPECT_EQ(1U, graph[0].aop.op.src_extents(1).num_blocks());
266
267  // And that the old dst extents haven't changed
268  EXPECT_EQ(2, graph[0].aop.op.dst_extents_size());
269  EXPECT_EQ(1U, graph[0].aop.op.dst_extents(0).start_block());
270  EXPECT_EQ(2U, graph[0].aop.op.dst_extents(0).num_blocks());
271  EXPECT_EQ(4U, graph[0].aop.op.dst_extents(1).start_block());
272  EXPECT_EQ(1U, graph[0].aop.op.dst_extents(1).num_blocks());
273
274  // Ensure it only depends on the next node and the new temp node
275  EXPECT_EQ(2U, graph[0].out_edges.size());
276  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
277  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
278                                                                  1));
279
280  // Check second node has unchanged extents
281  EXPECT_EQ(2, graph[1].aop.op.src_extents_size());
282  EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).start_block());
283  EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).num_blocks());
284  EXPECT_EQ(4U, graph[1].aop.op.src_extents(1).start_block());
285  EXPECT_EQ(1U, graph[1].aop.op.src_extents(1).num_blocks());
286
287  EXPECT_EQ(2, graph[1].aop.op.dst_extents_size());
288  EXPECT_EQ(3U, graph[1].aop.op.dst_extents(0).start_block());
289  EXPECT_EQ(1U, graph[1].aop.op.dst_extents(0).num_blocks());
290  EXPECT_EQ(5U, graph[1].aop.op.dst_extents(1).start_block());
291  EXPECT_EQ(2U, graph[1].aop.op.dst_extents(1).num_blocks());
292
293  // Ensure it only depends on the next node
294  EXPECT_EQ(1U, graph[1].out_edges.size());
295  EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
296}
297
298TEST_F(InplaceGeneratorTest, AssignTempBlocksReuseTest) {
299  Graph graph(9);
300
301  const vector<Extent> empt;
302  uint64_t tmp = kTempBlockStart;
303  const string kFilename = "/foo";
304
305  vector<CutEdgeVertexes> cuts;
306  cuts.resize(3);
307
308  // Simple broken loop:
309  GenVertex(
310      &graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", InstallOperation::MOVE);
311  GenVertex(&graph[1],
312            VectOfExt(tmp, 1),
313            VectOfExt(0, 1),
314            "",
315            InstallOperation::MOVE);
316  GenVertex(&graph[2],
317            VectOfExt(1, 1),
318            VectOfExt(tmp, 1),
319            "",
320            InstallOperation::MOVE);
321  // Corresponding edges:
322  graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
323  graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
324  graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
325  // Store the cut:
326  cuts[0].old_dst = 1;
327  cuts[0].old_src = 0;
328  cuts[0].new_vertex = 2;
329  cuts[0].tmp_extents = VectOfExt(tmp, 1);
330  tmp++;
331
332  // Slightly more complex pair of loops:
333  GenVertex(
334      &graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", InstallOperation::MOVE);
335  GenVertex(
336      &graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", InstallOperation::MOVE);
337  GenVertex(&graph[5],
338            VectOfExt(tmp, 3),
339            VectOfExt(4, 3),
340            kFilename,
341            InstallOperation::MOVE);
342  GenVertex(&graph[6],
343            VectOfExt(2, 2),
344            VectOfExt(tmp, 2),
345            "",
346            InstallOperation::MOVE);
347  GenVertex(&graph[7],
348            VectOfExt(7, 1),
349            VectOfExt(tmp + 2, 1),
350            "",
351            InstallOperation::MOVE);
352  // Corresponding edges:
353  graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
354  graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
355  graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
356  graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
357  graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
358  graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
359  // Store the cuts:
360  cuts[1].old_dst = 5;
361  cuts[1].old_src = 3;
362  cuts[1].new_vertex = 6;
363  cuts[1].tmp_extents = VectOfExt(tmp, 2);
364  cuts[2].old_dst = 5;
365  cuts[2].old_src = 4;
366  cuts[2].new_vertex = 7;
367  cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
368
369  // Supplier of temp block:
370  GenVertex(&graph[8], empt, VectOfExt(8, 1), "", InstallOperation::REPLACE);
371
372  // Specify the final order:
373  vector<Vertex::Index> op_indexes;
374  op_indexes.push_back(2);
375  op_indexes.push_back(0);
376  op_indexes.push_back(1);
377  op_indexes.push_back(6);
378  op_indexes.push_back(3);
379  op_indexes.push_back(7);
380  op_indexes.push_back(4);
381  op_indexes.push_back(5);
382  op_indexes.push_back(8);
383
384  vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
385  InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes,
386                                                &reverse_op_indexes);
387
388  CreateBlobFile();
389  EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph,
390                                                 "/dev/zero",
391                                                 blob_file_.get(),
392                                                 &op_indexes,
393                                                 &reverse_op_indexes,
394                                                 cuts));
395  EXPECT_FALSE(graph[6].valid);
396  EXPECT_FALSE(graph[7].valid);
397  EXPECT_EQ(1, graph[1].aop.op.src_extents_size());
398  EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).start_block());
399  EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).num_blocks());
400  EXPECT_EQ(InstallOperation::REPLACE_BZ, graph[5].aop.op.type());
401}
402
403TEST_F(InplaceGeneratorTest, MoveAndSortFullOpsToBackTest) {
404  Graph graph(4);
405  graph[0].aop.name = "A";
406  graph[0].aop.op.set_type(InstallOperation::REPLACE);
407  graph[1].aop.name = "B";
408  graph[1].aop.op.set_type(InstallOperation::BSDIFF);
409  graph[2].aop.name = "C";
410  graph[2].aop.op.set_type(InstallOperation::REPLACE_BZ);
411  graph[3].aop.name = "D";
412  graph[3].aop.op.set_type(InstallOperation::MOVE);
413
414  vector<Vertex::Index> vect(graph.size());
415
416  for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
417    vect[i] = i;
418  }
419  InplaceGenerator::MoveAndSortFullOpsToBack(&graph, &vect);
420  EXPECT_EQ(vect.size(), graph.size());
421  EXPECT_EQ(graph[vect[0]].aop.name, "B");
422  EXPECT_EQ(graph[vect[1]].aop.name, "D");
423  EXPECT_EQ(graph[vect[2]].aop.name, "A");
424  EXPECT_EQ(graph[vect[3]].aop.name, "C");
425}
426
427TEST_F(InplaceGeneratorTest, AssignTempBlocksTest) {
428  Graph graph(9);
429  const vector<Extent> empt;  // empty
430  const string kFilename = "/foo";
431
432  // Some scratch space:
433  GenVertex(&graph[0], empt, VectOfExt(200, 1), "", InstallOperation::REPLACE);
434  GenVertex(&graph[1], empt, VectOfExt(210, 10), "", InstallOperation::REPLACE);
435  GenVertex(&graph[2], empt, VectOfExt(220, 1), "", InstallOperation::REPLACE);
436
437  // A cycle that requires 10 blocks to break:
438  GenVertex(&graph[3],
439            VectOfExt(10, 11),
440            VectOfExt(0, 9),
441            "",
442            InstallOperation::BSDIFF);
443  graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
444  GenVertex(&graph[4],
445            VectOfExt(0, 9),
446            VectOfExt(10, 11),
447            "",
448            InstallOperation::BSDIFF);
449  graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
450
451  // A cycle that requires 9 blocks to break:
452  GenVertex(&graph[5],
453            VectOfExt(40, 11),
454            VectOfExt(30, 10),
455            "",
456            InstallOperation::BSDIFF);
457  graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
458  GenVertex(&graph[6],
459            VectOfExt(30, 10),
460            VectOfExt(40, 11),
461            "",
462            InstallOperation::BSDIFF);
463  graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
464
465  // A cycle that requires 40 blocks to break (which is too many):
466  GenVertex(&graph[7],
467            VectOfExt(120, 50),
468            VectOfExt(60, 40),
469            "",
470            InstallOperation::BSDIFF);
471  graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
472  GenVertex(&graph[8],
473            VectOfExt(60, 40),
474            VectOfExt(120, 50),
475            kFilename,
476            InstallOperation::BSDIFF);
477  graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
478
479  graph_utils::DumpGraph(graph);
480
481  vector<Vertex::Index> final_order;
482
483  CreateBlobFile();
484  EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
485                                                  "/dev/zero",
486                                                  blob_file_.get(),
487                                                  &final_order,
488                                                  Vertex::kInvalidIndex));
489
490  Graph expected_graph(12);
491  GenVertex(&expected_graph[0],
492            empt,
493            VectOfExt(200, 1),
494            "",
495            InstallOperation::REPLACE);
496  GenVertex(&expected_graph[1],
497            empt,
498            VectOfExt(210, 10),
499            "",
500            InstallOperation::REPLACE);
501  GenVertex(&expected_graph[2],
502            empt,
503            VectOfExt(220, 1),
504            "",
505            InstallOperation::REPLACE);
506  GenVertex(&expected_graph[3],
507            VectOfExt(10, 11),
508            VectOfExt(0, 9),
509            "",
510            InstallOperation::BSDIFF);
511  expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
512  GenVertex(&expected_graph[4],
513            VectOfExt(60, 9),
514            VectOfExt(10, 11),
515            "",
516            InstallOperation::BSDIFF);
517  expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
518  expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
519  GenVertex(&expected_graph[5],
520            VectOfExt(40, 11),
521            VectOfExt(30, 10),
522            "",
523            InstallOperation::BSDIFF);
524  expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
525
526  GenVertex(&expected_graph[6],
527            VectOfExt(60, 10),
528            VectOfExt(40, 11),
529            "",
530            InstallOperation::BSDIFF);
531  expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
532  expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
533
534  GenVertex(&expected_graph[7],
535            VectOfExt(120, 50),
536            VectOfExt(60, 40),
537            "",
538            InstallOperation::BSDIFF);
539  expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
540
541  GenVertex(&expected_graph[8],
542            empt,
543            VectOfExt(0, 50),
544            "/foo",
545            InstallOperation::REPLACE_BZ);
546  expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
547
548  GenVertex(&expected_graph[9],
549            VectOfExt(0, 9),
550            VectOfExt(60, 9),
551            "",
552            InstallOperation::MOVE);
553
554  GenVertex(&expected_graph[10],
555            VectOfExt(30, 10),
556            VectOfExt(60, 10),
557            "",
558            InstallOperation::MOVE);
559  expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
560
561  EXPECT_EQ(12U, graph.size());
562  EXPECT_FALSE(graph.back().valid);
563  for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
564    EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
565    if (i == 8) {
566      // special case
567    } else {
568      // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
569    }
570  }
571}
572
573TEST_F(InplaceGeneratorTest, CreateScratchNodeTest) {
574  Vertex vertex;
575  InplaceGenerator::CreateScratchNode(12, 34, &vertex);
576  EXPECT_EQ(InstallOperation::REPLACE_BZ, vertex.aop.op.type());
577  EXPECT_EQ(0U, vertex.aop.op.data_offset());
578  EXPECT_EQ(0U, vertex.aop.op.data_length());
579  EXPECT_EQ(1, vertex.aop.op.dst_extents_size());
580  EXPECT_EQ(12U, vertex.aop.op.dst_extents(0).start_block());
581  EXPECT_EQ(34U, vertex.aop.op.dst_extents(0).num_blocks());
582}
583
584TEST_F(InplaceGeneratorTest, ApplyMapTest) {
585  vector<uint64_t> collection = {1, 2, 3, 4, 6};
586  vector<uint64_t> expected_values = {1, 2, 5, 4, 8};
587  map<uint64_t, uint64_t> value_map;
588  value_map[3] = 5;
589  value_map[6] = 8;
590  value_map[5] = 10;
591
592  InplaceGenerator::ApplyMap(&collection, value_map);
593  EXPECT_EQ(expected_values, collection);
594}
595
596// We can't produce MOVE operations with a source or destination in the block 0.
597// This test checks that the cycle breaker procedure doesn't produce such
598// operations.
599TEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesAvoidMoveToZero) {
600  size_t block_size = 4096;
601  size_t num_blocks = 4;
602  vector<AnnotatedOperation> aops;
603
604  // Create a REPLACE_BZ for block 0, and a circular dependency among all other
605  // blocks. This situation would prefer to issue a MOVE to scratch space and
606  // the only available block is 0.
607  aops.emplace_back();
608  aops.back().name = base::StringPrintf("<bz-block-0>");
609  aops.back().op.set_type(InstallOperation::REPLACE_BZ);
610  StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents());
611
612  for (size_t i = 1; i < num_blocks; i++) {
613    AnnotatedOperation aop;
614    aop.name = base::StringPrintf("<op-%" PRIuS ">", i);
615    aop.op.set_type(InstallOperation::BSDIFF);
616    StoreExtents({ExtentForRange(1 + i % (num_blocks - 1), 1)},
617                 aop.op.mutable_src_extents());
618    StoreExtents({ExtentForRange(i, 1)}, aop.op.mutable_dst_extents());
619    aops.push_back(aop);
620  }
621
622  PartitionConfig part("part");
623  part.path = "/dev/zero";
624  part.size = num_blocks * block_size;
625
626  CreateBlobFile();
627
628  // We ran two tests here. The first one without enough blocks for the scratch
629  // space, forcing it to create a new full operation and the second case with
630  // one extra block in the partition that can be used for the move operation.
631  for (const auto part_blocks : vector<uint64_t>{num_blocks, num_blocks + 1}) {
632    SCOPED_TRACE(
633        base::StringPrintf("Using partition_blocks=%" PRIu64, part_blocks));
634    vector<AnnotatedOperation> result_aops = aops;
635    EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies(
636        part,
637        part,
638        part_blocks * block_size,
639        block_size,
640        blob_file_.get(),
641        &result_aops));
642
643    size_t full_ops = 0;
644    for (const auto& aop : result_aops) {
645      if (diff_utils::IsAReplaceOperation(aop.op.type()))
646        full_ops++;
647
648      if (aop.op.type() != InstallOperation::MOVE)
649        continue;
650      for (const Extent& extent : aop.op.src_extents()) {
651        EXPECT_NE(0U, extent.start_block())
652            << "On src extents for aop: " << aop;
653      }
654      for (const Extent& extent : aop.op.dst_extents()) {
655        EXPECT_NE(0U, extent.start_block())
656            << "On dst extents for aop: " << aop;
657      }
658    }
659
660    // If there's extra space in the partition, it should not use a new full
661    // operation for it.
662    EXPECT_EQ(part_blocks == num_blocks ? 2U : 1U, full_ops);
663
664    DumpAopsOnFailure(result_aops);
665  }
666}
667
668// Test that we can shrink a filesystem and break cycles.
669TEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesShrinkData) {
670  size_t block_size = 4096;
671  size_t old_blocks = 10;
672  size_t new_blocks = 8;
673  vector<AnnotatedOperation> aops;
674
675  // Create a loop using the blocks 1-6 and one other operation writing to the
676  // block 7 from outside the new partition. The loop in the blocks 1-6 uses
677  // two-block operations, so it needs two blocks of scratch space. It can't use
678  // the block 0 as scratch space (see previous test) and it can't use the
679  // blocks 7 or 8 due the last move operation.
680
681  aops.emplace_back();
682  aops.back().name = base::StringPrintf("<bz-block-0>");
683  aops.back().op.set_type(InstallOperation::REPLACE_BZ);
684  StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents());
685
686  const size_t num_ops = 3;
687  for (size_t i = 0; i < num_ops; i++) {
688    AnnotatedOperation aop;
689    aop.name = base::StringPrintf("<op-%" PRIuS ">", i);
690    aop.op.set_type(InstallOperation::BSDIFF);
691    StoreExtents({ExtentForRange(1 + 2 * i, 2)}, aop.op.mutable_src_extents());
692    StoreExtents({ExtentForRange(1 + 2 * ((i + 1) % num_ops), 2)},
693                 aop.op.mutable_dst_extents());
694    aops.push_back(aop);
695  }
696
697  {
698    AnnotatedOperation aop;
699    aop.name = "<op-shrink>";
700    aop.op.set_type(InstallOperation::BSDIFF);
701    StoreExtents({ExtentForRange(8, 1)}, aop.op.mutable_src_extents());
702    StoreExtents({ExtentForRange(7, 1)}, aop.op.mutable_dst_extents());
703    aops.push_back(aop);
704  }
705
706  PartitionConfig old_part("part");
707  old_part.path = "/dev/zero";
708  old_part.size = old_blocks * block_size;
709
710  PartitionConfig new_part("part");
711  new_part.path = "/dev/zero";
712  new_part.size = new_blocks * block_size;
713
714  CreateBlobFile();
715
716  EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies(
717      old_part,
718      new_part,
719      (old_blocks + 2) * block_size,  // enough scratch space.
720      block_size,
721      blob_file_.get(),
722      &aops));
723
724  size_t full_ops = 0;
725  for (const auto& aop : aops) {
726    if (diff_utils::IsAReplaceOperation(aop.op.type()))
727      full_ops++;
728  }
729  // There should be only one REPLACE* operation, the one we added for block 0.
730  EXPECT_EQ(1U, full_ops);
731
732  // There should be only one MOVE operation, the one used to break the loop
733  // which should write to scratch space past the block 7 (the last block of the
734  // new partition) which is being written later.
735  size_t move_ops = 0;
736  for (const auto& aop : aops) {
737    if (aop.op.type() == InstallOperation::MOVE) {
738      move_ops++;
739      for (const Extent& extent : aop.op.dst_extents()) {
740        EXPECT_LE(7U, extent.start_block()) << "On dst extents for aop: "
741                                            << aop;
742      }
743    }
744  }
745  EXPECT_EQ(1U, move_ops);
746
747  DumpAopsOnFailure(aops);
748}
749
750}  // namespace chromeos_update_engine
751