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.threadTime = 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, opt_args) {
 165       var colorId = tracing.getStringColorId(title);
 166       var slice = new this.sliceConstructor(category, title, colorId, ts,
 167                                             opt_args ? opt_args : {},
 168                                             duration);
 169       if (duration === undefined)
 170         slice.didNotFinish = true;
 171       this.pushSlice(slice);
 172       return slice;
 173     },
 174
 175     /**
 176      * Closes any open slices.
 177      * @param {Number=} opt_maxTimestamp The end time to use for the closed
 178      * slices. If not provided,
 179      * the max timestamp for this slice is provided.
 180      */
 181     autoCloseOpenSlices: function(opt_maxTimestamp) {
 182       if (!opt_maxTimestamp) {
 183         this.updateBounds();
 184         opt_maxTimestamp = this.bounds.max;
 185       }
 186       for (var sI = 0; sI < this.slices.length; sI++) {
 187         var slice = this.slices[sI];
 188         if (slice.didNotFinish)
 189           slice.duration = opt_maxTimestamp - slice.start;
 190       }
 191       this.openPartialSlices_ = [];
 192     },
 193
 194     /**
 195      * Shifts all the timestamps inside this group forward by the amount
 196      * specified.
 197      */
 198     shiftTimestampsForward: function(amount) {
 199       for (var sI = 0; sI < this.slices.length; sI++) {
 200         var slice = this.slices[sI];
 201         slice.start = (slice.start + amount);
 202       }
 203     },
 204
 205     /**
 206      * Updates the bounds for this group based on the slices it contains.
 207      */
 208     updateBounds: function() {
 209       this.bounds.reset();
 210       for (var i = 0; i < this.slices.length; i++) {
 211         this.bounds.addValue(this.slices[i].start);
 212         this.bounds.addValue(this.slices[i].end);
 213       }
 214     },
 215
 216     copySlice: function(slice) {
 217       var newSlice = new this.sliceConstructor(slice.category, slice.title,
 218           slice.colorId, slice.start,
 219           slice.args, slice.duration);
 220       newSlice.didNotFinish = slice.didNotFinish;
 221       return newSlice;
 222     },
 223
 224     iterateAllEvents: function(callback) {
 225       this.slices.forEach(callback);
 226     },
 227
 228     /**
 229      * Construct subSlices for this group.
 230      * Populate the group topLevelSlices, parent slices get a subSlices[]
 231      * and a selfTime, child slices get a parentSlice reference.
 232      */
 233     createSubSlices: function() {
 234       function addSliceIfBounds(root, child) {
 235         // Because we know that the start time of child is >= the start time
 236         // of all other slices seen so far, we can just check the last slice
 237         // of each row for bounding.
 238         if (root.bounds(child)) {
 239           if (root.subSlices && root.subSlices.length > 0) {
 240             if (addSliceIfBounds(root.subSlices[root.subSlices.length - 1],
 241                                  child))
 242               return true;
 243           }
 244           if (!root.selfTime)
 245             root.selfTime = root.duration;
 246           child.parentSlice = root;
 247           if (!root.subSlices)
 248             root.subSlices = [];
 249           root.subSlices.push(child);
 250           root.selfTime -= child.duration;
 251           return true;
 252         }
 253         return false;
 254       }
 255
 256       if (!this.slices.length)
 257         return;
 258
 259       var ops = [];
 260       for (var i = 0; i < this.slices.length; i++) {
 261         if (this.slices[i].subSlices)
 262           this.slices[i].subSlices.splice(0,
 263                                           this.slices[i].subSlices.length);
 264         ops.push(i);
 265       }
 266
 267       var groupSlices = this.slices;
 268       ops.sort(function(ix, iy) {
 269         var x = groupSlices[ix];
 270         var y = groupSlices[iy];
 271         if (x.start != y.start)
 272           return x.start - y.start;
 273
 274         // Elements get inserted into the slices array in order of when the
 275         // slices start. Because slices must be properly nested, we break
 276         // start-time ties by assuming that the elements appearing earlier
 277         // in the slices array (and thus ending earlier) start earlier.
 278         return ix - iy;
 279       });
 280
 281       var rootSlice = this.slices[ops[0]];
 282       this.topLevelSlices = [];
 283       this.topLevelSlices.push(rootSlice);
 284       for (var i = 1; i < ops.length; i++) {
 285         var slice = this.slices[ops[i]];
 286         if (!addSliceIfBounds(rootSlice, slice)) {
 287           rootSlice = slice;
 288           this.topLevelSlices.push(rootSlice);
 289         }
 290       }
 291     }
 292   };
 293
 294   /**
 295    * Merge two slice groups.
 296    *
 297    * If the two groups do not nest properly some of the slices of groupB will
 298    * be split to accomodate the improper nesting.  This is done to accomodate
 299    * combined kernel and userland call stacks on Android.  Because userland
 300    * tracing is done by writing to the trace_marker file, the kernel calls
 301    * that get invoked as part of that write may not be properly nested with
 302    * the userland call trace.  For example the following sequence may occur:
 303    *
 304    *     kernel enter sys_write        (the write to trace_marker)
 305    *     user   enter some_function
 306    *     kernel exit  sys_write
 307    *     ...
 308    *     kernel enter sys_write        (the write to trace_marker)
 309    *     user   exit  some_function
 310    *     kernel exit  sys_write
 311    *
 312    * This is handled by splitting the sys_write call into two slices as
 313    * follows:
 314    *
 315    *     | sys_write |            some_function            | sys_write (cont.) |
 316    *                 | sys_write (cont.) |     | sys_write |
 317    *
 318    * The colorId of both parts of the split slices are kept the same, and the
 319    * " (cont.)" suffix is appended to the later parts of a split slice.
 320    *
 321    * The two input SliceGroups are not modified by this, and the merged
 322    * SliceGroup will contain a copy of each of the input groups' slices (those
 323    * copies may be split).
 324    */
 325   SliceGroup.merge = function(groupA, groupB) {
 326     // This is implemented by traversing the two slice groups in reverse
 327     // order.  The slices in each group are sorted by ascending end-time, so
 328     // we must do the traversal from back to front in order to maintain the
 329     // sorting.
 330     //
 331     // We traverse the two groups simultaneously, merging as we go.  At each
 332     // iteration we choose the group from which to take the next slice based
 333     // on which group's next slice has the greater end-time.  During this
 334     // traversal we maintain a stack of currently "open" slices for each input
 335     // group.  A slice is considered "open" from the time it gets reached in
 336     // our input group traversal to the time we reach an slice in this
 337     // traversal with an end-time before the start time of the "open" slice.
 338     //
 339     // Each time a slice from groupA is opened or closed (events corresponding
 340     // to the end-time and start-time of the input slice, respectively) we
 341     // split all of the currently open slices from groupB.
 342
 343     if (groupA.openPartialSlices_.length > 0) {
 344       throw new Error('groupA has open partial slices');
 345     }
 346     if (groupB.openPartialSlices_.length > 0) {
 347       throw new Error('groupB has open partial slices');
 348     }
 349
 350     var result = new SliceGroup();
 351
 352     var slicesA = groupA.slices;
 353     var slicesB = groupB.slices;
 354     var idxA = 0;
 355     var idxB = 0;
 356     var openA = [];
 357     var openB = [];
 358
 359     var splitOpenSlices = function(when) {
 360       for (var i = 0; i < openB.length; i++) {
 361         var oldSlice = openB[i];
 362         var oldEnd = oldSlice.end;
 363         if (when < oldSlice.start || oldEnd < when) {
 364           throw new Error('slice should not be split');
 365         }
 366
 367         var newSlice = result.copySlice(oldSlice);
 368         newSlice.start = when;
 369         newSlice.duration = oldEnd - when;
 370         if (newSlice.title.indexOf(' (cont.)') == -1)
 371           newSlice.title += ' (cont.)';
 372         oldSlice.duration = when - oldSlice.start;
 373         openB[i] = newSlice;
 374         result.pushSlice(newSlice);
 375       }
 376     };
 377
 378     var closeOpenSlices = function(upTo) {
 379       while (openA.length > 0 || openB.length > 0) {
 380         var nextA = openA[openA.length - 1];
 381         var nextB = openB[openB.length - 1];
 382         var endA = nextA && nextA.end;
 383         var endB = nextB && nextB.end;
 384
 385         if ((endA === undefined || endA > upTo) &&
 386             (endB === undefined || endB > upTo)) {
 387           return;
 388         }
 389
 390         if (endB === undefined || endA < endB) {
 391           splitOpenSlices(endA);
 392           openA.pop();
 393         } else {
 394           openB.pop();
 395         }
 396       }
 397     };
 398
 399     while (idxA < slicesA.length || idxB < slicesB.length) {
 400       var sA = slicesA[idxA];
 401       var sB = slicesB[idxB];
 402       var nextSlice, isFromB;
 403
 404       if (sA === undefined || (sB !== undefined && sA.start > sB.start)) {
 405         nextSlice = result.copySlice(sB);
 406         isFromB = true;
 407         idxB++;
 408       } else {
 409         nextSlice = result.copySlice(sA);
 410         isFromB = false;
 411         idxA++;
 412       }
 413
 414       closeOpenSlices(nextSlice.start);
 415
 416       result.pushSlice(nextSlice);
 417
 418       if (isFromB) {
 419         openB.push(nextSlice);
 420       } else {
 421         splitOpenSlices(nextSlice.start);
 422         openA.push(nextSlice);
 423       }
 424     }
 425
 426     closeOpenSlices();
 427
 428     return result;
 429   };
 430
 431   return {
 432     SliceGroup: SliceGroup
 433   };
 434 });