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 map.exact_offset = loc.map_exact_offset;
104 map.start_offset = loc.map_elf_start_offset;
105 map.start = loc.map_start;
106 map.end = loc.map_end;
107 map.load_bias = loc.map_load_bias;
108 base::StringSplitter sp(loc.map_name, '/');
109 while (sp.Next())
110 map.path_components.emplace_back(string_interner_.Intern(sp.cur_token()));
111
112 Frame frame(mapping_interner_.Intern(std::move(map)),
113 string_interner_.Intern(loc.function_name), loc.rel_pc);
114
115 return frame_interner_.Intern(frame);
116 }
117
MakeRootFrame()118 Interned<Frame> GlobalCallstackTrie::MakeRootFrame() {
119 Mapping map(string_interner_.Intern(""));
120
121 Frame frame(mapping_interner_.Intern(std::move(map)),
122 string_interner_.Intern(""), 0);
123
124 return frame_interner_.Intern(frame);
125 }
126
AddChild(const Interned<Frame> & loc,uint64_t callstack_id,Node * parent)127 GlobalCallstackTrie::Node* GlobalCallstackTrie::Node::AddChild(
128 const Interned<Frame>& loc,
129 uint64_t callstack_id,
130 Node* parent) {
131 auto it = children_.emplace(loc, callstack_id, parent);
132 return const_cast<Node*>(&(*it.first));
133 }
RemoveChild(Node * node)134 void GlobalCallstackTrie::Node::RemoveChild(Node* node) {
135 children_.erase(*node);
136 }
137
GetChild(const Interned<Frame> & loc)138 GlobalCallstackTrie::Node* GlobalCallstackTrie::Node::GetChild(
139 const Interned<Frame>& loc) {
140 // This will be nicer with C++14 transparent comparators.
141 // Then we will be able to look up by just the key using a sutiable
142 // comparator.
143 //
144 // For now we need to allow to construct Node from the key.
145 Node node(loc);
146 auto it = children_.find(node);
147 if (it == children_.end())
148 return nullptr;
149 return const_cast<Node*>(&(*it));
150 }
151
152 } // namespace profiling
153 } // namespace perfetto
154