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