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
