diff --git a/delta_performer.cc b/delta_performer.cc
index e6441fe..0544e12 100644
--- a/delta_performer.cc
+++ b/delta_performer.cc
@@ -486,7 +486,6 @@
   return kMetadataParseSuccess;
 }
 
-
 // Wrapper around write. Returns true if all requested bytes
 // were written, or false on any error, regardless of progress
 // and stores an action exit code in |error|.
@@ -734,16 +733,12 @@
     ssize_t bytes_read_this_iteration = 0;
     const Extent& extent = operation.src_extents(i);
     const size_t bytes = extent.num_blocks() * block_size_;
-    if (extent.start_block() == kSparseHole) {
-      bytes_read_this_iteration = bytes;
-      memset(&buf[bytes_read], 0, bytes);
-    } else {
-      TEST_AND_RETURN_FALSE(utils::PReadAll(fd,
-                                            &buf[bytes_read],
-                                            bytes,
-                                            extent.start_block() * block_size_,
-                                            &bytes_read_this_iteration));
-    }
+    TEST_AND_RETURN_FALSE(extent.start_block() != kSparseHole);
+    TEST_AND_RETURN_FALSE(utils::PReadAll(fd,
+                                          &buf[bytes_read],
+                                          bytes,
+                                          extent.start_block() * block_size_,
+                                          &bytes_read_this_iteration));
     TEST_AND_RETURN_FALSE(
         bytes_read_this_iteration == static_cast<ssize_t>(bytes));
     bytes_read += bytes_read_this_iteration;
@@ -762,18 +757,11 @@
   for (int i = 0; i < operation.dst_extents_size(); i++) {
     const Extent& extent = operation.dst_extents(i);
     const size_t bytes = extent.num_blocks() * block_size_;
-    if (extent.start_block() == kSparseHole) {
-      DCHECK(buf.begin() + bytes_written ==
-             std::search_n(buf.begin() + bytes_written,
-                           buf.begin() + bytes_written + bytes,
-                           bytes, 0));
-    } else {
-      TEST_AND_RETURN_FALSE(
-          utils::PWriteAll(fd,
-                           &buf[bytes_written],
-                           bytes,
-                           extent.start_block() * block_size_));
-    }
+    TEST_AND_RETURN_FALSE(extent.start_block() != kSparseHole);
+    TEST_AND_RETURN_FALSE(utils::PWriteAll(fd,
+                                           &buf[bytes_written],
+                                           bytes,
+                                           extent.start_block() * block_size_));
     bytes_written += bytes;
   }
   DCHECK_EQ(bytes_written, bytes_read);
@@ -790,13 +778,9 @@
   uint64_t length = 0;
   for (int i = 0; i < extents.size(); i++) {
     Extent extent = extents.Get(i);
-    int64_t start = extent.start_block();
+    int64_t start = extent.start_block() * block_size;
     uint64_t this_length = min(full_length - length,
                                extent.num_blocks() * block_size);
-    if (start == static_cast<int64_t>(kSparseHole))
-      start = -1;
-    else
-      start *= block_size;
     ret += base::StringPrintf("%" PRIi64 ":%" PRIu64 ",", start, this_length);
     length += this_length;
   }
