AU: When generating delta, use scratch off end of filesystem

delta_diff_generator.cc

 // 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/delta_diff_generator.h"
 
 #include <errno.h>
 #include <fcntl.h>
 #include <inttypes.h>
 #include <sys/stat.h>
@@ skipping 36 matching lines @@
 using std::vector;
 
 namespace chromeos_update_engine {
 
 typedef DeltaDiffGenerator::Block Block;
 typedef map<const DeltaArchiveManifest_InstallOperation*,
             const string*> OperationNameMap;
 
 namespace {
 const size_t kBlockSize = 4096;  // bytes
 const size_t kRootFSPartitionSize = 1 * 1024 * 1024 * 1024;  // bytes

[petkov, 2010/12/02 05:04:06]

This is an obsolete dupe now? Remove.

[adlr, 2010/12/02 19:21:41]

Oops missed this. I decided to use this and not make the other

 const uint64_t kVersionNumber = 1;
 const uint64_t kFullUpdateChunkSize = 1024 * 1024;  // bytes
+const uint64_t kRootfsPartitionSize = 1024 * 1024 * 1024;  // bytes

[petkov, 2010/12/02 05:04:06]

Add a TODO to increase this to 2GiB when we stop caring about 1GiB devices any
more.

[adlr, 2010/12/02 19:21:41]

Done.

 
 static const char* kInstallOperationTypes[] = {
   "REPLACE",
   "REPLACE_BZ",
   "MOVE",
   "BSDIFF"
 };
 
 // Stores all Extents for a file into 'out'. Returns true on success.
 bool GatherExtents(const string& path,
@@ skipping 950 matching lines @@
              edge_e = (*graph)[test_node].out_edges.end();
          edge_i != edge_e; ++edge_i) {
       ranges.SubtractExtents(edge_i->second.extents);
     }
     if (ranges.blocks() == 0)
       continue;
 
     if (ranges.blocks() + scratch_blocks_found > blocks_needed) {
       // trim down ranges
       vector<Extent> new_ranges = ranges.GetExtentsForBlockCount(
-        blocks_needed - scratch_blocks_found);
+          blocks_needed - scratch_blocks_found);
       ranges = ExtentRanges();
       ranges.AddExtents(new_ranges);
     }
     scratch_ranges.AddRanges(ranges);
     block_suppliers.push_back(make_pair(test_node, ranges));
     scratch_blocks_found += ranges.blocks();
     if (scratch_ranges.blocks() >= blocks_needed)
       break;
   }
   if (scratch_ranges.blocks() < blocks_needed) {
@@ skipping 208 matching lines @@
         (*graph)[cut.old_dst].out_edges.end());
   (*graph)[cut.new_vertex].valid = false;
   LOG(INFO) << "marked node invalid: " << cut.new_vertex;
   return true;
 }
 
 bool DeltaDiffGenerator::ConvertGraphToDag(Graph* graph,
                                            const string& new_root,
                                            int fd,
                                            off_t* data_file_size,
-                                           vector<Vertex::Index>* final_order) {
+                                           vector<Vertex::Index>* final_order,
+                                           Vertex::Index scratch_vertex) {
   CycleBreaker cycle_breaker;
   LOG(INFO) << "Finding cycles...";
   set<Edge> cut_edges;
   cycle_breaker.BreakCycles(*graph, &cut_edges);
   LOG(INFO) << "done finding cycles";
   CheckGraph(*graph);
 
   // Calculate number of scratch blocks needed
 
   LOG(INFO) << "Cutting cycles...";
@@ skipping 20 matching lines @@
   if (!cuts.empty())
     TEST_AND_RETURN_FALSE(AssignTempBlocks(graph,
                                            new_root,
                                            fd,
                                            data_file_size,
                                            final_order,
                                            &inverse_final_order,
                                            cuts));
   LOG(INFO) << "Making sure all temp blocks have been allocated";
 
+  // Remove the scratch node, if any
+  if (scratch_vertex != Vertex::kInvalidIndex) {
+    final_order->erase(final_order->begin() +
+                       inverse_final_order[scratch_vertex]);
+    (*graph)[scratch_vertex].valid = false;
+    GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
+  }
+
   graph_utils::DumpGraph(*graph);
   CHECK(NoTempBlocksRemain(*graph));
   LOG(INFO) << "done making sure all temp blocks are allocated";
   return true;
 }
 
