OLD | NEW |
| (Empty) |
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 // Initlialize namespaces | |
30 var devtools = devtools || {}; | |
31 devtools.profiler = devtools.profiler || {}; | |
32 | |
33 | |
34 /** | |
35 * Creates a profile object for processing profiling-related events | |
36 * and calculating function execution times. | |
37 * | |
38 * @constructor | |
39 */ | |
40 devtools.profiler.Profile = function() { | |
41 this.codeMap_ = new devtools.profiler.CodeMap(); | |
42 this.topDownTree_ = new devtools.profiler.CallTree(); | |
43 this.bottomUpTree_ = new devtools.profiler.CallTree(); | |
44 }; | |
45 | |
46 | |
47 /** | |
48 * Returns whether a function with the specified name must be skipped. | |
49 * Should be overriden by subclasses. | |
50 * | |
51 * @param {string} name Function name. | |
52 */ | |
53 devtools.profiler.Profile.prototype.skipThisFunction = function(name) { | |
54 return false; | |
55 }; | |
56 | |
57 | |
58 /** | |
59 * Enum for profiler operations that involve looking up existing | |
60 * code entries. | |
61 * | |
62 * @enum {number} | |
63 */ | |
64 devtools.profiler.Profile.Operation = { | |
65 MOVE: 0, | |
66 DELETE: 1, | |
67 TICK: 2 | |
68 }; | |
69 | |
70 | |
71 /** | |
72 * Called whenever the specified operation has failed finding a function | |
73 * containing the specified address. Should be overriden by subclasses. | |
74 * See the devtools.profiler.Profile.Operation enum for the list of | |
75 * possible operations. | |
76 * | |
77 * @param {number} operation Operation. | |
78 * @param {number} addr Address of the unknown code. | |
79 * @param {number} opt_stackPos If an unknown address is encountered | |
80 * during stack strace processing, specifies a position of the frame | |
81 * containing the address. | |
82 */ | |
83 devtools.profiler.Profile.prototype.handleUnknownCode = function( | |
84 operation, addr, opt_stackPos) { | |
85 }; | |
86 | |
87 | |
88 /** | |
89 * Registers a library. | |
90 * | |
91 * @param {string} name Code entry name. | |
92 * @param {number} startAddr Starting address. | |
93 * @param {number} endAddr Ending address. | |
94 */ | |
95 devtools.profiler.Profile.prototype.addLibrary = function( | |
96 name, startAddr, endAddr) { | |
97 var entry = new devtools.profiler.CodeMap.CodeEntry( | |
98 endAddr - startAddr, name); | |
99 this.codeMap_.addLibrary(startAddr, entry); | |
100 return entry; | |
101 }; | |
102 | |
103 | |
104 /** | |
105 * Registers statically compiled code entry. | |
106 * | |
107 * @param {string} name Code entry name. | |
108 * @param {number} startAddr Starting address. | |
109 * @param {number} endAddr Ending address. | |
110 */ | |
111 devtools.profiler.Profile.prototype.addStaticCode = function( | |
112 name, startAddr, endAddr) { | |
113 var entry = new devtools.profiler.CodeMap.CodeEntry( | |
114 endAddr - startAddr, name); | |
115 this.codeMap_.addStaticCode(startAddr, entry); | |
116 return entry; | |
117 }; | |
118 | |
119 | |
120 /** | |
121 * Registers dynamic (JIT-compiled) code entry. | |
122 * | |
123 * @param {string} type Code entry type. | |
124 * @param {string} name Code entry name. | |
125 * @param {number} start Starting address. | |
126 * @param {number} size Code entry size. | |
127 */ | |
128 devtools.profiler.Profile.prototype.addCode = function( | |
129 type, name, start, size) { | |
130 var entry = new devtools.profiler.Profile.DynamicCodeEntry(size, type, name); | |
131 this.codeMap_.addCode(start, entry); | |
132 return entry; | |
133 }; | |
134 | |
135 | |
136 /** | |
137 * Reports about moving of a dynamic code entry. | |
138 * | |
139 * @param {number} from Current code entry address. | |
140 * @param {number} to New code entry address. | |
141 */ | |
142 devtools.profiler.Profile.prototype.moveCode = function(from, to) { | |
143 try { | |
144 this.codeMap_.moveCode(from, to); | |
145 } catch (e) { | |
146 this.handleUnknownCode(devtools.profiler.Profile.Operation.MOVE, from); | |
147 } | |
148 }; | |
149 | |
150 | |
151 /** | |
152 * Reports about deletion of a dynamic code entry. | |
153 * | |
154 * @param {number} start Starting address. | |
155 */ | |
156 devtools.profiler.Profile.prototype.deleteCode = function(start) { | |
157 try { | |
158 this.codeMap_.deleteCode(start); | |
159 } catch (e) { | |
160 this.handleUnknownCode(devtools.profiler.Profile.Operation.DELETE, start); | |
161 } | |
162 }; | |
163 | |
164 | |
165 /** | |
166 * Records a tick event. Stack must contain a sequence of | |
167 * addresses starting with the program counter value. | |
168 * | |
169 * @param {Array<number>} stack Stack sample. | |
170 */ | |
171 devtools.profiler.Profile.prototype.recordTick = function(stack) { | |
172 var processedStack = this.resolveAndFilterFuncs_(stack); | |
173 this.bottomUpTree_.addPath(processedStack); | |
174 processedStack.reverse(); | |
175 this.topDownTree_.addPath(processedStack); | |
176 }; | |
177 | |
178 | |
179 /** | |
180 * Translates addresses into function names and filters unneeded | |
181 * functions. | |
182 * | |
183 * @param {Array<number>} stack Stack sample. | |
184 */ | |
185 devtools.profiler.Profile.prototype.resolveAndFilterFuncs_ = function(stack) { | |
186 var result = []; | |
187 for (var i = 0; i < stack.length; ++i) { | |
188 var entry = this.codeMap_.findEntry(stack[i]); | |
189 if (entry) { | |
190 var name = entry.getName(); | |
191 if (!this.skipThisFunction(name)) { | |
192 result.push(name); | |
193 } | |
194 } else { | |
195 this.handleUnknownCode( | |
196 devtools.profiler.Profile.Operation.TICK, stack[i], i); | |
197 } | |
198 } | |
199 return result; | |
200 }; | |
201 | |
202 | |
203 /** | |
204 * Performs a BF traversal of the top down call graph. | |
205 * | |
206 * @param {function(devtools.profiler.CallTree.Node)} f Visitor function. | |
207 */ | |
208 devtools.profiler.Profile.prototype.traverseTopDownTree = function(f) { | |
209 this.topDownTree_.traverse(f); | |
210 }; | |
211 | |
212 | |
213 /** | |
214 * Performs a BF traversal of the bottom up call graph. | |
215 * | |
216 * @param {function(devtools.profiler.CallTree.Node)} f Visitor function. | |
217 */ | |
218 devtools.profiler.Profile.prototype.traverseBottomUpTree = function(f) { | |
219 this.bottomUpTree_.traverse(f); | |
220 }; | |
221 | |
222 | |
223 /** | |
224 * Calculates a top down profile for a node with the specified label. | |
225 * If no name specified, returns the whole top down calls tree. | |
226 * | |
227 * @param {string} opt_label Node label. | |
228 */ | |
229 devtools.profiler.Profile.prototype.getTopDownProfile = function(opt_label) { | |
230 return this.getTreeProfile_(this.topDownTree_, opt_label); | |
231 }; | |
232 | |
233 | |
234 /** | |
235 * Calculates a bottom up profile for a node with the specified label. | |
236 * If no name specified, returns the whole bottom up calls tree. | |
237 * | |
238 * @param {string} opt_label Node label. | |
239 */ | |
240 devtools.profiler.Profile.prototype.getBottomUpProfile = function(opt_label) { | |
241 return this.getTreeProfile_(this.bottomUpTree_, opt_label); | |
242 }; | |
243 | |
244 | |
245 /** | |
246 * Helper function for calculating a tree profile. | |
247 * | |
248 * @param {devtools.profiler.Profile.CallTree} tree Call tree. | |
249 * @param {string} opt_label Node label. | |
250 */ | |
251 devtools.profiler.Profile.prototype.getTreeProfile_ = function(tree, opt_label)
{ | |
252 if (!opt_label) { | |
253 tree.computeTotalWeights(); | |
254 return tree; | |
255 } else { | |
256 var subTree = tree.cloneSubtree(opt_label); | |
257 subTree.computeTotalWeights(); | |
258 return subTree; | |
259 } | |
260 }; | |
261 | |
262 | |
263 /** | |
264 * Calculates a flat profile of callees starting from a node with | |
265 * the specified label. If no name specified, starts from the root. | |
266 * | |
267 * @param {string} opt_label Starting node label. | |
268 */ | |
269 devtools.profiler.Profile.prototype.getFlatProfile = function(opt_label) { | |
270 var counters = new devtools.profiler.CallTree(); | |
271 var rootLabel = opt_label || devtools.profiler.CallTree.ROOT_NODE_LABEL; | |
272 var precs = {}; | |
273 precs[rootLabel] = 0; | |
274 var root = counters.findOrAddChild(rootLabel); | |
275 | |
276 this.topDownTree_.computeTotalWeights(); | |
277 this.topDownTree_.traverseInDepth( | |
278 function onEnter(node) { | |
279 if (!(node.label in precs)) { | |
280 precs[node.label] = 0; | |
281 } | |
282 var nodeLabelIsRootLabel = node.label == rootLabel; | |
283 if (nodeLabelIsRootLabel || precs[rootLabel] > 0) { | |
284 if (precs[rootLabel] == 0) { | |
285 root.selfWeight += node.selfWeight; | |
286 root.totalWeight += node.totalWeight; | |
287 } else { | |
288 var rec = root.findOrAddChild(node.label); | |
289 rec.selfWeight += node.selfWeight; | |
290 if (nodeLabelIsRootLabel || precs[node.label] == 0) { | |
291 rec.totalWeight += node.totalWeight; | |
292 } | |
293 } | |
294 precs[node.label]++; | |
295 } | |
296 }, | |
297 function onExit(node) { | |
298 if (node.label == rootLabel || precs[rootLabel] > 0) { | |
299 precs[node.label]--; | |
300 } | |
301 }, | |
302 null); | |
303 | |
304 if (!opt_label) { | |
305 // If we have created a flat profile for the whole program, we don't | |
306 // need an explicit root in it. Thus, replace the counters tree | |
307 // root with the node corresponding to the whole program. | |
308 counters.root_ = root; | |
309 } else { | |
310 // Propagate weights so percents can be calculated correctly. | |
311 counters.getRoot().selfWeight = root.selfWeight; | |
312 counters.getRoot().totalWeight = root.totalWeight; | |
313 } | |
314 return counters; | |
315 }; | |
316 | |
317 | |
318 /** | |
319 * Creates a dynamic code entry. | |
320 * | |
321 * @param {number} size Code size. | |
322 * @param {string} type Code type. | |
323 * @param {string} name Function name. | |
324 * @constructor | |
325 */ | |
326 devtools.profiler.Profile.DynamicCodeEntry = function(size, type, name) { | |
327 devtools.profiler.CodeMap.CodeEntry.call(this, size, name); | |
328 this.type = type; | |
329 }; | |
330 | |
331 | |
332 /** | |
333 * Returns node name. | |
334 */ | |
335 devtools.profiler.Profile.DynamicCodeEntry.prototype.getName = function() { | |
336 var name = this.name; | |
337 if (name.length == 0) { | |
338 name = '<anonymous>'; | |
339 } else if (name.charAt(0) == ' ') { | |
340 // An anonymous function with location: " aaa.js:10". | |
341 name = '<anonymous>' + name; | |
342 } | |
343 return this.type + ': ' + name; | |
344 }; | |
345 | |
346 | |
347 /** | |
348 * Constructs a call graph. | |
349 * | |
350 * @constructor | |
351 */ | |
352 devtools.profiler.CallTree = function() { | |
353 this.root_ = new devtools.profiler.CallTree.Node( | |
354 devtools.profiler.CallTree.ROOT_NODE_LABEL); | |
355 }; | |
356 | |
357 | |
358 /** | |
359 * The label of the root node. | |
360 */ | |
361 devtools.profiler.CallTree.ROOT_NODE_LABEL = ''; | |
362 | |
363 | |
364 /** | |
365 * @private | |
366 */ | |
367 devtools.profiler.CallTree.prototype.totalsComputed_ = false; | |
368 | |
369 | |
370 /** | |
371 * Returns the tree root. | |
372 */ | |
373 devtools.profiler.CallTree.prototype.getRoot = function() { | |
374 return this.root_; | |
375 }; | |
376 | |
377 | |
378 /** | |
379 * Adds the specified call path, constructing nodes as necessary. | |
380 * | |
381 * @param {Array<string>} path Call path. | |
382 */ | |
383 devtools.profiler.CallTree.prototype.addPath = function(path) { | |
384 if (path.length == 0) { | |
385 return; | |
386 } | |
387 var curr = this.root_; | |
388 for (var i = 0; i < path.length; ++i) { | |
389 curr = curr.findOrAddChild(path[i]); | |
390 } | |
391 curr.selfWeight++; | |
392 this.totalsComputed_ = false; | |
393 }; | |
394 | |
395 | |
396 /** | |
397 * Finds an immediate child of the specified parent with the specified | |
398 * label, creates a child node if necessary. If a parent node isn't | |
399 * specified, uses tree root. | |
400 * | |
401 * @param {string} label Child node label. | |
402 */ | |
403 devtools.profiler.CallTree.prototype.findOrAddChild = function(label) { | |
404 return this.root_.findOrAddChild(label); | |
405 }; | |
406 | |
407 | |
408 /** | |
409 * Creates a subtree by cloning and merging all subtrees rooted at nodes | |
410 * with a given label. E.g. cloning the following call tree on label 'A' | |
411 * will give the following result: | |
412 * | |
413 * <A>--<B> <B> | |
414 * / / | |
415 * <root> == clone on 'A' ==> <root>--<A> | |
416 * \ \ | |
417 * <C>--<A>--<D> <D> | |
418 * | |
419 * And <A>'s selfWeight will be the sum of selfWeights of <A>'s from the | |
420 * source call tree. | |
421 * | |
422 * @param {string} label The label of the new root node. | |
423 */ | |
424 devtools.profiler.CallTree.prototype.cloneSubtree = function(label) { | |
425 var subTree = new devtools.profiler.CallTree(); | |
426 this.traverse(function(node, parent) { | |
427 if (!parent && node.label != label) { | |
428 return null; | |
429 } | |
430 var child = (parent ? parent : subTree).findOrAddChild(node.label); | |
431 child.selfWeight += node.selfWeight; | |
432 return child; | |
433 }); | |
434 return subTree; | |
435 }; | |
436 | |
437 | |
438 /** | |
439 * Computes total weights in the call graph. | |
440 */ | |
441 devtools.profiler.CallTree.prototype.computeTotalWeights = function() { | |
442 if (this.totalsComputed_) { | |
443 return; | |
444 } | |
445 this.root_.computeTotalWeight(); | |
446 this.totalsComputed_ = true; | |
447 }; | |
448 | |
449 | |
450 /** | |
451 * Traverses the call graph in preorder. This function can be used for | |
452 * building optionally modified tree clones. This is the boilerplate code | |
453 * for this scenario: | |
454 * | |
455 * callTree.traverse(function(node, parentClone) { | |
456 * var nodeClone = cloneNode(node); | |
457 * if (parentClone) | |
458 * parentClone.addChild(nodeClone); | |
459 * return nodeClone; | |
460 * }); | |
461 * | |
462 * @param {function(devtools.profiler.CallTree.Node, *)} f Visitor function. | |
463 * The second parameter is the result of calling 'f' on the parent node. | |
464 */ | |
465 devtools.profiler.CallTree.prototype.traverse = function(f) { | |
466 var pairsToProcess = new ConsArray(); | |
467 pairsToProcess.concat([{node: this.root_, param: null}]); | |
468 while (!pairsToProcess.atEnd()) { | |
469 var pair = pairsToProcess.next(); | |
470 var node = pair.node; | |
471 var newParam = f(node, pair.param); | |
472 var morePairsToProcess = []; | |
473 node.forEachChild(function (child) { | |
474 morePairsToProcess.push({node: child, param: newParam}); }); | |
475 pairsToProcess.concat(morePairsToProcess); | |
476 } | |
477 }; | |
478 | |
479 | |
480 /** | |
481 * Performs an indepth call graph traversal. | |
482 * | |
483 * @param {function(devtools.profiler.CallTree.Node)} enter A function called | |
484 * prior to visiting node's children. | |
485 * @param {function(devtools.profiler.CallTree.Node)} exit A function called | |
486 * after visiting node's children. | |
487 */ | |
488 devtools.profiler.CallTree.prototype.traverseInDepth = function(enter, exit) { | |
489 function traverse(node) { | |
490 enter(node); | |
491 node.forEachChild(traverse); | |
492 exit(node); | |
493 } | |
494 traverse(this.root_); | |
495 }; | |
496 | |
497 | |
498 /** | |
499 * Constructs a call graph node. | |
500 * | |
501 * @param {string} label Node label. | |
502 * @param {devtools.profiler.CallTree.Node} opt_parent Node parent. | |
503 */ | |
504 devtools.profiler.CallTree.Node = function(label, opt_parent) { | |
505 this.label = label; | |
506 this.parent = opt_parent; | |
507 this.children = {}; | |
508 }; | |
509 | |
510 | |
511 /** | |
512 * Node self weight (how many times this node was the last node in | |
513 * a call path). | |
514 * @type {number} | |
515 */ | |
516 devtools.profiler.CallTree.Node.prototype.selfWeight = 0; | |
517 | |
518 | |
519 /** | |
520 * Node total weight (includes weights of all children). | |
521 * @type {number} | |
522 */ | |
523 devtools.profiler.CallTree.Node.prototype.totalWeight = 0; | |
524 | |
525 | |
526 /** | |
527 * Adds a child node. | |
528 * | |
529 * @param {string} label Child node label. | |
530 */ | |
531 devtools.profiler.CallTree.Node.prototype.addChild = function(label) { | |
532 var child = new devtools.profiler.CallTree.Node(label, this); | |
533 this.children[label] = child; | |
534 return child; | |
535 }; | |
536 | |
537 | |
538 /** | |
539 * Computes node's total weight. | |
540 */ | |
541 devtools.profiler.CallTree.Node.prototype.computeTotalWeight = | |
542 function() { | |
543 var totalWeight = this.selfWeight; | |
544 this.forEachChild(function(child) { | |
545 totalWeight += child.computeTotalWeight(); }); | |
546 return this.totalWeight = totalWeight; | |
547 }; | |
548 | |
549 | |
550 /** | |
551 * Returns all node's children as an array. | |
552 */ | |
553 devtools.profiler.CallTree.Node.prototype.exportChildren = function() { | |
554 var result = []; | |
555 this.forEachChild(function (node) { result.push(node); }); | |
556 return result; | |
557 }; | |
558 | |
559 | |
560 /** | |
561 * Finds an immediate child with the specified label. | |
562 * | |
563 * @param {string} label Child node label. | |
564 */ | |
565 devtools.profiler.CallTree.Node.prototype.findChild = function(label) { | |
566 return this.children[label] || null; | |
567 }; | |
568 | |
569 | |
570 /** | |
571 * Finds an immediate child with the specified label, creates a child | |
572 * node if necessary. | |
573 * | |
574 * @param {string} label Child node label. | |
575 */ | |
576 devtools.profiler.CallTree.Node.prototype.findOrAddChild = function(label) { | |
577 return this.findChild(label) || this.addChild(label); | |
578 }; | |
579 | |
580 | |
581 /** | |
582 * Calls the specified function for every child. | |
583 * | |
584 * @param {function(devtools.profiler.CallTree.Node)} f Visitor function. | |
585 */ | |
586 devtools.profiler.CallTree.Node.prototype.forEachChild = function(f) { | |
587 for (var c in this.children) { | |
588 f(this.children[c]); | |
589 } | |
590 }; | |
591 | |
592 | |
593 /** | |
594 * Walks up from the current node up to the call tree root. | |
595 * | |
596 * @param {function(devtools.profiler.CallTree.Node)} f Visitor function. | |
597 */ | |
598 devtools.profiler.CallTree.Node.prototype.walkUpToRoot = function(f) { | |
599 for (var curr = this; curr != null; curr = curr.parent) { | |
600 f(curr); | |
601 } | |
602 }; | |
603 | |
604 | |
605 /** | |
606 * Tries to find a node with the specified path. | |
607 * | |
608 * @param {Array<string>} labels The path. | |
609 * @param {function(devtools.profiler.CallTree.Node)} opt_f Visitor function. | |
610 */ | |
611 devtools.profiler.CallTree.Node.prototype.descendToChild = function( | |
612 labels, opt_f) { | |
613 for (var pos = 0, curr = this; pos < labels.length && curr != null; pos++) { | |
614 var child = curr.findChild(labels[pos]); | |
615 if (opt_f) { | |
616 opt_f(child, pos); | |
617 } | |
618 curr = child; | |
619 } | |
620 return curr; | |
621 }; | |
OLD | NEW |