src/third_party/WebKit/Source/devtools/front_end/profiler/heap_snapshot_worker/AllocationProfile.js

   1 /*
   2  * Copyright (C) 2013 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 /**
  32  * @constructor
  33  */
  34 WebInspector.AllocationProfile = function(profile, liveObjectStats)
  35 {
  36     this._strings = profile.strings;
  37     this._liveObjectStats = liveObjectStats;
  38
  39     this._nextNodeId = 1;
  40     this._functionInfos = []
  41     this._idToNode = {};
  42     this._idToTopDownNode = {};
  43     this._collapsedTopNodeIdToFunctionInfo = {};
  44
  45     this._traceTops = null;
  46
  47     this._buildFunctionAllocationInfos(profile);
  48     this._traceTree = this._buildAllocationTree(profile, liveObjectStats);
  49 }
  50
  51 WebInspector.AllocationProfile.prototype = {
  52     _buildFunctionAllocationInfos: function(profile)
  53     {
  54         var strings = this._strings;
  55
  56         var functionInfoFields = profile.snapshot.meta.trace_function_info_fields;
  57         var functionIdOffset = functionInfoFields.indexOf("function_id");
  58         var functionNameOffset = functionInfoFields.indexOf("name");
  59         var scriptNameOffset = functionInfoFields.indexOf("script_name");
  60         var scriptIdOffset = functionInfoFields.indexOf("script_id");
  61         var lineOffset = functionInfoFields.indexOf("line");
  62         var columnOffset = functionInfoFields.indexOf("column");
  63         var functionInfoFieldCount = functionInfoFields.length;
  64
  65         var rawInfos = profile.trace_function_infos;
  66         var infoLength = rawInfos.length;
  67         var functionInfos = this._functionInfos = new Array(infoLength / functionInfoFieldCount);
  68         var index = 0;
  69         for (var i = 0; i < infoLength; i += functionInfoFieldCount) {
  70             functionInfos[index++] = new WebInspector.FunctionAllocationInfo(
  71                 strings[rawInfos[i + functionNameOffset]],
  72                 strings[rawInfos[i + scriptNameOffset]],
  73                 rawInfos[i + scriptIdOffset],
  74                 rawInfos[i + lineOffset],
  75                 rawInfos[i + columnOffset]);
  76         }
  77     },
  78
  79     _buildAllocationTree: function(profile, liveObjectStats)
  80     {
  81         var traceTreeRaw = profile.trace_tree;
  82         var functionInfos = this._functionInfos;
  83         var idToTopDownNode = this._idToTopDownNode;
  84
  85         var traceNodeFields = profile.snapshot.meta.trace_node_fields;
  86         var nodeIdOffset = traceNodeFields.indexOf("id");
  87         var functionInfoIndexOffset = traceNodeFields.indexOf("function_info_index");
  88         var allocationCountOffset = traceNodeFields.indexOf("count");
  89         var allocationSizeOffset = traceNodeFields.indexOf("size");
  90         var childrenOffset = traceNodeFields.indexOf("children");
  91         var nodeFieldCount = traceNodeFields.length;
  92
  93         function traverseNode(rawNodeArray, nodeOffset, parent)
  94         {
  95             var functionInfo = functionInfos[rawNodeArray[nodeOffset + functionInfoIndexOffset]];
  96             var id = rawNodeArray[nodeOffset + nodeIdOffset];
  97             var stats = liveObjectStats[id];
  98             var liveCount = stats ? stats.count : 0;
  99             var liveSize = stats ? stats.size : 0;
 100             var result = new WebInspector.TopDownAllocationNode(
 101                 id,
 102                 functionInfo,
 103                 rawNodeArray[nodeOffset + allocationCountOffset],
 104                 rawNodeArray[nodeOffset + allocationSizeOffset],
 105                 liveCount,
 106                 liveSize,
 107                 parent);
 108             idToTopDownNode[id] = result;
 109             functionInfo.addTraceTopNode(result);
 110
 111             var rawChildren = rawNodeArray[nodeOffset + childrenOffset];
 112             for (var i = 0; i < rawChildren.length; i += nodeFieldCount) {
 113                 result.children.push(traverseNode(rawChildren, i, result));
 114             }
 115             return result;
 116         }
 117
 118         return traverseNode(traceTreeRaw, 0, null);
 119     },
 120
 121     /**
 122      * @return {!Array.<!WebInspector.HeapSnapshotCommon.SerializedAllocationNode>}
 123      */
 124     serializeTraceTops: function()
 125     {
 126         if (this._traceTops)
 127             return this._traceTops;
 128         var result = this._traceTops = [];
 129         var functionInfos = this._functionInfos;
 130         for (var i = 0; i < functionInfos.length; i++) {
 131             var info = functionInfos[i];
 132             if (info.totalCount === 0)
 133                 continue;
 134             var nodeId = this._nextNodeId++;
 135             var isRoot = i == 0;
 136             result.push(this._serializeNode(
 137                 nodeId,
 138                 info,
 139                 info.totalCount,
 140                 info.totalSize,
 141                 info.totalLiveCount,
 142                 info.totalLiveSize,
 143                 !isRoot));
 144             this._collapsedTopNodeIdToFunctionInfo[nodeId] = info;
 145         }
 146         result.sort(function(a, b) {
 147             return b.size - a.size;
 148         });
 149         return result;
 150     },
 151
 152     /**
 153      * @param {number} nodeId
 154      * @return {!WebInspector.HeapSnapshotCommon.AllocationNodeCallers}
 155      */
 156     serializeCallers: function(nodeId)
 157     {
 158         var node = this._ensureBottomUpNode(nodeId);
 159         var nodesWithSingleCaller = [];
 160         while (node.callers().length === 1) {
 161             node = node.callers()[0];
 162             nodesWithSingleCaller.push(this._serializeCaller(node));
 163         }
 164
 165         var branchingCallers = [];
 166         var callers = node.callers();
 167         for (var i = 0; i < callers.length; i++) {
 168             branchingCallers.push(this._serializeCaller(callers[i]));
 169         }
 170         return new WebInspector.HeapSnapshotCommon.AllocationNodeCallers(nodesWithSingleCaller, branchingCallers);
 171     },
 172
 173     /**
 174      * @param {number} traceNodeId
 175      * @return {!Array.<!WebInspector.HeapSnapshotCommon.AllocationStackFrame>}
 176      */
 177     serializeAllocationStack: function(traceNodeId)
 178     {
 179         var node = this._idToTopDownNode[traceNodeId];
 180         var result = [];
 181         while (node) {
 182             var functionInfo = node.functionInfo;
 183             result.push(new WebInspector.HeapSnapshotCommon.AllocationStackFrame(
 184                 functionInfo.functionName,
 185                 functionInfo.scriptName,
 186                 functionInfo.scriptId,
 187                 functionInfo.line,
 188                 functionInfo.column
 189             ));
 190             node = node.parent;
 191         }
 192         return result;
 193     },
 194
 195     /**
 196      * @param {number} allocationNodeId
 197      * @return {!Array.<number>}
 198      */
 199     traceIds: function(allocationNodeId)
 200     {
 201         return this._ensureBottomUpNode(allocationNodeId).traceTopIds;
 202     },
 203
 204     /**
 205      * @param {number} nodeId
 206      * @return {!WebInspector.BottomUpAllocationNode}
 207      */
 208     _ensureBottomUpNode: function(nodeId)
 209     {
 210         var node = this._idToNode[nodeId];
 211         if (!node) {
 212             var functionInfo = this._collapsedTopNodeIdToFunctionInfo[nodeId];
 213             node = functionInfo.bottomUpRoot();
 214             delete this._collapsedTopNodeIdToFunctionInfo[nodeId];
 215             this._idToNode[nodeId] = node;
 216         }
 217         return node;
 218     },
 219
 220     /**
 221      * @param {!WebInspector.BottomUpAllocationNode} node
 222      * @return {!WebInspector.HeapSnapshotCommon.SerializedAllocationNode}
 223      */
 224     _serializeCaller: function(node)
 225     {
 226         var callerId = this._nextNodeId++;
 227         this._idToNode[callerId] = node;
 228         return this._serializeNode(
 229             callerId,
 230             node.functionInfo,
 231             node.allocationCount,
 232             node.allocationSize,
 233             node.liveCount,
 234             node.liveSize,
 235             node.hasCallers());
 236     },
 237
 238     /**
 239      * @param {number} nodeId
 240      * @param {!WebInspector.FunctionAllocationInfo} functionInfo
 241      * @param {number} count
 242      * @param {number} size
 243      * @param {number} liveCount
 244      * @param {number} liveSize
 245      * @param {boolean} hasChildren
 246      * @return {!WebInspector.HeapSnapshotCommon.SerializedAllocationNode}
 247      */
 248     _serializeNode: function(nodeId, functionInfo, count, size, liveCount, liveSize, hasChildren)
 249     {
 250         return new WebInspector.HeapSnapshotCommon.SerializedAllocationNode(
 251             nodeId,
 252             functionInfo.functionName,
 253             functionInfo.scriptName,
 254             functionInfo.scriptId,
 255             functionInfo.line,
 256             functionInfo.column,
 257             count,
 258             size,
 259             liveCount,
 260             liveSize,
 261             hasChildren
 262         );
 263     }
 264 }
 265
 266
 267 /**
 268  * @constructor
 269  * @param {number} id
 270  * @param {!WebInspector.FunctionAllocationInfo} functionInfo
 271  * @param {number} count
 272  * @param {number} size
 273  * @param {number} liveCount
 274  * @param {number} liveSize
 275  * @param {?WebInspector.TopDownAllocationNode} parent
 276  */
 277 WebInspector.TopDownAllocationNode = function(id, functionInfo, count, size, liveCount, liveSize, parent)
 278 {
 279     this.id = id;
 280     this.functionInfo = functionInfo;
 281     this.allocationCount = count;
 282     this.allocationSize = size;
 283     this.liveCount = liveCount;
 284     this.liveSize = liveSize;
 285     this.parent = parent;
 286     this.children = [];
 287 }
 288
 289
 290 /**
 291  * @constructor
 292  * @param {!WebInspector.FunctionAllocationInfo} functionInfo
 293  */
 294 WebInspector.BottomUpAllocationNode = function(functionInfo)
 295 {
 296     this.functionInfo = functionInfo;
 297     this.allocationCount = 0;
 298     this.allocationSize = 0;
 299     this.liveCount = 0;
 300     this.liveSize = 0;
 301     this.traceTopIds = [];
 302     this._callers = [];
 303 }
 304
 305
 306 WebInspector.BottomUpAllocationNode.prototype = {
 307     /**
 308      * @param {!WebInspector.TopDownAllocationNode} traceNode
 309      * @return {!WebInspector.BottomUpAllocationNode}
 310      */
 311     addCaller: function(traceNode)
 312     {
 313         var functionInfo = traceNode.functionInfo;
 314         var result;
 315         for (var i = 0; i < this._callers.length; i++) {
 316             var caller = this._callers[i];
 317             if (caller.functionInfo === functionInfo) {
 318                 result = caller;
 319                 break;
 320             }
 321         }
 322         if (!result) {
 323             result = new WebInspector.BottomUpAllocationNode(functionInfo);
 324             this._callers.push(result);
 325         }
 326         return result;
 327     },
 328
 329     /**
 330      * @return {!Array.<!WebInspector.BottomUpAllocationNode>}
 331      */
 332     callers: function()
 333     {
 334         return this._callers;
 335     },
 336
 337     /**
 338      * @return {boolean}
 339      */
 340     hasCallers: function()
 341     {
 342         return this._callers.length > 0;
 343     }
 344 }
 345
 346
 347 /**
 348  * @constructor
 349  * @param {string} functionName
 350  * @param {string} scriptName
 351  * @param {number} scriptId
 352  * @param {number} line
 353  * @param {number} column
 354  */
 355 WebInspector.FunctionAllocationInfo = function(functionName, scriptName, scriptId, line, column)
 356 {
 357     this.functionName = functionName;
 358     this.scriptName = scriptName;
 359     this.scriptId = scriptId;
 360     this.line = line;
 361     this.column = column;
 362     this.totalCount = 0;
 363     this.totalSize = 0;
 364     this.totalLiveCount = 0;
 365     this.totalLiveSize = 0;
 366     this._traceTops = [];
 367 }
 368
 369 WebInspector.FunctionAllocationInfo.prototype = {
 370     /**
 371      * @param {!WebInspector.TopDownAllocationNode} node
 372      */
 373     addTraceTopNode: function(node)
 374     {
 375         if (node.allocationCount === 0)
 376             return;
 377         this._traceTops.push(node);
 378         this.totalCount += node.allocationCount;
 379         this.totalSize += node.allocationSize;
 380         this.totalLiveCount += node.liveCount;
 381         this.totalLiveSize += node.liveSize;
 382     },
 383
 384     /**
 385      * @return {?WebInspector.BottomUpAllocationNode}
 386      */
 387     bottomUpRoot: function()
 388     {
 389         if (!this._traceTops.length)
 390             return null;
 391         if (!this._bottomUpTree)
 392             this._buildAllocationTraceTree();
 393         return this._bottomUpTree;
 394     },
 395
 396     _buildAllocationTraceTree: function()
 397     {
 398         this._bottomUpTree = new WebInspector.BottomUpAllocationNode(this);
 399
 400         for (var i = 0; i < this._traceTops.length; i++) {
 401             var node = this._traceTops[i];
 402             var bottomUpNode = this._bottomUpTree;
 403             var count = node.allocationCount;
 404             var size = node.allocationSize;
 405             var liveCount = node.liveCount;
 406             var liveSize = node.liveSize;
 407             var traceId = node.id;
 408             while (true) {
 409                 bottomUpNode.allocationCount += count;
 410                 bottomUpNode.allocationSize += size;
 411                 bottomUpNode.liveCount += liveCount;
 412                 bottomUpNode.liveSize += liveSize;
 413                 bottomUpNode.traceTopIds.push(traceId);
 414                 node = node.parent;
 415                 if (node === null) {
 416                     break;
 417                 }
 418                 bottomUpNode = bottomUpNode.addCaller(node);
 419             }
 420         }
 421     }
 422 }