diff --git a/SConstruct b/SConstruct
index c9d5068..6b0646a 100644
--- a/SConstruct
+++ b/SConstruct
@@ -197,6 +197,7 @@
                        bz2
                        crypto
                        curl
+                       ext2fs
                        gflags
                        glib-2.0
                        gthread-2.0
@@ -256,6 +257,7 @@
                    http_fetcher.cc
                    libcurl_http_fetcher.cc
                    marshal.glibmarshal.c
+                   metadata.cc
                    omaha_hash_calculator.cc
                    omaha_request_action.cc
                    omaha_request_params.cc
@@ -297,6 +299,7 @@
                             full_update_generator_unittest.cc
                             graph_utils_unittest.cc
                             http_fetcher_unittest.cc
+                            metadata_unittest.cc
                             mock_http_fetcher.cc
                             omaha_hash_calculator_unittest.cc
                             omaha_request_action_unittest.cc
@@ -358,4 +361,4 @@
 unittest_cmd = unittest_env.Program('update_engine_unittests',
                            unittest_sources + unittest_main)
 Clean(unittest_cmd, Glob('*.gcda') + Glob('*.gcno') + Glob('*.gcov') +
-                    Split('html app.info'))
+                    Split('html app.info'))
\ No newline at end of file
diff --git a/delta_diff_generator.cc b/delta_diff_generator.cc
index 21a4c03..4f71c49 100644
--- a/delta_diff_generator.cc
+++ b/delta_diff_generator.cc
@@ -30,6 +30,7 @@
 #include "update_engine/full_update_generator.h"
 #include "update_engine/graph_types.h"
 #include "update_engine/graph_utils.h"
+#include "update_engine/metadata.h"
 #include "update_engine/omaha_hash_calculator.h"
 #include "update_engine/payload_signer.h"
 #include "update_engine/subprocess.h"
@@ -77,81 +78,6 @@
   return true;
 }
 
-// Runs the bsdiff tool on two files and returns the resulting delta in
-// 'out'. Returns true on success.
-bool BsdiffFiles(const string& old_file,
-                 const string& new_file,
-                 vector<char>* out) {
-  const string kPatchFile = "/tmp/delta.patchXXXXXX";
-  string patch_file_path;
-
-  TEST_AND_RETURN_FALSE(
-      utils::MakeTempFile(kPatchFile, &patch_file_path, NULL));
-
-  vector<string> cmd;
-  cmd.push_back(kBsdiffPath);
-  cmd.push_back(old_file);
-  cmd.push_back(new_file);
-  cmd.push_back(patch_file_path);
-
-  int rc = 1;
-  vector<char> patch_file;
-  TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc));
-  TEST_AND_RETURN_FALSE(rc == 0);
-  TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
-  unlink(patch_file_path.c_str());
-  return true;
-}
-
-// The blocks vector contains a reader and writer for each block on the
-// filesystem that's being in-place updated. We populate the reader/writer
-// fields of blocks by calling this function.
-// For each block in 'operation' that is read or written, find that block
-// in 'blocks' and set the reader/writer field to the vertex passed.
-// 'graph' is not strictly necessary, but useful for printing out
-// error messages.
-bool AddInstallOpToBlocksVector(
-    const DeltaArchiveManifest_InstallOperation& operation,
-    vector<Block>* blocks,
-    const Graph& graph,
-    Vertex::Index vertex) {
-  // See if this is already present.
-  TEST_AND_RETURN_FALSE(operation.dst_extents_size() > 0);
-
-  enum BlockField { READER = 0, WRITER, BLOCK_FIELD_COUNT };
-  for (int field = READER; field < BLOCK_FIELD_COUNT; field++) {
-    const int extents_size =
-        (field == READER) ? operation.src_extents_size() :
-        operation.dst_extents_size();
-    const char* past_participle = (field == READER) ? "read" : "written";
-    const google::protobuf::RepeatedPtrField<Extent>& extents =
-        (field == READER) ? operation.src_extents() : operation.dst_extents();
-    Vertex::Index Block::*access_type =
-        (field == READER) ? &Block::reader : &Block::writer;
-
-    for (int i = 0; i < extents_size; i++) {
-      const Extent& extent = extents.Get(i);
-      if (extent.start_block() == kSparseHole) {
-        // Hole in sparse file. skip
-        continue;
-      }
-      for (uint64_t block = extent.start_block();
-           block < (extent.start_block() + extent.num_blocks()); block++) {
-        if ((*blocks)[block].*access_type != Vertex::kInvalidIndex) {
-          LOG(FATAL) << "Block " << block << " is already "
-                     << past_participle << " by "
-                     << (*blocks)[block].*access_type << "("
-                     << graph[(*blocks)[block].*access_type].file_name
-                     << ") and also " << vertex << "("
-                     << graph[vertex].file_name << ")";
-        }
-        (*blocks)[block].*access_type = vertex;
-      }
-    }
-  }
-  return true;
-}
-
 // For a given regular file which must exist at new_root + path, and
 // may exist at old_root + path, creates a new InstallOperation and
 // adds it to the graph. Also, populates the |blocks| array as
