OLD | NEW |
1 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. | 1 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include <set> | 5 #include <set> |
6 #include <string> | 6 #include <string> |
7 #include <utility> | 7 #include <utility> |
8 #include <vector> | 8 #include <vector> |
9 #include <gtest/gtest.h> | 9 #include <gtest/gtest.h> |
10 #include "base/logging.h" | 10 #include "base/logging.h" |
11 #include "update_engine/cycle_breaker.h" | 11 #include "update_engine/cycle_breaker.h" |
12 #include "update_engine/graph_types.h" | 12 #include "update_engine/graph_types.h" |
13 #include "update_engine/utils.h" | 13 #include "update_engine/utils.h" |
14 | 14 |
15 using std::make_pair; | 15 using std::make_pair; |
16 using std::pair; | 16 using std::pair; |
17 using std::set; | 17 using std::set; |
18 using std::string; | 18 using std::string; |
19 using std::vector; | 19 using std::vector; |
20 | 20 |
21 namespace chromeos_update_engine { | 21 namespace chromeos_update_engine { |
22 | 22 |
| 23 namespace { |
| 24 void SetOpForNodes(Graph* graph) { |
| 25 for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) { |
| 26 it->op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE); |
| 27 } |
| 28 } |
| 29 } // namespace {} |
| 30 |
23 class CycleBreakerTest : public ::testing::Test {}; | 31 class CycleBreakerTest : public ::testing::Test {}; |
24 | 32 |
25 TEST(CycleBreakerTest, SimpleTest) { | 33 TEST(CycleBreakerTest, SimpleTest) { |
26 int counter = 0; | 34 int counter = 0; |
27 const Vertex::Index n_a = counter++; | 35 const Vertex::Index n_a = counter++; |
28 const Vertex::Index n_b = counter++; | 36 const Vertex::Index n_b = counter++; |
29 const Vertex::Index n_c = counter++; | 37 const Vertex::Index n_c = counter++; |
30 const Vertex::Index n_d = counter++; | 38 const Vertex::Index n_d = counter++; |
31 const Vertex::Index n_e = counter++; | 39 const Vertex::Index n_e = counter++; |
32 const Vertex::Index n_f = counter++; | 40 const Vertex::Index n_f = counter++; |
33 const Vertex::Index n_g = counter++; | 41 const Vertex::Index n_g = counter++; |
34 const Vertex::Index n_h = counter++; | 42 const Vertex::Index n_h = counter++; |
35 const Graph::size_type kNodeCount = counter++; | 43 const Graph::size_type kNodeCount = counter++; |
36 | 44 |
37 Graph graph(kNodeCount); | 45 Graph graph(kNodeCount); |
| 46 SetOpForNodes(&graph); |
38 | 47 |
39 graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties())); | 48 graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties())); |
40 graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties())); | 49 graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties())); |
41 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); | 50 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); |
42 graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties())); | 51 graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties())); |
43 graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties())); | 52 graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties())); |
44 graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties())); | 53 graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties())); |
45 graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties())); | 54 graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties())); |
46 graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties())); | 55 graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties())); |
47 graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties())); | 56 graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties())); |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
102 // such that the original cutting algo would cut edges (s). We changed | 111 // such that the original cutting algo would cut edges (s). We changed |
103 // the algorithm to cut cycles (t) instead, since they are closer to the | 112 // the algorithm to cut cycles (t) instead, since they are closer to the |
104 // root, and that can massively speed up cycle cutting. | 113 // root, and that can massively speed up cycle cutting. |
105 TEST(CycleBreakerTest, AggressiveCutTest) { | 114 TEST(CycleBreakerTest, AggressiveCutTest) { |
106 int counter = 0; | 115 int counter = 0; |
107 | 116 |
108 const int kNodesPerGroup = 4; | 117 const int kNodesPerGroup = 4; |
109 const int kGroups = 33; | 118 const int kGroups = 33; |
110 | 119 |
111 Graph graph(kGroups * kNodesPerGroup + 1); // + 1 for the root node | 120 Graph graph(kGroups * kNodesPerGroup + 1); // + 1 for the root node |
| 121 SetOpForNodes(&graph); |
112 | 122 |
113 const Vertex::Index n_root = counter++; | 123 const Vertex::Index n_root = counter++; |
114 | 124 |
115 Vertex::Index last_hub = n_root; | 125 Vertex::Index last_hub = n_root; |
116 for (int i = 0; i < kGroups; i++) { | 126 for (int i = 0; i < kGroups; i++) { |
117 uint64_t weight = 5; | 127 uint64_t weight = 5; |
118 if (i == 0) | 128 if (i == 0) |
119 weight = 2; | 129 weight = 2; |
120 else if (i == (kGroups - 1)) | 130 else if (i == (kGroups - 1)) |
121 weight = 1; | 131 weight = 1; |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
159 const Vertex::Index n_d = counter++; | 169 const Vertex::Index n_d = counter++; |
160 const Vertex::Index n_e = counter++; | 170 const Vertex::Index n_e = counter++; |
161 const Vertex::Index n_f = counter++; | 171 const Vertex::Index n_f = counter++; |
162 const Vertex::Index n_g = counter++; | 172 const Vertex::Index n_g = counter++; |
163 const Vertex::Index n_h = counter++; | 173 const Vertex::Index n_h = counter++; |
164 const Vertex::Index n_i = counter++; | 174 const Vertex::Index n_i = counter++; |
165 const Vertex::Index n_j = counter++; | 175 const Vertex::Index n_j = counter++; |
166 const Graph::size_type kNodeCount = counter++; | 176 const Graph::size_type kNodeCount = counter++; |
167 | 177 |
168 Graph graph(kNodeCount); | 178 Graph graph(kNodeCount); |
| 179 SetOpForNodes(&graph); |
169 | 180 |
170 graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 4)); | 181 graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 4)); |
171 graph[n_a].out_edges.insert(EdgeWithWeight(n_f, 3)); | 182 graph[n_a].out_edges.insert(EdgeWithWeight(n_f, 3)); |
172 graph[n_a].out_edges.insert(EdgeWithWeight(n_h, 2)); | 183 graph[n_a].out_edges.insert(EdgeWithWeight(n_h, 2)); |
173 graph[n_b].out_edges.insert(EdgeWithWeight(n_a, 3)); | 184 graph[n_b].out_edges.insert(EdgeWithWeight(n_a, 3)); |
174 graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 4)); | 185 graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 4)); |
175 graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 5)); | 186 graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 5)); |
176 graph[n_c].out_edges.insert(EdgeWithWeight(n_d, 3)); | 187 graph[n_c].out_edges.insert(EdgeWithWeight(n_d, 3)); |
177 graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 6)); | 188 graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 6)); |
178 graph[n_d].out_edges.insert(EdgeWithWeight(n_e, 3)); | 189 graph[n_d].out_edges.insert(EdgeWithWeight(n_e, 3)); |
(...skipping 22 matching lines...) Expand all Loading... |
201 | 212 |
202 TEST(CycleBreakerTest, UnblockGraphTest) { | 213 TEST(CycleBreakerTest, UnblockGraphTest) { |
203 int counter = 0; | 214 int counter = 0; |
204 const Vertex::Index n_a = counter++; | 215 const Vertex::Index n_a = counter++; |
205 const Vertex::Index n_b = counter++; | 216 const Vertex::Index n_b = counter++; |
206 const Vertex::Index n_c = counter++; | 217 const Vertex::Index n_c = counter++; |
207 const Vertex::Index n_d = counter++; | 218 const Vertex::Index n_d = counter++; |
208 const Graph::size_type kNodeCount = counter++; | 219 const Graph::size_type kNodeCount = counter++; |
209 | 220 |
210 Graph graph(kNodeCount); | 221 Graph graph(kNodeCount); |
| 222 SetOpForNodes(&graph); |
211 | 223 |
212 graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1)); | 224 graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1)); |
213 graph[n_a].out_edges.insert(EdgeWithWeight(n_c, 1)); | 225 graph[n_a].out_edges.insert(EdgeWithWeight(n_c, 1)); |
214 graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 2)); | 226 graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 2)); |
215 graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 2)); | 227 graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 2)); |
216 graph[n_b].out_edges.insert(EdgeWithWeight(n_d, 2)); | 228 graph[n_b].out_edges.insert(EdgeWithWeight(n_d, 2)); |
217 graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 2)); | 229 graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 2)); |
218 | 230 |
219 CycleBreaker breaker; | 231 CycleBreaker breaker; |
220 | 232 |
221 set<Edge> broken_edges; | 233 set<Edge> broken_edges; |
222 breaker.BreakCycles(graph, &broken_edges); | 234 breaker.BreakCycles(graph, &broken_edges); |
223 | 235 |
224 // These are required to be broken: | 236 // These are required to be broken: |
225 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_b))); | 237 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_b))); |
226 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_c))); | 238 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_c))); |
227 } | 239 } |
228 | 240 |
| 241 TEST(CycleBreakerTest, SkipOpsTest) { |
| 242 int counter = 0; |
| 243 const Vertex::Index n_a = counter++; |
| 244 const Vertex::Index n_b = counter++; |
| 245 const Vertex::Index n_c = counter++; |
| 246 const Graph::size_type kNodeCount = counter++; |
| 247 |
| 248 Graph graph(kNodeCount); |
| 249 SetOpForNodes(&graph); |
| 250 graph[n_a].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ); |
| 251 graph[n_c].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE); |
| 252 |
| 253 graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1)); |
| 254 graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 1)); |
| 255 |
| 256 CycleBreaker breaker; |
| 257 |
| 258 set<Edge> broken_edges; |
| 259 breaker.BreakCycles(graph, &broken_edges); |
| 260 |
| 261 EXPECT_EQ(2, breaker.skipped_ops()); |
| 262 } |
| 263 |
229 } // namespace chromeos_update_engine | 264 } // namespace chromeos_update_engine |
OLD | NEW |