TBR: derat@chromium.org
diff --git a/delta_diff_generator.cc b/delta_diff_generator.cc
index 6f352c7..45872bc 100644
--- a/delta_diff_generator.cc
+++ b/delta_diff_generator.cc
@@ -72,6 +72,8 @@
       : mode(0),
         uid(0),
         gid(0),
+        nlink(0),
+        inode(0),
         compressed(false),
         offset(-1),
         length(0),
@@ -81,6 +83,14 @@
   uid_t uid;
   gid_t gid;
 
+  // a file may be a potential hardlink if it's not a directory
+  // and it has a link count > 1.
+  bool IsPotentialHardlink() const {
+    return !S_ISDIR(mode) && nlink > 1;
+  }
+  nlink_t nlink;  // number of hard links
+  ino_t inode;
+
   // data
   bool compressed;
   int offset;  // -1 means no data
@@ -102,6 +112,8 @@
   node->mode = stbuf.st_mode;
   node->uid = stbuf.st_uid;
   node->gid = stbuf.st_gid;
+  node->nlink = stbuf.st_nlink;
+  node->inode = stbuf.st_ino;
   if (!S_ISDIR(node->mode)) {
     return true;
   }
@@ -153,11 +165,20 @@
 }
 
 // This converts a Node tree rooted at n into a DeltaArchiveManifest.
-void NodeToDeltaArchiveManifest(Node* n, DeltaArchiveManifest* archive) {
+void NodeToDeltaArchiveManifest(Node* n, DeltaArchiveManifest* archive,
+                                map<ino_t, string>* hard_links,
+                                const string& path) {
   DeltaArchiveManifest_File *f = archive->add_files();
   f->set_mode(n->mode);
   f->set_uid(n->uid);
   f->set_gid(n->gid);
+  if (utils::MapContainsKey(*hard_links, n->inode)) {
+    // We have a hard link
+    CHECK(!S_ISDIR(n->mode));
+    f->set_hardlink_path((*hard_links)[n->inode]);
+  } else if (n->IsPotentialHardlink()) {
+    (*hard_links)[n->inode] = path;
+  }
   if (!S_ISDIR(n->mode))
     return;
   for (unsigned int i = 0; i < n->children.size(); i++) {
@@ -166,7 +187,8 @@
     child->set_index(n->children[i]->node->idx);
   }
   for (unsigned int i = 0; i < n->children.size(); i++) {
-    NodeToDeltaArchiveManifest(n->children[i]->node.get(), archive);
+    NodeToDeltaArchiveManifest(n->children[i]->node.get(), archive, hard_links,
+                               path + "/" + n->children[i]->name);
   }
 }
 
@@ -182,7 +204,8 @@
     const std::string& old_path,
     const std::string& new_path,
     FileWriter* out_file_writer,
-    int* out_file_length) {
+    int* out_file_length,
+    const std::string& force_compress_dev_path) {
   TEST_AND_RETURN_FALSE(file->has_mode());
 
   // Stat the actual file, too
@@ -204,12 +227,14 @@
           old_path + "/" + file_name,
           new_path + "/" + file_name,
           out_file_writer,
-          out_file_length));
+          out_file_length,
+          force_compress_dev_path));
     }
     return true;
   }
 
-  if (S_ISFIFO(file->mode()) || S_ISSOCK(file->mode())) {
+  if (S_ISFIFO(file->mode()) || S_ISSOCK(file->mode()) ||
+      file->has_hardlink_path()) {
     // These don't store any additional data
     return true;
   }
@@ -219,13 +244,13 @@
   bool format_set = false;
   DeltaArchiveManifest_File_DataFormat format;
   if (S_ISLNK(file->mode())) {
-    LOG(INFO) << "link";
     TEST_AND_RETURN_FALSE(EncodeLink(new_path + "/" + file_name, &data));
   } else if (S_ISCHR(file->mode()) || S_ISBLK(file->mode())) {
-    LOG(INFO) << "dev";
-    TEST_AND_RETURN_FALSE(EncodeDev(stbuf, &data));
+    TEST_AND_RETURN_FALSE(EncodeDev(stbuf, &data, &format,
+                                    new_path + "/" + file_name ==
+                                    force_compress_dev_path));
+    format_set = true;
   } else if (S_ISREG(file->mode())) {
-    LOG(INFO) << "reg";
     // regular file. We may use a delta here.
     TEST_AND_RETURN_FALSE(EncodeFile(old_path, new_path, file_name, &format,
                                      &data));
@@ -239,7 +264,7 @@
     LOG(ERROR) << "Unhandled mode type: " << file->mode();
     return false;
   }
-  LOG(INFO) << "data len: " << data.size();
+
   if (!format_set) {
     // Pick a format now
     vector<char> compressed_data;
@@ -276,13 +301,24 @@
   return true;
 }
 
-bool DeltaDiffGenerator::EncodeDev(const struct stat& stbuf,
-                                   std::vector<char>* out) {
+bool DeltaDiffGenerator::EncodeDev(
+    const struct stat& stbuf,
+    vector<char>* out,
+    DeltaArchiveManifest_File_DataFormat* format,
+    bool force_compression) {
   LinuxDevice dev;
   dev.set_major(major(stbuf.st_rdev));
   dev.set_minor(minor(stbuf.st_rdev));
   out->resize(dev.ByteSize());
   TEST_AND_RETURN_FALSE(dev.SerializeToArray(&(*out)[0], out->size()));
+  if (force_compression) {
+    vector<char> compressed;
+    TEST_AND_RETURN_FALSE(GzipCompress(*out, &compressed));
+    out->swap(compressed);
+    *format = DeltaArchiveManifest_File_DataFormat_FULL_GZ;
+  } else {
+    *format = DeltaArchiveManifest_File_DataFormat_FULL;
+  }
   return true;
 }
 
@@ -354,14 +390,17 @@
   int index = 0;
   PopulateChildIndexes(&node, &index);
   DeltaArchiveManifest *ret = new DeltaArchiveManifest;
-  NodeToDeltaArchiveManifest(&node, ret);
+  map<ino_t, string> hard_links;  // inode -> first found path for inode
+  NodeToDeltaArchiveManifest(&node, ret, &hard_links, "");
   return ret;
 }
 
-bool DeltaDiffGenerator::EncodeDataToDeltaFile(DeltaArchiveManifest* archive,
-                                               const std::string& old_path,
-                                               const std::string& new_path,
-                                               const std::string& out_file) {
+bool DeltaDiffGenerator::EncodeDataToDeltaFile(
+    DeltaArchiveManifest* archive,
+    const std::string& old_path,
+    const std::string& new_path,
+    const std::string& out_file,
+    const std::string& force_compress_dev_path) {
   DirectFileWriter out_writer;
   int r = out_writer.Open(out_file.c_str(), O_WRONLY | O_CREAT | O_TRUNC, 0666);
   TEST_AND_RETURN_FALSE_ERRNO(r >= 0);
@@ -386,7 +425,8 @@
                                                   old_path,
                                                   new_path,
                                                   &out_writer,
-                                                  &out_file_length));
+                                                  &out_file_length,
+                                                  force_compress_dev_path));
 
   // Finally, write the protobuf to the end of the file
   string encoded_archive;
