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