diff --git a/delta_diff_generator_unittest.cc b/delta_diff_generator_unittest.cc
index 7fa28c3..181fd27 100644
--- a/delta_diff_generator_unittest.cc
+++ b/delta_diff_generator_unittest.cc
@@ -657,6 +657,190 @@
   }
 }
 
+// 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("/tmp/NoSparseAsTempTest.XXXXXX",
+                                       &temp_dir));
+  ScopedDirRemover temp_dir_remover(temp_dir);
+
+  const size_t kBlockSize = 4096;
+  vector<char> 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("/tmp/NoSparseAsTempTestData.XXXXXX",
+                                  NULL,
+                                  &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;
   op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
diff --git a/extent_ranges.cc b/extent_ranges.cc
index a8836c9..5193d3d 100644
--- a/extent_ranges.cc
+++ b/extent_ranges.cc
@@ -20,6 +20,8 @@
 bool ExtentRanges::ExtentsOverlapOrTouch(const Extent& a, const Extent& b) {
   if (a.start_block() == b.start_block())
     return true;
+  if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
+    return false;
   if (a.start_block() < b.start_block()) {
     return a.start_block() + a.num_blocks() >= b.start_block();
   } else {
@@ -30,6 +32,8 @@
 bool ExtentRanges::ExtentsOverlap(const Extent& a, const Extent& b) {
   if (a.start_block() == b.start_block())
     return true;
+  if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
+    return false;
   if (a.start_block() < b.start_block()) {
     return a.start_block() + a.num_blocks() > b.start_block();
   } else {
@@ -48,16 +52,18 @@
 namespace {
 
 Extent UnionOverlappingExtents(const Extent& first, const Extent& second) {
+  CHECK_NE(kSparseHole, first.start_block());
+  CHECK_NE(kSparseHole, second.start_block());
   uint64_t start = min(first.start_block(), second.start_block());
   uint64_t end = max(first.start_block() + first.num_blocks(),
                      second.start_block() + second.num_blocks());
   return ExtentForRange(start, end - start);
 }
-  
+
 }  // namespace {}
 
 void ExtentRanges::AddExtent(Extent extent) {
-  if (extent.num_blocks() == 0)
+  if (extent.start_block() == kSparseHole || extent.num_blocks() == 0)
     return;
 
   ExtentSet::iterator begin_del = extent_set_.end();
@@ -100,7 +106,7 @@
 }  // namespace {}
 
 void ExtentRanges::SubtractExtent(const Extent& extent) {
-  if (extent.num_blocks() == 0)
+  if (extent.start_block() == kSparseHole || extent.num_blocks() == 0)
     return;
 
   ExtentSet::iterator begin_del = extent_set_.end();
@@ -111,12 +117,12 @@
        it != e; ++it) {
     if (!ExtentsOverlap(*it, extent))
       continue;
-    
+
     if (begin_del == extent_set_.end())
       begin_del = it;
     end_del = it;
     ++end_del;
-    
+
     del_blocks += it->num_blocks();
 
     ExtentSet subtraction = SubtractOverlappingExtents(*it, extent);
diff --git a/extent_ranges.h b/extent_ranges.h
index 8fdc302..2ab347a 100644
--- a/extent_ranges.h
+++ b/extent_ranges.h
@@ -15,9 +15,12 @@
 #include "update_engine/graph_types.h"
 #include "update_engine/update_metadata.pb.h"
 
-// An ExtentRanges object represents an unordered collection of extents
-// (and therefore blocks). Such an object may be modified by adding or
-// subtracting blocks (think: set addition or set subtraction).
+// An ExtentRanges object represents an unordered collection of extents (and
+// therefore blocks). Such an object may be modified by adding or subtracting
+// blocks (think: set addition or set subtraction). Note that ExtentRanges
+// ignores sparse hole extents mostly to avoid confusion between extending a
+// sparse hole range vs. set addition but also to ensure that the delta
+// generator doesn't use sparse holes as scratch space.
 
 namespace chromeos_update_engine {
 
@@ -52,7 +55,7 @@
 
   // Dumps contents to the log file. Useful for debugging.
   void Dump() const;
-  
+
   uint64_t blocks() const { return blocks_; }
   const ExtentSet& extent_set() const { return extent_set_; }
 
diff --git a/extent_ranges_unittest.cc b/extent_ranges_unittest.cc
index b5a32d9..1b767f1 100644
--- a/extent_ranges_unittest.cc
+++ b/extent_ranges_unittest.cc
@@ -17,7 +17,7 @@
 
 namespace {
 void ExpectRangeEq(const ExtentRanges& ranges,
-                   uint64_t* expected,
+                   const uint64_t* expected,
                    size_t sz,
                    int line) {
   uint64_t blocks = 0;
@@ -113,39 +113,50 @@
   ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10);
   ExpectFalseRangesOverlap(10, 20, 30, 10);
   ExpectRangesOverlap(12, 4, 12, 3);
+
+  ExpectRangesOverlapOrTouch(kSparseHole, 2, kSparseHole, 3);
+  ExpectRangesOverlap(kSparseHole, 2, kSparseHole, 3);
+  ExpectFalseRangesOverlapOrTouch(kSparseHole, 2, 10, 3);
+  ExpectFalseRangesOverlapOrTouch(10, 2, kSparseHole, 3);
+  ExpectFalseRangesOverlap(kSparseHole, 2, 10, 3);
+  ExpectFalseRangesOverlap(10, 2, kSparseHole, 3);
 }
 
 TEST(ExtentRangesTest, SimpleTest) {
   ExtentRanges ranges;
   {
-    uint64_t expected[] = {};
+    static const uint64_t expected[] = {};
     // Can't use arraysize() on 0-length arrays:
     ExpectRangeEq(ranges, expected, 0, __LINE__);
   }
   ranges.SubtractBlock(2);
   {
-    uint64_t expected[] = {};
+    static const uint64_t expected[] = {};
     // Can't use arraysize() on 0-length arrays:
     ExpectRangeEq(ranges, expected, 0, __LINE__);
   }
-  
+
   ranges.AddBlock(0);
   ranges.Dump();
   ranges.AddBlock(1);
   ranges.AddBlock(3);
-  
+
   {
-    uint64_t expected[] = {0, 2, 3, 1};
+    static const uint64_t expected[] = {0, 2, 3, 1};
     EXPECT_RANGE_EQ(ranges, expected);
   }
   ranges.AddBlock(2);
   {
-    uint64_t expected[] = {0, 4};
+    static const uint64_t expected[] = {0, 4};
+    EXPECT_RANGE_EQ(ranges, expected);
+    ranges.AddBlock(kSparseHole);
+    EXPECT_RANGE_EQ(ranges, expected);
+    ranges.SubtractBlock(kSparseHole);
     EXPECT_RANGE_EQ(ranges, expected);
   }
   ranges.SubtractBlock(2);
   {
-    uint64_t expected[] = {0, 2, 3, 1};
+    static const uint64_t expected[] = {0, 2, 3, 1};
     EXPECT_RANGE_EQ(ranges, expected);
   }
 
@@ -153,27 +164,35 @@
     ranges.AddExtent(ExtentForRange(i, 50));
   }
   {
-    uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 50, 300, 50, 400, 50,
-                           500, 50, 600, 50, 700, 50, 800, 50, 900, 50};
+    static const uint64_t expected[] = {
+      0, 2, 3, 1, 100, 50, 200, 50, 300, 50, 400, 50,
+      500, 50, 600, 50, 700, 50, 800, 50, 900, 50
+    };
     EXPECT_RANGE_EQ(ranges, expected);
   }
 
   ranges.SubtractExtent(ExtentForRange(210, 410 - 210));
   {
-    uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
-                           600, 50, 700, 50, 800, 50, 900, 50};
+    static const uint64_t expected[] = {
+      0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+      600, 50, 700, 50, 800, 50, 900, 50
+    };
     EXPECT_RANGE_EQ(ranges, expected);
   }
   ranges.AddExtent(ExtentForRange(100000, 0));
   {
-    uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
-                           600, 50, 700, 50, 800, 50, 900, 50};
+    static const uint64_t expected[] = {
+      0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+      600, 50, 700, 50, 800, 50, 900, 50
+    };
     EXPECT_RANGE_EQ(ranges, expected);
   }
   ranges.SubtractExtent(ExtentForRange(3, 0));
   {
-    uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
-                           600, 50, 700, 50, 800, 50, 900, 50};
+    static const uint64_t expected[] = {
+      0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+      600, 50, 700, 50, 800, 50, 900, 50
+    };
     EXPECT_RANGE_EQ(ranges, expected);
   }
 }
diff --git a/graph_utils.cc b/graph_utils.cc
index 02b49c3..3e3cc9e 100644
--- a/graph_utils.cc
+++ b/graph_utils.cc
@@ -33,21 +33,17 @@
 }
 
 void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) {
+  // First try to extend the last extent in |extents|, if any.
   if (!extents->empty()) {
     Extent& extent = extents->back();
-    if (block == kSparseHole) {
-      if (extent.start_block() == kSparseHole) {
-        // Extend sparse hole extent
-        extent.set_num_blocks(extent.num_blocks() + 1);
-        return;
-      } else {
-        // Create new extent below outer 'if'
-      }
-    } else if (extent.start_block() + extent.num_blocks() == block) {
+    uint64_t next_block = extent.start_block() == kSparseHole ?
+        kSparseHole : extent.start_block() + extent.num_blocks();
+    if (next_block == block) {
       extent.set_num_blocks(extent.num_blocks() + 1);
       return;
     }
   }
+  // If unable to extend the last extent, append a new single-block extent.
   Extent new_extent;
   new_extent.set_start_block(block);
   new_extent.set_num_blocks(1);
diff --git a/graph_utils_unittest.cc b/graph_utils_unittest.cc
index cfa2b5c..3bd9d16 100644
--- a/graph_utils_unittest.cc
+++ b/graph_utils_unittest.cc
@@ -19,7 +19,7 @@
 
 TEST(GraphUtilsTest, SimpleTest) {
   Graph graph(2);
-  
+
   graph[0].out_edges.insert(make_pair(1, EdgeProperties()));
 
   vector<Extent>& extents = graph[0].out_edges[1].extents;
@@ -31,16 +31,36 @@
   graph_utils::AppendBlockToExtents(&extents, 2);
   EXPECT_EQ(1, extents.size());
   graph_utils::AppendBlockToExtents(&extents, 4);
-  
+
   EXPECT_EQ(2, extents.size());
   EXPECT_EQ(0, extents[0].start_block());
   EXPECT_EQ(3, extents[0].num_blocks());
   EXPECT_EQ(4, extents[1].start_block());
   EXPECT_EQ(1, extents[1].num_blocks());
-  
+
   EXPECT_EQ(4, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
 }
 
+TEST(GraphUtilsTest, AppendSparseToExtentsTest) {
+  vector<Extent> extents;
+
+  EXPECT_EQ(0, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+  EXPECT_EQ(1, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, 0);
+  EXPECT_EQ(2, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+  graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+
+  ASSERT_EQ(3, extents.size());
+  EXPECT_EQ(kSparseHole, extents[0].start_block());
+  EXPECT_EQ(1, extents[0].num_blocks());
+  EXPECT_EQ(0, extents[1].start_block());
+  EXPECT_EQ(1, extents[1].num_blocks());
+  EXPECT_EQ(kSparseHole, extents[2].start_block());
+  EXPECT_EQ(2, extents[2].num_blocks());
+}
+
 TEST(GraphUtilsTest, BlocksInExtentsTest) {
   {
     vector<Extent> extents;
@@ -66,7 +86,7 @@
 
 TEST(GraphUtilsTest, DepsTest) {
   Graph graph(3);
-  
+
   graph_utils::AddReadBeforeDep(&graph[0], 1, 3);
   EXPECT_EQ(1, graph[0].out_edges.size());
   {
@@ -93,7 +113,7 @@
   graph[2].out_edges[1].write_extents.swap(graph[2].out_edges[1].extents);
   graph_utils::DropWriteBeforeDeps(&graph[2].out_edges);
   EXPECT_EQ(0, graph[2].out_edges.size());
-  
+
   EXPECT_EQ(1, graph[0].out_edges.size());
   graph_utils::DropIncomingEdgesTo(&graph, 1);
   EXPECT_EQ(0, graph[0].out_edges.size());