From 5f8de423f190bbb79a62f804151bc24824fa32d8 Mon Sep 17 00:00:00 2001 From: "Matt A. Tobin" Date: Fri, 2 Feb 2018 04:16:08 -0500 Subject: Add m-esr52 at 52.6.0 --- .../performance/modules/logic/frame-utils.js | 478 ++++++++++++++++++ devtools/client/performance/modules/logic/jit.js | 342 +++++++++++++ .../client/performance/modules/logic/moz.build | 12 + .../client/performance/modules/logic/telemetry.js | 122 +++++ .../client/performance/modules/logic/tree-model.js | 556 +++++++++++++++++++++ .../performance/modules/logic/waterfall-utils.js | 167 +++++++ 6 files changed, 1677 insertions(+) create mode 100644 devtools/client/performance/modules/logic/frame-utils.js create mode 100644 devtools/client/performance/modules/logic/jit.js create mode 100644 devtools/client/performance/modules/logic/moz.build create mode 100644 devtools/client/performance/modules/logic/telemetry.js create mode 100644 devtools/client/performance/modules/logic/tree-model.js create mode 100644 devtools/client/performance/modules/logic/waterfall-utils.js (limited to 'devtools/client/performance/modules/logic') diff --git a/devtools/client/performance/modules/logic/frame-utils.js b/devtools/client/performance/modules/logic/frame-utils.js new file mode 100644 index 000000000..f82996be2 --- /dev/null +++ b/devtools/client/performance/modules/logic/frame-utils.js @@ -0,0 +1,478 @@ +/* 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 global = require("devtools/client/performance/modules/global"); +const demangle = require("devtools/client/shared/demangle"); +const { assert } = require("devtools/shared/DevToolsUtils"); +const { isChromeScheme, isContentScheme, parseURL } = + require("devtools/client/shared/source-utils"); + +const { CATEGORY_MASK, CATEGORY_MAPPINGS } = require("devtools/client/performance/modules/categories"); + +// Character codes used in various parsing helper functions. +const CHAR_CODE_R = "r".charCodeAt(0); +const CHAR_CODE_0 = "0".charCodeAt(0); +const CHAR_CODE_9 = "9".charCodeAt(0); +const CHAR_CODE_CAP_Z = "Z".charCodeAt(0); + +const CHAR_CODE_LPAREN = "(".charCodeAt(0); +const CHAR_CODE_RPAREN = ")".charCodeAt(0); +const CHAR_CODE_COLON = ":".charCodeAt(0); +const CHAR_CODE_SPACE = " ".charCodeAt(0); +const CHAR_CODE_UNDERSCORE = "_".charCodeAt(0); + +const EVAL_TOKEN = "%20%3E%20eval"; + +// The cache used to store inflated frames. +const gInflatedFrameStore = new WeakMap(); + +// The cache used to store frame data from `getInfo`. +const gFrameData = new WeakMap(); + +/** + * Parses the raw location of this function call to retrieve the actual + * function name, source url, host name, line and column. + */ +function parseLocation(location, fallbackLine, fallbackColumn) { + // Parse the `location` for the function name, source url, line, column etc. + + let line, column, url; + + // These two indices are used to extract the resource substring, which is + // location[parenIndex + 1 .. lineAndColumnIndex]. + // + // There are 3 variants of location strings in the profiler (with optional + // column numbers): + // 1) "name (resource:line)" + // 2) "resource:line" + // 3) "resource" + // + // For example for (1), take "foo (bar.js:1)". + // ^ ^ + // | | + // | | + // | | + // parenIndex will point to ------+ | + // | + // lineAndColumnIndex will point to -----+ + // + // For an example without parentheses, take "bar.js:2". + // ^ ^ + // | | + // parenIndex will point to ----------------+ | + // | + // lineAndColumIndex will point to ----------------+ + // + // To parse, we look for the last occurrence of the string ' ('. + // + // For 1), all occurrences of space ' ' characters in the resource string + // are urlencoded, so the last occurrence of ' (' is the separator between + // the function name and the resource. + // + // For 2) and 3), there can be no occurences of ' (' since ' ' characters + // are urlencoded in the resource string. + // + // XXX: Note that 3) is ambiguous with SPS marker locations like + // "EnterJIT". We can't distinguish the two, so we treat 3) like a function + // name. + let parenIndex = -1; + let lineAndColumnIndex = -1; + + let lastCharCode = location.charCodeAt(location.length - 1); + let i; + if (lastCharCode === CHAR_CODE_RPAREN) { + // Case 1) + i = location.length - 2; + } else if (isNumeric(lastCharCode)) { + // Case 2) + i = location.length - 1; + } else { + // Case 3) + i = 0; + } + + if (i !== 0) { + // Look for a :number. + let end = i; + while (isNumeric(location.charCodeAt(i))) { + i--; + } + if (location.charCodeAt(i) === CHAR_CODE_COLON) { + column = location.substr(i + 1, end - i); + i--; + } + + // Look for a preceding :number. + end = i; + while (isNumeric(location.charCodeAt(i))) { + i--; + } + + // If two were found, the first is the line and the second is the + // column. If only a single :number was found, then it is the line number. + if (location.charCodeAt(i) === CHAR_CODE_COLON) { + line = location.substr(i + 1, end - i); + lineAndColumnIndex = i; + i--; + } else { + lineAndColumnIndex = i + 1; + line = column; + column = undefined; + } + } + + // Look for the last occurrence of ' (' in case 1). + if (lastCharCode === CHAR_CODE_RPAREN) { + for (; i >= 0; i--) { + if (location.charCodeAt(i) === CHAR_CODE_LPAREN && + i > 0 && + location.charCodeAt(i - 1) === CHAR_CODE_SPACE) { + parenIndex = i; + break; + } + } + } + + let parsedUrl; + if (lineAndColumnIndex > 0) { + let resource = location.substring(parenIndex + 1, lineAndColumnIndex); + url = resource.split(" -> ").pop(); + if (url) { + parsedUrl = parseURL(url); + } + } + + let functionName, fileName, port, host; + line = line || fallbackLine; + column = column || fallbackColumn; + + // If the URL digged out from the `location` is valid, this is a JS frame. + if (parsedUrl) { + functionName = location.substring(0, parenIndex - 1); + fileName = parsedUrl.fileName; + port = parsedUrl.port; + host = parsedUrl.host; + + // Check for the case of the filename containing eval + // e.g. "file.js%20line%2065%20%3E%20eval" + let evalIndex = fileName.indexOf(EVAL_TOKEN); + if (evalIndex !== -1 && evalIndex === (fileName.length - EVAL_TOKEN.length)) { + // Match the filename + let evalLine = line; + let [, _fileName, , _line] = fileName.match(/(.+)(%20line%20(\d+)%20%3E%20eval)/) + || []; + fileName = `${_fileName} (eval:${evalLine})`; + line = _line; + assert(_fileName !== undefined, + "Filename could not be found from an eval location site"); + assert(_line !== undefined, + "Line could not be found from an eval location site"); + + // Match the url as well + [, url] = url.match(/(.+)( line (\d+) > eval)/) || []; + assert(url !== undefined, + "The URL could not be parsed correctly from an eval location site"); + } + } else { + functionName = location; + url = null; + } + + return { functionName, fileName, host, port, url, line, column }; +} + +/** + * Sets the properties of `isContent` and `category` on a frame. + * + * @param {InflatedFrame} frame + */ +function computeIsContentAndCategory(frame) { + // Only C++ stack frames have associated category information. + if (frame.category) { + return; + } + + let location = frame.location; + + // There are 3 variants of location strings in the profiler (with optional + // column numbers): + // 1) "name (resource:line)" + // 2) "resource:line" + // 3) "resource" + let lastCharCode = location.charCodeAt(location.length - 1); + let schemeStartIndex = -1; + if (lastCharCode === CHAR_CODE_RPAREN) { + // Case 1) + // + // Need to search for the last occurrence of ' (' to find the start of the + // resource string. + for (let i = location.length - 2; i >= 0; i--) { + if (location.charCodeAt(i) === CHAR_CODE_LPAREN && + i > 0 && + location.charCodeAt(i - 1) === CHAR_CODE_SPACE) { + schemeStartIndex = i + 1; + break; + } + } + } else { + // Cases 2) and 3) + schemeStartIndex = 0; + } + + if (isContentScheme(location, schemeStartIndex)) { + frame.isContent = true; + return; + } + + if (schemeStartIndex !== 0) { + for (let j = schemeStartIndex; j < location.length; j++) { + if (location.charCodeAt(j) === CHAR_CODE_R && + isChromeScheme(location, j) && + (location.indexOf("resource://devtools") !== -1 || + location.indexOf("resource://devtools") !== -1)) { + frame.category = CATEGORY_MASK("tools"); + return; + } + } + } + + if (location === "EnterJIT") { + frame.category = CATEGORY_MASK("js"); + return; + } + + frame.category = CATEGORY_MASK("other"); +} + +/** + * Get caches to cache inflated frames and computed frame keys of a frame + * table. + * + * @param object framesTable + * @return object + */ +function getInflatedFrameCache(frameTable) { + let inflatedCache = gInflatedFrameStore.get(frameTable); + if (inflatedCache !== undefined) { + return inflatedCache; + } + + // Fill with nulls to ensure no holes. + inflatedCache = Array.from({ length: frameTable.data.length }, () => null); + gInflatedFrameStore.set(frameTable, inflatedCache); + return inflatedCache; +} + +/** + * Get or add an inflated frame to a cache. + * + * @param object cache + * @param number index + * @param object frameTable + * @param object stringTable + */ +function getOrAddInflatedFrame(cache, index, frameTable, stringTable) { + let inflatedFrame = cache[index]; + if (inflatedFrame === null) { + inflatedFrame = cache[index] = new InflatedFrame(index, frameTable, stringTable); + } + return inflatedFrame; +} + +/** + * An intermediate data structured used to hold inflated frames. + * + * @param number index + * @param object frameTable + * @param object stringTable + */ +function InflatedFrame(index, frameTable, stringTable) { + const LOCATION_SLOT = frameTable.schema.location; + const IMPLEMENTATION_SLOT = frameTable.schema.implementation; + const OPTIMIZATIONS_SLOT = frameTable.schema.optimizations; + const LINE_SLOT = frameTable.schema.line; + const CATEGORY_SLOT = frameTable.schema.category; + + let frame = frameTable.data[index]; + let category = frame[CATEGORY_SLOT]; + this.location = stringTable[frame[LOCATION_SLOT]]; + this.implementation = frame[IMPLEMENTATION_SLOT]; + this.optimizations = frame[OPTIMIZATIONS_SLOT]; + this.line = frame[LINE_SLOT]; + this.column = undefined; + this.category = category; + this.isContent = false; + + // Attempt to compute if this frame is a content frame, and if not, + // its category. + // + // Since only C++ stack frames have associated category information, + // attempt to generate a useful category, fallback to the one provided + // by the profiling data, or fallback to an unknown category. + computeIsContentAndCategory(this); +} + +/** + * Gets the frame key (i.e., equivalence group) according to options. Content + * frames are always identified by location. Chrome frames are identified by + * location if content-only filtering is off. If content-filtering is on, they + * are identified by their category. + * + * @param object options + * @return string + */ +InflatedFrame.prototype.getFrameKey = function getFrameKey(options) { + if (this.isContent || !options.contentOnly || options.isRoot) { + options.isMetaCategoryOut = false; + return this.location; + } + + if (options.isLeaf) { + // We only care about leaf platform frames if we are displaying content + // only. If no category is present, give the default category of "other". + // + // 1. The leaf is where time is _actually_ being spent, so we _need_ to + // show it to developers in some way to give them accurate profiling + // data. We decide to split the platform into various category buckets + // and just show time spent in each bucket. + // + // 2. The calls leading to the leaf _aren't_ where we are spending time, + // but _do_ give the developer context for how they got to the leaf + // where they _are_ spending time. For non-platform hackers, the + // non-leaf platform frames don't give any meaningful context, and so we + // can safely filter them out. + options.isMetaCategoryOut = true; + return this.category; + } + + // Return an empty string denoting that this frame should be skipped. + return ""; +}; + +function isNumeric(c) { + return c >= CHAR_CODE_0 && c <= CHAR_CODE_9; +} + +function shouldDemangle(name) { + return name && name.charCodeAt && + name.charCodeAt(0) === CHAR_CODE_UNDERSCORE && + name.charCodeAt(1) === CHAR_CODE_UNDERSCORE && + name.charCodeAt(2) === CHAR_CODE_CAP_Z; +} + +/** + * Calculates the relative costs of this frame compared to a root, + * and generates allocations information if specified. Uses caching + * if possible. + * + * @param {ThreadNode|FrameNode} node + * The node we are calculating. + * @param {ThreadNode} options.root + * The root thread node to calculate relative costs. + * Generates [self|total] [duration|percentage] values. + * @param {boolean} options.allocations + * Generates `totalAllocations` and `selfAllocations`. + * + * @return {object} + */ +function getFrameInfo(node, options) { + let data = gFrameData.get(node); + + if (!data) { + if (node.nodeType === "Thread") { + data = Object.create(null); + data.functionName = global.L10N.getStr("table.root"); + } else { + data = parseLocation(node.location, node.line, node.column); + data.hasOptimizations = node.hasOptimizations(); + data.isContent = node.isContent; + data.isMetaCategory = node.isMetaCategory; + } + data.samples = node.youngestFrameSamples; + data.categoryData = CATEGORY_MAPPINGS[node.category] || {}; + data.nodeType = node.nodeType; + + // Frame name (function location or some meta information) + if (data.isMetaCategory) { + data.name = data.categoryData.label; + } else if (shouldDemangle(data.functionName)) { + data.name = demangle(data.functionName); + } else { + data.name = data.functionName; + } + + data.tooltiptext = data.isMetaCategory ? + data.categoryData.label : + node.location || ""; + + gFrameData.set(node, data); + } + + // If no options specified, we can't calculate relative values, abort here + if (!options) { + return data; + } + + // If a root specified, calculate the relative costs in the context of + // this call tree. The cached store may already have this, but generate + // if it does not. + let totalSamples = options.root.samples; + let totalDuration = options.root.duration; + if (options && options.root && !data.COSTS_CALCULATED) { + data.selfDuration = node.youngestFrameSamples / totalSamples * totalDuration; + data.selfPercentage = node.youngestFrameSamples / totalSamples * 100; + data.totalDuration = node.samples / totalSamples * totalDuration; + data.totalPercentage = node.samples / totalSamples * 100; + data.COSTS_CALCULATED = true; + } + + if (options && options.allocations && !data.ALLOCATION_DATA_CALCULATED) { + let totalBytes = options.root.byteSize; + data.selfCount = node.youngestFrameSamples; + data.totalCount = node.samples; + data.selfCountPercentage = node.youngestFrameSamples / totalSamples * 100; + data.totalCountPercentage = node.samples / totalSamples * 100; + data.selfSize = node.youngestFrameByteSize; + data.totalSize = node.byteSize; + data.selfSizePercentage = node.youngestFrameByteSize / totalBytes * 100; + data.totalSizePercentage = node.byteSize / totalBytes * 100; + data.ALLOCATION_DATA_CALCULATED = true; + } + + return data; +} + +exports.getFrameInfo = getFrameInfo; + +/** + * Takes an inverted ThreadNode and searches its youngest frames for + * a FrameNode with matching location. + * + * @param {ThreadNode} threadNode + * @param {string} location + * @return {?FrameNode} + */ +function findFrameByLocation(threadNode, location) { + if (!threadNode.inverted) { + throw new Error( + "FrameUtils.findFrameByLocation only supports leaf nodes in an inverted tree."); + } + + let calls = threadNode.calls; + for (let i = 0; i < calls.length; i++) { + if (calls[i].location === location) { + return calls[i]; + } + } + return null; +} + +exports.findFrameByLocation = findFrameByLocation; +exports.computeIsContentAndCategory = computeIsContentAndCategory; +exports.parseLocation = parseLocation; +exports.getInflatedFrameCache = getInflatedFrameCache; +exports.getOrAddInflatedFrame = getOrAddInflatedFrame; +exports.InflatedFrame = InflatedFrame; +exports.shouldDemangle = shouldDemangle; diff --git a/devtools/client/performance/modules/logic/jit.js b/devtools/client/performance/modules/logic/jit.js new file mode 100644 index 000000000..a958c3c4a --- /dev/null +++ b/devtools/client/performance/modules/logic/jit.js @@ -0,0 +1,342 @@ +/* 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"; + +// An outcome of an OptimizationAttempt that is considered successful. +const SUCCESSFUL_OUTCOMES = [ + "GenericSuccess", "Inlined", "DOM", "Monomorphic", "Polymorphic" +]; + +/** + * Model representing JIT optimization sites from the profiler + * for a frame (represented by a FrameNode). Requires optimization data from + * a profile, which is an array of RawOptimizationSites. + * + * When the ThreadNode for the profile iterates over the samples' frames, each + * frame's optimizations are accumulated in their respective FrameNodes. Each + * FrameNode may contain many different optimization sites. One sample may + * pick up optimization X on line Y in the frame, with the next sample + * containing optimization Z on line W in the same frame, as each frame is + * only function. + * + * An OptimizationSite contains a record of how many times the + * RawOptimizationSite was sampled, as well as the unique id based off of the + * original profiler array, and the RawOptimizationSite itself as a reference. + * @see devtools/client/performance/modules/logic/tree-model.js + * + * @struct RawOptimizationSite + * A structure describing a location in a script that was attempted to be optimized. + * Contains all the IonTypes observed, and the sequence of OptimizationAttempts that + * were attempted, and the line and column in the script. This is retrieved from the + * profiler after a recording, and our base data structure. Should always be referenced, + * and unmodified. + * + * Note that propertyName is an index into a string table, which needs to be + * provided in order for the raw optimization site to be inflated. + * + * @type {Array} types + * @type {Array} attempts + * @type {?number} propertyName + * @type {number} line + * @type {number} column + * + * + * @struct IonType + * IonMonkey attempts to classify each value in an optimization site by some type. + * Based off of the observed types for a value (like a variable that could be a + * string or an instance of an object), it determines what kind of type it should be + * classified as. Each IonType here contains an array of all ObservedTypes under `types`, + * the Ion type that IonMonkey decided this value should be (Int32, Object, etc.) as + * `mirType`, and the component of this optimization type that this value refers to -- + * like a "getter" optimization, `a[b]`, has site `a` (the "Receiver") and `b` + * (the "Index"). + * + * Generally the more ObservedTypes, the more deoptimized this OptimizationSite is. + * There could be no ObservedTypes, in which case `typeset` is undefined. + * + * @type {?Array} typeset + * @type {string} site + * @type {string} mirType + * + * + * @struct ObservedType + * When IonMonkey attempts to determine what type a value is, it checks on each sample. + * The ObservedType can be thought of in more of JavaScripty-terms, rather than C++. + * The `keyedBy` property is a high level description of the type, like "primitive", + * "constructor", "function", "singleton", "alloc-site" (that one is a bit more weird). + * If the `keyedBy` type is a function or constructor, the ObservedType should have a + * `name` property, referring to the function or constructor name from the JS source. + * If IonMonkey can determine the origin of this type (like where the constructor is + * defined), the ObservedType will also have `location` and `line` properties, but + * `location` can sometimes be non-URL strings like "self-hosted" or a memory location + * like "102ca7880", or no location at all, and maybe `line` is 0 or undefined. + * + * @type {string} keyedBy + * @type {?string} name + * @type {?string} location + * @type {?string} line + * + * + * @struct OptimizationAttempt + * Each RawOptimizationSite contains an array of OptimizationAttempts. Generally, + * IonMonkey goes through a series of strategies for each kind of optimization, starting + * from most-niche and optimized, to the less-optimized, but more general strategies -- + * for example, a getter opt may first try to optimize for the scenario of a getter on an + * `arguments` object -- that will fail most of the time, as most objects are not + * arguments objects, but it will attempt several strategies in order until it finds a + * strategy that works, or fails. Even in the best scenarios, some attempts will fail + * (like the arguments getter example), which is OK, as long as some attempt succeeds + * (with the earlier attempts preferred, as those are more optimized). In an + * OptimizationAttempt structure, we store just the `strategy` name and `outcome` name, + * both from enums in js/public/TrackedOptimizationInfo.h as TRACKED_STRATEGY_LIST and + * TRACKED_OUTCOME_LIST, respectively. An array of successful outcome strings are above + * in SUCCESSFUL_OUTCOMES. + * + * @see js/public/TrackedOptimizationInfo.h + * + * @type {string} strategy + * @type {string} outcome + */ + +/* + * A wrapper around RawOptimizationSite to record sample count and ID (referring to the + * index of where this is in the initially seeded optimizations data), so we don't mutate + * the original data from the profiler. Provides methods to access the underlying + * optimization data easily, so understanding the semantics of JIT data isn't necessary. + * + * @constructor + * + * @param {Array} optimizations + * @param {number} optsIndex + * + * @type {RawOptimizationSite} data + * @type {number} samples + * @type {number} id + */ + +const OptimizationSite = function (id, opts) { + this.id = id; + this.data = opts; + this.samples = 1; +}; + +/** + * Constructor for JITOptimizations. A collection of OptimizationSites for a frame. + * + * @constructor + * @param {Array} rawSites + * Array of raw optimization sites. + * @param {Array} stringTable + * Array of strings from the profiler used to inflate + * JIT optimizations. Do not modify this! + */ + +const JITOptimizations = function (rawSites, stringTable) { + // Build a histogram of optimization sites. + let sites = []; + + for (let rawSite of rawSites) { + let existingSite = sites.find((site) => site.data === rawSite); + if (existingSite) { + existingSite.samples++; + } else { + sites.push(new OptimizationSite(sites.length, rawSite)); + } + } + + // Inflate the optimization information. + for (let site of sites) { + let data = site.data; + let STRATEGY_SLOT = data.attempts.schema.strategy; + let OUTCOME_SLOT = data.attempts.schema.outcome; + let attempts = data.attempts.data.map((a) => { + return { + id: site.id, + strategy: stringTable[a[STRATEGY_SLOT]], + outcome: stringTable[a[OUTCOME_SLOT]] + }; + }); + let types = data.types.map((t) => { + let typeset = maybeTypeset(t.typeset, stringTable); + if (typeset) { + typeset.forEach(ts => { + ts.id = site.id; + }); + } + + return { + id: site.id, + typeset, + site: stringTable[t.site], + mirType: stringTable[t.mirType] + }; + }); + // Add IDs to to all children objects, so we can correllate sites when + // just looking at a specific type, attempt, etc.. + attempts.id = types.id = site.id; + + site.data = { + attempts, + types, + propertyName: maybeString(stringTable, data.propertyName), + line: data.line, + column: data.column + }; + } + + this.optimizationSites = sites.sort((a, b) => b.samples - a.samples); +}; + +/** + * Make JITOptimizations iterable. + */ +JITOptimizations.prototype = { + [Symbol.iterator]: function* () { + yield* this.optimizationSites; + }, + + get length() { + return this.optimizationSites.length; + } +}; + +/** + * Takes an "outcome" string from an OptimizationAttempt and returns + * a boolean indicating whether or not its a successful outcome. + * + * @return {boolean} + */ + +function isSuccessfulOutcome(outcome) { + return !!~SUCCESSFUL_OUTCOMES.indexOf(outcome); +} + +/** + * Takes an OptimizationSite. Returns a boolean indicating if the passed + * in OptimizationSite has a "good" outcome at the end of its attempted strategies. + * + * @param {OptimizationSite} optimizationSite + * @return {boolean} + */ + +function hasSuccessfulOutcome(optimizationSite) { + let attempts = optimizationSite.data.attempts; + let lastOutcome = attempts[attempts.length - 1].outcome; + return isSuccessfulOutcome(lastOutcome); +} + +function maybeString(stringTable, index) { + return index ? stringTable[index] : undefined; +} + +function maybeTypeset(typeset, stringTable) { + if (!typeset) { + return undefined; + } + return typeset.map((ty) => { + return { + keyedBy: maybeString(stringTable, ty.keyedBy), + name: maybeString(stringTable, ty.name), + location: maybeString(stringTable, ty.location), + line: ty.line + }; + }); +} + +// Map of optimization implementation names to an enum. +const IMPLEMENTATION_MAP = { + "interpreter": 0, + "baseline": 1, + "ion": 2 +}; +const IMPLEMENTATION_NAMES = Object.keys(IMPLEMENTATION_MAP); + +/** + * Takes data from a FrameNode and computes rendering positions for + * a stacked mountain graph, to visualize JIT optimization tiers over time. + * + * @param {FrameNode} frameNode + * The FrameNode who's optimizations we're iterating. + * @param {Array} sampleTimes + * An array of every sample time within the range we're counting. + * From a ThreadNode's `sampleTimes` property. + * @param {number} bucketSize + * Size of each bucket in milliseconds. + * `duration / resolution = bucketSize` in OptimizationsGraph. + * @return {?Array} + */ +function createTierGraphDataFromFrameNode(frameNode, sampleTimes, bucketSize) { + let tierData = frameNode.getTierData(); + let stringTable = frameNode._stringTable; + let output = []; + let implEnum; + + let tierDataIndex = 0; + let nextOptSample = tierData[tierDataIndex]; + + // Bucket data + let samplesInCurrentBucket = 0; + let currentBucketStartTime = sampleTimes[0]; + let bucket = []; + + // Store previous data point so we can have straight vertical lines + let previousValues; + + // Iterate one after the samples, so we can finalize the last bucket + for (let i = 0; i <= sampleTimes.length; i++) { + let sampleTime = sampleTimes[i]; + + // If this sample is in the next bucket, or we're done + // checking sampleTimes and on the last iteration, finalize previous bucket + if (sampleTime >= (currentBucketStartTime + bucketSize) || + i >= sampleTimes.length) { + let dataPoint = {}; + dataPoint.values = []; + dataPoint.delta = currentBucketStartTime; + + // Map the opt site counts as a normalized percentage (0-1) + // of its count in context of total samples this bucket + for (let j = 0; j < IMPLEMENTATION_NAMES.length; j++) { + dataPoint.values[j] = (bucket[j] || 0) / (samplesInCurrentBucket || 1); + } + + // Push the values from the previous bucket to the same time + // as the current bucket so we get a straight vertical line. + if (previousValues) { + let data = Object.create(null); + data.values = previousValues; + data.delta = currentBucketStartTime; + output.push(data); + } + + output.push(dataPoint); + + // Set the new start time of this bucket and reset its count + currentBucketStartTime += bucketSize; + samplesInCurrentBucket = 0; + previousValues = dataPoint.values; + bucket = []; + } + + // If this sample observed an optimization in this frame, record it + if (nextOptSample && nextOptSample.time === sampleTime) { + // If no implementation defined, it was the "interpreter". + implEnum = IMPLEMENTATION_MAP[stringTable[nextOptSample.implementation] || + "interpreter"]; + bucket[implEnum] = (bucket[implEnum] || 0) + 1; + nextOptSample = tierData[++tierDataIndex]; + } + + samplesInCurrentBucket++; + } + + return output; +} + +exports.createTierGraphDataFromFrameNode = createTierGraphDataFromFrameNode; +exports.OptimizationSite = OptimizationSite; +exports.JITOptimizations = JITOptimizations; +exports.hasSuccessfulOutcome = hasSuccessfulOutcome; +exports.isSuccessfulOutcome = isSuccessfulOutcome; +exports.SUCCESSFUL_OUTCOMES = SUCCESSFUL_OUTCOMES; diff --git a/devtools/client/performance/modules/logic/moz.build b/devtools/client/performance/modules/logic/moz.build new file mode 100644 index 000000000..179cd71b3 --- /dev/null +++ b/devtools/client/performance/modules/logic/moz.build @@ -0,0 +1,12 @@ +# vim: set filetype=python: +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +DevToolsModules( + 'frame-utils.js', + 'jit.js', + 'telemetry.js', + 'tree-model.js', + 'waterfall-utils.js', +) diff --git a/devtools/client/performance/modules/logic/telemetry.js b/devtools/client/performance/modules/logic/telemetry.js new file mode 100644 index 000000000..b8e322170 --- /dev/null +++ b/devtools/client/performance/modules/logic/telemetry.js @@ -0,0 +1,122 @@ +/* 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 Telemetry = require("devtools/client/shared/telemetry"); +const flags = require("devtools/shared/flags"); +const EVENTS = require("devtools/client/performance/events"); + +const EVENT_MAP_FLAGS = new Map([ + [EVENTS.RECORDING_IMPORTED, "DEVTOOLS_PERFTOOLS_RECORDING_IMPORT_FLAG"], + [EVENTS.RECORDING_EXPORTED, "DEVTOOLS_PERFTOOLS_RECORDING_EXPORT_FLAG"], +]); + +const RECORDING_FEATURES = [ + "withMarkers", "withTicks", "withMemory", "withAllocations" +]; + +const SELECTED_VIEW_HISTOGRAM_NAME = "DEVTOOLS_PERFTOOLS_SELECTED_VIEW_MS"; + +function PerformanceTelemetry(emitter) { + this._emitter = emitter; + this._telemetry = new Telemetry(); + this.onFlagEvent = this.onFlagEvent.bind(this); + this.onRecordingStateChange = this.onRecordingStateChange.bind(this); + this.onViewSelected = this.onViewSelected.bind(this); + + for (let [event] of EVENT_MAP_FLAGS) { + this._emitter.on(event, this.onFlagEvent); + } + + this._emitter.on(EVENTS.RECORDING_STATE_CHANGE, this.onRecordingStateChange); + this._emitter.on(EVENTS.UI_DETAILS_VIEW_SELECTED, this.onViewSelected); + + if (flags.testing) { + this.recordLogs(); + } +} + +PerformanceTelemetry.prototype.destroy = function () { + if (this._previousView) { + this._telemetry.stopTimer(SELECTED_VIEW_HISTOGRAM_NAME, this._previousView); + } + + this._telemetry.destroy(); + for (let [event] of EVENT_MAP_FLAGS) { + this._emitter.off(event, this.onFlagEvent); + } + this._emitter.off(EVENTS.RECORDING_STATE_CHANGE, this.onRecordingStateChange); + this._emitter.off(EVENTS.UI_DETAILS_VIEW_SELECTED, this.onViewSelected); + this._emitter = null; +}; + +PerformanceTelemetry.prototype.onFlagEvent = function (eventName, ...data) { + this._telemetry.log(EVENT_MAP_FLAGS.get(eventName), true); +}; + +PerformanceTelemetry.prototype.onRecordingStateChange = function (_, status, model) { + if (status != "recording-stopped") { + return; + } + + if (model.isConsole()) { + this._telemetry.log("DEVTOOLS_PERFTOOLS_CONSOLE_RECORDING_COUNT", true); + } else { + this._telemetry.log("DEVTOOLS_PERFTOOLS_RECORDING_COUNT", true); + } + + this._telemetry.log("DEVTOOLS_PERFTOOLS_RECORDING_DURATION_MS", model.getDuration()); + + let config = model.getConfiguration(); + for (let k in config) { + if (RECORDING_FEATURES.indexOf(k) !== -1) { + this._telemetry.logKeyed("DEVTOOLS_PERFTOOLS_RECORDING_FEATURES_USED", k, + config[k]); + } + } +}; + +PerformanceTelemetry.prototype.onViewSelected = function (_, viewName) { + if (this._previousView) { + this._telemetry.stopTimer(SELECTED_VIEW_HISTOGRAM_NAME, this._previousView); + } + this._previousView = viewName; + this._telemetry.startTimer(SELECTED_VIEW_HISTOGRAM_NAME); +}; + +/** + * Utility to record histogram calls to this instance. + * Should only be used in testing mode; throws otherwise. + */ +PerformanceTelemetry.prototype.recordLogs = function () { + if (!flags.testing) { + throw new Error("Can only record telemetry logs in tests."); + } + + let originalLog = this._telemetry.log; + let originalLogKeyed = this._telemetry.logKeyed; + this._log = {}; + + this._telemetry.log = (function (histo, data) { + let results = this._log[histo] = this._log[histo] || []; + results.push(data); + originalLog(histo, data); + }).bind(this); + + this._telemetry.logKeyed = (function (histo, key, data) { + let results = this._log[histo] = this._log[histo] || []; + results.push([key, data]); + originalLogKeyed(histo, key, data); + }).bind(this); +}; + +PerformanceTelemetry.prototype.getLogs = function () { + if (!flags.testing) { + throw new Error("Can only get telemetry logs in tests."); + } + + return this._log; +}; + +exports.PerformanceTelemetry = PerformanceTelemetry; diff --git a/devtools/client/performance/modules/logic/tree-model.js b/devtools/client/performance/modules/logic/tree-model.js new file mode 100644 index 000000000..b6376ee8a --- /dev/null +++ b/devtools/client/performance/modules/logic/tree-model.js @@ -0,0 +1,556 @@ +/* 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 { JITOptimizations } = require("devtools/client/performance/modules/logic/jit"); +const FrameUtils = require("devtools/client/performance/modules/logic/frame-utils"); + +/** + * A call tree for a thread. This is essentially a linkage between all frames + * of all samples into a single tree structure, with additional information + * on each node, like the time spent (in milliseconds) and samples count. + * + * @param object thread + * The raw thread object received from the backend. Contains samples, + * stackTable, frameTable, and stringTable. + * @param object options + * Additional supported options + * - number startTime + * - number endTime + * - boolean contentOnly [optional] + * - boolean invertTree [optional] + * - boolean flattenRecursion [optional] + */ +function ThreadNode(thread, options = {}) { + if (options.endTime == void 0 || options.startTime == void 0) { + throw new Error("ThreadNode requires both `startTime` and `endTime`."); + } + this.samples = 0; + this.sampleTimes = []; + this.youngestFrameSamples = 0; + this.calls = []; + this.duration = options.endTime - options.startTime; + this.nodeType = "Thread"; + this.inverted = options.invertTree; + + // Total bytesize of all allocations if enabled + this.byteSize = 0; + this.youngestFrameByteSize = 0; + + let { samples, stackTable, frameTable, stringTable } = thread; + + // Nothing to do if there are no samples. + if (samples.data.length === 0) { + return; + } + + this._buildInverted(samples, stackTable, frameTable, stringTable, options); + if (!options.invertTree) { + this._uninvert(); + } +} + +ThreadNode.prototype = { + /** + * Build an inverted call tree from profile samples. The format of the + * samples is described in tools/profiler/ProfileEntry.h, under the heading + * "ThreadProfile JSON Format". + * + * The profile data is naturally presented inverted. Inverting the call tree + * is also the default in the Performance tool. + * + * @param object samples + * The raw samples array received from the backend. + * @param object stackTable + * The table of deduplicated stacks from the backend. + * @param object frameTable + * The table of deduplicated frames from the backend. + * @param object stringTable + * The table of deduplicated strings from the backend. + * @param object options + * Additional supported options + * - number startTime + * - number endTime + * - boolean contentOnly [optional] + * - boolean invertTree [optional] + */ + _buildInverted: function buildInverted(samples, stackTable, frameTable, stringTable, + options) { + function getOrAddFrameNode(calls, isLeaf, frameKey, inflatedFrame, isMetaCategory, + leafTable) { + // Insert the inflated frame into the call tree at the current level. + let frameNode; + + // Leaf nodes have fan out much greater than non-leaf nodes, thus the + // use of a hash table. Otherwise, do linear search. + // + // Note that this method is very hot, thus the manual looping over + // Array.prototype.find. + if (isLeaf) { + frameNode = leafTable[frameKey]; + } else { + for (let i = 0; i < calls.length; i++) { + if (calls[i].key === frameKey) { + frameNode = calls[i]; + break; + } + } + } + + if (!frameNode) { + frameNode = new FrameNode(frameKey, inflatedFrame, isMetaCategory); + if (isLeaf) { + leafTable[frameKey] = frameNode; + } + calls.push(frameNode); + } + + return frameNode; + } + + const SAMPLE_STACK_SLOT = samples.schema.stack; + const SAMPLE_TIME_SLOT = samples.schema.time; + const SAMPLE_BYTESIZE_SLOT = samples.schema.size; + + const STACK_PREFIX_SLOT = stackTable.schema.prefix; + const STACK_FRAME_SLOT = stackTable.schema.frame; + + const getOrAddInflatedFrame = FrameUtils.getOrAddInflatedFrame; + + let samplesData = samples.data; + let stacksData = stackTable.data; + + // Caches. + let inflatedFrameCache = FrameUtils.getInflatedFrameCache(frameTable); + let leafTable = Object.create(null); + + let startTime = options.startTime; + let endTime = options.endTime; + let flattenRecursion = options.flattenRecursion; + + // Reused options object passed to InflatedFrame.prototype.getFrameKey. + let mutableFrameKeyOptions = { + contentOnly: options.contentOnly, + isRoot: false, + isLeaf: false, + isMetaCategoryOut: false + }; + + let byteSize = 0; + for (let i = 0; i < samplesData.length; i++) { + let sample = samplesData[i]; + let sampleTime = sample[SAMPLE_TIME_SLOT]; + + if (SAMPLE_BYTESIZE_SLOT !== void 0) { + byteSize = sample[SAMPLE_BYTESIZE_SLOT]; + } + + // A sample's end time is considered to be its time of sampling. Its + // start time is the sampling time of the previous sample. + // + // Thus, we compare sampleTime <= start instead of < to filter out + // samples that end exactly at the start time. + if (!sampleTime || sampleTime <= startTime || sampleTime > endTime) { + continue; + } + + let stackIndex = sample[SAMPLE_STACK_SLOT]; + let calls = this.calls; + let prevCalls = this.calls; + let prevFrameKey; + let isLeaf = mutableFrameKeyOptions.isLeaf = true; + let skipRoot = options.invertTree; + + // Inflate the stack and build the FrameNode call tree directly. + // + // In the profiler data, each frame's stack is referenced by an index + // into stackTable. + // + // Each entry in stackTable is a pair [ prefixIndex, frameIndex ]. The + // prefixIndex is itself an index into stackTable, referencing the + // prefix of the current stack (that is, the younger frames). In other + // words, the stackTable is encoded as a trie of the inverted + // callstack. The frameIndex is an index into frameTable, describing the + // frame at the current depth. + // + // This algorithm inflates each frame in the frame table while walking + // the stack trie as described above. + // + // The frame key is then computed from the inflated frame /and/ the + // current depth in the FrameNode call tree. That is, the frame key is + // not wholly determinable from just the inflated frame. + // + // For content frames, the frame key is just its location. For chrome + // frames, the key may be a metacategory or its location, depending on + // rendering options and its position in the FrameNode call tree. + // + // The frame key is then used to build up the inverted FrameNode call + // tree. + // + // Note that various filtering functions, such as filtering for content + // frames or flattening recursion, are inlined into the stack inflation + // loop. This is important for performance as it avoids intermediate + // structures and multiple passes. + while (stackIndex !== null) { + let stackEntry = stacksData[stackIndex]; + let frameIndex = stackEntry[STACK_FRAME_SLOT]; + + // Fetch the stack prefix (i.e. older frames) index. + stackIndex = stackEntry[STACK_PREFIX_SLOT]; + + // Do not include the (root) node in this sample, as the costs of each frame + // will make it clear to differentiate (root)->B vs (root)->A->B + // when a tree is inverted, a revert of bug 1147604 + if (stackIndex === null && skipRoot) { + break; + } + + // Inflate the frame. + let inflatedFrame = getOrAddInflatedFrame(inflatedFrameCache, frameIndex, + frameTable, stringTable); + + // Compute the frame key. + mutableFrameKeyOptions.isRoot = stackIndex === null; + let frameKey = inflatedFrame.getFrameKey(mutableFrameKeyOptions); + + // An empty frame key means this frame should be skipped. + if (frameKey === "") { + continue; + } + + // If we shouldn't flatten the current frame into the previous one, advance a + // level in the call tree. + let shouldFlatten = flattenRecursion && frameKey === prevFrameKey; + if (!shouldFlatten) { + calls = prevCalls; + } + + let frameNode = getOrAddFrameNode(calls, isLeaf, frameKey, inflatedFrame, + mutableFrameKeyOptions.isMetaCategoryOut, + leafTable); + if (isLeaf) { + frameNode.youngestFrameSamples++; + frameNode._addOptimizations(inflatedFrame.optimizations, + inflatedFrame.implementation, sampleTime, + stringTable); + + if (byteSize) { + frameNode.youngestFrameByteSize += byteSize; + } + } + + // Don't overcount flattened recursive frames. + if (!shouldFlatten) { + frameNode.samples++; + if (byteSize) { + frameNode.byteSize += byteSize; + } + } + + prevFrameKey = frameKey; + prevCalls = frameNode.calls; + isLeaf = mutableFrameKeyOptions.isLeaf = false; + } + + this.samples++; + this.sampleTimes.push(sampleTime); + if (byteSize) { + this.byteSize += byteSize; + } + } + }, + + /** + * Uninverts the call tree after its having been built. + */ + _uninvert: function uninvert() { + function mergeOrAddFrameNode(calls, node, samples, size) { + // Unlike the inverted call tree, we don't use a root table for the top + // level, as in general, there are many fewer entry points than + // leaves. Instead, linear search is used regardless of level. + for (let i = 0; i < calls.length; i++) { + if (calls[i].key === node.key) { + let foundNode = calls[i]; + foundNode._merge(node, samples, size); + return foundNode.calls; + } + } + let copy = node._clone(samples, size); + calls.push(copy); + return copy.calls; + } + + let workstack = [{ node: this, level: 0 }]; + let spine = []; + let entry; + + // The new root. + let rootCalls = []; + + // Walk depth-first and keep the current spine (e.g., callstack). + do { + entry = workstack.pop(); + if (entry) { + spine[entry.level] = entry; + + let node = entry.node; + let calls = node.calls; + let callSamples = 0; + let callByteSize = 0; + + // Continue the depth-first walk. + for (let i = 0; i < calls.length; i++) { + workstack.push({ node: calls[i], level: entry.level + 1 }); + callSamples += calls[i].samples; + callByteSize += calls[i].byteSize; + } + + // The sample delta is used to distinguish stacks. + // + // Suppose we have the following stack samples: + // + // A -> B + // A -> C + // A + // + // The inverted tree is: + // + // A + // / \ + // B C + // + // with A.samples = 3, B.samples = 1, C.samples = 1. + // + // A is distinguished as being its own stack because + // A.samples - (B.samples + C.samples) > 0. + // + // Note that bottoming out is a degenerate where callSamples = 0. + + let samplesDelta = node.samples - callSamples; + let byteSizeDelta = node.byteSize - callByteSize; + if (samplesDelta > 0) { + // Reverse the spine and add them to the uninverted call tree. + let uninvertedCalls = rootCalls; + for (let level = entry.level; level > 0; level--) { + let callee = spine[level]; + uninvertedCalls = mergeOrAddFrameNode(uninvertedCalls, callee.node, + samplesDelta, byteSizeDelta); + } + } + } + } while (entry); + + // Replace the toplevel calls with rootCalls, which now contains the + // uninverted roots. + this.calls = rootCalls; + }, + + /** + * Gets additional details about this node. + * @see FrameNode.prototype.getInfo for more information. + * + * @return object + */ + getInfo: function (options) { + return FrameUtils.getFrameInfo(this, options); + }, + + /** + * Mimicks the interface of FrameNode, and a ThreadNode can never have + * optimization data (at the moment, anyway), so provide a function + * to return null so we don't need to check if a frame node is a thread + * or not everytime we fetch optimization data. + * + * @return {null} + */ + + hasOptimizations: function () { + return null; + } +}; + +/** + * A function call node in a tree. Represents a function call with a unique context, + * resulting in each FrameNode having its own row in the corresponding tree view. + * Take samples: + * A()->B()->C() + * A()->B() + * Q()->B() + * + * In inverted tree, A()->B()->C() would have one frame node, and A()->B() and + * Q()->B() would share a frame node. + * In an uninverted tree, A()->B()->C() and A()->B() would share a frame node, + * with Q()->B() having its own. + * + * In all cases, all the frame nodes originated from the same InflatedFrame. + * + * @param string frameKey + * The key associated with this frame. The key determines identity of + * the node. + * @param string location + * The location of this function call. Note that this isn't sanitized, + * so it may very well (not?) include the function name, url, etc. + * @param number line + * The line number inside the source containing this function call. + * @param number category + * The category type of this function call ("js", "graphics" etc.). + * @param number allocations + * The number of memory allocations performed in this frame. + * @param number isContent + * Whether this frame is content. + * @param boolean isMetaCategory + * Whether or not this is a platform node that should appear as a + * generalized meta category or not. + */ +function FrameNode(frameKey, { location, line, category, isContent }, isMetaCategory) { + this.key = frameKey; + this.location = location; + this.line = line; + this.youngestFrameSamples = 0; + this.samples = 0; + this.calls = []; + this.isContent = !!isContent; + this._optimizations = null; + this._tierData = []; + this._stringTable = null; + this.isMetaCategory = !!isMetaCategory; + this.category = category; + this.nodeType = "Frame"; + this.byteSize = 0; + this.youngestFrameByteSize = 0; +} + +FrameNode.prototype = { + /** + * Take optimization data observed for this frame. + * + * @param object optimizationSite + * Any JIT optimization information attached to the current + * sample. Lazily inflated via stringTable. + * @param number implementation + * JIT implementation used for this observed frame (baseline, ion); + * can be null indicating "interpreter" + * @param number time + * The time this optimization occurred. + * @param object stringTable + * The string table used to inflate the optimizationSite. + */ + _addOptimizations: function (site, implementation, time, stringTable) { + // Simply accumulate optimization sites for now. Processing is done lazily + // by JITOptimizations, if optimization information is actually displayed. + if (site) { + let opts = this._optimizations; + if (opts === null) { + opts = this._optimizations = []; + } + opts.push(site); + } + + if (!this._stringTable) { + this._stringTable = stringTable; + } + + // Record type of implementation used and the sample time + this._tierData.push({ implementation, time }); + }, + + _clone: function (samples, size) { + let newNode = new FrameNode(this.key, this, this.isMetaCategory); + newNode._merge(this, samples, size); + return newNode; + }, + + _merge: function (otherNode, samples, size) { + if (this === otherNode) { + return; + } + + this.samples += samples; + this.byteSize += size; + if (otherNode.youngestFrameSamples > 0) { + this.youngestFrameSamples += samples; + } + + if (otherNode.youngestFrameByteSize > 0) { + this.youngestFrameByteSize += otherNode.youngestFrameByteSize; + } + + if (this._stringTable === null) { + this._stringTable = otherNode._stringTable; + } + + if (otherNode._optimizations) { + if (!this._optimizations) { + this._optimizations = []; + } + let opts = this._optimizations; + let otherOpts = otherNode._optimizations; + for (let i = 0; i < otherOpts.length; i++) { + opts.push(otherOpts[i]); + } + } + + if (otherNode._tierData.length) { + let tierData = this._tierData; + let otherTierData = otherNode._tierData; + for (let i = 0; i < otherTierData.length; i++) { + tierData.push(otherTierData[i]); + } + tierData.sort((a, b) => a.time - b.time); + } + }, + + /** + * Returns the parsed location and additional data describing + * this frame. Uses cached data if possible. Takes the following + * options: + * + * @param {ThreadNode} options.root + * The root thread node to calculate relative costs. + * Generates [self|total] [duration|percentage] values. + * @param {boolean} options.allocations + * Generates `totalAllocations` and `selfAllocations`. + * + * @return object + * The computed { name, file, url, line } properties for this + * function call, as well as additional params if options specified. + */ + getInfo: function (options) { + return FrameUtils.getFrameInfo(this, options); + }, + + /** + * Returns whether or not the frame node has an JITOptimizations model. + * + * @return {Boolean} + */ + hasOptimizations: function () { + return !this.isMetaCategory && !!this._optimizations; + }, + + /** + * Returns the underlying JITOptimizations model representing + * the optimization attempts occuring in this frame. + * + * @return {JITOptimizations|null} + */ + getOptimizations: function () { + if (!this._optimizations) { + return null; + } + return new JITOptimizations(this._optimizations, this._stringTable); + }, + + /** + * Returns the tiers used overtime. + * + * @return {Array} + */ + getTierData: function () { + return this._tierData; + } +}; + +exports.ThreadNode = ThreadNode; +exports.FrameNode = FrameNode; diff --git a/devtools/client/performance/modules/logic/waterfall-utils.js b/devtools/client/performance/modules/logic/waterfall-utils.js new file mode 100644 index 000000000..04c05a544 --- /dev/null +++ b/devtools/client/performance/modules/logic/waterfall-utils.js @@ -0,0 +1,167 @@ +/* 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"; + +/** + * Utility functions for collapsing markers into a waterfall. + */ + +const { extend } = require("sdk/util/object"); +const { MarkerBlueprintUtils } = require("devtools/client/performance/modules/marker-blueprint-utils"); + +/** + * Creates a parent marker, which functions like a regular marker, + * but is able to hold additional child markers. + * + * The marker is seeded with values from `marker`. + * @param object marker + * @return object + */ +function createParentNode(marker) { + return extend(marker, { submarkers: [] }); +} + +/** + * Collapses markers into a tree-like structure. + * @param object rootNode + * @param array markersList + * @param array filter + */ +function collapseMarkersIntoNode({ rootNode, markersList, filter }) { + let { + getCurrentParentNode, + pushNode, + popParentNode + } = createParentNodeFactory(rootNode); + + for (let i = 0, len = markersList.length; i < len; i++) { + let curr = markersList[i]; + + // If this marker type should not be displayed, just skip + if (!MarkerBlueprintUtils.shouldDisplayMarker(curr, filter)) { + continue; + } + + let parentNode = getCurrentParentNode(); + let blueprint = MarkerBlueprintUtils.getBlueprintFor(curr); + + let nestable = "nestable" in blueprint ? blueprint.nestable : true; + let collapsible = "collapsible" in blueprint ? blueprint.collapsible : true; + + let finalized = false; + + // Extend the marker with extra properties needed in the marker tree + let extendedProps = { index: i }; + if (collapsible) { + extendedProps.submarkers = []; + } + curr = extend(curr, extendedProps); + + // If not nestible, just push it inside the root node. Additionally, + // markers originating outside the main thread are considered to be + // "never collapsible", to avoid confusion. + // A beter solution would be to collapse every marker with its siblings + // from the same thread, but that would require a thread id attached + // to all markers, which is potentially expensive and rather useless at + // the moment, since we don't really have that many OTMT markers. + if (!nestable || curr.isOffMainThread) { + pushNode(rootNode, curr); + continue; + } + + // First off, if any parent nodes exist, finish them off + // recursively upwards if this marker is outside their ranges and nestable. + while (!finalized && parentNode) { + // If this marker is eclipsed by the current parent marker, + // make it a child of the current parent and stop going upwards. + // If the markers aren't from the same process, attach them to the root + // node as well. Every process has its own main thread. + if (nestable && + curr.start >= parentNode.start && + curr.end <= parentNode.end && + curr.processType == parentNode.processType) { + pushNode(parentNode, curr); + finalized = true; + break; + } + + // If this marker is still nestable, but outside of the range + // of the current parent, iterate upwards on the next parent + // and finalize the current parent. + if (nestable) { + popParentNode(); + parentNode = getCurrentParentNode(); + continue; + } + } + + if (!finalized) { + pushNode(rootNode, curr); + } + } +} + +/** + * Takes a root marker node and creates a hash of functions used + * to manage the creation and nesting of additional parent markers. + * + * @param {object} root + * @return {object} + */ +function createParentNodeFactory(root) { + let parentMarkers = []; + let factory = { + /** + * Pops the most recent parent node off the stack, finalizing it. + * Sets the `end` time based on the most recent child if not defined. + */ + popParentNode: () => { + if (parentMarkers.length === 0) { + throw new Error("Cannot pop parent markers when none exist."); + } + + let lastParent = parentMarkers.pop(); + + // If this finished parent marker doesn't have an end time, + // so probably a synthesized marker, use the last marker's end time. + if (lastParent.end == void 0) { + lastParent.end = lastParent.submarkers[lastParent.submarkers.length - 1].end; + } + + // If no children were ever pushed into this parent node, + // remove its submarkers so it behaves like a non collapsible + // node. + if (!lastParent.submarkers.length) { + delete lastParent.submarkers; + } + + return lastParent; + }, + + /** + * Returns the most recent parent node. + */ + getCurrentParentNode: () => parentMarkers.length + ? parentMarkers[parentMarkers.length - 1] + : null, + + /** + * Push this marker into the most recent parent node. + */ + pushNode: (parent, marker) => { + parent.submarkers.push(marker); + + // If pushing a parent marker, track it as the top of + // the parent stack. + if (marker.submarkers) { + parentMarkers.push(marker); + } + } + }; + + return factory; +} + +exports.createParentNode = createParentNode; +exports.collapseMarkersIntoNode = collapseMarkersIntoNode; -- cgit v1.2.3