diff --git a/delta_diff_generator.h b/delta_diff_generator.h
index 0f73d06..2c355a4 100644
--- a/delta_diff_generator.h
+++ b/delta_diff_generator.h
@@ -33,10 +33,13 @@
   // fill in the missing fields (DeltaArchiveManifest_File_data_*), and
   // write the full delta out to the output file.
   // Returns true on success.
+  // If non-empty, the device at force_compress_dev_path will be compressed.
   static bool EncodeDataToDeltaFile(DeltaArchiveManifest* archive,
                                     const std::string& old_path,
                                     const std::string& new_path,
-                                    const std::string& out_file);
+                                    const std::string& out_file,
+                                    const std::string& force_compress_dev_path);
+
  private:
   // These functions encode all the data about a file that's not already
   // stored in the DeltaArchiveManifest message into the vector 'out'.
@@ -46,7 +49,10 @@
   static bool EncodeLink(const std::string& path, std::vector<char>* out);
   // EncodeDev stores the major and minor device numbers.
   // Specifically it writes a LinuxDevice message.
-  static bool EncodeDev(const struct stat& stbuf, std::vector<char>* out);
+  static bool EncodeDev(
+      const struct stat& stbuf, std::vector<char>* out,
+      DeltaArchiveManifest_File_DataFormat* format,
+      bool force_compression);
   // EncodeFile stores the full data, gzipped data, or a binary diff from
   // the old data. out_data_format will be set to the method used.
   static bool EncodeFile(const std::string& old_dir,
@@ -55,13 +61,16 @@
                          DeltaArchiveManifest_File_DataFormat* out_data_format,
                          std::vector<char>* out);
 
-  static bool WriteFileDiffsToDeltaFile(DeltaArchiveManifest* archive,
-                                        DeltaArchiveManifest_File* file,
-                                        const std::string& file_name,
-                                        const std::string& old_path,
-                                        const std::string& new_path,
-                                        FileWriter* out_file_writer,
-                                        int* out_file_length);
+  // If non-empty, the device at force_compress_dev_path will be compressed.
+  static bool WriteFileDiffsToDeltaFile(
+      DeltaArchiveManifest* archive,
+      DeltaArchiveManifest_File* file,
+      const std::string& file_name,
+      const std::string& old_path,
+      const std::string& new_path,
+      FileWriter* out_file_writer,
+      int* out_file_length,
+      const std::string& force_compress_dev_path);
 
   // This should never be constructed
   DISALLOW_IMPLICIT_CONSTRUCTORS(DeltaDiffGenerator);
diff --git a/delta_diff_generator_unittest.cc b/delta_diff_generator_unittest.cc
index 495bc3e..ef6e7b1 100644
--- a/delta_diff_generator_unittest.cc
+++ b/delta_diff_generator_unittest.cc
@@ -39,6 +39,12 @@
   }
 }
 
+const char* const kWellCompressingFilename =
+    "this_compresses_well_xxxxxxxxxxxxxxxxx"
+    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
+    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
+    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
+    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
 // The following files are generated at the path 'base':
 // /
 //  cdev (c 2 1)
@@ -71,19 +77,24 @@
   EXPECT_EQ(0, System(StringPrintf("mkfifo '%s/dir/subdir/fifo'", base_c)));
   EXPECT_EQ(0, System(StringPrintf("ln -f -s /target '%s/dir/subdir/link'",
                                    base_c)));
+  EXPECT_EQ(0, System(StringPrintf("rm -f '%s/hard_link'", base_c)));
+  EXPECT_EQ(0, System(StringPrintf("ln '%s/hi' '%s/hard_link'",
+                                   base_c, base_c)));
+  EXPECT_EQ(0, System(StringPrintf(
+      "ln -f -s '%s' '%s/compress_link'", kWellCompressingFilename, base_c)));
 
