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 BranchFromEntryBranchFromEntry37 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 SampleEntrySampleEntry54 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: SampleTree(ThreadTree * thread_tree,compare_sample_func_t sample_compare_function)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 TotalSamples()103 uint64_t TotalSamples() const { 104 return total_samples_; 105 } 106 TotalPeriod()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 { operatorSampleComparator117 bool operator()(SampleEntry* sample1, SampleEntry* sample2) const { 118 return compare_function(*sample1, *sample2) < 0; 119 } SampleComparatorSampleComparator120 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 { operatorSortedSampleComparator127 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 } SortedSampleComparatorSortedSampleComparator135 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