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 // If duplicated = true, this call tree is part of another call tree. 42 // And we don't need to show it in brief callgraph report mode. 43 bool duplicated; 44 uint64_t children_period; 45 std::vector<std::unique_ptr<NodeT>> children; 46 47 CallChainRoot() : duplicated(false), children_period(0) {} 48 49 void AddCallChain( 50 const std::vector<EntryT*>& callchain, uint64_t period, 51 std::function<bool(const EntryT*, const EntryT*)> is_same_sample) { 52 children_period += period; 53 NodeT* p = FindMatchingNode(children, callchain[0], is_same_sample); 54 if (p == nullptr) { 55 std::unique_ptr<NodeT> new_node = AllocateNode(callchain, 0, period, 0); 56 children.push_back(std::move(new_node)); 57 return; 58 } 59 size_t callchain_pos = 0; 60 while (true) { 61 size_t match_length = 62 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], 77 is_same_sample); 78 if (np != nullptr) { 79 p = np; 80 continue; 81 } 82 } 83 std::unique_ptr<NodeT> new_node = 84 AllocateNode(callchain, callchain_pos, period, 0); 85 p->children.push_back(std::move(new_node)); 86 break; 87 } 88 } 89 90 void SortByPeriod() { 91 std::queue<std::vector<std::unique_ptr<NodeT>>*> queue; 92 queue.push(&children); 93 while (!queue.empty()) { 94 std::vector<std::unique_ptr<NodeT>>* v = queue.front(); 95 queue.pop(); 96 std::sort(v->begin(), v->end(), CallChainRoot::CompareNodeByPeriod); 97 for (auto& node : *v) { 98 if (!node->children.empty()) { 99 queue.push(&node->children); 100 } 101 } 102 } 103 } 104 105 private: 106 NodeT* FindMatchingNode( 107 const std::vector<std::unique_ptr<NodeT>>& nodes, const EntryT* sample, 108 std::function<bool(const EntryT*, const EntryT*)> is_same_sample) { 109 for (auto& node : nodes) { 110 if (is_same_sample(node->chain.front(), sample)) { 111 return node.get(); 112 } 113 } 114 return nullptr; 115 } 116 117 size_t GetMatchingLengthInNode( 118 NodeT* node, const std::vector<EntryT*>& chain, size_t chain_start, 119 std::function<bool(const EntryT*, const EntryT*)> is_same_sample) { 120 size_t i, j; 121 for (i = 0, j = chain_start; i < node->chain.size() && j < chain.size(); 122 ++i, ++j) { 123 if (!is_same_sample(node->chain[i], chain[j])) { 124 break; 125 } 126 } 127 return i; 128 } 129 130 void SplitNode(NodeT* parent, size_t parent_length) { 131 std::unique_ptr<NodeT> child = AllocateNode( 132 parent->chain, parent_length, parent->period, parent->children_period); 133 child->children = std::move(parent->children); 134 parent->period = 0; 135 parent->children_period = child->period + child->children_period; 136 parent->chain.resize(parent_length); 137 parent->children.clear(); 138 parent->children.push_back(std::move(child)); 139 } 140 141 std::unique_ptr<NodeT> AllocateNode(const std::vector<EntryT*>& chain, 142 size_t chain_start, uint64_t period, 143 uint64_t children_period) { 144 std::unique_ptr<NodeT> node(new NodeT); 145 for (size_t i = chain_start; i < chain.size(); ++i) { 146 node->chain.push_back(chain[i]); 147 } 148 node->period = period; 149 node->children_period = children_period; 150 return node; 151 } 152 153 static bool CompareNodeByPeriod(const std::unique_ptr<NodeT>& n1, 154 const std::unique_ptr<NodeT>& n2) { 155 uint64_t period1 = n1->period + n1->children_period; 156 uint64_t period2 = n2->period + n2->children_period; 157 return period1 > period2; 158 } 159 }; 160 161 #endif // SIMPLE_PERF_CALLCHAIN_H_ 162
