delta_diff_utils_unittest.cc revision dcbc0ae6a5c48b40a1bc7d3c2ed62ec2a9fe7748
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// Squashfs example filesystem, generated with: 44// echo hola>hola 45// mksquashfs hola hola.sqfs -noappend -nopad 46// hexdump hola.sqfs -e '16/1 "%02x, " "\n"' 47const uint8_t kSquashfsFile[] = { 48 0x68, 0x73, 0x71, 0x73, 0x02, 0x00, 0x00, 0x00, // magic, inodes 49 0x3e, 0x49, 0x61, 0x54, 0x00, 0x00, 0x02, 0x00, 50 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x11, 0x00, 51 0xc0, 0x00, 0x02, 0x00, 0x04, 0x00, 0x00, 0x00, // flags, noids, major, minor 52 0x20, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // root_inode 53 0xef, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // bytes_used 54 0xe7, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 55 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 56 0x65, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 57 0x93, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 58 0xbd, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 59 0xd5, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 60 0x68, 0x6f, 0x6c, 0x61, 0x0a, 0x2c, 0x00, 0x78, 61 0xda, 0x63, 0x62, 0x58, 0xc2, 0xc8, 0xc0, 0xc0, 62 0xc8, 0xd0, 0x6b, 0x91, 0x18, 0x02, 0x64, 0xa0, 63 0x00, 0x56, 0x06, 0x90, 0xcc, 0x7f, 0xb0, 0xbc, 64 0x9d, 0x67, 0x62, 0x08, 0x13, 0x54, 0x1c, 0x44, 65 0x4b, 0x03, 0x31, 0x33, 0x10, 0x03, 0x00, 0xb5, 66 0x87, 0x04, 0x89, 0x16, 0x00, 0x78, 0xda, 0x63, 67 0x60, 0x80, 0x00, 0x46, 0x28, 0xcd, 0xc4, 0xc0, 68 0xcc, 0x90, 0x91, 0x9f, 0x93, 0x08, 0x00, 0x04, 69 0x70, 0x01, 0xab, 0x10, 0x80, 0x60, 0x00, 0x00, 70 0x00, 0x00, 0x00, 0x00, 0x00, 0x05, 0x00, 0x00, 71 0x01, 0x00, 0x00, 0x00, 0x00, 0xab, 0x00, 0x00, 72 0x00, 0x00, 0x00, 0x00, 0x00, 0x0e, 0x00, 0x78, 73 0xda, 0x63, 0x60, 0x80, 0x00, 0x05, 0x28, 0x0d, 74 0x00, 0x01, 0x10, 0x00, 0x21, 0xc5, 0x00, 0x00, 75 0x00, 0x00, 0x00, 0x00, 0x00, 0x08, 0x80, 0x99, 76 0xcd, 0x02, 0x00, 0x88, 0x13, 0x00, 0x00, 0xdd, 77 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 78}; 79 80// Writes the |data| in the blocks specified by |extents| on the partition 81// |part_path|. The |data| size could be smaller than the size of the blocks 82// passed. 83bool WriteExtents(const string& part_path, 84 const vector<Extent>& extents, 85 off_t block_size, 86 const brillo::Blob& data) { 87 uint64_t offset = 0; 88 base::ScopedFILE fp(fopen(part_path.c_str(), "r+")); 89 TEST_AND_RETURN_FALSE(fp.get()); 90 91 for (const Extent& extent : extents) { 92 if (offset >= data.size()) 93 break; 94 TEST_AND_RETURN_FALSE( 95 fseek(fp.get(), extent.start_block() * block_size, SEEK_SET) == 0); 96 uint64_t to_write = std::min(extent.num_blocks() * block_size, 97 data.size() - offset); 98 TEST_AND_RETURN_FALSE( 99 fwrite(data.data() + offset, 1, to_write, fp.get()) == to_write); 100 offset += extent.num_blocks() * block_size; 101 } 102 return true; 103} 104 105// Create a fake filesystem of the given |size| and initialize the partition 106// holding it in the PartitionConfig |part|. 107void CreatePartition(PartitionConfig* part, const string& pattern, 108 uint64_t block_size, off_t size) { 109 int fd = -1; 110 ASSERT_TRUE(utils::MakeTempFile(pattern.c_str(), &part->path, &fd)); 111 ASSERT_EQ(0, ftruncate(fd, size)); 112 ASSERT_EQ(0, close(fd)); 113 part->fs_interface.reset(new FakeFilesystem(block_size, size / block_size)); 114 part->size = size; 115} 116 117// Writes to the |partition| path blocks such they are all different and they 118// include the tag passed in |tag|, making them also different to any other 119// block on a partition initialized with this function with a different tag. 120// The |block_size| should be a divisor of the partition size. 121// Returns whether the function succeeded writing the partition. 122bool InitializePartitionWithUniqueBlocks(const PartitionConfig& part, 123 uint64_t block_size, 124 uint64_t tag) { 125 TEST_AND_RETURN_FALSE(part.size % block_size == 0); 126 size_t num_blocks = part.size / block_size; 127 brillo::Blob file_data(part.size); 128 for (size_t i = 0; i < num_blocks; ++i) { 129 string prefix = base::StringPrintf( 130 "block tag 0x%.16" PRIx64 ", block number %16" PRIuS " ", tag, i); 131 brillo::Blob block_data(prefix.begin(), prefix.end()); 132 TEST_AND_RETURN_FALSE(prefix.size() <= block_size); 133 block_data.resize(block_size, 'X'); 134 std::copy(block_data.begin(), block_data.end(), 135 file_data.begin() + i * block_size); 136 } 137 return test_utils::WriteFileVector(part.path, file_data); 138} 139 140} // namespace 141 142class DeltaDiffUtilsTest : public ::testing::Test { 143 protected: 144 const uint64_t kDefaultBlockCount = 128; 145 146 void SetUp() override { 147 CreatePartition(&old_part_, "DeltaDiffUtilsTest-old_part-XXXXXX", 148 block_size_, block_size_ * kDefaultBlockCount); 149 CreatePartition(&new_part_, "DeltaDiffUtilsTest-old_part-XXXXXX", 150 block_size_, block_size_ * kDefaultBlockCount); 151 ASSERT_TRUE(utils::MakeTempFile("DeltaDiffUtilsTest-blob-XXXXXX", 152 &blob_path_, 153 &blob_fd_)); 154 } 155 156 void TearDown() override { 157 unlink(old_part_.path.c_str()); 158 unlink(new_part_.path.c_str()); 159 if (blob_fd_ != -1) 160 close(blob_fd_); 161 unlink(blob_path_.c_str()); 162 } 163 164 // Helper function to call DeltaMovedAndZeroBlocks() using this class' data 165 // members. This simply avoid repeating all the arguments that never change. 166 bool RunDeltaMovedAndZeroBlocks(ssize_t chunk_blocks, 167 bool src_ops_allowed) { 168 BlobFileWriter blob_file(blob_fd_, &blob_size_); 169 return diff_utils::DeltaMovedAndZeroBlocks( 170 &aops_, 171 old_part_.path, 172 new_part_.path, 173 old_part_.size / block_size_, 174 new_part_.size / block_size_, 175 chunk_blocks, 176 src_ops_allowed, 177 &blob_file, 178 &old_visited_blocks_, 179 &new_visited_blocks_); 180 } 181 182 // Old and new temporary partitions used in the tests. These are initialized 183 // with 184 PartitionConfig old_part_{"part"}; 185 PartitionConfig new_part_{"part"}; 186 187 // The file holding the output blob from the various diff utils functions. 188 string blob_path_; 189 int blob_fd_{-1}; 190 off_t blob_size_{0}; 191 192 size_t block_size_{kBlockSize}; 193 194 // Default input/output arguments used when calling DeltaMovedAndZeroBlocks(). 195 vector<AnnotatedOperation> aops_; 196 ExtentRanges old_visited_blocks_; 197 ExtentRanges new_visited_blocks_; 198}; 199 200TEST_F(DeltaDiffUtilsTest, MoveSmallTest) { 201 brillo::Blob data_blob(block_size_); 202 test_utils::FillWithData(&data_blob); 203 204 // The old file is on a different block than the new one. 205 vector<Extent> old_extents = { ExtentForRange(11, 1) }; 206 vector<Extent> new_extents = { ExtentForRange(1, 1) }; 207 208 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob)); 209 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob)); 210 211 brillo::Blob data; 212 InstallOperation op; 213 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 214 old_part_.path, 215 new_part_.path, 216 old_extents, 217 new_extents, 218 true, // bsdiff_allowed 219 true, // imgdiff_allowed 220 &data, 221 &op, 222 false)); // src_ops_allowed 223 EXPECT_TRUE(data.empty()); 224 225 EXPECT_TRUE(op.has_type()); 226 EXPECT_EQ(InstallOperation::MOVE, op.type()); 227 EXPECT_FALSE(op.has_data_offset()); 228 EXPECT_FALSE(op.has_data_length()); 229 EXPECT_EQ(1, op.src_extents_size()); 230 EXPECT_EQ(kBlockSize, op.src_length()); 231 EXPECT_EQ(1, op.dst_extents_size()); 232 EXPECT_EQ(kBlockSize, op.dst_length()); 233 EXPECT_EQ(BlocksInExtents(op.src_extents()), 234 BlocksInExtents(op.dst_extents())); 235 EXPECT_EQ(1U, BlocksInExtents(op.dst_extents())); 236} 237 238TEST_F(DeltaDiffUtilsTest, MoveWithSameBlock) { 239 // Setup the old/new files so that it has immobile chunks; we make sure to 240 // utilize all sub-cases of such chunks: blocks 21--22 induce a split (src) 241 // and complete removal (dst), whereas blocks 24--25 induce trimming of the 242 // tail (src) and head (dst) of extents. The final block (29) is used for 243 // ensuring we properly account for the number of bytes removed in cases where 244 // the last block is partly filled. The detailed configuration: 245 // 246 // Old: [ 20 21 22 23 24 25 ] [ 28 29 ] 247 // New: [ 18 ] [ 21 22 ] [ 20 ] [ 24 25 26 ] [ 29 ] 248 // Same: ^^ ^^ ^^ ^^ ^^ 249 vector<Extent> old_extents = { 250 ExtentForRange(20, 6), 251 ExtentForRange(28, 2) }; 252 vector<Extent> new_extents = { 253 ExtentForRange(18, 1), 254 ExtentForRange(21, 2), 255 ExtentForRange(20, 1), 256 ExtentForRange(24, 3), 257 ExtentForRange(29, 1) }; 258 259 uint64_t num_blocks = BlocksInExtents(old_extents); 260 EXPECT_EQ(num_blocks, BlocksInExtents(new_extents)); 261 262 // The size of the data should match the total number of blocks. Each block 263 // has a different content. 264 brillo::Blob file_data; 265 for (uint64_t i = 0; i < num_blocks; ++i) { 266 file_data.resize(file_data.size() + kBlockSize, 'a' + i); 267 } 268 269 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, file_data)); 270 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, file_data)); 271 272 brillo::Blob data; 273 InstallOperation op; 274 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 275 old_part_.path, 276 new_part_.path, 277 old_extents, 278 new_extents, 279 true, // bsdiff_allowed 280 true, // imgdiff_allowed 281 &data, 282 &op, 283 false)); // src_ops_allowed 284 285 EXPECT_TRUE(data.empty()); 286 287 EXPECT_TRUE(op.has_type()); 288 EXPECT_EQ(InstallOperation::MOVE, op.type()); 289 EXPECT_FALSE(op.has_data_offset()); 290 EXPECT_FALSE(op.has_data_length()); 291 292 // The expected old and new extents that actually moved. See comment above. 293 old_extents = { 294 ExtentForRange(20, 1), 295 ExtentForRange(23, 1), 296 ExtentForRange(28, 1) }; 297 new_extents = { 298 ExtentForRange(18, 1), 299 ExtentForRange(20, 1), 300 ExtentForRange(26, 1) }; 301 num_blocks = BlocksInExtents(old_extents); 302 303 EXPECT_EQ(num_blocks * kBlockSize, op.src_length()); 304 EXPECT_EQ(num_blocks * kBlockSize, op.dst_length()); 305 306 EXPECT_EQ(old_extents.size(), static_cast<size_t>(op.src_extents_size())); 307 for (int i = 0; i < op.src_extents_size(); i++) { 308 EXPECT_EQ(old_extents[i].start_block(), op.src_extents(i).start_block()) 309 << "i == " << i; 310 EXPECT_EQ(old_extents[i].num_blocks(), op.src_extents(i).num_blocks()) 311 << "i == " << i; 312 } 313 314 EXPECT_EQ(new_extents.size(), static_cast<size_t>(op.dst_extents_size())); 315 for (int i = 0; i < op.dst_extents_size(); i++) { 316 EXPECT_EQ(new_extents[i].start_block(), op.dst_extents(i).start_block()) 317 << "i == " << i; 318 EXPECT_EQ(new_extents[i].num_blocks(), op.dst_extents(i).num_blocks()) 319 << "i == " << i; 320 } 321} 322 323TEST_F(DeltaDiffUtilsTest, BsdiffSmallTest) { 324 // Test a BSDIFF operation from block 1 to block 2. 325 brillo::Blob data_blob(kBlockSize); 326 test_utils::FillWithData(&data_blob); 327 328 // The old file is on a different block than the new one. 329 vector<Extent> old_extents = { ExtentForRange(1, 1) }; 330 vector<Extent> new_extents = { ExtentForRange(2, 1) }; 331 332 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob)); 333 // Modify one byte in the new file. 334 data_blob[0]++; 335 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob)); 336 337 brillo::Blob data; 338 InstallOperation op; 339 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 340 old_part_.path, 341 new_part_.path, 342 old_extents, 343 new_extents, 344 true, // bsdiff_allowed 345 true, // imgdiff_allowed 346 &data, 347 &op, 348 false)); // src_ops_allowed 349 350 EXPECT_FALSE(data.empty()); 351 352 EXPECT_TRUE(op.has_type()); 353 EXPECT_EQ(InstallOperation::BSDIFF, op.type()); 354 EXPECT_FALSE(op.has_data_offset()); 355 EXPECT_FALSE(op.has_data_length()); 356 EXPECT_EQ(1, op.src_extents_size()); 357 EXPECT_EQ(kBlockSize, op.src_length()); 358 EXPECT_EQ(1, op.dst_extents_size()); 359 EXPECT_EQ(kBlockSize, op.dst_length()); 360 EXPECT_EQ(BlocksInExtents(op.src_extents()), 361 BlocksInExtents(op.dst_extents())); 362 EXPECT_EQ(1U, BlocksInExtents(op.dst_extents())); 363} 364 365TEST_F(DeltaDiffUtilsTest, BsdiffNotAllowedTest) { 366 // Same setup as the previous test, but this time BSDIFF operations are not 367 // allowed. 368 brillo::Blob data_blob(kBlockSize); 369 test_utils::FillWithData(&data_blob); 370 371 // The old file is on a different block than the new one. 372 vector<Extent> old_extents = { ExtentForRange(1, 1) }; 373 vector<Extent> new_extents = { ExtentForRange(2, 1) }; 374 375 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob)); 376 // Modify one byte in the new file. 377 data_blob[0]++; 378 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob)); 379 380 brillo::Blob data; 381 InstallOperation op; 382 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 383 old_part_.path, 384 new_part_.path, 385 old_extents, 386 new_extents, 387 false, // bsdiff_allowed 388 false, // imgdiff_allowed 389 &data, 390 &op, 391 false)); // src_ops_allowed 392 393 EXPECT_FALSE(data.empty()); 394 395 // The point of this test is that we don't use BSDIFF the way the above 396 // did. The rest of the details are to be caught in other tests. 397 EXPECT_TRUE(op.has_type()); 398 EXPECT_NE(InstallOperation::BSDIFF, op.type()); 399} 400 401TEST_F(DeltaDiffUtilsTest, BsdiffNotAllowedMoveTest) { 402 brillo::Blob data_blob(kBlockSize); 403 test_utils::FillWithData(&data_blob); 404 405 // The old file is on a different block than the new one. 406 vector<Extent> old_extents = { ExtentForRange(1, 1) }; 407 vector<Extent> new_extents = { ExtentForRange(2, 1) }; 408 409 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob)); 410 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob)); 411 412 brillo::Blob data; 413 InstallOperation op; 414 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 415 old_part_.path, 416 new_part_.path, 417 old_extents, 418 new_extents, 419 false, // bsdiff_allowed 420 false, // imgdiff_allowed 421 &data, 422 &op, 423 false)); // src_ops_allowed 424 425 EXPECT_TRUE(data.empty()); 426 427 // The point of this test is that we can still use a MOVE for a file 428 // that is blacklisted. 429 EXPECT_TRUE(op.has_type()); 430 EXPECT_EQ(InstallOperation::MOVE, op.type()); 431} 432 433TEST_F(DeltaDiffUtilsTest, ReplaceSmallTest) { 434 // The old file is on a different block than the new one. 435 vector<Extent> old_extents = { ExtentForRange(1, 1) }; 436 vector<Extent> new_extents = { ExtentForRange(2, 1) }; 437 438 // Make a blob that's just 1's that will compress well. 439 brillo::Blob ones(kBlockSize, 1); 440 441 // Make a blob with random data that won't compress well. 442 brillo::Blob random_data; 443 std::mt19937 gen(12345); 444 std::uniform_int_distribution<uint8_t> dis(0, 255); 445 for (uint32_t i = 0; i < kBlockSize; i++) { 446 random_data.push_back(dis(gen)); 447 } 448 449 for (int i = 0; i < 2; i++) { 450 brillo::Blob data_to_test = i == 0 ? random_data : ones; 451 // The old_extents will be initialized with 0. 452 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, 453 data_to_test)); 454 455 brillo::Blob data; 456 InstallOperation op; 457 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 458 old_part_.path, 459 new_part_.path, 460 old_extents, 461 new_extents, 462 true, // bsdiff_allowed 463 true, // imgdiff_allowed 464 &data, 465 &op, 466 false)); // src_ops_allowed 467 EXPECT_FALSE(data.empty()); 468 469 EXPECT_TRUE(op.has_type()); 470 const InstallOperation_Type expected_type = 471 (i == 0 ? InstallOperation::REPLACE : InstallOperation::REPLACE_BZ); 472 EXPECT_EQ(expected_type, op.type()); 473 EXPECT_FALSE(op.has_data_offset()); 474 EXPECT_FALSE(op.has_data_length()); 475 EXPECT_EQ(0, op.src_extents_size()); 476 EXPECT_FALSE(op.has_src_length()); 477 EXPECT_EQ(1, op.dst_extents_size()); 478 EXPECT_EQ(data_to_test.size(), op.dst_length()); 479 EXPECT_EQ(1U, BlocksInExtents(op.dst_extents())); 480 } 481} 482 483TEST_F(DeltaDiffUtilsTest, SourceCopyTest) { 484 // Makes sure SOURCE_COPY operations are emitted whenever src_ops_allowed 485 // is true. It is the same setup as MoveSmallTest, which checks that 486 // the operation is well-formed. 487 brillo::Blob data_blob(kBlockSize); 488 test_utils::FillWithData(&data_blob); 489 490 // The old file is on a different block than the new one. 491 vector<Extent> old_extents = { ExtentForRange(11, 1) }; 492 vector<Extent> new_extents = { ExtentForRange(1, 1) }; 493 494 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob)); 495 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob)); 496 497 brillo::Blob data; 498 InstallOperation op; 499 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 500 old_part_.path, 501 new_part_.path, 502 old_extents, 503 new_extents, 504 true, // bsdiff_allowed 505 true, // imgdiff_allowed 506 &data, 507 &op, 508 true)); // src_ops_allowed 509 EXPECT_TRUE(data.empty()); 510 511 EXPECT_TRUE(op.has_type()); 512 EXPECT_EQ(InstallOperation::SOURCE_COPY, op.type()); 513} 514 515TEST_F(DeltaDiffUtilsTest, SourceBsdiffTest) { 516 // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed 517 // is true. It is the same setup as BsdiffSmallTest, which checks 518 // that the operation is well-formed. 519 brillo::Blob data_blob(kBlockSize); 520 test_utils::FillWithData(&data_blob); 521 522 // The old file is on a different block than the new one. 523 vector<Extent> old_extents = { ExtentForRange(1, 1) }; 524 vector<Extent> new_extents = { ExtentForRange(2, 1) }; 525 526 EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob)); 527 // Modify one byte in the new file. 528 data_blob[0]++; 529 EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob)); 530 531 brillo::Blob data; 532 InstallOperation op; 533 EXPECT_TRUE(diff_utils::ReadExtentsToDiff( 534 old_part_.path, 535 new_part_.path, 536 old_extents, 537 new_extents, 538 true, // bsdiff_allowed 539 true, // imgdiff_allowed 540 &data, 541 &op, 542 true)); // src_ops_allowed 543 544 EXPECT_FALSE(data.empty()); 545 EXPECT_TRUE(op.has_type()); 546 EXPECT_EQ(InstallOperation::SOURCE_BSDIFF, op.type()); 547} 548 549TEST_F(DeltaDiffUtilsTest, IsNoopOperationTest) { 550 InstallOperation op; 551 op.set_type(InstallOperation::REPLACE_BZ); 552 EXPECT_FALSE(diff_utils::IsNoopOperation(op)); 553 op.set_type(InstallOperation::MOVE); 554 EXPECT_TRUE(diff_utils::IsNoopOperation(op)); 555 *(op.add_src_extents()) = ExtentForRange(3, 2); 556 *(op.add_dst_extents()) = ExtentForRange(3, 2); 557 EXPECT_TRUE(diff_utils::IsNoopOperation(op)); 558 *(op.add_src_extents()) = ExtentForRange(7, 5); 559 *(op.add_dst_extents()) = ExtentForRange(7, 5); 560 EXPECT_TRUE(diff_utils::IsNoopOperation(op)); 561 *(op.add_src_extents()) = ExtentForRange(20, 2); 562 *(op.add_dst_extents()) = ExtentForRange(20, 1); 563 *(op.add_dst_extents()) = ExtentForRange(21, 1); 564 EXPECT_TRUE(diff_utils::IsNoopOperation(op)); 565 *(op.add_src_extents()) = ExtentForRange(24, 1); 566 *(op.add_dst_extents()) = ExtentForRange(25, 1); 567 EXPECT_FALSE(diff_utils::IsNoopOperation(op)); 568} 569 570TEST_F(DeltaDiffUtilsTest, FilterNoopOperations) { 571 AnnotatedOperation aop1; 572 aop1.op.set_type(InstallOperation::REPLACE_BZ); 573 *(aop1.op.add_dst_extents()) = ExtentForRange(3, 2); 574 aop1.name = "aop1"; 575 576 AnnotatedOperation aop2 = aop1; 577 aop2.name = "aop2"; 578 579 AnnotatedOperation noop; 580 noop.op.set_type(InstallOperation::MOVE); 581 *(noop.op.add_src_extents()) = ExtentForRange(3, 2); 582 *(noop.op.add_dst_extents()) = ExtentForRange(3, 2); 583 noop.name = "noop"; 584 585 vector<AnnotatedOperation> ops = {noop, aop1, noop, noop, aop2, noop}; 586 diff_utils::FilterNoopOperations(&ops); 587 EXPECT_EQ(2u, ops.size()); 588 EXPECT_EQ("aop1", ops[0].name); 589 EXPECT_EQ("aop2", ops[1].name); 590} 591 592// Test the simple case where all the blocks are different and no new blocks are 593// zeroed. 594TEST_F(DeltaDiffUtilsTest, NoZeroedOrUniqueBlocksDetected) { 595 InitializePartitionWithUniqueBlocks(old_part_, block_size_, 5); 596 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42); 597 598 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks 599 false)); // src_ops_allowed 600 601 EXPECT_EQ(0U, old_visited_blocks_.blocks()); 602 EXPECT_EQ(0U, new_visited_blocks_.blocks()); 603 EXPECT_EQ(0, blob_size_); 604 EXPECT_TRUE(aops_.empty()); 605} 606 607// Test that when the partitions have identical blocks in the same positions no 608// MOVE operation is performed and all the blocks are handled. 609TEST_F(DeltaDiffUtilsTest, IdenticalPartitionsDontMove) { 610 InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42); 611 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42); 612 613 // Mark some of the blocks as already visited. 614 vector<Extent> already_visited = {ExtentForRange(5, 10), 615 ExtentForRange(25, 10)}; 616 old_visited_blocks_.AddExtents(already_visited); 617 new_visited_blocks_.AddExtents(already_visited); 618 619 // Most of the blocks rest in the same place, but there's no need for MOVE 620 // operations on those blocks. 621 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks 622 false)); // src_ops_allowed 623 624 EXPECT_EQ(kDefaultBlockCount, old_visited_blocks_.blocks()); 625 EXPECT_EQ(kDefaultBlockCount, new_visited_blocks_.blocks()); 626 EXPECT_EQ(0, blob_size_); 627 EXPECT_TRUE(aops_.empty()); 628} 629 630// Test that when the partitions have identical blocks in the same positions 631// MOVE operation is performed and all the blocks are handled. 632TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedFromSource) { 633 // We use a smaller partition for this test. 634 old_part_.size = kBlockSize * 50; 635 new_part_.size = kBlockSize * 50; 636 637 InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42); 638 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42); 639 640 // Mark some of the blocks as already visited. 641 vector<Extent> already_visited = {ExtentForRange(5, 5), 642 ExtentForRange(25, 7)}; 643 old_visited_blocks_.AddExtents(already_visited); 644 new_visited_blocks_.AddExtents(already_visited); 645 646 // Override some of the old blocks with different data. 647 vector<Extent> different_blocks = {ExtentForRange(40, 5)}; 648 EXPECT_TRUE(WriteExtents(old_part_.path, different_blocks, kBlockSize, 649 brillo::Blob(5 * kBlockSize, 'a'))); 650 651 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(10, // chunk_blocks 652 true)); // src_ops_allowed 653 654 ExtentRanges expected_ranges; 655 expected_ranges.AddExtent(ExtentForRange(0, 50)); 656 expected_ranges.SubtractExtents(different_blocks); 657 658 EXPECT_EQ(expected_ranges.extent_set(), old_visited_blocks_.extent_set()); 659 EXPECT_EQ(expected_ranges.extent_set(), new_visited_blocks_.extent_set()); 660 EXPECT_EQ(0, blob_size_); 661 662 // We expect all the blocks that we didn't override with |different_blocks| 663 // and that we didn't mark as visited in |already_visited| to match and have a 664 // SOURCE_COPY operation chunked at 10 blocks. 665 vector<Extent> expected_op_extents = { 666 ExtentForRange(0, 5), 667 ExtentForRange(10, 10), 668 ExtentForRange(20, 5), 669 ExtentForRange(32, 8), 670 ExtentForRange(45, 5), 671 }; 672 673 EXPECT_EQ(expected_op_extents.size(), aops_.size()); 674 for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) { 675 SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i)); 676 const AnnotatedOperation& aop = aops_[i]; 677 EXPECT_EQ(InstallOperation::SOURCE_COPY, aop.op.type()); 678 EXPECT_EQ(1, aop.op.src_extents_size()); 679 EXPECT_EQ(expected_op_extents[i], aop.op.src_extents(0)); 680 EXPECT_EQ(1, aop.op.dst_extents_size()); 681 EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0)); 682 } 683} 684 685TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedInOder) { 686 // We use a smaller partition for this test. 687 old_part_.size = block_size_ * 50; 688 new_part_.size = block_size_ * 50; 689 690 // Create two identical partitions with 5 copies of the same unique "file". 691 brillo::Blob file_data(block_size_ * 10, 'a'); 692 for (size_t offset = 0; offset < file_data.size(); offset += block_size_) 693 file_data[offset] = 'a' + offset / block_size_; 694 695 brillo::Blob partition_data(old_part_.size); 696 for (size_t offset = 0; offset < partition_data.size(); 697 offset += file_data.size()) { 698 std::copy(file_data.begin(), file_data.end(), 699 partition_data.begin() + offset); 700 } 701 EXPECT_TRUE(test_utils::WriteFileVector(old_part_.path, partition_data)); 702 EXPECT_TRUE(test_utils::WriteFileVector(new_part_.path, partition_data)); 703 704 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks 705 true)); // src_ops_allowed 706 707 // There should be only one SOURCE_COPY, for the whole partition and the 708 // source extents should cover only the first copy of the source file since 709 // we prefer to re-read files (maybe cached) instead of continue reading the 710 // rest of the partition. 711 EXPECT_EQ(1U, aops_.size()); 712 const AnnotatedOperation& aop = aops_[0]; 713 EXPECT_EQ(InstallOperation::SOURCE_COPY, aop.op.type()); 714 EXPECT_EQ(5, aop.op.src_extents_size()); 715 for (int i = 0; i < aop.op.src_extents_size(); ++i) { 716 EXPECT_EQ(ExtentForRange(0, 10), aop.op.src_extents(i)); 717 } 718 719 EXPECT_EQ(1, aop.op.dst_extents_size()); 720 EXPECT_EQ(ExtentForRange(0, 50), aop.op.dst_extents(0)); 721 722 EXPECT_EQ(0, blob_size_); 723} 724 725// Test that all blocks with zeros are handled separately using REPLACE_BZ 726// operations unless they are not moved. 727TEST_F(DeltaDiffUtilsTest, ZeroBlocksUseReplaceBz) { 728 InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42); 729 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 5); 730 731 // We set four ranges of blocks with zeros: a single block, a range that fits 732 // in the chunk size, a range that doesn't and finally a range of zeros that 733 // was also zeros in the old image. 734 vector<Extent> new_zeros = { 735 ExtentForRange(10, 1), 736 ExtentForRange(20, 4), 737 // The last range is split since the old image has zeros in part of it. 738 ExtentForRange(30, 20), 739 }; 740 brillo::Blob zeros_data(BlocksInExtents(new_zeros) * block_size_, '\0'); 741 EXPECT_TRUE(WriteExtents(new_part_.path, new_zeros, block_size_, zeros_data)); 742 743 vector<Extent> old_zeros = vector<Extent>{ExtentForRange(43, 7)}; 744 EXPECT_TRUE(WriteExtents(old_part_.path, old_zeros, block_size_, zeros_data)); 745 746 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(5, // chunk_blocks 747 false)); // src_ops_allowed 748 749 // Zeroed blocks from old_visited_blocks_ were copied over, so me actually 750 // use them regardless of the trivial MOVE operation not being emitted. 751 EXPECT_EQ(old_zeros, 752 old_visited_blocks_.GetExtentsForBlockCount( 753 old_visited_blocks_.blocks())); 754 755 // All the new zeroed blocks should be used, part with REPLACE_BZ and part 756 // trivial MOVE operations (not included). 757 EXPECT_EQ(new_zeros, 758 new_visited_blocks_.GetExtentsForBlockCount( 759 new_visited_blocks_.blocks())); 760 761 vector<Extent> expected_op_extents = { 762 ExtentForRange(10, 1), 763 ExtentForRange(20, 4), 764 // This range should be split. 765 ExtentForRange(30, 5), 766 ExtentForRange(35, 5), 767 ExtentForRange(40, 3), 768 }; 769 770 EXPECT_EQ(expected_op_extents.size(), aops_.size()); 771 for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) { 772 SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i)); 773 const AnnotatedOperation& aop = aops_[i]; 774 EXPECT_EQ(InstallOperation::REPLACE_BZ, aop.op.type()); 775 EXPECT_EQ(0, aop.op.src_extents_size()); 776 EXPECT_EQ(1, aop.op.dst_extents_size()); 777 EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0)); 778 } 779 EXPECT_NE(0, blob_size_); 780} 781 782TEST_F(DeltaDiffUtilsTest, ShuffledBlocksAreTracked) { 783 vector<uint64_t> permutation = {0, 1, 5, 6, 7, 2, 3, 4, 9, 10, 11, 12, 8}; 784 vector<Extent> perm_extents; 785 for (uint64_t x : permutation) 786 AppendBlockToExtents(&perm_extents, x); 787 788 // We use a smaller partition for this test. 789 old_part_.size = block_size_ * permutation.size(); 790 new_part_.size = block_size_ * permutation.size(); 791 InitializePartitionWithUniqueBlocks(new_part_, block_size_, 123); 792 793 // We initialize the old_part_ with the blocks from new_part but in the 794 // |permutation| order. Block i in the old_part_ will contain the same data 795 // as block permutation[i] in the new_part_. 796 brillo::Blob new_contents; 797 EXPECT_TRUE(utils::ReadFile(new_part_.path, &new_contents)); 798 EXPECT_TRUE(WriteExtents(old_part_.path, perm_extents, block_size_, 799 new_contents)); 800 801 EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks 802 true)); // src_ops_allowed 803 804 EXPECT_EQ(permutation.size(), old_visited_blocks_.blocks()); 805 EXPECT_EQ(permutation.size(), new_visited_blocks_.blocks()); 806 807 // There should be only one SOURCE_COPY, with a complicate list of extents. 808 EXPECT_EQ(1U, aops_.size()); 809 const AnnotatedOperation& aop = aops_[0]; 810 EXPECT_EQ(InstallOperation::SOURCE_COPY, aop.op.type()); 811 vector<Extent> aop_src_extents; 812 ExtentsToVector(aop.op.src_extents(), &aop_src_extents); 813 EXPECT_EQ(perm_extents, aop_src_extents); 814 815 EXPECT_EQ(1, aop.op.dst_extents_size()); 816 EXPECT_EQ(ExtentForRange(0, permutation.size()), aop.op.dst_extents(0)); 817 818 EXPECT_EQ(0, blob_size_); 819} 820 821TEST_F(DeltaDiffUtilsTest, IsExtFilesystemTest) { 822 EXPECT_TRUE(diff_utils::IsExtFilesystem(test_utils::GetBuildArtifactsPath() 823 .Append("gen/disk_ext2_1k.img") 824 .value())); 825 EXPECT_TRUE(diff_utils::IsExtFilesystem(test_utils::GetBuildArtifactsPath() 826 .Append("gen/disk_ext2_4k.img") 827 .value())); 828} 829 830TEST_F(DeltaDiffUtilsTest, IsSquashfs4FilesystemTest) { 831 uint8_t buffer[sizeof(kSquashfsFile)]; 832 memcpy(buffer, kSquashfsFile, sizeof(kSquashfsFile)); 833 string img; 834 EXPECT_TRUE(utils::MakeTempFile("img.XXXXXX", &img, nullptr)); 835 ScopedPathUnlinker img_unlinker(img); 836 837 // Not enough bytes passed. 838 EXPECT_TRUE(utils::WriteFile(img.c_str(), buffer, 10)); 839 EXPECT_FALSE(diff_utils::IsSquashfs4Filesystem(img)); 840 841 // The whole file system is passed, which is enough for parsing. 842 EXPECT_TRUE(utils::WriteFile(img.c_str(), buffer, sizeof(kSquashfsFile))); 843 EXPECT_TRUE(diff_utils::IsSquashfs4Filesystem(img)); 844 845 // Modify the major version to 5. 846 uint16_t* s_major = reinterpret_cast<uint16_t*>(buffer + 0x1c); 847 *s_major = 5; 848 EXPECT_TRUE(utils::WriteFile(img.c_str(), buffer, sizeof(kSquashfsFile))); 849 EXPECT_FALSE(diff_utils::IsSquashfs4Filesystem(img)); 850} 851 852} // namespace chromeos_update_engine 853