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