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