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 20ec12ed9010128483993a87d68edc02d3a89d56cfYabin Cui#include <limits.h> 212672dea3f1112b13678103023011c797ca283bacYabin Cui#include <functional> 222672dea3f1112b13678103023011c797ca283bacYabin Cui#include <set> 232672dea3f1112b13678103023011c797ca283bacYabin Cui#include <string> 242672dea3f1112b13678103023011c797ca283bacYabin Cui#include <unordered_map> 2538e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui#include <unordered_set> 26b47de4af4d9a1ceffa74a148f6e89be4dbb62bcdYabin Cui#include <vector> 272672dea3f1112b13678103023011c797ca283bacYabin Cui 28ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui#include "callchain.h" 2960a0ea96c0fb9e807c899759256df5e20bd904bdYabin Cui#include "thread_tree.h" 3041d4ba9f6f2781155a0519a784606d5382cda88fYabin Cui 318a530e3bae0cc031d60e397c347e96f44487e919Yabin Cuistruct BranchFromEntry { 328a530e3bae0cc031d60e397c347e96f44487e919Yabin Cui uint64_t ip; 338a530e3bae0cc031d60e397c347e96f44487e919Yabin Cui const MapEntry* map; 34c84856093e8bf4350d30fc521dc0f1c800c5270bYabin Cui const Symbol* symbol; 358a530e3bae0cc031d60e397c347e96f44487e919Yabin Cui uint64_t flags; 36ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 37ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui BranchFromEntry() : ip(0), map(nullptr), symbol(nullptr), flags(0) { 38ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui } 398a530e3bae0cc031d60e397c347e96f44487e919Yabin Cui}; 408a530e3bae0cc031d60e397c347e96f44487e919Yabin Cui 4141d4ba9f6f2781155a0519a784606d5382cda88fYabin Cuistruct SampleEntry { 422672dea3f1112b13678103023011c797ca283bacYabin Cui uint64_t ip; 432672dea3f1112b13678103023011c797ca283bacYabin Cui uint64_t time; 442672dea3f1112b13678103023011c797ca283bacYabin Cui uint64_t period; 4536c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui uint64_t accumulated_period; // Accumulated when appearing in other samples' callchain. 462672dea3f1112b13678103023011c797ca283bacYabin Cui uint64_t sample_count; 4741d4ba9f6f2781155a0519a784606d5382cda88fYabin Cui const ThreadEntry* thread; 4841d4ba9f6f2781155a0519a784606d5382cda88fYabin Cui const char* thread_comm; // It refers to the thread comm when the sample happens. 49ec12ed9010128483993a87d68edc02d3a89d56cfYabin Cui const MapEntry* map; 50c84856093e8bf4350d30fc521dc0f1c800c5270bYabin Cui const Symbol* symbol; 518a530e3bae0cc031d60e397c347e96f44487e919Yabin Cui BranchFromEntry branch_from; 52ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui CallChainRoot callchain; // A callchain tree representing all callchains in the sample records. 53ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 54ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui SampleEntry(uint64_t ip, uint64_t time, uint64_t period, uint64_t accumulated_period, 55ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui uint64_t sample_count, const ThreadEntry* thread, const MapEntry* map, 56c84856093e8bf4350d30fc521dc0f1c800c5270bYabin Cui const Symbol* symbol) 57ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui : ip(ip), 58ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui time(time), 59ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui period(period), 60ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui accumulated_period(accumulated_period), 61ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui sample_count(sample_count), 62ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui thread(thread), 63ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui thread_comm(thread->comm), 64ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui map(map), 65ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui symbol(symbol) { 66ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui } 67ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui 68ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui // The data member 'callchain' can only move, not copy. 69ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui SampleEntry(SampleEntry&&) = default; 70ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui SampleEntry(SampleEntry&) = delete; 712672dea3f1112b13678103023011c797ca283bacYabin Cui}; 722672dea3f1112b13678103023011c797ca283bacYabin Cui 732672dea3f1112b13678103023011c797ca283bacYabin Cuitypedef std::function<int(const SampleEntry&, const SampleEntry&)> compare_sample_func_t; 742672dea3f1112b13678103023011c797ca283bacYabin Cui 752672dea3f1112b13678103023011c797ca283bacYabin Cuiclass SampleTree { 762672dea3f1112b13678103023011c797ca283bacYabin Cui public: 7760a0ea96c0fb9e807c899759256df5e20bd904bdYabin Cui SampleTree(ThreadTree* thread_tree, compare_sample_func_t sample_compare_function) 7860a0ea96c0fb9e807c899759256df5e20bd904bdYabin Cui : thread_tree_(thread_tree), 79ba50c4bba1c3ea7e98a475a3d2ae2e6c24ee81f2Yabin Cui sample_comparator_(sample_compare_function), 802672dea3f1112b13678103023011c797ca283bacYabin Cui sample_tree_(sample_comparator_), 8138e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui callchain_sample_tree_(sample_comparator_), 822672dea3f1112b13678103023011c797ca283bacYabin Cui sorted_sample_comparator_(sample_compare_function), 832672dea3f1112b13678103023011c797ca283bacYabin Cui sorted_sample_tree_(sorted_sample_comparator_), 842672dea3f1112b13678103023011c797ca283bacYabin Cui total_samples_(0), 852672dea3f1112b13678103023011c797ca283bacYabin Cui total_period_(0) { 86b47de4af4d9a1ceffa74a148f6e89be4dbb62bcdYabin Cui } 87b47de4af4d9a1ceffa74a148f6e89be4dbb62bcdYabin Cui 8838e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui void SetFilters(const std::unordered_set<int>& pid_filter, 8938e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui const std::unordered_set<int>& tid_filter, 9038e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui const std::unordered_set<std::string>& comm_filter, 9138e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui const std::unordered_set<std::string>& dso_filter); 9238e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui 9336c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui SampleEntry* AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period, 9436c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui bool in_kernel); 958a530e3bae0cc031d60e397c347e96f44487e919Yabin Cui void AddBranchSample(int pid, int tid, uint64_t from_ip, uint64_t to_ip, uint64_t branch_flags, 968a530e3bae0cc031d60e397c347e96f44487e919Yabin Cui uint64_t time, uint64_t period); 9736c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui SampleEntry* AddCallChainSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period, 9836c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui bool in_kernel, const std::vector<SampleEntry*>& callchain); 99ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui void InsertCallChainForSample(SampleEntry* sample, const std::vector<SampleEntry*>& callchain, 100ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui uint64_t period); 1012672dea3f1112b13678103023011c797ca283bacYabin Cui void VisitAllSamples(std::function<void(const SampleEntry&)> callback); 1022672dea3f1112b13678103023011c797ca283bacYabin Cui 1032672dea3f1112b13678103023011c797ca283bacYabin Cui uint64_t TotalSamples() const { 1042672dea3f1112b13678103023011c797ca283bacYabin Cui return total_samples_; 1052672dea3f1112b13678103023011c797ca283bacYabin Cui } 1062672dea3f1112b13678103023011c797ca283bacYabin Cui 1072672dea3f1112b13678103023011c797ca283bacYabin Cui uint64_t TotalPeriod() const { 1082672dea3f1112b13678103023011c797ca283bacYabin Cui return total_period_; 1092672dea3f1112b13678103023011c797ca283bacYabin Cui } 1102672dea3f1112b13678103023011c797ca283bacYabin Cui 1112672dea3f1112b13678103023011c797ca283bacYabin Cui private: 11238e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui bool IsFilteredOut(const SampleEntry& value); 11336c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui SampleEntry* InsertSample(SampleEntry& value); 114ecb9a302b52b034610efb85bd73cb473e7c4ddb2Yabin Cui SampleEntry* AllocateSample(SampleEntry& value); 1152672dea3f1112b13678103023011c797ca283bacYabin Cui 1162672dea3f1112b13678103023011c797ca283bacYabin Cui struct SampleComparator { 11736c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui bool operator()(SampleEntry* sample1, SampleEntry* sample2) const { 11836c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui return compare_function(*sample1, *sample2) < 0; 1192672dea3f1112b13678103023011c797ca283bacYabin Cui } 1202672dea3f1112b13678103023011c797ca283bacYabin Cui SampleComparator(compare_sample_func_t compare_function) : compare_function(compare_function) { 1212672dea3f1112b13678103023011c797ca283bacYabin Cui } 1222672dea3f1112b13678103023011c797ca283bacYabin Cui 1232672dea3f1112b13678103023011c797ca283bacYabin Cui compare_sample_func_t compare_function; 1242672dea3f1112b13678103023011c797ca283bacYabin Cui }; 1252672dea3f1112b13678103023011c797ca283bacYabin Cui 1262672dea3f1112b13678103023011c797ca283bacYabin Cui struct SortedSampleComparator { 12736c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui bool operator()(SampleEntry* sample1, SampleEntry* sample2) const { 12836c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui uint64_t period1 = sample1->period + sample1->accumulated_period; 12936c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui uint64_t period2 = sample2->period + sample2->accumulated_period; 13036c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui if (period1 != period2) { 13136c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui return period1 > period2; 1322672dea3f1112b13678103023011c797ca283bacYabin Cui } 13336c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui return compare_function(*sample1, *sample2) < 0; 1342672dea3f1112b13678103023011c797ca283bacYabin Cui } 1352672dea3f1112b13678103023011c797ca283bacYabin Cui SortedSampleComparator(compare_sample_func_t compare_function) 1362672dea3f1112b13678103023011c797ca283bacYabin Cui : compare_function(compare_function) { 1372672dea3f1112b13678103023011c797ca283bacYabin Cui } 1382672dea3f1112b13678103023011c797ca283bacYabin Cui 1392672dea3f1112b13678103023011c797ca283bacYabin Cui compare_sample_func_t compare_function; 1402672dea3f1112b13678103023011c797ca283bacYabin Cui }; 1412672dea3f1112b13678103023011c797ca283bacYabin Cui 14260a0ea96c0fb9e807c899759256df5e20bd904bdYabin Cui ThreadTree* thread_tree_; 1432672dea3f1112b13678103023011c797ca283bacYabin Cui SampleComparator sample_comparator_; 14436c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui std::set<SampleEntry*, SampleComparator> sample_tree_; 14538e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui // If a CallChainSample is filtered out, it is stored in callchain_sample_tree_ and only used 14638e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui // in other SampleEntry's callchain. 14738e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui std::set<SampleEntry*, SampleComparator> callchain_sample_tree_; 14838e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui 1492672dea3f1112b13678103023011c797ca283bacYabin Cui SortedSampleComparator sorted_sample_comparator_; 15036c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui std::set<SampleEntry*, SortedSampleComparator> sorted_sample_tree_; 15136c662b538bd89e591b1bfcbce59fc0de3602bf6Yabin Cui std::vector<std::unique_ptr<SampleEntry>> sample_storage_; 1522672dea3f1112b13678103023011c797ca283bacYabin Cui 15338e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui std::unordered_set<int> pid_filter_; 15438e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui std::unordered_set<int> tid_filter_; 15538e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui std::unordered_set<std::string> comm_filter_; 15638e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui std::unordered_set<std::string> dso_filter_; 15738e573ee1958959253ba8f3af7567adb4cbeea55Yabin Cui 1582672dea3f1112b13678103023011c797ca283bacYabin Cui uint64_t total_samples_; 1592672dea3f1112b13678103023011c797ca283bacYabin Cui uint64_t total_period_; 1602672dea3f1112b13678103023011c797ca283bacYabin Cui}; 1612672dea3f1112b13678103023011c797ca283bacYabin Cui 1622672dea3f1112b13678103023011c797ca283bacYabin Cui#endif // SIMPLE_PERF_SAMPLE_TREE_H_ 163