diff --git a/delta_performer_unittest.cc b/delta_performer_unittest.cc
index e0bd95d..2b0bc45 100644
--- a/delta_performer_unittest.cc
+++ b/delta_performer_unittest.cc
@@ -1029,10 +1029,10 @@
 }
 
 TEST(DeltaPerformerTest, ExtentsToByteStringTest) {
-  uint64_t test[] = {1, 1, 4, 2, kSparseHole, 1, 0, 1};
+  uint64_t test[] = {1, 1, 4, 2, 0, 1};
   COMPILE_ASSERT(arraysize(test) % 2 == 0, array_size_uneven);
   const uint64_t block_size = 4096;
-  const uint64_t file_length = 5 * block_size - 13;
+  const uint64_t file_length = 4 * block_size - 13;
 
   google::protobuf::RepeatedPtrField<Extent> extents;
   for (size_t i = 0; i < arraysize(test); i += 2) {
@@ -1041,7 +1041,7 @@
     extent->set_num_blocks(test[i + 1]);
   }
 
-  string expected_output = "4096:4096,16384:8192,-1:4096,0:4083";
+  string expected_output = "4096:4096,16384:8192,0:4083";
   string actual_output;
   EXPECT_TRUE(DeltaPerformer::ExtentsToBsdiffPositionsString(extents,
                                                              block_size,
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 725442a..fca6064 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -93,6 +93,10 @@
 
 namespace {
 
+bool IsSparseHole(const Extent &extent) {
+  return (extent.start_block() == kSparseHole);
+}
+
 // Stores all the extents of |path| into |extents|. Returns true on success.
 bool GatherExtents(const string& path,
                    off_t chunk_offset,
@@ -100,8 +104,7 @@
                    vector<Extent>* extents) {
   extents->clear();
   TEST_AND_RETURN_FALSE(
-      get_extents_with_chunk_func(
-          path, chunk_offset, chunk_size, extents));
+      get_extents_with_chunk_func(path, chunk_offset, chunk_size, extents));
   return true;
 }
 
@@ -299,6 +302,8 @@
 
 bool DeltaDiffGenerator::DeltaReadFiles(Graph* graph,
                                         vector<Block>* blocks,
+                                        const string& old_part,
+                                        const string& new_part,
                                         const string& old_root,
                                         const string& new_root,
                                         off_t chunk_size,
@@ -353,6 +358,8 @@
           graph,
           Vertex::kInvalidIndex,
           blocks,
+          old_part,
+          new_part,
           (should_diff_from_source ? old_root : kEmptyPath),
           new_root,
           fs_iter.GetPartialPath(),
@@ -369,6 +376,8 @@
 bool DeltaDiffGenerator::DeltaReadFile(Graph* graph,
                                        Vertex::Index existing_vertex,
                                        vector<Block>* blocks,
+                                       const string& old_part,
+                                       const string& new_part,
                                        const string& old_root,
                                        const string& new_root,
                                        const string& path,  // within new_root
@@ -380,9 +389,6 @@
   chromeos::Blob data;
   DeltaArchiveManifest_InstallOperation operation;
 
-  string old_path = (old_root == kEmptyPath) ? kEmptyPath :
-      old_root + path;
-
   // If bsdiff breaks again, blacklist the problem file by using:
   //   bsdiff_allowed = (path != "/foo/bar")
   //
@@ -395,15 +401,19 @@
   if (!bsdiff_allowed)
     LOG(INFO) << "bsdiff blacklisting: " << path;
 
-  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ReadFileToDiff(old_path,
-                                                           new_root + path,
+  string old_filename = (old_root == kEmptyPath) ? kEmptyPath : old_root + path;
+
+  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ReadFileToDiff(old_part,
+                                                           new_part,
                                                            chunk_offset,
                                                            chunk_size,
                                                            bsdiff_allowed,
                                                            &data,
                                                            &operation,
                                                            true,
-                                                           src_ops_allowed));
+                                                           src_ops_allowed,
+                                                           old_filename,
+                                                           new_root + path));
 
   // Check if the operation writes nothing.
   if (operation.dst_extents_size() == 0) {
@@ -450,41 +460,17 @@
 }
 
 bool DeltaDiffGenerator::ReadFileToDiff(
-    const string& old_filename,
-    const string& new_filename,
+    const string& old_part,
+    const string& new_part,
     off_t chunk_offset,
     off_t chunk_size,
     bool bsdiff_allowed,
     chromeos::Blob* out_data,
     DeltaArchiveManifest_InstallOperation* out_op,
     bool gather_extents,
-    bool src_ops_allowed) {
-  // Read new data in
-  chromeos::Blob new_data;
-  TEST_AND_RETURN_FALSE(
-      utils::ReadFileChunk(new_filename, chunk_offset, chunk_size, &new_data));
-
-  TEST_AND_RETURN_FALSE(!new_data.empty());
-  TEST_AND_RETURN_FALSE(chunk_size == -1 ||
-                        static_cast<off_t>(new_data.size()) <= chunk_size);
-
-  chromeos::Blob new_data_bz;
-  TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
-  CHECK(!new_data_bz.empty());
-
-  chromeos::Blob data;  // Data blob that will be written to delta file.
-
-  DeltaArchiveManifest_InstallOperation operation;
-  size_t current_best_size = 0;
-  if (new_data.size() <= new_data_bz.size()) {
-    operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-    current_best_size = new_data.size();
-    data = new_data;
-  } else {
-    operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-    current_best_size = new_data_bz.size();
-    data = new_data_bz;
-  }
+    bool src_ops_allowed,
+    const string& old_filename,
+    const string& new_filename) {
 
   // Do we have an original file to consider?
   off_t old_size = 0;
@@ -495,12 +481,92 @@
     original = false;
   }
 
+  DeltaArchiveManifest_InstallOperation operation;
+  vector<Extent> src_extents, dst_extents;
+  // Gather source extents if we have an original file.
+  if (original) {
+    if (gather_extents) {
+      TEST_AND_RETURN_FALSE(
+          GatherExtents(old_filename, chunk_offset, chunk_size, &src_extents));
+      ClearSparseHoles(&src_extents);
+      if (src_extents.size() == 0) {
+        // Reading from sparse hole, do nothing.
+        operation.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+        *out_op = operation;
+        return true;
+      }
+    } else {
+      // We have a kernel, so make one extent to cover it all.
+      Extent* src_extent = operation.add_src_extents();
+      src_extent->set_start_block(0);
+      src_extent->set_num_blocks(
+          (utils::FileSize(old_filename) + (kBlockSize - 1)) / kBlockSize);
+      src_extents.push_back(*src_extent);
+    }
+  }
+
+  // Gather destination extents.
+  if (gather_extents) {
+    TEST_AND_RETURN_FALSE(
+        GatherExtents(new_filename, chunk_offset, chunk_size, &dst_extents));
+    ClearSparseHoles(&dst_extents);
+    if (dst_extents.size() == 0) {
+      // Make an empty move operation.
+      operation.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+      *out_op = operation;
+      return true;
+    }
+  } else {
+    Extent* dst_extent = operation.add_dst_extents();
+    dst_extent->set_start_block(0);
+    dst_extent->set_num_blocks(
+        (utils::FileSize(new_filename) + (kBlockSize - 1)) / kBlockSize);
+    dst_extents.push_back(*dst_extent);
+  }
+
+  // Figure out how many blocks we need to write to dst_extents.
+  uint64_t blocks_to_write = 0;
+  for (uint32_t i = 0; i < dst_extents.size(); i++)
+    blocks_to_write += dst_extents[i].num_blocks();
+
+  // Figure out how many blocks we need to read to src_extents.
+  uint64_t blocks_to_read = 0;
+  for (uint32_t i = 0; i < src_extents.size(); i++)
+    blocks_to_read += src_extents[i].num_blocks();
+
+  // Read in bytes from new data.
+  chromeos::Blob new_data;
+  TEST_AND_RETURN_FALSE(utils::ReadExtents(new_part,
+                                           &dst_extents,
+                                           &new_data,
+                                           kBlockSize * blocks_to_write,
+                                           kBlockSize));
+
+  TEST_AND_RETURN_FALSE(!new_data.empty());
+  TEST_AND_RETURN_FALSE(chunk_size == -1 ||
+                        static_cast<off_t>(new_data.size()) <= chunk_size);
+
+  chromeos::Blob new_data_bz;
+  TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
+  CHECK(!new_data_bz.empty());
+  chromeos::Blob data;  // Data blob that will be written to delta file.
+
+  size_t current_best_size = 0;
+  if (new_data.size() <= new_data_bz.size()) {
+    operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+    current_best_size = new_data.size();
+    data = new_data;
+  } else {
+    operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+    current_best_size = new_data_bz.size();
+    data = new_data_bz;
+  }
   chromeos::Blob old_data;
   if (original) {
-    // Read old data
+    // Read old data.
     TEST_AND_RETURN_FALSE(
-        utils::ReadFileChunk(
-            old_filename, chunk_offset, chunk_size, &old_data));
+        utils::ReadExtents(old_part, &src_extents, &old_data,
+                           kBlockSize * blocks_to_read, kBlockSize));
     if (old_data == new_data) {
       // No change in data.
       if (src_ops_allowed) {
@@ -544,43 +610,12 @@
     }
   }
 
+  operation.set_src_length(old_data.size());
+  operation.set_dst_length(new_data.size());
+
   // Set parameters of the operations
   CHECK_EQ(data.size(), current_best_size);
 
-  vector<Extent> src_extents, dst_extents;
-  if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE ||
-      operation.type() == DeltaArchiveManifest_InstallOperation_Type_BSDIFF ||
-      operation.type() ==
-          DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY ||
-      operation.type() ==
-          DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF) {
-    if (gather_extents) {
-      TEST_AND_RETURN_FALSE(
-          GatherExtents(old_filename,
-                        chunk_offset,
-                        chunk_size,
-                        &src_extents));
-    } else {
-      Extent* src_extent = operation.add_src_extents();
-      src_extent->set_start_block(0);
-      src_extent->set_num_blocks((old_size + kBlockSize - 1) / kBlockSize);
-    }
-    operation.set_src_length(old_data.size());
-  }
-
-  if (gather_extents) {
-    TEST_AND_RETURN_FALSE(
-        GatherExtents(new_filename,
-                      chunk_offset,
-                      chunk_size,
-                      &dst_extents));
-  } else {
-    Extent* dst_extent = operation.add_dst_extents();
-    dst_extent->set_start_block(0);
-    dst_extent->set_num_blocks((new_data.size() + kBlockSize - 1) / kBlockSize);
-  }
-  operation.set_dst_length(new_data.size());
-
   if (gather_extents) {
     // Remove identical src/dst block ranges in MOVE operations.
     if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
@@ -599,6 +634,14 @@
     StoreExtents(dst_extents, operation.mutable_dst_extents());
   }
 
+  // Replace operations should not have source extents.
+  if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+      operation.type() ==
+          DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+    operation.clear_src_extents();
+    operation.clear_src_length();
+  }
+
   out_data->swap(data);
   *out_op = operation;
 
@@ -625,8 +668,10 @@
                      true,  // bsdiff_allowed
                      &data,
                      &op,
-                     false,
-                     src_ops_allowed));
+                     false,  // gather_extents
+                     src_ops_allowed,
+                     old_kernel_part,  // Doesn't matter, kernel has no files.
+                     new_kernel_part));
 
   // Check if the operation writes nothing.
   if (op.dst_extents_size() == 0) {
@@ -951,6 +996,8 @@
   Graph graph;
   TEST_AND_RETURN_FALSE(DeltaReadFiles(&graph,
                                        &blocks,
+                                       config.source.rootfs_part,
+                                       config.target.rootfs_part,
                                        config.source.rootfs_mountpt,
                                        config.target.rootfs_mountpt,
                                        config.chunk_size,
@@ -1253,4 +1300,9 @@
                                kBlockSize);
 }
 
+void DeltaDiffGenerator::ClearSparseHoles(vector<Extent>* extents) {
+  extents->erase(std::remove_if(extents->begin(), extents->end(), IsSparseHole),
+                 extents->end());
+}
+
 };  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
