diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 077b8fb..ef8b8ff 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -767,7 +767,7 @@
   for (vector<Block>::size_type i = 0; i < blocks.size(); i++) {
     if (blocks[i].writer != Vertex::kInvalidIndex)
       continue;
-    graph_utils::AppendBlockToExtents(&extents, i);
+    AppendBlockToExtents(&extents, i);
     block_count++;
   }
 
@@ -825,7 +825,7 @@
             graph_utils::AddReadBeforeDep(vertex, blocks[block_idx].reader,
                                           block_idx);
           }
-          graph_utils::AppendBlockToExtents(&changed_extents, block_idx);
+          AppendBlockToExtents(&changed_extents, block_idx);
           changed_block_count++;
         }
         buf_offset = buf_end_offset;
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
index 800168e..07e26ad 100644
--- a/payload_generator/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -13,8 +13,8 @@
 #include <chromeos/secure_blob.h>
 
 #include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_utils.h"
 #include "update_engine/payload_generator/graph_types.h"
-#include "update_engine/payload_generator/graph_utils.h"
 #include "update_engine/payload_generator/operations_generator.h"
 #include "update_engine/payload_generator/payload_generation_config.h"
 #include "update_engine/update_metadata.pb.h"
@@ -217,7 +217,7 @@
   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);
+      const Extent extent = GetElement(extents, i);
       if (extent.start_block() == kSparseHole) {
         ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
       } else {
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
index cf393db..94dd1e4 100644
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -29,7 +29,6 @@
 #include "update_engine/payload_constants.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"
 #include "update_engine/subprocess.h"
 #include "update_engine/test_utils.h"
 #include "update_engine/utils.h"
diff --git a/payload_generator/extent_mapper.cc b/payload_generator/extent_mapper.cc
index ce490d2..c936450 100644
--- a/payload_generator/extent_mapper.cc
+++ b/payload_generator/extent_mapper.cc
@@ -17,8 +17,7 @@
 #include <algorithm>
 
 #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/payload_generator/extent_utils.h"
 #include "update_engine/utils.h"
 
 using std::string;
@@ -71,7 +70,7 @@
 
     const uint64_t block = (block32 == 0 ? kSparseHole : block32);
 
-    graph_utils::AppendBlockToExtents(out, block);
+    AppendBlockToExtents(out, block);
   }
   return true;
 }
