incremental-marking.h 9.93 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5 6
#ifndef V8_HEAP_INCREMENTAL_MARKING_H_
#define V8_HEAP_INCREMENTAL_MARKING_H_
7

8
#include "src/base/platform/mutex.h"
9
#include "src/heap/heap.h"
10
#include "src/heap/incremental-marking-job.h"
11
#include "src/heap/mark-compact.h"
12
#include "src/tasks/cancelable-task.h"
13 14 15 16

namespace v8 {
namespace internal {

17
class HeapObject;
18
class MarkBit;
19 20
class Map;
class Object;
21 22
class PagedSpace;

23
enum class StepOrigin { kV8, kTask };
24 25 26 27 28
enum class StepResult {
  kNoImmediateWork,
  kMoreWorkRemaining,
  kWaitingForFinalization
};
29

30
class V8_EXPORT_PRIVATE IncrementalMarking final {
31
 public:
32
  enum State : uint8_t { STOPPED, MARKING, COMPLETE };
33 34

  enum CompletionAction { GC_VIA_STACK_GUARD, NO_GC_VIA_STACK_GUARD };
35

36
  enum GCRequestType { NONE, COMPLETE_MARKING, FINALIZATION };
37

38 39 40
  using MarkingState = MarkCompactCollector::MarkingState;
  using AtomicMarkingState = MarkCompactCollector::AtomicMarkingState;
  using NonAtomicMarkingState = MarkCompactCollector::NonAtomicMarkingState;
41

42
  class V8_NODISCARD PauseBlackAllocationScope {
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
   public:
    explicit PauseBlackAllocationScope(IncrementalMarking* marking)
        : marking_(marking), paused_(false) {
      if (marking_->black_allocation()) {
        paused_ = true;
        marking_->PauseBlackAllocation();
      }
    }

    ~PauseBlackAllocationScope() {
      if (paused_) {
        marking_->StartBlackAllocation();
      }
    }

   private:
    IncrementalMarking* marking_;
    bool paused_;
  };

63 64 65 66 67 68 69 70 71 72
  // It's hard to know how much work the incremental marker should do to make
  // progress in the face of the mutator creating new work for it.  We start
  // of at a moderate rate of work and gradually increase the speed of the
  // incremental marker until it completes.
  // Do some marking every time this much memory has been allocated or that many
  // heavy (color-checking) write barriers have been invoked.
  static const size_t kYoungGenerationAllocatedThreshold = 64 * KB;
  static const size_t kOldGenerationAllocatedThreshold = 256 * KB;
  static const size_t kMinStepSizeInBytes = 64 * KB;

73 74
  static constexpr double kStepSizeInMs = 1;
  static constexpr double kMaxStepSizeInMs = 5;
75 76

#ifndef DEBUG
77 78
  static constexpr size_t kV8ActivationThreshold = 8 * MB;
  static constexpr size_t kGlobalActivationThreshold = 16 * MB;
79
#else
80 81
  static constexpr size_t kV8ActivationThreshold = 0;
  static constexpr size_t kGlobalActivationThreshold = 0;
82 83
#endif

84
#ifdef V8_ATOMIC_MARKING_STATE
85 86 87 88 89
  static const AccessMode kAtomicity = AccessMode::ATOMIC;
#else
  static const AccessMode kAtomicity = AccessMode::NON_ATOMIC;
#endif

90
  IncrementalMarking(Heap* heap, WeakObjects* weak_objects);
91

92
  MarkingState* marking_state() { return &marking_state_; }
93

94
  AtomicMarkingState* atomic_marking_state() { return &atomic_marking_state_; }
95

96 97
  NonAtomicMarkingState* non_atomic_marking_state() {
    return &non_atomic_marking_state_;
98
  }
99

100
  void NotifyLeftTrimming(HeapObject from, HeapObject to);
101

102
  V8_INLINE void TransferColor(HeapObject from, HeapObject to);
103

104
  State state() const {
105
    DCHECK(state_ == STOPPED || FLAG_incremental_marking);
106 107 108
    return state_;
  }

109 110
  bool finalize_marking_completed() const {
    return finalize_marking_completed_;
111 112
  }

113
  void SetWeakClosureWasOverApproximatedForTesting(bool val) {
114
    finalize_marking_completed_ = val;
115 116
  }

117
  inline bool IsStopped() const { return state() == STOPPED; }
118

119
  inline bool IsMarking() const { return state() >= MARKING; }
120

121
  inline bool IsMarkingIncomplete() const { return state() == MARKING; }
122

123
  inline bool IsComplete() const { return state() == COMPLETE; }
124

125
  inline bool IsReadyToOverApproximateWeakClosure() const {
126
    return request_type_ == FINALIZATION && !finalize_marking_completed_;
127 128
  }

129 130 131 132 133
  inline bool NeedsFinalization() {
    return IsMarking() &&
           (request_type_ == FINALIZATION || request_type_ == COMPLETE_MARKING);
  }

134 135
  GCRequestType request_type() const { return request_type_; }

136 137
  void reset_request_type() { request_type_ = NONE; }

138
  bool CanBeActivated();
139

140 141
  bool WasActivated();

142
  void Start(GarbageCollectionReason gc_reason);
143

144
  void FinalizeIncrementally();
145

146
  void UpdateMarkingWorklistAfterScavenge();
147
  void UpdateMarkedBytesAfterScavenge(size_t dead_bytes_in_new_space);
148 149 150 151 152

