simpleperf/callchain.h

   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 #ifndef SIMPLE_PERF_CALLCHAIN_H_
  18 #define SIMPLE_PERF_CALLCHAIN_H_
  19
  20 #include <string.h>
  21
  22 #include <algorithm>
  23 #include <functional>
  24 #include <memory>
  25 #include <queue>
  26 #include <vector>
  27
  28 #include <android-base/logging.h>
  29
  30 template <typename EntryT>
  31 struct CallChainNode {
  32   uint64_t period;
  33   uint64_t children_period;
  34   std::vector<EntryT*> chain;
  35   std::vector<std::unique_ptr<CallChainNode>> children;
  36 };
  37
  38 template <typename EntryT>
  39 struct CallChainRoot {
  40   typedef CallChainNode<EntryT> NodeT;
  41   // If duplicated = true, this call tree is part of another call tree.
  42   // And we don't need to show it in brief callgraph report mode.
  43   bool duplicated;
  44   uint64_t children_period;
  45   std::vector<std::unique_ptr<NodeT>> children;
  46
  47   CallChainRoot() : duplicated(false), children_period(0) {}
  48
  49   void AddCallChain(
  50       const std::vector<EntryT*>& callchain, uint64_t period,
  51       std::function<bool(const EntryT*, const EntryT*)> is_same_sample) {
  52     children_period += period;
  53     NodeT* p = FindMatchingNode(children, callchain[0], is_same_sample);
  54     if (p == nullptr) {
  55       std::unique_ptr<NodeT> new_node = AllocateNode(callchain, 0, period, 0);
  56       children.push_back(std::move(new_node));
  57       return;
  58     }
  59     size_t callchain_pos = 0;
  60     while (true) {
  61       size_t match_length =
  62           GetMatchingLengthInNode(p, callchain, callchain_pos, is_same_sample);
  63       CHECK_GT(match_length, 0u);
  64       callchain_pos += match_length;
  65       bool find_child = true;
  66       if (match_length < p->chain.size()) {
  67         SplitNode(p, match_length);
  68         find_child = false;  // No need to find matching node in p->children.
  69       }
  70       if (callchain_pos == callchain.size()) {
  71         p->period += period;
  72         return;
  73       }
  74       p->children_period += period;
  75       if (find_child) {
  76         NodeT* np = FindMatchingNode(p->children, callchain[callchain_pos],
  77                                      is_same_sample);
  78         if (np != nullptr) {
  79           p = np;
  80           continue;
  81         }
  82       }
  83       std::unique_ptr<NodeT> new_node =
  84           AllocateNode(callchain, callchain_pos, period, 0);
  85       p->children.push_back(std::move(new_node));
  86       break;
  87     }
  88   }
  89
  90   void SortByPeriod() {
  91     std::queue<std::vector<std::unique_ptr<NodeT>>*> queue;
  92     queue.push(&children);
  93     while (!queue.empty()) {
  94       std::vector<std::unique_ptr<NodeT>>* v = queue.front();
  95       queue.pop();
  96       std::sort(v->begin(), v->end(), CallChainRoot::CompareNodeByPeriod);
  97       for (auto& node : *v) {
  98         if (!node->children.empty()) {
  99           queue.push(&node->children);
 100         }
 101       }
 102     }
 103   }
 104
 105  private:
 106   NodeT* FindMatchingNode(
 107       const std::vector<std::unique_ptr<NodeT>>& nodes, const EntryT* sample,
 108       std::function<bool(const EntryT*, const EntryT*)> is_same_sample) {
 109     for (auto& node : nodes) {
 110       if (is_same_sample(node->chain.front(), sample)) {
 111         return node.get();
 112       }
 113     }
 114     return nullptr;
 115   }
 116
 117   size_t GetMatchingLengthInNode(
 118       NodeT* node, const std::vector<EntryT*>& chain, size_t chain_start,
 119       std::function<bool(const EntryT*, const EntryT*)> is_same_sample) {
 120     size_t i, j;
 121     for (i = 0, j = chain_start; i < node->chain.size() && j < chain.size();
 122          ++i, ++j) {
 123       if (!is_same_sample(node->chain[i], chain[j])) {
 124         break;
 125       }
 126     }
 127     return i;
 128   }
 129
 130   void SplitNode(NodeT* parent, size_t parent_length) {
 131     std::unique_ptr<NodeT> child = AllocateNode(
 132         parent->chain, parent_length, parent->period, parent->children_period);
 133     child->children = std::move(parent->children);
 134     parent->period = 0;
 135     parent->children_period = child->period + child->children_period;
 136     parent->chain.resize(parent_length);
 137     parent->children.clear();
 138     parent->children.push_back(std::move(child));
 139   }
 140
 141   std::unique_ptr<NodeT> AllocateNode(const std::vector<EntryT*>& chain,
 142                                       size_t chain_start, uint64_t period,
 143                                       uint64_t children_period) {
 144     std::unique_ptr<NodeT> node(new NodeT);
 145     for (size_t i = chain_start; i < chain.size(); ++i) {
 146       node->chain.push_back(chain[i]);
 147     }
 148     node->period = period;
 149     node->children_period = children_period;
 150     return node;
 151   }
 152
 153   static bool CompareNodeByPeriod(const std::unique_ptr<NodeT>& n1,
 154                                   const std::unique_ptr<NodeT>& n2) {
 155     uint64_t period1 = n1->period + n1->children_period;
 156     uint64_t period2 = n2->period + n2->children_period;
 157     return period1 > period2;
 158   }
 159 };
 160
 161 #endif  // SIMPLE_PERF_CALLCHAIN_H_