diff --git a/SConstruct b/SConstruct
index bd2a5d8..fd98b20 100644
--- a/SConstruct
+++ b/SConstruct
@@ -249,6 +249,7 @@
                    filesystem_iterator.cc
                    file_writer.cc
                    flimflam_proxy.cc
+                   full_update_generator.cc
                    graph_utils.cc
                    gzip.cc
                    libcurl_http_fetcher.cc
@@ -290,6 +291,7 @@
                             filesystem_copier_action_unittest.cc
                             filesystem_iterator_unittest.cc
                             flimflam_proxy_unittest.cc
+                            full_update_generator_unittest.cc
                             graph_utils_unittest.cc
                             http_fetcher_unittest.cc
                             mock_http_fetcher.cc
diff --git a/delta_diff_generator.cc b/delta_diff_generator.cc
index 64c1766..50db931 100644
--- a/delta_diff_generator.cc
+++ b/delta_diff_generator.cc
@@ -27,6 +27,7 @@
 #include "update_engine/extent_ranges.h"
 #include "update_engine/file_writer.h"
 #include "update_engine/filesystem_iterator.h"
+#include "update_engine/full_update_generator.h"
 #include "update_engine/graph_types.h"
 #include "update_engine/graph_utils.h"
 #include "update_engine/omaha_hash_calculator.h"
@@ -1308,85 +1309,6 @@
   return true;
 }
 
-bool DeltaDiffGenerator::ReadFullUpdateFromDisk(
-    Graph* graph,
-    const std::string& new_kernel_part,
-    const std::string& new_image,
-    off_t image_size,
-    int fd,
-    off_t* data_file_size,
-    off_t chunk_size,
-    vector<DeltaArchiveManifest_InstallOperation>* kernel_ops,
-    std::vector<Vertex::Index>* final_order) {
-  TEST_AND_RETURN_FALSE(chunk_size > 0);
-  TEST_AND_RETURN_FALSE((chunk_size % kBlockSize) == 0);
-
-  // Get the sizes early in the function, so we can fail fast if the user
-  // passed us bad paths.
-  TEST_AND_RETURN_FALSE(image_size >= 0 &&
-                        image_size <= utils::FileSize(new_image));
-  const off_t kernel_size = utils::FileSize(new_kernel_part);
-  TEST_AND_RETURN_FALSE(kernel_size >= 0);
-
-  off_t part_sizes[] = { image_size, kernel_size };
-  string paths[] = { new_image, new_kernel_part };
-
-  for (int partition = 0; partition < 2; ++partition) {
-    const string& path = paths[partition];
-    LOG(INFO) << "compressing " << path;
-
-    int in_fd = open(path.c_str(), O_RDONLY, 0);
-    TEST_AND_RETURN_FALSE(in_fd >= 0);
-    ScopedFdCloser in_fd_closer(&in_fd);
-
-    for (off_t bytes_left = part_sizes[partition], counter = 0, offset = 0;
-         bytes_left > 0;
-         bytes_left -= chunk_size, ++counter, offset += chunk_size) {
-      DeltaArchiveManifest_InstallOperation* op = NULL;
-      if (partition == 0) {
-        graph->resize(graph->size() + 1);
-        graph->back().file_name = path + StringPrintf("-%" PRIi64, counter);
-        op = &graph->back().op;
-        final_order->push_back(graph->size() - 1);
-      } else {
-        kernel_ops->resize(kernel_ops->size() + 1);
-        op = &kernel_ops->back();
-      }
-
-      vector<char> buf(min(bytes_left, chunk_size));
-      ssize_t bytes_read = -1;
-
-      TEST_AND_RETURN_FALSE(utils::PReadAll(
-          in_fd, &buf[0], buf.size(), offset, &bytes_read));
-      TEST_AND_RETURN_FALSE(bytes_read == static_cast<ssize_t>(buf.size()));
-
-      vector<char> buf_compressed;
-
-      TEST_AND_RETURN_FALSE(BzipCompress(buf, &buf_compressed));
-      const bool compress = buf_compressed.size() < buf.size();
-      const vector<char>& use_buf = compress ? buf_compressed : buf;
-      if (compress) {
-        op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-      } else {
-        op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-      }
-      op->set_data_offset(*data_file_size);
-      TEST_AND_RETURN_FALSE(utils::WriteAll(fd, &use_buf[0], use_buf.size()));
-      *data_file_size += use_buf.size();
-      op->set_data_length(use_buf.size());
-      Extent* dst_extent = op->add_dst_extents();
-      dst_extent->set_start_block(offset / kBlockSize);
-      dst_extent->set_num_blocks(chunk_size / kBlockSize);
-
-      LOG(INFO) << StringPrintf("%.1f", offset * 100.0 / part_sizes[partition])
-                << "% complete (offset: " << offset << ", buf size: "
-                << buf.size() << ")";
-    }
-  }
-
-  return true;
-}
-
 bool DeltaDiffGenerator::GenerateDeltaUpdateFile(
     const string& old_root,
     const string& old_image,
@@ -1480,15 +1402,16 @@
       // Full update
       off_t new_image_size =
           static_cast<off_t>(new_image_block_count) * new_image_block_size;
-      TEST_AND_RETURN_FALSE(ReadFullUpdateFromDisk(&graph,
-                                                   new_kernel_part,
-                                                   new_image,
-                                                   new_image_size,
-                                                   fd,
-                                                   &data_file_size,
-                                                   kFullUpdateChunkSize,
-                                                   &kernel_ops,
-                                                   &final_order));
+      TEST_AND_RETURN_FALSE(FullUpdateGenerator::Run(&graph,
+                                                     new_kernel_part,
+                                                     new_image,
+                                                     new_image_size,
+                                                     fd,
+                                                     &data_file_size,
+                                                     kFullUpdateChunkSize,
+                                                     kBlockSize,
+                                                     &kernel_ops,
+                                                     &final_order));
     }
   }
 
