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
MatchSampleByName(const SampleEntry * sample1,const SampleEntry * sample2)26 static bool MatchSampleByName(const SampleEntry* sample1, const SampleEntry* sample2) {
27 return strcmp(sample1->symbol->Name(), sample2->symbol->Name()) == 0;
28 }
29
GetMatchingLengthInNode(const CallChainNode * node,const std::vector<SampleEntry * > & chain,size_t chain_start)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
FindMatchingNode(const std::vector<std::unique_ptr<CallChainNode>> & nodes,const SampleEntry * sample)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
AllocateNode(const std::vector<SampleEntry * > & chain,size_t chain_start,uint64_t period,uint64_t children_period)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
SplitNode(CallChainNode * parent,size_t parent_length)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
AddCallChain(const std::vector<SampleEntry * > & callchain,uint64_t period)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
CompareNodeByPeriod(const std::unique_ptr<CallChainNode> & n1,const std::unique_ptr<CallChainNode> & n2)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
SortByPeriod()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