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 <unordered_map>
  21
  22 #include "callchain.h"
  23 #include "dwarf_unwind.h"
  24 #include "perf_regs.h"
  25 #include "record.h"
  26 #include "SampleComparator.h"
  27 #include "SampleDisplayer.h"
  28 #include "thread_tree.h"
  29
  30 // A SampleTree is a collection of samples. A profiling report is mainly about
  31 // constructing a SampleTree and display it. There are three steps involved:
  32 // build the tree, sort the tree, and display it. For example, if we want to
  33 // show how many cpu-cycles are spent in different functions, we should do as
  34 // follows:
  35 // 1. Build a SampleTree from SampleRecords with each sample containing
  36 //    (cpu-cycles, function name). When building the tree, we should merge
  37 //    samples containing the same function name.
  38 // 2. Sort the SampleTree by cpu-cycles in the sample. As we want to display the
  39 //    samples in a decreasing order of cpu-cycles, we should sort it like this.
  40 // 3. Display the SampleTree, each sample prints its (cpu-cycles, function name)
  41 //    pair.
  42 //
  43 // We represent the three steps with three template classes.
  44 // 1. A SampleTree is built by SampleTreeBuilder. The comparator passed in
  45 //    SampleTreeBuilder's constructor decides the property of samples should be
  46 //    merged together.
  47 // 2. After a SampleTree is built and got from SampleTreeBuilder, it should be
  48 //    sorted by SampleTreeSorter. The sort result decides the order to show
  49 //    samples.
  50 // 3. At last, the sorted SampleTree is passed to SampleTreeDisplayer, which
  51 //    displays each sample in the SampleTree.
  52
  53 template <typename EntryT, typename AccumulateInfoT>
  54 class SampleTreeBuilder {
  55  public:
  56   explicit SampleTreeBuilder(SampleComparator<EntryT> comparator)
  57       : sample_set_(comparator),
  58         accumulate_callchain_(false),
  59         sample_comparator_(comparator),
  60         callchain_sample_set_(comparator),
  61         use_branch_address_(false),
  62         build_callchain_(false),
  63         use_caller_as_callchain_root_(false),
  64         strict_unwind_arch_check_(false) {}
  65
  66   virtual ~SampleTreeBuilder() {}
  67
  68   void SetBranchSampleOption(bool use_branch_address) {
  69     use_branch_address_ = use_branch_address;
  70   }
  71
  72   void SetCallChainSampleOptions(bool accumulate_callchain,
  73                                  bool build_callchain,
  74                                  bool use_caller_as_callchain_root,
  75                                  bool strict_unwind_arch_check) {
  76     accumulate_callchain_ = accumulate_callchain;
  77     build_callchain_ = build_callchain;
  78     use_caller_as_callchain_root_ = use_caller_as_callchain_root;
  79     strict_unwind_arch_check_ = strict_unwind_arch_check;
  80   }
  81
  82   void ProcessSampleRecord(const SampleRecord& r) {
  83     if (use_branch_address_ && (r.sample_type & PERF_SAMPLE_BRANCH_STACK)) {
  84       for (uint64_t i = 0; i < r.branch_stack_data.stack_nr; ++i) {
  85         auto& item = r.branch_stack_data.stack[i];
  86         if (item.from != 0 && item.to != 0) {
  87           CreateBranchSample(r, item);
  88         }
  89       }
  90       return;
  91     }
  92     bool in_kernel = r.InKernel();
  93     AccumulateInfoT acc_info;
  94     EntryT* sample = CreateSample(r, in_kernel, &acc_info);
  95     if (sample == nullptr) {
  96       return;
  97     }
  98     if (accumulate_callchain_) {
  99       std::vector<uint64_t> ips;
 100       if (r.sample_type & PERF_SAMPLE_CALLCHAIN) {
 101         ips.insert(ips.end(), r.callchain_data.ips,
 102                    r.callchain_data.ips + r.callchain_data.ip_nr);
 103       }
 104       const ThreadEntry* thread = GetThreadOfSample(sample);
 105       // Use stack_user_data.data.size() instead of stack_user_data.dyn_size, to
 106       // make up for the missing kernel patch in N9. See b/22612370.
 107       if (thread != nullptr && (r.sample_type & PERF_SAMPLE_REGS_USER) &&
 108           (r.regs_user_data.reg_mask != 0) &&
 109           (r.sample_type & PERF_SAMPLE_STACK_USER) &&
 110           (r.GetValidStackSize() > 0)) {
 111         RegSet regs = CreateRegSet(r.regs_user_data.abi,
 112                                    r.regs_user_data.reg_mask,
 113                                    r.regs_user_data.regs);
 114         std::vector<uint64_t> unwind_ips =
 115             UnwindCallChain(r.regs_user_data.abi, *thread, regs,
 116                             r.stack_user_data.data,
 117                             r.GetValidStackSize(), strict_unwind_arch_check_);
 118         if (!unwind_ips.empty()) {
 119           ips.push_back(PERF_CONTEXT_USER);
 120           ips.insert(ips.end(), unwind_ips.begin(), unwind_ips.end());
 121         }
 122       }
 123
 124       std::vector<EntryT*> callchain;
 125       callchain.push_back(sample);
 126
 127       bool first_ip = true;
 128       for (auto& ip : ips) {
 129         if (ip >= PERF_CONTEXT_MAX) {
 130           switch (ip) {
 131             case PERF_CONTEXT_KERNEL:
 132               in_kernel = true;
 133               break;
 134             case PERF_CONTEXT_USER:
 135               in_kernel = false;
 136               break;
 137             default:
 138               LOG(DEBUG) << "Unexpected perf_context in callchain: " << ip;
 139           }
 140         } else {
 141           if (first_ip) {
 142             first_ip = false;
 143             // Remove duplication with sampled ip.
 144             if (ip == r.ip_data.ip) {
 145               continue;
 146             }
 147           }
 148           EntryT* callchain_sample =
 149               CreateCallChainSample(sample, ip, in_kernel, callchain, acc_info);
 150           if (callchain_sample == nullptr) {
 151             break;
 152           }
 153           callchain.push_back(callchain_sample);
 154         }
 155       }
 156
 157       if (build_callchain_) {
 158         std::set<EntryT*> added_set;
 159         if (use_caller_as_callchain_root_) {
 160           std::reverse(callchain.begin(), callchain.end());
 161         }
 162         EntryT* parent = nullptr;
 163         while (callchain.size() >= 2) {
 164           EntryT* sample = callchain[0];
 165           callchain.erase(callchain.begin());
 166           // Add only once for recursive calls on callchain.
 167           if (added_set.find(sample) != added_set.end()) {
 168             continue;
 169           }
 170           added_set.insert(sample);
 171           InsertCallChainForSample(sample, callchain, acc_info);
 172           UpdateCallChainParentInfo(sample, parent);
 173           parent = sample;
 174         }
 175       }
 176     }
 177   }
 178
 179   std::vector<EntryT*> GetSamples() const {
 180     std::vector<EntryT*> result;
 181     for (auto& entry : sample_set_) {
 182       result.push_back(entry);
 183     }
 184     return result;
 185   }
 186
 187  protected:
 188   virtual EntryT* CreateSample(const SampleRecord& r, bool in_kernel,
 189                                AccumulateInfoT* acc_info) = 0;
 190   virtual EntryT* CreateBranchSample(const SampleRecord& r,
 191                                      const BranchStackItemType& item) = 0;
 192   virtual EntryT* CreateCallChainSample(const EntryT* sample, uint64_t ip,
 193                                         bool in_kernel,
 194                                         const std::vector<EntryT*>& callchain,
 195                                         const AccumulateInfoT& acc_info) = 0;
 196   virtual const ThreadEntry* GetThreadOfSample(EntryT*) = 0;
 197   virtual uint64_t GetPeriodForCallChain(const AccumulateInfoT& acc_info) = 0;
 198   virtual bool FilterSample(const EntryT*) { return true; }
 199
 200   virtual void UpdateSummary(const EntryT*) {}
 201
 202   virtual void MergeSample(EntryT* sample1, EntryT* sample2) = 0;
 203
 204   EntryT* InsertSample(std::unique_ptr<EntryT> sample) {
 205     if (sample == nullptr || !FilterSample(sample.get())) {
 206       return nullptr;
 207     }
 208     UpdateSummary(sample.get());
 209     EntryT* result;
 210     auto it = sample_set_.find(sample.get());
 211     if (it == sample_set_.end()) {
 212       result = sample.get();
 213       sample_set_.insert(sample.get());
 214       sample_storage_.push_back(std::move(sample));
 215     } else {
 216       result = *it;
 217       MergeSample(*it, sample.get());
 218     }
 219     return result;
 220   }
 221
 222   EntryT* InsertCallChainSample(std::unique_ptr<EntryT> sample,
 223                                 const std::vector<EntryT*>& callchain) {
 224     if (sample == nullptr) {
 225       return nullptr;
 226     }
 227     if (!FilterSample(sample.get())) {
 228       // Store in callchain_sample_set_ for use in other EntryT's callchain.
 229       auto it = callchain_sample_set_.find(sample.get());
 230       if (it != callchain_sample_set_.end()) {
 231         return *it;
 232       }
 233       EntryT* result = sample.get();
 234       callchain_sample_set_.insert(sample.get());
 235       sample_storage_.push_back(std::move(sample));
 236       return result;
 237     }
 238
 239     auto it = sample_set_.find(sample.get());
 240     if (it != sample_set_.end()) {
 241       EntryT* sample = *it;
 242       // Process only once for recursive function call.
 243       if (std::find(callchain.begin(), callchain.end(), sample) !=
 244           callchain.end()) {
 245         return sample;
 246       }
 247     }
 248     return InsertSample(std::move(sample));
 249   }
 250
 251   void InsertCallChainForSample(EntryT* sample,
 252                                 const std::vector<EntryT*>& callchain,
 253                                 const AccumulateInfoT& acc_info) {
 254     uint64_t period = GetPeriodForCallChain(acc_info);
 255     sample->callchain.AddCallChain(
 256         callchain, period, [&](const EntryT* s1, const EntryT* s2) {
 257           return sample_comparator_.IsSameSample(s1, s2);
 258         });
 259   }
 260
 261   void AddCallChainDuplicateInfo() {
 262     if (build_callchain_) {
 263       for (EntryT* sample : sample_set_) {
 264         auto it = callchain_parent_map_.find(sample);
 265         if (it != callchain_parent_map_.end() && !it->second.has_multiple_parents) {
 266           sample->callchain.duplicated = true;
 267         }
 268       }
 269     }
 270   }
 271
 272   std::set<EntryT*, SampleComparator<EntryT>> sample_set_;
 273   bool accumulate_callchain_;
 274
 275  private:
 276   void UpdateCallChainParentInfo(EntryT* sample, EntryT* parent) {
 277     if (parent == nullptr) {
 278       return;
 279     }
 280     auto it = callchain_parent_map_.find(sample);
 281     if (it == callchain_parent_map_.end()) {
 282       CallChainParentInfo info;
 283       info.parent = parent;
 284       info.has_multiple_parents = false;
 285       callchain_parent_map_[sample] = info;
 286     } else if (it->second.parent != parent) {
 287       it->second.has_multiple_parents = true;
 288     }
 289   }
 290
 291   const SampleComparator<EntryT> sample_comparator_;
 292   // If a CallChainSample is filtered out, it is stored in callchain_sample_set_
 293   // and only used in other EntryT's callchain.
 294   std::set<EntryT*, SampleComparator<EntryT>> callchain_sample_set_;
 295   std::vector<std::unique_ptr<EntryT>> sample_storage_;
 296
 297   struct CallChainParentInfo {
 298     EntryT* parent;
 299     bool has_multiple_parents;
 300   };
 301   std::unordered_map<EntryT*, CallChainParentInfo> callchain_parent_map_;
 302
 303   bool use_branch_address_;
 304   bool build_callchain_;
 305   bool use_caller_as_callchain_root_;
 306   bool strict_unwind_arch_check_;
 307 };
 308
 309 template <typename EntryT>
 310 class SampleTreeSorter {
 311  public:
 312   explicit SampleTreeSorter(SampleComparator<EntryT> comparator)
 313       : comparator_(comparator) {}
 314
 315   virtual ~SampleTreeSorter() {}
 316
 317   void Sort(std::vector<EntryT*>& v, bool sort_callchain) {
 318     if (sort_callchain) {
 319       for (auto& sample : v) {
 320         SortCallChain(sample);
 321       }
 322     }
 323     if (!comparator_.empty()) {
 324       std::sort(v.begin(), v.end(), [this](const EntryT* s1, const EntryT* s2) {
 325         return comparator_(s1, s2);
 326       });
 327     }
 328   }
 329
 330  protected:
 331   void SortCallChain(EntryT* sample) { sample->callchain.SortByPeriod(); }
 332
 333  private:
 334   SampleComparator<EntryT> comparator_;
 335 };
 336
 337 template <typename EntryT, typename InfoT>
 338 class SampleTreeDisplayer {
 339  public:
 340   explicit SampleTreeDisplayer(SampleDisplayer<EntryT, InfoT> displayer)
 341       : displayer_(displayer) {}
 342
 343   virtual ~SampleTreeDisplayer() {}
 344
 345   void DisplaySamples(FILE* fp, const std::vector<EntryT*>& samples,
 346                       const InfoT* info) {
 347     displayer_.SetInfo(info);
 348     for (const auto& sample : samples) {
 349       displayer_.AdjustWidth(sample);
 350     }
 351     displayer_.PrintNames(fp);
 352     for (const auto& sample : samples) {
 353       displayer_.PrintSample(fp, sample);
 354     }
 355   }
 356
 357  private:
 358   SampleDisplayer<EntryT, InfoT> displayer_;
 359 };
 360
 361 #endif  // SIMPLE_PERF_SAMPLE_TREE_H_