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/DominatorTreeNode.js | 336 ++++++++++++++++++++++ 1 file changed, 336 insertions(+) create mode 100644 devtools/shared/heapsnapshot/DominatorTreeNode.js (limited to 'devtools/shared/heapsnapshot/DominatorTreeNode.js') 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; + } +}; -- cgit v1.2.3