delta_diff_generator.cc revision 1beda780333ce51d7872603b70712772eb2383fb
1// Copyright (c) 2012 The Chromium OS Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include "update_engine/payload_generator/delta_diff_generator.h" 6 7#include <errno.h> 8#include <fcntl.h> 9#include <inttypes.h> 10#include <sys/stat.h> 11#include <sys/types.h> 12 13#include <algorithm> 14#include <map> 15#include <memory> 16#include <string> 17#include <utility> 18#include <vector> 19 20#include <base/files/file_path.h> 21#include <base/files/file_util.h> 22#include <base/logging.h> 23#include <base/strings/stringprintf.h> 24#include <base/strings/string_util.h> 25#include <bzlib.h> 26#include <chromeos/secure_blob.h> 27 28#include "update_engine/bzip.h" 29#include "update_engine/delta_performer.h" 30#include "update_engine/file_writer.h" 31#include "update_engine/omaha_hash_calculator.h" 32#include "update_engine/payload_constants.h" 33#include "update_engine/payload_generator/ext2_filesystem.h" 34#include "update_engine/payload_generator/extent_ranges.h" 35#include "update_engine/payload_generator/full_update_generator.h" 36#include "update_engine/payload_generator/inplace_generator.h" 37#include "update_engine/payload_generator/payload_signer.h" 38#include "update_engine/payload_generator/raw_filesystem.h" 39#include "update_engine/payload_verifier.h" 40#include "update_engine/subprocess.h" 41#include "update_engine/update_metadata.pb.h" 42#include "update_engine/utils.h" 43 44using std::map; 45using std::set; 46using std::sort; 47using std::string; 48using std::unique_ptr; 49using std::vector; 50 51namespace { 52 53const uint64_t kMajorVersionNumber = 1; 54 55// The maximum destination size allowed for bsdiff. In general, bsdiff should 56// work for arbitrary big files, but the payload generation and payload 57// application requires a significant amount of RAM. We put a hard-limit of 58// 200 MiB that should not affect any released board, but will limit the 59// Chrome binary in ASan builders. 60const uint64_t kMaxBsdiffDestinationSize = 200 * 1024 * 1024; // bytes 61 62static const char* kInstallOperationTypes[] = { 63 "REPLACE", 64 "REPLACE_BZ", 65 "MOVE", 66 "BSDIFF", 67 "SOURCE_COPY", 68 "SOURCE_BSDIFF" 69}; 70 71} // namespace 72 73namespace chromeos_update_engine { 74 75typedef map<const DeltaArchiveManifest_InstallOperation*, 76 string> OperationNameMap; 77 78// bytes 79const size_t kRootFSPartitionSize = static_cast<size_t>(2) * 1024 * 1024 * 1024; 80const size_t kBlockSize = 4096; // bytes 81const char* const kEmptyPath = ""; 82const char* const kBsdiffPath = "bsdiff"; 83 84namespace { 85 86// Writes the uint64_t passed in in host-endian to the file as big-endian. 87// Returns true on success. 88bool WriteUint64AsBigEndian(FileWriter* writer, const uint64_t value) { 89 uint64_t value_be = htobe64(value); 90 TEST_AND_RETURN_FALSE(writer->Write(&value_be, sizeof(value_be))); 91 return true; 92} 93 94// Adds each operation from |rootfs_ops| and |kernel_ops| to |out_manifest| in 95// the order they come in those vectors. reports the operations names 96void InstallOperationsToManifest( 97 const vector<AnnotatedOperation>& rootfs_ops, 98 const vector<AnnotatedOperation>& kernel_ops, 99 DeltaArchiveManifest* out_manifest, 100 OperationNameMap* out_op_name_map) { 101 for (const AnnotatedOperation& aop : rootfs_ops) { 102 if (DeltaDiffGenerator::IsNoopOperation(aop.op)) 103 continue; 104 DeltaArchiveManifest_InstallOperation* new_op = 105 out_manifest->add_install_operations(); 106 (*out_op_name_map)[new_op] = aop.name; 107 *new_op = aop.op; 108 } 109 for (const AnnotatedOperation& aop : kernel_ops) { 110 if (DeltaDiffGenerator::IsNoopOperation(aop.op)) 111 continue; 112 DeltaArchiveManifest_InstallOperation* new_op = 113 out_manifest->add_kernel_install_operations(); 114 (*out_op_name_map)[new_op] = aop.name; 115 *new_op = aop.op; 116 } 117} 118 119struct DeltaObject { 120 DeltaObject(const string& in_name, const int in_type, const off_t in_size) 121 : name(in_name), 122 type(in_type), 123 size(in_size) {} 124 bool operator <(const DeltaObject& object) const { 125 return (size != object.size) ? (size < object.size) : (name < object.name); 126 } 127 string name; 128 int type; 129 off_t size; 130}; 131 132void ReportPayloadUsage(const DeltaArchiveManifest& manifest, 133 const int64_t manifest_metadata_size, 134 const OperationNameMap& op_name_map) { 135 vector<DeltaObject> objects; 136 off_t total_size = 0; 137 138 // Rootfs install operations. 139 for (int i = 0; i < manifest.install_operations_size(); ++i) { 140 const DeltaArchiveManifest_InstallOperation& op = 141 manifest.install_operations(i); 142 objects.push_back(DeltaObject(op_name_map.find(&op)->second, 143 op.type(), 144 op.data_length())); 145 total_size += op.data_length(); 146 } 147 148 // Kernel install operations. 149 for (int i = 0; i < manifest.kernel_install_operations_size(); ++i) { 150 const DeltaArchiveManifest_InstallOperation& op = 151 manifest.kernel_install_operations(i); 152 objects.push_back(DeltaObject(base::StringPrintf("<kernel-operation-%d>", 153 i), 154 op.type(), 155 op.data_length())); 156 total_size += op.data_length(); 157 } 158 159 objects.push_back(DeltaObject("<manifest-metadata>", 160 -1, 161 manifest_metadata_size)); 162 total_size += manifest_metadata_size; 163 164 sort(objects.begin(), objects.end()); 165 166 static const char kFormatString[] = "%6.2f%% %10jd %-10s %s\n"; 167 for (const DeltaObject& object : objects) { 168 fprintf(stderr, kFormatString, 169 object.size * 100.0 / total_size, 170 static_cast<intmax_t>(object.size), 171 object.type >= 0 ? kInstallOperationTypes[object.type] : "-", 172 object.name.c_str()); 173 } 174 fprintf(stderr, kFormatString, 175 100.0, static_cast<intmax_t>(total_size), "", "<total>"); 176} 177 178// Process a range of blocks from |range_start| to |range_end| in the extent at 179// position |*idx_p| of |extents|. If |do_remove| is true, this range will be 180// removed, which may cause the extent to be trimmed, split or removed entirely. 181// The value of |*idx_p| is updated to point to the next extent to be processed. 182// Returns true iff the next extent to process is a new or updated one. 183bool ProcessExtentBlockRange(vector<Extent>* extents, size_t* idx_p, 184 const bool do_remove, uint64_t range_start, 185 uint64_t range_end) { 186 size_t idx = *idx_p; 187 uint64_t start_block = (*extents)[idx].start_block(); 188 uint64_t num_blocks = (*extents)[idx].num_blocks(); 189 uint64_t range_size = range_end - range_start; 190 191 if (do_remove) { 192 if (range_size == num_blocks) { 193 // Remove the entire extent. 194 extents->erase(extents->begin() + idx); 195 } else if (range_end == num_blocks) { 196 // Trim the end of the extent. 197 (*extents)[idx].set_num_blocks(num_blocks - range_size); 198 idx++; 199 } else if (range_start == 0) { 200 // Trim the head of the extent. 201 (*extents)[idx].set_start_block(start_block + range_size); 202 (*extents)[idx].set_num_blocks(num_blocks - range_size); 203 } else { 204 // Trim the middle, splitting the remainder into two parts. 205 (*extents)[idx].set_num_blocks(range_start); 206 Extent e; 207 e.set_start_block(start_block + range_end); 208 e.set_num_blocks(num_blocks - range_end); 209 idx++; 210 extents->insert(extents->begin() + idx, e); 211 } 212 } else if (range_end == num_blocks) { 213 // Done with this extent. 214 idx++; 215 } else { 216 return false; 217 } 218 219 *idx_p = idx; 220 return true; 221} 222 223// Remove identical corresponding block ranges in |src_extents| and 224// |dst_extents|. Used for preventing moving of blocks onto themselves during 225// MOVE operations. The value of |total_bytes| indicates the actual length of 226// content; this may be slightly less than the total size of blocks, in which 227// case the last block is only partly occupied with data. Returns the total 228// number of bytes removed. 229size_t RemoveIdenticalBlockRanges(vector<Extent>* src_extents, 230 vector<Extent>* dst_extents, 231 const size_t total_bytes) { 232 size_t src_idx = 0; 233 size_t dst_idx = 0; 234 uint64_t src_offset = 0, dst_offset = 0; 235 bool new_src = true, new_dst = true; 236 size_t removed_bytes = 0, nonfull_block_bytes; 237 bool do_remove = false; 238 while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) { 239 if (new_src) { 240 src_offset = 0; 241 new_src = false; 242 } 243 if (new_dst) { 244 dst_offset = 0; 245 new_dst = false; 246 } 247 248 do_remove = ((*src_extents)[src_idx].start_block() + src_offset == 249 (*dst_extents)[dst_idx].start_block() + dst_offset); 250 251 uint64_t src_num_blocks = (*src_extents)[src_idx].num_blocks(); 252 uint64_t dst_num_blocks = (*dst_extents)[dst_idx].num_blocks(); 253 uint64_t min_num_blocks = std::min(src_num_blocks - src_offset, 254 dst_num_blocks - dst_offset); 255 uint64_t prev_src_offset = src_offset; 256 uint64_t prev_dst_offset = dst_offset; 257 src_offset += min_num_blocks; 258 dst_offset += min_num_blocks; 259 260 new_src = ProcessExtentBlockRange(src_extents, &src_idx, do_remove, 261 prev_src_offset, src_offset); 262 new_dst = ProcessExtentBlockRange(dst_extents, &dst_idx, do_remove, 263 prev_dst_offset, dst_offset); 264 if (do_remove) 265 removed_bytes += min_num_blocks * kBlockSize; 266 } 267 268 // If we removed the last block and this block is only partly used by file 269 // content, deduct the unused portion from the total removed byte count. 270 if (do_remove && (nonfull_block_bytes = total_bytes % kBlockSize)) 271 removed_bytes -= kBlockSize - nonfull_block_bytes; 272 273 return removed_bytes; 274} 275 276// Compare two AnnotatedOperations by the start block of the first Extent in 277// their destination extents. 278bool CompareAopsByDestination(AnnotatedOperation first_aop, 279 AnnotatedOperation second_aop) { 280 // We want empty operations to be at the end of the payload. 281 if (!first_aop.op.dst_extents().size() || !second_aop.op.dst_extents().size()) 282 return ((!first_aop.op.dst_extents().size()) < 283 (!second_aop.op.dst_extents().size())); 284 uint32_t first_dst_start = first_aop.op.dst_extents(0).start_block(); 285 uint32_t second_dst_start = second_aop.op.dst_extents(0).start_block(); 286 return first_dst_start < second_dst_start; 287} 288 289} // namespace 290 291bool DeltaDiffGenerator::DeltaReadFilesystem( 292 vector<AnnotatedOperation>* aops, 293 const string& old_part, 294 const string& new_part, 295 FilesystemInterface* old_fs, 296 FilesystemInterface* new_fs, 297 off_t chunk_blocks, 298 int data_fd, 299 off_t* data_file_size, 300 bool src_ops_allowed) { 301 ExtentRanges old_visited_blocks; 302 ExtentRanges new_visited_blocks; 303 304 map<string, vector<Extent>> old_files_map; 305 if (old_fs) { 306 vector<FilesystemInterface::File> old_files; 307 old_fs->GetFiles(&old_files); 308 for (const FilesystemInterface::File& file : old_files) 309 old_files_map[file.name] = file.extents; 310 } 311 312 vector<FilesystemInterface::File> new_files; 313 new_fs->GetFiles(&new_files); 314 315 // The processing is very straightforward here, we generate operations for 316 // every file (and pseudo-file such as the metadata) in the new filesystem 317 // based on the file with the same name in the old filesystem, if any. 318 // Files with overlapping data blocks (like hardlinks or filesystems with tail 319 // packing or compression where the blocks store more than one file) are only 320 // generated once in the new image, but are also used only once from the old 321 // image due to some simplifications (see below). 322 for (const FilesystemInterface::File& new_file : new_files) { 323 // Ignore the files in the new filesystem without blocks. Symlinks with 324 // data blocks (for example, symlinks bigger than 60 bytes in ext2) are 325 // handled as normal files. We also ignore blocks that were already 326 // processed by a previous file. 327 vector<Extent> new_file_extents = FilterExtentRanges( 328 new_file.extents, new_visited_blocks); 329 new_visited_blocks.AddExtents(new_file_extents); 330 331 if (new_file_extents.empty()) 332 continue; 333 334 LOG(INFO) << "Encoding file " << new_file.name << " (" 335 << BlocksInExtents(new_file_extents) << " blocks)"; 336 337 // We can't visit each dst image inode more than once, as that would 338 // duplicate work. Here, we avoid visiting each source image inode 339 // more than once. Technically, we could have multiple operations 340 // that read the same blocks from the source image for diffing, but 341 // we choose not to avoid complexity. Eventually we will move away 342 // from using a graph/cycle detection/etc to generate diffs, and at that 343 // time, it will be easy (non-complex) to have many operations read 344 // from the same source blocks. At that time, this code can die. -adlr 345 vector<Extent> old_file_extents = FilterExtentRanges( 346 old_files_map[new_file.name], old_visited_blocks); 347 old_visited_blocks.AddExtents(old_file_extents); 348 349 TEST_AND_RETURN_FALSE(DeltaReadFile( 350 aops, 351 old_part, 352 new_part, 353 old_file_extents, 354 new_file_extents, 355 new_file.name, // operation name 356 chunk_blocks, 357 data_fd, 358 data_file_size, 359 src_ops_allowed)); 360 } 361 // Process all the blocks not included in any file. We provided all the unused 362 // blocks in the old partition as available data. 363 vector<Extent> new_unvisited = { ExtentForRange(0, new_fs->GetBlockCount()) }; 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_fs) { 370 old_unvisited.push_back(ExtentForRange(0, old_fs->GetBlockCount())); 371 old_unvisited = FilterExtentRanges(old_unvisited, old_visited_blocks); 372 } 373 374 LOG(INFO) << "Scanning " << BlocksInExtents(new_unvisited) 375 << " unwritten blocks"; 376 TEST_AND_RETURN_FALSE(DeltaReadFile( 377 aops, 378 old_part, 379 new_part, 380 old_unvisited, 381 new_unvisited, 382 "<non-file-data>", // operation name 383 chunk_blocks, 384 data_fd, 385 data_file_size, 386 src_ops_allowed)); 387 388 return true; 389} 390 391bool DeltaDiffGenerator::DeltaReadFile( 392 vector<AnnotatedOperation>* aops, 393 const string& old_part, 394 const string& new_part, 395 const vector<Extent>& old_extents, 396 const vector<Extent>& new_extents, 397 const string& name, 398 off_t chunk_blocks, 399 int data_fd, 400 off_t* data_file_size, 401 bool src_ops_allowed) { 402 chromeos::Blob data; 403 DeltaArchiveManifest_InstallOperation operation; 404 405 uint64_t total_blocks = BlocksInExtents(new_extents); 406 if (chunk_blocks == -1) 407 chunk_blocks = total_blocks; 408 409 // If bsdiff breaks again, blacklist the problem file by using: 410 // bsdiff_allowed = (name != "/foo/bar") 411 // 412 // TODO(dgarrett): chromium-os:15274 connect this test to the command line. 413 bool bsdiff_allowed = true; 414 if (static_cast<uint64_t>(chunk_blocks) * kBlockSize > 415 kMaxBsdiffDestinationSize) { 416 bsdiff_allowed = false; 417 } 418 419 if (!bsdiff_allowed) { 420 LOG(INFO) << "bsdiff blacklisting: " << name; 421 } 422 423 for (uint64_t block_offset = 0; block_offset < total_blocks; 424 block_offset += chunk_blocks) { 425 // Split the old/new file in the same chunks. Note that this could drop 426 // some information from the old file used for the new chunk. If the old 427 // file is smaller (or even empty when there's no old file) the chunk will 428 // also be empty. 429 vector<Extent> old_extents_chunk = ExtentsSublist( 430 old_extents, block_offset, chunk_blocks); 431 vector<Extent> new_extents_chunk = ExtentsSublist( 432 new_extents, block_offset, chunk_blocks); 433 NormalizeExtents(&old_extents_chunk); 434 NormalizeExtents(&new_extents_chunk); 435 436 TEST_AND_RETURN_FALSE(ReadExtentsToDiff(old_part, 437 new_part, 438 old_extents_chunk, 439 new_extents_chunk, 440 bsdiff_allowed, 441 &data, 442 &operation, 443 src_ops_allowed)); 444 445 // Check if the operation writes nothing. 446 if (operation.dst_extents_size() == 0) { 447 if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) { 448 LOG(INFO) << "Empty MOVE operation (" 449 << name << "), skipping"; 450 continue; 451 } else { 452 LOG(ERROR) << "Empty non-MOVE operation"; 453 return false; 454 } 455 } 456 457 // Write the data 458 if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE && 459 operation.type() != 460 DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) { 461 operation.set_data_offset(*data_file_size); 462 operation.set_data_length(data.size()); 463 } 464 465 TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, data.data(), data.size())); 466 *data_file_size += data.size(); 467 468 // Now, insert into the list of operations. 469 AnnotatedOperation aop; 470 aop.name = name; 471 if (static_cast<uint64_t>(chunk_blocks) < total_blocks) { 472 aop.name = base::StringPrintf("%s:%" PRIu64, 473 name.c_str(), block_offset / chunk_blocks); 474 } 475 aop.op = operation; 476 aops->emplace_back(aop); 477 } 478 return true; 479} 480 481bool DeltaDiffGenerator::ReadExtentsToDiff( 482 const string& old_part, 483 const string& new_part, 484 const vector<Extent>& old_extents, 485 const vector<Extent>& new_extents, 486 bool bsdiff_allowed, 487 chromeos::Blob* out_data, 488 DeltaArchiveManifest_InstallOperation* out_op, 489 bool src_ops_allowed) { 490 DeltaArchiveManifest_InstallOperation operation; 491 // Data blob that will be written to delta file. 492 const chromeos::Blob* data_blob = nullptr; 493 494 // We read blocks from old_extents and write blocks to new_extents. 495 uint64_t blocks_to_read = BlocksInExtents(old_extents); 496 uint64_t blocks_to_write = BlocksInExtents(new_extents); 497 498 // Make copies of the extents so we can modify them. 499 vector<Extent> src_extents = old_extents; 500 vector<Extent> dst_extents = new_extents; 501 502 // Read in bytes from new data. 503 chromeos::Blob new_data; 504 TEST_AND_RETURN_FALSE(utils::ReadExtents(new_part, 505 new_extents, 506 &new_data, 507 kBlockSize * blocks_to_write, 508 kBlockSize)); 509 TEST_AND_RETURN_FALSE(!new_data.empty()); 510 511 512 // Using a REPLACE is always an option. 513 operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE); 514 data_blob = &new_data; 515 516 // Try compressing it with bzip2. 517 chromeos::Blob new_data_bz; 518 TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz)); 519 CHECK(!new_data_bz.empty()); 520 if (new_data_bz.size() < data_blob->size()) { 521 // A REPLACE_BZ is better. 522 operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ); 523 data_blob = &new_data_bz; 524 } 525 526 chromeos::Blob old_data; 527 chromeos::Blob empty_blob; 528 chromeos::Blob bsdiff_delta; 529 if (blocks_to_read > 0) { 530 // Read old data. 531 TEST_AND_RETURN_FALSE( 532 utils::ReadExtents(old_part, src_extents, &old_data, 533 kBlockSize * blocks_to_read, kBlockSize)); 534 if (old_data == new_data) { 535 // No change in data. 536 if (src_ops_allowed) { 537 operation.set_type( 538 DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY); 539 } else { 540 operation.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE); 541 } 542 data_blob = &empty_blob; 543 } else if (bsdiff_allowed) { 544 // If the source file is considered bsdiff safe (no bsdiff bugs 545 // triggered), see if BSDIFF encoding is smaller. 546 base::FilePath old_chunk; 547 TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&old_chunk)); 548 ScopedPathUnlinker old_unlinker(old_chunk.value()); 549 TEST_AND_RETURN_FALSE( 550 utils::WriteFile(old_chunk.value().c_str(), 551 old_data.data(), old_data.size())); 552 base::FilePath new_chunk; 553 TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&new_chunk)); 554 ScopedPathUnlinker new_unlinker(new_chunk.value()); 555 TEST_AND_RETURN_FALSE( 556 utils::WriteFile(new_chunk.value().c_str(), 557 new_data.data(), new_data.size())); 558 559 TEST_AND_RETURN_FALSE( 560 BsdiffFiles(old_chunk.value(), new_chunk.value(), &bsdiff_delta)); 561 CHECK_GT(bsdiff_delta.size(), static_cast<chromeos::Blob::size_type>(0)); 562 if (bsdiff_delta.size() < data_blob->size()) { 563 if (src_ops_allowed) { 564 operation.set_type( 565 DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF); 566 } else { 567 operation.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF); 568 } 569 data_blob = &bsdiff_delta; 570 } 571 } 572 } 573 574 size_t removed_bytes = 0; 575 // Remove identical src/dst block ranges in MOVE operations. 576 if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) { 577 removed_bytes = RemoveIdenticalBlockRanges( 578 &src_extents, &dst_extents, new_data.size()); 579 } 580 // Set legacy src_length and dst_length fields. 581 operation.set_src_length(old_data.size() - removed_bytes); 582 operation.set_dst_length(new_data.size() - removed_bytes); 583 584 // Embed extents in the operation. 585 StoreExtents(src_extents, operation.mutable_src_extents()); 586 StoreExtents(dst_extents, operation.mutable_dst_extents()); 587 588 // Replace operations should not have source extents. 589 if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE || 590 operation.type() == 591 DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) { 592 operation.clear_src_extents(); 593 operation.clear_src_length(); 594 } 595 596 *out_data = std::move(*data_blob); 597 *out_op = operation; 598 599 return true; 600} 601 602bool DeltaDiffGenerator::DeltaCompressKernelPartition( 603 const string& old_kernel_part, 604 const string& new_kernel_part, 605 uint64_t old_kernel_size, 606 uint64_t new_kernel_size, 607 uint64_t block_size, 608 vector<AnnotatedOperation>* aops, 609 int blobs_fd, 610 off_t* blobs_length, 611 bool src_ops_allowed) { 612 LOG(INFO) << "Delta compressing kernel partition..."; 613 LOG_IF(INFO, old_kernel_part.empty()) << "Generating full kernel update..."; 614 615 unique_ptr<RawFilesystem> old_kernel_fs; 616 if (!old_kernel_part.empty()) 617 old_kernel_fs = RawFilesystem::Create("<kernel-delta-operation>", 618 block_size, 619 old_kernel_size / block_size); 620 unique_ptr<RawFilesystem> new_kernel_fs = RawFilesystem::Create( 621 "<kernel-delta-operation>", 622 block_size, 623 new_kernel_size / block_size); 624 625 DeltaReadFilesystem(aops, 626 old_kernel_part, 627 new_kernel_part, 628 old_kernel_fs.get(), 629 new_kernel_fs.get(), 630 -1, // chunk_blocks 631 blobs_fd, 632 blobs_length, 633 src_ops_allowed); 634 635 LOG(INFO) << "Done delta compressing kernel partition."; 636 return true; 637} 638 639bool DeltaDiffGenerator::InitializePartitionInfo(const PartitionConfig& part, 640 PartitionInfo* info) { 641 info->set_size(part.size); 642 OmahaHashCalculator hasher; 643 TEST_AND_RETURN_FALSE(hasher.UpdateFile(part.path, part.size) == 644 static_cast<off_t>(part.size)); 645 TEST_AND_RETURN_FALSE(hasher.Finalize()); 646 const chromeos::Blob& hash = hasher.raw_hash(); 647 info->set_hash(hash.data(), hash.size()); 648 LOG(INFO) << part.path << ": size=" << part.size << " hash=" << hasher.hash(); 649 return true; 650} 651 652bool InitializePartitionInfos(const PayloadGenerationConfig& config, 653 DeltaArchiveManifest* manifest) { 654 if (!config.source.kernel.path.empty()) { 655 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo( 656 config.source.kernel, 657 manifest->mutable_old_kernel_info())); 658 } 659 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo( 660 config.target.kernel, 661 manifest->mutable_new_kernel_info())); 662 if (!config.source.rootfs.path.empty()) { 663 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo( 664 config.source.rootfs, 665 manifest->mutable_old_rootfs_info())); 666 } 667 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo( 668 config.target.rootfs, 669 manifest->mutable_new_rootfs_info())); 670 return true; 671} 672 673// Stores all Extents in 'extents' into 'out'. 674void DeltaDiffGenerator::StoreExtents( 675 const vector<Extent>& extents, 676 google::protobuf::RepeatedPtrField<Extent>* out) { 677 for (const Extent& extent : extents) { 678 Extent* new_extent = out->Add(); 679 *new_extent = extent; 680 } 681} 682 683// Stores all extents in |extents| into |out_vector|. 684void DeltaDiffGenerator::ExtentsToVector( 685 const google::protobuf::RepeatedPtrField<Extent>& extents, 686 vector<Extent>* out_vector) { 687 out_vector->clear(); 688 for (int i = 0; i < extents.size(); i++) { 689 out_vector->push_back(extents.Get(i)); 690 } 691} 692 693// Returns true if |op| is a no-op operation that doesn't do any useful work 694// (e.g., a move operation that copies blocks onto themselves). 695bool DeltaDiffGenerator::IsNoopOperation( 696 const DeltaArchiveManifest_InstallOperation& op) { 697 return (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE && 698 ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents())); 699} 700 701void DeltaDiffGenerator::FilterNoopOperations(vector<AnnotatedOperation>* ops) { 702 ops->erase( 703 std::remove_if( 704 ops->begin(), ops->end(), 705 [](const AnnotatedOperation& aop){return IsNoopOperation(aop.op);}), 706 ops->end()); 707} 708 709bool DeltaDiffGenerator::ReorderDataBlobs( 710 DeltaArchiveManifest* manifest, 711 const string& data_blobs_path, 712 const string& new_data_blobs_path) { 713 int in_fd = open(data_blobs_path.c_str(), O_RDONLY, 0); 714 TEST_AND_RETURN_FALSE_ERRNO(in_fd >= 0); 715 ScopedFdCloser in_fd_closer(&in_fd); 716 717 DirectFileWriter writer; 718 TEST_AND_RETURN_FALSE( 719 writer.Open(new_data_blobs_path.c_str(), 720 O_WRONLY | O_TRUNC | O_CREAT, 721 0644) == 0); 722 ScopedFileWriterCloser writer_closer(&writer); 723 uint64_t out_file_size = 0; 724 725 for (int i = 0; i < (manifest->install_operations_size() + 726 manifest->kernel_install_operations_size()); i++) { 727 DeltaArchiveManifest_InstallOperation* op = nullptr; 728 if (i < manifest->install_operations_size()) { 729 op = manifest->mutable_install_operations(i); 730 } else { 731 op = manifest->mutable_kernel_install_operations( 732 i - manifest->install_operations_size()); 733 } 734 if (!op->has_data_offset()) 735 continue; 736 CHECK(op->has_data_length()); 737 chromeos::Blob buf(op->data_length()); 738 ssize_t rc = pread(in_fd, buf.data(), buf.size(), op->data_offset()); 739 TEST_AND_RETURN_FALSE(rc == static_cast<ssize_t>(buf.size())); 740 741 // Add the hash of the data blobs for this operation 742 TEST_AND_RETURN_FALSE(AddOperationHash(op, buf)); 743 744 op->set_data_offset(out_file_size); 745 TEST_AND_RETURN_FALSE(writer.Write(buf.data(), buf.size())); 746 out_file_size += buf.size(); 747 } 748 return true; 749} 750 751bool DeltaDiffGenerator::AddOperationHash( 752 DeltaArchiveManifest_InstallOperation* op, 753 const chromeos::Blob& buf) { 754 OmahaHashCalculator hasher; 755 TEST_AND_RETURN_FALSE(hasher.Update(buf.data(), buf.size())); 756 TEST_AND_RETURN_FALSE(hasher.Finalize()); 757 const chromeos::Blob& hash = hasher.raw_hash(); 758 op->set_data_sha256_hash(hash.data(), hash.size()); 759 return true; 760} 761 762bool DeltaDiffGenerator::GenerateOperations( 763 const PayloadGenerationConfig& config, 764 int data_file_fd, 765 off_t* data_file_size, 766 vector<AnnotatedOperation>* rootfs_ops, 767 vector<AnnotatedOperation>* kernel_ops) { 768 unique_ptr<Ext2Filesystem> old_fs = Ext2Filesystem::CreateFromFile( 769 config.source.rootfs.path); 770 unique_ptr<Ext2Filesystem> new_fs = Ext2Filesystem::CreateFromFile( 771 config.target.rootfs.path); 772 773 off_t chunk_blocks = config.chunk_size == -1 ? -1 : ( 774 config.chunk_size / config.block_size); 775 776 rootfs_ops->clear(); 777 TEST_AND_RETURN_FALSE(DeltaReadFilesystem(rootfs_ops, 778 config.source.rootfs.path, 779 config.target.rootfs.path, 780 old_fs.get(), 781 new_fs.get(), 782 chunk_blocks, 783 data_file_fd, 784 data_file_size, 785 true)); // src_ops_allowed 786 LOG(INFO) << "done reading normal files"; 787 788 // Read kernel partition 789 TEST_AND_RETURN_FALSE( 790 DeltaCompressKernelPartition(config.source.kernel.path, 791 config.target.kernel.path, 792 config.source.kernel.size, 793 config.target.kernel.size, 794 config.block_size, 795 kernel_ops, 796 data_file_fd, 797 data_file_size, 798 true)); // src_ops_allowed 799 LOG(INFO) << "done reading kernel"; 800 801 TEST_AND_RETURN_FALSE(FragmentOperations(rootfs_ops, 802 config.target.rootfs.path, 803 data_file_fd, 804 data_file_size)); 805 TEST_AND_RETURN_FALSE(FragmentOperations(kernel_ops, 806 config.target.kernel.path, 807 data_file_fd, 808 data_file_size)); 809 SortOperationsByDestination(rootfs_ops); 810 SortOperationsByDestination(kernel_ops); 811 // TODO(alliewood): Change merge operations to use config.chunk_size once 812 // specifying chunk_size on the command line works. crbug/485397. 813 TEST_AND_RETURN_FALSE(MergeOperations(rootfs_ops, 814 kDefaultChunkSize, 815 config.target.rootfs.path, 816 data_file_fd, 817 data_file_size)); 818 TEST_AND_RETURN_FALSE(MergeOperations(kernel_ops, 819 kDefaultChunkSize, 820 config.target.kernel.path, 821 data_file_fd, 822 data_file_size)); 823 return true; 824} 825 826bool GenerateUpdatePayloadFile( 827 const PayloadGenerationConfig& config, 828 const string& output_path, 829 const string& private_key_path, 830 uint64_t* metadata_size) { 831 if (config.is_delta) { 832 LOG_IF(WARNING, config.source.rootfs.size != config.target.rootfs.size) 833 << "Old and new images have different block counts."; 834 // TODO(deymo): Our tools only support growing the filesystem size during 835 // an update. Remove this check when that's fixed. crbug.com/192136 836 LOG_IF(FATAL, config.source.rootfs.size > config.target.rootfs.size) 837 << "Shirking the rootfs size is not supported at the moment."; 838 } 839 840 // Sanity checks for the partition size. 841 LOG(INFO) << "Rootfs partition size: " << config.rootfs_partition_size; 842 LOG(INFO) << "Actual filesystem size: " << config.target.rootfs.size; 843 844 LOG(INFO) << "Block count: " 845 << config.target.rootfs.size / config.block_size; 846 847 const string kTempFileTemplate("CrAU_temp_data.XXXXXX"); 848 string temp_file_path; 849 unique_ptr<ScopedPathUnlinker> temp_file_unlinker; 850 off_t data_file_size = 0; 851 852 LOG(INFO) << "Reading files..."; 853 854 // Create empty protobuf Manifest object 855 DeltaArchiveManifest manifest; 856 manifest.set_minor_version(config.minor_version); 857 858 vector<AnnotatedOperation> rootfs_ops; 859 vector<AnnotatedOperation> kernel_ops; 860 861 // Select payload generation strategy based on the config. 862 unique_ptr<OperationsGenerator> strategy; 863 if (config.is_delta) { 864 // We don't efficiently support deltas on squashfs. For now, we will 865 // produce full operations in that case. 866 if (utils::IsSquashfsFilesystem(config.target.rootfs.path)) { 867 LOG(INFO) << "Using generator FullUpdateGenerator::Run for squashfs " 868 "deltas"; 869 strategy.reset(new FullUpdateGenerator()); 870 } else if (utils::IsExtFilesystem(config.target.rootfs.path)) { 871 // Delta update (with possibly a full kernel update). 872 if (config.minor_version == kInPlaceMinorPayloadVersion) { 873 LOG(INFO) << "Using generator InplaceGenerator::GenerateInplaceDelta"; 874 strategy.reset(new InplaceGenerator()); 875 } else if (config.minor_version == kSourceMinorPayloadVersion) { 876 LOG(INFO) << "Using generator DeltaDiffGenerator::GenerateSourceDelta"; 877 strategy.reset(new DeltaDiffGenerator()); 878 } else { 879 LOG(ERROR) << "Unsupported minor version given for delta payload: " 880 << config.minor_version; 881 return false; 882 } 883 } else { 884 LOG(ERROR) << "Unsupported filesystem for delta payload in " 885 << config.target.rootfs.path; 886 return false; 887 } 888 } else { 889 // Full update. 890 LOG(INFO) << "Using generator FullUpdateGenerator::Run"; 891 strategy.reset(new FullUpdateGenerator()); 892 } 893 894 { 895 int data_file_fd; 896 TEST_AND_RETURN_FALSE( 897 utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &data_file_fd)); 898 temp_file_unlinker.reset(new ScopedPathUnlinker(temp_file_path)); 899 TEST_AND_RETURN_FALSE(data_file_fd >= 0); 900 ScopedFdCloser data_file_fd_closer(&data_file_fd); 901 902 // Generate the operations using the strategy we selected above. 903 TEST_AND_RETURN_FALSE(strategy->GenerateOperations(config, 904 data_file_fd, 905 &data_file_size, 906 &rootfs_ops, 907 &kernel_ops)); 908 } 909 910 if (!config.source.ImageInfoIsEmpty()) 911 *(manifest.mutable_old_image_info()) = config.source.image_info; 912 913 if (!config.target.ImageInfoIsEmpty()) 914 *(manifest.mutable_new_image_info()) = config.target.image_info; 915 916 // Filter the no-operations. OperationsGenerators should not output this kind 917 // of operations normally, but this is an extra step to fix that if 918 // happened. 919 DeltaDiffGenerator::FilterNoopOperations(&rootfs_ops); 920 DeltaDiffGenerator::FilterNoopOperations(&kernel_ops); 921 922 OperationNameMap op_name_map; 923 InstallOperationsToManifest(rootfs_ops, kernel_ops, &manifest, &op_name_map); 924 manifest.set_block_size(config.block_size); 925 926 // Reorder the data blobs with the newly ordered manifest. 927 string ordered_blobs_path; 928 TEST_AND_RETURN_FALSE(utils::MakeTempFile( 929 "CrAU_temp_data.ordered.XXXXXX", 930 &ordered_blobs_path, 931 nullptr)); 932 ScopedPathUnlinker ordered_blobs_unlinker(ordered_blobs_path); 933 TEST_AND_RETURN_FALSE( 934 DeltaDiffGenerator::ReorderDataBlobs(&manifest, 935 temp_file_path, 936 ordered_blobs_path)); 937 temp_file_unlinker.reset(); 938 939 // Check that install op blobs are in order. 940 uint64_t next_blob_offset = 0; 941 { 942 for (int i = 0; i < (manifest.install_operations_size() + 943 manifest.kernel_install_operations_size()); i++) { 944 DeltaArchiveManifest_InstallOperation* op = 945 i < manifest.install_operations_size() ? 946 manifest.mutable_install_operations(i) : 947 manifest.mutable_kernel_install_operations( 948 i - manifest.install_operations_size()); 949 if (op->has_data_offset()) { 950 if (op->data_offset() != next_blob_offset) { 951 LOG(FATAL) << "bad blob offset! " << op->data_offset() << " != " 952 << next_blob_offset; 953 } 954 next_blob_offset += op->data_length(); 955 } 956 } 957 } 958 959 // Signatures appear at the end of the blobs. Note the offset in the 960 // manifest 961 if (!private_key_path.empty()) { 962 uint64_t signature_blob_length = 0; 963 TEST_AND_RETURN_FALSE( 964 PayloadSigner::SignatureBlobLength(vector<string>(1, private_key_path), 965 &signature_blob_length)); 966 DeltaDiffGenerator::AddSignatureOp( 967 next_blob_offset, signature_blob_length, &manifest); 968 } 969 970 TEST_AND_RETURN_FALSE(InitializePartitionInfos(config, &manifest)); 971 972 // Serialize protobuf 973 string serialized_manifest; 974 975 TEST_AND_RETURN_FALSE(manifest.AppendToString(&serialized_manifest)); 976 977 LOG(INFO) << "Writing final delta file header..."; 978 DirectFileWriter writer; 979 TEST_AND_RETURN_FALSE_ERRNO(writer.Open(output_path.c_str(), 980 O_WRONLY | O_CREAT | O_TRUNC, 981 0644) == 0); 982 ScopedFileWriterCloser writer_closer(&writer); 983 984 // Write header 985 TEST_AND_RETURN_FALSE(writer.Write(kDeltaMagic, strlen(kDeltaMagic))); 986 987 // Write major version number 988 TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer, kMajorVersionNumber)); 989 990 // Write protobuf length 991 TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer, 992 serialized_manifest.size())); 993 994 // Write protobuf 995 LOG(INFO) << "Writing final delta file protobuf... " 996 << serialized_manifest.size(); 997 TEST_AND_RETURN_FALSE(writer.Write(serialized_manifest.data(), 998 serialized_manifest.size())); 999 1000 // Append the data blobs 1001 LOG(INFO) << "Writing final delta file data blobs..."; 1002 int blobs_fd = open(ordered_blobs_path.c_str(), O_RDONLY, 0); 1003 ScopedFdCloser blobs_fd_closer(&blobs_fd); 1004 TEST_AND_RETURN_FALSE(blobs_fd >= 0); 1005 for (;;) { 1006 vector<char> buf(config.block_size); 1007 ssize_t rc = read(blobs_fd, buf.data(), buf.size()); 1008 if (0 == rc) { 1009 // EOF 1010 break; 1011 } 1012 TEST_AND_RETURN_FALSE_ERRNO(rc > 0); 1013 TEST_AND_RETURN_FALSE(writer.Write(buf.data(), rc)); 1014 } 1015 1016 // Write signature blob. 1017 if (!private_key_path.empty()) { 1018 LOG(INFO) << "Signing the update..."; 1019 chromeos::Blob signature_blob; 1020 TEST_AND_RETURN_FALSE(PayloadSigner::SignPayload( 1021 output_path, 1022 vector<string>(1, private_key_path), 1023 &signature_blob)); 1024 TEST_AND_RETURN_FALSE(writer.Write(signature_blob.data(), 1025 signature_blob.size())); 1026 } 1027 1028 *metadata_size = 1029 strlen(kDeltaMagic) + 2 * sizeof(uint64_t) + serialized_manifest.size(); 1030 ReportPayloadUsage(manifest, *metadata_size, op_name_map); 1031 1032 LOG(INFO) << "All done. Successfully created delta file with " 1033 << "metadata size = " << *metadata_size; 1034 return true; 1035} 1036 1037// Runs the bsdiff tool on two files and returns the resulting delta in 1038// 'out'. Returns true on success. 1039bool DeltaDiffGenerator::BsdiffFiles(const string& old_file, 1040 const string& new_file, 1041 chromeos::Blob* out) { 1042 const string kPatchFile = "delta.patchXXXXXX"; 1043 string patch_file_path; 1044 1045 TEST_AND_RETURN_FALSE( 1046 utils::MakeTempFile(kPatchFile, &patch_file_path, nullptr)); 1047 1048 vector<string> cmd; 1049 cmd.push_back(kBsdiffPath); 1050 cmd.push_back(old_file); 1051 cmd.push_back(new_file); 1052 cmd.push_back(patch_file_path); 1053 1054 int rc = 1; 1055 chromeos::Blob patch_file; 1056 TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, nullptr)); 1057 TEST_AND_RETURN_FALSE(rc == 0); 1058 TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out)); 1059 unlink(patch_file_path.c_str()); 1060 return true; 1061} 1062 1063void DeltaDiffGenerator::AddSignatureOp(uint64_t signature_blob_offset, 1064 uint64_t signature_blob_length, 1065 DeltaArchiveManifest* manifest) { 1066 LOG(INFO) << "Making room for signature in file"; 1067 manifest->set_signatures_offset(signature_blob_offset); 1068 LOG(INFO) << "set? " << manifest->has_signatures_offset(); 1069 // Add a dummy op at the end to appease older clients 1070 DeltaArchiveManifest_InstallOperation* dummy_op = 1071 manifest->add_kernel_install_operations(); 1072 dummy_op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE); 1073 dummy_op->set_data_offset(signature_blob_offset); 1074 manifest->set_signatures_offset(signature_blob_offset); 1075 dummy_op->set_data_length(signature_blob_length); 1076 manifest->set_signatures_size(signature_blob_length); 1077 Extent* dummy_extent = dummy_op->add_dst_extents(); 1078 // Tell the dummy op to write this data to a big sparse hole 1079 dummy_extent->set_start_block(kSparseHole); 1080 dummy_extent->set_num_blocks((signature_blob_length + kBlockSize - 1) / 1081 kBlockSize); 1082} 1083 1084bool DeltaDiffGenerator::FragmentOperations( 1085 vector<AnnotatedOperation>* aops, 1086 const string& target_part_path, 1087 int data_fd, 1088 off_t* data_file_size) { 1089 vector<AnnotatedOperation> fragmented_aops; 1090 for (const AnnotatedOperation& aop : *aops) { 1091 if (aop.op.type() == 1092 DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) { 1093 TEST_AND_RETURN_FALSE(SplitSourceCopy(aop, &fragmented_aops)); 1094 } else if ((aop.op.type() == 1095 DeltaArchiveManifest_InstallOperation_Type_REPLACE) || 1096 (aop.op.type() == 1097 DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) { 1098 TEST_AND_RETURN_FALSE(SplitReplaceOrReplaceBz(aop, &fragmented_aops, 1099 target_part_path, data_fd, 1100 data_file_size)); 1101 } else { 1102 fragmented_aops.push_back(aop); 1103 } 1104 } 1105 *aops = fragmented_aops; 1106 return true; 1107} 1108 1109void DeltaDiffGenerator::SortOperationsByDestination( 1110 vector<AnnotatedOperation>* aops) { 1111 sort(aops->begin(), aops->end(), CompareAopsByDestination); 1112} 1113 1114bool DeltaDiffGenerator::SplitSourceCopy( 1115 const AnnotatedOperation& original_aop, 1116 vector<AnnotatedOperation>* result_aops) { 1117 DeltaArchiveManifest_InstallOperation original_op = original_aop.op; 1118 TEST_AND_RETURN_FALSE(original_op.type() == 1119 DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY); 1120 // Keeps track of the index of curr_src_ext. 1121 int curr_src_ext_index = 0; 1122 Extent curr_src_ext = original_op.src_extents(curr_src_ext_index); 1123 for (int i = 0; i < original_op.dst_extents_size(); i++) { 1124 Extent dst_ext = original_op.dst_extents(i); 1125 // The new operation which will have only one dst extent. 1126 DeltaArchiveManifest_InstallOperation new_op; 1127 uint64_t blocks_left = dst_ext.num_blocks(); 1128 while (blocks_left > 0) { 1129 if (curr_src_ext.num_blocks() <= blocks_left) { 1130 // If the curr_src_ext is smaller than dst_ext, add it. 1131 blocks_left -= curr_src_ext.num_blocks(); 1132 *(new_op.add_src_extents()) = curr_src_ext; 1133 if (curr_src_ext_index + 1 < original_op.src_extents().size()) { 1134 curr_src_ext = original_op.src_extents(++curr_src_ext_index); 1135 } else { 1136 break; 1137 } 1138 } else { 1139 // Split src_exts that are bigger than the dst_ext we're dealing with. 1140 Extent first_ext; 1141 first_ext.set_num_blocks(blocks_left); 1142 first_ext.set_start_block(curr_src_ext.start_block()); 1143 *(new_op.add_src_extents()) = first_ext; 1144 // Keep the second half of the split op. 1145 curr_src_ext.set_num_blocks(curr_src_ext.num_blocks() - blocks_left); 1146 curr_src_ext.set_start_block(curr_src_ext.start_block() + blocks_left); 1147 blocks_left -= first_ext.num_blocks(); 1148 } 1149 } 1150 // Fix up our new operation and add it to the results. 1151 new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY); 1152 *(new_op.add_dst_extents()) = dst_ext; 1153 new_op.set_src_length(dst_ext.num_blocks() * kBlockSize); 1154 new_op.set_dst_length(dst_ext.num_blocks() * kBlockSize); 1155 1156 AnnotatedOperation new_aop; 1157 new_aop.op = new_op; 1158 new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i); 1159 result_aops->push_back(new_aop); 1160 } 1161 if (curr_src_ext_index != original_op.src_extents().size() - 1) { 1162 LOG(FATAL) << "Incorrectly split SOURCE_COPY operation. Did not use all " 1163 << "source extents."; 1164 } 1165 return true; 1166} 1167 1168bool DeltaDiffGenerator::SplitReplaceOrReplaceBz( 1169 const AnnotatedOperation& original_aop, 1170 vector<AnnotatedOperation>* result_aops, 1171 const string& target_part_path, 1172 int data_fd, 1173 off_t* data_file_size) { 1174 DeltaArchiveManifest_InstallOperation original_op = original_aop.op; 1175 const bool is_replace = 1176 original_op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE; 1177 TEST_AND_RETURN_FALSE( 1178 is_replace || 1179 (original_op.type() == 1180 DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)); 1181 1182 uint32_t data_offset = original_op.data_offset(); 1183 for (int i = 0; i < original_op.dst_extents_size(); i++) { 1184 Extent dst_ext = original_op.dst_extents(i); 1185 // Make a new operation with only one dst extent. 1186 DeltaArchiveManifest_InstallOperation new_op; 1187 *(new_op.add_dst_extents()) = dst_ext; 1188 uint32_t data_size = dst_ext.num_blocks() * kBlockSize; 1189 new_op.set_dst_length(data_size); 1190 // If this is a REPLACE, attempt to reuse portions of the existing blob. 1191 if (is_replace) { 1192 new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE); 1193 new_op.set_data_length(data_size); 1194 new_op.set_data_offset(data_offset); 1195 data_offset += data_size; 1196 } 1197 1198 AnnotatedOperation new_aop; 1199 new_aop.op = new_op; 1200 new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i); 1201 TEST_AND_RETURN_FALSE(AddDataAndSetType(&new_aop, target_part_path, data_fd, 1202 data_file_size)); 1203 1204 result_aops->push_back(new_aop); 1205 } 1206 return true; 1207} 1208 1209bool DeltaDiffGenerator::MergeOperations(vector<AnnotatedOperation>* aops, 1210 off_t chunk_size, 1211 const string& target_part_path, 1212 int data_fd, 1213 off_t* data_file_size) { 1214 vector<AnnotatedOperation> new_aops; 1215 for (const AnnotatedOperation& curr_aop : *aops) { 1216 if (new_aops.empty()) { 1217 new_aops.push_back(curr_aop); 1218 continue; 1219 } 1220 AnnotatedOperation& last_aop = new_aops.back(); 1221 1222 if (last_aop.op.dst_extents_size() <= 0 || 1223 curr_aop.op.dst_extents_size() <= 0) { 1224 new_aops.push_back(curr_aop); 1225 continue; 1226 } 1227 uint32_t last_dst_idx = last_aop.op.dst_extents_size() - 1; 1228 uint32_t last_end_block = 1229 last_aop.op.dst_extents(last_dst_idx).start_block() + 1230 last_aop.op.dst_extents(last_dst_idx).num_blocks(); 1231 uint32_t curr_start_block = curr_aop.op.dst_extents(0).start_block(); 1232 uint32_t combined_block_count = 1233 last_aop.op.dst_extents(last_dst_idx).num_blocks() + 1234 curr_aop.op.dst_extents(0).num_blocks(); 1235 bool good_op_type = 1236 curr_aop.op.type() == 1237 DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY || 1238 curr_aop.op.type() == 1239 DeltaArchiveManifest_InstallOperation_Type_REPLACE || 1240 curr_aop.op.type() == 1241 DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ; 1242 if (good_op_type && 1243 last_aop.op.type() == curr_aop.op.type() && 1244 last_end_block == curr_start_block && 1245 static_cast<off_t>(combined_block_count * kBlockSize) <= chunk_size) { 1246 // If the operations have the same type (which is a type that we can 1247 // merge), are contiguous, are fragmented to have one destination extent, 1248 // and their combined block count would be less than chunk size, merge 1249 // them. 1250 last_aop.name = base::StringPrintf("%s,%s", 1251 last_aop.name.c_str(), 1252 curr_aop.name.c_str()); 1253 1254 ExtendExtents(last_aop.op.mutable_src_extents(), 1255 curr_aop.op.src_extents()); 1256 if (curr_aop.op.src_length() > 0) 1257 last_aop.op.set_src_length(last_aop.op.src_length() + 1258 curr_aop.op.src_length()); 1259 ExtendExtents(last_aop.op.mutable_dst_extents(), 1260 curr_aop.op.dst_extents()); 1261 if (curr_aop.op.dst_length() > 0) 1262 last_aop.op.set_dst_length(last_aop.op.dst_length() + 1263 curr_aop.op.dst_length()); 1264 // Set the data length to zero so we know to add the blob later. 1265 if (curr_aop.op.type() == 1266 DeltaArchiveManifest_InstallOperation_Type_REPLACE || 1267 curr_aop.op.type() == 1268 DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) { 1269 last_aop.op.set_data_length(0); 1270 } 1271 } else { 1272 // Otherwise just include the extent as is. 1273 new_aops.push_back(curr_aop); 1274 } 1275 } 1276 1277 // Set the blobs for REPLACE/REPLACE_BZ operations that have been merged. 1278 for (AnnotatedOperation& curr_aop : new_aops) { 1279 if (curr_aop.op.data_length() == 0 && 1280 (curr_aop.op.type() == 1281 DeltaArchiveManifest_InstallOperation_Type_REPLACE || 1282 curr_aop.op.type() == 1283 DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) { 1284 TEST_AND_RETURN_FALSE(AddDataAndSetType(&curr_aop, target_part_path, 1285 data_fd, data_file_size)); 1286 } 1287 } 1288 1289 *aops = new_aops; 1290 return true; 1291} 1292 1293void DeltaDiffGenerator::ExtendExtents( 1294 google::protobuf::RepeatedPtrField<Extent>* extents, 1295 const google::protobuf::RepeatedPtrField<Extent>& extents_to_add) { 1296 vector<Extent> extents_vector; 1297 vector<Extent> extents_to_add_vector; 1298 ExtentsToVector(*extents, &extents_vector); 1299 ExtentsToVector(extents_to_add, &extents_to_add_vector); 1300 extents_vector.insert(extents_vector.end(), 1301 extents_to_add_vector.begin(), 1302 extents_to_add_vector.end()); 1303 NormalizeExtents(&extents_vector); 1304 extents->Clear(); 1305 StoreExtents(extents_vector, extents); 1306} 1307 1308bool DeltaDiffGenerator::AddDataAndSetType(AnnotatedOperation* aop, 1309 const string& target_part_path, 1310 int data_fd, 1311 off_t* data_file_size) { 1312 TEST_AND_RETURN_FALSE( 1313 aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE || 1314 aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ); 1315 1316 chromeos::Blob data(aop->op.dst_length()); 1317 vector<Extent> dst_extents; 1318 ExtentsToVector(aop->op.dst_extents(), &dst_extents); 1319 TEST_AND_RETURN_FALSE(utils::ReadExtents(target_part_path, 1320 dst_extents, 1321 &data, 1322 data.size(), 1323 kBlockSize)); 1324 1325 chromeos::Blob data_bz; 1326 TEST_AND_RETURN_FALSE(BzipCompress(data, &data_bz)); 1327 CHECK(!data_bz.empty()); 1328 1329 chromeos::Blob* data_p = nullptr; 1330 DeltaArchiveManifest_InstallOperation_Type new_op_type; 1331 if (data_bz.size() < data.size()) { 1332 new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ; 1333 data_p = &data_bz; 1334 } else { 1335 new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE; 1336 data_p = &data; 1337 } 1338 1339 // If the operation already points to a data blob, check whether it's 1340 // identical to the new one, in which case don't add it. 1341 if (aop->op.type() == new_op_type && 1342 aop->op.data_length() == data_p->size()) { 1343 chromeos::Blob current_data(data_p->size()); 1344 ssize_t bytes_read; 1345 TEST_AND_RETURN_FALSE(utils::PReadAll(data_fd, 1346 current_data.data(), 1347 aop->op.data_length(), 1348 aop->op.data_offset(), 1349 &bytes_read)); 1350 TEST_AND_RETURN_FALSE(bytes_read == 1351 static_cast<ssize_t>(aop->op.data_length())); 1352 if (current_data == *data_p) 1353 data_p = nullptr; 1354 } 1355 1356 if (data_p) { 1357 aop->op.set_type(new_op_type); 1358 aop->SetOperationBlob(data_p, data_fd, data_file_size); 1359 } 1360 1361 return true; 1362} 1363 1364}; // namespace chromeos_update_engine 1365