| /* |
| * Copyright (C) 2015 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #include "callchain.h" |
| |
| #include <string.h> |
| |
| #include <queue> |
| |
| #include <android-base/logging.h> |
| #include "sample_tree.h" |
| |
| static bool MatchSampleByName(const SampleEntry* sample1, const SampleEntry* sample2) { |
| return strcmp(sample1->symbol->Name(), sample2->symbol->Name()) == 0; |
| } |
| |
| static size_t GetMatchingLengthInNode(const CallChainNode* node, |
| const std::vector<SampleEntry*>& chain, size_t chain_start) { |
| size_t i, j; |
| for (i = 0, j = chain_start; i < node->chain.size() && j < chain.size(); ++i, ++j) { |
| if (!MatchSampleByName(node->chain[i], chain[j])) { |
| break; |
| } |
| } |
| return i; |
| } |
| |
| static CallChainNode* FindMatchingNode(const std::vector<std::unique_ptr<CallChainNode>>& nodes, |
| const SampleEntry* sample) { |
| for (auto& node : nodes) { |
| if (MatchSampleByName(node->chain.front(), sample)) { |
| return node.get(); |
| } |
| } |
| return nullptr; |
| } |
| |
| static std::unique_ptr<CallChainNode> AllocateNode(const std::vector<SampleEntry*>& chain, |
| size_t chain_start, uint64_t period, |
| uint64_t children_period) { |
| std::unique_ptr<CallChainNode> node(new CallChainNode); |
| for (size_t i = chain_start; i < chain.size(); ++i) { |
| node->chain.push_back(chain[i]); |
| } |
| node->period = period; |
| node->children_period = children_period; |
| return node; |
| } |
| |
| static void SplitNode(CallChainNode* parent, size_t parent_length) { |
| std::unique_ptr<CallChainNode> child = |
| AllocateNode(parent->chain, parent_length, parent->period, parent->children_period); |
| child->children = std::move(parent->children); |
| parent->period = 0; |
| parent->children_period = child->period + child->children_period; |
| parent->chain.resize(parent_length); |
| parent->children.clear(); |
| parent->children.push_back(std::move(child)); |
| } |
| |
| void CallChainRoot::AddCallChain(const std::vector<SampleEntry*>& callchain, uint64_t period) { |
| children_period += period; |
| CallChainNode* p = FindMatchingNode(children, callchain[0]); |
| if (p == nullptr) { |
| std::unique_ptr<CallChainNode> new_node = AllocateNode(callchain, 0, period, 0); |
| children.push_back(std::move(new_node)); |
| return; |
| } |
| size_t callchain_pos = 0; |
| while (true) { |
| size_t match_length = GetMatchingLengthInNode(p, callchain, callchain_pos); |
| CHECK_GT(match_length, 0u); |
| callchain_pos += match_length; |
| bool find_child = true; |
| if (match_length < p->chain.size()) { |
| SplitNode(p, match_length); |
| find_child = false; // No need to find matching node in p->children. |
| } |
| if (callchain_pos == callchain.size()) { |
| p->period += period; |
| return; |
| } |
| p->children_period += period; |
| if (find_child) { |
| CallChainNode* np = FindMatchingNode(p->children, callchain[callchain_pos]); |
| if (np != nullptr) { |
| p = np; |
| continue; |
| } |
| } |
| std::unique_ptr<CallChainNode> new_node = AllocateNode(callchain, callchain_pos, period, 0); |
| p->children.push_back(std::move(new_node)); |
| break; |
| } |
| } |
| |
| static bool CompareNodeByPeriod(const std::unique_ptr<CallChainNode>& n1, |
| const std::unique_ptr<CallChainNode>& n2) { |
| uint64_t period1 = n1->period + n1->children_period; |
| uint64_t period2 = n2->period + n2->children_period; |
| return period1 > period2; |
| } |
| |
| void CallChainRoot::SortByPeriod() { |
| std::queue<std::vector<std::unique_ptr<CallChainNode>>*> queue; |
| queue.push(&children); |
| while (!queue.empty()) { |
| std::vector<std::unique_ptr<CallChainNode>>* v = queue.front(); |
| queue.pop(); |
| std::sort(v->begin(), v->end(), CompareNodeByPeriod); |
| for (auto& node : *v) { |
| queue.push(&node->children); |
| } |
| } |
| } |