simpleperf/callchain.cpp

   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 }