AU: Try delta updates first, then full updates

src/platform/update_engine/delta_diff_generator.cc

 // Copyright (c) 2009 The Chromium 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/delta_diff_generator.h"
 #include <dirent.h>
 #include <endian.h>
 #include <errno.h>
 #include <stdio.h>
 #include <unistd.h>
 #include <algorithm>
+#include <map>
+#include <set>
+#include <string>
 #include <vector>
 #include <tr1/memory>
 #include <zlib.h>
 #include "chromeos/obsolete_logging.h"
 #include "base/scoped_ptr.h"
 #include "update_engine/delta_diff_parser.h"
 #include "update_engine/gzip.h"
 #include "update_engine/subprocess.h"
 #include "update_engine/utils.h"
 
+using std::map;
+using std::set;
+using std::string;
 using std::vector;
 using std::tr1::shared_ptr;
 using chromeos_update_engine::DeltaArchiveManifest;
 
 namespace chromeos_update_engine {
 
 namespace {
+
+const char* kBsdiffPath = "/usr/bin/bsdiff";
+
 // These structs and methods are helpers for EncodeDataToDeltaFile()
 
 // Before moving the data into a proto buffer, the data is stored in
 // memory in these Node and Child structures.
 
 // Each Node struct represents a file on disk (which can be regular file,
 // directory, fifo, socket, symlink, etc). Nodes that contain children
 // (just directories) will have a vector of Child objects. Each child
 // object has a filename and a pointer to the associated Node. Thus,
 // filenames for files are stored with their parents, not as part of
@@ skipping 154 matching lines @@
 }
 
 }  // namespace {}
 
 // For each file in archive, write a delta for it into out_file
 // and update 'file' to refer to the delta.
 // This is a recursive function. Returns true on success.
 bool DeltaDiffGenerator::WriteFileDiffsToDeltaFile(
     DeltaArchiveManifest* archive,
     DeltaArchiveManifest_File* file,
-    const std::string& file_name,
-    const std::string& old_path,
-    const std::string& new_path,
+    const string& file_name,
+    const string& old_path,
+    const string& new_path,
     FileWriter* out_file_writer,
     int* out_file_length,
-    const std::string& force_compress_dev_path) {
+    set<string> always_full_target_paths,
+    const string& force_compress_dev_path) {
   TEST_AND_RETURN_FALSE(file->has_mode());
 
   // Stat the actual file, too
   struct stat stbuf;
   TEST_AND_RETURN_FALSE_ERRNO(lstat((new_path + "/" + file_name).c_str(),
                                     &stbuf) == 0);
   TEST_AND_RETURN_FALSE(stbuf.st_mode == file->mode());
 
   // See if we're a directory or not
   if (S_ISDIR(file->mode())) {
     for (int i = 0; i < file->children_size(); i++) {
       DeltaArchiveManifest_File_Child* child = file->mutable_children(i);
       DeltaArchiveManifest_File* child_file =
           archive->mutable_files(child->index());
+      string recurse_old_path = old_path;
+      string recurse_new_path = new_path;
+      if (!file_name.empty()) {
+        recurse_new_path += "/" + file_name;
+        recurse_old_path += "/" + file_name;
+      }
       TEST_AND_RETURN_FALSE(WriteFileDiffsToDeltaFile(
           archive,
           child_file,
           child->name(),
-          old_path + "/" + file_name,
-          new_path + "/" + file_name,
+          recurse_old_path,
+          recurse_new_path,
           out_file_writer,
           out_file_length,
+          always_full_target_paths,
           force_compress_dev_path));
     }
     return true;
   }
 
   if (S_ISFIFO(file->mode()) || S_ISSOCK(file->mode()) ||
       file->has_hardlink_path()) {
     // These don't store any additional data
     return true;
   }
 
   vector<char> data;
   bool should_compress = true;
   bool format_set = false;
   DeltaArchiveManifest_File_DataFormat format;
   if (S_ISLNK(file->mode())) {
     TEST_AND_RETURN_FALSE(EncodeLink(new_path + "/" + file_name, &data));
   } else if (S_ISCHR(file->mode()) || S_ISBLK(file->mode())) {
     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())) {
     // regular file. We may use a delta here.
-    TEST_AND_RETURN_FALSE(EncodeFile(old_path, new_path, file_name, &format,
-                                     &data));
+    const bool avoid_diff = utils::SetContainsKey(always_full_target_paths,
+                                                  new_path + "/" + file_name);
+    bool no_change = false;
+    TEST_AND_RETURN_FALSE(EncodeFile(old_path, new_path, file_name,
+                                     avoid_diff, &format, &data, &no_change));
+    if (no_change) {
+      // No data change. We're done!
+      return true;
+    }
     should_compress = false;
     format_set = true;
     if ((format == DeltaArchiveManifest_File_DataFormat_BSDIFF) ||
         (format == DeltaArchiveManifest_File_DataFormat_FULL_GZ))
       TEST_AND_RETURN_FALSE(!data.empty());
   } else {
     // Should never get here; unhandled mode type.
     LOG(ERROR) << "Unhandled mode type: " << file->mode();
     return false;
   }
 
   if (!format_set) {
     // Pick a format now
     vector<char> compressed_data;
     TEST_AND_RETURN_FALSE(GzipCompress(data, &compressed_data));
     if (compressed_data.size() < data.size()) {
       format = DeltaArchiveManifest_File_DataFormat_FULL_GZ;
       data.swap(compressed_data);
     } else {
       format = DeltaArchiveManifest_File_DataFormat_FULL;
     }
     format_set = true;
   }
 
