Merge remote-tracking branch 'aosp/upstream-master' into merge
It's a merge from chrome OS with some reverts.
1. the fd watcher change, because the libbrillo version isn't
compatible in aosp.
commit 6955bcc4ffe4cc9d62a88186b9a7e75d095a7897
commit 493fecb3f48c8478fd3ef244d631d857730dd14d
2. two libcurl unittest. Because the RunOnce() of the fake message
loop seems to have different behavior in aosp.
commit d3d84218cafbc1a95e7d6bbb775b495d1bebf4d2
Put preprocessor guards to use the old code in aosp. And we can
switch to the new code in the other path after adopting the new
libbrillo & libchrome.
Test: unit tests pass, apply an OTA
Change-Id: Id613599834b0f44f92841dbeae6303601db5490d
diff --git a/payload_generator/ab_generator_unittest.cc b/payload_generator/ab_generator_unittest.cc
index 270657a..7a95284 100644
--- a/payload_generator/ab_generator_unittest.cc
+++ b/payload_generator/ab_generator_unittest.cc
@@ -30,10 +30,10 @@
#include "update_engine/common/test_utils.h"
#include "update_engine/common/utils.h"
#include "update_engine/payload_generator/annotated_operation.h"
-#include "update_engine/payload_generator/bzip.h"
#include "update_engine/payload_generator/delta_diff_generator.h"
#include "update_engine/payload_generator/extent_ranges.h"
#include "update_engine/payload_generator/extent_utils.h"
+#include "update_engine/payload_generator/xz.h"
using std::string;
using std::vector;
@@ -48,8 +48,8 @@
return ext.start_block() == start_block && ext.num_blocks() == num_blocks;
}
-// Tests splitting of a REPLACE/REPLACE_BZ operation.
-void TestSplitReplaceOrReplaceBzOperation(InstallOperation::Type orig_type,
+// Tests splitting of a REPLACE/REPLACE_XZ operation.
+void TestSplitReplaceOrReplaceXzOperation(InstallOperation::Type orig_type,
bool compressible) {
const size_t op_ex1_start_block = 2;
const size_t op_ex1_num_blocks = 2;
@@ -71,7 +71,7 @@
}
ASSERT_EQ(part_size, part_data.size());
test_utils::ScopedTempFile part_file(
- "SplitReplaceOrReplaceBzTest_part.XXXXXX");
+ "SplitReplaceOrReplaceXzTest_part.XXXXXX");
ASSERT_TRUE(test_utils::WriteFileVector(part_file.path(), part_data));
// Create original operation and blob data.
@@ -97,7 +97,7 @@
if (orig_type == InstallOperation::REPLACE) {
op_blob = op_data;
} else {
- ASSERT_TRUE(BzipCompress(op_data, &op_blob));
+ ASSERT_TRUE(XzCompress(op_data, &op_blob));
}
op.set_data_offset(0);
op.set_data_length(op_blob.size());
@@ -108,7 +108,7 @@
// Create the data file.
test_utils::ScopedTempFile data_file(
- "SplitReplaceOrReplaceBzTest_data.XXXXXX");
+ "SplitReplaceOrReplaceXzTest_data.XXXXXX");
EXPECT_TRUE(test_utils::WriteFileVector(data_file.path(), op_blob));
int data_fd = open(data_file.path().c_str(), O_RDWR, 000);
EXPECT_GE(data_fd, 0);
@@ -118,14 +118,14 @@
// Split the operation.
vector<AnnotatedOperation> result_ops;
- PayloadVersion version(kChromeOSMajorPayloadVersion,
+ PayloadVersion version(kBrilloMajorPayloadVersion,
kSourceMinorPayloadVersion);
ASSERT_TRUE(ABGenerator::SplitAReplaceOp(
version, aop, part_file.path(), &result_ops, &blob_file));
// Check the result.
InstallOperation::Type expected_type =
- compressible ? InstallOperation::REPLACE_BZ : InstallOperation::REPLACE;
+ compressible ? InstallOperation::REPLACE_XZ : InstallOperation::REPLACE;
ASSERT_EQ(2U, result_ops.size());
@@ -143,7 +143,7 @@
part_data.begin() + op_ex1_offset + op_ex1_size);
brillo::Blob first_expected_blob;
if (compressible) {
- ASSERT_TRUE(BzipCompress(first_expected_data, &first_expected_blob));
+ ASSERT_TRUE(XzCompress(first_expected_data, &first_expected_blob));
} else {
first_expected_blob = first_expected_data;
}
@@ -173,7 +173,7 @@
part_data.begin() + op_ex2_offset + op_ex2_size);
brillo::Blob second_expected_blob;
if (compressible) {
- ASSERT_TRUE(BzipCompress(second_expected_data, &second_expected_blob));
+ ASSERT_TRUE(XzCompress(second_expected_data, &second_expected_blob));
} else {
second_expected_blob = second_expected_data;
}
@@ -199,8 +199,8 @@
}
}
-// Tests merging of REPLACE/REPLACE_BZ operations.
-void TestMergeReplaceOrReplaceBzOperations(InstallOperation::Type orig_type,
+// Tests merging of REPLACE/REPLACE_XZ operations.
+void TestMergeReplaceOrReplaceXzOperations(InstallOperation::Type orig_type,
bool compressible) {
const size_t first_op_num_blocks = 1;
const size_t second_op_num_blocks = 2;
@@ -221,7 +221,7 @@
}
ASSERT_EQ(part_size, part_data.size());
test_utils::ScopedTempFile part_file(
- "MergeReplaceOrReplaceBzTest_part.XXXXXX");
+ "MergeReplaceOrReplaceXzTest_part.XXXXXX");
ASSERT_TRUE(test_utils::WriteFileVector(part_file.path(), part_data));
// Create original operations and blob data.
@@ -239,7 +239,7 @@
if (orig_type == InstallOperation::REPLACE) {
first_op_blob = first_op_data;
} else {
- ASSERT_TRUE(BzipCompress(first_op_data, &first_op_blob));
+ ASSERT_TRUE(XzCompress(first_op_data, &first_op_blob));
}
first_op.set_data_offset(0);
first_op.set_data_length(first_op_blob.size());
@@ -259,7 +259,7 @@
if (orig_type == InstallOperation::REPLACE) {
second_op_blob = second_op_data;
} else {
- ASSERT_TRUE(BzipCompress(second_op_data, &second_op_blob));
+ ASSERT_TRUE(XzCompress(second_op_data, &second_op_blob));
}
second_op.set_data_offset(first_op_blob.size());
second_op.set_data_length(second_op_blob.size());
@@ -272,7 +272,7 @@
// Create the data file.
test_utils::ScopedTempFile data_file(
- "MergeReplaceOrReplaceBzTest_data.XXXXXX");
+ "MergeReplaceOrReplaceXzTest_data.XXXXXX");
EXPECT_TRUE(test_utils::WriteFileVector(data_file.path(), blob_data));
int data_fd = open(data_file.path().c_str(), O_RDWR, 000);
EXPECT_GE(data_fd, 0);
@@ -281,14 +281,14 @@
BlobFileWriter blob_file(data_fd, &data_file_size);
// Merge the operations.
- PayloadVersion version(kChromeOSMajorPayloadVersion,
+ PayloadVersion version(kBrilloMajorPayloadVersion,
kSourceMinorPayloadVersion);
EXPECT_TRUE(ABGenerator::MergeOperations(
&aops, version, 5, part_file.path(), &blob_file));
// Check the result.
InstallOperation::Type expected_op_type =
- compressible ? InstallOperation::REPLACE_BZ : InstallOperation::REPLACE;
+ compressible ? InstallOperation::REPLACE_XZ : InstallOperation::REPLACE;
EXPECT_EQ(1U, aops.size());
InstallOperation new_op = aops[0].op;
EXPECT_EQ(expected_op_type, new_op.type());
@@ -303,7 +303,7 @@
part_data.begin() + total_op_size);
brillo::Blob expected_blob;
if (compressible) {
- ASSERT_TRUE(BzipCompress(expected_data, &expected_blob));
+ ASSERT_TRUE(XzCompress(expected_data, &expected_blob));
} else {
expected_blob = expected_data;
}
@@ -384,19 +384,19 @@
}
TEST_F(ABGeneratorTest, SplitReplaceTest) {
- TestSplitReplaceOrReplaceBzOperation(InstallOperation::REPLACE, false);
+ TestSplitReplaceOrReplaceXzOperation(InstallOperation::REPLACE, false);
}
-TEST_F(ABGeneratorTest, SplitReplaceIntoReplaceBzTest) {
- TestSplitReplaceOrReplaceBzOperation(InstallOperation::REPLACE, true);
+TEST_F(ABGeneratorTest, SplitReplaceIntoReplaceXzTest) {
+ TestSplitReplaceOrReplaceXzOperation(InstallOperation::REPLACE, true);
}
-TEST_F(ABGeneratorTest, SplitReplaceBzTest) {
- TestSplitReplaceOrReplaceBzOperation(InstallOperation::REPLACE_BZ, true);
+TEST_F(ABGeneratorTest, SplitReplaceXzTest) {
+ TestSplitReplaceOrReplaceXzOperation(InstallOperation::REPLACE_XZ, true);
}
-TEST_F(ABGeneratorTest, SplitReplaceBzIntoReplaceTest) {
- TestSplitReplaceOrReplaceBzOperation(InstallOperation::REPLACE_BZ, false);
+TEST_F(ABGeneratorTest, SplitReplaceXzIntoReplaceTest) {
+ TestSplitReplaceOrReplaceXzOperation(InstallOperation::REPLACE_XZ, false);
}
TEST_F(ABGeneratorTest, SortOperationsByDestinationTest) {
@@ -464,7 +464,7 @@
aops.push_back(third_aop);
BlobFileWriter blob_file(0, nullptr);
- PayloadVersion version(kChromeOSMajorPayloadVersion,
+ PayloadVersion version(kBrilloMajorPayloadVersion,
kSourceMinorPayloadVersion);
EXPECT_TRUE(ABGenerator::MergeOperations(&aops, version, 5, "", &blob_file));
@@ -484,19 +484,19 @@
}
TEST_F(ABGeneratorTest, MergeReplaceOperationsTest) {
- TestMergeReplaceOrReplaceBzOperations(InstallOperation::REPLACE, false);
+ TestMergeReplaceOrReplaceXzOperations(InstallOperation::REPLACE, false);
}
-TEST_F(ABGeneratorTest, MergeReplaceOperationsToReplaceBzTest) {
- TestMergeReplaceOrReplaceBzOperations(InstallOperation::REPLACE, true);
+TEST_F(ABGeneratorTest, MergeReplaceOperationsToReplaceXzTest) {
+ TestMergeReplaceOrReplaceXzOperations(InstallOperation::REPLACE, true);
}
-TEST_F(ABGeneratorTest, MergeReplaceBzOperationsTest) {
- TestMergeReplaceOrReplaceBzOperations(InstallOperation::REPLACE_BZ, true);
+TEST_F(ABGeneratorTest, MergeReplaceXzOperationsTest) {
+ TestMergeReplaceOrReplaceXzOperations(InstallOperation::REPLACE_XZ, true);
}
-TEST_F(ABGeneratorTest, MergeReplaceBzOperationsToReplaceTest) {
- TestMergeReplaceOrReplaceBzOperations(InstallOperation::REPLACE_BZ, false);
+TEST_F(ABGeneratorTest, MergeReplaceXzOperationsToReplaceTest) {
+ TestMergeReplaceOrReplaceXzOperations(InstallOperation::REPLACE_XZ, false);
}
TEST_F(ABGeneratorTest, NoMergeOperationsTest) {
@@ -537,7 +537,7 @@
aops.push_back(fourth_aop);
BlobFileWriter blob_file(0, nullptr);
- PayloadVersion version(kChromeOSMajorPayloadVersion,
+ PayloadVersion version(kBrilloMajorPayloadVersion,
kSourceMinorPayloadVersion);
EXPECT_TRUE(ABGenerator::MergeOperations(&aops, version, 4, "", &blob_file));
diff --git a/payload_generator/cycle_breaker.cc b/payload_generator/cycle_breaker.cc
deleted file mode 100644
index d6eeed2..0000000
--- a/payload_generator/cycle_breaker.cc
+++ /dev/null
@@ -1,218 +0,0 @@
-//
-// Copyright (C) 2012 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/cycle_breaker.h"
-
-#include <inttypes.h>
-
-#include <limits>
-#include <set>
-#include <string>
-#include <utility>
-
-#include <base/stl_util.h>
-#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"
-
-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++) {
- InstallOperation::Type op_type = graph[i].aop.op.type();
- if (op_type == InstallOperation::REPLACE ||
- op_type == InstallOperation::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 (base::ContainsKey(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<vector<Vertex::Index>::size_type>(2));
- Edge min_edge = make_pair(stack_[0], stack_[1]);
- uint64_t min_edge_weight = std::numeric_limits<uint64_t>::max();
- 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 (vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
- e = stack_.end();
- it != e;
- ++it) {
- Edge edge = make_pair(*(it - 1), *it);
- if (base::ContainsKey(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 (Vertex::Index index : stack_) {
- stack_str += std::to_string(index);
- stack_str += " -> ";
- }
- 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
deleted file mode 100644
index 01518fe..0000000
--- a/payload_generator/cycle_breaker.h
+++ /dev/null
@@ -1,71 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
-#define 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 // UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
diff --git a/payload_generator/cycle_breaker_unittest.cc b/payload_generator/cycle_breaker_unittest.cc
deleted file mode 100644
index fdcf49b..0000000
--- a/payload_generator/cycle_breaker_unittest.cc
+++ /dev/null
@@ -1,279 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/cycle_breaker.h"
-
-#include <set>
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/logging.h>
-#include <base/stl_util.h>
-#include <gtest/gtest.h>
-
-#include "update_engine/payload_generator/graph_types.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 (Vertex& vertex : *graph) {
- vertex.aop.op.set_type(InstallOperation::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(base::ContainsKey(broken_edges, make_pair(n_a, n_e)) ||
- base::ContainsKey(broken_edges, make_pair(n_e, n_b)) ||
- base::ContainsKey(broken_edges, make_pair(n_b, n_a)));
- EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_c, n_d)) ||
- base::ContainsKey(broken_edges, make_pair(n_d, n_e)) ||
- base::ContainsKey(broken_edges, make_pair(n_e, n_c)));
- EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_g, n_h)) ||
- base::ContainsKey(broken_edges, make_pair(n_h, n_g)));
- EXPECT_EQ(3U, 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) {
- size_t 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) {
- size_t 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(base::ContainsKey(broken_edges, make_pair(n_b, n_a)));
- EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_b, n_c)));
- EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_d, n_e)));
- EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_f, n_g)));
- EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_h, n_i)));
-}
-
-TEST(CycleBreakerTest, UnblockGraphTest) {
- size_t 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(base::ContainsKey(broken_edges, make_pair(n_a, n_b)));
- EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_a, n_c)));
-}
-
-TEST(CycleBreakerTest, SkipOpsTest) {
- size_t 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].aop.op.set_type(InstallOperation::REPLACE_BZ);
- graph[n_c].aop.op.set_type(InstallOperation::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(2U, breaker.skipped_ops());
-}
-
-} // namespace chromeos_update_engine
diff --git a/payload_generator/deflate_utils.cc b/payload_generator/deflate_utils.cc
index 01402dd..c874bfd 100644
--- a/payload_generator/deflate_utils.cc
+++ b/payload_generator/deflate_utils.cc
@@ -46,7 +46,7 @@
// TODO(*): Optimize this so we don't have to read all extents into memory in
// case it is large.
bool CopyExtentsToFile(const string& in_path,
- const vector<Extent> extents,
+ const vector<Extent>& extents,
const string& out_path,
size_t block_size) {
brillo::Blob data(utils::BlocksInExtents(extents) * block_size);
@@ -284,8 +284,9 @@
TEST_AND_RETURN_FALSE(
CopyExtentsToFile(part.path, file.extents, path.value(), kBlockSize));
// Test if it is actually a Squashfs file.
- auto sqfs =
- SquashfsFilesystem::CreateFromFile(path.value(), extract_deflates);
+ auto sqfs = SquashfsFilesystem::CreateFromFile(path.value(),
+ extract_deflates,
+ /*load_settings=*/false);
if (sqfs) {
// It is an squashfs file. Get its files to replace with itself.
vector<FilesystemInterface::File> files;
@@ -306,7 +307,7 @@
}
}
- if (is_regular_file && extract_deflates) {
+ if (is_regular_file && extract_deflates && !file.is_compressed) {
// Search for deflates if the file is in zip or gzip format.
// .zvoice files may eventually move out of rootfs. If that happens,
// remove ".zvoice" (crbug.com/782918).
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index d484d32..595a41e 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -37,7 +37,6 @@
#include "update_engine/payload_generator/blob_file_writer.h"
#include "update_engine/payload_generator/delta_diff_utils.h"
#include "update_engine/payload_generator/full_update_generator.h"
-#include "update_engine/payload_generator/inplace_generator.h"
#include "update_engine/payload_generator/payload_file.h"
using std::string;
@@ -93,13 +92,8 @@
unique_ptr<OperationsGenerator> strategy;
if (!old_part.path.empty()) {
// Delta update.
- if (config.version.minor == kInPlaceMinorPayloadVersion) {
- LOG(INFO) << "Using generator InplaceGenerator().";
- strategy.reset(new InplaceGenerator());
- } else {
- LOG(INFO) << "Using generator ABGenerator().";
- strategy.reset(new ABGenerator());
- }
+ LOG(INFO) << "Using generator ABGenerator().";
+ strategy.reset(new ABGenerator());
} else {
LOG(INFO) << "Using generator FullUpdateGenerator().";
strategy.reset(new FullUpdateGenerator());
@@ -110,11 +104,6 @@
TEST_AND_RETURN_FALSE(strategy->GenerateOperations(
config, old_part, new_part, &blob_file, &aops));
- // Filter the no-operations. OperationsGenerators should not output this
- // kind of operations normally, but this is an extra step to fix that if
- // happened.
- diff_utils::FilterNoopOperations(&aops);
-
TEST_AND_RETURN_FALSE(payload.AddPartition(old_part, new_part, aops));
}
}
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
index 4ba6e24..22752e8 100644
--- a/payload_generator/delta_diff_utils.cc
+++ b/payload_generator/delta_diff_utils.cc
@@ -83,103 +83,6 @@
const int kBrotliCompressionQuality = 11;
-// 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;
- size_t removed_bytes = 0, nonfull_block_bytes;
- bool do_remove = false;
- while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) {
- 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 =
- std::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;
-
- bool new_src = ProcessExtentBlockRange(
- src_extents, &src_idx, do_remove, prev_src_offset, src_offset);
- bool new_dst = ProcessExtentBlockRange(
- dst_extents, &dst_idx, do_remove, prev_dst_offset, dst_offset);
- if (new_src) {
- src_offset = 0;
- }
- if (new_dst) {
- dst_offset = 0;
- }
-
- 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;
-}
-
// Storing a diff operation has more overhead over replace operation in the
// manifest, we need to store an additional src_sha256_hash which is 32 bytes
// and not compressible, and also src_extents which could use anywhere from a
@@ -318,13 +221,11 @@
return;
}
- if (!version_.InplaceUpdate()) {
- if (!ABGenerator::FragmentOperations(
- version_, &file_aops_, new_part_, blob_file_)) {
- LOG(ERROR) << "Failed to fragment operations for " << name_;
- failed_ = true;
- return;
- }
+ if (!ABGenerator::FragmentOperations(
+ version_, &file_aops_, new_part_, blob_file_)) {
+ LOG(ERROR) << "Failed to fragment operations for " << name_;
+ failed_ = true;
+ return;
}
LOG(INFO) << "Encoded file " << name_ << " (" << new_extents_blocks_
@@ -349,12 +250,13 @@
if (old_file_iter != old_files_map.end())
return old_file_iter->second;
- // No old file match for the new file name, use a similar file with the
- // shortest levenshtein distance.
+ // No old file matches the new file name. Use a similar file with the
+ // shortest levenshtein distance instead.
// This works great if the file has version number in it, but even for
// a completely new file, using a similar file can still help.
- int min_distance = new_file_name.size();
- const FilesystemInterface::File* old_file;
+ int min_distance =
+ LevenshteinDistance(new_file_name, old_files_map.begin()->first);
+ const FilesystemInterface::File* old_file = &old_files_map.begin()->second;
for (const auto& pair : old_files_map) {
int distance = LevenshteinDistance(new_file_name, pair.first);
if (distance < min_distance) {
@@ -447,12 +349,8 @@
// from the same source blocks. At that time, this code can die. -adlr
FilesystemInterface::File old_file =
GetOldFile(old_files_map, new_file.name);
- vector<Extent> old_file_extents;
- if (version.InplaceUpdate())
- old_file_extents =
- FilterExtentRanges(old_file.extents, old_visited_blocks);
- else
- old_file_extents = FilterExtentRanges(old_file.extents, old_zero_blocks);
+ auto old_file_extents =
+ FilterExtentRanges(old_file.extents, old_zero_blocks);
old_visited_blocks.AddExtents(old_file_extents);
file_delta_processors.emplace_back(old_part.path,
@@ -541,21 +439,6 @@
&old_block_ids,
&new_block_ids));
- // If the update is inplace, we map all the blocks that didn't move,
- // regardless of the contents since they are already copied and no operation
- // is required.
- if (version.InplaceUpdate()) {
- uint64_t num_blocks = std::min(old_num_blocks, new_num_blocks);
- for (uint64_t block = 0; block < num_blocks; block++) {
- if (old_block_ids[block] == new_block_ids[block] &&
- !old_visited_blocks->ContainsBlock(block) &&
- !new_visited_blocks->ContainsBlock(block)) {
- old_visited_blocks->AddBlock(block);
- new_visited_blocks->AddBlock(block);
- }
- }
- }
-
// A mapping from the block_id to the list of block numbers with that block id
// in the old partition. This is used to lookup where in the old partition
// is a block from the new partition.
@@ -602,10 +485,6 @@
AppendBlockToExtents(&old_identical_blocks,
old_blocks_map_it->second.back());
AppendBlockToExtents(&new_identical_blocks, block);
- // We can't reuse source blocks in minor version 1 because the cycle
- // breaking algorithm used in the in-place update doesn't support that.
- if (version.InplaceUpdate())
- old_blocks_map_it->second.pop_back();
}
if (chunk_blocks == -1)
@@ -657,9 +536,7 @@
aops->emplace_back();
AnnotatedOperation* aop = &aops->back();
aop->name = "<identical-blocks>";
- aop->op.set_type(version.OperationAllowed(InstallOperation::SOURCE_COPY)
- ? InstallOperation::SOURCE_COPY
- : InstallOperation::MOVE);
+ aop->op.set_type(InstallOperation::SOURCE_COPY);
uint64_t chunk_num_blocks =
std::min(static_cast<uint64_t>(extent.num_blocks()) - op_block_offset,
@@ -704,6 +581,11 @@
InstallOperation operation;
uint64_t total_blocks = utils::BlocksInExtents(new_extents);
+ if (chunk_blocks == 0) {
+ LOG(ERROR) << "Invalid number of chunk_blocks. Cannot be 0.";
+ return false;
+ }
+
if (chunk_blocks == -1)
chunk_blocks = total_blocks;
@@ -732,13 +614,8 @@
// Check if the operation writes nothing.
if (operation.dst_extents_size() == 0) {
- if (operation.type() == InstallOperation::MOVE) {
- LOG(INFO) << "Empty MOVE operation (" << name << "), skipping";
- continue;
- } else {
- LOG(ERROR) << "Empty non-MOVE operation";
- return false;
- }
+ LOG(ERROR) << "Empty non-MOVE operation";
+ return false;
}
// Now, insert into the list of operations.
@@ -828,8 +705,7 @@
// Disable bsdiff, and puffdiff when the data is too big.
bool bsdiff_allowed =
- version.OperationAllowed(InstallOperation::SOURCE_BSDIFF) ||
- version.OperationAllowed(InstallOperation::BSDIFF);
+ version.OperationAllowed(InstallOperation::SOURCE_BSDIFF);
if (bsdiff_allowed &&
blocks_to_read * kBlockSize > kMaxBsdiffDestinationSize) {
LOG(INFO) << "bsdiff blacklisted, data too big: "
@@ -878,9 +754,7 @@
kBlockSize));
if (old_data == new_data) {
// No change in data.
- operation.set_type(version.OperationAllowed(InstallOperation::SOURCE_COPY)
- ? InstallOperation::SOURCE_COPY
- : InstallOperation::MOVE);
+ operation.set_type(InstallOperation::SOURCE_COPY);
data_blob = brillo::Blob();
} else if (IsDiffOperationBetter(
operation, data_blob.size(), 0, src_extents.size())) {
@@ -892,7 +766,7 @@
ScopedPathUnlinker unlinker(patch.value());
std::unique_ptr<bsdiff::PatchWriterInterface> bsdiff_patch_writer;
- InstallOperation::Type operation_type = InstallOperation::BSDIFF;
+ InstallOperation::Type operation_type = InstallOperation::SOURCE_BSDIFF;
if (version.OperationAllowed(InstallOperation::BROTLI_BSDIFF)) {
bsdiff_patch_writer =
bsdiff::CreateBSDF2PatchWriter(patch.value(),
@@ -901,9 +775,6 @@
operation_type = InstallOperation::BROTLI_BSDIFF;
} else {
bsdiff_patch_writer = bsdiff::CreateBsdiffPatchWriter(patch.value());
- if (version.OperationAllowed(InstallOperation::SOURCE_BSDIFF)) {
- operation_type = InstallOperation::SOURCE_BSDIFF;
- }
}
brillo::Blob bsdiff_delta;
@@ -976,23 +847,14 @@
}
}
- // Remove identical src/dst block ranges in MOVE operations.
- if (operation.type() == InstallOperation::MOVE) {
- auto removed_bytes =
- RemoveIdenticalBlockRanges(&src_extents, &dst_extents, new_data.size());
- operation.set_src_length(old_data.size() - removed_bytes);
- operation.set_dst_length(new_data.size() - removed_bytes);
- }
-
// WARNING: We always set legacy |src_length| and |dst_length| fields for
// BSDIFF. For SOURCE_BSDIFF we only set them for minor version 3 and
// lower. This is needed because we used to use these two parameters in the
// SOURCE_BSDIFF for minor version 3 and lower, but we do not need them
// anymore in higher minor versions. This means if we stop adding these
// parameters for those minor versions, the delta payloads will be invalid.
- if (operation.type() == InstallOperation::BSDIFF ||
- (operation.type() == InstallOperation::SOURCE_BSDIFF &&
- version.minor <= kOpSrcHashMinorPayloadVersion)) {
+ if (operation.type() == InstallOperation::SOURCE_BSDIFF &&
+ version.minor <= kOpSrcHashMinorPayloadVersion) {
operation.set_src_length(old_data.size());
operation.set_dst_length(new_data.size());
}
@@ -1021,22 +883,6 @@
op_type == InstallOperation::DISCARD);
}
-// 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 IsNoopOperation(const InstallOperation& op) {
- return (op.type() == InstallOperation::MOVE &&
- ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
-}
-
-void FilterNoopOperations(vector<AnnotatedOperation>* ops) {
- ops->erase(std::remove_if(ops->begin(),
- ops->end(),
- [](const AnnotatedOperation& aop) {
- return IsNoopOperation(aop.op);
- }),
- ops->end());
-}
-
bool InitializePartitionInfo(const PartitionConfig& part, PartitionInfo* info) {
info->set_size(part.size);
HashCalculator hasher;
diff --git a/payload_generator/delta_diff_utils.h b/payload_generator/delta_diff_utils.h
index 2211b30..c75d16d 100644
--- a/payload_generator/delta_diff_utils.h
+++ b/payload_generator/delta_diff_utils.h
@@ -127,14 +127,6 @@
// Returns true if an operation with type |op_type| has no |src_extents|.
bool IsNoSourceOperation(InstallOperation::Type op_type);
-// 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 IsNoopOperation(const InstallOperation& op);
-
-// Filters all the operations that are no-op, maintaining the relative order
-// of the rest of the operations.
-void FilterNoopOperations(std::vector<AnnotatedOperation>* ops);
-
bool InitializePartitionInfo(const PartitionConfig& partition,
PartitionInfo* info);
diff --git a/payload_generator/delta_diff_utils_unittest.cc b/payload_generator/delta_diff_utils_unittest.cc
index b2950e8..0857f9c 100644
--- a/payload_generator/delta_diff_utils_unittest.cc
+++ b/payload_generator/delta_diff_utils_unittest.cc
@@ -136,7 +136,7 @@
bool RunDeltaMovedAndZeroBlocks(ssize_t chunk_blocks,
uint32_t minor_version) {
BlobFileWriter blob_file(blob_fd_, &blob_size_);
- PayloadVersion version(kChromeOSMajorPayloadVersion, minor_version);
+ PayloadVersion version(kBrilloMajorPayloadVersion, minor_version);
ExtentRanges old_zero_blocks;
return diff_utils::DeltaMovedAndZeroBlocks(&aops_,
old_part_.path,
@@ -194,164 +194,6 @@
}
}
-TEST_F(DeltaDiffUtilsTest, MoveSmallTest) {
- brillo::Blob data_blob(block_size_);
- test_utils::FillWithData(&data_blob);
-
- // The old file is on a different block than the new one.
- vector<Extent> old_extents = {ExtentForRange(11, 1)};
- vector<Extent> new_extents = {ExtentForRange(1, 1)};
-
- EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
- EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
-
- brillo::Blob data;
- InstallOperation op;
- EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
- old_part_.path,
- new_part_.path,
- old_extents,
- new_extents,
- {}, // old_deflates
- {}, // new_deflates
- PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
- &data,
- &op));
- EXPECT_TRUE(data.empty());
-
- EXPECT_TRUE(op.has_type());
- EXPECT_EQ(InstallOperation::MOVE, op.type());
- EXPECT_FALSE(op.has_data_offset());
- EXPECT_FALSE(op.has_data_length());
- EXPECT_EQ(1, op.src_extents_size());
- EXPECT_EQ(kBlockSize, op.src_length());
- EXPECT_EQ(1, op.dst_extents_size());
- EXPECT_EQ(kBlockSize, op.dst_length());
- EXPECT_EQ(utils::BlocksInExtents(op.src_extents()),
- utils::BlocksInExtents(op.dst_extents()));
- EXPECT_EQ(1U, utils::BlocksInExtents(op.dst_extents()));
-}
-
-TEST_F(DeltaDiffUtilsTest, MoveWithSameBlock) {
- // 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 = {ExtentForRange(20, 6), ExtentForRange(28, 2)};
- vector<Extent> new_extents = {ExtentForRange(18, 1),
- ExtentForRange(21, 2),
- ExtentForRange(20, 1),
- ExtentForRange(24, 3),
- ExtentForRange(29, 1)};
-
- uint64_t num_blocks = utils::BlocksInExtents(old_extents);
- EXPECT_EQ(num_blocks, utils::BlocksInExtents(new_extents));
-
- // The size of the data should match the total number of blocks. Each block
- // has a different content.
- brillo::Blob file_data;
- for (uint64_t i = 0; i < num_blocks; ++i) {
- file_data.resize(file_data.size() + kBlockSize, 'a' + i);
- }
-
- EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, file_data));
- EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, file_data));
-
- brillo::Blob data;
- InstallOperation op;
- EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
- old_part_.path,
- new_part_.path,
- old_extents,
- new_extents,
- {}, // old_deflates
- {}, // new_deflates
- PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
- &data,
- &op));
-
- EXPECT_TRUE(data.empty());
-
- EXPECT_TRUE(op.has_type());
- EXPECT_EQ(InstallOperation::MOVE, op.type());
- EXPECT_FALSE(op.has_data_offset());
- EXPECT_FALSE(op.has_data_length());
-
- // The expected old and new extents that actually moved. See comment above.
- old_extents = {
- ExtentForRange(20, 1), ExtentForRange(23, 1), ExtentForRange(28, 1)};
- new_extents = {
- ExtentForRange(18, 1), ExtentForRange(20, 1), ExtentForRange(26, 1)};
- num_blocks = utils::BlocksInExtents(old_extents);
-
- EXPECT_EQ(num_blocks * kBlockSize, op.src_length());
- EXPECT_EQ(num_blocks * kBlockSize, op.dst_length());
-
- EXPECT_EQ(old_extents.size(), static_cast<size_t>(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(new_extents.size(), static_cast<size_t>(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;
- }
-}
-
-TEST_F(DeltaDiffUtilsTest, BsdiffSmallTest) {
- // Test a BSDIFF operation from block 1 to block 2.
- brillo::Blob data_blob(kBlockSize);
- test_utils::FillWithData(&data_blob);
-
- // The old file is on a different block than the new one.
- vector<Extent> old_extents = {ExtentForRange(1, 1)};
- vector<Extent> new_extents = {ExtentForRange(2, 1)};
-
- EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
- // Modify one byte in the new file.
- data_blob[0]++;
- EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
-
- brillo::Blob data;
- InstallOperation op;
- EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
- old_part_.path,
- new_part_.path,
- old_extents,
- new_extents,
- {}, // old_deflates
- {}, // new_deflates
- PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
- &data,
- &op));
-
- EXPECT_FALSE(data.empty());
-
- EXPECT_TRUE(op.has_type());
- EXPECT_EQ(InstallOperation::BSDIFF, op.type());
- EXPECT_FALSE(op.has_data_offset());
- EXPECT_FALSE(op.has_data_length());
- EXPECT_EQ(1, op.src_extents_size());
- EXPECT_EQ(kBlockSize, op.src_length());
- EXPECT_EQ(1, op.dst_extents_size());
- EXPECT_EQ(kBlockSize, op.dst_length());
- EXPECT_EQ(utils::BlocksInExtents(op.src_extents()),
- utils::BlocksInExtents(op.dst_extents()));
- EXPECT_EQ(1U, utils::BlocksInExtents(op.dst_extents()));
-}
-
TEST_F(DeltaDiffUtilsTest, ReplaceSmallTest) {
// The old file is on a different block than the new one.
vector<Extent> old_extents = {ExtentForRange(1, 1)};
@@ -383,8 +225,7 @@
new_extents,
{}, // old_deflates
{}, // new_deflates
- PayloadVersion(kChromeOSMajorPayloadVersion,
- kInPlaceMinorPayloadVersion),
+ PayloadVersion(kBrilloMajorPayloadVersion, kSourceMinorPayloadVersion),
&data,
&op));
EXPECT_FALSE(data.empty());
@@ -426,7 +267,7 @@
new_extents,
{}, // old_deflates
{}, // new_deflates
- PayloadVersion(kChromeOSMajorPayloadVersion, kSourceMinorPayloadVersion),
+ PayloadVersion(kBrilloMajorPayloadVersion, kSourceMinorPayloadVersion),
&data,
&op));
EXPECT_TRUE(data.empty());
@@ -460,7 +301,7 @@
new_extents,
{}, // old_deflates
{}, // new_deflates
- PayloadVersion(kChromeOSMajorPayloadVersion, kSourceMinorPayloadVersion),
+ PayloadVersion(kBrilloMajorPayloadVersion, kSourceMinorPayloadVersion),
&data,
&op));
@@ -500,49 +341,6 @@
EXPECT_EQ(InstallOperation::REPLACE_BZ, op.type());
}
-TEST_F(DeltaDiffUtilsTest, IsNoopOperationTest) {
- InstallOperation op;
- op.set_type(InstallOperation::REPLACE_BZ);
- EXPECT_FALSE(diff_utils::IsNoopOperation(op));
- op.set_type(InstallOperation::MOVE);
- EXPECT_TRUE(diff_utils::IsNoopOperation(op));
- *(op.add_src_extents()) = ExtentForRange(3, 2);
- *(op.add_dst_extents()) = ExtentForRange(3, 2);
- EXPECT_TRUE(diff_utils::IsNoopOperation(op));
- *(op.add_src_extents()) = ExtentForRange(7, 5);
- *(op.add_dst_extents()) = ExtentForRange(7, 5);
- EXPECT_TRUE(diff_utils::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(diff_utils::IsNoopOperation(op));
- *(op.add_src_extents()) = ExtentForRange(24, 1);
- *(op.add_dst_extents()) = ExtentForRange(25, 1);
- EXPECT_FALSE(diff_utils::IsNoopOperation(op));
-}
-
-TEST_F(DeltaDiffUtilsTest, FilterNoopOperations) {
- AnnotatedOperation aop1;
- aop1.op.set_type(InstallOperation::REPLACE_BZ);
- *(aop1.op.add_dst_extents()) = ExtentForRange(3, 2);
- aop1.name = "aop1";
-
- AnnotatedOperation aop2 = aop1;
- aop2.name = "aop2";
-
- AnnotatedOperation noop;
- noop.op.set_type(InstallOperation::MOVE);
- *(noop.op.add_src_extents()) = ExtentForRange(3, 2);
- *(noop.op.add_dst_extents()) = ExtentForRange(3, 2);
- noop.name = "noop";
-
- vector<AnnotatedOperation> ops = {noop, aop1, noop, noop, aop2, noop};
- diff_utils::FilterNoopOperations(&ops);
- EXPECT_EQ(2u, ops.size());
- EXPECT_EQ("aop1", ops[0].name);
- EXPECT_EQ("aop2", ops[1].name);
-}
-
// Test the simple case where all the blocks are different and no new blocks are
// zeroed.
TEST_F(DeltaDiffUtilsTest, NoZeroedOrUniqueBlocksDetected) {
@@ -550,7 +348,7 @@
InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks
- kInPlaceMinorPayloadVersion));
+ kSourceMinorPayloadVersion));
EXPECT_EQ(0U, old_visited_blocks_.blocks());
EXPECT_EQ(0U, new_visited_blocks_.blocks());
@@ -558,29 +356,6 @@
EXPECT_TRUE(aops_.empty());
}
-// Test that when the partitions have identical blocks in the same positions no
-// MOVE operation is performed and all the blocks are handled.
-TEST_F(DeltaDiffUtilsTest, IdenticalPartitionsDontMove) {
- InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
- InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
-
- // Mark some of the blocks as already visited.
- vector<Extent> already_visited = {ExtentForRange(5, 10),
- ExtentForRange(25, 10)};
- old_visited_blocks_.AddExtents(already_visited);
- new_visited_blocks_.AddExtents(already_visited);
-
- // Most of the blocks rest in the same place, but there's no need for MOVE
- // operations on those blocks.
- EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1, // chunk_blocks
- kInPlaceMinorPayloadVersion));
-
- EXPECT_EQ(kDefaultBlockCount, old_visited_blocks_.blocks());
- EXPECT_EQ(kDefaultBlockCount, new_visited_blocks_.blocks());
- EXPECT_EQ(0, blob_size_);
- EXPECT_TRUE(aops_.empty());
-}
-
// Test that when the partitions have identical blocks in the same positions
// MOVE operation is performed and all the blocks are handled.
TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedFromSource) {
@@ -701,16 +476,14 @@
EXPECT_TRUE(WriteExtents(old_part_.path, old_zeros, block_size_, zeros_data));
EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(5, // chunk_blocks
- kInPlaceMinorPayloadVersion));
+ kSourceMinorPayloadVersion));
- // Zeroed blocks from old_visited_blocks_ were copied over, so me actually
- // use them regardless of the trivial MOVE operation not being emitted.
+ // Zeroed blocks from |old_visited_blocks_| were copied over.
EXPECT_EQ(old_zeros,
old_visited_blocks_.GetExtentsForBlockCount(
old_visited_blocks_.blocks()));
- // All the new zeroed blocks should be used, part with REPLACE_BZ and part
- // trivial MOVE operations (not included).
+ // All the new zeroed blocks should be used with REPLACE_BZ.
EXPECT_EQ(new_zeros,
new_visited_blocks_.GetExtentsForBlockCount(
new_visited_blocks_.blocks()));
@@ -721,7 +494,8 @@
// This range should be split.
ExtentForRange(30, 5),
ExtentForRange(35, 5),
- ExtentForRange(40, 3),
+ ExtentForRange(40, 5),
+ ExtentForRange(45, 5),
};
EXPECT_EQ(expected_op_extents.size(), aops_.size());
@@ -821,6 +595,8 @@
"update_engine");
EXPECT_EQ(diff_utils::GetOldFile(old_files_map, "bin/delta_generator").name,
"delta_generator");
+ // Check file name with minimum size.
+ EXPECT_EQ(diff_utils::GetOldFile(old_files_map, "a").name, "filename");
}
} // namespace chromeos_update_engine
diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
index 0e3f087..4600efe 100644
--- a/payload_generator/extent_ranges.cc
+++ b/payload_generator/extent_ranges.cc
@@ -27,7 +27,6 @@
#include "update_engine/payload_consumer/payload_constants.h"
#include "update_engine/payload_generator/extent_utils.h"
-using std::set;
using std::vector;
namespace chromeos_update_engine {
diff --git a/payload_generator/extent_ranges_unittest.cc b/payload_generator/extent_ranges_unittest.cc
index 2bcffed..326e936 100644
--- a/payload_generator/extent_ranges_unittest.cc
+++ b/payload_generator/extent_ranges_unittest.cc
@@ -18,6 +18,7 @@
#include <vector>
+#include <base/stl_util.h>
#include <gtest/gtest.h>
#include "update_engine/common/test_utils.h"
@@ -53,7 +54,7 @@
#define EXPECT_RANGE_EQ(ranges, var) \
do { \
- ExpectRangeEq(ranges, var, arraysize(var), __LINE__); \
+ ExpectRangeEq(ranges, var, base::size(var), __LINE__); \
} while (0)
void ExpectRangesOverlapOrTouch(uint64_t a_start,
diff --git a/payload_generator/filesystem_interface.h b/payload_generator/filesystem_interface.h
index d04295c..05d387f 100644
--- a/payload_generator/filesystem_interface.h
+++ b/payload_generator/filesystem_interface.h
@@ -62,6 +62,13 @@
// indicating the starting block, and the number of consecutive blocks.
std::vector<Extent> extents;
+ // If true, the file is already compressed on the disk, so we don't need to
+ // parse it again for deflates. For example, image .gz files inside a
+ // compressed SquashFS image. They might have already been compressed by the
+ // mksquashfs, so we can't really parse the file and look for deflate
+ // compressed parts anymore.
+ bool is_compressed = false;
+
// All the deflate locations in the file. These locations are not relative
// to the extents. They are relative to the file system itself.
std::vector<puffin::BitExtent> deflates;
diff --git a/payload_generator/full_update_generator_unittest.cc b/payload_generator/full_update_generator_unittest.cc
index e398125..5f39e8b 100644
--- a/payload_generator/full_update_generator_unittest.cc
+++ b/payload_generator/full_update_generator_unittest.cc
@@ -90,7 +90,7 @@
EXPECT_EQ(config_.hard_chunk_size / config_.block_size,
aops[i].op.dst_extents(0).num_blocks());
if (aops[i].op.type() != InstallOperation::REPLACE) {
- EXPECT_EQ(InstallOperation::REPLACE_BZ, aops[i].op.type());
+ EXPECT_EQ(InstallOperation::REPLACE_XZ, aops[i].op.type());
}
}
}
diff --git a/payload_generator/generate_delta_main.cc b/payload_generator/generate_delta_main.cc
index f035ff1..f7df211 100644
--- a/payload_generator/generate_delta_main.cc
+++ b/payload_generator/generate_delta_main.cc
@@ -38,6 +38,7 @@
#include "update_engine/payload_consumer/payload_constants.h"
#include "update_engine/payload_generator/delta_diff_generator.h"
#include "update_engine/payload_generator/payload_generation_config.h"
+#include "update_engine/payload_generator/payload_properties.h"
#include "update_engine/payload_generator/payload_signer.h"
#include "update_engine/payload_generator/xz.h"
#include "update_engine/update_metadata.pb.h"
@@ -53,6 +54,9 @@
namespace {
+constexpr char kPayloadPropertiesFormatKeyValue[] = "key-value";
+constexpr char kPayloadPropertiesFormatJson[] = "json";
+
void ParseSignatureSizes(const string& signature_sizes_flag,
vector<size_t>* signature_sizes) {
signature_sizes->clear();
@@ -267,14 +271,24 @@
return true;
}
-int ExtractProperties(const string& payload_path, const string& props_file) {
- brillo::KeyValueStore properties;
- TEST_AND_RETURN_FALSE(
- PayloadSigner::ExtractPayloadProperties(payload_path, &properties));
- if (props_file == "-") {
- printf("%s", properties.SaveToString().c_str());
+bool ExtractProperties(const string& payload_path,
+ const string& props_file,
+ const string& props_format) {
+ string properties;
+ PayloadProperties payload_props(payload_path);
+ if (props_format == kPayloadPropertiesFormatKeyValue) {
+ TEST_AND_RETURN_FALSE(payload_props.GetPropertiesAsKeyValue(&properties));
+ } else if (props_format == kPayloadPropertiesFormatJson) {
+ TEST_AND_RETURN_FALSE(payload_props.GetPropertiesAsJson(&properties));
} else {
- properties.Save(base::FilePath(props_file));
+ LOG(FATAL) << "Invalid option " << props_format
+ << " for --properties_format flag.";
+ }
+ if (props_file == "-") {
+ printf("%s", properties.c_str());
+ } else {
+ utils::WriteFile(
+ props_file.c_str(), properties.c_str(), properties.length());
LOG(INFO) << "Generated properties file at " << props_file;
}
return true;
@@ -361,7 +375,11 @@
DEFINE_string(properties_file,
"",
"If passed, dumps the payload properties of the payload passed "
- "in --in_file and exits.");
+ "in --in_file and exits. Look at --properties_format.");
+ DEFINE_string(properties_format,
+ kPayloadPropertiesFormatKeyValue,
+ "Defines the format of the --properties_file. The acceptable "
+ "values are: key-value (default) and json");
DEFINE_int64(max_timestamp,
0,
"The maximum timestamp of the OS allowed to apply this "
@@ -500,7 +518,10 @@
return VerifySignedPayload(FLAGS_in_file, FLAGS_public_key);
}
if (!FLAGS_properties_file.empty()) {
- return ExtractProperties(FLAGS_in_file, FLAGS_properties_file) ? 0 : 1;
+ return ExtractProperties(
+ FLAGS_in_file, FLAGS_properties_file, FLAGS_properties_format)
+ ? 0
+ : 1;
}
// A payload generation was requested. Convert the flags to a
@@ -521,16 +542,10 @@
partition_names = base::SplitString(
FLAGS_partition_names, ":", base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL);
CHECK(!partition_names.empty());
- if (FLAGS_major_version == kChromeOSMajorPayloadVersion ||
- FLAGS_new_partitions.empty()) {
- LOG_IF(FATAL, partition_names.size() != 2)
- << "To support more than 2 partitions, please use the "
- << "--new_partitions flag and major version 2.";
- LOG_IF(FATAL,
- partition_names[0] != kPartitionNameRoot ||
- partition_names[1] != kPartitionNameKernel)
- << "To support non-default partition name, please use the "
- << "--new_partitions flag and major version 2.";
+ if (FLAGS_major_version < kMinSupportedMajorPayloadVersion ||
+ FLAGS_major_version > kMaxSupportedMajorPayloadVersion) {
+ LOG(FATAL) << "Unsupported major version " << FLAGS_major_version;
+ return 1;
}
if (!FLAGS_new_partitions.empty()) {
@@ -591,8 +606,6 @@
}
if (!FLAGS_new_postinstall_config_file.empty()) {
- LOG_IF(FATAL, FLAGS_major_version == kChromeOSMajorPayloadVersion)
- << "Postinstall config is only allowed in major version 2 or newer.";
brillo::KeyValueStore store;
CHECK(store.Load(base::FilePath(FLAGS_new_postinstall_config_file)));
CHECK(payload_config.target.LoadPostInstallConfig(store));
@@ -610,9 +623,6 @@
CHECK(payload_config.target.LoadImageSize());
if (!FLAGS_dynamic_partition_info_file.empty()) {
- LOG_IF(FATAL, FLAGS_major_version == kChromeOSMajorPayloadVersion)
- << "Dynamic partition info is only allowed in major version 2 or "
- "newer.";
brillo::KeyValueStore store;
CHECK(store.Load(base::FilePath(FLAGS_dynamic_partition_info_file)));
CHECK(payload_config.target.LoadDynamicPartitionMetadata(store));
@@ -656,25 +666,40 @@
// Autodetect minor_version by looking at the update_engine.conf in the old
// image.
if (payload_config.is_delta) {
- payload_config.version.minor = kInPlaceMinorPayloadVersion;
brillo::KeyValueStore store;
uint32_t minor_version;
+ bool minor_version_found = false;
for (const PartitionConfig& part : payload_config.source.partitions) {
if (part.fs_interface && part.fs_interface->LoadSettings(&store) &&
utils::GetMinorVersion(store, &minor_version)) {
payload_config.version.minor = minor_version;
+ minor_version_found = true;
+ LOG(INFO) << "Auto-detected minor_version="
+ << payload_config.version.minor;
break;
}
}
+ if (!minor_version_found) {
+ LOG(FATAL) << "Failed to detect the minor version.";
+ return 1;
+ }
} else {
payload_config.version.minor = kFullPayloadMinorVersion;
+ LOG(INFO) << "Using non-delta minor_version="
+ << payload_config.version.minor;
}
- LOG(INFO) << "Auto-detected minor_version=" << payload_config.version.minor;
} else {
payload_config.version.minor = FLAGS_minor_version;
LOG(INFO) << "Using provided minor_version=" << FLAGS_minor_version;
}
+ if (payload_config.version.minor != kFullPayloadMinorVersion &&
+ (payload_config.version.minor < kMinSupportedMinorPayloadVersion ||
+ payload_config.version.minor > kMaxSupportedMinorPayloadVersion)) {
+ LOG(FATAL) << "Unsupported minor version " << payload_config.version.minor;
+ return 1;
+ }
+
payload_config.max_timestamp = FLAGS_max_timestamp;
if (payload_config.version.minor >= kVerityMinorPayloadVersion)
diff --git a/payload_generator/graph_types.cc b/payload_generator/graph_types.cc
deleted file mode 100644
index c03766d..0000000
--- a/payload_generator/graph_types.cc
+++ /dev/null
@@ -1,23 +0,0 @@
-//
-// Copyright (C) 2015 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/graph_types.h"
-
-namespace chromeos_update_engine {
-
-const Vertex::Index Vertex::kInvalidIndex = static_cast<Vertex::Index>(-1);
-
-} // namespace chromeos_update_engine
diff --git a/payload_generator/graph_types.h b/payload_generator/graph_types.h
deleted file mode 100644
index f96b0f3..0000000
--- a/payload_generator/graph_types.h
+++ /dev/null
@@ -1,87 +0,0 @@
-//
-// Copyright (C) 2009 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
-#define UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
-
-#include <map>
-#include <set>
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/macros.h>
-
-#include "update_engine/payload_generator/annotated_operation.h"
-#include "update_engine/payload_generator/extent_utils.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 {
-
-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) {}
- 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:
- AnnotatedOperation aop;
-
- typedef std::vector<Vertex>::size_type Index;
- static const Vertex::Index kInvalidIndex;
-};
-
-typedef std::vector<Vertex> Graph;
-
-typedef std::pair<Vertex::Index, Vertex::Index> Edge;
-
-const uint64_t kTempBlockStart = 1ULL << 60;
-static_assert(kTempBlockStart != 0, "kTempBlockStart invalid");
-
-} // namespace chromeos_update_engine
-
-#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
diff --git a/payload_generator/graph_utils.cc b/payload_generator/graph_utils.cc
deleted file mode 100644
index 7f5cf8f..0000000
--- a/payload_generator/graph_utils.cc
+++ /dev/null
@@ -1,142 +0,0 @@
-//
-// Copyright (C) 2009 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/graph_utils.h"
-
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/logging.h>
-#include <base/macros.h>
-
-#include "update_engine/payload_consumer/payload_constants.h"
-#include "update_engine/payload_generator/annotated_operation.h"
-#include "update_engine/payload_generator/extent_utils.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 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);
- }
-}
-
-namespace {
-template <typename T>
-void DumpExtents(const T& field, int prepend_space_count) {
- string header(prepend_space_count, ' ');
- for (const auto& extent : field) {
- LOG(INFO) << header << "(" << extent.start_block() << ", "
- << extent.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) {
- LOG(INFO) << i << (graph[i].valid ? "" : "-INV") << ": "
- << graph[i].aop.name << ": "
- << InstallOperationTypeName(graph[i].aop.op.type());
- LOG(INFO) << " src_extents:";
- DumpExtents(graph[i].aop.op.src_extents(), 4);
- LOG(INFO) << " dst_extents:";
- DumpExtents(graph[i].aop.op.dst_extents(), 4);
- LOG(INFO) << " out edges:";
- DumpOutEdges(graph[i].out_edges);
- }
-}
-
-} // namespace graph_utils
-} // namespace chromeos_update_engine
diff --git a/payload_generator/graph_utils.h b/payload_generator/graph_utils.h
deleted file mode 100644
index 7024215..0000000
--- a/payload_generator/graph_utils.h
+++ /dev/null
@@ -1,54 +0,0 @@
-//
-// Copyright (C) 2009 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
-#define UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
-
-#include <vector>
-
-#include <base/macros.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);
-
-void DumpGraph(const Graph& graph);
-
-} // namespace graph_utils
-
-} // namespace chromeos_update_engine
-
-#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
diff --git a/payload_generator/graph_utils_unittest.cc b/payload_generator/graph_utils_unittest.cc
deleted file mode 100644
index 07e7664..0000000
--- a/payload_generator/graph_utils_unittest.cc
+++ /dev/null
@@ -1,94 +0,0 @@
-//
-// Copyright (C) 2009 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/graph_utils.h"
-
-#include <utility>
-#include <vector>
-
-#include <gtest/gtest.h>
-
-#include "update_engine/payload_consumer/payload_constants.h"
-#include "update_engine/payload_generator/extent_ranges.h"
-#include "update_engine/payload_generator/extent_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(0U, extents.size());
- AppendBlockToExtents(&extents, 0);
- EXPECT_EQ(1U, extents.size());
- AppendBlockToExtents(&extents, 1);
- AppendBlockToExtents(&extents, 2);
- EXPECT_EQ(1U, extents.size());
- AppendBlockToExtents(&extents, 4);
-
- EXPECT_EQ(2U, extents.size());
- EXPECT_EQ(0U, extents[0].start_block());
- EXPECT_EQ(3U, extents[0].num_blocks());
- EXPECT_EQ(4U, extents[1].start_block());
- EXPECT_EQ(1U, extents[1].num_blocks());
-
- EXPECT_EQ(4U, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
-}
-
-TEST(GraphUtilsTest, DepsTest) {
- Graph graph(3);
-
- graph_utils::AddReadBeforeDep(&graph[0], 1, 3);
- EXPECT_EQ(1U, graph[0].out_edges.size());
- {
- Extent& extent = graph[0].out_edges[1].extents[0];
- EXPECT_EQ(3U, extent.start_block());
- EXPECT_EQ(1U, extent.num_blocks());
- }
- graph_utils::AddReadBeforeDep(&graph[0], 1, 4);
- EXPECT_EQ(1U, graph[0].out_edges.size());
- {
- Extent& extent = graph[0].out_edges[1].extents[0];
- EXPECT_EQ(3U, extent.start_block());
- EXPECT_EQ(2U, extent.num_blocks());
- }
- graph_utils::AddReadBeforeDepExtents(
- &graph[2], 1, vector<Extent>(1, ExtentForRange(5, 2)));
- EXPECT_EQ(1U, graph[2].out_edges.size());
- {
- Extent& extent = graph[2].out_edges[1].extents[0];
- EXPECT_EQ(5U, extent.start_block());
- EXPECT_EQ(2U, 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(0U, graph[2].out_edges.size());
-
- EXPECT_EQ(1U, graph[0].out_edges.size());
- graph_utils::DropIncomingEdgesTo(&graph, 1);
- EXPECT_EQ(0U, graph[0].out_edges.size());
-}
-
-} // namespace chromeos_update_engine
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
deleted file mode 100644
index d553cc4..0000000
--- a/payload_generator/inplace_generator.cc
+++ /dev/null
@@ -1,798 +0,0 @@
-//
-// Copyright (C) 2015 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/inplace_generator.h"
-
-#include <algorithm>
-#include <map>
-#include <set>
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/stl_util.h>
-
-#include "update_engine/common/utils.h"
-#include "update_engine/payload_consumer/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/delta_diff_utils.h"
-#include "update_engine/payload_generator/extent_ranges.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/update_metadata.pb.h"
-
-using std::make_pair;
-using std::map;
-using std::pair;
-using std::set;
-using std::string;
-using std::vector;
-
-namespace chromeos_update_engine {
-
-using Block = InplaceGenerator::Block;
-
-namespace {
-
-// The only PayloadVersion supported by this implementation.
-const PayloadVersion kInPlacePayloadVersion{kChromeOSMajorPayloadVersion,
- kInPlaceMinorPayloadVersion};
-
-// 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:
- 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_{kTempBlockStart};
-};
-
-// 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 (uint64_t block : blocks) {
- AppendBlockToExtents(&new_extents, block);
- }
- return new_extents;
-}
-
-// Helper class to compare two operations by start block of the first Extent in
-// their destination extents given the index of the operations in the graph.
-class IndexedInstallOperationsDstComparator {
- public:
- explicit IndexedInstallOperationsDstComparator(Graph* graph)
- : graph_(graph) {}
-
- // Compares the operations in the vertex a and b of graph_.
- bool operator()(size_t a, size_t b) const {
- return diff_utils::CompareAopsByDestination((*graph_)[a].aop,
- (*graph_)[b].aop);
- }
-
- private:
- const Graph* const graph_;
-};
-
-} // namespace
-
-void InplaceGenerator::CheckGraph(const Graph& graph) {
- for (const Vertex& v : graph) {
- CHECK(v.aop.op.has_type());
- }
-}
-
-void InplaceGenerator::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->aop.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];
- }
- ApplyMap(&read_blocks, conversion);
- for (auto& edge_prop_pair : vertex->out_edges) {
- vector<uint64_t> write_before_deps_expanded =
- ExpandExtents(edge_prop_pair.second.write_extents);
- ApplyMap(&write_before_deps_expanded, conversion);
- edge_prop_pair.second.write_extents =
- CompressExtents(write_before_deps_expanded);
- }
- }
- // Convert read_blocks back to extents
- vertex->aop.op.clear_src_extents();
- vector<Extent> new_extents = CompressExtents(read_blocks);
- StoreExtents(new_extents, vertex->aop.op.mutable_src_extents());
-}
-
-bool InplaceGenerator::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 (const Edge& edge : edges) {
- cuts.resize(cuts.size() + 1);
- vector<Extent> old_extents =
- (*graph)[edge.first].out_edges[edge.second].extents;
- // Choose some scratch space
- scratch_blocks_used += graph_utils::EdgeWeight(*graph, edge);
- cuts.back().tmp_extents =
- scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, edge));
- // create vertex to copy original->scratch
- cuts.back().new_vertex = graph->size();
- graph->emplace_back();
- cuts.back().old_src = edge.first;
- cuts.back().old_dst = edge.second;
-
- EdgeProperties& cut_edge_properties =
- (*graph)[edge.first].out_edges.find(edge.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)[edge.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().aop.op.set_type(InstallOperation::MOVE);
- StoreExtents(cut_edge_properties.extents,
- graph->back().aop.op.mutable_src_extents());
- StoreExtents(cuts.back().tmp_extents,
- graph->back().aop.op.mutable_dst_extents());
- graph->back().aop.op.set_src_length(graph_utils::EdgeWeight(*graph, edge) *
- kBlockSize);
- graph->back().aop.op.set_dst_length(graph->back().aop.op.src_length());
-
- // make the dest node read from the scratch space
- SubstituteBlocks(&((*graph)[edge.second]),
- (*graph)[edge.first].out_edges[edge.second].extents,
- cuts.back().tmp_extents);
-
- // delete the old edge
- CHECK_EQ(static_cast<Graph::size_type>(1),
- (*graph)[edge.first].out_edges.erase(edge.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)[edge.second].out_edges.insert(
- make_pair(graph->size() - 1, write_before_edge_properties));
- }
- out_cuts->swap(cuts);
- return true;
-}
-
-// 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 InplaceGenerator::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());
- }
- AppendBlockToExtents(&edge_it->second.extents, i);
- }
-}
-
-namespace {
-
-class SortCutsByTopoOrderLess {
- public:
- explicit SortCutsByTopoOrderLess(
- const 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:
- const vector<vector<Vertex::Index>::size_type>& table_;
-};
-
-} // namespace
-
-void InplaceGenerator::GenerateReverseTopoOrderMap(
- const 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 InplaceGenerator::SortCutsByTopoOrder(
- const 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 InplaceGenerator::MoveAndSortFullOpsToBack(
- Graph* graph, vector<Vertex::Index>* op_indexes) {
- vector<Vertex::Index> ret;
- vector<Vertex::Index> full_ops;
- ret.reserve(op_indexes->size());
- for (auto op_index : *op_indexes) {
- InstallOperation::Type type = (*graph)[op_index].aop.op.type();
- if (type == InstallOperation::REPLACE ||
- type == InstallOperation::REPLACE_BZ) {
- full_ops.push_back(op_index);
- } else {
- ret.push_back(op_index);
- }
- }
- LOG(INFO) << "Stats: " << full_ops.size() << " full ops out of "
- << (full_ops.size() + ret.size()) << " total ops.";
- // Sort full ops according to their dst_extents.
- sort(full_ops.begin(),
- full_ops.end(),
- IndexedInstallOperationsDstComparator(graph));
- ret.insert(ret.end(), full_ops.begin(), full_ops.end());
- op_indexes->swap(ret);
-}
-
-namespace {
-
-template <typename T>
-bool TempBlocksExistInExtents(const T& extents) {
- for (const auto& extent : extents) {
- uint64_t start = extent.start_block();
- uint64_t num = extent.num_blocks();
- 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;
-}
-
-// Converts 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_part,
- BlobFileWriter* blob_file,
- 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 (const CutEdgeVertexes& cut : cuts) {
- TEST_AND_RETURN_FALSE(
- InplaceGenerator::ConvertCutToFullOp(graph, cut, new_part, blob_file));
- deleted_nodes.insert(cut.new_vertex);
- }
- deleted_nodes.insert(cuts[0].old_dst);
-
- vector<Vertex::Index> new_op_indexes;
- new_op_indexes.reserve(op_indexes->size());
- for (Vertex::Index vertex_index : *op_indexes) {
- if (base::ContainsKey(deleted_nodes, vertex_index))
- continue;
- new_op_indexes.push_back(vertex_index);
- }
- new_op_indexes.push_back(cuts[0].old_dst);
- op_indexes->swap(new_op_indexes);
- InplaceGenerator::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_part,
- BlobFileWriter* blob_file,
- 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;
- vector<uint64_t> cuts_blocks_needed(cuts.size());
- for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
- uint64_t cut_blocks_needed = 0;
- for (const Extent& extent : cuts[i].tmp_extents) {
- cut_blocks_needed += extent.num_blocks();
- }
- blocks_needed += cut_blocks_needed;
- cuts_blocks_needed[i] = 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].aop.op.dst_extents());
- ranges.SubtractExtent(
- ExtentForRange(kTempBlockStart, kSparseHole - kTempBlockStart));
- ranges.SubtractRepeatedExtents((*graph)[test_node].aop.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);
- }
-
- // Prevent using the block 0 as scratch space due to crbug.com/480751.
- if (ranges.ContainsBlock(0)) {
- LOG(INFO) << "Removing block 0 from the selected scratch range in vertex "
- << i;
- ranges.SubtractBlock(0);
- }
-
- 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_part, blob_file, 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 (const auto& index_range_pair : block_suppliers) {
- graph_utils::AddReadBeforeDepExtents(
- &(*graph)[index_range_pair.first],
- old_dst,
- index_range_pair.second.GetExtentsForBlockCount(
- index_range_pair.second.blocks()));
- }
-
- // Replace temp blocks in each cut
- for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
- const CutEdgeVertexes& cut = cuts[i];
- vector<Extent> real_extents =
- scratch_ranges.GetExtentsForBlockCount(cuts_blocks_needed[i]);
- scratch_ranges.SubtractExtents(real_extents);
-
- // Fix the old dest node w/ the real blocks
- InplaceGenerator::SubstituteBlocks(
- &(*graph)[old_dst], cut.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.
- InstallOperation* op = &(*graph)[cut.new_vertex].aop.op;
- op->clear_dst_extents();
- StoreExtents(real_extents, op->mutable_dst_extents());
- }
- return true;
-}
-
-} // namespace
-
-bool InplaceGenerator::AssignTempBlocks(
- Graph* graph,
- const string& new_part,
- BlobFileWriter* blob_file,
- 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].aop.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_part,
- blob_file,
- 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_part, blob_file, op_indexes, reverse_op_indexes, cuts_group));
- return true;
-}
-
-bool InplaceGenerator::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 InstallOperation& op = it->aop.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 (const auto& edge_prop_pair : it->out_edges) {
- if (TempBlocksExistInExtents(edge_prop_pair.second.extents) ||
- TempBlocksExistInExtents(edge_prop_pair.second.write_extents)) {
- LOG(INFO) << "bad out edge in node " << idx;
- LOG(INFO) << "so yeah";
- return false;
- }
- }
- }
- return true;
-}
-
-bool InplaceGenerator::ConvertCutToFullOp(Graph* graph,
- const CutEdgeVertexes& cut,
- const string& new_part,
- BlobFileWriter* blob_file) {
- // Drop all incoming edges, keep all outgoing edges
-
- // Keep all outgoing edges
- if ((*graph)[cut.old_dst].aop.op.type() != InstallOperation::REPLACE_BZ &&
- (*graph)[cut.old_dst].aop.op.type() != InstallOperation::REPLACE) {
- Vertex::EdgeMap out_edges = (*graph)[cut.old_dst].out_edges;
- graph_utils::DropWriteBeforeDeps(&out_edges);
-
- // Replace the operation with a REPLACE or REPLACE_BZ to generate the same
- // |new_extents| list of blocks and update the graph.
- vector<AnnotatedOperation> new_aop;
- vector<Extent> new_extents;
- ExtentsToVector((*graph)[cut.old_dst].aop.op.dst_extents(), &new_extents);
- TEST_AND_RETURN_FALSE(diff_utils::DeltaReadFile(
- &new_aop,
- "", // old_part
- new_part,
- vector<Extent>(), // old_extents
- new_extents,
- {}, // old_deflates
- {}, // new_deflates
- (*graph)[cut.old_dst].aop.name,
- -1, // chunk_blocks, forces to have a single operation.
- kInPlacePayloadVersion,
- blob_file));
- TEST_AND_RETURN_FALSE(new_aop.size() == 1);
- TEST_AND_RETURN_FALSE(AddInstallOpToGraph(
- graph, cut.old_dst, nullptr, new_aop.front().op, new_aop.front().name));
-
- (*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 InplaceGenerator::ConvertGraphToDag(Graph* graph,
- const string& new_part,
- BlobFileWriter* blob_file,
- 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";
- MoveAndSortFullOpsToBack(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_part, blob_file, 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 InplaceGenerator::CreateScratchNode(uint64_t start_block,
- uint64_t num_blocks,
- Vertex* vertex) {
- vertex->aop.name = "<scratch>";
- vertex->aop.op.set_type(InstallOperation::REPLACE_BZ);
- vertex->aop.op.set_data_offset(0);
- vertex->aop.op.set_data_length(0);
- Extent* extent = vertex->aop.op.add_dst_extents();
- extent->set_start_block(start_block);
- extent->set_num_blocks(num_blocks);
-}
-
-bool InplaceGenerator::AddInstallOpToBlocksVector(
- const 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 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 (const Extent& extent : extents) {
- 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].aop.name
- << ") and also " << vertex << "(" << graph[vertex].aop.name
- << ")";
- }
- (*blocks)[block].*access_type = vertex;
- }
- }
- }
- return true;
-}
-
-bool InplaceGenerator::AddInstallOpToGraph(Graph* graph,
- Vertex::Index existing_vertex,
- vector<Block>* blocks,
- const InstallOperation& operation,
- const string& op_name) {
- Vertex::Index vertex = existing_vertex;
- if (vertex == Vertex::kInvalidIndex) {
- graph->emplace_back();
- vertex = graph->size() - 1;
- }
- (*graph)[vertex].aop.op = operation;
- CHECK((*graph)[vertex].aop.op.has_type());
- (*graph)[vertex].aop.name = op_name;
-
- if (blocks)
- TEST_AND_RETURN_FALSE(InplaceGenerator::AddInstallOpToBlocksVector(
- (*graph)[vertex].aop.op, *graph, vertex, blocks));
- return true;
-}
-
-void InplaceGenerator::ApplyMap(vector<uint64_t>* collection,
- const map<uint64_t, uint64_t>& the_map) {
- for (uint64_t& elem : *collection) {
- const auto& map_it = the_map.find(elem);
- if (map_it != the_map.end())
- elem = map_it->second;
- }
-}
-
-bool InplaceGenerator::ResolveReadAfterWriteDependencies(
- const PartitionConfig& old_part,
- const PartitionConfig& new_part,
- uint64_t partition_size,
- size_t block_size,
- BlobFileWriter* blob_file,
- vector<AnnotatedOperation>* aops) {
- // Convert the operations to the graph.
- Graph graph;
- CheckGraph(graph);
- vector<Block> blocks(std::max(old_part.size, new_part.size) / block_size);
- for (const auto& aop : *aops) {
- AddInstallOpToGraph(
- &graph, Vertex::kInvalidIndex, &blocks, aop.op, aop.name);
- }
- CheckGraph(graph);
-
- // Final scratch block (if there's space)
- Vertex::Index scratch_vertex = Vertex::kInvalidIndex;
- if (blocks.size() < (partition_size / block_size)) {
- scratch_vertex = graph.size();
- graph.emplace_back();
- size_t scratch_blocks = (partition_size / block_size) - blocks.size();
- LOG(INFO) << "Added " << scratch_blocks << " scratch space blocks.";
- CreateScratchNode(blocks.size(), scratch_blocks, &graph.back());
- }
- CheckGraph(graph);
-
- LOG(INFO) << "Creating edges...";
- CreateEdges(&graph, blocks);
- LOG(INFO) << "Done creating edges";
- CheckGraph(graph);
-
- vector<Vertex::Index> final_order;
- TEST_AND_RETURN_FALSE(ConvertGraphToDag(
- &graph, new_part.path, blob_file, &final_order, scratch_vertex));
-
- // Copy operations over to the |aops| vector in the final_order generated by
- // the topological sort.
- aops->clear();
- aops->reserve(final_order.size());
- for (const Vertex::Index vertex_index : final_order) {
- const Vertex& vertex = graph[vertex_index];
- aops->push_back(vertex.aop);
- }
- return true;
-}
-
-bool InplaceGenerator::GenerateOperations(const PayloadGenerationConfig& config,
- const PartitionConfig& old_part,
- const PartitionConfig& new_part,
- BlobFileWriter* blob_file,
- vector<AnnotatedOperation>* aops) {
- TEST_AND_RETURN_FALSE(old_part.name == new_part.name);
- TEST_AND_RETURN_FALSE(config.version.major == kInPlacePayloadVersion.major);
- TEST_AND_RETURN_FALSE(config.version.minor == kInPlacePayloadVersion.minor);
-
- ssize_t hard_chunk_blocks =
- (config.hard_chunk_size == -1
- ? -1
- : config.hard_chunk_size / config.block_size);
- size_t soft_chunk_blocks = config.soft_chunk_size / config.block_size;
- uint64_t partition_size = new_part.size;
- if (new_part.name == kPartitionNameRoot)
- partition_size = config.rootfs_partition_size;
-
- LOG(INFO) << "Delta compressing " << new_part.name << " partition...";
- TEST_AND_RETURN_FALSE(diff_utils::DeltaReadPartition(aops,
- old_part,
- new_part,
- hard_chunk_blocks,
- soft_chunk_blocks,
- config.version,
- blob_file));
- LOG(INFO) << "Done reading " << new_part.name;
-
- TEST_AND_RETURN_FALSE(ResolveReadAfterWriteDependencies(
- old_part, new_part, partition_size, config.block_size, blob_file, aops));
- LOG(INFO) << "Done reordering " << new_part.name;
- return true;
-}
-
-}; // namespace chromeos_update_engine
diff --git a/payload_generator/inplace_generator.h b/payload_generator/inplace_generator.h
deleted file mode 100644
index e7298d2..0000000
--- a/payload_generator/inplace_generator.h
+++ /dev/null
@@ -1,240 +0,0 @@
-//
-// Copyright (C) 2015 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
-#define UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
-
-#include <map>
-#include <set>
-#include <string>
-#include <vector>
-
-#include "update_engine/payload_generator/blob_file_writer.h"
-#include "update_engine/payload_generator/delta_diff_generator.h"
-#include "update_engine/payload_generator/graph_types.h"
-#include "update_engine/payload_generator/operations_generator.h"
-
-// InplaceGenerator contains all functionality related to the inplace algorithm
-// for generating update payloads. These are the functions used when delta minor
-// version is 1.
-
-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 InplaceGenerator : public OperationsGenerator {
- 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;
- };
-
- InplaceGenerator() = default;
-
- // Checks all the operations in the graph have a type assigned.
- static void CheckGraph(const Graph& graph);
-
- // 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);
-
- // 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);
-
- // 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(
- const std::vector<Vertex::Index>& op_indexes,
- std::vector<std::vector<Vertex::Index>::size_type>* reverse_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(const std::vector<Vertex::Index>& op_indexes,
- std::vector<CutEdgeVertexes>* cuts);
-
- // 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 MoveAndSortFullOpsToBack(Graph* graph,
- std::vector<Vertex::Index>* op_indexes);
-
- // 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);
-
- // 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_part,
- BlobFileWriter* blob_file,
- std::vector<Vertex::Index>* op_indexes,
- std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes,
- const std::vector<CutEdgeVertexes>& cuts);
-
- // 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_part,
- BlobFileWriter* blob_file);
-
- // 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_part,
- BlobFileWriter* blob_file,
- std::vector<Vertex::Index>* final_order,
- Vertex::Index scratch_vertex);
-
- // 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);
-
- // 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 InstallOperation& operation,
- const Graph& graph,
- Vertex::Index vertex,
- std::vector<Block>* blocks);
-
- // Add a vertex (if |existing_vertex| is kInvalidVertex) or update an
- // |existing_vertex| with the passed |operation|.
- // This method will also register the vertex as the reader or writer of the
- // blocks involved in the operation updating the |blocks| vector. The
- // |op_name| associated with the Vertex is used for logging purposes.
- static bool AddInstallOpToGraph(Graph* graph,
- Vertex::Index existing_vertex,
- std::vector<Block>* blocks,
- const InstallOperation& operation,
- const std::string& op_name);
-
- // Apply the transformation stored in |the_map| to the |collection| vector
- // replacing the map keys found in |collection| with its associated value in
- // |the_map|.
- static void ApplyMap(std::vector<uint64_t>* collection,
- const std::map<uint64_t, uint64_t>& the_map);
-
- // Resolve all read-after-write dependencies in the operation list |aops|. The
- // operations in |aops| are such that they generate the desired |new_part| if
- // applied reading always from the original image. This function reorders the
- // operations and generates new operations when needed to make these
- // operations produce the same |new_part| result when applied in-place.
- // The new operations will create blobs in |data_file_fd| and update
- // the file size pointed by |data_file_size| if needed.
- // On success, stores the new operations in |aops| in the right order and
- // returns true.
- static bool ResolveReadAfterWriteDependencies(
- const PartitionConfig& old_part,
- const PartitionConfig& new_part,
- uint64_t partition_size,
- size_t block_size,
- BlobFileWriter* blob_file,
- std::vector<AnnotatedOperation>* aops);
-
- // Generate the update payload operations for the given partition using
- // only operations that read from the target and/or write to the target,
- // hence, applying the payload "in-place" in the target partition. This method
- // assumes that the contents of the source image are pre-copied to the target
- // partition, up to the size of the source image. Use this method to generate
- // a delta update with the minor version kInPlaceMinorPayloadVersion.
- // The operations are stored in |aops|. All the offsets in the operations
- // reference the data written to |blob_file|.
- bool GenerateOperations(const PayloadGenerationConfig& config,
- const PartitionConfig& old_part,
- const PartitionConfig& new_part,
- BlobFileWriter* blob_file,
- std::vector<AnnotatedOperation>* aops) override;
-
- private:
- DISALLOW_COPY_AND_ASSIGN(InplaceGenerator);
-};
-
-}; // namespace chromeos_update_engine
-
-#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
deleted file mode 100644
index 8028f36..0000000
--- a/payload_generator/inplace_generator_unittest.cc
+++ /dev/null
@@ -1,752 +0,0 @@
-//
-// Copyright (C) 2015 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/inplace_generator.h"
-
-#include <map>
-#include <memory>
-#include <set>
-#include <sstream>
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/format_macros.h>
-#include <base/logging.h>
-#include <base/strings/string_util.h>
-#include <base/strings/stringprintf.h>
-#include <gtest/gtest.h>
-
-#include "update_engine/common/test_utils.h"
-#include "update_engine/common/utils.h"
-#include "update_engine/payload_generator/cycle_breaker.h"
-#include "update_engine/payload_generator/delta_diff_generator.h"
-#include "update_engine/payload_generator/delta_diff_utils.h"
-#include "update_engine/payload_generator/extent_ranges.h"
-#include "update_engine/payload_generator/graph_types.h"
-#include "update_engine/payload_generator/graph_utils.h"
-
-using std::map;
-using std::set;
-using std::string;
-using std::stringstream;
-using std::vector;
-
-namespace chromeos_update_engine {
-
-using Block = InplaceGenerator::Block;
-
-namespace {
-
-void GenVertex(Vertex* out,
- const vector<Extent>& src_extents,
- const vector<Extent>& dst_extents,
- const string& path,
- InstallOperation::Type type) {
- out->aop.op.set_type(type);
- out->aop.name = path;
- StoreExtents(src_extents, out->aop.op.mutable_src_extents());
- StoreExtents(dst_extents, out->aop.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) {
- 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() << "}";
-}
-
-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(InstallOperation* op, uint64_t start, uint64_t length) {
- Extent* extent = op->add_src_extents();
- extent->set_start_block(start);
- extent->set_num_blocks(length);
-}
-
-} // namespace
-
-class InplaceGeneratorTest : public ::testing::Test {
- protected:
- // Initialize |blob_path_|, |blob_file_size_| and |blob_file_fd_| variables
- // with a new blob file. The file is closed and removed automatically when
- // the test finishes.
- void CreateBlobFile() {
- // blob_fd_closer_ takes a pointer to blob_fd_. Make sure we destroy a
- // previous instance before overriding blob_fd_.
- blob_fd_closer_.reset();
- EXPECT_TRUE(utils::MakeTempFile(
- "InplaceGenerator_blob_file.XXXXXX", &blob_path_, &blob_fd_));
- blob_path_unlinker_.reset(new ScopedPathUnlinker(blob_path_));
- blob_fd_closer_.reset(new ScopedFdCloser(&blob_fd_));
- blob_file_size_ = 0;
- EXPECT_GE(blob_fd_, 0);
- blob_file_.reset(new BlobFileWriter(blob_fd_, &blob_file_size_));
- }
-
- // Dump the list of operations |aops| in case of test failure.
- void DumpAopsOnFailure(const vector<AnnotatedOperation>& aops) {
- if (HasNonfatalFailure()) {
- LOG(INFO) << "Result operation list:";
- for (const auto& aop : aops) {
- LOG(INFO) << aop;
- }
- }
- }
-
- // Blob file name, file descriptor and file size used to store operation
- // blobs.
- string blob_path_;
- int blob_fd_{-1};
- off_t blob_file_size_{0};
- std::unique_ptr<BlobFileWriter> blob_file_;
- std::unique_ptr<ScopedPathUnlinker> blob_path_unlinker_;
- std::unique_ptr<ScopedFdCloser> blob_fd_closer_;
-};
-
-TEST_F(InplaceGeneratorTest, BlockDefaultValues) {
- // Tests that a Block is initialized with the default values as a
- // Vertex::kInvalidIndex. This is required by the delta generators.
- Block block;
- EXPECT_EQ(Vertex::kInvalidIndex, block.reader);
- EXPECT_EQ(Vertex::kInvalidIndex, block.writer);
-}
-
-TEST_F(InplaceGeneratorTest, 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;
- InstallOperation& op = vertex.aop.op;
- OpAppendExtent(&op, 4, 3);
- OpAppendExtent(&op, kSparseHole, 4); // Sparse hole in file
- OpAppendExtent(&op, 3, 1);
- OpAppendExtent(&op, 7, 3);
-
- InplaceGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
-
- EXPECT_EQ(7, op.src_extents_size());
- EXPECT_EQ(11U, op.src_extents(0).start_block());
- EXPECT_EQ(1U, op.src_extents(0).num_blocks());
- EXPECT_EQ(13U, op.src_extents(1).start_block());
- EXPECT_EQ(1U, op.src_extents(1).num_blocks());
- EXPECT_EQ(6U, op.src_extents(2).start_block());
- EXPECT_EQ(1U, op.src_extents(2).num_blocks());
- EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
- EXPECT_EQ(4U, op.src_extents(3).num_blocks());
- EXPECT_EQ(10U, op.src_extents(4).start_block());
- EXPECT_EQ(1U, op.src_extents(4).num_blocks());
- EXPECT_EQ(14U, op.src_extents(5).start_block());
- EXPECT_EQ(1U, op.src_extents(5).num_blocks());
- EXPECT_EQ(8U, op.src_extents(6).start_block());
- EXPECT_EQ(2U, op.src_extents(6).num_blocks());
-}
-
-TEST_F(InplaceGeneratorTest, CutEdgesTest) {
- Graph graph;
- vector<Block> blocks(9);
-
- // Create nodes in graph
- {
- graph.resize(graph.size() + 1);
- graph.back().aop.op.set_type(InstallOperation::MOVE);
- // Reads from blocks 3, 5, 7
- vector<Extent> extents;
- AppendBlockToExtents(&extents, 3);
- AppendBlockToExtents(&extents, 5);
- AppendBlockToExtents(&extents, 7);
- StoreExtents(extents, graph.back().aop.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();
- AppendBlockToExtents(&extents, 1);
- AppendBlockToExtents(&extents, 2);
- AppendBlockToExtents(&extents, 4);
- StoreExtents(extents, graph.back().aop.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().aop.op.set_type(InstallOperation::MOVE);
- // Reads from blocks 1, 2, 4
- vector<Extent> extents;
- AppendBlockToExtents(&extents, 1);
- AppendBlockToExtents(&extents, 2);
- AppendBlockToExtents(&extents, 4);
- StoreExtents(extents, graph.back().aop.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();
- AppendBlockToExtents(&extents, 3);
- AppendBlockToExtents(&extents, 5);
- AppendBlockToExtents(&extents, 6);
- StoreExtents(extents, graph.back().aop.op.mutable_dst_extents());
- blocks[3].writer = graph.size() - 1;
- blocks[5].writer = graph.size() - 1;
- blocks[6].writer = graph.size() - 1;
- }
-
- // Create edges
- InplaceGenerator::CreateEdges(&graph, blocks);
-
- // Find cycles
- CycleBreaker cycle_breaker;
- set<Edge> cut_edges;
- cycle_breaker.BreakCycles(graph, &cut_edges);
-
- EXPECT_EQ(1U, cut_edges.size());
- EXPECT_TRUE(cut_edges.end() !=
- cut_edges.find(std::pair<Vertex::Index, Vertex::Index>(1, 0)));
-
- vector<CutEdgeVertexes> cuts;
- EXPECT_TRUE(InplaceGenerator::CutEdges(&graph, cut_edges, &cuts));
-
- EXPECT_EQ(3U, graph.size());
-
- // Check new node in graph:
- EXPECT_EQ(InstallOperation::MOVE, graph.back().aop.op.type());
- EXPECT_EQ(2, graph.back().aop.op.src_extents_size());
- EXPECT_EQ(1, graph.back().aop.op.dst_extents_size());
- EXPECT_EQ(kTempBlockStart, graph.back().aop.op.dst_extents(0).start_block());
- EXPECT_EQ(2U, graph.back().aop.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].aop.op.src_extents_size());
- EXPECT_EQ(kTempBlockStart, graph[0].aop.op.src_extents(0).start_block());
- EXPECT_EQ(2U, graph[0].aop.op.src_extents(0).num_blocks());
- EXPECT_EQ(7U, graph[0].aop.op.src_extents(1).start_block());
- EXPECT_EQ(1U, graph[0].aop.op.src_extents(1).num_blocks());
-
- // And that the old dst extents haven't changed
- EXPECT_EQ(2, graph[0].aop.op.dst_extents_size());
- EXPECT_EQ(1U, graph[0].aop.op.dst_extents(0).start_block());
- EXPECT_EQ(2U, graph[0].aop.op.dst_extents(0).num_blocks());
- EXPECT_EQ(4U, graph[0].aop.op.dst_extents(1).start_block());
- EXPECT_EQ(1U, graph[0].aop.op.dst_extents(1).num_blocks());
-
- // Ensure it only depends on the next node and the new temp node
- EXPECT_EQ(2U, 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].aop.op.src_extents_size());
- EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).start_block());
- EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).num_blocks());
- EXPECT_EQ(4U, graph[1].aop.op.src_extents(1).start_block());
- EXPECT_EQ(1U, graph[1].aop.op.src_extents(1).num_blocks());
-
- EXPECT_EQ(2, graph[1].aop.op.dst_extents_size());
- EXPECT_EQ(3U, graph[1].aop.op.dst_extents(0).start_block());
- EXPECT_EQ(1U, graph[1].aop.op.dst_extents(0).num_blocks());
- EXPECT_EQ(5U, graph[1].aop.op.dst_extents(1).start_block());
- EXPECT_EQ(2U, graph[1].aop.op.dst_extents(1).num_blocks());
-
- // Ensure it only depends on the next node
- EXPECT_EQ(1U, graph[1].out_edges.size());
- EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
-}
-
-TEST_F(InplaceGeneratorTest, AssignTempBlocksReuseTest) {
- 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), "", InstallOperation::MOVE);
- GenVertex(&graph[1],
- VectOfExt(tmp, 1),
- VectOfExt(0, 1),
- "",
- InstallOperation::MOVE);
- GenVertex(&graph[2],
- VectOfExt(1, 1),
- VectOfExt(tmp, 1),
- "",
- InstallOperation::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), "", InstallOperation::MOVE);
- GenVertex(
- &graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", InstallOperation::MOVE);
- GenVertex(&graph[5],
- VectOfExt(tmp, 3),
- VectOfExt(4, 3),
- kFilename,
- InstallOperation::MOVE);
- GenVertex(&graph[6],
- VectOfExt(2, 2),
- VectOfExt(tmp, 2),
- "",
- InstallOperation::MOVE);
- GenVertex(&graph[7],
- VectOfExt(7, 1),
- VectOfExt(tmp + 2, 1),
- "",
- InstallOperation::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), "", InstallOperation::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;
- InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes,
- &reverse_op_indexes);
-
- CreateBlobFile();
- EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph,
- "/dev/zero",
- blob_file_.get(),
- &op_indexes,
- &reverse_op_indexes,
- cuts));
- EXPECT_FALSE(graph[6].valid);
- EXPECT_FALSE(graph[7].valid);
- EXPECT_EQ(1, graph[1].aop.op.src_extents_size());
- EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).start_block());
- EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).num_blocks());
- EXPECT_EQ(InstallOperation::REPLACE_BZ, graph[5].aop.op.type());
-}
-
-TEST_F(InplaceGeneratorTest, MoveAndSortFullOpsToBackTest) {
- Graph graph(4);
- graph[0].aop.name = "A";
- graph[0].aop.op.set_type(InstallOperation::REPLACE);
- graph[1].aop.name = "B";
- graph[1].aop.op.set_type(InstallOperation::BSDIFF);
- graph[2].aop.name = "C";
- graph[2].aop.op.set_type(InstallOperation::REPLACE_BZ);
- graph[3].aop.name = "D";
- graph[3].aop.op.set_type(InstallOperation::MOVE);
-
- vector<Vertex::Index> vect(graph.size());
-
- for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
- vect[i] = i;
- }
- InplaceGenerator::MoveAndSortFullOpsToBack(&graph, &vect);
- EXPECT_EQ(vect.size(), graph.size());
- EXPECT_EQ(graph[vect[0]].aop.name, "B");
- EXPECT_EQ(graph[vect[1]].aop.name, "D");
- EXPECT_EQ(graph[vect[2]].aop.name, "A");
- EXPECT_EQ(graph[vect[3]].aop.name, "C");
-}
-
-TEST_F(InplaceGeneratorTest, AssignTempBlocksTest) {
- Graph graph(9);
- const vector<Extent> empt; // empty
- const string kFilename = "/foo";
-
- // Some scratch space:
- GenVertex(&graph[0], empt, VectOfExt(200, 1), "", InstallOperation::REPLACE);
- GenVertex(&graph[1], empt, VectOfExt(210, 10), "", InstallOperation::REPLACE);
- GenVertex(&graph[2], empt, VectOfExt(220, 1), "", InstallOperation::REPLACE);
-
- // A cycle that requires 10 blocks to break:
- GenVertex(&graph[3],
- VectOfExt(10, 11),
- VectOfExt(0, 9),
- "",
- InstallOperation::BSDIFF);
- graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
- GenVertex(&graph[4],
- VectOfExt(0, 9),
- VectOfExt(10, 11),
- "",
- InstallOperation::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),
- "",
- InstallOperation::BSDIFF);
- graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
- GenVertex(&graph[6],
- VectOfExt(30, 10),
- VectOfExt(40, 11),
- "",
- InstallOperation::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),
- "",
- InstallOperation::BSDIFF);
- graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
- GenVertex(&graph[8],
- VectOfExt(60, 40),
- VectOfExt(120, 50),
- kFilename,
- InstallOperation::BSDIFF);
- graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
-
- graph_utils::DumpGraph(graph);
-
- vector<Vertex::Index> final_order;
-
- CreateBlobFile();
- EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
- "/dev/zero",
- blob_file_.get(),
- &final_order,
- Vertex::kInvalidIndex));
-
- Graph expected_graph(12);
- GenVertex(&expected_graph[0],
- empt,
- VectOfExt(200, 1),
- "",
- InstallOperation::REPLACE);
- GenVertex(&expected_graph[1],
- empt,
- VectOfExt(210, 10),
- "",
- InstallOperation::REPLACE);
- GenVertex(&expected_graph[2],
- empt,
- VectOfExt(220, 1),
- "",
- InstallOperation::REPLACE);
- GenVertex(&expected_graph[3],
- VectOfExt(10, 11),
- VectOfExt(0, 9),
- "",
- InstallOperation::BSDIFF);
- expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
- GenVertex(&expected_graph[4],
- VectOfExt(60, 9),
- VectOfExt(10, 11),
- "",
- InstallOperation::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),
- "",
- InstallOperation::BSDIFF);
- expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
-
- GenVertex(&expected_graph[6],
- VectOfExt(60, 10),
- VectOfExt(40, 11),
- "",
- InstallOperation::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),
- "",
- InstallOperation::BSDIFF);
- expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
-
- GenVertex(&expected_graph[8],
- empt,
- VectOfExt(0, 50),
- "/foo",
- InstallOperation::REPLACE_BZ);
- expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
-
- GenVertex(&expected_graph[9],
- VectOfExt(0, 9),
- VectOfExt(60, 9),
- "",
- InstallOperation::MOVE);
-
- GenVertex(&expected_graph[10],
- VectOfExt(30, 10),
- VectOfExt(60, 10),
- "",
- InstallOperation::MOVE);
- expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
-
- EXPECT_EQ(12U, 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_F(InplaceGeneratorTest, CreateScratchNodeTest) {
- Vertex vertex;
- InplaceGenerator::CreateScratchNode(12, 34, &vertex);
- EXPECT_EQ(InstallOperation::REPLACE_BZ, vertex.aop.op.type());
- EXPECT_EQ(0U, vertex.aop.op.data_offset());
- EXPECT_EQ(0U, vertex.aop.op.data_length());
- EXPECT_EQ(1, vertex.aop.op.dst_extents_size());
- EXPECT_EQ(12U, vertex.aop.op.dst_extents(0).start_block());
- EXPECT_EQ(34U, vertex.aop.op.dst_extents(0).num_blocks());
-}
-
-TEST_F(InplaceGeneratorTest, ApplyMapTest) {
- vector<uint64_t> collection = {1, 2, 3, 4, 6};
- vector<uint64_t> expected_values = {1, 2, 5, 4, 8};
- map<uint64_t, uint64_t> value_map;
- value_map[3] = 5;
- value_map[6] = 8;
- value_map[5] = 10;
-
- InplaceGenerator::ApplyMap(&collection, value_map);
- EXPECT_EQ(expected_values, collection);
-}
-
-// We can't produce MOVE operations with a source or destination in the block 0.
-// This test checks that the cycle breaker procedure doesn't produce such
-// operations.
-TEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesAvoidMoveToZero) {
- size_t block_size = 4096;
- size_t num_blocks = 4;
- vector<AnnotatedOperation> aops;
-
- // Create a REPLACE_BZ for block 0, and a circular dependency among all other
- // blocks. This situation would prefer to issue a MOVE to scratch space and
- // the only available block is 0.
- aops.emplace_back();
- aops.back().name = base::StringPrintf("<bz-block-0>");
- aops.back().op.set_type(InstallOperation::REPLACE_BZ);
- StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents());
-
- for (size_t i = 1; i < num_blocks; i++) {
- AnnotatedOperation aop;
- aop.name = base::StringPrintf("<op-%" PRIuS ">", i);
- aop.op.set_type(InstallOperation::BSDIFF);
- StoreExtents({ExtentForRange(1 + i % (num_blocks - 1), 1)},
- aop.op.mutable_src_extents());
- StoreExtents({ExtentForRange(i, 1)}, aop.op.mutable_dst_extents());
- aops.push_back(aop);
- }
-
- PartitionConfig part("part");
- part.path = "/dev/zero";
- part.size = num_blocks * block_size;
-
- CreateBlobFile();
-
- // We ran two tests here. The first one without enough blocks for the scratch
- // space, forcing it to create a new full operation and the second case with
- // one extra block in the partition that can be used for the move operation.
- for (const auto part_blocks : vector<uint64_t>{num_blocks, num_blocks + 1}) {
- SCOPED_TRACE(
- base::StringPrintf("Using partition_blocks=%" PRIu64, part_blocks));
- vector<AnnotatedOperation> result_aops = aops;
- EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies(
- part,
- part,
- part_blocks * block_size,
- block_size,
- blob_file_.get(),
- &result_aops));
-
- size_t full_ops = 0;
- for (const auto& aop : result_aops) {
- if (diff_utils::IsAReplaceOperation(aop.op.type()))
- full_ops++;
-
- if (aop.op.type() != InstallOperation::MOVE)
- continue;
- for (const Extent& extent : aop.op.src_extents()) {
- EXPECT_NE(0U, extent.start_block())
- << "On src extents for aop: " << aop;
- }
- for (const Extent& extent : aop.op.dst_extents()) {
- EXPECT_NE(0U, extent.start_block())
- << "On dst extents for aop: " << aop;
- }
- }
-
- // If there's extra space in the partition, it should not use a new full
- // operation for it.
- EXPECT_EQ(part_blocks == num_blocks ? 2U : 1U, full_ops);
-
- DumpAopsOnFailure(result_aops);
- }
-}
-
-// Test that we can shrink a filesystem and break cycles.
-TEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesShrinkData) {
- size_t block_size = 4096;
- size_t old_blocks = 10;
- size_t new_blocks = 8;
- vector<AnnotatedOperation> aops;
-
- // Create a loop using the blocks 1-6 and one other operation writing to the
- // block 7 from outside the new partition. The loop in the blocks 1-6 uses
- // two-block operations, so it needs two blocks of scratch space. It can't use
- // the block 0 as scratch space (see previous test) and it can't use the
- // blocks 7 or 8 due the last move operation.
-
- aops.emplace_back();
- aops.back().name = base::StringPrintf("<bz-block-0>");
- aops.back().op.set_type(InstallOperation::REPLACE_BZ);
- StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents());
-
- const size_t num_ops = 3;
- for (size_t i = 0; i < num_ops; i++) {
- AnnotatedOperation aop;
- aop.name = base::StringPrintf("<op-%" PRIuS ">", i);
- aop.op.set_type(InstallOperation::BSDIFF);
- StoreExtents({ExtentForRange(1 + 2 * i, 2)}, aop.op.mutable_src_extents());
- StoreExtents({ExtentForRange(1 + 2 * ((i + 1) % num_ops), 2)},
- aop.op.mutable_dst_extents());
- aops.push_back(aop);
- }
-
- {
- AnnotatedOperation aop;
- aop.name = "<op-shrink>";
- aop.op.set_type(InstallOperation::BSDIFF);
- StoreExtents({ExtentForRange(8, 1)}, aop.op.mutable_src_extents());
- StoreExtents({ExtentForRange(7, 1)}, aop.op.mutable_dst_extents());
- aops.push_back(aop);
- }
-
- PartitionConfig old_part("part");
- old_part.path = "/dev/zero";
- old_part.size = old_blocks * block_size;
-
- PartitionConfig new_part("part");
- new_part.path = "/dev/zero";
- new_part.size = new_blocks * block_size;
-
- CreateBlobFile();
-
- EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies(
- old_part,
- new_part,
- (old_blocks + 2) * block_size, // enough scratch space.
- block_size,
- blob_file_.get(),
- &aops));
-
- size_t full_ops = 0;
- for (const auto& aop : aops) {
- if (diff_utils::IsAReplaceOperation(aop.op.type()))
- full_ops++;
- }
- // There should be only one REPLACE* operation, the one we added for block 0.
- EXPECT_EQ(1U, full_ops);
-
- // There should be only one MOVE operation, the one used to break the loop
- // which should write to scratch space past the block 7 (the last block of the
- // new partition) which is being written later.
- size_t move_ops = 0;
- for (const auto& aop : aops) {
- if (aop.op.type() == InstallOperation::MOVE) {
- move_ops++;
- for (const Extent& extent : aop.op.dst_extents()) {
- EXPECT_LE(7U, extent.start_block())
- << "On dst extents for aop: " << aop;
- }
- }
- }
- EXPECT_EQ(1U, move_ops);
-
- DumpAopsOnFailure(aops);
-}
-
-} // namespace chromeos_update_engine
diff --git a/payload_generator/payload_file.cc b/payload_generator/payload_file.cc
index a111fd6..69325d7 100644
--- a/payload_generator/payload_file.cc
+++ b/payload_generator/payload_file.cc
@@ -74,11 +74,9 @@
manifest_.set_block_size(config.block_size);
manifest_.set_max_timestamp(config.max_timestamp);
- if (major_version_ == kBrilloMajorPayloadVersion) {
- if (config.target.dynamic_partition_metadata != nullptr)
- *(manifest_.mutable_dynamic_partition_metadata()) =
- *(config.target.dynamic_partition_metadata);
- }
+ if (config.target.dynamic_partition_metadata != nullptr)
+ *(manifest_.mutable_dynamic_partition_metadata()) =
+ *(config.target.dynamic_partition_metadata);
return true;
}
@@ -86,13 +84,6 @@
bool PayloadFile::AddPartition(const PartitionConfig& old_conf,
const PartitionConfig& new_conf,
const vector<AnnotatedOperation>& aops) {
- // Check partitions order for Chrome OS
- if (major_version_ == kChromeOSMajorPayloadVersion) {
- const vector<const char*> part_order = {kPartitionNameRoot,
- kPartitionNameKernel};
- TEST_AND_RETURN_FALSE(part_vec_.size() < part_order.size());
- TEST_AND_RETURN_FALSE(new_conf.name == part_order[part_vec_.size()]);
- }
Partition part;
part.name = new_conf.name;
part.aops = aops;
@@ -134,66 +125,45 @@
}
// Copy the operations and partition info from the part_vec_ to the manifest.
- manifest_.clear_install_operations();
- manifest_.clear_kernel_install_operations();
manifest_.clear_partitions();
for (const auto& part : part_vec_) {
- if (major_version_ == kBrilloMajorPayloadVersion) {
- PartitionUpdate* partition = manifest_.add_partitions();
- partition->set_partition_name(part.name);
- if (part.postinstall.run) {
- partition->set_run_postinstall(true);
- if (!part.postinstall.path.empty())
- partition->set_postinstall_path(part.postinstall.path);
- if (!part.postinstall.filesystem_type.empty())
- partition->set_filesystem_type(part.postinstall.filesystem_type);
- partition->set_postinstall_optional(part.postinstall.optional);
+ PartitionUpdate* partition = manifest_.add_partitions();
+ partition->set_partition_name(part.name);
+ if (part.postinstall.run) {
+ partition->set_run_postinstall(true);
+ if (!part.postinstall.path.empty())
+ partition->set_postinstall_path(part.postinstall.path);
+ if (!part.postinstall.filesystem_type.empty())
+ partition->set_filesystem_type(part.postinstall.filesystem_type);
+ partition->set_postinstall_optional(part.postinstall.optional);
+ }
+ if (!part.verity.IsEmpty()) {
+ if (part.verity.hash_tree_extent.num_blocks() != 0) {
+ *partition->mutable_hash_tree_data_extent() =
+ part.verity.hash_tree_data_extent;
+ *partition->mutable_hash_tree_extent() = part.verity.hash_tree_extent;
+ partition->set_hash_tree_algorithm(part.verity.hash_tree_algorithm);
+ if (!part.verity.hash_tree_salt.empty())
+ partition->set_hash_tree_salt(part.verity.hash_tree_salt.data(),
+ part.verity.hash_tree_salt.size());
}
- if (!part.verity.IsEmpty()) {
- if (part.verity.hash_tree_extent.num_blocks() != 0) {
- *partition->mutable_hash_tree_data_extent() =
- part.verity.hash_tree_data_extent;
- *partition->mutable_hash_tree_extent() = part.verity.hash_tree_extent;
- partition->set_hash_tree_algorithm(part.verity.hash_tree_algorithm);
- if (!part.verity.hash_tree_salt.empty())
- partition->set_hash_tree_salt(part.verity.hash_tree_salt.data(),
- part.verity.hash_tree_salt.size());
- }
- if (part.verity.fec_extent.num_blocks() != 0) {
- *partition->mutable_fec_data_extent() = part.verity.fec_data_extent;
- *partition->mutable_fec_extent() = part.verity.fec_extent;
- partition->set_fec_roots(part.verity.fec_roots);
- }
- }
- for (const AnnotatedOperation& aop : part.aops) {
- *partition->add_operations() = aop.op;
- }
- if (part.old_info.has_size() || part.old_info.has_hash())
- *(partition->mutable_old_partition_info()) = part.old_info;
- if (part.new_info.has_size() || part.new_info.has_hash())
- *(partition->mutable_new_partition_info()) = part.new_info;
- } else {
- // major_version_ == kChromeOSMajorPayloadVersion
- if (part.name == kPartitionNameKernel) {
- for (const AnnotatedOperation& aop : part.aops)
- *manifest_.add_kernel_install_operations() = aop.op;
- if (part.old_info.has_size() || part.old_info.has_hash())
- *manifest_.mutable_old_kernel_info() = part.old_info;
- if (part.new_info.has_size() || part.new_info.has_hash())
- *manifest_.mutable_new_kernel_info() = part.new_info;
- } else {
- for (const AnnotatedOperation& aop : part.aops)
- *manifest_.add_install_operations() = aop.op;
- if (part.old_info.has_size() || part.old_info.has_hash())
- *manifest_.mutable_old_rootfs_info() = part.old_info;
- if (part.new_info.has_size() || part.new_info.has_hash())
- *manifest_.mutable_new_rootfs_info() = part.new_info;
+ if (part.verity.fec_extent.num_blocks() != 0) {
+ *partition->mutable_fec_data_extent() = part.verity.fec_data_extent;
+ *partition->mutable_fec_extent() = part.verity.fec_extent;
+ partition->set_fec_roots(part.verity.fec_roots);
}
}
+ for (const AnnotatedOperation& aop : part.aops) {
+ *partition->add_operations() = aop.op;
+ }
+ if (part.old_info.has_size() || part.old_info.has_hash())
+ *(partition->mutable_old_partition_info()) = part.old_info;
+ if (part.new_info.has_size() || part.new_info.has_hash())
+ *(partition->mutable_new_partition_info()) = part.new_info;
}
// Signatures appear at the end of the blobs. Note the offset in the
- // manifest_.
+ // |manifest_|.
uint64_t signature_blob_length = 0;
if (!private_key_path.empty()) {
TEST_AND_RETURN_FALSE(PayloadSigner::SignatureBlobLength(
@@ -201,7 +171,6 @@
PayloadSigner::AddSignatureToManifest(
next_blob_offset,
signature_blob_length,
- major_version_ == kChromeOSMajorPayloadVersion,
&manifest_);
}
@@ -229,18 +198,14 @@
TEST_AND_RETURN_FALSE(
WriteUint64AsBigEndian(&writer, serialized_manifest.size()));
- // Write metadata signature size.
- uint32_t metadata_signature_size = 0;
- if (major_version_ == kBrilloMajorPayloadVersion) {
- // Metadata signature has the same size as payload signature, because they
- // are both the same kind of signature for the same kind of hash.
- uint32_t metadata_signature_size = htobe32(signature_blob_length);
- TEST_AND_RETURN_FALSE_ERRNO(writer.Write(&metadata_signature_size,
- sizeof(metadata_signature_size)));
- metadata_size += sizeof(metadata_signature_size);
- // Set correct size instead of big endian size.
- metadata_signature_size = signature_blob_length;
- }
+ // Metadata signature has the same size as payload signature, because they
+ // are both the same kind of signature for the same kind of hash.
+ uint32_t metadata_signature_size = htobe32(signature_blob_length);
+ TEST_AND_RETURN_FALSE_ERRNO(
+ writer.Write(&metadata_signature_size, sizeof(metadata_signature_size)));
+ metadata_size += sizeof(metadata_signature_size);
+ // Set correct size instead of big endian size.
+ metadata_signature_size = signature_blob_length;
// Write protobuf
LOG(INFO) << "Writing final delta file protobuf... "
@@ -249,8 +214,7 @@
writer.Write(serialized_manifest.data(), serialized_manifest.size()));
// Write metadata signature blob.
- if (major_version_ == kBrilloMajorPayloadVersion &&
- !private_key_path.empty()) {
+ if (!private_key_path.empty()) {
brillo::Blob metadata_hash;
TEST_AND_RETURN_FALSE(HashCalculator::RawHashOfFile(
payload_file, metadata_size, &metadata_hash));
@@ -261,7 +225,7 @@
writer.Write(metadata_signature.data(), metadata_signature.size()));
}
- // Append the data blobs
+ // 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);
diff --git a/payload_generator/payload_generation_config.cc b/payload_generator/payload_generation_config.cc
index 88cca30..b653a03 100644
--- a/payload_generator/payload_generation_config.cc
+++ b/payload_generator/payload_generation_config.cc
@@ -32,6 +32,7 @@
#include "update_engine/payload_generator/ext2_filesystem.h"
#include "update_engine/payload_generator/mapfile_filesystem.h"
#include "update_engine/payload_generator/raw_filesystem.h"
+#include "update_engine/payload_generator/squashfs_filesystem.h"
using std::string;
@@ -86,6 +87,14 @@
return true;
}
+ fs_interface = SquashfsFilesystem::CreateFromFile(path,
+ /*extract_deflates=*/true,
+ /*load_settings=*/true);
+ if (fs_interface) {
+ TEST_AND_RETURN_FALSE(fs_interface->GetBlockSize() == kBlockSize);
+ return true;
+ }
+
// Fall back to a RAW filesystem.
TEST_AND_RETURN_FALSE(size % kBlockSize == 0);
fs_interface = RawFilesystem::Create(
@@ -219,10 +228,8 @@
}
bool PayloadVersion::Validate() const {
- TEST_AND_RETURN_FALSE(major == kChromeOSMajorPayloadVersion ||
- major == kBrilloMajorPayloadVersion);
+ TEST_AND_RETURN_FALSE(major == kBrilloMajorPayloadVersion);
TEST_AND_RETURN_FALSE(minor == kFullPayloadMinorVersion ||
- minor == kInPlaceMinorPayloadVersion ||
minor == kSourceMinorPayloadVersion ||
minor == kOpSrcHashMinorPayloadVersion ||
minor == kBrotliBsdiffMinorPayloadVersion ||
@@ -237,13 +244,10 @@
case InstallOperation::REPLACE:
case InstallOperation::REPLACE_BZ:
// These operations were included in the original payload format.
- return true;
-
case InstallOperation::REPLACE_XZ:
- // These operations are included in the major version used in Brillo, but
- // can also be used with minor version 3 or newer.
- return major == kBrilloMajorPayloadVersion ||
- minor >= kOpSrcHashMinorPayloadVersion;
+ // These operations are included minor version 3 or newer and full
+ // payloads.
+ return true;
case InstallOperation::ZERO:
case InstallOperation::DISCARD:
@@ -252,14 +256,6 @@
// them for delta payloads for now.
return minor >= kBrotliBsdiffMinorPayloadVersion;
- // Delta operations:
- case InstallOperation::MOVE:
- case InstallOperation::BSDIFF:
- // MOVE and BSDIFF were replaced by SOURCE_COPY and SOURCE_BSDIFF and
- // should not be used in newer delta versions, since the idempotent checks
- // were removed.
- return minor == kInPlaceMinorPayloadVersion;
-
case InstallOperation::SOURCE_COPY:
case InstallOperation::SOURCE_BSDIFF:
return minor >= kSourceMinorPayloadVersion;
@@ -269,6 +265,10 @@
case InstallOperation::PUFFDIFF:
return minor >= kPuffdiffMinorPayloadVersion;
+
+ case InstallOperation::MOVE:
+ case InstallOperation::BSDIFF:
+ NOTREACHED();
}
return false;
}
@@ -277,10 +277,6 @@
return minor != kFullPayloadMinorVersion;
}
-bool PayloadVersion::InplaceUpdate() const {
- return minor == kInPlaceMinorPayloadVersion;
-}
-
bool PayloadGenerationConfig::Validate() const {
TEST_AND_RETURN_FALSE(version.Validate());
TEST_AND_RETURN_FALSE(version.IsDelta() == is_delta);
@@ -307,11 +303,6 @@
for (const PartitionConfig& part : target.partitions) {
TEST_AND_RETURN_FALSE(part.ValidateExists());
TEST_AND_RETURN_FALSE(part.size % block_size == 0);
- if (version.minor == kInPlaceMinorPayloadVersion &&
- part.name == kPartitionNameRoot)
- TEST_AND_RETURN_FALSE(rootfs_partition_size >= part.size);
- if (version.major == kChromeOSMajorPayloadVersion)
- TEST_AND_RETURN_FALSE(part.postinstall.IsEmpty());
if (version.minor < kVerityMinorPayloadVersion)
TEST_AND_RETURN_FALSE(part.verity.IsEmpty());
}
diff --git a/payload_generator/payload_generation_config.h b/payload_generator/payload_generation_config.h
index e90edde..af6f181 100644
--- a/payload_generator/payload_generation_config.h
+++ b/payload_generator/payload_generation_config.h
@@ -173,10 +173,6 @@
// Whether this payload version is a delta payload.
bool IsDelta() const;
- // Tells whether the update is done in-place, that is, whether the operations
- // read and write from the same partition.
- bool InplaceUpdate() const;
-
// The major version of the payload.
uint64_t major;
diff --git a/payload_generator/payload_properties.cc b/payload_generator/payload_properties.cc
new file mode 100644
index 0000000..bc82eb7
--- /dev/null
+++ b/payload_generator/payload_properties.cc
@@ -0,0 +1,142 @@
+//
+// Copyright 2019 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#include "update_engine/payload_generator/payload_properties.h"
+
+#include <algorithm>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/json/json_writer.h>
+#include <base/strings/string_util.h>
+#include <base/values.h>
+#include <brillo/data_encoding.h>
+
+#include "update_engine/common/constants.h"
+#include "update_engine/common/hash_calculator.h"
+#include "update_engine/common/utils.h"
+#include "update_engine/payload_consumer/payload_metadata.h"
+#include "update_engine/update_metadata.pb.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+// These ones are needed by the GoldenEye.
+const char kPayloadPropertyJsonVersion[] = "version";
+const char kPayloadPropertyJsonPayloadHash[] = "sha256_hex";
+const char kPayloadPropertyJsonMetadataSize[] = "metadata_size";
+const char kPayloadPropertyJsonMetadataSignature[] = "metadata_signature";
+
+// These are needed by the Nebraska and devserver.
+const char kPayloadPropertyJsonPayloadSize[] = "size";
+const char kPayloadPropertyJsonIsDelta[] = "is_delta";
+const char kPayloadPropertyJsonTargetVersion[] = "target_version";
+const char kPayloadPropertyJsonSourceVersion[] = "source_version";
+} // namespace
+
+PayloadProperties::PayloadProperties(const string& payload_path)
+ : payload_path_(payload_path) {}
+
+bool PayloadProperties::GetPropertiesAsJson(string* json_str) {
+ TEST_AND_RETURN_FALSE(LoadFromPayload());
+
+ base::DictionaryValue properties;
+ properties.SetInteger(kPayloadPropertyJsonVersion, version_);
+ properties.SetInteger(kPayloadPropertyJsonMetadataSize, metadata_size_);
+ properties.SetString(kPayloadPropertyJsonMetadataSignature,
+ metadata_signatures_);
+ properties.SetInteger(kPayloadPropertyJsonPayloadSize, payload_size_);
+ properties.SetString(kPayloadPropertyJsonPayloadHash, payload_hash_);
+ properties.SetBoolean(kPayloadPropertyJsonIsDelta, is_delta_);
+ properties.SetString(kPayloadPropertyJsonTargetVersion, target_version_);
+ if (is_delta_) {
+ properties.SetString(kPayloadPropertyJsonSourceVersion, source_version_);
+ }
+
+ return base::JSONWriter::Write(properties, json_str);
+}
+
+bool PayloadProperties::GetPropertiesAsKeyValue(string* key_value_str) {
+ TEST_AND_RETURN_FALSE(LoadFromPayload());
+
+ brillo::KeyValueStore properties;
+ properties.SetString(kPayloadPropertyFileSize, std::to_string(payload_size_));
+ properties.SetString(kPayloadPropertyMetadataSize,
+ std::to_string(metadata_size_));
+ properties.SetString(kPayloadPropertyFileHash, payload_hash_);
+ properties.SetString(kPayloadPropertyMetadataHash, metadata_hash_);
+
+ *key_value_str = properties.SaveToString();
+ return true;
+}
+
+bool PayloadProperties::LoadFromPayload() {
+ PayloadMetadata payload_metadata;
+ DeltaArchiveManifest manifest;
+ Signatures metadata_signatures;
+ TEST_AND_RETURN_FALSE(payload_metadata.ParsePayloadFile(
+ payload_path_, &manifest, &metadata_signatures));
+
+ metadata_size_ = payload_metadata.GetMetadataSize();
+ payload_size_ = utils::FileSize(payload_path_);
+
+ brillo::Blob metadata_hash;
+ TEST_AND_RETURN_FALSE(HashCalculator::RawHashOfFile(
+ payload_path_, metadata_size_, &metadata_hash) ==
+ static_cast<off_t>(metadata_size_));
+ metadata_hash_ = brillo::data_encoding::Base64Encode(metadata_hash);
+
+ brillo::Blob payload_hash;
+ TEST_AND_RETURN_FALSE(HashCalculator::RawHashOfFile(
+ payload_path_, payload_size_, &payload_hash) ==
+ static_cast<off_t>(payload_size_));
+ payload_hash_ = brillo::data_encoding::Base64Encode(payload_hash);
+
+ if (payload_metadata.GetMetadataSignatureSize() > 0) {
+ TEST_AND_RETURN_FALSE(metadata_signatures.signatures_size() > 0);
+ vector<string> base64_signatures;
+ for (const auto& sig : metadata_signatures.signatures()) {
+ base64_signatures.push_back(
+ brillo::data_encoding::Base64Encode(sig.data()));
+ }
+ metadata_signatures_ = base::JoinString(base64_signatures, ":");
+ }
+
+ is_delta_ = manifest.has_old_image_info() ||
+ std::any_of(manifest.partitions().begin(),
+ manifest.partitions().end(),
+ [](const PartitionUpdate& part) {
+ return part.has_old_partition_info();
+ });
+
+ if (manifest.has_new_image_info()) {
+ target_version_ = manifest.new_image_info().version();
+ } else {
+ target_version_ = "99999.0.0";
+ }
+
+ // No need to set the source version if it was not a delta payload.
+ if (is_delta_ && manifest.has_old_image_info()) {
+ source_version_ = manifest.old_image_info().version();
+ }
+ return true;
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/payload_properties.h b/payload_generator/payload_properties.h
new file mode 100644
index 0000000..3b34511
--- /dev/null
+++ b/payload_generator/payload_properties.h
@@ -0,0 +1,73 @@
+//
+// Copyright 2019 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_PROPERTIES_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_PROPERTIES_H_
+
+#include <string>
+
+#include <brillo/key_value_store.h>
+#include <brillo/secure_blob.h>
+
+namespace chromeos_update_engine {
+
+// A class for extracting information about a payload from the payload file
+// itself. Currently the metadata can be exported as a json file or a key/value
+// properties file. But more can be added if required.
+class PayloadProperties {
+ public:
+ explicit PayloadProperties(const std::string& payload_path);
+ ~PayloadProperties() = default;
+
+ // Get the properties in a json format. The json file will be used in
+ // autotests, cros flash, etc. Mainly in Chrome OS.
+ bool GetPropertiesAsJson(std::string* json_str);
+
+ // Get the properties of the payload as a key/value store. This is mainly used
+ // in Android.
+ bool GetPropertiesAsKeyValue(std::string* key_value_str);
+
+ private:
+ // Does the main job of reading the payload and extracting information from
+ // it.
+ bool LoadFromPayload();
+
+ // The path to the payload file.
+ std::string payload_path_;
+
+ // The version of the metadata json format. If the output json file changes
+ // format, this needs to be increased.
+ int version_{2};
+
+ size_t metadata_size_;
+ std::string metadata_hash_;
+ std::string metadata_signatures_;
+
+ size_t payload_size_;
+ std::string payload_hash_;
+
+ // Whether the payload is a delta (true) or full (false).
+ bool is_delta_;
+
+ std::string target_version_;
+ std::string source_version_;
+
+ DISALLOW_COPY_AND_ASSIGN(PayloadProperties);
+};
+
+} // namespace chromeos_update_engine
+
+#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_PROPERTIES_H_
diff --git a/payload_generator/payload_properties_unittest.cc b/payload_generator/payload_properties_unittest.cc
new file mode 100644
index 0000000..db3902c
--- /dev/null
+++ b/payload_generator/payload_properties_unittest.cc
@@ -0,0 +1,144 @@
+//
+// Copyright (C) 2019 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#include "update_engine/payload_generator/payload_properties.h"
+
+#include <memory>
+#include <string>
+#include <vector>
+
+#include <base/files/file_util.h>
+#include <base/files/scoped_file.h>
+#include <base/files/scoped_temp_dir.h>
+#include <base/rand_util.h>
+#include <base/strings/stringprintf.h>
+#include <brillo/data_encoding.h>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/common/hash_calculator.h"
+#include "update_engine/common/test_utils.h"
+#include "update_engine/common/utils.h"
+#include "update_engine/payload_consumer/install_plan.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
+#include "update_engine/payload_generator/full_update_generator.h"
+#include "update_engine/payload_generator/operations_generator.h"
+#include "update_engine/payload_generator/payload_file.h"
+#include "update_engine/payload_generator/payload_generation_config.h"
+
+using chromeos_update_engine::test_utils::ScopedTempFile;
+using std::string;
+using std::unique_ptr;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+// TODO(kimjae): current implementation is very specific to a static way of
+// producing a deterministic test. It would definitely be beneficial to
+// extend the |PayloadPropertiesTest::SetUp()| into a generic helper or
+// seperate class that can handle creation of different |PayloadFile|s.
+class PayloadPropertiesTest : public ::testing::Test {
+ protected:
+ void SetUp() override {
+ PayloadGenerationConfig config;
+ config.version.major = kBrilloMajorPayloadVersion;
+ config.version.minor = kSourceMinorPayloadVersion;
+ config.source.image_info.set_version("123.0.0");
+ config.target.image_info.set_version("456.7.8");
+ PayloadFile payload;
+ EXPECT_TRUE(payload.Init(config));
+
+ const string kTempFileTemplate = "temp_data.XXXXXX";
+ int data_file_fd;
+ string temp_file_path;
+ EXPECT_TRUE(
+ utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &data_file_fd));
+ ScopedPathUnlinker temp_file_unlinker(temp_file_path);
+ EXPECT_LE(0, data_file_fd);
+
+ const auto SetupPartitionConfig =
+ [](PartitionConfig* config, const string& path, size_t size) {
+ config->path = path;
+ config->size = size;
+ };
+ const auto WriteZerosToFile = [](const char path[], size_t size) {
+ string zeros(size, '\0');
+ EXPECT_TRUE(utils::WriteFile(path, zeros.c_str(), zeros.size()));
+ };
+ ScopedTempFile old_part_file;
+ ScopedTempFile new_part_file;
+ PartitionConfig old_part(kPartitionNameRoot);
+ PartitionConfig new_part(kPartitionNameRoot);
+ SetupPartitionConfig(&old_part, old_part_file.path(), 0);
+ SetupPartitionConfig(&new_part, new_part_file.path(), 10000);
+ WriteZerosToFile(old_part_file.path().c_str(), old_part.size);
+ WriteZerosToFile(new_part_file.path().c_str(), new_part.size);
+
+ // Select payload generation strategy based on the config.
+ unique_ptr<OperationsGenerator> strategy(new FullUpdateGenerator());
+
+ vector<AnnotatedOperation> aops;
+ off_t data_file_size = 0;
+ BlobFileWriter blob_file_writer(data_file_fd, &data_file_size);
+ // Generate the operations using the strategy we selected above.
+ EXPECT_TRUE(strategy->GenerateOperations(
+ config, old_part, new_part, &blob_file_writer, &aops));
+
+ payload.AddPartition(old_part, new_part, aops);
+
+ uint64_t metadata_size;
+ EXPECT_TRUE(payload.WritePayload(
+ payload_file.path(), temp_file_path, "", &metadata_size));
+ }
+
+ ScopedTempFile payload_file;
+};
+
+// Validate the hash of file exists within the output.
+TEST_F(PayloadPropertiesTest, GetPropertiesAsJsonTestHash) {
+ constexpr char kJsonProperties[] =
+ "{"
+ R"("is_delta":true,)"
+ R"("metadata_signature":"",)"
+ R"("metadata_size":187,)"
+ R"("sha256_hex":"Rtrj9v3xXhrAi1741HAojtGxAQEOZ7mDyhzskIF4PJc=",)"
+ R"("size":233,)"
+ R"("source_version":"123.0.0",)"
+ R"("target_version":"456.7.8",)"
+ R"("version":2)"
+ "}";
+ string json;
+ EXPECT_TRUE(
+ PayloadProperties(payload_file.path()).GetPropertiesAsJson(&json));
+ EXPECT_EQ(kJsonProperties, json) << "JSON contents:\n" << json;
+}
+
+// Validate the hash of file and metadata are within the output.
+TEST_F(PayloadPropertiesTest, GetPropertiesAsKeyValueTestHash) {
+ constexpr char kKeyValueProperties[] =
+ "FILE_HASH=Rtrj9v3xXhrAi1741HAojtGxAQEOZ7mDyhzskIF4PJc=\n"
+ "FILE_SIZE=233\n"
+ "METADATA_HASH=kiXTexy/s2aPttf4+r8KRZWYZ6FYvwhU6rJGcnnI+U0=\n"
+ "METADATA_SIZE=187\n";
+ string key_value;
+ EXPECT_TRUE(PayloadProperties{payload_file.path()}.GetPropertiesAsKeyValue(
+ &key_value));
+ EXPECT_EQ(kKeyValueProperties, key_value) << "Key Value contents:\n"
+ << key_value;
+}
+
+} // namespace chromeos_update_engine
diff --git a/payload_generator/payload_signer.cc b/payload_generator/payload_signer.cc
index 72780b1..7e5fd4e 100644
--- a/payload_generator/payload_signer.cc
+++ b/payload_generator/payload_signer.cc
@@ -104,22 +104,20 @@
uint64_t metadata_size = payload_metadata.GetMetadataSize();
uint32_t metadata_signature_size =
payload_metadata.GetMetadataSignatureSize();
- if (payload_metadata.GetMajorVersion() == kBrilloMajorPayloadVersion) {
- // Write metadata signature size in header.
- uint32_t metadata_signature_size_be = htobe32(metadata_signature.size());
- memcpy(payload.data() + manifest_offset,
- &metadata_signature_size_be,
- sizeof(metadata_signature_size_be));
- manifest_offset += sizeof(metadata_signature_size_be);
- // Replace metadata signature.
- payload.erase(payload.begin() + metadata_size,
- payload.begin() + metadata_size + metadata_signature_size);
- payload.insert(payload.begin() + metadata_size,
- metadata_signature.begin(),
- metadata_signature.end());
- metadata_signature_size = metadata_signature.size();
- LOG(INFO) << "Metadata signature size: " << metadata_signature_size;
- }
+ // Write metadata signature size in header.
+ uint32_t metadata_signature_size_be = htobe32(metadata_signature.size());
+ memcpy(payload.data() + manifest_offset,
+ &metadata_signature_size_be,
+ sizeof(metadata_signature_size_be));
+ manifest_offset += sizeof(metadata_signature_size_be);
+ // Replace metadata signature.
+ payload.erase(payload.begin() + metadata_size,
+ payload.begin() + metadata_size + metadata_signature_size);
+ payload.insert(payload.begin() + metadata_size,
+ metadata_signature.begin(),
+ metadata_signature.end());
+ metadata_signature_size = metadata_signature.size();
+ LOG(INFO) << "Metadata signature size: " << metadata_signature_size;
DeltaArchiveManifest manifest;
TEST_AND_RETURN_FALSE(payload_metadata.GetManifest(payload, &manifest));
@@ -143,7 +141,6 @@
PayloadSigner::AddSignatureToManifest(
payload.size() - metadata_size - metadata_signature_size,
payload_signature.size(),
- payload_metadata.GetMajorVersion() == kChromeOSMajorPayloadVersion,
&manifest);
// Updates the payload to include the new manifest.
@@ -241,25 +238,12 @@
void PayloadSigner::AddSignatureToManifest(uint64_t signature_blob_offset,
uint64_t signature_blob_length,
- bool add_dummy_op,
DeltaArchiveManifest* manifest) {
LOG(INFO) << "Making room for signature in file";
manifest->set_signatures_offset(signature_blob_offset);
LOG(INFO) << "set? " << manifest->has_signatures_offset();
manifest->set_signatures_offset(signature_blob_offset);
manifest->set_signatures_size(signature_blob_length);
- // Add a dummy op at the end to appease older clients
- if (add_dummy_op) {
- InstallOperation* dummy_op = manifest->add_kernel_install_operations();
- dummy_op->set_type(InstallOperation::REPLACE);
- dummy_op->set_data_offset(signature_blob_offset);
- dummy_op->set_data_length(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(
- utils::DivRoundUp(signature_blob_length, kBlockSize));
- }
}
bool PayloadSigner::VerifySignedPayload(const string& payload_path,
@@ -512,35 +496,4 @@
return true;
}
-bool PayloadSigner::ExtractPayloadProperties(
- const string& payload_path, brillo::KeyValueStore* properties) {
- brillo::Blob payload;
- TEST_AND_RETURN_FALSE(
- utils::ReadFileChunk(payload_path, 0, kMaxPayloadHeaderSize, &payload));
-
- PayloadMetadata payload_metadata;
- TEST_AND_RETURN_FALSE(payload_metadata.ParsePayloadHeader(payload));
- uint64_t metadata_size = payload_metadata.GetMetadataSize();
-
- uint64_t file_size = utils::FileSize(payload_path);
- properties->SetString(kPayloadPropertyFileSize, std::to_string(file_size));
- properties->SetString(kPayloadPropertyMetadataSize,
- std::to_string(metadata_size));
-
- brillo::Blob file_hash, metadata_hash;
- TEST_AND_RETURN_FALSE(
- HashCalculator::RawHashOfFile(payload_path, file_size, &file_hash) ==
- static_cast<off_t>(file_size));
-
- TEST_AND_RETURN_FALSE(HashCalculator::RawHashOfFile(
- payload_path, metadata_size, &metadata_hash) ==
- static_cast<off_t>(metadata_size));
-
- properties->SetString(kPayloadPropertyFileHash,
- brillo::data_encoding::Base64Encode(file_hash));
- properties->SetString(kPayloadPropertyMetadataHash,
- brillo::data_encoding::Base64Encode(metadata_hash));
- return true;
-}
-
} // namespace chromeos_update_engine
diff --git a/payload_generator/payload_signer.h b/payload_generator/payload_signer.h
index bd1e32f..06e4823 100644
--- a/payload_generator/payload_signer.h
+++ b/payload_generator/payload_signer.h
@@ -39,12 +39,9 @@
static bool VerifySignedPayload(const std::string& payload_path,
const std::string& public_key_path);
- // Adds specified signature offset/length to given |manifest|, also adds a
- // dummy operation that points to a signature blob located at the specified
- // offset/length if |add_dummy_op| is true.
+ // Adds specified signature offset/length to given |manifest|.
static void AddSignatureToManifest(uint64_t signature_blob_offset,
uint64_t signature_blob_length,
- bool add_dummy_op,
DeltaArchiveManifest* manifest);
// Given a raw |hash| and a private key in |private_key_path| calculates the
diff --git a/payload_generator/payload_signer_unittest.cc b/payload_generator/payload_signer_unittest.cc
index bf7100b..fe62997 100644
--- a/payload_generator/payload_signer_unittest.cc
+++ b/payload_generator/payload_signer_unittest.cc
@@ -20,6 +20,7 @@
#include <vector>
#include <base/logging.h>
+#include <base/stl_util.h>
#include <gtest/gtest.h>
#include "update_engine/common/hash_calculator.h"
@@ -118,8 +119,8 @@
EXPECT_EQ(1, signatures.signatures_size());
const Signatures::Signature& sig = signatures.signatures(0);
const string& sig_data = sig.data();
- ASSERT_EQ(arraysize(kDataSignature), sig_data.size());
- for (size_t i = 0; i < arraysize(kDataSignature); i++) {
+ ASSERT_EQ(base::size(kDataSignature), sig_data.size());
+ for (size_t i = 0; i < base::size(kDataSignature); i++) {
EXPECT_EQ(kDataSignature[i], static_cast<uint8_t>(sig_data[i]));
}
}
diff --git a/payload_generator/squashfs_filesystem.cc b/payload_generator/squashfs_filesystem.cc
index 6c892f5..eb4fda3 100644
--- a/payload_generator/squashfs_filesystem.cc
+++ b/payload_generator/squashfs_filesystem.cc
@@ -23,6 +23,7 @@
#include <utility>
#include <base/files/file_util.h>
+#include <base/files/scoped_temp_dir.h>
#include <base/logging.h>
#include <base/strings/string_number_conversions.h>
#include <base/strings/string_split.h>
@@ -36,6 +37,8 @@
#include "update_engine/payload_generator/extent_utils.h"
#include "update_engine/update_metadata.pb.h"
+using base::FilePath;
+using base::ScopedTempDir;
using std::string;
using std::unique_ptr;
using std::vector;
@@ -49,6 +52,8 @@
constexpr uint64_t kSquashfsCompressedBit = 1 << 24;
constexpr uint32_t kSquashfsZlibCompression = 1;
+constexpr char kUpdateEngineConf[] = "etc/update_engine.conf";
+
bool ReadSquashfsHeader(const brillo::Blob blob,
SquashfsFilesystem::SquashfsHeader* header) {
if (blob.size() < kSquashfsSuperBlockSize) {
@@ -76,18 +81,59 @@
// Run unsquashfs to get the system file map.
// unsquashfs -m <map-file> <squashfs-file>
vector<string> cmd = {"unsquashfs", "-m", map_file, sqfs_path};
- string stdout;
+ string stdout, stderr;
int exit_code;
- if (!Subprocess::SynchronousExec(cmd, &exit_code, &stdout) ||
+ if (!Subprocess::SynchronousExec(cmd, &exit_code, &stdout, &stderr) ||
exit_code != 0) {
- LOG(ERROR) << "Failed to run unsquashfs -m. The stdout content was: "
- << stdout;
+ LOG(ERROR) << "Failed to run `unsquashfs -m` with stdout content: "
+ << stdout << " and stderr content: " << stderr;
return false;
}
TEST_AND_RETURN_FALSE(utils::ReadFile(map_file, map));
return true;
}
+bool GetUpdateEngineConfig(const std::string& sqfs_path, string* config) {
+ ScopedTempDir unsquash_dir;
+ if (!unsquash_dir.CreateUniqueTempDir()) {
+ PLOG(ERROR) << "Failed to create a temporary directory.";
+ return false;
+ }
+
+ // Run unsquashfs to extract update_engine.conf
+ // -f: To force overriding if the target directory exists.
+ // -d: The directory to unsquash the files.
+ vector<string> cmd = {"unsquashfs",
+ "-f",
+ "-d",
+ unsquash_dir.GetPath().value(),
+ sqfs_path,
+ kUpdateEngineConf};
+ string stdout, stderr;
+ int exit_code;
+ if (!Subprocess::SynchronousExec(cmd, &exit_code, &stdout, &stderr) ||
+ exit_code != 0) {
+ PLOG(ERROR) << "Failed to unsquashfs etc/update_engine.conf with stdout: "
+ << stdout << " and stderr: " << stderr;
+ return false;
+ }
+
+ auto config_path = unsquash_dir.GetPath().Append(kUpdateEngineConf);
+ string config_content;
+ if (!utils::ReadFile(config_path.value(), &config_content)) {
+ PLOG(ERROR) << "Failed to read " << config_path.value();
+ return false;
+ }
+
+ if (config_content.empty()) {
+ LOG(ERROR) << "update_engine config file was empty!!";
+ return false;
+ }
+
+ *config = std::move(config_content);
+ return true;
+}
+
} // namespace
bool SquashfsFilesystem::Init(const string& map,
@@ -120,6 +166,7 @@
uint64_t start;
TEST_AND_RETURN_FALSE(base::StringToUint64(splits[1], &start));
uint64_t cur_offset = start;
+ bool is_compressed = false;
for (size_t i = 2; i < splits.size(); ++i) {
uint64_t blk_size;
TEST_AND_RETURN_FALSE(base::StringToUint64(splits[i], &blk_size));
@@ -127,10 +174,11 @@
auto new_blk_size = blk_size & ~kSquashfsCompressedBit;
TEST_AND_RETURN_FALSE(new_blk_size <= header.block_size);
if (new_blk_size > 0 && !(blk_size & kSquashfsCompressedBit)) {
- // Compressed block
+ // It is a compressed block.
if (is_zlib && extract_deflates) {
zlib_blks.emplace_back(cur_offset, new_blk_size);
}
+ is_compressed = true;
}
cur_offset += new_blk_size;
}
@@ -140,6 +188,7 @@
File file;
file.name = splits[0].as_string();
file.extents = {ExtentForBytes(kBlockSize, start, cur_offset - start)};
+ file.is_compressed = is_compressed;
files_.emplace_back(file);
}
}
@@ -151,7 +200,8 @@
// If there is any overlap between two consecutive extents, remove them. Here
// we are assuming all files have exactly one extent. If this assumption
// changes then this implementation needs to change too.
- for (auto first = files_.begin(), second = first + 1;
+ for (auto first = files_.begin(),
+ second = first + (first == files_.end() ? 0 : 1);
first != files_.end() && second != files_.end();
second = first + 1) {
auto first_begin = first->extents[0].start_block();
@@ -217,6 +267,14 @@
return a.offset < b.offset;
});
+ // Sometimes a squashfs can have a two files that are hard linked. In this
+ // case both files will have the same starting offset in the image and hence
+ // the same zlib blocks. So we need to remove these duplicates to eliminate
+ // further potential probems. As a matter of fact the next statement will
+ // fail if there are duplicates (there will be overlap between two blocks).
+ auto last = std::unique(zlib_blks.begin(), zlib_blks.end());
+ zlib_blks.erase(last, zlib_blks.end());
+
// Sanity check. Make sure zlib blocks are not overlapping.
auto result = std::adjacent_find(
zlib_blks.begin(),
@@ -239,12 +297,12 @@
}
unique_ptr<SquashfsFilesystem> SquashfsFilesystem::CreateFromFile(
- const string& sqfs_path, bool extract_deflates) {
+ const string& sqfs_path, bool extract_deflates, bool load_settings) {
if (sqfs_path.empty())
return nullptr;
brillo::StreamPtr sqfs_file =
- brillo::FileStream::Open(base::FilePath(sqfs_path),
+ brillo::FileStream::Open(FilePath(sqfs_path),
brillo::Stream::AccessMode::READ,
brillo::FileStream::Disposition::OPEN_EXISTING,
nullptr);
@@ -278,6 +336,12 @@
return nullptr;
}
+ if (load_settings) {
+ if (!GetUpdateEngineConfig(sqfs_path, &sqfs->update_engine_config_)) {
+ return nullptr;
+ }
+ }
+
return sqfs;
}
@@ -311,9 +375,12 @@
}
bool SquashfsFilesystem::LoadSettings(brillo::KeyValueStore* store) const {
- // Settings not supported in squashfs.
- LOG(ERROR) << "squashfs doesn't support LoadSettings().";
- return false;
+ if (!store->LoadFromString(update_engine_config_)) {
+ LOG(ERROR) << "Failed to load the settings with config: "
+ << update_engine_config_;
+ return false;
+ }
+ return true;
}
bool SquashfsFilesystem::IsSquashfsImage(const brillo::Blob& blob) {
diff --git a/payload_generator/squashfs_filesystem.h b/payload_generator/squashfs_filesystem.h
index b79f8c7..5045dfc 100644
--- a/payload_generator/squashfs_filesystem.h
+++ b/payload_generator/squashfs_filesystem.h
@@ -59,7 +59,7 @@
// |extract_deflates| is true, it will process files to find location of all
// deflate streams.
static std::unique_ptr<SquashfsFilesystem> CreateFromFile(
- const std::string& sqfs_path, bool extract_deflates);
+ const std::string& sqfs_path, bool extract_deflates, bool load_settings);
// Creates the file system from a file map |filemap| which is a multi-line
// string with each line with the following format:
@@ -113,6 +113,9 @@
// All the files in the filesystem.
std::vector<File> files_;
+ // The content of /etc/update_engine.conf.
+ std::string update_engine_config_;
+
DISALLOW_COPY_AND_ASSIGN(SquashfsFilesystem);
};
diff --git a/payload_generator/squashfs_filesystem_unittest.cc b/payload_generator/squashfs_filesystem_unittest.cc
index 29fcf1c..68ca9df 100644
--- a/payload_generator/squashfs_filesystem_unittest.cc
+++ b/payload_generator/squashfs_filesystem_unittest.cc
@@ -112,7 +112,7 @@
#ifdef __CHROMEOS__
TEST_F(SquashfsFilesystemTest, EmptyFilesystemTest) {
unique_ptr<SquashfsFilesystem> fs = SquashfsFilesystem::CreateFromFile(
- GetBuildArtifactsPath("gen/disk_sqfs_empty.img"), true);
+ GetBuildArtifactsPath("gen/disk_sqfs_empty.img"), true, false);
CheckSquashfs(fs);
// Even an empty squashfs filesystem is rounded up to 4K.
@@ -133,7 +133,7 @@
TEST_F(SquashfsFilesystemTest, DefaultFilesystemTest) {
unique_ptr<SquashfsFilesystem> fs = SquashfsFilesystem::CreateFromFile(
- GetBuildArtifactsPath("gen/disk_sqfs_default.img"), true);
+ GetBuildArtifactsPath("gen/disk_sqfs_default.img"), true, false);
CheckSquashfs(fs);
vector<FilesystemInterface::File> files;
@@ -148,6 +148,18 @@
EXPECT_EQ(files[0].name, file.name);
EXPECT_EQ(files[0].extents, file.extents);
}
+
+TEST_F(SquashfsFilesystemTest, UpdateEngineConfigTest) {
+ unique_ptr<SquashfsFilesystem> fs = SquashfsFilesystem::CreateFromFile(
+ GetBuildArtifactsPath("gen/disk_sqfs_unittest.img"), true, true);
+ CheckSquashfs(fs);
+
+ brillo::KeyValueStore kvs;
+ EXPECT_TRUE(fs->LoadSettings(&kvs));
+ string minor_version;
+ EXPECT_TRUE(kvs.GetString("PAYLOAD_MINOR_VERSION", &minor_version));
+ EXPECT_EQ(minor_version, "1234");
+}
#endif // __CHROMEOS__
TEST_F(SquashfsFilesystemTest, SimpleFileMapTest) {
diff --git a/payload_generator/tarjan.cc b/payload_generator/tarjan.cc
deleted file mode 100644
index 2d4ca31..0000000
--- a/payload_generator/tarjan.cc
+++ /dev/null
@@ -1,83 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-#include "update_engine/payload_generator/tarjan.h"
-
-#include <algorithm>
-#include <vector>
-
-#include <base/logging.h>
-#include <base/stl_util.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 (base::ContainsValue(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 (base::ContainsValue(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
deleted file mode 100644
index 39ac4e4..0000000
--- a/payload_generator/tarjan.h
+++ /dev/null
@@ -1,53 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
-#define UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
-
-// This is an implementation 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 // UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
diff --git a/payload_generator/tarjan_unittest.cc b/payload_generator/tarjan_unittest.cc
deleted file mode 100644
index b271227..0000000
--- a/payload_generator/tarjan_unittest.cc
+++ /dev/null
@@ -1,94 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/tarjan.h"
-
-#include <string>
-#include <utility>
-
-#include <base/logging.h>
-#include <base/stl_util.h>
-#include <gtest/gtest.h>
-
-#include "update_engine/payload_generator/graph_types.h"
-
-using std::make_pair;
-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(5U, vertex_indexes.size());
- EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_a));
- EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_b));
- EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_c));
- EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_d));
- EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_e));
- }
-
- {
- vector<Vertex::Index> vertex_indexes;
- tarjan.Execute(n_f, &graph, &vertex_indexes);
-
- EXPECT_EQ(1U, vertex_indexes.size());
- EXPECT_TRUE(base::ContainsValue(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(2U, vertex_indexes.size());
- EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_g));
- EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_h));
- }
-}
-
-} // namespace chromeos_update_engine
diff --git a/payload_generator/topological_sort.cc b/payload_generator/topological_sort.cc
deleted file mode 100644
index 0abd708..0000000
--- a/payload_generator/topological_sort.cc
+++ /dev/null
@@ -1,57 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#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
deleted file mode 100644
index 461cbe1..0000000
--- a/payload_generator/topological_sort.h
+++ /dev/null
@@ -1,42 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
-#define 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 // UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
diff --git a/payload_generator/topological_sort_unittest.cc b/payload_generator/topological_sort_unittest.cc
deleted file mode 100644
index aa296d8..0000000
--- a/payload_generator/topological_sort_unittest.cc
+++ /dev/null
@@ -1,96 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/topological_sort.h"
-
-#include <utility>
-#include <vector>
-
-#include <gtest/gtest.h>
-
-#include "update_engine/payload_generator/graph_types.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