1// Copyright 2014 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5
6/**
7 * @constructor
8 * @param {!ProfilerAgent.CPUProfile} profile
9 */
10WebInspector.CPUProfileDataModel = function(profile)
11{
12    this.profileHead = profile.head;
13    this.samples = profile.samples;
14    this.timestamps = profile.timestamps;
15    this.profileStartTime = profile.startTime * 1000;
16    this.profileEndTime = profile.endTime * 1000;
17    this._assignParentsInProfile();
18    if (this.samples) {
19        this._normalizeTimestamps();
20        this._buildIdToNodeMap();
21        this._fixMissingSamples();
22    }
23    this._calculateTimes(profile);
24}
25
26/**
27 * @param {string} name
28 * @return {string}
29 */
30WebInspector.CPUProfileDataModel.beautifyFunctionName = function(name)
31{
32    return name || WebInspector.UIString("(anonymous function)");
33}
34
35WebInspector.CPUProfileDataModel.prototype = {
36    /**
37     * @param {!ProfilerAgent.CPUProfile} profile
38     */
39    _calculateTimes: function(profile)
40    {
41        function totalHitCount(node) {
42            var result = node.hitCount;
43            for (var i = 0; i < node.children.length; i++)
44                result += totalHitCount(node.children[i]);
45            return result;
46        }
47        profile.totalHitCount = totalHitCount(profile.head);
48
49        var duration = this.profileEndTime - this.profileStartTime;
50        var samplingInterval = duration / profile.totalHitCount;
51        this.samplingInterval = samplingInterval;
52
53        function calculateTimesForNode(node) {
54            node.selfTime = node.hitCount * samplingInterval;
55            var totalHitCount = node.hitCount;
56            for (var i = 0; i < node.children.length; i++)
57                totalHitCount += calculateTimesForNode(node.children[i]);
58            node.totalTime = totalHitCount * samplingInterval;
59            return totalHitCount;
60        }
61        calculateTimesForNode(profile.head);
62    },
63
64    _assignParentsInProfile: function()
65    {
66        var head = this.profileHead;
67        head.parent = null;
68        head.depth = -1;
69        this.maxDepth = 0;
70        var nodesToTraverse = [ head ];
71        while (nodesToTraverse.length) {
72            var parent = nodesToTraverse.pop();
73            var depth = parent.depth + 1;
74            if (depth > this.maxDepth)
75                this.maxDepth = depth;
76            var children = parent.children;
77            var length = children.length;
78            for (var i = 0; i < length; ++i) {
79                var child = children[i];
80                child.parent = parent;
81                child.depth = depth;
82                if (child.children.length)
83                    nodesToTraverse.push(child);
84            }
85        }
86    },
87
88    _normalizeTimestamps: function()
89    {
90        var timestamps = this.timestamps;
91        if (!timestamps) {
92            // Support loading old CPU profiles that are missing timestamps.
93            // Derive timestamps from profile start and stop times.
94            var profileStartTime = this.profileStartTime;
95            var interval = (this.profileEndTime - profileStartTime) / this.samples.length;
96            timestamps = new Float64Array(this.samples.length + 1);
97            for (var i = 0; i < timestamps.length; ++i)
98                timestamps[i] = profileStartTime + i * interval;
99            this.timestamps = timestamps;
100            return;
101        }
102
103        // Convert samples from usec to msec
104        for (var i = 0; i < timestamps.length; ++i)
105            timestamps[i] /= 1000;
106        var averageSample = (timestamps.peekLast() - timestamps[0]) / (timestamps.length - 1);
107        // Add an extra timestamp used to calculate the last sample duration.
108        this.timestamps.push(timestamps.peekLast() + averageSample);
109        this.profileStartTime = timestamps[0];
110        this.profileEndTime = timestamps.peekLast();
111    },
112
113    _buildIdToNodeMap: function()
114    {
115        /** @type {!Object.<number, !ProfilerAgent.CPUProfileNode>} */
116        this._idToNode = {};
117        var idToNode = this._idToNode;
118        var stack = [this.profileHead];
119        while (stack.length) {
120            var node = stack.pop();
121            idToNode[node.id] = node;
122            for (var i = 0; i < node.children.length; i++)
123                stack.push(node.children[i]);
124        }
125
126        var topLevelNodes = this.profileHead.children;
127        for (var i = 0; i < topLevelNodes.length && !(this.gcNode && this.programNode && this.idleNode); i++) {
128            var node = topLevelNodes[i];
129            if (node.functionName === "(garbage collector)")
130                this.gcNode = node;
131            else if (node.functionName === "(program)")
132                this.programNode = node;
133            else if (node.functionName === "(idle)")
134                this.idleNode = node;
135        }
136    },
137
138    _fixMissingSamples: function()
139    {
140        // Sometimes sampler is not able to parse the JS stack and returns
141        // a (program) sample instead. The issue leads to call frames belong
142        // to the same function invocation being split apart.
143        // Here's a workaround for that. When there's a single (program) sample
144        // between two call stacks sharing the same bottom node, it is replaced
145        // with the preceeding sample.
146        var samples = this.samples;
147        var samplesCount = samples.length;
148        if (!this.programNode || samplesCount < 3)
149            return;
150        var idToNode = this._idToNode;
151        var programNodeId = this.programNode.id;
152        var gcNodeId = this.gcNode ? this.gcNode.id : -1;
153        var idleNodeId = this.idleNode ? this.idleNode.id : -1;
154        var prevNodeId = samples[0];
155        var nodeId = samples[1];
156        for (var sampleIndex = 1; sampleIndex < samplesCount - 1; sampleIndex++) {
157            var nextNodeId = samples[sampleIndex + 1];
158            if (nodeId === programNodeId && !isSystemNode(prevNodeId) && !isSystemNode(nextNodeId)
159                && bottomNode(idToNode[prevNodeId]) === bottomNode(idToNode[nextNodeId])) {
160                samples[sampleIndex] = prevNodeId;
161            }
162            prevNodeId = nodeId;
163            nodeId = nextNodeId;
164        }
165
166        /**
167         * @param {!ProfilerAgent.CPUProfileNode} node
168         * @return {!ProfilerAgent.CPUProfileNode}
169         */
170        function bottomNode(node)
171        {
172            while (node.parent)
173                node = node.parent;
174            return node;
175        }
176
177        /**
178         * @param {number} nodeId
179         * @return {boolean}
180         */
181        function isSystemNode(nodeId)
182        {
183            return nodeId === programNodeId || nodeId === gcNodeId || nodeId === idleNodeId;
184        }
185    },
186
187    /**
188     * @param {function(number, !ProfilerAgent.CPUProfileNode, number)} openFrameCallback
189     * @param {function(number, !ProfilerAgent.CPUProfileNode, number, number, number)} closeFrameCallback
190     * @param {number=} startTime
191     * @param {number=} stopTime
192     */
193    forEachFrame: function(openFrameCallback, closeFrameCallback, startTime, stopTime)
194    {
195        if (!this.profileHead)
196            return;
197
198        startTime = startTime || 0;
199        stopTime = stopTime || Infinity;
200        var samples = this.samples;
201        var timestamps = this.timestamps;
202        var idToNode = this._idToNode;
203        var gcNode = this.gcNode;
204        var samplesCount = samples.length;
205        var startIndex = timestamps.lowerBound(startTime);
206        var stackTop = 0;
207        var stackNodes = [];
208        var prevId = this.profileHead.id;
209        var prevHeight = this.profileHead.depth;
210        var sampleTime = timestamps[samplesCount];
211        var gcParentNode = null;
212
213        if (!this._stackStartTimes)
214            this._stackStartTimes = new Float64Array(this.maxDepth + 2);
215        var stackStartTimes = this._stackStartTimes;
216        if (!this._stackChildrenDuration)
217            this._stackChildrenDuration = new Float64Array(this.maxDepth + 2);
218        var stackChildrenDuration = this._stackChildrenDuration;
219
220        for (var sampleIndex = startIndex; sampleIndex < samplesCount; sampleIndex++) {
221            sampleTime = timestamps[sampleIndex];
222            if (sampleTime >= stopTime)
223                break;
224            var id = samples[sampleIndex];
225            if (id === prevId)
226                continue;
227            var node = idToNode[id];
228            var prevNode = idToNode[prevId];
229
230            if (node === gcNode) {
231                // GC samples have no stack, so we just put GC node on top of the last recorded sample.
232                gcParentNode = prevNode;
233                openFrameCallback(gcParentNode.depth + 1, gcNode, sampleTime);
234                stackStartTimes[++stackTop] = sampleTime;
235                stackChildrenDuration[stackTop] = 0;
236                prevId = id;
237                continue;
238            }
239            if (prevNode === gcNode) {
240                // end of GC frame
241                var start = stackStartTimes[stackTop];
242                var duration = sampleTime - start;
243                stackChildrenDuration[stackTop - 1] += duration;
244                closeFrameCallback(gcParentNode.depth + 1, gcNode, start, duration, duration - stackChildrenDuration[stackTop]);
245                --stackTop;
246                prevNode = gcParentNode;
247                prevId = prevNode.id;
248                gcParentNode = null;
249            }
250
251            while (node.depth > prevNode.depth) {
252                stackNodes.push(node);
253                node = node.parent;
254            }
255
256            // Go down to the LCA and close current intervals.
257            while (prevNode !== node) {
258                var start = stackStartTimes[stackTop];
259                var duration = sampleTime - start;
260                stackChildrenDuration[stackTop - 1] += duration;
261                closeFrameCallback(prevNode.depth, prevNode, start, duration, duration - stackChildrenDuration[stackTop]);
262                --stackTop;
263                if (node.depth === prevNode.depth) {
264                    stackNodes.push(node);
265                    node = node.parent;
266                }
267                prevNode = prevNode.parent;
268            }
269
270            // Go up the nodes stack and open new intervals.
271            while (stackNodes.length) {
272                node = stackNodes.pop();
273                openFrameCallback(node.depth, node, sampleTime);
274                stackStartTimes[++stackTop] = sampleTime;
275                stackChildrenDuration[stackTop] = 0;
276            }
277
278            prevId = id;
279        }
280
281        if (idToNode[prevId] === gcNode) {
282            var start = stackStartTimes[stackTop];
283            var duration = sampleTime - start;
284            stackChildrenDuration[stackTop - 1] += duration;
285            closeFrameCallback(gcParentNode.depth + 1, node, start, duration, duration - stackChildrenDuration[stackTop]);
286            --stackTop;
287        }
288
289        for (var node = idToNode[prevId]; node.parent; node = node.parent) {
290            var start = stackStartTimes[stackTop];
291            var duration = sampleTime - start;
292            stackChildrenDuration[stackTop - 1] += duration;
293            closeFrameCallback(node.depth, node, start, duration, duration - stackChildrenDuration[stackTop]);
294            --stackTop;
295        }
296    },
297
298    /**
299     * @param {number} index
300     * @return {!ProfilerAgent.CPUProfileNode}
301     */
302    nodeByIndex: function(index)
303    {
304        return this._idToNode[this.samples[index]];
305    }
306
307}
308