diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 0855232..77444e1 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -13,7 +13,6 @@
 #include <algorithm>
 #include <map>
 #include <memory>
-#include <set>
 #include <string>
 #include <utility>
 #include <vector>
@@ -28,29 +27,25 @@
 
 #include "update_engine/bzip.h"
 #include "update_engine/delta_performer.h"
-#include "update_engine/extent_ranges.h"
 #include "update_engine/file_writer.h"
 #include "update_engine/omaha_hash_calculator.h"
 #include "update_engine/payload_constants.h"
-#include "update_engine/payload_generator/cycle_breaker.h"
 #include "update_engine/payload_generator/extent_mapper.h"
 #include "update_engine/payload_generator/filesystem_iterator.h"
 #include "update_engine/payload_generator/full_update_generator.h"
 #include "update_engine/payload_generator/graph_types.h"
 #include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/inplace_generator.h"
 #include "update_engine/payload_generator/metadata.h"
 #include "update_engine/payload_generator/payload_signer.h"
-#include "update_engine/payload_generator/topological_sort.h"
 #include "update_engine/payload_verifier.h"
 #include "update_engine/subprocess.h"
 #include "update_engine/update_metadata.pb.h"
 #include "update_engine/utils.h"
 
-using std::make_pair;
 using std::map;
 using std::max;
 using std::min;
-using std::pair;
 using std::set;
 using std::string;
 using std::unique_ptr;
@@ -61,9 +56,6 @@
 const uint64_t kVersionNumber = 1;
 const uint64_t kFullUpdateChunkSize = 1024 * 1024;  // bytes
 
-const size_t kBlockSize = 4096;  // bytes
-const char kEmptyPath[] = "";
-
 // The maximum destination size allowed for bsdiff. In general, bsdiff should
 // work for arbitrary big files, but the payload generation and payload
 // application requires a significant amount of RAM. We put a hard-limit of
@@ -90,6 +82,9 @@
 
 // bytes
 const size_t kRootFSPartitionSize = static_cast<size_t>(2) * 1024 * 1024 * 1024;
+const size_t kBlockSize = 4096;  // bytes
+const char* const kEmptyPath = "";
+const char* const kBsdiffPath = "bsdiff";
 
 // Needed for testing purposes, in case we can't use actual filesystem objects.
 // TODO(garnold) (chromium:331965) Replace this hack with a properly injected
@@ -112,92 +107,6 @@
   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
-// necessary, if |blocks| is non-null.  Also, writes the data
-// necessary to send the file down to the client into data_fd, which
-// has length *data_file_size. *data_file_size is updated
-// appropriately. If |existing_vertex| is no kInvalidIndex, use that
-// rather than allocating a new vertex. Returns true on success.
-bool DeltaReadFile(Graph* graph,
-                   Vertex::Index existing_vertex,
-                   vector<Block>* blocks,
-                   const string& old_root,
-                   const string& new_root,
-                   const string& path,  // within new_root
-                   off_t chunk_offset,
-                   off_t chunk_size,
-                   int data_fd,
-                   off_t* data_file_size) {
-  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")
-  //
-  // TODO(dgarrett): chromium-os:15274 connect this test to the command line.
-  bool bsdiff_allowed = true;
-
-  if (utils::FileSize(new_root + path) > kMaxBsdiffDestinationSize)
-    bsdiff_allowed = false;
-
-  if (!bsdiff_allowed)
-    LOG(INFO) << "bsdiff blacklisting: " << path;
-
-  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ReadFileToDiff(old_path,
-                                                           new_root + path,
-                                                           chunk_offset,
-                                                           chunk_size,
-                                                           bsdiff_allowed,
-                                                           &data,
-                                                           &operation,
-                                                           true));
-
-  // Check if the operation writes nothing.
-  if (operation.dst_extents_size() == 0) {
-    if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
-      LOG(INFO) << "Empty MOVE operation (" << new_root + path << "), skipping";
-      return true;
-    } else {
-      LOG(ERROR) << "Empty non-MOVE operation";
-      return false;
-    }
-  }
-
-  // Write the data
-  if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
-    operation.set_data_offset(*data_file_size);
-    operation.set_data_length(data.size());
-  }
-
-  TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, data.data(), data.size()));
-  *data_file_size += data.size();
-
-  // Now, insert into graph and blocks vector
-  Vertex::Index vertex = existing_vertex;
-  if (vertex == Vertex::kInvalidIndex) {
-    graph->resize(graph->size() + 1);
-    vertex = graph->size() - 1;
-  }
-  (*graph)[vertex].op = operation;
-  CHECK((*graph)[vertex].op.has_type());
-  (*graph)[vertex].file_name = path;
-  (*graph)[vertex].chunk_offset = chunk_offset;
-  (*graph)[vertex].chunk_size = chunk_size;
-
-  if (blocks)
-    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::AddInstallOpToBlocksVector(
-        (*graph)[vertex].op,
-        *graph,
-        vertex,
-        blocks));
-  return true;
-}
-
 // For each regular file within new_root, creates a node in the graph,
 // determines the best way to compress it (REPLACE, REPLACE_BZ, COPY, BSDIFF),
 // and writes any necessary data to the end of data_fd.
@@ -252,41 +161,22 @@
       if (offset + size >= dst_size) {
         size = -1;  // Read through the end of the file.
       }
-      TEST_AND_RETURN_FALSE(DeltaReadFile(graph,
-                                          Vertex::kInvalidIndex,
-                                          blocks,
-                                          (should_diff_from_source ?
-                                           old_root :
-                                           kEmptyPath),
-                                          new_root,
-                                          fs_iter.GetPartialPath(),
-                                          offset,
-                                          size,
-                                          data_fd,
-                                          data_file_size));
+      TEST_AND_RETURN_FALSE(DeltaDiffGenerator::DeltaReadFile(
+          graph,
+          Vertex::kInvalidIndex,
+          blocks,
+          (should_diff_from_source ? old_root : kEmptyPath),
+          new_root,
+          fs_iter.GetPartialPath(),
+          offset,
+          size,
+          data_fd,
+          data_file_size));
     }
   }
   return true;
 }
 
-// This class allocates non-existent temp blocks, starting from
-// kTempBlockStart. Other code is responsible for converting these
-// temp blocks into real blocks, as the client can't read or write to
-// these blocks.
-class DummyExtentAllocator {
- public:
-  DummyExtentAllocator() : next_block_(kTempBlockStart) {}
-  vector<Extent> Allocate(const uint64_t block_count) {
-    vector<Extent> ret(1);
-    ret[0].set_start_block(next_block_);
-    ret[0].set_num_blocks(block_count);
-    next_block_ += block_count;
-    return ret;
-  }
- private:
-  uint64_t next_block_;
-};
-
 // Reads blocks from image_path that are not yet marked as being written in the
 // blocks array. These blocks that remain are either unchanged files or
 // non-file-data blocks.  We compare each of them to the old image, and compress
@@ -486,12 +376,6 @@
   }
 }
 
-void CheckGraph(const Graph& graph) {
-  for (const Vertex& v : graph) {
-    CHECK(v.op.has_type());
-  }
-}
-
 // 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
 // string, generates a full update of the partition.
@@ -704,6 +588,91 @@
 
 }  // namespace
 
+void DeltaDiffGenerator::CheckGraph(const Graph& graph) {
+  for (const Vertex& v : graph) {
+    CHECK(v.op.has_type());
+  }
+}
+
+bool DeltaDiffGenerator::DeltaReadFile(Graph* graph,
+                                       Vertex::Index existing_vertex,
+                                       vector<Block>* blocks,
+                                       const string& old_root,
+                                       const string& new_root,
+                                       const string& path,  // within new_root
+                                       off_t chunk_offset,
+                                       off_t chunk_size,
+                                       int data_fd,
+                                       off_t* data_file_size) {
+  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")
+  //
+  // TODO(dgarrett): chromium-os:15274 connect this test to the command line.
+  bool bsdiff_allowed = true;
+
+  if (utils::FileSize(new_root + path) > kMaxBsdiffDestinationSize)
+    bsdiff_allowed = false;
+
+  if (!bsdiff_allowed)
+    LOG(INFO) << "bsdiff blacklisting: " << path;
+
+  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ReadFileToDiff(old_path,
+                                                           new_root + path,
+                                                           chunk_offset,
+                                                           chunk_size,
+                                                           bsdiff_allowed,
+                                                           &data,
+                                                           &operation,
+                                                           true));
+
+  // Check if the operation writes nothing.
+  if (operation.dst_extents_size() == 0) {
+    if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+      LOG(INFO) << "Empty MOVE operation (" << new_root + path << "), skipping";
+      return true;
+    } else {
+      LOG(ERROR) << "Empty non-MOVE operation";
+      return false;
+    }
+  }
+
+  // Write the data
+  if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+    operation.set_data_offset(*data_file_size);
+    operation.set_data_length(data.size());
+  }
+
+  TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, data.data(), data.size()));
+  *data_file_size += data.size();
+
+  // Now, insert into graph and blocks vector
+  Vertex::Index vertex = existing_vertex;
+  if (vertex == Vertex::kInvalidIndex) {
+    graph->resize(graph->size() + 1);
+    vertex = graph->size() - 1;
+  }
+  (*graph)[vertex].op = operation;
+  CHECK((*graph)[vertex].op.has_type());
+  (*graph)[vertex].file_name = path;
+  (*graph)[vertex].chunk_offset = chunk_offset;
+  (*graph)[vertex].chunk_size = chunk_size;
+
+  if (blocks)
+    TEST_AND_RETURN_FALSE(InplaceGenerator::AddInstallOpToBlocksVector(
+        (*graph)[vertex].op,
+        *graph,
+        vertex,
+        blocks));
+  return true;
+}
+
+
 bool DeltaDiffGenerator::ReadFileToDiff(
     const string& old_filename,
     const string& new_filename,
@@ -899,139 +868,6 @@
   return true;
 }
 
-namespace {
-
-// Takes a collection (vector or RepeatedPtrField) of Extent and
-// returns a vector of the blocks referenced, in order.
-template<typename T>
-vector<uint64_t> ExpandExtents(const T& extents) {
-  vector<uint64_t> ret;
-  for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) {
-    const Extent extent = graph_utils::GetElement(extents, i);
-    if (extent.start_block() == kSparseHole) {
-      ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
-    } else {
-      for (uint64_t block = extent.start_block();
-           block < (extent.start_block() + extent.num_blocks()); block++) {
-        ret.push_back(block);
-      }
-    }
-  }
-  return ret;
-}
-
-// Takes a vector of blocks and returns an equivalent vector of Extent
-// objects.
-vector<Extent> CompressExtents(const vector<uint64_t>& blocks) {
-  vector<Extent> new_extents;
-  for (uint64_t block : blocks) {
-    graph_utils::AppendBlockToExtents(&new_extents, block);
-  }
-  return new_extents;
-}
-
-}  // namespace
-
-void DeltaDiffGenerator::SubstituteBlocks(
-    Vertex* vertex,
-    const vector<Extent>& remove_extents,
-    const vector<Extent>& replace_extents) {
-  // First, expand out the blocks that op reads from
-  vector<uint64_t> read_blocks = ExpandExtents(vertex->op.src_extents());
-  {
-    // Expand remove_extents and replace_extents
-    vector<uint64_t> remove_extents_expanded =
-        ExpandExtents(remove_extents);
-    vector<uint64_t> replace_extents_expanded =
-        ExpandExtents(replace_extents);
-    CHECK_EQ(remove_extents_expanded.size(), replace_extents_expanded.size());
-    map<uint64_t, uint64_t> conversion;
-    for (vector<uint64_t>::size_type i = 0;
-         i < replace_extents_expanded.size(); i++) {
-      conversion[remove_extents_expanded[i]] = replace_extents_expanded[i];
-    }
-    utils::ApplyMap(&read_blocks, conversion);
-    for (auto& edge_prop_pair : vertex->out_edges) {
-      vector<uint64_t> write_before_deps_expanded =
-          ExpandExtents(edge_prop_pair.second.write_extents);
-      utils::ApplyMap(&write_before_deps_expanded, conversion);
-      edge_prop_pair.second.write_extents =
-          CompressExtents(write_before_deps_expanded);
-    }
-  }
-  // Convert read_blocks back to extents
-  vertex->op.clear_src_extents();
-  vector<Extent> new_extents = CompressExtents(read_blocks);
-  DeltaDiffGenerator::StoreExtents(new_extents,
-                                   vertex->op.mutable_src_extents());
-}
-
-bool DeltaDiffGenerator::CutEdges(Graph* graph,
-                                  const set<Edge>& edges,
-                                  vector<CutEdgeVertexes>* out_cuts) {
-  DummyExtentAllocator scratch_allocator;
-  vector<CutEdgeVertexes> cuts;
-  cuts.reserve(edges.size());
-
-  uint64_t scratch_blocks_used = 0;
-  for (const Edge& edge : edges) {
-    cuts.resize(cuts.size() + 1);
-    vector<Extent> old_extents =
-        (*graph)[edge.first].out_edges[edge.second].extents;
-    // Choose some scratch space
-    scratch_blocks_used += graph_utils::EdgeWeight(*graph, edge);
-    cuts.back().tmp_extents =
-        scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, edge));
-    // create vertex to copy original->scratch
-    cuts.back().new_vertex = graph->size();
-    graph->resize(graph->size() + 1);
-    cuts.back().old_src = edge.first;
-    cuts.back().old_dst = edge.second;
-
-    EdgeProperties& cut_edge_properties =
-        (*graph)[edge.first].out_edges.find(edge.second)->second;
-
-    // This should never happen, as we should only be cutting edges between
-    // real file nodes, and write-before relationships are created from
-    // a real file node to a temp copy node:
-    CHECK(cut_edge_properties.write_extents.empty())
-        << "Can't cut edge that has write-before relationship.";
-
-    // make node depend on the copy operation
-    (*graph)[edge.first].out_edges.insert(make_pair(graph->size() - 1,
-                                                   cut_edge_properties));
-
-    // Set src/dst extents and other proto variables for copy operation
-    graph->back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
-    DeltaDiffGenerator::StoreExtents(
-        cut_edge_properties.extents,
-        graph->back().op.mutable_src_extents());
-    DeltaDiffGenerator::StoreExtents(cuts.back().tmp_extents,
-                                     graph->back().op.mutable_dst_extents());
-    graph->back().op.set_src_length(
-        graph_utils::EdgeWeight(*graph, edge) * kBlockSize);
-    graph->back().op.set_dst_length(graph->back().op.src_length());
-
-    // make the dest node read from the scratch space
-    DeltaDiffGenerator::SubstituteBlocks(
-        &((*graph)[edge.second]),
-        (*graph)[edge.first].out_edges[edge.second].extents,
-        cuts.back().tmp_extents);
-
-    // delete the old edge
-    CHECK_EQ(static_cast<Graph::size_type>(1),
-             (*graph)[edge.first].out_edges.erase(edge.second));
-
-    // Add an edge from dst to copy operation
-    EdgeProperties write_before_edge_properties;
-    write_before_edge_properties.write_extents = cuts.back().tmp_extents;
-    (*graph)[edge.second].out_edges.insert(
-        make_pair(graph->size() - 1, write_before_edge_properties));
-  }
-  out_cuts->swap(cuts);
-  return true;
-}
-
 // Stores all Extents in 'extents' into 'out'.
 void DeltaDiffGenerator::StoreExtents(
     const vector<Extent>& extents,
@@ -1042,274 +878,6 @@
   }
 }
 
