cycle_breaker_unittest.cc revision 3b2c7d0e6d859e6fc75c82b3417f87cf5968a49d 
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
3// found in the LICENSE file.
4
5#include "update_engine/payload_generator/cycle_breaker.h"
6
7#include <set>
8#include <string>
9#include <utility>
10#include <vector>
11
12#include <base/logging.h>
13#include <gtest/gtest.h>
14
15#include "update_engine/payload_generator/graph_types.h"
16#include "update_engine/utils.h"
17
18using std::make_pair;
19using std::pair;
20using std::set;
21using std::string;
22using std::vector;
23
24namespace chromeos_update_engine {
25
26namespace {
27void SetOpForNodes(Graph* graph) {
28  for (Vertex& vertex : *graph) {
29    vertex.aop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
30  }
31}
32}  // namespace
33
34class CycleBreakerTest : public ::testing::Test {};
35
36TEST(CycleBreakerTest, SimpleTest) {
37  int counter = 0;
38  const Vertex::Index n_a = counter++;
39  const Vertex::Index n_b = counter++;
40  const Vertex::Index n_c = counter++;
41  const Vertex::Index n_d = counter++;
42  const Vertex::Index n_e = counter++;
43  const Vertex::Index n_f = counter++;
44  const Vertex::Index n_g = counter++;
45  const Vertex::Index n_h = counter++;
46  const Graph::size_type kNodeCount = counter++;
47
48  Graph graph(kNodeCount);
49  SetOpForNodes(&graph);
50
51  graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties()));
52  graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties()));
53  graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
54  graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties()));
55  graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties()));
56  graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties()));
57  graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties()));
58  graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties()));
59  graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties()));
60  graph[n_f].out_edges.insert(make_pair(n_g, EdgeProperties()));
61  graph[n_g].out_edges.insert(make_pair(n_h, EdgeProperties()));
62  graph[n_h].out_edges.insert(make_pair(n_g, EdgeProperties()));
63
64  CycleBreaker breaker;
65
66  set<Edge> broken_edges;
67  breaker.BreakCycles(graph, &broken_edges);
68
69  // The following cycles must be cut:
70  // A->E->B
71  // C->D->E
72  // G->H
73
74  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_e)) ||
75              utils::SetContainsKey(broken_edges, make_pair(n_e, n_b)) ||
76              utils::SetContainsKey(broken_edges, make_pair(n_b, n_a)));
77  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_c, n_d)) ||
78              utils::SetContainsKey(broken_edges, make_pair(n_d, n_e)) ||
79              utils::SetContainsKey(broken_edges, make_pair(n_e, n_c)));
80  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_g, n_h)) ||
81              utils::SetContainsKey(broken_edges, make_pair(n_h, n_g)));
82  EXPECT_EQ(3, broken_edges.size());
83}
84
85namespace {
86pair<Vertex::Index, EdgeProperties> EdgeWithWeight(Vertex::Index dest,
87uint64_t weight) {
88  EdgeProperties props;
89  props.extents.resize(1);
90  props.extents[0].set_num_blocks(weight);
91  return make_pair(dest, props);
92}
93}  // namespace
94
95
96// This creates a bunch of cycles like this:
97//
98//               root <------.
99//    (t)->     / | \        |
100//             V  V  V       |
101//             N  N  N       |
102//              \ | /        |
103//               VVV         |
104//                N          |
105//              / | \        |
106//             V  V  V       |
107//             N  N  N       |
108//               ...         |
109//     (s)->    \ | /        |
110//               VVV         |
111//                N          |
112//                 \_________/
113//
114// such that the original cutting algo would cut edges (s). We changed
115// the algorithm to cut cycles (t) instead, since they are closer to the
116// root, and that can massively speed up cycle cutting.
117TEST(CycleBreakerTest, AggressiveCutTest) {
118  int counter = 0;
119
120  const int kNodesPerGroup = 4;
121  const int kGroups = 33;
122
123  Graph graph(kGroups * kNodesPerGroup + 1);  // + 1 for the root node
124  SetOpForNodes(&graph);
125
126  const Vertex::Index n_root = counter++;
127
128  Vertex::Index last_hub = n_root;
129  for (int i = 0; i < kGroups; i++) {
130    uint64_t weight = 5;
131    if (i == 0)
132      weight = 2;
133    else if (i == (kGroups - 1))
134      weight = 1;
135
136    const Vertex::Index next_hub = counter++;
137
138    for (int j = 0; j < (kNodesPerGroup - 1); j++) {
139      const Vertex::Index node = counter++;
140      graph[last_hub].out_edges.insert(EdgeWithWeight(node, weight));
141      graph[node].out_edges.insert(EdgeWithWeight(next_hub, weight));
142    }
143    last_hub = next_hub;
144  }
145
146  graph[last_hub].out_edges.insert(EdgeWithWeight(n_root, 5));
147
148  EXPECT_EQ(counter, graph.size());
149
150  CycleBreaker breaker;
151
152  set<Edge> broken_edges;
153  LOG(INFO) << "If this hangs for more than 1 second, the test has failed.";
154  breaker.BreakCycles(graph, &broken_edges);
155
156  set<Edge> expected_cuts;
157
158  for (Vertex::EdgeMap::const_iterator it = graph[n_root].out_edges.begin(),
159       e = graph[n_root].out_edges.end(); it != e; ++it) {
160    expected_cuts.insert(make_pair(n_root, it->first));
161  }
162
163  EXPECT_TRUE(broken_edges == expected_cuts);
164}
165
166TEST(CycleBreakerTest, WeightTest) {
167  int counter = 0;
168  const Vertex::Index n_a = counter++;
169  const Vertex::Index n_b = counter++;
170  const Vertex::Index n_c = counter++;
171  const Vertex::Index n_d = counter++;
172  const Vertex::Index n_e = counter++;
173  const Vertex::Index n_f = counter++;
174  const Vertex::Index n_g = counter++;
175  const Vertex::Index n_h = counter++;
176  const Vertex::Index n_i = counter++;
177  const Vertex::Index n_j = counter++;
178  const Graph::size_type kNodeCount = counter++;
179
180  Graph graph(kNodeCount);
181  SetOpForNodes(&graph);
182
183  graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 4));
184  graph[n_a].out_edges.insert(EdgeWithWeight(n_f, 3));
185  graph[n_a].out_edges.insert(EdgeWithWeight(n_h, 2));
186  graph[n_b].out_edges.insert(EdgeWithWeight(n_a, 3));
187  graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 4));
188  graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 5));
189  graph[n_c].out_edges.insert(EdgeWithWeight(n_d, 3));
190  graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 6));
191  graph[n_d].out_edges.insert(EdgeWithWeight(n_e, 3));
192  graph[n_e].out_edges.insert(EdgeWithWeight(n_d, 4));
193  graph[n_e].out_edges.insert(EdgeWithWeight(n_g, 5));
194  graph[n_f].out_edges.insert(EdgeWithWeight(n_g, 2));
195  graph[n_g].out_edges.insert(EdgeWithWeight(n_f, 3));
196  graph[n_g].out_edges.insert(EdgeWithWeight(n_d, 5));
197  graph[n_h].out_edges.insert(EdgeWithWeight(n_i, 8));
198  graph[n_i].out_edges.insert(EdgeWithWeight(n_e, 4));
199  graph[n_i].out_edges.insert(EdgeWithWeight(n_h, 9));
200  graph[n_i].out_edges.insert(EdgeWithWeight(n_j, 6));
201
202  CycleBreaker breaker;
203
204  set<Edge> broken_edges;
205  breaker.BreakCycles(graph, &broken_edges);
206
207  // These are required to be broken:
208  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_a)));
209  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_c)));
210  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_d, n_e)));
211  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_f, n_g)));
212  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_h, n_i)));
213}
214
215TEST(CycleBreakerTest, UnblockGraphTest) {
216  int counter = 0;
217  const Vertex::Index n_a = counter++;
218  const Vertex::Index n_b = counter++;
219  const Vertex::Index n_c = counter++;
220  const Vertex::Index n_d = counter++;
221  const Graph::size_type kNodeCount = counter++;
222
223  Graph graph(kNodeCount);
224  SetOpForNodes(&graph);
225
226  graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
227  graph[n_a].out_edges.insert(EdgeWithWeight(n_c, 1));
228  graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 2));
229  graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 2));
230  graph[n_b].out_edges.insert(EdgeWithWeight(n_d, 2));
231  graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 2));
232
233  CycleBreaker breaker;
234
235  set<Edge> broken_edges;
236  breaker.BreakCycles(graph, &broken_edges);
237
238  // These are required to be broken:
239  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_b)));
240  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_c)));
241}
242
243TEST(CycleBreakerTest, SkipOpsTest) {
244  int counter = 0;
245  const Vertex::Index n_a = counter++;
246  const Vertex::Index n_b = counter++;
247  const Vertex::Index n_c = counter++;
248  const Graph::size_type kNodeCount = counter++;
249
250  Graph graph(kNodeCount);
251  SetOpForNodes(&graph);
252  graph[n_a].aop.op.set_type(
253      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
254  graph[n_c].aop.op.set_type(
255      DeltaArchiveManifest_InstallOperation_Type_REPLACE);
256
257  graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
258  graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 1));
259
260  CycleBreaker breaker;
261
262  set<Edge> broken_edges;
263  breaker.BreakCycles(graph, &broken_edges);
264
265  EXPECT_EQ(2, breaker.skipped_ops());
266}
267
268}  // namespace chromeos_update_engine
269