@@ -197,10 +123,11 @@
   (*graph)[vertex].file_name = path;
 
   if (blocks)
-    TEST_AND_RETURN_FALSE(AddInstallOpToBlocksVector((*graph)[vertex].op,
-                                                     blocks,
-                                                     *graph,
-                                                     vertex));
+    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::AddInstallOpToBlocksVector(
+        (*graph)[vertex].op,
+        *graph,
+        vertex,
+        blocks));
   return true;
 }
 
@@ -1390,6 +1317,16 @@
       LOG(INFO) << "done reading normal files";
       CheckGraph(graph);
 
+      LOG(INFO) << "Starting metadata processing";
+      TEST_AND_RETURN_FALSE(Metadata::DeltaReadMetadata(&graph,
+                                                        &blocks,
+                                                        old_image,
+                                                        new_image,
+                                                        fd,
+                                                        &data_file_size));
+      LOG(INFO) << "Done metadata processing";
+      CheckGraph(graph);
+
       graph.resize(graph.size() + 1);
       TEST_AND_RETURN_FALSE(ReadUnwrittenBlocks(blocks,
                                                 fd,
@@ -1585,6 +1522,81 @@
   return true;
 }
 
+// Runs the bsdiff tool on two files and returns the resulting delta in
+// 'out'. Returns true on success.
+bool DeltaDiffGenerator::BsdiffFiles(const string& old_file,
+                                     const string& new_file,
+                                     vector<char>* out) {
+  const string kPatchFile = "/tmp/delta.patchXXXXXX";
+  string patch_file_path;
+
+  TEST_AND_RETURN_FALSE(
+      utils::MakeTempFile(kPatchFile, &patch_file_path, NULL));
+
+  vector<string> cmd;
+  cmd.push_back(kBsdiffPath);
+  cmd.push_back(old_file);
+  cmd.push_back(new_file);
+  cmd.push_back(patch_file_path);
+
+  int rc = 1;
+  vector<char> patch_file;
+  TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc));
+  TEST_AND_RETURN_FALSE(rc == 0);
+  TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
+  unlink(patch_file_path.c_str());
+  return true;
+}
+
+// The |blocks| vector contains a reader and writer for each block on the
+// filesystem that's being in-place updated. We populate the reader/writer
+// fields of |blocks| by calling this function.
+// For each block in |operation| that is read or written, find that block
+// in |blocks| and set the reader/writer field to the vertex passed.
+// |graph| is not strictly necessary, but useful for printing out
+// error messages.
+bool DeltaDiffGenerator::AddInstallOpToBlocksVector(
+    const DeltaArchiveManifest_InstallOperation& operation,
+    const Graph& graph,
+    Vertex::Index vertex,
+    vector<Block>* blocks) {
+  // See if this is already present.
+  TEST_AND_RETURN_FALSE(operation.dst_extents_size() > 0);
+
+  enum BlockField { READER = 0, WRITER, BLOCK_FIELD_COUNT };
+  for (int field = READER; field < BLOCK_FIELD_COUNT; field++) {
+    const int extents_size =
+        (field == READER) ? operation.src_extents_size() :
+        operation.dst_extents_size();
+    const char* past_participle = (field == READER) ? "read" : "written";
+    const google::protobuf::RepeatedPtrField<Extent>& extents =
+        (field == READER) ? operation.src_extents() : operation.dst_extents();
+    Vertex::Index Block::*access_type =
+        (field == READER) ? &Block::reader : &Block::writer;
+
+    for (int i = 0; i < extents_size; i++) {
+      const Extent& extent = extents.Get(i);
+      if (extent.start_block() == kSparseHole) {
+        // Hole in sparse file. skip
+        continue;
+      }
+      for (uint64_t block = extent.start_block();
+           block < (extent.start_block() + extent.num_blocks()); block++) {
+        if ((*blocks)[block].*access_type != Vertex::kInvalidIndex) {
+          LOG(FATAL) << "Block " << block << " is already "
+                     << past_participle << " by "
+                     << (*blocks)[block].*access_type << "("
+                     << graph[(*blocks)[block].*access_type].file_name
+                     << ") and also " << vertex << "("
+                     << graph[vertex].file_name << ")";
+        }
+        (*blocks)[block].*access_type = vertex;
+      }
+    }
+  }
+  return true;
+}
+
 const char* const kBsdiffPath = "bsdiff";
 const char* const kBspatchPath = "bspatch";
 const char* const kDeltaMagic = "CrAU";