-  // Things that will encode differently:
-  EXPECT_EQ(0, System(StringPrintf("mkdir -p '%s/encoding'", base_c)));
-  EXPECT_EQ(0, System(StringPrintf("echo nochange > '%s/encoding/nochange'",
-                                   base_c)));
-  EXPECT_EQ(0, System(StringPrintf("echo -n > '%s/encoding/onebyte'", base_c)));
-  EXPECT_EQ(0, System(StringPrintf("echo -n > '%s/encoding/long_new'",
-                                   base_c)));
-  // Random 1 MiB byte length file
-  EXPECT_TRUE(WriteFile((base +
-                         "/encoding/long_small_change").c_str(),
-                        reinterpret_cast<const char*>(kRandomString),
-                        sizeof(kRandomString)));
+// Things that will encode differently:
+EXPECT_EQ(0, System(StringPrintf("mkdir -p '%s/encoding'", base_c)));
+EXPECT_EQ(0, System(StringPrintf("echo nochange > '%s/encoding/nochange'",
+                                 base_c)));
+EXPECT_EQ(0, System(StringPrintf("echo -n > '%s/encoding/onebyte'", base_c)));
+EXPECT_EQ(0, System(StringPrintf("echo -n > '%s/encoding/long_new'",
+                                 base_c)));
+// Random 1 MiB byte length file
+EXPECT_TRUE(WriteFile((base +
+                       "/encoding/long_small_change").c_str(),
+                      reinterpret_cast<const char*>(kRandomString),
+                      sizeof(kRandomString)));
 }
 // base points to a folder that was passed to GenerateFilesAtPath().
 // This edits some, so that one can make a diff from the original data
@@ -120,17 +131,20 @@
           (string(cwd) + "/diff-gen-test/new").c_str());
   EXPECT_TRUE(NULL != archive);
 
-  EXPECT_EQ(16, archive->files_size());
+  EXPECT_EQ(18, archive->files_size());
   //DumpProto(archive);
   const DeltaArchiveManifest_File& root = archive->files(0);
   EXPECT_TRUE(S_ISDIR(root.mode()));
   EXPECT_EQ(0, root.uid());
   EXPECT_EQ(0, root.gid());
-  ASSERT_EQ(4, root.children_size());
+  ASSERT_EQ(6, root.children_size());
   EXPECT_EQ("cdev", root.children(0).name());
-  EXPECT_EQ("dir", root.children(1).name());
-  EXPECT_EQ("encoding", root.children(2).name());
-  EXPECT_EQ("hi", root.children(3).name());
+  EXPECT_EQ("compress_link", root.children(1).name());
+  EXPECT_EQ("dir", root.children(2).name());
+  EXPECT_EQ("encoding", root.children(3).name());
+  EXPECT_EQ("hard_link", root.children(4).name());
+  EXPECT_EQ("hi", root.children(5).name());
+  EXPECT_FALSE(root.has_hardlink_path());
   EXPECT_FALSE(root.has_data_format());
   EXPECT_FALSE(root.has_data_offset());
   EXPECT_FALSE(root.has_data_length());
@@ -141,22 +155,47 @@
   EXPECT_TRUE(S_ISCHR(cdev.mode()));
   EXPECT_EQ(0, cdev.uid());
   EXPECT_EQ(0, cdev.gid());
+  EXPECT_FALSE(cdev.has_hardlink_path());
   EXPECT_FALSE(cdev.has_data_format());
   EXPECT_FALSE(cdev.has_data_offset());
   EXPECT_FALSE(cdev.has_data_length());
 
+  const DeltaArchiveManifest_File& compress_link =
+      archive->files(root.children(1).index());
+  EXPECT_EQ(0, compress_link.children_size());
+  EXPECT_TRUE(S_ISLNK(compress_link.mode()));
+  EXPECT_EQ(0, compress_link.uid());
+  EXPECT_EQ(0, compress_link.gid());
+  EXPECT_FALSE(compress_link.has_hardlink_path());
+  EXPECT_FALSE(compress_link.has_data_format());
+  EXPECT_FALSE(compress_link.has_data_offset());
+  EXPECT_FALSE(compress_link.has_data_length());
+
+  const DeltaArchiveManifest_File& hard_link =
+      archive->files(root.children(4).index());
+  EXPECT_EQ(0, hard_link.children_size());
+  EXPECT_TRUE(S_ISREG(hard_link.mode()));
+  EXPECT_EQ(0, hard_link.uid());
+  EXPECT_EQ(0, hard_link.gid());
+  EXPECT_FALSE(hard_link.has_hardlink_path());
+  EXPECT_FALSE(hard_link.has_data_format());
+  EXPECT_FALSE(hard_link.has_data_offset());
+  EXPECT_FALSE(hard_link.has_data_length());
+
   const DeltaArchiveManifest_File& hi =
-      archive->files(root.children(3).index());
+      archive->files(root.children(5).index());
   EXPECT_EQ(0, hi.children_size());
   EXPECT_TRUE(S_ISREG(hi.mode()));
   EXPECT_EQ(0, hi.uid());
   EXPECT_EQ(0, hi.gid());
+  EXPECT_TRUE(hi.has_hardlink_path());
+  EXPECT_EQ("/hard_link", hi.hardlink_path());
   EXPECT_FALSE(hi.has_data_format());
   EXPECT_FALSE(hi.has_data_offset());
   EXPECT_FALSE(hi.has_data_length());
 
   const DeltaArchiveManifest_File& encoding =
-      archive->files(root.children(2).index());
+      archive->files(root.children(3).index());
   EXPECT_TRUE(S_ISDIR(encoding.mode()));
   EXPECT_EQ(0, encoding.uid());
   EXPECT_EQ(0, encoding.gid());
@@ -165,6 +204,7 @@
   EXPECT_EQ("long_small_change", encoding.children(1).name());
   EXPECT_EQ("nochange", encoding.children(2).name());
   EXPECT_EQ("onebyte", encoding.children(3).name());
+  EXPECT_FALSE(encoding.has_hardlink_path());
   EXPECT_FALSE(encoding.has_data_format());
   EXPECT_FALSE(encoding.has_data_offset());
   EXPECT_FALSE(encoding.has_data_length());
@@ -175,6 +215,7 @@
   EXPECT_TRUE(S_ISREG(long_new.mode()));
   EXPECT_EQ(0, long_new.uid());
   EXPECT_EQ(0, long_new.gid());
