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