• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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