catapult/tracing/tracing/metrics/v8/utils.html - platform/external/chromium-trace - Git at Google

 <!DOCTYPE html>
 <!--
 Copyright 2016 The Chromium Authors. All rights reserved.
 Use of this source code is governed by a BSD-style license that can be
 found in the LICENSE file.
 -->

 <link rel="import" href="/tracing/base/piecewise_linear_function.html">
 <link rel="import" href="/tracing/base/range.html">
 <link rel="import" href="/tracing/base/range_utils.html">
 <link rel="import" href="/tracing/base/unit.html">
 <link rel="import" href="/tracing/metrics/metric_registry.html">
 <link rel="import" href="/tracing/value/histogram.html">

 <script>
 'use strict';

 tr.exportTo('tr.metrics.v8.utils', function() {
   // The title of the idle task event.
   var IDLE_TASK_EVENT = 'SingleThreadIdleTaskRunner::RunTask';

   // V8 execution event.
   var V8_EXECUTE = 'V8.Execute';

   // GC events start with this prefix.
   var GC_EVENT_PREFIX = 'V8.GC';

   // Special handling is required for full GCs inside low memory notification.
   var FULL_GC_EVENT = 'V8.GCCompactor';

   var LOW_MEMORY_EVENT = 'V8.GCLowMemoryNotification';

   var MAJOR_GC_EVENT = 'MajorGC';
   var MINOR_GC_EVENT = 'MinorGC';

   // Maps the top-level GC events in timeline to telemetry friendly names.
   var TOP_GC_EVENTS = {
       'V8.GCCompactor': 'v8-gc-full-mark-compactor',
       'V8.GCFinalizeMC': 'v8-gc-latency-mark-compactor',
       'V8.GCFinalizeMCReduceMemory': 'v8-gc-memory-mark-compactor',
       'V8.GCIncrementalMarking': 'v8-gc-incremental-step',
       'V8.GCIncrementalMarkingFinalize': 'v8-gc-incremental-finalize',
       'V8.GCIncrementalMarkingStart': 'v8-gc-incremental-start',
       'V8.GCPhantomHandleProcessingCallback' : 'v8-gc-phantom-handle-callback',
       'V8.GCScavenger': 'v8-gc-scavenger'
   };

   var LOW_MEMORY_MARK_COMPACTOR = 'v8-gc-low-memory-mark-compactor';

   /**
    * Finds the first parent of the |event| for which the |predicate| holds.
    */
   function findParent(event, predicate) {
     var parent = event.parentSlice;
     while (parent) {
       if (predicate(parent)) {
         return parent;
       }
       parent = parent.parentSlice;
     }
     return null;
   }

   function isIdleTask(event) {
     return event.title === IDLE_TASK_EVENT;
   }

   function isLowMemoryEvent(event) {
     return event.title === LOW_MEMORY_EVENT;
   }

   function isV8ExecuteEvent(event) {
     return event.title === V8_EXECUTE;
   }

   function isTopV8ExecuteEvent(event) {
     return isV8ExecuteEvent(event) && findParent(isV8ExecuteEvent) === null;
   }

   function isGarbageCollectionEvent(event) {
     // Low memory notification is handled specially because it contains
     // several full mark compact events.
     return event.title && event.title.startsWith(GC_EVENT_PREFIX) &&
            event.title != LOW_MEMORY_EVENT;
   }

   function isTopGarbageCollectionEvent(event) {
     return event.title in TOP_GC_EVENTS;
   }

   function isForcedGarbageCollectionEvent(event) {
     return findParent(event, isLowMemoryEvent) !== null;
   }

   function isSubGarbageCollectionEvent(event) {
     // To reduce number of results, we return only the first level of GC
     // subevents. Some subevents are nested in MajorGC or MinorGC events, so
     // we have to check for it explicitly.
     return isGarbageCollectionEvent(event) &&
            event.parentSlice &&
            (isTopGarbageCollectionEvent(event.parentSlice) ||
             event.parentSlice.title === MAJOR_GC_EVENT ||
             event.parentSlice.title === MINOR_GC_EVENT);
   }

   function topGarbageCollectionEventName(event) {
     if (event.title === FULL_GC_EVENT) {
       // Full mark compact events inside a low memory notification
       // are counted as low memory mark compacts.
       if (findParent(event, isLowMemoryEvent)) {
         return LOW_MEMORY_MARK_COMPACTOR;
       }
     }
     return TOP_GC_EVENTS[event.title];
   }

   function subGarbageCollectionEventName(event) {
     var topEvent = findParent(event, isTopGarbageCollectionEvent);
     var prefix = topEvent ? topGarbageCollectionEventName(topEvent) : 'unknown';
     // Remove redundant prefixes and convert to lower case.
     var name = event.title.replace('V8.GC_MC_', '')
                           .replace('V8.GC_SCAVENGER_', '')
                           .replace('V8.GC_', '')
                           .replace(/_/g, '-').toLowerCase();
     return prefix + '-' + name;
   }

   /**
    * Filters events using the |filterCallback|, then groups events by the user
    * the name computed using the |nameCallback|, and then invokes
    * the |processCallback| with the grouped events.
    * @param {Function} filterCallback Takes an event and returns a boolean.
    * @param {Function} nameCallback Takes event and returns a string.
    * @param {Function} processCallback Takes a name, and an array of events.
    */
   function groupAndProcessEvents(model, filterCallback,
                                  nameCallback, processCallback) {
     // Map: name -> [events].
     var nameToEvents = {};
     for (var event of model.getDescendantEvents()) {
       if (!filterCallback(event)) continue;
       var name = nameCallback(event);
       nameToEvents[name] = nameToEvents[name] || [];
       nameToEvents[name].push(event);
     }
     tr.b.iterItems(nameToEvents, function(name, events) {
       processCallback(name, events);
     });
   }

   /**
   * Given a list of intervals, returns a new list with all overalapping
   * intervals merged into a single interval.
   */
   function unionOfIntervals(intervals) {
     if (intervals.length === 0)
       return [];
     return tr.b.mergeRanges(
       intervals.map(x => ({min: x.start, max: x.end})), 1e-6,
       function(ranges) {
         return {
           start: ranges.reduce((acc, x) => Math.min(acc, x.min), ranges[0].min),
           end: ranges.reduce((acc, x) => Math.max(acc, x.max), ranges[0].max)
         };
       }
     );
   }

   /**
    * An end-point of a window that is sliding from left to right
    * over |points| starting from time |start|.
    * It is intended to be used only by the |mutatorUtilization| function.
    * @constructor
    */
   function WindowEndpoint(start, points) {
     this.points = points;
     // The index of the last passed point.
     this.lastIndex = -1;
     // The position of the end-point in the time line.
     this.position = start;
     // The distance until the next point.
     this.distanceUntilNextPoint = points[0].position - start;
     // The cumulative duration of GC pauses until this position.
     this.cummulativePause = 0;
     // The number of entered GC intervals.
     this.stackDepth = 0;
   }

   WindowEndpoint.prototype = {
     // Advance the end-point by the given |delta|.
     advance: function(delta) {
       var points = this.points;
       if (delta < this.distanceUntilNextPoint) {
         this.position += delta;
         this.cummulativePause += this.stackDepth > 0 ? delta : 0;
         this.distanceUntilNextPoint =
             points[this.lastIndex + 1].position - this.position;
       } else {
         this.position += this.distanceUntilNextPoint;
         this.cummulativePause +=
             this.stackDepth > 0 ? this.distanceUntilNextPoint : 0;
         this.distanceUntilNextPoint = 0;
         this.lastIndex++;
         if (this.lastIndex < points.length) {
           this.stackDepth += points[this.lastIndex].delta;
           if (this.lastIndex + 1 < points.length)
             this.distanceUntilNextPoint =
                 points[this.lastIndex + 1].position - this.position;
         }
       }
     }
   };

   /**
    * Returns mutator utilization as a piecewise linear function.
    * Mutator utilization for a window size w is a function of time mu_w(t)
    * that shows how much time in [t, t+w] is left for the mutator relative
    * to the time window size.
    * More formally:
    * mu_w(t) = (w - total_time_spent_in_gc_in(t, t + w)) / w.
    * The range of mu_w(t) is [0..1].
    * See "A Parallel, Real-Time Garbage Collector" by Cheng et. al. for
    * more info [https://www.cs.cmu.edu/~guyb/papers/gc2001.pdf].
    *
    * All parameters must use the same time unit.
    * @param {number} start The start time of execution.
    * @param {number} end The end time of execution.
    * @param {number} timeWindow The size of the time window.
    * @param {!Array<!{start: number, end: number}>} intervals The list of
    *     GC pauses.
    */
   function mutatorUtilization(start, end, timeWindow, intervals) {
     var mu = new tr.b.PiecewiseLinearFunction();
     // If the interval is smaller than the time window, then the function is
     // empty.
     if (end - start <= timeWindow)
       return mu;
     // If there are GC pauses then the mutator utilization is 1.0.
     if (intervals.length === 0) {
       mu.push(start, 1.0, end - timeWindow, 1.0);
       return mu;
     }
     intervals = unionOfIntervals(intervals);
     // Create a point for the start and the end of each interval.
     var points = [];
     intervals.forEach(function(interval) {
       points.push({position: interval.start, delta: 1});
       points.push({position: interval.end, delta: -1});
     });
     points.sort((a, b) => a.position - b.position);
     points.push({position: end, delta: 0});
     // The left and the right limit of the sliding window.
     var left = new WindowEndpoint(start, points);
     var right = new WindowEndpoint(start, points);
     // Advance the right end-point until we get the correct window size.
     while (right.position - left.position < timeWindow)
       right.advance(timeWindow - (right.position - left.position));
     while (right.lastIndex < points.length) {
       // Advance the window end-points by the largest possible amount
       // without jumping over a point.
       var distanceUntilNextPoint =
           Math.min(left.distanceUntilNextPoint, right.distanceUntilNextPoint);
       var position1 = left.position;
       var value1 = right.cummulativePause - left.cummulativePause;
       left.advance(distanceUntilNextPoint);
       right.advance(distanceUntilNextPoint);
       // Add a new mutator utilization segment only if it is non-trivial.
       if (distanceUntilNextPoint > 0) {
         var position2 = left.position;
         var value2 = right.cummulativePause - left.cummulativePause;
         mu.push(position1, 1.0 - value1 / timeWindow,
                 position2, 1.0 - value2 / timeWindow);
       }
     }
     return mu;
   }

   function hasV8Stats(globalMemoryDump) {
     var v8stats = undefined;
     globalMemoryDump.iterateContainerDumps(function(dump) {
       v8stats = v8stats || dump.getMemoryAllocatorDumpByFullName('v8');
     });
     return !!v8stats;
   }

   function rangeForMemoryDumps(model) {
     var startOfFirstDumpWithV8 =
         model.globalMemoryDumps.filter(hasV8Stats).reduce(
             (start, dump) => Math.min(start, dump.start), Infinity);
     if (startOfFirstDumpWithV8 === Infinity)
       return new tr.b.Range(); // Empty range.
     return tr.b.Range.fromExplicitRange(startOfFirstDumpWithV8, Infinity);
   }

   return {
     findParent: findParent,
     groupAndProcessEvents: groupAndProcessEvents,
     isForcedGarbageCollectionEvent: isForcedGarbageCollectionEvent,
     isGarbageCollectionEvent: isGarbageCollectionEvent,
     isIdleTask: isIdleTask,
     isLowMemoryEvent: isLowMemoryEvent,
     isSubGarbageCollectionEvent: isSubGarbageCollectionEvent,
     isTopGarbageCollectionEvent: isTopGarbageCollectionEvent,
     isTopV8ExecuteEvent: isTopV8ExecuteEvent,
     isV8ExecuteEvent: isV8ExecuteEvent,
     mutatorUtilization: mutatorUtilization,
     subGarbageCollectionEventName: subGarbageCollectionEventName,
     topGarbageCollectionEventName: topGarbageCollectionEventName,
     rangeForMemoryDumps: rangeForMemoryDumps,
     unionOfIntervals: unionOfIntervals
   };
 });
 </script>
	<!DOCTYPE html>
	<!--
	Copyright 2016 The Chromium Authors. All rights reserved.
	Use of this source code is governed by a BSD-style license that can be
	found in the LICENSE file.
	-->

	<link rel="import" href="/tracing/base/piecewise_linear_function.html">
	<link rel="import" href="/tracing/base/range.html">
	<link rel="import" href="/tracing/base/range_utils.html">
	<link rel="import" href="/tracing/base/unit.html">
	<link rel="import" href="/tracing/metrics/metric_registry.html">
	<link rel="import" href="/tracing/value/histogram.html">

	<script>
	'use strict';

	tr.exportTo('tr.metrics.v8.utils', function() {
	// The title of the idle task event.
	var IDLE_TASK_EVENT = 'SingleThreadIdleTaskRunner::RunTask';

	// V8 execution event.
	var V8_EXECUTE = 'V8.Execute';

	// GC events start with this prefix.
	var GC_EVENT_PREFIX = 'V8.GC';

	// Special handling is required for full GCs inside low memory notification.
	var FULL_GC_EVENT = 'V8.GCCompactor';

	var LOW_MEMORY_EVENT = 'V8.GCLowMemoryNotification';

	var MAJOR_GC_EVENT = 'MajorGC';
	var MINOR_GC_EVENT = 'MinorGC';

	// Maps the top-level GC events in timeline to telemetry friendly names.
	var TOP_GC_EVENTS = {
	'V8.GCCompactor': 'v8-gc-full-mark-compactor',
	'V8.GCFinalizeMC': 'v8-gc-latency-mark-compactor',
	'V8.GCFinalizeMCReduceMemory': 'v8-gc-memory-mark-compactor',
	'V8.GCIncrementalMarking': 'v8-gc-incremental-step',
	'V8.GCIncrementalMarkingFinalize': 'v8-gc-incremental-finalize',
	'V8.GCIncrementalMarkingStart': 'v8-gc-incremental-start',
	'V8.GCPhantomHandleProcessingCallback' : 'v8-gc-phantom-handle-callback',
	'V8.GCScavenger': 'v8-gc-scavenger'
	};

	var LOW_MEMORY_MARK_COMPACTOR = 'v8-gc-low-memory-mark-compactor';

	/**
	* Finds the first parent of the \|event\| for which the \|predicate\| holds.
	*/
	function findParent(event, predicate) {
	var parent = event.parentSlice;
	while (parent) {
	if (predicate(parent)) {
	return parent;
	}
	parent = parent.parentSlice;
	}
	return null;
	}

	function isIdleTask(event) {
	return event.title === IDLE_TASK_EVENT;
	}

	function isLowMemoryEvent(event) {
	return event.title === LOW_MEMORY_EVENT;
	}

	function isV8ExecuteEvent(event) {
	return event.title === V8_EXECUTE;
	}

	function isTopV8ExecuteEvent(event) {
	return isV8ExecuteEvent(event) && findParent(isV8ExecuteEvent) === null;
	}

	function isGarbageCollectionEvent(event) {
	// Low memory notification is handled specially because it contains
	// several full mark compact events.
	return event.title && event.title.startsWith(GC_EVENT_PREFIX) &&
	event.title != LOW_MEMORY_EVENT;
	}

	function isTopGarbageCollectionEvent(event) {
	return event.title in TOP_GC_EVENTS;
	}

	function isForcedGarbageCollectionEvent(event) {
	return findParent(event, isLowMemoryEvent) !== null;
	}

	function isSubGarbageCollectionEvent(event) {
	// To reduce number of results, we return only the first level of GC
	// subevents. Some subevents are nested in MajorGC or MinorGC events, so
	// we have to check for it explicitly.
	return isGarbageCollectionEvent(event) &&
	event.parentSlice &&
	(isTopGarbageCollectionEvent(event.parentSlice) \|\|
	event.parentSlice.title === MAJOR_GC_EVENT \|\|
	event.parentSlice.title === MINOR_GC_EVENT);
	}

	function topGarbageCollectionEventName(event) {
	if (event.title === FULL_GC_EVENT) {
	// Full mark compact events inside a low memory notification
	// are counted as low memory mark compacts.
	if (findParent(event, isLowMemoryEvent)) {
	return LOW_MEMORY_MARK_COMPACTOR;
	}
	}
	return TOP_GC_EVENTS[event.title];
	}

	function subGarbageCollectionEventName(event) {
	var topEvent = findParent(event, isTopGarbageCollectionEvent);
	var prefix = topEvent ? topGarbageCollectionEventName(topEvent) : 'unknown';
	// Remove redundant prefixes and convert to lower case.
	var name = event.title.replace('V8.GC_MC_', '')
	.replace('V8.GC_SCAVENGER_', '')
	.replace('V8.GC_', '')
	.replace(/_/g, '-').toLowerCase();
	return prefix + '-' + name;
	}

	/**
	* Filters events using the \|filterCallback\|, then groups events by the user
	* the name computed using the \|nameCallback\|, and then invokes
	* the \|processCallback\| with the grouped events.
	* @param {Function} filterCallback Takes an event and returns a boolean.
	* @param {Function} nameCallback Takes event and returns a string.
	* @param {Function} processCallback Takes a name, and an array of events.
	*/
	function groupAndProcessEvents(model, filterCallback,
	nameCallback, processCallback) {
	// Map: name -> [events].
	var nameToEvents = {};
	for (var event of model.getDescendantEvents()) {
	if (!filterCallback(event)) continue;
	var name = nameCallback(event);
	nameToEvents[name] = nameToEvents[name] \|\| [];
	nameToEvents[name].push(event);
	}
	tr.b.iterItems(nameToEvents, function(name, events) {
	processCallback(name, events);
	});
	}

	/**
	* Given a list of intervals, returns a new list with all overalapping
	* intervals merged into a single interval.
	*/
	function unionOfIntervals(intervals) {
	if (intervals.length === 0)
	return [];
	return tr.b.mergeRanges(
	intervals.map(x => ({min: x.start, max: x.end})), 1e-6,
	function(ranges) {
	return {
	start: ranges.reduce((acc, x) => Math.min(acc, x.min), ranges[0].min),
	end: ranges.reduce((acc, x) => Math.max(acc, x.max), ranges[0].max)
	};
	}
	);
	}

	/**
	* An end-point of a window that is sliding from left to right
	* over \|points\| starting from time \|start\|.
	* It is intended to be used only by the \|mutatorUtilization\| function.
	* @constructor
	*/
	function WindowEndpoint(start, points) {
	this.points = points;
	// The index of the last passed point.
	this.lastIndex = -1;
	// The position of the end-point in the time line.
	this.position = start;
	// The distance until the next point.
	this.distanceUntilNextPoint = points[0].position - start;
	// The cumulative duration of GC pauses until this position.
	this.cummulativePause = 0;
	// The number of entered GC intervals.
	this.stackDepth = 0;
	}

	WindowEndpoint.prototype = {
	// Advance the end-point by the given \|delta\|.
	advance: function(delta) {
	var points = this.points;
	if (delta < this.distanceUntilNextPoint) {
	this.position += delta;
	this.cummulativePause += this.stackDepth > 0 ? delta : 0;
	this.distanceUntilNextPoint =
	points[this.lastIndex + 1].position - this.position;
	} else {
	this.position += this.distanceUntilNextPoint;
	this.cummulativePause +=
	this.stackDepth > 0 ? this.distanceUntilNextPoint : 0;
	this.distanceUntilNextPoint = 0;
	this.lastIndex++;
	if (this.lastIndex < points.length) {
	this.stackDepth += points[this.lastIndex].delta;
	if (this.lastIndex + 1 < points.length)
	this.distanceUntilNextPoint =
	points[this.lastIndex + 1].position - this.position;
	}
	}
	}
	};

	/**
	* Returns mutator utilization as a piecewise linear function.
	* Mutator utilization for a window size w is a function of time mu_w(t)
	* that shows how much time in [t, t+w] is left for the mutator relative
	* to the time window size.
	* More formally:
	* mu_w(t) = (w - total_time_spent_in_gc_in(t, t + w)) / w.
	* The range of mu_w(t) is [0..1].
	* See "A Parallel, Real-Time Garbage Collector" by Cheng et. al. for
	* more info [https://www.cs.cmu.edu/~guyb/papers/gc2001.pdf].
	*
	* All parameters must use the same time unit.
	* @param {number} start The start time of execution.
	* @param {number} end The end time of execution.
	* @param {number} timeWindow The size of the time window.
	* @param {!Array<!{start: number, end: number}>} intervals The list of
	* GC pauses.
	*/
	function mutatorUtilization(start, end, timeWindow, intervals) {
	var mu = new tr.b.PiecewiseLinearFunction();
	// If the interval is smaller than the time window, then the function is
	// empty.
	if (end - start <= timeWindow)
	return mu;
	// If there are GC pauses then the mutator utilization is 1.0.
	if (intervals.length === 0) {
	mu.push(start, 1.0, end - timeWindow, 1.0);
	return mu;
	}
	intervals = unionOfIntervals(intervals);
	// Create a point for the start and the end of each interval.
	var points = [];
	intervals.forEach(function(interval) {
	points.push({position: interval.start, delta: 1});
	points.push({position: interval.end, delta: -1});
	});
	points.sort((a, b) => a.position - b.position);
	points.push({position: end, delta: 0});
	// The left and the right limit of the sliding window.
	var left = new WindowEndpoint(start, points);
	var right = new WindowEndpoint(start, points);
	// Advance the right end-point until we get the correct window size.
	while (right.position - left.position < timeWindow)
	right.advance(timeWindow - (right.position - left.position));
	while (right.lastIndex < points.length) {
	// Advance the window end-points by the largest possible amount
	// without jumping over a point.
	var distanceUntilNextPoint =
	Math.min(left.distanceUntilNextPoint, right.distanceUntilNextPoint);
	var position1 = left.position;
	var value1 = right.cummulativePause - left.cummulativePause;
	left.advance(distanceUntilNextPoint);
	right.advance(distanceUntilNextPoint);
	// Add a new mutator utilization segment only if it is non-trivial.
	if (distanceUntilNextPoint > 0) {
	var position2 = left.position;
	var value2 = right.cummulativePause - left.cummulativePause;
	mu.push(position1, 1.0 - value1 / timeWindow,
	position2, 1.0 - value2 / timeWindow);
	}
	}
	return mu;
	}

	function hasV8Stats(globalMemoryDump) {
	var v8stats = undefined;
	globalMemoryDump.iterateContainerDumps(function(dump) {
	v8stats = v8stats \|\| dump.getMemoryAllocatorDumpByFullName('v8');
	});
	return !!v8stats;
	}

	function rangeForMemoryDumps(model) {
	var startOfFirstDumpWithV8 =
	model.globalMemoryDumps.filter(hasV8Stats).reduce(
	(start, dump) => Math.min(start, dump.start), Infinity);
	if (startOfFirstDumpWithV8 === Infinity)
	return new tr.b.Range(); // Empty range.
	return tr.b.Range.fromExplicitRange(startOfFirstDumpWithV8, Infinity);
	}

	return {
	findParent: findParent,
	groupAndProcessEvents: groupAndProcessEvents,
	isForcedGarbageCollectionEvent: isForcedGarbageCollectionEvent,
	isGarbageCollectionEvent: isGarbageCollectionEvent,
	isIdleTask: isIdleTask,
	isLowMemoryEvent: isLowMemoryEvent,
	isSubGarbageCollectionEvent: isSubGarbageCollectionEvent,
	isTopGarbageCollectionEvent: isTopGarbageCollectionEvent,
	isTopV8ExecuteEvent: isTopV8ExecuteEvent,
	isV8ExecuteEvent: isV8ExecuteEvent,
	mutatorUtilization: mutatorUtilization,
	subGarbageCollectionEventName: subGarbageCollectionEventName,
	topGarbageCollectionEventName: topGarbageCollectionEventName,
	rangeForMemoryDumps: rangeForMemoryDumps,
	unionOfIntervals: unionOfIntervals
	};
	});
	</script>