diff --git a/delta_diff_generator.h b/delta_diff_generator.h
index 067ce1f..53d3f87 100644
--- a/delta_diff_generator.h
+++ b/delta_diff_generator.h
@@ -194,23 +194,6 @@
       std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes,
       const std::vector<CutEdgeVertexes>& cuts);
 
-  // Given a new rootfs and kernel (|new_image|, |new_kernel_part|), Reads them
-  // sequentially, creating a full update of chunk_size chunks.  Populates
-  // |graph|, |kernel_ops|, and |final_order|, with data about the update
-  // operations, and writes relevant data to |fd|, updating |data_file_size| as
-  // it does. Only the first |image_size| bytes are read from |new_image|
-  // assuming that this is the actual file system.
-  static bool ReadFullUpdateFromDisk(
-      Graph* graph,
-      const std::string& new_kernel_part,
-      const std::string& new_image,
-      off_t image_size,
-      int fd,
-      off_t* data_file_size,
-      off_t chunk_size,
-      std::vector<DeltaArchiveManifest_InstallOperation>* kernel_ops,
-      std::vector<Vertex::Index>* final_order);
-
   // 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).
   static bool IsNoopOperation(const DeltaArchiveManifest_InstallOperation& op);
diff --git a/delta_performer_unittest.cc b/delta_performer_unittest.cc
index 3c05b1d..37a0c68 100755
--- a/delta_performer_unittest.cc
+++ b/delta_performer_unittest.cc
@@ -18,6 +18,7 @@
 #include "update_engine/delta_diff_generator.h"
 #include "update_engine/delta_performer.h"
 #include "update_engine/extent_ranges.h"
+#include "update_engine/full_update_generator.h"
 #include "update_engine/graph_types.h"
 #include "update_engine/payload_signer.h"
 #include "update_engine/prefs_mock.h"
@@ -113,7 +114,7 @@
   return true;
 }
 