index 6004d31..9a35a61 100644
--- a/payload_generator/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -75,6 +75,8 @@
   // and writes any necessary data to the end of data_fd.
   static bool DeltaReadFiles(Graph* graph,
                              std::vector<Block>* blocks,
+                             const std::string& old_part,
+                             const std::string& new_part,
                              const std::string& old_root,
                              const std::string& new_root,
                              off_t chunk_size,
@@ -93,6 +95,8 @@
   static bool DeltaReadFile(Graph* graph,
                             Vertex::Index existing_vertex,
                             std::vector<Block>* blocks,
+                            const std::string& old_part,
+                            const std::string& new_part,
                             const std::string& old_root,
                             const std::string& new_root,
                             const std::string& path,
@@ -103,9 +107,9 @@
                             bool src_ops_allowed);
 
   // Reads old_filename (if it exists) and a new_filename and determines
-  // the smallest way to encode this file for the diff. It stores
-  // necessary data in out_data and fills in out_op.
-  // If there's no change in old and new files, it creates a MOVE
+  // the smallest way to encode this file for the diff. It reads extents from
+  // |old_part| and |new_part|. It stores necessary data in out_data and fills
+  // in out_op. If there's no change in old and new files, it creates a MOVE
   // operation. If there is a change, or the old file doesn't exist,
   // the smallest of REPLACE, REPLACE_BZ, or BSDIFF wins.
   // new_filename must contain at least one byte.
@@ -114,15 +118,17 @@
   // If |src_ops_allowed| is true, it will emit SOURCE_COPY and SOURCE_BSDIFF
   // operations instead of MOVE and BSDIFF, respectively.
   // Returns true on success.
-  static bool ReadFileToDiff(const std::string& old_filename,
-                             const std::string& new_filename,
+  static bool ReadFileToDiff(const std::string& old_part,
+                             const std::string& new_part,
                              off_t chunk_offset,
                              off_t chunk_size,
                              bool bsdiff_allowed,
                              chromeos::Blob* out_data,
                              DeltaArchiveManifest_InstallOperation* out_op,
                              bool gather_extents,
-                             bool src_ops_allowed);
+                             bool src_ops_allowed,
+                             const std::string& old_filename,
+                             const std::string& new_filename);
 
   // Delta compresses a kernel partition |new_kernel_part| with knowledge of the
   // old kernel partition |old_kernel_part|. If |old_kernel_part| is an empty
@@ -217,6 +223,9 @@
     return ret;
   }
 
+  // Takes a vector of extents and removes extents that begin in a sparse hole.
+  static void ClearSparseHoles(std::vector<Extent>* extents);
+
  private:
   DISALLOW_COPY_AND_ASSIGN(DeltaDiffGenerator);
 };
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
index 22d9c12..4769242 100644
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -9,6 +9,7 @@
 #include <sys/types.h>
 #include <unistd.h>
 
+#include <algorithm>
 #include <map>
 #include <set>
 #include <sstream>
@@ -75,6 +76,39 @@
   }
 }
 
+// Inserts |data| at block |offset| in |result|. Fills in the remaining blocks
+// so that there are |num_blocks| blocks in |result|.
+bool MakePartition(uint64_t num_blocks, const string& data, off_t offset,
+                   chromeos::Blob* result) {
+  TEST_AND_RETURN_FALSE(
+      static_cast<uint64_t>((kBlockSize * offset) + data.size()) <=
+                            kBlockSize * num_blocks);
+  chromeos::Blob out(kBlockSize * num_blocks, 0);
+  chromeos::Blob::iterator start = out.begin() + (kBlockSize * offset);
+  copy(data.begin(), data.end(), start);
+  *result = out;
+  return true;
+}
+
+// Copies from |target| to |result|. Gets the substring of |target| starting
+// at block |start_block| of length |num_blocks| blocks and inserts it at block
+// |block_offset| in |result|.
+void UpdatePartition(const string& target, uint64_t start_block,
+                     uint64_t num_blocks, off_t block_offset,
+                     chromeos::Blob* result) {
+  uint64_t num_insert = num_blocks * kBlockSize;
+  off_t target_offset = block_offset * kBlockSize;
+
+  const string target_substr = target.substr(kBlockSize * start_block,
+                                             num_insert);
+  ASSERT_EQ(target_substr.size(), num_insert);
+
+  for (uint64_t i = 0; i < num_insert; i++) {
+    result->at(target_offset + i) =
+        static_cast<unsigned char>(target_substr[i]);
+  }
+}
+
 }  // namespace
 
 class DeltaDiffGeneratorTest : public ::testing::Test {
@@ -84,6 +118,13 @@
                                     &old_path_, nullptr));
     ASSERT_TRUE(utils::MakeTempFile("DeltaDiffGeneratorTest-new_path-XXXXXX",
                                     &new_path_, nullptr));
+    ASSERT_TRUE(utils::MakeTempFile(
+        "DeltaDiffGeneratorTest-old_part_path-XXXXXX",
+        &old_part_path_, nullptr));
+    ASSERT_TRUE(utils::MakeTempFile(
+        "DeltaDiffGeneratorTest-new_part_path-XXXXXX",
+        &new_part_path_, nullptr));
+
     // Mock out the extent gathering function.
     orig_get_extents_with_chunk_func_ = get_extents_with_chunk_func;
     get_extents_with_chunk_func = FakeGetExtents;
@@ -94,6 +135,8 @@
   void TearDown() override {
     unlink(old_path_.c_str());
     unlink(new_path_.c_str());
+    unlink(old_part_path_.c_str());
+    unlink(new_part_path_.c_str());
     get_extents_with_chunk_func = orig_get_extents_with_chunk_func_;
   }
 
@@ -127,6 +170,10 @@
   string old_path_;
   string new_path_;
 
+  // Paths to old and new temporary filesystems used in the tests.
+  string old_part_path_;
+  string new_part_path_;
+
   GetExtentsWithChunk orig_get_extents_with_chunk_func_;
 };
 
@@ -139,27 +186,43 @@
 }
 
 TEST_F(DeltaDiffGeneratorTest, MoveSmallTest) {
+  const string random_string(reinterpret_cast<const char*>(kRandomString),
+                             sizeof(kRandomString));
   EXPECT_TRUE(utils::WriteFile(old_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString)));
+                               random_string.c_str(),
+                               random_string.size()));
   EXPECT_TRUE(utils::WriteFile(new_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString)));
