1 /* 2 * Copyright (C) 2015 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_H_ 18 #define SIMPLE_PERF_CALLCHAIN_H_ 19 20 #include <string.h> 21 22 #include <algorithm> 23 #include <functional> 24 #include <memory> 25 #include <queue> 26 #include <vector> 27 28 #include <android-base/logging.h> 29 30 namespace simpleperf { 31 32 template <typename EntryT> 33 struct CallChainNode { 34 uint64_t period; 35 uint64_t children_period; 36 std::vector<EntryT*> chain; 37 std::vector<std::unique_ptr<CallChainNode>> children; 38 }; 39 40 template <typename EntryT> 41 struct CallChainRoot { 42 typedef CallChainNode<EntryT> NodeT; 43 // If duplicated = true, this call tree is part of another call tree. 44 // And we don't need to show it in brief callgraph report mode. 45 bool duplicated; 46 uint64_t children_period; 47 std::vector<std::unique_ptr<NodeT>> children; 48 CallChainRootCallChainRoot49 CallChainRoot() : duplicated(false), children_period(0) {} 50 AddCallChainCallChainRoot51 void AddCallChain(const std::vector<EntryT*>& callchain, uint64_t period, 52 std::function<bool(const EntryT*, const EntryT*)> is_same_sample) { 53 children_period += period; 54 NodeT* p = FindMatchingNode(children, callchain[0], is_same_sample); 55 if (p == nullptr) { 56 std::unique_ptr<NodeT> new_node = AllocateNode(callchain, 0, period, 0); 57 children.push_back(std::move(new_node)); 58 return; 59 } 60 size_t callchain_pos = 0; 61 while (true) { 62 size_t match_length = GetMatchingLengthInNode(p, callchain, callchain_pos, is_same_sample); 63 CHECK_GT(match_length, 0u); 64 callchain_pos += match_length; 65 bool find_child = true; 66 if (match_length < p->chain.size()) { 67 SplitNode(p, match_length); 68 find_child = false; // No need to find matching node in p->children. 69 } 70 if (callchain_pos == callchain.size()) { 71 p->period += period; 72 return; 73 } 74 p->children_period += period; 75 if (find_child) { 76 NodeT* np = FindMatchingNode(p->children, callchain[callchain_pos], is_same_sample); 77 if (np != nullptr) { 78 p = np; 79 continue; 80 } 81 } 82 std::unique_ptr<NodeT> new_node = AllocateNode(callchain, callchain_pos, period, 0); 83 p->children.push_back(std::move(new_node)); 84 break; 85 } 86 } 87 SortByPeriodCallChainRoot88 void SortByPeriod() { 89 std::queue<std::vector<std::unique_ptr<NodeT>>*> queue; 90 queue.push(&children); 91 while (!queue.empty()) { 92 std::vector<std::unique_ptr<NodeT>>* v = queue.front(); 93 queue.pop(); 94 std::sort(v->begin(), v->end(), CallChainRoot::CompareNodeByPeriod); 95 for (auto& node : *v) { 96 if (!node->children.empty()) { 97 queue.push(&node->children); 98 } 99 } 100 } 101 } 102 103 private: FindMatchingNodeCallChainRoot104 NodeT* FindMatchingNode(const std::vector<std::unique_ptr<NodeT>>& nodes, const EntryT* sample, 105 std::function<bool(const EntryT*, const EntryT*)> is_same_sample) { 106 for (auto& node : nodes) { 107 if (is_same_sample(node->chain.front(), sample)) { 108 return node.get(); 109 } 110 } 111 return nullptr; 112 } 113 GetMatchingLengthInNodeCallChainRoot114 size_t GetMatchingLengthInNode(NodeT* node, const std::vector<EntryT*>& chain, size_t chain_start, 115 std::function<bool(const EntryT*, const EntryT*)> is_same_sample) { 116 size_t i, j; 117 for (i = 0, j = chain_start; i < node->chain.size() && j < chain.size(); ++i, ++j) { 118 if (!is_same_sample(node->chain[i], chain[j])) { 119 break; 120 } 121 } 122 return i; 123 } 124 SplitNodeCallChainRoot125 void SplitNode(NodeT* parent, size_t parent_length) { 126 std::unique_ptr<NodeT> child = 127 AllocateNode(parent->chain, parent_length, parent->period, parent->children_period); 128 child->children = std::move(parent->children); 129 parent->period = 0; 130 parent->children_period = child->period + child->children_period; 131 parent->chain.resize(parent_length); 132 parent->children.clear(); 133 parent->children.push_back(std::move(child)); 134 } 135 AllocateNodeCallChainRoot136 std::unique_ptr<NodeT> AllocateNode(const std::vector<EntryT*>& chain, size_t chain_start, 137 uint64_t period, uint64_t children_period) { 138 std::unique_ptr<NodeT> node(new NodeT); 139 for (size_t i = chain_start; i < chain.size(); ++i) { 140 node->chain.push_back(chain[i]); 141 } 142 node->period = period; 143 node->children_period = children_period; 144 return node; 145 } 146 CompareNodeByPeriodCallChainRoot147 static bool CompareNodeByPeriod(const std::unique_ptr<NodeT>& n1, 148 const std::unique_ptr<NodeT>& n2) { 149 uint64_t period1 = n1->period + n1->children_period; 150 uint64_t period2 = n2->period + n2->children_period; 151 return period1 > period2; 152 } 153 }; 154 155 } // namespace simpleperf 156 157 #endif // SIMPLE_PERF_CALLCHAIN_H_ 158