simpleperf/sample_tree.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_SAMPLE_TREE_H_
  18 #define SIMPLE_PERF_SAMPLE_TREE_H_
  19
  20 #include <limits.h>
  21 #include <functional>
  22 #include <set>
  23 #include <string>
  24 #include <unordered_map>
  25 #include <unordered_set>
  26 #include <vector>
  27
  28 #include "callchain.h"
  29 #include "thread_tree.h"
  30
  31 struct BranchFromEntry {
  32   uint64_t ip;
  33   const MapEntry* map;
  34   const Symbol* symbol;
  35   uint64_t flags;
  36
  37   BranchFromEntry() : ip(0), map(nullptr), symbol(nullptr), flags(0) {
  38   }
  39 };
  40
  41 struct SampleEntry {
  42   uint64_t ip;
  43   uint64_t time;
  44   uint64_t period;
  45   uint64_t accumulated_period;  // Accumulated when appearing in other samples' callchain.
  46   uint64_t sample_count;
  47   const ThreadEntry* thread;
  48   const char* thread_comm;  // It refers to the thread comm when the sample happens.
  49   const MapEntry* map;
  50   const Symbol* symbol;
  51   BranchFromEntry branch_from;
  52   CallChainRoot callchain;  // A callchain tree representing all callchains in the sample records.
  53
  54   SampleEntry(uint64_t ip, uint64_t time, uint64_t period, uint64_t accumulated_period,
  55               uint64_t sample_count, const ThreadEntry* thread, const MapEntry* map,
  56               const Symbol* symbol)
  57       : ip(ip),
  58         time(time),
  59         period(period),
  60         accumulated_period(accumulated_period),
  61         sample_count(sample_count),
  62         thread(thread),
  63         thread_comm(thread->comm),
  64         map(map),
  65         symbol(symbol) {
  66   }
  67
  68   // The data member 'callchain' can only move, not copy.
  69   SampleEntry(SampleEntry&&) = default;
  70   SampleEntry(SampleEntry&) = delete;
  71 };
  72
  73 typedef std::function<int(const SampleEntry&, const SampleEntry&)> compare_sample_func_t;
  74
  75 class SampleTree {
  76  public:
  77   SampleTree(ThreadTree* thread_tree, compare_sample_func_t sample_compare_function)
  78       : thread_tree_(thread_tree),
  79         sample_comparator_(sample_compare_function),
  80         sample_tree_(sample_comparator_),
  81         callchain_sample_tree_(sample_comparator_),
  82         sorted_sample_comparator_(sample_compare_function),
  83         sorted_sample_tree_(sorted_sample_comparator_),
  84         total_samples_(0),
  85         total_period_(0) {
  86   }
  87
  88   void SetFilters(const std::unordered_set<int>& pid_filter,
  89                   const std::unordered_set<int>& tid_filter,
  90                   const std::unordered_set<std::string>& comm_filter,
  91                   const std::unordered_set<std::string>& dso_filter);
  92
  93   SampleEntry* AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period,
  94                          bool in_kernel);
  95   void AddBranchSample(int pid, int tid, uint64_t from_ip, uint64_t to_ip, uint64_t branch_flags,
  96                        uint64_t time, uint64_t period);
  97   SampleEntry* AddCallChainSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period,
  98                                   bool in_kernel, const std::vector<SampleEntry*>& callchain);
  99   void InsertCallChainForSample(SampleEntry* sample, const std::vector<SampleEntry*>& callchain,
 100                                 uint64_t period);
 101   void VisitAllSamples(std::function<void(const SampleEntry&)> callback);
 102
 103   uint64_t TotalSamples() const {
 104     return total_samples_;
 105   }
 106
 107   uint64_t TotalPeriod() const {
 108     return total_period_;
 109   }
 110
 111  private:
 112   bool IsFilteredOut(const SampleEntry& value);
 113   SampleEntry* InsertSample(SampleEntry& value);
 114   SampleEntry* AllocateSample(SampleEntry& value);
 115
 116   struct SampleComparator {
 117     bool operator()(SampleEntry* sample1, SampleEntry* sample2) const {
 118       return compare_function(*sample1, *sample2) < 0;
 119     }
 120     SampleComparator(compare_sample_func_t compare_function) : compare_function(compare_function) {
 121     }
 122
 123     compare_sample_func_t compare_function;
 124   };
 125
 126   struct SortedSampleComparator {
 127     bool operator()(SampleEntry* sample1, SampleEntry* sample2) const {
 128       uint64_t period1 = sample1->period + sample1->accumulated_period;
 129       uint64_t period2 = sample2->period + sample2->accumulated_period;
 130       if (period1 != period2) {
 131         return period1 > period2;
 132       }
 133       return compare_function(*sample1, *sample2) < 0;
 134     }
 135     SortedSampleComparator(compare_sample_func_t compare_function)
 136         : compare_function(compare_function) {
 137     }
 138
 139     compare_sample_func_t compare_function;
 140   };
 141
 142   ThreadTree* thread_tree_;
 143   SampleComparator sample_comparator_;
 144   std::set<SampleEntry*, SampleComparator> sample_tree_;
 145   // If a CallChainSample is filtered out, it is stored in callchain_sample_tree_ and only used
 146   // in other SampleEntry's callchain.
 147   std::set<SampleEntry*, SampleComparator> callchain_sample_tree_;
 148
 149   SortedSampleComparator sorted_sample_comparator_;
 150   std::set<SampleEntry*, SortedSampleComparator> sorted_sample_tree_;
 151   std::vector<std::unique_ptr<SampleEntry>> sample_storage_;
 152
 153   std::unordered_set<int> pid_filter_;
 154   std::unordered_set<int> tid_filter_;
 155   std::unordered_set<std::string> comm_filter_;
 156   std::unordered_set<std::string> dso_filter_;
 157
 158   uint64_t total_samples_;
 159   uint64_t total_period_;
 160 };
 161
 162 #endif  // SIMPLE_PERF_SAMPLE_TREE_H_