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/extent_ranges.h" 37 #include "update_engine/payload_generator/graph_types.h" 38 #include "update_engine/payload_generator/graph_utils.h" 39 40 using std::map; 41 using std::set; 42 using std::string; 43 using std::stringstream; 44 using std::vector; 45 46 namespace chromeos_update_engine { 47 48 using Block = InplaceGenerator::Block; 49 50 namespace { 51 52 void 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 63 vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) { 64 return vector<Extent>(1, ExtentForRange(start_block, num_blocks)); 65 } 66 67 EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) { 68 EdgeProperties ret; 69 ret.extents = extents; 70 return ret; 71 } 72 73 EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) { 74 EdgeProperties ret; 75 ret.write_extents = extents; 76 return ret; 77 } 78 79 template<typename T> 80 void 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 89 void 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 95 void 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 103 class 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 131 TEST_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 139 TEST_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(11U, op.src_extents(0).start_block()); 157 EXPECT_EQ(1U, op.src_extents(0).num_blocks()); 158 EXPECT_EQ(13U, op.src_extents(1).start_block()); 159 EXPECT_EQ(1U, op.src_extents(1).num_blocks()); 160 EXPECT_EQ(6U, op.src_extents(2).start_block()); 161 EXPECT_EQ(1U, op.src_extents(2).num_blocks()); 162 EXPECT_EQ(kSparseHole, op.src_extents(3).start_block()); 163 EXPECT_EQ(4U, op.src_extents(3).num_blocks()); 164 EXPECT_EQ(10U, op.src_extents(4).start_block()); 165 EXPECT_EQ(1U, op.src_extents(4).num_blocks()); 166 EXPECT_EQ(14U, op.src_extents(5).start_block()); 167 EXPECT_EQ(1U, op.src_extents(5).num_blocks()); 168 EXPECT_EQ(8U, op.src_extents(6).start_block()); 169 EXPECT_EQ(2U, op.src_extents(6).num_blocks()); 170 } 171 172 TEST_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(1U, 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(3U, 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(2U, 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(2U, graph[0].aop.op.src_extents(0).num_blocks()); 253 EXPECT_EQ(7U, graph[0].aop.op.src_extents(1).start_block()); 254 EXPECT_EQ(1U, 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(1U, graph[0].aop.op.dst_extents(0).start_block()); 259 EXPECT_EQ(2U, graph[0].aop.op.dst_extents(0).num_blocks()); 260 EXPECT_EQ(4U, graph[0].aop.op.dst_extents(1).start_block()); 261 EXPECT_EQ(1U, 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(2U, 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(1U, graph[1].aop.op.src_extents(0).start_block()); 272 EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).num_blocks()); 273 EXPECT_EQ(4U, graph[1].aop.op.src_extents(1).start_block()); 274 EXPECT_EQ(1U, graph[1].aop.op.src_extents(1).num_blocks()); 275 276 EXPECT_EQ(2, graph[1].aop.op.dst_extents_size()); 277 EXPECT_EQ(3U, graph[1].aop.op.dst_extents(0).start_block()); 278 EXPECT_EQ(1U, graph[1].aop.op.dst_extents(0).num_blocks()); 279 EXPECT_EQ(5U, graph[1].aop.op.dst_extents(1).start_block()); 280 EXPECT_EQ(2U, graph[1].aop.op.dst_extents(1).num_blocks()); 281 282 // Ensure it only depends on the next node 283 EXPECT_EQ(1U, graph[1].out_edges.size()); 284 EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2)); 285 } 286 287 TEST_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(2U, graph[1].aop.op.src_extents(0).start_block()); 388 EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).num_blocks()); 389 EXPECT_EQ(InstallOperation::REPLACE_BZ, graph[5].aop.op.type()); 390 } 391 392 TEST_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 416 TEST_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(12U, 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 562 TEST_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(0U, vertex.aop.op.data_offset()); 567 EXPECT_EQ(0U, vertex.aop.op.data_length()); 568 EXPECT_EQ(1, vertex.aop.op.dst_extents_size()); 569 EXPECT_EQ(12U, vertex.aop.op.dst_extents(0).start_block()); 570 EXPECT_EQ(34U, vertex.aop.op.dst_extents(0).num_blocks()); 571 } 572 573 TEST_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. 588 TEST_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(0U, extent.start_block()) 639 << "On src extents for aop: " << aop; 640 } 641 for (const Extent& extent : aop.op.dst_extents()) { 642 EXPECT_NE(0U, extent.start_block()) 643 << "On dst extents for aop: " << aop; 644 } 645 } 646 647 // If there's extra space in the partition, it should not use a new full 648 // operation for it. 649 EXPECT_EQ(part_blocks == num_blocks ? 2U : 1U, full_ops); 650 651 if (HasNonfatalFailure()) { 652 LOG(INFO) << "Result operation list:"; 653 for (const auto& aop : result_aops) { 654 LOG(INFO) << aop; 655 } 656 } 657 } 658 } 659 660 } // namespace chromeos_update_engine 661
