Home | History | Annotate | Download | only in heap 
      1 // Copyright 2012 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_INCREMENTAL_MARKING_H_
      6 #define V8_HEAP_INCREMENTAL_MARKING_H_
      7 
      8 #include "src/cancelable-task.h"
      9 #include "src/execution.h"
     10 #include "src/heap/incremental-marking-job.h"
     11 #include "src/heap/spaces.h"
     12 #include "src/objects.h"
     13 
     14 namespace v8 {
     15 namespace internal {
     16 
     17 // Forward declarations.
     18 class MarkBit;
     19 class PagedSpace;
     20 
     21 class IncrementalMarking {
     22  public:
     23   enum State { STOPPED, SWEEPING, MARKING, COMPLETE };
     24 
     25   enum CompletionAction { GC_VIA_STACK_GUARD, NO_GC_VIA_STACK_GUARD };
     26 
     27   enum ForceMarkingAction { FORCE_MARKING, DO_NOT_FORCE_MARKING };
     28 
     29   enum ForceCompletionAction { FORCE_COMPLETION, DO_NOT_FORCE_COMPLETION };
     30 
     31   enum GCRequestType { COMPLETE_MARKING, FINALIZATION };
     32 
     33   struct StepActions {
     34     StepActions(CompletionAction complete_action_,
     35                 ForceMarkingAction force_marking_,
     36                 ForceCompletionAction force_completion_)
     37         : completion_action(complete_action_),
     38           force_marking(force_marking_),
     39           force_completion(force_completion_) {}
     40 
     41     CompletionAction completion_action;
     42     ForceMarkingAction force_marking;
     43     ForceCompletionAction force_completion;
     44   };
     45 
     46   static StepActions IdleStepActions();
     47 
     48   explicit IncrementalMarking(Heap* heap);
     49 
     50   static void Initialize();
     51 
     52   State state() {
     53     DCHECK(state_ == STOPPED || FLAG_incremental_marking);
     54     return state_;
     55   }
     56 
     57   bool should_hurry() { return should_hurry_; }
     58   void set_should_hurry(bool val) { should_hurry_ = val; }
     59 
     60   bool finalize_marking_completed() const {
     61     return finalize_marking_completed_;
     62   }
     63 
     64   void SetWeakClosureWasOverApproximatedForTesting(bool val) {
     65     finalize_marking_completed_ = val;
     66   }
     67 
     68   inline bool IsStopped() { return state() == STOPPED; }
     69 
     70   INLINE(bool IsMarking()) { return state() >= MARKING; }
     71 
     72   inline bool IsMarkingIncomplete() { return state() == MARKING; }
     73 
     74   inline bool IsComplete() { return state() == COMPLETE; }
     75 
     76   inline bool IsReadyToOverApproximateWeakClosure() const {
     77     return request_type_ == FINALIZATION && !finalize_marking_completed_;
     78   }
     79 
     80   GCRequestType request_type() const { return request_type_; }
     81 
     82   bool CanBeActivated();
     83 
     84   bool ShouldActivateEvenWithoutIdleNotification();
     85 
     86   bool WasActivated();
     87 
     88   void Start(const char* reason = nullptr);
     89 
     90   void FinalizeIncrementally();
     91 
     92   void UpdateMarkingDequeAfterScavenge();
     93 
     94   void Hurry();
     95 
     96   void Finalize();
     97 
     98   void Stop();
     99 
    100   void FinalizeMarking(CompletionAction action);
    101 
    102   void MarkingComplete(CompletionAction action);
    103 
    104   void Epilogue();
    105 
    106   // Performs incremental marking steps of step_size_in_bytes as long as
    107   // deadline_ins_ms is not reached. step_size_in_bytes can be 0 to compute
    108   // an estimate increment. Returns the remaining time that cannot be used
    109   // for incremental marking anymore because a single step would exceed the
    110   // deadline.
    111   double AdvanceIncrementalMarking(intptr_t step_size_in_bytes,
    112                                    double deadline_in_ms,
    113                                    StepActions step_actions);
    114 
    115   // It's hard to know how much work the incremental marker should do to make
    116   // progress in the face of the mutator creating new work for it.  We start
    117   // of at a moderate rate of work and gradually increase the speed of the
    118   // incremental marker until it completes.
    119   // Do some marking every time this much memory has been allocated or that many
    120   // heavy (color-checking) write barriers have been invoked.
    121   static const intptr_t kAllocatedThreshold = 65536;
    122   static const intptr_t kWriteBarriersInvokedThreshold = 32768;
    123   // Start off by marking this many times more memory than has been allocated.
    124   static const intptr_t kInitialMarkingSpeed = 1;
    125   // But if we are promoting a lot of data we need to mark faster to keep up
    126   // with the data that is entering the old space through promotion.
    127   static const intptr_t kFastMarking = 3;
    128   // After this many steps we increase the marking/allocating factor.
    129   static const intptr_t kMarkingSpeedAccellerationInterval = 1024;
    130   // This is how much we increase the marking/allocating factor by.
    131   static const intptr_t kMarkingSpeedAccelleration = 2;
    132   static const intptr_t kMaxMarkingSpeed = 1000;
    133 
    134   // This is the upper bound for how many times we allow finalization of
    135   // incremental marking to be postponed.
    136   static const size_t kMaxIdleMarkingDelayCounter = 3;
    137 
    138   void OldSpaceStep(intptr_t allocated);
    139 
    140   intptr_t Step(intptr_t allocated, CompletionAction action,
    141                 ForceMarkingAction marking = DO_NOT_FORCE_MARKING,
    142                 ForceCompletionAction completion = FORCE_COMPLETION);
    143 
    144   inline void RestartIfNotMarking() {
    145     if (state_ == COMPLETE) {
    146       state_ = MARKING;
    147       if (FLAG_trace_incremental_marking) {
    148         PrintF("[IncrementalMarking] Restarting (new grey objects)\n");
    149       }
    150     }
    151   }
    152 
    153   static void RecordWriteFromCode(HeapObject* obj, Object** slot,
    154                                   Isolate* isolate);
    155 
    156   // Record a slot for compaction.  Returns false for objects that are
    157   // guaranteed to be rescanned or not guaranteed to survive.
    158   //
    159   // No slots in white objects should be recorded, as some slots are typed and
    160   // cannot be interpreted correctly if the underlying object does not survive
    161   // the incremental cycle (stays white).
    162   INLINE(bool BaseRecordWrite(HeapObject* obj, Object* value));
    163   INLINE(void RecordWrite(HeapObject* obj, Object** slot, Object* value));
    164   INLINE(void RecordWriteIntoCode(HeapObject* obj, RelocInfo* rinfo,
    165                                   Object* value));
    166   INLINE(void RecordWriteOfCodeEntry(JSFunction* host, Object** slot,
    167                                      Code* value));
    168 
    169 
    170   void RecordWriteSlow(HeapObject* obj, Object** slot, Object* value);
    171   void RecordWriteIntoCodeSlow(HeapObject* obj, RelocInfo* rinfo,
    172                                Object* value);
    173   void RecordWriteOfCodeEntrySlow(JSFunction* host, Object** slot, Code* value);
    174   void RecordCodeTargetPatch(Code* host, Address pc, HeapObject* value);
    175   void RecordCodeTargetPatch(Address pc, HeapObject* value);
    176 
    177   void RecordWrites(HeapObject* obj);
    178 
    179   void BlackToGreyAndUnshift(HeapObject* obj, MarkBit mark_bit);
    180 
    181   void WhiteToGreyAndPush(HeapObject* obj, MarkBit mark_bit);
    182 
    183   inline void SetOldSpacePageFlags(MemoryChunk* chunk) {
    184     SetOldSpacePageFlags(chunk, IsMarking(), IsCompacting());
    185   }
    186 
    187   inline void SetNewSpacePageFlags(MemoryChunk* chunk) {
    188     SetNewSpacePageFlags(chunk, IsMarking());
    189   }
    190 
    191   bool IsCompacting() { return IsMarking() && is_compacting_; }
    192 
    193   void ActivateGeneratedStub(Code* stub);
    194 
    195   void NotifyOfHighPromotionRate();
    196 
    197   void EnterNoMarkingScope() { no_marking_scope_depth_++; }
    198 
    199   void LeaveNoMarkingScope() { no_marking_scope_depth_--; }
    200 
    201   void NotifyIncompleteScanOfObject(int unscanned_bytes) {
    202     unscanned_bytes_of_large_object_ = unscanned_bytes;
    203   }
    204 
    205   void ClearIdleMarkingDelayCounter();
    206 
    207   bool IsIdleMarkingDelayCounterLimitReached();
    208 
    209   INLINE(static void MarkObject(Heap* heap, HeapObject* object));
    210 
    211   Heap* heap() const { return heap_; }
    212 
    213   IncrementalMarkingJob* incremental_marking_job() {
    214     return &incremental_marking_job_;
    215   }
    216 
    217  private:
    218   class Observer : public InlineAllocationObserver {
    219    public:
    220     Observer(IncrementalMarking& incremental_marking, intptr_t step_size)
    221         : InlineAllocationObserver(step_size),
    222           incremental_marking_(incremental_marking) {}
    223 
    224     void Step(int bytes_allocated, Address, size_t) override {
    225       incremental_marking_.Step(bytes_allocated,
    226                                 IncrementalMarking::GC_VIA_STACK_GUARD);
    227     }
    228 
    229    private:
    230     IncrementalMarking& incremental_marking_;
    231   };
    232 
    233   int64_t SpaceLeftInOldSpace();
    234 
    235   void SpeedUp();
    236 
    237   void ResetStepCounters();
    238 
    239   void StartMarking();
    240 
    241   void MarkRoots();
    242   void MarkObjectGroups();
    243   void ProcessWeakCells();
    244   // Retain dying maps for <FLAG_retain_maps_for_n_gc> garbage collections to
    245   // increase chances of reusing of map transition tree in future.
    246   void RetainMaps();
    247 
    248   void ActivateIncrementalWriteBarrier(PagedSpace* space);
    249   static void ActivateIncrementalWriteBarrier(NewSpace* space);
    250   void ActivateIncrementalWriteBarrier();
    251 
    252   static void DeactivateIncrementalWriteBarrierForSpace(PagedSpace* space);
    253   static void DeactivateIncrementalWriteBarrierForSpace(NewSpace* space);
    254   void DeactivateIncrementalWriteBarrier();
    255 
    256   static void SetOldSpacePageFlags(MemoryChunk* chunk, bool is_marking,
    257                                    bool is_compacting);
    258 
    259   static void SetNewSpacePageFlags(MemoryChunk* chunk, bool is_marking);
    260 
    261   INLINE(void ProcessMarkingDeque());
    262 
    263   INLINE(intptr_t ProcessMarkingDeque(intptr_t bytes_to_process));
    264 
    265   INLINE(void VisitObject(Map* map, HeapObject* obj, int size));
    266 
    267   void IncrementIdleMarkingDelayCounter();
    268 
    269   Heap* heap_;
    270 
    271   Observer observer_;
    272 
    273   State state_;
    274   bool is_compacting_;
    275 
    276   int steps_count_;
    277   int64_t old_generation_space_available_at_start_of_incremental_;
    278   int64_t old_generation_space_used_at_start_of_incremental_;
    279   int64_t bytes_rescanned_;
    280   bool should_hurry_;
    281   int marking_speed_;
    282   intptr_t bytes_scanned_;
    283   intptr_t allocated_;
    284   intptr_t write_barriers_invoked_since_last_step_;
    285   size_t idle_marking_delay_counter_;
    286 
    287   int no_marking_scope_depth_;
    288 
    289   int unscanned_bytes_of_large_object_;
    290 
    291   bool was_activated_;
    292 
    293   bool finalize_marking_completed_;
    294 
    295   int incremental_marking_finalization_rounds_;
    296 
    297   GCRequestType request_type_;
    298 
    299   IncrementalMarkingJob incremental_marking_job_;
    300 
    301   DISALLOW_IMPLICIT_CONSTRUCTORS(IncrementalMarking);
    302 };
    303 }  // namespace internal
    304 }  // namespace v8
    305 
    306 #endif  // V8_HEAP_INCREMENTAL_MARKING_H_
    307