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