sample_tree.h revision 22ec7fa2032610b6868e4fb8997bb28aee0dea84 
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 <vector>
26
27#include "dso.h"
28
29struct ProcessEntry {
30  int pid;
31  std::string comm;
32};
33
34struct MapEntry {
35  int pid;  // pid = -1 for kernel map entries.
36  uint64_t start_addr;
37  uint64_t len;
38  uint64_t pgoff;
39  uint64_t time;  // Map creation time.
40  DsoEntry* dso;
41};
42
43struct SampleEntry {
44  int tid;
45  uint64_t ip;
46  uint64_t time;
47  uint64_t period;
48  uint64_t sample_count;
49  const ProcessEntry* process;
50  const MapEntry* map;
51  const SymbolEntry* symbol;
52};
53
54typedef std::function<int(const SampleEntry&, const SampleEntry&)> compare_sample_func_t;
55
56class SampleTree {
57 public:
58  SampleTree(compare_sample_func_t sample_compare_function)
59      : sample_comparator_(sample_compare_function),
60        sample_tree_(sample_comparator_),
61        sorted_sample_comparator_(sample_compare_function),
62        sorted_sample_tree_(sorted_sample_comparator_),
63        total_samples_(0),
64        total_period_(0) {
65    unknown_dso_.path = "unknown";
66    unknown_symbol_ = {
67        .name = "unknown", .addr = 0, .len = ULLONG_MAX,
68    };
69  }
70
71  void AddProcess(int pid, const std::string& comm);
72  void AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
73                    const std::string& filename);
74  void AddUserMap(int pid, uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
75                  const std::string& filename);
76  void AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period, bool in_kernel);
77  void VisitAllSamples(std::function<void(const SampleEntry&)> callback);
78
79  uint64_t TotalSamples() const {
80    return total_samples_;
81  }
82
83  uint64_t TotalPeriod() const {
84    return total_period_;
85  }
86
87 private:
88  void RemoveOverlappedUserMap(const MapEntry* map);
89  const ProcessEntry* FindProcessEntryOrNew(int pid);
90  const MapEntry* FindMapEntryOrNew(int pid, uint64_t ip, bool in_kernel);
91  const MapEntry* FindUnknownMapEntryOrNew(int pid);
92  DsoEntry* FindKernelDsoOrNew(const std::string& filename);
93  DsoEntry* FindUserDsoOrNew(const std::string& filename);
94  const SymbolEntry* FindSymbolEntry(uint64_t ip, const MapEntry* map_entry);
95
96  struct MapComparator {
97    bool operator()(const MapEntry* map1, const MapEntry* map2);
98  };
99
100  struct SampleComparator {
101    bool operator()(const SampleEntry& sample1, const SampleEntry& sample2) {
102      return compare_function(sample1, sample2) < 0;
103    }
104    SampleComparator(compare_sample_func_t compare_function) : compare_function(compare_function) {
105    }
106
107    compare_sample_func_t compare_function;
108  };
109
110  struct SortedSampleComparator {
111    bool operator()(const SampleEntry& sample1, const SampleEntry& sample2) {
112      if (sample1.period != sample2.period) {
113        return sample1.period > sample2.period;
114      }
115      return compare_function(sample1, sample2) < 0;
116    }
117    SortedSampleComparator(compare_sample_func_t compare_function)
118        : compare_function(compare_function) {
119    }
120
121    compare_sample_func_t compare_function;
122  };
123
124  std::unordered_map<int, std::unique_ptr<ProcessEntry>> process_tree_;
125
126  std::set<MapEntry*, MapComparator> kernel_map_tree_;
127  std::set<MapEntry*, MapComparator> user_map_tree_;
128  std::unordered_map<int, MapEntry*> unknown_maps_;
129  std::vector<std::unique_ptr<MapEntry>> map_storage_;
130
131  std::unique_ptr<DsoEntry> kernel_dso_;
132  std::unordered_map<std::string, std::unique_ptr<DsoEntry>> module_dso_tree_;
133  std::unordered_map<std::string, std::unique_ptr<DsoEntry>> user_dso_tree_;
134  DsoEntry unknown_dso_;
135  SymbolEntry unknown_symbol_;
136
137  SampleComparator sample_comparator_;
138  std::set<SampleEntry, SampleComparator> sample_tree_;
139  SortedSampleComparator sorted_sample_comparator_;
140  std::set<SampleEntry, SortedSampleComparator> sorted_sample_tree_;
141
142  uint64_t total_samples_;
143  uint64_t total_period_;
144};
145
146#endif  // SIMPLE_PERF_SAMPLE_TREE_H_
147