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 #include "callchain.h" 18 19 #include <string.h> 20 21 #include <queue> 22 23 #include <android-base/logging.h> 24 #include "sample_tree.h" 25 26 static bool MatchSampleByName(const SampleEntry* sample1, const SampleEntry* sample2) { 27 return strcmp(sample1->symbol->Name(), sample2->symbol->Name()) == 0; 28 } 29 30 static size_t GetMatchingLengthInNode(const CallChainNode* node, 31 const std::vector<SampleEntry*>& chain, size_t chain_start) { 32 size_t i, j; 33 for (i = 0, j = chain_start; i < node->chain.size() && j < chain.size(); ++i, ++j) { 34 if (!MatchSampleByName(node->chain[i], chain[j])) { 35 break; 36 } 37 } 38 return i; 39 } 40 41 static CallChainNode* FindMatchingNode(const std::vector<std::unique_ptr<CallChainNode>>& nodes, 42 const SampleEntry* sample) { 43 for (auto& node : nodes) { 44 if (MatchSampleByName(node->chain.front(), sample)) { 45 return node.get(); 46 } 47 } 48 return nullptr; 49 } 50 51 static std::unique_ptr<CallChainNode> AllocateNode(const std::vector<SampleEntry*>& chain, 52 size_t chain_start, uint64_t period, 53 uint64_t children_period) { 54 std::unique_ptr<CallChainNode> node(new CallChainNode); 55 for (size_t i = chain_start; i < chain.size(); ++i) { 56 node->chain.push_back(chain[i]); 57 } 58 node->period = period; 59 node->children_period = children_period; 60 return node; 61 } 62 63 static void SplitNode(CallChainNode* parent, size_t parent_length) { 64 std::unique_ptr<CallChainNode> child = 65 AllocateNode(parent->chain, parent_length, parent->period, parent->children_period); 66 child->children = std::move(parent->children); 67 parent->period = 0; 68 parent->children_period = child->period + child->children_period; 69 parent->chain.resize(parent_length); 70 parent->children.clear(); 71 parent->children.push_back(std::move(child)); 72 } 73 74 void CallChainRoot::AddCallChain(const std::vector<SampleEntry*>& callchain, uint64_t period) { 75 children_period += period; 76 CallChainNode* p = FindMatchingNode(children, callchain[0]); 77 if (p == nullptr) { 78 std::unique_ptr<CallChainNode> new_node = AllocateNode(callchain, 0, period, 0); 79 children.push_back(std::move(new_node)); 80 return; 81 } 82 size_t callchain_pos = 0; 83 while (true) { 84 size_t match_length = GetMatchingLengthInNode(p, callchain, callchain_pos); 85 CHECK_GT(match_length, 0u); 86 callchain_pos += match_length; 87 bool find_child = true; 88 if (match_length < p->chain.size()) { 89 SplitNode(p, match_length); 90 find_child = false; // No need to find matching node in p->children. 91 } 92 if (callchain_pos == callchain.size()) { 93 p->period += period; 94 return; 95 } 96 p->children_period += period; 97 if (find_child) { 98 CallChainNode* np = FindMatchingNode(p->children, callchain[callchain_pos]); 99 if (np != nullptr) { 100 p = np; 101 continue; 102 } 103 } 104 std::unique_ptr<CallChainNode> new_node = AllocateNode(callchain, callchain_pos, period, 0); 105 p->children.push_back(std::move(new_node)); 106 break; 107 } 108 } 109 110 static bool CompareNodeByPeriod(const std::unique_ptr<CallChainNode>& n1, 111 const std::unique_ptr<CallChainNode>& n2) { 112 uint64_t period1 = n1->period + n1->children_period; 113 uint64_t period2 = n2->period + n2->children_period; 114 return period1 > period2; 115 } 116 117 void CallChainRoot::SortByPeriod() { 118 std::queue<std::vector<std::unique_ptr<CallChainNode>>*> queue; 119 queue.push(&children); 120 while (!queue.empty()) { 121 std::vector<std::unique_ptr<CallChainNode>>* v = queue.front(); 122 queue.pop(); 123 std::sort(v->begin(), v->end(), CompareNodeByPeriod); 124 for (auto& node : *v) { 125 queue.push(&node->children); 126 } 127 } 128 } 129