-  if (!data.empty()) {
-    TEST_AND_RETURN_FALSE(format_set);
-    file->set_data_format(format);
-    file->set_data_offset(*out_file_length);
-    TEST_AND_RETURN_FALSE(static_cast<ssize_t>(data.size()) ==
-                          out_file_writer->Write(&data[0], data.size()));
-    file->set_data_length(data.size());
-    *out_file_length += data.size();
-  }
+  TEST_AND_RETURN_FALSE(format_set);
+  file->set_data_format(format);
+  file->set_data_offset(*out_file_length);
+  TEST_AND_RETURN_FALSE(static_cast<ssize_t>(data.size()) ==
+                        out_file_writer->Write(&data[0], data.size()));
+  file->set_data_length(data.size());
+  *out_file_length += data.size();
   return true;
 }
 
-bool DeltaDiffGenerator::EncodeLink(const std::string& path,
-                                    std::vector<char>* out) {
+bool DeltaDiffGenerator::EncodeLink(const string& path, vector<char>* out) {
   // Store symlink path as file data
   vector<char> link_data(4096);
   int rc = readlink(path.c_str(), &link_data[0], link_data.size());
   TEST_AND_RETURN_FALSE_ERRNO(rc >= 0);
   link_data.resize(rc);
   out->swap(link_data);
   return true;
 }
 
 bool DeltaDiffGenerator::EncodeDev(
@@ skipping 17 matching lines @@
   return true;
 }
 
 // Encode the file at new_path + "/" + file_name. It may be a binary diff
 // based on old_path + "/" + file_name. out_data_format will be set to
 // the format used. out_data_format may not be NULL.
 bool DeltaDiffGenerator::EncodeFile(
     const string& old_dir,
     const string& new_dir,
     const string& file_name,
+    const bool avoid_diff,
     DeltaArchiveManifest_File_DataFormat* out_data_format,
-    vector<char>* out) {
+    vector<char>* out,
+    bool* no_change) {
   TEST_AND_RETURN_FALSE(out_data_format);
-  // First, see the full length:
+  vector<char> ret;
   vector<char> full_data;
-  TEST_AND_RETURN_FALSE(utils::ReadFile(new_dir + "/" + file_name, &full_data));
-  vector<char> gz_data;
-  if (!full_data.empty()) {
-    TEST_AND_RETURN_FALSE(GzipCompress(full_data, &gz_data));
+  {
+    // First, see the full length:
+    TEST_AND_RETURN_FALSE(utils::ReadFile(new_dir + "/" + file_name,
+                                          &full_data));
+    vector<char> gz_data;
+    if (!full_data.empty()) {
+      TEST_AND_RETURN_FALSE(GzipCompress(full_data, &gz_data));
+    }
+
+    if (gz_data.size() < full_data.size()) {
+      *out_data_format = DeltaArchiveManifest_File_DataFormat_FULL_GZ;
+      ret.swap(gz_data);
+    } else {
+      *out_data_format = DeltaArchiveManifest_File_DataFormat_FULL;
+      ret = full_data;
+    }
   }
-  vector<char> *ret = NULL;
 
-  if (gz_data.size() < full_data.size()) {
-    *out_data_format = DeltaArchiveManifest_File_DataFormat_FULL_GZ;
-    ret = &gz_data;
-  } else {
-    *out_data_format = DeltaArchiveManifest_File_DataFormat_FULL;
-    ret = &full_data;
+  if (avoid_diff) {
+    out->swap(ret);
+    return true;
   }
 
   struct stat old_stbuf;
   if ((stat((old_dir + "/" + file_name).c_str(), &old_stbuf) < 0) ||
       (!S_ISREG(old_stbuf.st_mode))) {
-    // stat() failed or old file is not a regular file. Just send back the full
-    // contents
-    *out = *ret;
+    // stat() failed or old file is not a regular file. Just send back
+    // the full contents
+    out->swap(ret);
     return true;
   }
-  // We have an old file. Do a binary diff. For now use bsdiff.
-  const string kPatchFile = "/tmp/delta.patch";
+  // We have an old file.
+  // First see if the data is _exactly_ the same
+  {
+    vector<char> original_data;
+    TEST_AND_RETURN_FALSE(utils::ReadFile(old_dir + "/" + file_name,
+                                          &original_data));
+    if (original_data == full_data) {
+      // Original data unchanged in new file.
+      *no_change = true;
+      return true;
+    }
+  }
+  
+  // Do a binary diff. For now use bsdiff.
+  const string kPatchFile = "/tmp/delta.patchXXXXXX";
+  vector<char> patch_file_path(kPatchFile.begin(), kPatchFile.end());
+  patch_file_path.push_back('\0');
+  
+  int fd = mkstemp(&patch_file_path[0]);
+  if (fd >= 0)
+    close(fd);
+  TEST_AND_RETURN_FALSE(fd != -1);
 
   vector<string> cmd;
-  cmd.push_back("/usr/bin/bsdiff");
+  cmd.push_back(kBsdiffPath);
   cmd.push_back(old_dir + "/" + file_name);
   cmd.push_back(new_dir + "/" + file_name);
-  cmd.push_back(kPatchFile);
+  cmd.push_back(&patch_file_path[0]);
 
   int rc = 1;
+  vector<char> patch_file;
   TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc));
   TEST_AND_RETURN_FALSE(rc == 0);
-  vector<char> patch_file;
-  TEST_AND_RETURN_FALSE(utils::ReadFile(kPatchFile, &patch_file));
-  unlink(kPatchFile.c_str());
+  TEST_AND_RETURN_FALSE(utils::ReadFile(&patch_file_path[0], &patch_file));
+  unlink(&patch_file_path[0]);
 
-  if (patch_file.size() < ret->size()) {
+  if (patch_file.size() < ret.size()) {
     *out_data_format = DeltaArchiveManifest_File_DataFormat_BSDIFF;
-    ret = &patch_file;
+    ret.swap(patch_file);
   }
-
-  *out = *ret;
+  out->swap(ret);
   return true;
 }
 
 DeltaArchiveManifest* DeltaDiffGenerator::EncodeMetadataToProtoBuffer(
     const char* new_path) {
   Node node;
   if (!UpdateNodeFromPath(new_path, &node))
     return NULL;
   int index = 0;
   PopulateChildIndexes(&node, &index);
   DeltaArchiveManifest *ret = new DeltaArchiveManifest;
   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,
-    const std::string& force_compress_dev_path) {
+    const string& old_path,
+    const string& new_path,
+    const string& out_file,
+    const set<string>& nondiff_paths,
+    const 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);
   ScopedFileWriterCloser closer(&out_writer);
   TEST_AND_RETURN_FALSE(out_writer.Write(DeltaDiffParser::kFileMagic,
                                          strlen(DeltaDiffParser::kFileMagic))
                         == static_cast<ssize_t>(
                             strlen(DeltaDiffParser::kFileMagic)));
   // Write 8 null bytes. This will be filled in w/ the offset of
   // the protobuf.
   TEST_AND_RETURN_FALSE(out_writer.Write("\0\0\0\0\0\0\0\0", 8) == 8);
   // 8 more bytes will be filled w/ the protobuf length.
   TEST_AND_RETURN_FALSE(out_writer.Write("\0\0\0\0\0\0\0\0", 8) == 8);
   int out_file_length = strlen(DeltaDiffParser::kFileMagic) + 16;
 
   TEST_AND_RETURN_FALSE(archive->files_size() > 0);
   DeltaArchiveManifest_File* file = archive->mutable_files(0);
 
+  // nondiff_paths is passed in w/ paths relative to the installed
+  // system (e.g. /etc/fstab), but WriteFileDiffsToDeltaFile requires them
+  // to be the entire path of the new file. We create a new set
+  // here with nondiff_paths expanded.
+  set<string> always_full_target_paths;
+  for (set<string>::const_iterator it = nondiff_paths.begin();
+       it != nondiff_paths.end(); ++it) {
+    always_full_target_paths.insert(new_path + *it);
+  }
+
   TEST_AND_RETURN_FALSE(WriteFileDiffsToDeltaFile(archive,
                                                   file,
                                                   "",
                                                   old_path,
                                                   new_path,
                                                   &out_writer,
                                                   &out_file_length,
+                                                  always_full_target_paths,
                                                   force_compress_dev_path));
 
   // Finally, write the protobuf to the end of the file
   string encoded_archive;
   TEST_AND_RETURN_FALSE(archive->SerializeToString(&encoded_archive));
 
   // Compress the protobuf (which contains filenames)
   vector<char> compressed_encoded_archive;
   TEST_AND_RETURN_FALSE(GzipCompressString(encoded_archive,
                                            &compressed_encoded_archive));
@@ skipping 15 matching lines @@
   TEST_AND_RETURN_FALSE(pwrite(out_writer.fd(),
                                &pb_length,
                                sizeof(pb_length),
                                strlen(DeltaDiffParser::kFileMagic) +
                                sizeof(big_endian_protobuf_offset)) ==
                         sizeof(pb_length));
   return true;
 }
 
 }  // namespace chromeos_update_engine