deps/v8/src/heap/gc-idle-time-handler.cc

   1 // Copyright 2014 the V8 project 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 #include "src/heap/gc-idle-time-handler.h"
   6 #include "src/heap/gc-tracer.h"
   7 #include "src/utils.h"
   8
   9 namespace v8 {
  10 namespace internal {
  11
  12 const double GCIdleTimeHandler::kConservativeTimeRatio = 0.9;
  13 const size_t GCIdleTimeHandler::kMaxMarkCompactTimeInMs = 1000;
  14 const size_t GCIdleTimeHandler::kMaxFinalIncrementalMarkCompactTimeInMs = 1000;
  15 const size_t GCIdleTimeHandler::kMinTimeForFinalizeSweeping = 100;
  16 const int GCIdleTimeHandler::kMaxMarkCompactsInIdleRound = 2;
  17 const int GCIdleTimeHandler::kIdleScavengeThreshold = 5;
  18 const double GCIdleTimeHandler::kHighContextDisposalRate = 100;
  19 const size_t GCIdleTimeHandler::kMinTimeForOverApproximatingWeakClosureInMs = 1;
  20
  21
  22 void GCIdleTimeAction::Print() {
  23   switch (type) {
  24     case DONE:
  25       PrintF("done");
  26       break;
  27     case DO_NOTHING:
  28       PrintF("no action");
  29       break;
  30     case DO_INCREMENTAL_MARKING:
  31       PrintF("incremental marking with step %" V8_PTR_PREFIX "d / ms",
  32              parameter);
  33       if (additional_work) {
  34         PrintF("; finalized marking");
  35       }
  36       break;
  37     case DO_SCAVENGE:
  38       PrintF("scavenge");
  39       break;
  40     case DO_FULL_GC:
  41       PrintF("full GC");
  42       break;
  43     case DO_FINALIZE_SWEEPING:
  44       PrintF("finalize sweeping");
  45       break;
  46   }
  47 }
  48
  49
  50 void GCIdleTimeHandler::HeapState::Print() {
  51   PrintF("contexts_disposed=%d ", contexts_disposed);
  52   PrintF("contexts_disposal_rate=%f ", contexts_disposal_rate);
  53   PrintF("size_of_objects=%" V8_PTR_PREFIX "d ", size_of_objects);
  54   PrintF("incremental_marking_stopped=%d ", incremental_marking_stopped);
  55   PrintF("can_start_incremental_marking=%d ", can_start_incremental_marking);
  56   PrintF("sweeping_in_progress=%d ", sweeping_in_progress);
  57   PrintF("mark_compact_speed=%" V8_PTR_PREFIX "d ",
  58          mark_compact_speed_in_bytes_per_ms);
  59   PrintF("incremental_marking_speed=%" V8_PTR_PREFIX "d ",
  60          incremental_marking_speed_in_bytes_per_ms);
  61   PrintF("scavenge_speed=%" V8_PTR_PREFIX "d ", scavenge_speed_in_bytes_per_ms);
  62   PrintF("new_space_size=%" V8_PTR_PREFIX "d ", used_new_space_size);
  63   PrintF("new_space_capacity=%" V8_PTR_PREFIX "d ", new_space_capacity);
  64   PrintF("new_space_allocation_throughput=%" V8_PTR_PREFIX "d",
  65          new_space_allocation_throughput_in_bytes_per_ms);
  66 }
  67
  68
  69 size_t GCIdleTimeHandler::EstimateMarkingStepSize(
  70     size_t idle_time_in_ms, size_t marking_speed_in_bytes_per_ms) {
  71   DCHECK(idle_time_in_ms > 0);
  72
  73   if (marking_speed_in_bytes_per_ms == 0) {
  74     marking_speed_in_bytes_per_ms = kInitialConservativeMarkingSpeed;
  75   }
  76
  77   size_t marking_step_size = marking_speed_in_bytes_per_ms * idle_time_in_ms;
  78   if (marking_step_size / marking_speed_in_bytes_per_ms != idle_time_in_ms) {
  79     // In the case of an overflow we return maximum marking step size.
  80     return kMaximumMarkingStepSize;
  81   }
  82
  83   if (marking_step_size > kMaximumMarkingStepSize)
  84     return kMaximumMarkingStepSize;
  85
  86   return static_cast<size_t>(marking_step_size * kConservativeTimeRatio);
  87 }
  88
  89
  90 size_t GCIdleTimeHandler::EstimateMarkCompactTime(
  91     size_t size_of_objects, size_t mark_compact_speed_in_bytes_per_ms) {
  92   // TODO(hpayer): Be more precise about the type of mark-compact event. It
  93   // makes a huge difference if compaction is happening.
  94   if (mark_compact_speed_in_bytes_per_ms == 0) {
  95     mark_compact_speed_in_bytes_per_ms = kInitialConservativeMarkCompactSpeed;
  96   }
  97   size_t result = size_of_objects / mark_compact_speed_in_bytes_per_ms;
  98   return Min(result, kMaxMarkCompactTimeInMs);
  99 }
 100
 101
 102 size_t GCIdleTimeHandler::EstimateFinalIncrementalMarkCompactTime(
 103     size_t size_of_objects,
 104     size_t final_incremental_mark_compact_speed_in_bytes_per_ms) {
 105   if (final_incremental_mark_compact_speed_in_bytes_per_ms == 0) {
 106     final_incremental_mark_compact_speed_in_bytes_per_ms =
 107         kInitialConservativeFinalIncrementalMarkCompactSpeed;
 108   }
 109   size_t result =
 110       size_of_objects / final_incremental_mark_compact_speed_in_bytes_per_ms;
 111   return Min(result, kMaxFinalIncrementalMarkCompactTimeInMs);
 112 }
 113
 114
 115 bool GCIdleTimeHandler::ShouldDoScavenge(
 116     size_t idle_time_in_ms, size_t new_space_size, size_t used_new_space_size,
 117     size_t scavenge_speed_in_bytes_per_ms,
 118     size_t new_space_allocation_throughput_in_bytes_per_ms) {
 119   size_t new_space_allocation_limit =
 120       kMaxScheduledIdleTime * scavenge_speed_in_bytes_per_ms;
 121
 122   // If the limit is larger than the new space size, then scavenging used to be
 123   // really fast. We can take advantage of the whole new space.
 124   if (new_space_allocation_limit > new_space_size) {
 125     new_space_allocation_limit = new_space_size;
 126   }
 127
 128   // We do not know the allocation throughput before the first Scavenge.
 129   // TODO(hpayer): Estimate allocation throughput before the first Scavenge.
 130   if (new_space_allocation_throughput_in_bytes_per_ms == 0) {
 131     new_space_allocation_limit =
 132         static_cast<size_t>(new_space_size * kConservativeTimeRatio);
 133   } else {
 134     // We have to trigger scavenge before we reach the end of new space.
 135     new_space_allocation_limit -=
 136         new_space_allocation_throughput_in_bytes_per_ms * kMaxScheduledIdleTime;
 137   }
 138
 139   if (scavenge_speed_in_bytes_per_ms == 0) {
 140     scavenge_speed_in_bytes_per_ms = kInitialConservativeScavengeSpeed;
 141   }
 142
 143   if (new_space_allocation_limit <= used_new_space_size) {
 144     if (used_new_space_size / scavenge_speed_in_bytes_per_ms <=
 145         idle_time_in_ms) {
 146       return true;
 147     }
 148   }
 149   return false;
 150 }
 151
 152
 153 bool GCIdleTimeHandler::ShouldDoMarkCompact(
 154     size_t idle_time_in_ms, size_t size_of_objects,
 155     size_t mark_compact_speed_in_bytes_per_ms) {
 156   return idle_time_in_ms >= kMaxScheduledIdleTime &&
 157          idle_time_in_ms >=
 158              EstimateMarkCompactTime(size_of_objects,
 159                                      mark_compact_speed_in_bytes_per_ms);
 160 }
 161
 162
 163 bool GCIdleTimeHandler::ShouldDoContextDisposalMarkCompact(
 164     int contexts_disposed, double contexts_disposal_rate) {
 165   return contexts_disposed > 0 && contexts_disposal_rate > 0 &&
 166          contexts_disposal_rate < kHighContextDisposalRate;
 167 }
 168
 169
 170 bool GCIdleTimeHandler::ShouldDoFinalIncrementalMarkCompact(
 171     size_t idle_time_in_ms, size_t size_of_objects,
 172     size_t final_incremental_mark_compact_speed_in_bytes_per_ms) {
 173   return idle_time_in_ms >=
 174          EstimateFinalIncrementalMarkCompactTime(
 175              size_of_objects,
 176              final_incremental_mark_compact_speed_in_bytes_per_ms);
 177 }
 178
 179
 180 bool GCIdleTimeHandler::ShouldDoOverApproximateWeakClosure(
 181     size_t idle_time_in_ms) {
 182   // TODO(jochen): Estimate the time it will take to build the object groups.
 183   return idle_time_in_ms >= kMinTimeForOverApproximatingWeakClosureInMs;
 184 }
 185
 186
 187 GCIdleTimeAction GCIdleTimeHandler::NothingOrDone() {
 188   if (idle_times_which_made_no_progress_since_last_idle_round_ >=
 189       kMaxNoProgressIdleTimesPerIdleRound) {
 190     return GCIdleTimeAction::Done();
 191   } else {
 192     idle_times_which_made_no_progress_since_last_idle_round_++;
 193     return GCIdleTimeAction::Nothing();
 194   }
 195 }
 196
 197
 198 // The following logic is implemented by the controller:
 199 // (1) If we don't have any idle time, do nothing, unless a context was
 200 // disposed, incremental marking is stopped, and the heap is small. Then do
 201 // a full GC.
 202 // (2) If the new space is almost full and we can afford a Scavenge or if the
 203 // next Scavenge will very likely take long, then a Scavenge is performed.
 204 // (3) If there is currently no MarkCompact idle round going on, we start a
 205 // new idle round if enough garbage was created. Otherwise we do not perform
 206 // garbage collection to keep system utilization low.
 207 // (4) If incremental marking is done, we perform a full garbage collection
 208 // if  we are allowed to still do full garbage collections during this idle
 209 // round or if we are not allowed to start incremental marking. Otherwise we
 210 // do not perform garbage collection to keep system utilization low.
 211 // (5) If sweeping is in progress and we received a large enough idle time
 212 // request, we finalize sweeping here.
 213 // (6) If incremental marking is in progress, we perform a marking step. Note,
 214 // that this currently may trigger a full garbage collection.
 215 GCIdleTimeAction GCIdleTimeHandler::Compute(double idle_time_in_ms,
 216                                             HeapState heap_state) {
 217   if (static_cast<int>(idle_time_in_ms) <= 0) {
 218     if (heap_state.contexts_disposed > 0) {
 219       StartIdleRound();
 220     }
 221     if (heap_state.incremental_marking_stopped) {
 222       if (ShouldDoContextDisposalMarkCompact(
 223               heap_state.contexts_disposed,
 224               heap_state.contexts_disposal_rate)) {
 225         return GCIdleTimeAction::FullGC();
 226       }
 227     }
 228     return GCIdleTimeAction::Nothing();
 229   }
 230
 231   if (ShouldDoScavenge(
 232           static_cast<size_t>(idle_time_in_ms), heap_state.new_space_capacity,
 233           heap_state.used_new_space_size,
 234           heap_state.scavenge_speed_in_bytes_per_ms,
 235           heap_state.new_space_allocation_throughput_in_bytes_per_ms)) {
 236     return GCIdleTimeAction::Scavenge();
 237   }
 238
 239   if (IsMarkCompactIdleRoundFinished()) {
 240     if (EnoughGarbageSinceLastIdleRound()) {
 241       StartIdleRound();
 242     } else {
 243       return GCIdleTimeAction::Done();
 244     }
 245   }
 246
 247   if (heap_state.incremental_marking_stopped) {
 248     if (ShouldDoMarkCompact(static_cast<size_t>(idle_time_in_ms),
 249                             heap_state.size_of_objects,
 250                             heap_state.mark_compact_speed_in_bytes_per_ms)) {
 251       return GCIdleTimeAction::FullGC();
 252     }
 253   }
 254
 255   // TODO(hpayer): Estimate finalize sweeping time.
 256   if (heap_state.sweeping_in_progress) {
 257     if (static_cast<size_t>(idle_time_in_ms) >= kMinTimeForFinalizeSweeping) {
 258       return GCIdleTimeAction::FinalizeSweeping();
 259     }
 260     return NothingOrDone();
 261   }
 262
 263   if (heap_state.incremental_marking_stopped &&
 264       !heap_state.can_start_incremental_marking) {
 265     return NothingOrDone();
 266   }
 267
 268   size_t step_size = EstimateMarkingStepSize(
 269       static_cast<size_t>(kIncrementalMarkingStepTimeInMs),
 270       heap_state.incremental_marking_speed_in_bytes_per_ms);
 271   return GCIdleTimeAction::IncrementalMarking(step_size);
 272 }
 273 }
 274 }