delta_diff_generator.cc revision 35589c2b9a0e20b42661b132890128d8025c1954 
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(const PartitionConfig& part,
640                                                 PartitionInfo* info) {
641  info->set_size(part.size);
642  OmahaHashCalculator hasher;
643  TEST_AND_RETURN_FALSE(hasher.UpdateFile(part.path, part.size) ==
644                        static_cast<off_t>(part.size));
645  TEST_AND_RETURN_FALSE(hasher.Finalize());
646  const chromeos::Blob& hash = hasher.raw_hash();
647  info->set_hash(hash.data(), hash.size());
648  LOG(INFO) << part.path << ": size=" << part.size << " hash=" << hasher.hash();
649  return true;
650}
651
652bool InitializePartitionInfos(const PayloadGenerationConfig& config,
653                              DeltaArchiveManifest* manifest) {
654  if (!config.source.kernel.path.empty()) {
655    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
656        config.source.kernel,
657        manifest->mutable_old_kernel_info()));
658  }
659  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
660      config.target.kernel,
661      manifest->mutable_new_kernel_info()));
662  if (!config.source.rootfs.path.empty()) {
663    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
664        config.source.rootfs,
665        manifest->mutable_old_rootfs_info()));
666  }
667  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
668      config.target.rootfs,
669      manifest->mutable_new_rootfs_info()));
670  return true;
671}
672
673// Stores all Extents in 'extents' into 'out'.
674void DeltaDiffGenerator::StoreExtents(
675    const vector<Extent>& extents,
676    google::protobuf::RepeatedPtrField<Extent>* out) {
677  for (const Extent& extent : extents) {
678    Extent* new_extent = out->Add();
679    *new_extent = extent;
680  }
681}
682
683// Stores all extents in |extents| into |out_vector|.
684void DeltaDiffGenerator::ExtentsToVector(
685    const google::protobuf::RepeatedPtrField<Extent>& extents,
686    vector<Extent>* out_vector) {
687  out_vector->clear();
688  for (int i = 0; i < extents.size(); i++) {
689    out_vector->push_back(extents.Get(i));
690  }
691}
692
693// Returns true if |op| is a no-op operation that doesn't do any useful work
694// (e.g., a move operation that copies blocks onto themselves).
695bool DeltaDiffGenerator::IsNoopOperation(
696    const DeltaArchiveManifest_InstallOperation& op) {
697  return (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE &&
698          ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
699}
700
701void DeltaDiffGenerator::FilterNoopOperations(vector<AnnotatedOperation>* ops) {
702  ops->erase(
703      std::remove_if(
704          ops->begin(), ops->end(),
705          [](const AnnotatedOperation& aop){return IsNoopOperation(aop.op);}),
706      ops->end());
707}
708
709bool DeltaDiffGenerator::ReorderDataBlobs(
710    DeltaArchiveManifest* manifest,
711    const string& data_blobs_path,
712    const string& new_data_blobs_path) {
713  int in_fd = open(data_blobs_path.c_str(), O_RDONLY, 0);
714  TEST_AND_RETURN_FALSE_ERRNO(in_fd >= 0);
715  ScopedFdCloser in_fd_closer(&in_fd);
716
717  DirectFileWriter writer;
718  TEST_AND_RETURN_FALSE(
719      writer.Open(new_data_blobs_path.c_str(),
720                  O_WRONLY | O_TRUNC | O_CREAT,
721                  0644) == 0);
722  ScopedFileWriterCloser writer_closer(&writer);
723  uint64_t out_file_size = 0;
724
725  for (int i = 0; i < (manifest->install_operations_size() +
726                       manifest->kernel_install_operations_size()); i++) {
727    DeltaArchiveManifest_InstallOperation* op = nullptr;
728    if (i < manifest->install_operations_size()) {
729      op = manifest->mutable_install_operations(i);
730    } else {
731      op = manifest->mutable_kernel_install_operations(
732          i - manifest->install_operations_size());
733    }
734    if (!op->has_data_offset())
735      continue;
736    CHECK(op->has_data_length());
737    chromeos::Blob buf(op->data_length());
738    ssize_t rc = pread(in_fd, buf.data(), buf.size(), op->data_offset());
739    TEST_AND_RETURN_FALSE(rc == static_cast<ssize_t>(buf.size()));
740
741    // Add the hash of the data blobs for this operation
742    TEST_AND_RETURN_FALSE(AddOperationHash(op, buf));
743
744    op->set_data_offset(out_file_size);
745    TEST_AND_RETURN_FALSE(writer.Write(buf.data(), buf.size()));
746    out_file_size += buf.size();
747  }
748  return true;
749}
750
751bool DeltaDiffGenerator::AddOperationHash(
752    DeltaArchiveManifest_InstallOperation* op,
753    const chromeos::Blob& buf) {
754  OmahaHashCalculator hasher;
755  TEST_AND_RETURN_FALSE(hasher.Update(buf.data(), buf.size()));
756  TEST_AND_RETURN_FALSE(hasher.Finalize());
757  const chromeos::Blob& hash = hasher.raw_hash();
758  op->set_data_sha256_hash(hash.data(), hash.size());
759  return true;
760}
761
762bool DeltaDiffGenerator::GenerateOperations(
763    const PayloadGenerationConfig& config,
764    int data_file_fd,
765    off_t* data_file_size,
766    vector<AnnotatedOperation>* rootfs_ops,
767    vector<AnnotatedOperation>* kernel_ops) {
768  unique_ptr<Ext2Filesystem> old_fs = Ext2Filesystem::CreateFromFile(
769      config.source.rootfs.path);
770  unique_ptr<Ext2Filesystem> new_fs = Ext2Filesystem::CreateFromFile(
771      config.target.rootfs.path);
772
773  off_t chunk_blocks = config.chunk_size == -1 ? -1 : (
774      config.chunk_size / config.block_size);
775
776  rootfs_ops->clear();
777  TEST_AND_RETURN_FALSE(DeltaReadFilesystem(rootfs_ops,
778                                            config.source.rootfs.path,
779                                            config.target.rootfs.path,
780                                            old_fs.get(),
781                                            new_fs.get(),
782                                            chunk_blocks,
783                                            data_file_fd,
784                                            data_file_size,
785                                            true));  // src_ops_allowed
786  LOG(INFO) << "done reading normal files";
787
788  // Read kernel partition
789  TEST_AND_RETURN_FALSE(
790      DeltaCompressKernelPartition(config.source.kernel.path,
791                                   config.target.kernel.path,
792                                   config.source.kernel.size,
793                                   config.target.kernel.size,
794                                   config.block_size,
795                                   kernel_ops,
796                                   data_file_fd,
797                                   data_file_size,
798                                   true));  // src_ops_allowed
799  LOG(INFO) << "done reading kernel";
800
801  TEST_AND_RETURN_FALSE(FragmentOperations(rootfs_ops,
802                                           config.target.rootfs.path,
803                                           data_file_fd,
804                                           data_file_size));
805  TEST_AND_RETURN_FALSE(FragmentOperations(kernel_ops,
806                                           config.target.kernel.path,
807                                           data_file_fd,
808                                           data_file_size));
809  SortOperationsByDestination(rootfs_ops);
810  SortOperationsByDestination(kernel_ops);
811  // TODO(alliewood): Change merge operations to use config.chunk_size once
812  // specifying chunk_size on the command line works. crbug/485397.
813  TEST_AND_RETURN_FALSE(MergeOperations(rootfs_ops,
814                                        kDefaultChunkSize,
815                                        config.target.rootfs.path,
816                                        data_file_fd,
817                                        data_file_size));
818  TEST_AND_RETURN_FALSE(MergeOperations(kernel_ops,
819                                        kDefaultChunkSize,
820                                        config.target.kernel.path,
821                                        data_file_fd,
822                                        data_file_size));
823  return true;
824}
825
826bool GenerateUpdatePayloadFile(
827    const PayloadGenerationConfig& config,
828    const string& output_path,
829    const string& private_key_path,
830    uint64_t* metadata_size) {
831  if (config.is_delta) {
832    LOG_IF(WARNING, config.source.rootfs.size != config.target.rootfs.size)
833        << "Old and new images have different block counts.";
834    // TODO(deymo): Our tools only support growing the filesystem size during
835    // an update. Remove this check when that's fixed. crbug.com/192136
836    LOG_IF(FATAL, config.source.rootfs.size > config.target.rootfs.size)
837        << "Shirking the rootfs size is not supported at the moment.";
838  }
839
840  // Sanity checks for the partition size.
841  LOG(INFO) << "Rootfs partition size: " << config.rootfs_partition_size;
842  LOG(INFO) << "Actual filesystem size: " << config.target.rootfs.size;
843
844  LOG(INFO) << "Block count: "
845            << config.target.rootfs.size / config.block_size;
846
847  const string kTempFileTemplate("CrAU_temp_data.XXXXXX");
848  string temp_file_path;
849  unique_ptr<ScopedPathUnlinker> temp_file_unlinker;
850  off_t data_file_size = 0;
851
852  LOG(INFO) << "Reading files...";
853
854  // Create empty protobuf Manifest object
855  DeltaArchiveManifest manifest;
856  manifest.set_minor_version(config.minor_version);
857
858  vector<AnnotatedOperation> rootfs_ops;
859  vector<AnnotatedOperation> kernel_ops;
860
861  // Select payload generation strategy based on the config.
862  unique_ptr<OperationsGenerator> strategy;
863  if (config.is_delta) {
864    // We don't efficiently support deltas on squashfs. For now, we will
865    // produce full operations in that case.
866    if (utils::IsSquashfsFilesystem(config.target.rootfs.path)) {
867      LOG(INFO) << "Using generator FullUpdateGenerator::Run for squashfs "
868                   "deltas";
869      strategy.reset(new FullUpdateGenerator());
870    } else if (utils::IsExtFilesystem(config.target.rootfs.path)) {
871      // Delta update (with possibly a full kernel update).
872      if (config.minor_version == kInPlaceMinorPayloadVersion) {
873        LOG(INFO) << "Using generator InplaceGenerator::GenerateInplaceDelta";
874        strategy.reset(new InplaceGenerator());
875      } else if (config.minor_version == kSourceMinorPayloadVersion) {
876        LOG(INFO) << "Using generator DeltaDiffGenerator::GenerateSourceDelta";
877        strategy.reset(new DeltaDiffGenerator());
878      } else {
879        LOG(ERROR) << "Unsupported minor version given for delta payload: "
880                   << config.minor_version;
881        return false;
882      }
883    } else {
884      LOG(ERROR) << "Unsupported filesystem for delta payload in "
885                 << config.target.rootfs.path;
886      return false;
887    }
888  } else {
889    // Full update.
890    LOG(INFO) << "Using generator FullUpdateGenerator::Run";
891    strategy.reset(new FullUpdateGenerator());
892  }
893
894  {
895    int data_file_fd;
896    TEST_AND_RETURN_FALSE(
897        utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &data_file_fd));
898    temp_file_unlinker.reset(new ScopedPathUnlinker(temp_file_path));
899    TEST_AND_RETURN_FALSE(data_file_fd >= 0);
900    ScopedFdCloser data_file_fd_closer(&data_file_fd);
901
902    // Generate the operations using the strategy we selected above.
903    TEST_AND_RETURN_FALSE(strategy->GenerateOperations(config,
904                                                       data_file_fd,
905                                                       &data_file_size,
906                                                       &rootfs_ops,
907                                                       &kernel_ops));
908  }
909
910  if (!config.source.ImageInfoIsEmpty())
911    *(manifest.mutable_old_image_info()) = config.source.image_info;
912
913  if (!config.target.ImageInfoIsEmpty())
914    *(manifest.mutable_new_image_info()) = config.target.image_info;
915
916  // Filter the no-operations. OperationsGenerators should not output this kind
917  // of operations normally, but this is an extra step to fix that if
918  // happened.
919  DeltaDiffGenerator::FilterNoopOperations(&rootfs_ops);
920  DeltaDiffGenerator::FilterNoopOperations(&kernel_ops);
921
922  OperationNameMap op_name_map;
923  InstallOperationsToManifest(rootfs_ops, kernel_ops, &manifest, &op_name_map);
924  manifest.set_block_size(config.block_size);
925
926  // Reorder the data blobs with the newly ordered manifest.
927  string ordered_blobs_path;
928  TEST_AND_RETURN_FALSE(utils::MakeTempFile(
929      "CrAU_temp_data.ordered.XXXXXX",
930      &ordered_blobs_path,
931      nullptr));
932  ScopedPathUnlinker ordered_blobs_unlinker(ordered_blobs_path);
933  TEST_AND_RETURN_FALSE(
934      DeltaDiffGenerator::ReorderDataBlobs(&manifest,
935                                           temp_file_path,
936                                           ordered_blobs_path));
937  temp_file_unlinker.reset();
938
939  // Check that install op blobs are in order.
940  uint64_t next_blob_offset = 0;
941  {
942    for (int i = 0; i < (manifest.install_operations_size() +
943                         manifest.kernel_install_operations_size()); i++) {
944      DeltaArchiveManifest_InstallOperation* op =
945          i < manifest.install_operations_size() ?
946          manifest.mutable_install_operations(i) :
947          manifest.mutable_kernel_install_operations(
948              i - manifest.install_operations_size());
949      if (op->has_data_offset()) {
950        if (op->data_offset() != next_blob_offset) {
951          LOG(FATAL) << "bad blob offset! " << op->data_offset() << " != "
952                     << next_blob_offset;
953        }
954        next_blob_offset += op->data_length();
955      }
956    }
957  }
958
959  // Signatures appear at the end of the blobs. Note the offset in the
960  // manifest
961  if (!private_key_path.empty()) {
962    uint64_t signature_blob_length = 0;
963    TEST_AND_RETURN_FALSE(
964        PayloadSigner::SignatureBlobLength(vector<string>(1, private_key_path),
965                                           &signature_blob_length));
966    DeltaDiffGenerator::AddSignatureOp(
967        next_blob_offset, signature_blob_length, &manifest);
968  }
969
970  TEST_AND_RETURN_FALSE(InitializePartitionInfos(config, &manifest));
971
972  // Serialize protobuf
973  string serialized_manifest;
974
975  TEST_AND_RETURN_FALSE(manifest.AppendToString(&serialized_manifest));
976
977  LOG(INFO) << "Writing final delta file header...";
978  DirectFileWriter writer;
979  TEST_AND_RETURN_FALSE_ERRNO(writer.Open(output_path.c_str(),
980                                          O_WRONLY | O_CREAT | O_TRUNC,
981                                          0644) == 0);
982  ScopedFileWriterCloser writer_closer(&writer);
983
984  // Write header
985  TEST_AND_RETURN_FALSE(writer.Write(kDeltaMagic, strlen(kDeltaMagic)));
986
987  // Write major version number
988  TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer, kMajorVersionNumber));
989
990  // Write protobuf length
991  TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer,
992                                               serialized_manifest.size()));
993
994  // Write protobuf
995  LOG(INFO) << "Writing final delta file protobuf... "
996            << serialized_manifest.size();
997  TEST_AND_RETURN_FALSE(writer.Write(serialized_manifest.data(),
998                                     serialized_manifest.size()));
999
1000  // Append the data blobs
1001  LOG(INFO) << "Writing final delta file data blobs...";
1002  int blobs_fd = open(ordered_blobs_path.c_str(), O_RDONLY, 0);
1003  ScopedFdCloser blobs_fd_closer(&blobs_fd);
1004  TEST_AND_RETURN_FALSE(blobs_fd >= 0);
1005  for (;;) {
1006    vector<char> buf(config.block_size);
1007    ssize_t rc = read(blobs_fd, buf.data(), buf.size());
1008    if (0 == rc) {
1009      // EOF
1010      break;
1011    }
1012    TEST_AND_RETURN_FALSE_ERRNO(rc > 0);
1013    TEST_AND_RETURN_FALSE(writer.Write(buf.data(), rc));
1014  }
1015
1016  // Write signature blob.
1017  if (!private_key_path.empty()) {
1018    LOG(INFO) << "Signing the update...";
1019    chromeos::Blob signature_blob;
1020    TEST_AND_RETURN_FALSE(PayloadSigner::SignPayload(
1021        output_path,
1022        vector<string>(1, private_key_path),
1023        &signature_blob));
1024    TEST_AND_RETURN_FALSE(writer.Write(signature_blob.data(),
1025                                       signature_blob.size()));
1026  }
1027
1028  *metadata_size =
1029      strlen(kDeltaMagic) + 2 * sizeof(uint64_t) + serialized_manifest.size();
1030  ReportPayloadUsage(manifest, *metadata_size, op_name_map);
1031
1032  LOG(INFO) << "All done. Successfully created delta file with "
1033            << "metadata size = " << *metadata_size;
1034  return true;
1035}
1036
1037// Runs the bsdiff tool on two files and returns the resulting delta in
1038// 'out'. Returns true on success.
1039bool DeltaDiffGenerator::BsdiffFiles(const string& old_file,
1040                                     const string& new_file,
1041                                     chromeos::Blob* out) {
1042  const string kPatchFile = "delta.patchXXXXXX";
1043  string patch_file_path;
1044
1045  TEST_AND_RETURN_FALSE(
1046      utils::MakeTempFile(kPatchFile, &patch_file_path, nullptr));
1047
1048  vector<string> cmd;
1049  cmd.push_back(kBsdiffPath);
1050  cmd.push_back(old_file);
1051  cmd.push_back(new_file);
1052  cmd.push_back(patch_file_path);
1053
1054  int rc = 1;
1055  chromeos::Blob patch_file;
1056  TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, nullptr));
1057  TEST_AND_RETURN_FALSE(rc == 0);
1058  TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
1059  unlink(patch_file_path.c_str());
1060  return true;
1061}
1062
1063void DeltaDiffGenerator::AddSignatureOp(uint64_t signature_blob_offset,
1064                                        uint64_t signature_blob_length,
1065                                        DeltaArchiveManifest* manifest) {
1066  LOG(INFO) << "Making room for signature in file";
1067  manifest->set_signatures_offset(signature_blob_offset);
1068  LOG(INFO) << "set? " << manifest->has_signatures_offset();
1069  // Add a dummy op at the end to appease older clients
1070  DeltaArchiveManifest_InstallOperation* dummy_op =
1071      manifest->add_kernel_install_operations();
1072  dummy_op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
1073  dummy_op->set_data_offset(signature_blob_offset);
1074  manifest->set_signatures_offset(signature_blob_offset);
1075  dummy_op->set_data_length(signature_blob_length);
1076  manifest->set_signatures_size(signature_blob_length);
1077  Extent* dummy_extent = dummy_op->add_dst_extents();
1078  // Tell the dummy op to write this data to a big sparse hole
1079  dummy_extent->set_start_block(kSparseHole);
1080  dummy_extent->set_num_blocks((signature_blob_length + kBlockSize - 1) /
1081                               kBlockSize);
1082}
1083
1084bool DeltaDiffGenerator::FragmentOperations(
1085    vector<AnnotatedOperation>* aops,
1086    const string& target_part_path,
1087    int data_fd,
1088    off_t* data_file_size) {
1089  vector<AnnotatedOperation> fragmented_aops;
1090  for (const AnnotatedOperation& aop : *aops) {
1091    if (aop.op.type() ==
1092        DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) {
1093      TEST_AND_RETURN_FALSE(SplitSourceCopy(aop, &fragmented_aops));
1094    } else if ((aop.op.type() ==
1095                DeltaArchiveManifest_InstallOperation_Type_REPLACE) ||
1096               (aop.op.type() ==
1097                DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) {
1098      TEST_AND_RETURN_FALSE(SplitReplaceOrReplaceBz(aop, &fragmented_aops,
1099                                                    target_part_path, data_fd,
1100                                                    data_file_size));
1101    } else {
1102      fragmented_aops.push_back(aop);
1103    }
1104  }
1105  *aops = fragmented_aops;
1106  return true;
1107}
1108
1109void DeltaDiffGenerator::SortOperationsByDestination(
1110    vector<AnnotatedOperation>* aops) {
1111  sort(aops->begin(), aops->end(), CompareAopsByDestination);
1112}
1113
1114bool DeltaDiffGenerator::SplitSourceCopy(
1115    const AnnotatedOperation& original_aop,
1116    vector<AnnotatedOperation>* result_aops) {
1117  DeltaArchiveManifest_InstallOperation original_op = original_aop.op;
1118  TEST_AND_RETURN_FALSE(original_op.type() ==
1119                        DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
1120  // Keeps track of the index of curr_src_ext.
1121  int curr_src_ext_index = 0;
1122  Extent curr_src_ext = original_op.src_extents(curr_src_ext_index);
1123  for (int i = 0; i < original_op.dst_extents_size(); i++) {
1124    Extent dst_ext = original_op.dst_extents(i);
1125    // The new operation which will have only one dst extent.
1126    DeltaArchiveManifest_InstallOperation new_op;
1127    uint64_t blocks_left = dst_ext.num_blocks();
1128    while (blocks_left > 0) {
1129      if (curr_src_ext.num_blocks() <= blocks_left) {
1130        // If the curr_src_ext is smaller than dst_ext, add it.
1131        blocks_left -= curr_src_ext.num_blocks();
1132        *(new_op.add_src_extents()) = curr_src_ext;
1133        if (curr_src_ext_index + 1 < original_op.src_extents().size()) {
1134          curr_src_ext = original_op.src_extents(++curr_src_ext_index);
1135        } else {
1136          break;
1137        }
1138      } else {
1139        // Split src_exts that are bigger than the dst_ext we're dealing with.
1140        Extent first_ext;
1141        first_ext.set_num_blocks(blocks_left);
1142        first_ext.set_start_block(curr_src_ext.start_block());
1143        *(new_op.add_src_extents()) = first_ext;
1144        // Keep the second half of the split op.
1145        curr_src_ext.set_num_blocks(curr_src_ext.num_blocks() - blocks_left);
1146        curr_src_ext.set_start_block(curr_src_ext.start_block() + blocks_left);
1147        blocks_left -= first_ext.num_blocks();
1148      }
1149    }
1150    // Fix up our new operation and add it to the results.
1151    new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
1152    *(new_op.add_dst_extents()) = dst_ext;
1153    new_op.set_src_length(dst_ext.num_blocks() * kBlockSize);
1154    new_op.set_dst_length(dst_ext.num_blocks() * kBlockSize);
1155
1156    AnnotatedOperation new_aop;
1157    new_aop.op = new_op;
1158    new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i);
1159    result_aops->push_back(new_aop);
1160  }
1161  if (curr_src_ext_index != original_op.src_extents().size() - 1) {
1162    LOG(FATAL) << "Incorrectly split SOURCE_COPY operation. Did not use all "
1163               << "source extents.";
1164  }
1165  return true;
1166}
1167
1168bool DeltaDiffGenerator::SplitReplaceOrReplaceBz(
1169    const AnnotatedOperation& original_aop,
1170    vector<AnnotatedOperation>* result_aops,
1171    const string& target_part_path,
1172    int data_fd,
1173    off_t* data_file_size) {
1174  DeltaArchiveManifest_InstallOperation original_op = original_aop.op;
1175  const bool is_replace =
1176      original_op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE;
1177  TEST_AND_RETURN_FALSE(
1178      is_replace ||
1179      (original_op.type() ==
1180       DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ));
1181
1182  uint32_t data_offset = original_op.data_offset();
1183  for (int i = 0; i < original_op.dst_extents_size(); i++) {
1184    Extent dst_ext = original_op.dst_extents(i);
1185    // Make a new operation with only one dst extent.
1186    DeltaArchiveManifest_InstallOperation new_op;
1187    *(new_op.add_dst_extents()) = dst_ext;
1188    uint32_t data_size = dst_ext.num_blocks() * kBlockSize;
1189    new_op.set_dst_length(data_size);
1190    // If this is a REPLACE, attempt to reuse portions of the existing blob.
1191    if (is_replace) {
1192      new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
1193      new_op.set_data_length(data_size);
1194      new_op.set_data_offset(data_offset);
1195      data_offset += data_size;
1196    }
1197
1198    AnnotatedOperation new_aop;
1199    new_aop.op = new_op;
1200    new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i);
1201    TEST_AND_RETURN_FALSE(AddDataAndSetType(&new_aop, target_part_path, data_fd,
1202                                            data_file_size));
1203
1204    result_aops->push_back(new_aop);
1205  }
1206  return true;
1207}
1208
1209bool DeltaDiffGenerator::MergeOperations(vector<AnnotatedOperation>* aops,
1210                                         off_t chunk_size,
1211                                         const string& target_part_path,
1212                                         int data_fd,
1213                                         off_t* data_file_size) {
1214  vector<AnnotatedOperation> new_aops;
1215  for (const AnnotatedOperation& curr_aop : *aops) {
1216    if (new_aops.empty()) {
1217      new_aops.push_back(curr_aop);
1218      continue;
1219    }
1220    AnnotatedOperation& last_aop = new_aops.back();
1221
1222    if (last_aop.op.dst_extents_size() <= 0 ||
1223        curr_aop.op.dst_extents_size() <= 0) {
1224      new_aops.push_back(curr_aop);
1225      continue;
1226    }
1227    uint32_t last_dst_idx = last_aop.op.dst_extents_size() - 1;
1228    uint32_t last_end_block =
1229        last_aop.op.dst_extents(last_dst_idx).start_block() +
1230        last_aop.op.dst_extents(last_dst_idx).num_blocks();
1231    uint32_t curr_start_block = curr_aop.op.dst_extents(0).start_block();
1232    uint32_t combined_block_count =
1233        last_aop.op.dst_extents(last_dst_idx).num_blocks() +
1234        curr_aop.op.dst_extents(0).num_blocks();
1235    bool good_op_type =
1236        curr_aop.op.type() ==
1237            DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY ||
1238        curr_aop.op.type() ==
1239            DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
1240        curr_aop.op.type() ==
1241            DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ;
1242    if (good_op_type &&
1243        last_aop.op.type() == curr_aop.op.type() &&
1244        last_end_block == curr_start_block &&
1245        static_cast<off_t>(combined_block_count * kBlockSize) <= chunk_size) {
1246      // If the operations have the same type (which is a type that we can
1247      // merge), are contiguous, are fragmented to have one destination extent,
1248      // and their combined block count would be less than chunk size, merge
1249      // them.
1250      last_aop.name = base::StringPrintf("%s,%s",
1251                                         last_aop.name.c_str(),
1252                                         curr_aop.name.c_str());
1253
1254      ExtendExtents(last_aop.op.mutable_src_extents(),
1255                    curr_aop.op.src_extents());
1256      if (curr_aop.op.src_length() > 0)
1257        last_aop.op.set_src_length(last_aop.op.src_length() +
1258                                   curr_aop.op.src_length());
1259      ExtendExtents(last_aop.op.mutable_dst_extents(),
1260                    curr_aop.op.dst_extents());
1261      if (curr_aop.op.dst_length() > 0)
1262        last_aop.op.set_dst_length(last_aop.op.dst_length() +
1263                                   curr_aop.op.dst_length());
1264      // Set the data length to zero so we know to add the blob later.
1265      if (curr_aop.op.type() ==
1266          DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
1267          curr_aop.op.type() ==
1268          DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
1269        last_aop.op.set_data_length(0);
1270      }
1271    } else {
1272      // Otherwise just include the extent as is.
1273      new_aops.push_back(curr_aop);
1274    }
1275  }
1276
1277  // Set the blobs for REPLACE/REPLACE_BZ operations that have been merged.
1278  for (AnnotatedOperation& curr_aop : new_aops) {
1279    if (curr_aop.op.data_length() == 0 &&
1280        (curr_aop.op.type() ==
1281            DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
1282         curr_aop.op.type() ==
1283            DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) {
1284      TEST_AND_RETURN_FALSE(AddDataAndSetType(&curr_aop, target_part_path,
1285                                              data_fd, data_file_size));
1286    }
1287  }
1288
1289  *aops = new_aops;
1290  return true;
1291}
1292
1293void DeltaDiffGenerator::ExtendExtents(
1294    google::protobuf::RepeatedPtrField<Extent>* extents,
1295    const google::protobuf::RepeatedPtrField<Extent>& extents_to_add) {
1296  vector<Extent> extents_vector;
1297  vector<Extent> extents_to_add_vector;
1298  ExtentsToVector(*extents, &extents_vector);
1299  ExtentsToVector(extents_to_add, &extents_to_add_vector);
1300  extents_vector.insert(extents_vector.end(),
1301                        extents_to_add_vector.begin(),
1302                        extents_to_add_vector.end());
1303  NormalizeExtents(&extents_vector);
1304  extents->Clear();
1305  StoreExtents(extents_vector, extents);
1306}
1307
1308bool DeltaDiffGenerator::AddDataAndSetType(AnnotatedOperation* aop,
1309                                           const string& target_part_path,
1310                                           int data_fd,
1311                                           off_t* data_file_size) {
1312  TEST_AND_RETURN_FALSE(
1313      aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
1314      aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
1315
1316  chromeos::Blob data(aop->op.dst_length());
1317  vector<Extent> dst_extents;
1318  ExtentsToVector(aop->op.dst_extents(), &dst_extents);
1319  TEST_AND_RETURN_FALSE(utils::ReadExtents(target_part_path,
1320                                           dst_extents,
1321                                           &data,
1322                                           data.size(),
1323                                           kBlockSize));
1324
1325  chromeos::Blob data_bz;
1326  TEST_AND_RETURN_FALSE(BzipCompress(data, &data_bz));
1327  CHECK(!data_bz.empty());
1328
1329  chromeos::Blob* data_p = nullptr;
1330  DeltaArchiveManifest_InstallOperation_Type new_op_type;
1331  if (data_bz.size() < data.size()) {
1332    new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ;
1333    data_p = &data_bz;
1334  } else {
1335    new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE;
1336    data_p = &data;
1337  }
1338
1339  // If the operation already points to a data blob, check whether it's
1340  // identical to the new one, in which case don't add it.
1341  if (aop->op.type() == new_op_type &&
1342      aop->op.data_length() == data_p->size()) {
1343    chromeos::Blob current_data(data_p->size());
1344    ssize_t bytes_read;
1345    TEST_AND_RETURN_FALSE(utils::PReadAll(data_fd,
1346                                          current_data.data(),
1347                                          aop->op.data_length(),
1348                                          aop->op.data_offset(),
1349                                          &bytes_read));
1350    TEST_AND_RETURN_FALSE(bytes_read ==
1351                          static_cast<ssize_t>(aop->op.data_length()));
1352    if (current_data == *data_p)
1353      data_p = nullptr;
1354  }
1355
1356  if (data_p) {
1357    aop->op.set_type(new_op_type);
1358    aop->SetOperationBlob(data_p, data_fd, data_file_size);
1359  }
1360
1361  return true;
1362}
1363
1364};  // namespace chromeos_update_engine
1365