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