diff --git a/payload_generator/extent_utils.cc b/payload_generator/extent_utils.cc
new file mode 100644
index 0000000..dcb8bf8
--- /dev/null
+++ b/payload_generator/extent_utils.cc
@@ -0,0 +1,53 @@
+// Copyright (c) 2009 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/extent_utils.h"
+
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/logging.h>
+#include <base/macros.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/annotated_operation.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+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();
+    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);
+  extents->push_back(new_extent);
+}
+
+Extent GetElement(const vector<Extent>& collection, size_t index) {
+  return collection[index];
+}
+Extent GetElement(
+    const google::protobuf::RepeatedPtrField<Extent>& collection,
+    size_t index) {
+  return collection.Get(index);
+}
+
+bool operator==(const Extent& a, const Extent& b) {
+  return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/extent_utils.h b/payload_generator/extent_utils.h
new file mode 100644
index 0000000..1583618
--- /dev/null
+++ b/payload_generator/extent_utils.h
@@ -0,0 +1,41 @@
+// 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_EXTENT_UTILS_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_UTILS_H_
+
+#include <vector>
+
+#include "update_engine/update_metadata.pb.h"
+
+// Utility functions for manipulating Extents and lists of blocks.
+
+namespace chromeos_update_engine {
+
+// |block| must either be the next block in the last extent or a block
+// in the next extent. This function will not handle inserting block
+// into an arbitrary place in the extents.
+void AppendBlockToExtents(std::vector<Extent>* extents, uint64_t block);
+
+// Get/SetElement are intentionally overloaded so that templated functions
+// can accept either type of collection of Extents.
+Extent GetElement(const std::vector<Extent>& collection, size_t index);
+Extent GetElement(
+    const google::protobuf::RepeatedPtrField<Extent>& collection,
+    size_t index);
+
+template<typename T>
+uint64_t BlocksInExtents(const T& collection) {
+  uint64_t ret = 0;
+  for (size_t i = 0; i < static_cast<size_t>(collection.size()); ++i) {
+    ret += GetElement(collection, i).num_blocks();
+  }
+  return ret;
+}
+
+bool operator==(const Extent& a, const Extent& b);
+
+}  // namespace chromeos_update_engine
+
+#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_UTILS_H_
diff --git a/payload_generator/extent_utils_unittest.cc b/payload_generator/extent_utils_unittest.cc
new file mode 100644
index 0000000..fe1d000
--- /dev/null
+++ b/payload_generator/extent_utils_unittest.cc
@@ -0,0 +1,64 @@
+// 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/extent_utils.h"
+
+#include <utility>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_constants.h"
+
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class ExtentUtilsTest : public ::testing::Test {};
+
+TEST(ExtentUtilsTest, AppendSparseToExtentsTest) {
+  vector<Extent> extents;
+
+  EXPECT_EQ(0, extents.size());
+  AppendBlockToExtents(&extents, kSparseHole);
+  EXPECT_EQ(1, extents.size());
+  AppendBlockToExtents(&extents, 0);
+  EXPECT_EQ(2, extents.size());
+  AppendBlockToExtents(&extents, kSparseHole);
+  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(ExtentUtilsTest, BlocksInExtentsTest) {
+  {
+    vector<Extent> extents;
+    EXPECT_EQ(0, BlocksInExtents(extents));
+    extents.push_back(ExtentForRange(0, 1));
+    EXPECT_EQ(1, BlocksInExtents(extents));
+    extents.push_back(ExtentForRange(23, 55));
+    EXPECT_EQ(56, BlocksInExtents(extents));
+    extents.push_back(ExtentForRange(1, 2));
+    EXPECT_EQ(58, BlocksInExtents(extents));
+  }
+  {
+    google::protobuf::RepeatedPtrField<Extent> extents;
+    EXPECT_EQ(0, BlocksInExtents(extents));
+    *extents.Add() = ExtentForRange(0, 1);
+    EXPECT_EQ(1, BlocksInExtents(extents));
+    *extents.Add() = ExtentForRange(23, 55);
+    EXPECT_EQ(56, BlocksInExtents(extents));
+    *extents.Add() = ExtentForRange(1, 2);
+    EXPECT_EQ(58, BlocksInExtents(extents));
+  }
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/graph_utils.cc b/payload_generator/graph_utils.cc
index 3f9b28f..7b03236 100644
--- a/payload_generator/graph_utils.cc
+++ b/payload_generator/graph_utils.cc
@@ -13,6 +13,7 @@
 
 #include "update_engine/payload_constants.h"
 #include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/extent_utils.h"
 
 using std::make_pair;
 using std::pair;
@@ -20,7 +21,6 @@
 using std::vector;
 
 namespace chromeos_update_engine {
-
 namespace graph_utils {
 
 uint64_t EdgeWeight(const Graph& graph, const Edge& edge) {
@@ -35,24 +35,6 @@
   return weight;
 }
 
-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();
-    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);
-  extents->push_back(new_extent);
-}
-
 void AddReadBeforeDep(Vertex* src,
                       Vertex::Index dst,
                       uint64_t block) {
@@ -106,15 +88,6 @@
   }
 }
 
-Extent GetElement(const vector<Extent>& collection, size_t index) {
-  return collection[index];
-}
-Extent GetElement(
-    const google::protobuf::RepeatedPtrField<Extent>& collection,
-    size_t index) {
-  return collection.Get(index);
-}
-
 namespace {
 template<typename T>
 void DumpExtents(const T& field, int prepend_space_count) {
@@ -154,9 +127,4 @@
 }
 
 }  // namespace graph_utils
-
-bool operator==(const Extent& a, const Extent& b) {
-  return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
-}
-
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/graph_utils.h b/payload_generator/graph_utils.h
index e4692e0..6595e57 100644
--- a/payload_generator/graph_utils.h
+++ b/payload_generator/graph_utils.h
@@ -35,27 +35,6 @@
 // For each node N in graph, drop all edges N->|index|.
 void DropIncomingEdgesTo(Graph* graph, Vertex::Index index);
 
-// block must either be the next block in the last extent or a block
-// in the next extent. This function will not handle inserting block
-// into an arbitrary place in the extents.
-void AppendBlockToExtents(std::vector<Extent>* extents, uint64_t block);
-
-// Get/SetElement are intentionally overloaded so that templated functions
-// can accept either type of collection of Extents.
-Extent GetElement(const std::vector<Extent>& collection, size_t index);
-Extent GetElement(
-    const google::protobuf::RepeatedPtrField<Extent>& collection,
-    size_t index);
-
-template<typename T>
-uint64_t BlocksInExtents(const T& collection) {
-  uint64_t ret = 0;
-  for (size_t i = 0; i < static_cast<size_t>(collection.size()); ++i) {
-    ret += GetElement(collection, i).num_blocks();
-  }
-  return ret;
-}
-
 void DumpGraph(const Graph& graph);
 
 }  // namespace graph_utils
diff --git a/payload_generator/graph_utils_unittest.cc b/payload_generator/graph_utils_unittest.cc
index c96927f..3253f71 100644
--- a/payload_generator/graph_utils_unittest.cc
+++ b/payload_generator/graph_utils_unittest.cc
@@ -11,6 +11,7 @@
 
 #include "update_engine/extent_ranges.h"
 #include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_utils.h"
 
 using std::make_pair;
 using std::vector;
@@ -27,12 +28,12 @@
   vector<Extent>& extents = graph[0].out_edges[1].extents;
 
   EXPECT_EQ(0, extents.size());
-  graph_utils::AppendBlockToExtents(&extents, 0);
+  AppendBlockToExtents(&extents, 0);
   EXPECT_EQ(1, extents.size());
-  graph_utils::AppendBlockToExtents(&extents, 1);
-  graph_utils::AppendBlockToExtents(&extents, 2);
+  AppendBlockToExtents(&extents, 1);
+  AppendBlockToExtents(&extents, 2);
   EXPECT_EQ(1, extents.size());
-  graph_utils::AppendBlockToExtents(&extents, 4);
+  AppendBlockToExtents(&extents, 4);
 
   EXPECT_EQ(2, extents.size());
   EXPECT_EQ(0, extents[0].start_block());
@@ -43,48 +44,6 @@
   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;
-    EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
-    extents.push_back(ExtentForRange(0, 1));
-    EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
-    extents.push_back(ExtentForRange(23, 55));
-    EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
-    extents.push_back(ExtentForRange(1, 2));
-    EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
-  }
-  {
-    google::protobuf::RepeatedPtrField<Extent> extents;
-    EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
-    *extents.Add() = ExtentForRange(0, 1);
-    EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
-    *extents.Add() = ExtentForRange(23, 55);
-    EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
-    *extents.Add() = ExtentForRange(1, 2);
-    EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
-  }
-}
 
 TEST(GraphUtilsTest, DepsTest) {
   Graph graph(3);
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index febb5e6..29d53e3 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -56,7 +56,7 @@
 vector<Extent> CompressExtents(const vector<uint64_t>& blocks) {
   vector<Extent> new_extents;
   for (uint64_t block : blocks) {
-    graph_utils::AppendBlockToExtents(&new_extents, block);
+    AppendBlockToExtents(&new_extents, block);
   }
   return new_extents;
 }
@@ -194,7 +194,7 @@
       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);
