delta_diff_generator.cc revision f329b933db41d26644a97afef928eb1b319d6d99
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 <set> 17#include <string> 18#include <utility> 19#include <vector> 20 21#include <base/files/file_util.h> 22#include <base/files/file_path.h> 23#include <base/logging.h> 24#include <base/strings/string_number_conversions.h> 25#include <base/strings/string_util.h> 26#include <base/strings/stringprintf.h> 27#include <bzlib.h> 28 29#include "update_engine/bzip.h" 30#include "update_engine/delta_performer.h" 31#include "update_engine/extent_ranges.h" 32#include "update_engine/file_writer.h" 33#include "update_engine/omaha_hash_calculator.h" 34#include "update_engine/payload_constants.h" 35#include "update_engine/payload_generator/cycle_breaker.h" 36#include "update_engine/payload_generator/extent_mapper.h" 37#include "update_engine/payload_generator/filesystem_iterator.h" 38#include "update_engine/payload_generator/full_update_generator.h" 39#include "update_engine/payload_generator/graph_types.h" 40#include "update_engine/payload_generator/graph_utils.h" 41#include "update_engine/payload_generator/metadata.h" 42#include "update_engine/payload_generator/payload_signer.h" 43#include "update_engine/payload_generator/topological_sort.h" 44#include "update_engine/payload_verifier.h" 45#include "update_engine/subprocess.h" 46#include "update_engine/update_metadata.pb.h" 47#include "update_engine/utils.h" 48 49using std::make_pair; 50using std::map; 51using std::max; 52using std::min; 53using std::pair; 54using std::set; 55using std::string; 56using std::unique_ptr; 57using std::vector; 58 59namespace { 60 61const uint64_t kVersionNumber = 1; 62const uint64_t kFullUpdateChunkSize = 1024 * 1024; // bytes 63 64const size_t kBlockSize = 4096; // bytes 65const char kEmptyPath[] = ""; 66 67// The maximum destination size allowed for bsdiff. In general, bsdiff should 68// work for arbitrary big files, but the payload generation and payload 69// application requires a significant amount of RAM. We put a hard-limit of 70// 200 MiB that should not affect any released board, but will limit the 71// Chrome binary in ASan builders. 72const off_t kMaxBsdiffDestinationSize = 200 * 1024 * 1024; // bytes 73 74static const char* kInstallOperationTypes[] = { 75 "REPLACE", 76 "REPLACE_BZ", 77 "MOVE", 78 "BSDIFF" 79}; 80 81} // namespace 82 83namespace chromeos_update_engine { 84 85typedef DeltaDiffGenerator::Block Block; 86typedef map<const DeltaArchiveManifest_InstallOperation*, 87 string> OperationNameMap; 88 89// bytes 90const size_t kRootFSPartitionSize = static_cast<size_t>(2) * 1024 * 1024 * 1024; 91 92// Needed for testing purposes, in case we can't use actual filesystem objects. 93// TODO(garnold) (chromium:331965) Replace this hack with a properly injected 94// parameter in form of a mockable abstract class. 95bool (*get_extents_with_chunk_func)(const string&, off_t, off_t, 96 vector<Extent>*) = 97 extent_mapper::ExtentsForFileChunkFibmap; 98 99namespace { 100 101// Stores all the extents of |path| into |extents|. Returns true on success. 102bool GatherExtents(const string& path, 103 off_t chunk_offset, 104 off_t chunk_size, 105 vector<Extent>* extents) { 106 extents->clear(); 107 TEST_AND_RETURN_FALSE( 108 get_extents_with_chunk_func( 109 path, chunk_offset, chunk_size, extents)); 110 return true; 111} 112 113// For a given regular file which must exist at new_root + path, and 114// may exist at old_root + path, creates a new InstallOperation and 115// adds it to the graph. Also, populates the |blocks| array as 116// necessary, if |blocks| is non-null. Also, writes the data 117// necessary to send the file down to the client into data_fd, which 118// has length *data_file_size. *data_file_size is updated 119// appropriately. If |existing_vertex| is no kInvalidIndex, use that 120// rather than allocating a new vertex. Returns true on success. 121bool DeltaReadFile(Graph* graph, 122 Vertex::Index existing_vertex, 123 vector<Block>* blocks, 124 const string& old_root, 125 const string& new_root, 126 const string& path, // within new_root 127 off_t chunk_offset, 128 off_t chunk_size, 129 int data_fd, 130 off_t* data_file_size) { 131 vector<char> data; 132 DeltaArchiveManifest_InstallOperation operation; 133 134 string old_path = (old_root == kEmptyPath) ? kEmptyPath : 135 old_root + path; 136 137 // If bsdiff breaks again, blacklist the problem file by using: 138 // bsdiff_allowed = (path != "/foo/bar") 139 // 140 // TODO(dgarrett): chromium-os:15274 connect this test to the command line. 141 bool bsdiff_allowed = true; 142 143 if (utils::FileSize(new_root + path) > kMaxBsdiffDestinationSize) 144 bsdiff_allowed = false; 145 146 if (!bsdiff_allowed) 147 LOG(INFO) << "bsdiff blacklisting: " << path; 148 149 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ReadFileToDiff(old_path, 150 new_root + path, 151 chunk_offset, 152 chunk_size, 153 bsdiff_allowed, 154 &data, 155 &operation, 156 true)); 157 158 // Check if the operation writes nothing. 159 if (operation.dst_extents_size() == 0) { 160 if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) { 161 LOG(INFO) << "Empty MOVE operation (" << new_root + path << "), skipping"; 162 return true; 163 } else { 164 LOG(ERROR) << "Empty non-MOVE operation"; 165 return false; 166 } 167 } 168 169 // Write the data 170 if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) { 171 operation.set_data_offset(*data_file_size); 172 operation.set_data_length(data.size()); 173 } 174 175 TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, &data[0], data.size())); 176 *data_file_size += data.size(); 177 178 // Now, insert into graph and blocks vector 179 Vertex::Index vertex = existing_vertex; 180 if (vertex == Vertex::kInvalidIndex) { 181 graph->resize(graph->size() + 1); 182 vertex = graph->size() - 1; 183 } 184 (*graph)[vertex].op = operation; 185 CHECK((*graph)[vertex].op.has_type()); 186 (*graph)[vertex].file_name = path; 187 (*graph)[vertex].chunk_offset = chunk_offset; 188 (*graph)[vertex].chunk_size = chunk_size; 189 190 if (blocks) 191 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::AddInstallOpToBlocksVector( 192 (*graph)[vertex].op, 193 *graph, 194 vertex, 195 blocks)); 196 return true; 197} 198 199// For each regular file within new_root, creates a node in the graph, 200// determines the best way to compress it (REPLACE, REPLACE_BZ, COPY, BSDIFF), 201// and writes any necessary data to the end of data_fd. 202bool DeltaReadFiles(Graph* graph, 203 vector<Block>* blocks, 204 const string& old_root, 205 const string& new_root, 206 off_t chunk_size, 207 int data_fd, 208 off_t* data_file_size) { 209 set<ino_t> visited_inodes; 210 set<ino_t> visited_src_inodes; 211 for (FilesystemIterator fs_iter(new_root, 212 utils::SetWithValue<string>("/lost+found")); 213 !fs_iter.IsEnd(); fs_iter.Increment()) { 214 // We never diff symlinks (here, we check that dst file is not a symlink). 215 if (!S_ISREG(fs_iter.GetStat().st_mode)) 216 continue; 217 218 // Make sure we visit each inode only once. 219 if (utils::SetContainsKey(visited_inodes, fs_iter.GetStat().st_ino)) 220 continue; 221 visited_inodes.insert(fs_iter.GetStat().st_ino); 222 off_t dst_size = fs_iter.GetFileSize(); 223 if (dst_size == 0) 224 continue; 225 226 LOG(INFO) << "Encoding file " << fs_iter.GetPartialPath(); 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 bool should_diff_from_source = false; 237 string src_path = old_root + fs_iter.GetPartialPath(); 238 struct stat src_stbuf; 239 // We never diff symlinks (here, we check that src file is not a symlink). 240 if (0 == lstat(src_path.c_str(), &src_stbuf) && 241 S_ISREG(src_stbuf.st_mode)) { 242 should_diff_from_source = !utils::SetContainsKey(visited_src_inodes, 243 src_stbuf.st_ino); 244 visited_src_inodes.insert(src_stbuf.st_ino); 245 } 246 247 off_t size = chunk_size == -1 ? dst_size : chunk_size; 248 off_t step = size; 249 for (off_t offset = 0; offset < dst_size; offset += step) { 250 if (offset + size >= dst_size) { 251 size = -1; // Read through the end of the file. 252 } 253 TEST_AND_RETURN_FALSE(DeltaReadFile(graph, 254 Vertex::kInvalidIndex, 255 blocks, 256 (should_diff_from_source ? 257 old_root : 258 kEmptyPath), 259 new_root, 260 fs_iter.GetPartialPath(), 261 offset, 262 size, 263 data_fd, 264 data_file_size)); 265 } 266 } 267 return true; 268} 269 270// This class allocates non-existent temp blocks, starting from 271// kTempBlockStart. Other code is responsible for converting these 272// temp blocks into real blocks, as the client can't read or write to 273// these blocks. 274class DummyExtentAllocator { 275 public: 276 DummyExtentAllocator() : next_block_(kTempBlockStart) {} 277 vector<Extent> Allocate(const uint64_t block_count) { 278 vector<Extent> ret(1); 279 ret[0].set_start_block(next_block_); 280 ret[0].set_num_blocks(block_count); 281 next_block_ += block_count; 282 return ret; 283 } 284 private: 285 uint64_t next_block_; 286}; 287 288// Reads blocks from image_path that are not yet marked as being written 289// in the blocks array. These blocks that remain are non-file-data blocks. 290// In the future we might consider intelligent diffing between this data 291// and data in the previous image, but for now we just bzip2 compress it 292// and include it in the update. 293// Creates a new node in the graph to write these blocks and writes the 294// appropriate blob to blobs_fd. Reads and updates blobs_length; 295bool ReadUnwrittenBlocks(const vector<Block>& blocks, 296 int blobs_fd, 297 off_t* blobs_length, 298 const string& image_path, 299 Vertex* vertex) { 300 vertex->file_name = "<rootfs-non-file-data>"; 301 302 DeltaArchiveManifest_InstallOperation* out_op = &vertex->op; 303 int image_fd = open(image_path.c_str(), O_RDONLY, 000); 304 TEST_AND_RETURN_FALSE_ERRNO(image_fd >= 0); 305 ScopedFdCloser image_fd_closer(&image_fd); 306 307 string temp_file_path; 308 TEST_AND_RETURN_FALSE(utils::MakeTempFile("CrAU_temp_data.XXXXXX", 309 &temp_file_path, 310 nullptr)); 311 312 FILE* file = fopen(temp_file_path.c_str(), "w"); 313 TEST_AND_RETURN_FALSE(file); 314 int err = BZ_OK; 315 316 BZFILE* bz_file = BZ2_bzWriteOpen(&err, 317 file, 318 9, // max compression 319 0, // verbosity 320 0); // default work factor 321 TEST_AND_RETURN_FALSE(err == BZ_OK); 322 323 vector<Extent> extents; 324 vector<Block>::size_type block_count = 0; 325 326 LOG(INFO) << "Appending left over blocks to extents"; 327 for (vector<Block>::size_type i = 0; i < blocks.size(); i++) { 328 if (blocks[i].writer != Vertex::kInvalidIndex) 329 continue; 330 if (blocks[i].reader != Vertex::kInvalidIndex) { 331 graph_utils::AddReadBeforeDep(vertex, blocks[i].reader, i); 332 } 333 graph_utils::AppendBlockToExtents(&extents, i); 334 block_count++; 335 } 336 337 // Code will handle 'buf' at any size that's a multiple of kBlockSize, 338 // so we arbitrarily set it to 1024 * kBlockSize. 339 vector<char> buf(1024 * kBlockSize); 340 341 LOG(INFO) << "Reading left over blocks"; 342 vector<Block>::size_type blocks_copied_count = 0; 343 344 // For each extent in extents, write the data into BZ2_bzWrite which 345 // sends it to an output file. 346 // We use the temporary buffer 'buf' to hold the data, which may be 347 // smaller than the extent, so in that case we have to loop to get 348 // the extent's data (that's the inner while loop). 349 for (vector<Extent>::const_iterator it = extents.begin(); 350 it != extents.end(); ++it) { 351 vector<Block>::size_type blocks_read = 0; 352 float printed_progress = -1; 353 while (blocks_read < it->num_blocks()) { 354 const int copy_block_cnt = 355 min(buf.size() / kBlockSize, 356 static_cast<vector<char>::size_type>( 357 it->num_blocks() - blocks_read)); 358 ssize_t rc = pread(image_fd, 359 &buf[0], 360 copy_block_cnt * kBlockSize, 361 (it->start_block() + blocks_read) * kBlockSize); 362 TEST_AND_RETURN_FALSE_ERRNO(rc >= 0); 363 TEST_AND_RETURN_FALSE(static_cast<size_t>(rc) == 364 copy_block_cnt * kBlockSize); 365 BZ2_bzWrite(&err, bz_file, &buf[0], copy_block_cnt * kBlockSize); 366 TEST_AND_RETURN_FALSE(err == BZ_OK); 367 blocks_read += copy_block_cnt; 368 blocks_copied_count += copy_block_cnt; 369 float current_progress = 370 static_cast<float>(blocks_copied_count) / block_count; 371 if (printed_progress + 0.1 < current_progress || 372 blocks_copied_count == block_count) { 373 LOG(INFO) << "progress: " << current_progress; 374 printed_progress = current_progress; 375 } 376 } 377 } 378 BZ2_bzWriteClose(&err, bz_file, 0, nullptr, nullptr); 379 TEST_AND_RETURN_FALSE(err == BZ_OK); 380 bz_file = nullptr; 381 TEST_AND_RETURN_FALSE_ERRNO(0 == fclose(file)); 382 file = nullptr; 383 384 vector<char> compressed_data; 385 LOG(INFO) << "Reading compressed data off disk"; 386 TEST_AND_RETURN_FALSE(utils::ReadFile(temp_file_path, &compressed_data)); 387 TEST_AND_RETURN_FALSE(unlink(temp_file_path.c_str()) == 0); 388 389 // Add node to graph to write these blocks 390 out_op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ); 391 out_op->set_data_offset(*blobs_length); 392 out_op->set_data_length(compressed_data.size()); 393 LOG(INFO) << "Rootfs non-data blocks compressed take up " 394 << compressed_data.size(); 395 *blobs_length += compressed_data.size(); 396 out_op->set_dst_length(kBlockSize * block_count); 397 DeltaDiffGenerator::StoreExtents(extents, out_op->mutable_dst_extents()); 398 399 TEST_AND_RETURN_FALSE(utils::WriteAll(blobs_fd, 400 &compressed_data[0], 401 compressed_data.size())); 402 LOG(INFO) << "done with extra blocks"; 403 return true; 404} 405 406// Writes the uint64_t passed in in host-endian to the file as big-endian. 407// Returns true on success. 408bool WriteUint64AsBigEndian(FileWriter* writer, const uint64_t value) { 409 uint64_t value_be = htobe64(value); 410 TEST_AND_RETURN_FALSE(writer->Write(&value_be, sizeof(value_be))); 411 return true; 412} 413 414// Adds each operation from |graph| to |out_manifest| in the order specified by 415// |order| while building |out_op_name_map| with operation to name 416// mappings. Adds all |kernel_ops| to |out_manifest|. Filters out no-op 417// operations. 418void InstallOperationsToManifest( 419 const Graph& graph, 420 const vector<Vertex::Index>& order, 421 const vector<DeltaArchiveManifest_InstallOperation>& kernel_ops, 422 DeltaArchiveManifest* out_manifest, 423 OperationNameMap* out_op_name_map) { 424 for (vector<Vertex::Index>::const_iterator it = order.begin(); 425 it != order.end(); ++it) { 426 const Vertex& vertex = graph[*it]; 427 const DeltaArchiveManifest_InstallOperation& add_op = vertex.op; 428 if (DeltaDiffGenerator::IsNoopOperation(add_op)) { 429 continue; 430 } 431 DeltaArchiveManifest_InstallOperation* op = 432 out_manifest->add_install_operations(); 433 *op = add_op; 434 string name = vertex.file_name; 435 if (vertex.chunk_offset || vertex.chunk_size != -1) { 436 string offset = base::Int64ToString(vertex.chunk_offset); 437 if (vertex.chunk_size != -1) { 438 name += " [" + offset + ", " + 439 base::Int64ToString(vertex.chunk_offset + vertex.chunk_size - 1) + 440 "]"; 441 } else { 442 name += " [" + offset + ", end]"; 443 } 444 } 445 (*out_op_name_map)[op] = name; 446 } 447 for (vector<DeltaArchiveManifest_InstallOperation>::const_iterator it = 448 kernel_ops.begin(); it != kernel_ops.end(); ++it) { 449 const DeltaArchiveManifest_InstallOperation& add_op = *it; 450 if (DeltaDiffGenerator::IsNoopOperation(add_op)) { 451 continue; 452 } 453 DeltaArchiveManifest_InstallOperation* op = 454 out_manifest->add_kernel_install_operations(); 455 *op = add_op; 456 } 457} 458 459void CheckGraph(const Graph& graph) { 460 for (Graph::const_iterator it = graph.begin(); it != graph.end(); ++it) { 461 CHECK(it->op.has_type()); 462 } 463} 464 465// Delta compresses a kernel partition |new_kernel_part| with knowledge of the 466// old kernel partition |old_kernel_part|. If |old_kernel_part| is an empty 467// string, generates a full update of the partition. 468bool DeltaCompressKernelPartition( 469 const string& old_kernel_part, 470 const string& new_kernel_part, 471 vector<DeltaArchiveManifest_InstallOperation>* ops, 472 int blobs_fd, 473 off_t* blobs_length) { 474 LOG(INFO) << "Delta compressing kernel partition..."; 475 LOG_IF(INFO, old_kernel_part.empty()) << "Generating full kernel update..."; 476 477 DeltaArchiveManifest_InstallOperation op; 478 vector<char> data; 479 TEST_AND_RETURN_FALSE( 480 DeltaDiffGenerator::ReadFileToDiff(old_kernel_part, 481 new_kernel_part, 482 0, // chunk_offset 483 -1, // chunk_size 484 true, // bsdiff_allowed 485 &data, 486 &op, 487 false)); 488 489 // Check if the operation writes nothing. 490 if (op.dst_extents_size() == 0) { 491 if (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) { 492 LOG(INFO) << "Empty MOVE operation, nothing to do."; 493 return true; 494 } else { 495 LOG(ERROR) << "Empty non-MOVE operation"; 496 return false; 497 } 498 } 499 500 // Write the data. 501 if (op.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) { 502 op.set_data_offset(*blobs_length); 503 op.set_data_length(data.size()); 504 } 505 506 // Add the new install operation. 507 ops->clear(); 508 ops->push_back(op); 509 510 TEST_AND_RETURN_FALSE(utils::WriteAll(blobs_fd, &data[0], data.size())); 511 *blobs_length += data.size(); 512 513 LOG(INFO) << "Done delta compressing kernel partition: " 514 << kInstallOperationTypes[op.type()]; 515 return true; 516} 517 518struct DeltaObject { 519 DeltaObject(const string& in_name, const int in_type, const off_t in_size) 520 : name(in_name), 521 type(in_type), 522 size(in_size) {} 523 bool operator <(const DeltaObject& object) const { 524 return (size != object.size) ? (size < object.size) : (name < object.name); 525 } 526 string name; 527 int type; 528 off_t size; 529}; 530 531void ReportPayloadUsage(const DeltaArchiveManifest& manifest, 532 const int64_t manifest_metadata_size, 533 const OperationNameMap& op_name_map) { 534 vector<DeltaObject> objects; 535 off_t total_size = 0; 536 537 // Rootfs install operations. 538 for (int i = 0; i < manifest.install_operations_size(); ++i) { 539 const DeltaArchiveManifest_InstallOperation& op = 540 manifest.install_operations(i); 541 objects.push_back(DeltaObject(op_name_map.find(&op)->second, 542 op.type(), 543 op.data_length())); 544 total_size += op.data_length(); 545 } 546 547 // Kernel install operations. 548 for (int i = 0; i < manifest.kernel_install_operations_size(); ++i) { 549 const DeltaArchiveManifest_InstallOperation& op = 550 manifest.kernel_install_operations(i); 551 objects.push_back(DeltaObject(base::StringPrintf("<kernel-operation-%d>", 552 i), 553 op.type(), 554 op.data_length())); 555 total_size += op.data_length(); 556 } 557 558 objects.push_back(DeltaObject("<manifest-metadata>", 559 -1, 560 manifest_metadata_size)); 561 total_size += manifest_metadata_size; 562 563 std::sort(objects.begin(), objects.end()); 564 565 static const char kFormatString[] = "%6.2f%% %10jd %-10s %s\n"; 566 for (vector<DeltaObject>::const_iterator it = objects.begin(); 567 it != objects.end(); ++it) { 568 const DeltaObject& object = *it; 569 fprintf(stderr, kFormatString, 570 object.size * 100.0 / total_size, 571 static_cast<intmax_t>(object.size), 572 object.type >= 0 ? kInstallOperationTypes[object.type] : "-", 573 object.name.c_str()); 574 } 575 fprintf(stderr, kFormatString, 576 100.0, static_cast<intmax_t>(total_size), "", "<total>"); 577} 578 579// Process a range of blocks from |range_start| to |range_end| in the extent at 580// position |*idx_p| of |extents|. If |do_remove| is true, this range will be 581// removed, which may cause the extent to be trimmed, split or removed entirely. 582// The value of |*idx_p| is updated to point to the next extent to be processed. 583// Returns true iff the next extent to process is a new or updated one. 584bool ProcessExtentBlockRange(vector<Extent>* extents, size_t* idx_p, 585 const bool do_remove, uint64_t range_start, 586 uint64_t range_end) { 587 size_t idx = *idx_p; 588 uint64_t start_block = (*extents)[idx].start_block(); 589 uint64_t num_blocks = (*extents)[idx].num_blocks(); 590 uint64_t range_size = range_end - range_start; 591 592 if (do_remove) { 593 if (range_size == num_blocks) { 594 // Remove the entire extent. 595 extents->erase(extents->begin() + idx); 596 } else if (range_end == num_blocks) { 597 // Trim the end of the extent. 598 (*extents)[idx].set_num_blocks(num_blocks - range_size); 599 idx++; 600 } else if (range_start == 0) { 601 // Trim the head of the extent. 602 (*extents)[idx].set_start_block(start_block + range_size); 603 (*extents)[idx].set_num_blocks(num_blocks - range_size); 604 } else { 605 // Trim the middle, splitting the remainder into two parts. 606 (*extents)[idx].set_num_blocks(range_start); 607 Extent e; 608 e.set_start_block(start_block + range_end); 609 e.set_num_blocks(num_blocks - range_end); 610 idx++; 611 extents->insert(extents->begin() + idx, e); 612 } 613 } else if (range_end == num_blocks) { 614 // Done with this extent. 615 idx++; 616 } else { 617 return false; 618 } 619 620 *idx_p = idx; 621 return true; 622} 623 624// Remove identical corresponding block ranges in |src_extents| and 625// |dst_extents|. Used for preventing moving of blocks onto themselves during 626// MOVE operations. The value of |total_bytes| indicates the actual length of 627// content; this may be slightly less than the total size of blocks, in which 628// case the last block is only partly occupied with data. Returns the total 629// number of bytes removed. 630size_t RemoveIdenticalBlockRanges(vector<Extent>* src_extents, 631 vector<Extent>* dst_extents, 632 const size_t total_bytes) { 633 size_t src_idx = 0; 634 size_t dst_idx = 0; 635 uint64_t src_offset = 0, dst_offset = 0; 636 bool new_src = true, new_dst = true; 637 size_t removed_bytes = 0, nonfull_block_bytes; 638 bool do_remove = false; 639 while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) { 640 if (new_src) { 641 src_offset = 0; 642 new_src = false; 643 } 644 if (new_dst) { 645 dst_offset = 0; 646 new_dst = false; 647 } 648 649 do_remove = ((*src_extents)[src_idx].start_block() + src_offset == 650 (*dst_extents)[dst_idx].start_block() + dst_offset); 651 652 uint64_t src_num_blocks = (*src_extents)[src_idx].num_blocks(); 653 uint64_t dst_num_blocks = (*dst_extents)[dst_idx].num_blocks(); 654 uint64_t min_num_blocks = min(src_num_blocks - src_offset, 655 dst_num_blocks - dst_offset); 656 uint64_t prev_src_offset = src_offset; 657 uint64_t prev_dst_offset = dst_offset; 658 src_offset += min_num_blocks; 659 dst_offset += min_num_blocks; 660 661 new_src = ProcessExtentBlockRange(src_extents, &src_idx, do_remove, 662 prev_src_offset, src_offset); 663 new_dst = ProcessExtentBlockRange(dst_extents, &dst_idx, do_remove, 664 prev_dst_offset, dst_offset); 665 if (do_remove) 666 removed_bytes += min_num_blocks * kBlockSize; 667 } 668 669 // If we removed the last block and this block is only partly used by file 670 // content, deduct the unused portion from the total removed byte count. 671 if (do_remove && (nonfull_block_bytes = total_bytes % kBlockSize)) 672 removed_bytes -= kBlockSize - nonfull_block_bytes; 673 674 return removed_bytes; 675} 676 677} // namespace 678 679bool DeltaDiffGenerator::ReadFileToDiff( 680 const string& old_filename, 681 const string& new_filename, 682 off_t chunk_offset, 683 off_t chunk_size, 684 bool bsdiff_allowed, 685 vector<char>* out_data, 686 DeltaArchiveManifest_InstallOperation* out_op, 687 bool gather_extents) { 688 // Read new data in 689 vector<char> new_data; 690 TEST_AND_RETURN_FALSE( 691 utils::ReadFileChunk(new_filename, chunk_offset, chunk_size, &new_data)); 692 693 TEST_AND_RETURN_FALSE(!new_data.empty()); 694 TEST_AND_RETURN_FALSE(chunk_size == -1 || 695 static_cast<off_t>(new_data.size()) <= chunk_size); 696 697 vector<char> new_data_bz; 698 TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz)); 699 CHECK(!new_data_bz.empty()); 700 701 vector<char> data; // Data blob that will be written to delta file. 702 703 DeltaArchiveManifest_InstallOperation operation; 704 size_t current_best_size = 0; 705 if (new_data.size() <= new_data_bz.size()) { 706 operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE); 707 current_best_size = new_data.size(); 708 data = new_data; 709 } else { 710 operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ); 711 current_best_size = new_data_bz.size(); 712 data = new_data_bz; 713 } 714 715 // Do we have an original file to consider? 716 off_t old_size = 0; 717 bool original = !old_filename.empty(); 718 if (original && (old_size = utils::FileSize(old_filename)) < 0) { 719 // If stat-ing the old file fails, it should be because it doesn't exist. 720 TEST_AND_RETURN_FALSE(!utils::FileExists(old_filename.c_str())); 721 original = false; 722 } 723 724 vector<char> old_data; 725 if (original) { 726 // Read old data 727 TEST_AND_RETURN_FALSE( 728 utils::ReadFileChunk( 729 old_filename, chunk_offset, chunk_size, &old_data)); 730 if (old_data == new_data) { 731 // No change in data. 732 operation.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE); 733 current_best_size = 0; 734 data.clear(); 735 } else if (!old_data.empty() && bsdiff_allowed) { 736 // If the source file is considered bsdiff safe (no bsdiff bugs 737 // triggered), see if BSDIFF encoding is smaller. 738 base::FilePath old_chunk; 739 TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&old_chunk)); 740 ScopedPathUnlinker old_unlinker(old_chunk.value()); 741 TEST_AND_RETURN_FALSE( 742 utils::WriteFile(old_chunk.value().c_str(), 743 &old_data[0], old_data.size())); 744 base::FilePath new_chunk; 745 TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&new_chunk)); 746 ScopedPathUnlinker new_unlinker(new_chunk.value()); 747 TEST_AND_RETURN_FALSE( 748 utils::WriteFile(new_chunk.value().c_str(), 749 &new_data[0], new_data.size())); 750 751 vector<char> bsdiff_delta; 752 TEST_AND_RETURN_FALSE( 753 BsdiffFiles(old_chunk.value(), new_chunk.value(), &bsdiff_delta)); 754 CHECK_GT(bsdiff_delta.size(), static_cast<vector<char>::size_type>(0)); 755 if (bsdiff_delta.size() < current_best_size) { 756 operation.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF); 757 current_best_size = bsdiff_delta.size(); 758 data = bsdiff_delta; 759 } 760 } 761 } 762 763 // Set parameters of the operations 764 CHECK_EQ(data.size(), current_best_size); 765 766 vector<Extent> src_extents, dst_extents; 767 if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE || 768 operation.type() == DeltaArchiveManifest_InstallOperation_Type_BSDIFF) { 769 if (gather_extents) { 770 TEST_AND_RETURN_FALSE( 771 GatherExtents(old_filename, 772 chunk_offset, 773 chunk_size, 774 &src_extents)); 775 } else { 776 Extent* src_extent = operation.add_src_extents(); 777 src_extent->set_start_block(0); 778 src_extent->set_num_blocks((old_size + kBlockSize - 1) / kBlockSize); 779 } 780 operation.set_src_length(old_data.size()); 781 } 782 783 if (gather_extents) { 784 TEST_AND_RETURN_FALSE( 785 GatherExtents(new_filename, 786 chunk_offset, 787 chunk_size, 788 &dst_extents)); 789 } else { 790 Extent* dst_extent = operation.add_dst_extents(); 791 dst_extent->set_start_block(0); 792 dst_extent->set_num_blocks((new_data.size() + kBlockSize - 1) / kBlockSize); 793 } 794 operation.set_dst_length(new_data.size()); 795 796 if (gather_extents) { 797 // Remove identical src/dst block ranges in MOVE operations. 798 if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) { 799 size_t removed_bytes = RemoveIdenticalBlockRanges( 800 &src_extents, &dst_extents, new_data.size()); 801 802 // Adjust the file length field accordingly. 803 if (removed_bytes) { 804 operation.set_src_length(old_data.size() - removed_bytes); 805 operation.set_dst_length(new_data.size() - removed_bytes); 806 } 807 } 808 809 // Embed extents in the operation. 810 DeltaDiffGenerator::StoreExtents(src_extents, 811 operation.mutable_src_extents()); 812 DeltaDiffGenerator::StoreExtents(dst_extents, 813 operation.mutable_dst_extents()); 814 } 815 816 out_data->swap(data); 817 *out_op = operation; 818 819 return true; 820} 821 822bool DeltaDiffGenerator::InitializePartitionInfo(bool is_kernel, 823 const string& partition, 824 PartitionInfo* info) { 825 int64_t size = 0; 826 if (is_kernel) { 827 size = utils::FileSize(partition); 828 } else { 829 int block_count = 0, block_size = 0; 830 TEST_AND_RETURN_FALSE(utils::GetFilesystemSize(partition, 831 &block_count, 832 &block_size)); 833 size = static_cast<int64_t>(block_count) * block_size; 834 } 835 TEST_AND_RETURN_FALSE(size > 0); 836 info->set_size(size); 837 OmahaHashCalculator hasher; 838 TEST_AND_RETURN_FALSE(hasher.UpdateFile(partition, size) == size); 839 TEST_AND_RETURN_FALSE(hasher.Finalize()); 840 const vector<char>& hash = hasher.raw_hash(); 841 info->set_hash(hash.data(), hash.size()); 842 LOG(INFO) << partition << ": size=" << size << " hash=" << hasher.hash(); 843 return true; 844} 845 846bool InitializePartitionInfos(const string& old_kernel, 847 const string& new_kernel, 848 const string& old_rootfs, 849 const string& new_rootfs, 850 DeltaArchiveManifest* manifest) { 851 if (!old_kernel.empty()) { 852 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo( 853 true, 854 old_kernel, 855 manifest->mutable_old_kernel_info())); 856 } 857 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo( 858 true, 859 new_kernel, 860 manifest->mutable_new_kernel_info())); 861 if (!old_rootfs.empty()) { 862 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo( 863 false, 864 old_rootfs, 865 manifest->mutable_old_rootfs_info())); 866 } 867 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo( 868 false, 869 new_rootfs, 870 manifest->mutable_new_rootfs_info())); 871 return true; 872} 873 874namespace { 875 876// Takes a collection (vector or RepeatedPtrField) of Extent and 877// returns a vector of the blocks referenced, in order. 878template<typename T> 879vector<uint64_t> ExpandExtents(const T& extents) { 880 vector<uint64_t> ret; 881 for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) { 882 const Extent extent = graph_utils::GetElement(extents, i); 883 if (extent.start_block() == kSparseHole) { 884 ret.resize(ret.size() + extent.num_blocks(), kSparseHole); 885 } else { 886 for (uint64_t block = extent.start_block(); 887 block < (extent.start_block() + extent.num_blocks()); block++) { 888 ret.push_back(block); 889 } 890 } 891 } 892 return ret; 893} 894 895// Takes a vector of blocks and returns an equivalent vector of Extent 896// objects. 897vector<Extent> CompressExtents(const vector<uint64_t>& blocks) { 898 vector<Extent> new_extents; 899 for (vector<uint64_t>::const_iterator it = blocks.begin(), e = blocks.end(); 900 it != e; ++it) { 901 graph_utils::AppendBlockToExtents(&new_extents, *it); 902 } 903 return new_extents; 904} 905 906} // namespace 907 908void DeltaDiffGenerator::SubstituteBlocks( 909 Vertex* vertex, 910 const vector<Extent>& remove_extents, 911 const vector<Extent>& replace_extents) { 912 // First, expand out the blocks that op reads from 913 vector<uint64_t> read_blocks = ExpandExtents(vertex->op.src_extents()); 914 { 915 // Expand remove_extents and replace_extents 916 vector<uint64_t> remove_extents_expanded = 917 ExpandExtents(remove_extents); 918 vector<uint64_t> replace_extents_expanded = 919 ExpandExtents(replace_extents); 920 CHECK_EQ(remove_extents_expanded.size(), replace_extents_expanded.size()); 921 map<uint64_t, uint64_t> conversion; 922 for (vector<uint64_t>::size_type i = 0; 923 i < replace_extents_expanded.size(); i++) { 924 conversion[remove_extents_expanded[i]] = replace_extents_expanded[i]; 925 } 926 utils::ApplyMap(&read_blocks, conversion); 927 for (Vertex::EdgeMap::iterator it = vertex->out_edges.begin(), 928 e = vertex->out_edges.end(); it != e; ++it) { 929 vector<uint64_t> write_before_deps_expanded = 930 ExpandExtents(it->second.write_extents); 931 utils::ApplyMap(&write_before_deps_expanded, conversion); 932 it->second.write_extents = CompressExtents(write_before_deps_expanded); 933 } 934 } 935 // Convert read_blocks back to extents 936 vertex->op.clear_src_extents(); 937 vector<Extent> new_extents = CompressExtents(read_blocks); 938 DeltaDiffGenerator::StoreExtents(new_extents, 939 vertex->op.mutable_src_extents()); 940} 941 942bool DeltaDiffGenerator::CutEdges(Graph* graph, 943 const set<Edge>& edges, 944 vector<CutEdgeVertexes>* out_cuts) { 945 DummyExtentAllocator scratch_allocator; 946 vector<CutEdgeVertexes> cuts; 947 cuts.reserve(edges.size()); 948 949 uint64_t scratch_blocks_used = 0; 950 for (set<Edge>::const_iterator it = edges.begin(); 951 it != edges.end(); ++it) { 952 cuts.resize(cuts.size() + 1); 953 vector<Extent> old_extents = 954 (*graph)[it->first].out_edges[it->second].extents; 955 // Choose some scratch space 956 scratch_blocks_used += graph_utils::EdgeWeight(*graph, *it); 957 cuts.back().tmp_extents = 958 scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, *it)); 959 // create vertex to copy original->scratch 960 cuts.back().new_vertex = graph->size(); 961 graph->resize(graph->size() + 1); 962 cuts.back().old_src = it->first; 963 cuts.back().old_dst = it->second; 964 965 EdgeProperties& cut_edge_properties = 966 (*graph)[it->first].out_edges.find(it->second)->second; 967 968 // This should never happen, as we should only be cutting edges between 969 // real file nodes, and write-before relationships are created from 970 // a real file node to a temp copy node: 971 CHECK(cut_edge_properties.write_extents.empty()) 972 << "Can't cut edge that has write-before relationship."; 973 974 // make node depend on the copy operation 975 (*graph)[it->first].out_edges.insert(make_pair(graph->size() - 1, 976 cut_edge_properties)); 977 978 // Set src/dst extents and other proto variables for copy operation 979 graph->back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE); 980 DeltaDiffGenerator::StoreExtents( 981 cut_edge_properties.extents, 982 graph->back().op.mutable_src_extents()); 983 DeltaDiffGenerator::StoreExtents(cuts.back().tmp_extents, 984 graph->back().op.mutable_dst_extents()); 985 graph->back().op.set_src_length( 986 graph_utils::EdgeWeight(*graph, *it) * kBlockSize); 987 graph->back().op.set_dst_length(graph->back().op.src_length()); 988 989 // make the dest node read from the scratch space 990 DeltaDiffGenerator::SubstituteBlocks( 991 &((*graph)[it->second]), 992 (*graph)[it->first].out_edges[it->second].extents, 993 cuts.back().tmp_extents); 994 995 // delete the old edge 996 CHECK_EQ(static_cast<Graph::size_type>(1), 997 (*graph)[it->first].out_edges.erase(it->second)); 998 999 // Add an edge from dst to copy operation 1000 EdgeProperties write_before_edge_properties; 1001 write_before_edge_properties.write_extents = cuts.back().tmp_extents; 1002 (*graph)[it->second].out_edges.insert( 1003 make_pair(graph->size() - 1, write_before_edge_properties)); 1004 } 1005 out_cuts->swap(cuts); 1006 return true; 1007} 1008 1009// Stores all Extents in 'extents' into 'out'. 1010void DeltaDiffGenerator::StoreExtents( 1011 const vector<Extent>& extents, 1012 google::protobuf::RepeatedPtrField<Extent>* out) { 1013 for (vector<Extent>::const_iterator it = extents.begin(); 1014 it != extents.end(); ++it) { 1015 Extent* new_extent = out->Add(); 1016 *new_extent = *it; 1017 } 1018} 1019 1020// Creates all the edges for the graph. Writers of a block point to 1021// readers of the same block. This is because for an edge A->B, B 1022// must complete before A executes. 1023void DeltaDiffGenerator::CreateEdges(Graph* graph, 1024 const vector<Block>& blocks) { 1025 for (vector<Block>::size_type i = 0; i < blocks.size(); i++) { 1026 // Blocks with both a reader and writer get an edge 1027 if (blocks[i].reader == Vertex::kInvalidIndex || 1028 blocks[i].writer == Vertex::kInvalidIndex) 1029 continue; 1030 // Don't have a node depend on itself 1031 if (blocks[i].reader == blocks[i].writer) 1032 continue; 1033 // See if there's already an edge we can add onto 1034 Vertex::EdgeMap::iterator edge_it = 1035 (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader); 1036 if (edge_it == (*graph)[blocks[i].writer].out_edges.end()) { 1037 // No existing edge. Create one 1038 (*graph)[blocks[i].writer].out_edges.insert( 1039 make_pair(blocks[i].reader, EdgeProperties())); 1040 edge_it = (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader); 1041 CHECK(edge_it != (*graph)[blocks[i].writer].out_edges.end()); 1042 } 1043 graph_utils::AppendBlockToExtents(&edge_it->second.extents, i); 1044 } 1045} 1046 1047namespace { 1048 1049class SortCutsByTopoOrderLess { 1050 public: 1051 explicit SortCutsByTopoOrderLess( 1052 const vector<vector<Vertex::Index>::size_type>& table) 1053 : table_(table) {} 1054 bool operator()(const CutEdgeVertexes& a, const CutEdgeVertexes& b) { 1055 return table_[a.old_dst] < table_[b.old_dst]; 1056 } 1057 private: 1058 const vector<vector<Vertex::Index>::size_type>& table_; 1059}; 1060 1061} // namespace 1062 1063void DeltaDiffGenerator::GenerateReverseTopoOrderMap( 1064 const vector<Vertex::Index>& op_indexes, 1065 vector<vector<Vertex::Index>::size_type>* reverse_op_indexes) { 1066 vector<vector<Vertex::Index>::size_type> table(op_indexes.size()); 1067 for (vector<Vertex::Index>::size_type i = 0, e = op_indexes.size(); 1068 i != e; ++i) { 1069 Vertex::Index node = op_indexes[i]; 1070 if (table.size() < (node + 1)) { 1071 table.resize(node + 1); 1072 } 1073 table[node] = i; 1074 } 1075 reverse_op_indexes->swap(table); 1076} 1077 1078void DeltaDiffGenerator::SortCutsByTopoOrder( 1079 const vector<Vertex::Index>& op_indexes, 1080 vector<CutEdgeVertexes>* cuts) { 1081 // first, make a reverse lookup table. 1082 vector<vector<Vertex::Index>::size_type> table; 1083 GenerateReverseTopoOrderMap(op_indexes, &table); 1084 SortCutsByTopoOrderLess less(table); 1085 sort(cuts->begin(), cuts->end(), less); 1086} 1087 1088void DeltaDiffGenerator::MoveFullOpsToBack(Graph* graph, 1089 vector<Vertex::Index>* op_indexes) { 1090 vector<Vertex::Index> ret; 1091 vector<Vertex::Index> full_ops; 1092 ret.reserve(op_indexes->size()); 1093 for (vector<Vertex::Index>::size_type i = 0, e = op_indexes->size(); i != e; 1094 ++i) { 1095 DeltaArchiveManifest_InstallOperation_Type type = 1096 (*graph)[(*op_indexes)[i]].op.type(); 1097 if (type == DeltaArchiveManifest_InstallOperation_Type_REPLACE || 1098 type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) { 1099 full_ops.push_back((*op_indexes)[i]); 1100 } else { 1101 ret.push_back((*op_indexes)[i]); 1102 } 1103 } 1104 LOG(INFO) << "Stats: " << full_ops.size() << " full ops out of " 1105 << (full_ops.size() + ret.size()) << " total ops."; 1106 ret.insert(ret.end(), full_ops.begin(), full_ops.end()); 1107 op_indexes->swap(ret); 1108} 1109 1110namespace { 1111 1112template<typename T> 1113bool TempBlocksExistInExtents(const T& extents) { 1114 for (int i = 0, e = extents.size(); i < e; ++i) { 1115 Extent extent = graph_utils::GetElement(extents, i); 1116 uint64_t start = extent.start_block(); 1117 uint64_t num = extent.num_blocks(); 1118 if (start == kSparseHole) 1119 continue; 1120 if (start >= kTempBlockStart || 1121 (start + num) >= kTempBlockStart) { 1122 LOG(ERROR) << "temp block!"; 1123 LOG(ERROR) << "start: " << start << ", num: " << num; 1124 LOG(ERROR) << "kTempBlockStart: " << kTempBlockStart; 1125 LOG(ERROR) << "returning true"; 1126 return true; 1127 } 1128 // check for wrap-around, which would be a bug: 1129 CHECK(start <= (start + num)); 1130 } 1131 return false; 1132} 1133 1134// Converts the cuts, which must all have the same |old_dst| member, 1135// to full. It does this by converting the |old_dst| to REPLACE or 1136// REPLACE_BZ, dropping all incoming edges to |old_dst|, and marking 1137// all temp nodes invalid. 1138bool ConvertCutsToFull( 1139 Graph* graph, 1140 const string& new_root, 1141 int data_fd, 1142 off_t* data_file_size, 1143 vector<Vertex::Index>* op_indexes, 1144 vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, 1145 const vector<CutEdgeVertexes>& cuts) { 1146 CHECK(!cuts.empty()); 1147 set<Vertex::Index> deleted_nodes; 1148 for (vector<CutEdgeVertexes>::const_iterator it = cuts.begin(), 1149 e = cuts.end(); it != e; ++it) { 1150 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ConvertCutToFullOp( 1151 graph, 1152 *it, 1153 new_root, 1154 data_fd, 1155 data_file_size)); 1156 deleted_nodes.insert(it->new_vertex); 1157 } 1158 deleted_nodes.insert(cuts[0].old_dst); 1159 1160 vector<Vertex::Index> new_op_indexes; 1161 new_op_indexes.reserve(op_indexes->size()); 1162 for (vector<Vertex::Index>::iterator it = op_indexes->begin(), 1163 e = op_indexes->end(); it != e; ++it) { 1164 if (utils::SetContainsKey(deleted_nodes, *it)) 1165 continue; 1166 new_op_indexes.push_back(*it); 1167 } 1168 new_op_indexes.push_back(cuts[0].old_dst); 1169 op_indexes->swap(new_op_indexes); 1170 DeltaDiffGenerator::GenerateReverseTopoOrderMap(*op_indexes, 1171 reverse_op_indexes); 1172 return true; 1173} 1174 1175// Tries to assign temp blocks for a collection of cuts, all of which share 1176// the same old_dst member. If temp blocks can't be found, old_dst will be 1177// converted to a REPLACE or REPLACE_BZ operation. Returns true on success, 1178// which can happen even if blocks are converted to full. Returns false 1179// on exceptional error cases. 1180bool AssignBlockForAdjoiningCuts( 1181 Graph* graph, 1182 const string& new_root, 1183 int data_fd, 1184 off_t* data_file_size, 1185 vector<Vertex::Index>* op_indexes, 1186 vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, 1187 const vector<CutEdgeVertexes>& cuts) { 1188 CHECK(!cuts.empty()); 1189 const Vertex::Index old_dst = cuts[0].old_dst; 1190 // Calculate # of blocks needed 1191 uint64_t blocks_needed = 0; 1192 map<const CutEdgeVertexes*, uint64_t> cuts_blocks_needed; 1193 for (vector<CutEdgeVertexes>::const_iterator it = cuts.begin(), 1194 e = cuts.end(); it != e; ++it) { 1195 uint64_t cut_blocks_needed = 0; 1196 for (vector<Extent>::const_iterator jt = it->tmp_extents.begin(), 1197 je = it->tmp_extents.end(); jt != je; ++jt) { 1198 cut_blocks_needed += jt->num_blocks(); 1199 } 1200 blocks_needed += cut_blocks_needed; 1201 cuts_blocks_needed[&*it] = cut_blocks_needed; 1202 } 1203 1204 // Find enough blocks 1205 ExtentRanges scratch_ranges; 1206 // Each block that's supplying temp blocks and the corresponding blocks: 1207 typedef vector<pair<Vertex::Index, ExtentRanges>> SupplierVector; 1208 SupplierVector block_suppliers; 1209 uint64_t scratch_blocks_found = 0; 1210 for (vector<Vertex::Index>::size_type i = (*reverse_op_indexes)[old_dst] + 1, 1211 e = op_indexes->size(); i < e; ++i) { 1212 Vertex::Index test_node = (*op_indexes)[i]; 1213 if (!(*graph)[test_node].valid) 1214 continue; 1215 // See if this node has sufficient blocks 1216 ExtentRanges ranges; 1217 ranges.AddRepeatedExtents((*graph)[test_node].op.dst_extents()); 1218 ranges.SubtractExtent(ExtentForRange( 1219 kTempBlockStart, kSparseHole - kTempBlockStart)); 1220 ranges.SubtractRepeatedExtents((*graph)[test_node].op.src_extents()); 1221 // For now, for simplicity, subtract out all blocks in read-before 1222 // dependencies. 1223 for (Vertex::EdgeMap::const_iterator edge_i = 1224 (*graph)[test_node].out_edges.begin(), 1225 edge_e = (*graph)[test_node].out_edges.end(); 1226 edge_i != edge_e; ++edge_i) { 1227 ranges.SubtractExtents(edge_i->second.extents); 1228 } 1229 if (ranges.blocks() == 0) 1230 continue; 1231 1232 if (ranges.blocks() + scratch_blocks_found > blocks_needed) { 1233 // trim down ranges 1234 vector<Extent> new_ranges = ranges.GetExtentsForBlockCount( 1235 blocks_needed - scratch_blocks_found); 1236 ranges = ExtentRanges(); 1237 ranges.AddExtents(new_ranges); 1238 } 1239 scratch_ranges.AddRanges(ranges); 1240 block_suppliers.push_back(make_pair(test_node, ranges)); 1241 scratch_blocks_found += ranges.blocks(); 1242 if (scratch_ranges.blocks() >= blocks_needed) 1243 break; 1244 } 1245 if (scratch_ranges.blocks() < blocks_needed) { 1246 LOG(INFO) << "Unable to find sufficient scratch"; 1247 TEST_AND_RETURN_FALSE(ConvertCutsToFull(graph, 1248 new_root, 1249 data_fd, 1250 data_file_size, 1251 op_indexes, 1252 reverse_op_indexes, 1253 cuts)); 1254 return true; 1255 } 1256 // Use the scratch we found 1257 TEST_AND_RETURN_FALSE(scratch_ranges.blocks() == scratch_blocks_found); 1258 1259 // Make all the suppliers depend on this node 1260 for (SupplierVector::iterator it = block_suppliers.begin(), 1261 e = block_suppliers.end(); it != e; ++it) { 1262 graph_utils::AddReadBeforeDepExtents( 1263 &(*graph)[it->first], 1264 old_dst, 1265 it->second.GetExtentsForBlockCount(it->second.blocks())); 1266 } 1267 1268 // Replace temp blocks in each cut 1269 for (vector<CutEdgeVertexes>::const_iterator it = cuts.begin(), 1270 e = cuts.end(); it != e; ++it) { 1271 vector<Extent> real_extents = 1272 scratch_ranges.GetExtentsForBlockCount(cuts_blocks_needed[&*it]); 1273 scratch_ranges.SubtractExtents(real_extents); 1274 1275 // Fix the old dest node w/ the real blocks 1276 DeltaDiffGenerator::SubstituteBlocks(&(*graph)[old_dst], 1277 it->tmp_extents, 1278 real_extents); 1279 1280 // Fix the new node w/ the real blocks. Since the new node is just a 1281 // copy operation, we can replace all the dest extents w/ the real 1282 // blocks. 1283 DeltaArchiveManifest_InstallOperation *op = 1284 &(*graph)[it->new_vertex].op; 1285 op->clear_dst_extents(); 1286 DeltaDiffGenerator::StoreExtents(real_extents, op->mutable_dst_extents()); 1287 } 1288 return true; 1289} 1290 1291} // namespace 1292 1293// Returns true if |op| is a no-op operation that doesn't do any useful work 1294// (e.g., a move operation that copies blocks onto themselves). 1295bool DeltaDiffGenerator::IsNoopOperation( 1296 const DeltaArchiveManifest_InstallOperation& op) { 1297 return (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE && 1298 ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents())); 1299} 1300 1301bool DeltaDiffGenerator::AssignTempBlocks( 1302 Graph* graph, 1303 const string& new_root, 1304 int data_fd, 1305 off_t* data_file_size, 1306 vector<Vertex::Index>* op_indexes, 1307 vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, 1308 const vector<CutEdgeVertexes>& cuts) { 1309 CHECK(!cuts.empty()); 1310 1311 // group of cuts w/ the same old_dst: 1312 vector<CutEdgeVertexes> cuts_group; 1313 1314 for (vector<CutEdgeVertexes>::size_type i = cuts.size() - 1, e = 0; 1315 true ; --i) { 1316 LOG(INFO) << "Fixing temp blocks in cut " << i 1317 << ": old dst: " << cuts[i].old_dst << " new vertex: " 1318 << cuts[i].new_vertex << " path: " 1319 << (*graph)[cuts[i].old_dst].file_name; 1320 1321 if (cuts_group.empty() || (cuts_group[0].old_dst == cuts[i].old_dst)) { 1322 cuts_group.push_back(cuts[i]); 1323 } else { 1324 CHECK(!cuts_group.empty()); 1325 TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph, 1326 new_root, 1327 data_fd, 1328 data_file_size, 1329 op_indexes, 1330 reverse_op_indexes, 1331 cuts_group)); 1332 cuts_group.clear(); 1333 cuts_group.push_back(cuts[i]); 1334 } 1335 1336 if (i == e) { 1337 // break out of for() loop 1338 break; 1339 } 1340 } 1341 CHECK(!cuts_group.empty()); 1342 TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph, 1343 new_root, 1344 data_fd, 1345 data_file_size, 1346 op_indexes, 1347 reverse_op_indexes, 1348 cuts_group)); 1349 return true; 1350} 1351 1352bool DeltaDiffGenerator::NoTempBlocksRemain(const Graph& graph) { 1353 size_t idx = 0; 1354 for (Graph::const_iterator it = graph.begin(), e = graph.end(); it != e; 1355 ++it, ++idx) { 1356 if (!it->valid) 1357 continue; 1358 const DeltaArchiveManifest_InstallOperation& op = it->op; 1359 if (TempBlocksExistInExtents(op.dst_extents()) || 1360 TempBlocksExistInExtents(op.src_extents())) { 1361 LOG(INFO) << "bad extents in node " << idx; 1362 LOG(INFO) << "so yeah"; 1363 return false; 1364 } 1365 1366 // Check out-edges: 1367 for (Vertex::EdgeMap::const_iterator jt = it->out_edges.begin(), 1368 je = it->out_edges.end(); jt != je; ++jt) { 1369 if (TempBlocksExistInExtents(jt->second.extents) || 1370 TempBlocksExistInExtents(jt->second.write_extents)) { 1371 LOG(INFO) << "bad out edge in node " << idx; 1372 LOG(INFO) << "so yeah"; 1373 return false; 1374 } 1375 } 1376 } 1377 return true; 1378} 1379 1380bool DeltaDiffGenerator::ReorderDataBlobs( 1381 DeltaArchiveManifest* manifest, 1382 const string& data_blobs_path, 1383 const string& new_data_blobs_path) { 1384 int in_fd = open(data_blobs_path.c_str(), O_RDONLY, 0); 1385 TEST_AND_RETURN_FALSE_ERRNO(in_fd >= 0); 1386 ScopedFdCloser in_fd_closer(&in_fd); 1387 1388 DirectFileWriter writer; 1389 TEST_AND_RETURN_FALSE( 1390 writer.Open(new_data_blobs_path.c_str(), 1391 O_WRONLY | O_TRUNC | O_CREAT, 1392 0644) == 0); 1393 ScopedFileWriterCloser writer_closer(&writer); 1394 uint64_t out_file_size = 0; 1395 1396 for (int i = 0; i < (manifest->install_operations_size() + 1397 manifest->kernel_install_operations_size()); i++) { 1398 DeltaArchiveManifest_InstallOperation* op = nullptr; 1399 if (i < manifest->install_operations_size()) { 1400 op = manifest->mutable_install_operations(i); 1401 } else { 1402 op = manifest->mutable_kernel_install_operations( 1403 i - manifest->install_operations_size()); 1404 } 1405 if (!op->has_data_offset()) 1406 continue; 1407 CHECK(op->has_data_length()); 1408 vector<char> buf(op->data_length()); 1409 ssize_t rc = pread(in_fd, &buf[0], buf.size(), op->data_offset()); 1410 TEST_AND_RETURN_FALSE(rc == static_cast<ssize_t>(buf.size())); 1411 1412 // Add the hash of the data blobs for this operation 1413 TEST_AND_RETURN_FALSE(AddOperationHash(op, buf)); 1414 1415 op->set_data_offset(out_file_size); 1416 TEST_AND_RETURN_FALSE(writer.Write(&buf[0], buf.size())); 1417 out_file_size += buf.size(); 1418 } 1419 return true; 1420} 1421 1422bool DeltaDiffGenerator::AddOperationHash( 1423 DeltaArchiveManifest_InstallOperation* op, 1424 const vector<char>& buf) { 1425 OmahaHashCalculator hasher; 1426 1427 TEST_AND_RETURN_FALSE(hasher.Update(&buf[0], buf.size())); 1428 TEST_AND_RETURN_FALSE(hasher.Finalize()); 1429 1430 const vector<char>& hash = hasher.raw_hash(); 1431 op->set_data_sha256_hash(hash.data(), hash.size()); 1432 return true; 1433} 1434 1435bool DeltaDiffGenerator::ConvertCutToFullOp(Graph* graph, 1436 const CutEdgeVertexes& cut, 1437 const string& new_root, 1438 int data_fd, 1439 off_t* data_file_size) { 1440 // Drop all incoming edges, keep all outgoing edges 1441 1442 // Keep all outgoing edges 1443 if ((*graph)[cut.old_dst].op.type() != 1444 DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ && 1445 (*graph)[cut.old_dst].op.type() != 1446 DeltaArchiveManifest_InstallOperation_Type_REPLACE) { 1447 Vertex::EdgeMap out_edges = (*graph)[cut.old_dst].out_edges; 1448 graph_utils::DropWriteBeforeDeps(&out_edges); 1449 1450 TEST_AND_RETURN_FALSE(DeltaReadFile(graph, 1451 cut.old_dst, 1452 nullptr, 1453 kEmptyPath, 1454 new_root, 1455 (*graph)[cut.old_dst].file_name, 1456 (*graph)[cut.old_dst].chunk_offset, 1457 (*graph)[cut.old_dst].chunk_size, 1458 data_fd, 1459 data_file_size)); 1460 1461 (*graph)[cut.old_dst].out_edges = out_edges; 1462 1463 // Right now we don't have doubly-linked edges, so we have to scan 1464 // the whole graph. 1465 graph_utils::DropIncomingEdgesTo(graph, cut.old_dst); 1466 } 1467 1468 // Delete temp node 1469 (*graph)[cut.old_src].out_edges.erase(cut.new_vertex); 1470 CHECK((*graph)[cut.old_dst].out_edges.find(cut.new_vertex) == 1471 (*graph)[cut.old_dst].out_edges.end()); 1472 (*graph)[cut.new_vertex].valid = false; 1473 LOG(INFO) << "marked node invalid: " << cut.new_vertex; 1474 return true; 1475} 1476 1477bool DeltaDiffGenerator::ConvertGraphToDag(Graph* graph, 1478 const string& new_root, 1479 int fd, 1480 off_t* data_file_size, 1481 vector<Vertex::Index>* final_order, 1482 Vertex::Index scratch_vertex) { 1483 CycleBreaker cycle_breaker; 1484 LOG(INFO) << "Finding cycles..."; 1485 set<Edge> cut_edges; 1486 cycle_breaker.BreakCycles(*graph, &cut_edges); 1487 LOG(INFO) << "done finding cycles"; 1488 CheckGraph(*graph); 1489 1490 // Calculate number of scratch blocks needed 1491 1492 LOG(INFO) << "Cutting cycles..."; 1493 vector<CutEdgeVertexes> cuts; 1494 TEST_AND_RETURN_FALSE(CutEdges(graph, cut_edges, &cuts)); 1495 LOG(INFO) << "done cutting cycles"; 1496 LOG(INFO) << "There are " << cuts.size() << " cuts."; 1497 CheckGraph(*graph); 1498 1499 LOG(INFO) << "Creating initial topological order..."; 1500 TopologicalSort(*graph, final_order); 1501 LOG(INFO) << "done with initial topo order"; 1502 CheckGraph(*graph); 1503 1504 LOG(INFO) << "Moving full ops to the back"; 1505 MoveFullOpsToBack(graph, final_order); 1506 LOG(INFO) << "done moving full ops to back"; 1507 1508 vector<vector<Vertex::Index>::size_type> inverse_final_order; 1509 GenerateReverseTopoOrderMap(*final_order, &inverse_final_order); 1510 1511 SortCutsByTopoOrder(*final_order, &cuts); 1512 1513 if (!cuts.empty()) 1514 TEST_AND_RETURN_FALSE(AssignTempBlocks(graph, 1515 new_root, 1516 fd, 1517 data_file_size, 1518 final_order, 1519 &inverse_final_order, 1520 cuts)); 1521 LOG(INFO) << "Making sure all temp blocks have been allocated"; 1522 1523 // Remove the scratch node, if any 1524 if (scratch_vertex != Vertex::kInvalidIndex) { 1525 final_order->erase(final_order->begin() + 1526 inverse_final_order[scratch_vertex]); 1527 (*graph)[scratch_vertex].valid = false; 1528 GenerateReverseTopoOrderMap(*final_order, &inverse_final_order); 1529 } 1530 1531 graph_utils::DumpGraph(*graph); 1532 CHECK(NoTempBlocksRemain(*graph)); 1533 LOG(INFO) << "done making sure all temp blocks are allocated"; 1534 return true; 1535} 1536 1537void DeltaDiffGenerator::CreateScratchNode(uint64_t start_block, 1538 uint64_t num_blocks, 1539 Vertex* vertex) { 1540 vertex->file_name = "<scratch>"; 1541 vertex->op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ); 1542 vertex->op.set_data_offset(0); 1543 vertex->op.set_data_length(0); 1544 Extent* extent = vertex->op.add_dst_extents(); 1545 extent->set_start_block(start_block); 1546 extent->set_num_blocks(num_blocks); 1547} 1548 1549bool DeltaDiffGenerator::GenerateDeltaUpdateFile( 1550 const string& old_root, 1551 const string& old_image, 1552 const string& new_root, 1553 const string& new_image, 1554 const string& old_kernel_part, 1555 const string& new_kernel_part, 1556 const string& output_path, 1557 const string& private_key_path, 1558 off_t chunk_size, 1559 size_t rootfs_partition_size, 1560 const ImageInfo* old_image_info, 1561 const ImageInfo* new_image_info, 1562 uint64_t* metadata_size) { 1563 TEST_AND_RETURN_FALSE(chunk_size == -1 || chunk_size % kBlockSize == 0); 1564 int old_image_block_count = 0, old_image_block_size = 0; 1565 int new_image_block_count = 0, new_image_block_size = 0; 1566 TEST_AND_RETURN_FALSE(utils::GetFilesystemSize(new_image, 1567 &new_image_block_count, 1568 &new_image_block_size)); 1569 if (!old_image.empty()) { 1570 TEST_AND_RETURN_FALSE(utils::GetFilesystemSize(old_image, 1571 &old_image_block_count, 1572 &old_image_block_size)); 1573 TEST_AND_RETURN_FALSE(old_image_block_size == new_image_block_size); 1574 LOG_IF(WARNING, old_image_block_count != new_image_block_count) 1575 << "Old and new images have different block counts."; 1576 1577 // If new_image_info is present, old_image_info must be present. 1578 TEST_AND_RETURN_FALSE(!old_image_info == !new_image_info); 1579 } else { 1580 // old_image_info must not be present for a full update. 1581 TEST_AND_RETURN_FALSE(!old_image_info); 1582 } 1583 1584 // Sanity checks for the partition size. 1585 TEST_AND_RETURN_FALSE(rootfs_partition_size % kBlockSize == 0); 1586 size_t fs_size = static_cast<size_t>(new_image_block_size) * 1587 new_image_block_count; 1588 LOG(INFO) << "Rootfs partition size: " << rootfs_partition_size; 1589 LOG(INFO) << "Actual filesystem size: " << fs_size; 1590 TEST_AND_RETURN_FALSE(rootfs_partition_size >= fs_size); 1591 1592 // Sanity check kernel partition arg 1593 TEST_AND_RETURN_FALSE(utils::FileSize(new_kernel_part) >= 0); 1594 1595 vector<Block> blocks(max(old_image_block_count, new_image_block_count)); 1596 LOG(INFO) << "Invalid block index: " << Vertex::kInvalidIndex; 1597 LOG(INFO) << "Block count: " << blocks.size(); 1598 for (vector<Block>::size_type i = 0; i < blocks.size(); i++) { 1599 CHECK(blocks[i].reader == Vertex::kInvalidIndex); 1600 CHECK(blocks[i].writer == Vertex::kInvalidIndex); 1601 } 1602 Graph graph; 1603 CheckGraph(graph); 1604 1605 const string kTempFileTemplate("CrAU_temp_data.XXXXXX"); 1606 string temp_file_path; 1607 unique_ptr<ScopedPathUnlinker> temp_file_unlinker; 1608 off_t data_file_size = 0; 1609 1610 LOG(INFO) << "Reading files..."; 1611 1612 // Create empty protobuf Manifest object 1613 DeltaArchiveManifest manifest; 1614 1615 vector<DeltaArchiveManifest_InstallOperation> kernel_ops; 1616 1617 vector<Vertex::Index> final_order; 1618 Vertex::Index scratch_vertex = Vertex::kInvalidIndex; 1619 { 1620 int fd; 1621 TEST_AND_RETURN_FALSE( 1622 utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &fd)); 1623 temp_file_unlinker.reset(new ScopedPathUnlinker(temp_file_path)); 1624 TEST_AND_RETURN_FALSE(fd >= 0); 1625 ScopedFdCloser fd_closer(&fd); 1626 if (!old_image.empty()) { 1627 // Delta update 1628 1629 TEST_AND_RETURN_FALSE(DeltaReadFiles(&graph, 1630 &blocks, 1631 old_root, 1632 new_root, 1633 chunk_size, 1634 fd, 1635 &data_file_size)); 1636 LOG(INFO) << "done reading normal files"; 1637 CheckGraph(graph); 1638 1639 LOG(INFO) << "Starting metadata processing"; 1640 TEST_AND_RETURN_FALSE(Metadata::DeltaReadMetadata(&graph, 1641 &blocks, 1642 old_image, 1643 new_image, 1644 fd, 1645 &data_file_size)); 1646 LOG(INFO) << "Done metadata processing"; 1647 CheckGraph(graph); 1648 1649 graph.resize(graph.size() + 1); 1650 TEST_AND_RETURN_FALSE(ReadUnwrittenBlocks(blocks, 1651 fd, 1652 &data_file_size, 1653 new_image, 1654 &graph.back())); 1655 1656 // Final scratch block (if there's space) 1657 if (blocks.size() < (rootfs_partition_size / kBlockSize)) { 1658 scratch_vertex = graph.size(); 1659 graph.resize(graph.size() + 1); 1660 CreateScratchNode(blocks.size(), 1661 (rootfs_partition_size / kBlockSize) - blocks.size(), 1662 &graph.back()); 1663 } 1664 1665 // Read kernel partition 1666 TEST_AND_RETURN_FALSE(DeltaCompressKernelPartition(old_kernel_part, 1667 new_kernel_part, 1668 &kernel_ops, 1669 fd, 1670 &data_file_size)); 1671 1672 LOG(INFO) << "done reading kernel"; 1673 CheckGraph(graph); 1674 1675 LOG(INFO) << "Creating edges..."; 1676 CreateEdges(&graph, blocks); 1677 LOG(INFO) << "Done creating edges"; 1678 CheckGraph(graph); 1679 1680 TEST_AND_RETURN_FALSE(ConvertGraphToDag(&graph, 1681 new_root, 1682 fd, 1683 &data_file_size, 1684 &final_order, 1685 scratch_vertex)); 1686 1687 // Set the minor version for this payload. 1688 LOG(INFO) << "Adding Delta Minor Version."; 1689 manifest.set_minor_version(DeltaPerformer::kSupportedMinorPayloadVersion); 1690 } else { 1691 // Full update 1692 off_t new_image_size = 1693 static_cast<off_t>(new_image_block_count) * new_image_block_size; 1694 TEST_AND_RETURN_FALSE(FullUpdateGenerator::Run(&graph, 1695 new_kernel_part, 1696 new_image, 1697 new_image_size, 1698 fd, 1699 &data_file_size, 1700 kFullUpdateChunkSize, 1701 kBlockSize, 1702 &kernel_ops, 1703 &final_order)); 1704 1705 // Set the minor version for this payload. 1706 LOG(INFO) << "Adding Full Minor Version."; 1707 manifest.set_minor_version(DeltaPerformer::kFullPayloadMinorVersion); 1708 } 1709 } 1710 1711 if (old_image_info) 1712 *(manifest.mutable_old_image_info()) = *old_image_info; 1713 1714 if (new_image_info) 1715 *(manifest.mutable_new_image_info()) = *new_image_info; 1716 1717 OperationNameMap op_name_map; 1718 CheckGraph(graph); 1719 InstallOperationsToManifest(graph, 1720 final_order, 1721 kernel_ops, 1722 &manifest, 1723 &op_name_map); 1724 CheckGraph(graph); 1725 manifest.set_block_size(kBlockSize); 1726 1727 // Reorder the data blobs with the newly ordered manifest 1728 string ordered_blobs_path; 1729 TEST_AND_RETURN_FALSE(utils::MakeTempFile( 1730 "CrAU_temp_data.ordered.XXXXXX", 1731 &ordered_blobs_path, 1732 nullptr)); 1733 ScopedPathUnlinker ordered_blobs_unlinker(ordered_blobs_path); 1734 TEST_AND_RETURN_FALSE(ReorderDataBlobs(&manifest, 1735 temp_file_path, 1736 ordered_blobs_path)); 1737 temp_file_unlinker.reset(); 1738 1739 // Check that install op blobs are in order. 1740 uint64_t next_blob_offset = 0; 1741 { 1742 for (int i = 0; i < (manifest.install_operations_size() + 1743 manifest.kernel_install_operations_size()); i++) { 1744 DeltaArchiveManifest_InstallOperation* op = 1745 i < manifest.install_operations_size() ? 1746 manifest.mutable_install_operations(i) : 1747 manifest.mutable_kernel_install_operations( 1748 i - manifest.install_operations_size()); 1749 if (op->has_data_offset()) { 1750 if (op->data_offset() != next_blob_offset) { 1751 LOG(FATAL) << "bad blob offset! " << op->data_offset() << " != " 1752 << next_blob_offset; 1753 } 1754 next_blob_offset += op->data_length(); 1755 } 1756 } 1757 } 1758 1759 // Signatures appear at the end of the blobs. Note the offset in the 1760 // manifest 1761 if (!private_key_path.empty()) { 1762 uint64_t signature_blob_length = 0; 1763 TEST_AND_RETURN_FALSE( 1764 PayloadSigner::SignatureBlobLength(vector<string>(1, private_key_path), 1765 &signature_blob_length)); 1766 AddSignatureOp(next_blob_offset, signature_blob_length, &manifest); 1767 } 1768 1769 TEST_AND_RETURN_FALSE(InitializePartitionInfos(old_kernel_part, 1770 new_kernel_part, 1771 old_image, 1772 new_image, 1773 &manifest)); 1774 1775 // Serialize protobuf 1776 string serialized_manifest; 1777 1778 CheckGraph(graph); 1779 TEST_AND_RETURN_FALSE(manifest.AppendToString(&serialized_manifest)); 1780 CheckGraph(graph); 1781 1782 LOG(INFO) << "Writing final delta file header..."; 1783 DirectFileWriter writer; 1784 TEST_AND_RETURN_FALSE_ERRNO(writer.Open(output_path.c_str(), 1785 O_WRONLY | O_CREAT | O_TRUNC, 1786 0644) == 0); 1787 ScopedFileWriterCloser writer_closer(&writer); 1788 1789 // Write header 1790 TEST_AND_RETURN_FALSE(writer.Write(kDeltaMagic, strlen(kDeltaMagic))); 1791 1792 // Write version number 1793 TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer, kVersionNumber)); 1794 1795 // Write protobuf length 1796 TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer, 1797 serialized_manifest.size())); 1798 1799 // Write protobuf 1800 LOG(INFO) << "Writing final delta file protobuf... " 1801 << serialized_manifest.size(); 1802 TEST_AND_RETURN_FALSE(writer.Write(serialized_manifest.data(), 1803 serialized_manifest.size())); 1804 1805 // Append the data blobs 1806 LOG(INFO) << "Writing final delta file data blobs..."; 1807 int blobs_fd = open(ordered_blobs_path.c_str(), O_RDONLY, 0); 1808 ScopedFdCloser blobs_fd_closer(&blobs_fd); 1809 TEST_AND_RETURN_FALSE(blobs_fd >= 0); 1810 for (;;) { 1811 char buf[kBlockSize]; 1812 ssize_t rc = read(blobs_fd, buf, sizeof(buf)); 1813 if (0 == rc) { 1814 // EOF 1815 break; 1816 } 1817 TEST_AND_RETURN_FALSE_ERRNO(rc > 0); 1818 TEST_AND_RETURN_FALSE(writer.Write(buf, rc)); 1819 } 1820 1821 // Write signature blob. 1822 if (!private_key_path.empty()) { 1823 LOG(INFO) << "Signing the update..."; 1824 vector<char> signature_blob; 1825 TEST_AND_RETURN_FALSE(PayloadSigner::SignPayload( 1826 output_path, 1827 vector<string>(1, private_key_path), 1828 &signature_blob)); 1829 TEST_AND_RETURN_FALSE(writer.Write(&signature_blob[0], 1830 signature_blob.size())); 1831 } 1832 1833 *metadata_size = 1834 strlen(kDeltaMagic) + 2 * sizeof(uint64_t) + serialized_manifest.size(); 1835 ReportPayloadUsage(manifest, *metadata_size, op_name_map); 1836 1837 LOG(INFO) << "All done. Successfully created delta file with " 1838 << "metadata size = " << *metadata_size; 1839 return true; 1840} 1841 1842// Runs the bsdiff tool on two files and returns the resulting delta in 1843// 'out'. Returns true on success. 1844bool DeltaDiffGenerator::BsdiffFiles(const string& old_file, 1845 const string& new_file, 1846 vector<char>* out) { 1847 const string kPatchFile = "delta.patchXXXXXX"; 1848 string patch_file_path; 1849 1850 TEST_AND_RETURN_FALSE( 1851 utils::MakeTempFile(kPatchFile, &patch_file_path, nullptr)); 1852 1853 vector<string> cmd; 1854 cmd.push_back(kBsdiffPath); 1855 cmd.push_back(old_file); 1856 cmd.push_back(new_file); 1857 cmd.push_back(patch_file_path); 1858 1859 int rc = 1; 1860 vector<char> patch_file; 1861 TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, nullptr)); 1862 TEST_AND_RETURN_FALSE(rc == 0); 1863 TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out)); 1864 unlink(patch_file_path.c_str()); 1865 return true; 1866} 1867 1868// The |blocks| vector contains a reader and writer for each block on the 1869// filesystem that's being in-place updated. We populate the reader/writer 1870// fields of |blocks| by calling this function. 1871// For each block in |operation| that is read or written, find that block 1872// in |blocks| and set the reader/writer field to the vertex passed. 1873// |graph| is not strictly necessary, but useful for printing out 1874// error messages. 1875bool DeltaDiffGenerator::AddInstallOpToBlocksVector( 1876 const DeltaArchiveManifest_InstallOperation& operation, 1877 const Graph& graph, 1878 Vertex::Index vertex, 1879 vector<Block>* blocks) { 1880 // See if this is already present. 1881 TEST_AND_RETURN_FALSE(operation.dst_extents_size() > 0); 1882 1883 enum BlockField { READER = 0, WRITER, BLOCK_FIELD_COUNT }; 1884 for (int field = READER; field < BLOCK_FIELD_COUNT; field++) { 1885 const int extents_size = 1886 (field == READER) ? operation.src_extents_size() : 1887 operation.dst_extents_size(); 1888 const char* past_participle = (field == READER) ? "read" : "written"; 1889 const google::protobuf::RepeatedPtrField<Extent>& extents = 1890 (field == READER) ? operation.src_extents() : operation.dst_extents(); 1891 Vertex::Index Block::*access_type = 1892 (field == READER) ? &Block::reader : &Block::writer; 1893 1894 for (int i = 0; i < extents_size; i++) { 1895 const Extent& extent = extents.Get(i); 1896 if (extent.start_block() == kSparseHole) { 1897 // Hole in sparse file. skip 1898 continue; 1899 } 1900 for (uint64_t block = extent.start_block(); 1901 block < (extent.start_block() + extent.num_blocks()); block++) { 1902 if ((*blocks)[block].*access_type != Vertex::kInvalidIndex) { 1903 LOG(FATAL) << "Block " << block << " is already " 1904 << past_participle << " by " 1905 << (*blocks)[block].*access_type << "(" 1906 << graph[(*blocks)[block].*access_type].file_name 1907 << ") and also " << vertex << "(" 1908 << graph[vertex].file_name << ")"; 1909 } 1910 (*blocks)[block].*access_type = vertex; 1911 } 1912 } 1913 } 1914 return true; 1915} 1916 1917void DeltaDiffGenerator::AddSignatureOp(uint64_t signature_blob_offset, 1918 uint64_t signature_blob_length, 1919 DeltaArchiveManifest* manifest) { 1920 LOG(INFO) << "Making room for signature in file"; 1921 manifest->set_signatures_offset(signature_blob_offset); 1922 LOG(INFO) << "set? " << manifest->has_signatures_offset(); 1923 // Add a dummy op at the end to appease older clients 1924 DeltaArchiveManifest_InstallOperation* dummy_op = 1925 manifest->add_kernel_install_operations(); 1926 dummy_op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE); 1927 dummy_op->set_data_offset(signature_blob_offset); 1928 manifest->set_signatures_offset(signature_blob_offset); 1929 dummy_op->set_data_length(signature_blob_length); 1930 manifest->set_signatures_size(signature_blob_length); 1931 Extent* dummy_extent = dummy_op->add_dst_extents(); 1932 // Tell the dummy op to write this data to a big sparse hole 1933 dummy_extent->set_start_block(kSparseHole); 1934 dummy_extent->set_num_blocks((signature_blob_length + kBlockSize - 1) / 1935 kBlockSize); 1936} 1937 1938const char* const kBsdiffPath = "bsdiff"; 1939 1940}; // namespace chromeos_update_engine 1941