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