diff --git a/delta_diff_generator.h b/delta_diff_generator.h
index 50a3a89..d02de48 100644
--- a/delta_diff_generator.h
+++ b/delta_diff_generator.h
@@ -213,6 +213,25 @@
                                       const std::string& partition,
                                       PartitionInfo* info);
 
+  // Runs the bsdiff tool on two files and returns the resulting delta in
+  // |out|. Returns true on success.
+  static bool BsdiffFiles(const std::string& old_file,
+                          const std::string& new_file,
+                          std::vector<char>* out);
+
+  // The |blocks| vector contains a reader and writer for each block on the
+  // filesystem that's being in-place updated. We populate the reader/writer
+  // fields of |blocks| by calling this function.
+  // For each block in |operation| that is read or written, find that block
+  // in |blocks| and set the reader/writer field to the vertex passed.
+  // |graph| is not strictly necessary, but useful for printing out
+  // error messages.
+  static bool AddInstallOpToBlocksVector(
+      const DeltaArchiveManifest_InstallOperation& operation,
+      const Graph& graph,
+      Vertex::Index vertex,
+      std::vector<DeltaDiffGenerator::Block>* blocks);
+
  private:
   // This should never be constructed
   DISALLOW_IMPLICIT_CONSTRUCTORS(DeltaDiffGenerator);
diff --git a/delta_diff_generator_unittest.cc b/delta_diff_generator_unittest.cc
index 2a70399..bd0b48e 100644
--- a/delta_diff_generator_unittest.cc
+++ b/delta_diff_generator_unittest.cc
@@ -6,13 +6,17 @@
 #include <sys/stat.h>
 #include <fcntl.h>
 #include <unistd.h>
+
 #include <set>
 #include <sstream>
 #include <string>
 #include <utility>
 #include <vector>
+
+#include <base/logging.h>
+#include <base/string_util.h>
 #include <gtest/gtest.h>
-#include "base/logging.h"
+
 #include "update_engine/cycle_breaker.h"
 #include "update_engine/delta_diff_generator.h"
 #include "update_engine/delta_performer.h"
@@ -713,7 +717,7 @@
                                   &fd));
   ScopedFdCloser fd_closer(&fd);
   off_t data_file_size = 0;
