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 "src/profiling/common/callstack_trie.h"
18
19 #include <vector>
20
21 #include "perfetto/ext/base/string_splitter.h"
22 #include "src/profiling/common/interner.h"
23 #include "src/profiling/common/unwind_support.h"
24
25 namespace perfetto {
26 namespace profiling {
27
GetOrCreateChild(Node * self,const Interned<Frame> & loc)28 GlobalCallstackTrie::Node* GlobalCallstackTrie::GetOrCreateChild(
29 Node* self,
30 const Interned<Frame>& loc) {
31 Node* child = self->children_.Get(loc);
32 if (!child)
33 child = self->children_.Emplace(loc, ++next_callstack_id_, self);
34 return child;
35 }
36
BuildInverseCallstack(const Node * node) const37 std::vector<Interned<Frame>> GlobalCallstackTrie::BuildInverseCallstack(
38 const Node* node) const {
39 std::vector<Interned<Frame>> res;
40 while (node != &root_) {
41 res.emplace_back(node->location_);
42 node = node->parent_;
43 }
44 return res;
45 }
46
CreateCallsite(const std::vector<FrameData> & callstack)47 GlobalCallstackTrie::Node* GlobalCallstackTrie::CreateCallsite(
48 const std::vector<FrameData>& callstack) {
49 Node* node = &root_;
50 // libunwindstack gives the frames top-first, but we want to bookkeep and
51 // emit as bottom first.
52 for (auto it = callstack.crbegin(); it != callstack.crend(); ++it) {
53 const FrameData& loc = *it;
54 node = GetOrCreateChild(node, InternCodeLocation(loc));
55 }
56 return node;
57 }
58
CreateCallsite(const std::vector<Interned<Frame>> & callstack)59 GlobalCallstackTrie::Node* GlobalCallstackTrie::CreateCallsite(
60 const std::vector<Interned<Frame>>& callstack) {
61 Node* node = &root_;
62 // libunwindstack gives the frames top-first, but we want to bookkeep and
63 // emit as bottom first.
64 for (auto it = callstack.crbegin(); it != callstack.crend(); ++it) {
65 const Interned<Frame>& loc = *it;
66 node = GetOrCreateChild(node, loc);
67 }
68 return node;
69 }
70
IncrementNode(Node * node)71 void GlobalCallstackTrie::IncrementNode(Node* node) {
72 while (node != nullptr) {
73 node->ref_count_ += 1;
74 node = node->parent_;
75 }
76 }
77
DecrementNode(Node * node)78 void GlobalCallstackTrie::DecrementNode(Node* node) {
79 PERFETTO_DCHECK(node->ref_count_ >= 1);
80
81 bool delete_prev = false;
82 Node* prev = nullptr;
83 while (node != nullptr) {
84 if (delete_prev)
85 node->children_.Remove(*prev);
86 node->ref_count_ -= 1;
87 delete_prev = node->ref_count_ == 0;
88 prev = node;
89 node = node->parent_;
90 }
91 }
92
InternCodeLocation(const FrameData & loc)93 Interned<Frame> GlobalCallstackTrie::InternCodeLocation(const FrameData& loc) {
94 Mapping map(string_interner_.Intern(loc.build_id));
95 map.exact_offset = loc.frame.map_exact_offset;
96 map.start_offset = loc.frame.map_elf_start_offset;
97 map.start = loc.frame.map_start;
98 map.end = loc.frame.map_end;
99 map.load_bias = loc.frame.map_load_bias;
100 base::StringSplitter sp(loc.frame.map_name, '/');
101 while (sp.Next())
102 map.path_components.emplace_back(string_interner_.Intern(sp.cur_token()));
103
104 Frame frame(mapping_interner_.Intern(std::move(map)),
105 string_interner_.Intern(loc.frame.function_name),
106 loc.frame.rel_pc);
107
108 return frame_interner_.Intern(frame);
109 }
110
MakeRootFrame()111 Interned<Frame> GlobalCallstackTrie::MakeRootFrame() {
112 Mapping map(string_interner_.Intern(""));
113
114 Frame frame(mapping_interner_.Intern(std::move(map)),
115 string_interner_.Intern(""), 0);
116
117 return frame_interner_.Intern(frame);
118 }
119
120 } // namespace profiling
121 } // namespace perfetto
122