+  EXPECT_FALSE(long_new.has_hardlink_path());
   EXPECT_FALSE(long_new.has_data_format());
   EXPECT_FALSE(long_new.has_data_offset());
   EXPECT_FALSE(long_new.has_data_length());
@@ -185,6 +226,7 @@
   EXPECT_TRUE(S_ISREG(long_small_change.mode()));
   EXPECT_EQ(0, long_small_change.uid());
   EXPECT_EQ(0, long_small_change.gid());
+  EXPECT_FALSE(long_small_change.has_hardlink_path());
   EXPECT_FALSE(long_small_change.has_data_format());
   EXPECT_FALSE(long_small_change.has_data_offset());
   EXPECT_FALSE(long_small_change.has_data_length());
@@ -195,6 +237,7 @@
   EXPECT_TRUE(S_ISREG(nochange.mode()));
   EXPECT_EQ(0, nochange.uid());
   EXPECT_EQ(0, nochange.gid());
+  EXPECT_FALSE(nochange.has_hardlink_path());
   EXPECT_FALSE(nochange.has_data_format());
   EXPECT_FALSE(nochange.has_data_offset());
   EXPECT_FALSE(nochange.has_data_length());
@@ -205,12 +248,13 @@
   EXPECT_TRUE(S_ISREG(onebyte.mode()));
   EXPECT_EQ(0, onebyte.uid());
   EXPECT_EQ(0, onebyte.gid());
+  EXPECT_FALSE(onebyte.has_hardlink_path());
   EXPECT_FALSE(onebyte.has_data_format());
   EXPECT_FALSE(onebyte.has_data_offset());
   EXPECT_FALSE(onebyte.has_data_length());
 
   const DeltaArchiveManifest_File& dir =
-      archive->files(root.children(1).index());
+      archive->files(root.children(2).index());
   EXPECT_TRUE(S_ISDIR(dir.mode()));
   EXPECT_EQ(0, dir.uid());
   EXPECT_EQ(0, dir.gid());
@@ -220,6 +264,7 @@
   EXPECT_EQ("hello", dir.children(2).name());
   EXPECT_EQ("newempty", dir.children(3).name());
   EXPECT_EQ("subdir", dir.children(4).name());
+  EXPECT_FALSE(dir.has_hardlink_path());
   EXPECT_FALSE(dir.has_data_format());
   EXPECT_FALSE(dir.has_data_offset());
   EXPECT_FALSE(dir.has_data_length());
@@ -230,6 +275,7 @@
   EXPECT_TRUE(S_ISBLK(bdev.mode()));
   EXPECT_EQ(0, bdev.uid());
   EXPECT_EQ(0, bdev.gid());
+  EXPECT_FALSE(bdev.has_hardlink_path());
   EXPECT_FALSE(bdev.has_data_format());
   EXPECT_FALSE(bdev.has_data_offset());
   EXPECT_FALSE(bdev.has_data_length());
@@ -240,6 +286,7 @@
   EXPECT_TRUE(S_ISDIR(emptydir.mode()));
   EXPECT_EQ(501, emptydir.uid());
   EXPECT_EQ(503, emptydir.gid());
+  EXPECT_FALSE(emptydir.has_hardlink_path());
   EXPECT_FALSE(emptydir.has_data_format());
   EXPECT_FALSE(emptydir.has_data_offset());
   EXPECT_FALSE(emptydir.has_data_length());
@@ -250,6 +297,7 @@
   EXPECT_TRUE(S_ISREG(hello.mode()));
   EXPECT_EQ(0, hello.uid());
   EXPECT_EQ(0, hello.gid());
+  EXPECT_FALSE(hello.has_hardlink_path());
   EXPECT_FALSE(hello.has_data_format());
   EXPECT_FALSE(hello.has_data_offset());
   EXPECT_FALSE(hello.has_data_length());
@@ -260,6 +308,7 @@
   EXPECT_TRUE(S_ISREG(newempty.mode()));
   EXPECT_EQ(0, newempty.uid());
   EXPECT_EQ(0, newempty.gid());
+  EXPECT_FALSE(newempty.has_hardlink_path());
   EXPECT_FALSE(newempty.has_data_format());
   EXPECT_FALSE(newempty.has_data_offset());
   EXPECT_FALSE(newempty.has_data_length());
@@ -272,6 +321,7 @@
   EXPECT_TRUE(S_ISDIR(subdir.mode()));
   EXPECT_EQ(0, subdir.uid());
   EXPECT_EQ(0, subdir.gid());
+  EXPECT_FALSE(subdir.has_hardlink_path());
   EXPECT_FALSE(subdir.has_data_format());
   EXPECT_FALSE(subdir.has_data_offset());
   EXPECT_FALSE(subdir.has_data_length());
@@ -282,6 +332,7 @@
   EXPECT_TRUE(S_ISFIFO(fifo.mode()));
   EXPECT_EQ(0, fifo.uid());
   EXPECT_EQ(0, fifo.gid());
+  EXPECT_FALSE(fifo.has_hardlink_path());
   EXPECT_FALSE(fifo.has_data_format());
   EXPECT_FALSE(fifo.has_data_offset());
   EXPECT_FALSE(fifo.has_data_length());
@@ -292,6 +343,7 @@
   EXPECT_TRUE(S_ISLNK(link.mode()));
   EXPECT_EQ(0, link.uid());
   EXPECT_EQ(0, link.gid());
+  EXPECT_FALSE(link.has_hardlink_path());
   EXPECT_FALSE(link.has_data_format());
   EXPECT_FALSE(link.has_data_offset());
   EXPECT_FALSE(link.has_data_length());
@@ -316,19 +368,23 @@
       archive,
       string(cwd) + "/diff-gen-test/old",
       string(cwd) + "/diff-gen-test/new",
