Home | History | Annotate | Download | only in payload_generator
      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 
     41 using std::map;
     42 using std::set;
     43 using std::string;
     44 using std::stringstream;
     45 using std::vector;
     46 
     47 namespace chromeos_update_engine {
     48 
     49 using Block = InplaceGenerator::Block;
     50 
     51 namespace {
     52 
     53 void 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 
     64 vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
     65   return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
     66 }
     67 
     68 EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
     69   EdgeProperties ret;
     70   ret.extents = extents;
     71   return ret;
     72 }
     73 
     74 EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
     75   EdgeProperties ret;
     76   ret.write_extents = extents;
     77   return ret;
     78 }
     79 
     80 template<typename T>
     81 void 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 
     90 void 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 
     96 void 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 
    104 class 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 
    142 TEST_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 
    150 TEST_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 
    183 TEST_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 
    298 TEST_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 
    403 TEST_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 
    427 TEST_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 
    573 TEST_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 
    584 TEST_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.
    599 TEST_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.
    669 TEST_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