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 #ifndef SRC_PROFILING_COMMON_CALLSTACK_TRIE_H_
18 #define SRC_PROFILING_COMMON_CALLSTACK_TRIE_H_
19 
20 #include <set>
21 #include <string>
22 #include <typeindex>
23 #include <vector>
24 
25 #include <unwindstack/Unwinder.h>
26 
27 #include "src/profiling/common/interner.h"
28 #include "src/profiling/common/unwind_support.h"
29 
30 namespace perfetto {
31 namespace profiling {
32 
33 struct Mapping {
MappingMapping34   explicit Mapping(Interned<std::string> b) : build_id(std::move(b)) {}
35 
36   Interned<std::string> build_id;
37   uint64_t exact_offset = 0;
38   uint64_t start_offset = 0;
39   uint64_t start = 0;
40   uint64_t end = 0;
41   uint64_t load_bias = 0;
42   std::vector<Interned<std::string>> path_components{};
43 
44   bool operator<(const Mapping& other) const {
45     return std::tie(build_id, exact_offset, start_offset, start, end, load_bias,
46                     path_components) <
47            std::tie(other.build_id, other.exact_offset, other.start_offset,
48                     other.start, other.end, other.load_bias,
49                     other.path_components);
50   }
51   bool operator==(const Mapping& other) const {
52     return std::tie(build_id, exact_offset, start_offset, start, end, load_bias,
53                     path_components) ==
54            std::tie(other.build_id, other.exact_offset, other.start_offset,
55                     other.start, other.end, other.load_bias,
56                     other.path_components);
57   }
58 };
59 
60 struct Frame {
FrameFrame61   Frame(Interned<Mapping> m, Interned<std::string> fn_name, uint64_t pc)
62       : mapping(m), function_name(fn_name), rel_pc(pc) {}
63   Interned<Mapping> mapping;
64   Interned<std::string> function_name;
65   uint64_t rel_pc;
66 
67   bool operator<(const Frame& other) const {
68     return std::tie(mapping, function_name, rel_pc) <
69            std::tie(other.mapping, other.function_name, other.rel_pc);
70   }
71 
72   bool operator==(const Frame& other) const {
73     return std::tie(mapping, function_name, rel_pc) ==
74            std::tie(other.mapping, other.function_name, other.rel_pc);
75   }
76 };
77 
78 // Graph of function callsites. A single instance can be used for callsites from
79 // different processes. Each call site is represented by a
80 // GlobalCallstackTrie::Node that is owned by the parent callsite. Each node has
81 // a pointer to its parent, which means the function call-graph can be
82 // reconstructed from a GlobalCallstackTrie::Node by walking down the parent
83 // chain.
84 //
85 // For the following two callstacks:
86 //  * libc_init -> main -> foo -> alloc_buf
87 //  * libc_init -> main -> bar -> alloc_buf
88 // The tree looks as following:
89 //             alloc_buf  alloc_buf
90 //                   |      |
91 //                  foo    bar
92 //                    \    /
93 //                      main
94 //                       |
95 //                   libc_init
96 //                       |
97 //                    [root_]
98 class GlobalCallstackTrie {
99  public:
100   // Optionally, Nodes can be externally refcounted via |IncrementNode| and
101   // |DecrementNode|. In which case, the orphaned nodes are deleted when the
102   // last reference is decremented.
103   class Node {
104    public:
105     // This is opaque except to GlobalCallstackTrie.
106     friend class GlobalCallstackTrie;
107 
108     // Allow building a node out of a frame for GetChild.
Node(Interned<Frame> frame)109     explicit Node(Interned<Frame> frame) : Node(frame, 0, nullptr) {}
110     Node(const Node&) = default;
111     Node(Node&&) = default;
112 
Node(Interned<Frame> frame,uint64_t id)113     Node(Interned<Frame> frame, uint64_t id)
114         : Node(std::move(frame), id, nullptr) {}
Node(Interned<Frame> frame,uint64_t id,Node * parent)115     Node(Interned<Frame> frame, uint64_t id, Node* parent)
116         : id_(id), parent_(parent), location_(frame) {}
117 
~Node()118     ~Node() { PERFETTO_DCHECK(!ref_count_); }
119 
id()120     uint64_t id() const { return id_; }
121 
122    private:
123     Node* GetOrCreateChild(const Interned<Frame>& loc);
124     // Deletes all descendant nodes, regardless of |ref_count_|.
DeleteChildren()125     void DeleteChildren() { children_.clear(); }
126 
127     uint64_t ref_count_ = 0;
128     uint64_t id_;
129     Node* const parent_;
130     const Interned<Frame> location_;
131 
132     class NodeComparator {
133      public:
operator()134       bool operator()(const Node& one, const Node& other) const {
135         return one.location_ < other.location_;
136       }
137     };
138     Node* AddChild(const Interned<Frame>& loc,
139                    uint64_t next_callstack_id_,
140                    Node* parent);
141     void RemoveChild(Node* node);
142     Node* GetChild(const Interned<Frame>& loc);
143 
144     std::set<Node, NodeComparator> children_;
145   };
146 
147   GlobalCallstackTrie() = default;
148   ~GlobalCallstackTrie() = default;
149   GlobalCallstackTrie(const GlobalCallstackTrie&) = delete;
150   GlobalCallstackTrie& operator=(const GlobalCallstackTrie&) = delete;
151 
152   // Moving this would invalidate the back pointers to the root_ node.
153   GlobalCallstackTrie(GlobalCallstackTrie&&) = delete;
154   GlobalCallstackTrie& operator=(GlobalCallstackTrie&&) = delete;
155 
156   Interned<Frame> InternCodeLocation(const unwindstack::FrameData& loc,
157                                      const std::string& build_id);
158 
159   Node* CreateCallsite(const std::vector<unwindstack::FrameData>& callstack,
160                        const std::vector<std::string>& build_ids);
161   Node* CreateCallsite(const std::vector<Interned<Frame>>& callstack);
162 
163   static void IncrementNode(Node* node);
164   static void DecrementNode(Node* node);
165 
166   std::vector<Interned<Frame>> BuildInverseCallstack(const Node* node) const;
167 
168   // Purges all interned callstacks (and the associated internings), without
169   // restarting any interning sequences. Incompatible with external refcounting
170   // of nodes (Node.ref_count_).
ClearTrie()171   void ClearTrie() {
172     PERFETTO_DLOG("Clearing trie");
173     root_.DeleteChildren();
174   }
175 
176  private:
177   Node* GetOrCreateChild(Node* self, const Interned<Frame>& loc);
178 
179   Interned<Frame> MakeRootFrame();
180 
181   Interner<std::string> string_interner_;
182   Interner<Mapping> mapping_interner_;
183   Interner<Frame> frame_interner_;
184 
185   uint64_t next_callstack_id_ = 0;
186 
187   Node root_{MakeRootFrame(), ++next_callstack_id_};
188 };
189 
190 }  // namespace profiling
191 }  // namespace perfetto
192 
193 template <>
194 struct std::hash<::perfetto::profiling::Mapping> {
195   using argument_type = ::perfetto::profiling::Mapping;
196   using result_type = size_t;
197   result_type operator()(const argument_type& mapping) {
198     size_t h =
199         std::hash<::perfetto::profiling::InternID>{}(mapping.build_id.id());
200     h ^= std::hash<uint64_t>{}(mapping.exact_offset);
201     h ^= std::hash<uint64_t>{}(mapping.start_offset);
202     h ^= std::hash<uint64_t>{}(mapping.start);
203     h ^= std::hash<uint64_t>{}(mapping.end);
204     h ^= std::hash<uint64_t>{}(mapping.load_bias);
205     for (const auto& path : mapping.path_components)
206       h ^= std::hash<uint64_t>{}(path.id());
207     return h;
208   }
209 };
210 
211 template <>
212 struct std::hash<::perfetto::profiling::Frame> {
213   using argument_type = ::perfetto::profiling::Frame;
214   using result_type = size_t;
215   result_type operator()(const argument_type& frame) {
216     size_t h = std::hash<::perfetto::profiling::InternID>{}(frame.mapping.id());
217     h ^= std::hash<::perfetto::profiling::InternID>{}(frame.function_name.id());
218     h ^= std::hash<uint64_t>{}(frame.rel_pc);
219     return h;
220   }
221 };
222 
223 #endif  // SRC_PROFILING_COMMON_CALLSTACK_TRIE_H_
224