diff options
Diffstat (limited to 'dom')
| -rw-r--r-- | dom/heapsnapshot/CensusUtils.js | 489 | ||||
| -rw-r--r-- | dom/heapsnapshot/DominatorTreeNode.js | 336 | ||||
| -rw-r--r-- | dom/heapsnapshot/HeapAnalysesClient.js | 277 | ||||
| -rw-r--r-- | dom/heapsnapshot/HeapAnalysesWorker.js | 303 | ||||
| -rw-r--r-- | dom/heapsnapshot/HeapSnapshotFileUtils.js | 95 | ||||
| -rw-r--r-- | dom/heapsnapshot/census-tree-node.js | 748 | ||||
| -rw-r--r-- | dom/heapsnapshot/moz.build | 11 | ||||
| -rw-r--r-- | dom/heapsnapshot/shortest-paths.js | 91 |
8 files changed, 0 insertions, 2350 deletions
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<number, TreeNode>} aggregator - * - * @return {Object<number, TreeNode>} - */ -const createParentMap = exports.createParentMap = function (node, - getId = node => node.id, - aggregator = Object.create(null)) { - if (node.children) { - for (let i = 0, length = node.children.length; i < length; i++) { - const child = node.children[i]; - aggregator[getId(child)] = node; - createParentMap(child, getId, aggregator); - } - } - - return aggregator; -}; - -const BUCKET = Object.freeze({ by: "bucket" }); - -/** - * Convert a breakdown whose leaves are { by: "count" } to an identical - * breakdown, except with { by: "bucket" } leaves. - * - * @param {Object} breakdown - * @returns {Object} - */ -exports.countToBucketBreakdown = function (breakdown) { - if (typeof breakdown !== "object" || !breakdown) { - return breakdown; - } - - if (breakdown.by === "count") { - return BUCKET; - } - - const keys = Object.keys(breakdown); - const vals = keys.reduce((vs, k) => { - vs.push(exports.countToBucketBreakdown(breakdown[k])); - return vs; - }, []); - - const result = {}; - for (let i = 0, length = keys.length; i < length; i++) { - result[keys[i]] = vals[i]; - } - - return Object.freeze(result); -}; - -/** - * A Visitor for finding report leaves by their DFS index. - */ -function GetLeavesVisitor(targetIndices) { - this._index = -1; - this._targetIndices = targetIndices; - this._leaves = []; -} - -GetLeavesVisitor.prototype = Object.create(Visitor.prototype); - -/** - * @overrides Visitor.prototype.enter - */ -GetLeavesVisitor.prototype.enter = function (breakdown, report, edge) { - this._index++; - if (this._targetIndices.has(this._index)) { - this._leaves.push(report); - } -}; - -/** - * Get the accumulated report leaves after traversal. - */ -GetLeavesVisitor.prototype.leaves = function () { - if (this._index === -1) { - throw new Error("Attempt to call `leaves` before traversing report!"); - } - return this._leaves; -}; - -/** - * Given a set of indices of leaves in a pre-order depth-first traversal of the - * given census report, return the leaves. - * - * @param {Set<Number>} indices - * @param {Object} breakdown - * @param {Object} report - * - * @returns {Array<Object>} - */ -exports.getReportLeaves = function (indices, breakdown, report) { - const visitor = new GetLeavesVisitor(indices); - walk(breakdown, report, visitor); - return visitor.leaves(); -}; - -/** - * Get a list of the individual node IDs that belong to the census report leaves - * of the given indices. - * - * @param {Set<Number>} indices - * @param {Object} breakdown - * @param {HeapSnapshot} snapshot - * - * @returns {Array<NodeId>} - */ -exports.getCensusIndividuals = function (indices, countBreakdown, snapshot) { - const bucketBreakdown = exports.countToBucketBreakdown(countBreakdown); - const bucketReport = snapshot.takeCensus({ breakdown: bucketBreakdown }); - const buckets = exports.getReportLeaves(indices, - bucketBreakdown, - bucketReport); - return flatten(buckets); -}; diff --git a/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<NodeId>} path - * @param {Array<DominatorTreeNode>} newChildren - * @param {Boolean} moreChildrenAvailable - * - * @returns {DominatorTreeNode} - */ -DominatorTreeNode.insert = function (tree, path, newChildren, moreChildrenAvailable) { - function insert(tree, i) { - if (tree.nodeId !== path[i]) { - return tree; - } - - if (i == path.length - 1) { - return immutableUpdate(tree, { - children: (tree.children || []).concat(newChildren), - moreChildrenAvailable, - }); - } - - return tree.children - ? immutableUpdate(tree, { - children: tree.children.map(c => insert(c, i + 1)) - }) - : tree; - } - - return insert(tree, 0); -}; - -/** - * Get the new canonical node with the given `id` in `tree` that exists along - * `path`. If there is no such node along `path`, return null. - * - * This is useful if we have a reference to a now-outdated DominatorTreeNode due - * to a recent call to DominatorTreeNode.insert and want to get the up-to-date - * version. We don't have to walk the whole tree: if there is an updated version - * of the node then it *must* be along the path. - * - * @param {NodeId} id - * @param {DominatorTreeNode} tree - * @param {Array<NodeId>} path - * - * @returns {DominatorTreeNode|null} - */ -DominatorTreeNode.getNodeByIdAlongPath = function (id, tree, path) { - function find(node, i) { - if (!node || node.nodeId !== path[i]) { - return null; - } - - if (node.nodeId === id) { - return node; - } - - if (i === path.length - 1 || !node.children) { - return null; - } - - const nextId = path[i + 1]; - return find(node.children.find(c => c.nodeId === nextId), i + 1); - } - - return find(tree, 0); -}; - -/** - * Find the shortest retaining paths for the given set of DominatorTreeNodes, - * and populate each node's `shortestPaths` property with them in place. - * - * @param {HeapSnapshot} snapshot - * @param {Object} breakdown - * @param {NodeId} start - * @param {Array<DominatorTreeNode>} treeNodes - * @param {Number} maxNumPaths - */ -DominatorTreeNode.attachShortestPaths = function (snapshot, - breakdown, - start, - treeNodes, - maxNumPaths = DEFAULT_MAX_NUM_PATHS) { - const idToTreeNode = new Map(); - const targets = []; - for (let node of treeNodes) { - const id = node.nodeId; - idToTreeNode.set(id, node); - targets.push(id); - } - - const shortestPaths = snapshot.computeShortestPaths(start, - targets, - maxNumPaths); - - for (let [target, paths] of shortestPaths) { - const deduped = deduplicatePaths(target, paths); - deduped.nodes = deduped.nodes.map(id => { - const { label } = - DominatorTreeNode.getLabelAndShallowSize(id, snapshot, breakdown); - return { id, label }; - }); - - idToTreeNode.get(target).shortestPaths = deduped; - } -}; diff --git a/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<undefined> - */ -HeapAnalysesClient.prototype.deleteHeapSnapshot = function (snapshotFilePath) { - return this._worker.performTask("deleteHeapSnapshot", { snapshotFilePath }); -}; - -/** - * Request the creation time given a snapshot file path. Returns `null` - * if snapshot does not exist. - * - * @param {String} snapshotFilePath - * The path to the snapshot. - * @return {Number?} - * The unix timestamp of the creation time of the snapshot, or null if - * snapshot does not exist. - */ -HeapAnalysesClient.prototype.getCreationTime = function (snapshotFilePath) { - return this._worker.performTask("getCreationTime", snapshotFilePath); -}; - -/** * Censuses *****************************************************************/ - -/** - * Ask the worker to perform a census analysis on the heap snapshot with the - * given path. The heap snapshot at the given path must have already been read - * into memory by the worker (see `readHeapSnapshot`). - * - * @param {String} snapshotFilePath - * - * @param {Object} censusOptions - * A structured-cloneable object specifying the requested census's - * breakdown. See the "takeCensus" section of - * `js/src/doc/Debugger/Debugger.Memory.md` for detailed documentation. - * - * @param {Object} requestOptions - * An object specifying options of this worker request. - * - {Boolean} asTreeNode - * Whether or not the census is returned as a CensusTreeNode, - * or just a breakdown report. Defaults to false. - * @see `devtools/shared/heapsnapshot/census-tree-node.js` - * - {Boolean} asInvertedTreeNode - * Whether or not the census is returned as an inverted - * CensusTreeNode. Defaults to false. - * - {String} filter - * A filter string to prune the resulting tree with. Only applies if - * either asTreeNode or asInvertedTreeNode is true. - * - * @returns Promise<Object> - * An object with the following properties: - * - report: - * The report generated by the given census breakdown, or a - * CensusTreeNode generated by the given census breakdown if - * `asTreeNode` is true. - * - parentMap: - * The result of calling CensusUtils.createParentMap on the generated - * report. Only exists if asTreeNode or asInvertedTreeNode are set. - */ -HeapAnalysesClient.prototype.takeCensus = function (snapshotFilePath, - censusOptions, - requestOptions = {}) { - return this._worker.performTask("takeCensus", { - snapshotFilePath, - censusOptions, - requestOptions, - }); -}; - -/** - * Get the individual nodes that correspond to the given census report leaf - * indices. - * - * @param {Object} opts - * An object with the following properties: - * - {DominatorTreeId} dominatorTreeId: The id of the dominator tree. - * - {Set<Number>} indices: The indices of the census report leaves we - * would like to get the individuals for. - * - {Object} censusBreakdown: The breakdown used to generate the census. - * - {Object} labelBreakdown: The breakdown we would like to use when - * labeling the resulting nodes. - * - {Number} maxRetainingPaths: The maximum number of retaining paths to - * compute for each node. - * - {Number} maxIndividuals: The maximum number of individual nodes to - * return. - * - * @returns {Promise<Object>} - * A promise of an object with the following properties: - * - {Array<DominatorTreeNode>} nodes: An array of `DominatorTreeNode`s - * with their shortest paths attached, and without any dominator tree - * child/parent information attached. The results are sorted by - * retained size. - * - */ -HeapAnalysesClient.prototype.getCensusIndividuals = function (opts) { - return this._worker.performTask("getCensusIndividuals", opts); -}; - -/** - * Request that the worker take a census on the heap snapshots with the given - * paths and then return the difference between them. Both heap snapshots must - * have already been read into memory by the worker (see `readHeapSnapshot`). - * - * @param {String} firstSnapshotFilePath - * The first snapshot file path. - * - * @param {String} secondSnapshotFilePath - * The second snapshot file path. - * - * @param {Object} censusOptions - * A structured-cloneable object specifying the requested census's - * breakdown. See the "takeCensus" section of - * `js/src/doc/Debugger/Debugger.Memory.md` for detailed documentation. - * - * @param {Object} requestOptions - * An object specifying options for this request. - * - {Boolean} asTreeNode - * Whether the resulting delta report should be converted to a census - * tree node before returned. Defaults to false. - * - {Boolean} asInvertedTreeNode - * Whether or not the census is returned as an inverted - * CensusTreeNode. Defaults to false. - * - {String} filter - * A filter string to prune the resulting tree with. Only applies if - * either asTreeNode or asInvertedTreeNode is true. - * - * @returns Promise<Object> - * - delta: - * The delta report generated by diffing the two census reports, or a - * CensusTreeNode generated from the delta report if - * `requestOptions.asTreeNode` was true. - * - parentMap: - * The result of calling CensusUtils.createParentMap on the generated - * delta. Only exists if asTreeNode or asInvertedTreeNode are set. - */ -HeapAnalysesClient.prototype.takeCensusDiff = function (firstSnapshotFilePath, - secondSnapshotFilePath, - censusOptions, - requestOptions = {}) { - return this._worker.performTask("takeCensusDiff", { - firstSnapshotFilePath, - secondSnapshotFilePath, - censusOptions, - requestOptions - }); -}; - -/** * Dominator Trees **********************************************************/ - -/** - * Compute the dominator tree of the heap snapshot loaded from the given file - * path. Returns the id of the computed dominator tree. - * - * @param {String} snapshotFilePath - * - * @returns {Promise<DominatorTreeId>} - */ -HeapAnalysesClient.prototype.computeDominatorTree = function (snapshotFilePath) { - return this._worker.performTask("computeDominatorTree", snapshotFilePath); -}; - -/** - * Get the initial, partial view of the dominator tree with the given id. - * - * @param {Object} opts - * An object specifying options for this request. - * - {DominatorTreeId} dominatorTreeId - * The id of the dominator tree. - * - {Object} breakdown - * The breakdown used to generate node labels. - * - {Number} maxDepth - * The maximum depth to traverse down the tree to create this initial - * view. - * - {Number} maxSiblings - * The maximum number of siblings to visit within each traversed node's - * children. - * - {Number} maxRetainingPaths - * The maximum number of retaining paths to find for each node. - * - * @returns {Promise<DominatorTreeNode>} - */ -HeapAnalysesClient.prototype.getDominatorTree = function (opts) { - return this._worker.performTask("getDominatorTree", opts); -}; - -/** - * Get a subset of a nodes children in the dominator tree. - * - * @param {Object} opts - * An object specifying options for this request. - * - {DominatorTreeId} dominatorTreeId - * The id of the dominator tree. - * - {NodeId} nodeId - * The id of the node whose children are being found. - * - {Object} breakdown - * The breakdown used to generate node labels. - * - {Number} startIndex - * The starting index within the full set of immediately dominated - * children of the children being requested. Children are always sorted - * by greatest to least retained size. - * - {Number} maxCount - * The maximum number of children to return. - * - {Number} maxRetainingPaths - * The maximum number of retaining paths to find for each node. - * - * @returns {Promise<Object>} - * A promise of an object with the following properties: - * - {Array<DominatorTreeNode>} nodes - * The requested nodes that are immediately dominated by the node - * identified by `opts.nodeId`. - * - {Boolean} moreChildrenAvailable - * True iff there are more children available after the returned - * nodes. - * - {Array<NodeId>} path - * The path through the tree from the root to these node's parent, eg - * [root's id, child of root's id, child of child of root's id, ..., `nodeId`]. - */ -HeapAnalysesClient.prototype.getImmediatelyDominated = function (opts) { - return this._worker.performTask("getImmediatelyDominated", opts); -}; diff --git a/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<Boolean> - */ -exports.haveHeapSnapshotTempFile = function (snapshotId) { - const path = exports.getHeapSnapshotTempFilePath(snapshotId); - if (!path) { - return Promise.resolve(false); - } - - return OS.File.stat(path).then(() => true, - () => false); -}; - -/** - * Given a heap snapshot's file path, extricate the snapshot id. - * - * @param {String} path - * - * @returns String - */ -exports.getSnapshotIdFromPath = function (path) { - return path.slice(OS.Constants.Path.tmpDir.length + 1, - path.length - ".fxsnapshot".length); -}; diff --git a/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<SavedFrame>} - */ -function getArrayOfFrames(stack) { - const frames = []; - let frame = stack; - while (frame) { - frames.push(frame); - frame = frame.parent; - } - frames.reverse(); - return frames; -} - -/** - * Given an `edge` to a sub-`report` whose structure is described by - * `breakdown`, create a CensusTreeNode tree. - * - * @param {Object} breakdown - * The breakdown specifying the structure of the given report. - * - * @param {Object} report - * The census report. - * - * @param {null|String|SavedFrame} edge - * The edge leading to this report from the parent report. - * - * @param {CensusTreeNodeCache} cache - * The cache of CensusTreeNodes we have already made for the siblings of - * the node being created. The existing nodes are reused when possible. - * - * @param {Object} outParams - * The return values are attached to this object after this function - * returns. Because we create a CensusTreeNode for each frame in a - * SavedFrame stack edge, there may multiple nodes per sub-report. - * - * - top: The deepest node in the CensusTreeNode subtree created. - * - * - bottom: The shallowest node in the CensusTreeNode subtree created. - * This is null if the shallowest node in the subtree was - * found in the `cache` and reused. - * - * Note that top and bottom are not necessarily different. In the case - * where there is a 1:1 correspondence between an edge in the report and - * a CensusTreeNode, top and bottom refer to the same node. - */ -function makeCensusTreeNodeSubTree(breakdown, report, edge, cache, outParams) { - if (!isSavedFrame(edge)) { - const node = new CensusTreeNode(edge); - outParams.top = outParams.bottom = node; - return; - } - - const frames = getArrayOfFrames(edge); - let currentCache = cache; - let prevNode; - for (let i = 0, length = frames.length; i < length; i++) { - const frame = frames[i]; - - // Get or create the CensusTreeNodeCacheValue for this frame. If we already - // have a CensusTreeNodeCacheValue (and hence a CensusTreeNode) for this - // frame, we don't need to add the node to the previous node's children as - // we have already done that. If we don't have a CensusTreeNodeCacheValue - // and CensusTreeNode for this frame, then create one and make sure to hook - // it up as a child of the previous node. - let isNewNode = false; - let val = CensusTreeNodeCache.lookupFrame(currentCache, frame); - if (!val) { - isNewNode = true; - val = new CensusTreeNodeCacheValue(); - val.node = new CensusTreeNode(frame); - - CensusTreeNodeCache.insertFrame(currentCache, val); - if (prevNode) { - addChild(prevNode, val.node); - } - } - - if (i === 0) { - outParams.bottom = isNewNode ? val.node : null; - } - if (i === length - 1) { - outParams.top = val.node; - } - - prevNode = val.node; - - if (i !== length - 1 && !val.children) { - // This is not the last frame and therefore this node will have - // children, which we must cache. - val.children = new CensusTreeNodeCache(); - } - - currentCache = val.children; - } -} - -/** - * A Visitor that walks a census report and creates the corresponding - * CensusTreeNode tree. - */ -function CensusTreeNodeVisitor() { - // The root of the resulting CensusTreeNode tree. - this._root = null; - - // The stack of CensusTreeNodes that we are in the process of building while - // walking the census report. - this._nodeStack = []; - - // To avoid unnecessary allocations, we reuse the same out parameter object - // passed to `makeCensusTreeNodeSubTree` every time we call it. - this._outParams = { - top: null, - bottom: null, - }; - - // The stack of `CensusTreeNodeCache`s that we use to aggregate many - // SavedFrame stacks into a single CensusTreeNode tree. - this._cacheStack = [new CensusTreeNodeCache()]; - - // The current index in the DFS of the census report tree. - this._index = -1; -} - -CensusTreeNodeVisitor.prototype = Object.create(Visitor); - -/** - * Create the CensusTreeNode subtree for this sub-report and link it to the - * parent CensusTreeNode. - * - * @overrides Visitor.prototype.enter - */ -CensusTreeNodeVisitor.prototype.enter = function (breakdown, report, edge) { - this._index++; - - const cache = this._cacheStack[this._cacheStack.length - 1]; - makeCensusTreeNodeSubTree(breakdown, report, edge, cache, this._outParams); - const { top, bottom } = this._outParams; - - if (!this._root) { - this._root = bottom; - } else if (bottom) { - addChild(this._nodeStack[this._nodeStack.length - 1], bottom); - } - - this._cacheStack.push(new CensusTreeNodeCache()); - this._nodeStack.push(top); -}; - -function values(cache) { - return Object.keys(cache).map(k => cache[k]); -} - -function isNonEmpty(node) { - return (node.children !== undefined && node.children.length) - || node.bytes !== 0 - || node.count !== 0; -} - -/** - * We have finished adding children to the CensusTreeNode subtree for the - * current sub-report. Make sure that the children are sorted for every node in - * the subtree. - * - * @overrides Visitor.prototype.exit - */ -CensusTreeNodeVisitor.prototype.exit = function (breakdown, report, edge) { - // Ensure all children are sorted and have their counts/bytes aggregated. We - // only need to consider cache children here, because other children - // correspond to other sub-reports and we already fixed them up in an earlier - // invocation of `exit`. - - function dfs(node, childrenCache) { - if (childrenCache) { - const childValues = values(childrenCache); - for (let i = 0, length = childValues.length; i < length; i++) { - dfs(childValues[i].node, childValues[i].children); - } - } - - node.totalCount = node.count; - node.totalBytes = node.bytes; - - if (node.children) { - // Prune empty leaves. - node.children = node.children.filter(isNonEmpty); - - node.children.sort(compareByTotal); - - for (let i = 0, length = node.children.length; i < length; i++) { - node.totalCount += node.children[i].totalCount; - node.totalBytes += node.children[i].totalBytes; - } - } - } - - const top = this._nodeStack.pop(); - const cache = this._cacheStack.pop(); - dfs(top, cache); -}; - -/** - * @overrides Visitor.prototype.count - */ -CensusTreeNodeVisitor.prototype.count = function (breakdown, report, edge) { - const node = this._nodeStack[this._nodeStack.length - 1]; - node.reportLeafIndex = this._index; - - if (breakdown.count) { - node.count = report.count; - } - - if (breakdown.bytes) { - node.bytes = report.bytes; - } -}; - -/** - * Get the root of the resulting CensusTreeNode tree. - * - * @returns {CensusTreeNode} - */ -CensusTreeNodeVisitor.prototype.root = function () { - if (!this._root) { - throw new Error("Attempt to get the root before walking the census report!"); - } - - if (this._nodeStack.length) { - throw new Error("Attempt to get the root while walking the census report!"); - } - - return this._root; -}; - -/** - * Create a single, uninitialized CensusTreeNode. - * - * @param {null|String|SavedFrame} name - */ -function CensusTreeNode(name) { - // Display name for this CensusTreeNode. Either null, a string, or a - // SavedFrame. - this.name = name; - - // The number of bytes occupied by matching things in the heap snapshot. - this.bytes = 0; - - // The sum of `this.bytes` and `child.totalBytes` for each child in - // `this.children`. - this.totalBytes = 0; - - // The number of things in the heap snapshot that match this node in the - // census tree. - this.count = 0; - - // The sum of `this.count` and `child.totalCount` for each child in - // `this.children`. - this.totalCount = 0; - - // An array of this node's children, or undefined if it has no children. - this.children = undefined; - - // The unique ID of this node. - this.id = ++censusTreeNodeIdCounter; - - // If present, the unique ID of this node's parent. If this node does not have - // a parent, then undefined. - this.parent = undefined; - - // The `reportLeafIndex` property allows mapping a CensusTreeNode node back to - // a leaf in the census report it was generated from. It is always one of the - // following variants: - // - // * A `Number` index pointing a leaf report in a pre-order DFS traversal of - // this CensusTreeNode's census report. - // - // * A `Set` object containing such indices, when this is part of an inverted - // CensusTreeNode tree and multiple leaves in the report map onto this node. - // - // * Finally, `undefined` when no leaves in the census report correspond with - // this node. - // - // The first and third cases are the common cases. The second case is rather - // uncommon, and to avoid doubling the number of allocations when creating - // CensusTreeNode trees, and objects that get structured cloned when sending - // such trees from the HeapAnalysesWorker to the main thread, we only allocate - // a Set object once a node actually does have multiple leaves it corresponds - // to. - this.reportLeafIndex = undefined; -} - -CensusTreeNode.prototype = null; - -/** - * Compare the given nodes by their `totalBytes` properties, and breaking ties - * with the `totalCount`, `bytes`, and `count` properties (in that order). - * - * @param {CensusTreeNode} node1 - * @param {CensusTreeNode} node2 - * - * @returns {Number} - * A number suitable for using with Array.prototype.sort. - */ -function compareByTotal(node1, node2) { - return Math.abs(node2.totalBytes) - Math.abs(node1.totalBytes) - || Math.abs(node2.totalCount) - Math.abs(node1.totalCount) - || Math.abs(node2.bytes) - Math.abs(node1.bytes) - || Math.abs(node2.count) - Math.abs(node1.count); -} - -/** - * Compare the given nodes by their `bytes` properties, and breaking ties with - * the `count`, `totalBytes`, and `totalCount` properties (in that order). - * - * @param {CensusTreeNode} node1 - * @param {CensusTreeNode} node2 - * - * @returns {Number} - * A number suitable for using with Array.prototype.sort. - */ -function compareBySelf(node1, node2) { - return Math.abs(node2.bytes) - Math.abs(node1.bytes) - || Math.abs(node2.count) - Math.abs(node1.count) - || Math.abs(node2.totalBytes) - Math.abs(node1.totalBytes) - || Math.abs(node2.totalCount) - Math.abs(node1.totalCount); -} - -/** - * Given a parent cache value from a tree we are building and a child node from - * a tree we are basing the new tree off of, if we already have a corresponding - * node in the parent's children cache, merge this node's counts with - * it. Otherwise, create the corresponding node, add it to the parent's children - * cache, and create the parent->child edge. - * - * @param {CensusTreeNodeCacheValue} parentCachevalue - * @param {CensusTreeNode} node - * - * @returns {CensusTreeNodeCacheValue} - * The new or extant child node's corresponding cache value. - */ -function insertOrMergeNode(parentCacheValue, node) { - if (!parentCacheValue.children) { - parentCacheValue.children = new CensusTreeNodeCache(); - } - - let val = CensusTreeNodeCache.lookupNode(parentCacheValue.children, node); - - if (val) { - // When inverting, it is possible that multiple leaves in the census report - // get merged into a single CensusTreeNode node. When this occurs, switch - // from a single index to a set of indices. - if (val.node.reportLeafIndex !== undefined && - val.node.reportLeafIndex !== node.reportLeafIndex) { - if (typeof val.node.reportLeafIndex === "number") { - const oldIndex = val.node.reportLeafIndex; - val.node.reportLeafIndex = new Set(); - val.node.reportLeafIndex.add(oldIndex); - val.node.reportLeafIndex.add(node.reportLeafIndex); - } else { - val.node.reportLeafIndex.add(node.reportLeafIndex); - } - } - - val.node.count += node.count; - val.node.bytes += node.bytes; - } else { - val = new CensusTreeNodeCacheValue(); - - val.node = new CensusTreeNode(node.name); - val.node.reportLeafIndex = node.reportLeafIndex; - val.node.count = node.count; - val.node.totalCount = node.totalCount; - val.node.bytes = node.bytes; - val.node.totalBytes = node.totalBytes; - - addChild(parentCacheValue.node, val.node); - CensusTreeNodeCache.insertNode(parentCacheValue.children, val); - } - - return val; -} - -/** - * Given an un-inverted CensusTreeNode tree, return the corresponding inverted - * CensusTreeNode tree. The input tree is not modified. The resulting inverted - * tree is sorted by self bytes rather than by total bytes. - * - * @param {CensusTreeNode} tree - * The un-inverted tree. - * - * @returns {CensusTreeNode} - * The corresponding inverted tree. - */ -function invert(tree) { - const inverted = new CensusTreeNodeCacheValue(); - inverted.node = new CensusTreeNode(null); - - // Do a depth-first search of the un-inverted tree. As we reach each leaf, - // take the path from the old root to the leaf, reverse that path, and add it - // to the new, inverted tree's root. - - const path = []; - (function addInvertedPaths(node) { - path.push(node); - - if (node.children) { - for (let i = 0, length = node.children.length; i < length; i++) { - addInvertedPaths(node.children[i]); - } - } else { - // We found a leaf node, add the reverse path to the inverted tree. - let currentCacheValue = inverted; - for (let i = path.length - 1; i >= 0; i--) { - currentCacheValue = insertOrMergeNode(currentCacheValue, path[i]); - } - } - - path.pop(); - }(tree)); - - // Ensure that the root node always has the totals. - inverted.node.totalBytes = tree.totalBytes; - inverted.node.totalCount = tree.totalCount; - - return inverted.node; -} - -/** - * Given a CensusTreeNode tree and predicate function, create the tree - * containing only the nodes in any path `(node_0, node_1, ..., node_n-1)` in - * the given tree where `predicate(node_j)` is true for `0 <= j < n`, `node_0` - * is the given tree's root, and `node_n-1` is a leaf in the given tree. The - * given tree is left unmodified. - * - * @param {CensusTreeNode} tree - * @param {Function} predicate - * - * @returns {CensusTreeNode} - */ -function filter(tree, predicate) { - const filtered = new CensusTreeNodeCacheValue(); - filtered.node = new CensusTreeNode(null); - - // Do a DFS over the given tree. If the predicate returns true for any node, - // add that node and its whole subtree to the filtered tree. - - const path = []; - let match = false; - - function addMatchingNodes(node) { - path.push(node); - - let oldMatch = match; - if (!match && predicate(node)) { - match = true; - } - - if (node.children) { - for (let i = 0, length = node.children.length; i < length; i++) { - addMatchingNodes(node.children[i]); - } - } else if (match) { - // We found a matching leaf node, add it to the filtered tree. - let currentCacheValue = filtered; - for (let i = 0, length = path.length; i < length; i++) { - currentCacheValue = insertOrMergeNode(currentCacheValue, path[i]); - } - } - - match = oldMatch; - path.pop(); - } - - if (tree.children) { - for (let i = 0, length = tree.children.length; i < length; i++) { - addMatchingNodes(tree.children[i]); - } - } - - filtered.node.count = tree.count; - filtered.node.totalCount = tree.totalCount; - filtered.node.bytes = tree.bytes; - filtered.node.totalBytes = tree.totalBytes; - - return filtered.node; -} - -/** - * Given a filter string, return a predicate function that takes a node and - * returns true iff the node matches the filter. - * - * @param {String} filterString - * @returns {Function} - */ -function makeFilterPredicate(filterString) { - return function (node) { - if (!node.name) { - return false; - } - - if (isSavedFrame(node.name)) { - return node.name.source.includes(filterString) - || (node.name.functionDisplayName || "").includes(filterString) - || (node.name.asyncCause || "").includes(filterString); - } - - return String(node.name).includes(filterString); - }; -} - -/** - * Takes a report from a census (`dbg.memory.takeCensus()`) and the breakdown - * used to generate the census and returns a structure used to render - * a tree to display the data. - * - * Returns a recursive "CensusTreeNode" object, looking like: - * - * CensusTreeNode = { - * // `children` if it exists, is sorted by `bytes`, if they are leaf nodes. - * children: ?[<CensusTreeNode...>], - * name: <?String> - * count: <?Number> - * bytes: <?Number> - * id: <?Number> - * parent: <?Number> - * } - * - * @param {Object} breakdown - * The breakdown used to generate the census report. - * - * @param {Object} report - * The census report generated with the specified breakdown. - * - * @param {Object} options - * Configuration options. - * - invert: Whether to invert the resulting tree or not. Defaults to - * false, ie uninverted. - * - * @returns {CensusTreeNode} - */ -exports.censusReportToCensusTreeNode = function (breakdown, report, - options = { - invert: false, - filter: null - }) { - // Reset the counter so that turning the same census report into a - // CensusTreeNode tree repeatedly is idempotent. - censusTreeNodeIdCounter = 0; - - const visitor = new CensusTreeNodeVisitor(); - walk(breakdown, report, visitor); - let result = visitor.root(); - - if (options.invert) { - result = invert(result); - } - - if (typeof options.filter === "string") { - result = filter(result, makeFilterPredicate(options.filter)); - } - - // If the report is a delta report that was generated by diffing two other - // reports, make sure to use the basis totals rather than the totals of the - // difference. - if (typeof report[basisTotalBytes] === "number") { - result.totalBytes = report[basisTotalBytes]; - result.totalCount = report[basisTotalCount]; - } - - // Inverting and filtering could have messed up the sort order, so do a - // depth-first search of the tree and ensure that siblings are sorted. - const comparator = options.invert ? compareBySelf : compareByTotal; - (function ensureSorted(node) { - if (node.children) { - node.children.sort(comparator); - for (let i = 0, length = node.children.length; i < length; i++) { - ensureSorted(node.children[i]); - } - } - }(result)); - - return result; -}; diff --git a/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<Path>} paths - * An array of paths to `target`, as returned by - * `HeapSnapshot.computeShortestPaths`. - * - * @returns {Object} - * An object with two properties: - * - edges: An array of unique objects of the form: - * { - * from: <node ID>, - * to: <node ID>, - * name: <string or null> - * } - * - nodes: An array of unique node IDs. Every `from` and `to` id is - * guaranteed to be in this array exactly once. - */ -exports.deduplicatePaths = function (target, paths) { - // Use this structure to de-duplicate edges among many retaining paths from - // start to target. - // - // Map<FromNodeId, Map<ToNodeId, Set<EdgeName>>> - const deduped = new Map(); - - function insert(from, to, name) { - let toMap = deduped.get(from); - if (!toMap) { - toMap = new Map(); - deduped.set(from, toMap); - } - - let nameSet = toMap.get(to); - if (!nameSet) { - nameSet = new Set(); - toMap.set(to, nameSet); - } - - nameSet.add(name); - } - - outer: for (let path of paths) { - const pathLength = path.length; - - // Check for duplicate predecessors in the path, and skip paths that contain - // them. - const predecessorsSeen = new Set(); - predecessorsSeen.add(target); - for (let i = 0; i < pathLength; i++) { - if (predecessorsSeen.has(path[i].predecessor)) { - continue outer; - } - predecessorsSeen.add(path[i].predecessor); - } - - for (let i = 0; i < pathLength - 1; i++) { - insert(path[i].predecessor, path[i + 1].predecessor, path[i].edge); - } - - insert(path[pathLength - 1].predecessor, target, path[pathLength - 1].edge); - } - - const nodes = [target]; - const edges = []; - - for (let [from, toMap] of deduped) { - // If the second/third/etc shortest path contains the `target` anywhere - // other than the very last node, we could accidentally put the `target` in - // `nodes` more than once. - if (from !== target) { - nodes.push(from); - } - - for (let [to, edgeNameSet] of toMap) { - for (let name of edgeNameSet) { - edges.push({ from, to, name }); - } - } - } - - return { nodes, edges }; -}; |