+                               random_string.c_str(),
+                               random_string.size()));
+
+  chromeos::Blob old_part;
+  chromeos::Blob new_part;
+  EXPECT_TRUE(MakePartition(11, random_string, 10, &old_part));
+  EXPECT_TRUE(MakePartition(1, random_string, 0, &new_part));
+
+  EXPECT_TRUE(utils::WriteFile(old_part_path_.c_str(),
+                               old_part.data(), old_part.size()));
+  EXPECT_TRUE(utils::WriteFile(new_part_path_.c_str(),
+                               new_part.data(), new_part.size()));
+
   // Force the old file to be on a different block.
   UpdateFakeFileExtents(old_path_, kBlockSize, 10);
   UpdateFakeFileExtents(new_path_, kBlockSize);
 
   chromeos::Blob data;
   DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path_,
-                                                 new_path_,
+
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_part_path_,
+                                                 new_part_path_,
                                                  0,  // chunk_offset
                                                  -1,  // chunk_size
                                                  true,  // bsdiff_allowed
                                                  &data,
                                                  &op,
                                                  true,  // gather_extents
-                                                 false));  // src_ops_allowed
+                                                 false,  // src_ops_allowed
+                                                 old_path_,
+                                                 new_path_));
   EXPECT_TRUE(data.empty());
 
   EXPECT_TRUE(op.has_type());
@@ -167,9 +230,9 @@
   EXPECT_FALSE(op.has_data_offset());
   EXPECT_FALSE(op.has_data_length());
   EXPECT_EQ(1, op.src_extents_size());
-  EXPECT_EQ(sizeof(kRandomString), op.src_length());
+  EXPECT_EQ(kBlockSize, op.src_length());
   EXPECT_EQ(1, op.dst_extents_size());
-  EXPECT_EQ(sizeof(kRandomString), op.dst_length());
+  EXPECT_EQ(kBlockSize, op.dst_length());
   EXPECT_EQ(BlocksInExtents(op.src_extents()),
             BlocksInExtents(op.dst_extents()));
   EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
@@ -207,24 +270,49 @@
   string random_data;
   while (random_data.size() < file_len)
     random_data += random_string;
-  if (random_data.size() > file_len)
+  if (random_data.size() > file_len) {
     random_data.erase(file_len);
+    random_data.insert(random_data.end(), (4096 - 3333), 0);
+  }
+
   EXPECT_TRUE(utils::WriteFile(old_path_.c_str(),
                                random_data.c_str(), file_len));
   EXPECT_TRUE(utils::WriteFile(new_path_.c_str(),
                                random_data.c_str(), file_len));
 
+  // Make partitions that match the extents and random_data.
+  chromeos::Blob old_part;
+  chromeos::Blob new_part;
+  EXPECT_TRUE(MakePartition(30, "", 0, &old_part));
+  EXPECT_TRUE(MakePartition(30, "", 0, &new_part));
+
+  UpdatePartition(random_data, 0, 6, 20, &old_part);
+  UpdatePartition(random_data, 6, 2, 28, &old_part);
+
+  UpdatePartition(random_data, 0, 1, 18, &new_part);
+  UpdatePartition(random_data, 1, 2, 21, &new_part);
+  UpdatePartition(random_data, 3, 1, 20, &new_part);
+  UpdatePartition(random_data, 4, 3, 24, &new_part);
+  UpdatePartition(random_data, 7, 1, 29, &new_part);
+
+  EXPECT_TRUE(utils::WriteFile(old_part_path_.c_str(),
+                               old_part.data(), old_part.size()));
+  EXPECT_TRUE(utils::WriteFile(new_part_path_.c_str(),
+                               new_part.data(), new_part.size()));
+
   chromeos::Blob data;
   DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path_,
-                                                 new_path_,
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_part_path_,
+                                                 new_part_path_,
                                                  0,  // chunk_offset
                                                  -1,  // chunk_size
                                                  true,  // bsdiff_allowed
                                                  &data,
                                                  &op,
                                                  true,  // gather_extents
-                                                 false));  // src_ops_allowed
+                                                 false,  // src_ops_allowed
+                                                 old_path_,
+                                                 new_path_));
 
   // Adjust the old/new extents to remove duplicates.
   old_extents[0].set_num_blocks(1);
@@ -269,25 +357,41 @@
 }
 
 TEST_F(DeltaDiffGeneratorTest, BsdiffSmallTest) {
+  const string random_string(reinterpret_cast<const char*>(kRandomString),
+                             sizeof(kRandomString));
   EXPECT_TRUE(utils::WriteFile(old_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString) - 1));
+                               random_string.c_str(),
+                               random_string.size() - 1));
   EXPECT_TRUE(utils::WriteFile(new_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString)));
+                               random_string.c_str(),
+                               random_string.size()));
   UpdateFakeExtents();
 
+  chromeos::Blob old_part;
+  chromeos::Blob new_part;
+  EXPECT_TRUE(MakePartition(
+      1, random_string.substr(0, random_string.size() - 1),  0, &old_part));
+  EXPECT_TRUE(MakePartition(1, random_string, 0, &new_part));
+
+  EXPECT_TRUE(utils::WriteFile(old_part_path_.c_str(),
+                               old_part.data(), old_part.size()));
+  EXPECT_TRUE(utils::WriteFile(new_part_path_.c_str(),
+                               new_part.data(), new_part.size()));
+
   chromeos::Blob data;
   DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path_,
-                                                 new_path_,
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_part_path_,
+                                                 new_part_path_,
                                                  0,  // chunk_offset
                                                  -1,  // chunk_size
                                                  true,  // bsdiff_allowed
                                                  &data,
                                                  &op,
                                                  true,  // gather_extents
-                                                 false));  // src_ops_allowed
+                                                 false,  // src_ops_allowed
+                                                 old_path_,
+                                                 new_path_));
+
   EXPECT_FALSE(data.empty());
 
   EXPECT_TRUE(op.has_type());
@@ -295,35 +399,51 @@
   EXPECT_FALSE(op.has_data_offset());
   EXPECT_FALSE(op.has_data_length());
   EXPECT_EQ(1, op.src_extents_size());
-  EXPECT_EQ(sizeof(kRandomString) - 1, op.src_length());
+  EXPECT_EQ(kBlockSize, op.src_length());
   EXPECT_EQ(1, op.dst_extents_size());
-  EXPECT_EQ(sizeof(kRandomString), op.dst_length());
+  EXPECT_EQ(kBlockSize, op.dst_length());
   EXPECT_EQ(BlocksInExtents(op.src_extents()),
             BlocksInExtents(op.dst_extents()));
   EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
 }
 
 TEST_F(DeltaDiffGeneratorTest, BsdiffNotAllowedTest) {
+  const string random_string(reinterpret_cast<const char*>(kRandomString),
+                             sizeof(kRandomString));
   EXPECT_TRUE(utils::WriteFile(old_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString) - 1));
+                               random_string.c_str(),
+                               random_string.size() - 1));
   EXPECT_TRUE(utils::WriteFile(new_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString)));
+                               random_string.c_str(),
+                               random_string.size()));
   UpdateFakeExtents();
 
+  chromeos::Blob old_part;
+  chromeos::Blob new_part;
+  EXPECT_TRUE(MakePartition(
+      1, random_string.substr(0, random_string.size() - 1),  0, &old_part));
+  EXPECT_TRUE(MakePartition(1, random_string, 0, &new_part));
+
+  EXPECT_TRUE(utils::WriteFile(old_part_path_.c_str(),
+                               old_part.data(), old_part.size()));
+  EXPECT_TRUE(utils::WriteFile(new_part_path_.c_str(),
+                               new_part.data(), new_part.size()));
+
   chromeos::Blob data;
   DeltaArchiveManifest_InstallOperation op;
 