-// Creates all the edges for the graph. Writers of a block point to
-// readers of the same block. This is because for an edge A->B, B
-// must complete before A executes.
-void DeltaDiffGenerator::CreateEdges(Graph* graph,
-                                     const vector<Block>& blocks) {
-  for (vector<Block>::size_type i = 0; i < blocks.size(); i++) {
-    // Blocks with both a reader and writer get an edge
-    if (blocks[i].reader == Vertex::kInvalidIndex ||
-        blocks[i].writer == Vertex::kInvalidIndex)
-      continue;
-    // Don't have a node depend on itself
-    if (blocks[i].reader == blocks[i].writer)
-      continue;
-    // See if there's already an edge we can add onto
-    Vertex::EdgeMap::iterator edge_it =
-        (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader);
-    if (edge_it == (*graph)[blocks[i].writer].out_edges.end()) {
-      // No existing edge. Create one
-      (*graph)[blocks[i].writer].out_edges.insert(
-          make_pair(blocks[i].reader, EdgeProperties()));
-      edge_it = (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader);
-      CHECK(edge_it != (*graph)[blocks[i].writer].out_edges.end());
-    }
-    graph_utils::AppendBlockToExtents(&edge_it->second.extents, i);
-  }
-}
-
-namespace {
-
-class SortCutsByTopoOrderLess {
- public:
-  explicit SortCutsByTopoOrderLess(
-      const vector<vector<Vertex::Index>::size_type>& table)
-      : table_(table) {}
-  bool operator()(const CutEdgeVertexes& a, const CutEdgeVertexes& b) {
-    return table_[a.old_dst] < table_[b.old_dst];
-  }
- private:
-  const vector<vector<Vertex::Index>::size_type>& table_;
-};
-
-}  // namespace
-
-void DeltaDiffGenerator::GenerateReverseTopoOrderMap(
-    const vector<Vertex::Index>& op_indexes,
-    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes) {
-  vector<vector<Vertex::Index>::size_type> table(op_indexes.size());
-  for (vector<Vertex::Index>::size_type i = 0, e = op_indexes.size();
-       i != e; ++i) {
-    Vertex::Index node = op_indexes[i];
-    if (table.size() < (node + 1)) {
-      table.resize(node + 1);
-    }
-    table[node] = i;
-  }
-  reverse_op_indexes->swap(table);
-}
-
-void DeltaDiffGenerator::SortCutsByTopoOrder(
-    const vector<Vertex::Index>& op_indexes,
-    vector<CutEdgeVertexes>* cuts) {
-  // first, make a reverse lookup table.
-  vector<vector<Vertex::Index>::size_type> table;
-  GenerateReverseTopoOrderMap(op_indexes, &table);
-  SortCutsByTopoOrderLess less(table);
-  sort(cuts->begin(), cuts->end(), less);
-}
-
-void DeltaDiffGenerator::MoveFullOpsToBack(Graph* graph,
-                                           vector<Vertex::Index>* op_indexes) {
-  vector<Vertex::Index> ret;
-  vector<Vertex::Index> full_ops;
-  ret.reserve(op_indexes->size());
-  for (vector<Vertex::Index>::size_type i = 0, e = op_indexes->size(); i != e;
-       ++i) {
-    DeltaArchiveManifest_InstallOperation_Type type =
-        (*graph)[(*op_indexes)[i]].op.type();
-    if (type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
-        type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
-      full_ops.push_back((*op_indexes)[i]);
-    } else {
-      ret.push_back((*op_indexes)[i]);
-    }
-  }
-  LOG(INFO) << "Stats: " << full_ops.size() << " full ops out of "
-            << (full_ops.size() + ret.size()) << " total ops.";
-  ret.insert(ret.end(), full_ops.begin(), full_ops.end());
-  op_indexes->swap(ret);
-}
-
-namespace {
-
-template<typename T>
-bool TempBlocksExistInExtents(const T& extents) {
-  for (int i = 0, e = extents.size(); i < e; ++i) {
-    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;
-      LOG(ERROR) << "kTempBlockStart: " << kTempBlockStart;
-      LOG(ERROR) << "returning true";
-      return true;
-    }
-    // check for wrap-around, which would be a bug:
-    CHECK(start <= (start + num));
-  }
-  return false;
-}
-
-// Converts the cuts, which must all have the same |old_dst| member,
-// to full. It does this by converting the |old_dst| to REPLACE or
-// REPLACE_BZ, dropping all incoming edges to |old_dst|, and marking
-// all temp nodes invalid.
-bool ConvertCutsToFull(
-    Graph* graph,
-    const string& new_root,
-    int data_fd,
-    off_t* data_file_size,
-    vector<Vertex::Index>* op_indexes,
-    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
-    const vector<CutEdgeVertexes>& cuts) {
-  CHECK(!cuts.empty());
-  set<Vertex::Index> deleted_nodes;
-  for (const CutEdgeVertexes& cut : cuts) {
-    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ConvertCutToFullOp(
-        graph,
-        cut,
-        new_root,
-        data_fd,
-        data_file_size));
-    deleted_nodes.insert(cut.new_vertex);
-  }
-  deleted_nodes.insert(cuts[0].old_dst);
-
-  vector<Vertex::Index> new_op_indexes;
-  new_op_indexes.reserve(op_indexes->size());
-  for (Vertex::Index vertex_index : *op_indexes) {
-    if (utils::SetContainsKey(deleted_nodes, vertex_index))
-      continue;
-    new_op_indexes.push_back(vertex_index);
-  }
-  new_op_indexes.push_back(cuts[0].old_dst);
-  op_indexes->swap(new_op_indexes);
-  DeltaDiffGenerator::GenerateReverseTopoOrderMap(*op_indexes,
-                                                  reverse_op_indexes);
-  return true;
-}
-
-// Tries to assign temp blocks for a collection of cuts, all of which share
-// the same old_dst member. If temp blocks can't be found, old_dst will be
-// converted to a REPLACE or REPLACE_BZ operation. Returns true on success,
-// which can happen even if blocks are converted to full. Returns false
-// on exceptional error cases.
-bool AssignBlockForAdjoiningCuts(
-    Graph* graph,
-    const string& new_root,
-    int data_fd,
-    off_t* data_file_size,
-    vector<Vertex::Index>* op_indexes,
-    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
-    const vector<CutEdgeVertexes>& cuts) {
-  CHECK(!cuts.empty());
-  const Vertex::Index old_dst = cuts[0].old_dst;
-  // Calculate # of blocks needed
-  uint64_t blocks_needed = 0;
-  vector<uint64_t> cuts_blocks_needed(cuts.size());
-  for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
-    uint64_t cut_blocks_needed = 0;
-    for (const Extent& extent : cuts[i].tmp_extents) {
-      cut_blocks_needed += extent.num_blocks();
-    }
-    blocks_needed += cut_blocks_needed;
-    cuts_blocks_needed[i] = cut_blocks_needed;
-  }
-
-  // Find enough blocks
-  ExtentRanges scratch_ranges;
-  // Each block that's supplying temp blocks and the corresponding blocks:
-  typedef vector<pair<Vertex::Index, ExtentRanges>> SupplierVector;
-  SupplierVector block_suppliers;
-  uint64_t scratch_blocks_found = 0;
-  for (vector<Vertex::Index>::size_type i = (*reverse_op_indexes)[old_dst] + 1,
-           e = op_indexes->size(); i < e; ++i) {
-    Vertex::Index test_node = (*op_indexes)[i];
-    if (!(*graph)[test_node].valid)
-      continue;
-    // See if this node has sufficient blocks
-    ExtentRanges ranges;
-    ranges.AddRepeatedExtents((*graph)[test_node].op.dst_extents());
-    ranges.SubtractExtent(ExtentForRange(
-        kTempBlockStart, kSparseHole - kTempBlockStart));
-    ranges.SubtractRepeatedExtents((*graph)[test_node].op.src_extents());
-    // For now, for simplicity, subtract out all blocks in read-before
-    // dependencies.
-    for (Vertex::EdgeMap::const_iterator edge_i =
-             (*graph)[test_node].out_edges.begin(),
-             edge_e = (*graph)[test_node].out_edges.end();
-         edge_i != edge_e; ++edge_i) {
-      ranges.SubtractExtents(edge_i->second.extents);
-    }
-    if (ranges.blocks() == 0)
-      continue;
-
-    if (ranges.blocks() + scratch_blocks_found > blocks_needed) {
-      // trim down ranges
-      vector<Extent> new_ranges = ranges.GetExtentsForBlockCount(
-          blocks_needed - scratch_blocks_found);
-      ranges = ExtentRanges();
-      ranges.AddExtents(new_ranges);
-    }
-    scratch_ranges.AddRanges(ranges);
-    block_suppliers.push_back(make_pair(test_node, ranges));
-    scratch_blocks_found += ranges.blocks();
-    if (scratch_ranges.blocks() >= blocks_needed)
-      break;
-  }
-  if (scratch_ranges.blocks() < blocks_needed) {
-    LOG(INFO) << "Unable to find sufficient scratch";
-    TEST_AND_RETURN_FALSE(ConvertCutsToFull(graph,
-                                            new_root,
-                                            data_fd,
-                                            data_file_size,
-                                            op_indexes,
-                                            reverse_op_indexes,
-                                            cuts));
-    return true;
-  }
-  // Use the scratch we found
-  TEST_AND_RETURN_FALSE(scratch_ranges.blocks() == scratch_blocks_found);
-
-  // Make all the suppliers depend on this node
-  for (const auto& index_range_pair : block_suppliers) {
-    graph_utils::AddReadBeforeDepExtents(
-        &(*graph)[index_range_pair.first],
-        old_dst,
-        index_range_pair.second.GetExtentsForBlockCount(
-            index_range_pair.second.blocks()));
-  }
-
-  // Replace temp blocks in each cut
-  for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
-    const CutEdgeVertexes& cut = cuts[i];
-    vector<Extent> real_extents =
-        scratch_ranges.GetExtentsForBlockCount(cuts_blocks_needed[i]);
-    scratch_ranges.SubtractExtents(real_extents);
-
-    // Fix the old dest node w/ the real blocks
-    DeltaDiffGenerator::SubstituteBlocks(&(*graph)[old_dst],
-                                         cut.tmp_extents,
-                                         real_extents);
-
-    // Fix the new node w/ the real blocks. Since the new node is just a
-    // copy operation, we can replace all the dest extents w/ the real
-    // blocks.
-    DeltaArchiveManifest_InstallOperation *op = &(*graph)[cut.new_vertex].op;
-    op->clear_dst_extents();
-    DeltaDiffGenerator::StoreExtents(real_extents, op->mutable_dst_extents());
-  }
-  return true;
-}
-
-}  // namespace
-
 // Returns true if |op| is a no-op operation that doesn't do any useful work
 // (e.g., a move operation that copies blocks onto themselves).
 bool DeltaDiffGenerator::IsNoopOperation(
@@ -1318,84 +886,6 @@
           ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
 }
 
-bool DeltaDiffGenerator::AssignTempBlocks(
-    Graph* graph,
-    const string& new_root,
-    int data_fd,
-    off_t* data_file_size,
-    vector<Vertex::Index>* op_indexes,
-    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
-    const vector<CutEdgeVertexes>& cuts) {
-  CHECK(!cuts.empty());
-
-  // group of cuts w/ the same old_dst:
-  vector<CutEdgeVertexes> cuts_group;
-
-  for (vector<CutEdgeVertexes>::size_type i = cuts.size() - 1, e = 0;
-       true ; --i) {
-    LOG(INFO) << "Fixing temp blocks in cut " << i
-              << ": old dst: " << cuts[i].old_dst << " new vertex: "
-              << cuts[i].new_vertex << " path: "
-              << (*graph)[cuts[i].old_dst].file_name;
-
-    if (cuts_group.empty() || (cuts_group[0].old_dst == cuts[i].old_dst)) {
-      cuts_group.push_back(cuts[i]);
-    } else {
-      CHECK(!cuts_group.empty());
-      TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
-                                                        new_root,
-                                                        data_fd,
-                                                        data_file_size,
-                                                        op_indexes,
-                                                        reverse_op_indexes,
-                                                        cuts_group));
-      cuts_group.clear();
-      cuts_group.push_back(cuts[i]);
-    }
-
-    if (i == e) {
-      // break out of for() loop
-      break;
-    }
-  }
-  CHECK(!cuts_group.empty());
-  TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
-                                                    new_root,
-                                                    data_fd,
-                                                    data_file_size,
-                                                    op_indexes,
-                                                    reverse_op_indexes,
-                                                    cuts_group));
-  return true;
-}
-
-bool DeltaDiffGenerator::NoTempBlocksRemain(const Graph& graph) {
-  size_t idx = 0;
-  for (Graph::const_iterator it = graph.begin(), e = graph.end(); it != e;
-       ++it, ++idx) {
-    if (!it->valid)
-      continue;
-    const DeltaArchiveManifest_InstallOperation& op = it->op;
-    if (TempBlocksExistInExtents(op.dst_extents()) ||
-        TempBlocksExistInExtents(op.src_extents())) {
-      LOG(INFO) << "bad extents in node " << idx;
-      LOG(INFO) << "so yeah";
-      return false;
-    }
-
-    // Check out-edges:
-    for (const auto& edge_prop_pair : it->out_edges) {
-      if (TempBlocksExistInExtents(edge_prop_pair.second.extents) ||
-          TempBlocksExistInExtents(edge_prop_pair.second.write_extents)) {
-        LOG(INFO) << "bad out edge in node " << idx;
-        LOG(INFO) << "so yeah";
-        return false;
-      }
-    }
-  }
-  return true;
-}
-
 bool DeltaDiffGenerator::ReorderDataBlobs(
     DeltaArchiveManifest* manifest,
     const string& data_blobs_path,
@@ -1451,120 +941,6 @@
   return true;
 }
 
