Home | History | Annotate | Download | only in simpleperf 
      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 }
    129