delta_diff_utils.cc revision a4073ef63482fd08c3678982f7d153360b088094
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 <endian.h> 20#include <ext2fs/ext2fs.h> 21 22#include <algorithm> 23#include <map> 24 25#include <base/files/file_util.h> 26#include <base/format_macros.h> 27#include <base/strings/stringprintf.h> 28 29#include "update_engine/common/hash_calculator.h" 30#include "update_engine/common/subprocess.h" 31#include "update_engine/common/utils.h" 32#include "update_engine/payload_generator/block_mapping.h" 33#include "update_engine/payload_generator/bzip.h" 34#include "update_engine/payload_generator/delta_diff_generator.h" 35#include "update_engine/payload_generator/extent_ranges.h" 36#include "update_engine/payload_generator/extent_utils.h" 37 38using std::map; 39using std::string; 40using std::vector; 41 42namespace chromeos_update_engine { 43namespace { 44 45const char* const kBsdiffPath = "bsdiff"; 46const char* const kImgdiffPath = "imgdiff"; 47 48// The maximum destination size allowed for bsdiff. In general, bsdiff should 49// work for arbitrary big files, but the payload generation and payload 50// application requires a significant amount of RAM. We put a hard-limit of 51// 200 MiB that should not affect any released board, but will limit the 52// Chrome binary in ASan builders. 53const uint64_t kMaxBsdiffDestinationSize = 200 * 1024 * 1024; // bytes 54 55// The maximum destination size allowed for imgdiff. In general, imgdiff should 56// work for arbitrary big files, but the payload application is quite memory 57// intensive, so we limit these operations to 50 MiB. 58const uint64_t kMaxImgdiffDestinationSize = 50 * 1024 * 1024; // bytes 59 60// Process a range of blocks from |range_start| to |range_end| in the extent at 61// position |*idx_p| of |extents|. If |do_remove| is true, this range will be 62// removed, which may cause the extent to be trimmed, split or removed entirely. 63// The value of |*idx_p| is updated to point to the next extent to be processed. 64// Returns true iff the next extent to process is a new or updated one. 65bool ProcessExtentBlockRange(vector<Extent>* extents, size_t* idx_p, 66 const bool do_remove, uint64_t range_start, 67 uint64_t range_end) { 68 size_t idx = *idx_p; 69 uint64_t start_block = (*extents)[idx].start_block(); 70 uint64_t num_blocks = (*extents)[idx].num_blocks(); 71 uint64_t range_size = range_end - range_start; 72 73 if (do_remove) { 74 if (range_size == num_blocks) { 75 // Remove the entire extent. 76 extents->erase(extents->begin() + idx); 77 } else if (range_end == num_blocks) { 78 // Trim the end of the extent. 79 (*extents)[idx].set_num_blocks(num_blocks - range_size); 80 idx++; 81 } else if (range_start == 0) { 82 // Trim the head of the extent. 83 (*extents)[idx].set_start_block(start_block + range_size); 84 (*extents)[idx].set_num_blocks(num_blocks - range_size); 85 } else { 86 // Trim the middle, splitting the remainder into two parts. 87 (*extents)[idx].set_num_blocks(range_start); 88 Extent e; 89 e.set_start_block(start_block + range_end); 90 e.set_num_blocks(num_blocks - range_end); 91 idx++; 92 extents->insert(extents->begin() + idx, e); 93 } 94 } else if (range_end == num_blocks) { 95 // Done with this extent. 96 idx++; 97 } else { 98 return false; 99 } 100 101 *idx_p = idx; 102 return true; 103} 104 105// Remove identical corresponding block ranges in |src_extents| and 106// |dst_extents|. Used for preventing moving of blocks onto themselves during 107// MOVE operations. The value of |total_bytes| indicates the actual length of 108// content; this may be slightly less than the total size of blocks, in which 109// case the last block is only partly occupied with data. Returns the total 110// number of bytes removed. 111size_t RemoveIdenticalBlockRanges(vector<Extent>* src_extents, 112 vector<Extent>* dst_extents, 113 const size_t total_bytes) { 114 size_t src_idx = 0; 115 size_t dst_idx = 0; 116 uint64_t src_offset = 0, dst_offset = 0; 117 bool new_src = true, new_dst = true; 118 size_t removed_bytes = 0, nonfull_block_bytes; 119 bool do_remove = false; 120 while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) { 121 if (new_src) { 122 src_offset = 0; 123 new_src = false; 124 } 125 if (new_dst) { 126 dst_offset = 0; 127 new_dst = false; 128 } 129 130 do_remove = ((*src_extents)[src_idx].start_block() + src_offset == 131 (*dst_extents)[dst_idx].start_block() + dst_offset); 132 133 uint64_t src_num_blocks = (*src_extents)[src_idx].num_blocks(); 134 uint64_t dst_num_blocks = (*dst_extents)[dst_idx].num_blocks(); 135 uint64_t min_num_blocks = std::min(src_num_blocks - src_offset, 136 dst_num_blocks - dst_offset); 137 uint64_t prev_src_offset = src_offset; 138 uint64_t prev_dst_offset = dst_offset; 139 src_offset += min_num_blocks; 140 dst_offset += min_num_blocks; 141 142 new_src = ProcessExtentBlockRange(src_extents, &src_idx, do_remove, 143 prev_src_offset, src_offset); 144 new_dst = ProcessExtentBlockRange(dst_extents, &dst_idx, do_remove, 145 prev_dst_offset, dst_offset); 146 if (do_remove) 147 removed_bytes += min_num_blocks * kBlockSize; 148 } 149 150 // If we removed the last block and this block is only partly used by file 151 // content, deduct the unused portion from the total removed byte count. 152 if (do_remove && (nonfull_block_bytes = total_bytes % kBlockSize)) 153 removed_bytes -= kBlockSize - nonfull_block_bytes; 154 155 return removed_bytes; 156} 157 158// Returns true if the given blob |data| contains gzip header magic. 159bool ContainsGZip(const brillo::Blob& data) { 160 const uint8_t kGZipMagic[] = {0x1f, 0x8b, 0x08, 0x00}; 161 return std::search(data.begin(), 162 data.end(), 163 std::begin(kGZipMagic), 164 std::end(kGZipMagic)) != data.end(); 165} 166 167} // namespace 168 169namespace diff_utils { 170 171bool DeltaReadPartition(vector<AnnotatedOperation>* aops, 172 const PartitionConfig& old_part, 173 const PartitionConfig& new_part, 174 ssize_t hard_chunk_blocks, 175 size_t soft_chunk_blocks, 176 const PayloadVersion& version, 177 BlobFileWriter* blob_file) { 178 ExtentRanges old_visited_blocks; 179 ExtentRanges new_visited_blocks; 180 181 TEST_AND_RETURN_FALSE(DeltaMovedAndZeroBlocks( 182 aops, 183 old_part.path, 184 new_part.path, 185 old_part.fs_interface ? old_part.fs_interface->GetBlockCount() : 0, 186 new_part.fs_interface->GetBlockCount(), 187 soft_chunk_blocks, 188 version, 189 blob_file, 190 &old_visited_blocks, 191 &new_visited_blocks)); 192 193 map<string, vector<Extent>> old_files_map; 194 if (old_part.fs_interface) { 195 vector<FilesystemInterface::File> old_files; 196 old_part.fs_interface->GetFiles(&old_files); 197 for (const FilesystemInterface::File& file : old_files) 198 old_files_map[file.name] = file.extents; 199 } 200 201 TEST_AND_RETURN_FALSE(new_part.fs_interface); 202 vector<FilesystemInterface::File> new_files; 203 new_part.fs_interface->GetFiles(&new_files); 204 205 // The processing is very straightforward here, we generate operations for 206 // every file (and pseudo-file such as the metadata) in the new filesystem 207 // based on the file with the same name in the old filesystem, if any. 208 // Files with overlapping data blocks (like hardlinks or filesystems with tail 209 // packing or compression where the blocks store more than one file) are only 210 // generated once in the new image, but are also used only once from the old 211 // image due to some simplifications (see below). 212 for (const FilesystemInterface::File& new_file : new_files) { 213 // Ignore the files in the new filesystem without blocks. Symlinks with 214 // data blocks (for example, symlinks bigger than 60 bytes in ext2) are 215 // handled as normal files. We also ignore blocks that were already 216 // processed by a previous file. 217 vector<Extent> new_file_extents = FilterExtentRanges( 218 new_file.extents, new_visited_blocks); 219 new_visited_blocks.AddExtents(new_file_extents); 220 221 if (new_file_extents.empty()) 222 continue; 223 224 LOG(INFO) << "Encoding file " << new_file.name << " (" 225 << BlocksInExtents(new_file_extents) << " blocks)"; 226 227 // We can't visit each dst image inode more than once, as that would 228 // duplicate work. Here, we avoid visiting each source image inode 229 // more than once. Technically, we could have multiple operations 230 // that read the same blocks from the source image for diffing, but 231 // we choose not to avoid complexity. Eventually we will move away 232 // from using a graph/cycle detection/etc to generate diffs, and at that 233 // time, it will be easy (non-complex) to have many operations read 234 // from the same source blocks. At that time, this code can die. -adlr 235 vector<Extent> old_file_extents = FilterExtentRanges( 236 old_files_map[new_file.name], old_visited_blocks); 237 old_visited_blocks.AddExtents(old_file_extents); 238 239 TEST_AND_RETURN_FALSE(DeltaReadFile(aops, 240 old_part.path, 241 new_part.path, 242 old_file_extents, 243 new_file_extents, 244 new_file.name, // operation name 245 hard_chunk_blocks, 246 version, 247 blob_file)); 248 } 249 // Process all the blocks not included in any file. We provided all the unused 250 // blocks in the old partition as available data. 251 vector<Extent> new_unvisited = { 252 ExtentForRange(0, new_part.size / kBlockSize)}; 253 new_unvisited = FilterExtentRanges(new_unvisited, new_visited_blocks); 254 if (new_unvisited.empty()) 255 return true; 256 257 vector<Extent> old_unvisited; 258 if (old_part.fs_interface) { 259 old_unvisited.push_back(ExtentForRange(0, old_part.size / kBlockSize)); 260 old_unvisited = FilterExtentRanges(old_unvisited, old_visited_blocks); 261 } 262 263 LOG(INFO) << "Scanning " << BlocksInExtents(new_unvisited) 264 << " unwritten blocks using chunk size of " 265 << soft_chunk_blocks << " blocks."; 266 // We use the soft_chunk_blocks limit for the <non-file-data> as we don't 267 // really know the structure of this data and we should not expect it to have 268 // redundancy between partitions. 269 TEST_AND_RETURN_FALSE(DeltaReadFile(aops, 270 old_part.path, 271 new_part.path, 272 old_unvisited, 273 new_unvisited, 274 "<non-file-data>", // operation name 275 soft_chunk_blocks, 276 version, 277 blob_file)); 278 279 return true; 280} 281 282bool DeltaMovedAndZeroBlocks(vector<AnnotatedOperation>* aops, 283 const string& old_part, 284 const string& new_part, 285 size_t old_num_blocks, 286 size_t new_num_blocks, 287 ssize_t chunk_blocks, 288 const PayloadVersion& version, 289 BlobFileWriter* blob_file, 290 ExtentRanges* old_visited_blocks, 291 ExtentRanges* new_visited_blocks) { 292 vector<BlockMapping::BlockId> old_block_ids; 293 vector<BlockMapping::BlockId> new_block_ids; 294 TEST_AND_RETURN_FALSE(MapPartitionBlocks(old_part, 295 new_part, 296 old_num_blocks * kBlockSize, 297 new_num_blocks * kBlockSize, 298 kBlockSize, 299 &old_block_ids, 300 &new_block_ids)); 301 302 // If the update is inplace, we map all the blocks that didn't move, 303 // regardless of the contents since they are already copied and no operation 304 // is required. 305 if (version.InplaceUpdate()) { 306 uint64_t num_blocks = std::min(old_num_blocks, new_num_blocks); 307 for (uint64_t block = 0; block < num_blocks; block++) { 308 if (old_block_ids[block] == new_block_ids[block] && 309 !old_visited_blocks->ContainsBlock(block) && 310 !new_visited_blocks->ContainsBlock(block)) { 311 old_visited_blocks->AddBlock(block); 312 new_visited_blocks->AddBlock(block); 313 } 314 } 315 } 316 317 // A mapping from the block_id to the list of block numbers with that block id 318 // in the old partition. This is used to lookup where in the old partition 319 // is a block from the new partition. 320 map<BlockMapping::BlockId, vector<uint64_t>> old_blocks_map; 321 322 for (uint64_t block = old_num_blocks; block-- > 0; ) { 323 if (old_block_ids[block] != 0 && !old_visited_blocks->ContainsBlock(block)) 324 old_blocks_map[old_block_ids[block]].push_back(block); 325 } 326 327 // The collection of blocks in the new partition with just zeros. This is a 328 // common case for free-space that's also problematic for bsdiff, so we want 329 // to optimize it using REPLACE_BZ operations. The blob for a REPLACE_BZ of 330 // just zeros is so small that it doesn't make sense to spend the I/O reading 331 // zeros from the old partition. 332 vector<Extent> new_zeros; 333 334 vector<Extent> old_identical_blocks; 335 vector<Extent> new_identical_blocks; 336 337 for (uint64_t block = 0; block < new_num_blocks; block++) { 338 // Only produce operations for blocks that were not yet visited. 339 if (new_visited_blocks->ContainsBlock(block)) 340 continue; 341 if (new_block_ids[block] == 0) { 342 AppendBlockToExtents(&new_zeros, block); 343 continue; 344 } 345 346 auto old_blocks_map_it = old_blocks_map.find(new_block_ids[block]); 347 // Check if the block exists in the old partition at all. 348 if (old_blocks_map_it == old_blocks_map.end() || 349 old_blocks_map_it->second.empty()) 350 continue; 351 352 AppendBlockToExtents(&old_identical_blocks, 353 old_blocks_map_it->second.back()); 354 AppendBlockToExtents(&new_identical_blocks, block); 355 // We can't reuse source blocks in minor version 1 because the cycle 356 // breaking algorithm used in the in-place update doesn't support that. 357 if (version.InplaceUpdate()) 358 old_blocks_map_it->second.pop_back(); 359 } 360 361 // Produce operations for the zero blocks split per output extent. 362 // TODO(deymo): Produce ZERO operations instead of calling DeltaReadFile(). 363 size_t num_ops = aops->size(); 364 new_visited_blocks->AddExtents(new_zeros); 365 for (Extent extent : new_zeros) { 366 TEST_AND_RETURN_FALSE(DeltaReadFile(aops, 367 "", 368 new_part, 369 vector<Extent>(), // old_extents 370 vector<Extent>{extent}, // new_extents 371 "<zeros>", 372 chunk_blocks, 373 version, 374 blob_file)); 375 } 376 LOG(INFO) << "Produced " << (aops->size() - num_ops) << " operations for " 377 << BlocksInExtents(new_zeros) << " zeroed blocks"; 378 379 // Produce MOVE/SOURCE_COPY operations for the moved blocks. 380 num_ops = aops->size(); 381 if (chunk_blocks == -1) 382 chunk_blocks = new_num_blocks; 383 uint64_t used_blocks = 0; 384 old_visited_blocks->AddExtents(old_identical_blocks); 385 new_visited_blocks->AddExtents(new_identical_blocks); 386 for (Extent extent : new_identical_blocks) { 387 // We split the operation at the extent boundary or when bigger than 388 // chunk_blocks. 389 for (uint64_t op_block_offset = 0; op_block_offset < extent.num_blocks(); 390 op_block_offset += chunk_blocks) { 391 aops->emplace_back(); 392 AnnotatedOperation* aop = &aops->back(); 393 aop->name = "<identical-blocks>"; 394 aop->op.set_type(version.OperationAllowed(InstallOperation::SOURCE_COPY) 395 ? InstallOperation::SOURCE_COPY 396 : InstallOperation::MOVE); 397 398 uint64_t chunk_num_blocks = 399 std::min(extent.num_blocks() - op_block_offset, 400 static_cast<uint64_t>(chunk_blocks)); 401 402 // The current operation represents the move/copy operation for the 403 // sublist starting at |used_blocks| of length |chunk_num_blocks| where 404 // the src and dst are from |old_identical_blocks| and 405 // |new_identical_blocks| respectively. 406 StoreExtents( 407 ExtentsSublist(old_identical_blocks, used_blocks, chunk_num_blocks), 408 aop->op.mutable_src_extents()); 409 410 Extent* op_dst_extent = aop->op.add_dst_extents(); 411 op_dst_extent->set_start_block(extent.start_block() + op_block_offset); 412 op_dst_extent->set_num_blocks(chunk_num_blocks); 413 CHECK( 414 vector<Extent>{*op_dst_extent} == // NOLINT(whitespace/braces) 415 ExtentsSublist(new_identical_blocks, used_blocks, chunk_num_blocks)); 416 417 used_blocks += chunk_num_blocks; 418 } 419 } 420 LOG(INFO) << "Produced " << (aops->size() - num_ops) << " operations for " 421 << used_blocks << " identical blocks moved"; 422 423 return true; 424} 425 426bool DeltaReadFile(vector<AnnotatedOperation>* aops, 427 const string& old_part, 428 const string& new_part, 429 const vector<Extent>& old_extents, 430 const vector<Extent>& new_extents, 431 const string& name, 432 ssize_t chunk_blocks, 433 const PayloadVersion& version, 434 BlobFileWriter* blob_file) { 435 brillo::Blob data; 436 InstallOperation operation; 437 438 uint64_t total_blocks = BlocksInExtents(new_extents); 439 if (chunk_blocks == -1) 440 chunk_blocks = total_blocks; 441 442 for (uint64_t block_offset = 0; block_offset < total_blocks; 443 block_offset += chunk_blocks) { 444 // Split the old/new file in the same chunks. Note that this could drop 445 // some information from the old file used for the new chunk. If the old 446 // file is smaller (or even empty when there's no old file) the chunk will 447 // also be empty. 448 vector<Extent> old_extents_chunk = ExtentsSublist( 449 old_extents, block_offset, chunk_blocks); 450 vector<Extent> new_extents_chunk = ExtentsSublist( 451 new_extents, block_offset, chunk_blocks); 452 NormalizeExtents(&old_extents_chunk); 453 NormalizeExtents(&new_extents_chunk); 454 455 TEST_AND_RETURN_FALSE(ReadExtentsToDiff(old_part, 456 new_part, 457 old_extents_chunk, 458 new_extents_chunk, 459 version, 460 &data, 461 &operation)); 462 463 // Check if the operation writes nothing. 464 if (operation.dst_extents_size() == 0) { 465 if (operation.type() == InstallOperation::MOVE) { 466 LOG(INFO) << "Empty MOVE operation (" 467 << name << "), skipping"; 468 continue; 469 } else { 470 LOG(ERROR) << "Empty non-MOVE operation"; 471 return false; 472 } 473 } 474 475 // Now, insert into the list of operations. 476 AnnotatedOperation aop; 477 aop.name = name; 478 if (static_cast<uint64_t>(chunk_blocks) < total_blocks) { 479 aop.name = base::StringPrintf("%s:%" PRIu64, 480 name.c_str(), block_offset / chunk_blocks); 481 } 482 aop.op = operation; 483 484 // Write the data 485 if (operation.type() != InstallOperation::MOVE && 486 operation.type() != InstallOperation::SOURCE_COPY) { 487 TEST_AND_RETURN_FALSE(aop.SetOperationBlob(&data, blob_file)); 488 } else { 489 TEST_AND_RETURN_FALSE(blob_file->StoreBlob(data) != -1); 490 } 491 aops->emplace_back(aop); 492 } 493 return true; 494} 495 496bool ReadExtentsToDiff(const string& old_part, 497 const string& new_part, 498 const vector<Extent>& old_extents, 499 const vector<Extent>& new_extents, 500 const PayloadVersion& version, 501 brillo::Blob* out_data, 502 InstallOperation* out_op) { 503 InstallOperation operation; 504 // Data blob that will be written to delta file. 505 const brillo::Blob* data_blob = nullptr; 506 507 // We read blocks from old_extents and write blocks to new_extents. 508 uint64_t blocks_to_read = BlocksInExtents(old_extents); 509 uint64_t blocks_to_write = BlocksInExtents(new_extents); 510 511 // Disable bsdiff and imgdiff when the data is too big. 512 bool bsdiff_allowed = 513 version.OperationAllowed(InstallOperation::SOURCE_BSDIFF) || 514 version.OperationAllowed(InstallOperation::BSDIFF); 515 if (bsdiff_allowed && 516 blocks_to_read * kBlockSize > kMaxBsdiffDestinationSize) { 517 LOG(INFO) << "bsdiff blacklisted, data too big: " 518 << blocks_to_read * kBlockSize << " bytes"; 519 bsdiff_allowed = false; 520 } 521 522 bool imgdiff_allowed = version.OperationAllowed(InstallOperation::IMGDIFF); 523 if (imgdiff_allowed && 524 blocks_to_read * kBlockSize > kMaxImgdiffDestinationSize) { 525 LOG(INFO) << "imgdiff blacklisted, data too big: " 526 << blocks_to_read * kBlockSize << " bytes"; 527 imgdiff_allowed = false; 528 } 529 530 // Make copies of the extents so we can modify them. 531 vector<Extent> src_extents = old_extents; 532 vector<Extent> dst_extents = new_extents; 533 534 // Read in bytes from new data. 535 brillo::Blob new_data; 536 TEST_AND_RETURN_FALSE(utils::ReadExtents(new_part, 537 new_extents, 538 &new_data, 539 kBlockSize * blocks_to_write, 540 kBlockSize)); 541 TEST_AND_RETURN_FALSE(!new_data.empty()); 542 543 544 // Using a REPLACE is always an option. 545 operation.set_type(InstallOperation::REPLACE); 546 data_blob = &new_data; 547 548 // Try compressing it with bzip2. 549 brillo::Blob new_data_bz; 550 TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz)); 551 CHECK(!new_data_bz.empty()); 552 if (new_data_bz.size() < data_blob->size()) { 553 // A REPLACE_BZ is better. 554 operation.set_type(InstallOperation::REPLACE_BZ); 555 data_blob = &new_data_bz; 556 } 557 558 brillo::Blob old_data; 559 brillo::Blob empty_blob; 560 brillo::Blob bsdiff_delta; 561 brillo::Blob imgdiff_delta; 562 if (blocks_to_read > 0) { 563 // Read old data. 564 TEST_AND_RETURN_FALSE( 565 utils::ReadExtents(old_part, src_extents, &old_data, 566 kBlockSize * blocks_to_read, kBlockSize)); 567 if (old_data == new_data) { 568 // No change in data. 569 operation.set_type(version.OperationAllowed(InstallOperation::SOURCE_COPY) 570 ? InstallOperation::SOURCE_COPY 571 : InstallOperation::MOVE); 572 data_blob = &empty_blob; 573 } else if (bsdiff_allowed || imgdiff_allowed) { 574 // If the source file is considered bsdiff safe (no bsdiff bugs 575 // triggered), see if BSDIFF encoding is smaller. 576 base::FilePath old_chunk; 577 TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&old_chunk)); 578 ScopedPathUnlinker old_unlinker(old_chunk.value()); 579 TEST_AND_RETURN_FALSE(utils::WriteFile( 580 old_chunk.value().c_str(), old_data.data(), old_data.size())); 581 base::FilePath new_chunk; 582 TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&new_chunk)); 583 ScopedPathUnlinker new_unlinker(new_chunk.value()); 584 TEST_AND_RETURN_FALSE(utils::WriteFile( 585 new_chunk.value().c_str(), new_data.data(), new_data.size())); 586 587 if (bsdiff_allowed) { 588 TEST_AND_RETURN_FALSE(DiffFiles( 589 kBsdiffPath, old_chunk.value(), new_chunk.value(), &bsdiff_delta)); 590 CHECK_GT(bsdiff_delta.size(), static_cast<brillo::Blob::size_type>(0)); 591 if (bsdiff_delta.size() < data_blob->size()) { 592 operation.set_type( 593 version.OperationAllowed(InstallOperation::SOURCE_BSDIFF) 594 ? InstallOperation::SOURCE_BSDIFF 595 : InstallOperation::BSDIFF); 596 data_blob = &bsdiff_delta; 597 } 598 } 599 if (imgdiff_allowed && ContainsGZip(old_data) && ContainsGZip(new_data)) { 600 // Imgdiff might fail in some cases, only use the result if it succeed, 601 // otherwise print the extents to analyze. 602 if (DiffFiles(kImgdiffPath, 603 old_chunk.value(), 604 new_chunk.value(), 605 &imgdiff_delta) && 606 imgdiff_delta.size() > 0) { 607 if (imgdiff_delta.size() < data_blob->size()) { 608 operation.set_type(InstallOperation::IMGDIFF); 609 data_blob = &imgdiff_delta; 610 } 611 } else { 612 LOG(ERROR) << "Imgdiff failed with source extents: " 613 << ExtentsToString(src_extents) 614 << ", destination extents: " 615 << ExtentsToString(dst_extents); 616 } 617 } 618 } 619 } 620 621 size_t removed_bytes = 0; 622 // Remove identical src/dst block ranges in MOVE operations. 623 if (operation.type() == InstallOperation::MOVE) { 624 removed_bytes = RemoveIdenticalBlockRanges( 625 &src_extents, &dst_extents, new_data.size()); 626 } 627 // Set legacy src_length and dst_length fields. 628 operation.set_src_length(old_data.size() - removed_bytes); 629 operation.set_dst_length(new_data.size() - removed_bytes); 630 631 // Embed extents in the operation. 632 StoreExtents(src_extents, operation.mutable_src_extents()); 633 StoreExtents(dst_extents, operation.mutable_dst_extents()); 634 635 // Replace operations should not have source extents. 636 if (operation.type() == InstallOperation::REPLACE || 637 operation.type() == InstallOperation::REPLACE_BZ) { 638 operation.clear_src_extents(); 639 operation.clear_src_length(); 640 } 641 642 *out_data = std::move(*data_blob); 643 *out_op = operation; 644 645 return true; 646} 647 648// Runs the bsdiff or imgdiff tool in |diff_path| on two files and returns the 649// resulting delta in |out|. Returns true on success. 650bool DiffFiles(const string& diff_path, 651 const string& old_file, 652 const string& new_file, 653 brillo::Blob* out) { 654 const string kPatchFile = "delta.patchXXXXXX"; 655 string patch_file_path; 656 657 TEST_AND_RETURN_FALSE( 658 utils::MakeTempFile(kPatchFile, &patch_file_path, nullptr)); 659 660 vector<string> cmd; 661 cmd.push_back(diff_path); 662 cmd.push_back(old_file); 663 cmd.push_back(new_file); 664 cmd.push_back(patch_file_path); 665 666 int rc = 1; 667 brillo::Blob patch_file; 668 string stdout; 669 TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, &stdout)); 670 if (rc != 0) { 671 LOG(ERROR) << diff_path << " returned " << rc << std::endl << stdout; 672 return false; 673 } 674 TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out)); 675 unlink(patch_file_path.c_str()); 676 return true; 677} 678 679// Returns true if |op| is a no-op operation that doesn't do any useful work 680// (e.g., a move operation that copies blocks onto themselves). 681bool IsNoopOperation(const InstallOperation& op) { 682 return (op.type() == InstallOperation::MOVE && 683 ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents())); 684} 685 686void FilterNoopOperations(vector<AnnotatedOperation>* ops) { 687 ops->erase( 688 std::remove_if( 689 ops->begin(), ops->end(), 690 [](const AnnotatedOperation& aop){return IsNoopOperation(aop.op);}), 691 ops->end()); 692} 693 694bool InitializePartitionInfo(const PartitionConfig& part, PartitionInfo* info) { 695 info->set_size(part.size); 696 HashCalculator hasher; 697 TEST_AND_RETURN_FALSE(hasher.UpdateFile(part.path, part.size) == 698 static_cast<off_t>(part.size)); 699 TEST_AND_RETURN_FALSE(hasher.Finalize()); 700 const brillo::Blob& hash = hasher.raw_hash(); 701 info->set_hash(hash.data(), hash.size()); 702 LOG(INFO) << part.path << ": size=" << part.size << " hash=" << hasher.hash(); 703 return true; 704} 705 706bool CompareAopsByDestination(AnnotatedOperation first_aop, 707 AnnotatedOperation second_aop) { 708 // We want empty operations to be at the end of the payload. 709 if (!first_aop.op.dst_extents().size() || !second_aop.op.dst_extents().size()) 710 return ((!first_aop.op.dst_extents().size()) < 711 (!second_aop.op.dst_extents().size())); 712 uint32_t first_dst_start = first_aop.op.dst_extents(0).start_block(); 713 uint32_t second_dst_start = second_aop.op.dst_extents(0).start_block(); 714 return first_dst_start < second_dst_start; 715} 716 717bool IsExtFilesystem(const string& device) { 718 brillo::Blob header; 719 // See include/linux/ext2_fs.h for more details on the structure. We obtain 720 // ext2 constants from ext2fs/ext2fs.h header but we don't link with the 721 // library. 722 if (!utils::ReadFileChunk( 723 device, 0, SUPERBLOCK_OFFSET + SUPERBLOCK_SIZE, &header) || 724 header.size() < SUPERBLOCK_OFFSET + SUPERBLOCK_SIZE) 725 return false; 726 727 const uint8_t* superblock = header.data() + SUPERBLOCK_OFFSET; 728 729 // ext3_fs.h: ext3_super_block.s_blocks_count 730 uint32_t block_count = 731 *reinterpret_cast<const uint32_t*>(superblock + 1 * sizeof(int32_t)); 732 733 // ext3_fs.h: ext3_super_block.s_log_block_size 734 uint32_t log_block_size = 735 *reinterpret_cast<const uint32_t*>(superblock + 6 * sizeof(int32_t)); 736 737 // ext3_fs.h: ext3_super_block.s_magic 738 uint16_t magic = 739 *reinterpret_cast<const uint16_t*>(superblock + 14 * sizeof(int32_t)); 740 741 block_count = le32toh(block_count); 742 log_block_size = le32toh(log_block_size) + EXT2_MIN_BLOCK_LOG_SIZE; 743 magic = le16toh(magic); 744 745 if (magic != EXT2_SUPER_MAGIC) 746 return false; 747 748 // Sanity check the parameters. 749 TEST_AND_RETURN_FALSE(log_block_size >= EXT2_MIN_BLOCK_LOG_SIZE && 750 log_block_size <= EXT2_MAX_BLOCK_LOG_SIZE); 751 TEST_AND_RETURN_FALSE(block_count > 0); 752 return true; 753} 754 755bool IsSquashfs4Filesystem(const string& device) { 756 brillo::Blob header; 757 // See fs/squashfs/squashfs_fs.h for format details. We only support 758 // Squashfs 4.x little endian. 759 760 // The first 96 is enough to read the squashfs superblock. 761 const ssize_t kSquashfsSuperBlockSize = 96; 762 if (!utils::ReadFileChunk(device, 0, kSquashfsSuperBlockSize, &header) || 763 header.size() < kSquashfsSuperBlockSize) 764 return false; 765 766 // Check magic, squashfs_fs.h: SQUASHFS_MAGIC 767 if (memcmp(header.data(), "hsqs", 4) != 0) 768 return false; // Only little endian is supported. 769 770 // squashfs_fs.h: struct squashfs_super_block.s_major 771 uint16_t s_major = *reinterpret_cast<const uint16_t*>( 772 header.data() + 5 * sizeof(uint32_t) + 4 * sizeof(uint16_t)); 773 774 if (s_major != 4) { 775 LOG(ERROR) << "Found unsupported squashfs major version " << s_major; 776 return false; 777 } 778 return true; 779} 780 781} // namespace diff_utils 782 783} // namespace chromeos_update_engine 784