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/perfetto_sql/intrinsics/table_functions/experimental_flamegraph.h"
18
19 #include <cstdint>
20 #include <memory>
21 #include <optional>
22 #include <string>
23 #include <utility>
24 #include <vector>
25
26 #include "perfetto/base/logging.h"
27 #include "perfetto/base/status.h"
28 #include "perfetto/ext/base/status_or.h"
29 #include "perfetto/ext/base/string_utils.h"
30 #include "perfetto/trace_processor/basic_types.h"
31 #include "src/trace_processor/db/column/types.h"
32 #include "src/trace_processor/db/table.h"
33 #include "src/trace_processor/importers/proto/heap_graph_tracker.h"
34 #include "src/trace_processor/perfetto_sql/intrinsics/table_functions/flamegraph_construction_algorithms.h"
35 #include "src/trace_processor/sqlite/sqlite_utils.h"
36 #include "src/trace_processor/storage/trace_storage.h"
37 #include "src/trace_processor/tables/profiler_tables_py.h"
38 #include "src/trace_processor/types/trace_processor_context.h"
39 #include "src/trace_processor/util/status_macros.h"
40
41 namespace perfetto::trace_processor {
42
43 namespace {
44
ExtractProfileType(const std::string & profile_name)45 base::StatusOr<ExperimentalFlamegraph::ProfileType> ExtractProfileType(
46 const std::string& profile_name) {
47 if (profile_name == "graph") {
48 return ExperimentalFlamegraph::ProfileType::kGraph;
49 }
50 if (profile_name == "native") {
51 return ExperimentalFlamegraph::ProfileType::kHeapProfile;
52 }
53 if (profile_name == "perf") {
54 return ExperimentalFlamegraph::ProfileType::kPerf;
55 }
56 return base::ErrStatus(
57 "experimental_flamegraph: Could not recognize profile type: %s.",
58 profile_name.c_str());
59 }
60
ParseTimeConstraintTs(const std::string & c,uint32_t offset)61 base::StatusOr<int64_t> ParseTimeConstraintTs(const std::string& c,
62 uint32_t offset) {
63 std::optional<int64_t> ts = base::CStringToInt64(&c[offset]);
64 if (!ts) {
65 return base::ErrStatus(
66 "experimental_flamegraph: Unable to parse timestamp");
67 }
68 return *ts;
69 }
70
ParseTimeConstraint(const std::string & c)71 base::StatusOr<TimeConstraints> ParseTimeConstraint(const std::string& c) {
72 if (base::StartsWith(c, "=")) {
73 ASSIGN_OR_RETURN(int64_t ts, ParseTimeConstraintTs(c, 1));
74 return TimeConstraints{FilterOp::kEq, ts};
75 }
76 if (base::StartsWith(c, ">=")) {
77 ASSIGN_OR_RETURN(int64_t ts, ParseTimeConstraintTs(c, 2));
78 return TimeConstraints{FilterOp::kGe, ts};
79 }
80 if (base::StartsWith(c, ">")) {
81 ASSIGN_OR_RETURN(int64_t ts, ParseTimeConstraintTs(c, 1));
82 return TimeConstraints{FilterOp::kGt, ts};
83 }
84 if (base::StartsWith(c, "<=")) {
85 ASSIGN_OR_RETURN(int64_t ts, ParseTimeConstraintTs(c, 2));
86 return TimeConstraints{FilterOp::kLe, ts};
87 }
88 if (base::StartsWith(c, ">=")) {
89 ASSIGN_OR_RETURN(int64_t ts, ParseTimeConstraintTs(c, 2));
90 return TimeConstraints{FilterOp::kLt, ts};
91 }
92 return base::ErrStatus("experimental_flamegraph: Unknown time constraint");
93 }
94
ExtractTimeConstraints(const SqlValue & value)95 base::StatusOr<std::vector<TimeConstraints>> ExtractTimeConstraints(
96 const SqlValue& value) {
97 PERFETTO_DCHECK(value.is_null() || value.type == SqlValue::kString);
98 std::vector<TimeConstraints> constraints;
99 if (value.is_null()) {
100 return constraints;
101 }
102 std::vector<std::string> raw_cs = base::SplitString(value.AsString(), ",");
103 for (const std::string& c : raw_cs) {
104 ASSIGN_OR_RETURN(TimeConstraints tc, ParseTimeConstraint(c));
105 constraints.push_back(tc);
106 }
107 return constraints;
108 }
109
110 // For filtering, this method uses the same constraints as
111 // ExperimentalFlamegraph::ValidateConstraints and should therefore
112 // be kept in sync.
GetFlamegraphInputValues(const std::vector<SqlValue> & arguments)113 base::StatusOr<ExperimentalFlamegraph::InputValues> GetFlamegraphInputValues(
114 const std::vector<SqlValue>& arguments) {
115 PERFETTO_CHECK(arguments.size() == 6);
116
117 const SqlValue& raw_profile_type = arguments[0];
118 if (raw_profile_type.type != SqlValue::kString) {
119 return base::ErrStatus(
120 "experimental_flamegraph: profile_type must be an string");
121 }
122 const SqlValue& ts = arguments[1];
123 if (ts.type != SqlValue::kLong && !ts.is_null()) {
124 return base::ErrStatus("experimental_flamegraph: ts must be an integer");
125 }
126 const SqlValue& ts_constraints = arguments[2];
127 if (ts_constraints.type != SqlValue::kString && !ts_constraints.is_null()) {
128 return base::ErrStatus(
129 "experimental_flamegraph: ts constraint must be an string");
130 }
131 const SqlValue& upid = arguments[3];
132 if (upid.type != SqlValue::kLong && !upid.is_null()) {
133 return base::ErrStatus("experimental_flamegraph: upid must be an integer");
134 }
135 const SqlValue& upid_group = arguments[4];
136 if (upid_group.type != SqlValue::kString && !upid_group.is_null()) {
137 return base::ErrStatus(
138 "experimental_flamegraph: upid_group must be an string");
139 }
140 const SqlValue& focus_str = arguments[5];
141 if (focus_str.type != SqlValue::kString && !focus_str.is_null()) {
142 return base::ErrStatus(
143 "experimental_flamegraph: focus_str must be an string");
144 }
145
146 if (ts.is_null() && ts_constraints.is_null()) {
147 return base::ErrStatus(
148 "experimental_flamegraph: one of ts and ts_constraints must not be "
149 "null");
150 }
151 if (upid.is_null() && upid_group.is_null()) {
152 return base::ErrStatus(
153 "experimental_flamegraph: one of upid or upid_group must not be null");
154 }
155 ASSIGN_OR_RETURN(std::vector<TimeConstraints> time_constraints,
156 ExtractTimeConstraints(ts_constraints));
157 ASSIGN_OR_RETURN(ExperimentalFlamegraph::ProfileType profile_type,
158 ExtractProfileType(raw_profile_type.AsString()));
159 return ExperimentalFlamegraph::InputValues{
160 profile_type,
161 ts.is_null() ? std::nullopt : std::make_optional(ts.AsLong()),
162 std::move(time_constraints),
163 upid.is_null() ? std::nullopt
164 : std::make_optional(static_cast<uint32_t>(upid.AsLong())),
165 upid_group.is_null() ? std::nullopt
166 : std::make_optional(upid_group.AsString()),
167 focus_str.is_null() ? std::nullopt
168 : std::make_optional(focus_str.AsString()),
169 };
170 }
171
172 class Matcher {
173 public:
Matcher(const std::string & str)174 explicit Matcher(const std::string& str) : focus_str_(base::ToLower(str)) {}
175 Matcher(const Matcher&) = delete;
176 Matcher& operator=(const Matcher&) = delete;
177
matches(const std::string & s) const178 bool matches(const std::string& s) const {
179 // TODO(149833691): change to regex.
180 // We cannot use regex.h (does not exist in windows) or std regex (throws
181 // exceptions).
182 return base::Contains(base::ToLower(s), focus_str_);
183 }
184
185 private:
186 const std::string focus_str_;
187 };
188
189 enum class FocusedState {
190 kNotFocused,
191 kFocusedPropagating,
192 kFocusedNotPropagating,
193 };
194
195 using tables::ExperimentalFlamegraphTable;
ComputeFocusedState(const ExperimentalFlamegraphTable & table,const Matcher & focus_matcher)196 std::vector<FocusedState> ComputeFocusedState(
197 const ExperimentalFlamegraphTable& table,
198 const Matcher& focus_matcher) {
199 // Each row corresponds to a node in the flame chart tree with its parent
200 // ptr. Root trees (no parents) will have a null parent ptr.
201 std::vector<FocusedState> focused(table.row_count());
202
203 for (uint32_t i = 0; i < table.row_count(); ++i) {
204 auto parent_id = table.parent_id()[i];
205 // Constraint: all descendants MUST come after their parents.
206 PERFETTO_DCHECK(!parent_id.has_value() || *parent_id < table.id()[i]);
207
208 if (focus_matcher.matches(table.name().GetString(i).ToStdString())) {
209 // Mark as focused
210 focused[i] = FocusedState::kFocusedPropagating;
211 auto current = parent_id;
212 // Mark all parent nodes as focused
213 while (current.has_value()) {
214 auto current_idx = *table.id().IndexOf(*current);
215 if (focused[current_idx] != FocusedState::kNotFocused) {
216 // We have already visited these nodes, skip
217 break;
218 }
219 focused[current_idx] = FocusedState::kFocusedNotPropagating;
220 current = table.parent_id()[current_idx];
221 }
222 } else if (parent_id.has_value() &&
223 focused[*table.id().IndexOf(*parent_id)] ==
224 FocusedState::kFocusedPropagating) {
225 // Focus cascades downwards.
226 focused[i] = FocusedState::kFocusedPropagating;
227 } else {
228 focused[i] = FocusedState::kNotFocused;
229 }
230 }
231 return focused;
232 }
233
234 struct CumulativeCounts {
235 int64_t size;
236 int64_t count;
237 int64_t alloc_size;
238 int64_t alloc_count;
239 };
FocusTable(TraceStorage * storage,std::unique_ptr<ExperimentalFlamegraphTable> in,const std::string & focus_str)240 std::unique_ptr<tables::ExperimentalFlamegraphTable> FocusTable(
241 TraceStorage* storage,
242 std::unique_ptr<ExperimentalFlamegraphTable> in,
243 const std::string& focus_str) {
244 if (in->row_count() == 0 || focus_str.empty()) {
245 return in;
246 }
247 std::vector<FocusedState> focused_state =
248 ComputeFocusedState(*in, Matcher(focus_str));
249 std::unique_ptr<ExperimentalFlamegraphTable> tbl(
250 new tables::ExperimentalFlamegraphTable(storage->mutable_string_pool()));
251
252 // Recompute cumulative counts
253 std::vector<CumulativeCounts> node_to_cumulatives(in->row_count());
254 for (int64_t idx = in->row_count() - 1; idx >= 0; --idx) {
255 auto i = static_cast<uint32_t>(idx);
256 if (focused_state[i] == FocusedState::kNotFocused) {
257 continue;
258 }
259 auto& cumulatives = node_to_cumulatives[i];
260 cumulatives.size += in->size()[i];
261 cumulatives.count += in->count()[i];
262 cumulatives.alloc_size += in->alloc_size()[i];
263 cumulatives.alloc_count += in->alloc_count()[i];
264
265 auto parent_id = in->parent_id()[i];
266 if (parent_id.has_value()) {
267 auto& parent_cumulatives =
268 node_to_cumulatives[*in->id().IndexOf(*parent_id)];
269 parent_cumulatives.size += cumulatives.size;
270 parent_cumulatives.count += cumulatives.count;
271 parent_cumulatives.alloc_size += cumulatives.alloc_size;
272 parent_cumulatives.alloc_count += cumulatives.alloc_count;
273 }
274 }
275
276 // Mapping between the old rows ('node') to the new identifiers.
277 std::vector<ExperimentalFlamegraphTable::Id> node_to_id(in->row_count());
278 for (uint32_t i = 0; i < in->row_count(); ++i) {
279 if (focused_state[i] == FocusedState::kNotFocused) {
280 continue;
281 }
282
283 tables::ExperimentalFlamegraphTable::Row alloc_row{};
284 // We must reparent the rows as every insertion will get its own
285 // identifier.
286 auto original_parent_id = in->parent_id()[i];
287 if (original_parent_id.has_value()) {
288 auto original_idx = *in->id().IndexOf(*original_parent_id);
289 alloc_row.parent_id = node_to_id[original_idx];
290 }
291
292 alloc_row.ts = in->ts()[i];
293 alloc_row.upid = in->upid()[i];
294 alloc_row.profile_type = in->profile_type()[i];
295 alloc_row.depth = in->depth()[i];
296 alloc_row.name = in->name()[i];
297 alloc_row.map_name = in->map_name()[i];
298 alloc_row.count = in->count()[i];
299 alloc_row.size = in->size()[i];
300 alloc_row.alloc_count = in->alloc_count()[i];
301 alloc_row.alloc_size = in->alloc_size()[i];
302
303 const auto& cumulative = node_to_cumulatives[i];
304 alloc_row.cumulative_count = cumulative.count;
305 alloc_row.cumulative_size = cumulative.size;
306 alloc_row.cumulative_alloc_count = cumulative.alloc_count;
307 alloc_row.cumulative_alloc_size = cumulative.alloc_size;
308 node_to_id[i] = tbl->Insert(alloc_row).id;
309 }
310 return tbl;
311 }
312 } // namespace
313
ExperimentalFlamegraph(TraceProcessorContext * context)314 ExperimentalFlamegraph::ExperimentalFlamegraph(TraceProcessorContext* context)
315 : context_(context) {}
316
317 ExperimentalFlamegraph::~ExperimentalFlamegraph() = default;
318
ComputeTable(const std::vector<SqlValue> & arguments)319 base::StatusOr<std::unique_ptr<Table>> ExperimentalFlamegraph::ComputeTable(
320 const std::vector<SqlValue>& arguments) {
321 ASSIGN_OR_RETURN(auto values, GetFlamegraphInputValues(arguments));
322
323 std::unique_ptr<tables::ExperimentalFlamegraphTable> table;
324 switch (values.profile_type) {
325 case ProfileType::kGraph: {
326 if (!values.ts || !values.upid) {
327 return base::ErrStatus(
328 "experimental_flamegraph: ts and upid must be present for heap "
329 "graph");
330 }
331 table = HeapGraphTracker::GetOrCreate(context_)->BuildFlamegraph(
332 *values.ts, *values.upid);
333 break;
334 }
335 case ProfileType::kHeapProfile: {
336 if (!values.ts || !values.upid) {
337 return base::ErrStatus(
338 "experimental_flamegraph: ts and upid must be present for heap "
339 "profile");
340 }
341 table = BuildHeapProfileFlamegraph(context_->storage.get(), *values.upid,
342 *values.ts);
343 break;
344 }
345 case ProfileType::kPerf: {
346 table = BuildNativeCallStackSamplingFlamegraph(
347 context_->storage.get(), values.upid, values.upid_group,
348 values.time_constraints);
349 break;
350 }
351 }
352 if (!table) {
353 return base::ErrStatus("Failed to build flamegraph");
354 }
355 if (values.focus_str) {
356 table = FocusTable(context_->storage.get(), std::move(table),
357 *values.focus_str);
358 }
359 return std::unique_ptr<Table>(std::move(table));
360 }
361
CreateSchema()362 Table::Schema ExperimentalFlamegraph::CreateSchema() {
363 return tables::ExperimentalFlamegraphTable::ComputeStaticSchema();
364 }
365
TableName()366 std::string ExperimentalFlamegraph::TableName() {
367 return tables::ExperimentalFlamegraphTable::Name();
368 }
369
EstimateRowCount()370 uint32_t ExperimentalFlamegraph::EstimateRowCount() {
371 // TODO(lalitm): return a better estimate here when possible.
372 return 1024;
373 }
374
375 } // namespace perfetto::trace_processor
376