1 // Copyright 2009 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 29 /** 30 * Creates a profile object for processing profiling-related events 31 * and calculating function execution times. 32 * 33 * @constructor 34 */ 35 function Profile() { 36 this.codeMap_ = new CodeMap(); 37 this.topDownTree_ = new CallTree(); 38 this.bottomUpTree_ = new CallTree(); 39 }; 40 41 42 /** 43 * Returns whether a function with the specified name must be skipped. 44 * Should be overriden by subclasses. 45 * 46 * @param {string} name Function name. 47 */ 48 Profile.prototype.skipThisFunction = function(name) { 49 return false; 50 }; 51 52 53 /** 54 * Enum for profiler operations that involve looking up existing 55 * code entries. 56 * 57 * @enum {number} 58 */ 59 Profile.Operation = { 60 MOVE: 0, 61 DELETE: 1, 62 TICK: 2 63 }; 64 65 66 /** 67 * Enum for code state regarding its dynamic optimization. 68 * 69 * @enum {number} 70 */ 71 Profile.CodeState = { 72 COMPILED: 0, 73 OPTIMIZABLE: 1, 74 OPTIMIZED: 2 75 }; 76 77 78 /** 79 * Called whenever the specified operation has failed finding a function 80 * containing the specified address. Should be overriden by subclasses. 81 * See the Profile.Operation enum for the list of 82 * possible operations. 83 * 84 * @param {number} operation Operation. 85 * @param {number} addr Address of the unknown code. 86 * @param {number} opt_stackPos If an unknown address is encountered 87 * during stack strace processing, specifies a position of the frame 88 * containing the address. 89 */ 90 Profile.prototype.handleUnknownCode = function( 91 operation, addr, opt_stackPos) { 92 }; 93 94 95 /** 96 * Registers a library. 97 * 98 * @param {string} name Code entry name. 99 * @param {number} startAddr Starting address. 100 * @param {number} endAddr Ending address. 101 */ 102 Profile.prototype.addLibrary = function( 103 name, startAddr, endAddr) { 104 var entry = new CodeMap.CodeEntry( 105 endAddr - startAddr, name); 106 this.codeMap_.addLibrary(startAddr, entry); 107 return entry; 108 }; 109 110 111 /** 112 * Registers statically compiled code entry. 113 * 114 * @param {string} name Code entry name. 115 * @param {number} startAddr Starting address. 116 * @param {number} endAddr Ending address. 117 */ 118 Profile.prototype.addStaticCode = function( 119 name, startAddr, endAddr) { 120 var entry = new CodeMap.CodeEntry( 121 endAddr - startAddr, name); 122 this.codeMap_.addStaticCode(startAddr, entry); 123 return entry; 124 }; 125 126 127 /** 128 * Registers dynamic (JIT-compiled) code entry. 129 * 130 * @param {string} type Code entry type. 131 * @param {string} name Code entry name. 132 * @param {number} start Starting address. 133 * @param {number} size Code entry size. 134 */ 135 Profile.prototype.addCode = function( 136 type, name, start, size) { 137 var entry = new Profile.DynamicCodeEntry(size, type, name); 138 this.codeMap_.addCode(start, entry); 139 return entry; 140 }; 141 142 143 /** 144 * Registers dynamic (JIT-compiled) code entry. 145 * 146 * @param {string} type Code entry type. 147 * @param {string} name Code entry name. 148 * @param {number} start Starting address. 149 * @param {number} size Code entry size. 150 * @param {number} funcAddr Shared function object address. 151 * @param {Profile.CodeState} state Optimization state. 152 */ 153 Profile.prototype.addFuncCode = function( 154 type, name, start, size, funcAddr, state) { 155 // As code and functions are in the same address space, 156 // it is safe to put them in a single code map. 157 var func = this.codeMap_.findDynamicEntryByStartAddress(funcAddr); 158 if (!func) { 159 func = new Profile.FunctionEntry(name); 160 this.codeMap_.addCode(funcAddr, func); 161 } else if (func.name !== name) { 162 // Function object has been overwritten with a new one. 163 func.name = name; 164 } 165 var entry = this.codeMap_.findDynamicEntryByStartAddress(start); 166 if (entry) { 167 if (entry.size === size && entry.func === func) { 168 // Entry state has changed. 169 entry.state = state; 170 } 171 } else { 172 entry = new Profile.DynamicFuncCodeEntry(size, type, func, state); 173 this.codeMap_.addCode(start, entry); 174 } 175 return entry; 176 }; 177 178 179 /** 180 * Reports about moving of a dynamic code entry. 181 * 182 * @param {number} from Current code entry address. 183 * @param {number} to New code entry address. 184 */ 185 Profile.prototype.moveCode = function(from, to) { 186 try { 187 this.codeMap_.moveCode(from, to); 188 } catch (e) { 189 this.handleUnknownCode(Profile.Operation.MOVE, from); 190 } 191 }; 192 193 194 /** 195 * Reports about deletion of a dynamic code entry. 196 * 197 * @param {number} start Starting address. 198 */ 199 Profile.prototype.deleteCode = function(start) { 200 try { 201 this.codeMap_.deleteCode(start); 202 } catch (e) { 203 this.handleUnknownCode(Profile.Operation.DELETE, start); 204 } 205 }; 206 207 208 /** 209 * Reports about moving of a dynamic code entry. 210 * 211 * @param {number} from Current code entry address. 212 * @param {number} to New code entry address. 213 */ 214 Profile.prototype.moveFunc = function(from, to) { 215 if (this.codeMap_.findDynamicEntryByStartAddress(from)) { 216 this.codeMap_.moveCode(from, to); 217 } 218 }; 219 220 221 /** 222 * Retrieves a code entry by an address. 223 * 224 * @param {number} addr Entry address. 225 */ 226 Profile.prototype.findEntry = function(addr) { 227 return this.codeMap_.findEntry(addr); 228 }; 229 230 231 /** 232 * Records a tick event. Stack must contain a sequence of 233 * addresses starting with the program counter value. 234 * 235 * @param {Array<number>} stack Stack sample. 236 */ 237 Profile.prototype.recordTick = function(stack) { 238 var processedStack = this.resolveAndFilterFuncs_(stack); 239 this.bottomUpTree_.addPath(processedStack); 240 processedStack.reverse(); 241 this.topDownTree_.addPath(processedStack); 242 }; 243 244 245 /** 246 * Translates addresses into function names and filters unneeded 247 * functions. 248 * 249 * @param {Array<number>} stack Stack sample. 250 */ 251 Profile.prototype.resolveAndFilterFuncs_ = function(stack) { 252 var result = []; 253 for (var i = 0; i < stack.length; ++i) { 254 var entry = this.codeMap_.findEntry(stack[i]); 255 if (entry) { 256 var name = entry.getName(); 257 if (!this.skipThisFunction(name)) { 258 result.push(name); 259 } 260 } else { 261 this.handleUnknownCode( 262 Profile.Operation.TICK, stack[i], i); 263 } 264 } 265 return result; 266 }; 267 268 269 /** 270 * Performs a BF traversal of the top down call graph. 271 * 272 * @param {function(CallTree.Node)} f Visitor function. 273 */ 274 Profile.prototype.traverseTopDownTree = function(f) { 275 this.topDownTree_.traverse(f); 276 }; 277 278 279 /** 280 * Performs a BF traversal of the bottom up call graph. 281 * 282 * @param {function(CallTree.Node)} f Visitor function. 283 */ 284 Profile.prototype.traverseBottomUpTree = function(f) { 285 this.bottomUpTree_.traverse(f); 286 }; 287 288 289 /** 290 * Calculates a top down profile for a node with the specified label. 291 * If no name specified, returns the whole top down calls tree. 292 * 293 * @param {string} opt_label Node label. 294 */ 295 Profile.prototype.getTopDownProfile = function(opt_label) { 296 return this.getTreeProfile_(this.topDownTree_, opt_label); 297 }; 298 299 300 /** 301 * Calculates a bottom up profile for a node with the specified label. 302 * If no name specified, returns the whole bottom up calls tree. 303 * 304 * @param {string} opt_label Node label. 305 */ 306 Profile.prototype.getBottomUpProfile = function(opt_label) { 307 return this.getTreeProfile_(this.bottomUpTree_, opt_label); 308 }; 309 310 311 /** 312 * Helper function for calculating a tree profile. 313 * 314 * @param {Profile.CallTree} tree Call tree. 315 * @param {string} opt_label Node label. 316 */ 317 Profile.prototype.getTreeProfile_ = function(tree, opt_label) { 318 if (!opt_label) { 319 tree.computeTotalWeights(); 320 return tree; 321 } else { 322 var subTree = tree.cloneSubtree(opt_label); 323 subTree.computeTotalWeights(); 324 return subTree; 325 } 326 }; 327 328 329 /** 330 * Calculates a flat profile of callees starting from a node with 331 * the specified label. If no name specified, starts from the root. 332 * 333 * @param {string} opt_label Starting node label. 334 */ 335 Profile.prototype.getFlatProfile = function(opt_label) { 336 var counters = new CallTree(); 337 var rootLabel = opt_label || CallTree.ROOT_NODE_LABEL; 338 var precs = {}; 339 precs[rootLabel] = 0; 340 var root = counters.findOrAddChild(rootLabel); 341 342 this.topDownTree_.computeTotalWeights(); 343 this.topDownTree_.traverseInDepth( 344 function onEnter(node) { 345 if (!(node.label in precs)) { 346 precs[node.label] = 0; 347 } 348 var nodeLabelIsRootLabel = node.label == rootLabel; 349 if (nodeLabelIsRootLabel || precs[rootLabel] > 0) { 350 if (precs[rootLabel] == 0) { 351 root.selfWeight += node.selfWeight; 352 root.totalWeight += node.totalWeight; 353 } else { 354 var rec = root.findOrAddChild(node.label); 355 rec.selfWeight += node.selfWeight; 356 if (nodeLabelIsRootLabel || precs[node.label] == 0) { 357 rec.totalWeight += node.totalWeight; 358 } 359 } 360 precs[node.label]++; 361 } 362 }, 363 function onExit(node) { 364 if (node.label == rootLabel || precs[rootLabel] > 0) { 365 precs[node.label]--; 366 } 367 }, 368 null); 369 370 if (!opt_label) { 371 // If we have created a flat profile for the whole program, we don't 372 // need an explicit root in it. Thus, replace the counters tree 373 // root with the node corresponding to the whole program. 374 counters.root_ = root; 375 } else { 376 // Propagate weights so percents can be calculated correctly. 377 counters.getRoot().selfWeight = root.selfWeight; 378 counters.getRoot().totalWeight = root.totalWeight; 379 } 380 return counters; 381 }; 382 383 384 /** 385 * Cleans up function entries that are not referenced by code entries. 386 */ 387 Profile.prototype.cleanUpFuncEntries = function() { 388 var referencedFuncEntries = []; 389 var entries = this.codeMap_.getAllDynamicEntriesWithAddresses(); 390 for (var i = 0, l = entries.length; i < l; ++i) { 391 if (entries[i][1].constructor === Profile.FunctionEntry) { 392 entries[i][1].used = false; 393 } 394 } 395 for (var i = 0, l = entries.length; i < l; ++i) { 396 if ("func" in entries[i][1]) { 397 entries[i][1].func.used = true; 398 } 399 } 400 for (var i = 0, l = entries.length; i < l; ++i) { 401 if (entries[i][1].constructor === Profile.FunctionEntry && 402 !entries[i][1].used) { 403 this.codeMap_.deleteCode(entries[i][0]); 404 } 405 } 406 }; 407 408 409 /** 410 * Creates a dynamic code entry. 411 * 412 * @param {number} size Code size. 413 * @param {string} type Code type. 414 * @param {string} name Function name. 415 * @constructor 416 */ 417 Profile.DynamicCodeEntry = function(size, type, name) { 418 CodeMap.CodeEntry.call(this, size, name); 419 this.type = type; 420 }; 421 422 423 /** 424 * Returns node name. 425 */ 426 Profile.DynamicCodeEntry.prototype.getName = function() { 427 return this.type + ': ' + this.name; 428 }; 429 430 431 /** 432 * Returns raw node name (without type decoration). 433 */ 434 Profile.DynamicCodeEntry.prototype.getRawName = function() { 435 return this.name; 436 }; 437 438 439 Profile.DynamicCodeEntry.prototype.isJSFunction = function() { 440 return false; 441 }; 442 443 444 Profile.DynamicCodeEntry.prototype.toString = function() { 445 return this.getName() + ': ' + this.size.toString(16); 446 }; 447 448 449 /** 450 * Creates a dynamic code entry. 451 * 452 * @param {number} size Code size. 453 * @param {string} type Code type. 454 * @param {Profile.FunctionEntry} func Shared function entry. 455 * @param {Profile.CodeState} state Code optimization state. 456 * @constructor 457 */ 458 Profile.DynamicFuncCodeEntry = function(size, type, func, state) { 459 CodeMap.CodeEntry.call(this, size); 460 this.type = type; 461 this.func = func; 462 this.state = state; 463 }; 464 465 Profile.DynamicFuncCodeEntry.STATE_PREFIX = ["", "~", "*"]; 466 467 /** 468 * Returns node name. 469 */ 470 Profile.DynamicFuncCodeEntry.prototype.getName = function() { 471 var name = this.func.getName(); 472 return this.type + ': ' + Profile.DynamicFuncCodeEntry.STATE_PREFIX[this.state] + name; 473 }; 474 475 476 /** 477 * Returns raw node name (without type decoration). 478 */ 479 Profile.DynamicFuncCodeEntry.prototype.getRawName = function() { 480 return this.func.getName(); 481 }; 482 483 484 Profile.DynamicFuncCodeEntry.prototype.isJSFunction = function() { 485 return true; 486 }; 487 488 489 Profile.DynamicFuncCodeEntry.prototype.toString = function() { 490 return this.getName() + ': ' + this.size.toString(16); 491 }; 492 493 494 /** 495 * Creates a shared function object entry. 496 * 497 * @param {string} name Function name. 498 * @constructor 499 */ 500 Profile.FunctionEntry = function(name) { 501 CodeMap.CodeEntry.call(this, 0, name); 502 }; 503 504 505 /** 506 * Returns node name. 507 */ 508 Profile.FunctionEntry.prototype.getName = function() { 509 var name = this.name; 510 if (name.length == 0) { 511 name = '<anonymous>'; 512 } else if (name.charAt(0) == ' ') { 513 // An anonymous function with location: " aaa.js:10". 514 name = '<anonymous>' + name; 515 } 516 return name; 517 }; 518 519 Profile.FunctionEntry.prototype.toString = CodeMap.CodeEntry.prototype.toString; 520 521 /** 522 * Constructs a call graph. 523 * 524 * @constructor 525 */ 526 function CallTree() { 527 this.root_ = new CallTree.Node( 528 CallTree.ROOT_NODE_LABEL); 529 }; 530 531 532 /** 533 * The label of the root node. 534 */ 535 CallTree.ROOT_NODE_LABEL = ''; 536 537 538 /** 539 * @private 540 */ 541 CallTree.prototype.totalsComputed_ = false; 542 543 544 /** 545 * Returns the tree root. 546 */ 547 CallTree.prototype.getRoot = function() { 548 return this.root_; 549 }; 550 551 552 /** 553 * Adds the specified call path, constructing nodes as necessary. 554 * 555 * @param {Array<string>} path Call path. 556 */ 557 CallTree.prototype.addPath = function(path) { 558 if (path.length == 0) { 559 return; 560 } 561 var curr = this.root_; 562 for (var i = 0; i < path.length; ++i) { 563 curr = curr.findOrAddChild(path[i]); 564 } 565 curr.selfWeight++; 566 this.totalsComputed_ = false; 567 }; 568 569 570 /** 571 * Finds an immediate child of the specified parent with the specified 572 * label, creates a child node if necessary. If a parent node isn't 573 * specified, uses tree root. 574 * 575 * @param {string} label Child node label. 576 */ 577 CallTree.prototype.findOrAddChild = function(label) { 578 return this.root_.findOrAddChild(label); 579 }; 580 581 582 /** 583 * Creates a subtree by cloning and merging all subtrees rooted at nodes 584 * with a given label. E.g. cloning the following call tree on label 'A' 585 * will give the following result: 586 * 587 * <A>--<B> <B> 588 * / / 589 * <root> == clone on 'A' ==> <root>--<A> 590 * \ \ 591 * <C>--<A>--<D> <D> 592 * 593 * And <A>'s selfWeight will be the sum of selfWeights of <A>'s from the 594 * source call tree. 595 * 596 * @param {string} label The label of the new root node. 597 */ 598 CallTree.prototype.cloneSubtree = function(label) { 599 var subTree = new CallTree(); 600 this.traverse(function(node, parent) { 601 if (!parent && node.label != label) { 602 return null; 603 } 604 var child = (parent ? parent : subTree).findOrAddChild(node.label); 605 child.selfWeight += node.selfWeight; 606 return child; 607 }); 608 return subTree; 609 }; 610 611 612 /** 613 * Computes total weights in the call graph. 614 */ 615 CallTree.prototype.computeTotalWeights = function() { 616 if (this.totalsComputed_) { 617 return; 618 } 619 this.root_.computeTotalWeight(); 620 this.totalsComputed_ = true; 621 }; 622 623 624 /** 625 * Traverses the call graph in preorder. This function can be used for 626 * building optionally modified tree clones. This is the boilerplate code 627 * for this scenario: 628 * 629 * callTree.traverse(function(node, parentClone) { 630 * var nodeClone = cloneNode(node); 631 * if (parentClone) 632 * parentClone.addChild(nodeClone); 633 * return nodeClone; 634 * }); 635 * 636 * @param {function(CallTree.Node, *)} f Visitor function. 637 * The second parameter is the result of calling 'f' on the parent node. 638 */ 639 CallTree.prototype.traverse = function(f) { 640 var pairsToProcess = new ConsArray(); 641 pairsToProcess.concat([{node: this.root_, param: null}]); 642 while (!pairsToProcess.atEnd()) { 643 var pair = pairsToProcess.next(); 644 var node = pair.node; 645 var newParam = f(node, pair.param); 646 var morePairsToProcess = []; 647 node.forEachChild(function (child) { 648 morePairsToProcess.push({node: child, param: newParam}); }); 649 pairsToProcess.concat(morePairsToProcess); 650 } 651 }; 652 653 654 /** 655 * Performs an indepth call graph traversal. 656 * 657 * @param {function(CallTree.Node)} enter A function called 658 * prior to visiting node's children. 659 * @param {function(CallTree.Node)} exit A function called 660 * after visiting node's children. 661 */ 662 CallTree.prototype.traverseInDepth = function(enter, exit) { 663 function traverse(node) { 664 enter(node); 665 node.forEachChild(traverse); 666 exit(node); 667 } 668 traverse(this.root_); 669 }; 670 671 672 /** 673 * Constructs a call graph node. 674 * 675 * @param {string} label Node label. 676 * @param {CallTree.Node} opt_parent Node parent. 677 */ 678 CallTree.Node = function(label, opt_parent) { 679 this.label = label; 680 this.parent = opt_parent; 681 this.children = {}; 682 }; 683 684 685 /** 686 * Node self weight (how many times this node was the last node in 687 * a call path). 688 * @type {number} 689 */ 690 CallTree.Node.prototype.selfWeight = 0; 691 692 693 /** 694 * Node total weight (includes weights of all children). 695 * @type {number} 696 */ 697 CallTree.Node.prototype.totalWeight = 0; 698 699 700 /** 701 * Adds a child node. 702 * 703 * @param {string} label Child node label. 704 */ 705 CallTree.Node.prototype.addChild = function(label) { 706 var child = new CallTree.Node(label, this); 707 this.children[label] = child; 708 return child; 709 }; 710 711 712 /** 713 * Computes node's total weight. 714 */ 715 CallTree.Node.prototype.computeTotalWeight = 716 function() { 717 var totalWeight = this.selfWeight; 718 this.forEachChild(function(child) { 719 totalWeight += child.computeTotalWeight(); }); 720 return this.totalWeight = totalWeight; 721 }; 722 723 724 /** 725 * Returns all node's children as an array. 726 */ 727 CallTree.Node.prototype.exportChildren = function() { 728 var result = []; 729 this.forEachChild(function (node) { result.push(node); }); 730 return result; 731 }; 732 733 734 /** 735 * Finds an immediate child with the specified label. 736 * 737 * @param {string} label Child node label. 738 */ 739 CallTree.Node.prototype.findChild = function(label) { 740 return this.children[label] || null; 741 }; 742 743 744 /** 745 * Finds an immediate child with the specified label, creates a child 746 * node if necessary. 747 * 748 * @param {string} label Child node label. 749 */ 750 CallTree.Node.prototype.findOrAddChild = function(label) { 751 return this.findChild(label) || this.addChild(label); 752 }; 753 754 755 /** 756 * Calls the specified function for every child. 757 * 758 * @param {function(CallTree.Node)} f Visitor function. 759 */ 760 CallTree.Node.prototype.forEachChild = function(f) { 761 for (var c in this.children) { 762 f(this.children[c]); 763 } 764 }; 765 766 767 /** 768 * Walks up from the current node up to the call tree root. 769 * 770 * @param {function(CallTree.Node)} f Visitor function. 771 */ 772 CallTree.Node.prototype.walkUpToRoot = function(f) { 773 for (var curr = this; curr != null; curr = curr.parent) { 774 f(curr); 775 } 776 }; 777 778 779 /** 780 * Tries to find a node with the specified path. 781 * 782 * @param {Array<string>} labels The path. 783 * @param {function(CallTree.Node)} opt_f Visitor function. 784 */ 785 CallTree.Node.prototype.descendToChild = function( 786 labels, opt_f) { 787 for (var pos = 0, curr = this; pos < labels.length && curr != null; pos++) { 788 var child = curr.findChild(labels[pos]); 789 if (opt_f) { 790 opt_f(child, pos); 791 } 792 curr = child; 793 } 794 return curr; 795 }; 796