1ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui/* 2ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * Copyright (C) 2015 The Android Open Source Project 3ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * 4ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * Licensed under the Apache License, Version 2.0 (the "License"); 5ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * you may not use this file except in compliance with the License. 6ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * You may obtain a copy of the License at 7ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * 8ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * http://www.apache.org/licenses/LICENSE-2.0 9ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * 10ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * Unless required by applicable law or agreed to in writing, software 11ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * distributed under the License is distributed on an "AS IS" BASIS, 12ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * See the License for the specific language governing permissions and 14ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui * limitations under the License. 15ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui */ 16ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 17ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui#ifndef SIMPLE_PERF_CALLCHAIN_H_ 18ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui#define SIMPLE_PERF_CALLCHAIN_H_ 19ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 20b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui#include <string.h> 21b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 22b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui#include <algorithm> 239970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui#include <functional> 24ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui#include <memory> 25b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui#include <queue> 26ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui#include <vector> 27ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 28b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui#include <android-base/logging.h> 29ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 30b64a86327afe2b77dab7d724d363386c674163b6Yabin Cuitemplate <typename EntryT> 31ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cuistruct CallChainNode { 32ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui uint64_t period; 33ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui uint64_t children_period; 34b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::vector<EntryT*> chain; 35ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui std::vector<std::unique_ptr<CallChainNode>> children; 36ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui}; 37ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 38b64a86327afe2b77dab7d724d363386c674163b6Yabin Cuitemplate <typename EntryT> 39ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cuistruct CallChainRoot { 40b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui typedef CallChainNode<EntryT> NodeT; 410c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui // If duplicated = true, this call tree is part of another call tree. 420c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui // And we don't need to show it in brief callgraph report mode. 430c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui bool duplicated; 44ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui uint64_t children_period; 45b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::vector<std::unique_ptr<NodeT>> children; 46b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 470c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui CallChainRoot() : duplicated(false), children_period(0) {} 48b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 499970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui void AddCallChain( 509970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui const std::vector<EntryT*>& callchain, uint64_t period, 519970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui std::function<bool(const EntryT*, const EntryT*)> is_same_sample) { 52b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui children_period += period; 539970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui NodeT* p = FindMatchingNode(children, callchain[0], is_same_sample); 54b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (p == nullptr) { 55b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::unique_ptr<NodeT> new_node = AllocateNode(callchain, 0, period, 0); 56b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui children.push_back(std::move(new_node)); 57b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return; 58b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 59b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui size_t callchain_pos = 0; 60b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui while (true) { 61b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui size_t match_length = 629970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui GetMatchingLengthInNode(p, callchain, callchain_pos, is_same_sample); 63b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui CHECK_GT(match_length, 0u); 64b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui callchain_pos += match_length; 65b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui bool find_child = true; 66b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (match_length < p->chain.size()) { 67b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui SplitNode(p, match_length); 68b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui find_child = false; // No need to find matching node in p->children. 69b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 70b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (callchain_pos == callchain.size()) { 71b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui p->period += period; 72b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return; 73b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 74b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui p->children_period += period; 75b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (find_child) { 769970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui NodeT* np = FindMatchingNode(p->children, callchain[callchain_pos], 779970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui is_same_sample); 78b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (np != nullptr) { 79b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui p = np; 80b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui continue; 81b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 82b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 83b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::unique_ptr<NodeT> new_node = 84b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui AllocateNode(callchain, callchain_pos, period, 0); 85b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui p->children.push_back(std::move(new_node)); 86b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui break; 87b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 88b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 89b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 90b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui void SortByPeriod() { 91b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::queue<std::vector<std::unique_ptr<NodeT>>*> queue; 92b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui queue.push(&children); 93b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui while (!queue.empty()) { 94b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::vector<std::unique_ptr<NodeT>>* v = queue.front(); 95b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui queue.pop(); 96b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::sort(v->begin(), v->end(), CallChainRoot::CompareNodeByPeriod); 97b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui for (auto& node : *v) { 98b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (!node->children.empty()) { 99b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui queue.push(&node->children); 100b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 101b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 102b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 103b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 104b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 105b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui private: 1069970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui NodeT* FindMatchingNode( 1079970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui const std::vector<std::unique_ptr<NodeT>>& nodes, const EntryT* sample, 1089970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui std::function<bool(const EntryT*, const EntryT*)> is_same_sample) { 109b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui for (auto& node : nodes) { 1109970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui if (is_same_sample(node->chain.front(), sample)) { 111b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return node.get(); 112b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 113b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 114b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return nullptr; 115b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 116b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 1179970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui size_t GetMatchingLengthInNode( 1189970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui NodeT* node, const std::vector<EntryT*>& chain, size_t chain_start, 1199970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui std::function<bool(const EntryT*, const EntryT*)> is_same_sample) { 120b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui size_t i, j; 121b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui for (i = 0, j = chain_start; i < node->chain.size() && j < chain.size(); 122b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui ++i, ++j) { 1239970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui if (!is_same_sample(node->chain[i], chain[j])) { 124b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui break; 125b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 126b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 127b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return i; 128b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 129b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 130b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui void SplitNode(NodeT* parent, size_t parent_length) { 131b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::unique_ptr<NodeT> child = AllocateNode( 132b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui parent->chain, parent_length, parent->period, parent->children_period); 133b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui child->children = std::move(parent->children); 134b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui parent->period = 0; 135b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui parent->children_period = child->period + child->children_period; 136b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui parent->chain.resize(parent_length); 137b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui parent->children.clear(); 138b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui parent->children.push_back(std::move(child)); 139b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 140ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 141b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::unique_ptr<NodeT> AllocateNode(const std::vector<EntryT*>& chain, 142b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui size_t chain_start, uint64_t period, 143b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui uint64_t children_period) { 144b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::unique_ptr<NodeT> node(new NodeT); 145b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui for (size_t i = chain_start; i < chain.size(); ++i) { 146b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui node->chain.push_back(chain[i]); 147b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 148b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui node->period = period; 149b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui node->children_period = children_period; 150b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return node; 151ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui } 152ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 153b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui static bool CompareNodeByPeriod(const std::unique_ptr<NodeT>& n1, 154b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui const std::unique_ptr<NodeT>& n2) { 155b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui uint64_t period1 = n1->period + n1->children_period; 156b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui uint64_t period2 = n2->period + n2->children_period; 157b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return period1 > period2; 158b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 159ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui}; 160ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 161ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui#endif // SIMPLE_PERF_CALLCHAIN_H_ 162