12672dea3f1112b13678103023011c797ca283bacYabin Cui/* 22672dea3f1112b13678103023011c797ca283bacYabin Cui * Copyright (C) 2015 The Android Open Source Project 32672dea3f1112b13678103023011c797ca283bacYabin Cui * 42672dea3f1112b13678103023011c797ca283bacYabin Cui * Licensed under the Apache License, Version 2.0 (the "License"); 52672dea3f1112b13678103023011c797ca283bacYabin Cui * you may not use this file except in compliance with the License. 62672dea3f1112b13678103023011c797ca283bacYabin Cui * You may obtain a copy of the License at 72672dea3f1112b13678103023011c797ca283bacYabin Cui * 82672dea3f1112b13678103023011c797ca283bacYabin Cui * http://www.apache.org/licenses/LICENSE-2.0 92672dea3f1112b13678103023011c797ca283bacYabin Cui * 102672dea3f1112b13678103023011c797ca283bacYabin Cui * Unless required by applicable law or agreed to in writing, software 112672dea3f1112b13678103023011c797ca283bacYabin Cui * distributed under the License is distributed on an "AS IS" BASIS, 122672dea3f1112b13678103023011c797ca283bacYabin Cui * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 132672dea3f1112b13678103023011c797ca283bacYabin Cui * See the License for the specific language governing permissions and 142672dea3f1112b13678103023011c797ca283bacYabin Cui * limitations under the License. 152672dea3f1112b13678103023011c797ca283bacYabin Cui */ 162672dea3f1112b13678103023011c797ca283bacYabin Cui 172672dea3f1112b13678103023011c797ca283bacYabin Cui#ifndef SIMPLE_PERF_SAMPLE_TREE_H_ 182672dea3f1112b13678103023011c797ca283bacYabin Cui#define SIMPLE_PERF_SAMPLE_TREE_H_ 192672dea3f1112b13678103023011c797ca283bacYabin Cui 200c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui#include <unordered_map> 210c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui 22ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui#include "callchain.h" 23b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui#include "dwarf_unwind.h" 24b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui#include "perf_regs.h" 25b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui#include "record.h" 26b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui#include "SampleComparator.h" 27b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui#include "SampleDisplayer.h" 2860a0ea96c0fb9e807c899759256df5e20bd904bdYabin Cui#include "thread_tree.h" 2941d4ba9f6f2781155a0519a784606d5382cda88fYabin Cui 30b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// A SampleTree is a collection of samples. A profiling report is mainly about 31b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// constructing a SampleTree and display it. There are three steps involved: 32b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// build the tree, sort the tree, and display it. For example, if we want to 33b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// show how many cpu-cycles are spent in different functions, we should do as 34b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// follows: 35b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// 1. Build a SampleTree from SampleRecords with each sample containing 36b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// (cpu-cycles, function name). When building the tree, we should merge 37b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// samples containing the same function name. 38b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// 2. Sort the SampleTree by cpu-cycles in the sample. As we want to display the 39b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// samples in a decreasing order of cpu-cycles, we should sort it like this. 40b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// 3. Display the SampleTree, each sample prints its (cpu-cycles, function name) 41b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// pair. 42b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// 43b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// We represent the three steps with three template classes. 44b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// 1. A SampleTree is built by SampleTreeBuilder. The comparator passed in 45b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// SampleTreeBuilder's constructor decides the property of samples should be 46b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// merged together. 47b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// 2. After a SampleTree is built and got from SampleTreeBuilder, it should be 48b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// sorted by SampleTreeSorter. The sort result decides the order to show 49b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// samples. 50b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// 3. At last, the sorted SampleTree is passed to SampleTreeDisplayer, which 51b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui// displays each sample in the SampleTree. 52b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 53b64a86327afe2b77dab7d724d363386c674163b6Yabin Cuitemplate <typename EntryT, typename AccumulateInfoT> 54b64a86327afe2b77dab7d724d363386c674163b6Yabin Cuiclass SampleTreeBuilder { 55b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui public: 565674ed87431f2d9b05f4ec0c7f7c2e56e585c956Chih-Hung Hsieh explicit SampleTreeBuilder(SampleComparator<EntryT> comparator) 57b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui : sample_set_(comparator), 586965d42c43f12fd2dfcca3c490b51edc67822586Yabin Cui accumulate_callchain_(false), 599970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui sample_comparator_(comparator), 60b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui callchain_sample_set_(comparator), 61b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui use_branch_address_(false), 62b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui build_callchain_(false), 63b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui use_caller_as_callchain_root_(false), 64b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui strict_unwind_arch_check_(false) {} 65b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 66b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui virtual ~SampleTreeBuilder() {} 67ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 68b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui void SetBranchSampleOption(bool use_branch_address) { 69b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui use_branch_address_ = use_branch_address; 70ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui } 718a530e3bae0cc031d60e397c347e96f44487e919Yabin Cui 72b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui void SetCallChainSampleOptions(bool accumulate_callchain, 73b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui bool build_callchain, 74b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui bool use_caller_as_callchain_root, 75b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui bool strict_unwind_arch_check) { 76b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui accumulate_callchain_ = accumulate_callchain; 77b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui build_callchain_ = build_callchain; 78b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui use_caller_as_callchain_root_ = use_caller_as_callchain_root; 79b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui strict_unwind_arch_check_ = strict_unwind_arch_check; 80ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui } 81ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 82b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui void ProcessSampleRecord(const SampleRecord& r) { 83b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (use_branch_address_ && (r.sample_type & PERF_SAMPLE_BRANCH_STACK)) { 84190a848fb2d4f502372b2528c55ca1f520e90609Yabin Cui for (uint64_t i = 0; i < r.branch_stack_data.stack_nr; ++i) { 85190a848fb2d4f502372b2528c55ca1f520e90609Yabin Cui auto& item = r.branch_stack_data.stack[i]; 86b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (item.from != 0 && item.to != 0) { 87b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui CreateBranchSample(r, item); 88b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 89b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 90b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return; 91b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 92b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui bool in_kernel = r.InKernel(); 93b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui AccumulateInfoT acc_info; 94b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui EntryT* sample = CreateSample(r, in_kernel, &acc_info); 95b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (sample == nullptr) { 96b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return; 97b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 98b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (accumulate_callchain_) { 99b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::vector<uint64_t> ips; 100b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (r.sample_type & PERF_SAMPLE_CALLCHAIN) { 101190a848fb2d4f502372b2528c55ca1f520e90609Yabin Cui ips.insert(ips.end(), r.callchain_data.ips, 102190a848fb2d4f502372b2528c55ca1f520e90609Yabin Cui r.callchain_data.ips + r.callchain_data.ip_nr); 103b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 104b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui const ThreadEntry* thread = GetThreadOfSample(sample); 105b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui // Use stack_user_data.data.size() instead of stack_user_data.dyn_size, to 106b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui // make up for the missing kernel patch in N9. See b/22612370. 107b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (thread != nullptr && (r.sample_type & PERF_SAMPLE_REGS_USER) && 108b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui (r.regs_user_data.reg_mask != 0) && 109b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui (r.sample_type & PERF_SAMPLE_STACK_USER) && 110190a848fb2d4f502372b2528c55ca1f520e90609Yabin Cui (r.GetValidStackSize() > 0)) { 111417df291499b37f63fa9b930e081d80a25bf38ecYabin Cui RegSet regs = CreateRegSet(r.regs_user_data.abi, 112417df291499b37f63fa9b930e081d80a25bf38ecYabin Cui r.regs_user_data.reg_mask, 113417df291499b37f63fa9b930e081d80a25bf38ecYabin Cui r.regs_user_data.regs); 114cf31e9d83d3fff0c0970aa344366136e4d5126a7Yabin Cui std::vector<uint64_t> unwind_ips = 115417df291499b37f63fa9b930e081d80a25bf38ecYabin Cui UnwindCallChain(r.regs_user_data.abi, *thread, regs, 116417df291499b37f63fa9b930e081d80a25bf38ecYabin Cui r.stack_user_data.data, 117cf31e9d83d3fff0c0970aa344366136e4d5126a7Yabin Cui r.GetValidStackSize(), strict_unwind_arch_check_); 118b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (!unwind_ips.empty()) { 119b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui ips.push_back(PERF_CONTEXT_USER); 120b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui ips.insert(ips.end(), unwind_ips.begin(), unwind_ips.end()); 121b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 122b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 1232672dea3f1112b13678103023011c797ca283bacYabin Cui 124b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::vector<EntryT*> callchain; 125b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui callchain.push_back(sample); 1262672dea3f1112b13678103023011c797ca283bacYabin Cui 127b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui bool first_ip = true; 128b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui for (auto& ip : ips) { 129b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (ip >= PERF_CONTEXT_MAX) { 130b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui switch (ip) { 131b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui case PERF_CONTEXT_KERNEL: 132b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui in_kernel = true; 133b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui break; 134b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui case PERF_CONTEXT_USER: 135b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui in_kernel = false; 136b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui break; 137b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui default: 138b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui LOG(DEBUG) << "Unexpected perf_context in callchain: " << ip; 139b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 140b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } else { 141b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (first_ip) { 142b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui first_ip = false; 143b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui // Remove duplication with sampled ip. 144b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (ip == r.ip_data.ip) { 145b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui continue; 146b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 147b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 148b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui EntryT* callchain_sample = 149b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui CreateCallChainSample(sample, ip, in_kernel, callchain, acc_info); 150b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (callchain_sample == nullptr) { 151b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui break; 152b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 153b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui callchain.push_back(callchain_sample); 154b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 155b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 156b47de4af4d9a1ceffa74a148f6e89be4dbb62bcdYabin Cui 157b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (build_callchain_) { 158b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::set<EntryT*> added_set; 159b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (use_caller_as_callchain_root_) { 160b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::reverse(callchain.begin(), callchain.end()); 161b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 1620c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui EntryT* parent = nullptr; 163b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui while (callchain.size() >= 2) { 164b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui EntryT* sample = callchain[0]; 165b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui callchain.erase(callchain.begin()); 166b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui // Add only once for recursive calls on callchain. 167b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (added_set.find(sample) != added_set.end()) { 168b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui continue; 169b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 170b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui added_set.insert(sample); 171b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui InsertCallChainForSample(sample, callchain, acc_info); 1720c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui UpdateCallChainParentInfo(sample, parent); 1730c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui parent = sample; 174b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 175b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 176b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 1772672dea3f1112b13678103023011c797ca283bacYabin Cui } 1782672dea3f1112b13678103023011c797ca283bacYabin Cui 179b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::vector<EntryT*> GetSamples() const { 180b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::vector<EntryT*> result; 181b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui for (auto& entry : sample_set_) { 182b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui result.push_back(entry); 183b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 184b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return result; 1852672dea3f1112b13678103023011c797ca283bacYabin Cui } 1862672dea3f1112b13678103023011c797ca283bacYabin Cui 187b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui protected: 188b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui virtual EntryT* CreateSample(const SampleRecord& r, bool in_kernel, 189b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui AccumulateInfoT* acc_info) = 0; 190b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui virtual EntryT* CreateBranchSample(const SampleRecord& r, 191b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui const BranchStackItemType& item) = 0; 192b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui virtual EntryT* CreateCallChainSample(const EntryT* sample, uint64_t ip, 193b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui bool in_kernel, 194b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui const std::vector<EntryT*>& callchain, 195b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui const AccumulateInfoT& acc_info) = 0; 196b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui virtual const ThreadEntry* GetThreadOfSample(EntryT*) = 0; 1979970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui virtual uint64_t GetPeriodForCallChain(const AccumulateInfoT& acc_info) = 0; 198b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui virtual bool FilterSample(const EntryT*) { return true; } 1992672dea3f1112b13678103023011c797ca283bacYabin Cui 200b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui virtual void UpdateSummary(const EntryT*) {} 201b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 202b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui virtual void MergeSample(EntryT* sample1, EntryT* sample2) = 0; 203b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 204b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui EntryT* InsertSample(std::unique_ptr<EntryT> sample) { 205b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (sample == nullptr || !FilterSample(sample.get())) { 206b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return nullptr; 2072672dea3f1112b13678103023011c797ca283bacYabin Cui } 208b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui UpdateSummary(sample.get()); 209b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui EntryT* result; 210b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui auto it = sample_set_.find(sample.get()); 211b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (it == sample_set_.end()) { 212b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui result = sample.get(); 213b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui sample_set_.insert(sample.get()); 214b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui sample_storage_.push_back(std::move(sample)); 215b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } else { 216b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui result = *it; 217b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui MergeSample(*it, sample.get()); 2182672dea3f1112b13678103023011c797ca283bacYabin Cui } 219b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return result; 220b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 2212672dea3f1112b13678103023011c797ca283bacYabin Cui 222b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui EntryT* InsertCallChainSample(std::unique_ptr<EntryT> sample, 223b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui const std::vector<EntryT*>& callchain) { 224b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (sample == nullptr) { 225b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return nullptr; 226b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 227b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (!FilterSample(sample.get())) { 228b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui // Store in callchain_sample_set_ for use in other EntryT's callchain. 229b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui auto it = callchain_sample_set_.find(sample.get()); 230b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (it != callchain_sample_set_.end()) { 231b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return *it; 232b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 233b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui EntryT* result = sample.get(); 234b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui callchain_sample_set_.insert(sample.get()); 235b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui sample_storage_.push_back(std::move(sample)); 236b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return result; 237b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 238b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 239b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui auto it = sample_set_.find(sample.get()); 240b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (it != sample_set_.end()) { 241b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui EntryT* sample = *it; 242b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui // Process only once for recursive function call. 243b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (std::find(callchain.begin(), callchain.end(), sample) != 244b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui callchain.end()) { 245b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return sample; 246b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 247b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 248b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return InsertSample(std::move(sample)); 249b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 250b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 2519970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui void InsertCallChainForSample(EntryT* sample, 2529970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui const std::vector<EntryT*>& callchain, 2539970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui const AccumulateInfoT& acc_info) { 2549970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui uint64_t period = GetPeriodForCallChain(acc_info); 255cf31e9d83d3fff0c0970aa344366136e4d5126a7Yabin Cui sample->callchain.AddCallChain( 256cf31e9d83d3fff0c0970aa344366136e4d5126a7Yabin Cui callchain, period, [&](const EntryT* s1, const EntryT* s2) { 257cf31e9d83d3fff0c0970aa344366136e4d5126a7Yabin Cui return sample_comparator_.IsSameSample(s1, s2); 258cf31e9d83d3fff0c0970aa344366136e4d5126a7Yabin Cui }); 2599970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui } 2609970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui 2610c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui void AddCallChainDuplicateInfo() { 2620c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui if (build_callchain_) { 2630c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui for (EntryT* sample : sample_set_) { 2640c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui auto it = callchain_parent_map_.find(sample); 2650c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui if (it != callchain_parent_map_.end() && !it->second.has_multiple_parents) { 2660c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui sample->callchain.duplicated = true; 2670c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui } 2680c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui } 2690c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui } 2700c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui } 2710c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui 272b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::set<EntryT*, SampleComparator<EntryT>> sample_set_; 2736965d42c43f12fd2dfcca3c490b51edc67822586Yabin Cui bool accumulate_callchain_; 274b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 275b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui private: 2760c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui void UpdateCallChainParentInfo(EntryT* sample, EntryT* parent) { 2770c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui if (parent == nullptr) { 2780c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui return; 2790c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui } 2800c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui auto it = callchain_parent_map_.find(sample); 2810c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui if (it == callchain_parent_map_.end()) { 2820c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui CallChainParentInfo info; 2830c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui info.parent = parent; 2840c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui info.has_multiple_parents = false; 2850c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui callchain_parent_map_[sample] = info; 2860c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui } else if (it->second.parent != parent) { 2870c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui it->second.has_multiple_parents = true; 2880c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui } 2890c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui } 2900c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui 2919970a2344333f2c19d9126cfec4f833f50ff2f22Yabin Cui const SampleComparator<EntryT> sample_comparator_; 292b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui // If a CallChainSample is filtered out, it is stored in callchain_sample_set_ 293b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui // and only used in other EntryT's callchain. 294b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::set<EntryT*, SampleComparator<EntryT>> callchain_sample_set_; 295b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::vector<std::unique_ptr<EntryT>> sample_storage_; 296b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 2970c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui struct CallChainParentInfo { 2980c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui EntryT* parent; 2990c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui bool has_multiple_parents; 3000c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui }; 3010c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui std::unordered_map<EntryT*, CallChainParentInfo> callchain_parent_map_; 3020c093f3cc0dbced581c9d430e0ed8cd12def61ceYabin Cui 303b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui bool use_branch_address_; 304b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui bool build_callchain_; 305b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui bool use_caller_as_callchain_root_; 306b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui bool strict_unwind_arch_check_; 307b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui}; 308b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 309b64a86327afe2b77dab7d724d363386c674163b6Yabin Cuitemplate <typename EntryT> 310b64a86327afe2b77dab7d724d363386c674163b6Yabin Cuiclass SampleTreeSorter { 311b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui public: 3125674ed87431f2d9b05f4ec0c7f7c2e56e585c956Chih-Hung Hsieh explicit SampleTreeSorter(SampleComparator<EntryT> comparator) 313b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui : comparator_(comparator) {} 314b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 315b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui virtual ~SampleTreeSorter() {} 3162672dea3f1112b13678103023011c797ca283bacYabin Cui 317b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui void Sort(std::vector<EntryT*>& v, bool sort_callchain) { 318b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (sort_callchain) { 319b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui for (auto& sample : v) { 320b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui SortCallChain(sample); 3212672dea3f1112b13678103023011c797ca283bacYabin Cui } 3222672dea3f1112b13678103023011c797ca283bacYabin Cui } 323b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui if (!comparator_.empty()) { 324b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui std::sort(v.begin(), v.end(), [this](const EntryT* s1, const EntryT* s2) { 325b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui return comparator_(s1, s2); 326b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui }); 3272672dea3f1112b13678103023011c797ca283bacYabin Cui } 328b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 3292672dea3f1112b13678103023011c797ca283bacYabin Cui 330b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui protected: 331b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui void SortCallChain(EntryT* sample) { sample->callchain.SortByPeriod(); } 3322672dea3f1112b13678103023011c797ca283bacYabin Cui 333b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui private: 334b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui SampleComparator<EntryT> comparator_; 335b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui}; 33638e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui 337b64a86327afe2b77dab7d724d363386c674163b6Yabin Cuitemplate <typename EntryT, typename InfoT> 338b64a86327afe2b77dab7d724d363386c674163b6Yabin Cuiclass SampleTreeDisplayer { 339b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui public: 3405674ed87431f2d9b05f4ec0c7f7c2e56e585c956Chih-Hung Hsieh explicit SampleTreeDisplayer(SampleDisplayer<EntryT, InfoT> displayer) 341b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui : displayer_(displayer) {} 3422672dea3f1112b13678103023011c797ca283bacYabin Cui 343b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui virtual ~SampleTreeDisplayer() {} 34438e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui 345b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui void DisplaySamples(FILE* fp, const std::vector<EntryT*>& samples, 346b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui const InfoT* info) { 347b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui displayer_.SetInfo(info); 348b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui for (const auto& sample : samples) { 349b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui displayer_.AdjustWidth(sample); 350b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 351b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui displayer_.PrintNames(fp); 352b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui for (const auto& sample : samples) { 353b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui displayer_.PrintSample(fp, sample); 354b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 355b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui } 356b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui 357b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui private: 358b64a86327afe2b77dab7d724d363386c674163b6Yabin Cui SampleDisplayer<EntryT, InfoT> displayer_; 3592672dea3f1112b13678103023011c797ca283bacYabin Cui}; 3602672dea3f1112b13678103023011c797ca283bacYabin Cui 3612672dea3f1112b13678103023011c797ca283bacYabin Cui#endif // SIMPLE_PERF_SAMPLE_TREE_H_ 362