• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// Copyright (C) 2019 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 {Actions} from '../common/actions';
16import {Engine} from '../common/engine';
17import {
18  ALLOC_SPACE_MEMORY_ALLOCATED_KEY,
19  DEFAULT_VIEWING_OPTION,
20  expandCallsites,
21  findRootSize,
22  mergeCallsites,
23  OBJECTS_ALLOCATED_KEY,
24  OBJECTS_ALLOCATED_NOT_FREED_KEY,
25  PERF_SAMPLES_KEY,
26  SPACE_MEMORY_ALLOCATED_NOT_FREED_KEY
27} from '../common/flamegraph_util';
28import {NUM, STR} from '../common/query_result';
29import {CallsiteInfo, FlamegraphState} from '../common/state';
30import {toNs} from '../common/time';
31import {
32  FlamegraphDetails,
33  globals as frontendGlobals
34} from '../frontend/globals';
35import {publishFlamegraphDetails} from '../frontend/publish';
36import {
37  Config as PerfSampleConfig,
38  PERF_SAMPLES_PROFILE_TRACK_KIND
39} from '../tracks/perf_samples_profile/common';
40
41import {AreaSelectionHandler} from './area_selection_handler';
42import {Controller} from './controller';
43import {globals} from './globals';
44
45export interface FlamegraphControllerArgs {
46  engine: Engine;
47}
48const MIN_PIXEL_DISPLAYED = 1;
49
50class TablesCache {
51  private engine: Engine;
52  private cache: Map<string, string>;
53  private prefix: string;
54  private tableId: number;
55  private cacheSizeLimit: number;
56
57  constructor(engine: Engine, prefix: string) {
58    this.engine = engine;
59    this.cache = new Map<string, string>();
60    this.prefix = prefix;
61    this.tableId = 0;
62    this.cacheSizeLimit = 10;
63  }
64
65  async getTableName(query: string): Promise<string> {
66    let tableName = this.cache.get(query);
67    if (tableName === undefined) {
68      // TODO(hjd): This should be LRU.
69      if (this.cache.size > this.cacheSizeLimit) {
70        for (const name of this.cache.values()) {
71          await this.engine.query(`drop table ${name}`);
72        }
73        this.cache.clear();
74      }
75      tableName = `${this.prefix}_${this.tableId++}`;
76      await this.engine.query(
77          `create temp table if not exists ${tableName} as ${query}`);
78      this.cache.set(query, tableName);
79    }
80    return tableName;
81  }
82}
83
84export class FlamegraphController extends Controller<'main'> {
85  private flamegraphDatasets: Map<string, CallsiteInfo[]> = new Map();
86  private lastSelectedFlamegraphState?: FlamegraphState;
87  private requestingData = false;
88  private queuedRequest = false;
89  private flamegraphDetails: FlamegraphDetails = {};
90  private areaSelectionHandler: AreaSelectionHandler;
91  private cache: TablesCache;
92
93  constructor(private args: FlamegraphControllerArgs) {
94    super('main');
95    this.cache = new TablesCache(args.engine, 'grouped_callsites');
96    this.areaSelectionHandler = new AreaSelectionHandler();
97  }
98
99  run() {
100    const [hasAreaChanged, area] = this.areaSelectionHandler.getAreaChange();
101    if (hasAreaChanged) {
102      const upids = [];
103      if (!area) {
104        this.checkCompletionAndPublishFlamegraph(
105            {...frontendGlobals.flamegraphDetails, isInAreaSelection: false});
106        return;
107      }
108      for (const trackId of area.tracks) {
109        const trackState = frontendGlobals.state.tracks[trackId];
110        if (!trackState ||
111            trackState.kind !== PERF_SAMPLES_PROFILE_TRACK_KIND) {
112          continue;
113        }
114        upids.push((trackState.config as PerfSampleConfig).upid);
115      }
116      if (upids.length === 0) {
117        this.checkCompletionAndPublishFlamegraph(
118            {...frontendGlobals.flamegraphDetails, isInAreaSelection: false});
119        return;
120      }
121      frontendGlobals.dispatch(Actions.openFlamegraph({
122        upids,
123        startNs: toNs(area.startSec),
124        endNs: toNs(area.endSec),
125        type: 'perf',
126        viewingOption: PERF_SAMPLES_KEY
127      }));
128    }
129    const selection = frontendGlobals.state.currentFlamegraphState;
130    if (!selection || !this.shouldRequestData(selection)) {
131      return;
132    }
133    if (this.requestingData) {
134      this.queuedRequest = true;
135      return;
136    }
137    this.requestingData = true;
138
139    this.assembleFlamegraphDetails(selection, hasAreaChanged);
140  }
141
142  private async assembleFlamegraphDetails(
143      selection: FlamegraphState, hasAreaChanged: boolean) {
144    const selectedFlamegraphState = {...selection};
145    const flamegraphMetadata = await this.getFlamegraphMetadata(
146        selection.type,
147        selectedFlamegraphState.startNs,
148        selectedFlamegraphState.endNs,
149        selectedFlamegraphState.upids);
150    if (flamegraphMetadata !== undefined) {
151      Object.assign(this.flamegraphDetails, flamegraphMetadata);
152    }
153
154    // TODO(hjd): Clean this up.
155    if (this.lastSelectedFlamegraphState &&
156        this.lastSelectedFlamegraphState.focusRegex !== selection.focusRegex) {
157      this.flamegraphDatasets.clear();
158    }
159
160    this.lastSelectedFlamegraphState = {...selection};
161
162    const expandedId = selectedFlamegraphState.expandedCallsite ?
163        selectedFlamegraphState.expandedCallsite.id :
164        -1;
165    const rootSize = selectedFlamegraphState.expandedCallsite === undefined ?
166        undefined :
167        selectedFlamegraphState.expandedCallsite.totalSize;
168
169    const key = `${selectedFlamegraphState.upids};${
170        selectedFlamegraphState.startNs};${selectedFlamegraphState.endNs}`;
171
172    try {
173      const flamegraphData = await this.getFlamegraphData(
174          key,
175          selectedFlamegraphState.viewingOption ?
176              selectedFlamegraphState.viewingOption :
177              DEFAULT_VIEWING_OPTION,
178          selection.startNs,
179          selection.endNs,
180          selectedFlamegraphState.upids,
181          selectedFlamegraphState.type,
182          selectedFlamegraphState.focusRegex);
183      if (flamegraphData !== undefined && selection &&
184          selection.kind === selectedFlamegraphState.kind &&
185          selection.startNs === selectedFlamegraphState.startNs &&
186          selection.endNs === selectedFlamegraphState.endNs) {
187        const expandedFlamegraphData =
188            expandCallsites(flamegraphData, expandedId);
189        this.prepareAndMergeCallsites(
190            expandedFlamegraphData,
191            this.lastSelectedFlamegraphState.viewingOption,
192            hasAreaChanged,
193            rootSize,
194            this.lastSelectedFlamegraphState.expandedCallsite);
195      }
196    } finally {
197      this.requestingData = false;
198      if (this.queuedRequest) {
199        this.queuedRequest = false;
200        this.run();
201      }
202    }
203  }
204
205  private shouldRequestData(selection: FlamegraphState) {
206    return selection.kind === 'FLAMEGRAPH_STATE' &&
207        (this.lastSelectedFlamegraphState === undefined ||
208         (this.lastSelectedFlamegraphState.startNs !== selection.startNs ||
209          this.lastSelectedFlamegraphState.endNs !== selection.endNs ||
210          this.lastSelectedFlamegraphState.type !== selection.type ||
211          !FlamegraphController.areArraysEqual(
212              this.lastSelectedFlamegraphState.upids, selection.upids) ||
213          this.lastSelectedFlamegraphState.viewingOption !==
214              selection.viewingOption ||
215          this.lastSelectedFlamegraphState.focusRegex !==
216              selection.focusRegex ||
217          this.lastSelectedFlamegraphState.expandedCallsite !==
218              selection.expandedCallsite));
219  }
220
221  private prepareAndMergeCallsites(
222      flamegraphData: CallsiteInfo[],
223      viewingOption: string|undefined = DEFAULT_VIEWING_OPTION,
224      hasAreaChanged: boolean, rootSize?: number,
225      expandedCallsite?: CallsiteInfo) {
226    this.flamegraphDetails.flamegraph = mergeCallsites(
227        flamegraphData, this.getMinSizeDisplayed(flamegraphData, rootSize));
228    this.flamegraphDetails.expandedCallsite = expandedCallsite;
229    this.flamegraphDetails.viewingOption = viewingOption;
230    this.flamegraphDetails.isInAreaSelection = hasAreaChanged;
231    this.checkCompletionAndPublishFlamegraph(this.flamegraphDetails);
232  }
233
234  private async checkCompletionAndPublishFlamegraph(flamegraphDetails:
235                                                        FlamegraphDetails) {
236    flamegraphDetails.graphIncomplete =
237        (await this.args.engine.query(`select value from stats
238       where severity = 'error' and name = 'heap_graph_non_finalized_graph'`))
239            .firstRow({value: NUM})
240            .value > 0;
241    publishFlamegraphDetails(flamegraphDetails);
242  }
243
244  async getFlamegraphData(
245      baseKey: string, viewingOption: string, startNs: number, endNs: number,
246      upids: number[], type: string,
247      focusRegex: string): Promise<CallsiteInfo[]> {
248    let currentData: CallsiteInfo[];
249    const key = `${baseKey}-${viewingOption}`;
250    if (this.flamegraphDatasets.has(key)) {
251      currentData = this.flamegraphDatasets.get(key)!;
252    } else {
253      // TODO(hjd): Show loading state.
254
255      // Collecting data for drawing flamegraph for selected profile.
256      // Data needs to be in following format:
257      // id, name, parent_id, depth, total_size
258      const tableName = await this.prepareViewsAndTables(
259          startNs, endNs, upids, type, focusRegex);
260      currentData = await this.getFlamegraphDataFromTables(
261          tableName, viewingOption, focusRegex);
262      this.flamegraphDatasets.set(key, currentData);
263    }
264    return currentData;
265  }
266
267  async getFlamegraphDataFromTables(
268      tableName: string, viewingOption = DEFAULT_VIEWING_OPTION,
269      focusRegex: string) {
270    let orderBy = '';
271    let totalColumnName: 'cumulativeSize'|'cumulativeAllocSize'|
272        'cumulativeCount'|'cumulativeAllocCount' = 'cumulativeSize';
273    let selfColumnName: 'size'|'count' = 'size';
274    // TODO(fmayer): Improve performance so this is no longer necessary.
275    // Alternatively consider collapsing frames of the same label.
276    const maxDepth = 100;
277    switch (viewingOption) {
278      case ALLOC_SPACE_MEMORY_ALLOCATED_KEY:
279        orderBy = `where cumulative_alloc_size > 0 and depth < ${
280            maxDepth} order by depth, parent_id,
281            cumulative_alloc_size desc, name`;
282        totalColumnName = 'cumulativeAllocSize';
283        selfColumnName = 'size';
284        break;
285      case OBJECTS_ALLOCATED_NOT_FREED_KEY:
286        orderBy = `where cumulative_count > 0 and depth < ${
287            maxDepth} order by depth, parent_id,
288            cumulative_count desc, name`;
289        totalColumnName = 'cumulativeCount';
290        selfColumnName = 'count';
291        break;
292      case OBJECTS_ALLOCATED_KEY:
293        orderBy = `where cumulative_alloc_count > 0 and depth < ${
294            maxDepth} order by depth, parent_id,
295            cumulative_alloc_count desc, name`;
296        totalColumnName = 'cumulativeAllocCount';
297        selfColumnName = 'count';
298        break;
299      case PERF_SAMPLES_KEY:
300      case SPACE_MEMORY_ALLOCATED_NOT_FREED_KEY:
301        orderBy = `where cumulative_size > 0 and depth < ${
302            maxDepth} order by depth, parent_id,
303            cumulative_size desc, name`;
304        totalColumnName = 'cumulativeSize';
305        selfColumnName = 'size';
306        break;
307      default:
308        break;
309    }
310
311    const callsites = await this.args.engine.query(`
312        SELECT
313        id as hash,
314        IFNULL(IFNULL(DEMANGLE(name), name), '[NULL]') as name,
315        IFNULL(parent_id, -1) as parentHash,
316        depth,
317        cumulative_size as cumulativeSize,
318        cumulative_alloc_size as cumulativeAllocSize,
319        cumulative_count as cumulativeCount,
320        cumulative_alloc_count as cumulativeAllocCount,
321        map_name as mapping,
322        size,
323        count,
324        IFNULL(source_file, '') as sourceFile,
325        IFNULL(line_number, -1) as lineNumber
326        from ${tableName} ${orderBy}`);
327
328    const flamegraphData: CallsiteInfo[] = [];
329    const hashToindex: Map<number, number> = new Map();
330    const it = callsites.iter({
331      hash: NUM,
332      name: STR,
333      parentHash: NUM,
334      depth: NUM,
335      cumulativeSize: NUM,
336      cumulativeAllocSize: NUM,
337      cumulativeCount: NUM,
338      cumulativeAllocCount: NUM,
339      mapping: STR,
340      sourceFile: STR,
341      lineNumber: NUM,
342      size: NUM,
343      count: NUM,
344    });
345    for (let i = 0; it.valid(); ++i, it.next()) {
346      const hash = it.hash;
347      let name = it.name;
348      const parentHash = it.parentHash;
349      const depth = it.depth;
350      const totalSize = it[totalColumnName];
351      const selfSize = it[selfColumnName];
352      const mapping = it.mapping;
353      const highlighted = focusRegex !== '' &&
354          name.toLocaleLowerCase().includes(focusRegex.toLocaleLowerCase());
355      const parentId =
356          hashToindex.has(+parentHash) ? hashToindex.get(+parentHash)! : -1;
357
358      let location: string|undefined;
359      if (/[a-zA-Z]/i.test(it.sourceFile)) {
360        location = it.sourceFile;
361        if (it.lineNumber !== -1) {
362          location += `:${it.lineNumber}`;
363        }
364      }
365
366      if (depth === maxDepth - 1) {
367        name += ' [tree truncated]';
368      }
369      // Instead of hash, we will store index of callsite in this original array
370      // as an id of callsite. That way, we have quicker access to parent and it
371      // will stay unique:
372      hashToindex.set(hash, i);
373
374      flamegraphData.push({
375        id: i,
376        totalSize,
377        depth,
378        parentId,
379        name,
380        selfSize,
381        mapping,
382        merged: false,
383        highlighted,
384        location
385      });
386    }
387    return flamegraphData;
388  }
389
390  private async prepareViewsAndTables(
391      startNs: number, endNs: number, upids: number[], type: string,
392      focusRegex: string): Promise<string> {
393    // Creating unique names for views so we can reuse and not delete them
394    // for each marker.
395    let focusRegexConditional = '';
396    if (focusRegex !== '') {
397      focusRegexConditional = `and focus_str = '${focusRegex}'`;
398    }
399
400    /*
401     * TODO(octaviant) this branching should be eliminated for simplicity.
402     */
403    if (type === 'perf') {
404      let upidConditional = `upid = ${upids[0]}`;
405      if (upids.length > 1) {
406        upidConditional =
407            `upid_group = '${FlamegraphController.serializeUpidGroup(upids)}'`;
408      }
409      return this.cache.getTableName(
410          `select id, name, map_name, parent_id, depth, cumulative_size,
411          cumulative_alloc_size, cumulative_count, cumulative_alloc_count,
412          size, alloc_size, count, alloc_count, source_file, line_number
413          from experimental_flamegraph
414          where profile_type = '${type}' and ${startNs} <= ts and ts <= ${
415              endNs} and ${upidConditional}
416          ${focusRegexConditional}`);
417    }
418    return this.cache.getTableName(
419        `select id, name, map_name, parent_id, depth, cumulative_size,
420          cumulative_alloc_size, cumulative_count, cumulative_alloc_count,
421          size, alloc_size, count, alloc_count, source_file, line_number
422          from experimental_flamegraph
423          where profile_type = '${type}'
424            and ts = ${endNs}
425            and upid = ${upids[0]}
426            ${focusRegexConditional}`);
427  }
428
429  getMinSizeDisplayed(flamegraphData: CallsiteInfo[], rootSize?: number):
430      number {
431    const timeState = globals.state.frontendLocalState.visibleState;
432    let width = (timeState.endSec - timeState.startSec) / timeState.resolution;
433    // TODO(168048193): Remove screen size hack:
434    width = Math.max(width, 800);
435    if (rootSize === undefined) {
436      rootSize = findRootSize(flamegraphData);
437    }
438    return MIN_PIXEL_DISPLAYED * rootSize / width;
439  }
440
441  async getFlamegraphMetadata(
442      type: string, startNs: number, endNs: number, upids: number[]) {
443    // Don't do anything if selection of the marker stayed the same.
444    if ((this.lastSelectedFlamegraphState !== undefined &&
445         ((this.lastSelectedFlamegraphState.startNs === startNs &&
446           this.lastSelectedFlamegraphState.endNs === endNs &&
447           FlamegraphController.areArraysEqual(
448               this.lastSelectedFlamegraphState.upids, upids))))) {
449      return undefined;
450    }
451
452    // Collecting data for more information about profile, such as:
453    // total memory allocated, memory that is allocated and not freed.
454    const upidGroup = FlamegraphController.serializeUpidGroup(upids);
455
456    const result = await this.args.engine.query(
457        `select pid from process where upid in (${upidGroup})`);
458    const it = result.iter({pid: NUM});
459    const pids = [];
460    for (let i = 0; it.valid(); ++i, it.next()) {
461      pids.push(it.pid);
462    }
463    return {startNs, durNs: endNs - startNs, pids, upids, type};
464  }
465
466  private static areArraysEqual(a: number[], b: number[]) {
467    if (a.length !== b.length) {
468      return false;
469    }
470    for (let i = 0; i < a.length; i++) {
471      if (a[i] !== b[i]) {
472        return false;
473      }
474    }
475    return true;
476  }
477
478  private static serializeUpidGroup(upids: number[]) {
479    return new Array(upids).join();
480  }
481}
482