diff options
Diffstat (limited to 'devtools/shared/heapsnapshot')
| -rw-r--r-- | devtools/shared/heapsnapshot/CensusUtils.js | 489 | ||||
| -rw-r--r-- | devtools/shared/heapsnapshot/DominatorTreeNode.js | 336 | ||||
| -rw-r--r-- | devtools/shared/heapsnapshot/HeapAnalysesClient.js | 277 | ||||
| -rw-r--r-- | devtools/shared/heapsnapshot/HeapAnalysesWorker.js | 303 | ||||
| -rw-r--r-- | devtools/shared/heapsnapshot/HeapSnapshotFileUtils.js | 95 | ||||
| -rw-r--r-- | devtools/shared/heapsnapshot/census-tree-node.js | 748 | ||||
| -rw-r--r-- | devtools/shared/heapsnapshot/moz.build | 15 | ||||
| -rw-r--r-- | devtools/shared/heapsnapshot/shortest-paths.js | 91 |
8 files changed, 2354 insertions, 0 deletions
diff --git a/devtools/shared/heapsnapshot/CensusUtils.js b/devtools/shared/heapsnapshot/CensusUtils.js new file mode 100644 index 000000000..36bdd2d82 --- /dev/null +++ b/devtools/shared/heapsnapshot/CensusUtils.js @@ -0,0 +1,489 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ +"use strict"; + +const { flatten } = require("resource://devtools/shared/ThreadSafeDevToolsUtils.js"); + +/** * Visitor ****************************************************************/ + +/** + * A Visitor visits each node and edge of a census report tree as the census + * report is being traversed by `walk`. + */ +function Visitor() { } +exports.Visitor = Visitor; + +/** + * The `enter` method is called when a new sub-report is entered in traversal. + * + * @param {Object} breakdown + * The breakdown for the sub-report that is being entered by traversal. + * + * @param {Object} report + * The report generated by the given breakdown. + * + * @param {any} edge + * The edge leading to this sub-report. The edge is null if (but not iff! + * eg, null allocation stack edges) we are entering the root report. + */ +Visitor.prototype.enter = function (breakdown, report, edge) { }; + +/** + * The `exit` method is called when traversal of a sub-report has finished. + * + * @param {Object} breakdown + * The breakdown for the sub-report whose traversal has finished. + * + * @param {Object} report + * The report generated by the given breakdown. + * + * @param {any} edge + * The edge leading to this sub-report. The edge is null if (but not iff! + * eg, null allocation stack edges) we are entering the root report. + */ +Visitor.prototype.exit = function (breakdown, report, edge) { }; + +/** + * The `count` method is called when leaf nodes (reports whose breakdown is + * by: "count") in the report tree are encountered. + * + * @param {Object} breakdown + * The count breakdown for this report. + * + * @param {Object} report + * The report generated by a breakdown by "count". + * + * @param {any|null} edge + * The edge leading to this count report. The edge is null if we are + * entering the root report. + */ +Visitor.prototype.count = function (breakdown, report, edge) { }; + +/** * getReportEdges *********************************************************/ + +const EDGES = Object.create(null); + +EDGES.count = function (breakdown, report) { + return []; +}; + +EDGES.bucket = function (breakdown, report) { + return []; +}; + +EDGES.internalType = function (breakdown, report) { + return Object.keys(report).map(key => ({ + edge: key, + referent: report[key], + breakdown: breakdown.then + })); +}; + +EDGES.objectClass = function (breakdown, report) { + return Object.keys(report).map(key => ({ + edge: key, + referent: report[key], + breakdown: key === "other" ? breakdown.other : breakdown.then + })); +}; + +EDGES.coarseType = function (breakdown, report) { + return [ + { edge: "objects", referent: report.objects, breakdown: breakdown.objects }, + { edge: "scripts", referent: report.scripts, breakdown: breakdown.scripts }, + { edge: "strings", referent: report.strings, breakdown: breakdown.strings }, + { edge: "other", referent: report.other, breakdown: breakdown.other }, + ]; +}; + +EDGES.allocationStack = function (breakdown, report) { + const edges = []; + report.forEach((value, key) => { + edges.push({ + edge: key, + referent: value, + breakdown: key === "noStack" ? breakdown.noStack : breakdown.then + }); + }); + return edges; +}; + +EDGES.filename = function (breakdown, report) { + return Object.keys(report).map(key => ({ + edge: key, + referent: report[key], + breakdown: key === "noFilename" ? breakdown.noFilename : breakdown.then + })); +}; + +/** + * Get the set of outgoing edges from `report` as specified by the given + * breakdown. + * + * @param {Object} breakdown + * The census breakdown. + * + * @param {Object} report + * The census report. + */ +function getReportEdges(breakdown, report) { + return EDGES[breakdown.by](breakdown, report); +} +exports.getReportEdges = getReportEdges; + +/** * walk *******************************************************************/ + +function recursiveWalk(breakdown, edge, report, visitor) { + if (breakdown.by === "count") { + visitor.enter(breakdown, report, edge); + visitor.count(breakdown, report, edge); + visitor.exit(breakdown, report, edge); + } else { + visitor.enter(breakdown, report, edge); + for (let { edge, referent, breakdown: subBreakdown } of getReportEdges(breakdown, report)) { + recursiveWalk(subBreakdown, edge, referent, visitor); + } + visitor.exit(breakdown, report, edge); + } +} + +/** + * Walk the given `report` that was generated by taking a census with the + * specified `breakdown`. + * + * @param {Object} breakdown + * The census breakdown. + * + * @param {Object} report + * The census report. + * + * @param {Visitor} visitor + * The Visitor instance to call into while traversing. + */ +function walk(breakdown, report, visitor) { + recursiveWalk(breakdown, null, report, visitor); +} +exports.walk = walk; + +/** * diff *******************************************************************/ + +/** + * Return true if the object is a Map, false otherwise. Works with Map objects + * from other globals, unlike `instanceof`. + * + * @returns {Boolean} + */ +function isMap(obj) { + return Object.prototype.toString.call(obj) === "[object Map]"; +} + +/** + * A Visitor for computing the difference between the census report being + * traversed and the given other census. + * + * @param {Object} otherCensus + * The other census report. + */ +function DiffVisitor(otherCensus) { + // The other census we are comparing against. + this._otherCensus = otherCensus; + + // The total bytes and count of the basis census we are traversing. + this._totalBytes = 0; + this._totalCount = 0; + + // Stack maintaining the current corresponding sub-report for the other + // census we are comparing against. + this._otherCensusStack = []; + + // Stack maintaining the set of edges visited at each sub-report. + this._edgesVisited = [new Set()]; + + // The final delta census. Valid only after traversal. + this._results = null; + + // Stack maintaining the results corresponding to each sub-report we are + // currently traversing. + this._resultsStack = []; +} + +DiffVisitor.prototype = Object.create(Visitor.prototype); + +/** + * Given a report and an outgoing edge, get the edge's referent. + */ +DiffVisitor.prototype._get = function (report, edge) { + if (!report) { + return undefined; + } + return isMap(report) ? report.get(edge) : report[edge]; +}; + +/** + * Given a report, an outgoing edge, and a value, set the edge's referent to + * the given value. + */ +DiffVisitor.prototype._set = function (report, edge, val) { + if (isMap(report)) { + report.set(edge, val); + } else { + report[edge] = val; + } +}; + +/** + * @overrides Visitor.prototype.enter + */ +DiffVisitor.prototype.enter = function (breakdown, report, edge) { + const isFirstTimeEntering = this._results === null; + + const newResults = breakdown.by === "allocationStack" ? new Map() : {}; + let newOther; + + if (!this._results) { + // This is the first time we have entered a sub-report. + this._results = newResults; + newOther = this._otherCensus; + } else { + const topResults = this._resultsStack[this._resultsStack.length - 1]; + this._set(topResults, edge, newResults); + + const topOther = this._otherCensusStack[this._otherCensusStack.length - 1]; + newOther = this._get(topOther, edge); + } + + this._resultsStack.push(newResults); + this._otherCensusStack.push(newOther); + + const visited = this._edgesVisited[this._edgesVisited.length - 1]; + visited.add(edge); + this._edgesVisited.push(new Set()); +}; + +/** + * @overrides Visitor.prototype.exit + */ +DiffVisitor.prototype.exit = function (breakdown, report, edge) { + // Find all the edges in the other census report that were not traversed and + // add them to the results directly. + const other = this._otherCensusStack[this._otherCensusStack.length - 1]; + if (other) { + const visited = this._edgesVisited[this._edgesVisited.length - 1]; + const unvisited = getReportEdges(breakdown, other) + .map(e => e.edge) + .filter(e => !visited.has(e)); + const results = this._resultsStack[this._resultsStack.length - 1]; + for (let edge of unvisited) { + this._set(results, edge, this._get(other, edge)); + } + } + + this._otherCensusStack.pop(); + this._resultsStack.pop(); + this._edgesVisited.pop(); +}; + +/** + * @overrides Visitor.prototype.count + */ +DiffVisitor.prototype.count = function (breakdown, report, edge) { + const other = this._otherCensusStack[this._otherCensusStack.length - 1]; + const results = this._resultsStack[this._resultsStack.length - 1]; + + if (breakdown.count) { + this._totalCount += report.count; + } + if (breakdown.bytes) { + this._totalBytes += report.bytes; + } + + if (other) { + if (breakdown.count) { + results.count = other.count - report.count; + } + if (breakdown.bytes) { + results.bytes = other.bytes - report.bytes; + } + } else { + if (breakdown.count) { + results.count = -report.count; + } + if (breakdown.bytes) { + results.bytes = -report.bytes; + } + } +}; + +const basisTotalBytes = exports.basisTotalBytes = Symbol("basisTotalBytes"); +const basisTotalCount = exports.basisTotalCount = Symbol("basisTotalCount"); + +/** + * Get the resulting report of the difference between the traversed census + * report and the other census report. + * + * @returns {Object} + * The delta census report. + */ +DiffVisitor.prototype.results = function () { + if (!this._results) { + throw new Error("Attempt to get results before computing diff!"); + } + + if (this._resultsStack.length) { + throw new Error("Attempt to get results while still computing diff!"); + } + + this._results[basisTotalBytes] = this._totalBytes; + this._results[basisTotalCount] = this._totalCount; + + return this._results; +}; + +/** + * Take the difference between two censuses. The resulting delta report + * contains the number/size of things that are in the `endCensus` that are not + * in the `startCensus`. + * + * @param {Object} breakdown + * The breakdown used to generate both census reports. + * + * @param {Object} startCensus + * The first census report. + * + * @param {Object} endCensus + * The second census report. + * + * @returns {Object} + * A delta report mirroring the structure of the two census reports (as + * specified by the given breakdown). Has two additional properties: + * - {Number} basisTotalBytes: the total number of bytes in the start + * census. + * - {Number} basisTotalCount: the total count in the start census. + */ +function diff(breakdown, startCensus, endCensus) { + const visitor = new DiffVisitor(endCensus); + walk(breakdown, startCensus, visitor); + return visitor.results(); +} +exports.diff = diff; + +/** + * Creates a hash map mapping node IDs to its parent node. + * + * @param {CensusTreeNode} node + * @param {Object<number, TreeNode>} aggregator + * + * @return {Object<number, TreeNode>} + */ +const createParentMap = exports.createParentMap = function (node, + getId = node => node.id, + aggregator = Object.create(null)) { + if (node.children) { + for (let i = 0, length = node.children.length; i < length; i++) { + const child = node.children[i]; + aggregator[getId(child)] = node; + createParentMap(child, getId, aggregator); + } + } + + return aggregator; +}; + +const BUCKET = Object.freeze({ by: "bucket" }); + +/** + * Convert a breakdown whose leaves are { by: "count" } to an identical + * breakdown, except with { by: "bucket" } leaves. + * + * @param {Object} breakdown + * @returns {Object} + */ +exports.countToBucketBreakdown = function (breakdown) { + if (typeof breakdown !== "object" || !breakdown) { + return breakdown; + } + + if (breakdown.by === "count") { + return BUCKET; + } + + const keys = Object.keys(breakdown); + const vals = keys.reduce((vs, k) => { + vs.push(exports.countToBucketBreakdown(breakdown[k])); + return vs; + }, []); + + const result = {}; + for (let i = 0, length = keys.length; i < length; i++) { + result[keys[i]] = vals[i]; + } + + return Object.freeze(result); +}; + +/** + * A Visitor for finding report leaves by their DFS index. + */ +function GetLeavesVisitor(targetIndices) { + this._index = -1; + this._targetIndices = targetIndices; + this._leaves = []; +} + +GetLeavesVisitor.prototype = Object.create(Visitor.prototype); + +/** + * @overrides Visitor.prototype.enter + */ +GetLeavesVisitor.prototype.enter = function (breakdown, report, edge) { + this._index++; + if (this._targetIndices.has(this._index)) { + this._leaves.push(report); + } +}; + +/** + * Get the accumulated report leaves after traversal. + */ +GetLeavesVisitor.prototype.leaves = function () { + if (this._index === -1) { + throw new Error("Attempt to call `leaves` before traversing report!"); + } + return this._leaves; +}; + +/** + * Given a set of indices of leaves in a pre-order depth-first traversal of the + * given census report, return the leaves. + * + * @param {Set<Number>} indices + * @param {Object} breakdown + * @param {Object} report + * + * @returns {Array<Object>} + */ +exports.getReportLeaves = function (indices, breakdown, report) { + const visitor = new GetLeavesVisitor(indices); + walk(breakdown, report, visitor); + return visitor.leaves(); +}; + +/** + * Get a list of the individual node IDs that belong to the census report leaves + * of the given indices. + * + * @param {Set<Number>} indices + * @param {Object} breakdown + * @param {HeapSnapshot} snapshot + * + * @returns {Array<NodeId>} + */ +exports.getCensusIndividuals = function (indices, countBreakdown, snapshot) { + const bucketBreakdown = exports.countToBucketBreakdown(countBreakdown); + const bucketReport = snapshot.takeCensus({ breakdown: bucketBreakdown }); + const buckets = exports.getReportLeaves(indices, + bucketBreakdown, + bucketReport); + return flatten(buckets); +}; diff --git a/devtools/shared/heapsnapshot/DominatorTreeNode.js b/devtools/shared/heapsnapshot/DominatorTreeNode.js new file mode 100644 index 000000000..13a847fd0 --- /dev/null +++ b/devtools/shared/heapsnapshot/DominatorTreeNode.js @@ -0,0 +1,336 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ +"use strict"; + +const { immutableUpdate } = require("resource://devtools/shared/ThreadSafeDevToolsUtils.js"); +const { Visitor, walk } = require("resource://devtools/shared/heapsnapshot/CensusUtils.js"); +const { deduplicatePaths } = require("resource://devtools/shared/heapsnapshot/shortest-paths"); + +const DEFAULT_MAX_DEPTH = 4; +const DEFAULT_MAX_SIBLINGS = 15; +const DEFAULT_MAX_NUM_PATHS = 5; + +/** + * A single node in a dominator tree. + * + * @param {NodeId} nodeId + * @param {NodeSize} retainedSize + */ +function DominatorTreeNode(nodeId, label, shallowSize, retainedSize) { + // The id of this node. + this.nodeId = nodeId; + + // The label structure generated by describing the given node. + this.label = label; + + // The shallow size of this node. + this.shallowSize = shallowSize; + + // The retained size of this node. + this.retainedSize = retainedSize; + + // The id of this node's parent or undefined if this node is the root. + this.parentId = undefined; + + // An array of immediately dominated child `DominatorTreeNode`s, or undefined. + this.children = undefined; + + // An object of the form returned by `deduplicatePaths`, encoding the set of + // the N shortest retaining paths for this node as a graph. + this.shortestPaths = undefined; + + // True iff the `children` property does not contain every immediately + // dominated node. + // + // * If children is an array and this property is true: the array does not + // contain the complete set of immediately dominated children. + // * If children is an array and this property is false: the array contains + // the complete set of immediately dominated children. + // * If children is undefined and this property is true: there exist + // immediately dominated children for this node, but they have not been + // loaded yet. + // * If children is undefined and this property is false: this node does not + // dominate any others and therefore has no children. + this.moreChildrenAvailable = true; +} + +DominatorTreeNode.prototype = null; + +module.exports = DominatorTreeNode; + +/** + * Add `child` to the `parent`'s set of children. + * + * @param {DominatorTreeNode} parent + * @param {DominatorTreeNode} child + */ +DominatorTreeNode.addChild = function (parent, child) { + if (parent.children === undefined) { + parent.children = []; + } + + parent.children.push(child); + child.parentId = parent.nodeId; +}; + +/** + * A Visitor that is used to generate a label for a node in the heap snapshot + * and get its shallow size as well while we are at it. + */ +function LabelAndShallowSizeVisitor() { + // As we walk the description, we accumulate edges in this array. + this._labelPieces = []; + + // Once we reach the non-zero count leaf node in the description, we move the + // labelPieces here to signify that we no longer need to accumulate edges. + this._label = undefined; + + // Once we reach the non-zero count leaf node in the description, we grab the + // shallow size and place it here. + this._shallowSize = 0; +} + +DominatorTreeNode.LabelAndShallowSizeVisitor = LabelAndShallowSizeVisitor; + +LabelAndShallowSizeVisitor.prototype = Object.create(Visitor); + +/** + * @overrides Visitor.prototype.enter + */ +LabelAndShallowSizeVisitor.prototype.enter = function (breakdown, report, edge) { + if (this._labelPieces && edge) { + this._labelPieces.push(edge); + } +}; + +/** + * @overrides Visitor.prototype.exit + */ +LabelAndShallowSizeVisitor.prototype.exit = function (breakdown, report, edge) { + if (this._labelPieces && edge) { + this._labelPieces.pop(); + } +}; + +/** + * @overrides Visitor.prototype.count + */ +LabelAndShallowSizeVisitor.prototype.count = function (breakdown, report, edge) { + if (report.count === 0) { + return; + } + + this._label = this._labelPieces; + this._labelPieces = undefined; + + this._shallowSize = report.bytes; +}; + +/** + * Get the generated label structure accumulated by this visitor. + * + * @returns {Object} + */ +LabelAndShallowSizeVisitor.prototype.label = function () { + return this._label; +}; + +/** + * Get the shallow size of the node this visitor visited. + * + * @returns {Number} + */ +LabelAndShallowSizeVisitor.prototype.shallowSize = function () { + return this._shallowSize; +}; + +/** + * Generate a label structure for the node with the given id and grab its + * shallow size. + * + * What is a "label" structure? HeapSnapshot.describeNode essentially takes a + * census of a single node rather than the whole heap graph. The resulting + * report has only one count leaf that is non-zero. The label structure is the + * path in this report from the root to the non-zero count leaf. + * + * @param {Number} nodeId + * @param {HeapSnapshot} snapshot + * @param {Object} breakdown + * + * @returns {Object} + * An object with the following properties: + * - {Number} shallowSize + * - {Object} label + */ +DominatorTreeNode.getLabelAndShallowSize = function (nodeId, + snapshot, + breakdown) { + const description = snapshot.describeNode(breakdown, nodeId); + + const visitor = new LabelAndShallowSizeVisitor(); + walk(breakdown, description, visitor); + + return { + label: visitor.label(), + shallowSize: visitor.shallowSize(), + }; +}; + +/** + * Do a partial traversal of the given dominator tree and convert it into a tree + * of `DominatorTreeNode`s. Dominator trees have a node for every node in the + * snapshot's heap graph, so we must not allocate a JS object for every node. It + * would be way too many and the node count is effectively unbounded. + * + * Go no deeper down the tree than `maxDepth` and only consider at most + * `maxSiblings` within any single node's children. + * + * @param {DominatorTree} dominatorTree + * @param {HeapSnapshot} snapshot + * @param {Object} breakdown + * @param {Number} maxDepth + * @param {Number} maxSiblings + * + * @returns {DominatorTreeNode} + */ +DominatorTreeNode.partialTraversal = function (dominatorTree, + snapshot, + breakdown, + maxDepth = DEFAULT_MAX_DEPTH, + maxSiblings = DEFAULT_MAX_SIBLINGS) { + function dfs(nodeId, depth) { + const { label, shallowSize } = + DominatorTreeNode.getLabelAndShallowSize(nodeId, snapshot, breakdown); + const retainedSize = dominatorTree.getRetainedSize(nodeId); + const node = new DominatorTreeNode(nodeId, label, shallowSize, retainedSize); + const childNodeIds = dominatorTree.getImmediatelyDominated(nodeId); + + const newDepth = depth + 1; + if (newDepth < maxDepth) { + const endIdx = Math.min(childNodeIds.length, maxSiblings); + for (let i = 0; i < endIdx; i++) { + DominatorTreeNode.addChild(node, dfs(childNodeIds[i], newDepth)); + } + node.moreChildrenAvailable = endIdx < childNodeIds.length; + } else { + node.moreChildrenAvailable = childNodeIds.length > 0; + } + + return node; + } + + return dfs(dominatorTree.root, 0); +}; + +/** + * Insert more children into the given (partially complete) dominator tree. + * + * The tree is updated in an immutable and persistent manner: a new tree is + * returned, but all unmodified subtrees (which is most) are shared with the + * original tree. Only the modified nodes are re-allocated. + * + * @param {DominatorTreeNode} tree + * @param {Array<NodeId>} path + * @param {Array<DominatorTreeNode>} newChildren + * @param {Boolean} moreChildrenAvailable + * + * @returns {DominatorTreeNode} + */ +DominatorTreeNode.insert = function (tree, path, newChildren, moreChildrenAvailable) { + function insert(tree, i) { + if (tree.nodeId !== path[i]) { + return tree; + } + + if (i == path.length - 1) { + return immutableUpdate(tree, { + children: (tree.children || []).concat(newChildren), + moreChildrenAvailable, + }); + } + + return tree.children + ? immutableUpdate(tree, { + children: tree.children.map(c => insert(c, i + 1)) + }) + : tree; + } + + return insert(tree, 0); +}; + +/** + * Get the new canonical node with the given `id` in `tree` that exists along + * `path`. If there is no such node along `path`, return null. + * + * This is useful if we have a reference to a now-outdated DominatorTreeNode due + * to a recent call to DominatorTreeNode.insert and want to get the up-to-date + * version. We don't have to walk the whole tree: if there is an updated version + * of the node then it *must* be along the path. + * + * @param {NodeId} id + * @param {DominatorTreeNode} tree + * @param {Array<NodeId>} path + * + * @returns {DominatorTreeNode|null} + */ +DominatorTreeNode.getNodeByIdAlongPath = function (id, tree, path) { + function find(node, i) { + if (!node || node.nodeId !== path[i]) { + return null; + } + + if (node.nodeId === id) { + return node; + } + + if (i === path.length - 1 || !node.children) { + return null; + } + + const nextId = path[i + 1]; + return find(node.children.find(c => c.nodeId === nextId), i + 1); + } + + return find(tree, 0); +}; + +/** + * Find the shortest retaining paths for the given set of DominatorTreeNodes, + * and populate each node's `shortestPaths` property with them in place. + * + * @param {HeapSnapshot} snapshot + * @param {Object} breakdown + * @param {NodeId} start + * @param {Array<DominatorTreeNode>} treeNodes + * @param {Number} maxNumPaths + */ +DominatorTreeNode.attachShortestPaths = function (snapshot, + breakdown, + start, + treeNodes, + maxNumPaths = DEFAULT_MAX_NUM_PATHS) { + const idToTreeNode = new Map(); + const targets = []; + for (let node of treeNodes) { + const id = node.nodeId; + idToTreeNode.set(id, node); + targets.push(id); + } + + const shortestPaths = snapshot.computeShortestPaths(start, + targets, + maxNumPaths); + + for (let [target, paths] of shortestPaths) { + const deduped = deduplicatePaths(target, paths); + deduped.nodes = deduped.nodes.map(id => { + const { label } = + DominatorTreeNode.getLabelAndShallowSize(id, snapshot, breakdown); + return { id, label }; + }); + + idToTreeNode.get(target).shortestPaths = deduped; + } +}; diff --git a/devtools/shared/heapsnapshot/HeapAnalysesClient.js b/devtools/shared/heapsnapshot/HeapAnalysesClient.js new file mode 100644 index 000000000..98601a2b1 --- /dev/null +++ b/devtools/shared/heapsnapshot/HeapAnalysesClient.js @@ -0,0 +1,277 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +"use strict"; + +const DevToolsUtils = require("devtools/shared/DevToolsUtils"); +const { DevToolsWorker } = require("devtools/shared/worker/worker"); + +const WORKER_URL = + "resource://devtools/shared/heapsnapshot/HeapAnalysesWorker.js"; +var workerCounter = 0; + +/** + * A HeapAnalysesClient instance provides a developer-friendly interface for + * interacting with a HeapAnalysesWorker. This enables users to be ignorant of + * the message passing protocol used to communicate with the worker. The + * HeapAnalysesClient owns the worker, and terminating the worker is done by + * terminating the client (see the `destroy` method). + */ +const HeapAnalysesClient = module.exports = function () { + this._worker = new DevToolsWorker(WORKER_URL, { + name: `HeapAnalyses-${workerCounter++}`, + verbose: DevToolsUtils.dumpv.wantVerbose + }); +}; + +/** + * Destroy the worker, causing it to release its resources (such as heap + * snapshots it has deserialized and read into memory). The client is no longer + * usable after calling this method. + */ +HeapAnalysesClient.prototype.destroy = function () { + this._worker.destroy(); + this._worker = null; +}; + +/** + * Tell the worker to read into memory the heap snapshot at the given file + * path. This is a prerequisite for asking the worker to perform various + * analyses on a heap snapshot. + * + * @param {String} snapshotFilePath + * + * @returns Promise + * The promise is fulfilled if the heap snapshot is successfully + * deserialized and read into memory. The promise is rejected if that + * does not happen, eg due to a bad file path or malformed heap + * snapshot file. + */ +HeapAnalysesClient.prototype.readHeapSnapshot = function (snapshotFilePath) { + return this._worker.performTask("readHeapSnapshot", { snapshotFilePath }); +}; + +/** + * Tell the worker to delete all references to the snapshot and dominator trees + * linked to the provided snapshot file path. + * + * @param {String} snapshotFilePath + * @return Promise<undefined> + */ +HeapAnalysesClient.prototype.deleteHeapSnapshot = function (snapshotFilePath) { + return this._worker.performTask("deleteHeapSnapshot", { snapshotFilePath }); +}; + +/** + * Request the creation time given a snapshot file path. Returns `null` + * if snapshot does not exist. + * + * @param {String} snapshotFilePath + * The path to the snapshot. + * @return {Number?} + * The unix timestamp of the creation time of the snapshot, or null if + * snapshot does not exist. + */ +HeapAnalysesClient.prototype.getCreationTime = function (snapshotFilePath) { + return this._worker.performTask("getCreationTime", snapshotFilePath); +}; + +/** * Censuses *****************************************************************/ + +/** + * Ask the worker to perform a census analysis on the heap snapshot with the + * given path. The heap snapshot at the given path must have already been read + * into memory by the worker (see `readHeapSnapshot`). + * + * @param {String} snapshotFilePath + * + * @param {Object} censusOptions + * A structured-cloneable object specifying the requested census's + * breakdown. See the "takeCensus" section of + * `js/src/doc/Debugger/Debugger.Memory.md` for detailed documentation. + * + * @param {Object} requestOptions + * An object specifying options of this worker request. + * - {Boolean} asTreeNode + * Whether or not the census is returned as a CensusTreeNode, + * or just a breakdown report. Defaults to false. + * @see `devtools/shared/heapsnapshot/census-tree-node.js` + * - {Boolean} asInvertedTreeNode + * Whether or not the census is returned as an inverted + * CensusTreeNode. Defaults to false. + * - {String} filter + * A filter string to prune the resulting tree with. Only applies if + * either asTreeNode or asInvertedTreeNode is true. + * + * @returns Promise<Object> + * An object with the following properties: + * - report: + * The report generated by the given census breakdown, or a + * CensusTreeNode generated by the given census breakdown if + * `asTreeNode` is true. + * - parentMap: + * The result of calling CensusUtils.createParentMap on the generated + * report. Only exists if asTreeNode or asInvertedTreeNode are set. + */ +HeapAnalysesClient.prototype.takeCensus = function (snapshotFilePath, + censusOptions, + requestOptions = {}) { + return this._worker.performTask("takeCensus", { + snapshotFilePath, + censusOptions, + requestOptions, + }); +}; + +/** + * Get the individual nodes that correspond to the given census report leaf + * indices. + * + * @param {Object} opts + * An object with the following properties: + * - {DominatorTreeId} dominatorTreeId: The id of the dominator tree. + * - {Set<Number>} indices: The indices of the census report leaves we + * would like to get the individuals for. + * - {Object} censusBreakdown: The breakdown used to generate the census. + * - {Object} labelBreakdown: The breakdown we would like to use when + * labeling the resulting nodes. + * - {Number} maxRetainingPaths: The maximum number of retaining paths to + * compute for each node. + * - {Number} maxIndividuals: The maximum number of individual nodes to + * return. + * + * @returns {Promise<Object>} + * A promise of an object with the following properties: + * - {Array<DominatorTreeNode>} nodes: An array of `DominatorTreeNode`s + * with their shortest paths attached, and without any dominator tree + * child/parent information attached. The results are sorted by + * retained size. + * + */ +HeapAnalysesClient.prototype.getCensusIndividuals = function (opts) { + return this._worker.performTask("getCensusIndividuals", opts); +}; + +/** + * Request that the worker take a census on the heap snapshots with the given + * paths and then return the difference between them. Both heap snapshots must + * have already been read into memory by the worker (see `readHeapSnapshot`). + * + * @param {String} firstSnapshotFilePath + * The first snapshot file path. + * + * @param {String} secondSnapshotFilePath + * The second snapshot file path. + * + * @param {Object} censusOptions + * A structured-cloneable object specifying the requested census's + * breakdown. See the "takeCensus" section of + * `js/src/doc/Debugger/Debugger.Memory.md` for detailed documentation. + * + * @param {Object} requestOptions + * An object specifying options for this request. + * - {Boolean} asTreeNode + * Whether the resulting delta report should be converted to a census + * tree node before returned. Defaults to false. + * - {Boolean} asInvertedTreeNode + * Whether or not the census is returned as an inverted + * CensusTreeNode. Defaults to false. + * - {String} filter + * A filter string to prune the resulting tree with. Only applies if + * either asTreeNode or asInvertedTreeNode is true. + * + * @returns Promise<Object> + * - delta: + * The delta report generated by diffing the two census reports, or a + * CensusTreeNode generated from the delta report if + * `requestOptions.asTreeNode` was true. + * - parentMap: + * The result of calling CensusUtils.createParentMap on the generated + * delta. Only exists if asTreeNode or asInvertedTreeNode are set. + */ +HeapAnalysesClient.prototype.takeCensusDiff = function (firstSnapshotFilePath, + secondSnapshotFilePath, + censusOptions, + requestOptions = {}) { + return this._worker.performTask("takeCensusDiff", { + firstSnapshotFilePath, + secondSnapshotFilePath, + censusOptions, + requestOptions + }); +}; + +/** * Dominator Trees **********************************************************/ + +/** + * Compute the dominator tree of the heap snapshot loaded from the given file + * path. Returns the id of the computed dominator tree. + * + * @param {String} snapshotFilePath + * + * @returns {Promise<DominatorTreeId>} + */ +HeapAnalysesClient.prototype.computeDominatorTree = function (snapshotFilePath) { + return this._worker.performTask("computeDominatorTree", snapshotFilePath); +}; + +/** + * Get the initial, partial view of the dominator tree with the given id. + * + * @param {Object} opts + * An object specifying options for this request. + * - {DominatorTreeId} dominatorTreeId + * The id of the dominator tree. + * - {Object} breakdown + * The breakdown used to generate node labels. + * - {Number} maxDepth + * The maximum depth to traverse down the tree to create this initial + * view. + * - {Number} maxSiblings + * The maximum number of siblings to visit within each traversed node's + * children. + * - {Number} maxRetainingPaths + * The maximum number of retaining paths to find for each node. + * + * @returns {Promise<DominatorTreeNode>} + */ +HeapAnalysesClient.prototype.getDominatorTree = function (opts) { + return this._worker.performTask("getDominatorTree", opts); +}; + +/** + * Get a subset of a nodes children in the dominator tree. + * + * @param {Object} opts + * An object specifying options for this request. + * - {DominatorTreeId} dominatorTreeId + * The id of the dominator tree. + * - {NodeId} nodeId + * The id of the node whose children are being found. + * - {Object} breakdown + * The breakdown used to generate node labels. + * - {Number} startIndex + * The starting index within the full set of immediately dominated + * children of the children being requested. Children are always sorted + * by greatest to least retained size. + * - {Number} maxCount + * The maximum number of children to return. + * - {Number} maxRetainingPaths + * The maximum number of retaining paths to find for each node. + * + * @returns {Promise<Object>} + * A promise of an object with the following properties: + * - {Array<DominatorTreeNode>} nodes + * The requested nodes that are immediately dominated by the node + * identified by `opts.nodeId`. + * - {Boolean} moreChildrenAvailable + * True iff there are more children available after the returned + * nodes. + * - {Array<NodeId>} path + * The path through the tree from the root to these node's parent, eg + * [root's id, child of root's id, child of child of root's id, ..., `nodeId`]. + */ +HeapAnalysesClient.prototype.getImmediatelyDominated = function (opts) { + return this._worker.performTask("getImmediatelyDominated", opts); +}; diff --git a/devtools/shared/heapsnapshot/HeapAnalysesWorker.js b/devtools/shared/heapsnapshot/HeapAnalysesWorker.js new file mode 100644 index 000000000..d07d67f80 --- /dev/null +++ b/devtools/shared/heapsnapshot/HeapAnalysesWorker.js @@ -0,0 +1,303 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ +/* global ThreadSafeChromeUtils*/ + +// This is a worker which reads offline heap snapshots into memory and performs +// heavyweight analyses on them without blocking the main thread. A +// HeapAnalysesWorker is owned and communicated with by a HeapAnalysesClient +// instance. See HeapAnalysesClient.js. + +"use strict"; + +importScripts("resource://gre/modules/workers/require.js"); +importScripts("resource://devtools/shared/worker/helper.js"); +const { censusReportToCensusTreeNode } = require("resource://devtools/shared/heapsnapshot/census-tree-node.js"); +const DominatorTreeNode = require("resource://devtools/shared/heapsnapshot/DominatorTreeNode.js"); +const CensusUtils = require("resource://devtools/shared/heapsnapshot/CensusUtils.js"); + +const DEFAULT_START_INDEX = 0; +const DEFAULT_MAX_COUNT = 50; + +/** + * The set of HeapSnapshot instances this worker has read into memory. Keyed by + * snapshot file path. + */ +const snapshots = Object.create(null); + +/** + * The set of `DominatorTree`s that have been computed, mapped by their id (aka + * the index into this array). + * + * @see /dom/webidl/DominatorTree.webidl + */ +const dominatorTrees = []; + +/** + * The i^th HeapSnapshot in this array is the snapshot used to generate the i^th + * dominator tree in `dominatorTrees` above. This lets us map from a dominator + * tree id to the snapshot it came from. + */ +const dominatorTreeSnapshots = []; + +/** + * @see HeapAnalysesClient.prototype.readHeapSnapshot + */ +workerHelper.createTask(self, "readHeapSnapshot", ({ snapshotFilePath }) => { + snapshots[snapshotFilePath] = + ThreadSafeChromeUtils.readHeapSnapshot(snapshotFilePath); + return true; +}); + +/** + * @see HeapAnalysesClient.prototype.deleteHeapSnapshot + */ +workerHelper.createTask(self, "deleteHeapSnapshot", ({ snapshotFilePath }) => { + let snapshot = snapshots[snapshotFilePath]; + if (!snapshot) { + throw new Error(`No known heap snapshot for '${snapshotFilePath}'`); + } + + snapshots[snapshotFilePath] = undefined; + + let dominatorTreeId = dominatorTreeSnapshots.indexOf(snapshot); + if (dominatorTreeId != -1) { + dominatorTreeSnapshots[dominatorTreeId] = undefined; + dominatorTrees[dominatorTreeId] = undefined; + } +}); + +/** + * @see HeapAnalysesClient.prototype.takeCensus + */ +workerHelper.createTask(self, "takeCensus", ({ snapshotFilePath, censusOptions, requestOptions }) => { + if (!snapshots[snapshotFilePath]) { + throw new Error(`No known heap snapshot for '${snapshotFilePath}'`); + } + + let report = snapshots[snapshotFilePath].takeCensus(censusOptions); + let parentMap; + + if (requestOptions.asTreeNode || requestOptions.asInvertedTreeNode) { + const opts = { filter: requestOptions.filter || null }; + if (requestOptions.asInvertedTreeNode) { + opts.invert = true; + } + report = censusReportToCensusTreeNode(censusOptions.breakdown, report, opts); + parentMap = CensusUtils.createParentMap(report); + } + + return { report, parentMap }; +}); + +/** + * @see HeapAnalysesClient.prototype.getCensusIndividuals + */ +workerHelper.createTask(self, "getCensusIndividuals", request => { + const { + dominatorTreeId, + indices, + censusBreakdown, + labelBreakdown, + maxRetainingPaths, + maxIndividuals, + } = request; + + const dominatorTree = dominatorTrees[dominatorTreeId]; + if (!dominatorTree) { + throw new Error( + `There does not exist a DominatorTree with the id ${dominatorTreeId}`); + } + + const snapshot = dominatorTreeSnapshots[dominatorTreeId]; + const nodeIds = CensusUtils.getCensusIndividuals(indices, censusBreakdown, snapshot); + + const nodes = nodeIds + .sort((a, b) => dominatorTree.getRetainedSize(b) - dominatorTree.getRetainedSize(a)) + .slice(0, maxIndividuals) + .map(id => { + const { label, shallowSize } = + DominatorTreeNode.getLabelAndShallowSize(id, snapshot, labelBreakdown); + const retainedSize = dominatorTree.getRetainedSize(id); + const node = new DominatorTreeNode(id, label, shallowSize, retainedSize); + node.moreChildrenAvailable = false; + return node; + }); + + DominatorTreeNode.attachShortestPaths(snapshot, + labelBreakdown, + dominatorTree.root, + nodes, + maxRetainingPaths); + + return { nodes }; +}); + +/** + * @see HeapAnalysesClient.prototype.takeCensusDiff + */ +workerHelper.createTask(self, "takeCensusDiff", request => { + const { + firstSnapshotFilePath, + secondSnapshotFilePath, + censusOptions, + requestOptions + } = request; + + if (!snapshots[firstSnapshotFilePath]) { + throw new Error(`No known heap snapshot for '${firstSnapshotFilePath}'`); + } + + if (!snapshots[secondSnapshotFilePath]) { + throw new Error(`No known heap snapshot for '${secondSnapshotFilePath}'`); + } + + const first = snapshots[firstSnapshotFilePath].takeCensus(censusOptions); + const second = snapshots[secondSnapshotFilePath].takeCensus(censusOptions); + let delta = CensusUtils.diff(censusOptions.breakdown, first, second); + let parentMap; + + if (requestOptions.asTreeNode || requestOptions.asInvertedTreeNode) { + const opts = { filter: requestOptions.filter || null }; + if (requestOptions.asInvertedTreeNode) { + opts.invert = true; + } + delta = censusReportToCensusTreeNode(censusOptions.breakdown, delta, opts); + parentMap = CensusUtils.createParentMap(delta); + } + + return { delta, parentMap }; +}); + +/** + * @see HeapAnalysesClient.prototype.getCreationTime + */ +workerHelper.createTask(self, "getCreationTime", snapshotFilePath => { + if (!snapshots[snapshotFilePath]) { + throw new Error(`No known heap snapshot for '${snapshotFilePath}'`); + } + return snapshots[snapshotFilePath].creationTime; +}); + +/** + * @see HeapAnalysesClient.prototype.computeDominatorTree + */ +workerHelper.createTask(self, "computeDominatorTree", snapshotFilePath => { + const snapshot = snapshots[snapshotFilePath]; + if (!snapshot) { + throw new Error(`No known heap snapshot for '${snapshotFilePath}'`); + } + + const id = dominatorTrees.length; + dominatorTrees.push(snapshot.computeDominatorTree()); + dominatorTreeSnapshots.push(snapshot); + return id; +}); + +/** + * @see HeapAnalysesClient.prototype.getDominatorTree + */ +workerHelper.createTask(self, "getDominatorTree", request => { + const { + dominatorTreeId, + breakdown, + maxDepth, + maxSiblings, + maxRetainingPaths, + } = request; + + if (!(0 <= dominatorTreeId && dominatorTreeId < dominatorTrees.length)) { + throw new Error( + `There does not exist a DominatorTree with the id ${dominatorTreeId}`); + } + + const dominatorTree = dominatorTrees[dominatorTreeId]; + const snapshot = dominatorTreeSnapshots[dominatorTreeId]; + + const tree = DominatorTreeNode.partialTraversal(dominatorTree, + snapshot, + breakdown, + maxDepth, + maxSiblings); + + const nodes = []; + (function getNodes(node) { + nodes.push(node); + if (node.children) { + for (let i = 0, length = node.children.length; i < length; i++) { + getNodes(node.children[i]); + } + } + }(tree)); + + DominatorTreeNode.attachShortestPaths(snapshot, + breakdown, + dominatorTree.root, + nodes, + maxRetainingPaths); + + return tree; +}); + +/** + * @see HeapAnalysesClient.prototype.getImmediatelyDominated + */ +workerHelper.createTask(self, "getImmediatelyDominated", request => { + const { + dominatorTreeId, + nodeId, + breakdown, + startIndex, + maxCount, + maxRetainingPaths, + } = request; + + if (!(0 <= dominatorTreeId && dominatorTreeId < dominatorTrees.length)) { + throw new Error( + `There does not exist a DominatorTree with the id ${dominatorTreeId}`); + } + + const dominatorTree = dominatorTrees[dominatorTreeId]; + const snapshot = dominatorTreeSnapshots[dominatorTreeId]; + + const childIds = dominatorTree.getImmediatelyDominated(nodeId); + if (!childIds) { + throw new Error(`${nodeId} is not a node id in the dominator tree`); + } + + const start = startIndex || DEFAULT_START_INDEX; + const count = maxCount || DEFAULT_MAX_COUNT; + const end = start + count; + + const nodes = childIds + .slice(start, end) + .map(id => { + const { label, shallowSize } = + DominatorTreeNode.getLabelAndShallowSize(id, snapshot, breakdown); + const retainedSize = dominatorTree.getRetainedSize(id); + const node = new DominatorTreeNode(id, label, shallowSize, retainedSize); + node.parentId = nodeId; + // DominatorTree.getImmediatelyDominated will always return non-null here + // because we got the id directly from the dominator tree. + node.moreChildrenAvailable = dominatorTree.getImmediatelyDominated(id).length > 0; + return node; + }); + + const path = []; + let id = nodeId; + do { + path.push(id); + id = dominatorTree.getImmediateDominator(id); + } while (id !== null); + path.reverse(); + + const moreChildrenAvailable = childIds.length > end; + + DominatorTreeNode.attachShortestPaths(snapshot, + breakdown, + dominatorTree.root, + nodes, + maxRetainingPaths); + + return { nodes, moreChildrenAvailable, path }; +}); diff --git a/devtools/shared/heapsnapshot/HeapSnapshotFileUtils.js b/devtools/shared/heapsnapshot/HeapSnapshotFileUtils.js new file mode 100644 index 000000000..abd44fc30 --- /dev/null +++ b/devtools/shared/heapsnapshot/HeapSnapshotFileUtils.js @@ -0,0 +1,95 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +// Heap snapshots are always saved in the temp directory, and have a regular +// naming convention. This module provides helpers for working with heap +// snapshot files in a safe manner. Because we attempt to avoid unnecessary +// copies of the heap snapshot files by checking the local filesystem for a heap +// snapshot file with the given snapshot id, we want to ensure that we are only +// attempting to open heap snapshot files and not `~/.ssh/id_rsa`, for +// example. Therefore, the RDP only talks about snapshot ids, or transfering the +// bulk file data. A file path can be recovered from a snapshot id, which allows +// one to check for the presence of the heap snapshot file on the local file +// system, but we don't have to worry about opening arbitrary files. +// +// The heap snapshot file path conventions permits the following forms: +// +// $TEMP_DIRECTORY/XXXXXXXXXX.fxsnapshot +// $TEMP_DIRECTORY/XXXXXXXXXX-XXXXX.fxsnapshot +// +// Where the strings of "X" are zero or more digits. + +"use strict"; + +const { Ci } = require("chrome"); +loader.lazyRequireGetter(this, "FileUtils", + "resource://gre/modules/FileUtils.jsm", true); +loader.lazyRequireGetter(this, "OS", "resource://gre/modules/osfile.jsm", true); + +function getHeapSnapshotFileTemplate() { + return OS.Path.join(OS.Constants.Path.tmpDir, `${Date.now()}.fxsnapshot`); +} + +/** + * Get a unique temp file path for a new heap snapshot. The file is guaranteed + * not to exist before this call. + * + * @returns String + */ +exports.getNewUniqueHeapSnapshotTempFilePath = function () { + let file = new FileUtils.File(getHeapSnapshotFileTemplate()); + // The call to createUnique will append "-N" after the leaf name (but before + // the extension) until a new file is found and create it. This guarantees we + // won't accidentally choose the same file twice. + file.createUnique(Ci.nsIFile.NORMAL_FILE_TYPE, 0o666); + return file.path; +}; + +function isValidSnapshotFileId(snapshotId) { + return /^\d+(\-\d+)?$/.test(snapshotId); +} + +/** + * Get the file path for the given snapshot id. + * + * @param {String} snapshotId + * + * @returns String | null + */ +exports.getHeapSnapshotTempFilePath = function (snapshotId) { + // Don't want anyone sneaking "../../../.." strings into the snapshot id and + // trying to make us open arbitrary files. + if (!isValidSnapshotFileId(snapshotId)) { + return null; + } + return OS.Path.join(OS.Constants.Path.tmpDir, snapshotId + ".fxsnapshot"); +}; + +/** + * Return true if we have the heap snapshot file for the given snapshot id on + * the local file system. False is returned otherwise. + * + * @returns Promise<Boolean> + */ +exports.haveHeapSnapshotTempFile = function (snapshotId) { + const path = exports.getHeapSnapshotTempFilePath(snapshotId); + if (!path) { + return Promise.resolve(false); + } + + return OS.File.stat(path).then(() => true, + () => false); +}; + +/** + * Given a heap snapshot's file path, extricate the snapshot id. + * + * @param {String} path + * + * @returns String + */ +exports.getSnapshotIdFromPath = function (path) { + return path.slice(OS.Constants.Path.tmpDir.length + 1, + path.length - ".fxsnapshot".length); +}; diff --git a/devtools/shared/heapsnapshot/census-tree-node.js b/devtools/shared/heapsnapshot/census-tree-node.js new file mode 100644 index 000000000..b041e77f9 --- /dev/null +++ b/devtools/shared/heapsnapshot/census-tree-node.js @@ -0,0 +1,748 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ +"use strict"; + +// CensusTreeNode is an intermediate representation of a census report that +// exists between after a report is generated by taking a census and before the +// report is rendered in the DOM. It must be dead simple to render, with no +// further data processing or massaging needed before rendering DOM nodes. Our +// goal is to do the census report to CensusTreeNode transformation in the +// HeapAnalysesWorker, and ensure that the **only** work that the main thread +// has to do is strictly DOM rendering work. + +const { + Visitor, + walk, + basisTotalBytes, + basisTotalCount, +} = require("resource://devtools/shared/heapsnapshot/CensusUtils.js"); + +// Monotonically increasing integer for CensusTreeNode `id`s. +let censusTreeNodeIdCounter = 0; + +/** + * Return true if the given object is a SavedFrame stack object, false otherwise. + * + * @param {any} obj + * @returns {Boolean} + */ +function isSavedFrame(obj) { + return Object.prototype.toString.call(obj) === "[object SavedFrame]"; +} + +/** + * A CensusTreeNodeCache maps from SavedFrames to CensusTreeNodes. It is used when + * aggregating multiple SavedFrame allocation stack keys into a tree of many + * CensusTreeNodes. Each stack may share older frames, and we want to preserve + * this sharing when converting to CensusTreeNode, so before creating a new + * CensusTreeNode, we look for an existing one in one of our CensusTreeNodeCaches. + */ +function CensusTreeNodeCache() {} +CensusTreeNodeCache.prototype = null; + +/** + * The value of a single entry stored in a CensusTreeNodeCache. It is a pair of + * the CensusTreeNode for this cache value, and the subsequent + * CensusTreeNodeCache for this node's children. + * + * @param {SavedFrame} frame + * The frame being cached. + */ +function CensusTreeNodeCacheValue() { + // The CensusTreeNode for this cache value. + this.node = undefined; + // The CensusTreeNodeCache for this frame's children. + this.children = undefined; +} + +CensusTreeNodeCacheValue.prototype = null; + +/** + * Create a unique string for the given SavedFrame (ignoring the frame's parent + * chain) that can be used as a hash to key this frame within a CensusTreeNodeCache. + * + * NB: We manually hash rather than using an ES6 Map because we are purposely + * ignoring the parent chain and wish to consider frames with everything the + * same except their parents as the same. + * + * @param {SavedFrame} frame + * The SavedFrame object we would like to lookup in or insert into a + * CensusTreeNodeCache. + * + * @returns {String} + * The unique string that can be used as a key in a CensusTreeNodeCache. + */ +CensusTreeNodeCache.hashFrame = function (frame) { + return `FRAME,${frame.functionDisplayName},${frame.source},${frame.line},${frame.column},${frame.asyncCause}`; +}; + +/** + * Create a unique string for the given CensusTreeNode **with regards to + * siblings at the current depth of the tree, not within the whole tree.** It + * can be used as a hash to key this node within a CensusTreeNodeCache. + * + * @param {CensusTreeNode} node + * The node we would like to lookup in or insert into a cache. + * + * @returns {String} + * The unique string that can be used as a key in a CensusTreeNodeCache. + */ +CensusTreeNodeCache.hashNode = function (node) { + return isSavedFrame(node.name) + ? CensusTreeNodeCache.hashFrame(node.name) + : `NODE,${node.name}`; +}; + +/** + * Insert the given CensusTreeNodeCacheValue whose node.name is a SavedFrame + * object in the given cache. + * + * @param {CensusTreeNodeCache} cache + * @param {CensusTreeNodeCacheValue} value + */ +CensusTreeNodeCache.insertFrame = function (cache, value) { + cache[CensusTreeNodeCache.hashFrame(value.node.name)] = value; +}; + +/** + * Insert the given value in the cache. + * + * @param {CensusTreeNodeCache} cache + * @param {CensusTreeNodeCacheValue} value + */ +CensusTreeNodeCache.insertNode = function (cache, value) { + if (isSavedFrame(value.node.name)) { + CensusTreeNodeCache.insertFrame(cache, value); + } else { + cache[CensusTreeNodeCache.hashNode(value.node)] = value; + } +}; + +/** + * Lookup `frame` in `cache` and return its value if it exists. + * + * @param {CensusTreeNodeCache} cache + * @param {SavedFrame} frame + * + * @returns {undefined|CensusTreeNodeCacheValue} + */ +CensusTreeNodeCache.lookupFrame = function (cache, frame) { + return cache[CensusTreeNodeCache.hashFrame(frame)]; +}; + +/** + * Lookup `node` in `cache` and return its value if it exists. + * + * @param {CensusTreeNodeCache} cache + * @param {CensusTreeNode} node + * + * @returns {undefined|CensusTreeNodeCacheValue} + */ +CensusTreeNodeCache.lookupNode = function (cache, node) { + return isSavedFrame(node.name) + ? CensusTreeNodeCache.lookupFrame(cache, node.name) + : cache[CensusTreeNodeCache.hashNode(node)]; +}; + +/** + * Add `child` to `parent`'s set of children and store the parent ID + * on the child. + * + * @param {CensusTreeNode} parent + * @param {CensusTreeNode} child + */ +function addChild(parent, child) { + if (!parent.children) { + parent.children = []; + } + child.parent = parent.id; + parent.children.push(child); +} + +/** + * Get an array of each frame in the provided stack. + * + * @param {SavedFrame} stack + * @returns {Array<SavedFrame>} + */ +function getArrayOfFrames(stack) { + const frames = []; + let frame = stack; + while (frame) { + frames.push(frame); + frame = frame.parent; + } + frames.reverse(); + return frames; +} + +/** + * Given an `edge` to a sub-`report` whose structure is described by + * `breakdown`, create a CensusTreeNode tree. + * + * @param {Object} breakdown + * The breakdown specifying the structure of the given report. + * + * @param {Object} report + * The census report. + * + * @param {null|String|SavedFrame} edge + * The edge leading to this report from the parent report. + * + * @param {CensusTreeNodeCache} cache + * The cache of CensusTreeNodes we have already made for the siblings of + * the node being created. The existing nodes are reused when possible. + * + * @param {Object} outParams + * The return values are attached to this object after this function + * returns. Because we create a CensusTreeNode for each frame in a + * SavedFrame stack edge, there may multiple nodes per sub-report. + * + * - top: The deepest node in the CensusTreeNode subtree created. + * + * - bottom: The shallowest node in the CensusTreeNode subtree created. + * This is null if the shallowest node in the subtree was + * found in the `cache` and reused. + * + * Note that top and bottom are not necessarily different. In the case + * where there is a 1:1 correspondence between an edge in the report and + * a CensusTreeNode, top and bottom refer to the same node. + */ +function makeCensusTreeNodeSubTree(breakdown, report, edge, cache, outParams) { + if (!isSavedFrame(edge)) { + const node = new CensusTreeNode(edge); + outParams.top = outParams.bottom = node; + return; + } + + const frames = getArrayOfFrames(edge); + let currentCache = cache; + let prevNode; + for (let i = 0, length = frames.length; i < length; i++) { + const frame = frames[i]; + + // Get or create the CensusTreeNodeCacheValue for this frame. If we already + // have a CensusTreeNodeCacheValue (and hence a CensusTreeNode) for this + // frame, we don't need to add the node to the previous node's children as + // we have already done that. If we don't have a CensusTreeNodeCacheValue + // and CensusTreeNode for this frame, then create one and make sure to hook + // it up as a child of the previous node. + let isNewNode = false; + let val = CensusTreeNodeCache.lookupFrame(currentCache, frame); + if (!val) { + isNewNode = true; + val = new CensusTreeNodeCacheValue(); + val.node = new CensusTreeNode(frame); + + CensusTreeNodeCache.insertFrame(currentCache, val); + if (prevNode) { + addChild(prevNode, val.node); + } + } + + if (i === 0) { + outParams.bottom = isNewNode ? val.node : null; + } + if (i === length - 1) { + outParams.top = val.node; + } + + prevNode = val.node; + + if (i !== length - 1 && !val.children) { + // This is not the last frame and therefore this node will have + // children, which we must cache. + val.children = new CensusTreeNodeCache(); + } + + currentCache = val.children; + } +} + +/** + * A Visitor that walks a census report and creates the corresponding + * CensusTreeNode tree. + */ +function CensusTreeNodeVisitor() { + // The root of the resulting CensusTreeNode tree. + this._root = null; + + // The stack of CensusTreeNodes that we are in the process of building while + // walking the census report. + this._nodeStack = []; + + // To avoid unnecessary allocations, we reuse the same out parameter object + // passed to `makeCensusTreeNodeSubTree` every time we call it. + this._outParams = { + top: null, + bottom: null, + }; + + // The stack of `CensusTreeNodeCache`s that we use to aggregate many + // SavedFrame stacks into a single CensusTreeNode tree. + this._cacheStack = [new CensusTreeNodeCache()]; + + // The current index in the DFS of the census report tree. + this._index = -1; +} + +CensusTreeNodeVisitor.prototype = Object.create(Visitor); + +/** + * Create the CensusTreeNode subtree for this sub-report and link it to the + * parent CensusTreeNode. + * + * @overrides Visitor.prototype.enter + */ +CensusTreeNodeVisitor.prototype.enter = function (breakdown, report, edge) { + this._index++; + + const cache = this._cacheStack[this._cacheStack.length - 1]; + makeCensusTreeNodeSubTree(breakdown, report, edge, cache, this._outParams); + const { top, bottom } = this._outParams; + + if (!this._root) { + this._root = bottom; + } else if (bottom) { + addChild(this._nodeStack[this._nodeStack.length - 1], bottom); + } + + this._cacheStack.push(new CensusTreeNodeCache()); + this._nodeStack.push(top); +}; + +function values(cache) { + return Object.keys(cache).map(k => cache[k]); +} + +function isNonEmpty(node) { + return (node.children !== undefined && node.children.length) + || node.bytes !== 0 + || node.count !== 0; +} + +/** + * We have finished adding children to the CensusTreeNode subtree for the + * current sub-report. Make sure that the children are sorted for every node in + * the subtree. + * + * @overrides Visitor.prototype.exit + */ +CensusTreeNodeVisitor.prototype.exit = function (breakdown, report, edge) { + // Ensure all children are sorted and have their counts/bytes aggregated. We + // only need to consider cache children here, because other children + // correspond to other sub-reports and we already fixed them up in an earlier + // invocation of `exit`. + + function dfs(node, childrenCache) { + if (childrenCache) { + const childValues = values(childrenCache); + for (let i = 0, length = childValues.length; i < length; i++) { + dfs(childValues[i].node, childValues[i].children); + } + } + + node.totalCount = node.count; + node.totalBytes = node.bytes; + + if (node.children) { + // Prune empty leaves. + node.children = node.children.filter(isNonEmpty); + + node.children.sort(compareByTotal); + + for (let i = 0, length = node.children.length; i < length; i++) { + node.totalCount += node.children[i].totalCount; + node.totalBytes += node.children[i].totalBytes; + } + } + } + + const top = this._nodeStack.pop(); + const cache = this._cacheStack.pop(); + dfs(top, cache); +}; + +/** + * @overrides Visitor.prototype.count + */ +CensusTreeNodeVisitor.prototype.count = function (breakdown, report, edge) { + const node = this._nodeStack[this._nodeStack.length - 1]; + node.reportLeafIndex = this._index; + + if (breakdown.count) { + node.count = report.count; + } + + if (breakdown.bytes) { + node.bytes = report.bytes; + } +}; + +/** + * Get the root of the resulting CensusTreeNode tree. + * + * @returns {CensusTreeNode} + */ +CensusTreeNodeVisitor.prototype.root = function () { + if (!this._root) { + throw new Error("Attempt to get the root before walking the census report!"); + } + + if (this._nodeStack.length) { + throw new Error("Attempt to get the root while walking the census report!"); + } + + return this._root; +}; + +/** + * Create a single, uninitialized CensusTreeNode. + * + * @param {null|String|SavedFrame} name + */ +function CensusTreeNode(name) { + // Display name for this CensusTreeNode. Either null, a string, or a + // SavedFrame. + this.name = name; + + // The number of bytes occupied by matching things in the heap snapshot. + this.bytes = 0; + + // The sum of `this.bytes` and `child.totalBytes` for each child in + // `this.children`. + this.totalBytes = 0; + + // The number of things in the heap snapshot that match this node in the + // census tree. + this.count = 0; + + // The sum of `this.count` and `child.totalCount` for each child in + // `this.children`. + this.totalCount = 0; + + // An array of this node's children, or undefined if it has no children. + this.children = undefined; + + // The unique ID of this node. + this.id = ++censusTreeNodeIdCounter; + + // If present, the unique ID of this node's parent. If this node does not have + // a parent, then undefined. + this.parent = undefined; + + // The `reportLeafIndex` property allows mapping a CensusTreeNode node back to + // a leaf in the census report it was generated from. It is always one of the + // following variants: + // + // * A `Number` index pointing a leaf report in a pre-order DFS traversal of + // this CensusTreeNode's census report. + // + // * A `Set` object containing such indices, when this is part of an inverted + // CensusTreeNode tree and multiple leaves in the report map onto this node. + // + // * Finally, `undefined` when no leaves in the census report correspond with + // this node. + // + // The first and third cases are the common cases. The second case is rather + // uncommon, and to avoid doubling the number of allocations when creating + // CensusTreeNode trees, and objects that get structured cloned when sending + // such trees from the HeapAnalysesWorker to the main thread, we only allocate + // a Set object once a node actually does have multiple leaves it corresponds + // to. + this.reportLeafIndex = undefined; +} + +CensusTreeNode.prototype = null; + +/** + * Compare the given nodes by their `totalBytes` properties, and breaking ties + * with the `totalCount`, `bytes`, and `count` properties (in that order). + * + * @param {CensusTreeNode} node1 + * @param {CensusTreeNode} node2 + * + * @returns {Number} + * A number suitable for using with Array.prototype.sort. + */ +function compareByTotal(node1, node2) { + return Math.abs(node2.totalBytes) - Math.abs(node1.totalBytes) + || Math.abs(node2.totalCount) - Math.abs(node1.totalCount) + || Math.abs(node2.bytes) - Math.abs(node1.bytes) + || Math.abs(node2.count) - Math.abs(node1.count); +} + +/** + * Compare the given nodes by their `bytes` properties, and breaking ties with + * the `count`, `totalBytes`, and `totalCount` properties (in that order). + * + * @param {CensusTreeNode} node1 + * @param {CensusTreeNode} node2 + * + * @returns {Number} + * A number suitable for using with Array.prototype.sort. + */ +function compareBySelf(node1, node2) { + return Math.abs(node2.bytes) - Math.abs(node1.bytes) + || Math.abs(node2.count) - Math.abs(node1.count) + || Math.abs(node2.totalBytes) - Math.abs(node1.totalBytes) + || Math.abs(node2.totalCount) - Math.abs(node1.totalCount); +} + +/** + * Given a parent cache value from a tree we are building and a child node from + * a tree we are basing the new tree off of, if we already have a corresponding + * node in the parent's children cache, merge this node's counts with + * it. Otherwise, create the corresponding node, add it to the parent's children + * cache, and create the parent->child edge. + * + * @param {CensusTreeNodeCacheValue} parentCachevalue + * @param {CensusTreeNode} node + * + * @returns {CensusTreeNodeCacheValue} + * The new or extant child node's corresponding cache value. + */ +function insertOrMergeNode(parentCacheValue, node) { + if (!parentCacheValue.children) { + parentCacheValue.children = new CensusTreeNodeCache(); + } + + let val = CensusTreeNodeCache.lookupNode(parentCacheValue.children, node); + + if (val) { + // When inverting, it is possible that multiple leaves in the census report + // get merged into a single CensusTreeNode node. When this occurs, switch + // from a single index to a set of indices. + if (val.node.reportLeafIndex !== undefined && + val.node.reportLeafIndex !== node.reportLeafIndex) { + if (typeof val.node.reportLeafIndex === "number") { + const oldIndex = val.node.reportLeafIndex; + val.node.reportLeafIndex = new Set(); + val.node.reportLeafIndex.add(oldIndex); + val.node.reportLeafIndex.add(node.reportLeafIndex); + } else { + val.node.reportLeafIndex.add(node.reportLeafIndex); + } + } + + val.node.count += node.count; + val.node.bytes += node.bytes; + } else { + val = new CensusTreeNodeCacheValue(); + + val.node = new CensusTreeNode(node.name); + val.node.reportLeafIndex = node.reportLeafIndex; + val.node.count = node.count; + val.node.totalCount = node.totalCount; + val.node.bytes = node.bytes; + val.node.totalBytes = node.totalBytes; + + addChild(parentCacheValue.node, val.node); + CensusTreeNodeCache.insertNode(parentCacheValue.children, val); + } + + return val; +} + +/** + * Given an un-inverted CensusTreeNode tree, return the corresponding inverted + * CensusTreeNode tree. The input tree is not modified. The resulting inverted + * tree is sorted by self bytes rather than by total bytes. + * + * @param {CensusTreeNode} tree + * The un-inverted tree. + * + * @returns {CensusTreeNode} + * The corresponding inverted tree. + */ +function invert(tree) { + const inverted = new CensusTreeNodeCacheValue(); + inverted.node = new CensusTreeNode(null); + + // Do a depth-first search of the un-inverted tree. As we reach each leaf, + // take the path from the old root to the leaf, reverse that path, and add it + // to the new, inverted tree's root. + + const path = []; + (function addInvertedPaths(node) { + path.push(node); + + if (node.children) { + for (let i = 0, length = node.children.length; i < length; i++) { + addInvertedPaths(node.children[i]); + } + } else { + // We found a leaf node, add the reverse path to the inverted tree. + let currentCacheValue = inverted; + for (let i = path.length - 1; i >= 0; i--) { + currentCacheValue = insertOrMergeNode(currentCacheValue, path[i]); + } + } + + path.pop(); + }(tree)); + + // Ensure that the root node always has the totals. + inverted.node.totalBytes = tree.totalBytes; + inverted.node.totalCount = tree.totalCount; + + return inverted.node; +} + +/** + * Given a CensusTreeNode tree and predicate function, create the tree + * containing only the nodes in any path `(node_0, node_1, ..., node_n-1)` in + * the given tree where `predicate(node_j)` is true for `0 <= j < n`, `node_0` + * is the given tree's root, and `node_n-1` is a leaf in the given tree. The + * given tree is left unmodified. + * + * @param {CensusTreeNode} tree + * @param {Function} predicate + * + * @returns {CensusTreeNode} + */ +function filter(tree, predicate) { + const filtered = new CensusTreeNodeCacheValue(); + filtered.node = new CensusTreeNode(null); + + // Do a DFS over the given tree. If the predicate returns true for any node, + // add that node and its whole subtree to the filtered tree. + + const path = []; + let match = false; + + function addMatchingNodes(node) { + path.push(node); + + let oldMatch = match; + if (!match && predicate(node)) { + match = true; + } + + if (node.children) { + for (let i = 0, length = node.children.length; i < length; i++) { + addMatchingNodes(node.children[i]); + } + } else if (match) { + // We found a matching leaf node, add it to the filtered tree. + let currentCacheValue = filtered; + for (let i = 0, length = path.length; i < length; i++) { + currentCacheValue = insertOrMergeNode(currentCacheValue, path[i]); + } + } + + match = oldMatch; + path.pop(); + } + + if (tree.children) { + for (let i = 0, length = tree.children.length; i < length; i++) { + addMatchingNodes(tree.children[i]); + } + } + + filtered.node.count = tree.count; + filtered.node.totalCount = tree.totalCount; + filtered.node.bytes = tree.bytes; + filtered.node.totalBytes = tree.totalBytes; + + return filtered.node; +} + +/** + * Given a filter string, return a predicate function that takes a node and + * returns true iff the node matches the filter. + * + * @param {String} filterString + * @returns {Function} + */ +function makeFilterPredicate(filterString) { + return function (node) { + if (!node.name) { + return false; + } + + if (isSavedFrame(node.name)) { + return node.name.source.includes(filterString) + || (node.name.functionDisplayName || "").includes(filterString) + || (node.name.asyncCause || "").includes(filterString); + } + + return String(node.name).includes(filterString); + }; +} + +/** + * Takes a report from a census (`dbg.memory.takeCensus()`) and the breakdown + * used to generate the census and returns a structure used to render + * a tree to display the data. + * + * Returns a recursive "CensusTreeNode" object, looking like: + * + * CensusTreeNode = { + * // `children` if it exists, is sorted by `bytes`, if they are leaf nodes. + * children: ?[<CensusTreeNode...>], + * name: <?String> + * count: <?Number> + * bytes: <?Number> + * id: <?Number> + * parent: <?Number> + * } + * + * @param {Object} breakdown + * The breakdown used to generate the census report. + * + * @param {Object} report + * The census report generated with the specified breakdown. + * + * @param {Object} options + * Configuration options. + * - invert: Whether to invert the resulting tree or not. Defaults to + * false, ie uninverted. + * + * @returns {CensusTreeNode} + */ +exports.censusReportToCensusTreeNode = function (breakdown, report, + options = { + invert: false, + filter: null + }) { + // Reset the counter so that turning the same census report into a + // CensusTreeNode tree repeatedly is idempotent. + censusTreeNodeIdCounter = 0; + + const visitor = new CensusTreeNodeVisitor(); + walk(breakdown, report, visitor); + let result = visitor.root(); + + if (options.invert) { + result = invert(result); + } + + if (typeof options.filter === "string") { + result = filter(result, makeFilterPredicate(options.filter)); + } + + // If the report is a delta report that was generated by diffing two other + // reports, make sure to use the basis totals rather than the totals of the + // difference. + if (typeof report[basisTotalBytes] === "number") { + result.totalBytes = report[basisTotalBytes]; + result.totalCount = report[basisTotalCount]; + } + + // Inverting and filtering could have messed up the sort order, so do a + // depth-first search of the tree and ensure that siblings are sorted. + const comparator = options.invert ? compareBySelf : compareByTotal; + (function ensureSorted(node) { + if (node.children) { + node.children.sort(comparator); + for (let i = 0, length = node.children.length; i < length; i++) { + ensureSorted(node.children[i]); + } + } + }(result)); + + return result; +}; diff --git a/devtools/shared/heapsnapshot/moz.build b/devtools/shared/heapsnapshot/moz.build new file mode 100644 index 000000000..9a915e426 --- /dev/null +++ b/devtools/shared/heapsnapshot/moz.build @@ -0,0 +1,15 @@ +# -*- Mode: python; indent-tabs-mode: nil; tab-width: 40 -*- +# vim: set filetype=python: +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +DevToolsModules( + 'census-tree-node.js', + 'CensusUtils.js', + 'DominatorTreeNode.js', + 'HeapAnalysesClient.js', + 'HeapAnalysesWorker.js', + 'HeapSnapshotFileUtils.js', + 'shortest-paths.js', +) diff --git a/devtools/shared/heapsnapshot/shortest-paths.js b/devtools/shared/heapsnapshot/shortest-paths.js new file mode 100644 index 000000000..2d97b7de9 --- /dev/null +++ b/devtools/shared/heapsnapshot/shortest-paths.js @@ -0,0 +1,91 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ +"use strict"; + +/** + * Compress a set of paths leading to `target` into a single graph, returned as + * a set of nodes and a set of edges. + * + * @param {NodeId} target + * The target node passed to `HeapSnapshot.computeShortestPaths`. + * + * @param {Array<Path>} paths + * An array of paths to `target`, as returned by + * `HeapSnapshot.computeShortestPaths`. + * + * @returns {Object} + * An object with two properties: + * - edges: An array of unique objects of the form: + * { + * from: <node ID>, + * to: <node ID>, + * name: <string or null> + * } + * - nodes: An array of unique node IDs. Every `from` and `to` id is + * guaranteed to be in this array exactly once. + */ +exports.deduplicatePaths = function (target, paths) { + // Use this structure to de-duplicate edges among many retaining paths from + // start to target. + // + // Map<FromNodeId, Map<ToNodeId, Set<EdgeName>>> + const deduped = new Map(); + + function insert(from, to, name) { + let toMap = deduped.get(from); + if (!toMap) { + toMap = new Map(); + deduped.set(from, toMap); + } + + let nameSet = toMap.get(to); + if (!nameSet) { + nameSet = new Set(); + toMap.set(to, nameSet); + } + + nameSet.add(name); + } + + outer: for (let path of paths) { + const pathLength = path.length; + + // Check for duplicate predecessors in the path, and skip paths that contain + // them. + const predecessorsSeen = new Set(); + predecessorsSeen.add(target); + for (let i = 0; i < pathLength; i++) { + if (predecessorsSeen.has(path[i].predecessor)) { + continue outer; + } + predecessorsSeen.add(path[i].predecessor); + } + + for (let i = 0; i < pathLength - 1; i++) { + insert(path[i].predecessor, path[i + 1].predecessor, path[i].edge); + } + + insert(path[pathLength - 1].predecessor, target, path[pathLength - 1].edge); + } + + const nodes = [target]; + const edges = []; + + for (let [from, toMap] of deduped) { + // If the second/third/etc shortest path contains the `target` anywhere + // other than the very last node, we could accidentally put the `target` in + // `nodes` more than once. + if (from !== target) { + nodes.push(from); + } + + for (let [to, edgeNameSet] of toMap) { + for (let name of edgeNameSet) { + edges.push({ from, to, name }); + } + } + } + + return { nodes, edges }; +}; |