1 /*
2  * Copyright (C) 2020 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 "perfetto/ext/trace_processor/importers/memory_tracker/graph_processor.h"
18 
19 #include <stddef.h>
20 
21 #include "perfetto/base/build_config.h"
22 #include "test/gtest_and_gmock.h"
23 
24 namespace perfetto {
25 namespace trace_processor {
26 
27 using Edge = GlobalNodeGraph::Edge;
28 using Node = GlobalNodeGraph::Node;
29 using Process = GlobalNodeGraph::Process;
30 
31 namespace {
32 
33 const MemoryAllocatorNodeId kEmptyId;
34 
35 }  // namespace
36 
37 class GraphProcessorTest : public testing::Test {
38  public:
GraphProcessorTest()39   GraphProcessorTest() {}
40 
MarkImplicitWeakParentsRecursively(Node * node)41   void MarkImplicitWeakParentsRecursively(Node* node) {
42     GraphProcessor::MarkImplicitWeakParentsRecursively(node);
43   }
44 
MarkWeakOwnersAndChildrenRecursively(Node * node)45   void MarkWeakOwnersAndChildrenRecursively(Node* node) {
46     std::set<const Node*> visited;
47     GraphProcessor::MarkWeakOwnersAndChildrenRecursively(node, &visited);
48   }
49 
RemoveWeakNodesRecursively(Node * node)50   void RemoveWeakNodesRecursively(Node* node) {
51     GraphProcessor::RemoveWeakNodesRecursively(node);
52   }
53 
AssignTracingOverhead(const std::string & allocator,GlobalNodeGraph * global_graph,Process * process)54   void AssignTracingOverhead(const std::string& allocator,
55                              GlobalNodeGraph* global_graph,
56                              Process* process) {
57     GraphProcessor::AssignTracingOverhead(allocator, global_graph, process);
58   }
59 
AggregateNumericWithNameForNode(Node * node,const std::string & name)60   GlobalNodeGraph::Node::Entry AggregateNumericWithNameForNode(
61       Node* node,
62       const std::string& name) {
63     return GraphProcessor::AggregateNumericWithNameForNode(node, name);
64   }
65 
AggregateNumericsRecursively(Node * node)66   void AggregateNumericsRecursively(Node* node) {
67     GraphProcessor::AggregateNumericsRecursively(node);
68   }
69 
PropagateNumericsAndDiagnosticsRecursively(Node * node)70   void PropagateNumericsAndDiagnosticsRecursively(Node* node) {
71     GraphProcessor::PropagateNumericsAndDiagnosticsRecursively(node);
72   }
73 
AggregateSizeForDescendantNode(Node * root,Node * descendant)74   std::optional<uint64_t> AggregateSizeForDescendantNode(Node* root,
75                                                          Node* descendant) {
76     return GraphProcessor::AggregateSizeForDescendantNode(root, descendant);
77   }
78 
CalculateSizeForNode(Node * node)79   void CalculateSizeForNode(Node* node) {
80     GraphProcessor::CalculateSizeForNode(node);
81   }
82 
CalculateNodeSubSizes(Node * node)83   void CalculateNodeSubSizes(Node* node) {
84     GraphProcessor::CalculateNodeSubSizes(node);
85   }
86 
CalculateNodeOwnershipCoefficient(Node * node)87   void CalculateNodeOwnershipCoefficient(Node* node) {
88     GraphProcessor::CalculateNodeOwnershipCoefficient(node);
89   }
90 
CalculateNodeCumulativeOwnershipCoefficient(Node * node)91   void CalculateNodeCumulativeOwnershipCoefficient(Node* node) {
92     GraphProcessor::CalculateNodeCumulativeOwnershipCoefficient(node);
93   }
94 
CalculateNodeEffectiveSize(Node * node)95   void CalculateNodeEffectiveSize(Node* node) {
96     GraphProcessor::CalculateNodeEffectiveSize(node);
97   }
98 
99  protected:
100   GlobalNodeGraph graph;
101 };
102 
TEST_F(GraphProcessorTest,SmokeComputeMemoryGraph)103 TEST_F(GraphProcessorTest, SmokeComputeMemoryGraph) {
104   std::map<base::PlatformProcessId, std::unique_ptr<RawProcessMemoryNode>>
105       process_nodes;
106 
107   std::unique_ptr<RawMemoryGraphNode> source(new RawMemoryGraphNode(
108       "test1/test2/test3", LevelOfDetail::kDetailed, MemoryAllocatorNodeId(42),
109       std::vector<RawMemoryGraphNode::MemoryNodeEntry>{
110           {RawMemoryGraphNode::kNameSize, RawMemoryGraphNode::kUnitsBytes,
111            10}}));
112 
113   std::unique_ptr<RawMemoryGraphNode> target(new RawMemoryGraphNode(
114       "target", LevelOfDetail::kDetailed, MemoryAllocatorNodeId(4242)));
115 
116   std::unique_ptr<MemoryGraphEdge> edge(
117       new MemoryGraphEdge(source->id(), target->id(), 10, false));
118   RawProcessMemoryNode::AllocatorNodeEdgesMap edgesMap;
119   edgesMap.emplace(edge->source, std::move(edge));
120 
121   RawProcessMemoryNode::MemoryNodesMap nodesMap;
122   nodesMap.emplace(source->absolute_name(), std::move(source));
123   nodesMap.emplace(target->absolute_name(), std::move(target));
124 
125   auto pmd = std::unique_ptr<RawProcessMemoryNode>(new RawProcessMemoryNode(
126       LevelOfDetail::kDetailed, std::move(edgesMap), std::move(nodesMap)));
127   process_nodes.emplace(1, std::move(pmd));
128 
129   auto global_node = GraphProcessor::CreateMemoryGraph(process_nodes);
130 
131   ASSERT_EQ(1u, global_node->process_node_graphs().size());
132 
133   auto id_to_node_it = global_node->process_node_graphs().find(1);
134   auto* first_child = id_to_node_it->second->FindNode("test1");
135   ASSERT_NE(first_child, nullptr);
136   ASSERT_EQ(first_child->parent(), id_to_node_it->second->root());
137 
138   auto* second_child = first_child->GetChild("test2");
139   ASSERT_NE(second_child, nullptr);
140   ASSERT_EQ(second_child->parent(), first_child);
141 
142   auto* third_child = second_child->GetChild("test3");
143   ASSERT_NE(third_child, nullptr);
144   ASSERT_EQ(third_child->parent(), second_child);
145 
146   auto* direct = id_to_node_it->second->FindNode("test1/test2/test3");
147   ASSERT_EQ(third_child, direct);
148 
149   ASSERT_EQ(third_child->entries()->size(), 1ul);
150 
151   auto size = third_child->entries()->find(RawMemoryGraphNode::kNameSize);
152   ASSERT_EQ(10ul, size->second.value_uint64);
153 
154   auto& edges = global_node->edges();
155   auto edge_it = edges.begin();
156   ASSERT_EQ(std::distance(edges.begin(), edges.end()), 1l);
157   ASSERT_EQ(edge_it->source(), direct);
158   ASSERT_EQ(edge_it->target(), id_to_node_it->second->FindNode("target"));
159   ASSERT_EQ(edge_it->priority(), 10);
160 }
161 
TEST_F(GraphProcessorTest,ComputeSharedFootprintFromGraphSameImportance)162 TEST_F(GraphProcessorTest, ComputeSharedFootprintFromGraphSameImportance) {
163   Process* global_process = graph.shared_memory_graph();
164   Node* global_node = global_process->CreateNode(kEmptyId, "global/1", false);
165   global_node->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 100);
166 
167   Process* first = graph.CreateGraphForProcess(1);
168   Node* shared_1 = first->CreateNode(kEmptyId, "shared_memory/1", false);
169 
170   Process* second = graph.CreateGraphForProcess(2);
171   Node* shared_2 = second->CreateNode(kEmptyId, "shared_memory/2", false);
172 
173   graph.AddNodeOwnershipEdge(shared_1, global_node, 1);
174   graph.AddNodeOwnershipEdge(shared_2, global_node, 1);
175 
176   auto pid_to_sizes = GraphProcessor::ComputeSharedFootprintFromGraph(graph);
177   ASSERT_EQ(pid_to_sizes[1], 50ul);
178   ASSERT_EQ(pid_to_sizes[2], 50ul);
179 }
180 
TEST_F(GraphProcessorTest,ComputeSharedFootprintFromGraphSomeDiffImportance)181 TEST_F(GraphProcessorTest, ComputeSharedFootprintFromGraphSomeDiffImportance) {
182   Process* global_process = graph.shared_memory_graph();
183 
184   Node* global_node = global_process->CreateNode(kEmptyId, "global/1", false);
185   global_node->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 100);
186 
187   Process* first = graph.CreateGraphForProcess(1);
188   Node* shared_1 = first->CreateNode(kEmptyId, "shared_memory/1", false);
189 
190   Process* second = graph.CreateGraphForProcess(2);
191   Node* shared_2 = second->CreateNode(kEmptyId, "shared_memory/2", false);
192 
193   Process* third = graph.CreateGraphForProcess(3);
194   Node* shared_3 = third->CreateNode(kEmptyId, "shared_memory/3", false);
195 
196   Process* fourth = graph.CreateGraphForProcess(4);
197   Node* shared_4 = fourth->CreateNode(kEmptyId, "shared_memory/4", false);
198 
199   Process* fifth = graph.CreateGraphForProcess(5);
200   Node* shared_5 = fifth->CreateNode(kEmptyId, "shared_memory/5", false);
201 
202   graph.AddNodeOwnershipEdge(shared_1, global_node, 1);
203   graph.AddNodeOwnershipEdge(shared_2, global_node, 2);
204   graph.AddNodeOwnershipEdge(shared_3, global_node, 3);
205   graph.AddNodeOwnershipEdge(shared_4, global_node, 3);
206   graph.AddNodeOwnershipEdge(shared_5, global_node, 3);
207 
208   auto pid_to_sizes = GraphProcessor::ComputeSharedFootprintFromGraph(graph);
209   ASSERT_EQ(pid_to_sizes[1], 0ul);
210   ASSERT_EQ(pid_to_sizes[2], 0ul);
211   ASSERT_EQ(pid_to_sizes[3], 33ul);
212   ASSERT_EQ(pid_to_sizes[4], 33ul);
213   ASSERT_EQ(pid_to_sizes[5], 33ul);
214 }
215 
TEST_F(GraphProcessorTest,MarkWeakParentsSimple)216 TEST_F(GraphProcessorTest, MarkWeakParentsSimple) {
217   Process* process = graph.CreateGraphForProcess(1);
218   Node* parent = process->CreateNode(kEmptyId, "parent", false);
219   Node* first = process->CreateNode(kEmptyId, "parent/first", true);
220   Node* second = process->CreateNode(kEmptyId, "parent/second", false);
221 
222   // Case where one child is not weak.
223   parent->set_explicit(false);
224   first->set_explicit(true);
225   second->set_explicit(true);
226 
227   // The function should be a no-op.
228   MarkImplicitWeakParentsRecursively(parent);
229   ASSERT_FALSE(parent->is_weak());
230   ASSERT_TRUE(first->is_weak());
231   ASSERT_FALSE(second->is_weak());
232 
233   // Case where all children is weak.
234   second->set_weak(true);
235 
236   // The function should mark parent as weak.
237   MarkImplicitWeakParentsRecursively(parent);
238   ASSERT_TRUE(parent->is_weak());
239   ASSERT_TRUE(first->is_weak());
240   ASSERT_TRUE(second->is_weak());
241 }
242 
TEST_F(GraphProcessorTest,MarkWeakParentsComplex)243 TEST_F(GraphProcessorTest, MarkWeakParentsComplex) {
244   Process* process = graph.CreateGraphForProcess(1);
245 
246   // |first| is explicitly strong but |first_child| is implicitly so.
247   Node* parent = process->CreateNode(kEmptyId, "parent", false);
248   Node* first = process->CreateNode(kEmptyId, "parent/f", false);
249   Node* first_child = process->CreateNode(kEmptyId, "parent/f/c", false);
250   Node* first_gchild = process->CreateNode(kEmptyId, "parent/f/c/c", true);
251 
252   parent->set_explicit(false);
253   first->set_explicit(true);
254   first_child->set_explicit(false);
255   first_gchild->set_explicit(true);
256 
257   // That should lead to |first_child| marked implicitly weak.
258   MarkImplicitWeakParentsRecursively(parent);
259   ASSERT_FALSE(parent->is_weak());
260   ASSERT_FALSE(first->is_weak());
261   ASSERT_TRUE(first_child->is_weak());
262   ASSERT_TRUE(first_gchild->is_weak());
263 
264   // Reset and change so that first is now only implicitly strong.
265   first->set_explicit(false);
266   first_child->set_weak(false);
267 
268   // The whole chain should now be weak.
269   MarkImplicitWeakParentsRecursively(parent);
270   ASSERT_TRUE(parent->is_weak());
271   ASSERT_TRUE(first->is_weak());
272   ASSERT_TRUE(first_child->is_weak());
273   ASSERT_TRUE(first_gchild->is_weak());
274 }
275 
TEST_F(GraphProcessorTest,MarkWeakOwners)276 TEST_F(GraphProcessorTest, MarkWeakOwners) {
277   Process* process = graph.CreateGraphForProcess(1);
278 
279   // Make only the ultimate owned node weak.
280   Node* owner = process->CreateNode(kEmptyId, "owner", false);
281   Node* owned = process->CreateNode(kEmptyId, "owned", false);
282   Node* owned_2 = process->CreateNode(kEmptyId, "owned2", true);
283 
284   graph.AddNodeOwnershipEdge(owner, owned, 0);
285   graph.AddNodeOwnershipEdge(owned, owned_2, 0);
286 
287   // Starting from leaf node should lead to everything being weak.
288   MarkWeakOwnersAndChildrenRecursively(process->root());
289   ASSERT_TRUE(owner->is_weak());
290   ASSERT_TRUE(owned->is_weak());
291   ASSERT_TRUE(owned_2->is_weak());
292 }
293 
TEST_F(GraphProcessorTest,MarkWeakParent)294 TEST_F(GraphProcessorTest, MarkWeakParent) {
295   Process* process = graph.CreateGraphForProcess(1);
296   Node* parent = process->CreateNode(kEmptyId, "parent", true);
297   Node* child = process->CreateNode(kEmptyId, "parent/c", false);
298   Node* child_2 = process->CreateNode(kEmptyId, "parent/c/c", false);
299 
300   // Starting from parent node should lead to everything being weak.
301   MarkWeakOwnersAndChildrenRecursively(process->root());
302   ASSERT_TRUE(parent->is_weak());
303   ASSERT_TRUE(child->is_weak());
304   ASSERT_TRUE(child_2->is_weak());
305 }
306 
TEST_F(GraphProcessorTest,MarkWeakParentOwner)307 TEST_F(GraphProcessorTest, MarkWeakParentOwner) {
308   Process* process = graph.CreateGraphForProcess(1);
309 
310   // Make only the parent node weak.
311   Node* parent = process->CreateNode(kEmptyId, "parent", true);
312   Node* child = process->CreateNode(kEmptyId, "parent/c", false);
313   Node* child_2 = process->CreateNode(kEmptyId, "parent/c/c", false);
314   Node* owner = process->CreateNode(kEmptyId, "owner", false);
315 
316   graph.AddNodeOwnershipEdge(owner, parent, 0);
317 
318   // Starting from parent node should lead to everything being weak.
319   MarkWeakOwnersAndChildrenRecursively(process->root());
320   ASSERT_TRUE(parent->is_weak());
321   ASSERT_TRUE(child->is_weak());
322   ASSERT_TRUE(child_2->is_weak());
323   ASSERT_TRUE(owner->is_weak());
324 }
325 
TEST_F(GraphProcessorTest,RemoveWeakNodesRecursively)326 TEST_F(GraphProcessorTest, RemoveWeakNodesRecursively) {
327   Process* process = graph.CreateGraphForProcess(1);
328 
329   // Make only the child node weak.
330   Node* parent = process->CreateNode(kEmptyId, "parent", false);
331   Node* child = process->CreateNode(kEmptyId, "parent/c", true);
332   process->CreateNode(kEmptyId, "parent/c/c", false);
333   Node* owned = process->CreateNode(kEmptyId, "parent/owned", false);
334 
335   graph.AddNodeOwnershipEdge(child, owned, 0);
336 
337   // Starting from parent node should lead child and child_2 being
338   // removed and owned to have the edge from it removed.
339   RemoveWeakNodesRecursively(parent);
340 
341   ASSERT_EQ(parent->children()->size(), 1ul);
342   ASSERT_EQ(parent->children()->begin()->second, owned);
343 
344   ASSERT_TRUE(owned->owned_by_edges()->empty());
345 }
346 
TEST_F(GraphProcessorTest,RemoveWeakNodesRecursivelyBetweenGraphs)347 TEST_F(GraphProcessorTest, RemoveWeakNodesRecursivelyBetweenGraphs) {
348   Process* f_process = graph.CreateGraphForProcess(1);
349   Process* s_process = graph.CreateGraphForProcess(2);
350 
351   // Make only the child node weak.
352   Node* child = f_process->CreateNode(kEmptyId, "c", true);
353   f_process->CreateNode(kEmptyId, "c/c", false);
354   Node* owned = s_process->CreateNode(kEmptyId, "owned", false);
355 
356   graph.AddNodeOwnershipEdge(child, owned, 0);
357 
358   // Starting from root node should lead child and child_2 being
359   // removed.
360   RemoveWeakNodesRecursively(f_process->root());
361 
362   ASSERT_EQ(f_process->root()->children()->size(), 0ul);
363   ASSERT_EQ(s_process->root()->children()->size(), 1ul);
364 
365   // This should be false until our next pass.
366   ASSERT_FALSE(owned->owned_by_edges()->empty());
367 
368   RemoveWeakNodesRecursively(s_process->root());
369 
370   // We should now have cleaned up the owned node's edges.
371   ASSERT_TRUE(owned->owned_by_edges()->empty());
372 }
373 
TEST_F(GraphProcessorTest,AssignTracingOverhead)374 TEST_F(GraphProcessorTest, AssignTracingOverhead) {
375   Process* process = graph.CreateGraphForProcess(1);
376 
377   // Now add an allocator node.
378   process->CreateNode(kEmptyId, "malloc", false);
379 
380   // If the tracing node does not exist, this should do nothing.
381   AssignTracingOverhead("malloc", &graph, process);
382   ASSERT_TRUE(process->root()->GetChild("malloc")->children()->empty());
383 
384   // Now add a tracing node.
385   process->CreateNode(kEmptyId, "tracing", false);
386 
387   // This should now add a node with the allocator.
388   AssignTracingOverhead("malloc", &graph, process);
389   ASSERT_NE(process->FindNode("malloc/allocated_objects/tracing_overhead"),
390             nullptr);
391 }
392 
TEST_F(GraphProcessorTest,AggregateNumericWithNameForNode)393 TEST_F(GraphProcessorTest, AggregateNumericWithNameForNode) {
394   Process* process = graph.CreateGraphForProcess(1);
395 
396   Node* c1 = process->CreateNode(kEmptyId, "c1", false);
397   Node* c2 = process->CreateNode(kEmptyId, "c2", false);
398   Node* c3 = process->CreateNode(kEmptyId, "c3", false);
399 
400   c1->AddEntry("random_numeric", Node::Entry::ScalarUnits::kBytes, 100);
401   c2->AddEntry("random_numeric", Node::Entry::ScalarUnits::kBytes, 256);
402   c3->AddEntry("other_numeric", Node::Entry::ScalarUnits::kBytes, 1000);
403 
404   Node* root = process->root();
405   Node::Entry entry = AggregateNumericWithNameForNode(root, "random_numeric");
406   ASSERT_EQ(entry.value_uint64, 356ul);
407   ASSERT_EQ(entry.units, Node::Entry::ScalarUnits::kBytes);
408 }
409 
TEST_F(GraphProcessorTest,AggregateNumericsRecursively)410 TEST_F(GraphProcessorTest, AggregateNumericsRecursively) {
411   Process* process = graph.CreateGraphForProcess(1);
412 
413   Node* c1 = process->CreateNode(kEmptyId, "c1", false);
414   Node* c2 = process->CreateNode(kEmptyId, "c2", false);
415   Node* c2_c1 = process->CreateNode(kEmptyId, "c2/c1", false);
416   Node* c2_c2 = process->CreateNode(kEmptyId, "c2/c2", false);
417   Node* c3_c1 = process->CreateNode(kEmptyId, "c3/c1", false);
418   Node* c3_c2 = process->CreateNode(kEmptyId, "c3/c2", false);
419 
420   // If an entry already exists in the parent, the child should not
421   // ovewrite it. If nothing exists, then the child can aggregrate.
422   c1->AddEntry("random_numeric", Node::Entry::ScalarUnits::kBytes, 100);
423   c2->AddEntry("random_numeric", Node::Entry::ScalarUnits::kBytes, 256);
424   c2_c1->AddEntry("random_numeric", Node::Entry::ScalarUnits::kBytes, 256);
425   c2_c2->AddEntry("random_numeric", Node::Entry::ScalarUnits::kBytes, 256);
426   c3_c1->AddEntry("random_numeric", Node::Entry::ScalarUnits::kBytes, 10);
427   c3_c2->AddEntry("random_numeric", Node::Entry::ScalarUnits::kBytes, 10);
428 
429   Node* root = process->root();
430   AggregateNumericsRecursively(root);
431   ASSERT_EQ(root->entries()->size(), 1ul);
432 
433   auto entry = root->entries()->begin()->second;
434   ASSERT_EQ(entry.value_uint64, 376ul);
435   ASSERT_EQ(entry.units, Node::Entry::ScalarUnits::kBytes);
436 }
437 
TEST_F(GraphProcessorTest,AggregateSizeForDescendantNode)438 TEST_F(GraphProcessorTest, AggregateSizeForDescendantNode) {
439   Process* process = graph.CreateGraphForProcess(1);
440 
441   Node* c1 = process->CreateNode(kEmptyId, "c1", false);
442   Node* c2 = process->CreateNode(kEmptyId, "c2", false);
443   Node* c2_c1 = process->CreateNode(kEmptyId, "c2/c1", false);
444   Node* c2_c2 = process->CreateNode(kEmptyId, "c2/c2", false);
445   Node* c3_c1 = process->CreateNode(kEmptyId, "c3/c1", false);
446   Node* c3_c2 = process->CreateNode(kEmptyId, "c3/c2", false);
447 
448   c1->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 100);
449   c2_c1->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 256);
450   c2_c2->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 256);
451   c3_c1->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 10);
452   c3_c2->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 10);
453 
454   graph.AddNodeOwnershipEdge(c2_c2, c3_c2, 0);
455 
456   // Aggregating root should give size of (100 + 256 + 10 * 2) = 376.
457   // |c2_c2| is not counted because it is owns by |c3_c2|.
458   Node* root = process->root();
459   ASSERT_EQ(376ul, *AggregateSizeForDescendantNode(root, root));
460 
461   // Aggregating c2 should give size of (256 * 2) = 512. |c2_c2| is counted
462   // because |c3_c2| is not a child of |c2|.
463   ASSERT_EQ(512ul, *AggregateSizeForDescendantNode(c2, c2));
464 }
465 
TEST_F(GraphProcessorTest,CalculateSizeForNode)466 TEST_F(GraphProcessorTest, CalculateSizeForNode) {
467   Process* process = graph.CreateGraphForProcess(1);
468 
469   Node* c1 = process->CreateNode(kEmptyId, "c1", false);
470   Node* c2 = process->CreateNode(kEmptyId, "c2", false);
471   Node* c2_c1 = process->CreateNode(kEmptyId, "c2/c1", false);
472   Node* c2_c2 = process->CreateNode(kEmptyId, "c2/c2", false);
473   Node* c3 = process->CreateNode(kEmptyId, "c3", false);
474   Node* c3_c1 = process->CreateNode(kEmptyId, "c3/c1", false);
475   Node* c3_c2 = process->CreateNode(kEmptyId, "c3/c2", false);
476 
477   c1->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 600);
478   c2_c1->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 10);
479   c2_c2->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 10);
480   c3->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 600);
481   c3_c1->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 256);
482   c3_c2->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 256);
483 
484   graph.AddNodeOwnershipEdge(c2_c2, c3_c2, 0);
485 
486   // Compute size entry for |c2| since computations for |c2_c1| and |c2_c2|
487   // are already complete.
488   CalculateSizeForNode(c2);
489 
490   // Check that |c2| now has a size entry of 20 (sum of children).
491   auto c2_entry = c2->entries()->begin()->second;
492   ASSERT_EQ(c2_entry.value_uint64, 20ul);
493   ASSERT_EQ(c2_entry.units, Node::Entry::ScalarUnits::kBytes);
494 
495   // Compute size entry for |c3_c2| which should not change in size.
496   CalculateSizeForNode(c3_c2);
497 
498   // Check that |c3_c2| now has unchanged size.
499   auto c3_c2_entry = c3_c2->entries()->begin()->second;
500   ASSERT_EQ(c3_c2_entry.value_uint64, 256ul);
501   ASSERT_EQ(c3_c2_entry.units, Node::Entry::ScalarUnits::kBytes);
502 
503   // Compute size entry for |c3| which should add an unspecified node.
504   CalculateSizeForNode(c3);
505 
506   // Check that |c3| has unchanged size.
507   auto c3_entry = c3->entries()->begin()->second;
508   ASSERT_EQ(c3_entry.value_uint64, 600ul);
509   ASSERT_EQ(c3_entry.units, Node::Entry::ScalarUnits::kBytes);
510 
511   // Check that the unspecified node is a child of |c3| and has size
512   // 600 - 512 = 88.
513   Node* c3_child = c3->children()->find("<unspecified>")->second;
514   auto c3_child_entry = c3_child->entries()->begin()->second;
515   ASSERT_EQ(c3_child_entry.value_uint64, 88ul);
516   ASSERT_EQ(c3_child_entry.units, Node::Entry::ScalarUnits::kBytes);
517 
518   // Compute size entry for |root| which should aggregate children sizes.
519   CalculateSizeForNode(process->root());
520 
521   // Check that |root| has been assigned a size of 600 + 10 + 600 = 1210.
522   // Note that |c2_c2| is not counted because it ows |c3_c2| which is a
523   // descendant of |root|.
524   auto root_entry = process->root()->entries()->begin()->second;
525   ASSERT_EQ(root_entry.value_uint64, 1210ul);
526   ASSERT_EQ(root_entry.units, Node::Entry::ScalarUnits::kBytes);
527 }
528 
TEST_F(GraphProcessorTest,CalculateNodeSubSizes)529 TEST_F(GraphProcessorTest, CalculateNodeSubSizes) {
530   Process* process_1 = graph.CreateGraphForProcess(1);
531   Process* process_2 = graph.CreateGraphForProcess(2);
532 
533   Node* parent_1 = process_1->CreateNode(kEmptyId, "parent", false);
534   Node* child_1 = process_1->CreateNode(kEmptyId, "parent/child", false);
535 
536   Node* parent_2 = process_2->CreateNode(kEmptyId, "parent", false);
537   Node* child_2 = process_2->CreateNode(kEmptyId, "parent/child", false);
538 
539   graph.AddNodeOwnershipEdge(parent_1, parent_2, 0);
540 
541   process_1->root()->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 4);
542   parent_1->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 4);
543   child_1->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 4);
544   process_2->root()->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 5);
545   parent_2->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 5);
546   child_2->AddEntry("size", Node::Entry::ScalarUnits::kBytes, 5);
547 
548   // Each of these nodes should have owner/owned same as size itself.
549   CalculateNodeSubSizes(child_1);
550   ASSERT_EQ(child_1->not_owned_sub_size(), 4ul);
551   ASSERT_EQ(child_1->not_owning_sub_size(), 4ul);
552   CalculateNodeSubSizes(child_2);
553   ASSERT_EQ(child_2->not_owned_sub_size(), 5ul);
554   ASSERT_EQ(child_2->not_owning_sub_size(), 5ul);
555 
556   // These nodes should also have size of children.
557   CalculateNodeSubSizes(parent_1);
558   ASSERT_EQ(parent_1->not_owned_sub_size(), 4ul);
559   ASSERT_EQ(parent_1->not_owning_sub_size(), 4ul);
560   CalculateNodeSubSizes(parent_2);
561   ASSERT_EQ(parent_2->not_owned_sub_size(), 5ul);
562   ASSERT_EQ(parent_2->not_owning_sub_size(), 5ul);
563 
564   // These nodes should account for edge between parents.
565   CalculateNodeSubSizes(process_1->root());
566   ASSERT_EQ(process_1->root()->not_owned_sub_size(), 4ul);
567   ASSERT_EQ(process_1->root()->not_owning_sub_size(), 0ul);
568   CalculateNodeSubSizes(process_2->root());
569   ASSERT_EQ(process_2->root()->not_owned_sub_size(), 1ul);
570   ASSERT_EQ(process_2->root()->not_owning_sub_size(), 5ul);
571 }
572 
TEST_F(GraphProcessorTest,CalculateNodeOwnershipCoefficient)573 TEST_F(GraphProcessorTest, CalculateNodeOwnershipCoefficient) {
574   Process* process = graph.CreateGraphForProcess(1);
575 
576   Node* owned = process->CreateNode(kEmptyId, "owned", false);
577   Node* owner_1 = process->CreateNode(kEmptyId, "owner1", false);
578   Node* owner_2 = process->CreateNode(kEmptyId, "owner2", false);
579   Node* owner_3 = process->CreateNode(kEmptyId, "owner3", false);
580   Node* owner_4 = process->CreateNode(kEmptyId, "owner4", false);
581 
582   graph.AddNodeOwnershipEdge(owner_1, owned, 2);
583   graph.AddNodeOwnershipEdge(owner_2, owned, 2);
584   graph.AddNodeOwnershipEdge(owner_3, owned, 1);
585   graph.AddNodeOwnershipEdge(owner_4, owned, 0);
586 
587   // Ensure the owned node has a size otherwise calculations will not happen.
588   owned->AddEntry("size", Node::Entry::kBytes, 10);
589 
590   // Setup the owned/owning sub sizes.
591   owned->add_not_owned_sub_size(10);
592   owner_1->add_not_owning_sub_size(6);
593   owner_2->add_not_owning_sub_size(7);
594   owner_3->add_not_owning_sub_size(5);
595   owner_4->add_not_owning_sub_size(8);
596 
597   // Perform the computation.
598   CalculateNodeOwnershipCoefficient(owned);
599 
600   // Ensure that the coefficients are correct.
601   ASSERT_DOUBLE_EQ(owned->owned_coefficient(), 2.0 / 10.0);
602   ASSERT_DOUBLE_EQ(owner_1->owning_coefficient(), 3.0 / 6.0);
603   ASSERT_DOUBLE_EQ(owner_2->owning_coefficient(), 4.0 / 7.0);
604   ASSERT_DOUBLE_EQ(owner_3->owning_coefficient(), 0.0 / 5.0);
605   ASSERT_DOUBLE_EQ(owner_4->owning_coefficient(), 1.0 / 8.0);
606 }
607 
TEST_F(GraphProcessorTest,CalculateNodeCumulativeOwnershipCoefficient)608 TEST_F(GraphProcessorTest, CalculateNodeCumulativeOwnershipCoefficient) {
609   Process* process = graph.CreateGraphForProcess(1);
610 
611   Node* c1 = process->CreateNode(kEmptyId, "c1", false);
612   Node* c1_c1 = process->CreateNode(kEmptyId, "c1/c1", false);
613   Node* c1_c2 = process->CreateNode(kEmptyId, "c1/c2", false);
614   Node* owned = process->CreateNode(kEmptyId, "owned", false);
615 
616   graph.AddNodeOwnershipEdge(c1_c2, owned, 2);
617 
618   // Ensure all nodes have sizes otherwise calculations will not happen.
619   c1_c1->AddEntry("size", Node::Entry::kBytes, 10);
620   c1_c2->AddEntry("size", Node::Entry::kBytes, 10);
621   owned->AddEntry("size", Node::Entry::kBytes, 10);
622 
623   // Setup the owned/owning cummulative coefficients.
624   c1->set_cumulative_owning_coefficient(0.123);
625   c1->set_cumulative_owned_coefficient(0.456);
626   owned->set_cumulative_owning_coefficient(0.789);
627   owned->set_cumulative_owned_coefficient(0.987);
628 
629   // Set owning and owned for the children.
630   c1_c1->set_owning_coefficient(0.654);
631   c1_c1->set_owned_coefficient(0.321);
632   c1_c2->set_owning_coefficient(0.135);
633   c1_c2->set_owned_coefficient(0.246);
634 
635   // Perform the computation and check our answers.
636   CalculateNodeCumulativeOwnershipCoefficient(c1_c1);
637   ASSERT_DOUBLE_EQ(c1_c1->cumulative_owning_coefficient(), 0.123);
638   ASSERT_DOUBLE_EQ(c1_c1->cumulative_owned_coefficient(), 0.456 * 0.321);
639 
640   CalculateNodeCumulativeOwnershipCoefficient(c1_c2);
641   ASSERT_DOUBLE_EQ(c1_c2->cumulative_owning_coefficient(), 0.135 * 0.789);
642   ASSERT_DOUBLE_EQ(c1_c2->cumulative_owned_coefficient(), 0.456 * 0.246);
643 }
644 
TEST_F(GraphProcessorTest,CalculateNodeEffectiveSize)645 TEST_F(GraphProcessorTest, CalculateNodeEffectiveSize) {
646   Process* process = graph.CreateGraphForProcess(1);
647 
648   Node* c1 = process->CreateNode(kEmptyId, "c1", false);
649   Node* c1_c1 = process->CreateNode(kEmptyId, "c1/c1", false);
650   Node* c1_c2 = process->CreateNode(kEmptyId, "c1/c2", false);
651 
652   // Ensure all nodes have sizes otherwise calculations will not happen.
653   c1->AddEntry("size", Node::Entry::kBytes, 200);
654   c1_c1->AddEntry("size", Node::Entry::kBytes, 32);
655   c1_c2->AddEntry("size", Node::Entry::kBytes, 20);
656 
657   // Setup the owned/owning cummulative coefficients.
658   c1_c1->set_cumulative_owning_coefficient(0.123);
659   c1_c1->set_cumulative_owned_coefficient(0.456);
660   c1_c2->set_cumulative_owning_coefficient(0.789);
661   c1_c2->set_cumulative_owned_coefficient(0.987);
662 
663   // Perform the computation and check our answers.
664   CalculateNodeEffectiveSize(c1_c1);
665   const Node::Entry& entry_c1_c1 =
666       c1_c1->entries()->find("effective_size")->second;
667   uint64_t expected_c1_c1 = static_cast<int>(0.123 * 0.456 * 32);
668   ASSERT_EQ(entry_c1_c1.value_uint64, expected_c1_c1);
669 
670   CalculateNodeEffectiveSize(c1_c2);
671   const Node::Entry& entry_c1_c2 =
672       c1_c2->entries()->find("effective_size")->second;
673   uint64_t expected_c1_c2 = static_cast<int>(0.789 * 0.987 * 20);
674   ASSERT_EQ(entry_c1_c2.value_uint64, expected_c1_c2);
675 
676   CalculateNodeEffectiveSize(c1);
677   const Node::Entry& entry_c1 = c1->entries()->find("effective_size")->second;
678   ASSERT_EQ(entry_c1.value_uint64, expected_c1_c1 + expected_c1_c2);
679 }
680 
681 }  // namespace trace_processor
682 }  // namespace perfetto
683