-  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path_,
-                                                 new_path_,
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_part_path_,
+                                                 new_part_path_,
                                                  0,  // chunk_offset
                                                  -1,  // chunk_size
                                                  false,  // bsdiff_allowed
                                                  &data,
                                                  &op,
                                                  true,  // gather_extents
-                                                 false));  // src_ops_allowed
+                                                 false,  // src_ops_allowed
+                                                 old_path_,
+                                                 new_path_));
+
   EXPECT_FALSE(data.empty());
 
   // The point of this test is that we don't use BSDIFF the way the above
@@ -333,26 +453,41 @@
 }
 
 TEST_F(DeltaDiffGeneratorTest, BsdiffNotAllowedMoveTest) {
+  const string random_string(reinterpret_cast<const char*>(kRandomString),
+                             sizeof(kRandomString));
   EXPECT_TRUE(utils::WriteFile(old_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString)));
+                               random_string.c_str(),
+                               random_string.size()));
   EXPECT_TRUE(utils::WriteFile(new_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString)));
+                               random_string.c_str(),
+                               random_string.size()));
   UpdateFakeExtents();
 
+  chromeos::Blob old_part;
+  chromeos::Blob new_part;
+  EXPECT_TRUE(MakePartition(1, random_string,  0, &old_part));
+  EXPECT_TRUE(MakePartition(1, random_string, 0, &new_part));
+
+  EXPECT_TRUE(utils::WriteFile(old_part_path_.c_str(),
+                               old_part.data(), old_part.size()));
+  EXPECT_TRUE(utils::WriteFile(new_part_path_.c_str(),
+                               new_part.data(), new_part.size()));
+
   chromeos::Blob data;
   DeltaArchiveManifest_InstallOperation op;
 
-  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path_,
-                                                 new_path_,
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_part_path_,
+                                                 new_part_path_,
                                                  0,  // chunk_offset
                                                  -1,  // chunk_size
                                                  false,  // bsdiff_allowed
                                                  &data,
                                                  &op,
                                                  true,  // gather_extents
-                                                 false));  // src_ops_allowed
+                                                 false,  // src_ops_allowed
+                                                 old_path_,
+                                                 new_path_));
+
   EXPECT_TRUE(data.empty());
 
   // The point of this test is that we can still use a MOVE for a file
@@ -362,26 +497,54 @@
 }
 
 TEST_F(DeltaDiffGeneratorTest, ReplaceSmallTest) {
-  chromeos::Blob new_data;
+  chromeos::Blob new_part;
+
+  chromeos::Blob old_part(kBlockSize, 0);
+  EXPECT_TRUE(utils::WriteFile(old_part_path_.c_str(),
+                               old_part.data(), old_part.size()));
+
+  // Fill old_path with zeroes.
+  chromeos::Blob old_data(kBlockSize, 0);
+  EXPECT_TRUE(utils::WriteFile(old_path_.c_str(),
+                               old_data.data(),
+                               old_data.size()));
+
+  chromeos::Blob random_data;
+  // Make a blob with random data that won't compress well.
+  std::mt19937 gen(12345);
+  std::uniform_int_distribution<uint8_t> dis(0, 255);
+  for (uint32_t i = 0; i < kBlockSize; i++) {
+    random_data.push_back(dis(gen));
+  }
+
+  // Make a blob that's just 1's that will compress well.
+  chromeos::Blob ones(kBlockSize, 1);
+
   for (int i = 0; i < 2; i++) {
-    new_data.insert(new_data.end(),
-                    std::begin(kRandomString), std::end(kRandomString));
+    chromeos::Blob data_to_test = i == 0 ? random_data : ones;
     EXPECT_TRUE(utils::WriteFile(new_path_.c_str(),
-                                 new_data.data(),
-                                 new_data.size()));
+                                 data_to_test.data(),
+                                 data_to_test.size()));
     UpdateFakeExtents();
 
+    string data_str(data_to_test.begin(), data_to_test.end());
+    EXPECT_TRUE(MakePartition(1, data_str, 0, &new_part));
+    EXPECT_TRUE(utils::WriteFile(new_part_path_.c_str(),
+                                 new_part.data(), new_part.size()));
+
     chromeos::Blob data;
     DeltaArchiveManifest_InstallOperation op;
-    EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path_,
-                                                   new_path_,
+    EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_part_path_,
+                                                   new_part_path_,
                                                    0,  // chunk_offset
                                                    -1,  // chunk_size
                                                    true,  // bsdiff_allowed
                                                    &data,
                                                    &op,
                                                    true,  // gather_extents
-                                                   false));  // src_ops_allowed
+                                                   false,  // src_ops_allowed
+                                                   old_path_,
+                                                   new_path_));
     EXPECT_FALSE(data.empty());
 
     EXPECT_TRUE(op.has_type());
@@ -394,29 +557,45 @@
     EXPECT_EQ(0, op.src_extents_size());
     EXPECT_FALSE(op.has_src_length());
     EXPECT_EQ(1, op.dst_extents_size());
-    EXPECT_EQ(new_data.size(), op.dst_length());
+    EXPECT_EQ(data_to_test.size(), op.dst_length());
     EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
   }
 }
 
 TEST_F(DeltaDiffGeneratorTest, BsdiffNoGatherExtentsSmallTest) {
+  const string random_string(reinterpret_cast<const char*>(kRandomString),
+                             sizeof(kRandomString));
   EXPECT_TRUE(utils::WriteFile(old_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString) - 1));
+                               random_string.data(),
+                               random_string.size() - 1));
   EXPECT_TRUE(utils::WriteFile(new_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString)));
+                               random_string.c_str(),
+                               random_string.size()));
+
+  chromeos::Blob old_part;
+  chromeos::Blob new_part;
+  EXPECT_TRUE(MakePartition(
+      1, random_string.substr(0, random_string.size() - 1),  0, &old_part));
+  EXPECT_TRUE(MakePartition(1, random_string, 0, &new_part));
+
+  EXPECT_TRUE(utils::WriteFile(old_part_path_.c_str(),
+                               old_part.data(), old_part.size()));
+  EXPECT_TRUE(utils::WriteFile(new_part_path_.c_str(),
+                               new_part.data(), new_part.size()));
   chromeos::Blob data;
   DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path_,
-                                                 new_path_,
+
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_part_path_,
+                                                 new_part_path_,
                                                  0,  // chunk_offset
                                                  -1,  // chunk_size
                                                  true,  // bsdiff_allowed
                                                  &data,
                                                  &op,
                                                  false,  // gather_extents
-                                                 false));  // src_ops_allowed
+                                                 false,  // src_ops_allowed
+                                                 old_path_,
+                                                 new_path_));
   EXPECT_FALSE(data.empty());
 
   EXPECT_TRUE(op.has_type());
@@ -426,36 +605,51 @@
   EXPECT_EQ(1, op.src_extents_size());
   EXPECT_EQ(0, op.src_extents().Get(0).start_block());
   EXPECT_EQ(1, op.src_extents().Get(0).num_blocks());
-  EXPECT_EQ(sizeof(kRandomString) - 1, op.src_length());
+  EXPECT_EQ(kBlockSize, op.src_length());
   EXPECT_EQ(1, op.dst_extents_size());
   EXPECT_EQ(0, op.dst_extents().Get(0).start_block());
   EXPECT_EQ(1, op.dst_extents().Get(0).num_blocks());