-bool DeltaDiffGenerator::ConvertCutToFullOp(Graph* graph,
-                                            const CutEdgeVertexes& cut,
-                                            const string& new_root,
-                                            int data_fd,
-                                            off_t* data_file_size) {
-  // Drop all incoming edges, keep all outgoing edges
-
-  // Keep all outgoing edges
-  if ((*graph)[cut.old_dst].op.type() !=
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ &&
-      (*graph)[cut.old_dst].op.type() !=
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
-    Vertex::EdgeMap out_edges = (*graph)[cut.old_dst].out_edges;
-    graph_utils::DropWriteBeforeDeps(&out_edges);
-
-    TEST_AND_RETURN_FALSE(DeltaReadFile(graph,
-                                        cut.old_dst,
-                                        nullptr,
-                                        kEmptyPath,
-                                        new_root,
-                                        (*graph)[cut.old_dst].file_name,
-                                        (*graph)[cut.old_dst].chunk_offset,
-                                        (*graph)[cut.old_dst].chunk_size,
-                                        data_fd,
-                                        data_file_size));
-
-    (*graph)[cut.old_dst].out_edges = out_edges;
-
-    // Right now we don't have doubly-linked edges, so we have to scan
-    // the whole graph.
-    graph_utils::DropIncomingEdgesTo(graph, cut.old_dst);
-  }
-
-  // Delete temp node
-  (*graph)[cut.old_src].out_edges.erase(cut.new_vertex);
-  CHECK((*graph)[cut.old_dst].out_edges.find(cut.new_vertex) ==
-        (*graph)[cut.old_dst].out_edges.end());
-  (*graph)[cut.new_vertex].valid = false;
-  LOG(INFO) << "marked node invalid: " << cut.new_vertex;
-  return true;
-}
-
-bool DeltaDiffGenerator::ConvertGraphToDag(Graph* graph,
-                                           const string& new_root,
-                                           int fd,
-                                           off_t* data_file_size,
-                                           vector<Vertex::Index>* final_order,
-                                           Vertex::Index scratch_vertex) {
-  CycleBreaker cycle_breaker;
-  LOG(INFO) << "Finding cycles...";
-  set<Edge> cut_edges;
-  cycle_breaker.BreakCycles(*graph, &cut_edges);
-  LOG(INFO) << "done finding cycles";
-  CheckGraph(*graph);
-
-  // Calculate number of scratch blocks needed
-
-  LOG(INFO) << "Cutting cycles...";
-  vector<CutEdgeVertexes> cuts;
-  TEST_AND_RETURN_FALSE(CutEdges(graph, cut_edges, &cuts));
-  LOG(INFO) << "done cutting cycles";
-  LOG(INFO) << "There are " << cuts.size() << " cuts.";
-  CheckGraph(*graph);
-
-  LOG(INFO) << "Creating initial topological order...";
-  TopologicalSort(*graph, final_order);
-  LOG(INFO) << "done with initial topo order";
-  CheckGraph(*graph);
-
-  LOG(INFO) << "Moving full ops to the back";
-  MoveFullOpsToBack(graph, final_order);
-  LOG(INFO) << "done moving full ops to back";
-
-  vector<vector<Vertex::Index>::size_type> inverse_final_order;
-  GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
-
-  SortCutsByTopoOrder(*final_order, &cuts);
-
-  if (!cuts.empty())
-    TEST_AND_RETURN_FALSE(AssignTempBlocks(graph,
-                                           new_root,
-                                           fd,
-                                           data_file_size,
-                                           final_order,
-                                           &inverse_final_order,
-                                           cuts));
-  LOG(INFO) << "Making sure all temp blocks have been allocated";
-
-  // Remove the scratch node, if any
-  if (scratch_vertex != Vertex::kInvalidIndex) {
-    final_order->erase(final_order->begin() +
-                       inverse_final_order[scratch_vertex]);
-    (*graph)[scratch_vertex].valid = false;
-    GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
-  }
-
-  graph_utils::DumpGraph(*graph);
-  CHECK(NoTempBlocksRemain(*graph));
-  LOG(INFO) << "done making sure all temp blocks are allocated";
-  return true;
-}
-
-void DeltaDiffGenerator::CreateScratchNode(uint64_t start_block,
-                                           uint64_t num_blocks,
-                                           Vertex* vertex) {
-  vertex->file_name = "<scratch>";
-  vertex->op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-  vertex->op.set_data_offset(0);
-  vertex->op.set_data_length(0);
-  Extent* extent = vertex->op.add_dst_extents();
-  extent->set_start_block(start_block);
-  extent->set_num_blocks(num_blocks);
-}
-
 bool DeltaDiffGenerator::GenerateDeltaUpdateFile(
     const string& old_root,
     const string& old_image,
@@ -1686,9 +1062,10 @@
       if (blocks.size() < (rootfs_partition_size / kBlockSize)) {
         scratch_vertex = graph.size();
         graph.resize(graph.size() + 1);
-        CreateScratchNode(blocks.size(),
-                          (rootfs_partition_size / kBlockSize) - blocks.size(),
-                          &graph.back());
+        InplaceGenerator::CreateScratchNode(
+            blocks.size(),
+            (rootfs_partition_size / kBlockSize) - blocks.size(),
+            &graph.back());
       }
 
       // Read kernel partition
@@ -1702,16 +1079,17 @@
       CheckGraph(graph);
 
       LOG(INFO) << "Creating edges...";
-      CreateEdges(&graph, blocks);
+      InplaceGenerator::CreateEdges(&graph, blocks);
       LOG(INFO) << "Done creating edges";
       CheckGraph(graph);
 
-      TEST_AND_RETURN_FALSE(ConvertGraphToDag(&graph,
-                                              new_root,
-                                              fd,
-                                              &data_file_size,
-                                              &final_order,
-                                              scratch_vertex));
+      TEST_AND_RETURN_FALSE(InplaceGenerator::ConvertGraphToDag(
+          &graph,
+          new_root,
+          fd,
+          &data_file_size,
+          &final_order,
+          scratch_vertex));
     } else {
       // Full update
       off_t new_image_size =
@@ -1890,55 +1268,6 @@
   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;
-}
-
 void DeltaDiffGenerator::AddSignatureOp(uint64_t signature_blob_offset,
                                         uint64_t signature_blob_length,
                                         DeltaArchiveManifest* manifest) {
@@ -1960,6 +1289,4 @@
                                kBlockSize);
 }
 
-const char* const kBsdiffPath = "bsdiff";
-
 };  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
index 8fc84eb..a28e1a8 100644
--- a/payload_generator/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -12,7 +12,9 @@
 #include <base/macros.h>
 #include <chromeos/secure_blob.h>
 
+#include "update_engine/payload_constants.h"
 #include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
 #include "update_engine/update_metadata.pb.h"
 
 // There is one function in DeltaDiffGenerator of importance to users
@@ -24,6 +26,10 @@
 
 namespace chromeos_update_engine {
 
+extern const char* const kEmptyPath;
+extern const size_t kBlockSize;
+extern const size_t kRootFSPartitionSize;
+
 // This struct stores all relevant info for an edge that is cut between
 // nodes old_src -> old_dst by creating new vertex new_vertex. The new
 // relationship is:
@@ -88,21 +94,24 @@
 
   // These functions are public so that the unit tests can access them:
 
-  // Takes a graph, which is not a DAG, which represents the files just
-  // read from disk, and converts it into a DAG by breaking all cycles
-  // and finding temp space to resolve broken edges.
-  // The final order of the nodes is given in |final_order|
-  // Some files may need to be reread from disk, thus |fd| and
-  // |data_file_size| are be passed.
-  // If |scratch_vertex| is not kInvalidIndex, removes it from
-  // |final_order| before returning.
-  // Returns true on success.
-  static bool ConvertGraphToDag(Graph* graph,
-                                const std::string& new_root,
-                                int fd,
-                                off_t* data_file_size,
-                                std::vector<Vertex::Index>* final_order,
-                                Vertex::Index scratch_vertex);
+  // 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
+  // necessary, if |blocks| is non-null.  Also, writes the data
+  // necessary to send the file down to the client into data_fd, which
+  // has length *data_file_size. *data_file_size is updated
+  // appropriately. If |existing_vertex| is no kInvalidIndex, use that
+  // rather than allocating a new vertex. Returns true on success.
+  static bool DeltaReadFile(Graph* graph,
+                            Vertex::Index existing_vertex,
+                            std::vector<Block>* blocks,
+                            const std::string& old_root,
+                            const std::string& new_root,
+                            const std::string& path,
+                            off_t chunk_offset,
+                            off_t chunk_size,
+                            int data_fd,
+                            off_t* data_file_size);
 
   // Reads old_filename (if it exists) and a new_filename and determines
   // the smallest way to encode this file for the diff. It stores
@@ -123,62 +132,10 @@
                              DeltaArchiveManifest_InstallOperation* out_op,
                              bool gather_extents);
 
-  // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used
-  // to provide scratch space. The node writes |num_blocks| blocks starting at
-  // |start_block|The node should be marked invalid before writing all nodes to
-  // the output file.
-  static void CreateScratchNode(uint64_t start_block,
-                                uint64_t num_blocks,
-                                Vertex* vertex);
-
-  // Modifies blocks read by 'op' so that any blocks referred to by
-  // 'remove_extents' are replaced with blocks from 'replace_extents'.
-  // 'remove_extents' and 'replace_extents' must be the same number of blocks.
-  // Blocks will be substituted in the order listed in the vectors.
-  // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents
-  // contains blocks 6, 2, 3, 5, and replace blocks contains
-  // 12, 13, 14, 15, then op will be changed to read from:
-  // 1, 13, 14, 4, 15, 12, 7, 8
-  static void SubstituteBlocks(Vertex* vertex,
-                               const std::vector<Extent>& remove_extents,
-                               const std::vector<Extent>& replace_extents);
-
-  // Cuts 'edges' from 'graph' according to the AU algorithm. This means
-  // for each edge A->B, remove the dependency that B occur before A.
-  // Do this by creating a new operation X that copies from the blocks
-  // specified by the edge's properties to temp space T. Modify B to read
-  // from T rather than the blocks in the edge. Modify A to depend on X,
-  // but not on B. Free space is found by looking in 'blocks'.
-  // Returns true on success.
-  static bool CutEdges(Graph* graph,
-                       const std::set<Edge>& edges,
-                       std::vector<CutEdgeVertexes>* out_cuts);
-
   // Stores all Extents in 'extents' into 'out'.
   static void StoreExtents(const std::vector<Extent>& extents,
                            google::protobuf::RepeatedPtrField<Extent>* out);
 
-  // Creates all the edges for the graph. Writers of a block point to
-  // readers of the same block. This is because for an edge A->B, B
-  // must complete before A executes.
-  static void CreateEdges(Graph* graph, const std::vector<Block>& blocks);
-
-  // Given a topologically sorted graph |op_indexes| and |graph|, alters
-  // |op_indexes| to move all the full operations to the end of the vector.
-  // Full operations should not be depended on, so this is safe.
-  static void MoveFullOpsToBack(Graph* graph,
-                                std::vector<Vertex::Index>* op_indexes);
-
-  // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is
-  // determined by the order of elements in op_indexes.
-  static void SortCutsByTopoOrder(
-      const std::vector<Vertex::Index>& op_indexes,
-      std::vector<CutEdgeVertexes>* cuts);
-
-  // Returns true iff there are no extents in the graph that refer to temp
-  // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole).
-  static bool NoTempBlocksRemain(const Graph& graph);
-
   // Install operations in the manifest may reference data blobs, which
   // are in data_blobs_path. This function creates a new data blobs file
   // with the data blobs in the same order as the referencing install
@@ -199,41 +156,6 @@
   static bool AddOperationHash(DeltaArchiveManifest_InstallOperation* op,
                                const chromeos::Blob& buf);
 
-  // Handles allocation of temp blocks to a cut edge by converting the
-  // dest node to a full op. This removes the need for temp blocks, but
-  // comes at the cost of a worse compression ratio.
-  // For example, say we have A->B->A. It would first be cut to form:
-  // A->B->N<-A, where N copies blocks to temp space. If there are no
-  // temp blocks, this function can be called to convert it to the form:
-  // A->B. Now, A is a full operation.
-  static bool ConvertCutToFullOp(Graph* graph,
-                                 const CutEdgeVertexes& cut,
-                                 const std::string& new_root,
-                                 int data_fd,
-                                 off_t* data_file_size);
-
-  // Takes |op_indexes|, which is effectively a mapping from order in
-  // which the op is performed -> graph vertex index, and produces the
-  // reverse: a mapping from graph vertex index -> op_indexes index.
-  static void GenerateReverseTopoOrderMap(
-      const std::vector<Vertex::Index>& op_indexes,
-      std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes);
-
-  // Takes a |graph|, which has edges that must be cut, as listed in
-  // |cuts|.  Cuts the edges. Maintains a list in which the operations
-  // will be performed (in |op_indexes|) and the reverse (in
-  // |reverse_op_indexes|).  Cutting edges requires scratch space, and
-  // if insufficient scratch is found, the file is reread and will be
-  // send down (either as REPLACE or REPLACE_BZ).  Returns true on
-  // success.
-  static bool AssignTempBlocks(
-      Graph* graph,
-      const std::string& new_root,
-      int data_fd,
-      off_t* data_file_size,
-      std::vector<Vertex::Index>* op_indexes,
-      std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes,
-      const std::vector<CutEdgeVertexes>& cuts);
 
   // Returns true if |op| is a no-op operation that doesn't do any useful work
   // (e.g., a move operation that copies blocks onto themselves).
