• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// Copyright (C) 2024 The Android Open Source Project
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15import m from 'mithril';
16import {AsyncLimiter} from '../base/async_limiter';
17import {AsyncDisposableStack} from '../base/disposable_stack';
18import {assertExists} from '../base/logging';
19import {Monitor} from '../base/monitor';
20import {uuidv4Sql} from '../base/uuid';
21import {Engine} from '../trace_processor/engine';
22import {
23  createPerfettoIndex,
24  createPerfettoTable,
25} from '../trace_processor/sql_utils';
26import {
27  NUM,
28  NUM_NULL,
29  STR,
30  STR_NULL,
31  UNKNOWN,
32} from '../trace_processor/query_result';
33import {
34  Flamegraph,
35  FlamegraphPropertyDefinition,
36  FlamegraphQueryData,
37  FlamegraphState,
38  FlamegraphView,
39  FlamegraphOptionalAction,
40} from '../widgets/flamegraph';
41import {Trace} from '../public/trace';
42
43export interface QueryFlamegraphColumn {
44  // The name of the column in SQL.
45  readonly name: string;
46
47  // The human readable name describing the contents of the column.
48  readonly displayName: string;
49
50  // Whether the name should be displayed in the UI.
51  readonly isVisible?: boolean;
52}
53
54export interface AggQueryFlamegraphColumn extends QueryFlamegraphColumn {
55  // The aggregation to be run when nodes are merged together in the flamegraph.
56  //
57  // TODO(lalitm): consider adding extra functions here (e.g. a top 5 or similar).
58  readonly mergeAggregation: 'ONE_OR_NULL' | 'SUM' | 'CONCAT_WITH_COMMA';
59}
60
61export interface QueryFlamegraphMetric {
62  // The human readable name of the metric: will be shown to the user to change
63  // between metrics.
64  readonly name: string;
65
66  // The human readable SI-style unit of `selfValue`. Values will be shown to
67  // the user suffixed with this.
68  readonly unit: string;
69
70  // SQL statement which need to be run in preparation for being able to execute
71  // `statement`.
72  readonly dependencySql?: string;
73
74  // A single SQL statement which returns the columns `id`, `parentId`, `name`
75  // `selfValue`, all columns specified by `unaggregatableProperties` and
76  // `aggregatableProperties`.
77  readonly statement: string;
78
79  // Additional contextual columns containing data which should not be merged
80  // between sibling nodes, even if they have the same name.
81  //
82  // Examples include the mapping that a name comes from, the heap graph root
83  // type etc.
84  //
85  // Note: the name is always unaggregatable and should not be specified here.
86  readonly unaggregatableProperties?: ReadonlyArray<QueryFlamegraphColumn>;
87
88  // Additional contextual columns containing data which will be displayed to
89  // the user if there is no merging. If there is merging, currently the value
90  // will not be shown.
91  //
92  // Examples include the source file and line number.
93  readonly aggregatableProperties?: ReadonlyArray<AggQueryFlamegraphColumn>;
94
95  // Optional actions to be taken on the flamegraph nodes. Accessible from the
96  // flamegraph tooltip.
97  //
98  // Examples include showing a table of objects from a class reference
99  // hierarchy.
100  readonly optionalNodeActions?: ReadonlyArray<FlamegraphOptionalAction>;
101
102  // Optional actions to be taken on the flamegraph root. Accessible from the
103  // flamegraph tooltip.
104  //
105  // Examples include showing a table of objects from a class reference
106  // hierarchy.
107  readonly optionalRootActions?: ReadonlyArray<FlamegraphOptionalAction>;
108}
109
110export interface QueryFlamegraphState {
111  state: FlamegraphState;
112}
113
114// Given a table and columns on those table (corresponding to metrics),
115// returns an array of `QueryFlamegraphMetric` structs which can be passed
116// in QueryFlamegraph's attrs.
117//
118// `tableOrSubquery` should have the columns `id`, `parentId`, `name` and all
119// columns specified by `tableMetrics[].name`, `unaggregatableProperties` and
120// `aggregatableProperties`.
121export function metricsFromTableOrSubquery(
122  tableOrSubquery: string,
123  tableMetrics: ReadonlyArray<{name: string; unit: string; columnName: string}>,
124  dependencySql?: string,
125  unaggregatableProperties?: ReadonlyArray<QueryFlamegraphColumn>,
126  aggregatableProperties?: ReadonlyArray<AggQueryFlamegraphColumn>,
127  optionalActions?: ReadonlyArray<FlamegraphOptionalAction>,
128): QueryFlamegraphMetric[] {
129  const metrics = [];
130  for (const {name, unit, columnName} of tableMetrics) {
131    metrics.push({
132      name,
133      unit,
134      dependencySql,
135      statement: `
136        select *, ${columnName} as value
137        from ${tableOrSubquery}
138      `,
139      unaggregatableProperties,
140      aggregatableProperties,
141      optionalActions,
142    });
143  }
144  return metrics;
145}
146
147// A Perfetto UI component which wraps the `Flamegraph` widget and fetches the
148// data for the widget by querying an `Engine`.
149export class QueryFlamegraph {
150  private data?: FlamegraphQueryData;
151  private readonly selMonitor = new Monitor([() => this.state.state]);
152  private readonly queryLimiter = new AsyncLimiter();
153
154  constructor(
155    private readonly trace: Trace,
156    private readonly metrics: ReadonlyArray<QueryFlamegraphMetric>,
157    private state: QueryFlamegraphState,
158  ) {}
159
160  render() {
161    if (this.selMonitor.ifStateChanged()) {
162      const metric = assertExists(
163        this.metrics.find(
164          (x) => this.state.state.selectedMetricName === x.name,
165        ),
166      );
167      const engine = this.trace.engine;
168      const state = this.state;
169      this.data = undefined;
170      this.queryLimiter.schedule(async () => {
171        this.data = undefined;
172        this.data = await computeFlamegraphTree(engine, metric, state.state);
173      });
174    }
175    return m(Flamegraph, {
176      metrics: this.metrics,
177      data: this.data,
178      state: this.state.state,
179      onStateChange: (state) => {
180        this.state.state = state;
181      },
182    });
183  }
184}
185
186async function computeFlamegraphTree(
187  engine: Engine,
188  {
189    dependencySql,
190    statement,
191    unaggregatableProperties,
192    aggregatableProperties,
193    optionalNodeActions,
194    optionalRootActions,
195  }: QueryFlamegraphMetric,
196  {filters, view}: FlamegraphState,
197): Promise<FlamegraphQueryData> {
198  const showStack = filters
199    .filter((x) => x.kind === 'SHOW_STACK')
200    .map((x) => x.filter);
201  const hideStack = filters
202    .filter((x) => x.kind === 'HIDE_STACK')
203    .map((x) => x.filter);
204  const showFromFrame = filters
205    .filter((x) => x.kind === 'SHOW_FROM_FRAME')
206    .map((x) => x.filter);
207  const hideFrame = filters
208    .filter((x) => x.kind === 'HIDE_FRAME')
209    .map((x) => x.filter);
210
211  // Pivot also essentially acts as a "show stack" filter so treat it like one.
212  const showStackAndPivot = [...showStack];
213  if (view.kind === 'PIVOT') {
214    showStackAndPivot.push(view.pivot);
215  }
216
217  const showStackFilter =
218    showStackAndPivot.length === 0
219      ? '0'
220      : showStackAndPivot
221          .map(
222            (x, i) => `((name like '${makeSqlFilter(x)}' escape '\\') << ${i})`,
223          )
224          .join(' | ');
225  const showStackBits = (1 << showStackAndPivot.length) - 1;
226
227  const hideStackFilter =
228    hideStack.length === 0
229      ? 'false'
230      : hideStack
231          .map((x) => `name like '${makeSqlFilter(x)}' escape '\\'`)
232          .join(' OR ');
233
234  const showFromFrameFilter =
235    showFromFrame.length === 0
236      ? '0'
237      : showFromFrame
238          .map(
239            (x, i) => `((name like '${makeSqlFilter(x)}' escape '\\') << ${i})`,
240          )
241          .join(' | ');
242  const showFromFrameBits = (1 << showFromFrame.length) - 1;
243
244  const hideFrameFilter =
245    hideFrame.length === 0
246      ? 'false'
247      : hideFrame
248          .map((x) => `name like '${makeSqlFilter(x)}' escape '\\'`)
249          .join(' OR ');
250
251  const pivotFilter = getPivotFilter(view);
252
253  const unagg = unaggregatableProperties ?? [];
254  const unaggCols = unagg.map((x) => x.name);
255
256  const agg = aggregatableProperties ?? [];
257  const aggCols = agg.map((x) => x.name);
258
259  const nodeActions = optionalNodeActions ?? [];
260  const rootActions = optionalRootActions ?? [];
261
262  const groupingColumns = `(${(unaggCols.length === 0 ? ['groupingColumn'] : unaggCols).join()})`;
263  const groupedColumns = `(${(aggCols.length === 0 ? ['groupedColumn'] : aggCols).join()})`;
264
265  if (dependencySql !== undefined) {
266    await engine.query(dependencySql);
267  }
268  await engine.query(`include perfetto module viz.flamegraph;`);
269
270  const uuid = uuidv4Sql();
271  await using disposable = new AsyncDisposableStack();
272
273  disposable.use(
274    await createPerfettoTable(
275      engine,
276      `_flamegraph_materialized_statement_${uuid}`,
277      statement,
278    ),
279  );
280  disposable.use(
281    await createPerfettoIndex(
282      engine,
283      `_flamegraph_materialized_statement_${uuid}_index`,
284      `_flamegraph_materialized_statement_${uuid}(parentId)`,
285    ),
286  );
287
288  // TODO(lalitm): this doesn't need to be called unless we have
289  // a non-empty set of filters.
290  disposable.use(
291    await createPerfettoTable(
292      engine,
293      `_flamegraph_source_${uuid}`,
294      `
295        select *
296        from _viz_flamegraph_prepare_filter!(
297          (
298            select
299              s.id,
300              s.parentId,
301              s.name,
302              s.value,
303              ${(unaggCols.length === 0
304                ? [`'' as groupingColumn`]
305                : unaggCols.map((x) => `s.${x}`)
306              ).join()},
307              ${(aggCols.length === 0
308                ? [`'' as groupedColumn`]
309                : aggCols.map((x) => `s.${x}`)
310              ).join()}
311            from _flamegraph_materialized_statement_${uuid} s
312          ),
313          (${showStackFilter}),
314          (${hideStackFilter}),
315          (${showFromFrameFilter}),
316          (${hideFrameFilter}),
317          (${pivotFilter}),
318          ${1 << showStackAndPivot.length},
319          ${groupingColumns}
320        )
321      `,
322    ),
323  );
324  // TODO(lalitm): this doesn't need to be called unless we have
325  // a non-empty set of filters.
326  disposable.use(
327    await createPerfettoTable(
328      engine,
329      `_flamegraph_filtered_${uuid}`,
330      `
331        select *
332        from _viz_flamegraph_filter_frames!(
333          _flamegraph_source_${uuid},
334          ${showFromFrameBits}
335        )
336      `,
337    ),
338  );
339  disposable.use(
340    await createPerfettoTable(
341      engine,
342      `_flamegraph_accumulated_${uuid}`,
343      `
344        select *
345        from _viz_flamegraph_accumulate!(
346          _flamegraph_filtered_${uuid},
347          ${showStackBits}
348        )
349      `,
350    ),
351  );
352  disposable.use(
353    await createPerfettoTable(
354      engine,
355      `_flamegraph_hash_${uuid}`,
356      `
357        select *
358        from _viz_flamegraph_downwards_hash!(
359          _flamegraph_source_${uuid},
360          _flamegraph_filtered_${uuid},
361          _flamegraph_accumulated_${uuid},
362          ${groupingColumns},
363          ${groupedColumns},
364          ${view.kind === 'BOTTOM_UP' ? 'FALSE' : 'TRUE'}
365        )
366        union all
367        select *
368        from _viz_flamegraph_upwards_hash!(
369          _flamegraph_source_${uuid},
370          _flamegraph_filtered_${uuid},
371          _flamegraph_accumulated_${uuid},
372          ${groupingColumns},
373          ${groupedColumns}
374        )
375        order by hash
376      `,
377    ),
378  );
379  disposable.use(
380    await createPerfettoTable(
381      engine,
382      `_flamegraph_merged_${uuid}`,
383      `
384        select *
385        from _viz_flamegraph_merge_hashes!(
386          _flamegraph_hash_${uuid},
387          ${groupingColumns},
388          ${computeGroupedAggExprs(agg)}
389        )
390      `,
391    ),
392  );
393  disposable.use(
394    await createPerfettoTable(
395      engine,
396      `_flamegraph_layout_${uuid}`,
397      `
398        select *
399        from _viz_flamegraph_local_layout!(
400          _flamegraph_merged_${uuid}
401        );
402      `,
403    ),
404  );
405  const res = await engine.query(`
406    select *
407    from _viz_flamegraph_global_layout!(
408      _flamegraph_merged_${uuid},
409      _flamegraph_layout_${uuid},
410      ${groupingColumns},
411      ${groupedColumns}
412    )
413  `);
414
415  const it = res.iter({
416    id: NUM,
417    parentId: NUM,
418    depth: NUM,
419    name: STR,
420    selfValue: NUM,
421    cumulativeValue: NUM,
422    parentCumulativeValue: NUM_NULL,
423    xStart: NUM,
424    xEnd: NUM,
425    ...Object.fromEntries(unaggCols.map((m) => [m, STR_NULL])),
426    ...Object.fromEntries(aggCols.map((m) => [m, UNKNOWN])),
427  });
428  let postiveRootsValue = 0;
429  let negativeRootsValue = 0;
430  let minDepth = 0;
431  let maxDepth = 0;
432  const nodes = [];
433  for (; it.valid(); it.next()) {
434    const properties = new Map<string, FlamegraphPropertyDefinition>();
435    for (const a of [...agg, ...unagg]) {
436      const r = it.get(a.name);
437      if (r !== null) {
438        properties.set(a.name, {
439          displayName: a.displayName,
440          value: r as string,
441          isVisible: a.isVisible ?? true,
442        });
443      }
444    }
445    nodes.push({
446      id: it.id,
447      parentId: it.parentId,
448      depth: it.depth,
449      name: it.name,
450      selfValue: it.selfValue,
451      cumulativeValue: it.cumulativeValue,
452      parentCumulativeValue: it.parentCumulativeValue ?? undefined,
453      xStart: it.xStart,
454      xEnd: it.xEnd,
455      properties,
456    });
457    if (it.depth === 1) {
458      postiveRootsValue += it.cumulativeValue;
459    } else if (it.depth === -1) {
460      negativeRootsValue += it.cumulativeValue;
461    }
462    minDepth = Math.min(minDepth, it.depth);
463    maxDepth = Math.max(maxDepth, it.depth);
464  }
465  const sumQuery = await engine.query(
466    `select sum(value) v from _flamegraph_source_${uuid}`,
467  );
468  const unfilteredCumulativeValue = sumQuery.firstRow({v: NUM_NULL}).v ?? 0;
469  return {
470    nodes,
471    allRootsCumulativeValue:
472      view.kind === 'BOTTOM_UP' ? negativeRootsValue : postiveRootsValue,
473    unfilteredCumulativeValue,
474    minDepth,
475    maxDepth,
476    nodeActions,
477    rootActions,
478  };
479}
480
481function makeSqlFilter(x: string) {
482  if (x.startsWith('^') && x.endsWith('$')) {
483    return x.slice(1, -1);
484  }
485  return `%${x}%`;
486}
487
488function getPivotFilter(view: FlamegraphView) {
489  if (view.kind === 'PIVOT') {
490    return `name like '${makeSqlFilter(view.pivot)}'`;
491  }
492  if (view.kind === 'BOTTOM_UP') {
493    return 'value > 0';
494  }
495  return '0';
496}
497
498function computeGroupedAggExprs(agg: ReadonlyArray<AggQueryFlamegraphColumn>) {
499  const aggFor = (x: AggQueryFlamegraphColumn) => {
500    switch (x.mergeAggregation) {
501      case 'ONE_OR_NULL':
502        return `IIF(COUNT() = 1, ${x.name}, NULL) AS ${x.name}`;
503      case 'SUM':
504        return `SUM(${x.name}) AS ${x.name}`;
505      case 'CONCAT_WITH_COMMA':
506        return `GROUP_CONCAT(${x.name}, ',') AS ${x.name}`;
507    }
508  };
509  return `(${agg.length === 0 ? 'groupedColumn' : agg.map((x) => aggFor(x)).join(',')})`;
510}
511