diff options
Diffstat (limited to 'devtools/shared/heapsnapshot/census-tree-node.js')
| -rw-r--r-- | devtools/shared/heapsnapshot/census-tree-node.js | 748 |
1 files changed, 748 insertions, 0 deletions
diff --git a/devtools/shared/heapsnapshot/census-tree-node.js b/devtools/shared/heapsnapshot/census-tree-node.js new file mode 100644 index 0000000000..b041e77f9c --- /dev/null +++ b/devtools/shared/heapsnapshot/census-tree-node.js @@ -0,0 +1,748 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ +"use strict"; + +// CensusTreeNode is an intermediate representation of a census report that +// exists between after a report is generated by taking a census and before the +// report is rendered in the DOM. It must be dead simple to render, with no +// further data processing or massaging needed before rendering DOM nodes. Our +// goal is to do the census report to CensusTreeNode transformation in the +// HeapAnalysesWorker, and ensure that the **only** work that the main thread +// has to do is strictly DOM rendering work. + +const { + Visitor, + walk, + basisTotalBytes, + basisTotalCount, +} = require("resource://devtools/shared/heapsnapshot/CensusUtils.js"); + +// Monotonically increasing integer for CensusTreeNode `id`s. +let censusTreeNodeIdCounter = 0; + +/** + * Return true if the given object is a SavedFrame stack object, false otherwise. + * + * @param {any} obj + * @returns {Boolean} + */ +function isSavedFrame(obj) { + return Object.prototype.toString.call(obj) === "[object SavedFrame]"; +} + +/** + * A CensusTreeNodeCache maps from SavedFrames to CensusTreeNodes. It is used when + * aggregating multiple SavedFrame allocation stack keys into a tree of many + * CensusTreeNodes. Each stack may share older frames, and we want to preserve + * this sharing when converting to CensusTreeNode, so before creating a new + * CensusTreeNode, we look for an existing one in one of our CensusTreeNodeCaches. + */ +function CensusTreeNodeCache() {} +CensusTreeNodeCache.prototype = null; + +/** + * The value of a single entry stored in a CensusTreeNodeCache. It is a pair of + * the CensusTreeNode for this cache value, and the subsequent + * CensusTreeNodeCache for this node's children. + * + * @param {SavedFrame} frame + * The frame being cached. + */ +function CensusTreeNodeCacheValue() { + // The CensusTreeNode for this cache value. + this.node = undefined; + // The CensusTreeNodeCache for this frame's children. + this.children = undefined; +} + +CensusTreeNodeCacheValue.prototype = null; + +/** + * Create a unique string for the given SavedFrame (ignoring the frame's parent + * chain) that can be used as a hash to key this frame within a CensusTreeNodeCache. + * + * NB: We manually hash rather than using an ES6 Map because we are purposely + * ignoring the parent chain and wish to consider frames with everything the + * same except their parents as the same. + * + * @param {SavedFrame} frame + * The SavedFrame object we would like to lookup in or insert into a + * CensusTreeNodeCache. + * + * @returns {String} + * The unique string that can be used as a key in a CensusTreeNodeCache. + */ +CensusTreeNodeCache.hashFrame = function (frame) { + return `FRAME,${frame.functionDisplayName},${frame.source},${frame.line},${frame.column},${frame.asyncCause}`; +}; + +/** + * Create a unique string for the given CensusTreeNode **with regards to + * siblings at the current depth of the tree, not within the whole tree.** It + * can be used as a hash to key this node within a CensusTreeNodeCache. + * + * @param {CensusTreeNode} node + * The node we would like to lookup in or insert into a cache. + * + * @returns {String} + * The unique string that can be used as a key in a CensusTreeNodeCache. + */ +CensusTreeNodeCache.hashNode = function (node) { + return isSavedFrame(node.name) + ? CensusTreeNodeCache.hashFrame(node.name) + : `NODE,${node.name}`; +}; + +/** + * Insert the given CensusTreeNodeCacheValue whose node.name is a SavedFrame + * object in the given cache. + * + * @param {CensusTreeNodeCache} cache + * @param {CensusTreeNodeCacheValue} value + */ +CensusTreeNodeCache.insertFrame = function (cache, value) { + cache[CensusTreeNodeCache.hashFrame(value.node.name)] = value; +}; + +/** + * Insert the given value in the cache. + * + * @param {CensusTreeNodeCache} cache + * @param {CensusTreeNodeCacheValue} value + */ +CensusTreeNodeCache.insertNode = function (cache, value) { + if (isSavedFrame(value.node.name)) { + CensusTreeNodeCache.insertFrame(cache, value); + } else { + cache[CensusTreeNodeCache.hashNode(value.node)] = value; + } +}; + +/** + * Lookup `frame` in `cache` and return its value if it exists. + * + * @param {CensusTreeNodeCache} cache + * @param {SavedFrame} frame + * + * @returns {undefined|CensusTreeNodeCacheValue} + */ +CensusTreeNodeCache.lookupFrame = function (cache, frame) { + return cache[CensusTreeNodeCache.hashFrame(frame)]; +}; + +/** + * Lookup `node` in `cache` and return its value if it exists. + * + * @param {CensusTreeNodeCache} cache + * @param {CensusTreeNode} node + * + * @returns {undefined|CensusTreeNodeCacheValue} + */ +CensusTreeNodeCache.lookupNode = function (cache, node) { + return isSavedFrame(node.name) + ? CensusTreeNodeCache.lookupFrame(cache, node.name) + : cache[CensusTreeNodeCache.hashNode(node)]; +}; + +/** + * Add `child` to `parent`'s set of children and store the parent ID + * on the child. + * + * @param {CensusTreeNode} parent + * @param {CensusTreeNode} child + */ +function addChild(parent, child) { + if (!parent.children) { + parent.children = []; + } + child.parent = parent.id; + parent.children.push(child); +} + +/** + * Get an array of each frame in the provided stack. + * + * @param {SavedFrame} stack + * @returns {Array<SavedFrame>} + */ +function getArrayOfFrames(stack) { + const frames = []; + let frame = stack; + while (frame) { + frames.push(frame); + frame = frame.parent; + } + frames.reverse(); + return frames; +} + +/** + * Given an `edge` to a sub-`report` whose structure is described by + * `breakdown`, create a CensusTreeNode tree. + * + * @param {Object} breakdown + * The breakdown specifying the structure of the given report. + * + * @param {Object} report + * The census report. + * + * @param {null|String|SavedFrame} edge + * The edge leading to this report from the parent report. + * + * @param {CensusTreeNodeCache} cache + * The cache of CensusTreeNodes we have already made for the siblings of + * the node being created. The existing nodes are reused when possible. + * + * @param {Object} outParams + * The return values are attached to this object after this function + * returns. Because we create a CensusTreeNode for each frame in a + * SavedFrame stack edge, there may multiple nodes per sub-report. + * + * - top: The deepest node in the CensusTreeNode subtree created. + * + * - bottom: The shallowest node in the CensusTreeNode subtree created. + * This is null if the shallowest node in the subtree was + * found in the `cache` and reused. + * + * Note that top and bottom are not necessarily different. In the case + * where there is a 1:1 correspondence between an edge in the report and + * a CensusTreeNode, top and bottom refer to the same node. + */ +function makeCensusTreeNodeSubTree(breakdown, report, edge, cache, outParams) { + if (!isSavedFrame(edge)) { + const node = new CensusTreeNode(edge); + outParams.top = outParams.bottom = node; + return; + } + + const frames = getArrayOfFrames(edge); + let currentCache = cache; + let prevNode; + for (let i = 0, length = frames.length; i < length; i++) { + const frame = frames[i]; + + // Get or create the CensusTreeNodeCacheValue for this frame. If we already + // have a CensusTreeNodeCacheValue (and hence a CensusTreeNode) for this + // frame, we don't need to add the node to the previous node's children as + // we have already done that. If we don't have a CensusTreeNodeCacheValue + // and CensusTreeNode for this frame, then create one and make sure to hook + // it up as a child of the previous node. + let isNewNode = false; + let val = CensusTreeNodeCache.lookupFrame(currentCache, frame); + if (!val) { + isNewNode = true; + val = new CensusTreeNodeCacheValue(); + val.node = new CensusTreeNode(frame); + + CensusTreeNodeCache.insertFrame(currentCache, val); + if (prevNode) { + addChild(prevNode, val.node); + } + } + + if (i === 0) { + outParams.bottom = isNewNode ? val.node : null; + } + if (i === length - 1) { + outParams.top = val.node; + } + + prevNode = val.node; + + if (i !== length - 1 && !val.children) { + // This is not the last frame and therefore this node will have + // children, which we must cache. + val.children = new CensusTreeNodeCache(); + } + + currentCache = val.children; + } +} + +/** + * A Visitor that walks a census report and creates the corresponding + * CensusTreeNode tree. + */ +function CensusTreeNodeVisitor() { + // The root of the resulting CensusTreeNode tree. + this._root = null; + + // The stack of CensusTreeNodes that we are in the process of building while + // walking the census report. + this._nodeStack = []; + + // To avoid unnecessary allocations, we reuse the same out parameter object + // passed to `makeCensusTreeNodeSubTree` every time we call it. + this._outParams = { + top: null, + bottom: null, + }; + + // The stack of `CensusTreeNodeCache`s that we use to aggregate many + // SavedFrame stacks into a single CensusTreeNode tree. + this._cacheStack = [new CensusTreeNodeCache()]; + + // The current index in the DFS of the census report tree. + this._index = -1; +} + +CensusTreeNodeVisitor.prototype = Object.create(Visitor); + +/** + * Create the CensusTreeNode subtree for this sub-report and link it to the + * parent CensusTreeNode. + * + * @overrides Visitor.prototype.enter + */ +CensusTreeNodeVisitor.prototype.enter = function (breakdown, report, edge) { + this._index++; + + const cache = this._cacheStack[this._cacheStack.length - 1]; + makeCensusTreeNodeSubTree(breakdown, report, edge, cache, this._outParams); + const { top, bottom } = this._outParams; + + if (!this._root) { + this._root = bottom; + } else if (bottom) { + addChild(this._nodeStack[this._nodeStack.length - 1], bottom); + } + + this._cacheStack.push(new CensusTreeNodeCache()); + this._nodeStack.push(top); +}; + +function values(cache) { + return Object.keys(cache).map(k => cache[k]); +} + +function isNonEmpty(node) { + return (node.children !== undefined && node.children.length) + || node.bytes !== 0 + || node.count !== 0; +} + +/** + * We have finished adding children to the CensusTreeNode subtree for the + * current sub-report. Make sure that the children are sorted for every node in + * the subtree. + * + * @overrides Visitor.prototype.exit + */ +CensusTreeNodeVisitor.prototype.exit = function (breakdown, report, edge) { + // Ensure all children are sorted and have their counts/bytes aggregated. We + // only need to consider cache children here, because other children + // correspond to other sub-reports and we already fixed them up in an earlier + // invocation of `exit`. + + function dfs(node, childrenCache) { + if (childrenCache) { + const childValues = values(childrenCache); + for (let i = 0, length = childValues.length; i < length; i++) { + dfs(childValues[i].node, childValues[i].children); + } + } + + node.totalCount = node.count; + node.totalBytes = node.bytes; + + if (node.children) { + // Prune empty leaves. + node.children = node.children.filter(isNonEmpty); + + node.children.sort(compareByTotal); + + for (let i = 0, length = node.children.length; i < length; i++) { + node.totalCount += node.children[i].totalCount; + node.totalBytes += node.children[i].totalBytes; + } + } + } + + const top = this._nodeStack.pop(); + const cache = this._cacheStack.pop(); + dfs(top, cache); +}; + +/** + * @overrides Visitor.prototype.count + */ +CensusTreeNodeVisitor.prototype.count = function (breakdown, report, edge) { + const node = this._nodeStack[this._nodeStack.length - 1]; + node.reportLeafIndex = this._index; + + if (breakdown.count) { + node.count = report.count; + } + + if (breakdown.bytes) { + node.bytes = report.bytes; + } +}; + +/** + * Get the root of the resulting CensusTreeNode tree. + * + * @returns {CensusTreeNode} + */ +CensusTreeNodeVisitor.prototype.root = function () { + if (!this._root) { + throw new Error("Attempt to get the root before walking the census report!"); + } + + if (this._nodeStack.length) { + throw new Error("Attempt to get the root while walking the census report!"); + } + + return this._root; +}; + +/** + * Create a single, uninitialized CensusTreeNode. + * + * @param {null|String|SavedFrame} name + */ +function CensusTreeNode(name) { + // Display name for this CensusTreeNode. Either null, a string, or a + // SavedFrame. + this.name = name; + + // The number of bytes occupied by matching things in the heap snapshot. + this.bytes = 0; + + // The sum of `this.bytes` and `child.totalBytes` for each child in + // `this.children`. + this.totalBytes = 0; + + // The number of things in the heap snapshot that match this node in the + // census tree. + this.count = 0; + + // The sum of `this.count` and `child.totalCount` for each child in + // `this.children`. + this.totalCount = 0; + + // An array of this node's children, or undefined if it has no children. + this.children = undefined; + + // The unique ID of this node. + this.id = ++censusTreeNodeIdCounter; + + // If present, the unique ID of this node's parent. If this node does not have + // a parent, then undefined. + this.parent = undefined; + + // The `reportLeafIndex` property allows mapping a CensusTreeNode node back to + // a leaf in the census report it was generated from. It is always one of the + // following variants: + // + // * A `Number` index pointing a leaf report in a pre-order DFS traversal of + // this CensusTreeNode's census report. + // + // * A `Set` object containing such indices, when this is part of an inverted + // CensusTreeNode tree and multiple leaves in the report map onto this node. + // + // * Finally, `undefined` when no leaves in the census report correspond with + // this node. + // + // The first and third cases are the common cases. The second case is rather + // uncommon, and to avoid doubling the number of allocations when creating + // CensusTreeNode trees, and objects that get structured cloned when sending + // such trees from the HeapAnalysesWorker to the main thread, we only allocate + // a Set object once a node actually does have multiple leaves it corresponds + // to. + this.reportLeafIndex = undefined; +} + +CensusTreeNode.prototype = null; + +/** + * Compare the given nodes by their `totalBytes` properties, and breaking ties + * with the `totalCount`, `bytes`, and `count` properties (in that order). + * + * @param {CensusTreeNode} node1 + * @param {CensusTreeNode} node2 + * + * @returns {Number} + * A number suitable for using with Array.prototype.sort. + */ +function compareByTotal(node1, node2) { + return Math.abs(node2.totalBytes) - Math.abs(node1.totalBytes) + || Math.abs(node2.totalCount) - Math.abs(node1.totalCount) + || Math.abs(node2.bytes) - Math.abs(node1.bytes) + || Math.abs(node2.count) - Math.abs(node1.count); +} + +/** + * Compare the given nodes by their `bytes` properties, and breaking ties with + * the `count`, `totalBytes`, and `totalCount` properties (in that order). + * + * @param {CensusTreeNode} node1 + * @param {CensusTreeNode} node2 + * + * @returns {Number} + * A number suitable for using with Array.prototype.sort. + */ +function compareBySelf(node1, node2) { + return Math.abs(node2.bytes) - Math.abs(node1.bytes) + || Math.abs(node2.count) - Math.abs(node1.count) + || Math.abs(node2.totalBytes) - Math.abs(node1.totalBytes) + || Math.abs(node2.totalCount) - Math.abs(node1.totalCount); +} + +/** + * Given a parent cache value from a tree we are building and a child node from + * a tree we are basing the new tree off of, if we already have a corresponding + * node in the parent's children cache, merge this node's counts with + * it. Otherwise, create the corresponding node, add it to the parent's children + * cache, and create the parent->child edge. + * + * @param {CensusTreeNodeCacheValue} parentCachevalue + * @param {CensusTreeNode} node + * + * @returns {CensusTreeNodeCacheValue} + * The new or extant child node's corresponding cache value. + */ +function insertOrMergeNode(parentCacheValue, node) { + if (!parentCacheValue.children) { + parentCacheValue.children = new CensusTreeNodeCache(); + } + + let val = CensusTreeNodeCache.lookupNode(parentCacheValue.children, node); + + if (val) { + // When inverting, it is possible that multiple leaves in the census report + // get merged into a single CensusTreeNode node. When this occurs, switch + // from a single index to a set of indices. + if (val.node.reportLeafIndex !== undefined && + val.node.reportLeafIndex !== node.reportLeafIndex) { + if (typeof val.node.reportLeafIndex === "number") { + const oldIndex = val.node.reportLeafIndex; + val.node.reportLeafIndex = new Set(); + val.node.reportLeafIndex.add(oldIndex); + val.node.reportLeafIndex.add(node.reportLeafIndex); + } else { + val.node.reportLeafIndex.add(node.reportLeafIndex); + } + } + + val.node.count += node.count; + val.node.bytes += node.bytes; + } else { + val = new CensusTreeNodeCacheValue(); + + val.node = new CensusTreeNode(node.name); + val.node.reportLeafIndex = node.reportLeafIndex; + val.node.count = node.count; + val.node.totalCount = node.totalCount; + val.node.bytes = node.bytes; + val.node.totalBytes = node.totalBytes; + + addChild(parentCacheValue.node, val.node); + CensusTreeNodeCache.insertNode(parentCacheValue.children, val); + } + + return val; +} + +/** + * Given an un-inverted CensusTreeNode tree, return the corresponding inverted + * CensusTreeNode tree. The input tree is not modified. The resulting inverted + * tree is sorted by self bytes rather than by total bytes. + * + * @param {CensusTreeNode} tree + * The un-inverted tree. + * + * @returns {CensusTreeNode} + * The corresponding inverted tree. + */ +function invert(tree) { + const inverted = new CensusTreeNodeCacheValue(); + inverted.node = new CensusTreeNode(null); + + // Do a depth-first search of the un-inverted tree. As we reach each leaf, + // take the path from the old root to the leaf, reverse that path, and add it + // to the new, inverted tree's root. + + const path = []; + (function addInvertedPaths(node) { + path.push(node); + + if (node.children) { + for (let i = 0, length = node.children.length; i < length; i++) { + addInvertedPaths(node.children[i]); + } + } else { + // We found a leaf node, add the reverse path to the inverted tree. + let currentCacheValue = inverted; + for (let i = path.length - 1; i >= 0; i--) { + currentCacheValue = insertOrMergeNode(currentCacheValue, path[i]); + } + } + + path.pop(); + }(tree)); + + // Ensure that the root node always has the totals. + inverted.node.totalBytes = tree.totalBytes; + inverted.node.totalCount = tree.totalCount; + + return inverted.node; +} + +/** + * Given a CensusTreeNode tree and predicate function, create the tree + * containing only the nodes in any path `(node_0, node_1, ..., node_n-1)` in + * the given tree where `predicate(node_j)` is true for `0 <= j < n`, `node_0` + * is the given tree's root, and `node_n-1` is a leaf in the given tree. The + * given tree is left unmodified. + * + * @param {CensusTreeNode} tree + * @param {Function} predicate + * + * @returns {CensusTreeNode} + */ +function filter(tree, predicate) { + const filtered = new CensusTreeNodeCacheValue(); + filtered.node = new CensusTreeNode(null); + + // Do a DFS over the given tree. If the predicate returns true for any node, + // add that node and its whole subtree to the filtered tree. + + const path = []; + let match = false; + + function addMatchingNodes(node) { + path.push(node); + + let oldMatch = match; + if (!match && predicate(node)) { + match = true; + } + + if (node.children) { + for (let i = 0, length = node.children.length; i < length; i++) { + addMatchingNodes(node.children[i]); + } + } else if (match) { + // We found a matching leaf node, add it to the filtered tree. + let currentCacheValue = filtered; + for (let i = 0, length = path.length; i < length; i++) { + currentCacheValue = insertOrMergeNode(currentCacheValue, path[i]); + } + } + + match = oldMatch; + path.pop(); + } + + if (tree.children) { + for (let i = 0, length = tree.children.length; i < length; i++) { + addMatchingNodes(tree.children[i]); + } + } + + filtered.node.count = tree.count; + filtered.node.totalCount = tree.totalCount; + filtered.node.bytes = tree.bytes; + filtered.node.totalBytes = tree.totalBytes; + + return filtered.node; +} + +/** + * Given a filter string, return a predicate function that takes a node and + * returns true iff the node matches the filter. + * + * @param {String} filterString + * @returns {Function} + */ +function makeFilterPredicate(filterString) { + return function (node) { + if (!node.name) { + return false; + } + + if (isSavedFrame(node.name)) { + return node.name.source.includes(filterString) + || (node.name.functionDisplayName || "").includes(filterString) + || (node.name.asyncCause || "").includes(filterString); + } + + return String(node.name).includes(filterString); + }; +} + +/** + * Takes a report from a census (`dbg.memory.takeCensus()`) and the breakdown + * used to generate the census and returns a structure used to render + * a tree to display the data. + * + * Returns a recursive "CensusTreeNode" object, looking like: + * + * CensusTreeNode = { + * // `children` if it exists, is sorted by `bytes`, if they are leaf nodes. + * children: ?[<CensusTreeNode...>], + * name: <?String> + * count: <?Number> + * bytes: <?Number> + * id: <?Number> + * parent: <?Number> + * } + * + * @param {Object} breakdown + * The breakdown used to generate the census report. + * + * @param {Object} report + * The census report generated with the specified breakdown. + * + * @param {Object} options + * Configuration options. + * - invert: Whether to invert the resulting tree or not. Defaults to + * false, ie uninverted. + * + * @returns {CensusTreeNode} + */ +exports.censusReportToCensusTreeNode = function (breakdown, report, + options = { + invert: false, + filter: null + }) { + // Reset the counter so that turning the same census report into a + // CensusTreeNode tree repeatedly is idempotent. + censusTreeNodeIdCounter = 0; + + const visitor = new CensusTreeNodeVisitor(); + walk(breakdown, report, visitor); + let result = visitor.root(); + + if (options.invert) { + result = invert(result); + } + + if (typeof options.filter === "string") { + result = filter(result, makeFilterPredicate(options.filter)); + } + + // If the report is a delta report that was generated by diffing two other + // reports, make sure to use the basis totals rather than the totals of the + // difference. + if (typeof report[basisTotalBytes] === "number") { + result.totalBytes = report[basisTotalBytes]; + result.totalCount = report[basisTotalCount]; + } + + // Inverting and filtering could have messed up the sort order, so do a + // depth-first search of the tree and ensure that siblings are sorted. + const comparator = options.invert ? compareBySelf : compareByTotal; + (function ensureSorted(node) { + if (node.children) { + node.children.sort(comparator); + for (let i = 0, length = node.children.length; i < length; i++) { + ensureSorted(node.children[i]); + } + } + }(result)); + + return result; +}; |