+void DeltaDiffGenerator::CreateScratchNode(uint64_t start_block,
+                                           uint64_t num_blocks,
+                                           Vertex* vertex) {
+  vertex->file_name = "<scratch>";
+  vertex->op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  vertex->op.set_data_offset(0);
+  vertex->op.set_data_length(0);
+  Extent* extent = vertex->op.add_dst_extents();
+  extent->set_start_block(start_block);
+  extent->set_num_blocks(num_blocks);
+}
+
 bool DeltaDiffGenerator::GenerateDeltaUpdateFile(
     const string& old_root,
     const string& old_image,
     const string& new_root,
     const string& new_image,
     const string& old_kernel_part,
     const string& new_kernel_part,
     const string& output_path,
     const string& private_key_path) {
   int old_image_block_count = 0, old_image_block_size = 0;
@@ skipping 24 matching lines @@
 
   const string kTempFileTemplate("/tmp/CrAU_temp_data.XXXXXX");
   string temp_file_path;
   off_t data_file_size = 0;
 
   LOG(INFO) << "Reading files...";
 
   vector<DeltaArchiveManifest_InstallOperation> kernel_ops;
 
   vector<Vertex::Index> final_order;
+  Vertex::Index scratch_vertex = Vertex::kInvalidIndex;
   {
     int fd;
     TEST_AND_RETURN_FALSE(
         utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &fd));
     TEST_AND_RETURN_FALSE(fd >= 0);
     ScopedFdCloser fd_closer(&fd);
     if (!old_image.empty()) {
       // Delta update
 
       TEST_AND_RETURN_FALSE(DeltaReadFiles(&graph,
                                            &blocks,
                                            old_root,
                                            new_root,
                                            fd,
                                            &data_file_size));
       LOG(INFO) << "done reading normal files";
       CheckGraph(graph);
 
       graph.resize(graph.size() + 1);
       TEST_AND_RETURN_FALSE(ReadUnwrittenBlocks(blocks,
                                                 fd,
                                                 &data_file_size,
                                                 new_image,
                                                 &graph.back()));
 
+      // Final scratch block (if there's space)
+      if (blocks.size() < (kRootfsPartitionSize / kBlockSize)) {
+        scratch_vertex = graph.size();
+        graph.resize(graph.size() + 1);
+        CreateScratchNode(blocks.size(),
+                          (kRootfsPartitionSize / kBlockSize) - blocks.size(),
+                          &graph.back());
+      }
+
       // Read kernel partition
       TEST_AND_RETURN_FALSE(DeltaCompressKernelPartition(old_kernel_part,
                                                          new_kernel_part,
                                                          &kernel_ops,
                                                          fd,
                                                          &data_file_size));
 
       LOG(INFO) << "done reading kernel";
       CheckGraph(graph);
 
       LOG(INFO) << "Creating edges...";
       CreateEdges(&graph, blocks);
       LOG(INFO) << "Done creating edges";
       CheckGraph(graph);
 
       TEST_AND_RETURN_FALSE(ConvertGraphToDag(&graph,
                                               new_root,
                                               fd,
                                               &data_file_size,
-                                              &final_order));
+                                              &final_order,
+                                              scratch_vertex));
     } else {
       // Full update
       off_t new_image_size =
           static_cast<off_t>(new_image_block_count) * new_image_block_size;
       TEST_AND_RETURN_FALSE(FullUpdateGenerator::Run(&graph,
                                                      new_kernel_part,
                                                      new_image,
                                                      new_image_size,
                                                      fd,
                                                      &data_file_size,
@@ skipping 143 matching lines @@
 
   LOG(INFO) << "All done. Successfully created delta file.";
   return true;
 }
 
 const char* const kBsdiffPath = "bsdiff";
 const char* const kBspatchPath = "bspatch";
 const char* const kDeltaMagic = "CrAU";
 
 };  // namespace chromeos_update_engine