sample_tree.h revision 38e573ee1958959253ba8f3af7567adb4cbeea55 
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
31struct BranchFromEntry {
32  uint64_t ip;
33  const MapEntry* map;
34  const SymbolEntry* symbol;
35  uint64_t flags;
36
37  BranchFromEntry() : ip(0), map(nullptr), symbol(nullptr), flags(0) {
38  }
39};
40
41struct 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 SymbolEntry* 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 SymbolEntry* 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
73typedef std::function<int(const SampleEntry&, const SampleEntry&)> compare_sample_func_t;
74
75class 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_
163