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 template <typename EntryT> 31 struct CallChainNode { 32 uint64_t period; 33 uint64_t children_period; 34 std::vector<EntryT*> chain; 35 std::vector<std::unique_ptr<CallChainNode>> children; 36 }; 37 38 template <typename EntryT> 39 struct CallChainRoot { 40 typedef CallChainNode<EntryT> NodeT; 41 uint64_t children_period; 42 std::vector<std::unique_ptr<NodeT>> children; 43 CallChainRootCallChainRoot44 CallChainRoot() : children_period(0) {} 45 AddCallChainCallChainRoot46 void AddCallChain( 47 const std::vector<EntryT*>& callchain, uint64_t period, 48 std::function<bool(const EntryT*, const EntryT*)> is_same_sample) { 49 children_period += period; 50 NodeT* p = FindMatchingNode(children, callchain[0], is_same_sample); 51 if (p == nullptr) { 52 std::unique_ptr<NodeT> new_node = AllocateNode(callchain, 0, period, 0); 53 children.push_back(std::move(new_node)); 54 return; 55 } 56 size_t callchain_pos = 0; 57 while (true) { 58 size_t match_length = 59 GetMatchingLengthInNode(p, callchain, callchain_pos, is_same_sample); 60 CHECK_GT(match_length, 0u); 61 callchain_pos += match_length; 62 bool find_child = true; 63 if (match_length < p->chain.size()) { 64 SplitNode(p, match_length); 65 find_child = false; // No need to find matching node in p->children. 66 } 67 if (callchain_pos == callchain.size()) { 68 p->period += period; 69 return; 70 } 71 p->children_period += period; 72 if (find_child) { 73 NodeT* np = FindMatchingNode(p->children, callchain[callchain_pos], 74 is_same_sample); 75 if (np != nullptr) { 76 p = np; 77 continue; 78 } 79 } 80 std::unique_ptr<NodeT> new_node = 81 AllocateNode(callchain, callchain_pos, period, 0); 82 p->children.push_back(std::move(new_node)); 83 break; 84 } 85 } 86 SortByPeriodCallChainRoot87 void SortByPeriod() { 88 std::queue<std::vector<std::unique_ptr<NodeT>>*> queue; 89 queue.push(&children); 90 while (!queue.empty()) { 91 std::vector<std::unique_ptr<NodeT>>* v = queue.front(); 92 queue.pop(); 93 std::sort(v->begin(), v->end(), CallChainRoot::CompareNodeByPeriod); 94 for (auto& node : *v) { 95 if (!node->children.empty()) { 96 queue.push(&node->children); 97 } 98 } 99 } 100 } 101 102 private: FindMatchingNodeCallChainRoot103 NodeT* FindMatchingNode( 104 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( 115 NodeT* node, const std::vector<EntryT*>& chain, size_t chain_start, 116 std::function<bool(const EntryT*, const EntryT*)> is_same_sample) { 117 size_t i, j; 118 for (i = 0, j = chain_start; i < node->chain.size() && j < chain.size(); 119 ++i, ++j) { 120 if (!is_same_sample(node->chain[i], chain[j])) { 121 break; 122 } 123 } 124 return i; 125 } 126 SplitNodeCallChainRoot127 void SplitNode(NodeT* parent, size_t parent_length) { 128 std::unique_ptr<NodeT> child = AllocateNode( 129 parent->chain, parent_length, parent->period, parent->children_period); 130 child->children = std::move(parent->children); 131 parent->period = 0; 132 parent->children_period = child->period + child->children_period; 133 parent->chain.resize(parent_length); 134 parent->children.clear(); 135 parent->children.push_back(std::move(child)); 136 } 137 AllocateNodeCallChainRoot138 std::unique_ptr<NodeT> AllocateNode(const std::vector<EntryT*>& chain, 139 size_t chain_start, uint64_t period, 140 uint64_t children_period) { 141 std::unique_ptr<NodeT> node(new NodeT); 142 for (size_t i = chain_start; i < chain.size(); ++i) { 143 node->chain.push_back(chain[i]); 144 } 145 node->period = period; 146 node->children_period = children_period; 147 return node; 148 } 149 CompareNodeByPeriodCallChainRoot150 static bool CompareNodeByPeriod(const std::unique_ptr<NodeT>& n1, 151 const std::unique_ptr<NodeT>& n2) { 152 uint64_t period1 = n1->period + n1->children_period; 153 uint64_t period2 = n2->period + n2->children_period; 154 return period1 > period2; 155 } 156 }; 157 158 #endif // SIMPLE_PERF_CALLCHAIN_H_ 159