  void Hurry();

  void Finalize();

153
  void Stop();
154

155
  void FinalizeMarking(CompletionAction action);
156

157
  void MarkingComplete(CompletionAction action);
158

159 160
  void Epilogue();

161 162 163 164 165 166
  // Performs incremental marking steps and returns before the deadline_in_ms is
  // reached. It may return earlier if the marker is already ahead of the
  // marking schedule, which is indicated with StepResult::kDone.
  StepResult AdvanceWithDeadline(double deadline_in_ms,
                                 CompletionAction completion_action,
                                 StepOrigin step_origin);
167

168
  void FinalizeSweeping();
169
  bool ContinueConcurrentSweeping();
170
  void SupportConcurrentSweeping();
171

172 173
  StepResult Step(double max_step_size_in_ms, CompletionAction action,
                  StepOrigin step_origin);
174 175

  bool ShouldDoEmbedderStep();
176
  StepResult EmbedderStep(double expected_duration_ms, double* duration_ms);
177

178
  V8_INLINE void RestartIfNotMarking();
179

180 181
  // Returns true if the function succeeds in transitioning the object
  // from white to grey.
182
  V8_INLINE bool WhiteToGreyAndPush(HeapObject obj);
183

184 185 186
  // This function is used to color the object black before it undergoes an
  // unsafe layout change. This is a part of synchronization protocol with
  // the concurrent marker.
187
  void MarkBlackAndVisitObjectDueToLayoutChange(HeapObject obj);
188

189 190
  void MarkBlackBackground(HeapObject obj, int object_size);

191 192
  bool IsCompacting() { return IsMarking() && is_compacting_; }

193
  void ProcessBlackAllocatedObject(HeapObject obj);
194 195 196

  Heap* heap() const { return heap_; }

197 198 199 200
  IncrementalMarkingJob* incremental_marking_job() {
    return &incremental_marking_job_;
  }

hpayer's avatar
hpayer committed
201 202
  bool black_allocation() { return black_allocation_; }

203 204 205 206 207
  void StartBlackAllocationForTesting() {
    if (!black_allocation_) {
      StartBlackAllocation();
    }
  }
208

209 210
  MarkingWorklists::Local* local_marking_worklists() const {
    return collector_->local_marking_worklists();
211
  }
212

213 214
  void Deactivate();

215 216 217 218
  // Ensures that the given region is black allocated if it is in the old
  // generation.
  void EnsureBlackAllocated(Address allocated, size_t size);

219 220
  bool IsBelowActivationThresholds() const;

221 222 223 224 225
  void IncrementLiveBytesBackground(MemoryChunk* chunk, intptr_t by) {
    base::MutexGuard guard(&background_live_bytes_mutex_);
    background_live_bytes_[chunk] += by;
  }

226
 private:
227 228
  class Observer : public AllocationObserver {
   public:
229
    Observer(IncrementalMarking* incremental_marking, intptr_t step_size)
230 231 232
        : AllocationObserver(step_size),
          incremental_marking_(incremental_marking) {}

233
    void Step(int bytes_allocated, Address, size_t) override;
234 235