-void DoSmallImageTest(bool full_kernel, bool noop) {
+void DoSmallImageTest(bool full_kernel, bool full_rootfs, bool noop) {
   string a_img, b_img;
   EXPECT_TRUE(utils::MakeTempFile("/tmp/a_img.XXXXXX", &a_img, NULL));
   ScopedPathUnlinker a_img_unlinker(a_img);
@@ -221,8 +222,8 @@
 
     EXPECT_TRUE(
         DeltaDiffGenerator::GenerateDeltaUpdateFile(
-            a_mnt,
-            a_img,
+            full_rootfs ? "" : a_mnt,
+            full_rootfs ? "" : a_img,
             b_mnt,
             b_img,
             full_kernel ? "" : old_kernel,
@@ -278,12 +279,17 @@
       EXPECT_FALSE(manifest.old_kernel_info().hash().empty());
     }
 
+    if (full_rootfs) {
+      EXPECT_FALSE(manifest.has_old_rootfs_info());
+    } else {
+      EXPECT_EQ(image_size, manifest.old_rootfs_info().size());
+      EXPECT_FALSE(manifest.old_rootfs_info().hash().empty());
+    }
+
     EXPECT_EQ(new_kernel_data.size(), manifest.new_kernel_info().size());
-    EXPECT_EQ(image_size, manifest.old_rootfs_info().size());
     EXPECT_EQ(image_size, manifest.new_rootfs_info().size());
 
     EXPECT_FALSE(manifest.new_kernel_info().hash().empty());
-    EXPECT_FALSE(manifest.old_rootfs_info().hash().empty());
     EXPECT_FALSE(manifest.new_rootfs_info().hash().empty());
   }
 
@@ -346,79 +352,19 @@
 }
 
 TEST(DeltaPerformerTest, RunAsRootSmallImageTest) {
-  DoSmallImageTest(false, false);
+  DoSmallImageTest(false, false, false);
 }
 
 TEST(DeltaPerformerTest, RunAsRootFullKernelSmallImageTest) {
-  DoSmallImageTest(true, false);
+  DoSmallImageTest(true, false, false);
+}
+
+TEST(DeltaPerformerTest, RunAsRootFullSmallImageTest) {
+  DoSmallImageTest(true, true, false);
 }
 
 TEST(DeltaPerformerTest, RunAsRootNoopSmallImageTest) {
-  DoSmallImageTest(false, true);
-}
-
-TEST(DeltaPerformerTest, NewFullUpdateTest) {
-  vector<char> new_root(20 * 1024 * 1024);
-  vector<char> new_kern(16 * 1024 * 1024);
-  const off_t kChunkSize = 128 * 1024;
-  FillWithData(&new_root);
-  FillWithData(&new_kern);
-  // Assume hashes take 2 MiB beyond the rootfs.
-  off_t new_rootfs_size = new_root.size() - 2 * 1024 * 1024;
-
-  string new_root_path;
-  EXPECT_TRUE(utils::MakeTempFile("/tmp/NewFullUpdateTest_R.XXXXXX",
-                                  &new_root_path,
-                                  NULL));
-  ScopedPathUnlinker new_root_path_unlinker(new_root_path);
-  EXPECT_TRUE(WriteFileVector(new_root_path, new_root));
-
-  string new_kern_path;
-  EXPECT_TRUE(utils::MakeTempFile("/tmp/NewFullUpdateTest_K.XXXXXX",
-                                  &new_kern_path,
-                                  NULL));
-  ScopedPathUnlinker new_kern_path_unlinker(new_kern_path);
-  EXPECT_TRUE(WriteFileVector(new_kern_path, new_kern));
-
-  string out_blobs_path;
-  int out_blobs_fd;
-  EXPECT_TRUE(utils::MakeTempFile("/tmp/NewFullUpdateTest_D.XXXXXX",
-                                  &out_blobs_path,
-                                  &out_blobs_fd));
-  ScopedPathUnlinker out_blobs_path_unlinker(out_blobs_path);
-  ScopedFdCloser out_blobs_fd_closer(&out_blobs_fd);
-
-  off_t out_blobs_length = 0;
-
-  Graph graph;
-  vector<DeltaArchiveManifest_InstallOperation> kernel_ops;
-  vector<Vertex::Index> final_order;
-
-  EXPECT_TRUE(DeltaDiffGenerator::ReadFullUpdateFromDisk(&graph,
-                                                         new_kern_path,
-                                                         new_root_path,
-                                                         new_rootfs_size,
-                                                         out_blobs_fd,
-                                                         &out_blobs_length,
-                                                         kChunkSize,
-                                                         &kernel_ops,
-                                                         &final_order));
-  EXPECT_EQ(new_rootfs_size / kChunkSize, graph.size());
-  EXPECT_EQ(new_rootfs_size / kChunkSize, final_order.size());
-  EXPECT_EQ(new_kern.size() / kChunkSize, kernel_ops.size());
-  for (off_t i = 0; i < (new_rootfs_size / kChunkSize); ++i) {
-    EXPECT_EQ(i, final_order[i]);
-    EXPECT_EQ(1, graph[i].op.dst_extents_size());
-    EXPECT_EQ(i * kChunkSize / kBlockSize,
-              graph[i].op.dst_extents(0).start_block()) << "i = " << i;
-    EXPECT_EQ(kChunkSize / kBlockSize,
-              graph[i].op.dst_extents(0).num_blocks());
-    if (graph[i].op.type() !=
-        DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
-      EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
-                graph[i].op.type());
-    }
-  }
+  DoSmallImageTest(false, false, true);
 }
 
 TEST(DeltaPerformerTest, IsIdempotentOperationTest) {
diff --git a/full_update_generator.cc b/full_update_generator.cc
new file mode 100644
index 0000000..0140107
--- /dev/null
+++ b/full_update_generator.cc
@@ -0,0 +1,197 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/full_update_generator.h"
+
+#include <inttypes.h>
+#include <fcntl.h>
+
+#include <tr1/memory>
+
+#include <base/string_util.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/utils.h"
+
+using std::deque;
+using std::min;
+using std::max;
+using std::string;
+using std::tr1::shared_ptr;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+// This class encapsulates a full update chunk processing thread. The processor
+// reads a chunk of data from the input file descriptor and compresses it. The
+// processor needs to be started through Start() then waited on through Wait().
+class ChunkProcessor {
+ public:
+  // Read a chunk of |size| bytes from |fd| starting at offset |offset|.
+  ChunkProcessor(int fd, off_t offset, size_t size)
+      : thread_(NULL),
+        fd_(fd),
+        offset_(offset),
+        buffer_in_(size) {}
+  ~ChunkProcessor() { Wait(); }
+
+  off_t offset() const { return offset_; }
+  const vector<char>& buffer_in() const { return buffer_in_; }
+  const vector<char>& buffer_compressed() const { return buffer_compressed_; }
+
+  // Starts the processor. Returns true on success, false on failure.
+  bool Start();
+
+  // Waits for the processor to complete. Returns true on success, false on
+  // failure.
+  bool Wait();
+
+  bool ShouldCompress() const {
+    return buffer_compressed_.size() < buffer_in_.size();
+  }
+
+ private:
+  // Reads the input data into |buffer_in_| and compresses it into
+  // |buffer_compressed_|. Returns true on success, false otherwise.
+  bool ReadAndCompress();
+  static gpointer ReadAndCompressThread(gpointer data);
+
+  GThread* thread_;
+  int fd_;
+  off_t offset_;
+  vector<char> buffer_in_;
+  vector<char> buffer_compressed_;
+
+  DISALLOW_COPY_AND_ASSIGN(ChunkProcessor);
+};
+
+bool ChunkProcessor::Start() {
+  thread_ = g_thread_create(ReadAndCompressThread, this, TRUE, NULL);
+  TEST_AND_RETURN_FALSE(thread_ != NULL);
+  return true;
+}
+
+bool ChunkProcessor::Wait() {
+  if (!thread_) {
+    return false;
+  }
+  gpointer result = g_thread_join(thread_);
+  thread_ = NULL;
+  TEST_AND_RETURN_FALSE(result == this);
+  return true;
+}
+
+gpointer ChunkProcessor::ReadAndCompressThread(gpointer data) {
+  return
+      reinterpret_cast<ChunkProcessor*>(data)->ReadAndCompress() ? data : NULL;
+}
+
+bool ChunkProcessor::ReadAndCompress() {
+  ssize_t bytes_read = -1;
+  TEST_AND_RETURN_FALSE(utils::PReadAll(fd_,
+                                        buffer_in_.data(),
+                                        buffer_in_.size(),
+                                        offset_,
+                                        &bytes_read));
+  TEST_AND_RETURN_FALSE(bytes_read == static_cast<ssize_t>(buffer_in_.size()));
+  TEST_AND_RETURN_FALSE(BzipCompress(buffer_in_, &buffer_compressed_));
+  return true;
+}
+
+}  // namespace
+
+bool FullUpdateGenerator::Run(
+    Graph* graph,
+    const std::string& new_kernel_part,
+    const std::string& new_image,
+    off_t image_size,
+    int fd,
+    off_t* data_file_size,
+    off_t chunk_size,
+    off_t block_size,
+    vector<DeltaArchiveManifest_InstallOperation>* kernel_ops,
+    std::vector<Vertex::Index>* final_order) {
+  TEST_AND_RETURN_FALSE(chunk_size > 0);
+  TEST_AND_RETURN_FALSE((chunk_size % block_size) == 0);
+
+  size_t max_threads = max(sysconf(_SC_NPROCESSORS_ONLN), 4L);
+  LOG(INFO) << "Max threads: " << max_threads;
+
+  // Get the sizes early in the function, so we can fail fast if the user
+  // passed us bad paths.
+  TEST_AND_RETURN_FALSE(image_size >= 0 &&
+                        image_size <= utils::FileSize(new_image));
+  const off_t kernel_size = utils::FileSize(new_kernel_part);
+  TEST_AND_RETURN_FALSE(kernel_size >= 0);
+
+  off_t part_sizes[] = { image_size, kernel_size };
+  string paths[] = { new_image, new_kernel_part };
+
+  for (int partition = 0; partition < 2; ++partition) {
+    const string& path = paths[partition];
+    LOG(INFO) << "compressing " << path;
+
+    int in_fd = open(path.c_str(), O_RDONLY, 0);
+    TEST_AND_RETURN_FALSE(in_fd >= 0);
+    ScopedFdCloser in_fd_closer(&in_fd);
+
+    deque<shared_ptr<ChunkProcessor> > threads;
+
+    off_t bytes_left = part_sizes[partition], counter = 0, offset = 0;
+    while (bytes_left > 0 || !threads.empty()) {
+      // Check and start new chunk processors if possible.
+      while (threads.size() < max_threads && bytes_left > 0) {
+        shared_ptr<ChunkProcessor> processor(
+            new ChunkProcessor(in_fd, offset, min(bytes_left, chunk_size)));
+        threads.push_back(processor);
+        TEST_AND_RETURN_FALSE(processor->Start());
+        bytes_left -= chunk_size;
+        offset += chunk_size;
+      }
+
+      // Need to wait for a chunk processor to complete and process its ouput
+      // before spawning new processors.
+      shared_ptr<ChunkProcessor> processor = threads.front();
+      threads.pop_front();
+      TEST_AND_RETURN_FALSE(processor->Wait());
+
+      DeltaArchiveManifest_InstallOperation* op = NULL;
+      if (partition == 0) {
+        graph->resize(graph->size() + 1);
+        graph->back().file_name =
+            StringPrintf("<rootfs-operation-%" PRIi64 ">", counter++);
+        op = &graph->back().op;
+        final_order->push_back(graph->size() - 1);
+      } else {
+        kernel_ops->resize(kernel_ops->size() + 1);
+        op = &kernel_ops->back();
+      }
+
+      const bool compress = processor->ShouldCompress();
+      const vector<char>& use_buf =
+          compress ? processor->buffer_compressed() : processor->buffer_in();
+      op->set_type(compress ?
+                   DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ :
+                   DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+      op->set_data_offset(*data_file_size);
+      TEST_AND_RETURN_FALSE(utils::WriteAll(fd, &use_buf[0], use_buf.size()));
+      *data_file_size += use_buf.size();
+      op->set_data_length(use_buf.size());
+      Extent* dst_extent = op->add_dst_extents();
+      dst_extent->set_start_block(processor->offset() / block_size);
+      dst_extent->set_num_blocks(chunk_size / block_size);
+
+      LOG(INFO)
+          << StringPrintf("%.1f",
+                          processor->offset() * 100.0 / part_sizes[partition])
+          << "% complete (output size: " << *data_file_size << ")";
+    }
+  }
+
+  return true;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/full_update_generator.h b/full_update_generator.h
new file mode 100644
index 0000000..4b9211c
--- /dev/null
+++ b/full_update_generator.h
@@ -0,0 +1,41 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_FULL_UPDATE_GENERATOR_H__
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_FULL_UPDATE_GENERATOR_H__
+
+#include <glib.h>
+
+#include "update_engine/graph_types.h"
+
+namespace chromeos_update_engine {
+
+class FullUpdateGenerator {
+ public:
+  // Given a new rootfs and kernel (|new_image|, |new_kernel_part|), reads them
+  // sequentially, creating a full update of chunk_size chunks. Populates
+  // |graph|, |kernel_ops|, and |final_order|, with data about the update
+  // operations, and writes relevant data to |fd|, updating |data_file_size| as
+  // it does. Only the first |image_size| bytes are read from |new_image|
+  // assuming that this is the actual file system.
+  static bool Run(
+      Graph* graph,
+      const std::string& new_kernel_part,
+      const std::string& new_image,
+      off_t image_size,
+      int fd,
+      off_t* data_file_size,
+      off_t chunk_size,
+      off_t block_size,
+      std::vector<DeltaArchiveManifest_InstallOperation>* kernel_ops,
+      std::vector<Vertex::Index>* final_order);
+
+ private:
+  // This should never be constructed.
+  DISALLOW_IMPLICIT_CONSTRUCTORS(FullUpdateGenerator);
+};
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_FULL_UPDATE_GENERATOR_H__
diff --git a/full_update_generator_unittest.cc b/full_update_generator_unittest.cc
new file mode 100644
index 0000000..16aa568
--- /dev/null
+++ b/full_update_generator_unittest.cc
@@ -0,0 +1,91 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <string>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/full_update_generator.h"
+#include "update_engine/test_utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+  const size_t kBlockSize = 4096;
+}  // namespace {}
+
+
+class FullUpdateGeneratorTest : public ::testing::Test { };
+
+
+TEST(FullUpdateGeneratorTest, RunTest) {
+  vector<char> new_root(20 * 1024 * 1024);
+  vector<char> new_kern(16 * 1024 * 1024);
+  const off_t kChunkSize = 128 * 1024;
+  FillWithData(&new_root);
+  FillWithData(&new_kern);
+  // Assume hashes take 2 MiB beyond the rootfs.
+  off_t new_rootfs_size = new_root.size() - 2 * 1024 * 1024;
+
+  string new_root_path;
+  EXPECT_TRUE(utils::MakeTempFile("/tmp/NewFullUpdateTest_R.XXXXXX",
+                                  &new_root_path,
+                                  NULL));
+  ScopedPathUnlinker new_root_path_unlinker(new_root_path);
+  EXPECT_TRUE(WriteFileVector(new_root_path, new_root));
+
+  string new_kern_path;
+  EXPECT_TRUE(utils::MakeTempFile("/tmp/NewFullUpdateTest_K.XXXXXX",
+                                  &new_kern_path,
+                                  NULL));
+  ScopedPathUnlinker new_kern_path_unlinker(new_kern_path);
+  EXPECT_TRUE(WriteFileVector(new_kern_path, new_kern));
+
+  string out_blobs_path;
+  int out_blobs_fd;
+  EXPECT_TRUE(utils::MakeTempFile("/tmp/NewFullUpdateTest_D.XXXXXX",
+                                  &out_blobs_path,
+                                  &out_blobs_fd));
+  ScopedPathUnlinker out_blobs_path_unlinker(out_blobs_path);
+  ScopedFdCloser out_blobs_fd_closer(&out_blobs_fd);
+
+  off_t out_blobs_length = 0;
+
+  Graph graph;
+  vector<DeltaArchiveManifest_InstallOperation> kernel_ops;
+  vector<Vertex::Index> final_order;
+
+  EXPECT_TRUE(FullUpdateGenerator::Run(&graph,
+                                       new_kern_path,
+                                       new_root_path,
+                                       new_rootfs_size,
+                                       out_blobs_fd,
+                                       &out_blobs_length,
+                                       kChunkSize,
+                                       kBlockSize,
+                                       &kernel_ops,
+                                       &final_order));
+  EXPECT_EQ(new_rootfs_size / kChunkSize, graph.size());
+  EXPECT_EQ(new_rootfs_size / kChunkSize, final_order.size());
+  EXPECT_EQ(new_kern.size() / kChunkSize, kernel_ops.size());
+  for (off_t i = 0; i < (new_rootfs_size / kChunkSize); ++i) {
+    EXPECT_EQ(i, final_order[i]);
+    EXPECT_EQ(1, graph[i].op.dst_extents_size());
+    EXPECT_EQ(i * kChunkSize / kBlockSize,
+              graph[i].op.dst_extents(0).start_block()) << "i = " << i;
+    EXPECT_EQ(kChunkSize / kBlockSize,
+              graph[i].op.dst_extents(0).num_blocks());
+    if (graph[i].op.type() !=
+        DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+      EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
+                graph[i].op.type());
+    }
+  }
+}
+
+}  // namespace chromeos_update_engine