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