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