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