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