1 /*
2 * Copyright (C) 2020 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 "src/trace_processor/dynamic/experimental_flamegraph_generator.h"
18
19 #include "perfetto/ext/base/string_utils.h"
20
21 #include "src/trace_processor/importers/proto/heap_graph_tracker.h"
22 #include "src/trace_processor/importers/proto/heap_profile_tracker.h"
23 #include "src/trace_processor/types/trace_processor_context.h"
24
25 namespace perfetto {
26 namespace trace_processor {
27
28 namespace {
29
GetFlamegraphInputValues(const std::vector<Constraint> & cs)30 ExperimentalFlamegraphGenerator::InputValues GetFlamegraphInputValues(
31 const std::vector<Constraint>& cs) {
32 using T = tables::ExperimentalFlamegraphNodesTable;
33
34 auto ts_fn = [](const Constraint& c) {
35 return c.col_idx == static_cast<uint32_t>(T::ColumnIndex::ts) &&
36 c.op == FilterOp::kEq;
37 };
38 auto upid_fn = [](const Constraint& c) {
39 return c.col_idx == static_cast<uint32_t>(T::ColumnIndex::upid) &&
40 c.op == FilterOp::kEq;
41 };
42 auto profile_type_fn = [](const Constraint& c) {
43 return c.col_idx == static_cast<uint32_t>(T::ColumnIndex::profile_type) &&
44 c.op == FilterOp::kEq;
45 };
46 auto focus_str_fn = [](const Constraint& c) {
47 return c.col_idx == static_cast<uint32_t>(T::ColumnIndex::focus_str) &&
48 c.op == FilterOp::kEq;
49 };
50
51 auto ts_it = std::find_if(cs.begin(), cs.end(), ts_fn);
52 auto upid_it = std::find_if(cs.begin(), cs.end(), upid_fn);
53 auto profile_type_it = std::find_if(cs.begin(), cs.end(), profile_type_fn);
54 auto focus_str_it = std::find_if(cs.begin(), cs.end(), focus_str_fn);
55
56 // We should always have valid iterators here because BestIndex should only
57 // allow the constraint set to be chosen when we have an equality constraint
58 // on both ts and upid.
59 PERFETTO_CHECK(ts_it != cs.end());
60 PERFETTO_CHECK(upid_it != cs.end());
61 PERFETTO_CHECK(profile_type_it != cs.end());
62
63 int64_t ts = ts_it->value.AsLong();
64 UniquePid upid = static_cast<UniquePid>(upid_it->value.AsLong());
65 std::string profile_type = profile_type_it->value.AsString();
66 std::string focus_str =
67 focus_str_it != cs.end() ? focus_str_it->value.AsString() : "";
68 return ExperimentalFlamegraphGenerator::InputValues{ts, upid, profile_type,
69 focus_str};
70 }
71
72 class Matcher {
73 public:
Matcher(const std::string & str)74 explicit Matcher(const std::string& str) : focus_str_(base::ToLower(str)) {}
75 Matcher(const Matcher&) = delete;
76 Matcher& operator=(const Matcher&) = delete;
77
matches(const std::string & s) const78 bool matches(const std::string& s) const {
79 // TODO(149833691): change to regex.
80 // We cannot use regex.h (does not exist in windows) or std regex (throws
81 // exceptions).
82 return base::Contains(base::ToLower(s), focus_str_);
83 }
84
85 private:
86 const std::string focus_str_;
87 };
88
89 enum class FocusedState {
90 kNotFocused,
91 kFocusedPropagating,
92 kFocusedNotPropagating,
93 };
94
95 using tables::ExperimentalFlamegraphNodesTable;
ComputeFocusedState(const ExperimentalFlamegraphNodesTable & table,const Matcher & focus_matcher)96 std::vector<FocusedState> ComputeFocusedState(
97 const ExperimentalFlamegraphNodesTable& table,
98 const Matcher& focus_matcher) {
99 // Each row corresponds to a node in the flame chart tree with its parent
100 // ptr. Root trees (no parents) will have a null parent ptr.
101 std::vector<FocusedState> focused(table.row_count());
102
103 for (uint32_t i = 0; i < table.row_count(); ++i) {
104 auto parent_id = table.parent_id()[i];
105 // Constraint: all descendants MUST come after their parents.
106 PERFETTO_DCHECK(!parent_id.has_value() || *parent_id < table.id()[i]);
107
108 if (focus_matcher.matches(table.name().GetString(i).ToStdString())) {
109 // Mark as focused
110 focused[i] = FocusedState::kFocusedPropagating;
111 auto current = parent_id;
112 // Mark all parent nodes as focused
113 while (current.has_value()) {
114 auto current_idx = *table.id().IndexOf(*current);
115 if (focused[current_idx] != FocusedState::kNotFocused) {
116 // We have already visited these nodes, skip
117 break;
118 }
119 focused[current_idx] = FocusedState::kFocusedNotPropagating;
120 current = table.parent_id()[current_idx];
121 }
122 } else if (parent_id.has_value() &&
123 focused[*table.id().IndexOf(*parent_id)] ==
124 FocusedState::kFocusedPropagating) {
125 // Focus cascades downwards.
126 focused[i] = FocusedState::kFocusedPropagating;
127 } else {
128 focused[i] = FocusedState::kNotFocused;
129 }
130 }
131 return focused;
132 }
133
134 struct CumulativeCounts {
135 int64_t size;
136 int64_t count;
137 int64_t alloc_size;
138 int64_t alloc_count;
139 };
FocusTable(TraceStorage * storage,std::unique_ptr<ExperimentalFlamegraphNodesTable> in,const std::string & focus_str)140 std::unique_ptr<tables::ExperimentalFlamegraphNodesTable> FocusTable(
141 TraceStorage* storage,
142 std::unique_ptr<ExperimentalFlamegraphNodesTable> in,
143 const std::string& focus_str) {
144 if (in->row_count() == 0 || focus_str.empty()) {
145 return in;
146 }
147 std::vector<FocusedState> focused_state =
148 ComputeFocusedState(*in, Matcher(focus_str));
149 std::unique_ptr<ExperimentalFlamegraphNodesTable> tbl(
150 new tables::ExperimentalFlamegraphNodesTable(
151 storage->mutable_string_pool(), nullptr));
152
153 // Recompute cumulative counts
154 std::vector<CumulativeCounts> node_to_cumulatives(in->row_count());
155 for (int64_t idx = in->row_count() - 1; idx >= 0; --idx) {
156 auto i = static_cast<uint32_t>(idx);
157 if (focused_state[i] == FocusedState::kNotFocused) {
158 continue;
159 }
160 auto& cumulatives = node_to_cumulatives[i];
161 cumulatives.size += in->size()[i];
162 cumulatives.count += in->count()[i];
163 cumulatives.alloc_size += in->alloc_size()[i];
164 cumulatives.alloc_count += in->alloc_count()[i];
165
166 auto parent_id = in->parent_id()[i];
167 if (parent_id.has_value()) {
168 auto& parent_cumulatives =
169 node_to_cumulatives[*in->id().IndexOf(*parent_id)];
170 parent_cumulatives.size += cumulatives.size;
171 parent_cumulatives.count += cumulatives.count;
172 parent_cumulatives.alloc_size += cumulatives.alloc_size;
173 parent_cumulatives.alloc_count += cumulatives.alloc_count;
174 }
175 }
176
177 // Mapping between the old rows ('node') to the new identifiers.
178 std::vector<ExperimentalFlamegraphNodesTable::Id> node_to_id(in->row_count());
179 for (uint32_t i = 0; i < in->row_count(); ++i) {
180 if (focused_state[i] == FocusedState::kNotFocused) {
181 continue;
182 }
183
184 tables::ExperimentalFlamegraphNodesTable::Row alloc_row{};
185 // We must reparent the rows as every insertion will get its own
186 // identifier.
187 auto original_parent_id = in->parent_id()[i];
188 if (original_parent_id.has_value()) {
189 auto original_idx = *in->id().IndexOf(*original_parent_id);
190 alloc_row.parent_id = node_to_id[original_idx];
191 }
192
193 alloc_row.ts = in->ts()[i];
194 alloc_row.upid = in->upid()[i];
195 alloc_row.profile_type = in->profile_type()[i];
196 alloc_row.depth = in->depth()[i];
197 alloc_row.name = in->name()[i];
198 alloc_row.map_name = in->map_name()[i];
199 alloc_row.count = in->count()[i];
200 alloc_row.size = in->size()[i];
201 alloc_row.alloc_count = in->alloc_count()[i];
202 alloc_row.alloc_size = in->alloc_size()[i];
203
204 const auto& cumulative = node_to_cumulatives[i];
205 alloc_row.cumulative_count = cumulative.count;
206 alloc_row.cumulative_size = cumulative.size;
207 alloc_row.cumulative_alloc_count = cumulative.alloc_count;
208 alloc_row.cumulative_alloc_size = cumulative.alloc_size;
209 node_to_id[i] = tbl->Insert(alloc_row).id;
210 }
211 return tbl;
212 }
213 } // namespace
214
ExperimentalFlamegraphGenerator(TraceProcessorContext * context)215 ExperimentalFlamegraphGenerator::ExperimentalFlamegraphGenerator(
216 TraceProcessorContext* context)
217 : context_(context) {}
218
219 ExperimentalFlamegraphGenerator::~ExperimentalFlamegraphGenerator() = default;
220
ValidateConstraints(const QueryConstraints & qc)221 util::Status ExperimentalFlamegraphGenerator::ValidateConstraints(
222 const QueryConstraints& qc) {
223 using T = tables::ExperimentalFlamegraphNodesTable;
224
225 const auto& cs = qc.constraints();
226
227 auto ts_fn = [](const QueryConstraints::Constraint& c) {
228 return c.column == static_cast<int>(T::ColumnIndex::ts) &&
229 c.op == SQLITE_INDEX_CONSTRAINT_EQ;
230 };
231 bool has_ts_cs = std::find_if(cs.begin(), cs.end(), ts_fn) != cs.end();
232
233 auto upid_fn = [](const QueryConstraints::Constraint& c) {
234 return c.column == static_cast<int>(T::ColumnIndex::upid) &&
235 c.op == SQLITE_INDEX_CONSTRAINT_EQ;
236 };
237 bool has_upid_cs = std::find_if(cs.begin(), cs.end(), upid_fn) != cs.end();
238
239 auto profile_type_fn = [](const QueryConstraints::Constraint& c) {
240 return c.column == static_cast<int>(T::ColumnIndex::profile_type) &&
241 c.op == SQLITE_INDEX_CONSTRAINT_EQ;
242 };
243 bool has_profile_type_cs =
244 std::find_if(cs.begin(), cs.end(), profile_type_fn) != cs.end();
245
246 return has_ts_cs && has_upid_cs && has_profile_type_cs
247 ? util::OkStatus()
248 : util::ErrStatus("Failed to find required constraints");
249 }
250
ComputeTable(const std::vector<Constraint> & cs,const std::vector<Order> &)251 std::unique_ptr<Table> ExperimentalFlamegraphGenerator::ComputeTable(
252 const std::vector<Constraint>& cs,
253 const std::vector<Order>&) {
254 // Get the input column values and compute the flamegraph using them.
255 auto values = GetFlamegraphInputValues(cs);
256
257 std::unique_ptr<tables::ExperimentalFlamegraphNodesTable> table;
258 if (values.profile_type == "graph") {
259 auto* tracker = HeapGraphTracker::GetOrCreate(context_);
260 table = tracker->BuildFlamegraph(values.ts, values.upid);
261 }
262 if (values.profile_type == "native") {
263 table =
264 BuildNativeFlamegraph(context_->storage.get(), values.upid, values.ts);
265 }
266 if (!values.focus_str.empty()) {
267 table =
268 FocusTable(context_->storage.get(), std::move(table), values.focus_str);
269 // The pseudocolumns must be populated because as far as SQLite is
270 // concerned these are equality constraints.
271 auto focus_id =
272 context_->storage->InternString(base::StringView(values.focus_str));
273 for (uint32_t i = 0; i < table->row_count(); ++i) {
274 table->mutable_focus_str()->Set(i, focus_id);
275 }
276 }
277 // We need to explicitly std::move as clang complains about a bug in old
278 // compilers otherwise (-Wreturn-std-move-in-c++11).
279 return std::move(table);
280 }
281
CreateSchema()282 Table::Schema ExperimentalFlamegraphGenerator::CreateSchema() {
283 return tables::ExperimentalFlamegraphNodesTable::Schema();
284 }
285
TableName()286 std::string ExperimentalFlamegraphGenerator::TableName() {
287 return "experimental_flamegraph";
288 }
289
EstimateRowCount()290 uint32_t ExperimentalFlamegraphGenerator::EstimateRowCount() {
291 // TODO(lalitm): return a better estimate here when possible.
292 return 1024;
293 }
294
295 } // namespace trace_processor
296 } // namespace perfetto
297