-  EXPECT_EQ(sizeof(kRandomString), op.dst_length());
+  EXPECT_EQ(kBlockSize, op.dst_length());
 }
 
 TEST_F(DeltaDiffGeneratorTest, SourceCopyTest) {
   // Makes sure SOURCE_COPY operations are emitted whenever src_ops_allowed
   // is true. It is the same setup as MoveSmallTest, which checks that
   // the operation is well-formed.
+  const string random_string(reinterpret_cast<const char*>(kRandomString),
+                             sizeof(kRandomString));
   EXPECT_TRUE(utils::WriteFile(old_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString)));
+                               random_string.data(),
+                               random_string.size()));
   EXPECT_TRUE(utils::WriteFile(new_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString)));
+                               random_string.c_str(),
+                               random_string.size()));
   UpdateFakeExtents();
 
   chromeos::Blob data;
   DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path_,
-                                                 new_path_,
+
+  chromeos::Blob old_part;
+  chromeos::Blob new_part;
+  EXPECT_TRUE(MakePartition(1, random_string,  0, &old_part));
+  EXPECT_TRUE(MakePartition(1, random_string, 0, &new_part));
+
+  EXPECT_TRUE(utils::WriteFile(old_part_path_.c_str(),
+                               old_part.data(), old_part.size()));
+  EXPECT_TRUE(utils::WriteFile(new_part_path_.c_str(),
+                               new_part.data(), new_part.size()));
+
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_part_path_,
+                                                 new_part_path_,
                                                  0,  // chunk_offset
                                                  -1,  // chunk_size
                                                  true,  // bsdiff_allowed
                                                  &data,
                                                  &op,
                                                  true,  // gather_extents
-                                                 true));  // src_ops_allowed
+                                                 true,  // src_ops_allowed
+                                                 old_path_,
+                                                 new_path_));
   EXPECT_TRUE(data.empty());
 
   EXPECT_TRUE(op.has_type());
@@ -466,25 +660,42 @@
   // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
   // is true. It is the same setup as BsdiffSmallTest, which checks
   // that the operation is well-formed.
+  const string random_string(reinterpret_cast<const char*>(kRandomString),
+                             sizeof(kRandomString));
   EXPECT_TRUE(utils::WriteFile(old_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString) - 1));
+                               random_string.data(),
+                               random_string.size() - 1));
   EXPECT_TRUE(utils::WriteFile(new_path_.c_str(),
-                               reinterpret_cast<const char*>(kRandomString),
-                               sizeof(kRandomString)));
+                               random_string.c_str(),
+                               random_string.size()));
   UpdateFakeExtents();
 
+  chromeos::Blob old_part;
+  chromeos::Blob new_part;
+  EXPECT_TRUE(MakePartition(
+      1, random_string.substr(0, random_string.size() - 1),  0, &old_part));
+  EXPECT_TRUE(MakePartition(1, random_string, 0, &new_part));
+
+  EXPECT_TRUE(utils::WriteFile(old_part_path_.c_str(),
+                               old_part.data(), old_part.size()));
+  EXPECT_TRUE(utils::WriteFile(new_part_path_.c_str(),
+                               new_part.data(), new_part.size()));
+
   chromeos::Blob data;
   DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path_,
-                                                 new_path_,
+
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_part_path_,
+                                                 new_part_path_,
                                                  0,  // chunk_offset
                                                  -1,  // chunk_size
                                                  true,  // bsdiff_allowed
                                                  &data,
                                                  &op,
                                                  true,  // gather_extents
-                                                 true));  // src_ops_allowed
+                                                 true,  // src_ops_allowed
+                                                 old_path_,
+                                                 new_path_));
+
   EXPECT_FALSE(data.empty());
   EXPECT_TRUE(op.has_type());
   EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF,
@@ -546,10 +757,6 @@
   *(op.add_dst_extents()) = ExtentForRange(20, 1);
   *(op.add_dst_extents()) = ExtentForRange(21, 1);
   EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
-  *(op.add_src_extents()) = ExtentForRange(kSparseHole, 2);
-  *(op.add_src_extents()) = ExtentForRange(kSparseHole, 1);
-  *(op.add_dst_extents()) = ExtentForRange(kSparseHole, 3);
-  EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
   *(op.add_src_extents()) = ExtentForRange(24, 1);
   *(op.add_dst_extents()) = ExtentForRange(25, 1);
   EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
@@ -577,4 +784,18 @@
   EXPECT_EQ("aop2", ops[1].name);
 }
 
+TEST_F(DeltaDiffGeneratorTest, SparseHolesFilteredTest) {
+  // Test to see that extents starting with a sparse hole are filtered out by
+  // ClearSparseHoles.
+  vector<Extent> extents;
+  AddExtent(kSparseHole, 1, &extents);
+  AddExtent(21, 2, &extents);
+  AddExtent(kSparseHole, 3, &extents);
+  AddExtent(29, 1, &extents);
+  DeltaDiffGenerator::ClearSparseHoles(&extents);
+  EXPECT_EQ(extents.size(), 2);
+  EXPECT_EQ(extents[0], ExtentForRange(21, 2));
+  EXPECT_EQ(extents[1], ExtentForRange(29, 1));
+}
+
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index 0e3284c..23617f3 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -269,8 +269,6 @@
     Extent extent = graph_utils::GetElement(extents, i);
     uint64_t start = extent.start_block();
     uint64_t num = extent.num_blocks();
