delta_diff_utils.cc revision 5ef5d4561dbc40c128d1e9bbd8e2da525adcf581 
1//
2// Copyright (C) 2015 The Android Open Source Project
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8//      http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15//
16
17#include "update_engine/payload_generator/delta_diff_utils.h"
18
19#include <endian.h>
20#if defined(__clang__)
21// TODO: Remove these pragmas when b/35721782 is fixed.
22#pragma clang diagnostic push
23#pragma clang diagnostic ignored "-Wmacro-redefined"
24#endif
25#include <ext2fs/ext2fs.h>
26#if defined(__clang__)
27#pragma clang diagnostic pop
28#endif
29
30
31#include <algorithm>
32#include <map>
33
34#include <base/files/file_util.h>
35#include <base/format_macros.h>
36#include <base/strings/stringprintf.h>
37
38#include "update_engine/common/hash_calculator.h"
39#include "update_engine/common/subprocess.h"
40#include "update_engine/common/utils.h"
41#include "update_engine/payload_generator/block_mapping.h"
42#include "update_engine/payload_generator/bzip.h"
43#include "update_engine/payload_generator/delta_diff_generator.h"
44#include "update_engine/payload_generator/extent_ranges.h"
45#include "update_engine/payload_generator/extent_utils.h"
46#include "update_engine/payload_generator/xz.h"
47
48using std::map;
49using std::string;
50using std::vector;
51
52namespace chromeos_update_engine {
53namespace {
54
55const char* const kBsdiffPath = "bsdiff";
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 uint64_t kMaxBsdiffDestinationSize = 200 * 1024 * 1024;  // bytes
63
64// The maximum destination size allowed for puffdiff. In general, puffdiff
65// should work for arbitrary big files, but the payload application is quite
66// memory intensive, so we limit these operations to 50 MiB.
67const uint64_t kMaxPuffdiffDestinationSize = 50 * 1024 * 1024;  // bytes
68
69// Process a range of blocks from |range_start| to |range_end| in the extent at
70// position |*idx_p| of |extents|. If |do_remove| is true, this range will be
71// removed, which may cause the extent to be trimmed, split or removed entirely.
72// The value of |*idx_p| is updated to point to the next extent to be processed.
73// Returns true iff the next extent to process is a new or updated one.
74bool ProcessExtentBlockRange(vector<Extent>* extents, size_t* idx_p,
75                             const bool do_remove, uint64_t range_start,
76                             uint64_t range_end) {
77  size_t idx = *idx_p;
78  uint64_t start_block = (*extents)[idx].start_block();
79  uint64_t num_blocks = (*extents)[idx].num_blocks();
80  uint64_t range_size = range_end - range_start;
81
82  if (do_remove) {
83    if (range_size == num_blocks) {
84      // Remove the entire extent.
85      extents->erase(extents->begin() + idx);
86    } else if (range_end == num_blocks) {
87      // Trim the end of the extent.
88      (*extents)[idx].set_num_blocks(num_blocks - range_size);
89      idx++;
90    } else if (range_start == 0) {
91      // Trim the head of the extent.
92      (*extents)[idx].set_start_block(start_block + range_size);
93      (*extents)[idx].set_num_blocks(num_blocks - range_size);
94    } else {
95      // Trim the middle, splitting the remainder into two parts.
96      (*extents)[idx].set_num_blocks(range_start);
97      Extent e;
98      e.set_start_block(start_block + range_end);
99      e.set_num_blocks(num_blocks - range_end);
100      idx++;
101      extents->insert(extents->begin() + idx, e);
102    }
103  } else if (range_end == num_blocks) {
104    // Done with this extent.
105    idx++;
106  } else {
107    return false;
108  }
109
110  *idx_p = idx;
111  return true;
112}
113
114// Remove identical corresponding block ranges in |src_extents| and
115// |dst_extents|. Used for preventing moving of blocks onto themselves during
116// MOVE operations. The value of |total_bytes| indicates the actual length of
117// content; this may be slightly less than the total size of blocks, in which
118// case the last block is only partly occupied with data. Returns the total
119// number of bytes removed.
120size_t RemoveIdenticalBlockRanges(vector<Extent>* src_extents,
121                                  vector<Extent>* dst_extents,
122                                  const size_t total_bytes) {
123  size_t src_idx = 0;
124  size_t dst_idx = 0;
125  uint64_t src_offset = 0, dst_offset = 0;
126  size_t removed_bytes = 0, nonfull_block_bytes;
127  bool do_remove = false;
128  while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) {
129    do_remove = ((*src_extents)[src_idx].start_block() + src_offset ==
130                 (*dst_extents)[dst_idx].start_block() + dst_offset);
131
132    uint64_t src_num_blocks = (*src_extents)[src_idx].num_blocks();
133    uint64_t dst_num_blocks = (*dst_extents)[dst_idx].num_blocks();
134    uint64_t min_num_blocks = std::min(src_num_blocks - src_offset,
135                                       dst_num_blocks - dst_offset);
136    uint64_t prev_src_offset = src_offset;
137    uint64_t prev_dst_offset = dst_offset;
138    src_offset += min_num_blocks;
139    dst_offset += min_num_blocks;
140
141    bool new_src = ProcessExtentBlockRange(src_extents, &src_idx, do_remove,
142                                           prev_src_offset, src_offset);
143    bool new_dst = ProcessExtentBlockRange(dst_extents, &dst_idx, do_remove,
144                                           prev_dst_offset, dst_offset);
145    if (new_src) {
146      src_offset = 0;
147    }
148    if (new_dst) {
149      dst_offset = 0;
150    }
151
152    if (do_remove)
153      removed_bytes += min_num_blocks * kBlockSize;
154  }
155
156  // If we removed the last block and this block is only partly used by file
157  // content, deduct the unused portion from the total removed byte count.
158  if (do_remove && (nonfull_block_bytes = total_bytes % kBlockSize))
159    removed_bytes -= kBlockSize - nonfull_block_bytes;
160
161  return removed_bytes;
162}
163
164}  // namespace
165
166namespace diff_utils {
167
168bool DeltaReadPartition(vector<AnnotatedOperation>* aops,
169                        const PartitionConfig& old_part,
170                        const PartitionConfig& new_part,
171                        ssize_t hard_chunk_blocks,
172                        size_t soft_chunk_blocks,
173                        const PayloadVersion& version,
174                        BlobFileWriter* blob_file) {
175  ExtentRanges old_visited_blocks;
176  ExtentRanges new_visited_blocks;
177
178  TEST_AND_RETURN_FALSE(DeltaMovedAndZeroBlocks(
179      aops,
180      old_part.path,
181      new_part.path,
182      old_part.size / kBlockSize,
183      new_part.size / kBlockSize,
184      soft_chunk_blocks,
185      version,
186      blob_file,
187      &old_visited_blocks,
188      &new_visited_blocks));
189
190  map<string, vector<Extent>> old_files_map;
191  if (old_part.fs_interface) {
192    vector<FilesystemInterface::File> old_files;
193    old_part.fs_interface->GetFiles(&old_files);
194    for (const FilesystemInterface::File& file : old_files)
195      old_files_map[file.name] = file.extents;
196  }
197
198  TEST_AND_RETURN_FALSE(new_part.fs_interface);
199  vector<FilesystemInterface::File> new_files;
200  new_part.fs_interface->GetFiles(&new_files);
201
202  // The processing is very straightforward here, we generate operations for
203  // every file (and pseudo-file such as the metadata) in the new filesystem
204  // based on the file with the same name in the old filesystem, if any.
205  // Files with overlapping data blocks (like hardlinks or filesystems with tail
206  // packing or compression where the blocks store more than one file) are only
207  // generated once in the new image, but are also used only once from the old
208  // image due to some simplifications (see below).
209  for (const FilesystemInterface::File& new_file : new_files) {
210    // Ignore the files in the new filesystem without blocks. Symlinks with
211    // data blocks (for example, symlinks bigger than 60 bytes in ext2) are
212    // handled as normal files. We also ignore blocks that were already
213    // processed by a previous file.
214    vector<Extent> new_file_extents = FilterExtentRanges(
215        new_file.extents, new_visited_blocks);
216    new_visited_blocks.AddExtents(new_file_extents);
217
218    if (new_file_extents.empty())
219      continue;
220
221    LOG(INFO) << "Encoding file " << new_file.name << " ("
222              << BlocksInExtents(new_file_extents) << " blocks)";
223
224    // We can't visit each dst image inode more than once, as that would
225    // duplicate work. Here, we avoid visiting each source image inode
226    // more than once. Technically, we could have multiple operations
227    // that read the same blocks from the source image for diffing, but
228    // we choose not to avoid complexity. Eventually we will move away
229    // from using a graph/cycle detection/etc to generate diffs, and at that
230    // time, it will be easy (non-complex) to have many operations read
231    // from the same source blocks. At that time, this code can die. -adlr
232    vector<Extent> old_file_extents = FilterExtentRanges(
233        old_files_map[new_file.name], old_visited_blocks);
234    old_visited_blocks.AddExtents(old_file_extents);
235
236    TEST_AND_RETURN_FALSE(DeltaReadFile(aops,
237                                        old_part.path,
238                                        new_part.path,
239                                        old_file_extents,
240                                        new_file_extents,
241                                        new_file.name,  // operation name
242                                        hard_chunk_blocks,
243                                        version,
244                                        blob_file));
245  }
246  // Process all the blocks not included in any file. We provided all the unused
247  // blocks in the old partition as available data.
248  vector<Extent> new_unvisited = {
249      ExtentForRange(0, new_part.size / kBlockSize)};
250  new_unvisited = FilterExtentRanges(new_unvisited, new_visited_blocks);
251  if (new_unvisited.empty())
252    return true;
253
254  vector<Extent> old_unvisited;
255  if (old_part.fs_interface) {
256    old_unvisited.push_back(ExtentForRange(0, old_part.size / kBlockSize));
257    old_unvisited = FilterExtentRanges(old_unvisited, old_visited_blocks);
258  }
259
260  LOG(INFO) << "Scanning " << BlocksInExtents(new_unvisited)
261            << " unwritten blocks using chunk size of "
262            << soft_chunk_blocks << " blocks.";
263  // We use the soft_chunk_blocks limit for the <non-file-data> as we don't
264  // really know the structure of this data and we should not expect it to have
265  // redundancy between partitions.
266  TEST_AND_RETURN_FALSE(DeltaReadFile(aops,
267                                      old_part.path,
268                                      new_part.path,
269                                      old_unvisited,
270                                      new_unvisited,
271                                      "<non-file-data>",  // operation name
272                                      soft_chunk_blocks,
273                                      version,
274                                      blob_file));
275
276  return true;
277}
278
279bool DeltaMovedAndZeroBlocks(vector<AnnotatedOperation>* aops,
280                             const string& old_part,
281                             const string& new_part,
282                             size_t old_num_blocks,
283                             size_t new_num_blocks,
284                             ssize_t chunk_blocks,
285                             const PayloadVersion& version,
286                             BlobFileWriter* blob_file,
287                             ExtentRanges* old_visited_blocks,
288                             ExtentRanges* new_visited_blocks) {
289  vector<BlockMapping::BlockId> old_block_ids;
290  vector<BlockMapping::BlockId> new_block_ids;
291  TEST_AND_RETURN_FALSE(MapPartitionBlocks(old_part,
292                                           new_part,
293                                           old_num_blocks * kBlockSize,
294                                           new_num_blocks * kBlockSize,
295                                           kBlockSize,
296                                           &old_block_ids,
297                                           &new_block_ids));
298
299  // If the update is inplace, we map all the blocks that didn't move,
300  // regardless of the contents since they are already copied and no operation
301  // is required.
302  if (version.InplaceUpdate()) {
303    uint64_t num_blocks = std::min(old_num_blocks, new_num_blocks);
304    for (uint64_t block = 0; block < num_blocks; block++) {
305      if (old_block_ids[block] == new_block_ids[block] &&
306          !old_visited_blocks->ContainsBlock(block) &&
307          !new_visited_blocks->ContainsBlock(block)) {
308        old_visited_blocks->AddBlock(block);
309        new_visited_blocks->AddBlock(block);
310      }
311    }
312  }
313
314  // A mapping from the block_id to the list of block numbers with that block id
315  // in the old partition. This is used to lookup where in the old partition
316  // is a block from the new partition.
317  map<BlockMapping::BlockId, vector<uint64_t>> old_blocks_map;
318
319  for (uint64_t block = old_num_blocks; block-- > 0; ) {
320    if (old_block_ids[block] != 0 && !old_visited_blocks->ContainsBlock(block))
321      old_blocks_map[old_block_ids[block]].push_back(block);
322
323    // Mark all zeroed blocks in the old image as "used" since it doesn't make
324    // any sense to spend I/O to read zeros from the source partition and more
325    // importantly, these could sometimes be blocks discarded in the SSD which
326    // would read non-zero values.
327    if (old_block_ids[block] == 0)
328      old_visited_blocks->AddBlock(block);
329  }
330
331  // The collection of blocks in the new partition with just zeros. This is a
332  // common case for free-space that's also problematic for bsdiff, so we want
333  // to optimize it using REPLACE_BZ operations. The blob for a REPLACE_BZ of
334  // just zeros is so small that it doesn't make sense to spend the I/O reading
335  // zeros from the old partition.
336  vector<Extent> new_zeros;
337
338  vector<Extent> old_identical_blocks;
339  vector<Extent> new_identical_blocks;
340
341  for (uint64_t block = 0; block < new_num_blocks; block++) {
342    // Only produce operations for blocks that were not yet visited.
343    if (new_visited_blocks->ContainsBlock(block))
344      continue;
345    if (new_block_ids[block] == 0) {
346      AppendBlockToExtents(&new_zeros, block);
347      continue;
348    }
349
350    auto old_blocks_map_it = old_blocks_map.find(new_block_ids[block]);
351    // Check if the block exists in the old partition at all.
352    if (old_blocks_map_it == old_blocks_map.end() ||
353        old_blocks_map_it->second.empty())
354      continue;
355
356    AppendBlockToExtents(&old_identical_blocks,
357                         old_blocks_map_it->second.back());
358    AppendBlockToExtents(&new_identical_blocks, block);
359    // We can't reuse source blocks in minor version 1 because the cycle
360    // breaking algorithm used in the in-place update doesn't support that.
361    if (version.InplaceUpdate())
362      old_blocks_map_it->second.pop_back();
363  }
364
365  // Produce operations for the zero blocks split per output extent.
366  // TODO(deymo): Produce ZERO operations instead of calling DeltaReadFile().
367  size_t num_ops = aops->size();
368  new_visited_blocks->AddExtents(new_zeros);
369  for (const Extent& extent : new_zeros) {
370    TEST_AND_RETURN_FALSE(DeltaReadFile(aops,
371                                        "",
372                                        new_part,
373                                        vector<Extent>(),        // old_extents
374                                        vector<Extent>{extent},  // new_extents
375                                        "<zeros>",
376                                        chunk_blocks,
377                                        version,
378                                        blob_file));
379  }
380  LOG(INFO) << "Produced " << (aops->size() - num_ops) << " operations for "
381            << BlocksInExtents(new_zeros) << " zeroed blocks";
382
383  // Produce MOVE/SOURCE_COPY operations for the moved blocks.
384  num_ops = aops->size();
385  if (chunk_blocks == -1)
386    chunk_blocks = new_num_blocks;
387  uint64_t used_blocks = 0;
388  old_visited_blocks->AddExtents(old_identical_blocks);
389  new_visited_blocks->AddExtents(new_identical_blocks);
390  for (const Extent& extent : new_identical_blocks) {
391    // We split the operation at the extent boundary or when bigger than
392    // chunk_blocks.
393    for (uint64_t op_block_offset = 0; op_block_offset < extent.num_blocks();
394         op_block_offset += chunk_blocks) {
395      aops->emplace_back();
396      AnnotatedOperation* aop = &aops->back();
397      aop->name = "<identical-blocks>";
398      aop->op.set_type(version.OperationAllowed(InstallOperation::SOURCE_COPY)
399                           ? InstallOperation::SOURCE_COPY
400                           : InstallOperation::MOVE);
401
402      uint64_t chunk_num_blocks =
403          std::min(static_cast<uint64_t>(extent.num_blocks()) - op_block_offset,
404                   static_cast<uint64_t>(chunk_blocks));
405
406      // The current operation represents the move/copy operation for the
407      // sublist starting at |used_blocks| of length |chunk_num_blocks| where
408      // the src and dst are from |old_identical_blocks| and
409      // |new_identical_blocks| respectively.
410      StoreExtents(
411          ExtentsSublist(old_identical_blocks, used_blocks, chunk_num_blocks),
412          aop->op.mutable_src_extents());
413
414      Extent* op_dst_extent = aop->op.add_dst_extents();
415      op_dst_extent->set_start_block(extent.start_block() + op_block_offset);
416      op_dst_extent->set_num_blocks(chunk_num_blocks);
417      CHECK(
418          vector<Extent>{*op_dst_extent} ==  // NOLINT(whitespace/braces)
419          ExtentsSublist(new_identical_blocks, used_blocks, chunk_num_blocks));
420
421      used_blocks += chunk_num_blocks;
422    }
423  }
424  LOG(INFO) << "Produced " << (aops->size() - num_ops) << " operations for "
425            << used_blocks << " identical blocks moved";
426
427  return true;
428}
429
430bool DeltaReadFile(vector<AnnotatedOperation>* aops,
431                   const string& old_part,
432                   const string& new_part,
433                   const vector<Extent>& old_extents,
434                   const vector<Extent>& new_extents,
435                   const string& name,
436                   ssize_t chunk_blocks,
437                   const PayloadVersion& version,
438                   BlobFileWriter* blob_file) {
439  brillo::Blob data;
440  InstallOperation operation;
441
442  uint64_t total_blocks = BlocksInExtents(new_extents);
443  if (chunk_blocks == -1)
444    chunk_blocks = total_blocks;
445
446  for (uint64_t block_offset = 0; block_offset < total_blocks;
447      block_offset += chunk_blocks) {
448    // Split the old/new file in the same chunks. Note that this could drop
449    // some information from the old file used for the new chunk. If the old
450    // file is smaller (or even empty when there's no old file) the chunk will
451    // also be empty.
452    vector<Extent> old_extents_chunk = ExtentsSublist(
453        old_extents, block_offset, chunk_blocks);
454    vector<Extent> new_extents_chunk = ExtentsSublist(
455        new_extents, block_offset, chunk_blocks);
456    NormalizeExtents(&old_extents_chunk);
457    NormalizeExtents(&new_extents_chunk);
458
459    TEST_AND_RETURN_FALSE(ReadExtentsToDiff(old_part,
460                                            new_part,
461                                            old_extents_chunk,
462                                            new_extents_chunk,
463                                            version,
464                                            &data,
465                                            &operation));
466
467    // Check if the operation writes nothing.
468    if (operation.dst_extents_size() == 0) {
469      if (operation.type() == InstallOperation::MOVE) {
470        LOG(INFO) << "Empty MOVE operation ("
471                  << name << "), skipping";
472        continue;
473      } else {
474        LOG(ERROR) << "Empty non-MOVE operation";
475        return false;
476      }
477    }
478
479    // Now, insert into the list of operations.
480    AnnotatedOperation aop;
481    aop.name = name;
482    if (static_cast<uint64_t>(chunk_blocks) < total_blocks) {
483      aop.name = base::StringPrintf("%s:%" PRIu64,
484                                    name.c_str(), block_offset / chunk_blocks);
485    }
486    aop.op = operation;
487
488    // Write the data
489    TEST_AND_RETURN_FALSE(aop.SetOperationBlob(data, blob_file));
490    aops->emplace_back(aop);
491  }
492  return true;
493}
494
495bool GenerateBestFullOperation(const brillo::Blob& new_data,
496                               const PayloadVersion& version,
497                               brillo::Blob* out_blob,
498                               InstallOperation_Type* out_type) {
499  if (new_data.empty())
500    return false;
501
502  if (version.OperationAllowed(InstallOperation::ZERO) &&
503      std::all_of(
504          new_data.begin(), new_data.end(), [](uint8_t x) { return x == 0; })) {
505    // The read buffer is all zeros, so produce a ZERO operation. No need to
506    // check other types of operations in this case.
507    *out_blob = brillo::Blob();
508    *out_type = InstallOperation::ZERO;
509    return true;
510  }
511
512  bool out_blob_set = false;
513
514  // Try compressing |new_data| with xz first.
515  if (version.OperationAllowed(InstallOperation::REPLACE_XZ)) {
516    brillo::Blob new_data_xz;
517    if (XzCompress(new_data, &new_data_xz) && !new_data_xz.empty()) {
518      *out_type = InstallOperation::REPLACE_XZ;
519      *out_blob = std::move(new_data_xz);
520      out_blob_set = true;
521    }
522  }
523
524  // Try compressing it with bzip2.
525  if (version.OperationAllowed(InstallOperation::REPLACE_BZ)) {
526    brillo::Blob new_data_bz;
527    // TODO(deymo): Implement some heuristic to determine if it is worth trying
528    // to compress the blob with bzip2 if we already have a good REPLACE_XZ.
529    if (BzipCompress(new_data, &new_data_bz) && !new_data_bz.empty() &&
530        (!out_blob_set || out_blob->size() > new_data_bz.size())) {
531      // A REPLACE_BZ is better or nothing else was set.
532      *out_type = InstallOperation::REPLACE_BZ;
533      *out_blob = std::move(new_data_bz);
534      out_blob_set = true;
535    }
536  }
537
538  // If nothing else worked or it was badly compressed we try a REPLACE.
539  if (!out_blob_set || out_blob->size() >= new_data.size()) {
540    *out_type = InstallOperation::REPLACE;
541    // This needs to make a copy of the data in the case bzip or xz didn't
542    // compress well, which is not the common case so the performance hit is
543    // low.
544    *out_blob = new_data;
545  }
546  return true;
547}
548
549bool ReadExtentsToDiff(const string& old_part,
550                       const string& new_part,
551                       const vector<Extent>& old_extents,
552                       const vector<Extent>& new_extents,
553                       const PayloadVersion& version,
554                       brillo::Blob* out_data,
555                       InstallOperation* out_op) {
556  InstallOperation operation;
557
558  // We read blocks from old_extents and write blocks to new_extents.
559  uint64_t blocks_to_read = BlocksInExtents(old_extents);
560  uint64_t blocks_to_write = BlocksInExtents(new_extents);
561
562  // Disable bsdiff, and puffdiff when the data is too big.
563  bool bsdiff_allowed =
564      version.OperationAllowed(InstallOperation::SOURCE_BSDIFF) ||
565      version.OperationAllowed(InstallOperation::BSDIFF);
566  if (bsdiff_allowed &&
567      blocks_to_read * kBlockSize > kMaxBsdiffDestinationSize) {
568    LOG(INFO) << "bsdiff blacklisted, data too big: "
569              << blocks_to_read * kBlockSize << " bytes";
570    bsdiff_allowed = false;
571  }
572
573  bool puffdiff_allowed = version.OperationAllowed(InstallOperation::PUFFDIFF);
574  if (puffdiff_allowed &&
575      blocks_to_read * kBlockSize > kMaxPuffdiffDestinationSize) {
576    LOG(INFO) << "puffdiff blacklisted, data too big: "
577              << blocks_to_read * kBlockSize << " bytes";
578    puffdiff_allowed = false;
579  }
580
581  // Make copies of the extents so we can modify them.
582  vector<Extent> src_extents = old_extents;
583  vector<Extent> dst_extents = new_extents;
584
585  // Read in bytes from new data.
586  brillo::Blob new_data;
587  TEST_AND_RETURN_FALSE(utils::ReadExtents(new_part,
588                                           new_extents,
589                                           &new_data,
590                                           kBlockSize * blocks_to_write,
591                                           kBlockSize));
592  TEST_AND_RETURN_FALSE(!new_data.empty());
593
594  // Data blob that will be written to delta file.
595  brillo::Blob data_blob;
596
597  // Try generating a full operation for the given new data, regardless of the
598  // old_data.
599  InstallOperation_Type op_type;
600  TEST_AND_RETURN_FALSE(
601      GenerateBestFullOperation(new_data, version, &data_blob, &op_type));
602  operation.set_type(op_type);
603
604  brillo::Blob old_data;
605  if (blocks_to_read > 0) {
606    // Read old data.
607    TEST_AND_RETURN_FALSE(
608        utils::ReadExtents(old_part, src_extents, &old_data,
609                           kBlockSize * blocks_to_read, kBlockSize));
610    if (old_data == new_data) {
611      // No change in data.
612      operation.set_type(version.OperationAllowed(InstallOperation::SOURCE_COPY)
613                             ? InstallOperation::SOURCE_COPY
614                             : InstallOperation::MOVE);
615      data_blob = brillo::Blob();
616    } else if (bsdiff_allowed || puffdiff_allowed) {
617      // If the source file is considered bsdiff safe (no bsdiff bugs
618      // triggered), see if BSDIFF encoding is smaller.
619      base::FilePath old_chunk;
620      TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&old_chunk));
621      ScopedPathUnlinker old_unlinker(old_chunk.value());
622      TEST_AND_RETURN_FALSE(utils::WriteFile(
623          old_chunk.value().c_str(), old_data.data(), old_data.size()));
624      base::FilePath new_chunk;
625      TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&new_chunk));
626      ScopedPathUnlinker new_unlinker(new_chunk.value());
627      TEST_AND_RETURN_FALSE(utils::WriteFile(
628          new_chunk.value().c_str(), new_data.data(), new_data.size()));
629
630      if (bsdiff_allowed) {
631        brillo::Blob bsdiff_delta;
632        TEST_AND_RETURN_FALSE(DiffFiles(
633            kBsdiffPath, old_chunk.value(), new_chunk.value(), &bsdiff_delta));
634        CHECK_GT(bsdiff_delta.size(), static_cast<brillo::Blob::size_type>(0));
635        if (bsdiff_delta.size() < data_blob.size()) {
636          operation.set_type(
637              version.OperationAllowed(InstallOperation::SOURCE_BSDIFF)
638                  ? InstallOperation::SOURCE_BSDIFF
639                  : InstallOperation::BSDIFF);
640          data_blob = std::move(bsdiff_delta);
641        }
642      }
643      if (puffdiff_allowed) {
644        LOG(ERROR) << "puffdiff is not supported yet!";
645        return false;
646      }
647    }
648  }
649
650  size_t removed_bytes = 0;
651  // Remove identical src/dst block ranges in MOVE operations.
652  if (operation.type() == InstallOperation::MOVE) {
653    removed_bytes = RemoveIdenticalBlockRanges(
654        &src_extents, &dst_extents, new_data.size());
655  }
656  // Set legacy src_length and dst_length fields.
657  operation.set_src_length(old_data.size() - removed_bytes);
658  operation.set_dst_length(new_data.size() - removed_bytes);
659
660  // Embed extents in the operation.
661  StoreExtents(src_extents, operation.mutable_src_extents());
662  StoreExtents(dst_extents, operation.mutable_dst_extents());
663
664  // Replace operations should not have source extents.
665  if (IsAReplaceOperation(operation.type())) {
666    operation.clear_src_extents();
667    operation.clear_src_length();
668  }
669
670  *out_data = std::move(data_blob);
671  *out_op = operation;
672  return true;
673}
674
675// Runs the bsdiff tool in |diff_path| on two files and returns the
676// resulting delta in |out|. Returns true on success.
677bool DiffFiles(const string& diff_path,
678               const string& old_file,
679               const string& new_file,
680               brillo::Blob* out) {
681  const string kPatchFile = "delta.patchXXXXXX";
682  string patch_file_path;
683
684  TEST_AND_RETURN_FALSE(
685      utils::MakeTempFile(kPatchFile, &patch_file_path, nullptr));
686
687  vector<string> cmd;
688  cmd.push_back(diff_path);
689  cmd.push_back(old_file);
690  cmd.push_back(new_file);
691  cmd.push_back(patch_file_path);
692
693  int rc = 1;
694  string stdout;
695  TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, &stdout));
696  if (rc != 0) {
697    LOG(ERROR) << diff_path << " returned " << rc << std::endl << stdout;
698    return false;
699  }
700  TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
701  unlink(patch_file_path.c_str());
702  return true;
703}
704
705bool IsAReplaceOperation(InstallOperation_Type op_type) {
706  return (op_type == InstallOperation::REPLACE ||
707          op_type == InstallOperation::REPLACE_BZ ||
708          op_type == InstallOperation::REPLACE_XZ);
709}
710
711// Returns true if |op| is a no-op operation that doesn't do any useful work
712// (e.g., a move operation that copies blocks onto themselves).
713bool IsNoopOperation(const InstallOperation& op) {
714  return (op.type() == InstallOperation::MOVE &&
715          ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
716}
717
718void FilterNoopOperations(vector<AnnotatedOperation>* ops) {
719  ops->erase(
720      std::remove_if(
721          ops->begin(), ops->end(),
722          [](const AnnotatedOperation& aop){return IsNoopOperation(aop.op);}),
723      ops->end());
724}
725
726bool InitializePartitionInfo(const PartitionConfig& part, PartitionInfo* info) {
727  info->set_size(part.size);
728  HashCalculator hasher;
729  TEST_AND_RETURN_FALSE(hasher.UpdateFile(part.path, part.size) ==
730                        static_cast<off_t>(part.size));
731  TEST_AND_RETURN_FALSE(hasher.Finalize());
732  const brillo::Blob& hash = hasher.raw_hash();
733  info->set_hash(hash.data(), hash.size());
734  LOG(INFO) << part.path << ": size=" << part.size << " hash=" << hasher.hash();
735  return true;
736}
737
738bool CompareAopsByDestination(AnnotatedOperation first_aop,
739                              AnnotatedOperation second_aop) {
740  // We want empty operations to be at the end of the payload.
741  if (!first_aop.op.dst_extents().size() || !second_aop.op.dst_extents().size())
742    return ((!first_aop.op.dst_extents().size()) <
743            (!second_aop.op.dst_extents().size()));
744  uint32_t first_dst_start = first_aop.op.dst_extents(0).start_block();
745  uint32_t second_dst_start = second_aop.op.dst_extents(0).start_block();
746  return first_dst_start < second_dst_start;
747}
748
749bool IsExtFilesystem(const string& device) {
750  brillo::Blob header;
751  // See include/linux/ext2_fs.h for more details on the structure. We obtain
752  // ext2 constants from ext2fs/ext2fs.h header but we don't link with the
753  // library.
754  if (!utils::ReadFileChunk(
755          device, 0, SUPERBLOCK_OFFSET + SUPERBLOCK_SIZE, &header) ||
756      header.size() < SUPERBLOCK_OFFSET + SUPERBLOCK_SIZE)
757    return false;
758
759  const uint8_t* superblock = header.data() + SUPERBLOCK_OFFSET;
760
761  // ext3_fs.h: ext3_super_block.s_blocks_count
762  uint32_t block_count =
763      *reinterpret_cast<const uint32_t*>(superblock + 1 * sizeof(int32_t));
764
765  // ext3_fs.h: ext3_super_block.s_log_block_size
766  uint32_t log_block_size =
767      *reinterpret_cast<const uint32_t*>(superblock + 6 * sizeof(int32_t));
768
769  // ext3_fs.h: ext3_super_block.s_magic
770  uint16_t magic =
771      *reinterpret_cast<const uint16_t*>(superblock + 14 * sizeof(int32_t));
772
773  block_count = le32toh(block_count);
774  log_block_size = le32toh(log_block_size) + EXT2_MIN_BLOCK_LOG_SIZE;
775  magic = le16toh(magic);
776
777  if (magic != EXT2_SUPER_MAGIC)
778    return false;
779
780  // Sanity check the parameters.
781  TEST_AND_RETURN_FALSE(log_block_size >= EXT2_MIN_BLOCK_LOG_SIZE &&
782                        log_block_size <= EXT2_MAX_BLOCK_LOG_SIZE);
783  TEST_AND_RETURN_FALSE(block_count > 0);
784  return true;
785}
786
787}  // namespace diff_utils
788
789}  // namespace chromeos_update_engine
790