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 {
StateState87     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 
99   enum EventType { kTimer, kMarkCompact, kContextDisposed };
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 
MemoryReducer(Heap * heap)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);
116   void NotifyContextDisposed(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 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 
heap()129   Heap* heap() { return heap_; }
130 
ShouldGrowHeapSlowly()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
168