1 // Copyright 2015 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 #ifndef V8_HEAP_memory_reducer_H 6 #define V8_HEAP_memory_reducer_H 7 8 #include "include/v8-platform.h" 9 #include "src/base/macros.h" 10 #include "src/cancelable-task.h" 11 #include "src/globals.h" 12 13 namespace v8 { 14 namespace internal { 15 16 class Heap; 17 18 19 // The goal of the MemoryReducer class is to detect transition of the mutator 20 // from high allocation phase to low allocation phase and to collect potential 21 // garbage created in the high allocation phase. 22 // 23 // The class implements an automaton with the following states and transitions. 24 // 25 // States: 26 // - DONE <last_gc_time_ms> 27 // - WAIT <started_gcs> <next_gc_start_ms> <last_gc_time_ms> 28 // - RUN <started_gcs> <last_gc_time_ms> 29 // The <started_gcs> is an integer in range from 0..kMaxNumberOfGCs that stores 30 // the number of GCs initiated by the MemoryReducer since it left the DONE 31 // state. 32 // The <next_gc_start_ms> is a double that stores the earliest time the next GC 33 // can be initiated by the MemoryReducer. 34 // The <last_gc_start_ms> is a double that stores the time of the last full GC. 35 // The DONE state means that the MemoryReducer is not active. 36 // The WAIT state means that the MemoryReducer is waiting for mutator allocation 37 // rate to drop. The check for the allocation rate happens in the timer task 38 // callback. If the allocation rate does not drop in watchdog_delay_ms since 39 // the last GC then transition to the RUN state is forced. 40 // The RUN state means that the MemoryReducer started incremental marking and is 41 // waiting for it to finish. Incremental marking steps are performed as usual 42 // in the idle notification and in the mutator. 43 // 44 // Transitions: 45 // DONE t -> WAIT 0 (now_ms + long_delay_ms) t' happens: 46 // - on context disposal. 47 // - at the end of mark-compact GC initiated by the mutator. 48 // This signals that there is potential garbage to be collected. 49 // 50 // WAIT n x t -> WAIT n (now_ms + long_delay_ms) t' happens: 51 // - on mark-compact GC initiated by the mutator, 52 // - in the timer callback if the mutator allocation rate is high or 53 // incremental GC is in progress or (now_ms - t < watchdog_delay_ms) 54 // 55 // WAIT n x t -> WAIT (n+1) t happens: 56 // - on background idle notification, which signals that we can start 57 // incremental marking even if the allocation rate is high. 58 // The MemoryReducer starts incremental marking on this transition but still 59 // has a pending timer task. 60 // 61 // WAIT n x t -> DONE t happens: 62 // - in the timer callback if n >= kMaxNumberOfGCs. 63 // 64 // WAIT n x t -> RUN (n+1) t happens: 65 // - in the timer callback if the mutator allocation rate is low 66 // and now_ms >= x and there is no incremental GC in progress. 67 // - in the timer callback if (now_ms - t > watchdog_delay_ms) and 68 // and now_ms >= x and there is no incremental GC in progress. 69 // The MemoryReducer starts incremental marking on this transition. 70 // 71 // RUN n t -> DONE now_ms happens: 72 // - at end of the incremental GC initiated by the MemoryReducer if 73 // (n > 1 and there is no more garbage to be collected) or 74 // n == kMaxNumberOfGCs. 75 // RUN n t -> WAIT n (now_ms + short_delay_ms) now_ms happens: 76 // - at end of the incremental GC initiated by the MemoryReducer if 77 // (n == 1 or there is more garbage to be collected) and 78 // n < kMaxNumberOfGCs. 79 // 80 // now_ms is the current time, 81 // t' is t if the current event is not a GC event and is now_ms otherwise, 82 // long_delay_ms, short_delay_ms, and watchdog_delay_ms are constants. 83 class V8_EXPORT_PRIVATE MemoryReducer { 84 public: 85 enum Action { kDone, kWait, kRun }; 86 87 struct State { StateState88 State(Action action, int started_gcs, double next_gc_start_ms, 89 double last_gc_time_ms, size_t committed_memory_at_last_run) 90 : action(action), 91 started_gcs(started_gcs), 92 next_gc_start_ms(next_gc_start_ms), 93 last_gc_time_ms(last_gc_time_ms), 94 committed_memory_at_last_run(committed_memory_at_last_run) {} 95 Action action; 96 int started_gcs; 97 double next_gc_start_ms; 98 double last_gc_time_ms; 99 size_t committed_memory_at_last_run; 100 }; 101 102 enum EventType { kTimer, kMarkCompact, kPossibleGarbage }; 103 104 struct Event { 105 EventType type; 106 double time_ms; 107 size_t committed_memory; 108 bool next_gc_likely_to_collect_more; 109 bool should_start_incremental_gc; 110 bool can_start_incremental_gc; 111 }; 112 MemoryReducer(Heap * heap)113 explicit MemoryReducer(Heap* heap) 114 : heap_(heap), 115 state_(kDone, 0, 0.0, 0.0, 0), 116 js_calls_counter_(0), 117 js_calls_sample_time_ms_(0.0) {} 118 // Callbacks. 119 void NotifyMarkCompact(const Event& event); 120 void NotifyPossibleGarbage(const Event& event); 121 void NotifyBackgroundIdleNotification(const Event& event); 122 // The step function that computes the next state from the current state and 123 // the incoming event. 124 static State Step(const State& state, const Event& event); 125 // Posts a timer task that will call NotifyTimer after the given delay. 126 void ScheduleTimer(double time_ms, double delay_ms); 127 void TearDown(); 128 static const int kLongDelayMs; 129 static const int kShortDelayMs; 130 static const int kWatchdogDelayMs; 131 static const int kMaxNumberOfGCs; 132 // The committed memory has to increase by at least this factor since the 133 // last run in order to trigger a new run after mark-compact. 134 static const double kCommittedMemoryFactor; 135 // The committed memory has to increase by at least this amount since the 136 // last run in order to trigger a new run after mark-compact. 137 static const size_t kCommittedMemoryDelta; 138 heap()139 Heap* heap() { return heap_; } 140 ShouldGrowHeapSlowly()141 bool ShouldGrowHeapSlowly() { 142 return state_.action == kDone && state_.started_gcs > 0; 143 } 144 145 private: 146 class TimerTask : public v8::internal::CancelableTask { 147 public: 148 explicit TimerTask(MemoryReducer* memory_reducer); 149 150 private: 151 // v8::internal::CancelableTask overrides. 152 void RunInternal() override; 153 MemoryReducer* memory_reducer_; 154 DISALLOW_COPY_AND_ASSIGN(TimerTask); 155 }; 156 157 void NotifyTimer(const Event& event); 158 159 static bool WatchdogGC(const State& state, const Event& event); 160 161 Heap* heap_; 162 State state_; 163 unsigned int js_calls_counter_; 164 double js_calls_sample_time_ms_; 165 166 // Used in cctest. 167 friend class HeapTester; 168 DISALLOW_COPY_AND_ASSIGN(MemoryReducer); 169 }; 170 171 } // namespace internal 172 } // namespace v8 173 174 #endif // V8_HEAP_memory_reducer_H 175