   private:
236
    IncrementalMarking* incremental_marking_;
237 238
  };

239
  void StartMarking();
240

hpayer's avatar
hpayer committed
241
  void StartBlackAllocation();
242
  void PauseBlackAllocation();
hpayer's avatar
hpayer committed
243 244
  void FinishBlackAllocation();

245
  void MarkRoots();
246
  bool ShouldRetainMap(Map map, int age);
247 248 249
  // Retain dying maps for <FLAG_retain_maps_for_n_gc> garbage collections to
  // increase chances of reusing of map transition tree in future.
  void RetainMaps();
250

251 252
  void PublishWriteBarrierWorklists();

253 254 255 256 257 258 259
  // Updates scheduled_bytes_to_mark_ to ensure marking progress based on
  // time.
  void ScheduleBytesToMarkBasedOnTime(double time_ms);
  // Updates scheduled_bytes_to_mark_ to ensure marking progress based on
  // allocations.
  void ScheduleBytesToMarkBasedOnAllocation();
  // Helper functions for ScheduleBytesToMarkBasedOnAllocation.
260 261
  size_t StepSizeToKeepUpWithAllocations();
  size_t StepSizeToMakeProgress();
262 263 264 265 266 267 268 269 270 271 272 273 274 275 276
  void AddScheduledBytesToMark(size_t bytes_to_mark);

  // Schedules more bytes to mark so that the marker is no longer ahead
  // of schedule.
  void FastForwardSchedule();
  void FastForwardScheduleIfCloseToFinalization();

  // Fetches marked byte counters from the concurrent marker.
  void FetchBytesMarkedConcurrently();

  // Returns the bytes to mark in the current step based on the scheduled
  // bytes and already marked bytes.
  size_t ComputeStepSizeInBytes(StepOrigin step_origin);

  void AdvanceOnAllocation();
277

278 279 280 281 282
  void SetState(State s) {
    state_ = s;
    heap_->SetIsMarkingFlag(s >= MARKING);
  }

283 284
  double CurrentTimeToMarkingTask() const;

285
  Heap* const heap_;
286
  MarkCompactCollector* const collector_;
287
  WeakObjects* weak_objects_;
288

289 290 291 292 293 294 295
  double start_time_ms_ = 0.0;
  double time_to_force_completion_ = 0.0;
  size_t initial_old_generation_size_ = 0;
  size_t old_generation_allocation_counter_ = 0;
  size_t bytes_marked_ = 0;
  size_t scheduled_bytes_to_mark_ = 0;
  double schedule_update_time_ms_ = 0.0;
296 297 298
  // A sample of concurrent_marking()->TotalMarkedBytes() at the last
  // incremental marking step. It is used for updating
  // bytes_marked_ahead_of_schedule_ with contribution of concurrent marking.
299
  size_t bytes_marked_concurrently_ = 0;
300

301
  // Must use SetState() above to update state_
302 303 304 305
  // Atomic since main thread can complete marking (= changing state), while a
  // background thread's slow allocation path will check whether incremental
  // marking is currently running.
  std::atomic<State> state_;
306

307 308 309 310
  bool is_compacting_ = false;
  bool was_activated_ = false;
  bool black_allocation_ = false;
  bool finalize_marking_completed_ = false;
311
  IncrementalMarkingJob incremental_marking_job_;
312

313
  std::atomic<GCRequestType> request_type_{NONE};
314

315 316
  Observer new_generation_observer_;
  Observer old_generation_observer_;
317

318 319 320
  MarkingState marking_state_;
  AtomicMarkingState atomic_marking_state_;
  NonAtomicMarkingState non_atomic_marking_state_;
321

322 323 324
  base::Mutex background_live_bytes_mutex_;
  std::unordered_map<MemoryChunk*, intptr_t> background_live_bytes_;

325 326
  DISALLOW_IMPLICIT_CONSTRUCTORS(IncrementalMarking);
};
327 328
}  // namespace internal
}  // namespace v8
329

330
#endif  // V8_HEAP_INCREMENTAL_MARKING_H_