-      string(cwd) + "/diff-gen-test/out.dat"));
+      string(cwd) + "/diff-gen-test/out.dat",
+      ""));
 
-  EXPECT_EQ(16, archive->files_size());
+  EXPECT_EQ(18, archive->files_size());
 
   const DeltaArchiveManifest_File& root = archive->files(0);
   EXPECT_TRUE(S_ISDIR(root.mode()));
   EXPECT_EQ(0, root.uid());
   EXPECT_EQ(0, root.gid());
-  ASSERT_EQ(4, root.children_size());
+  ASSERT_EQ(6, root.children_size());
   EXPECT_EQ("cdev", root.children(0).name());
-  EXPECT_EQ("dir", root.children(1).name());
-  EXPECT_EQ("encoding", root.children(2).name());
-  EXPECT_EQ("hi", root.children(3).name());
+  EXPECT_EQ("compress_link", root.children(1).name());
+  EXPECT_EQ("dir", root.children(2).name());
+  EXPECT_EQ("encoding", root.children(3).name());
+  EXPECT_EQ("hard_link", root.children(4).name());
+  EXPECT_EQ("hi", root.children(5).name());
+  EXPECT_FALSE(root.has_hardlink_path());
   EXPECT_FALSE(root.has_data_format());
   EXPECT_FALSE(root.has_data_offset());
   EXPECT_FALSE(root.has_data_length());
@@ -344,21 +400,49 @@
   EXPECT_TRUE(cdev.has_data_offset());
   ASSERT_TRUE(cdev.has_data_length());
   EXPECT_GT(cdev.data_length(), 0);
+  EXPECT_FALSE(cdev.has_hardlink_path());
+
+  const DeltaArchiveManifest_File& compress_link =
+      archive->files(root.children(1).index());
+  EXPECT_EQ(0, compress_link.children_size());
+  EXPECT_TRUE(S_ISLNK(compress_link.mode()));
+  EXPECT_EQ(0, compress_link.uid());
+  EXPECT_EQ(0, compress_link.gid());
+  ASSERT_TRUE(compress_link.has_data_format());
+  EXPECT_EQ(DeltaArchiveManifest_File_DataFormat_FULL_GZ,
+            compress_link.data_format());
+  EXPECT_TRUE(compress_link.has_data_offset());
+  ASSERT_TRUE(compress_link.has_data_length());
+  EXPECT_GT(compress_link.data_length(), 0);
+  EXPECT_FALSE(compress_link.has_hardlink_path());
+
+  const DeltaArchiveManifest_File& hard_link =
+      archive->files(root.children(4).index());
+  EXPECT_EQ(0, hard_link.children_size());
+  EXPECT_TRUE(S_ISREG(hard_link.mode()));
+  EXPECT_EQ(0, hard_link.uid());
+  EXPECT_EQ(0, hard_link.gid());
+  ASSERT_TRUE(hard_link.has_data_format());
+  EXPECT_EQ(DeltaArchiveManifest_File_DataFormat_FULL, hard_link.data_format());
+  EXPECT_TRUE(hard_link.has_data_offset());
+  ASSERT_TRUE(hard_link.has_data_length());
+  EXPECT_GT(hard_link.data_length(), 0);
+  EXPECT_FALSE(hard_link.has_hardlink_path());
 
   const DeltaArchiveManifest_File& hi =
-      archive->files(root.children(3).index());
+      archive->files(root.children(5).index());
   EXPECT_EQ(0, hi.children_size());
   EXPECT_TRUE(S_ISREG(hi.mode()));
   EXPECT_EQ(0, hi.uid());
   EXPECT_EQ(0, hi.gid());
-  ASSERT_TRUE(hi.has_data_format());
-  EXPECT_EQ(DeltaArchiveManifest_File_DataFormat_FULL, hi.data_format());
-  EXPECT_TRUE(hi.has_data_offset());
-  ASSERT_TRUE(hi.has_data_length());
-  EXPECT_GT(hi.data_length(), 0);
+  EXPECT_FALSE(hi.has_data_format());
+  EXPECT_FALSE(hi.has_data_offset());
+  EXPECT_FALSE(hi.has_data_length());
+  EXPECT_TRUE(hi.has_hardlink_path());
+  EXPECT_EQ("/hard_link", hi.hardlink_path());
 
   const DeltaArchiveManifest_File& encoding =
-      archive->files(root.children(2).index());
+      archive->files(root.children(3).index());
   EXPECT_TRUE(S_ISDIR(encoding.mode()));
   EXPECT_EQ(0, encoding.uid());
   EXPECT_EQ(0, encoding.gid());
@@ -370,6 +454,7 @@
   EXPECT_FALSE(encoding.has_data_format());
   EXPECT_FALSE(encoding.has_data_offset());
   EXPECT_FALSE(encoding.has_data_length());
+  EXPECT_FALSE(encoding.has_hardlink_path());
 
   const DeltaArchiveManifest_File& long_new =
       archive->files(encoding.children(0).index());
@@ -382,6 +467,7 @@
             long_new.data_format());
   EXPECT_TRUE(long_new.has_data_offset());
   EXPECT_TRUE(long_new.has_data_length());
+  EXPECT_FALSE(long_new.has_hardlink_path());
 
   const DeltaArchiveManifest_File& long_small_change =
       archive->files(encoding.children(1).index());
@@ -394,6 +480,7 @@
             long_small_change.data_format());
   EXPECT_TRUE(long_small_change.has_data_offset());
   EXPECT_TRUE(long_small_change.has_data_length());
+  EXPECT_FALSE(long_small_change.has_hardlink_path());
 
   const DeltaArchiveManifest_File& nochange =
       archive->files(encoding.children(2).index());
@@ -405,6 +492,7 @@
   EXPECT_EQ(DeltaArchiveManifest_File_DataFormat_FULL, nochange.data_format());
   EXPECT_TRUE(nochange.has_data_offset());
   EXPECT_TRUE(nochange.has_data_length());
