path: root/chromium/v8/src/heap/gc-idle-time-handler.cc

// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/heap/gc-idle-time-handler.h"
#include "src/heap/gc-tracer.h"
#include "src/utils.h"

namespace v8 {
namespace internal {

const double GCIdleTimeHandler::kConservativeTimeRatio = 0.9;
const size_t GCIdleTimeHandler::kMaxMarkCompactTimeInMs = 1000;
const size_t GCIdleTimeHandler::kMaxFinalIncrementalMarkCompactTimeInMs = 1000;
const double GCIdleTimeHandler::kHighContextDisposalRate = 100;
const size_t GCIdleTimeHandler::kMinTimeForOverApproximatingWeakClosureInMs = 1;


void GCIdleTimeAction::Print() {
  switch (type) {
    case DONE:
      PrintF("done");
      break;
    case DO_NOTHING:
      PrintF("no action");
      break;
    case DO_INCREMENTAL_MARKING:
      PrintF("incremental marking with step %" V8_PTR_PREFIX "d / ms",
             parameter);
      if (additional_work) {
        PrintF("; finalized marking");
      }
      break;
    case DO_SCAVENGE:
      PrintF("scavenge");
      break;
    case DO_FULL_GC:
      PrintF("full GC");
      break;
    case DO_FINALIZE_SWEEPING:
      PrintF("finalize sweeping");
      break;
  }
}


void GCIdleTimeHandler::HeapState::Print() {
  PrintF("contexts_disposed=%d ", contexts_disposed);
  PrintF("contexts_disposal_rate=%f ", contexts_disposal_rate);
  PrintF("size_of_objects=%" V8_PTR_PREFIX "d ", size_of_objects);
  PrintF("incremental_marking_stopped=%d ", incremental_marking_stopped);
  PrintF("can_start_incremental_marking=%d ", can_start_incremental_marking);
  PrintF("sweeping_in_progress=%d ", sweeping_in_progress);
  PrintF("mark_compact_speed=%" V8_PTR_PREFIX "d ",
         mark_compact_speed_in_bytes_per_ms);
  PrintF("incremental_marking_speed=%" V8_PTR_PREFIX "d ",
         incremental_marking_speed_in_bytes_per_ms);
  PrintF("scavenge_speed=%" V8_PTR_PREFIX "d ", scavenge_speed_in_bytes_per_ms);
  PrintF("new_space_size=%" V8_PTR_PREFIX "d ", used_new_space_size);
  PrintF("new_space_capacity=%" V8_PTR_PREFIX "d ", new_space_capacity);
  PrintF("new_space_allocation_throughput=%" V8_PTR_PREFIX "d",
         new_space_allocation_throughput_in_bytes_per_ms);
}


size_t GCIdleTimeHandler::EstimateMarkingStepSize(
    size_t idle_time_in_ms, size_t marking_speed_in_bytes_per_ms) {
  DCHECK(idle_time_in_ms > 0);

  if (marking_speed_in_bytes_per_ms == 0) {
    marking_speed_in_bytes_per_ms = kInitialConservativeMarkingSpeed;
  }

  size_t marking_step_size = marking_speed_in_bytes_per_ms * idle_time_in_ms;
  if (marking_step_size / marking_speed_in_bytes_per_ms != idle_time_in_ms) {
    // In the case of an overflow we return maximum marking step size.
    return kMaximumMarkingStepSize;
  }

  if (marking_step_size > kMaximumMarkingStepSize)
    return kMaximumMarkingStepSize;

  return static_cast<size_t>(marking_step_size * kConservativeTimeRatio);
}


size_t GCIdleTimeHandler::EstimateMarkCompactTime(
    size_t size_of_objects, size_t mark_compact_speed_in_bytes_per_ms) {
  // TODO(hpayer): Be more precise about the type of mark-compact event. It
  // makes a huge difference if compaction is happening.
  if (mark_compact_speed_in_bytes_per_ms == 0) {
    mark_compact_speed_in_bytes_per_ms = kInitialConservativeMarkCompactSpeed;
  }
  size_t result = size_of_objects / mark_compact_speed_in_bytes_per_ms;
  return Min(result, kMaxMarkCompactTimeInMs);
}


size_t GCIdleTimeHandler::EstimateFinalIncrementalMarkCompactTime(
    size_t size_of_objects,
    size_t final_incremental_mark_compact_speed_in_bytes_per_ms) {
  if (final_incremental_mark_compact_speed_in_bytes_per_ms == 0) {
    final_incremental_mark_compact_speed_in_bytes_per_ms =
        kInitialConservativeFinalIncrementalMarkCompactSpeed;
  }
  size_t result =
      size_of_objects / final_incremental_mark_compact_speed_in_bytes_per_ms;
  return Min(result, kMaxFinalIncrementalMarkCompactTimeInMs);
}


bool GCIdleTimeHandler::ShouldDoScavenge(
    size_t idle_time_in_ms, size_t new_space_size, size_t used_new_space_size,
    size_t scavenge_speed_in_bytes_per_ms,
    size_t new_space_allocation_throughput_in_bytes_per_ms) {
  size_t new_space_allocation_limit =
      kMaxScheduledIdleTime * scavenge_speed_in_bytes_per_ms;

  // If the limit is larger than the new space size, then scavenging used to be
  // really fast. We can take advantage of the whole new space.
  if (new_space_allocation_limit > new_space_size) {
    new_space_allocation_limit = new_space_size;
  }

  // We do not know the allocation throughput before the first Scavenge.
  // TODO(hpayer): Estimate allocation throughput before the first Scavenge.
  if (new_space_allocation_throughput_in_bytes_per_ms == 0) {
    new_space_allocation_limit =
        static_cast<size_t>(new_space_size * kConservativeTimeRatio);
  } else {
    // We have to trigger scavenge before we reach the end of new space.
    size_t adjust_limit = new_space_allocation_throughput_in_bytes_per_ms *
                          kTimeUntilNextIdleEvent;
    if (adjust_limit > new_space_allocation_limit)
      new_space_allocation_limit = 0;
    else
      new_space_allocation_limit -= adjust_limit;
  }

  if (scavenge_speed_in_bytes_per_ms == 0) {
    scavenge_speed_in_bytes_per_ms = kInitialConservativeScavengeSpeed;
  }

  if (new_space_allocation_limit <= used_new_space_size) {
    if (used_new_space_size / scavenge_speed_in_bytes_per_ms <=
        idle_time_in_ms) {
      return true;
    }
  }
  return false;
}


bool GCIdleTimeHandler::ShouldDoMarkCompact(
    size_t idle_time_in_ms, size_t size_of_objects,
    size_t mark_compact_speed_in_bytes_per_ms) {
  return idle_time_in_ms >= kMaxScheduledIdleTime &&
         idle_time_in_ms >=
             EstimateMarkCompactTime(size_of_objects,
                                     mark_compact_speed_in_bytes_per_ms);
}


bool GCIdleTimeHandler::ShouldDoContextDisposalMarkCompact(
    int contexts_disposed, double contexts_disposal_rate) {
  return contexts_disposed > 0 && contexts_disposal_rate > 0 &&
         contexts_disposal_rate < kHighContextDisposalRate;
}


bool GCIdleTimeHandler::ShouldDoFinalIncrementalMarkCompact(
    size_t idle_time_in_ms, size_t size_of_objects,
    size_t final_incremental_mark_compact_speed_in_bytes_per_ms) {
  return idle_time_in_ms >=
         EstimateFinalIncrementalMarkCompactTime(
             size_of_objects,
             final_incremental_mark_compact_speed_in_bytes_per_ms);
}


bool GCIdleTimeHandler::ShouldDoOverApproximateWeakClosure(
    size_t idle_time_in_ms) {
  // TODO(jochen): Estimate the time it will take to build the object groups.
  return idle_time_in_ms >= kMinTimeForOverApproximatingWeakClosureInMs;
}


GCIdleTimeAction GCIdleTimeHandler::NothingOrDone() {
  if (idle_times_which_made_no_progress_per_mode_ >=
      kMaxNoProgressIdleTimesPerMode) {
    return GCIdleTimeAction::Done();
  } else {
    idle_times_which_made_no_progress_per_mode_++;
    return GCIdleTimeAction::Nothing();
  }
}


// The idle time handler has three modes and transitions between them
// as shown in the diagram:
//
//  kReduceLatency -----> kReduceMemory -----> kDone
//      ^    ^                  |                |
//      |    |                  |                |
//      |    +------------------+                |
//      |                                        |
//      +----------------------------------------+
//
// In kReduceLatency mode the handler only starts incremental marking
// if can_start_incremental_marking is false.
// In kReduceMemory mode the handler can force a new GC cycle by starting
// incremental marking even if can_start_incremental_marking is false. It can
// cause at most X idle GCs.
// In kDone mode the idle time handler does nothing.
//
// The initial mode is kReduceLatency.
//
// kReduceLatency => kReduceMemory transition happens if there were Y
// consecutive long idle notifications without any mutator GC. This is our
// notion of "mutator is idle".
//
// kReduceMemory => kDone transition happens after X idle GCs.
//
// kReduceMemory => kReduceLatency transition happens if N mutator GCs
// were performed meaning that the mutator is active.
//
// kDone => kReduceLatency transition happens if there were M mutator GCs or
// context was disposed.
//
// X = kMaxIdleMarkCompacts
// Y = kLongIdleNotificationsBeforeMutatorIsIdle
// N = #(idle GCs)
// M = kGCsBeforeMutatorIsActive
GCIdleTimeAction GCIdleTimeHandler::Compute(double idle_time_in_ms,
                                            HeapState heap_state) {
  Mode next_mode = NextMode(heap_state);

  if (next_mode != mode_) {
    mode_ = next_mode;
    ResetCounters();
  }

  UpdateCounters(idle_time_in_ms);

  if (mode_ == kDone) {
    return GCIdleTimeAction::Done();
  } else {
    return Action(idle_time_in_ms, heap_state, mode_ == kReduceMemory);
  }
}


// The following logic is implemented by the controller:
// (1) If we don't have any idle time, do nothing, unless a context was
// disposed, incremental marking is stopped, and the heap is small. Then do
// a full GC.
// (2) If the new space is almost full and we can afford a Scavenge or if the
// next Scavenge will very likely take long, then a Scavenge is performed.
// (3) If incremental marking is done, we perform a full garbage collection
// if  we are allowed to still do full garbage collections during this idle
// round or if we are not allowed to start incremental marking. Otherwise we
// do not perform garbage collection to keep system utilization low.
// (4) If sweeping is in progress and we received a large enough idle time
// request, we finalize sweeping here.
// (5) If incremental marking is in progress, we perform a marking step. Note,
// that this currently may trigger a full garbage collection.
GCIdleTimeAction GCIdleTimeHandler::Action(double idle_time_in_ms,
                                           const HeapState& heap_state,
                                           bool reduce_memory) {
  if (static_cast<int>(idle_time_in_ms) <= 0) {
    if (heap_state.incremental_marking_stopped) {
      if (ShouldDoContextDisposalMarkCompact(
              heap_state.contexts_disposed,
              heap_state.contexts_disposal_rate)) {
        return GCIdleTimeAction::FullGC(false);
      }
    }
    return GCIdleTimeAction::Nothing();
  }

  if (ShouldDoScavenge(
          static_cast<size_t>(idle_time_in_ms), heap_state.new_space_capacity,
          heap_state.used_new_space_size,
          heap_state.scavenge_speed_in_bytes_per_ms,
          heap_state.new_space_allocation_throughput_in_bytes_per_ms)) {
    return GCIdleTimeAction::Scavenge();
  }

  if (heap_state.incremental_marking_stopped && reduce_memory) {
    if (ShouldDoMarkCompact(static_cast<size_t>(idle_time_in_ms),
                            heap_state.size_of_objects,
                            heap_state.mark_compact_speed_in_bytes_per_ms)) {
      return GCIdleTimeAction::FullGC(reduce_memory);
    }
  }

  if (heap_state.sweeping_in_progress) {
    if (heap_state.sweeping_completed) {
      return GCIdleTimeAction::FinalizeSweeping();
    } else {
      return NothingOrDone();
    }
  }

  if (heap_state.incremental_marking_stopped &&
      !heap_state.can_start_incremental_marking && !reduce_memory) {
    return NothingOrDone();
  }

  size_t step_size = EstimateMarkingStepSize(
      static_cast<size_t>(kIncrementalMarkingStepTimeInMs),
      heap_state.incremental_marking_speed_in_bytes_per_ms);
  return GCIdleTimeAction::IncrementalMarking(step_size, reduce_memory);
}


void GCIdleTimeHandler::UpdateCounters(double idle_time_in_ms) {
  if (mode_ == kReduceLatency) {
    int gcs = scavenges_ + mark_compacts_;
    if (gcs > 0) {
      // There was a GC since the last notification.
      long_idle_notifications_ = 0;
      background_idle_notifications_ = 0;
    }
    idle_mark_compacts_ = 0;
    mark_compacts_ = 0;
    scavenges_ = 0;
    if (idle_time_in_ms >= kMinBackgroundIdleTime) {
      background_idle_notifications_++;
    } else if (idle_time_in_ms >= kMinLongIdleTime) {
      long_idle_notifications_++;
    }
  }
}


void GCIdleTimeHandler::ResetCounters() {
  long_idle_notifications_ = 0;
  background_idle_notifications_ = 0;
  idle_mark_compacts_ = 0;
  mark_compacts_ = 0;
  scavenges_ = 0;
  idle_times_which_made_no_progress_per_mode_ = 0;
}


bool GCIdleTimeHandler::IsMutatorActive(int contexts_disposed,
                                        int mark_compacts) {
  return contexts_disposed > 0 ||
         mark_compacts >= kMarkCompactsBeforeMutatorIsActive;
}


bool GCIdleTimeHandler::IsMutatorIdle(int long_idle_notifications,
                                      int background_idle_notifications,
                                      int mutator_gcs) {
  return mutator_gcs == 0 &&
         (long_idle_notifications >=
              kLongIdleNotificationsBeforeMutatorIsIdle ||
          background_idle_notifications >=
              kBackgroundIdleNotificationsBeforeMutatorIsIdle);
}


GCIdleTimeHandler::Mode GCIdleTimeHandler::NextMode(
    const HeapState& heap_state) {
  DCHECK(mark_compacts_ >= idle_mark_compacts_);
  int mutator_gcs = scavenges_ + mark_compacts_ - idle_mark_compacts_;
  switch (mode_) {
    case kDone:
      DCHECK(idle_mark_compacts_ == 0);
      if (IsMutatorActive(heap_state.contexts_disposed, mark_compacts_)) {
        return kReduceLatency;
      }
      break;
    case kReduceLatency:
      if (IsMutatorIdle(long_idle_notifications_,
                        background_idle_notifications_, mutator_gcs)) {
        return kReduceMemory;
      }
      break;
    case kReduceMemory:
      if (idle_mark_compacts_ >= kMaxIdleMarkCompacts) {
        return kDone;
      }
      if (mutator_gcs > idle_mark_compacts_) {
        return kReduceLatency;
      }
      break;
  }
  return mode_;
}
}
}