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
9namespace v8 {
10namespace internal {
11
12const double GCIdleTimeHandler::kConservativeTimeRatio = 0.9;
13const size_t GCIdleTimeHandler::kMaxMarkCompactTimeInMs = 1000;
14const size_t GCIdleTimeHandler::kMinTimeForFinalizeSweeping = 100;
15const int GCIdleTimeHandler::kMaxMarkCompactsInIdleRound = 7;
16const int GCIdleTimeHandler::kIdleScavengeThreshold = 5;
17
18
19void GCIdleTimeAction::Print() {
20  switch (type) {
21    case DONE:
22      PrintF("done");
23      break;
24    case DO_NOTHING:
25      PrintF("no action");
26      break;
27    case DO_INCREMENTAL_MARKING:
28      PrintF("incremental marking with step %" V8_PTR_PREFIX "d", parameter);
29      break;
30    case DO_SCAVENGE:
31      PrintF("scavenge");
32      break;
33    case DO_FULL_GC:
34      PrintF("full GC");
35      break;
36    case DO_FINALIZE_SWEEPING:
37      PrintF("finalize sweeping");
38      break;
39  }
40}
41
42
43size_t GCIdleTimeHandler::EstimateMarkingStepSize(
44    size_t idle_time_in_ms, size_t marking_speed_in_bytes_per_ms) {
45  DCHECK(idle_time_in_ms > 0);
46
47  if (marking_speed_in_bytes_per_ms == 0) {
48    marking_speed_in_bytes_per_ms = kInitialConservativeMarkingSpeed;
49  }
50
51  size_t marking_step_size = marking_speed_in_bytes_per_ms * idle_time_in_ms;
52  if (marking_step_size / marking_speed_in_bytes_per_ms != idle_time_in_ms) {
53    // In the case of an overflow we return maximum marking step size.
54    return kMaximumMarkingStepSize;
55  }
56
57  if (marking_step_size > kMaximumMarkingStepSize)
58    return kMaximumMarkingStepSize;
59
60  return static_cast<size_t>(marking_step_size * kConservativeTimeRatio);
61}
62
63
64size_t GCIdleTimeHandler::EstimateMarkCompactTime(
65    size_t size_of_objects, size_t mark_compact_speed_in_bytes_per_ms) {
66  if (mark_compact_speed_in_bytes_per_ms == 0) {
67    mark_compact_speed_in_bytes_per_ms = kInitialConservativeMarkCompactSpeed;
68  }
69  size_t result = size_of_objects / mark_compact_speed_in_bytes_per_ms;
70  return Min(result, kMaxMarkCompactTimeInMs);
71}
72
73
74size_t GCIdleTimeHandler::EstimateScavengeTime(
75    size_t new_space_size, size_t scavenge_speed_in_bytes_per_ms) {
76  if (scavenge_speed_in_bytes_per_ms == 0) {
77    scavenge_speed_in_bytes_per_ms = kInitialConservativeScavengeSpeed;
78  }
79  return new_space_size / scavenge_speed_in_bytes_per_ms;
80}
81
82
83bool GCIdleTimeHandler::ScavangeMayHappenSoon(
84    size_t available_new_space_memory,
85    size_t new_space_allocation_throughput_in_bytes_per_ms) {
86  if (available_new_space_memory <=
87      new_space_allocation_throughput_in_bytes_per_ms *
88          kMaxFrameRenderingIdleTime) {
89    return true;
90  }
91  return false;
92}
93
94
95// The following logic is implemented by the controller:
96// (1) If the new space is almost full and we can effort a Scavenge, then a
97// Scavenge is performed.
98// (2) If there is currently no MarkCompact idle round going on, we start a
99// new idle round if enough garbage was created or we received a context
100// disposal event. Otherwise we do not perform garbage collection to keep
101// system utilization low.
102// (3) If incremental marking is done, we perform a full garbage collection
103// if context was disposed or if we are allowed to still do full garbage
104// collections during this idle round or if we are not allowed to start
105// incremental marking. Otherwise we do not perform garbage collection to
106// keep system utilization low.
107// (4) If sweeping is in progress and we received a large enough idle time
108// request, we finalize sweeping here.
109// (5) If incremental marking is in progress, we perform a marking step. Note,
110// that this currently may trigger a full garbage collection.
111GCIdleTimeAction GCIdleTimeHandler::Compute(size_t idle_time_in_ms,
112                                            HeapState heap_state) {
113  if (idle_time_in_ms <= kMaxFrameRenderingIdleTime &&
114      ScavangeMayHappenSoon(
115          heap_state.available_new_space_memory,
116          heap_state.new_space_allocation_throughput_in_bytes_per_ms) &&
117      idle_time_in_ms >=
118          EstimateScavengeTime(heap_state.new_space_capacity,
119                               heap_state.scavenge_speed_in_bytes_per_ms)) {
120    return GCIdleTimeAction::Scavenge();
121  }
122  if (IsMarkCompactIdleRoundFinished()) {
123    if (EnoughGarbageSinceLastIdleRound() || heap_state.contexts_disposed > 0) {
124      StartIdleRound();
125    } else {
126      return GCIdleTimeAction::Done();
127    }
128  }
129
130  if (idle_time_in_ms == 0) {
131    return GCIdleTimeAction::Nothing();
132  }
133
134  if (heap_state.incremental_marking_stopped) {
135    size_t estimated_time_in_ms =
136        EstimateMarkCompactTime(heap_state.size_of_objects,
137                                heap_state.mark_compact_speed_in_bytes_per_ms);
138    if (idle_time_in_ms >= estimated_time_in_ms ||
139        (heap_state.size_of_objects < kSmallHeapSize &&
140         heap_state.contexts_disposed > 0)) {
141      // If there are no more than two GCs left in this idle round and we are
142      // allowed to do a full GC, then make those GCs full in order to compact
143      // the code space.
144      // TODO(ulan): Once we enable code compaction for incremental marking, we
145      // can get rid of this special case and always start incremental marking.
146      int remaining_mark_sweeps =
147          kMaxMarkCompactsInIdleRound - mark_compacts_since_idle_round_started_;
148      if (heap_state.contexts_disposed > 0 ||
149          (idle_time_in_ms > kMaxFrameRenderingIdleTime &&
150           (remaining_mark_sweeps <= 2 ||
151            !heap_state.can_start_incremental_marking))) {
152        return GCIdleTimeAction::FullGC();
153      }
154    }
155    if (!heap_state.can_start_incremental_marking) {
156      return GCIdleTimeAction::Nothing();
157    }
158  }
159  // TODO(hpayer): Estimate finalize sweeping time.
160  if (heap_state.sweeping_in_progress &&
161      idle_time_in_ms >= kMinTimeForFinalizeSweeping) {
162    return GCIdleTimeAction::FinalizeSweeping();
163  }
164
165  if (heap_state.incremental_marking_stopped &&
166      !heap_state.can_start_incremental_marking) {
167    return GCIdleTimeAction::Nothing();
168  }
169  size_t step_size = EstimateMarkingStepSize(
170      idle_time_in_ms, heap_state.incremental_marking_speed_in_bytes_per_ms);
171  return GCIdleTimeAction::IncrementalMarking(step_size);
172}
173}
174}
175