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->GetChild(loc);
32 if (!child)
33 child = self->AddChild(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<unwindstack::FrameData> & callstack,const std::vector<std::string> & build_ids)47 GlobalCallstackTrie::Node* GlobalCallstackTrie::CreateCallsite(
48 const std::vector<unwindstack::FrameData>& callstack,
49 const std::vector<std::string>& build_ids) {
50 PERFETTO_CHECK(callstack.size() == build_ids.size());
51 Node* node = &root_;
52 // libunwindstack gives the frames top-first, but we want to bookkeep and
53 // emit as bottom first.
54 auto callstack_it = callstack.crbegin();
55 auto build_id_it = build_ids.crbegin();
56 for (; callstack_it != callstack.crend() && build_id_it != build_ids.crend();
57 ++callstack_it, ++build_id_it) {
58 const unwindstack::FrameData& loc = *callstack_it;
59 const std::string& build_id = *build_id_it;
60 node = GetOrCreateChild(node, InternCodeLocation(loc, build_id));
61 }
62 return node;
63 }
64
CreateCallsite(const std::vector<Interned<Frame>> & callstack)65 GlobalCallstackTrie::Node* GlobalCallstackTrie::CreateCallsite(
66 const std::vector<Interned<Frame>>& callstack) {
67 Node* node = &root_;
68 // libunwindstack gives the frames top-first, but we want to bookkeep and
69 // emit as bottom first.
70 for (auto it = callstack.crbegin(); it != callstack.crend(); ++it) {
71 const Interned<Frame>& loc = *it;
72 node = GetOrCreateChild(node, loc);
73 }
74 return node;
75 }
76
IncrementNode(Node * node)77 void GlobalCallstackTrie::IncrementNode(Node* node) {
78 while (node != nullptr) {
79 node->ref_count_ += 1;
80 node = node->parent_;
81 }
82 }
83
DecrementNode(Node * node)84 void GlobalCallstackTrie::DecrementNode(Node* node) {
85 PERFETTO_DCHECK(node->ref_count_ >= 1);
86
87 bool delete_prev = false;
88 Node* prev = nullptr;
89 while (node != nullptr) {
90 if (delete_prev)
91 node->RemoveChild(prev);
92 node->ref_count_ -= 1;
93 delete_prev = node->ref_count_ == 0;
94 prev = node;
95 node = node->parent_;
96 }
97 }
98
InternCodeLocation(const unwindstack::FrameData & loc,const std::string & build_id)99 Interned<Frame> GlobalCallstackTrie::InternCodeLocation(
100 const unwindstack::FrameData& loc,
101 const std::string& build_id) {
102 Mapping map(string_interner_.Intern(build_id));
103 if (loc.map_info != nullptr) {
104 map.exact_offset = loc.map_info->offset();
105 map.start_offset = loc.map_info->elf_start_offset();
106 map.start = loc.map_info->start();
107 map.end = loc.map_info->end();
108 map.load_bias = loc.map_info->GetLoadBias();
109 base::StringSplitter sp(loc.map_info->GetFullName(), '/');
110 while (sp.Next())
111 map.path_components.emplace_back(string_interner_.Intern(sp.cur_token()));
112 }
113
114 Frame frame(mapping_interner_.Intern(std::move(map)),
115 string_interner_.Intern(loc.function_name), loc.rel_pc);
116
117 return frame_interner_.Intern(frame);
118 }
119
MakeRootFrame()120 Interned<Frame> GlobalCallstackTrie::MakeRootFrame() {
121 Mapping map(string_interner_.Intern(""));
122
123 Frame frame(mapping_interner_.Intern(std::move(map)),
124 string_interner_.Intern(""), 0);
125
126 return frame_interner_.Intern(frame);
127 }
128
AddChild(const Interned<Frame> & loc,uint64_t callstack_id,Node * parent)129 GlobalCallstackTrie::Node* GlobalCallstackTrie::Node::AddChild(
130 const Interned<Frame>& loc,
131 uint64_t callstack_id,
132 Node* parent) {
133 auto it = children_.emplace(loc, callstack_id, parent);
134 return const_cast<Node*>(&(*it.first));
135 }
RemoveChild(Node * node)136 void GlobalCallstackTrie::Node::RemoveChild(Node* node) {
137 children_.erase(*node);
138 }
139
GetChild(const Interned<Frame> & loc)140 GlobalCallstackTrie::Node* GlobalCallstackTrie::Node::GetChild(
141 const Interned<Frame>& loc) {
142 // This will be nicer with C++14 transparent comparators.
143 // Then we will be able to look up by just the key using a sutiable
144 // comparator.
145 //
146 // For now we need to allow to construct Node from the key.
147 Node node(loc);
148 auto it = children_.find(node);
149 if (it == children_.end())
150 return nullptr;
151 return const_cast<Node*>(&(*it));
152 }
153
154 } // namespace profiling
155 } // namespace perfetto
156