-    if (start == kSparseHole)
-      continue;
     if (start >= kTempBlockStart || (start + num) >= kTempBlockStart) {
       LOG(ERROR) << "temp block!";
       LOG(ERROR) << "start: " << start << ", num: " << num;
@@ -291,6 +289,7 @@
 bool ConvertCutsToFull(
     Graph* graph,
     const string& new_root,
+    const string& new_part,
     int data_fd,
     off_t* data_file_size,
     vector<Vertex::Index>* op_indexes,
@@ -302,6 +301,7 @@
     TEST_AND_RETURN_FALSE(InplaceGenerator::ConvertCutToFullOp(
         graph,
         cut,
+        new_part,
         new_root,
         data_fd,
         data_file_size));
@@ -331,6 +331,7 @@
 bool AssignBlockForAdjoiningCuts(
     Graph* graph,
     const string& new_root,
+    const string& new_part,
     int data_fd,
     off_t* data_file_size,
     vector<Vertex::Index>* op_indexes,
@@ -395,6 +396,7 @@
     LOG(INFO) << "Unable to find sufficient scratch";
     TEST_AND_RETURN_FALSE(ConvertCutsToFull(graph,
                                             new_root,
+                                            new_part,
                                             data_fd,
                                             data_file_size,
                                             op_indexes,
@@ -441,6 +443,7 @@
 bool InplaceGenerator::AssignTempBlocks(
     Graph* graph,
     const string& new_root,
+    const string& new_part,
     int data_fd,
     off_t* data_file_size,
     vector<Vertex::Index>* op_indexes,
@@ -464,6 +467,7 @@
       CHECK(!cuts_group.empty());
       TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
                                                         new_root,
+                                                        new_part,
                                                         data_fd,
                                                         data_file_size,
                                                         op_indexes,
@@ -481,6 +485,7 @@
   CHECK(!cuts_group.empty());
   TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
                                                     new_root,
+                                                    new_part,
                                                     data_fd,
                                                     data_file_size,
                                                     op_indexes,
@@ -518,6 +523,7 @@
 
 bool InplaceGenerator::ConvertCutToFullOp(Graph* graph,
                                           const CutEdgeVertexes& cut,
+                                          const string& new_part,
                                           const string& new_root,
                                           int data_fd,
                                           off_t* data_file_size) {
@@ -535,6 +541,8 @@
         graph,
         cut.old_dst,
         nullptr,
+        kEmptyPath,  // old_part
+        new_part,
         kEmptyPath,
         new_root,
         (*graph)[cut.old_dst].file_name,
@@ -561,6 +569,7 @@
 }
 
 bool InplaceGenerator::ConvertGraphToDag(Graph* graph,
+                                        const string& new_part,
                                         const string& new_root,
                                         int fd,
                                         off_t* data_file_size,
@@ -598,6 +607,7 @@
 
   if (!cuts.empty())
     TEST_AND_RETURN_FALSE(AssignTempBlocks(graph,
+                                           new_part,
                                            new_root,
                                            fd,
                                            data_file_size,
@@ -654,10 +664,6 @@
 
     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) {
@@ -688,6 +694,8 @@
   TEST_AND_RETURN_FALSE(
       DeltaDiffGenerator::DeltaReadFiles(&graph,
                                          &blocks,
+                                         config.source.rootfs_part,
+                                         config.target.rootfs_part,
                                          config.source.rootfs_mountpt,
                                          config.target.rootfs_mountpt,
                                          config.chunk_size,
@@ -753,6 +761,7 @@
   vector<Vertex::Index> final_order;
   TEST_AND_RETURN_FALSE(ConvertGraphToDag(
       &graph,
+      config.target.rootfs_part,
       config.target.rootfs_mountpt,
       data_file_fd,
       data_file_size,
diff --git a/payload_generator/inplace_generator.h b/payload_generator/inplace_generator.h
index 5799c0b..9d10548 100644
--- a/payload_generator/inplace_generator.h
+++ b/payload_generator/inplace_generator.h
@@ -103,6 +103,7 @@
   // success.
   static bool AssignTempBlocks(
       Graph* graph,
+      const std::string& new_part,
       const std::string& new_root,
       int data_fd,
       off_t* data_file_size,
@@ -119,6 +120,7 @@
   // A->B. Now, A is a full operation.
   static bool ConvertCutToFullOp(Graph* graph,
                                  const CutEdgeVertexes& cut,
+                                 const std::string& new_part,
                                  const std::string& new_root,
                                  int data_fd,
                                  off_t* data_file_size);
@@ -133,6 +135,7 @@
   // |final_order| before returning.
   // Returns true on success.
   static bool ConvertGraphToDag(Graph* graph,
+                                const std::string& new_part,
                                 const std::string& new_root,
                                 int fd,
                                 off_t* data_file_size,
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
index 051902f..fdf3aba 100644
--- a/payload_generator/inplace_generator_unittest.cc
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -340,6 +340,7 @@
 
   EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph,
                                                  temp_dir,
+                                                 "/dev/zero",
                                                  fd,
                                                  &data_file_size,
                                                  &op_indexes,
@@ -436,9 +437,9 @@
   ScopedFdCloser fd_closer(&fd);
   off_t data_file_size = 0;
 
-
   EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
                                                   temp_dir,
+                                                  "/dev/zero",
                                                   fd,
                                                   &data_file_size,
                                                   &final_order,
@@ -512,189 +513,6 @@
   }
 }
 
-// Test that sparse holes are not used as scratch. More specifically, test that
-// if all full operations write to sparse holes and there's no extra scratch
-// space, delta operations that need scratch are converted to full. See
-// crbug.com/238440.
-TEST_F(InplaceGeneratorTest, RunAsRootNoSparseAsTempTest) {
-  Graph graph(3);
-  const vector<Extent> kEmpty;
-  const string kFilename = "/foo";
-
-  // Make sure this sparse hole is not used as scratch.
-  GenVertex(&graph[0], kEmpty, VectOfExt(kSparseHole, 1), "", OP_REPLACE);
-
-  // Create a single-block cycle.
-  GenVertex(&graph[1], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_BSDIFF);
-  graph[1].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
-  GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(0, 1), kFilename, OP_BSDIFF);
-  graph[2].out_edges[1] = EdgeWithReadDep(VectOfExt(0, 1));
-
-  graph_utils::DumpGraph(graph);
-
-  vector<Vertex::Index> final_order;
-
-  // Prepare the filesystem with the minimum required for this to work.
-  string temp_dir;
-  EXPECT_TRUE(utils::MakeTempDirectory("NoSparseAsTempTest.XXXXXX",
-                                       &temp_dir));
-  ScopedDirRemover temp_dir_remover(temp_dir);
-
-  chromeos::Blob temp_data(kBlockSize);
-  test_utils::FillWithData(&temp_data);
-  EXPECT_TRUE(test_utils::WriteFileVector(temp_dir + kFilename, temp_data));
-  ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
-
-  int fd = -1;
-  EXPECT_TRUE(utils::MakeTempFile("NoSparseAsTempTestData.XXXXXX",
-                                  nullptr,
-                                  &fd));
-  ScopedFdCloser fd_closer(&fd);
-  off_t data_file_size = 0;
-
-  EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
-                                                  temp_dir,
-                                                  fd,
-                                                  &data_file_size,
-                                                  &final_order,
-                                                  Vertex::kInvalidIndex));
-
-  ASSERT_EQ(4, graph.size());
-
-  // The second BSDIFF operation must have been converted to a full operation
-  // (due to insufficient scratch space).
-  EXPECT_TRUE(graph[2].op.type() == OP_REPLACE ||
-              graph[2].op.type() == OP_REPLACE_BZ);
-
-  // The temporary node created for breaking the cycle must have been marked as
-  // invalid.
-  EXPECT_FALSE(graph[3].valid);
-}
-
-// Test that sparse holes are not used as scratch. More specifically, test that
-// if scratch space comes only from full operations writing to real blocks as
-// well as sparse holes, only the real blocks are utilized. See
-// crbug.com/238440.
-TEST_F(InplaceGeneratorTest, NoSparseAsTempTest) {
-  Graph graph;
-  vector<Block> blocks(4);
-
-  // Create nodes in |graph|.
-  {
-    graph.resize(graph.size() + 1);
-    graph.back().op.set_type(
-        DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-
-    // Write to a sparse hole -- basically a no-op to ensure sparse holes are
-    // not used as scratch.
-    vector<Extent> extents;
-    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
-    DeltaDiffGenerator::StoreExtents(extents,
-                                     graph.back().op.mutable_dst_extents());
-  }
-  {
-    graph.resize(graph.size() + 1);
-    graph.back().op.set_type(OP_REPLACE);
-
-    // Scratch space: write to block 0 with sparse holes around.
-    vector<Extent> extents;
-    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
-    graph_utils::AppendBlockToExtents(&extents, 0);
-    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
-    DeltaDiffGenerator::StoreExtents(extents,
-                                     graph.back().op.mutable_dst_extents());
-    blocks[0].writer = graph.size() - 1;
-  }
-  {
-    graph.resize(graph.size() + 1);
-    graph.back().op.set_type(OP_REPLACE);
-
-    // Write to a sparse hole.
-    vector<Extent> extents;
-    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
-    DeltaDiffGenerator::StoreExtents(extents,
-                                     graph.back().op.mutable_dst_extents());
-  }
-  // Create a two-node cycle between (2, sparse, sparse) and (1, sparse, 3).
-  {
-    graph.resize(graph.size() + 1);
-    graph.back().op.set_type(OP_MOVE);
-    // Read from (2, sparse, sparse).
-    vector<Extent> extents;
-    graph_utils::AppendBlockToExtents(&extents, 2);
-    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
-    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
-    DeltaDiffGenerator::StoreExtents(extents,
-                                     graph.back().op.mutable_src_extents());
-    blocks[2].reader = graph.size() - 1;
-
-    // Write to (1, sparse, 3).
-    extents.clear();
-    graph_utils::AppendBlockToExtents(&extents, 1);
-    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
-    graph_utils::AppendBlockToExtents(&extents, 3);
-    DeltaDiffGenerator::StoreExtents(extents,
-                                     graph.back().op.mutable_dst_extents());
-    blocks[1].writer = graph.size() - 1;
-    blocks[3].writer = graph.size() - 1;
-  }
-  {
-    graph.resize(graph.size() + 1);
-    graph.back().op.set_type(OP_MOVE);
-    // Read from (1, sparse, 3).
-    vector<Extent> extents;
-    graph_utils::AppendBlockToExtents(&extents, 1);
-    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
-    graph_utils::AppendBlockToExtents(&extents, 3);
-    DeltaDiffGenerator::StoreExtents(extents,
-                                     graph.back().op.mutable_src_extents());
-    blocks[1].reader = graph.size() - 1;
-    blocks[3].reader = graph.size() - 1;
-
-    // Write to (2, sparse, sparse).
-    extents.clear();
-    graph_utils::AppendBlockToExtents(&extents, 2);
-    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
-    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
-    DeltaDiffGenerator::StoreExtents(extents,
-                                     graph.back().op.mutable_dst_extents());
-    blocks[2].writer = graph.size() - 1;
-  }
-
-  graph_utils::DumpGraph(graph);
-
-  // Create edges
-  InplaceGenerator::CreateEdges(&graph, blocks);
-
-  graph_utils::DumpGraph(graph);
-
-  vector<Vertex::Index> final_order;
-  off_t data_file_size = 0;
-  EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
-                                                  "/non/existent/dir",
-                                                  -1,
-                                                  &data_file_size,
-                                                  &final_order,
-                                                  Vertex::kInvalidIndex));
-
-  // Check for a single temporary node writing to scratch.
-  ASSERT_EQ(6, graph.size());
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
-            graph[5].op.type());
-  EXPECT_EQ(1, graph[5].op.src_extents_size());
-  ASSERT_EQ(1, graph[5].op.dst_extents_size());
-  EXPECT_EQ(0, graph[5].op.dst_extents(0).start_block());
-  EXPECT_EQ(1, graph[5].op.dst_extents(0).num_blocks());
-
-  // Make sure the cycle nodes still read from and write to sparse holes.
-  for (int i = 3; i < 5; i++) {
-    ASSERT_GE(graph[i].op.src_extents_size(), 2);
-    EXPECT_EQ(kSparseHole, graph[i].op.src_extents(1).start_block());
-    ASSERT_GE(graph[i].op.dst_extents_size(), 2);
-    EXPECT_EQ(kSparseHole, graph[i].op.dst_extents(1).start_block());
-  }
-}
-
 TEST_F(InplaceGeneratorTest, CreateScratchNodeTest) {
   Vertex vertex;
   InplaceGenerator::CreateScratchNode(12, 34, &vertex);
diff --git a/update_metadata.proto b/update_metadata.proto
index 923ea26..f99c912 100644
--- a/update_metadata.proto
+++ b/update_metadata.proto
@@ -130,15 +130,14 @@
 
     // Ordered list of extents that are read from (if any) and written to.
     repeated Extent src_extents = 4;
-    // Byte length of src, not necessarily block aligned. It's only used for
-    // BSDIFF, because we need to pass that external program the number
-    // of bytes to read from the blocks we pass it.
+    // Byte length of src, equal to the number of blocks in src_extents *
+    // block_size. It is used for BSDIFF, because we need to pass that
+    // external program the number of bytes to read from the blocks we pass it.
     optional uint64 src_length = 5;
 
     repeated Extent dst_extents = 6;
-    // byte length of dst, not necessarily block aligned. It's only used for
-    // BSDIFF, because we need to fill in the rest of the last block
-    // that bsdiff writes with '\0' bytes.
+    // Byte length of dst, equal to the number of blocks in dst_extents *
+    // block_size. Used for BSDIFF.
     optional uint64 dst_length = 7;
 
     // Optional SHA 256 hash of the blob associated with this operation.
diff --git a/utils.cc b/utils.cc
index c076682..31b25af 100644
--- a/utils.cc
+++ b/utils.cc
@@ -1691,6 +1691,32 @@
   return false;
 }
 
+bool ReadExtents(const std::string& path, vector<Extent>* extents,
+                 chromeos::Blob* out_data, ssize_t out_data_size,
+                 size_t block_size) {
+  chromeos::Blob data(out_data_size);
+  ssize_t bytes_read = 0;
+  int fd = open(path.c_str(), O_RDONLY);
+  TEST_AND_RETURN_FALSE_ERRNO(fd >= 0);
+  ScopedFdCloser fd_closer(&fd);
+
+  for (const Extent& extent : *extents) {
+    ssize_t bytes_read_this_iteration = 0;
+    ssize_t bytes = extent.num_blocks() * block_size;
+    TEST_AND_RETURN_FALSE(bytes_read + bytes <= out_data_size);
+    TEST_AND_RETURN_FALSE(utils::PReadAll(fd,
+                                          &data[bytes_read],
+                                          bytes,
+                                          extent.start_block() * block_size,
+                                          &bytes_read_this_iteration));
+    TEST_AND_RETURN_FALSE(bytes_read_this_iteration == bytes);
+    bytes_read += bytes_read_this_iteration;
+  }
+  TEST_AND_RETURN_FALSE(out_data_size == bytes_read);
+  *out_data = data;
+  return true;
+}
+
 }  // namespace utils
 
 }  // namespace chromeos_update_engine
diff --git a/utils.h b/utils.h
index 2374a94..6d8b373 100644
--- a/utils.h
+++ b/utils.h
@@ -28,6 +28,7 @@
 #include "update_engine/constants.h"
 #include "update_engine/file_descriptor.h"
 #include "update_engine/metrics.h"
+#include "update_engine/update_metadata.pb.h"
 
 namespace chromeos_update_engine {
 
@@ -468,6 +469,14 @@
 // value and setting it, and |false| otherwise.
 bool GetMinorVersion(base::FilePath path, uint32_t* minor_version);
 
+// This function reads the specified data in |extents| into |out_data|. The
+// extents are read from the file at |path|. |out_data_size| is the size of
+// |out_data|. Returns false if the number of bytes to read given in
+// |extents| does not equal |out_data_size|.
+bool ReadExtents(const std::string& path, std::vector<Extent>* extents,
+                 chromeos::Blob* out_data, ssize_t out_data_size,
+                 size_t block_size);
+
 }  // namespace utils