AU: Cyclebreaker optimization
When using the cycle breaker, we know that operations that are full
(REPLACE, REPLACE_BZ) can't have any incoming edges, and thus can't be
in a cycle.
To help reduce CPU usage, change the cycle breaker to skip nodes that
are REPLACE or REPLACE_BZ.
BUG=7294
TEST=Attached unittests, generated delta update and applied it
Review URL: http://codereview.chromium.org/3618006
diff --git a/cycle_breaker_unittest.cc b/cycle_breaker_unittest.cc
index d06fe81..9922917 100644
--- a/cycle_breaker_unittest.cc
+++ b/cycle_breaker_unittest.cc
@@ -20,6 +20,14 @@
namespace chromeos_update_engine {
+namespace {
+void SetOpForNodes(Graph* graph) {
+ for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
+ it->op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+ }
+}
+} // namespace {}
+
class CycleBreakerTest : public ::testing::Test {};
TEST(CycleBreakerTest, SimpleTest) {
@@ -35,6 +43,7 @@
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()));
@@ -109,6 +118,7 @@
const int kGroups = 33;
Graph graph(kGroups * kNodesPerGroup + 1); // + 1 for the root node
+ SetOpForNodes(&graph);
const Vertex::Index n_root = counter++;
@@ -166,6 +176,7 @@
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));
@@ -208,6 +219,7 @@
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));
@@ -226,4 +238,27 @@
EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_c)));
}
+TEST(CycleBreakerTest, SkipOpsTest) {
+ int counter = 0;
+ const Vertex::Index n_a = counter++;
+ const Vertex::Index n_b = counter++;
+ const Vertex::Index n_c = counter++;
+ const Graph::size_type kNodeCount = counter++;
+
+ Graph graph(kNodeCount);
+ SetOpForNodes(&graph);
+ graph[n_a].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+ graph[n_c].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+
+ graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
+ graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 1));
+
+ CycleBreaker breaker;
+
+ set<Edge> broken_edges;
+ breaker.BreakCycles(graph, &broken_edges);
+
+ EXPECT_EQ(2, breaker.skipped_ops());
+}
+
} // namespace chromeos_update_engine