src/third_party/trace-viewer/trace_viewer/tracing/trace_model/slice_group.html

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