Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | |
| 12 | namespace v8 { |
| 13 | namespace internal { |
| 14 | |
| 15 | class Heap; |
| 16 | |
| 17 | |
| 18 | // The goal of the MemoryReducer class is to detect transition of the mutator |
| 19 | // from high allocation phase to low allocation phase and to collect potential |
| 20 | // garbage created in the high allocation phase. |
| 21 | // |
| 22 | // The class implements an automaton with the following states and transitions. |
| 23 | // |
| 24 | // States: |
| 25 | // - DONE <last_gc_time_ms> |
| 26 | // - WAIT <started_gcs> <next_gc_start_ms> <last_gc_time_ms> |
| 27 | // - RUN <started_gcs> <last_gc_time_ms> |
| 28 | // The <started_gcs> is an integer in range from 0..kMaxNumberOfGCs that stores |
| 29 | // the number of GCs initiated by the MemoryReducer since it left the DONE |
| 30 | // state. |
| 31 | // The <next_gc_start_ms> is a double that stores the earliest time the next GC |
| 32 | // can be initiated by the MemoryReducer. |
| 33 | // The <last_gc_start_ms> is a double that stores the time of the last full GC. |
| 34 | // The DONE state means that the MemoryReducer is not active. |
| 35 | // The WAIT state means that the MemoryReducer is waiting for mutator allocation |
| 36 | // rate to drop. The check for the allocation rate happens in the timer task |
| 37 | // callback. If the allocation rate does not drop in watchdog_delay_ms since |
| 38 | // the last GC then transition to the RUN state is forced. |
| 39 | // The RUN state means that the MemoryReducer started incremental marking and is |
| 40 | // waiting for it to finish. Incremental marking steps are performed as usual |
| 41 | // in the idle notification and in the mutator. |
| 42 | // |
| 43 | // Transitions: |
| 44 | // DONE t -> WAIT 0 (now_ms + long_delay_ms) t' happens: |
| 45 | // - on context disposal. |
| 46 | // - at the end of mark-compact GC initiated by the mutator. |
| 47 | // This signals that there is potential garbage to be collected. |
| 48 | // |
| 49 | // WAIT n x t -> WAIT n (now_ms + long_delay_ms) t' happens: |
| 50 | // - on mark-compact GC initiated by the mutator, |
| 51 | // - in the timer callback if the mutator allocation rate is high or |
| 52 | // incremental GC is in progress or (now_ms - t < watchdog_delay_ms) |
| 53 | // |
| 54 | // WAIT n x t -> WAIT (n+1) t happens: |
| 55 | // - on background idle notification, which signals that we can start |
| 56 | // incremental marking even if the allocation rate is high. |
| 57 | // The MemoryReducer starts incremental marking on this transition but still |
| 58 | // has a pending timer task. |
| 59 | // |
| 60 | // WAIT n x t -> DONE t happens: |
| 61 | // - in the timer callback if n >= kMaxNumberOfGCs. |
| 62 | // |
| 63 | // WAIT n x t -> RUN (n+1) t happens: |
| 64 | // - in the timer callback if the mutator allocation rate is low |
| 65 | // and now_ms >= x and there is no incremental GC in progress. |
| 66 | // - in the timer callback if (now_ms - t > watchdog_delay_ms) and |
| 67 | // and now_ms >= x and there is no incremental GC in progress. |
| 68 | // The MemoryReducer starts incremental marking on this transition. |
| 69 | // |
| 70 | // RUN n t -> DONE now_ms happens: |
| 71 | // - at end of the incremental GC initiated by the MemoryReducer if |
| 72 | // (n > 1 and there is no more garbage to be collected) or |
| 73 | // n == kMaxNumberOfGCs. |
| 74 | // RUN n t -> WAIT n (now_ms + short_delay_ms) now_ms happens: |
| 75 | // - at end of the incremental GC initiated by the MemoryReducer if |
| 76 | // (n == 1 or there is more garbage to be collected) and |
| 77 | // n < kMaxNumberOfGCs. |
| 78 | // |
| 79 | // now_ms is the current time, |
| 80 | // t' is t if the current event is not a GC event and is now_ms otherwise, |
| 81 | // long_delay_ms, short_delay_ms, and watchdog_delay_ms are constants. |
| 82 | class MemoryReducer { |
| 83 | public: |
| 84 | enum Action { kDone, kWait, kRun }; |
| 85 | |
| 86 | struct State { |
| 87 | State(Action action, int started_gcs, double next_gc_start_ms, |
| 88 | double last_gc_time_ms) |
| 89 | : action(action), |
| 90 | started_gcs(started_gcs), |
| 91 | next_gc_start_ms(next_gc_start_ms), |
| 92 | last_gc_time_ms(last_gc_time_ms) {} |
| 93 | Action action; |
| 94 | int started_gcs; |
| 95 | double next_gc_start_ms; |
| 96 | double last_gc_time_ms; |
| 97 | }; |
| 98 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 99 | enum EventType { kTimer, kMarkCompact, kPossibleGarbage }; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 100 | |
| 101 | struct Event { |
| 102 | EventType type; |
| 103 | double time_ms; |
| 104 | bool next_gc_likely_to_collect_more; |
| 105 | bool should_start_incremental_gc; |
| 106 | bool can_start_incremental_gc; |
| 107 | }; |
| 108 | |
| 109 | explicit MemoryReducer(Heap* heap) |
| 110 | : heap_(heap), |
| 111 | state_(kDone, 0, 0.0, 0.0), |
| 112 | js_calls_counter_(0), |
| 113 | js_calls_sample_time_ms_(0.0) {} |
| 114 | // Callbacks. |
| 115 | void NotifyMarkCompact(const Event& event); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 116 | void NotifyPossibleGarbage(const Event& event); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 time_ms, 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 | |
| 129 | Heap* heap() { return heap_; } |
| 130 | |
| 131 | bool ShouldGrowHeapSlowly() { |
| 132 | return state_.action == kDone && state_.started_gcs > 0; |
| 133 | } |
| 134 | |
| 135 | private: |
| 136 | class TimerTask : public v8::internal::CancelableTask { |
| 137 | public: |
| 138 | explicit TimerTask(MemoryReducer* memory_reducer); |
| 139 | |
| 140 | private: |
| 141 | // v8::internal::CancelableTask overrides. |
| 142 | void RunInternal() override; |
| 143 | MemoryReducer* memory_reducer_; |
| 144 | DISALLOW_COPY_AND_ASSIGN(TimerTask); |
| 145 | }; |
| 146 | |
| 147 | void NotifyTimer(const Event& event); |
| 148 | |
| 149 | static bool WatchdogGC(const State& state, const Event& event); |
| 150 | |
| 151 | // Returns the rate of JS calls initiated from the API. |
| 152 | double SampleAndGetJsCallsPerMs(double time_ms); |
| 153 | |
| 154 | Heap* heap_; |
| 155 | State state_; |
| 156 | unsigned int js_calls_counter_; |
| 157 | double js_calls_sample_time_ms_; |
| 158 | |
| 159 | // Used in cctest. |
| 160 | friend class HeapTester; |
| 161 | DISALLOW_COPY_AND_ASSIGN(MemoryReducer); |
| 162 | }; |
| 163 | |
| 164 | } // namespace internal |
| 165 | } // namespace v8 |
| 166 | |
| 167 | #endif // V8_HEAP_memory_reducer_H |