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