blob: c0535e7a6c8ef0bba1c3bb3f3f0ffdf12b243ea0 [file] [log] [blame]
// Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
/// Helper for building a treemap out of AOT snapshot size dump.
library vm_snapshot_analysis.treemap;
import 'dart:math';
import 'package:vm_snapshot_analysis/program_info.dart';
import 'package:vm_snapshot_analysis/instruction_sizes.dart'
as instruction_sizes;
import 'package:vm_snapshot_analysis/utils.dart';
import 'package:vm_snapshot_analysis/v8_profile.dart' as v8_profile;
/// Specifies the granularity at which snapshot nodes are represented when
/// converting V8 snapshot profile into a treemap.
enum TreemapFormat {
/// Snapshot nodes are collapsed and only info nodes which own them are
/// represented in the treemap, meaning that each leaf treemap node is
/// essentially representing a [ProgramInfoNode].
collapsed,
/// Similar to [collapsed] but we also fold all information about nested
/// functions into the outermost function (e.g. a method or a top-level
/// function) further simplifying the output.
simplified,
/// Snapshot nodes are collapsed based on their type into two categories:
/// executable code and data. Leaf node in a treemap represents amount of
/// code or data bytes owned by a specific [ProgramInfoNode].
dataAndCode,
/// Snapshot nodes are grouped based on their type, but no further
/// aggregation is performed. Leaf node in a treemap represents amount of
/// bytes occupied by objects of a specific type owned by a specific
/// [ProgramInfoNode].
objectType
}
const kindSymbol = 's';
const kindPath = 'p';
const symbolTypeGlobalText = 'T';
const symbolTypeGlobalInitializedData = 'D';
/// Convert the given AOT snapshot information file into a treemap object,
/// represented as a Map. Each node of the tree has one of the two schemas.
///
/// Leaf symbol nodes:
/// ```
/// {
/// 'k': kindSymbol,
/// 'n': /* name */,
/// 'lastPathElement': true,
/// 't': symbolTypeGlobalText | symbolTypeGlobalInitializedData,
/// 'value': /* symbol size */
/// }
/// ```
///
/// Path nodes:
/// ```
/// {
/// 'k': kindPath,
/// 'n': /* name */,
/// 'children': /* array of treemap nodes */
/// }
/// ```
///
/// If [inputJson] represents a V8 snapshot profile then [format] allows to
/// controls how individual [v8_profile.Snapshot] nodes are collapsed into
/// leaf treemap nodes (see [TreemapFormat] for more details).
///
/// By default chains of single child path nodes are collapsed into a single
/// path node, e.g.
/// `{k: 'p', n: 'a', children: [{k: 'p', n: 'b', children: [...]}]}`
/// becomes `{k: 'p', n: 'a/b', children: [...]}`. This behavior is controlled
/// by [collapseSingleChildPathNodes] parameter and can be switched off by
/// setting it to [false].
Map<String, dynamic> treemapFromJson(Object inputJson,
{TreemapFormat format = TreemapFormat.objectType,
bool collapseSingleChildPathNodes = true}) {
final root = {'n': '', 'children': {}, 'k': kindPath, 'maxDepth': 0};
if (v8_profile.Snapshot.isV8HeapSnapshot(inputJson)) {
_treemapFromSnapshot(root, v8_profile.Snapshot.fromJson(inputJson),
format: format);
} else {
final symbols = instruction_sizes.fromJson(inputJson);
for (var symbol in symbols) {
_addSymbol(root, _treePath(symbol), symbol.name.scrubbed, symbol.size);
}
}
return _flatten(root,
collapseSingleChildPathNodes: collapseSingleChildPathNodes);
}
/// Convert the given [ProgramInfo] object into a treemap in either
/// [TreemapFormat.collapsed] or [TreemapFormat.simplified] format.
///
/// See [treemapFromJson] for the schema of the returned map object.
Map<String, dynamic> treemapFromInfo(ProgramInfo info,
{TreemapFormat format = TreemapFormat.collapsed,
bool collapseSingleChildPathNodes = true}) {
final root = {'n': '', 'children': {}, 'k': kindPath, 'maxDepth': 0};
_treemapFromInfo(root, info, format: format);
return _flatten(root,
collapseSingleChildPathNodes: collapseSingleChildPathNodes);
}
void _treemapFromInfo(Map<String, dynamic> root, ProgramInfo info,
{TreemapFormat format = TreemapFormat.simplified}) {
if (format != TreemapFormat.collapsed && format != TreemapFormat.simplified) {
throw ArgumentError(
'can only build simplified or collapsed formats from the program info',
);
}
int cumulativeSize(ProgramInfoNode node) {
return (node.size ?? 0) +
node.children.values
.fold<int>(0, (sum, child) => sum + cumulativeSize(child));
}
void recurse(ProgramInfoNode node, String path, Map<String, dynamic> root,
TreemapFormat format) {
if (node.children.isEmpty ||
(node.type == NodeType.functionNode &&
format == TreemapFormat.simplified)) {
// For simple format we remove information about nested functions from
// the output.
_addSymbol(root, path, node.name, cumulativeSize(node));
return;
}
// Don't add package node names to the path because nested library nodes
// already contain package name.
if (node.type == NodeType.packageNode) {
_addSymbol(root, node.name, '<self>', node.size);
} else {
path = path != '' ? '$path/${node.name}' : node.name;
_addSymbol(root, path, '<self>', node.size);
}
for (var child in node.children.values) {
recurse(child, path, root, format);
}
}
_addSymbol(root, '', info.root.name, info.root.size);
for (var child in info.root.children.values) {
recurse(child, '', root, format);
}
}
void _treemapFromSnapshot(Map<String, dynamic> root, v8_profile.Snapshot snap,
{TreemapFormat format = TreemapFormat.objectType}) {
final info = v8_profile.toProgramInfo(snap);
// For collapsed and simple formats there is no need to traverse snapshot
// nodes. Just recurse into [ProgramInfo] structure instead.
if (format == TreemapFormat.collapsed || format == TreemapFormat.simplified) {
_treemapFromInfo(root, info, format: format);
return;
}
final ownerPathCache =
List<String>.filled(info.snapshotInfo.infoNodes.length, null);
ownerPathCache[info.root.id] = info.root.name;
String ownerPath(ProgramInfoNode n) {
return ownerPathCache[n.id] ??=
((n.parent != info.root) ? '${ownerPath(n.parent)}/${n.name}' : n.name);
}
final nameFormatter = _nameFormatters[format];
for (var node in snap.nodes) {
if (node.selfSize > 0) {
final owner = info.snapshotInfo.ownerOf(node);
final name = nameFormatter(node);
final path = ownerPath(owner);
final type = _isExecutableCode(node)
? symbolTypeGlobalText
: symbolTypeGlobalInitializedData;
_addSymbol(root, path, name, node.selfSize, symbolType: type);
}
}
}
/// Returns [true] if the given [node] represents executable machine code.
bool _isExecutableCode(v8_profile.Node node) =>
node.type == '(RO) Instructions';
/// A map of formatters which produce treemap node name to be used for the
/// given [v8_profile.Node].
final Map<TreemapFormat, String Function(v8_profile.Node)> _nameFormatters = {
TreemapFormat.dataAndCode: (n) => _isExecutableCode(n) ? '<code>' : '<data>',
TreemapFormat.objectType: (n) => '<${n.type}>',
};
/// Returns a /-separated path to the given symbol within the treemap.
String _treePath(instruction_sizes.SymbolInfo symbol) {
if (symbol.name.isStub) {
if (symbol.name.isAllocationStub) {
return '@stubs/allocation-stubs/${symbol.libraryUri}/${symbol.className}';
} else {
return '@stubs';
}
} else {
return '${symbol.libraryUri}/${symbol.className}';
}
}
/// Create a child with the given name within the given node or return
/// an existing child.
Map<String, dynamic> _addChild(
Map<String, dynamic> node, String kind, String name) {
return node['children'].putIfAbsent(name, () {
final n = <String, dynamic>{'n': name, 'k': kind};
if (kind != kindSymbol) {
n['children'] = {};
}
return n;
});
}
/// Add the given symbol to the tree.
void _addSymbol(Map<String, dynamic> root, String path, String name, int size,
{String symbolType = symbolTypeGlobalText}) {
if (size == null || size == 0) {
return;
}
var node = root;
var depth = 0;
if (path != '') {
final parts = partsForPath(path);
for (var part in parts) {
node = _addChild(node, kindPath, part);
depth++;
}
}
node['lastPathElement'] = true;
node = _addChild(node, kindSymbol, name);
node['t'] = symbolType;
node['value'] = (node['value'] ?? 0) + size;
depth += 1;
root['maxDepth'] = max<int>(root['maxDepth'], depth);
}
/// Convert all children entries from maps to lists.
Map<String, dynamic> _flatten(Map<String, dynamic> node,
{bool collapseSingleChildPathNodes = true}) {
dynamic children = node['children'];
if (children != null) {
children = children.values.map((dynamic v) => _flatten(v)).toList();
node['children'] = children;
if (collapseSingleChildPathNodes &&
children.length == 1 &&
children.first['k'] == kindPath) {
final singleChild = children.first;
singleChild['n'] = '${node['n']}/${singleChild['n']}';
return singleChild;
}
}
return node;
}