+    AppendBlockToExtents(&edge_it->second.extents, i);
   }
 }
 
@@ -266,7 +266,7 @@
 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);
+    Extent extent = GetElement(extents, i);
     uint64_t start = extent.start_block();
     uint64_t num = extent.num_blocks();
     if (start >= kTempBlockStart || (start + num) >= kTempBlockStart) {
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
index fdf3aba..6c4f36b 100644
--- a/payload_generator/inplace_generator_unittest.cc
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -18,6 +18,7 @@
 #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/test_utils.h"
 #include "update_engine/utils.h"
 
@@ -136,9 +137,9 @@
     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);
+    AppendBlockToExtents(&extents, 3);
+    AppendBlockToExtents(&extents, 5);
+    AppendBlockToExtents(&extents, 7);
     DeltaDiffGenerator::StoreExtents(extents,
                                      graph.back().op.mutable_src_extents());
     blocks[3].reader = graph.size() - 1;
@@ -147,9 +148,9 @@
 
     // Writes to blocks 1, 2, 4
     extents.clear();
-    graph_utils::AppendBlockToExtents(&extents, 1);
-    graph_utils::AppendBlockToExtents(&extents, 2);
-    graph_utils::AppendBlockToExtents(&extents, 4);
+    AppendBlockToExtents(&extents, 1);
+    AppendBlockToExtents(&extents, 2);
+    AppendBlockToExtents(&extents, 4);
     DeltaDiffGenerator::StoreExtents(extents,
                                      graph.back().op.mutable_dst_extents());
     blocks[1].writer = graph.size() - 1;
@@ -161,9 +162,9 @@
     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);
+    AppendBlockToExtents(&extents, 1);
+    AppendBlockToExtents(&extents, 2);
+    AppendBlockToExtents(&extents, 4);
     DeltaDiffGenerator::StoreExtents(extents,
                                      graph.back().op.mutable_src_extents());
     blocks[1].reader = graph.size() - 1;
@@ -172,9 +173,9 @@
 
     // Writes to blocks 3, 5, 6
     extents.clear();
-    graph_utils::AppendBlockToExtents(&extents, 3);
-    graph_utils::AppendBlockToExtents(&extents, 5);
-    graph_utils::AppendBlockToExtents(&extents, 6);
+    AppendBlockToExtents(&extents, 3);
+    AppendBlockToExtents(&extents, 5);
+    AppendBlockToExtents(&extents, 6);
     DeltaDiffGenerator::StoreExtents(extents,
                                      graph.back().op.mutable_dst_extents());
     blocks[3].writer = graph.size() - 1;
diff --git a/payload_generator/metadata.cc b/payload_generator/metadata.cc
index 77e02fa..f185465 100644
--- a/payload_generator/metadata.cc
+++ b/payload_generator/metadata.cc
@@ -18,7 +18,7 @@
 #include "update_engine/extent_ranges.h"
 #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/extent_utils.h"
 #include "update_engine/payload_generator/inplace_generator.h"
 #include "update_engine/utils.h"
 
@@ -281,7 +281,7 @@
                           int ref_offset,
                           void* priv) {
   vector<Extent>* extents = static_cast<vector<Extent>*>(priv);
-  graph_utils::AppendBlockToExtents(extents, *blocknr);
+  AppendBlockToExtents(extents, *blocknr);
   return 0;
 }
 
@@ -295,7 +295,7 @@
                                void* priv) {
   vector<Extent>* extents = static_cast<vector<Extent>*>(priv);
   if (blockcnt < 0) {
-    graph_utils::AppendBlockToExtents(extents, *blocknr);
+    AppendBlockToExtents(extents, *blocknr);
   }
   return 0;
 }