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