+  EXPECT_FALSE(nochange.has_hardlink_path());
 
   const DeltaArchiveManifest_File& onebyte =
       archive->files(encoding.children(3).index());
@@ -417,9 +505,10 @@
   EXPECT_TRUE(onebyte.has_data_offset());
   EXPECT_TRUE(onebyte.has_data_length());
   EXPECT_EQ(1, onebyte.data_length());
+  EXPECT_FALSE(onebyte.has_hardlink_path());
 
   const DeltaArchiveManifest_File& dir =
-      archive->files(root.children(1).index());
+      archive->files(root.children(2).index());
   EXPECT_TRUE(S_ISDIR(dir.mode()));
   EXPECT_EQ(0, dir.uid());
   EXPECT_EQ(0, dir.gid());
@@ -432,6 +521,7 @@
   EXPECT_FALSE(dir.has_data_format());
   EXPECT_FALSE(dir.has_data_offset());
   EXPECT_FALSE(dir.has_data_length());
+  EXPECT_FALSE(dir.has_hardlink_path());
 
   const DeltaArchiveManifest_File& bdev =
       archive->files(dir.children(0).index());
@@ -444,6 +534,7 @@
   EXPECT_TRUE(bdev.has_data_offset());
   ASSERT_TRUE(bdev.has_data_length());
   EXPECT_GT(bdev.data_length(), 0);
+  EXPECT_FALSE(bdev.has_hardlink_path());
 
   const DeltaArchiveManifest_File& emptydir =
       archive->files(dir.children(1).index());
@@ -454,6 +545,7 @@
   EXPECT_FALSE(emptydir.has_data_format());
   EXPECT_FALSE(emptydir.has_data_offset());
   EXPECT_FALSE(emptydir.has_data_length());
+  EXPECT_FALSE(emptydir.has_hardlink_path());
 
   const DeltaArchiveManifest_File& hello =
       archive->files(dir.children(2).index());
@@ -466,6 +558,7 @@
   EXPECT_TRUE(hello.has_data_offset());
   ASSERT_TRUE(hello.has_data_length());
   EXPECT_GT(hello.data_length(), 0);
+  EXPECT_FALSE(hello.has_hardlink_path());
 
   const DeltaArchiveManifest_File& newempty =
       archive->files(dir.children(3).index());
@@ -476,6 +569,7 @@
   EXPECT_FALSE(newempty.has_data_format());
   EXPECT_FALSE(newempty.has_data_offset());
   EXPECT_FALSE(newempty.has_data_length());
+  EXPECT_FALSE(newempty.has_hardlink_path());
 
   const DeltaArchiveManifest_File& subdir =
       archive->files(dir.children(4).index());
@@ -488,6 +582,7 @@
   EXPECT_FALSE(subdir.has_data_format());
   EXPECT_FALSE(subdir.has_data_offset());
   EXPECT_FALSE(subdir.has_data_length());
+  EXPECT_FALSE(subdir.has_hardlink_path());
 
   const DeltaArchiveManifest_File& fifo =
       archive->files(subdir.children(0).index());
@@ -498,6 +593,7 @@
   EXPECT_FALSE(fifo.has_data_format());
   EXPECT_FALSE(fifo.has_data_offset());
   EXPECT_FALSE(fifo.has_data_length());
+  EXPECT_FALSE(fifo.has_hardlink_path());
 
   const DeltaArchiveManifest_File& link =
       archive->files(subdir.children(1).index());
@@ -510,6 +606,7 @@
   EXPECT_TRUE(link.has_data_offset());
   ASSERT_TRUE(link.has_data_length());
   EXPECT_GT(link.data_length(), 0);
+  EXPECT_FALSE(link.has_hardlink_path());
 }
 
 class DeltaDiffParserTest : public ::testing::Test {
@@ -569,7 +666,8 @@
       archive,
       string(cwd) + "/diff-gen-test/old",
       string(cwd) + "/diff-gen-test/new",
-      string(cwd) + "/diff-gen-test/out.dat"));
+      string(cwd) + "/diff-gen-test/out.dat",
+      ""));
   // parse the file
 
   DeltaDiffParser parser(string(cwd) + "/diff-gen-test/out.dat");
@@ -578,6 +676,7 @@
   string expected_paths[] = {
     "",
     "/cdev",
+    "/compress_link",
     "/dir",
     "/dir/bdev",
     "/dir/emptydir",
@@ -591,6 +690,7 @@
     "/encoding/long_small_change",
     "/encoding/nochange",
     "/encoding/onebyte",
+    "/hard_link",
     "/hi"
   };
   for (unsigned int i = 0;
@@ -646,6 +746,16 @@
   EXPECT_EQ(linux_device.major(), 2);
   EXPECT_EQ(linux_device.minor(), 1);
 
+  // compress_link
+  file = parser.GetFileAtPath("/compress_link");
+  EXPECT_TRUE(S_ISLNK(file.mode()));
+  EXPECT_TRUE(file.has_data_format());
+  EXPECT_EQ(DeltaArchiveManifest_File_DataFormat_FULL_GZ, file.data_format());
+  EXPECT_EQ(kWellCompressingFilename,
+            GzipDecompressToString(ReadFilePart(string(cwd) +
+                                                "/diff-gen-test/out.dat",
+                                                file.data_offset(),
+                                                file.data_length())));
   // dir
   file = parser.GetFileAtPath("/dir");
   EXPECT_TRUE(S_ISDIR(file.mode()));
@@ -764,8 +874,8 @@
                                       file.data_offset(),
                                       file.data_length()));
 
-  // hi
-  file = parser.GetFileAtPath("/hi");
+  // hard_link
+  file = parser.GetFileAtPath("/hard_link");
   EXPECT_TRUE(S_ISREG(file.mode()));
   EXPECT_TRUE(file.has_data_format());
   EXPECT_EQ(DeltaArchiveManifest_File_DataFormat_FULL, file.data_format());