@@ -249,33 +171,38 @@
                           const std::string& new_file,
                           chromeos::Blob* 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);
-
   // Adds to |manifest| a dummy operation that points to a signature blob
   // located at the specified offset/length.
   static void AddSignatureOp(uint64_t signature_blob_offset,
                              uint64_t signature_blob_length,
                              DeltaArchiveManifest* manifest);
 
+  // Takes a collection (vector or RepeatedPtrField) of Extent and
+  // returns a vector of the blocks referenced, in order.
+  template<typename T>
+  static std::vector<uint64_t> ExpandExtents(const T& extents) {
+    std::vector<uint64_t> ret;
+    for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) {
+      const Extent extent = graph_utils::GetElement(extents, i);
+      if (extent.start_block() == kSparseHole) {
+        ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
+      } else {
+        for (uint64_t block = extent.start_block();
+             block < (extent.start_block() + extent.num_blocks()); block++) {
+          ret.push_back(block);
+        }
+      }
+    }
+    return ret;
+  }
+
+  static void CheckGraph(const Graph& graph);
+
  private:
   // This should never be constructed.
   DISALLOW_IMPLICIT_CONSTRUCTORS(DeltaDiffGenerator);
 };
 
-extern const char* const kBsdiffPath;
-extern const size_t kRootFSPartitionSize;
-
 };  // namespace chromeos_update_engine
 
 #endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
index 88e1b75..d60aa79 100644
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -23,7 +23,6 @@
 #include "update_engine/delta_performer.h"
 #include "update_engine/extent_ranges.h"
 #include "update_engine/payload_constants.h"
-#include "update_engine/payload_generator/cycle_breaker.h"
 #include "update_engine/payload_generator/extent_mapper.h"
 #include "update_engine/payload_generator/graph_types.h"
 #include "update_engine/payload_generator/graph_utils.h"
@@ -32,12 +31,9 @@
 #include "update_engine/test_utils.h"
 #include "update_engine/utils.h"
 
-using chromeos_update_engine::test_utils::FillWithData;
 using chromeos_update_engine::test_utils::kRandomString;
-using chromeos_update_engine::test_utils::WriteFileVector;
 using std::set;
 using std::string;
-using std::stringstream;
 using std::vector;
 
 namespace chromeos_update_engine {
@@ -387,174 +383,6 @@
   EXPECT_EQ(sizeof(kRandomString), op.dst_length());
 }
 
