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