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/delta_diff_utils.h" 18 19 #include <algorithm> 20 #include <random> 21 #include <string> 22 #include <vector> 23 24 #include <base/files/scoped_file.h> 25 #include <base/format_macros.h> 26 #include <base/strings/stringprintf.h> 27 #include <gtest/gtest.h> 28 29 #include "update_engine/common/test_utils.h" 30 #include "update_engine/common/utils.h" 31 #include "update_engine/payload_generator/delta_diff_generator.h" 32 #include "update_engine/payload_generator/extent_ranges.h" 33 #include "update_engine/payload_generator/extent_utils.h" 34 #include "update_engine/payload_generator/fake_filesystem.h" 35 36 using std::string; 37 using std::vector; 38 39 namespace chromeos_update_engine { 40 41 namespace { 42 43 // Writes the |data| in the blocks specified by |extents| on the partition 44 // |part_path|. The |data| size could be smaller than the size of the blocks 45 // passed. 46 bool WriteExtents(const string& part_path, 47 const vector<Extent>& extents, 48 off_t block_size, 49 const brillo::Blob& data) { 50 uint64_t offset = 0; 51 base::ScopedFILE fp(fopen(part_path.c_str(), "r+")); 52 TEST_AND_RETURN_FALSE(fp.get()); 53 54 for (const Extent& extent : extents) { 55 if (offset >= data.size()) 56 break; 57 TEST_AND_RETURN_FALSE( 58 fseek(fp.get(), extent.start_block() * block_size, SEEK_SET) == 0); 59 uint64_t to_write = 60 std::min(static_cast<uint64_t>(extent.num_blocks()) * block_size, 61 static_cast<uint64_t>(data.size()) - offset); 62 TEST_AND_RETURN_FALSE( 63 fwrite(data.data() + offset, 1, to_write, fp.get()) == to_write); 64 offset += extent.num_blocks() * block_size; 65 } 66 return true; 67 } 68 69 // Create a fake filesystem of the given |size| and initialize the partition 70 // holding it in the PartitionConfig |part|. 71 void CreatePartition(PartitionConfig* part, const string& pattern, 72 uint64_t block_size, off_t size) { 73 int fd = -1; 74 ASSERT_TRUE(utils::MakeTempFile(pattern.c_str(), &part->path, &fd)); 75 ASSERT_EQ(0, ftruncate(fd, size)); 76 ASSERT_EQ(0, close(fd)); 77 part->fs_interface.reset(new FakeFilesystem(block_size, size / block_size)); 78 part->size = size; 79 } 80 81 // Writes to the |partition| path blocks such they are all different and they 82 // include the tag passed in |tag|, making them also different to any other 83 // block on a partition initialized with this function with a different tag. 84 // The |block_size| should be a divisor of the partition size. 85 // Returns whether the function succeeded writing the partition. 86 bool InitializePartitionWithUniqueBlocks(const PartitionConfig& part, 87 uint64_t block_size, 88 uint64_t tag) { 89 TEST_AND_RETURN_FALSE(part.size % block_size == 0); 90 size_t num_blocks = part.size / block_size; 91 brillo::Blob file_data(part.size); 92 for (size_t i = 0; i < num_blocks; ++i) { 93 string prefix = base::StringPrintf( 94 "block tag 0x%.16" PRIx64 ", block number %16" PRIuS " ", tag, i); 95 brillo::Blob block_data(prefix.begin(), prefix.end()); 96 TEST_AND_RETURN_FALSE(prefix.size() <= block_size); 97 block_data.resize(block_size, 'X'); 98 std::copy(block_data.begin(), block_data.end(), 99 file_data.begin() + i * block_size); 100 } 101 return test_utils::WriteFileVector(part.path, file_data); 102 } 103 104 } // namespace 105 106 class DeltaDiffUtilsTest : public ::testing::Test { 107 protected: 108 const uint64_t kDefaultBlockCount = 128; 109 110 void SetUp() override { 111 CreatePartition(&old_part_, "DeltaDiffUtilsTest-old_part-XXXXXX", 112 block_size_, block_size_ * kDefaultBlockCount); 113 CreatePartition(&new_part_, "DeltaDiffUtilsTest-old_part-XXXXXX", 114 block_size_, block_size_ * kDefaultBlockCount); 115 ASSERT_TRUE(utils::MakeTempFile("DeltaDiffUtilsTest-blob-XXXXXX", 116 &blob_path_, 117 &blob_fd_)); 118 } 119 120 void TearDown() override { 121 unlink(old_part_.path.c_str()); 122 unlink(new_part_.path.c_str()); 123 if (blob_fd_ != -1) 124 close(blob_fd_); 125 unlink(blob_path_.c_str()); 126 } 127 128 // Helper function to call DeltaMovedAndZeroBlocks() using this class' data 129 // members. This simply avoids repeating all the arguments that never change. 130 bool RunDeltaMovedAndZeroBlocks(ssize_t chunk_blocks, 131 uint32_t minor_version) { 132 BlobFileWriter blob_file(blob_fd_, &blob_size_); 133 PayloadVersion version(kChromeOSMajorPayloadVersion, minor_version); 134 return diff_utils::DeltaMovedAndZeroBlocks(&aops_, 135 old_part_.path, 136 new_part_.path, 137 old_part_.size / block_size_, 138 new_part_.size / block_size_, 139 chunk_blocks, 140 version, 141 &blob_file, 142 &old_visited_blocks_, 143 &new_visited_blocks_); 144 } 145 146 // Old and new temporary partitions used in the tests. These are initialized 147 // with 148 PartitionConfig old_part_{"part"}; 149 PartitionConfig new_part_{"part"}; 150 151 // The file holding the output blob from the various diff utils functions. 152 string blob_path_; 153 int blob_fd_{-1}; 154 off_t blob_size_{0}; 155 156 size_t block_size_{kBlockSize}; 157 158 // Default input/output arguments used when calling DeltaMovedAndZeroBlocks(). 159 vector<AnnotatedOperation> aops_; 160 ExtentRanges old_visited_blocks_; 161 ExtentRanges new_visited_blocks_; 162 }; 163 164 TEST_F(DeltaDiffUtilsTest, MoveSmallTest) { 165 brillo::Blob data_blob(block_size_); 166 test_utils::FillWithData(&data_blob); 167 168 // The old file is on a different block than the new one. 169 vector<Extent> old_extents = { ExtentForRange(11, 1) }; 170 vector<Extent> new_extents = { ExtentForRange(1, 1) }; 171 172 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob)); 173 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob)); 174 175 brillo::Blob data; 176 InstallOperation op; 177 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 178 old_part_.path, 179 new_part_.path, 180 old_extents, 181 new_extents, 182 {}, // old_deflates 183 {}, // new_deflates 184 PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion), 185 &data, 186 &op)); 187 EXPECT_TRUE(data.empty()); 188 189 EXPECT_TRUE(op.has_type()); 190 EXPECT_EQ(InstallOperation::MOVE, op.type()); 191 EXPECT_FALSE(op.has_data_offset()); 192 EXPECT_FALSE(op.has_data_length()); 193 EXPECT_EQ(1, op.src_extents_size()); 194 EXPECT_EQ(kBlockSize, op.src_length()); 195 EXPECT_EQ(1, op.dst_extents_size()); 196 EXPECT_EQ(kBlockSize, op.dst_length()); 197 EXPECT_EQ(utils::BlocksInExtents(op.src_extents()), 198 utils::BlocksInExtents(op.dst_extents())); 199 EXPECT_EQ(1U, utils::BlocksInExtents(op.dst_extents())); 200 } 201 202 TEST_F(DeltaDiffUtilsTest, MoveWithSameBlock) { 203 // Setup the old/new files so that it has immobile chunks; we make sure to 204 // utilize all sub-cases of such chunks: blocks 21--22 induce a split (src) 205 // and complete removal (dst), whereas blocks 24--25 induce trimming of the 206 // tail (src) and head (dst) of extents. The final block (29) is used for 207 // ensuring we properly account for the number of bytes removed in cases where 208 // the last block is partly filled. The detailed configuration: 209 // 210 // Old: [ 20 21 22 23 24 25 ] [ 28 29 ] 211 // New: [ 18 ] [ 21 22 ] [ 20 ] [ 24 25 26 ] [ 29 ] 212 // Same: ^^ ^^ ^^ ^^ ^^ 213 vector<Extent> old_extents = { 214 ExtentForRange(20, 6), 215 ExtentForRange(28, 2) }; 216 vector<Extent> new_extents = { 217 ExtentForRange(18, 1), 218 ExtentForRange(21, 2), 219 ExtentForRange(20, 1), 220 ExtentForRange(24, 3), 221 ExtentForRange(29, 1) }; 222 223 uint64_t num_blocks = utils::BlocksInExtents(old_extents); 224 EXPECT_EQ(num_blocks, utils::BlocksInExtents(new_extents)); 225 226 // The size of the data should match the total number of blocks. Each block 227 // has a different content. 228 brillo::Blob file_data; 229 for (uint64_t i = 0; i < num_blocks; ++i) { 230 file_data.resize(file_data.size() + kBlockSize, 'a' + i); 231 } 232 233 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, file_data)); 234 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, file_data)); 235 236 brillo::Blob data; 237 InstallOperation op; 238 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 239 old_part_.path, 240 new_part_.path, 241 old_extents, 242 new_extents, 243 {}, // old_deflates 244 {}, // new_deflates 245 PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion), 246 &data, 247 &op)); 248 249 EXPECT_TRUE(data.empty()); 250 251 EXPECT_TRUE(op.has_type()); 252 EXPECT_EQ(InstallOperation::MOVE, op.type()); 253 EXPECT_FALSE(op.has_data_offset()); 254 EXPECT_FALSE(op.has_data_length()); 255 256 // The expected old and new extents that actually moved. See comment above. 257 old_extents = { 258 ExtentForRange(20, 1), 259 ExtentForRange(23, 1), 260 ExtentForRange(28, 1) }; 261 new_extents = { 262 ExtentForRange(18, 1), 263 ExtentForRange(20, 1), 264 ExtentForRange(26, 1) }; 265 num_blocks = utils::BlocksInExtents(old_extents); 266 267 EXPECT_EQ(num_blocks * kBlockSize, op.src_length()); 268 EXPECT_EQ(num_blocks * kBlockSize, op.dst_length()); 269 270 EXPECT_EQ(old_extents.size(), static_cast<size_t>(op.src_extents_size())); 271 for (int i = 0; i < op.src_extents_size(); i++) { 272 EXPECT_EQ(old_extents[i].start_block(), op.src_extents(i).start_block()) 273 << "i == " << i; 274 EXPECT_EQ(old_extents[i].num_blocks(), op.src_extents(i).num_blocks()) 275 << "i == " << i; 276 } 277 278 EXPECT_EQ(new_extents.size(), static_cast<size_t>(op.dst_extents_size())); 279 for (int i = 0; i < op.dst_extents_size(); i++) { 280 EXPECT_EQ(new_extents[i].start_block(), op.dst_extents(i).start_block()) 281 << "i == " << i; 282 EXPECT_EQ(new_extents[i].num_blocks(), op.dst_extents(i).num_blocks()) 283 << "i == " << i; 284 } 285 } 286 287 TEST_F(DeltaDiffUtilsTest, BsdiffSmallTest) { 288 // Test a BSDIFF operation from block 1 to block 2. 289 brillo::Blob data_blob(kBlockSize); 290 test_utils::FillWithData(&data_blob); 291 292 // The old file is on a different block than the new one. 293 vector<Extent> old_extents = { ExtentForRange(1, 1) }; 294 vector<Extent> new_extents = { ExtentForRange(2, 1) }; 295 296 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob)); 297 // Modify one byte in the new file. 298 data_blob[0]++; 299 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob)); 300 301 brillo::Blob data; 302 InstallOperation op; 303 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 304 old_part_.path, 305 new_part_.path, 306 old_extents, 307 new_extents, 308 {}, // old_deflates 309 {}, // new_deflates 310 PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion), 311 &data, 312 &op)); 313 314 EXPECT_FALSE(data.empty()); 315 316 EXPECT_TRUE(op.has_type()); 317 EXPECT_EQ(InstallOperation::BSDIFF, op.type()); 318 EXPECT_FALSE(op.has_data_offset()); 319 EXPECT_FALSE(op.has_data_length()); 320 EXPECT_EQ(1, op.src_extents_size()); 321 EXPECT_EQ(kBlockSize, op.src_length()); 322 EXPECT_EQ(1, op.dst_extents_size()); 323 EXPECT_EQ(kBlockSize, op.dst_length()); 324 EXPECT_EQ(utils::BlocksInExtents(op.src_extents()), 325 utils::BlocksInExtents(op.dst_extents())); 326 EXPECT_EQ(1U, utils::BlocksInExtents(op.dst_extents())); 327 } 328 329 TEST_F(DeltaDiffUtilsTest, ReplaceSmallTest) { 330 // The old file is on a different block than the new one. 331 vector<Extent> old_extents = { ExtentForRange(1, 1) }; 332 vector<Extent> new_extents = { ExtentForRange(2, 1) }; 333 334 // Make a blob that's just 1's that will compress well. 335 brillo::Blob ones(kBlockSize, 1); 336 337 // Make a blob with random data that won't compress well. 338 brillo::Blob random_data; 339 std::mt19937 gen(12345); 340 std::uniform_int_distribution<uint8_t> dis(0, 255); 341 for (uint32_t i = 0; i < kBlockSize; i++) { 342 random_data.push_back(dis(gen)); 343 } 344 345 for (int i = 0; i < 2; i++) { 346 brillo::Blob data_to_test = i == 0 ? random_data : ones; 347 // The old_extents will be initialized with 0. 348 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, 349 data_to_test)); 350 351 brillo::Blob data; 352 InstallOperation op; 353 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 354 old_part_.path, 355 new_part_.path, 356 old_extents, 357 new_extents, 358 {}, // old_deflates 359 {}, // new_deflates 360 PayloadVersion(kChromeOSMajorPayloadVersion, 361 kInPlaceMinorPayloadVersion), 362 &data, 363 &op)); 364 EXPECT_FALSE(data.empty()); 365 366 EXPECT_TRUE(op.has_type()); 367 const InstallOperation_Type expected_type = 368 (i == 0 ? InstallOperation::REPLACE : InstallOperation::REPLACE_BZ); 369 EXPECT_EQ(expected_type, op.type()); 370 EXPECT_FALSE(op.has_data_offset()); 371 EXPECT_FALSE(op.has_data_length()); 372 EXPECT_EQ(0, op.src_extents_size()); 373 EXPECT_FALSE(op.has_src_length()); 374 EXPECT_EQ(1, op.dst_extents_size()); 375 EXPECT_FALSE(op.has_dst_length()); 376 EXPECT_EQ(1U, utils::BlocksInExtents(op.dst_extents())); 377 } 378 } 379 380 TEST_F(DeltaDiffUtilsTest, SourceCopyTest) { 381 // Makes sure SOURCE_COPY operations are emitted whenever src_ops_allowed 382 // is true. It is the same setup as MoveSmallTest, which checks that 383 // the operation is well-formed. 384 brillo::Blob data_blob(kBlockSize); 385 test_utils::FillWithData(&data_blob); 386 387 // The old file is on a different block than the new one. 388 vector<Extent> old_extents = { ExtentForRange(11, 1) }; 389 vector<Extent> new_extents = { ExtentForRange(1, 1) }; 390 391 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob)); 392 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob)); 393 394 brillo::Blob data; 395 InstallOperation op; 396 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 397 old_part_.path, 398 new_part_.path, 399 old_extents, 400 new_extents, 401 {}, // old_deflates 402 {}, // new_deflates 403 PayloadVersion(kChromeOSMajorPayloadVersion, kSourceMinorPayloadVersion), 404 &data, 405 &op)); 406 EXPECT_TRUE(data.empty()); 407 408 EXPECT_TRUE(op.has_type()); 409 EXPECT_EQ(InstallOperation::SOURCE_COPY, op.type()); 410 } 411 412 TEST_F(DeltaDiffUtilsTest, SourceBsdiffTest) { 413 // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed 414 // is true. It is the same setup as BsdiffSmallTest, which checks 415 // that the operation is well-formed. 416 brillo::Blob data_blob(kBlockSize); 417 test_utils::FillWithData(&data_blob); 418 419 // The old file is on a different block than the new one. 420 vector<Extent> old_extents = { ExtentForRange(1, 1) }; 421 vector<Extent> new_extents = { ExtentForRange(2, 1) }; 422 423 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob)); 424 // Modify one byte in the new file. 425 data_blob[0]++; 426 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob)); 427 428 brillo::Blob data; 429 InstallOperation op; 430 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 431 old_part_.path, 432 new_part_.path, 433 old_extents, 434 new_extents, 435 {}, // old_deflates 436 {}, // new_deflates 437 PayloadVersion(kChromeOSMajorPayloadVersion, kSourceMinorPayloadVersion), 438 &data, 439 &op)); 440 441 EXPECT_FALSE(data.empty()); 442 EXPECT_TRUE(op.has_type()); 443 EXPECT_EQ(InstallOperation::SOURCE_BSDIFF, op.type()); 444 } 445 446 TEST_F(DeltaDiffUtilsTest, IsNoopOperationTest) { 447 InstallOperation op; 448 op.set_type(InstallOperation::REPLACE_BZ); 449 EXPECT_FALSE(diff_utils::IsNoopOperation(op)); 450 op.set_type(InstallOperation::MOVE); 451 EXPECT_TRUE(diff_utils::IsNoopOperation(op)); 452 *(op.add_src_extents()) = ExtentForRange(3, 2); 453 *(op.add_dst_extents()) = ExtentForRange(3, 2); 454 EXPECT_TRUE(diff_utils::IsNoopOperation(op)); 455 *(op.add_src_extents()) = ExtentForRange(7, 5); 456 *(op.add_dst_extents()) = ExtentForRange(7, 5); 457 EXPECT_TRUE(diff_utils::IsNoopOperation(op)); 458 *(op.add_src_extents()) = ExtentForRange(20, 2); 459 *(op.add_dst_extents()) = ExtentForRange(20, 1); 460 *(op.add_dst_extents()) = ExtentForRange(21, 1); 461 EXPECT_TRUE(diff_utils::IsNoopOperation(op)); 462 *(op.add_src_extents()) = ExtentForRange(24, 1); 463 *(op.add_dst_extents()) = ExtentForRange(25, 1); 464 EXPECT_FALSE(diff_utils::IsNoopOperation(op)); 465 } 466 467 TEST_F(DeltaDiffUtilsTest, FilterNoopOperations) { 468 AnnotatedOperation aop1; 469 aop1.op.set_type(InstallOperation::REPLACE_BZ); 470 *(aop1.op.add_dst_extents()) = ExtentForRange(3, 2); 471 aop1.name = "aop1"; 472 473 AnnotatedOperation aop2 = aop1; 474 aop2.name = "aop2"; 475 476 AnnotatedOperation noop; 477 noop.op.set_type(InstallOperation::MOVE); 478 *(noop.op.add_src_extents()) = ExtentForRange(3, 2); 479 *(noop.op.add_dst_extents()) = ExtentForRange(3, 2); 480 noop.name = "noop"; 481 482 vector<AnnotatedOperation> ops = {noop, aop1, noop, noop, aop2, noop}; 483 diff_utils::FilterNoopOperations(&ops); 484 EXPECT_EQ(2u, ops.size()); 485 EXPECT_EQ("aop1", ops[0].name); 486 EXPECT_EQ("aop2", ops[1].name); 487 } 488 489 // Test the simple case where all the blocks are different and no new blocks are 490 // zeroed. 491 TEST_F(DeltaDiffUtilsTest, NoZeroedOrUniqueBlocksDetected) { 492 InitializePartitionWithUniqueBlocks(old_part_, block_size_, 5); 493 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42); 494 495 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks 496 kInPlaceMinorPayloadVersion)); 497 498 EXPECT_EQ(0U, old_visited_blocks_.blocks()); 499 EXPECT_EQ(0U, new_visited_blocks_.blocks()); 500 EXPECT_EQ(0, blob_size_); 501 EXPECT_TRUE(aops_.empty()); 502 } 503 504 // Test that when the partitions have identical blocks in the same positions no 505 // MOVE operation is performed and all the blocks are handled. 506 TEST_F(DeltaDiffUtilsTest, IdenticalPartitionsDontMove) { 507 InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42); 508 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42); 509 510 // Mark some of the blocks as already visited. 511 vector<Extent> already_visited = {ExtentForRange(5, 10), 512 ExtentForRange(25, 10)}; 513 old_visited_blocks_.AddExtents(already_visited); 514 new_visited_blocks_.AddExtents(already_visited); 515 516 // Most of the blocks rest in the same place, but there's no need for MOVE 517 // operations on those blocks. 518 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks 519 kInPlaceMinorPayloadVersion)); 520 521 EXPECT_EQ(kDefaultBlockCount, old_visited_blocks_.blocks()); 522 EXPECT_EQ(kDefaultBlockCount, new_visited_blocks_.blocks()); 523 EXPECT_EQ(0, blob_size_); 524 EXPECT_TRUE(aops_.empty()); 525 } 526 527 // Test that when the partitions have identical blocks in the same positions 528 // MOVE operation is performed and all the blocks are handled. 529 TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedFromSource) { 530 // We use a smaller partition for this test. 531 old_part_.size = kBlockSize * 50; 532 new_part_.size = kBlockSize * 50; 533 534 InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42); 535 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42); 536 537 // Mark some of the blocks as already visited. 538 vector<Extent> already_visited = {ExtentForRange(5, 5), 539 ExtentForRange(25, 7)}; 540 old_visited_blocks_.AddExtents(already_visited); 541 new_visited_blocks_.AddExtents(already_visited); 542 543 // Override some of the old blocks with different data. 544 vector<Extent> different_blocks = {ExtentForRange(40, 5)}; 545 EXPECT_TRUE(WriteExtents(old_part_.path, different_blocks, kBlockSize, 546 brillo::Blob(5 * kBlockSize, 'a'))); 547 548 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(10, // chunk_blocks 549 kSourceMinorPayloadVersion)); 550 551 ExtentRanges expected_ranges; 552 expected_ranges.AddExtent(ExtentForRange(0, 50)); 553 expected_ranges.SubtractExtents(different_blocks); 554 555 EXPECT_EQ(expected_ranges.extent_set(), old_visited_blocks_.extent_set()); 556 EXPECT_EQ(expected_ranges.extent_set(), new_visited_blocks_.extent_set()); 557 EXPECT_EQ(0, blob_size_); 558 559 // We expect all the blocks that we didn't override with |different_blocks| 560 // and that we didn't mark as visited in |already_visited| to match and have a 561 // SOURCE_COPY operation chunked at 10 blocks. 562 vector<Extent> expected_op_extents = { 563 ExtentForRange(0, 5), 564 ExtentForRange(10, 10), 565 ExtentForRange(20, 5), 566 ExtentForRange(32, 8), 567 ExtentForRange(45, 5), 568 }; 569 570 EXPECT_EQ(expected_op_extents.size(), aops_.size()); 571 for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) { 572 SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i)); 573 const AnnotatedOperation& aop = aops_[i]; 574 EXPECT_EQ(InstallOperation::SOURCE_COPY, aop.op.type()); 575 EXPECT_EQ(1, aop.op.src_extents_size()); 576 EXPECT_EQ(expected_op_extents[i], aop.op.src_extents(0)); 577 EXPECT_EQ(1, aop.op.dst_extents_size()); 578 EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0)); 579 } 580 } 581 582 TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedInOder) { 583 // We use a smaller partition for this test. 584 old_part_.size = block_size_ * 50; 585 new_part_.size = block_size_ * 50; 586 587 // Create two identical partitions with 5 copies of the same unique "file". 588 brillo::Blob file_data(block_size_ * 10, 'a'); 589 for (size_t offset = 0; offset < file_data.size(); offset += block_size_) 590 file_data[offset] = 'a' + offset / block_size_; 591 592 brillo::Blob partition_data(old_part_.size); 593 for (size_t offset = 0; offset < partition_data.size(); 594 offset += file_data.size()) { 595 std::copy(file_data.begin(), file_data.end(), 596 partition_data.begin() + offset); 597 } 598 EXPECT_TRUE(test_utils::WriteFileVector(old_part_.path, partition_data)); 599 EXPECT_TRUE(test_utils::WriteFileVector(new_part_.path, partition_data)); 600 601 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks 602 kSourceMinorPayloadVersion)); 603 604 // There should be only one SOURCE_COPY, for the whole partition and the 605 // source extents should cover only the first copy of the source file since 606 // we prefer to re-read files (maybe cached) instead of continue reading the 607 // rest of the partition. 608 EXPECT_EQ(1U, aops_.size()); 609 const AnnotatedOperation& aop = aops_[0]; 610 EXPECT_EQ(InstallOperation::SOURCE_COPY, aop.op.type()); 611 EXPECT_EQ(5, aop.op.src_extents_size()); 612 for (int i = 0; i < aop.op.src_extents_size(); ++i) { 613 EXPECT_EQ(ExtentForRange(0, 10), aop.op.src_extents(i)); 614 } 615 616 EXPECT_EQ(1, aop.op.dst_extents_size()); 617 EXPECT_EQ(ExtentForRange(0, 50), aop.op.dst_extents(0)); 618 619 EXPECT_EQ(0, blob_size_); 620 } 621 622 // Test that all blocks with zeros are handled separately using REPLACE_BZ 623 // operations unless they are not moved. 624 TEST_F(DeltaDiffUtilsTest, ZeroBlocksUseReplaceBz) { 625 InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42); 626 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 5); 627 628 // We set four ranges of blocks with zeros: a single block, a range that fits 629 // in the chunk size, a range that doesn't and finally a range of zeros that 630 // was also zeros in the old image. 631 vector<Extent> new_zeros = { 632 ExtentForRange(10, 1), 633 ExtentForRange(20, 4), 634 // The last range is split since the old image has zeros in part of it. 635 ExtentForRange(30, 20), 636 }; 637 brillo::Blob zeros_data(utils::BlocksInExtents(new_zeros) * block_size_, 638 '\0'); 639 EXPECT_TRUE(WriteExtents(new_part_.path, new_zeros, block_size_, zeros_data)); 640 641 vector<Extent> old_zeros = vector<Extent>{ExtentForRange(43, 7)}; 642 EXPECT_TRUE(WriteExtents(old_part_.path, old_zeros, block_size_, zeros_data)); 643 644 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(5, // chunk_blocks 645 kInPlaceMinorPayloadVersion)); 646 647 // Zeroed blocks from old_visited_blocks_ were copied over, so me actually 648 // use them regardless of the trivial MOVE operation not being emitted. 649 EXPECT_EQ(old_zeros, 650 old_visited_blocks_.GetExtentsForBlockCount( 651 old_visited_blocks_.blocks())); 652 653 // All the new zeroed blocks should be used, part with REPLACE_BZ and part 654 // trivial MOVE operations (not included). 655 EXPECT_EQ(new_zeros, 656 new_visited_blocks_.GetExtentsForBlockCount( 657 new_visited_blocks_.blocks())); 658 659 vector<Extent> expected_op_extents = { 660 ExtentForRange(10, 1), 661 ExtentForRange(20, 4), 662 // This range should be split. 663 ExtentForRange(30, 5), 664 ExtentForRange(35, 5), 665 ExtentForRange(40, 3), 666 }; 667 668 EXPECT_EQ(expected_op_extents.size(), aops_.size()); 669 for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) { 670 SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i)); 671 const AnnotatedOperation& aop = aops_[i]; 672 EXPECT_EQ(InstallOperation::REPLACE_BZ, aop.op.type()); 673 EXPECT_EQ(0, aop.op.src_extents_size()); 674 EXPECT_EQ(1, aop.op.dst_extents_size()); 675 EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0)); 676 } 677 EXPECT_NE(0, blob_size_); 678 } 679 680 TEST_F(DeltaDiffUtilsTest, ShuffledBlocksAreTracked) { 681 vector<uint64_t> permutation = {0, 1, 5, 6, 7, 2, 3, 4, 9, 10, 11, 12, 8}; 682 vector<Extent> perm_extents; 683 for (uint64_t x : permutation) 684 AppendBlockToExtents(&perm_extents, x); 685 686 // We use a smaller partition for this test. 687 old_part_.size = block_size_ * permutation.size(); 688 new_part_.size = block_size_ * permutation.size(); 689 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 123); 690 691 // We initialize the old_part_ with the blocks from new_part but in the 692 // |permutation| order. Block i in the old_part_ will contain the same data 693 // as block permutation[i] in the new_part_. 694 brillo::Blob new_contents; 695 EXPECT_TRUE(utils::ReadFile(new_part_.path, &new_contents)); 696 EXPECT_TRUE(WriteExtents(old_part_.path, perm_extents, block_size_, 697 new_contents)); 698 699 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks 700 kSourceMinorPayloadVersion)); 701 702 EXPECT_EQ(permutation.size(), old_visited_blocks_.blocks()); 703 EXPECT_EQ(permutation.size(), new_visited_blocks_.blocks()); 704 705 // There should be only one SOURCE_COPY, with a complicate list of extents. 706 EXPECT_EQ(1U, aops_.size()); 707 const AnnotatedOperation& aop = aops_[0]; 708 EXPECT_EQ(InstallOperation::SOURCE_COPY, aop.op.type()); 709 vector<Extent> aop_src_extents; 710 ExtentsToVector(aop.op.src_extents(), &aop_src_extents); 711 EXPECT_EQ(perm_extents, aop_src_extents); 712 713 EXPECT_EQ(1, aop.op.dst_extents_size()); 714 EXPECT_EQ(ExtentForRange(0, permutation.size()), aop.op.dst_extents(0)); 715 716 EXPECT_EQ(0, blob_size_); 717 } 718 719 TEST_F(DeltaDiffUtilsTest, IsExtFilesystemTest) { 720 EXPECT_TRUE(diff_utils::IsExtFilesystem( 721 test_utils::GetBuildArtifactsPath("gen/disk_ext2_1k.img"))); 722 EXPECT_TRUE(diff_utils::IsExtFilesystem( 723 test_utils::GetBuildArtifactsPath("gen/disk_ext2_4k.img"))); 724 } 725 726 } // namespace chromeos_update_engine 727