-  
+
   EXPECT_TRUE(DeltaDiffGenerator::AssignTempBlocks(&graph,
                                                    temp_dir,
                                                    fd,
diff --git a/delta_performer_unittest.cc b/delta_performer_unittest.cc
index 238731a..51299fb 100755
--- a/delta_performer_unittest.cc
+++ b/delta_performer_unittest.cc
@@ -66,27 +66,6 @@
   EXPECT_EQ(expected_output, actual_output);
 }
 
-class ScopedLoopMounter {
- public:
-  explicit ScopedLoopMounter(const string& file_path, string* mnt_path,
-                             unsigned long flags) {
-    EXPECT_TRUE(utils::MakeTempDirectory("/tmp/mnt.XXXXXX", mnt_path));
-    dir_remover_.reset(new ScopedDirRemover(*mnt_path));
-
-    string loop_dev = GetUnusedLoopDevice();
-    EXPECT_EQ(0, system(StringPrintf("losetup %s %s", loop_dev.c_str(),
-                                     file_path.c_str()).c_str()));
-    loop_releaser_.reset(new ScopedLoopbackDeviceReleaser(loop_dev));
-
-    EXPECT_TRUE(utils::MountFilesystem(loop_dev, *mnt_path, flags));
-    unmounter_.reset(new ScopedFilesystemUnmounter(*mnt_path));
-  }
- private:
-  scoped_ptr<ScopedDirRemover> dir_remover_;
-  scoped_ptr<ScopedLoopbackDeviceReleaser> loop_releaser_;
-  scoped_ptr<ScopedFilesystemUnmounter> unmounter_;
-};
-
 void CompareFilesByBlock(const string& a_file, const string& b_file) {
   vector<char> a_data, b_data;
   EXPECT_TRUE(utils::ReadFile(a_file, &a_data)) << "file failed: " << a_file;
diff --git a/metadata.cc b/metadata.cc
new file mode 100644
index 0000000..20c0a0d
--- /dev/null
+++ b/metadata.cc
@@ -0,0 +1,482 @@
+// 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;
+
+typedef DeltaDiffGenerator::Block Block;
+
+// Read data from the specified extents.
+bool ReadExtentsData(const ext2_filsys fs,
+                     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
+  const size_t kMaxReadBlocks = 256;
+  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(kMaxReadBlocks,
+              static_cast<size_t>(
+                  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(
+      DeltaDiffGenerator::BsdiffFiles(temp_old_file_path,
+                                      temp_new_file_path,
+                                      bsdiff_delta));
+
+  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.
+  DeltaArchiveManifest_InstallOperation op;
+
+  {
+    // Read in the metadata blocks from the old and new image.
+    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());
+
+    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;
+      }
+    }
+
+    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(DeltaDiffGenerator::AddInstallOpToBlocksVector(
+      (*graph)[vertex].op,
+      *graph,
+      vertex,
+      blocks));
+
+  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));
+  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);
+
+    // If we get an error enumerating the inodes, we'll just log the error
+    // and exit from our loop which will eventually return a success code
+    // back to the caller. The inode blocks that we cannot account for will
+    // be handled by DeltaDiffGenerator::ReadUnwrittenBlocks().
+    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;
+}
+
+}  // namespace {}
+
+// 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 Metadata::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
diff --git a/metadata.h b/metadata.h
new file mode 100644
index 0000000..72eb145
--- /dev/null
+++ b/metadata.h
@@ -0,0 +1,37 @@
+// 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.
+
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_METADATA_H__
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_METADATA_H__
+
+#include "update_engine/delta_diff_generator.h"
+#include "update_engine/graph_types.h"
+
+namespace chromeos_update_engine {
+
+class Metadata {
+ public:
+  // 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.
+  static bool DeltaReadMetadata(Graph* graph,
+                                std::vector<DeltaDiffGenerator::Block>* blocks,
+                                const std::string& old_image,
+                                const std::string& new_image,
+                                int data_fd,
+                                off_t* data_file_size);
+
+ private:
+  // This should never be constructed.
+  DISALLOW_IMPLICIT_CONSTRUCTORS(Metadata);
+};
+
+};  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_METADATA_H__
diff --git a/metadata_unittest.cc b/metadata_unittest.cc
new file mode 100644
index 0000000..fde0b98
--- /dev/null
+++ b/metadata_unittest.cc
@@ -0,0 +1,157 @@
+// 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 <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+
+#include <string>
+#include <vector>
+
+#include <base/string_util.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/graph_types.h"
+#include "update_engine/delta_diff_generator.h"
+#include "update_engine/metadata.h"
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+typedef DeltaDiffGenerator::Block Block;
+
+class MetadataTest : public ::testing::Test {
+};
+
+TEST_F(MetadataTest, RunAsRootReadMetadataDissimilarFileSystems) {
+  string a_img, b_img;
+  EXPECT_TRUE(utils::MakeTempFile("/tmp/a_img.XXXXXX", &a_img, NULL));
+  ScopedPathUnlinker a_img_unlinker(a_img);
+  EXPECT_TRUE(utils::MakeTempFile("/tmp/b_img.XXXXXX", &b_img, NULL));
+  ScopedPathUnlinker b_img_unlinker(b_img);
+
+  CreateEmptyExtImageAtPath(a_img, 10485759, 4096);
+  CreateEmptyExtImageAtPath(b_img, 11534336, 4096);
+
+  Graph graph;
+  vector<Block> blocks;
+  EXPECT_TRUE(Metadata::DeltaReadMetadata(&graph,
+                                          &blocks,
+                                          a_img,
+                                          b_img,
+                                          0,
+                                          NULL));
+  EXPECT_EQ(graph.size(), 0);
+
+  CreateEmptyExtImageAtPath(a_img, 10485759, 4096);
+  CreateEmptyExtImageAtPath(b_img, 10485759, 8192);
+
+  graph.clear();
+  blocks.clear();
+  EXPECT_TRUE(Metadata::DeltaReadMetadata(&graph,
+                                          &blocks,
+                                          a_img,
+                                          b_img,
+                                          0,
+                                          NULL));
+  EXPECT_EQ(graph.size(), 0);
+}
+
+TEST_F(MetadataTest, RunAsRootReadMetadata) {
+  string a_img, b_img, data_file;
+  EXPECT_TRUE(utils::MakeTempFile("/tmp/a_img.XXXXXX", &a_img, NULL));
+  ScopedPathUnlinker a_img_unlinker(a_img);
+  EXPECT_TRUE(utils::MakeTempFile("/tmp/b_img.XXXXXX", &b_img, NULL));
+  ScopedPathUnlinker b_img_unlinker(b_img);
+  EXPECT_TRUE(utils::MakeTempFile("/tmp/data_file.XXXXXX", &data_file, NULL));
+  ScopedPathUnlinker data_file_unlinker(data_file);
+
+  const size_t image_size = (256 * 1024 * 1024);  // Enough for 2 block groups
+  const int block_size = 4096;
+  CreateEmptyExtImageAtPath(a_img, image_size, block_size);
+
+  // Create a file large enough to create an indirect block
+  {
+    string a_img_mnt;
+    ScopedLoopMounter a_img_mount(a_img, &a_img_mnt, 0);
+    System(StringPrintf("dd if=/dev/zero of=%s/test_file bs=%d count=%d",
+                        a_img_mnt.c_str(), block_size, EXT2_NDIR_BLOCKS + 1));
+  }
+
+  System(StringPrintf("cp %s %s", a_img.c_str(), b_img.c_str()));
+
+  int fd = open(data_file.c_str(), O_RDWR | O_CREAT, S_IRWXU);
+  EXPECT_NE(fd, -1);
+  ScopedFdCloser fd_closer(&fd);
+
+  Graph graph;
+  vector<Block> blocks(image_size / block_size);
+  off_t data_file_size;
+  EXPECT_TRUE(Metadata::DeltaReadMetadata(&graph,
+                                          &blocks,
+                                          a_img,
+                                          b_img,
+                                          fd,
+                                          &data_file_size));
+
+  // There are 12 metadata that we look for:
+  //   - Block group 0 metadata (superblock, group descriptor, bitmaps, etc)
+  //       - Chunk 0, 1, 2, 3
+  //   - Block group 1 metadata
+  //       - Chunk 0, 1, 2, 3
+  //   - Root directory (inode 2)
+  //   - Journal (inode 8)
+  //   - lost+found directory (inode 11)
+  //   - test_file indirect block (inode 12)
+  struct {
+    string metadata_name;
+    off_t start_block; // Set to -1 to skip start block verification
+    off_t num_blocks; // Set to -1 to skip num blocks verification
+  } exp_results[] =
+      {{"<rootfs-bg-0-0-metadata>", 0, 260},
+       {"<rootfs-bg-0-1-metadata>", 260, 260},
+       {"<rootfs-bg-0-2-metadata>", 520, 260},
+       {"<rootfs-bg-0-3-metadata>", 780, 263},
+       {"<rootfs-bg-1-0-metadata>", 32768, 260},
+       {"<rootfs-bg-1-1-metadata>", 33028, 260},
+       {"<rootfs-bg-1-2-metadata>", 33288, 260},
+       {"<rootfs-bg-1-3-metadata>", 33548, 263},
+       {"<rootfs-inode-2-metadata>", -1, 1},
+       {"<rootfs-inode-8-metadata>", -1, 4101},
+       {"<rootfs-inode-11-metadata>", -1, 4},
+       {"<rootfs-inode-12-metadata>", -1, 1}};
+
+  int num_exp_results = sizeof(exp_results) / sizeof(exp_results[0]);
+  EXPECT_EQ(graph.size(), num_exp_results);
+
+  for (int i = 0; i < num_exp_results; i++) {
+    Vertex& vertex = graph[i];
+    DeltaArchiveManifest_InstallOperation& op = vertex.op;
+
+    EXPECT_STRCASEEQ(vertex.file_name.c_str(),
+                     exp_results[i].metadata_name.c_str());
+
+    EXPECT_EQ(op.src_extents().size(), op.dst_extents().size());
+    for (int e = 0; e < op.src_extents().size(); e++) {
+      EXPECT_EQ(op.src_extents(e).start_block(),
+                op.dst_extents(e).start_block());
+      EXPECT_EQ(op.src_extents(e).num_blocks(),
+                op.dst_extents(e).num_blocks());
+    }
+
+    if (exp_results[i].start_block != -1) {
+      EXPECT_EQ(op.src_extents(0).start_block(), exp_results[i].start_block);
+    }
+
+    if (exp_results[i].num_blocks != -1) {
+      EXPECT_EQ(op.src_extents(0).num_blocks(), exp_results[i].num_blocks);
+    }
+  }
+}
+
+}  // namespace chromeos_update_engine
diff --git a/test_utils.cc b/test_utils.cc
index c1bdb48..9d1b5d0 100644
--- a/test_utils.cc
+++ b/test_utils.cc
@@ -178,6 +178,16 @@
   }
 }
 