-namespace {
-void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
-  vect->resize(vect->size() + 1);
-  vect->back().set_start_block(start);
-  vect->back().set_num_blocks(length);
-}
-void OpAppendExtent(DeltaArchiveManifest_InstallOperation* op,
-                    uint64_t start,
-                    uint64_t length) {
-  Extent* extent = op->add_src_extents();
-  extent->set_start_block(start);
-  extent->set_num_blocks(length);
-}
-}  // namespace
-
-TEST_F(DeltaDiffGeneratorTest, SubstituteBlocksTest) {
-  vector<Extent> remove_blocks;
-  AppendExtent(&remove_blocks, 3, 3);
-  AppendExtent(&remove_blocks, 7, 1);
-  vector<Extent> replace_blocks;
-  AppendExtent(&replace_blocks, 10, 2);
-  AppendExtent(&replace_blocks, 13, 2);
-  Vertex vertex;
-  DeltaArchiveManifest_InstallOperation& op = vertex.op;
-  OpAppendExtent(&op, 4, 3);
-  OpAppendExtent(&op, kSparseHole, 4);  // Sparse hole in file
-  OpAppendExtent(&op, 3, 1);
-  OpAppendExtent(&op, 7, 3);
-
-  DeltaDiffGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
-
-  EXPECT_EQ(7, op.src_extents_size());
-  EXPECT_EQ(11, op.src_extents(0).start_block());
-  EXPECT_EQ(1, op.src_extents(0).num_blocks());
-  EXPECT_EQ(13, op.src_extents(1).start_block());
-  EXPECT_EQ(1, op.src_extents(1).num_blocks());
-  EXPECT_EQ(6, op.src_extents(2).start_block());
-  EXPECT_EQ(1, op.src_extents(2).num_blocks());
-  EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
-  EXPECT_EQ(4, op.src_extents(3).num_blocks());
-  EXPECT_EQ(10, op.src_extents(4).start_block());
-  EXPECT_EQ(1, op.src_extents(4).num_blocks());
-  EXPECT_EQ(14, op.src_extents(5).start_block());
-  EXPECT_EQ(1, op.src_extents(5).num_blocks());
-  EXPECT_EQ(8, op.src_extents(6).start_block());
-  EXPECT_EQ(2, op.src_extents(6).num_blocks());
-}
-
-TEST_F(DeltaDiffGeneratorTest, CutEdgesTest) {
-  Graph graph;
-  vector<Block> blocks(9);
-
-  // Create nodes in graph
-  {
-    graph.resize(graph.size() + 1);
-    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
-    // Reads from blocks 3, 5, 7
-    vector<Extent> extents;
-    graph_utils::AppendBlockToExtents(&extents, 3);
-    graph_utils::AppendBlockToExtents(&extents, 5);
-    graph_utils::AppendBlockToExtents(&extents, 7);
-    DeltaDiffGenerator::StoreExtents(extents,
-                                     graph.back().op.mutable_src_extents());
-    blocks[3].reader = graph.size() - 1;
-    blocks[5].reader = graph.size() - 1;
-    blocks[7].reader = graph.size() - 1;
-
-    // Writes to blocks 1, 2, 4
-    extents.clear();
-    graph_utils::AppendBlockToExtents(&extents, 1);
-    graph_utils::AppendBlockToExtents(&extents, 2);
-    graph_utils::AppendBlockToExtents(&extents, 4);
-    DeltaDiffGenerator::StoreExtents(extents,
-                                     graph.back().op.mutable_dst_extents());
-    blocks[1].writer = graph.size() - 1;
-    blocks[2].writer = graph.size() - 1;
-    blocks[4].writer = graph.size() - 1;
-  }
-  {
-    graph.resize(graph.size() + 1);
-    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
-    // Reads from blocks 1, 2, 4
-    vector<Extent> extents;
-    graph_utils::AppendBlockToExtents(&extents, 1);
-    graph_utils::AppendBlockToExtents(&extents, 2);
-    graph_utils::AppendBlockToExtents(&extents, 4);
-    DeltaDiffGenerator::StoreExtents(extents,
-                                     graph.back().op.mutable_src_extents());
-    blocks[1].reader = graph.size() - 1;
-    blocks[2].reader = graph.size() - 1;
-    blocks[4].reader = graph.size() - 1;
-
-    // Writes to blocks 3, 5, 6
-    extents.clear();
-    graph_utils::AppendBlockToExtents(&extents, 3);
-    graph_utils::AppendBlockToExtents(&extents, 5);
-    graph_utils::AppendBlockToExtents(&extents, 6);
-    DeltaDiffGenerator::StoreExtents(extents,
-                                     graph.back().op.mutable_dst_extents());
-    blocks[3].writer = graph.size() - 1;
-    blocks[5].writer = graph.size() - 1;
-    blocks[6].writer = graph.size() - 1;
-  }
-
-  // Create edges
-  DeltaDiffGenerator::CreateEdges(&graph, blocks);
-
-  // Find cycles
-  CycleBreaker cycle_breaker;
-  set<Edge> cut_edges;
-  cycle_breaker.BreakCycles(graph, &cut_edges);
-
-  EXPECT_EQ(1, cut_edges.size());
-  EXPECT_TRUE(cut_edges.end() != cut_edges.find(
-      std::pair<Vertex::Index, Vertex::Index>(1, 0)));
-
-  vector<CutEdgeVertexes> cuts;
-  EXPECT_TRUE(DeltaDiffGenerator::CutEdges(&graph, cut_edges, &cuts));
-
-  EXPECT_EQ(3, graph.size());
-
-  // Check new node in graph:
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
-            graph.back().op.type());
-  EXPECT_EQ(2, graph.back().op.src_extents_size());
-  EXPECT_EQ(1, graph.back().op.dst_extents_size());
-  EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
-  EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
-  EXPECT_TRUE(graph.back().out_edges.empty());
-
-  // Check that old node reads from new blocks
-  EXPECT_EQ(2, graph[0].op.src_extents_size());
-  EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
-  EXPECT_EQ(2, graph[0].op.src_extents(0).num_blocks());
-  EXPECT_EQ(7, graph[0].op.src_extents(1).start_block());
-  EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks());
-
-  // And that the old dst extents haven't changed
-  EXPECT_EQ(2, graph[0].op.dst_extents_size());
-  EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block());
-  EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks());
-  EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block());
-  EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks());
-
-  // Ensure it only depends on the next node and the new temp node
-  EXPECT_EQ(2, graph[0].out_edges.size());
-  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
-  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
-                                                                  1));
-
-  // Check second node has unchanged extents
-  EXPECT_EQ(2, graph[1].op.src_extents_size());
-  EXPECT_EQ(1, graph[1].op.src_extents(0).start_block());
-  EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks());
-  EXPECT_EQ(4, graph[1].op.src_extents(1).start_block());
-  EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks());
-
-  EXPECT_EQ(2, graph[1].op.dst_extents_size());
-  EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block());
-  EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
-  EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
-  EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
-
-  // Ensure it only depends on the next node
-  EXPECT_EQ(1, graph[1].out_edges.size());
-  EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
-}
-
 TEST_F(DeltaDiffGeneratorTest, ReorderBlobsTest) {
   string orig_blobs;
   EXPECT_TRUE(utils::MakeTempFile("ReorderBlobsTest.orig.XXXXXX", &orig_blobs,
@@ -594,395 +422,6 @@
   unlink(new_blobs.c_str());
 }
 
-TEST_F(DeltaDiffGeneratorTest, MoveFullOpsToBackTest) {
-  Graph graph(4);
-  graph[0].file_name = "A";
-  graph[0].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-  graph[1].file_name = "B";
-  graph[1].op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
-  graph[2].file_name = "C";
-  graph[2].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-  graph[3].file_name = "D";
-  graph[3].op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
-
-  vector<Vertex::Index> vect(graph.size());
-
-  for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
-    vect[i] = i;
-  }
-  DeltaDiffGenerator::MoveFullOpsToBack(&graph, &vect);
-  EXPECT_EQ(vect.size(), graph.size());
-  EXPECT_EQ(graph[vect[0]].file_name, "B");
-  EXPECT_EQ(graph[vect[1]].file_name, "D");
-  EXPECT_EQ(graph[vect[2]].file_name, "A");
-  EXPECT_EQ(graph[vect[3]].file_name, "C");
-}
-
-namespace {
-
-#define OP_BSDIFF DeltaArchiveManifest_InstallOperation_Type_BSDIFF
-#define OP_MOVE DeltaArchiveManifest_InstallOperation_Type_MOVE
-#define OP_REPLACE DeltaArchiveManifest_InstallOperation_Type_REPLACE
-#define OP_REPLACE_BZ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ
-
-void GenVertex(Vertex* out,
-               const vector<Extent>& src_extents,
-               const vector<Extent>& dst_extents,
-               const string& path,
-               DeltaArchiveManifest_InstallOperation_Type type) {
-  out->op.set_type(type);
-  out->file_name = path;
-  DeltaDiffGenerator::StoreExtents(src_extents, out->op.mutable_src_extents());
-  DeltaDiffGenerator::StoreExtents(dst_extents, out->op.mutable_dst_extents());
-}
-
-vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
-  return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
-}
-
-EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
-  EdgeProperties ret;
-  ret.extents = extents;
-  return ret;
-}
-
-EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
-  EdgeProperties ret;
-  ret.write_extents = extents;
-  return ret;
-}
-
-template<typename T>
-void DumpVect(const vector<T>& vect) {
-  stringstream ss(stringstream::out);
-  for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
-       it != e; ++it) {
-    ss << *it << ", ";
-  }
-  LOG(INFO) << "{" << ss.str() << "}";
-}
-
-}  // namespace
-
-TEST_F(DeltaDiffGeneratorTest, RunAsRootAssignTempBlocksTest) {
-  Graph graph(9);
-  const vector<Extent> empt;  // empty
-  const string kFilename = "/foo";
-
-  // Some scratch space:
-  GenVertex(&graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
-  GenVertex(&graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
-  GenVertex(&graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
-
-  // A cycle that requires 10 blocks to break:
-  GenVertex(&graph[3], VectOfExt(10, 11), VectOfExt(0, 9), "", OP_BSDIFF);
-  graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
-  GenVertex(&graph[4], VectOfExt(0, 9), VectOfExt(10, 11), "", OP_BSDIFF);
-  graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
-
-  // A cycle that requires 9 blocks to break:
-  GenVertex(&graph[5], VectOfExt(40, 11), VectOfExt(30, 10), "", OP_BSDIFF);
-  graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
-  GenVertex(&graph[6], VectOfExt(30, 10), VectOfExt(40, 11), "", OP_BSDIFF);
-  graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
-
-  // A cycle that requires 40 blocks to break (which is too many):
-  GenVertex(&graph[7],
-            VectOfExt(120, 50),
-            VectOfExt(60, 40),
-            "",
-            OP_BSDIFF);
-  graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
-  GenVertex(&graph[8],
-            VectOfExt(60, 40),
-            VectOfExt(120, 50),
-            kFilename,
-            OP_BSDIFF);
-  graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
-
-  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("AssignTempBlocksTest.XXXXXX",
-                                       &temp_dir));
-  ScopedDirRemover temp_dir_remover(temp_dir);
-
-  const size_t kBlockSize = 4096;
-  chromeos::Blob temp_data(kBlockSize * 50);
-  FillWithData(&temp_data);
-  EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
-  ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
-
-  int fd;
-  EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksTestData.XXXXXX",
-                                  nullptr,
-                                  &fd));
-  ScopedFdCloser fd_closer(&fd);
-  off_t data_file_size = 0;
-
-
-  EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
-                                                    temp_dir,
-                                                    fd,
-                                                    &data_file_size,
-                                                    &final_order,
-                                                    Vertex::kInvalidIndex));
-
-
-  Graph expected_graph(12);
-  GenVertex(&expected_graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
-  GenVertex(&expected_graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
-  GenVertex(&expected_graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
-  GenVertex(&expected_graph[3],
-            VectOfExt(10, 11),
-            VectOfExt(0, 9),
-            "",
-            OP_BSDIFF);
-  expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
-  GenVertex(&expected_graph[4],
-            VectOfExt(60, 9),
-            VectOfExt(10, 11),
-            "",
-            OP_BSDIFF);
-  expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
-  expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
-  GenVertex(&expected_graph[5],
-            VectOfExt(40, 11),
-            VectOfExt(30, 10),
-            "",
-            OP_BSDIFF);
-  expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
-
-  GenVertex(&expected_graph[6],
-            VectOfExt(60, 10),
-            VectOfExt(40, 11),
-            "",
-            OP_BSDIFF);
-  expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
-  expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
-
-  GenVertex(&expected_graph[7],
-            VectOfExt(120, 50),
-            VectOfExt(60, 40),
-            "",
-            OP_BSDIFF);
-  expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
-
-  GenVertex(&expected_graph[8], empt, VectOfExt(0, 50), "/foo", OP_REPLACE_BZ);
-  expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
-
-  GenVertex(&expected_graph[9],
-            VectOfExt(0, 9),
-            VectOfExt(60, 9),
-            "",
-            OP_MOVE);
-
-  GenVertex(&expected_graph[10],
-            VectOfExt(30, 10),
-            VectOfExt(60, 10),
-            "",
-            OP_MOVE);
-  expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
-
-  EXPECT_EQ(12, graph.size());
-  EXPECT_FALSE(graph.back().valid);
-  for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
-    EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
-    if (i == 8) {
-      // special case
-    } else {
-      // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
-    }
-  }
-}
-
-// 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(DeltaDiffGeneratorTest, 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);
-
-  const size_t kBlockSize = 4096;
-  chromeos::Blob temp_data(kBlockSize);
-  FillWithData(&temp_data);
-  EXPECT_TRUE(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(DeltaDiffGenerator::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(DeltaDiffGeneratorTest, 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
-  DeltaDiffGenerator::CreateEdges(&graph, blocks);
-
-  graph_utils::DumpGraph(graph);
-
-  vector<Vertex::Index> final_order;
-  off_t data_file_size = 0;
-  EXPECT_TRUE(DeltaDiffGenerator::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(DeltaDiffGeneratorTest, IsNoopOperationTest) {
   DeltaArchiveManifest_InstallOperation op;
@@ -1009,124 +448,4 @@
   EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
 }
 
-TEST_F(DeltaDiffGeneratorTest, RunAsRootAssignTempBlocksReuseTest) {
-  // AssignTempBlocks(Graph* graph,
-  // const string& new_root,
-  // int data_fd,
-  // off_t* data_file_size,
-  // vector<Vertex::Index>* op_indexes,
-  // vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
-  // const vector<CutEdgeVertexes>& cuts
-  Graph graph(9);
-
-  const vector<Extent> empt;
-  uint64_t tmp = kTempBlockStart;
-  const string kFilename = "/foo";
-
-  vector<CutEdgeVertexes> cuts;
-  cuts.resize(3);
-
-  // Simple broken loop:
-  GenVertex(&graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_MOVE);
-  GenVertex(&graph[1], VectOfExt(tmp, 1), VectOfExt(0, 1), "", OP_MOVE);
-  GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(tmp, 1), "", OP_MOVE);
-  // Corresponding edges:
-  graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
-  graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
-  graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
-  // Store the cut:
-  cuts[0].old_dst = 1;
-  cuts[0].old_src = 0;
-  cuts[0].new_vertex = 2;
-  cuts[0].tmp_extents = VectOfExt(tmp, 1);
-  tmp++;
-
-  // Slightly more complex pair of loops:
-  GenVertex(&graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", OP_MOVE);
-  GenVertex(&graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", OP_MOVE);
-  GenVertex(&graph[5], VectOfExt(tmp, 3), VectOfExt(4, 3), kFilename, OP_MOVE);
-  GenVertex(&graph[6], VectOfExt(2, 2), VectOfExt(tmp, 2), "", OP_MOVE);
-  GenVertex(&graph[7], VectOfExt(7, 1), VectOfExt(tmp + 2, 1), "", OP_MOVE);
-  // Corresponding edges:
-  graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
-  graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
-  graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
-  graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
-  graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
-  graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
-  // Store the cuts:
-  cuts[1].old_dst = 5;
-  cuts[1].old_src = 3;
-  cuts[1].new_vertex = 6;
-  cuts[1].tmp_extents = VectOfExt(tmp, 2);
-  cuts[2].old_dst = 5;
-  cuts[2].old_src = 4;
-  cuts[2].new_vertex = 7;
-  cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
-
-  // Supplier of temp block:
-  GenVertex(&graph[8], empt, VectOfExt(8, 1), "", OP_REPLACE);
-
-  // Specify the final order:
-  vector<Vertex::Index> op_indexes;
-  op_indexes.push_back(2);
-  op_indexes.push_back(0);
-  op_indexes.push_back(1);
-  op_indexes.push_back(6);
-  op_indexes.push_back(3);
-  op_indexes.push_back(7);
-  op_indexes.push_back(4);
-  op_indexes.push_back(5);
-  op_indexes.push_back(8);
-
-  vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
-  DeltaDiffGenerator::GenerateReverseTopoOrderMap(op_indexes,
-                                                  &reverse_op_indexes);
-
-  // Prepare the filesystem with the minimum required for this to work
-  string temp_dir;
-  EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksReuseTest.XXXXXX",
-                                       &temp_dir));
-  ScopedDirRemover temp_dir_remover(temp_dir);
-
-  const size_t kBlockSize = 4096;
-  chromeos::Blob temp_data(kBlockSize * 3);
-  FillWithData(&temp_data);
-  EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
-  ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
-
-  int fd;
-  EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksReuseTest.XXXXXX",
-                                  nullptr,
-                                  &fd));
-  ScopedFdCloser fd_closer(&fd);
-  off_t data_file_size = 0;
-
-  EXPECT_TRUE(DeltaDiffGenerator::AssignTempBlocks(&graph,
-                                                   temp_dir,
-                                                   fd,
-                                                   &data_file_size,
-                                                   &op_indexes,
-                                                   &reverse_op_indexes,
-                                                   cuts));
-  EXPECT_FALSE(graph[6].valid);
-  EXPECT_FALSE(graph[7].valid);
-  EXPECT_EQ(1, graph[1].op.src_extents_size());
-  EXPECT_EQ(2, graph[1].op.src_extents(0).start_block());
-  EXPECT_EQ(1, graph[1].op.src_extents(0).num_blocks());
-  EXPECT_EQ(OP_REPLACE_BZ, graph[5].op.type());
-}
-
-TEST_F(DeltaDiffGeneratorTest, CreateScratchNodeTest) {
-  Vertex vertex;
-  DeltaDiffGenerator::CreateScratchNode(12, 34, &vertex);
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
-            vertex.op.type());
-  EXPECT_EQ(0, vertex.op.data_offset());
-  EXPECT_EQ(0, vertex.op.data_length());
-  EXPECT_EQ(1, vertex.op.dst_extents_size());
-  EXPECT_EQ(12, vertex.op.dst_extents(0).start_block());
-  EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
-}
-
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
new file mode 100644
index 0000000..0567b62
--- /dev/null
+++ b/payload_generator/inplace_generator.cc
@@ -0,0 +1,677 @@
+// Copyright 2015 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 "update_engine/payload_generator/inplace_generator.h"
+
+#include <algorithm>
+#include <map>
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/cycle_breaker.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/topological_sort.h"
+#include "update_engine/update_metadata.pb.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::map;
+using std::pair;
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+using Block = DeltaDiffGenerator::Block;
+
+// This class allocates non-existent temp blocks, starting from
+// kTempBlockStart. Other code is responsible for converting these
+// temp blocks into real blocks, as the client can't read or write to
+// these blocks.
+class DummyExtentAllocator {
+ public:
+  vector<Extent> Allocate(const uint64_t block_count) {
+    vector<Extent> ret(1);
+    ret[0].set_start_block(next_block_);
+    ret[0].set_num_blocks(block_count);
+    next_block_ += block_count;
+    return ret;
+  }
+
+ private:
+  uint64_t next_block_{kTempBlockStart};
+};
+
+// Takes a vector of blocks and returns an equivalent vector of Extent
+// objects.
+vector<Extent> CompressExtents(const vector<uint64_t>& blocks) {
+  vector<Extent> new_extents;
+  for (uint64_t block : blocks) {
+    graph_utils::AppendBlockToExtents(&new_extents, block);
+  }
+  return new_extents;
+}
+
+void InplaceGenerator::SubstituteBlocks(
+    Vertex* vertex,
+    const vector<Extent>& remove_extents,
+    const vector<Extent>& replace_extents) {
+  // First, expand out the blocks that op reads from
+  vector<uint64_t> read_blocks =
+      DeltaDiffGenerator::ExpandExtents(vertex->op.src_extents());
+  {
+    // Expand remove_extents and replace_extents
+    vector<uint64_t> remove_extents_expanded =
+        DeltaDiffGenerator::ExpandExtents(remove_extents);
+    vector<uint64_t> replace_extents_expanded =
+        DeltaDiffGenerator::ExpandExtents(replace_extents);
+    CHECK_EQ(remove_extents_expanded.size(), replace_extents_expanded.size());
+    map<uint64_t, uint64_t> conversion;
+    for (vector<uint64_t>::size_type i = 0;
+         i < replace_extents_expanded.size(); i++) {
+      conversion[remove_extents_expanded[i]] = replace_extents_expanded[i];
+    }
+    utils::ApplyMap(&read_blocks, conversion);
+    for (auto& edge_prop_pair : vertex->out_edges) {
+      vector<uint64_t> write_before_deps_expanded =
+          DeltaDiffGenerator::ExpandExtents(
+              edge_prop_pair.second.write_extents);
+      utils::ApplyMap(&write_before_deps_expanded, conversion);
+      edge_prop_pair.second.write_extents =
+          CompressExtents(write_before_deps_expanded);
+    }
+  }
+  // Convert read_blocks back to extents
+  vertex->op.clear_src_extents();
+  vector<Extent> new_extents = CompressExtents(read_blocks);
+  DeltaDiffGenerator::StoreExtents(new_extents,
+                                   vertex->op.mutable_src_extents());
+}
+
+bool InplaceGenerator::CutEdges(Graph* graph,
+                                const set<Edge>& edges,
+                                vector<CutEdgeVertexes>* out_cuts) {
+  DummyExtentAllocator scratch_allocator;
+  vector<CutEdgeVertexes> cuts;
+  cuts.reserve(edges.size());
+
+  uint64_t scratch_blocks_used = 0;
+  for (const Edge& edge : edges) {
+    cuts.resize(cuts.size() + 1);
+    vector<Extent> old_extents =
+        (*graph)[edge.first].out_edges[edge.second].extents;
+    // Choose some scratch space
+    scratch_blocks_used += graph_utils::EdgeWeight(*graph, edge);
+    cuts.back().tmp_extents =
+        scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, edge));
+    // create vertex to copy original->scratch
+    cuts.back().new_vertex = graph->size();
+    graph->resize(graph->size() + 1);
+    cuts.back().old_src = edge.first;
+    cuts.back().old_dst = edge.second;
+
+    EdgeProperties& cut_edge_properties =
+        (*graph)[edge.first].out_edges.find(edge.second)->second;
+
+    // This should never happen, as we should only be cutting edges between
+    // real file nodes, and write-before relationships are created from
+    // a real file node to a temp copy node:
+    CHECK(cut_edge_properties.write_extents.empty())
+        << "Can't cut edge that has write-before relationship.";
+
+    // make node depend on the copy operation
+    (*graph)[edge.first].out_edges.insert(make_pair(graph->size() - 1,
+                                                    cut_edge_properties));
+
+    // Set src/dst extents and other proto variables for copy operation
+    graph->back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+    DeltaDiffGenerator::StoreExtents(
+        cut_edge_properties.extents,
+        graph->back().op.mutable_src_extents());
+    DeltaDiffGenerator::StoreExtents(cuts.back().tmp_extents,
+                                     graph->back().op.mutable_dst_extents());
+    graph->back().op.set_src_length(
+        graph_utils::EdgeWeight(*graph, edge) * kBlockSize);
+    graph->back().op.set_dst_length(graph->back().op.src_length());
+
+    // make the dest node read from the scratch space
+    SubstituteBlocks(
+        &((*graph)[edge.second]),
+        (*graph)[edge.first].out_edges[edge.second].extents,
+        cuts.back().tmp_extents);
+
+    // delete the old edge
+    CHECK_EQ(static_cast<Graph::size_type>(1),
+             (*graph)[edge.first].out_edges.erase(edge.second));
+
+    // Add an edge from dst to copy operation
+    EdgeProperties write_before_edge_properties;
+    write_before_edge_properties.write_extents = cuts.back().tmp_extents;
+    (*graph)[edge.second].out_edges.insert(
+        make_pair(graph->size() - 1, write_before_edge_properties));
+  }
+  out_cuts->swap(cuts);
+  return true;
+}
+
+// Creates all the edges for the graph. Writers of a block point to
+// readers of the same block. This is because for an edge A->B, B
+// must complete before A executes.
+void InplaceGenerator::CreateEdges(
+    Graph* graph,
+    const vector<DeltaDiffGenerator::Block>& blocks) {
+  for (vector<DeltaDiffGenerator::Block>::size_type i = 0;
+       i < blocks.size(); i++) {
+    // Blocks with both a reader and writer get an edge
+    if (blocks[i].reader == Vertex::kInvalidIndex ||
+        blocks[i].writer == Vertex::kInvalidIndex)
+      continue;
+    // Don't have a node depend on itself
+    if (blocks[i].reader == blocks[i].writer)
+      continue;
+    // See if there's already an edge we can add onto
+    Vertex::EdgeMap::iterator edge_it =
+        (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader);
+    if (edge_it == (*graph)[blocks[i].writer].out_edges.end()) {
+      // No existing edge. Create one
+      (*graph)[blocks[i].writer].out_edges.insert(
+          make_pair(blocks[i].reader, EdgeProperties()));
+      edge_it = (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader);
+      CHECK(edge_it != (*graph)[blocks[i].writer].out_edges.end());
+    }
+    graph_utils::AppendBlockToExtents(&edge_it->second.extents, i);
+  }
+}
+
+namespace {
+
+class SortCutsByTopoOrderLess {
+ public:
+  explicit SortCutsByTopoOrderLess(
+      const vector<vector<Vertex::Index>::size_type>& table)
+      : table_(table) {}
+  bool operator()(const CutEdgeVertexes& a, const CutEdgeVertexes& b) {
+    return table_[a.old_dst] < table_[b.old_dst];
+  }
+ private:
+  const vector<vector<Vertex::Index>::size_type>& table_;
+};
+
+}  // namespace
+
+void InplaceGenerator::GenerateReverseTopoOrderMap(
+    const vector<Vertex::Index>& op_indexes,
+    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes) {
+  vector<vector<Vertex::Index>::size_type> table(op_indexes.size());
+  for (vector<Vertex::Index>::size_type i = 0, e = op_indexes.size();
+       i != e; ++i) {
+    Vertex::Index node = op_indexes[i];
+    if (table.size() < (node + 1)) {
+      table.resize(node + 1);
+    }
+    table[node] = i;
+  }
+  reverse_op_indexes->swap(table);
+}
+
+void InplaceGenerator::SortCutsByTopoOrder(
+    const vector<Vertex::Index>& op_indexes,
+    vector<CutEdgeVertexes>* cuts) {
+  // first, make a reverse lookup table.
+  vector<vector<Vertex::Index>::size_type> table;
+  GenerateReverseTopoOrderMap(op_indexes, &table);
+  SortCutsByTopoOrderLess less(table);
+  sort(cuts->begin(), cuts->end(), less);
+}
+
+void InplaceGenerator::MoveFullOpsToBack(Graph* graph,
+                                         vector<Vertex::Index>* op_indexes) {
+  vector<Vertex::Index> ret;
+  vector<Vertex::Index> full_ops;
+  ret.reserve(op_indexes->size());
+  for (vector<Vertex::Index>::size_type i = 0, e = op_indexes->size(); i != e;
+       ++i) {
+    DeltaArchiveManifest_InstallOperation_Type type =
+        (*graph)[(*op_indexes)[i]].op.type();
+    if (type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+        type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+      full_ops.push_back((*op_indexes)[i]);
+    } else {
+      ret.push_back((*op_indexes)[i]);
+    }
+  }
+  LOG(INFO) << "Stats: " << full_ops.size() << " full ops out of "
+            << (full_ops.size() + ret.size()) << " total ops.";
+  ret.insert(ret.end(), full_ops.begin(), full_ops.end());
+  op_indexes->swap(ret);
+}
+
+namespace {
+
+template<typename T>
+bool TempBlocksExistInExtents(const T& extents) {
+  for (int i = 0, e = extents.size(); i < e; ++i) {
+    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;
+      LOG(ERROR) << "kTempBlockStart: " << kTempBlockStart;
+      LOG(ERROR) << "returning true";
+      return true;
+    }
+    // check for wrap-around, which would be a bug:
+    CHECK(start <= (start + num));
+  }
+  return false;
+}
+
+// Converts the cuts, which must all have the same |old_dst| member,
+// to full. It does this by converting the |old_dst| to REPLACE or
+// REPLACE_BZ, dropping all incoming edges to |old_dst|, and marking
+// all temp nodes invalid.
+bool ConvertCutsToFull(
+    Graph* graph,
+    const string& new_root,
+    int data_fd,
+    off_t* data_file_size,
+    vector<Vertex::Index>* op_indexes,
+    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+    const vector<CutEdgeVertexes>& cuts) {
+  CHECK(!cuts.empty());
+  set<Vertex::Index> deleted_nodes;
+  for (const CutEdgeVertexes& cut : cuts) {
+    TEST_AND_RETURN_FALSE(InplaceGenerator::ConvertCutToFullOp(
+        graph,
+        cut,
+        new_root,
+        data_fd,
+        data_file_size));
+    deleted_nodes.insert(cut.new_vertex);
+  }
+  deleted_nodes.insert(cuts[0].old_dst);
+
+  vector<Vertex::Index> new_op_indexes;
+  new_op_indexes.reserve(op_indexes->size());
+  for (Vertex::Index vertex_index : *op_indexes) {
+    if (utils::SetContainsKey(deleted_nodes, vertex_index))
+      continue;
+    new_op_indexes.push_back(vertex_index);
+  }
+  new_op_indexes.push_back(cuts[0].old_dst);
+  op_indexes->swap(new_op_indexes);
+  InplaceGenerator::GenerateReverseTopoOrderMap(*op_indexes,
+                                                reverse_op_indexes);
+  return true;
+}
+
+// Tries to assign temp blocks for a collection of cuts, all of which share
+// the same old_dst member. If temp blocks can't be found, old_dst will be
+// converted to a REPLACE or REPLACE_BZ operation. Returns true on success,
+// which can happen even if blocks are converted to full. Returns false
+// on exceptional error cases.
+bool AssignBlockForAdjoiningCuts(
+    Graph* graph,
+    const string& new_root,
+    int data_fd,
+    off_t* data_file_size,
+    vector<Vertex::Index>* op_indexes,
+    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+    const vector<CutEdgeVertexes>& cuts) {
+  CHECK(!cuts.empty());
+  const Vertex::Index old_dst = cuts[0].old_dst;
+  // Calculate # of blocks needed
+  uint64_t blocks_needed = 0;
+  vector<uint64_t> cuts_blocks_needed(cuts.size());
+  for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
+    uint64_t cut_blocks_needed = 0;
+    for (const Extent& extent : cuts[i].tmp_extents) {
+      cut_blocks_needed += extent.num_blocks();
+    }
+    blocks_needed += cut_blocks_needed;
+    cuts_blocks_needed[i] = cut_blocks_needed;
+  }
+
+  // Find enough blocks
+  ExtentRanges scratch_ranges;
+  // Each block that's supplying temp blocks and the corresponding blocks:
+  typedef vector<pair<Vertex::Index, ExtentRanges>> SupplierVector;
+  SupplierVector block_suppliers;
+  uint64_t scratch_blocks_found = 0;
+  for (vector<Vertex::Index>::size_type i = (*reverse_op_indexes)[old_dst] + 1,
+           e = op_indexes->size(); i < e; ++i) {
+    Vertex::Index test_node = (*op_indexes)[i];
+    if (!(*graph)[test_node].valid)
+      continue;
+    // See if this node has sufficient blocks
+    ExtentRanges ranges;
+    ranges.AddRepeatedExtents((*graph)[test_node].op.dst_extents());
+    ranges.SubtractExtent(ExtentForRange(
+        kTempBlockStart, kSparseHole - kTempBlockStart));
+    ranges.SubtractRepeatedExtents((*graph)[test_node].op.src_extents());
+    // For now, for simplicity, subtract out all blocks in read-before
+    // dependencies.
+    for (Vertex::EdgeMap::const_iterator edge_i =
+             (*graph)[test_node].out_edges.begin(),
+             edge_e = (*graph)[test_node].out_edges.end();
+         edge_i != edge_e; ++edge_i) {
+      ranges.SubtractExtents(edge_i->second.extents);
+    }
+    if (ranges.blocks() == 0)
+      continue;
+
+    if (ranges.blocks() + scratch_blocks_found > blocks_needed) {
+      // trim down ranges
+      vector<Extent> new_ranges = ranges.GetExtentsForBlockCount(
+          blocks_needed - scratch_blocks_found);
+      ranges = ExtentRanges();
+      ranges.AddExtents(new_ranges);
+    }
+    scratch_ranges.AddRanges(ranges);
+    block_suppliers.push_back(make_pair(test_node, ranges));
+    scratch_blocks_found += ranges.blocks();
+    if (scratch_ranges.blocks() >= blocks_needed)
+      break;
+  }
+  if (scratch_ranges.blocks() < blocks_needed) {
+    LOG(INFO) << "Unable to find sufficient scratch";
+    TEST_AND_RETURN_FALSE(ConvertCutsToFull(graph,
+                                            new_root,
+                                            data_fd,
+                                            data_file_size,
+                                            op_indexes,
+                                            reverse_op_indexes,
+                                            cuts));
+    return true;
+  }
+  // Use the scratch we found
+  TEST_AND_RETURN_FALSE(scratch_ranges.blocks() == scratch_blocks_found);
+
+  // Make all the suppliers depend on this node
+  for (const auto& index_range_pair : block_suppliers) {
+    graph_utils::AddReadBeforeDepExtents(
+        &(*graph)[index_range_pair.first],
+        old_dst,
+        index_range_pair.second.GetExtentsForBlockCount(
+            index_range_pair.second.blocks()));
+  }
+
+  // Replace temp blocks in each cut
+  for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
+    const CutEdgeVertexes& cut = cuts[i];
+    vector<Extent> real_extents =
+        scratch_ranges.GetExtentsForBlockCount(cuts_blocks_needed[i]);
+    scratch_ranges.SubtractExtents(real_extents);
+
+    // Fix the old dest node w/ the real blocks
+    InplaceGenerator::SubstituteBlocks(&(*graph)[old_dst],
+                                         cut.tmp_extents,
+                                         real_extents);
+
+    // Fix the new node w/ the real blocks. Since the new node is just a
+    // copy operation, we can replace all the dest extents w/ the real
+    // blocks.
+    DeltaArchiveManifest_InstallOperation *op = &(*graph)[cut.new_vertex].op;
+    op->clear_dst_extents();
+    DeltaDiffGenerator::StoreExtents(real_extents, op->mutable_dst_extents());
+  }
+  return true;
+}
+
+}  // namespace
+
+bool InplaceGenerator::AssignTempBlocks(
+    Graph* graph,
+    const string& new_root,
+    int data_fd,
+    off_t* data_file_size,
+    vector<Vertex::Index>* op_indexes,
+    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+    const vector<CutEdgeVertexes>& cuts) {
+  CHECK(!cuts.empty());
+
+  // group of cuts w/ the same old_dst:
+  vector<CutEdgeVertexes> cuts_group;
+
+  for (vector<CutEdgeVertexes>::size_type i = cuts.size() - 1, e = 0;
+       true ; --i) {
+    LOG(INFO) << "Fixing temp blocks in cut " << i
+              << ": old dst: " << cuts[i].old_dst << " new vertex: "
+              << cuts[i].new_vertex << " path: "
+              << (*graph)[cuts[i].old_dst].file_name;
+
+    if (cuts_group.empty() || (cuts_group[0].old_dst == cuts[i].old_dst)) {
+      cuts_group.push_back(cuts[i]);
+    } else {
+      CHECK(!cuts_group.empty());
+      TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
+                                                        new_root,
+                                                        data_fd,
+                                                        data_file_size,
+                                                        op_indexes,
+                                                        reverse_op_indexes,
+                                                        cuts_group));
+      cuts_group.clear();
+      cuts_group.push_back(cuts[i]);
+    }
+
+    if (i == e) {
+      // break out of for() loop
+      break;
+    }
+  }
+  CHECK(!cuts_group.empty());
+  TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
+                                                    new_root,
+                                                    data_fd,
+                                                    data_file_size,
+                                                    op_indexes,
+                                                    reverse_op_indexes,
+                                                    cuts_group));
+  return true;
+}
+
+bool InplaceGenerator::NoTempBlocksRemain(const Graph& graph) {
+  size_t idx = 0;
+  for (Graph::const_iterator it = graph.begin(), e = graph.end(); it != e;
+       ++it, ++idx) {
+    if (!it->valid)
+      continue;
+    const DeltaArchiveManifest_InstallOperation& op = it->op;
+    if (TempBlocksExistInExtents(op.dst_extents()) ||
+        TempBlocksExistInExtents(op.src_extents())) {
+      LOG(INFO) << "bad extents in node " << idx;
+      LOG(INFO) << "so yeah";
+      return false;
+    }
+
+    // Check out-edges:
+    for (const auto& edge_prop_pair : it->out_edges) {
+      if (TempBlocksExistInExtents(edge_prop_pair.second.extents) ||
+          TempBlocksExistInExtents(edge_prop_pair.second.write_extents)) {
+        LOG(INFO) << "bad out edge in node " << idx;
+        LOG(INFO) << "so yeah";
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
+bool InplaceGenerator::ConvertCutToFullOp(Graph* graph,
+                                          const CutEdgeVertexes& cut,
+                                          const string& new_root,
+                                          int data_fd,
+                                          off_t* data_file_size) {
+  // Drop all incoming edges, keep all outgoing edges
+
+  // Keep all outgoing edges
+  if ((*graph)[cut.old_dst].op.type() !=
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ &&
+      (*graph)[cut.old_dst].op.type() !=
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+    Vertex::EdgeMap out_edges = (*graph)[cut.old_dst].out_edges;
+    graph_utils::DropWriteBeforeDeps(&out_edges);
+
+    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::DeltaReadFile(
+        graph,
+        cut.old_dst,
+        nullptr,
+        kEmptyPath,
+        new_root,
+        (*graph)[cut.old_dst].file_name,
+        (*graph)[cut.old_dst].chunk_offset,
+        (*graph)[cut.old_dst].chunk_size,
+        data_fd,
+        data_file_size));
+
+    (*graph)[cut.old_dst].out_edges = out_edges;
+
+    // Right now we don't have doubly-linked edges, so we have to scan
+    // the whole graph.
+    graph_utils::DropIncomingEdgesTo(graph, cut.old_dst);
+  }
+
+  // Delete temp node
+  (*graph)[cut.old_src].out_edges.erase(cut.new_vertex);
+  CHECK((*graph)[cut.old_dst].out_edges.find(cut.new_vertex) ==
+        (*graph)[cut.old_dst].out_edges.end());
+  (*graph)[cut.new_vertex].valid = false;
+  LOG(INFO) << "marked node invalid: " << cut.new_vertex;
+  return true;
+}
+
+bool InplaceGenerator::ConvertGraphToDag(Graph* graph,
+                                        const string& new_root,
+                                        int fd,
+                                        off_t* data_file_size,
+                                        vector<Vertex::Index>* final_order,
+                                        Vertex::Index scratch_vertex) {
+  CycleBreaker cycle_breaker;
+  LOG(INFO) << "Finding cycles...";
+  set<Edge> cut_edges;
+  cycle_breaker.BreakCycles(*graph, &cut_edges);
+  LOG(INFO) << "done finding cycles";
+  DeltaDiffGenerator::CheckGraph(*graph);
+
+  // Calculate number of scratch blocks needed
+
+  LOG(INFO) << "Cutting cycles...";
+  vector<CutEdgeVertexes> cuts;
+  TEST_AND_RETURN_FALSE(CutEdges(graph, cut_edges, &cuts));
+  LOG(INFO) << "done cutting cycles";
+  LOG(INFO) << "There are " << cuts.size() << " cuts.";
+  DeltaDiffGenerator::CheckGraph(*graph);
+
+  LOG(INFO) << "Creating initial topological order...";
+  TopologicalSort(*graph, final_order);
+  LOG(INFO) << "done with initial topo order";
+  DeltaDiffGenerator::CheckGraph(*graph);
+
+  LOG(INFO) << "Moving full ops to the back";
+  MoveFullOpsToBack(graph, final_order);
+  LOG(INFO) << "done moving full ops to back";
+
+  vector<vector<Vertex::Index>::size_type> inverse_final_order;
+  GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
+
+  SortCutsByTopoOrder(*final_order, &cuts);
+
+  if (!cuts.empty())
+    TEST_AND_RETURN_FALSE(AssignTempBlocks(graph,
+                                           new_root,
+                                           fd,
+                                           data_file_size,
+                                           final_order,
+                                           &inverse_final_order,
+                                           cuts));
+  LOG(INFO) << "Making sure all temp blocks have been allocated";
+
+  // Remove the scratch node, if any
+  if (scratch_vertex != Vertex::kInvalidIndex) {
+    final_order->erase(final_order->begin() +
+                       inverse_final_order[scratch_vertex]);
+    (*graph)[scratch_vertex].valid = false;
+    GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
+  }
+
+  graph_utils::DumpGraph(*graph);
+  CHECK(NoTempBlocksRemain(*graph));
+  LOG(INFO) << "done making sure all temp blocks are allocated";
+  return true;
+}
+
+void InplaceGenerator::CreateScratchNode(uint64_t start_block,
+                                         uint64_t num_blocks,
+                                         Vertex* vertex) {
+  vertex->file_name = "<scratch>";
+  vertex->op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  vertex->op.set_data_offset(0);
+  vertex->op.set_data_length(0);
+  Extent* extent = vertex->op.add_dst_extents();
+  extent->set_start_block(start_block);
+  extent->set_num_blocks(num_blocks);
+}
+
+// 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 InplaceGenerator::AddInstallOpToBlocksVector(
+    const DeltaArchiveManifest_InstallOperation& operation,
+    const Graph& graph,
+    Vertex::Index vertex,
+    vector<DeltaDiffGenerator::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 DeltaDiffGenerator::Block::*access_type =
+        (field == READER) ? &DeltaDiffGenerator::Block::reader
+            : &DeltaDiffGenerator::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;
+}
+
+};  // namespace chromeos_update_engine
diff --git a/payload_generator/inplace_generator.h b/payload_generator/inplace_generator.h
new file mode 100644
index 0000000..73a791b
--- /dev/null
+++ b/payload_generator/inplace_generator.h
@@ -0,0 +1,148 @@
+// Copyright 2015 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 UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+
+// InplaceGenerator contains all functionality related to the inplace algorithm
+// for generating update payloads. These are the functions used when delta minor
+// version is 1.
+
+namespace chromeos_update_engine {
+
+class InplaceGenerator {
+ public:
+  // Modifies blocks read by 'op' so that any blocks referred to by
+  // 'remove_extents' are replaced with blocks from 'replace_extents'.
+  // 'remove_extents' and 'replace_extents' must be the same number of blocks.
+  // Blocks will be substituted in the order listed in the vectors.
+  // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents
+  // contains blocks 6, 2, 3, 5, and replace blocks contains
+  // 12, 13, 14, 15, then op will be changed to read from:
+  // 1, 13, 14, 4, 15, 12, 7, 8
+  static void SubstituteBlocks(Vertex* vertex,
+                               const std::vector<Extent>& remove_extents,
+                               const std::vector<Extent>& replace_extents);
+
+  // Cuts 'edges' from 'graph' according to the AU algorithm. This means
+  // for each edge A->B, remove the dependency that B occur before A.
+  // Do this by creating a new operation X that copies from the blocks
+  // specified by the edge's properties to temp space T. Modify B to read
+  // from T rather than the blocks in the edge. Modify A to depend on X,
+  // but not on B. Free space is found by looking in 'blocks'.
+  // Returns true on success.
+  static bool CutEdges(Graph* graph,
+                       const std::set<Edge>& edges,
+                       std::vector<CutEdgeVertexes>* out_cuts);
+
+  // Creates all the edges for the graph. Writers of a block point to
+  // readers of the same block. This is because for an edge A->B, B
+  // must complete before A executes.
+  static void CreateEdges(Graph* graph,
+                          const std::vector<DeltaDiffGenerator::Block>& blocks);
+
+  // Takes |op_indexes|, which is effectively a mapping from order in
+  // which the op is performed -> graph vertex index, and produces the
+  // reverse: a mapping from graph vertex index -> op_indexes index.
+  static void GenerateReverseTopoOrderMap(
+      const std::vector<Vertex::Index>& op_indexes,
+      std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes);
+
+  // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is
+  // determined by the order of elements in op_indexes.
+  static void SortCutsByTopoOrder(
+      const std::vector<Vertex::Index>& op_indexes,
+      std::vector<CutEdgeVertexes>* cuts);
+
+  // Given a topologically sorted graph |op_indexes| and |graph|, alters
+  // |op_indexes| to move all the full operations to the end of the vector.
+  // Full operations should not be depended on, so this is safe.
+  static void MoveFullOpsToBack(Graph* graph,
+                                std::vector<Vertex::Index>* op_indexes);
+
+  // Returns true iff there are no extents in the graph that refer to temp
+  // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole).
+  static bool NoTempBlocksRemain(const Graph& graph);
+
+  // Takes a |graph|, which has edges that must be cut, as listed in
+  // |cuts|.  Cuts the edges. Maintains a list in which the operations
+  // will be performed (in |op_indexes|) and the reverse (in
+  // |reverse_op_indexes|).  Cutting edges requires scratch space, and
+  // if insufficient scratch is found, the file is reread and will be
+  // send down (either as REPLACE or REPLACE_BZ).  Returns true on
+  // success.
+  static bool AssignTempBlocks(
+      Graph* graph,
+      const std::string& new_root,
+      int data_fd,
+      off_t* data_file_size,
+      std::vector<Vertex::Index>* op_indexes,
+      std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes,
+      const std::vector<CutEdgeVertexes>& cuts);
+
+  // Handles allocation of temp blocks to a cut edge by converting the
+  // dest node to a full op. This removes the need for temp blocks, but
+  // comes at the cost of a worse compression ratio.
+  // For example, say we have A->B->A. It would first be cut to form:
+  // A->B->N<-A, where N copies blocks to temp space. If there are no
+  // temp blocks, this function can be called to convert it to the form:
+  // A->B. Now, A is a full operation.
+  static bool ConvertCutToFullOp(Graph* graph,
+                                 const CutEdgeVertexes& cut,
+                                 const std::string& new_root,
+                                 int data_fd,
+                                 off_t* data_file_size);
+
+  // Takes a graph, which is not a DAG, which represents the files just
+  // read from disk, and converts it into a DAG by breaking all cycles
+  // and finding temp space to resolve broken edges.
+  // The final order of the nodes is given in |final_order|
+  // Some files may need to be reread from disk, thus |fd| and
+  // |data_file_size| are be passed.
+  // If |scratch_vertex| is not kInvalidIndex, removes it from
+  // |final_order| before returning.
+  // Returns true on success.
+  static bool ConvertGraphToDag(Graph* graph,
+                                const std::string& new_root,
+                                int fd,
+                                off_t* data_file_size,
+                                std::vector<Vertex::Index>* final_order,
+                                Vertex::Index scratch_vertex);
+
+  // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used
+  // to provide scratch space. The node writes |num_blocks| blocks starting at
+  // |start_block|The node should be marked invalid before writing all nodes to
+  // the output file.
+  static void CreateScratchNode(uint64_t start_block,
+                                uint64_t num_blocks,
+                                Vertex* vertex);
+
+  // 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(InplaceGenerator);
+};
+
+};  // namespace chromeos_update_engine
+
+#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
new file mode 100644
index 0000000..051902f
--- /dev/null
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -0,0 +1,710 @@
+// Copyright 2015 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 "update_engine/payload_generator/inplace_generator.h"
+
+#include <set>
+#include <sstream>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/logging.h>
+#include <base/strings/string_util.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_generator/cycle_breaker.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::set;
+using std::string;
+using std::stringstream;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+typedef DeltaDiffGenerator::Block Block;
+
+namespace {
+
+#define OP_BSDIFF DeltaArchiveManifest_InstallOperation_Type_BSDIFF
+#define OP_MOVE DeltaArchiveManifest_InstallOperation_Type_MOVE
+#define OP_REPLACE DeltaArchiveManifest_InstallOperation_Type_REPLACE
+#define OP_REPLACE_BZ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ
+
+void GenVertex(Vertex* out,
+               const vector<Extent>& src_extents,
+               const vector<Extent>& dst_extents,
+               const string& path,
+               DeltaArchiveManifest_InstallOperation_Type type) {
+  out->op.set_type(type);
+  out->file_name = path;
+  DeltaDiffGenerator::StoreExtents(src_extents, out->op.mutable_src_extents());
+  DeltaDiffGenerator::StoreExtents(dst_extents, out->op.mutable_dst_extents());
+}
+
+vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
+  return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
+}
+
+EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
+  EdgeProperties ret;
+  ret.extents = extents;
+  return ret;
+}
+
+EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
+  EdgeProperties ret;
+  ret.write_extents = extents;
+  return ret;
+}
+
+template<typename T>
+void DumpVect(const vector<T>& vect) {
+  stringstream ss(stringstream::out);
+  for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
+       it != e; ++it) {
+    ss << *it << ", ";
+  }
+  LOG(INFO) << "{" << ss.str() << "}";
+}
+
+void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
+  vect->resize(vect->size() + 1);
+  vect->back().set_start_block(start);
+  vect->back().set_num_blocks(length);
+}
+
+void OpAppendExtent(DeltaArchiveManifest_InstallOperation* op,
+                    uint64_t start,
+                    uint64_t length) {
+  Extent* extent = op->add_src_extents();
+  extent->set_start_block(start);
+  extent->set_num_blocks(length);
+}
+
+}  // namespace
+
+class InplaceGeneratorTest : public ::testing::Test {
+};
+
+TEST_F(InplaceGeneratorTest, SubstituteBlocksTest) {
+  vector<Extent> remove_blocks;
+  AppendExtent(&remove_blocks, 3, 3);
+  AppendExtent(&remove_blocks, 7, 1);
+  vector<Extent> replace_blocks;
+  AppendExtent(&replace_blocks, 10, 2);
+  AppendExtent(&replace_blocks, 13, 2);
+  Vertex vertex;
+  DeltaArchiveManifest_InstallOperation& op = vertex.op;
+  OpAppendExtent(&op, 4, 3);
+  OpAppendExtent(&op, kSparseHole, 4);  // Sparse hole in file
+  OpAppendExtent(&op, 3, 1);
+  OpAppendExtent(&op, 7, 3);
+
+  InplaceGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
+
+  EXPECT_EQ(7, op.src_extents_size());
+  EXPECT_EQ(11, op.src_extents(0).start_block());
+  EXPECT_EQ(1, op.src_extents(0).num_blocks());
+  EXPECT_EQ(13, op.src_extents(1).start_block());
+  EXPECT_EQ(1, op.src_extents(1).num_blocks());
+  EXPECT_EQ(6, op.src_extents(2).start_block());
+  EXPECT_EQ(1, op.src_extents(2).num_blocks());
+  EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
+  EXPECT_EQ(4, op.src_extents(3).num_blocks());
+  EXPECT_EQ(10, op.src_extents(4).start_block());
+  EXPECT_EQ(1, op.src_extents(4).num_blocks());
+  EXPECT_EQ(14, op.src_extents(5).start_block());
+  EXPECT_EQ(1, op.src_extents(5).num_blocks());
+  EXPECT_EQ(8, op.src_extents(6).start_block());
+  EXPECT_EQ(2, op.src_extents(6).num_blocks());
+}
+
+TEST_F(InplaceGeneratorTest, CutEdgesTest) {
+  Graph graph;
+  vector<Block> blocks(9);
+
+  // Create nodes in graph
+  {
+    graph.resize(graph.size() + 1);
+    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+    // Reads from blocks 3, 5, 7
+    vector<Extent> extents;
+    graph_utils::AppendBlockToExtents(&extents, 3);
+    graph_utils::AppendBlockToExtents(&extents, 5);
+    graph_utils::AppendBlockToExtents(&extents, 7);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_src_extents());
+    blocks[3].reader = graph.size() - 1;
+    blocks[5].reader = graph.size() - 1;
+    blocks[7].reader = graph.size() - 1;
+
+    // Writes to blocks 1, 2, 4
+    extents.clear();
+    graph_utils::AppendBlockToExtents(&extents, 1);
+    graph_utils::AppendBlockToExtents(&extents, 2);
+    graph_utils::AppendBlockToExtents(&extents, 4);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_dst_extents());
+    blocks[1].writer = graph.size() - 1;
+    blocks[2].writer = graph.size() - 1;
+    blocks[4].writer = graph.size() - 1;
+  }
+  {
+    graph.resize(graph.size() + 1);
+    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+    // Reads from blocks 1, 2, 4
+    vector<Extent> extents;
+    graph_utils::AppendBlockToExtents(&extents, 1);
+    graph_utils::AppendBlockToExtents(&extents, 2);
+    graph_utils::AppendBlockToExtents(&extents, 4);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_src_extents());
+    blocks[1].reader = graph.size() - 1;
+    blocks[2].reader = graph.size() - 1;
+    blocks[4].reader = graph.size() - 1;
+
+    // Writes to blocks 3, 5, 6
+    extents.clear();
+    graph_utils::AppendBlockToExtents(&extents, 3);
+    graph_utils::AppendBlockToExtents(&extents, 5);
+    graph_utils::AppendBlockToExtents(&extents, 6);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_dst_extents());
+    blocks[3].writer = graph.size() - 1;
+    blocks[5].writer = graph.size() - 1;
+    blocks[6].writer = graph.size() - 1;
+  }
+
+  // Create edges
+  InplaceGenerator::CreateEdges(&graph, blocks);
+
+  // Find cycles
+  CycleBreaker cycle_breaker;
+  set<Edge> cut_edges;
+  cycle_breaker.BreakCycles(graph, &cut_edges);
+
+  EXPECT_EQ(1, cut_edges.size());
+  EXPECT_TRUE(cut_edges.end() != cut_edges.find(
+      std::pair<Vertex::Index, Vertex::Index>(1, 0)));
+
+  vector<CutEdgeVertexes> cuts;
+  EXPECT_TRUE(InplaceGenerator::CutEdges(&graph, cut_edges, &cuts));
+
+  EXPECT_EQ(3, graph.size());
+
+  // Check new node in graph:
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
+            graph.back().op.type());
+  EXPECT_EQ(2, graph.back().op.src_extents_size());
+  EXPECT_EQ(1, graph.back().op.dst_extents_size());
+  EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
+  EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
+  EXPECT_TRUE(graph.back().out_edges.empty());
+
+  // Check that old node reads from new blocks
+  EXPECT_EQ(2, graph[0].op.src_extents_size());
+  EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
+  EXPECT_EQ(2, graph[0].op.src_extents(0).num_blocks());
+  EXPECT_EQ(7, graph[0].op.src_extents(1).start_block());
+  EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks());
+
+  // And that the old dst extents haven't changed
+  EXPECT_EQ(2, graph[0].op.dst_extents_size());
+  EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block());
+  EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks());
+  EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block());
+  EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks());
+
+  // Ensure it only depends on the next node and the new temp node
+  EXPECT_EQ(2, graph[0].out_edges.size());
+  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
+  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
+                                                                  1));
+
+  // Check second node has unchanged extents
+  EXPECT_EQ(2, graph[1].op.src_extents_size());
+  EXPECT_EQ(1, graph[1].op.src_extents(0).start_block());
+  EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks());
+  EXPECT_EQ(4, graph[1].op.src_extents(1).start_block());
+  EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks());
+
+  EXPECT_EQ(2, graph[1].op.dst_extents_size());
+  EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block());
+  EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
+  EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
+  EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
+
+  // Ensure it only depends on the next node
+  EXPECT_EQ(1, graph[1].out_edges.size());
+  EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
+}
+
+TEST_F(InplaceGeneratorTest, RunAsRootAssignTempBlocksReuseTest) {
+  // AssignTempBlocks(Graph* graph,
+  // const string& new_root,
+  // int data_fd,
+  // off_t* data_file_size,
+  // vector<Vertex::Index>* op_indexes,
+  // vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+  // const vector<CutEdgeVertexes>& cuts
+  Graph graph(9);
+
+  const vector<Extent> empt;
+  uint64_t tmp = kTempBlockStart;
+  const string kFilename = "/foo";
+
+  vector<CutEdgeVertexes> cuts;
+  cuts.resize(3);
+
+  // Simple broken loop:
+  GenVertex(&graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_MOVE);
+  GenVertex(&graph[1], VectOfExt(tmp, 1), VectOfExt(0, 1), "", OP_MOVE);
+  GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(tmp, 1), "", OP_MOVE);
+  // Corresponding edges:
+  graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
+  graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
+  graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
+  // Store the cut:
+  cuts[0].old_dst = 1;
+  cuts[0].old_src = 0;
+  cuts[0].new_vertex = 2;
+  cuts[0].tmp_extents = VectOfExt(tmp, 1);
+  tmp++;
+
+  // Slightly more complex pair of loops:
+  GenVertex(&graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", OP_MOVE);
+  GenVertex(&graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", OP_MOVE);
+  GenVertex(&graph[5], VectOfExt(tmp, 3), VectOfExt(4, 3), kFilename, OP_MOVE);
+  GenVertex(&graph[6], VectOfExt(2, 2), VectOfExt(tmp, 2), "", OP_MOVE);
+  GenVertex(&graph[7], VectOfExt(7, 1), VectOfExt(tmp + 2, 1), "", OP_MOVE);
+  // Corresponding edges:
+  graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
+  graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
+  graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
+  graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
+  graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
+  graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
+  // Store the cuts:
+  cuts[1].old_dst = 5;
+  cuts[1].old_src = 3;
+  cuts[1].new_vertex = 6;
+  cuts[1].tmp_extents = VectOfExt(tmp, 2);
+  cuts[2].old_dst = 5;
+  cuts[2].old_src = 4;
+  cuts[2].new_vertex = 7;
+  cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
+
+  // Supplier of temp block:
+  GenVertex(&graph[8], empt, VectOfExt(8, 1), "", OP_REPLACE);
+
+  // Specify the final order:
+  vector<Vertex::Index> op_indexes;
+  op_indexes.push_back(2);
+  op_indexes.push_back(0);
+  op_indexes.push_back(1);
+  op_indexes.push_back(6);
+  op_indexes.push_back(3);
+  op_indexes.push_back(7);
+  op_indexes.push_back(4);
+  op_indexes.push_back(5);
+  op_indexes.push_back(8);
+
+  vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
+  InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes,
+                                                &reverse_op_indexes);
+
+  // Prepare the filesystem with the minimum required for this to work
+  string temp_dir;
+  EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksReuseTest.XXXXXX",
+                                       &temp_dir));
+  ScopedDirRemover temp_dir_remover(temp_dir);
+
+  chromeos::Blob temp_data(kBlockSize * 3);
+  test_utils::FillWithData(&temp_data);
+  EXPECT_TRUE(test_utils::WriteFileVector(temp_dir + kFilename, temp_data));
+  ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+  int fd;
+  EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksReuseTest.XXXXXX",
+                                  nullptr,
+                                  &fd));
+  ScopedFdCloser fd_closer(&fd);
+  off_t data_file_size = 0;
+
+  EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph,
+                                                 temp_dir,
+                                                 fd,
+                                                 &data_file_size,
+                                                 &op_indexes,
+                                                 &reverse_op_indexes,
+                                                 cuts));
+  EXPECT_FALSE(graph[6].valid);
+  EXPECT_FALSE(graph[7].valid);
+  EXPECT_EQ(1, graph[1].op.src_extents_size());
+  EXPECT_EQ(2, graph[1].op.src_extents(0).start_block());
+  EXPECT_EQ(1, graph[1].op.src_extents(0).num_blocks());
+  EXPECT_EQ(OP_REPLACE_BZ, graph[5].op.type());
+}
+
+TEST_F(InplaceGeneratorTest, MoveFullOpsToBackTest) {
+  Graph graph(4);
+  graph[0].file_name = "A";
+  graph[0].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+  graph[1].file_name = "B";
+  graph[1].op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+  graph[2].file_name = "C";
+  graph[2].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  graph[3].file_name = "D";
+  graph[3].op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+
+  vector<Vertex::Index> vect(graph.size());
+
+  for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
+    vect[i] = i;
+  }
+  InplaceGenerator::MoveFullOpsToBack(&graph, &vect);
+  EXPECT_EQ(vect.size(), graph.size());
+  EXPECT_EQ(graph[vect[0]].file_name, "B");
+  EXPECT_EQ(graph[vect[1]].file_name, "D");
+  EXPECT_EQ(graph[vect[2]].file_name, "A");
+  EXPECT_EQ(graph[vect[3]].file_name, "C");
+}
+
+TEST_F(InplaceGeneratorTest, RunAsRootAssignTempBlocksTest) {
+  Graph graph(9);
+  const vector<Extent> empt;  // empty
+  const string kFilename = "/foo";
+
+  // Some scratch space:
+  GenVertex(&graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
+  GenVertex(&graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
+  GenVertex(&graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
+
+  // A cycle that requires 10 blocks to break:
+  GenVertex(&graph[3], VectOfExt(10, 11), VectOfExt(0, 9), "", OP_BSDIFF);
+  graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
+  GenVertex(&graph[4], VectOfExt(0, 9), VectOfExt(10, 11), "", OP_BSDIFF);
+  graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
+
+  // A cycle that requires 9 blocks to break:
+  GenVertex(&graph[5], VectOfExt(40, 11), VectOfExt(30, 10), "", OP_BSDIFF);
+  graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
+  GenVertex(&graph[6], VectOfExt(30, 10), VectOfExt(40, 11), "", OP_BSDIFF);
+  graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
+
+  // A cycle that requires 40 blocks to break (which is too many):
+  GenVertex(&graph[7],
+            VectOfExt(120, 50),
+            VectOfExt(60, 40),
+            "",
+            OP_BSDIFF);
+  graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
+  GenVertex(&graph[8],
+            VectOfExt(60, 40),
+            VectOfExt(120, 50),
+            kFilename,
+            OP_BSDIFF);
+  graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
+
+  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("AssignTempBlocksTest.XXXXXX",
+                                       &temp_dir));
+  ScopedDirRemover temp_dir_remover(temp_dir);
+
+  chromeos::Blob temp_data(kBlockSize * 50);
+  test_utils::FillWithData(&temp_data);
+  EXPECT_TRUE(test_utils::WriteFileVector(temp_dir + kFilename, temp_data));
+  ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+  int fd;
+  EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksTestData.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));
+
+
+  Graph expected_graph(12);
+  GenVertex(&expected_graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
+  GenVertex(&expected_graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
+  GenVertex(&expected_graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
+  GenVertex(&expected_graph[3],
+            VectOfExt(10, 11),
+            VectOfExt(0, 9),
+            "",
+            OP_BSDIFF);
+  expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
+  GenVertex(&expected_graph[4],
+            VectOfExt(60, 9),
+            VectOfExt(10, 11),
+            "",
+            OP_BSDIFF);
+  expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
+  expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
+  GenVertex(&expected_graph[5],
+            VectOfExt(40, 11),
+            VectOfExt(30, 10),
+            "",
+            OP_BSDIFF);
+  expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
+
+  GenVertex(&expected_graph[6],
+            VectOfExt(60, 10),
+            VectOfExt(40, 11),
+            "",
+            OP_BSDIFF);
+  expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
+  expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
+
+  GenVertex(&expected_graph[7],
+            VectOfExt(120, 50),
+            VectOfExt(60, 40),
+            "",
+            OP_BSDIFF);
+  expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
+
+  GenVertex(&expected_graph[8], empt, VectOfExt(0, 50), "/foo", OP_REPLACE_BZ);
+  expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
+
+  GenVertex(&expected_graph[9],
+            VectOfExt(0, 9),
+            VectOfExt(60, 9),
+            "",
+            OP_MOVE);
+
+  GenVertex(&expected_graph[10],
+            VectOfExt(30, 10),
+            VectOfExt(60, 10),
+            "",
+            OP_MOVE);
+  expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
+
+  EXPECT_EQ(12, graph.size());
+  EXPECT_FALSE(graph.back().valid);
+  for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
+    EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
+    if (i == 8) {
+      // special case
+    } else {
+      // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
+    }
+  }
+}
+
+// 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);
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
+            vertex.op.type());
+  EXPECT_EQ(0, vertex.op.data_offset());
+  EXPECT_EQ(0, vertex.op.data_length());
+  EXPECT_EQ(1, vertex.op.dst_extents_size());
+  EXPECT_EQ(12, vertex.op.dst_extents(0).start_block());
+  EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/metadata.cc b/payload_generator/metadata.cc
index 7a6493c..a96071a 100644
--- a/payload_generator/metadata.cc
+++ b/payload_generator/metadata.cc
@@ -19,6 +19,7 @@
 #include "update_engine/payload_generator/delta_diff_generator.h"
 #include "update_engine/payload_generator/ext2_utils.h"
 #include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/inplace_generator.h"
 #include "update_engine/utils.h"
 
 using base::StringPrintf;
@@ -192,7 +193,7 @@
   CHECK((*graph)[vertex].op.has_type());
   (*graph)[vertex].file_name = metadata_name;
 
-  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::AddInstallOpToBlocksVector(
+  TEST_AND_RETURN_FALSE(InplaceGenerator::AddInstallOpToBlocksVector(
       (*graph)[vertex].op,
       *graph,
       vertex,