1 /* 2 * Copyright (C) 2017 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 SIMPLE_PERF_CALLCHAIN_JOINER_H_ 18 #define SIMPLE_PERF_CALLCHAIN_JOINER_H_ 19 20 #include <inttypes.h> 21 #include <stdio.h> 22 #include <unistd.h> 23 24 #include <unordered_set> 25 #include <vector> 26 27 namespace simpleperf { 28 29 namespace call_chain_joiner_impl { 30 31 // Each node represents a function in a call chain, having a tuple info (tid, ip, sp). 32 // A node remembers its parent in the call chain. 33 struct CacheNode { 34 uint64_t ip; 35 uint64_t sp; 36 uint32_t tid; 37 // Whether the node is at the bottom of a call chain. 38 uint32_t is_leaf : 1; 39 // The index of the parent node in a call chain. 40 uint32_t parent_index : 31; 41 // When is_leaf = false, children_count remembers how many nodes have current node as parent. 42 // When is_leaf = true, leaf_link_prev and leaf_link_next keeps current node in a LRU linked list. 43 union { 44 uint32_t children_count; 45 struct { 46 uint32_t leaf_link_prev; 47 uint32_t leaf_link_next; 48 }; 49 }; 50 }; 51 52 static_assert(sizeof(CacheNode) == 32, ""); 53 54 struct LRUCacheStat { 55 size_t cache_size = 0u; 56 size_t matched_node_count_to_extend_callchain = 0u; 57 size_t max_node_count = 0u; 58 size_t used_node_count = 0u; 59 size_t recycled_node_count = 0u; 60 }; 61 62 // LRUCache caches call chains in memory, and supports extending a call chain if the (tid, ip, sp) 63 // tuples of its top [matched_node_count_to_extend_callchain] appear in the cache. 64 class LRUCache { 65 public: 66 // cache_size is the bytes of memory we want to use in this cache. 67 // matched_node_count_to_extend_callchain decides how many nodes we need to match to extend a 68 // call chain. Higher value means more strict. 69 LRUCache(size_t cache_size = 8 * 1024 * 1024, size_t matched_node_count_to_extend_callchain = 1); 70 ~LRUCache(); 71 72 // Add a call chain in the cache, and extend it if possible. 73 void AddCallChain(pid_t tid, std::vector<uint64_t>& ips, std::vector<uint64_t>& sps); 74 Stat()75 const LRUCacheStat& Stat() { return cache_stat_; } 76 FindNode(uint32_t tid,uint64_t ip,uint64_t sp)77 CacheNode* FindNode(uint32_t tid, uint64_t ip, uint64_t sp) { 78 CacheNode key; 79 key.tid = tid; 80 key.ip = ip; 81 key.sp = sp; 82 auto it = node_set_.find(&key); 83 return it != node_set_.end() ? *it : nullptr; 84 } 85 86 private: 87 static bool CacheNodeEqual(const CacheNode* n1, const CacheNode* n2); 88 static size_t CacheNodeHash(const CacheNode* n); 89 90 typedef std::unordered_set<CacheNode*, decltype(&CacheNodeHash), decltype(&CacheNodeEqual)> 91 set_type; 92 GetParent(CacheNode * node)93 CacheNode* GetParent(CacheNode* node) { 94 return node->parent_index == 0u ? nullptr : nodes_ + node->parent_index; 95 } 96 GetNodeIndex(CacheNode * node)97 int GetNodeIndex(CacheNode* node) { return node - nodes_; } 98 RemoveNodeFromLRUList(CacheNode * node)99 void RemoveNodeFromLRUList(CacheNode* node) { 100 CacheNode* prev = &nodes_[node->leaf_link_prev]; 101 CacheNode* next = &nodes_[node->leaf_link_next]; 102 prev->leaf_link_next = node->leaf_link_next; 103 next->leaf_link_prev = node->leaf_link_prev; 104 } 105 AppendNodeToLRUList(CacheNode * node)106 void AppendNodeToLRUList(CacheNode* node) { 107 CacheNode* next = &nodes_[0]; 108 CacheNode* prev = &nodes_[next->leaf_link_prev]; 109 node->leaf_link_next = 0; 110 node->leaf_link_prev = next->leaf_link_prev; 111 next->leaf_link_prev = prev->leaf_link_next = GetNodeIndex(node); 112 } 113 DecreaseChildCountOfNode(CacheNode * node)114 void DecreaseChildCountOfNode(CacheNode* node) { 115 if (--node->children_count == 0u) { 116 node->is_leaf = true; 117 AppendNodeToLRUList(node); 118 } 119 } 120 121 CacheNode* GetNode(uint32_t tid, uint64_t ip, uint64_t sp); 122 CacheNode* AllocNode(); 123 void LinkParent(CacheNode* child, CacheNode* new_parent); 124 void UnlinkParent(CacheNode* child); 125 126 CacheNode* nodes_; 127 set_type node_set_; 128 LRUCacheStat cache_stat_; 129 }; 130 131 } // namespace call_chain_joiner_impl 132 133 // CallChainJoiner is used to join callchains of samples in the same thread, in order to get 134 // complete call graph. For example, if we have two samples for a thread: 135 // sample 1: (ip A, sp A) -> (ip B, sp B) -> (ip C, sp C) -> ... 136 // sample 2: (ip B, sp B) -> (ip C, sp C) -> ... 137 // Because we know (ip A, sp A) calls (ip B, sp B) in sample 1, then we can guess the (ip B, sp B) 138 // in sample 2 is also called from (ip A, sp A). So we can add (ip A, sp A) in sample 2 as below. 139 // sample 2: (ip A, sp A) -> (ip B, sp B) -> (ip C, sp C) -> ... 140 class CallChainJoiner { 141 public: 142 // The parameters are used in LRUCache. 143 CallChainJoiner(size_t cache_size, size_t matched_node_count_to_extend_callchain, 144 bool keep_original_callchains); 145 ~CallChainJoiner(); 146 147 enum ChainType { 148 ORIGINAL_OFFLINE, 149 ORIGINAL_REMOTE, 150 JOINED_OFFLINE, 151 JOINED_REMOTE, 152 }; 153 154 bool AddCallChain(pid_t pid, pid_t tid, ChainType type, const std::vector<uint64_t>& ips, 155 const std::vector<uint64_t>& sps); 156 bool JoinCallChains(); 157 bool GetNextCallChain(pid_t& pid, pid_t& tid, ChainType& type, std::vector<uint64_t>& ips, 158 std::vector<uint64_t>& sps); 159 160 struct Stat { 161 size_t chain_count = 0u; 162 size_t before_join_node_count = 0u; 163 size_t after_join_node_count = 0u; 164 size_t after_join_max_chain_length = 0u; 165 }; 166 void DumpStat(); GetStat()167 const Stat& GetStat() { return stat_; } GetCacheStat()168 const call_chain_joiner_impl::LRUCacheStat& GetCacheStat() { return cache_stat_; } 169 170 private: 171 bool keep_original_callchains_; 172 FILE* original_chains_fp_; 173 FILE* joined_chains_fp_; 174 size_t next_chain_index_; 175 call_chain_joiner_impl::LRUCacheStat cache_stat_; 176 Stat stat_; 177 }; 178 179 } // namespace simpleperf 180 181 #endif // SIMPLE_PERF_CALLCHAIN_JOINER_H_ 182