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