<!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>