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

This idea was originally coded by Darin Petkov, but was lost during a
separate bug fix a while ago. This CL restores the functionality.

The partition limit is set to 1GiB right now.

BUG=7444
TEST=tested generating/applying on host and checking results; unittest; tested specific case 110.9->128.4 that release engineers saw

Change-Id: I28a9a8d7025b83ec20b91e97dce5b783fc060b7c

Review URL: http://codereview.chromium.org/5548002
diff --git a/delta_diff_generator.cc b/delta_diff_generator.cc
index d084138..21a4c03 100644
--- a/delta_diff_generator.cc
+++ b/delta_diff_generator.cc
@@ -54,6 +54,9 @@
 
 namespace {
 const size_t kBlockSize = 4096;  // bytes
+
+// TODO(adlr): switch from 1GiB to 2GiB when we no longer care about old
+// clients:
 const size_t kRootFSPartitionSize = 1 * 1024 * 1024 * 1024;  // bytes
 const uint64_t kVersionNumber = 1;
 const uint64_t kFullUpdateChunkSize = 1024 * 1024;  // bytes
@@ -1027,7 +1030,7 @@
     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);
     }
@@ -1256,7 +1259,8 @@
                                            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;
@@ -1297,12 +1301,32 @@
                                            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,
@@ -1347,6 +1371,7 @@
   vector<DeltaArchiveManifest_InstallOperation> kernel_ops;
 
   vector<Vertex::Index> final_order;
+  Vertex::Index scratch_vertex = Vertex::kInvalidIndex;
   {
     int fd;
     TEST_AND_RETURN_FALSE(
@@ -1372,6 +1397,15 @@
                                                 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,
@@ -1391,7 +1425,8 @@
                                               new_root,
                                               fd,
                                               &data_file_size,
-                                              &final_order));
+                                              &final_order,
+                                              scratch_vertex));
     } else {
       // Full update
       off_t new_image_size =
diff --git a/delta_diff_generator.h b/delta_diff_generator.h
index 53d3f87..50a3a89 100644
--- a/delta_diff_generator.h
+++ b/delta_diff_generator.h
@@ -79,12 +79,15 @@
   // The final order of the nodes is given in |final_order|
   // Some files may need to be reread from disk, thus |fd| and
   // |data_file_size| are be passed.
+  // If |scratch_vertex| is not kInvalidIndex, removes it from
+  // |final_order| before returning.
   // Returns true on success.
   static bool ConvertGraphToDag(Graph* graph,
                                 const std::string& new_root,
                                 int fd,
                                 off_t* data_file_size,
-                                std::vector<Vertex::Index>* final_order);
+                                std::vector<Vertex::Index>* final_order,
+                                Vertex::Index scratch_vertex);
 
   // Reads old_filename (if it exists) and a new_filename and determines
   // the smallest way to encode this file for the diff. It stores
@@ -100,6 +103,14 @@
                              DeltaArchiveManifest_InstallOperation* out_op,
                              bool gather_extents);
 
+  // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used
+  // to provide scratch space. The node writes |num_blocks| blocks starting at
+  // |start_block|The node should be marked invalid before writing all nodes to
+  // the output file.
+  static void CreateScratchNode(uint64_t start_block,
+                                uint64_t num_blocks,
+                                Vertex* vertex);
+
   // Modifies blocks read by 'op' so that any blocks referred to by
   // 'remove_extents' are replaced with blocks from 'replace_extents'.
   // 'remove_extents' and 'replace_extents' must be the same number of blocks.
diff --git a/delta_diff_generator_unittest.cc b/delta_diff_generator_unittest.cc
index 4a11c52..2a70399 100644
--- a/delta_diff_generator_unittest.cc
+++ b/delta_diff_generator_unittest.cc
@@ -525,7 +525,8 @@
                                                     temp_dir,
                                                     fd,
                                                     &data_file_size,
-                                                    &final_order));
+                                                    &final_order,
+                                                    Vertex::kInvalidIndex));
 
 
   Graph expected_graph(12);
@@ -728,4 +729,16 @@
   EXPECT_EQ(OP_REPLACE_BZ, graph[5].op.type());
 }
 
+TEST_F(DeltaDiffGeneratorTest, CreateScratchNodeTest) {
+  Vertex vertex;
+  DeltaDiffGenerator::CreateScratchNode(12, 34, &vertex);
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
+            vertex.op.type());
+  EXPECT_EQ(0, vertex.op.data_offset());
+  EXPECT_EQ(0, vertex.op.data_length());
+  EXPECT_EQ(1, vertex.op.dst_extents_size());
+  EXPECT_EQ(12, vertex.op.dst_extents(0).start_block());
+  EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
+}
+
 }  // namespace chromeos_update_engine