@@ -773,6 +883,13 @@
                                             "/diff-gen-test/out.dat",
                                             file.data_offset(),
                                             file.data_length()));
+
+  // hi
+  file = parser.GetFileAtPath("/hi");
+  EXPECT_TRUE(S_ISREG(file.mode()));
+  EXPECT_FALSE(file.has_data_format());
+  EXPECT_TRUE(file.has_hardlink_path());
+  EXPECT_EQ("/hard_link", file.hardlink_path());
 }
 
 TEST_F(DeltaDiffParserTest, FakerootInvalidTest) {
diff --git a/install_action.cc b/install_action.cc
index 9c644df..c70867e 100644
--- a/install_action.cc
+++ b/install_action.cc
@@ -63,11 +63,14 @@
   ScopedFilesystemUnmounter filesystem_unmounter(mountpoint);
 
   {
-    // iterate through existing fs, deleting unneeded files
+    // Iterate through existing fs, deleting unneeded files
+    // Delete files that don't exist in the update, or exist but are
+    // hard links.
     FilesystemIterator iter(mountpoint,
                             utils::SetWithValue<string>("/lost+found"));
     for (; !iter.IsEnd(); iter.Increment()) {
-      if (!parser.ContainsPath(iter.GetPartialPath())) {
+      if (!parser.ContainsPath(iter.GetPartialPath()) ||
+          parser.GetFileAtPath(iter.GetPartialPath()).has_hardlink_path()) {
         VLOG(1) << "install removing local path: " << iter.GetFullPath();
         TEST_AND_RETURN(utils::RecursiveUnlinkDir(iter.GetFullPath()));
       }
@@ -96,7 +99,12 @@
   TEST_AND_RETURN_FALSE_ERRNO((result == 0) || (errno == ENOENT));
   bool exists = (result == 0);
   // Create the proper file
-  if (S_ISDIR(file.mode())) {
+  if (file.has_hardlink_path()) {
+    TEST_AND_RETURN_FALSE(file.has_hardlink_path());
+    TEST_AND_RETURN_FALSE_ERRNO(link(
+        (mountpoint + file.hardlink_path()).c_str(),
+        (mountpoint + path).c_str()) == 0);
+  } else if (S_ISDIR(file.mode())) {
     if (!exists) {
       TEST_AND_RETURN_FALSE_ERRNO(
           (mkdir((mountpoint + path).c_str(), file.mode())) == 0);
@@ -186,6 +194,7 @@
   dev_t dev = 0;
   if (S_ISCHR(file.mode()) || S_ISBLK(file.mode())) {
     vector<char> dev_proto;
+    TEST_AND_RETURN_FALSE(file.has_data_format());
     TEST_AND_RETURN_FALSE(parser.ReadDataVector(file.data_offset(),
                                                 file.data_length(),
                                                 &dev_proto));
diff --git a/install_action_unittest.cc b/install_action_unittest.cc
index dde15ea..6f2cf2d 100644
--- a/install_action_unittest.cc
+++ b/install_action_unittest.cc
@@ -5,6 +5,7 @@
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <errno.h>
+#include <utime.h>
 #include <set>
 #include <string>
 #include <vector>
@@ -16,7 +17,10 @@
 #include "update_engine/test_utils.h"
 #include "update_engine/utils.h"
 
+using chromeos_update_engine::DeltaDiffGenerator;
+using chromeos_update_engine::kRandomString;
 using chromeos_update_engine::System;
+using chromeos_update_engine::WriteFile;
 using std::set;
 using std::string;
 using std::vector;
@@ -24,6 +28,8 @@
 namespace {
 void GenerateFilesAtPath(const string& base) {
   EXPECT_EQ(0, System(StringPrintf("echo hi > %s/hi", base.c_str())));
+  EXPECT_EQ(0, System(StringPrintf("ln %s/hi %s/hard_link", base.c_str(),
+                                   base.c_str())));
   EXPECT_EQ(0, System(StringPrintf("mkdir -p %s/dir", base.c_str())));
   EXPECT_EQ(0, System(StringPrintf("echo hello > %s/dir/hello", base.c_str())));
   EXPECT_EQ(0, System(StringPrintf("echo -n > %s/dir/newempty", base.c_str())));
@@ -41,6 +47,9 @@
   EXPECT_EQ(0, System(StringPrintf("mkfifo %s/dir/subdir/fifo", base.c_str())));
   EXPECT_EQ(0, System(StringPrintf("ln -f -s /target %s/dir/subdir/link",
                                    base.c_str())));
+  EXPECT_TRUE(WriteFile((base + "/big_file").c_str(),
+                        reinterpret_cast<const char*>(kRandomString),
+                        sizeof(kRandomString)));
 }
 
 // Returns true if files at paths a, b are equal and there are no errors.
@@ -56,6 +65,8 @@
   TEST_AND_RETURN_FALSE(a_stbuf.st_mode == b_stbuf.st_mode);
   if (S_ISBLK(a_stbuf.st_mode) || S_ISCHR(a_stbuf.st_mode))
     TEST_AND_RETURN_FALSE(a_stbuf.st_rdev == b_stbuf.st_rdev);
+  if (!S_ISDIR(a_stbuf.st_mode))
+    TEST_AND_RETURN_FALSE(a_stbuf.st_nlink == b_stbuf.st_nlink);
   if (!S_ISREG(a_stbuf.st_mode)) {
     return true;
   }
@@ -113,6 +124,24 @@
     }
     EXPECT_TRUE(WriteFileVector(new_dir + "/dir/bigfile", buf));
   }
+  const char* const new_dir_cstr = new_dir.c_str();
+  EXPECT_EQ(0, System(StringPrintf("mkdir -p '%s/newdir'", new_dir_cstr)));
+  EXPECT_EQ(0, System(StringPrintf("mkdir -p '%s/newdir/x'", new_dir_cstr)));
+  EXPECT_EQ(0, System(StringPrintf("echo -n foo > '%s/newdir/x/file'",
+                                   new_dir_cstr)));
+  EXPECT_EQ(0, System(StringPrintf("echo -n x >> '%s/big_file'",
+                                   new_dir_cstr)));
+  // Make a symlink that compresses well:
+  EXPECT_EQ(0, System(StringPrintf(
+      "ln -s "
+      "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
+      "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
+      "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx "
+      "'%s/compress_sym'", new_dir_cstr)));
+
+  // Make a device that will compress
+  EXPECT_EQ(0, mknod((new_dir + "/bdev_gz").c_str(), S_IFCHR | 0644, 0));
+
   // Make a diff
   DeltaArchiveManifest* delta =
       DeltaDiffGenerator::EncodeMetadataToProtoBuffer(new_dir.c_str());
@@ -120,7 +149,8 @@
   EXPECT_TRUE(DeltaDiffGenerator::EncodeDataToDeltaFile(delta,
                                                         original_dir,
                                                         new_dir,
-                                                        "delta"));
+                                                        "delta",
+                                                        new_dir + "/bdev_gz"));
 
   ASSERT_EQ(0, System(string("umount ") + original_dir));
 
@@ -174,15 +204,70 @@
   }
   LOG(INFO) << "new_count = " << new_count;
   EXPECT_EQ(new_count, original_count);
-  EXPECT_EQ(12, original_count);  // 12 files in each dir
+  EXPECT_EQ(19, original_count);
 
-  ASSERT_EQ(0, System(string("umount ") + original_dir));
+  // Make sure hard-link installed properly
+  {
+    struct stat hard_link_stbuf;
+    struct stat hi_stbuf;
+    EXPECT_EQ(0, lstat((string(new_dir) + "/hard_link").c_str(),
+                       &hard_link_stbuf));
+    EXPECT_EQ(0, lstat((string(new_dir) + "/hi").c_str(), &hi_stbuf));
+    EXPECT_EQ(hard_link_stbuf.st_mode, hi_stbuf.st_mode);
+    EXPECT_EQ(2, hard_link_stbuf.st_nlink);
+    EXPECT_EQ(2, hi_stbuf.st_nlink);
+    EXPECT_EQ(hi_stbuf.st_ino, hard_link_stbuf.st_ino);
+  }
+
+  EXPECT_EQ(0, System(string("umount ") + original_dir));
 
   // Cleanup generated files
-  ASSERT_EQ(0, System(string("rm -rf ") + original_dir));
-  ASSERT_EQ(0, System(string("rm -rf ") + new_dir));
+  EXPECT_EQ(0, System(string("rm -rf ") + original_dir));
+  EXPECT_EQ(0, System(string("rm -rf ") + new_dir));
   EXPECT_EQ(0, System(string("rm -f ") + original_image));
-  ASSERT_EQ(0, system("rm -f delta"));
+  EXPECT_EQ(0, system("rm -f delta"));
+}
+
+TEST(InstallActionTest, FullUpdateTest) {
+  ObjectFeederAction<InstallPlan> feeder_action;
+  InstallAction install_action;
+  ObjectCollectorAction<string> collector_action;
+
+  BondActions(&feeder_action, &install_action);
+  BondActions(&install_action, &collector_action);
+
+  ActionProcessor processor;
+  processor.EnqueueAction(&feeder_action);
+  processor.EnqueueAction(&install_action);
+  processor.EnqueueAction(&collector_action);
+
+  InstallPlan install_plan(true, "", "", "delta", "install_path");
+  feeder_action.set_obj(install_plan);
+
+  processor.StartProcessing();
+  EXPECT_FALSE(processor.IsRunning()) << "Update to handle async actions";
+  EXPECT_EQ("install_path", collector_action.object());
+}
+
+TEST(InstallActionTest, InvalidDeltaFileTest) {
+  ObjectFeederAction<InstallPlan> feeder_action;
+  InstallAction install_action;
+  ObjectCollectorAction<string> collector_action;
+
+  BondActions(&feeder_action, &install_action);
+  BondActions(&install_action, &collector_action);
+
+  ActionProcessor processor;
+  processor.EnqueueAction(&feeder_action);
+  processor.EnqueueAction(&install_action);
+  processor.EnqueueAction(&collector_action);
+
+  InstallPlan install_plan(false, "", "", "no_such_file", "install_path");
+  feeder_action.set_obj(install_plan);
+
+  processor.StartProcessing();
+  EXPECT_FALSE(processor.IsRunning()) << "Update to handle async actions";
+  EXPECT_TRUE(collector_action.object().empty());
 }
 
 }  // namespace chromeos_update_engine
diff --git a/update_metadata.proto b/update_metadata.proto
index 48935d8..61b4965 100644
--- a/update_metadata.proto
+++ b/update_metadata.proto
@@ -107,6 +107,13 @@
     optional uint32 data_offset = 5;
     // The length of the data in the delta file
     optional uint32 data_length = 6;
+    
+    // When a file is a hard link, hardlink_path exists and
+    // is the path within the DeltaArchiveManifest to the "original" file.
+    // When iterating through a DeltaArchiveManifest,  you will be guaranteed
+    // to hit a hardlink only after you've hit the path to the first file.
+    // Directories can't be hardlinked.
+    optional string hardlink_path = 8;
 
     message Child {
       // A File that's a directory (and only those types of File objects)
@@ -116,7 +123,7 @@
       // Index into DeltaArchiveManifest.files for the File object of the child.
       required uint32 index = 2;
     }
-    repeated Child children = 7;
+    repeated Child children = 9;
   }
   repeated File files = 1;
 }