Move payload generator files to payload_generator/ directory.
This creates a new subdirectory payload_generator/ with all the
payload generator specific files.
The SConstruct file is updated to continue building all the files
together, including those in the subdirectories, since some parts
of the update_engine are using parts of the payload generation code.
To reduce this code coupling, a new payload_constants.h file is
introduced, with few constants used on the payload definition by both
the payload generation and the payload performer.
Finally, includes are updated and in some cases removed when they
weren't used. Order of includes is also fixed to comply with the
style guide.
BUG=chromium:374377
TEST=Build and unittests still pass. delta_generator still present on base directory.
Change-Id: I454bbc7a66c70ebb19fd596c352c7be40a081f3d
Reviewed-on: https://chromium-review.googlesource.com/200325
Reviewed-by: Alex Deymo <[email protected]>
Commit-Queue: Alex Deymo <[email protected]>
Tested-by: Alex Deymo <[email protected]>
diff --git a/payload_generator/cycle_breaker.cc b/payload_generator/cycle_breaker.cc
new file mode 100644
index 0000000..10ef6fb
--- /dev/null
+++ b/payload_generator/cycle_breaker.cc
@@ -0,0 +1,199 @@
+// Copyright (c) 2012 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/payload_generator/cycle_breaker.h"
+
+#include <inttypes.h>
+
+#include <set>
+#include <utility>
+
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/tarjan.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::set;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+// This is the outer function from the original paper.
+void CycleBreaker::BreakCycles(const Graph& graph, set<Edge>* out_cut_edges) {
+ cut_edges_.clear();
+
+ // Make a copy, which we will modify by removing edges. Thus, in each
+ // iteration subgraph_ is the current subgraph or the original with
+ // vertices we desire. This variable was "A_K" in the original paper.
+ subgraph_ = graph;
+
+ // The paper calls for the "adjacency structure (i.e., graph) of
+ // strong (-ly connected) component K with least vertex in subgraph
+ // induced by {s, s + 1, ..., n}".
+ // We arbitrarily order each vertex by its index in the graph. Thus,
+ // each iteration, we are looking at the subgraph {s, s + 1, ..., n}
+ // and looking for the strongly connected component with vertex s.
+
+ TarjanAlgorithm tarjan;
+ skipped_ops_ = 0;
+
+ for (Graph::size_type i = 0; i < subgraph_.size(); i++) {
+ DeltaArchiveManifest_InstallOperation_Type op_type = graph[i].op.type();
+ if (op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+ op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+ skipped_ops_++;
+ continue;
+ }
+
+ if (i > 0) {
+ // Erase node (i - 1) from subgraph_. First, erase what it points to
+ subgraph_[i - 1].out_edges.clear();
+ // Now, erase any pointers to node (i - 1)
+ for (Graph::size_type j = i; j < subgraph_.size(); j++) {
+ subgraph_[j].out_edges.erase(i - 1);
+ }
+ }
+
+ // Calculate SCC (strongly connected component) with vertex i.
+ vector<Vertex::Index> component_indexes;
+ tarjan.Execute(i, &subgraph_, &component_indexes);
+
+ // Set subgraph edges for the components in the SCC.
+ for (vector<Vertex::Index>::iterator it = component_indexes.begin();
+ it != component_indexes.end(); ++it) {
+ subgraph_[*it].subgraph_edges.clear();
+ for (vector<Vertex::Index>::iterator jt = component_indexes.begin();
+ jt != component_indexes.end(); ++jt) {
+ // If there's a link from *it -> *jt in the graph,
+ // add a subgraph_ edge
+ if (utils::MapContainsKey(subgraph_[*it].out_edges, *jt))
+ subgraph_[*it].subgraph_edges.insert(*jt);
+ }
+ }
+
+ current_vertex_ = i;
+ blocked_.clear();
+ blocked_.resize(subgraph_.size());
+ blocked_graph_.clear();
+ blocked_graph_.resize(subgraph_.size());
+ Circuit(current_vertex_, 0);
+ }
+
+ out_cut_edges->swap(cut_edges_);
+ LOG(INFO) << "Cycle breaker skipped " << skipped_ops_ << " ops.";
+ DCHECK(stack_.empty());
+}
+
+static const size_t kMaxEdgesToConsider = 2;
+
+void CycleBreaker::HandleCircuit() {
+ stack_.push_back(current_vertex_);
+ CHECK_GE(stack_.size(),
+ static_cast<std::vector<Vertex::Index>::size_type>(2));
+ Edge min_edge = make_pair(stack_[0], stack_[1]);
+ uint64_t min_edge_weight = kuint64max;
+ size_t edges_considered = 0;
+ for (vector<Vertex::Index>::const_iterator it = stack_.begin();
+ it != (stack_.end() - 1); ++it) {
+ Edge edge = make_pair(*it, *(it + 1));
+ if (cut_edges_.find(edge) != cut_edges_.end()) {
+ stack_.pop_back();
+ return;
+ }
+ uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge);
+ if (edge_weight < min_edge_weight) {
+ min_edge_weight = edge_weight;
+ min_edge = edge;
+ }
+ edges_considered++;
+ if (edges_considered == kMaxEdgesToConsider)
+ break;
+ }
+ cut_edges_.insert(min_edge);
+ stack_.pop_back();
+}
+
+void CycleBreaker::Unblock(Vertex::Index u) {
+ blocked_[u] = false;
+
+ for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin();
+ it != blocked_graph_[u].out_edges.end(); ) {
+ Vertex::Index w = it->first;
+ blocked_graph_[u].out_edges.erase(it++);
+ if (blocked_[w])
+ Unblock(w);
+ }
+}
+
+bool CycleBreaker::StackContainsCutEdge() const {
+ for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
+ e = stack_.end(); it != e; ++it) {
+ Edge edge = make_pair(*(it - 1), *it);
+ if (utils::SetContainsKey(cut_edges_, edge)) {
+ return true;
+ }
+ }
+ return false;
+}
+
+bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) {
+ // "vertex" was "v" in the original paper.
+ bool found = false; // Was "f" in the original paper.
+ stack_.push_back(vertex);
+ blocked_[vertex] = true;
+ {
+ static int counter = 0;
+ counter++;
+ if (counter == 10000) {
+ counter = 0;
+ std::string stack_str;
+ for (vector<Vertex::Index>::const_iterator it = stack_.begin();
+ it != stack_.end(); ++it) {
+ stack_str += base::StringPrintf("%lu -> ",
+ static_cast<long unsigned int>(*it));
+ }
+ LOG(INFO) << "stack: " << stack_str;
+ }
+ }
+
+ for (Vertex::SubgraphEdgeMap::iterator w =
+ subgraph_[vertex].subgraph_edges.begin();
+ w != subgraph_[vertex].subgraph_edges.end(); ++w) {
+ if (*w == current_vertex_) {
+ // The original paper called for printing stack_ followed by
+ // current_vertex_ here, which is a cycle. Instead, we call
+ // HandleCircuit() to break it.
+ HandleCircuit();
+ found = true;
+ } else if (!blocked_[*w]) {
+ if (Circuit(*w, depth + 1)) {
+ found = true;
+ if ((depth > kMaxEdgesToConsider) || StackContainsCutEdge())
+ break;
+ }
+ }
+ }
+
+ if (found) {
+ Unblock(vertex);
+ } else {
+ for (Vertex::SubgraphEdgeMap::iterator w =
+ subgraph_[vertex].subgraph_edges.begin();
+ w != subgraph_[vertex].subgraph_edges.end(); ++w) {
+ if (blocked_graph_[*w].out_edges.find(vertex) ==
+ blocked_graph_[*w].out_edges.end()) {
+ blocked_graph_[*w].out_edges.insert(make_pair(vertex,
+ EdgeProperties()));
+ }
+ }
+ }
+ CHECK_EQ(vertex, stack_.back());
+ stack_.pop_back();
+ return found;
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/cycle_breaker.h b/payload_generator/cycle_breaker.h
new file mode 100644
index 0000000..d0ae3fd
--- /dev/null
+++ b/payload_generator/cycle_breaker.h
@@ -0,0 +1,59 @@
+// 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_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
+
+// This is a modified implementation of Donald B. Johnson's algorithm for
+// finding all elementary cycles (a.k.a. circuits) in a directed graph.
+// See the paper "Finding All the Elementary Circuits of a Directed Graph"
+// at http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf
+// for reference.
+
+// Note: this version of the algorithm not only finds cycles, but breaks them.
+// It uses a simple greedy algorithm for cutting: when a cycle is discovered,
+// the edge with the least weight is cut. Longer term we may wish to do
+// something more intelligent, since the goal is (ideally) to minimize the
+// sum of the weights of all cut cycles. In practice, it's intractable
+// to consider all cycles before cutting any; there are simply too many.
+// In a sample graph representative of a typical workload, I found over
+// 5 * 10^15 cycles.
+
+#include <set>
+#include <vector>
+
+#include "update_engine/payload_generator/graph_types.h"
+
+namespace chromeos_update_engine {
+
+class CycleBreaker {
+ public:
+ CycleBreaker() : skipped_ops_(0) {}
+ // out_cut_edges is replaced with the cut edges.
+ void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges);
+
+ size_t skipped_ops() const { return skipped_ops_; }
+
+ private:
+ void HandleCircuit();
+ void Unblock(Vertex::Index u);
+ bool Circuit(Vertex::Index vertex, Vertex::Index depth);
+ bool StackContainsCutEdge() const;
+
+ std::vector<bool> blocked_; // "blocked" in the paper
+ Vertex::Index current_vertex_; // "s" in the paper
+ std::vector<Vertex::Index> stack_; // the stack variable in the paper
+ Graph subgraph_; // "A_K" in the paper
+ Graph blocked_graph_; // "B" in the paper
+
+ std::set<Edge> cut_edges_;
+
+ // Number of operations skipped b/c we know they don't have any
+ // incoming edges.
+ size_t skipped_ops_;
+};
+
+} // namespace chromeos_update_engine
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
diff --git a/payload_generator/cycle_breaker_unittest.cc b/payload_generator/cycle_breaker_unittest.cc
new file mode 100644
index 0000000..b2cd5d4
--- /dev/null
+++ b/payload_generator/cycle_breaker_unittest.cc
@@ -0,0 +1,266 @@
+// 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/payload_generator/cycle_breaker.h"
+
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/logging.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::pair;
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+void SetOpForNodes(Graph* graph) {
+ for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
+ it->op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ }
+}
+} // namespace {}
+
+class CycleBreakerTest : public ::testing::Test {};
+
+TEST(CycleBreakerTest, SimpleTest) {
+ int counter = 0;
+ const Vertex::Index n_a = counter++;
+ const Vertex::Index n_b = counter++;
+ const Vertex::Index n_c = counter++;
+ const Vertex::Index n_d = counter++;
+ const Vertex::Index n_e = counter++;
+ const Vertex::Index n_f = counter++;
+ const Vertex::Index n_g = counter++;
+ const Vertex::Index n_h = counter++;
+ const Graph::size_type kNodeCount = counter++;
+
+ Graph graph(kNodeCount);
+ SetOpForNodes(&graph);
+
+ graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties()));
+ graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties()));
+ graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
+ graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties()));
+ graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties()));
+ graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties()));
+ graph[n_f].out_edges.insert(make_pair(n_g, EdgeProperties()));
+ graph[n_g].out_edges.insert(make_pair(n_h, EdgeProperties()));
+ graph[n_h].out_edges.insert(make_pair(n_g, EdgeProperties()));
+
+ CycleBreaker breaker;
+
+ set<Edge> broken_edges;
+ breaker.BreakCycles(graph, &broken_edges);
+
+ // The following cycles must be cut:
+ // A->E->B
+ // C->D->E
+ // G->H
+
+ EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_e)) ||
+ utils::SetContainsKey(broken_edges, make_pair(n_e, n_b)) ||
+ utils::SetContainsKey(broken_edges, make_pair(n_b, n_a)));
+ EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_c, n_d)) ||
+ utils::SetContainsKey(broken_edges, make_pair(n_d, n_e)) ||
+ utils::SetContainsKey(broken_edges, make_pair(n_e, n_c)));
+ EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_g, n_h)) ||
+ utils::SetContainsKey(broken_edges, make_pair(n_h, n_g)));
+ EXPECT_EQ(3, broken_edges.size());
+}
+
+namespace {
+pair<Vertex::Index, EdgeProperties> EdgeWithWeight(Vertex::Index dest,
+uint64_t weight) {
+ EdgeProperties props;
+ props.extents.resize(1);
+ props.extents[0].set_num_blocks(weight);
+ return make_pair(dest, props);
+}
+} // namespace {}
+
+
+// This creates a bunch of cycles like this:
+//
+// root <------.
+// (t)-> / | \ |
+// V V V |
+// N N N |
+// \ | / |
+// VVV |
+// N |
+// / | \ |
+// V V V |
+// N N N |
+// ... |
+// (s)-> \ | / |
+// VVV |
+// N |
+// \_________/
+//
+// such that the original cutting algo would cut edges (s). We changed
+// the algorithm to cut cycles (t) instead, since they are closer to the
+// root, and that can massively speed up cycle cutting.
+TEST(CycleBreakerTest, AggressiveCutTest) {
+ int counter = 0;
+
+ const int kNodesPerGroup = 4;
+ const int kGroups = 33;
+
+ Graph graph(kGroups * kNodesPerGroup + 1); // + 1 for the root node
+ SetOpForNodes(&graph);
+
+ const Vertex::Index n_root = counter++;
+
+ Vertex::Index last_hub = n_root;
+ for (int i = 0; i < kGroups; i++) {
+ uint64_t weight = 5;
+ if (i == 0)
+ weight = 2;
+ else if (i == (kGroups - 1))
+ weight = 1;
+
+ const Vertex::Index next_hub = counter++;
+
+ for (int j = 0; j < (kNodesPerGroup - 1); j++) {
+ const Vertex::Index node = counter++;
+ graph[last_hub].out_edges.insert(EdgeWithWeight(node, weight));
+ graph[node].out_edges.insert(EdgeWithWeight(next_hub, weight));
+ }
+ last_hub = next_hub;
+ }
+
+ graph[last_hub].out_edges.insert(EdgeWithWeight(n_root, 5));
+
+ EXPECT_EQ(counter, graph.size());
+
+ CycleBreaker breaker;
+
+ set<Edge> broken_edges;
+ LOG(INFO) << "If this hangs for more than 1 second, the test has failed.";
+ breaker.BreakCycles(graph, &broken_edges);
+
+ set<Edge> expected_cuts;
+
+ for (Vertex::EdgeMap::const_iterator it = graph[n_root].out_edges.begin(),
+ e = graph[n_root].out_edges.end(); it != e; ++it) {
+ expected_cuts.insert(make_pair(n_root, it->first));
+ }
+
+ EXPECT_TRUE(broken_edges == expected_cuts);
+}
+
+TEST(CycleBreakerTest, WeightTest) {
+ int counter = 0;
+ const Vertex::Index n_a = counter++;
+ const Vertex::Index n_b = counter++;
+ const Vertex::Index n_c = counter++;
+ const Vertex::Index n_d = counter++;
+ const Vertex::Index n_e = counter++;
+ const Vertex::Index n_f = counter++;
+ const Vertex::Index n_g = counter++;
+ const Vertex::Index n_h = counter++;
+ const Vertex::Index n_i = counter++;
+ const Vertex::Index n_j = counter++;
+ const Graph::size_type kNodeCount = counter++;
+
+ Graph graph(kNodeCount);
+ SetOpForNodes(&graph);
+
+ graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 4));
+ graph[n_a].out_edges.insert(EdgeWithWeight(n_f, 3));
+ graph[n_a].out_edges.insert(EdgeWithWeight(n_h, 2));
+ graph[n_b].out_edges.insert(EdgeWithWeight(n_a, 3));
+ graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 4));
+ graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 5));
+ graph[n_c].out_edges.insert(EdgeWithWeight(n_d, 3));
+ graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 6));
+ graph[n_d].out_edges.insert(EdgeWithWeight(n_e, 3));
+ graph[n_e].out_edges.insert(EdgeWithWeight(n_d, 4));
+ graph[n_e].out_edges.insert(EdgeWithWeight(n_g, 5));
+ graph[n_f].out_edges.insert(EdgeWithWeight(n_g, 2));
+ graph[n_g].out_edges.insert(EdgeWithWeight(n_f, 3));
+ graph[n_g].out_edges.insert(EdgeWithWeight(n_d, 5));
+ graph[n_h].out_edges.insert(EdgeWithWeight(n_i, 8));
+ graph[n_i].out_edges.insert(EdgeWithWeight(n_e, 4));
+ graph[n_i].out_edges.insert(EdgeWithWeight(n_h, 9));
+ graph[n_i].out_edges.insert(EdgeWithWeight(n_j, 6));
+
+ CycleBreaker breaker;
+
+ set<Edge> broken_edges;
+ breaker.BreakCycles(graph, &broken_edges);
+
+ // These are required to be broken:
+ EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_a)));
+ EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_c)));
+ EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_d, n_e)));
+ EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_f, n_g)));
+ EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_h, n_i)));
+}
+
+TEST(CycleBreakerTest, UnblockGraphTest) {
+ int counter = 0;
+ const Vertex::Index n_a = counter++;
+ const Vertex::Index n_b = counter++;
+ const Vertex::Index n_c = counter++;
+ const Vertex::Index n_d = counter++;
+ const Graph::size_type kNodeCount = counter++;
+
+ Graph graph(kNodeCount);
+ SetOpForNodes(&graph);
+
+ graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
+ graph[n_a].out_edges.insert(EdgeWithWeight(n_c, 1));
+ graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 2));
+ graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 2));
+ graph[n_b].out_edges.insert(EdgeWithWeight(n_d, 2));
+ graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 2));
+
+ CycleBreaker breaker;
+
+ set<Edge> broken_edges;
+ breaker.BreakCycles(graph, &broken_edges);
+
+ // These are required to be broken:
+ EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_b)));
+ EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_c)));
+}
+
+TEST(CycleBreakerTest, SkipOpsTest) {
+ int counter = 0;
+ const Vertex::Index n_a = counter++;
+ const Vertex::Index n_b = counter++;
+ const Vertex::Index n_c = counter++;
+ const Graph::size_type kNodeCount = counter++;
+
+ Graph graph(kNodeCount);
+ SetOpForNodes(&graph);
+ graph[n_a].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ graph[n_c].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+
+ graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
+ graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 1));
+
+ CycleBreaker breaker;
+
+ set<Edge> broken_edges;
+ breaker.BreakCycles(graph, &broken_edges);
+
+ EXPECT_EQ(2, breaker.skipped_ops());
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
new file mode 100644
index 0000000..8fbbd0d
--- /dev/null
+++ b/payload_generator/delta_diff_generator.cc
@@ -0,0 +1,1928 @@
+// Copyright (c) 2012 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/payload_generator/delta_diff_generator.h"
+
+#include <errno.h>
+#include <fcntl.h>
+#include <inttypes.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <algorithm>
+#include <map>
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/file_util.h>
+#include <base/files/file_path.h>
+#include <base/logging.h>
+#include <base/memory/scoped_ptr.h>
+#include <base/strings/string_number_conversions.h>
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+#include <bzlib.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/delta_performer.h"
+#include "update_engine/extent_ranges.h"
+#include "update_engine/file_writer.h"
+#include "update_engine/omaha_hash_calculator.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/cycle_breaker.h"
+#include "update_engine/payload_generator/extent_mapper.h"
+#include "update_engine/payload_generator/filesystem_iterator.h"
+#include "update_engine/payload_generator/full_update_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/metadata.h"
+#include "update_engine/payload_generator/topological_sort.h"
+#include "update_engine/payload_signer.h"
+#include "update_engine/subprocess.h"
+#include "update_engine/update_metadata.pb.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::map;
+using std::max;
+using std::min;
+using std::pair;
+using std::set;
+using std::string;
+using std::vector;
+
+namespace {
+
+const uint64_t kVersionNumber = 1;
+const uint64_t kFullUpdateChunkSize = 1024 * 1024; // bytes
+
+const size_t kBlockSize = 4096; // bytes
+const string kNonexistentPath = "";
+
+static const char* kInstallOperationTypes[] = {
+ "REPLACE",
+ "REPLACE_BZ",
+ "MOVE",
+ "BSDIFF"
+};
+
+} // namespace
+
+namespace chromeos_update_engine {
+
+typedef DeltaDiffGenerator::Block Block;
+typedef map<const DeltaArchiveManifest_InstallOperation*,
+ string> OperationNameMap;
+
+// bytes
+const size_t kRootFSPartitionSize = static_cast<size_t>(2) * 1024 * 1024 * 1024;
+
+// Needed for testing purposes, in case we can't use actual filesystem objects.
+// TODO(garnold)(chromium:331965) Replace this hack with a properly injected
+// parameter in form of a mockable abstract class.
+bool (*get_extents_with_chunk_func)(const std::string&, off_t, off_t,
+ std::vector<Extent>*) =
+ extent_mapper::ExtentsForFileChunkFibmap;
+
+namespace {
+
+// Stores all the extents of |path| into |extents|. Returns true on success.
+bool GatherExtents(const string& path,
+ off_t chunk_offset,
+ off_t chunk_size,
+ vector<Extent>* extents) {
+ extents->clear();
+ TEST_AND_RETURN_FALSE(
+ get_extents_with_chunk_func(
+ path, chunk_offset, chunk_size, extents));
+ return true;
+}
+
+// For a given regular file which must exist at new_root + path, and
+// may exist at old_root + path, creates a new InstallOperation and
+// adds it to the graph. Also, populates the |blocks| array as
+// necessary, if |blocks| is non-NULL. Also, writes the data
+// necessary to send the file down to the client into data_fd, which
+// has length *data_file_size. *data_file_size is updated
+// appropriately. If |existing_vertex| is no kInvalidIndex, use that
+// rather than allocating a new vertex. Returns true on success.
+bool DeltaReadFile(Graph* graph,
+ Vertex::Index existing_vertex,
+ vector<Block>* blocks,
+ const string& old_root,
+ const string& new_root,
+ const string& path, // within new_root
+ off_t chunk_offset,
+ off_t chunk_size,
+ int data_fd,
+ off_t* data_file_size) {
+ vector<char> data;
+ DeltaArchiveManifest_InstallOperation operation;
+
+ string old_path = (old_root == kNonexistentPath) ? kNonexistentPath :
+ old_root + path;
+
+ // If bsdiff breaks again, blacklist the problem file by using:
+ // bsdiff_allowed = (path != "/foo/bar")
+ //
+ // TODO(dgarrett): chromium-os:15274 connect this test to the command line.
+ bool bsdiff_allowed = true;
+
+ if (!bsdiff_allowed)
+ LOG(INFO) << "bsdiff blacklisting: " << path;
+
+ TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ReadFileToDiff(old_path,
+ new_root + path,
+ chunk_offset,
+ chunk_size,
+ bsdiff_allowed,
+ &data,
+ &operation,
+ true));
+
+ // Check if the operation writes nothing.
+ if (operation.dst_extents_size() == 0) {
+ if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+ LOG(INFO) << "Empty MOVE operation (" << new_root + path << "), skipping";
+ return true;
+ } else {
+ LOG(ERROR) << "Empty non-MOVE operation";
+ return false;
+ }
+ }
+
+ // Write the data
+ if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+ operation.set_data_offset(*data_file_size);
+ operation.set_data_length(data.size());
+ }
+
+ TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, &data[0], data.size()));
+ *data_file_size += data.size();
+
+ // Now, insert into graph and blocks vector
+ Vertex::Index vertex = existing_vertex;
+ if (vertex == Vertex::kInvalidIndex) {
+ graph->resize(graph->size() + 1);
+ vertex = graph->size() - 1;
+ }
+ (*graph)[vertex].op = operation;
+ CHECK((*graph)[vertex].op.has_type());
+ (*graph)[vertex].file_name = path;
+ (*graph)[vertex].chunk_offset = chunk_offset;
+ (*graph)[vertex].chunk_size = chunk_size;
+
+ if (blocks)
+ TEST_AND_RETURN_FALSE(DeltaDiffGenerator::AddInstallOpToBlocksVector(
+ (*graph)[vertex].op,
+ *graph,
+ vertex,
+ blocks));
+ return true;
+}
+
+// For each regular file within new_root, creates a node in the graph,
+// determines the best way to compress it (REPLACE, REPLACE_BZ, COPY, BSDIFF),
+// and writes any necessary data to the end of data_fd.
+bool DeltaReadFiles(Graph* graph,
+ vector<Block>* blocks,
+ const string& old_root,
+ const string& new_root,
+ off_t chunk_size,
+ int data_fd,
+ off_t* data_file_size) {
+ set<ino_t> visited_inodes;
+ set<ino_t> visited_src_inodes;
+ for (FilesystemIterator fs_iter(new_root,
+ utils::SetWithValue<string>("/lost+found"));
+ !fs_iter.IsEnd(); fs_iter.Increment()) {
+ // We never diff symlinks (here, we check that dst file is not a symlink).
+ if (!S_ISREG(fs_iter.GetStat().st_mode))
+ continue;
+
+ // Make sure we visit each inode only once.
+ if (utils::SetContainsKey(visited_inodes, fs_iter.GetStat().st_ino))
+ continue;
+ visited_inodes.insert(fs_iter.GetStat().st_ino);
+ off_t dst_size = fs_iter.GetStat().st_size;
+ if (dst_size == 0)
+ continue;
+
+ LOG(INFO) << "Encoding file " << fs_iter.GetPartialPath();
+
+ // We can't visit each dst image inode more than once, as that would
+ // duplicate work. Here, we avoid visiting each source image inode
+ // more than once. Technically, we could have multiple operations
+ // that read the same blocks from the source image for diffing, but
+ // we choose not to to avoid complexity. Eventually we will move away
+ // from using a graph/cycle detection/etc to generate diffs, and at that
+ // time, it will be easy (non-complex) to have many operations read
+ // from the same source blocks. At that time, this code can die. -adlr
+ bool should_diff_from_source = false;
+ string src_path = old_root + fs_iter.GetPartialPath();
+ struct stat src_stbuf;
+ // We never diff symlinks (here, we check that src file is not a symlink).
+ if (0 == lstat(src_path.c_str(), &src_stbuf) &&
+ S_ISREG(src_stbuf.st_mode)) {
+ should_diff_from_source = !utils::SetContainsKey(visited_src_inodes,
+ src_stbuf.st_ino);
+ visited_src_inodes.insert(src_stbuf.st_ino);
+ }
+
+ off_t size = chunk_size == -1 ? dst_size : chunk_size;
+ off_t step = size;
+ for (off_t offset = 0; offset < dst_size; offset += step) {
+ if (offset + size >= dst_size) {
+ size = -1; // Read through the end of the file.
+ }
+ TEST_AND_RETURN_FALSE(DeltaReadFile(graph,
+ Vertex::kInvalidIndex,
+ blocks,
+ (should_diff_from_source ?
+ old_root :
+ kNonexistentPath),
+ new_root,
+ fs_iter.GetPartialPath(),
+ offset,
+ size,
+ data_fd,
+ data_file_size));
+ }
+ }
+ return true;
+}
+
+// This class allocates non-existent temp blocks, starting from
+// kTempBlockStart. Other code is responsible for converting these
+// temp blocks into real blocks, as the client can't read or write to
+// these blocks.
+class DummyExtentAllocator {
+ public:
+ explicit DummyExtentAllocator()
+ : next_block_(kTempBlockStart) {}
+ vector<Extent> Allocate(const uint64_t block_count) {
+ vector<Extent> ret(1);
+ ret[0].set_start_block(next_block_);
+ ret[0].set_num_blocks(block_count);
+ next_block_ += block_count;
+ return ret;
+ }
+ private:
+ uint64_t next_block_;
+};
+
+// Reads blocks from image_path that are not yet marked as being written
+// in the blocks array. These blocks that remain are non-file-data blocks.
+// In the future we might consider intelligent diffing between this data
+// and data in the previous image, but for now we just bzip2 compress it
+// and include it in the update.
+// Creates a new node in the graph to write these blocks and writes the
+// appropriate blob to blobs_fd. Reads and updates blobs_length;
+bool ReadUnwrittenBlocks(const vector<Block>& blocks,
+ int blobs_fd,
+ off_t* blobs_length,
+ const string& image_path,
+ Vertex* vertex) {
+ vertex->file_name = "<rootfs-non-file-data>";
+
+ DeltaArchiveManifest_InstallOperation* out_op = &vertex->op;
+ int image_fd = open(image_path.c_str(), O_RDONLY, 000);
+ TEST_AND_RETURN_FALSE_ERRNO(image_fd >= 0);
+ ScopedFdCloser image_fd_closer(&image_fd);
+
+ string temp_file_path;
+ TEST_AND_RETURN_FALSE(utils::MakeTempFile("CrAU_temp_data.XXXXXX",
+ &temp_file_path,
+ NULL));
+
+ FILE* file = fopen(temp_file_path.c_str(), "w");
+ TEST_AND_RETURN_FALSE(file);
+ int err = BZ_OK;
+
+ BZFILE* bz_file = BZ2_bzWriteOpen(&err,
+ file,
+ 9, // max compression
+ 0, // verbosity
+ 0); // default work factor
+ TEST_AND_RETURN_FALSE(err == BZ_OK);
+
+ vector<Extent> extents;
+ vector<Block>::size_type block_count = 0;
+
+ LOG(INFO) << "Appending left over blocks to extents";
+ for (vector<Block>::size_type i = 0; i < blocks.size(); i++) {
+ if (blocks[i].writer != Vertex::kInvalidIndex)
+ continue;
+ if (blocks[i].reader != Vertex::kInvalidIndex) {
+ graph_utils::AddReadBeforeDep(vertex, blocks[i].reader, i);
+ }
+ graph_utils::AppendBlockToExtents(&extents, i);
+ block_count++;
+ }
+
+ // Code will handle 'buf' at any size that's a multiple of kBlockSize,
+ // so we arbitrarily set it to 1024 * kBlockSize.
+ vector<char> buf(1024 * kBlockSize);
+
+ LOG(INFO) << "Reading left over blocks";
+ vector<Block>::size_type blocks_copied_count = 0;
+
+ // For each extent in extents, write the data into BZ2_bzWrite which
+ // sends it to an output file.
+ // We use the temporary buffer 'buf' to hold the data, which may be
+ // smaller than the extent, so in that case we have to loop to get
+ // the extent's data (that's the inner while loop).
+ for (vector<Extent>::const_iterator it = extents.begin();
+ it != extents.end(); ++it) {
+ vector<Block>::size_type blocks_read = 0;
+ float printed_progress = -1;
+ while (blocks_read < it->num_blocks()) {
+ const int copy_block_cnt =
+ min(buf.size() / kBlockSize,
+ static_cast<vector<char>::size_type>(
+ it->num_blocks() - blocks_read));
+ ssize_t rc = pread(image_fd,
+ &buf[0],
+ copy_block_cnt * kBlockSize,
+ (it->start_block() + blocks_read) * kBlockSize);
+ TEST_AND_RETURN_FALSE_ERRNO(rc >= 0);
+ TEST_AND_RETURN_FALSE(static_cast<size_t>(rc) ==
+ copy_block_cnt * kBlockSize);
+ BZ2_bzWrite(&err, bz_file, &buf[0], copy_block_cnt * kBlockSize);
+ TEST_AND_RETURN_FALSE(err == BZ_OK);
+ blocks_read += copy_block_cnt;
+ blocks_copied_count += copy_block_cnt;
+ float current_progress =
+ static_cast<float>(blocks_copied_count) / block_count;
+ if (printed_progress + 0.1 < current_progress ||
+ blocks_copied_count == block_count) {
+ LOG(INFO) << "progress: " << current_progress;
+ printed_progress = current_progress;
+ }
+ }
+ }
+ BZ2_bzWriteClose(&err, bz_file, 0, NULL, NULL);
+ TEST_AND_RETURN_FALSE(err == BZ_OK);
+ bz_file = NULL;
+ TEST_AND_RETURN_FALSE_ERRNO(0 == fclose(file));
+ file = NULL;
+
+ vector<char> compressed_data;
+ LOG(INFO) << "Reading compressed data off disk";
+ TEST_AND_RETURN_FALSE(utils::ReadFile(temp_file_path, &compressed_data));
+ TEST_AND_RETURN_FALSE(unlink(temp_file_path.c_str()) == 0);
+
+ // Add node to graph to write these blocks
+ out_op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ out_op->set_data_offset(*blobs_length);
+ out_op->set_data_length(compressed_data.size());
+ LOG(INFO) << "Rootfs non-data blocks compressed take up "
+ << compressed_data.size();
+ *blobs_length += compressed_data.size();
+ out_op->set_dst_length(kBlockSize * block_count);
+ DeltaDiffGenerator::StoreExtents(extents, out_op->mutable_dst_extents());
+
+ TEST_AND_RETURN_FALSE(utils::WriteAll(blobs_fd,
+ &compressed_data[0],
+ compressed_data.size()));
+ LOG(INFO) << "done with extra blocks";
+ return true;
+}
+
+// Writes the uint64_t passed in in host-endian to the file as big-endian.
+// Returns true on success.
+bool WriteUint64AsBigEndian(FileWriter* writer, const uint64_t value) {
+ uint64_t value_be = htobe64(value);
+ TEST_AND_RETURN_FALSE(writer->Write(&value_be, sizeof(value_be)));
+ return true;
+}
+
+// Adds each operation from |graph| to |out_manifest| in the order specified by
+// |order| while building |out_op_name_map| with operation to name
+// mappings. Adds all |kernel_ops| to |out_manifest|. Filters out no-op
+// operations.
+void InstallOperationsToManifest(
+ const Graph& graph,
+ const vector<Vertex::Index>& order,
+ const vector<DeltaArchiveManifest_InstallOperation>& kernel_ops,
+ DeltaArchiveManifest* out_manifest,
+ OperationNameMap* out_op_name_map) {
+ for (vector<Vertex::Index>::const_iterator it = order.begin();
+ it != order.end(); ++it) {
+ const Vertex& vertex = graph[*it];
+ const DeltaArchiveManifest_InstallOperation& add_op = vertex.op;
+ if (DeltaDiffGenerator::IsNoopOperation(add_op)) {
+ continue;
+ }
+ DeltaArchiveManifest_InstallOperation* op =
+ out_manifest->add_install_operations();
+ *op = add_op;
+ string name = vertex.file_name;
+ if (vertex.chunk_offset || vertex.chunk_size != -1) {
+ string offset = base::Int64ToString(vertex.chunk_offset);
+ if (vertex.chunk_size != -1) {
+ name += " [" + offset + ", " +
+ base::Int64ToString(vertex.chunk_offset + vertex.chunk_size - 1) +
+ "]";
+ } else {
+ name += " [" + offset + ", end]";
+ }
+ }
+ (*out_op_name_map)[op] = name;
+ }
+ for (vector<DeltaArchiveManifest_InstallOperation>::const_iterator it =
+ kernel_ops.begin(); it != kernel_ops.end(); ++it) {
+ const DeltaArchiveManifest_InstallOperation& add_op = *it;
+ if (DeltaDiffGenerator::IsNoopOperation(add_op)) {
+ continue;
+ }
+ DeltaArchiveManifest_InstallOperation* op =
+ out_manifest->add_kernel_install_operations();
+ *op = add_op;
+ }
+}
+
+void CheckGraph(const Graph& graph) {
+ for (Graph::const_iterator it = graph.begin(); it != graph.end(); ++it) {
+ CHECK(it->op.has_type());
+ }
+}
+
+// Delta compresses a kernel partition |new_kernel_part| with knowledge of the
+// old kernel partition |old_kernel_part|. If |old_kernel_part| is an empty
+// string, generates a full update of the partition.
+bool DeltaCompressKernelPartition(
+ const string& old_kernel_part,
+ const string& new_kernel_part,
+ vector<DeltaArchiveManifest_InstallOperation>* ops,
+ int blobs_fd,
+ off_t* blobs_length) {
+ LOG(INFO) << "Delta compressing kernel partition...";
+ LOG_IF(INFO, old_kernel_part.empty()) << "Generating full kernel update...";
+
+ DeltaArchiveManifest_InstallOperation op;
+ vector<char> data;
+ TEST_AND_RETURN_FALSE(
+ DeltaDiffGenerator::ReadFileToDiff(old_kernel_part,
+ new_kernel_part,
+ 0, // chunk_offset
+ -1, // chunk_size
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ false));
+
+ // Check if the operation writes nothing.
+ if (op.dst_extents_size() == 0) {
+ if (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+ LOG(INFO) << "Empty MOVE operation, nothing to do.";
+ return true;
+ } else {
+ LOG(ERROR) << "Empty non-MOVE operation";
+ return false;
+ }
+ }
+
+ // Write the data.
+ if (op.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+ op.set_data_offset(*blobs_length);
+ op.set_data_length(data.size());
+ }
+
+ // Add the new install operation.
+ ops->clear();
+ ops->push_back(op);
+
+ TEST_AND_RETURN_FALSE(utils::WriteAll(blobs_fd, &data[0], data.size()));
+ *blobs_length += data.size();
+
+ LOG(INFO) << "Done delta compressing kernel partition: "
+ << kInstallOperationTypes[op.type()];
+ return true;
+}
+
+struct DeltaObject {
+ DeltaObject(const string& in_name, const int in_type, const off_t in_size)
+ : name(in_name),
+ type(in_type),
+ size(in_size) {}
+ bool operator <(const DeltaObject& object) const {
+ return (size != object.size) ? (size < object.size) : (name < object.name);
+ }
+ string name;
+ int type;
+ off_t size;
+};
+
+void ReportPayloadUsage(const DeltaArchiveManifest& manifest,
+ const int64_t manifest_metadata_size,
+ const OperationNameMap& op_name_map) {
+ vector<DeltaObject> objects;
+ off_t total_size = 0;
+
+ // Rootfs install operations.
+ for (int i = 0; i < manifest.install_operations_size(); ++i) {
+ const DeltaArchiveManifest_InstallOperation& op =
+ manifest.install_operations(i);
+ objects.push_back(DeltaObject(op_name_map.find(&op)->second,
+ op.type(),
+ op.data_length()));
+ total_size += op.data_length();
+ }
+
+ // Kernel install operations.
+ for (int i = 0; i < manifest.kernel_install_operations_size(); ++i) {
+ const DeltaArchiveManifest_InstallOperation& op =
+ manifest.kernel_install_operations(i);
+ objects.push_back(DeltaObject(base::StringPrintf("<kernel-operation-%d>",
+ i),
+ op.type(),
+ op.data_length()));
+ total_size += op.data_length();
+ }
+
+ objects.push_back(DeltaObject("<manifest-metadata>",
+ -1,
+ manifest_metadata_size));
+ total_size += manifest_metadata_size;
+
+ std::sort(objects.begin(), objects.end());
+
+ static const char kFormatString[] = "%6.2f%% %10jd %-10s %s\n";
+ for (vector<DeltaObject>::const_iterator it = objects.begin();
+ it != objects.end(); ++it) {
+ const DeltaObject& object = *it;
+ fprintf(stderr, kFormatString,
+ object.size * 100.0 / total_size,
+ static_cast<intmax_t>(object.size),
+ object.type >= 0 ? kInstallOperationTypes[object.type] : "-",
+ object.name.c_str());
+ }
+ fprintf(stderr, kFormatString,
+ 100.0, static_cast<intmax_t>(total_size), "", "<total>");
+}
+
+// Process a range of blocks from |range_start| to |range_end| in the extent at
+// position |*idx_p| of |extents|. If |do_remove| is true, this range will be
+// removed, which may cause the extent to be trimmed, split or removed entirely.
+// The value of |*idx_p| is updated to point to the next extent to be processed.
+// Returns true iff the next extent to process is a new or updated one.
+bool ProcessExtentBlockRange(vector<Extent>* extents, size_t* idx_p,
+ const bool do_remove, uint64_t range_start,
+ uint64_t range_end) {
+ size_t idx = *idx_p;
+ uint64_t start_block = (*extents)[idx].start_block();
+ uint64_t num_blocks = (*extents)[idx].num_blocks();
+ uint64_t range_size = range_end - range_start;
+
+ if (do_remove) {
+ if (range_size == num_blocks) {
+ // Remove the entire extent.
+ extents->erase(extents->begin() + idx);
+ } else if (range_end == num_blocks) {
+ // Trim the end of the extent.
+ (*extents)[idx].set_num_blocks(num_blocks - range_size);
+ idx++;
+ } else if (range_start == 0) {
+ // Trim the head of the extent.
+ (*extents)[idx].set_start_block(start_block + range_size);
+ (*extents)[idx].set_num_blocks(num_blocks - range_size);
+ } else {
+ // Trim the middle, splitting the remainder into two parts.
+ (*extents)[idx].set_num_blocks(range_start);
+ Extent e;
+ e.set_start_block(start_block + range_end);
+ e.set_num_blocks(num_blocks - range_end);
+ idx++;
+ extents->insert(extents->begin() + idx, e);
+ }
+ } else if (range_end == num_blocks) {
+ // Done with this extent.
+ idx++;
+ } else {
+ return false;
+ }
+
+ *idx_p = idx;
+ return true;
+}
+
+// Remove identical corresponding block ranges in |src_extents| and
+// |dst_extents|. Used for preventing moving of blocks onto themselves during
+// MOVE operations. The value of |total_bytes| indicates the actual length of
+// content; this may be slightly less than the total size of blocks, in which
+// case the last block is only partly occupied with data. Returns the total
+// number of bytes removed.
+size_t RemoveIdenticalBlockRanges(vector<Extent>* src_extents,
+ vector<Extent>* dst_extents,
+ const size_t total_bytes) {
+ size_t src_idx = 0;
+ size_t dst_idx = 0;
+ uint64_t src_offset = 0, dst_offset = 0;
+ bool new_src = true, new_dst = true;
+ size_t removed_bytes = 0, nonfull_block_bytes;
+ bool do_remove = false;
+ while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) {
+ if (new_src) {
+ src_offset = 0;
+ new_src = false;
+ }
+ if (new_dst) {
+ dst_offset = 0;
+ new_dst = false;
+ }
+
+ do_remove = ((*src_extents)[src_idx].start_block() + src_offset ==
+ (*dst_extents)[dst_idx].start_block() + dst_offset);
+
+ uint64_t src_num_blocks = (*src_extents)[src_idx].num_blocks();
+ uint64_t dst_num_blocks = (*dst_extents)[dst_idx].num_blocks();
+ uint64_t min_num_blocks = min(src_num_blocks - src_offset,
+ dst_num_blocks - dst_offset);
+ uint64_t prev_src_offset = src_offset;
+ uint64_t prev_dst_offset = dst_offset;
+ src_offset += min_num_blocks;
+ dst_offset += min_num_blocks;
+
+ new_src = ProcessExtentBlockRange(src_extents, &src_idx, do_remove,
+ prev_src_offset, src_offset);
+ new_dst = ProcessExtentBlockRange(dst_extents, &dst_idx, do_remove,
+ prev_dst_offset, dst_offset);
+ if (do_remove)
+ removed_bytes += min_num_blocks * kBlockSize;
+ }
+
+ // If we removed the last block and this block is only partly used by file
+ // content, deduct the unused portion from the total removed byte count.
+ if (do_remove && (nonfull_block_bytes = total_bytes % kBlockSize))
+ removed_bytes -= kBlockSize - nonfull_block_bytes;
+
+ return removed_bytes;
+}
+
+} // namespace {}
+
+bool DeltaDiffGenerator::ReadFileToDiff(
+ const string& old_filename,
+ const string& new_filename,
+ off_t chunk_offset,
+ off_t chunk_size,
+ bool bsdiff_allowed,
+ vector<char>* out_data,
+ DeltaArchiveManifest_InstallOperation* out_op,
+ bool gather_extents) {
+ // Read new data in
+ vector<char> new_data;
+ TEST_AND_RETURN_FALSE(
+ utils::ReadFileChunk(new_filename, chunk_offset, chunk_size, &new_data));
+
+ TEST_AND_RETURN_FALSE(!new_data.empty());
+ TEST_AND_RETURN_FALSE(chunk_size == -1 ||
+ static_cast<off_t>(new_data.size()) <= chunk_size);
+
+ vector<char> new_data_bz;
+ TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
+ CHECK(!new_data_bz.empty());
+
+ vector<char> data; // Data blob that will be written to delta file.
+
+ DeltaArchiveManifest_InstallOperation operation;
+ size_t current_best_size = 0;
+ if (new_data.size() <= new_data_bz.size()) {
+ operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ current_best_size = new_data.size();
+ data = new_data;
+ } else {
+ operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ current_best_size = new_data_bz.size();
+ data = new_data_bz;
+ }
+
+ // Do we have an original file to consider?
+ struct stat old_stbuf;
+ bool original = !old_filename.empty();
+ if (original && 0 != stat(old_filename.c_str(), &old_stbuf)) {
+ // If stat-ing the old file fails, it should be because it doesn't exist.
+ TEST_AND_RETURN_FALSE(errno == ENOTDIR || errno == ENOENT);
+ original = false;
+ }
+
+ vector<char> old_data;
+ if (original) {
+ // Read old data
+ TEST_AND_RETURN_FALSE(
+ utils::ReadFileChunk(
+ old_filename, chunk_offset, chunk_size, &old_data));
+ if (old_data == new_data) {
+ // No change in data.
+ operation.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ current_best_size = 0;
+ data.clear();
+ } else if (!old_data.empty() && bsdiff_allowed) {
+ // If the source file is considered bsdiff safe (no bsdiff bugs
+ // triggered), see if BSDIFF encoding is smaller.
+ base::FilePath old_chunk;
+ TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&old_chunk));
+ ScopedPathUnlinker old_unlinker(old_chunk.value());
+ TEST_AND_RETURN_FALSE(
+ utils::WriteFile(old_chunk.value().c_str(),
+ &old_data[0], old_data.size()));
+ base::FilePath new_chunk;
+ TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&new_chunk));
+ ScopedPathUnlinker new_unlinker(new_chunk.value());
+ TEST_AND_RETURN_FALSE(
+ utils::WriteFile(new_chunk.value().c_str(),
+ &new_data[0], new_data.size()));
+
+ vector<char> bsdiff_delta;
+ TEST_AND_RETURN_FALSE(
+ BsdiffFiles(old_chunk.value(), new_chunk.value(), &bsdiff_delta));
+ CHECK_GT(bsdiff_delta.size(), static_cast<vector<char>::size_type>(0));
+ if (bsdiff_delta.size() < current_best_size) {
+ operation.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+ current_best_size = bsdiff_delta.size();
+ data = bsdiff_delta;
+ }
+ }
+ }
+
+ // Set parameters of the operations
+ CHECK_EQ(data.size(), current_best_size);
+
+ vector<Extent> src_extents, dst_extents;
+ if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE ||
+ operation.type() == DeltaArchiveManifest_InstallOperation_Type_BSDIFF) {
+ if (gather_extents) {
+ TEST_AND_RETURN_FALSE(
+ GatherExtents(old_filename,
+ chunk_offset,
+ chunk_size,
+ &src_extents));
+ } else {
+ Extent* src_extent = operation.add_src_extents();
+ src_extent->set_start_block(0);
+ src_extent->set_num_blocks(
+ (old_stbuf.st_size + kBlockSize - 1) / kBlockSize);
+ }
+ operation.set_src_length(old_data.size());
+ }
+
+ if (gather_extents) {
+ TEST_AND_RETURN_FALSE(
+ GatherExtents(new_filename,
+ chunk_offset,
+ chunk_size,
+ &dst_extents));
+ } else {
+ Extent* dst_extent = operation.add_dst_extents();
+ dst_extent->set_start_block(0);
+ dst_extent->set_num_blocks((new_data.size() + kBlockSize - 1) / kBlockSize);
+ }
+ operation.set_dst_length(new_data.size());
+
+ if (gather_extents) {
+ // Remove identical src/dst block ranges in MOVE operations.
+ if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+ size_t removed_bytes = RemoveIdenticalBlockRanges(
+ &src_extents, &dst_extents, new_data.size());
+
+ // Adjust the file length field accordingly.
+ if (removed_bytes) {
+ operation.set_src_length(old_data.size() - removed_bytes);
+ operation.set_dst_length(new_data.size() - removed_bytes);
+ }
+ }
+
+ // Embed extents in the operation.
+ DeltaDiffGenerator::StoreExtents(src_extents,
+ operation.mutable_src_extents());
+ DeltaDiffGenerator::StoreExtents(dst_extents,
+ operation.mutable_dst_extents());
+ }
+
+ out_data->swap(data);
+ *out_op = operation;
+
+ return true;
+}
+
+bool DeltaDiffGenerator::InitializePartitionInfo(bool is_kernel,
+ const string& partition,
+ PartitionInfo* info) {
+ int64_t size = 0;
+ if (is_kernel) {
+ size = utils::FileSize(partition);
+ } else {
+ int block_count = 0, block_size = 0;
+ TEST_AND_RETURN_FALSE(utils::GetFilesystemSize(partition,
+ &block_count,
+ &block_size));
+ size = static_cast<int64_t>(block_count) * block_size;
+ }
+ TEST_AND_RETURN_FALSE(size > 0);
+ info->set_size(size);
+ OmahaHashCalculator hasher;
+ TEST_AND_RETURN_FALSE(hasher.UpdateFile(partition, size) == size);
+ TEST_AND_RETURN_FALSE(hasher.Finalize());
+ const vector<char>& hash = hasher.raw_hash();
+ info->set_hash(hash.data(), hash.size());
+ LOG(INFO) << partition << ": size=" << size << " hash=" << hasher.hash();
+ return true;
+}
+
+bool InitializePartitionInfos(const string& old_kernel,
+ const string& new_kernel,
+ const string& old_rootfs,
+ const string& new_rootfs,
+ DeltaArchiveManifest* manifest) {
+ if (!old_kernel.empty()) {
+ TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
+ true,
+ old_kernel,
+ manifest->mutable_old_kernel_info()));
+ }
+ TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
+ true,
+ new_kernel,
+ manifest->mutable_new_kernel_info()));
+ if (!old_rootfs.empty()) {
+ TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
+ false,
+ old_rootfs,
+ manifest->mutable_old_rootfs_info()));
+ }
+ TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
+ false,
+ new_rootfs,
+ manifest->mutable_new_rootfs_info()));
+ return true;
+}
+
+namespace {
+
+// Takes a collection (vector or RepeatedPtrField) of Extent and
+// returns a vector of the blocks referenced, in order.
+template<typename T>
+vector<uint64_t> ExpandExtents(const T& extents) {
+ vector<uint64_t> ret;
+ for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) {
+ const Extent extent = graph_utils::GetElement(extents, i);
+ if (extent.start_block() == kSparseHole) {
+ ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
+ } else {
+ for (uint64_t block = extent.start_block();
+ block < (extent.start_block() + extent.num_blocks()); block++) {
+ ret.push_back(block);
+ }
+ }
+ }
+ return ret;
+}
+
+// Takes a vector of blocks and returns an equivalent vector of Extent
+// objects.
+vector<Extent> CompressExtents(const vector<uint64_t>& blocks) {
+ vector<Extent> new_extents;
+ for (vector<uint64_t>::const_iterator it = blocks.begin(), e = blocks.end();
+ it != e; ++it) {
+ graph_utils::AppendBlockToExtents(&new_extents, *it);
+ }
+ return new_extents;
+}
+
+} // namespace {}
+
+void DeltaDiffGenerator::SubstituteBlocks(
+ Vertex* vertex,
+ const vector<Extent>& remove_extents,
+ const vector<Extent>& replace_extents) {
+ // First, expand out the blocks that op reads from
+ vector<uint64_t> read_blocks = ExpandExtents(vertex->op.src_extents());
+ {
+ // Expand remove_extents and replace_extents
+ vector<uint64_t> remove_extents_expanded =
+ ExpandExtents(remove_extents);
+ vector<uint64_t> replace_extents_expanded =
+ ExpandExtents(replace_extents);
+ CHECK_EQ(remove_extents_expanded.size(), replace_extents_expanded.size());
+ map<uint64_t, uint64_t> conversion;
+ for (vector<uint64_t>::size_type i = 0;
+ i < replace_extents_expanded.size(); i++) {
+ conversion[remove_extents_expanded[i]] = replace_extents_expanded[i];
+ }
+ utils::ApplyMap(&read_blocks, conversion);
+ for (Vertex::EdgeMap::iterator it = vertex->out_edges.begin(),
+ e = vertex->out_edges.end(); it != e; ++it) {
+ vector<uint64_t> write_before_deps_expanded =
+ ExpandExtents(it->second.write_extents);
+ utils::ApplyMap(&write_before_deps_expanded, conversion);
+ it->second.write_extents = CompressExtents(write_before_deps_expanded);
+ }
+ }
+ // Convert read_blocks back to extents
+ vertex->op.clear_src_extents();
+ vector<Extent> new_extents = CompressExtents(read_blocks);
+ DeltaDiffGenerator::StoreExtents(new_extents,
+ vertex->op.mutable_src_extents());
+}
+
+bool DeltaDiffGenerator::CutEdges(Graph* graph,
+ const set<Edge>& edges,
+ vector<CutEdgeVertexes>* out_cuts) {
+ DummyExtentAllocator scratch_allocator;
+ vector<CutEdgeVertexes> cuts;
+ cuts.reserve(edges.size());
+
+ uint64_t scratch_blocks_used = 0;
+ for (set<Edge>::const_iterator it = edges.begin();
+ it != edges.end(); ++it) {
+ cuts.resize(cuts.size() + 1);
+ vector<Extent> old_extents =
+ (*graph)[it->first].out_edges[it->second].extents;
+ // Choose some scratch space
+ scratch_blocks_used += graph_utils::EdgeWeight(*graph, *it);
+ cuts.back().tmp_extents =
+ scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, *it));
+ // create vertex to copy original->scratch
+ cuts.back().new_vertex = graph->size();
+ graph->resize(graph->size() + 1);
+ cuts.back().old_src = it->first;
+ cuts.back().old_dst = it->second;
+
+ EdgeProperties& cut_edge_properties =
+ (*graph)[it->first].out_edges.find(it->second)->second;
+
+ // This should never happen, as we should only be cutting edges between
+ // real file nodes, and write-before relationships are created from
+ // a real file node to a temp copy node:
+ CHECK(cut_edge_properties.write_extents.empty())
+ << "Can't cut edge that has write-before relationship.";
+
+ // make node depend on the copy operation
+ (*graph)[it->first].out_edges.insert(make_pair(graph->size() - 1,
+ cut_edge_properties));
+
+ // Set src/dst extents and other proto variables for copy operation
+ graph->back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ DeltaDiffGenerator::StoreExtents(
+ cut_edge_properties.extents,
+ graph->back().op.mutable_src_extents());
+ DeltaDiffGenerator::StoreExtents(cuts.back().tmp_extents,
+ graph->back().op.mutable_dst_extents());
+ graph->back().op.set_src_length(
+ graph_utils::EdgeWeight(*graph, *it) * kBlockSize);
+ graph->back().op.set_dst_length(graph->back().op.src_length());
+
+ // make the dest node read from the scratch space
+ DeltaDiffGenerator::SubstituteBlocks(
+ &((*graph)[it->second]),
+ (*graph)[it->first].out_edges[it->second].extents,
+ cuts.back().tmp_extents);
+
+ // delete the old edge
+ CHECK_EQ(static_cast<Graph::size_type>(1),
+ (*graph)[it->first].out_edges.erase(it->second));
+
+ // Add an edge from dst to copy operation
+ EdgeProperties write_before_edge_properties;
+ write_before_edge_properties.write_extents = cuts.back().tmp_extents;
+ (*graph)[it->second].out_edges.insert(
+ make_pair(graph->size() - 1, write_before_edge_properties));
+ }
+ out_cuts->swap(cuts);
+ return true;
+}
+
+// Stores all Extents in 'extents' into 'out'.
+void DeltaDiffGenerator::StoreExtents(
+ const vector<Extent>& extents,
+ google::protobuf::RepeatedPtrField<Extent>* out) {
+ for (vector<Extent>::const_iterator it = extents.begin();
+ it != extents.end(); ++it) {
+ Extent* new_extent = out->Add();
+ *new_extent = *it;
+ }
+}
+
+// Creates all the edges for the graph. Writers of a block point to
+// readers of the same block. This is because for an edge A->B, B
+// must complete before A executes.
+void DeltaDiffGenerator::CreateEdges(Graph* graph,
+ const vector<Block>& blocks) {
+ for (vector<Block>::size_type i = 0; i < blocks.size(); i++) {
+ // Blocks with both a reader and writer get an edge
+ if (blocks[i].reader == Vertex::kInvalidIndex ||
+ blocks[i].writer == Vertex::kInvalidIndex)
+ continue;
+ // Don't have a node depend on itself
+ if (blocks[i].reader == blocks[i].writer)
+ continue;
+ // See if there's already an edge we can add onto
+ Vertex::EdgeMap::iterator edge_it =
+ (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader);
+ if (edge_it == (*graph)[blocks[i].writer].out_edges.end()) {
+ // No existing edge. Create one
+ (*graph)[blocks[i].writer].out_edges.insert(
+ make_pair(blocks[i].reader, EdgeProperties()));
+ edge_it = (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader);
+ CHECK(edge_it != (*graph)[blocks[i].writer].out_edges.end());
+ }
+ graph_utils::AppendBlockToExtents(&edge_it->second.extents, i);
+ }
+}
+
+namespace {
+
+class SortCutsByTopoOrderLess {
+ public:
+ SortCutsByTopoOrderLess(vector<vector<Vertex::Index>::size_type>& table)
+ : table_(table) {}
+ bool operator()(const CutEdgeVertexes& a, const CutEdgeVertexes& b) {
+ return table_[a.old_dst] < table_[b.old_dst];
+ }
+ private:
+ vector<vector<Vertex::Index>::size_type>& table_;
+};
+
+} // namespace {}
+
+void DeltaDiffGenerator::GenerateReverseTopoOrderMap(
+ vector<Vertex::Index>& op_indexes,
+ vector<vector<Vertex::Index>::size_type>* reverse_op_indexes) {
+ vector<vector<Vertex::Index>::size_type> table(op_indexes.size());
+ for (vector<Vertex::Index>::size_type i = 0, e = op_indexes.size();
+ i != e; ++i) {
+ Vertex::Index node = op_indexes[i];
+ if (table.size() < (node + 1)) {
+ table.resize(node + 1);
+ }
+ table[node] = i;
+ }
+ reverse_op_indexes->swap(table);
+}
+
+void DeltaDiffGenerator::SortCutsByTopoOrder(vector<Vertex::Index>& op_indexes,
+ vector<CutEdgeVertexes>* cuts) {
+ // first, make a reverse lookup table.
+ vector<vector<Vertex::Index>::size_type> table;
+ GenerateReverseTopoOrderMap(op_indexes, &table);
+ SortCutsByTopoOrderLess less(table);
+ sort(cuts->begin(), cuts->end(), less);
+}
+
+void DeltaDiffGenerator::MoveFullOpsToBack(Graph* graph,
+ vector<Vertex::Index>* op_indexes) {
+ vector<Vertex::Index> ret;
+ vector<Vertex::Index> full_ops;
+ ret.reserve(op_indexes->size());
+ for (vector<Vertex::Index>::size_type i = 0, e = op_indexes->size(); i != e;
+ ++i) {
+ DeltaArchiveManifest_InstallOperation_Type type =
+ (*graph)[(*op_indexes)[i]].op.type();
+ if (type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+ type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+ full_ops.push_back((*op_indexes)[i]);
+ } else {
+ ret.push_back((*op_indexes)[i]);
+ }
+ }
+ LOG(INFO) << "Stats: " << full_ops.size() << " full ops out of "
+ << (full_ops.size() + ret.size()) << " total ops.";
+ ret.insert(ret.end(), full_ops.begin(), full_ops.end());
+ op_indexes->swap(ret);
+}
+
+namespace {
+
+template<typename T>
+bool TempBlocksExistInExtents(const T& extents) {
+ for (int i = 0, e = extents.size(); i < e; ++i) {
+ Extent extent = graph_utils::GetElement(extents, i);
+ uint64_t start = extent.start_block();
+ uint64_t num = extent.num_blocks();
+ if (start == kSparseHole)
+ continue;
+ if (start >= kTempBlockStart ||
+ (start + num) >= kTempBlockStart) {
+ LOG(ERROR) << "temp block!";
+ LOG(ERROR) << "start: " << start << ", num: " << num;
+ LOG(ERROR) << "kTempBlockStart: " << kTempBlockStart;
+ LOG(ERROR) << "returning true";
+ return true;
+ }
+ // check for wrap-around, which would be a bug:
+ CHECK(start <= (start + num));
+ }
+ return false;
+}
+
+// Convertes the cuts, which must all have the same |old_dst| member,
+// to full. It does this by converting the |old_dst| to REPLACE or
+// REPLACE_BZ, dropping all incoming edges to |old_dst|, and marking
+// all temp nodes invalid.
+bool ConvertCutsToFull(
+ Graph* graph,
+ const string& new_root,
+ int data_fd,
+ off_t* data_file_size,
+ vector<Vertex::Index>* op_indexes,
+ vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+ const vector<CutEdgeVertexes>& cuts) {
+ CHECK(!cuts.empty());
+ set<Vertex::Index> deleted_nodes;
+ for (vector<CutEdgeVertexes>::const_iterator it = cuts.begin(),
+ e = cuts.end(); it != e; ++it) {
+ TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ConvertCutToFullOp(
+ graph,
+ *it,
+ new_root,
+ data_fd,
+ data_file_size));
+ deleted_nodes.insert(it->new_vertex);
+ }
+ deleted_nodes.insert(cuts[0].old_dst);
+
+ vector<Vertex::Index> new_op_indexes;
+ new_op_indexes.reserve(op_indexes->size());
+ for (vector<Vertex::Index>::iterator it = op_indexes->begin(),
+ e = op_indexes->end(); it != e; ++it) {
+ if (utils::SetContainsKey(deleted_nodes, *it))
+ continue;
+ new_op_indexes.push_back(*it);
+ }
+ new_op_indexes.push_back(cuts[0].old_dst);
+ op_indexes->swap(new_op_indexes);
+ DeltaDiffGenerator::GenerateReverseTopoOrderMap(*op_indexes,
+ reverse_op_indexes);
+ return true;
+}
+
+// Tries to assign temp blocks for a collection of cuts, all of which share
+// the same old_dst member. If temp blocks can't be found, old_dst will be
+// converted to a REPLACE or REPLACE_BZ operation. Returns true on success,
+// which can happen even if blocks are converted to full. Returns false
+// on exceptional error cases.
+bool AssignBlockForAdjoiningCuts(
+ Graph* graph,
+ const string& new_root,
+ int data_fd,
+ off_t* data_file_size,
+ vector<Vertex::Index>* op_indexes,
+ vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+ const vector<CutEdgeVertexes>& cuts) {
+ CHECK(!cuts.empty());
+ const Vertex::Index old_dst = cuts[0].old_dst;
+ // Calculate # of blocks needed
+ uint64_t blocks_needed = 0;
+ map<const CutEdgeVertexes*, uint64_t> cuts_blocks_needed;
+ for (vector<CutEdgeVertexes>::const_iterator it = cuts.begin(),
+ e = cuts.end(); it != e; ++it) {
+ uint64_t cut_blocks_needed = 0;
+ for (vector<Extent>::const_iterator jt = it->tmp_extents.begin(),
+ je = it->tmp_extents.end(); jt != je; ++jt) {
+ cut_blocks_needed += jt->num_blocks();
+ }
+ blocks_needed += cut_blocks_needed;
+ cuts_blocks_needed[&*it] = cut_blocks_needed;
+ }
+
+ // Find enough blocks
+ ExtentRanges scratch_ranges;
+ // Each block that's supplying temp blocks and the corresponding blocks:
+ typedef vector<pair<Vertex::Index, ExtentRanges> > SupplierVector;
+ SupplierVector block_suppliers;
+ uint64_t scratch_blocks_found = 0;
+ for (vector<Vertex::Index>::size_type i = (*reverse_op_indexes)[old_dst] + 1,
+ e = op_indexes->size(); i < e; ++i) {
+ Vertex::Index test_node = (*op_indexes)[i];
+ if (!(*graph)[test_node].valid)
+ continue;
+ // See if this node has sufficient blocks
+ ExtentRanges ranges;
+ ranges.AddRepeatedExtents((*graph)[test_node].op.dst_extents());
+ ranges.SubtractExtent(ExtentForRange(
+ kTempBlockStart, kSparseHole - kTempBlockStart));
+ ranges.SubtractRepeatedExtents((*graph)[test_node].op.src_extents());
+ // For now, for simplicity, subtract out all blocks in read-before
+ // dependencies.
+ for (Vertex::EdgeMap::const_iterator edge_i =
+ (*graph)[test_node].out_edges.begin(),
+ 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);
+ 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) {
+ LOG(INFO) << "Unable to find sufficient scratch";
+ TEST_AND_RETURN_FALSE(ConvertCutsToFull(graph,
+ new_root,
+ data_fd,
+ data_file_size,
+ op_indexes,
+ reverse_op_indexes,
+ cuts));
+ return true;
+ }
+ // Use the scratch we found
+ TEST_AND_RETURN_FALSE(scratch_ranges.blocks() == scratch_blocks_found);
+
+ // Make all the suppliers depend on this node
+ for (SupplierVector::iterator it = block_suppliers.begin(),
+ e = block_suppliers.end(); it != e; ++it) {
+ graph_utils::AddReadBeforeDepExtents(
+ &(*graph)[it->first],
+ old_dst,
+ it->second.GetExtentsForBlockCount(it->second.blocks()));
+ }
+
+ // Replace temp blocks in each cut
+ for (vector<CutEdgeVertexes>::const_iterator it = cuts.begin(),
+ e = cuts.end(); it != e; ++it) {
+ vector<Extent> real_extents =
+ scratch_ranges.GetExtentsForBlockCount(cuts_blocks_needed[&*it]);
+ scratch_ranges.SubtractExtents(real_extents);
+
+ // Fix the old dest node w/ the real blocks
+ DeltaDiffGenerator::SubstituteBlocks(&(*graph)[old_dst],
+ it->tmp_extents,
+ real_extents);
+
+ // Fix the new node w/ the real blocks. Since the new node is just a
+ // copy operation, we can replace all the dest extents w/ the real
+ // blocks.
+ DeltaArchiveManifest_InstallOperation *op =
+ &(*graph)[it->new_vertex].op;
+ op->clear_dst_extents();
+ DeltaDiffGenerator::StoreExtents(real_extents, op->mutable_dst_extents());
+ }
+ return true;
+}
+
+} // namespace {}
+
+// 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).
+bool DeltaDiffGenerator::IsNoopOperation(
+ const DeltaArchiveManifest_InstallOperation& op) {
+ return (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE &&
+ ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
+}
+
+bool DeltaDiffGenerator::AssignTempBlocks(
+ Graph* graph,
+ const string& new_root,
+ int data_fd,
+ off_t* data_file_size,
+ vector<Vertex::Index>* op_indexes,
+ vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+ const vector<CutEdgeVertexes>& cuts) {
+ CHECK(!cuts.empty());
+
+ // group of cuts w/ the same old_dst:
+ vector<CutEdgeVertexes> cuts_group;
+
+ for (vector<CutEdgeVertexes>::size_type i = cuts.size() - 1, e = 0;
+ true ; --i) {
+ LOG(INFO) << "Fixing temp blocks in cut " << i
+ << ": old dst: " << cuts[i].old_dst << " new vertex: "
+ << cuts[i].new_vertex << " path: "
+ << (*graph)[cuts[i].old_dst].file_name;
+
+ if (cuts_group.empty() || (cuts_group[0].old_dst == cuts[i].old_dst)) {
+ cuts_group.push_back(cuts[i]);
+ } else {
+ CHECK(!cuts_group.empty());
+ TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
+ new_root,
+ data_fd,
+ data_file_size,
+ op_indexes,
+ reverse_op_indexes,
+ cuts_group));
+ cuts_group.clear();
+ cuts_group.push_back(cuts[i]);
+ }
+
+ if (i == e) {
+ // break out of for() loop
+ break;
+ }
+ }
+ CHECK(!cuts_group.empty());
+ TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
+ new_root,
+ data_fd,
+ data_file_size,
+ op_indexes,
+ reverse_op_indexes,
+ cuts_group));
+ return true;
+}
+
+bool DeltaDiffGenerator::NoTempBlocksRemain(const Graph& graph) {
+ size_t idx = 0;
+ for (Graph::const_iterator it = graph.begin(), e = graph.end(); it != e;
+ ++it, ++idx) {
+ if (!it->valid)
+ continue;
+ const DeltaArchiveManifest_InstallOperation& op = it->op;
+ if (TempBlocksExistInExtents(op.dst_extents()) ||
+ TempBlocksExistInExtents(op.src_extents())) {
+ LOG(INFO) << "bad extents in node " << idx;
+ LOG(INFO) << "so yeah";
+ return false;
+ }
+
+ // Check out-edges:
+ for (Vertex::EdgeMap::const_iterator jt = it->out_edges.begin(),
+ je = it->out_edges.end(); jt != je; ++jt) {
+ if (TempBlocksExistInExtents(jt->second.extents) ||
+ TempBlocksExistInExtents(jt->second.write_extents)) {
+ LOG(INFO) << "bad out edge in node " << idx;
+ LOG(INFO) << "so yeah";
+ return false;
+ }
+ }
+ }
+ return true;
+}
+
+bool DeltaDiffGenerator::ReorderDataBlobs(
+ DeltaArchiveManifest* manifest,
+ const std::string& data_blobs_path,
+ const std::string& new_data_blobs_path) {
+ int in_fd = open(data_blobs_path.c_str(), O_RDONLY, 0);
+ TEST_AND_RETURN_FALSE_ERRNO(in_fd >= 0);
+ ScopedFdCloser in_fd_closer(&in_fd);
+
+ DirectFileWriter writer;
+ TEST_AND_RETURN_FALSE(
+ writer.Open(new_data_blobs_path.c_str(),
+ O_WRONLY | O_TRUNC | O_CREAT,
+ 0644) == 0);
+ ScopedFileWriterCloser writer_closer(&writer);
+ uint64_t out_file_size = 0;
+
+ for (int i = 0; i < (manifest->install_operations_size() +
+ manifest->kernel_install_operations_size()); i++) {
+ DeltaArchiveManifest_InstallOperation* op = NULL;
+ if (i < manifest->install_operations_size()) {
+ op = manifest->mutable_install_operations(i);
+ } else {
+ op = manifest->mutable_kernel_install_operations(
+ i - manifest->install_operations_size());
+ }
+ if (!op->has_data_offset())
+ continue;
+ CHECK(op->has_data_length());
+ vector<char> buf(op->data_length());
+ ssize_t rc = pread(in_fd, &buf[0], buf.size(), op->data_offset());
+ TEST_AND_RETURN_FALSE(rc == static_cast<ssize_t>(buf.size()));
+
+ // Add the hash of the data blobs for this operation
+ TEST_AND_RETURN_FALSE(AddOperationHash(op, buf));
+
+ op->set_data_offset(out_file_size);
+ TEST_AND_RETURN_FALSE(writer.Write(&buf[0], buf.size()));
+ out_file_size += buf.size();
+ }
+ return true;
+}
+
+bool DeltaDiffGenerator::AddOperationHash(
+ DeltaArchiveManifest_InstallOperation* op,
+ const vector<char>& buf) {
+ OmahaHashCalculator hasher;
+
+ TEST_AND_RETURN_FALSE(hasher.Update(&buf[0], buf.size()));
+ TEST_AND_RETURN_FALSE(hasher.Finalize());
+
+ const vector<char>& hash = hasher.raw_hash();
+ op->set_data_sha256_hash(hash.data(), hash.size());
+ return true;
+}
+
+bool DeltaDiffGenerator::ConvertCutToFullOp(Graph* graph,
+ const CutEdgeVertexes& cut,
+ const string& new_root,
+ int data_fd,
+ off_t* data_file_size) {
+ // Drop all incoming edges, keep all outgoing edges
+
+ // Keep all outgoing edges
+ if ((*graph)[cut.old_dst].op.type() !=
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ &&
+ (*graph)[cut.old_dst].op.type() !=
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+ Vertex::EdgeMap out_edges = (*graph)[cut.old_dst].out_edges;
+ graph_utils::DropWriteBeforeDeps(&out_edges);
+
+ TEST_AND_RETURN_FALSE(DeltaReadFile(graph,
+ cut.old_dst,
+ NULL,
+ kNonexistentPath,
+ new_root,
+ (*graph)[cut.old_dst].file_name,
+ (*graph)[cut.old_dst].chunk_offset,
+ (*graph)[cut.old_dst].chunk_size,
+ data_fd,
+ data_file_size));
+
+ (*graph)[cut.old_dst].out_edges = out_edges;
+
+ // Right now we don't have doubly-linked edges, so we have to scan
+ // the whole graph.
+ graph_utils::DropIncomingEdgesTo(graph, cut.old_dst);
+ }
+
+ // Delete temp node
+ (*graph)[cut.old_src].out_edges.erase(cut.new_vertex);
+ CHECK((*graph)[cut.old_dst].out_edges.find(cut.new_vertex) ==
+ (*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,
+ 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...";
+ vector<CutEdgeVertexes> cuts;
+ TEST_AND_RETURN_FALSE(CutEdges(graph, cut_edges, &cuts));
+ LOG(INFO) << "done cutting cycles";
+ LOG(INFO) << "There are " << cuts.size() << " cuts.";
+ CheckGraph(*graph);
+
+ LOG(INFO) << "Creating initial topological order...";
+ TopologicalSort(*graph, final_order);
+ LOG(INFO) << "done with initial topo order";
+ CheckGraph(*graph);
+
+ LOG(INFO) << "Moving full ops to the back";
+ MoveFullOpsToBack(graph, final_order);
+ LOG(INFO) << "done moving full ops to back";
+
+ vector<vector<Vertex::Index>::size_type> inverse_final_order;
+ GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
+
+ SortCutsByTopoOrder(*final_order, &cuts);
+
+ 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,
+ off_t chunk_size,
+ size_t rootfs_partition_size,
+ const ImageInfo* old_image_info,
+ const ImageInfo* new_image_info,
+ uint64_t* metadata_size) {
+ TEST_AND_RETURN_FALSE(chunk_size == -1 || chunk_size % kBlockSize == 0);
+ int old_image_block_count = 0, old_image_block_size = 0;
+ int new_image_block_count = 0, new_image_block_size = 0;
+ TEST_AND_RETURN_FALSE(utils::GetFilesystemSize(new_image,
+ &new_image_block_count,
+ &new_image_block_size));
+ if (!old_image.empty()) {
+ TEST_AND_RETURN_FALSE(utils::GetFilesystemSize(old_image,
+ &old_image_block_count,
+ &old_image_block_size));
+ TEST_AND_RETURN_FALSE(old_image_block_size == new_image_block_size);
+ LOG_IF(WARNING, old_image_block_count != new_image_block_count)
+ << "Old and new images have different block counts.";
+
+ // If new_image_info is present, old_image_info must be present.
+ TEST_AND_RETURN_FALSE((bool)old_image_info == (bool)new_image_info);
+ } else {
+ // old_image_info must not be present for a full update.
+ TEST_AND_RETURN_FALSE(!old_image_info);
+ }
+
+ // Sanity checks for the partition size.
+ TEST_AND_RETURN_FALSE(rootfs_partition_size % kBlockSize == 0);
+ size_t fs_size = static_cast<size_t>(new_image_block_size) *
+ new_image_block_count;
+ LOG(INFO) << "Rootfs partition size: " << rootfs_partition_size;
+ LOG(INFO) << "Actual filesystem size: " << fs_size;
+ TEST_AND_RETURN_FALSE(rootfs_partition_size >= fs_size);
+
+ // Sanity check kernel partition arg
+ TEST_AND_RETURN_FALSE(utils::FileSize(new_kernel_part) >= 0);
+
+ vector<Block> blocks(max(old_image_block_count, new_image_block_count));
+ LOG(INFO) << "Invalid block index: " << Vertex::kInvalidIndex;
+ LOG(INFO) << "Block count: " << blocks.size();
+ for (vector<Block>::size_type i = 0; i < blocks.size(); i++) {
+ CHECK(blocks[i].reader == Vertex::kInvalidIndex);
+ CHECK(blocks[i].writer == Vertex::kInvalidIndex);
+ }
+ Graph graph;
+ CheckGraph(graph);
+
+ const string kTempFileTemplate("CrAU_temp_data.XXXXXX");
+ string temp_file_path;
+ scoped_ptr<ScopedPathUnlinker> temp_file_unlinker;
+ off_t data_file_size = 0;
+
+ LOG(INFO) << "Reading files...";
+
+ // Create empty protobuf Manifest object
+ DeltaArchiveManifest manifest;
+
+ 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));
+ temp_file_unlinker.reset(new ScopedPathUnlinker(temp_file_path));
+ 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,
+ chunk_size,
+ fd,
+ &data_file_size));
+ LOG(INFO) << "done reading normal files";
+ CheckGraph(graph);
+
+ LOG(INFO) << "Starting metadata processing";
+ TEST_AND_RETURN_FALSE(Metadata::DeltaReadMetadata(&graph,
+ &blocks,
+ old_image,
+ new_image,
+ fd,
+ &data_file_size));
+ LOG(INFO) << "Done metadata processing";
+ 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() < (rootfs_partition_size / kBlockSize)) {
+ scratch_vertex = graph.size();
+ graph.resize(graph.size() + 1);
+ CreateScratchNode(blocks.size(),
+ (rootfs_partition_size / 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,
+ scratch_vertex));
+
+ // Set the minor version for this payload.
+ LOG(INFO) << "Adding Delta Minor Version.";
+ manifest.set_minor_version(DeltaPerformer::kSupportedMinorPayloadVersion);
+ } 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,
+ kFullUpdateChunkSize,
+ kBlockSize,
+ &kernel_ops,
+ &final_order));
+
+ // Set the minor version for this payload.
+ LOG(INFO) << "Adding Full Minor Version.";
+ manifest.set_minor_version(DeltaPerformer::kFullPayloadMinorVersion);
+ }
+ }
+
+ if (old_image_info)
+ *(manifest.mutable_old_image_info()) = *old_image_info;
+
+ if (new_image_info)
+ *(manifest.mutable_new_image_info()) = *new_image_info;
+
+ OperationNameMap op_name_map;
+ CheckGraph(graph);
+ InstallOperationsToManifest(graph,
+ final_order,
+ kernel_ops,
+ &manifest,
+ &op_name_map);
+ CheckGraph(graph);
+ manifest.set_block_size(kBlockSize);
+
+ // Reorder the data blobs with the newly ordered manifest
+ string ordered_blobs_path;
+ TEST_AND_RETURN_FALSE(utils::MakeTempFile(
+ "CrAU_temp_data.ordered.XXXXXX",
+ &ordered_blobs_path,
+ NULL));
+ ScopedPathUnlinker ordered_blobs_unlinker(ordered_blobs_path);
+ TEST_AND_RETURN_FALSE(ReorderDataBlobs(&manifest,
+ temp_file_path,
+ ordered_blobs_path));
+ temp_file_unlinker.reset();
+
+ // Check that install op blobs are in order.
+ uint64_t next_blob_offset = 0;
+ {
+ for (int i = 0; i < (manifest.install_operations_size() +
+ manifest.kernel_install_operations_size()); i++) {
+ DeltaArchiveManifest_InstallOperation* op =
+ i < manifest.install_operations_size() ?
+ manifest.mutable_install_operations(i) :
+ manifest.mutable_kernel_install_operations(
+ i - manifest.install_operations_size());
+ if (op->has_data_offset()) {
+ if (op->data_offset() != next_blob_offset) {
+ LOG(FATAL) << "bad blob offset! " << op->data_offset() << " != "
+ << next_blob_offset;
+ }
+ next_blob_offset += op->data_length();
+ }
+ }
+ }
+
+ // Signatures appear at the end of the blobs. Note the offset in the
+ // manifest
+ if (!private_key_path.empty()) {
+ uint64_t signature_blob_length = 0;
+ TEST_AND_RETURN_FALSE(
+ PayloadSigner::SignatureBlobLength(vector<string>(1, private_key_path),
+ &signature_blob_length));
+ AddSignatureOp(next_blob_offset, signature_blob_length, &manifest);
+ }
+
+ TEST_AND_RETURN_FALSE(InitializePartitionInfos(old_kernel_part,
+ new_kernel_part,
+ old_image,
+ new_image,
+ &manifest));
+
+ // Serialize protobuf
+ string serialized_manifest;
+
+ CheckGraph(graph);
+ TEST_AND_RETURN_FALSE(manifest.AppendToString(&serialized_manifest));
+ CheckGraph(graph);
+
+ LOG(INFO) << "Writing final delta file header...";
+ DirectFileWriter writer;
+ TEST_AND_RETURN_FALSE_ERRNO(writer.Open(output_path.c_str(),
+ O_WRONLY | O_CREAT | O_TRUNC,
+ 0644) == 0);
+ ScopedFileWriterCloser writer_closer(&writer);
+
+ // Write header
+ TEST_AND_RETURN_FALSE(writer.Write(kDeltaMagic, strlen(kDeltaMagic)));
+
+ // Write version number
+ TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer, kVersionNumber));
+
+ // Write protobuf length
+ TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer,
+ serialized_manifest.size()));
+
+ // Write protobuf
+ LOG(INFO) << "Writing final delta file protobuf... "
+ << serialized_manifest.size();
+ TEST_AND_RETURN_FALSE(writer.Write(serialized_manifest.data(),
+ serialized_manifest.size()));
+
+ // Append the data blobs
+ LOG(INFO) << "Writing final delta file data blobs...";
+ int blobs_fd = open(ordered_blobs_path.c_str(), O_RDONLY, 0);
+ ScopedFdCloser blobs_fd_closer(&blobs_fd);
+ TEST_AND_RETURN_FALSE(blobs_fd >= 0);
+ for (;;) {
+ char buf[kBlockSize];
+ ssize_t rc = read(blobs_fd, buf, sizeof(buf));
+ if (0 == rc) {
+ // EOF
+ break;
+ }
+ TEST_AND_RETURN_FALSE_ERRNO(rc > 0);
+ TEST_AND_RETURN_FALSE(writer.Write(buf, rc));
+ }
+
+ // Write signature blob.
+ if (!private_key_path.empty()) {
+ LOG(INFO) << "Signing the update...";
+ vector<char> signature_blob;
+ TEST_AND_RETURN_FALSE(PayloadSigner::SignPayload(
+ output_path,
+ vector<string>(1, private_key_path),
+ &signature_blob));
+ TEST_AND_RETURN_FALSE(writer.Write(&signature_blob[0],
+ signature_blob.size()));
+ }
+
+ *metadata_size =
+ strlen(kDeltaMagic) + 2 * sizeof(uint64_t) + serialized_manifest.size();
+ ReportPayloadUsage(manifest, *metadata_size, op_name_map);
+
+ LOG(INFO) << "All done. Successfully created delta file with "
+ << "metadata size = " << *metadata_size;
+ return true;
+}
+
+// Runs the bsdiff tool on two files and returns the resulting delta in
+// 'out'. Returns true on success.
+bool DeltaDiffGenerator::BsdiffFiles(const string& old_file,
+ const string& new_file,
+ vector<char>* out) {
+ const string kPatchFile = "delta.patchXXXXXX";
+ string patch_file_path;
+
+ TEST_AND_RETURN_FALSE(
+ utils::MakeTempFile(kPatchFile, &patch_file_path, NULL));
+
+ vector<string> cmd;
+ cmd.push_back(kBsdiffPath);
+ cmd.push_back(old_file);
+ cmd.push_back(new_file);
+ cmd.push_back(patch_file_path);
+
+ int rc = 1;
+ vector<char> patch_file;
+ TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, NULL));
+ TEST_AND_RETURN_FALSE(rc == 0);
+ TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
+ unlink(patch_file_path.c_str());
+ return true;
+}
+
+// The |blocks| vector contains a reader and writer for each block on the
+// filesystem that's being in-place updated. We populate the reader/writer
+// fields of |blocks| by calling this function.
+// For each block in |operation| that is read or written, find that block
+// in |blocks| and set the reader/writer field to the vertex passed.
+// |graph| is not strictly necessary, but useful for printing out
+// error messages.
+bool DeltaDiffGenerator::AddInstallOpToBlocksVector(
+ const DeltaArchiveManifest_InstallOperation& operation,
+ const Graph& graph,
+ Vertex::Index vertex,
+ vector<Block>* blocks) {
+ // See if this is already present.
+ TEST_AND_RETURN_FALSE(operation.dst_extents_size() > 0);
+
+ enum BlockField { READER = 0, WRITER, BLOCK_FIELD_COUNT };
+ for (int field = READER; field < BLOCK_FIELD_COUNT; field++) {
+ const int extents_size =
+ (field == READER) ? operation.src_extents_size() :
+ operation.dst_extents_size();
+ const char* past_participle = (field == READER) ? "read" : "written";
+ const google::protobuf::RepeatedPtrField<Extent>& extents =
+ (field == READER) ? operation.src_extents() : operation.dst_extents();
+ Vertex::Index Block::*access_type =
+ (field == READER) ? &Block::reader : &Block::writer;
+
+ for (int i = 0; i < extents_size; i++) {
+ const Extent& extent = extents.Get(i);
+ if (extent.start_block() == kSparseHole) {
+ // Hole in sparse file. skip
+ continue;
+ }
+ for (uint64_t block = extent.start_block();
+ block < (extent.start_block() + extent.num_blocks()); block++) {
+ if ((*blocks)[block].*access_type != Vertex::kInvalidIndex) {
+ LOG(FATAL) << "Block " << block << " is already "
+ << past_participle << " by "
+ << (*blocks)[block].*access_type << "("
+ << graph[(*blocks)[block].*access_type].file_name
+ << ") and also " << vertex << "("
+ << graph[vertex].file_name << ")";
+ }
+ (*blocks)[block].*access_type = vertex;
+ }
+ }
+ }
+ return true;
+}
+
+void DeltaDiffGenerator::AddSignatureOp(uint64_t signature_blob_offset,
+ uint64_t signature_blob_length,
+ DeltaArchiveManifest* manifest) {
+ LOG(INFO) << "Making room for signature in file";
+ manifest->set_signatures_offset(signature_blob_offset);
+ LOG(INFO) << "set? " << manifest->has_signatures_offset();
+ // Add a dummy op at the end to appease older clients
+ DeltaArchiveManifest_InstallOperation* dummy_op =
+ manifest->add_kernel_install_operations();
+ dummy_op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ dummy_op->set_data_offset(signature_blob_offset);
+ manifest->set_signatures_offset(signature_blob_offset);
+ dummy_op->set_data_length(signature_blob_length);
+ manifest->set_signatures_size(signature_blob_length);
+ Extent* dummy_extent = dummy_op->add_dst_extents();
+ // Tell the dummy op to write this data to a big sparse hole
+ dummy_extent->set_start_block(kSparseHole);
+ dummy_extent->set_num_blocks((signature_blob_length + kBlockSize - 1) /
+ kBlockSize);
+}
+
+const char* const kBsdiffPath = "bsdiff";
+
+}; // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
new file mode 100644
index 0000000..596d9c0
--- /dev/null
+++ b/payload_generator/delta_diff_generator.h
@@ -0,0 +1,276 @@
+// Copyright (c) 2012 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_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
+
+#include <string>
+#include <vector>
+
+#include <base/basictypes.h>
+
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/update_metadata.pb.h"
+
+// There is one function in DeltaDiffGenerator of importance to users
+// of the class: GenerateDeltaUpdateFile(). Before calling it,
+// the old and new images must be mounted. Call GenerateDeltaUpdateFile()
+// with both the mount-points of the images in addition to the paths of
+// the images (both old and new). A delta from old to new will be
+// generated and stored in output_path.
+
+namespace chromeos_update_engine {
+
+// This struct stores all relevant info for an edge that is cut between
+// nodes old_src -> old_dst by creating new vertex new_vertex. The new
+// relationship is:
+// old_src -(read before)-> new_vertex <-(write before)- old_dst
+// new_vertex is a MOVE operation that moves some existing blocks into
+// temp space. The temp extents are, by necessity, stored in new_vertex
+// (as dst extents) and old_dst (as src extents), but they are also broken
+// out into tmp_extents, as the nodes themselves may contain many more
+// extents.
+struct CutEdgeVertexes {
+ Vertex::Index new_vertex;
+ Vertex::Index old_src;
+ Vertex::Index old_dst;
+ std::vector<Extent> tmp_extents;
+};
+
+class DeltaDiffGenerator {
+ public:
+ // Represents a disk block on the install partition.
+ struct Block {
+ // During install, each block on the install partition will be written
+ // and some may be read (in all likelihood, many will be read).
+ // The reading and writing will be performed by InstallOperations,
+ // each of which has a corresponding vertex in a graph.
+ // A Block object tells which vertex will read or write this block
+ // at install time.
+ // Generally, there will be a vector of Block objects whose length
+ // is the number of blocks on the install partition.
+ Block() : reader(Vertex::kInvalidIndex), writer(Vertex::kInvalidIndex) {}
+ Vertex::Index reader;
+ Vertex::Index writer;
+ };
+
+ // This is the only function that external users of the class should call.
+ // old_image and new_image are paths to two image files. They should be
+ // mounted read-only at paths old_root and new_root respectively.
+ // {old,new}_kernel_part are paths to the old and new kernel partition
+ // images, respectively.
+ // private_key_path points to a private key used to sign the update.
+ // Pass empty string to not sign the update.
+ // output_path is the filename where the delta update should be written.
+ // If |chunk_size| is not -1, the delta payload is generated based on
+ // |chunk_size| chunks rather than whole files.
+ // This method computes scratch space based on |rootfs_partition_size|.
+ // Returns true on success. Also writes the size of the metadata into
+ // |metadata_size|.
+ static bool GenerateDeltaUpdateFile(const std::string& old_root,
+ const std::string& old_image,
+ const std::string& new_root,
+ const std::string& new_image,
+ const std::string& old_kernel_part,
+ const std::string& new_kernel_part,
+ const std::string& output_path,
+ const std::string& private_key_path,
+ off_t chunk_size,
+ size_t rootfs_partition_size,
+ const ImageInfo* old_image_info,
+ const ImageInfo* new_image_info,
+ uint64_t* metadata_size);
+
+ // These functions are public so that the unit tests can access them:
+
+ // Takes a graph, which is not a DAG, which represents the files just
+ // read from disk, and converts it into a DAG by breaking all cycles
+ // and finding temp space to resolve broken edges.
+ // 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,
+ 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
+ // necessary data in out_data and fills in out_op.
+ // If there's no change in old and new files, it creates a MOVE
+ // operation. If there is a change, or the old file doesn't exist,
+ // the smallest of REPLACE, REPLACE_BZ, or BSDIFF wins.
+ // new_filename must contain at least one byte.
+ // |new_filename| is read starting at |chunk_offset|.
+ // If |chunk_size| is not -1, only up to |chunk_size| bytes are diffed.
+ // Returns true on success.
+ static bool ReadFileToDiff(const std::string& old_filename,
+ const std::string& new_filename,
+ off_t chunk_offset,
+ off_t chunk_size,
+ bool bsdiff_allowed,
+ std::vector<char>* out_data,
+ 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.
+ // Blocks will be substituted in the order listed in the vectors.
+ // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents
+ // contains blocks 6, 2, 3, 5, and replace blocks contains
+ // 12, 13, 14, 15, then op will be changed to read from:
+ // 1, 13, 14, 4, 15, 12, 7, 8
+ static void SubstituteBlocks(Vertex* vertex,
+ const std::vector<Extent>& remove_extents,
+ const std::vector<Extent>& replace_extents);
+
+ // Cuts 'edges' from 'graph' according to the AU algorithm. This means
+ // for each edge A->B, remove the dependency that B occur before A.
+ // Do this by creating a new operation X that copies from the blocks
+ // specified by the edge's properties to temp space T. Modify B to read
+ // from T rather than the blocks in the edge. Modify A to depend on X,
+ // but not on B. Free space is found by looking in 'blocks'.
+ // Returns true on success.
+ static bool CutEdges(Graph* graph,
+ const std::set<Edge>& edges,
+ std::vector<CutEdgeVertexes>* out_cuts);
+
+ // Stores all Extents in 'extents' into 'out'.
+ static void StoreExtents(const std::vector<Extent>& extents,
+ google::protobuf::RepeatedPtrField<Extent>* out);
+
+ // Creates all the edges for the graph. Writers of a block point to
+ // readers of the same block. This is because for an edge A->B, B
+ // must complete before A executes.
+ static void CreateEdges(Graph* graph, const std::vector<Block>& blocks);
+
+ // Given a topologically sorted graph |op_indexes| and |graph|, alters
+ // |op_indexes| to move all the full operations to the end of the vector.
+ // Full operations should not be depended on, so this is safe.
+ static void MoveFullOpsToBack(Graph* graph,
+ std::vector<Vertex::Index>* op_indexes);
+
+ // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is
+ // determined by the order of elements in op_indexes.
+ static void SortCutsByTopoOrder(std::vector<Vertex::Index>& op_indexes,
+ std::vector<CutEdgeVertexes>* cuts);
+
+ // Returns true iff there are no extents in the graph that refer to temp
+ // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole).
+ static bool NoTempBlocksRemain(const Graph& graph);
+
+ // Install operations in the manifest may reference data blobs, which
+ // are in data_blobs_path. This function creates a new data blobs file
+ // with the data blobs in the same order as the referencing install
+ // operations in the manifest. E.g. if manifest[0] has a data blob
+ // "X" at offset 1, manifest[1] has a data blob "Y" at offset 0,
+ // and data_blobs_path's file contains "YX", new_data_blobs_path
+ // will set to be a file that contains "XY".
+ static bool ReorderDataBlobs(DeltaArchiveManifest* manifest,
+ const std::string& data_blobs_path,
+ const std::string& new_data_blobs_path);
+
+ // Computes a SHA256 hash of the given buf and sets the hash value in the
+ // operation so that update_engine could verify. This hash should be set
+ // for all operations that have a non-zero data blob. One exception is the
+ // dummy operation for signature blob because the contents of the signature
+ // blob will not be available at payload creation time. So, update_engine will
+ // gracefully ignore the dummy signature operation.
+ static bool AddOperationHash(DeltaArchiveManifest_InstallOperation* op,
+ const std::vector<char>& buf);
+
+ // Handles allocation of temp blocks to a cut edge by converting the
+ // dest node to a full op. This removes the need for temp blocks, but
+ // comes at the cost of a worse compression ratio.
+ // For example, say we have A->B->A. It would first be cut to form:
+ // A->B->N<-A, where N copies blocks to temp space. If there are no
+ // temp blocks, this function can be called to convert it to the form:
+ // A->B. Now, A is a full operation.
+ static bool ConvertCutToFullOp(Graph* graph,
+ const CutEdgeVertexes& cut,
+ const std::string& new_root,
+ int data_fd,
+ off_t* data_file_size);
+
+ // Takes |op_indexes|, which is effectively a mapping from order in
+ // which the op is performed -> graph vertex index, and produces the
+ // reverse: a mapping from graph vertex index -> op_indexes index.
+ static void GenerateReverseTopoOrderMap(
+ std::vector<Vertex::Index>& op_indexes,
+ std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes);
+
+ // Takes a |graph|, which has edges that must be cut, as listed in
+ // |cuts|. Cuts the edges. Maintains a list in which the operations
+ // will be performed (in |op_indexes|) and the reverse (in
+ // |reverse_op_indexes|). Cutting edges requires scratch space, and
+ // if insufficient scratch is found, the file is reread and will be
+ // send down (either as REPLACE or REPLACE_BZ). Returns true on
+ // success.
+ static bool AssignTempBlocks(
+ Graph* graph,
+ const std::string& new_root,
+ int data_fd,
+ off_t* data_file_size,
+ std::vector<Vertex::Index>* op_indexes,
+ std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes,
+ const std::vector<CutEdgeVertexes>& cuts);
+
+ // 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);
+
+ static bool InitializePartitionInfo(bool is_kernel,
+ const std::string& partition,
+ PartitionInfo* info);
+
+ // Runs the bsdiff tool on two files and returns the resulting delta in
+ // |out|. Returns true on success.
+ static bool BsdiffFiles(const std::string& old_file,
+ const std::string& new_file,
+ std::vector<char>* out);
+
+ // The |blocks| vector contains a reader and writer for each block on the
+ // filesystem that's being in-place updated. We populate the reader/writer
+ // fields of |blocks| by calling this function.
+ // For each block in |operation| that is read or written, find that block
+ // in |blocks| and set the reader/writer field to the vertex passed.
+ // |graph| is not strictly necessary, but useful for printing out
+ // error messages.
+ static bool AddInstallOpToBlocksVector(
+ const DeltaArchiveManifest_InstallOperation& operation,
+ const Graph& graph,
+ Vertex::Index vertex,
+ std::vector<DeltaDiffGenerator::Block>* blocks);
+
+ // Adds to |manifest| a dummy operation that points to a signature blob
+ // located at the specified offset/length.
+ static void AddSignatureOp(uint64_t signature_blob_offset,
+ uint64_t signature_blob_length,
+ DeltaArchiveManifest* manifest);
+
+ private:
+ // This should never be constructed
+ DISALLOW_IMPLICIT_CONSTRUCTORS(DeltaDiffGenerator);
+};
+
+extern const char* const kBsdiffPath;
+extern const size_t kRootFSPartitionSize;
+
+}; // namespace chromeos_update_engine
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
new file mode 100644
index 0000000..05b173c
--- /dev/null
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -0,0 +1,1130 @@
+// Copyright (c) 2012 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 <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <map>
+#include <set>
+#include <sstream>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/logging.h>
+#include <base/strings/string_util.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/delta_performer.h"
+#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/cycle_breaker.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/extent_mapper.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/topological_sort.h"
+#include "update_engine/subprocess.h"
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::set;
+using std::string;
+using std::stringstream;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+typedef DeltaDiffGenerator::Block Block;
+
+typedef bool (*GetExtentsWithChunk)(const std::string&, off_t, off_t,
+ std::vector<Extent>*);
+extern GetExtentsWithChunk get_extents_with_chunk_func;
+
+namespace {
+int64_t BlocksInExtents(
+ const google::protobuf::RepeatedPtrField<Extent>& extents) {
+ int64_t ret = 0;
+ for (int i = 0; i < extents.size(); i++) {
+ ret += extents.Get(i).num_blocks();
+ }
+ return ret;
+}
+} // namespace {}
+
+class DeltaDiffGeneratorTest : public ::testing::Test {
+ protected:
+ const string& old_path() { return old_path_; }
+ const string& new_path() { return new_path_; }
+
+ virtual void SetUp() {
+ ASSERT_TRUE(utils::MakeTempFile("DeltaDiffGeneratorTest-old_path-XXXXXX",
+ &old_path_, NULL));
+ ASSERT_TRUE(utils::MakeTempFile("DeltaDiffGeneratorTest-new_path-XXXXXX",
+ &new_path_, NULL));
+ }
+
+ virtual void TearDown() {
+ unlink(old_path().c_str());
+ unlink(new_path().c_str());
+ }
+
+ private:
+ string old_path_;
+ string new_path_;
+};
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootMoveSmallTest) {
+ EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+ reinterpret_cast<const char*>(kRandomString),
+ sizeof(kRandomString)));
+ EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+ reinterpret_cast<const char*>(kRandomString),
+ sizeof(kRandomString)));
+ vector<char> data;
+ DeltaArchiveManifest_InstallOperation op;
+ EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+ new_path(),
+ 0, // chunk_offset
+ -1, // chunk_size
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ true));
+ EXPECT_TRUE(data.empty());
+
+ EXPECT_TRUE(op.has_type());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
+ EXPECT_FALSE(op.has_data_offset());
+ EXPECT_FALSE(op.has_data_length());
+ EXPECT_EQ(1, op.src_extents_size());
+ EXPECT_EQ(sizeof(kRandomString), op.src_length());
+ EXPECT_EQ(1, op.dst_extents_size());
+ EXPECT_EQ(sizeof(kRandomString), op.dst_length());
+ EXPECT_EQ(BlocksInExtents(op.src_extents()),
+ BlocksInExtents(op.dst_extents()));
+ EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+}
+
+std::map<string, vector<Extent>*> fake_file_extents;
+
+bool FakeGetExtents(const string& path, off_t chunk_offset, off_t chunk_size,
+ vector<Extent>* out) {
+ if (fake_file_extents.count(path) == 1) {
+ *out = *fake_file_extents[path];
+ return true;
+ } else {
+ return false;
+ }
+}
+
+uint64_t AddExtent(uint64_t start_block, uint64_t num_blocks,
+ vector<Extent>* extents) {
+ Extent e;
+ e.set_start_block(start_block);
+ e.set_num_blocks(num_blocks);
+ extents->push_back(e);
+ return num_blocks;
+}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootMoveWithSameBlock) {
+ // Mock out the extent gathering function.
+ GetExtentsWithChunk orig_get_extents_with_chunk_func =
+ get_extents_with_chunk_func;
+ get_extents_with_chunk_func = FakeGetExtents;
+
+ // Setup the old/new files so that it has immobile chunks; we make sure to
+ // utilize all sub-cases of such chunks: blocks 21--22 induce a split (src)
+ // and complete removal (dst), whereas blocks 24--25 induce trimming of the
+ // tail (src) and head (dst) of extents. The final block (29) is used for
+ // ensuring we properly account for the number of bytes removed in cases where
+ // the last block is partly filled. The detailed configuration:
+ //
+ // Old: [ 20 21 22 23 24 25 ] [ 28 29 ]
+ // New: [ 18 ] [ 21 22 ] [ 20 ] [ 24 25 26 ] [ 29 ]
+ // Same: ^^ ^^ ^^ ^^ ^^
+ vector<Extent> old_extents;
+ uint64_t num_extents = 0;
+ num_extents += AddExtent(20, 6, &old_extents);
+ num_extents += AddExtent(28, 2, &old_extents);
+ fake_file_extents[old_path()] = &old_extents;
+ vector<Extent> new_extents;
+ AddExtent(18, 1, &new_extents);
+ AddExtent(21, 2, &new_extents);
+ AddExtent(20, 1, &new_extents);
+ AddExtent(24, 3, &new_extents);
+ AddExtent(29, 1, &new_extents);
+ fake_file_extents[new_path()] = &new_extents;
+
+ // The size of the data should match the total number of blocks; the last
+ // block is only partly filled.
+ size_t file_len = 7 * 4096 + 3333;
+ const string random_string(reinterpret_cast<const char*>(kRandomString),
+ sizeof(kRandomString));
+ string random_data;
+ while (random_data.size() < file_len)
+ random_data += random_string;
+ if (random_data.size() > file_len)
+ random_data.erase(file_len);
+ EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+ random_data.c_str(), file_len));
+ EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+ random_data.c_str(), file_len));
+
+ vector<char> data;
+ DeltaArchiveManifest_InstallOperation op;
+ EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+ new_path(),
+ 0, // chunk_offset
+ -1, // chunk_size
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ true));
+
+ // Adjust the old/new extents to remove duplicates.
+ old_extents[0].set_num_blocks(1);
+ Extent e;
+ e.set_start_block(23);
+ e.set_num_blocks(1);
+ old_extents.insert(old_extents.begin() + 1, e);
+ old_extents[2].set_num_blocks(1);
+ new_extents.erase(new_extents.begin() + 1);
+ new_extents[2].set_start_block(26);
+ new_extents[2].set_num_blocks(1);
+ new_extents.erase(new_extents.begin() + 3);
+ num_extents -= 5;
+ file_len -= 4 * 4096 + 3333;
+
+ EXPECT_TRUE(data.empty());
+
+ EXPECT_TRUE(op.has_type());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
+ EXPECT_FALSE(op.has_data_offset());
+ EXPECT_FALSE(op.has_data_length());
+
+ EXPECT_EQ(file_len, op.src_length());
+ EXPECT_EQ(num_extents, BlocksInExtents(op.src_extents()));
+ EXPECT_EQ(old_extents.size(), op.src_extents_size());
+ for (int i = 0; i < op.src_extents_size(); i++) {
+ EXPECT_EQ(old_extents[i].start_block(), op.src_extents(i).start_block())
+ << "i == " << i;
+ EXPECT_EQ(old_extents[i].num_blocks(), op.src_extents(i).num_blocks())
+ << "i == " << i;
+ }
+
+ EXPECT_EQ(file_len, op.dst_length());
+ EXPECT_EQ(num_extents, BlocksInExtents(op.dst_extents()));
+ EXPECT_EQ(new_extents.size(), op.dst_extents_size());
+ for (int i = 0; i < op.dst_extents_size(); i++) {
+ EXPECT_EQ(new_extents[i].start_block(), op.dst_extents(i).start_block())
+ << "i == " << i;
+ EXPECT_EQ(new_extents[i].num_blocks(), op.dst_extents(i).num_blocks())
+ << "i == " << i;
+ }
+
+ // Clean up fake extents and restore the module's extent gathering logic.
+ fake_file_extents.clear();
+ get_extents_with_chunk_func = orig_get_extents_with_chunk_func;
+}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffSmallTest) {
+ EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+ reinterpret_cast<const char*>(kRandomString),
+ sizeof(kRandomString) - 1));
+ EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+ reinterpret_cast<const char*>(kRandomString),
+ sizeof(kRandomString)));
+ vector<char> data;
+ DeltaArchiveManifest_InstallOperation op;
+ EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+ new_path(),
+ 0, // chunk_offset
+ -1, // chunk_size
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ true));
+ EXPECT_FALSE(data.empty());
+
+ EXPECT_TRUE(op.has_type());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
+ EXPECT_FALSE(op.has_data_offset());
+ EXPECT_FALSE(op.has_data_length());
+ EXPECT_EQ(1, op.src_extents_size());
+ EXPECT_EQ(sizeof(kRandomString) - 1, op.src_length());
+ EXPECT_EQ(1, op.dst_extents_size());
+ EXPECT_EQ(sizeof(kRandomString), op.dst_length());
+ EXPECT_EQ(BlocksInExtents(op.src_extents()),
+ BlocksInExtents(op.dst_extents()));
+ EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNotAllowedTest) {
+ EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+ reinterpret_cast<const char*>(kRandomString),
+ sizeof(kRandomString) - 1));
+ EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+ reinterpret_cast<const char*>(kRandomString),
+ sizeof(kRandomString)));
+ vector<char> data;
+ DeltaArchiveManifest_InstallOperation op;
+
+ EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+ new_path(),
+ 0, // chunk_offset
+ -1, // chunk_size
+ false, // bsdiff_allowed
+ &data,
+ &op,
+ true));
+ EXPECT_FALSE(data.empty());
+
+ // The point of this test is that we don't use BSDIFF the way the above
+ // did. The rest of the details are to be caught in other tests.
+ EXPECT_TRUE(op.has_type());
+ EXPECT_NE(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
+}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNotAllowedMoveTest) {
+ EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+ reinterpret_cast<const char*>(kRandomString),
+ sizeof(kRandomString)));
+ EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+ reinterpret_cast<const char*>(kRandomString),
+ sizeof(kRandomString)));
+ vector<char> data;
+ DeltaArchiveManifest_InstallOperation op;
+
+ EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+ new_path(),
+ 0, // chunk_offset
+ -1, // chunk_size
+ false, // bsdiff_allowed
+ &data,
+ &op,
+ true));
+ EXPECT_TRUE(data.empty());
+
+ // The point of this test is that we can still use a MOVE for a file
+ // that is blacklisted.
+ EXPECT_TRUE(op.has_type());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
+}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootReplaceSmallTest) {
+ vector<char> new_data;
+ for (int i = 0; i < 2; i++) {
+ new_data.insert(new_data.end(),
+ kRandomString,
+ kRandomString + sizeof(kRandomString));
+ EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+ &new_data[0],
+ new_data.size()));
+ vector<char> data;
+ DeltaArchiveManifest_InstallOperation op;
+ EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+ new_path(),
+ 0, // chunk_offset
+ -1, // chunk_size
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ true));
+ EXPECT_FALSE(data.empty());
+
+ EXPECT_TRUE(op.has_type());
+ const DeltaArchiveManifest_InstallOperation_Type expected_type =
+ (i == 0 ? DeltaArchiveManifest_InstallOperation_Type_REPLACE :
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ EXPECT_EQ(expected_type, op.type());
+ EXPECT_FALSE(op.has_data_offset());
+ EXPECT_FALSE(op.has_data_length());
+ EXPECT_EQ(0, op.src_extents_size());
+ EXPECT_FALSE(op.has_src_length());
+ EXPECT_EQ(1, op.dst_extents_size());
+ EXPECT_EQ(new_data.size(), op.dst_length());
+ EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+ }
+}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNoGatherExtentsSmallTest) {
+ EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+ reinterpret_cast<const char*>(kRandomString),
+ sizeof(kRandomString) - 1));
+ EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+ reinterpret_cast<const char*>(kRandomString),
+ sizeof(kRandomString)));
+ vector<char> data;
+ DeltaArchiveManifest_InstallOperation op;
+ EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+ new_path(),
+ 0, // chunk_offset
+ -1, // chunk_size
+ true, // bsdiff_allowed
+ &data,
+ &op,
+ false));
+ EXPECT_FALSE(data.empty());
+
+ EXPECT_TRUE(op.has_type());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
+ EXPECT_FALSE(op.has_data_offset());
+ EXPECT_FALSE(op.has_data_length());
+ EXPECT_EQ(1, op.src_extents_size());
+ EXPECT_EQ(0, op.src_extents().Get(0).start_block());
+ EXPECT_EQ(1, op.src_extents().Get(0).num_blocks());
+ EXPECT_EQ(sizeof(kRandomString) - 1, op.src_length());
+ EXPECT_EQ(1, op.dst_extents_size());
+ EXPECT_EQ(0, op.dst_extents().Get(0).start_block());
+ EXPECT_EQ(1, op.dst_extents().Get(0).num_blocks());
+ EXPECT_EQ(sizeof(kRandomString), op.dst_length());
+}
+
+namespace {
+void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
+ vect->resize(vect->size() + 1);
+ vect->back().set_start_block(start);
+ vect->back().set_num_blocks(length);
+}
+void OpAppendExtent(DeltaArchiveManifest_InstallOperation* op,
+ uint64_t start,
+ uint64_t length) {
+ Extent* extent = op->add_src_extents();
+ extent->set_start_block(start);
+ extent->set_num_blocks(length);
+}
+}
+
+TEST_F(DeltaDiffGeneratorTest, SubstituteBlocksTest) {
+ vector<Extent> remove_blocks;
+ AppendExtent(&remove_blocks, 3, 3);
+ AppendExtent(&remove_blocks, 7, 1);
+ vector<Extent> replace_blocks;
+ AppendExtent(&replace_blocks, 10, 2);
+ AppendExtent(&replace_blocks, 13, 2);
+ Vertex vertex;
+ DeltaArchiveManifest_InstallOperation& op = vertex.op;
+ OpAppendExtent(&op, 4, 3);
+ OpAppendExtent(&op, kSparseHole, 4); // Sparse hole in file
+ OpAppendExtent(&op, 3, 1);
+ OpAppendExtent(&op, 7, 3);
+
+ DeltaDiffGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
+
+ EXPECT_EQ(7, op.src_extents_size());
+ EXPECT_EQ(11, op.src_extents(0).start_block());
+ EXPECT_EQ(1, op.src_extents(0).num_blocks());
+ EXPECT_EQ(13, op.src_extents(1).start_block());
+ EXPECT_EQ(1, op.src_extents(1).num_blocks());
+ EXPECT_EQ(6, op.src_extents(2).start_block());
+ EXPECT_EQ(1, op.src_extents(2).num_blocks());
+ EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
+ EXPECT_EQ(4, op.src_extents(3).num_blocks());
+ EXPECT_EQ(10, op.src_extents(4).start_block());
+ EXPECT_EQ(1, op.src_extents(4).num_blocks());
+ EXPECT_EQ(14, op.src_extents(5).start_block());
+ EXPECT_EQ(1, op.src_extents(5).num_blocks());
+ EXPECT_EQ(8, op.src_extents(6).start_block());
+ EXPECT_EQ(2, op.src_extents(6).num_blocks());
+}
+
+TEST_F(DeltaDiffGeneratorTest, CutEdgesTest) {
+ Graph graph;
+ vector<Block> blocks(9);
+
+ // Create nodes in graph
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ // Reads from blocks 3, 5, 7
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, 3);
+ graph_utils::AppendBlockToExtents(&extents, 5);
+ graph_utils::AppendBlockToExtents(&extents, 7);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_src_extents());
+ blocks[3].reader = graph.size() - 1;
+ blocks[5].reader = graph.size() - 1;
+ blocks[7].reader = graph.size() - 1;
+
+ // Writes to blocks 1, 2, 4
+ extents.clear();
+ graph_utils::AppendBlockToExtents(&extents, 1);
+ graph_utils::AppendBlockToExtents(&extents, 2);
+ graph_utils::AppendBlockToExtents(&extents, 4);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[1].writer = graph.size() - 1;
+ blocks[2].writer = graph.size() - 1;
+ blocks[4].writer = graph.size() - 1;
+ }
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ // Reads from blocks 1, 2, 4
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, 1);
+ graph_utils::AppendBlockToExtents(&extents, 2);
+ graph_utils::AppendBlockToExtents(&extents, 4);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_src_extents());
+ blocks[1].reader = graph.size() - 1;
+ blocks[2].reader = graph.size() - 1;
+ blocks[4].reader = graph.size() - 1;
+
+ // Writes to blocks 3, 5, 6
+ extents.clear();
+ graph_utils::AppendBlockToExtents(&extents, 3);
+ graph_utils::AppendBlockToExtents(&extents, 5);
+ graph_utils::AppendBlockToExtents(&extents, 6);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[3].writer = graph.size() - 1;
+ blocks[5].writer = graph.size() - 1;
+ blocks[6].writer = graph.size() - 1;
+ }
+
+ // Create edges
+ DeltaDiffGenerator::CreateEdges(&graph, blocks);
+
+ // Find cycles
+ CycleBreaker cycle_breaker;
+ set<Edge> cut_edges;
+ cycle_breaker.BreakCycles(graph, &cut_edges);
+
+ EXPECT_EQ(1, cut_edges.size());
+ EXPECT_TRUE(cut_edges.end() != cut_edges.find(make_pair<Vertex::Index>(1,
+ 0)));
+
+ vector<CutEdgeVertexes> cuts;
+ EXPECT_TRUE(DeltaDiffGenerator::CutEdges(&graph, cut_edges, &cuts));
+
+ EXPECT_EQ(3, graph.size());
+
+ // Check new node in graph:
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
+ graph.back().op.type());
+ EXPECT_EQ(2, graph.back().op.src_extents_size());
+ EXPECT_EQ(1, graph.back().op.dst_extents_size());
+ EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
+ EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
+ EXPECT_TRUE(graph.back().out_edges.empty());
+
+ // Check that old node reads from new blocks
+ EXPECT_EQ(2, graph[0].op.src_extents_size());
+ EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
+ EXPECT_EQ(2, graph[0].op.src_extents(0).num_blocks());
+ EXPECT_EQ(7, graph[0].op.src_extents(1).start_block());
+ EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks());
+
+ // And that the old dst extents haven't changed
+ EXPECT_EQ(2, graph[0].op.dst_extents_size());
+ EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block());
+ EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks());
+ EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block());
+ EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks());
+
+ // Ensure it only depends on the next node and the new temp node
+ EXPECT_EQ(2, graph[0].out_edges.size());
+ EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
+ EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
+ 1));
+
+ // Check second node has unchanged extents
+ EXPECT_EQ(2, graph[1].op.src_extents_size());
+ EXPECT_EQ(1, graph[1].op.src_extents(0).start_block());
+ EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks());
+ EXPECT_EQ(4, graph[1].op.src_extents(1).start_block());
+ EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks());
+
+ EXPECT_EQ(2, graph[1].op.dst_extents_size());
+ EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block());
+ EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
+ EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
+ EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
+
+ // Ensure it only depends on the next node
+ EXPECT_EQ(1, graph[1].out_edges.size());
+ EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
+}
+
+TEST_F(DeltaDiffGeneratorTest, ReorderBlobsTest) {
+ string orig_blobs;
+ EXPECT_TRUE(
+ utils::MakeTempFile("ReorderBlobsTest.orig.XXXXXX", &orig_blobs, NULL));
+
+ string orig_data = "abcd";
+ EXPECT_TRUE(
+ utils::WriteFile(orig_blobs.c_str(), orig_data.data(), orig_data.size()));
+
+ string new_blobs;
+ EXPECT_TRUE(
+ utils::MakeTempFile("ReorderBlobsTest.new.XXXXXX", &new_blobs, NULL));
+
+ DeltaArchiveManifest manifest;
+ DeltaArchiveManifest_InstallOperation* op =
+ manifest.add_install_operations();
+ op->set_data_offset(1);
+ op->set_data_length(3);
+ op = manifest.add_install_operations();
+ op->set_data_offset(0);
+ op->set_data_length(1);
+
+ EXPECT_TRUE(DeltaDiffGenerator::ReorderDataBlobs(&manifest,
+ orig_blobs,
+ new_blobs));
+
+ string new_data;
+ EXPECT_TRUE(utils::ReadFile(new_blobs, &new_data));
+ EXPECT_EQ("bcda", new_data);
+ EXPECT_EQ(2, manifest.install_operations_size());
+ EXPECT_EQ(0, manifest.install_operations(0).data_offset());
+ EXPECT_EQ(3, manifest.install_operations(0).data_length());
+ EXPECT_EQ(3, manifest.install_operations(1).data_offset());
+ EXPECT_EQ(1, manifest.install_operations(1).data_length());
+
+ unlink(orig_blobs.c_str());
+ unlink(new_blobs.c_str());
+}
+
+TEST_F(DeltaDiffGeneratorTest, MoveFullOpsToBackTest) {
+ Graph graph(4);
+ graph[0].file_name = "A";
+ graph[0].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ graph[1].file_name = "B";
+ graph[1].op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+ graph[2].file_name = "C";
+ graph[2].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ graph[3].file_name = "D";
+ graph[3].op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+
+ vector<Vertex::Index> vect(graph.size());
+
+ for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
+ vect[i] = i;
+ }
+ DeltaDiffGenerator::MoveFullOpsToBack(&graph, &vect);
+ EXPECT_EQ(vect.size(), graph.size());
+ EXPECT_EQ(graph[vect[0]].file_name, "B");
+ EXPECT_EQ(graph[vect[1]].file_name, "D");
+ EXPECT_EQ(graph[vect[2]].file_name, "A");
+ EXPECT_EQ(graph[vect[3]].file_name, "C");
+}
+
+namespace {
+
+#define OP_BSDIFF DeltaArchiveManifest_InstallOperation_Type_BSDIFF
+#define OP_MOVE DeltaArchiveManifest_InstallOperation_Type_MOVE
+#define OP_REPLACE DeltaArchiveManifest_InstallOperation_Type_REPLACE
+#define OP_REPLACE_BZ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ
+
+void GenVertex(Vertex* out,
+ const vector<Extent>& src_extents,
+ const vector<Extent>& dst_extents,
+ const string& path,
+ DeltaArchiveManifest_InstallOperation_Type type) {
+ out->op.set_type(type);
+ out->file_name = path;
+ DeltaDiffGenerator::StoreExtents(src_extents, out->op.mutable_src_extents());
+ DeltaDiffGenerator::StoreExtents(dst_extents, out->op.mutable_dst_extents());
+}
+
+vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
+ return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
+}
+
+EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
+ EdgeProperties ret;
+ ret.extents = extents;
+ return ret;
+}
+
+EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
+ EdgeProperties ret;
+ ret.write_extents = extents;
+ return ret;
+}
+
+template<typename T>
+void DumpVect(const vector<T>& vect) {
+ std::stringstream ss(stringstream::out);
+ for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
+ it != e; ++it) {
+ ss << *it << ", ";
+ }
+ LOG(INFO) << "{" << ss.str() << "}";
+}
+
+} // namespace {}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootAssignTempBlocksTest) {
+ Graph graph(9);
+ const vector<Extent> empt; // empty
+ const string kFilename = "/foo";
+
+ // Some scratch space:
+ GenVertex(&graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
+ GenVertex(&graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
+ GenVertex(&graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
+
+ // A cycle that requires 10 blocks to break:
+ GenVertex(&graph[3], VectOfExt(10, 11), VectOfExt(0, 9), "", OP_BSDIFF);
+ graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
+ GenVertex(&graph[4], VectOfExt(0, 9), VectOfExt(10, 11), "", OP_BSDIFF);
+ graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
+
+ // A cycle that requires 9 blocks to break:
+ GenVertex(&graph[5], VectOfExt(40, 11), VectOfExt(30, 10), "", OP_BSDIFF);
+ graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
+ GenVertex(&graph[6], VectOfExt(30, 10), VectOfExt(40, 11), "", OP_BSDIFF);
+ graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
+
+ // A cycle that requires 40 blocks to break (which is too many):
+ GenVertex(&graph[7],
+ VectOfExt(120, 50),
+ VectOfExt(60, 40),
+ "",
+ OP_BSDIFF);
+ graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
+ GenVertex(&graph[8],
+ VectOfExt(60, 40),
+ VectOfExt(120, 50),
+ kFilename,
+ OP_BSDIFF);
+ graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
+
+ graph_utils::DumpGraph(graph);
+
+ vector<Vertex::Index> final_order;
+
+
+ // Prepare the filesystem with the minimum required for this to work
+ string temp_dir;
+ EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksTest.XXXXXX",
+ &temp_dir));
+ ScopedDirRemover temp_dir_remover(temp_dir);
+
+ const size_t kBlockSize = 4096;
+ vector<char> temp_data(kBlockSize * 50);
+ FillWithData(&temp_data);
+ EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
+ ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+ int fd;
+ EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksTestData.XXXXXX",
+ NULL,
+ &fd));
+ ScopedFdCloser fd_closer(&fd);
+ off_t data_file_size = 0;
+
+
+ EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
+ temp_dir,
+ fd,
+ &data_file_size,
+ &final_order,
+ Vertex::kInvalidIndex));
+
+
+ Graph expected_graph(12);
+ GenVertex(&expected_graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
+ GenVertex(&expected_graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
+ GenVertex(&expected_graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
+ GenVertex(&expected_graph[3],
+ VectOfExt(10, 11),
+ VectOfExt(0, 9),
+ "",
+ OP_BSDIFF);
+ expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
+ GenVertex(&expected_graph[4],
+ VectOfExt(60, 9),
+ VectOfExt(10, 11),
+ "",
+ OP_BSDIFF);
+ expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
+ expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
+ GenVertex(&expected_graph[5],
+ VectOfExt(40, 11),
+ VectOfExt(30, 10),
+ "",
+ OP_BSDIFF);
+ expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
+
+ GenVertex(&expected_graph[6],
+ VectOfExt(60, 10),
+ VectOfExt(40, 11),
+ "",
+ OP_BSDIFF);
+ expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
+ expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
+
+ GenVertex(&expected_graph[7],
+ VectOfExt(120, 50),
+ VectOfExt(60, 40),
+ "",
+ OP_BSDIFF);
+ expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
+
+ GenVertex(&expected_graph[8], empt, VectOfExt(0, 50), "/foo", OP_REPLACE_BZ);
+ expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
+
+ GenVertex(&expected_graph[9],
+ VectOfExt(0, 9),
+ VectOfExt(60, 9),
+ "",
+ OP_MOVE);
+
+ GenVertex(&expected_graph[10],
+ VectOfExt(30, 10),
+ VectOfExt(60, 10),
+ "",
+ OP_MOVE);
+ expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
+
+ EXPECT_EQ(12, graph.size());
+ EXPECT_FALSE(graph.back().valid);
+ for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
+ EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
+ if (i == 8) {
+ // special case
+ } else {
+ // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
+ }
+ }
+}
+
+// Test that sparse holes are not used as scratch. More specifically, test that
+// if all full operations write to sparse holes and there's no extra scratch
+// space, delta operations that need scratch are converted to full. See
+// crbug.com/238440.
+TEST_F(DeltaDiffGeneratorTest, RunAsRootNoSparseAsTempTest) {
+ Graph graph(3);
+ const vector<Extent> kEmpty;
+ const string kFilename = "/foo";
+
+ // Make sure this sparse hole is not used as scratch.
+ GenVertex(&graph[0], kEmpty, VectOfExt(kSparseHole, 1), "", OP_REPLACE);
+
+ // Create a single-block cycle.
+ GenVertex(&graph[1], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_BSDIFF);
+ graph[1].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
+ GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(0, 1), kFilename, OP_BSDIFF);
+ graph[2].out_edges[1] = EdgeWithReadDep(VectOfExt(0, 1));
+
+ graph_utils::DumpGraph(graph);
+
+ vector<Vertex::Index> final_order;
+
+ // Prepare the filesystem with the minimum required for this to work.
+ string temp_dir;
+ EXPECT_TRUE(utils::MakeTempDirectory("NoSparseAsTempTest.XXXXXX",
+ &temp_dir));
+ ScopedDirRemover temp_dir_remover(temp_dir);
+
+ const size_t kBlockSize = 4096;
+ vector<char> temp_data(kBlockSize);
+ FillWithData(&temp_data);
+ EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
+ ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+ int fd = -1;
+ EXPECT_TRUE(utils::MakeTempFile("NoSparseAsTempTestData.XXXXXX",
+ NULL,
+ &fd));
+ ScopedFdCloser fd_closer(&fd);
+ off_t data_file_size = 0;
+
+ EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
+ temp_dir,
+ fd,
+ &data_file_size,
+ &final_order,
+ Vertex::kInvalidIndex));
+
+ ASSERT_EQ(4, graph.size());
+
+ // The second BSDIFF operation must have been converted to a full operation
+ // (due to insufficient scratch space).
+ EXPECT_TRUE(graph[2].op.type() == OP_REPLACE ||
+ graph[2].op.type() == OP_REPLACE_BZ);
+
+ // The temporary node created for breaking the cycle must have been marked as
+ // invalid.
+ EXPECT_FALSE(graph[3].valid);
+}
+
+// Test that sparse holes are not used as scratch. More specifically, test that
+// if scratch space comes only from full operations writing to real blocks as
+// well as sparse holes, only the real blocks are utilized. See
+// crbug.com/238440.
+TEST_F(DeltaDiffGeneratorTest, NoSparseAsTempTest) {
+ Graph graph;
+ vector<Block> blocks(4);
+
+ // Create nodes in |graph|.
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+
+ // Write to a sparse hole -- basically a no-op to ensure sparse holes are
+ // not used as scratch.
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ }
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_REPLACE);
+
+ // Scratch space: write to block 0 with sparse holes around.
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, 0);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[0].writer = graph.size() - 1;
+ }
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_REPLACE);
+
+ // Write to a sparse hole.
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ }
+ // Create a two-node cycle between (2, sparse, sparse) and (1, sparse, 3).
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_MOVE);
+ // Read from (2, sparse, sparse).
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, 2);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_src_extents());
+ blocks[2].reader = graph.size() - 1;
+
+ // Write to (1, sparse, 3).
+ extents.clear();
+ graph_utils::AppendBlockToExtents(&extents, 1);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, 3);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[1].writer = graph.size() - 1;
+ blocks[3].writer = graph.size() - 1;
+ }
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_MOVE);
+ // Read from (1, sparse, 3).
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, 1);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, 3);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_src_extents());
+ blocks[1].reader = graph.size() - 1;
+ blocks[3].reader = graph.size() - 1;
+
+ // Write to (2, sparse, sparse).
+ extents.clear();
+ graph_utils::AppendBlockToExtents(&extents, 2);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[2].writer = graph.size() - 1;
+ }
+
+ graph_utils::DumpGraph(graph);
+
+ // Create edges
+ DeltaDiffGenerator::CreateEdges(&graph, blocks);
+
+ graph_utils::DumpGraph(graph);
+
+ vector<Vertex::Index> final_order;
+ off_t data_file_size = 0;
+ EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
+ "/non/existent/dir",
+ -1,
+ &data_file_size,
+ &final_order,
+ Vertex::kInvalidIndex));
+
+ // Check for a single temporary node writing to scratch.
+ ASSERT_EQ(6, graph.size());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
+ graph[5].op.type());
+ EXPECT_EQ(1, graph[5].op.src_extents_size());
+ ASSERT_EQ(1, graph[5].op.dst_extents_size());
+ EXPECT_EQ(0, graph[5].op.dst_extents(0).start_block());
+ EXPECT_EQ(1, graph[5].op.dst_extents(0).num_blocks());
+
+ // Make sure the cycle nodes still read from and write to sparse holes.
+ for (int i = 3; i < 5; i++) {
+ ASSERT_GE(graph[i].op.src_extents_size(), 2);
+ EXPECT_EQ(kSparseHole, graph[i].op.src_extents(1).start_block());
+ ASSERT_GE(graph[i].op.dst_extents_size(), 2);
+ EXPECT_EQ(kSparseHole, graph[i].op.dst_extents(1).start_block());
+ }
+}
+
+TEST_F(DeltaDiffGeneratorTest, IsNoopOperationTest) {
+ DeltaArchiveManifest_InstallOperation op;
+ op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
+ op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
+ *(op.add_src_extents()) = ExtentForRange(3, 2);
+ *(op.add_dst_extents()) = ExtentForRange(3, 2);
+ EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
+ *(op.add_src_extents()) = ExtentForRange(7, 5);
+ *(op.add_dst_extents()) = ExtentForRange(7, 5);
+ EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
+ *(op.add_src_extents()) = ExtentForRange(20, 2);
+ *(op.add_dst_extents()) = ExtentForRange(20, 1);
+ *(op.add_dst_extents()) = ExtentForRange(21, 1);
+ EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
+ *(op.add_src_extents()) = ExtentForRange(kSparseHole, 2);
+ *(op.add_src_extents()) = ExtentForRange(kSparseHole, 1);
+ *(op.add_dst_extents()) = ExtentForRange(kSparseHole, 3);
+ EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
+ *(op.add_src_extents()) = ExtentForRange(24, 1);
+ *(op.add_dst_extents()) = ExtentForRange(25, 1);
+ EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
+}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootAssignTempBlocksReuseTest) {
+ // AssignTempBlocks(Graph* graph,
+ // const string& new_root,
+ // int data_fd,
+ // off_t* data_file_size,
+ // vector<Vertex::Index>* op_indexes,
+ // vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+ // const vector<CutEdgeVertexes>& cuts
+ Graph graph(9);
+
+ const vector<Extent> empt;
+ uint64_t tmp = kTempBlockStart;
+ const string kFilename = "/foo";
+
+ vector<CutEdgeVertexes> cuts;
+ cuts.resize(3);
+
+ // Simple broken loop:
+ GenVertex(&graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_MOVE);
+ GenVertex(&graph[1], VectOfExt(tmp, 1), VectOfExt(0, 1), "", OP_MOVE);
+ GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(tmp, 1), "", OP_MOVE);
+ // Corresponding edges:
+ graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
+ graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
+ graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
+ // Store the cut:
+ cuts[0].old_dst = 1;
+ cuts[0].old_src = 0;
+ cuts[0].new_vertex = 2;
+ cuts[0].tmp_extents = VectOfExt(tmp, 1);
+ tmp++;
+
+ // Slightly more complex pair of loops:
+ GenVertex(&graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", OP_MOVE);
+ GenVertex(&graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", OP_MOVE);
+ GenVertex(&graph[5], VectOfExt(tmp, 3), VectOfExt(4, 3), kFilename, OP_MOVE);
+ GenVertex(&graph[6], VectOfExt(2, 2), VectOfExt(tmp, 2), "", OP_MOVE);
+ GenVertex(&graph[7], VectOfExt(7, 1), VectOfExt(tmp + 2, 1), "", OP_MOVE);
+ // Corresponding edges:
+ graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
+ graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
+ graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
+ graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
+ graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
+ graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
+ // Store the cuts:
+ cuts[1].old_dst = 5;
+ cuts[1].old_src = 3;
+ cuts[1].new_vertex = 6;
+ cuts[1].tmp_extents = VectOfExt(tmp, 2);
+ cuts[2].old_dst = 5;
+ cuts[2].old_src = 4;
+ cuts[2].new_vertex = 7;
+ cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
+
+ // Supplier of temp block:
+ GenVertex(&graph[8], empt, VectOfExt(8, 1), "", OP_REPLACE);
+
+ // Specify the final order:
+ vector<Vertex::Index> op_indexes;
+ op_indexes.push_back(2);
+ op_indexes.push_back(0);
+ op_indexes.push_back(1);
+ op_indexes.push_back(6);
+ op_indexes.push_back(3);
+ op_indexes.push_back(7);
+ op_indexes.push_back(4);
+ op_indexes.push_back(5);
+ op_indexes.push_back(8);
+
+ vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
+ DeltaDiffGenerator::GenerateReverseTopoOrderMap(op_indexes,
+ &reverse_op_indexes);
+
+ // Prepare the filesystem with the minimum required for this to work
+ string temp_dir;
+ EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksReuseTest.XXXXXX",
+ &temp_dir));
+ ScopedDirRemover temp_dir_remover(temp_dir);
+
+ const size_t kBlockSize = 4096;
+ vector<char> temp_data(kBlockSize * 3);
+ FillWithData(&temp_data);
+ EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
+ ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+ int fd;
+ EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksReuseTest.XXXXXX",
+ NULL,
+ &fd));
+ ScopedFdCloser fd_closer(&fd);
+ off_t data_file_size = 0;
+
+ EXPECT_TRUE(DeltaDiffGenerator::AssignTempBlocks(&graph,
+ temp_dir,
+ fd,
+ &data_file_size,
+ &op_indexes,
+ &reverse_op_indexes,
+ cuts));
+ EXPECT_FALSE(graph[6].valid);
+ EXPECT_FALSE(graph[7].valid);
+ EXPECT_EQ(1, graph[1].op.src_extents_size());
+ EXPECT_EQ(2, graph[1].op.src_extents(0).start_block());
+ EXPECT_EQ(1, graph[1].op.src_extents(0).num_blocks());
+ 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
diff --git a/payload_generator/extent_mapper.cc b/payload_generator/extent_mapper.cc
new file mode 100644
index 0000000..9e66619
--- /dev/null
+++ b/payload_generator/extent_mapper.cc
@@ -0,0 +1,93 @@
+// 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/payload_generator/extent_mapper.h"
+
+#include <assert.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <linux/fs.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/ioctl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace extent_mapper {
+
+namespace {
+const int kBlockSize = 4096;
+}
+
+bool ExtentsForFileChunkFibmap(const std::string& path,
+ off_t chunk_offset,
+ off_t chunk_size,
+ std::vector<Extent>* out) {
+ CHECK(out);
+ CHECK_EQ(0, chunk_offset % kBlockSize);
+ CHECK(chunk_size == -1 || chunk_size >= 0);
+ struct stat stbuf;
+ int rc = stat(path.c_str(), &stbuf);
+ TEST_AND_RETURN_FALSE_ERRNO(rc == 0);
+ TEST_AND_RETURN_FALSE(S_ISREG(stbuf.st_mode));
+
+ int fd = open(path.c_str(), O_RDONLY, 0);
+ TEST_AND_RETURN_FALSE_ERRNO(fd >= 0);
+ ScopedFdCloser fd_closer(&fd);
+
+ // Get file size in blocks
+ rc = fstat(fd, &stbuf);
+ if (rc < 0) {
+ perror("fstat");
+ return false;
+ }
+ CHECK_LE(chunk_offset, stbuf.st_size);
+ off_t size = stbuf.st_size - chunk_offset;
+ if (chunk_size != -1) {
+ size = std::min(size, chunk_size);
+ }
+ const int block_count = (size + kBlockSize - 1) / kBlockSize;
+ const int start_block = chunk_offset / kBlockSize;
+ Extent current;
+ current.set_start_block(0);
+ current.set_num_blocks(0);
+
+ for (int i = start_block; i < start_block + block_count; i++) {
+ unsigned int block32 = i;
+ rc = ioctl(fd, FIBMAP, &block32);
+ TEST_AND_RETURN_FALSE_ERRNO(rc == 0);
+
+ const uint64_t block = (block32 == 0 ? kSparseHole : block32);
+
+ graph_utils::AppendBlockToExtents(out, block);
+ }
+ return true;
+}
+
+bool ExtentsForFileFibmap(const std::string& path, std::vector<Extent>* out) {
+ return ExtentsForFileChunkFibmap(path, 0, -1, out);
+}
+
+bool GetFilesystemBlockSize(const std::string& path, uint32_t* out_blocksize) {
+ int fd = open(path.c_str(), O_RDONLY, 0);
+ TEST_AND_RETURN_FALSE_ERRNO(fd >= 0);
+ ScopedFdCloser fd_closer(&fd);
+ int rc = ioctl(fd, FIGETBSZ, out_blocksize);
+ TEST_AND_RETURN_FALSE_ERRNO(rc != -1);
+ return true;
+}
+
+} // namespace extent_mapper
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/extent_mapper.h b/payload_generator/extent_mapper.h
new file mode 100644
index 0000000..bc46e47
--- /dev/null
+++ b/payload_generator/extent_mapper.h
@@ -0,0 +1,46 @@
+// 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_PAYLOAD_GENERATOR_EXTENT_MAPPER_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_MAPPER_H_
+
+#include <string>
+#include <vector>
+
+#include <base/basictypes.h>
+
+#include "update_engine/update_metadata.pb.h"
+
+namespace chromeos_update_engine {
+
+namespace extent_mapper {
+
+// Uses the FIBMAP ioctl to get all blocks used by a file and return them
+// as extents. Blocks are relative to the start of the filesystem. If
+// there is a sparse "hole" in the file, the blocks for that will be
+// represented by an extent whose start block is kSpareseHole.
+// The resulting extents are stored in 'out'. Keep in mind that while
+// the blocksize of a filesystem is often 4096 bytes, that is not always
+// the case, so one should consult GetFilesystemBlockSize(), too.
+// Returns true on success.
+//
+// ExtentsForFileChunkFibmap gets the blocks starting from
+// |chunk_offset|. |chunk_offset| must be a multiple of the block size. If
+// |chunk_size| is not -1, only blocks covering up to |chunk_size| bytes are
+// returned.
+bool ExtentsForFileFibmap(const std::string& path, std::vector<Extent>* out);
+bool ExtentsForFileChunkFibmap(const std::string& path,
+ off_t chunk_offset,
+ off_t chunk_size,
+ std::vector<Extent>* out);
+
+// Puts the blocksize of the filesystem, as used by the FIBMAP ioctl, into
+// out_blocksize by using the FIGETBSZ ioctl. Returns true on success.
+bool GetFilesystemBlockSize(const std::string& path, uint32_t* out_blocksize);
+
+} // namespace extent_mapper
+
+} // namespace chromeos_update_engine
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_MAPPER_H_
diff --git a/payload_generator/extent_mapper_unittest.cc b/payload_generator/extent_mapper_unittest.cc
new file mode 100644
index 0000000..3b23246
--- /dev/null
+++ b/payload_generator/extent_mapper_unittest.cc
@@ -0,0 +1,111 @@
+// 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/payload_generator/extent_mapper.h"
+
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include <base/basictypes.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/utils.h"
+
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class ExtentMapperTest : public ::testing::Test {};
+
+TEST(ExtentMapperTest, RunAsRootSimpleTest) {
+ // It's hard to have a concrete test for extent mapping without including
+ // a specific filesystem image.
+ // In lieu of this, we do a weak test: make sure the extents of the unittest
+ // executable are consistent and they match with the size of the file.
+ const string kFilename = "/proc/self/exe";
+
+ uint32_t block_size = 0;
+ EXPECT_TRUE(extent_mapper::GetFilesystemBlockSize(kFilename, &block_size));
+ EXPECT_GT(block_size, 0);
+
+ vector<Extent> extents;
+
+ ASSERT_TRUE(extent_mapper::ExtentsForFileFibmap(kFilename, &extents));
+
+ EXPECT_FALSE(extents.empty());
+ set<uint64_t> blocks;
+
+ for (vector<Extent>::const_iterator it = extents.begin();
+ it != extents.end(); ++it) {
+ for (uint64_t block = it->start_block();
+ block < it->start_block() + it->num_blocks();
+ block++) {
+ EXPECT_FALSE(utils::SetContainsKey(blocks, block));
+ blocks.insert(block);
+ }
+ }
+
+ struct stat stbuf;
+ EXPECT_EQ(0, stat(kFilename.c_str(), &stbuf));
+ EXPECT_EQ(blocks.size(), (stbuf.st_size + block_size - 1)/block_size);
+
+ // Map a 2-block chunk at offset |block_size|.
+ vector<Extent> chunk_extents;
+ ASSERT_TRUE(
+ extent_mapper::ExtentsForFileChunkFibmap(kFilename,
+ block_size,
+ block_size + 1,
+ &chunk_extents));
+ EXPECT_FALSE(chunk_extents.empty());
+ int chunk_blocks = 0;
+ for (vector<Extent>::const_iterator it = chunk_extents.begin();
+ it != chunk_extents.end(); ++it) {
+ chunk_blocks += it->num_blocks();
+ }
+ EXPECT_EQ(2, chunk_blocks);
+}
+
+TEST(ExtentMapperTest, RunAsRootSparseFileTest) {
+ // Create sparse file with one real block, then two sparse ones, then a real
+ // block at the end.
+ const char tmp_name_template[] =
+ "/tmp/ExtentMapperTest.RunAsRootSparseFileTest.XXXXXX";
+ char buf[sizeof(tmp_name_template)];
+ strncpy(buf, tmp_name_template, sizeof(buf));
+ COMPILE_ASSERT(sizeof(buf) > 8, buf_size_incorrect);
+ ASSERT_EQ('\0', buf[sizeof(buf) - 1]);
+
+ int fd = mkstemp(buf);
+ ASSERT_GE(fd, 0);
+
+ uint32_t block_size = 0;
+ EXPECT_TRUE(extent_mapper::GetFilesystemBlockSize(buf, &block_size));
+ EXPECT_GT(block_size, 0);
+
+ EXPECT_EQ(1, pwrite(fd, "x", 1, 0));
+ EXPECT_EQ(1, pwrite(fd, "x", 1, 3 * block_size));
+ close(fd);
+
+ vector<Extent> extents;
+ EXPECT_TRUE(extent_mapper::ExtentsForFileFibmap(buf, &extents));
+ unlink(buf);
+ EXPECT_EQ(3, extents.size());
+ EXPECT_EQ(1, extents[0].num_blocks());
+ EXPECT_EQ(2, extents[1].num_blocks());
+ EXPECT_EQ(1, extents[2].num_blocks());
+ EXPECT_NE(kSparseHole, extents[0].start_block());
+ EXPECT_EQ(kSparseHole, extents[1].start_block());
+ EXPECT_NE(kSparseHole, extents[2].start_block());
+ EXPECT_NE(extents[2].start_block(), extents[0].start_block());
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/filesystem_iterator.cc b/payload_generator/filesystem_iterator.cc
new file mode 100644
index 0000000..b7455fa
--- /dev/null
+++ b/payload_generator/filesystem_iterator.cc
@@ -0,0 +1,151 @@
+// Copyright (c) 2009 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/payload_generator/filesystem_iterator.h"
+
+#include <dirent.h>
+#include <errno.h>
+#include <sys/types.h>
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include <base/logging.h>
+
+#include "update_engine/utils.h"
+
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+// We use a macro here for two reasons:
+// 1. We want to be able to return from the caller's function.
+// 2. We can use the #macro_arg ism to get a string of the calling statement,
+// which we can log.
+
+#define RETURN_ERROR_IF_FALSE(_statement) \
+ do { \
+ bool _result = (_statement); \
+ if (!_result) { \
+ string _message = utils::ErrnoNumberAsString(errno); \
+ LOG(INFO) << #_statement << " failed: " << _message << ". Aborting"; \
+ is_end_ = true; \
+ is_err_ = true; \
+ return; \
+ } \
+ } while (0)
+
+FilesystemIterator::FilesystemIterator(
+ const std::string& path,
+ const std::set<std::string>& excl_prefixes)
+ : excl_prefixes_(excl_prefixes),
+ is_end_(false),
+ is_err_(false) {
+ root_path_ = utils::NormalizePath(path, true);
+ RETURN_ERROR_IF_FALSE(lstat(root_path_.c_str(), &stbuf_) == 0);
+ root_dev_ = stbuf_.st_dev;
+}
+
+FilesystemIterator::~FilesystemIterator() {
+ for (vector<DIR*>::iterator it = dirs_.begin(); it != dirs_.end(); ++it) {
+ LOG_IF(ERROR, closedir(*it) != 0) << "closedir failed";
+ }
+}
+
+// Returns full path for current file
+std::string FilesystemIterator::GetFullPath() const {
+ return root_path_ + GetPartialPath();
+}
+
+std::string FilesystemIterator::GetPartialPath() const {
+ std::string ret;
+ for (vector<string>::const_iterator it = names_.begin();
+ it != names_.end(); ++it) {
+ ret += "/";
+ ret += *it;
+ }
+ return ret;
+}
+
+// Increments to the next file
+void FilesystemIterator::Increment() {
+ // If we're currently on a dir, descend into children, but only if
+ // we're on the same device as the root device
+
+ bool entering_dir = false; // true if we're entering into a new dir
+ if (S_ISDIR(stbuf_.st_mode) && (stbuf_.st_dev == root_dev_)) {
+ DIR* dir = opendir(GetFullPath().c_str());
+ if ((!dir) && ((errno == ENOTDIR) || (errno == ENOENT))) {
+ // opendir failed b/c either it's not a dir or it doesn't exist.
+ // that's fine. let's just skip over this.
+ LOG(ERROR) << "Can't descend into " << GetFullPath();
+ } else {
+ RETURN_ERROR_IF_FALSE(dir);
+ entering_dir = true;
+ dirs_.push_back(dir);
+ }
+ }
+
+ if (!entering_dir && names_.empty()) {
+ // root disappeared while we tried to descend into it
+ is_end_ = true;
+ return;
+ }
+
+ if (!entering_dir)
+ names_.pop_back();
+
+ IncrementInternal();
+ for (set<string>::const_iterator it = excl_prefixes_.begin();
+ it != excl_prefixes_.end(); ++it) {
+ if (utils::StringHasPrefix(GetPartialPath(), *it)) {
+ Increment();
+ break;
+ }
+ }
+ return;
+}
+
+// Assumes that we need to find the next child of dirs_.back(), or if
+// there are none more, go up the chain
+void FilesystemIterator::IncrementInternal() {
+ CHECK_EQ(dirs_.size(), names_.size() + 1);
+ for (;;) {
+ struct dirent dir_entry;
+ struct dirent* dir_entry_pointer;
+ int r;
+ RETURN_ERROR_IF_FALSE(
+ (r = readdir_r(dirs_.back(), &dir_entry, &dir_entry_pointer)) == 0);
+ if (dir_entry_pointer) {
+ // Found an entry
+ names_.push_back(dir_entry_pointer->d_name);
+ // Validate
+ RETURN_ERROR_IF_FALSE(lstat(GetFullPath().c_str(), &stbuf_) == 0);
+ if (strcmp(dir_entry_pointer->d_name, ".") &&
+ strcmp(dir_entry_pointer->d_name, "..")) {
+ // Done
+ return;
+ }
+ // Child didn't work out. Try again
+ names_.pop_back();
+ } else {
+ // No more children in this dir. Pop it and try again
+ RETURN_ERROR_IF_FALSE(closedir(dirs_.back()) == 0);
+ dirs_.pop_back();
+ if (dirs_.empty()) {
+ CHECK(names_.empty());
+ // Done with the entire iteration
+ is_end_ = true;
+ return;
+ }
+ CHECK(!names_.empty());
+ names_.pop_back();
+ }
+ }
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/filesystem_iterator.h b/payload_generator/filesystem_iterator.h
new file mode 100644
index 0000000..859965d
--- /dev/null
+++ b/payload_generator/filesystem_iterator.h
@@ -0,0 +1,127 @@
+// Copyright (c) 2009 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_PAYLOAD_GENERATOR_FILESYSTEM_ITERATOR_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FILESYSTEM_ITERATOR_H_
+
+// This class is used to walk a filesystem. It will iterate over every file
+// on the same device as the file passed in the ctor. Directories will be
+// visited before their children. Children will be visited in no particular
+// order.
+
+// The iterator is a forward iterator. It's not random access nor can it be
+// decremented.
+
+// Note: If the iterator comes across a mount point where another filesystem
+// is mounted, that mount point will be present, but none of its children
+// will be. Technically the mount point is on the other filesystem (and
+// the Stat() call will verify that), but we return it anyway since:
+// 1. Such a folder must exist in the first filesystem if it got used
+// as a mount point.
+// 2. You probably want to copy if it you're using the iterator to do a
+// filesystem copy
+// 3. If you don't want that, you can just check Stat().st_dev and skip
+// foreign filesystems manually.
+
+#include <dirent.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <set>
+#include <string>
+#include <vector>
+
+namespace chromeos_update_engine {
+
+class FilesystemIterator {
+ public:
+ FilesystemIterator(const std::string& path,
+ const std::set<std::string>& excl_prefixes);
+
+ ~FilesystemIterator();
+
+ // Returns stat struct for the current file.
+ struct stat GetStat() const {
+ return stbuf_;
+ }
+
+ // Returns full path for current file.
+ std::string GetFullPath() const;
+
+ // Returns the path that's part of the iterator. For example, if
+ // the object were constructed by passing in "/foo/bar" and Path()
+ // returns "/foo/bar/baz/bat.txt", IterPath would return
+ // "/baz/bat.txt". When this object is on root (ie, the very first
+ // path), IterPath will return "", otherwise the first character of
+ // IterPath will be "/".
+ std::string GetPartialPath() const;
+
+ // Returns name for current file.
+ std::string GetBasename() const {
+ return names_.back();
+ }
+
+ // Increments to the next file.
+ void Increment();
+
+ // If we're at the end. If at the end, do not call Stat(), Path(), etc.,
+ // since this iterator currently isn't pointing to any file at all.
+ bool IsEnd() const {
+ return is_end_;
+ }
+
+ // Returns true if the iterator is in an error state.
+ bool IsErr() const {
+ return is_err_;
+ }
+ private:
+ // Helper for Increment.
+ void IncrementInternal();
+
+ // Returns true if path exists and it's a directory.
+ bool DirectoryExists(const std::string& path);
+
+ // In general (i.e., not midway through a call to Increment()), there is a
+ // relationship between dirs_ and names_: dirs[i] == names_[i - 1].
+ // For example, say we are asked to iterate "/usr/local" and we're currently
+ // at /usr/local/share/dict/words. dirs_ contains DIR* variables for the
+ // dirs at: {"/usr/local", ".../share", ".../dict"} and names_ contains:
+ // {"share", "dict", "words"}. root_path_ contains "/usr/local".
+ // root_dev_ would be the dev for root_path_
+ // (and /usr/local/share/dict/words). stbuf_ would be the stbuf for
+ // /usr/local/share/dict/words.
+
+ // All opened directories. If this is empty, we're currently on the root,
+ // but not descended into the root.
+ // This will always contain the current directory and all it's ancestors
+ // in root-to-leaf order. For more details, see comment above.
+ std::vector<DIR*> dirs_;
+
+ // The list of all filenames for the current path that we've descended into.
+ std::vector<std::string> names_;
+
+ // The device of the root path we've been asked to iterate.
+ dev_t root_dev_;
+
+ // The root path we've been asked to iteratate.
+ std::string root_path_;
+
+ // Exclude items w/ this prefix.
+ std::set<std::string> excl_prefixes_;
+
+ // The struct stat of the current file we're at.
+ struct stat stbuf_;
+
+ // Generally false; set to true when we reach the end of files to iterate
+ // or error occurs.
+ bool is_end_;
+
+ // Generally false; set to true if an error occurrs.
+ bool is_err_;
+};
+
+} // namespace chromeos_update_engine
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FILESYSTEM_ITERATOR_H_
diff --git a/payload_generator/filesystem_iterator_unittest.cc b/payload_generator/filesystem_iterator_unittest.cc
new file mode 100644
index 0000000..67ac177
--- /dev/null
+++ b/payload_generator/filesystem_iterator_unittest.cc
@@ -0,0 +1,146 @@
+// Copyright (c) 2012 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/payload_generator/filesystem_iterator.h"
+
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class FilesystemIteratorTest : public ::testing::Test {
+ protected:
+ virtual void SetUp() {
+ ASSERT_TRUE(utils::MakeTempDirectory("FilesystemIteratorTest-XXXXXX",
+ &test_dir_));
+ LOG(INFO) << "SetUp() mkdir " << test_dir_;
+ }
+
+ virtual void TearDown() {
+ LOG(INFO) << "TearDown() rmdir " << test_dir_;
+ EXPECT_EQ(0, System(base::StringPrintf("rm -rf %s", TestDir())));
+ }
+
+ const char* TestDir() {
+ return test_dir_.c_str();
+ }
+
+ private:
+ string test_dir_;
+};
+
+TEST_F(FilesystemIteratorTest, RunAsRootSuccessTest) {
+ ASSERT_EQ(0, getuid());
+
+ // Create uniquely named main/sub images.
+ string main_image;
+ ASSERT_TRUE(utils::MakeTempFile("FilesystemIteratorTest.image1-XXXXXX",
+ &main_image, NULL));
+ ScopedPathUnlinker main_image_unlinker(main_image);
+
+ string sub_image;
+ ASSERT_TRUE(utils::MakeTempFile("FilesystemIteratorTest.image2-XXXXXX",
+ &sub_image, NULL));
+ ScopedPathUnlinker sub_image_unlinker(sub_image);
+
+ // Create uniqely named main/sub mount points.
+ string main_image_mount_point;
+ ASSERT_TRUE(utils::MakeTempDirectory(
+ "FilesystemIteratorTest.mount-XXXXXX",
+ &main_image_mount_point));
+ ScopedPathUnlinker main_image_mount_point_unlinker(main_image_mount_point);
+ const string sub_image_mount_point = main_image_mount_point + "/some_dir/mnt";
+
+ vector<string> expected_paths_vector;
+ CreateExtImageAtPath(main_image, &expected_paths_vector);
+ CreateExtImageAtPath(sub_image, NULL);
+ ASSERT_EQ(0, System(string("mount -o loop ") + main_image + " " +
+ main_image_mount_point));
+ ASSERT_EQ(0, System(string("mount -o loop ") + sub_image + " " +
+ sub_image_mount_point));
+ for (vector<string>::iterator it = expected_paths_vector.begin();
+ it != expected_paths_vector.end(); ++it)
+ *it = main_image_mount_point + *it;
+ set<string> expected_paths(expected_paths_vector.begin(),
+ expected_paths_vector.end());
+ VerifyAllPaths(main_image_mount_point, expected_paths);
+
+ EXPECT_TRUE(utils::UnmountFilesystem(sub_image_mount_point));
+ EXPECT_TRUE(utils::UnmountFilesystem(main_image_mount_point));
+}
+
+TEST_F(FilesystemIteratorTest, NegativeTest) {
+ {
+ FilesystemIterator iter("/non/existent/path", set<string>());
+ EXPECT_TRUE(iter.IsEnd());
+ EXPECT_TRUE(iter.IsErr());
+ }
+
+ {
+ FilesystemIterator iter(TestDir(), set<string>());
+ EXPECT_FALSE(iter.IsEnd());
+ EXPECT_FALSE(iter.IsErr());
+ // Here I'm deleting the exact directory that iterator is point at,
+ // then incrementing (which normally would descend into that directory).
+ EXPECT_EQ(0, rmdir(TestDir()));
+ iter.Increment();
+ EXPECT_TRUE(iter.IsEnd());
+ EXPECT_FALSE(iter.IsErr());
+ }
+}
+
+TEST_F(FilesystemIteratorTest, DeleteWhileTraverseTest) {
+ const string dir_name = TestDir();
+ ASSERT_EQ(0, chmod(dir_name.c_str(), 0755));
+ const string sub_dir_name(dir_name + "/a");
+ ASSERT_EQ(0, mkdir(sub_dir_name.c_str(), 0755));
+ const string sub_sub_dir_name(sub_dir_name + "/b");
+ ASSERT_EQ(0, mkdir(sub_sub_dir_name.c_str(), 0755));
+ ASSERT_EQ(0, mkdir((dir_name + "/b").c_str(), 0755));
+ ASSERT_EQ(0, mkdir((dir_name + "/c").c_str(), 0755));
+
+ string expected_paths_arr[] = {
+ "",
+ "/a",
+ "/b",
+ "/c"
+ };
+ set<string> expected_paths(expected_paths_arr,
+ expected_paths_arr +
+ arraysize(expected_paths_arr));
+
+ FilesystemIterator iter(dir_name, set<string>());
+ while (!iter.IsEnd()) {
+ string path = iter.GetPartialPath();
+ EXPECT_TRUE(expected_paths.find(path) != expected_paths.end());
+ if (expected_paths.find(path) != expected_paths.end()) {
+ expected_paths.erase(path);
+ }
+ if (path == "/a") {
+ EXPECT_EQ(0, rmdir(sub_sub_dir_name.c_str()));
+ EXPECT_EQ(0, rmdir(sub_dir_name.c_str()));
+ }
+ iter.Increment();
+ }
+ EXPECT_FALSE(iter.IsErr());
+ EXPECT_TRUE(expected_paths.empty());
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/full_update_generator.cc b/payload_generator/full_update_generator.cc
new file mode 100644
index 0000000..3a17594
--- /dev/null
+++ b/payload_generator/full_update_generator.cc
@@ -0,0 +1,203 @@
+// Copyright (c) 2012 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/payload_generator/full_update_generator.h"
+
+#include <fcntl.h>
+#include <inttypes.h>
+
+#include <tr1/memory>
+
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/utils.h"
+
+using std::deque;
+using std::max;
+using std::min;
+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() {
+ // g_thread_create is deprecated since glib 2.32. Use
+ // g_thread_new instead.
+ thread_ = g_thread_try_new("chunk_proc", ReadAndCompressThread, this, 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;
+ int last_progress_update = INT_MIN;
+ 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 =
+ base::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);
+
+ int progress = static_cast<int>(
+ (processor->offset() + processor->buffer_in().size()) * 100.0 /
+ part_sizes[partition]);
+ if (last_progress_update < progress &&
+ (last_progress_update + 10 <= progress || progress == 100)) {
+ LOG(INFO) << progress << "% complete (output size: "
+ << *data_file_size << ")";
+ last_progress_update = progress;
+ }
+ }
+ }
+
+ return true;
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/full_update_generator.h b/payload_generator/full_update_generator.h
new file mode 100644
index 0000000..4ca1aa4
--- /dev/null
+++ b/payload_generator/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_PAYLOAD_GENERATOR_FULL_UPDATE_GENERATOR_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FULL_UPDATE_GENERATOR_H_
+
+#include <glib.h>
+
+#include "update_engine/payload_generator/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_PAYLOAD_GENERATOR_FULL_UPDATE_GENERATOR_H_
diff --git a/payload_generator/full_update_generator_unittest.cc b/payload_generator/full_update_generator_unittest.cc
new file mode 100644
index 0000000..c3da115
--- /dev/null
+++ b/payload_generator/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/payload_generator/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("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("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("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
diff --git a/payload_generator/generate_delta_main.cc b/payload_generator/generate_delta_main.cc
new file mode 100644
index 0000000..9dd6175
--- /dev/null
+++ b/payload_generator/generate_delta_main.cc
@@ -0,0 +1,397 @@
+// 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 <errno.h>
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include <base/command_line.h>
+#include <base/logging.h>
+#include <base/strings/string_number_conversions.h>
+#include <base/strings/string_split.h>
+#include <gflags/gflags.h>
+#include <glib.h>
+
+#include "update_engine/delta_performer.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_signer.h"
+#include "update_engine/prefs.h"
+#include "update_engine/subprocess.h"
+#include "update_engine/terminator.h"
+#include "update_engine/update_metadata.pb.h"
+#include "update_engine/utils.h"
+
+DEFINE_string(old_dir, "",
+ "Directory where the old rootfs is loop mounted read-only");
+DEFINE_string(new_dir, "",
+ "Directory where the new rootfs is loop mounted read-only");
+DEFINE_string(old_image, "", "Path to the old rootfs");
+DEFINE_string(new_image, "", "Path to the new rootfs");
+DEFINE_string(old_kernel, "", "Path to the old kernel partition image");
+DEFINE_string(new_kernel, "", "Path to the new kernel partition image");
+DEFINE_string(in_file, "",
+ "Path to input delta payload file used to hash/sign payloads "
+ "and apply delta over old_image (for debugging)");
+DEFINE_string(out_file, "", "Path to output delta payload file");
+DEFINE_string(out_hash_file, "", "Path to output hash file");
+DEFINE_string(out_metadata_hash_file, "", "Path to output metadata hash file");
+DEFINE_string(private_key, "", "Path to private key in .pem format");
+DEFINE_string(public_key, "", "Path to public key in .pem format");
+DEFINE_int32(public_key_version,
+ chromeos_update_engine::kSignatureMessageCurrentVersion,
+ "Key-check version # of client");
+DEFINE_string(prefs_dir, "/tmp/update_engine_prefs",
+ "Preferences directory, used with apply_delta");
+DEFINE_string(signature_size, "",
+ "Raw signature size used for hash calculation. "
+ "You may pass in multiple sizes by colon separating them. E.g. "
+ "2048:2048:4096 will assume 3 signatures, the first two with "
+ "2048 size and the last 4096.");
+DEFINE_string(signature_file, "",
+ "Raw signature file to sign payload with. To pass multiple "
+ "signatures, use a single argument with a colon between paths, "
+ "e.g. /path/to/sig:/path/to/next:/path/to/last_sig . Each "
+ "signature will be assigned a client version, starting from "
+ "kSignatureOriginalVersion.");
+DEFINE_int32(chunk_size, -1, "Payload chunk size (-1 -- no limit/default)");
+DEFINE_int64(rootfs_partition_size,
+ chromeos_update_engine::kRootFSPartitionSize,
+ "RootFS partition size for the image once installed");
+
+DEFINE_string(old_channel, "",
+ "The channel for the old image. 'dev-channel', 'npo-channel', "
+ "etc. Ignored, except during delta generation.");
+DEFINE_string(old_board, "",
+ "The board for the old image. 'x86-mario', 'lumpy', "
+ "etc. Ignored, except during delta generation.");
+DEFINE_string(old_version, "",
+ "The build version of the old image. 1.2.3, etc.");
+DEFINE_string(old_key, "",
+ "The key used to sign the old image. 'premp', 'mp', 'mp-v3',"
+ " etc");
+DEFINE_string(old_build_channel, "",
+ "The channel for the build of the old image. 'dev-channel', "
+ "etc, but will never contain special channels such as "
+ "'npo-channel'. Ignored, except during delta generation.");
+DEFINE_string(old_build_version, "",
+ "The version of the build containing the old image.");
+
+DEFINE_string(new_channel, "",
+ "The channel for the new image. 'dev-channel', 'npo-channel', "
+ "etc. Ignored, except during delta generation.");
+DEFINE_string(new_board, "",
+ "The board for the new image. 'x86-mario', 'lumpy', "
+ "etc. Ignored, except during delta generation.");
+DEFINE_string(new_version, "",
+ "The build version of the new image. 1.2.3, etc.");
+DEFINE_string(new_key, "",
+ "The key used to sign the new image. 'premp', 'mp', 'mp-v3',"
+ " etc");
+DEFINE_string(new_build_channel, "",
+ "The channel for the build of the new image. 'dev-channel', "
+ "etc, but will never contain special channels such as "
+ "'npo-channel'. Ignored, except during delta generation.");
+DEFINE_string(new_build_version, "",
+ "The version of the build containing the new image.");
+
+// This file contains a simple program that takes an old path, a new path,
+// and an output file as arguments and the path to an output file and
+// generates a delta that can be sent to Chrome OS clients.
+
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+bool IsDir(const char* path) {
+ struct stat stbuf;
+ TEST_AND_RETURN_FALSE_ERRNO(lstat(path, &stbuf) == 0);
+ return S_ISDIR(stbuf.st_mode);
+}
+
+void ParseSignatureSizes(const string& signature_sizes_flag,
+ vector<int>* signature_sizes) {
+ signature_sizes->clear();
+ vector<string> split_strings;
+
+ base::SplitString(signature_sizes_flag, ':', &split_strings);
+ for (vector<string>::iterator i = split_strings.begin();
+ i < split_strings.end();
+ i++) {
+ int size = 0;
+ bool parsing_successful = base::StringToInt(*i, &size);
+ LOG_IF(FATAL, !parsing_successful)
+ << "Invalid signature size: " << *i;
+
+ LOG_IF(FATAL, size != (2048 / 8)) <<
+ "Only signature sizes of 256 bytes are supported.";
+
+ signature_sizes->push_back(size);
+ }
+}
+
+
+bool ParseImageInfo(const string& channel,
+ const string& board,
+ const string& version,
+ const string& key,
+ const string& build_channel,
+ const string& build_version,
+ ImageInfo* image_info) {
+
+ // All of these arguments should be present or missing.
+ bool empty = channel.empty();
+
+ CHECK_EQ(channel.empty(), empty);
+ CHECK_EQ(board.empty(), empty);
+ CHECK_EQ(version.empty(), empty);
+ CHECK_EQ(key.empty(), empty);
+
+ if (empty)
+ return false;
+
+ image_info->set_channel(channel);
+ image_info->set_board(board);
+ image_info->set_version(version);
+ image_info->set_key(key);
+
+ image_info->set_build_channel(
+ build_channel.empty() ? channel : build_channel);
+
+ image_info->set_build_version(
+ build_version.empty() ? version : build_version);
+
+ return true;
+}
+
+void CalculatePayloadHashForSigning(const vector<int> &sizes,
+ const string& out_hash_file) {
+ LOG(INFO) << "Calculating payload hash for signing.";
+ LOG_IF(FATAL, FLAGS_in_file.empty())
+ << "Must pass --in_file to calculate hash for signing.";
+ LOG_IF(FATAL, out_hash_file.empty())
+ << "Must pass --out_hash_file to calculate hash for signing.";
+
+ vector<char> hash;
+ bool result = PayloadSigner::HashPayloadForSigning(FLAGS_in_file, sizes,
+ &hash);
+ CHECK(result);
+
+ result = utils::WriteFile(out_hash_file.c_str(), hash.data(), hash.size());
+ CHECK(result);
+ LOG(INFO) << "Done calculating payload hash for signing.";
+}
+
+
+void CalculateMetadataHashForSigning(const vector<int> &sizes,
+ const string& out_metadata_hash_file) {
+ LOG(INFO) << "Calculating metadata hash for signing.";
+ LOG_IF(FATAL, FLAGS_in_file.empty())
+ << "Must pass --in_file to calculate metadata hash for signing.";
+ LOG_IF(FATAL, out_metadata_hash_file.empty())
+ << "Must pass --out_metadata_hash_file to calculate metadata hash.";
+
+ vector<char> hash;
+ bool result = PayloadSigner::HashMetadataForSigning(FLAGS_in_file, sizes,
+ &hash);
+ CHECK(result);
+
+ result = utils::WriteFile(out_metadata_hash_file.c_str(), hash.data(),
+ hash.size());
+ CHECK(result);
+
+ LOG(INFO) << "Done calculating metadata hash for signing.";
+}
+
+void SignPayload() {
+ LOG(INFO) << "Signing payload.";
+ LOG_IF(FATAL, FLAGS_in_file.empty())
+ << "Must pass --in_file to sign payload.";
+ LOG_IF(FATAL, FLAGS_out_file.empty())
+ << "Must pass --out_file to sign payload.";
+ LOG_IF(FATAL, FLAGS_signature_file.empty())
+ << "Must pass --signature_file to sign payload.";
+ vector<vector<char> > signatures;
+ vector<string> signature_files;
+ base::SplitString(FLAGS_signature_file, ':', &signature_files);
+ for (vector<string>::iterator it = signature_files.begin(),
+ e = signature_files.end(); it != e; ++it) {
+ vector<char> signature;
+ CHECK(utils::ReadFile(*it, &signature));
+ signatures.push_back(signature);
+ }
+ uint64_t final_metadata_size;
+ CHECK(PayloadSigner::AddSignatureToPayload(
+ FLAGS_in_file, signatures, FLAGS_out_file, &final_metadata_size));
+ LOG(INFO) << "Done signing payload. Final metadata size = "
+ << final_metadata_size;
+}
+
+void VerifySignedPayload() {
+ LOG(INFO) << "Verifying signed payload.";
+ LOG_IF(FATAL, FLAGS_in_file.empty())
+ << "Must pass --in_file to verify signed payload.";
+ LOG_IF(FATAL, FLAGS_public_key.empty())
+ << "Must pass --public_key to verify signed payload.";
+ CHECK(PayloadSigner::VerifySignedPayload(FLAGS_in_file, FLAGS_public_key,
+ FLAGS_public_key_version));
+ LOG(INFO) << "Done verifying signed payload.";
+}
+
+void ApplyDelta() {
+ LOG(INFO) << "Applying delta.";
+ LOG_IF(FATAL, FLAGS_old_image.empty())
+ << "Must pass --old_image to apply delta.";
+ Prefs prefs;
+ InstallPlan install_plan;
+ LOG(INFO) << "Setting up preferences under: " << FLAGS_prefs_dir;
+ LOG_IF(ERROR, !prefs.Init(base::FilePath(FLAGS_prefs_dir)))
+ << "Failed to initialize preferences.";
+ // Get original checksums
+ LOG(INFO) << "Calculating original checksums";
+ PartitionInfo kern_info, root_info;
+ CHECK(DeltaDiffGenerator::InitializePartitionInfo(true, // is_kernel
+ FLAGS_old_kernel,
+ &kern_info));
+ CHECK(DeltaDiffGenerator::InitializePartitionInfo(false, // is_kernel
+ FLAGS_old_image,
+ &root_info));
+ install_plan.kernel_hash.assign(kern_info.hash().begin(),
+ kern_info.hash().end());
+ install_plan.rootfs_hash.assign(root_info.hash().begin(),
+ root_info.hash().end());
+ DeltaPerformer performer(&prefs, NULL, &install_plan);
+ CHECK_EQ(performer.Open(FLAGS_old_image.c_str(), 0, 0), 0);
+ CHECK(performer.OpenKernel(FLAGS_old_kernel.c_str()));
+ vector<char> buf(1024 * 1024);
+ int fd = open(FLAGS_in_file.c_str(), O_RDONLY, 0);
+ CHECK_GE(fd, 0);
+ ScopedFdCloser fd_closer(&fd);
+ for (off_t offset = 0;; offset += buf.size()) {
+ ssize_t bytes_read;
+ CHECK(utils::PReadAll(fd, &buf[0], buf.size(), offset, &bytes_read));
+ if (bytes_read == 0)
+ break;
+ CHECK_EQ(performer.Write(&buf[0], bytes_read), bytes_read);
+ }
+ CHECK_EQ(performer.Close(), 0);
+ DeltaPerformer::ResetUpdateProgress(&prefs, false);
+ LOG(INFO) << "Done applying delta.";
+}
+
+int Main(int argc, char** argv) {
+ google::ParseCommandLineFlags(&argc, &argv, true);
+ CommandLine::Init(argc, argv);
+ Terminator::Init();
+ Subprocess::Init();
+
+ logging::LoggingSettings log_settings;
+ log_settings.log_file = "delta_generator.log";
+ log_settings.logging_dest = logging::LOG_TO_SYSTEM_DEBUG_LOG;
+ log_settings.lock_log = logging::DONT_LOCK_LOG_FILE;
+ log_settings.delete_old = logging::APPEND_TO_OLD_LOG_FILE;
+ log_settings.dcheck_state =
+ logging::DISABLE_DCHECK_FOR_NON_OFFICIAL_RELEASE_BUILDS;
+
+ logging::InitLogging(log_settings);
+
+ vector<int> signature_sizes;
+ ParseSignatureSizes(FLAGS_signature_size, &signature_sizes);
+
+ if (!FLAGS_out_hash_file.empty() || !FLAGS_out_metadata_hash_file.empty()) {
+ if (!FLAGS_out_hash_file.empty()) {
+ CalculatePayloadHashForSigning(signature_sizes, FLAGS_out_hash_file);
+ }
+ if (!FLAGS_out_metadata_hash_file.empty()) {
+ CalculateMetadataHashForSigning(signature_sizes,
+ FLAGS_out_metadata_hash_file);
+ }
+ return 0;
+ }
+ if (!FLAGS_signature_file.empty()) {
+ SignPayload();
+ return 0;
+ }
+ if (!FLAGS_public_key.empty()) {
+ VerifySignedPayload();
+ return 0;
+ }
+ if (!FLAGS_in_file.empty()) {
+ ApplyDelta();
+ return 0;
+ }
+ CHECK(!FLAGS_new_image.empty());
+ CHECK(!FLAGS_out_file.empty());
+ CHECK(!FLAGS_new_kernel.empty());
+
+ bool is_delta = !FLAGS_old_image.empty();
+
+ ImageInfo old_image_info;
+ ImageInfo new_image_info;
+
+ // Ignore failures. These are optional arguments.
+ ParseImageInfo(FLAGS_new_channel,
+ FLAGS_new_board,
+ FLAGS_new_version,
+ FLAGS_new_key,
+ FLAGS_new_build_channel,
+ FLAGS_new_build_version,
+ &new_image_info);
+
+ // Ignore failures. These are optional arguments.
+ ParseImageInfo(FLAGS_old_channel,
+ FLAGS_old_board,
+ FLAGS_old_version,
+ FLAGS_old_key,
+ FLAGS_old_build_channel,
+ FLAGS_old_build_version,
+ &old_image_info);
+
+ if (is_delta) {
+ LOG(INFO) << "Generating delta update";
+ CHECK(!FLAGS_old_dir.empty());
+ CHECK(!FLAGS_new_dir.empty());
+ if ((!IsDir(FLAGS_old_dir.c_str())) || (!IsDir(FLAGS_new_dir.c_str()))) {
+ LOG(FATAL) << "old_dir or new_dir not directory";
+ }
+ } else {
+ LOG(INFO) << "Generating full update";
+ }
+
+ uint64_t metadata_size;
+ if (!DeltaDiffGenerator::GenerateDeltaUpdateFile(
+ FLAGS_old_dir,
+ FLAGS_old_image,
+ FLAGS_new_dir,
+ FLAGS_new_image,
+ FLAGS_old_kernel,
+ FLAGS_new_kernel,
+ FLAGS_out_file,
+ FLAGS_private_key,
+ FLAGS_chunk_size,
+ FLAGS_rootfs_partition_size,
+ is_delta ? &old_image_info : NULL,
+ &new_image_info,
+ &metadata_size)) {
+ return 1;
+ }
+ return 0;
+}
+
+} // namespace {}
+
+} // namespace chromeos_update_engine
+
+int main(int argc, char** argv) {
+ return chromeos_update_engine::Main(argc, argv);
+}
diff --git a/payload_generator/graph_types.h b/payload_generator/graph_types.h
new file mode 100644
index 0000000..c5531c2
--- /dev/null
+++ b/payload_generator/graph_types.h
@@ -0,0 +1,83 @@
+// Copyright (c) 2009 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_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
+
+#include <map>
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/basictypes.h>
+
+#include "update_engine/update_metadata.pb.h"
+
+// A few classes that help in generating delta images use these types
+// for the graph work.
+
+namespace chromeos_update_engine {
+
+bool operator==(const Extent& a, const Extent& b);
+
+struct EdgeProperties {
+ // Read-before extents. I.e., blocks in |extents| must be read by the
+ // node pointed to before the pointing node runs (presumably b/c it
+ // overwrites these blocks).
+ std::vector<Extent> extents;
+
+ // Write before extents. I.e., blocks in |write_extents| must be written
+ // by the node pointed to before the pointing node runs (presumably
+ // b/c it reads the data written by the other node).
+ std::vector<Extent> write_extents;
+
+ bool operator==(const EdgeProperties& that) const {
+ return extents == that.extents && write_extents == that.write_extents;
+ }
+};
+
+struct Vertex {
+ Vertex() :
+ valid(true),
+ index(-1),
+ lowlink(-1),
+ chunk_offset(0),
+ chunk_size(-1) {}
+ bool valid;
+
+ typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap;
+ EdgeMap out_edges;
+
+ // We sometimes wish to consider a subgraph of a graph. A subgraph would have
+ // a subset of the vertices from the graph and a subset of the edges.
+ // When considering this vertex within a subgraph, subgraph_edges stores
+ // the out-edges.
+ typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap;
+ SubgraphEdgeMap subgraph_edges;
+
+ // For Tarjan's algorithm:
+ std::vector<Vertex>::size_type index;
+ std::vector<Vertex>::size_type lowlink;
+
+ // Other Vertex properties:
+ DeltaArchiveManifest_InstallOperation op;
+ std::string file_name;
+ off_t chunk_offset;
+ off_t chunk_size;
+
+ typedef std::vector<Vertex>::size_type Index;
+ static const Vertex::Index kInvalidIndex = -1;
+};
+
+typedef std::vector<Vertex> Graph;
+
+typedef std::pair<Vertex::Index, Vertex::Index> Edge;
+
+const uint64_t kTempBlockStart = 1ULL << 60;
+COMPILE_ASSERT(kTempBlockStart != 0, kTempBlockStart_invalid);
+
+} // namespace chromeos_update_engine
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
diff --git a/payload_generator/graph_utils.cc b/payload_generator/graph_utils.cc
new file mode 100644
index 0000000..8b6535d
--- /dev/null
+++ b/payload_generator/graph_utils.cc
@@ -0,0 +1,176 @@
+// Copyright (c) 2009 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/payload_generator/graph_utils.h"
+
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/basictypes.h>
+#include <base/logging.h>
+
+#include "update_engine/payload_constants.h"
+
+using std::make_pair;
+using std::pair;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace graph_utils {
+
+uint64_t EdgeWeight(const Graph& graph, const Edge& edge) {
+ uint64_t weight = 0;
+ const vector<Extent>& extents =
+ graph[edge.first].out_edges.find(edge.second)->second.extents;
+ for (vector<Extent>::const_iterator it = extents.begin();
+ it != extents.end(); ++it) {
+ if (it->start_block() != kSparseHole)
+ weight += it->num_blocks();
+ }
+ return weight;
+}
+
+void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) {
+ // First try to extend the last extent in |extents|, if any.
+ if (!extents->empty()) {
+ Extent& extent = extents->back();
+ uint64_t next_block = extent.start_block() == kSparseHole ?
+ kSparseHole : extent.start_block() + extent.num_blocks();
+ if (next_block == block) {
+ extent.set_num_blocks(extent.num_blocks() + 1);
+ return;
+ }
+ }
+ // If unable to extend the last extent, append a new single-block extent.
+ Extent new_extent;
+ new_extent.set_start_block(block);
+ new_extent.set_num_blocks(1);
+ extents->push_back(new_extent);
+}
+
+void AddReadBeforeDep(Vertex* src,
+ Vertex::Index dst,
+ uint64_t block) {
+ Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst);
+ if (edge_it == src->out_edges.end()) {
+ // Must create new edge
+ pair<Vertex::EdgeMap::iterator, bool> result =
+ src->out_edges.insert(make_pair(dst, EdgeProperties()));
+ CHECK(result.second);
+ edge_it = result.first;
+ }
+ AppendBlockToExtents(&edge_it->second.extents, block);
+}
+
+void AddReadBeforeDepExtents(Vertex* src,
+ Vertex::Index dst,
+ const vector<Extent>& extents) {
+ // TODO(adlr): Be more efficient than adding each block individually.
+ for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
+ it != e; ++it) {
+ const Extent& extent = *it;
+ for (uint64_t block = extent.start_block(),
+ block_end = extent.start_block() + extent.num_blocks();
+ block != block_end; ++block) {
+ AddReadBeforeDep(src, dst, block);
+ }
+ }
+}
+
+void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map) {
+ // Specially crafted for-loop for the map-iterate-delete dance.
+ for (Vertex::EdgeMap::iterator it = edge_map->begin();
+ it != edge_map->end(); ) {
+ if (!it->second.write_extents.empty())
+ it->second.write_extents.clear();
+ if (it->second.extents.empty()) {
+ // Erase *it, as it contains no blocks
+ edge_map->erase(it++);
+ } else {
+ ++it;
+ }
+ }
+}
+
+// For each node N in graph, drop all edges N->|index|.
+void DropIncomingEdgesTo(Graph* graph, Vertex::Index index) {
+ // This would be much more efficient if we had doubly-linked
+ // edges in the graph.
+ for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
+ it->out_edges.erase(index);
+ }
+}
+
+Extent GetElement(const std::vector<Extent>& collection, size_t index) {
+ return collection[index];
+}
+Extent GetElement(
+ const google::protobuf::RepeatedPtrField<Extent>& collection,
+ size_t index) {
+ return collection.Get(index);
+}
+
+namespace {
+template<typename T>
+void DumpExtents(const T& field, int prepend_space_count) {
+ string header(prepend_space_count, ' ');
+ for (int i = 0, e = field.size(); i != e; ++i) {
+ LOG(INFO) << header << "(" << GetElement(field, i).start_block() << ", "
+ << GetElement(field, i).num_blocks() << ")";
+ }
+}
+
+void DumpOutEdges(const Vertex::EdgeMap& out_edges) {
+ for (Vertex::EdgeMap::const_iterator it = out_edges.begin(),
+ e = out_edges.end(); it != e; ++it) {
+ LOG(INFO) << " " << it->first << " read-before:";
+ DumpExtents(it->second.extents, 6);
+ LOG(INFO) << " write-before:";
+ DumpExtents(it->second.write_extents, 6);
+ }
+}
+} // namespace {}
+
+void DumpGraph(const Graph& graph) {
+ LOG(INFO) << "Graph length: " << graph.size();
+ for (Graph::size_type i = 0, e = graph.size(); i != e; ++i) {
+ string type_str = "UNK";
+ switch(graph[i].op.type()) {
+ case DeltaArchiveManifest_InstallOperation_Type_BSDIFF:
+ type_str = "BSDIFF";
+ break;
+ case DeltaArchiveManifest_InstallOperation_Type_MOVE:
+ type_str = "MOVE";
+ break;
+ case DeltaArchiveManifest_InstallOperation_Type_REPLACE:
+ type_str = "REPLACE";
+ break;
+ case DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ:
+ type_str = "REPLACE_BZ";
+ break;
+ }
+ LOG(INFO) << i
+ << (graph[i].valid ? "" : "-INV")
+ << ": " << graph[i].file_name
+ << " " << graph[i].chunk_size << "@" << graph[i].chunk_offset
+ << ": " << type_str;
+ LOG(INFO) << " src_extents:";
+ DumpExtents(graph[i].op.src_extents(), 4);
+ LOG(INFO) << " dst_extents:";
+ DumpExtents(graph[i].op.dst_extents(), 4);
+ LOG(INFO) << " out edges:";
+ DumpOutEdges(graph[i].out_edges);
+ }
+}
+
+} // namespace graph_utils
+
+bool operator==(const Extent& a, const Extent& b) {
+ return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/graph_utils.h b/payload_generator/graph_utils.h
new file mode 100644
index 0000000..0489793
--- /dev/null
+++ b/payload_generator/graph_utils.h
@@ -0,0 +1,65 @@
+// Copyright (c) 2009 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_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
+
+#include <vector>
+
+#include <base/basictypes.h>
+
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/update_metadata.pb.h"
+
+// A few utility functions for graphs
+
+namespace chromeos_update_engine {
+
+namespace graph_utils {
+
+// Returns the number of blocks represented by all extents in the edge.
+uint64_t EdgeWeight(const Graph& graph, const Edge& edge);
+
+// These add a read-before dependency from graph[src] -> graph[dst]. If the dep
+// already exists, the block/s is/are added to the existing edge.
+void AddReadBeforeDep(Vertex* src,
+ Vertex::Index dst,
+ uint64_t block);
+void AddReadBeforeDepExtents(Vertex* src,
+ Vertex::Index dst,
+ const std::vector<Extent>& extents);
+
+void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map);
+
+// For each node N in graph, drop all edges N->|index|.
+void DropIncomingEdgesTo(Graph* graph, Vertex::Index index);
+
+// block must either be the next block in the last extent or a block
+// in the next extent. This function will not handle inserting block
+// into an arbitrary place in the extents.
+void AppendBlockToExtents(std::vector<Extent>* extents, uint64_t block);
+
+// Get/SetElement are intentionally overloaded so that templated functions
+// can accept either type of collection of Extents.
+Extent GetElement(const std::vector<Extent>& collection, size_t index);
+Extent GetElement(
+ const google::protobuf::RepeatedPtrField<Extent>& collection,
+ size_t index);
+
+template<typename T>
+uint64_t BlocksInExtents(const T& collection) {
+ uint64_t ret = 0;
+ for (size_t i = 0; i < static_cast<size_t>(collection.size()); ++i) {
+ ret += GetElement(collection, i).num_blocks();
+ }
+ return ret;
+}
+
+void DumpGraph(const Graph& graph);
+
+} // namespace graph_utils
+
+} // namespace chromeos_update_engine
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
diff --git a/payload_generator/graph_utils_unittest.cc b/payload_generator/graph_utils_unittest.cc
new file mode 100644
index 0000000..0aed78d
--- /dev/null
+++ b/payload_generator/graph_utils_unittest.cc
@@ -0,0 +1,123 @@
+// Copyright (c) 2009 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 <utility>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/graph_utils.h"
+
+using std::make_pair;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class GraphUtilsTest : public ::testing::Test {};
+
+TEST(GraphUtilsTest, SimpleTest) {
+ Graph graph(2);
+
+ graph[0].out_edges.insert(make_pair(1, EdgeProperties()));
+
+ vector<Extent>& extents = graph[0].out_edges[1].extents;
+
+ EXPECT_EQ(0, extents.size());
+ graph_utils::AppendBlockToExtents(&extents, 0);
+ EXPECT_EQ(1, extents.size());
+ graph_utils::AppendBlockToExtents(&extents, 1);
+ graph_utils::AppendBlockToExtents(&extents, 2);
+ EXPECT_EQ(1, extents.size());
+ graph_utils::AppendBlockToExtents(&extents, 4);
+
+ EXPECT_EQ(2, extents.size());
+ EXPECT_EQ(0, extents[0].start_block());
+ EXPECT_EQ(3, extents[0].num_blocks());
+ EXPECT_EQ(4, extents[1].start_block());
+ EXPECT_EQ(1, extents[1].num_blocks());
+
+ EXPECT_EQ(4, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
+}
+
+TEST(GraphUtilsTest, AppendSparseToExtentsTest) {
+ vector<Extent> extents;
+
+ EXPECT_EQ(0, extents.size());
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ EXPECT_EQ(1, extents.size());
+ graph_utils::AppendBlockToExtents(&extents, 0);
+ EXPECT_EQ(2, extents.size());
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+
+ ASSERT_EQ(3, extents.size());
+ EXPECT_EQ(kSparseHole, extents[0].start_block());
+ EXPECT_EQ(1, extents[0].num_blocks());
+ EXPECT_EQ(0, extents[1].start_block());
+ EXPECT_EQ(1, extents[1].num_blocks());
+ EXPECT_EQ(kSparseHole, extents[2].start_block());
+ EXPECT_EQ(2, extents[2].num_blocks());
+}
+
+TEST(GraphUtilsTest, BlocksInExtentsTest) {
+ {
+ vector<Extent> extents;
+ EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
+ extents.push_back(ExtentForRange(0, 1));
+ EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
+ extents.push_back(ExtentForRange(23, 55));
+ EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
+ extents.push_back(ExtentForRange(1, 2));
+ EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
+ }
+ {
+ google::protobuf::RepeatedPtrField<Extent> extents;
+ EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
+ *extents.Add() = ExtentForRange(0, 1);
+ EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
+ *extents.Add() = ExtentForRange(23, 55);
+ EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
+ *extents.Add() = ExtentForRange(1, 2);
+ EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
+ }
+}
+
+TEST(GraphUtilsTest, DepsTest) {
+ Graph graph(3);
+
+ graph_utils::AddReadBeforeDep(&graph[0], 1, 3);
+ EXPECT_EQ(1, graph[0].out_edges.size());
+ {
+ Extent& extent = graph[0].out_edges[1].extents[0];
+ EXPECT_EQ(3, extent.start_block());
+ EXPECT_EQ(1, extent.num_blocks());
+ }
+ graph_utils::AddReadBeforeDep(&graph[0], 1, 4);
+ EXPECT_EQ(1, graph[0].out_edges.size());
+ {
+ Extent& extent = graph[0].out_edges[1].extents[0];
+ EXPECT_EQ(3, extent.start_block());
+ EXPECT_EQ(2, extent.num_blocks());
+ }
+ graph_utils::AddReadBeforeDepExtents(&graph[2], 1,
+ vector<Extent>(1, ExtentForRange(5, 2)));
+ EXPECT_EQ(1, graph[2].out_edges.size());
+ {
+ Extent& extent = graph[2].out_edges[1].extents[0];
+ EXPECT_EQ(5, extent.start_block());
+ EXPECT_EQ(2, extent.num_blocks());
+ }
+ // Change most recent edge from read-before to write-before
+ graph[2].out_edges[1].write_extents.swap(graph[2].out_edges[1].extents);
+ graph_utils::DropWriteBeforeDeps(&graph[2].out_edges);
+ EXPECT_EQ(0, graph[2].out_edges.size());
+
+ EXPECT_EQ(1, graph[0].out_edges.size());
+ graph_utils::DropIncomingEdgesTo(&graph, 1);
+ EXPECT_EQ(0, graph[0].out_edges.size());
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/metadata.cc b/payload_generator/metadata.cc
new file mode 100644
index 0000000..f0c9238
--- /dev/null
+++ b/payload_generator/metadata.cc
@@ -0,0 +1,486 @@
+// Copyright (c) 2012 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 <algorithm>
+#include <string>
+#include <vector>
+
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+#include <et/com_err.h>
+#include <ext2fs/ext2_io.h>
+#include <ext2fs/ext2fs.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/metadata.h"
+#include "update_engine/utils.h"
+
+using base::StringPrintf;
+using std::min;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+const size_t kBlockSize = 4096;
+
+typedef DeltaDiffGenerator::Block Block;
+
+// Read data from the specified extents.
+bool ReadExtentsData(const ext2_filsys fs,
+ const vector<Extent>& extents,
+ vector<char>* data) {
+ // Resize the data buffer to hold all data in the extents
+ size_t num_data_blocks = 0;
+ for (vector<Extent>::const_iterator it = extents.begin();
+ it != extents.end(); it++) {
+ num_data_blocks += it->num_blocks();
+ }
+
+ data->resize(num_data_blocks * kBlockSize);
+
+ // Read in the data blocks
+ const size_t kMaxReadBlocks = 256;
+ vector<Block>::size_type blocks_copied_count = 0;
+ for (vector<Extent>::const_iterator it = extents.begin();
+ it != extents.end(); it++) {
+ vector<Block>::size_type blocks_read = 0;
+ while (blocks_read < it->num_blocks()) {
+ const int copy_block_cnt =
+ min(kMaxReadBlocks,
+ static_cast<size_t>(
+ it->num_blocks() - blocks_read));
+ TEST_AND_RETURN_FALSE_ERRCODE(
+ io_channel_read_blk(fs->io,
+ it->start_block() + blocks_read,
+ copy_block_cnt,
+ &(*data)[blocks_copied_count * kBlockSize]));
+ blocks_read += copy_block_cnt;
+ blocks_copied_count += copy_block_cnt;
+ }
+ }
+
+ return true;
+}
+
+// Compute the bsdiff between two metadata blobs.
+bool ComputeMetadataBsdiff(const vector<char>& old_metadata,
+ const vector<char>& new_metadata,
+ vector<char>* bsdiff_delta) {
+ const string kTempFileTemplate("CrAU_temp_data.XXXXXX");
+
+ // Write the metadata buffers to temporary files
+ int old_fd;
+ string temp_old_file_path;
+ TEST_AND_RETURN_FALSE(
+ utils::MakeTempFile(kTempFileTemplate, &temp_old_file_path, &old_fd));
+ TEST_AND_RETURN_FALSE(old_fd >= 0);
+ ScopedPathUnlinker temp_old_file_path_unlinker(temp_old_file_path);
+ ScopedFdCloser old_fd_closer(&old_fd);
+ TEST_AND_RETURN_FALSE(utils::WriteAll(old_fd,
+ &old_metadata[0],
+ old_metadata.size()));
+
+ int new_fd;
+ string temp_new_file_path;
+ TEST_AND_RETURN_FALSE(
+ utils::MakeTempFile(kTempFileTemplate, &temp_new_file_path, &new_fd));
+ TEST_AND_RETURN_FALSE(new_fd >= 0);
+ ScopedPathUnlinker temp_new_file_path_unlinker(temp_new_file_path);
+ ScopedFdCloser new_fd_closer(&new_fd);
+ TEST_AND_RETURN_FALSE(utils::WriteAll(new_fd,
+ &new_metadata[0],
+ new_metadata.size()));
+
+ // Perform bsdiff on these files
+ TEST_AND_RETURN_FALSE(
+ DeltaDiffGenerator::BsdiffFiles(temp_old_file_path,
+ temp_new_file_path,
+ bsdiff_delta));
+
+ return true;
+}
+
+// Add the specified metadata extents to the graph and blocks vector.
+bool AddMetadataExtents(Graph* graph,
+ vector<Block>* blocks,
+ const ext2_filsys fs_old,
+ const ext2_filsys fs_new,
+ const string& metadata_name,
+ const vector<Extent>& extents,
+ int data_fd,
+ off_t* data_file_size) {
+ vector<char> data; // Data blob that will be written to delta file.
+ DeltaArchiveManifest_InstallOperation op;
+
+ {
+ // Read in the metadata blocks from the old and new image.
+ vector<char> old_data;
+ TEST_AND_RETURN_FALSE(ReadExtentsData(fs_old, extents, &old_data));
+
+ vector<char> new_data;
+ TEST_AND_RETURN_FALSE(ReadExtentsData(fs_new, extents, &new_data));
+
+ // Determine the best way to compress this.
+ vector<char> new_data_bz;
+ TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
+ CHECK(!new_data_bz.empty());
+
+ size_t current_best_size = 0;
+ if (new_data.size() <= new_data_bz.size()) {
+ op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+ current_best_size = new_data.size();
+ data = new_data;
+ } else {
+ op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ current_best_size = new_data_bz.size();
+ data = new_data_bz;
+ }
+
+ if (old_data == new_data) {
+ // No change in data.
+ op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ current_best_size = 0;
+ data.clear();
+ } else {
+ // Try bsdiff of old to new data
+ vector<char> bsdiff_delta;
+ TEST_AND_RETURN_FALSE(ComputeMetadataBsdiff(old_data,
+ new_data,
+ &bsdiff_delta));
+ CHECK_GT(bsdiff_delta.size(), static_cast<vector<char>::size_type>(0));
+
+ if (bsdiff_delta.size() < current_best_size) {
+ op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+ current_best_size = bsdiff_delta.size();
+ data = bsdiff_delta;
+ }
+ }
+
+ CHECK_EQ(data.size(), current_best_size);
+
+ // Set the source and dest extents to be the same since the filesystem
+ // structures are identical
+ if (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE ||
+ op.type() == DeltaArchiveManifest_InstallOperation_Type_BSDIFF) {
+ DeltaDiffGenerator::StoreExtents(extents, op.mutable_src_extents());
+ op.set_src_length(old_data.size());
+ }
+
+ DeltaDiffGenerator::StoreExtents(extents, op.mutable_dst_extents());
+ op.set_dst_length(new_data.size());
+ }
+
+ // Write data to output file
+ if (op.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+ op.set_data_offset(*data_file_size);
+ op.set_data_length(data.size());
+ }
+
+ TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, &data[0], data.size()));
+ *data_file_size += data.size();
+
+ // Now, insert into graph and blocks vector
+ graph->resize(graph->size() + 1);
+ Vertex::Index vertex = graph->size() - 1;
+ (*graph)[vertex].op = op;
+ CHECK((*graph)[vertex].op.has_type());
+ (*graph)[vertex].file_name = metadata_name;
+
+ TEST_AND_RETURN_FALSE(DeltaDiffGenerator::AddInstallOpToBlocksVector(
+ (*graph)[vertex].op,
+ *graph,
+ vertex,
+ blocks));
+
+ return true;
+}
+
+// Reads the file system metadata extents.
+bool ReadFilesystemMetadata(Graph* graph,
+ vector<Block>* blocks,
+ const ext2_filsys fs_old,
+ const ext2_filsys fs_new,
+ int data_fd,
+ off_t* data_file_size) {
+ LOG(INFO) << "Processing <rootfs-metadata>";
+
+ // Read all the extents that belong to the main file system metadata.
+ // The metadata blocks are at the start of each block group and goes
+ // until the end of the inode table.
+ for (dgrp_t bg = 0; bg < fs_old->group_desc_count; bg++) {
+ struct ext2_group_desc* group_desc = ext2fs_group_desc(fs_old,
+ fs_old->group_desc,
+ bg);
+ __u32 num_metadata_blocks = (group_desc->bg_inode_table +
+ fs_old->inode_blocks_per_group) -
+ (bg * fs_old->super->s_blocks_per_group);
+ __u32 bg_start_block = bg * fs_old->super->s_blocks_per_group;
+
+ // Due to bsdiff slowness, we're going to break each block group down
+ // into metadata chunks and feed them to bsdiff.
+ __u32 num_chunks = 10;
+ __u32 blocks_per_chunk = num_metadata_blocks / num_chunks;
+ __u32 curr_block = bg_start_block;
+ for (__u32 chunk = 0; chunk < num_chunks; chunk++) {
+ Extent extent;
+ if (chunk < num_chunks - 1) {
+ extent = ExtentForRange(curr_block, blocks_per_chunk);
+ } else {
+ extent = ExtentForRange(curr_block,
+ bg_start_block + num_metadata_blocks -
+ curr_block);
+ }
+
+ vector<Extent> extents;
+ extents.push_back(extent);
+
+ string metadata_name = StringPrintf("<rootfs-bg-%d-%d-metadata>",
+ bg, chunk);
+
+ LOG(INFO) << "Processing " << metadata_name;
+
+ TEST_AND_RETURN_FALSE(AddMetadataExtents(graph,
+ blocks,
+ fs_old,
+ fs_new,
+ metadata_name,
+ extents,
+ data_fd,
+ data_file_size));
+
+ curr_block += blocks_per_chunk;
+ }
+ }
+
+ return true;
+}
+
+// Processes all blocks belonging to an inode
+int ProcessInodeAllBlocks(ext2_filsys fs,
+ blk_t* blocknr,
+ e2_blkcnt_t blockcnt,
+ blk_t ref_blk,
+ int ref_offset,
+ void* priv) {
+ vector<Extent>* extents = static_cast<vector<Extent>*>(priv);
+ graph_utils::AppendBlockToExtents(extents, *blocknr);
+ return 0;
+}
+
+// Processes only indirect, double indirect or triple indirect metadata
+// blocks belonging to an inode
+int ProcessInodeMetadataBlocks(ext2_filsys fs,
+ blk_t* blocknr,
+ e2_blkcnt_t blockcnt,
+ blk_t ref_blk,
+ int ref_offset,
+ void* priv) {
+ vector<Extent>* extents = static_cast<vector<Extent>*>(priv);
+ if (blockcnt < 0) {
+ graph_utils::AppendBlockToExtents(extents, *blocknr);
+ }
+ return 0;
+}
+
+// Read inode metadata blocks.
+bool ReadInodeMetadata(Graph* graph,
+ vector<Block>* blocks,
+ const ext2_filsys fs_old,
+ const ext2_filsys fs_new,
+ int data_fd,
+ off_t* data_file_size) {
+ TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_read_inode_bitmap(fs_old));
+ TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_read_inode_bitmap(fs_new));
+
+ ext2_inode_scan iscan;
+ TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open_inode_scan(fs_old, 0, &iscan));
+
+ ext2_ino_t ino;
+ ext2_inode old_inode;
+ while (true) {
+ // Get the next inode on both file systems
+ errcode_t error = ext2fs_get_next_inode(iscan, &ino, &old_inode);
+
+ // If we get an error enumerating the inodes, we'll just log the error
+ // and exit from our loop which will eventually return a success code
+ // back to the caller. The inode blocks that we cannot account for will
+ // be handled by DeltaDiffGenerator::ReadUnwrittenBlocks().
+ if (error) {
+ LOG(ERROR) << "Failed to retrieve next inode (" << error << ")";
+ break;
+ }
+
+ if (ino == 0) {
+ break;
+ }
+
+ if (ino == EXT2_RESIZE_INO) {
+ continue;
+ }
+
+ ext2_inode new_inode;
+ error = ext2fs_read_inode(fs_new, ino, &new_inode);
+ if (error) {
+ LOG(ERROR) << "Failed to retrieve new inode (" << error << ")";
+ continue;
+ }
+
+ // Skip inodes that are not in use
+ if (!ext2fs_test_inode_bitmap(fs_old->inode_map, ino) ||
+ !ext2fs_test_inode_bitmap(fs_new->inode_map, ino)) {
+ continue;
+ }
+
+ // Skip inodes that have no data blocks
+ if (old_inode.i_blocks == 0 || new_inode.i_blocks == 0) {
+ continue;
+ }
+
+ // Skip inodes that are not the same type
+ bool is_old_dir = (ext2fs_check_directory(fs_old, ino) == 0);
+ bool is_new_dir = (ext2fs_check_directory(fs_new, ino) == 0);
+ if (is_old_dir != is_new_dir) {
+ continue;
+ }
+
+ // Process the inodes metadata blocks
+ // For normal files, metadata blocks are indirect, double indirect
+ // and triple indirect blocks (no data blocks). For directories and
+ // the journal, all blocks are considered metadata blocks.
+ LOG(INFO) << "Processing inode " << ino << " metadata";
+
+ bool all_blocks = ((ino == EXT2_JOURNAL_INO) || is_old_dir || is_new_dir);
+
+ vector<Extent> old_extents;
+ error = ext2fs_block_iterate2(fs_old, ino, 0, NULL,
+ all_blocks ? ProcessInodeAllBlocks :
+ ProcessInodeMetadataBlocks,
+ &old_extents);
+ if (error) {
+ LOG(ERROR) << "Failed to enumerate old inode " << ino
+ << " blocks (" << error << ")";
+ continue;
+ }
+
+ vector<Extent> new_extents;
+ error = ext2fs_block_iterate2(fs_new, ino, 0, NULL,
+ all_blocks ? ProcessInodeAllBlocks :
+ ProcessInodeMetadataBlocks,
+ &new_extents);
+ if (error) {
+ LOG(ERROR) << "Failed to enumerate new inode " << ino
+ << " blocks (" << error << ")";
+ continue;
+ }
+
+ // Skip inode if there are no metadata blocks
+ if (old_extents.size() == 0 || new_extents.size() == 0) {
+ continue;
+ }
+
+ // Make sure the two inodes have the same metadata blocks
+ if (old_extents.size() != new_extents.size()) {
+ continue;
+ }
+
+ bool same_metadata_extents = true;
+ vector<Extent>::iterator it_old;
+ vector<Extent>::iterator it_new;
+ for (it_old = old_extents.begin(),
+ it_new = new_extents.begin();
+ it_old != old_extents.end() && it_new != new_extents.end();
+ it_old++, it_new++) {
+ if (it_old->start_block() != it_new->start_block() ||
+ it_old->num_blocks() != it_new->num_blocks()) {
+ same_metadata_extents = false;
+ break;
+ }
+ }
+
+ if (!same_metadata_extents) {
+ continue;
+ }
+
+ // We have identical inode metadata blocks, we can now add them to
+ // our graph and blocks vector
+ string metadata_name = StringPrintf("<rootfs-inode-%d-metadata>", ino);
+ TEST_AND_RETURN_FALSE(AddMetadataExtents(graph,
+ blocks,
+ fs_old,
+ fs_new,
+ metadata_name,
+ old_extents,
+ data_fd,
+ data_file_size));
+ }
+
+ ext2fs_close_inode_scan(iscan);
+
+ return true;
+}
+
+} // namespace {}
+
+// Reads metadata from old image and new image and determines
+// the smallest way to encode the metadata for the diff.
+// If there's no change in the metadata, it creates a MOVE
+// operation. If there is a change, the smallest of REPLACE, REPLACE_BZ,
+// or BSDIFF wins. It writes the diff to data_fd and updates data_file_size
+// accordingly. It also adds the required operation to the graph and adds the
+// metadata extents to blocks.
+// Returns true on success.
+bool Metadata::DeltaReadMetadata(Graph* graph,
+ vector<Block>* blocks,
+ const string& old_image,
+ const string& new_image,
+ int data_fd,
+ off_t* data_file_size) {
+ // Open the two file systems.
+ ext2_filsys fs_old;
+ TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open(old_image.c_str(), 0, 0, 0,
+ unix_io_manager, &fs_old));
+ ScopedExt2fsCloser fs_old_closer(fs_old);
+
+ ext2_filsys fs_new;
+ TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open(new_image.c_str(), 0, 0, 0,
+ unix_io_manager, &fs_new));
+ ScopedExt2fsCloser fs_new_closer(fs_new);
+
+ // Make sure these two file systems are the same.
+ // If they are not the same, the metadata blocks will be packaged up in its
+ // entirety by ReadUnwrittenBlocks().
+ if (fs_old->blocksize != fs_new->blocksize ||
+ fs_old->fragsize != fs_new->fragsize ||
+ fs_old->group_desc_count != fs_new->group_desc_count ||
+ fs_old->inode_blocks_per_group != fs_new->inode_blocks_per_group ||
+ fs_old->super->s_inodes_count != fs_new->super->s_inodes_count ||
+ fs_old->super->s_blocks_count != fs_new->super->s_blocks_count) {
+ return true;
+ }
+
+ // Process the main file system metadata (superblock, inode tables, etc)
+ TEST_AND_RETURN_FALSE(ReadFilesystemMetadata(graph,
+ blocks,
+ fs_old,
+ fs_new,
+ data_fd,
+ data_file_size));
+
+ // Process each inode metadata blocks.
+ TEST_AND_RETURN_FALSE(ReadInodeMetadata(graph,
+ blocks,
+ fs_old,
+ fs_new,
+ data_fd,
+ data_file_size));
+
+ return true;
+}
+
+}; // namespace chromeos_update_engine
diff --git a/payload_generator/metadata.h b/payload_generator/metadata.h
new file mode 100644
index 0000000..452e303
--- /dev/null
+++ b/payload_generator/metadata.h
@@ -0,0 +1,37 @@
+// 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_PAYLOAD_GENERATOR_METADATA_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_METADATA_H_
+
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+
+namespace chromeos_update_engine {
+
+class Metadata {
+ public:
+ // Reads metadata from old image and new image and determines
+ // the smallest way to encode the metadata for the diff.
+ // If there's no change in the metadata, it creates a MOVE
+ // operation. If there is a change, the smallest of REPLACE, REPLACE_BZ,
+ // or BSDIFF wins. It writes the diff to data_fd and updates data_file_size
+ // accordingly. It also adds the required operation to the graph and adds the
+ // metadata extents to blocks.
+ // Returns true on success.
+ static bool DeltaReadMetadata(Graph* graph,
+ std::vector<DeltaDiffGenerator::Block>* blocks,
+ const std::string& old_image,
+ const std::string& new_image,
+ int data_fd,
+ off_t* data_file_size);
+
+ private:
+ // This should never be constructed.
+ DISALLOW_IMPLICIT_CONSTRUCTORS(Metadata);
+};
+
+}; // namespace chromeos_update_engine
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_METADATA_H_
diff --git a/payload_generator/metadata_unittest.cc b/payload_generator/metadata_unittest.cc
new file mode 100644
index 0000000..39a2476
--- /dev/null
+++ b/payload_generator/metadata_unittest.cc
@@ -0,0 +1,171 @@
+// Copyright (c) 2012 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 <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <string>
+#include <vector>
+
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/metadata.h"
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+typedef DeltaDiffGenerator::Block Block;
+
+class MetadataTest : public ::testing::Test {
+};
+
+TEST_F(MetadataTest, RunAsRootReadMetadataDissimilarFileSystems) {
+ string a_img, b_img;
+ EXPECT_TRUE(utils::MakeTempFile("a_img.XXXXXX", &a_img, NULL));
+ ScopedPathUnlinker a_img_unlinker(a_img);
+ EXPECT_TRUE(utils::MakeTempFile("b_img.XXXXXX", &b_img, NULL));
+ ScopedPathUnlinker b_img_unlinker(b_img);
+
+ CreateEmptyExtImageAtPath(a_img, 10485759, 4096);
+ CreateEmptyExtImageAtPath(b_img, 11534336, 4096);
+
+ Graph graph;
+ vector<Block> blocks;
+ EXPECT_TRUE(Metadata::DeltaReadMetadata(&graph,
+ &blocks,
+ a_img,
+ b_img,
+ 0,
+ NULL));
+ EXPECT_EQ(graph.size(), 0);
+
+ CreateEmptyExtImageAtPath(a_img, 10485759, 4096);
+ CreateEmptyExtImageAtPath(b_img, 10485759, 8192);
+
+ graph.clear();
+ blocks.clear();
+ EXPECT_TRUE(Metadata::DeltaReadMetadata(&graph,
+ &blocks,
+ a_img,
+ b_img,
+ 0,
+ NULL));
+ EXPECT_EQ(graph.size(), 0);
+}
+
+TEST_F(MetadataTest, RunAsRootReadMetadata) {
+ string a_img, b_img, data_file;
+ EXPECT_TRUE(utils::MakeTempFile("a_img.XXXXXX", &a_img, NULL));
+ ScopedPathUnlinker a_img_unlinker(a_img);
+ EXPECT_TRUE(utils::MakeTempFile("b_img.XXXXXX", &b_img, NULL));
+ ScopedPathUnlinker b_img_unlinker(b_img);
+ EXPECT_TRUE(utils::MakeTempFile("data_file.XXXXXX", &data_file, NULL));
+ ScopedPathUnlinker data_file_unlinker(data_file);
+
+ const size_t image_size = (256 * 1024 * 1024); // Enough for 2 block groups
+ const int block_size = 4096;
+ CreateEmptyExtImageAtPath(a_img, image_size, block_size);
+
+ // Create a file large enough to create an indirect block
+ {
+ string a_img_mnt;
+ ScopedLoopMounter a_img_mount(a_img, &a_img_mnt, 0);
+ System(base::StringPrintf("dd if=/dev/zero of=%s/test_file bs=%d count=%d",
+ a_img_mnt.c_str(), block_size,
+ EXT2_NDIR_BLOCKS + 1));
+ }
+
+ System(base::StringPrintf("cp %s %s", a_img.c_str(), b_img.c_str()));
+
+ int fd = open(data_file.c_str(), O_RDWR | O_CREAT, S_IRWXU);
+ EXPECT_NE(fd, -1);
+ ScopedFdCloser fd_closer(&fd);
+
+ Graph graph;
+ vector<Block> blocks(image_size / block_size);
+ off_t data_file_size;
+ EXPECT_TRUE(Metadata::DeltaReadMetadata(&graph,
+ &blocks,
+ a_img,
+ b_img,
+ fd,
+ &data_file_size));
+
+ // There are 12 metadata that we look for:
+ // - Block group 0 metadata (superblock, group descriptor, bitmaps, etc)
+ // - Chunk 0, 1, 2, 3
+ // - Block group 1 metadata
+ // - Chunk 0, 1, 2, 3
+ // - Root directory (inode 2)
+ // - Journal (inode 8)
+ // - lost+found directory (inode 11)
+ // - test_file indirect block (inode 12)
+ struct {
+ string metadata_name;
+ off_t start_block; // Set to -1 to skip start block verification
+ off_t num_blocks; // Set to -1 to skip num blocks verification
+ } exp_results[] =
+ {{"<rootfs-bg-0-0-metadata>", 0, 104},
+ {"<rootfs-bg-0-1-metadata>", 104, 104},
+ {"<rootfs-bg-0-2-metadata>", 208, 104},
+ {"<rootfs-bg-0-3-metadata>", 312, 104},
+ {"<rootfs-bg-0-4-metadata>", 416, 104},
+ {"<rootfs-bg-0-5-metadata>", 520, 104},
+ {"<rootfs-bg-0-6-metadata>", 624, 104},
+ {"<rootfs-bg-0-7-metadata>", 728, 104},
+ {"<rootfs-bg-0-8-metadata>", 832, 104},
+ {"<rootfs-bg-0-9-metadata>", 936, 107},
+ {"<rootfs-bg-1-0-metadata>", 32768, 104},
+ {"<rootfs-bg-1-1-metadata>", 32872, 104},
+ {"<rootfs-bg-1-2-metadata>", 32976, 104},
+ {"<rootfs-bg-1-3-metadata>", 33080, 104},
+ {"<rootfs-bg-1-4-metadata>", 33184, 104},
+ {"<rootfs-bg-1-5-metadata>", 33288, 104},
+ {"<rootfs-bg-1-6-metadata>", 33392, 104},
+ {"<rootfs-bg-1-7-metadata>", 33496, 104},
+ {"<rootfs-bg-1-8-metadata>", 33600, 104},
+ {"<rootfs-bg-1-9-metadata>", 33704, 107},
+ {"<rootfs-inode-2-metadata>", -1, 1},
+ {"<rootfs-inode-8-metadata>", -1, 4101},
+ {"<rootfs-inode-11-metadata>", -1, 4},
+ {"<rootfs-inode-12-metadata>", -1, 1}};
+
+ int num_exp_results = sizeof(exp_results) / sizeof(exp_results[0]);
+ EXPECT_EQ(graph.size(), num_exp_results);
+
+ for (int i = 0; i < num_exp_results; i++) {
+ Vertex& vertex = graph[i];
+ DeltaArchiveManifest_InstallOperation& op = vertex.op;
+
+ EXPECT_STRCASEEQ(vertex.file_name.c_str(),
+ exp_results[i].metadata_name.c_str());
+
+ EXPECT_EQ(op.src_extents().size(), op.dst_extents().size());
+ for (int e = 0; e < op.src_extents().size(); e++) {
+ EXPECT_EQ(op.src_extents(e).start_block(),
+ op.dst_extents(e).start_block());
+ EXPECT_EQ(op.src_extents(e).num_blocks(),
+ op.dst_extents(e).num_blocks());
+ }
+
+ if (exp_results[i].start_block != -1) {
+ EXPECT_EQ(op.src_extents(0).start_block(), exp_results[i].start_block);
+ }
+
+ if (exp_results[i].num_blocks != -1) {
+ EXPECT_EQ(op.src_extents(0).num_blocks(), exp_results[i].num_blocks);
+ }
+ }
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/tarjan.cc b/payload_generator/tarjan.cc
new file mode 100644
index 0000000..f3029c1
--- /dev/null
+++ b/payload_generator/tarjan.cc
@@ -0,0 +1,71 @@
+// 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/payload_generator/tarjan.h"
+
+#include <algorithm>
+#include <vector>
+
+#include <base/logging.h>
+
+#include "update_engine/utils.h"
+
+using std::min;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+const vector<Vertex>::size_type kInvalidIndex = -1;
+}
+
+void TarjanAlgorithm::Execute(Vertex::Index vertex,
+ Graph* graph,
+ vector<Vertex::Index>* out) {
+ stack_.clear();
+ components_.clear();
+ index_ = 0;
+ for (Graph::iterator it = graph->begin(); it != graph->end(); ++it)
+ it->index = it->lowlink = kInvalidIndex;
+ required_vertex_ = vertex;
+
+ Tarjan(vertex, graph);
+ if (!components_.empty())
+ out->swap(components_[0]);
+}
+
+void TarjanAlgorithm::Tarjan(Vertex::Index vertex, Graph* graph) {
+ CHECK_EQ((*graph)[vertex].index, kInvalidIndex);
+ (*graph)[vertex].index = index_;
+ (*graph)[vertex].lowlink = index_;
+ index_++;
+ stack_.push_back(vertex);
+ for (Vertex::EdgeMap::iterator it = (*graph)[vertex].out_edges.begin();
+ it != (*graph)[vertex].out_edges.end(); ++it) {
+ Vertex::Index vertex_next = it->first;
+ if ((*graph)[vertex_next].index == kInvalidIndex) {
+ Tarjan(vertex_next, graph);
+ (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
+ (*graph)[vertex_next].lowlink);
+ } else if (utils::VectorContainsValue(stack_, vertex_next)) {
+ (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
+ (*graph)[vertex_next].index);
+ }
+ }
+ if ((*graph)[vertex].lowlink == (*graph)[vertex].index) {
+ vector<Vertex::Index> component;
+ Vertex::Index other_vertex;
+ do {
+ other_vertex = stack_.back();
+ stack_.pop_back();
+ component.push_back(other_vertex);
+ } while (other_vertex != vertex && !stack_.empty());
+
+ if (utils::VectorContainsValue(component, required_vertex_)) {
+ components_.resize(components_.size() + 1);
+ component.swap(components_.back());
+ }
+ }
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/tarjan.h b/payload_generator/tarjan.h
new file mode 100644
index 0000000..544cee3
--- /dev/null
+++ b/payload_generator/tarjan.h
@@ -0,0 +1,40 @@
+// 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_PAYLOAD_GENERATOR_TARJAN_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
+
+// This is an implemenation of Tarjan's algorithm which finds all
+// Strongly Connected Components in a graph.
+
+// Note: a true Tarjan algorithm would find all strongly connected components
+// in the graph. This implementation will only find the strongly connected
+// component containing the vertex passed in.
+
+#include <vector>
+
+#include "update_engine/payload_generator/graph_types.h"
+
+namespace chromeos_update_engine {
+
+class TarjanAlgorithm {
+ public:
+ TarjanAlgorithm() : index_(0), required_vertex_(0) {}
+
+ // 'out' is set to the result if there is one, otherwise it's untouched.
+ void Execute(Vertex::Index vertex,
+ Graph* graph,
+ std::vector<Vertex::Index>* out);
+ private:
+ void Tarjan(Vertex::Index vertex, Graph* graph);
+
+ Vertex::Index index_;
+ Vertex::Index required_vertex_;
+ std::vector<Vertex::Index> stack_;
+ std::vector<std::vector<Vertex::Index> > components_;
+};
+
+} // namespace chromeos_update_engine
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
diff --git a/payload_generator/tarjan_unittest.cc b/payload_generator/tarjan_unittest.cc
new file mode 100644
index 0000000..a5fbac2
--- /dev/null
+++ b/payload_generator/tarjan_unittest.cc
@@ -0,0 +1,83 @@
+// 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/payload_generator/tarjan.h"
+
+#include <utility>
+
+#include <base/logging.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::pair;
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class TarjanAlgorithmTest : public ::testing::Test {};
+
+TEST(TarjanAlgorithmTest, SimpleTest) {
+ const Vertex::Index n_a = 0;
+ const Vertex::Index n_b = 1;
+ const Vertex::Index n_c = 2;
+ const Vertex::Index n_d = 3;
+ const Vertex::Index n_e = 4;
+ const Vertex::Index n_f = 5;
+ const Vertex::Index n_g = 6;
+ const Vertex::Index n_h = 7;
+ const Graph::size_type kNodeCount = 8;
+
+ Graph graph(kNodeCount);
+
+ graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties()));
+ graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties()));
+ graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
+ graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties()));
+ graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties()));
+ graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties()));
+ graph[n_f].out_edges.insert(make_pair(n_g, EdgeProperties()));
+ graph[n_g].out_edges.insert(make_pair(n_h, EdgeProperties()));
+ graph[n_h].out_edges.insert(make_pair(n_g, EdgeProperties()));
+
+ TarjanAlgorithm tarjan;
+
+ for (Vertex::Index i = n_a; i <= n_e; i++) {
+ vector<Vertex::Index> vertex_indexes;
+ tarjan.Execute(i, &graph, &vertex_indexes);
+
+ EXPECT_EQ(5, vertex_indexes.size());
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_a));
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_b));
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_c));
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_d));
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_e));
+ }
+
+ {
+ vector<Vertex::Index> vertex_indexes;
+ tarjan.Execute(n_f, &graph, &vertex_indexes);
+
+ EXPECT_EQ(1, vertex_indexes.size());
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_f));
+ }
+
+ for (Vertex::Index i = n_g; i <= n_h; i++) {
+ vector<Vertex::Index> vertex_indexes;
+ tarjan.Execute(i, &graph, &vertex_indexes);
+
+ EXPECT_EQ(2, vertex_indexes.size());
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_g));
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_h));
+ }
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/topological_sort.cc b/payload_generator/topological_sort.cc
new file mode 100644
index 0000000..3ee8c75
--- /dev/null
+++ b/payload_generator/topological_sort.cc
@@ -0,0 +1,44 @@
+// 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/payload_generator/topological_sort.h"
+
+#include <set>
+#include <vector>
+
+#include <base/logging.h>
+
+using std::set;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+void TopologicalSortVisit(const Graph& graph,
+ set<Vertex::Index>* visited_nodes,
+ vector<Vertex::Index>* nodes,
+ Vertex::Index node) {
+ if (visited_nodes->find(node) != visited_nodes->end())
+ return;
+
+ visited_nodes->insert(node);
+ // Visit all children.
+ for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin();
+ it != graph[node].out_edges.end(); ++it) {
+ TopologicalSortVisit(graph, visited_nodes, nodes, it->first);
+ }
+ // Visit this node.
+ nodes->push_back(node);
+}
+} // namespace {}
+
+void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) {
+ set<Vertex::Index> visited_nodes;
+
+ for (Vertex::Index i = 0; i < graph.size(); i++) {
+ TopologicalSortVisit(graph, &visited_nodes, out, i);
+ }
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/topological_sort.h b/payload_generator/topological_sort.h
new file mode 100644
index 0000000..be130ce
--- /dev/null
+++ b/payload_generator/topological_sort.h
@@ -0,0 +1,30 @@
+// 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_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
+
+#include <vector>
+
+#include "update_engine/payload_generator/graph_types.h"
+
+namespace chromeos_update_engine {
+
+// Performs a topological sort on the directed graph 'graph' and stores
+// the nodes, in order visited, in 'out'.
+// For example, this graph:
+// A ---> C ----.
+// \ v
+// `--> B --> D
+// Might result in this in 'out':
+// out[0] = D
+// out[1] = B
+// out[2] = C
+// out[3] = A
+// Note: results are undefined if there is a cycle in the graph.
+void TopologicalSort(const Graph& graph, std::vector<Vertex::Index>* out);
+
+} // namespace chromeos_update_engine
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
diff --git a/payload_generator/topological_sort_unittest.cc b/payload_generator/topological_sort_unittest.cc
new file mode 100644
index 0000000..696fd5b
--- /dev/null
+++ b/payload_generator/topological_sort_unittest.cc
@@ -0,0 +1,82 @@
+// 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 <utility>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/topological_sort.h"
+
+using std::make_pair;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class TopologicalSortTest : public ::testing::Test {};
+
+namespace {
+// Returns true if the value is found in vect. If found, the index is stored
+// in out_index if out_index is not null.
+template<typename T>
+bool IndexOf(const vector<T>& vect,
+ const T& value,
+ typename vector<T>::size_type* out_index) {
+ for (typename vector<T>::size_type i = 0; i < vect.size(); i++) {
+ if (vect[i] == value) {
+ if (out_index) {
+ *out_index = i;
+ }
+ return true;
+ }
+ }
+ return false;
+}
+} // namespace {}
+
+TEST(TopologicalSortTest, SimpleTest) {
+ int counter = 0;
+ const Vertex::Index n_a = counter++;
+ const Vertex::Index n_b = counter++;
+ const Vertex::Index n_c = counter++;
+ const Vertex::Index n_d = counter++;
+ const Vertex::Index n_e = counter++;
+ const Vertex::Index n_f = counter++;
+ const Vertex::Index n_g = counter++;
+ const Vertex::Index n_h = counter++;
+ const Vertex::Index n_i = counter++;
+ const Vertex::Index n_j = counter++;
+ const Graph::size_type kNodeCount = counter++;
+
+ Graph graph(kNodeCount);
+
+ graph[n_i].out_edges.insert(make_pair(n_j, EdgeProperties()));
+ graph[n_i].out_edges.insert(make_pair(n_c, EdgeProperties()));
+ graph[n_i].out_edges.insert(make_pair(n_e, EdgeProperties()));
+ graph[n_i].out_edges.insert(make_pair(n_h, EdgeProperties()));
+ graph[n_c].out_edges.insert(make_pair(n_b, EdgeProperties()));
+ graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_d, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_g, EdgeProperties()));
+ graph[n_g].out_edges.insert(make_pair(n_d, EdgeProperties()));
+ graph[n_g].out_edges.insert(make_pair(n_f, EdgeProperties()));
+ graph[n_d].out_edges.insert(make_pair(n_a, EdgeProperties()));
+
+ vector<Vertex::Index> sorted;
+ TopologicalSort(graph, &sorted);
+
+ for (Vertex::Index i = 0; i < graph.size(); i++) {
+ vector<Vertex::Index>::size_type src_index = 0;
+ EXPECT_TRUE(IndexOf(sorted, i, &src_index));
+ for (Vertex::EdgeMap::const_iterator it = graph[i].out_edges.begin();
+ it != graph[i].out_edges.end(); ++it) {
+ vector<Vertex::Index>::size_type dst_index = 0;
+ EXPECT_TRUE(IndexOf(sorted, it->first, &dst_index));
+ EXPECT_LT(dst_index, src_index);
+ }
+ }
+}
+
+} // namespace chromeos_update_engine
