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 113 explicit MemoryReducer(Heap* heap); 114 // Callbacks. 115 void NotifyMarkCompact(const Event& event); 116 void NotifyPossibleGarbage(const Event& event); 117 void NotifyBackgroundIdleNotification(const Event& event); 118 // The step function that computes the next state from the current state and 119 // the incoming event. 120 static State Step(const State& state, const Event& event); 121 // Posts a timer task that will call NotifyTimer after the given delay. 122 void ScheduleTimer(double delay_ms); 123 void TearDown(); 124 static const int kLongDelayMs; 125 static const int kShortDelayMs; 126 static const int kWatchdogDelayMs; 127 static const int kMaxNumberOfGCs; 128 // The committed memory has to increase by at least this factor since the 129 // last run in order to trigger a new run after mark-compact. 130 static const double kCommittedMemoryFactor; 131 // The committed memory has to increase by at least this amount since the 132 // last run in order to trigger a new run after mark-compact. 133 static const size_t kCommittedMemoryDelta; 134 heap()135 Heap* heap() { return heap_; } 136 ShouldGrowHeapSlowly()137 bool ShouldGrowHeapSlowly() { 138 return state_.action == kDone && state_.started_gcs > 0; 139 } 140 141 private: 142 class TimerTask : public v8::internal::CancelableTask { 143 public: 144 explicit TimerTask(MemoryReducer* memory_reducer); 145 146 private: 147 // v8::internal::CancelableTask overrides. 148 void RunInternal() override; 149 MemoryReducer* memory_reducer_; 150 DISALLOW_COPY_AND_ASSIGN(TimerTask); 151 }; 152 153 void NotifyTimer(const Event& event); 154 155 static bool WatchdogGC(const State& state, const Event& event); 156 157 Heap* heap_; 158 std::shared_ptr<v8::TaskRunner> taskrunner_; 159 State state_; 160 unsigned int js_calls_counter_; 161 double js_calls_sample_time_ms_; 162 163 // Used in cctest. 164 friend class HeapTester; 165 DISALLOW_COPY_AND_ASSIGN(MemoryReducer); 166 }; 167 168 } // namespace internal 169 } // namespace v8 170 171 #endif // V8_HEAP_MEMORY_REDUCER_H_ 172