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