delta_diff_utils.cc revision 8cc502dacbccdab96824d42287f230ce04004784 
1// Copyright 2015 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_utils.h"
6
7#include <algorithm>
8#include <map>
9
10#include <base/files/file_util.h>
11#include <base/format_macros.h>
12#include <base/strings/stringprintf.h>
13
14#include "update_engine/bzip.h"
15#include "update_engine/omaha_hash_calculator.h"
16#include "update_engine/payload_generator/block_mapping.h"
17#include "update_engine/payload_generator/delta_diff_generator.h"
18#include "update_engine/payload_generator/extent_ranges.h"
19#include "update_engine/payload_generator/extent_utils.h"
20#include "update_engine/subprocess.h"
21#include "update_engine/utils.h"
22
23using std::map;
24using std::string;
25using std::vector;
26
27namespace chromeos_update_engine {
28namespace {
29
30const char* const kBsdiffPath = "bsdiff";
31
32// The maximum destination size allowed for bsdiff. In general, bsdiff should
33// work for arbitrary big files, but the payload generation and payload
34// application requires a significant amount of RAM. We put a hard-limit of
35// 200 MiB that should not affect any released board, but will limit the
36// Chrome binary in ASan builders.
37const uint64_t kMaxBsdiffDestinationSize = 200 * 1024 * 1024;  // bytes
38
39// Process a range of blocks from |range_start| to |range_end| in the extent at
40// position |*idx_p| of |extents|. If |do_remove| is true, this range will be
41// removed, which may cause the extent to be trimmed, split or removed entirely.
42// The value of |*idx_p| is updated to point to the next extent to be processed.
43// Returns true iff the next extent to process is a new or updated one.
44bool ProcessExtentBlockRange(vector<Extent>* extents, size_t* idx_p,
45                             const bool do_remove, uint64_t range_start,
46                             uint64_t range_end) {
47  size_t idx = *idx_p;
48  uint64_t start_block = (*extents)[idx].start_block();
49  uint64_t num_blocks = (*extents)[idx].num_blocks();
50  uint64_t range_size = range_end - range_start;
51
52  if (do_remove) {
53    if (range_size == num_blocks) {
54      // Remove the entire extent.
55      extents->erase(extents->begin() + idx);
56    } else if (range_end == num_blocks) {
57      // Trim the end of the extent.
58      (*extents)[idx].set_num_blocks(num_blocks - range_size);
59      idx++;
60    } else if (range_start == 0) {
61      // Trim the head of the extent.
62      (*extents)[idx].set_start_block(start_block + range_size);
63      (*extents)[idx].set_num_blocks(num_blocks - range_size);
64    } else {
65      // Trim the middle, splitting the remainder into two parts.
66      (*extents)[idx].set_num_blocks(range_start);
67      Extent e;
68      e.set_start_block(start_block + range_end);
69      e.set_num_blocks(num_blocks - range_end);
70      idx++;
71      extents->insert(extents->begin() + idx, e);
72    }
73  } else if (range_end == num_blocks) {
74    // Done with this extent.
75    idx++;
76  } else {
77    return false;
78  }
79
80  *idx_p = idx;
81  return true;
82}
83
84// Remove identical corresponding block ranges in |src_extents| and
85// |dst_extents|. Used for preventing moving of blocks onto themselves during
86// MOVE operations. The value of |total_bytes| indicates the actual length of
87// content; this may be slightly less than the total size of blocks, in which
88// case the last block is only partly occupied with data. Returns the total
89// number of bytes removed.
90size_t RemoveIdenticalBlockRanges(vector<Extent>* src_extents,
91                                  vector<Extent>* dst_extents,
92                                  const size_t total_bytes) {
93  size_t src_idx = 0;
94  size_t dst_idx = 0;
95  uint64_t src_offset = 0, dst_offset = 0;
96  bool new_src = true, new_dst = true;
97  size_t removed_bytes = 0, nonfull_block_bytes;
98  bool do_remove = false;
99  while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) {
100    if (new_src) {
101      src_offset = 0;
102      new_src = false;
103    }
104    if (new_dst) {
105      dst_offset = 0;
106      new_dst = false;
107    }
108
109    do_remove = ((*src_extents)[src_idx].start_block() + src_offset ==
110                 (*dst_extents)[dst_idx].start_block() + dst_offset);
111
112    uint64_t src_num_blocks = (*src_extents)[src_idx].num_blocks();
113    uint64_t dst_num_blocks = (*dst_extents)[dst_idx].num_blocks();
114    uint64_t min_num_blocks = std::min(src_num_blocks - src_offset,
115                                       dst_num_blocks - dst_offset);
116    uint64_t prev_src_offset = src_offset;
117    uint64_t prev_dst_offset = dst_offset;
118    src_offset += min_num_blocks;
119    dst_offset += min_num_blocks;
120
121    new_src = ProcessExtentBlockRange(src_extents, &src_idx, do_remove,
122                                      prev_src_offset, src_offset);
123    new_dst = ProcessExtentBlockRange(dst_extents, &dst_idx, do_remove,
124                                      prev_dst_offset, dst_offset);
125    if (do_remove)
126      removed_bytes += min_num_blocks * kBlockSize;
127  }
128
129  // If we removed the last block and this block is only partly used by file
130  // content, deduct the unused portion from the total removed byte count.
131  if (do_remove && (nonfull_block_bytes = total_bytes % kBlockSize))
132    removed_bytes -= kBlockSize - nonfull_block_bytes;
133
134  return removed_bytes;
135}
136
137}  // namespace
138
139namespace diff_utils {
140
141bool DeltaReadPartition(
142    vector<AnnotatedOperation>* aops,
143    const PartitionConfig& old_part,
144    const PartitionConfig& new_part,
145    ssize_t hard_chunk_blocks,
146    size_t soft_chunk_blocks,
147    BlobFileWriter* blob_file,
148    bool src_ops_allowed) {
149  ExtentRanges old_visited_blocks;
150  ExtentRanges new_visited_blocks;
151
152  TEST_AND_RETURN_FALSE(DeltaMovedAndZeroBlocks(
153      aops,
154      old_part.path,
155      new_part.path,
156      old_part.fs_interface ? old_part.fs_interface->GetBlockCount() : 0,
157      new_part.fs_interface->GetBlockCount(),
158      soft_chunk_blocks,
159      src_ops_allowed,
160      blob_file,
161      &old_visited_blocks,
162      &new_visited_blocks));
163
164  map<string, vector<Extent>> old_files_map;
165  if (old_part.fs_interface) {
166    vector<FilesystemInterface::File> old_files;
167    old_part.fs_interface->GetFiles(&old_files);
168    for (const FilesystemInterface::File& file : old_files)
169      old_files_map[file.name] = file.extents;
170  }
171
172  TEST_AND_RETURN_FALSE(new_part.fs_interface);
173  vector<FilesystemInterface::File> new_files;
174  new_part.fs_interface->GetFiles(&new_files);
175
176  // The processing is very straightforward here, we generate operations for
177  // every file (and pseudo-file such as the metadata) in the new filesystem
178  // based on the file with the same name in the old filesystem, if any.
179  // Files with overlapping data blocks (like hardlinks or filesystems with tail
180  // packing or compression where the blocks store more than one file) are only
181  // generated once in the new image, but are also used only once from the old
182  // image due to some simplifications (see below).
183  for (const FilesystemInterface::File& new_file : new_files) {
184    // Ignore the files in the new filesystem without blocks. Symlinks with
185    // data blocks (for example, symlinks bigger than 60 bytes in ext2) are
186    // handled as normal files. We also ignore blocks that were already
187    // processed by a previous file.
188    vector<Extent> new_file_extents = FilterExtentRanges(
189        new_file.extents, new_visited_blocks);
190    new_visited_blocks.AddExtents(new_file_extents);
191
192    if (new_file_extents.empty())
193      continue;
194
195    LOG(INFO) << "Encoding file " << new_file.name << " ("
196              << BlocksInExtents(new_file_extents) << " blocks)";
197
198    // We can't visit each dst image inode more than once, as that would
199    // duplicate work. Here, we avoid visiting each source image inode
200    // more than once. Technically, we could have multiple operations
201    // that read the same blocks from the source image for diffing, but
202    // we choose not to avoid complexity. Eventually we will move away
203    // from using a graph/cycle detection/etc to generate diffs, and at that
204    // time, it will be easy (non-complex) to have many operations read
205    // from the same source blocks. At that time, this code can die. -adlr
206    vector<Extent> old_file_extents = FilterExtentRanges(
207        old_files_map[new_file.name], old_visited_blocks);
208    old_visited_blocks.AddExtents(old_file_extents);
209
210    TEST_AND_RETURN_FALSE(DeltaReadFile(
211        aops,
212        old_part.path,
213        new_part.path,
214        old_file_extents,
215        new_file_extents,
216        new_file.name,  // operation name
217        hard_chunk_blocks,
218        blob_file,
219        src_ops_allowed));
220  }
221  // Process all the blocks not included in any file. We provided all the unused
222  // blocks in the old partition as available data.
223  vector<Extent> new_unvisited = {
224      ExtentForRange(0, new_part.size / kBlockSize)};
225  new_unvisited = FilterExtentRanges(new_unvisited, new_visited_blocks);
226  if (new_unvisited.empty())
227    return true;
228
229  vector<Extent> old_unvisited;
230  if (old_part.fs_interface) {
231    old_unvisited.push_back(ExtentForRange(0, old_part.size / kBlockSize));
232    old_unvisited = FilterExtentRanges(old_unvisited, old_visited_blocks);
233  }
234
235  LOG(INFO) << "Scanning " << BlocksInExtents(new_unvisited)
236            << " unwritten blocks using chunk size of "
237            << soft_chunk_blocks << " blocks.";
238  // We use the soft_chunk_blocks limit for the <non-file-data> as we don't
239  // really know the structure of this data and we should not expect it to have
240  // redundancy between partitions.
241  TEST_AND_RETURN_FALSE(DeltaReadFile(
242      aops,
243      old_part.path,
244      new_part.path,
245      old_unvisited,
246      new_unvisited,
247      "<non-file-data>",  // operation name
248      soft_chunk_blocks,
249      blob_file,
250      src_ops_allowed));
251
252  return true;
253}
254
255bool DeltaMovedAndZeroBlocks(
256    vector<AnnotatedOperation>* aops,
257    const string& old_part,
258    const string& new_part,
259    size_t old_num_blocks,
260    size_t new_num_blocks,
261    ssize_t chunk_blocks,
262    bool src_ops_allowed,
263    BlobFileWriter* blob_file,
264    ExtentRanges* old_visited_blocks,
265    ExtentRanges* new_visited_blocks) {
266  vector<BlockMapping::BlockId> old_block_ids;
267  vector<BlockMapping::BlockId> new_block_ids;
268  TEST_AND_RETURN_FALSE(MapPartitionBlocks(old_part,
269                                           new_part,
270                                           old_num_blocks * kBlockSize,
271                                           new_num_blocks * kBlockSize,
272                                           kBlockSize,
273                                           &old_block_ids,
274                                           &new_block_ids));
275
276  // For minor-version=1, we map all the blocks that didn't move, regardless of
277  // the contents since they are already copied and no operation is required.
278  if (!src_ops_allowed) {
279    uint64_t num_blocks = std::min(old_num_blocks, new_num_blocks);
280    for (uint64_t block = 0; block < num_blocks; block++) {
281      if (old_block_ids[block] == new_block_ids[block] &&
282          !old_visited_blocks->ContainsBlock(block) &&
283          !new_visited_blocks->ContainsBlock(block)) {
284        old_visited_blocks->AddBlock(block);
285        new_visited_blocks->AddBlock(block);
286      }
287    }
288  }
289
290  // A mapping from the block_id to the list of block numbers with that block id
291  // in the old partition. This is used to lookup where in the old partition
292  // is a block from the new partition.
293  map<BlockMapping::BlockId, vector<uint64_t>> old_blocks_map;
294
295  for (uint64_t block = old_num_blocks; block-- > 0; ) {
296    if (old_block_ids[block] != 0 && !old_visited_blocks->ContainsBlock(block))
297      old_blocks_map[old_block_ids[block]].push_back(block);
298  }
299
300  // The collection of blocks in the new partition with just zeros. This is a
301  // common case for free-space that's also problematic for bsdiff, so we want
302  // to optimize it using REPLACE_BZ operations. The blob for a REPLACE_BZ of
303  // just zeros is so small that it doesn't make sense to spend the I/O reading
304  // zeros from the old partition.
305  vector<Extent> new_zeros;
306
307  vector<Extent> old_identical_blocks;
308  vector<Extent> new_identical_blocks;
309
310  for (uint64_t block = 0; block < new_num_blocks; block++) {
311    // Only produce operations for blocks that were not yet visited.
312    if (new_visited_blocks->ContainsBlock(block))
313      continue;
314    if (new_block_ids[block] == 0) {
315      AppendBlockToExtents(&new_zeros, block);
316      continue;
317    }
318
319    auto old_blocks_map_it = old_blocks_map.find(new_block_ids[block]);
320    // Check if the block exists in the old partition at all.
321    if (old_blocks_map_it == old_blocks_map.end() ||
322        old_blocks_map_it->second.empty())
323      continue;
324
325    AppendBlockToExtents(&old_identical_blocks,
326                         old_blocks_map_it->second.back());
327    AppendBlockToExtents(&new_identical_blocks, block);
328    // We can't reuse source blocks in minor version 1 because the cycle
329    // breaking algorithm doesn't support that.
330    if (!src_ops_allowed)
331      old_blocks_map_it->second.pop_back();
332  }
333
334  // Produce operations for the zero blocks split per output extent.
335  size_t num_ops = aops->size();
336  new_visited_blocks->AddExtents(new_zeros);
337  for (Extent extent : new_zeros) {
338    TEST_AND_RETURN_FALSE(DeltaReadFile(
339        aops,
340        "",
341        new_part,
342        vector<Extent>(),  // old_extents
343        vector<Extent>{extent},  // new_extents
344        "<zeros>",
345        chunk_blocks,
346        blob_file,
347        src_ops_allowed));
348  }
349  LOG(INFO) << "Produced " << (aops->size() - num_ops) << " operations for "
350            << BlocksInExtents(new_zeros) << " zeroed blocks";
351
352  // Produce MOVE/SOURCE_COPY operations for the moved blocks.
353  num_ops = aops->size();
354  if (chunk_blocks == -1)
355    chunk_blocks = new_num_blocks;
356  uint64_t used_blocks = 0;
357  old_visited_blocks->AddExtents(old_identical_blocks);
358  new_visited_blocks->AddExtents(new_identical_blocks);
359  for (Extent extent : new_identical_blocks) {
360    // We split the operation at the extent boundary or when bigger than
361    // chunk_blocks.
362    for (uint64_t op_block_offset = 0; op_block_offset < extent.num_blocks();
363         op_block_offset += chunk_blocks) {
364      aops->emplace_back();
365      AnnotatedOperation* aop = &aops->back();
366      aop->name = "<identical-blocks>";
367      aop->op.set_type(src_ops_allowed ?
368                       DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY :
369                       DeltaArchiveManifest_InstallOperation_Type_MOVE);
370
371      uint64_t chunk_num_blocks =
372        std::min(extent.num_blocks() - op_block_offset,
373                 static_cast<uint64_t>(chunk_blocks));
374
375      // The current operation represents the move/copy operation for the
376      // sublist starting at |used_blocks| of length |chunk_num_blocks| where
377      // the src and dst are from |old_identical_blocks| and
378      // |new_identical_blocks| respectively.
379      StoreExtents(
380          ExtentsSublist(old_identical_blocks, used_blocks, chunk_num_blocks),
381          aop->op.mutable_src_extents());
382
383      Extent* op_dst_extent = aop->op.add_dst_extents();
384      op_dst_extent->set_start_block(extent.start_block() + op_block_offset);
385      op_dst_extent->set_num_blocks(chunk_num_blocks);
386      CHECK(
387          vector<Extent>{*op_dst_extent} ==  // NOLINT(whitespace/braces)
388          ExtentsSublist(new_identical_blocks, used_blocks, chunk_num_blocks));
389
390      used_blocks += chunk_num_blocks;
391    }
392  }
393  LOG(INFO) << "Produced " << (aops->size() - num_ops) << " operations for "
394            << used_blocks << " identical blocks moved";
395
396  return true;
397}
398
399bool DeltaReadFile(
400    vector<AnnotatedOperation>* aops,
401    const string& old_part,
402    const string& new_part,
403    const vector<Extent>& old_extents,
404    const vector<Extent>& new_extents,
405    const string& name,
406    ssize_t chunk_blocks,
407    BlobFileWriter* blob_file,
408    bool src_ops_allowed) {
409  chromeos::Blob data;
410  DeltaArchiveManifest_InstallOperation operation;
411
412  uint64_t total_blocks = BlocksInExtents(new_extents);
413  if (chunk_blocks == -1)
414    chunk_blocks = total_blocks;
415
416  // If bsdiff breaks again, blacklist the problem file by using:
417  //   bsdiff_allowed = (name != "/foo/bar")
418  //
419  // TODO(dgarrett): chromium-os:15274 connect this test to the command line.
420  bool bsdiff_allowed = true;
421  if (static_cast<uint64_t>(chunk_blocks) * kBlockSize >
422      kMaxBsdiffDestinationSize) {
423    bsdiff_allowed = false;
424  }
425
426  if (!bsdiff_allowed) {
427    LOG(INFO) << "bsdiff blacklisting: " << name;
428  }
429
430  for (uint64_t block_offset = 0; block_offset < total_blocks;
431      block_offset += chunk_blocks) {
432    // Split the old/new file in the same chunks. Note that this could drop
433    // some information from the old file used for the new chunk. If the old
434    // file is smaller (or even empty when there's no old file) the chunk will
435    // also be empty.
436    vector<Extent> old_extents_chunk = ExtentsSublist(
437        old_extents, block_offset, chunk_blocks);
438    vector<Extent> new_extents_chunk = ExtentsSublist(
439        new_extents, block_offset, chunk_blocks);
440    NormalizeExtents(&old_extents_chunk);
441    NormalizeExtents(&new_extents_chunk);
442
443    TEST_AND_RETURN_FALSE(ReadExtentsToDiff(old_part,
444                                            new_part,
445                                            old_extents_chunk,
446                                            new_extents_chunk,
447                                            bsdiff_allowed,
448                                            &data,
449                                            &operation,
450                                            src_ops_allowed));
451
452    // Check if the operation writes nothing.
453    if (operation.dst_extents_size() == 0) {
454      if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
455        LOG(INFO) << "Empty MOVE operation ("
456                  << name << "), skipping";
457        continue;
458      } else {
459        LOG(ERROR) << "Empty non-MOVE operation";
460        return false;
461      }
462    }
463
464    // Now, insert into the list of operations.
465    AnnotatedOperation aop;
466    aop.name = name;
467    if (static_cast<uint64_t>(chunk_blocks) < total_blocks) {
468      aop.name = base::StringPrintf("%s:%" PRIu64,
469                                    name.c_str(), block_offset / chunk_blocks);
470    }
471    aop.op = operation;
472
473    // Write the data
474    if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE &&
475        operation.type() !=
476            DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) {
477      TEST_AND_RETURN_FALSE(aop.SetOperationBlob(&data, blob_file));
478    } else {
479      TEST_AND_RETURN_FALSE(blob_file->StoreBlob(data) != -1);
480    }
481    aops->emplace_back(aop);
482  }
483  return true;
484}
485
486bool ReadExtentsToDiff(const string& old_part,
487                       const string& new_part,
488                       const vector<Extent>& old_extents,
489                       const vector<Extent>& new_extents,
490                       bool bsdiff_allowed,
491                       chromeos::Blob* out_data,
492                       DeltaArchiveManifest_InstallOperation* out_op,
493                       bool src_ops_allowed) {
494  DeltaArchiveManifest_InstallOperation operation;
495  // Data blob that will be written to delta file.
496  const chromeos::Blob* data_blob = nullptr;
497
498  // We read blocks from old_extents and write blocks to new_extents.
499  uint64_t blocks_to_read = BlocksInExtents(old_extents);
500  uint64_t blocks_to_write = BlocksInExtents(new_extents);
501
502  // Make copies of the extents so we can modify them.
503  vector<Extent> src_extents = old_extents;
504  vector<Extent> dst_extents = new_extents;
505
506  // Read in bytes from new data.
507  chromeos::Blob new_data;
508  TEST_AND_RETURN_FALSE(utils::ReadExtents(new_part,
509                                           new_extents,
510                                           &new_data,
511                                           kBlockSize * blocks_to_write,
512                                           kBlockSize));
513  TEST_AND_RETURN_FALSE(!new_data.empty());
514
515
516  // Using a REPLACE is always an option.
517  operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
518  data_blob = &new_data;
519
520  // Try compressing it with bzip2.
521  chromeos::Blob new_data_bz;
522  TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
523  CHECK(!new_data_bz.empty());
524  if (new_data_bz.size() < data_blob->size()) {
525    // A REPLACE_BZ is better.
526    operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
527    data_blob = &new_data_bz;
528  }
529
530  chromeos::Blob old_data;
531  chromeos::Blob empty_blob;
532  chromeos::Blob bsdiff_delta;
533  if (blocks_to_read > 0) {
534    // Read old data.
535    TEST_AND_RETURN_FALSE(
536        utils::ReadExtents(old_part, src_extents, &old_data,
537                           kBlockSize * blocks_to_read, kBlockSize));
538    if (old_data == new_data) {
539      // No change in data.
540      if (src_ops_allowed) {
541        operation.set_type(
542            DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
543      } else {
544        operation.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
545      }
546      data_blob = &empty_blob;
547    } else if (bsdiff_allowed) {
548      // If the source file is considered bsdiff safe (no bsdiff bugs
549      // triggered), see if BSDIFF encoding is smaller.
550      base::FilePath old_chunk;
551      TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&old_chunk));
552      ScopedPathUnlinker old_unlinker(old_chunk.value());
553      TEST_AND_RETURN_FALSE(
554          utils::WriteFile(old_chunk.value().c_str(),
555                           old_data.data(), old_data.size()));
556      base::FilePath new_chunk;
557      TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&new_chunk));
558      ScopedPathUnlinker new_unlinker(new_chunk.value());
559      TEST_AND_RETURN_FALSE(
560          utils::WriteFile(new_chunk.value().c_str(),
561                           new_data.data(), new_data.size()));
562
563      TEST_AND_RETURN_FALSE(
564          BsdiffFiles(old_chunk.value(), new_chunk.value(), &bsdiff_delta));
565      CHECK_GT(bsdiff_delta.size(), static_cast<chromeos::Blob::size_type>(0));
566      if (bsdiff_delta.size() < data_blob->size()) {
567        if (src_ops_allowed) {
568          operation.set_type(
569              DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF);
570        } else {
571          operation.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
572        }
573        data_blob = &bsdiff_delta;
574      }
575    }
576  }
577
578  size_t removed_bytes = 0;
579  // Remove identical src/dst block ranges in MOVE operations.
580  if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
581    removed_bytes = RemoveIdenticalBlockRanges(
582        &src_extents, &dst_extents, new_data.size());
583  }
584  // Set legacy src_length and dst_length fields.
585  operation.set_src_length(old_data.size() - removed_bytes);
586  operation.set_dst_length(new_data.size() - removed_bytes);
587
588  // Embed extents in the operation.
589  StoreExtents(src_extents, operation.mutable_src_extents());
590  StoreExtents(dst_extents, operation.mutable_dst_extents());
591
592  // Replace operations should not have source extents.
593  if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
594      operation.type() ==
595          DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
596    operation.clear_src_extents();
597    operation.clear_src_length();
598  }
599
600  *out_data = std::move(*data_blob);
601  *out_op = operation;
602
603  return true;
604}
605
606// Runs the bsdiff tool on two files and returns the resulting delta in
607// 'out'. Returns true on success.
608bool BsdiffFiles(const string& old_file,
609                 const string& new_file,
610                 chromeos::Blob* out) {
611  const string kPatchFile = "delta.patchXXXXXX";
612  string patch_file_path;
613
614  TEST_AND_RETURN_FALSE(
615      utils::MakeTempFile(kPatchFile, &patch_file_path, nullptr));
616
617  vector<string> cmd;
618  cmd.push_back(kBsdiffPath);
619  cmd.push_back(old_file);
620  cmd.push_back(new_file);
621  cmd.push_back(patch_file_path);
622
623  int rc = 1;
624  chromeos::Blob patch_file;
625  TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, nullptr));
626  TEST_AND_RETURN_FALSE(rc == 0);
627  TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
628  unlink(patch_file_path.c_str());
629  return true;
630}
631
632// Returns true if |op| is a no-op operation that doesn't do any useful work
633// (e.g., a move operation that copies blocks onto themselves).
634bool IsNoopOperation(const DeltaArchiveManifest_InstallOperation& op) {
635  return (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE &&
636          ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
637}
638
639void FilterNoopOperations(vector<AnnotatedOperation>* ops) {
640  ops->erase(
641      std::remove_if(
642          ops->begin(), ops->end(),
643          [](const AnnotatedOperation& aop){return IsNoopOperation(aop.op);}),
644      ops->end());
645}
646
647bool InitializePartitionInfo(const PartitionConfig& part, PartitionInfo* info) {
648  info->set_size(part.size);
649  OmahaHashCalculator hasher;
650  TEST_AND_RETURN_FALSE(hasher.UpdateFile(part.path, part.size) ==
651                        static_cast<off_t>(part.size));
652  TEST_AND_RETURN_FALSE(hasher.Finalize());
653  const chromeos::Blob& hash = hasher.raw_hash();
654  info->set_hash(hash.data(), hash.size());
655  LOG(INFO) << part.path << ": size=" << part.size << " hash=" << hasher.hash();
656  return true;
657}
658
659bool CompareAopsByDestination(AnnotatedOperation first_aop,
660                              AnnotatedOperation second_aop) {
661  // We want empty operations to be at the end of the payload.
662  if (!first_aop.op.dst_extents().size() || !second_aop.op.dst_extents().size())
663    return ((!first_aop.op.dst_extents().size()) <
664            (!second_aop.op.dst_extents().size()));
665  uint32_t first_dst_start = first_aop.op.dst_extents(0).start_block();
666  uint32_t second_dst_start = second_aop.op.dst_extents(0).start_block();
667  return first_dst_start < second_dst_start;
668}
669
670}  // namespace diff_utils
671
672}  // namespace chromeos_update_engine
673