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#include "sample_tree.h"
18
19#include <android-base/logging.h>
20
21#include "environment.h"
22
23void SampleTree::SetFilters(const std::unordered_set<int>& pid_filter,
24                            const std::unordered_set<int>& tid_filter,
25                            const std::unordered_set<std::string>& comm_filter,
26                            const std::unordered_set<std::string>& dso_filter) {
27  pid_filter_ = pid_filter;
28  tid_filter_ = tid_filter;
29  comm_filter_ = comm_filter;
30  dso_filter_ = dso_filter;
31}
32
33SampleEntry* SampleTree::AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period,
34                                   bool in_kernel) {
35  const ThreadEntry* thread = thread_tree_->FindThreadOrNew(pid, tid);
36  const MapEntry* map = thread_tree_->FindMap(thread, ip, in_kernel);
37  const Symbol* symbol = thread_tree_->FindSymbol(map, ip);
38
39  SampleEntry value(ip, time, period, 0, 1, thread, map, symbol);
40
41  if (IsFilteredOut(value)) {
42    return nullptr;
43  }
44  return InsertSample(value);
45}
46
47void SampleTree::AddBranchSample(int pid, int tid, uint64_t from_ip, uint64_t to_ip,
48                                 uint64_t branch_flags, uint64_t time, uint64_t period) {
49  const ThreadEntry* thread = thread_tree_->FindThreadOrNew(pid, tid);
50  const MapEntry* from_map = thread_tree_->FindMap(thread, from_ip, false);
51  if (from_map == thread_tree_->UnknownMap()) {
52    from_map = thread_tree_->FindMap(thread, from_ip, true);
53  }
54  const Symbol* from_symbol = thread_tree_->FindSymbol(from_map, from_ip);
55  const MapEntry* to_map = thread_tree_->FindMap(thread, to_ip, false);
56  if (to_map == thread_tree_->UnknownMap()) {
57    to_map = thread_tree_->FindMap(thread, to_ip, true);
58  }
59  const Symbol* to_symbol = thread_tree_->FindSymbol(to_map, to_ip);
60
61  SampleEntry value(to_ip, time, period, 0, 1, thread, to_map, to_symbol);
62  value.branch_from.ip = from_ip;
63  value.branch_from.map = from_map;
64  value.branch_from.symbol = from_symbol;
65  value.branch_from.flags = branch_flags;
66
67  if (IsFilteredOut(value)) {
68    return;
69  }
70  InsertSample(value);
71}
72
73SampleEntry* SampleTree::AddCallChainSample(int pid, int tid, uint64_t ip, uint64_t time,
74                                            uint64_t period, bool in_kernel,
75                                            const std::vector<SampleEntry*>& callchain) {
76  const ThreadEntry* thread = thread_tree_->FindThreadOrNew(pid, tid);
77  const MapEntry* map = thread_tree_->FindMap(thread, ip, in_kernel);
78  const Symbol* symbol = thread_tree_->FindSymbol(map, ip);
79
80  SampleEntry value(ip, time, 0, period, 0, thread, map, symbol);
81
82  if (IsFilteredOut(value)) {
83    // Store in callchain_sample_tree_ for use in other SampleEntry's callchain.
84    auto it = callchain_sample_tree_.find(&value);
85    if (it != callchain_sample_tree_.end()) {
86      return *it;
87    }
88    SampleEntry* sample = AllocateSample(value);
89    callchain_sample_tree_.insert(sample);
90    return sample;
91  }
92
93  auto it = sample_tree_.find(&value);
94  if (it != sample_tree_.end()) {
95    SampleEntry* sample = *it;
96    // Process only once for recursive function call.
97    if (std::find(callchain.begin(), callchain.end(), sample) != callchain.end()) {
98      return sample;
99    }
100  }
101  return InsertSample(value);
102}
103
104bool SampleTree::IsFilteredOut(const SampleEntry& value) {
105  if (!pid_filter_.empty() && pid_filter_.find(value.thread->pid) == pid_filter_.end()) {
106    return true;
107  }
108  if (!tid_filter_.empty() && tid_filter_.find(value.thread->tid) == tid_filter_.end()) {
109    return true;
110  }
111  if (!comm_filter_.empty() && comm_filter_.find(value.thread_comm) == comm_filter_.end()) {
112    return true;
113  }
114  if (!dso_filter_.empty() && dso_filter_.find(value.map->dso->Path()) == dso_filter_.end()) {
115    return true;
116  }
117  return false;
118}
119
120SampleEntry* SampleTree::InsertSample(SampleEntry& value) {
121  SampleEntry* result;
122  auto it = sample_tree_.find(&value);
123  if (it == sample_tree_.end()) {
124    result = AllocateSample(value);
125    auto pair = sample_tree_.insert(result);
126    CHECK(pair.second);
127  } else {
128    result = *it;
129    result->period += value.period;
130    result->accumulated_period += value.accumulated_period;
131    result->sample_count += value.sample_count;
132  }
133  total_samples_ += value.sample_count;
134  total_period_ += value.period;
135  return result;
136}
137
138SampleEntry* SampleTree::AllocateSample(SampleEntry& value) {
139  SampleEntry* sample = new SampleEntry(std::move(value));
140  sample_storage_.push_back(std::unique_ptr<SampleEntry>(sample));
141  return sample;
142}
143
144void SampleTree::InsertCallChainForSample(SampleEntry* sample,
145                                          const std::vector<SampleEntry*>& callchain,
146                                          uint64_t period) {
147  sample->callchain.AddCallChain(callchain, period);
148}
149
150void SampleTree::VisitAllSamples(std::function<void(const SampleEntry&)> callback) {
151  if (sorted_sample_tree_.size() != sample_tree_.size()) {
152    sorted_sample_tree_.clear();
153    for (auto& sample : sample_tree_) {
154      sample->callchain.SortByPeriod();
155      sorted_sample_tree_.insert(sample);
156    }
157  }
158  for (auto& sample : sorted_sample_tree_) {
159    callback(*sample);
160  }
161}
162