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/common/globals.h" 11 #include "src/tasks/cancelable-task.h" 12 13 namespace v8 { 14 namespace internal { 15 16 namespace heap { 17 class HeapTester; 18 } // namespace heap 19 20 class Heap; 21 22 23 // The goal of the MemoryReducer class is to detect transition of the mutator 24 // from high allocation phase to low allocation phase and to collect potential 25 // garbage created in the high allocation phase. 26 // 27 // The class implements an automaton with the following states and transitions. 28 // 29 // States: 30 // - DONE <last_gc_time_ms> 31 // - WAIT <started_gcs> <next_gc_start_ms> <last_gc_time_ms> 32 // - RUN <started_gcs> <last_gc_time_ms> 33 // The <started_gcs> is an integer in range from 0..kMaxNumberOfGCs that stores 34 // the number of GCs initiated by the MemoryReducer since it left the DONE 35 // state. 36 // The <next_gc_start_ms> is a double that stores the earliest time the next GC 37 // can be initiated by the MemoryReducer. 38 // The <last_gc_start_ms> is a double that stores the time of the last full GC. 39 // The DONE state means that the MemoryReducer is not active. 40 // The WAIT state means that the MemoryReducer is waiting for mutator allocation 41 // rate to drop. The check for the allocation rate happens in the timer task 42 // callback. If the allocation rate does not drop in watchdog_delay_ms since 43 // the last GC then transition to the RUN state is forced. 44 // The RUN state means that the MemoryReducer started incremental marking and is 45 // waiting for it to finish. Incremental marking steps are performed as usual 46 // in the idle notification and in the mutator. 47 // 48 // Transitions: 49 // DONE t -> WAIT 0 (now_ms + long_delay_ms) t' happens: 50 // - on context disposal. 51 // - at the end of mark-compact GC initiated by the mutator. 52 // This signals that there is potential garbage to be collected. 53 // 54 // WAIT n x t -> WAIT n (now_ms + long_delay_ms) t' happens: 55 // - on mark-compact GC initiated by the mutator, 56 // - in the timer callback if the mutator allocation rate is high or 57 // incremental GC is in progress or (now_ms - t < watchdog_delay_ms) 58 // 59 // WAIT n x t -> WAIT (n+1) t happens: 60 // - on background idle notification, which signals that we can start 61 // incremental marking even if the allocation rate is high. 62 // The MemoryReducer starts incremental marking on this transition but still 63 // has a pending timer task. 64 // 65 // WAIT n x t -> DONE t happens: 66 // - in the timer callback if n >= kMaxNumberOfGCs. 67 // 68 // WAIT n x t -> RUN (n+1) t happens: 69 // - in the timer callback if the mutator allocation rate is low 70 // and now_ms >= x and there is no incremental GC in progress. 71 // - in the timer callback if (now_ms - t > watchdog_delay_ms) and 72 // and now_ms >= x and there is no incremental GC in progress. 73 // The MemoryReducer starts incremental marking on this transition. 74 // 75 // RUN n t -> DONE now_ms happens: 76 // - at end of the incremental GC initiated by the MemoryReducer if 77 // (n > 1 and there is no more garbage to be collected) or 78 // n == kMaxNumberOfGCs. 79 // RUN n t -> WAIT n (now_ms + short_delay_ms) now_ms happens: 80 // - at end of the incremental GC initiated by the MemoryReducer if 81 // (n == 1 or there is more garbage to be collected) and 82 // n < kMaxNumberOfGCs. 83 // 84 // now_ms is the current time, 85 // t' is t if the current event is not a GC event and is now_ms otherwise, 86 // long_delay_ms, short_delay_ms, and watchdog_delay_ms are constants. 87 class V8_EXPORT_PRIVATE MemoryReducer { 88 public: 89 enum Action { kDone, kWait, kRun }; 90 91 struct State { StateState92 State(Action action, int started_gcs, double next_gc_start_ms, 93 double last_gc_time_ms, size_t committed_memory_at_last_run) 94 : action(action), 95 started_gcs(started_gcs), 96 next_gc_start_ms(next_gc_start_ms), 97 last_gc_time_ms(last_gc_time_ms), 98 committed_memory_at_last_run(committed_memory_at_last_run) {} 99 Action action; 100 int started_gcs; 101 double next_gc_start_ms; 102 double last_gc_time_ms; 103 size_t committed_memory_at_last_run; 104 }; 105 106 enum EventType { kTimer, kMarkCompact, kPossibleGarbage }; 107 108 struct Event { 109 EventType type; 110 double time_ms; 111 size_t committed_memory; 112 bool next_gc_likely_to_collect_more; 113 bool should_start_incremental_gc; 114 bool can_start_incremental_gc; 115 }; 116 117 explicit MemoryReducer(Heap* heap); 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 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 std::shared_ptr<v8::TaskRunner> taskrunner_; 163 State state_; 164 unsigned int js_calls_counter_; 165 double js_calls_sample_time_ms_; 166 167 // Used in cctest. 168 friend class heap::HeapTester; 169 DISALLOW_COPY_AND_ASSIGN(MemoryReducer); 170 }; 171 172 } // namespace internal 173 } // namespace v8 174 175 #endif // V8_HEAP_MEMORY_REDUCER_H_ 176