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.h"
18 
19 #include "perfetto/base/build_config.h"
20 #include "test/gtest_and_gmock.h"
21 
22 namespace perfetto {
23 namespace trace_processor {
24 
25 namespace {
26 
27 using Node = GlobalNodeGraph::Node;
28 using Process = GlobalNodeGraph::Process;
29 
30 const MemoryAllocatorNodeId kEmptyId;
31 
32 }  // namespace
33 
TEST(GlobalNodeGraphTest,CreateContainerForProcess)34 TEST(GlobalNodeGraphTest, CreateContainerForProcess) {
35   GlobalNodeGraph global_dump_graph;
36 
37   Process* dump = global_dump_graph.CreateGraphForProcess(10);
38   ASSERT_NE(dump, nullptr);
39 
40   auto* map = global_dump_graph.process_node_graphs().find(10)->second.get();
41   ASSERT_EQ(dump, map);
42 }
43 
TEST(GlobalNodeGraphTest,AddNodeOwnershipEdge)44 TEST(GlobalNodeGraphTest, AddNodeOwnershipEdge) {
45   GlobalNodeGraph global_dump_graph;
46   Node owner(global_dump_graph.shared_memory_graph(), nullptr);
47   Node owned(global_dump_graph.shared_memory_graph(), nullptr);
48 
49   global_dump_graph.AddNodeOwnershipEdge(&owner, &owned, 1);
50 
51   auto& edges = global_dump_graph.edges();
52   ASSERT_NE(edges.begin(), edges.end());
53 
54   auto& edge = *edges.begin();
55   ASSERT_EQ(edge.source(), &owner);
56   ASSERT_EQ(edge.target(), &owned);
57   ASSERT_EQ(edge.priority(), 1);
58 }
59 
TEST(GlobalNodeGraphTest,VisitInDepthFirstPostOrder)60 TEST(GlobalNodeGraphTest, VisitInDepthFirstPostOrder) {
61   GlobalNodeGraph graph;
62   Process* process_1 = graph.CreateGraphForProcess(1);
63   Process* process_2 = graph.CreateGraphForProcess(2);
64 
65   Node* c1 = process_1->CreateNode(kEmptyId, "c1", false);
66   Node* c2 = process_1->CreateNode(kEmptyId, "c2", false);
67   Node* c2_c1 = process_1->CreateNode(kEmptyId, "c2/c1", false);
68   Node* c2_c2 = process_1->CreateNode(kEmptyId, "c2/c2", false);
69 
70   Node* c3 = process_2->CreateNode(kEmptyId, "c3", false);
71   Node* c3_c1 = process_2->CreateNode(kEmptyId, "c3/c1", false);
72   Node* c3_c2 = process_2->CreateNode(kEmptyId, "c3/c2", false);
73 
74   // |c3_c2| owns |c2_c2|.
75   graph.AddNodeOwnershipEdge(c3_c2, c2_c2, 1);
76 
77   // This method should always call owners and then children before the node
78   // itself.
79   auto iterator = graph.VisitInDepthFirstPostOrder();
80   ASSERT_EQ(iterator.next(), graph.shared_memory_graph()->root());
81   ASSERT_EQ(iterator.next(), c1);
82   ASSERT_EQ(iterator.next(), c2_c1);
83   ASSERT_EQ(iterator.next(), c3_c2);
84   ASSERT_EQ(iterator.next(), c2_c2);
85   ASSERT_EQ(iterator.next(), c2);
86   ASSERT_EQ(iterator.next(), process_1->root());
87   ASSERT_EQ(iterator.next(), c3_c1);
88   ASSERT_EQ(iterator.next(), c3);
89   ASSERT_EQ(iterator.next(), process_2->root());
90   ASSERT_EQ(iterator.next(), nullptr);
91 }
92 
TEST(GlobalNodeGraphTest,VisitInDepthFirstPreOrder)93 TEST(GlobalNodeGraphTest, VisitInDepthFirstPreOrder) {
94   GlobalNodeGraph graph;
95   Process* process_1 = graph.CreateGraphForProcess(1);
96   Process* process_2 = graph.CreateGraphForProcess(2);
97 
98   Node* c1 = process_1->CreateNode(kEmptyId, "c1", false);
99   Node* c2 = process_1->CreateNode(kEmptyId, "c2", false);
100   Node* c2_c1 = process_1->CreateNode(kEmptyId, "c2/c1", false);
101   Node* c2_c2 = process_1->CreateNode(kEmptyId, "c2/c2", false);
102 
103   Node* c3 = process_2->CreateNode(kEmptyId, "c3", false);
104   Node* c3_c1 = process_2->CreateNode(kEmptyId, "c3/c1", false);
105   Node* c3_c2 = process_2->CreateNode(kEmptyId, "c3/c2", false);
106 
107   // |c2_c2| owns |c3_c2|. Note this is opposite of post-order.
108   graph.AddNodeOwnershipEdge(c2_c2, c3_c2, 1);
109 
110   // This method should always call owners and then children after the node
111   // itself.
112   auto iterator = graph.VisitInDepthFirstPreOrder();
113   ASSERT_EQ(iterator.next(), graph.shared_memory_graph()->root());
114   ASSERT_EQ(iterator.next(), process_1->root());
115   ASSERT_EQ(iterator.next(), c1);
116   ASSERT_EQ(iterator.next(), c2);
117   ASSERT_EQ(iterator.next(), c2_c1);
118   ASSERT_EQ(iterator.next(), process_2->root());
119   ASSERT_EQ(iterator.next(), c3);
120   ASSERT_EQ(iterator.next(), c3_c1);
121   ASSERT_EQ(iterator.next(), c3_c2);
122   ASSERT_EQ(iterator.next(), c2_c2);
123   ASSERT_EQ(iterator.next(), nullptr);
124 }
125 
TEST(ProcessTest,CreateAndFindNode)126 TEST(ProcessTest, CreateAndFindNode) {
127   GlobalNodeGraph global_dump_graph;
128   Process graph(1, &global_dump_graph);
129 
130   Node* first =
131       graph.CreateNode(MemoryAllocatorNodeId(1), "simple/test/1", false);
132   Node* second =
133       graph.CreateNode(MemoryAllocatorNodeId(2), "simple/test/2", false);
134   Node* third =
135       graph.CreateNode(MemoryAllocatorNodeId(3), "simple/other/1", false);
136   Node* fourth =
137       graph.CreateNode(MemoryAllocatorNodeId(4), "complex/path", false);
138   Node* fifth =
139       graph.CreateNode(MemoryAllocatorNodeId(5), "complex/path/child/1", false);
140 
141   ASSERT_EQ(graph.FindNode("simple/test/1"), first);
142   ASSERT_EQ(graph.FindNode("simple/test/2"), second);
143   ASSERT_EQ(graph.FindNode("simple/other/1"), third);
144   ASSERT_EQ(graph.FindNode("complex/path"), fourth);
145   ASSERT_EQ(graph.FindNode("complex/path/child/1"), fifth);
146 
147   auto& nodes_by_id = global_dump_graph.nodes_by_id();
148   ASSERT_EQ(nodes_by_id.find(MemoryAllocatorNodeId(1))->second, first);
149   ASSERT_EQ(nodes_by_id.find(MemoryAllocatorNodeId(2))->second, second);
150   ASSERT_EQ(nodes_by_id.find(MemoryAllocatorNodeId(3))->second, third);
151   ASSERT_EQ(nodes_by_id.find(MemoryAllocatorNodeId(4))->second, fourth);
152   ASSERT_EQ(nodes_by_id.find(MemoryAllocatorNodeId(5))->second, fifth);
153 }
154 
TEST(ProcessTest,CreateNodeParent)155 TEST(ProcessTest, CreateNodeParent) {
156   GlobalNodeGraph global_dump_graph;
157   Process graph(1, &global_dump_graph);
158 
159   Node* parent = graph.CreateNode(MemoryAllocatorNodeId(1), "simple", false);
160   Node* child =
161       graph.CreateNode(MemoryAllocatorNodeId(1), "simple/child", false);
162 
163   ASSERT_EQ(parent->parent(), graph.root());
164   ASSERT_EQ(child->parent(), parent);
165 }
166 
TEST(ProcessTest,WeakAndExplicit)167 TEST(ProcessTest, WeakAndExplicit) {
168   GlobalNodeGraph global_dump_graph;
169   Process graph(1, &global_dump_graph);
170 
171   Node* first =
172       graph.CreateNode(MemoryAllocatorNodeId(1), "simple/test/1", true);
173   Node* second =
174       graph.CreateNode(MemoryAllocatorNodeId(2), "simple/test/2", false);
175 
176   ASSERT_TRUE(first->is_weak());
177   ASSERT_FALSE(second->is_weak());
178 
179   ASSERT_TRUE(first->is_explicit());
180   ASSERT_TRUE(second->is_explicit());
181 
182   Node* parent = graph.FindNode("simple/test");
183   ASSERT_NE(parent, nullptr);
184   ASSERT_FALSE(parent->is_weak());
185   ASSERT_FALSE(parent->is_explicit());
186 
187   Node* grandparent = graph.FindNode("simple");
188   ASSERT_NE(grandparent, nullptr);
189   ASSERT_FALSE(grandparent->is_weak());
190   ASSERT_FALSE(grandparent->is_explicit());
191 }
192 
TEST(NodeTest,GetChild)193 TEST(NodeTest, GetChild) {
194   GlobalNodeGraph global_dump_graph;
195   Node node(global_dump_graph.shared_memory_graph(), nullptr);
196 
197   ASSERT_EQ(node.GetChild("test"), nullptr);
198 
199   Node child(global_dump_graph.shared_memory_graph(), &node);
200   node.InsertChild("child", &child);
201   ASSERT_EQ(node.GetChild("child"), &child);
202 }
203 
TEST(NodeTest,InsertChild)204 TEST(NodeTest, InsertChild) {
205   GlobalNodeGraph global_dump_graph;
206   Node node(global_dump_graph.shared_memory_graph(), nullptr);
207 
208   ASSERT_EQ(node.GetChild("test"), nullptr);
209 
210   Node child(global_dump_graph.shared_memory_graph(), &node);
211   node.InsertChild("child", &child);
212   ASSERT_EQ(node.GetChild("child"), &child);
213 }
214 
TEST(NodeTest,AddEntry)215 TEST(NodeTest, AddEntry) {
216   GlobalNodeGraph global_dump_graph;
217   Node node(global_dump_graph.shared_memory_graph(), nullptr);
218 
219   node.AddEntry("scalar", Node::Entry::ScalarUnits::kBytes, 100ul);
220   ASSERT_EQ(node.entries()->size(), 1ul);
221 
222   node.AddEntry("string", "data");
223   ASSERT_EQ(node.entries()->size(), 2ul);
224 
225   auto scalar = node.entries()->find("scalar");
226   ASSERT_EQ(scalar->first, "scalar");
227   ASSERT_EQ(scalar->second.units, Node::Entry::ScalarUnits::kBytes);
228   ASSERT_EQ(scalar->second.value_uint64, 100ul);
229 
230   auto string = node.entries()->find("string");
231   ASSERT_EQ(string->first, "string");
232   ASSERT_EQ(string->second.value_string, "data");
233 }
234 
235 }  // namespace trace_processor
236 }  // namespace perfetto
237