Add support for bsdiff of file system metadata blocks

metadata.cc

+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <algorithm>
+#include <string>
+#include <vector>
+
+#include <base/string_util.h>
+#include <et/com_err.h>
+#include <ext2fs/ext2_io.h>
+#include <ext2fs/ext2fs.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/delta_diff_generator.h"
+#include "update_engine/extent_ranges.h"
+#include "update_engine/graph_utils.h"
+#include "update_engine/metadata.h"
+#include "update_engine/utils.h"
+
+using std::min;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+  const size_t kBlockSize = 4096;

[adlr, 2010/12/15 03:11:23]

unindent

[thieule, 2010/12/15 19:57:01]

Done.

+}  // namespace {}
+
+typedef DeltaDiffGenerator::Block Block;
+
+// Read data from the specified extents.
+bool ReadExtentsData(const ext2_filsys fs,

[petkov, 2010/12/15 18:40:32]

this and all other internal only routines should be part of the anonymous
namespace

[thieule, 2010/12/15 19:57:01]

Done.

+                     const vector<Extent>& extents,
+                     vector<char>* data) {
+  // Resize the data buffer to hold all data in the extents
+  size_t num_data_blocks = 0;
+  for (vector<Extent>::const_iterator it = extents.begin();
+       it != extents.end(); it++) {
+    num_data_blocks += it->num_blocks();
+  }
+
+  data->resize(num_data_blocks * kBlockSize);
+
+  // Read in the data blocks

[adlr, 2010/12/15 03:11:23]

would "metadata blocks" be more appropriate?

[thieule, 2010/12/15 19:57:01]

ReadExtentsData is generic and just reads data from the specified |extents|.  It
could be metadata, free space, etc.

On 2010/12/15 03:11:23, adlr wrote:

+  const size_t max_read_blocks = 256;

[adlr, 2010/12/15 03:11:23]

kMaxReadBlocks

[thieule, 2010/12/15 19:57:01]

Done.

+  vector<Block>::size_type blocks_copied_count = 0;
+  for (vector<Extent>::const_iterator it = extents.begin();
+       it != extents.end(); it++) {
+    vector<Block>::size_type blocks_read = 0;
+    while (blocks_read < it->num_blocks()) {
+      const int copy_block_cnt =
+          min(max_read_blocks,
+              static_cast<vector<char>::size_type>(

[adlr, 2010/12/15 03:11:23]

why vector<char>? you could just use size_t or vector<Block> to be consistent

[thieule, 2010/12/15 19:57:01]

Had a synapse misfire here.

On 2010/12/15 03:11:23, adlr wrote:

+                  it->num_blocks() - blocks_read));
+      TEST_AND_RETURN_FALSE_ERRCODE(
+          io_channel_read_blk(fs->io,
+                              it->start_block() + blocks_read,
+                              copy_block_cnt,
+                              &(*data)[blocks_copied_count * kBlockSize]));
+      blocks_read += copy_block_cnt;
+      blocks_copied_count += copy_block_cnt;
+    }
+  }
+
+  return true;
+}
+
+// Compute the bsdiff between two metadata blobs.
+bool ComputeMetadataBsdiff(const vector<char>& old_metadata,
+                           const vector<char>& new_metadata,
+                           vector<char>* bsdiff_delta) {
+  const string kTempFileTemplate("/tmp/CrAU_temp_data.XXXXXX");
+
+  // Write the metadata buffers to temporary files
+  int old_fd;
+  string temp_old_file_path;
+  TEST_AND_RETURN_FALSE(
+      utils::MakeTempFile(kTempFileTemplate, &temp_old_file_path, &old_fd));
+  TEST_AND_RETURN_FALSE(old_fd >= 0);
+  ScopedPathUnlinker temp_old_file_path_unlinker(temp_old_file_path);
+  ScopedFdCloser old_fd_closer(&old_fd);
+  TEST_AND_RETURN_FALSE(utils::WriteAll(old_fd,
+                                        &old_metadata[0],
+                                        old_metadata.size()));
+
+  int new_fd;
+  string temp_new_file_path;
+  TEST_AND_RETURN_FALSE(
+      utils::MakeTempFile(kTempFileTemplate, &temp_new_file_path, &new_fd));
+  TEST_AND_RETURN_FALSE(new_fd >= 0);
+  ScopedPathUnlinker temp_new_file_path_unlinker(temp_new_file_path);
+  ScopedFdCloser new_fd_closer(&new_fd);
+  TEST_AND_RETURN_FALSE(utils::WriteAll(new_fd,
+                                        &new_metadata[0],
+                                        new_metadata.size()));
+
+  // Perform bsdiff on these files
+  TEST_AND_RETURN_FALSE(
+      BsdiffFiles(temp_old_file_path, temp_new_file_path, bsdiff_delta));
+  CHECK_GT(bsdiff_delta->size(), 0);

[adlr, 2010/12/15 03:11:23]

do you really want to crash if this fails? would TEST_AND_RETURN_FALSE() be
better?

[thieule, 2010/12/15 19:57:01]

I've removed this, it's a redundant check.  The better place to check this is
below in AddMetadataExtents() where there is more context as to why the
bsdiff_delta->size() must be greater than zero (since it's only called when we
know the two metadata are different).

On 2010/12/15 03:11:23, adlr wrote:

+
+  return true;
+}
+
+// Add the specified metadata extents to the graph and blocks vector.
+bool AddMetadataExtents(Graph* graph,
+                        vector<Block>* blocks,
+                        const ext2_filsys fs_old,
+                        const ext2_filsys fs_new,
+                        const string& metadata_name,
+                        const vector<Extent>& extents,
+                        int data_fd,
+                        off_t* data_file_size) {
+  vector<char> data;  // Data blob that will be written to delta file.
+
+  // Read in the metadata blocks from the old and new image.

[adlr, 2010/12/15 03:11:23]

add { (more below)

[thieule, 2010/12/15 19:57:01]

Done.

+  vector<char> old_data;
+  TEST_AND_RETURN_FALSE(ReadExtentsData(fs_old, extents, &old_data));
+
+  vector<char> new_data;
+  TEST_AND_RETURN_FALSE(ReadExtentsData(fs_new, extents, &new_data));
+
+  // Determine the best way to compress this.
+  vector<char> new_data_bz;
+  TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
+  CHECK(!new_data_bz.empty());
+
+  DeltaArchiveManifest_InstallOperation op;
+  size_t current_best_size = 0;
+  if (new_data.size() <= new_data_bz.size()) {
+    op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+    current_best_size = new_data.size();
+    data = new_data;
+  } else {
+    op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+    current_best_size = new_data_bz.size();
+    data = new_data_bz;
+  }
+
+  if (old_data == new_data) {
+    // No change in data.
+    op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+    current_best_size = 0;
+    data.clear();
+  } else {
+    // Try bsdiff of old to new data
+    vector<char> bsdiff_delta;
+    TEST_AND_RETURN_FALSE(ComputeMetadataBsdiff(old_data,
+                                                new_data,
+                                                &bsdiff_delta));
+    CHECK_GT(bsdiff_delta.size(), 0);
+
+    if (bsdiff_delta.size() < current_best_size) {
+      op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+      current_best_size = bsdiff_delta.size();
+      data = bsdiff_delta;
+    }
+  }
+

[adlr, 2010/12/15 03:11:23]

add } here

this deallocates the extra copy/copies of data

[thieule, 2010/12/15 19:57:01]

Done.

+  CHECK_EQ(data.size(), current_best_size);
+
+  // Set the source and dest extents to be the same since the filesystem
+  // structures are identical
+  if (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE ||
+      op.type() == DeltaArchiveManifest_InstallOperation_Type_BSDIFF) {
+    DeltaDiffGenerator::StoreExtents(extents, op.mutable_src_extents());
+    op.set_src_length(old_data.size());
+  }
+
+  DeltaDiffGenerator::StoreExtents(extents, op.mutable_dst_extents());
+  op.set_dst_length(new_data.size());
+
+  // Write data to output file
+  if (op.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+    op.set_data_offset(*data_file_size);
+    op.set_data_length(data.size());
+  }
+
+  TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, &data[0], data.size()));
+  *data_file_size += data.size();
+
+  // Now, insert into graph and blocks vector
+  graph->resize(graph->size() + 1);
+  Vertex::Index vertex = graph->size() - 1;
+  (*graph)[vertex].op = op;
+  CHECK((*graph)[vertex].op.has_type());
+  (*graph)[vertex].file_name = metadata_name;
+
+  TEST_AND_RETURN_FALSE(AddInstallOpToBlocksVector((*graph)[vertex].op,
+                                                   blocks,
+                                                   *graph,
+                                                   vertex));
+
+  return true;
+}
+
+// Reads the file system metadata extents.
+bool ReadFilesystemMetadata(Graph* graph,
+                            vector<Block>* blocks,
+                            const ext2_filsys fs_old,
+                            const ext2_filsys fs_new,
+                            int data_fd,
+                            off_t* data_file_size) {
+  LOG(INFO) << "Processing <rootfs-metadata>";
+
+  // Read all the extents that belong to the main file system metadata.
+  // The metadata blocks are at the start of each block group and goes
+  // until the end of the inode table.
+  for (dgrp_t bg = 0; bg < fs_old->group_desc_count; bg++) {
+    struct ext2_group_desc* group_desc = &fs_old->group_desc[bg];
+    __u32 num_metadata_blocks = (group_desc->bg_inode_table +
+                                 fs_old->inode_blocks_per_group) -
+                                 (bg * fs_old->super->s_blocks_per_group);
+    __u32 bg_start_block = bg * fs_old->super->s_blocks_per_group;
+
+    // Due to bsdiff slowness, we're going to break each block group down
+    // into metadata chunks and feed them to bsdiff.
+    __u32 num_chunks = 4;
+    __u32 blocks_per_chunk = num_metadata_blocks / num_chunks;
+    __u32 curr_block = bg_start_block;
+    for (__u32 chunk = 0; chunk < num_chunks; chunk++) {
+      Extent extent;
+      if (chunk < num_chunks - 1) {
+        extent = ExtentForRange(curr_block, blocks_per_chunk);
+      } else {
+        extent = ExtentForRange(curr_block,
+                                bg_start_block + num_metadata_blocks -
+                                curr_block);
+      }
+
+      vector<Extent> extents;
+      extents.push_back(extent);
+
+      string metadata_name = StringPrintf("<rootfs-bg-%d-%d-metadata>",
+                                          bg, chunk);
+
+      LOG(INFO) << "Processing " << metadata_name;
+
+      TEST_AND_RETURN_FALSE(AddMetadataExtents(graph,
+                                               blocks,
+                                               fs_old,
+                                               fs_new,
+                                               metadata_name,
+                                               extents,
+                                               data_fd,
+                                               data_file_size));
+
+      curr_block += blocks_per_chunk;
+    }
+  }
+
+  return true;
+}
+
+// Processes all blocks belonging to an inode
+int ProcessInodeAllBlocks(ext2_filsys fs,
+                          blk_t* blocknr,
+                          e2_blkcnt_t blockcnt,
+                          blk_t ref_blk,
+                          int ref_offset,
+                          void* priv) {
+  vector<Extent>* extents = static_cast<vector<Extent>*>(priv);
+  graph_utils::AppendBlockToExtents(extents, *blocknr);
+  return 0;
+}
+
+// Processes only indirect, double indirect or triple indirect metadata
+// blocks belonging to an inode
+int ProcessInodeMetadataBlocks(ext2_filsys fs,
+                               blk_t* blocknr,
+                               e2_blkcnt_t blockcnt,
+                               blk_t ref_blk,
+                               int ref_offset,
+                               void* priv) {
+  vector<Extent>* extents = static_cast<vector<Extent>*>(priv);
+  if (blockcnt < 0) {
+    graph_utils::AppendBlockToExtents(extents, *blocknr);
+  }
+  return 0;
+}
+
+// Read inode metadata blocks.
+bool ReadInodeMetadata(Graph* graph,
+                       vector<Block>* blocks,
+                       const ext2_filsys fs_old,
+                       const ext2_filsys fs_new,
+                       int data_fd,
+                       off_t* data_file_size) {
+  TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_read_inode_bitmap(fs_old));
+

