src/third_party/trace-viewer/src/tracing/trace_model/slice_group.js

   1 // Copyright (c) 2013 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 'use strict';
   6
   7 /**
   8  * @fileoverview Provides the SliceGroup class.
   9  */
  10 base.require('base.range');
  11 base.require('tracing.trace_model.slice');
  12 base.require('tracing.color_scheme');
  13 base.require('tracing.filter');
  14
  15 base.exportTo('tracing.trace_model', function() {
  16   var Slice = tracing.trace_model.Slice;
  17
  18   /**
  19    * A group of Slices, plus code to create them from B/E events, as
  20    * well as arrange them into subRows.
  21    *
  22    * Do not mutate the slices array directly. Modify it only by
  23    * SliceGroup mutation methods.
  24    *
  25    * @constructor
  26    * @param {function(new:Slice, category, title, colorId, start, args)=}
  27    *     opt_sliceConstructor The constructor to use when creating slices.
  28    */
  29   function SliceGroup(opt_sliceConstructor) {
  30     var sliceConstructor = opt_sliceConstructor || Slice;
  31     this.sliceConstructor = sliceConstructor;
  32
  33     this.openPartialSlices_ = [];
  34
  35     this.slices = [];
  36     this.bounds = new base.Range();
  37     this.topLevelSlices = [];
  38   }
  39
  40   SliceGroup.prototype = {
  41     __proto__: Object.prototype,
  42
  43     /**
  44      * @return {Number} The number of slices in this group.
  45      */
  46     get length() {
  47       return this.slices.length;
  48     },
  49
  50     /**
  51      * Helper function that pushes the provided slice onto the slices array.
  52      * @param {Slice} slice The slice to be added to the slices array.
  53      */
  54     pushSlice: function(slice) {
  55       this.slices.push(slice);
  56       return slice;
  57     },
  58
  59     /**
  60      * Helper function that pushes the provided slice onto the slices array.
  61      * @param {Array.<Slice>} slices An array of slices to be added.
  62      */
  63     pushSlices: function(slices) {
  64       this.slices.push.apply(this.slices, slices);
  65     },
  66
  67     /**
  68      * Push an instant event into the slice list.
  69      * @param {tracing.trace_model.InstantEvent} instantEvent The instantEvent.
  70      */
  71     pushInstantEvent: function(instantEvent) {
  72       this.slices.push(instantEvent);
  73     },
  74
  75     /**
  76      * Opens a new slice in the group's slices.
  77      *
  78      * Calls to beginSlice and
  79      * endSlice must be made with non-monotonically-decreasing timestamps.
  80      *
  81      * @param {String} category Category name of the slice to add.
  82      * @param {String} title Title of the slice to add.
  83      * @param {Number} ts The timetsamp of the slice, in milliseconds.
  84      * @param {Object.<string, Object>=} opt_args Arguments associated with
  85      * the slice.
  86      */
  87     beginSlice: function(category, title, ts, opt_args, opt_tts) {
  88       if (this.openPartialSlices_.length) {
  89         var prevSlice = this.openPartialSlices_[
  90             this.openPartialSlices_.length - 1];
  91         if (ts < prevSlice.start)
  92           throw new Error('Slices must be added in increasing timestamp order');
  93       }
  94
  95       var colorId = tracing.getStringColorId(title);
  96       var slice = new this.sliceConstructor(category, title, colorId, ts,
  97                                             opt_args ? opt_args : {}, null,
  98                                             opt_tts);
  99       this.openPartialSlices_.push(slice);
 100       slice.didNotFinish = true;
 101       this.pushSlice(slice);
 102
 103       return slice;
 104     },
 105
 106     isTimestampValidForBeginOrEnd: function(ts) {
 107       if (!this.openPartialSlices_.length)
 108         return true;
 109       var top = this.openPartialSlices_[this.openPartialSlices_.length - 1];
 110       return ts >= top.start;
 111     },
 112
 113     /**
 114      * @return {Number} The number of beginSlices for which an endSlice has not
 115      * been issued.
 116      */
 117     get openSliceCount() {
 118       return this.openPartialSlices_.length;
 119     },
 120
 121     get mostRecentlyOpenedPartialSlice() {
 122       if (!this.openPartialSlices_.length)
 123         return undefined;
 124       return this.openPartialSlices_[this.openPartialSlices_.length - 1];
 125     },
 126
 127     /**
 128      * Ends the last begun slice in this group and pushes it onto the slice
 129      * array.
 130      *
 131      * @param {Number} ts Timestamp when the slice ended.
 132      * @return {Slice} slice.
 133      */
 134     endSlice: function(ts, opt_tts) {
 135       if (!this.openSliceCount)
 136         throw new Error('endSlice called without an open slice');
 137
 138       var slice = this.openPartialSlices_[this.openSliceCount - 1];
 139       this.openPartialSlices_.splice(this.openSliceCount - 1, 1);
 140       if (ts < slice.start)
 141         throw new Error('Slice ' + slice.title +
 142                         ' end time is before its start.');
 143
 144       slice.duration = ts - slice.start;
 145       slice.didNotFinish = false;
 146
 147       if (opt_tts && slice.threadStart)
 148         slice.threadDuration = opt_tts - slice.threadStart;
 149
 150       return slice;
 151     },
 152
 153     /**
 154      * Push a complete event as a Slice into the slice list.
 155      * The timestamp can be in any order.
 156      *
 157      * @param {String} category Category name of the slice to add.
 158      * @param {String} title Title of the slice to add.
 159      * @param {Number} ts The timetsamp of the slice, in milliseconds.
 160      * @param {Number} duration The duration of the slice, in milliseconds.
 161      * @param {Object.<string, Object>=} opt_args Arguments associated with
 162      * the slice.
 163      */
 164     pushCompleteSlice: function(category, title, ts, duration, tts,
 165                                 threadDuration, opt_args) {
 166       var colorId = tracing.getStringColorId(title);
 167       var slice = new this.sliceConstructor(category, title, colorId, ts,
 168                                             opt_args ? opt_args : {},
 169                                             duration, tts, threadDuration);
 170       if (duration === undefined)
 171         slice.didNotFinish = true;
 172       this.pushSlice(slice);
 173       return slice;
 174     },
 175
 176     /**
 177      * Closes any open slices.
 178      * @param {Number=} opt_maxTimestamp The end time to use for the closed
 179      * slices. If not provided,
 180      * the max timestamp for this slice is provided.
 181      */
 182     autoCloseOpenSlices: function(opt_maxTimestamp) {
 183       if (!opt_maxTimestamp) {
 184         this.updateBounds();
 185         opt_maxTimestamp = this.bounds.max;
 186       }
 187       for (var sI = 0; sI < this.slices.length; sI++) {
 188         var slice = this.slices[sI];
 189         if (slice.didNotFinish)
 190           slice.duration = opt_maxTimestamp - slice.start;
 191       }
 192       this.openPartialSlices_ = [];
 193     },
 194
 195     /**
 196      * Shifts all the timestamps inside this group forward by the amount
 197      * specified.
 198      */
 199     shiftTimestampsForward: function(amount) {
 200       for (var sI = 0; sI < this.slices.length; sI++) {
 201         var slice = this.slices[sI];
 202         slice.start = (slice.start + amount);
 203       }
 204     },
 205
 206     /**
 207      * Updates the bounds for this group based on the slices it contains.
 208      */
 209     updateBounds: function() {
 210       this.bounds.reset();
 211       for (var i = 0; i < this.slices.length; i++) {
 212         this.bounds.addValue(this.slices[i].start);
 213         this.bounds.addValue(this.slices[i].end);
 214       }
 215     },
 216
 217     copySlice: function(slice) {
 218       var newSlice = new this.sliceConstructor(slice.category, slice.title,
 219           slice.colorId, slice.start,
 220           slice.args, slice.duration, slice.threadStart, slice.threadDuration);
 221       newSlice.didNotFinish = slice.didNotFinish;
 222       return newSlice;
 223     },
 224
 225     iterateAllEvents: function(callback) {
 226       this.slices.forEach(callback);
 227     },
 228
 229     /**
 230      * Construct subSlices for this group.
 231      * Populate the group topLevelSlices, parent slices get a subSlices[]
 232      * and a selfTime, child slices get a parentSlice reference.
 233      */
 234     createSubSlices: function() {
 235       function addSliceIfBounds(root, child) {
 236         // Because we know that the start time of child is >= the start time
 237         // of all other slices seen so far, we can just check the last slice
 238         // of each row for bounding.
 239         if (root.bounds(child)) {
 240           if (root.subSlices && root.subSlices.length > 0) {
 241             if (addSliceIfBounds(root.subSlices[root.subSlices.length - 1],
 242                                  child))
 243               return true;
 244           }
 245           if (!root.selfTime)
 246             root.selfTime = root.duration;
 247           child.parentSlice = root;
 248           if (!root.subSlices)
 249             root.subSlices = [];
 250           root.subSlices.push(child);
 251           root.selfTime -= child.duration;
 252           return true;
 253         }
 254         return false;
 255       }
 256
 257       if (!this.slices.length)
 258         return;
 259
 260       var ops = [];
 261       for (var i = 0; i < this.slices.length; i++) {
 262         if (this.slices[i].subSlices)
 263           this.slices[i].subSlices.splice(0,
 264                                           this.slices[i].subSlices.length);
 265         ops.push(i);
 266       }
 267
 268       var groupSlices = this.slices;
 269       ops.sort(function(ix, iy) {
 270         var x = groupSlices[ix];
 271         var y = groupSlices[iy];
 272         if (x.start != y.start)
 273           return x.start - y.start;
 274
 275         // Elements get inserted into the slices array in order of when the
 276         // slices start. Because slices must be properly nested, we break
 277         // start-time ties by assuming that the elements appearing earlier
 278         // in the slices array (and thus ending earlier) start earlier.
 279         return ix - iy;
 280       });
 281
 282       var rootSlice = this.slices[ops[0]];
 283       this.topLevelSlices = [];
 284       this.topLevelSlices.push(rootSlice);
 285       for (var i = 1; i < ops.length; i++) {
 286         var slice = this.slices[ops[i]];
 287         if (!addSliceIfBounds(rootSlice, slice)) {
 288           rootSlice = slice;
 289           this.topLevelSlices.push(rootSlice);
 290         }
 291       }
 292     }
 293   };
 294
 295   /**
 296    * Merge two slice groups.
 297    *
 298    * If the two groups do not nest properly some of the slices of groupB will
 299    * be split to accomodate the improper nesting.  This is done to accomodate
 300    * combined kernel and userland call stacks on Android.  Because userland
 301    * tracing is done by writing to the trace_marker file, the kernel calls
 302    * that get invoked as part of that write may not be properly nested with
 303    * the userland call trace.  For example the following sequence may occur:
 304    *
 305    *     kernel enter sys_write        (the write to trace_marker)
 306    *     user   enter some_function
 307    *     kernel exit  sys_write
 308    *     ...
 309    *     kernel enter sys_write        (the write to trace_marker)
 310    *     user   exit  some_function
 311    *     kernel exit  sys_write
 312    *
 313    * This is handled by splitting the sys_write call into two slices as
 314    * follows:
 315    *
 316    *     | sys_write |            some_function            | sys_write (cont.) |
 317    *                 | sys_write (cont.) |     | sys_write |
 318    *
 319    * The colorId of both parts of the split slices are kept the same, and the
 320    * " (cont.)" suffix is appended to the later parts of a split slice.
 321    *
 322    * The two input SliceGroups are not modified by this, and the merged
 323    * SliceGroup will contain a copy of each of the input groups' slices (those
 324    * copies may be split).
 325    */
 326   SliceGroup.merge = function(groupA, groupB) {
 327     // This is implemented by traversing the two slice groups in reverse
 328     // order.  The slices in each group are sorted by ascending end-time, so
 329     // we must do the traversal from back to front in order to maintain the
 330     // sorting.
 331     //
 332     // We traverse the two groups simultaneously, merging as we go.  At each
 333     // iteration we choose the group from which to take the next slice based
 334     // on which group's next slice has the greater end-time.  During this
 335     // traversal we maintain a stack of currently "open" slices for each input
 336     // group.  A slice is considered "open" from the time it gets reached in
 337     // our input group traversal to the time we reach an slice in this
 338     // traversal with an end-time before the start time of the "open" slice.
 339     //
 340     // Each time a slice from groupA is opened or closed (events corresponding
 341     // to the end-time and start-time of the input slice, respectively) we
 342     // split all of the currently open slices from groupB.
 343
 344     if (groupA.openPartialSlices_.length > 0) {
 345       throw new Error('groupA has open partial slices');
 346     }
 347     if (groupB.openPartialSlices_.length > 0) {
 348       throw new Error('groupB has open partial slices');
 349     }
 350
 351     var result = new SliceGroup();
 352
 353     var slicesA = groupA.slices;
 354     var slicesB = groupB.slices;
 355     var idxA = 0;
 356     var idxB = 0;
 357     var openA = [];
 358     var openB = [];
 359
 360     var splitOpenSlices = function(when) {
 361       for (var i = 0; i < openB.length; i++) {
 362         var oldSlice = openB[i];
 363         var oldEnd = oldSlice.end;
 364         if (when < oldSlice.start || oldEnd < when) {
 365           throw new Error('slice should not be split');
 366         }
 367
 368         var newSlice = result.copySlice(oldSlice);
 369         newSlice.start = when;
 370         newSlice.duration = oldEnd - when;
 371         if (newSlice.title.indexOf(' (cont.)') == -1)
 372           newSlice.title += ' (cont.)';
 373         oldSlice.duration = when - oldSlice.start;
 374         openB[i] = newSlice;
 375         result.pushSlice(newSlice);
 376       }
 377     };
 378
 379     var closeOpenSlices = function(upTo) {
 380       while (openA.length > 0 || openB.length > 0) {
 381         var nextA = openA[openA.length - 1];
 382         var nextB = openB[openB.length - 1];
 383         var endA = nextA && nextA.end;
 384         var endB = nextB && nextB.end;
 385
 386         if ((endA === undefined || endA > upTo) &&
 387             (endB === undefined || endB > upTo)) {
 388           return;
 389         }
 390
 391         if (endB === undefined || endA < endB) {
 392           splitOpenSlices(endA);
 393           openA.pop();
 394         } else {
 395           openB.pop();
 396         }
 397       }
 398     };
 399
 400     while (idxA < slicesA.length || idxB < slicesB.length) {
 401       var sA = slicesA[idxA];
 402       var sB = slicesB[idxB];
 403       var nextSlice, isFromB;
 404
 405       if (sA === undefined || (sB !== undefined && sA.start > sB.start)) {
 406         nextSlice = result.copySlice(sB);
 407         isFromB = true;
 408         idxB++;
 409       } else {
 410         nextSlice = result.copySlice(sA);
 411         isFromB = false;
 412         idxA++;
 413       }
 414
 415       closeOpenSlices(nextSlice.start);
 416
 417       result.pushSlice(nextSlice);
 418
 419       if (isFromB) {
 420         openB.push(nextSlice);
 421       } else {
 422         splitOpenSlices(nextSlice.start);
 423         openA.push(nextSlice);
 424       }
 425     }
 426
 427     closeOpenSlices();
 428
 429     return result;
 430   };
 431
 432   return {
 433     SliceGroup: SliceGroup
 434   };
 435 });