+void CreateEmptyExtImageAtPath(const string& path,
+                               size_t size,
+                               int block_size) {
+  EXPECT_EQ(0, System(StringPrintf("dd if=/dev/zero of=%s"
+                                   " seek=%zu bs=1 count=1",
+                                   path.c_str(), size)));
+  EXPECT_EQ(0, System(StringPrintf("mkfs.ext3 -b %d -F %s",
+                                   block_size, path.c_str())));
+}
+
 void CreateExtImageAtPath(const string& path, vector<string>* out_paths) {
   // create 10MiB sparse file
   EXPECT_EQ(0, System(StringPrintf("dd if=/dev/zero of=%s"
@@ -199,7 +209,7 @@
   EXPECT_EQ(0, System(StringPrintf("ln %s/some_dir/test %s/testlink",
                                    kMountPath, kMountPath)));
   EXPECT_EQ(0, System(StringPrintf("umount -d %s", kMountPath)));
-  
+
   if (out_paths) {
     out_paths->clear();
     out_paths->push_back("");
@@ -263,4 +273,19 @@
   }
 }
 
+ScopedLoopMounter::ScopedLoopMounter(const std::string& file_path,
+                                     std::string* mnt_path,
+                                     unsigned long flags) {
+  EXPECT_TRUE(utils::MakeTempDirectory("/tmp/mnt.XXXXXX", mnt_path));
+  dir_remover_.reset(new ScopedDirRemover(*mnt_path));
+
+  std::string loop_dev = GetUnusedLoopDevice();
+  EXPECT_EQ(0, system(StringPrintf("losetup %s %s", loop_dev.c_str(),
+                                   file_path.c_str()).c_str()));
+  loop_releaser_.reset(new ScopedLoopbackDeviceReleaser(loop_dev));
+
+  EXPECT_TRUE(utils::MountFilesystem(loop_dev, *mnt_path, flags));
+  unmounter_.reset(new ScopedFilesystemUnmounter(*mnt_path));
+}
+
 }  // namespace chromeos_update_engine
diff --git a/test_utils.h b/test_utils.h
index 4c82888..68de48d 100644
--- a/test_utils.h
+++ b/test_utils.h
@@ -8,8 +8,10 @@
 #include <set>
 #include <string>
 #include <vector>
+
+#include <base/scoped_ptr.h>
 #include <gtest/gtest.h>
-#include "base/scoped_ptr.h"
+
 #include "update_engine/action.h"
 #include "update_engine/subprocess.h"
 #include "update_engine/utils.h"
@@ -92,6 +94,11 @@
 const char* const kMountPath = "/tmp/UpdateEngineTests_mnt";
 }  // namespace {}
 
+// Creates an empty ext image.
+void CreateEmptyExtImageAtPath(const std::string& path,
+                               size_t size,
+                               int block_size);
+
 // Creates an ext image with some files in it. The paths creates are
 // returned in out_paths.
 void CreateExtImageAtPath(const std::string& path,
@@ -211,6 +218,22 @@
   T object_;
 };
 
+class ScopedLoopMounter {
+ public:
+  explicit ScopedLoopMounter(const std::string& file_path,
+                             std::string* mnt_path,
+                             unsigned long flags);
+
+ private:
+  // These objects must be destructed in the following order:
+  //   ScopedFilesystemUnmounter (the file system must be unmounted first)
+  //   ScopedLoopbackDeviceReleaser (then the loop device can be deleted)
+  //   ScopedDirRemover (then the mount point can be deleted)
+  scoped_ptr<ScopedDirRemover> dir_remover_;
+  scoped_ptr<ScopedLoopbackDeviceReleaser> loop_releaser_;
+  scoped_ptr<ScopedFilesystemUnmounter> unmounter_;
+};
+
 }  // namespace chromeos_update_engine
 
 #endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_TEST_UTILS_H__
