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