[petkov, 2010/12/15 18:40:32]

remove blank line

[thieule, 2010/12/15 19:57:01]

Done.

+  TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_read_inode_bitmap(fs_new));
+
+  ext2_inode_scan iscan;
+  TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open_inode_scan(fs_old, 0, &iscan));
+
+  ext2_ino_t ino;
+  ext2_inode old_inode;
+  while (true) {
+    // Get the next inode on both file systems
+    errcode_t error = ext2fs_get_next_inode(iscan, &ino, &old_inode);

[adlr, 2010/12/15 03:11:23]

is there a TEST_AND_RETURN_FALSE* thing you can use for this?

[thieule, 2010/12/15 19:57:01]

If we return false here, it will cause the delta_generator to exit with an
error.  By exiting here with a break which leads to a successful return code,
the delta_generator will treat the missing blocks as non-file data blocks and
compress them as an entire blob in ReadUnwrittenBlocks().  Since we have this
failsafe fallback, I don't think we need to error out here.  I've added comments
to reflect this.

On 2010/12/15 03:11:23, adlr wrote:

+    if (error) {
+      LOG(ERROR) << "Failed to retrieve next inode (" << error << ")";
+      break;
+    }
+
+    if (ino == 0) {
+      break;
+    }
+
+    if (ino == EXT2_RESIZE_INO) {
+      continue;
+    }
+
+    ext2_inode new_inode;
+    error = ext2fs_read_inode(fs_new, ino, &new_inode);
+    if (error) {
+      LOG(ERROR) << "Failed to retrieve new inode (" << error << ")";
+      continue;
+    }
+
+    // Skip inodes that are not in use
+    if (!ext2fs_test_inode_bitmap(fs_old->inode_map, ino)  ||
+        !ext2fs_test_inode_bitmap(fs_new->inode_map, ino)) {
+      continue;
+    }
+
+    // Skip inodes that have no data blocks
+    if (old_inode.i_blocks == 0 || new_inode.i_blocks == 0) {
+      continue;
+    }
+
+    // Skip inodes that are not the same type
+    bool is_old_dir = (ext2fs_check_directory(fs_old, ino) == 0);
+    bool is_new_dir = (ext2fs_check_directory(fs_new, ino) == 0);
+    if (is_old_dir != is_new_dir) {
+      continue;
+    }
+
+    // Process the inodes metadata blocks
+    // For normal files, metadata blocks are indirect, double indirect
+    // and triple indirect blocks (no data blocks). For directories and
+    // the journal, all blocks are considered metadata blocks.
+    LOG(INFO) << "Processing inode " << ino << " metadata";
+
+    bool all_blocks = ((ino == EXT2_JOURNAL_INO) || is_old_dir || is_new_dir);
+
+    vector<Extent> old_extents;
+    error = ext2fs_block_iterate2(fs_old, ino, 0, NULL,
+                                  all_blocks ? ProcessInodeAllBlocks :
+                                               ProcessInodeMetadataBlocks,
+                                  &old_extents);
+    if (error) {
+      LOG(ERROR) << "Failed to enumerate old inode " << ino
+                << " blocks (" << error << ")";
+      continue;
+    }
+
+    vector<Extent> new_extents;
+    error = ext2fs_block_iterate2(fs_new, ino, 0, NULL,
+                                  all_blocks ? ProcessInodeAllBlocks :
+                                               ProcessInodeMetadataBlocks,
+                                  &new_extents);
+    if (error) {
+      LOG(ERROR) << "Failed to enumerate new inode " << ino
+                << " blocks (" << error << ")";
+      continue;
+    }
+
+    // Skip inode if there are no metadata blocks
+    if (old_extents.size() == 0 || new_extents.size() == 0) {
+      continue;
+    }
+
+    // Make sure the two inodes have the same metadata blocks
+    if (old_extents.size() != new_extents.size()) {
+      continue;
+    }
+
+    bool same_metadata_extents = true;
+    vector<Extent>::iterator it_old;
+    vector<Extent>::iterator it_new;
+    for (it_old = old_extents.begin(),
+         it_new = new_extents.begin();
+         it_old != old_extents.end() && it_new != new_extents.end();
+         it_old++, it_new++) {
+      if (it_old->start_block() != it_new->start_block() ||
+          it_old->num_blocks() != it_new->num_blocks()) {
+            same_metadata_extents = false;
+            break;
+      }
+    }
+
+    if (!same_metadata_extents) {
+      continue;
+    }
+
+    // We have identical inode metadata blocks, we can now add them to
+    // our graph and blocks vector
+    string metadata_name = StringPrintf("<rootfs-inode-%d-metadata>", ino);
+    TEST_AND_RETURN_FALSE(AddMetadataExtents(graph,
+                                             blocks,
+                                             fs_old,
+                                             fs_new,
+                                             metadata_name,
+                                             old_extents,
+                                             data_fd,
+                                             data_file_size));
+  }
+
+  ext2fs_close_inode_scan(iscan);
+
+  return true;
+}
+
+// Reads metadata from old image and new image and determines
+// the smallest way to encode the metadata for the diff.
+// If there's no change in the metadata, it creates a MOVE
+// operation. If there is a change, the smallest of REPLACE, REPLACE_BZ,
+// or BSDIFF wins. It writes the diff to data_fd and updates data_file_size
+// accordingly. It also adds the required operation to the graph and adds the
+// metadata extents to blocks.
+// Returns true on success.
+bool DeltaReadMetadata(Graph* graph,
+                       vector<Block>* blocks,
+                       const string& old_image,
+                       const string& new_image,
+                       int data_fd,
+                       off_t* data_file_size) {
+  // Open the two file systems.
+  ext2_filsys fs_old;
+  TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open(old_image.c_str(), 0, 0, 0,
+                                            unix_io_manager, &fs_old));
+  ScopedExt2fsCloser fs_old_closer(fs_old);
+
+  ext2_filsys fs_new;
+  TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open(new_image.c_str(), 0, 0, 0,
+                                            unix_io_manager, &fs_new));
+  ScopedExt2fsCloser fs_new_closer(fs_new);
+
+  // Make sure these two file systems are the same.
+  // If they are not the same, the metadata blocks will be packaged up in its
+  // entirety by ReadUnwrittenBlocks().
+  if (fs_old->blocksize != fs_new->blocksize ||
+      fs_old->fragsize != fs_new->fragsize ||
+      fs_old->group_desc_count != fs_new->group_desc_count ||
+      fs_old->inode_blocks_per_group != fs_new->inode_blocks_per_group ||
+      fs_old->super->s_inodes_count != fs_new->super->s_inodes_count ||
+      fs_old->super->s_blocks_count != fs_new->super->s_blocks_count) {
+    return true;
+  }
+
+  // Process the main file system metadata (superblock, inode tables, etc)
+  TEST_AND_RETURN_FALSE(ReadFilesystemMetadata(graph,
+                                               blocks,
+                                               fs_old,
+                                               fs_new,
+                                               data_fd,
+                                               data_file_size));
+
+  // Process each inode metadata blocks.
+  TEST_AND_RETURN_FALSE(ReadInodeMetadata(graph,
+                                          blocks,
+                                          fs_old,
+                                          fs_new,
+                                          data_fd,
+                                          data_file_size));
+
+  return true;
+}
+
+};  // namespace chromeos_update_engine