From e9ee12c988d80f847f8163c0873db9639b3fa8f4 Mon Sep 17 00:00:00 2001 From: "Matt A. Tobin" Date: Sun, 23 Feb 2020 10:38:36 -0500 Subject: Follow-up to 4e2e9be6a - Move HeapSnapshot DevTools-only Modules back to DevTools I am so done with this. Resolves #316 --- devtools/shared/heapsnapshot/CensusUtils.js | 489 ++++++++++++++ devtools/shared/heapsnapshot/DominatorTreeNode.js | 336 +++++++++ devtools/shared/heapsnapshot/HeapAnalysesClient.js | 277 ++++++++ devtools/shared/heapsnapshot/HeapAnalysesWorker.js | 303 +++++++++ .../shared/heapsnapshot/HeapSnapshotFileUtils.js | 95 +++ devtools/shared/heapsnapshot/census-tree-node.js | 748 +++++++++++++++++++++ devtools/shared/heapsnapshot/moz.build | 15 + devtools/shared/heapsnapshot/shortest-paths.js | 91 +++ devtools/shared/moz.build | 1 + dom/heapsnapshot/CensusUtils.js | 489 -------------- dom/heapsnapshot/DominatorTreeNode.js | 336 --------- dom/heapsnapshot/HeapAnalysesClient.js | 277 -------- dom/heapsnapshot/HeapAnalysesWorker.js | 303 --------- dom/heapsnapshot/HeapSnapshotFileUtils.js | 95 --- dom/heapsnapshot/census-tree-node.js | 748 --------------------- dom/heapsnapshot/moz.build | 11 - dom/heapsnapshot/shortest-paths.js | 91 --- 17 files changed, 2355 insertions(+), 2350 deletions(-) create mode 100644 devtools/shared/heapsnapshot/CensusUtils.js create mode 100644 devtools/shared/heapsnapshot/DominatorTreeNode.js create mode 100644 devtools/shared/heapsnapshot/HeapAnalysesClient.js create mode 100644 devtools/shared/heapsnapshot/HeapAnalysesWorker.js create mode 100644 devtools/shared/heapsnapshot/HeapSnapshotFileUtils.js create mode 100644 devtools/shared/heapsnapshot/census-tree-node.js create mode 100644 devtools/shared/heapsnapshot/moz.build create mode 100644 devtools/shared/heapsnapshot/shortest-paths.js delete mode 100644 dom/heapsnapshot/CensusUtils.js delete mode 100644 dom/heapsnapshot/DominatorTreeNode.js delete mode 100644 dom/heapsnapshot/HeapAnalysesClient.js delete mode 100644 dom/heapsnapshot/HeapAnalysesWorker.js delete mode 100644 dom/heapsnapshot/HeapSnapshotFileUtils.js delete mode 100644 dom/heapsnapshot/census-tree-node.js delete mode 100644 dom/heapsnapshot/shortest-paths.js 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} aggregator + * + * @return {Object} + */ +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} indices + * @param {Object} breakdown + * @param {Object} report + * + * @returns {Array} + */ +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} indices + * @param {Object} breakdown + * @param {HeapSnapshot} snapshot + * + * @returns {Array} + */ +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} path + * @param {Array} 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} 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} 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 + */ +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 + * 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} 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} + * A promise of an object with the following properties: + * - {Array} 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 + * - 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} + */ +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} + */ +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} + * A promise of an object with the following properties: + * - {Array} 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} 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 + */ +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} + */ +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: ?[], + * name: + * count: + * bytes: + * id: + * parent: + * } + * + * @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} 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: , + * to: , + * name: + * } + * - 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>> + 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 }; +}; diff --git a/devtools/shared/moz.build b/devtools/shared/moz.build index 9dd4a20d6..e4de1d84a 100644 --- a/devtools/shared/moz.build +++ b/devtools/shared/moz.build @@ -14,6 +14,7 @@ DIRS += [ 'discovery', 'fronts', 'gcli', + 'heapsnapshot', 'inspector', 'jsbeautify', 'layout', diff --git a/dom/heapsnapshot/CensusUtils.js b/dom/heapsnapshot/CensusUtils.js deleted file mode 100644 index 36bdd2d82..000000000 --- a/dom/heapsnapshot/CensusUtils.js +++ /dev/null @@ -1,489 +0,0 @@ -/* 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} aggregator - * - * @return {Object} - */ -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} indices - * @param {Object} breakdown - * @param {Object} report - * - * @returns {Array} - */ -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} indices - * @param {Object} breakdown - * @param {HeapSnapshot} snapshot - * - * @returns {Array} - */ -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/dom/heapsnapshot/DominatorTreeNode.js b/dom/heapsnapshot/DominatorTreeNode.js deleted file mode 100644 index 13a847fd0..000000000 --- a/dom/heapsnapshot/DominatorTreeNode.js +++ /dev/null @@ -1,336 +0,0 @@ -/* 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} path - * @param {Array} 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} 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} 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/dom/heapsnapshot/HeapAnalysesClient.js b/dom/heapsnapshot/HeapAnalysesClient.js deleted file mode 100644 index 98601a2b1..000000000 --- a/dom/heapsnapshot/HeapAnalysesClient.js +++ /dev/null @@ -1,277 +0,0 @@ -/* 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 - */ -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 - * 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} 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} - * A promise of an object with the following properties: - * - {Array} 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 - * - 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} - */ -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} - */ -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} - * A promise of an object with the following properties: - * - {Array} 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} 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/dom/heapsnapshot/HeapAnalysesWorker.js b/dom/heapsnapshot/HeapAnalysesWorker.js deleted file mode 100644 index d07d67f80..000000000 --- a/dom/heapsnapshot/HeapAnalysesWorker.js +++ /dev/null @@ -1,303 +0,0 @@ -/* 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/dom/heapsnapshot/HeapSnapshotFileUtils.js b/dom/heapsnapshot/HeapSnapshotFileUtils.js deleted file mode 100644 index abd44fc30..000000000 --- a/dom/heapsnapshot/HeapSnapshotFileUtils.js +++ /dev/null @@ -1,95 +0,0 @@ -/* 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 - */ -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/dom/heapsnapshot/census-tree-node.js b/dom/heapsnapshot/census-tree-node.js deleted file mode 100644 index b041e77f9..000000000 --- a/dom/heapsnapshot/census-tree-node.js +++ /dev/null @@ -1,748 +0,0 @@ -/* 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} - */ -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: ?[], - * name: - * count: - * bytes: - * id: - * parent: - * } - * - * @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/dom/heapsnapshot/moz.build b/dom/heapsnapshot/moz.build index fa9ef3915..3fb6b0552 100644 --- a/dom/heapsnapshot/moz.build +++ b/dom/heapsnapshot/moz.build @@ -48,16 +48,5 @@ DEFINES['GOOGLE_PROTOBUF_NO_RTTI'] = True FINAL_LIBRARY = 'xul' -if CONFIG['MOZ_DEVTOOLS_SERVER']: - DevToolsModules( - 'census-tree-node.js', - 'CensusUtils.js', - 'DominatorTreeNode.js', - 'HeapAnalysesClient.js', - 'HeapAnalysesWorker.js', - 'HeapSnapshotFileUtils.js', - 'shortest-paths.js', - ) - if CONFIG['GNU_CXX']: CXXFLAGS += ['-Wno-error=shadow'] diff --git a/dom/heapsnapshot/shortest-paths.js b/dom/heapsnapshot/shortest-paths.js deleted file mode 100644 index 2d97b7de9..000000000 --- a/dom/heapsnapshot/shortest-paths.js +++ /dev/null @@ -1,91 +0,0 @@ -/* 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} 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: , - * to: , - * name: - * } - * - 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>> - 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 }; -}; -- cgit v1.2.3