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