diff --git a/utils.h b/utils.h
index 34b862e..4979636 100644
--- a/utils.h
+++ b/utils.h
@@ -12,6 +12,7 @@
 #include <string>
 #include <vector>
 
+#include <ext2fs/ext2fs.h>
 #include <glib.h>
 
 #include "update_engine/action.h"
@@ -271,6 +272,17 @@
   DISALLOW_COPY_AND_ASSIGN(ScopedFdCloser);
 };
 
+// Utility class to close a file system
+class ScopedExt2fsCloser {
+ public:
+  explicit ScopedExt2fsCloser(ext2_filsys filsys) : filsys_(filsys) {}
+  ~ScopedExt2fsCloser() { ext2fs_close(filsys_); }
+
+ private:
+  ext2_filsys filsys_;
+  DISALLOW_COPY_AND_ASSIGN(ScopedExt2fsCloser);
+};
+
 // Utility class to delete a file when it goes out of scope.
 class ScopedPathUnlinker {
  public:
@@ -389,6 +401,16 @@
     }                                                                          \
   } while (0)
 
+#define TEST_AND_RETURN_FALSE_ERRCODE(_x)                                      \
+  do {                                                                         \
+    errcode_t _error = (_x);                                                   \
+    if (_error) {                                                              \
+      errno = _error;                                                          \
+      LOG(ERROR) << #_x " failed: " << _error;                                 \
+      return false;                                                            \
+    }                                                                          \
+  } while (0)
+
 
 
 #endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_UTILS_H__