1 /*
2 * Copyright (C) 2019 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "src/trace_processor/importers/proto/heap_graph_walker.h"
18
19 #include "perfetto/base/logging.h"
20 #include "test/gtest_and_gmock.h"
21
22 namespace perfetto {
23 namespace trace_processor {
24 namespace {
25
26 using ::testing::UnorderedElementsAre;
27 using ::testing::UnorderedElementsAreArray;
28
29 class HeapGraphWalkerTestDelegate : public HeapGraphWalker::Delegate {
30 public:
31 ~HeapGraphWalkerTestDelegate() override = default;
32
MarkReachable(int64_t row)33 void MarkReachable(int64_t row) override { reachable_.emplace(row); }
34
SetRetained(int64_t row,int64_t retained,int64_t unique_retained)35 void SetRetained(int64_t row,
36 int64_t retained,
37 int64_t unique_retained) override {
38 bool inserted;
39 std::tie(std::ignore, inserted) = retained_.emplace(row, retained);
40 PERFETTO_CHECK(inserted);
41 std::tie(std::ignore, inserted) =
42 unique_retained_.emplace(row, unique_retained);
43 PERFETTO_CHECK(inserted);
44 }
45
Reachable(int64_t row)46 bool Reachable(int64_t row) {
47 return reachable_.find(row) != reachable_.end();
48 }
49
Retained(int64_t row)50 int64_t Retained(int64_t row) {
51 auto it = retained_.find(row);
52 PERFETTO_CHECK(it != retained_.end());
53 return it->second;
54 }
55
UniqueRetained(int64_t row)56 int64_t UniqueRetained(int64_t row) {
57 auto it = unique_retained_.find(row);
58 PERFETTO_CHECK(it != unique_retained_.end());
59 return it->second;
60 }
61
62 private:
63 std::map<int64_t, int64_t> retained_;
64 std::map<int64_t, int64_t> unique_retained_;
65 std::set<int64_t> reachable_;
66 };
67
68 // 1 |
69 // ^^ |
70 // / \ |
71 // 2 3 |
72 // ^ ^ |
73 // \ / |
74 // 4R |
TEST(HeapGraphWalkerTest,Diamond)75 TEST(HeapGraphWalkerTest, Diamond) {
76 HeapGraphWalkerTestDelegate delegate;
77 HeapGraphWalker walker(&delegate);
78 walker.AddNode(1, 1);
79 walker.AddNode(2, 2);
80 walker.AddNode(3, 3);
81 walker.AddNode(4, 4);
82
83 walker.AddEdge(2, 1);
84 walker.AddEdge(3, 1);
85 walker.AddEdge(4, 2);
86 walker.AddEdge(4, 3);
87
88 walker.MarkRoot(4);
89 walker.CalculateRetained();
90
91 EXPECT_EQ(delegate.Retained(1), 1);
92 EXPECT_EQ(delegate.Retained(2), 3);
93 EXPECT_EQ(delegate.Retained(3), 4);
94 EXPECT_EQ(delegate.Retained(4), 10);
95
96 EXPECT_EQ(delegate.UniqueRetained(1), 1);
97 EXPECT_EQ(delegate.UniqueRetained(2), 2);
98 EXPECT_EQ(delegate.UniqueRetained(3), 3);
99 EXPECT_EQ(delegate.UniqueRetained(4), 10);
100 }
101
102 // 1 2 |
103 // ^ ^ |
104 // \ / |
105 // 3R<->4 |
TEST(HeapGraphWalkerTest,Loop)106 TEST(HeapGraphWalkerTest, Loop) {
107 HeapGraphWalkerTestDelegate delegate;
108 HeapGraphWalker walker(&delegate);
109 walker.AddNode(1, 1);
110 walker.AddNode(2, 2);
111 walker.AddNode(3, 3);
112 walker.AddNode(4, 4);
113
114 walker.AddEdge(3, 1);
115 walker.AddEdge(3, 4);
116 walker.AddEdge(4, 2);
117 walker.AddEdge(4, 3);
118
119 walker.MarkRoot(3);
120 walker.CalculateRetained();
121
122 EXPECT_EQ(delegate.Retained(1), 1);
123 EXPECT_EQ(delegate.Retained(2), 2);
124 EXPECT_EQ(delegate.Retained(3), 10);
125 EXPECT_EQ(delegate.Retained(4), 10);
126
127 EXPECT_EQ(delegate.UniqueRetained(1), 1);
128 EXPECT_EQ(delegate.UniqueRetained(2), 2);
129 EXPECT_EQ(delegate.UniqueRetained(3), 4);
130 EXPECT_EQ(delegate.UniqueRetained(4), 6);
131 }
132
133 // 1R |
134 // ^\ |
135 // / v |
136 // 3<-2 |
TEST(HeapGraphWalkerTest,Triangle)137 TEST(HeapGraphWalkerTest, Triangle) {
138 HeapGraphWalkerTestDelegate delegate;
139 HeapGraphWalker walker(&delegate);
140 walker.AddNode(1, 1);
141 walker.AddNode(2, 2);
142 walker.AddNode(3, 3);
143
144 walker.AddEdge(1, 2);
145 walker.AddEdge(2, 3);
146 walker.AddEdge(3, 1);
147
148 walker.MarkRoot(1);
149 walker.CalculateRetained();
150
151 EXPECT_EQ(delegate.Retained(1), 6);
152 EXPECT_EQ(delegate.Retained(2), 6);
153 EXPECT_EQ(delegate.Retained(3), 6);
154
155 EXPECT_EQ(delegate.UniqueRetained(1), 1);
156 EXPECT_EQ(delegate.UniqueRetained(2), 2);
157 EXPECT_EQ(delegate.UniqueRetained(3), 3);
158 }
159
160 // 1 |
161 // ^ |
162 // | |
163 // 2 4 |
164 // ^ ^ |
165 // | | |
166 // 3R 5 |
TEST(HeapGraphWalkerTest,Disconnected)167 TEST(HeapGraphWalkerTest, Disconnected) {
168 HeapGraphWalkerTestDelegate delegate;
169 HeapGraphWalker walker(&delegate);
170 walker.AddNode(1, 1);
171 walker.AddNode(2, 2);
172 walker.AddNode(3, 3);
173 walker.AddNode(4, 4);
174 walker.AddNode(5, 5);
175
176 walker.AddEdge(2, 1);
177 walker.AddEdge(3, 2);
178 walker.AddEdge(5, 4);
179
180 walker.MarkRoot(3);
181 walker.CalculateRetained();
182
183 EXPECT_EQ(delegate.Retained(1), 1);
184 EXPECT_EQ(delegate.Retained(2), 3);
185 EXPECT_EQ(delegate.Retained(3), 6);
186
187 EXPECT_EQ(delegate.UniqueRetained(1), 1);
188 EXPECT_EQ(delegate.UniqueRetained(2), 3);
189 EXPECT_EQ(delegate.UniqueRetained(3), 6);
190
191 EXPECT_TRUE(delegate.Reachable(1));
192 EXPECT_TRUE(delegate.Reachable(2));
193 EXPECT_TRUE(delegate.Reachable(3));
194 EXPECT_FALSE(delegate.Reachable(4));
195 EXPECT_FALSE(delegate.Reachable(5));
196 }
197
198 // 1 |
199 // ^^ |
200 // / \ |
201 // 2 3 |
202 // ^ ^^ |
203 // |/ | |
204 // 4 5 |
205 // ^ ^ |
206 // \ / |
207 // 6R |
TEST(HeapGraphWalkerTest,Complex)208 TEST(HeapGraphWalkerTest, Complex) {
209 HeapGraphWalkerTestDelegate delegate;
210 HeapGraphWalker walker(&delegate);
211 walker.AddNode(1, 1);
212 walker.AddNode(2, 2);
213 walker.AddNode(3, 3);
214 walker.AddNode(4, 4);
215 walker.AddNode(5, 5);
216 walker.AddNode(6, 6);
217
218 walker.AddEdge(2, 1);
219 walker.AddEdge(3, 1);
220 walker.AddEdge(4, 2);
221 walker.AddEdge(4, 3);
222 walker.AddEdge(5, 3);
223 walker.AddEdge(6, 4);
224 walker.AddEdge(6, 5);
225
226 walker.MarkRoot(6);
227 walker.CalculateRetained();
228
229 EXPECT_EQ(delegate.Retained(1), 1);
230 EXPECT_EQ(delegate.Retained(2), 3);
231 EXPECT_EQ(delegate.Retained(3), 4);
232 EXPECT_EQ(delegate.Retained(4), 10);
233 EXPECT_EQ(delegate.Retained(5), 9);
234 EXPECT_EQ(delegate.Retained(6), 21);
235
236 EXPECT_EQ(delegate.UniqueRetained(1), 1);
237 EXPECT_EQ(delegate.UniqueRetained(2), 2);
238 EXPECT_EQ(delegate.UniqueRetained(3), 3);
239 EXPECT_EQ(delegate.UniqueRetained(4), 6);
240 EXPECT_EQ(delegate.UniqueRetained(5), 5);
241 EXPECT_EQ(delegate.UniqueRetained(6), 21);
242 }
243
244 // 1 |
245 // ^^ |
246 // / \ |
247 // 2<-> 3 |
248 // ^ |
249 // | |
250 // 4R |
TEST(HeapGraphWalkerTest,SharedInComponent)251 TEST(HeapGraphWalkerTest, SharedInComponent) {
252 HeapGraphWalkerTestDelegate delegate;
253 HeapGraphWalker walker(&delegate);
254 walker.AddNode(1, 1);
255 walker.AddNode(2, 2);
256 walker.AddNode(3, 3);
257 walker.AddNode(4, 4);
258
259 walker.AddEdge(2, 1);
260 walker.AddEdge(2, 3);
261 walker.AddEdge(3, 1);
262 walker.AddEdge(3, 2);
263 walker.AddEdge(4, 2);
264
265 walker.MarkRoot(4);
266 walker.CalculateRetained();
267
268 EXPECT_EQ(delegate.Retained(1), 1);
269 EXPECT_EQ(delegate.Retained(2), 6);
270 EXPECT_EQ(delegate.Retained(3), 6);
271 EXPECT_EQ(delegate.Retained(4), 10);
272
273 EXPECT_EQ(delegate.UniqueRetained(1), 1);
274 // TODO(fmayer): this should be 6, as it breaks away the component.
275 EXPECT_EQ(delegate.UniqueRetained(2), 2);
276 EXPECT_EQ(delegate.UniqueRetained(3), 3);
277 EXPECT_EQ(delegate.UniqueRetained(4), 10);
278 }
279
280 // 1 <- 2 |
281 // ^ ^ |
282 // | | |
283 // 3<-> 4R |
TEST(HeapGraphWalkerTest,TwoPaths)284 TEST(HeapGraphWalkerTest, TwoPaths) {
285 HeapGraphWalkerTestDelegate delegate;
286 HeapGraphWalker walker(&delegate);
287 walker.AddNode(1, 1);
288 walker.AddNode(2, 2);
289 walker.AddNode(3, 3);
290 walker.AddNode(4, 4);
291
292 walker.AddEdge(2, 1);
293 walker.AddEdge(3, 1);
294 walker.AddEdge(3, 4);
295 walker.AddEdge(4, 2);
296 walker.AddEdge(4, 3);
297
298 walker.MarkRoot(4);
299 walker.CalculateRetained();
300
301 EXPECT_EQ(delegate.Retained(1), 1);
302 EXPECT_EQ(delegate.Retained(2), 3);
303 EXPECT_EQ(delegate.Retained(3), 10);
304 EXPECT_EQ(delegate.Retained(4), 10);
305
306 EXPECT_EQ(delegate.UniqueRetained(1), 1);
307 EXPECT_EQ(delegate.UniqueRetained(2), 2);
308 EXPECT_EQ(delegate.UniqueRetained(3), 3);
309 EXPECT_EQ(delegate.UniqueRetained(4), 6);
310 }
311
312 // 1 |
313 // ^^ |
314 // / \ |
315 // 2R 3R |
TEST(HeapGraphWalkerTest,Diverge)316 TEST(HeapGraphWalkerTest, Diverge) {
317 HeapGraphWalkerTestDelegate delegate;
318 HeapGraphWalker walker(&delegate);
319 walker.AddNode(1, 1);
320 walker.AddNode(2, 2);
321 walker.AddNode(3, 3);
322
323 walker.AddEdge(2, 1);
324 walker.AddEdge(3, 1);
325
326 walker.MarkRoot(2);
327 walker.MarkRoot(3);
328 walker.CalculateRetained();
329
330 EXPECT_EQ(delegate.Retained(1), 1);
331 EXPECT_EQ(delegate.Retained(2), 3);
332 EXPECT_EQ(delegate.Retained(3), 4);
333
334 EXPECT_EQ(delegate.UniqueRetained(1), 1);
335 EXPECT_EQ(delegate.UniqueRetained(2), 2);
336 EXPECT_EQ(delegate.UniqueRetained(3), 3);
337 }
338
339 // 1 |
340 // ^^ |
341 // / \ |
342 // 2R 3 (dead) |
TEST(HeapGraphWalkerTest,Dead)343 TEST(HeapGraphWalkerTest, Dead) {
344 HeapGraphWalkerTestDelegate delegate;
345 HeapGraphWalker walker(&delegate);
346 walker.AddNode(1, 1);
347 walker.AddNode(2, 2);
348 walker.AddNode(3, 3);
349
350 walker.AddEdge(2, 1);
351 walker.AddEdge(3, 1);
352
353 walker.MarkRoot(2);
354 walker.CalculateRetained();
355
356 EXPECT_EQ(delegate.Retained(1), 1);
357 EXPECT_EQ(delegate.Retained(2), 3);
358
359 EXPECT_EQ(delegate.UniqueRetained(1), 1);
360 EXPECT_EQ(delegate.UniqueRetained(2), 3);
361 }
362
363 // 2<->3 |
364 // ^ |
365 // | |
366 // 1R |
TEST(HeapGraphWalkerTest,Component)367 TEST(HeapGraphWalkerTest, Component) {
368 HeapGraphWalkerTestDelegate delegate;
369 HeapGraphWalker walker(&delegate);
370 walker.AddNode(1, 1);
371 walker.AddNode(2, 2);
372 walker.AddNode(3, 3);
373
374 walker.AddEdge(1, 2);
375 walker.AddEdge(2, 3);
376 walker.AddEdge(3, 2);
377
378 walker.MarkRoot(1);
379 walker.CalculateRetained();
380
381 EXPECT_EQ(delegate.Retained(1), 6);
382 EXPECT_EQ(delegate.Retained(2), 5);
383 EXPECT_EQ(delegate.Retained(3), 5);
384
385 EXPECT_EQ(delegate.UniqueRetained(1), 6);
386 // TODO(fmayer): this should be 5, as this breaks away the component.
387 EXPECT_EQ(delegate.UniqueRetained(2), 2);
388 EXPECT_EQ(delegate.UniqueRetained(3), 3);
389 }
390
391 // 2<->3R |
392 // ^ |
393 // | |
394 // 1R |
TEST(HeapGraphWalkerTest,ComponentWithRoot)395 TEST(HeapGraphWalkerTest, ComponentWithRoot) {
396 HeapGraphWalkerTestDelegate delegate;
397 HeapGraphWalker walker(&delegate);
398 walker.AddNode(1, 1);
399 walker.AddNode(2, 2);
400 walker.AddNode(3, 3);
401
402 walker.AddEdge(1, 2);
403 walker.AddEdge(2, 3);
404 walker.AddEdge(3, 2);
405
406 walker.MarkRoot(1);
407 walker.MarkRoot(3);
408 walker.CalculateRetained();
409
410 EXPECT_EQ(delegate.Retained(1), 6);
411 EXPECT_EQ(delegate.Retained(2), 5);
412 EXPECT_EQ(delegate.Retained(3), 5);
413
414 EXPECT_EQ(delegate.UniqueRetained(1), 1);
415 EXPECT_EQ(delegate.UniqueRetained(2), 2);
416 EXPECT_EQ(delegate.UniqueRetained(3), 3);
417 }
418
419 // R
420 // 2 <- 3 |
421 // ^ ^ |
422 // \ / |
423 // 1R |
TEST(HeapGraphWalkerTest,TwoRoots)424 TEST(HeapGraphWalkerTest, TwoRoots) {
425 HeapGraphWalkerTestDelegate delegate;
426 HeapGraphWalker walker(&delegate);
427 walker.AddNode(1, 1);
428 walker.AddNode(2, 2);
429 walker.AddNode(3, 3);
430
431 walker.AddEdge(1, 2);
432 walker.AddEdge(1, 3);
433 walker.AddEdge(3, 2);
434
435 walker.MarkRoot(1);
436 walker.MarkRoot(2);
437 walker.CalculateRetained();
438
439 EXPECT_EQ(delegate.Retained(1), 6);
440 EXPECT_EQ(delegate.Retained(2), 2);
441 EXPECT_EQ(delegate.Retained(3), 5);
442
443 EXPECT_EQ(delegate.UniqueRetained(1), 4);
444 EXPECT_EQ(delegate.UniqueRetained(2), 2);
445 EXPECT_EQ(delegate.UniqueRetained(3), 3);
446 }
447
448 // Call a function for every set in the powerset or the cartesian product
449 // of v with itself.
450 // TODO(fmayer): Find a smarter way to generate all graphs.
451 template <typename F>
SquarePowerSet(const std::vector<int64_t> & v,F fn)452 void SquarePowerSet(const std::vector<int64_t>& v, F fn) {
453 for (uint64_t subset = 0; subset < pow(2, pow(v.size(), 2)); ++subset) {
454 std::vector<std::pair<int64_t, int64_t>> ps;
455 uint64_t node = 0;
456 for (int64_t n1 : v) {
457 for (int64_t n2 : v) {
458 if ((1 << node++) & subset)
459 ps.emplace_back(n1, n2);
460 }
461 }
462 fn(ps);
463 }
464 }
465
466 // Call a function for every set in the powerset.
467 template <typename F>
PowerSet(const std::vector<int64_t> & v,F fn)468 void PowerSet(const std::vector<int64_t>& v, F fn) {
469 for (uint64_t subset = 0; subset < pow(2, v.size()); ++subset) {
470 std::vector<int64_t> ps;
471 uint64_t node = 0;
472 for (int64_t n : v) {
473 if ((1 << node++) & subset)
474 ps.emplace_back(n);
475 }
476 fn(ps);
477 }
478 }
479
TEST(PowerSetTest,Simple)480 TEST(PowerSetTest, Simple) {
481 std::vector<int64_t> s = {0, 1, 2};
482 std::vector<std::vector<int64_t>> ps;
483 PowerSet(s, [&ps](const std::vector<int64_t>& x) { ps.emplace_back(x); });
484 EXPECT_THAT(ps, UnorderedElementsAre(std::vector<int64_t>{}, //
485 std::vector<int64_t>{0}, //
486 std::vector<int64_t>{1}, //
487 std::vector<int64_t>{2}, //
488 std::vector<int64_t>{0, 1}, //
489 std::vector<int64_t>{0, 2}, //
490 std::vector<int64_t>{1, 2}, //
491 std::vector<int64_t>{0, 1, 2}));
492 }
493
TEST(SquarePowerSetTest,Simple)494 TEST(SquarePowerSetTest, Simple) {
495 std::vector<int64_t> s = {0, 1};
496 std::vector<std::vector<std::pair<int64_t, int64_t>>> ps;
497 SquarePowerSet(s, [&ps](const std::vector<std::pair<int64_t, int64_t>>& x) {
498 ps.emplace_back(x);
499 });
500
501 std::vector<std::pair<int64_t, int64_t>> expected[] = {
502 {}, //
503 {{0, 0}}, //
504 {{0, 1}}, //
505 {{1, 0}}, //
506 {{1, 1}}, //
507 {{0, 0}, {0, 1}}, //
508 {{0, 0}, {1, 0}}, //
509 {{0, 0}, {1, 1}}, //
510 {{0, 1}, {1, 0}}, //
511 {{0, 1}, {1, 1}}, //
512 {{1, 0}, {1, 1}}, //
513 {{0, 0}, {0, 1}, {1, 0}}, //
514 {{0, 0}, {0, 1}, {1, 1}}, //
515 {{0, 0}, {1, 0}, {1, 1}}, //
516 {{0, 1}, {1, 0}, {1, 1}}, //
517 {{0, 0}, {0, 1}, {1, 0}, {1, 1}}};
518 EXPECT_THAT(ps, UnorderedElementsAreArray(expected));
519 }
520
521 // Generate all graphs with 4 nodes, and assert that deleting one node frees
522 // up more memory than that node's unique retained.
TEST(HeapGraphWalkerTest,DISABLED_AllGraphs)523 TEST(HeapGraphWalkerTest, DISABLED_AllGraphs) {
524 std::vector<int64_t> nodes{1, 2, 3, 4};
525 std::vector<uint64_t> sizes{0, 1, 2, 3, 4};
526 PowerSet(nodes, [&nodes, &sizes](const std::vector<int64_t>& roots) {
527 SquarePowerSet(
528 nodes, [&nodes, &sizes,
529 &roots](const std::vector<std::pair<int64_t, int64_t>>& edges) {
530 HeapGraphWalkerTestDelegate delegate;
531 HeapGraphWalker walker(&delegate);
532
533 HeapGraphWalkerTestDelegate delegate2;
534 HeapGraphWalker walker2(&delegate2);
535
536 for (int64_t node : nodes) {
537 walker.AddNode(node, sizes[static_cast<size_t>(node)]);
538 // walker2 leaves out node 1.
539 if (node != 1)
540 walker2.AddNode(node, sizes[static_cast<size_t>(node)]);
541 }
542
543 for (const auto& p : edges) {
544 walker.AddEdge(p.first, p.second);
545 // walker2 leaves out node 1.
546 if (p.first != 1 && p.second != 1)
547 walker2.AddEdge(p.first, p.second);
548 }
549
550 for (int64_t r : roots) {
551 walker.MarkRoot(r);
552 // walker2 leaves out node 1.
553 if (r != 1)
554 walker2.MarkRoot(r);
555 }
556
557 walker.CalculateRetained();
558 // We do not need to CalculateRetained on walker2, because we only
559 // get the reachable nodes.
560
561 int64_t reachable = 0;
562 int64_t reachable2 = 0;
563
564 ASSERT_FALSE(delegate2.Reachable(1));
565 for (int64_t n : nodes) {
566 if (delegate.Reachable(n))
567 reachable += sizes[static_cast<size_t>(n)];
568 if (delegate2.Reachable(n))
569 reachable2 += sizes[static_cast<size_t>(n)];
570 }
571 EXPECT_LE(reachable2, reachable);
572 if (delegate.Reachable(1)) {
573 // TODO(fmayer): This should be EXPECT_EQ, but we do currently
574 // undercount the unique retained, because we do not include the
575 // memory that could get freed by the component being broken apart.
576 EXPECT_LE(delegate.UniqueRetained(1), reachable - reachable2)
577 << "roots: " << testing::PrintToString(roots)
578 << ", edges: " << testing::PrintToString(edges);
579 } else {
580 EXPECT_EQ(reachable2, reachable);
581 }
582 });
583 });
584 }
585
HasPath(const HeapGraphWalker::PathFromRoot & path,const HeapGraphWalker::PathFromRoot::Node & node,std::vector<HeapGraphWalker::ClassNameId> class_names)586 bool HasPath(const HeapGraphWalker::PathFromRoot& path,
587 const HeapGraphWalker::PathFromRoot::Node& node,
588 std::vector<HeapGraphWalker::ClassNameId> class_names) {
589 if (class_names.empty())
590 return true;
591 auto it = node.children.find(class_names[0]);
592 if (it == node.children.end())
593 return false;
594 class_names.erase(class_names.begin());
595 return HasPath(path, path.nodes[it->second], std::move(class_names));
596 }
597
HasPath(const HeapGraphWalker::PathFromRoot & path,std::vector<uint32_t> class_names)598 bool HasPath(const HeapGraphWalker::PathFromRoot& path,
599 std::vector<uint32_t> class_names) {
600 return HasPath(path, path.nodes[HeapGraphWalker::PathFromRoot::kRoot],
601 std::move(class_names));
602 }
603
604 // 1 |
605 // ^^ |
606 // / \ |
607 // 2<-> 3 |
608 // ^ |
609 // | |
610 // 4R |
TEST(HeapGraphWalkerTest,ShortestPath)611 TEST(HeapGraphWalkerTest, ShortestPath) {
612 HeapGraphWalkerTestDelegate delegate;
613 HeapGraphWalker walker(&delegate);
614 walker.AddNode(1, 1, 1u);
615 walker.AddNode(2, 2, 2u);
616 walker.AddNode(3, 3, 3u);
617 walker.AddNode(4, 4, 4);
618
619 walker.AddEdge(2, 1);
620 walker.AddEdge(2, 3);
621 walker.AddEdge(3, 1);
622 walker.AddEdge(3, 2);
623 walker.AddEdge(4, 2);
624
625 walker.MarkRoot(4);
626 auto path = walker.FindPathsFromRoot();
627
628 EXPECT_TRUE(HasPath(path, {4u, 2u, 1u}));
629 EXPECT_TRUE(HasPath(path, {4u, 2u, 3u}));
630 EXPECT_FALSE(HasPath(path, {4u, 2u, 3u, 1u}));
631 }
632
633 // 1 |
634 // ^^ |
635 // / \ |
636 // 2R<->3 |
637 // ^ |
638 // | |
639 // 4R |
TEST(HeapGraphWalkerTest,ShortestPathMultipleRoots)640 TEST(HeapGraphWalkerTest, ShortestPathMultipleRoots) {
641 HeapGraphWalkerTestDelegate delegate;
642 HeapGraphWalker walker(&delegate);
643 walker.AddNode(1, 1, 1u);
644 walker.AddNode(2, 2, 2u);
645 walker.AddNode(3, 3, 3u);
646 walker.AddNode(4, 4, 4u);
647
648 walker.AddEdge(2, 1);
649 walker.AddEdge(2, 3);
650 walker.AddEdge(3, 1);
651 walker.AddEdge(3, 2);
652 walker.AddEdge(4, 2);
653
654 walker.MarkRoot(4);
655 walker.MarkRoot(2);
656 auto path = walker.FindPathsFromRoot();
657
658 EXPECT_TRUE(HasPath(path, {2u, 1u}));
659 EXPECT_TRUE(HasPath(path, {2u, 3u}));
660 EXPECT_FALSE(HasPath(path, {4u, 2u, 3u}));
661 }
662
663 } // namespace
664 } // namespace trace_processor
665 } // namespace perfetto
666